short-paper

Accelerating multi-party scheduling for transaction-level modeling

Authors:

Di Wang,

Wei Qin,

Jayanta BhadraAuthors Info & Claims

GLSVLSI '09: Proceedings of the 19th ACM Great Lakes symposium on VLSI

Pages 339 - 344

https://doi.org/10.1145/1531542.1531619

Published: 10 May 2009 Publication History

Get Access

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.

Google Scholar

[2]

ISO/IEC(8652:1995). Ada Reference Manual -- Language and Standard Libraries. 1995.

Google Scholar

[3]

Barrett, Geoff. occam3 reference manual. INMOS Ltd., 1992.

Google Scholar

[4]

Bolongnesi, Tommaso and Brinksma, Ed. Introduction to the ISO specification language LOTOS. Computer Networks and ISDN Systems, 14, 1 (January 1987), 25--59.

Digital Library

Google Scholar

[5]

Hoare, C.A.R. Communicating Sequential Processes. Prentice Hall, 1985.

Digital Library

Google Scholar

[6]

Milner, R. Communication and Concurrency. Prentice Hall, 1989.

Digital Library

Google Scholar

[7]

CELOXICA LTD. Handel-C Language Reference Manual. 2005.

Google Scholar

[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.

Digital Library

Google Scholar

[9]

Handshake Solutions, Haste Progamming Language Manual, 2008.

Google Scholar

[10]

Joung, Yuh-Jzer and Smolka, Scott A. A comprehensive study of the complexity of multiparty interaction. Journal of ACM, 43, 1 (January 1996), 75--115.

Digital Library

Google Scholar

[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.

Google Scholar

[12]

Barth, Peter. Logic-Based 0-1 Constraint Programming. Springer, 1995.

Digital Library

Google Scholar

[13]

Budruk, Ravi, Anderson, Don, and Shanley, Tom. PCI Express System Architecture. MindShare Inc, 2004.

Digital Library

Google Scholar

Cited By

View all

Venkataraman VWang DQin WBose MBhadra J(2009)Simulation of a Heterogeneous System at Multiple Levels of Abstraction Using Rendezvous Based ModelingProceedings of the 2009 10th International Workshop on Microprocessor Test and Verification10.1109/MTV.2009.20(3-8)Online publication date: 7-Dec-2009
https://dl.acm.org/doi/10.1109/MTV.2009.20
Venkataraman VWang DMahram AQin WBose MBhadra J(2009)Synthesis Oriented Scheduling of Multiparty Rendezvous in Transaction Level ModelsProceedings of the 2009 IEEE Computer Society Annual Symposium on VLSI10.1109/ISVLSI.2009.8(241-246)Online publication date: 13-May-2009
https://dl.acm.org/doi/10.1109/ISVLSI.2009.8

Index Terms

Accelerating multi-party scheduling for transaction-level modeling
1. Hardware
  1. Electronic design automation
    1. Hardware description languages and compilation
    2. High-level and register-transfer level synthesis

Recommendations

On rigorous Transaction Scheduling

The class of transaction scheduling mechanisms in which the transaction serialization order can be determined by controlling their commitment order, is defined. This class of transaction management mechanisms is important, because it simplifies ...
Scheduling of deteriorating jobs with release dates to minimize the maximum lateness

In this paper, we consider the problem of scheduling n deteriorating jobs with release dates on a single (batching) machine. Each job's processing time is a simple linear function of its starting time. The objective is to minimize the maximum lateness. ...
Scheduling rules for dynamic shops that manufacture multi-level jobs

The problem of scheduling in dynamic conventional jobshops has been extensively investigated over many years. However, the problem of scheduling in assembly jobshops (i.e. shops that manufacture multi-level jobs with components and subassemblies) has ...

Comments

Information & Contributors

Information

Published In

GLSVLSI '09: Proceedings of the 19th ACM Great Lakes symposium on VLSI

May 2009

558 pages

ISBN:9781605585222

DOI:10.1145/1531542

Co-chair:
Fabrizio Lombardi,
General Chairs:
Sanjukta Bhanja
University of South Florida, USA
,
Yehia Massoud
Rice University, USA
,
Program Chair:
R. Iris Bahar
Brown University, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

GLSVLSI '09

Sponsor:

GLSVLSI '09: Great Lakes Symposium on VLSI 2009

May 10 - 12, 2009

MA, Boston Area, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25

Sponsor:
sigda

Great Lakes Symposium on VLSI 2025

June 30 - July 2, 2025

New Orleans , LA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
100
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Venkataraman VWang DQin WBose MBhadra J(2009)Simulation of a Heterogeneous System at Multiple Levels of Abstraction Using Rendezvous Based ModelingProceedings of the 2009 10th International Workshop on Microprocessor Test and Verification10.1109/MTV.2009.20(3-8)Online publication date: 7-Dec-2009
https://dl.acm.org/doi/10.1109/MTV.2009.20
Venkataraman VWang DMahram AQin WBose MBhadra J(2009)Synthesis Oriented Scheduling of Multiparty Rendezvous in Transaction Level ModelsProceedings of the 2009 IEEE Computer Society Annual Symposium on VLSI10.1109/ISVLSI.2009.8(241-246)Online publication date: 13-May-2009
https://dl.acm.org/doi/10.1109/ISVLSI.2009.8

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

On rigorous Transaction Scheduling

Scheduling of deteriorating jobs with release dates to minimize the maximum lateness

Scheduling rules for dynamic shops that manufacture multi-level jobs

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations