Complexity Issues in VLSI

From Foundations of Computing

Complexity Issues in VLSI

Optimal Layouts for the Shuffle-Exchange Graph and Other Networks

By Frank Thomson Leighton

Hardcover $27.50 S
Paperback $23.00 X £17.99




This book solves several mathematical problems in the areas of Very Large Scale Integration (VLSI) and parallel computation. In particular, it describes optimal layouts for the shuffle-exchange graph, one of the best known networks for parallel computation. Attempts to design a shuffle-exchange computer have been hampered in part by the fact that, until now, no good layouts for the shuffle-exchange graph were known. The mesh of trees network (which may eventually prove as useful as the shuffle-exchange graph) is introduced and the book shows how it can be used to perform a variety of computations, including sorting and matrix multiplication, in a logarithmic number of steps. Next, the book introduces the tree of meshes, the first planar graph that was discovered not to have a linear-area layout. Most recently, the structure of this graph has been used to develop a general framework for solving VLSI graph layout problems. Finally, the book develops techniques for proving lower bounds on the bisection width, crossing number, and layout area of a graph. These techniques significantly extend the power and range of previous methods.Researchers in the fields of VLSI, parallel computation, and graph theory will find this study of particular value; it is also accessible to anyone with an elementary knowledge of mathematics and computer science. The book is self-contained and presents in a unified and original manner many results scattered in the technical literature, while also covering new and fundamental results for the first time.


Out of Print ISBN: 9780262121040 156 pp. | 6 in x 9 in


$23.00 X | £17.99 ISBN: 9780262621786 156 pp. | 6 in x 9 in