Compiling computer programs to exploit parallelism without...

Details Compiling computer programs to exploit parallelism without... Compiling computer programs to exploit parallelism without...

2005-04-25

2008-07-15

Steelman, Mary (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S151000, C717S152000, C717S153000, C717S154000, C717S155000, C717S156000, C717S158000

Reexamination Certificate

active

07401329

ABSTRACT:
A compilation technique for computer programs forms a data flow graph of vertices which are analysed to form clusters C for parallel execution where those clusters are added to up to the point at which arbitrary selection between further vertices C, D to be added must be made. This data flow graph with these small clusters is then scheduled such that the clusters do not overlap with other clusters or with vertices outside of clusters. This starting point scheduled data flow graph is then subject to iterative processing whereby a window of timestamps is analysed to see if a candidate cluster formed by the parallel execution of the vertices within that window will result in faster execution whilst avoiding exceeding architectural constraints, such as register occupancy. If the rescheduled vertices do improve performance without exceeding architectural constraints, then this new schedule is adopted and the following vertices are subject to an adjustment in their timestamps to account for this. A window at a different point within the schedule is then adopted and an attempted rescheduling examined. This process is repeated until no progress is being made in reducing the overall execution time.

REFERENCES:
patent: 5367651 (1994-11-01), Smith et al.
patent: 5606698 (1997-02-01), Powell
patent: 5706503 (1998-01-01), Poppen et al.
patent: 5819088 (1998-10-01), Reinders
patent: 6367067 (2002-04-01), Odani et al.
patent: 6457173 (2002-09-01), Gupta et al.
patent: 6611956 (2003-08-01), Ogawa et al.
patent: 7146606 (2006-12-01), Mitchell et al.
patent: 2004/0073899 (2004-04-01), Luk et al.
patent: 2006/0005176 (2006-01-01), Kawahara et al.
patent: 2007/0169042 (2007-07-01), Janczewski
patent: 2007/0198971 (2007-08-01), Dasu et al.
patent: 2008/0034356 (2008-02-01), Gschwind
Chekuri, et al. “Profile-Driven Instruction Level Parallel Scheduling with Application to Super Blocks”, 1996, IEEE, p. 58-67.
Engels, et al. “Parallel Processor Scheduling with Delay Constraints”, 2001, Society for Industrial and Applied Mathematics, p. 577-585.
Leung, et al. “Scheduling Time-Constrained Instructions on Pipelined Processors”, 2001, ACM, p. 73-103.
Xiao, et al. “Instruction Scheduling of VLIW Architectures for Balanced Power Consumption”, 2005, IEEE, p. 824-829.

Affiliated with

Also associated with

Rating

Compiling computer programs to exploit parallelism without... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Compiling computer programs to exploit parallelism without..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compiling computer programs to exploit parallelism without... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3965800