Algorithm engineering for integral and dynamic problems (Q2703351)

The book addresses algorithmic engineering in a parallel setting, for regular array processors. It focuses on a powerful engineering technique -- regular array synthesis -- which simultaneously embody best practice and are well-founded in mathematical theories. A criticism that is often leveled against regular array synthesis is that it can only be applied to restricted classes of algorithms. The author shows how regular array synthesis can be extended to include classes of algorithms traditionally thought to be beyond its domain of application.NEWLINENEWLINENEWLINEThe book is organized as follows. Chapter 1 is an introduction. In Chapter 2 one describes the design process in regular array synthesis and one introduces some basic definitions and properties. Also one discusses technical issues related to the regularization of nonuniform data dependencies as the basis for the development of the following chapters. In Chapter 3 integral problems and their regularization are introduced. The relation between integral and affine problems is explored and the advantages and limitations of the approach are discussed. In Chapter 4 the step from static to dynamic problems is formalized and a subclass of dynamic problems (for which a systematic regularization technique is provided) is presented. In Chapter 5 a number of case studies to illustrate the application of the proposed technique to well-known problems from the literature is given. Chapter 6 is devoted to some possible developments of the work and a number of conclusions. In the Appendices (A, B, C, D) most of the mathematical notations, definitions and properties upon which the book is based are included.NEWLINENEWLINENEWLINEThe book is aimed at researchers and practitioners in the field of algorithmic engineering. In this book they can find a comprehensive treatment of algorithm transformations for the derivation of regular array processors.