Accelerating multi-party scheduling for transaction-level modeling
Di Wang, Vyas Venkataraman, Zhen Wang, Wei Qin, Hangsheng Wang, Mrinal Bose, Jayanta Bhadra · 2009
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.