waashk/dblp huggingface dataset:
finding linear building-blocks for rtl synthesis of polynomial datapaths with fixed-size bit-vectors. polynomial computations over fixed-size bit-vectors are found in many practical datapath designs. for efficient rtl synthesis, it is important to identify good decompositions of the polynomial into smaller/simpler units. symbolic computer algebra algorithms and tools have been used for this purpose. however, fixed-size (m) bit-vector arithmetic is polynomial algebra over the finite integer ring z2m, which is a non-unique factorization domain (non-ufd). while non-ufds provide an extra freedom to search for decompositions, they complicate polynomial manipulation as traditional division-based algorithms are inapplicable. this paper presents new mathematical concepts for polynomial decomposition over z2m, for rtl synthesis over fixed-size m-bit vectors. given a polynomial, we identify a specific set of linear expressions and compute the gr&ouml;bner bases of their ideal (over non-ufd z2m) using syzygies. this basis serves as good building-blocks for the given computation. a decomposition is identified by subsequent gr&ouml;bner basis reduction. experimental results demonstrate significant area savings due to our approach, as compared against contemporary datapath synthesis techniques.
an efficient method to identify critical gates under circuit aging. negative bias temperature instability (nbti) is the leading factor of circuit performance degradation. due to its complex dependence on operating conditions, especially signal probability, it is a tremendous challenge to accurately predict the degradation rate in reality. on the other hand, we demonstrate in this work that it is feasible to reliably predict the relative importance of gates under nbti. by identifying critical gates that are the most important ones for timing degradation, we will be able to effectively protect the circuit from aging, with the minimum design overhead. the proposed method is based on a new timing analysis framework that integrates a nbti-aware library. for each potential critical path, we prove that there exists a particular signal probability, which leads to the worst case of timing degradation. the search of such worst case signal probability provides a safe guardband for the degradation, yet avoiding overly pessimistic analysis. by applying this method to iscas and itc benchmark circuits at the 65nm node, we demonstrate that in average only 1% of total gates need to be protected in order to control the timing degradation within 10% in ten years. since this method only requires one-time analysis of each critical path, it is very efficient in computation. with the information of critical gates available, it further enables other resilient design techniques to mitigate circuit aging under nbti.
efficient vco phase macromodel generation considering statistical parametric variations. with the growing concern of process variability, parameterized circuit models are becoming increasingly important for circuit design and verification. although techniques exist to extract compact vco phase macromodels, a direct parametrization of vco macromodels over a large set of parametric variations not only results in highly complex models, but also leads to significantly high computational cost. in this paper, an efficient parameterized vco phase model generation technique is presented to capture the impacts of statistical parametric variations. the model extraction cost of our approach is significantly reduced by exploiting circuit-specific parameter dimension reduction, which effectively reduces the parameter space dimension over which the phase model needs to be extracted. the application of parameter reduction is facilitated by a novel and fast time-domain sampling technique that provides the essential statistical correlation data. our numerical experiments have shown that the proposed model generation approach is more efficient than brute-force parametric modeling while producing accurate parameterized phase models that can capture large range parametric variations.
compatibility path based binding algorithm for interconnect reduction in high level synthesis. this paper describes a register and functional unit (fu) binding algorithm in high level synthesis. our algorithm targets the reduction of multiplexer inputs. since multiplexers connect multiple inputs to fus or registers, the multiplexer count is a good indicator of the interconnect complexity. reducing the number of multiplexer inputs results in reducing interconnect cost. specifically, our algorithm constructs a weighted and ordered compatibility graph, and binds operations that form a long path in the graph together. as a result, operations with many flow dependencies and common inputs are bound to same fu, leading to a small number of fu inputs. in addition, the operation variables generated by a single fu are assigned to the same register so that connections between fus and registers are reduced. we have implemented our algorithm within a matlab to verilog conversion tool, and applied it to a suite of benchmark programs. our experimental results have shown that the proposed scheme achieves 11.8%, 43.6% and 58.8% multiplexer input count reduction on average over weighted bipartite matching algorithm, k-cofamily algorithm and left edge algorithm, respectively. to assess the impact on interconnect reduction, we have generated layouts of the circuits from our verilog description. it is shown that our approach delivers a 10.1% reduction in total wire-length of global interconnects with minor area overhead of register and fus in comparison to the best previously proposed scheme.
efficient multi-layer obstacle-avoiding rectilinear steiner tree construction. given a set of pins and a set of obstacles on routing layers, a multi-layer obstacle-avoiding rectilinear steiner minimal tree (ml-oarsmt) connects these pins by rectilinear edges within layers and vias between layers, and avoids running through any obstacle to construct a steiner tree with a minimal total cost. the ml-oarsmt problem is very important for many vlsi designs with pins being located in multiple routing layers that contain numerous routing obstacles incurred from ip blocks, power networks, prerouted nets, etc. therefore, it is desired to develop an effective algorithm for the ml-oarsmt problem. however, there is no existing work on the mloarsmt problem. in this paper, we first formulate the mloarsmt problem and identify key different properties of the problem from its single-layer counterpart. based on the multi-layer obstacle-avoiding spanning graph (ml-oasg), we present the first algorithm to solve the ml-oarsmt problem. our algorithm can guarantee an optimal solution for any 2-pin net and many higher-pin nets. experiments show that our algorithm results in 33% smaller total costs on average than a construction-by-correction heuristic which is widely used for steiner-tree construction in the recent literature.
untangling twisted nets for bus routing. previous works [1], [2] on pcb bus routing assume matched pin ordering for both sides. but in practice, the pin ordering might be mismatched and the nets become twisted. in this paper, we propose a preprocessing step to untangle such twisted nets. we also present an algorithm to solve this untangling problem. our algorithm produces an optimal single-detour routing scheme that rematches the pin ordering. by integrating our preprocessing step into the bus router in [2], we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.
a novel synthesis algorithm for reversible circuits. in this paper, a new non-search based synthesis algorithm for reversible circuits is proposed. compared with the widely used search-based methods, our algorithm is guarantied to produce a result and can lead to a solution with much fewer steps. to evaluate the proposed method, several circuits taken from the literature are used. the experimental results corroborate the expected findings.
a geometric approach for early power grid verification using current constraints. the verification of power grids in modern integrated circuits must start at design time, where circuit information is unknown but could be specified or inferred from design or architectural considerations. this work builds on previously proposed techniques to deal with circuit uncertainty in the framework of linear current constraints, but proposes a cost-controlled solution, by following a geometric approach, and transforming a problem that requires as many linear programs as there are power grid nodes, to another involving a user-limited number of solutions of one linear system.
a methodology for fast and accurate yield factor estimation during global routing. in this paper, a novel and computationally efficient methodology to accurately estimate key yield factors during the global routing stage is presented. such an yield factor estimator at the global routing stage is essential since it can used to either get an early estimate of the final yield of the same design (i.e. the yield after applying the required sequence of detailed routing and post-routing yield optimizations) and/or to improve the final yield of the design by making the solution at the end of global routing more amenable to post-routing yield optimizations. the proposed yield factor estimator is inherently flexible and can easily be programmed to estimate during global routing a variety of key yield factors of the same design after a typical sequence of detailed routing and representative post-routing yield optimizations has been applied. examples are provided to show how the yield factor estimator can be used to predict short and open critical area and metal density after typical yield optimization solutions like wire-spreading, wire-widening and metal filling, respectively. experimental results presented in the paper show that the proposed yield factor estimator can predict final yield factor hotspots/values with a high degree of accuracy. the proposed estimator is also shown to be more suited for the purpose of yield factor estimation compared with typical metrics at the global routing stage like congestion.
timing optimization by restructuring long combinatorial paths. we present an implementation of an algorithm for constructing provably fast circuits for a class of boolean functions with input signals that have individual starting times. we show how to adapt this algorithm to logic optimization for timing correction at late stages of vlsi physical design and report experimental results on recent industrial chips. by restructuring long critical paths, our code achieves worst-slack improvements of up to several hundred picoseconds on top of traditional timing optimization techniques.
a fast and high-capacity electromagnetic solution for highspeed ic design. this paper proposes a fast and high-capacity electromagnetic solution, time-domain layered finite element reduction recovery (lafe-rr) method, for high-frequency modeling and simulation of large-scale on-chip circuits. this method rigorously reduces the matrix of a multilayer system to that of a single-layer one regardless of the original problem size. more important, the matrix reduction is achieved analytically, and hence the cpu and memory overheads are minimal. the recovery of solutions in all other layers involves only forward and backward substitution of matrices of single-layer size. the memory cost is also modest-requiring only the memory needed for the factorization of a single layer sparse matrix. the improved performance applies to any arbitrarily shaped multilayer structure. numerical and experimental results are presented to demonstrate the accuracy, efficiency, and capacity of the proposed method.
the coming of age of physical synthesis. physical synthesis, the integration of logic synthesis with physical design information, was born in the mid to late 1990s, which means it is about to enter its teenage years. today, physical synthesis tools are a major part of the eda industry, accounting for hundreds of millions of dollars in revenue. this work looks at how technology and design trends have affected physical synthesis over the last decade and also how physical synthesis will continue to evolve on its way to adulthood.
thermal-aware steiner routing for 3d stacked ics. in this paper, we present the first work on the steiner routing for 3d stacked ics. in the 3d steiner routing problem, the pins are located in multiple device layers, which makes it more general than its 2d counterpart. our algorithm consists of two steps: tree construction and tree refinement. our tree construction algorithm builds a delay-oriented steiner tree under a given thermal profile. we show that thermal-aware 3d tree construction involves the minimization of two-variable elmore delay function. in our tree refinement algorithm, we reposition the through-vias while preserving the original routing topology for further thermal optimization under performance constraint. we employ a novel scheme to relax the initial nlp formulation to ilp and consider all through-vias from all nets simultaneously. our related experiments show the effectiveness of our proposed solutions.
timing budgeting under arbitrary process variations. timing budgeting under process variations is an important step in a statistical optimization flow. we propose a novel formulation of the problem where budgets are statistical instead of deterministic as in existing works. this new formulation considers the changes of both the means and variances of delays, and thus can reduce the timing violation introduced by ignoring the changes of variances. we transform the problem to a linear programming problem using a robust optimization technique. our approach can be used in late-stage design where the detailed distribution information is known, and is most useful in early-stage design since our approach does not assume specific underlying distributions. in addition, with the help of block-level timing budgeting, our approach can reduce the timing pessimism. our approach is applied to the leakage power minimization problem. the results demonstrate that our approach can reduce timing violation from 690ps to ops, and the worst total leakage power by 17.50% on average.
a novel technique for incremental analysis of on-chip power distribution networks. we propose a novel and efficient incremental analysis technique for 'what-if analysis of on-chip power distribution networks (pdn). effect of local modifications to a pdn, including local topology changes, can be quickly analyzed without need for very expensive re-analysis of the entire modified network. we borrow ideas from a fictitious domain method that has been successfully used in solving partial differential equations arising from inhomogeneous problems in mechanics. the effect of local wiring modifications in several pdn regions is mimicked by applying fictitious currents at the boundaries of these regions in the original unmodified network. the fictitious currents are calculated from component sub-problems in a low-computation iterative procedure. the practicality of this method for use in what-if analysis is demonstrated with several large power networks from actual industrial designs. it analyzes a modified network with few million changes in a fraction of time it would take for a complete re-analysis.
fault-tolerant multi-level logic decoder for nanoscale crossbar memory arrays. several technologies with sub-lithographic features are targeting the fabrication of crossbar memories in which the nanowire decoder is playing a major role. in this paper, we suggest a way to reduce the decoder size and keep it defect tolerant by using multiple threshold voltages (vt), which is enabled by our underlying technology. we define two types of multi-valued decoders and model the defects they undergo due to the vt variation. multi-valued hot decoders yield better area saving than n-ary reflexive codes (nrc), and under severe conditions, nrc enables a non-vanishing part of the code space to recover. there are many combinations of decoder type and number of vt's yielding equal effective memory capacities. the optimal choice saves area up to 24%. we also show that the precision of the addressing voltages for decoders with unreliable vt's is a crucial parameter for the decoder design and permits large savings in memory area.
strategies for improving the parametric yield and profits of 3d ics. three-dimensional (3d) integrated circuits (ics) that integrate die with through-silicon vias (tsvs) promise to continue system and functionality scaling beyond the traditional geometric 2d device scaling. 3d integration also improves the performance of ics by reducing the communication time between different chip components through the use of short tsv-based vertical wires. this reduction is particularly attractive in processors where it is desirable to reduce the access time between the main logic die and the l2 cache or the main memory die. process variations in 2d ics lead to a drop in parametric yield (as measured by speed, leakage and sales profits), which forces manufacturers to speed bin their chips and to sell slow chips at reduced prices. in this paper we develop a model to quantify the impact of process variations on the parametric yield of 3d ics, and then we propose a number of integration strategies that use a graph-theoretic framework to maximize the performance, parametric yield and profits of 3d ics. comparing our proposed strategies to current yield-oblivious methods, it is demonstrated that it is possible to increase the number of 3d ics in the fastest speed bins by almost 2x, while simultaneously reducing the number of slow ics by 29.4%. this leads to an improvement in performance by up to 6.45% and an increase of about 12.48% in total sales revenue using up-to-date market price models.
incremental component implementation selection: enabling eco in compositional system synthesis. the component implementation selection problem (cisp) is to select the appropriate implementation for components of a design, such that the timing constraint is met and some global design objective is optimized. cisp is a generic problem that implicitly or explicitly appears in many stages of cad flow. in this paper, we present a methodology for quick and efficient updating of cisp solutions in face of incremental engineering changes. for a commonly-used formulation, we discuss necessary and sufficient conditions for optimality of a cisp solution based on which, we develop an algorithm that maintains both validity and optimality of a solution subject to incremental changes. we implemented our approach to incrementally update the threshold voltage assignment solution for a netlist going through engineering changes. on average, our method ran over 300 times faster than the "from-scratch" solver, while delivering the same results.
a methodology for timing model characterization for statistical static timing analysis. while the increasing need for addressing process variability in sub-90nm vlsi technologies has sparkled a large body of statistical timing and optimization research, the realization of these techniques heavily depends on the availability of timing models that feed the statistical timing analysis engine. to target at this critical but less explored territory, in this paper, we present numerical and statistical modeling techniques that are suitable for the underlying timing model characterization infrastructure of statistical timing analysis. our techniques are centered around the understanding that while the widening process variability calls for accurate non-first-order timing models, their deployment requires well-controlled characterization techniques to cope with the complexity and scalability. we present a methodology by which timing variabilities in interconnects and nonlinear gates are translated efficiently into quadratic timing models suitable for accurate statistical timing analysis. specific parameter reduction techniques are developed to control the characterization cost that is a function of number of variation sources. the proposed techniques are extensively demonstrated under the context of logic stage timing characterization involving interactions between logic gates and interconnects.
design, synthesis and evaluation of heterogeneous fpga with mixed luts and macro-gates. small gates, such as and2, xor2 and mux2, have been mixed with lookup tables (luts) inside the programmable logic block (plb) to reduce area and power and increase performance in fpgas. however, it is unclear whether incorporating macro-gates with wide inputs inside plbs is beneficial. in this paper, we first propose a methodology to extract a small set of logic functions that are able to implement a large portion of functions for given fpga applications. assuming that the extracted logic functions are implemented by macro-gates in plbs, we then develop a complete synthesis flow for such heterogeneous plbs with mixed luts and macro-gates. the flow includes a cut-based delay and area optimized technology mapping, a mixed binary integer and linear programming based area recovery algorithm to balance the resource utilization of macro-gates and luts for area-efficient packing, and a sat-based packing. we finally evaluate the proposed heterogeneous fpga using the newly developed flow and show that mixing lut and macro-gates, both with 6 inputs, improves performance by 16.5% and reduces logic area by 30% compared to using merely 6-input luts.
procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems. many computing systems have adopted the dynamic voltage scaling (dvs) technique to reduce energy consumption by slowing down operation speed. however, the longer a job executes, the more energy in leakage current the processor consumes for the job. to reduce the power/energy consumption from the leakage current, a processor can enter the dormant mode. existing research results for leakage-aware dvs scheduling perform procrastination of real-time jobs greedily so that the idle time can be aggregated as long as possible to turn off the processor. this paper proposes algorithms for the procrastination determination of periodic real-time tasks in uniprocessor systems. instead of greedy procrastination, the procrastination procedures are applied only when the evaluated energy consumption is less than not procrastination. evaluation results show that our proposed algorithms could derive energy-efficient solutions and outperform existing algorithms.
exploiting symmetry in sat-based boolean matching for heterogeneous fpga technology mapping. the boolean matching problem is a key procedure in technology mapping for heterogeneous field programmable gate arrays (fpga), and sat-based boolean matching (sat-bm) provides a highly flexible solution for various fpga architectures. however, the computational complexity of state-of-the-art sat-bm prohibits its application practically. in this paper we propose an efficient sat-bm algorithm by exploring function and architectural symmetries. while the most recent work obtained up to 13x speedup, we achieve up to 200x speedup, when both are compared to the original sat-bm algorithm.