Search

Computing systems utilize multicore processors with complex cache coherence protocols to meet the increasing need for performance and energy improvement. It is a major challenge to verify the correctness of a cache coherence protocol since the number of reachable states grows exponentially with the number of cores. In this paper, we propose an efficient test generation technique, which can be used to achieve full state and transition coverage in simulation-based verification for a wide variety of cache coherence protocols. Based on effective analysis of the state space structure, our method can generate more efficient test sequences (50% shorter) on-the-fly compared with tests generated by BFS. While our on-the-fly method can reduce the numbers of required tests by half, it can still be impractical to verify all possible transitions in the presence of large number of cores. We propose scalable on-the-fly test generation techniques using quotient state space. The proposed approach guarantees selection of important transitions by utilizing equivalence classes, and omits only similar transitions. Our experimental results demonstrate that our proposed approaches can efficiently tradeoff between transition coverage and validation effort. [ABSTRACT FROM AUTHOR]

This paper proposes a new technique, called conditional differential coefficients method (CDCM), for hardware-efficient realization of finite impulse response filters using differential coefficients. In connection to this, a group of differential coefficients are extracted from the entire set which aims to reduce the total number of ones in the coefficient representation. Selection of the differential coefficients has been done in accordance with its difference with the original coefficient. It has the consequent effect of minimizing the total number of full adders with respect to direct method, minimum index floating point representation scheme, minimal difference DCM, and so on. [ABSTRACT FROM AUTHOR]

Neuro-inspired architectures based on synaptic memory arrays have been proposed for on-chip acceleration of weighted sum and weight update in machine/deep learning algorithms. In this paper, we developed NeuroSim, a circuit-level macro model that estimates the area, latency, dynamic energy, and leakage power to facilitate the design space exploration of neuro-inspired architectures with mainstream and emerging device technologies. NeuroSim provides flexible interface and a wide variety of design options at the circuit and device level. Therefore, NeuroSim can be used by neural networks (NNs) as a supporting tool to provide circuit-level performance evaluation. With NeuroSim, an integrated framework can be built with hierarchical organization from the device level (synaptic device properties) to the circuit level (array architectures) and then to the algorithm level (NN topology), enabling instruction-accurate evaluation on the learning accuracy as well as the circuit-level performance metrics at the run-time of online learning. Using multilayer perceptron as a case-study algorithm, we investigated the impact of the “analog” emerging nonvolatile memory (eNVM)’s “nonideal” device properties and benchmarked the tradeoffs between SRAM, digital, and analog eNVM-based architectures for online learning and offline classification. [ABSTRACT FROM AUTHOR]

Current trends in high performance and embedded computing include design of increasingly complex hardware architectures with high parallelism, heterogeneous processing elements, and nonuniform communication resources. In order to take hardware and software design decisions, early evaluations of the system nonfunctional properties are needed. These evaluations of system efficiency require electronic system-level information on both algorithms and architecture. Contrary to algorithm models for which a major body of work has been conducted on defining formal models of computation (MoCs), architecture models from the literature are mostly empirical models from which reproducible experimentation requires the accompanying software. In this paper, a precise definition of a model of architecture (MoA) is proposed that focuses on reproducibility and abstraction and removes the overlap previously existing between the notions of MoA and MoC. A first MoA, called the linear system-level architecture model (LSLA), is presented. To demonstrate the generic nature of the proposed new architecture modeling concepts, we show that the LSLA model can be integrated flexibly with different MoCs. LSLA is then used to model the energy consumption of a state-of-the-art multiprocessor system-on-chip (MPSoC) when running an application described using the synchronous dataflow MoC. A method to automatically learn LSLA model parameters from platform measurements is introduced. Despite the high complexity of the underlying hardware and software, a simple LSLA model is demonstrated to estimate the energy consumption of the MPSoC with a fidelity of 86%. [ABSTRACT FROM AUTHOR]

Automated analog circuit synthesis algorithms are conceptually different from manual design procedures mainly because of their limited learning capabilities, including understanding the causal justifications for certain design decisions. However, the causal information is critical for activities like constructing new circuit topologies, incrementally updating existing designs, circuit verification, and improving design optimization. This paper presents a model to represent the causal elements embedded in an analog circuit design and the methodology and algorithms to automatically extract the causal information. Experiments discuss the methodology for two state-of-the-art OpAmp/OTA circuits. [ABSTRACT FROM AUTHOR]

Flow-based microfluidic biochips are attracting increasing attention with successful applications in biochemical experiments, point-of-care diagnosis, etc. Existing works in design automation consider the flow-layer design and control-layer design separately, lacking a global optimization and hence resulting in degraded routability and reliability. This paper presents a novel integrated physical co-design methodology, which seamlessly integrates the flow-layer and control-layer design stages. In the flow-layer design stage, a sequence-pair-based placement method is presented, which allows for an iterative placement refinement based on routing feedbacks. In the control-layer design stage, the minimum cost flow formulation is adopted to further improve the routability. Besides that, effective placement adjustment strategies are proposed to iteratively enhance the solution quality of the overall control-layer design. Experimental results show that compared with the existing work, the proposed design flow obtains an average reduction of 40.44% in flow-channel crossings, 31.95% in total chip area, and 22.02% in total flow-channel length. Moreover, all the valves are successfully routed in the control-layer design stage. [ABSTRACT FROM PUBLISHER]

Monolithic 3-D integration is expected to provide significantly higher degree of device density than through-silicon-via-based 3-D integration due mainly to its nano-scale intertier connections. By stacking more than two device layers (multitier) within a 3-D chip, further wirelength reduction could be achieved, which can lead to additional performance and power benefits. In this paper, we propose a detailed placement algorithm called nonuniform-scaling-based placement to optimize the dynamic power consumption of multitier gate-level monolithic 3-D ICs. We also introduce delay- and length-based timing constraints to prevent potential degradation of the performance metric during placement. Under the same timing constraints, our algorithm reduces dynamic power consumption more effectively than the uniform-scaling-based placement algorithm by 2% to 14%. [ABSTRACT FROM AUTHOR]

Microfluidic laboratories-on-a-chip (LoCs) are replacing the conventional biochemical analyzers and are able to integrate the necessary functions for biochemical analysis on-chip. There are several types of LoCs, each having its advantages and limitations. In this paper we are interested in flow-based LoCs, in which a continuous flow of liquid is manipulated using integrated microvalves. By combining several microvalves, more complex units, such as micropumps, switches, mixers, and multiplexers, can be built. We consider that the architecture of the LoC is given, and we are interested in synthesizing an implementation, consisting of the binding of operations in the application to the functional units of the architecture, the scheduling of operations and the routing and scheduling of the fluid flows, such that the application completion time is minimized. To solve this problem, we propose a list scheduling-based application mapping (LSAM) framework and evaluate it by using real-life as well as synthetic benchmarks. When biochemical applications contain fluids that may adsorb on the substrate on which they are transported, the solution is to use rinsing operations for contamination avoidance. Hence, we also propose a rinsing heuristic, which has been integrated in the LSAM framework. [ABSTRACT FROM PUBLISHER]

Memory bandwidth bottlenecks severely restrict parallel access of data elements from data arrays. To realize high throughput out of a relatively low bandwidth, memory partitioning algorithms have been proposed to separate data arrays into multiple memory banks, from which multiple data can be accessed in parallel. However, previous partitioning schemes only considered the case of single-pattern and single-array. In the case of multipattern and multiarray, the previous partitioning schemes will use too much time to find a partition solution and cause excessively high storage overhead. In this paper, we propose an efficient two-step memory partitioning strategy for multipattern data access in multiple arrays. First, a fast, low complexity and low overhead difference-based data splitting algorithm provides a multibank solution for multiple patterns access. Then an area-efficient bank merging algorithm merges those partitioned banks from different arrays which satisfy conflict-free requirement in order to reduce the area overhead caused by partitioning. Experimental results show that our data splitting algorithm saves up to 83.0% in searching time and reduces 39.4% storage overhead compared to the state-of-the-art approaches. With the further optimization of area-efficient bank merging, the memory area overhead are saved up to 18.9% and the total partitioning time are saved up to 45.6%. [ABSTRACT FROM AUTHOR]

Directed-self-assembly (DSA) technology is a promising candidate for cut printing in sub-10nm 1-D gridded designs, where cuts might need to be redistributed such that they could be patterned by DSA guiding templates. In this paper, we first propose a linear-time optimal dynamic-programming-based algorithm for a special case of the template guided cut redistribution problem, where there is at most one dummy wire segment on a track. We then extend our algorithm to general cases by applying a bipartite matching algorithm to decompose a general problem to a set of subproblems conforming to the special case (thus each of them can be solved optimally). Our resulting algorithm can achieve a provably good performance bound, with the cost of a template distribution only linearly to the problem size. Experimental results show that our algorithm can resolve all spacing rule violations, with smaller running times, compared with the previous works on a set of common benchmarks. In addition, we also extend our algorithm to consider general design rules, simple templates, and dummy cuts. [ABSTRACT FROM PUBLISHER]

Analog CMOS integrated circuits (ICs) designs depend typically on designer knowledge and experience, as such problems are multivariate and multiobjective, presenting many combinations of input variables to be investigated in order to meet the required specifications. Nowadays, the a posteriori approach is widely used to perform the optimization processes of analog CMOS ICs using evolutionary algorithms. However, these techniques are not totally able to explore potential solutions in specific regions of the Pareto front. Designers then have difficulty in choosing the best solution capable of achieving all desired specifications simultaneously among all the ones found. In this context, the a priori approach using fitness functions has become an important alternative method to overcome these issues of the a posteriori methodology. This paper aims to compare different fitness function profiles used in the a priori optimization processes to boost the effectiveness of the search processes in relation to robustness, accuracy, and yield in analog CMOS ICs designs. We show that the Gaussian profile, proposed here, applied to the lower limit, center value, and upper limit fitness functions is able to improve all the a priori optimization evolutionary techniques investigated, including the genetic, imperialist competitive, and shuffled frog leaping algorithms. [ABSTRACT FROM PUBLISHER]

The continuous globalization of the semiconductor industry has significantly raised the vulnerability of chips under hardware Trojan (HT) attacks. It is extremely challenging to detect HTs in fabricated chips due to the existence of process variations (PVs), since PVs may cause larger impacts than HTs. In this paper, we propose a novel framework for HT detection in digital integrated circuits. The goal of this paper is to detect HTs inserted during fabrication. The HT detection problem is formulated as an under-determined linear system by a sparse gate profiling technique, and the existence of HTs is mapped to the sparse solution of the linear system. A Bayesian inference-based calibration technique is proposed to recover PVs for each chip for the sparse gate profiling technique. A batch of under-determined linear systems are solved together by the well-studied simultaneous orthogonal matching pursuit algorithm to get their common sparse solution. Experimental results show that even under big measurement errors, the proposed framework gets quite high HT detection rates with low measurement cost. [ABSTRACT FROM PUBLISHER]

Control applications are often implemented on highly cost-sensitive and resource-constrained embedded platforms, such as microcontrollers with a small on-chip memory. Typically, control algorithms are designed using model-based approaches, where the details of the implementation platform are completely ignored. As a result, optimizations that integrate platform-level characteristics into the control algorithms design are largely missing. With the emergence of cyber-physical systems (CPS)-oriented thinking, there has lately been a strong interest in co-design of control algorithms and their implementation platforms, leading to work on networked control systems and computation-aware control algorithms design. However, there has so far been no work on integrating the characteristics of a memory architecture into the design of control algorithms. In this paper we, for the first time, show that accounting for the impact of on-chip memory (or cache) reuse on the performance of control applications motivates new techniques for control algorithms design. This leads to significant improvement in quality of control for given resource availability, or more efficient implementations of embedded control applications. We believe that this paper opens up a variety of possibilities for memory-related optimizations of embedded control systems, that will be pursued by researchers working on computer-aided design for CPS. [ABSTRACT FROM PUBLISHER]

This paper presents the extension of framework for automatic design space exploration (FADSE) tool using a meta-optimization approach, which is used to improve the performance of design space exploration algorithms, by driving two different multiobjective meta-heuristics concurrently. More precisely, we selected two genetic multiobjective algorithms: 1) non-dominated sorting genetic algorithm-II and 2) strength Pareto evolutionary algorithm 2, that work together in order to improve both the solutions’ quality and the convergence speed. With the proposed improvements, we ran FADSE in order to optimize the hardware parameters’ values of the grid ALU processor (GAP) micro-architecture from a bi-objective point of view (performance and hardware complexity). Using our developed approach we obtained better GAP instances (a configuration has for almost the same cycles per instruction – 1.00, the hardware complexity 38% smaller/better – 35.81 versus 58.61) in half of the time compared to a classical sequential optimization approach (5 days versus 10 days). [ABSTRACT FROM PUBLISHER]

Power consumption has become one of the major challenges in current chip design. One effective low power technology, multiple supply voltages (MSVs), has succeeded in 2D network-on-chip (NoC) design. However, few researches considered the MSV in 3D NoC, especially application-specific 3D NoC. In this paper, a complete three-stage synthesis flow for MSV-driven application-specific 3D NoC is proposed, which involves all the issues of layer assignment, voltage level assignment, 3D NoC synthesis, floorplanning, and post-floorplanning adjustment. First, a unified model is presented considering both layer assignment and voltage level assignment, which achieves the best tradeoff between core power and communication power. After that, a 3D NoC synthesis method is proposed to assign network components (NCs) to each layer and generate interlayer connections while a two-stage floorplanning algorithm is used to determine the positions of both cores and NCs. Finally, a novel transitive closure graph-based post-floorplanning repacking algorithm is applied to further reduce the communication power without changing much of the floorplan. Experimental results show that the proposed method is very effective. Compared to traditional 3D NoC, the proposed method can reduce the core power by about 33.6%; compared to MSV-driven 2D NoC, the proposed method can reduce the communication power by about 52.6%. [ABSTRACT FROM AUTHOR]

Automatic identification of custom instructions (CI) is the process of supporting the programmer in choosing automatically beneficial parts of the application source code that can then be synthesized and run on dedicated hardware. Identification is typically modeled as choosing a subgraph from a graph, representing the application, that has the highest speedup potential when implemented in custom hardware, and that fulfills the constraints of convexity and of a given maximum number of inputs and outputs. Existing algorithms for CI identification either enumerate all the valid subgraphs under the constraints of convexity and I/O, or return the subset of all maximal valid subgraphs with respect to convexity only. The downside of the former approach is that enumerating all valid subgraphs is costly, especially for large values of input and output constraints, while we may be interested in the subgraphs which obtain the best speedup only. Instead, the latter approach may fail to find a feasible solution, since the valid subgraphs with respect to convexity only can be too large to be useful. In this paper, we present a novel approach which attempts to fill the gap between the existing methods. In particular, we present an algorithm that enumerates the subset of all maximum valid subgraphs with respect to convexity and number of inputs and outputs. Our method revisits and combines the existing approaches and yields an algorithm which is effective and outperforms the state-of-the-art for large values of input and output constraints. [ABSTRACT FROM PUBLISHER]

Exploring the design space of computer architectures generally consists of a trial-and-error procedure where several architectural configurations are evaluated by using simulation techniques. The final goal of the multiobjective design space exploration (DSE) process is the identification of architectural configurations optimal for a set of target objective functions, typically power consumption, and performance. Simulations are computationally expensive making it rather hard to efficiently explore the design space to identify high-quality configurations in an acceptable exploration time when relying solely on a single-core machine to run simulations. To tackle this problem, engineers proposed solutions based on either: 1) the use of approximate analytic performance models to prune the suboptimal regions of the design space by reducing the number of simulations to run or 2) the use of parallel computing resources to run different simulations concurrently. In this paper we demonstrate that, to efficiently speedup the DSE process while fully exploiting the parallel computing infrastructure, we need to combine the two techniques together in a structured manner. In this paper, we investigate this issue and we propose a DSE solution that exploits approximate analytic prediction models to improve the simulation schedule on a parallel computing environment rather than to prune the number of simulations. Experimental results demonstrate that the proposed technique provides a speedup from 1.26\boldsymbol \times to 4\boldsymbol \times with respect to other parallel state-of-the art DSE techniques. [ABSTRACT FROM PUBLISHER]

In this paper, a precise systematic delay model is proposed for the analysis and estimation of critical path delay of multiple constant multiplication (MCM) blocks. For the first time in literature, the mathematical derivation of lower bound of critical path delay of MCM blocks is presented and necessary conditions for achieving the lower bound of critical path delay are discussed. It is shown that the lower bound of critical path delay of MCMs is significantly smaller than that achieved by existing MCM algorithms. An improved genetic algorithm-based approach, with a heuristic algorithm to generate the initial population, is proposed to search for low complexity MCM solutions with the lower bound of critical path delay. This is the first time that design algorithms with gate-level delay control is proposed. Moreover, it is shown that using the information of lower bound of critical path delay, perturbation of timing can be applied to tradeoff the lower bound critical path delay against hardware complexity. It is shown that area-time efficient design of MCM blocks can be obtained by using the proposed techniques. [ABSTRACT FROM AUTHOR]

This paper introduces a multiterminal escape routing algorithm for the design of printed circuit boards (PCBs) that control digital microfluidic biochips (DMFBs). The new algorithm extends a negotiated congestion-based single-terminal escape router that has been shown to be superior to previous methods. It relaxes the pin assignment to allow pin groups to be broken up when doing so can reduce the number of PCB layers. Experimental results indicate that the improved method can reduce both the number of PCB layers and average wirelength compared to existing DMFB escape routers. [ABSTRACT FROM AUTHOR]

The portion of clock power in system is rapidly increasing with the continuous increasing of clock frequency and clock resources. Last two decades, a great research attention has been paid to minimizing the clock power. Recently, it is shown that the structure of resonant clock networks is very effective in saving power since it can store electric energy to the inserted inductors rather than dissipate. On the other side, it has been known that dynamic voltage-frequency scaling (DVFS) is one of the most effectively and widely used power reduction techniques. However, so far no works have addressed the design methodology problem of synthesizing resonant clock networks that are able to operate under the designs with DVFS capability even though the problem is potentially very important to maximize the synergy effect on saving power. In this context, this paper proposes a comprehensive solution to the problem. Precisely, we propose a two-phase synthesis algorithm: 1) formulating the problem of inductor allocation, placement, and adjustable-sizing to support DVFS into a weighted set cover problem with the objective of minimizing total area of inductors and 2) followed by performing the task of resizing of adjustable driving buffers to support the switch of driving strength according to the clock frequencies by DVFS. Through experiments with benchmark circuits, it is shown that for designs with DVFS using 1 and 3 GHz, our algorithm synthesizes resonant clock networks with 25.9% less power on the execution of the clock frequency, which is not supported by resonant clocking in the previous no-DVFS aware resonant clock synthesis algorithm. [ABSTRACT FROM PUBLISHER]

The acceptance criteria for analog designs are traditionally defined in terms of real-valued features defined over behavioral responses. For example, rise time, peak overshoot, and settling time are features of the response of a second-order system under a step input. Designers of analog and mixed-signal (AMS) designs typically like to see whether the relevant features lie within their specified ranges, and if so, by what margin. Assertions are capable of capturing the acceptance criteria, but they do not help in evaluating how well (or by what margin) the design satisfies the specification. We introduce the notion of Feature Indented Assertions (FIAs) for overlaying the definition of real-valued features over the syntactic fabric of AMS assertions. In this paper, we present the formal syntax and semantics of our language, FIA, and demonstrate its ability to capture a wide variety of AMS features. We present our dynamic feature evaluation tool that plugs into standard AMS simulators through Verilog Procedural Interfaces and evaluates features over simulation. At the heart of this tool, we have our interval arithmetic-based algorithm for monitoring features over continuous time and value domains. This algorithm is presented with corresponding proofs of correctness and with results over industrial testcases. [ABSTRACT FROM PUBLISHER]

Recent advancements in the development of memristive devices has opened new opportunities for hardware implementation of new computing models. Researchers have shown the suitability of memristive devices for swarm intelligence algorithms to solve a maze in hardware. In this paper, we utilize swarm intelligence of memristive networks to perform image edge detection. First, we propose a hardware-friendly algorithm for image edge detection based on ant colony optimization. Second, we implement the image edge detection algorithm using memristive networks. Furthermore, we explain the impact of various parameters of the memristors on the efficacy of the implementation. Our results show 28% improvement in the energy compared to a low power CMOS hardware implementation based on stochastic circuits. Furthermore, our design occupies up to $5\boldsymbol \times $ less area. [ABSTRACT FROM AUTHOR]

Hierarchical temporal memory (HTM) is a machine learning algorithm inspired by the information processing mechanisms of the human neocortex and consists of a spatial pooler (SP) and temporal memory (TM). In this paper, we develop circuits and systems to achieve the optimized design of an HTM SP, an HTM TM, and a memristive analog pattern matcher for pattern recognition applications. The HTM SP realizes an optimized hardware design through the introduction of mean overlap calculations and by replacing the threshold determination in the inhibition stage with a weighted summation operator over the neighborhood of the pixel under consideration. HTM TM is based on discrete analog memristive memory arrays and a weight update procedure. The operation of the proposed system is demonstrated for a face recognition problem, using the standard AR, ORL, and Yale databases, and for speech recognition, using the TIMIT database, with achieved accuracies of 87.21% and approximately 90%, respectively, given an SNR of 10 dB. Visual data processing using binary HTM SP features requires less storage and processing memory than required by the traditional processing methods, with the area and power requirements for its implementation being 0.096 mm2 and 1756 mW, respectively. The design of the TM circuit for a single pixel requires 23.85 \mu\textm^2 of area and 442.26 \mu\textW of power. [ABSTRACT FROM PUBLISHER]

In recent years, a new concurrent error detection method by using invariant relationships inside a circuit, called implications, has been proposed. Algorithms have also been developed to reduce the total number of required implications so as to minimize the incurred area overhead due to implication checking logic. This implication reduction process, however, would result in degradation on the probability of error detection ( P{\mathrm{ detection}} ) of the method. In this paper, we analyze the impact of this issue mathematically together with illustration by a real case study. Our analytical results show that just one percent degradation on P{\mathrm{ detection}} would result in millions more errors being undetected per second and thereby significant loss on reliability of the target circuit. To address this issue, we develop a new implication reduction algorithm that guarantees no loss on P{\mathrm{ detection}} . In our algorithm, the detectability of errors for each candidate implication is carefully evaluated. The evaluation results are then utilized to select the most efficient candidates for detecting all the detectable errors. We also analyze the computation and memory complexity of the proposed algorithm. The experimental results on 28 representative benchmark circuits from ISCAS’85, ISCAS’89, and ITC’99 show that the implication reduction rate of our method (92.59%) is close to that of the previous work (95.8%). Only a small number of additional implications need to be selected to guarantee no loss on P{\mathrm{ detection}} . [ABSTRACT FROM PUBLISHER]

In this paper, a straightforward and effective method to identify threshold logic function (TLF) is presented. Threshold logic is a promising alternative to conventional Boolean logic due to its suitability for emerging technologies, like memristors, quantum-dot cellular automata, resonant tunneling device, and spintronic devices. Identification and synthesis of TLF are essential tasks in a design flow based on such a logic strategy. The proposed method relies on irredundant sum-of-products Boolean function description form and exploits both ordering of variables and system of inequalities to assign the variable weights and the function threshold value. This is the first heuristic algorithm able to identify all threshold functions with up to six variables, being also more effective than other heuristic methods for functions with a larger number of variables. For functions obtained from k -cuts of benchmark circuits, experimental results demonstrated effectiveness near to 100% when compared to exact methods, even when the number of function variables increases. The execution time of the proposed approach is similar to related heuristic methods, being faster than integer linear programming-based algorithms. [ABSTRACT FROM PUBLISHER]

Mismatches caused by random and systematic variations among identical designed devices usually dominate the performance of analog circuits, where the former can be controlled by increasing area, while the latter should be tackled by careful layout design. Most of existing studies propose analog placement methodologies with the common centroid constraint to mitigate the linear systematic gradient effect. However, nonlinear gradient error compensation should also be addressed for circuits requiring high performance. This paper presents a current source placement algorithm considering quadratic (second order) gradient error for a high-accuracy current-steering digital-to-analog converter to pursue excellent linearity. A new switching scheme and a submatrix swapping technique are proposed to maximize quadratic gradient compensation, and a simulated annealing-based matrix perturbation algorithm is also proposed to directly minimize integral nonlinearity (INL). In addition, to tackle the extremely high complexity of current source interconnections, we model the routing instance as a branch assignment problem and propose an optimal greedy-based algorithm, which is inspired by the well-known left-edge algorithm. The experimental results show an order of magnitude reduction in INL compared to a state-of-the-art nonlinear gradient-aware current source placement approach and better dynamic performance in post-layout simulation. [ABSTRACT FROM AUTHOR]

A placer without considering modern technology and region constraints could generate solutions with irresolvable detailed-routing (DR) violations or even illegal solutions. This paper presents a high-quality placement algorithm to satisfy technology and region constraints and optimize DR routability with five major techniques: 1) a clustering algorithm followed by two-round quadratic placement to obtain an initial placement satisfying region constraints; 2) a novel density control technique to handle prefixed architectures and minimize global routing congestions; 3) an analytical placement algorithm with new wirelength and density models to consider region constraints; 4) a dynamic penalty increment strategy that reduces wirelength increments during global placement; and 5) a legalization algorithm that preserves the solution quality of global placement while satisfying technology and region constraints. Compared with the winning teams of the ISPD 2015 Blockage-Aware Detailed Routing-Driven Placement Contest and recent works, our placer achieves the best overall score and DR results. [ABSTRACT FROM PUBLISHER]

Detailed routing is an important stage in very large scale integrated physical design. Due to the extreme scaling of transistor feature size and the complicated design rules, ensuring routing completion without design rule checking (DRC) violations becomes more and more difficult. Studies have shown that the low routing quality partly results from nonoptimal net-ordering nature of traditional sequential methods. The concurrent routing strategy is always based on an NP-hard model, thus is at a disadvantage in runtime. In this paper, we present a novel concurrent detailed routing algorithm that routes all nets simultaneously. Based on the multicommodity flow model, detailed routing problem with complex design rule constraints is formulated as an integer linear programming. Some model simplification heuristics and efficient model solving algorithms are proposed to improve the runtime. Experimental results show that, the proposed algorithms can reduce the DRC violations by 80%, meanwhile can reduce wirelength and via count by 5% and 8% compared with an industry tool. In addition, the proposed algorithm is general that it can be adopted as an incremental detailed router to refine a routing solution, so the number of DRC violations that industry tool cannot fix are further reduced by 27%. [ABSTRACT FROM PUBLISHER]

In this paper, we propose Lagrangian relaxation (LR)-based algorithms to optimize both circuit performance and total wirelength at the global placement stage. We introduce a general timing-driven global placement problem formulation that is applicable to three different circuit design styles: 1) synchronous circuits; 2) synchronous circuits with sequential optimization techniques; and 3) asynchronous circuits. LR is applied to handle the timing constraints of the formulated problem. Based on how the cell spreading constraints are handled, two different approaches are proposed: one approach handles the spreading constraints inside the LR framework and transforms the timing-driven placement (TDP) problem into a series of weighted wirelength minimization problems, which can be solved by directly leveraging existing wirelength-driven placers. The other approach handles the spreading constraints outside the LR framework. Thus, only timing constraints need to be taken care of in the LR framework and better solutions can be expected. In both approaches, we simplified the LR subproblem using Karush–Kuhn–Tucker conditions. Our algorithms are implemented based on a state-of-the-art wirelength-driven quadratic placer. The experiments demonstrate that the proposed algorithms are able to achieve significant improvements on circuit performance compared with a commercial wirelength-driven placement flow and a commercial asynchronous TDP flow. [ABSTRACT FROM PUBLISHER]

This paper presents a dynamically reconfigurable processing array named Anole for symmetric-key algorithms. Processing elements and the interconnections between them are designed to support various block and stream ciphers. Without affecting flexibility, three key techniques are presented to increase energy efficiency (throughput/power, the number of operations per unit energy consumption) and area efficiency (throughput/area). First, the distributed control network supports multithreading on reconfigurable fabrics at a low cost, thereby maximizing the utility of computing resources in the space domain. Second, the concurrent computation and reconfiguration scheme integrates configuration contexts with processing data to simultaneously execute in the data-path. The resulted immediate switching between different configurations increases the utilization rate of hardware resources in the temporal domain. Third, under configuration context compression and organization, the context memory size and configuration time are further minimized. Anole is implemented on a 7.75 mm2silicon square with TSMC 65-nm technology at 400 MHz. Experiments show that Anole significantly outperforms field programmable gate array and general purpose processor by more than two orders of magnitude in energy and area efficiencies. Compared with state-of-the-art reconfigurable solutions, Anole achieves (average) $16.5\boldsymbol {\times }$ higher energy efficiency and $9.4\boldsymbol {\times }$ higher area efficiency. [ABSTRACT FROM AUTHOR]

Secure masking schemes have been proven in theory to be secure countermeasures against side-channel attacks. The security framework proposed by Ishai, Sahai, and Wagner, known as the Ishai–Sahai–Wagner scheme, is one of the most acceptable secure models of the existing $d$ th-order masking schemes, where $d$ represents the masking order and plays the role of a security parameter. However, a gap may exist between scheme and design. Several analyses have determined that the glitch has been regarded as the main challenge of masking in hardware designs. A practical method of locating the precise position of leakage points (LPs) in the original hardware design is very rare. Existing research on this glitch mainly focuses on the first-order leakages; however, higher-order analysis can combine several shares to recover the secret key. In this paper, we propose a practical method, sensitive glitch location (SGL) method to locate the less order leakage in hardware design. Specifically, the SGL method can locate any-order of LP in the hardware implementation of $d$ th-order masking schemes. We conducted experiments and verified that the time complexity of SGL on the $d$ th-order masking schemes is ${O(nm)}$ , where $m$ is the number of signals and $n$ is the number of shares in masking scheme. It can therefore be regarded as an efficient tool for the masking designs. In addition, we analyzed the $d$ th-order masking scheme proposed by Rivain and Prouff (2010) along with the SecMult algorithm from the Rivain–Prouff countermeasure, which has been analyzed by our SGL. The experimental results verified that a higher-order leakage may exist in certain hardware designs, even the masking scheme has been proven as a secure countermeasure. To the best of our knowledge, SGL is the first tool that can be used to locate any-order of power/electromagnetic LP in hardware designs. It thus shows the weakness in the original design file of hardware implementations. This property can help designers directly improve the real security of the designs. Moreover, SGL returns the path of the leakages, which can elucidate the original cause and propagation of the weakness. [ABSTRACT FROM AUTHOR]

As a scalable substitute of on-chip bus, network-on-chip (NoC) is proposed as the communication infrastructure in modern multi/many-core system-on-chip (SoC). Efficient communication in NoC is critical to the overall SoC performance. Although local congestion has an important impact on communication delay, it is barely taken into account when designing routing algorithms. In this paper, we propose an offline methodology of designing routing algorithm based on channel pressure model to address the local congestion issue. Specifically, the proposed methodology uses divide-conquer with the aim of generating high performance routing algorithms, which are able to balance the load over the network with a consequent reduction of local congestion. By using the proposed methodology, the obtained routing could achieve up to 37% performance improvement (in terms of average communication delay) as compared to the well-known odd-even routing algorithm for $15\times 15$ network. [ABSTRACT FROM PUBLISHER]

A wirelength-driven placer without considering routability could introduce irresolvable routing-congested placements. Therefore, it is desirable to develop an effective routability-driven placer for modern mixed-size designs employing hierarchical methodologies for faster turnaround time. In this paper, we propose a novel routability-driven analytical placement algorithm for hierarchical mixed-size circuit designs. This paper presents a novel design hierarchy identification technique to effectively identify design hierarchies and guide placement for better wirelength and routability. The proposed algorithm optimizes routability from four major aspects: 1) narrow channel handling; 2) pin density; 3) routing overflow optimization; and 4) net congestion optimization. Routability-driven legalization and detailed placement are also proposed to further optimize routing congestion. Compared with the participating teams for the 2012 ICCAD Design Hierarchy Aware Routability-driven Placement Contest, our placer can achieve the best quality (both the average overflow and wirelength) and the best overall score (by additionally considering running time). [ABSTRACT FROM PUBLISHER]

Symmetry, common-centroid, topology-matching, and length-matching constraints are four major routing considerations to improve the performance of an analog circuit. Symmetry constraints are specified to route matched nets symmetrically with respect to some common axes. Common-centroid constraints are also specified to route matched net symmetrically with respect to some common centers. Topology-matching constraints are commonly imposed on critical yet asymmetry nets with the same number of bends, vias, and wirelength. Length-matching constraints are specified to route the nets which have limited resources with the same wirelength. These four constraints can reduce current mismatches and unwanted electrical effects between two critical nets. In this paper, we propose the first work to simultaneously consider the four constraints for analog routing while minimizing total wirelength, bend numbers, via counts, and coupling noise at the same time. We first present a basic integer linear programming (ILP) formulation to simultaneously consider the four constraints for analog routing. Then, a prioritized-constraint-aware routing algorithm is proposed to assist analog designers for assigning the four matching constraints and optimizing routing topologies. Effective reduction techniques are also employed to reduce the numbers of ILP variables and constraints for the two routing algorithms. To further enhance the routing performance, a nonuniform multilevel routing framework is presented and integrated into our routing algorithms. Experimental results show that our approach can obtain better routing results and satisfy all specified routing constraints while optimizing circuit performance. [ABSTRACT FROM PUBLISHER]

This paper presents an efficient method for extracting a yield-aware Pareto front between two competing metrics of an analog circuit block, with the purpose of performing hierarchical, system-level optimization using the component-level Pareto fronts as meta-models. The proposed method consists of three steps: finding a set of Pareto-optimal design points by tracing them on a discrete grid, estimating the yield distribution of each optimal design point using a control-variate technique, and constructing a yield-aware Pareto front by interpolation. The proposed algorithm is demonstrated on a problem of finding the optimal power allocation among the components composing a clock recovery path to minimize the final clock jitter. The algorithm can estimate the Pareto front of each circuit block within a 2% error, expressing the minimum achievable jitter with 99% yield for different power budgets, while requiring only \(600~\sim ~1100\) Monte-Carlo simulation samples in total. [ABSTRACT FROM PUBLISHER]

This paper proposes a nearly-2-satisfiability (SAT) routing solution for segmented-channels in row-based field programmable gate array architectures. Both dogleg-free routing and routing with doglegging are considered here. The constraints for these problems have been expressed as Boolean conjunctive norm form (CNF) clauses and the conjunction of these clauses creates a Boolean function. The formulation ensures that the maximum number of clauses created consist of 2 literals. Hence, it converts the routing problem, which is an optimization problem, to a nearly-2-SAT problem. Since 2-SAT, i.e., checking the SAT of a Boolean CNF function with clauses having maximum 2 literals, is polynomial time computable, a nearly-2-SAT problem will also compute faster than other SAT-based solutions. We have used statistical distributions to experimentally test the efficiency of our technique and compared the performance with existing SAT-based technique for segmented-channel routing. The results show that more than 90% clauses are 2-literal for both routing options in the proposed methodology and around 20 \times speedup is observed with respect to existing technique. [ABSTRACT FROM PUBLISHER]

Idling, or running the engine when the vehicle is not moving, accounts for 13%–23% of vehicle driving time and costs billions of gallons of fuel each year. In this paper, we consider the problem of idling reduction under the uncertainty of vehicle stop time. We abstract it as a classic ski rental problem, and propose a constrained version with two statistics \mu B^{\tt -} and qB^{\tt +} , the expected length of short stops and the probability of long stops. We develop two online algorithms, a suboptimal closed-form algorithm and an optimal numerical solution, that combine the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the algorithms perform better than existing solutions in terms of both worst case guarantee and average case performance using simulation and real-world driving data. [ABSTRACT FROM AUTHOR]

As the complexities of automotive systems increase, designing a system is a difficult task that cannot be done manually. In this paper, we focus on wire routing and wire sizing for weight minimization to deal with more and more connections between devices in automotive systems. The wire routing problem is formulated as a minimal Steiner tree problem with capacity constraints, and the location of a Steiner vertex is selected to add a splice which is used to connect more than two wires. We modify the Kou-Markowsky-Berman algorithm to efficiently construct Steiner trees and propose an integer linear programming (ILP) formulation to relocate Steiner vertices and satisfy capacity constraints. The ILP formulation is relaxed to a linear programming (LP) formulation which has the same optimal objective and can be solved more efficiently. Besides wire routing, wire sizing is also performed to satisfy resistance constraints and minimize the total wiring weight. To the best of our knowledge, this is the first work in the literature to formulate the automotive routing problem as a minimal Steiner tree problem with capacity constraints and perform wire routing and wire sizing for weight minimization. An industrial case study shows the effectiveness and efficiency of our algorithm which provides an efficient, flexible, and scalable approach for the design optimization of automotive systems. [ABSTRACT FROM AUTHOR]

Electron-beam (e-beam) lithography has long been employed for mask writing but the write time is increasing due to the escalating mask pattern complexity. Besides, e-beam direct write is being pursued as an alternative solution for chip production in the sub-22 nm regime. To improve the throughput of e-beam lithography, character projection method is commonly employed and a critical problem is to pack as many useful characters as possible onto the stencil. In this paper, we consider three enhancements in packed stencil design over previous works. First, the fact that the pattern of a character can be located anywhere within its enclosing projection region is exploited to facilitate flexible blank space sharing. Second, the use of multiple shaping apertures with different sizes is explored. Third, the use of overlapping shots for printing some characters is investigated. For the packed stencil design problem with flexible blank space sharing and multiple shaping apertures, two dynamic programming-based algorithms are proposed, one allows overlapping shots and the other does not. Experimental results show that the proposed enhancement and the associated algorithms can significantly reduce the total shot count and hence improve the throughput of e-beam lithography. [ABSTRACT FROM PUBLISHER]

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

A villainous son of Poseidon in Greek mythology who forces travelers to fit into his bed by stretching their bodies or cutting off their legs (adapted from Merriam-Webster). [ABSTRACT FROM PUBLISHER]

Threshold voltage assignment is a very effective technique to reduce leakage power consumption in modern integrated circuit design. As feature size continues to decrease, the layout constraints [called minimum implant area (MinIA) constraints] on the implant area, which determines the threshold voltage of a device, are becoming increasingly difficult to satisfy. It is necessary to take these constraints into consideration during the placement stage. In this paper, we propose to resolve the MinIA constraint violations of a given placement by performing simultaneous detailed placement and threshold voltage refinement. We first present an optimal and efficient mixed integer-linear programming (MILP)-based algorithm to handle intrarow MinIA constraints. We then extend the MILP-based algorithm to handle both inter-row and intrarow MinIA constraints. Both of our algorithms guarantee to fix all MinIA constraint violations. Experimental results demonstrate that our algorithms only perturb the original placement and threshold voltage assignment solutions minimally to eliminate all violations and are fast in practice. [ABSTRACT FROM AUTHOR]

A 3-D network-on-chip (NoC) enables the design of high performance and low power many-core chips. Existing 3-D NoCs are inadequate for meeting the ever-increasing performance requirements of many-core processors since they are simple extensions of regular 2-D architectures and they do not fully exploit the advantages provided by 3-D integration. Moreover, the anticipated performance gain of a 3-D NoC-enabled many-core chip may be compromised due to the potential failures of through-silicon-vias that are predominantly used as vertical interconnects in a 3-D IC. To address these problems, we propose a machine-learning-inspired predictive design methodology for energy-efficient and reliable many-core architectures enabled by 3-D integration. We demonstrate that a small-world network-based 3-D NoC (3-D SWNoC) performs significantly better than its 3-D MESH-based counterparts. On average, the 3-D SWNoC shows 35% energy-delay-product improvement over 3-D MESH for the PARSEC and SPLASH2 benchmarks considered in this paper. To improve the reliability of 3-D NoC, we propose a computationally efficient spare-vertical link (sVL) allocation algorithm based on a state-space search formulation. Our results show that the proposed sVL allocation algorithm can significantly improve the reliability as well as the lifetime of 3-D SWNoC. [ABSTRACT FROM AUTHOR]

This paper studies fault tolerance in switching reconfigurable nano-crossbar arrays. Both permanent and transient faults are taken into account by independently assigning stuck-open and stuck-closed fault probabilities into crosspoints. In the presence of permanent faults, a fast and accurate heuristic algorithm is proposed that uses the techniques of index sorting, backtracking, and row matching. The algorithm’s effectiveness is demonstrated on standard benchmark circuits in terms of runtime, success rate, and accuracy. In the presence of transient faults, tolerance analysis is performed by formally and recursively determining tolerable fault positions. In this way, we are able to specify fault tolerance performances of nano-crossbars without relying on randomly generated faults that is relatively costly regarding that the number of fault distributions in a crossbar grows exponentially with the crossbar size. [ABSTRACT FROM AUTHOR]

Many critical electronic design automation (EDA) problems suffer from the curse of dimensionality, i.e., the very fast-scaling computational burden produced by large number of parameters and/or unknown variables. This phenomenon may be caused by multiple spatial or temporal factors (e.g., 3-D field solvers discretizations and multirate circuit simulation), nonlinearity of devices and circuits, large number of design or optimization parameters (e.g., full-chip routing/placement and circuit sizing), or extensive process variations (e.g., variability /reliability analysis and design for manufacturability). The computational challenges generated by such high-dimensional problems are generally hard to handle efficiently with traditional EDA core algorithms that are based on matrix and vector computation. This paper presents “tensor computation” as an alternative general framework for the development of efficient EDA algorithms and tools. A tensor is a high-dimensional generalization of a matrix and a vector, and is a natural choice for both storing and solving efficiently high-dimensional EDA problems. This paper gives a basic tutorial on tensors, demonstrates some recent examples of EDA applications (e.g., nonlinear circuit modeling and high-dimensional uncertainty quantification), and suggests further open EDA problems where the use of tensor computation could be of advantage. [ABSTRACT FROM PUBLISHER]

This paper proposes a graph-based algorithm for solving the adjustable delay buffer (ADB) allocation problem optimally under useful clock skew scheduling. Our algorithm supports additional features: extending the optimality to the allocation of ADBs with quantized delay values, extending the optimality to the allocation of ADBs with delay upper bound, and extending to the consideration of the delay variability of clock buffers. In addition, we propose two acceleration techniques for speeding up the computation. The first one is speeding up the graph traversal of our optimal solver without sacrificing the optimality while the second one, supplementing our algorithm, is to deal with the extremely large designs at the expense of the allocation quality. The experiments with benchmark circuits show that our algorithm reduces the number of ADBs by 23.3% on average over the results produced by the conventional ADB allocation under useful clock skew scheduling and reduces the number of ADBs by 86.3% on average over that produced by the previous optimal ADB allocation under bounded clock skew constraint. In addition, our optimal algorithm runs 30–460 times faster than the prior work. [ABSTRACT FROM PUBLISHER]

Security and safety are more and more important in embedded system design. A key issue, hence lies in the ability of systems to respond safely when errors occur at runtime, to prevent unacceptable behaviors that can lead to failures or sensitive data leakage. In this paper, we propose a design approach that automatically generates on-chip monitors (OCMs) during high-level synthesis (HLS) of hardware accelerators (HWaccs). OCM checks at runtime the input/output timing behavior, the control flow execution and algorithmic properties (via American National Standards Institute C assertions) of the monitored HWacc. OCM is implemented separately from the HWacc and an original technique is introduced for their synchronization. Two synthesis options are proposed to tradeoff between performance and area. Experiment results show that error detection on the control flow is $16\times $ better compared to the existing approaches while the cost of assertions is reduced by 17.48% on average. The impact on execution time (i.e., latency of the HWacc) is decreased by $2.76\times $ at no area penalty and up to $4.5\times $ with less than 10% extra-area. The clock period overhead is at worst less than 5% and the overhead on the synthesis time of the HWacc to generate OCMs is 7.44% on average. [ABSTRACT FROM AUTHOR]

Integrating more functionality in a smaller form factor with higher performance and lower-power consumption is pushing semiconductor technology scaling to its limits. 3-D chip stacking is touted as the silver bullet technology that can keep Moore’s momentum and fuel the next wave of consumer electronic products. Additionally, the complexity of digital designs imposes that computer-aided design algorithms are getting harder and slower. This paper introduces a framework for application implementation onto 3-D reconfigurable architectures. In contrast to existing approaches, the proposed solution is customizable according to constraints posed by the application and the target 3-D device in order to improve performance metrics. Experimental results highlight the effectiveness of our framework, as we achieve average enhancements in terms of maximum operation frequency and power consumption by 35% and 47%, respectively, as compared to state-of-the-art algorithms. [ABSTRACT FROM PUBLISHER]

This paper addresses elevator assignment in vertically-partially-connected 3-D-networks-on-chip (NoCs). Elevators are vertical links between dies. Because of yield issues, Through-Silicon-Via (TSV) cost, and heterogeneity in dimension, topology, and technology of different dies, vertically-partially-connected topologies seem unavoidable in the emerging 3-D-NoCs as opposed to fully-connected topologies. In such partially-connected topologies, as there are fewer elevators than routers, the assignment of elevators to routers becomes a new 3-D-specific optimization problem. An improper assignment can lead to dramatic network performance degradation. This paper proposes an elevator assignment method for best-effort wormhole 3-D-NoCs to improve the average network performance. Experimental results show an improvement of about 90% even compared to a greedy (intrinsically good) initial assignment. [ABSTRACT FROM PUBLISHER]

Cryptographic cores are known to leak information about their private key due to runtime variations, and there are many well-known attacks that can exploit this timing channel. In this paper, we study how information theoretic measures can quantify the amount of key leakage that can be exacted from runtime measurements. We develop and analyze 22 Rivest–Shamir–Adleman (RSA) hardware designs—each with unique performance optimizations, timing channel mitigation techniques, or discretization/randomization countermeasures. We demonstrate the effectiveness of information theoretic measures for quantifying timing leakage through correlation analysis of information theoretic measurements and attack results. Experimental results show that mutual information is a promising technique for quantifying timing leakage for RSA, advanced encryption standard, and elliptic curve cryptography ciphers, i.e., the mutual information correlates to being able to successfully guess the value of the private key. This is an important step toward a hardware security metric which allows designers to reason about security alongside traditional hardware design metrics like area, performance, and power. [ABSTRACT FROM AUTHOR]

Graph applications have been gaining importance in the last decade due to emerging big data analytics problems such as Web graphs, social networks, and biological networks. For these applications, traditional CPU and GPU architectures suffer in terms of performance and power consumption due to irregular communications, random memory accesses, and load balancing problems. It has been shown that specialized hardware accelerators can achieve much better power and energy efficiency compared to the general purpose CPUs and GPUs. In this paper, we present a template-based methodology specifically targeted for hardware accelerator design of big-data graph applications. Important architectural features that are key for energy efficient execution are implemented in a common template. The proposed template-based methodology is used to design hardware accelerators for different graph applications with little effort. Compared to an application-specific high-level synthesis methodology, we show that the proposed methodology can generate hardware accelerators with up to $18\boldsymbol \times$ better energy efficiency and requires less design effort. [ABSTRACT FROM AUTHOR]