Algorithm Engineering for Integral and Dynamic Problems

ISBN-13: 9789056993283 / Angielski / Twarda / 2001 / 280 str.

Lucia Rapanotti; Rapanotti Rapanotti

Opis

Algorithm engineering allows computer engineers to produce a computational machine that will execute an algorithm as efficiently and cost-effectively as possible given a set of constraints, such as minimal performance or the availability of technology. Addressing algorithm engineering in a parallel setting, regular array syntheses offer powerful computation and embody best practice, but often face the criticism that they are applicable only to restricted classes of algorithms.
Algorithm Engineering for Integral and Dynamic Problems reviews the basic principles of regular array synthesis and shows how to extend its use into classes of algorithms traditionally viewed to be beyond its domain of application. The author discusses the transformation of the initial algorithm specification into a specification with data dependencies of increased regularity in order to obtain corresponding regular arrays by direct application of the standard mapping techniques. The book includes a review of the basic principles of regular array synthesis followed by applications of these techniques to well-known algorithms, concluding with numerous case studies to illustrate the methods.
Researchers and practitioners in algorithm engineering will find that this text significantly extends their understanding of the applications of regular array synthesis and regular array processors beyond the traditionally narrow field of relevance.

Spis treści

LIST OF FIGURES
LIST OF TABLES
PREFACE
ACKNOWLEDGEMENTS
INTRODUCTION
Algorithm Specialization
Regular Array Synthesis
From Affine to Integral Problems
From Static to Dynamic Problems
Outlines of the Book
REGULAR ARRAY SYNTHESIS
Basic Design Steps
Euclidean Synthesis
Regularization
A Brief Survey
Summary
INTEGRAL RECURRENCE EQUATIONS
Integral Data Dependencies
Regularization
Regularization and Affine Scheduling
Summary
DYNAMIC RECURRENCE EQUATIONS
Inputs and Indexed Variables
Dynamic Data Dependencies
Dynamic Data Dependencies in Euclidean Synthesis
Regularization
Regularization and Affine Scheduling
Summary
CASE STUDIES
Cyclic Reduction
N Points FIR Filter for M-to-1 Decimation
Knapsack Problem
Gaussian Elimination with Partial Pivoting
Summary
CONCLUSIONS
Further Work
APPENDIX A: NOTATION
APPENDIX B: GRAPH THEORY
Graphs
Connectivity Relations
Graph Operations
APPENDIX C: CONVEX SETS AND POLYHEDRA
Combinations
Affine Sets and Transformations
Convex Sets
Cones
Recession Cone and Unboundedness
Polyhedral Convex Sets
Duality
Separating Hyperplane Theorem
Other Results
APPENDIX D: ASPECTS OF LINEAR ALGEBRA
Elementary Row Operations and Elementary Matrices
Hermite Normal Form
Integer Elementary Row Operations
Unimodularity
Echelon Form
Linear Functional and Duality
Annihilators
Algorithmic Issues
BIBLIOGRAPHY
INDEX

O autorze

Lucia Rapanotti