Method for assigning job in parallel processing method and parallel processing method

• US 7,370,328 B2
• Filed: 04/25/2002
• Issued: 05/06/2008
• Est. Priority Date: 04/28/2000
• Status: Expired due to Fees

• Current Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Original Assignee: Honda Motor Co., Ltd. (Honda Motor Company), Taisho Pharmaceutical Company Limited (Taisho Pharmaceutical Holdings Company Limited)
• Inventors: Takashima, Hajime, Miyakawa, Nobuaki, Nagashima, Unpei, Inabata, Shinjiro, Kitamura, Kunihiro, Yamada, Sou
• Primary Examiner(s): Bullock, Jr.; Lewis A.
• Application Number:
  US10/257,913
• Publication Number:
  US 20030204576A1
• Time in Patent Office: 2,203 Days
• Field of Search: 718/1, 718100-108, 709200-253
• US Class Current: 718/105
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• 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

When parallel processing is executed by parallel computers composed of a host computer and a plurality of processors connected to the host computer through a common bus, there is provided a method of assigning jobs to respective processors with high efficiency. A job in which a ratio between a communication time and a calculation time is larger than a predetermined value or larger than a fraction of processors and a job in which a ratio between a communication time and a calculation time is smaller than a predetermined value or smaller than a fraction of processors can be alternately assigned to respective processors. Alternatively, jobs are assigned to respective processors in such a manner that a plurality of processors and a plurality of jobs are divided into a plurality of groups in a one-to-one relation, jobs in which sizes comprising communication time and calculation time and ratios between the communication times and the calculation times approximate to each other may belong to different job groups and the order in which the jobs in which the sizes comprising the communication time and the calculation time and the ratios between the communication times and the calculation times approximate to each other are assigned within respective job groups may differ from each other among a plurality of job groups.

Claims

1. In a parallel processing method for parallelly processing a plurality of jobs comprising communication processing between a host computer and a plurality of processors and calculation processing in said processors by said plurality of processors in a computer system comprising said host computer and said plurality of processors connected to said host computer through a common bus, a job assignment method in a parallel processing method characterized in that jobs are assigned to said processors in such a manner that an average value of ratios between communication times and calculation times of said job falls within a predetermined value;

and

a job assignment method in a parallel processing method characterized in that jobs are assigned to said respective processors in such a manner that an average value of ratios between communication times and calculation times of said jobs becomes equal to 1/(the number of said processors) when a whole communication time of said plurality of jobs is nearly equal to a total amount of calculation times in one job obtained when a plurality of jobs are equally assigned to said plurality of jobs.

2. In a parallel processing method for parallelly processing a plurality of jobs comprising communication processing between a host computer and a plurality of processors and calculation processing in said processors by said plurality of processors in a computer system comprising said host computer and said plurality of processors connected to said host computer through a common bus, a job assignment method in a parallel processing method characterized in that jobs are assigned to said processors in such a manner that an average value of ratios between communication times and calculation times of said job falls within a predetermined value;

and

a job assignment method in a parallel processing method characterized in that jobs in which ratios between communication times and calculation times is larger than said predetermined value or 1/(the number of said processors) and jobs in which ratios between communication times and calculation times are smaller than said predetermined value or 1/(the number of said processors) are alternately assigned to respective processors.

3. In a parallel processing method for parallelly processing a plurality of jobs comprising communication processing between a host computer and a plurality of processors and calculation processing in said processors by said plurality of processors in a computer system comprising said host computer and said plurality of processors connected to said host computer through a common bus, a job assignment method in a parallel processing method characterized in that said plurality of jobs are continuously numbered by integers ranging from N (N is an integer) to M (integer greater than N), a job that is numbered as N+(M−

J−

1) is assigned to the processor as the next job if the number J of the job that has been assigned just before is not greater than (N+M)/2 and a job that is numbered as N+(M−

J) is assigned to the processor as the next job if the number J of the job that has been assigned just before is greater than (N+M)/2, otherwise a job that is numbered as N+(M−

J) is assigned to the processor as the next job if the number J of the job that has been assigned just before is less than (N+M)/2 and a job that is numbered as N+(M−

J−

1) is assigned to the processor as the next job if the number J of the job that has been assigned just before is not less than (N+M)/2 and respective jobs are assigned to processors in such a manner that an average value of ratios between said communication times and said calculation times falls within a predetermined value.

4. In a method for parallel processing of a plurality of jobs, comprising a host computer and a plurality of processors connected by common bus, communication processing between said host computer and said processors, and calculation processing in said processors:

a job assignment method wherein;

said plurality of processors is divided into G (G is an integer not less than

     2) processor groups wherein the number of processors is equal within each group;

said jobs are divided into G job groups in which the number of jobs is equal within each group;

said processor groups and said job groups being associated with each other in a one-to-one relation;

jobs in each job group being assigned to processors within the corresponding processor group;

jobs in which sizes, said sizes comprising communication time and calculation time and ratios between said communication time and said calculation time, are approximately equal to each other belong to different job groups;

and jobs in which said sizes are approximately equal to each other are assigned to processors in such a manner that the assignment order of said jobs within said job groups differ from each other within said plurality of job groups.

5. In a job assignment method in a parallel processing method according to claim 4, a job assignment method in a parallel processing method characterized in that said plurality of jobs are numbered by integers ranging from N (N is an integer) to M (integer greater than N), g-th job group is comprised of jobs of numbers in which remainders of division by G are equal to g when the numbers of said jobs are replaced with numbers sequentially numbered as 0 and respective jobs are assigned to processors in such a manner that an average value of ratios between said communication times and said calculation times falls within a predetermined value.

6. In a job assignment method in a parallel processing method according to claim 5, a job assignment method in a parallel processing method characterized in that job being first assigned to processors within g-th job groups is a job within one of job blocks which are comprised of jobs having the job numbers whose quotients obtained when the job number J is divided by the processor group number G are equal to each other and which are the job blocks having numbers not less than (B/G)×

g and less than (B/G)×

(g+1) within the job blocks numbered with integers not less than 0 and not greater than B=(M−

N+1)/G.

7. In a job assignment method in a parallel processing method according to claim 6, a job assignment method in a parallel processing method characterized in that, when a b-th job block contains a job that has been assigned just before within a g-th job group, a job belonging to (b+1)-th job block is assigned to a processor as the next job of said g-th job group if(b+1)-th job block contains a job of a g-th job group or a job belonging to a 0-th job block is assigned to a processor as the next job of said g-th job group if not, or a job belonging to a (b−

1)-th job block is assigned to a processor as the next job of said g-th job group and a job of the largest number which is not yet assigned within said g-th job group is assigned to a processor as the next job of said g-th job group if not.

8. In a job assignment method in a parallel processing method according to claim 5, a job assignment method in a parallel processing method characterized in that job being assigned first to processors within g-th job groups related to a processor group in which the number of processor elements is m, is a job within one of job blocks which are comprised of jobs having the job numbers whose quotients obtained when the job number J is divided by the processor group number G are equal to each other and which are the job blocks having numbers not less than (B/G/m)×

g and less than (B/G/m)×

(g+1) within job blocks numbered with integers not less than 0 and not greater than B=(M−

N+1)/G.

9. In a job assignment method in a parallel processing method according to claim 8, a job assignment method in a parallel processing method characterized in that, when a b-th job block contains a job that has been assigned just before within a g-th job group, jobs within a b+(B/m)-th job block are assigned to processors as the next jobs of said g-th job group if said b+(B/m)-th job block contains jobs of said g-th job group and jobs within a job group of the number equal to a remainder which is obtained by dividing b+1 with (B/m) if not or jobs within a b−

(B/m)-th job block are assigned to processors as the next jobs of said g-th job group if b−

(B/m) is not less than 0, jobs within a job block, which contain the jobs of the g-th job group, with the largest number among the numbers which remainder obtained being divided by (B/m) is equal to (B/m)−

1 are assigned to processors if b is equal to 0 and jobs within a job block, which contain the jobs of the g-th job group, with the largest number among the numbers in which a remainder obtained being divided by (B/m) is equal to the remainder obtained by divided b+1 with (B/m) are assigned to processors as the next jobs of said g-th job group if b is other numerical value.

10. In a job assignment method in a parallel processing method according to claim 4, a job assignment method characterized in that said plurality of jobs are numbered by integers continuing from N (N is an integer) to M (integer greater than N), g-th group is comprised of jobs in which remainders obtained when job numbers are divided by 2×

G are equal to g and jobs in which remainders obtained when job numbers are divided by 2×

G are equal to (2×

G−

g−

1) in the condition that the numbers of said jobs are replaced with sequential numbers from 0 and respective jobs are assigned to processors in such a manner that an average value of ratios between said communication times and said calculation times falls within a predetermined value.

11. In a job assignment method in a parallel processing method according to claim 10, a job assignment method in a parallel processing method characterized in that job being first assigned to processors within g-th job groups is a job within one of job blocks which are comprised of jobs having the job numbers whose quotients obtained when the job number J is divided by the processor group number G are equal to each other and which are the job blocks having numbers not less than (B/G)×

g and less than (B/G)×

(g+1) within the job blocks numbered with integers not less than 0 and not greater than B=(M−

N+1)/G.

12. In a job assignment method in a parallel processing method according to claim 11, a job assignment method in a parallel processing method characterized in that, when a b-th job block contains a job that has been assigned just before within a g-th job group, a job belonging to (b+1)-th job block is assigned to a processor as the next job of said g-th job group if(b+1)-th job block contains a job of a g-th job group or a job belonging to a 0-th job block is assigned to a processor as the next job of said g-th job group if not, or a job belonging to a (b−

1)-th job block is assigned to a processor as the next job of said g-th job group and a job of the largest number which is not yet assigned within said g-th job group is assigned to a processor as the next job of said g-th job group if not.

13. In a job assignment method in a parallel processing method according to claim 10, a job assignment method in a parallel processing method characterized in that job being assigned first to processors within g-th job groups related to a processor group in which the number of processor elements is m, is a job within one of job blocks which are comprised of jobs having the job numbers whose quotients obtained when the job number J is divided by the processor group number G are equal to each other and which are the job blocks having numbers not less than (B/G/m)×

g and less than (B/G/m)×

(g+1) within job blocks numbered with integers not less than 0 and not greater than B=(M−

N+1)/G.

14. In a job assignment method in a parallel processing method according to claim 13, a job assignment method in a parallel processing method characterized in that, when a b-th job block contains a job that has been assigned just before within a g-th job group, jobs within a b+(B/m)-th job block are assigned to processors as the next jobs of said g-th job group if said b+(B/m)-th job block contains jobs of said g-th job group and jobs within a job group of the number equal to a remainder which is obtained by dividing b+1 with (B/m) if not or jobs within a b−

(B/m)-th job block are assigned to processors as the next jobs of said g-th job group if b−

(B/m) is not less than 0, jobs within a job block, which contain the jobs of the g-th job group, with the largest number among the numbers which remainder obtained being divided by (B/m) is equal to (B/m)−

1 are assigned to processors if b is equal to 0 and jobs within a job block, which contain the jobs of the g-th job group, with the largest number among the numbers in which a remainder obtained being divided by (B/m) is equal to the remainder obtained by divided b+1 with (B/m) are assigned to processors as the next jobs of said g-th job group if b is other numerical value.

15. In a parallel processing method in which molecular orbital calculation for calculating energy of molecule expressed by n (n is a positive integer) contracted shells is executed by a computer system comprising a host computer and a plurality of processors, with respect to all matrix elements F(I, J) of Fock matrix F expressed in the form of a sum concerning all of primitive basis functions contained in contracted basis functions I, J composed of primitive basis functions i, j in a calculation of a sum f(I, J)=f1 (I, J)+f2(I, J), an outermost loop is selected as a loop concerning a combination of said contracted shell R and T which can satisfy relationships of R≦

n max (n max represents the maximum value of numbers assigned to n contracted shells) and T≦

R,

a second loop in the inside of said outermost loop is selected as a loop concerning said contracted shell S,

a third loop in the inside of said second loop is selected as a loop concerning said contracted shell U,

or said second loop is selected as a loop concerning said contracted shell U and said third loop is selected as a loop concerning said contracted shell S,

a range of values which said contracted shell S can take is selected to be not greater than R, a range of values which said contracted shell U can take is selected to be not greater than R,

a predetermined two-electron integral and a part of a predetermined Fock matrix element using the result of said predetermined two-electron integral are calculated at the inside of said third loop, said second and third loops are collected as one job unit and processing is assigned to said processor at said job unit, a parallel processing method characterized in that said jobs are formed in such a manner that a low number is assigned to a job whose orbital quantum number of said contracted shell R is large and a high number is assigned to a job whose orbital quantum number of said contracted shell R is small, wherein

f1(I, J) represents the sum concerning all contracted basis functions of products A1·

P(K, L)·

g(i,j, k, l) with a coefficient A1;

f2(i, j) represents the sum concerning all contracted basis functions of a product A2·

P(K, L)·

g(i, k, j, l) with a coefficient A2,

g(i, j, k, l) represents the function value of a two-electron integral function g expressed by using primitive basis functions i, j, k, l which are components of primitive shells r, s, t, u contained in contracted shell R, D, T, U as indexes; and

P(K, L) represents the element of density matrix P expressed by using a contracted basis function K composed of said primitive basis function k and a contracted basis function L composed of said primitive basis function I as indexes.

16. In a parallel processing method according to claim 15, a parallel processing method characterized in that respective jobs are assigned to each of said plurality of processors in such a manner that an average value of ratios between communication times and calculation times of said job falls within a predetermined value.

17. In a parallel processing method according to claim 16, a parallel processing method characterized in that respective jobs are assigned to each of said processors in such a manner that an average value of ratios between a communication times and a calculation times of said job is equal to 1/(the number of said processor) when a whole communication time of said plurality of jobs and a total of a calculation time of one job obtained when said plurality of jobs is equally assigned to said plurality of processors are nearly equal to each other.

18. In a parallel processing method according to claim 17, a parallel processing method characterized in that each of said plurality of processors has a job in which a ratio between a communication time and a calculation time is larger than said predetermined value or 1/(the number of said processor) and a job in which a ratio between a communication time and a calculation time is shorter than said predetermined value or 1/(the numbers of said processor) assigned thereto alternately.

19. In a parallel processing method according to claim 16, a parallel processing method characterized in that each of said plurality of processors has a job in which a ratio between a communication time and a calculation time is larger than said predetermined value or 1/(the number of said processor) and a job in which a ratio between a communication time and a calculation time is shorter than said predetermined value or 1/(the number of said processor) assigned thereto alternately.

20. In a parallel processing method according to claim 15, a parallel processing method characterized in that said plurality of processors is divided into G (G is an integer not less than 2) processor groups in which the number of said processors is equal within the each group, said plurality of jobs is divided into G job groups in which the number of said jobs is equal within the each group, said processors groups and said job groups are associated with each other in a one-to-one relation and jobs within one job group are assigned to processors within corresponding one processor group, jobs in which sizes comprising said communication time and said calculation time and ratios between said communication times and said calculation times are approximate to each other belong to different job groups of said job group and jobs in which sizes comprising said communication time and said calculation time and ratios between said communication times and said calculation times are approximate to each other are assigned to processors in such a manner that assignment order of said jobs within said job groups differ from each other within said plurality of job groups.

21. In a parallel processing method according to claim 20, a parallel processing method characterized in that a low contracted shell number is assigned to a contracted shell whose orbital quantum number is large and a high contracted shell number is assigned to a contracted shell whose orbital quantum number is small, said job numbers are determined in accordance with a calculation formula of R(R+1)/2+T and numbered with integers continuing from N (N is an integer) to M (integer greater than N) and when said job numbers are replaced with ones numbered sequentially from 0, a g-th job group is composed of jobs of number in which a remainder obtained from division by said G is equal to g, whereby jobs are assigned such that an average Value of ratios between said communication times and said calculation times falls within a predetermined value.

22. In a parallel processing method according to claim 21, a parallel processing method characterized in that job being first assigned to processors within g-th job groups is a job within one of job blocks which are comprised of jobs having the job numbers whose quotients obtained when the job number J is divided by the processor group number G are equal to each other and which are the job blocks having numbers not less than (B/G)×

g and less than (B/G)×

(g+1) within the job blocks numbered with integers not less than 0 and not greater than B=(M−

N+1)/G.

23. In a parallel processing method according to claim 21, a parallel processing method characterized in that job being assigned first to processors within g-th job groups related to a processor group in which the number of processor elements is m, is a job within one of job blocks which are comprised of jobs having the job numbers whose quotients obtained when the job number J is divided by the processor group number G are equal to each other and which are the job blocks having numbers not less than (B/G/m)×

g and less than (B/G/m)×

(g+1) within job blocks numbered with integers not less than 0 and not greater than B=(M−

N+1)/G.

24. In a parallel processing method according to claim 23, a parallel processing method characterized in that, when a b-th job block contains a job that has been assigned just before within a g-th job group, a job belonging to (b+1)-th job block is assigned to a processor as the next job of said g-th job group if (b+1)-th job block contains a job of a g-th job group or a job belonging to a 0-th job block is assigned to a processor as the next job of said g-th job group if not, or a job belonging to a (b−

1)-th job block is assigned to a processor as the next job of said g-th job group and a job of the largest number which is not yet assigned within said g-th job group is assigned to a processor as the next job of said g-th job group if not.

25. In a parallel processing method according to claim 23 a parallel processing method characterized in that, when a b-th job block contains a job that has been assigned just before within a g-th job group, jobs within a b+(B/m)-th job block are assigned to processors as the next jobs of said g-th job group if said b+(B/m)-th job block contains jobs of said g-th job group and jobs within a job group of the number equal to a remainder which is obtained by dividing b+1 with (B/m) if not or jobs within a b−

(B/m)-th job block are assigned to processors as the next jobs of said g-th job group if b−

(B/m) is not less than 0, jobs within a job block, which contain the jobs of the g-th job group, with the largest number among the numbers which remainder obtained being divided by (B/m) is equal to (B/m)−

1 are assigned to processors if b is equal to 0 and jobs within a job block, which contain the jobs of the g-th job group, with the largest number among the numbers in which a remainder obtained being divided by (B/m) is equal to the remainder obtained by divided b+1 with (B/m) are assigned to processors as the next jobs of said g-th job group if b is other numerical value.

26. In a parallel processing method according to claim 20, a parallel processing method characterized in that a low contracted shell number is assigned to a contracted shell whose orbital quantum number is large, a high contracted shell number is assigned to a contracted shell whose orbital quantum number is small, said job numbers are determined in accordance with a calculation formula of R(R+1)/2+T and numbered with integers continuing from N (N is an integer) to M (integer greater than N) and when said job numbers are replaced with ones numbered sequentially from 0, a g-th job group is composed of jobs in which a remainder obtained when a job number is divided by 2×

G is equal to g and jobs in which a remainder obtained when a job number is divided by 2×

G is equal to (2×

G−

g−

1), whereby jobs are assigned such that an average value of ratios between said communication times and said calculation times falls within a predetermined value.

27. In a parallel processing method according to claim 26, a parallel processing method characterized in that job being first assigned to processors within g-th job groups is a job within one of job blocks which are comprised of jobs having the job numbers whose quotients obtained when the job number J is divided by the processor group number G are equal to each other and which are the job blocks having numbers not less than (B/G)×

g and less than (B/G)×

(g+1) within the job blocks numbered with integers not less than 0 and not greater than B=(M−

N+1)/G.

28. In a parallel processing method according to claim 27, a parallel processing method characterized in that, when a b-th job block contains a job that has been assigned just before within a g-th job group, a job belonging to (b+1)-th job block is assigned to a processor as the next job of said g-th job group if(b+1)-th job block contains a job of a g-th job group or a job belonging to a 0-th job block is assigned to a processor as the next job of said g-th job group if not, or a job belonging to a (b−

1)-th job block is assigned to a processor as the next job of said g-th job group and a job of the largest number which is not yet assigned within said g-th job group is assigned to a processor as the next job of said g-th job group if not.

29. In a parallel processing method according to claim 26, a parallel processing method characterized in that job being assigned first to processors within g-th job groups related to a processor group in which the number of processor elements is m, is a job within one of job blocks which are comprised of jobs having the job numbers whose quotients obtained when the job number J is divided by the processor group number G are equal to each other and which are the job blocks having numbers not less than (B/G/m)×

g and less than (B/G/m)×

(g+1) within job blocks numbered with integers not less than 0 and not greater than B=(M−

N+1)/G.

30. In a parallel processing method according to claim 29, a parallel processing method characterized in that, when a b-th job block contains a job that has been assigned just before within a g-th job group, jobs within a b+(B/m)-th job block are assigned to processors as the next jobs of said g-th job group if said b+(B/m)-th job block contains jobs of said g-th job group and jobs within a job group of the number equal to a remainder which is obtained by dividing b+1 with (B/m) if not or jobs within a b−

(B/m)-th job block are assigned to processors as the next jobs of said g-th job group if b−

(B/m) is not less than 0, jobs within a job block, which contain the jobs of the g-th job group, with the largest number among the numbers which remainder obtained being divided by (B/m) is equal to (B/m)−

1 are assigned to processors if b is equal to 0 and jobs within a job block, which contain the jobs of the g-th job group, with the largest number among the numbers in which a remainder obtained being divided by (B/m) is equal to the remainder obtained by divided b+1 with (B/m) are assigned to processors as the next jobs of said g-th job group if b is other numerical value.

31. In a parallel processing method according to claim 15, a parallel processing method characterized in that a low contracted shell number is assigned to a contracted shell whose orbital quantum number is large and a high contracted shell number is assigned to a contracted shell whose orbital quantum number is small, said job numbers are determined in accordance with a calculation formula of R(R+1)/2+T and numbered with integers continuing from N (N is an integer) to M (integer greater than N), if a number J of a job that has been assigned just before is not greater than (N+M)/2, then a job whose number is N+(M−

J−

1) is assigned as the next job and if a number J of a job that has been assigned just before is greater than (N+M)/2, then a job whose number is N+(M−

J) is assigned as the next job, or if a number J of a job that has been assigned just before is smaller than (N+M)/2, then a job whose number is N+(M−

J) is assigned as the next job and if a number J of a job that has been assigned just before is not less than (N+M)/2, then a job whose number is N+(M−

J−

1) is assigned as the next job, whereby jobs are assigned such that an average value of ratios between said communication times and said calculation times falls within a predetermined value.