Methods of selecting simultaneously transmitted messages in a multiprocessor system

• US 4,956,772 A
• Filed: 11/03/1988
• Issued: 09/11/1990
• Est. Priority Date: 04/01/1981
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata Corporation
• Inventors: Neches, Philip M.
• Primary Examiner(s): Lee, Thomas C.
• Application Number:
  US07/266,899
• Time in Patent Office: 677 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300, 340/825.02, 340/825.03, 340/825.50, 340/825.51, 340/825.52, 370/85.94, 370/85.6, 370/94.1
• US Class Current: 719/313
• CPC Class Codes: G06F 11/202 where processing functionality is redundant redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 15/161 Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning casings, cabinets, racks or drawers for data centers H05K5/00
• CPC Class Codes: G06F 15/17368 non hierarchical topologies
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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 meassages, 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 priorty 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.

Claims

1. A method of processing data using a plurality of processor modules comprising the steps of:

a. subdividing a data processing task into information packets each said information packet representing a subtask;

b. simultaneously broadcasting pairs of successive said information packets to a priority determining network having a plurality of priority determining holes;

c. determining at each said priority determining node which said information packet of the broadcasting pair has a higher priority solely based upon data contents thereof;

d. selecting by said priority determining network a chosen information packet from a plurality of said information packets each having a higher priority;

e. broadcasting successive chosen information packets to all the processor modules simultaneously, each of the chosen information packets containing a characterizing message;

f. determining from the characterizing message in each said chosen information packet, at all the processor modules, an appropriate individual processor module or modules for carrying out the subtask represented by each said chosen information packet;

g. generating processed information packets at the processor modules based upon result of said determining step;

h. broadcasting different ones of the processed information packets to all the processor modules simultaneously.

2. The method as set forth in claim 1 above, wherein the information packets comprise both data and response messages and selecting step prioritizes said response message as well as data messages.

3. The method as set forth in claim 2 above, wherein the processor modules generate information packets containing characterizing messages defining further subtasks, such that said processor modules can function cooperatively with any one said processor modules functioning as coordinator.

4. The method as set forth in claim 3 above, wherein the method is used for management of a data base comprising a number of files each said file corresponding to one of said processor modules, and further including the step of storing disjoint subsets of the data base at each file, the disjoint subsets having known relationships, among themselves and defining a complete data base.

5. The method as set forth in claim 4 above, further including the step of hashing the characterizing messages in the information packets at each processor module said to determine whether the information packet relates to the disjoint subset of the data base at the file corresponding to said processor module.

6. A method of data base management in a data processing system which shares a processing task between a number of small processors each having an allotted portion of the data base but frees the data processing system from the task of supervising or monitoring locations and status of the processors comprising the steps of:

a. generating at said processors concurrent information packets representing individual data base task assignment respectively;

b. initially broadcasting concurrently from each said processor said information packet to a priority determining network;

c. deriving by said priority determining network a single highest priority information packet among the concurrent information packets solely based upon data content thereof;

d. transmitting the highest priority information packet such that the highest priority information packet reaches all said processors simultaneously;

e. determining at each said processor from the highest priority information packet whether the individual task is within the allotted data base portion for said processor;

f. processing the highest priority information packet by at least one of said processors based upon result of said determining step to generate one or more information packets having processed data;

g. broadcasting competing information packets again concurrently to all said processors while prioritizing the concurrent information packets such that the information packets involving task assignments and processed data are inherently sequenced by a priority protocol.

7. The method as set forth in claim 6 above, further including the step of broadcasting competing responses to received information packets from all said processors, while prioritizing by said priority determining network the reponses to derive a single or common priority response.

8. The method as set forth in claim 7 above, further including the step of broadcasting competing status and control packets from the processors concurrently with other information packets while prioritizing all said packets in accordance with a coherent priority schedule.

9. The method as set forth in claim 8 above, wherein the information packets and said responses comprise data streams and including the steps of concurrently initiating the data streams and transferring the single or common priority stream to all said processors after a predetermined delay.

10. The method as set forth in claim 9 above, wherein the data streams are variable length byte sequences and said prioritizing step comprises the steps of making successive pair comparisons between contending data streams.

11. The method as set forth in claim 10 above, wherein the system has n said processors, each of said n processors stores an exclusive 1/nth of the data base as a primary file.

12. The method as set forth in claim 11 above, wherein the primary files are disjoint subsets of the data base and each of the n processors also stores an exclusive 1/nth of the data base as a backup file, the backup files being disjoint subsets and non-redundant to the primary files at the same processor.

13. The method as set forth in claim 12 above, wherein the information packets comprises hash values for identifying data base portions and further including the step of hashing the hash values to ascertain whether the data base portion is allocated to the particular processor.

14. The method as set forth in claim 13 above, including the furter step of assembling processed packets derived after processing within the system.

15. The method as set forth in claim 14 above, wherein the system includes at least one host computer for providing a processing task to the small processors, and the method includes the further steps of transferring data base task assignments from the host computer to the small processors and transferring from the small processors assembled processed packets to the host computer.

16. A method competing messages from a plurality of processors in a sorted color based upon priorites of said messages, the messages being generated during completion of asynchronous processing tasks, the method comprising the steps of:

a. assembling, at each said processor, sequences of said messages, each said message having its data content as a sorting criteria;

b. synchronously transmitting said competing messages from said processors concurrently to a priority determining network having a plurality of message receiving nodes;

c. receiving simultaneously a message from each of a pair of said processors at each said message receiving node;

determining a higher priority message of the simultaneously received messages within each said message receiving node solely based upon the data content thereof;

e. determining by the priority determining network a highest priority message among said messages each having a higher priority;

f. transmitting the highest priority message to said processors;

g. synchronously repeating steps e and f until all said competing messages have been completely transmitted.

17. The method as set forth in claim 16 above, further including the steps of starting and stopping an operation by first transmitting start and stop commands of higher priority in competition with other said messages, dynamically prioritizing by said priority determining network the start and stop commands, and delivering the commands to all said processors concurrently.

18. The method as set forth in claim 17 above, including in addition the steps of assembling said messages in sorted suborders at the processors, dynamically prioritizing by said priority determining network all messages pertaining to one suborder, and then repeating the sequence with subsequent suborders.

19. The method as set forth in claim 18 above, including in addition the steps of delivering the priority messages to all said processors concurrently, responding to each said priority message from all processors concurrently, and dynamically prioritizing by said priority determining network the responses before synchronously transmitting further messages.