New Algorithmic Techniques for Complex EDA Problems

VLSI design is a very complex problem in today’s decananometer technology and billion-plus gate designs. There are two broad sets of effects that result from the rapidly decreasing feature sizes in CMOS VLSI: (a) significant increase in the number and the diversity of systems that are implemented on a single chip and (b) further exacerbation of old problems and the introduction of new ones, such as high power dissipation and temperature hot spots at all levels of the design process, high process-voltage-temperature based variability in various CMOS and interconnect parameters, and reliability of the design stemming from reduced feature sizes, to name a few. These issues present significant challenges to the entire range of EDA tools from system-level to gate-level synthesis to more accurate and computationally tractable analysis methods to better reliability via robust design and effective testing techniques. However, current algorithmic approaches used to tackle these issues lack the necessary optimization and analysis heft needed, while also being computationally tractable. Thus we feel that significant algorithmic innovations are needed to tackle these new problems with efficiency and efficacy at various stages of the VLSI design flow.

Included in this special issue are six papers that present novel algorithms for a number of the aforementioned issues. A high-level meta-algorithm for scheduling a chain of coarse grained tasks on a linear array of FPGAs, which can tackle a wide range of problem formulations and cost functions, is presented in the first paper “Meta-algorithms for scheduling a chain of coarse-grained tasks on an array of reconfigurable FPGAs” by D. P. Mehta, C. Shetters and D.W. Bouldin. The second paper “Power-driven global routing for multisupply voltage domains” by T.-H. Wu, A. Davoodi, and J. T. Linderoth, presents a new formulation for the power-aware routing problem for multi-supply voltage designs. The problem is solved using integer programming and parallel processing, the latter being an aspect that is actively being explored for various time-intensive EDA problems. In the third paper “Fast and near-optimal timing-driven cell sizing under cell area and leakage power constraints using a simplified discrete network flow algorithm,” H. Ren and S. Dutt develop a simplified and fast discretized network flow (DNF) algorithm for cell sizing for timing optimization under power and area constraints. This technique is much faster than a “full-fledged” DNF algorithm, but provides close to optimal solutions. The fourth paper “A graph-based approach to optimal scan chain stitching using RTL design descriptions” by L. Zaourar, Y. Kieffer, and C. Aktouf, presents a first-time mathematical formulation of the problem of scan insertion at the register transfer level of a design, and solves it as a traveling salesman problem. The work presented in the fifth paper “A novel framework for applying multiobjective GA and PSO based approaches for simultaneous area, delay, and power optimization in high level synthesis of datapaths” by D. S. Harish Ram, M. C. Bhuvaneswari and S. S. Prabhu, provides an application of the non-dominated sorting genetic algorithm (NSGA II) to the problem of multi-objective optimization in high-level synthesis with the goal of achieving solutions that are close to the true Pareto front of optimal solutions. Finally, the sixth paper “Line search-based inverse lithography technique for mask design” by X. Zhao and C. Chu, presents a novel enhanced mask design method via a highly efficient gradient-basedsearch technique that results in fewer pattern errors than previous work;it thus also reduces variability.

We hope the readers will find the papers interesting and informative, and that this special issue will get researchers thinking about developing new algorithmic approaches to effectively solving critical problems in current VLSI design.

Shantanu Dutt Dinesh Mehta Gi-Joon Nam