Near-threshold computing has emerged as a promising solution to significantly increase the energy efficiency of next-generation multicore systems. This paper evaluates and analyzes the behavior of dynamic voltage and frequency scaling for multicore systems operating under extended range: including near-threshold, nominal, and turbo modes. We adapt the model selection technique from machine learning to determine the relationship between performance and power. The theoretical results show that the resulting models satisfy convexity, which efficiently determines the optimal voltage/frequency operating points for: 1) minimizing energy consumption under throughput constraints or 2) maximizing throughput under a given power budget. We validate our models on FinFET-based chip-multiprocessors. Considering process variations (PVs), experimental results show that at 30% PV levels, our proposed method: 1) reduces energy consumption by 31.09% at iso-performance condition and 2) increases throughput by 11.46% at iso-power when compared with variation-agnostic nominal case.

This paper proposes an efficient algorithm that maximizes performance under power constraints and is applicable in the general context of traditional dynamic voltage/frequency (V/P) scaling, or core heterogeneity and emerging dynamic micro-architectural adaptation. Performance maximization in these scenarios can be essentially viewed as mapping application threads to appropriate core states that have various power/performance characteristics. Such problems are formulated as a generic 0-1 integer linear program (ILP). The proposed algorithm is an iterative heuristic-based solution. Compared with an optimal solution generated by commercial ILP solver, the proposed algorithm produces results less than 1% away from optimum on average, with more than two orders of magnitude improvement in runtime. The algorithm can be brought online for hundred-core heterogeneous systems as it scales to systems comprised of 256 cores with less than 1 ms in overhead in worst cases. The intrinsic history awareness also provides flexibility to control cost induced by switching V/F pairs, migrating threads across cores, or tuning on/off micro-architectural resources.

This paper addresses the problem of dynamic thread mapping in heterogeneous many-core systems via an efficient algorithm that maximizes performance under power constraints. Heterogeneous many-core systems are composed of multiple core types with different power-performance characteristics. As well documented in the literature, the generic mapping problem is an NP-complete problem which can be formulated as a 0-1 integer linear program, therefore, prohibitively expensive to solve optimally in an online scenario. However, in real applications, thread mapping decisions need to be responsive to workload phase changes. This paper proposes an iterative approach bounding the runtime as O(n2/m), for mapping multi-threaded applications on n cores comprising of m core types. Compared with an optimal solution, the proposed algorithm produces results less than 0.6% away from optimum on average, with two orders of magnitude improvement in runtime. Results show that performance improvement can reach 16% under iso-power constraints compared to a random mapping. The algorithm can be brought online for hundred-core heterogeneous systems as it scales to systems comprised of 256 cores with less than one millisecond in overhead.

Video applications including video codecs place a large traffic demand on main memory. Emerging memory technology, such as phase-change RAM (PRAM) tends to suffer from the write endurance problem, in which the maximum number of writes is limited. Thus, it is required to improve video application designs to adapt to the new requirements of emerging memory technology, i.e., to minimize the number of writes in terms of bit updates. In this paper, we present a way to optimize video application design for PRAM-based main memory. We propose two methods to resolve the write endurance problem: inter-block differential data encoding and inter-frame multiple experts. Experimental results show an average of 18.4% reduction in bit updates when compared to the best existing data encoding methods for PRAM.

One of the most serious constraints of an embedded system is its limited memory, which requires small code size for embedded software. One popular method to reduce the code size is reducing the instruction encoding, such as the ARM THUMB or the MIPS-16 architectures. They employ shorter instructions by reducing the field width, including those of register operands. This obviously reduces the number of registers available for register allocation than in the original architecture, which can lead to more register spills, negatively affecting the code size. This paper proposes a simple architectural upgrade by reconstructing the original register file into register banks and by providing a bank change instruction. This can allow all of the original registers to be available for register allocation when the bank change instructions are added appropriately. For such a banked register file, we propose an efficient, region-based register bank allocation technique where appropriate regions are chosen first for bank changes, followed by conventional global register allocation. As a case study, we apply the idea to the ARM THUMB architecture and evaluate how the upgrade affects its overall code size. We found that the upgrade results in an average of 5.0% code size reduction for some of MiBench and MediaBench benchmarks, compared to the original THUMB code.

Graph-coloring register allocators eliminate copies by coalescing the source and target nodes of a copy if they do not interfere in the interference graph. Coalescing, however, can be harmful to the colorability of the graph because it tends to yield a graph with nodes of higher degrees. Unlike aggressive coalescing , which coalesces any pair of noninterfering copy-related nodes, conservative coalescing or iterated coalescing perform safe coalescing that preserves the colorability. Unfortunately, these heuristics give up coalescing too early, losing many opportunities for coalescing that would turn out to be safe. Moreover, they ignore the fact that coalescing may even improve the colorability of the graph by reducing the degree of neighbor nodes that are interfering with both the source and target nodes being coalesced. This article proposes a new heuristic called optimistic coalescing which optimistically performs aggressive coalescing, thus exploiting the positive impact of coalescing aggressively, but when a coalesced node is to be spilled, it is split back into separate nodes. Since there is a better chance of coloring one of those splits, we can reduce the overall spill amount.

Enhanced pipeline scheduling (EPS) is a software pipelining technique which can achieve a variable initiation interval (II) for loops with control flow via its code motion pipelining. EPS, however, leaves behind many renaming copy instructions that cannot be coalesced due to interferences. These copies take resources and, more seriously, they may cause a stall if they rename a multilatency instruction whose latency is longer than the II aimed for by EPS. This paper proposes a code transformation technique based on loop unrolling which makes those copies coalescible. Two unique features of the technique are its method of determining the precise unroll amount, based on an idea of extended live ranges, and its insertion of special bookkeeping copies at loop exits. The proposed technique enables EPS to avoid a serious slowdown from latency handling and resource pressure, while keeping its variable II and other advantages. In fact, renaming through copies, followed by unroll-based copy elimination, is EPS's solution to the cross-iteration register overwrite problem in software pipelining. It works for loops with arbitrary control flow that EPS must deal with, as well as for straightline loops. Our empirical study performed on a VLIW testbed with a two-cycle load latency shows that 86 percent of the otherwise uncoalescible copies in innermost loops become coalescible when unrolled 2.2 times on average. In addition, it is demonstrated that the unroll amount obtained is precise and the most efficient. The unrolled version of the VLIW code includes fewer no-op VLIW caused by stalls, improving the performance by a geometric mean of 18 percent on a 16-ALU machine.

Aggressive instruction scheduling leaves behind many renaming copy instructions that cannot be coalesced due to interferences. These copies take resources, and more seriously, they may cause a stall if they are generated for renaming of multi-latency instructions. This paper proposes a code transformation technique based on loop unrolling which makes those copies coalescible. Two unique features of the technique are its method of determining the precise unroll amount based on an idea of extended live range, and its insertion of special bookkeeping copies at loop exits. In fact, the technique provides a more general and simpler solution for the cross-iteration register overwrite problem in software pipelining which works for loops with control flows as well as for straight-line loops. In addition, it is applicable to other optimizations including path length reduction and redundant subscripted reference elimination.