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.

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.

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.

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.

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.