Parallel Computing in Optimization
During the last three decades, breakthroughs in computer technology have made a tremendous impact on optimization. In particular, parallel computing has made it possible to solve larger and computationally more difficult prob lems. This volume contains m
- PDF / 47,132,347 Bytes
- 596 Pages / 453.543 x 680.315 pts Page_size
- 16 Downloads / 226 Views
Applied Optimization Volume 7 Series Editors: Panos M. Pardalos University of Florida, U.S.A. Donald Hearn University of Florida, U.SA.
The titles published in this series are listed at the end of this volume.
Parallel Computing in Optimization Edited by
Athanasios Migdalas LinJcijping Institute of Technology
Panos M. Pardalos University ofFlorida
and
Sverre Stor0y University ofBergen
KLUWER ACADEMIC PUBLISHERS DORDRECHT I BOSTON I LONDON
A C.l.P. Catalogue record for this book is available from the Library of Congress.
ISBN-13: 978-1-4613-3402-6
e-ISBN-13:978-1-4613-3400-2
001: 10.1007/978-1-4613-3400-2
Published by Kluwer Academic Publishers, P.O. Box 17,3300 AA Dordrecht, The Netherlands. Kluwer Academic Publishers incorporates the publishing programmes of D. Reidel, Martinus Nijhoff, Dr W. Junk and MTP Press. Sold and distributed in the U.S.A. and Canada by Kluwer Academic Publishers, 101 Philip Drive, Norwell, MA 02061, U.S.A. In all other countries, sold and distributed by Kluwer Academic Publishers, P.O. Box 322, 3300 AH Dordrecht, The Netherlands.
Printed on acid-free paper
All Rights Reserved © 1997 Kluwer Academic Publishers Softcover reprint of the hardcover 1st edition 1997 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner.
"there is no rest for the messenger till the message is delivered" The Rescue: A Romance in the Shallows (by Joseph Conrad)
CONTENTS
PREFACE 1
xvii
MODELS FOR PARALLEL ALGORITHM DESIGN: AN INTRODUCTION
Afonso Ferreira and Michel Morvan 1 Introduction Shared memory model: PRAM 2 Distributed memory models: DMM 3 The coarse grained multicomputer model: CGM 4 Summary 5 6
2
EXERCISES
PARALLEL ALGORITHMS AND COMPLEXITY
Martin Furer 1 Introduction Models of Parallel Computers 2 Limits of Parallelism 3 Classification of some Important Graph Problems 4 Basic Techniques 5 6
7 8
3
1 1 4 13 21 24 24
Parallel Algorithms Toolbox Approximating the Minimum Degree Spanning Tree Problem EXERCISES
27 28 30 34 38 40 44 49 52
A PROGRAMMER'S VIEW OF PARALLEL COMPUTERS TorS¢revik
1
57 57
Introduction
Vll
PARALLEL COMPUTING IN OPTIMIZATION
Vlll
2 3 4 5
4
The Memory Hierarchy Communication Network Future trends EXERCISES
SCALABLE PARALLEL ALGORITHMS FOR SPARSE LINEAR SYSTEMS Anshul Gupta, George Karypis, and Vipin Kumar
1 2 3 4
5
Introduction Parallel Direct Cholesky Factorization Multilevel Graph Partitioning EXERCISES
73 73 77 84 91
OBJECT ORIENTED MATHEMATICAL MODELLING AND COMPILATION TO PARALLEL CODE Niclas Andersson and Peter Fritzson
1 2 3 4 5 6 7 8 9 10 11
6
59 65 68 69
Introduction Object Math Background to Parallel Code Generation Definitions Towards a Parallelising Compiler Equation System Level Equation Level Clustered Task Level Explicit Parallelism Summary EXERCISES
99 100 102 121 136 141 145 151 159 170 177 178
