IEEE Transactions on Parallel and Distributed Systems, Volume 9

Volume 9, Number 1, January 1998

Compilation

• 
  Rudolf Eigenmann, Jay P. Hoeflinger, David A. Padua:
  On the Automatic Parallelization of the Perfect Benchmarks. 5-23
• 
  Pierre-Yves Calland, Alain Darte, Yves Robert:
  Circuit Retiming Applied to Decomposed Software Pipelining. 24-35

Operating Systems

• 
  Juan Carlos Gomez, Edward Mascarenhas, Vernon Rego:
  The CLAM Approach to Multithreaded Communication on Shared-Memory Multiprocessors: Design and Experiments. 36-49
• 
  Nian-Feng Tzeng, Hsing-Lung Chen:
  Fast Compaction in Hypercubes. 50-56
• 
  Debendra Das Sharma, Dhiraj K. Pradhan:
  Job Scheduling in Mesh Multicomputers. 57-70

Models for Parallel Programming

• 
  Gail A. Alverson, William G. Griswold, Calvin Lin, David Notkin, Lawrence Snyder:
  Abstractions for Portable, Scalable Parallel Programming. 71-86

Scheduling Algorithms

• 
  Sekhar Darbha, Dharma P. Agrawal:
  Optimal Scheduling Algorithm for Distributed-Memory Machines. 87-96

Volume 9, Number 2, February 1998

Applications and Algorithms

• 
  Thomas Lippert, Armin Seyfried, Achim Bode, Klaus Schilling:
  Hyper-Systolic Parallel Computing. 97-108
• 
  Cong Fu, Xiangmin Jiao, Tao Yang:
  Efficient Sparse LU Factorization with Partial Pivoting on Distributed Memory Architectures. 109-125
• 
  Hao Chen, Nicholas S. Flann, Daniel W. Watson:
  Parallel Genetic Simulated Annealing: A Massively Parallel SIMD Algorithm. 126-136
• 
  Yuh-Jzer Joung, Scott A. Smolka:
  Strong Interaction Fairness Via Randomization. 137-149

Routing

• 
  Andrew A. Chien:
  A Cost and Speed Model for k-ary n-Cube Wormhole Routers. 150-162
• 
  Ming-Jer Tsai, Sheng-De Wang:
  A Fully Adaptive Routing Algorithm for Dynamically Injured Hypercubes, Meshes, and Tori. 163-174

Interconnection Networks

• 
  Geunmo Kim, Hyunsoo Yoon:
  On Submesh Allocation for Mesh Multicomputers: A Best-Fit Allocation and a Virtual Submesh Allocation for Faulty Meshes. 175-185
• 
  Biing-Feng Wang:
  Finding a k-Tree Core and a k-Tree Center of a Tree Network in Parallel. 186-191

Mapping Applications to Machines

• 
  Frederic Desprez, Jack J. Dongarra, Antoine Petitet, Cyril Randriamaro, Yves Robert:
  Scheduling Block-Cyclic Array Redistribution. 192-205

Performance Evaluation

• 
  Gheith A. Abandah, Edward S. Davidson:
  Characterizing Distributed Shared Memory Performance: A Case Study of the Convex SPP1000. 206-216

Multcasting

• 
  Ge-Ming Chiu, Chih-Ming Hsiao:
  A Note on Total Ordering Multicast Using Propagation Trees. 217-223

Volume 9, Number 3, March 1998

Operating Systems

• 
  Jeeho Sohn, Thomas G. Robertazzi, Serge Luryi:
  Optimizing Computing Costs Using Divisible Load Analysis. 225-234
• 
  Jerrell Watts, Stephen Taylor:
  A Practical Approach to Dynamic Load Balancing. 235-248
• 
  Albert Y. Zomaya, Matthew Clements, Stephan Olariu:
  A Framework for Reinforcement-Based Scheduling in Parallel Processor Systems. 249-260

Interconnection Networks

• 
  Marcelo M. de Azevedo, Nader Bagherzadeh, Shahram Latifi:
  Low Expansion Packings and Embeddings of Hypercubes into Star Graphs: A Performance-Oriented Approach. 261-274

Algorithms

• 
  Tatsuya Hayashi, Koji Nakano, Stephan Olariu:
  Work-Time Optimal k-Merge Algorithms on the PRAM. 275-282

Applications and Algorithms

• 
  Tieng K. Yap, Ophir Frieder, Robert L. Martino:
  Parallel Computation in Biological Sequence Analysis. 283-294

Performance Evaluation/Analysis

• 
  John C. S. Lui, Richard R. Muntz, Donald F. Towsley:
  Computing Performance Bounds of Fork-Join Parallel Programs Under a Multiprocessing Environment. 295-311

Real-Time

• 
  G. Manimaran, C. Siva Ram Murthy:
  An Efficient Dynamic Scheduling Algorithm For Multiprocessor Real-Time Systems. 312-319

Volume 9, Number 4, April 1998

Fault Tolerance

• 
  Jie Wu:
  Adaptive Fault-Tolerant Routing in Cube-Based Multicomputers Using Safety Vectors. 321-334
• 
  Hin-Sing Siu, Yeh-Hao Chin, Wei-Pang Yang:
  Byzantine Agreement in the Presence of Mixed Faults on Processors and Links. 335-345

Algorithms

• 
  Lars Lundberg, Håkan Lennerstad:
  Using Recorded Values for Bounding the Minimum Completion Time in Multiprocessors. 346-358
• 
  Yeh-Ching Chung, Ching-Hsien Hsu, Sheng-Wen Bai:
  A Basic-Cycle Calculation Technique for Efficient Dynamic Data Redistribution. 359-377

Distributed Software

• 
  A. Prasad Sistla, Ouri Wolfson, Yixiu Huang:
  Minimization of Communication Cost Through Caching in Mobile Environments. 378-390

Databases

• 
  Ouri Wolfson, Yixiu Huang:
  Competitive Analysis of Caching in Distributed Databases. 391-409

Comments

• 
  Sang Kyun Yun, Kyu Ho Park:
  Comments on "Hierarchical Cubic Networks". 410-414
• 
  Ting-Lu Huang, Chien-Hua Shann:
  A Comment on "A Circular List-Based Mutual Exclusion Scheme for Large Shared-Memory Multiprocessors". 414-416

Volume 9, Number 5, May 1998

Applications and Algorithms

• 
  Edin Hodzic, Weijia Shang:
  On Supernode Transformation with Minimized Total Running Time. 417-428
• 
  Gerassimos D. Barlas:
  Collection-Aware Optimum Sequencing of Operations and Closed-Form Solutions for the Distribution of a Divisible Load on Arbitrary Processor Trees. 429-441
• 
  Young-Joo Suh, Sudhakar Yalamanchili:
  All-To-All Communication with Minimum Start-Up Costs in 2D/3D Tori and Meshes. 442-458

Operating Systems

• 
  Bozhidar Dimitrov, Vernon Rego:
  Arachne: A Portable Threads System Supporting Migrant Threads on Heterogeneous Network Farms. 459-469

Fault Tolerance/Reliability

• 
  Qin Zheng, Kang G. Shin:
  Fault-Tolerant Real-Time Communication in Distributed Computing Systems. 470-480

Networks

• 
  Debashis Basak, Dhabaleswar K. Panda:
  Alleviating Consumption Channel Bottleneck in Wormhole-Routed k-ary n-Cube Systems. 481-496
• 
  Ahmed Louri, Brent Weech, Costas Neocleous:
  A Spanning Multichannel Linked Hypercube: A Gradually Scalable Optical Interconnection Network for Massively Parallel Computing. 497-512

Volume 9, Number 6, June 1998

Networks

• 
  Ben H. H. Juurlink, Jop F. Sibeyn, P. S. Rao:
  Gossiping on Meshes and Tori. 513-525
• 
  Jenq-Shyan Yang, Chung-Ta King:
  Designing Tree-Based Barrier Synchronization on 2D Mesh Networks. 526-534
• 
  Rajendra V. Boppana, Suresh Chalasani, Cauligi S. Raghavendra:
  Resource Deadlocks and Performance of Wormhole Multicast Routing Algorithms. 535-549

Applications and Algorithms

• 
  Amit Sengupta, Cauligi S. Raghavendra:
  All-To-All Broadcast and Matrix Multiplication in Faulty SIMD Hypercubes. 550-560
• 
  Koji Nakano, Stephan Olariu:
  An Efficient Algorithm for Row Minima Computations on Basic Reconfigurable Meshes. 561-569

Machine Architecture and Design

• 
  Steven Wallace, Nader Bagherzadeh:
  Modeled and Measured Instruction Fetching Performance for Superscalar Microprocessors. 570-578

Fault Tolerance/Reliability

• 
  Narutoshi Umemoto, Hirotsugu Kakugawa, Masafumi Yamashita:
  A Self-Stabilizing Ring Orientation Algorithm With a Smaller Number of Processor States. 579-584

Performance Evaluation/Analysis

• 
  Michele Colajanni, Philip S. Yu, Daniel M. Dias:
  Analysis of Task Assignment Policies in Scalable Distributed Web-Server Systems. 585-600

Cache

• 
  David C. Wong, Edward W. Davis, Jeffrey O. Young:
  A Software Approach to Avoiding Spatial Cache Collisions in Parallel Processor Systems. 601-608

Volume 9, Number 7, July 1998

Compilation

• 
  Gagan Agrawal:
  Interprocedural Partial Redundancy Elimination With Application to Distributed Memory Compilation. 609-625

Networks

• 
  Eric Fleury, Pierre Fraigniaud:
  A General Theory for Deadlock Avoidance in Wormhole-Routed Networks. 626-638
• 
  Vassilios V. Dimakopoulos, Nikitas J. Dimopoulos:
  A Theory for Total Exchange in Multidimensional Interconnection Networks. 639-649
• 
  Dilip K. Saikia, R. Badrinath, Ranjan K. Sen:
  Embedding Torus on the Star Graph. 650-663

Real-Time

• 
  Shobana Balakrishnan, Füsun Özgüner:
  A Priority-Driven Flow Control Mechanism for Real-Time Traffic in Multiprocessor Networks. 664-678

Algorithms

• 
  Abdel Krim Amoura, Evripidis Bampis, Jean-Claude König:
  Scheduling Algorithms for Parallel Gaussian Elimination With Communication Costs. 679-686
• 
  Sanguthevar Rajasekaran, Insup Lee:
  Parallel Algorithms for Relational Coarsest Partition Problems. 687-699

Comments

• 
  Sipra Das Bit, Arnab Chaudhuri:
  Fault Diagnosis in a Benes Interconnection Network. 700-703

Volume 9, Number 8, August 1998

Applications & Algorithms

• 
  Keqin Li, Yi Pan, Si-Qing Zheng:
  Fast and Processor Efficient Parallel Matrix Multiplication Algorithms on a Linear Array With a Reconfigurable Pipelined Bus System. 705-720
• 
  Yu-Chen Kuo, Shing-Tsaan Huang:
  Recognizing Nondominated Coteries and wr-Coteries by Availability. 721-728
• 
  Sanda M. Harabagiu, Dan I. Moldovan:
  Parallel System for Text Inference Using Marker Propagations. 729-747
• 
  Azzedine Boukerche, Carl Tropper:
  A Distributed Graph Algorithm for the Detection of Local Cycles and Knots. 748-757

Machine Architecture & Design

• 
  Susanne E. Hambrusch, Ashfaq A. Khokhar, Yi Liu:
  Scalable S-To-P Broadcasting on Message-Passing MPPs. 758-768

Compilation

• 
  Kathryn S. McKinley:
  A Compiler Optimization Algorithm for Shared-Memory Multiprocessors. 769-787

Networks

• 
  Johanne Cohen, Pierre Fraigniaud, Jean-Claude König, André Raspaud:
  Optimized Broadcasting and Multicasting Protocols in Cut-Through Routed Networks. 788-802
• 
  Ralf Klasing:
  Improved Compressions of Cube-Connected Cycles Networks. 803-812

Fault Tolerance/Reliability

• 
  Lihao Xu, Jehoshua Bruck:
  Deterministic Voting in Distributed Systems Using Error-Correcting Codes. 813-824
• 
  K. N. Balasubramanya Murthy, K. Bhuvaneswari, C. Siva Ram Murthy:
  A New Algorithm Based on Givens Rotations for Solving Linear Equations on Fault-Tolerant Mesh-Connected Processors. 825-832

Volume 9, Number 9, September 1998

Applications & Algorithms

• 
  Sanguthevar Rajasekaran, Sartaj Sahni:
  Randomized Routing, Selection, and Sorting on the OTIS-Mesh. 833-840
• 
  Shan Zhu, Garng M. Huang:
  A New Parallel and Distributed Shortest Path Algorithm for Hierarchically Clustered Data Networks. 841-855
• 
  Oh-Heum Kwon, Kyung-Yong Chwa:
  An Algorithm for Scheduling Jobs in Hypercube Systems. 856-860
• 
  José Alberto Fernández-Zepeda, Ramachandran Vaidyanathan, Jerry L. Trahan:
  Scaling Simulation of the Fusing-Restricted Reconfigurable Mesh. 861-871
• 
  Ishfaq Ahmad, Yu-Kwong Kwok:
  On Exploiting Task Duplication in Parallel Program Scheduling. 872-892

Networks

• 
  W. Stephen Lacy, José Cruz-Rivera, D. Scott Wills:
  The Offset Cube: A Three-Dimensional Multicomputer Network Topology Using Through-Wafer Optics. 893-908

Databases/Security

• 
  Moni Naor, Avishai Wool:
  Access Control and Signatures via Quorum Secret Sharing. 909-922

Comments

• 
  Jianxi Fan:
  Diagnosability of the Möbius Cubes. 923-928

Volume 9, Number 10, October 1998

Applications & Algorithms

• 
  Dharmavani Bhagavathi, Himabindu Gurla, Stephan Olariu, James L. Schwing, Larry Wilson, Jingyuan Zhang:
  Time- and VLSI-Optimal Sorting on Enhanced Meshes. 929-937
• 
  James C. Greer:
  Parallelization Model for Successive Approximations to the Rayleigh-Ritz Linear Variational Problem. 938-946

Fault Tolerance/Reliability

• 
  Hussam M. Soliman, Adel Said Elmaghraby:
  An Analytical Model for Hybrid Checkpointing in Time Warp Distributed Simulation. 947-951
• 
  Ge-Ming Chiu, Kai-Shung Chen:
  Efficient Fault-Tolerant Multicast Scheme for Hypercube Multicomputers. 952-962
• 
  Jichiang Tsai, Sy-Yen Kuo, Yi-Min Wang:
  Theoretical Analysis for Communication-Induced Checkpointing Protocols with Rollback-Dependency Trackability. 963-971
• 
  James S. Plank, Kai Li, Michael A. Puening:
  Diskless Checkpointing. 972-986

Interconnection Networks

• 
  Chi-Hsiang Yeh, Emmanouel A. Varvarigos:
  Macro-Star Networks: Efficient Low-Degree Alternatives to Star Graphs. 987-1003
• 
  Rajeev Sivaram, Dhabaleswar K. Panda, Craig B. Stunkel:
  Efficient Broadcast and Multicast on Multistage Interconnection Networks Using Multiport Encoding. 1004-1028

Memory

• 
  Jeffrey K. Hollingsworth:
  Critical Path Profiling of Message Passing and Shared-Memory Programs. 1029-1040

Performance Evaluation

• 
  Simonetta Balsamo, Lorenzo Donatiello, Nico M. van Dijk:
  Bound Performance Models of Heterogeneous Parallel Processing Systems. 1041-1056

Volume 9, Number 11, November 1998

Algorithms

• 
  Venkatavasu Bokka, Himabindu Gurla, Stephan Olariu, James L. Schwing:
  Constant-Time Algorithms for Constrained Triangulations on Reconfigurable Meshes. 1057-1072

Data Structures/Databases

• 
  Isidore Rigoutsos, Alex Delis:
  Managing Statistical Behavior of Large Data Sets in Shared-Nothing Architectures. 1073-1087

Mapping Applications to Machines

• 
  Min Tan, Howard Jay Siegel:
  A Stochastic Model for Heterogeneous Computing and Its Application in Data Relocation Scheme Development. 1088-1101

Operating Systems

• 
  Samuel H. Russ, Jonathan Robinson, Brian K. Flachs, Bjørn Heckel:
  The Hector Distributed Run-Time Environment. 1102-1114

Performance Evaluation

• 
  Chung-Yen Chang, Prasant Mohapatra:
  An Efficient Method for Approximating Submesh Reliability of Two-Dimensional Meshes. 1115-1124

Real-Time

• 
  Ti-Yen Yen, Wayne H. Wolf:
  Performance Estimation for Real-Time Distributed Embedded Systems. 1125-1136
• 
  G. Manimaran, C. Siva Ram Murthy:
  A Fault-Tolerant Dynamic Scheduling Algorithm for Multiprocessor Real-Time Systems and Its Analysis. 1137-1152

Volume 9, Number 12, December 1998

Algorithms

• 
  Tatsuya Hayashi, Koji Nakano, Stephan Olariu:
  Optimal Parallel Algorithms for Finding Proximate Points, with Applications. 1153-1166
• 
  Tatsuya Hayashi, Koji Nakano, Stephan Olariu:
  An O((log log n)²) Time Algorithm to Compute the Convex Hull of Sorted Points on Reconfigurable Meshes. 1167-1179

Compilation

• 
  William Blume, Rudolf Eigenmann:
  Nonlinear and Symbolic Data Dependence Testing. 1180-1194

Fault Tolerance

• 
  Marcelo M. de Azevedo, Douglas M. Blough:
  Multistep Interactive Convergence: An Efficient Approach to the Fault-Tolerant Clock Synchronization of Large Multicomputers. 1195-1212
• 
  Guohong Cao, Mukesh Singhal:
  On Coordinated Checkpointing in Distributed Systems. 1213-1225

Machine Architecture

• 
  Chih-Fang Wang, Sartaj Sahni:
  Basic Operations on the OTIS-Mesh Optoelectronic Computer. 1226-1236

Memory

• 
  Qutaibah M. Malluhi, William E. Johnston:
  Coding for High Availability of a Distributed-Parallel Storage System. 1237-1252

Networks

• 
  Ada Wai-Chee Fu, Siu-Cheung Chau:
  Cyclic-Cubes: A New Family of Interconnection Networks of Even Fixed-Degrees. 1253-1268