Patent US5414849A successfully refreshed from Google Patents.
US5414849A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Evaluating method of data division patterns and a program execution time for a distributed memory parallel computer system, and parallel program producing method using such an evaluating method
Assignee: Hitachi Ltd
•
Filing: 1993-06-09
•
Granted: 1995-05-09
•
Expires: 2013-06-09
Abstract
Abstract For candidates of a plurality of data dividing patterns which are expressed by using a data dividing pattern library, in a case where data and program are allocated to each processor by a method which has been predetermined in correspondence to each data dividing pattern and are executed, an evaluating program to measure an amount about the processing time is produced. By executing the evaluating program by a sequential computer, a plurality of data division candidates are compared and evaluated and the optimum data division is selected. Distributed memory parallel programs are produced in accordance with the optimum data division.
Inventors
- 👤 Fujio Yamamoto
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 07:06
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5061; G06F9/5066
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
268 words
A method for evaluating a data dividing patterns used in converting a sequential program into parallel programs, executed by an apparatus, comprising the steps of: (a) dividing data which is processed by a sequential source program to be converted into parallel programs, into a plurality of data groups to be processed in parallel in accordance with one of a plurality of data dividing pattern candidates; (b) allocating each of said data groups to one of a plurality of processors included in a distributed memory parallel computer system, based on a predetermined data allocation rule; (c) allocating each of a plurality of partial processes required to execute a process requested by said sequential source program, to a corresponding one of said processors, based on a predetermined process allocation rule; (d) estimating, as evaluation information of said one of the data dividing pattern candidates for suitably allocating said plurality of data groups and partial processes to each of said plurality of processors, an amount related to an executing time required to execute in parallel the plurality of partial processes as allocated to said processors in the step (c), in a state in which said plurality of data groups are allocated to said processors in said step (b); (e) repeating said steps (a) to (d) with respect to each of others of said plurality of dividing patterns candidates; and (f) assigning said evaluation information to said amount related to said executing time estimated to each of said plurality of dividing patterns candidates based on predetermined priority, and ordering said plurality of dividing patterns candidates with ascending order of said evaluation information.
Claim 2
Independent Claim
268 words
A method for evaluating a data dividing patterns used in converting a sequential program into parallel programs, executed by an apparatus, comprising the steps of: (a) dividing data which is processed by a sequential source program to be converted into parallel programs, into a plurality of data groups to be processed in parallel in accordance with one of a plurality of data dividing pattern candidates; (b) allocating each of said data groups to one of a plurality of processors included in a distributed memory parallel computer system, based on a predetermined data allocation rule; (c) allocating each of a plurality of partial processes required to execute a process requested by said sequential source program, to a corresponding one of said processors, based on a predetermined process allocation rule; (d) estimating, as evaluation information of said one of the data dividing pattern candidates for suitably allocating said plurality of data groups and partial processes to each of said plurality of processors, an amount related to an executing time required to execute in parallel the plurality of partial processes as allocated to said processors in the step (c), in a state in which said plurality of data groups are allocated to said processors in said step (b); (e) repeating said steps (a) to (d) with respect to each of others of said plurality of dividing patterns candidates; and (f) assigning said evaluation information to said amount related to said executing time estimated to each of said plurality of dividing patterns candidates based on predetermined priority, and ordering said plurality of dividing patterns candidates with ascending order of said evaluation information.
Claim 3
Dependent Claim
58 words
A method according to claim 1, wherein said estimating step of said amount related to the executing time includes: generating an evaluating program by adding to said sequential program a program code for collecting, at the time of executing said sequential program, said amount to measure the executing time; and executing said evaluating program by a sequential computer.
Claim 4
Dependent Claim
65 words
A method according to claim 1, wherein said amount related to the executing time includes a first amount related to an executing time required by each processor for execution of a processing assigned to said each processor, and a second amount related to a data transfer time required by said each processor for transfer of data between said each processor and others of said processors.
Claim 5
Dependent Claim
60 words
A method according to claim 1, wherein said amount related to the executing time includes: a distribution of calculation loads among said processors; a number of arithmetic operations executed by each processor for processing a unit amount of reception data received from other processors; and an average amount of reception data received by said each processor during one reception operation.
Claim 6
Dependent Claim
125 words
A method according to claim 1, further having the step of: selecting one of said plurality of dividing pattern candidates for each of a plurality of data processed by said sequential program, so that one combination of dividing pattern candidates are selected for said plurality of data, based on said evaluation information; wherein said steps (a) and (b) are executed for each of said plurality of data, based upon one dividing pattern candidates selected for said each data; wherein said repeating step (e) includes the steps of: repeating said step (f) before repetition of said steps (a) to (d), so that another combination of dividing pattern candidates is selected for said plurality of data; and executing the steps (a) to (d) for said another combination.
Claim 7
Dependent Claim
97 words
A method according to claim 1, further having the step of: registering each of said data dividing patterns into a library each in terms of data dividing functions each indicative of a corresponding relation between an index of an element of an array data to be divided and a number of serial of said processors to which said element should be allocated; and wherein said step (a) includes a step of: selecting one of the data dividing functions registered in said library for array data appearing in the sequential program and to be divided into data groups.
Claim 8
Dependent Claim
40 words
A method according to claim 1, wherein the data group allocation determining step (b) is executed in accordance with a data allocation rule which has been predetermined in correspondence to said one data dividing pattern used in said step (a).
Claim 9
Dependent Claim
52 words
A method according to claim 1, wherein the process allocation step (c) is executed in a manner such that a processing to define a value of data belonging to one of said data groups is allocated to one of said processors to which one processor said one data group has been allocated.
Claim 10
Dependent Claim
54 words
A method according to claim 1, further having the step of selecting one of said plurality of data dividing pattern candidates which is suitable to divide the data of said sequential program as to minimize said executing time, on the basis of amounts each evaluated for each of said plurality of data dividing patterns.
Claim 11
Dependent Claim
60 words
A method according to claim 9, wherein said amount related to the executing time includes: a distribution of calculation loads among said processors; a number of arithmetic operations executed by each processor for processing a unit amount of reception data required from other processors; and an average amount of reception data received by said each processor during one reception operation.
Claim 12
Dependent Claim
37 words
A method according to claim 9, wherein the selecting step of said suitable data dividing pattern candidate is executed further on the basis of a predetermined evaluation reference to determine whether said candidate is omitted or not.
Claim 13
Dependent Claim
31 words
A method according to claim 11, wherein the selecting step of said suitable data dividing pattern candidate is executed further on the basis of characteristics of said distributed memory parallel computer.
Claim 14
Dependent Claim
42 words
A method according to claim 9, further having a step of: displaying results of said estimating each with respect to one of said plurality of data dividing patterns candidates; and selecting said suitable data dividing pattern candidates, as instructed by a user.
Claim 15
Dependent Claim
60 words
A method according to claim 13, wherein said amount related to the executing time includes: a distribution of calculation loads among said processors; a number of arithmetic operations executed by each processor for processing a unit amount of reception data received from other processors; and an average amount of reception data received by said each processor during one reception operation.
Claim 16
Dependent Claim
61 words
A method according to claim 9, further having the steps of: executing again said steps (a) and (b) for said selected data dividing pattern candidate; and generating parallel programs to be executed by said distributed memory parallel computer system from said sequential program, in accordance with results of said steps (a) and (b) executed for said selected data dividing pattern candidate.
Claim 17
Independent Claim
212 words
A method for evaluating an amount related to an executing time of a program to be executed by a distributed memory parallel computer system, executed by an apparatus, the steps including: (a) dividing data which is included in a sequential program and should be processed by a plurality of processors which belongs to said computer system, into a plurality of data groups, in accordance with a predetermined data dividing pattern; (b) allocating each of said plurality of data groups to a corresponding one of said processors; (c) dividing a process executed by said sequential program into a plurality of partial processes to be executed in parallel, and allocating each of said partial processes to one of said processors in such a manner that one of said processors executes a statement to define a value of data belonging to one of the data groups each of which is allocated to said one processor; and (d) evaluating an amount related to an executing required for execution of said partial processes by said processors, including: inserting into said sequential program, data transmission commands and data reception commands both of which are required for execution of said partial processes by said processors; wherein said evaluating is executed based upon the sequential program modified by said inserting.
Claim 18
Independent Claim
212 words
A method for evaluating an amount related to an executing time of a program to be executed by a distributed memory parallel computer system, executed by an apparatus, the steps including: (a) dividing data which is included in a sequential program and should be processed by a plurality of processors which belongs to said computer system, into a plurality of data groups, in accordance with a predetermined data dividing pattern; (b) allocating each of said plurality of data groups to a corresponding one of said processors; (c) dividing a process executed by said sequential program into a plurality of partial processes to be executed in parallel, and allocating each of said partial processes to one of said processors in such a manner that one of said processors executes a statement to define a value of data belonging to one of the data groups each of which is allocated to said one processor; and (d) evaluating an amount related to an executing required for execution of said partial processes by said processors, including: inserting into said sequential program, data transmission commands and data reception commands both of which are required for execution of said partial processes by said processors; wherein said evaluating is executed based upon the sequential program modified by said inserting.
Claim 19
Dependent Claim
131 words
A method according to claim 16, wherein said measuring step (d) further includes the steps of: measuring (1) a total number of data elements which does not belong to one of said data groups assigned to each processor, among data elements which are used by one of the plurality of partial processes assigned to said each processor, (2) a total number of using times by said each processor, of said data elements which does not belong to said one data group assigned to said each processor, (3) a total number of execution of reception operations required in order for said each processor to receive said data elements from other ones of said processors, and (4) a total amount of arithmetic or logical operations executed by one process assigned to each processor.
Claim 20
Dependent Claim
65 words
A method according to claim 16, wherein the measuring step further includes the step of: inserting into the sequential program, first program codes which are necessary to execute said steps (a), (b), and (c), and second program codes which are necessary to measure said amount related to said executing time of said sequential program modified by said inserting of said first and second program codes.
Claim 21
Dependent Claim
20 words
A method according to claim 18, wherein said executing of said modified sequential program is done by a sequential computer.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-05-08 | 1998-11-07 | 1999-05-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-05-08 | 2002-11-07 | 2003-05-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-05-08 | 2006-11-07 | 2007-05-09 | $7700.00 | Window Closed / Lapsed |