Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
5612953
Olnowich
March 18, 1997
Title
Multi-media serial line switching adapter for parallel networks and heterogeneous and homologous computer systems
Abstract
A generic network device for performing parallel or serial communications amongst multiple nodes over switching networks. An aspect is the adaptation of standard or proprietary serial interfaces using optical or electrical transmission to interface to the parallel switch. Converted serial data is routed to the selected destination through the parallel switch network. At the destination the data is converted back to a serial optical or electrical interface/protocol. Any number of different serial protocols can interface with the same parallel switch network allowing every node of the parallel system to send and receive messages in its native protocol. The switch enables generic networks forming a computer system with heterogeneous or homologous nodes.
Inventors:
Olnowich; Howard T.
(Endwell,
NY
)
Assignee:
International Business Machines Corporation
(Armonk,
NY
)
Appl. No.:
544625
Filed:
October 18, 1995
Current U.S. Class:
370/367
370/389
Field of Search:
370/60.16,60.1,94.1,94.2,94.3,58.1-58.3 340/895.79,895.8
U.S. Patent Documents
5136584
August 1992
Hedlund
5140583
August 1992
May et al.
5214640
May 1993
Sakurai et al.
5218465
June 1993
Lebby et al.
5229990
July 1993
Teraslinna
5285444
February 1994
Sakurai et al.
5287491
February 1994
Hsu
5321813
June 1994
McMillen et al.
Primary Examiner:
Olms; Douglas W.
Assistant Examiner:
Patel; Ajit
Attorney, Agent or Firm:
Shkurko; Eugene I. Beckstrand; Shelley M.
Parent Case Text
CROSS REFERENCE TO RELATED APPLICATIONS
This application is a continuation of application Ser. No. 08/178,974, filed Jan. 7, 1994, now abandoned which is a division of prior application Ser. No. 07/799,602 filed Nov. 27, 1991, now abandoned and is a continuation-in-part of the following related patent applications:
"Asynchronous Low Latency Data Recovery Apparatus and Method", Betts et al, U.S. Ser. No. 07/659,199, filed Feb. 22, 1991; now abandoned; and
"All-Node Switch, An Unclocked, Unbuffered Asynchronous Switching Apparatus" by P. A. Franaszek et al, U.S. Ser. No. 07/677,543, filed Mar. 29, 1991; now abandoned; and
"Broadcast/Switching Apparatus For Executing Broadcast/Multi-Cast" by H. T. Olnowich et al, U.S. Ser. No. 07/748,316, filed Aug. 21, 1991, now issued as U.S. Pat. No. 5,404,461; and
"Multi-Sender/Switching Apparatus For Status Reporting Over Unbuffered Asynchronous Multi-Stage Networks" by H. T. Olnowich et al, U.S. Ser. No. 07/748,302, filed Aug. 21, 1991; and
"Sync-Net--A Barrier Synchronization Apparatus For Multi-Stage Networks" by P. L. Childs et al, U.S. Ser. No. 07/748,303, filed Aug. 21, 1991, now issued as U.S. Pat. No. 5,365,228; and
"GVT-Net--A Global Virtual Time Calculation Apparatus For Multi-Stage Networks" by P. L. Childs et al, U.S. Ser. No. 07/748,295, filed Aug. 21, 1991, now issued as U.S. Pat. No. 5,250,943; and
in addition, concurrently filed herewith are related applications:
"Priority Broadcast And Multi-Cast For Unbuffered Multi-Stage Networks" by H. T. Olnowich et al, U.S. Ser. No. 07/799,262, filed Nov. 27, 1991;
The "Dual Priority Switching Apparatus for Simplex Networks" with H. T. Olnowich et al, U.S. Ser. No. 07/800,652, filed Nov. 27, 1991; now U.S. Pat. No. 5,444,705.
"Multi-Function Network" by H. T. Olnowich et al, U.S. Ser. No. 07/799,497, filed Nov. 27, 1991;
"Dynamic Multi-Mode Parallel Processor Array Architecture Computer System", P. Kogge, U.S. Ser. No. 07/798,788, Filed Nov. 27, 1991 abandoned.
These applications and the present application are owned by one and the same assignee, namely, International Business Machines Corporation of Armonk, N.Y.
The descriptions set forth in these applications are hereby incorporated into the present application by this reference.
CO-PENDING APPLICATION
There is a co-pending application U.S. Ser. No. 07/753,281, filed Aug. 30, 1991, issued as U.S. Pat. No. 5,307,342, with C. J. Georgiou and T. A. Larsen, inventors, entitled HETEROGENEOUS PORTS SWITCH, assigned in common to the assignee of this application.
Claims
What is claimed is:
1. A multi-stage bufferless and clockless switch network comprising:
a plurality of bufferless and clockless switch apparatuses cascaded into a plurality of stages, said switch apparatuses each including a plurality of switch inputs and a plurality of switch outputs, of the switch outputs included in each of said switch apparatuses each coupled to a different one of the switch apparatuses via a switch input of said different one of the switch apparatuses, switch outputs of last stage switch apparatuses each comprising a network output port and switch inputs of first stage switch apparatuses each comprising a network input port; and
said network output ports each coupled to a network input port through one of a plurality of nodes, each of said nodes comprising:
a processor operating under a native protocol, said native protocol different from an operating protocol of at least one other of the nodes;
means for receiving a data message from a coupled network output port; and
means for sending a data message to a coupled network input port, said data message to a coupled network input port including a path connection request;
said switch apparatuses each further including:
connection means for establishing a point-to-point communication path between any one of the network input ports and any one of the network output ports in response to said connection request received at said any one of the network input ports, said point-to-point communication path for transmitting a data message received at said any one of the network input ports to said any one of the network output ports;
multicast means for establishing a multicast communication path between said any one of the network input ports and any portion of the network output ports in response to said connection request received at said any one of the network input ports, said multicast communication path for transmitting the data message received at said any one of the network input ports simultaneously to said any portion of the network output ports;
broadcast means for establishing a broadcast communication path between said any one of the network input ports and all of the network output ports in response to said connection request received at said any one of the network input ports, said broadcast communication path for transmitting the data message received at said any one of the network input ports simultaneously to said all of the network output ports; and
asynchronous connection means for establishing asynchronously, in response to a plurality of path connection requests received separately or simultaneously at a plurality of network input ports, a plurality of concurrently active:
point-to-point communication paths,
multicast communication paths, and
point-to-point and multicast communications paths in combination,
said plurality of concurrently active point-to-point communication paths, multicast communication paths, and point-to-point and multicast communications paths in combination for transmitting concurrently a plurality of data messages received separately or simultaneously at said plurality Of the network input ports to a plurality of the network output ports.
2. The multi-stage bufferless and clockless switch network according to claim 1, wherein at least two processors each from separate nodes each comprise a parallel processing program for enabling processing in parallel, by said at least two processors, portions of an application program.
3. The multi-stage bufferless and clockless switch network according to claim 1, further comprising means for establishing any communication path in two data transmission cycles for each stage of the network traversed by said any communication path.
4. The multi-stage bufferless and clockless switch network according to claim 1, wherein the means for sending a data message to a coupled network input port includes a software interface driver for converting serial data to parallel data.
5. The multi-stage bufferless and clockless switch network according to claim 4, wherein the means for receiving a data message from a coupled network output port includes a software interface driver for converting parallel data to serial data.
6. The multi-stage bufferless and clockless switch network according to claim 5, wherein the means for sending and the means for receiving a data message include, respectively, means for sending and means for recognizing bit patterns denoting a start and an end of a data message.
7. The multi-stage bufferless and clockless switch network according to claim 2, wherein said application program includes a subroutine for transferring portions of the application program between said at least two processors.
8. The multi-stage bufferless and clockless switch network according to claim 2, wherein said application program includes a first subroutine for executing on a first one of said at least two processors and a second subroutine for executing on a second one of said at least two processors.
9. The multi-stage bufferless and clockless switch network according to claim 1, wherein each of the nodes further comprise a parallel processing program for enabling processing concurrently and in parallel, by all of the nodes, portions of an application program.
Description
FIELD OF THE INVENTION
The inventions relate to multi-stage switching networks, and particularly to systems which use fully parallel and unbuffered switching elements to comprise the multi- stage network. The inventions include applications adapting of serial fiber or copper wire transmission media to parallel switching networks for the purpose of line switching the serial data from various sources to various destinations through the parallel switching network, ways to couple the systems via RF to other systems, and to heterogeneous and homologous computers systems, and to applications for these systems.
BACKGROUND OF THE INVENTIONS
This application is directed to parallel processing, parallel switching networks, and particularly to an improved adaptation of serial fiber or copper wire and wireless transmission media to parallel switching networks for the purpose of interconnecting large numbers of processors with a minimal interface. With the interconnection network it is possible to connect individual processing elements on chips, say of the kind of Li et al, U.S. Pat. No. 4,783,738, issued Nov. 8, 1988, through a network. Through this minimal interface nodes can interact in parallel and form gateways to other nodes and networks, via bridges which may be of wire, fiber optics, wireless radio or other through the air or space transmissions. Thus the switch may form the basis of a generic network of great size and flexibility. The processors can be heterogeneous or homologous and the computer systems which are created by the developments have wide application. Some of these will be described in detail.
The inventions relate to networks. Networks of some type have existed for many years to connect sending devices to receiving devices, and the early networks were telephone related. Coexisting with these networks have been radio and other wireless transmitters and receivers. In recent years there has been a connections of wireless devices to land based systems. However, the existing systems have been to expensive and not sufficiently flexible for high speed parallel coupling of nodes over a network. This has remained a problem despite numerous prior developements and theory.
The practitioner in the computer field will be trained in some networks today. However, as there are many types, the training will not extend to the many available possibilities which have been developed in the network art. Among the most commonly used networks for digital communication between processors are the Ethernet or Token Ring of LAN networks. "Ethernet: Distributed Packet Switching for Local Computer Networks" Communications of the ACM, July 1976, Vol. 19, No. 7, pp. 395-404; and "Token-Ring Local-Area Networks and Their Performance", W. Bux, Proceedings of the IEEE, Vol 77, No. 2, February 1989, pp 238-256; are representative articles which describe this kind of network, which provide a serial shared medium used by one node at a time to send a message to another node or nodes.
"Data Networks", D. Bertsekas, R. Gallager, Prentice Hall, Inc. 1987, ISBN 0-13-196825-4 025, is a book which describes generally the art of data networks. It describes a broad range of networks and node-to-node communication, drawing on the works of others. FIG. 1.3 at Page 3 illustrates what is considered as a generic network, to which the inventions herein relate. It draws upon the work of many others but falls short in suggesting the solutions achieved by the present inventions.
There are many kinds of networks. "A Survey of Interconnection Networks", T. Feng, IEEE COMPUTER, 0018-1962/81/1200-0012, December 1981, pp 12-27, describes and categorizes the networks of the art. The present application describes something which would be classified as a dynamic network topology, which is of a non-blocking nature. Unlike the restricted networks described the network described in this application can be made to implement a variety of possible network designs. Other papers relating to high level considerations which may be reviewed include: "The Theory of Connecting Networks and Their Complexity: A Review", M. Marcus, Proceedings of the IEEE, Vol 65, No. 9, September 1977, pp 1263-1271; and "Interconnection Networks for SIMD Machines", H. Siegel, IEEE COMPUTER, June 1971, 0018-9162/79/0600-0057, pp. 57-65.
Historically many kinds of networks were developed for the telephone system. Telephone switching is described in "Circuit Switching: Unique Architecture and Application", A. Joel, Jr., IEEE COMPUTER, June 1979, 0018-9162/79/0600-0010, pp 10-22; however, this article considers circuit switching with time-multiplexing and frequency-multiplexing of messages simultaneously onto the same transmission medium, which ideas are not implemented in the preferred embodiment of the inventions here. There are nevertheless networks and network theory which has been developed for non-blocking telephone device to device interconnection. For instance, the CLOS network has been developed. Such kind of network could be formed by the presently described switch, but as will be appreciated from reading the detailed description of the inventions, the CLOS network does not suggest or describe our inventions. The basic work of Clos in non-blocking networks is thought to be "A Study of Non-Blocking Switching Networks", C. Clos, The Bell System Technical Journal, Vol. XXXII, March 1953, pages 406-424. It described a general method for making a network non-blocking (in a manner different from the present inventions preferred embodiment) by making the network large enough to always be able to connect an input to an output by adding more paths or stages to the network. This solution increase greatly costs of a network.
Other networks which could be created by the present inventions include complete and incomplete Hypercubes and Benes networks which are in turn derived from Clos. Hypercube type networks are described in "Incomplete Hypercubes", H. Katseff; IEEE Transactions on Computers, Vol. 37, No. 5, May 1988, 0018-9340/88/0500-0604, pp. 604-608; "Generalized Hypercube and Hyperbus Structures for a Computer Network", L. Bhuyan et al, IEEE Transactions on Computers, Vol. C-33, No. 1, April 1984, pp. 323-333
(EH0246-9/86/0000/0307-1984 IEEE); and The Indirect Binary n-Cube Microprocessor Array, M. Pease, III; IEEE Transactions on Computers, Vol C.26, No. 5, May 1977; pp 458-473. While a hypercube structure could be implemented with the present inventions, it is not our preferred embodiment. The hypercube can be much slower due to relays though nodes than is possible with the present structure of the preferred embodiment. Similarly, the Benes network, as described in "Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used Permutations", J. Lenfant, IEEE Transactions on Computers, VOl. C-27, No. 7, July 1978, pp 637-647, uses switches in a recurrent structure with a software algorithm for selecting a route. While such a structure could be implements with the switch of the present inventions, in our preferred embodiment the hardware is used to find a path through a parallel network, again something not suggested here.
Shuffle networks are still another kind of network. Parallel processing with a network as described in "Parallel Processing with the Perfect Shuffle", H. Stone, IEEE Transactions on Computers, Vol C-20, No. 2, February 1971 is a particular kind of multi-stage network with an interconnection pattern which is described as "Perfect Shuffle". This kind of network has better scalabability characteristics than some other networks, and sometimes can achieve good performance. Another application of a shuffle network is for SIMD, as described in "On the Augmented Data Manipulator in SIMD Environments". K. Lee et al, IEEE Transactions on Computers. Vol 37, No. 5, May 1988; pp 574-584; and in one of the related applications referenced above such a machine is disclosed. This perfect shuffle also could be implemented by the present structure, but the system which we have described for search has better non-blocking characteristics. It is also faster than any other known network, with extremely low message latency.
There are many, many facets for integrating computer systems, and with the move to open systems and distributed processing, those working at the highest level of expertise in the art continue to plow the ground of those who developed the theories elucidated in the past. The articles published in Proceedings, COMPUTER NETWORKING SYMPOSIUM, IEEE Computer Society, Apr. 11-13, 1988, IEE Catalog 88-CH2547-8, recognize the problems associated with heterogeneous environments and describe many protocols under consideration; while the Working Implementation Agreements for Open Systems Interconnection Protocols, F. Boland, Vol. 2, No. 1, 1989 Reprint Edition of NISTIR 89-4198, IEEE Computer Society Press, No 2042, ISBN 0-8186-2042-0, worked on message format and other aspects of file transfer between disparate systems which are generally used in commerce today. However, as indicated by the various articles in the Proceedings Vol. III, Ninth Annual Joint Conference on IEEE Computer and Communication Societies, The Multiple Facets of Integration; June 1990, IEEE Society Press. Cat No. 90CH2826-5 using the systems of the past requires much adaptation and considerable work, and there are many limitations which still need to be overcome particularly when many processors are intercoupled to send data between themselves.
The above articles may be supplemented by the patent literature. For instance, several patents may be contrasted to the present inventions. U.S. Pat. No. 4,484,325--4-WAY SELECTOR SWITCH, and U.S. Pat. No. 4,475,188--4-WAY ARBITRATION SWITCH, describe a switch itself, rather than a switch having any adapter for converting serial data to parallel switch data. The switch itself does not provide interfaces to fiber optics or standard protocols, which is an object of the present invention. The switch is not programmable or adaptable to various protocols--if fact it implements its own unique (nonstandard) protocol. This switch is organized as a 5 port solution which may allow better latency to the nearest neighbors, but increasingly worse latency to for larger systems. The switch is not equi-distant from all nodes, as is the present invention, which causes communication latency imbalance and difficulty of software routing and software switch management. The switch transfers one bit at a time with each bit requiring an individual handshake, which provides an unbelievably slow communication method--especially through a network. In contrast the present switch handshakes only the transmission of the entire message, which can be thousands or millions of bits--and thus provides a thousand or million times speed improvement. U.S. Pat. No. 4,482,996--Five Port Node, appears to be associated with the above patents and this patent relates to a node that attaches to the switch, rather than an adapter or a switch.
U.S. Pat. No. 4,307,446--Digital Networks Employing Speed Independent Switches deals with smaller selector and arbitration switches. It describes any combination of one or two input and output ports, but not larger. This patent has the problems mentioned, except this doesn't require a LAN connection and permits multi-stage networks. However, the small size switch may be okay for small systems, but cumbersome and slow for massively parallel systems. It also provides a non-standard serial interface directly and is not provided with anything like the adapters here disclosed, nor does it appear to have considered any flexibility to handle various protocols.
Other patents which may be thought by some to have some elements which are in common with those of the disclosure include: U.S. Pat. No. 4,929,939, entitled High Speed Switching System with Flexible Protocol Capability, by C. J. Georgious and T. A. Larsen. It generally describes a modular multi-plane cross-point switching system which allows efficient switching of both short and long messages. The switching system consists of two distinct types of switching planes, data planes and control/data planes. The data planes are used solely for the purpose of transferring data and contain no hardware to extract control information from the message or to determine the setting of the crosspoints in the plane. The control/data planes perform the dual functions of transferring data as well as setting up the switch planes based on control information extracted from the message. The system provides two modes for communication between processors. Shod messages are switched through the control/data planes using message switching to achieve low latency. Long messages are transferred by distributing the data across all the switching planes by means of a protocol based on circuit switching. The basic switch is for a plurality of processors, and the switching station comprises a plurality of switching planes for transferring data therethrough; a plurality of data links, each of said data links being coupled at a first end thereof to a respective one of said switching planes and at a second end thereof to one of said processors; at least one of said switching planes is a control/data plane with controls for controlling the transfer therethrough of data and for controlling data transfer through other of said switching planes; and the switching station is operable in a first mode wherein only said one switching plane is used for data transfer and in a second mode wherein said one switching plane and said other switching planes are used for data transfer. This type of switching system may be called a collision crossbar. It requires at least 10 clocks to set up every stage, is synchronous, and requires up to 5 different networks working in harmony to function properly. Basically it is slower, more expensive than the present ALLNODE Switch--and requires complex synchronization. It is an attempt to make one large crossbar to interconnect all nodes rather than using a multi-stage network. They attempt to solve the large crossbar pin problem by making the crossbar only 1 bit wide and calling it a switch plane, and using several or many switch planes in parallel to get wider data transfers. It uses data planes and control planes and combinations of the two. However, the various planes must be synchronized and problems exist in resolving contention for a given node that could lead to circuit stressing and degraded performance. The various multiple planes are not needed with the present improvements. Another patent of the same nature is represented by the CROSS-POINT SWITCH OF MULTIPLE AUTONOMOUS PLANES. U.S. Pat. No. 4,695,999, which also shows a multi-plane cross-point switching system in which a communication message from a sender is shown. Here the communication is divided into a plurality of data links which are separately connected through autonomous cross-point switches to the receiver where the links are recombined. The cross-points in each plane are separately set by control messages transmitted along with the separate parts of the divided message. While divided messages are possible with the present invention the means disclosed is complex and not simple. Synchronizing planes is still a problem here. The ALLNODE Switch avoids these problems and operates more simply. Further this prior patent cannot adapt various serial protocols to communicate to each other as the present disclosure does; they cannot intermix serial and parallel transfers.
U.S. Pat. No. 4,763,122 entitled Parallel Switching with Round Robin Priority, by P. A. Franaszek, describes another scheme for determining priority of users for a transmission line. This also occurs in the cross point switch described described in U.S. Pat. No. 4,929,939, where multiple planes are used. U.S. Pat. No. 4,763,122 describes how some of these planes can be used to perform a round robin priority scheme which is not needed with the disclosed apparatus.
U.S. Pat. No. 4,961,140 entitled A NEW ADDRESS/DATA/COMMUNICATION INPUT OUTPUT BUS INCLUDING A NEW COMMANDS AND INSTRUCTIONS BEING USED AS A RESULT OF THE NEW IMPLEMENTATION OF THE NEW BUS IN A MULTIPROCESSOR COMPUTER SYSTEM describes a single processor to multiple I/O device interface over a bus rather than a switch. This describes something like a microchannel bus and is related only in that the present preferred embodiments can communicate via a microchannel bus.
U.S. Pat. No. 4,803,485--LAN COMMUNICATION SYSTEM, represents a LAN approach which use of the present inventions would replace. This patent describes a medium conversion adapter similar to the present invention, but for adapting various protocols to a communication system having multiple transmission medium segments in a ring configuration, like a token ring or LAN. The token ring can have fiber or metallic interconnections. The present invention differs in that it adapts multiple transmission medium segments in an unbuffered multi-stage parallel transfer configuration, that gets latencies in the sub-microsecond range, rather than in the millisecond range of LAN's, that provides simultaneous and equi-distant communication paths, whose transmission bandwidth and number of simultaneous paths scale with increased system size. The present invention is the replacement for the state-of-the-art LAN approach that reduce latency and improve bandwidth by many orders of magnitude. These differences will be of value in the future.
Harold Stone in his book "High-Performance Computer Architecture", Addison Wesley 1990 recognizes (p. 309) that there is a need in architectures which are parallel for machine mechanisms which minimize overhead required among processors jointly working on the job. The overhead needed need to be solved, and effectively. Interconnection thorough existing networks is slow, and with heterogeneous networks for large interactive data exchanges intolerably slow. While more detail will be found in the detailed description below, it should be recognized that there is a need for an inexpensive high speed switching device which can be used as a "generic". This is an achievement of the present inventions. The achievement allows creating of many new computer systems with heterogeneous and homologous processors, and can be used as a generic network interconnection device for high speed transfers.
SUMMARY OF THE INVENTIONS
The present invention provides a generic solution applicable to performing either parallel or serial communications amongst multiple nodes over switching networks. In particular, the disclosure applies to byte-wide parallel hardware using parallel crossbar switches for a byte parallel multi-sized interface switch for communicating over multi-staged switching networks using electrical switching components. The switch which is described can be manufactured with VLSI technology, and can be made with various technologies on a chip. It becomes the stage of a multi-stage generic network. The switch is a dynamic switch which can be applied with non-blocking for point to point connection of nodal points (to processors) with an apparently optimal two cycle connect time per stage. The number of points connected depends upon the selection of stages applied.
The MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER and the parallel switching network make it feasible for serial message data to be switched and routed to various destinations. This means that for the first time, a parallel electrical switch can efficiently handle either optical or electrical serial data and provide the features required for parallel processing and "farm" approaches, such as low latency, high bandwidth, scalability, fault tolerance, and high reliability. In addition, further flexibility is provided which permits the MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER to be personalized to support the any one of a number of standard and proprietary serial protocols. A personalization PROM is part of the disclosure and specifies the particular serial protocol that each individual adapter is to support. The parallel switching network becomes a flexible media that interconnects and allows different serial protocols to communicate with each other; i.e., any number of different serial protocols can interface with the same parallel switch network. This allows every node of the parallel system to send and receive messages using its own native protocol. However, a node is not restricted to communicating only with others nodes using the same protocol, but it can communicate with any of the other nodes regardless of the serial protocol they use.
One aspect of this solution permits direct parallel electrical tie-in to the parallel switch interface using copper wire. This approach is efficient and economical for short distance connections of 100 ft. or less, but it is not a comprehensive solution that allows longer interconnection distances. Also, as the number of interconnecting nodes increases the cabling complexity becomes worse because of the large number of parallel wires required. In addition, the native parallel switch interface is not a standard interface and there are no existing CPU's or workstations that standardly support the parallel switch interface that would tie directly into the parallel switch.
The second and key aspect of the present invention is the adaptation of standard and proprietary serial interfaces using either optical or electrical transmission media to interface to the parallel switch. A first MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER, disclosed herein, receives either serial optical or electrical interfaces/protocols and converts them into the parallel electrical interfaces/protocols required by the parallel switch. The converted serial data is routed to the selected destination through the parallel switch network, where it is received by a second MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER and converted back into a serial optical or electrical interface/protocol. Both the electrical and optical interfaces can serve as a gateway to wireless transmitters and receivers.
The function of providing compatibility amongst various protocols is provided by the present invention. A node sending a serial message transmits the message in its native protocol over fiber or copper wire to a first MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER, which is dedicated entirely to that individual node and is personalized by the PROM to understand the protocol generated by that node. The first MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER converts the first serial protocol to the parallel protocol of the ALLNODE switch and forwards the converted message to the parallel network. The message is routed through the network to the selected destination, where it is received by a second MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER. The second MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER converts the parallel message it receives in the parallel switch protocol to a second serial protocol the protocol defined by its personalization PROM and which is the native protocol understood by the receiving node. The second MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER then forwards the message serially to the receiving node over either fiber or copper wire. The first and second serial protocols can be the same or different, and the transfer will be accomplished equally well.
In accordance with our inventions, it is also possible to intermix transfers to or from nodes which implement the parallel switch interface directly. In this case, the conversion provided by one or both MULTI-MEDIA SERIAL LINE SWITCHING ADAPTERS can be bypassed because the message already exists in the appropriate protocol as it either comes directly from a sending node or goes directly to a receiving node.
In accordance with our inventions, we provide a programmable protocol conversion circuit which works equally well for transmitting serial messages across parallel networks regardless of the number of network stages or the size of the network.
In addition, the invention apparatus has the .capability of providing a positive feedback acknowledgment that it has successfully transmitted the serial message across the parallel network.
Among the things that these basic and generic features provide is a computer system which can have many many nodes interconnected through and in which the interconnection network provides means for interconnecting for parallel transmission through a node point matrix controlled switch signals enabling coupling set up of a dynamic switching asynchronous network in two cycles a switch. In such a system the set-up is parallel and non-blocking is achieved by alternate paths.
Thus the interconnection network can couple processor nodal points of a dynamic multi-stage switching network for transmitting n messages to n nodal points at the same time or over lapped in any manner as part of a heterogeneous and/or homologous system.
The computer system can have a plurality of heterogeneous and/or homologous processors, with an interconnection network for coupling n processors to n processors via optional parallel channels, or via serial optical, electrical or wireless adapters, to permit n messages to be transmitted dynamically with no significant latency over direct or alternative network paths.
The computer interconnection device provides a network with the matrix controlled switch with parallel set-up providing an interconnection network for asynchronously and dynamically coupling n processor to n processor nodal points point to point with a set up of two cycles per stage. The latency of a switch matrix may be in the range of 150 ns with a delay per stage in the range of 10 nano seconds. With the current bandwidth of my design which is being manufactured, 40 MBS is achieved, and this may be increased. The preferred embodiment utilizes a microchannel interface which has practical advantages, and the low latency which is achieved is considered to be a most important feature. This latency can be lowered with more dense packaging, a dense CMOS, or even more with bi-polar or other higher speed logic.
A computer interconnection device made can generically have a plurality of processor nodes, the interconnection network, and the system can use one or more of the processors for coupling messages comprising parts or all of a message from one or more sending nodes to a plurality of receiving nodes, enabling simulcast of point to point broadcast of instructions and data messages for voice, data and image information from said one or more senders. This application may be useful in control, simulation, and for teaching. In fact, a multimedia system with parallel connections though the interconnection matrix permits a plurality of processor nodes to couple through the interconnection network time variable original digitized data from one or more sending nodes to a plurality of receiving nodes, enabling parallel simulcast of point to point broadcast of instructions and data messages for voice, data and image information from said one or more sending nodes for coherent intermixed presentation of said broadcast information. You can have a digital video presentation with different voice inputs, you can use different languages, all of which might match a scroll or other presentation of stored information.
These features and other improvements are described in the following description. For a better understanding of the inventions, together with related features, reference may be made to the previous ALL-NODE switch application for background. Further, specifically as to the improvements described herein, reference should be made to the following description and the associated drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates generally our preferred embodiment of the present invention of a Multi-Media Serial Adaptation apparatus, which has the capability of interconnecting fiber or copper serial channels to a parallel switching network.
FIG. 2 illustrates the capability of the present invention to perform protocol conversions, which enable fiber serial channels and copper serial channels having various and different protocols to be adapted to the same parallel switch protocol, therefore enabling them to communicate with each other.
FIG. 3 illustrates the capability of the present invention to provide a multiple serial connections means which allows many processors of the same or different architectures to communicate quickly and efficiently to provide a farm or joint processing capability.
FIG. 4 illustrates the advantages of the present invention to establish fully parallel switch network connections with unlimited expansion capabilities, as compared to the state-of-the-art matrix switch networks which are neither fully parallel nor easy to expand.
FIG. 5 illustrates a previously disclosed four input and four output (4.times.4) crossbar switching apparatus, which has the capability of being used with the present invention to provide fully parallel switching means for interconnecting up to four system nodes, as previously disclosed in the prior parent application U.S. Ser. No. 07/677,543.
FIG. 6 shows in more detail, as illustrated also in the prior parent application U.S. Ser. No. 07/677,543, the detailed schematic of the 4.times.4 crossbar switching apparatus and its interface connections.
FIG. 7 shows a typical method for cascading the 4.times.4 prior parent embodiment of the invention switching apparatus to accommodate systems having more than 4 nodes.
FIG. 8 shows a schematic block diagram of the simple data flow and control path implementations of the 4.times.4 prior parent embodiment of the invention switching apparatus.
FIG. 9 illustrates a typical method for generating parallel control and and multiple line serial data information to be sent to the 4.times.4 prior parent embodiment of the invention switching apparatus over four synchronous data lines.
FIG. 10 shows a typical timing diagram for routing the interface signals arriving at one input port of the 4.times.4 prior parent embodiment of the invention switching apparatus to one output port.
FIG. 11 illustrates the typical method of selecting and establishing a transmission path through a network comprised of the invention switching apparatus for the purpose of sending data from one node to another.
FIG. 12 illustrates generally our preferred embodiment of the parent switching apparatus to be used with the present invention apparatus to provide an 8 input and 8 output (8.times.8) crossbar switching apparatus having 8 multiple serial data data paths to provide increased performance.
FIG. 13 illustrates typical method for cascading the preferred embodiment switching apparatus to accommodate systems having up to 64 nodes by employing two stages of switches.
FIG. 14 shows a schematic block diagram of our preferred embodiment of the present invention of a Multi-Media Serial Adaptation apparatus, showing the function it performs of connecting serial fiber or copper interfaces to a parallel switching network.
FIG. 15 shows a schematic block diagram of the general functions performed by fiber optic modules and how they relate to the present invention.
FIG. 16 shows a schematic block diagram of our preferred embodiment of the continuous sequence support provided as a portion of the present invention to continuously monitor fiber optic serial data.
FIG. 17 shows a schematic block diagram of our preferred embodiment of the serial-frame receive and protocol translation functions provided as a portion of the present invention to adapt serial data protocols to the preferred parallel switch protocol.
FIG. 18 shows a schematic block diagram of our preferred embodiment of the buffer memory for the purpose of temporarily storing messages being sent from the serial channels to the parallel switch network.
FIG. 19 shows a schematic logic diagram of our preferred embodiment of the serial frame receive and protocol translation function provided for the purpose of recognizing the start of a serial frame of message data arriving at the present invention over serial fiber or copper input channels.
FIG. 20 shows a schematic logic diagram of our preferred embodiment of the serial frame receive and protocol translation function provided for the purpose of recognizing the end of a serial frame of message data arriving at the present invention over serial fiber or copper input channels.
FIG. 21 shows a schematic logic diagram of our preferred embodiment of the serial frame receive and protocol translation function provided for the purpose of recognizing the aborting of a serial frame of message data arriving at the present invention over serial fiber or copper input channels.
FIG. 22 shows a detailed logic diagram of the timing function of our preferred embodiment of the serial frame receive and protocol translation function of the present invention.
FIG. 23 shows an additional detailed logic diagram of the timing and control function of our preferred embodiment of the serial frame receive and protocol translation function of the present invention.
FIG. 24 is a timing diagram, which shows a typical example of the serial frame receive and protocol translation function of the present invention receiving and translating the protocol for a message frame received over the serial fiber or copper interface.
FIG. 25 shows a detailed logic diagram of the function performed by our preferred embodiment of the serial frame receive and protocol translation function of the present invention to reconstruct the serial message frame into the protocol to be sent to the parallel switch network.
FIG. 26 shows a detailed logic diagram of the message parameter registers required by our preferred embodiment of the serial frame receive and protocol translation function of the present invention to translate protocols.
FIG. 27 shows a schematic diagram of the preferred embodiment of the parallel switch protocol and the command field provided as a means of communication with the switching network by the present invention.
FIG. 28 shows a detailed logic diagram of the timing function of our preferred embodiment of the network send function of the present invention, which accesses messages from the send buffer and transmits them to the parallel switch network.
FIG. 29 shows a detailed logic diagram of the control function of our preferred embodiment of the network send function of the present invention.
FIG. 30 shows a detailed logic diagram of the termination and retry functions of our preferred embodiment of the network send function of the present invention.
FIG. 31 is a timing diagram, which shows a typical example of the network send function in regards to the control and establishment of connections in the parallel switch network.
FIG. 32 is a timing diagram, which shows a typical example of the network send function in regards to sending a message to a previously established path in the parallel switch network.
FIG. 33 is a timing diagram, which shows a typical example of the network send function in regards to the connection in the parallel switch network being busy and causing a rejection of the message.
FIG. 34 shows a detailed logic diagram of the serial link control functions of our preferred embodiment of the network send function of the present invention.
FIG. 35 shows a schematic block diagram of our preferred embodiment of the buffer memory for the purpose of temporarily storing messages being sent from the parallel switch network to the serial channels.
FIG. 36 shows a detailed logic diagram of the timing function of our preferred embodiment of the network receive function of the present invention, which receives messages from parallel switch network and stores them in the receive buffer memory.
FIG. 37 shows a detailed logic diagram of the control function of our preferred embodiment of the network receive function of the present invention.
FIG. 38 is a timing diagram, which shows a typical example of the network receive function in regards to receiving a message from the parallel switch network and storing it in the receive buffer memory.
FIG. 39 shows a schematic block diagram of our preferred embodiment of the serial frame transmit and protocol translation functions provided as a portion of the present invention to send serial data protocols over fiber or copper channels when communications are received from the parallel switch network.
FIG. 40 shows a detailed logic diagram of the timing function of our preferred embodiment of the serial frame transmit and protocol translation function of the present invention.
FIG. 41 shows an additional detailed logic diagram of the timing and control function of our preferred embodiment of the serial frame transmit and protocol translation function of the present invention.
FIG. 42 is a timing diagram, which shows a typical example of the serial frame transmit and protocol translation function of the present invention receiving and translating the protocol for a message received over the parallel switch network.
FIG. 43 shows a detailed logic diagram of the termination control and error detection function of our preferred embodiment of the serial frame transmit and protocol translation function of the present invention.
FIG. 44 shows a detailed logic diagram of the serial data generation function of our preferred embodiment of the serial frame transmit and protocol translation function of the present invention.
FIG. 45 shows a detailed logic diagram of the message parameter registers required by our preferred embodiment of the serial frame transmit and protocol translation function of the present invention to translate protocols.
FIG. 46 shows a typical Alternate Path configuration as a 3-stage network as applied to a 64 node system that provides 8 alternate paths between any two nodes and always permits a non-blocked path to be found between any two IDLE nodes by searching.
FIG. 47 shows a farm, illustrating a prior art laboratory which uses a LAN, which LAN can be replaced by a parallel switch configuration which provides LAN and WAN functions to illustrate an application of the present invention.
FIG. 48 shows an application accelerator schematic, while
FIG. 49 shows a typical application planar, and
FIG. 50 shows multiple unit configurations which illustrates various applications of the heterogenous and homogenous computer systems.
DETAILED DESCRIPTION OF THE INVENTIONS
Introduction to the Applications
The heterogeneous and/or homologous processors in accordance with the inventions can be to be interconnected to form a shared processing resource--a "farm" of processors--to provide either massive joint computational power for a single task or individual processors assignable to individual tasks. Corporations are beginning to view this type of "farm" approach as being very valuable. Individual workstations can be purchased and given to individual employees to support their work effort during the day. However, in the evenings or on weekends, the workstations are networked together to form a massive processing base for performing batch jobs or parallel processing. Industry should note that massive processing power can be obtained at a lower cost by investing in less expensive workstations, rather than in the traditional single large mainframe processor.
The state-of-the-art serial set up line switches such as those now being made within IBM and which may be provided by others are not thought effectively meet the requirements of the new "farm" systems. First, they are inflexible and dictate that a single homogeneous serial transmission media and protocol be employed throughout the entire system. Secondly, they are generally switching systems designed to switch high bandwidth serial transfers without regard for latency. They attack only half the problem in that they provide parallel data communication, but they do not provide for parallel path set-up through the switch. Therefore, they do not provide a full parallel network capability. Instead, all network paths share a central matrix controller function that operates in serial. If a processing node wishes to use a path through the switch, it must first arbitrate for the facilities of the central matrix controller. The matrix controller services one request at a time, causing parallel requests to wait their turn. The central matrix controller acknowledges one switch set-up request at a time. It receives a short message indicating the switch connection desired. The central matrix controller checks a matrix map stored in the central matrix controller's memory and determines whether the requested connection can be established or not. If it can, the central matrix controller sends a command to the switching element (usually referred to as the switch fabric) to make the requested connection. Then the central matrix controller responds to the requesting node telling it whether the desired connection has been made or is not available. The processing node then uses the established connection and transmits data to or from the desired destination through the switch fabric, while the central matrix controller works on establishing the next serial connection. The processing node must go through a similar procedure to break the switch fabric connection using the central matrix controller, when it is finished using a given switch path. Thus, the latency of the central matrix controller approach in regards to establishing and breaking switch paths is very poor. In existing products, this type of approach has been adequate to connect DASD's, Direct Access Storage Devices and disk files, and other I/O devices to computer complexes, or to send batch information between processors. These types of applications transfer long disc records or large batch data at a high bandwidth. The poor latency is amortized over the large transfer and has a small effect on the overall performance. However, this is not the case for the modern "farm" approach, where messages can be short and latency becomes as important, if not more so, as bandwidth. As noted by Harold S. Stone in his book "High-Performance Computer Architecture" (Addison-Wesley 1990, pg. 309) that the performance benefits of parallel processing depends strongly on the ratio R/C, where R is the run-time of the processing (the computational work to be done) and C is the communication overhead required amongst n parallel processors jointly working on the job. The value C includes latency as well as bandwidth, and to keep C small and make parallel processing efficient, the switch latency must also be kept small.
Thirdly, another drawback of the central matrix controller switching approach is the limited number of processors that a single central controller can manage. Systems have been built to interconnect 8, 16, 32, and possibly as many as 64
processors, but that appears to be approaching the the limit of the concept. The central matrix controller approach also has a reliability problem in that a failure in the central controller can fail the entire communication system and render the whole parallel system useless.
I have solved some of the problems encountered in the prior art which I referred to above. A distributed switch controller approach, rather than a centralized approach, appears to be a better solution for parallel processing because of its inherent low latency, its ability to withstand failures, and its ability to expand to interconnecting massively parallel systems. The distributed and fully parallel switch utilized herein to solve the "farm" interconnect problem efficiently is an elaboration of the ALLNODE Switch (Asynchronous, Low Latency, inter-NODE switch), which is disclosed in U.S. Ser. No. 07/677,543 and adapted by the present invention to perform the switching of serial data lines at low latency and high bandwidths. The ALLNODE switch provides a circuit switching capability at high bandwidths similar to the switch fabric in the central matrix controlled switches; however, the ALLNODE switch includes distributed switch path connection set-up and tear-down controls individually within each switch--thus providing parallel set-up, low latency, and elimination of central point failures. We will further describe in the detailed description a way whereby the ALLNODE switch and the present invention can be used to solve the "farm" problem effectively.
DETAILED DESCRIPTION OF THE SWITCHING NETWORK AND APPLICATIONS
Turning now to the drawings in greater detail, as illustrated by FIG. 1, showing the preferred method of interconnecting N nodes via serial data channels connected to a parallel multi-stage switching network. Each node 1 of a parallel system can be comprised of a workstation, personal computer. mainframe CPU, or any I/O device, such as a DASD. A typical node 1A connects to the parallel network over the standard (e.g. IEEE Fiber Channel Standard FCS) or proprietary (e.g. IBM ESCON or Serial Link Adapter) serial data channel 40A that is normally provided with that particular node; i.e., no unique hardware is required at node 1. Each serial data channel uniquely connects one node to one MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER (MMSA); for instance, serial data channel 40A connects node 1A to MMSA 20A. In turn, each MMSA uniquely connects one serial data channel to one parallel switch port; for instance, MMSA 20A connects serial data channel 40A to parallel switch port interface 46A.
The preferred embodiment uses only unidirectional interfaces, and therefore FIG. 1 shows serial data channels 40A to be comprised of two unidirectional lines, one carrying data from node 1A to MMSA 20A, and one carrying data from MMSA 20A to node
1A. Likewise, the parallel switch interface 46A is comprised of two unidirectional sets of signal lines, one carrying data from MMSA 20A to switch network 30, and one carrying data from the switch network 30 to MMSA 20A. To be consistent with the unidirectional concept, MMSA 20A internally has two sections--one which receives serial data from interface 40A, converts the data to parallel; and sends it to switch interface 46A; and one which receives parallel data from switch interface 46A, converts the data to the designated serial protocol, and sends it to interface 40A.
Referring to FIG. 1, it is possible for any node to send data to any other node through switch network 30. For example, node 1A could send a message using serial data channel 40A to MMSA 20A. MMSA 20A converts the serial message protocol to a parallel message protocol and sends it to switch interface 46A. MMSA 20A receives destination identification data (DID) as part of the serial data message, which it uses to command the switch network 30 to make the connection to the requested destination node (node 1N in our example). Switch network 30 forms the requested connection and parallel data flows from MMSA 20A through network 30 to MMSA 20N. MMSA 20N receives the parallel message protocol over switch interface 46N. MMSA 20N converts the parallel message protocol to the designated serial message protocol and sends it to node 1N over serial channel 40N. Node 1A sends its own node number, referred to as source identification data (SID), as part of the message, so that node 1N can respond to the message if it so desires. To do this, node 1N constructs a response message using the SID of the message it received as the DID of the response message it generates. Node 1N sends the response message over serial data channel 40N to MMSA 20N. MMSA 20N converts the serial message protocol to a parallel message protocol and sends it to switch interface 46N. MMSA 20N uses the DID it receives to command the switch network 30 to make the connection to the requested destination node (node 1A in our example). Switch network 30 forms the requested connection and parallel data flows from MMSA 20N through network 30 to MMSA 20A. MMSA 20A receives the parallel message over switch interface 46A. MMSA 20A converts the parallel message protocol to the designated serial message protocol and sends it to node 1A over serial channel 40A. In similar fashion any node can communicate with any other node.
Referring to FIG. 2, the flexibility of the MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER 20 (MMSA) and the switch network 30 design is demonstrated. The flexibility allows the present invention to support a nodal system comprised of various types of interfaces. The MMSA can be personalized to support the any one of a number of standard and proprietary serial protocols. A personalization PROM is part of the MMSA, which is used to specificity the particular serial protocol that each individual adapter is to support. For instance, MMSA 20A is shown to be personalized to support the Fiber Channel Standard protocol, whereas MMSA 20C is personalized to support the RS-232 electrical protocol and MMSA 20N is personalized to support a proprietary serial fiber protocol. Thus, it is possible to use the parallel switching network as a multi-media device that interconnects and allows different serial protocols to communicate with each other; i.e., any number of different serial protocols can interface with the same parallel switch network 30. This allows every node of the parallel system to send and receive messages using its own unique protocol. However, a node is not restricted to communicating only with others nodes having the same protocol, but it can communicate with any of the other nodes regardless of the serial protocol they use. For example, node 1 could send a message over serial data channel 40A to MMSA 20A using the Fiber Channel Serial protocol at a 1 gigabit per second (GbS) rate. MMSA 20A is personalized to convert the message received in the Fiber Channel Standard protocol to a message having the same meaning in parallel switch protocol. MMSA 20A makes the conversion and sends the message to switch interface 46A including the DID switch routing information. After switch network 30 forms the connection indicated by the DID, parallel data flows from MMSA 20A through network 30 to MMSA 20C. MMSA 20C receives the parallel message over switch interface 46C. MMSA
20C is personalized to convert the message received in the parallel switch protocol to a message having the same meaning in the RS-232 serial electrical protocol. MMSA 20C makes the conversion and sends the message at a 1 mega bits per second (Mbs) rate to node 3 over serial channel 48. In similar fashion any node can communicate with any other node using different protocols. A node sending a serial message transmits the message in its native protocol over fiber or copper wire to its associated MMSA, which is personalized by the PROM to understand the protocol generated by that node.
An additional flexibility is shown in FIG. 2. It is possible to intermix transfers to or from nodes which implement the parallel switch interface directly. For instance, node 2 is shown to connect directly to switch network 30 and to provide the parallel switch interface 46B directly, without requiring the serial to parallel protocol conversion functions. Thus, the direct connect interface 46B does not require the services of the MMSA. Node 2 can still communicate with all other nodes of the system. For instance, node 2 could send a message directly to switch network 30 over parallel channel 46B at a 40 megabytes per second (MBS) rate and specify node N as the destination of the message. After switch network 30 forms the connection indicated to node N, parallel data flows from node 2 through network 30 to MMSA 20N. MMSA 20N receives the parallel message over switch interface 46N. MMSA 20N is personalized to convert the message received in the parallel switch protocol to a message having the same meaning in a proprietary serial protocol.
MMSA 20N makes the conversion and sends the message at 200 MBS to node N over serial channel 49. In similar fashion any node can communicate to or from node 2. In the case where the node supports the switch interface 46B directly, the conversion provided by the MULTI-MEDIA SERIAL LINE SWITCHING ADAPTER is not required because the message already exists in the appropriate protocol as it either comes directly from a sending node or goes directly to a receiving node.
A further flexibility is shown in FIG. 2. Block 4 illustrates that any node of the system, such as node 4, can serve as a bridge to another network, whereby networks of the same type as network 30 (ALLNODE Switch Networks) can be interconnected to each other through network bridge nodes, like node 4. It is also possible to interconnection to network 30, other networks which are of a different type than network 30, such as telephone networks, wireless networks, or other types of multi-stage or crossbar networks through network bridge nodes, like node 4. FIG. 2 shows that bridge nodes, like node 4, can be connected to network 30 by either a serial protocol that goes through MMSA block 20D, or by a parallel protocol that would by pass block 20D in the manner shown by parallel interface 46B.
Referring to FIG. 3, the application of the combined function provided by MMSA adapters 20 and the ALLNODE switch network 30 is shown as a means of interconnecting "farms" of various architectures. The "farm" system is is interconnected by an improved adaptation over a minimal serial fiber or copper wire transmission media to parallel switching networks for the purpose of interconnecting large numbers of processors. The processors can be interconnected to form a shared processing resource--a "farm" of processors--to provide either massive joint computational power for a single task or individual processors assignable to individual tasks. Some of the various "farm" members are shown in FIG. 3 by blocks 100 to 107. Any workstation, personal computer, mainframe, or I/O device can be a node of the "farm" system. All the nodes can be of the same type; for instance, a 100 node "farm" could have blocks 107 at all 100 nodes and interconnection would be provided by block 20&30. However, it is not necessary to have the same block 107 at every node. A system, like the one shown in FIG. 3, having a different processor at every node will work equally well. The limit on the number of nodes that can be interconnect through block 20&30 is restricted by the expansion capability of network 30. There is presently no known limit that would keep the ALLNODE Switch network 30 from expanding to as many as 32,000 nodes.
Referring to FIG. 4, the difference is shown between the present parallel switch interconnection apparatus and the state-of-the-art matrix controlled switches, which do not effectively meet the requirements of modern parallel systems. The matrix switch shown in FIG. 4 attacks only half the problem in that it provides parallel data communication through switch fabric 36 which can support the interconnection of many processors (90A to 90N) simultaneously, but set-up and breakdown of the connections in switch fabric 36 is accomplished serially (not in parallel) through the serial matrix controller 35. All network paths share a central matrix controller function that operates in serial. If processor node 90A wishes to communicate to processor node 90N using a path through the switch fabric 36, processor node 90A must first arbitrate for the facilities of the serial matrix controller 35. The central matrix controller 35 services only one request at a time, causing simultaneous requests to wait their turn. The central matrix controller 35 acknowledges one switch set-up request at a time. It receives a short message from processor node 90A after processor 90A has won the arbitration for the matrix controller 35, the short message indicating the switch connection desired to processor 90N. The central matrix controller 35 checks a matrix map stored in the central matrix controller's memory and determines whether the requested connection can be established or not. If it can, the central matrix controller 35 sends a command to the switch fabric 36 commanding it to make the requested connection. Then, the central matrix controller 35 responds to the requesting processor 90A telling it whether the desired connection has been made or is not available. The processing node 90A then uses the established connection and transmits data to or from the destination processor 90N through the switch fabric 36, while the central matrix controller 35 works on establishing the next serial connection. The processing node 90A must go through a similar procedure to break the switch fabric 36 connection using the central matrix controller 35, when it is finished using a given switch path. Thus, the latency of the matrix switch approach in regards to establishing and breaking switch paths is very poor. Numbers quoted for the latency of existing matrix switch products usually are in the range of 10 to 100 microseconds. However, modern parallel processing systems require latencies in the sub-microsecond range to be efficient.
In contrast, the present invention applies to low latency fully parallel switch networks, also shown in FIG. 4. In this type of network there is no shared matrix controller, but the switch fabric and path set-up and breakdown control is provided by the same block 30. The parallel switch 30 provides parallel data communication, identical to the matrix switch, which can support the interconnection of many processors (90A to 90N) simultaneously. However, the set-up and breakdown of connections is accomplished in parallel quickly through the same parallel switch 30 function. For example, N/2 of the processor nodes 90A to 90N could simultaneously request connections be established through parallel switch 30 and they would all be processed immediately and simultaneously. Thus, the latency of a comparable parallel switch would usually be in the range of 100 ns or less, and N/2 connections can be processed simultaneously giving an effective maximum rate of one set-up every 200/N ns. This yields a 3 to 4 order of magnitude improvement in latency of the parallel switch over the matrix switch.
The distributed and fully parallel switch utilized in the preferred embodiment of the present invention the ALLNODE Switch (Asynchronous, Low Latency, inter-NODE switch), which is disclosed in U.S. Ser. No. 07/677,543 and adapted by the present invention to perform the switching of serial data lines at low latency and high bandwidths. The ALLNODE switch provides a circuit switching capability at high bandwidths similar to the switch fabric in the central matrix controlled switches; however, the ALLNODE switch includes distributed switch path connection set-up and tear-down controls individually within each switch--thus providing parallel set-up, low latency, and elimination of central point failures.
It is here understood that the FIGS. 5 to 11 are illustrations which are common to U.S. Ser. No. 07/677,543, the parent application which is incorporated herein by reference as to all of its contents. FIGS. 5 to 11 refer to a 4.times.4
crossbar implementation of the ALLNODE Switch to illustrate the principles and speed of the switching concept.
As illustrated by FIG. 5 the ALLNODE switching apparatus would be provided for a node having a plurality of input and output ports, and would comprise the connection control circuit for each input port, and a multiplexer control circuit for each output port for connecting any of I inputs to any of Z outputs, where I and Z can assume any unique value greater or equal to two, as in the parent application.
FIG. 5 shows a 4.times.4 crossbar ALLNODE switching apparatus, where the function is to provide a means of connecting any of four input ports on a mutually exclusive basis to any one of the unused four output ports on a priority basis. The
4.times.4 crossbar ALLNODE switching apparatus can support up to four simultaneous connections at any given time. For instance, Input 1 could be connected to Output 3, Input 2 to Output 4, Input 3 to Output 2, and Input 4 to Output 1.
The ALLNODE switching apparatus 10 is unidirectional, which means that data flows in only one direction across the said switching apparatus 10, that being from input to output. Although the said switch apparatus 10 is unidirectional, it supports bidirectional communication amongst four nodes (20, 22, 24, and 26) by connecting the 4.times.4 ALL-NODE switching apparatus 10 as shown in FIG. 5. Each node 20, 22, 24, and 26 has two sets of unidirectional interconnecting wires, one going to the switch 10 and one coming from the switch 10. The dashed lines internal to the switching apparatus 10 indicate that the function of the said switching apparatus is to connect an input port such as INPUT PORT 1 to one of four possible output ports. The switching apparatus 10 provides exactly the same function for each input port, allowing it to be connected to any unused output port.
Referring thus to FIG. 6, block 12 shows an expanded drawing of switching apparatus 10 and defines in detail the interlace lines connecting to switching apparatus 10. The set of lines 31, 32, 33, and 34 at each in-port to the switching apparatus
12 are identical in number and function to the set of lines 41, 42, 43, and 44 at each out-port. The sets of interlace lines to each input and output port contain eight unique signals: four data lines and four control lines (VALID, REJECT, ACCEPT, and BRDCAST) which are differentiated by a prefix of INX- or OUTX- indicating the direction and number of the port (X) that they are associated with. The four data and VALID and HI PRI lines have a signal flow in the direction going from input to output across switching apparatus 12, while the REJECT and ACCEPT control lines have a signal flow in the opposite direction.
The sets of input port interlace lines 31, 32, 33, and 34 transfer control information to switching apparatus 12 for the purpose of commanding and establishing input port to output port connections internal to the said switching apparatus. In addition, the said port interlace lines also carry data information to be transferred from input port to output port across the switching apparatus 12. The four data interlace lines contained in interfaces 31, 32, 33, and 34 do not restrict the transfer of data across switching apparatus 12 to only four bits of information, but rather the said four data lines can each contain a string of serial data making the transmission of any size data possible. For example, the said four data lines could transfer data at a 160 Mbits/sec rate, if all four data lines were transmitting serial data at a 40 MHZ rate.
The Switch Interface requires only 8 signals, as shown in FIG. 6, to transmit and control dual priority data through the network--the data transfer width is 1/2 byte (4 bits) at a time. The signals required are:
DATA: 4 parallel signals used to command switch connections and transmit data messages.
VALID: When active, indicates that a message is in the process of being transmitted. When inactive, indicates a RESET command and causes all switches to reset to the IDLE state. All switch functions are reset, except the high priority latches.
BRDCAST: When active, indicates the message in process is to be broadcast (sent in parallel) to all nodes, or that the present switch connection is to be held and maintained, even when the VALID line goes inactive.
REJECT: Signal flow is in the opposite direction from the other 6 signals. When active, it indicates that a REJECT or error condition has been detected.
ACCEPT: Signal flow is in the same direction as the REJECT signal and opposite to that of the other 6 signals. When in the low state, it indicates that a message is in the process of being received and checked for accuracy. When active, it indicates the message has been received correctly.
Referring to FIG. 7, a method is illustrated for increasing the number of nodes in a system by cascading eight switching apparatus 10 blocks. The eight cascaded switches are denoted as 10A through 10H to indicate that they are identical copies of switching apparatus 10, varying only in regards to the wiring of their input and output ports. It can be noted that any of sixteen nodes can communicate to any other node over a connection that passes through exactly two of the switching apparatus 10
blocks. For instance, Node 5 can send messages to Node 15 by traversing switch 10B and switch 10H. Since all connections are made through two switching apparatus 10 blocks, the network comprised of the eight switching apparatus 10 blocks is referred to as a two stage switching network. Other multi-stage networks can be configured from switching apparatus 10 blocks by using three stages, four stages, etc. in a similar manner.
Referring to FIG. 8, a functional diagram of the simple data flow across ALLNODE switching apparatus 10 is illustrated. The BRDCAST, VALID and four data lines at each input port, inside the switch, and at each output port are represented by a single line in FIG. 8 for simplicity. For instance, the BRDCAST, VALID, and four data lines entering broadcast/switch 10 at IN PORT 1 go to five internal functional blocks of broadcast/switching apparatus 10; these are blocks 50A, 60A, 60B, 60C, and
60D. Block 50A makes the decision as to which of the four possible output ports are to be connected to input port 1. The BRDCAST, VALID, and four data lines from each input port go to each output multiplexer block (60A, 60B, 60C, and 60D); this makes it possible to connect any input port to any output port. Each of the four output multiplexer blocks (60A, 60B, 60C, and 60D) is uniquely commanded from each of the control blocks (50A, 50B, 50C, and 50D) as to which of the four possible sets of input port lines is to be gated through to each output port. For instance, control block 50A can command multiplexer 60C to connect input port 1 to output port 3; control block 50B can command multiplexer 60A to connect input port 2 to output port 1; and control block 50C can command multiplexers 60B and 60D to connect input port 3 in a multi-cast fashion to output port 2 and output port 4. All three connections are capable of being established simultaneously or at different times. At the same time that multiplexers 60A to 60D form connections to move the BRDCAST, VALID, and data signals across switch 10 with a unidirectional signal flow from input port to output port, multiplexer 61D and AND gate 63D form signal connections for the REJECT and ACCEPT signals, respectively, with a signal flow in the opposite direction of output port to input port (typical implementations are shown by blocks 61D and 63D--similar blocks are associated with each input port). These REJECT and ACCEPT signals provide a positive feedback indication to switch 10 of actions taken either by subsequent switch 10 stages in a cascaded network or by the device receiving and interpreting the BRDCAST, VALID, and four data signals. A command or message being transmitted through switching apparatus 10 over the four data signals under control of the VALID signal can be REJECTed by any network stage if it is unable to establish the commanded connection or by the receiving device if it is not capable of receiving the message at this time or if it detects an error in the transmission. The receiving device also has the capability of confirming the correct arrival of a command or message (without errors being detected) by pulsing the ACCEPT signal. Since the REJECT and ACCEPT signals go in the opposite direction from the data flow, they provide a means of reporting back a positive indication to the sender on whether the attempted transmission was received correctly or rejected.
Referring to FIG. 9, blocks 56, 52, and 54 illustrate a typical method for generating multi-line (parallel)/serial data in the form of a message which can be transmitted to and across switching apparatus 14, which is a partial drawing of the switching apparatus 12. Similar parallel/serial data generation logic as provided by 56, 52, and 54 can be used at each of the other input ports to switching apparatus 12. Each set of input data lines provides 4 serial data lines to a given input port which is synchronized to the same clock by the four shift registers 54 which create the parallel/serial data by shifting four synchronized lines of data 31 as controlled by the same identical clocking signal (100 MHZ in FIG. 9). However, the four different input port sources (31, 32, 33, and 34) to switching apparatus 14 can be asynchronous to each other, being based on different, non-synchronized, 100 MHZ clocking signals.
The process for sending parallel/serial messages through switching apparatus 14 involves FIFO 56, which accumulates data messages to be transmitted. The next entire message to be transmitted is moved to buffer 52. The message stored in buffer
52 is moved to shift registers 54 in preparation for transmittal and the data is dispersed across the four shift registers 54 by placing data bit 0 into the first bit of shift register 1, data bit 1 into the first bit of shift register 2, data bit 2 into the first bit of shift register 3, data bit 3 into the first bit of shift register 4, data bit 4 into the second bit of shift register 1, etc. Shift registers 54 then begin to send serial data to switching apparatus 14 over four synchronized data lines, in such a manner that the parallel/serial data flows continuously until the entire message has been transmitted. The switch apparatus 14 uses the first eight bits transmitted (in the first two clock cycles of serial data over interface 31 from serial registers 54 to switching apparatus 14) to select and establish a connection path through the switching apparatus 14. The example in FIG. 9 illustrates via dashed lines, the switching apparatus establishing a temporary connection between input port 1
(31) and output port 2 (42), such that each of the eight individual lines in interface 31 are uniquely and directly connected to each of the corresponding lines in interface 42.
Referring to FIG. 10, typical serial waveforms are shown for both input and output ports of the switching apparatus 14. The switch removes the first 8 bits of the serial transmission as sent by shift registers 54 and uses them to make and hold a connection, such as interface 31 to interface 42. The remainder of the serial message in our example is transferred directly from interface 31 to interface 42, so that interface 42 sees that exact same message that interface 31 receives, minus the first
8 bits and delayed by the circuit delays encountered by the serial data as it traverses the switching apparatus 14. Switching apparatus 14 does not buffer or re-clock the serial data entering via interface 31 in any manner: it merely reflects as quickly as possible the input waveforms it receives over interface 31 to output interface 42 without changing them in any way, except to strip off the first 8 bits.
The convention for indicating to a switch 14 input port over an interface (such as 31) that there is no transfer in progress, is to issue continuous IDLE commands, which are denoted by the 4 data lines and the VALID control line being held at logical 0's. The detection of a logical 1 on any of the input lines will signify the departure from the IDLE state and signify to the switch that a selection and transfer is beginning. Likewise, the output lines from the switch will be held in the IDLE state (at all 0's), when there is no active transfer in progress.
In general, all switches require a path selection method, whereby they are commanded which connection (input port to output port) to establish. For switching apparatus 10, the path selection command is transmitted to the switch over the same interface that the data is transferred; i.e., the 4 data lines associated with each input port. Selection information must be transferred prior to the data, so that the commanded interconnections can be established and the data can then flow to the commanded destination. The selection information need NOT identify an input port number (1 to 4), because it is arriving at the switch over a specific input and the switch already knows what input number it is receiving data on. Therefore, the selection information need ONLY specify the number (1 to 4) of which one of the four output ports of switching apparatus 10 to which to connect. The method of path Selection recommended here is one out of N encoding with a return to zero (called a DEAD FIELD).
Referring to FIG. 11, a typical example of the exact serial bit patterns and control signal activation is shown for sending control and data information to switching apparatus 10. The example references the cascaded, two stage switching network shown in FIG. 7 and involves sending data across the network from node 1 through switching apparatus 10A and 10F to node 7. To make this connection, input port 1 must be connected to output port 2 of the first stage switching apparatus 10A, and input port 1 must be connected to output port 3 of the second stage switching apparatus 10F. The signal sequence that is sent to input port 1 to cause the desired connections in switching apparatus 10A and 10F is shown in FIG. 7. In the signal sequence of
1's and 0's, time advances from left to right, so that the values seen at clock time -2 arrive at switch 10A first, and the values at clock time -1 arrive second, etc. The values of the IN1-DATA and IN1-VALID lines are all zeroes and cause nothing to happen at switch 10A during times -2 and -1, because they indicate IDLE. At clock time 0, the IN1-VALID line goes to a logical 1. This prepares switch 10A by enabling the input port 1 to receive data, but no connection or action takes place at switch
10A at this time. The IN1-VALID control line basically enables the corresponding switch input port; when IN1-VALID is a logical 0, switch 10A cannot make any connections or receive any data from input port 1, which is held RESET. Finally, at clock time
1, switch 10A receives its command as to what output port to connect to; the command is received entirely during clock time 1.
The command bit pattern sent at clock time 1 is used by switch 10A to establish connection to an output port; this process is referred to as a path selection operation and takes place completely internal to switch 10A. The path selection approach implemented by the present ALL-NODE switch invention is to let each of the 4 IN1-DATA lines to define a unique output of switch 10A to be selected. For instance, IN1-DATA1 signal going to a logical 1 at time 1 tells switch 10A to connect to output port 1, IN1-DATA2 commands connection to output port 2, etc. In our example, since IN1-DATA2 goes to a logical 1 during clock time 1, switch 10A is thereby commanded to connect to output port 2. In other words, the connection algorithm is that the first data input line going to a logical 1 after an input port has been enabled, defines the connection which that input port is to make. This is a mutually exclusive process, in that for the normal case only one data line at clock time 1 is allowed to be a logical 1; the other 3 data lines must be 0's. Note that since 1 bit of selection information is guaranteed to be a logical 1, switch 10A will be able to recognize the start of a transmission without requiring any additional bits to signify that a transfer is commencing. The switch 10A makes the commanded connection by removing the 4 bits from the data lines and storing them in a selection register in control block 50A of FIG. 8. The bits transmitted during clock time 1 are not passed through switch 10A to switch 10F, but instead switch 10A begins passing the very next 4 bits of data corresponding to clock time 2 to the next switch 10F. However, the information bits following a selection command (those transmitted by the 4 data lines at clock time 2 in our example) must always be all zeroes (a DEAD FIELD) as shown in FIG. 11. The purpose of this will be explained subsequently.
At clock time 2, the connection of switch 10A input port 1 to output port 2 is established and causes the signal sequence at clock time 2 to be transmitted across switch 10A and the interconnecting wires to switch 10F input port 1. From this time on, switch 10A merely transmits all subsequent data immediately to switch 10F input port 1; it never examines or takes any action on any other data patterns presented to switch 10A over its input port 1 interface. It just passes all data patterns it receives over input port 1 immediately to the output port 2 and switch 10F. Thus, at clock time 2, assuming zero delay across switch 10A and its associated cable, switch 10F input port 1 sees the VALID signal rise and the all zeroes DEAD FIELD on the
4 data lines coming into switch 10F input port 1. In this way, at time 2, switch 10F input port 1 is enabled in an identical manner to the way switch 10A input port 1 was enabled previously at time 0.
In our example illustrated in FIG. 11, IN1-DATA3 goes to a logical 1 during clock time 3 and switch 10F is thereby commanded to connect its input port 1 to its output port 3, in a manner similar to the way switch 10A was commanded to connect its input port 1 to its output 2 during clock time 1. The switch 10F in making the commanded connection, removes the 4 bits at clock time 3 from the data lines, and stores them in the selection register which is part of control block 50A of FIG. 8. The bits transmitted during clock time 3 are not passed through switch 10F to Node 7, but instead switch 10F begins passing the very next 4 bits of data corresponding to clock time 4 to Node 7. However, the information bits following a selection command (those transmitted by the 4 data lines at clock time 4 in our example) must always be all zeroes (a DEAD FIELD) as shown in FIG. 11. Thus, by clock time 4, switches 10A and 10F have established a connection path for transferring data directly from Node
1 to Node 7. Up to clock time 5, Node 7 sees nothing but IDLE commands. At time 4, Node 7 sees the OUT3-VALID line from switch 10F go active and is thereby enabled to start receiving data at time 5. From time 5 on, Node 7 can receive data from Node 1
over the 4 OUT3-DATA lines from switch 10F. The protocol of the actual data being transmitted can be any of the normal formats such as manchester encoded, 8/10 bit encoding with preamble, etc. However, the preferred embodiment, as shown in FIG. 11 is an all ones synchronization field at time 5, followed by the NRZ data message. The data message can specify the word count length of the transfer. The purpose of the Synchronization field of all ones as a prefix to the actual data message, is to enable the receiving node 7 to synchronize to the sending node 1 in one clock time. This assumes that the two nodes involved in the data transfer have clocking Systems that are asynchronous to each other, but are effectively operating at the same frequency.
The preferred embodiment is to transmit the word count length of the message first during clock time 6 and clock time 7. Node 7 then decrements the length count and can detect when the transfer is complete. Node 7 can then check the message for accuracy using the selected error detection method (parity, ECC, or CRC). If the message has been received correctly, Node 7 responds by activating the ACCEPT interface line back to switch 10F at clock times n+1 and n+2. Switch 10F passes the ACCEPT indication back to switch 10A, which in turn returns it immediately to Node 1. This indicates to Node 1 that the transfer completed successfully, and Node 1 resets its VALID and 4 data lines to switch 10A to zeroes, thus, completing the data transfer and returning to the IDLE state. The IN1-VALID input line to switch 10A going to a zero at time n+3, causes switch 10A input port 1 to break its connection to output port 2 and to return to the IDLE state. Immediately, switch 10F sees its IN1-VALID input line go to a zero, breaks its connection to output port 3 and returns to the IDLE state. Thus, the connections can be broken and the switches returned to IDLE in as little as one clock time. If Node 1 has another message to transmit, it can load the next message into buffer 52 and shift registers 54 (FIG. 9), and begin transmission to Node 7 or any other node as soon as time n+4. The only restriction is that the VALID signal generated by Node 1 must return to zero for a minimum of one clock time (time n+3) to signify the end of one transfer before beginning another.
If Node 7 finds an error in the message it has received after the word count has gone to zero at clock time n, it responds by activating the REJECT interface line (instead of ACCEPT) back to switch 10F. Switch 10F uses the incoming REJECT signal from Node 7 to break its connection to Node 7, to return to the IDLE state, and to pass the REJECT indication back to switch 10A, which in turn returns it immediately to Node 1 after breaking its connections and returning to IDLE. Node 1 then notes that the transfer has been rejected, and returns to the IDLE state by resetting its VALID and 4 data lines to switch 10A to zeroes. Node 1 may then retry the transmission by reloading shift registers 54 from buffer 52 and starting the transmission over again from the very beginning (clock time -1). The retransmission can occur over the identical path as the previously rejected transmission, or if alternate paths through the network are implemented another path can be tried. If continuous REJECTs are encountered, such that a specified number of REJECTs occur for the same message, an error reporting mechanism may be invoked.
It is also possible for any switch 10 in a network path to REJECT a message. This can occur for either of two cases:
1) BUSY--If the output port to which the switch is commanded to connect is BUSY (i.e., it is being used by a previously established connection), the switch will signify this condition to the input port issuing the command by activating the REJECT line back to the previous network stage or to the transmitter (if the first stage of the network detects BUSY). For instance, in the example shown in FIG. 11, if 10A had received a command at clock time -2 to connect input port 4 to output port 2, that connection would have been active when input port 1 requested to be connected to output port 2 at clock time 1. In this case, output port 2 is BUSY at clock time 1 and switch 10A would activate the IN1-REJECT line to Node 1. As described above, the transmitter may retry any REJECTed message.
Likewise, the connection could be made successfully at switch 10A, yet output port 3 of switch 10F could be BUSY at clock time 3, causing switch 10F to issue the REJECT signal to switch 10A. This, in turn, causes switch 10A to return REJECT immediately to Node 1 after breaking its connections and returning to IDLE.
2) Simultaneous CONTENTION--Rather than input port 4 establishing a connection to output port 2 in switch 10A at clock time -2 as described above (in advance of the same command from input port 1 at clock time 1), it is possible for two or more input ports to try to connect to the same output port at approximately the same time. This is called CONTENTION for an available output port. For instance, suppose input ports 1 and 4 both sent simultaneous commands at clock time 1 requesting to be connected to output port 2. The present invention resolves this contention by first connecting both contending input ports 1 and 4 to output port 2. The net effect is to electrically connect the 2 input ports to output port 2, which will logically OR the signals coming from both sources. During clock time 2 the logical OR of the 2 input ports will NOT cause an error, because the values present on both input ports 1 and 4 are identical: the VALID lines for each are logical 1's and the data lines for each contain the DEAD FIELD (logical 0's). However, at clock time 3, the signals from each source could be different and an error could be caused if the 2 input ports both remained connected at clock time 3 and later. In other words, switch 10A has 1
cycle time (clock time 2) to correct the decision it made to connect two or more inputs to the same output. Switch 10A makes this correction during clock time 2 by detecting the fact that more than one input is connected to a given output. It then takes action by resetting all but one of the multiple connections, and does this before clock time 3 occurs. The decision of which connection(s) to reset and which one to keep is a decision based on priority. For the preferred embodiment, a simple priority scheme is used as follows: If input port 1 is contending it gets the connection, If input port 1 is not contending and input port 2 is, input port 2 gets the connection. If input ports 1 and 2 are not contending and input port 3 is, input port
3 gets the connection. Input port 4 gets the connection only if no other input port wants it. Applying the priority selection to our example, input port 1 gets to keep its connection to output port 2, while the connection of input port 4 to output port
2 is reset during clock time 2. This results in the REJECT signal being issued in the normal fashion from switch 10A to input port 4.
Thus, the purpose of the DEAD FIELD in the present invention is to allow one clock time per switch stage to resolve simultaneous contention. The secondary purposes of the DEAD FIELD are to cause a falling edge on the selection bit which was active during the previous clock time, and to compensate for timing skew which might be present across the 4 data lines carrying serial selection data to the cascaded switches. Both the rise and fall of data bits commanding the switches to make connections gives the unclocked switch two clock edges (rise and fall) on which it can trigger and make decisions. These are the only two decision making times available to the ALL-NODE switch.
The present invention is comprised of two major portions as shown in FIG. 1, the serial adapter 20 and the switching apparatus 30. The preferred embodiment of the switching element comprising the switching apparatus 30 is shown in FIG. 12, which is an expanded 8.times.8 version of the 4.times.4 ALLNODE Switch 10. The 8.times.8 ALLNODE Switch 16 functions exactly the same as the 4.times.4 ALLNODE Switch 10, except that it implements byte wide (8 bit) data and has 8 input ports and 8 output ports. The input and output port interfaces are identical and are comprised of 8 data lines and 4 control lines each.
Referring to FIG. 13, the 8.times.8 ALLNODE switch 16 can be cascaded into two stages by interconnecting 16 ALLNODE switch 16 devices as shown, 8 devices per stage to provide full interconnection amongst 64 nodes. I have selected as a preferred embodiment 64 nodes because most algorithms which have needed parallel implementation would appear to be serviced adequately by 64 nodes, preferably RS/6000 type nodes. This number should not be considered limiting, as 512 or 32000 nodes can be made into a network with the device described. This 64 node network is the preferred embodiment for the present invention parallel switch network 30. All nodes are connected equidistantly, such that any node can send a message to any other node including itself by traversing 2 and only 2 stages of the network. The inputs to the switch network are shown on the left and the outputs from the switch network are shown on the right of FIG. 13. The 64 nodes attached to the network are numbered from 0 to 63. Each node has an input port of 12 lines to the network and receives an output port of 12 lines from the network, as shown by interface 46A in FIG. 1. The input and output to the network ports are named identically (such as "NODE 0"), because both interface to the same node, one interface coming from the node to the switch network 30 and one interface coming from switch network 30 to the node.
A message may be sent via switch network 30 from any node to any other node. The destination of each message is specified by a destination ID number indicating which node is to receive the message from the sending mode which assigns the message. The destination ID (DID) number is equal to the physical node number of the node attached to the network and is independent of the source of the message. For instance, any node 0 to 63 wishing to send a message to node 10, sends the message to DID=10. The DID is used to route the message to the correct path in the network, so that it arrives at the proper destination only (in this case, node 10). The DID is the binary representation of the destination node number segmented into two three-bit binary values to form the routing information for the network, with each three-bit value controlling one stage of the switch. The values occur in 3-bit groups because three bits are required to select one of the eight possible output ports at each 8.times.8
switch 16. For instance, for the two-stage network shown in FIG. 13, the six-bit binary representation for destination ID number 10 is (001,010), where the first 3 bits (001) indicate the output port that is to be selected in switch stage 1; and the second three bits indicate (010) the output port that is to be selected in switch stage 2. If, as an example, node 1 wishes to send a message to node 10, the output port selected in switch stage 1 would be the second output port down on the right hand side of the switch 16A (corresponding to the selection value for stage 1 (001)). Node 1 forms a connection through switch 16A to "LINE X" to the first input port of switch 16J. Next switch 16J is commanded to make the connection to its third output port via the second 3-bit binary value (010)--where node 10 is located. Thus, the connection from node 1 to node 10 is completed, based only on the binary representation of the destination DID number.
The present invention connects serial interfaces to switch network 30 interfaces. Turning now to the serial interfaces, many different serial protocols exist but they have many common aspects. Therefore, a typical serial interface will be described herein as the preferred embodiment of the serial protocol and used as an example of how any serial interface can be adapter to the switch network 30.
Most serial fiber protocol use a message frame to transfer data, where the frame proceeds the message data with a link header and define the end of the data message using a link trailer. ##STR1##
The link header and link trailer are each comprised of several entities as follows: ##STR2## SOF=Start of Frame Delimiter--Two to four 10-bit characters having fixed patterns which delineate the beginning of a message. Two different SOF patterns are used--connect and passive. The Connect-SOF causes a connection to be established in the network, passive assumes no connection is required, but that a previously formed connection has been held active. This field is assumed to be two characters in the preferred embodiment in the following sequence: first 001111 1001, second 001111 1000 to indicate Connect-SOF, and first 001111 1010, second 001111 1000 to indicate Passive-SOF.
EOF=End of Frame Delimiter--Two to four 10-bit characters having fixed patterns which delineate the end of a message. Two different EOF patterns are used--disconnect and passive. The Disconnect-EOF causes a connection to be broken in the network after the present message is transmitted, passive inhibits the breaking of the network connection, so that the previously formed connection is held active. EOF is also used to identify the preceding field as the CRC field. This field is assumed to be three characters in the preferred embodiment in the following sequence: first 001111 0110, second 001111 1001, third 001111 1001 to indicate Disconnect-EOF, and first 001111 0110, second 001111 0101, third 001111 1010 to indicate Passive-EOF.
The Abort-EOF is a special EOF sequence to indicate that the current message is to be discarded immediately. This field is assumed to be three characters in the preferred embodiment in the following sequence: first 001111 0110, second 001111
0010, third 001111 0010 to indicate Abort-EOF.
DID=Destination Identification (ID) field--Two to four 10-bit characters which specify the node which is to receive the Device Data Message or the Link Control Command. This field is assumed to be two bytes in the preferred embodiment, having the following meaning: ##STR3## SID=Source ID field--Two to four 10-bit characters which specify the node sending the message, so that responses can be directed to the appropriate node. This field is assumed to be two bytes in the preferred embodiment, having the following meaning: ##STR4## CRC=The Cyclic Redundancy Check Field--Two to four 10-bit characters which is used to check the integrity of all transmitted fields in the message except the SOF and EOF fields. The polynomial used for the transmission of CRC in the preferred embodiment is: ##STR5## which generates a two 10-bit character CRC field. CNTL=The Link Control field indicates the type of frame and other link control information. This field is assumed to be one byte in the preferred embodiment, having the following meaning: ##STR6##
Serial protocols usually support two basic types of messages--Link and Device Messages, where Link messages are directed to control the serial interface logic and the switch network, while Device messages are directed to other nodes in the system. A Link Control short message doesn't require any data message at all, ##STR7## whereas, a Link Control Long message or device message uses a data message portion of the frame. As shown here by the preferred embodiment of the Device and Link Control message. ##STR8##
Devices messages can request responses and/or acknowledgements, but these device protocols are part of the data field and are not considered here. The device protocols are merely transmitted by the present invention like any other part of the data field and not operated on in any manner by the present invention, just transferred from one node to another where the device protocols are acted upon by the processor at the receiving node.
Most fiber serial interface transmit continuous sequences in between serial messages to keep the media synchronized and immediately available when serial messages become available. The preferred serial interface embodiment assumes the following continuous sequences and the following responses from the end of the serial interface receiving the continuous sequence:
1. IDLE--Message frame transmission is allowed--Respond with IDLE or send message frame.
2. UD--Unconditional Disconnect--Respond with UDR sequence.
3. UDR--Unconditional Disconnect Response--Respond with IDLE.
4. NOS--Not Operational Sequence--Respond with OLS
5. OLS--Off Line Sequence--Respond with UD
Referring to FIG. 14, a block diagram of the MULTI-MEDIA SERIAL ADAPTER (MMSA) 20 is shown to interconnect 2 serial interface ports to two parallel/serial (referred to hereafter as parallel) switch ports. One serial interface port receives serial data either over fiber by Fiber Optic Receiver Module 126 or over copper wire by Serial to Parallel Receiver Module 128--whichever one is active. The serial data is received and the link header and trailer interpreted by block 140. Then, the data message is translated into a data message having the parallel switch protocol. The converted message is stored in the Switch Message Send Buffer 160 until it is received in full, then the Switch Message Send logic 180 reads the data message form buffer 160 and sends it over the parallel switch network 30 to the commanded destination based on the DID. If the data message in buffer 160 is a Link Control Message, it is routed to and processed by block 172, instead of being sent to the switch network 30. Block 180 implements a switch output port which sends byte wide data to the switch network, and becomes an input port to an ALLNODE Switch 16 in network 30. The corresponding output from the switch network 30 is connected to Switch Message Receive Logic 170, which acts as a switch input port from the network and receives data messages from the network 30. The message received from the network is stored as is in the Switch Message Receive Buffer 150 until it is received in full, then the Message Frame Transmitter and Protocol translator 130 reads the data message form buffer 150 and converts it to the serial data protocol, generates the link header, serializes the message, generates the link trailer, and transmits the entire frame either over fiber using Fiber Optic Transmitter Module 122 or over copper wire using the Serial to Parallel Transmitter Module 120--whichever one is active. In addition, the MMSA 20 function controls the detection and generation of continuous sequences over the serial fiber interfaces using block 132, and generates the necessary clocks required by the MMSA 20 using block 124.
With respect to FIG. 14, it will be seen how Block 172 as part of the Link Control function provided by block 172 allows for the monitoring of network parameters and activity.
Referring to FIG. 15, a more detailed drawing of Fiber Optical Transmitter Module 122 is shown. The module receives byte wide parallel input data into block 125, which converts the data to bit serial and transmits the data over fiber using optical driver 123 and either LED or laser diodes 121. Fiber Optical Receiver Module 126 is shown to receive bit serial data from the fiber interface into pin diode and preamp 127 and post amplifier 129. The serial data is then recovered and converted to byte parallel data in block 131. Modules 122 and 126 meeting the requirements described are not unique, and IBM with ESCON or other series and manufacturers have such devices for sale. For instance, AT&T sells an ODL 200 fiber optic LED and photodiode sender receiver, and also have a laser transceiver which encompasses both a sender and receiver, it is understood.
Referring to FIG. 16, a more detailed drawing of the Continuous Sequence and Generation block 132 from FIG. 14 is shown, which is shown to contain 8 registers 141 to 148 which are initially loaded from PROM Serial Format Controller 134. The PROM
134 is uniquely programmed for every different serial protocol supported by MMSA 20 and upon detecting power-on conditions, the contents of PROM 134 are loaded into registers, like 141 to 148, to control the subsequent operation of the MMSA 20 in a unique manner to conform to the selected serial protocol. Registers 141 to 145 each define the bit pattern that block 132 is to recognize for each of the standard continuous sequences--IDLE, UD, UDR, NOS, and OLS, respectively. In addition, registers
146 to 148 provide the capability to recognize 3 non-standard sequences to give added flexibility to block 132. Register 146 defines a unique continuous sequence that is non-standard, but can still be programmed to be recognized. Register 147 defines the continuous sequence which is generated in response to the unique UNQ sequence, and Register 148 defines the continuous sequence which is generated in response to the unique register UNQR sequence. Control block 169 is also loaded from PROM 134 and defines for each serial protocol which continuous response is to be generated for each incoming continuous sequence detected. The incoming fiber is continuously monitored to determine if a continuous sequence or a valid message is being received. The serial bit stream is received into module 126 and converted to 10-bit parallel data which is stored in register 152. Register 152 then sends sequences of consecutive bytes as they are received to comparators 161 to 168, where each comparator individually checks the incoming data to see if it compares to any one of the values programmed into registers 141 to 148, respectively. On a mutually exclusive basis, one continuous sequence of the 8 possible sequences will be recognized by one of the comparators 161 to 168, which will inform the Continuous Sequence Control block 154 of the detection of a match condition. Block 154 will then refer to Controls block 169 to determine what response it should issue to the detected continuous sequence. Block 154 will respond by controlling multiplexer 156 to select the proper response sequence and send it to block 158, where the data is converted to byte parallel, and sent to block 120 where is is serialized and transmitted in response over the fiber interface. Block 154 also controls the inserting of valid messages into the continuous sequence stream. Block 154 receives the Frame Transmit Request from the Message Frame Protocol Transmitter block 130 of FIG. 14, when block 130 has a valid message ready for transmission. At the appropriate instant, after the transmission of a complete IDLE sequence, block 154 responds to block 130 with the Frame Transmit Enable signal, which defines the interval when block 130 can use register 158 and transmitter module 122 to transmit a valid message. Synchronized with the completion of the valid message by the transmission of the link trailer, block 130 drops the Frame Transmit Request signal, which causes block 154 to drop the Frame Transmit Enable signal and to then return to transmitting continuous IDLE sequences.
Referring to FIG. 17, a more detailed drawing of the Frame Interpreter and Protocol-to-Protocol Translator block 140 from FIG. 14 is shown, which is shown to contain 5 registers 210 to 214 which are initially loaded from PROM Serial Format Controller 134. The PROM 134 is uniquely programmed for every serial protocol supported by MMSA 20 and upon detecting power-on conditions, the contents of PROM 134 are loaded into registers, like 210 to 214, to control the subsequent operation of MMSA
20 in a unique manner to conform to the selected serial protocol. Register 212 defines the bit pattern for each byte in the SOF portion of the link header plus the number of bytes in the SOF. This not only allows the SOF bit patterns to be programmable, but it also controls the size of the SOF field. The incoming fiber is continuously monitored to determine if a continuous sequence or a valid message is being received. The serial bit stream is received into module 126 or 128 and converted to 10-bit parallel data which is stored in register 153. Register 153 looks for valid messages by examining every 10-bits arriving to check for the SOF sequence. Register 153 sends all incoming sequences to comparator 216 to check for an incoming pattern match against the SOF Definition Register 212.
Referring to FIG. 19, more specific details of the SOF checking logic is shown. The SOF Definition Register 212 is shown in more detail by block 260. Register 260 is organized in 11-bit sections--an Enable bit plus a 10-bit SOF pattern. The
11-bit values from Register 260 are multiplexed to form one 11-bit value at a time by MUX 262. 10 bits from MUX 262 are fed to comparator 270 to perform a compare against every incoming 10-bit pattern (coming through receiver module 126 to register
153). If the incoming 10-bits compare identically to the first SOF pattern and the first Enable bit is set as detected by gate 271, latch 272 is set to record that SOF Match 1 has occurred. MUX 262 steps to select the second 10-bit pattern from register 260 and compares that pattern to the next arriving 10-bit pattern from register 153. If the second 10-bit compare is successful and the second Enable bit is set as detected by gate 273, latch 274 is set to record that SOF Match 2 has occurred. MUX 262 steps to select the third 10-bit pattern from register 260 and compares that pattern to the next arriving 10-bit pattern from register 153. If the third 10-bit compare is successful and the third Enable bit is set as detected by gate 275, latch
276 is set to record that SOF Match 3 has occurred. MUX 262 steps to select the fourth 10-bit pattern from register 260 and compares that pattern to the next arriving 10-bit pattern from register 153. If the fourth 10-bit compare is successful and the fourth Enable bit is set as detected by gate 277, latch 278 is set to record that SOF Match 4 has occurred. This selection process could continue to perform further 10-bit compares; however, the preferred embodiment only proceeds through four compares and the preferred serial protocol only requires 2 compares to detect SOF. If all four 10-bit compares match, as detected by gate 283, then the output of OR gate 286 goes active indicating that a complete 4 value SOF sequence has been recognized and the start of a frame (SOF) containing a valid message is detected. The flexible SOF detection logic works equally well for SOF fields containing 1, 2 or 3 10-bit characters. For instance, if the SOF was defined to be only a one 10-bit character sequence, the second Enable bit in register 260 would be programmed to be a 0. This would cause the input to inverter 268 to go to a 0 after latch 272 was set to indicate the first 10-bit match. This would cause the inverter 268 to go to a one and enable gate
280 after the first match and subsequently cause the output of OR gate 286 to go active indicating that a 1 value SOF sequence has been recognized and the start of a frame (SOF) containing a valid message has been detected. If SOF was defined to be a two 10-bit character sequence, the third Enable bit in register 260 would be