Dp. Mehta, CLOTH MEASURE - A SOFTWARE TOOL FOR ESTIMATING THE MEMORY REQUIREMENTS OF CORNER STITCHING DATA-STRUCTURES, VLSI design (Print), 7(4), 1998, pp. 425-436
In a previous paper [1], we derived formulae for estimating the storag
e requirements of the Rectangular and L-shaped Corner Stitching data s
tructures [2, 3] for a given layout. These formulae require the comput
ation of quantities called violations, which are geometric properties
of the layout. In this paper, we present optimal Theta(n log n) algori
thms for computing violations, where n is the number of rectangles in
the layout. These algorithms are incorporated into a software tool cal
led CLOTH MEASURE. Experiments conducted with CLOTH MEASURE show that
it is a viable tool for estimating the memory requirements of a layout
without having to implement the corner stitching data structures, whi
ch is a tedious and time-consuming task.