Dynamic packet routing network

• US 5,282,201 A
• Filed: 05/10/1990
• Issued: 01/25/1994
• Est. Priority Date: 12/22/1987
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Kendall Square Research Corp.
• Inventors: Morss, Stephen W., Binder, Paul A., Rothnie, James B., Kelly, Dana R., Frank, Steven J., Burkhardt, Henry III, Epstein, David I.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Kizou, H.
• Application Number:
  US07/521,798
• Time in Patent Office: 1,356 Days
• Field of Search: 370/85.9, 370/85.12, 370/85.13, 370/85.14, 370/85.15, 370/85.1, 370/85.8, 370/94.1, 370/94.3, 370/95.2, 370/60, 370/60.1
• US Class Current: 370/403
• CPC Class Codes: G06F 11/004 Error avoidance G06F11/07 and subgroups take precedence
• CPC Class Codes: G06F 11/0724 in a multiprocessor or a multi-core unit multiprocessors per se G06F15/80
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0772 Means for error signaling, e.g. using interrupts, exception flags, dedicated error registers
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 2212/272 Cache only memory architecture [COMA]
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3865 using deferred exception handling, e.g. exception flags
• CPC Class Codes: G06F 9/468 Specific access rights for resources, e.g. using capability register
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H04L 12/4637 Interconnected ring systems
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 45/04 : Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 49/107 : using shared medium
• CPC Class Codes: H04L 49/255 : Control mechanisms for ATM switching fabrics
• CPC Class Codes: H04L 49/256 : Routing or path finding in ATM switching fabrics

Abstract

A digital data communications apparatus includes first and second processing groups, each made up of a plurality of processing cells interconnected by an associated bus. An element (RRC) transfers information packets generated by the processing cells between the first and second processing groups. The RRC includes an input for receiving packets from the bus of the first processing group, as well as first and second outputs for outputting packets to the buses of the first and second groups, respectively. A control element routes packets received at the input to a selected one of the outputs based upon a prior history of routings of the datum referenced in that information packet (or requests for that data) between said first and second processing groups.

Claims

1. A digital data communications apparatus comprising

A. first and second processing groups, each said group including a plurality of processing cells connected by an associated bus means for transferring signals representative of information packets therebetween,

each processing cell

i) having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

ii) including CCU means for at least one of generating and receiving signals representative of an information packet including a descriptor of a datum subject to reference,

B. first level transfer means for transferring information packets between said first and second processing groups, said first level transfer means including

i) first input means, coupled to the bus means of said first processing group, for receiving an information packet therefrom,

ii) first output means, coupled to the bus means of said first processing group, for selectively outputting an information packet thereto,

iii) second output means, coupled to the bus means of said second processing group, for selectively outputting an information packet thereto,

C. said first level transfer means including routing control means, connected to said first input means and to said first and second output means, for routing an information packet received on said first input means to a selected one of said first and second output means based upon prior routings, if any, of the datum referenced in that information packet, or requests for that datum, between said first and second processing groups.

2. An apparatus according to claim 1, wherein said routing control means includes directory means for storing signals representative of prior routings of data, or request therefor, between said first and second processing groups.

3. An apparatus according to claim 2, wherein said routing control means includes means coupled to said directory means for comparing a descriptor in a packet received at said first input means with said directory signals to determine which of said first and second output means to route that packet to.

4. An apparatus according to claim 3, wherein said first level means further includes

A. second input means, coupled to the bus means of said second processing group and to said routing control means, for receiving an information packet from said second processing group, and

B. said routing control means further includes means for routing an information packet received by said second input means to a selected one of said first and second output means based on prior routings, if any, of the datum referenced in that information packet, or requests for that datum, between said first and second processing groups.

18. An apparatus according to claim 4 or 8, wherein said second processing group comprises

A. a plurality of further processing groups, each including a plurality of processing cells connected by an associated bus means for transferring information packets therebetween,

B. a plurality of further level transfer means, each associated with a corresponding one of said further processing groups and coupled to the bus means thereof, for selectively transferring information packets therewith, and

C. means connected with said first level transfer means and with said further level transfer means for transferring information packets therebetween.

65. An apparatus according to claim 4 or 8, wherein

A. said second processing group comprises third and fourth processing groups, each including a plurality of said processing cells, the processing cells of each said processing group being connected by an associated bus means for transferring at least information packets therebetween, each processing cell

i) including CCU means for at least one of generating and receiving an information packet including a descriptor of a datum subject to reference,

ii) having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

B. ring-one bus means, connected to said second input means and said second output means of said first level transfer means, carrying information packets, and

C. second and third ones of said level transfer means, each connecting the respective bus means of said third and fourth processing groups to said ring-one bus means.

66. An apparatus according to claim 65, wherein the directory means of the routing control means of each of said first, second and third level transfer means includes means for storing allocation state-defining information for at least selected data, or copies thereof, allocated to the processing cells of the corresponding processing group, said allocation state-defining information including at least an invalid allocation state for an invalid datum allocated to said first processing group.

67. An apparatus according to claim 66, wherein

A. a processing cell in said first processing group includes invalidating means for generating and transferring to the bus means associated with said first processing group an invalid-descriptor packet including a descriptor associated with a datum, or copy thereof, to be invalidated in others of said processing cells,

B. said first level transfer means includes means for routing said invalid-descriptor packet to said ring-one bus means.

68. An apparatus according to claim 67, wherein at least one of said second and third level transfer means includes

A. means responsive to said invalid-descriptor packet received on said ring-one bus means for generating a look-ahead packet including said invalidated descriptor associate with said datum, or copy thereof, to be invalidated and for transferring that look-ahead packet onward on said ring-one bus means, and

B. means for substantially concurrently transferring said invalid-descriptor packet to said associated processing group to invalidate a read-only copy of the datum referenced in that invalid-descriptor packet.

69. An apparatus according to claim 68, wherein at least one of said second and third level transfer means includes means responsive to said look-ahead packet received on said ring-one bus means for invalidating a read-only copy of the datum referenced in that look-ahead packet, and for continuing transfer of said look-ahead packet on said ring-one bus means.

70. An apparatus according to claim 69, wherein

A. at least one of said second and third level transfer means includes means for routing said invalid-descriptor packet, as indicative of completion of invalidation of a read-only copy, if any, of the datum in that packet in the associated processing group, to said ring-one bus means,

B. at least one of the other of said second and third level transfer means includes means responsive to receipt of said invalid-descriptor packet subsequent to receipt of said look-ahead packet on said ring-one bus means for passing that invalid-descriptor packet to said first level transfer means on said ring-one bus means.

5. A digital data communications apparatus comprising

A. first and second processing groups, each said group including a plurality of processing cells connected by an associated bus means for transferring signals representative of information packets therebetween,

each processing cell

i) having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced

ii) including CCU means for at least one of generating and receiving signals representative of an information packet including a descriptor of a datum subject to reference,

iii) wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that same processing cell,

B. first level transfer means for transferring information packets between said first and second processing groups, said first level transfer means including

i) first input means, coupled to the bus means of said first processing group, for receiving an information packet therefrom,

ii) first output means, coupled to the bus means of said first processing group, for selectively outputting an information packet thereto,

iii) second output means, coupled to the bus means of said second processing group, for selectively outputting an information packet thereto,

C. said first level transfer means including routing control means, connected to said first input means and to said first and second output means, for routing an information packet received by that input means to a selected one of those output means based upon correspondence between the descriptor in that information packet and data allocated to, or requested for allocation by, one or more processing cells of said first processing group.

6. An apparatus according to claim 5, wherein said routing control means includes directory means for storing signals representative of data allocated to, or requested for allocation by, said first processing group.

7. An apparatus according to claim 6, wherein said routing control means includes means coupled to said directory means for comparing a descriptor in a packet received at said first input means with said directory signals to determine which of said first and second output means to route that packet to.

8. An apparatus according to claim 7, wherein said first level transfer means further includes

A. second input means, coupled to the bus means of said second processing group and to said routing control means, for receiving an information packet from said second processing group, and

B. said routing control means further includes means for routing an information packet received by said second input means to a selected one of said first and second output means based on correspondence between the descriptor in that information packet and the data allocated to, or requested for allocation by, one or more processing cells of said first processing group.

9. A routing switch apparatus for digital information packets, comprising

A. first input means for receiving an information packet from a first processing group,

B. first and second output means for transferring said information packet to a respective one of said first processing group and a second processing group,

each said processing group comprising a plurality of processing cells coupled by an associated bus means,

said first input and output means being coupled to the bus means associated with said first processing group, said second output means being coupled to the bus means associated with said second processing group,

each processing cell

i) having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

ii) including CCU means for at least one of generating and receiving signals representative of an information packet including a descriptor of a datum subject to reference,

ii) wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that processing cell,

C. first level transfer means for transferring information packets between said first and second processing groups, said first level transfer means including routing control means, connected to said first input means and to said first and second output means, for routing an information packet received by that input means to a selected one of those output means based upon correspondence between the descriptor in that information packet and the datum allocated to, or requested for allocation by, one or more processing cells in said first processing group.

10. An apparatus according to claim 9, wherein said routing control means includes directory means for storing signals representative of data allocated to, or requested for allocation by, said first processing group.

11. An apparatus according to claim 10, wherein said routing control means includes means coupled to said directory means for comparing a descriptor in a packet received at said first input means with said directory signals to determine which of said first and second output means to route that packet to.

12. An apparatus according to claim 11, wherein said first level transfer means further includes

A. second input means, coupled to the bus means of said second processing group and to said routing control means, for receiving an information packet from said second processing group, and

B. said routing control means further includes means for routing an information packet received by said second input means to a selected one of said first and second output means based on correspondence between the descriptor in that information packet and data allocated to, or requested for allocation by, one or more processing cells of said first processing group.

16. An apparatus according to claims 4 or 8 or 12 or 15, wherein

A. at least one of said first and second input means is disposed physically remotely from at least one of said first and second output means, and

B. said first level transfer means includes remote interface means, coupled to said routing control means and to said at least one remotely disposed input means and to said first and second output means, for selectively transferring an information packet received by said at least one remotely disposed input means to said selected one of said first and second output means.

17. An apparatus according to claim 16, wherein said remote interface means includes fiber optic transmission media for carrying signals representative of said information packets between said at least one remotely disposed input means and said first and second output means.

19. An apparatus according to claim 4 or 8 or 12 or 15, wherein said directory means includes means for storing allocation state-defining information for at least selected data, or copies thereof, allocated to said first processing group, said allocation state-defining information including at least one of

i) an invalid allocation state for an invalid datum allocated to said first processing group,

ii) a read-only allocation state for a copy of a datum allocated to and subject to read-only access by a processing cell of said first processing group, no copy of which datum is modifiable by a processing cell of said first processing group,

iii) a nonexclusive owner allocation state for a datum allocated to and modifiable by a processing cell of said first processing group, one or more read-only copies of which datum are allocated to other processing cells of said first and second processing groups, and

iv) an exclusive owner allocation state for a datum exclusively allocated to and modifiable by a processing cell of said first processing groups, no copies of which datum are allocated to other processing cells of said first and second processing groups.

20. An apparatus according to claim 4 or 8 or 12 or 15, wherein said directory means includes a first directory portion for storing signals representative of descriptors corresponding to data for which requests are pending to said first processing group from said second processing group.

21. An apparatus according to claim 20, wherein said directory means includes a second directory portion for storing signals representative of descriptors corresponding to data for which requests are pending to said second processing group from said first processing group.

22. An apparatus according to claim 21, wherein said directory means includes means for storing at least one of said directory portions a signal representative of a descriptor corresponding to a datum for which a request is pending, said storing occurring upon receipt of a first information packet requesting allocation of that datum.

23. An apparatus according to claim 21, wherein at least one of said first and second directory portions includes means for storing pending state-defining information for at least selected data for which requests are pending to at least one of said processing groups, said pending state-defining information including at least one of

i) a none-pending pending state for a datum for which no requests are pending,

ii) a read-only pending state for a datum for which a read-only allocation request is pending,

iii) an ownership pending state for a datum for which an ownership allocation request is pending, or for which an invalidation request is pending, and

iv) a reissue pending state for a datum for which a request is pending and for which a response other than one generated in response to that request has issued.

24. An apparatus according to claim 23, wherein said routing control means includes means for updating said first and second directory portions in conjunction with the routing of a request packet between said first and second processing groups.

25. An apparatus according to claim 24, wherein said routing control means includes routing directory unit means, connected to said directory means, for comparing the descriptor included in an information packet received from any of said first and second input means to said directory means to determine if a datum, or a request therefor, is allocated to said first processing group.

30. An apparatus according to claim 4 or 8 or 12 or 15, wherein said first level transfer means includes multiple request-handling means selectively responsive to receipt, from processing cells in any of said first and second processing groups, of multiple information packets requesting allocation of a datum for transferring an initial one of those multiple information packets to the other of said processing groups and for responding to later received ones of those multiple information packets by generating a signal indicating that a responding processing cell is busy.

31. An apparatus according to claim 30, wherein the processing cells that generated said later received ones of those multiple information packets include means for selectively copying a datum included in a packet responding to said initial one of those multiple information packets.

32. An apparatus according to claim 30, wherein said multiple request-handling means includes at least one of

A. means selectively responsive to receipt, from processing cells in any of said first and second processing groups, of multiple information packets requesting read-only allocation of a datum for transferring an initial one of those multiple information packets to the other of said processing groups and for responding to later received ones of those multiple information packets by generating a signal indicating that a responding processing cell is busy, and

B. means selectively responsive to receipt, from processing cells of any of said first and second processing groups, of one or more information packets requesting ownership allocation or invalidation of a datum for transferring those packets to the other of said processing groups.

33. An apparatus according to claim 30, wherein said multiple request-handling means includes at least one of

A. means selectively responsive to receipt, from processing cells of any of said first and second processing groups, of multiple information packets requesting read-only allocation of a datum for transferring an initial one of those multiple information packets to the other of said processing groups and for responding to later received ones of those multiple information packets by generating a signal indicating that a responding processing cell is busy,

B. means selectively responsive to receipt, from processing cells of any of said first and second processing groups, of multiple information packets requesting exclusive ownership of a datum for transferring an initial one of those multiple information packets to the other of said processing groups and for responding to later received ones of those multiple information packets by generating a signal indicating that a responding processing cell is busy,

C. means selectively responsive to receipt, from processing cells of any of said first and second processing groups, of multiple information packets requesting, without wait, atomic ownership of a datum for transferring an initial one of those multiple information packets to the other of said processing groups and for responding to later received ones of those multiple information packets by generating a signal indicating that the requested datum is atomically owned,

D. means selectively responsive to receipt, from processing cells of any of said first and second processing groups, of multiple information packets requesting, with wait, atomic ownership of a datum for an initial one of those multiple information packets to the other of said processing groups and for responding to subsequently received ones of those multiple information packets, as well as to subsequently received packets requesting atomic ownership without wait, by indicating that the requested datum is atomically owned, and

E. reissue means selectively responsive to receipt of an information packet requesting a datum, a response to which packet was not routed to the processing cell which issued that packet, and which information packet was previously issued by the first level transfer means associated with said multiple request-handling means, for generating a signal indicating that a responding processing cell is busy.

34. An apparatus according to claim 4 or 8 or 12 or 15, wherein said first level transfer means includes

A. multiple request-handling means selectively responsive to receipt, for processing cells of any of said first and second processing groups, of multiple information packets requesting allocation of a datum for transferring an initial one of those multiple information packets to the other of said processing groups and for deleting later issued ones of those multiple information packets, and

B. said multiple request-handling means including merge means for associating a merged-state signal with a datum generated in response to said initial one of those multiple packets and for which datum such later issued ones of those multiple information packets have been deleted.

35. An apparatus according to claim 34, wherein said first level transfer means includes means for responding to a response packet including a datum associated with said merged-state signal for including in that packet a merged-response signal for preventing at least the processing cell which issued the initial one of said multiple information packets from deleting that response packet.

36. An apparatus according to claim 35, wherein each of said processing cells includes means responsive to a packet including said merged-response signal for generating a copy of that packet for use by that processing cell and for passing that packet to others of said processing cells.

37. An apparatus according to claim 34, wherein

A. said first level transfer means includes means responsive to multiple information packets requesting allocation of a datum in a like access state for transferring at least an initial one of those multiple information packets to said other processing group and for deleting later issued ones of those multiple information packets, and

B. said multiple request-handling means including merge means for associating a merged-state signal with a datum generated in response to said initial one of those multiple packets and for which datum such later issued ones of such like requests have been deleted.

49. An apparatus according to claim 4 or 8 or 12 or 15, wherein

A. at least a first processing cell includes means for storing allocation state-defining information associated with at least selected data, or copies thereof, allocated thereto, said allocation state-defining information including at least

i) an atomic ownership state for a datum allocated for priority exclusive access in said first processing cell which another processing cell has not requested to have allocated,

ii) a transient atomic ownership state for a datum allocated for priority exclusive access in said first processing cell which another processing cell has requested to have allocated, and

B. the CCU means of said first processing cell includes

i) means responsive to a request from others of said processing cells for allocation of a datum associated with either of said atomic ownership or transient atomic ownership states for preventing allocation of that datum, or copy thereof, by such requesting processing cells,

ii) means responsive to a request from an atomic-requesting one of said other processing cells for priority exclusive allocation of datum associated with said atomic ownership state in said first processing cell for associating that datum with said transient atomic ownership state.

50. An apparatus according to claim 49, wherein said CCU means of said first processing cell includes atomic-transaction termination means for

i) associating a datum previously associated with said atomic ownership state with an exclusive ownership state and, thereby, re-enabling response to subsequent requests from others of said processing cells for allocation of that datum, or a copy thereof,

ii) selectively generating a release information packet including a datum associated with said transient atomic ownership state and transferring that packet on the associated bus means.

51. An apparatus according to claim 50, wherein said atomic-requesting processing cell includes means responsive to said release packet for allocating the datum included therein.

52. An apparatus according to claim 50, wherein said first processing cell includes

means responsive to receipt of said release packet subsequent to initial generation and transfer thereof on said associated bus means for associating the datum included therein with an exclusive ownership state and, thereby, re-enabling response to subsequent requests from others of said processing cells for allocation of that datum, or a copy thereof.

53. An apparatus according to claim 4 or 8 or 12 or 15, wherein

A. the CCU means of at least one of said processing cells includes means for generating a duplicate data information packet including a copy of a datum allocated to that processing cell, as well as the descriptor corresponding to that datum, and for transferring that packet to the bus means of the processing group with which that processing cell is associated, and

B. the CCU means of at least one other of said processing cells includes means responsive to that duplicate data packet for selectively updating a copy of said datum allocated, if at all, to that other processing cell.

54. An apparatus according to claim 53, wherein said first level transfer means includes duplicate data means responsive to a first duplicate data packet received on the bus means associated with said first processing group for generating a second duplicate data packet including a copy of the datum in said initial duplicate data packet, as well as the descriptor corresponding to that datum, and for transferring that second duplicate data packet to said second processing group, and for passing said first duplicate data packet to said first processing group.

55. An apparatus according to claim 53, wherein said first level transfer means includes duplicate data means responsive to a first duplicate data packet received on the bus means associated said second processing group including a copy of a datum allocated in a selected access state to a processing cell in said first processing group for generating a second duplicate data packet including a copy of the datum in said initial duplicate data packet, as well as the descriptor corresponding to that datum, and for transferring that second duplicate data packet to said first processing group, and for passing said first duplicate data packet to said second processing group.

56. An apparatus according to claim 55, wherein said duplicate data means includes means responsive to a first duplicate data packet received on the bus means of said second processing group including a copy of a datum for which at least one of

i) a read-only request has been generated by a processing cell in said first processing groups, and

ii) an invalid copy is allocated to a processing cell in said first processing group,

for generating said second duplicate data packet.

57. An apparatus according to claim 4 or 8 or 12 or 15, wherein said routing control means includes means responsive to receipt of an information packet from the bus means associated with any of said first and second processing groups, said packet including a datum or copy thereof for which a request has been generated by a processing cell in the other of said processing groups, for routing to that other processing group an information packet including that datum or copy thereof.

58. An apparatus according to claim 57, wherein said routing control means includes means responsive to receipt of an information packet from the bus means associated with any of said first and second processing groups, said packet including a datum or copy thereof for which a request has been generated by a processing cell in the other of said processing groups, said packet further including a requester-ID signal uniquely identifying that requesting processing cell, for routing to that other processing group that information packet.

59. An apparatus according to claim 57, wherein said routing control means includes snarf means selectively responsive to receipt of an information packet from the bus means associated with said second processing group, said packet including a datum or copy thereof for which at least one of

i) a read-only request has been generated by a processing cell in said first processing groups, and

ii) an invalid copy is allocated to a processing cell in said first processing group,

for generating a duplicate data packet including a copy of that datum and for transferring that duplicate data packet to said first processing group.

60. An apparatus according to claim 57, wherein said routing control means includes snarf means selectively responsive to receipt of an information packet from the bus means associated with said second processing group, said packet including a datum or copy thereof for which any of an ownership request and atomic request has been generated within said first processing group for routing that information packet to said first processing group.

61. An apparatus according to claim 4 or 8 or 12 or 15, wherein

A. a processing cell in said first processing group includes means for generating a recombine information packet including a datum subject to allocation in another of said processing cells, and for transferring that recombine packet to the bus means associated with said first processing group, and

B. at least one of said other processing cells in said first and second processing groups includes recombine means for selectively allocating the datum in said recombine packet.

62. An apparatus according to claim 61, wherein said first level transfer means includes

A. polling means for determining whether any of the other processing cells in said first processing group will allocate the datum in said recombine packet prior to transferring that packet to said second processing group, and

B. said polling means including means for transferring said recombine packet to said other processing cell in said first processing group on the bus means associated with that group.

63. An apparatus according to claim 62, wherein said first level transfer means includes means responsive to the failure of any of said other processing cells in said first processing group to allocate the datum in said recombine packet to transfer that packet to said second processing group.

64. An apparatus according to claim 63, wherein said routing control means includes means responsive to a recombine packet received on the bus means of said second processing group, said packet including a datum a copy of which is allocated to said first processing group, for routing that recombine packet to said first processing group for emptying by the cell that generated said recombine packet.

13. A digital data communications apparatus comprising

A. (n) packet transfer levels, each respectively designated level(k), where (k) represents successive integers between (0) and (n-1), inclusive,

B. each packet transfer level including a plurality of segments, where the number of segments in each packet transfer level(k), except packet transfer level(0), is less than the number of segments in packet transfer level(k-1), and where packet transfer level(n-1) includes only one such segment, each segment including

i) zero, one or more processing cells, each having

zero, one or more data, or copies thereof, allocated thereto, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

CCU means for at least one of generating and receiving signals representative of an information packet including a descriptor of a datum subject to reference,

wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that processing cell,

ii) bus means for carrying information packets within that segment,

C. each segment of packet transfer level(k), for (k) between (1) and (n-1), inclusive, being referred to as a level(k) segment and including plural first level transfer means for selectively transferring information packets between that level(k) segment and one or more level(k-1) segments associated therewith, said first level transfer means including

first input means, coupled to the bus means of that level(k) segment, for receiving an information packet therefrom,

first output means, also coupled to the bus means of that level(k) segment, for selectively outputting an information packet thereto,

second input means, coupled to the bus means of an associated level(k-1) segment, for receiving an information packet thereto,

second output means, coupled to the bus means of that associated level(k-1) segment, for selectively outputting an information packet thereto,

where each such associated level(k-1) segment, as well as each descendant thereof, if any, is termed a descendant of that level(k) segment, where the processing cells associated with descendants of a level(k) segment are referred to as a first group of processing cells and said processing cells other than those associated with a descendant of a level(k) segment are referred to as a second group of processing cells, and

D. at least one said first level transfer means including routing control means, connected to said first and second input means and to said first and second output means, for routing an information packet received by any of those input means to a selected one of those output means based upon correspondence between the descriptor in that information packet and data allocated to one or more processing cells of the first processing group.

14. An apparatus according to claim 13, wherein said routing control means includes directory means for storing signals representative of data allocated to said first processing group.

15. An apparatus according to claim 14, wherein said routing control means includes means coupled to said directory means for comparing a descriptor in a packet received at said first input means with said directory signals to determine which of said first and second output means to route that packet to.

26. An apparatus according to claim 4 or 8 or 15, wherein at least a processing cell in said first processing group includes means for deallocating from the associated directory means a signal representative of an invalid datum, or copy thereof, for which physical storage space is allocated within that processing cell, and for transferring to the bus means associated with that first processing group a deallocate packet including the descriptor of that datum.

27. An apparatus according to claim 26, wherein said first level transfer means includes polling means responsive to said deallocate packet for determining whether any other processing cells of said first processing group have allocated thereto the datum, or copy thereof, associated with the descriptor in that deallocate packet.

28. An apparatus according to claim 27, wherein

A. said polling means includes means for transferring said deallocate packet on the bus means of said first processing group, and

B. the processing cells of said first processing group include means for generating a busy signal indicating that they have allocated thereto the datum, or a copy thereof, associated with the descriptor in that deallocate packet.

29. An apparatus according to claim 28, wherein said polling means includes means responsive to an absence of said busy signal upon subsequent receipt of said deallocate packet for deallocating from that directory means said signal representative of the datum, or copy thereof, associated with the descriptor in that deallocate packet.

38. An apparatus according to claim 4 or 8 or 15, wherein the CCU means of at least a requesting one of said processing cells includes

A. request means for generating an ownership request information packet representative of a request for ownership allocation of a datum, and

B. routing control means for selectively transferring that packet to the bus means of the processing group with which that processing cell is associated.

39. An apparatus according to claim 38, wherein the CCU means of at least a responding processing cell includes

A. response means for generating an ownership response information packet representative of a response to said ownership request packet, said response packet including the datum for which ownership allocation is requested, and

B. means for transferring that packet to the bus means of the processing group with which the responding processing cell is associated.

40. An apparatus according to claim 39, wherein

A. the CCU means of the requesting processing cell includes means responsive to said response packet for allocating physical storage space for the datum in that packet in the associated processing cell, and

B. the CCU means of the responding processing cell includes means for deallocating the requested datum from the responding processing unit.

41. An apparatus according to claim 39, wherein

A. said request means includes means for generating a request packet having a requester-ID field representative of an identification of the processing cell generating that request packet,

B. said response means includes means for generating a response packet having the requester-ID field of the request packet for which it represents a response, and

C. said routing control means includes means responsive to the requester-ID field of a response packet for routing that response packet to a processing group in which the processing cell that generated the request was generated.

42. An apparatus according to claim 4 or 8 or 15, wherein

the CCU means of at least a requesting one of said processing cells includes request means for generating an ownership request information packet representative of a request for ownership allocation of a datum, and for transferring that packet to the bus means of the processing group with which that requesting processing cell is associated.

43. An apparatus according to claim 42, wherein the CCU means of at least a responding one of said processing cells includes response means for generating an ownership response information packet representative of a response to said ownership request packet, said response packet including the datum for which ownership allocation is requested, and for transferring that packet to the bus means of the processing group with which the responding processing cell is associated.

44. An apparatus according to claim 43, wherein the CCU means of the requesting processing cell includes means responsive to said ownership response packet for allocating within that processing cell physical storage space for the requested datum.

45. An apparatus according to claim 44, wherein the CCU means of the responding processing cell includes means for deallocating physical storage space previously allocated to the requested datum within the responding processing cell.

46. An apparatus according to claim 45, wherein said directory means includes means for storing signals representative of descriptors of at least one of

i) data, or copies thereof, allocated to processing cells in said first processing group,

ii) datum for which a request packet generated by a processing cell in said second processing group has been routed to said first processing group, and

iii) datum for which a request packet generated by a processing cell in said first processing group has been routed to said second processing group.

47. An apparatus according to claim 46, wherein said routing control means includes

i) routing directory unit means coupled to said directory means for comparing a descriptor of a request packet generated in the first processing group with said directory means to determine whether the datum corresponding to that descriptor is allocated to one or more processing cells of said first processing group, and

ii) means responsive to a determination that the datum corresponding to that descriptor is not allocated to said first processing group for routing that request packet to said second processing group, and updating said directory means accordingly.

48. An apparatus according to claim 46, wherein said routing control means includes

i) routing directory unit means coupled to said directory means for comparing a descriptor of a request packet generated in the second processing group with said directory means to determine whether the datum corresponding to that descriptor is allocated to said first processing group, and

ii) means responsive to a determination that the datum corresponding to that descriptor is allocated to said first processing group for routing that request packet to said first processing group, and updating said directory means accordingly.

71. A digital data communications apparatus comprising

A. (n) packet transfer levels, each respectively designated level(k), where (k) represents successive integers between (0) and (n-1), inclusive,

B. each packet transfer level including a plurality of segments, where the number of segments in each packet transfer level(k), except packet transfer level(0), is less than the number of segments in packet transfer level (k-1), and where packet transfer level(n-1) includes only one such segment, each segment including

i) zero, one or more processing cells, each having zero, one or more data, or copies thereof, allocated thereto, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

each processing cell further having means for generating a signal representative of an information packet, said information packet including one of at least a request packet having a descriptor corresponding to a datum to be allocated, and a response packet comprising a response to a request packet,

ii) bus means for carrying information packets within that level(k) segment,

C. CCU means coupled to said processing cells for selectively deallocating a datum allocated to a first cell and concurrently allocating that datum exclusively to a second cell,

D. each level(k) segment, for (k) between (1) and (n-1), inclusive, including plural routing cells, each connected to the bus means of that segment and to the bus means of an associated level(k-1) segment for selectively transferring information packets between those segments, where each such associated level(k-1) segment, as well as each descendant thereof, is termed a descendant of that level(k) segment, and

E. each said routing cell including means for selecting a request packet for transfer between associated level(k) and level(k-1) segments based upon correspondence of the descriptor in that request packet and a datum allocated to a processing cell in a descendant of that level(k) segment.

72. A digital data communications apparatus according to claim 71, wherein said routing cell includes means for selecting for transfer from the associated level(k-1) segment to the associated level(k) segment a request packet, generated by a processing cell in a descendant of that level(k) segment, having a descriptor corresponding to a datum that is not allocated to a processing cell which is a descendant of that level(k) segment.

73. A digital data communications apparatus according to claim 71, wherein said routing cell includes means for selecting for transfer to the associated level(k-1) segment from the associated level(k) segment a request packet that was not generated by a processing cell in that level(k-1) segment, or a descendant thereof, and that includes a descriptor corresponding to a datum that is allocated within a processing cell in that level(k-1) segment, or a descendant thereof.

74. A digital data communications apparatus according to claim 72, wherein said routing cell includes means for selecting for transfer to the associated level(k-1) segment from the associated level(k) segment a response packet directed to a processing cell in that level(k-1) segment, or a descendant thereof.

75. A digital data communications apparatus according to claim 74, wherein said routing cell includes means for selecting for transfer from the associated level(k-1) segment to the associated level(k) segment a response packet directed to a processing cell that is not a descendant of that level(k-1) segment.

76. A digital data communications apparatus according to claim 73, wherein

A. the bus means of each said level(k) segment defines a unidirectional flow path for said information packets, and

B. each said routing cell includes interface means coupled to the bus means of the associated level(k) and level(k-1) segments for receiving a first information packet from an adjacent upstream portion of an associated bus means, and selectively executing at least one of the following operations:

i) transferring that first information packet unchanged to an adjacent downstream portion of that associated bus means

ii) modifying that first information packet and transferring it to an adjacent downstream portion of that associated bus means,

iii) copying that first information packet to create a second information packet, transferring the second information packet to an associated segment, and

iv) emptying that first information packet.

77. A digital data communications apparatus according to claim 76, wherein at least one of said bus means comprises a shift register ring.

78. A digital data communications apparatus according to claim 76, wherein each routing cell includes means for storing a directory of descriptors corresponding to data allocated to the processing cells, if any, in descendants of the associated level(k) segment.

79. A digital data communications apparatus according to claim 78, wherein each said routing cell includes means for comparing a descriptor of a request packet to said directory to determine whether the datum in that request packet is allocated to a processing cell in a descendant of the associated level(k) segment, or a descendant thereof.

80. An improved method for digital data communications comprising the steps of

A. providing first and second processing groups, each including a plurality of processing cells interconnected by an associated bus means for carrying information packet-representative signals,

each processing cell having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that same processing cell,

B. generating within one or more of said processing cells signals representative of information packets, each including a descriptor of a datum subject to reference, and selectively transferring one or more of those information packet-representative signal to the bus means associated with said one or more processing cells which generated them, and

C. selectively routing said information packets between the bus means associated with each of said first and second processing groups based upon prior routings, if any, of the data, or requests therefor, referenced by the descriptors in those packets between said first and second processing groups.

81. A method according to claim 80 further comprising the step of storing in a directory signals representative of prior routings of data, or requests therefor, between said first and second processing groups.

86. An method according to claims 81, 83 or 85, wherein said directory signal-storing step includes the further step of storing in said directory allocation state-defining information for at least selected data, or copies thereof, allocated to said first processing group, said allocation state-defining information including at least one of

i) an invalid allocation state for an invalid datum allocated to said first processing group,

ii) a read-only allocation state for a copy of a datum allocated to and subject to read-only access by a processing cell of said first processing group, no copy of which datum is modifiable by a processing cell of said first processing group,

iii) a nonexclusive owner allocation state for a datum allocated to and modifiable by a processing cell of said first processing group, one or more read-only copies of which datum are allocated to other processing cells of said first and second processing groups,

iv) an exclusive owner allocation state for a datum exclusively allocated to and modifiable by a processing cell of said first processing groups, no copies of which datum are allocated to other processing cells of said first and second processing groups.

87. A method according to claims 81, 83 or 85, wherein said directory signal storing step includes the steps of

A. storing in a first directory portion signals representative of descriptors corresponding to datum for which requests are pending to said first processing group from said second processing group, and

B. storing in a second directory portion signals representative of descriptors corresponding to data for which requests are pending to said second processing group from said first processing group.

88. A method according to claims 81, 83 or 85, including the further steps of

A. deallocating a directory signal representative of an invalid datum, or copy thereof, for which physical storage space is allocated within a processing cell, and transferring in conjunction therewith a deallocate packet including the descriptor of that invalid datum, and

B. responding to said deallocate packet for deallocating directory signals representative of the datum, or copy thereof, associated with the descriptor in that deallocate packet.

89. A method according to claims 81, 83 or 85, including the step of responding to receipt, from processing cells in any of said first and second processing groups, of multiple information packets requesting allocation of a datum for transferring an initial one of said request packets to the other of said processing groups and for responding to later received ones of such request packets by generating a signal indicating that a responding processing cell is busy.

90. A method according to claims 81, 83 or 85, including the further steps of

A. responding, selectively, to receipt from processing cells of any of said first and second processing groups of multiple information packets requesting allocation of a datum for transferring an initial one of said multiple information packets to the other of said processing groups and for deleting later issued ones of said multiple information packets, and

B. associating a merged-state signal with a datum generated in response to said initial one of those multiple packets and for which such later issued ones of said multiple information packets have been deleted.

91. A method according to claim 81, 83 or 85, including the further steps of

A. generating within one of said processing cells an ownership request information packet representative of a request for ownership allocation of a datum,

B. transferring that packet to the bus of the processing group with which that processing cell is associated,

C. responding, within another of said processing cells, to said ownership request packet by generating a response packet including the datum for which ownership allocation is requested, and

D. transferring that ownership response packet to the bus means of the processing group with which the responding processing cell is associated.

92. A method according to claims 81, 83 or 85, including the further steps of

A. storing in at least a first processing cell allocation state-defining information associated with at least selected data, or copies thereof, allocated thereto, said allocation state-defining information including at least

i) an atomic ownership state for a datum allocated for priority exclusive access in said first processing cell which another processing cell has not requested to have allocated,

ii) a transient atomic ownership state for a datum allocated for priority exclusive access in said first processing cell which another processing cell has requested to have allocated, and

B. responding to a request from others of said processing cells for allocation of a datum associated with either of said atomic ownership or transient atomic ownership states for preventing allocation of that datum, or copy thereof, by such requesting processing cells,

C. responding to a request from an atomic-requesting one of said other processing cells for priority exclusive allocation of a datum associated with said atomic ownership state in said first processing cell for associating that datum with said transient atomic ownership state.

93. A method according to claims 81, 83 or 85, including the further steps of

A. generating in at least one of said processing cells a duplicate data information packet including a copy of a datum allocated to that processing cell, as well as the descriptor corresponding to that datum, and transferring that packet to the bus means of the processing group with which that processing cell is associated, and

B. responding, with at least one other of said processing cells, to that duplicate data packet for selectively updating a copy of said datum allocated, if at all, to that other processing cell.

94. A method according to claims 81, 83 or 85, including the further steps of responding to receipt of an information packet from the bus associated with any of said first and second processing groups, said packet including a datum or copy thereof for which a request has been generated by a processing cell in the other of said processing groups, for routing to that other processing group an information packet including that datum or copy thereof.

95. A method according to claims 81, 83 or 85, including the further steps of

A. generating, in a processing cell in said first processing group, a recombine information packet including a datum subject to allocation in another of said processing cells, and transferring that recombine packet to the bus means associated with said first processing group, and

B. selectively allocating, within at least one of said other processing cells in said first and second processing groups, the datum in said recombine packet.

96. A method according to claims 81, 83 or 85, including the further steps of

A. providing in said second processing group third and fourth processing groups, each including a plurality of said processing cells interconnected by an associated bus means for carrying information packet-representative signals,

each processing cell having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data_-- to that same processing cell,

B. generating within one or more of said processing cells of said third and forth processing groups signals representative of information packets, each including a descriptor of a datum subject to reference,

C. providing a ring-one bus for interconnecting said first, third and fourth processing groups, and

D. selectively transferring information packets between the respective busses of each of said first, third and fourth buses.

97. A method according to claims 81, 83 or 85, comprising the further steps of

A. disposing said first and second processing groups at locations physically remote from one another, and

B. selectively transferring an information packet received from one of said processing groups to the other, physically remote processing group.

98. A method according to claims 81, 83 or 85, including the steps of

A. providing within said second processing group a plurality of further processing groups, each including a plurality of processing cells connected by an associated bus for transferring information packets therebetween, and

B. selectively transferring information packets between said further processing groups and said first processing group.

82. An improved method for digital data communications comprising the steps of

A. providing first and second processing groups, each including a plurality of processing cells interconnected by an associated bus means for carrying information packet-representative signals,

each processing cell having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that same processing cell,

B. generating within one or more of said processing cells signals representative of information packets, each including a descriptor of a datum subject to reference, and selectively transferring one or more of those information packet-representative signal to the bus means associated with said one or more processing cells which generated them, and

C. selectively routing said information packets between the bus means associated with each of said first and second processing groups based upon correspondence between the descriptor in that information packet and the data allocated to, or requested for allocation by, one or more processing cells of said first processing group.

83. A method according to claim 82 further comprising the step of storing in a directory signals representative of data allocated to, or requested for allocation by, said first processing group.

84. An improved method of digital information packet switching comprising the steps of

A. receiving an information packet from a first processing group including a plurality of processing cells interconnected by an associated bus means for carrying information packet-representative signals,

each processing cell having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that same processing cell, and

B. selectively routing said information packet to a respective one of said first processing group and a second processing group based upon correspondence between the descriptor in that information packet and the datum allocated to one or more processing cells of said first processing group,

said second processing group including a plurality of processing cells interconnected by an associated bus means for carrying information packet-representative signals,

each processing cell having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of that corresponding datum with respect to other data, if any, allocated to that same processing cell.

85. A method according to claim 84 further comprising the step of storing in a directory signals representative of data or copies thereof routed between said first and second processing groups.

99. A digital data communications apparatus comprising,

A. first and second processing groups, each said group including a plurality of processing cells, the processing cells within each of said processing groups being connected by an associated bus means for transferring signals representative of information packets therebetween, each processing cell

i) having allocated thereto zero, one or more data or copies thereof, each such datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,

ii) including CCU means for at least one of generating and receiving signals representative of an information packet including a descriptor of a datum or copy subject to reference,

B. first level transfer means for transferring information packets between said first and second processing groups, said first level transfer means including,

first input means, coupled to the bus means of said first processing group, for receiving an information packet therefrom,

first output means, coupled to the bus means of said first processing group, for selectively outputting an information packet thereto,

second output means, coupled to the bus means of said second processing group, for selectively outputting an information packet thereto,

C. said first level transfer means including routing control means, connected to said first input means and to said first and second output means,

said routing means including directory means for storing signals representative of descriptors corresponding with at least selected data or copies thereof allocated to said first processing group, said routing means providing for routing an information packet received on said first input means to a selected one of first and second output means based upon correspondence between a descriptor referenced in that information packet and a signal representative of that descriptor in said directory means.