Lucia Rapanotti
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.
|
* Presents the application of regular array synthesis for regular array processors used to make efficient computational machines
* Reviews the basic principles of regular array synthesis
* Illustrates well-known algorithms using the author's techniques for regular array synthesis
* Contains numerous case studies to illustrate the concepts in practice
* Discusses integral recurrence equations, dynamic recurrence equations, regularization and affine scheduling, and dynamic data dependencies
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. Regular Array Synthesis. Integral Recurrence Equations. Dynamic Recurrence Equations. Case Studies. Conclusions. Appendix A: Notation. Appendix B: Graph Theory. Appendix C: Convex Sets and Polyhedra. Appendix D: Aspects of Linear Algebra. Bibliography. Index.
Algorithm engineering allows to produce a computational machine that executes an algorithm efficiently and cost-effectively. Addressing this, regular array synthesis offers powerful computation and embody best practice. This book reviews the principles of regular array synthesis and shows how to extend its use into classes of algorithms.
Inhaltsverzeichnis
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
Klappentext
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.
