Compiling computer programs to exploit parallelism without exceeding available processing resources

• US 7,401,329 B2
• Filed: 04/25/2005
• Issued: 07/15/2008
• Est. Priority Date: 04/25/2005
• Status: Active Grant

• Current Assignee: u-blox Cambridge Ltd. (u-blox Holding AG)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: De Rijck, Bert
• Primary Examiner(s): Steelman; Mary
• Assistant Examiner(s): Nahar; Qamrun
• Application Number:
  US11/113,307
• Publication Number:
  US 20060242633A1
• Time in Patent Office: 1,177 Days
• Field of Search: 717/161, 717/151, 717/152, 717/153, 717/154, 717/155, 717/156, 717/158, 717/141, 717/149, 707/100
• US Class Current: 717/161
• CPC Class Codes: G06F 8/456 Parallelism detection

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.

Claims

1. A method of compiling a computer program, said method comprising the steps of:

(i) forming from said computer program a data flow graph corresponding to a plurality of linked vertices, a vertex representing a data processing operation performed by said computer program and a link between vertices representing data flow between data processing operations;

(ii) associating linked vertices within said data flow graph to form clusters of linked vertices corresponding to data processing operations to be scheduled together for execution, said clusters being grown with vertices being added to a cluster until an arbitrary selection of a next vertex to be added to said cluster has to be made between two or more vertices;

(iii) scheduling said vertices within each cluster and then scheduling said clusters for non-overlapped execution to form a current schedule and associating a timestamp with vertices within said clusters indicative of a scheduled time of execution;

(iv) disassociating said vertices within said clusters;

(v) associating a plurality of vertices adjacent in timestamp order to form a candidate cluster, vertices being added to a current candidate cluster until a threshold criteria for said current candidate cluster is exceeded whereupon adding of vertices to said candidate cluster is stopped;

(vi) rescheduling said vertices within said candidate cluster to form a candidate schedule;

(vii) determining if a time for execution of said vertices within said candidate cluster in accordance with said candidate schedule is less than with said current schedule and that said threshold criteria is not exceeded;

(viii) if said time for execution is less and said threshold criteria is not exceeded, then retaining said candidate schedule as a new current schedule for said vertices within said candidate cluster and rescheduling and modifying timestamps for following vertices within said data flow graph to compensate for said new current schedule;

(ix) if said time for execution is not less or said threshold criteria exceeded, then discarding said candidate schedule and retaining said current schedule;

(x) if attempted rescheduling of a sufficient proportion of said vertices of said data flow graph has not been performed, then returning to step (v) to start forming a next candidate cluster starting from a vertex having different starting timestamp;

(xi) if rescheduling of at least one candidate cluster has reduced said time for execution of said computer program sufficiently in accordance with a convergence criteria, then returning to step (v); and

(xii) if rescheduling of at least one candidate cluster has not reduced said time for execution of said computer program sufficiently in accordance with said convergence criteria, then generating an output compiled computer program in accordance with said current scheduling.

2. A method as claimed in claim 1, wherein said threshold criteria is exceeding available processing resources.

3. A method as claimed in claim 1, wherein said computer program is a computer program for controlling processing operations performed by a VLIW device having a plurality of parallel data processing paths to be controlled.

4. A method as claimed in claim 2, wherein said available processing resources comprise one or more of:

available data storage registers;

available execution units;

available memory; and

available data transfer bandwidth.

5. A method as claimed in claim 1, wherein when performing step (xi) and returning to step (v) said associating linked vertices starts with a different timestamp.

6. A method as claimed in claim 1, wherein said arbitrary selection comprises an arbitrary scheduling decision.

7. A method as claimed in claim 1, wherein said step of forming a next candidate cluster starting from a vertex having different starting timestamp comprises forming a next candidate cluster starting from a vertex having next timestamp.

8. A method as claimed in claim 1, wherein said sufficient proportion of said vertices of said data flow graph comprises all of said vertices of said data flow graph.

9. A method as claimed in claim 1, wherein said convergence criteria comprises any reduction in time.

10. A computer program product comprising a computer program recording medium including a computer program operable to control a computer to perform a method as claimed in claim 1.