Page 43 - DSP Integrated Circuits

28 Chapter 1 DSP Integrated Circuits

point is a system description consisting of the basic building blocks, or modules,
with their sizes and interconnections. The aim is to find a partition that satisfies
the interconnection constraints and minimizes the number of chips and their
sizes. There are several ways to formulate a suitable cost function [5].
Generally, partitioning algorithms can be divided into constructive and itera-
tive improvement methods. Constructive methods are often fast, but the quality of
the results is generally not good since the algorithms are "greedy." Solutions quite
far from the global minimum are often obtained. Iterative methods start with an
initial solution, possibly obtained by a constructive algorithm, and improve the
quality of the solution by modifying it incrementally. Fortunately, in practice most
systems have only a few natural partitions, which can be found relatively easily by
the human designer.
The simplest form of iterative improvement is to select at random a pair of
modules belonging to different partitions, and then interchange them. In most
algorithms of this type, the interchange of modules is accepted only if the cost
function is decreased. If the cost increases, the change is rejected. These algo-
rithms usually lead to fairly good results, but the algorithms discussed next gener-
ally lead to even better ones.
The Kernighan-Lin algorithm, also called the group migration method, is also
based on an interchange of two modules belonging to different partitions. The
algorithm achieves its goal by using a scoring function that reflects the cost before
and after the two modules have been interchanged.
The problem with greedy algorithms, such as the random interchange
method, is that they are often trapped in a local minimum. In the simulated
annealing approach (see Chapter 7), changes that increase the cost are accepted
with a certain probability. It can be shown that this algorithm will reach the global
minimum under certain conditions.

REFERENCES
[1] Anceau R: The Architecture of Microprocessors, Addison-Wesley, Wokingham
England, 1986.
[2] Armstrong J.R.: Chip-Level Modeling with VHDL, Prentice Hall, NJ, 1989.
[3] Armstrong J.R. and Gray F.G.: Structured Logic Design with VHDL, Prentice
Hall, NJ, 1993.
[4] Birtwistle G. and Subrahmanyan: VLSI Specification, Verification and
Synthesis, Kluwer Academic Pub., Boston, 1988.
[5] Bowen B.A. and Brown W.R.: System Design, Volume II of VLSI Systems
Design for Digital Signal Processing, Prentice Hall, NJ, 1985.
[6] Coelho D.: The VHDL Handbook, Kluwer Academic Pub., Boston, 1989.
[7] Gormen T.H., Leiserson C.E., and Rivest R.L.: Introduction to Algorithms,
MIT Press, Cambridge, MA, McGraw-Hill, New York, 1993.
[8] Dillinger T.E.: VLSI Engineering, Prentice Hall, NJ, 1988.
[9] Geiger R.L., Allen P.E., and Strader II N.R.: VLSI Design Techniques for
Analog and Digital Circuits, McGraw-Hill, New York, 1989.
[10] Gregorian R. and Temes G.C.: Analog MOS Integrated Circuits for Signal
Processing, J. Wiley & Sons, New York, 1986.
[11] Haskard M.R. and May I.C.: Analog VLSI Design—nMOS and CMOS,
Prentice Hall, NJ, 1988.