Bit-sliced cross-connect chip having a tree topology of arbitration cells for connecting memory modules to processors in a multiprocessor system

• US 5,053,942 A
• Filed: 11/01/1988
• Issued: 10/01/1991
• Est. Priority Date: 11/01/1988
• Status: Expired due to Fees

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Srini, Vason P.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Harrell, Robert B.
• Application Number:
  US07/265,546
• Time in Patent Office: 1,064 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 370/1, 370/24, 370/34, 370/41, 370/49.5, 370/53, 370/69.1, 370/77, 370/119
• US Class Current: 710/317
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines
• CPC Class Codes: G06F 15/17375 One dimensional, e.g. linear array, ring

Abstract

A cross-connect circuit for coupling each of a plurality of processors to a memory module selected from a plurality of such modules, provided the module in question has not been identified for connection to another of the processors is disclosed. The circuit is preferably organized as a bit-sliced chip. The connections made by the cross-connect circuit can be changed after each memory cycle.

Claims

1. A cross-connect circuit for coupling each of a plurality of processors to one of a plurality of modules, provided a module in question has not been identified for connection to another one of said processors, said circuit comprising a plurality of input ports, one of said input ports corresponding to each of said processors, and a plurality of output ports, one of said output ports corresponding to each of said modules:

each of said input ports comprising;

means for connecting one of said processors to said cross-connect circuit;

means for receiving a module address specifying one of said modules;

means for receiving an address bit to be communicated to said one of said modules specified by said module address;

means for receiving a data bit to be transmitted to said one of said modules specified by said module address; and

means for transmitting a data bit to be received by said one of said processors connected thereto; and

each of said output ports comprising;

means for connecting said cross-connect circuit to said one of said modules specified by said module address;

means for transmitting an address bit to be communicated to said one of said modules specified by said module address;

means for transmitting a data bit to be received by said one of said modules specified by said module address; and

means for receiving a data bit from said one of said modules connected thereto,

said cross-connect circuit further comprising;

a plurality of arbiter means for assigning each of said modules to one of said processors, wherein each said arbiter means includes a plurality of arbiter cells connected in a tree topology with more than one branch point, one of said arbiter means corresponding to each of said modules, each of said arbiter means being connected to each of said means for receiving a module address and being responsive to said module address received by said means for receiving a module address, wherein when more than one of said input ports receives an identical said module address, said one of said arbiter means corresponding to said module address selects only one of said input ports for connection to said one of said modules specified by said module address; and

cross-connect matrix means for connecting each of said input ports to each of said output ports, said arbiter means determining which of said input ports and output ports are to be connected at any given time by said cross-connect matrix means.

2. The cross-connect circuit of claim 1 wherein each of said means for receiving a module address further comprise means for decoding said module address, said means for decoding including one decode conductor corresponding to each of said modules and producing a signal on said decode conductor corresponding to a given one of said modules in response to said module address corresponding to said given one of said modules being received by said means for receiving a module address.

3. A cross-connect circuit for coupling each of a plurality of processors to one of a plurality of modules, provided a module in question has not been identified for connection to another one of said processors, said circuit comprising a plurality of input ports, one of said input ports corresponding to each of said processors, and a plurality of output ports, one of said output ports corresponding to each of said modules:

each of said input ports comprising;

means for connecting one of said processors to said cross-connect circuit;

means for receiving a module address specifying one of said modules;

said means for receiving a module address comprising means for decoding said module address, said means for decoding including one decode conductor corresponding to each of said modules and producing a signal on said decode conductor corresponding to a given one of said modules in response to said module address corresponding to said given one of said modules being received by said means for receiving a module address,

means for receiving an address bit to be communicated to said one of said modules specified by said module address;

means for receiving a data bit to be transmitted to said one of said modules specified by said module address; and

means for transmitting a data bit to be received by said one of said processors connected thereto; and

each of said output ports comprising;

means for connecting said cross-connect circuit to said one of said modules specified by said module address;

means for transmitting an address bit to be communicated to said one of said modules specified by said module address;

means for transmitting a data bit to be received by said one of said modules specified by said module address; and

means for receiving a data bit from said one of said modules connected thereto,

said cross-connect circuit further comprising;

a plurality of arbiter means for assigning each of said modules to one of said processors, one of said arbiter means corresponding to each of said modules, each of said arbiter means being connected to each of said means for receiving a module address and being responsive to said module address received by said means for receiving a module address, wherein when more than one of said input ports receives an identical said module address, said one of said arbiter means corresponding to said module address selects only one of said input ports for connection to said one of said modules specified by said module address;

cross-connect matrix means for connecting each of said input ports to each of said output ports, said arbiter means, determining which of said input ports and said output ports are to be connected at any given time by said cross-connect matrix means; and

wherein each of said arbiter means comprises a plurality of arbiter cells, each of said arbiter cells comprising;

means for specifying two states, a one and a zero;

first, second, and third input means for receiving a first, second, and third input binary signal, respectively;

first, second, and third output means for transmitting first, second and third output binary signal, respectively, wherein

said third output signal is a one if either of said first or second input signals is a one and zero otherwise, and wherein said second and third output signals are given by the following table;

space="preserve" listing-type="tabular">__________________________________________________________________________PRESENT NEXT INPUT MEANS OUTPUT MEANS STATE STATE FIRST SECOND THIRD FIRST SECOND __________________________________________________________________________0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 -- -- 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1 1 -- -- 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 __________________________________________________________________________

wherein "--" indicates that either one or zero may be present, and wherein said arbiter cells are connected in a tree topology comprising an order sequence of M levels designated as a first level through to an Mth level, inclusive, said first level being the leaf level of said tree, said Mth level comprising one of said arbiter cells and an Ith level comprising twice as many of said arbiter cells as an (I+1)st level,

said arbiter cells in said Ith level, for I values from 2 to (M-1), being connected with said first input means of each said arbiter cell connected to said third output means of one of said arbiter cells in an (I-1)st level and said second input means of each said arbiter connected to said third output means of a different one of said arbiter cells in the (I-1)st level, said third input means of each of said arbiter cells being connected to either a said first output means or a said second output means of one of said arbiter cells in said (I+1)st level,

said third output means of said one of said arbiter cells comprising said Mth level being connected to said third input means thereof,

said first and second input means of said arbiter cells in said first level being connected to different ones of said decode conductors, and

said first and second output means of said arbiter cells in said first level being connected to said cross-connect matrix means and determining which connections are made thereby.

4. A cross-connect circuit for coupling each of a plurality of processors to one of a plurality of modules, provided a module in question has not been identified for connection to another one of said processors, said circuit comprising a plurality of input ports, one of said input ports corresponding to each of said processors, and a plurality of output ports, one of said output ports corresponding to each of said modules;

each of said input ports comprising;

means for connecting one of said processors to said cross-connect circuit;

means for receiving a module address specifying one of said modules;

said means for receiving a module address comprising means for decoding said module address, said means for decoding including one decode conductor corresponding to each of said modules and producing a signal on said decode conductor corresponding to a given one of said modules in response to said module address corresponding to said given one of said modules being received by said means for receiving a module address,

means for receiving an address bit to be communicated to said one of said modules specified by said module address;

means for receiving a data bit to be transmitted to said one of said modules specified by said module address; and

means for transmitting a data bit to be received by said one of said processors connected thereto; and

each of said output ports comprising;

means for connecting said cross-connect circuit to said one of said modules specified by said module address;

means for transmitting an address bit to be communicated to said one of said modules specified by said module address;

means for transmitting a data bit to be received by said one of said modules specified by said module address; and

means for receiving a data bit from said one of said modules connected thereto,

said cross-connect circuit further comprising;

a plurality of arbiter means for assigning each of said modules to one of said processors, one of said arbiter means corresponding to each of said modules, each of said arbiter means being connected to each of said means for receiving a module address and being responsive to said module address received by said means for receiving a module address, wherein when more than one of said input ports receives an identical said module address, said one of said arbiter means corresponding to said module address selects only one of said input ports for connection to said one of said modules specified by said module address;

cross-connect matrix means for connecting each of said input ports to each of said output ports, said arbiter means determining which of said input ports and said output ports are to be connected at any given time by said cross-connect matrix means; and

wherein each of said arbiter means comprises a plurality of arbiter cells, each of said arbiter cells comprising;

means for specifying two states designated by a binary signal, Q, being a one or a zero;

first, second, third, and fourth input means for receiving binary signals, RQ0, RQ1, GRC, and RESETB, respectively;

first, second, and third output means for transmitting a first, second and third output binary signal, respectively, wherein

said third output signal is a one if either of said first or second input signals is a one and zero otherwise, said first output signal is determined by a logic equation

space="preserve" listing-type="equation">RQ0*GRC*(Q+RQ1)*RESETB

wherein said second output signal is determined by a logic equation

space="preserve" listing-type="equation">RQ1*GRC*(Q+RQ0)*RESETB

and wherein said arbiter cells are connected in a tree topology comprising an order sequence of M levels designated as a first level through to an Mth level, inclusive, said first level being the leaf level of said tree, said Mth level comprising one of said arbiter cells and an Ith level comprising twice as many of said arbiter cells as an (I+1)st level,

said arbiter cells in said Ith level, for I values from 2 to (M-1), being connected with said first input means of each said arbiter cell connected to said third output means of one of said arbiter cells in an (I-1)st level and said second input means of each said arbiter connected to said third output means of a different one of said arbiter cells in the (I-1)st level, said third input means of each of said arbiter cells being connected to either a said first output means or a said second output means of one of said arbiter cells in said (I+1)st level,

said third output means of said one of said arbiter cells comprising said Mth level being connected to said third input means thereof,

said first and second input means of said arbiter cells in said first level being connected to different ones of said decode conductors, and

said first and second output means of said arbiter cells in said first level being connected to different ones of said decode conductors, and

said first and second output means of said arbiter cells in said first level being connected to said cross-connect matrix means and determining which connections are made thereby.

5. The cross-connect circuit of claim 4 wherein said means for specifying two states comprises a J-K flip-flop, and wherein each of said arbiter cells further comprises means for applying a first signal to a J input of said J-K flip-flop, said first signal satisfying the logic equation

6. The cross-connect circuit of claim 4 wherein said means for specifying two states comprises a D flip-flop, and wherein each of said arbiter cells further comprises means for applying a signal to D input of said D flip-flop, said signal satisfying a logic equation

7. An arbiter circuit connected to a plurality of input lines and a plurality of output lines, the number of said input lines being equal to the number of said output lines, said circuit providing means for producing a signal on a single one of said output lines in response to one or more signals on said input lines, said arbiter circuit including a plurality of arbiter cells, each of said cells comprising:

means for specifying two states, a one and a zero;

first, second, and third input means for receiving a first, second and third input binary input signals, respectively;

first, second and third output means for transmitting a first, second and third binary output signal, respectively, wherein

said third output signal is a one if either of said first or second input signals is a one and zero otherwise, and wherein said first and second output signals are given by the following table;

space="preserve" listing-type="tabular">__________________________________________________________________________PRESENT NEXT INPUT MEANS OUTPUT MEANS STATE STATE FIRST SECOND THIRD FIRST SECOND __________________________________________________________________________0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 -- -- 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1 1 -- -- 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 __________________________________________________________________________

wherein "--" indicates that either one or zero may be present, and wherein said arbiter cells are connected in a tree topology comprising an order sequence of M levels designated as a first level through to an Mth level, inclusive, said first level being the leaf level of said tree, said Mth level comprising one of said arbiter cells and an Ith level comprising twice as many of said arbiter cells as an (I+1)st level,

said arbiter cells in said Ith level, for I values from 2 to (M-1), being connected with said first input means of each said arbiter cell connected to said third output means of one of said arbiter cells in an (I-1)st level and said second input means of each said arbiter connected to said third output means of a different one of said arbiter cells in the (I-1)st level, said third input means of each of said arbiter cells being connected to either a said first output means or a said second output means of one of said arbiter cells in said (I+1)st level,

said third output means of said one of said arbiter cells comprising said Mth level being connected to said third input means thereof,

said first and second input means of said arbiter cells in said first level being connected to different ones of a plurality of decode conductors, and

said first and second output means of said arbiter cells in said first level being connected to different ones of said output lines.