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.
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