Algorithms and Parallel Very Large Scale Integration Architectures II: Proceedings of the International Workshop, Chateau de Bonas, Gers, France, 3-6 June 1991

Since the emergence of VLSI, the relationship between the development of parallel algorithms and the design of special-purpose architecture has always been of major concern. The analysis of this relationship is the main topic of this book. Hardware and software issues closely depend upon one another and cannot be solved independently. Beyond the natural complexity of algorithm design, the designer has to face that of choosing the appropriate technology medium for its efficient realization. The dramatic developments in VLSI technology now offers extraordinary opportunities for implementing complex applications. As application specific/systems can offer 100 to 1000-fold improvements in cost/performance over general purpose computers on applications, they are attracting increasing attention in both academic and industrial communities. Highly specialized application-specific arrays of processors, which are the targeted architectures in this book, are extremely appealing. The papers in this volume give a thorough overview on current research in the areas of parallel algorithms, synthesis methods, VLSI architectures, and design tools.

Table of Contents:
Parts: 1. Parallel Algorithms. Orthogonal lattice algorithms for adaptive filtering and beam forming (J.G. McWhirter, I.K. Proudler). Mapping QR decomposition of a banded matrix on a 1D systolic array with data contraflow and pipelined functional units (M. Valero-Garcia et al.). Algorithms and architectures for recursive total least squares estimation (M. Moonen). Meshes with flexible redundancy (R. Melhem, J. Ramirez). Systolic generation of derangements (S.G. Akl et al.). A 2D toroidal systolic array for the knapsack problem (R. Andonov, F. Gruau). A parallel program for the recognition of P-invariant segments (J. Katoen, B. Schoenmakers). Parallel algorithms for finding connected, independent and total domination in interval graphs (G.S. Adhar, S. Peng). Parallel algorithms for color image quantization on hypercubes and meshes (F. Dehne, A. Rau-Chaplin). A parallel thinning algorithm using the bounding boxes technique (S. Ubeda). Time-varying system theory for computational networks (A.J. van der Veen, P. Dewilde). 2. Synthesis Methodologies. Generalized cycle shrinking (W. Shang et al.). Direct mapping of nested loops on piecewise regular processor arrays (D.J. Soudris et al.). From systolic to periodic array design (V. Van Dongen). Linear systolic arrays for matrix multiplication: comparisons of existing synthesis methods and new results (T. Risset). Refinement based algorithm mapping techniques for linear systolic arrays (R. Varadarajan, B. Ravichandran). Specifying control signals for one-dimensional systolic arrays by uniform recurrence equations (J. Xue, C. Lengauer). An improved systolic algorithm for the algebraic path problem (S. Rajopadhye). Synthesis of size-optimal toroidal arrays for the algebraic path problem (P. Clauss et al.). A programmable VLSI array with constant I/O pins (M.A. Aboelaze et al.). Array design methodologies for real-time signal processing in the Cathedral IV synthesis environment (F. Catthoor et al.). Signal analysis and signal transformations for ASIC regular array architecture synthesis (M. Van Swaaij et al.). 3. VLSI Architectures. Experience in the design of parallel processor arrays (P. Frison, D. Lavenier). On the use of most significant digit first arithmetic in the design of high performance DSP chips (J. McCanny). On line computing: a survey and some new results (J.M. Muller). Delays of on-line floating point operators in borrow-save representation (J. Duprat et al.). Nonlinear adaptive filtering algorithms for parallel and systolic implementation (F. Rauf, H.M. Ahmed). Distributed simulation of parallel VLSI architectures (D.K. Arvind). Transe: an experimental design tool (G. Durrieu et al.). Matrix multiplication on an associative string processor: application to image compression by Gabor expansion (F. Dufaux, M. Kunt). Loop unrolling for processors with instruction cache (H.P. Charles). Implementing cellular automata on the ArMen machine (K. Bouazza et al.). 4.