Издательство Cambridge University Press, 1990, -443 pp.
The development of VLSI fabrication technology has resulted in a wide range of new ideas for application specific hardware and computer architectures, and in an extensive set of significant new theoretical problems for the design of hardware. The design of hardware is a process of creating a device that realises an algorithm, and many of the problems are conceed with the nature of algorithms that may be realised. Thus fundamental research on the design of algorithms, programming and programming languages is directly relevant to research on the design of hardware. And conversely, research on hardware raises many new questions for research on software. These points are discussed at some length in the introductory chapter. .
The papers that make up this volume are conceed with the theoretical foundations of the design of hardware, as viewed from computer science. The topics addressed are the complexity of computation; the methodology of design; and the specification, derivation and verification of designs. Most of the papers are based on lectures delivered at our workshop on Theoretical aspects of VLSI design held at the Centre for Theoretical Computer Science, University of Leeds in September 1986. We wish to express our thanks to the contributors and referees for their cooperation in producing this work.
Introduction.
Theoretical foundations of hardware design.
Part 1 Formal methods and verification.
A mechanized proof of correctness of a simple counter.
A formal model for the hierarchical design of synchronous and systolic algorithms.
Verification of a systolic algorithm in process algebra.
Part 2 Theory and methodology of design.
Formal specification of a digital correlator.
Describing and reasoning about circuits using relations.
The synthesis of VLSI signal processors: theory and example.
Part 3 Methods of circuits and complexity theory.
The prioritiser experiment: estimation and measurement of computation time in VLSI.
Superpolynomial lower bounds on monotone network complexity.
The development of VLSI fabrication technology has resulted in a wide range of new ideas for application specific hardware and computer architectures, and in an extensive set of significant new theoretical problems for the design of hardware. The design of hardware is a process of creating a device that realises an algorithm, and many of the problems are conceed with the nature of algorithms that may be realised. Thus fundamental research on the design of algorithms, programming and programming languages is directly relevant to research on the design of hardware. And conversely, research on hardware raises many new questions for research on software. These points are discussed at some length in the introductory chapter. .
The papers that make up this volume are conceed with the theoretical foundations of the design of hardware, as viewed from computer science. The topics addressed are the complexity of computation; the methodology of design; and the specification, derivation and verification of designs. Most of the papers are based on lectures delivered at our workshop on Theoretical aspects of VLSI design held at the Centre for Theoretical Computer Science, University of Leeds in September 1986. We wish to express our thanks to the contributors and referees for their cooperation in producing this work.
Introduction.
Theoretical foundations of hardware design.
Part 1 Formal methods and verification.
A mechanized proof of correctness of a simple counter.
A formal model for the hierarchical design of synchronous and systolic algorithms.
Verification of a systolic algorithm in process algebra.
Part 2 Theory and methodology of design.
Formal specification of a digital correlator.
Describing and reasoning about circuits using relations.
The synthesis of VLSI signal processors: theory and example.
Part 3 Methods of circuits and complexity theory.
The prioritiser experiment: estimation and measurement of computation time in VLSI.
Superpolynomial lower bounds on monotone network complexity.