************************************************** SIXTH IEEE SYMPOSIUM ON PARALLEL AND DISTRIBUTED PROCESSING Registration form and Advance Program ************************************************** *********************************************************** Sixth IEEE Symposium on Parallel and Distributed Processing Registration form *********************************************************** Sponsors: IEEE-CS TC for Computer Architecture, TC for Distributed Computing, and IEEE-CS-Dallas Chapter Bristol Suites Hotel, Dallas, Texas October 26-29, 1994 Technical program, to be held October 26-28, features: - Keynote Speech 1: "Parallel & Distributed Computing: Competitors or Partners?", David Kuck (UIUC, USA), October 26, 1994. - Keynote Speech 2: "Teraflop Computing and Beyond", Steve Wallach (Convex Corp., USA), October 28, 1994. - Workshop 1: "Parallel and Super Computing in Mexico" Organized by Jose Luis Figueroa (Supercomputing Center, ITESM, Mexico) and S. Lakshmivarahan (Univ. of Oklahoma, USA), October 26, 1994. - Workshop 2: "Concurrent Object-Based Systems" Organized by Lonnie Welch (NJIT, USA) and Dieter K. Hammer (Eindhoven Univ. of Technology, The Netherlands), October 27, 1994. Full-day Tutorials (October 29): T1: Introduction to Parallel Computing, V. Kumar, University of Minnesota, USA. T2: Distributed and Object Oriented Database Systems, R. Elmasri and A. Helal, University of Texas at Arlington, USA. T3: Distributed Shared Memory: Concepts and Systems, J.Protic, M. Tomasevic and V. Milutinovic, IFACT, USA. ------------------------------------------------------------------------------ Hotel Reservations: Please place your reservations directly with Bristol Suites Hotel at 7800 Alpha Road, Dallas, Texas 75240, USA, Tel: (214) 233-7600, Fax: (214) 701-8618. You must mention that you are attending IEEE SPDP in order to receive the special symposium rate of $95/night for a single and $100/night for a double room. These rates include a complimentary full breakfast in the hotel's Cafe Biarritz. Please check with the reservations' desk for the applicability of other special rates, such as those available to AAA members. Reservations should be made before October 4, 1994. After this date, reservations are subject to space availability. Directions: Bristol Suites Hotel, the conference site, is located in North Dallas on the northwest corner of LBJ Freeway (635) and Coit Road. The hotel is about 25 minutes from the Dallas/Fort Worth (DFW) International Airport. By Car: Take DFW Int'l Airport north exit. Take LBJ Freeway (635) East towards Dallas, go approximately 18 miles, take Coit Road North Exit. Alpha Road is the first street crossing Coit north of the LBJ Freeway; take a left on Alpha. The hotel will be to your left. Shuttle Service: Super Shuttle provides van service from DFW Int'l Airport to the Bristol Suites for $12.00 per person each way. For more information and reservations, call (817) 329-2002. Once you arrive at the airport, go to the baggage claim area and using a free "Share-Ride" phone, dial 02 to inform Super Shuttle of your arrival. Weather: Dallas weather in late October ranges from mid 60's to high 70's Fahrenheit. ---------------------------------------------------------------------------- - Please send the completed registration form (below), along with your payment to the Registration Chair: Dr. Lonnie Welch, Dept. of Computer and Information Science, New Jersey Institute of Technology, University Heights, Newark, NJ 07102 USA, phone: (201) 596-5683, fax: (201) 596-5777, email: elch@vienna.njit.edu. PLEASE MAKE CHECKS PAYABLE TO "SPDP". - The symposium registration includes the attendance at the workshops and the symposium proceedings, banquet, and luncheon. Student registration does not include the luncheon. Advance Registration: Before October 4, 1994 Symposium Tutorial Advance On-site Advance On-site IEEE Mem. US$265 US$315 US$225 US$270 Non-Mem. US$330 US$395 US$280 US$335 Full-time Students US$180 US$225 US$225 US$270 IEEE Member:____ Non-Member:____ Student:____ IEEE/Student No.:______________________ Symposium: $_______ Tutorial: $_______ Specify choice of tutorial(s): T____ Total: $_______ _____Check enclosed, USA BANKS ONLY (payable to SPDP) ____Credit Card (VISA or Master Card ONLY) VISA___ or Master Card___ Credit Card No.:________________________________ Expiration Date:____________ Signature:_____________________________ Last Name:__________________________________ First Name:___________________________ Middle Initial:_____ Organization: _____________________________________________________ Address: _____________________________________________________ _______________________________________________ City, State, Zip/Country:_________________________________________ Phone: ___________________ Fax: ____________________ E-mail:___________________________________________ -------------------------------------------------------------------------- *********************************************************** Sixth IEEE Symposium on Parallel and Distributed Processing Advance Program *********************************************************** Wednesday, October 26, 1994 7:30 - 8:30 am On-site Registration - Conference Material Available at the Registration Desk 8:30 - 10:00 am Opening Session and Keynote Speech David Kuck - UIUC "Parallel & Distributed Computing: Competitors or Partners?" 10:00 - 10:30 am: BREAK 10:30 am - 5:00 pm- Workshop 1: "Parallel and Super Computing in Mexico" Organized by Jose Luis Figueroa (Supercomputing Center, ITESM, Mexico) and S. Lakshmivarahan (Univ. of Oklahoma, USA). 10:30 - 12:00 noon Session A-1:Potpourri I Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time Frank Dehne, Claire Kenyon and Andreas Fabri On the Design and Implementation of Broadcast and Global Combine Operations Using the Postal Model J. Bruck, L. de Coster, N. Dewulf, C.-T. Ho, and R. Lauwereins Embedding of Cycles in Rotator and Incomplete Rotator Graphs Subburajan Ponnuswany and Vipin Chaudhary Session B-1: Communications Optimal Fault Tolerant Communication Algorithms on Product Networks Using Spanning Trees Sabine R. Ohring and Dirk H. Hohndel Synchronization and Communication in Algorithmic Structures Mario J. Gonzalez and Linda F. Wilson Eager Combining: A Coherency Protocol for Increasing Effective Network and Memory Bandwidth in Shared-Memory Multiprocessors Ricardo Bianchini and Thomas J. LeBlanc Session C-1: Interconnection Networks I Simultaneous Access Renegable Priority Queues P. R. Venkata Subramaniam and Kam-Hoi Cheng Conflict-Free Data Access of Arrays and Trees in Parallel Memory Systems Sajal K. Das and Falguni Sarkar WICI: An Efficient Switching Scheme for Large Scalable Networks Hyunmin Park and Dharma P. Agrawal 12:00 - 1:30 pm: LUNCH 1:30 - 3:00 pm Session A-2: Real-Time Distributed Systems Timing Analysis of Real-Time Distributed Systems in CRSMs and ERL Yaodong Bi Assignment and Pre-Run-Time Scheduling of Object-Based, Parallel Real-Time Processes J. P. C. Verhoosel, D. K. Hammer, E. J. Luit, and Lonnie R. Welch Performability Analysis of Non-Repairable Multicomponent Systems Using Order Statistics Amiya Bhattacharya, Ramesh R. Rao, and Ting-Ting Y. Lin Session B-2: Applications I An Adaptive SOR Algorithm and Its Parallel Implementation for Power System Applications G. M. Huang and W. Ongsakul An Analysis of Parallel Synchronous and Conser- vative Asynchronous Logic Simulation Schemes William T. Baker and Ausif Mahmood Parallel Bidirectional Heuristic Search on the EM-4 Multiprocessor Andrew Sohn and Mitsuhisa Sato, S. Sakai, Y. Kodama, and Y. Yamaguchi Session C-2: Distributed Systems III Dynamic Load Balancing on a Distributed System M. D. Feng and C. K. Yuen Virtual Computers -- A New Paradigm for Distributed Operating Systems Banu Ozden, Aaron J. Goldberg and Avi Silberschatz Write Grouping for Update-Based Cache Coherence Protocols D. B. Glasco, B. A. Delagi, and M. J. Flynn 3:00 - 3:30 pm: BREAK 3:30 - 5:00 pm Session A-3: Multistage Interconnection Networks Star-Graph Based Multistage Interconnection Network for ATM Switch Fabric C. P. Ravikumar and G. Manimaran Multicast in Extra-Stage Multistage Interconnection Networks Chi-Ming Chiang and Sourav Bhattacharya, and Lionel M. Ni Bounds on the Number of Passes in Multistage Interconnection Networks Yshovardhan R. Potapalli and Dharma P. Agrawal Session B-3: Algorithms III Software Interleaving Ricardo Bianchini, Mark E. Crovella, L. Kontothanassis, and Thomas J. LeBlanc Program Dependence Analysis for Concurrency Exploitation in Programs Composed of Abstract Data Type Modules Guohui Yu and Lonnie R. Welch Minimum Dependence Distance Tiling of Nested Loops with Non- Uniform Dependences Swamy Punyamurtula and Vipin Chaudhary Session C-3: Routing I Matrix Transpose on Meshes with Wormhole and XY Routing Kuo-Shun Ding, Ching-Tien Ho, and Jyh-Jong Tsay Towards Practical Permutation Routing on Meshes Michael Kaufmann, Uli Meyer, and Jop F. Sibeyn Efficient Submesh Permutations in Wormhole-Routed Meshes Ching-Tien Ho and Ming-Yang Kao 5:00 - 6:00 p.m.: BREAK 6:00 - 9:00 p.m.: CONFERENCE RECEPTION (Hors d'oeuvres and Cash Bar) Thursday, October 27, 1994 8:30 am - 5:00 pm - Workshop 2: "Concurrent Object-Based Systems" Organized by Lonnie Welch (NJIT, USA) and Dieter K. Hammer (Eindhoven Univ. of Technology, The Netherlands). 8:30 - 10:00 am Session A-4: Algorithms I Sorting Large Data Sets on a Massively Parallel System Ralf Diekmann, Jorn Gehring, Reinhard Luling, Burkhard Monien, Markus Nubel and Rolf Wanka A Low-Latency Scalable Locking Algorithm for Shared Memory Multiprocessors Amitabh Dave, Nayeem Islam and Roy Campbell A Hybrid Approach for Mutual Exclusion in Distributed Computing Systems Anup Kumar Session B-4: Performance Evaluation Performance Predictions on Implicit Communication Systems Xiaodong Zhang, Zhichen Xu and Lin Sun Performance of SPEC92 on Prime-Mapped Vector Cache Tong Sun and Qing Yang Performance Model for a Prioritized Multiple-Bus Multiprocessor System Lizy Kurian and Yu-cheng Liu Session C-4: Distributed Models Inevitable Global States: A Concept to Detect Unstable Properties of Distributed Computations in an Observer Independent Way Eddy Fromentin and Michel Raynal Causality versus Time: How to Specify and Verify Distributed Algorithms Vivjay K. Garg and Alexander I. Tomlinson Synchronization Expressions and Languages L. Guo, K. Salomaa and S. Yu 10:00 - 10:30 am: BREAK 10:30 - 12:00 noon Session A-5: Routing II Minimal Turn Restrictions for Designing Deadlock-Free Adaptive Routing Chiu-Chuan Lin and Ferng-Ching Lin Hierarchical Adaptive Routing: A Framework for Fully Adaptive and Deadlock-Free Wormhole Routing Ziqiang Liu and Andrew A. Chien Wormhold Routing Algorithms for Twisted Cube Networks Paul Cull and Shawn M. Larson Session B-5: Parallel Models Good Algorithm Design Style for Multiprocessors Xiaotie Deng and Nian Gu C3 : An Architecture-Independent Model for Coarse-Grained Parallel Machines Susanne E. Hambrusch and Ashfaq A. Khokhar Computational Bounds for the Simple and the MRMW PRAM Fabrizio Luccio and Linda Pagli Session C-5: Network Algorithms II Parallelism and Locality in Priority Queues A. Ranade, S. Cheng, E. Deprit, J. Jones and S. Shih Upper and Lower Bounds for Selection on the Mesh Lata Narayanan and Anne Condon Optimal Hypercube Algorithm for the All-Nearest Smaller Values Problem Dina Kravets and C. Greg Plaxton 12:00 - 1:30 pm: LUNCH 1:30 - 3:00 pm Session A-6: Parallel Algorithms Very Fast Optimal Parallel Algorithms for Heap Construction P. F. Dietz and R. Raman The Efficiency of Randomized Parallel Backtrack Search Yanjun Zhang and Augustyn Ortynski On the Convergence of a Parallel Algorithm for Finding Polynomial Zeroes Flaminia L. Luccio Session B-6: Distributed Algorithms Optimal Multiple Message Broadcasting in Telephone-Like Communication Systems A. Bar-Noy, S. Kipnis, and B. Schieber Optimal Polling in Communication Networks Adele A. Rescigno Election on Faulty Rings with Incomplete Size Information Gary L. Peterson and Byungho Yi Session C-6: Applications III Distributed Image Edge Detection Methods and Performance Xiaodong Zhang and H. Deng Improving Parallel Execution Performance for Logic Programs Using Mode Information Jeffrey J. P. Tsai and Bing Li An analysis of Data Distribution Methods for Gaussian Elimination in Distributed-Memory Multicomputers Ben Lee 3:00 - 3:30 pm: BREAK 3:30 - 5:00 pm Session A-7: Message Passing Systems A Practical Communication Cost Formula for Users of Message Passig Systems Andrew P. Wack Exploiting Duplication to Minimize the Execution Times of Parallel Programs on Message-Passing Systems Yu-Kwok Kwak and Ishfaq Ahmad A Comparison fo Techniques Used for Mapping Parallel Algorithms to Message-Passing Multicomputers MariosD. Dikaiakos, Anne Rogers, and Ken Steiglitz Session B-7: Architecture A Class of Scalable Architectures for High-Performance, Cost- Effective Parallel Computing Sotirios G. Ziavras Efficient Mapping of Randomly Sparse Neural Networks on Parallel Vector Supercomputers Silvia M. Muller and Benedict Gomes Derivation and Performance of a Pipelined Transaction Processor Andrew J. Bennett, Paul H. J. Kelly and Ross A. Patterson Session C-7: Distributed Systems I On-the-Fly Replay: A Practical Paradigm and Its Implementation for Distributed Debugging O. Gerstel, Shmuel Zaks, M. Hurfin, N. Plouzeau and M. Raynal Embedding Rings in Recursive Networks Roland Fernandes, Donald Friesen, and Arkady Kanevsky DTVS: A Distributed Trace Visualization System Dennis Edwards and John P. Kearns Friday, October 28, 1994 8:30 - 10:00 am Session A-8: Algorithms II Coarse-Grain Parallel Genetic Algorithms: Categorization and New Approach Shyh-Chang Lin, W. F. Punch III, and E. D. Goodman An Efficient Dynamic Processor Allocation Algorithm for Adaptive Mesh Applications Ravi Varadarajan and Injae Hwang A Performance Comparison of Processor Allocation and Job Scheduling Algorithms for Mesh-Connected Multiprocessors Davender Babbar and Phillip Krueger Session B-8: Interconnection Networks II A New Family of Fixed Degree Cayley Networks for Multiprocessor Design Premkumar Vadapalli and Pradip K. Srimani Pin-Efficient Networks for Cubic Neighborhoods Charles M. Fiduccia and Kevin J. Rappoport Necklaces and Scalability of Kautz Diagraphs Pavel Turdik Session C-8: Fault Tolerant Systems Maximal Global Snapshot with Concurrent Initiators Mukesh Singhal and Ravi Prakash A Divide-and-Conquer Methodology for System-Level Diagnosis of Processor Arrays Chao Feng. L. N. Bhuyan, and F. Lombardi Combining Replication and Purity Approaches for Fault-Tolerant Disk Arrays Chung-Sheng Li, Ming-Syan Chen, Philip S. Yu, and Hui-L. Hsiao 10:00 - 10:30 am: BREAK 10:30 - 12:00 noon Session A-9: Potpourri II Modelling Accesses to Migratory and Producer-Consumer Characterized Data in a Shared Memory Multiprocessor Mats Brorsson and Per Stenstrom A Performance Analysis for Two-Dimensional Disk Array J.-C. Lee, C.-S. Lee, T.-M. Parng, C.-N. Tsai and S. Huang Session B-9: Routing III On the Role of K-Bits Bitonic Sorting Network in Multicast Routing Majad Z. Al-Hajery and Kenneth E. Batcher Routing with Locality in Partitioned-Bus Meshes Steven Cheung and Francis C. M. Lau On Multicast Wormhole Routing in Multicomputer Networks Rajendra V. Boppana, Suresh Chalasani, and C. S. Raghavendra Session C-9: Distributed Systems II Distributed Token Management in Calypso File System Ajay Mohindra and Murthy Devarakonda Characterization of Applications with I/O for Processor Scheduling in Multiprogrammed Parallel Systems S. Majumdar and Yiu Ming Leung Sharing Networked Workstations: A Performance Model Gregory D. Peterson and Roger D. Chamberlain 12:00 - 2:00 pm: CONFERENCE LUNCHEON and KEYNOTE SPEECH Steve Wallach - Convex Corp. "Teraflop Computing and Beyond" 1:30 - 3:00 pm Session A-10: Applications II A Scalable Sharing Architecture for a Parallel Database System Vibby Gottemukkala, Edward Omiecinski, and Umakishore Ramachandran Application-Specific Array Processors for Binary Prefix Sum Computation Rong Lin and S. Olariu Out-of-Order Access to Vector Elements in Order to Reduce Conflicts in Vector Processors Anna M. del Corral and J. M. Llaberia Session B-10: Network Algorithms I The Reconfigurable Ring of Processors: Fine-Grained Tree- Structured Computations Arnold L. Rosenberg, Vittorio Scarano, and Ramesh K. Sitaraman On Balancing Computational Load on Rings of Processors Lixin Gao and Arnold L. Rosenberg The Red-Blue Algorithm for Dynamic Programming on Linear Arrays Kevin J. Rappoport Saturday, October 29, 1994 8:30 am - 5:00 pm Tutorial T1: Intoduction to Parallel Computing by V. Kumar - University of Minnesota The tutorial will provide an overview of parallel architectures (SIMD/MIMD, shared versus distributed memory, interconnection networks, embeddings), routing (store-and-forward versus wormhole routing), examples of some currently available parallel computers, basic communication operations (1-to-all broadcast, all- to-all broadcast, scan, synchronization), basic metrics for performance evaluation (speedup, efficiency, isoefficiency), matrix algorithms (matrix-vector products, matrix-matrix multiplication), sorting, graph problems, and parallel programming paradigms. This tutorial would be useful for anyone interested in solving problems on parallel computers. Tutorial T2: Distributed and Object Oriented Database Systems by R. Elmasri and A. Helal - University of Texas at Arlington The distributed nature of corporate database and information systems, and the demand for increasing their availability and performance have created a great demand for the development of distributed database systems. Such systems support distributed transactions and other database operations on a variety of database objects. This tutorial will cover the main concepts of distributed database design and implementation, and the fundamentals of object-oriented databases. The purpose of the tutorial will be to provide a quick and basic background on distributed and object- oriented database developments and technology. Database developers will benefit the most from this tutorial. Tutorial T3: Distributed Shared Memory: Concepts and Systems by J. Protic, M. Tomasevic and V. Milutinovic - IFACT This tutorial covers topics that include: - Introduction to DSM (Distributed Shared Memory) concepts and algorithms - Classification criteria in the field - Relevant classification parameters - DSM algorithms - DSM implementations on the hardware level - DSM implementations on the software level - DSM hybrid approach - DSM implementation in heterogeneous systems - Evaluation of the DSM coherence schemes End of the document Article 52843 of comp.arch: Newsgroups: comp.arch Path: cantaloupe.srv.cs.cmu.edu!das-news.harvard.edu!news2.near.net!MathWorks.Com!panix!zip.eecs.umich.edu!newsxfer.itd.umich.edu!gatech!howland.reston.ans.net!cs.utexas.edu!news.uta.edu!cse.uta.edu!hbchen From: hbchen@cse.uta.edu (Hsing B Chen) Subject: Advanced program- SPDP 1994 Message-ID: <1994Sep9.164052.11409@news.uta.edu> Sender: news@news.uta.edu (USENET News System) Nntp-Posting-Host: cse.uta.edu Organization: Computer Science Engineering at the University of Texas at Arlington Date: Fri, 9 Sep 1994 16:40:52 GMT Lines: 544 ************************************************** SIXTH IEEE SYMPOSIUM ON PARALLEL AND DISTRIBUTED PROCESSING Registration form and Advance Program ************************************************** *********************************************************** Sixth IEEE Symposium on Parallel and Distributed Processing Registration form *********************************************************** Sponsors: IEEE-CS TC for Computer Architecture, TC for Distributed Computing, and IEEE-CS-Dallas Chapter Bristol Suites Hotel, Dallas, Texas October 26-29, 1994 Technical program, to be held October 26-28, features: - Keynote Speech 1: "Parallel & Distributed Computing: Competitors or Partners?", David Kuck (UIUC, USA), October 26, 1994. - Keynote Speech 2: "Teraflop Computing and Beyond", Steve Wallach (Convex Corp., USA), October 28, 1994. - Workshop 1: "Parallel and Super Computing in Mexico" Organized by Jose Luis Figueroa (Supercomputing Center, ITESM, Mexico) and S. Lakshmivarahan (Univ. of Oklahoma, USA), October 26, 1994. - Workshop 2: "Concurrent Object-Based Systems" Organized by Lonnie Welch (NJIT, USA) and Dieter K. Hammer (Eindhoven Univ. of Technology, The Netherlands), October 27, 1994. Full-day Tutorials (October 29): T1: Introduction to Parallel Computing, V. Kumar, University of Minnesota, USA. T2: Distributed and Object Oriented Database Systems, R. Elmasri and A. Helal, University of Texas at Arlington, USA. T3: Distributed Shared Memory: Concepts and Systems, J.Protic, M. Tomasevic and V. Milutinovic, IFACT, USA. ------------------------------------------------------------------------------ Hotel Reservations: Please place your reservations directly with Bristol Suites Hotel at 7800 Alpha Road, Dallas, Texas 75240, USA, Tel: (214) 233-7600, Fax: (214) 701-8618. You must mention that you are attending IEEE SPDP in order to receive the special symposium rate of $95/night for a single and $100/night for a double room. These rates include a complimentary full breakfast in the hotel's Cafe Biarritz. Please check with the reservations' desk for the applicability of other special rates, such as those available to AAA members. Reservations should be made before October 4, 1994. After this date, reservations are subject to space availability. Directions: Bristol Suites Hotel, the conference site, is located in North Dallas on the northwest corner of LBJ Freeway (635) and Coit Road. The hotel is about 25 minutes from the Dallas/Fort Worth (DFW) International Airport. By Car: Take DFW Int'l Airport north exit. Take LBJ Freeway (635) East towards Dallas, go approximately 18 miles, take Coit Road North Exit. Alpha Road is the first street crossing Coit north of the LBJ Freeway; take a left on Alpha. The hotel will be to your left. Shuttle Service: Super Shuttle provides van service from DFW Int'l Airport to the Bristol Suites for $12.00 per person each way. For more information and reservations, call (817) 329-2002. Once you arrive at the airport, go to the baggage claim area and using a free "Share-Ride" phone, dial 02 to inform Super Shuttle of your arrival. Weather: Dallas weather in late October ranges from mid 60's to high 70's Fahrenheit. ---------------------------------------------------------------------------- - Please send the completed registration form (below), along with your payment to the Registration Chair: Dr. Lonnie Welch, Dept. of Computer and Information Science, New Jersey Institute of Technology, University Heights, Newark, NJ 07102 USA, phone: (201) 596-5683, fax: (201) 596-5777, email: elch@vienna.njit.edu. PLEASE MAKE CHECKS PAYABLE TO "SPDP". - The symposium registration includes the attendance at the workshops and the symposium proceedings, banquet, and luncheon. Student registration does not include the luncheon. Advance Registration: Before October 4, 1994 Symposium Tutorial Advance On-site Advance On-site IEEE Mem. US$265 US$315 US$225 US$270 Non-Mem. US$330 US$395 US$280 US$335 Full-time Students US$180 US$225 US$225 US$270 IEEE Member:____ Non-Member:____ Student:____ IEEE/Student No.:______________________ Symposium: $_______ Tutorial: $_______ Specify choice of tutorial(s): T____ Total: $_______ _____Check enclosed, USA BANKS ONLY (payable to SPDP) ____Credit Card (VISA or Master Card ONLY) VISA___ or Master Card___ Credit Card No.:________________________________ Expiration Date:____________ Signature:_____________________________ Last Name:__________________________________ First Name:___________________________ Middle Initial:_____ Organization: _____________________________________________________ Address: _____________________________________________________ _______________________________________________ City, State, Zip/Country:_________________________________________ Phone: ___________________ Fax: ____________________ E-mail:___________________________________________ -------------------------------------------------------------------------- *********************************************************** Sixth IEEE Symposium on Parallel and Distributed Processing Advance Program *********************************************************** Wednesday, October 26, 1994 7:30 - 8:30 am On-site Registration - Conference Material Available at the Registration Desk 8:30 - 10:00 am Opening Session and Keynote Speech David Kuck - UIUC "Parallel & Distributed Computing: Competitors or Partners?" 10:00 - 10:30 am: BREAK 10:30 am - 5:00 pm- Workshop 1: "Parallel and Super Computing in Mexico" Organized by Jose Luis Figueroa (Supercomputing Center, ITESM, Mexico) and S. Lakshmivarahan (Univ. of Oklahoma, USA). 10:30 - 12:00 noon Session A-1:Potpourri I Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time Frank Dehne, Claire Kenyon and Andreas Fabri On the Design and Implementation of Broadcast and Global Combine Operations Using the Postal Model J. Bruck, L. de Coster, N. Dewulf, C.-T. Ho, and R. Lauwereins Embedding of Cycles in Rotator and Incomplete Rotator Graphs Subburajan Ponnuswany and Vipin Chaudhary Session B-1: Communications Optimal Fault Tolerant Communication Algorithms on Product Networks Using Spanning Trees Sabine R. Ohring and Dirk H. Hohndel Synchronization and Communication in Algorithmic Structures Mario J. Gonzalez and Linda F. Wilson Eager Combining: A Coherency Protocol for Increasing Effective Network and Memory Bandwidth in Shared-Memory Multiprocessors Ricardo Bianchini and Thomas J. LeBlanc Session C-1: Interconnection Networks I Simultaneous Access Renegable Priority Queues P. R. Venkata Subramaniam and Kam-Hoi Cheng Conflict-Free Data Access of Arrays and Trees in Parallel Memory Systems Sajal K. Das and Falguni Sarkar WICI: An Efficient Switching Scheme for Large Scalable Networks Hyunmin Park and Dharma P. Agrawal 12:00 - 1:30 pm: LUNCH 1:30 - 3:00 pm Session A-2: Real-Time Distributed Systems Timing Analysis of Real-Time Distributed Systems in CRSMs and ERL Yaodong Bi Assignment and Pre-Run-Time Scheduling of Object-Based, Parallel Real-Time Processes J. P. C. Verhoosel, D. K. Hammer, E. J. Luit, and Lonnie R. Welch Performability Analysis of Non-Repairable Multicomponent Systems Using Order Statistics Amiya Bhattacharya, Ramesh R. Rao, and Ting-Ting Y. Lin Session B-2: Applications I An Adaptive SOR Algorithm and Its Parallel Implementation for Power System Applications G. M. Huang and W. Ongsakul An Analysis of Parallel Synchronous and Conser- vative Asynchronous Logic Simulation Schemes William T. Baker and Ausif Mahmood Parallel Bidirectional Heuristic Search on the EM-4 Multiprocessor Andrew Sohn and Mitsuhisa Sato, S. Sakai, Y. Kodama, and Y. Yamaguchi Session C-2: Distributed Systems III Dynamic Load Balancing on a Distributed System M. D. Feng and C. K. Yuen Virtual Computers -- A New Paradigm for Distributed Operating Systems Banu Ozden, Aaron J. Goldberg and Avi Silberschatz Write Grouping for Update-Based Cache Coherence Protocols D. B. Glasco, B. A. Delagi, and M. J. Flynn 3:00 - 3:30 pm: BREAK 3:30 - 5:00 pm Session A-3: Multistage Interconnection Networks Star-Graph Based Multistage Interconnection Network for ATM Switch Fabric C. P. Ravikumar and G. Manimaran Multicast in Extra-Stage Multistage Interconnection Networks Chi-Ming Chiang and Sourav Bhattacharya, and Lionel M. Ni Bounds on the Number of Passes in Multistage Interconnection Networks Yshovardhan R. Potapalli and Dharma P. Agrawal Session B-3: Algorithms III Software Interleaving Ricardo Bianchini, Mark E. Crovella, L. Kontothanassis, and Thomas J. LeBlanc Program Dependence Analysis for Concurrency Exploitation in Programs Composed of Abstract Data Type Modules Guohui Yu and Lonnie R. Welch Minimum Dependence Distance Tiling of Nested Loops with Non- Uniform Dependences Swamy Punyamurtula and Vipin Chaudhary Session C-3: Routing I Matrix Transpose on Meshes with Wormhole and XY Routing Kuo-Shun Ding, Ching-Tien Ho, and Jyh-Jong Tsay Towards Practical Permutation Routing on Meshes Michael Kaufmann, Uli Meyer, and Jop F. Sibeyn Efficient Submesh Permutations in Wormhole-Routed Meshes Ching-Tien Ho and Ming-Yang Kao 5:00 - 6:00 p.m.: BREAK 6:00 - 9:00 p.m.: CONFERENCE RECEPTION (Hors d'oeuvres and Cash Bar) Thursday, October 27, 1994 8:30 am - 5:00 pm - Workshop 2: "Concurrent Object-Based Systems" Organized by Lonnie Welch (NJIT, USA) and Dieter K. Hammer (Eindhoven Univ. of Technology, The Netherlands). 8:30 - 10:00 am Session A-4: Algorithms I Sorting Large Data Sets on a Massively Parallel System Ralf Diekmann, Jorn Gehring, Reinhard Luling, Burkhard Monien, Markus Nubel and Rolf Wanka A Low-Latency Scalable Locking Algorithm for Shared Memory Multiprocessors Amitabh Dave, Nayeem Islam and Roy Campbell A Hybrid Approach for Mutual Exclusion in Distributed Computing Systems Anup Kumar Session B-4: Performance Evaluation Performance Predictions on Implicit Communication Systems Xiaodong Zhang, Zhichen Xu and Lin Sun Performance of SPEC92 on Prime-Mapped Vector Cache Tong Sun and Qing Yang Performance Model for a Prioritized Multiple-Bus Multiprocessor System Lizy Kurian and Yu-cheng Liu Session C-4: Distributed Models Inevitable Global States: A Concept to Detect Unstable Properties of Distributed Computations in an Observer Independent Way Eddy Fromentin and Michel Raynal Causality versus Time: How to Specify and Verify Distributed Algorithms Vivjay K. Garg and Alexander I. Tomlinson Synchronization Expressions and Languages L. Guo, K. Salomaa and S. Yu 10:00 - 10:30 am: BREAK 10:30 - 12:00 noon Session A-5: Routing II Minimal Turn Restrictions for Designing Deadlock-Free Adaptive Routing Chiu-Chuan Lin and Ferng-Ching Lin Hierarchical Adaptive Routing: A Framework for Fully Adaptive and Deadlock-Free Wormhole Routing Ziqiang Liu and Andrew A. Chien Wormhold Routing Algorithms for Twisted Cube Networks Paul Cull and Shawn M. Larson Session B-5: Parallel Models Good Algorithm Design Style for Multiprocessors Xiaotie Deng and Nian Gu C3 : An Architecture-Independent Model for Coarse-Grained Parallel Machines Susanne E. Hambrusch and Ashfaq A. Khokhar Computational Bounds for the Simple and the MRMW PRAM Fabrizio Luccio and Linda Pagli Session C-5: Network Algorithms II Parallelism and Locality in Priority Queues A. Ranade, S. Cheng, E. Deprit, J. Jones and S. Shih Upper and Lower Bounds for Selection on the Mesh Lata Narayanan and Anne Condon Optimal Hypercube Algorithm for the All-Nearest Smaller Values Problem Dina Kravets and C. Greg Plaxton 12:00 - 1:30 pm: LUNCH 1:30 - 3:00 pm Session A-6: Parallel Algorithms Very Fast Optimal Parallel Algorithms for Heap Construction P. F. Dietz and R. Raman The Efficiency of Randomized Parallel Backtrack Search Yanjun Zhang and Augustyn Ortynski On the Convergence of a Parallel Algorithm for Finding Polynomial Zeroes Flaminia L. Luccio Session B-6: Distributed Algorithms Optimal Multiple Message Broadcasting in Telephone-Like Communication Systems A. Bar-Noy, S. Kipnis, and B. Schieber Optimal Polling in Communication Networks Adele A. Rescigno Election on Faulty Rings with Incomplete Size Information Gary L. Peterson and Byungho Yi Session C-6: Applications III Distributed Image Edge Detection Methods and Performance Xiaodong Zhang and H. Deng Improving Parallel Execution Performance for Logic Programs Using Mode Information Jeffrey J. P. Tsai and Bing Li An analysis of Data Distribution Methods for Gaussian Elimination in Distributed-Memory Multicomputers Ben Lee 3:00 - 3:30 pm: BREAK 3:30 - 5:00 pm Session A-7: Message Passing Systems A Practical Communication Cost Formula for Users of Message Passig Systems Andrew P. Wack Exploiting Duplication to Minimize the Execution Times of Parallel Programs on Message-Passing Systems Yu-Kwok Kwak and Ishfaq Ahmad A Comparison fo Techniques Used for Mapping Parallel Algorithms to Message-Passing Multicomputers MariosD. Dikaiakos, Anne Rogers, and Ken Steiglitz Session B-7: Architecture A Class of Scalable Architectures for High-Performance, Cost- Effective Parallel Computing Sotirios G. Ziavras Efficient Mapping of Randomly Sparse Neural Networks on Parallel Vector Supercomputers Silvia M. Muller and Benedict Gomes Derivation and Performance of a Pipelined Transaction Processor Andrew J. Bennett, Paul H. J. Kelly and Ross A. Patterson Session C-7: Distributed Systems I On-the-Fly Replay: A Practical Paradigm and Its Implementation for Distributed Debugging O. Gerstel, Shmuel Zaks, M. Hurfin, N. Plouzeau and M. Raynal Embedding Rings in Recursive Networks Roland Fernandes, Donald Friesen, and Arkady Kanevsky DTVS: A Distributed Trace Visualization System Dennis Edwards and John P. Kearns Friday, October 28, 1994 8:30 - 10:00 am Session A-8: Algorithms II Coarse-Grain Parallel Genetic Algorithms: Categorization and New Approach Shyh-Chang Lin, W. F. Punch III, and E. D. Goodman An Efficient Dynamic Processor Allocation Algorithm for Adaptive Mesh Applications Ravi Varadarajan and Injae Hwang A Performance Comparison of Processor Allocation and Job Scheduling Algorithms for Mesh-Connected Multiprocessors Davender Babbar and Phillip Krueger Session B-8: Interconnection Networks II A New Family of Fixed Degree Cayley Networks for Multiprocessor Design Premkumar Vadapalli and Pradip K. Srimani Pin-Efficient Networks for Cubic Neighborhoods Charles M. Fiduccia and Kevin J. Rappoport Necklaces and Scalability of Kautz Diagraphs Pavel Turdik Session C-8: Fault Tolerant Systems Maximal Global Snapshot with Concurrent Initiators Mukesh Singhal and Ravi Prakash A Divide-and-Conquer Methodology for System-Level Diagnosis of Processor Arrays Chao Feng. L. N. Bhuyan, and F. Lombardi Combining Replication and Purity Approaches for Fault-Tolerant Disk Arrays Chung-Sheng Li, Ming-Syan Chen, Philip S. Yu, and Hui-L. Hsiao 10:00 - 10:30 am: BREAK 10:30 - 12:00 noon Session A-9: Potpourri II Modelling Accesses to Migratory and Producer-Consumer Characterized Data in a Shared Memory Multiprocessor Mats Brorsson and Per Stenstrom A Performance Analysis for Two-Dimensional Disk Array J.-C. Lee, C.-S. Lee, T.-M. Parng, C.-N. Tsai and S. Huang Session B-9: Routing III On the Role of K-Bits Bitonic Sorting Network in Multicast Routing Majad Z. Al-Hajery and Kenneth E. Batcher Routing with Locality in Partitioned-Bus Meshes Steven Cheung and Francis C. M. Lau On Multicast Wormhole Routing in Multicomputer Networks Rajendra V. Boppana, Suresh Chalasani, and C. S. Raghavendra Session C-9: Distributed Systems II Distributed Token Management in Calypso File System Ajay Mohindra and Murthy Devarakonda Characterization of Applications with I/O for Processor Scheduling in Multiprogrammed Parallel Systems S. Majumdar and Yiu Ming Leung Sharing Networked Workstations: A Performance Model Gregory D. Peterson and Roger D. Chamberlain 12:00 - 2:00 pm: CONFERENCE LUNCHEON and KEYNOTE SPEECH Steve Wallach - Convex Corp. "Teraflop Computing and Beyond" 1:30 - 3:00 pm Session A-10: Applications II A Scalable Sharing Architecture for a Parallel Database System Vibby Gottemukkala, Edward Omiecinski, and Umakishore Ramachandran Application-Specific Array Processors for Binary Prefix Sum Computation Rong Lin and S. Olariu Out-of-Order Access to Vector Elements in Order to Reduce Conflicts in Vector Processors Anna M. del Corral and J. M. Llaberia Session B-10: Network Algorithms I The Reconfigurable Ring of Processors: Fine-Grained Tree- Structured Computations Arnold L. Rosenberg, Vittorio Scarano, and Ramesh K. Sitaraman On Balancing Computational Load on Rings of Processors Lixin Gao and Arnold L. Rosenberg The Red-Blue Algorithm for Dynamic Programming on Linear Arrays Kevin J. Rappoport Saturday, October 29, 1994 8:30 am - 5:00 pm Tutorial T1: Intoduction to Parallel Computing by V. Kumar - University of Minnesota The tutorial will provide an overview of parallel architectures (SIMD/MIMD, shared versus distributed memory, interconnection networks, embeddings), routing (store-and-forward versus wormhole routing), examples of some currently available parallel computers, basic communication operations (1-to-all broadcast, all- to-all broadcast, scan, synchronization), basic metrics for performance evaluation (speedup, efficiency, isoefficiency), matrix algorithms (matrix-vector products, matrix-matrix multiplication), sorting, graph problems, and parallel programming paradigms. This tutorial would be useful for anyone interested in solving problems on parallel computers. Tutorial T2: Distributed and Object Oriented Database Systems by R. Elmasri and A. Helal - University of Texas at Arlington The distributed nature of corporate database and information systems, and the demand for increasing their availability and performance have created a great demand for the development of distributed database systems. Such systems support distributed transactions and other database operations on a variety of database objects. This tutorial will cover the main concepts of distributed database design and implementation, and the fundamentals of object-oriented databases. The purpose of the tutorial will be to provide a quick and basic background on distributed and object- oriented database developments and technology. Database developers will benefit the most from this tutorial. Tutorial T3: Distributed Shared Memory: Concepts and Systems by J. Protic, M. Tomasevic and V. Milutinovic - IFACT This tutorial covers topics that include: - Introduction to DSM (Distributed Shared Memory) concepts and algorithms - Classification criteria in the field - Relevant classification parameters - DSM algorithms - DSM implementations on the hardware level - DSM implementations on the software level - DSM hybrid approach - DSM implementation in heterogeneous systems - Evaluation of the DSM coherence schemes End of the document