Multi processor sorting network for sorting while transmitting concurrently presented messages by message content to deliver a highest priority message
First Claim
1. A multi-processor system having a plurality of processors and improved facility for intercommunication of data packets between processors, comprising:
- a sort network, intercoupling the processors such that each of the processors is coupled to all others of the processors, for sorting the data packets into priority order based on at least one criteria comprising command code, data content, and data length;
means at each of the processors for concurrently presenting data packets to the sort network; and
means at each of the processors responsive to received data packets from the sort network for accepting packets based on the data content thereof.
3 Assignments
0 Petitions
Accused Products
Abstract
A multiprocessor system intercouples the processors with an active logic network having a plurality of priority determining nodes. Messages applied concurrently to the network in groups are sorted, using the data content of the messages, to a single or common priority message which is distributed to all the processors with a predetermined total network delay time. Losing messages are again retried concurrently in groups at a later time. Message routing is determined by local acceptance or rejection of messages at the processors, based upon destination data in the messages. All messages occupy places in a coherent priority scheme and are transferred in contending groups with prioritization on the network. Using data, status, control and response messages, and different multiprocessor modes, the system is particularly suited for configuration in a relational data base machine having capability for maintaining an extended data base and handling complex queries.
-
Citations
39 Claims
-
1. A multi-processor system having a plurality of processors and improved facility for intercommunication of data packets between processors, comprising:
-
a sort network, intercoupling the processors such that each of the processors is coupled to all others of the processors, for sorting the data packets into priority order based on at least one criteria comprising command code, data content, and data length; means at each of the processors for concurrently presenting data packets to the sort network; and means at each of the processors responsive to received data packets from the sort network for accepting packets based on the data content thereof.
-
-
2. A method of communicating between processors to confirm in a minimum number of steps that all processors intended to receive a given task message have correctly received the message, the method comprising the steps of:
-
concurrently transmitting competing task messages having a given order of priority from the processors; sorting the task messages, while transferring them, to derive a priority task message delivered concurrently to all processors, wherein the sorting is based on at least one criteria comprising command code, data content, and data length; concurrently responding to the priority task message at all processors with response messages having a given order of priority, a "correct reception" response message having a lower order of priority than a "rejection" response message for an intended processor, and the response messages having priority over the task messages; sorting the response messages, while transferring them, to derive a single priority response message delivered to all intended processors, wherein the sorting is based on at least one criteria comprising command code, data content, and data length; and accepting the priority task message at the intended processors if the priority response message is a "correct reception" response message. - View Dependent Claims (3, 4, 5, 6, 7, 8)
-
-
9. A method for assuring, in a minimum number of interchanges, that all relevant processors in a multi-processor system accept or commit to a task, the method comprising the steps of:
-
broadcasting a message intended to be accepted by the relevant processors; concurrently responding to the broadcast message with response messages indicating by data content thereof whether the broadcast message has been accepted at the relevant processors; and arbitrating the response messages based on at least one criteria comprising command code, data content, and data length, to broadcast a single priority response message indicative of acceptance by all of the relevant processors, unless at least one relevant processor has indicated non-acceptance. - View Dependent Claims (10, 11, 12)
-
-
13. In a multi-processor system, a method of confirming successful concurrent acceptance of messages by different relevant processors to a given process in arbitrarily controlled groupings, comprising the steps of:
-
broadcasting a message to all of the processors; recognizing, at each of the processors, the message'"'"'s relevance to the processor; sending response messages concurrently from all processors, the response messages having data contents varying in accordance with a priority rule to denote that the broadcast message is not relevant, is relevant and reception is confirmed, or is relevant but reception is not confirmed; and prioritizing the concurrent response messages based on at least one criteria comprising command code, data content, and data length, to establish whether all relevant processors have confirmed reception, such that one concurrent broadcast message to, and one concurrent response message from, each of the processors assures confirmation from all relevant processors.
-
-
14. A method of transmitting and receiving primary data messages in a multi-processor, the method comprising the steps of:
-
a) simultaneously broadcasting a primary data message to a plurality of processors; b) determining at each individual processor if the broadcast primary data message is intended for the individual processor; c) generating a response at each intended individual processor, the response indicating each individual processor'"'"'s ability to process the primary data message; d) transmitting the generated response for each intended individual processor through a priority determining network to prioritize all the generated responses based on at least one criteria comprising command code, data content, and data length; e) granting highest priority within the priority determining network to any generated response indicating any intended individual processor'"'"'s inability to process the primary data message; and f) granting lowest priority within the priority determining network to any generated response acknowledging an intended individual processor'"'"'s ability to process the primary data message, thereby causing the priority determining network to create an output signal indicating acknowledgment of the primary data message only when intended individual processor indicates an ability to process the primary data message. - View Dependent Claims (15, 16, 17)
-
-
18. A method of processing primary data messages in a multi-processor system, the method comprising the steps of:
-
a) transmitting the primary data messages to a network coupled to a plurality of processors; b) sorting the primary data messages, by the network, into priority order based on at least one criteria comprising command code, data content, and data length to obtain a highest priority primary data message; c) receiving the highest priority primary data message at the processors, the processors each independently; i) determining when the reception of the highest priority primary data message is completed; ii) determining if the processor is a member of a group of processors intended for the highest priority primary data message; iii) determining if the intended processor is in a state to process the highest priority primary data message; iv) generating a responsive message indicating if the intended processor will process the highest priority primary data message; v) transmitting the responsive message to the network; d) determining within the network if every intended processor will process the highest priority primary data message; and e) completing the processing of the highest priority primary data message only if the network indicates that every intended processor will process the highest priority primary data message. - View Dependent Claims (19, 20, 21, 22, 23)
-
-
24. A method of processing tasks in different processors of a computer system and merging message packets into a sorted order, the method comprising the steps of:
-
transmitting messages to the different processors for identifying individual portions of the tasks to be performed; asynchronously carrying out the individual portions of the task in the different processors to generate processed message packets; locally chaining together the processed message packets at each of the different processors into a sorted order, thereby creating a plurality of sorted message packets; transmitting a "start merge" instruction to the different processors concurrently; concurrently transmitting a highest priority one of the sorted message packets from each of the different processors while dynamically prioritizing a single message packet based on at least one criteria comprising command code, data content, and data length; and repeating the concurrent transmission and prioritizing with losing and new message packets until all message packets pertaining to the task have been transmitted in sorted order. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. A method of placing messages from a plurality of individual 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, sequences of the messages, the messages having sorting criteria therein; synchronously transmitting high priority messages according to the sorting criteria from each of the individual processors; dynamically prioritizing competing high priority messages based on at least one criteria comprising command code, data content, and data length to reject all but a highest priority message; and synchronously repeating the transmission of remaining high priority messages until all the messages have been completely transmitted. - View Dependent Claims (34, 35, 36)
-
-
37. A method of multiplexing a multi-processing computer system so that the processors may function as to a member of task requests, the method comprising the steps of:
-
assigning each of the processors to a sort/merge stream for each task request with which the processor is to be active; asynchronously assembling, at each of the processors, sorted subsets of messages pertaining to the relevant task requests for that processor; synchronously transmitting high priority messages from each subset pertaining to a given task request; dynamically sort/merging the competing high priority messages to select a highest priority message wherein the high priority messages are sorted based on at least one criteria comprising command code data content and data length; and assembling the sort/merge stream by repeated synchronous transmissions and selection of successive high priority messages. - View Dependent Claims (38, 39)
-
Specification