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 prabhat@maverick.usc.edu. 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.

---

3

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

96

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

112

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,

239

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

146

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

17

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

247

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

36

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

168

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

35

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

32

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

127

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

61

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

79

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

57

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

138

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

89

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

18

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

184

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

188

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

195

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

202

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

91

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

244

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

151

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

170

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

43

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

139

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

234

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

131

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

52

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

39

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

48

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

56

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

113

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

144

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

134

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

95

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

214

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

121

Shuffle Memory System
Kichul Kim, University of Seoul, Korea

192

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

88

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

63

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

114

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

42

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

198

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

255

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

148

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

100

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

237

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

34

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

167

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

116

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

47

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

22

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

218

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

46

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

135

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

213

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

197

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

182

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

140

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

126

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

12

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

58

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

74

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

228

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

215

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

154

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

173

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

208

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

23

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

224

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

9

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

217

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

53

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

181

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

222

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

226

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

105

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

4

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

93

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

108

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

14

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

150

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

200

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

207

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

115

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

251

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

221

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

216

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

65

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

225

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

152

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

162

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

28

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

99

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

130

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

180

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

147

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

257

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

62

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

104

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

81

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

194

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

156

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

176

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

229

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

256

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

252

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

122

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

243

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

45

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