scientific article; zbMATH DE number 3858396
algorithmsautomatic design systemscompilationintegrated circuitslayout algorithmslower bounds for area and timeparallel algorithmsprocessor networkssystolic algorithmsVLSI circuitsVLSI design
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)
This new monograph was probably the most difficult to write. The domain involved is quite prodigious and new. The author had to select some of the typical issues in such a way that the balance of the details could be filled in, and he had to make understandable areas that lack in specific formalism. We thus appreciate this first fifth generation Computer Science text despite some inadvertencies and our feeling that some parts could have been better written. The (declared) purpose of the book is the investigation of algorithms and the way they can be presented as integrated circuits. We are lead to a global understanding of the field in nine chapters and an Appendix, starting with VLSI circuits and continuing with layout algorithms, processor networks and parallel algorithms. Chapter one is dedicated to the basic of very large scale integrated circuit design (rudiments of the underlying electronics and the Mead-Conway design rules for NMOS circuits) and to the introduction of specific concepts and terminology (clock cycle, timing calculation, implementation area, layout, a.s.o.). The grid model for VLSI circuits is also described. In the second chapter principal methods for finding lower bounds for area and time are presented. These are based on a fooling argument which uses the (formalized) notions of a problem, information content of a problem and crossing sequence. In Chapter three the level of abstraction is raised and layout algorithms for different processor network organizations are discussed. Raising once more the level of abstraction, Chapter four presents a language that could be used to describe parallel algorithms executed by networks of processors (this language has an explicit construction for those parts of an algorithm that must have a synchronized execution). New types of processor networks are analyzed, together with the most suitable algorithms that could be realized on them. Chapter five deals with systolic algorithms and mechanical ways for converting nonsystolic algorithms to systolic ones (more generally: changing the timing of data flow in processor networks). In Chapter six other organizations for processor networks are discussed, namely those for which the wire area dominates the processor area. The seventh chapter deals with the problem of automating the VLSI design process. Existing general purpose design systems are briefly presented (languages, facilities, power, applicability level on the way from algorithm to chip). The optimum compilation from a higher level language into a lower one and and the state of the art in silicon compilation are treated in more detail in Chapter eight. Other tools (beside compilation) used in automatic design systems are described in Chapter nine. Every chapter contains interesting examples and ends with valuable exercises and bibliography notes.
- Unifying computers and dynamical systems using the theory of synchronous concurrent algorithms
- The performance of multilective VLSI algorithms
- Topological transformations as a tool in the design of systolic networks
- Tight chip area lower bounds for discrete Fourier and Walsh-Hadamard transformations
- On the maximum edge length in VLSI layouts of complete binary trees
- Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs
- Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture
- Distributed algorithms in synchronous broadcasting networks
- A logic-topological calculus for the construction of integrated circuits. I
- On fault tolerant routings in general networks
- Area-time lower-bound techniques with applications to sorting
- A minimum-area circuit for -selection
- Multiple cuts, input repetition, and VLSI complexity
- Algorithms for the compilation of regular expressions into PLAs
- Optimal three-dimensional layouts of complete binary trees
- Bit serial addition trees and their applications
- Communication complexity of convex optimization
- Succinct representation of regular sets using gotos and Boolean variables
- On problem transformability in VLSI
- River routing in VLSI
- On the VLSI complexity of some arithmetic and numerical problems
- Graph graphics: Theory and practice
- Tight chip area lower bounds for string matching
- On totalistic systolic networks
- On O(\(\sqrt{n})\) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors
- Set containment inference and syllogisms
- Emulating digital logic using transputer networks (very high parallelism \(=\) simplicity \(=\) performance)
- Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
- Integer summing algorithms on reconfigurable meshes
- Almost exact minimum feedback vertex set in meshes and butterflies
- The complexity of short two-person games
- Computing convexity properties of images on a pyramid computer
- Parallel computation of distance transforms
- Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays
- Optimal geometric algorithms for digitized images on fixed-size linear arrays and scan-line arrays
- On graphs preserving rectilinear shortest paths in the presence of obstacles
- A tight upper bound for the number of intersections between two rectangulars paths
- Nonlinear lower bounds on the number of processors of circuits with sublinear separators
- Special characteristics of programming for VLIW computers (review)
- Decoupling the dimensions of a system of affine recurrence equations
- Automatic verification of a class of systolic circuits
- Efficient algorithms for the largest rectangle problem
- Lower bounds on the area complexity of Boolean circuits
- Stirling networks: A versatile combinatorial topology for multiprocessor systems
- An asymptotic equality for the number of necklaces in a shuffle-exchange network
- Efficient VLSI fault simulation
- Asymptotic component densities in programmable gate arrays realizing all circuits of a given size
- A new model for large memories
- A note on optimal area algorithms for upward drawings of binary trees
- VLSI algorithms and architectures. 3rd Aegean workshop on computing, AWOC '88, Corfu, Greece, June 28-July 1, 1988. Proceedings
- Special volume: VLSI
- Path optimization for graph partitioning problems
- A fast and simple Steiner routing heuristic
- Fast consensus in networks of bounded degree.
- A near-optimal Manhattan channel router for a class of nets with the shift-right-one pattern
- Drawing graphs in two layers
- Using domain decomposition to find graph bisectors
- From regular expressions to DFA's using compressed NFA's
- Edge ranking of graphs is hard
- Bisecting de Bruijn and Kautz graphs
- On the communication complexity of Lipschitzian optimization for the coordinated model of computation
- Dense edge-disjoint embedding of complete binary trees in interconnection networks
- A finite automata approach to modeling the cross product of interconnection networks.
- Coverings that preserve sense of direction
- Algorithms for the fixed linear crossing number problem
- Alternative evaluation functions for the cyclic bandwidth sum problem
- Finding a largest rectangle inside a digital object and rectangularization
- A hybrid breakout local search and reinforcement learning approach to the vertex separator problem
- Representing graph families with edge grammars
- Trace theory and VLSI design
- On the complexity of planar Boolean circuits
- Symmetrizing a Hessenberg matrix: Designs for VLSI parallel processor arrays
- Applications of the crossing number
- Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
- Embedding-preserving rectangle visibility representations of nonplanar graphs
- Separator-based graph embedding into multidimensional grids with small edge-congestion
- Constant-slowdown simulations of normal hypercube algorithms on the butterfly network
- Multi-way graph partition by stochastic probe
- Two-page book embedding of trees under vertex-neighborhood constraints
- Approximating the fixed linear crossing number
- An analysis of some linear graph layout heuristics
- Optimal systolic array algorithms for tensor product
- Continuous quadratic programming formulations of optimization problems on graphs
- The balanced binary tree technique on mesh-connected computers
- Parallel merging on the instruction systolic array
- Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges
- Algorithms and bounds for L-drawings of directed graphs
- Fast sequential and parallel algorithms for finding the largest rectangle separating two sets
- Wafer-Scale Integration of Systolic Arrays
- A unified framework for off-line permutation routing in parallel networks
- Tight bounds for oblivious routing in the hypercube
- ON SIMULATING A CLASS OF PARALLEL ARCHITECTURES
- scientific article; zbMATH DE number 4135870 (Why is no real title available?)
- scientific article; zbMATH DE number 3898774 (Why is no real title available?)
- Optimal Allocation of Area for Single-Chip Computations
- scientific article; zbMATH DE number 3919826 (Why is no real title available?)
- scientific article; zbMATH DE number 3919827 (Why is no real title available?)
- scientific article; zbMATH DE number 3926249 (Why is no real title available?)
- scientific article; zbMATH DE number 3959290 (Why is no real title available?)
- scientific article; zbMATH DE number 3990911 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3326832)