Newsgroups: comp.parallel From: banerjee@crhc.uiuc.edu (Prithviraj Banerjee) Subject: New Book: "Parallel Algorithms for VLSI CAD" Organization: University of Illinois at Urbana-Champaign Date: Sun, 10 Jul 1994 19:14:47 GMT Message-ID: NEW BOOK INFORMATION TITLE: Parallel Algorithms For VLSI Computer-Aided Design AUTHOR: Prithviraj Banerjee YEAR: 1994 PUBLISHER: Prentice Hall, Englewoods Cliffs, NJ-07632 PRICE: $60.00 ORDER NUMBER: 01583-4 ISBN NUMBER: 0-13-015835-6 ABOUT THE BOOK: Parallel computing is becoming an increasing cost effective and affordable means for providing enormous computing power. Workstations are currently using parallel processing technology, and will use it even more in the future. It is widely believed while it is relatively easy to build massively parallel processing (MPP) machines whose peak performance will be GFLOPS, it is not always easy to harness the computational power effectively. Therein lies the challenge: design of good parallel algorithms that can efficiently use the hardware resources to get the maximum performance. This book discusses the use of parallel processing for solving problems in a growing application area whose computational requirements are enormous: VLSI CAD applications. While numerous books exist on general parallel algorithms for regular matrix problems or graph theory problems, they are mostly theoretical in nature. This book discusses PRACTICAL parallel algorithms for shared memory MIMD, message passing MIMD, and SIMD parallel machines. The first two chapters of the book provide a detailed introduction to the field of parallel computing: architectures, algorithms, and programming and forms the groundwork for writing parallel programs for parallel machines. The remaining chapters (3-9) deal with different CAD applications, placement, routing, layout verification and analysis, circuit simulation, logic simulation, test generation and fault simulation, and logic synthesis and verification. For each CAD application, the problem is first clearly formulated, then different sequential approaches for solving the problem are discussed. Subsequently, for each approach, the corresponding shared memory MIMD, message passing MIMD and SIMD parallel algorithms are presented. Actual experimental results obtained with these parallel algorithms on real parallel machines are reported. The advantages and disadvantages of choosing each of these approaches are discussed with results of case studies on specific applications. Each chapter ends with a complete bibliography of the area; the book has over 400 references in the field. PROSPECTIVE BUYERS OF BOOK: 1) Professors and graduate students in electrical engineering and computer science, who are knowledgeable in VLSI CAD area, but wish to learn about parallel processing to accelerate own applications, or to look at potential research areas, since there is a detailed bibliography. 2) Professors and graduate students in electrical engineering and computer science, who are knowledgeable about the parallel processing area, but who currently solve toy problems, but wish to learn about exciting new application area which is related to person's field. 3) Graduate level courses can be taught on this book's topic at many universities. 4) Engineers in VLSI CAD companies, who wish to learn how to use parallel processing technology for their applications. 5) Engineers in parallel computer companies, trying to develop useful software for marketing parallel machines, or to benchmark machines, or redesign parallel machines. OUTLINE OF BOOK: Chapter 1: INTRODUCTION. Provides an introduction to VLSI CAD, an introduction to parallel processing, and gives an overview of book. Chapter 2: PARALLEL ARCHITECTURES AND PROGRAMMING. Provides an introduction to shared memory MIMD, message passing MIMD, and SIMD parallel architectures, and parallel programming. Describes actual parallel programming of three simple applications for each machine type. Chapter 3: PLACEMENT AND FLOORPLANNING. Provides an introduction to placement and floorplanning problems. Describes different sequential approaches to problems, such as pairwise interchange, simulated annealing, simulated evolution, genetic algorithms, hierarchical decomposition. For each approach, describe shared memory MIMD, message passing MIMD and SIMD parallel algorithms. Chapter 4: DETAILED AND GLOBAL ROUTING. Provides an introduction to detailed and global routing problems. Describes different sequential approaches to detailed routing problems, such as maze routing, channel routing, to global routing approaches such as graph expansion, iterative improvement, and hierarchical decomposition. For each approach, describe shared memory MIMD, message passing MIMD and SIMD parallel algorithms. Chapter 5: LAYOUT VERIFICATION AND ANALYSIS. Provides an introduction to design rule checking, netlist extraction and parameter extraction problems. Describes different sequential approaches to problems, such as data decomposition, functional decomposition, hierarchical decomposition. For each approach, describe shared memory MIMD, message passing MIMD and SIMD parallel algorithms. Chapter 6: CIRCUIT SIMULATION. Provides an introduction to the circuit simulation problem, and presents different approaches to solve the problem such as direct methods, nonlinear relaxation methods and waveform relaxation methods. For each approach, describe shared memory MIMD, message passing MIMD and SIMD parallel algorithms. Chapter 7: LOGIC AND BEHAVIORAL SIMULATION. Provides an introduction to the logic simulation problem and outlines various approaches to parallel logic simulation such as data parallelism, functional parallelism, circuit parallelism, synchronous and asynchronous event driven simulation, conservative and optimistic asynchronous parallel event driven simulation. Provides an introduction to behavioral simulation using VHDL, and discusses approaches to parallelize behavioral simulation. For each approach, describe shared memory MIMD, message passing MIMD and SIMD parallel algorithms. Chapter 8: TEST GENERATION AND FAULT SIMULATION. Provides an introduction to the test generation problem and outlines various approaches to parallelism, such as fault parallelism, heuristic parallelism, AND-parallel, OR-parallel and circuit parallel approaches. Provides introduction to the fault simulation problem, and outlines various parallelism approaches, such as fault parallel, input pattern parallel, and circuit parallel. For each approach, describe shared memory MIMD, message passing MIMD and SIMD parallel allgorithms. Chapter 9: LOGIC SYNTHESIS AND VERIFICATION. Provides an introduction to the logic synthesis problem and outlines various approaches to parallelism, such as circuit parallel, two-level minimization, multilevel minimization using tranduction and MIS approaches. Provides introduction to the logic verification problem, and outlines various parallelism approaches, such as tautology checking, and implicit enumeration. For each approach, describe shared memory MIMD, message passing MIMD and SIMD parallel allgorithms. Chapter 10: CONCLUSIONS AND FUTURE DIRECTIONS. Summarizes state of the art in parallel CAD. Identifies the problems facing the field, and points to some promising solutions. Gives overview of ProperCAD project on portable, parallel algorithms for CAD. ABOUT THE AUTHOR: Prithviraj Banerjee received his B.Tech. degree in Electronics and Electrical Engineering from the Indian Institute of Technology, Kharagpur, India, in August 1981, and the M.S. and Ph.D degrees in Electrical Engineering from the University of Illinois at Urbana-Champaign in December 1982 and December 1984. He is currently Professor of Electrical and Computer Engineering, and Director of Computational Science and Engineering at the University of Illinois at Urbana-Champaign. His research interests are in parallel algorithms for VLSI design automation, and distributed memory parallel architectures, is the author of over 140 papers in these areas. He has supervised 10 Ph.D. theses so far. He has been working on parallel algorithms for numerous VLSI design automation applications for the last 10 years. Dr. Banerjee was the recipient of the President of India Gold Medal from the Indian Institute of Technology, Kharagpur, in 1981, the IBM Young Faculty Development Award in 1986, the National Science Foundation's Presidential Young Investigators' Award in 1987, the IEEE Senior Membership in 1990, the Senior Xerox Research Award in 1992, and the University Scholar award >from the University of Illinois in 1993. Dr. Banerjee has served on the program and organizing committees of numerous conferences such as International Parallel Processing Symposia, the International Symposia on Computer Architecture, the International Symposium on VLSI Design, and the Fault Tolerant Computing Symposia. He is also the editor of the IEEE Transactions on VLSI Systems, and the Journal of Parallel and Distributed Computing.