Parallel computers 2 : architecture, programming, and algorithms

Since the publication of the first edition, parallel computing technology has gained considerable momentum. A large proportion of this has come from the improvement in VLSI techniques, offering one to two orders of magnitude more devices than previously possible. A second contributing factor in the fast development of the subject is commercialization. The supercomputer is no longer restricted to a few well-established research institutions and large companies. A new computer breed combining the architectural advantages of the supercomputer with the advance of VLSI technology is now available at very attractive prices. A pioneering device in this development is the transputer, a VLSI processor specifically designed to operate in large concurrent systems. Parallel Computers 2: Architecture, Programming and Algorithms reflects the shift in emphasis of parallel computing and tracks the development of supercomputers in the years since the first edition was published. It looks at large-scale parallelism as found in transputer ensembles. This extensively rewritten second edition includes major new sections on the transputer and the OCCAM language. The book contains specific information on the various types of machines available, details of computer architecture and technologies, and descriptions of programming languages and algorithms. Aimed at an advanced undergraduate and postgraduate level, this handbook is also useful for research workers, machine designers, and programmers concerned with parallel computers. In addition, it will serve as a guide for potential parallel computer users, especially in disciplines where large amounts of computer time are regularly used. Cover 1 Half Title 2 Title Page 4 Copyright Page 5 Dedication 6 Contents 8 PREFACE 10 1 INTRODUCTION 18 1.1 History of parallelism and supercomputing 19 1.2 Classification of designs 70 1.3 Characterisation of performance 98 2 PIPELINED COMPUTERS 134 2.1 Selection and comparison 134 2.2 The CRAY X-MP and CRAY-2 135 2.3 The CDC CYBER 205 and ETA[sup(10)] 172 2.4 Japanese vector computers: Fujitsu, Hitachi, NEC 207 2.5 The FPS AP-120B, FPS164 (M140, M30), 264 (M60), 164/MAX (M145) 223 3 MULTIPROCESSORS AND PROCESSOR ARRAYS 262 3.1 The limitations of pipelining 262 3.2 The alternative of replication 263 3.3 Switching networks 276 3.4 An historical perspective: ICL DAP, BSP, HEP 302 3.5 Replication—a future with VLSI: AMT DAP, RPA, Transputer 339 4 PARALLEL LANGUAGES 387 4.1 Introduction 387 4.2 Implicit parallelism and vectorisation 392 4.3 Structure parallelism: DAP FORTRAN, FORTRAN 8X, CMLISP 400 4.4 Process parallelism: OCCAM 435 4.5 Techniques for exploiting parallelism 445 5 PARALLEL ALGORITHMS 449 5.1 General principles 449 5.2 Recurrences 465 5.3 Matrix multiplication 482 5.4 Tridiagonal systems 487 5.5 Transforms 506 5.6 Partial differential equations 541 6 TECHNOLOGY AND THE FUTURE 568 6.1 Characterisation 570 6.2 Bipolar technologies (TTL , ECL, I[sup(2)]L) 573 6.3 MOS technologies (NMOS and CMOS) 574 6.4 Scaling technologies 578 6.5 The problems with scaling 579 6.6 System partitioning 587 6.7 Wafer-scale integration 592 6.8 The last word 597 APPENDIX 598 REFERENCES 604 INDEX 628