waashk/dblp huggingface dataset:
a convex programming approach to positive real rational approximation. as system integration evolves and tighter design constraints must be met, it becomes necessary to account for the non-ideal behavior of all the elements in a system. certain devices common in high-frequency integrated circuit applications, such as spiral inductors, saw filters, etc, are often described and studied in the frequency domain. models take the form of frequency domain data obtained through measurement or through physical simulation. usually the available data is sampled, incomplete, noisy, and covers only a finite range of the spectrum.in this paper we present a methodology for generating guaranteed passive time-domain models of frequency-described subsystems. the methodology presented is based on convex programming based algorithms for fixed denominator system identification. the algorithm is guaranteed to produce a passive system model that is optimal in the sense of having minimum weighted square error in the frequency band of interest over all models with a prescribed set of system poles. an incremental-fitting reformulation of the problem is also introduced that trades optimality for efficiency while still guaranteeing passivity. results of the application of the proposed methodologies to the modeling of a variety of subsystems are presented and discussed.
optimization based passive constrained fitting. verification of contemporary integrated circuits requires accurate modeling of high-frequency effects in all passive component sub-systems. often, descriptions of those subsystems are only available in the frequency-domain. in this paper, we propose a simple, scalar, constrained-passive rational approximation scheme that incorporates a grid-based test for strict positive realness. in contrast to similar recent work based on convex optimization and the positive real lemma, the methodology is potentially more efficient, since it does not introduce a quadratic number of auxiliary variables, is potentially more accurate, since pole locations can be re-adjusted during the optimization, but possibly less reliable, since it relies on the solution of optimization problems that are not convex. there-fore, because of the use of local constrained non-convex optimization, the generation of feasible initial guesses is also considered.
an optimal technology mapping algorithm for delay optimization in lookup-table based fpga designs. presents a polynomial time technology mapping algorithm, called flow-map, that optimally solves the lookup-table (lut)-based field-programmable gate array (fpga) technology mapping problem for depth minimization for general boolean networks. this theoretical breakthrough makes a sharp contrast with the fact that the conventional technology mapping problem in library-based designs is np-hard. a key step in flow-map is to compute a minimum height k-feasible cut in a network, solved by network flow computation. the algorithm also effectively minimizes the number of luts by maximizing the volume of each cut and by several postprocessing operations. the flow-map algorithm was tested on a a set of benchmarks and achieved reductions of both the network depth and the number of luts in mapping solutions as compared with previous algorithms
architectural synthesis integrated with global placement for multi-cycle communication. multiple clock cycles are needed to cross the global interconnectsfor multi-gigahertz designs in nanometer technologies. forsynchronous design, this requires the consideration of multi-cycleon-chip communication at the high level. in this paper, we presenta new architectural synthesis system integrated with globalplacement, named mcas (multi-cycle architectural synthesis),on top of the recently-proposed regular distributed register(rdr) micro-architecture. the rdr architecture provides aregular synthesis platform for supporting multi-cyclecommunication. novel architectural synthesis algorithms thatintegrate high-level synthesis with global placement have beendeveloped in mcas, including scheduling-driven placement anddistributed controller generation, etc. experimental results showthat our methodology can achieve a clock period improvement of31% and a total latency improvement of 24% on averagecompared to the conventional architectural synthesis flow.
an implicit connection graph maze routing algorithm for eco routing. eco routing is a very important design capability in advanced ic, mcm and pcb designs when additional routings need to be made at the latter stage of the physical design. eco is difficult in two aspects: first, there are a large number of existing interconnects which become obstacles in the region. a hierarchical approach is not applicable in this situation, and we need to search a large, congested region thoroughly. second, advances in circuit designs require variable width and variable spacing on interconnects. thus, a gridless routing algorithm is needed. in this paper, we propose to use an implicit representation of a non-uniform grid graph for gridless maze routing algorithm. a novel slit-tree plus interval-tree data structure is developed, combined with a cache structure, to support efficient queries into the connection graph. our experiments show that this data structure is very small in memory usage while very fast in answering maze expansion related queries. this make the framework very useful in the eco type of routing.
multilevel approach to full-chip gridless routing. this paper presents a novel gridless detailed routing approach based on multilevel optimization. the multilevel framework with recursive coarsening and refinement in a "v-shaped" flow allows efficient scaling of our gridless detailed router to very large designs. the downward pass of recursive coarsening builds the representations of routing regions at different levels, while the upward pass of iterative refinement allows a gradual convergence to a globally optimized solution. the use of a multicommodity flow-based routing algorithm for the initial routing at the coarsest level and a modified maze algorithm for the refinement at each level considerably improves the quality of gridless routing results. compared with the recently published gridless detailed routing algorithm using wire planning [1], our multilevel gridless routing algorithm is 3&times; to 75&times; faster. we also compared our multilevel framework with a recently developed three-level routing approach [1] and a traditional hierarchical routing approach. our multilevel algorithm generates better detailed routing results with higher completion rates. to our knowledge, this is the first time that multilevel optimization has been applied to ic routing.
optimal wiresizing for interconnects with multiple sources. the optimal wiresizing problem for nets with multiple sources is studied under the distributed elmore delay model. we decompose such a net into a source subtree (sst) and a set of loading subtrees (lsts), and show the optimal wiresizing solution satisfies a number of interesting properties, including: the lst separability, the lst monotone property, the sst local monotone property and the general dominance property. furthermore, we study the optimal wiresizing problem using a variable grid and reveal the bundled refinement property. these properties lead to efficient algorithms to compute the lower and upper bounds of the optimal solutions. experiment results on nets from an intel processor layout show an interconnect delay reduction of up to 35.9\% when compared to the minimum-width solution. in addition, the algorithm based on a variable grid yields a speedup of two orders of magnitude without loss of accuracy, when compared with the fixed grid based methods.
an efficient approach to simultaneous transistor and interconnect sizing. in this paper, we study the simultaneous transistor and interconnect sizing (stis) problem. we define a class of optimization problems as ch-posynomial programs and reveal a general dominance property for all ch-posynomial programs. we show that the stis problems under a number of transistor delay models are ch-posynomial programs and propose an efficient and near-optimal stis algorithm based on the dominance property. when used to solve the simultaneous driver/buffer and wire sizing problem for real designs, it reduces the maximum delay by up to 16.1%, and more significantly, reduces the power consumption by a factor of 1.63x, when compared with the original designs. when used to solve the transistor sizing problem, it achieves a smooth area-delay trade-off. moreover, the algorithm optimizes a clock net of 367 drivers/buffers and 59304 /spl mu/m-long wire in 120 seconds, and a 32-bit adder with 1026 transistors in 66 seconds on a sparc-5 workstation.
global interconnect sizing and spacing with consideration of coupling capacitance. the paper presents an efficient approach to perform global interconnect sizing and spacing (giss) for multiple nets to minimize interconnect delays with consideration of coupling capacitance, in addition to area and fringing capacitances. we introduce the formulation of symmetric and asymmetric wire sizing and spacing. we prove two important results on the symmetric and asymmetric effective fringing properties which lead to a very effective bound computation algorithm to compute the upper and lower bounds of the optimal wire sizing and spacing solution for all nets under consideration. our experiments show that in most cases the upper and lower bounds meet quickly after a few iterations and we actually obtain the optimal solution. to our knowledge, this is the first in depth study of global wire sizing and spacing for multiple nets with consideration of coupling capacitance. experimental results show that our giss solutions lead to substantially better delay reduction than existing single net wire sizing solutions without consideration of coupling capacitance.
architecture and compilation for data bandwidth improvement in configurable embedded processors. many commercially available embedded processors are capable of extending their base instruction set for a specific domain of applications. while steady progress has been made in the tools and methodologies of automatic instruction set extension for configurable processors, recent study has shown that the limited data bandwidth available in the core processor (e.g., the number of simultaneous accesses to the register file) becomes a serious performance bottleneck. in this paper, we propose a new low-cost architectural extension and associated compilation techniques to address the data bandwidth problem. specifically, we embed a single control bit in the instruction op-codes to selectively copy the execution results to a set of hash-mapped shadow registers in the write-back stage. this can efficiently reduce the communication overhead due to data transfers between the core processor and the custom logic. we also present a novel simultaneous global shadow register binding with a hash function generation algorithm to take full advantage of the extension. the application of our approach leads to a nearly-optimal performance speedup (within 2% of the ideal speedup).
simultaneous driver and wire sizing for performance and power optimization. in this paper, we study the simultaneous driver and wire sizing (sdws) problem under two objective functions: (i) delay minimization only, or (ii) combined delay and power dissipation minimization. we present general formulations of the sdws problem under these two objectives based on the distributed elmore delay model with consideration of both capacitive power dissipation and short-circuit power dissipation. we show several interesting properties of the optimal sdws solutions under the two objectives, including an important result (theorem 3) which reveals the relationship between driver sizing and optimal wire sizing. these results lead to polynomial time algorithms for computing the lower and upper bounds of optimal sdws solutions under the two objectives, and efficient algorithms for computing optimal sdws solutions under the two objectives. we have implemented these algorithms and compared them with existing design methods for driver sizing only or independent driver and wire sizing. accurate spice simulations shows that our methods reduce the delay by up to 11%&ndash;47% and power dissipation by 26%&ndash;63% compared with existing design methods.
interconnect layout optimization under higher-order rlc model. studies the interconnect layout optimization problem under a higher-order rlc model to optimize not just the delay but also the waveform for rlc circuits with non-monotone signal response. we propose a unified approach that considers topology optimization, wire-sizing optimization and waveform optimization simultaneously. our algorithm considers a large class of routing topologies, ranging from shortest-path steiner trees to bounded-radius steiner trees and steiner routings. we construct a set of required-arrival-time steiner (rats) trees, providing a smooth trade-off among signal delay, waveform and routing area. using a new incremental moment computation algorithm, we interleave topology construction with moment computation to facilitate accurate delay calculation and evaluation of waveform quality. experimental results show that our algorithm is able to construct a set of topologies providing a smooth trade-off among signal delay, signal settling time, voltage overshoot and routing cost.
bounded-skew clock and steiner routing under elmore delay. we study the minimum-cost bounded-skew routing tree problem under the elmore delay model. we present two approaches to construct bounded-skew routing trees: (i) the boundary merging and embedding (bme) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the interior merging and embedding (ime) algorithm which employs a sampling strategy and dynamic programming to consider merging points that are interior to, rather than on the boundary of, the merging regions. our new algorithms allow accurate control of elmore delay skew, and show the utility of merging points inside merging regions.
buffer block planning for interconnect-driven floorplanning. this paper studies buffer block planning for interconnect-driven floorplanning in deep submicron designs. we first introduce the concept of feasible region (fr) for buffer insertion, and derive closed-form formula for fr. we observe that the fr for a buffer is quite large in general even under fairly tight delay constraint. therefore, fr gives us a lot of flexibility to plan for buffer locations. we then develop an effective buffer block planning (bbp) algorithm to perform buffer clustering such that the overall chip area and the buffer block number can be minimized. to the best of our knowledge, this is the first in-depth study on buffer planning for interconnect-driven floorplanning with both area and delay consideration.
large-scale circuit placement: gap and promise. placement is one of the most important steps in the rtl-to-gdsii synthesis process, as it directly defines the interconnects, which have become the bottleneck in circuit andsystem performance in deep submicron technologies. theplacement problem has been studied extensively in the past30 years. however, recent studies show that existing placement solutions are surprisingly far from optimal. the first part of this tutorial summarizes results from recent optimality and scalability studies of existing placement tools. thesestudies show that the results of leading placement tools fromboth industry and academia may be up to 50% to 150% awayfrom optimal in total wirelength. if such a gap can be closed,the corresponding performance improvement will be equivalent to several technology-generation advancements. thesecond part of the tutorial highlights the recent progress onlarge-scale circuit placement, including techniques for wirelength minimization, routability optimization, and performance optimization.
physical planning with retiming. in this paper, we propose a unified approach to partitioning, floorplanning, and retiming for effective and efficient performance optimization. the integration enables the partitioner to exploit more realistic geometric delay model provided by the underlying floorplan. simultaneous consideration of partitioning and retiming under the geometric delay model enables us to hide global interconnect latency effectively by repositioning ff along long wires. under the proposed geometric embedding based performance driven partitioning problem, our geo algorithm performs multi-level top-down partitioning while determining the location of the partitions. we adopt the concept of sequential arrival time [14] and develop sequential required time in our retiming based timing analysis engine. geo performs cluster-move based iterative improvement on top of multi-level cluster hierarchy [4], where the gain function obtained from the timing analysis is based on the minimization of cutsize, wirelength, and sequential slack. in our comparison to (i) state-of-the-art partitioner hmetis [9] followed by retiming [11] and simulated annealing based slicing floorplanning [15], and (ii) state-of-the-art simultaneous partitioning with retiming hpm [7] followed by floorplanning [15], geo obtains 35% and 23% better delay results while maintaining comparable cutsize, wirelength, and runtime results.
a new enhanced spfd rewiring algorithm. this paper presents an in-depth study of the theory and algorithms for the spfd-based (set of pairs of functions to be distinguished) rewiring, and explores the flexibility in the spfd computation. our contributions are in the following two areas: (1) we present a theorem and a related algorithm for more precise characterization of feasible spfd-based rewiring. extensive experimental results show that for lut-based fpgas, the rewiring ability of our new algorithm is 70% higher than spfd-based local rewiring algorithms (spfd-lr) [19][21] and 18% higher than the recently developed spfd-based global rewiring algorithm (spfd-gr)[20]. (2) in order to achieve more rewiring ability on certain selected wires used in various optimizations, we study the impact of using different atomic spfd pair assignment methods during the spfd-based rewiring. we develop several heuristic atomic spfd pair assignment methods for area or delay minimization and show that they lead to 10% more selected rewiring ability than the random (or arbitrary) assignment methods. when combining (1) and (2) together, we can achieve 38.1% higher general rewiring ability.
large scale circuit partitioning with loose/stable net removal and signal flow based clustering. in this paper, we present an efficient iterative improvement based partitioning (iip) algorithm called lsr/mffs, that combines signal flow based maximum fanout free subgraph (mffs) clustering algorithm with loose and stable net removal (lsr) partitioning algorithm. the mffs algorithm generalizes existing mffc decomposition method from combinational circuits to general sequential circuits in order to handle cycles naturally. we also study the properties of the nets that straddle the cutline carefully, and introduce the concepts of the loose and stable nets as well as effective ways to remove them out of the cutset. the lsr/mffs algorithm first applies lsr algorithm to clustered netlist generated by mffs algorithm for global-level cutsize optimization and then declusters netlist for further cutsize refinement. as a result, the lsr/mffs algorithm has achieved the best cutsize result among all the bipartitioning algorithms published in the literatures with very promising runtime performance. in particular, it outperforms the recent state-of-the-art iip algorithms la3-cdip, clip-propf, strawman, hmetis-fm, and mlc by 17.4%, 12.1%, 5.9%, 3.1%, and 1.9%, respectively. it also outperforms the state-of-the-art non-iip algorithms paraboli, fbb, and panza by 32.0%, 21.4%, and 1.4%, respectively.
multi-way vlsi circuit partitioning based on dual net representation. in this paper, we study the area-balanced multi-way partitioning problem of vlsi circuits based on a new dual netlist representation named the hybrid dual netlist (hdn). given a netlist, we first compute a k-way partition of the nets based on the hdn representation, and then transform a k-way net partition into a k-way module partitioning solution. the main contribution of our work is the formulation and solution of the k-way module contention (k-mc) problem, which determines the best assignment of the modules in contention to partitions, while maintaining user-specified area requirements, when we transform the net partition into a module partition. under a natural definition of binding factor between nets and modules, and preference function between partitions and modules, we show that the k-mc problem can be reduced to a min-cost max-flow problem. we present efficient solutions to the k-mc problem based on network flow computation. extensive experimental results show that our algorithm consistently outperforms the conventional k-fm partitioning algorithm by a significant margin.
interconnect design for deep submicron ics. in this paper, we study the interconnect layout optimization problem under a higher-order rlc model to optimize not just delay, but also waveform for rlc circuits with non-monotone signal response. we propose a unified approach that considers topology optimization, wiresizing optimization, and waveform optimization simultaneously. our algorithm considers a large class of routing topologies, ranging from shortest-path steiner trees to bounded-radius steiner trees and steiner routings. we construct a set of required-arrival-time steiner trees or rats-trees, providing a smooth trade-off among signal delay, waveform, and routing area. using a new incremental moment computation algorithm, we interleave topology construction with moment computation to facilitate accurate delay calculation and evaluation of waveform quality. experimental results show that our algorithm is able to construct a set of topologies providing a smooth trade-off among signal delay, signal settling time, voltage overshoot, and routing cost.
robust mixed-size placement under tight white-space constraints. a novel and very simple correct-by-construction top-down methodology for high-utilization mixed-size placement is presented. the polarbear algorithm combines recursive cut-size-driven partitioning with fast and scalable legalization of every placement subproblem generated by every partitioning. the feedback provided by the legalizer at all stages of partitioning improves final placement quality significantly on standard ibm benchmarks and dramatically on low-white-space adaptations of them. compared to feng shui 5.1 and capo 9.3, polarbear is the only tool that can consistently find high-quality placements for benchmarks with less than 5% white space. with white space at 5%, polarbear beats capo 9.3 by 10% in average total wirelength while feng shui 5.1 frequently fails to find legal placements altogether. with 20% white space, polarbear still beats capo 9.3 by 1% and feng shui 5.1 by 1% in average total wirelength, in comparable run times.