A general model for performance optimization of sequential systems

ABSTRACT

Retiming, c-slow retiming and recycling are different transformations for the performance optimization of sequential circuits. For retiming and c-slow retiming, different models that provide exact solutions have already been proposed. An exact model for recycling was yet unknown. This paper presents a general formulation that covers the combination of the three schemes for performance optimization. It provides an exact model based on integer linear programming that resorts to the structural theory of marked graphs. A set of experiments has been designed to show the benefits in performance obtained by combining retiming and recycling. The results also show the applicability of the method in large circuits.

REFERENCES

• 1: C. E. Leiserson and J. B. Saxe, "Retiming synchronous circuitry." Algorithmica, vol. 6, no. 1, pp. 5--35, 1991.
• 2: Narendra Shenoy, Retiming: theory and practice, Integration, the VLSI Journal, v.22 n.1-2, p.1-21, Aug. 1997 [doi>10.1016/S0167-9260(97)00002-3]
• 3: S. S. Sapatnekar and R. B. Deokar, "Utilizing the timing shew equivalence in a practical algorithm for retiming large circuits," IEEE Transactions on Computer-Aided Design, vol. 15, no. 10, pp. 1237--1248, Oct. 1996.
• 4: Chuan Lin , Hai Zhou, Retiming for Wire Pipelining in System-On-Chip, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.215, November 09-13, 2003 [doi>10.1109/ICCAD.2003.117]
• 5: Vidyasagar Nookala , Sachin S. Sapatnekar, A method for correcting the functionality of a wire-pipelined circuit, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996724]
• 6: Luca P. Carloni , Kenneth L. McMillan , Alexander Saldanha , Alberto L. Sangiovanni-Vincentelli, A methodology for correct-by-construction latency insensitive design, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.309-315, November 07-11, 1999, San Jose, California, United States
• 7: Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Performance analysis and optimization of latency insensitive systems, Proceedings of the 37th conference on Design automation, p.361-367, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337441]
• 8: Ted E. Williams, Performance of iterative computation in self-timed rings, Journal of VLSI Signal Processing Systems, v.7 n.1-2, p.17-31, Feb. 1994 [doi>10.1007/BF02108187]
• 9: Rajit Manohar , Alain J. Martin, Slack Elasticity in Concurrent Computing, Proceedings of the Mathematics of Program Construction, p.272-285, June 15-17, 1998
• 10: Peter A. Beerel , Nam-Hoon Kim , Andrew Lines , Mike Davies, Slack Matching Asynchronous Designs, Proceedings of the 12th IEEE International Symposium on Asynchronous Circuits and Systems, p.184, March 13-15, 2006 [doi>10.1109/ASYNC.2006.26]
• 11: Piyush Prakash , Alain J. Martin, Slack Matching Quasi Delay-Insensitive Circuits, Proceedings of the 12th IEEE International Symposium on Asynchronous Circuits and Systems, p.195, March 13-15, 2006 [doi>10.1109/ASYNC.2006.27]
• 12: Mario R. Casu , Luca Macchiarulo, A new approach to latency insensitive design, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996725]
• 13: Jordi Cortadella , Mike Kishinevsky , Bill Grundmann, Synthesis of synchronous elastic architectures, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147077]
• 14: Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Combining Retiming and Recycling to Optimize the Performance of Synchronous Circuits, Proceedings of the 16th symposium on Integrated circuits and systems design, p.47, September 08-11, 2003
• 15: H. J. Touati and R. K. Brayton, "Computing the initial states of retimed circuits," IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 12, no. 1, pp. 157--162, 1993.
• 16: R. Lu and C.-K. Koh, "Performance analysis of latency-insensitive systems," IEEE Transactions on Computer-Aided Design, vol. 25, no. 3, pp. 469--483, 2006.
• 17: T. Murata, "Petri Nets: Properties, analysis and applications," Proceedings of the IEEE, pp. 541--580, Apr. 1989.
• 18: F. Commoner, A. W. Holt, S. Even, and A. Pnueli, "Marked directed graphs," Journal of Computer and System Sciences, vol. 5, pp. 511--523, 1971.
• 19: T. Murata, "Circuit theoretic analysis and synthesis of marked graphs," IEEE Trans. Circuits and Systems, vol. CAS-24, no. 7, pp. 400--405, July 1977.
• 20: C. Ramchandani, ANALYSIS OF ASYNCHRONOUS CONCURRENT SYSTEMS BY TIMED PETRI NETS, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 21: Marios C. Papaefthymiou, Understanding retiming through maximum average-delay cycles, Mathematical Systems Theory, v.27 n.1, p.65-84, Jan./Feb. 1994
• 22: Javier Campos , Giovanni Chiola , Manuel Silva, Ergodicity and Throughput Bounds of Petri Nets with Unique Consistent Firing Count Vector, IEEE Transactions on Software Engineering, v.17 n.2, p.117-125, February 1991 [doi>10.1109/32.67593]
• 23: C. Papadimitriou, Computational Complexity. Addison-Wesley, 1995.
• 24: "CPLEX," http://www.ilog.com/products/cplex.