23rd International Conference on Parallel Processing Aug. 15-19, 1994 Conference at a Glance ************************************************************************| | Monday | |-----------------------------------------------------------------------| 9:15 | Tutorials 1 & 2 | |-----------------------------------------------------------------------| 5:00 | Registration | |-----------------------------------------------------------------------| 7:00 | Award Session | |-----------------------------------------------------------------------| 7:30 | Panel 1: Parallel Task Scheduling | | Ted Lewis, Naval Postgraduate School |-----------------------------------------------------------------------| 9:00 | Beer Bibblers' Party | ************************************************************************| ************************************************************************| | Tuesday | |-----------------------------------------------------------------------| 8:15 | Registration | | | |-----------------------------------------------------------------------| | | A | B | C | |-----------------------------------------------------------------------|-9:15 | 1 | Interconnection | Compilers-I | Parallel | | | Networks - I | | Algorithms | |------------------------------------------- ---------------------------|-10:45 | Coffee Break | |-----------------------------------------------------------------------|-11:00 | 2 | Static Networks | Scheduling-I | Applications | | | | | | |-----------------------------------------------------------------------|-12:30 | Lunch and Keynote Speech: The next 50 years of Parallel Processing | | Michael J. Flynn, Stanford University. | |-----------------------------------------------------------------------|-2:30 | 3 | Hierarchical | Environment & | Numerical | | | Networks | Synchronization | Methods | |-----------------------------------------------------------------------|-4:00 | Coffee Break | |-----------------------------------------------------------------------|-4:30 | 4 | Novel Architectures | Monitoring | Task Assignment | | | | | | |-----------------------------------------------------------------------|-6:00 | Dinner | |-----------------------------------------------------------------------|-7:30 | Panel 2: Sea of Interconnection Networks: What's your choice? | | Lionel M. Ni, Michigan State University. | |-----------------------------------------------------------------------|-9:00 | Wine and Cheese Party | |-----------------------------------------------------------------------| ************************************************************************* ************************************************************************* | Wednesday | |-----------------------------------------------------------------------| | | A | B | C | |-----------------------------------------------------------------------|-8:30 | 5 | Interconnection | Compilers-II | Distributed | | | Networks-II | | Algorithms | |-----------------------------------------------------------------------|-10:00 | Coffee Break | |-----------------------------------------------------------------------|-10:30 | 6 | Wormhole Routing | Scheduling-II | Simulation/ | | | | | Synthesis | |-----------------------------------------------------------------------|-12:00 | Lunch and Keynote Speech: Computational Science and Engineering: | | an interdisciplinary field | | Ahmed Sameh, University of Minnesota | |-----------------------------------------------------------------------|-2:00 | 7 | Cache-I | Migration & | Protocol/Routing | | | | Performance | | |-----------------------------------------------------------------------|-3:30 | Coffee Break | |-----------------------------------------------------------------------|-4:00 | 8 | Communication Issues | Potpourri | Performance | |-----------------------------------------------------------------------|-5:30 | Dinner | |-----------------------------------------------------------------------|-7:30 | Panel 3: Parallel I/O: How do we achieve it? | | Daniel A. Reed, University of Illinois, Urbana. | |-----------------------------------------------------------------------|-9:00 | Coctail Party | |-----------------------------------------------------------------------| ************************************************************************* ************************************************************************* | Thursday | |-----------------------------------------------------------------------| | | A | B | C | |-----------------------------------------------------------------------|-8:30 | 9 | Memory Systems | Compilers-III | Graph Problems | |-----------------------------------------------------------------------|-10:00 | Coffee Break | |-----------------------------------------------------------------------|-10:30 | 10 | VLSI Based | Scheduling-III | Database | | | Architecture | | Applications | |-----------------------------------------------------------------------|-12:00 | Lunch and Keynote Speech: Scalable Parallel Systems and | | Workstation Clusters: Synergy or Conflict? | | Marc Snir, IBM TJ Watson Research Center. | |-----------------------------------------------------------------------|-2:00 | 11 | Cache-II | Efficient Execution | Discrete Methods | |-----------------------------------------------------------------------|-3:30 | Coffee Break | |-----------------------------------------------------------------------|-4:00 | 12 | Multithreading | Performance Issues | Numerical | | | | | Applications | |-----------------------------------------------------------------------|-5:30 | Dinner | |-----------------------------------------------------------------------|-7:30 | Visit to Argonne National Lab (Tentative) | |-----------------------------------------------------------------------|-9:00 ************************************************************************* | Friday August 19: Tutorials 3 & 4 |-8:30 *************************************************************************4:30 PRECONFERENCE TUTORIALS TUTORIAL 1: INTRODUCTION TO PARALLEL COMPUTING Instructor: Mary M. Eshaghian Audience: Computer scientists/engineers interested in an introduction to the theory and design of parallel architectures and algorithms. Course Description: In the first part, various models of parallel computations are introduced. In part 2 parallel memory organizations are presented. Pipelining, vector processing, and systolic arrays are discussed in part 3. Part 4 contains a detailed overview of various SIMD topologies and efficient techniques for design and mapping of SIMD algorithms. Several interconnection networks are introduced in part 5. In the last part, advanced topics in parallel processing are discussed. Mary M. Eshaghian is the director of the Advanced Computer Architecture and Parallel Processing Lab at New Jersey Institute of Technology. She received her Ph.D. in Computer Engineering from the University of Southern California, in 1988. TUTORIAL 2: Parallel Algorithm Design Instructor: H. J. Siegel Audience: Computer scientists or engineers who are interested in the use of large-scale parallel processing systems. Course Description: A variety of techniques for mapping tasks onto large- scale parallel machines are explained and demonstrated with algorithm case studies. Issues addressed include data distribution, scalability, network topology influence, SIMD (synchronous) vs. MIMD (asynchronous) vs. mixed-mode parallelism, trading off computation time vs. communication time, partitioning for subtask parallelism, overlapping the operation of the SIMD control unit and its processors, and the difficulty of automatic parallelization of serial algorithms. H. J. Siegel is a Professor of Electrical Engineering at Purdue. He is an IEEE Fellow, was a Coeditor-in-Chief of J. Parallel and Distributed Computing, and is an Editor of IEEE Transactions on Parallel and Distributed Systems. POSTCONFERENCE TUTORIALS TUTORIAL 3: Multigranular Computing Instructor: Umakishore Ramachandran Audience: Industry/university types involved in the research and development of parallel architectures and software tools for parallel machines. Course Description: This tutorial will cover the granularity spectrum -- >from fine-grained to coarse-grained -- of parallel computation. The topics to be covered include architectural examples from discrete points in this granularity spectrum; analysis of application domains to identify types of parallelism; determining the match between applications and architectures; performance metrics; and case studies drawn from reconfigurable architectures to networked parallel computers of different granularities. Umakishore Ramachandran received his doctorate from the University of Wisconsin-Madison in 1986, and has been on the faculty at the Georgia Institute of Technology since then. He received NSF's Presidential Young Investigator Award in 1990. TUTORIAL 4: Parallel Arch. & Numerical Algorithms Instructor: Ramesh K. Agarwal Audience: Scientists, engineers, and technical managers who are interested in parallel architectures, parallel algorithms for the solution of partial differential equations, and implementation of large scale scientific applications on parallel machines. Course Description: The course will review the multiprocessor architectures including the recent potentially teraflop architectures such as T3D, SP2, Paragon, KSR2, CM5, etc. and their programming environment. The parallel algorithms for the solution of elliptic, parabolic, and hyperbolic equations will be presented. The crucial interplay of numerical algorithms and system software in fully exploiting these architectures will be discussed. Selected benchmarks of large scale problems from linear algebra and matrix theory, and computational physics will be presented. Ramesh K. Agarwal is a McDonnell Douglas Fellow at McDonnell Douglas Aerospace Corporation in St. Louis. He is also an Affiliate Professor at Washington University in St. Louis. He has published widely in parallel computing. ************************************************************************* Details of the Conference Program Session 1A: Interconnection Networks (I) Chair : C.S. Raghavendra (R): Multistage Interconnection Networks with Multiple Outlets T. Hanawa, H. Amano, and Y. Fujikawa (C): A High Throughput Packet-Switching Network with Neural Network Controlled Bypass Queueing and Multiplexing Y.-K. Park and G. Lee (C): Performance Analysis of Combining in Multistage Interconnection Networks P. Mohapatra, S. Wong, and C.R. Das (C): A General Inside-Out Routing Algorithm for a Class of Rearrangeable Networks S.-W. Seo and T.-y. Feng (C): Strategies for the Massively Parallel Simulation of Interconnection Networks M. Jurczyk, T. Schwederski, R. Born, H.J. Siegel, and S. Abraham Session 2A: Static Networks Chair : A. Youssef (R): Performance and Reliability of the Multistage Bus Network L.N. Bhuyan, A.K. Nanda, and T. Askar (C): Theory of Generalized Branch and Combine Clock Networks A. El-Amawy and P. Kulasinghe (C): Continuum : A Hybrid Time/Space Communications Paradigm for k-ary n-cubes A.C. Flavell and Y. Takahashi (C): Analysis of Interconnection Networks based on Cayley Graphs of Strong Generating Sets J.-p. Huang, S. Lakshmivarahan, and S.K. Dhall (C): A Comparative Study of Star Graphs and Rotator Graphs S. Ponnuswamy and V. Chaudhary Session 3A: Hierarchical Networks Chair : R.C. Joshi (R): Efficient Routing and Broadcasting in Recursive Interconnection Networks R. Fernandes, D.K. Friesen, and A. Kanevsky (C): A Class of Static and Dynamic Hierarchical Interconnection Networks P.T. Breznay and M.A. Lopez (C): Designing Large Hierarchical Multiprocessor Systems under Processor, Interconnection and Packaging Advancements D. Basak and D. K. Panda (C): Comparison of Mesh and Hierarchical Networks for Multiprocessors V.C. Hamacher and H. Jiang (C): Computational Properties of Mesh Connected Trees: Versatile Architectures for Parallel Computation K. Efe and A. Fernandez Session 4A: Novel Architectures Chair : W.E. Alexander (R): EXECUBE - A New Architecture for Scalable MPPs P.M. Kogge (R): Programming with Functional Memory R. Halverson Jr. and A. Lew (C): Dynamic Barrier Architecture for Multi-Mode Fine Grain Parallelism Using Conventional Processors W.E. Cohen, H.G. Dietz, and J.B. Sponaugle (C): Design and Evaluation of a Multiprocessor Architecture with Decentralized Control C. Wu, H. Chung, J. Rakes, P. J. Zievers, and Y. Lin Session 5A: Interconnection Networks (II) Chair : C.R. Das (R): Nonblocking Operation of Asymmetrical Clos Networks F. K. Liotopoulos and S. Chalasani (C): An Extended Bidirectional Tag Scheme and Its Tree Representation on A Shuffle-Exchange Network T. Feng and Y. Kim (C): On the Rearrangability of Reverse Shuffle/Exchange Networks B. Park and K. Watson (C): SNAIL : A Multiprocessor Based on the Simple Serial Synchronized Multistage Interconnection Network Architecture M. Sasahara, J. Terada, L. Zhou, K. Gaye, J. Yamamoto, S. Ogura, and H. Amano (C): Sorting Multiple Bitonic Sequences D. Lee and K. E. Batcher Session 6A: Wormhole Routing Chair : H.J. Siegel (R): Sequencing of Concurrent Communication Traffic in a Mesh Multicomputer with Virtual Channels B.-r. Tsai and K.G. Shin (R): Optimal Multicast Communication in a Wormhole-Routed Torus Networks D.F. Robinson, P.K. McKinley, and B.H.C. Cheng (R): A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks J. Duato Session 7A: Cache (I) Chair : J. Baer (R): A Distributed Cache Coherence Protocol for Hypercube Multiprocessors Y. Chang, L.N. Bhuyan, and A. Kumar (R): An Integrated Methodology for the Verification of Directory-Based Cache Protocols F. Pong, P. Stenstrom, and M. Dubois (R): Reducing the Write Traffic for a Hybrid Cache Protocol F. Dahlgren and P. Stenstrom Session 8A: Communication Issues Chair : K. Batcher (R): Latency Analysis of CC-NUMA and CC-COMA Ring Multiprocessors X. Zhang and Y. Yan (C): Compiling Functional Parallelism on a Family of Different Communication Cost Architectures S. Pande and K. Psarris (C): Deadlock Free Asynchronous Communication Strategies for Unstructured Computations on iPSC/860 S. Venugopal and V.K. Naik (C): A Comparative Performance Study of an Interconnection Cached Network V. Gupta and E. Schenfeld (C): Hybrid Multiprocessing in "OPTIMUL" : A Multiprocessor For Distributed and Shared Memory Multiprocessing with WDM Optical Fiber Interconnections K. Ghose, R.K. Horsell, and N. Singhvi Session 9A: Memory Systems Chair : M.S. Yousif (R): A Shared Memory Environment for Hypercubes A. Agarwala and C.R. Das (C): Optimizing IPC Performance for Shared-Memory Multiprocessors B. Gamsa, O. Krieger and M. Stumm (R): Module Partitioning and Interlaced Data Placement Schemes to Reduce Conflicts in Interleaved Memories L. Kurian, B. Choi, P.T. Hulina and L.D. Coraor (C): PSIM: Periodically Shifted Interleaved Memory System J. Y. Lee and H. Y. Youn Session 10A : VLSI Based Architecture Chair : A. Dahbura (R) : An Efficient VSLI Architecture for Template Matching N. Ranganathan and S. Venugopal (C) : Block Data Processing using Commercial Processors K.N. Ellis and W.E. Alexander (C) : Rank Ordering Filtering on an Array With Faulty Processors J. Salinas and F. Lombardi (C) : Parallel Image Correlation : A Case Study to Examine SIMD/MIMD Trade-offs for Scalable Parallel Algorithms J.B. Armstrong, M.A. Nichols, H.J. Siegel, and K.H. Casey (C) : Fault-Tolerant Routing Algorithms for a Massively Parallel Machine C. Aktouf, C. Robach, and G. Mazare Session 11A : Cache (II) Chair : L.N. Bhuyan (R) : A One's Complement Cache Memory Q. Yang and S. Adina (C) : Can High Bandwidth and Latency Justify Big Cache Blocks in Scalable Multiprocessors R. Bianchini and T.J. LeBlanc (C) : Compiler Optimization Technique for Data Cache Prefetching Using a Small CAM Array C.H. Chi (C) : Degenerate Sharing R. L. Hyde and B. D. Fleisch (C) : Error Recovery in Parallel Systems of Pipelined Pipelined Processors with Caches J.P. Lin, S.C. Wang, and S.Y. Kuo Session 12A : Multithreading/VLIW Chair : C.L. Wu (R) : Performance of Switch Blocking on Multithreaded Architectures K. Gopinath, Krishna Narasimhan M.K., B.H. Lim, and A. Agarwal (R) : An Analytical Approach to Scheduling Code for Superscalar and VLIW Architectures S.K. Chen, W.K. Fuchs, and W.M.W. Hwu (C) : Performance Issues of a Superscalar Microprocessor S. Wallace and N. Bagherzadeh (C) : Partitioning of Variables for Multiple-Register-File VLIW Architectures A. Capitanio, N. Dutt, and A. Nicolau ------------------------------------------------------------------- Session 1B: Compilers (I) Chair : D. Padua (R): Communication Optimizations for Distributed Memory Multicomputers used in the PARADIGM Compiler D. J. Palermo, E. Su, J. Chandy, and P. Banerjee (R): Parallel Region Execution of Loops with Irregular Dependencies A. Zaafrani, and M.R. Ito (C): Valid Transformations: A New Class of Loop Transformations M. Rim, and R. Jain (C): Statement Re-ordering for DOACROSS Loops D.K. Chen, and P.C. Yew Session 2B: Scheduling (I) Chair : T. Casavant (R): On-Line Hard Real-Time Scheduling of Parallel Tasks on Partitionable Multiprocessors D. Babbar and P. Krueger (R): Self-Adjusting Scheduling: An On-Line Optimization Technique for Locality Management and Load Balancing B. Hamidzadeh, and D. Lilja (C): A New Approach to Scheduling Parallel Programs Using Task Duplication I. Ahmad, and K.Y. Kwong (C): A Task Duplication Based Optimal Scheduling Algorithm For Variable Execution Time Tasks S. Darbha, and D.P. Agrawal Session 3B: Environment and Synchronization Chair : M. Spezialetti (R): Distributed Memo: A Heterogeneous Parallel and Distributed Software Programming Environment W.T. O'Connell, G.K. Thiruvathukal, and T.W. Christopher (C): Banger: A Large-Grain Parallel Programming Environment for Non-Programmers T. Lewis (C): Definitions and Detection of Deadlock, Livelock, and Starvation in Concurrent Programs K.C. Tai (C): On the fly testing of reular patterns in distributed computations E. Fromentin, and M. Raynal (C): An Efficient Solution To The Critical Section Problem In Distributed Systems K. Makki, and E.K. Park Session 4B: Monitoring Chair : J. Wileden (R): Perturbation Analysis: A Static Analysis Approach for the Non-Intrusive Monitoring of Distributed Programs R. Gupta, and M. Spezialetti (R): Cachier: A Tool for Automatically Inserting CICO Annotations T. Chilimbi, and J.R. Larus (C): Trace Recovery in Multi-Processing Systems: Architectural Considerations J.A. Gannon, K.J. Williams, M.S. Andersland, T.L. Casavant, and J.E. Lumpp (C): Parallel Program Trace Extrapolation Z.K.F. Eckert, and G.J. Nutt Session 5B: Compilers (II) Chair : R. Eigenmann (R): Undoing Code Transformations in an Independent Order C.R. Dow, M.L. Soffa,and S.K. Chang (R): A Convex Programming Approach for Exploiting Data and Functional Parallelism on Distributed Memory Multicomputers S. Ramaswamy, S. Sapatnekar, and P. Banerjee (C): Statement Merge: an Inter-Statement Optimization of Array Language Programs D.C. Ju, C.L. Wu, and P. Carini (C): Full Parallelism in Uniform Nested Loops using Multi-Dimensional Retiming N.L. Passos, and E.H.M. Sha Session 6B: Scheduling (II) Chair : C. McCreary (R): Subcube Level Time-Sharing in Hypercube Multicomputers D.D. Sharma, G.D. Holland, and D.K. Pradhan (R): Limit Allocation: An Efficient Processor Management Scheme for Hypercubes C. Yu, and C.R. Das (C): A bottom up approach to Task Scheduling in Distributed Memory Multiprocessors N. Mehdiratta, and K. Ghose (C): A Static Scheduling Algorithm using Dynamic Critical Path for Assigning Parallel Algorithms onto Multiprocessors K.Y. Kwong, and I. Ahmad Session 7B: Migration and Performance Chair : J. Fang (R): Dynamic Task Migration from SPMD to SIMD Virtual Machines J.B. Armstrong, H.J. Siegel, W. Cohen, M. Tan, H. Dietz, and J.A.B. Fortes (C): Efficient Task Migration for Message Driven Parallel Execution on Nonshared Memory Architectures N. Doulas, and B. Ramkumar (C): Impact of Loop Granularity and Self-Preemtion on the Performance of Loop Parallel Applications on a Multiprogrammed Shared-Memory Multiprocessor C. Natarajan, S. Sharma, and R. Iyer (C): Experimental Validation of Stochastic Performance Models of General Layered Task Systems A.B. Tayyab, and J.G. Kuhl (C): A Performance Debugger for a Language Supporting Data Distribution Primitives G. Hurteau, A. Singh, M. Hancu, V.V. Dongen, and H. Hum Session 8B: Potpourri Chair : D. Hislop (C): A Closed-Form Formula for Queueing Delays in Disk Arrays T. Yang, S. Hu, and Q. Yang (C): Dynamic Parity Grouping for Improving Write Performance of RAID-5 Disk Arrays P.S. Yu, K.-L. Wu, and A. Dan (C): A General Framework for Synthesis of Data Format Converters J. Bae and V.K. Prasanna (C): Scientific Computing Using pPVM K. Maly, S. Kelkar and M. Zubair (C): An Optimistic Recovery Scheme for Message-Passing Multicomputer Systems P. Krishna, N.H. Vaidya, and D.K. Pradhan (C): New Systolic Arrays for Matrix Multiplication S.-G. Chen, J.-C. Lee, and C.-C. Li Session 9B: Compilers (III) Chair : M.R. Ito (R): A Framework for Data Dependence Testing in the Presence of Pointers J. Hummel, L.J. Hendren, and A. Nicolau (R): Optimizing Offset Alignment for Data Parallel Programs H. Xu and L.M. Ni (C): Symbolic Analysis Techniques Needed for the Effective Parallelization of the Perfect Benchmarks W. Blume, and R. Eigenmann (C): Compilation of a Functional Language for the Multithreaded Architecture: DAVRID E. Rho, S. Ha, H. Kim, D. Hwang, and S. Han Session 10B: Scheduling (III) Chair : H. Dietz (R): A Comparison of Multiprocessor Scheduling Heuristics A.A. Khan, C.L. McCreary, and M.S. Jones (R): Job Scheduling in Mesh Multicomputers D.D. Sharma, and D.K. Pradhan (C): An Empirical Study of the Workload Distribution Under Static Scheduling Z. Li, and T.N. Nguyen (C): Experimental Evaluation of Load Balancing Strategies for Ray Tracing on Parallel Processors T.Y. Lee, C.S. Raghavendra, and J.B. Nicholas Session 11B: Efficient Execution Chair : X. Zhang (R): A Distributed Hardware Mechanism for Process Synchronization on Shared-Bus Multiprocessors D. Johnson, D. Lilja, and J. Riedl (C): Data Prefetching and Data Forwarding in Shared Memory Multiprocessors D.K. Poulsen and P.-C. Yew (C): An Integrated Hardware/Software Data Prefetching Scheme for Shared-Memory Multiprocessors E.H. Gornish and A. Veidenbaum (C): Data Access Mechanisms for a Decoupled Computer Architecture A. Berrached, P.T. Hulina, and L.D. Coraor (C): An Asynchronous Approach to Efficient Execution of Programs on Adaptive Architectures Utilizing FPGAs L. Agarwal, M. Wazlowski, and S. Ghosh Session 12B: Performance Issues Chair : N.F. Tzeng (R): Measuring and Analyzing Parallel Computing Scalability X. Zhang, Y. Yan, and Q. Ma (C): Comparing the Performance of the DASH and Cedar Multiprocessors for Scientific Applications J. Torrellas, D. Koufaty, and D. Padua (C): Evaluation of the Cluster Structure on the PIM/c Parallel Interface Machine T. Tarui, M. Asaie, N. Ido, T. Nakagawa, and M. Sugie (C): A Parallel Trace-driven Simulator: Implementation and Performance X. Qin and J.L. Baer (C): Reconfiguration of Spanning Trees in Faulty Hypercubes K.M. Al-Tawil and D.R. Avresky ------------------------------------------------------------------- Session 1C: Parallel Algorithms Chair : S. Sahni (R): A Memory Constrained Scalability Metric M.A. Fienup and S.C. Kothari (C): Parallel Speculative Computation of Simulated Annealing A. Sohn (C): Speculative Computation: Overcoming Communication Delays V. Govindan and M.A. Franklin (C): A Fast, Partially Parallelizable Algorithm for Predicting Execution Time of EQL Rule-Based Programs J. R. Chen and A.M.K. Cheng (C): Parallel Recursive Computations Where Both Recombination and Partition Overheads are Problem-Dependent A. Saha and M.D. Wagh Session 2C: Applications I Chair : I. Pramanic (R): An Efficient Parallel Algorithm for Vector Quantizer Design J. Lin (C): Efficient Component Labeling on SIMD Mesh Processors W. Yong and M.L. Brady (C): Time-Optimal Multiple Rank Computations on Meshes with Multiple Broadcasting D. Bhagavathi, V. Bokka, H. Gurla, R. Lin, S. Olariu, J.L. Schwing, W. Shen, and L. Wilson (C): Efficient Parallel Computation of Projections for Animated Volume Visualization T. Wu and M.L. Brady (C): A Parallel Approach for Utilizing Contextual Knowledge to Improve Speech Understanding S. Chung and D.I. Moldovan Session 3C: Numerical Methods Chair : P. Wang (R): Parallel Algorithms for the Two-Dimensional Discrete Wavelet Transform D. Krishnaswamy and M. Orchard (R): A Parallel Algorithm for an Inverse Problem Associated with a Hyperbolic System of Partial Differential Equations P. Nelson and M.R. Phillips (C): Practical Issues of 2-D Parallel Finite Element Analysis M. Hribar and V.E. Taylor (C): Derivation of Systolic Programs L. Kazerouni, B. Rajan, and R.K. Shyamsunder Session 4C: Task Assignment Chair : G. Pathak (C): Speedy Task Migration in Hypercube Systems H.-L. Chen and N.-F. Tzeng (C): Schedulability: Real-Time Tasks Scheduling in a Multiprocessor System G.S. Alijani, F. Jafari and C. Wen-Shui (C): Performance Comparison of Two Algorithms for Task Assignment A. Kumar, S. Ramakrishnan, C. Deshpande and L. Dunning (C): Dimension-Exchange-Based Load Balancing on Injured Hypercubes J. Wu (C): An Empirical Study of the I Test for Exact Data Dependence K. Psarris, S. Pande (C): A Framework for Dependence Based Optimization and Parallelization of Practical DO Loops V. Konda and A. Kumar Session 5C: Distributed Algorithms Chair : R.K. Shyamsunder (C): Distributed Digital Logic Simulation on a Network of Workstations S. Sunderam (C): Distributed Approach for Implementing Genetic Algorithms A. Srivastava, A. Kumar, and R.M. Pathak (C): Distributed, Synchronized Implemetation of an Algorithm for the Maximum Flow Problem J.L. Traff (C): Digital Circuit Testing on a Network of Workstations S. Srinivasan and J.H. Aylor (C): A Parallel Solution for the Multiprocessor Document Allocation Problem K. Park, O. Frieder and A. Sood (C): A Concurrent Multi Target Tracker: Benchmarking and Portability S. Hariri, R. Yadav, B. Thiagarajan, S. Park, M. Subramanyam, R. Reddy, and G.C. Fox Session 6C: Synthesis/Simulation Chair : P. Nelson (R): Evaluation of a Local Adaptive Protocol for Distributed Discrete Event Simulation D.O. Hamnes and A. Tripathi (R): Parallel Logic Synthesis Using Partitioning K. De and P. Banerjee (C): Fast Algorithms for Simulating the CRCW Shared-Memory Computer on Reconfigurable Meshes D. Shyu, B. Wang, and C. Tang (C): Efficient CRCW PRAM Emulation on Practical Networks M. Hamdi Session 7C: Protocol/Routing Chair : S. Shukla (R): Strategies for Multicasting in Meshes E. Fleury and P. Fraigniaud (C): A Resource Synchronization Protocol for Multiprocessor Real-Time Systems C.-M. Chen, S.K. Tripathi, and A. Blackmore (C): A Fault-Tolerant Routing Algorithm in Hypercubes Y. Lan (C): Optimal Broadcast in All-Port Wormhole-Routed Hypercubes C.-T. Ho and M.-Y. Kao (C): Path Selection for Communicating Tasks in a Wormhole-Routed Multicomputer S. Lee and J. Kim Session 8C: Performance Chair : M. Hamdi (R): Adaptive Algorithm-Based Fault Tolerance for Parallel Computations in Linear Systems J.I. Khan, W. Linn, and D.Y.Y. Yun (C): Failure Resilient Computations in the EcliPSe System F. Knop, V. Rego, and V. Sunderam (C): A Hierarchical Approach to Modeling and Improving the Performance of Scientific Applications on the KSR1 E.L. Boyd, W. Azeem, H. Lee, T. Shih, S. Hung, and E.S. Davidson (C): Improving the Performance of Global Communication on a 3D torus network Y. Kawakura and S. Oyanagi (C): MPI-F: An Efficient Implementation of MPI on IBM-SP1 H. Franke, P. Hochschild, P. Pattnaik and M. Snir Session 9C: Graph Problems Chair : P. Banerjee (R): Efficient Parallel Algorithms for Geometric Partitioning Problems Through Parallel Range Searching A. Datta (C): Constant Time Convexity Problems on Dense Reconfigurable Meshes V. Bokka, H. Gurla, S. Olariu, and J.L. Schwing (C): Constant Time Graph and Poset Algorithms on the Reconfigurable Multiple Bus Machine J. L. Trahan, R. Vaidyanathan, and C. Subbaraman (C): Computing k-vertex Connectivity on an Interval Graph T. -W. Kao and S.-J. Horng (C): A Unified Approach to Construct Search Trees in Parallel S.K. Das and K.B. Min Session 10C: Database Applications Chair : A. Gahlot (R): Data-Parallel Spatial Join Algorithms E. G. Hoel and H. Samet (R): Message-Task Scheduling in Object-Oriented Heterogeneous GURU Distributed DBMS R.C. Joshi, G.S.D. Varma, K. Singh (C): A Backjumping Search Algorithm for a Distributed Memory Multicomputer J. Conrad and J. Mathew (C): A Modeling Paradigm for Multidatabases S. Damodaran-Kamal, J.M. Francioni, and N. Pissinou Session 11C: Discrete Methods Chair : A. Kumar (R): Triangulating on a Reconfigurable Mesh With Buses M. Nigam and S. Sahni (R): Parallel Graph Constraction with Applications to a Reconfigurable Parallel Architecture Y.-D. Lyuu and E. Schenfeld (C): Sequential and Parallel Algorithms for Partitioning Tree Task Graphs on a Shared Memory Architecture S. Ray and H. Jiang (C): Distributed Algorithms for Constructing a Depth-First-Search Tree S.A.M. Makki and G. Havas Session 12C: Numerical Applications Chair :B. HEnriksen (R): On Solving Block Toeplitz Systems Using a Block Schur Algorithm S. Thirumalai, K. Gallivan, and P. Van Dooren (R): A Parallel Prefix-Like Algorithm for Almost Toeplitz Tridiagonal Systems X. Sun and R.D. Joslin (R): Scheduling Strategies for Sparse Cholesky Factorization on a Shared Virtual Memory Parallel Computer M. Hahad, J. Erhel, and T. Priol ***************************************************************************** REGISTRATION FORM ***************************************************************************** 23rd INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING August 15-19, 1994 Location: Pheasant Run Hotel, St. Charles (West of Chicago), IL 60174 Hotel Phone: (708) 584-6300 The forms below may be duplicated for additional registrations CONFERENCE/TUTORIAL REGISTRATION FORM REGISTRATION FEE--Make your check or money order payable to: INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING for the TOTAL amount indicated below and mail it to: Pheasant Run, P.O. Box 64, St. Charles, Illinois 60174, Attn: Ms. Rebecca Dobbs. *Conference* Advance (till 7-31-1994) Regular $360 Student $200 Late/On Site Regular $400 Student $220 *Tutorials* Tutorial 1: Intro. to Parallel Comp. Advance (till 7-31-94) Regular $250 Student $180 Late/On Site Regular $300 Student $200 Tutorial 2: Parallel Algorithm Design Advance (till 7-31-94) Regular $250 Student $180 Late/On Site Regular $300 Student $200 Tutorial 3: Multigranular Computing Advance (till 7-31-94) Regular $250 Student $180 Late/On Site Regular $300 Student $200 Tutorial 4: Parallel Arch. & Numerical Algorithm Advance (till 7-31-94) Regular $250 Student $180 Late/On Site Regular $300 Student $200 Circle appropriate fees and enter the TOTAL here:__________________ *The Advanced Conference Registration fee includes 3 lunches on August 16 -18, 1994, but Late/On-Site Registration fee does not include any lunches. You may purchase extra lunch tickets in advance for your spouse or friends at $15 per lunch per person. Please specify the number of tickets needed and the dates desired below, then add the amount to the TOTAL above. Please inform us if you prefer vegetarian meals by checking below. Extra lunch tickets: (available with ADVANCED REGISTRATION only),$15 x _____days (check dates desired: Tue.__________Wed.______Thur._________) Check here if you prefer vegetarian meals Yes ** Student registration requires showing ID at the Conference and includes ICPP Proceedings and 3 lunches on August 16-18, 1994. NOTE: REFUND POLICY: Cancellation of registration must be in writing to: T. Feng, 208 Pond Lab., The Pennsylvania State University, University Park, PA 16802, Cancellations must be RECEIVED BY July 31, 1994. No oral/phone cancellations will be accepted. We do not accept company/government vouchers or credit cards. Foreign checks must be withdrawable from a U.S. Bank. *We reserve the right to cancel a tutorial due to insufficient participation or other unforseeable problems. Name_________________________________________________________________ Affiliation__________________________________________________________ Address______________________________________________________________ City/State/Zip Code__________________________________________________ Country______________________________________________________________ Business Phone_______________________________________________________ Home Phone___________________________________________________________ If you wish to be on our ICPP mailing list please write to: T. Feng, 208 Pond Lab., The Pennsylvania State University, University Park, PA 16802. --------------------------------------------------------------------- ------------------------------------------------ *ROOM RESERVATION FORM* ROOM DEPOSIT: One night deposit payable to PHEASANT RUN, P.O. Box 64, St. Charles, Illinois 60174, Attn: Ms. Rebecca Dobbs, for guaranteed reservation. Please fill out the form below: Arrival Date______________________Departure Date_____________________ Number of______________Adults,___________Children,_____________Rooms The room rates are: Standard Room $65/Single $75/Double Deluxe/Tower Room $85/Single $95/Double Bi-level Suite (for family or 3-4 persons) $125/Suite Assignment of rooms will be made according to the date of receipt of the room deposit. REGISTER EARLY TO ASSURE ACCOMMODATIONS. Check in time is 4 P.M. The Pheasant Run will try to accommodate early arrivals. *Room reservation without Conference/Tutorial registration will not be accepted.* --------------------------------------------------------------------- *IMPORTANT NOTICE* We must receive TWO checks: (one payable to the INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING conference/tutorial registration, the other for a one-night deposit payable to PHEASANT RUN for room reservation), in order to guarantee both registration and room reservation. BOTH THE CONFERENCE/TUTORIAL REGISTRATION FORM AND THE ROOM RESERVATION FORM MUST BE RECEIVED BY July 31, 1994. Send BOTH checks to: Pheasant Run P.O. Box 64 St. Charles, IL 60174 Attn: Ms. Rebecca Dobbs CHECKS MUST BE RECEIVED WITH REGISTRATION AND RESERVATION FORMS Registration fees must be paid by check or money order, we regret that we do not accept company/government vouchers or credit cards. Foreign checks must be in U.S. dollar DRAWN ON A U.S. BANK. Neither phone registration nor registrations without payment will be accepted. NOTE: REFUND POLICY: Cancellation of registration must be in writing to: T. Feng, 208 Pond Lab., The Pennsylvania State University, University Park, PA 16802, Cancellations must be RECEIVED BY July 31, 1994. No oral/phone canellations will be accepted. CONFERENCE DETAILS LOCATION Pheasant Run is located in DuPage County, Illinois and is about 25 miles >from O'Hare International Airport and 45-minutes from Chicago's loop. The 500-room resort hotel has various sports and health facilities. TRANSPORTATION Van Transport from Chicago's O'Hare Airport and Midway Airport to the hotel is available through the hotel's Transportation Department. Please contact the hotel Transportation Department 3 days or more prior to your arrival. Without 3 day prior notification your pick- up time will be delayed greatly and additional charges may be incurred. Upon your arrival at the O'Hare Airport or Midway Airport, you should call 1-800-924-7376 and you will be directed to your vehicle. If you have made an advance reservation, our flight will be monitored by the hotel staff and your pickup will be within 30 minutes of your actual landing time. For reservations or further information please call (708) 584-6300 Ext. 7699. You may fax your reservation (3 days or more prior to your arrival) at (708) 584-4693. The rate for transportation between the O'Hare Airport or the Midway Airport and Pheasant Run is $20 per person each way. ADDITIONAL COPIES The three-volume sets of the 1994 ICPP Proceedings may be ordered from : CRC Press, 2000 Corporate Blvd., NW, Boca Raton, FL 33431. Telephone 1-800-272-7737 (all residents except Florida) 1-407-994-0555 (Florida residents) REGISTRATION Pre-registration is mandatory because the limited space is being reserved for Conference participants only. THE REGISTRATION DEADLINE IS July 31, 1994. Register early to assure your accommodation. YOU MUST SEND TWO CHECKS: One for registration for the amount of the conference and/or tutorial, payable to "International Conference on Parallel Processing." See the registration form. One for a guaranteed room reservation, in the amount of one night deposit per room, payable to "Pheasant Run". Please mail both checks to : PHEASANT RUN P.O. Box 64 St. Charles, Illinois 60174 Attn: Ms. Rebecca Dobbs Phone (708) 584-6300. Both the registration fee and the deposit for guaranteed reservations a written cancellation is received on or before July 31, 1994. *(See Important Notice above.)* FURTHER INFORMATION For additional information on the technical contents of the Conference, please contact: Dr. Dharma P. Agrawal (dpa@ncsu.edu) (919) 515-3984, Dept. of Electrical & Computer Engineering 232 Daniels Hall North Carolina State University Raleigh, NC 27695-7911. For information or assistance regarding accommodations or registration, please contact: Ms. Rebecca Dobbs, Pheasant Run, P.O. Box 64, St. Charles, Illinois 60174. Phone (708) 584-6300. Sponsored by The Pennsylvania State University