To scale ILP, designers build deeper and wider out-of-order superscalar CPUs.However, this approach incurs quadratic scaling complexity, area, and energy costs with each generation.While small loops may benefit from increased instruction-window sizes and large loops may see speedups via thread-level parallelism across cores, there remains unexploited medium-granularity parallelism.We propose LoopFrog to tap into this potential by bringing thread-level speculation schemes into the modern era.LoopFrog runs multiple loop iterations from a single thread in parallel within the microarchitecture.The core can spawn future loop iterations as new microarchitectural threadlets based on compiler-inserted hints, which can leapfrog execution beyond the parent thread's instruction window, exposing a new, medium-grained parallelism, orthogonal to traditional ILP and TLP.LoopFrog monitors data dependencies between executing threadlets, forwards data for true dependencies and squashes speculative threadlets on ordering violations.Using an LLVM-based compiler to insert hints, we achieve a geometric mean loop speedup of 43%, translating to whole-program speedups of 9.2% on SPEC CPU 2006 and 9.5% on SPEC CPU 2017 benchmarks, with only modest area and power overheads.

Improving sequential performance of out-of-order processors is becoming harder. Further improvements may require exploitation of thread-level parallelism, on top of ILP, as it can provide better design and performance scaling. Unfortunately, previous “speculative multithreading” approaches have shown small gains and/or incur a high cost, particularly for general-purpose, non-numeric applications. This paper investigates the fundamental limits to sequential performance scaling through speculative multithreading - we present an LLVM compiler-driven limit study framework that investigates the limits of loop-level parallelism at run-time. This new study of loop-level parallelism demonstrates the potential for up to 4.6x and 7.2x geometric mean speedup on SpecINT2000 and SpecINT2006. Thanks to the additional consideration of recent parallelization schemes, such as generalized DOACROSS (HELIX), these potential speedups are higher than reported by previous state-of-the-art limit studies. Our analysis further categorizes the various inter-thread dependencies and ordering constraints with respect to the specific architectural choices and techniques each would require for implementation. We then evaluate the relative importance of each such constraint for different application (benchmark) types, and provide insight into the cost/benefit trade-offs when designing systems for efficiently implementing speculative multithreading. Such insights should help the design of bespoke systems for speculative multithreading while achieving better speedups, efficiency, and scaling, relative to typical approaches which, thus far, have relied upon adapting conventional multi-core systems. Our analysis further categorizes the various inter-thread dependencies and ordering constraints with respect to the specific architectural choices and techniques each would require for implementation. We then evaluate the relative importance of each such constraint for different application (benchmark) types, and provide insight into the cost/benefit trade-offs when designing systems for efficiently implementing speculative multithreading. Such insights should help the design of bespoke systems for speculative multithreading while achieving better speedups, efficiency, and scaling, relative to typical approaches which, thus far, have relied upon adapting conventional multi-core systems.

Although custom (and reconfigurable) computing can provide orders-of-magnitude improvements in energy efficiency and performance for many numeric, data-parallel applications, performance on nonnumeric, sequential code is often worse than conventional superscalar processors. This work attempts to improve sequential performance in custom hardware by (a) switching from a statically scheduled to a dynamically scheduled (dataflow) execution model and (b) developing a new compiler IR for high-level synthesis—the value state flow graph (VSFG)—that enables aggressive exposition of ILP even in the presence of complex control flow. Compared to existing control-data flow graph (CDFG)-based IRs, the VSFG exposes more instruction-level parallelism from control-intensive sequential code by exploiting aggressive speculation, enabling control dependence analysis, as well as execution along multiple flows of control. This new IR is directly implemented as a static-dataflow graph in hardware by our prototype high-level synthesis tool chain and shows an average speedup of 1.13× over equivalent hardware generated using LegUp, an existing CDFG-based HLS tool. Furthermore, the VSFG allows us to further trade area and energy for performance through loop unrolling, increasing the average speedup to 1.55×, with a peak speedup of 4.05×. Our VSFG-based hardware approaches the sequential cycle counts of an Intel Nehalem Core i7 processor while consuming only 0.25× the energy of an in-order Altera Nios II f processor.

With the impending Dark Silicon problem spelling doom for multicore performance scaling, there is an ever increasing need for processor architectures with much better energy efficiency. To address this, designers are increasingly utilising custom (and reconfigurable) computing to provide orders-of-magnitude improvements in energy efficiency over equivalent software implementations of the same code. Unfortunately, one of the key issues with custom computing is that it is often unable to match the performance of conventional processors when implementing irregular code with complex control-flow. Out-of-order superscalar processors implement aggressive branch prediction to speculate across multiple branches with very high accuracy, dynamically exposing ILP. But custom hardware lacks an efficient and safe control-flow speculation mechanism (particularly for loops), as it is difficult to implement misprediction roll-back and recovery in hardware without introducing a centralized synchronization bottleneck. By providing a mechanism for compiling high level languages to hardware, as well as improving performance of control-flow intensive code in hardware, much more pervasive utilization of custom and reconfigurable hardware were enable for general-purpose computation, thereby helping to mitigate the effects of dark silicon.

Simulated evolution (SimE) is an evolutionary metaheuristic that has produced results comparable to well established stochastic heuristics such as SA, TS and GA, with shorter runtimes. However, for problems with a very large set of elements to optimize, such as in VLSI placement and routing, runtimes can still be very large and parallelization is an attractive option. Compared to other metaheuristics, parallelization of SimE has not been extensively explored. This paper presents a comprehensive set of parallelization approaches for SimE when applied to multiobjective VLSI cell placement problem. Each of these approaches are evaluated with respect to SimE characteristics and the constraints imposed by the problem instance. Conclusions drawn can be extended to parallelization of other SimE based optimization problems

Simulated annealing (SA) is a popular iterative heuristic used to solve a wide variety of combinatorial optimization problems. However, depending on the size of the problem, it may have large run-time requirements. One practical approach to speed up its execution is to parallelize it. In this paper we develop parallel SA schemes based on the asynchronous multiple-Markov chain model (AMMC) described in S.-Y. Lee and K. G. Lee (1996) and applied to standard-cell placement as presented in J. Chandy et al. (1997), The schemes are applied to solve the multi-objective standard cell placement problem using an inexpensive cluster-of-workstations environment. This problem requires the optimization of conflicting objectives (interconnect wire-length, power dissipation, and timing performance), and fuzzy logic is used to integrate the costs of these objectives stated in J.A. Khan et al. (2002) and S. M. Sait and H. Youssef (2001). Experiments are performed on ISCAS-85/89 benchmark circuits. Our goal is to develop parallel SA schemes that provide significantly improved runtime/solution quality characteristics for this key CAD problem, by making the best possible use of an inexpensive parallel environment.

In this paper we present an evaluation of selected parallel strategies for Simulated Annealing and Simulated Evolution, identifying the impact of various issues on the effectiveness of parallelization. Issues under consideration are the characteristics of these algorithms, the problem instance, and the implementation environment. Observations are presented regarding the impact of parallel strategies on runtime and achievable solution quality. Effective parallel algorithm design choices are identified, along with pitfalls to avoid. We further attempt to generalize our assessments to other heuristics.