A Parallel Algorithm Synthesis Procedure for High-Performance Computer Architectures
Despite five decades of research, parallel computing remains an exotic, frontier technology on the fringes of mainstream computing. Its much-heralded triumph over sequential computing has yet to materialize. This is in spite of the fact that the processin
- PDF / 9,021,903 Bytes
- 114 Pages / 439.37 x 666.142 pts Page_size
- 108 Downloads / 251 Views
SERIES IN COMPUTER SCIENCE Series Editor: Rami G. Melhem University of Pittsburgh Pittsburgh, Pennsylvania
ENGINEERING ELECTRONIC NEGOTIATIONS A Guide to Electronic Negotiation Technologies for the Design and Implementation of Next-Generation Electronic Markets-Future Silkroads of eCommerce Michael Strobel FUNDAMENTALS OF X PROGRAMMING Graphical User Interfaces and Beyond Theo Pavlidis INTRODUCTION TO PARALLEL PROCESSING Algorithms and Architectures Behrooz Parhami OBJECT-ORIENTED DISCRETE-EVENT SIMULATION WITH JAVA A Practical Introduction Jose M. Garrido A PARALLEL ALGORITHM SYNTHESIS PROCEDURE FOR HIGHPERFORMANCE COMPUTER ARCHITECTURES Ian N. Dunn and Gerard G. L. Meyer PERFORMANCE MODELING OF OPERATING SYSTEMS USING OBJECT-ORIENTED SIMULATION A Practical Introduction jose M. Garrido POWER AWARE COMPUTING Edited by Robert Graybill and Rami Melhem THE STRUCTURAL THEORY OF PROBABILITY New Ideas from Computer Science on the Ancient Problem of Probabi I ity Interpretation Paolo Rocchi
A Parallel Algorithm Synthesis Procedure for High-Performance Computer Architectures Ian N. Dunn Mercury Computer Systems, Inc. Chelmsford, Massachusetts
and
Gerard G. L. Meyer Johns Hopkins University Baltimore, Maryland
SPRINGER SCIENCE+BUSINESS MEDIA, LLC
ISBN 978-1-4613-4658-6 ISBN 978-1-4419-8650-4 (eBook) DOI 10.1007/978-1-4419-8650-4
©2003 Springer Science+Business Media New York Originally published by Kluwer Academic / Plenum Publishers, New York in 2003 Softcover reprint of the hardcover 1st edition 2003 http://www.wkap.nl
10
9
8
7
6
5
4
3 2
1
A c.i.P. record for this book is available from the Library of Congress
AII rights reserved No part oi this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any meims, electronic, mechanical, photocopying, microfilming, recording, or otherwise, without written permission from the Publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work.
Contents
List of Figures List of Tables Acknowledgments
vii ix xi
1. INTRODUCTION
1 2
1 2 3
Notation and Conventions Chapter Organization
5 6
2. PARALLEL COMPUTING Architectures 1 Programming Models 2 Performance Metrics 3
9 10
3. PARALLEL ALGORITHM SYNTHESIS PROCEDURE 1 2
3
Architectural Model for Algorithm Synthesis Synthesis Procedure Related Work
13 14 15 25
4. REVIEW OF MATRIX FACTORIZATION Givens-based Solution Procedures 1 Householder-based Solution Procedures 2
29
36
5. CASE STUDY 1: PARALLEL FAST GIVENS QR
41
31
1
Parallel Fast Givens Algorithm
42
2 3 4
Communication Procedures
51
Related Work Experimental Results
59
60
v
PARALLEL ALGORITHM SYNTHESIS PROCEDURE
VI
6. CASE STUDY 2: PARALLEL COMPACT WY QR 1 Parallel Compact WY Algorithm 2
3
Related Work Experimental Results
7. CASE STUDY 3: PARALLEL BIDIAGONALIZATION 1 Parallel Matrix Bidiagonalization Algorithm 2 3
Related Work Experimental Results
8. CONCLUSION References Ind
Data Loading...