E-Book Overview
This book is on dependence concepts and general methods for dependence testing. Here, dependence means data dependence and the tests are compile-time tests. We felt the time was ripe to create a solid theory of the subject, to provide the research community with a uniform conceptual framework in which things fit together nicely. How successful we have been in meeting these goals, of course, remains to be seen. We do not try to include all the minute details that are known, nor do we deal with clever tricks that all good programmers would want to use. We do try to convince the reader that there is a mathematical basis consisting of theories of bounds of linear functions and linear diophantine equations, that levels and direction vectors are concepts that arise rather natu rally, that different dependence tests are really special cases of some general tests, and so on. Some mathematical maturity is needed for a good understand ing of the book: mainly calculus and linear algebra. We have cov ered diophantine equations rather thoroughly and given a descrip of some matrix theory ideas that are not very widely known. tion A reader familiar with linear programming would quickly recog nize several concepts. We have learned a great deal from the works of M. Wolfe, and K. Kennedy and R. Allen. Wolfe's Ph. D. thesis at the University of Illinois and Kennedy & Allen's paper on vectorization of Fortran programs are still very useful sources on this subject.
E-Book Content
DEPENDENCE ANALYSIS FOR SUPERCOMPUTING
THE KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE PARALLEL PROCESSING AND FIFTH GENERATION COMPUTING
Consulting Editor Doug DeGroot Other books in the series: PARALLEL EXECUTION OF LOGIC PROGRAMS John S. Conery ISBN 0-89838-194-0 PARALLEL COMPUTATION AND COMPUTERS FOR ARTIFICIAL INTELLIGENCE Janusz S. Kowalik ISBN 0-89838-227-0 MEMORY STORAGE PATTERNS IN PARALLEL PROCESSING Mary E. Mace ISBN 0-89838-239-4 SUPERCOMPUTER ARCHITECTURE Paul B. Schneck ISBN 0-89838-234~4 ASSIGNMENT PROBLEMS IN PARALLEL AND DISTRIBUTED COMPUTING Shahid H. Bokhari ISBN 0-89838-240-8 MEMORY PERFORMANCE OF PROLOG ARCHITECTURES Evan Tick ISBN 0-89838-254-8 DATABASE MACHINES AND KNOWLEDGE BASE MACHINES Masaru Kitsuregawa ISBN 0-89838-257-2 PARALLEL PROGRAMMING AND COMPILERS Constantine D. Polychronopoulos ISBN 0-89838-288-2
DEPENDENCE ANALYSIS FOR SUPERCOMPUTING by
Utpal Banerjee
Control Data Corporation Sunnyvale, California
KLUWER ACADEMIC PUBLISHERS
Boston/Dordrecht/London
Distributors for North America: Kluwer Academic Publishers 101 Philip Drive Assinippi Park Norwell, Massachusetts 02061 USA Distributors for the UK and Ireland: Kluwer Academic Publishers Falcon House, Queen Square Lancaster LA1 lRN, UNITED KINGDOM Distributors for all other countries: Kluwer Academic Publishers Group Distribution Centre Post Office Box 322 3300 AH Dordrecht, THE NETHERLANDS
Library of Congress Cataloging-in-Publication Data Banerjee, Utpal, 1942Dependence analysis for supercomputing / by Utpal Banerjee. p. cm. --(The Kluwer international series in engineering and computer science. Parallel processing and fifth generation computing) Bibliography: p. Includes index. ISBN-13: 978-1-4684-6896-0 DOl: 10.1007/978-1-4684-6894-6
e-ISBN-13: 978-1-4684-6894-6
1. Supercomputers. 2. Parallel processing (Electronic computers) I. Title. II. Series. QA76.5.B264 1988 88-13375 004.1 'J-dcI9 CIP
Copyright © 1988 by Kluwer Academic Publishers Softcover reprint of the hardcover 1st edition 1988
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher, Kluwer Academ