Compiling computer programs to exploit parallelism without exceeding available processing resources

摘要

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.