waashk/dblp huggingface dataset:
analytical delay models for vlsi interconnects under ramp input. elmore delay has been widely used as an analytical estimate of interconnect delays in the performance-driven synthesis and layout of vlsi routing topologies. however, for typical rlc interconnections with ramp input, elmore delay can deviate by up to 100% or more from spice-computed delay since it is independent of rise time of the input ramp signal. we develop new analytical delay models based on the first and second moments of the interconnect transfer function when the input is a ramp signal with finite rise time. delay estimates using our first moment based analytical models are within 4% of spice-computed delay, and models based on both first and second moments are within 2.3% of spice, across a wide range of interconnect parameter values. evaluation of our analytical models is several orders of magnitude faster than simulation using spice. we also describe extensions of our approach for estimation of source-sink delays in arbitrary interconnect trees.
evaluation of placement techniques for dna probe array layout. dna probe arrays have emerged as a core genomic technology thatenables cost-effective gene expression monitoring, mutation detection,single nucleotide polymorphism analysis and other genomicanalyses. dna chips are manufactured through a highly scalableprocess, very large-scale immobilized polymer synthesis (vl-sips),that combines photolithographic technologies adapted fromthe semiconductor industry with combinatorial chemistry. commerciallyavailable dna chips contain more than a half millionprobes and are expected to exceed one hundred million probes inthe next generation. this paper is one of the first attempts to applyvlsi cad methods to the problem of probe placement in dnachips, where the main objective is to minimize total border cost(i.e., the number of nucleotide mismatches between adjacent sites).we make the following contributions. first, we propose severalpartitioning-based algorithms for dna probe placement thatimprove solution quality by over 4% compared to best previouslyknown methods. second, we give a simple in-place probe re-embeddingalgorithm with solution quality better than previous"chessboard" and batched greedy algorithms. third, we experimentallyevaluate scalability and suboptimality of existing and newlyproposed probe placement algorithms. interestingly, we find thatdna placement algorithms appear to have better suboptimalityproperties than those recently reported for vlsi placement algorithms.
intrinsic shortest path length: a new, accurate a priori wirelength estimator. a priori wirelength estimation is concerned with predicting various wirelength characteristics before placement. in this work we propose a novel, accurate estimator of net lengths. we observe that in "good" placements, the length of a net is very strongly correlated with the numbers of nets in the shortest paths connecting node pairs of the net, when each shortest path is computed under the restriction that the net itself does not exist. we refer to this as the net's intrinsic shortest path length (ispl). using ispl as a wirelength estimator has several advantages: (1) it transparently handles multi-pin nets and is a strong predictor of their length; (2) it strongly correlates with the average netlist wirelength; (3) it has a distribution that is similar to that of wirelength; and (4) it acts as a good predictor for individual net lengths. based on ispls, we characterize vlsi netlists with a single value and develop an intuitive, empirical link between our proposed value and the rent parameter. we also analytically model the relationship between ispl and wirelength, and use ispls in two practical applications: a priori total wirelength estimation and a priori global interconnect prediction.
architecture and details of a high quality, large-scale analytical placer. modern design requirements have brought additional complexities to netlists and layouts. millions of components, whitespace resources, and fixed/movable blocks are just a few to mention in the list of complexities. with these complexities in mind, placers are faced with the burden of finding an arrangement of placeable objects under strict wirelength, timing, and power constraints. in this paper we describe the architecture and novel details of our high quality, large-scale analytical placer. the performance of our placer has been recently recognized in the recent ispd-2005 placement contest, and in this paper we disclose many of the technical details that we believe are key factors to its performance. we describe (i) a new clustering architecture, (ii) a dynamically adaptive analytical solver, and (iii) better legalization schemes and novel detailed placement methods. we also provide extensive experimental results on a number of benchmark sets. on average, our results are better than the best published results by 3%, 14%, and 6% for the ibm ispd '04, iccad '04, and ispd '05 benchmark sets respectively. one of the goals of this paper is to also provide enough details to enable possible future replication of our methods.
low-cost single-layer clock trees with exact zero elmore delay skew. we give the first single-layer clock tree construction with exact zero skew according to the elmore delay model. the previous linear-planar-dme method guarantees a planar solution under the linear delay model. in this paper, we use a linear-planar-dme variant connection topology to construct a low-cost zero skew tree (zst) according to the elmore delay model. while a linear-delay zst is trivially converted to an elmore-delay zst by &ldquo;detouring&rdquo; wires, the key idea is to defer this detouring as much as possible to reduce tree cost. costs of our planar zst solutions are comparable to those of the best previous non-planar zst solutions, and substantially improve over previous planar clock routing methods.
an analytic placer for mixed-size placement and timing-driven placement. we extend the aplace wirelength-driven standard-cell analytic placement framework of a.a. kennings and i.l. markov (2002) to address timing-driven and mixed-size ("boulders and dust") placement. compared with timing-driven industry tools, evaluated by commercial detailed routing and sta, we achieve an average of 8.4% reduction in cycle time and 7.5% reduction in wirelength for a set of six industry testcases. for mixed-size placement, we achieve an average of 4% wirelength reduction on ispd02 mixed-size placement benchmarks compared to results of the leading-edge solver, feng shui (v2.4) (khatkhate et al., 2004). we are currently evaluating our placer on industry testcases that combine the challenges of timing constraints, large instance sizes, and embedded blocks (both fixed and unfixed).
on identifying don't care inputs of test patterns for combinational circuits. given a test set for stuck-at faults, some of primary input values may be changed to opposite logic values without losing fault coverage. we can regard such input values as don't care (x). in this paper, we propose a method for identifying x inputs of test vectors in a given test set. while there are many combinations of x inputs in the test set generally, the proposed method finds one including x inputs as many as possible, by using fault simulation and procedures similar to implication and justification of atpg algorithms. experimental results for iscas benchmark circuits show that approximately 66% of inputs of un-compacted test sets could be x in average. even for compacted test sets, the method found that approximately 47% of inputs are x. finally, we discuss how logic values are reassigned to the identified x inputs where several applications exist to make test vectors more desirable.
hardware/software partitioning for multi-function systems. we are interested in optimizing the design of multi-function embedded systems that run a pre-specified set of applications, such as multi-standard audio/video codecs and multi-system phones. such systems usually have stringent performance constraints and tend to have mixed hardware-software implementations. the current state of the art in the hardware/software codesign of such systems is to design for each application separately. this often leads to application-specific sub-optimal decisions and inconsistent mappings of common nodes in different applications. we use these as the guiding principles to formulate, as a codesign problem, the design and synthesis of an efficient hardware-software implementation for a multi-function embedded system. our solution methodology is to first identify nodes that represent similar functionality across different applications. such "common" nodes are characterized by several metrics. these metrics are quantified and used by a hardware/software partitioning tool to map common nodes to the same resource as far as possible. we demonstrate how this is achieved by modifying a traditional partitioning algorithm (gclp) used to partition single applications. the overall result of the system-level partitioning process is (1) a hardware or software mapping and (2) a schedule for execution for each node within the application set. on an example set consisting of three video applications, we show that the solution obtained by the use of our method is 38% smaller than that obtained when each application is considered independently.
lru-seq: a novel replacement policy for transition energy reduction in instruction caches. leakage energy will be the major energy consumer in futuredeep sub-micron designs. especially the memory sub-systemof future socs will be negatively affected by this trend. inorder to reduce the leakage energy, memory banks are transitionedto a low-energy state when possible. this transitionitself costs some energy which is termed as the transition energy.in this paper we present, as the first approach of its kind,a novel energy saving replacement policy called lru-seq forinstruction caches. evaluation of the policy on various architecturesin a system-level environment has shown that upto23% energy savings can be obtained. considering the negligiblehardware impact, lru-seq offers a viable choice foran energy saving policy.
mixed signal dft: a concise overview. practical mixed-signal dft solutions are presentedwith an emphasis on performance, cost, and testcoverage.special consideration is given to thepossible dft techniques for phase-locked loops(plls) with associated implications on testcoverage, performance, cost, and time to market.an introduction to practical dft techniques fordata converters (a/d and d/a) follow.anoverview of ieee p1149.4 analog test bus standardconcludes the embedded tutorial.
interconnect parasitic extraction in the digital ic design methodology. accurate interconnect analysis has become essential not only for post-layout verification but also for synthesis. this tutorial explores interconnect analysis and extraction methodology on three levels: coarse extraction to guide synthesis, detailed extraction for full-chip analysis, and full 3d analysis for critical nets. we will also describe the electrical issues caused by parasitics and how they have, and will be, influenced by changing technology. the importance of model order reduction will be described as well as methodologies at the synthesis stage for avoiding parasitic problems.
fastpep: a fast parasitic extraction program for complex three-dimensional geometries. in this paper we describe a computationally efficient approach to generating reduced-order models from peec-based three-dimensional electromagnetic analysis programs. it is shown that a recycled multipole-accelerated approach applied to recent model order reduction techniques requires nearly two orders of magnitude fewer floating point operations than direct techniques thus allowing the analysis of larger, more complex three-dimensional geometries.
efficient techniques for inductance extraction of complex 3-d geometries. the combination of a mesh analysis equation formulation technique with a preconditioned gmres matrix solution algorithm to accelerate the determination of inductances of complex three-dimensional structures is described. addition of the preconditioner to gmres can reduce the cost of solution to m2 operations compared to m 2 for direct inversion. results from fasthenry, a 3-d inductance extraction program, demonstrate that the iterative approach can accelerate solution times by more than an order of magnitude
highly accurate fast methods for extraction and sparsification of substrate coupling based on low-rank approximation. more aggressive design practices have created renewed interest in techniques for analyzing substrate coupling problems. most previous work has focused primarily on faster techniques for extracting coupling resistances, but has offered little help for reducing the resulting resistance matrix, whose number of nonzero entries grows quadratically with the number of contacts. wavelet-like methods have been applied to sparsifying the resistance matrix representing the substrate coupling, but the accuracy of the method is very sensitive to the particulars of the contact layout. in this paper we show that for the substrate problem it is possible to improve considerably on the wavelet-like methods by making use of the algorithmic structure common to the fast multipole and wavelet-like algorithms, but making judicious use of low-rank approximations. the approach, motivated by the hierarchical svd algorithm, can achieve more than an order of magnitude better accuracy for commensurate sparsity, or can achieve much better sparsity at commensurate accuracy, when compared to the wavelet-like algorithm.
2d data locality: definition, abstraction, and application. data locality has been a central theme in the compiler optimization world for a long time. most of the prior compiler techniques try to optimize data locality in a one-dimensional linear address space. however, there are many problems out there where the domain for data locality can be two or higher dimensional. for example, in a 2d mesh network environment, each node has connections with its four neighbors, and therefore, the data locality can potentially be exploited in two dimensions from a given processor's viewpoint. because of this, maximizing the number of communications with any of four neighbors (instead of other nodes) helps improve performance. similar examples can be given from the areas of embedded sensor processing and 3d systems as well. in this application domain, we make two specific contributions. first, we show how array data of a loop-intensive application can be mapped onto a 2d mesh so that the communication distances between the nodes are reduced. second, we discuss how code restructuring through loop transformation can help us achieve better data locality in the 2d space.
banked scratch-pad memory management for reducing leakage energy consumption. current trends indicate that leakage energy consumption will be an important concern in upcoming process technologies. we propose a compiler-based leakage energy optimization strategy for on-chip scratch-pad memories (spms). the idea is to divide spm into banks and use compiler-guided data layout optimization and data migration to maximize spm bank idleness, thereby increasing the chances of placing banks into low-power (low-leakage) state.
improving memory energy using access pattern classification. in this paper, we propose a data-driven strategy to optimize the memory energy consumption in a banked memory system. our compiler-based strategy modifies the original execution order of loop iterations in array-dominated applications to increase the length of the time period(s) in which memory banks are idle (i.e., not accessed by any loop iteration). to achieve this, it first classifies loop iterations according to their bank access patterns and then, with the help of a polyhedral tool, tries to bring the iterations with similar bank access patterns close together. increasing the idle periods of memory banks brings two major benefits; first, it allows us to place more memory banks into low-power operating modes, and second, it enables us to use a more aggressive (i.e., more energy saving) operating mode for a given bank. our strategy has been evaluated using seven array-dominated applications on both a cacheless system and a system with cache memory. our results indicate that the strategy is very successful in reducing the memory system energy, and improves the memory energy by as much as 34% on the average.
delay bounded buffered tree construction for timing driven floorplanning. as devices and lines shrink into the deep submicron range, the propagation delay of signals can be effectively improved by repowering the signals using intermediate buffers placed within the routing trees. almost no existing timing driven floorplanning and placement approaches consider the option of buffer insertion. as such, they may exclude solutions, particularly early in the design process, with smaller overall area and better routability. in this paper, we propose a new methodology in which buffered trees are used to estimate wire delay during floorplanning and placement. instead of treating delay as one of the objectives, as done by the majority of previous work, we formulate the problem in terms of delay bounded buffered trees (dbb-tree). the dbb formulation is as follows: given a net and delay bounds on critical sinks, construct a tree with intermediate buffers inserted to minimize both the total wiring length and the number of buffers while satisfying the given delay bounds. based on the elmore delay model, we propose an efficient algorithm to construct a dbb spanning tree for use during floorplanning and placement. experimental results show that the algorithm is very effective. using buffer insertion at the floorplanning and placement stage yields significantly better solutions in terms of both chip area and total wire length.
fir filter synthesis algorithms for minimizing the delay and the number of adders. as the complexity of digital filters is dominated by the number of multiplications, many works have focused on minimizing the complexity of multiplier blocks that compute the constant coefficient multiplications required in filters. although the complexity of multiplier blocks is significantly reduced by using efficient techniques such as decomposing multiplications into simple operations and sharing common subexpressions, previous works have not considered the delay of multiplier blocks which is a critical factor in the design of complex filters. in this paper, we present new algorithms to minimize the complexity of multiplier blocks under the given delay constraints. by analyzing multiplier blocks in view of delay, three delay reduction methods are proposed and combined into previous algorithms. since the proposed algorithms can generate multiplier blocks that meet the specified delay, a trade-off between delay and hardware complexity is enabled by changing the delay constraints. experimental results show that the proposed algorithms can reduce the delay of multiplier blocks at the cost of a little increase of complexity.
subthreshold leakage modeling and reduction techniques. as technology scales, subthreshold leakage currents grow exponentially and become an increasingly large component of total power dissipation. cad tools to help model and manage subthreshold leakage currents will be needed for developing ultra low power and high performance integrated circuits. this paper gives an overview of current research to control leakage currents, with an emphasis on areas where cad improvements will be needed. the first part of the paper explores techniques to model subthreshold leakage currents at the device, circuit, and system levels. next, circuit techniques such as source biasing, dual vt partitioning, mtcmos, and vtcmos are described. these techniques reduce leakage currents during standby states and minimize power consumption. this paper also explores ways to reduce total active power by limiting leakage currents and optimally trading off between dynamic and leakage power components.
a novel clock distribution and dynamic de-skewing methodology. in present day vlsi ics, intra-die processing variations are becoming harder to control, resulting in a large skew in the clock signals at the end of the clock distribution network. we describe a buffered h-tree technique to distribute the clock signal and to de-skew a clock network. the clock shielding wires (which are connected to gnd in normal operation) are, in de-skewing mode, used to selectively return the clock signal for de-skewing, and for serial communication with the clock distribution sites for skew adjustment. our forward and return clock networks are buffered, with identically sized and co-located wires and buffers. this results in both these networks exhibiting identical delay characteristics in the presence of intra-die process variations. unlike existing approaches, our method utilizes a single phase detection circuit, and can achieve a very low maximum chip-level clock skew. this skew value is not dependent on the resolution of the phase detector. further, our technique can be applied dynamically, either at boot time or periodically during the operation of the ic, as necessary. additionally, our buffered h-tree enables us to implement efficient clock gating by allowing the user to turn off clocks in the distribution network itself, thus disabling entire sections of the clock network. we demonstrate the utility of our technique on a 6-level h-tree clock distribution network. in a clock distribution network which is initially skewed by up to 300ps, our technique can de-skew signals to within 4ps of each other. we show that the total wiring area of our clock distribution and de-skewing methodology is about 35% higher than a traditional h-tree (which does not have a deskewing functionality), while the active logic area overhead is about 25%. the power consumption of our network is 5% lower than that of a traditional h-tree network with no de-skewing functionality.
ies3: a fast integral equation solver for efficient 3-dimensional extraction. integral equation techniques are often used to extract models of integrated circuit structures. this extraction involves solving a dense system of linear equations, and using direct solution methods is prohibitive for large problems. in this paper, we present ies/sup 3/ (pronounced "ice cube"), a fast integral equation solver for three-dimensional problems with arbitrary kernels. extraction methods based on ies/sup 3/ are substantially more efficient than existing multipole-based approaches.
efficient time-domain simulation of frequency-dependent elements. we describe an efficient algorithm for the time-domain simulation of elements described by causal impulse responses. the computational bottleneck in the simulation of such elements is the need to compute convolutions at each time point. hence, direct approaches for the simulation of such elements require time o(n^2), where n is the length of the simulation. we apply ideas from approximation theory to reduce this complexity to o(n \log n) while maintaining double-precision accuracy. the only restriction imposed by our method is that the impulse response h(t) gets ``smoother'' as t goes to infinity. essentially all physically reasonable impulse responses have this characteristic. the ideas presented can also be applied to time-domain simulation of elements described in the frequency domain, including those characterized by measured data. in this paper, we demonstrate the efficiency of the algorithm by applying it to the simulation of lossy transmission lines.
logical effort based technology mapping. we propose a new approach to library-based technology mapping, based on the method of logical effort. our algorithm is close to optimal for fanout-free circuits, and is extended to solve the load-distribution problem for circuits with fanout. on average, benchmark circuits mapped using our approach are 25.39% faster than the solutions obtained from sis.