AI Seminar
    -------------------------------
    Tuesday, March 16th, 2004
    4:00 pm - 5:30 pm
    175 ATL (Large Conference Room)

    "Block Packing: From Puzzle-Solving to Chip Design"

    Igor Markov
    Department of Electrical Engineering and Computer Science
    Advanced Computer Architecture Laboratory
    University of Michigan




----------------------------------
Packing more boxes into a fixed-size container
can be useful in many applications, and two-dimensional
variants of this problem are often called floorplanning.
These problems appear very hard in practical applications,
such as VLSI chip design, and are typically solved with
simulated annealing. However, recent work significantly
improves optimal solvers.

The talk will cover recent results on block-packing puzzles
and several abstract floorplanning formulations, including
blocks with fixed and variable aspect ratios, in the context of
either outline minimization or fixed outline. I will then relate
block packing to the design and manufacturing of integrated
circuits and describe our ongoing work on CAD tools.

A particularly interesting problem with impactful applications
is the so-called mixed-size ("boulders and dust") placement. It
combines the complexity of block packing with that of large-scale
VLSI placement, and allows one to improve clock cycle and power
consumption of semiconductor products with embedded memories,
pre-designed arithmetic circuits, analog components, etc.