Performance optimization of elastic systems using buffer resizing and buffer insertion

ABSTRACT

Buffer resizing and buffer insertion are two transformation techniques for the performance optimization of elastic systems. Different approaches for each technique have already been proposed in the literature. Both techniques increase the storage capacity and can potentially contribute to improve the throughput of the system. Each technique offers a different trade-off between area cost and latency. This paper presents a method that combines both techniques to achieve the maximum possible throughput while minimizing the cost of the implementation. The provided method is based on mixed integer linear programming. A set of experiments is designed to show the feasibility of the approach.

REFERENCES

• 1: J. Cong, "Challenges and opportunities for design innovations in nanometer technologies. in SRC working paper, Dec." 1997.
• 2: 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
• 3: Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Coping with Latency in SOC Design, IEEE Micro, v.22 n.5, p.24-35, September 2002 [doi>10.1109/MM.2002.1044297]
• 4: Ruibing Lu , Cheng-Kok Koh, Performance Optimization of Latency Insensitive Systems Through Buffer Queue Sizing of Communication Channels, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.227, November 09-13, 2003 [doi>10.1109/ICCAD.2003.113]
• 5: J. Sparsø and S. Furber, Eds., Principles of Asynchronous Circuit Design: A Systems Perspective. Kluwer Academic Publishers, 2001.
• 6: 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]
• 7: 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]
• 8: 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]
• 9: 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.
• 10: T. Murata, "Petri Nets: Properties, analysis and applications," Proceedings of the IEEE, pp. 541--580, Apr. 1989.
• 11: R. Lu and C.-K. Koh, "Performance analysis of latency-insensitive systems." IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 25, no. 3, 2006.
• 12: R. Karp, "A characterization of the minimum cycle mean in a digraph," Discrete Mathematics, vol. 23, pp. 309--311, 1978.
• 13: Ali Dasdan , Sandy S. Irani , Rajesh K. Gupta, Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.37-42, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309862]
• 14: C. Ramchandani, ANALYSIS OF ASYNCHRONOUS CONCURRENT SYSTEMS BY TIMED PETRI NETS, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 15: Steven M. Burns , Alain J. Martin, Performance analysis and optimization of asynchronous circuits, Proceedings of the 1991 University of California/Santa Cruz conference on Advanced research in VLSI, p.71-86, April 1991
• 16: 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]
• 17: C. V. Ramamoorthy , G. S. Ho, Performance Evaluation of Asynchronous Concurrent Systems Using Petri Nets, IEEE Transactions on Software Engineering, v.6 n.5, p.440-449, September 1980 [doi>10.1109/TSE.1980.230492]
• 18: Kenneth Fazel , Lun Li , Mitch Thornton , Robert B. Reese , Cherrice Traver, Performance enhancement in phased logic circuits using automatic slack-matching buffer insertion, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA [doi>10.1145/988952.989051]
• 19: Rebecca L. Collins , Luca P. Carloni, Topology-based optimization of maximal sustainable throughput in a latency-insensitive system, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278586]
• 20: Steven Morgan Burns, Performance analysis and optimization of asynchronous circuits, California Institute of Technology, Pasadena, CA, 1992
• 21: J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. M. Gettrick, and J.-P. Quadrat, "Numerical computation of spectral elements in max-plus algebra," Proc. of the IFAC Conference on System Structure and Control, july 1998.
• 22: "CPLEX," Available from http://www.ilog.com.