Your Search Results

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.

Experience the freedom of customizing your course pack with AcademicPub!
Not an educator but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

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.