Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-02-04
2002-02-26
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C711S100000
Reexamination Certificate
active
06351845
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
This invention relates generally to methods for optimizing performance of computer programs and, more particularly, to methods for analyzing memory use in optimizing performance of computer programs.
B. Description of the Related Art
Computer programmers are continuously searching for ways to make application programs run faster and more efficiently. The performance time of an application may be minimized by reducing the time needed to execute each operation. Many application programs today, however, involve thousands of lines of code and millions of operations thereby making optimization of code a difficult process.
Almost each operation in an application program involves the memory of a computer in some capacity. Memory is “read” when an instruction in the application looks at (and generally uses) the contents of some area of memory without alteration. A “write” to memory takes place when an instruction of the program stores information in an area of memory, overwriting what, if anything, was previously stored in that memory location. Memory accesses may be either “reads” or “writes” to memory. Since a large number of operations of an application program involve accessing memory, performance may be improved by reducing the number of memory accesses performed by an application program.
One important step in optimizing an application program is to understand how the memory of the computer is allocated and how the memory is accessed during operation of the program. Conventionally, programmers study how the application works by, for example, inserting “print” instructions in the program that when executed, output the contents of memory at various points in the program operation, as process known as “instrumentation.” This conventional method produces lengthy printouts of memory accesses that require close further analysis by a programmer and patterns of memory use are not easily detected. Programmers also frequently resort to a painstaking process of hand drawing representations of memory to aid the programmer in visually tracing memory accesses.
Multiple parallel processors may be used to improve the execution time of application programs. Application programs for a multiprocessor environment, however, are complicated to debug and optimize. To write new or modify existing application programs for use on multiple parallel processors, programmers must have a clear understanding of how each operation in a program interacts with memory and which specific memory elements are accessed. By determining where in a program the number of reads and writes is concentrated, programmers can identify portions of application code that need to be optimized. The execution time of these sections of program code with a high number of memory accesses may then be improved, for example, by replacing the section with optimized code or using a special purpose hardware device.
Another method for optimizing application programs is to identify and exploit data dependencies. Data dependencies arise when one computation requires the result of a previous computation. In multiplying two matrices, for example, items in the matrices are multiplied, then those results are summed. To arrive at the correct result, the sum must be performed after the multiplication. Program code that performs a matrix multiplication, will access some memory elements repeatedly. When a matrix multiplication is programmed for parallel processors, programmers must determine when certain memory elements are read for the last time, so that when the program writes to that matrix entry, no matrix information is lost.
There exist hardware and software devices that track accesses to particular memory elements. These devices, however, do not identify whether the particular access is a “read” or a “write.” Furthermore, these conventional devices do not track data dependencies.
There exist also conventional tools that check for memory errors during execution of an application program. Purify™ from Pure Software Inc. and Insure++™ from ParaSoft Corporation are examples of tools that will perform run time memory checks for programs written in the C and C++ programming languages. These conventional tools help detect run-time memory errors arising from improper memory accesses, such as reading or writing beyond the bounds of an array, reading or writing to freed memory, freeing memory multiple times, reading and using uninitialised memory, and forgetting to free memory (called “memory leaks”) once a program has terminated. These tools, however, produce lengthy printouts that need further analysis by a programmer. Furthermore, conventional tools, like Purify and Insure++, notify the programmer only when these error conditions occur. Additionally, conventional memory-usage analysis tools do not use visual displays to track use of individual memory areas.
Conventional tools used to debug application programs may visually display regions of memory using various colors depending on the value in the memory element. Debugging tools are used to identify and correct errors that occur during execution of an application program. These conventional visual debugging tools are useful for analyzing how values in memory change as an application program executes, but do not show when memory is accessed but not changed. For example, it does not show “reads” because during reads the value stored in memory is not changed. Furthermore, debugging tools typically do not show the frequency that a particular memory element is accessed.
Some compiler optimizers do data flow analysis when compiling application programs. Optimization by compiler optimizers, however, is performed at a basic block level and not generally performed for an entire program. Furthermore, compiler optimizers guess at data dependencies merely by looking at the source code of a program, not by running the code. Some data dependencies, however, are not detectable until runtime. Some sophisticated models may make good approximations, but these are still approximations versus actual accesses.
Furthermore, some data dependencies are not always obvious to a compiler that looks only at the source code. For example, in the expression A(I)=A(I)+A(I+1), the data dependency between the last two terms will be recognized by many conventional compilers. However, the following example shows a set of instructions with a data dependency that would not be obvious to most conventional compilers.
Do J=1,10
I=B(j)
A(I)=A(I)+A((B(J+1))
Enddo
This program code adds the i
th
element of array A to another array element, which is determined by B(J+1). If B is an array of independent, unrelated values, the relationship between the last two terms is not easily determined at the time when the instructions are compiled.
Therefore, a need exists for an improved method of optimizing programs by analyzing memory accesses. Furthermore, a need exists for a method of analyzing memory accesses that identifies data dependencies and displaying this information in a manner useful for a programmer.
SUMMARY OF THE INVENTION
Systems, methods, and articles of manufacture consistent with the present invention track accesses to memory during execution of an application program. Additional instructions are inserted into the application program and the instrumented application program is executed. During execution of the instrumented application program, information reflecting different types of memory access operations is generated. This generated information is displayed in a visual form reflecting the different types of memory access operations using a different visual effect for each type of memory access operation.
REFERENCES:
patent: 5613063 (1997-03-01), Eustace et al.
patent: 5689712 (1997-11-01), Heisch
patent: 5787480 (1998-07-01), Scales et al.
patent: 5905488 (1999-05-01), Demers et al.
patent: 5974536 (1999-10-01), Richardson
patent: 6018793 (2000-01-01), Rao
patent: 6085029 (2000-07-01), Kolawa e
Dennie Shaun
Hinker Paul
Powell Mark R.
Sun Microsystems Inc.
Zhen Wei
LandOfFree
Methods, apparatus, and articles of manufacture for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods, apparatus, and articles of manufacture for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods, apparatus, and articles of manufacture for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2984782