Systolic Computations Book

	Series Editor's Preface
	Preface
	Acknowledgements
Ch. 1	VLSI models	1
1	Short history of the parallel processing	1
2	Physical opportunities and limits of VLSI	4
1	Basics of physics of semiconductor devices and integrated circuits	4
2	Restrictions and opportunities of VLSI technology	9
3	VLSI model	11
3	Algorithms for VLSI	16
1	Representation of algorithms by graphs	16
2	Representation of computational structures by graphs. The mapping problem	25
Ch. 2	The complexity of VLSI computations	29
1	VLSI complexity and complexity of algorithms	30
1	Integral measures of VLSI complexity	30
2	The information content of a function	32
3	Degree of transitivity of a function	41
4	Bounded arrays	43
5	Computations with registers and pebble games	45
2	Grid model of VLSI design	59
1	Area-time tradeoff for matrix multiplication	59
2	Area-time tradeoff for sign detection in the Residue Number System	66
3	Energy dissipation by computations	70
3	Complexity of parallel computations	79
1	Parallel algorithms and complexity	79
2	NC and RNC classes	81
3	Parallel algorithms in linear algebra	89
4	Parallel computations with polynomials and integers	95
5	Parallel algorithms for combinatorial problems	104
Ch. 3	Systolic algorithms and systolic processors	109
1	Systolic processing	109
1	Systolic processors for linear algebra	110
2	Systolic processors for digital signal processing	121
3	A systolic processor for linear programming problem	143
4	Systolic processors for mathematical physics	151
5	Systolic processors for graph problems	155
2	Mapping systolic algorithms on systolic processors	161
3	Graphs of systolic processors	169
1	Meshes	169
2	Shuffles	172
3	Trees	180
4	Embeddings of meshes, trees and shuffles into the hypercube	186
5	Universal graphs and systolic processors	195
6	Graph grammars and the generation of graphs	204
4	Iterations of systolic processors	207
1	Pipelining and the cut theorem	207
2	Asynchronous processors	210
3	Fault tolerance of systolic processors	220
Ch. 4	The systolic programming	225
1	Systolic processors and supercomputers	227
1	Systolic programming for parallel and vector computers	227
2	Simulation of SP by the Cray-1 like computer	231
2	Parallel programming languages	245
1	Features of parallel programming languages	245
2	Parallel programming languages	247
3	Systolic programming in UNIX environment	255
1	INMOS Transputers	255
2	Intel i860	259
3	UNIX system calls for parallel processing	260
4	Systolic versus parallel programming	265
	Appendix 1. Library of systolic algorithms	267
	Appendix 2. The grammar of the SPL	272
	References	277
	Index	313