Modular crossbar interconnection metwork for data transactions between system units in a multi-processor system

We claim:

1. In a multi-processing system of the kind having a system control unit (SCU) for operating a plurality of system units in a parallel fashion, said system units including a plurality of central processing units (CPUs), at least one input/output (I/O) unit and at least one main memory unit (MMU), interconnection means for establishing communication paths for data transactions between system units designated by communication commands as source and destination nodes, said interconnection means comprising:

at least two crossbar modules, each module adapted to establish a direct path or mapping between one of a fixed number of source nodes and one of the same fixed number of destination nodes defined thereupon, the source and destination nodes provided on one crossbar module corresponding to different ones of said system units than those provided on other crossbar modules,

each of said modules including at least one expansion source node and at least one corresponding expansion destination node through which the crossbar modules are connectable in such a way as to establish a data path between source nodes defined on one of said crossbar modules and destination nodes defined on another of said crossbar modules,

wherein said interconnection means further comprises:

means for accepting control commands designating the source and destination nodes for executing a data transaction,

means for determining whether the designated source and destination nodes are defined on a single crossbar module or are defined on separate crossbar modules,

means for generating a control signal to said single crossbar module containing both the source and destination nodes in order to establish the required data path by a direct mapping between said nodes, and

means for generating separate control signals to each of said crossbar modules on which the source and destination nodes are separately defined in order to establish the required data path by an indirect mapping between said nodes, said indirect mapping being established by (i) a first sub-mapping between the designated source node and the expansion node of the crossbar module containing said source node and (ii) a second sub-mapping between the designated destination node and the expansion node of the crossbar module containing said destination node.

2. The multi-processing system of claim 1 wherein said interconnection means further includes means for generating, for a selected time period, a busy signal indicating that the source node, the destination node, and the expansion nodes being used at a given time for establishing a data transaction path are unavailable for establishing other transaction paths.

3. The multi-processing system of claim 2 wherein the control commands accepted by the interconnection means include a size command defining a period of time for which the required transaction path needs to be established, and wherein said means provided within said interconnection means for generating said busy signal generates said signal for predefined periods of time for certain predefined data transactions, and for other data transactions generates the busy signal on the basis of said size commands.

4. The multi-processing system of claim 1 wherein the system comprises four CPUs, two MMUs, two I/O units, and one service processor unit (SPU), and wherein the interconnection means comprises two crossbar modules, each crossbar module being adapted to provide interconnections between up to five source and destination nodes, respectively corresponding to two CPUs, one I/O unit, one MMU, and one SPU.

5. A multi-processing computer system comprising:

a plurality of system units, said system units including a plurality of central processing units (CPUs), at least one input/.output (I/O) unit, and at least one main memory unit (MMU); and

interconnection means for establishing communication paths for data transactions between system units designated by communication commands as source and destination nodes, said interconnection means including:

at least two crossbar modules; each module including means for establishing a direct path between one of a fixed number of source nodes and one of the same fixed number of destination nodes defined thereupon, and at least one expansion source node and at least one corresponding expansion destination node, the expansion source and expansion destination nodes of one crossbar module being connected to the expansion destination and expansion source nodes, respectively, of the other module for enabling a data path to be established between source nodes defined on one crossbar module and destination nodes defined on the other crossbar module;

means for accepting control commands designating the source and destination nodes for executing a data transaction,

means for determining whether the designated source and destination nodes are defined on a single crossbar module or are defined on separate crossbar modules,

means for generating a control signal to said single crossbar module containing both the source and destination nodes in order to establish the required data path by a direct mapping between said nodes; and

means for generating separate control signals to each of said crossbar modules on which the source and destination nodes are separately defined in order to establish the required data path by an indirect mapping between said nodes, said indirect mapping being established by (i) a first sub-mapping between the designated source node and the expansion node of the crossbar module containing said source node and (ii) a second sub-mapping between the designated destination node and the expansion node of the crossbar module containing said destination node.

6. The multi-processing system of claim 5 wherein the control commands accepted by the interconnection means include a size command defining a period of time for which the required transaction path needs to be established, and wherein said means provided within said interconnection means for generating said busy signal generates said signal for predefined periods of time for certain predefined data transactions, and for other data transactions generates the busy signal on the basis of said size commands.

7. The multi-processing system of claim 6 wherein the control commands accepted by the interconnection means include a size command defining the period of time for which the required transaction path needs to be established, and wherein said means provided within said interconnection means for generating said busy signal generates said signal for predefined periods of time for certain predefined data transactions, and for other data transactions generates the busy signal on the basis of said size commands.

8. The multi-processing system of claim 5 wherein the system comprises four CPUs, two MMUs, two I/O units, and one service processor unit (SPU), and wherein each crossbar module has five source and destination nodes, respectively, connected to two CPUs, one I/O unit, one MMU, and one SPU.

9. In a multi-processing system of the kind having a system control unit (SCU) for operating a plurality of system units in a parallel fashion, said system units including a plurality of central processing units (CUPs), at least one input/output (I/O) unit, and at least one main memory unit (MMU), interconnection means for establishing communication paths for data transactions between system units designated by communication commands as source and destination nodes, said interconnection means comprising:

at least two crossbar modules, each module adapted to establish a direct path between one of a fixed number of source nodes and one of a fixed number of destination nodes defined thereupon, each crossbar module having a respective demultiplexer for each source node and a respective multiplexer for each destination node, each demultiplexer in each crossbar module having an input connected to its respective source node and a respective output for each of the destination nodes in said each crossbar module, each multiplexer in each crossbar module having an output connected to its respective destination node and a respective input connected to a respective output of each of the demultiplexers in said each crossbar module, each of said modules including at least one expansion source node and at least one corresponding expansion destination node, the expansion source node of each module being connected directly to the expansion destination node of another one of the modules, to thereby establish a data path between source nodes defined on one of said crossbar modules and destination nodes defined on another of said crossbar modules; and

control means for operating said demultiplexers and said multiplexers in said modules for executing data transactions between designated source and destination nodes, said control means including

means responsive when the designated source and destination nodes are defined on a single crossbar module for operating the demultiplexer of the designated source node and the multiplexer of the designated destination node in order to establish the required data path by a direct path between the designated source and destination nodes, and

means responsive when the designated source and destination nodes are defined on separate crossbar modules for operating the demultiplexer of the designated source node and the multiplexer of the destination expansion node on a first one of the separate crossbar modules, and for operating the multiplexer of the destination node and the demultiplexer of the expansion source node on a second one of the separate crossbar modules, in order to establish the required data path by an indirect path between said nodes, said indirect path including the expansion destination node on the module having the designated source node, and the expansion source node on the module having the designated destination node.

10. The multi-processing system of claim 9, wherein said interconnection means further includes means for generating, for a selected time period, a busy signal indicating that the source node, the destination node, and the expansion nodes being used at a given time for establishing a data transaction path are unavailable for establishing other transaction paths.

11. The multi-processing system of claim 10, wherein the control commands accepted by the interconnection means include a size command defining a period of time for which the required transaction paths needs to be established, and wherein said means for generating said busy signal generates said signal for predefined periods of time for certain predefined data transactions, and for other data transactions generates the busy signal on the basis of said size commands.;

12. The multi-processing system of claim 10, wherein the system comprises four CPUs, two MMUs, two I/O units, the one service processor unit (SPU), and wherein the interconnection means comprises two crossbar modules, each crossbar module being adapted to provide interconnections between up to five source and destination nodes, respectively corresponding to two CPUs, one I/O unit, one MMU, and one SPU.

Description Submit all comments and votes

RELATED APPLICATIONS

The present application discloses certain aspects of a computing system that is further described in the following U.S. patent applications filed concurrently with the present application: Evans et al., AN INTERFACE BETWEEN A SYSTEM CONTROL UNIT AND A SYSTEM PROCESSING UNIT OF A DIGITAL COMPUTER, Ser. No. 07/306,325 filed Feb. 3, 1989; Arnold et al., METHOD AND APPARATUS FOR INTERFACING A SYSTEM CONTROL UNIT FOR A MULTIPROCESSOR SYSTEM WITH THE CENTRAL PROCESSING UNITS, Ser. No. 07/306,837 filed Feb. 3, 1989; Gagliardo et al., METHOD AND MEANS FOR INTERFACING A SYSTEM CONTROL UNIT FOR A MULTI-PROCESSOR SYSTEM WITH THE SYSTEM MAIN MEMORY, Ser. No. 07,306,326 filed Feb. 3, 1989; D. Fite et al., METHOD AND APPARATUS FOR RESOLVING A VARIABLE NUMBER OF POTENTIAL MEMORY ACCESS CONFLICTS IN A PIPELINED COMPUTER SYSTEM, Ser. No. 07/306,767 filed Feb. 3, 1989; D. Fite et al., DECODING MULTIPLE SPECIFIERS IN A VARIABLE LENGTH INSTRUCTION ARCHITECTURE, Ser. No. 07/307,347 filed Feb. 3, 1989; D. Fite et al., VIRTUAL INSTRUCTION CACHE REFILL ALGORITHM, Ser. No. 07/306,831 filed Feb. 3, 1989; Herman et al., PIPELINE PROCESSING OF REGISTER AND REGISTER MODIFYING SPECIFIERS WITHIN THE SAME INSTRUCTION, Ser. No. 07/306,833 filed Feb. 3, 1989; Murray et al., MULTIPLE INSTRUCTION PREPROCESSING SYSTEM WITH DATA DEPENDENCY RESOLUTION FOR DIGITAL COMPUTERS, Ser. No. 07/306,773 filed Feb. 3, 1989; D. Fite et al., PREPROCESSING IMPLIED SPECIFIERS IN A PIPELINED PROCESSOR, Ser. No. 07,306,849 filed Feb. 3, 1989; D. Fite et al., BRANCH PREDICTION, Ser. No. 07/306,760 filed Feb. 3, 1989; Fossum et al., PIPELINED FLOATING POINT ADDER FOR DIGITAL COMPUTER, Ser. No. 07/306,343 filed Feb. 3, 1989; Grundmann et al., SELF TIMED REGISTER FILE, Ser. No. 07/306,445 filed Feb. 3, 1989; Beaven et al., METHOD AND APPARATUS FOR DETECTING AND CORRECTING ERRORS IN A PIPELINED COMPUTER SYSTEM, Ser. No. 07,306,828 filed Feb. 3, 1989; Flynn et al., METHOD AND MEANS FOR ARBITRATING REQUESTS USING A SYSTEM CONTROL UNIT IN A MULTI-PROCESSOR SYSTEM, Ser. No. 07,306,871 filed Feb. 3, 1989; E. Fite et al., CONTROL OF MULTIPLE FUNCTION UNITS WITH PARALLEL OPERATION IN A MICROCODED EXECUTION UNIT, Ser. No. 07,306,832 filed Feb. 3, 1989; Webb, Jr. et al., PROCESSING OF MEMORY ACCESS EXCEPTIONS WITH PRE-FETCHED INSTRUCTIONS WITHIN THE INSTRUCTION PIPELINE OF A VIRTUAL MEMORY SYSTEM-BASED DIGITAL COMPUTER, Ser. No. 07,306,866 filed Feb. 3, 1989; Hetherington et al., METHOD AND APPARATUS FOR CONTROLLING THE CONVERSION OF VIRTUAL TO PHYSICAL MEMORY ADDRESSES IN A DIGITAL COMPUTER SYSTEM, Ser. No. 07,306,544 filed Feb. 3, 1989; Hetherington et al., WRITE BACK BUFFER WITH ERROR CORRECTING CAPABILITIES, Ser No. 07,306,703 filed Feb. 3, 1989; Flynn et al., METHOD AND MEANS FOR ARBITRATING COMMUNICATION REQUESTS USING A SYSTEM CONTROL UNIT IN A MULTI-PROCESSOR SYSTEM, Ser. No. 07,306,871 filed Feb. 3, 1989; Polzin et al., METHOD AND APPARATUS FOR INTERFACING A SYSTEM CONTROL UNIT FOR A MULTI-PROCESSOR SYSTEM WITH INPUT/OUTPUT UNIT, Ser. No. 07,306,862 filed Feb. 3, 1989; Gagliardo et al., MEMORY CONFIGURATION FOR USE WITH MEANS FOR INTERFACING A SYSTEM CONTROL UNIT FOR A MULTI-PROCESSOR SYSTEM WITH THE SYSTEM MAIN MEMORY, Ser. No. 07,306,404 filed Feb. 3, 1989; and Gagliardo et al., METHOD AND MEANS FOR ERROR CHECKING OF DRAM-CONTROL SIGNALS BETWEEN SYSTEM MODULES, Ser. No. 07/306,836 filed Feb. 3, 1989;

TECHNICAL FIELD

This invention relates generally to multi computer systems in which a plurality of system units including multiple central processor units (CPUs), Input/Output (I/O) units, and main memory units (MMUs) are operated in a parallel fashion. More particularly, this invention relates to an improved interconnection network adapted for use in such a multi-processor system and which provides efficient data transaction linkage between system units.

DESCRIPTION OF RELATED ART

High performance computers have traditionally relied upon the techniques of multi-processing and parallel processing in order to achieve increased computational power by, among other factors, circumventing bottleneck problems resulting from use of a single memory interface through which all data and control information must pass. Parallel architectures, for instance, approach such problems in a variety of ways, ranging from simple replication of conventional architecture to the utilization of completely new machine organizations.

Multi-processor architectures typically comprise a number of processors connected through some form of multi-path communication system to a common shared memory, a shared I/O system, and possibly to each other. High operational speeds and operational redundancy are achieved in high performance systems by provision of multiple communication paths between a plurality of processor units and input/output units along with parallel paths to mass storage and other devices. In a multi-processing system the parallel operation of the plurality of CPUs in conjunction with the system memory units, input/output devices, and other units of the computing system is typically coordinated by a system control unit (SCU) which links all system units ported into it and provides inter-unit communication for efficient exchange of data and related control signals. The SCU keeps all system components active while avoiding inter-unit conflicts and services requests for communications between the system memory and the system units linked through the various ports on the SCU.

Accordingly, one of the important aspects of such a system is to provide an efficient interconnection network linking the various system units that are ported into the SCU. System units in multi-processor systems are generally linked by one of two interconnection techniques: via shared buses or through data switches. A number of factors dictate the choice of one of these techniques for a particular multi-processing application. Shared buses are relatively less expensive but have restricted application because of their inherent time-multiplexed nature of operation which permits only one communication transaction (e.g., a memory to process or contact) to occur at a time. Buses, however, have the advantageous capability of being readily expanded to accept another processor, memory, or other system unit since the interconnection to the bus is necessitated only at a single junction.

Switched networks, on the other hand, allow multiple transactions to be executed concurrently as long as the transactions involved do not relate to the same system unit. More specifically, the processing elements or system units in such networks are interconnected with some kind of switching network with the capacity to transfer many data items simultaneously. A variety of switching networks are conventional and include shuffle networks, augmented data manipulation networks, butterfly switches, and crossbar matrix switches. Crossbar switches, in particular, are commonly used for implementation of a generalized connection network providing a mapping between input and output nodes in such a manner that each input can be switched to any output. However, in interconnected multi-processor systems, the time efficiency resulting from the capability to handle simultaneous multiple communication sessions comes at the expense of switch complexity and the associated increase in cost.

A major disadvantage accruing from the use of switched interconnection networks is the difficulty involved in expanding the number of system nodes beyond a predefined limit. With crossbar switches, for instance, the complexity of connections for "n" modes is given by n.sup.2 ; consequently, the number of connections increases dramatically when new processors and system units are added. As a result, when the node count is high, it becomes necessary to employ complicated multi-stage switching.

A severe restriction associated with crossbar switches is the extreme difficulty in expanding the crossbar to accommodate added system ports. Crossbars are hence designed for specific system configurations; when there is a need for the system configuration to be revised to include additional processors or memory ports, particularly in systems having a modular memory configuration adapted for expandability, a complete redesign of the crossbar network is necessitated.

SUMMARY OF THE INVENTION

For efficiently handling data transactions between various system units in a multi-processor system, the system units are linked via a plurality of expandable crossbar modules, each providing a set of interconnections or well-defined mappings between the sets of input and output nodes, with each output being defined in terms of only one input. In addition to the nodes provided at the input and output sections, each crossbar module is also provided with discrete input and output expansion ports through which the module may be linked to other identically configured crossbar modules when additional nodes are to be integrated into the system. The addition of each new crossbar module functionally replicates the modular capability of the basic crossbar module configuration.

The provision of the expansion ports on each crossbar module accordingly allows a multi-stage interconnection network to simulate the operation of a complete crossbar switch, when a full connection network is desired. It is significant that the provision of the expansion ports on each basic crossbar module permits easy expansion of node-handling capacity without the need for redesigning the crossbar and without the additional full-capacity exchange switches that would be required in a similar multi-stage interconnection network using conventional non-modular crossbars.

According to a preferred embodiment, an interconnection network is provided that permits the SCU to process simultaneous data transactions between units of a multi-processor system, which at its full capacity includes four CPUs, a pair of independently accessible main memory units (MMUs), a pair of input/output (I/O) units, and a console or service processor unit (SPU). Each crossbar module is designed as a 5.times.5 crossbar switch adapted to provide a complete mapping of five input nodes to five output nodes. A single crossbar module is hence capable of switching data transactions between a sub-system comprising a pair of CPUs, a single MMU, and a single I/O unit, and a SPU. Each module is provided with an expansion source node and an expansion destination node for serially linking crossbar modules so as to establish a connection between source and destination nodes which are spread across different crossbar modules.

If the sub-system is to be upgraded to its full capacity, it is merely required that an additional crossbar module be provided, with the expansion ports of the separate crossbar modules being linked together in a serial manner, without the need for additional switching arrangements. The serially-linked expansion ports realize the direct mapping of all system modes in the form of a two-stage network; however, what is important is that the basic crossbar design remains the same and the need to redesign the module to accommodate the added data-transfer nodes is obviated.

The modular arrangement using the expansion ports on each crossbar module can conveniently be expanded to accommodate larger node capacities by the addition of a corresponding number of identical crossbar modules. In all cases, a direct mapping of nodes existing across serially expanded crossbars is realized by a series of sub-mappings providing links respectively between a source node within a given crossbar to the output expansion port thereof, the output expansion port to the input expansion port of a crossbar module which includes the destination node, and finally that input expansion port to the destination node itself.

According to a preferred implementation of the modular crossbar scheme of this invention, incoming data transaction commands are buffered and decoded to identify the source and destination ports. A data switch controller is provided for identifying the need for sub-mappings and in response thereto assigning the sub-mappings required for executing a particular direct mapping. More specifically, the controller monitors the availability of data transaction paths by recognizing when any of the specified source and destination nodes become unavailable for participating in data transactions. More importantly the controller determines whether the two nodes specified for a particular data transaction are ported into the crossbar module forming the initial stage of the interconnection network. If the nodes are part of the same module, data transfer is accomplished by a direct mapping from the source node to the destination node. Otherwise, control is relinquished to an expansion port decoder which identifies the particular crossbar modules in the subsequent stages of the interconnection network in which the designated nodes are defined.

Appropriate sub-mappings are then provided for serially linking the expansion ports of the crossbar modules identified as housing the ports for the source and the destination nodes. In physical terms, the sub-mappings establish a sequential, yet direct link for transfer of data to or from a requesting source node and a designated destination node. The details involved in implementing a modular crossbar arrangement of the type discussed above , including the identification of the need to address expansion ports, the decoding process for identifying modules containing a source and destination nodes, and the generation of sub-mappings linking the nodes will be discussed in detailed below.

BRIEF DESCRIPTION OF THE DRAWINGS

Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the drawings in which:

FIG. 1 is a simplified block diagram illustrating a multi-processor computer system in which a system control unit (SCU) is provided with an interconnection network for linking a plurality of processors and input/output (I/O) units together and to a shared memory;

FIG. 2 is a simplified illustration of a preferred interconnection network in the form of a pair of crossbar modules serially linked through expansion ports for use with the multi-processor system of FIG. 1;

FIG. 3 is a detailed schematic diagram of the basic modular composition of a crossbar module illustrating the manner in which input nodes are mapped onto output nodes including the expansion nodes;

FIG. 4 is a block diagram illustrating data transaction commands recognized by a data switch controller and responsive control signals generated by the data switch controller for controlling the crossbar modules;

FIG. 5 is a table illustrating the preferred control inputs for defining the source/destination ports for the two-staged arrangement of crossbar modules shown in FIG. 3;

FIG. 6 is a table illustrating the preferred control inputs for defining sub-sources and sub-destinations for crossbar modules when sub-mappings are needed to execute communication requests;

FIG. 7 is a block diagram of a preferred modular construction for the data switch controller of FIG. 4; and

FIG. 8 is a flowchart illustrating the arbitration of communication requests and the response of the data switch controller to granted requests for controlling the crossbar modules for establishing the requested data transaction paths between system units.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that it is not intended to limit the invention to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

DESCRIPTION OF THE PREFERRED EMBODIMENT

Turning now to the drawings and referring in particular to FIG. 1, there is shown a simplified block diagram of a multi-processor computer system 10 which uses a plurality of central processing units (CPUs) 12 and is adapted to permit simultaneous operation of the system CPUs, in combination with a plurality of input/output (I/O) units 14, by allowing the system units to share a common main memory 16 for the system. The I/O units 14 are used to permit the processing system in general and the CPUs in particular to communicate with the external world through an appropriate I/O interface (not shown) associated with the units. The main memory 16 itself typically comprises a plurality of memory modules or units 16A and 16B. A system control unit (SCU) 18 links the CPUs 12 and I/O units 14 to the main memory 16 and to each other through an interconnection network 20. The SCU 18 also uses the interconnection network 20 to link the various system modules to a service processor/console unit (SPU) 22 which performs traditional console functions including status determination and the control of the overall operation of the processing system.

In the multi-processor system of FIG. 1, efficient communication between system units linked through the SCU 18 and the main memory 16, and more particularly between each system CPU 12 and each system I/O unit 14 and the individually addressable segments comprising each memory unit 16A, 16B is handled through dedicated interface means 24. The specific configuration of the main memory and the particular manner in which the SCU is interfaced to the memory is not important to the present invention and accordingly will not be discussed in detail herein. For purposes of describing the present invention, it suffices to state that each memory unit 16A, 16B of the main memory 16 is provided with a corresponding memory port on the SCU with each port being linked to a separate pair of individually addressable segments which are interleaved on block boundaries.

The interconnection network 20 functions as means for providing a path for data transactions between the various system units and the multi-processor system and links the CPUs 12, the I/O units 14, and the SPU 22 together for exchange of data between themselves and each of the plurality of main memory units (MMUs) 16A and 16B. Accordingly, the interconnection network 20 may form part of the dedicated interface means 24 between the SCU and main memory in addition to linking the remaining system units.

Each system unit, such as a CPU or an I/O unit, is ported into the SCU 18 through a discrete port and all communication requests between memory and the system units, as well as between the units themselves, are lodged at the corresponding port on the SCU. The SCU 18 functions to keep system units active while avoiding inter-unit conflict by handling requests for communications between the system unit and the system memory that are received at various ports on the SCU. Because the various CPUs and I/O units are operated in a parallel fashion within the multi-processor system, a plurality of communication requests are routinely received at the SCU. In addition, a number of such requests may typically require access to the same system resources in order to honor the requests by executing the commands associated therewith.

Incoming requests received at the SCU ports from the system units are arbitrated for processing by the SCU in a manner which utilizes the system resources in the most efficient manner and in addition treats each arriving system request in a fair manner by processing the request within a reasonable period of time. A preferred technique on the basis of which the SCU can arbitrate outstanding requests from system units in such a way as to achieve the dual requirements of system efficiency and unit fairness is described in the above mentioned Flynn et al. U.S. application Ser. No., 07/306,871, filed Feb. 3, 1989 titled "Method and Means for Arbitrating Communication Requests Using A System Control Unit In a Multi-Processor System," which is also owned by the assignee of the present invention.

Regardless of the arbitration technique that is used to define the order in which incoming communication requests are processed, it is critical that a number of data transactions between system units be performed simultaneously in order to achieve efficient system operation by optimizing the processing capabilities of the plurality of system CPUs.

Traditional interconnection networks have typically comprised of shared buses in systems where simultaneous multiple data transactions are not critical. Where a number a number of data transactions have to be processe