Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-01-13
2001-08-07
Elmore, Reba I. (Department: 2187)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000
Reexamination Certificate
active
06272676
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data processing, and, in particular, to the detection of loop_level parallelism within a sequence of program instructions.
BACKGROUND OF THE INVENTION
In the past computer systems typically executed sequences of instructions in a computer program in a strict sequential order. That is, instructions were executed in the actual order of the computer program.
Executing instructions in strict sequential order presented many limitations on the efficiency of executing instructions. For example, often the microprocessor would sit idle while waiting for the completion of a memory operation (e.g., a memory location being read or written). Meanwhile, subsequent instructions, which were not dependent on the memory operation being completed would nevertheless be required to wait to be executed, even though the microprocessor was not busy.
However, as computer systems and microprocessors have evolved, computer systems now are able to execute programs more efficiently. For example, the microprocessors execute instruction in a pipelined manner. In other words, multiple instructions can be executed simultaneously. That is, while one instruction is being executed, a subsequent instruction can be decoded, and another instruction can be fetched from a memory location.
In addition, advanced computer systems are able to perform multitasking (i.e., simultaneously execute two or more programs in one computer system.) More than one program can run simultaneously in the same computer because of the differences between I/O and processing speed. While one program is waiting for input, instructions in another can be executed. During the milliseconds one program waits for data to be read from a disk, millions of instructions in another program can be executed. For example, in interactive programs, thousands of instructions can be executed between each keystroke on the keyboard.
Moreover, advanced computer systems may also perform multitasking within a single program, commonly referred to as multithreading. That is, multi-threading allows multiple streams of execution to take place concurrently within the same program, each stream processing a different transaction or message.
One example of multi-threading could include the simultaneous execution of the different iterations of a loop in a pointer-based computer program. A loop consist of a set of instructions in a program that are executed repeatedly, either a fixed number of times or until some condition is true or false. Each pass through the set of instructions is referred to herein as an iteration.
The separate iterations of a loop will often operate on data stored in one or more fields in a particular record
101
of a pointer based data structure. Subsequent iterations will either execute data stored in the same record
101
, or alternatively proceed to process one or more fields of another record
103
, which may be connected to the previous record by a pointer
101
e
, as shown in pointer based data structure of FIG.
1
.
As a result, in order to be able to concurrently execute the separate iterations of loop in the pointer based program, it typically should first be determined that the iterations of the loop are not dependent on each other. That is, if a first iteration writes to a particular memory location, and a second iteration reads the same memory location, then the second iteration can not be executed prior to the completion of the first iteration. Otherwise, the second iteration may read invalid data at the memory location to be updated by the first iteration. The determination of whether two or more iterations in a loop of a program operate on the same memory location, and thereby potentially prevent the concurrent execution of the iteration, is sometimes referred to as memory disambiguation.
If it is determined that separate iterations of a loop do not operate on the same memory locations, than the separate iterations are independent and can be scheduled to be executed simultaneously (a.k.a., loop_level parallelism), assuming the respective loop terminates. On the other hand, if separate iterations of a loop could possibly operate on the same memory location (e.g., the same fields within a record), then the iterations should not be simultaneously executed.
Therefore, a need exist for a method of determining whether separate iterations within a loop in a sequence of instructions in a pointer based application are independent because they do not operate on the same memory locations.
SUMMARY OF THE INVENTION
The present invention provides a method for finding loop_level parallelism in a sequence of instructions. In one embodiment, the method includes the steps of determining if a variable which identifies a memory address of a data structure is an induction variable; and determining if execution of the sequence of instructions terminates in response to a comparison of the variable to an invariant value.
REFERENCES:
patent: 5067068 (1991-11-01), Iwasawa et al.
patent: 5109331 (1992-04-01), Ishida et al.
patent: 5121498 (1992-06-01), Gilbert et al.
patent: 5265253 (1993-11-01), Yamada
patent: 5303357 (1994-04-01), Inoue et al.
patent: 5317743 (1994-05-01), Imai et al.
patent: 5450554 (1995-09-01), Zaiki
patent: 5522074 (1996-05-01), Endo
patent: 5577253 (1996-11-01), Blickstein
patent: 5584027 (1996-12-01), Smith
patent: 5797013 (1998-08-01), Mahadevan et al.
Liu,S.-M.; Lo, R.; Chow, F.; “Loop Induction Variable Canoncalization in Parallelizing Compilers”; Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques; pp. 228-237, Oct. 1996.*
Davidson, J.; Jinturkar, S.; “Improving Instruction-Level Parallelism by Loop Unrolling and Dynamic Memory Disambiguation”; Proceedings of the 28th Annual International Symposium on Microarchitecture; pp. 125-132, Nov. 1995.*
Maydan, D.; Hennessy, J.; Lam, M.; “Effectiveness of Data Dependence Analysis”; International Journal of Parallel Programming; vol. 23, No. 1, pp. 63-81, Feb. 1995.*
Larus, J.; “Loop-Level Parallelism in Numeric and Symbolic Programs”; IEEE Transactions on Parallel and Distributed Systems; vol. 4, No. 7, pp. 812-826, Jul. 1993.*
Aho, A.; Sethi, R.; Ullman, J.; “Compilers —Principles, Techniques and Tools”; Addison-Wesley Publishing Company; pp. 638-648,1986.*
M. R. Haghighat,Symbolic Analysis for Parallelizing, Kluwer Academic Publishers (1995), Contents pp. vii-ix, List of Figures pp. xi-xiii, Chapter 4-Induction Variables pp. 35-56.
Girkar Milind
Haghighat Mohammad R.
Blakely , Sokoloff, Taylor & Zafman LLP
Elmore Reba I.
Intel Corporation
LandOfFree
Method and apparatus for finding loop— lever... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for finding loop— lever..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for finding loop— lever... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2544264