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