A high level transformation framework for iterative algorithms
Date
1996
Authors
Shi, Jian-Feng
Major Professor
Advisor
Chao, Liang-Fang
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
An iterative algorithm can be modeled by a cyclic data-flow graph. The bottleneck for scheduling cyclic data-flow graphs lies on dependencies that form cycles. The maximum computation-time-to-delay ratio among all the cycles in the graph, gives a lower bound on pipeline schedule length. In this thesis, a framework for algebraic transformations is proposed to reduce the lower bound. A novel algorithm is proposed to apply transformations within iterations or over iteration boundaries. A set of beneficial transformations are chosen, and applied simultaneously in each pass of the algorithm. A measure of criticalness on loops is used to identify transformations leading to potential lower bound reduction. Experimental results show that substantial reductions on the lower bound are achieved, and shorter pipelined schedules are generated.
However, resource constrained algebraic transformations for loop pipelining remains a hard problem because of the inherent nature of loop pipelining. In second part of the thesis, a new method based on distribution graphs to solve this problem is proposed. A novel algorithm for algebraic transformation with resource constraints is provided, which works for non-pipelined schedules as well. Experimental results show that our algorithm is promising.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
thesis