Method of processing a program by parallel processing, and a processing unit thereof

• US 5,410,696 A
• Filed: 03/16/1993
• Issued: 04/25/1995
• Est. Priority Date: 03/16/1992
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Ikeda, Mitsuji, Kiyoshige, Yoshikazu, Seki, Mitsuho
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US08/032,066
• Time in Patent Office: 770 Days
• Field of Search: 364/DIG. 1 MS File, 395/650
• US Class Current: 717/149
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

In order to process a program by parallel processing using a plurality of processors, the program is divided into a plurality of partial programs. Then one or more expressions are derived, the or each expression expressing a relationship between the partial programs, such as which can be executed independently and which require the execution of another partial program. The expression or expressions can then be investigated to determine which has a desired characteristic, such as a characteristic corresponding to uniform loading of the processors. The expression can also be varied, to give more options for the selection of the expression with the desired characteristic. Then the partial programs can be distributed to the processors on the basis of the relationship corresponding to the expression which has the desired characteristic. Furthermore, when the partial programs are being executed by the processors, any processor which has completed its processing broadcasts a signal to the other processors, which may then re-assign one or more of their partial programs. In this way, parallel processing can be carried out quickly, with substantially uniform loading of the processors.

Claims

1. A method of processing a program by parallel processing using a plurality of processors, said method comprising the steps of:

dividing said program into a plurality of sets of instructions, each set of instructions representing a plurality of partial programs;

determining a plurality of relationships for said plurality of partial programs, each relationship of said plurality of relationships corresponding to a relationship between a corresponding two or more partial programs of said plurality of partial programs;

determining a plurality of expressions, each expression of said plurality of expressions corresponding to a respective set of said plurality of sets;

investigating said plurality of expressions to select an expression of said plurality of expressions having a predetermined characteristic; and

assigning said plurality of partial programs to said plurality of processors, for parallel processing thereby, on a basis of a selected set of said plurality of sets corresponding to a selected expression of said plurality of expressions.

2. A method according to claim 1, including the further step of:

displaying said plurality of partial programs corresponding to said selected set of said plurality of sets.

3. A method according to claim 1, including the further step of:

displaying said plurality of relationships corresponding to said plurality of partial programs corresponding to said selected set of said plurality of sets.

4. A method according to claim 1, including the further step of:

allowing at least some of said plurality of expressions to be modified by a user prior to said investigating of said plurality of expressions.

5. A method according to claim 1, wherein said step of assigning of said plurality of partial programs includes a sub-step of determining a processing capability for each of said plurality of processors.

6. A method according to claim 1, wherein said step of determining of said plurality of relationships includes a sub-step of determining an estimated processing time for each partial program of said plurality of partial programs for each set of said plurality of sets, and said step of investigating of said plurality of expressions includes a sub-step of comparing said estimated processing times.

7. A method according to claim 1, wherein said step of investigating of said plurality of expressions is performed sequentially with respect to said plurality of expressions, and said investigating of said plurality of expressions is halted when said expression of said plurality of expressions is selected.

8. A method according to claim 1, wherein said predetermined characteristic is an optimum processing time for parallel processing of said plurality of partial programs of said selected set of said plurality of sets by said plurality of processors.

9. A method of processing a program by parallel processing using a plurality of processors, said method comprising the steps of:

dividing said program into a plurality of partial programs;

determining a plurality of relationships for said partial programs, each relationship of said plurality of relationships corresponding to a relationship between a corresponding two or more partial programs of said plurality of partial programs;

determining a plurality of expressions, each expression of said plurality of expressions corresponding to a respective combination of said plurality of relationships;

investigating said plurality of expressions to select an expression of said plurality of expressions having a predetermined characteristic; and

assigning said plurality of partial programs to said plurality of processors, for parallel processing thereby, on a basis of a combination of said plurality of relationships corresponding to a selected expression of said plurality of expressions.

10. A method of processing a program by parallel processing using a plurality of processors, said method comprising the steps of:

dividing said program into a plurality of partial programs;

determining a plurality of relationships for said plurality of partial programs, each relationship of said plurality of relationships corresponding to a relationship between a corresponding two or more partial programs of said plurality of partial programs;

determining an expression corresponding to a combination of said plurality of relationships;

investigating said expression to determine whether said expression has a predetermined characteristic;

re-dividing said program into a plurality of further partial programs unless said expression has said predetermined characteristic;

repeating steps of said determining of a plurality of relationships, said determining of an expression, and said investigating of said expression, for said plurality of further partial programs; and

assigning one of said plurality of partial programs and said plurality of further partial programs to said plurality of processors, for parallel processing thereby, on a basis of said expression when said expression has said predetermined characteristic.

11. A method according to claim 10, wherein said plurality of further partial programs correspond to subdivisions of said plurality of partial programs.

12. A method of processing a program by parallel processing using a plurality of processors, said method comprising the steps of:

dividing said program into a plurality of partial programs;

determining a plurality of relationships for said plurality of partial programs, each relationship of said plurality of relationships corresponding to a relationship between a corresponding two or more partial programs of said plurality of partial programs;

determining an expression corresponding to a combination of said plurality of relationships;

investigating said expression corresponding to a combination of said plurality of relationships;

investigating said expression to determine whether said expression has a predetermined characteristic;

determining a further plurality of relationships for said plurality of partial programs unless said expression has said predetermined characteristic, said plurality of further relationships corresponding to a further relationship between said corresponding two or more partial programs of said plurality of partial programs;

repeating steps of said determining of an expression, and said investigating of said expression, for said further plurality of relationships; and

assigning said plurality of programs to said plurality of processors, for parallel processing thereby, on a basis of said expression when said expression has said predetermined characteristic.

13. A method of processing a plurality of programs by parallel processing using a plurality of processors, said method comprising the steps of:

dividing said program into a plurality of partial programs;

assigning said plurality of partial programs to said plurality of processors for parallel processing thereby;

generating a completion signal when any processor of said plurality of processors has completed parallel processing of partial programs of said plurality of partial programs assigned thereto, said completion signal being generated by said any processor of said plurality of processors;

detecting said completion signal at all other processors of said plurality of processors; and

transferring at least one partial program of said plurality of partial programs from at least one processor of said all other processors of said plurality of processors to another processor of said plurality of processors.

14. A processing unit for processing a program by parallel processing comprising:

a plurality of processors;

a dividing means for dividing said program into a plurality of sets of instructions, each set of instructions representing a plurality of partial programs;

a relationship determining means for determining a plurality of relationships for said plurality of partial programs, each relationship of said plurality of relationships corresponding to a relationship between a corresponding two or more partial programs of said plurality of partial programs;

an expression determining means for determining a plurality of expressions, each expression of said plurality of expressions corresponding to a respective set of instructions of said plurality of sets of instructions;

an investigating means for investigating said plurality of expressions to select one expression of said plurality of expressions having a predetermined characteristic; and

an assigning means for assigning said plurality of partial programs to said plurality of processors, for parallel processing thereby, on a basis of a selected set of said plurality of sets of instructions corresponding to a selected expression of said plurality of expressions.

15. A processing unit for processing a program by parallel processing, comprising:

a plurality of processors;

a dividing means for dividing said program into a plurality of partial programs;

a relationship determining means for determining a plurality of relationships for said partial programs, each relationship of said plurality of relationships corresponding to a relationship between a corresponding two or more partial programs of said plurality of partial programs;

an expression determining means for determining a plurality of expressions, each expression of said expressions corresponding to a respective combination of two or more relationships of said plurality of relationships;

an investigating means for investigating said plurality of expressions to select an expression of said plurality of expressions having a predetermined characteristic; and

an assigning means for assigning said plurality of partial programs to said plurality of processors, for parallel processing thereby, on a basis of a combination of said plurality of relationships corresponding to a selected said expression of said plurality of expressions.

16. A processing unit for processing a program by parallel processing comprising:

a plurality of processors;

a dividing means for dividing said program into a plurality of partial programs;

a relationship determining means for determining a plurality of relationships for said plurality of partial programs, each relationship of said plurality of relationships corresponding to a relationship between a corresponding two or more partial programs of said plurality of partial programs;

an expression determining means for determining an expression corresponding to a combination of two or more relationships of said plurality of relationships;

an investigating means for investigating said expression to determine whether said expression has a predetermined characteristic;

wherein said dividing means for dividing said program is arranged to re-divide said program into a plurality of further partial programs unless said expression has said predetermined characteristic, said relationship determining means for determining a plurality of relationships is arranged to repeat said determining of a plurality of relationships, said expression determining means for determining an expression is arranged to repeat said determining of an expression, and said investigating means for investigating said expression is arranged to repeat said investigating of said expression, for said plurality of further partial programs; and

wherein said processing unit further includes an assigning means for assigning one of said plurality of partial programs and said plurality of further partial programs to said plurality of processors, for parallel processing thereby, on a basis of said expression when said expression has said predetermined characteristic.

17. A processing unit for processing a program by parallel processing comprising:

a plurality of processors;

a dividing means for dividing said program into a plurality of partial programs;

a relationship determining means for determining a plurality of relationships for said plurality of partial programs, each relationship of said plurality of relationships corresponding to a relationship between a corresponding two or more partial programs of said plurality of partial programs;

an expression determining means for determining an expression corresponding to a combination of said plurality of relationships;

an investigating means for investigating said expression to determine whether said expression has a predetermined characteristic;

wherein said relationship determining means for determining a plurality of relationships is arranged to determine a further plurality of relationships for said plurality of partial programs unless said expression has said predetermined characteristic, said plurality of further relationships corresponding to a further relationship between said corresponding two or more partial programs of said plurality of partial programs, said expression determining means for determining an expression is arranged to repeat said determining an expression, and said investigating means for investigating said expression is arranged to repeat said investigating of said expression, for said further plurality of relationships; and

wherein said processing unit further includes an assigning means for assigning said plurality of programs to said plurality of processors, for parallel processing thereby, on a basis of said expression when said expression has said predetermined characteristic.

18. A processing unit for processing a plurality of programs by parallel processing comprising:

a plurality of processors;

a dividing means for dividing said program into a plurality of partial programs;

an assigning means for assigning said plurality of partial programs to said plurality of processors for parallel processing thereby;

wherein

a completion signal generator for allowing any processor of said plurality of processors to generate a completion signal when said any processor of said plurality of processors has completed parallel processing of said plurality of partial programs assigned thereto;

a detector for allowing remaining processors of said plurality of processors other than said any processor of said plurality of processors to detect said completion signal; and

a transfer for allowing at least one processor of said remaining processors of said plurality of processors other than said any processor of said plurality of processors to transfer at least one of said plurality of partial programs therefrom to said any processor of said plurality of processors.