Abstract | ||
---|---|---|
The execution time estimation of programs plays an important role in parailelizing compilers. In this paper, we present a recursive approach aimed at predicating lower bounds on the minimum times taken to execute pro. gram traces on high-performance machines with heterogeneous functional units. Our approach considers the execution influence between different types of processing resources. The algorithm implemented analyzes the execution delays incurred due to heterogeneous resource constraints and accumulates these delays along the paths they propagate, thus establishing a tighter lower time bound for a given program trace. To evaluate the performance of this algorithm., we use the computed bound to develop a new branch-and-bound algorithm for obtaining an optimal solution. Experimental results show that the deviation of our estimation from the optimal solution is very small. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1145/330560.331005 | SAC |
Keywords | Field | DocType |
program trace,recursive time estimation algorithm,resource constraint,heterogeneous computing,functional unit,lower bound,parallel algorithms,branch and bound algorithm,bulk synchronous parallel | Parallel algorithm,Computer science,Parallel computing,Symmetric multiprocessor system,Bulk synchronous parallel,Recursion | Conference |
ISBN | Citations | PageRank |
0-89791-969-6 | 0 | 0.34 |
References | Authors | |
11 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dingchao Li | 1 | 1 | 2.76 |
Yuji Iwahori | 2 | 159 | 56.83 |
Naohiro Ishii | 3 | 461 | 128.62 |