PREFACE This book aims at giving an impression of the way current research in algorithms, ar- chitectures and compilation for parallel systems is evolving. It is focused especially on domains where embedded systems are required, either oriented to application-specific or programmable realisations. These are crucial in domains such as audio, telecom, instrumen- tation, speech, robotics, medical and automotive processing, image and video processing, TV, multimedia, radar and sonar. Also the domain of scientific, numerical computing is covered. The material in the book is based on the author contributions presented at the 3rd Inter- national Workshop on Algorithms and Parallel VLSI Architectures, held in Leuven, Au- gust 29-31, 1994. This workshop was partly sponsored by EURASIP and the Belgian NFWO (National Fund for Scientific Research), and organized in co-operation with the IEEE Benelux Signal Processing Chapter, the IEEE Benelux Circuits and Systems Chap- ter, and INRIA, France. It was a continuation of two previous workshops of the same name which were held in Pont-&-Mousson, France, June 1990 1, and Bonas, France, June 1991 2. All of these workshops have been organized in the frame of the EC Basic Research Actions NANA and NANA2, Novel parallel Algorithms for New real.time Architectures, sponsored by the ESPRIT program of Directorate XIII of the European Commission. The NANA Contractors are IMEC, Leuven, Belgium (F. Catthoor), K.U. Leuven, Leuven, Bel- gium (J. Vandewalle), ENSL, Lyon, France (Y. Robert), TU Delft, Delft, The Netherlands (P. Dewilde and E. Deprettere), IRISA, Rennes, France (P. Quinton). The goal within these projects has been to contribute algorithms suited for parallel architecture realisation on the one hand, and on the other hand design methodologies and synthesis techniques which address the design trajectory from real behaviour down to the parallel architecture realisatlon of the system. As such, this is clearly overlapping with the scope of the workshop and the book. An overview of the main results presented in the different chapters combined with an attempt to structure all this information is available in the introductory chapter. We expect this book to be of interest in academia, both for detailed descriptions of research results as well as for the overview of the field given here, with many important but less widely known issues which must be addressed to arrive at practically relevant results. In addition, many authors have considered applications and the book is intended to reflect this fact. The real-life applications that have driven the research are described in several vi ecaferP contributions, and the impact of their characteristics on the methodologies is assessed. We therefore believe that the book will be of interest also to senior design engineers and CAD managers in industry, who wish either to anticipate the evolution of commercially available design tools over the next few years, or to make use of the concepts in their own research and development. It has been a pleasure for us to organize the workshop and to work together with the authors to assemble this book. We feel amply rewarded with the result of this co-operation, and we want to thank all the authors here for their effort. We have spent significant effort in trying to deliver as much as possible consistent material, by careful editing. The international aspect has allowed us to group the results of many research groups with a different background and "research culture," which si felt to be particularly enriching. We would be remiss not to thank Prof. L. Thiele of Universit~t des Saarlandes, Saarbriicken, Germany, who was an additional member to the workshops organizing committee, and F. Vanpoucke who was a perfect workshop managing director and also did a great job in collecting and processing the contributions to this book. We hope that the reader will find the book useful and enjoyable, and that the results presented will contribute to the continued progress of the field of parallel algorithms, ar- chitectures and compilation. Leuven, October ,t~991 eht editors References 1 E.Deprettere, A.Van der Veen (eds.), "Algorithms and Parallel VLSI Architectures", Elsevier, Amsterdam, 1991. 2 P.Quinton and Y.Robert (eds.), "Algorithms and Parallel VLSI Architectures II", El- sevier, Amsterdam, 1992. smhtiroglA dna Parallel VLSI Architectures III M. Moonen dna F. Catthoor )srotidE( (cid:14)9 1995 Elsevier Science B.V. All rights reserved. ALGORITHMS AND PARALLEL VLSI ARCHITECTURES F. CATTHOOtt IMEC Kapeldreef 57 800I Leuven, Belgium [email protected] M. MOONEN ESAT Katholieke Universiteit Leuven 800I Leuven, Belgium Marc. Moonen @esat.kuleu ven. .ca eb ABSTRACT. In this introductory chapter, ew will summarize the main contributions of the chapters collected in this book. Moreover, the topics addressed in these chapters will be linked to the major research trends in the domain of parallel algorithms, architectures and compilation. 1 STRUCTURE OF BOOK The contributions to the workshop and the book can be classified in three categories: .1 Parallel Algorithms: The emphasis lies on the search for more efficient and inherently parallelisable algorithms for particular computational kernels, mainly from linear al- gebra. The demand for fast matrix computations has arisen in a variety of fields, such as speech and image processing, telecommunication, radar and sonar, biomedi- cal signal processing, and os on. The work si motivated by the belief that preliminary algorithmic manipulations largely determine the success of, e.g, a dedicated hardware design, because radical algorithmic manipulations and engineering techniques are not easily captured, e.g, in automatic synthesis tools. Most of the contributions here deal with real-time signal processing applications, and in many cases, the research on these algorithms si already tightly linked to the potential parallel realisation options to be exploited in the architecture phase. .F Catthoor and M. Moonen .2 Parallel Architectures: Starting from an already paraUelized algorithm or a group of algorithms (a target application domain), the key issue here is to derive a particular architecture which efficiently realizes the intended behaviour for a specific technology. In this book, the target technology will be CMOS electronic circuitry. In order to achieve this architecture realisation, the detailed implementation characteristics of the building blocks - like registers/memories, arithmetic components, logic gates and connection networks- have to be incorporated. The end result is an optimized net- list/layout of either primitive custom components or of programmable building blocks. The trend of the last years is to mix both styles. So more custom features are embedded in the massively parallel programmable machines, especially in the storage hierarchy and the network topologies. In addition, (much) more flexibility is built into the custom architectures, sometimes leading to highly-flexible weakly-parallel processors. The path followed to arrive at such architectures is the starting point for the formalisation into reusable compilation methodologies. .3 Parallel Compilation: Most designs in industry suffer from increasing time pressure. As a result, the methods to derive efficient architectures and implementations have to become more efficient and less error-prone. For this purpose, an increasing amount of research is spent on formalized methodologies to map specific classes of algorithms (ap- plication domain) to selected architectural templates (target style). In addition, some steps in these methodologies are becoming supported by interactive or automated design techniques (architectural synthesis or compilation). In this book, the empha- sis will be on modular algorithms with much inherent parallelism to be mapped on (regular) parallel array styles. Both custom (application-specific) and programmable (general-purpose) target styles Uiw be considered. These categories correspond to the different parts of the book. An outline of the main contributions in each part is given next, along with an attempt to capture the key-features of the presented research. 2 PARALLEL ALGORITHMS In recent years, it has become clear that for many advanced real-time signal processing and adaptive systems and control applications the required level of computing power is well beyond that available on present-day programmable signal processors. Linear algebra and matrix computations play an increasingly prominent role here, and the demand for fast matrix computations has arisen in a variety of fields, such as speech and image processing, telecommunication, radar and sonar, biomedical signal processing, and so on. Dedicated architectures then provide a means of achieving orders of magnitude improvement in per- formance, consistent with the requirements. However, past experience has shown that preliminary algorithmic manipulations largely determine the success of such a design. This has led to a new research activity, aimed at tailoring algorithmic design to architectural design and vice versa, or in other words deriving numerically stable algorithms which are suitable for parallel computation. At this stage, there is also interaction already with the parallel architecture designers who