Modeling and Simulation of Invasive Applications and Architectures

One of the most important drivers of technological advancements in microprocessors over the past half century was the continuous decrease in transistor size according to Moore’s law Moore(Electronics 38:114–117, 1965 [1]). It states that the number of transistors per chip will double approximately every two years, which corresponds to an exponential growth.

This chapter gives an introduction to the concepts of a computing paradigm called invasive computing, which has been introduced to tackle different problems that arise when designing and programming complex multi-core architectures comprising of hundreds to thousands of cores as well as hardware accelerators on a single chip (e.g., overheating, reliability, and power issues as well as resource contention). The basic principles of invasive computing as well as the realization of these concepts in hardware and software are explained. This chapter outlines the challenges in designing and programming future many-core architectures as well as the concepts of invasive computing on all layers from the hardware, over the runtime system to the language implementation. These concepts are introduced by the help of illustrations, graphs, and code snippets. Furthermore, a detailed introduction of the concepts, language constructs, and runtime implementation of the parallel programming language X10 is presented, which acts as the fundamental basis for realizing the ideas of invasive computing (InvadeX10) as well as for implementing the full-system simulator InvadeSIM and the actor-oriented programming library ActorX10. By the help of descriptive graphics, detailed descriptions, and various code examples, the partitioned global address space programming model, essential language features of X10 including extensions to the sequential core and the language constructs for concurrency, synchronization, and distribution as well as the X10 runtime system are explained, which helps the reader to understand modern concepts of parallel and distributed programming languages.

In this chapter novel, fast, and flexible simulation techniques for modern heterogeneous NoC-based multi-core architectures are presented. They include the design and development of the full-system simulator InvadeSIM, which allows modeling complex MPSoC architectures, emulating the execution behavior of the runtime system, and simulating function and timing of invasive parallel applications apart from utilization, efficiency, and competition. A novel high-level processor simulation approach based on direct-execution and a linear timing estimation model is proposed that tackles the complexity and the heterogeneity of current multi and many-core architectures. Furthermore, a discrete-event simulation framework is presented, which allows integrating and synchronizing different simulation tasks such as software or hardware simulations. Besides processor simulation, exemplary timing models for hardware accelerators such as tightly-coupled processor arrays and special cores with instruction-set extensions are presented.

In this chapter, an efficient hybrid NoC simulation approach is presented that allows simulating communication delays equally accurate but in average much faster than on a cycle-by-cycle basis. This approach includes novel algorithmic and analytical techniques, which dynamically predict the transmission delays of messages considering the actual congestion in the NoC, routing information, packet lengths, and other parameters. According to these predictions, the simulation time may be automatically advanced in many cases, which drastically reduces the number of cycles the NoC simulator has to process. Furthermore, the integration of the proposed NoC simulation technique into the full-system simulator InvadeSIM is shown.

In order to exploit the parallelism of a multi-core host machines, this chapter introduces four novel parallel discrete-event simulation techniques, which exploit the parallelism of the simulated target architectures and applications for parallel simulation on the host machine. In order to guarantee timing results equal to sequential simulation, a correct synchronization and activation of the parallel host threads are required, which is differently realized for each of the four proposed parallelization techniques. Furthermore, parallel simulation allows evaluating different architectural design choices such as the number of tiles, internal tile structure, and selection of cores within each tile. Here, case studies regarding performance and costs trade-offs of different heterogeneous invasive architecture variants are presented. The combination of the provided simulation techniques provides a holistic simulation approach for modern multi- and many-core architectures that is fast and accurate enough in timing to simulate parallel invasive applications so to gain valuable insight into their dynamic behavior and to evaluate different architecture alternatives. The reader will understand the presented concepts for modeling and accelerating the simulation of different hardware components on architecture level and how to combine them to a unified full-system simulation.

The focus of the this chapter is on models and techniques to guarantee real-time requirements made at design time independent from dynamic workloads. Here, so-called hybrid application mapping approaches are introduced. In this context, the design and implementation of a novel actor-oriented programming library called ActorX10 is presented, which allows describing computation and communication of stream processing applications formally. In order to find constellations of resources fulfilling statically determined resource constraints at run time, the implementation and evaluation of an efficient problem-specific mapping algorithm based on backtracking are presented. Furthermore, simulation-based real-world case studies to demonstrate the capabilities of invasive computing to provide predictable executions of stream processing applications on heterogeneous MPSoCs and to guarantee statically analyzed best and worst-case timing requirements on latency and throughput are presented. This chapter thereby presents an overview of current techniques to guarantee different execution time properties of parallel programs on multi-core architectures. The reader will understand the principles of actor-oriented programming and how applications modeled using these concepts are used in hybrid application mapping approaches. Real-world case studies help to understand how the presented concepts are practically applied and what their benefits are.

In this chapter, we shortly summarize the goals and achievements of this book and possible future directions. In this book novel simulation techniques have been investigated that enable the validation and variants’ exploration of all essential features of a novel computing paradigm called invasive computing.