Compiler method of exploiting data value locality for computation reuse

Patent metadata

Field	Value
Publication number	US-9361078-B2
Application number	US-68809007-A
Country	US
Kind code	B2
Filing date	Mar 19, 2007
Priority date	Mar 19, 2007
Publication date	Jun 7, 2016
Grant date	Jun 7, 2016

Abstract

A compiler method for exploiting data value locality for computation reuse. When a code region having single entry and exit points and in which a potential computation reuse opportunity exists is identified during runtime, a helper thread is created separate from the master thread. One of the helper thread and master thread performs a computation specified in the code region, and the other of the helper thread and master thread looks up a value of the computation previously executed and stored in a lookup table. If the value of the computation previously executed is located in the lookup table, the other thread retrieves the value from the table, and ignores the computation performed by the thread. If the value of the computation is not located, the other thread obtains a result of the computation performed by the thread and stores the result in the lookup table for future computation reuse.

First claim

What is claimed is:

1. A computer implemented method for computation reuse in a region of software code, the computer implemented method comprising:
identifying a region of software code during runtime which has single entry and exit points and in which a potential computation reuse opportunity exists;
creating a helper thread separate from a master thread for the region of software code, wherein one of the helper thread and master thread performs a computation specified in the region of software code, and wherein the other of the helper thread and master thread looks up a value of the computation previously executed and stored in a lookup table;
responsive to the other of the helper thread and master thread locating the value of the computation previously executed in the lookup table, retrieving the value from the lookup table, wherein the other of the helper thread and master thread ignores the computation performed by the one of the helper thread and master thread; and
responsive to a failure of the other of the helper thread and master thread to locate the value of the computation in the lookup table, obtaining a result of the computation performed by the one of the helper thread and master thread and storing the result in the lookup table for future computation reuse.

2. The computer implemented method of claim 1 , wherein a potential computation reuse opportunity exists if the region of software code comprises a data value locality.

3. The computer implemented method of claim 1 , further comprising:
creating a pool of helper threads when the software code is initialized, wherein each helper thread waits to receive a work item comprising an outlined procedure and corresponding input parameters from the master thread.

4. The computer implemented method of claim 3 , further comprising:
marking a helper thread as unavailable when the helper thread receives a work item from the master thread.

5. The computer implemented method of claim 1 , further comprising:
automatically caching the result of the computation performed by the one of the helper thread and master thread.

6. The computer implemented method of claim 1 , further comprising:
responsive to a failure to identify a region of software code during runtime in which a potential computation reuse opportunity exists, ceasing the computation reuse.

7. A computer implemented method for generating multiple thread code for computation reuse, the computer implemented method comprising:
identifying code regions in a computer program which have single entry and exit points and are executed with data value locality;
estimating a profitability cost of performing computations of each identified code region;
building a candidate list of the code regions for computation reuse based on the estimated profitability cost;
outlining the code regions in the candidate list;
building a lookup table to hold values of computations performed for the code regions in the candidate list;
embedding the code regions in the candidate list with a procedure which spawns a helper thread, wherein an embedded procedure is created, wherein one of the helper thread and a master thread performs computations in the code regions while the other of the helper thread and master thread performs a lookup to locate values of the computations previously stored in the lookup table; and
generating multiple thread code comprising the embedded procedure.

8. The computer implemented method of claim 7 , wherein identifying a code region further comprises:
building a call graph for each process in the computer program;
identifying variables in the code regions which show data value locality; and
determining values of computations for the identified variables.

9. The computer implemented method of claim 8 , wherein the call graph represents calling relationships among subroutines in the computer program.

10. The computer implemented method of claim 8 , wherein building the call graph includes building a control flow graph and a data flow graph.

11. The computer implemented method of claim 8 , wherein the values are determined using dynamic value profiling.

12. The computer implemented method of claim 7 , wherein the code region is a subset of another code region.

13. The computer implemented method of claim 7 , further comprising:
responsive to a determination that no data value locality exists for a given code region, terminating the computation reuse.

14. A data processing system for computation reuse in a region of software code, the data processing system comprising:
a bus;
a storage device coupled to the bus, wherein the storage device contains computer usable code;
at least one managed device coupled to the bus;
a communications unit coupled to the bus; and
a processing unit coupled to the bus, wherein the processing unit executes the computer usable code to identify a region of software code during runtime which has single entry and exit points and in which a potential computation reuse opportunity exists; create a helper thread separate from a master thread for the region of software code to cause one of the helper thread and master thread to perform a computation specified in the region of software code and to cause the other of the helper thread and master thread to look up a value of the computation previously executed and stored in a lookup table; retrieve the value from the lookup table in response to the other of the helper thread and master thread locating the value of the computation previously executed in the lookup table, wherein the other of the helper thread and master thread ignores the computation performed by the one of the helper thread and master thread; and, in response to a failure of the other of the helper thread and master thread to locate the value of the computation in the lookup table, obtain a result of the computation performed by the one of the helper thread and master thread and store the result in the lookup table for future computation reuse.

15. A data processing system for generating multiple thread code for computation reuse, the data processing system comprising:
a bus;
a storage device coupled to the bus, wherein the storage device contains computer usable code;
at least one managed device coupled to the bus;
a communications unit coupled to the bus; and
a processing unit coupled to the bus, wherein the processing unit executes the computer usable code to identify code regions in a computer program which have single entry and exit points and are executed with data value locality; estimate a profitability cost of performing computations of each identified code region; build a candidate list of the code regions for computation reuse based on the estimated profitability cost; outline the code regions in the candidate list; build a lookup table to hold values of computations performed for the code regions in the candidate list; embed the code regions in the candidate list with a procedure which spawns a helper thread to create an embedded procedure, wherein one of the helper thread and a master thread performs computations in the code regions while the other of the helper thread and master thread performs a lookup to locate values of the computations previously stored in the lookup table; and generate multiple thread code comprising the embedded procedure.

16. A non-transitory computer readable storage medium storing a computer program product for computation reuse in a region of software code, the computer program product comprising:
computer usable program code for identifying a region of software code during runtime w

Assignees

• Gao Yaoqing
• Hu Liangxiao
• Zhang Guansong
• Zhao Peng
• IBM

Inventors

• Gao Yaoqing
• Hu Liangxiao
• Zhang Guansong
• Zhao Peng

Classifications

• G06F9/3851

  from multiple instruction streams, e.g. multistreaming · CPC title

• G06F9/383

  Operand prefetching (cache prefetching G06F12/0862) · CPC title

• G06F8/4441 Primary

  Reducing the execution time required by the program code · CPC title