PARALLEL LANGUAGE AND COMPILER RESEARCH IN JAPAN PARALLEL LANGUAGE AND COMPILER RESEARCH IN JAPAN EDITED BY Lubomir F. BIC University of California, Irvine Irvine. CA 92717 • Alexandru N ICOLAU University of California, Irvine Irvine. CA 92717 • Mitsuhisa SATO Electrotechnical Laboratory Tsukuba. Japan SPRINGER-SCIENCE+BUSINESS MEDIA, B.V. ISBN 978-1-4613-5957-9 ISBN 978-1-4615-2269-0 (eBook) DOI 10.1007/978-1-4615-2269-0 Library of Congress Cataloging-In-Publication Data A C.I.P. Catalogue record for this book is available from the Library of Congress. Copyright 1995 Springer Science+Business Media Dordrecht CI Originally published by Kluwer Academic Publishers in 1995 Softcover reprint of the hardcover I st edition 1995 All rights reserved. No pan 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 pennission of the publisher, Springer-Science+Business Media, B.V. Primed on acid-free paper. CONTENTS FOREWORD lX 1 INTRODUCTION Lubomir F. Bic, Alex Nicolau and Mitsuhisa Sato 1 2 LANGUAGE DESIGN AND IMPLEMENTATION OF DFCII FOR A DATAFLOW SUPERCOMPUTER SIGMA-l Satoshi Sekiguchi, Kei Hiraki and Toshio Shimada 13 3 EM-C: PROGRAMMING WITH EXPLICIT PARALLELISM AND LOCALITY FOR EM-4 MULTIPROCESSOR Mitsuhisa Sato, Yuetsu Kodama, Shuichi Sakai and Yoshinori Yamaguchi 47 4 INTRODUCTION OF RWC MASSIVELY PARALLEL PROGRAMMING LANGUAGES Yutaka Ishikawa, Hiroki Konaka, Atsushi Hori, Munenori Maeda and Takashi Tomokiyo 75 5 COMPILING AND MANAGING CONCURRENT OBJECTS FOR EFFICIENT EXECUTION ON HIGH-PERFORMANCE MPPS Satoshi Matsuoka, Masahiro Yasugi, Kenjiro Taura, Tomio Kamada and Akinori Yonezawa 91 v VI PARALLEL LANGUAGE AND COMPILER RESEARCH IN JAPAN 6 IMPLEMENTATION OF PARALLEL FUNCTIONAL LANGUAGE ON CONVENTIONAL MULTIPROCESSORS Shigeru Kusakabe, Eiichi Takahashi, Rin-ichiro Taniguchi and Makoto Amamiya 127 7 A FORTRAN COMPILER AND A VISUAL ENVIRONMENT OF PROGRAM DEVELOPMENT FOR DATAFLOW MACHINES Toshiaki Yasue and Yoichi Muraoka 151 8 STATIC TASK SCHEDULING ON FINE-GRAIN SUPPORTING MULTIPROCESSORS Tatsushi Inagaki, Takashi Matsumoto and Kei Hiraki 171 9 FLENG ON PIE64 AND ITS PROGRAMMING ENVIRONMENT Hidemoto Nakada and Hidehiko Tanaka 197 10 PARALLEL INFERENCE SYSTEM RESEARCH IN THE JAPANESE FGCS PROJECT Takashi Chikayama and Kazuaki Rokusawa 235 11 OSCAR FORTRAN MULTIGRAIN COMPILER H. Kasahara, H. Honda, K. Aida, M. Okamoto, A. Yoshida and W. Ogata 271 12 THE VECTORIZING/ PARALLELIZING COMPILER V-PASCAL Takao Tsuda, Yoshitoshi Kunieda, and Tetsutaro Uehara 303 13 AUTOMATIC PARALLELIZING COMPILER FOR DISTRIBUTED MEMORY PARALLEL COMPUTERS: NEW ALGORITHMS TO IMPROVE THE PERFORMANCE OF THE INSPECTOR/EXECUTOR Contents vii Atsushi Kubota, Ikuo Miyoshi, Kazuhiko Ohno, Shin-ichiro MoTi, Hiroshi Nakashima and Shinji Tomita 313 14 TOWARD THE SINGLE AND MULTIPLE PROGRAMMED ENVIRONMENTS FOR THE FUTURE LARGE-SCALED PARALLEL SYSTEMS Akira Fukuda and Kazuki Joe 325 15 SM-l AND ITS LANGUAGE SYSTEMS Taichi Yuasa, Motohiko Matsuda and Toshiro Kijima 349 16 PCASE: A PROGRAMMING ENVIRONMENT FOR PARALLEL SUPERCOMPUTERS Yoshiki Seo, Tsunehiko Kamachi, Kazuhiro Kusano, Yukimitsu Watanabe and Yukimasa Shiro to 377 17 VPP FORTRAN FOR DISTRIBUTED MEMORY PARALLEL COMPUTERS Tatsuya Shindo, Hidetoshi Iwashita and Shin Okada 405 18 PARALLEL PROGRAMMING LANGUAGE ADETRAN Koji Zaiki, Akiyoshi Wakatani, Tadashi Okamoto, Katsuyuki Kaneko and Tatsuo Nogi 429 19 PDEQSOL (PARTIAL DIFFERENTIAL EQUATION SOLVER LANGUAGE) FOR PARALLEL COMPUTERS Toshio Okochi 467 BIBLIOGRAPHY 485 AUTHOR/SUBJECT INDEX 521 FOREWORD When the editors of this book first approached the U.S. Office of Naval Re search in 1991 with the idea of preparing a book of this nature, they received an enthusiastic reaction. For almost 50 years, one of the primary charters of ONR has been to encourage and foster an understanding of international de velopments in science and technology. Even in the current age of the emerging information superhighway that links international researchers and technology practitioners in a web of inter-dependencies and collaborations, the flow of in formation and critical assessments regarding scientific and technology advances in certain countries is still severely hindered by technical and cultural obstacles. The case of Japan's science and technology is perhaps the most obvious exam ple of this phenomenon, where despite the growing efforts by Japanese industry and government to participate fully in the international commerce of science and technology exchange, difficult barriers involving language, alphabet, and custom continue to impede the visibility of Japanese innovations to interested international on-lookers. The contributions of Japanese scientists, engineers, and corporations in "hard ware-oriented" fields such as electronics miniaturization, video and audio record ing, optics and photography, and manufacturing quality are well- known inter nationally because of the many products exported world-wide that incorporate these advances. However, many other areas of Japanese science and technol ogy are not so well known. For example, Japanese innovations and advances in software technology are reported in scattered forums, with relatively little independent assessment or uniformity of presentation. Few Japanese software products are available internationally. As a result of these factors, the inter national technical community is only marginally aware of Japanese software research efforts, and perhaps underestimates their potential importance. The present volume offers the international community an opportunity to learn in-depth about key Japanese research efforts in the particular software domains of parallel programming languages and parallelizing compilers. These are im portant topics that strongly bear on the effectiveness and affordability of high performance computing systems. The chapters of this book convey a compre- IX X PARALLEL LANGUAGE AND COMPILER RESEARCH IN JAPAN hensive and current depiction of leading edge research efforts in Japan that focus on parallel software design, development, and optimization that could be obtained only through direct and personal interaction with the researchers themselves. It is my hope that readers will find this book to be both interesting and professionally valuable. Andre van Tilborg, Director Mathematical, Computer, and Information Sciences Division Office of Naval Research Arlington, VA 1 INTRODUCTION Lubomir F. Bic, Alex Nicolau, and Mitsuhisa Sato* Department of Information and Computer Science University of California, Irvine, California 92717 * Electrotechnical Laboratory Tsukuba, Ibaraki, 905 Japan The last decade has witnessed an explosion of projects in Japan aimed at the development of new parallel programming languages, compilers, and compila tion techniques capable of better exploiting the computational power of parallel computer architectures that are already on the market or are likely to emerge in the near future as a result of new technological breakthroughs. This book provides a comprehensive survey of most of the important Japanese projects currently in progress. In this introductory chapter, we will provide the moti vation for this survey as well as a framework for studying the various projects. The idea for compiling this book has its roots in the interest of the three co editors in the issues of parallel processing and in a realization that many new concepts and systems are being developed in Japan with relatively little pub licity in the United States and elsewhere. The geographical distances (albeit mitigated by electronic communication means) and, even more importantly, the language and cultural barriers make it rather difficult for non-Japanese re searchers to get a balanced view and judge the relative importance of the various projects. Having visited the sites where the projects are located and having discussed the various approaches with the respective researchers, we invited the leaders of each project to contribute an original chapter to this book, describing the most important aspects of their work according to uniform guidelines that provide for a level of consistency among the various contributions. In addi tion, we interviewed the project leaders and many of the researchers involved to gain additional insights that would allow us to make comparisons based on a variety of criteria. These will be presented in the following paragraphs of this introductory chapter. 1 2 CHAPTER 1 In addition to this introduction, the book comprises 18 chapters, each dealing with a distinct project. While collaboration exists among various projects, each has its own identity and distinct affiliation. Four are based in Japanese national laboratories, four others in leading computer manufacturing corporations, and the remaining ten are largely university-based projects, with the University of Tokyo housing three of these, Kyoto University and Waseda University housing two each, and Kyushu University, Nara Institute of Science and Technology, and Toyohashi University of Technology housing one each. Of course, collaborative ties between several of the university-based projects and industrial partners exist. In these cases, some level of financial support is usually provided by the corporate sponsors. Other projects are partially funded by MITI, the Japanese Ministry of Education (Monbu-sho), or the parent university itself. It is interesting to note that most projects are fairly recent efforts. Only four of them-one at the University of Tokyo, one at Kyoto University, one at ICOT, and one at ETL (Electrotechnical Laboratory, Tsukuba)-are more than ten years old. Approximately half of the others originated in the late 1980s and the other half only during the last four years. The different projects vary greatly in their scope, objectives, and approach. Most of the university-based projects have a similar hierarchical structure, com prising one or two faculty members as the leaders who supervise a number of graduate and undergraduate students, visitors, and possibly staff members. The commercial and national lab-based projects, on the other hand, usually comprise a small team of professional researchers, usually supported by a small group of programmers and/or engineers. Some of the labs, notably ETL, also host international and national visitors, who become involved in the project for the duration of their stay. Thus, the structure and organization of the projects covered span the range from an open university environment conduct ing basic research to more product-oriented environments typical of corporate laboratories. The particular organizational setting also reflects the project's main empha sis. While the corporate projects all identified the building of a commercial system or at least a working prototype as their immediate goal, the university and national lab-based projects are directed towards longer-term goals. While most still state that building a working prototype is an important part of their project, most affirm that basic research into new programming and compil ing paradigms is the main concern. Similarly, the methods and techniques for demonstrating the effectiveness of a project vary widely, with benchmark testing being the most common approach. Several university-based projects,