Advanced Search | Site Directory | Contact Us

Gabriel Robins is serving as Webmaster for this page. All comments regarding this page should be directed to webteam@cs.virginia.edu. Technical inquiries regarding individual problem areas should be directed to the individual problem moderators listed below. In order to modify/refine the problems below, please contact Naveed Sherwani by sending e-mail to sherwani@ichips.intel.com.

Text can be found at http://www.ece.nwu.edu/~majid/TOP10/

Text to be provided by Andrew

1. Interconnect design and optimization have received much attention recently in deep submicron VLSI layout design. Many algorithms have been proposed for interconnect topology optimization, optimal buffer insertion, optimal wire sizing and spacing for delay, power dissipation, and reliability optimization. These optimization techniques result in many different wire widths and different spacings.
2. Multi-layer routing is widely used in modern IC designs. Routing is no longer confined to rectangular channels or switchboxes.
3. Design complex has increased significantly. A single chip may contain over 100 million transistors. Many existing routing techniques (such as maze routing) do not scale well with the increase of the design complexity.

As a result, there is a strong need to develop highly efficient and scaleable multi-layer general-area gridless routing algorithms.

Detailed routing problem: Given a netlist, pin locations, width and spacing for each net (or wire segment), and an available multi-layer general-area routing region, generate a design-rule correct detailed routing solution with the maximum routability and the minimum total routing area.

Global routing problem (interconnect planning): Given a netlist, pin locations, and an available mulit-layer general-area routing region, determine the routing topology, width, and spacing for each net under the delay, and noise constraints to maximize the routability (by a detailed router) and minimize the overall routing area.

Many recent improvements have occurred in pure min-cut bipartitioning over the last few years, and experimental results have converged with respect to the current set of CAD benchmarks. In order to perform any reasonable future evaluation of partitioning techniques, new test cases with more than 25,000 modules must be made available.

Different algorithms are appropriate for different sizes and types of circuits. Experimental work should focus on finding the best heuristics for a certain class of circuits (e.g., over 50,000 cells) in terms of quality and runtimes. Thus, a hierarchical placement tool would call many different partitioning routines depending on the nature of the current instance.

New objectives besides min-cut need to be proposed and optimized since cut is only loosely correlated with real placement objectives. New objectives should take into account factors such congestion, timing, and fixed constraint sets.

The literature has been recently inundated with 45-55 bipartitioning papers, but experimental data is much sparser and more inconsistent for multi-way partitioning. Here, new objectives would be even more applicable.

Previous work in FPGA partitioning has sought to minimize cost while satisfying block and I/O constraints. Other FPGA objectives that are more esoteric need to be studied, such as maximizing routability.

Synthesis operations such as replication and alternative wires should be further researched.

Numerous clustering algorithms have been proposed over the years, but typically they have been proposed as a technique within another method. Systematic experimentation with clustering could help reveal the best clustering objectives and techniques for particular applications.

One of the problems with partitioning is that it is generally treated as pure formulation. Thus, even if a terrific algorithm comes along that produces great min-cuts, a CAD developer may be skeptical of its ability to improve say, a placement algorithm. However, measuring the true effectiveness of a partitioning technique in terms of placement quality is very difficult. Implementing a quality placement tool requires significant overhead and is beyond the scope of many research programs. Ideally, one research group could do a great service by making a placement tool available with a "plug-in" partitioning interface. This would allow direct and easy comparison of partitioning approaches in terms of placement quality and would go a long way towards solving some of the above problems. Of course, the more tools with this "plug-in" feature, the better.

Purpose: Chip design cycle is very long (2-3 years), in earlier part of this design cycle, only partial information is available. However for floorplanning and RC estimate reasons, we still need to route. In that sense, we are asking for an incremental routing estimation tool.

Given: A routing region with netlist, obstacles, already routed nets, pin locations for un-routed nets, allowable layers for routing per net, width of a net. And a number stating how many % nets are missing from the netlist (say 20%).

Output: Produce a routing of nets in the netlist while leaving space for un-listed nets.

Benchmark: Use any standard channel (or switch box) and delete randomly 20% nets. Algorithm should work with any 20% deleted.

Second delete only 10% nets and route the region.

Third delete only 5% nets and route the region.

Testing: Route the complete netlist and the incomplete netlist and report the comparison. Report how accuracy of your algorithm behaves as % incompleteness decreases.

Restrictions: We recommend starting with 2 and three layer channel ans switch-box routing problems.

Problem statement: In a synchronous digital system, the clock signal is used to define the time reference for the movement of data within that system. Since this function is vital to the operation of a synchronous system, much attention has been given to the characteristics of these clock signals and the networks used in their distribution. Clock signals are often regarded as simple control signals; however, these signals have some very special characteristics and attributes. Clock signals are typically loaded with the greatest fanout, travel over the greatest distances, and operate at the highest speeds of any signal, either control or data, within the entire system. Since the data signals are provided with a temporal reference by the clock signal, the clock waveforms must be particularly clean and sharp. Furthermore, these clock signals are strongly affected by technology scaling in that long global interconnect lines become highly resistive as line dimensions are decreased. This increased line resistance is one of the primary reasons for the increasing significance of clock distribution networks on synchronous performance. The control of any differences in the delay of the clock signals can also severely limit the maximum performance of the entire system and create catastrophic race conditions in which an incorrect data signal may latch within a register.

Hot topics in clock distribution networks:

1. Layout algorithms to automatically route clock distribution networks for both zero and non-zero clock skew
2. Integrated buffer/repeater sizing and insertion with wiring tapering
3. Clock skew scheduling algorithms
4. Effects of on-chip inductances on clock signal impedance characteristics
5. Clock tree topological synthesis
6. Tolerance to process parameter variations and source jitter
7. Microwave frequency design and compensation techniques
8. Methodology enhancements - top-down vs. bottom-up (or both?)

Purpose: One problem is crucial for interconnect optimization is to come up with a second order delay model which is more precise than the Elmore delay, yet can be simply expressed in terms of the circuit parameters. This could include, for example, both the first and second moments, expressed in a way that delay calculation and optimization can be done readily.

Problem statement:

Regular (2-dimensional) layout structures are the most efficient physical implementation of certain classes of circuits (especially datapaths). Although a considerable part of the logic on a chip is regular, conventional placement tools do not take advantage of the regularity. This results in poor area and especially in very poor timing.

Hot problems:

• Regularity extraction/Identifying datapaths: How to find regular parts in a seemingly random netlist.
• Optimal automatic placement of datapath which are not entirely regular or which have changing buswidths.
• Integrating the datapath physical design in a conventional physical design flow.

There is a paradigm shift from timing driven to timing driven/noise avoidance in the next two years for high end designs.