Network to transmit prioritized subtask pockets to dedicated processors

• US 4,814,979 A
• Filed: 07/16/1985
• Issued: 03/21/1989
• Est. Priority Date: 04/01/1981
• Status: Expired due to Term

• Current Assignee: NCR Corporation
• Original Assignee: Teradata Corporation
• Inventors: Neches, Philip M.
• Primary Examiner(s): Zache, Raulfe B.
• Assistant Examiner(s): Lee, Thomas C.
• Application Number:
  US06/755,436
• Time in Patent Office: 1,344 Days
• Field of Search: 340/825.02, 340/825.5, 340/825.52, 370/85, 370/94, 370/60, 379/269, 364/200 MS File, 364/900 MS File
• US Class Current: 718/106
• 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 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.

Claims

1. A multiprocessor system distributing a workload among individual processors and operating with low usage of executive software and inter-processor communication to provide an overall workload processing function divisible into parallel processing subtasks, comprising:

at least one processor system providing tasks for processing in the form of task messages;

interface processor means coupled to receive the task messages from the processor system and including means to transform the task messages into subtask request packets including information as to one or more appropriate recipients;

a plurality of processor modules, each having assigned responsibilities with respect to the workload and each including circuit means responsive to the subtask request packets to determine whether the subtask is appropriate therefor, means for executing an appropriate subtask and means for providing a responsive task result packet after executing the subtask, the task result packet competing for priority with task result packets from at least one other processor module and with the subtask request packets from the interface processor means;

bidirectional network means coupling the interface processor means to the processor modules and the processor modules to each other and including means for concurrently receiving the packets and for determining priority between contending packets and distributing each packet having priority concurrently to all processor modules, whereby the subtasks can be performed by the appropriate one or more processor modules without monitoring the operation of other processors or using software to determine routing for the packets.

2. The system as set forth in claim 1 above, wherein the subtask request packets include hash values characterizing the processing subtasks involved, and wherein the processor modules each comprises table lookup means responsive to the hash values included in a received request packet for recognizing the subtask represented by the request packet.

3. The invention as set forth in claim 2 above, wherein the table lookup means at each processor module comprise random access memory means defining disjoint portions of the workload processing function.

4. A multiprocessor system distributing a workload among individual processors and operating with low usage of executive software and inter-processor communication to provide an overall workload processing function divisible into parallel processing subtasks, comprising:

at least one processor system providing tasks for processing in the form of task messages;

interface processor means coupled to receive the task messages from the processor system and including means to transform the task messages into subtask request packets including information as to appropriate recipients;

and hash values characterizing the processing subtasks involved;

a plurality of processor modules, each comprising table lookup means responsive to the hash values for recognizing the subtask represented by a received subtask request packet, each table lookup means including random access memory means defining disjoint portions of the workload processing function and comprising means defining at least two random access memory sections at each processor module, one section storing data related to a primary function subset of the workload processing function, and the other section storing data related to a backup function subset of the workload processing function, wherein the backup function data for a given processor module duplicates portions of different primary function data for a number of the other processor modules, each processor module having assigned responsibilities with respect to the workload and each processor module including circuit means responsive to the subtask request packets to determine whether the subtask is appropriate therfor, means for executing an appropriate subtask and means for providing a responsive information packet after executing the subtask, the responsive information packet competing for priority with responsive information packets from at least one other processor module; and

bidirectional network means coupling the interface processor means to the processor modules and the processor modules to each other and including means for determining priority between contending packets and distributing each packet having priority concurrently to all processor modules, whereby the subtasks can be performed by the appropriate processor modules without monitoring the operation of other processors or using software to determine routing for the packets.

5. The invention as set forth in claim 4 above, wherein each of the processor modules further comprise a secondary memory containing a portion of the data base for a data base management system.

6. The invention as set forth in claim 4 above, wherein the interface processor means comprises a number of interface processor modules, and the bidirectional network means comprises a plurality of active circuit nodes including means for merging packets from the processor modules into a succession of packets following a predetermined order of priority.

7. The invention as set forth in claim 6 above, wherein the active circuit nodes include control means for transferring such indication to the originating processor module.

8. The invention as set forth in claim 7 above, wherein the network means includes means for transferring messages between the interface processor means and the processor modules, and between the various processor modules with uniform delay in transfer, and wherein the processor modules include means for terminating transmission in response to an indication of unsuccessful transmission.

9. The invention as set forth in claim 8 above, wherein the responses have priorities related to each other and to the subtask request packets from the processor modules, and wherein the network means determine priorities between contending responses.

10. The invention as set forth in claim 9 above, wherein the contending packets, including responses, are concurrent in time, and wherein the processor modules each includes means for initiating packets, including responses, synchronously with other processor modules.

11. A multiprocessor system comprising:

at least one processor system comprising data transmission means, the processor system generating task messages on the data transmission means;

at least one interface processor coupled to the data transmission means to receive task messages from the processor system, and including means to couple request packets for one or more access module processors to an active bus means in response to the received task messages, the at least one interface processor also including means to receive processed information packets from the active bus means, and to provide received processed information from the processed information packet to the processor system on the transmission means;

a plurality of access module processors receiving the request packets from the active bus means and providing packets including processed information packets to the active bus means in response to the received request packets, the at least one interface processor and the access module processors providing packets to the active bus means that initiate concurrently; and

active bus means intercoupling the at least one interface processor and the access module processors for concurrently receiving processed information packets from the access module processors and including means for determining priority between contending packets while uninterruptedly transferring the priority packet with a predetermined time delay to all of the interface processors and access module processors concurrently.

12. The invention as set forth in claim 11 above, wherein said active bus means comprises means for prioritizing contending packets solely in accordance with data content thereof.

13. The invention as set forth in claim 12 above, wherein said access module processors each comprises a secondary storage having a primary portion that stores a subset of a data base, and a backup portion that contains redundant portions of different subsets of the data base that are in other secondary storages.

14. A multiprocessor system comprising:

at least one processor system comprising data transmission means, the processor system generating task messages on the data transmission means;

at least one interface processor including means for providing request packets having destination criteria related to data base subsets stored in one or more access module processors in response to the received task messages, each interface processor being coupled to the data transmission means to receive the task messages from the processor system and to provide processed information packets to the processor system on the transmission means;

a plurality of access module processors, each comprising a secondary storage having a primary portion that stores a subset of a data base and a backup portion that contains redundant portions of different subsets of the database that are in other secondary storages, said access module processors each comprising circuit means for processing the destination criteria in received request packets to determine whether the received request packet is within range of data in the secondary storage for the access module processor, such that the data may be processed and a processed packet containing processed information may be delivered by the access module processor through active bus means to the processor system without prefatory intercommunication and the at least one interface processor and access module processors providing packets concurrently; and

active bus means intercoupling the at least one interface processor and access module processors for receiving concurrent packets from the processors and including means for determining priority between contending packets solely in accordance with the data content thereof while uninterruptedly transferring the priority packet with a predetermined time delay to all of the interface processors and access module processors concurrently.

15. The invention as set forth in claim 14 above, wherein said interface processors each comprises a channel controller for communication with the processor system and the bus means comprises bidirectional means having a terminus including recirculation means for transferring packets from any interface processor or access module processor to all processors.

16. The invention as set forth in claim 15 above, wherein said bus means comprises a tree network having multiple active circuit nodes including base nodes which are coupled to the interface processors and access module processors, the nodes each including means for giving priority to messages in accordance with data content thereof.

17. 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 in each of the different individual processors for providing concurrently initiated competing message packets including priority determining commands and data;

spatially distributed network means connected to the different individual processors for receiving the concurrently initiated competing 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 commands and data in the message packets to continue transfer through the network of those competing message packets having data content priority whereby multiple messages concurrently on the network are prioritized in the time and space domains and single message packets are returned on the network via the return circuit means; and

the plurality of processors each including means responsive to the message packets for responding only to those message packets appropriate to the individual processor, each processor being coupled to the network means and providing processed messages thereto, whereby tasks are automatically accepted at the appropriate processors without requiring inter-processor communications or central determinations of priority and routing.

18. The invention as set forth in claim 17 above wherein the network means includes means for delivering message packets to all processors concurrently.

19. The invention as set forth in claim 18 above, wherein the network means further includes means for indicating loss of priority contention by a message packet on the network means to a transmitting processor.

20. The invention as set forth in claim 19 above, wherein the active circuit means comprises three port devices arranged in a tree and having two downstream ports for receiving contending message packets from different processors and means for determining priority between the contending message packets.

21. The invention as set forth in claim 20 above, wherein the means for indicating loss of priority comprises control lines coupled along the three port devices of the tree back to the processors, and wherein the processors terminate transmission of a losing message packet until the network is available to receive a next message packet.

22. The invention as set forth in claim 21 above, wherein the network means includes means for indicating to the processors an availability to receive message packets and wherein the processors include means for transmitting responses to the network means for prioritized distribution thereby, and further include means for attempting message packet transmission concurrently when the network means is again available.

23. The invention as set forth in claim 22 above, wherein the network means comprises a pair of redundant networks each having a plurality of active circuit means and wherein the processors are each coupled to both of the network means.

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

a number of buffer means, each corresponding to a different one of the processors and coupled to the corresponding processor, each buffer means including at least one dedicated map reference section storing information for determining whether data within a selection field of a message indicates that the message pertains to the corresponding processor individually or as part of a class;

the processors generating messages including a selection field for referencing the dedicated map reference section of the buffer means corresponding associated with all destination processors to which a message pertains;

a number of interface means, each corresponding to a different processor, coupled to the network, to the corresponding processor and to the buffer means the corresponding processor and responsive to a selection field of a received message for referencing the dedicated section in the buffer means associated with the corresponding processor to generate, in response to information stored therein, signals indicating to the corresponding processor whether the selection field specifies that the message is intended for the corresponding processor; and

interconnect network means coupling the processors to the interface means and the buffer means, the network means receiving competing messages from the processors and being responsive to data content of the competing messages for prioritizing the competing messages to deliver a preferred message all the interface means, such that the messages may reach corresponding processors without software interaction with the processors themselves.

25. The invention as set forth in claim 24 above, wherein the buffer means comprises a random access memory having a table lookup section defining the dedicated map reference section.

26. A system for controlling routing of messages between processors in multiprocessor system comprises:

means at each processor for providing a serial message train including destination criteria for a class of processors, which class may include one or more processors in selectable groupings, said means including means for initiating the serial message trains concurrently;

table lookup means at each processor including one or more dedicated sections storing information characterizing the local destination individually and as a member of a plural class;

means coupled to each of the processors for receiving concurrently initiated messages transmitted by the processors, for selecting a single priority message chosen in accordance with data content of the messages from the messages and for delivering to all of the processors the single priority message; and

means at each processor responsive to the destination criteria in the single priority message for addressing a section of the lookup means in response to the destination criteria, and determining from the characterizing information stored in the addressed section whether the particular processor is being addressed individually or as a member of a plural class by the priority message.