Accelerating multi-party scheduling for transaction-level modeling

ABSTRACT

Transaction-level modeling is an essential component of system-level design. This paper advocates using rendezvous, a construct common to concurrent programming languages, as a theoretical foundation for transactions. Compared to regular function calls, rendezvous are atomic and support multipartiness and parallel composition. However, scheduling multiparty rendezvous is a challenging task due to its NP-hard complexity. This paper describes a heuristic algorithm that significantly reduces the scheduling complexity in practice. It first constructs a relationship graph among rendezvous. It then simplifies the graph and translates it into a decision tree, which assists the scheduler in partitioning and pruning the search space. Our experimental results show that the algorithm is able to improve the efficiency of the scheduler significantly.

REFERENCES

• 1: IEEE INC. IEEE Standard SystemC Language Reference Manual (1666--2005). New York, NY 10016--5997, USA, 2005.
• 2: ISO/IEC(8652:1995). Ada Reference Manual -- Language and Standard Libraries. 1995.
• 3: Barrett, Geoff. occam3 reference manual. INMOS Ltd., 1992.
• 4: Tommaso Bolognesi , Ed Brinksma, Introduction to the ISO specification language LOTOS, Computer Networks and ISDN Systems, v.14 n.1, p.25-59, March, 1987 [doi>10.1016/0169-7552(87)90085-7]
• 5: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 6: R. Milner, Communication and Concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 7: CELOXICA LTD. Handel-C Language Reference Manual. 2005.
• 8: Edwards, Stephen A and Tardieu, Olivier. SHIM: A Deterministic Model for Heterogeneous Embedded Systems. IEEE Transactions on Very Large Scale Integration Systems, 14, 8 (August 2006), 854--867.
• 9: Handshake Solutions, Haste Progamming Language Manual, 2008.
• 10: Yuh-Jzer Joung , Scott A. Smolka, A comprehensive study of the complexity of multiparty interaction, Journal of the ACM (JACM), v.43 n.1, p.75-115, Jan. 1996 [doi>10.1145/227595.227601]
• 11: Nikhil, Rishiyur. Bluespec: A General-Purpose Approach to High-Level Synthesis Based on Parallel Atomic Transactions. In Philippe Coussy, Adam Morawiec, ed., High-Level Synthesis -- From Algorithm to Digital Circuit. Springer, 2008.
• 12: Peter Barth, Logic-based 0-1 constraint programming, Kluwer Academic Publishers, Norwell, MA, 1995
• 13: Ravi Budruk , Don Anderson , Ed Solari, PCI Express System Architecture, Pearson Education, 2003

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Hardware description languages

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

General Terms:
Algorithms, Design, Languages, Verification

Keywords:
concurrent programming., multiparty rendezvous, scheduling, transaction level modeling