Multiprocessor intercommunication system and method

• US 4,412,285 A
• Filed: 04/01/1981
• Issued: 10/25/1983
• Est. Priority Date: 04/01/1981
• Status: Expired due to Term

• Current Assignee: NCR Corporation
• Original Assignee: Teradata Corporation
• Inventors: Hartke, David H., Neches, Philip M., Stockton, Richard C., Cronshaw, David, Shemer, Jack E., Watson, Martin C.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/250,022
• Time in Patent Office: 937 Days
• Field of Search: 364/200 MS File
• US Class Current: 709/252
• CPC Class Codes: G06F 15/17368 non hierarchical topologies
• CPC Class Codes: H04L 69/00 Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass networks security protocols H04L9/40; wireless communication networks H04W

Abstract

A system using a sorting network to intercouple multiple processors so as to distribute priority messages to all processors is characterized by semaphore means accessible to both the local processors and the global resource via the network. Transaction numbers identifying tasks are employed in the messages, and interfaces at each processor are locally controlled to establish transaction number related indications of the current status of each task being undertaken at the associated processor. A single query to all processors via the network elicits a prioritized response that denotes the global status as to that task. The transaction numbers also are used as global commands and local controls for the flow of messages. A destination selection system based on words in the messages is used as the basis for local acceptance or rejection of messages. This arrangement together with the transaction number system provides great flexibility as to intercommunication and control.

Claims

1. A multiprocessor system comprising:

a plurality of processor modules, each including means for providing externally accessible semaphores evidencing readiness states of the procesor as to different transactions;

network means coupled to the processor modules for conducting a "test and set" operation as to the readiness states of the processors relating to a given transaction simultaneously in all processors, and selecting the least ready state as an indication of global readiness.

2. The system as set forth in claim 1 above, wherein said means for providing semaphores comprises means for providing one of a range of values for each different transaction.

3. The system as set forth in claim 2 above, wherein said means for providing one of a range of values provides values of varying data content, and wherein said means for selecting the least ready state comprises means in said network means for merging the values in accordance with data content.

4. The system as set forth in claim 3 above, wherein said network means comprises a bidirectional network including means for broadcasting messages to all processor modules concurrently and means for merging messages from the processor modules within a predetermined fixed time interval.

5. The system as set forth in claim 4 above, wherein said plurality of processor modules include means for applying messages to the network means concurrently, the messages including primary data messages, semaphore queries and semaphore responses.

6. The system as set forth in claim 5 above, wherein the messages further include control messages and responses to primary data messages, and wherein all messages have data contents varying in accordance with a predetermined priority protocol.

7. The system as set forth in claim 6 above, wherein all messages have an initial command field having varying data content in accordance with the sorting priority for the message type.

8. The system as set forth in claim 7 above, wherein primary data messages, status and control messages include transaction numbers of varying data content, and said plurality of processor modules each include buffer means for storing and locally updating semaphores in externally accessible form in accordance with each transaction number.

9. The system as set forth in claim 8 above, wherein the transaction numbers comprise addresses for semaphore locations in the buffer means such that the buffer means may be addressed directly by transaction number to derive the semaphore value.

10. The system as set forth in claim 7 above, wherein the messages include destination selection information, and said plurality of processor modules include means for determining whether the processor module is to utilize the message, based upon the destination selection information.

11. The system as set forth in claim 10 above, wherein the destination selection information is a destination selection word of fixed length.

12. The system as set forth in claim 11 above, wherein said plurality of processor modules comprise memory means having a dedicated section and means for comparing the destination selection word to the contents of the dedicated memory section to determine if the message is appropriate for the processor module.

13. The system as set forth in claim 12 above, wherein the dedicated memory section comprises buffer means having destination selection data identifying the message as appropriate for the processor module specifically, or as one of a class of processor modules, or in accordance with a hashing function.

14. The system as set forth in claim 13 above, wherein the dedicated memory section comprises buffer means having portions corresponding to individual processor selection, class of processor selection, and hashing function selection, and the means for comparing comprises means for addressing the dedicated memory section in accordance with the destination selection word, and comparing the output of the addressed portion of the dedicated memory section to at least a portion of the destination selection word.

15. The system as set forth in claim 14 above, wherein the destination selection word comprises a map address, and a map selection code and wherein the dedicated memory section comprises a number of portions each addressed in parallel by the map address of the destination selection word, and the means for comparing comprises means responsive to the map selection code for selecting one of the outputs from the dedicated memory section, and means for comparing that output to the corresponding map code.

16. The system as set forth in claim 7 above, wherin primary data messages are of variable length, and include a code identifying end of message.

17. The system as set forth in claim 7 above, wherein primary data messages, status, control and response messages include tag following the command field, the tag having varying data content and being of fixed length and comprising an originating processor identification for responses.

18. The system as set forth in claim 17 above, wherein the combination of command field and tag characterize the message as a status query, an assigned transaction number control message, a relinquish transaction control message or a start or stop processor module merge control message.

19. The system as set forth in claim 18 above, wherein a predetermined one of the tags identifies the nonmerge state to the processor modules.

20. The system as set forth in claim 19 above, wherein the messages further comprise a fixed length destination selection word of varying data content and means at each processor module for identifying, from the destination selection word, whether a message is intended for the particular processor module.

21. The system as set forth in claim 20 above, wherein said plurality of processor modules each include means storing a number of reference values and responsive to the destination selection word for determining, from the destination selection word, whether the processor module is being addressed individually, is one of a class of addressed processor modules, or is being addressed in accordance with a hashing function.

22. The system as set forth in claim 21 above, wherein said plurality of processor modules each generate messages containing destination selection words and tags in the form of transaction numbers, such that any of the processor modules, using variations of the command field, transaction number and destination selection word can coordinate via the network means with all the other processor modules.

23. The system as set forth in claim 22 above, wherein the combination of command field, transaction number and destination selection word define a plurality of multiprocessor intercommunications, including task assignments, distributed updates, and coordinated merging of processed subtasks.

24. The system as set forth in claim 23 above, wherein said plurality of processor modules include means for varying the transaction numbers in the commands, means responsive to a specific transaction number and a non-merge command and means providing start merge commands, such that global merges and broadcast modes can be intermingled as to different tasks, to enable global coordination of system resources.

25. The system as set forth in claim 24 above, wherein the primary data messages further comprise key fields of varying data content as further merge criteria.

26. The system as set forth in claim 25 above, wherein the messages comprise serial byte sequences, and the bytes include control bits whose serial patterns define fields, transitions between fields and the end of message.

27. The system as set forth in claim 7 above, wherein the messages further comprise a fixed length transaction number for primary data messages, status and control messages, and an originating processor identification for responses, and are arranged in serial byte sequences, with the bytes including control bits whose sequence identifies different fields within the messages, such that the network merges messages including responses using the transaction number and originating processor identification where other criteria do not permit a merge determination.

28. The system as set forth in claim 27 above, wherein primary data messages further comprise destination selection words having a map address portion and a map code selection portion, and an end of message section characterized by a selected pattern of control bits.

29. The system as set forth in claim 28 above, wherein the command field data contents are arranged in accordance with a selected priority protocol covering all message types.

30. The system as set forth in claim 7 above, wherein each processor module includes message and semaphore buffer means, including means for accessing both to the network means and the processor module.

31. The system as set forth in claim 30 above, wherein said message and semaphore buffer means comprises means for storing a plurality of semaphore status indications in accordance with transaction numbers, and the processor module includes means coupled to the buffer means for locally updating the semaphore status in relation to transaction numbers, and the buffer means further comprises means for reading out semaphore status in response to a global transaction number status query without reference to the then current operation of the processor module.

32. The system as set forth in claim 31 above, wherein said message and semaphore buffer means further comprises table lookup means providing different processor references, and wherein the messages include destination selection information, and the buffer means includes means for addressing the table lookup means directly in response to the destination selection information for determining whether the processor module is selected for operation with respect to the message.

33. The system as set forth in claim 32 above, wherein said message and semaphore buffer means comprises a circular input buffer section for receiving messages from the network means and providing messages to the processor module on a first in, first out basis.

34. The system as set forth in claim 33 above, wherein the buffer means comprises an output buffer section for receiving messages from the processor module and providing them to the network means, and a circular output message complete vector buffer section for storing information as to the locations from the procesor module in which output messages are sent, and means coupled to said buffer means for sequencing output messages.

35. The system as set forth in claim 34 above, wherein the messages further include fixed length transaction number and destination selection words, and wherein the buffer means comprises dedicated transaction number and destination selection word portions, and means for addressing the dedicated memory portions directly using at least portions of the transaction number and destination selection word.

36. The system as set forth in claim 7 above, wherein the system includes means for transmitting, between messages, lowest priority idle signals.

37. The system as set forth in claim 36 above, wherein said plurality of processor modules include means responsive to the idle signals and the last prior transmission for initiating subsequent transmissions after a delay greater than the time of transmission through the network.

38. The system as set forth in claim 36 above, wherein the bidirectional network comprises a plurality of active circuit nodes, each including means for controlling transfer of messages therethrough, and means for resetting the node following the end of a message transmission.

39. The system as set forth in claim 38 above, wherein the nodes further include means for indicating collisions between competing messages and means for transferring the collision indications along the network.

40. The system as set forth in claim 7 above, wherein the messages comprise serial bytes of data including parity bits, the processor modules include means for forcing a parity error upon a change in status, and the network means comprises a plurality of nodes each including means for propagating the forced parity error once through the network to note a change in status of global resources of the system.

41. The method of intercommunication between processors in a multiprocessor system comprising the steps of:

maintaining locally updated semaphores as to readiness states at each processor;

globally testing the local semaphores simultaneously to provide competing responses; and

selecting the state evidencing least readiness as the global state from the competing responses.

42. The method as set forth in claim 41 above, wherein the state evidencing least readiness is selected by dynamically prioritizing the competing responses within a predetermined fixed time interval.

43. The method as set forth in claim 42 above, wherein the competing responses have different data contents in accordance with readiness state and the responses are prioritized by successive multiple pair comparisons for data content.

44. The method as set forth in claim 43 above, including in addition the steps of maintaining locally updated semaphores as to a plurality of differently identified transactions at each processor, and testing the local semaphores for a specific identified transaction by a distributed global status communication.

45. The method as set forth in claim 44 above, wherein the readiness states include a non-participating state, such that different processor subsets can participate in a given transaction and responses from other processors are excluded as being of lower priority.

46. The method as set forth in claim 45 above, including the step of directing different modes of multiprocessor operation by distributing a global command pertaining to an identified transaction.

47. The method as set forth in claim 46 above, wherein the global commands identify suspension and resumption of operations as to a particular identified transaction.

48. The method as set forth in claim 46 above, wherein a specific value of transaction identification represents the non-merge mode of operation.

49. The method as set forth in claim 46 above, including the steps of time sharing of the multiprocessor system between tasks by identifying tasks to be shared by different transaction numbers, determining the global state of readiness of the system as to a given transaction number, and proceeding to a different appropriate transaction number if the global readiness state is not yet complete as to the prior transaction number.

50. The method as set forth in claim 49 above, wherein the multiprocessor system is a data base management system and the method further includes the steps of maintaining the transaction number reference throughout processing of a given task.

51. The method as set forth in claim 50 above, wherein the data base management system includes data distributed in disjoint subsets upon which the processors operate asynchronously, and the method includes the step of maintaining primary and backup subsets in different mutually exclusive distributions.

52. The method as set forth in claim 41 above, including in addition the step of distributing concurrently to the processors, with the global testing, a selection value controlling the category of processor response.

53. The method as set forth in claim 52 above, wherein the distributed selection values identify a broadcast mode, a processor communication, or a specific class of recipient processors, and wherein the method further includes the step of comparing distributed selection values to stored reference values at each processor.

54. The method as set forth in claim 53 above, wherein the system has data distributed in accordance with hash maps and the method comprises the further step of using the selection value as a hashing value in identification or recipient processor in accordance with the data distributed thereto.

55. The method as set forth in claim 41 above, wherein the local semaphores have different data contents, and the step of selecting the state evidencing least readiness comprises dynamically prioritizing the competing responses in accordance with data content within a predetermined fixed time interval.

56. The method as set forth in claim 55 above, further comprising the step of maintaining locally updated semaphore status for each of a number of transactions at each processor, and broadcasting a status query as to a given transaction concurrently to all processors for deriving concurrent responses.

57. The method as set forth in claim 56 above, further including the step of prioritizing the responses within a fixed number of time frames by making binary pair comparisons.

58. The method as set forth in claim 57 above, further comprising the steps of repeatedly attempting transmissions from processors having available messages and prioritizing the competing transmissions to derive a single or common priority transmission, wherein the messages include a pair of reference entries for at least data messages and comprising transaction identity and destination selection entries, and the further steps of using the transaction identity to define the task and the destination selection entry to define the processor subset for accomplishing the task, such that all processors have equal access to each other and any can be the coordinator for a system task.

59. The method as set forth in claim 58 above, further including the steps of accepting or rejecting message transmissions at local processors based upon the transaction identity entry and the destination selection entry to control the multiprocessor mode of operation.

60. The method as set forth in claim 59 above, further including the step of providing a directory of transaction readiness states at each processor, entering the transaction readiness states in an accessible file to denote the readiness states as to given transaction identities, and globally querying the local readiness states simultaneously without modification of the readiness states.

61. The method as set forth in claim 60 above, wherein each processor includes a library of potential transaction identities, and the method further comprises the steps of assigning transaction identities to tasks, identifying processors to perform the task by destination selection entries, performing the task by reference to the transaction identity, and commanding the relinquishment of the transaction identity when the task is completed.

62. The method as set forth in claim 61 above, further including the step of coordinating message flows between processors by temporary storage of both accepted received messages and prepared send messages before transmission for prioritizing.

63. The method as set forth in claim 62 above, further including the steps of storing accepted received messages and transferring them in successive sequence to the associated processor, and receiving processed send messages from the processor and transmitting them in sequence.

64. A computing system for ascertaining the global status of a task being undertaken by individual processors performing subtasks related thereto, comprising:

locally controllable storage means at each of the processors for providing an externally accessible indication of readiness state as to the particular subtask; and

global test means intercoupling the processors and including means for broadcasting a status query to all the storage means concurrently and deriving, in a predetermined fixed time interval, the least ready status of the processors undertaking subtasks pertaining to the given task.

65. The system as set forth in claim 64 above, wherein the processors include means for storing the indication of readiness states as different ones of a group of digital values of different data content, and wherein the global test means comprises means for reading the digital values stored at the local storage means concurrently and merging the competing digital values in accordance with data content to derive the least ready state.

66. The system as set forth in claim 65 above, wherein the storage means at each processor includes interface means responsive to the processor associated therewith for locally updating the digital values in accordance with processor readiness for each of a plurality of transactions identified by transaction numbers and the global test means further includes network means for transmitting status queries characterized by command and transaction number data, the network means including means for prioritizing the queries in accordance with their data content.

67. An intercommunicating multiprocessor system whose global state of readiness as to any of a number of transactions can be ascertained within a predetermined fixed time interval comprising:

a plurality of processors, each including means for maintaining and updating local test and set semaphores pertaining to the different transactions;

network means coupled to each of the processors for providing transaction queries simultaneously to all processors and dynamically sorting concurrent responses within a fixed time interval; and

global test and set means coupling each of the processors to the network means for providing semaphore response transmissions concurrently to the network means.

68. The system as set forth in claim 67 above, wherein the semaphores have varying data contents dependent upon the local state of readiness, and the network means includes means for sorting in accordance with data content.

69. The system as set forth in claim 68 above, wherein the means for maintaining semaphores comprises random access storage means, and interface means coupling the storage means to the associated processor therewith and the network means, and wherein the semaphores are digital entries selected from a sorting sequence and stored at locations addressed by the transaction queries.

70. A computing system comprising:

a plurality of processor modules, each including means for locally establishing a semaphore as a digital value pertaining to different ones of a number of given transactions identified by different transaction numbers;

network means coupled to the processors for broadcasting concurrent messages to the processors, the messages including queries and commands identified by transaction numbers, the network means including means responsive to the concurrent messages for prioritizing the messages; and

a plurality of interface means coupled to the network means and associated with each processor module for providing digital semaphore values to the network means in response to a broadcast query, for prioritizing of such values to derive a single value.

71. The system as set forth in claim 70 above, wherein the means for locally establishing a semaphore includes means for providing a locally revisable, externally accessible semaphore for each of the different transaction numbers, and the interface means are responsive to the commands and include means for controlling the sequence of communications to the network means.

72. The system as set forth in claim 71 above, wherein the means for establishing semaphores comprises memory means for storing messages from and to the network means, and the interface means are responsive to the transaction numbers and commands for transmitting messages to the network means for prioritizing in merge and non-merge modes relative to particular transaction numbers.

73. The system as set forth in claim 71 above, wherein said means for providing semaphore states comprises storage means including a plurality of dedicated transaction number addresses, means for entering digital values representing semaphore values at the different addresses, and wherein the means for deriving semaphores comprises means for reading the storage means in response to transaction number addresses concurrently.

74. The system as set forth in claim 73 above, wherein the system further includes means for generating messages including present transaction numbers, and the means for reading the storage means are independent of the processors associated therewith, such that software and processor availability are not involved in the response.

75. A computing system having a plurality of processors and being capable of distributed asynchronous processing of multiple tasks and coordinated usage of task results, comprising:

a plurality of processors operating asynchronously but generating synchronous competing message transmissions, the messages including reference values of varying data content;

network means coupled to the processors and responsive to the data content of the competing messages for transferring a priority message to all processors;

a plurality of storage means, each associated with a different processor, for storing data relating to the reference values; and

a plurality of controller means coupled to the different storage means and responsive to the reference values and data relating thereto for controlling processor intercommunication via the network means.

76. The system as set forth in claim 75 above, wherein the reference values comprise transaction numbers and the storage means comprises a library of transaction number locations for storing digital values representing processor readiness as to tasks identified by particular transaction numbers.

77. The system as set forth in claim 76 above, including in addition means responsive to processor operation at each controller means for entering processor readiness values at each transaction number location, and means for accessing the readiness values via the network means.

78. The system as set forth in claim 77 above, wherein the readiness values have data contents varying in accordance with a predetermined priority protocol such that concurrent readiness values from a number of controller means are sorted to a priority status on the network means.

79. The system as set forth in claim 78 above, wherein a plurality of transaction numbers identify merge modes of operation and a single predetermined transaction number identifies a non-merge mode of operation.

80. The system as set forth in claim 75 above, wherein the storage means each include a dedicated memory section addressable by the reference values for generating related data.

81. The system as set froth in claim 76 above, wherein the reference values comprise destination selection words and the dedicated memory section comprises a file of destination section data.

82. The system as set forth in claim 81 above, wherein the controller means further comprises means responsive to the destination selection words for addressing the dedicated memory section, and means responsive to the related data derived from the memory section for comparing the values to determine whether the message is intended for the particular processor.

83. The system as set forth in claim 82 above, wherein the dedicated memory section comprises a portion for identifying an individual processor, a portion for identifying the processor as one of a process class, and a portion containing hash values.

84. The system as set forth in claim 83 above, wherein the dedicated memory section is arranged as at least two groups of commonly addressed storage maps providing corresponding independent outputs, and gate means responsive to at least a portion of the destination selection word and the outputs for detecting the existence of a match.

85. The system as set forth in claim 84 above, wherein the system includes a secondary storage having a subset of a data base associated with each processor and the hash values identify the portion of the data base associated with the processor.

86. The system as set froth in claim 80 above, wherein the reference values comprise a transaction number and a destination selection word, each having a selectable data content and providing a sort criteria for the network means, and the dedicated memory section comprises a transaction number section and a destination selection word section.

87. A system for intercommunication between a plurality of processor modules comprising:

means at each processor module providing serial messages comprising initial command bytes varying in data content to characterize the message as comprising data, status, control or response messages, and further to characterize messages within the different types, the command bytes being followed by subsequent message bytes;

means at each processor for transmitting messages in synchronism following the termination of prior messages; and

means intercoupling each processor to all other processors and including means for merging the serial messages in accordance with the data content therein during transmission to all the processors, wherein the data contents of the command bytes followed by the remaining message information successively determine message priority, and data, status, control and response messages are transferred between processor modules in accordance with a priority protocol without prefatory communications between processors.

88. The system as set forth in claim 87 above, wherein said further message bytes comprise alternatively transaction numbers and originating processor identification, and wherein said means at each processor for transmitting messages includes means for transmitting responses to primary messages in synchronism, the responses having higher priority than primary messages and being merged with a priority dependent first on response type and then originating processor identification.

89. The system as set forth in claim 88 above, wherein said transaction numbers are originating processor identification are fixed byte length words following immediately after the command bytes and varying in data content to act in determining priority.

90. The system as set forth in claim 89 above, wherein said primary message information further includes a fixed byte length destination selection word of varying data content following the transaction number.

91. The system as set forth in claim 90 above, wherein said means intercoupling each processor comprises a network of node means arranged in successive tiers and includes means for advancing the serial messages in successive time frames between tiers and means for determining priority between competing pairs of messages at each node means, and wherein the means intercoupling each processor further includes clock means coupled thereto for advancing the serial messages in synchronism.

92. A multiprocessor system for performing multiple data processing tasks in different individual processors within the system without the need for substantial software to determine routing, availability and priority status, comprising:

means providing message packets including priority determining commands and data;

spatially distributed network means coupled to receive the message packets and including a plurality of bidirectional active circuit means merging at a return circuit means, each of the active circuit means being responsive to the message packets to continue transfer of competing message packets having priority whereby multiple messages concurrently on the network are prioritized in the time and space domains and the single priority message packet is distributed concurrently on the network; and

a plurality of processor modules, each comprising a processor operating at a different rate than the network means and interface means including a random access memory means, the interface means being coupled to both the network means and the processor means and including means responsive to the message packets for responding only to those message packets appropriate for the individual processor, the interface means including means for storing receive and send messages to and from the processor, and dedicated memory sections for retaining task identifying and destination selection information separately accessible to the network means, whereby tasks may be automatically accepted for the appropriate processors without requiring interprocessor communications or central determinations of priority and routing.

93. The system as set forth in claim 92 wherein the interface means includes clocking means operating at a higher rate than the network means and processor means and control means responsive to the clock means for time multiplexing operation of the random access memory means between processor, send and receive phases.

94. The system as set forth in claim 93 above, wherein the processors operate asynchronously and the clock means is synchronized with the network means.

95. The system as set forth in claim 92 wherein the interface means further comprise means, including the random access memory means, responsive to the associated processor for storing status data in the random access memory means as to different tasks in a form accessible to the network means.

96. The system as set forth in claim 95 above, wherein the random access memory means comprises a reference directory of status indication response texts and the processor module includes means for controlling status indication response texts stored in the random access memory means.

97. The system as set forth in claim 96 above, wherein the message packets include transaction numbers and the interface means includes means for directly addressing the random access memory means to derive status indications without communication with the processor.

98. The system as set forth in claim 97 above, wherein the status data includes message count data for use in controlling the flow of message packets.

99. The system as set forth in claim 92 above, wherein the random access memory means includes message buffer means for assembling pluralities of receive and send message packets for communication between the network means and the associated processor.

100. The system as set forth in claim 99 above, wherein the interface means includes means for determining from the immediate contents of the receive and send buffer sections whether the processor module capacity for receive or send is exceeded, and indicating the nonavailability of the associated processor in response thereto.

101. The system as set forth in claim 100 above, wherein the means for indicating the nonavailability of a processor comprises means providing a circular buffer receive section in the random access memory means, and means for detecting an overrun condition therein.

102. The system as set forth in claim 100 above, wherein the message buffer means for assembling send message packets comprises a send buffer storage for message packets, and a send output message complete vector circular buffer for providing pointers to output message locations.

103. The system as set forth in claim 92 above, wherein the message packets include destination control information, and the interface means include means responsive to the destination control information, for (1) providing a response from a specific identified processor module, (2) providing responses from a specific identified group of processor modules, or (3) providing responses from all processor modules.

104. The system as set forth in claim 92 above, wherein the message packets comprise serial byte sequences including an initial command word, and including at least one control bit per byte, the control bit sequences defining internal fields, field translations within the message packets, and end of message.

105. The system as set forth in claim 104 above, wherein the network means includes means for granting priority in accordance with lowest data content and the processor modules include means providing an uninterrupted sequence of 1'"'"'s in at least the control bit to represent the idle state.

106. The system as set forth in claim 92 above, wherein the message packet bytes further include parity bit, the processor modules comprise means for forcing parity errors on change of status, and the network means comprises means for propagating the forced parity error once.

107. A system for controlling routing of messages between processors in a multiprocessor system comprising:

means at each processor for providing a serial message train including destination selection data comprising alternatively specific processor identification, identification of a process class, and hashing values;

lookup table means at each processor including at least three separate sections defining different destination selection criteria comprising a specific processor identification section, a processor class section and a hash value section;

means coupled to each of the processors for delivering to all processors, from a number of messages concurrently transmitted by the processors, a single priority message; and

means at each processor responsive to the destination selection data in the single priority message for addressing the lookup table means directly with the destination selection data to determine whether the particular processor is being addressed, such that the processor may be selected in accordance with one of a variety of multiprocessor modes, including a general broadcasting mode in the absence of a destination selection data entry.

108. The system as set forth in claim 107 above, wherein said means for delivering a single priority message comprises an active logic network and the lookup table means comprises a high speed random access memory and means for accessing the memory separately from the associated processor and the active logic network.

109. The system as set forth in claim 108 above, wherein the means for addressing the lookup table means comprises means for comparing the value at the addressed location to at least a portion of the destination selection data.

110. In a system having a number of processors communicating via an interconnect network, the combination comprising:

a number of buffer means, each associated with a different one of the processors and coupled to the network and the processor associated therewith, each buffer means including a dedicated memory reference section having at least two different selection maps representing different modes of selection;

the processors generating messages having selection data for referencing the selection maps; and

a number of interface means, each connected to a different processor and the buffer means coupled thereto, and coupled to the network, and each responsive to the selection data for referencing the selection maps in the buffer means to determine whether the selection data specify that the message is intended for the processor associated therewith, and coupled to control reception of messages intended for the processor associated therewith.

111. The system as set forth in claim 110 above, wherein the interconnect network includes means for providing the messages concurrently to the processors, and wherein each buffer means includes at least three reference sections, one organized to denote individual processors, a second to denote processors by class codes, and a third providing a hash map for distributed data.

112. The system as set forth in claim 111 above, wherein the interface means further includes means responsive to the selection data and the reference values for incorporating hash results in the message, and the buffer means includes a receive message section coupled to store the messages intended for the associated processor.

113. The system as set forth in claim 112 above, wherein at least the hash map section of the buffer means is divided into a number of parts each identified by a different map selection code and commonly addressed by a map address, and wherein the messages comprise destination selection words containing map selection code and map address portions.

114. The system as set forth in claim 113 above, wherein the interface means each comprise means for addressing the buffer means with the map address, and the interface means further comprise comparator means responsive to the map address and map selection code portions, and the contents of the buffer means addressed thereby, for determining whether the message is intended for the associated processor.

115. A system for effecting data transfer between a network and a processor providing transaction numbers comprising the combination of:

a network providing message streams associated with transaction numbers identifying a particular processing transaction or transaction type;

interface means, including high speed random access memory means, coupled to the processor and the network and including;

a memory section storing data in externally accessible form in accordance with transaction number addresses,

a memory section storing a directory of transaction readiness words, and

a section storing messages for transfer between the processor and the network;

and the processor being coupled to reference the directory to store updated entries in the transaction number addresses, such that the network can determine the state of readiness as to a particular transaction solely from the random access memory means.

116. The system as set forth in claim 115 above, wherein the random access memory means further includes a section for storing send messages from the processor, and a section for storing pointers to the locations from which send messages are transferred to the network, and wherein the processor controls the entry of messages in the memory means.

117. The system as set forth in claim 116 above, wherein the processor also provides destination selection words and the memory means includes a stored table of destination selection data, and the interface means includes means for addressing the selection data using the selection words to determine if a message is intended for the processor.

118. A bidirectional branching node circuit for a message switching system in which competing concurrent messages are received, comprising:

a bidirectional upstream port circuit and two bidirectional downstream port circuits each including parallel data lines and collision lines;

logic means coupled to the downstream port circuits for transferring a single one of two competing upstream messages received at the downstream ports to the upstream port by granting priority in accordance with a predetermined priority rule determined by message content;

means coupling the upstream and downstream port circuits and responsive to messages received at the upstream port for providing downstream transmission of such messages to both downstream ports; and

control means coupled to the logic means, the upstream port circuit and the downstream port circuits and responsive to the grant of priority between upstream messages for generating signals on the losing collision line to indicate that priority has been granted a message other than the message received at the port, and for transferring a signal received at the upstream port on the collision line thereat.

119. The system as set forth in claim 118 above, wherein the port circuits each include clock lines to and from the port circuit, and the node circuit further includes clock timing means coupled to the clock lines.

120. The system as set forth in claim 119, wherein said control means further comprises means responsive to the termination of a message for resetting the control means.

121. The system as set forth in claim 120 above, wherein the node circuit comprises, at each port, a plurality of upstream and downstream data lines, and at least one parity line and wherein the collision line from the upstream port is coupled to reset the control means on the termination of the collision signal from the upstream port.

122. A system for transferring data from multiple sources along a chain of nodes with zero time skew between the data flow at the nodes comprising:

a plurality of individual active circuit nodes in a sequential array culminating at an apex node, the coupling between successive nodes introducing no more than a given maximum time delay;

a master clock source coupled to the apex node;

a plurality of individual clock generating circuits, each disposed at a different node and generating a controllably adjustable clock signal at the nominal frequency of the master clock source;

means coupling successive pairs of nodes for returning clock signals from the next successive node to an originating node;

means at each node coupled to receive the clock signal and the returning clock signal for comparing the clock from an individual clock generating circuit to the retardation of the returning clock signals to generate an error signal; and

means for controlling the individual clock generating circuit with the error signal, whereby all clock generating circuits maintain a uniform time relation to the master clock.

123. The system as set forth in claim 122 above, wherein the sequential array comprises a bidirectional tree, wherein the data is transmitted in message packets, and wherein the active circuit node include means responsive to the individual clock signals for transferring the message packets in both directions from the tree base and along the tree to arrive back at the tree base in synchronism.

124. The system as set forth in claim 123 above, including in addition sources coupled to each node at the base of the tree, and clock means at each source for subdividing the clock interval to provide at least one other higher frequency clock in predetermined phase relationship therewith.

125. The system as set forth in claim 124 above, wherein the means for providing the higher frequency clock signal includes means defining at least three signal phases within the clock interval.

126. In a multiprocessor system in which processors transfer message packets by broadcasting to all other processors, means for generating messages organized as a series of bytes defining a plurality of fields comprising:

a command field comprising one of a selected sequence of message characterizing values of fixed byte length;

a tag field following the command field and comprising a fixed length transaction number or processor identification number, both of varying data content and fixed byte length; and

control bits in parallel with the bytes, the control bit sequences defining the fields.

127. The system as set forth in claim 126 above, including further an idle field to designate separations between messages, the idle field being defined by control bit sequences of fixed data content.

128. The system as set forth in claim 127 above, wherein the message further comprises a destination selection field of fixed length and varying data content following the tag field, and a data field of variable length following the destination selection field, the data field optionally including an initial key field of varying data content for characterizing the data.

129. The system as set forth in claim 128 above, wherein the destination selection field is subdivided into hash map address and hash map code selection portions of fixed length.

130. The system as set forth in claim 129 above, wherein the message further comprises an end of message field defined by a predetermined control bit sequence.

131. A system for determining the global status of the resources in a multiprocessor system, where the resource is associated with a local semaphore means in each processor which contains the resource, comprising:

means for querying the local semaphore means in each processor to derive a plurality of concurrent responses; and

means responsive to the concurrent responses for sorting the responses to derive a priority response indication of global status.

132. The system as set forth in claim 131 above, wherein the means for sorting comprises a network intercoupled throughout the multiprocessor system and sorting the responses in accordance with the contents thereof.

133. A multiprocessor system comprising:

a plurality of individual processors having local, externally accessible semaphores; and

a network coupled to all the processors for broadcasting queries and updates as to semaphore status concurrently to the processors.

134. The system as set forth in claim 133 above, wherein the processors further comprise means for transmitting messages, including semaphore status queries, having varying data contents and the network includes means for sorting the transmitted messages to broadcast a selected status query.

135. A multiprocessor system comprising:

a plurality of processors, each including means for transmitting a status response of selected data content, concurrently with responses from other processors, to a status query; and

network means coupled to the processors for arbitrating the responses in accordance with the data contents thereof to provide global indication of multiprocessor status in response to the query.

136. The system as set forth in claim 135 above, wherein the status responses vary in data content in accordance with processor readiness and wherein the global indication corresponds to the least ready processor status.

137. The system as set forth in claim 136 above, wherein the network means comprises a sort network.

138. The method of operating a plurality of processors which may be performing related tasks asynchronously so as to provide global task coordination, which method comprises the steps of:

identifying tasks with global transaction numbers;

sorting competing messages from different processors utilizing the data content of the communications, including the transaction numbers, to establish priority;

locally establishing processor status pertaining to each given transaction number;

transmitting a status request for sorting with competing messages;

concurrently transmitting transaction status from the processors in response to a status request that gains priority; and

merging the status responses in accordance with a predetermined priority rule such that an "update level" having the least priority takes precedence, whereby the global resource ascertains from the received response the readiness of the system in global terms.

139. The method as set forth in claim 138 above, wherein a transaction number of 0 identifies a non-merge mode, and wherein transaction numbers other than 0 identify competing communications that are to be merged, whereby processors are commanded as well as referenced by the transaction numbers.

140. The method as set forth in claim 139 above, including in addition the steps of commanding the processors to assign and relinquish transaction numbers by messages transmitted for sorting with competing messages.

141. The method as set forth in claim 140 above, including the steps of including destination selection information in the messages and locally determining from the priority messages sorted from competing messages which messages are to be acted on by the individual processor, whereby with the transaction numbers and commands the different processors can intercommunicate in different ways.

142. The method of monitoring the status of related but asynchronous individual processor activities in a multiprocessor system coupled by a sorting network comprising the steps of:

transmitting a transaction identity on the network to the processors for common referencing relative to each particular task that is to be performed by related subtasks;

accepting the transaction identity reference at each processor that is to function relative to the task;

associating with the transaction identity at each processor that is to function as to the task, a locally updated local status indication that is accessible to the network;

querying the processors concurrently to obtain concurrent local status indications as to a given transaction identity; and

merging the local status indications pertaining to a transaction identity to obtain a network determination of the transaction status.

143. The method as set forth in claim 142 above, further including the step of merging processed messages pertaining to a transaction identity following indication of readiness of all processors functioning on the given task.

144. The method as set forth in claim 142 above, further including the step of shifting to a different transaction identity to determine the readiness state thereof when the processors are not yet ready as to a first transaction identity.

145. The method as set forth in claim 144 above, wherein the local status indications have an order of priority and further including the steps of concurrently transmitting local status indications from each processor and merging such indications in accordance with the order of priority, with the least ready indication representing the global system status as to that transaction identity.

146. The method as set forth in claim 145 above, further including the step of assigning further coordination of global status determinations to the processor in the least ready status.

147. The method of placing messages from a plurality of processors in a sorted order, the messages being generated during the completion of asynchronous processing tasks, the method comprising the steps of:

assembling, at the individual processors, sorted sequences of messages in suborders pertaining to transaction numbers in the messages;

synchronously transmitting the highest priority messages from each of the processors pertaining to a given transaction number;

dynamically prioritizing the competing messages to reject all but that message having highest priority;

synchronously repeating the transmission of successive highest priority messages until all the messages in the sorted suborder pertaining to a given transaction number have been completely transmitted; and

successively repeating the sequence for messages pertaining to transaction numbers in descending order of priority.

148. The method as set forth in claim 147 above further comprising the steps of:

querying all processors concurrently as to state of readiness pertaining to a given transaction number;

locally indicating status of readiness concurrently; and

prioritizing the local indications to determine the least state of readiness as to the given transaction number.

149. The method of communicating with a plurality of processors in a multiprocessor system to determine the global status of the system as to a task divided into subtasks being performed asynchronously by the processors, comprising the steps of:

providing concurrent status indications from each of the processors as to the state of readiness of that processor as to its subtask; and

sorting the concurrent status indications.

150. The method as set forth in claim 149 above, wherein the status indications vary in data content and the step of sorting comprises sorting in accordance with data content.

151. The method as set forth in claim 150 above, further including the steps of:

broadcasting a query to the processors to elicit the concurrent status indications;

providing the concurrent status indications as serial signal trains; and

sorting the serial signal trains to a single or common priority signal train in a predetermined fixed time interval.

152. The method of communicating between multiple processors comprising the steps of:

maintaining a plurality of differently identified semaphores at each processor under local processor control; and

externally testing corresponding semaphores at all processors with a broadcast addressed to all processors for a specific identity.

153. The method as set forth in claim 152 above, further comprising the steps of:

transmitting messages from the processors concurrently; and

sorting the concurrent messages to derive a message for broadcast.

154. The method of providing a global assessment of the work status of processors as to a given task in a multiprocessor system comprising the steps of:

locally selecting, at each processor, one of a number of predetermined messages of different data content to indicate the local instantaneous readiness state as to the given task;

externally eliciting the messages concurrently from all processors involved in the given task; and

aribtrating the messages to establish the priority message based on data content.

155. The method as set forth in claim 154 above, wherein the messages vary in data content in accordance with a predetermined schedule of readiness states, the lowest data content indicating least readiness state, and wherein the arbitration step awards priority to the message of lowest data content.