List of Accepted Papers

Following is the list of accepted papers for the "contributed papers" sessions at IPPS/SPDP 1999. (This does not include the workshops.) The paper number is listed immediately before the title of each paper. Please locate your paper using your browser's "Find" utility. If your name, paper title, or affiliation has been misspelt, please inform us by sending email to To ensure that the correction will be incorporated into the hard copy of the Advance Program, your email should reach us before Dec. 25, 1998.


The Characterization of Data-Accumulating Algorithms
Stefan D. Bruda and Selim G. Akl, Queen's University, Canada


Prefix Computations on Symmetric Multiprocessors
David R. Helman and Joseph Ja'Ja', University of Maryland


Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms
Frank Dehne, Carleton University, Canada, Wolfgang Dittrich, Bosch Telecom, Germany, David Hutchinson and Anil Maheshwari, Carleton University, Canada,


Lower Bounds on the Loading of Degree-2 Multiple Bus Networks for Binary-Tree Algorithms
Hettihe P. Dharmasena and Ramachandran Vaidyanathan, Louisiana State University


A Time-Optimal Solution for the Path Cover Problem on Cographs
K. Nakano, Nagoya Institute of Technology, Japan, S. Olariu, Old Dominion University, A.Y. Zomaya, University of Western Australia, Australia


Parallel Matrix Multiplication on a Linear Array with a Reconfigurable Pipelined Bus System
Keqin Li, State University of New York at New Paltz, Victor Y. Pan, Lehman College, CUNY


Improving Collective I/O Performance Using Threads
Phillip M. Dickens, Illinois Institute of Technology, Rajeev Thakur, Argonne National Laboratory


Linear Aggressive Prefetching: A Way to Increase the Performance of Cooperative Caches
T. Cortes and J. Labarta, Universitat Politecnica de Catalunya, Spain


Hiding Communication Latency in Reconfigurable Message-Passing Environments
Ahmad Afsahi and Nikitas J. Dimopoulos, University of Victoria, Canada


Performance Impact of Memory Hierarchies and Networks on Cluster Computing
Xing Du, University of Virginia, Xiaodong Zhang, College of William and Mary


A Factorial Performance Evaluation for Hierarchical Memory Systems
Xian-He Sun and Dongmei He, Louisiana State University, Kirk W. Cameron, Louisiana State University and Los Alamos National Laboratory, Yong Luo, Los Alamos National Laboratory


A Performance Model of Speculative Prefetching in Distributed Information Systems
N.J. Tuah, M. Kumar, and S. Venkatesh, Curtin University of Technology, Australia


Run-Time Selection of Block Size in Pipelined Parallel Programs
David K. Lowenthal and Michael James, University of Georgia


Reducing Parallel Overheads Through Dynamic Serialization
Michael J. Voss and Rudolf Eigenmann, Purdue University


Using Channels for Multimedia Communication
David May and Henk L. Muller, University of Bristol, United Kingdom


The Paderborn University BSP (PUB) Library -- Design, Implementation and Performance
Olaf Bonorden, University of Paderborn, Germany, Ben Juurlink, Delft Tecnhical University, The Netherlands, Ingo von Otto and Ingo Rieping, University of Paderborn, Germany


A Capabilities Based Communication Model for High-Performance Distributed Applications: The Open HPC++ Approach
Shridhar Diwan and Dennis Gannon, Indiana University


Average-Case Analysis of Isospeed Scalability of Parallel Computations on Multiprocessors
Keqin Li, State University of New York at New Paltz, Xian-He Sun, Louisiana State University


Fully-Scalable Fault-Tolerant Simulations for BSP and CGM
Sung-Ryul Kim and Kunsoo Park, Seoul National University, Korea


Coarse Grained Parallel Maximum Matching in Convex Bipartite Graphs
J. Bose, A. Chan, F. Dehne, and M. Latzel, Carleton University, Canada


Experimental Evaluation of QSM, a Simple Shared-Memory Model
Brian Grayson, Michael Dahlin, and Vijaya Ramachandran, University of Texas at Austin


A Consistent History Link Connectivity Protocol
Paul LeMahieu and Jehoshua Bruck, California Institute of Technology


Performance Evaluation of ServerNet Under Self-Similar Traffic
D.R. Avresky and V. Shurbanov, Boston University, R. Horst, Compaq Tandem Labs


Low Latency Message Passing on Workstation Clusters Using SCRAMNet
Vijay Moorthy, Matthew G. Jacunski, Manoj Pillai, Peter P. Ware, Dhabaleswar K. Panda, Thomas W. Page Jr., and P. Sadayappan, Ohio State University, V. Nagarajan and Johns Daniel, SYSTRAN Corporation


Cashmere-VLM: Remote Memory Paging for Software Distributed Shared Memory
Sandhya Dwarkadas, University of Rochester, Nikolaos Hardavellas, Leonidas Kontothanassis, and Rishiyur Nikhil, Compaq Cambridge Research Lab, Robert Stets, University of Rochester


The Computational Co-op: Gathering Clusters Into a Metacomputer
Walfredo Cirne and Keith Marzullo, University of California at San Diego


Reducing System Overheads in Home-Based Software DSMs
Weiwu Hu, Weisong Shi, and Zhimin Tang, Chinese Academy of Sciences, China


Exploiting Global Structure for Performance on Clusters
Stephen Donaldson and Jonathan M.D. Hill, Oxford University, United Kingdom, David B. Skillicorn, Queen's University, Canada


Implementing Efficient MPI on LAPI for the IBM-SP: Experiences and Performance Evaluation
Mohammad Banikazemi, Ohio State University, Rama K. Govindaraju and Robert Blackmore, IBM, Dhabaleswar K. Panda, Ohio State University


PM-PVM: A Portable Multithreaded PVM
C.M.P. Santos and J.S. Aude, Federal University of Rio de Janeiro, Brazil


tmPVM -- Task Migratable PVM
C.P. Tan, W.F. Wong, and C.K. Yuen, National University of Singapore, Singapore


A Ubiquitous Message Passing Interface: jmpi
Kivanc Dincer, Baskent University, Turkey


On-Demand Multicast Routing Scheme and Its Algorithms
Te-Chou Su and Jia-Shung Wang, National Tsing Hua University, Taiwan


Fault-Tolerant Routing Algorithms for Hypercube Networks
Keiichi Kaneko and Hideo Ito, Chiba University, Japan


Dynamic Interval Routing on Asynchronous Rings
Danny Krizanc, Carleton University, Canada, Flaminia L. Luccio, Universita degli Studi di Milano, Italy, Rajeev Raman, King's College London, United Kingdom


Optimally Scaling Permutation Routing on Reconfigurable Linear Arrays with Optical Buses
Jerry L. Trahan and Anu G. Bourgeois, Louisiana State University, Yi Pan, University of Dayton, Ramachandran Vaidyanathan, Louisiana State University


A Comparison of Router Architectures for Virtual Cut-Through and Wormhole Switching in a NOW Environment
J. Duato, A. Robles, and F. Silla, Universidad Politecnica de Valencia, Spain, R. Beivide, Universidad de Cantabria, Spain


Dynamically Scheduling the Trace Produced During Program Execution into VLIW Instructions
Alberto Ferreira de Souza and Peter Rounce, University College London, United Kingdom


Segment Directory Enhancing the Limited Directory Cache Coherence Schemes
Jong Hyuk Choi and Kyu Ho Park, Korea Advanced Institute of Science and Technology, Korea


Shuffle Memory System
Kichul Kim, University of Seoul, Korea


An Efficient Parallel Prefix Sums Architecture with Domino Logic
Rong Lin, SUNY at Geneseo, Koji Nakano, Nagoya Institute of Technology, Japan, Stephan Olariu, Old Dominion University, Albert Y. Zomaya, University of Western Australia, Australia


The Performance of Coordinated and Independent Checkpointing
Luis M. Silva and Joao Gabriel Silva, Universidade de Coimbra, Portugal


Automatic Array Alignment in Parallel Matlab Scripts
Igor Z. Milosavljevic and Marwan A. Jabri, University of Sydney, Australia


Implementation of NAS Parallel Benchmarks in High Performance Fortran
Michael Frumkin, Haoqiang Jin, and Jerry Yan, MRJ Technology Solutions, Inc.


Parallel Program Archetypes
Berna L. Massingill and K. Mani Chandy, California Institute of Technology


Distributed, Scalable, Dependable Real-Time Systems: Middleware Services and Applications
Lonnie R. Welch and Binoy Ravindran, Virginia Polytechnic Institute and State University, Prashant A. Shirolkar, Shafqat M. Anwar, Terry Sergeant, and Behrooz A. Shirazi, University of Texas at Arlington, Paul Werme, Michael W. Masters, Robert D. Harrison, Wayne Mills, Tuy Do, and Judy Lafrata, Naval Surface Warfare Center, Steve Sharp, George Bilowus, Mark Swick, Jim Hoppel, and Joe Caruso, Computer Sciences Corporation


OpenMP for Networks of SMPs
Y. Charlie Hu, Honghui Lu, Alan L. Cox, and Willy Zwaenepoel, Rice University


Oblivious Deadlock-Free Routing in a Faulty Hypercube
JinSuk Kim, Eric Lehman, and Tom Leighton, Massachusetts Institute of Technology


Sparse Hypercube -- A Minimal k-Line Broadcast Graph
Satoshi Fujita, Hiroshima University, Japan, Arthur M. Farley, University of Oregon


All-to-All Broadcast on Switch-Based Clusters of Workstations
Matt Jacunski, P. Sadayappan, and D.K. Panda, Ohio State University


VBMAR: Virtual Network Load Balanced Minimal Adaptive Routing
Xicheng Liu, Timothy J. Li, and Wen Gao, Motorola-NCIC Joint R&D Laboratory, Chinese Academy of Sciences, P.R. China


Portable Parallel Programming for the Dynamic Load Balancing of Unstructured Grid Applications
Rupak Biswas, MRJ Technology Solutions, Inc., Sajal K. Das and Daniel J. Harvey, University of North Texas at Denton, Leonid Oliker, RIACS


Parallel Algorithms for Singular Value Decomposition as Applied to Failure Tolerant Manipulators
Tracy D. Braun, Anthony A. Maciejewski, and Howard Jay Siegel, Purdue University


A Parallel Adaptive Version of the Block-Based Gauss-Jordan Algorithm
N. Melab, E-G. Talbi, and S. Petiton, Universite' des Sciences et Technologies de Lille, France


Sparse Matrix Block-Cycle Redistribution
Gerardo Bandera and Emilio L. Zapata, University of Malaga, Spain


A New Approach to Parallel Dynamic Partitioning for Adaptive Unstructured Meshes
Gerd Heber, University of Delaware, Rupak Biswas, NASA Ames Research Center, Guang R. Gao, University of Delaware


An Object-Oriented Environment for Sparse Parallel Computation on Adaptive Grids
S. Filippone, IBM Semea, Italy, M. Colajanni and D. Pascucci, University of Rome "Tor Vergata", Italy


A Network Status Predictor to Support Dynamic Scheduling in Network-Based Computing Systems
JunSeong Kim and David J. Lilja, University of Minnesota


Performance Evaluation of an Infrastructure for Worldwide Parallel Computing
Thomas T. Kwan and Daniel A. Reed, University of Illinois


BRISK: A Portable and Flexible Distributed Instrumentation System
Aleksandar Bakic, Matt W. Mutka, and Diane T. Rover, Michigan State University


An Efficient Logging Algorithm for Incremental Replay of Message-Passing Applications
Franco Zambonelli, Universita di Modena e Reggio Emilia, Italy, Robert. H.B. Netzer, Brown University


Lazy Logging and Prefetch-Based Crash Recovery in Software Distributed Shared Memory Systems
Angkul Kongmunvattana and Nian-Feng Tzeng, University of Southwestern Louisiana


Visualization and Performance Prediction of Multithreaded Solaris Programs by Tracing Kernel Threads
Magnus Broberg, Lars Lundberg, and Hakan Grahn, University of Karlskrona/Ronneby, Sweden


Better Deterministic Routing on Meshes
Jop F. Sibeyn, Max-Planck-Institut fuer Informatik, Germany


Efficient Parallel Algorithms for Selection and Multiselection on Mesh-Connected Computers
Hong Shen, Griffith University, Australia


Constant-Time Algorithm for Medial Axis Transform on the Reconfigurable Mesh
Amitava Datta, University of Western Australia, Australia


2.5n-Step Sorting on n*n Meshes in the Presence of o(n^{1/2}) Worst-Case Faults
Chi-Hsiang Yeh, Behrooz Parhami, Hua Lee, and Emmanouel A. Varvarigos, University of California at Santa Barbara


The Recursive Grid Layout Scheme for VLSI Layout of Hierarchical Networks
Chi-Hsiang Yeh, Behrooz Parhami, and Emmanouel A. Varvarigos, University of California at Santa Barbara


Multi-Threaded Design and Implementation of Parallel Pipelined STAP on Parallel Computers with SMP Nodes
Wei-keng Liao, Syracuse University, Alok Choudhary, Northwestern University, Donald Weiner and Pramod Varshney, Syracuse University


A Parallel Phoneme Recognition Algorithm Based on Continuous Hidden Markov Model
Sang-Hwa Chung, Min-Uk Park, and Hyung-Soon Kim, Pusan National University, Korea


Load Adaptive Algorithms and Implementations for the 2D Discrete Wavelet Transform on Fine-Grain Multithreaded Architectures
Ashfaq A. Khokhar, Gerd Heber, Parimala Thulasiraman, and Guang R. Gao, University of Delaware


Application of Parallel Processors to Real-Time Sensor Array Processing
David R. Martinez, MIT Lincoln Laboratory


Mapping Media Streams Onto a Network of Servers
Reinhard Lueling, University of Paderborn, Germany


A Systolic Algorithm to Process Compressed Binary Images
Fikret Ercal, Mark Allen, and Hao Feng, University of Missouri at Rolla


Optimizations for Language-Directed Computational Steering
Jeffrey Vetter, University of Illinois, Karsten Schwan, Georgia Institute of Technology


Optimization Rules for Programming with Collective Operations
Sergei Gorlatch, Christoph Wedler, and Christian Lengauer, Universitaet Passau, Germany


A Flexible Clustering and Scheduling Scheme for Efficient Parallel Computation
S. Chingchit and M.J. Kumar, Curtin University of Technology, Australia, L.N. Bhuyan, Texas A&M University


Mechanisms for Just-in-Time Allocation of Resources to Adaptive Parallel Programs
Arash Baratloo, New York University, Ayal Itzkovitz, New York University and Technion, Israel, Zvi M. Kedem and Yuanyuan Zhao, New York University


Exploiting Application Tunability for Efficient, Predictable Parallel Resource Management
Fangzhe Chang, Vijay Karamcheti, and Zvi Kedem, New York University


Supporting Priorities and Improving Utilization of the IBM SP Scheduler Using Slack-Based Backfilling
David Talby and Dror G. Feitelson, The Hebrew University of Jerusalem, Israel


Guidelines for Data-Parallel Cycle-Stealing in Networks of Workstations, II: On Maximizing Guaranteed Output
Arnold L. Rosenberg, University of Massachusetts at Amherst


LLB: A Fast and Effective Scheduling Algorithm for Distributed-Memory Systems
Andrei Radulescu, Arjan J.C. van Gemund, and Hai-Xiang Lin, Delft University of Technology, The Netherlands


Parallel Load Balancing for Problems with Good Bisectors
Stefan Bischof, Ralf Ebner, and Thomas Erlebach, Technische Universitaet Muenchen, Germany


Asynchronous Group Mutual Exclusion in Ring Networks
Kuen-Pin Wu and Yuh-Jzer Joung, National Taiwan University, Taiwan


Randomized Initialization Protocols for Packet Radio Networks
Tatsuya Hayashi and Koji Nakano, Nagoya Institute of Technology, Japan, Stephan Olariu, Old Dominion University


An Optimal Disk Allocation Strategy for Partial Match Queries on Non-Uniform Cartesian Product Files
Sajal K. Das, University of North Texas at Denton, M. Cristina Pinotti, National Council of Research, Italy


Parallel Out-of-Core Divide and Conquer Techniques with Application to Classification Trees
Mahesh K. Sreenivas, Khaled Alsabti, and Sanjay Ranka, University of Florida


P-EDR: An Algorithm for Parallel Implementation of Parzen Density Estimation From Uncertain Observations
P.E. Lopez de Teruel, J.M. Garcia, M. Acacio, and O. Canovas, University of Murcia, Spain


A Fast Multithreaded Out-of-Core Visualization Technique
Peter D. Sulatycke and Kanad Ghose, State University of New York at Binghamton


Design and Implementation of a Scalable Parallel System for Multidimensional Analysis and OLAP
Sanjay Goil and Alok Choudhary, Northwestern University


Infrastructure for Building Parallel Database Systems for Multi-dimensional Data
Chialin Chang, Renato Ferreira, and Alan Sussman, University of Maryland, Joel Saltz, Johns Hopkins Medical Institutions


A New Memory-Saving Technique to Map System of Affine Recurrence Equations (SARE) onto Distributed Memory Systems
Alessandro Marongiu, University "La Sapienza", Italy, Paolo Palazzari, C.R. Casaccia, Italy


A Novel Compilation Framework for Supporting Semi-Regular Distributions in Hybrid Applications
Dhruva R. Chakrabarti and Prithviraj Banerjee, Northwestern University


Compiler Analysis to Support Compiled Communication for HPF-like Programs
Xin Yuan, Florida State University, Rajiv Gupta and Rami Melhem, University of Pittsburgh


PARADIGM (version 2.0): A New HPF Compilation System
Pramod G. Joisha and Prithviraj Banerjee, Northwestern University


Marshaling/Unmarshaling as a Compilation/Interpretation Process
Christian Queinnec, LIP6 and INRIA-Rocquencourt


Parallel Algorithms for 3D Reconstruction of Asymmetric Objects from Electron Micrographs
Robert E. Lynch, Dan C. Marinescu, Hong Lin, and Timothy S. Baker, Purdue University


Large Scale Simulation of Parallel Molecular Dynamics
Pierre-Eric Bernard, INRIA, France, Thierry Gautier and Denis Trystram, APACHE Group, France


A Parallel Algorithm for Bound-Smoothing
Kumar Rajan and Narsingh Deo, University of Central Florida


Parallel Biological Sequence Comparison Using Prefix Computations
Srinivas Aluru, New Mexico State University, Natsuhiko Futamura and Kishan Mehrotra, Syracuse University


Large Scale Simulation of Particulate Flows
Ahmed H. Sameh and Vivek Sarin, Purdue University


EDD Algorithm Performance Guarantee for Periodic Hard-Real-Time Scheduling in Distributed Systems
Maurizio A. Bonuccelli and M. Claudia Clo, Universita di Pisa, Italy


A Robust Adaptive Metric for Deadline Assignment in Heterogeneous Distributed Real-Time Systems
Jan Jonsson, Chalmers University of Technology, Sweden


The Parallelization of a Highway Traffic Flow Simulation
Charles M. Johnston, Concurrent Computer Corporation, Anthony T. Chronopoulos, The University of Texas at San Antonio


Relaxing Causal Constraints in PDES
Narayanan V. Thondugulam, Dhananjai Madhava Rao, and Philip A. Wilsey, University of Cincinnati


Rate of Change Load Balancing on Distributed and Parallel Systems
Luis Miguel Campos and Isaac D. Scherson, University of California at Irvine


An Efficient Dynamic Load Balancing Using the Dimension Exchange Method for Balancing of Quantized Loads on Hypercube Multiprocessors
Hwakyung Rim, Ju-wook Jang, and Sungchun Kim, Sogang University, Korea


Cascaded Execution: Speeding Up Unparallelized Execution on Shared-Memory Multiprocessors
Ruth E. Anderson, Thu D. Nguyen, and John Zahorjan, University of Washington


COWL: Prolog and the Magic COW
Vitor Santos Costa, Universidade do Porto, Portugal


Dynamic Grain-Size Adaptation on Object Oriented Parallel Programming -- The SCOOPP Approach
Joao Luis Sobral and Alberto Jose' Proenca, Universidade do Minho, Portugal


Implementation of a Virtual Time Synchronizer for Distributed Databases on a Cluster of Workstations
Azzedine Boukerche, University of North Texas at Denton, Timothy E. LeMaster, University of Nevada at Las Vegas, Sajal K. Das, University of North Texas at Denton, Ajoy Datta, University of Nevada at Las Vegas


A Graph Based Framework to Detect Optimal Memory Layouts for Improving Data Locality
M. Kandemir and A. Choudhary, Northwestern University, J. Ramanujam, Louisiana State University, P. Banerjee, Northwestern University


Hyperplane Partitioning: An Approach to Global Data Partitioning for Distributed Memory Machines
S.R. Prakash and Y.N. Srikant, Indian Institute of Science, India