NetNews Usenet Archive 1993 #3

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / parallel / 3016 < prev next >

Wrap

Text File | 1993-01-21 | 67.6 KB | 1,879 lines

Newsgroups: comp.parallel Path: sparky!uunet!gatech!hubcap!fpst From: ipps93@halcyon.usc.edu (International Parallel Processing Symphosium) Subject: for comp.parallel Message-ID: <1993Jan21.140212.6401@hubcap.clemson.edu> Sender: fpst@hubcap.clemson.edu (Steve Stevenson) Organization: Clemson University Date: Wed, 20 Jan 93 16:00:12 PST Approved: parallel@hubcap.clemson.edu Lines: 1867 7th INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM, IPPS '93 Newport Beach Marriot Hotel and Tennis Club, Newport Beach, California April 13--16, 1993 This is the plain text version of the advance program for IPPS '93. It is organized into four parts. Part I is an introduction to the symposium, Part II contains the list of accepted technical papers, Part III deals with tutorials and workshops, and Part IV contains the registration and hotel information and forms. Registration for IPPS '93 with the IEEE computer society must be made before March 26th to take advantage of advance registration rates. Hotel reservations must be made before March 23rd. -------------------------------------------------------------------------- PART I: Introduction -------------------- IPPS '93 ORGANIZATION --------------------- SYMPOSIUM CHAIR H. T. Kung, Carnegie-Mellon University and Harvard University SYMPOSIUM VICE-CHAIR Larry Canter, Computer Systems Approach, Inc. Program Chair Viktor K. Prasanna, USC Tutorials Chair Wei-Ming Lin, Mississippi State University Parallel Systems Fair Chair Hussein Alnuweiri, University of British Columbia Commercial Exhibits Chair Donna Quammen, George Mason University Proceedings Chair Anil S. Rao, Utrecht University ORGANIZING COMMITTEE Steering Committee Chair George Westrom, Odetics, Inc. Finance Bill Pitts, Toshiba America Information Systems, Inc. Local Arrangements Susamma Barua, California State University, Fullerton Publicity Chair Sally Jelinek, Electronic Design Associates Publicity Coordinators Europe-Asia: Dionisios I. Reisis, National Technical University of Athens Africa-India-Pacific Rim: L. M. Patnaik, Indian Institute of Science Program Committee ----------------- Mikhail Atallah, Purdue University Doug DeGroot, Texas Instruments Jack Dongarra, University of Tennessee and Oak Ridge National Laboratory Mary Eshaghian, New Jersey Institute of Technology Richard F. Freund, Naval Research and Development Center Kai Hwang, USC Oscar Ibarra, University Of California, Santa Barbara Mary Jane Irwin, Pennsylvania State University David Kuck, University of Illinois F. Thomson Leighton, Massachusetts Institute of Technology Viktor K. Prasanna, USC K. Wojtek Przytula, Hughes Research Laboratories C. S. Raghavendra, Washington State University Sartaj Sahni, University of Florida Isaac Scherson, University of California, Irvine Assaf Schuster, Technion - Israel Institute of Technology R. K. Shyamasundar, Tata Institute of Fundamental Research, India H. J. Siegel, Purdue University Satish K. Tripathi, University of Maryland Sponsorship ----------- The 7th International Parallel Processing Symposium is sponsored by the IEEE Computer Society 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 '93 is being provided by MasPar Computer Corporation and NEC Research Institute. IPPS '93 Proceedings The 1993 proceedings will be published by the IEEE Computer Society Press and made available to all registrants at the symposium. Extra copies and proceedings from previous symposia may be purchased at registration. COME TO THE BEACH IN APRIL '93 Join us from Tuesday, April 13 through Friday, April 16, 1993 at the Newport Beach Marriott and Tennis Club ideally located between Los Angeles and San Diego. In response to the call for participation, we have organized events which will focus on special topics of interest. These include workshops, tutorials, a parallel systems fair, and commercial exhibits. WORKSHOPS Five workshops have been organized for the first day of the symposium: 1. Heterogeneous processing 2. Parallel and distributed real-time systems 3. Input-output in parallel computer systems 4. Analyzing scalability of parallel algorithms and architectures 5. Strategic directions in computational microdevices TUTORIALS Four half-day and four full-day tutorials have been organized for Tuesday and Friday featuring current topics: 1. Connection Machine CM-5: Programming for performance 2. Data parallel programming and application development on the MasPar series of MPP systems 3. Programming support for distributed-memory computing environments 4. Software tools for visualization of parallel/distributed programs 5. High-performance I/O systems 6. Parallel programming on the Intel Paragon 7. Introduction to parallel processing 8. Parallel processing algorithms and systems PARALLEL SYSTEMS FAIR This one day event is scheduled for Wednesday and features parallel systems under development in academic, industrial, and research sites. It is open to all registrants. COMMERCIAL EXHIBITS Companies will be demonstrating commercial products and systems of particular interest to IPPS attendees Wednesday through Friday. SOCIAL EVENTS On Wednesday evening (7-9 PM), the symposium will hold a wine and cheese reception. Co-hosted by MasPar Computer Corporation, this will provide an opportunity for attendees to meet other participants. Other events will be announced at registration. NEWPORT BEACH MARRIOTT HOTEL & TENNIS CLUB The Newport Beach Marriott Hotel and Tennis Club is located south of Los Angeles in Orange County, ten minutes from the John Wayne/Orange County airport which is serviced by Alaska Airlines, American Airlines, American Eagle, America West, Continental, Delta, Northwest, TWA, United, and U.S. Air. The hotel provides complimentary limousine service. The Los Angeles International Airport (LAX) is serviced by all major air carriers and the drive time to Newport Beach is approximately 55 minutes. Convenient shuttle bus service to the hotel may be arranged upon arrival at LAX. DRIVING DIRECTIONS Driving from John Wayne/Orange County Airport: Take MacArthur south to Jamboree Road. Continue down Jamboree to Santa Barbara Drive. Turn left onto Santa Barbara Drive. Hotel will be right at the top of the hill. Driving from LAX: Take San Diego Freeway (405) south to the Corona del Mar Freeway (73). Exit on Corona del Mar Freeway, south toward Corona del Mar. Continue on to Jamboree Road and turn right onto Jamboree Road. Now proceed as above. Driving from downtown LA: Take Santa Ana Freeway (5) south to Newport Freeway (55). Take Newport Freeway south to Corona Del Mar (73) and proceed as above. LOCAL ATTRACTIONS The Newport Beach Marriott is located at Newport Center and overlooks the Newport Beach Country Club and Newport Harbor. It is just ten minutes from John Wayne/Orange County airport and fewer minutes from the sandy beaches of the Pacific Ocean. On premises is a tennis club, pool and sauna, and across the boulevard (an easy walk) are the Fashion Island speciality shops, department stores and cinemas, and plenty of eateries - from upscale restaurants to the Atrium open market, catering to a variety of tastes and appetites. Excursions may be taken to the San Diego Zoo and Sea World, and Universal Studios in Los Angeles. Nearby in Orange County is Disneyland. Given the local attractions, you may want to skip the traffic and crowds and take in local Newport Beach sites including Mariner's mile, Balboa Peninsula and Island, and Back Bay Preserve with its hiking paths and fine golf courses. Just up the road are the village communities of Corona del Mar and Laguna Beach which are the site of leading galleries. For the more adventuresome, there is surfing and scuba diving. This setting has been described as a "casual meeting site for those who don't take meetings casually." -------------------------------------------------------------------------- PART II: List of Accepted Papers and Keynote Addresses ------------------------------------------------------ -- Wednesday, April 14 --- 8:30 AM - 9:30 AM, KEYNOTE ADDRESS Why BSP Computers? Leslie Valiant, Harvard University 10:00 AM - 12:00 noon, SESSION 1, Architectures-I Chair: Jean-Loup Baer, University of Washington A Parallel Prolog Execution Model: Theoretical Approach and Experimental Results J.P. Bodeveix, Universite Paul Sabatier, and E. Bizouarn, Universite Paris-Sud. Invalidation Delayed Coherence for Multiprocessors Yung Syau Chen, University of Southern California. A High Speed Dataflow Processing Element and Its Performance Compared to a Von-Neumann Mainframe J. N. Coleman, University of Newcastle- Upon Tyne. Linked List Cache Coherence for Scalable Shared Memory Multiprocessors Manu Thapar, Hewlett-Packard Laboratories, Bruce Delagi and Michael J. Flynn, Stanford University. A Performance Comparison of Several Superscalar Processor Models with a VLIW Processor John Lenell and Nader Bagherzadeh, University of California, Irvine. Cache Coherence for Shared Memory Multiprocessors Based on Virtual Memory Support Karin Peterson and Kai Li, Princeton University. 10:00 AM - 12:00 noon, SESSION 2, Algorithms-I Chair: Oscar Ibarra, University of California, Santa Barbara Maintaining Bipartite Matchings in the Presence of Failures Edwin Hsing-Mean Sha, University of Notre Dame, and Kenneth Steiglitz, Princeton University. Parallel Algorithms for Rectilinear Link Distance Problems Andrzej Lingas, Lund University, Anil Maheshwari, Tata Institute of Fundamental Research, and Jorg-Rudiger Sack, Carleton University. Sorting n^{2} Numbers on n x n Meshes Madhusudan Nigam and Sartaj Sahni, University of Florida. On the Power of Segmenting and Fusing Buses R. K. Thiruchelvan, Advance Paradigms, Inc., Jerry L. Trahan and R. Vaidyanathan, Louisiana State University. A Separation Between Reconfigurable Mesh Models Philip D. MacKenzie, University of Texas. Sorting-Based Selection Algorithms for Hypercubic Networks P. Berthome, A. Ferreira, S. Perennes, Ecole Normale Supe'rieure de Lyon, B. M. Maggs, NEC Research Institute, and C. G. Plaxton, University of Texas at Austin. 10:00 AM - 12:00 noon, SESSION 3, Mapping/Scheduling-I Chair: Ashfaq Khokhar, USC Mapping a Class of Run-Time Dependencies onto Regular Arrays G. M. Megson, University of Newcastle-Upon-Tyne. Parallel Algorithms for Hypercube Allocation Yeimkuan Chang and Laxmi N. Bhuyan, Texas A&M University. Scheduling a Computational Dag on a Parallel System with Communication Delays and Replication of Node Execution Pauline Markenscoff and Yong Yuan Li, University of Houston. Scheduling Independent Tasks On Partitionable Hypercube Multiprocessors Bhagirath Narahari, George Washington University, and Ramesh Krishnamurti, Simon Fraser University. Mapping Realistic Data Sets on Parallel Computers R. Ponnuswamy, N. Mansour, A. Choudhary, and G. C. Fox, Syracuse University. Load Balancing of DOALL Loops in the Perfect Club Gary Elsesser and Viet Ngo, Cray Research Park, Sourav Bhattacharya and Wei-Tek Tsai, University of Minnesota. 1:30 PM - 3:30 PM, SESSION 4, Architectures-II Chair: Mary Jane Irwin, Pennsylvania State University Hierarchical Interconnection Cache Networks Sizheng Wei, Rutgers University, and Eugen Schenfeld, NEC Research Institute. A Multi-Level Hierarchical Cache Coherence Protocol for Multiprocessors Craig Anderson and Jean-Loup Baer, University of Washington. `Unstable Threads' Kernel Interface for Minimizing the Overhead of Thread Switching Shigekazu Inohara, Kazuhiko Kato, and Takashi Masuda, University of Tokyo. Global Combine on Mesh Architectures with Wormhole Routing M. Barnett, University of Idaho, R. Littlefield, Pacific Northwest Lab., D. G. Payne, Intel Corporation, and R. A. Van de Geijn, University of Texas at Austin. Impact of Multiple Consumption Channels on Wormhole Routed k-ary n-cube Networks Shobana Balakrishnan and Dhabaleswar K. Panda, The Ohio State University. New Degree Four Networks: Properties and Performance Gebre Gessesse and Suresh Chalasani, University of Wisconsin-Madison. 1:30 PM - 3:30 PM, SESSION 5, Algorithms-II Chair: Mike Atallah, Purdue University Sorting n Numbers on n x n Reconfigurable Meshes With Buses Madhusudan Nigam and Sartaj Sahni, University of Florida. Optimal Mesh Computer Algorithms for Simple Polygons Sumanta Guha, University of Wisconsin-Milwaukee. An Efficient Parallel Algorithm for Min-Cost Flow on Directed Series-Parallel Neworks Amit Jain and N. Chandrasekharan, University of Central Florida. Towards Optimal Parallel Radix Sorting R. Vaidyanathan, Louisiana State University, C. R. P. Hartmann and P. K. Varshney, Syracuse University. On the Shortest Path Problem for Permutation Graphs Oscar H. Ibarra and Qi Zheng, University of California, Santa Barbara. A Parallel MSF Algorithm for Planar Graphs on a Mesh and Applications to Image Processing David Nassimi, New Jersey Institute of Technology. 1:30 PM - 3:30 PM, SESSION 6, Mapping/Scheduling-II Chair: Sudhakar Yalamanchili, Georgia Institute of Technology A Cluster-M Based Mapping Methodology Mary M. Eshaghian, New Jersey Institute of Technology, and Muhammad E. Shaaban, University of Southern California. Scheduling In and Out Forests in the Presence of Communication Delays Theodore A. Varvarigou, AT&T Bell Labs., Vwani P. Roychowdhury, Purdue University, and Thomas Kailath, Stanford University. A Load Balancing Strategy for Priorized Execution of Tasks Amitabh Bhuvangyan Sinha and Laxmikant V. Kale, University of Illinois. Mapping onto Three Classes of Parallel Machines: A Case Study Using the Cyclic Reduction Algorithm Gene Saghi, H. J. Siegel, and Jeffrey L. Gray, Purdue University. Mapping to Reduce Contention in Multiprocessor Architectures Loren Schwiebert and D. N. Jayasimha, The Ohio State University. Static Scheduling of Uniform Nested Loops Liang-Fang Chao, Princeton University, and Edwin Hsing-Mean Sha, Notre Dame University. 4:00 PM - 6:00 PM, SESSION 7, Networks-I Chair: H. J. Siegel, Purdue University The Connection Cubes: Symmetric, Low Diameter Interconnection Networks with Low Node Degree Nitin K. Singhvi, State University of New York at Binghamton. Simulating Interconnection Networks in RAW W. B. Ligon III, Clemson University, and U. Ramachandran, Georgia Institute of Technology. A Trip-based Multicasting Model for Wormhole-routed Networks with Virtual Channels Yu-Chee Tseng and Dhabaleswar K. Panda, The Ohio State University. Efficient Offline Routing of Permutations on Restricted Access Exanded Delta Networks Isaac D. Scherson and Raghu Subramanian, University of California, Irvine. A Heuristic Approach for Embedding Communication Patterns in an Interconnection Cached Parallel Processing Network Vipul Gupta, Rutgers University, and Eugen Schenfeld, NEC Research Institute. Permutation on the Mesh with Reconfigurable Bus: Algorithms and Practical Considerations Yen-Wen Lu, James B. Burr, and Allen M. Peterson, Stanford University. 4:00 PM - 6:00 PM, SESSION 8, Algorithms-III Chair: S. Rajashekaran, University of Pennsylvania A Parallel Algorithm for Multiple Edge Updates of Minimum Spanning Trees Xiaojun Shen and Weifa Liang, University of Missouri-Kansas City. Approximate Parallel Prefix Computation and Its Applications Michael T. Goodrich, Johns Hopkins University, Yossi Matias and Uzi Vishkin University of Maryland. Testing a Simple Polygon for Monotonicity Optimally in Parallel Danny Z. Chen, University of Notre Dame, and Sumanta Guha, University of Wisconsin-Milwaukee. 2D- and 3D-Optimal Parallel Image Warping Craig M. Wittenbrink and Arun K. Somani, University of Washington. Gossiping on Interval Graphs Suresh Singh and M. A. Sridhar, University of South Carolina. Parallel Algorithms for Height Balancing Binary Trees Srinivasan Venkatraman, Alicia Kime, and Kankanahalli Srinivas, West Virginia University. 4:00 PM - 6:00 PM, SESSION 9, Mapping/Scheduling-III Chair: Chip Weems, University of Massachusetts A Framework for Predicting Delay Due to Job Interactions in a 2-D Mesh Multicomputer Dugki Min and Matt W. Mutka, Michigan State University. A Partially Asynchronous and Distributed Algorithm for Load Balancing Jianjian Song, National University of Singapore. Task Scheduling on a Hypercube with Link Contentions Seiichi Kon'ya and Tetsuji Satah, NTT NNetwork Innformation Systems Laboratories. A Probabilistic Analysis of a Locality Maintaining Load Balancing Algorithm Kishan Mehrotra, Sanjay Ranka, and Jhychun Wang, Syracuse University Multiprocessors Scheduling for Imprecise Computations in a Hard Real-Time Environment Ashok Khemka, K. V. Subrahmanyam, and R. K. Shyamasundar, Tata Institute of Fundamental Research. Data Partitioning Schemes for Parallel Implementation of the Revised Simplex Algorithm for LP Problems Usha Sridhar and Anirban Basu, Center for the Development of Advanced Computing 10:00 AM to 6:00 PM, PARALLEL SYSTEMS FAIR --------------------- Chair: Hussein M. Alnuweiri, University of British Columbia 10:00 A M - 12 noon, PSF Session-I, Multiprocessor Systems Chair: Mabo R. Ito, University of British Columbia The NYU Ultracomputer Allan Gottlieb, Ronald Bianchini, Susan Dickey, and Richard Kenner, New York University. Experience with the Hector Multiprocessor Michael Stumm, Zvonko Vranesic, Ron White, Ronald Unrau, and Kieth Farkas, University of Toronto. Advanced Parallel Function Processor Steven R. Gieseking and Cecil O. Alford, Georgia Institute of Technology. A T-9000 Based Parallel Image Processor R. S. Cok and J. Gerstenberger, Eastman Kodak Company. Architecture, Operating System, and I/O Subsystem Design of the M^2 Database Machine Yen-Jen Oyang, National Taiwan University. Parallel Image, Signal, and Neural Network Processing with HNC's Vision Processor (ViP) Chip Set and HNC's SIMD Neurocomputer Array Processor (SNAP) Robert W. Means and K. P. Qing, Hecht-Nielsen Corporation, Inc. 1:30 PM - 3:30 PM, PSF Session-II, Software for Parallel Processing Chair: Paul Suhler, University of Southern California On Massively Parallel Architectural Benchmarking: Kernels, Algorithms, and Architectures Issac D. Scherson and U. Krishnaswamy, University of California, Irvine. The Stuttgart Parallel Processing Library SPPL and the X Windows Parallel Debugger XPDB Ronald Zink, Institute for Parallel and Distributed High-Performance Systems. PACLIB: A System for Parallel Algebraic Computation on Shared Memory Multiprocessors Wolfgang Schreiner and Hoon Hong, Johannes Kepler University. ||MAPLE||: A System for Parallel Symbolic Computation Kurt Siegl, Johannes Kepler University. Ease: The Model and Its Implementation Steven E. Zenith, Kuck and Associates, Inc. PARSE: A Software Engineering Methodology for Parallel Program Design Ian Gorton, Jon Gray, and Innes Jelly, University of New South Wales. 4:00 PM - 6:00 PM, PSF Session-III, Applications Chair: Allan Gottlieb, New York University Image Understanding on MasPar MP-1 and Connection Machine CM-5: Experiments and Performance Comparisons Ashfaq Khokhar, University of Southern California, Hyoung J. Kim, Kangwon National University, and Cho-Li Wang, University of Southern California A Multiarchitecture Parallel-Processing Development Environment Scott Townsend, Richard Blech, and Gary Cole, NASA Lewis Research Center Group. Further Development of a Distributed Transputer Based X-Server Michal Wojtulewicz and Gordon Makinson, University of Kent. A Parallel Host Interface for High-Speed Networks Gerald W. Neufeld and Mabo R. Ito, University of British Columbia. Projections: A Scalable Performance Tool Amitabh Balwant Sinha and Laxmikant V. Kale', University of Illinois. Design and Implementation of a Distributed System using IBM PC Compatible Computers and a NOVELL Network C. J. Semple and V. Lakshmi Narasimhan, University of Queensland. -- Thursday, April 15 --- 8:30 AM - 9:30 AM, KEYNOTE ADDRESS Designing Efficient Parallel Algorithms: Models and Paradigms with Applications to Image Processing Joseph Ja' Ja', University of Maryland 10:00 AM - 12:00 noon, SESSION 10, Networks-II Chair: Isaac Scherson, University of California, Irvine Complexity of Intensive Communications on Balanced Generalized Hypercubes John K. Antonio and Longsong Lin, Purdue University, and Richard C. Metzger, Griffiss Air Force Base. Analytical Models of Bandwidth Allocation in Pipelined k-ary n-Cubes Patrick T. Gaughan and Sudhakar Yalamanchili, Georgia Institute of Technology. Reconfiguration of Binary Trees in Faulty Hypercubes Pei-Ji Yang, University of Southern California, and C. S. Raghavendra, Washington State University. On Synchronous Strictly Non-Blocking Concentrators and Generalized Concentrators H. K. Dai, University of North Dakota. Design of an Efficient Reconfigurable Network Arun K. Somani, University of Washington. New Wormhole Routing Algorithms for Multicomputers Rajendra V. Boppana, University of Texas at San Antonio, and Suresh Chalasani, University of Wisconsin-Madison. 10:00 AM - 12:00 noon, SESSION 11, Applications-I Chair: Tomas Lang, University of California, Irvine Supporting Insertions and Deletions in Striped Parallel Filesystems Theodore Johnson, University of Florida. A Portable Parallel Algorithm for VLSI Circuit Extraction Balkrishna Ramkumar, University of Iowa, and Prithviraj Banerjee, University of Illinois. Image Processing with the MGAP: A Cost-Effective Solution Raminder Singh Bajwa, Robert Michael Owens, and Mary Jane Irwin, Pennsylvania State University. Fast Parallel Algorithms for Model Checking Using BDDs Insup Lee and Sanguthevar Rajasekaran, University of Pennsylvania. Fixed Size Linear Arrays for Stereo and Image Matching Ashfaq Khokhar, University of Southern California, and Wei-Ming Lin, Mississippi State University. KSR1 Multiprocessor: Analysis of Latency Hiding Techniques in a Sparse Solver Daniel Windheiser, Eric L. Boyd, Eric Hao, and Santosh G. Abraham, University of Michigan. 10:00 AM - 12:00 noon, SESSION 12, Software-I Chair: Leah Jamieson, Purdue University Multiple Message Broadcasting in the Postal Model Amotz Bar-Noy and Shlomo Kipnis, IBM T. J. Watson Research Center. Concurrent Programming with Shared Objects in Networked Environments Charles Hartley and V. S. Sunderam, Emory University. Explicit Parallel Structuring for Rule-Based Programming Shiow-yang Wu and James C. Browne, The University of Texas at Austin. CMMD I/O : A Parallel Unix I/O Michael L. Best, Craig Stanfill, Adam Greenberg, and Lewis W. Tucker, Thinking Machines Corporation. Symbolic Synthesis of Parallel Processing Systems James J. Liu and Milos D. Ercegovac, University of California, Los Angeles. Barrier Synchronization in Distributed-Memory Multiprocessors Using Rendezvous Primitives Sandeep K. S. Gupta and Dhabaleswar K. Panda, The Ohio State University. 1:30 PM - 3:30 PM, SESSION 13, Networks-III Chair: Dhabaleshwar K. Panda, The Ohio State University Least Common Ancestor Networks Isaac D. Scherson and Chi-Kai Chien, University of California, Irvine. The Clustered-Star Graph: A New Topology for Large Interconnection Networks Shahram Latifi and Nader Bagherzadeh, University of California, Irvine. Dynamic Embeddings of Trees and Quasi-Grids into Hyper-de Bruijn Networks Sabine Ohring, University of Wurzburg, and Sajal K. Das, University of North Texas. On the Hierarchical Hypercube Interconnection Network Q. M. Malluhi, Magdy A. Bayoumi, and T. R. Rao, University of Southwestern Louisiana. Mapping Interconnection Networks into VEDIC Networks Vipin Chaudhary, Wayne State University, Bikash Sabata and J. K. Aggarwal, University of Texas at Austin. Hypershere Mapper: A Nonlinear Programming Approach to the Hypercube Embedding Problem John K. Antonio, Purdue University, and Richard C. Metzger, Griffiss Air Force Base. 1:30 PM - 3:30 PM, SESSION 14, Applications-II Chair: Pearl Wang, George Mason University Experimental Evidence for the Power of Random Sampling in Practical Parallel Algorithms Mujtaba Ghouse and Michael T. Goodrich, Johns Hopkins University. Parallel Analog Algorithms for Processing Polygonal Images on a Systolic Screen Sumanta Guha, University of Wisconsin-Milwaukee. Efficient Parallel Formulations for Some Dynamic Programming Algorithms George Karypis and Vipin Kumar, University of Minnesota. Fast Connectivity Algorithms on a Reconfigurable Network of Processors Hussein M. Alnuweiri, University of British Columbia. Parallel Dynamic st-numbering and Applications Eliezer Dekel and Jie Hu, University of Texas at Dallas. A Tensor Product Formulation of Strassen's Matrix Multiplication Algorithm with Memory Reduction B. Kumar, C-H. Huang, and P. Sadayappan, The Ohio State University, J. R. Johnson, Drexel University, and R. W. Johnson, St. Cloud University. 1:30 Pm - 3:30 Pm, Session 15, Software-Ii Chair: Craig Reinhart, Hughes Research Laboratories Critical Performance Path Analysis And Efficient Code Generation Issues For The Seamless Architecture D. L. Bright, B. H. Pease, M. L. Roderick, S. Sundaram, And T. L. Casavant, University Of Iowa, And S. A. Fineberg, Nasa Ames Research Center. Implementation Of Distributed Asynchrinous Algorithms With Stochastic Delays For Solving Time Drifting Optimization Problems Bassem F. Beidas And George P. Papavassilopoulos, University Of Southern California. Data-Parallel Functional Programming Steven Vanderweil And James A. Davis, Iowa State University. Advanced Methods Of Performance Data Processing And Analysis Dianne Rover, Abdul Waheed, And Markus Doetsch, Michigan State University. Process Groups: A Mechanism For The Coordination Of And Communication Among Processes In The Venus Collective Communication Theory Vasannth Bala Ad Shlomo Kipnis, Ibm T. J. Watson Research Center. The Data-Parallel Ada Run-Time System, Simulation And Emperical Results Herbert G. Meyer, Intel Supercomputer Systems Division, And Stefan Jaehnichen, Technische Universitat Berlin. 4:00 PM - 6:00 PM, Panel Discussion Will Massively Parallel Processing Ever Supply General Purpose High Performance Computing? Moderator: Richard Freund, Naval Research And Development Center Panelists: Prith Banerjeee, University Of Illinois Fran Berman, University Of California, San Diego Mary Eshaghian, New Jersey Institute Of Technology Evans Harrington, Cray Research Kai Hwang, Usc Chani Pangli, Kendall Square Research Vaidy Sunderam, Emory University Bob Voigt, National Science Foundation Jack Worlton, Worlton And Associates -- Friday April 16 --- 8:30 Am - 9:30 Am Keynote Address Writing Correct Parallel Programs. K. Mani Chandy, California Institute Of Technology 10:00 Am - 12:00 Pm, Session 16, Networks -Iv Chair: Suresh Chalasani, University Of Wisconsin, Madison On Some Topological Properties Of Hypercube, Incomplete Hypercube And Supercube Arunabha Sen, Arizona State University, Abhijit Sengupta, University Of South Carolina, And Subir Bandyopadhyay, University Of Windsor. Design And Analysis Of Generalized Link Extended Hierarchical Interconnection Networks Omar H. Karam And Dharma P. Agrawal, North Carolina State University. An Analytical Model For Wormhole Routing In Multicomputer Interconnection Networks Wei-Jing Guan, Wei K. Tsai, And Douglas Blough, University Of California, Irvine. Optimal Broadcasting In Binary deBruijn Networks And Hyper-deBruijn Networks Elango Ganesan And Dhiraj K. Pradhan, Texas A&M University. Selection, Routing And Sorting On The Star Graph Sanguthevar Rajasekaran, University Of Pennsylvania, And David S. L. Wei, Radford University. Delay Analysis Of Synchronous Circuit-Switched Delta Networks Amiya Bhattacharya, Ramesh R. Rao, And Ting-Ting Y. Lin, University Of California, San Diego. 10:00 Am - 12:00 Pm, Session 17, Applications-Iii Chair: Eugen Schenfeld, NEC Research Institute Strategies For Mapping Lee'S Maze Routing Algorithm Onto Parallel Architectures I-Ling Yen, Michigan State University, Rumi M. Dubash And Farokh B. Bastani, University Of Houston. Parallel: Applying Parallel Processing To NLP Minhwa Chung And Dan Moldovan, University Of Southern California. Parallel Computation Of Solvent Accessible Surface Area Of Protein Molecules Edward Suh, B. K. Lee, Robert Martino, National Institutes Of Health, Bhagirath Narahari, George Washington University, And Alok N. Choudhary, Syracuse University. Parallel Simulated Annealing for the n-Queens Problem R. Shonkwiler, Farzad Ghannadian, And C. O. Alford, Georgia Institute Of Technology. Computing Convolutions On Mesh-Like Structures Otfried Schwarzkopf, Utrecht University. VLSI Architectures For Depth Estimation Using Intensity Gradient Analysis Raghu Sastry And N. Ranganathan, University Of South Florida, And Ramesh C. Jain, University Of Michigan. 10:00 Am - 12:00 Pm, Session 18, Systems-I Chair: Lonnie Welch, New Jersey Institute Of Technology Global Semigroup Operations In Faulty Simd Hypercubes C. S. Raghavendra, Washington State University, And M. A. Sridhar, University Of South Carolina. Speedup, Communication Complexity And Blocking -- A La Recherche Du Temps Perdu Dan C. Marinescu And John R. Rice, Purdue University. The Cm-2 Data Transposition Problem Ronald J. Vetter, David H. C. Du, And Alan E. Klietz, University Of Minnesota. Class And User Based Parallelism In Raven Donald Acton And Gerald Neufeld, University Of British Columbia. VMPP: A Virtual Machine For Parallel Processing Edmond C. Loyot, Jr., and Andrew S. Grimshaw, University Of Virginia. Autonomous Parallel Heuristic Combinatorial Search Chao-Chun Wang and Leah H. Jamieson, Purdue University. 1:30 Pm - 3:30 Pm, Session 19, Networks-Iv Chair: Steve Olariu, Old Dominion University On Simulations Of Linear Arrays, Rings and 2-D Meshes On Fibonacci Cube Networks Bin Cong and Sanjay Sharma, South Dakota State University, S. Q. Zheng, Louisiana State University. Parallel Implementation Issues Of The Textured Algorithm For Optimal Routing Problem In Data Networks Garng Morton Huang, Shan Zhu and Wen-Lin Hsieh, Texas A&M University. A Dynamic Multiple Copy Approach For Message Passing In A Virtual Cut-Through Environment Moncef Hamdaoui and Parameswaran Ramanathan, University Of Wisconsin-Madison. Performance Of Buffered Multistage Interconnection Networks In Non Uniform Traffic Environment M. Atiquzzaman and M. S. Akhtar, La Trobe University. Efficient Address Encodings For Optical Message Switching Systems Yosi Ben-Asher, Haifa University, Aviad Cohen, Hebrew University, and Assaf Schuster, Technion-Israel Institute Of Technology. A New Model For The Performance Evaluation Of Synchronous Circuit Switched Multistage Interconnection Networks Shuo-Hsien Hsiao and C. Y. Roger Chen, Syracuse University. 1:30 Pm - 3:30 Pm, Session 20, Applications-Iv Chair: Salim Hariri, Syracuse University Parallel Execution Of Real-Time Rule-Based Systems Albert Mo Kim Cheng, University Of Houston. Managing The Bottlenecks In Parallel Gauss-Seidel Type Algorithms For Power Flow Analysis G. Huang and W. Ongsakul, Texas A&M University. Towards Understanding The Role Of Block Partitioning In Sparse Cholesky Factorization Sesh Venugopal, Rutgers University, and Vijay K. Naik, Ibm T.J. Watson Research Center. Parallel A* Algorithms And Their Performance On Hypercube Multiprocessors Shantanu Dutt and Nihar R. Mahapatra, University Of Minnesota. Mapping Of Uniform Dependence Algorithm Onto Fixed Size Processor Arrays Zhigang Chen and Weijia Shang, University of Southwestern Louisiana. On the Utilisation of Data Duplication to Accelerate the SORT Operation On Mesh Architectures Hossam ElGindy, The University Of Newcastle. 1:30 PM - 3:30 PM, Session 21, Systems-Ii Chair: Dan Moldovan, University of Southern California An Efficient Atomic Broadcast Protocol For Client-Server Models Thomas Becker and Klaus Grieger, University Of Kaiserslautern. Transformation Of Doacross Loops On Distributed Memory Systems A. Zaafrani and M. R. Ito, University Of British Columbia. Automatic Parallelization Of LINPACK Routines On Distributed Memory Parallel Processors Matthias Neeracher and Roland Ruhl Gloriastrasse, ETH. Performance Characteristics Of The IPSC/860 and CM-2 I/O Systems John Krystynak and Bill Nitzberg, NASA Ames Research Center. OCCAM Prototyping Of Massively Parallel Applications From Colored Petri-Nets F. Breant and J. F. Peyre, University Of Paris. C Parallelizing Compiler On Local-network-based Computer Environment Kouichi Asakura, Toyohide Watanabe, and Noboru Sugie, Nagoya University. -------------------------------------------------------------------------- Part III: Workshops and Tutorials --------------------------------- Workshops --------- 2nd WORKSHOP ON HETEROGENEOUS PROCESSING ---------------------------------------- Workshop Chair: Richard F. Freund, Naval Research and Development Center Program Co-Chairs: Mary Eshaghian, New Jersey Institute Of Technology Vaidy Sunderam, Emory University Program Committee: Fran Berman, University Of California, San Diego Tom Kitchens, Department Of Energy Sam Lomonaco, University Of Maryland Danny Menasce, George Mason University Jerry Potter, Kent State University Viktor K. Prasanna, USC Guna Seetharaman, University Of Southwestern Louisiana H. J. Siegel, Purdue University 8:30 Am - 9:30 Am, HP Keynote Address Heterogeneous Associative Computing. Jerry L. Potter, Kent State University 10:00 Am - 12:00 Noon, Hp Session-I, Theory Chair: Fran Berman, University Of California, San Diego A Selection Theory and Methodology for Heterogeneous Supercomputing Song Chen and Mary M. Eshaghian, New Jersey Institute Of Technology, Ashfaq Khokhar and Muhammad E. Shaaban, University Of Southern California. Partitioning Problems For Heterogenous Computer Systems M. Ashraf Iqbal, University Of Engineering and Technology, Lahore. Experiments With a Task Partitioning Model For Heterogeneous Computing David J. Lilja, University Of Minnesota. Heuristics For Mapping Parallel Computations To Heterogeneous Parallel Architectures L. Tao and Y.C. Zhao, Concordia University, and Bhagirath Narahari, George Washington University. Load Distribution Optimization In Heterogeneous Multiple Processor Systems Emile Haddad, Virginia Polytechnic Institute and State University. Problem Representations For An Automatic Mapping Algorithm On Heterogeneous Processing Environments Chokchai Leangsuksun and Jerry Potter, Kent State University. 1:30 Pm - 3:30 Pm, Hp Session-Ii, Tools and Systems Chair: Muhammad E. Shaaban, University Of Southern California A Framework For Compile-Time Selection Of Parallel Modes in an SIMD/SPMD Heterogeneous Environment Daniel W. Watson, H.J. Siegel, John K. Antonio, and Mark A. Nichols, Purdue University. Triton/1: A Massively-Parallel Mixed-Mode Computer Designed To Support High Level Languages Christian G. Herter, Thomas M. Warschko, Walter F. Tichy, and Michael Philippsen, University Of Karlsruhe. Towards A Virtual Multicomputer Duncan Batey and Julian Padget, University Of Bath. Developing Applications for a Heterogeneous Computing Environment Ralph Butler, William D. Gropp, and Ewing L. Lusk, Argonne National Laboratory. Heterogeneous by Design: An Environment For Exploiting Heterogeneity Richard P. LaRowe, Jr., and Thomas H. Probert, Worcester Polytechnic Institute. Xad: A Tool For Monitoring PVM Programs Adam Louis Beguelin, Carnegie Mellon University. 4:00 Pm - 6:00 Pm, Hp Session-Iii, Applications Chair: Guna Seetharaman, University Of Southwestern Louisiana Invited Paper: Heterogeneous Computing For Command and Control J. P. Schill, Naval Research and Development Center. A Case Study In Metacomputing: Distributed Simulations Of Mixing In Turbulent Convection A. E. Klietz, Minnesota Supercomputer Center, A.V. Malevsky and K. Chin-Purcell, University Of Minnesota. Partitioning Algorithms for A Class Of Application Specific Multiprocessor Architectures C. De Castro And S. Yalamanchili, Georgia Institute Of Technology. Design Of A Heterogeneous Parallel Processing System For Beam Forming C. H. Lee And Dan Sullivan, Naval Postgraduate School. Image Understanding: A Driving Application For Research In Heterogeneous Parallel Processing Charles C. Weems, Jr., University Of Massachusetts. Discussion And Chair'S Concluding Remarks. Workshop On Parallel And Distributed Real-Time Systems ------------------------------------------------------ Workshop Co-Chairs: Alexander D. Stoyenko, New Jersey Institute Of Technology Lonnie R. Welch, New Jersey Institute Of Technology As evidenced in several lectures at the recent NATO Advanced Study Institute On Real-Time Computing, there is a need for collaboration between the researchers in the field of Parallel and Distributed Processing and the field of Real-Time Systems. Parallel and Distributed Processing techniques can be applied in Real-Time Systems to meet timing constraints and to increase Fault Tolerance. To encourage discussion of research results from these fields in a forum where scientists from each field are present, a one day workshop will be held. The workshop will include paper presentations by leading researchers working in these complimentary areas. The state-of-the-art in areas such as those listed below will be described. -Assignment Of Tasks To Processors -Compiler Techniques -Complex Systems Engineering -Scheduling and Resource Allocation -Architecture and Hardware -Operating Systems -Fault Tolerance -Communications -Case Studies and Applications -Tools -Parallel Algorithms For Further Information, Contact Either Program Co-Chair At: The Real-Time Computing Laboratory Department Of Computer and Information Science New Jersey Institute Of Technology University Heights Newark, NJ 07102 (201) 596-5765 alex@vienna.njit.Edu (201) 596-5683 welch@vienna.njit.Edu Fax: (201) 596-5777 This Workshop is Co-Sponsored by the Real-Time Computing Laboratory at NJIT, The Institute for Systems Integration at NJIT, and the IEEE Technical Committee on Parallel Processing. 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 The workshop will focus on the I/O bottleneck facing parallel computer systems for many important applications such as multimedia information systems and volume visualization. Recognition of the importance of this problem has been growing steadily, and there have been a number of proposed solutions. There have been proposals to parallelize access to disks by striping or interleaving, provide enhanced architectural support for I/O by novel I/O interconnection architectures, implement sophisticated resource management algorithms for parallel I/O, enhance compiler support for overlapping parallel I/O with computation, and to structure applications to minimize the impact on the I/O subsystem. The proposals thus span hardware, architecture, systems software and algorithms. In addition, several commercial products have become available which provide parallel I/O capabilities for supercomputer systems. The workshop will bring together researchers in order to foster further research on these approaches and their integration into comprehensive systems solutions. Particular questions to be discussed will include: - the data transfer demands of current and future applications - compiler and operating systems support for parallel I/O - algorithms for managing the resources required by parallel I/O - design and performance of I/O subsystems and interconnection architectures - the impact of high-speed storage and channel technology The workshop will feature research papers as well as a panel discussion. For further information, please contact one of the workshop co-chairs. Ravi Jain Bellcore MRE 2P342 445 South Street Morristown, NJ 07962 Phone: (201) 829-4756 John Werth Department Of Computer Sciences Taylor Hall Room 2.124 University Of Texas At Austin Austin, TX 78712 Phone: (512) 471-9583 For enquiries by e-mail: ippsio@thumper.bellcore.com WORKSHOP ON ANALYZING SCALABILITY OF PARALLEL ALGORITHMS AND ARCHITECTURES ----------------------------------------------------------------------------- Workshop Co-chairs: Vipin Kumar, University of Minnesota Xian-He Sun, NASA Langley Research Center Scalability of a parallel computer system denotes the degree to which the system can effectively use increasing number of processors. Scalability analysis could be used to predict/analyze performance when the parallel computer is scaled up in terms of number of processors, processors speed and the speed of communication. It could be used for designing better parallel algorithms and architectures. The need for a concept of scalability both with respect to the architecture and the algorithm (implemented on the architecture) has been well established. Yet, there is no consensus on how the scalability of a parallel system should be determined. The objective of this workshop is to critically assess the state of the art in the theory of scalability analysis, and motivate further research. The workshop will bring together research done by theoreticians, application developers, and designers of architectures and system software on scalability analysis of large-scale parallel systems. Topics of interest include but are not limited to scalability metrics, scalability analysis of parallel algorithms, applications, and architectures, Cost effectiveness of scaling parallel architectures in terms of performance, software tools for scalable parallel systems. The workshop will consist of invited as well as contributed presentations by various researchers, and discussion sessions involving presenters and participants. Two copies of an extended abstract (preferably no more than 4 pages) should be sent to each of the workshop chair by February 1, 1993. The authors will be notified of the decision by March 1, 1993. Vipin Kumar Computer Science Department University of Minnesota Minneapolis, MN 55455 Tel: (612)-624-8023 internet:kumar@cs.umn.edu FAX: (612)-625-0572 Xian-He Sun ICASE NASA Langley Research Center Hampton, Virgina 23665 Tel: (804)-864-8018 internet: sun@icase.edu FAX: (804)-864-6134 WORKSHOP ON STRATEGIC DIRECTIONS IN COMPUTATIONAL MICRODEVICES -------------------------------------------------------------- Workshop Co-chairs: Sandeep Gulati, JPL/Caltech James Burr, Stanford University Jacob Barhen, JPL/Caltech This workshop co-sponsored by NASA and DoD brings together researchers of varied experience, to identify and evolve new directions and engineering practices in massively parallel, reconfigurable, ultra-high density microcomputing devices, packaging and implementation technologies. In the context of current technology outreach, this workshop shall seek to explore the synergism between advances in electronic, quantum-optoelectronic and molecular electronic devices, biosensors and micropackaging. An important unifying element underlying all disussion would be the emphasis on low energy computation. In particular emerging technologies for high-density processor-memory, processor-processor and processor-sensor fusion will be examined. This workshop shall by design be interdisciplinary, specifically based on a flow of ideas across the boundaries of biological information processing, nanotechnology, biomolecular or biomimetic materials, traditional computer science, applied physics and fabrication technology. In addition to exploring the computational physics underlying the microdevices, the workshop would provide a juxtaposition to massively parallel and distributing processing as well as neuroprocessing. In summary, an attempt will be made to leverage this technological cross-fertilization to address fundamental issues in phenomenology, molecular circuitry and fabrication technology and implications to machine intelligence. For additional detail contact any of the workshop chairs. Sandeep Gulati, Tel: (818)-354-3877, email: sgulati@jpl-cray.jpl.nasa.gov James Burr, Tel: (415)-723-4087, email: burr@mohave.stanford.edu Jacob Barhen, Tel: (818)-354-9218 Tutorials --------- TUTORIAL 1 (8:30 AM-12:30 PM, April 13) Connection Machine CM-5: Programming for Performance Lew Tucker and Adam Greenberg, Thinking Machines Corporation Who Should Attend: This tutorial is targeted at application developers and scientists interested in learning about the programming techniques available on the massively parallel Connection Machine CM-5. Course Description: The CM-5 is a massively parallel computer designed with an architecture which supports multiple forms of parallelism: data parallelism, message passing, and distributed processing. Application developers and research scientists are now presented with an unprecedented choice of programming models which may used to address a particular application requirement. This course will begin with a brief discussion of the basic architecture of the CM-5 and move quickly on to the issue of how developers may make use of different programming models and techniques to achieve high performance. Data parallel programming is supported by Fortran 90 (CM Fortran/HPF) and C*. The MIMD view provides independent threads and message passing. Of particular interest is the manner in which different forms of parallelism (data parallel and asynchronous message passing) may be used in the same application program. This "global/nodal" programming model combines these two major modes allowing "global-view" languages to call local node-level subroutines. This merging of the two dominant schools of parallel programming opens up new opportunities for achieving high performance on parallel machines. Lecturers: Lew Tucker is a senior scientist and director of programming models at Thinking Machines Corporation. He is one of the principle system architects of the CM-5. Adam Greenberg is project leader of the CMMD message passing group at Thinking Machines Corporation and conducts research on massively parallel algorithms for fluid dynamics. TUTORIAL 2 (2:00 PM - 6:00 PM, April 13) Data Parallel Programming and Application Development on the MasPar Series of MPP Systems Mahesh Rajan and Fairy Knappe MasPar Computer Corporation Who Should Attend: This course is geared towards the scientist or engineer interested in programming techniques for MasPar's MPP systems. Course Description: The objective of this tutorial is to familiarize the audience with MasPar's MP Series architecture and its integrated programming environment which includes MasPar Fortran (Fortran 90), MasPar's Programming Language (MPL-MasPar's Parallel C), plus tools to accelerate the development of data-parallel software. Various examples of application kernels will be overviewed. Porting and optimization techniques will be discussed. This tutorial will cover the following: - Overview on the MP-Series Architecture which will include Processing, communication, and IO subsystems. - Overview of MasPar's programming environment which will highlight many features is this window-based toolset. - Overview of Programming Languages and Application Libraries. - Kernels from various applications will reviewed with emphasis on data structures to exploit parallelism in the application. Lecturers: Mahesh Rajan is a Systems Engineer for MasPar Computer Corporation. Prior to joining MasPar, Dr. Rajan worked for Supercomputing Solutions, Inc., as a manager of Math Libraries. He received his doctorate degree in Engineering Mechanics from Virginia Tech in 1981. He served as a faculty at Arizona State University from 1981 to 1988. His research interests are parallel computer algorithms, computational mechanics and nonlinear mechanics. Fairy Knappe is also a Systems Engineer for MasPar. Before joining MasPar, Fairy worked for Star Technologies, Inc. a manufacturer of vector-based processors, from 1983-1985 and from 1986 to 1992, in various positions from Software Engineering to Technical Sales Support. She was also in Software Engineering at ETA Systems for a 12-month period in 1985-86. Fairy has a B.S degree in Quantitative Systems from Arizona State University. TUTORIAL 3 (8:30 AM - 6:00 PM, April 13) Programming Support for Distributed-Memory Computing Environments Lionel M. Ni and Philip K. McKinley, Michigan State University Who Should Attend: Intended for engineers, managers, researchers, and other users who are interested in developing programming tools or application programs that can exploit such tools in distributed-memory computing environments, including scalable multiprocessors and networked collections of workstations. Course Description: Both distributed-memory multiprocessors and networks of workstations are considered to be promising platforms for high performance computing. Although many such environments are available, their future success depends on appropriate programming support. The objective of this tutorial is to describe different methods and levels of support to assist programmers in developing computationally-intensive applications in such environments. The tutorial will begin with an introduction to the architectures of existing and emerging distributed-memory computing environments, including massively parallel computers and high-speed interconnects for workstations, followed by a discussion of parallel computation models and low-level communication mechanisms and protocols. Both traditional message-based parallel programming support, such as PVM, P4, and PICL, and high-level data-parallel languages, such as High Performance Fortran (HPF), will be covered. Scalable communication libraries and compilers that translate language constructs into appropriate communication primitives will be described. Finally, several visualization and monitoring tools, such as ParaGraph and HeNCE, which assist users in developing and testing scalable software, will be reviewed. Course Outline: . Introduction and Overview . Distributed-Memory Computing Environments . Parallel Computation Models . Communication Architectures and Protocols . Message-Based Programming Support . High-level Programming Languages . Compiler Support . Scalable Library Support . Programming and Performance Visualization Tools Lecturers: Dr. Lionel M. Ni is professor of computer science and director of Advanced Computer Systems Laboratory at Michigan State University. He has worked in the area of parallel processing and distributed computing for over 15 years and has extensive technical publications in this area. Dr. Ni is serving as a member of the editorial boards of Journal of Parallel and Distributed Computing and IEEE Transactions on Computers. Dr. Philip K. McKinley is an assistant professor in the Department of Computer Science at Michigan State University. He received the Ph.D. degree in computer science from the University of Illinois at Urbana-Champaign, and previously was a member of technical staff at AT&T Bell Laboratories. His current research interests include scalable architectures and software, communications libraries for parallel and distributed computing, multicast communication, gigabit network architectures and protocols, and parallel numerical algorithms. TUTORIAL 4 (8:30 AM - 6:00 PM, April 13) Software Tools for Visualization of Parallel/Distributed Programs and Systems Thomas L. Casavant, University of Iowa Who Should Attend: As a relatively young field, it has appeal to individuals from both academia as well as industry. The area is growing in importance for a large community of parallel computer users. Such users are becoming more and more common as parallel sys- tems work their way into more and more application settings. Advances to date have come mostly from academics, but the influence on industrial and commercial settings for the future will be dramatic. Course Description: This tutorial overviews major contributions to visualization for development of software for parallel/distributed computing. Emphasis is on improving the software development process for high-performance parallel com- puters via visualization techniques for program creation, debugging, verifi- cation, and maintenance. The topic is of growing importance for many paral- lel computer users, who are becoming more common as parallel systems appear in increasingly more application settings. Recent advances have come mostly from academics, but the influence on industrial and commercial settings for the future will be dramatic. General concepts, as well as a videotape illus- tration of practical tools are presented. Lecturer: Thomas Lee Casavant (Ph.D., ECE'86) was with the School of EE at Purdue University (86-89) where he was Director of the Parallel Pro- cessing Laboratory. Since 1989, he has been with the ECE Department at Iowa. Dr. Casavant has published numerous papers on parallel/distributed computing and has presented work in journals and at conferences in the US, Europe, and Asia. He was co-editor for the August 1991 issue of IEEE Computer on ``Dis- tributed Computing Systems,'' and is guest editor for the May 1993 issue of Journal of Parallel and Distributed Computing on ``Visualization Tools for Parallel Programs and Systems.'' TUTORIAL 5 (8:30 AM - 12:30 PM, April 16) High Performance I/O Systems Anujan Varma, University of California, Santa Cruz and Jai Menon, IBM Almaden Research Center. Who should attend: The tutorial is intended for practicing engineers, system designers, technical managers, and researchers in computer architecture seeking an introduction to the rapidly-changing area of I/O systems. Course Description: This tutorial is organized as two parts: The first part covers storage systems and the second part discusses I/O communication. Disk arrays are the focus of the first part. The following topics are covered: 1. Introduction: I/O system organizations; types of disk arrays and their characteristics -- RAID levels 0-6; parity striping; other types of disk arrays; advantages and disadvantages of different types of arrays. 2. Sparing Issues: Effect of sparing; estimating number of spares; shared versus non-shared spares; immediate versus deferred replacement of spares 3. Disk Array Performance Issues: Array operating modes --- normal, degraded, rebuild; performance of arrays in the three different modes; choice of array building blocks (4+P versus 8+P versus 16+P); choice of how to rebuild and rebuild unit --- sector rebuild, track rebuild, cylinder rebuild; choice of sparing on performance. 4. Case studies of RAID products: IBM 3514, IBM 9337, Core Microarray, Mylex DAC960, NCR ADP-92-06. The second part provides an overview of high-speed I/O channels. Topics include the following: 1. Overview of I/O channel architectures and standards. 2. The HIPPI Channel: Physical-layer protocol; framing; switch control; mapping to IPI-3 command sets; serial HIPPI. 3. The IBM ESCON Architecture: Architecture layers and their functions; addressing; framing; initialization protocols; device-level protocols; pacing; ESCON Director. 4. The ANSI Fibre Channel Standard: Physical link and interface choices; transmission coding; framing and addressing; FC-2 service classes and their characteristics; fabric design and management. Lecturers: Anujan Varma is assistant professor in computer engineering at the University of California, Santa Cruz. He was previously employed as a Research Staff Member at the IBM Thomas J. Watson Research Center. At IBM, he worked on the design and analysis of high-speed switching systems for the fiber-optic I/O channels based on the ESCON Architecture. Dr. Varma's current research interests include high-speed switching, high-speed communication networks and their applications, I/O systems, and multiprocessor interconnection networks. He has published more than 50 papers in these areas and holds four U.S. patents. He received the NSF Young Investigator Award in 1992 and the IEEE Darlington best-paper award for a paper published in IEEE Transactions on Circuits and Systems in 1991. Jai Menon is currently Manager of Storage Attachment Architecture and Performance Modeling in the Computer Science Department at the Almaden Research Center. His group has been working on disk arrays since 1988, and it is recognized as the leading industrial research group doing disk array research. Dr. Menon has received many awards from IBM including an Outstanding Technical Achievement Award (OTAA) for his efforts as the chief architect of the IBM S01787 disk controller, and four Invention Achievement Awards (IAAs) from IBM. He has published widely in the areas of I/O subsystems and disk arrays and has given many talks and tutorials on disk arrays at universities. His group has close interactions with all the leading universities doing disk array research (UC Berkeley, CMU, Univ of Michigan). TUTORIAL 6 (2:00 PM - 6:00 PM, April 16) Parallel Programming on the Intel Paragon Gary Withers, Intel Corporation Who Should Attend: Engineers, scientists and programmers desiring to better understand Paragon in order to more easily write or port codes and improve program execution performance. A working knowledge of C or Fortran programming is expected. Prior experience with parallelism and iPSC/860 (NX/2) message passing is recommended but not required. Course Description: The tutorial takes a view of Paragon architecture, operating system, and current functionality. Using a bottom-up approach, it begins with the low-level hardware and software details, moves up through the operating system to a discussion of mesh partition management and process scheduling, and finishes with the program development process, emphasizing how to get the best possible performance. Subject Matter Outline A. The Parallel Programming Model 1. Distributed Memory Architectures 2. Programmer's View of the System B. Intel Supercomputer System Architecture Overview 1. Node and System Hardware 2. Software and Tools C. Message-Passing and System Commands 1. Accessing and Using the Nodes 2. Parallel Programming using Message-Passing D. Parallel Decomposition Strategies and Techniques 1. Domain Decomposition 2. Control-Oriented Decomposition Lecturer: Gary Withers is the Director of Customer Training at Intel's Supercomputing Systems Division. He has been teaching and coordinating Intel's Parallel Programming Workshops for four years. Before joining Intel, Gary taught for the Department of Naval Reactors as a member of the technical staff at Naval Nuclear Power School in Orlando, Florida. TUTORIAL 7 (8:30 AM - 6:00 PM, April 16) Introduction to Parallel Processing Mary M. Eshaghian, New Jersey Institute of Technology Who Should Attend: This tutorial is intended for all computer and computational scientists interested in an introduction to design and analysis of parallel architectures and algorithms. Course Description: This course will present an overview of advanced computer architectures and parallel processing. The materials covered are divided into six parts. In the first part, various parallel models of computations and different classification of parallel systems are presented. In Part 2, several memory organizations for multiprocessor systems are introduced. Pipelining, Vector Processing and Systolic arrays are discussed in Part 3. This section includes several examples of such CPU designs and a set of algorithms for generic arithmetic computations. Part 4 is entitled SIMD Architectures and Algorithms. This parts contains a detailed overview of various SIMD topologies, such as VlSI architectures, meshes and hypercubes. Efficient techniques for mapping algorithms onto these models are presented and evaluated. Interconnection Networks are introduced in Part 5. Design issues for Crossbars versus various multi-stage interconnection networks are analyzed. In the last part of the tutorial, advanced topics in parallel processing including Optical computing and Heterogeneous computing are discussed. Lecturer: 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 until August, 1991. Currently, she is an assistant professor at the department of Computer and Information Science, New Jersey Institute of Technology. Her area of research in parallel processing includes: Heterogeneous Computing, VLSI architectures and algorithms, and Optical Interconnection networks. She serves on the executive board of IEEE Technical Committee on Parallel Processing. She is a program co-chair of Heterogeneous Processing Workshop, and a member of the technical committee of IEEE International Parallel Processing Symposium. TUTORIAL 8 (8:30 AM - 6:00 PM, April 16) Parallel Processing Algorithms and Systems H. J. Siegel, Purdue University Who Should Attend: People with a computer science or computer engineering background who are interested in the use and design of large-scale parallel processing systems. Course Description: The use and design of tightly-coupled large-scale parallel processing systems (i.e., 64 to 64K processors) are examined through case studies of algorithms and machines. Models of SIMD (synchronous) and MIMD (asynchronous) parallelism are described and contrasted. Various tasks are analyzed to demonstrate different techniques for mapping algorithms onto parallel machines. Issues addressed include SIMD/MIMD trade-offs, data distribution, influence of network topology, the impact of partitioning the system for subtask parallelism, the effect on execution time of increasing the number of processors used, CU/PE overlap in SIMD machines, and the difficulty of automatic parallelization of algorithms. The architectures of parallel systems such as CM-2, CM-5, IBM RP3, MasPar MP-1 and MP-2, nCUBE, PASM, and Ultracomputer are briefly overviewed. The tutorial concludes with a discussion of some of the problems (``alligators'') encountered in using and designing parallel systems. 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 MSE, MA, and PhD degrees from Princeton. He has coauthored over 150 technical papers and authored one book. He is a Fellow of the IEEE, and was a Coeditor-in-Chief of the ``Journal of Parallel and Distributed Computing.'' -------------------------------------------------------------------------- PART IV: Registration Forms (symposium and hotel) ------------------------------------------------- Cut Here ------------------------------------------------------------------------ IPPS '93 HOTEL RESERVATION FORM ------------------------------- Please mail or fax to: (requests after March 23 are not guaranteed) NEWPORT BEACH MARRIOTT HOTEL & TENNIS CLUB 900 Newport Center Drive, Newport Beach, CA 92660 VOX: (714)640-4000 FAX: (714)640-5055 NAME: _________________________________________________________________ COMPANY/UNIVERSITY: ___________________________________________________ ADDRESS: ______________________________________________________________ CITY/STATE/ZIP/COUNTRY: ________________________________________________ BUSINESS PHONE: ___________________ HOME PHONE: _______________________ RESERVATION MUST BE GUARANTEED BY ONE NIGHT'S ADVANCE DEPOSIT OR COMPANY GUARANTEE OF PAYMENT. PLEASE BE SURE YOUR RESERVATION REACHES THE HOTEL 21 DAYS IN ADVANCE TO INSURE YOUR ACCOMMODATIONS. PLEASE NOTES: CHECK-IN TIME IS 4:00 PM -CHECK-OUT TIME IS 12:00 NOON 7TH INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM APRIL 13-16, 1993 - NEWPORT BEACH, CALIFORNIA, USA IPPS '93 NEWPORT BEACH MARRIOTT HOTEL Nightly Rate = $110 ----------------------------------------------------------- All reservations must be received by March 23, 1993. Requests prior to & after IPPS '93 dates will be accepted on space available basis only. I plan to arrive ______________ I plan to depart _________________ (date) (date) (Note: Transportation to and from John Wayne Airport is available on a scheduled basis) Please check: [ ] Single Occupancy [ ] Double Occupancy [ ] Sharing with ____________________________________ Credit Card Number: _________________________ Exp. Date: ___________ [ ] AMERICAN EXPRESS [ ] VISA [ ] MASTERCARD [ ] DISCOVER [ ] MARRIOTT VISA [ ] DINERS CLUB [ ] JCB Cut Here ---------------------------------------------------------- 7TH INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM APRIL 13-16, 1993 - NEWPORT BEACH MARRIOTT- NEWPORT BEACH, CALIFORNIA 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-1903 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 Late/Onsite Registration (Until March 26, 1993) (After March 26, 1993) Member $275 Member $330 Non-member $345 Non-member $415 Student $150 Student $150 TUTORIAL REGISTRATION: (Price per tutorial) HALF-DAY TUTORIALS FULL-DAY TUTORIALS (Tuesday, April 13) (Tuesday, April 13) ___ 1. Connection Machine (CM-5) ___ 3. Programming Support for Distributed Programming for Performance Memory Computing Performance ___ 2. Data Parallel Programming/ ___ 4. Software Tools for Visualization of Application Development Parallel/Distributed Programs (MasPar) (Friday, April 16) (Friday, April 16) ___ 5. High-Performance I/O Systems ___ 7. Introduction to Parallel Processing ___ 6. Parallel Programming on the ___ 8. Parallel Processing Algorithms INTEL Paragon and Systems TUTORIAL FEES: ADVANCE REGISTRATION LATE/ON-SITE REGISTRATION (Until March 26, 1993) (After March 26, 1993) HALF-DAY FULL-DAY HALF-DAY FULL-DAY Member $150 $230 Member $190 $275 Non-member $200 $285 Non-member $235 $345 TOTAL ENCLOSED: $ ______________ PAYMENT MUST BE ENCLOSED. PLEASE MAKE ALL CHECKS PAYABLE TO "IEEE COMPUTER SOCIETY." ALL PAYMENTS 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 refunds must be received in IEEE Computer Society office no later than 3/26/92. Refunds are subject to a $50 processing fee. All no-show registrations will be billed in full. Registration after April 2, 1993 will be accepted on-site only. Do not include my mailing address on: _____ Non-Society Mailing Lists _____ Meeting Attendee Lists (PLEASE MAKE HOUSING RESERVATIONS DIRECTLY WITH HOTEL. SEE HOTEL RESERVATION FORM ABOVE)