Performance-constrained pipelining of software loops onto reconfigurable hardware

ABSTRACT

Retiming and slowdown are algorithms that can be used to pipeline synchronous circuits. Iterative modulo scheduling is an algorithm for software pipelining in the presence of resource constraints. Integrating the best features of both yields a pipelining algorithm, retimed modulo scheduling, that can more effectively exploit the idiosyncrasies of reconfigurable hardware. It also fits naturally into a design space exploration process to trade-off speed for power, energy or area.

REFERENCES

• 1: C. Leiserson, J. Saxe, "Retiming Synchronous Systems," Algorithmica, 6(1), 1991.
• 2: H. Touati, R. Brayton, "Computing the Initial States of Retimed Circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 1, January 1993.
• 3: Klaus Eckl , Jean Christophe Madre , Peter Zepter , Christian Legl, A practical approach to multiple-class retiming, Proceedings of the 36th ACM/IEEE conference on Design automation, p.237-242, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309920]
• 4: Vigyan Singhal , Sharad Malik , Robert K. Brayton, The case for retiming with explicit reset circuitry, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.618-625, November 10-14, 1996, San Jose, California, United States
• 5: B. Rau, "Iterative Modulo Scheduling," HP Labs Technical Report HPL-94-115.
• 6: Marios C. Papaefthymiou, Understanding retiming through maximum average-weight cycles, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.338-348, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113410]
• 7: Sandip Kundu , Leendert M. Huisman , Indira Nair , Vijay S. Iyengar , Lakshmi N. Reddy, A Small Test Generator for Large Designs, Proceedings of the IEEE International Test Conference on Discover the New World of Test and Design, p.30-40, September 20-24, 1992
• 8: C. Leiserson, J. Saxe, "Optimizing Synchronous Systems," Journal of VLSI and Computer Systems,vol.1,no1,1983.
• 9: C. Leiserson, "Systolic and Semisystolic Design," IEEE International Conference on Computer Design / VLSI in Computers, 1983.
• 10: Narendra Shenoy , Richard Rudell, Efficient implementation of retiming, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.226-233, November 06-10, 1994, San Jose, California, United States
• 11: Peichen Pan , Guohua Chen, Optimal Retiming for Initial State Computation, Proceedings of the 12th International Conference on VLSI Design - 'VLSI for the Information Appliance', p.366, January 10-13, 1999
• 12: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
• 13: M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]
• 14: Soha Hassoun , Carl Ebeling, Architectural retiming: pipelining latency-constrained circuits, Proceedings of the 33rd annual conference on Design automation, p.708-713, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240652]
• 15: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.1-14, June 24-28, 1991, Toronto, Ontario, Canada
• 16: Scott Alan Mahlke, Exploiting instruction level parallelism in the presence of conditional branches, University of Illinois at Urbana-Champaign, Champaign, IL, 1997
• 17: James C. Tiernan, An efficient search algorithm to find the elementary circuits of a graph, Communications of the ACM, v.13 n.12, p.722-726, Dec. 1970 [doi>10.1145/362814.362819]
• 18: Timothy J. Callahan , John Wawrzynek, Adapting software pipelining for reconfigurable computing, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.57-64, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354889]
• 19: Maya B. Gokhale , Janice M. Stone , Edson Gomersall, Co-Synthesis to a Hybrid RISC/FPGA Architecture, Journal of VLSI Signal Processing Systems, v.24 n.2-3, p.165-180, Mar. 2000 [doi>10.1023/A:1008141305507]
• 20: R.Schreiber,S.Aditya,B.Rau,V.Kathail,S.Mahlke,S. Abraham, G. Snider, "High-Level Synthesis of Nonprogrammable ardware Accelerators," HP Labs Technical Report HPL-2000-31.
• 21: Vinoo Srinivasan , Ranga Vemuri, A Retiming Based Relaxation Heuristic for Resource-Constrained Loop Pipelining", Proceedings of the Eleventh International Conference on VLSI Design: VLSI for Signal Processing, p.435, January 04-07, 1998
• 22: Pierre-Yves Calland , Alain Darte , Yves Robert, Circuit Retiming Applied to Decomposed Software Pipelining, IEEE Transactions on Parallel and Distributed Systems, v.9 n.1, p.24-35, January 1998 [doi>10.1109/71.655240]
• 23: M. Weinhardt, W. Luk, "Pipeline Vectorization," IEEE Transactions on Computer-Aided Designs of Integrated Circuits and Systems, vol. 20, no.2, February 2001.
• 24: T. O'Neil, S. Tongsima, E. Sha, "Optimal Scheduling of Data- Flow Graphs Using Extended Retiming," Proceedings of the ISCA 12th International Conference on Parallel and Distributed Computing Systems, 1999.
• 25: José Monteiro , Srinivas Devadas , Pranav Ashar , Ashutosh Mauskar, Scheduling techniques to enable power management, Proceedings of the 33rd annual conference on Design automation, p.349-352, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240584]
• 26: Han-Saem Yun , Jihong Kim, Power-aware modulo scheduling for high-performance VLIW processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.40-45, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383091]
• 27: E. Musoll , J. Cortadella, Scheduling and resource binding for low power, Proceedings of the 8th international symposium on System synthesis, p.104-109, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224523]