Performance analysis of concurrent systems with early evaluation

ABSTRACT

Early evaluation allows to execute operations when enough information at the inputs has been received to determine the value at the outputs. Systems that can tolerate variable-latency units, such as latency-insensitive or asynchronous systems, can enhance their performance by using early evaluation. The most relevant example of a unit with early evaluation is the multiplexor: the output can be determined as soon as the information of the selected channel arrives, without waiting for the other channels.

This paper analyzes the potential impact of early evaluation in concurrent systems. An analytical model, based on a Petri net extension with early firing is proposed to estimate the performance. The reduction of the analytical model to a linear programming formulation for an efficient estimation of the upper bound for the system throughput is proposed. The results show the accuracy of the model and the benefits of early evaluation.

REFERENCES

• 1: M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis. Modelling with Generalized Stochastic Petri Nets. Wiley, 1995.
• 2: C. Brej and J. Garside. Early output logic using anti-tokens. In Int. Workshop on Logic Synthesis, pages 302--309, May 2003.
• 3: 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]
• 4: L. Carloni, K. McMillan, and A. Sangiovanni-Vincentelli. Theory of latency-insensitive design. IEEE Transactions on Computer-Aided Design, 20(9):1059--1076, Sept. 2001.
• 5: F. Commoner, A. W. Holt, S. Even, and A. Pnueli. Marked directed graphs. Journal of Computer and System Sciences, 5:511--523, 1971.
• 6: A. Dasdan and R. K. Gupta. Faster maximum and minimum mean cycle algorithms for system performance analysis. IEEE Transactions on Computer-Aided Design, 17(10):889--899, 1998.
• 7: R. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23:309--311, 1978.
• 8: M. K. Molloy. Performance Analysis Using Stochastic Petri Nets. IEEE Trans. on Computers, 31(9):913--917, 1982.
• 9: T. Murata. Petri Nets: Properties, analysis and applications. Proceedings of the IEEE, pages 541--580, Apr. 1989.
• 10: R. Reese, M. Thornton, C. Traver, and D. Hemmendinger. Early evaluation for performance enhancement in phased logic. IEEE Transactions on Computer-Aided Design, 24(4):532--550, Apr. 2005.
• 11: J. Sparsø and S. Furber, editors. Principles of Asynchronous Circuit Design: A Systems Perspective. Kluwer Academic Publishers, 2001.
• 12: Alexandre Yakovlev , Michael Kishinevsky , Alex Kondratyev , Luciano Lavagno , Marta Pietkiewicz-Koutny, On the models for asynchronous circuit behaviour with OR causality, Formal Methods in System Design, v.9 n.3, p.189-233, Nov. 1996 [doi>10.1007/BF00122082]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Styles (e.g., parallel, pipeline, special-purpose)

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Design, Performance