FAST ALGORITHMS AND THEIR IMPLEMENTATION ON SPECIALIZED PARALLEL COMPUTERS

J. Miklosko, M. Vajtersic and I. Vrto
Insitute of Technical Cybernetics
Slovak Academy of Sciences
Bratislava, Czechoslovakia


R. Klette
Central Institute of Cybernetics and Information Processes
Academy of Sciences of GDR
Berlin, GDR


North-Holland, Amsterdam, 1989

ISBN 0-444-70141-9   261 pages

orders to:
	Elsevier Science Publishers B.V.
	P.O. Box 103
	100 AC Amsterdam
	The Netherlands


CHAPTER 1 - 	FAST ALGORITHMS

1.1. Introduction
1.2 Principles of construction of fast parallel algorithms
1.3 Matrix multiplication on parallel computers
1.4 Algorithms for solving the Poisson equation on parallel computers
References

CHAPTER 2 - 	FAST PARALLEL ALGORITHMS FOR ASSOCIATIVE 
			COMPUTERS

2.1 Introduction
2.2 Associative memory and parallel associative processor
2.3 Logical algorithms for PAP
2.4 Numerical algorithms for PAP
2.5 Sorting on an associative computer
2.6 Parallel implmentation of Fast Fourier Transform
2.7 Parallel histogram algorithms for an associative parallel computer
2.8 Linear algebra examples on a parallel associative SIMD-type computer
References

CHAPTER 3 -	SYSTOLIC ALGORITHMS AND THEIR 
			IMPLEMENTATION ON SPECIALIZED PROCESSORS

3.1 Introduction
3.2 Characteristics of systolic arrays and algorithms
3.3 Numerical algorithms
3.4 Non-numerical algorithms
3.5 Complexity of systolic algorithms
3.6 Conclusion
References

CHAPTER 4 -	ALGORITHMS FOR PIPELINE PROCESSORS, MATRIX 
			PROCESSORS AND MULIPROCESSORS

4.1 Introduction
4.2 Pipeline vector computers and their algorithms
4.3. Matrix processors and their algorithms
4.4 Muliprocessor computers and their algorithms
References

CHAPTER 5 - 	FAST ALGORITHM FOR SOLUTION OF A SYSTEM OF 
			LINEAR ALGEBRAIC EQUATIONS ON SPECIALIZED 
			VLSI COMPUTERS

5.1 Introduction
5.2 Single VLSI chip computer: SLECI
5.3 VLSI chip with P-processors and cache memory: SLEC2
5.4 VLSI orthogonal pipeline vector processors: SLEC3r and SLEC3c
5.5 VLSI systolic array: SLEC4
5.6 Conclusion
References

CHAPTER 6 - 	LOWER TIME BOUNDS FOR SIMD-TYPE ALGORITHMS

6.1 Introduction
6.2 The general SIMD model
6.3 OFF-NETs and ON-NETs
6.4 Local, global and total data transfer measures
6.5 Local, global and total data dependence measures
6.6 Data transfer lemma and applications
References

Subject index