Through sequence-based classification, this paper tries to accurately predict the DNA binding sites of transcription factors (TFs) in an unannotated cellular context. Related methods in the literature fail to perform such predictions accurately, since they do not consider sample distribution shift of sequence segments from an annotated (source) context to an unannotated (target) context. We, therefore, propose a method called "Transfer String Kernel" (TSK) that achieves improved prediction of transcription factor binding site (TFBS) using knowledge transfer via cross-context sample adaptation. TSK maps sequence segments to a high-dimensional feature space using a discriminative mismatch string kernel framework. In this high-dimensional space, labeled examples of the source context are re-weighted so that the revised sample distribution matches the target context more closely. We have experimentally verified TSK for TFBS identifications on 14 different TFs under a cross-organism setting. We find that TSK consistently outperforms the state-of-the-art TFBS tools, especially when working with TFs whose binding sequences are not conserved across contexts. We also demonstrate the generalizability of TSK by showing its cutting-edge performance on a different set of cross-context tasks for the MHC peptide binding predictions.

Micron's Automata Processor (AP) efficiently emulates non-deterministic finite automata and has been shown to provide large speedups over traditional von Neumann execution for massively parallel, rule-based, data-mining and pattern matching applications. We demonstrate the AP's ability to generate high-quality and energy efficient pseudo-random behavior for use in pseudo-random number generation or in chip simulation. By recognizing that transition rules become probabilistic when input characters are randomized, the AP is also capable of simulating Markov chains. Combining hundreds of parallel Markov chains creates high-quality, high-throughput pseudo-random number sequences with greater power efficiency than state-of-the-art CPU and GPU algorithms. This indicates that the AP could potentially accelerate other Markov Chain-based applications such as agent-based simulation. We explore how to achieve throughputs upwards of 40GB/s per AP chip, with power efficiency 6.8x greater than state-of-the-art pseudo-random number generation on GPUs.

MOTIVATION: Histone modifications are among the most important factors that control gene regulation. Computational methods that predict gene expression from histone modification signals are highly desirable for understanding their combinatorial effects in gene regulation. This knowledge can help in developing 'epigenetic drugs' for diseases like cancer. Previous studies for quantifying the relationship between histone modifications and gene expression levels either failed to capture combinatorial effects or relied on multiple methods that separate predictions and combinatorial analysis. This paper develops a unified discriminative framework using a deep convolutional neural network to classify gene expression using histone modification data as input. Our system, called DeepChrome, allows automatic extraction of complex interactions among important features. To simultaneously visualize the combinatorial interactions among histone modifications, we propose a novel optimization-based technique that generates feature pattern maps from the learnt deep model. This provides an intuitive description of underlying epigenetic mechanisms that regulate genes. RESULTS: We show that DeepChrome outperforms state-of-the-art models like Support Vector Machines and Random Forests for gene expression classification task on 56 different cell-types from REMC database. The output of our visualization technique not only validates the previous observations but also allows novel insights about combinatorial interactions among histone modification marks, some of which have recently been observed by experimental studies. AVAILABILITY AND IMPLEMENTATION: Codes and results are available at www.deepchrome.org CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

While massive datasets are often stored in compressed format, most algorithms are designed to operate on uncompressed data. We address this growing disconnect by developing a framework for compression-aware algorithms that operate directly on compressed datasets. Synergistically, we also propose new algorithmically-aware compression schemes that enable algorithms to efficiently process the compressed data. In particular, we apply this general methodology to geometric / CAD datasets that are ubiquitous in areas such as graphics, VLSI, and geographic information systems. We develop example algorithms and corresponding compression schemes that address different types of datasets, including point sets and graphs. Our methods are more efficient than their classical counterparts, and they extend to both lossless and lossy compression scenarios. This motivates further investigation of how this approach can enable algorithms to process ever-increasing big data volumes.

Design automation (DA) research has for over fifty years been performed in academia, semiconductor and system companies, and EDA companies worldwide. This research has been enabling to continued scaling of design productivity and growth of the semiconductor industry. For product companies, funding program managers and individual researchers alike, a highly relevant question is: what DA research, and what DA research outcomes, ultimately have the greatest “impact”? In this paper, we present measurements and analyses of DA research outputs (papers, patents, EDA companies), upon which future metrics of DA research impact might be based. Our studies consider 47000+ conference and journal papers from 1964-2014; the inter-patent citation graph over 759000+ DA-related patents; abstracts of 1150+ U.S. NSF projects over a three-decade span; 36 research needs documents of the Semiconductor Research Corporation from 2000-2013; and market segmentation of hundreds of EDA companies. We identify several interesting correlations, but do not claim to identify causal relationships; indeed, connecting traditional measures of research output to real-world impacts seems quite challenging. We conclude with several directions and targets for future investigation.

We study compression-aware algorithms, i.e. algorithms that can exploit regularity in their input data by directly operating on compressed data. While popular with string algorithms, we consider this idea for algorithms operating on numeric sequences and graphs that have been compressed using a variety of schemes including LZ77, grammar-based compression, a graph interpretation of Re-Pair, and a method presented by Boldi and Vigna in The Web Graph Framework. In all cases, we discover algorithms outperforming a trivial approach: to decompress the input and run a standard algorithm. We aim to develop an algorithmic toolkit for basic tasks to operate on a variety of compression inputs.

MOTIVATION: The comparison of diverse genomic datasets is fundamental to understand genome biology. Researchers must explore many large datasets of genome intervals (e.g. genes, sequence alignments) to place their experimental results in a broader context and to make new discoveries. Relationships between genomic datasets are typically measured by identifying intervals that intersect, that is, they overlap and thus share a common genome interval. Given the continued advances in DNA sequencing technologies, efficient methods for measuring statistically significant relationships between many sets of genomic features are crucial for future discovery. RESULTS: We introduce the Binary Interval Search (BITS) algorithm, a novel and scalable approach to interval set intersection. We demonstrate that BITS outperforms existing methods at counting interval intersections. Moreover, we show that BITS is intrinsically suited to parallel computing architectures, such as graphics processing units by illustrating its utility for efficient Monte Carlo simulations measuring the significance of relationships between sets of genomic intervals. AVAILABILITY: https://github.com/arq5x/bits.

Recent studies have demonstrated the potential for reducing energy consumption in integrated circuits by allowing errors during computation. While most proposed techniques for achieving this rely on voltage overscaling (VOS), this paper shows that Imprecise Hardware (IHW) with design-time structural parameters can achieve orthogonal energy-quality tradeoffs. Two IHW adders are improved and two IHW multipliers are introduced in this paper. In addition, a simulation-free error estimation technique is proposed to rapidly and accurately estimate the impact of IHW on output quality. Finally, a quality-aware energy minimization methodology is presented. To validate this methodology, experiments are conducted on two computational kernels: DOT-PRODUCT and L2-NORM -- used in three applications -- Leukocyte Tracker, SVM classification and K-means clustering. Results show that the Hellinger distance between estimated and simulated error distribution is within 0.05 and that the methodology enables designers to explore energy-quality tradeoffs with significant reduction in simulation complexity.

Abstract—Location-awareness of mobile objects is the key to numerous emerging ubiquitous computing applications. We show that RFID technology can be leveraged to achieve mobile object localization in an inexpensive, power efficient, scalable, widely applicable, flexible, and user-friendly manner. We outline the challenges that can adversely affect RFID-based localization techniques, and propose solutions to mitigate them. We present several algorithms for RFID-based mobile object localization that compare favorably or exceed previous methods in terms of accuracy, speed, reliability, scalability, and cost.

Radio frequency identification (RFID) is an increasingly popular technology that uses radio signals for object identification. Tracking and authentication in RFID tags have raised many privacy and security concerns. On the other hand, known privacy and security cryptographic defenses are too hardware-expensive to incorporate into low-cost RFID tags. In this paper, we propose hardware-based approaches to RFID security that rely on physically unclonable functions (PUFs). These functions exploit the inherent variability of wire delays and parasitic gate delays in manufactured circuits, and may be implemented with an order-of-magnitude reduction in gate count as compared with traditional cryptographic functions. We describe protocols for privacy-preserving tag identification and secure message authentication codes. We compare PUFs to digital cryptographic functions, address other uses of PUFs to enhance RFID security and suggest interesting directions for future research. The proposed solutions are efficient, practical, and appropriate for low-cost RFID systems

Recently Ari Juels suggested a "yoking-proof" where a pair of radio-frequency identification (RFID) tags are both read within a specified time bound, and left open for future research the problem of generating a proof for larger groups of tags. We generalize his protocol by developing a proof which ensures that a group of tags is read within a certain time period. The tags generate such a proof even if the reader is untrusted. The proof is improbable to forge, and is verifiable off-line by a trusted verifier. Juels's problem formulation does not take privacy into account and the resulting protocol offers no privacy to the tags. We modify the problem statement to require the "yoking-proof" to maintain privacy, and we give a protocol for this new anonymous yoking problem, along with suggestions for speed ups

The classical Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-time heuristic that achieves a best-known approximation ratio of $1 + \frac{\ln 3}{2} \approx 1.55$ for general graphs and best-known approximation ratios of $\approx 1.28$ for both quasi-bipartite graphs (i.e., where no two nonterminals are adjacent) and complete graphs with edge weights 1 and 2. Our method is considerably simpler and easier to implement than previous approaches. We also prove the first known nontrivial performance bound ($1.5 \cdot$ OPT) for the iterated 1-Steiner heuristic of Kahng and Robins in quasi-bipartite graphs.

Control of variability and performance in the back end of the VLSI manufacturing line has become extremely difficult with the introduction of new materials such as copper and low-k dielectrics. To improve manufacturability, and in particular to enable more uniform chemical-mechanical planarization (CMP), it is necessary to insert area fill features into low-density layout regions. Because area fill feature sizes are very small compared to the large empty layout areas that need to be filled, the filling process can increase the size of the resulting layout data file by an order of magnitude or more. To reduce file transfer times, and to accommodate future maskless lithography regimes, data compression becomes a significant requirement for fill synthesis. In this paper, we make the following contributions. First, we define two complementary strategies for fill data volume reduction corresponding to two different points in the design-to-manufacturing flow: compressible filling and post-fill compression . Second, we compare compressible filling methods in the fixed-dissection regime when two different sets of compression operators are used: the traditional GDSII array reference (AREF) construct, and the new Open Artwork System Interchange Standard (OASIS) repetitions. We apply greedy techniques to find practical compressible filling solutions and compare them with optimal integer linear programming solutions. Third, for the post-fill data compression problem, we propose two greedy heuristics, an exhaustive search-based method, and a smart spatial regularity search technique. We utilize an optimal bipartite matching algorithm to apply OASIS repetition operators to irregular fill patterns. Our experimental results indicate that both fill data compression methodologies can achieve significant data compression ratios, and that they outperform industry tools such as Calibre V8.8 from Mentor Graphics. Our experiments also highlight the advantages of the new OASIS compression operators over the GDSII AREF construct.

Control of variability in the back end of the line, and hence in interconnect performance as well, has become extremely difficult with the introduction of new materials such as copper and low-k dielectrics. Uniformity of chemical-mechanical planarization (CMP) requires the addition of area fill geometries into the layout, in order to smoothen the variation of feature densities across the die. Our work addresses the following smoothness gap in the recent literature on area fill synthesis. (1)The very first paper on the filling problem (Kahng et al., ISPD98 [7]) noted that there is potentially a large difference between the optimum window densities in fixed dissections vs. when all possible windows in the layout are considered. (2)Despite this observation, all filling methods since 1998 minimize and evaluate density variation only with respect to a fixed dissection. This paper gives the first evaluation of existing filling algorithms with respect to "gridless" ("floating-window") mode, according to both the effective and spatial density models. Our experiments indicate surprising advantages of Monte-Carlo and greedy strategies over "optimal" linear programming (LP) based methods. Second, we suggest new, more relevant methods of measuring a local uniformity based on Lipschitz conditions, and empirically demonstrate that Monte-Carlo methods are inherently better than LP with respect to the new criteria. Finally, we propose new LP-based filling methods that are directly driven by the new criteria, and show that these methods indeed help close the "smoothness gap".

Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron very large scale integration have varying effects on device and interconnect features, depending on local characteristics of the layout. To improve manufacturability and performance predictability, the authors seek to make a layout uniform with respect to prescribed density criteria, by inserting "area fill" geometries into the layout. In this paper, they make the following contributions. First, the authors define the flat, hierarchical, and multiple-layer filling problems, along with a unified density model description. Secondly, for the flat filling problem, they summarize current linear programming approaches with two different objectives, i.e., the Min-Var and Min-Fill objectives. They then propose several new Monte Carlo-based filling methods with fast dynamic data structures. Thirdly, they give practical iterated methods for layout density control for CMP uniformity based on linear programming, Monte Carlo, and greedy algorithms. Fourthly, to address the large data volume and inherent lack of scalability of flat layout density control, the authors propose practical methods for hierarchical layout density control. These methods smoothly trade off runtime, solution quality, and output data volume. Finally, they extend the linear programming approaches and present new Monte Carlo-based methods for the multiple-layer filling problem. Comparisons with previous filling methods show the advantages of the new iterated Monte Carlo and iterated greedy methods for both flat and hierarchical layouts and for both density models (spatial density and effective density). The authors achieve near-optimal filling for flat layouts with respect to each of these objectives. Their experiments indicate that the hybrid hierarchical filling approach is efficient, scalable, accurate, and highly competitive with existing methods (e.g., linear programming-based techniques) for hierarchical layouts.

To improve manufacturability and performance predictability, we seek to make a layout uniform with respect to prescribed density criteria, by inserting "fill" geometries into the layout. Previous approaches for at layout density control are not scalable due to the necessity of solving very large linear programs, the large data volume of the solution, and the impact of hierarchy-breaking on verification. In this paper, we give the first methods for hierarchical layout density control for process uniformity. Our approach trades off naturally between runtime, solution quality, and output data volume. We also allow generation of compressed GDSII of fill geometries. Our experiments show that this hybrid hierarchical filling approach saves data volume and is scalable, while yielding solution quality that is competitive with existing Monte-Carlo and linear programming based approaches.

We address a practical problem which arises in several areas, including network design and VLSI circuit layout. Given an undirected weighted graph G = (V, E and a family N = [N1, …, Nk] of k disjoint groups of nodes Ni ⊆ V, the Group Steiner Problem asks for a minimum-cost tree which contains at least one node from each group Ni. In this paper, we give polynomial-time O(kϵ-approximation algorithms for any fixed ϵ > 0. This result improves the previously known O(k)-approximation. We also apply our approximation algorithms to the Steiner problem in directed graphs, while guaranteeing the same performance ratio. © 2001 John Wiley & Sons, Inc.

Abstract| Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying eects on devic e and inter connect features, dep ending on local char acteristics of the layout.T o enhance manufacturability and performance p r edictability, we seek to make the layout uniform with respect to prescribed densit ycriteria, by inserting \ ll" geometries into the layout.We propose several new Monte-Carlo based lling methods with fast dynamic data structures and report the tradeo between runtime and accuracy for the suggested methods.Compared to existing linear programming based a p p r oaches, our Monte-Carlo methods seem very promising as they produc enearly-optimal solutions within reasonable runtimes.

We propose practical iterated methods for layout density control for CMP uniformity, based on linear programming, Monte-Carlo and greedy algorithms. We experimentally study the tradeoffs between two main filling objectives: minimizing density variation, and minimizing the total amount of inserted fill. Comparisons with previous filling methods show the advantages of our new iterated Monte-Carlo and iterated greedy methods. We achieve near-optimal filling with respect to each of the objectives and for both density models (spatial density [3] and effective density [8]). Our new methods are more efficient in practice than linear programming [3] and more accurate than non-iterated Monte-Carlo approaches [1].

Previous literature on very large scale integration routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however, each "terminal" consists of a large collection of electrically equivalent ports, a fact that is not accounted for in layout steps such as wiring estimation. In this paper, we address the general problem of minimum-cost routing tree construction in the presence of multiport terminals, which gives rise to the group Steiner minimal tree problem. Our main result is the first known approximation algorithm for the group Steiner problem with a sublinear performance bound. In particular, for a net with k multiport terminals, previous heuristics have a performance bound of (k-1)/spl middot/OPT, while our construction offers an improved performance bound of 2/spl middot/(2+1n(k/2))/spl middot//spl radic/k/spl middot/OPT. Our Java implementation is available on the Web.

Certain manufacturing steps in very deep submicron VLSI involve chemical-mechanical polishing (CIMP) which has varying effects on device and interconnect features, depending on local layout characteristics. To reduce manufacturing variation due to CMP and to improve yield and performance predictability, the layout needs to be made uniform with respect to certain density criteria, by inserting "fill" geometries into the layout. This paper presents an efficient multilevel approach to density analysis that affords user-tunable accuracy. We also develop exact fill synthesis solutions based on combining multilevel analysis with a linear programming approach. Our methods apply to both flat and hierarchical designs.

In very deep-submicron very large scale integration (VLSI), manufacturing steps involving chemical-mechanical polishing (CMP) have varying effects on device and interconnect features, depending on local characteristics of the layout. To reduce manufacturing variation due to CMP and to improve performance predictability and yield, the layout must be made uniform with respect to certain density criteria, by inserting "fill" geometries into the layout. To date, only foundries and special mask data processing tools perform layout post-processing for density control. In the future, better convergence of performance verification flows will depend on such layout manipulations being embedded within the layout synthesis (place-and-route) flow. In this paper, we give the first realistic formulation of the filling problem that arises in layout optimization for manufacturability. Our formulation seeks to add features to a given process layer, such that (1) feature area densities satisfy prescribed upper and lower bounds in all windows of given size and (2) the maximum variation of such densities over all possible window positions in the layout is minimized. We present efficient algorithms for density analysis, notably a multilevel approach that affords user-tunable accuracy. We also develop exact solutions to the problem of fill synthesis, based on a linear programming approach. These include a linear programming (LP) formulation for the fixed-dissection regime (where density bounds are imposed on a predetermined set of windows in the layout) and an LP formulation that is automatically generated by our multilevel density analysis. We briefly review criteria for fill pattern synthesis, and the paper then concludes with computational results and directions for future research.

Given a weighted graph and a family of k disjoint groups of nodes, the group Steiner problem asks for a minimum-cost routing tree that contains at least one node from each group. We give polynomial-time O(k/sup /spl epsiv//)-approximation algorithms for arbitrarily small values of /spl epsiv/>0, improving on the previously known O(k/sup 1/2 /)-approximation. Our techniques also solve the graph Steiner arborescence problem with an O(k/sup /spl epsiv//) approximation bound. These results are directly applicable to a practical problem in VLSI layout, namely the routing of nets with multi-port terminals. Our Java implementation is available on the Web.

In very deep-submicron VLSI, certain manufacturing steps &mdash notably optical exposure, resist development and etch, chemical vapor deposition and chemical-mechanical polishing (CMP)&mdash have varying effects on device and interconnect features depending on local characteristics of the layout. To make these effects uniform and predictable, the layout itself must be made uniform with respect to certain density parameters. Traditionally, only foundries have performed the post-processing needed to achieve this uniformity, via insertion (“filling”) or partial deletion (“slotting”) of features in the layout. Today, however, physical design and verification tools cannot remain oblivious to such foundry post-processing. Without an accurate estimate of the filling and slotting, RC extraction, delay calculation, and timing and noise analysis flows will all suffer from wild inaccuracies. Therefore, future place-and-route tools must efficiently perform filling and slotting prior to performance analysis within the layout optimization loop. We give the first formulations of the filling and slotting problems that arise in layout post-processing or layout optimization for manufacturability. Such formulations seek to add or remove features to a given process layer, so that the local area or perimeter density of features satisfies prescribed upper and lower bounds in all windows of a given size. We also present efficient algorithms for density analysis as well as for filling/slotting synthesis. Our work provides a new unification between manufacturing and physical design, and captures a number of general requirements imposed on layout by the manufacturing process.

We address the problem of verifying that a tree is connected using probe operations which check mutual connectivity between two (or more) leaves of the tree. We present optimal algorithms for determining minimal probe sets that detect all possible edge and vertex faults in arbitrary trees. Our results are of particular interest for the testing of interconnection substrates in VLSI multichip module packaging technologies. © 1998 John Wiley & Sons, Inc. Networks 32: 189–197, 1998

Previous literature on VLSI routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however (say, in a gridded routing regime), each "terminal" consists of a large collection of electrically equivalent ports, a fact that is not accounted for in layout steps such as wiring estimation. The presence of multiple ports for a given terminal gives rise to the group Steiner minimal tree problem. In this paper, we address the general problem of minimum-cost routing tree construction in the presence of multi-port terminals. Our main result is the first known heuristic with a sub-linear performance bound. In particular, for a net with k multi-port terminals, previous heuristics have a performance bound of (k \\Gamma 1) \\Delta OPT , while our construction offers an improved performance bound of (1 + ln k 2 ) \\Delta p k \\Delta OPT . Our Java implementation is available on the World Wide Web.

Motivated by the goal of increasing the performance of FPGA-based designs, we propose new Steiner and arborescence FPGA routing algorithms. Our Steiner tree constructions significantly outperform the best known ones and have provably good performance bounds. Our arborescence heuristics produce routing solutions with optimal source-sink pathlengths, and with wirelength on par with the best existing Steiner tree heuristics. We have incorporated these algorithms into an actual FPGA router, which routed a number of industrial circuits using channel width considerably smaller than is achievable by previous routers. Our routing results for both the 3000 and 4000-series Xilinx parts are currently the best known in the Literature.

Motivated by the goal of increasing the performance o f FPGA-based designs, we propose eective Steiner and arborescence FPGA routing algorithms.Our graphbased Steiner tree c onstructions have provably-good p erformance b ounds and outperform the best known ones in practice, while our arborescence heuristics produce r outing solutions with optimal source-sink pathlengths at a reasonably low wirelength penalty.We have incorporated our algorithms into an actual FPGA router which routed a number of industrial circuits using channel widths considerably smaller than was previously possible.

We present critical-sink routing tree (CSRT) constructions which exploit available critical-path information to yield high-performance routing trees. Our CS-Steiner and "global slack removal" algorithms together modify traditional Steiner tree constructions to optimize signal delay at identified critical sinks. We further propose an iterative Elmore routing tree (ERT) construction which optimizes Elmore delay directly, as opposed to heuristically abstracting linear or Elmore delay as in previous approaches. Extensive timing simulations on industry IC and MCM interconnect parameters show that our methods yield trees that significantly improve (by averages of up to 67%) over minimum Steiner routings in terms of delays to identified critical sinks. ERTs also serve as generic high-performance routing trees when no critical sink is specified: for 8-sink nets in standard IC (MCM) technology, we improve average sink delay by 19% (62%) and maximum sink delay by 22% (52%) over the minimum Steiner routing. These approaches provide simple, basic advances over existing performance-driven routing tree constructions. Our results are complemented by a detailed analysis of the accuracy and fidelity of the Elmore delay approximation; we also exactly assess the suboptimality of our heuristic tree constructions. In achieving the latter result, we develop a new characterization of Elmore-optimal routing trees, as well as a decomposition theorem for optimal Steiner trees, which are of independent interest.

An implicit premise of existing routing methods is that the routing topology must correspond to a tree (i.e., it does not contain cycles). In this paper we investigate the consequences of abandoning this basic axiom, and instead we allow routing topologies that correspond to arbitrary graphs (i.e., where cycles are allowed). We show that non-tree routing can significantly improve signal propagation delay, reduce signal skew, and afford increased reliability with respect to open faults that may be caused by manufacturing defects and electromigration. Simulations on uniformly distributed nets indicate that depending on net size and technology parameters, our non-tree routing construction reduces maximum source-sink SPICE delay by an average of up to 62%, and reduces signal skew by an average of up to 63%, as compared with Steiner routing. Moreover, up to 77% of the total wirelength in non-trees can tolerate an open fault without disconnecting the circuit.>

Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that under the Lp norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ball; we show an even tighter bound for MSTs where the maximum degree is minimized. We give the best-known bounds for the maximum MST degree for arbitrary Lp metrics in all dimensions, with a focus on the rectilinear metric in two and three dimensions. We show that for any finite set of points in the Manhattan plane there exists an MST with maximum degree of at most 4, and for three-dimensional Manhattan space the maximum possible degree of a minimum degree MST is either 13 or 14.

We povide a new theoretical framework for constructing Steiner routing trees with minimum Elmore delay. Earlier work [3, 13] has established Elmore delay as a high fidelity estimate of "physical", i.e., SPICE-computed, signal delay. Previously, however, it was not known how to construct an Elmore delay-optimal Steiner tree. Our main theoretical result is a generalization of Hanan's theorem [11] which limited the number of possible locations of Steiner nodes in an optimal delay rectilinear Steiner tree. Another theoretical result establishes a new decomposition theorem for constructing optimal-delay Steiner trees. We develop a branch-and-bound method, called BB-SORT-C, which exactly minimizes any linear combination of Elmore sink delays; BB-SORT-C is practical for routing small nets and for delimiting the space of achievable routing solutions with respect to Elmore delay.

We analyze the impact of wiresizing on the performance of Elmore-based routing constructions. Whereas previous wiresizing schemes are static (i.e., they wiresize an existing topology), we introduce a new dynamic wiresizing technique, which uses wiresizing considerations to drive the routing construction itself. Simulations show that dynamic wiresizing affords superior performance over static wiresizing, and also avoids topological degeneracies. Moreover, dynamically-wiresized Elmore-based routing constructions significantly outperform all previous methods (including A-Trees) in term of maximum source-sink signal delay, affording to 73% average SPICE delay improvement over traditional Steiner routing.>

The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring estimation, as well as in many other areas. The MRST problem is known to be NP-hard, and the best performing MRST heuristic to date is the Iterated 1-Steiner (I1S) method recently proposed by Kahng and Robins (see ibid., vol. 11, p. 893-902, 1992). In this paper, we develop a straightforward, efficient implementation of I1S, achieving a speedup factor of three orders of magnitude over previous implementations. We also give a parallel implementation that achieves near-linear speedup on multiple processors. Several performance-improving enhancements enable us to obtain Steiner trees with average cost within 0.25% of optimal, and our methods produce optimal solutions in up to 90% of the cases for typical nets. We generalize I1S and its variants to three dimensions, as well as to the case where all the pins lie on k parallel planes, which arises in, e.g., multilayer routing. Motivated by the goal of reducing the running times of our algorithms, we prove that any pointset in the Manhattan plane has a minimum spanning tree (MST) with maximum degree 4, and that in three-dimensional Manhattan space every pointset has an MST with maximum degree of 14 (the best previous upper bounds on the maximum MST degree in two and three dimensions are 6 and 26, respectively); these results are of independent theoretical interest and also settle an open problem in complexity theory.>

We present two critical-sink routing tree (CSRT) constructions which exp!oit criticai-path information that becomes availab[e during timing-driven layout.Our CS-Steiner heuristics with "Giobai Slack Removal" modify traditional Stetner constructions and produce routing trees wtth szgntjicanthj lower criticalsink delays compared with existing performance-driven methods.We also propose a new class of Elrnore routing tree (ERT) constructions, which deratively add tree edges to minimize Elmore delay.This direct optimization of Elmore delay yields trees that improve delays to identified crztical sinks by up to 69% over minimum Steiner routtngs.ERTs also improve performance over such recent methods as [1] [6] when no critical stnks are specified.

The minimum rectilinear Steiner tree (MRST) problem is known to be NP-hard, and the best performing MRST heuristic to date is the Iterated 1-Steiner (I1S) method recently proposed by A.B. Kahng and G. Robins (1992). The authors develop a straightforward, efficient implementation of I1S, achieving speedup factors of over 200 compared to previous implementations. They also propose a parallel implementation of I1S that achieves high parallel speedup on K processors. Extensive empirical testing confirms the viability of the approach, which allows the benchmarking of I1S on nets containing several hundred pins.>

We address the efficient construction of interconnection trees with near-optimal delays. We study the accuracy and fidelity of easily-computed delay models with respect to detailed simulation (e.g., SPICE-computed delays). We show that Elmore delay minimization (W.C. Elmore, 1948) is a high-fidelity interconnect objective for IC interconnect technologies, and propose a greedy low delay tree (LDT) heuristic which for any monotone delay function can efficiently minimize maximum delay. For comparison, we also generate optimal routing trees (ORTs) with respect to Elmore delay, using branch-and-bound search. Experimental results show that the LDT heuristic approximates ORTs very accurately: for nets with up to seven pins, LDT trees have a maximum sink delay within 2.3% of optimum on average. Moreover, compared with minimum spanning tree constructions, the LDT achieves average reductions in delay of up to 35% depending on the net size.>

The authors point out that minimizing clock skew is important in the design of high-performance VLSI systems. A general clock routing scheme that achieves extremely small clock skews while still using a reasonable amount of wirelength is presented. The routing solution is based on the construction of a binary tree using geometric matching. For cell-based designs, the total wirelength of the clock routing tree is on average within a constant factor of the wirelength in an optimal Steiner tree, and in the worst case is bounded by O( square root l/sub 1/l/sub 2/*1 square root n) for n terminals arbitrarily distributed in the l/sub 1/*l/sub 2/ grid. The bottom-up construction readily extends to general cell layouts, where it also achieves essentially zero clock skew within reasonably bounded total wirelength. The algorithms have been tested on numerous random examples and also on layouts of industrial benchmark circuits. The results are very promising: the clock routing yields near-zero average clock skew while using total wirelength competitive with that used by previously known methods.>

We address robust path planning for a mobile agent in a general environment by finding minimum cost source-destination paths having prescribed widths. The main result is a new approach that optimally solves the robust path planning problem using an efficient network flow formulation. Our algorithm represents a significant departure from conventional shortest-path or graph search based methods; it not only handles environments with solid polygonal obstacles, but also generalizes to arbitrary cost maps that may arise in modeling incomplete or uncertain knowledge of the environment. Simple extensions allow us to address higher dimensional problem instances and minimum-surface computations; the latter is a result of independent interest. We use an efficient implementation to exhibit optimal path-planning solutions for a variety of test problems. The paper concludes with open issues and directions for future work.>

The authors propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius minimum routing tree formulation. The authors first present several heuristics with good performance, based on an analog of Prim's minimum spanning tree construction. Next, they give an algorithm which simultaneously minimizes both routing cost and the longest interconnection path, so that both are bounded by small constant factors away from optimal. They also show that geometry helps in routing: in the Manhattan plane, the total wire length for Steiner routing improves to 3/2*(1+(1/ epsilon )) times the optimal Steiner tree cost, while in the Euclidean plane, the total cost is further reduced to (2/ square root 3)*(1+(1/ epsilon )) times optimal. The method generalizes to the case where varying wire length bounds are prescribed for different source-sink paths. Extensive simulations confirm that this approach works well.>

A fast approach to the minimum rectilinear Steiner tree (MRST) problem is presented. The method yields results that reduce wire length by up to 2% to 3% over the previous methods, and is the first heuristic which has been shown to have a performance ratio less than 3/2; in fact, the performance ratio is less than or equal to 4/3 on the entire class of instances where the ratio c(MST)/c(MRST) is exactly equal to 3/2. The algorithm has practical asymptotic complexity owing to an elegant implementation which uses methods from computation geometry and which parallelizes readily. A randomized variation of the algorithm, along with a batched variant, has also proved successful.>

A family of examples on which a large class C of minimum spanning tree-based rectilinear Steiner tree heuristics has a performance ratio arbitrarily close to 3/2 times optimal is given. The class C contains many published heuristics whose worst-case performance ratios were previously unknown. Of particular interest is that C contains two heuristics whose worst-case ratios had been conjectured to be bounded away from 3/2, and the construction also points out an incorrect claim of optimality for one of these heuristics. The examples also force the worst possible behavior in a number of heuristics outside C. The construction generalizes to d dimensions, where the heuristics will have performance ratios of at least 2d - 1/d; this improves the previous lower bound on performance ratio in arbitrary dimension.>

Minimizing clock skew is a very important problem in the design of high performance VLSI systems. We present a general clock routing scheme that achieves extremely small clock skews, while still using a reasonable amount of wire length. This routing solution is based on the construction of a binary tree using recursive geometric matching. We show that in the average case the total wire length of the perfect path-balanced tree is within a constant factor of the wire length in an optimal Steiner tree, and that in the worst case, is bounded by O(fi when the n leaves are arbitrarily distributed in the unit square. We tested our algorithm on numerous random examples and also on industrial benchmark circuits and obtained very promising results: our clock routing yields near-zero average clock skew while using similar or even shorter total wire length in comparison with the methods of [7].

Advances in VLSI technology and the increased complexity of circuit designs cause performance to become an increasingly important constraint for layout. The issue of delay optimization during the global routing phase is addressed. This problem is formulated as the construction of a bounded-radius spanning tree for a given pointset in the plane, and a family of effective heuristics is presented. This approach has very good empirical performance with respect to total wirelength, and can be smoothly tuned between the competing requirements of minimum delay and minimum total netlength, as confirmed by extensive computational results which confirm this. Extensions can be made to the graph and Steiner versions of the problem, and a number of open problems are described.>

Virtually all previous methods for the rectilinear Steiner tree problem begin with a minimum spanning tree topology and rearrange edges to induce Steiner points. This study presents a more direct approach: the authors iteratively find optimal Steiner points to be added to the layout. The method gives improved average-case performance, and also avoids the worst-case examples of existing approaches. Sophisticated computational geometry techniques allow efficient and practical implementation, and the method is naturally suited to real-world VLSI regimes where, e.g., via costs can be high. Extensive performance results show almost 3% wirelength reduction over the best existing methods. A number of variants and extensions are described.>