Last Modified: October 11, 2006
  1. The VLSI Design-Manufacturing Interface
  2. VLSI Interconnect Performance Analysis and Optimization
  3. VLSI Interconnect Synthesis and Prediction
  4. Technology Extrapolation and the "Living Roadmap"
  5. MARCO GSRC Calibrating Achievable Design (C.A.D.) Theme
  6. Other Topics

    1. Layout-Based Scan Optimizations
    2. DNA Array Synthesis
    3. Electronic / Computational Commerce
    4. The Y Interconnect Architecture
    5. Power Grid Planning
    6. Mask Fabrication Cost Reduction

6. Other Topics

  1. Layout-Based Scan Optimizations

    The increasing cost of test (ATE equipment and tester time) causes BIST (including scan-based BIST) solutions to be more attractive. We are investigating post-routing, or routing-aware, methods for scan chain ordering as well as full-scan based delay fault testing. For example, the scan chain ordering can exploit such degrees of freedom as (1) (timing- and noise-feasible) connection to any point in the fanout tree of Q or Q' in the scan flip-flop cell, and (2) insertion of inverting and/or non-inverting buffers for delay, noise and wirelength minimization. Also we consider pin-to-net distances instead of pin-to-pin distances for constrcuting the TSP cost matrix. This results in more asymmetric TSP instances (which may not obey the triangle inequality), which has implications for choice of heuristic solvers.

  2. back to top

  3. DNA Array Synthesis

    DNA arrays are synthesized using a photolithographic method similar to VLSI chip manufacturing. In this context, appropriate regions are activated by illuminating the array through a series of masks. Due to diffraction, internal reflection, and scattering, points close to the border between illuminated and shadowed regions are often subject to unintended illumination levels. To reduce the amount of unknown synthesized sequences and simplify interpretation of experimental data, a main objective of DNA array design is to minimize the total border length of the masks. There are two degrees of freedom that can be used to minimize border length: the assignment of probes to array cells (also called placement), and the geometry of masks.

    A sequence of masks is periodic if the masks synthesize nucleotides in a fixed periodic order, e.g., A,C,T,G,A,C,T,G,... A recent paper by Hannenhalli, Hubbell, Lipshutz, and Pevzner considers the case of synchronous array design, in which the sequence of masks is periodic, and every probe grows by exactly one nucleotide after every 4 masks. Under this restriction the mask geometry degree of freedom disappears, and the placement problem becomes equivalent to finding a 1-to-1 assignment of probes to array cells such that the sum of Hamming distances between all pairs of adjacent probes is minimized. We are currently investigating algorithms for finding periodic (but not necessarily synchronous) sequences of masks minimizing total border length, as well as methods for solving the combined probe placement and mask definition problem for non-synchronous synthesis.

  4. back to top

  5. Electronic / Computational Commerce

    Electronic commerce ("computational commerce") is one of the fastest growing areas of computer science research. Our work in this field lies at the intersection between computation theory, game-theory, and economic mechanism design. In particular, we have studied mechanisms in which buyers have a limited budget and wish to buy at most one item in multi-item auctions. We have shown the limitations of two known mechanisms -- sequence of single-item auctions and recently introduced XOR double auctions -- and introduced a new mechanism, the so-called XOR (double) auction with buyer preferences (XOR-(D)ABP), which avoids these limitations.

    In the proposed mechanism, buyers specify preferences on the items for which they bid. We seek allocations of the items to the buyers which are stable with respect to buyers' preferences, i.e., items which are preferable to the item allocated to a buyer are sold for a price higher or equal to what she offered for them. In the case of double auctions, the allocation should also ensure fairness to the sellers: if an item received a bid with a higher value than the allocated price then the buyer who placed that bid gets a more or equally preferable item. We first show that in an XOR auction with no ties in buyer preferences and bid values, both buyers and sellers are better off than in an XOR auction. Second, we show that finding stable allocations with maximum revenue or buyer satisfaction can be done efficiently in an XOR-DABP without ties, and that the problem is NP-hard when ties are allowed. We propose a practical heuristic for finding maximum stable allocations in the presence of ties, and report promising experimental results. Third, we consider the special case when all bids for an item have the same value and give an efficient algorithm based on maximum bipartite matching. We also show that in this case stable allocations form a greedoid.

    back to top

  6. The Y Interconnect Architecture

    The Y-architecture refers to the use of 0-, 120-, and 240-degree oriented wires for on-chip interconnect, along with supporting methodologies including hexagonal die shapes, hexagonal power and clock distribution, etc. This name is used in the same spirit as the ``X architecture'' for pervasive use of 45- and 135-degree angles. Compared to the traditional Manhattan architecture, the Y-architecture offers many potential advantages, such as substantially reduced wirelength and power consumption, and increased communication bandwidth for a wide range of demand topologies. Combined with the M-architecture, the Y-architecture can be applied to the upper two layers to improve global interconnects, such as clock and power distribution networks. Moreover, unlike the X-architecture, the Y-architecture supports a regular routing grid and novel means of avoiding via blockage effects.

    Our research provides a complete, technically in-depth analysis of key deployment and methodology issues associated with the Y-architecture for semiconductor ICs, including throughput analysis, estimates of wirelength savings, clock and power distribution methodology, wireability, and manufacturing. We have published two conference papers at SLIP03 and ICCAD03 in this area.

  7. back to top

  8. Power Grid Planning

    In engineering practice, design of the power distribution network usually consists of a number of stages. Many important decisions -- notably, the nominal wiring pitch and width for each interconnect layer -- are locked in for the power distribution network very early in the design process. In early stages of design, the power network has not yet been synthesized and the location and logic content of the blocks are unknown. It is therefore impossible to obtain the pattern of current drawn by the sinks, and transient analysis is essentially difficult at this stage. Thus, design decisions are mostly based on DC analysis of uniform mesh structures, with current drains modeled using simple area-based calculations. In current practice, designers often try different combinations of wire pitch and width for different layers, and select the best combination based on circuit simulations. Due to the time-consuming nature of circuit simulation, it is computationally infeasible to explore all possible configurations; the result is hence a suboptimal solution. In this context, it is both practically useful and theoretically interesting to seek a new approach to optimize topology for a hierarchical, uniform power distribution.

    We study the worst-case static IR-drop on hierarchical power meshes using both analytical and empirical methods. We propose a novel and efficient method for optimizing worst-case static IR-drop on hierarchical, uniform power distribution meshes. Our results can be used for planning of hierarchical power meshes in early design stages, so that for a fixed total routing area the worst-case IR-drop on the power mesh is minimal, or for a given IR-drop tolerance the power mesh achieves the IR-drop specification with minimal routing area. This work is in submission to ASP-DAC04.

  9. back to top

  10. Mask Fabrication Cost Reduction

    With the rapid increase of the mask cost, multi-project mask or "shuttle" service now becomes popular. Multiple project wafers allow customers to share the expensive cost of a mask set and result in faster prototyping. Currently, some production services such as MOSIS, CMP and TSMC, offer users small-volume design fabrication and reticle sharing for multi-design masks in order to minimize cost. Our research considers ways to minimize production costs for multiple-project wafers.

  11. back to top