1-1hit |
Katsumi HARASHIMA Miki YOSHIDA Hironori KOMI Kunio FUKUNAGA
We propose an optimal throughput problem using graph transformations to maximize throughput of a pipelined data path with some loops. The upper bound of the throughput, equals to the lower bound of the iteration interval between the start of two successive iterations, is limited by the length of a critical loop. Therefore we can maximize the throughput by minimizing the length of the critical loop. The proposed method first schedules an initial Data Flow Graph (DFG) under the initial iteration interval as few as it can use resources, then it transforms the DFG into the flow graph with the minimal length of the critical loop by rescheduling the given initial scheduling result. If there are any control steps which violate the resource constraints owing to the transformations, then these operations are adjusted so as to satisfy given resource consrtraints. Finally by rescheduling the transformed DFG, it gives a schedule with maximum throughput. Experiments show the efficiency of our proposed approach.