Skip to main content

2018 | Buch

Invasive Computing for Mapping Parallel Programs to Many-Core Architectures

verfasst von: Dipl.-Ing. Andreas Weichslgartner, Dr. Stefan Wildermann, Prof. Michael Glaß, Prof. Jürgen Teich

Verlag: Springer Singapore

Buchreihe : Computer Architecture and Design Methodologies

insite
SUCHEN

Über dieses Buch

This book provides an overview of and essential insights on invasive computing. Pursuing a comprehensive approach, it addresses proper concepts, invasive language constructs, and the principles of invasive hardware. The main focus is on the important topic of how to map task-parallel applications to future multi-core architectures including 1,000 or more processor units. A special focus today is the question of how applications can be mapped onto such architectures while not only taking into account functional correctness, but also non-functional execution properties such as execution times and security properties.
The book provides extensive experimental evaluations, investigating the benefits of applying invasive computing and hybrid application mapping to give guarantees on non-functional properties such as timing, energy, and security. The techniques in this book are presented in a step-by-step manner, supported by examples and figures. All proposed ideas for providing guarantees on performance, energy consumption, and security are enabled by using the concept of invasive computing and the exclusive usage of resources.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
One of the most important trends in computer architecture in recent years is the paradigm shift toward multi and many-core chips. This chapter outlines the implications and challenges of future many-core architectures and gives an overview of the book’s contributions.
Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, Jürgen Teich
Chapter 2. Invasive Computing
Abstract
As this book originates in the context of invasive computing, this chapter gives an overview of the invasive computing paradigm and its realization in software and hardware. It starts with its basic principles and then gives an overview how the paradigm is expressed at the language level. Afterwards, a formal definition and analysis of invasive speedup and efficiency according to Teich et al. is given. For the formal analysis of individual application programs independent from each other through composability presented in the later chapters of this book, it is a prerequisite to consider an actual invasive hardware architecture. Therefore, a tiled invasive architecture with its building blocks is detailed with a focus on the (i-NoC). Finally, a brief description of the employed operating system is given before other approaches which deal with heterogeneous many-core systems are reviewed.
Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, Jürgen Teich
Chapter 3. Fundamentals
Abstract
This chapter introduces the required formal foundation on which the mapping algorithms in later chapters build on. It details the formal application and architecture models which abstract from any actual invasive hardware and software. Further, important concepts of predictability and composability are presented. To build a formal foundation for the mapping algorithms in Chaps. 46, this chapter introduces the required formal models and notations. It details the formal application and architecture models which abstract from any actual invasive hardware and software. Further, important concepts of predictability and composability are given. They are essential for assuring nonfunctional properties through the HAM methodology from Chaps. 5 and 6.
Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, Jürgen Teich
Chapter 4. Self-embedding
Abstract
In this chapter, a self-embedding algorithm is presented which solves the mapping problem consisting of task binding to tiles, respectively processors, and message routing to NoC links as formalized in the previous chapter in an autonomous way. In the realm of invasive computing, self-embedding tackles the problem in a resource-aware, decentralized, and adaptive manner. Contrary to related work, the application itself initiates and performs its own mapping autonomously. The main idea of the algorithm is that each task, or i-let in invasive computing, embeds its succeeding task and the respective communication towards it.
Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, Jürgen Teich
Chapter 5. Hybrid Application Mapping
Abstract
Previously, a new class of distributed application run-time mapping algorithms called self-embedding was presented. They are not designed for hard real-time applications which require an upper bound for end-to-end latency. To achieve predictability or even *-predictability, a static (performance) analysis is inevitable to determine and optimize upper and lower bounds. Therefore, a novel hybrid application mapping methodology (consisting of a design-time analysis and run-time mapping) is introduced. In contrast to related work, a packet-switched NoC communication, as in the invasive NoC, is considered.
Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, Jürgen Teich
Chapter 6. Hybrid Mapping for Increased Security
Abstract
In this chapter, it is shown that the introduced hybrid application mapping can also be utilized to increase security in heterogeneous many-core systems. In the case of security, it is proposed to use the concept of spatial isolation enabled by invasion to close side channels. This requires a shift from the optimization criteria in the previous chapter. There, the hop distance between tasks is maximized to increase the run-time embeddability as one constraint graph typically allows for many concrete mappings. For spatial isolation, so-called shapes as a second intermediate representation besides the constraint graph are introduced. As these shapes represent tiles and adjacent routers, no communication constraints have to be evaluated during run-time mapping. This eases the run-time mapping and transforms it basically to a constrained 2D packing problem. Consequently, fast heuristics as well as SAT-based solvers which choose fitting shape incarnations from each application concurrently may be applied.
Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, Jürgen Teich
Chapter 7. Conclusions and Future Work
Abstract
In this chapter, the book is summarized and the contributions are revisited. Further, an outlook of future research directions is given and first steps toward there are presented. This includes considering fault tolerance as nonfunctional requirement in our hybrid application mapping methodology, operating points distillation, exploring constraint graphs instead of classic task-to-concrete-resource-mapping, and improved run-time mapping.
Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, Jürgen Teich
Backmatter
Metadaten
Titel
Invasive Computing for Mapping Parallel Programs to Many-Core Architectures
verfasst von
Dipl.-Ing. Andreas Weichslgartner
Dr. Stefan Wildermann
Prof. Michael Glaß
Prof. Jürgen Teich
Copyright-Jahr
2018
Verlag
Springer Singapore
Electronic ISBN
978-981-10-7356-4
Print ISBN
978-981-10-7355-7
DOI
https://doi.org/10.1007/978-981-10-7356-4

Neuer Inhalt