Eighth International Conference On Parallel And Distributed Computing Systems September 21-23 1995 Orlando, Florida USA Sponsored by The International Society for Computers and Their Applications (ISCA) in cooperation with The IEEE Computer Society - Technical Committee on Simulation ------------------------------------------------------------------- PRELIMINARY PROGRAM ------------------------------------------------------------------- THURSDAY, Sept. 21, 1995 7:00 a.m. - Registration 8:00 a.m. - 8:30 a.m. Welcome and Opening Remarks 8:30 a.m. - 9:30 a.m. Plenary Address: TBA 9:30 - 10:00 Break TECHNICAL SESSIONS Session T1A: Fault Tolerance I Thursday, Sept. 21, 10:00 a.m. - 11:40 a.m. 1. Monitoring Membership Changes in a Fault-Tolerant Distributed System Louise E. Moser (Univ. of California, Santa Barbara ) [113] 2. Modeling and Analysis of a Fault-Tolerant Remote Procedure Call Mansoor Alam (Univ. of Toledo ) [126] 3. Fault Free Embeddings in a Faulty 2-d Torus Ramakumar Kosuru (Univ. of Wisconsin-Milwaukee) [127] Session T1B: Algorithms I Thursday, Sept. 21, 10: 00 a.m. - 11:40 a.m. 1. An Optimal Load Sharing Strategy for Divisible Jobs with Time-Varying Processor Speed Thomas G. Robertazzi (SUNY at Stony Brook) [107] 2. A Model and an Algorithm of Subsystem Construction Z. P. Tao (Univ. de Montreal) [130] 3. New Convex Hull Algorithms on Linear Arrays Doris L. Carver (Louisiana State Univ.) [141] 4. Using Fuzzy Logic for Task Scheduling in Multiprocessor Systems Albert Y. Zomaya [148] 5. A Genetic Algorithm Based Approach for Generalization of Min-Cut Partitioning to Tree Structures Anup Kumar (Univ. of Louisville) [219] Session T1C: Distributed Computing Thursday, Sept. 21, 10: 00 a.m. - 11:40 a.m. 1. Enhanced Gradient Model: A Dynamic-Threshold Based Load Balancing Model for Applicative Multiprocessor System Tai M. Chung (Purdue Univ.) [115] 2. On the Design and the Proof of Correctness of a Distributed Lock Protocol Mukund M. Buddhikot (Univ. of Texas at Austin) [117] 3. An Extended A* Model for Task Allocation in Distributed Computer Systems Lar Dunning (Bowling Green State Univ. ) [163] 4. Dynamics of Distributed Transaction Processing: Load Sharing versus Locality Preference Edward A. Billard (Univ. of Aizu) [206] 5. Efficient Recovery Policies in Client-Server Systems Shalini Yajnik (AT&T Bell Laboratories) [208] 11:45a.m. - 1:00 p.m. LUNCH Session T2A: Real Time Thursday, Sept. 21, 1:00 p.m. - 2:40 p.m. 1. Veritable Time Representation for Clock Synchronization in Distributed Computer Systems Cyril U. Orji (Florida International Univ.) [210] 2. An End-to-End Transmission Protocol in ATM Networks for Real-Time Applications Yu Gong (Auburn Univ.) [212] 3. Selectively Fault-Tolerant, Hard Real-Time Multiprocessor Scheduling Edwin Hsing-Mean Sha (Univ. of Notre Dame) [227] 4. Optimal Multicast Routing with Real-time Constraint in ATM Networks Xiaohua Jia (City Univ. of Hong Kong) [246] Session T2B: Languages Thursday, Sept. 21, 1:00 p.m. - 2:40 p.m. 1. Optimum Pipeline Scheduling ... Howard Sholl (Univ. of Connecticut) [109] 2. Improving WHILE Loo Dynamic Scheduling in Shared Memory Parallel Computers Hesham El-Rewini (Univ. of Nebraska at Omaha) [142] 3. Array Data Layout for the Reduction of Cache Conflicts in Loop Nests Tarek Abdelrahman (Univ. of Toronto) [143] 4. A Unified Scheme for Partitioning and Clustering of Iteration Space of Nested Loops for Execution on Multiprocessors Safiullah Faizullah (KFUPM) [202] Session T2C: Concurrency & Parallelism Thursday, Sept. 21, 1:00 p.m. - 2:40 p.m. 1. A New System for Evaluation of Parallel Algorithym Performance Nevin M. Darwish (Cairo Univ.) [138] 2. Parallel Algorithm for Switching Function Minimization Ahmed E. Barbour (Georgia Southern Univ.) [211] 3. Incremental Exploitation of Parallelism in Prolog Gopal Gupta (New Mexico State Univ.) [216] 4. Application Specific Communication Scheduling on Parallel Systems Edwin Hsing-Mean Sha (Univ. of Notre Dame) [228] 5. A Parallel VLSI-Implementable Thinning Algorithm Dr. Zhang and Dr. Mahgoub (Florida Atlantic Univ.) [254-S] 2:40 p.m. - 3:00 p.m. BREAK Session T3A: Performance I Thursday, Sept. 21, 3:00 p.m. - 5:05 p.m. 1. An Evaluation of Load Balancing Algorithms through Simulation C. Bala Kumar (Motorola Inc.) [101] 2. Performance Modeling and Analysis of Correlated Parallel Computations Wei-Ming Lin (Univ. of Texas at San Antonio) [106] 3. Analytic Performance Model for Future Bus+ Systems Ulrich Stern (Stanford Univ.) [151] 4. An Approximation Procedure of Multi-layered Semaphore Queue with Coxian Arrivals and Exponential Service Times Paul Luh (National ChengChi Univ.) [203] 5. Quantitative Performance Evaluation of a Distributed Hardware Barrier Synchronization Protocol Mukund M. Buddhikot (Univ. of Texas at Austin) [229] 6. Performance Measurements of Automatic Prefetching Randy Appleton (Univ. of Kentucky) [237] Session T3B: Networks I Thursday, Sept. 21, 3:00 p.m. - 5:05 p.m. 1. Efficient Perfectly Secure Message Transmission in Synchronous Networks Hosame Abu-Amara (Texas A&M Univ.) [104] 2. Asynchronous Agreement and Leader Election for General Networks with Byzantine Faulty Links Hosame Abu-Amara (Texas A&M Univ.) [112] 3. Packet Switched Multistage Interconnection Networks with Multiple Packet Movement Per Network Cycle Hee Yong Youn (Univ. of Texas at Arlington) [121] 4. Hypernetworks: A Class of Interconnection Networks for new Generation Parallel Computers S. Q. Zheng (Louisiana State Univ.) [133] 5. Black Holes, Sacrificial Lambs, and a Robust Approach to Transaction Routing Donald Ferguson (IBM T. J. Watson Research Center)[135] 6. Traffic Analysis and Characterization of a Local Area Network with Different Classes of Users Abdelsalam A. Helal (Univ. of Texas at Arlington) [214] Session T3C: Architecture I Thursday, Sept. 21, 3:00 p.m. - 5:05 p.m. 1. A New Shared Memory Concept for Multiprocessor Systems with High-Speed Communication Links Eugen Brenner (Tech. Univ. Graz) [218] 2. Strategies for Processor Allocation in k-ary N-cubes Vipin Chaudhary (Wayne Univ.) [220] 3. Termination Detection on Hypercubes Frederic Drouhin (Lab.d'Informatique de Besancon) [224] 4. Optimal Clustering of Three-Level Coma Multiprocessors Based on the Modified MVA Model Fadi Sibai (Univ. of Akron) [144] 5. Unallocated Memory Space in COMA Multiprocessors Sujat Jamil (Univ. of Minn.) [233] 6. A Case Study of Parallel Hierarchical Radiosity Algorithms on a DM-COMA Architecture Cipin Chaudhary (Wayne St. Univ.) [242] 7:30 p.m. - 9:00 p.m. RECEPTION FRIDAY, Sept. 22, 1995 8:00 a.m. - Registration 8:30 a.m. - 9:30 a.m. Plenary Address: TBA 9:30 a.m. - 10:00 a.m. BREAK Session F1A: Operating Systems Friday, Sept. 22, 10:00 a.m. - 11:40 a.m. 1. Predicting Results of Programs for Meeting Timing Constraints and Overcoming Communication Delays Hasan Cam (KFUPM) [155] 2. Operating System Design Principles for Scalable Shared Memory Multiprocessors Mukherjee, Rajat (IBM T. J. Watson Research Center) [161] 3. Multithreaded Multiprocessor System G. Chaudhry (Univ. of Missouri-Columbia) [167] 4. Effects of Job Interactions Due to Scattered Processor Allocations in 2-D Wormhole Networks Matt W Mutka (Michigan St. Univ) [231] Session F1B: Reliability Friday, Sept. 22, 10:00 a.m. - 11:40 a.m. 1. The Subcube Reliability of a Modular Fault-Tolerant Hypercube Architecture Mostafa Abd-El-Barr (KFUPM) [129] 2. Fault-Tolerance and Reliability Analysis of Multi-Stage Data Manipulator Networks Khalid Al-Tawil (KFUPM) [154] 3. Parallel Reasoning in Model-Based Fault Diagnosis Ralph F. Grove (Indiana Univ. Southeast) [205] 4. An Efficient Method for Computing Submesh Reliability in Two-Dimensional Meshes Prasant Mohapatra (Iowa St. Univ.) [223] 5. Reliability Analysis of Large-Scale Ring-Based Hierarchical Networks Mohammad Al-Rousan (Brigham Young Univ.) [245] Session F1C: Networks II Friday, Sept. 22, 10:00 a.m. - 11:40 a.m. 1. On News of Personal Info... Howard Sholl (Univ. of Connecticut) [139] 2. A Network-based Model for Application-oriented Communication Protocols Salim Hariri (Syracuse University) [149] 3. A Scalable Multi-buffer ATM Switch Architecture Paul Shipley (Univ. of SW Louisiana ) [160] 4. The Implementation of Quorum Consensus Protocol Mei-Ling Liu (Cal Poly State Univ.) [207] 5. Scalable Locking in a Clustered Multiprocessor Protocol Mukund M. Buddhikot (Univ. of Texas at Austin) [251] 11:45 a.m. - 1:00 p.m. CONFERENCE LUNCHEON Session F2A: Parallel and Distributed Simulations Friday, Sept. 22, 1:00 P.m. - 2:40 p.m. Session Chair: Chaudhry 1. Performance Evaluation of VAX and Sun SPARC versus 80X86 D. Kaur, D. Shaheen and Yong G. Park (Univ. of Toledo) [401] 2. Multiple Bus-Based Hierarchical Multiprocessors and Their Bandwide Analysis Syed Masud Mahmud and L. Tissa Samaratunga (Wayne St. Univ.) [402] 3. Performance of Processor-Memory-Oriented-Partial- Multiple-Bus System G. M. Chaudhry and A. N. Khan (Univ. of Missouri- Columbia) [403] 4. Distributed Processing Techniques for Generation of Dertouzos Tables Jason Sodergren, Harpreet Singh and E. Yaprak (Wayne St. Univ.) [404] 5. An Efficient Algorithm for Computation of Reliability in Distributed Networks Nabil A. Hachem (Lawrence Tech. Univ.) and J. S. Bedi (Wayne St. Univ.) [405] Session F2B: Applications Friday, Sept. 22, 1:00 P.m. - 2:40 p.m. Session Chair: Nadia Hegazi 1. A Middleware for Distributed Multimedia Applications Michael Weiss (MITEL Corp.) [125] 2. Remote Control with Remote Procedure Calls Gerhard Eschelbeck (Univ. Linz) [234] 3. A High-Performance Arabic Character Recognition System Jasir Alherbish (Univ. of Connecticut) [244] 4. A New Parallel Heuristic for the Quadratic Assignment Problem Nishit Kumar (Univ. of Central Florida) [236] 5. Memory-based Parsing in Natural Language Using Semantic Networks Nadia Hegazi (Electronics Research Institute) [253] Session F2C: Algorithms II Friday, Sept. 22, 1:00 P.m. - 2:40 p.m. 1. Leaf Communications in Trees and Fat Trees Nikitas J. Dimopoulos (Univ. of Victoria) [137] 2. Locating Congruent and Similar Regions in a Planar Graph by a Mesh of Trees Fenglien Lee (Winston-Salem State Univ.) [213] 3. Distributed Systems Task Allocation: A Genetic Algorithm Perspective Khaled A. Kamel (Univ. of Louisville) [215] 4. Graph Based Allocation Scheme for Directed Process Graphs onto Multiprocessors Rammohan K. Ragade (Univ of Louisville) [226] 5. A Hybrid Dynamic Load Sharing Algorithm for Improving the Performance of Distributed Systems Anil Rao (Univ. of Connecticut) [243] 2:40 p.m. - 3:00 p.m. BREAK Session F3A: Math. Algorithms and Software Friday, Sept. 22, 3:00 p.m. - 5:05 p.m. Session Chair: D. Fausett 1. Parallel Computation of Large Least Squares problems Involving Kronecker Products on the Connection Machine 5 Charles T. Fulton and Limin Wu (Florida Inst. of Technology) [301] 2. The Use of Parallel Virtual Machines in Air Traffic Control John H. George, Jan Collins, David Ross, Eddie Bugg, and Howard Abrams (Embry-Riddle Aeronautical Univ.) [302] 3. Parallel Solution of Two Point Boundary Value Problems Using Collocation on a Hypercube Laurene V. Fausett (Florida Inst. of Tech.) [303] 4. Massive Parallel Computation for Large-Scale Nonlinear Models in Fluid Dynamics Suhrit K. Dey (Eastern Illinois Univ.) [304] 5. Some Methods for Direct Reduction to a Near-Tridiagonal Form Gary W. Howell (Florida Inst. of Tech.) [305] 6. Matrix Transpositin Algorithm on a Distributed Memory Parallel Computer Hany Hashish and Donald W. Fausett (Florida Inst. of Tech.) [306] Session F3B: Architectures II (Hyprcube) Friday, Sept. 22, 3:00 p.m. - 5:05 p.m. Session Chair: Mahgoub 1. Incomplete Crossed Hypercubes Yan-Qing Zhang (Univ. of S. Florida) [103] 2. Processor Allocation in Hypercube Multicomputers: The Random Allocation Strategy Debendra Das Sharma (Hewlett-Packard) [134] 3. Performance of an ATM-based Hypercube Brian Mackay (Univ. of Connecticut) [140] 4. Hypercube Hypernetworks: Implementation sof Hypercube with Increased Wire Sharing S. Q. Zheng (Louisiana State Univ.) [147] 5. The Associat SIMD Hypercube Magdy Bayoumi (Univ. of SW Louisiana) [159] 6. A Processor Allocation Scheme for Hypercube Computers Based on a Novel Approach Dr. ahgoub (Florida Atlantic Univ.) [255] Session F3C: PADS Friday, Sept. 22, 3:00 p.m. - 5:05 p.m. 1. An Improved Chandy-Lamport Snapshot Algorith for Global Virtual Time Approximation in Distributed Simulations Hussam M. Soliman and Adel S. Elmaghraby (Univ. of Louisvile) [150] 2. Performance Study of a Parallel-Event Simulator Hussam M. Soliman and Adel S. Elmaghraby (Univ. of Louisville) [153] 3. An Electrostatic Particle-in-cell (PIC) Simulation on INTEL Paragon Armagan Ozkaya (George Washington Univ.) [158] 4. Simulating Particle Travel with Lattice Computers John Case (Univ. of Delaware) [164] 5. Improving Performance of the Qualitative Simulator QSIM - Design and Implementation of a Specialized Computer Architecture Bernhard Rinner (Tech. Univ. Graz) [222] 6. The Modeling and Simulation of Complex Distributed Networks with the Department of Defense James Sidoran (USAF) [249] SATURDAY, Sept.23, 1995 Session S1A: Fault Tolerance II Saturday, Sept. 23, 8:00 a.m. - 9:30 a.m. 1. On Fault-Tolerant Ring Embedding in DeBruijn and Kautz Graphs Arunabha Sen (Arizona State Univ.) [128] 2. A Framework for Fault-Tolerant Distributed Mutual Exclusion and Replica Control Using Grid Structure Jehn-Ruey Jiang (National Tsing Hua University) [146] 3. CRAFT: CRiticAlity basded Fault Tolerance for real- time distributed systems with resource constraints Niraj K. Jha (Princeton Univ.) [201] 4. Enhanced Fibonacci Cubes Jie Wu (Florida Atlantic University) [235] Session S1B: Software Environments Saturday, Sept. 23, 8:00 a.m. - 9:30 a.m. 1. An Overview of the CHIP3S Performance Prediction Toolset for Parallel Systems E. Papaefstathiou (Univ. of Warwick) [119] 2. Priority: An I/O Instrumentation, Measurement, and Analysis Tool Steven VanderLeest (Univ. of Illinois) [132] 3. UTE: A Unified Trace Environment for IBM SP Systems C. Eric Wu (IBM T. J. Watson Res. Center) [221] Session S1C: Database Saturday, Sept. 23, 8:00 a.m. - 9:30 a.m. 1. A Heuristic Algorithm for Beneficial Semijoins Ye-In Chang (National Sun Yat-Sen Univ.) [118] 2. Two-Phase Commit in Gigabit-Networked Distributed Databases Panos K. Chrysanthis (Univ. of Pittsburgh) [123] 3. A Methodology for the Design of Distributed Object Oriented Databases Kokou Yetongnon (Univ. de Bourgogne) [136] 4. On the Use of Artificial Intelligence for Distributed Database Design Lena Sham (Hong Kong Polytechnic Univ.) [232] 9:30 a.m. - 10: 00 a.m. BREAK Session S2A: Architecture III Saturday, Sept. 23, 10:00 a.m. - 11:40 a.m. 1. Resource Placement in Cube-Connecticed-Cycles Networks Yuanyuan Yang (Univ. of Vermont) [102] 2. An Optimal Bound on the Gain of Using One Large Processor Cluster instead of a Number of Small Clusters Lars Lundberg (Univ. of Karlskrona/Ronneby) [108] 3. Process Mapping in a Multiprocessor System by Means of a Hardware Monitor R. Ginthor-Kalcsics (Graz. Univ of Tech.) [110] 4. CAM-8: A Virtual Processor Cellular Automata Machine N. Margolus (Massachusetts Institute of Technology ) [166] 5. A Class of Cache Coherence Schemes with Cache-Based Directories Imad Mahgoub (Florida Atlantic Univ.) [217] Session S2B: Algorithms III Saturday, Sept. 23, 10:00 a.m. - 11:40 a.m. 1. Optimal Scheduling of a Class of Parallel Algorithms Jie Wu (Florida Atlantic University) [116] 2. Parallel Algorithms for Fully Dynamic Maintenance of Extremal Sets in 0(logN) Time Using CREW Processors Hong Shen (Griffith Univ.) [152] 3. Performance of an Adaptive Algorithm for Dynamic Load Balancing Gregory S. Wolffe (Univ. of Wisconsin-Milwaukee) [209] 4. Past Parallel Tree Search with Static Load-Balancing Forward Checking Technique Wei-Ming Lin (Univ. of Texas - San Antonio) [230] Session S2C: Concurrency and Parallelism II Saturday, Sept. 23, 10:00 a.m. - 11:40 a.m. 1. A Data-Redundant Systolic Algorithm for Transitive Closure on Linear Arrays Kevin J. Rapport (Pacific-Sierra Research) [111] 2. Parallelism Detection Algorithm for Extended Sisal Programs in Centaur Jean-Luc Gaudiot (Univ. of Southern California) [204] 3. An Approximatin Algorithm for Scheduling Independent Parallel Tasks and Its Analysis Kequi Li (SUNY at New Paltz) [145] Ms. Mary Ann Sullivan Executive Director International Society for Computers Phone: (919) 847-3747 and Their Applications (ISCA) Fax: (919) 676-0666 8820 Six Forks Road E-mail: mas@isca.pdial.interpath.net Raleigh, NC 27615-2969