------------------------------------------------------------------------ IPPS'94 - 8TH INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM APRIL 26-29, 1994 - THE WESTIN REGINA RESORT - CANCUN, MEXICO ADVANCE PROGRAM ________________________________________________________________________ SYMPOSIUM ORGANIZATION _____________________________________________________ SYMPOSIUM CHAIR Viktor K. Prasanna, University of Southern California _____________________________________________________ PROGRAM CHAIR H.J. Siegel, Purdue University PROGRAM VICE-CHAIRS Algorithms: Mikhail J. Atallah, Purdue University Applications: Sartaj Sahni, University of Florida Architecture: Trevor Mudge, University of Michigan Software: Alexandru Nicolau, University of California at Irvine PROCEEDINGS CHAIR Nathaniel J. Davis, IV, Virginia Polytechnic Institute and State University PARALLEL SYSTEMS CHAIR Hussein M. Alnuweiri, University of British Columbia TUTORIALS CHAIR Alok Choudhary, Syracuse University INDUSTRIAL TRACK CHAIR John K. Antonio, 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: D.K. Panda, Ohio State University Asia: Pankaj Jalote, Indian Institute of Technology, Kanpur Europe: Stefan Lamberts, Technische Universitaet Muenchen Pacific Rim: David K. Kahaner, ONR Asia PROGRAM COMMITTEE John K. Antonio, Purdue University Prith Banerjee, University of Illinois Ken Batcher, Kent State University Francine Berman, University of California at San Diego Thomas L. Casavant, University of Iowa Janice Cuny, University of Massachusetts Jack Dennis, Massachusetts Institute of Technology Jack Dongarra, University of Tennessee and Oak Ridge National Laboratory Mary M. Eshaghian, New Jersey Institute of Technology Mike Flynn, Stanford University Geoffrey Fox, Syracuse University Richard F. Freund, NRaD Susanne Hambrusch, Purdue University Oscar H. Ibarra, University of California at Santa Barbara Joseph Ja'Ja', University of Maryland Leah H. Jamieson, Purdue University Mary Jane Irwin, Penn State University Lennart Johnsson, Thinking Machines Corporation and Harvard University Kai Li, Princeton University Virginia Lo, University of Oregon Richard C. Metzger, Rome Laboratory Russ Miller, SUNY- Buffalo David Nassimi, New Jersey Institute of Technology Lionel M. Ni, Michigan State University John R. Nickolls, MasPar Computer Corporation David Padua, University of Illinois Yale Patt, University of Michigan Donna Quammen, George Mason University C. S. Raghavendra, Washington State University Isaac Scherson, University of California at Irvine Pearl Wang, George Mason University Elizabeth Williams, Supercomputing Research Center Michael Wolfe, Oregon Graduate Institute PROGRAM COMMITTEE COORDINATOR Janet McWaid, Caltech CHAIRMAN EMERITUS Larry Canter, Computer Systems Approach, Inc. STEERING COMMITTEE CHAIR George Westrom, Odetics, Inc. SYMPOSIUM ADVISORY COMMITTEE Vijay P. Bhatkar, CDAC, India Michel Cosnard, Ecole Normale Superieure de Lyon, France Kai Hwang, University of Southern California F. Thomson Leighton, Massachusetts Institute of Technology Michael J. Quinn, Oregon State University Larry Snyder, University of Washington SPONSORSHIP The 8th 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'94 is being provided by the companies and organizations listed on the inside cover. IPPS'94 PROCEEDINGS The 1994 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. All registrants may obtain proceedings from one of the six workshops. Additional copies should be arranged with each workshop chair. PROGRAM: IPPS'94 LOCATION See the back of the program for information about Cancun and the Westin Regina Resort. It is recommended that travelers make advance plans for any special recreational or sightseeing activities. Similarly, travelers are advised to make airline reservations at least two months in advance. IPPS'94 PROGRAM SCHEDULE Registration will be open Monday evening to accommodate early arrivals. Our program for Tuesday through Friday will cover all areas of parallel processing, including experimental and commercial systems. The customary IPPS events will include contributed technical papers, keynote speeches, workshops, panels, a parallel systems fair, vendor presentations, and tutorials. On Wednesday and Thursday there will be three-hour lunch breaks so that attendees can hold relaxed technical discussions on the beach. CONTRIBUTED PAPERS There will be 127 contributed technical papers, selected from 395 submissions, presented in 21 sessions. Topics span the design, development, use, and analysis of parallel processing systems. KEYNOTE SPEAKERS Wednesday, April 27: Prospects of Ubiquitous Parallel Computing Arvind, MIT Thursday, April 28: Models, Control Primitives, and Resource Metrics for Parallel and Distributed Computation John Reif, Duke University and CMU Friday, April 29: The Software Crisis for the Emerging MPP Industry Dennis Gannon, Indiana University WORKSHOPS There will be six workshops - 1 through 5 will start on Tuesday and 6 will start on Thursday. Workshops are open to all symposium registrants. Technical details of the workshops may be obtained by anonymous ftp from "usc.edu" (login as "anonymous," use your email address as password, and "get pub/ipps94.workshops"). 1.Heterogeneous Computing 2.Input/Output in Parallel Computer Systems 3.Support for Large Scale Shared Memory Architectures 4.Reconfigurable Architectures 5.Massively Parallel Processing Using Optical Interconnections 6.Parallel and Distributed Real Time Systems PANELS 1.Program Portability Across Parallel Architectures Moderator: Michael Wolfe, Oregon Graduate Institute 2.The Right Stuff? Teaching Parallel Computing Moderator: Russ Miller, State University of New York at Buffalo PARALLEL SYSTEMS FAIR This Wednesday event will consist of two sessions with speakers reporting on the development or implementation of parallel machines and parallel programming environments at various universities and research institutions. VENDOR PRESENTATIONS An industrial track has been organized in lieu of commercial exhibits and will include invited technical papers authored and presented by leading researchers and developers from the industrial sector. TUTORIALS Two full day and four half day tutorials will be offered on Tuesday (1-5) and Friday (6). See the pages for those days for descriptions. 1.Parallel Programming Languages and Tools 2.Parallel Non-Numerical Algorithms with Applications to VLSI CAD 3.Parallel Algorithms 4.Multimedia and Scalable Computers 5.Continuing to Exploit Instruction Level Parallelism: Issues, Bottlenecks, and Enabling Conditions 6.Introduction to Parallel Computing SOCIAL EVENTS Attendees are invited to join others for coffee and tea before each day's events begin, and during the midmorning and afternoon breaks. Every day the resort will offer opportunity for active sport and relaxing conversation. Everyone is invited to gather Friday evening on the Westin Regina waterfront for food and refreshments (and Caribbean breezes). REGISTRATION See the tear-out forms in the middle of the Advance Program. Note that advance registration must be sent by March 25, 1994 and received by April 1, 1994 at the IEEE Computer Society. Registrations after April 1 will be accepted on-site only. ________________________________________ SYMPOSIUM OVERVIEW ________________________________________ THURSDAY, APRIL 26 7:30 AM - 7:30 PM Registration Open* 9:30 AM - 6:00 PM Tutorial 1 9:00 AM - 12:30 PM Tutorials 2 & 3 2:00 PM - 5:30 PM Tutorials 4 & 5 8:00 AM - 8:30 AM Morning Coffee/Tea 8:30 AM - 9:30 AM Workshops 1 to 5 Opening Addresses 9:30 AM - 10:00 AM Mid-Morning Break 10:00 AM - 12 NOON Workshops 1 to 5 - Session I 12:00 PM - 1:30 PM Lunch/On Your Own 1:30 PM - 3:30 PM Workshops 1 to 5 - Session II 3:30 PM - 4:00 PM Afternoon Break 4:00 PM - 6:00 PM Workshops 1 to 5 - Session III * Registration will be open on Monday from 6 PM to 10 PM. WEDNESDAY, APRIL 27 7:30 AM - 5:30 PM Registration Open 8:00 AM - 8:30 AM Morning Coffee/Tea 8:30 AM - 9:30 AM Symposium Keynote Address 9:30 AM - 10:00 AM Mid-Morning Break 10:00 AM - 12 NOON Contributed Papers - Session 1 - Session 2 - Session 3 Parallel Systems Fair - Session I Workshop 5 - Session IV 12:00 PM - 3:00 PM Lunch/On Your Own 3:00 PM - 5:00 PM Contributed Papers - Session 4 - Session 5 - Session 6 Parallel Systems Fair - Session II Workshop 5 - Session V 5:00 PM - 5:30 PM Afternoon Break 5:30 PM - 7:30 PM Contributed Papers - Session 7 - Session 8 - Session 9 Industrial Track - Session I Workshop 5 - Session VI THURSDAY, APRIL 28 8:00 AM - 5:30 PM Registration Open 8:00 AM - 8:30 AM Morning Coffee/Tea 8:30 AM - 9:30 AM Symposium 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 II Workshop 6 - Session I 12:00 PM - 3:00 PM Lunch/On Your Own 3:00 PM - 5:00 PM Contributed Papers - Session 13 - Session 14 - Session 15 Industrial Track - Session III Workshop 6 - Session II 5:00 PM - 5:30 PM Afternoon Break 5:30 PM - 7:30 PM Panel 1 - Research FRIDAY, APRIL 29 8:00 AM - 4:00 PM Registration Open 9:30 AM - 6:00 PM Tutorial 6 8:00 AM - 8:30 AM Morning Coffee/Tea 8:30 AM - 9:30 AM Symposium Keynote Address 9:30 AM - 10:00 AM Mid-Morning Break 10:00 AM - 12 NOON Contributed Papers - Session 16 - Session 17 - Session 18 Workshop 6 - Session III 12:00 PM - 1:30 PM Lunch/On Your Own 1:30 PM - 3:30 PM Contributed Papers - Session 19 - Session 20 - Session 21 Workshop 6 - Session IV 3:30 PM - 4:00 PM Afternoon Break 4:00 PM - 6:00 PM Panel 2 - Education 6:00 PM - 9:00 PM Beach Party _____________________________________________________________________ IPPS'94 PROGRAM SCHEDULE _____________________________________________________________________ ********************************************************************* TUESDAY, APRIL 26 ********************************************************************* Workshop 1: All Day Tuesday 3rd WORKSHOP ON HETEROGENEOUS COMPUTING (formerly Heterogeneous Processing) Workshop Chair: Richard F. Freund, NRaD ________________________________________ Program Chair: Mary Eshaghian, New Jersey Institute of Technology Program Committee: Gul Agha, University of Illinois Magdy A. Bayoumi, University of Southwestern Louisiana Fran Berman, University of California, San Diego Mike Dean, BBN Arif Ghafoor, Purdue University M. Ashraf Iqbal, University of Engineering & Technology, Pakistan Gary Johnson, DoE Ashfaq Khokhar, Purdue University Sam Lomonaco, University of Maryland C. Roberto Mechoso, University of California, Los Angeles Paul Messina, JPL/Caltech Jerry Potter, Kent State University Alice Parker, University of Southern California Viktor K. Prasanna, University of Southern California C.S. Raghavendra, Washington State University Craig Rienhart, Rockwell Science Center John Schill, ARPA H.J. Siegel, Purdue University, Bob Voigt, NSF Chip Weems, University of Massachusetts Jack Worlton, Worlton Associates Sudha Yalamanchili, Georgia Institute of Technology ________________________________________ 8:30 A M - 9:30 A M OPENING PRESENTATION Smartnet Scheduling for Heterogeneous Computing Richard F. Freund, NRaD ________________________________________ ________________________________________ 10:00 AM - 12:00 PM HC SESSION I Partitioning and Mapping Chair: Muhammad Shaaban New Jersey Institute of Technology _________________________________________ Matching and Scheduling in a Generalized Optimal Selection Theory Bhagirath Narahari, Abdou Youssef, and Hyeong-Ah Choi, The George Washington University A Sub-Optimal Assignment of Application Tasks onto Heterogeneous Systems Mary Eshaghian and Ying-Chieh Wu, NJIT, Jose C. DeSouza-Batista and Alice C. Parker, USC, Shiv Prakash, IBM Designs and Experiments on Heterogeneous Mapping Heuristics Chokchai Leangsuksun and Jerry L. Potter, Kent State University Estimating Execution Time for Parallel Tasks in Heterogeneous Processing Environment Ashfaq Khokhar, Jaehyung Yang, and Arif Ghafoor, Purdue University, Sohail Sheikh, Widener University Dynamic Optimization of Load Distribution in Heterogeneous Systems Emile Haddad, Virginia Polytechnic Institute and State University _________________________________________ 1:30 PM - 3:30 PM HC SESSION II Applications Chair: Sudha Yalamanchili, Georgia Institute of Technology _________________________________________ Heterogeneous Computing for Vision Ram Nevatia, USC Partitioning of Image Processing Tasks on Heterogeneous Computer Systems Muhammad Shaaban, USC, M. Ashraf Iqbal and Saeed Iqbal, University of Engineering & Technology, Pakistan A Heterogeneous Processing Framework for Multimedia Query Processing Ashfaq Khokhar and Arif Ghafoor, Purdue University Static Program Decomposition Among Machines in an SIMD/SPMD Heterogeneous Environment with Non-Constant Mode Switching Costs Daniel W. Watson, Utah State University, John K. Antonio, H.J. Siegel, and Mikhail Atallah, Purdue University Dynamic Task Assignment in Heterogeneous Linear Array Networks for Metacomputing Kyu Ho Park and Sang-Young Cho, Korea Advanced Institute of Science and Technology Heterogeneous Partitioning in a Workstation Network Thomas Schnekenburger and Martin Huber, Institut fur Informatik ________________________________________ 4:00 PM - 6:00 PM HC SESSION III Tools and Systems Chair: Chip Weems University of Massachusetts ________________________________________ Linguistic Support for Heterogeneous Parallel Processing: A Survey and an Approach Charles C. Weems, Glen Weaver, and Steven Dropsho, University of Massachusetts Scalable Heterogeneous Programming Tools Mary Eshaghian, Song Chen, and Ying-Chieh Wu, NJIT, Richard F. Freund, NRaD, Jerry Potter, Kent State University A Framework for the Virtual Heterogeneous Associative Machine Stephen L. Scott and Jerry Potter, Kent State University A Generic Virtual Machines Architecture for Distributed Parallel Operating Systems Design Traian Muntean, University of Grenoble A Network Architecture for Distributed High Performance Heterogeneous Computing Sourav Bhattacharya, David Du, Allalaghatta Pavan, Sheau-Ru Tong, Ronald Vetter, and Kenneth Williams, University of Minnesota ________________________________________ Discussion and Chairs' Concluding Remarks ________________________________________ Workshop 2: All Day Tuesday 2nd WORKSHOP ON INPUT/OUTPUT IN PARALLEL COMPUTER SYSTEMS Workshop Co-Chairs: Ravi Jain, Bellcore John Werth, University of Texas at Austin J.C. Browne, University of Texas at Austin ________________________________________ Program Committee: Peter Chen, University of Michigan Peter Corbett, IBM Watson Tom Cormen, Dartmouth David DeWitt, University of Wisconsin Sam Fineberg, NASA Ames S. Ghandeharizadeh, USC Paul Messina, Caltech Wayne Roiger, Cray Research ________________________________________ The workshop will focus on the increasingly important I/O bottleneck facing parallel and distributed computer systems. Applications affected by this bottleneck include Grand Challenge problems as well as newer application areas such as multimedia information systems and visualization. Comprehensive solutions to the parallel I/O bottleneck will include not only innovative hardware and architectural designs, but also new theoretical operating systems, compilers and applications approaches. As with the first workshop held in 1993, this workshop will aim to bring together researchers in order to compare and integrate theoretical and experimental approaches and solutions. Particular questions to be discussed will include: -the design and performance of I/O intensive applications, -theory and models of I/O complexity, -systems software support for parallel I/O, -concurrent and parallel file systems, -managing the resources required by parallel I/O, and -design and performance of I/O subsystems. The workshop will include research papers as well as a panel discussion. There will also be a session where participants can discuss work in progress. The workshop is sponsored by the IEEE Technical Committee on Parallel Processing and is held in cooperation with ACM SIGARCH. For further information, please contact one of following: Ravi Jain Bellcore MRE 2P342 445 South Street Morristown, NJ 07962 Phone: (201) 829-4756 John Werth Dept of Computer Sciences Taylor Hall Room 2.124 Univ. of Texas at Austin Austin, TX 78712 Phone: (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 January 31, 1994. Authors will be notified by March 15. For enquiries by e-mail: ippsio@thumper.bellcore.com ________________________________________ ________________________________________ Workshop 3: All Day Tuesday WORKSHOP ON SUPPORT FOR LARGE-SCALE SHARED MEMORY ARCHITECTURES Workshop Co-Chairs: Manu Thapar, Hewlett Packard Kai Li, Princeton University James R. Goodman, University of Wisconsin-Madison ________________________________________ Shared memory multiprocessors are quickly becoming an important form of computer systems. The single address space provided by these architectures provide the user with an easier programming model. Many commercial systems have been announced, or are under development. Though shared memory systems provide a simple programming paradigm, the architectural design of a scalable system has interesting alternatives, some of which increase the hardware complexity. Techniques that can improve the performance of the applications via software, are also very interesting. This workshop provides a forum for researchers and commercial developers to meet and discuss the various hardware and software issues involved in the design and use of scalable shared memory multiprocessors. Software methods, such as virtual shared memory and compiler support, are of special interest to this workshop. Papers in areas such as those listed below will be presented. -Architectures for scalable shared memory systems -Virtual shared memory -Hardware techniques for scalable shared memory -Operating system support -Compiler optimization and support -Application optimization and language support -Performance evaluation -Memory organization -Interconnect topology -Modeling techniques This workshop is sponsored by the IEEE Computer Society Technical Committee on Computer Architecture and the Technical Committee on Parallel Processing. The workshop program will be finalized by February 1, 1994. For further information, please contact one of the following co-chairs: Manu Thapar Hewlett Packard Research Labs 1501 Page Mill Road Palo Alto, CA 94304 Internet: thapar@hplabs.hp.com Phone: 415-857-6284 Fax: 415-857-8526 Kai Li Department of Computer Science Princeton University Princeton, NJ 08544 Internet: li@cs.princeton.edu Phone: 609-258-4637 Fax: 609-258-1771 James R. Goodman Computer Sciences Department University of Wisconsin-Madison 1210 West Dayton Street Madison, WI 53706 Internet: goodman@cs.wisc.edu Phone: 608-262-0765 ________________________________________ _________________________________________ Workshop 4: All Day Tuesday WORKSHOP ON RECONFIGURABLE ARCHITECTURES Workshop Chair: Hossam ElGindy, University of Newcastle, Australia _________________________________________ Program Committee: Hussein Alnuweiri, University of British Columbia Gen-Huey Chen, National Taiwan University Ju-Wook Jang, Samsung Electronics Co. Ltd., Korea Philip MacKenzie, University of Texas Koji Nakano, Hitachi, Ltd., Japan Stephan Olariu, Old Dominion University Viktor K. Prasanna, USC U. Ramachandran, Georgia Institute of Technology Sartag Sahni, University of Florida Arun Somani, University of Washington R. Vaidyanathan, Louisiana State University _________________________________________ Reconfigurable architectures refer to the class of computing networks where topology of the network outside the processors is fixed and the internal connections between the I/O ports of each processor can be set locally during execution of algorithms. Major advances in the use of reconfigurable hardware have been achieved over the last few years as demonstrated by: 1) the design of many optimal algorithms, 2) the establishment of fundamental algorithmic techniques and lower bounds, 3) the implementation of a number of hardware systems, and 4) the identification of reconfiguration models. The models differ in the allowed switch and connection patterns, word size, and the criteria to resolve transmission conflicts. This workshop is organized for researchers active in the study of reconfigurational computing to present state of the art results and to assess future directions for this young field of research. The workshop will feature a keynote speech, contributed research papers, and a session for discussing open problems and the future of the reconfigurable hardware paradigm. The contributed papers are selected by the program committee from submitted manuscripts. Topics covered are: -arithmetic, geometric, image and graph algorithms -separation and simulation of different reconfiguration models -lower bounds -scalability -high performance computing with reconfigurable architectures Manuscripts of exceptionally high quality may be sent to the Workshop Chair for consideration prior to February 1, 1994. The workshop program and proceedings will be available by E-mail from the Chair after March 1, 1994. For further information, please contact the Workshop Chair as follows: Prof. Hossam ElGindy Department of Computer Science University of Newcastle Callaghan, NSW 2308, Australia Phone: +61 49 21 5740 Fax: +61 49 21 6929 Email: raw94@cs.newcastle.edu.au ________________________________________ ________________________________________ Workshop 5: All Day Tuesday and Wednesday WORKSHOP ON MASSIVELY PARALLEL PROCESSING USING OPTICAL INTERCONNECTIONS Workshop Chair: Eugen Schenfeld, NEC Research Institute ________________________________________ Program Committee: Karsten Decker, Swiss Scientific Computing Center Patrick Dowd, SUNY at Buffalo John Feo, Lawrence Livermore Asher Friesem, Weizmann Institutute Allan Gottlieb, New-York University Joe Goodman, Stanford University Alan Huang, Bell Labs Yoshiki Ichioka, Osaka University Leah Jamieson, Purdue University Lennart Johnsson, Harvard University Israel Koren, University of Massachusetts Raymond Kostuk, University of Arizona Philippe Lalanne, Institution DUOptique Sing Lee, University of California, San Diego Steve Levitan, University of Pittsburgh Adolf Lohmann, University of Erlangen Miroslaw Malek, University of Texas at Austin J.R. Moulic, IBM Watson Miles Murdocca, Rutgers University John Neff, University of Colorado Viktor K. Prasanna, USC Paul Prucnal, Princeton University John Reif, Duke University A.A. Sawchuk, USC Eugen Schenfeld, NEC Research Institute Larry Snyder, University of Washington Harold Stone, IBM Watson Les Valiant, Harvard University ________________________________________ The first annual workshop on Massively Parallel Processing Architectures using Optical Interconnections (MPP-OI'94) will be held on the Tuesday and Wednesday of the Symposium (April 26 & 27). The workshop's focus is the possible use of optical interconnections for massively parallel processing systems, and their effect on system and algorithm design. Optics offer many benefits for interconnecting large numbers of processing elements, but may require us to rethink how we build parallel computer systems and communication networks, and how we write applications. Fully exploring the capabilities of optical interconnection networks requires an interdisciplinary effort. It is critical that researchers in all areas of the field are aware of each other's work and results. The intent of MPP-OI is to assemble the leading researchers and to build towards a synergistic approach to MPP architectures, optical interconnections, operating systems, and software development. The workshop will feature an invited address, followed by several sessions of submitted papers, and conclude with a panel discussion entitled, "Way of Using Optical Interconnections for MPPs In The Near Future (less than 10 years from now)." Authors are invited to submit manuscripts which demonstrate original unpublished research in areas of computer architecture and optical interconnections. The topics of interest include but are not limited to the following: -Reconfigurable Architectures -Optical interconnections -Embedding and mapping of applications and algorithms -Packaging and layout of optical interconnections -Electro-optical, and opto-electronic components -Relative merits of optical technologies (free-space, fibers, wave guides) -Passive optical elements -Algorithms and applications exploiting MPP-OI -Data distribution and partitioning -Characterizing parallel applications exploiting MPP-OI -Cost/performance studies For further information, contact the Workshop Chair as follows: Eugen Schenfeld NEC Research Institute 4 Independence Way Princeton, NJ 08540 Phone: (609) 951-2742 Fax: (609) 951-2482 email: MPPOI@RESEARCH.NJ.NEC.COM This workshop is co-sponsored by the ACM Special Interest Group on Architecture (SIGARCH), the Optical Society of America (OSA), the IEEE Computer Society's Technical Committee on Parallel Processing (TCPP) and Technical Committee on Computer Architecture (TCCA), and the Air Force Office of Scientific Research (AFOSR). ________________________________________ TUTORIAL 1 (Full-Day) ________________________________________ Parallel Programming Languages and Tools Siddhartha Chatterjee, RIACS/NASA Ames Research Center Doreen Y. Cheng, CSC/NASA Ames Research Center Who Should Attend: The tutorial is intended for application scientists and engineers who would like to use parallelism to reduce computation time, and for computer scientists and engineers designing and using parallel programming languages and tools. Course Description: The tutorial will be divided equally between parallel programming languages and tools. We will begin with a review of parallel architectures, and give a taxonomy of parallel programming languages and describe the design choices for such languages. We will then introduce the design goals and ideas of several categories of parallel programming languages (extensions to sequential languages, data-parallel languages, parallel object-oriented languages, coordination languages, functional languages, and logic languages), describe one language in each category in some detail, and compare their usability for real-world application development. On the tools side, we will introduce the main goals and approaches of parallel programming tools (libraries, debuggers, performance tuning tools, parallelization tools, network resource management tools, and tools for building tools), describe the main features of a few tools in each category, and compare usability for real-world application development. Finally, we will discuss future directions of research and development in both areas. Lecturers: Siddhartha Chatterjee received his Ph.D. in Computer Science from Carnegie Mellon University in 1991. At the Research Institute for Advanced Computer Science (RIACS) at NASA Ames Research Center, he is developing compiler optimizations for automatic data layout in the context of Fortran 90 and High Performance Fortran. He is also investigating the use of C++ in integrating task and data parallelism. He taught a graduate seminar on parallel programming languages at UC Berkeley in the fall of 1993. His research interests include the design and implementation of programming languages, high performance parallel architectures, and parallel algorithms and applications. Doreen Cheng received her Ph.D. in Electrical Engineering from Stanford University in 1988. At NAS/NASA Ames Research Center, she leads a team to develop tools for writing, debugging, and optimizing parallel programs. Her NASA report "A Survey of Parallel Programming Languages and Tools" has been requested by hundreds of organizations worldwide and is highly regarded. She has initiated and led an effort participated by more than 20 vendors to define and standardize protocols that facilitate debugger portability. Together with colleagues, she is developing a prototype for a portable parallel/distributed debugger. _________________________________________ TUTORIAL 2 (Half-Day Morning) _________________________________________ Parallel Non-Numerical Algorithms with Applications to VLSI CAD Prith Banerjee, University of Illinois at Urbana-Champaign Who Should Attend: The tutorial will be of immense value to researchers in the parallel processing community who are looking for interesting, non-numerical problems to solve. It will also be of value to CAD developers and users in the next few years if they wish to efficiently use the technology of parallel processing to solve the problems of the future. Course Description: While it is relatively easy to build massively parallel processing (MPP) machines whose peak performance can be GFLOPS, it is not always easy to harness the computational power effectively. Therein lies the challenge - design of good parallel algorithms that can efficiently use the hardware resources to get the maximum performance. This tutorial will discuss PRACTICAL parallel algorithms for shared memory MIMD, message passing MIMD, and SIMD parallel machines for solving problems in a growing application area whose computational requirements are enormous, and something that computer scientists can relate to; that is, VLSI CAD applications. The half-day tutorial will be organized as three sessions of 1 hour each. Session 1 will discuss parallel algorithms for physical design applications, namely placement, routing, layout extraction and layout verification. Session 2 will describe parallel algorithms for circuit, logic, and behavioral simulation. Session 3 will discuss parallel algorithms for logic synthesis, verification, and test. Lecturer: Prith Banerjee is a Professor of Electrical and Computer Engineering and Computer Science at the University of Illinois at Urbana-Champaign. His research interests are in Parallel Algorithms for VLSI Design Automation, and Distributed Memory Parallel Architectures, and is the author of over 120 papers in these areas. He has also written a book on Parallel Algorithms for VLSI CAD to be published by Prentice-Hall in 1994. He was the recipient of the NSF PYI Award in 1987. He has served on various Program and Organizing Committees including FTCS, IPPS, ISCA and ISVLSID. He is an Associate Editor of the IEEE Transactions on VLSI Systems, and the Journal of Parallel and Distributed Computing. ________________________________________ TUTORIAL 3 (Half-Day Morning) ________________________________________ Parallel Algorithms H. J. Siegel, Parallel Processing Laboratory, School of Electrical Engineering, Purdue University Who Should Attend: Professionals and researchers with a computer science or computer engineering background who are interested in the use of large-scale parallel processing systems. Course Description: Parallel machines with 64 to 64,000 processors are commercially available - the challenge is to transform a given task into a parallel algorithm that executes effectively. A variety of techniques for mapping tasks onto parallel machines are explored and demonstrated through the use of parallel algorithm case studies. Models of SIMD (synchronous), MIMD (asynchronous), and reconfigurable systems are described. The tasks to be examined are image smoothing, recursive doubling, global histogramming, 2-D FFT, and sorting. Issues addressed include data distribution, influence of network topology, SIMD vs. MIMD vs. mixed-mode trade-offs, the impact of partitioning the system for subtask parallelism, the effect on execution time of increasing the number of processors used, and the difficulty of automatic parallelization of serial algorithms. The RalligatorsS that make the design and use of large-scale parallel processing systems difficult are discussed. Lecturer: H. J. Siegel is a Professor and Coordinator of the Parallel Processing Laboratory in the School of Electrical Engineering at Purdue University. He received two BS degrees from MIT and the PhD from Princeton. He has co-authored over 150 technical papers, co-edited four volumes, authored one book, lectured as an IEEE Computer Society Distinguished Visitor, given tutorials in the USA, Europe, and Israel, and prepared two continuing education video tape courses. Dr. Siegel was a Coeditor-in-Chief of the Journal of Parallel and Distributed Computing and is a Fellow of the IEEE. He is currently an ACM National Lecturer and on the editorial boards of the IEEE Transactions on Parallel and Distributed Systems and the IEEE Transactions on Computers. _________________________________________ TUTORIAL 4 (Half-Day Afternoon) _________________________________________ Multimedia and Scalable Computers Kai Hwang, University of Southern California Who Should Attend: Designed for computer professionals including educators, researchers, engineers, managers, and applications developers. Parallel and distributed systems and the underlying technologies will be studied. Course Description: The Tutorial covers state-of-the-art technologies in multimedia, computers, communications, and commercial electronics. Besides, we will address the scalability, programmability, and systems applications. Important topics include systems architectures, latency tolerating techniques, multiprocessor and network OSs, distributed computing environments, multimedia desktops, PDA, broadband ISDNs, PCS, ATM networks, HDTV, CD-ROM, and DVI, etc. Lecturer: Kai Hwang is a professor in the Department of Electrical Engineering at the University of Southern California. ________________________________________ TUTORIAL 5 (Half-Day Afternoon) ________________________________________ Instruction Level Parallelism: Issues, Bottlenecks, and Enabling Conditions Yale N. Patt, University of Michigan Who Should Attend: The tutorial will be useful to the novice who has not immersed himself/herself in instruction-level parallelism as well as to the experienced computer architect who has. The novice will find the lecture style elementary (while not being superficial) and entertaining (while not being trivial). The experienced architect should find enough digressions into insights into exploiting ILP to make the day a worthwhile journey. Course Description: Multiprocessors are made up of individual cpus, and each cpu can do better if (a) its individual instruction stream has inherent parallelism in it, and (b) the hardware can find it and take advantage of it. First of all, (a) is almost always true. Second, this tutorial is about (b). Focus is on what can be accomplished at run time, including how the compiler can help. The current hot topics will be presented, such as compile time vs run time, superscalar vs VLIW, instruction supply mechanisms and branch prediction, multi-wide decode and issue, multiple functional units and distribution buses, etc., etc. Finally, we will look at where we go from here. Lecturer: Yale N. Patt has been teaching and doing research in computer architecture for more than 25 years. Professor of EECS at Michigan, he directs 11 PhD students in experimental research in high performance computer system design. He consults extensively in the computer industry (more than 25 years), in particular for DEC (since 1977) and for NCR (since 1986). He (with his students) introduced HPS in 1985. Today, many of its features have become standard parts in current mainstream microprocessors. ********************************************************************** WEDNESDAY, APRIL 27 ********************************************************************** ________________________________________ 8:30 AM - 9:30 AM KEYNOTE ADDRESS ________________________________________ Prospects of Ubiquitous Parallel Computing Arvind, MIT ________________________________________ 10:00 AM - 12:00 NOON SESSION 1 Interconnection Networks Chair: Wayne G. Nation IBM AS/400 Division ________________________________________ Interconnection Network Switch Architectures and Combining Strategies Susan Dickey and Allan Gottlieb, New York University, Yue-Sheng Liu, Dow-Jones Telerate Integrating Networks and Memory Hierarchies in a Multicomputer Node Architecture Lynn Choi and Andrew A. Chien, University of Illinois A Theoretical Network Model and the Hamming Cube Networks Sajal K. Das and Aisheng Mao, University of North Texas Low Cost Complexity of a General Multicast Bitonic Network Majed Z. Al-Hajery and Kenneth E. Batcher, Kent State University Generalized Ring Interconnection Networks Ronald Fernandes, Texas A&M University, and Arkady Kanevsky, University of Southern Mississippi Synchronous Bus Arbitration with Constant Logic Per Module Hussein M. Alnuweiri, University of British Columbia ________________________________________ 10:00 AM - 12:00 NOON SESSION 2 Languages Chair: Doug DeGroot Texas Instruments _________________________________________ A Verified Integration of Parallel Programming Paradigms in CC++ Paolo A.G. Sivilotti, California Institute of Technology Parallelization of Linearized Applications in Fortran D Lorie M. Liebrock and Ken Kennedy, Rice University Integrating Functional and Imperative Parallel Programming: CC++ Solutions to the Salishan Problems John Thornley, California Institute of Technology Accommodating Polymorphic Data Decompositions in Explicitly Parallel Programs Calvin Lin and Lawrence Snyder, University of Washington Performance Analysis of pC++: A Portable Data-Parallel Programming System for Scalable Parallel Computers Allen Malony and Bernd Mohr, University of Oregon, Peter Beckman, Dennis Gannon, and Shelby Yang, Indiana University, Francois Bodin, IRISA, University of Rennes MPC: A Massively Parallel C Language Jeffrey McDonald and Ken Hansen, MasPar Computer Corp. _________________________________________ 10:00 AM - 12:00 NOON SESSION 3 Computational Geometry Chair: Behrooz A. Shirazi University of Texas at Arlington ________________________________________ Computational Geometry on a Reconfigurable Mesh Madhusudan Nigam and Sartaj Sahni, University of Florida Time-Optimal Proximity Algorithms on Meshes with Multiple Broadcasting S. Olariu, Old Dominion University, I. Stojmenovic, University of Ottowa An Optimal Mesh Computer Algorithm for Constrained Delaunay Triangulation Sumanta Guha, University of Wisconsin-Milwaukee Time-Optimal Visibility-Related Algorithms on Meshes with Multiple Broadcasting D. Bhagavathi, V. Bokka, H. Gurla, S. Olariu, J.L. Schwing, and I. Stojmenovic, Old Dominion University, J. Zheng, Elizabeth City State University A Parallel Algorithm for Computing Polygon Set Operations Raghu Karinthi, Kankanahalli Srinivas, and George Almasi, West Virginia University Transformations Between Boundary Codes, Run Length Codes and Linear Quadtrees Myung Hee Kim and Oscar H. Ibarra, University of California, Santa Barbara ________________________________________ 3:00 PM - 5:00 PM SESSION 4 Memory Issues Chair: Yale Patt University of Michigan ________________________________________ Latin Cubes and Parallel Array Access Cong Fan and Ajay K. Gupta, Western Michigan University, Jiuqiang Liu, Eastern Michigan University A Framework for Programming Using Non-atomic Variables Ambuj K. Singh, University of California, Santa Barbara Hardware Support for Synchronization in the Scalable Coherent Interface (SCI) Nagi M. Aboulenein and James R. Goodman, University of Wisconsin, Stein Gjessing, University of Oslo, Philip J. Woest, Northwestern University Software Assistance for Directory-Based Caches Zhiyuan Li, University of Minnesota An Evaluation of Multiprocessor Cache Coherence Based on Virtual Memory Support Karin Petersen, Xerox PARC, Kai Li, Princeton University Queue Locks on Cache Coherent Multiprocessors Peter Magnussen, Anders Landin, and Erik Hagersten, Swedish Institute of Computer Science The Effect of Speculative Execution on Cache Performance Jim Pierce and Trevor Mudge, University of Michigan ________________________________________ 3:00 PM - 5:00 PM SESSION 5 Compiling Chair: Arif Ghafoor Purdue University ________________________________________ A Multi-Paradigm Object Oriented Parallel Environment F. Hamelin, J.-M Jezequel, and T. Priol, IRISA A Direct Array Injection Technique in a Fine-Grain Multithreading Execution Model Chinhyun Kim and Jean-Luc Gaudiot, University of Southern California Schedule-Based Multi-Dimensional Retiming on Data Flow Graphs Nelson Luiz Passos, Edwin Hsing-Mean Sha, and Steven C. Bass, University of Notre Dame Performing Data Flow Testing in Parallel Mary Jean Harrold, Clemson University A Language for Conveying the Aliasing Properties of Dynamic, Pointer-Based Data Structures Joseph Hummel and Alexandru Nicolau, University of California, Irvine, Laurie J. Hendren, McGill University Estimation of Nested Loops Execution Time by Integer Arithmetics in Convex Polyhedra Nadia Tawbi, BULL Centre de Recherche ________________________________________ 3:00 PM - 5:00 PM SESSION 6 Graph Algorithms Chair: Sartaj Sahni University of Florida ________________________________________ Solving the All-Pair Shortest Path Problem on Interval and Circular-Arc Graphs Danny Z. Chen, University of Notre Dame, D.T. Lee, Northwestern University An Optimal Parallel Matching Algorithm for a Convex Bipartite Graph on a Mesh-connected Computer Myung-Ho Kim, Pohang Institute of Science, Chang-Sung Jeong, Korea University, Myung-Soo Kim, Pohang Institute of Science Efficient Matrix Chain Ordering in Polylog Time Phillip G. Bradford, Gregory J.E. Rawlins, and Gregory E. Shannon, Indiana University Parallel Bidirectional Heuristic Search with Dynamic Process Re-Direction Anestis A. Toptsis, York University Solving Static Optimal Matching Problem in Heterogeneous Processing by Generalized Stable Marriage Algorithms J. Zhi Cheng Li, University of Hawaii A Decomposition-Based Parallel Simulated Annealing for Graph Partitioning Wen K. Lee, Kien A. Hua, and S.D. Lang, University of Central Florida ________________________________________ 5:30 PM - 7:30 PM SESSION 7 Machine Architectures Chair: David L. Tuomenoksa AT&T ________________________________________ Parallel Evaluation of a Parallel Architecture by Means of Calibrated Emulation Henk L. Muller, Paul W.A. Stallard, and David H.D. Warren, University of Bristol and PACT/SRF, Sanjay Raina, University of Bristol and Meiko, Ltd. Architecture and Implementation of Vulcan Craig B. Stunkel, Dennis G. Shea, Bulent Abali, Monty M. Denneau, Peter H. Hochschild, Douglas J. Joseph, Ben J. Nathanson, Michael Tsao, and Philip R. Varker, IBM Watson Research Center A Parallel Algorithm and Architecture for Robot Path Planning N. Ranganathan, Bharadwaj Parthasarathy, and Ken Hughes, University of South Florida GRAPE-4: A Teraflops Massively-Parallel Special-Purpose Computer System for Astrophysical N-body Simulations Makoto Taiji, Junichiro Makino, Toshikazu Ebisuzaki, and Daiichiro Sugimoto, University of Tokyo Building Multithreaded Architectures with Off-the-Shelf Microprocessors Herbert H.J. Hum, Concordia University, Kevin B. Theobald and Guang R. Gao, McGill University Optimizing General Design Objectives in Processor Array Design Kumar N. Ganapathy and Benjamin W. Wah, University of Illinois ________________________________________ 5:30 PM - 7:30 PM SESSION 8 Compiler Optimization Chair: Trevor Mudge University of Michigan ________________________________________ Variable Instruction Issue for Efficient MIMD Interpretation on SIMD Machines Nael Abu-Ghazaleh, Xianzhi Fan, Philip A. Wilsey, and Debra Hensgen, University of Cincinnati A Control Strategy Based on Heuristic Techniques for the Parallel Execution of Logic Programs Gitu Jain, B. Ramkumar, and Jon G. Kuhl, University of Iowa Loop Allocation Scheme for Multithreaded Dataflow Computers A.R. Hurson and Joford T. Lim, Pennsylvania State University, K. Kavi and B. Shirazi, University of Texas at Arlington Decoupling Parallel Control and Sequential Codes: the Pyramid Approach Z. Lin and S. Zhou, University of Toronto Extracting Parallelism from Fortran by Translation to a Single-Assignment Intermediate Form Robert J. Barry and Paraskevas Evripidou, Southern Methodist University Optimal Software Pipelining of Nested Loops J. Ramanujam, Louisiana State University ________________________________________ 5:30 PM - 7:30 PM SESSION 9 Algorithms Chair: Mikhail Atallah Purdue University ________________________________________ PRAM Algorithms for Static Dictionary Compression Lynn M. Stauffer and Daniel S. Hirschberg, University of California, Irvine Sorting Strings and Constructing Digital Search Trees in Parallel Joseph F. Ja'Ja', University of Maryland, Kwan Woo Ryu, Kyungpook National University, Uzi Vishkin, University of Maryland and Tel Aviv University Parallel Extended GCD Algorithm Pou-Yah Wu, Kaohsiung Polytechnic Institute, Julian Chuen-Liang Chen, National Taiwan University Efficient Parallel Algorithms for Tree-Related Problems Using the Parentheses Matching Strategy Sajal K. Das and Kwang Bae Min, University of North Texas, Ranette H. Halverson, Midwestern State University Systematic Development of a Parallel SPMD Program for General Divide-and-Conquer Sergei Gorlatch, University of Passau Can Parallel Algorithms Enhance Serial Implementation? Uzi Vishkin, University of Maryland and Tel Aviv University ________________________________________ PARALLEL SYSTEMS FAIR Chair: Hussein M. Alnuweiri University of British Columbia ________________________________________ 10:00 AM - 12:00 NOON PSF Session I Parallel Architectures Chair: Mounir Hamdi Hong Kong University of Science and Technology ________________________________________ Design and Development of Tightly-Coupled Heterogeneous Parallel Systems for Image Understanding C. Weems, University of Massachusetts at Amherst, J.R. Burrill, Amerinex Artificial Intelligence Inc., D.B. Shu, Hughes Research Laboratories OMARS: Optimal Mapping Alternate Routing System R.C. Metzger, L.S. Auvil, and C.A. Wright Jr., Rome Laboratory, J.K. Antonio, Y.A. Li, O.K. Wu, and E. Asbun, Purdue University MEMSY: A Modular Expandable Multiprocessor System with Fault Tolerance M. Dal Cin, A. Grygier, H. Hessenauer, U. Hildebrand, J. Honig, F. Hofmann, W. Hohl, C.-U. Linster, E. Michel, A. Pataricza, T. Thiel, and S. Turowski, University of Erlangen-Numberg The Prototype of a Heterogeneous Machine for Robot Vision: Architecture, Programming, and Performance R. Cucchiara, UniversitaU di Ferrara, L. Di Stefano, M. Monacelli, M. Piccardi, G. Rustichelli, and T.S. Cinotti, D.E.I.S., UniversitaU di Bologna An Outline of Objectives for the SAM-II Parallel Computer Prototype R.F. Hobson, Simon Fraser University FPGA-Based Synchronizations on ArMen Parallel Architecture P. Dhaussy, J.-M. Filloque, B. Pottier, and C. Rubini, Universite de Bretagne Occidentale et Telecom-Bretange _________________________________________ 3:00 PM - 5:00 PM PSF Session II Parallel Programming and Network Computing Chair: Rita Cucchiara UniversitaU di Ferrara _________________________________________ Efficient Parallel Image Processing Applications on a Network of Distributed Workstations C.-K. Lee and M. Hamdi, Hong Kong University of Science and Technology The GRIDS Parallel Programming Model for Grid-Based Scientific Applications U. Geuder, M. Hardtner, B. Worner, and R. Zink, University of Stuttgart An Environment for Investigating Shared Virtual Memory Behavior A. Bode and R. Hackenberg, Technical University of Munich Parallel Processing Ensembles for Embedded Robotics Computations A.Y. Zomaya, The University of Western Australia The Challenges of Heterogeneous Computing R. Freund, Naval Research and Development Center ________________________________________ Wednesday & Thursday INDUSTRIAL TRACK: INVITED VENDOR PRESENTATIONS Chair: John K. Antonio Purdue University ________________________________________ 5:30 PM to 7:30 PM INDUSTRIAL TRACK Session-I Parallel Processing Systems Chair: John K. Antonio Purdue University ________________________________________ Centre for Development of Advanced Computing PARAM Parallel Supercomputer: Architecture, Programming Environment and Applications Vijay P. Bhatkar, Executive Director, and Ashok Joshi, Director MasPar Computer Corporation The MasPar Scalable Unix I/O System John R. Nickolls, Vice President and Co-Founder NEC Corporation NEC Cenju-3: A Microprocessor-Based Parallel Computer Nobuhiko Koike, Senior Manager ********************************************************************** THURSDAY, APRIL 28 ********************************************************************** ________________________________________ 8:30 AM - 9:30 AM KEYNOTE ADDRESS ________________________________________ Models, Control Primitives, and Resource Metrics for Parallel and Distributed Computation John Reif, Duke University and CMU ________________________________________ 10:00 AM - 12:00 NOON SESSION 10 Sorting and Networks Chair: Kathy Liszka University of Akron ________________________________________ Deterministic Routing and Sorting on Rings Jop F. Sibeyn, Max Planck Institute Routing and Sorting on Meshes with Row and Column Buses Torsten Suel, University of Texas at Austin Bitonic Sorting on 2D-PEC: An Algorithmic Study on a Hierarchy of Meshes Network Donna J. Quammen and Pearl Y. Wang, George Mason University Generalizations of the New Class of g-Chain Periodic Sorting Networks David Nassimi and Yehoshua Perl, New Jersey Institute of Technology, Ronald Becker, University of Cape Town Priority Based Real-Time Communication for Large Scale Wormhole Networks Jong-Pyng Li and Matt W. Mutka, Michigan State University Fuzzy Communications for Distributed Computing on Message-Passing Systems Chien-Ming Cheng and Kai Hwang, University of Southern California ________________________________________ 10:00 AM - 12:00 NOON SESSION 11 Resource Management Chair: Richard C. Metzger Rome Laboratory ________________________________________ A Comparison of Heuristics for Scheduling DAGs on Multiprocessors C.L. McCreary, A.A. Khan, J.J. Thompson, and M.E. McArdle, Auburn University Effects of Control Parameters on Dynamic Load Balancing Vasudha Govindan and Mark A. Franklin, Washington University Information Sharing Mechanisms in Parallel Programs Laxmikant V. Kal and Amitabh B. Sinha, University of Illinois Processor Mapping Techniques Toward Efficient Data Redistribution Edgar T. Kalns and Lionel M. Ni, Michigan State University Redundant Synchronization Elimination for DOACROSS Loops Ding-Kai Chen and Pen-Chung Yew, University of Illinois Hybrid Resource Management Algorithms for Multicomputer Systems Jeff J. Baxter and John W.C. Fu, Intel Corp., B. Ramkumar, University of Iowa, Janak H. Patel, University of Illinois ________________________________________ 10:00 AM - 12:00 NOON SESSION 12 Numerical Methods Chair: Jagdish Chandra US Army Research Office ________________________________________ SIMD Algorithms for Matrix Multiplication on the Hypercube C.A. Alonso Sanches and S.W. Song, University of Sao Paolo An Efficient Task Allocation Algorithm and Its Use to Parallelize Irregular Gauss- Seidel Type Algorithms G. Huang and W. Ongsakul, Texas A&M University Scalable Techniques for Computing Band Linear Recurrences on Massively Parallel and Vector Supercomputers Haigeng Wang, Alexandru Nicolau, Stephen Keung, and Kai-Yeung Sunny Siu, University of California, Irvine A Clustered Reduced Communication Element by Element Preconditioned Conjugate Gradient Algorithm for Finite Element Computations Alpesh Amin, P. Sadayappan, and Murali Gudavalli, UES, Inc. Massively Parallel Algorithms for Solution of Schrodinger Equation Amir Fijany, Jacob Barhen, and Nikzad Toomarian, Jet Propulsion Laboratory Parallel Algorithms for Singular Value Decomposition Renard Ulrey, NCR, Inc., Anthony Maciejewski and Howard Jay Siegel, Purdue University ________________________________________ 3:00 PM - 5:00 PM SESSION 13 Routing Chair: Thomas Schwederski Institute for Microelectronics Stuttgart ________________________________________ Deterministic Permutation Routing on a Reconfigurable Mesh Ashish Kapoor, Heiko Schroder, and B. Beresford-Smith, University of Newcastle A High Performance Pattern Associative Oblivious Router for Tree Topologies Douglas H. Summerville and Jose G. Delgado-Frias, SUNY Binghamton, Stamatis Vassiliadis, IBM Corp. Encapsulating Networks and Routing B. Zerrouk, J.M. Blinn, and A. Greiner, University Pierre et Marie Curie Circuit-Switched Broadcasting in d-Dimensional Tori and Meshes Ju-Young L. Park, Sang-Kyu Lee, and Hyeong-Ah Choi, George Washington University All-to-All Communication on Meshes with Wormhole Routing Rajeev Thakur and Alok N. Choudhary, Syracuse University On Evil Twin Networks and the Value of Limited Randomized Routing Brian D. Alleyne, Princeton University, Isaac D. Scherson, University of California, Irvine ________________________________________ 3:00 PM - 5:00 PM SESSION 14 Synchronization Chair: Kai Hwang University of Southern California ________________________________________ Automatic Array Alignment as a Step in Hierarchical Program Transformation Bojan Cukic and Farokh B. Bastani, University of Houston Scalable Spin Locks for Multiprogrammed Systems Robert W. Wisniewski, Leonidas Kontothanassis, and Michael L. Scott, University of Rochester Dagger: Combining the Benefits of Synchronous and Asynchronous Communication Styles Attila Gursoy and Laxmikant V. Kal, University of Illinois Barrier Synchronization Techniques for Distributed Process Creation R.F. DeMara, C. Lin, S. Kuo, and B. Motlagh, University of Central Florida Efficient Barriers for Distributed Shared Memory Computers Dirk Grunwald and Suvas Vajracharya, University of Colorado Clustering and Intra-Processor Scheduling for Explicitly-Parallel Programs on Distributed-Memory Systems Vibha A. Dixit-Radiya and Dhabaleswar K. Panda, Ohio State University ________________________________________ 3:00 PM - 5:00 PM SESSION 15 Performance Chair: Dan C. Marinescu Purdue University ________________________________________ Measuring the Effects of Thread Placement on the Kendall Square KSR1 T.D. Wagner, E. Smirni, A.W. Apon, M. Madhukar, and L.W. Dowdy, Vanderbilt University Performance Prediction of Parallel Computation De-Ron Liang, Academia Sinica, Satish K. Tripathi, University of Maryland Experience with Executing Shared Memory Programs using Fine-Grain Communication and Multithreading in EM-4 Mitsuhisa Sato, Yuetsu Kodama, and Yoshinori Yamaguchi, Electrotechnical Laboratory, Shuichi Sakai, RWC Tukuba Research Center Shared Virtual Memory and Generalized Speedup Xian-He Sun and Jianping Zhu, Mississippi State University Performance Evaluation of Task-Grain Problems Vladimir Ivanov, Consultant Analysis of Memory Latency Factors and their impact on KSR1 MPP Performance Bassam Kahhaleh, University of Jordan __________________________________________________ 5:30 PM - 7:30 PM PANEL 1 Program Portability Across Parallel Architectures __________________________________________________ Moderator: Michael Wolfe Oregon Graduate Institute Panelists: Prithviraj Banerjee, University of Illinois at Urbana James Browne, University of Texas at Austin Jack Dennis, MIT Hank Dietz, Purdue University Chuck Koelbel, Rice University Alexandru Nicolau, University of California at Irvine Steve Otto, Oregon Graduate Institute _______________________________________________ INDUSTRIAL TRACK: INVITED VENDOR PRESENTATIONS (continued from Wednesday) _______________________________________________ 10:00 AM TO 12:00 NOON INDUSTRIAL TRACK Session-II Digital Media and Distributed Computing Chair: Daniel W. Watson Utah State University ________________________________________ Digital Equipment Corporation High Performance Fortran on Workstation Farms Marco Annaratone, Technical Director, Carl D. Offner, Technical Staff, and David B. Loveman, Technical Staff nCUBE Corporation The Digital Media Convergence Ron Buck, Vice President of Marketing Virtual Computer Corporation Transformable Computing Steve Casselman, President ________________________________________ 3:00 PM TO 5:00 PM INDUSTRIAL TRACK Session-III Portability, Scalability, and Applications Chair: Alan Berenbaum AT&T Bell Labs ________________________________________ HyperParallel Technologies HyperC: Portable Parallel Programming in C Philippe Clermont, President & Chief Executive Officer and Nicolas Paris, Software Development Manager The MITRE Corporation Modeling Intelligent Vehicle Highway Systems Using Parallel Processing William P. Niedringhaus, Lead Engineer, Jeff Opper, Technical Staff, and Lisa Rhodes, Technical Staff Transtech Parallel Systems Corporation Performance and Scalability of Parallel Applications Richard S. Stephens, Software Development Manager ___________________________________________________________ Workshop 6: Thursday & Friday 2nd WORKSHOP ON PARALLEL AND DISTRIBUTED REAL-TIME SYSTEMS Workshop Co-Chairs: Dieter K. Hammer, Technische Universiteit Eindhoven Lonnie R. Welch, New Jersey Institute of Technology ___________________________________________________________ Program Committee: Giovanni Cantone, University of Rome at Tor Vergata Klaus Ecker, Technical University of Clausthal Loe Feijs, Philips Research Leonard L. Goldsmith, US Army Prabha Gopinath, Honeywell Robert Harrison, US Naval Surface Warfare Center Mathai Joseph, University of Warwick Joerg Kaiser, GMD Jan van Katwijk, Delft University of Technology Gerard Le Lann, INRIA Jane W.S. Liu, University of Illinois Mike Rodd, University of Wales Kang G. Shin, University of Michigan Behrooz Shirazi, University of Texas Sang Son, University of Virginia John A. Stankovic, University of Massachusetts Robert Steigerwald, US Air Force Academy Alexander D. Stoyenko, New Jersey Institute of Technology Kenji Toda, MITI Electrotechnical Laboratory Jan Vytopil, University of Nijmegen ________________________________________ Parallel and distributed computer systems are increasingly used for the support of the primary process of enterprises, the control of the related production equipment and various other embedded applications, ranging from the control of television sets to avionic systems. There is an increasing requirement for these real-time systems to exploit parallel and distributed computer platforms in order to meet timing constraints and to support fault tolerance. Unfortunately, it is often the case that researchers focus on problems relevant to parallel processing only, optimizing average case behavior, while overlooking the guarantee of timeliness and reliability. A similar phenomenon also occurs often in real-time research, wherein techniques are developed that apply only to single processor systems. Since complex real-time and reliable systems cannot be based on a single paradigm, technique or method, we perceive a need for collaboration between researchers in the field of parallel and distributed processing, and the field of real-time and reliable systems. This workshop will provide opportunities for researchers to share original research results and experience in areas such as the following: -Scheduling -Resource Allocation -Optimization by Extraction and Exploitation of Parallelism -Fault Tolerance -Complex Systems Engineering and Reengineering The following related issues will also be explored along with relevant case studies, applications, development techniques, and tools: -Specification and Verification Methods -Compiler Techniques -Object-Oriented Techniques -Architecture and Hardware -Multiprocessor and Distributed Operating Systems -Artificial Intelligence and Neural Networks -Parallel and Distributed Algorithms -Communication Systems and Protocols -Case Studies, Applications, Development Techniques and Tools ******************************************************************* FRIDAY, APRIL 29 ******************************************************************* ________________________________________ 8:30 AM - 9:30 AM KEYNOTE ADDRESS ________________________________________ The Software Crisis for the Emerging MPP Industry Dennis Gannon, Indiana University ________________________________________ 10:00 AM - 12:00 NOON SESSION 16 Embedding & Message Passing Chair: Gene Saghi Texas Instruments ________________________________________ Latency Hiding in Message-Passing Architectures U. Bruening, W. K. Giloi, and W. Schroeder-Preikschat, GMD Institute for Computer Architecture and Software Technology Efficient Embedding K-ary Complete Trees into Hypercubes Xiaojun Shen, Qing Hu, and Weifa Liang, University of Missouri-Kansas City A New Combinatorial Approach to Optimal Embeddings of Rectangles Shou-Hsuan S. Huang, Hongfei Liu, and Rakesh M. Verma, University of Houston Distributed Identification of All Maximal Incomplete Subcubes in a Faulty Hypercube Hsing-Lung Chen, National Taiwan University, Nian-Feng Tzeng, University of Southwestern Louisiana The Semantics of Blocking and Nonblocking Send and Receive Primitives Robert Cypher and Eric Leu, IBM Almaden Research Center Improving Parallel Program Execution Time with Message Consolidation Steve Shafer, IBM Federal Systems, Kanad Ghose, SUNY Binghamton ________________________________________ 10:00 AM - 12:00 NOON SESSION 17 Models & Real Time Systems Chair: John C. Cherniavsky National Science Foundation _________________________________________ A Multipath Contention Model for Analyzing Job Interactions in 2-D Mesh Multicomputers Dugki Min and Matt W. Mutka, Michigan State University The Block Distributed Memory Model for Shared Memory Multiprocessors Joseph Ja'Ja', University of Maryland, Kwan Woo Ryu, Kyungpook National University Gossiping with Multiple Sends and Receives A. Bagchi, Bell Communications Research, E.F. Schmeichel, San Jose State University, S.L. Hakimi, University of California, Davis The Symmetry Programming Paradigm Kong Li and David Jefferson, University of California, Los Angeles Fault Detection and Recovery in a Data-Driven Real-Time Multiprocessor William G. Farquhar and Paraskevas Evripidou, Southern Methodist University Fault-Tolerant Scheduling on Hard Real-Time Multiprocessor Systems Sunondo Ghosh, Rami Melhem, and Daniel Moss, University of Pittsburgh ________________________________________ 10:00 AM - 12:00 NOON SESSION 18 Applications Chair: Susamma Barua California State University, Fullerton ________________________________________ Parallel Neural Network Learning Through Repetitive Bounded Depth Trajectory Branching Iuri Mehr and Zoran Obradovic, Washington State University The Design of Scalable Software Libraries for Distributed Memory Concurrent Computers Jaeyoung Choi and David W. Walker, Oak Ridge National Laboratory, Jack J. Dongarra, Oak Ridge National Laboratory and University of Tennessee A High Performance Communications and Memory Caching Scheme for Molecular Dynamics on the CM-5 David M. Beazley, Peter S. Lomdahl, Niels Gronbech-Jensen, and Pablo Tamayo, Los Alamos National Laboratory Parallel Implementation of a Model-Based Spectral Estimator for Doppler Blood Flow Instrumentation D.F. Nocetti, Universidad Nacional Autonoma de Mexico, M.G. Ruano, Universidad de Algarve, P.J. Fish, University of Wales, P.J. Fleming, University of Sheffield On the Parallel Implementation of OSI Protocol Processing Systems Robert Lam and Mabo R. Ito, University of British Columbia A Parallel Parsing Algorithm for Natural Language using Tree Adjoining Grammar Tom Nurkkala and Vipin Kumar, University of Minnesota ________________________________________ 1:30 PM - 3:30 PM SESSION 19 Network Performance Chair: Allan Gottlieb New York University ________________________________________ Fault Location in Multistage Interconnection Networks with Global and Distributed Control Ernst G. Bernard, Matthias Sauer, and Josef A. Nossek, Institute for Network Theory and Circuit Design CCL: A Portable and Tunable Collective Communication Library for Scalable Parallel Computers Vasanth Bala, Shlomo Kipnis, and Marc Snir, IBM Watson Research Center, Jehoshua Bruck, Robert Cypher, Pablo Elustondo, Alex Ho, and Ching-Tien Ho, IBM Almaden Research Center Latency Analysis: A Key Issue to Evaluate and Improve Parallel Computing Performance and Scalability Xiaodong Zhang, Yong Yan, and Keqiang He, University of Texas at San Antonio Total Exchange and Matrix Multiplication in Faulty SIMD Hypercubes Amit Sengupta and C.S. Raghavendra, Washington State University How to Get Good Performance from the CM-5 Data Network Eric A. Brewer and Bradley C. Kuszmaul, Massachusetts Institute of Technology Lookahead Processor Allocation in Mesh-Connected Massively Parallel Computers Sourav Bhattacharya, Honeywell Technology Center, Wei-Tek Tsai, University of Minnesota _________________________________________ 1:30 PM - 3:30 PM SESSION 20 Data Structures and Debugging Chair: Albert Y. Zomaya University of Western Australia _________________________________________ Parallel Dictionaries on AVL Trees Muralidhar Medidi and Narsingh Deo, University of Central Florida Concurrent Search and Insertion in K-Dimensional Height Balanced Trees Atul Varshneya, B.B. Madan, and M. Balakrishnan, Indian Institute of Technology, New Delhi AVL Trees with Relaxed Balance Kim S. Larsen, Odense University Heuristic Optimization of Speedup and Benefit/Cost for Parallel Database Scans on Shared-Memory Multiprocessors Michael Rys and Gerhard Weikum, ETH Zurich Towards Flexible Control of the Temporal Mapping from Concurrent Program Events to Animations Eileen Kraemer and John T. Stasko, Georgia Institute of Technology Designing a Parallel Debugger for Portability John May and Francine Berman, University of California, San Diego ________________________________________ 1:30 PM - 3:30 PM SESSION 21 Image Processing Chair: Janet McWaid Caltech ________________________________________ A Scalable MIMD Volume Rendering Algorithm Craig M. Wittenbrink and Michael Harrington, University of Washington Dynamic Space Warping Algorithm on Fine Grain Array Processors Heung-Nam Kim, Mary Jane Irwin, and Robert Owens, Pennsylvania State University, Chen-Mi Wu, National Taiwan Institute of Technology Parallel Implementation and Scheduling Issues of an Image Edge Detection Application on a Distributed Memory Multicomputer Xiaodong Zhang, Haixu Yang, and Yan Zhou, University of Texas at San Antonio ProperPLACE: A Portable Parallel Algorithm for Standard Cell Placement Sungho Kim and Prithviraj Banerjee, University of Illinois, Balkrishna Ramkumar, University of Iowa Parallel Logic Simulation Using Time Warp on Shared-Memory Multiprocessors Hong K. Kim and Soon M. Chung, Wright State University Parallel Routing of VLSI Circuits Based on Net Independency Henning Spruth and Frank M. Johannes, Technical University of Munich ________________________________________ 4:00 PM - 6:00 PM PANEL 2 The Right Stuff? Teaching Parallel Computing ________________________________________ Moderator: Russ Miller, State University of New York at Buffalo Panelists: Francine Berman, University of California, San Diego Janet Hartman, Illinois State University Elizabeth R. Jessup, University of Colorado at Boulder John R. Nickolls, MasPar Computer Corporation Ralph Roskies, Pittsburgh Supercomputing Center Nan C. Schaller, Rochester Institute of Technology ________________________________________ 6:00 PM - 9:00 PM Beach Party ________________________________________ ________________________________________ TUTORIAL 6 (Full-Day) ________________________________________ Introduction to Parallel Computing Mary M. Eshaghian, New Jersey Institute of Technology Vipin Kumar, University of Minnesota Who Should Attend: The tutorial is intended both for people from the computer science community as well as practicing engineers/scientists with problems requiring massively parallel computing. Course Description: The course consists to two parts. The first part presents an overview of parallel computer architectures. The second part presents some basic parallel algorithms. Part 1 - Introduction to parallel processing, parallel computational models such as PRAM and VLSI, classification of computer systems shared vs. distributed memory, and SIMD, MIMD, etc. An overview of various interconnection networks such as Ring, Star, Linear Array, Mesh, Hypercube, Meshes with broadcasting, and their performance using basic metrics such as speedup, efficiency, communication diameter, etc. Interconnection Networks such as Crossbars, Omega, Butterfly, Delta, Clos and Benes. Part 2 - Basic Communication Operations: One-to-all Broadcast, All-to-all Broadcast, One-to-all Personalized Communication, All-to-all Personalized Communication. Matrix Computations: Mapping Matrices on Processors, Matrix-Vector Multiplication, Matrix-Matrix Multiplication, Solving a System of Linear Equations. Graph Algorithms: Minimal spanning trees, shortest path. Sorting: Quick sort, sample sort. Lecturers: Mary M. Eshaghian received her Ph.D. in Computer Engineering from University of Southern California, in 1988. She then worked at Grumman Data Systems heading the Parallel Processing Research group. Since 1991, she has been an assistant professor at New Jersey Institute of Technology (NJIT). Her area of research in Parallel Processing includes: Parallel Models of Computations, Parallel Programming Tools, Heterogeneous Computing, Optical Interconnection Networks, and VLSI Architectures and Algorithms. She serves on the executive committee of the IEEE Technical Committee on Parallel Processing. Currently, she chairs the program committee of the IPPS Workshop on Heterogeneous Computing and serves on the program committee of the IEEE International Parallel Processing Symposium. Vipin Kumar is an associate professor of Computer Science at the University of Minnesota. He has done extensive research and teaching in the area of parallel computing over the last 10 years. He has published over 70 research articles, edited two books, and co-authored a text book "Introduction to Parallel Computing" (pub. Benjamin Cummings, November 1993). He serves on the editorial board of IEEE Transactions on Data and Knowledge Engineering, and on the advisory committee of the IEEE Technical Committee on Parallel Processing. He is a senior member of IEEE, a member of the ACM, and the American Association for Artificial Intelligence. ********************************************************************* LOCATION ********************************************************************* About Cancun: IPPS attendees will appreciate the story of how a "wise Mexican computer" in 1967 chose a small, swampy finger of land in an isolated part of the Mexican Caribbean to become the Cancun resort area. While Cancun may be new, the Yucatan Peninsula has witnessed a diversity of cultures, including the Mayan city states, which contributed to the areaUs historic progress in artistic, architectural, and astronomical skills. In Mexico today, there are about two and a half million native speakers of Maya, along with the many archaeological monuments to their past and to the Toltec civilization which succeeded them. Several of the larger archaeological sites are a day trip from Cancun, and there are two smaller ruins in Cancun which are well worth a visit. Air Transport: American Airlines will offer a special coach fare to IPPS'94 travelers. To obtain this fare, call 800-433-1790 and refer to STARFILE No. S3544R9. At this printing, the following airlines have routes to Cancun: American, Aeromexico, Continental, Iberia, LACSA, Mexicana, Northwest, United, and Varig. Check with airlines to obtain the best fare & schedule. Accommodations: The special IPPS'94 Westin Regina Resort rate is US $90 for single or double. All rooms are spacious and have a view of the water, and the Westin Regina offers the full amenities of an international hotel. For coolness and sand, the floors are tile without rugs, so bring along slippers or sandals. Rooms are equipped with safes for personal belongings (passports, cash, cameras, etc.) and attendees are encouraged to utilize them. Location: (See maps) Located along a quarter mile of beach, the Westin Regina has five outdoor swimming pools, a fitness center, and two lighted tennis courts. A water sports center located on the lagoon has scuba diving, snorkeling, boating, skiing, and fishing. CancunUs 18-hole golf course was designed by Robert Trent Jones, Jr. Local Transportation: There are buses and taxis along the peninsula, and all sightseeing tours are available on a/c motorcoaches. From the airport, taxis are recommended and fares average US $10 plus $2 tip. Getting around in Cancun is usually done by taxis which are available 24 hours a day at low rates. Car rentals, which tend to be more expensive than in the U.S., are available at the airport and at the hotel. Customs/Passports: For Canadians and Americans a passport is not required but is recommended to prevent delays. Those of other nationalities will require a passport and should check with their local Mexican consulate to determine whether a visa is also required. Currency: The unit of currency is the Mexican peso and as of 12/16/93, US $1 = N $3.10 (new peso). Hotel room rates are quoted in US dollars. Most restaurants and shops accept US dollars (no personal checks) and major credit cards. Usually the best rate of exchange can be obtained at local banks as well as at some small shops. Weather & Time: The climate is tropical and the temperature in April will average above 80 F (26.6 C). Casual, light clothing is the norm for meetings. The time is Central Standard - 2 hours ahead of Los Angeles and 1 hour behind New York. Many places are closed for several hours in the afternoon, but then most shops stay open into late evening. IPPS'94 is an ideal location to bring along family. Your traveling companions will be well entertained while you are participating in symposium events. On Wednesday and Thursday, no sessions are planned for the break from 12 noon to 3:00 pm, leaving you free to recreate, shop, and sightsee. For sightseeing and water activities, you may want to check with a travel agent to find out about schedules and requirements. ------------------------------------------------------------------------ IPPS '94 - 8TH INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM APRIL 26-29, 1994 - THE WESTIN REGINA RESORT - CANCUN, MEXICO ------------------------------------------------------------------------ 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? ______________________________________ ______________________________________________________________________ PLEASE CIRCLE APPROPRIATE FEES: .... CONFERENCE REGISTRATION FEES: _____________________________________________________ Advance Registration (Until March 25, 1994) Member Non-member Student $275 $345 $150 _____________________________________________________ Late/Onsite Registration (After April 1, 1994) Member Non-member Student $330 $415 $250 _____________________________________________________ .... TUTORIAL REGISTRATION: (Price per tutorial) ________________________________________________________________________ HALF-DAY TUTORIALS FULL-DAY TUTORIALS (Tuesday, April 26) (Tuesday, April 26) ____ 2. PARALLEL NON-NUMERICAL ____ 1. PARALLEL PROGRAMMING ALGORITHMS ... TO VLSI CAD LANGUAGES & TOOLS ____ 3. PARALLEL ALGORITHMS ____ 4. MULTIMEDIA & SCALABLE COMPUTERS (Friday, April 29) ____ 5. CONTINUING TO EXPLOIT ____ 6. INTRODUCTION TO INSTRUCTION LEVEL PARALLELISM PARALLEL COMPUTING _______________________________________________________________________ ..... TUTORIAL FEES: _______________________________________________________________________ Advance Registration (Until March 25, 1994) HALF-DAY TUTORIAL FULL-DAY TUTORIAL Member Non-Member Member Non-Member $150 $200 $230 $285 ______________________________________________________________________ Late/Onsite Registration (After April 1, 1994) HALF-DAY TUTORIAL FULL-DAY TUTORIAL Member Non-Member Member Non-Member $190 $235 $275 $345 _____________________________________________________________________ TOTAL ENCLOSED: $ __________________________________________________ PAYMENT MUST BE ENCLOSED. PLEASE MAKE ALL 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 25, 1994. Refunds are subject to a $50 processing fee. All no-show registrations will be billed in full. Registrations after April 1, 1994 will be accepted on-site only. Do not include my mailing address on: _________ Non-Society Mailing Lists _________ Meeting Attendee Lists ______________________________________________________________________ IPPS'94 HOTEL RESERVATION WESTIN REGINA RESORT CANCUN * The special IPPS'94 group rate of US $90.00 (single or double) is available from April 21 through May 4, 1994. All rates are subject to 10% tax, a $2.00 maid gratuity, and a $4.00 per person baggage handling fee. PLEASE MAKE HOUSING RESERVATIONS DIRECTLY WITH HOTEL. FAX 011-52-98-85-02-96 PHONE 1-800-524-5405 _______________________________________________________________________ -- Dhabaleswar K. Panda, Asst. Professor e-mail: panda@cis.ohio-state.edu Dept. of Computer and Information Science Office: (614) 292-5199 (Tel) Ohio State University, Columbus, OH 43210-1277, USA. (614) 292-2911 (Fax)