Patent US5579494A successfully refreshed from Google Patents.
US5579494A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for detecting possibility of parallel processing and method thereof and a program translation apparatus utilized therein
Assignee: Panasonic Holdings Corp
•
Filing: 1995-02-21
•
Granted: 1996-11-26
•
Expires: 2015-02-21
Abstract
Abstract The present invention provides an apparatus for detecting possibility to process in parallel a program including a loop where iteration processing is executed comprising a simulation unit for simulating each iteration of the loop in the program, a variable storage unit for storing information based on the simulation as to a variable whose value is defined in a program statement in relation with information showing a location where in the program the value of the variable is defined, and a judgement unit for judging whether or not parallel processing is possible by referring to the variable storage unit for information of the location; The present invention further provides a program translation apparatus for generating a program applicable to parallel processing based on the detected possibility of executing the program in parallel comprising the simulation unit, the variable storage unit, the judgement unit, and the program generation means for generating the program applicable to parallel processing when it is judged by the judgement unit that parallel processing of the program is possible.
Inventors
- 👤 Koji Zaiki
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 16:28
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/45
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
150 words
An apparatus for detecting whether iterations of a program loop can be processed in parallel, wherein the program loop includes at least one of a conditional branch statement, a variable appended with a subscript which is determined by a calculation, and a subroutine call statement, the apparatus comprising: simulation means for simulating each iteration of the program loop; variable storage means for storing values of variables, which are defined in program statements executed during simulation of the iterations, each value being stored with information showing both a location in the program where the value of the variable is defined and a number of the simulated iteration in which the variable is defined; and judgment means for judging that parallel processing is possible when, for each simulated iteration, variables whose values are referred to in program statements of a current iteration are defined in preceding program statements within the current iteration.
Claim 2
Independent Claim
150 words
An apparatus for detecting whether iterations of a program loop can be processed in parallel, wherein the program loop includes at least one of a conditional branch statement, a variable appended with a subscript which is determined by a calculation, and a subroutine call statement, the apparatus comprising: simulation means for simulating each iteration of the program loop; variable storage means for storing values of variables, which are defined in program statements executed during simulation of the iterations, each value being stored with information showing both a location in the program where the value of the variable is defined and a number of the simulated iteration in which the variable is defined; and judgment means for judging that parallel processing is possible when, for each simulated iteration, variables whose values are referred to in program statements of a current iteration are defined in preceding program statements within the current iteration.
Claim 3
Dependent Claim
152 words
A parallelism possibility detecting method for detecting whether a program having a plurality of program statements including an iterative loop can be processed in parallel, wherein the program ..loop includes at least one of a conditional branch statement, a variable appended with a subscript which is determined by a calculation, and a subroutine call statement, the method comprising the following steps: simulating each iteration of the loop in the program; storing values of variables that are defined by program statements executed during simulation of the iterations, each value being stored with information showing a location in the program where the value of the variable is defined and the simulated iteration number in which the variable is defined; and judging that parallel processing is possible when, for each simulated iteration, variables whose values are referred to in program statements of a current iteration are defined in preceding program statements within he current iteration.
Claim 4
Dependent Claim
152 words
A parallelism possibility detecting method for detecting whether a program having a plurality of program statements including an iterative loop can be processed in parallel, wherein the program ..loop includes at least one of a conditional branch statement, a variable appended with a subscript which is determined by a calculation, and a subroutine call statement, the method comprising the following steps: simulating each iteration of the loop in the program; storing values of variables that are defined by program statements executed during simulation of the iterations, each value being stored with information showing a location in the program where the value of the variable is defined and the simulated iteration number in which the variable is defined; and judging that parallel processing is possible when, for each simulated iteration, variables whose values are referred to in program statements of a current iteration are defined in preceding program statements within he current iteration.
Claim 5
Dependent Claim
190 words
A program translation apparatus for generating a program applicable to parallel processing if a possibility of executing the program in parallel is detected, wherein the program loop includes at least one of a conditional branch statement, a variable appended with a subscript which is determined by a calculation, and a subroutine call statement, the program translation apparatus comprising: simulation means for simulating each iteration of the program loop; variable storage means for storing values of variables, which are defined in program statements executed during simulation of the iterations, each value being stored with information showing both a location in the program where in the program the value of the variable is defined and a number of the simulated iteration in which the variable is defined; judgment means for judging that parallel processing is possible when, for each simulated iteration, variables whose values are referred to in program statements of a current iteration are defined in preceding program statements within the current iteration; and program generation means for generating the program applicable to parallel processing when it is judged by the judgment means that parallel processing of the program is possible.
Claim 6
Dependent Claim
190 words
A program translation apparatus for generating a program applicable to parallel processing if a possibility of executing the program in parallel is detected, wherein the program loop includes at least one of a conditional branch statement, a variable appended with a subscript which is determined by a calculation, and a subroutine call statement, the program translation apparatus comprising: simulation means for simulating each iteration of the program loop; variable storage means for storing values of variables, which are defined in program statements executed during simulation of the iterations, each value being stored with information showing both a location in the program where in the program the value of the variable is defined and a number of the simulated iteration in which the variable is defined; judgment means for judging that parallel processing is possible when, for each simulated iteration, variables whose values are referred to in program statements of a current iteration are defined in preceding program statements within the current iteration; and program generation means for generating the program applicable to parallel processing when it is judged by the judgment means that parallel processing of the program is possible.
Claim 7
Dependent Claim
210 words
A compiler for receiving a source program and generating an object program that is applicable to parallel processing, comprising: an input unit for inputting the source program; a detector for detecting a loop in the source program, and for further detecting at least one of an array, a subroutine, and a variable in the source program; a memory for storing information relating to the detected items; simulation means for simulating execution of the source program by referring to the stored information, the simulation means registering variables on left sides of instructions in the memory as the instructions are executed during each iteration of the program loop; judgement means for judging whether variables on right sides of instructions have been previously registered, the judgement occurring at the simulation of each instruction, the judgement means determining that parallel processing is possible when all variables on the right sides of instructions for each iteration have been registered for each iteration; and an object program generation unit for generating the object program that is applicable to parallel processing when parallel processing of the loop is judged to be possible, and for generating a general object program that is not applicable to parallel processing if parallel processing of the loop is judged to be impossible.
Claim 8
Dependent Claim
210 words
A compiler for receiving a source program and generating an object program that is applicable to parallel processing, comprising: an input unit for inputting the source program; a detector for detecting a loop in the source program, and for further detecting at least one of an array, a subroutine, and a variable in the source program; a memory for storing information relating to the detected items; simulation means for simulating execution of the source program by referring to the stored information, the simulation means registering variables on left sides of instructions in the memory as the instructions are executed during each iteration of the program loop; judgement means for judging whether variables on right sides of instructions have been previously registered, the judgement occurring at the simulation of each instruction, the judgement means determining that parallel processing is possible when all variables on the right sides of instructions for each iteration have been registered for each iteration; and an object program generation unit for generating the object program that is applicable to parallel processing when parallel processing of the loop is judged to be possible, and for generating a general object program that is not applicable to parallel processing if parallel processing of the loop is judged to be impossible.
Claim 9
Independent Claim
150 words
An apparatus for determining whether a plurality of iterations of a program loop can be processed in parallel, each iteration of the program loop requiring execution of a segment of instructions within the program loop, the apparatus comprising: simulation means for executing the segment of instructions once for each iteration of the program loop to thereby simulate execution of the program loop, the simulation means registering variables on left sides of instructions, and corresponding iteration numbers, as the instructions are executed during each iteration of the program loop; and judgement means for judging whether variables on right sides of instructions have been previously registered, the judgement occurring at the simulation of each instruction, the judgement means further determining that the plurality of iterations of the program loop can be processed in parallel when all variables on the right sides of instructions for each iteration have been registered for each iteration.
Claim 10
Independent Claim
150 words
An apparatus for determining whether a plurality of iterations of a program loop can be processed in parallel, each iteration of the program loop requiring execution of a segment of instructions within the program loop, the apparatus comprising: simulation means for executing the segment of instructions once for each iteration of the program loop to thereby simulate execution of the program loop, the simulation means registering variables on left sides of instructions, and corresponding iteration numbers, as the instructions are executed during each iteration of the program loop; and judgement means for judging whether variables on right sides of instructions have been previously registered, the judgement occurring at the simulation of each instruction, the judgement means further determining that the plurality of iterations of the program loop can be processed in parallel when all variables on the right sides of instructions for each iteration have been registered for each iteration.
Claim 11
Independent Claim
200 words
An apparatus for determining whether a plurality of iterations of a program loop can be processed in parallel, each iteration of the program loop requiring execution of a segment of instructions within the program loop, the apparatus comprising: executing means for executing the segment of instructions once for each iteration of the program loop to thereby simulate execution of the program loop; registering means for registering variables on left sides of instructions as the instructions are executed during each iteration of the program loop, each variable being registered with an iteration number indicating the iteration during which the instruction was executed; data-dependence judgement means for judging whether variables on right sides of instructions have been previously registered, the judging occurring at the simulation of each instruction; and parallelism judgement means for judging that the plurality of iterations of the program loop can be processed in parallel when all variables on the right sides of instructions for each iteration have been registered for each iteration, and for judging that the plurality of iterations of the program loop cannot be processed in parallel when at least one variable on the right side of an instruction has not been registered for an iteration.
Claim 12
Independent Claim
200 words
An apparatus for determining whether a plurality of iterations of a program loop can be processed in parallel, each iteration of the program loop requiring execution of a segment of instructions within the program loop, the apparatus comprising: executing means for executing the segment of instructions once for each iteration of the program loop to thereby simulate execution of the program loop; registering means for registering variables on left sides of instructions as the instructions are executed during each iteration of the program loop, each variable being registered with an iteration number indicating the iteration during which the instruction was executed; data-dependence judgement means for judging whether variables on right sides of instructions have been previously registered, the judging occurring at the simulation of each instruction; and parallelism judgement means for judging that the plurality of iterations of the program loop can be processed in parallel when all variables on the right sides of instructions for each iteration have been registered for each iteration, and for judging that the plurality of iterations of the program loop cannot be processed in parallel when at least one variable on the right side of an instruction has not been registered for an iteration.
Claim 13
Dependent Claim
224 words
A compiler for receiving a source program and generating an object program that is applicable to parallel processing, comprising: an input unit for inputting the source program; a detector for detecting a loop in the source program, and for further detecting at least one of an array, a subroutine, and a variable in the source program; a memory for storing information relating to the detected items; simulation means for simulating execution of the source program by referring to the stored information, the simulation means registering variables that are defined by program statements in the memory as the instructions are executed during each iteration of the program loop, each variable being registered with information on a number of the simulated iteration; judgement means for judging whether variables on right sides of instructions have been previously registered, the judgement occurring at the simulation of each instruction, the judgement means determining that parallel processing is possible when all variables on the right sides of instructions for each iteration have been registered for each iteration; and an object program generation unit for generating the object program that is applicable to parallel processing when parallel processing of the loop is judged to be possible, and for generating a general object program that is not applicable to parallel processing if parallel processing of the loop is judged to be impossible.
Claim 14
Dependent Claim
224 words
A compiler for receiving a source program and generating an object program that is applicable to parallel processing, comprising: an input unit for inputting the source program; a detector for detecting a loop in the source program, and for further detecting at least one of an array, a subroutine, and a variable in the source program; a memory for storing information relating to the detected items; simulation means for simulating execution of the source program by referring to the stored information, the simulation means registering variables that are defined by program statements in the memory as the instructions are executed during each iteration of the program loop, each variable being registered with information on a number of the simulated iteration; judgement means for judging whether variables on right sides of instructions have been previously registered, the judgement occurring at the simulation of each instruction, the judgement means determining that parallel processing is possible when all variables on the right sides of instructions for each iteration have been registered for each iteration; and an object program generation unit for generating the object program that is applicable to parallel processing when parallel processing of the loop is judged to be possible, and for generating a general object program that is not applicable to parallel processing if parallel processing of the loop is judged to be impossible.
References Cited (Backward Citations)
US4833606A
Cited
US5067068A
Cited
US5151991A
Cited
JPH01280862A
Cited
JPH0261727A
Cited
JPH03218528A
Cited
US5230053A
Cited
US5317743A
Cited
US5253255A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-26 | 2000-05-27 | 2000-11-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-26 | 2004-05-27 | 2004-11-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-26 | 2008-05-27 | 2008-11-26 | $7700.00 | Window Closed / Lapsed |