Multiprocessor interconnection and access arbitration arrangement

Claim 2

A multiprocessor system (FIG. 1) comprising a plurality of processors (10-12), and a non-blocking communication medium (16,19,20) interconnecting the plurality of processors, CHARACTERISED BY a control communication medium (14) interconnecting the plurality of processors; means (403) in each processor for communicating a request to access another processor to the other processor across the control medium; means (205) in each processor, responsive to conflicting requests for access to the associated processor received from other processors across the control medium, for resolving the conflicts and selectively granting the requests for access to the associated processors; and means (22), responsive to the granting of a request, for establishing a connection through the non-blocking medium between the requesting processor whose request was granted and the granting processor.

Claim 3

The system of claim 1 CHARACTERISED IN THAT the means for establishing a connection are a single, centralized, apparatus (22) responsive to the request-granting means of all of the processors.

Claim 4

The system of claim 2 CHARACTERISED IN THAT the conflict-resolving and request-granting means include means (804,808,809) in each processor responsive to the granting of a request by the associated processor's conflict-resolving and request-granting means, for communicating the grant across the control medium to the processor whose request was granted.

Claim 5

The system of claim 1 CHARACTERISED IN THAT the conflict-resolving and request-granting means comprise means (405) for prioritizing the conflicting requests and granting the requests sequentially in their order of priority.

Claim 6

The system of claim 1 CHARACTERISED IN THAT the non-blocking communication medium comprises: a crossbar switch (19,20); and a plurality of optical links (16) each connecting a different processor to the crossbar switch.

Claim 7

The system of claim 1 CHARACTERISED IN THAT the non-blocking communication medium comprises a non-blocking fabric (19), and a plurality of communication links (16,20), each connecting a processor to the fabric; the request-communicating means comprises means (403) in each processor for communicating a request to access the link of another processor to the other processor across the control medium; the conflict-resolving and request-granting means comprises means (205) in each processor, responsive to received conflicting requests for access to the link of the associated processor, for resolving the conflicts and selectively granting the access requests; and the connection-establishing means comprises means (22), responsive to the granting of a request, for establishing a connection through the non-blocking medium between the link of the requesting processor whose request was granted and the link to which the granted access was requested.

Claim 8

The system of claim 6 CHARACTERISED IN THAT the conflict-resolving and request-granting means include means (804, 808, 809) in each processor, responsive to the granting of request by the associated processor's conflict-resolving and request-granting means, for communicating the grant across the control medium to the processor whose request was granted; and means (400-405) in the processor whose request was granted, responsive to receipt of the communicated grant for measuring time elapsed since the grant was received and causing the associated conflict-resolving and request-­ granting means to grant a pending request for access to the associated link when a predetermined time has elapsed.

Claim 9

The system of claim 6 CHARACTERISED IN THAT the conflict-resolving and request-granting means interleave granting of access requests of processors other than the associated processor with granting of access requests of the associated processor.

Claim 10

The system of claim 6 CHARACTERISED IN THAT the conflict-resolving and request-granting means are responsive to conflicting requests for access to the link of the associated processor made both by the other processors and by the associated processor for resolving the conflicts and selectively granting the access requests.

Claim 11

The system of claim 9 CHARACTERISED IN THAT the conflict-resolving and request-granting means grant the access requests sequentially.

Claim 12

The system of claim 10 CHARACTERISED IN THAT the conflict-resolving and request-granting means interleave granting of access requests of processors other than the associated processor with granting of access requests of the associated processor.

Claim 13

The system of claim 6 CHARACTERISED IN THAT the conflict-resolving and request-granting means include means (400-405) in each processor, responsive to the granting of a request by the associated request-granting means, for measuring time elapsed since the request was granted and causing the associated request-granting means to grant another request when a predetermined time has elapsed.

Claim 14

The system of claim 9 CHARACTERISED IN THAT the request-communicating means are responsive to the granting, by the associated conflict-resolving and request-granting means, of a request of the associated processor, for communicating to another processor a request by the associated processor to access the link of the other processor.

Claim 15

The system of claim 13 CHARACTERISED IN THAT the conflict-resolving and request-granting means include first means (400-402,404,457,459) in each processor, responsive to the granting of a request of the associated processor by the associated request-granting means, for measuring time elapsed since the request was granted and indicating when a predetermined time has elapsed; and the request-communicating means further are responsive to the indication by the first time measuring and indicating means, for communicating to the other processor a cancellation of the request by the associated processor to access the link of the other processor.

Claim 16

The system of claim 14 CHARACTERISED IN THAT the conflict-resolving and request-granting means include second means (400-402,456,458) in each processor, responsive to the granting of a request by the associated request-granting means, for measuring time elapsed since the request was granted and indicating when a predetermined time has elapsed; and the request-granting means further are responsive to the indication by the second time measuring and indicating means, for granting another request.

Claim 17

The system of claim 1 CHARACTERISED BY a plurality of port circuits (18) one connected to each processor, each port circuit having a different I.D. (406); the contention medium (14) interconnecting the plurality of port circuits; and transmission means (21) for cyclically sequentially transmitting the I.D.s of the plurality of port circuits on the contention medium; each port circuit comprising the request-communicating means, which include first means (400,403), responsive to a request from the connected processor for access to another processor, for transmitting the request to the other processor across the contention medium when the I.D. of the other processor's port circuit is being transmitted on the contention medium by the transmission means, and the conflict-resolving and request-granting means, which include second means (800) for storing requests transmitted on the contention medium when the I.D. of the port circuit that includes the second means is transmitted on the contention medium by the transmission means, third means (803) for prioritizing request stored by the second means, fourth means (400-405) for determining when the connected processor is ready for access by another processor, and fifth means (804,808), responsive to determination by the fourth means that the connected processor is ready for access by another processor, for transmitting on the contention medium the I.D. of the port circuit having a highest-priority pending request stored by the second means, when the I.D. of the port circuit that includes the fifth means is transmitted on the contention medium by the transmission means; and the connection-establishing means including means (22) associated with the non-blocking communciation medium and responsive to transmission by a fifth means on the contention medium of the I.D. of a port circuit, for establishing a connection between the processors connected to the ports whose I.D.s are simultaneously transmitted on the contention medium by the fifth means and the transmission means.

Claim 18

The system of claim 16 CHARACTERISED IN THAT the conflict-resolving and request-granting means include sixth means (404), responsive to transmission by a fifth means on the contention medium of the I.D. of the port circuit that includes the sixth means, for notifying the fourth means that an access to another processor by the connected processor has been granted.

Claim 19

The system of claim 16 CHARACTERISED IN THAT the non-blocking communication medium comprises: a crossbar switch (19,20), and a plurality of optical links (16) each connecting a different processor to the crossbar switch.

Claim 20

The system of claim 18 CHARACTERISED IN THAT each optical link further connects the connected processor to the processor's port circuit.