Modeling cost/performance of a parallel computer simulator

This article examines the cost/performance of simulating a hypothetical target parallel computer using a commercial host parallel computer. We address the question of whether parallel simulation is simply faster than sequential simulation, or if it is also more cost-effective. To answer this, we develop a performance model of the Wisconsin Wind Tunnel (WWT), a system that simulates cache-coherent shared-memory machines on a message-passing Thinking Machines CM-5. The performance model uses Kruskal and Weiss's fork-join model to account for the effect of event processing time variability on WWT's conservative fixed-window simulation algorithm. A generalization of Thiebaut and Stone's footprint model accurately predicts the effect of cache interference on the CM-5. The model is calibrated using parameters extracted from a fully parallel simulation (p = N), and validated by measuring the speedup as the number of processors (p) ranges from 1 to the number of target nodes (N). Together with simple cost models, the performance model indicates that for target system sizes of 32 nodes and larger, parallel simulation is more cost-effective than sequential simulation. The key intuition behind this result is that large simulations require large memories, which dominate the cost of a uniprocessor; parallel computers allow multiple processors to simultaneously access this large memory.

Transactions Chasing Scalability and Instruction Locality on Multicores

Pinar Tözün

For several decades, online transaction processing (OLTP) has been one of the main server applications that drives innovations in the data management ecosystem, and in turn the database and computer architecture communities. Recent hardware trends oblige software to overcome two major challenges against systems scalability on modern multicore processors: (1) exploiting the abundant thread-level parallelism across cores and (2) taking advantage of the implicit parallelism within a core. The traditional design of the OLTP systems, however, faces inherent scalability problems due to its tightly coupled components. In addition, OLTP cannot exploit the full capability of the micro-architectural resources of modern processors because of the conventional scheduling decisions that ignore the cache locality for transactions. As a result, today’s commonly used server hardware remains largely underutilized leading to a huge waste of hardware resources and energy. .... In this thesis, we first identify the unbounded critical sections of traditional OLTP systems as the main enemy of thread-level parallelism. We design an alternative shared-everything system based on physiological partitioning (PLP) to eliminate the unbounded critical sections while providing an infrastructure for low-cost dynamic repartitioning and without introducing high-cost distributed transactions. Then, we demonstrate that L1 instruction cache stalls are the dominant factor leading to underutilization in the commodity servers. However, we also observe that independently of their high-level functionality, transactions running in parallel on a multicore system share significant amount of common instructions. By adaptively spreading the execution of a transaction over multiple cores through thread migration or multiplexing transactions on one core, we enable both an ample L1 instruction cache capacity for a transaction and reuse of common instructions across concurrent transactions. .... As the hardware demands more from the software to exploit the complexity and parallelism it offers in the multicore era, this work would change the way we traditionally schedule transactions. Instead of viewing a transaction as a single big task, we split it into smaller parts that can exploit data and instruction locality through careful dynamic scheduling decisions. The methods this thesis presents are not only specific to OLTP systems, but they can also benefit other types of applications that have concurrent requests executing a series of actions from a predefined set and face similar scalability problems on emerging hardware.

EPFL2014

Efficient Adaptive Hard Real-time Multi-processor Systems

Stefanos Skalistis

Modern computing systems are based on multi-processor systems, i.e. multiple cores on the same chip. Hard real-time systems are required to perform particular tasks within certain amount of time; failure to do so characterises an unaccepted behavior. Hard real-time systems are found in safety-critical applications, e.g. airbag control software, flight control software, etc. In safety-critical applications, failure to meet the real-time constraints can have catastrophic effects. The safe and, at the same time, efficient deployment of applications, with hard real-time constraints, on multi-processors is a challenging task. Scheduling methods and Models of Computation, that provide safe deployments, require a realistic estimation of the Worst-Case Execution Time (WCET) of tasks. The simultaneous access of shared resources by parallel tasks, causes interference delays due to hardware arbitration. Interference delays can be accounted for, with the pessimistic assumption that all possible interference can happen. The resulting schedules would be exceedingly conservative, thus the benefits of multi-processor would be significantly negated. Producing less pessimistic schedules is challenging due to the inter-dependency between WCET estimation and deployment optimisation. Accurate estimation of interference delays -and thus estimation of task WCET- depends on the way an application is deployed; deployment is an optimisation problem that depends on the estimation of task WCET. Another efficiency gap, which is of consequence in several systems (e.g. airbag control), stems from the fact that rarely tasks execute with their WCET. Safe runtime adaptation based on the Actual Execution Times, can yield additional improvements in terms of latency (more responsive systems). To achieve efficiency and retain adaptability, we propose that interference analysis should be coupled with the deployment process. The proposed interference analysis method estimates the possible amount of interference, based on an architecture and an application model. As more information is provided, such as scheduling, memory mapping, etc, the per-task interference estimation becomes more accurate. Thus, the method computes interference-sensitive WCET estimations (isWCET). Based on the isWCET method, we propose a method to break the inter-dependency between WCET estimation and deployment optimisation. Initially, the isWCETs are over-approximated, by assuming worst-case interference, and a safe deployment is derived. Subsequently, the proposed method computes accurate isWCETs by spatio-temporal exclusion, i.e. excluding interferences from non-overlapping tasks that share resources (space). Based on accurate isWCETs, the deployment solution is improved to provide better latency guarantees. We also propose a distributed runtime adaptation technique, that aims to improve run-time latency. Using isWCET estimations restricts the possible adaptations, as an adaptation might increase the interference and violate the safety guarantees. The proposed technique introduces statically scheduling dependencies between tasks that prevent additional interference. At runtime, a self-timed scheduling policy that respects these dependencies, is applied, proven to be safe, and with minimal overhead. Experimental evaluation on Kalray MPPA-256 shows that our methods improve isWCET up to 36%, guaranteed latency up to 46%, runtime performance up to 42%, with a consolidated performance gain of 50%.

EPFL2017

Architecture Exploration and Optimization of Heterogeneous Many-Core Compute and Memory Architectures with Architectural Extensions

Yasir Mahmood Qureshi

The expeditious proliferation of Internet connectivity and the growing adoption of digital products have transformed various spheres of our everyday lives. This increased digitization of society has led to the emergence of new applications, which are deployed all the way from High Performance Computing (HPC) systems and cloud servers to mobile devices. These new emerging applications like video analytics, autonomous driving, natural language processing, content recommendation, bioinformatics, and genome sequencing, have different performance/energy requirements, and are deployed on a variety of different platforms. To meet the performance and Quality-of-Service (QoS)constraints, cloud servers, and HPC platforms are comprised of many-core processors. Even the processors in today's mobile and edge devices are multi-core. To optimize energy efficiency and performance, a system-level simulator is required. This simulator must be capable of simultaneously executing multi-threaded applications in a full-system environment with a complete operating system (OS), on a heterogeneous many-core system.In this thesis, I present gem5-X, a system-level simulation platform to optimize many-core heterogeneous compute and memory architectures. Gem5-X exploration and optimization methodology is also proposed to optimize both the compute and memory sub-system for multi-thread applications. Gem5-X extends gem5 with architectural extensions for the compute and memory sub-systems, including in-caching computing accelerator, clustered heterogeneous cores, in-memory computing engine, and 3D stacked High Bandwidth Memory v2 (HBM2). It also adds support enhancements to gem5, including, Virtual Machine (VM) support, profiling support in the simulator using gperf profiler, enhanced checkpointing, and file sharing between the simulated and the host system. Finally, all the extensions and enhancements are fully supported in Full System (FS)mode of gem5-X, enabling booting and running a full Linux stack on top of the simulator, allowing almost any application running in a Linux system to be executed using gem5-X.To demonstrate the capabilities of gem5-X, various compute-dominated and memory-dominated applications are used as case studies. These state-of-the-art applications include video encoding, video analytics, VMs in the cloud, Binary Neural Networks (BNNs) and Recurrent Neural Networks (RNNs) as compute-intensive workloads. In addition to compute-dominated workloads, memory-dominated applications, including genome sequence alignment based on Next Generation Sequencing (NGS) techniques, and Convolutional Neural Networks (CNNs) are presented as case studies to demonstrate the memory sub-system extensions of gem5-X. Gem5-X exploration methodology is used to optimize architectures for these applications, achieving both performance and energy benefits. All the applications and workloads used in this thesis are case studies to showcase the capabilities of gem5-X. Gem5-X is generic and can be used to optimize and explore architectures for any multi-threaded (or single-threaded) application that can run on a Linux-based OS.

EPFL2021