US4412285A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiprocessor intercommunication system and method
Assignee: NCR Voyix Corp
•
Filing: 1981-04-01
•
Granted: 1983-10-25
•
Expires: 2001-04-01
Abstract
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.
Inventors
- 👤 Philip M. Neches
- 👤 David H. Hartke
- 👤 Richard C. Stockton
- 👤 Martin C. Watson
- 👤 David Cronshaw
- 👤 Jack E. Shemer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 15:27
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; H; H04; H04L; H04L69/00
Claims Analysis
Total Claims: 178
Claim 1
Independent Claim
70 words
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.
Claim 2
Dependent Claim
70 words
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.
Claim 3
Dependent Claim
29 words
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.
Claim 4
Dependent Claim
51 words
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.
Claim 5
Dependent Claim
42 words
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.
Claim 6
Dependent Claim
36 words
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.
Claim 7
Dependent Claim
37 words
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.
Claim 8
Dependent Claim
31 words
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.
Claim 9
Dependent Claim
50 words
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.
Claim 10
Dependent Claim
39 words
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.
Claim 11
Dependent Claim
41 words
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.
Claim 12
Dependent Claim
22 words
The system as set forth in claim 10 above, wherein the destination selection information is a destination selection word of fixed length.
Claim 13
Dependent Claim
49 words
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.
Claim 14
Dependent Claim
47 words
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.
Claim 15
Dependent Claim
75 words
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.
Claim 16
Dependent Claim
82 words
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.
Claim 17
Dependent Claim
25 words
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.
Claim 18
Dependent Claim
43 words
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.
Claim 19
Dependent Claim
45 words
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.
Claim 20
Dependent Claim
24 words
The system as set forth in claim 18 above, wherein a predetermined one of the tags identifies the nonmerge state to the processor modules.
Claim 21
Dependent Claim
47 words
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.
Claim 22
Dependent Claim
65 words
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.
Claim 23
Dependent Claim
61 words
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.
Claim 24
Dependent Claim
38 words
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.
Claim 25
Dependent Claim
63 words
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.
Claim 26
Dependent Claim
26 words
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.
Claim 27
Dependent Claim
35 words
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.
Claim 28
Dependent Claim
80 words
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.
Claim 29
Dependent Claim
43 words
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.
Claim 30
Dependent Claim
28 words
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.
Claim 31
Dependent Claim
32 words
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.
Claim 32
Dependent Claim
85 words
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.
Claim 33
Dependent Claim
68 words
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.
Claim 34
Dependent Claim
43 words
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.
Claim 35
Dependent Claim
69 words
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.
Claim 36
Dependent Claim
57 words
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.
Claim 37
Dependent Claim
22 words
The system as set forth in claim 7 above, wherein the system includes means for transmitting, between messages, lowest priority idle signals.
Claim 38
Dependent Claim
43 words
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.
Claim 39
Dependent Claim
42 words
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.
Claim 40
Dependent Claim
31 words
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.
Claim 41
Dependent Claim
69 words
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.
Claim 42
Independent Claim
50 words
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.
Claim 43
Independent Claim
50 words
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.
Claim 44
Dependent Claim
29 words
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.
Claim 45
Dependent Claim
35 words
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.
Claim 46
Dependent Claim
46 words
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.
Claim 47
Dependent Claim
40 words
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.
Claim 48
Dependent Claim
29 words
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.
Claim 49
Dependent Claim
25 words
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.
Claim 50
Dependent Claim
22 words
The method as set forth in claim 46 above, wherein a specific value of transaction identification represents the non-merge mode of operation.
Claim 51
Dependent Claim
69 words
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.
Claim 52
Dependent Claim
38 words
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.
Claim 53
Dependent Claim
44 words
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.
Claim 54
Dependent Claim
33 words
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.
Claim 55
Dependent Claim
48 words
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.
Claim 56
Dependent Claim
48 words
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.
Claim 57
Dependent Claim
44 words
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.
Claim 58
Dependent Claim
47 words
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.
Claim 59
Dependent Claim
29 words
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.
Claim 60
Dependent Claim
104 words
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.
Claim 61
Dependent Claim
40 words
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.
Claim 62
Dependent Claim
57 words
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.
Claim 63
Dependent Claim
64 words
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.
Claim 64
Dependent Claim
35 words
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.
Claim 65
Dependent Claim
41 words
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.
Claim 66
Dependent Claim
87 words
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.
Claim 67
Dependent Claim
87 words
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.
Claim 68
Dependent Claim
71 words
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.
Claim 69
Dependent Claim
82 words
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.
Claim 70
Dependent Claim
99 words
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.
Claim 71
Dependent Claim
99 words
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.
Claim 72
Dependent Claim
36 words
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.
Claim 73
Dependent Claim
57 words
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.
Claim 74
Dependent Claim
115 words
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.
Claim 75
Dependent Claim
115 words
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.
Claim 76
Dependent Claim
56 words
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.
Claim 77
Dependent Claim
58 words
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.
Claim 78
Dependent Claim
60 words
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.
Claim 79
Dependent Claim
49 words
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.
Claim 80
Dependent Claim
119 words
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.
Claim 81
Dependent Claim
119 words
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.
Claim 82
Dependent Claim
42 words
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.
Claim 83
Dependent Claim
42 words
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.
Claim 84
Dependent Claim
45 words
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.
Claim 85
Dependent Claim
32 words
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.
Claim 86
Dependent Claim
28 words
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.
Claim 87
Dependent Claim
29 words
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.
Claim 88
Dependent Claim
55 words
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.
Claim 89
Dependent Claim
40 words
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.
Claim 90
Dependent Claim
54 words
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.
Claim 91
Dependent Claim
42 words
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.
Claim 92
Dependent Claim
53 words
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.
Claim 93
Independent Claim
143 words
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.
Claim 94
Independent Claim
143 words
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.
Claim 95
Dependent Claim
66 words
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.
Claim 96
Dependent Claim
38 words
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.
Claim 97
Dependent Claim
31 words
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.
Claim 98
Dependent Claim
73 words
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.
Claim 99
Dependent Claim
230 words
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.
Claim 100
Dependent Claim
230 words
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.
Claim 101
Dependent Claim
51 words
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.
Claim 102
Dependent Claim
24 words
The system as set forth in claim 93 above, wherein the processors operate asynchronously and the clock means is synchronized with the network means.
Claim 103
Dependent Claim
48 words
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.
Claim 104
Dependent Claim
43 words
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.
Claim 105
Dependent Claim
39 words
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.
Claim 106
Dependent Claim
26 words
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.
Claim 107
Dependent Claim
38 words
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.
Claim 108
Dependent Claim
50 words
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.
Claim 109
Dependent Claim
41 words
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.
Claim 110
Dependent Claim
43 words
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.
Claim 111
Dependent Claim
59 words
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.
Claim 112
Dependent Claim
48 words
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.
Claim 113
Dependent Claim
47 words
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.
Claim 114
Dependent Claim
44 words
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.
Claim 115
Independent Claim
167 words
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.
Claim 116
Independent Claim
167 words
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.
Claim 117
Dependent Claim
51 words
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.
Claim 118
Dependent Claim
38 words
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.
Claim 119
Dependent Claim
142 words
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.
Claim 120
Dependent Claim
142 words
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.
Claim 121
Dependent Claim
58 words
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.
Claim 122
Dependent Claim
51 words
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.
Claim 123
Dependent Claim
58 words
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.
Claim 124
Dependent Claim
63 words
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.
Claim 125
Independent Claim
132 words
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.
Claim 126
Independent Claim
132 words
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.
Claim 127
Dependent Claim
57 words
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.
Claim 128
Dependent Claim
54 words
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.
Claim 129
Dependent Claim
173 words
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.
Claim 130
Dependent Claim
173 words
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.
Claim 131
Dependent Claim
37 words
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.
Claim 132
Dependent Claim
27 words
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.
Claim 133
Dependent Claim
58 words
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.
Claim 134
Independent Claim
177 words
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.
Claim 135
Independent Claim
177 words
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.
Claim 136
Dependent Claim
64 words
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.
Claim 137
Dependent Claim
48 words
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.
Claim 138
Dependent Claim
31 words
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.
Claim 139
Dependent Claim
91 words
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.
Claim 140
Dependent Claim
91 words
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.
Claim 141
Dependent Claim
32 words
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.
Claim 142
Dependent Claim
58 words
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.
Claim 143
Dependent Claim
29 words
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.
Claim 144
Dependent Claim
26 words
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.
Claim 145
Independent Claim
69 words
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.
Claim 146
Independent Claim
69 words
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.
Claim 147
Dependent Claim
32 words
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.
Claim 148
Dependent Claim
35 words
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.
Claim 149
Dependent Claim
35 words
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.
Claim 150
Dependent Claim
42 words
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.
Claim 151
Dependent Claim
60 words
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.
Claim 152
Dependent Claim
60 words
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.
Claim 153
Dependent Claim
34 words
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.
Claim 154
Dependent Claim
17 words
The system as set forth in claim 136 above, wherein the network means comprises a sort network.
Claim 155
Independent Claim
129 words
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.
Claim 156
Independent Claim
129 words
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.
Claim 157
Dependent Claim
46 words
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.
Claim 158
Dependent Claim
32 words
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.
Claim 159
Dependent Claim
57 words
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.
Claim 160
Independent Claim
132 words
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.
Claim 161
Independent Claim
132 words
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.
Claim 162
Dependent Claim
34 words
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.
Claim 163
Dependent Claim
39 words
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.
Claim 164
Dependent Claim
59 words
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.
Claim 165
Dependent Claim
29 words
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.
Claim 166
Independent Claim
123 words
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.
Claim 167
Independent Claim
123 words
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.
Claim 168
Dependent Claim
53 words
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.
Claim 169
Independent Claim
66 words
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.
Claim 170
Independent Claim
66 words
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.
Claim 171
Dependent Claim
29 words
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.
Claim 172
Dependent Claim
55 words
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.
Claim 173
Independent Claim
44 words
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.
Claim 174
Independent Claim
44 words
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.
Claim 175
Dependent Claim
31 words
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.
Claim 176
Independent Claim
80 words
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.
Claim 177
Independent Claim
80 words
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.
Claim 178
Dependent Claim
47 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1986-10-24 | 1987-04-25 | 1987-10-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1990-10-24 | 1991-04-25 | 1991-10-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1994-10-24 | 1995-04-25 | 1995-10-25 | $7700.00 | Window Closed / Lapsed |