Dynamically partitionable parallel processors

• US 4,925,311 A
• Filed: 02/10/1986
• Issued: 05/15/1990
• Est. Priority Date: 02/10/1986
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata Corporation
• Inventors: Hartke, David H., Woodcock, Darryl L., Papachristidis, Alexandros C., Baran, Richard J., Neches, Philip M.
• Primary Examiner(s): Zache, Raulfe B.
• Assistant Examiner(s): Mills, John G.
• Application Number:
  US06/828,440
• Time in Patent Office: 1,555 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 718/100
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A system for dynamically partitioning processors in a multiprocessor system intercoupled by a network utilizes, in association with each processor, a network accessible, locally changeable memory section. An available one of a number of common dynamic group addresses in each of the memories is reserved for a subgroup for the performance of subtasks within an overall task, and members of the group are designated as they receive messages to be processed. The members then locally update status words which establish membership, group validity and semaphore conditions, so that transactions may be initiated, coordinated and terminated with minimum involvement of processors that have no relevant subtasks. When the full task is completed the dynamic group is relinquished for use when a new task is to be undertaken. The system enables many tasks to be carried out concurrently with higher intercommunication efficiency.

Claims

1. A system for dynamically partitioning a plurality of parallel processors into different subcombinations for the performance of specific transactions involving limited and variable groupings of processors, comprising:

a plurality of processors, at least some of the processors including means for establishing a sequence of steps for a given transaction, each of the processors including a network interface having a network accessible random access memory storing a fixed length status word at each of a plurality of dynamic grouping addresses;

a network coupled to each of the processors at the network interface thereof and providing messages from any processor concurrently to the processor network interface of all processors, the messages including data for testing the status words at selected dynamic grouping addresses and for establishing membership of a selected processor in one or more groups of a selected dynamic grouping;

the processors each including means for modifying the status words at selected dynamic grouping addresses in their network accessible memory in accordance with the transaction step being performed thereat;

such that a transaction can be carried out at selected processors using processing time only at the selected processors, other processors being isolated from messages received from the network by determining at the network interface whether or not the processor is a participant in a dynamic grouping, and its status relative to the transaction.

2. A system as set forth in claim 1, wherein the status words identify group availability and processor membership and include a semaphore for testing group status.

3. A system as set forth in claim 2, wherein the network interface at each processor includes means for defining a plurality of process classes, preset over a substantial interval and addressable with destination selection words, within which class the dynamic groupings are transitory subsets.

4. A system as set forth in claim 3, wherein the status words include an abort combination such that the processors in the dynamic grouping may be advised of the invalidity of the transaction being undertaken.

5. A system as set forth in claim 4, wherein the status words are three bit codes and include a combination identifying a non-assigned condition.

6. A system as set forth in claim 5, wherein a processor which establishes a step sequence for a given transaction provides a message including an indication to processors that are to be part of a dynamic grouping, and further includes means for testing the dynamic grouping addresses to determine those which are available for assignment, and wherein those processors which are not part of a dynamic grouping return not applicable responses to status queries pertaining to the dynamic grouping.

7. A system for dynamically partitioning tasks, and steps within tasks, among a plurality of processors which perform assignments asynchronously and communicate by sending competing messages concurrently to other processors via a network which sorts in accordance with data content, comprising:

network interface means individually associated with each different processor and including memory means for providing a plurality of network accessible dynamic group storage locations, each having a fixed number of binary digits, each processor being simultaneously assignable to one or more dynamic groups;

the processors including means for identifying via the network those processors having responsibility for different parts of a task and concurrently entering fixed length status words in an available and common dynamic group storage location for each processor; and

the processors including means cooperative with the network interface means for locally changing the status words in accordance with (1) the status of the task being undertaken at that processor and (2) while testing is being undertaken.

8. A system as set forth in claim 7, wherein the processors include interface processor means for partitioning steps of a task to different ones of the processors, hash memory section in the memory means in each of the network interface means, and means for generating a destination selection word for addressing the hash memory section and the dynamic group storage location.

9. A system as set forth in claim 8, wherein the interface processor means comprises means for providing a signal to indicate that a processor should join a dynamic group.

10. A system for dynamically partitioning tasks among a plurality of parallel processors interconnected by network means, comprising:

individual interface means intercoupling the different ones of the processors and the network means and including means for storing a plurality of network accessible dynamic group status words in specific locations; and

the processors including means for partitioning a task to those other processors taking part in the task each processor being a member of at least one dynamic group by controlling word patterns in a specific location in the interface means for those processors involved in the task;

the interface means including means for intercommunicating with other processors as to the task being performed by addressing the specific location; and

the processors including means to locally update the status word in the specific location to reflect changes in the status of the step being performed thereat.

11. A system as set forth in claim 10, wherein the status word includes at least one digit constituting a semaphore, at least one digit representing whether the processor is a member of the dynamic group and at least one digit representing whether the group is reserved or not.

12. A method of carrying out transactions in a multiprocessor system in which processors are addressed concurrently via a network and identify locally whether a message is intended for them, and in which two or more processors are used in a transaction sequence involving multiple steps, comprising the method steps of:

denoting each processor involved in a transaction as a member of at least one dynamic group by a locally stored, network accessible status word while distributing steps to be performed to the processors;

locally maintaining an updated status word for each particular transaction in accordance with the step to be performed at each processor involved in the transaction; and

relinquishing the status word from all affected processors when the transaction is complete.

13. A method as set forth in claim 12, wherein the status word is stored in one of a plurality of network addressable locations and includes a semaphore bit that may be externally tested from the network.

14. A method as set forth in claim 13, including the further step of distributing steps to be performed within the transaction sequence by using the dynamic group identification, and monitoring the status of the transaction on a global basis by testing the semaphore bits at the processors involved.

15. A method as set forth in claim 14, wherein the status words are one of a fixed number of predetermined combinations denoting assignability to a group, validity of the group, membership in the group, relinquishment of membership in the group, abort conditions and completion of the assigned transaction step.

16. A method of partitioning related assignments among a number of processors which concurrently process different assignments in asynchronous fashion and which communicate on a data priority basis with other processors via a network, comprising the steps of:

sequencing, at an originating processor, a task to be performed;

establishing by the originating process an available common reference identity for all processors, the common identity being in the form of an externally accessible memory address;

transmitting an assignment to a first execution processor from the originating processor, the assignment including a designation of membership in at least one dynamic group for the memory address;

verifying at the first execution processor that the assignment is not in conflict with other assignments while concurrently locally entering a globally accessible semaphore at the memory address such that an indication is provided that verification is in process;

transmitting further, related, assignments to additional execution processors including a designation of membership in at least one dynamic group for the memory address;

performing the assignments at the execution processors in accordance with priorities and prior assignments;

returning the completed assignments from the execution processors to the originating processor by identifying the selected memory address at the originating processor;

locally changing, at the completion of return of each assignment, the contents of the selected memory address to reflect completion status of the member of the dynamic group;

checking at the completion of each assignment to determine if all assignments related to the dynamic group have been completed; and

relinquishing the dynamic group and the selected memory address when the task involving the successive assignment has been completed.

17. A method as set forth in claim 16, including the steps of identifying an abort condition by changing the group status to invalid while retaining the semaphore, and locally restoring data at the execution processors to their preassignment states.

18. A method as set forth in claim 17, wherein any of the processors can be an originating processor and where any number of assignments can be parsed to different execution processors.

19. A method as set forth in claim 18, including the step of providing a plurality of memory addresses for use in identifying assignment, membership status and semaphore status as to different dynamic groups.

20. A method as set forth in claim 19, wherein the memory addresses have three binary digits each, the binary digits being individually related to group assignment, membership status and semaphore respectively, and wherein combinations of the binary digits represent different operating states as to the performance of an assignment.