Use this resource - and many more! - in your textbook!
AcademicPub holds over eight million pieces of educational content for you to mix-and-match your way.
A framework for algebraic transformations in iterative algorithms
By: Liang-Fang Chao; Jian-Feng Shi;
1996 / IEEE / 0-7803-3073-0
This item was taken from the IEEE Periodical ' A framework for algebraic transformations in iterative algorithms ' 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 paper, 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.
Cyclic Data-flow Graph
Lower Bound Reduction
Signal Processing Algorithms
Very Large Scale Integration