Method of dynamically allocating processors in a massively parallel processing system

• US 5,103,393 A
• Filed: 06/29/1990
• Issued: 04/07/1992
• Est. Priority Date: 06/29/1990
• Status: Expired due to Term

• Current Assignee: Compaq Information Technologies Group LP (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Miller, Brad, Leibholz, Daniel, Harris, Jonathan P.
• Primary Examiner(s): Kriess, Kevin A.
• Application Number:
  US07/545,857
• Time in Patent Office: 648 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 709/226
• 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

Abstract

An "n" dimensional mesh-connected massively parallel processing system uses pointers to connect requesting processors to allocated processors, and also, to access the allocated processors. The requesting and allocated processors are connected by (i) storing in the requesting processor or in a system controller a pointer which points to the allocated processors as a group and (ii) storing in each of the allocated processors, in a designated memory location, an assigned-marker, or an identifier which identifies the processor as a member of the identified group. When one or more requesting processors require connection to free processors, a request is sent to each processor in the system asking each of them to determine if it is free. Each of the processors which is free then assigns itself indices relating to its position in the mesh and its position relative to other free processors. Each free processor sends its indices to a rendezvous processor associated with the requesting processors, and the rendezvous processor allocates the free processors to a requesting processor based on the connection requirements of that requesting processor and the indices. If several requesting processors request connection to blocks of free processors, the rendezvous processor allocates non-overlapping blocks by assigning to the requesting processors only those free processors with indices which are modulo the associated connection requirement.

Claims

1. A method of operating a multi-dimensional mesh-connected processing system which includes a plurality of processors, wherein the processors dynamically allocate contiguous "n"-dimensional configurations of available, or free, processors to request processors under the control of a system controller, the method including the steps of:

A. at the instruction of the system controller

i. numbering the requesting processors;

ii. sending the addresses of the requesting processors and their connection requirements to designated rendezvous processors associated with the numbers assigned in step A. i.; and

iii. sending to each of the other processors in the system, a request containing instructions which direct each of the other processors to determine if it is free;

B. each of the other processors, in response to the receipt of such a request, determining individually if it is free, and if it is free

i. numbering itself by

a. assigning itself a first index associated with a first dimension which indicates the number of free processors which are contiguous with it in the first dimension;

b. assigning itself a next index associated with a particular dimension which indicates the number of free processors which are contiguous with it in the particular dimension;

c. repeating step b for the remaining n-2 dimensions, such that each free processor has associated with it n indices; and

ii. if it has indices which indicate that it is contiguous with a number of free processors which satisfies the connection requirement of a requesting processor sending its address and indices to the rendezvous processors;

C. each rendezvous processor, in response to the receipt of address and connection requirements from the requesting processors and address and index information from the free processors allocating to each requesting processor from which it received a connection request an n-dimensional block of free processors, the rendezvous processor sending to each of the requesting processors the address of a free processor which has indices which together are greater than or equal to the number of processors requested by that requesting processor;

each requesting processor thereafter sending to each free processor allocated to it an identifier which identifies the allocated processor as a processor assigned to a particular task.

2. The method of operating the multi-dimensional mesh-connected processing system of claim 1, wherein said method further includes the steps of:

D. under the control of the system controller, if any requesting processors do not have allocated to them free processors after the rendezvous processors allocate the available free processors, sending a second request to the other processors instructing each of the other processors to look at a particular section of its memory to determine if that section is free, and

E. repeating steps B and C of claim 1 with each of the other processors which have the particular section of its memory free identifying itself as a free processor.

3. The method of operating the multi-dimensional mesh-connected processing system of claim 1, wherein

a. the step of each free processor with indices greater than or equal to the connection requirements sending address and index information to a rendezvous processor further includes

i. each of the free processors determining an associated individual block index by multiplying together indices associated with the location of the free processor in the mesh, and

ii. each of the free processors sending its block index together with its address to the rendezvous processor;

and

b. the step of the rendezvous processor allocating free processors to a requesting processor, further includes the rendezvous processor allocating to a requesting processor the free processor with the smallest block index.

4. The method of operating the multi-dimensional mesh-connected processing system of claim 1, wherein the step of each free processor assigning itself a first index includes:

a. each free processor assigning itself a first index of "1" and each processor which is not free assigning itself a first index of "0";

b. each processor sending a copy of its first index to its neighbor 2ⁱ processors away from it in an orientation associated with the first dimension, where i" is the count of an iteration counter and i equals 0 for this iteration;

c. each processor which has a first index greater than or equal to 2ⁱ updating its index by adding to it the received index;

d. incrementing the count of the iteration counter; and

e. repeating steps a-d until i equals ##STR1## where P is the number of processors in the orientation, corresponding to the first dimension.

5. The method operating the multi-dimensional mesh-connected processing system of claim 4, wherein the step of having each free processor assign itself a next index includes:

a. each of the free processors with a first index which is greater than or equal to a connection requirement along a first dimension assigning itself a next index of "1" and each of the processors with a first index which is less the connection requirement along the first dimension assigning itself a next index of "0";

b. each processor sending a copy of its next index to its neighbor 2ⁱ processors away from it in an orientation associated with the next dimension, where "i" is the count of an iteration counter and i equals 0 for this iteration;

c. each processor which has a next index greater than or equal to 2ⁱ updating its next index by adding to the next index the received index;

d. incrementing the count of the iteration counter; and

e. repeating steps a-d until i equals ##STR2## where P is the number of processors in the orientation corresponding to this next dimension.

6. The method operating the multi-dimensional mesh-connected processing system of claim 5, wherein the step of each free processor assigning itself a next index includes repeating steps a-e of claim 5 for each of the remaining dimensions of the required connection, wherein each free processor with assigned indices which are greater than or equal to the connection requirements in the associated dimensions assigning itself a next index of "1" in step a and each processor with any assigned indices which are less than the corresponding connection requirements in any of the associated dimensions assigning itself a next index of "0".

7. The method of operating the multi-dimensional mesh-connected processing system of claim 1, wherein the step of each free processor assigning itself a first index includes:

a. each free processor assigning itself a first index of "1" and each processor which is not free assigning itself a first index of "0";

b. each processor sending a copy of its first index to its neighbor 2ⁱ processors away from it in an orientation associated with the first dimension, where "i" is the count of an iteration counter and i equals 0 for this iteration;

c. each processor which has a first index greater than or equal to 2ⁱ updating its index by adding to the index the received index;

d. incrementing the count of the iteration counter; and

e. repeating steps a-d until 2ⁱ is greater than or equal to the corresponding dimension of the correction requirement.

8. The method of operating the multi-dimensional mesh-connected processing system of claim 7, wherein the step of having each free processor assign itself a next index includes:

a each of the processors with a first index which is greater that or equal to a connection requirement along a first dimension assigning itself a next index of "1" and each of the processors with a first index which is less the connection requirement along the first dimension assigning itself a next index of "0";

b. each processor sending a copy of its next index to its neighbor 2ⁱ processors away from it in an orientation associated with a next dimension, where "i" is the count of an iteration counter and i equals 0 for this iteration;

c. each processor which has a next index greater than or equal to 2ⁱ updating its next index by adding to the next index the received index;

d. incrementing the count of the iteration counter; and

e. repeating steps a-d until 2ⁱ is greater than or equal to the corresponding dimension of the connection requirement.

9. The method operating the multi-dimensional mesh-connected processing system of claim 7, wherein the step of each processor assigning itself a next index includes repeating steps a-e of claim 7 for each of the remaining dimensions of the required connection, wherein each processor with assigned indices which are greater than or equal to the connection requirements in the associated dimensions assigning itself a next index of "1" in step a and each processor with assigned indices which are less than the corresponding connection requirements assigning itself a next index of "0".

10. The method operating a multi-dimensional mesh-connected processing system of claim 3, wherein the step of the other processors sending their block indices to a rendezvous processor includes having only the processors with indices which are modulo the required corresponding dimension of the connection requirement send their block indices and addresses to the rendezvous processor.

11. The method of operating the multi-dimensional mesh-connected processing system of claim 3, wherein the step of the other processor sending its block index to a rendezvous processor further includes the step of each of the other processors with a block index comparing its block index with the block indices of other processors and numbering itself in correspondence with the relative value of its index and sending its number to the rendezvous processor along with its address.

12. The method of operating the multi-dimensional mesh-connected processing system of claim 10, wherein the step of the other processor sending its block index to the rendezvous processor further includes the step of each of the other processors with a block index comparing its block index with the block indices of the other processors and numbering itself in correspondence with the relative value of its index and sending its number to the rendezvous processor along with its address.

13. A method of operating a massively parallel processing system which includes a plurality of processors, wherein said processors dynamically allocate contiguous d-by-e blocks of available, or free, processors to requesting processors which require access to additional processors, the method including the steps of:

A. the requesting processors

i. numbering themselves;

ii. sending their addresses to designated rendezvous processors associated with the numbers assigned in step A.i; and

iii. sending a request to the other processors in the system instructing the other processors to determine if they are free;

B. each of the other processors, in response to the receipt of a request

i. determining if it is free;

ii. if it is free assigning itself vertical and horizontal indices which indicate the number of free processors which are contiguous with it in the vertical and horizontal directions, respectively;

iii. the other processors which have vertical indices which are multiples of "d" and horizontal indices which are multiples of "e" determining the product of their individual vertical and horizontal indices; and

iv. each of those with a product sending its address and product to the rendezvous processors;

C. each of the rendezvous processors;

i. allocating a block of free processors to each requesting processor, the block being associated with a free processor which sent the product and address information;

ii. sending to each requesting processor the addresses of the free processors allocated to it;

the requesting processors thereafter sending to the free processors allocated to them identifiers which identify the allocated processors as processors assigned to a particular task.

14. The method of operating a massively parallel processing system of claim 13, wherein the step of each processor assigning itself a vertical index includes:

a. each free processor assigning itself a vertical index of "1" and each processor which is not free assigning itself a vertical index of "0";

b. each processor sending a copy of its vertical index to its neighbor 2ⁱ processors below it, where "i" is the count of an iteration counter and i equals 0 for this iteration;

c. each processor which has a vertical index greater than or equal to 2ⁱ updating its index by adding to it the received index;

d. incrementing the count of the iteration counter; and

e. repeating steps a-d until i equals ##STR3## where P is the number of processors in the vertical orientation.

15. The method of claim 13, wherein the step of each processor assigning itself a horizontal index includes:

a. each processor with a vertical index which is greater than or equal to "d" assigning itself a horizontal index of "1" and each of the other processors assigning itself a horizontal index of "0";

b. each processor sending a copy of its horizontal index to its neighbor 2ⁱ processors away from it in the horizontal orientation, wherein "i" is the count of an iteration counter and i equals 0 for this iteration;

c. each processor which has a horizontal index greater than or equal to 2ⁱ updating its index by adding to the index the received index;

d. incrementing the count of the iteration counter; and

e. repeating steps a-d until equals ##STR4## where P is the number of processors in the horizontal orientation.

16. A method of operating an "n"-dimensional mesh-connected processing system which includes a plurality of processors, wherein the processors dynamically allocate contiguous "n"-dimensional configurations of free processors to a requesting processor by:

A. the requesting processor sending a request to the other processors in the system instructing the other processors to determine if they are free;

B. each of the other processors which are free, in response to the receipt of a request, assigning to itself a first index corresponding to a predetermined first orientation, the index indicating the number of contiguous free processors preceding and including that processor in a predetermined ordering of the processors in the first orientation;

C. each of the other processors with a first index which is greater than or equal to the corresponding dimension of the required configuration, assigning to itself a second index corresponding to a second orientation, the second index indicating the number of contiguous free processors preceding and including that processor in a predetermined ordering of the processors in the second orientation;

D. each of the other processors with a previous index which is greater that or equal to the corresponding dimension of the required configuration, assigning itself a next index corresponding to a next orientation, the next index indicating the number of contiguous free processors preceding and including that processor in a predetermined ordering of the processors in the corresponding orientation;

E. each of the other processors repeating step D for each of the remaining n dimensions;

F. each of the processors with a first index that is equal to or greater than the corresponding dimension of the required configuration and n indices which are equal to or greater than the other dimensions of the required configuration determining a block index, which is the product of coordinates associated with the processor based on its location within the mesh;

G. each of the processors with a block index determining which of the processors has the smallest block index;

H. the processor with the smallest block index sending its address to a rendezvous processor which is associated with the requesting processor; and

I. the rendezvous processor allocating a block to the requesting processor by sending to it the address of the processor with smallest block index.