NOTE: Advance Registration DEADLINE is Friday, MARCH 24. ******************** * ADVANCE PROGRAM * ******************** IPPS '95 - 9TH INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM APRIL 24-28, 1995 FESS PARKER'S RED LION RESORT SANTA BARBARA, CALIFORNIA For easier reading, ask for a hard copy of this advance program. Contact: Regina Morton, Department of EE-Systems, EEB 200, 3740 McClintock Avenue, University of Southern California, Los Angeles, CA 90089-2562 email: morton@pollux.usc.edu Fax: (213) 740-4418 Additional information regarding IPPS '95 events may be obtained by anonymous ftp (replicant.csci.unt.edu) or on the Web (using URL http://www.usc.edu/dept/ ceng/prasanna/ home.html) or contact IPPS '95 General Chair V.K. Prasanna (ipps95@halcyon.usc.edu). --------------------------------------------------------------------------- CONTENTS *************************************************************************** SYMPOSIUM ORGANIZATION IPPS '95 PROGRAM SYMPOSIUM OVERVIEW MONDAY, APRIL 24 Workshop 1 Tutorial 1 TUESDAY, APRIL 25 Workshop 1 (cont.) Workshops 2 to 7 Tutorials 2 & 3 WEDNESDAY, APRIL 26 Keynote Address Technical Sessions 1-9 Workshop 1 (cont.) THURSDAY, APRIL 27 Keynote Address Technical Sessions 10-15 Industrial Track Sessions Panel 1 FRIDAY, APRIL 28 Keynote Address Technical Sessions 16-20 Panel 2 LOCATION *************************************************************************** SYMPOSIUM ORGANIZATION ___________________________________________________________________________ SYMPOSIUM CHAIR Viktor K. Prasanna, University of Southern California ___________________________________________________________________________ PROGRAM CHAIR Joseph Ja'Ja', Institute for Advanced Computer Studies, University of Maryland ___________________________________________________________________________ PROGRAM VICE-CHAIRS Algorithms: Guy Blelloch, Carnegie Mellon University Applications: Vipin Kumar, University of Minnesota Architecture: Allan Gottlieb, New York University Software: Andrew Chien, University of Illinois, Urbana-Champaign INDUSTRIAL-COMMERCIAL CHAIR John K. Antonio, Purdue University PROCEEDINGS CHAIR Ronald Greenberg, University of Maryland TUTORIALS CHAIR Ashfaq Khokhar, Purdue University FINANCE CHAIR Bill Pitts, Toshiba America Information Systems, Inc. LOCAL ARRANGEMENTS CHAIR Susamma Barua, California State University, Fullerton PUBLICITY CHAIR Sally Jelinek, Electronic Design Associates PUBLICITY COORDINATORS Americas: Sajal Das, University of North Texas Asia: Raghu Raghavan, National University of Singapore Europe-Africa: Stefan (Lambo) Lamberts, Technische Universitaet Muenchen Pacific Rim: Albert Y. Zomaya, The University of Western Australia PROGRAM COMMITTEE COORDINATOR Johanna Weinstein, University of Maryland PROGRAM COMMITTEE Santosh Abraham, Hewlett Packard Labs Mike Atallah, Purdue University Jean-Loup Baer, University of Washington Prith Banerjee, University of Illinois, Urbana-Champaign Janice Cuny, University of Oregon Jack Dennis, Massachusetts Institute of Technology Jack Dongarra, University of Tennessee Michel Dubois, University of Southern California Guang R. Gao, McGill University Phillip B. Gibbons, AT&T Bell Laboratories Jim Goodman, University of Wisconsin John Gustafson, Ames Laboratory Suzanne Hambrusch, Purdue University Michael Heath, University of Illinois, Urbana-Champaign Oscar Ibarra, University of California, Santa Barbara Leah Jamieson, Purdue University Lennart Johnsson, Thinking Machines/ Harvard University Samir Khuller, University of Maryland Kai Li, Princeton University Jim Little, University of British Columbia Virginia Lo, University of Oregon Bruce Maggs, Carnegie Mellon University David Nassimi, New Jersey Institute of Technology Lionel M. Ni, Michigan State University Alexandru Nicolau, University of California at Irvine D.K. Panda, Ohio State University Bill Pugh, University of Maryland C.S. Raghavendra, Washington State University N. Ranganathan, University of South Florida Sanjay Ranka, Syracuse University Sartaj Sahni, University of Florida Joel Saltz, University of Maryland Assaf Schuster, Technion Francis Sullivan, Supercomputing Research Center Uzi Vishkin, University of Maryland Chip Weems, University of Massachusetts D. Scott Wills, Georgia Institute of Technology Pen-Chung Yew, University of Illinois, Urbana-Champaign Hans Zima, University of Vienna STEERING COMMITTEE CHAIR George Westrom, Odetics, Inc. STEERING COMMITTEE Larry Canter, CSA K. Mani Chandy, Caltech F. Thompson Leighton, MIT Viktor K. Prasanna, USC George Westrom, Odetics, Inc. SYMPOSIUM ADVISORY COMMITTEE Kai Hwang, USC Michael Quinn, Oregon State University R.K. Shyamasundar, TIFR H.J. Siegel, Purdue University Leslie Valiant, Harvard University CHAIRMAN EMERITUS Larry Canter, Computer Systems Approach, Inc. SPONSORSHIP The 9th International Parallel Processing Symposium is sponsored by the IEEE Computer Society Technical Committee on Parallel Processing (TCPP) and is held in cooperation with the ACM Special Interest Group on Computer Architecture (SIGARCH) and the Orange County chapter of the IEEE Computer Society. Additional support for IPPS '95 is being provided by the Department of Computer Science, University of California, Santa Barbara and the Institute for Advanced Computer Studies, University of Maryland, College Park. Companies and organizations listed on the inside cover are providing commercial support. IPPS '95 PROCEEDINGS The 1995 proceedings will be published by the IEEE Computer Society Press and made available to all registrants including students at the symposium. Extra copies and proceedings from previous symposia may be obtained by contacting the IEEE Computer Society. Although availability of proceedings from the seven workshops cannot be guaranteed, all registrants will be issued a ticket for one workshop proceedings; additional copies should be arranged with each workshop chair. PROGRAM IPPS '95 LOCATION See the back of the program for information about Santa Barbara and Fess Parker's Red Lion Resort. Also, note the hotel reservation form which is attached to the IPPS '95 registration form in the center of the program. IPPS '95 PROGRAM SCHEDULE The customary IPPS events include contributed technical papers, keynote addresses, workshops, panels, vendor presentations, and tutorials. Workshop 1 will start on Monday the 24th, so registration will be open the evening of Sunday the 23rd to accommodate early arrivals. The other 6 workshops will be held on Tuesday, and Workshop 1 will continue through Wednesday. The IPPS '95 tutorials will be conducted on Monday and Tuesday. Wednesday through Friday will feature sessions for contributed papers along with panel discussions and industrial track presentations, and each day will open with a keynote address. CONTRIBUTED PAPERS There will be 115 contributed technical papers to be presented in 20 technical sessions. Topics span the design, development, use, and analysis of parallel processing systems. KEYNOTE ADDRESSES Wednesday, April 26: Modeling Parallel Communication Richard Karp, University of California, Berkeley Thursday, April 27: The New Era of MPPs: Moderately Parallel Processors Forest Baskett, Silicon Graphics, Inc. Friday, April 28: Parallel Computing Sartaj Sahni, University of Florida PANELS 1. Networked Parallel Processing: Is It the Future of Scalable Computing? Moderator: Kai Hwang, University of Southern California 2. Different Approaches to Parallel Computing Education Moderator: Russ Miller, State University of New York, Buffalo WORKSHOPS There will be seven workshops: Workshop 1 starts on Monday the 24th, continues on Tuesday, and will conclude on Wednesday. The other six workshops will be held on Tuesday. Workshops are open to all symposium registrants. Since submission criteria and deadlines vary, contact individual workshop organizers for more information. Also, details on all IPPS activities including workshops are available by anonymous ftp from replicant.csci.unt.edu. (Login as "anonymous" and use your email address as password. The files are located in pub/IPPS95.) 1. Third IPPS Workshop on Parallel and Distributed Real-Time Systems (to be held jointly with 7th International Real-Time Ada Issues Workshop) 2. Fourth IPPS Workshop on Heterogeneous Computing 3. Third IPPS Workshop on Input/Output in Parallel and Distributed Systems 4. Second IPPS Workshop on Reconfigurable Architectures 5. First IPPS Workshop on Solving Irregular Problems on Distributed Memory Machines 6. First IPPS Workshop on High-Speed Network Computing 7. First IPPS Workshop on Job Scheduling Strategies for Parallel Processing TUTORIALS All three tutorials are half day. Tutorial 1 will be held Monday pm and 2 and 3 will be held Tuesday in the am and pm. It is thus possible to register for all three sessions. 1. Architecture-Independent Data Parallel Computing on Coarse Grained Machines 2. Techniques and Tools for Performance Tuning of Parallel and Distributed Scientific Applications 3. Parallel Processing for Multimedia Information Systems COMMERCIAL-INDUSTRIAL TRACK Two Industrial Track sessions are planned for Thursday, and commercial exhibits will be open on Wednesday, Thursday and Friday. For more information on participation and planned exhibits, contact Commercial-Industrial Chair John K. Antonio (jantonio@ecn.purdue.edu). SOCIAL EVENTS Refreshments will be served at several breaks throughout the day. On Wednesday evening a dinner event is planned. On Friday following the closing panel discussion, there will be a traditional IPPS party - overlooking the beach! REGISTRATION See the tear-out forms in the middle of the Advance Program. Note that advance registration must be sent by March 24, 1995 and received by March 31, 1995 at the IEEE Computer Society. Registrations after March 31 will be accepted on-site only. FOR MORE INFORMATION Additional information regarding IPPS '95 events may be obtained by anonymous ftp (replicant.csci.unt.edu) or on the Web (using URL http://www.usc.edu/dept/ ceng/prasanna/home.html) or contact IPPS '95 General Chair V.K. Prasanna (ipps95@halcyon.usc.edu). OVERVIEW Registration will be open in the evenings on Sunday, Monday, and Tuesday and will open early on Monday, Tuesday, and Wednesday. MONDAY, APRIL 24 8:30 AM - 9:30 AM WORKSHOP 1 - OPENING ADDRESS 9:30 AM - 10:00 AM MID MORNING BREAK 10:00 AM - 12 NOON WORKSHOP 1 - SESSION 1 12 NOON - 1:30 PM LUNCH BREAK (On Your Own) 1:30 PM - 3:30 PM WORKSHOP 1 - SESSION 2 2:00 PM - 6:00 PM TUTORIAL 1 3:30 PM - 4:00 PM AFTERNOON BREAK 4:00 PM - 6:00 PM WORKSHOP 1 - SESSION 3 TUESDAY, APRIL 25 8:30 AM - 9:30 AM WORKSHOPS 2 to 7 - OPENING ADDRESS 9:00 AM - 1:00 PM TUTORIAL 2 9:30 AM - 10:00 AM MID MORNING BREAK 10:00 AM - 12 NOON WORKSHOP 1 - SESSION 4 WORKSHOPS 2 to 7 - SESSION 1 12 NOON - 1:30 PM LUNCH BREAK (On Your Own) 1:30 PM - 3:30 PM WORKSHOP 1 - SESSION 5 WORKSHOPS 2 to 7 - SESSION 2 2:00 PM - 6:00 PM TUTORIAL 3 3:30 PM - 4:00 PM AFTERNOON BREAK 4:00 PM - 6:00 PM WORKSHOP 1 - SESSION 6 WORKSHOPS 2 to 7 - SESSION 3 WEDNESDAY, APRIL 26 8:30 AM - 9:30 AM KEYNOTE ADDRESS 9:30 AM - 10:00 AM MID MORNING BREAK 10:00 AM - 12 NOON CONTRIBUTED PAPERS - SESSION 1 - SESSION 2 - SESSION 3 WORKSHOP 1 - SESSION 7 12 NOON - 1:30 PM LUNCH BREAK (On Your Own) 1:30 PM - 3:30 PM CONTRIBUTED PAPERS - SESSION 4 - SESSION 5 - SESSION 6 WORKSHOP 1 - SESSION 8 3:30 PM - 4:00 PM AFTERNOON BREAK 4:00 PM - 6:00 PM CONTRIBUTED PAPERS - SESSION 7 - SESSION 8 - SESSION 9 WORKSHOP 1 - SESSION 9 7:30 PM IPPS '95 BANQUET THURSDAY, APRIL 27 8:30 AM - 9:30 AM KEYNOTE ADDRESS 9:30 AM - 10:00 AM MID MORNING BREAK 10:00 AM - 12 NOON CONTRIBUTED PAPERS - SESSION 10 - SESSION 11 - SESSION 12 INDUSTRIAL TRACK - Session I 12 NOON - 1:30 PM LUNCH BREAK (On Your Own) 1:30 PM - 3:30 PM CONTRIBUTED PAPERS - SESSION 13 - SESSION 14 - SESSION 15 INDUSTRIAL TRACK - Session II 3:30 PM - 4:00 PM AFTERNOON BREAK 4:00 PM - 6:00 PM PANEL 1 - RESEARCH 6:00 PM - (Evening On Your Own) FRIDAY, APRIL 28 8:30 AM - 9:30 AM KEYNOTE ADDRESS 9:30 AM - 10:00 AM MID MORNING BREAK 10:00 AM - 12 NOON CONTRIBUTED PAPERS - SESSION 16 - SESSION 17 - SESSION 18 12 NOON - 1:30 PM LUNCH BREAK (On Your Own) 1:30 PM - 3:30 PM CONTRIBUTED PAPERS - SESSION 19 - SESSION 20 3:30 PM - 4:00 PM AFTERNOON BREAK 4:00 PM - 6:00 PM PANEL 2 - EDUCATION 6:30 PM BEACH PARTY __________________________________________________________________ IPPS '95 PROGRAM SCHEDULE __________________________________________________________________ ****************************************************************** MONDAY, APRIL 24 ****************************************************************** Workshop 1: All Day Monday, Tuesday and Wednesday JOINT WORKSHOP ON PARALLEL AND DISTRIBUTED REAL-TIME SYSTEMS (3rd Workshop on Parallel and Distributed Real-Time Systems & 7th International Real-Time Ada Issues Workshop) Workshop Co-Chairs: Theodore Baker, Florida State University Dieter K. Hammer, Eindhoven University of Technology Yoshiaki Kakuda, Osaka University Lonnie R. Welch, New Jersey Institute of Technology ___________________________________________________ Program Committee: John Barnes, UK Maarten Boasson, Hollands Signal, The Netherlands Alan Burns, University of York, UK Steve Case, Computing Devices Int., USA Klaus Ecker, Technical University of Clausthal, Germany Loe Feijs, Philips Research, The Netherlands Borko Furht, Florida Atlantic University, USA Anthony Gargaro, Computer Sciences Corporation, USA Michael Gonzalez, Spain John Goodenough, Software Engineering Institute Robert Harrison, Naval Surface Warfare Center, USA Guenter Hommel, Technical University of Berlin, Germany Keith Hopper, New Zealand Norm Howes, Institute for Defense Analyses, USA Mathai Joseph, University of Warwick, UK Joerg Kaiser, GMD, Germany Mike Kamrad, Computing Devices Int., USA Jan van Katwijk, Delft University of Technology, The Netherlands Jane W.S. Liu, University of Illinois, USA Jyh C. Liu, Texas A&M University, USA Douglass Locke, Loral Federal Systems Division, USA Michael W. Masters, Naval Surface Warfare Center, USA Mike Rodd, University of Wales, UK Kang G. Shin, University of Michigan, USA Behrooz Shirazi, University of Texas, USA Sang Son, University of Virginia, USA John A. Stankovic, University of Massachusetts, USA Robert Steigerwald, U. S. Air Force Academy, USA Alfred Strohmeier, Swiss Fed Inst of Technology, Switzerland Morikazu Takegaki, Mitsubishi Electric Company, Japan Kenji Toda, MITI Electrotechnical Lab, Japan Joyce Tokar, Tartan Laboratories, USA Richard Volz, Texas A&M University, USA Andrew Wellings, University of York Mark Wilson, Naval Surface Warfare Center, USA Tomohiro Yoneda, Tokyo Institute of Technology, Japan Wei Zhao, Texas A&M University, USA Real-time systems frequently employ parallel and distributed computer platforms in order to meet timing constraints and to achieve fault tolerance and availability. In order to come to a usable solution, the issues of concurrency and dependability must be considered simultaneously. However, it is often the case that researchers focus on problems relevant to concurrent processing while overlooking timeliness. Similarly, real-time computing research efforts are often focused on producing techniques that apply only to single processor systems. The purpose of this IPPS '95 joint workshop is to address this unfortunate state of affairs. In its third year, the IPPS Workshop on Parallel and Distributed Real-Time Systems (WPDRTS3) will combine with the 7th International Real-Time Ada Issues Workshop. This partnering will help to place focus on problems of importance to those who are building concurrent real-time systems in Ada. Thus, in addition to considering issues relevant to concurrent real-time systems in general, the workshop will also give attention to issues pertinent to concurrent, real-time Ada and Ada 9X. Topics of interest include: - Architecture, hardware, communication systems and protocols - Operating systems - Hard and soft real-time systems - Fault tolerance, reliability, and security - Scheduling, resource allocation, and optimization - Programming languages and compiler techniques - Complex systems engineering and reengineering - Object-based techniques - Design and requirements - Applications (including multimedia, databases, artificial intelligence, command and control, and transportation) - Comparison of Ada/Ada 9X with other languages for real-time programming - Implementation/performance of Ada/Ada 9X real-time and concurrent features and Annexes - Advances in real-time Ada/Ada 9X runtime systems - Using Ada/Ada 9X for real-time concurrent computing This joint workshop is sponsored by the U. S. Naval Surface Warfare Center, and is held in cooperation with the IEEE Computer Society Technical Committee on Parallel Processing and Technical Committee on Real-Time Systems. For more information, please contact one of the following workshop co-chairs: For Ada-related papers: Theodore Baker Florida State University Internet: baker@cs.fsu.edu For Europe and Africa: Dieter K. Hammer Dept. of Mathematics and Computing Science Eindhoven Univ. of Technology P. O. Box 513 NL-5600 MB Eindhoven The Netherlands Vox: +31 40 474416 Internet: hammer@win.tue.nl For the Pacific Rim: Yoshiaki Kakuda Dept. of Information and Computer Sciences Faculty of Engineering Science Osaka University 1-3, Machikaneyama-cho, Toyonaka-shi Osaka 560, Japan Vox: +81 6 844 1151 ext.4841 Internet: kakuda@ics.es.osaka-u.ac.jp For the Americas: Lonnie R. Welch Dept. of Computer and Information Science New Jersey Institute of Technology University Heights Newark, NJ 07102 Vox: (201) 596-5683 Internet: welch@vienna.njit.edu ___________________________ Tutorial 1 (Half-Day Afternoon) ___________________________ Architecture-Independent Data Parallel Computing on Coarse Grained Machines Sanjay Ranka, Syracuse University Ravi V. Shankar, Syracuse University Who Should Attend: The tutorial is targeted at anyone interested in using parallel computing for solving real world applications. Overall, the tutorial's content will be split as follows: about 40% of it will be at an introductory level, about 40% at an intermediate level, and the remaining 20% at an advanced level. Course Description: Commercially available coarse grained machines provide the raw computational power to outperform traditional supercomputers by several orders of magnitude. The objective of this tutorial is to describe architecture- independent programming paradigms and software development techniques for the efficient parallelization of regular and irregular data parallel applications on coarse grained machines. Such data parallel applications cover a large fraction of the applications which have been successfully parallelized on these machines. The tutorial will discuss important characteristics of commercially available coarse grained parallel machines such as the IBM SP series, CM-5, nCUBE, and Intel Paragon; important communication primitives required for solving applications in the context of the Message Passing Interface (MPI) Standard; and an overview of parallel constructs and data partitioning directives in the context of High Performance Fortran (HPF). Several real world application kernels chosen from scientific computing, and from areas such as computer vision and image processing will be used to illustrate the algorithms and the software development process. Important metrics for evaluating the performance and scalability of the software developed will also be discussed. Lecturers: Sanjay Ranka is an associate professor in the School of Computer Science at Syracuse University, where he has been on the faculty since 1988. He received his B. Tech in Computer Science and Engineering from the Indian Institute of Technology, Kanpur in 1985 and Ph. D. in Computer and Information Science from the University of Minnesota, Minneapolis in 1988. His main research areas include models of parallel computation, parallel algorithms, runtime support for compilers, and high-performance computing. He has coauthored over 100 journal and conference papers, several book chapters and a book on "Hypercube Algorithms With Applications to Image Processing and Pattern Recognition," published by Springer Verlag. He serves on the editorial board of the Journal of Parallel and Distributed Computing and has served on the program committee of several conferences. He has been one of the main architects of the Fortran 90D/High Performance Fortran Compiler. He was a member of the Message Passing Interface Forum and actively participated in the High Performance Fortran Standard. Ravi V. Shankar received his B. E. in Computer Science and Engineering from Anna University, Madras and his M. S. from Syracuse University. He expects to receive his Ph. D. in Computer Science from Syracuse University in early 1995. During 1990, he was a visiting scholar at the Robotics Institute at Carnegie-Mellon University, and in 1991 he was a Guest Scientist at the Siemens Center for Research and Development in Munich, Germany. His research interests include parallel computing, computational science, and computer vision. ****************************************************************** TUESDAY, APRIL 25 ****************************************************************** Workshop 2: All Day Tuesday 4th WORKSHOP ON HETEROGENEOUS COMPUTING Workshop Chair: Richard Freund, NRaD ___________________________________________ Program Chair: Vaidy Sunderam, Emory University Steering Committee: Fran Berman, University of California, San Diego Jack Dongarra, Oak Ridge National Lab Richard Freund, NRaD (Chair) Paul Messina, JPL/Caltech Jerry Potter, Kent State University H. J. Siegel, Purdue University Program Committee: John Antonio, Purdue University Ray Cline, Sandia Labs/DoE Mary Eshaghian, New Jersey Institute of Technology Rod Fatoohi, NASA Ames Joan Francioni, University of Southwestern Louisiana Al Geist, Oak Ridge National Lab Andrew Grimshaw, University of Virginia Salim Hariri, Syracuse University Walt Ligon, Clemson University David Lilja, University of Minnesota Miron Livny, University of Wisconsin Rick Schlichting, University of Arizona Stephen Scott, Kent State University Vaidy Sunderam, Emory University (Chair) Dan Watson, Utah State University The 4th Heterogeneous Computing Workshop (HCW '95) will be held on April 25th. For the purpose of this workshop, Heterogeneous Computing (HC) is considered the use of different types of parallel processors, processing components, or connectivity paradigms to maximize performance, cost-effectiveness, and/or development effort. HC might range in mode from coupled supercomputing-class machines at separated sites (aka metacomputing) to diverse elements in a single computer (aka mixed-mode processing). Components of HC have appeared in the scientific literature over the past few years. They have included such efforts as the matching of individual code segments to best-suited machines, the development of heterogeneous processor suites to span wide problem sets, and the intelligent management of heterogeneous processor suites. The topics of interest include, but are not limited to, the following: - Code profiling - Network profiling - Matching and scheduling tools - Analytic benchmarking - Problem mapping - Intelligent management - Orchestration tools - Metacompilers - Configuration levels and modes - Configuration switching - Crossover strategies - Processor selection criteria - Programming tools - Programming paradigms The workshop will feature an invited address, several sessions of submitted paper presentations, poster presentations, and a panel discussion. Proceedings will be available at the symposium. For further information, please contact one of the following: Richard Freund NCCOSC RDTE Div 423 San Diego, CA 92152-7433 Vox: (619) 553-4071 freund@superc.nosc.mil Vaidy Sunderam Dept. of Mathematics and Computer Science Emory University Atlanta, GA 30322, USA Vox: (404) 727-5926 vss@mathcs.emory.edu __________________________________________________________________ Workshop 3: All Day Tuesday 3rd WORKSHOP ON INPUT/OUTPUT IN PARALLEL AND DISTRIBUTED SYSTEMS Workshop Co-Chairs: Ravi Jain, Bellcore John Werth, University of Texas at Austin J.C. Browne, University of Texas at Austin __________________________________________________________________ Program Committee: Abhaya Asthana, AT&T Bell Labs Larry Berdahl, Lawrence Livermore Labs Peter Chen, University of Michigan Alok Choudhary, Syracuse University Peter Corbett, IBM Watson Research Center Tom Cormen, Dartmouth College Sam Fineberg, NASA Ames Shahram Ghandeharizadeh, USC Paul Messina, Caltech John Nickolls, MasPar The 1995 workshop will be the third year of the workshop; in the previous two years it was entitled the "Workshop on I/O in Parallel Computer Systems". As expressed in the title change, the 1995 workshop will encourage broad participation from researchers involved in all aspects of solutions to the I/O bottleneck in parallel and distributed systems. Papers dealing with innovative theoretical, algorithmic, operating systems, compiler, architectural, and application level approaches are of interest. In keeping with discussions held at the 1994 workshop, papers describing experimental and empirical investigations are particularly encouraged. Topics to be discussed include but are not limited to: - Experimental characterization of I/O demand - Performance modeling and evaluation - Design and implementation of I/O intensive applications - Theory and implementation of algorithms for I/O - I/O subsystem architecture - Language and compiler support for parallel I/O - Operating system support for parallel I/O - Real-time and multimedia I/O - Scheduling and resource allocation - Concurrent and parallel file systems The workshop will include research papers as well as a panel discussion and also a session where participants can discuss work in progress. It is sponsored by the IEEE Computer Society Technical Committee on Parallel Processing and is held in cooperation with ACM SIGARCH. For further information, please contact one of the following: Ravi Jain Bellcore MRE 2L-249 445 South Street Morristown, NJ 07962 Vox: (201) 829-4756 John Werth Dept of Computer Sciences Taylor Hall Room 2.124 University of Texas at Austin Austin, TX 78712 Vox: (512) 471-9583 To submit papers, send six copies of a manuscript (at most 20 pages long including figures and references) describing original unpublished research to John Werth by February 21, 1995. For enquiries by e-mail: iopads@thumper.bellcore.com __________________________________________________________________ Workshop 4: All Day Tuesday 2nd WORKSHOP ON RECONFIGURABLE ARCHITECTURES Workshop Chair: Hossam ElGindy, University of Newcastle, Australia __________________________________________________________________ Program Committee: Hussein Alnuweiri, University of British Columbia Philip MacKenzie, University of Texas Russ Miller, SUNY at Buffalo Stephan Olariu, Old Dominion University Viktor K. Prasanna, USC Assaf Schuster, Technion Arun Somani, University of Washington R. Vaidyanathan, Louisiana State University Reconfigurable architectures are the class of computing networks whose topology of the network outside the processors is fixed and where the internal connections between the I/O ports of each processor can be set locally during program execution. The 2nd workshop is organized for researchers who are active in the study of reconfigurable computing to present state of the art results and to assess future directions for this young field of research. Following the successful format of RAW '94, the workshop will feature several sessions of submitted paper presentations and an informal panel discussion. In addition to reporting on progress following the panel discussion of RAW '94, the presentations will cover the topics of: - Algorithms (arithmetic/geometric/randomised) - High performance computing with reconfigurable networks - New models - Complexity and power of different reconfiguration models - Implementations A special session will be dedicated to the use of FPGAs for implementing the reconfigurable computing paradigm. The workshop will also feature a session for discussing open problems and future of the reconfigurable hardware paradigm. The contributed papers for the 2nd workshop selected by the program committee from manuscripts submitted prior to January 1, 1995 will be announced at that date. For further consideration after January 1, contact the workshop chair prior to February 1, 1995. The workshop program and proceedings will be available by e-mail from the chair after March 1, 1995. For further information, please contact: Hossam ElGindy Department of Computer Science University of Newcastle Callaghan, NSW 2308, Australia Fax : +61 49 21 6929 Internet: hossam@cs.newcastle.edu.au __________________________________________________________________ Workshop 5: All Day Tuesday WORKSHOP ON SOLVING IRREGULAR PROBLEMS ON DISTRIBUTED MEMORY MACHINES Workshop Chair: Sanjay Ranka, Syracuse University __________________________________________________________________ Program Committee: Dharma P. Agrawal, North Carolina State University Prith Banerjee, University of Illinois, Urbana-Champaign Jim Browne, University of Texas at Austin Apostolos Gerasoulis, Rutgers University Viktor K. Prasanna, University of Southern California John Reif, Duke University Jose Rolim, University of Geneva Ponnuswamy Sadayappan, Ohio State University Sartaj Sahni, University of Florida Joel Saltz, University of Maryland Jon Webb, Carnegie Mellon University Kathy Yelick, University of California, Berkeley Parallel computing has been shown to be successful for the solution of a wide variety of structured and regular applications. However, research in parallelization of many irregular applications is still in its infancy. Examples of irregular applications include parallel search techniques, discrete event simulation, sparse matrix problems, unstructured and adaptive PDE solvers, particle dynamics problems, computer vision, and CAD of VLSI. Many currently supported industrial and scientific grand challenge applications fall into this category. This workshop will focus on architectures, algorithms, programming models, and languages for efficiently solving large irregular problems on parallel machines with distributed memory. These include machines with and without hardware support for multithreading, message passing, and shared memory. The workshop will feature invited and contributed papers, and panel sessions in an informal setting. The deadline for contributed papers was the first week of November. However, manuscripts of exceptionally high quality may be sent to the workshop chair for consideration prior to January 21, 1995. The workshop program and proceedings will be available via WWW from the chair after March 15, 1995. For further information, please contact the workshop chair at: Sanjay Ranka School of Computer Science 4-116 CST, Syracuse University Syracuse, NY 13244-4100, USA Internet: ranka@top.cis.syr.edu WWW: http://www.cis.syr.edu/people/ranka __________________________________________________________________ Workshop 6: All Day Tuesday WORKSHOP ON HIGH-SPEED NETWORK COMPUTING Workshop Co-Chairs: Hussein M. Alnuweiri, University of British Columbia Mounir Hamdi, Hong Kong University of Science and Technology __________________________________________________________________ Program Committee: S. Chanson, University of Science and Technology D.H.C. Du, University of Minnesota S. Hariri, Syracuse University R. Jain, Ohio State University A. Jajszczyk, Franco-Polish School T.V. Lakshman, Bell Communications Research W.T. O'Connell, AT&T Bell Laboratories D.K. Panda, Ohio State University C.S. Raghavendra, Washington State University T. Szymanski, McGill University ______________________________ OPENING PRESENTATION Gb/s Networks Are Here - Now Nanette J. Boden, Myricom ______________________________ The theme of this workshop centers on the impact of the emerging technology of high-speed networks in the area of high-performance parallel and distributed computing. High-speed internetworking is viewed by the information processing and telecommunications communities as the next major infrastructure industry. High-speed networks (such as SONET/ATM and high-speed local area networks) can be used for interconnecting a large number of (possibly distant) autonomous computers that operate in a distributed computing environment. Contributors to HiNet '95 explore the capabilities, point out the difficulties, and report on their experiences with high-speed networks when employed in high-performance computing environments. The following is a partial list of topics to be presented: - High-speed network protocols - ATM-based local area networks - Computing paradigms for high-speed networks - Distributed data base design and processing on high-speed networks - Programming environments and tools for high-speed network computing - Architecture and topology of high-speed networks - Efficient communication interfaces - Applications to parallel and distributed processing The workshop program will be finalized by February 15, 1995. For more information, please contact one of the following workshop co-chairs: H.M. Alnuweiri Department of Electrical Engineering University of British Columbia Vancouver, B.C. V6T 1Z4 Canada Vox: (604) 822-9185 Fax: (604) 822-5949 Internet: hussein@ee.ubc.ca M. Hamdi Department of Computer Science Hong Kong University of Science and Technology Kowloon, Hong Kong Vox: (852) 358-6984 Fax: (852) 358-1477 Internet: hamdi@cs.ust.hk __________________________________________________________________ Workshop 7: All Day Tuesday WORKSHOP ON JOB SCHEDULING STRATEGIES FOR PARALLEL PROCESSING Workshop Co-Chairs: Dror Feitelson, IBM Research Larry Rudolph, Hebrew University __________________________________________________________________ Program Committee: David Black, OSF Jim Cownie, Meiko Allan Gottlieb, NYU Mal Kalos, Cornell Theory Center Bradley C. Kuszmaul, MIT Miron Livny, University of Wisconsin, Madison Virginia Lo, University of Oregon Reagan Moore, SDSC Charlie Smith, Cray Research Mark Squillante, IBM Research Bernard Traversat, NASA Ames John Zahorjan, University of Washington As large parallel computers become more popular, scheduling strategies become more important as a means of balancing the need for exclusive use of the machine's resources and the desire to make these resources readily available to many diverse users. Neither sign-up sheets, naive time-slicing, nor naive space-slicing are suitable solutions. Moreover, there appears to be a divergence between what is studied, modeled, and analyzed in academic circles and the actual, sometimes ad-hoc, scheduling schemes developed by vendors and large installations. The workshop is intended to attract people from academia, supercomputing centers, national laboratories, and parallel computer vendors to address resource management issues in multiuser parallel systems, and attempt to resolve the conflicting goals such as short response times for interactive work, minimal interference with batch jobs, fairness to all users, and high system utilization. We hope to achieve a balance between reports of current practices in large and heavily-used installations, proposals of novel schemes that have not yet been tested in a real environment, and realistic models and analysis. The emphasis will be on practical designs in the context of real parallel operating systems. Topics of interest are: - Experience with scheduling policies on current systems - Performance implications of scheduling strategies - Fairness, priorities, and accounting issues - Workload characterization and classification - Support for different classes of jobs (e.g., interactive vs. batch) - Static vs. dynamic partitioning - Time slicing and gang scheduling - Scheduling to support a specific model of computation - Interaction of scheduling with memory management and I/O Papers should be no longer than 20 pages, including figures and references. All papers will be reviewed, and a proceedings will be distributed at the workshop. Send 6 copies of the paper by February 1, 1995 to: Dror Feitelson IBM T J Watson Research Center P O Box 218 Yorktown Heights, NY 10598 Internet: feit@watson.ibm.com Please include name, address, phone, and e-mail of contact author. Authors will be notified by March 15, 1995. Final copies are due on April 3, 1995. __________________________________________________________________ Tutorial 2 (Half-Day Morning) __________________________________________________________________ Techniques and Tools for Performance Tuning of Parallel and Distributed Scientific Applications Sekhar R. Sarukkai, Recom Technologies, NASA Ames Research Center Rob F. Van der Wijngaart, MCAT Institute, NASA Ames Research Center Who Should Attend: This tutorial is primarily aimed at developers of scientific applications on message passing architectures (networks of workstations and massively parallel computers) who are interested in acquiring skills for improving the performance of their programs and in learning about tools to support such efforts. Developers of parallel performance tuning tools will also find interest in the user's perspective of the uses and limitations of existing tools and latest developments and future requirements of performance tools. Course Description: This tutorial introduces techniques and tools for developing efficient message passing programs on state-of-the-art parallel and distributed machines, based on the practical experience of the presenters in performance tuning of real life scientific applications. Performance tuning strategies and tools for uniprocessor, vector processor and multiprocessor (distributed memory) systems are compared and contrasted. Memory access behavior and computation requirements of a number of scientific applications and means of optimizing their performance are discussed. The performance impact of the choice of data distributions, nature of memory hierarchy, overhead of the message passing library and operating system choices will be illustrated with examples. The material covered in the tutorial will help program developers avoid common performance pitfalls, detect performance bottlenecks using existing tools, and apply techniques for improving program performance. The use of various tools and efficacy of the techniques in improving performance is illustrated with a number of numerical examples executed using PVM on workstation clusters, MPI and NX on parallel machines such as the IBM SP-2, Intel Paragon and Intel iPSC/860. Limitations of current tools will be discussed. Directions of current and future research in the areas of scalability analysis tools, user control of operating system choices, monitoring HPF programs, and performance prediction methodologies will also be highlighted. Lecturers: Sekhar Sarukkai (PhD, Indiana Univ., 1992) has been working in the area of performance evaluation of parallel programs over the last 6 years. Since his graduation he has been working on performance evaluation tools at NASA Ames Research Center, in association with a number of application developers. His main research interests are in the area of performance prediction and tuning techniques and tools for parallel and distributed applications. Rob Van der Wijngaart (PhD, Stanford Univ., 1989) has been working on developing and implementing algorithms in scientific computing for 12 years. He has held positions with the Netherlands National Aerospace Laboratory, Shell Research, and at NASA Ames Research Center, where he is currently involved in parallelizing large programs for the simulation of fluid flow around aircraft. __________________________________________________________________ Tutorial 3 (Half-Day Afternoon) __________________________________________________________________ Parallel Processing for Multimedia Information Systems Arif Ghafoor, Purdue University Who Should Attend: Researchers, developers and practitioners in the area of parallel processing and multimedia information systems. A brief exposure to general concept about parallel processing and data management would be helpful. Course Description: Multimedia is a newly evolving application-oriented discipline with applications in business, education/library, manufacturing, CAD/CAM/CAI, medicine, entertainment, etc. A multimedia system requires integration of diverse areas in computational sciences, including parallel processing, computer vision and image processing, multimedia databases, and fast compression/decoding schemes. In this tutorial we present the current state-of-the-art in this area and discuss engineering challenges and computational requirements for managing and encoding/decoding massively large image and video data, generating and maintaining large scale indices for multimedia query processing and allowing content-based retrievals. We elaborate how parallel processing technology can play a key role for efficient management of multimedia data and can provide computational needs for real-time retrieval/storage of multimedia data and for efficient on-line query processing. We discuss some case studies of parallel architectures for their potential use as multimedia database machines and video servers. Lecturer: Arif Ghafoor received his BS degree in Electrical Engineering from Pakistan in 1976, and the MS, MPhil and PhD from Columbia University, in 1977, 1980, and 1985, respectively. Currently, he is an associate professor in the School of Electrical Engineering, Purdue University. His research interests include design and analysis of parallel and distributed systems and multimedia information systems. He has published numerous papers in these areas, in leading journals and conferences. Currently, he is directing a project in distributed multimedia systems at Purdue University. His research in these areas has been funded by many government and industrial organizations. He has served on the program committees of various IEEE conferences. Currently, he is serving on the editorial boards of Multimedia Systems (ACM/Springer Verlag Publishers) and the Journal of Multimedia Tools and Applications (Kluwer Publishers). He is also a guest/co-guest editor for upcoming special issues of Journal of Parallel and Distributed Computing, IEEE Journal on Selected Areas in Communication and Multimedia Systems Journal. These issues are on various aspects of multimedia systems. He is consultant to many companies including Bell Labs and General Electric. He is a senior member of IEEE and a member of Eta Kappa Nu. ****************************************************************** WEDNESDAY, APRIL 26 ****************************************************************** __________________________________________________________________ 8:30 AM - 9:30 AM KEYNOTE ADDRESS Modeling Parallel Communication Richard Karp, University of California, Berkeley __________________________________________________________________ 10:00 AM - 12:00 NOON SESSION 1 Networks Chair: Allan Gottlieb New York University __________________________________________________________________ The Partitioned Optical Passive Stars (POPS) Topology G. Gravenstreter, Rami Melhem, D.M. Chiarulli, S.P. Levitan and J.P. Teza, University of Pittsburgh The Mcube: A Symmetrical Cube Based Network with Twisted Links Nitin K. Singhvi and Kanad Ghose, State University of New York at Binghamton Multi-Mesh - An Efficient Topology for Parallel Processing Debasish Das and Bhabani P. Sinha, Indian Statistical Institute Accuracy vs. Performance in Parallel Simulation of Interconnection Networks Douglas C. Burger and David A. Wood, University of Wisconsin, Madison Fat-tree for Local Area Multiprocessors Qiang Li and David Gustavson, Santa Clara University On Generalized Fat Trees Sabine R. Oehring, Maximilian Ibel and Sajal K. Das, University of North Texas, Mohan J. Kumar, Curtin University of Technology, Srinivas Kankanahalli, West Virginia University __________________________________________________________________ 10:00 AM - 12:00 NOON SESSION 2 Scientific Computing I Chair: John Gustafson Ames Laboratory __________________________________________________________________ Parallel Monte Carlo Simulation of MBE Growth Isabel Beichl, National Institute of Standards and Technology, Y. Ansel Teng, Jet Propulsion Laboratory, Jim Blue, National Institute of Standards and Technology Monte Carlo and Molecular Dynamics Simulations Using P4 K.J. Runge, P. Lee, J. Correa, R.T. Scalettar and V. Oklobdzija, University of California, Davis Performance Evaluation of a Seismic Data Analysis Kernel on the KSR Multiprocessors Weiming Gu, Georgia Institute of Technology Performance Evaluation of a New Parallel Preconditioner Keith Gremban, Gary Miller and Marco Zagha, Carnegie Mellon University A General Purpose Sparse Matrix Parallel Solvers Package Hong Q. Ding and Robert D. Ferraro, California Institute of Technology Parallel Algorithms for Space-Time Adaptive Processing Serge J. Olszanskyj, James M. Lebak and Adam W. Bojanczyk, Cornell University __________________________________________________________________ 10:00 AM - 12:00 NOON SESSION 3 Graph Algorithms Chair: Oscar Ibarra University of California, Santa Barbara __________________________________________________________________ Parallel Algorithms for Maximum Matching in Interval Graphs M.G. Andrews, AT&T Bell Laboratories, M.J. Atallah, Purdue University, D.Z. Chen, University of Notre Dame, D.T. Lee, Northwestern University An EREW PRAM Fully-Dynamic Algorithm for MST Paolo Ferragina, Universita di Pisa Recognizing Depth-First-Search Trees in Parallel C.H. Peng, B.F. Wang and J.S. Wang, National Tsing Hua University Implementation of Parallel Graph Algorithms on a Massively Parallel SIMD Computer with Virtual Processing Tsan-sheng Hsu, Academia Sinica, Vijaya Ramachandran, University of Texas at Austin, Nathaniel Dean, Bellcore A Highly Parallel Algorithm to Approximate MaxCut on Distributed Memory Architectures Steven Homer and Marcus Peinado, Boston University A Distributed Algorithm for the Detection of Local Cycles and Knots Azzedine Boukerche and Carl Tropper, McGill University __________________________________________________________________ 1:30 PM - 3:30 PM SESSION 4 Communication and I/O Chair: C.S. Raghavendra Washington State University __________________________________________________________________ PCODE: An Efficient and Reliable Collective Communication Protocol for Unreliable Broadcast Domains Jehoshua Bruck, California Institute of Technology, Danny Dolev, Hebrew University, Ching-Tien Ho, IBM Almaden Research Center, Rimon Orni, University of Maryland, Ray Strong, IBM Almaden Research Center Experience with Active Messages on the Meiko CS-2 Klaus E. Schauser and Chris J. Scheiman, University of California, Santa Barbara Performance of the Vesta Parallel File System Dror G. Feitelson, Peter F. Corbett and Jean-Pierre Prost, IBM T.J. Watson Research Center VIP-FS: A VIrtual, Parallel File System for High Performance Parallel and Distributed Computing Juan Miguel del Rosario, Michael Harry and Alok Choudhary, Syracuse University Characterizing Parallel File-Access Patterns on a Large-Scale Multiprocessor Apratim Purakayastha and Carla Schlatter Ellis, Duke University, David Kotz and Nils Nieuwejaar, Dartmouth College, Michael Best, MIT and Thinking Machines Corporation Parallel Algorithms for Database Operations Uzi Vishkin, University of Maryland and Rajeev Raman, King's College __________________________________________________________________ 1:30 PM - 3:30 PM SESSION 5 Non-Numeric Algorithms and Applications I Chair: Sanjay Ranka Syracuse University __________________________________________________________________ Solving the Traveling Salesman Problem with a Distributed Branch-and-Bound Algorithm on a 1024 Processor Network S. Tschoke, R. Luling and B. Monien, University of Paderborn Sequence Comparison on a Cluster of Workstations Using the PVM System X. Guan, R.J. Mural and E.C. Uberbacher, Oak Ridge National Laboratory B-Trees with Relaxed Balance Kim S. Larsen and Rolf Fagerberg, Odense University Fast Output Sensitive Algorithms for Minimum and Related Problems with Small Integer Inputs Omer Berkman, King's College, Yossi Matias, AT&T Bell Laboratories A Note on Simulations and Integer Sorting Yossi Matias, AT&T Bell Laboratories, Uzi Vishkin, University of Maryland The Parameterized Round-Robin Partitioned Algorithm for Parallel External Sort Honesty C. Young and Arun N. Swami, IBM Almaden Research Center __________________________________________________________________ 1:30 PM - 3:30 PM SESSION 6 Partitioning and Data Distribution Chair: Prith Banerjee University of Illinois, Urbana-Champaign __________________________________________________________________ Partitioning Regular Grid Applications with Irregular Boundaries for Cache- Coherent Multiprocessors Yang Zeng, University of Michigan, Santosh G. Abraham, Hewlett-Packard Laboratories Statement-Level Independent Partitioning of Uniform Recurrences J. Ramanujam and S. Vasanthakumar, Louisiana State University A Synthesis Method of LSGP Partitioning for Given-Shape Regular Arrays G.M. Megson and Xian Chen, University of Newcastle Hierarchical Tiling: A Framework for Multi-Level Parallelism and Locality Larry Carter and Jeanne Ferrante, University of California, San Diego, Susan Flynn Hummel, Polytechnic University and IBM T.J. Watson Research Center Replication of Uniformly Accessed Shared Data for Large-Scale Data-Parallel Algorithms Chung-Ming Chen and Soo-Young Lee, Cornell University The Emulation Problem on Trees Daw-Jong Shyu, Biing-Feng Wang and Chuan-Yi Tang, National Tsing Hua University __________________________________________________________________ 4:00 PM - 6:00 PM SESSION 7 Synchronization and Scheduling Chair: D.K. Panda Ohio State University __________________________________________________________________ A Performance Comparison of Fast Distributed Synchronization Algorithms Theodore Johnson, University of Florida Allnode Barrier Synchronization Network Howard T. Olnowich, IBM Corporation Efficient Implementation of Mutual Exclusion Locks in Large Multiprocessors Nian-Feng Tzeng and Shiwa S. Fu, University of Southwestern Louisiana Bicriterion Scheduling of Identical Processing Time Jobs by Uniform Processors A. Tuzikov and M. Makhaniok, Academy of Sciences of Republic Belarus, R. Manner, Universitat Mannheim and Universitat Heidelberg Fast Scheduling of Periodic Tasks on Multiple Resources Sanjoy K. Baruah, University of Vermont, Johannes Gehrke and C. Greg Plaxton, University of Texas at Austin A Parallel Approach for Multiprocessor Scheduling Ishfaq Ahmad and Yu-Kwong Kwok, Hong Kong University of Science and Technology __________________________________________________________________ 4:00 PM - 6:00 PM SESSION 8 Parallel Algorithms on Networks Chair: David Nassimi New Jersey Institute of Technology __________________________________________________________________ A Simple Voronoi Diagram Algorithm for a Reconfigurable Mesh Hossam ElGindy and Lachlan Wetherall, University of Newcastle Robust Shearsort on Incomplete Bypass Meshes Behrooz Parhami and Ching Yu Hung, University of California, Santa Barbara Fault-Tolerant Sorting in SIMD Hypercubes A. Mishra, Y. Chang, L. Bhuyan and F. Lombardi, Texas A&M University A Faster Sorting Algorithm in the Broadcast Communication Model Stephan Olariu and James L. Schwing, Old Dominion University Efficient Algorithms for Global Data Communication on the Multidimensional Torus Network Paraskevi Fragopoulou and Selim Akl, Queen's University A Near-Optimal Algorithm for Gossiping in a d-Dimensional Mesh Bus Interconnection Network Arun Jagota, University of Memphis __________________________________________________________________ 4:00 PM - 6:00 PM SESSION 9 Compiler Techniques Chair: Alan Sussman University of Maryland __________________________________________________________________ Combining Dependence and Data Flow Anaylses to Optimize Communication Ken Kennedy and Nenad Nedeljkovic, Rice University Parallelizing WHILE Loops for Multiprocessor Systems Lawrence Rauchwerger and David Padua, University of Illinois, Urbana-Champaign Symbolic Range Propagation William Blume and Rudolf Eigenmann, University of Illinois, Urbana-Champaign Construction of DO Loops for Non-Convex Iteration Spaces and Its Applications in Code Generation for Shared and Distributed Memory Machines Jingling Xue, Nanyang Technological University Compiler Techniques for Increasing CU/PE Overlap in SIMD Machines Gene Saghi, University of Idaho, Howard Jay Siegel, Purdue University __________________________________________________________________ 7:30 PM IPPS '95 BANQUET __________________________________________________________________ Andre LeCault of Science Applications International Corporation (SAIC) will host the IPPS banquet. There will be an after dinner talk and demonstration by Richard Freund of NRaD entitled 'Global Heterogeneous Scheduling.' ****************************************************************** THURSDAY, APRIL 27 ****************************************************************** __________________________________________________________________ 8:30 AM - 9:30 AM KEYNOTE ADDRESS The New Era of MPPs: Moderately Parallel Processors Forest Baskett, Silicon Graphics, Inc. __________________________________________________________________ 10:00 AM - 12:00 NOON SESSION 10 Parallel Architectures Chair: Jack Dennis Massachusetts Institute of Technology __________________________________________________________________ The Impact of Pipelining on SIMD Architectures James D. Allen and David E. Schimmel, Georgia Institute of Technology An Assessment of COMA Multiprocessors Gyungho Lee, University of Minnesota A Workload Characterization for Coarse-Grain Multiprocessors Christopher Connelly and Carla Schlatter Ellis, Duke University Unified vs. Split TLBs and Caches in Shared-Memory MP Systems Qidong Xu and Patricia J. Teller, New Mexico State University Access Order to Avoid Inter-Vector-Conflicts in Complex Memory Systems A.M. del Corral and J.M. Llaberia, Universitat Politecnica de Catalunya A Unified Theory for a Traffic Analysis in Product Networks Abdelghani Bellaachia, University of Qatar, Abdou Youssef, George Washington University __________________________________________________________________ 10:00 AM - 12:00 NOON SESSION 11 Scientific Computing II Chair: Vipin Kumar University of Minnesota __________________________________________________________________ Geometric Mesh Partitioning: Implementation and Experiments John R. Gilbert, Xerox Palo Alto Research Center, Gary L. Miller, Carnegie Mellon University, Shang-Hua Teng, University of Minnesota Non-Uniform 2-D Grid Partitioning for Heterogeneous Parallel Architectures Phyllis Crandall, University of Illinois, Urbana-Champaign, Michael J. Quinn, Oregon State University Toward Data Distribution Independent Parallel Matrix Multiplication Hyuk J. Lee and Jose A.B. Fortes, Purdue University Multi-Phase Array Redistribution: Modeling and Evaluation S.D. Kaushik and C.-H Huang, Ohio State University, J. Ramanujam, Louisiana State University, P. Sadayappan, Ohio State University Minimizing Communication Overhead for Matrix Inversion Algorithms on Hypercubes Xiadong Wang and Vwani P. Roychowdhury, Purdue University Folding Spatial Image Filters on the CM-5 Sandra G. Dykes and Xiaodong Zhang, University of Texas at San Antonio __________________________________________________________________ 10:00 AM - 12:00 NOON SESSION 12 Resource Management Chair: Sartaj Sahni University of Florida __________________________________________________________________ Robust Parallel Resource Management in Shared Memory Multiprocessor Systems I-Ling Yen, Michigan State University, Farokh B. Bastani, University of Houston Efficient Processor Allocation for 3D Tori Wenjian Qiao and Lionel M. Ni, Michigan State University An Analytical Comparison of Nearest Neighbor Algorithms for Load Balancing in Parallel Computers Chengzhong Xu, Burkhard Monien and Reinhard Luling, University of Paderborn, Francis Lau, University of Hong Kong Using Simple Page Placement Policies to Reduce the Cost of Cache Fills in Coherent Shared-Memory Systems Michael Marchetti, Leonidas Kontothanassis, Ricardo Bianchini and Michael Scott, University of Rochester Operating System Support for Concurrent Remote Task Creation Dejan S. Milojicic, David Black and Steve Sears, OSF Research Institute __________________________________________________________________ INDUSTRIAL TRACK: INVITED VENDOR PRESENTATIONS Industrial Track Chair: John K. Antonio, Purdue University __________________________________________________________________ 10:00 AM - 12:00 NOON INDUSTRIAL TRACK Session-I Architectures and Instrumentation Chair: Richard C. Metzger Rome Laboratory __________________________________________________________________ Honeywell Technology Center Topic: SPI: An Instrumentation Development Environment for Parallel/Distributed Systems Authors: Devesh Bhatt, Senior Principal Research Scientist, Rakesh Jha, Senior Principal Research Scientist, Todd Steeves, Principal Research Scientist, Rashmi Bhatt, Research Associate, and David Wills, Research Associate Litton Guidance and Control Systems, Inc. & MasPar Computer Corporation Topic: A Rugged Scalable Parallel System Authors: Alan Smeyne, Manager, Advanced Systems (Litton) and John R. Nickolls, Vice President and Co-Founder (MasPar) Mercury Computer Systems, Inc. Topic: The RACE Network Architecture Author: Bradley C. Kuszmaul, Consultant __________________________________________________________________ 1:30 PM - 3:30 PM INDUSTRIAL TRACK Session-II Applications and Programming Chair: Sajal K. Das University of North Texas __________________________________________________________________ nCUBE Topic: Parallel Innovation for the Real World Author: Peter Madams, Vice President, Software Technology The Portland Group, Inc. (PGI) Topic: Analysis & Performance Results of Several High Performance Fortran Benchmark Programs Authors: Douglas Miles, Technical Marketing, Larry Meadows, Chief Technical Officer, and Mark Young, Technical Marketing Virtual Computer Corporation Topic: Programming Hardware Objects Authors: John Schewel, Vice President of Sales & Marketing, Michael Thornburg, Vice President of Operations, and Steve Casselman, President __________________________________________________________________ 1:30 PM - 3:30 PM SESSION 13 Routing Chair: Assaf Schuster Technion __________________________________________________________________ A Novel Deadlock-Free Routing Technique for a Class of de Bruijn Graph Based Networks Hyunmin Park and Dharma P. Agrawal, North Carolina State University An Efficient Scheme for Complete Exchange in 2D Tori Yu-Chee Tseng, Chung-Hua Polytechnic Institute, Sandeep K.S. Gupta and Dhabaleswar K. Panda, Ohio State University DISHA: A Deadlock Recovery Scheme for Fully Adaptive Routing Anjan K.V. and Timothy Mark Pinkston, University of Southern California The Universality of the Total-Exchange Communication Primitive Satish B. Rao, NEC Research Institute, Thanasis Tsantilas, Columbia University, Mark Goudreau, University of Central Florida A Fast Distributed Optimal Routing Algorithm for Multicommodity Large Data Networks Garng M. Huang and Shan Zhu, Texas A&M University Efficient Routing and Message Bounds for Optimal Parallel Algorithms Xiaotie Deng and Patrick Dymond, York University __________________________________________________________________ 1:30 PM - 3:30 PM SESSION 14 Non-Numeric Algorithms and Applications II Chair: Charles Weems University of Massachusetts __________________________________________________________________ &ACE: A High-Performance Parallel Prolog System for Parallel Symbolic Computing Enrico Pontelli and Gopal Gupta, New Mexico State University, Manuel Hermenegildo, University of Madrid Process Combination to Increase Event Granularity in Parallel Logic Simulation Timothy J. McBrayer and Philip Wilsey, University of Cincinnati Parallel Algorithms for Logic Synthesis Using the MIS Approach Kaushik De, LSI Logic Corporation, John Chandy, Steven Parkes and Prithviraj Banerjee, University of Illinois Load Sharing in the Training Set Partition Algorithm for Parallel Neural Learning Bernard Girau and Helene Paugam-Moisy, CNRS Reconfiguration and Experiments in a Faulty Hypercube Guanghua Lin and Nian-Feng Tzeng, University of Southwestern Louisiana Time Scale Combining of Conservative Parallel Discrete Event Simulations Hatem Sellami and Sudhakar Yalamanchili, Georgia Institute of Technology __________________________________________________________________ 1:30 PM - 3:30 PM SESSION 15 Tracing and Performance Tools Chair: Andrew Chien University of Illinois, Urbana-Champaign __________________________________________________________________ Capturing and Automating Performance Diagnosis: The Poirot Approach B. Robert Helm, Allen D. Malony and Stephen F. Fickas, University of Oregon Monitoring and Controlling Remote Parallel Computations Using Schooner Zhanliang Chen and Richard D. Schlichting, University of Arizona Automated Instrumentation and Monitoring of Data Movement in Parallel Programs Sekhar R. Sarukkai, Jerry Yan and Melisa Schmidt, NASA Ames Research Center Performance Debugging and Prediction for Portable Parallel Execution on MIMD Architectures Gopal Chillariga and Balkrishna Ramkumar, University of Iowa Symbolic Performance Prediction of Scalable Parallel Programs Mark J. Clement, Brigham Young University, Michael J. Quinn, Oregon State University A Visualization-Based Environment for Top-Down Debugging of Parallel Programs Joseph L. Sharnowski and Betty H.C. Cheng, Michigan State University __________________________________________________________________ 4:00 PM - 6:00 PM PANEL 1 __________________________________________________________________ Networked Parallel Processing: Is It the Future of Scalable Computing ? Moderator: Kai Hwang, University of Southern California Panelists: Tilak Agerwala, IBM Kingston, New York James Cownie, Meiko Corp. David Du, University of Minnesota Kai Li, Princeton University Doug Pase, Cray Research, Inc. Michael Quinn, Oregon State University John Silvester, University of Southern California Richard Stellwagen, NCR/AT&T, San Diego Steve Wallach, Convex Computer Corp. David Wood, University of Wisconsin, Madison Key topics: - High-speed network infrastructure and information superhighway support for distributed computing and parallel processing. - Heterogeneous programming paradigms for networked computer systems, such as networks of workstations (NOW), symmetric multiprocessors, message-passing multicomputers, and massively parallel processors. - Tradeoffs between computation and communications requirements, distributed computing environments (DCE), and distributed management environments (DME). - Distributed and network applications for numeric, database, video, multimedia, and transaction processing, etc. - Research/development projects, testbeds, experiments, benchmarks, transportable parallel software, and distributed resources management. ****************************************************************** FRIDAY, APRIL 28 ****************************************************************** __________________________________________________________________ 8:30 AM - 9:30 AM KEYNOTE ADDRESS Parallel Computing Sartaj Sahni, University of Florida __________________________________________________________________ 10:00 AM - 12:00 NOON SESSION 16 Global Operations and Clocks Chair: James Goodman University of Wisconsin, Madison __________________________________________________________________ Global Reduction in Wormhole k-ary n-cube Networks with Multidestination Exchange Worms Dhabaleswar K. Panda, Ohio State University Broadcasting on the Star and Pancake Interconnection Networks Ke Qiu, Acadia University Time Synchronization on SP1 and SP2 Parallel Systems Bulent Abali and Craig B. Stunkel, IBM T.J. Watson Research Center Hardware for Fast Global Operations on Multicomputers Douglas V. Hall and Michael A. Driscoll, Portland State University Timestamp Consistency and Trace-Driven Analysis for Distributed Parallel Systems C. Eric Wu, Yew-Huey Liu and Yarsun Hsu, IBM T.J. Watson Research Center __________________________________________________________________ 10:00 AM - 12:00 NOON SESSION 17 Visualization and Image Processing Chair: Charles Weems University of Massachusetts __________________________________________________________________ Parallel Implementation of Ray-Tracing Algorithm on the Intel Delta Parallel Computer Tong-Yee Lee and C.S. Raghavendra, Washington State University, John B. Nicholas, Pacific Northwest Laboratory Parallel Volume Rendering Ruediger Westermann, German National Research Center for Computer Science Parallel Implementation of Volume Rendering on Denali Graphics Systems Sheng-Yih Guan, Kubota Graphics Corporation, Avi Bleiweiss, Silicon Graphics, Richard Lipes, Kubota Graphics Corporation An Optimal Parallel Algorithm for Volume Ray Casting Vineet Goel and Amar Mukherjee, University of Central Florida Parallel Motion Computing on the MasPar MP-2 Machine A. Branca and A. Distante, CNR-IESI, H.R.P. Ellingworth, MasPar Computer Ltd. Scalable Parallel Implementations of List Ranking on Fine-Grained Machines Jamshed N. Patel, Ashfaq A. Khokhar and Leah H. Jamieson, Purdue University __________________________________________________________________ 10:00 AM - 12:00 NOON SESSION 18 Parallel Programming Chair: Joel Saltz University of Maryland __________________________________________________________________ Integrating Task and Data Parallelism with the Collective Communication Archetype K. Mani Chandy, Rajit Manohar, Berna L. Massingill and Daniel I. Meiron, California Institute of Technology Divide-and-Conquer Programming on MIMD Computers Santhosh Kumaran and Michael J. Quinn, Oregon State University New Data-Parallel Language Features for Sparse Matrix Computations Manuel Ujaldon and Emilio Zapata, University of Malaga, Barbara M. Chapman and Hans P. Zima, University of Vienna Visualizing the Execution of High Performance Fortran (HPF) Programs Doug Kimelman, Pradeep Mittal, Edith Schonberg, Peter F. Sweeney, Ko-Yang Wang and Dror Zernik, IBM T.J. Watson Research Center Parallelization of a Wave Propagation Application using a Data Parallel Compiler Francoise Andre, Marc Le Fur, Yves Maheo and Jean-Louis Pazat, IRISA Derivation of Data Parallel Code from a Functional Program Patrice Quinton, IRISA, Sanjay Rajopadhye and Doran Wilde, Oregon State University __________________________________________________________________ 1:30 PM - 3:30 PM SESSION 19 Special Purpose Architectures Chair: N. Ranganathan University of South Florida __________________________________________________________________ Synapse-1: A High-Speed General Purpose Parallel Neurocomputer System U. Ramacher, W. Raab, J. Anlauf, U. Hachmann, J. Beichter, N. Bruls, M. Webeling and E. Sicheneder, Siemens AG, J. Glab, A. Wurz and R. Manner, Universitat Mannheim NERV: A Parallel Processor for Standard Genetic Algorithms R. Hauser and R. Manner, Universitat Mannheim, M. Makhaniok, Belarus Academy of Sciences Performance Measurements of a Concurrent Production System Architecture without Global Synchronization Jose Nelson Amaral and Joydeep Ghosh, University of Texas at Austin Parallel Processing Algorithms and Architecture for Multimedia On-Demand Servers Raja Neogi, Motorola Inc., Meghanad D. Wagh, Lehigh University Evaluating Bayes Nets with Concurrent Process Networks E. Tick, University of Oregon, Bruce D'Ambrosio, Oregon State University __________________________________________________________________ 1:30 PM - 3:30 PM SESSION 20 Run-Time Support for Irregular Parallelism Chair: Leah Jamieson Purdue University __________________________________________________________________ Index Translation Schemes for Adaptive Computations on Distributed Memory Multicomputers Bongki Moon, Mustafa Uysal and Joel Saltz, University of Maryland Exploiting Spatial Regularity in Irregular Interactive Applications Antonio Lain and Prithviraj Banerjee, University of Illinois, Urbana-Champaign Data Parallel Programming in an Adaptive Environment Guy Edjlali, Establissement Technique Central de l'Armament, Gagan Agrawal, Alan Sussman and Joel Saltz, University of Maryland Run-Time Support for Asynchronous Parallel Computations Guillermo A. Alvarez, University of California, San Diego, Marcelo O. Fernandez, Rogelio Alvez, IBM Argentina, Sylvia Rodriguez, Escuela Superior Latinoamericana de Informatica, Julio A. Sanchez Avalos, IBM Argentina, Jorge L.C. Sanz, University of Illinois, Urbana-Champaign An Adaptive Synchronization Method for Unpredictable Communication Patterns in Data Parallel Programs Sundeep Prakash and Rajive Bagrodia, University of California, Los Angeles __________________________________________________________________ 4:00 PM - 6:00 PM PANEL 2 __________________________________________________________________ Different Approaches to Parallel Computing Education Moderator: Russ Miller, Department of Computer Science, State University of New York at Buffalo Panelists: Daniel C. Hyde, Computer Science Department, Bucknell University David Kotz, Department of Computer Science, Dartmouth College Gordon Makinson, Senior Lecturer Computer Science, Computing Laboratory, University of Kent, UK P. Takis Metaxas, Computer Science Department, Wellesley College Chris Nevison, Computer Science Department, Colgate University Nan C. Schaller, Computer Science Department, Rochester Institute of Technology Greg V. Wilson, Computer Science Department, University of Toronto Description: A generic parallel computing curriculum has yet to emerge. This is evidenced by the myriad of approaches to teaching parallel computing that are represented in introductory texts. Last year, our panel presented different approaches to parallel processing education from the point of view of colleges, universities, supercomputing centers, and parallel computing vendors. The focus of that panel was on the issues involved in incorporating parallel computing into the post-secondary education process. This year, we bring together panelists who are approaching parallel computing education in very different and innovative ways - different from each other and different from the panelists last year. Topics to be covered include teaching parallel computing to freshmen, parallel computing by CD-ROM, cluster computing, laboratories for parallel computing, the Edinburgh Parallel Computing Centre Summer Scholarship Programme, and surfing the parallel computing web. ****************************************************************** LOCATION ****************************************************************** SYMPOSIUM LOCATION Fess Parker's Red Lion Resort in Santa Barbara overlooks the Pacific Ocean in an area described as the American Riviera where the sun shines more than 300 days a year. Santa Barbara is an historic, village-like community situated one third of the way north along the coast from Los Angeles to San Francisco. Many shops, cafes, and museums are within walking distance of the Red Lion. The area's temperate climate creates ideal conditions for tennis, golf, and rollerskating, and the salty water supports surfing, sailing, and fishing. All of these activities and more - basketball, horseback riding, polo! - may be arranged right at Fess Parker's. Across the street the Cabrillo Path unwinds 22 miles for runners, walkers and cyclists (they rent bikes) and at the end of every day there is sunset watching! As shown on the map (opposite page), there are many places to visit in Santa Barbara. Local sightseeing can be done from open air trolleys, and tour boats to the Channel Islands depart daily from the nearby Stearns Wharf. If you have already toured Disneyland, Universal Studios, and Knott's Berry Farm, day trips in other directions include Hearst Castle, the Danish village of Solvang, and the wine country. AIR TRANSPORTATION The Red Lion provides free airport transportation from the Santa Barbara Airport which is located only 20 minutes from the hotel. The airport is served by American, American Eagle, Skywest/Delta connections, United, United Express and USAIR Express. All major airlines fly into Los Angeles International Airport (LAX) which is less than a 2 hour drive from Santa Barbara. GROUND TRANSPORTATION Many local attractions are within walking distance and, as noted, the downtown area is served by the Santa Barbara Trolley Company. For day trips, excursion buses and auto rentals may be arranged at the Red Lion. ACCOMMODATIONS The special IPPS '95 rates at Fess Parker's Red Lion Resort are $110 for singles and doubles, $125 for triples, and $140 for quadruples. These rates are also available 2 days before and after the symposium. Guest rooms are as little as thirty feet from the ocean with a view patio or balcony. The spacious rooms include double vanities, mini bars, and remote control TV. And as described above, there are recreational resources to meet everyone's interest. As we discovered in 1994, the special IPPS rate makes this resort setting an ideal location to have family and friends join you while you also enjoy symposium events. ------------------------------------------------------------------------ IPPS '95 - 9TH INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM APRIL 24-28, 1994 - FESS PARKER'S RED LION RESORT - SANTA BARBARA - CALIFORNIA - USA ------------------------------------------------------------------------ ADVANCE REGISTRATION PLEASE MAIL OR FAX TO: IEEE Computer Society VOX: (202) 371-1013 1730 Massachusetts Avenue, NW FAX: (202) 728-0884 Washington, DC 20036 Attn: CONFERENCE DEPARTMENT PLEASE PRINT: NAME: _______________________________________________________________ LAST/FAMILY FIRST M.I. NAME ON BADGE COMPANY: ____________________________________________________________ ADDRESS/MAILSTOP: ___________________________________________________ CITY/STATE/ZIP/COUNTRY: _____________________________________________ DAYTIME NUMBER: __________________ FAX NUMBER: ____________________ IEEE MEMBERSHIP NUMBER: ____________ E-MAIL: _______________________ DO YOU HAVE ANY SPECIAL NEEDS? ______________________________________ DO NOT INCLUDE MY MAILING ADDRESS ON:______ NON-SOCIETY MAILING LISTS ______ MEETING ATTENDEE LISTS ______________________________________________________________________________ PLEASE CIRCLE APPROPRIATE FEES: ..... SYMPOSIUM REGISTRATION FEES: _____________________________________________________ Advance Registration (Until March 24, 1995) Member Non-member Student $275 $345 $150 _____________________________________________________ Late/Onsite Registration (After March 31, 1995) Member Non-member Student $330 $415 $200 _____________________________________________________ ..... TUTORIAL REGISTRATION FEE: (Per tutorial) ADVANCE REGISTRATION (Until March 24, 1995) Member Non-member $150 $200 Late/Onsite Registration (After March 31,1995) Member Non-member $190 $235 ___________________________________________________________________________ CHECK TUTORIAL(S) YOU WISH TO ATTEND: MONDAY, APRIL 24TH ( ) 1. Architecture-Independent Data Parallel Computing on Coarse Grained Machines(AFTERNOON) TUESDAY, APRIL 25TH ( ) 2. Techniques and Tools for Performance Tuning of Parallel and Distributed Scientific Applications (MORNING) ( ) 3. Parallel Processing for Multimedia Information Systems (AFTERNOON) COMPUTE PAYMENT BELOW: Symposium Fee $_______ Tutorial Fee $_______ TOTAL ENCLOSED $_______ (in U.S. dollars) PAYMENT MUST BE ENCLOSED. PLEASE MAKE CHECKS PAYABLE TO IEEE COMPUTER SOCIETY. ALL CHECKS MUST BE IN U.S. DOLLARS DRAWN ON U.S. BANKS METHOD OF PAYMENT: _____ PERSONAL CHECK _____ COMPANY CHECK _____ TRAVELER'S CHECKS _____ AMERICAN EXPRESS _____ MASTERCARD _____ VISA _____ DINERS CLUB _____ PURCHASE ORDER (Original must accompany registration form.) CREDIT CARD NUMBER: ________________________________________________ EXP. DATE: _______________ CARDHOLDER NAME: _____________________________________________________ SIGNATURE: ____________________________________________________________ Written requests for refund must be received in the IEEE Computer Society office no later than March 24, 1995. Refunds are subject to a $50 processing fee. All no-show registrations will be billed in full. Registrations after March 31, 1995 will be accepted on-site only. (PLEASE MAKE HOUSING RESERVATIONS DIRECTLY WITH HOTEL. SEE REGISTRATION FORM.) ______________________________________________________________________ IPPS '95 HOTEL RESERVATION FORM FESS PARKER'S RED LION RESORT Please reserve accommodation for: Name:___________________________________________________ Mailing Address:__________________________________________________ Home/Business phone:____________________________________________________________ Arrival Date: __________________ Arrival Time:__________ Departing Date:_______________ IPPS '95 special group rates at Fess Parker's Red Lion Resort are $110 (singles & doubles), $125 (triples) and $140 (quadruples). These rates are available 2 days before and after the symposium. Reservations must be received prior to March 25, 1995 to be eligible for the group rate. Rates subject to 10% State & City tax. _____________________________________________________________________________ 9th International Parallel Processing Symposium April 24-28, 1995 - Santa Barbara, California - USA RESERVATIONS MAY BE CALLED IN OR FAXED TO THE RED LION. Vox: (805) 564-4333 x4316/ (800) 879-2929 Fax: (805) 564-4964 USE THIS FORM TO FAX OR MAIL. SEND ATTN: RESERVATIONS. Red Lion - 633 East Cabrillo Blvd - Santa Barbara, CA 93103 Check-in time is 4:00 pm. Check-out time is 12 noon. No reservation will be held after 6:00 pm unless guaranteed by deposit or major credit card. There is a 72-hour cancellation policy and any room held after 6:00 pm and not occupied will be charged to the guarantor. For credit card: Name of credit card (e.g., VISA)___________________________________________ Card Number________________________________ Expiration Date________________ Signature of Cardholder____________________________________________________