Search

Timing-based side and covert channels in processor caches continue to be a threat to modern computers. This work shows for the first time, a systematic, large-scale analysis of Arm devices and the detailed results of attacks the processors are vulnerable to. Compared to x86, Arm uses different architectures, microarchitectural implementations, cache replacement policies, etc., which affects how attacks can be launched, and how security testing for the vulnerabilities should be done. To evaluate security, this paper presents security benchmarks specifically developed for testing Arm processors and their caches. The benchmarks are evaluated with sensitivity tests, which examine how sensitive the benchmarks are to having a correct configuration in the testing phase. Further, to evaluate a large number of devices, this work leverages a novel approach of using a cloud-based Arm device testbed for architectural and security research on timing channels and runs the benchmarks on 34 different physical devices. In parallel, there has been much interest in secure caches to defend the various attacks. Consequently, this paper also investigates secure cache architectures using proposed benchmarks. Especially, this paper implements and evaluates secure PL and RF caches, showing the security of PL and RF caches, but also uncovers new weaknesses. [ABSTRACT FROM AUTHOR]

Layout synthesis, an important step in quantum computing, processes quantum circuits to satisfy device layout constraints. In this paper, we construct QUEKO benchmarks for this problem, which have known optimal depths and gate counts. We use QUEKO to evaluate the optimality of current layout synthesis tools, including Cirq from Google, Qiskit from IBM, ⟨t|ket〉 from Cambridge Quantum Computing, and a recent academic work. To our surprise, despite over a decade of research and development by academia and industry on compilation and synthesis for quantum circuits, we are still able to demonstrate large optimality gaps: 1.5-12x on average on a smaller device and 5-45x on average on a larger device. This suggests substantial room for improvement of the efficiency of quantum computer by better layout synthesis tools. Finally, we also prove the NP-completeness of the layout synthesis problem for quantum computing. We have made the QUEKO benchmarks open-source. [ABSTRACT FROM AUTHOR]

The introduction of multicore/multithreaded processors, comprised of a large number of hardware contexts (virtual CPUs) that share resources at multiple levels, has made process scheduling, in particular assignment of running threads to available hardware contexts, an important aspect of system performance. Nevertheless, thread assignment of applications running on state-of-the art processors is an NP-complete problem. Over the years, numerous studies have proposed heuristic-based algorithms for thread assignment. Since the thread assignment problem is intractable, it is in general impossible to know the performance of the optimal assignment, so the room for improvement of a given algorithm is also unknown. It is therefore hard to decide whether to invest more effort and time to improve an algorithm that may already be close to optimal. In this paper, we present a statistical approach to the thread assignment problem. First, we present a method that predicts the performance of the optimal thread assignment, based on the observed performance of each thread assignment in a random sample. The method is based on Extreme Value Theory (EVT), a branch of statistics that analyses extreme deviations from the population mean. We also propose sample pruning, a method that significantly reduces the time required to apply the statistical method by reducing the number of candidate solutions that need to be measured. Finally, we show that, if no suitable heuristic-based algorithm is available, a sample of several thousand random thread assignments is enough to obtain, with high confidence, an assignment with performance close to optimal. The presented approach is architecture and application independent, and it can be used to address the thread assignment problem in various domains. It is especially well suited for systems in which the workload seldom changes. An example is network systems, which typically provide a constant set of services that are known in advance, with network applications performing a similar processing algorithm for each packet in the system. In this paper, we validate our methods with an industrial case study for a set of multithreaded network applications on an UltraSPARC T2 processor. This article is an extension of our previous work [44] , which was published in Proceedings of 17th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-2012). [ABSTRACT FROM AUTHOR]

As process technologies evolves, tackling process variation problems is becoming more challenging in 3D (i.e., die-stacked) microprocessors. Process variation adversely affects performance, power, and reliability of the 3D microprocessors, which in turn results in yield losses. In particular, last-level caches (LLCs: L2 or L3 caches) are known as the most vulnerable component to process variation in 3D microprocessors. In this paper, we propose a novel cache architecture that exploits narrow-width values for yield improvement of LLCs (in this paper, L2 caches) in 3D microprocessors. Our proposed architecture disables faulty cache subparts and turns on only the portions that store meaningful data in the cache arrays, which results in high energy-efficiency as well as high cache yield. In an energy-/performance-efficient manner, our proposed architecture significantly recovers not only SRAM cell failure-induced yield losses but also leakage-induced yield losses. [ABSTRACT FROM PUBLISHER]

Recent works in the synthesis of reversible logic circuits have been motivated by ever increasing emphasis on low-power design alternatives, and recent developments in quantum computing. Although most of the synthesis approaches use multiple-control Toffoli (MCT) gates with positive control lines, a few recent works have also considered MCT gates with negative control lines resulting in better circuit realizations. Some of the works have also tried to carry out post-synthesis optimization of given MCT gate netlists with positive control lines, using template matching and similar netlist transformation techniques. However, only one work is reported that attempts to optimize netlists containing negative control MCT gates. This paper proposes an efficient optimization technique for MCT gate netlists with both positive and negative control lines, which is based on repeated applications of a small set of pairwise gate merging and replacement rules. Experiments carried out on reversible circuit benchmarks show that it is possible to achieve significant reductions in number of gates and quantum costs. [ABSTRACT FROM PUBLISHER]

This paper presents a novel technique, called Zombie Chasing, for efficient flash management in solid state drives (SSDs). Due to the unique characteristics of NAND flash memory, SSDs need to accurately understand the liveness of the data stored in themselves. Recently, the TRIM command has been introduced to notify SSDs of dead data caused by file deletions, which otherwise could not be tracked by SSDs. This paper goes one step further and proposes a new liveness state, called the zombie state, to denote live data that will be dead shortly due to the corresponding dirty data in the buffer cache. We also devise new zombie-aware garbage collection algorithms which utilize the information about such zombie data inside SSDs. To evaluate Zombie Chasing, we implement zombie-aware garbage collection algorithms in the prototype SSD and modify the Linux kernel and the Oracle DBMS to deliver the information on the zombie data to the prototype SSD. Through comprehensive evaluations using our in-house micro-benchmark and the TPC-C benchmark, we observe that Zombie Chasing improves SSD performance effectively by reducing garbage collection overhead. Especially, our evaluation with the TPC-C benchmark on the Oracle DBMS shows that Zombie Chasing enhances the Transactions Per Second (TPS) value by up to 22% with negligible overhead. [ABSTRACT FROM AUTHOR]

Modern computing systems typically use a large number of independent, non-identical computing nodes to perform a set of coordinated computations in parallel. The computing system and its constituent computing nodes often exhibit more than two performance levels or states corresponding to different computing powers. This paper models and evaluates performability of large-scale multi-state computing systems, which is the probability that a computing system performs at a particular performance level. The heterogeneity in the constituent components of different nodes (due to factors such as different model generations, model suppliers, and operating environments) makes performability analysis difficult and challenging. In this paper a specification method for system performance level (SPL) is first introduced. A multi-valued decision diagram (MDD) based approach is then proposed for performability analysis of multi-state computing systems consisting of nodes with different state occupation probabilities, which encompasses novel and efficient MDD model generation procedures. Example and benchmark studies are performed to show that the proposed approach can offer efficient performability analysis of large-scale computing systems. [ABSTRACT FROM PUBLISHER]

In network-on-chip (NoC) based CMPs, DVFS is commonly used to co-optimize performance and power. To achieve optimal efficiency, it is important to gain proportional performance growth with power. However, power over/under provisioning often exists. To properly evaluate and guide NoC DVFS techniques, it is highly desirable to formalize and quantify power over/under provisioning. In this paper, we first show that application performance does not grow linearly with network power in an NoC-based CMP. Instead, their relationship is non-linear and can be captured using performance-power characteristics curve (PPCC) with three distinct regions: an inertial region, a linear region, and a saturation region. We note that conventional DVFS metrics such as Performance Per Watt (PPW) cannot accurately evaluate such non-linear relationship. Based on PPCC, we propose a new figure of merit called Marginal Performance (MP) which evaluates the incremental performance per power increment after the inertial region. The MP concept enables to formally define power over- and under-provisioning with reference to the linear region in which an efficient NoC DVFS should operate. Applying the PPCC and MP concepts in full-system simulations with PARSEC and SPEC OMP2012 benchmarks, we are able to identify power over/under provisioning occurrences, measure and compare their statistics in two latest NoC DVFS techniques. Moreover, we show evidences that MP can accurately and consistently evaluate the NoC DVFS techniques, avoiding the misjudgement and inconsistency of PPW-based evaluations. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the triple patterning lithography layout decomposition problem. To address the problem, a discrete relaxation theory is built. For designing a discrete relaxation based decomposition framework, we propose a surface projection method for identifying native conflicts in a layout, and then constructing the conflict graph. Guided by the theory, the conflict graph is reduced to small size subgraphs by vertex removals, which is a discrete relaxation. Furthermore, by ignoring stitch insertions and assigning weights to features, the layout decomposition problem on the small subgraphs is further relaxed to a 0-1 program, which is solved by the Branch-and-Bound method. To obtain a feasible solution of the original problem, legalization methods are introduced to legalize a relaxation solution. At the legalization stage, we prior utilize one-stitch insertion to eliminate conflicts, and use a backtrack coloring algorithm to obtain a better solution. We test our decomposition approach on the ISCAS-85 & 89 benchmarks. Comparisons of experimental results show that our approach finds solutions of some benchmarks better than those by the state-of-the-art decomposers. Especially, according to our discrete relaxation theory, some optimal decompositions are obtained. [ABSTRACT FROM PUBLISHER]

The pervasive use of virtualization techniques in today's datacenters poses challenges in power monitoring since it is not possible to directly measure the power consumption of a virtual entity such as a virtual machine (VM) and a container. In this paper, we present cWatts++, a lightweight virtual power meter that enables accurate power usage measurement in virtualized computing environments such as VMs and containers of Cloud data centers. At the core of cWatts++ is its application-agnostic power model. To this end, we devise two power models (eventModel and raplModel) that are driven by CPU event counters and the Running Average Power Limit (RAPL) feature of modern Intel CPUs, respectively. While eventModel is more generic and, thus, applicable to a wide range of workloads, raplModel is particularly good for CPU-bound workloads. We have evaluated cWatts++ with its two power models in a real system using the PARSEC benchmark suite and our in-house benchmarks. Our evaluation study demonstrates that these power models have an average error of 4.55 and 1.25 percent, respectively, compared with actual power usage measurements of a real power meter, Cabac Power-Mate. [ABSTRACT FROM AUTHOR]

Given a chip that produced a faulty output response to a test set, a defect diagnosis procedure produces a set of candidate faults that is expected to identify the defects that are present in the chip. The accuracy of the set of candidate faults is higher when the set is smaller or when its overlap with the defects that are present in the chip is larger. To increase the accuracy of a set of candidate faults, this paper describes an approach where several sets of candidate faults are computed based on different subsets of the test set. The subsets are obtained by removing small numbers of tests from the complete test set. The result is sets of candidate faults that are similar but not identical. The number of sets where a fault appears yields a confidence level that the fault actually belongs in a set of candidate faults. New sets of candidate faults are defined based on the confidence levels obtained. The smallest set of candidate faults can be used as the final result of defect diagnosis, or the sets can be used for ranking the candidates. Experimental results for benchmark circuits demonstrate the effectiveness of this approach. [ABSTRACT FROM PUBLISHER]

The old virtualization idea and the new multicore technology now make it possible to consolidate multiple workloads on one physical host. This helps reduce the amount of idle resources. In particular, transcendent memory is a recent idea to gather idle memory into a pool that is shared by virtual machines (VMs). It can be viewed as a new level in the memory hierarchy, between main memory and disks. Cleancache is the part of transcendent memory that is used for caching the VMs’ clean pages. This paper shows that a Cache Miss Equation can accurately capture observed cleancache behavior, despite its unusual design. The equation can be used to dynamically size and partition cleancache for the VMs. Experiments with a variety of workloads show that this equation-based allocation can help to drastically reduce disk reads and fairly allocate cleancache space. [ABSTRACT FROM PUBLISHER]

Emerging non-volatile byte-addressable memory (NVM) introduces many opportunities and challenges to memory system designs. As data become persistent at main memory level, persistent memory systems need to guarantee the consistent state of data in the event of system failures (i.e., crash consistency). Existing studies propose persistent memory designs with software-transparent crash consistency guarantee to reduce programmers' manual effort when taking advantage of persistent memory. However, these designs are suboptimal due to their performance overhead caused by creating checkpoints. In this paper, we propose a Non-Intrusive memory COntroller design (NICO) that uses backend operations for achieving software-transparent crash consistency with minimized checkpointing overhead. By moving data persist operations to the background, NICO fully decouples data persist operations from volatile execution and cache management. To efficiently enforce crash consistency, we design a lightweight checkpointing scheme which only needs to flush and modify a very small amount of data when creating a consistent snapshot of persistent memory data. Our results show that NICO reduces the percent of time spent on checkpointing to within 0.9 percent across different benchmarks, and improves performance by 2.04× compared with existing checkpoint-based designs on average. [ABSTRACT FROM AUTHOR]

The mitigation of process variability becomes paramount as chip fabrication advances deeper into the sub-micron regime. Conservative guard-bands result in considerable performance loss, while most low-level solutions impede dynamic customization at application level. This paper exploits the existing process variability of commercial off-the-shelf FPGAs to improve the operating frequency of a design, in-the-field, at anytime during the lifetime of a chip. We begin by measuring variability in prevalent FPGAs and assessing its impact on the performance of common DSP benchmarks. For the former, we develop a custom sensing network of Ring-Oscillators to generate detailed 2D maps per chip. For the latter, we perform intensive testing and statistical analysis to establish the relation between variability maps and benchmark frequencies. Accordingly, we propose a framework to automatically characterize the user's devices, place the design on the most efficient region, and scale its frequency based on user requirements and functional verification. Experimental results on 20 FPGAs of 28 nm Xilinx technology show up to 13 percent intra-die and 30 percent inter-die variability; with limited cost, our framework provides 10$-$-14.7 percent average gain by exploiting such variability, or up to 56$-$-138 percent by also customizing the guard-band. [ABSTRACT FROM AUTHOR]

Sampled simulation is a mature technique for reducing simulation time of single-threaded programs. Nevertheless, current sampling techniques do not take advantage of other execution models, like task-based execution, to provide both more accurate and faster simulation. Recent multi-threaded sampling techniques assume that the workload assigned to each thread does not change across multiple executions of a program. This assumption does not hold for dynamically scheduled task-based programming models. Task-based programming models allow the programmer to specify program segments as tasks which are instantiated many times and scheduled dynamically to available threads. Due to variation in scheduling decisions, two consecutive executions on the same machine typically result in different instruction streams processed by each thread. In this paper, we propose TaskPoint, a sampled simulation technique for dynamically scheduled task-based programs. We leverage task instances as sampling units and simulate only a fraction of all task instances in detail. Between detailed simulation intervals, we employ a novel fast-forwarding mechanism for dynamically scheduled programs. We evaluate different automatic techniques for clustering task instances and show that DBSCAN clustering combined with analytical performance modeling provides the best trade-off of simulation speed and accuracy. TaskPoint is the first technique combining sampled simulation and analytical modeling and provides a new way to trade off simulation speed and accuracy. Compared to detailed simulation, TaskPoint accelerates architectural simulation with 8 simulated threads by an average factor of 220x at an average error of 0.5 percent and a maximum error of 7.9 percent. [ABSTRACT FROM AUTHOR]

Massive computation power and storage capacity of cloud computing systems enable users to either store large generated scientific datasets in the cloud or delete and then regenerate them whenever reused. Due to the pay-as-you-go model, the more datasets we store, the more storage cost we need to pay, alternatively, we can delete some generated datasets to save the storage cost but more computation cost is incurred for regeneration whenever the datasets are reused. Hence, there should exist a trade-off between computation and storage in the cloud, where different storage strategies lead to different total costs. The minimum cost, which reflects the best trade-off, is an important benchmark for evaluating the cost-effectiveness of different storage strategies. However, the current benchmarking approach is neither efficient nor practical to be applied on the fly at runtime. In this paper, we propose a novel Partitioned Solution Space based approach with efficient algorithms for dynamic yet practical on-the-fly minimum cost benchmarking of storing generated datasets in the cloud. In this approach, we pre-calculate all the possible minimum cost storage strategies and save them in different partitioned solution spaces. The minimum cost storage strategy represents the minimum cost benchmark, and whenever the datasets storage cost changes at runtime in the cloud (e.g. new datasets are generated and/or existing datasets’ usage frequencies are changed), our algorithms can efficiently retrieve the current minimum cost storage strategy from the partitioned solution space and update the benchmark. By dynamically keeping the benchmark updated, our approach can be practically utilised on the fly at runtime in the cloud, based on which the minimum cost benchmark can be either proactively reported or instantly responded upon request. Case studies and experimental results based on Amazon cloud show the efficiency, scalability and practicality of our approach. [ABSTRACT FROM AUTHOR]

A restoration based static test compaction procedure removes unnecessary test vectors from a functional test sequence in order to reduce its length. To allow the procedure to reduce the storage requirements of the sequence further, this paper introduces a new approach where a single stored sequence is used for applying several different functional test sequences. Under this approach, the stored sequence is considered as two-dimensional arrays with different dimensions. Each array yields a different test sequence, which is a permutation of the stored sequence. When the permutations are effective in detecting target faults, an existing static test compaction procedure, with certain modifications, can reduce the length of the stored sequence, and rely on the application of the permutations to detect all the target faults. Simulation results show significant reductions in the input test data volume. The cost of increased numbers of clock cycles for test application can be utilized for increasing the fault coverage of non-target faults. [ABSTRACT FROM AUTHOR]

As a fundamental task in computer architecture research, performance comparison has been continuously hampered by the variability of computer performance. In traditional performance comparisons, the impact of performance variability is usually ignored (i.e., the means of performance observations are compared regardless of the variability), or in the few cases directly addressed with $t$ -statistics without checking the number and normality of performance observations. In this paper, we formulate a performance comparison as a statistical task, and empirically illustrate why and how common practices can lead to incorrect comparisons. We propose a non-parametric hierarchical performance testing (HPT) framework for performance comparison, which is significantly more practical than standard $t$ -statistics because it does not require to collect a large number of performance observations in order to achieve a normal distribution of sample mean. In particular, the proposed HPT can facilitate quantitative performance comparison, in which the performance speedup of one computer over another is statistically evaluated. Compared with the HPT, a common practice which uses geometric mean performance scores to estimate the performance speedup has errors of $8.0$ to $56.3$ percent on SPEC CPU2006 or SPEC MPI2007, which demonstrates the necessity of using appropriate statistical techniques. This HPT framework has been implemented as an open-source software, and integrated in the PARSEC 3.0 benchmark suite. [ABSTRACT FROM PUBLISHER]

This paper exploits small-value locality to accelerate the execution of memory instructions. We find that small-value loads—loads with small-value operands of 8 bits or less—are common across 52 applications from the desktop, embedded, and media domains. We show that the relative occurrences of small-value loads remain fairly stable during the program execution. Moreover, we establish that the frequency of small-value loads are almost independent of compiler and input data. We then introduce the concept of small-value caches (SVC) to compactly store small-value memory words. We show that SVCs provide significant speedup and reduce the overall energy dissipation with negligible chip-area overhead. [ABSTRACT FROM PUBLISHER]

As multicore processors are deployed in mainstream computing, the need for software tools to help parallelize programs is increasing dramatically. Data-dependence profiling is an important program analysis technique to exploit parallelism in serial programs. More specifically, manual, semiautomatic, or automatic parallelization can use the outcomes of data-dependence profiling to guide where and how to parallelize in a program. However, state-of-the-art data-dependence profiling techniques consume extremely huge resources as they suffer from two major issues when profiling large and long-running applications: 1) runtime overhead and 2) memory overhead. Existing data-dependence profilers are either unable to profile large-scale applications with a typical resource budget or only report very limited information. In this paper, we propose an efficient approach to data-dependence profiling that can address both runtime and memory overhead in a single framework. Our technique, called SD$({}^3)$, reduces the runtime overhead by parallelizing the dependence profiling step itself. To reduce the memory overhead, we compress memory accesses that exhibit stride patterns and compute data dependences directly in a compressed format. We demonstrate that SD$({}^3)$ reduces the runtime overhead when profiling SPEC 2006 by a factor of 4.1× and 9.7× on eight cores and 32 cores, respectively. For the memory overhead, we successfully profile 22 SPEC 2006 benchmarks with the reference input, while the previous approaches fail even with the train input. In some cases, we observe more than a 20× improvement in memory consumption and a 16× speedup in profiling time when 32 cores are used. We also demonstrate the usefulness of SD$({}^3)$ by showing manual parallelization followed by data dependence profiling results. [ABSTRACT FROM AUTHOR]

Reliability to soft errors is an increasingly important issue as technology continues to shrink. In this paper, we show that applications exhibit different reliability characteristics on big, high-performance cores versus small, power-efficient cores, and that there is significant opportunity to improve system reliability through reliability-aware scheduling on heterogeneous multicore processors. We monitor the reliability characteristics of all running applications, and dynamically schedule applications to the different core types in a heterogeneous multicore to maximize system reliability. Reliability-aware scheduling improves reliability by 25.4 percent on average (and up to 60.2 percent) compared to performance-optimized scheduling on a heterogeneous multicore processor with two big cores and two small cores, while degrading performance by 6.3 percent only. We also introduce a novel system-level reliability metric for multiprogram workloads on (heterogeneous) multicores. We provide a trade-off analysis among reliability-, power- and performance-optimized scheduling, and evaluate reliability-aware scheduling under performance constraints and for unprotected L1 caches. In addition, we also extend our scheduling mechanisms to multithreaded programs. The hardware cost in support of our reliability-aware scheduler is limited to 296 bytes per core. [ABSTRACT FROM PUBLISHER]

Reuse distance is an important metric for analytical estimation of cache miss rate. To find the miss rate of a particular cache, the reuse distance profile has to be measured for that particular level and configuration of the cache. Significant amount of simulation time and overhead can be reduced if we can find the miss rate of higher level cache like L2 cache from the RD profile with respect to a lower level cache (i.e., cache that is closer to the processor) such as L1. The objective of this paper is to give an analytical method to find the miss rate of L2 cache for various configurations from the RD profile with respect to L1 cache. We consider all three types of cache inclusion policies namely (i) Strictly Inclusive, (ii) Mutually Exclusive and (iii) Non-Inclusive Non-Exclusive policy. We first prove some general results relating the RD profile of L1 cache to that of L2 cache. We use probabilistic analysis for our derivations. We validate our model against simulations, using the multi-core simulator Sniper with the PARSEC and the SPLASH benchmark suites. [ABSTRACT FROM PUBLISHER]

While several hardware mechanisms have been proposed to control the interaction between hardware threads in an SMT processor, few have addressed the issue of software-controllable SMT performance. The IBM POWER5 and POWER6 are the first high-performance processors implementing a software-controllable hardware-thread prioritization mechanism that controls the rate at which each hardware-thread decodes instructions. This paper shows the potential of this basic mechanism to improve several target metrics for various applications on POWER5 and POWER6 processors. Our results show that although the software interface is exactly the same, the software-controlled priority mechanism has a different effect on POWER5 and POWER6. For instance, hardware threads in POWER6 are less sensitive to priorities than in POWER5 due to the in order design. We study the SMT thread malleability to enable user-level optimizations that leverage software-controlled thread priorities. We also show how to achieve various system objectives such as parallel application load balancing, in order to reduce execution time. Finally, we characterize user-level transparent execution on POWER5 and POWER6, and identify the workload mix that best benefits from it. [ABSTRACT FROM PUBLISHER]

The significant process parameter variations occurring during fabrication of high performance sequential circuits, such as microprocessors, are posing relevant uncertainties on the power that such circuits will consume in the field, while executing workloads typical for the diverse products they are oriented to (e.g., cellular phones, notebooks, servers, etc). On the other hand, different kinds of products have different constraints on the maximal power that could be consumed during the execution of typical workloads, due to diverse needs in terms of charge autonomy, heat dissipation, etc. Consequently, the power that will be consumed by microprocessors during the execution of typical workloads in the field needs to be accurately characterized at the end of fabrication. Such a power consumption characterization (hereinafter referred to as “power binning”), will enable to classify microprocessors in “power bins”, each one containing microprocessors suitable for different kinds of products, thus enabling to introduce them all into the market for different kinds of products. Based on these considerations, in this paper we propose an approach to characterize accurately at the end of fabrication, and at low-cost (in terms of characterization time), the power that microprocessors will consume in the in-field during the execution of workloads typical for different kinds of products. Our approach exploits scan-based Logic Built-In Self-Test (LBIST) to apply to microprocessors’ sequential blocks test vectors that induce on their internal nodes an activity factor (AF) similar to that experienced during the in-field execution of workloads typical for different kinds of products, thus enabling to perform power binning by simply measuring their consumed power. Our approach enables to scale the AF from 0 percent up to 97.6 percent (on average for the considered benchmark circuits) compared to conventional LBIST, with a granularity of the 2 percent, thus enabling to emulate accurately the AF induced by workloads typical of a wide range of products. We propose a hardware implementation for our approach requiring a limited area overhead (lower than 3 percent) over conventional LBIST. [ABSTRACT FROM PUBLISHER]

Soft real-time applications often show bursty memory access patterns—requiring high memory bandwidth for a short duration of time—that are often critical for timely data processing and performance. We call the code sections that exhibit such characteristics as Memory-Performance Critical Sections (MPCSs). Unfortunately, in multicore architectures, non-real-time applications on different cores may also demand high memory bandwidth at the same time. Resulting bandwidth contention can substantially increase the time spent on MPCSs of soft real-time applications, which in turn could result in missed deadlines. In this paper, we present a memory access control framework called BWLOCK, which is designed to protect MPCSs of soft real-time applications. BWLOCK consists of a user-level libarary and a kernel-level memory bandwidth control mechanism. The user-level library provides a lock-like API to declare MPCSs for real-time applications. When a real-time application enters a MPCS, the kernel-level bandwidth control mechanism dynamically throttles memory bandwidth of the rest of the cores to protect the MPCS, until it is completed. We evaluate BWLOCK using CortexSuite benchmarks. By selectively applying BWLOCK, based on the memory intensity of the code blocks in each benchmark, we achieve significant performance improvements, up to 150 percent reduction in slowdown, at a controllable throughput impact to non real-time applications. [ABSTRACT FROM AUTHOR]

Functional Units that are designed to receive inputs and produce outputs using a non-redundant format typically exhibit an inferior performance. In order to overcome this limitation, the carry-save and partial carry-save formats have been proposed. Both approaches are very suitable when implementing addition trees. Nevertheless, if there are multiplications in the datapath, the inputs to the multiplier must be reduced to a non-redundant form, to avoid applying the distributive property. In this paper we present a multiplier able to receive two numbers in partial carry-save format, and produce a result in partial carry-save format as well. This is done by modifying the Booth encoder and leveraging the generate and propagate group signals that are available because of the partial carry-save format. Hence, this can allow to fully implement datapaths without additional penalty cycles due to reductions to non-redundant forms. Experiments show that our proposed multiplier has 15 percent shorter delay with respect to a conventional Booth radix-4 multiplier. Moreover, when combining it with partial carry-save adders it is possible to reduce 36 percent execution time on average for several benchmarks, achieving a 32.7 percent reduction in the Energy Delay Product at the same time. [ABSTRACT FROM AUTHOR]

Infrastructure-as-a-service (IaaS) cloud providers offer tenants elastic computing resources in the form of virtual machine (VM) instances to run their jobs. Recently, providing predictable performance (i.e., performance guarantee) for tenant applications is becoming increasingly compelling in IaaS clouds. However, the hardware heterogeneity and performance interference across the same type of cloud VM instances can bring substantial performance variation to tenant applications, which inevitably stops the tenants from moving their performance-sensitive applications to the IaaS cloud. To tackle this issue, this paper proposes Heifer, a Heterogeneity and interference-aware VM provisioning framework for tenant applications, by focusing on MapReduce as a representative cloud application. It predicts the performance of MapReduce applications by designing a lightweight performance model using the online-measured resource utilization and capturing VM interference. Based on such a performance model, Heifer provisions the VM instances of the good-performing hardware type (i.e., the hardware that achieves the best application performance) to achieve predictable performance for tenant applications, by explicitly exploring the hardware heterogeneity and capturing VM interference. With extensive prototype experiments in our local private cloud and a real-world public cloud (i.e., Microsoft Azure) as well as complementary large-scale simulations, we demonstrate that Heifer can guarantee the job performance while saving the job budget for tenants. Moreover, our evaluation results show that Heifer can improve the job throughput of cloud datacenters, such that the revenue of cloud providers can be increased, thereby achieving a win-win situation between providers and tenants. [ABSTRACT FROM PUBLISHER]

Scratchpad memories in GPU architectures are employed as software-controlled caches to increase the effective GPU memory bandwidth. Through the use of well-known optimization techniques, such as privatization and tiling, they are properly exploited. Typically, they are banked memories which are addressed with a \textmod(2^N) bank indexing scheme. Although their bandwidth is fully exploited for linear memory accesses, their performance is burdened when non-unit strides appear in memory access patterns because they provoke bank conflicts. This paper explores the use of configurable bit-vector and bitwise XOR-based hash functions to evenly distribute memory addresses of the access patterns over the memory banks, reducing the number of bank conflicts. An exhaustive, but lightweight, search is used to configure bit-vector hash functions. Bitwise hash functions are configured with heuristics. Hardware and software implementations are carried out. For the hardware approach, the experimental results show 24 percent performance speed-up for 22 benchmarks on GPGPU-Sim, a Fermi-like simulator. Bank conflicts are reduced by 96 percent with bit-vector hash functions, and 97 percent with bitwise hash functions using our proposed Minimum Imbalance Heuristic. The software approach, using bit-vector hash functions, demonstrates 23 percent speed-up and 96 percent bank conflict reduction on a Fermi GPU, and 33 percent speed-up and 99 percent bank conflict reduction on a Kepler GPU. [ABSTRACT FROM AUTHOR]

Software Transactional Memory (STM) has recently emerged as a promising synchronization abstraction for multicore architectures. State-of-the-art STM algorithms, however, suffer from performance challenges due to contention and spinning on locks during the transaction commit phase. In this paper, we introduce Remote Transaction Commit (or RTC), a mechanism for executing commit phases of STM transactions. RTC dedicates server cores to execute transactional commit phases on behalf of application threads. This approach has two major benefits. First, it decreases the overheads of spinning on locks during commit, such as the number of cache misses, blocking of lock holders, and CAS operations. Second, it enables exploiting the benefits of coarse-grained locking algorithms (simple and fast lock acquisition, reduced false conflicts) and bloom filter-based algorithms (concurrent execution of independent transactions). Our experimental study on a 64-core machine with four sockets shows that RTC solves the problem of performance degradation due to spin locking on both micro-benchmarks (red-black trees), and macro-benchmarks (STAMP), especially when the commit phase is relatively long and when thread contention increases. [ABSTRACT FROM PUBLISHER]

Emerging data-intensive applications are creating non-uniform CPU and I/O workloads which impose the requirement to consider both CPU and I/O effects in the power management strategies. Current approaches focus on scaling down the CPU frequency based on CPU busy/idle ratio without taking I/O into considertation. Therefore, they do not fully exploit the opportunities in power conservation. In this paper, we propose a novel power management scheme called model-free, adaptive, rule-based (MAR) in multiprocessor systems to minimize the CPU power consumption subject to performance constraints. By introducing new I/O wait status, MAR is able to accurately describe the relationship between core frequencies, performance and power consumption. Moreover, we adopt a model-free control method to filter out the I/O wait status from the traditional CPU busy/idle model in order to achieve fast responsiveness to burst situations and take full advantage of power saving. Our extensive experiments on a physical testbed demonstrate that, for SPEC benchmarks and data-intensive (TPC-C) benchmarks, an MAR prototype system achieves 95.8-97.8 percent accuracy of the ideal power saving strategy calculated offline. Compared with baseline solutions, MAR is able to save 12.3-16.1 percent more power while maintain a comparable performance loss of about 0.78-1.08 percent. In addition, more simulation results indicate that our design achieved 3.35-14.2 percent more power saving efficiency and 4.2-10.7 percent less performance loss under various CMP configurations as compared with various baseline approaches such as LAST, Relax, PID and MPC. [ABSTRACT FROM PUBLISHER]

Graphics processing units (GPU), due to their massive computational power with up to thousands of concurrent threads and general-purpose GPU (GPGPU) programming models such as CUDA and OpenCL, have opened up new opportunities for speeding up general-purpose parallel applications. Unfortunately, pre-silicon architectural simulation of modern-day GPGPU architectures and workloads is extremely time-consuming. This paper addresses the GPGPU simulation challenge by proposing a framework, called GPGPU-MiniBench, for generating miniature, yet representative GPGPU workloads. GPGPU-MiniBench first summarizes the inherent execution behavior of existing GPGPU workloads in a profile. The central component in the profile is the Divergence Flow Statistics Graph (DFSG), which characterizes the dynamic control flow behavior including loops and branches of a GPGPU kernel. GPGPU-MiniBench generates a synthetic miniature GPGPU kernel that exhibits similar execution characteristics as the original workload, yet its execution time is much shorter thereby dramatically speeding up architectural simulation. Our experimental results show that GPGPU-MiniBench can speed up GPGPU architectural simulation by a factor of 49$\times$ on average and up to 589 $\times$ , with an average IPC error of 4.7 percent across a broad set of GPGPU benchmarks from the CUDA SDK, Rodinia and Parboil benchmark suites. We also demonstrate the usefulness of GPGPU-MiniBench for driving GPU architecture exploration. [ABSTRACT FROM PUBLISHER]

Test vector omission was introduced as a static test compaction procedure for functional test sequences. Experimental results indicated that it can also increase the fault coverage accidentally when it is applied to a sequence that does not detect all the detectable target faults. However, this capability was not explored directly. It is important since test vector omission provides a smaller search space for functional test sequences than any existing approach to sequential test generation. This paper describes a branch-and-bound procedure for test vector omission whose goal is to find functional test sequences for faults that are not detected by a given sequence. Experimental results for benchmark circuits demonstrate that the procedure provides a cost-effective addition to a simulation-based sequential test generation procedure. [ABSTRACT FROM PUBLISHER]

Numerous algorithms have been proposed for the well-known multi-constrained shortest path (MCSP) problem, but very few have good practical performance in case of two or more constraints. In this paper, we propose a new Lagrangian relaxation algorithm to solve a generalized version of the MCSP problem where we search for multiple shortest paths subject to multiple constraints. As in some related work, our algorithm first identifies the lower and upper bounds, and then tries to close the gap with a path enumeration procedure. However, our algorithm is based on the recognition that the Lagrange multipliers found by existing methods usually do not give the best search direction for minimizing path enumerations even though they can provide near-optimized lower bounds. We provide a solution to meet both of these goals, and incorporate feasibility checks into a state-of-the-art K-shortest paths algorithm to further reduce path enumerations. Through experiments on various networks including the most challenging benchmark instances, we show that our algorithm can solve a significantly larger number of instances to optimality with less computational cost, often by one or two orders of magnitude, when compared with the best known algorithm in the literature. [ABSTRACT FROM PUBLISHER]

In this paper we introduce ICCI, a new cache organization that leverages shared cache resources and flat coherence protocols to provide inexpensive hardware cache coherence for large core counts (e.g., 512), achieving execution times close to a non-scalable sparse directory while noticeably reducing the energy consumption of the memory system. Very simple changes in the system with respect to traditional bit-vector directories are enough to implement ICCI. Moreover, ICCI does not introduce any storage overhead with respect to a broadcast-based protocol, yet it provides large storage space for coherence information. ICCI makes smarter use of cache resources by dynamically allowing last-level cache entries to store blocks or sharing codes. This way, just the minimum number of directory entries required at runtime are allocated. Besides, ICCI suffers a negligible amount of directory-induced invalidations. Results for a 512-core CMP show that ICCI reduces the energy consumption of the memory system by up to 48 percent compared to a tag-embedded directory, up to 15 percent compared to a sparse directory, and up to 8 percent compared to the state-of-the-art Scalable Coherence Directory which ICCI also outperforms in execution time. In addition, ICCI can be used in combination with elaborated sharing codes to apply it to extremely large core counts. We also show analytically that ICCI’s dynamic allocation of entries makes it a suitable candidate to store coherence information efficiently for very large core counts (e.g., over 200K cores), based on the observation that data sharing makes fewer directory entries necessary per core as core count increases. [ABSTRACT FROM PUBLISHER]

In response to the increasing ubiquity of multicore processors, applications are usually designed or deployed to make each core busy. Unfortunately, lock contention within operating systems can limit the scalability of multicore systems so severely that an increase in the number of cores can actually lead to reduced performance (i.e., scalability collapse). Existing lock implementations have disadvantages in scalability, power consumption, and energy efficiency. In this paper, we observe that the number of tasks requesting a lock has a significant correlation with the occurrence of scalability collapse. Based on this observation, a lock implementation that allows tasks waiting for a lock to either spin or enter a power-saving state based on the number of requesters is proposed. Our lock protocol is called requester-based lock and is implemented in the Linux kernel to replace its default spin lock. Based on the results of a sensitivity analysis, we find that the best policy, in practice, for a task waiting for a lock to be granted is to enter the power-saving state immediately after noticing the lock cannot be acquired. Our requester-based lock scheme is evaluated using intensive benchmarking on AMD 32-core and Intel 40-core systems. Experimental results suggest that our lock avoids scalability collapse completely for most applications and shows better scalability, power consumption, and energy efficiency than previous work. Besides, the requester-based lock is extensible, which means using together with other kinds of spin locks can provide better scalability and energy efficiency. [ABSTRACT FROM AUTHOR]

State-of-the-art chip multiprocessor (CMP) proposals emphasize general optimizations designed to deliver computing power for many types of applications. Potentially, significant performance improvements that leverage application-specific characteristics such as data access behavior are missed by this approach. In this paper, we demonstrate how scalable and high-performance parallel systems can be built by classifying data accesses into different categories and treating them differently. We develop a novel compiler-based approach to speculatively detect a data classification termed practically private, which we demonstrate is ubiquitous in a wide range of parallel applications. Leveraging this classification provides efficient solutions to mitigate data access latency and coherence overhead in today’s many-core architectures. While the proposed data classification scheme can be applied to many micro-architectural constructs including the TLB, coherence directory, and interconnect, we demonstrate its potential through an efficient cache coherence design. Specifically, we show that the compiler-assisted mechanism reduces an average of 46% coherence traffic and achieves up to 12%, 8%, and 5% performance improvement over shared, private, and state-of-the-art NUCA-based caching, respectively, depending on scenarios. [ABSTRACT FROM AUTHOR]

Power dissipation trends are leading high-performance processors to a regime in which all chip elements cannot be operated simultaneously at maximum frequency. Consequently, energy-efficiency will increase even more in importance, and performance must be achieved within strict power budgets. Current designs employ techniques such as dynamic voltage and frequency scaling (DVFS) to provide power-performance tradeoffs for both single and multi-threaded workloads. In power-dominated regimes, processors will be run at or near the minimum voltage. Frequency can be reduced to save power, but there is no scaling strategy for increasing performance with high energy-efficiency if the processor is operating at its maximum frequency (and minimum voltage). In this paper, we evaluate the energy-efficiency of processor composability—dynamically aggregating small energy-efficient physical cores into larger logical processors—as a method of scaling single-threaded performance up and down, comparing composability to the energy-efficiency of voltage and frequency scaling. We measure the power breakdowns of the baseline composable microarchitecture (the TFlex microarchitecture, based on an EDGE ISA) and compare the energy-efficiency and performance to one processor designed for power-efficiency (XScale) and another designed for high-performance (a variant of the Power-4) using normalized power models for as fair a comparison as possible. The study shows that composing multiple dual-issue cores (up to eight) provides performance scaling that is as energy-efficient as frequency scaling in a balanced microarchitecture, and is considerably more efficient than scaling the voltage to achieve additional performance once the maximum frequency at the minimum voltage is attained. [ABSTRACT FROM AUTHOR]

Reducing memory access conflicts is a crucial part of the design of Transactional Memory (TM) systems since the number of running threads increases and long latency transactions gradually appear: without an efficient contention management, there will be repeated aborts and wasteful rollback operations. In this paper, we present a dynamic backoff control algorithm developed for complexity-effective and distributed contention management in Hardware Transactional Memory (HTM) systems. Our approach aims at controlling the restarting intervals of aborted transactions, and can be easily applied to the various TM systems. To this end, we have profiled the applications of the STAMP benchmark suite and have identified those “problem” transactions which repeatedly cause aborts in the applications with the attendant high contention rate. The proposed algorithm alleviates the impact of these repeated aborts by dynamically adjusting the initial exponent value of the traditional backoff approach. In addition, the proposed scheme decreases the number of wasted cycles down to 82% on average compared to the baseline TM system. Our design has been integrated in LogTM-SE where we observed an average performance improvement of 18%. [ABSTRACT FROM PUBLISHER]

Most chip-multiprocessors nowadays adopt a large shared last-level cache (SLLC). This paper is motivated by our analysis and evaluation of state-of-the-art cache management proposals which reveal a common weakness. That is, the existing alternative replacement policies and cache partitioning schemes, targeted at optimizing either locality or utility of co-scheduled threads, cannot deliver consistently the best performance under a variety of workloads. Therefore, we propose a novel adaptive scheme, called CLU, to interactively co-optimize the locality and utility of co-scheduled threads in thread-aware SLLC capacity management. CLU employs lightweight monitors to dynamically profile the LRU (least recently used) and BIP (bimodal insertion policy) hit curves of individual threads on runtime, enabling the scheme to co-optimize the locality and utility of concurrent threads and thus adapt to more diverse workloads than the existing approaches. We provide results from extensive execution-driven simulation experiments to demonstrate the feasibility and efficacy of CLU over the existing approaches (TADIP, NUCACHE, TA-DRRIP, UCP, and PIPP). [ABSTRACT FROM PUBLISHER]

Rapid growth of cloud computing services have led to creation of large scale enterprise data centers which consume great amounts of energy. Data centers usually have an service level agreement (SLA) between the clients and the service providers, which specify the terms and quality of service to be provided. In this paper, we consider a situation in a data center where multiple user applications are executing on a multi-core system and each application may have a specified SLA requirement. We design a voltage and frequency scheduler (the “cool” scheduler) that can be used in enterprise data centers to provide CPU energy saving under the specified SLA requirement by exploiting the applications’ run-time program phases. Our design greatly improves the computation efficiency compared to other recently published works. The scheduler is built into the Linux kernel and evaluated against SPEC CPU2006 and Phoronix Test Suite on a quad-core system. Experiment result demonstrates that our cool scheduler achieves 25.8% energy saving on average with 8.7% performance loss under the given SLA requirement (10% allowed performance loss). Our design achieves 35.8% and 31.6% more energy saving compared to two of the most advanced related works. [ABSTRACT FROM AUTHOR]

Prohibitive simulation time with pre-silicon design models and unavailability of proprietary target applications make microprocessor design very tedious. The framework proposed in this paper is the first attempt to automatically generate synthetic benchmark proxies for real world multithreaded applications. The framework includes metrics that characterize the behavior of the workloads in the shared caches, coherence logic, out-of-order cores, interconnection network and DRAM. The framework is evaluated by generating proxies for the workloads in the multithreaded PARSEC benchmark suite and validating their fidelity by comparing the microarchitecture dependent and independent metrics to that of the original workloads. The average error in IPC is 4.87 percent and maximum error is 10.8 percent for Raytrace in comparison to the original workloads. The average error in the power-per-cycle metric is 2.73 percent with a maximum of 5.5 percent when compared to original workloads. The representativeness of the proxies to that of the original workloads in terms of their sensitivity to design changes is evaluated by finding the correlation coefficient between the trends followed by the synthetic and the original for design changes in IPC, which is 0.92. A speedup of four to six orders of magnitude is achieved by using the synthetic proxies over the original workloads. [ABSTRACT FROM PUBLISHER]

The rapid advancements in the computational capabilities of the graphics processing unit (GPU) as well as the deployment of general programming models for these devices have made the vision of a desktop supercomputer a reality. It is now possible to assemble a system that provides several TFLOPs of performance on scientific applications for the cost of a high-end laptop computer. While these devices have clearly changed the landscape of computing, there are two central problems that arise. First, GPUs are designed and optimized for graphics applications resulting in delivered performance that is far below peak for more general scientific and mathematical applications. Second, GPUs are power hungry devices that often consume 100-300 watts, which restricts the scalability of the solution and requires expensive cooling. To combat these challenges, this paper presents the PEPSC architecture—an architecture customized for the domain of data parallel dense matrix style scientific application where power efficiency is the central focus. PEPSC utilizes a combination of a 2D single-instruction multiple-data (SIMD) datapath, an intelligent dynamic prefetching mechanism, and a configurable SIMD control approach to increase execution efficiency over conventional GPUs. A single PEPSC core has a peak performance of 120 GFLOPs while consuming 2 W of power when executing modern scientific applications, which represents an increase in computation efficiency of more than 10X over existing GPUs. [ABSTRACT FROM AUTHOR]

Multimedia computation has clearly become a primary and demanding application segment for new architectures targeted at portable devices. The main challenge for such architectures is to keep pace with the computational requirements of ever evolving media standards and applications while satisfying the power and energy consumption required to leverage smaller form-factors and longer battery lifetimes. One technique aimed at reducing both the energy consumption and the execution time of an application is Reuse. This technique memorizes the outcome of an instruction or set of instructions so that we can reuse it the next time we perform the same operation with the same inputs. In this paper, we analyze a region reuse schema specially focused on multimedia applications. While the technique appears to be, in theory, a promising vehicle to improve both timing and energy for low-end media applications, we will show that the extra hardware cost required becomes a severe shortcoming as we find the undesirable situation where we have to consume more energy in order to reduce the execution time (hence becoming a poor power-oriented solution). To mitigate the overhead of the reuse hardware, we advocate for exploiting a third variable in the power-time trade-off and we evaluate tolerant region reuse, a technique that relies in the tolerance in the output precision of media algorithms to improve reuse. With this technique, we afford to use less consuming hardware structures that drives benefits in both energy and timing. As a trade-off, tolerant region reuse introduces non-noticeable errors in the output data. The main drawback of tolerant region reuse is the strong reliance on application profiling, the need for careful tuning from the application developer, and the inability of the technique to adapt to the variability of the media contents being used as inputs. To address that inflexibility, we introduce dynamic tolerant region reuse. This novel technique overcomes the drawbacks of tolerant region reuse by allowing the hardware to study the precision quality of the region reuse output. Our mechanism allows the programmer to grant a minimum threshold on signal-to-noise ratio (SNR) while letting the technique adapt to the characteristics of the specific application and workload to minimize time and energy consumption. This leads to greater energy-delay savings while keeps output error below noticeable levels, avoiding at the same time the need of profiling. We studied our mechanism applied to a set of three different processors, from low to high end. As we will show our technique leads to consistent performance improvements in all of our benchmark programs while reducing energy consumption. We can report savings up to 30 percent in the energy*delay factor for all three processors. [ABSTRACT FROM PUBLISHER]

As the safety-critical applications (e.g., automotive and medical electronics) emerge, various techniques of radiation hardening by design (RHBD) are proposed to deal with soft errors. Among all RHBD techniques, Built-In Soft-Error Resilience (BISER) is the first one to apply the delayed latching to separate input signals on all flip-flops for error detection. However, the delay values induced by BISER extend the setup time of all flip-flops, and may fail to meet the timing specification of the design. For minimizing such delay impact on the setup time of each flip-flop, we propose the Automated Latching-Delay Assignment (ALDA) to transfer partial values to the CK-Q delay. Later, Time-Borrowable D-Flip-Flop (TBD-FF) as well as a modified design flow is also proposed to realize the delay assignment by ALDA and to complete the design hardening. Experiments show that ALDA together with TBD-FF effectively protects five benchmark circuits against soft errors, and optimally avoids the timing violations caused by the prior delayed-latching solutions. [ABSTRACT FROM AUTHOR]

Homing sequence derivation for nondeterministic finite state machines (NFSMs) has important applications in software/hardware system testing and verification. Unlike prior methods based on explicit tree-based search, in this article we formulate the derivation of a preset/adaptive homing sequence in terms of quantified Boolean formula (QBF) solving. This formulation exploits compact circuit representation of NFSMs and QBF encoding of the existence condition of homing sequence for effective computation. The implicit circuit representation effectively avoids explicit state enumeration, and can be more scalable. Different encoding schemes and QBF solvers are evaluated for their suitability for the homing sequence derivation. Experiments on various computation methods and benchmarks show the generality and feasibility of a proposed approach. [ABSTRACT FROM AUTHOR]

In the era of big data processing, more and more data centers in cloud storage are now replacing traditional HDDs with enterprise SSDs. Both developers and users of these SSDs require thorough benchmarking to evaluate and configure the variable parameters of emerging technologies. and are the recent development of the SSD industry, which assists in placing data on SSDs in a smart way to improve application performance and SSD endurance. The challenging part to use multi-stream SSDs is to assign stream IDs to incoming writes, such that each stream consists of data with a similar lifetime. The benefit of the stream management algorithms varies over different workloads. Thus, first, we propose a new framework, called Pattern I/O generator (PatIO), to capture the enterprise storage behavior that is prevailing across various user workloads, virtualization setup, file systems, and volume managers for the database server applications on flash-based storage. Second, using PatIO, we study what type of applications may be benefited by which stream assignment algorithm. Third, we design the framework to automatically tune the variable parameters of different stream identification algorithms of the multi-stream SSDs. Our evaluation shows 20 to 110 percent of the reward function increase, measuring the cumulative impact on application performance and SSD endurance. [ABSTRACT FROM AUTHOR]

The choice of radix is crucial for multivalued logic synthesis. Practical examples, however, reveal that it is not always possible to find the optimal radix when taking into consideration actual physical parameters of multivalued operations. In other words, each radix has its advantages and disadvantages. Our proposal is to synthesize logic in different radices, so it may benefit from their combination. The theory presented in this paper is based on Reed-Muller expansions over Galois field arithmetic. The work aims to first estimate the potential of the new approach and to second analyze its impact on circuit parameters down to the level of physical gates. The presented theory has been applied to real-life examples focusing on cryptographic circuits where Galois Fields find frequent application. The benchmark results show that the approach creates a new dimension for the trade-off between circuit parameters and provides information on how the implemented functions are related to different radices. [ABSTRACT FROM AUTHOR]

Voltage/Frequency Scaling (VFS) and Device Power Management (DPM) are two popular techniques commonly employed to save energy in real-time embedded systems. VFS policies aim at reducing the CPU energy, while DPM-based solutions involve putting the system components (e.g., memory or I/O devices) to low-power/sleep states at runtime, when sufficiently long idle intervals can be predicted. Despite numerous research papers that tackled the energy minimization problem using VFS or DPM separately, the interactions of these two popular techniques are not yet well understood. In this paper, we undertake an exact analysis of the problem for a real-time embedded application running on a VFS-enabled CPU and using multiple devices. Specifically, by adopting a generalized system-level energy model, we characterize the variations in different components of the system energy as a function of the CPU processing frequency. Then, we propose a provably optimal and efficient algorithm to determine the optimal CPU frequency as well as device state transition decisions to minimize the system-level energy. We also extend our solution to deal with workload variability. The experimental evaluations confirm that substantial energy savings can be obtained through our solution that combines VFS and DPM optimally under the given task and energy models. [ABSTRACT FROM AUTHOR]

Understanding the real performance of a proposed algorithm is a basic requirement for both algorithm designers and implementers. However, this is sometimes difficult to achieve. Each new algorithm published is evaluated from different perspectives and based on different assumptions. Without a common ground, it is almost impossible to compare different algorithms directly. Choosing an incompetent algorithm for an application can incur significant cost. This is especially true for packet classification in network routers, since packet classification is intrinsically a hard problem and all existing algorithms are based on some heuristics and filter set characteristics. The performance of the packet classification subsystem is critical to the overall performance of the network routers. Although numerous algorithms have been proposed so far, a benchmark that can give them consistent evaluation and reveal their comparable performance is still missing. This paper summarizes our efforts toward improving this situation. First, we conduct a high-level survey on the existing algorithms and extract some insights on the general design ideas. Second, we describe an open-source platform dedicated for advocacy-free evaluation of packet classification algorithms. Many representative algorithms are actually implemented under a set of uniform conditions and assumptions. The freely available implementations allow other researchers to easily test them under different scenarios. We also enforce some consistent and fundamental criteria for the algorithm evaluation, so that their performance and potentials are directly comparable, regardless of the actual implementation platforms. This project serves dual purpose: It helps the researchers to accelerate the innovation in the area of packet classification algorithm development by relieving them from the labor of replicating the previous work and by enabling them to quickly compare and evaluate algorithms. Meanwhile, it also helps the system implementers to easily choose the capable algorithm for their particular applications. Aiming to build an open-source library, we encourage external contributions of new algorithm implementations and evaluations under the same framework. We believe the practice will benefit the research and design community as a whole. [ABSTRACT FROM AUTHOR]

Determination of accurate estimates for the Worst-Case Execution Time of a program is essential for guaranteeing the correct temporal behavior of any Real-Time System. Of particular importance is tightly bounding the number of iterations of loops in the program or excessive undue pessimism can result. This paper presents a novel approach to determining the number of iterations of a loop for such analysis. Program traces are collected and analyzed allowing the number of loop executions to be parametrically determined safely and precisely under certain conditions. The approach is mathematically proved to be safe and its practicality is demonstrated on a series of benchmarks. [ABSTRACT FROM PUBLISHER]