skip to main content
10.1145/1023833.1023858acmconferencesArticle/Chapter ViewAbstractPublication PagesesweekConference Proceedingsconference-collections
Article

Providing time- and space- efficient procedure calls for asynchronous software thread integration

Published: 22 September 2004 Publication History

Abstract

Asynchronous Software Thread Integration (ASTI) provides fine-grain concurrency in real-time threads by statically scheduling (integrating) code from primary threads into secondary threads, reducing the context switching needed and allowing recovery of fine-grain idle time. Unlike STI, ASTI allows asynchronous thread progress.Current ASTI techniques do not support procedure calls in the secondary thread because they lead to timing conflicts during static scheduling. ASTI requires knowing the secondary thread's instruction execution schedule to guide placement of real-time instructions from the primary thread. A secondary thread procedure called from multiple sites will have ambiguous timing at compile time.In this paper we remove this constraint using both procedure inlining and cloning. We present a formal approach to choosing a subset of calls to inline and to remove the timing conflicts in the remaining call sites in an efficient fashion. Excessive inlining and cloning both lead to code size explosion, while poor choices in timing conflict elimination slow program execution. The cloned threads show a significant speedup when compared to non-cloned versions yet have low code expansion. The techniques presented here have been implemented in our post-pass compiler Thrint and demonstrated on a benchmark suite of secondary threads representative of low-end embedded systems.

References

[1]
"CAN specification version 2.0," Robert Bosch GmbH, 1991. {Online}. Available: http://www.mot-sps.com/csic/techdata/refman/can2spec.pdf]]
[2]
AVR304 Half Duplex Interrupt Driven Software UART, Atmel Corporation, Aug 1997.]]
[3]
"Application note: Software lin slave," Atmel Corporation, Feb. 2000.]]
[4]
AVR320 Software SPI Master, Atmel Corporation, May 2002.]]
[5]
AVR410 RC5 IR Remote Control Receiver, Atmel Corporation, May 2002.]]
[6]
A. G. Dean and R. R. Grzybowski, "A high-temperature embedded network interface using software thread integration," in Second Workshop on Compiler and Architectural Support for Embedded Systems, Washington, DC, October 1999.]]
[7]
A. G. Dean, "Software thread integration for hardware to software migration," Ph.D. dissertation, Carnegie Mellon University, February 2000.]]
[8]
N. J. Kumar, S. Shivshankar, and A. G. Dean, "Asynchronous software thread integration for efficient software implementations of embedded communication protocol controllers," in Proceedings of the 2004 ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems. 1em plus 0.5em minus 0.4em ACM Press, June 2004. {Online}. Available: http://www.cesr.ncsu.edu/agdean/TechReports/p55-kumar.pdf]]
[9]
M. E. Conway, "Design of a separable transition-diagram compiler," Communications of the ACM, vol. 6, no. 7, pp. 396--408, 1963.]]
[10]
M. Arnold, S. J. Fink, V. Sarkar, and P. F. Sweeney, "A comparative study of static and profile-based heuristics for inlining," in ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization (DYNAMO'00). 1em plus 0.5em minus 0.4em ACM, Jan. 2000, pp. 52--64.]]
[11]
R. Leupers and P. Marwedel, "Function inlining under code size constraints for embedded processors," in ICCAD, 1999, pp. 253--256. {Online}. Available: citeseer.ist.psu.edu/leupers99function.html]]
[12]
V. Asokan, "Relaxing control flow constraints in asti," Master's thesis, North Carolina State University, Jul 2003.]]
[13]
B. Welch, S. Kanaujia, A. Seetharam, D. Thirumalai, and A. G. Dean, "Extending sti for demanding hard-real-time systems," in Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems. 1em plus 0.5em minus 0.4em ACM Press, November 2003, pp. 41--50.]]
[14]
P. Ganesan and A. G. Dean, "Enhancing the avrx kernel with efficient secure communication using software thread integration," in Proceedings of the 10th IEEE Real-Time and Embedded Technology Applications Symposium. 1em plus 0.5em minus 0.4em IEEE Press, May 2004.]]
[15]
A. G. Dean, "Compiling for concurrency: Planning and performing software thread integration," in Proceedings of the 23rd IEEE Real-Time Systems Symposium, Austin, TX, Dec 2002.]]
[16]
Atmega 128: 8-Bit AVR Microcontroller with 128K Bytes In-System Programmable Flash, Atmel Corporation. {Online}. Available: http://www.atmel.com/dyn/resources/prod documents/doc2467.pdf]]
[17]
SAE J1850 Class B data communication network interface, Society of Automotive Engineers, 1992.]]
[18]
avr-gcc 3.2. {Online}. Available: http://www.avrfreaks.net/AVRGCC/index.php]]
[19]
P82C150 CAN Serial Linked I/O Device (SLIO) with Digital and Analog Port Functions Data Sheet, Philips Semiconductors, Jun 1996.]]
[20]
MCP2502X/5X CAN I/O Expander Family Data Sheet, Microchip Technology, Inc., Aug 2000.]]
[21]
MIC74 2-Wire Serial I/O Expander and Fan Controller, Micrel, Inc., Aug 2000.]]
[22]
PCF8574 Remote 8-bit I/O Expander for I2C-bus, Philips Semiconductors, Nov 2002.]]
[23]
R. Gupta and M. Spezialetti, "Busy-idle profiles and compact task graphs compile-time support for interleaved and overlapped scheduling of real-time tasks," in 15th IEEE Real Time Systems Symposium, 1994.]]
[24]
C. J. Beckmann, "Hardware and Software for Functional and Fine Grain Parallelism," Ph.D. dissertation, North Carolina State University, April 1993. {Online}. Available: citeseer.nj.nec.com/beckmann93hardware.html]]
[25]
P. Chou and G. Borriello, "Interval scheduling: Fine grained code scheduling for embedded systems," in Proceedings of the Design Automation Conference, June 1995, pp. 462--467.]]
[26]
R. K. Gupta and G. De Micheli, "A co-synthesis approach to embedded system design automation," Design Automation for Embedded Systems, vol. 1, no. 1-2, pp. 69--120, 1996.]]
[27]
S. A. Edwards, "Compiling esterel into sequential code," in Design Automation Conference, 2000, pp. 322--327. {Online}. Available: citeseer.nj.nec.com/edwards00compiling.html]]
[28]
R. S. French, M. S. Lam, J. R. Levitt, and K. Olukotun, "A general method for compiling event-driven simulations," in Design Automation Conference, 1995, pp. 151--156. {Online}. Available: citeseer.nj.nec.com/french95general.html]]
[29]
E. A. Lee, "Recurrences, iteration, and conditionals in statically scheduled block diagram languages," in VLSI Signal Processing III, R. W. Brodersen and H. S. Moscovitz, Eds. 1em plus 0.5em minus 0.4em IEEE Press, 1988, pp. 330--340.]]
[30]
C.Loeffler, A.Lightenberg, H.Bheda, and G. Moschytz, "Hierarchical scheduling systems for parallel architectures," in Proceedings of Euco, September 1988.]]
[31]
S. Ha and E. Lee, "Compile-time scheduling of dynamic constructs in dataflow program graphs," 1997. {Online}. Available: citeseer.ist.psu.edu/ha97compiletime.html]]
[32]
M. Sgroi, L. Lavagno, Y. Watanabe, and A. L. Sangiovanni-Vincentelli, "Quasi-static scheduling of embedded software using equal conflict nets," in ICATPN, 1999, pp. 208--227. {Online}. Available: citeseer.nj.nec.com/sgroi95quasistatic.html]]
[33]
B. Lin, "Efficient compilation of process-based concurrent programs without run-time scheduling," in Proceedings of the conference on Design, automation and test in Europe. 1em plus 0.5em minus 0.4em IEEE Computer Society, 1998, pp. 211--217.]]
[34]
E. A. Lee and D. G. Messerschmitt, "Static scheduling of synchronous data flow graphs for digital signal processing," IEEE Transactions on Computers, January 1987.]]
[35]
J. Cortadella, A. Kondratyev, L. Lavagno, C. Passerone, and Y. Watanabe, "Quasi-static scheduling of independent tasks for reactive systems," Design Automation Conference, June 2000. {Online}. Available: citeseer.nj.nec.com/541753.html]]
[36]
F. Allen and J. Cocke, A Catalogue of Optimizing Transformations, P. Hall, Ed. 1em plus 0.5em minus 0.4em Prentice Hall, 1972.]]
[37]
S. Richardson and M. Ganapathi, "Code optimization across procedures," Computer, vol. 22, no. 2, pp. 42--50, 1989.]]
[38]
P. P. Chang, S. A. Mahlke, W. Y. Chen, and W. mei W. Hwu, "Profile-guided automatic inline expansion for c programs," Software - Practice and Experience, vol. 22, no. 5, pp. 349--369, 1992. {Online}. Available: citeseer.ist.psu.edu/chang92profileguided.html]]
[39]
K. D. Cooper, M. W. Hall, and K. Kennedy, "A methodology for procedure cloning," Computer Languages, vol. 19, no. 2, pp. 105--117, 1993. {Online}. Available: citeseer.ist.psu.edu/cooper93methodology.html]]
[40]
J. Dean, C. Chambers, and D. Grove, "Selective specialization for object-oriented languages," in SIGPLAN Conference on Programming Language Design and Implementation, 1995, pp. 93--102. {Online}. Available: citeseer.ist.psu.edu/dean95selective.html]]
[41]
W. So and A. G. Dean, "Procedure cloning and integration for converting parallelism from coarse to fine grain," in Proceedings of the Seventh Workshop on Interaction between Compilers and Computer Architectures, Feb 2003.]]

Cited By

View all
  • (2005)Balancing register pressure and context-switching delays in ASTI systemsProceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems10.1145/1086297.1086335(286-294)Online publication date: 24-Sep-2005

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CASES '04: Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems
September 2004
324 pages
ISBN:1581138903
DOI:10.1145/1023833
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 September 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. asynchronous software thread integration
  2. fine-grain concurrency
  3. hardware to software migration
  4. software-implemented communication protocol controllers

Qualifiers

  • Article

Conference

CASES04

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2005)Balancing register pressure and context-switching delays in ASTI systemsProceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems10.1145/1086297.1086335(286-294)Online publication date: 24-Sep-2005

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media