E-Book Content
Architecture of High Performance Computers Volume II
R. N. Ibbett and N. P. Topham Department of Computer Science University of Edinburgh Edinburgh Scotland ER9 3JZ
Architecture of High Performance Computers
Volume II i\rray processors and multiprocessor systems
Springer Science+Business Media, LLC
© Roland N. Ibbett and Nigel P. Topham 1989 Original1y published by Springer Verlag New York in 1989. All rights reserved. No reproduction, copy or transmission of this publication may be made without written permission. First published 1989
Published by MACMILLAN EDUCATION LTD Houndmills, Basingstoke, Hampshire RG21 2XS and London Companies and representatives throughout the world ISBN 978-1-4899-6703-9 ISBN 978-1-4899-6701-5 (eBook) DOI 10.1007/978-1-4899-6701-5
Contents
Preface 1 Introduction 1.1 Parallel hardware structures . 1.2 Taxonomy of parallel architectures 1.3 Summary of the book . . . .
viii 1 2 3 4
2 Array-processor Architecture 2.1 Design Issues . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Array processor organisation .. . . . . . . . 2.1.2 ILLIAC IV - a distributed-memory machine 2.1.3 BSP - a shared-memory machine 2.2 Performance issues 2.2.1 Scalability. 2.3 Summary . . . . .
6 7 8 11 12 15 20 21
3 Interconnection Networks 3.1 Characteristics of interconnection structures . 3.2 Network routing functions 3.3 Network topology . . . . . 3.3.1 Static networks .. 3.3.2 Dynamic networks 3.3.3 Multi-stage networks . 3.4 Summary . . . . . . . . . . .
22 23 24
4 Practical Array Architectures 4.1 The ICL DAP . . . . . . . . 4.1.1 System architecture 4.1.2 Array architecture 4.1.3 PE architecture . 4.1.4 Instruction set 4.1.5 Performance .. 4.1.6 The DAP-3 . . . 4.2 The Connection Machine 4.2.1 System architecture 4.2.2 Processing elements
43 43 44 45
29
31 35 36 42
48 52 56 58 58 59 61
Contents
vi
4.3
4.2.3 The router Summary .. . . .
5 Array Processor Software 5.1
5.2
5.3
Array processing languages 5.1.1 DAP Fortran . . . . 5.1.2 CM-Lisp . . . . . . . Algorithms for array processors 5.2.1 Partial differential equations 5.2.2 Minimum path length Summary . . . . . . . . . .
6 Multiprocessor Architecture 6.1
6.2
6.3
Design issues . . . . . . . . . . . . . . . 6.1.1 Categories of MIMD architecture 6.1.2 Granularity .. 6.1.3 Load balancing . . . . . Performance issues . . . . . . . 6.2.1 Speed-up and efficiency 6.2.2 Extensibility . . . . . . 6.2.3 Reliability and fault-tolerance . Summary . . . . . . . . . . . . .
7 Shared-memory Multiprocessors 7.1
7.2
7.3
7.4
7.5
Shared-memory architecture . . . . . . . . . . . . 7.1.1 Sequential-access shared-memory systems 7.1.2 Highly-connected shared-memory systems 7.1.3 Scalable multiprocessors The Sequent Balance 8000 . 7.2.1 Cache consistency .. . 7.2.2 The SLIC . . . . . . . . 7.2.3 The SB8000 system bus C.mmp . . . . . . . . . . . . . 7.3.1 The small address problem 7.3.2 Locks and synchronisation. The BBN Butterfly . . . . . . . . . 7.4.1 Overview of the Butterfly . 7.4.2 Butterfly processing nodes . 7.4.3 The Butterfly switch 7.4.4 Performance Summary . . . . . . . . . .
63 66 67 67 68 70 73 75 79 82
83 86 88 89 90 91
96 .104 .105 .108
109 .109 · 111 .115 .116 .116 .118 .118 .121 .122 .124 · 125 · 127 · 127 · 128 .130 .132 .140
Contents
vii
141
8 Message-passmg Multiprocessors 8.1 Design issues for message-passing architectures 8.2 Transputer-based systems . . . . . . . . . . 8.2.1 Architecture of the T414 . . . . . . . . . 8.2.2 The T800 floating point transputer .. . 8.2.3 Constructing multi-transputer systems . 8