**Efficient Cellular Automata Algorithms for Planar Graph
and VLSI Layout Homotopic Compaction
**

Fawaz
S. Al-Anzi

Department of Computer Engineering, Kuwait University

P.O. Box 5969, Safat, Postal Code 13060 Kuwait

Email: alanzif@eng.kuniv.edu.kw

**Abstract**

One-dimensional homotopic compaction is defined
as; In a given routable layout, a layout of minimum width is reachable by
operations that can move each module horizontally as a unit, also deform lines
maintaining their connections and maintain their routability. This paper
exploits the nature of parallelism of this problem and introduces an efficient
cellular automata algorithm for homotopic compaction of layouts of planar graphs
and VLSI circuits. The proposed algorithm inputs a bitmap representation of a
routable initial layout and produces a feasible layout of minimum width. The
proposed algorithm achieves a speed up of *O(N ^{2}logN) *over the
best known sequential algorithm. It also solves the problem of automatic jog
introduction effectively. The
algorithm is implemented on CAM6, a cellular automata machine developed by Tom
Toffoli [19] at MIT. The proposed algorithm has good performance measures in
terms of total area, total wire length, total number of bends and module
distribution of a layout. The implementation objectives of minimizing the number
of bits per processing element and reducing the time complexity of the overall
task are also studied. The results
show that the compacted bitmap representation of a planar graph, and hence a
VLSI layout, is a potential approach to high performance computing in CAD
environments by using a cellular automata machine as an inexpensive accelerator.

**Keywords**:
.