Name
Abstract | ||
|---|---|---|
Multi-dimensional systems containing nested loops are widely used to model scientific applications such as image processing, geophysical signal processing and fluid dynamics. However, branches within these loops may degrade the performance of pipelined architectures. This paper presents the theory, supporting hardware and experiments of a novel technique, based on multi-dimensional retiming, for reducing pipeline hazards caused by branches within nested loops. This technique, called ``Multi-Dimensional Branch Anticipation Scheduling'', is able to achieve near-optimal schedule length for nested loops containing branch instructions. It transforms a multi-dimensional conditional data flow graph representing the problem, carries out conditional resource sharing and reduces additional hardware requirements incurred by propagation of branch control signals along the schedule. Such propagation is accomplished by ``Branch Anticipation Bits'' (babits). We further analyze the intricacies of branch anticipation control logic and show that the incurred hardware complexity is low. Thus we demonstrate the efficiency of the algorithm and feasibility of hardware support through a series of experiments. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1109/GLSV.1997.580532 | Great Lakes Symposium on VLSI |
Keywords | Field | DocType |
conditional resource sharing,branch control signal,hardware support,branch instruction,nested loop,additional hardware requirement,branch anticipation bits,multi-dimensional branch anticipation scheduling,branch anticipation control logic,hardware complexity,fluid dynamics,hardware,scheduling,scheduling algorithm,resource management,nested loops,parallel processing,signal processing,multidimensional systems | Retiming,Fair-share scheduling,Computer science,Anticipation,Scheduling (computing),Parallel computing,Image processing,Real-time computing,Computer hardware,Geophysical signal processing,Nested loop join,Multidimensional systems | Conference |
ISSN | ISBN | Citations |
1066-1395 | 0-8186-7904-2 | 2 |
PageRank | References | Authors |
0.42 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ted Zhihong Yu | 1 | 13 | 1.38 |
| Edwin H.-M. Sha | 2 | 1318 | 97.35 |
| Nelson Passos | 3 | 2 | 0.42 |
| Roy Dz-ching Ju | 4 | 326 | 21.37 |