Performance analysis and optimization of latency insensitive systems

ABSTRACT

Latency insensitive design has been recently proposed in literature as a way to design complex digital systems, whose functional behavior is robust with respect to arbitrary variations in interconnect latency. However, this approach does not guarantee the same robustness for the performance of the design, which indeed can experience big losses. This paper presents a simple, yet rigorous, method to (1) model the key properties of a latency insensitive system, (2) analyze the impact of interconnect latency on the overall throughput, and (3) optimize the performance of the final implementation.

REFERENCES

• 1: A. Agarwal. Raw Computation. Scientific American, 281(2):60-63, August 1999.
• 2: F. Bacelli, G. Cohen, G.J. Olsder, and J.P. Quadrat. Synchronization and Linearity. Wiley, New York, 1992.
• 3: Vasudev Bhaskaran , Konstantinos Konstantinides, Image and Video Compression Standards: Algorithms and Architectures, Kluwer Academic Publishers, Norwell, MA, 1997
• 4: Steven Morgan Burns, Performance analysis and optimization of asynchronous circuits, California Institute of Technology, Pasadena, CA, 1992
• 5: 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
• 6: Luca P. Carloni , Kenneth L. McMillan , Alberto L. Sangiovanni-Vincentelli, Latency Insensitive Protocols, Proceedings of the 11th International Conference on Computer Aided Verification, p.123-133, July 06-10, 1999
• 7: L. P. Carloni and Alberto L. Sangiovanni-Vincentelli. Recycle, Reuse, Reduce. Technical Report UCB/ERL M99/53, Electronics Research Lab, University of California, Berkeley, CA 94720, October 1999.
• 8: J. Cong. Challenges and Opportunities for Design Innovations in Nanometer Technologies. In SRC Design Sciences Concept Paper, December 1997.
• 9: Jason Cong , Zhigang Pan , Lei He , Cheng-Kok Koh , Kei-Yong Khoo, Interconnect design for deep submicron ICs, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.478-485, November 09-13, 1997, San Jose, California, United States
• 10: Doug Matzke, Will Physical Scalability Sabotage Performance Gains?, Computer, v.30 n.9, p.37-39, September 1997 [doi>10.1109/2.612245]
• 11: A. Dasdan and Rajesh K. Gupta. Faster Maximum and Minimum Mean Cycle Algorithms for System-Perofrmance Analysis. IEEE Transactions on Computer-Aided Design, 17(10):889-899, October 1998.
• 12: Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997 [doi>10.1109/2.612254]
• 13: Mitsuo Ikeda , Tsuneo Okubo , Tetsuya Abe , Yoshinori Ito , Yutaka Tashiro , Ryota Kasai, A Hardware/Software Concurrent Design for a Real-Time SP@ML MPEG2 Video-Encoder Chip Set, Proceedings of the 1996 European conference on Design and Test, p.320, March 11-14, 1996
• 14: Mitsuo Ikeda , Toshio Kondo , Koyo Nitta , Kazuhito Suguri , Takeshi Yoshitome , Toshihiro Minami , Hiroe Iwasaki , Katsuyuki Ochiai , Jiro Naganuma , Makoto Endo , Yutaka Tashiro , Hiroshi Watanabe , Naoki Kobayashi , Tsuneo Okubo , Takeshi Ogura , Ryota Kasai, SuperENC: MPEG-2 Video Encoder Chip, IEEE Micro, v.19 n.4, p.56-65, July 1999 [doi>10.1109/40.782568]
• 15: Richard J. Higgins, Digital signal processing in VLSI, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 16: R. M. Karp. A Characterization of the Minimum Cycle Mean in a Digraph. Discrete Math., 23:309-311, 1978.
• 17: M. Horowitz and R. Ho and K. Mai. The Future of Wires. In Invited Workshop Paper for SRC Conference. Available at "http://velox.stanford.edu/", May 1999.
• 18: M. T. Bohr. Interconnect Scaling - The Real Limiter to High Performance ULSI. IEEE International Electron Devices Meeting, pages 241-244, December 1995.
• 19: Mark Bohr, Silicon trends and limits for advanced microprocessors, Communications of the ACM, v.41 n.3, p.80-87, March 1998 [doi>10.1145/272287.272327]
• 20: Michael J. Flynn , Patrick Hung , Kevin W. Rudd, Deep-Submicron Microprocessor Design Issues, IEEE Micro, v.19 n.4, p.11-22, July 1999 [doi>10.1109/40.782563]
• 21: Francois Pogodalla , Richard Hersemeule , Pierre Coulomb, Fast prototyping: a system design flow for fast design, prototyping and efficient IP reuse, Proceedings of the seventh international workshop on Hardware/software codesign, p.69-73, March 1999, Rome, Italy [doi>10.1145/301177.301215]
• 22: Ron Ho , Ken Mai , Hema Kapadia , Mark Horowitz, Interconnect scaling implications for CAD, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.425-429, November 07-11, 1999, San Jose, California, United States
• 23: C. V. Ramamoorthy and G. S. Ho. Performance Evaluation of Asynchronous Concurrent Systems Using Petri Nets. IEEE Transactions on Software Engineering, 6(5):440-449, September 1980.
• 24: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 25: T. McHale. Electronic Design Automation: Time to Grow Up. Electronic Business, June 1999.
• 26: R. E. Tarjan. Depth-First Search and Linear Graph Algorithms. In SIAM J. Comput., volume 1, pages 146-160. Society for Industrial and Applied Mathematics, 1972.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Performance, Theory