Search

In the past years, quantum computers more and more have evolved from an academic idea to an upcoming reality. IBM’s project IBM ${Q}$ can be seen as evidence of this progress. Launched in March 2017 with the goal to provide access to quantum computers for a broad audience, this allowed users to conduct quantum experiments on a 5-qubit and, since June 2017, also on a 16-qubit quantum computer (called IBM QX2 and IBM QX3, respectively). Revised versions of these 5- and 16-qubit quantum computers (named IBM QX4 and IBM QX5, respectively) are available since September 2017. In order to use these, the desired quantum functionality (e.g., provided in terms of a quantum circuit) has to be properly mapped so that the underlying physical constraints are satisfied—a complex task. This demands solutions to automatically and efficiently conduct this mapping process. In this paper, we propose a methodology which addresses this problem, i.e., maps the given quantum functionality to a realization which satisfies all constraints given by the architecture and, at the same time, keeps the overhead in terms of additionally required quantum gates minimal. The proposed methodology is generic, can easily be configured for similar future architectures, and is fully integrated into IBM’s SDK. Experimental evaluations show that the proposed approach clearly outperforms IBM’s own mapping solution. In fact, for many quantum circuits, the proposed approach determines a mapping to the IBM architecture within minutes, while IBM’s solution suffers from long runtimes and runs into a timeout of 1 h in several cases. As an additional benefit, the proposed approach yields mapped circuits with smaller costs (i.e., fewer additional gates are required). All implementations of the proposed methodology are publicly available at http://iic.jku.at/eda/research/ibm_qx_mapping. [ABSTRACT FROM AUTHOR]

The design of cyber-physical systems (CPSs) faces various new challenges that are unheard of in the design of classical real-time systems. Power optimization is one of the major design goals that is witnessing such new challenges. The presence of interaction between the cyber and physical components of a CPS leads to dependence between the time delay of a computational task and the amount of workload in the next iteration. We demonstrate that it is essential to take this delay-workload dependence into consideration in order to achieve low power consumption. In this paper, we identify this new challenge, and present the first formal and comprehensive model to enable rigorous investigations on this topic. We propose a simple power management policy, and show that this policy achieves a best possible notion of optimality. In fact, we show that the optimal power consumption is attained in a “steady-state” operation and a simple policy of finding and entering this steady state suffices, which can be quite surprising considering the added complexity of this problem. Finally, we validated the efficiency of our policy with experiments. [ABSTRACT FROM AUTHOR]

An error-correcting code (ECC) immune to bit errors has been widely used in reliable computer systems. However, ECC techniques can make memory performance severely degraded since incomplete-word write requests lead to inefficient read-to-write (RTW) and write-to-read operations of synchronous dynamic random access memory. In this paper, we propose a memory subsystem efficient for ECC operations. Our key idea is that the RTW operations causing incomplete-word write requests are split and grouped into independent read and write operations, and then the grouped read and write operations are individually scheduled for the optimal memory performance under application constraints. Experimental results show that the proposed ECC-aware memory subsystem achieves 17% shorter memory latency, and 12% higher memory utilization, on average, than the latest conventional memory subsystems on industrial multimedia applications. Moreover, the ECC-aware memory subsystem improves up to 2.5 times higher memory performance on synthetic benchmarks. [ABSTRACT FROM AUTHOR]

In recent years, machine learning (ML) techniques are proven to be powerful tools in various emerging applications. Traditionally, ML techniques are processed on general-purpose CPUs and GPUs, but their energy efficiencies are limited due to their excessive support for flexibility. As an efficient alternative to CPUs/GPUs, hardware accelerators are still limited as they often accommodate only a single ML technique (family). However, different problems may require different ML techniques, which implies that such accelerators may achieve poor learning accuracy or even be ineffective. In this paper, we present a polyvalent accelerator architecture integrated with multiple processing cores, called ParaML, which accommodates ten representative ML techniques, including $k$ -means, $k$ -nearest neighbors ($k$ -NN), naive Bayes (NB), support vector machine (SVM), linear regression (LR), classification tree (CT), deep neural network (DNN), learning vector quantization (LVQ), parzen window (PW), and principal component analysis (PCA). Benefited from our thorough analysis on computational primitives and locality properties of different ML techniques, the single-core ParaML can perform up to 1056 GOP/s (e.g., additions and multiplications) in an area of 3.51 mm2 and consumes 596 mW only, estimated by ICC and PrimeTime PX with post-synthesis netlist, respectively. Compared with the NVIDIA K20M GPU (28-nm process), the single-core ParaML (65-nm process) is $1.21\times $ faster, and can reduce the energy by $137.93\times $. We also compare the single-core ParaML with other accelerators. Compared with PRINS, single-core ParaML achieves $72.09\times $ and $2.57\times $ energy benefit for $k$ -NN and $k$ -means, respectively, and speeds up each query in $k$ -NN by $44.76\times $. Compared with EIE, the single-core ParaML achieves $5.02\times $ speedup and $4.97\times $ energy benefit with $11.62\times $ less area when evaluating with dense DNN. Compared with TPU, the single-core ParaML achieves $2.45\times $ better power efficiency (5647 Gop/W versus 2300 Gop/W) with $321.36\times $ less area. Compared to the single-core version, the 8-core ParaML will further improve the speedup up to $3.98\times $ with an area of 13.44 mm2 and a power of 2036 mW. [ABSTRACT FROM AUTHOR]

In this paper, we propose novel algorithms for pattern matching which dissects patterns into rectangles based on polygon edges. Unlike other design rule check (DRC)-based pattern matching algorithms, our solution utilizes simple DRC edge length rules to create rectangles for hotspot pattern descriptions. This approach has at least three advantages over other solutions. First, it is faster than other state-of-the-art pattern matching tools. Second, it is intuitive and simple for pattern matching engineers to understand and describe patterns. Third, it scales well for parallel computation. We also show how to improve pattern matching run time using vector space created by an origin rectangle and other reference rectangles inside a pattern bounding box. By adopting the vector concept, we iterate only once or twice when detecting different pattern orientations. Other pattern matching techniques usually iterate eight times (4 rotations $ \times \,\, 2$ mirrored images) to detect all of the eight different orientations. Our method eliminates these unnecessary iterations. [ABSTRACT FROM PUBLISHER]

Microelectronic circuits exhibit increasing variations in performance, power consumption, and reliability parameters across the manufactured parts and across use of these parts over time in the field. These variations have led to increasing use of overdesign and guardbands in design and test to ensure yield and reliability with respect to a rigid set of datasheet specifications. This paper explores the possibility of constructing computing machines that purposely expose hardware variations to various layers of the system stack including software. This leads to the vision of underdesigned hardware that utilizes a software stack that opportunistically adapts to a sensed or modeled hardware. The envisioned underdesigned and opportunistic computing (UnO) machines face a number of challenges related to the sensing infrastructure and software interfaces that can effectively utilize the sensory data. In this paper, we outline specific sensing mechanisms that we have developed and their potential use in building UnO machines. [ABSTRACT FROM AUTHOR]

Three-dimensional integration has the potential to improve the communication latency and integration density of chip-level multiprocessors (CMPs). However, the stacked high-power density layers of 3-D CMPs increase the importance and difficulty of thermal management. In this paper, we investigate the 3-D CMP run-time thermal management problem and describe efficient management techniques. This paper makes the following main contributions: 1) It identifies and describes the critical concepts required for optimal thermal management, namely the methods by which heterogeneity in both workload power characteristics and processor core thermal characteristics should be exploited; and 2) it proposes an efficient proactive continuously engaged hardware and operating system thermal management technique governed by optimal thermal management polices. The proposed technique is evaluated using multiprogrammed and multithreaded benchmarks in an integrated power, performance, and temperature full-system simulation environment. We find that proactive power-thermal budgeting allows a 30% improvement in instruction throughput compared to a proactive thermal management approach that bases decisions only upon local information. The software components of the proposed thermal management technique have been implemented in the Linux 2.6.8 kernel. This source code will be publicly released. The analysis and technique developed in this paper provide a general solution for future 3-D and 2-D CMPs. [ABSTRACT FROM AUTHOR]

Adaptive body biasing is a powerful technique that allows post-silicon tuning of individual manufactured dies such that each die optimally meets the delay and power constraints. Assigning individual bias control to each gate leads to severe overhead, rendering the method impractical. However, assigning a single bias control to all gates in the circuit prevents the method from compensating for intra-die variation and greatly reduces its effectiveness. In this paper, we propose a new variability-aware method that clusters gates at design time into a handful of carefully chosen independent body-bias groups, which are then individually tuned post-silicon for each die. We show that this allows us to obtain near-optimal performance and power characteristics with minimal overhead. For each gate, we generate the probability distribution of its post-silicon ideal body bias voltage using an efficient sampling method. We then use these distributions and their correlations to drive a statistically aware clustering technique. We study the physical design constraints and show how the area and wirelength overhead can be significantly limited using the proposed method. Compared with a fixed design-time based dual threshold voltage assignment method, we improve leakage power by 38%-68% while simultaneously reducing the standard deviation of delay by two to nine times. [ABSTRACT FROM AUTHOR]

The complexity of many embedded software applications and their stringent performance requirements have reached a point where they can no longer be supported by conventional embedded-system architectures based on a single general-purpose processor. Nanometer fabrication technologies have made it feasible to integrate several embedded processors on a single chip to create multiprocessor systems-on-chip (MPSoCs) for a wide range of applications. It is already well known that, for embedded systems, customizing the processor to the application can significantly increase performance and energy efficiency. Single-chip heterogeneous multiprocessors, where the different processors are customized to the tasks they perform, are thus attracting attention. Despite their significant potential, a primary bottleneck to their adoption remains the development of programming paradigms and tools to alleviate the design complexity. Some advances have been made in the areas of custom multiprocessor architecture, tool support, and design methodology in order to reduce the design turnaround time. However, because of the heterogeneity of the custom processors, the designers are still required to manually map the application tasks to the different processors and, at the same time, customize each processor so that the overall performance requirements are satisfied. A multilevel custom multiprocessor-synthesis methodology to perform the assignment and scheduling of the application tasks on the various processors together with processor customization in an integrated manner is proposed. This paper focuses on extensible processors, which provide a good tradeoff between efficiency, flexibility, and design turnaround time, by combining a configurable base processor with hardware that implements custom instructions to extend its instruction set. This paper motivates the need for such an integrated approach by demonstrating that custom-instruction selection has complex interdependencies with task assignment and scheduling, and performing these steps independently often results in significant degradation in the quality of the synthesized multiprocessor architecture. The methodology presented here uses an iterative improvement algorithm to first assign and schedule tasks on processors and then select custom instructions along the critical path. It utilizes the concept of ‘expected execution time’ to connect these two steps. It not only considers the currently selected custom instructions for the current task assignment and schedule, but also the possibility of better custom instructions being selected in future iterations. The methodology presented here is also enhanced to integrate task-level software pipelining to further increase the parallelism in the task graph and provide opportunities for multiprocessing. In this paper, the proposed heterogeneous multiprocessor-synthesis methodology is implemented in the context of a commercial extensible-processor design flow, using the Xtensa platform from Tensilica Inc. The presented tool was evaluated by automatically generating custom multiprocessor architectures for several complex embedded software benchmarks. The results show that architectures synthesized by the proposed methodology demonstrate an average speedup of 2.0 × (up to 2.9 ×) compared to symmetric multiprocessor architectures in which the processors have not been augmented with custom instructions. To the best of the authors' knowledge, this is the first tool for the synthesis of custom MPSoCs using extensible processors. [ABSTRACT FROM AUTHOR]

This paper proposes an approach to optimally synthesize quantum circuits by symbolic reachability analysis, where the primary inputs and outputs are basis binary and the internal signals can be nonbinary in a multiple-valued domain. The authors present an optimal synthesis method to minimize quantum cost and some speedup methods with nonoptimal quantum cost. The methods here are applicable to small reversible functions. Unlike previous works that use permutative reversible gates, a lower level library that includes nonpermutative quantum gates is used here. The proposed approach obtains the minimum cost quantum circuits for Miller gate, half adder, and full adder, which are better than previous results. This cost is minimum for any circuit using the set of quantum gates in this paper, where the control qubit of 2-qubit gates is always basis binary. In addition, the minimum quantum cost in the same manner for Fredkin, Peres, and Toffoli gates is proven. The method can also find the best conversion from an irreversible function to a reversible circuit as a byproduct of the generality of its formulation, thus synthesizing in principle arbitrary multi-output Boolean functions with quantum gate library. This paper constitutes the first successful experience of applying formal methods and satisfiability to quantum logic synthesis. [ABSTRACT FROM AUTHOR]

Due to the critical role played by data memory subsystems in the performance and energy efficiency of embedded systems, the design of energy-efficient data memory architectures has received considerable attention in recent years. In this paper, we propose a novel special-purpose data memory subsystem called Xtreain-Fit which is aimed at achieving high energy-delay efficiency for streaming media applications. A key novelty of Xtream-Fit is that it exposes a single customization parameter, thus enabling a very simple and yet effective design space exploration methodology. A second key contribution of this paper is the ability to achieve very high energy-delay efficiency through a synergistic combination of: 1) special purpose memory subsystem components, namely, a streaming memory and a scratch-pad memory and (2) a novel task-based execution model that exposes/enhances opportunities for efficient prefetching, and aggressive dynamic energy conservation techniques targeting on-chip and off-chip memory components. Extensive experimental results show that Xtream-Fit reduces the energy-delay product by 22% to 61%, as compared to general-purpose memory sub- systems enhanced with state of the art cache decay and SDRAM power-mode control policies. [ABSTRACT FROM AUTHOR]

This paper examines the controversy between two approaches to inductance extraction: loop versus partial treatments for integrated circuit applications. We advocate the first one, and explicitly show that the alternative demands monopole-like magnetic configurations as well as dense inductance matrices. We argue that the uncertainties in the loop inductance treatment associated with possibly unknown return paths are in fact negligible for frequencies where inductance effects are important. Within the loop formulation, we develop an efficient way of computing mutual inductances between loops in terms of the field generated by a magnetic dipole. We derive easily computable analytical formulas. On numerical simulations, this dipole approximation (DA) shows good accuracy when compared to FastHenry, down to distances smaller than 30 μm for 90-nm lithography. The DA leads naturally to selection rules for discarding the coupling for certain geometrical configurations, an experimentally verifiable prediction. [ABSTRACT FROM AUTHOR]

This paper introduces a new class of finite memory compaction schemes called convolutional compactors (CCs). They provide compaction ratios of test responses in excess of 100 ×, even for a very small number of outputs. This is combined with the capability to detect multiple errors, handling of unknown states, and the ability to diagnose failing scan cells directly from compacted responses. The CCs can also be used to significantly enhance conventional multiple input signature registers. Experimental results presented in the paper demonstrate the efficiency of convolutional compaction for several industrial circuits. [ABSTRACT FROM AUTHOR]

This paper introduces a technique to derive a word-level abstraction of the function implemented by a combinational logic circuit. The abstraction provides a canonical representation of the function as a polynomial Z = \mathcal F(A) over the finite field $ {{\mathbb {F}}_{2^{k}}} , where Z and A represent the k -bit output and input bit-vectors (words) of the circuit, respectively. This canonical abstraction can be utilized for formal verification and equivalence checking of combinational circuits. Our approach to abstraction is based upon concepts from computational commutative algebra and algebraic geometry. We show that the abstraction Z = \mathcal F(A) can be derived by computing a Gröbner basis of the polynomials corresponding to the circuit, using a specific elimination term order derived from the circuit’s topology. Computing Gröbner bases using elimination term orders is infeasible for large circuits. To overcome this limitation, we describe an efficient symbolic computation to derive the word-level polynomial. Our algorithms exploit: 1) the structure of the circuit; 2) the properties of Gröbner bases; 3) characteristics of finite fields $ {{\mathbb {F}}_{2^{k}}}$ ; and 4) modern algorithms from symbolic algebra, to derive the canonical polynomial representation. This approach is employed to verify (and detect bugs in) large combinational finite field arithmetic circuits, where contemporary verification techniques are known to be infeasible. [ABSTRACT FROM PUBLISHER]

Quantum mechanical phenomena such as phase shifts, superposition, and entanglement show promise in use for computation. Suitable technologies for the modeling and design of quantum computers and other information processing techniques that exploit quantum mechanical principles are in the range of vision. Quantum algorithms that significantly speed up the process of solving several important computation problems have been proposed in the past. The most common representation of quantum mechanical phenomena are transformation matrices. However, the transformation matrices grow exponentially with the size of a quantum system and, thus, pose significant challenges for efficient representation and manipulation of quantum functionality. In order to address this problem, first approaches for the representation of quantum systems in terms of decision diagrams have been proposed. One very promising approach is given by Quantum Multiple-Valued Decision Diagrams (QMDDs) which are able to efficiently represent transformation matrices and also inherently support multiple-valued basis states offered by many physical quantum systems. However, the initial proposal of QMDDs was lacking in a formal basis and did not allow, e.g., the change of the variable order—an established core functionality in decision diagrams which is crucial for determining more compact representations. Because of this, the full potential of QMDDs or decision diagrams for quantum functionality in general has not been fully exploited yet. In this paper, we present a refined definition of QMDDs for the general quantum case. Furthermore, we provide significantly improved computational methods for their use and manipulation and show that the resulting representation satisfies important criteria for a decision diagram, i.e., compactness and canonicity. An experimental evaluation confirms the efficiency of QMDDs. [ABSTRACT FROM PUBLISHER]

The memory system presents one of the critical challenges in embedded system design and optimization. This is mainly due to the ever-increasing code complexity of embedded applications and the exponential increase seen in the amount of data they manipulate. The memory bottleneck is even more important for multiprocessor-system-on-a-chip (MPSoC) architectures due to the high cost of off-chip memory accesses in terms of both energy and performance. As a result, reducing the memory-space occupancy of embedded applications is very important and will be even more important in the next decade. While it is true that the on-chip memory capacity of embedded systems is continuously increasing, the increases in the complexity of embedded applications and the sizes of the data sets they process are far greater. Motivated by this observation, this paper presents and evaluates a compiler-driven approach to data compression for reducing memory-space occupancy. Our goal is to study how automated compiler support can help in deciding the set of data elements to compress/decompress and the points during execution at which these compressions/decompressions should be performed. We first study this problem in the context of single-core systems and then extend it to MPSoCs where we schedule compressions and decompressions intelligently such that they do not conflict with application execution as much as possible. Particularly, in MPSoCs, one needs to decide which processors should participate in the compression and decompression activities at any given point during the course of execution. We propose both static and dynamic algorithms for this purpose. In the static scheme, the processors are divided into two groups: those performing compression/decompression and those executing the application, and this grouping is maintained throughout the execution of the application. In the dynamic scheme, on the other hand, the execution starts with some grouping but this grouping can change during the course of execution, depending on the dynamic variations in the data access pattern. Our experimental results show that, in a single-core system, the proposed approach reduces maximum memory occupancy by 47.9% and average memory occupancy by 48.3% when averaged over all the benchmarks. Our results also indicate that, in an MPSoC, the average energy saving is 12.7% when all eight benchmarks are considered. While compressions and decompressions and related bookkeeping activities take extra cycles and memory space and consume additional energy, we found that the improvements they bring from the memory space, execution cycles, and energy perspectives are much higher than these overheads. [ABSTRACT FROM AUTHOR]

Synthesis of reversible logic has become a very important research area in recent years. Applications can be found in the domain of low-power design, optical computing, and quantum computing. In the past, several approaches have been introduced that synthesize reversible networks with respect to a given function. Most of these methods only approximate a minimal network representation. In this paper, exact algorithms for the synthesis of multiple-control Toffoli networks are presented, i.e., algorithms that guarantee to find a network with the minimal number of gates. Our iterative algorithms formulate the synthesis problem as a sequence of decision problems. The decision problems are encoded as Boolean satisfiability (SAT) or SAT modulo theory (SMT) instances, respectively. As soon as one of these instances becomes satisfiable, a Toffoli network representation for the given function has been found. We show that choosing the encoding for synthesis is crucial for the resulting runtimes. Furthermore, we discuss the principal limits of the SAT and SMT approaches. To overcome these limits, we propose a method using problem-specific knowledge during synthesis. In addition, better embeddings to make irreversible functions reversible are considered. For the resulting synthesis problems, an improvement is presented that reduces the overall runtime by automatically setting the constant inputs to their optimal values. Experimental results on a large set of benchmarks demonstrate the differences between three exact synthesis algorithms. In addition, a comparison with the best-known heuristic results is provided. In summary, the results show that, for some benchmarks, the heuristic approaches have already found the minimal network, while for other benchmarks, significantly smaller networks exist. [ABSTRACT FROM AUTHOR]

Recent field-programmable gate array (FPGA) architectures are heterogeneous, owing to the presence of millions of gates in configurable logic blocks (CLBs), block RAMs, and multiplier blocks (MULs) which can host fairly large designs. While their physical design calls for floorplanning, the traditional algorithms for application-specific integrated circuits (ASIC) do not suffice. In this paper, we propose a three-phase algorithm for unified floorplan-topology generation and sizing on heterogeneous FPGAs. The method consists of a recursive balanced bipartitioning followed by the generation of slicing topologies and finally the allocation of CLBs and RAM/MULs to modules by a greedy heuristic and minimum-cost maximum-flow method, respectively. Experimental results on benchmark circuits show that our method HeteroFloorplan produces feasible floorplans within a few seconds with total half-perimeter wirelength (HPWL) improvement of 18%-52% over the very few previous approaches. We also compare our locally greedy CLB allocation with a network-flow formulation to establish its effectiveness. [ABSTRACT FROM AUTHOR]

Exploiting runtime memory access traces can be a complementary approach to compiler optimizations for the energy reduction in memory hierarchy. This is particularly important for emerging multimedia applications since they usually have input-sensitive runtime behavior which results in dynamic and/or irregular memory access patterns. These types of applications are normally hard to optimize by static compiler optimizations. The reason is that their behavior stays unknown until runtime and may even change during computation. To tackle this problem, we propose an integrated approach of software [compiler and operating system (OS)] and hardware (data access record table) techniques to exploit data reusability of multimedia applications in Multiprocessor Systems on Chip. Guided by compiler analysis for generating scratch pad data layouts and hardware components for tracking dynamic memory accesses, the scratch pad data layout adapts to an input data pattern with the help of a run-time scratch pad memory manager incorporated in the OS. The runtime data placement strategy presented in this paper provides efficient scratch pad utilization for the dynamic applications. The goal is to minimize the amount of accesses to the main memory over the entire runtime of the system, which leads to a reduction in the energy consumption of the system. Our experimental results show that our approach is able to significantly improve the energy consumption of multimedia applications with dynamic memory access behavior over an existing compiler technique and an alternative hardware technique. [ABSTRACT FROM AUTHOR]

Embedded systems are constrained by the available memory. Code-compression techniques address this issue by reducing the code size of application programs. It is a major challenge to develop an efficient code-compression technique that can generate substantial reduction in code size without affecting the overall system performance. We present a novel code-compression technique using bitmasks, which significantly improves the compression efficiency without introducing any decompression penalty. This paper makes three important contributions. 1) It develops an efficient bitmask-selection technique that can create a large set of matching patterns. 2) It develops an efficient dictionary-selection technique based on bitmasks. 3) It proposes a dictionary-based code-compression algorithm using the bitmask-and dictionary-selection techniques that can significantly reduce the memory requirement. To demonstrate the usefulness of our approach, we have performed code compression using applications from various domains and compiled for a wide variety of architectures. Our approach outperforms the existing dictionary-based techniques by an average of 20%, giving a compression ratio of 55%-65%. [ABSTRACT FROM AUTHOR]

A newly developed method is introduced in this paper to efficiently model frequency-dependent on-die pad capacitance and conductance, which can be easily integrated in computer-aided-design tools. An equivalent lumped circuit is used to model the pad parasitic effect. Three critical frequencies are defined to characterize the pad-frequency characteristics based on this model. A relationship between normalized pad capacitance and normalized frequency is then established to guide practical pad designs. Three different methods are compared to determine the parameters in the equivalent lumped circuit. Our newly developed quasi-static method gives the best agreement with full-wave simulation. In this method, each capacitance in the model is divided into the parallel-plate part and the fringing part. The pad is innovatively treated as transmission lines several times, and a closed-form formula is used to extract the per-unit-length (p.u.l.) capacitance for these transmission lines. The fringing capacitances are then calculated from these p.u.l. capacitances. The substrate conductance can be determined from the substrate capacitance. Simulation results based on our model show good agreement with full-wave simulation results, which justify the validity of our modeling. Such a method with fast computation and good accuracy is very helpful in the early integrated circuit design stage. [ABSTRACT FROM AUTHOR]

This paper presents a set of comprehensive techniques for the intratask voltage-scheduling problem to reduce energy consumption in hard real-time tasks of embedded systems. Based on the execution profile of the task, a voltage-scheduling technique that optimally determines the operating voltages to individual basic blocks in the task is proposed. The obtained voltage schedule guarantees minimum average energy consumption. The proposed technique is then extended to solve practical issues regarding transition overheads, which are totally or partially ignored in the existing approaches. Finally, a technique involving a novel extension of our optimal scheduler is proposed to solve the scheduling problem in a discretely variable voltage environment. We also present a novel voltage set-up technique to determine each voltage level for customizable systems-on-chips (SoCs) with discretely variable voltages. In summary, it is con- firmed from experiments that the proposed optimal scheduling technique reduces energy consumption by 20.2% over that of one of the state-of-the-art schedulers (Shin and Kim, 2001) and, further, the extended technique in a discrete-voltage environment reduces energy consumption by 45.3% on average. [ABSTRACT FROM AUTHOR]

Nonuniform thermal profiles on the substrate in high-performance ICs can significantly impact the performance of global on-chip interconnects. This paper presents a detailed modeling and analysis of the interconnect performance degradation due to the nonuniform temperature profiles that are encountered along long metal interconnects as a result of existing thermal gradients in the underlying Silicon substrate. A nonuniform temperature dependent distributed RC interconnect delay model is proposed. The model is applied to a wide variety of interconnect layouts and substrate temperature distributions to quantify the impact of such thermal nonuniformities on signal integrity issues including speed degradation in global interconnect lines and skew fluctuations in clock signal distribution networks. Subsequently, a new thermally dependent zero-skew clock-routing methodology is presented. This study suggests that thermally aware analysis should become an integrated part of the various optimization steps in physical-synthesis flow to improve the performance and integrity of signals in global ultra large scale integration interconnects. [ABSTRACT FROM AUTHOR]

Net weighting is a key technique in timing-driven placement (TDP), which plays a crucial role for deep submiron very large scale integration of physical synthesis and timing closure. A popular way to assign net weight is based on its slack, such that the worst negative slack (WNS) of the entire circuit may be minimized. While WNS is an important optimization metric, another figure of merit (FOM), defined as the total slack difference compared to a certain slack threshold for all timing end points, is of equal importance to measure the overall timing closure result for highly complex modern application specific integrated circuits and microprocessor designs. Moreover, to optimally assign net weight for timing closure, the effect of net weighting on timing should be carefully studied. In this paper, we perform a comprehensive analysis of the wirelength, slack, and FOM sensitivities to the net weight, and propose a new net weighting scheme based on those sensitivities. Such sensitivity analysis implicitly takes potential physical synthesis effect into consideration. The experiments on a set of industrial circuits show promising results for both stand-alone TIM' and physical synthesis afterwards. [ABSTRACT FROM AUTHOR]

In this paper, we present a methodology for the design of high-performance system-on-chip communication architectures. The approach is based on the addition of a layer of circuitry called the communication architecture tuner (CAT) layer around an existing communication architecture topology. The added layer provides a system with the capability of adapting to runtime variability in the communication needs of its constituent components. For example, more critical data may be handled differently, leading to lower communication latencies. The CAT associated with each component monitors its internal state, analyzes the communication transactions it generates, and "predicts" the relative importance of the transactions in terms of their impact on system-level performance metrics. It then configures the protocol parameters of the underlying communication architecture (e.g., priorities, burst modes, etc.) to best suit the system's changing communication needs. We illustrate the issues and tradeoffs involved in the design of CAT-based communication architectures, and present algorithms that automate the key steps. Experiments with example systems indicate that performance metrics (e.g., number of missed deadlines, average processing time) for systems with CAT-based communication architectures are significantly (sometimes over an order of magnitude) better than those with conventional communication architectures. [ABSTRACT FROM AUTHOR]

In this paper, we aim to improve the performance and power metrics of packet-switched network-on-chips (NoCs) and benefits from the scalability and resource utilization advantages of NoCs and superior communication performance of point-to-point dedicated links. The proposed method sets up the virtual point-to-point (VIP) connections over one virtual channel which bypasses the entire router pipeline) at each physical channel of the NoC. We present two schemes for constructing such VIP circuits. In the first scheme, the circuits are constructed for an application based on its task-graph at design time. The second scheme addresses constructing the connections at runtime using a light-weight setup network. It involves monitoring the NoC traffic in order to detect heavy communication flows and setting up a VIP connection for them using a run-time circuit construction mechanism. The proposed mechanism is compared to a traditional packet-switched NoC and some modern switching mechanisms and the results show a significant reduction in the network power and latency over the other considered NoCs. [ABSTRACT FROM AUTHOR]

While application-specific instruction-set processors (ASIPs) have allowed designers to create processors with custom instructions to target specific applications, floating-point (FP) units (FPUs) are still instantiated as noncustomizable general-purpose units, which, if underutilized, wastes area and performance. Therefore, there is a need for custom FPUs for embedded systems. To create a custom FPU, the subset of FP instructions that should be implemented in hardware has to be determined. Implementing more instructions in hardware reduces the cycle count of the application but may lead to increased latency if the critical delay of the FPU increases. Therefore, a balance between the hardware-implemented and the software-emulated instructions, which produces the best performance, must be found. In order to find this balance, a rapid design space exploration was performed to explore the tradeoffs between the area and the performance. In order to reduce the area of the custom FPU, it is desirable to merge the datapaths for each of the FP operations so that redundant hardware is minimized. However, FP datapaths are complex and contain components with varying bit widths; hence, sharing components of different bit widths is necessary. This introduces the problem of bit alignment, which involves determining how smaller resources should be aligned within larger resources when merged. A novel algorithm for solving the bit-alignment problem during datapath merging was developed. Our results show that adding more FP hardware does not necessarily equate to lower runtime if the delays associated with the additional hardware overcomes the cycle count reductions. We found that, with the Mediabench applications, datapath merging with bit alignment reduced area by an average of 22.5%, compared with an average of 14.1% without bit alignment. [ABSTRACT FROM AUTHOR]

Register bypassing is a popular and powerful architectural feature to improve processor performance in pipelined processors by eliminating certain data hazards. However, extensive bypassing comes with a significant impact on cycle time, area, and power consumption of the processor. Recent research therefore advocates the use of partial bypassing in a processor. However, accurate performance evaluation of partially bypassed processors is still a challenge, primarily due to the lack of bypass-sensitive retargetable compilation techniques. No existing partial bypass exploration framework estimates the power and area overhead of partial bypassing. As a result, the designers end up making suboptimal design decisions during the exploration of partial bypass design space. This paper presents PBExplore—an automatic design-space-exploration framework for register bypasses. PBExplore accurately evaluates the performance of a partially by- passed processor using a bypass-sensitive compilation technique. It synthesizes the bypass control logic and estimates the area and energy overhead of each bypass configuration. PBExplore is thus able to effectively perform multidimensional exploration of the partial bypass design space. We present experimental results of benchmarks from the MiBench suite on the Intel XScale architecture on and demonstrate the need, utility, and exploration capabilities of PBExplore. [ABSTRACT FROM AUTHOR]

Memory and communication architectures have a significant impact on the cost, performance, and time-to-market of complex multiprocessor system-on-chip (MPSoC) designs. The memory architecture dictates most of the data traffic flow in a design, which in turn influences the design of the communication architecture. Thus, there is a need to cosynthesize the memory and communication architectures to avoid making suboptimal design decisions. This is in contrast to traditional platform-based design approaches where memory and communication architectures are synthesized separately. In this paper, the authors propose an automated application-specific cosynthesis framework for memory and communication architecture (COSMECA) in MPSoC designs. The primary objective is to design a communication architecture having the least number of buses, which satisfies performance and memory-area constraints, while the secondary objective is to reduce the memory-area cost. Results of applying COSMECA to several industrial strength MPSoC applications from the networking domain indicate a saving of as much as 40% in number of buses and 29% in memory area compared to the traditional approach. [ABSTRACT FROM AUTHOR]

This paper investigates an integrated approach for achieving fault tolerance and energy savings in real-time embedded systems. Fault tolerance is achieved via checkpointing, and energy is saved using dynamic voltage scaling (DVS). The authors present a feasibility analysis for checkpointing schemes for a constant processor speed as well as for variable processor speeds. DVS is then carried out on the basis of the feasibility analysis. The authors incorporate important practical issues such as faults during checkpointing, rollback recovery time, memory access time, and energy needed for checkpointing, as well as DVS and context switching overhead. Numerical results based on real-life checkpointing data and processor data sheets show that compared to fault-oblivious methods, the proposed approach significantly reduces power consumption and guarantees timely task completion in the presence of faults. [ABSTRACT FROM AUTHOR]

Microprocessor datapath architectures operate on signed numbers usually represented in two's-complement or sign-magnitude formats. The multiplication operation is performed by optimized array multipliers of various architectures which are often produced by automatic module generators. Array multipliers have either a standard, nonrecoded signed (or tin- signed) architecture or a recoded (modified Booth's algorithm) architecture. High-quality testing of array multipliers based on a comprehensive sequential fault model and not affecting their well -optimized structure has not been proposed in the past. In this paper, we present a built-in self-testing (BIST) architecture for signed and unsigned array multipliers with respect to a comprehensive sequential fault model. The BIST architecture does not alter the well-optimized multiplier structure. The proposed test sets can be applied externally but their regular nature makes them very suitable for embedded, self-test application by simple specialized hardware which imposes small overheads. Two different implementations of the BIST architecture are proposed. The first implementation focuses on the test invalidation problem and targets robust sequential fault testing, while the second one focuses on test cost reduction (test time and hardware overhead). [ABSTRACT FROM AUTHOR]

The scope of the Formal System Design (ForSyDe) methodology is high-level modeling and refinement of systems-on-a-chip and embedded systems. Starting with a formal specification model, that captures the functionality of the system at a high abstraction level, it provides formal design-transformation methods for a transparent refinement process of the system model into an implementation model that is optimized for synthesis. The main contribution of this paper is the ForSyDe modeling technique and the formal treatment of transformational design refinement We introduce process constructors, that cleanly separate the computation part of a process from the synchronization and communication part. We develop the characteristic function for each process type and use it to define semantic preserving and design decision transformations. These transformations are characterized by name, the format of the original process network, the transformed process network, and a design implication. The implication expresses the relation between original and transformed process network by means of the characteristic function. The objective of the refinement process is a model that can be implemented cost efficiently. To this end, process constructors and processes have a hardware and software interpretation which shall facilitate accurate performance and cost estimations. In a study of a digital equalizer example, we illustrate the modeling and refinement process and focus in particular on refinement of the clock domain, communication refinement, and resource sharing. [ABSTRACT FROM AUTHOR]

Testing for delay faults in heavily gated clock designs has the major test challenges of reduced fault coverage and high test power consumption. In the scan-test method, gated clocks are often simplified and replaced with global test clocks. As such, partial clocking by the gated clocks is not inherited in test operations. Global clocking suffers from delay fault coverage loss because a sensitization state cannot easily be created due to the increased state dependence in functional paths, as compared to partial clocking. The global clocking scheme in the test mode is not adequate for low-power designs either, because the power consumed during a test operation exceeds that used during a normal operation. The power grid may not be sufficient to support the power drawn during testing, perhaps resulting in overkilled devices. It is therefore critical that power consumption be maintained under a safe limit, even during testing. In the proposed method, partial clocking in gated designs is preserved to the maximum possible to create more reachable states, thereby increasing transition fault coverage and reducing test power during launch and capture cycles. A transition fault simulator was developed, and it demonstrated higher transition' fault coverage and reduced test power for ISCAS-89 circuits when partial clocking is used. [ABSTRACT FROM AUTHOR]

As MPSoC has become an effective solution to ever-increasing design complexity of modern embedded systems, fast and accurate cosimulation of such systems is becoming a tough challenge. Cosimulation performance is in inverse proportion to the number of processor simulators in conventional cosimulation frameworks with lock-step synchronization schemes. To overcome this problem, we propose a novel time synchronization technique called trace-driven virtual synchronization. Having separate phases of event generation and event alignment in the cosimulation, time synchronization overhead is reduced to almost zero, boosting cosimulation speed while accuracy is almost preserved. In addition, this technique enables (1) a fast mixed level cosimulation where different abstraction level simulators are easily integrated communicating with traces and (2) a distributed parallel cosimulation where each simulator can run at its full speed without synchronizing with other simulator too frequently. We compared the performance and the accuracy with MaxSim, a well-known commercial SystemC simulation framework, and the proposed framework showed 11 times faster performance for H.263 decoder example, while the error was below 5%. [ABSTRACT FROM AUTHOR]

In the not-so-distant future, quantum computing will change the way we tackle certain problems. It promises to dramatically speed-up many chemical, financial, cryptographical, and machine-learning applications. However, in order to capitalize on those promises, complex design flows composed of steps, such as compilation, decomposition, mapping, or transpilation need to be employed before being able to execute a conceptual quantum algorithm on an actual device. This results in many descriptions at various levels of abstraction which may significantly differ from each other. The complexity of the underlying design problems makes it ever more important to not only provide efficient solutions for the single steps but also to verify that the originally intended functionality is preserved throughout all levels of abstraction. This motivates methods for equivalence checking of quantum circuits. However, most existing methods for this are inspired by equivalence checking in the classical realm and have merely been extended to support quantum circuits (i.e., circuits which do not only rely on 0’s and 1’s but also employ superposition and entanglement). In this work, we propose an advanced methodology that takes the different paradigms of quantum circuits not only as a burden but as an opportunity. In fact, the proposed methodology explicitly utilizes characteristics unique to quantum computing in order to overcome the shortcomings of existing approaches. We show that by exploiting the reversibility of quantum circuits, complexity can be kept feasible in many cases. Moreover, we show that, in contrast to the classical realm, simulation is very powerful in verifying quantum circuits. Experimental evaluations confirm that the resulting methodology allows one to conduct equivalence checking dramatically faster than ever before—in many cases just a single simulation run is sufficient. An implementation of the proposed equivalence checking flow is publicly available at https://iic.jku.at/eda/research/quantum_verification/. [ABSTRACT FROM AUTHOR]

Noisy intermediate scale quantum (NISQ) computers are becoming a reality thanks to the recent advances made by researchers who physically build such systems. In order to execute corresponding quantum algorithms (usually provided in terms of quantum circuits), certain physical constraints in the architectures need to be satisfied. More precisely, physical constraints restrict the possible interactions between qubits which frequently result in cases where qubits which are supposed to interact in a quantum circuit are not allowed to interact on the physical device. Thus far, this is addressed by dedicated methods that map the logical quantum circuit to a physical realization and satisfy the constraints by inserting further operations. This leads to additional costs which harm the fidelity of the circuit and, hence, urgently need to be avoided. Unfortunately, current state-of-the-art approaches for this mapping process take the existing architectures as invariant and only try to reduce the number of additionally needed operations. In contrast, (slight) changes in the, respectively, given architectures (which still keep the underlying physical constraints satisfied) might be possible and may allow for even better (i.e., less costly) mappings. But this potential has not been investigated yet. In this work, we explore this potential. More precisely, we introduce several schemes for generating alternative coupling graphs (and, by this, quantum computing architectures) that still might be able to satisfy physical constraints but, at the same time, allow for a more efficient realization of the desired quantum functionality. Evaluations confirm the potential of those alternative coupling graphs and demonstrate that they can reduce the mapping overhead by up to 60% in the best case and up to almost 40% on average. [ABSTRACT FROM AUTHOR]

The binary information technology reaches its limits set by the atomic size miniaturization, by calculation speed and by the fundamental principle of energy dissipation per bit processing. Employing multiple-valued logic (MVL) cells as computing and memory units reduces energy losses and enables to pack of unprecedented high-density information, but the current silicon-based material technologies have been studied marginally for the material realization of MVL devices. Here, we propose to use the ferroelectrics for the implementation of MVL units using their ability to pin the polarization as a sequence of multistable states. More specifically, the realization of a programmable logic array (PLA) based on MVL units is considered with the application of the ferroelectrics technology in implementation of memory units. The specific of the PLA construction is the use of generalized Reed-Muller expression for the representation of an MVL function. In this article, several possible implementations of such PLAs are considered, and their properties are analyzed from the logic design point of view. [ABSTRACT FROM AUTHOR]

Quantum computers are becoming a reality today due to the rapid progress made by researchers in the last years. In the process of building quantum computers, IBM has developed several versions—starting from 5-qubit architectures like IBM QX2 and IBM QX4 to larger 16- or 20-qubit architectures. These architectures support arbitrary rotations of a single qubit and a controlled negation (CNOT) involving two qubits. The two qubit operations come with added coupling-map restrictions that only allow specific physical qubits to be the control and target qubits of the operation. In order to execute a quantum circuit on the IBM QX architecture, CNOT gates must satisfy the so-called coupling constraints of the architecture. Previous works addressed this issue with the objective of reducing the number of gates and the circuit depth. However, in this article, we show that further improvements are possible. To this end, we present a general approach for further improving the number of gate operations and depth of the mapped circuit. The proposed approach encompasses the selection of physical qubits, determining initial and local permutations efficiently to obtain the final circuit mapped to the given IBM QX architecture. Through experiments, improvements are observed over existing methods in terms of the number of gates and circuit depth. [ABSTRACT FROM AUTHOR]

This article presents a survey of the different modern high-level synthesis (HLS) design space exploration (DSE) techniques that have been proposed so far to automatically generate hardware accelerators of different tradeoffs. HLS has multiple advantages compared to traditional RT-level-based hardware design. One key advantage is that a variety of different microarchitectures of unique tradeoffs can be obtained from the same untimed behavioral description by setting different synthesis options. Out of all the possible microarchitectures, the one that the designers are most interested in are the Pareto-optimal ones. The main problem is that the search space grows superlinearly with the number of synthesis options, and hence, heuristics have been proposed to search the space efficiently. This article summarizes the main techniques proposed and addresses the critical issues still not resolved as well identifies new opportunities in this field. It also serves as a guide for anyone wanting to create their own HLS DSE. [ABSTRACT FROM AUTHOR]

We present a synthesis framework to map logic networks into quantum circuits for quantum computing. The synthesis framework is based on lookup-table (LUT) networks, which play a key role in conventional logic synthesis. Establishing a connection between LUTs in an LUT network and reversible single-target gates in a reversible network allows us to bridge conventional logic synthesis with logic synthesis for quantum computing, despite several fundamental differences. We call our synthesis framework LUT-based hierarchical reversible logic synthesis (LHRS). Input to LHRS is a classical logic network representing an arbitrary Boolean combinational operation; output is a quantum network (realized in terms of Clifford+T gates). The framework allows one to account for qubit count requirements imposed by the overlying quantum algorithm or target quantum computing hardware. In a fast first step, an initial network is derived that only consists of single-target gates and already completely determines the number of qubits in the final quantum network. Different methods are then used to map each single-target gate into Clifford+T gates, while aiming at optimally using available resources. We demonstrate the versatility of our method by conducting a design space exploration using different parameters on a set of large combinational benchmarks. On the same benchmarks, we show that our approach can advance over the state-of-the-art hierarchical reversible logic synthesis algorithms. [ABSTRACT FROM AUTHOR]

Embedded cryptographic devices are vulnerable to power analysis attacks. Threshold implementations (TIs) provide provable security against first-order power analysis attacks for hardware and software implementations. Like masking, the approach relies on secret sharing but it differs in the implementation of logic functions. While masking can fail to provide protection due to glitches in the circuit, TIs rely on few assumptions about the hardware and are fully compatible with standard design flows. We investigate two important properties of TIs in detail and point out interesting trade-offs between circuit area and randomness requirements. We propose two new TIs of AES that, starting from a common previously published implementation, illustrate possible trade-offs. We provide concrete ASIC implementation results for all three designs using the same library, and we evaluate the practical security of all three designs on the same FPGA platform. Our analysis allow us to directly compare the security provided by the different trade-offs, and to quantify the associated hardware cost. [ABSTRACT FROM PUBLISHER]

Outsourcing computation to the cloud has recently become a very attractive option for enterprises and consumers, due to mostly reduced cost and extensive scalability. At the same time, however, concerns about the privacy of the data entrusted to cloud providers keeps rising. To address these concerns and thwart potential attackers, cloud providers today resort to numerous security controls as well as data encryption. Since the actual computation is still unencrypted inside cloud microprocessor chips, it is only a matter of time until new attacks and side channels are devised to leak sensitive information. To address the challenge of securing general-purpose computation inside microprocessor chips, we propose a novel computer architecture, and present a complete framework for general-purpose encrypted computation without shared keys, enabling secure data processing. This new architecture, called homomophically encrypted one instruction computation, contrary to the previous work in the area does not require a secret key installed inside the microprocessor chip. Instead, it leverages the powerful properties of homomorphic encryption combined with the simplicity of one instruction set computing. The proposed framework introduces: 1) a RTL implementation for reconfigurable hardware and 2) a ready-to-deploy virtual machine, which can be readily ported to existing server processor architectures. [ABSTRACT FROM PUBLISHER]

Level-sensitive latches are widely used in high-performance custom designs while edge-triggered flip-flops are predominantly used in application-specific integrated circuits. We consider a latch as a basis for storage and address each step of high-level synthesis (HLS), including scheduling, allocation, and control synthesis. While the use of latches provides an opportunity to reduce the latency during the scheduling, the register allocation has to take extra conflicts caused by latch into account, and the control synthesis has to be tailored to support the latch-based data-path. Optimization potentials specific to this HLS are identified and solutions are proposed. Specifically, the register allocation can be improved by refining the operation schedule in a way to reduce the number of edges in a register conflict graph; the latency can be reduced by adjusting the clock duty cycle in a way to generate a tighter schedule. All the steps of HLS and optimization procedures were integrated into a framework called HLS-l. It was tested on benchmark designs implemented in 1.1-V, 45 nm complementary metal-oxide-semiconductor technology. Compared to the conventional HLS, HLS-l was able to reduce the latency by 18.2% on average with 9.2% less area and 16.0% less power consumption. The application of HLS-l to an industrial example is demonstrated through the design of a module extracted from H.264/advanced video coding. [ABSTRACT FROM AUTHOR]

We present a methodology for power reduction by instruction/data cache-tag compression for low-power embedded processors. By statically analyzing the code/data memory layouts for the application hot spots, a variety of proposed schemes for effective tag-size reduction can be employed for power minimization in instruction and data caches. The schemes rely on significantly reducing the number of tag bits stored in the tag arrays for cache-conflict identification, thus considerably decreasing the number of active bitlines, sense amps, and comparator cells. We present a set of tag compression techniques and evaluate each of them separately in terms of efficiency and required hardware sup- port. A detailed very large scale integrated implementation has been performed and a number of experimental results on a set of embedded applications is reported for each technique. Energy dissipation decreases of up to 95% can be observed for the tag arrays, implying significant energy reductions in the range of 50% when amortized across the overall cache subsystem. [ABSTRACT FROM AUTHOR]

We describe a constrained test-generation procedure for synchronous sequential circuits embedded in a large design where scan is used to provide access to the inputs of the individual circuits. The constrained test-generation procedure generates test sequences, where each vector is obtained from the previous one by shifting the scan chain a limited number of positions. Such constrained sequences can be applied through a scan chain with minimal test-application time overhead due to scan. When a shift by a single positions is used to obtain each vector from the previous one, the constrained test sequences can allow functional (at-speed) testing of the circuit. Although constrained test sequences cannot achieve complete fault coverage, they reduce the overall test-application time required to achieve complete fault coverage when used together with unconstrained test sequences. We demonstrate these features through experimental results. [ABSTRACT FROM AUTHOR]

A new form of logic diagnosis is described that is suitable for diagnosing falls in combinational logic. It can diagnose defects that can affect arbitrarily many elements in the integrated circuit. It operates by first identifying patterns during which only one element is affected by the defect, and then diagnosing the fails observed during the application of such patterns, one pattern at a time. Single stuck-at faults are used for this purpose, and the aggregate of stuck-at fault locations thus identified is then further analyzed to obtain the most accurate estimate of the identifies of those elements that can be affected by the defect. This approach to logic diagnosis is as effective as that of classical stuck-at fault-based diagnosis, when the latter applies, but is far more general. In particular, it can diagnose fails caused by bridges and opens as well as fails caused by regular stuck-at faults. [ABSTRACT FROM AUTHOR]

Studies the aspects of the field of computer aided design for electronic systems as it developed from the 1960s to 2000. Background on the discovery of computers; Discussion on the simulation of circuits and systems on computers; Political issue on microelectronics in Europe in the 1950s and 1960s.