research-article

Supporting islands of coherency for highly-parallel embedded architectures using compile-time virtualisation

Authors:

Neil C. AudsleyAuthors Info & Claims

SCOPES '10: Proceedings of the 13th International Workshop on Software & Compilers for Embedded Systems

Article No.: 8, Pages 1 - 10

https://doi.org/10.1145/1811212.1811223

Published: 28 June 2010 Publication History

Abstract

As their complexity grows, the architectures of embedded systems are becoming increasingly parallel. However, the frameworks used to assist development on highly-parallel general-purpose systems (such as CORBA or MPI) are too heavyweight for use on the non-standard architectures of embedded systems. They introduce significant overheads due to the lack of architectural and structural information contained within most programming languages. Specifically, thread migration across irregular architectures can lead to very poor memory access times, and unconstrained cache coherency cannot scale to cope with large systems.

This paper introduces an approach to solving these problems in a scalable way with minimal run-time overhead by using the concept of 'Islands of Coherency'. Cooperating threads are grouped into clusters along with the data that they use. These clusters can then be efficiently mapped to the target architecture, utilising migration only in the areas where the programmer explicitly declares it.

This is supported through the use of an existing technique called Compile-Time Virtualisation (CTV). CTV does not support run-time dynamism, so it is extended to allow the implementation of Islands of Coherency. The presented system is evaluated experimentally through implementation on an FPGA platform. Simulation-based results are also presented that show the potential that this approach has for increasing the performance of future embedded systems.

References

[1]

R. Banakar, S. Steinke, B.-S. Lee, M. Balakrishnan, and P. Marwedel. Scratchpad memory: design alternative for cache on-chip memory in embedded systems. In CODES '02, pages 73--78, 2002.

Digital Library

[2]

A. Baumann, P. Barham, P.-E. Dagand, T. Harris, R. Isaacs, S. Peter, T. Roscoe, A. Schüpbach, and A. Singhania. The multikernel: a new os architecture for scalable multicore systems. In SOSP '09: Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles, pages 29--44, New York, NY, USA, 2009. ACM.

Digital Library

[3]

R. Brukardt. The ada95 language reference manual - appendix e, distributed systems (international standard iso/iec 8652:1995). http://www.adaic.org/standards/95lrm/html/RM-E.html.

[4]

A. Burns, B. Dobbing, and G. Romanski. The Ravenscar tasking profile for high integrity real-time programs. In Ada-Europe '98, pages 263--275. Springer-Verlag, 1998.

Digital Library

[5]

W. W. Carlson, D. E. Culler, and E. Brooks. Introduction to upc and language specification. CCS-TR-99-157, 1999.

[6]

W. Cesario et al. Component-based design approach for multicore SoCs. DAC, 00:789, 2002.

Digital Library

[7]

B. Chamberlain, D. Callahan, and H. Zima. Parallel programmability and the Chapel language. Int. J. High Perform. Comput. Appl., 21(3):291--312, 2007.

Digital Library

[8]

W. J. Dally and B. Towles. Route packets, not wires: On-chip interconnection networks. DAC, 2001.

Digital Library

[9]

P. Dibble and A. Wellings. Jsr-282 status report. In Proceedings of the 7th International Workshop on Java Technologies for Real-Time and Embedded Systems, ACM International Conference Proceeding Series, pages 179--182, New York, NY, USA, 2009. ACM.

Digital Library

[10]

N. D. Enright Jerger, L.-S. Peh, and M. H. Lipasti. Virtual tree coherence: Leveraging regions and in-network multicast trees for scalable cache coherence. In MICRO '08: Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, pages 35--46, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[11]

K. Fatahalian et al. Sequoia: programming the memory hierarchy. In SC '06, page 83, 2006.

Digital Library

[12]

D. Geer. Chip makers turn to multicore processors. Computer, 38(5):11--13, May 2005.

Digital Library

[13]

A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. S. Sunderam. PVM: Parallel Virtual Machine. MIT Press, 1994.

Digital Library

[14]

J. Gosling and G. Bollella. The Real-Time Specification for Java. Addison-Wesley Longman Publishing Co., Inc., 2000.

Digital Library

[15]

I. Gray and N. Audsley. Exposing non-standard architectures to embedded software using compile-time virtualisation. International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '09), 2009.

Digital Library

[16]

W. Gropp, E. Lusk, and A. Skjellum. Using MPI: portable parallel programming with the message-passing interface. MIT Press, Cambridge, MA, USA, 1994.

Digital Library

[17]

H. Huang, N. Yuan, W. Lin, G. Long, F. Song, L. Yu, Y. Liu, L. Liu, Y. Zhou, X. Ye, J. Zhang, D. Fan, and Z. Tang. Architecture supported synchronization-based cache coherence protocol for many-core processors. Chinese Journal of Computers, 8:1618--1630, 2009.

[18]

J. Kwon, A. Wellings, and S. King. Ravenscar-Java: A high integrity profile for Real-Time Java. In In Joint ACM Java Grande/ISCOPE Conference, pages 131--140. ACM Press, 2002.

Digital Library

[19]

M. Loghi, M. Poncino, and L. Benini. Cache coherence tradeoffs in shared-memory mpsocs. ACM Trans. Embed. Comput. Syst., 5(2):383--407, 2006.

Digital Library

[20]

A. L. Pope. The CORBA reference guide: understanding the Common Object Request Broker Architecture. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1998.

Digital Library

[21]

J. Robelly, G. Cichon, H. Seidel, and G. Fettweis. A HW/SW design methodology for embedded SIMD vector signal processors, 2005.

[22]

B. Sprunt, L. Sha, and J. Lehoczky. Aperiodic task scheduling for hard-real-time systems. Real-Time Systems, Volume 1:27--60, 1989.

[23]

D. Stranneby. Digital Signal Processing, DSP & Applications. Newnes, Oxford, 2001.

Digital Library

[24]

M. Ullmann, M. Huebner, B. Grimm, and J. Becker. An FPGA run-time system for dynamical on-demand reconfiguration. In Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International, pages 135--, April 2004.

[25]

Xilinx Corporation. Virtex-4 user guide. Xilinx User Guides, UG070, 2007.

[26]

C. A. Zeferino and A. A. Susin. SoCIN: A parametric and scalable network-on-chip. In SBCCI '03, page 169, Washington, DC, USA, 2003. IEEE Computer Society.

Digital Library

Cited By

Audsley NGray IKolovos DMatragkas NPaige RIndrusiak L(2013)Automatic Development of Embedded Systems Using Model Driven Engineering and Compile-Time VirtualisationEmbedded and Real Time System Development: A Software Engineering Perspective10.1007/978-3-642-40888-5_2(23-53)Online publication date: 20-Nov-2013
https://doi.org/10.1007/978-3-642-40888-5_2
Audsley NGray IAcquaviva AHaines R(2012)ToucHMore toolchain and system software for energy and variability customisation2012 IEEE International High Level Design Validation and Test Workshop (HLDVT)10.1109/HLDVT.2012.6418257(148-155)Online publication date: Nov-2012
https://doi.org/10.1109/HLDVT.2012.6418257
Gray IAudsley N(2011)Targeting complex embedded architectures by combining the multicore communications API (mcapi) with compile-time virtualisationACM SIGPLAN Notices10.1145/2016603.196768546:5(51-60)Online publication date: 11-Apr-2011
https://dl.acm.org/doi/10.1145/2016603.1967685
Show More Cited By

Index Terms

Supporting islands of coherency for highly-parallel embedded architectures using compile-time virtualisation
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Retargetable compilers

Recommendations

Targeting complex embedded architectures by combining the multicore communications API (mcapi) with compile-time virtualisation
LCTES '11: Proceedings of the 2011 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

Within the domain of embedded systems, hardware architectures are commonly characterised by application-specific heterogeneity. Systems may contain multiple dissimilar processing elements, non-standard memory architectures, and custom hardware elements. ...
Compile-time decided instruction cache locking using worst-case execution paths
CODES+ISSS '07: Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis

Caches are notorious for their unpredictability. It is difficult or even impossible to predict if a memory access results in a definite cache hit or miss. This unpredictability is highly undesired for real-time systems. The Worst-Case Execution Time (...
Predicting Cache Contention for Multithread Applications at Compile Time
IPDPSW '14: Proceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium Workshops

Shared cache in multicore processors is an important hardware resource that should be utilized effectively to achieve high performance for parallel applications. It is critical to coordinate accesses by multiple threads to data that reside in shared ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SCOPES '10: Proceedings of the 13th International Workshop on Software & Compilers for Embedded Systems

June 2010

91 pages

ISBN:9781450300841

DOI:10.1145/1811212

General Chair:
Ed Deprettere
Leiden University, NL
,
Program Chair:
Todor Stefanov
Leiden University, NL

Copyright © 2010 ACM.

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

EDAA: European Design Automation Association

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

SCOPES '10

Sponsor:

EDAA

SCOPES '10: 13th International Workshop on Software and Compilers for Embedded Systems

June 28 - 29, 2010

St. Goar, Germany

Acceptance Rates

Overall Acceptance Rate 38 of 79 submissions, 48%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
122
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Audsley NGray IKolovos DMatragkas NPaige RIndrusiak L(2013)Automatic Development of Embedded Systems Using Model Driven Engineering and Compile-Time VirtualisationEmbedded and Real Time System Development: A Software Engineering Perspective10.1007/978-3-642-40888-5_2(23-53)Online publication date: 20-Nov-2013
https://doi.org/10.1007/978-3-642-40888-5_2
Audsley NGray IAcquaviva AHaines R(2012)ToucHMore toolchain and system software for energy and variability customisation2012 IEEE International High Level Design Validation and Test Workshop (HLDVT)10.1109/HLDVT.2012.6418257(148-155)Online publication date: Nov-2012
https://doi.org/10.1109/HLDVT.2012.6418257
Gray IAudsley N(2011)Targeting complex embedded architectures by combining the multicore communications API (mcapi) with compile-time virtualisationACM SIGPLAN Notices10.1145/2016603.196768546:5(51-60)Online publication date: 11-Apr-2011
https://dl.acm.org/doi/10.1145/2016603.1967685
Gray IAudsley NVitek JDe Sutter B(2011)Targeting complex embedded architectures by combining the multicore communications API (mcapi) with compile-time virtualisationProceedings of the 2011 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems10.1145/1967677.1967685(51-60)Online publication date: 11-Apr-2011
https://dl.acm.org/doi/10.1145/1967677.1967685

View Options

Get Access

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.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents