IEEE Transactions on Parallel and Distributed Systems, Volume 7

Volume 7, Number 1, January 1996

• Editorial Board Changes. 1-2
  
• Chang-Wu Yu, Gen-Huey Chen:
  An Efficient Parallel Recognition Algorithm For Bipartite-Permutation Graphs. 3-10
  
• Zhaofang Wen:
  Multiway Merging in Parallel. 11-17
  
• Prasant Mohapatra, Chita R. Das:
  Performance Analysis of Finite-Buffered Asynchronous Multistage Interconnection Networks. 18-25
  
• Premkumar Vadapalli, Pradip K. Srimani:
  A New Family of Cayley Graph Interconnection Networks of Constant Degree Four. 26-32
  
• David M. Mandelbaum, Stefanie G. Mandelbaum:
  A Fast, Efficient Parallel-Acting Method of Generating Functions Defined by Power Series, Including Logarithm, Exponential, and Sine, Cosine. 33-45
  
• Michael A. Palis, Jing-Chiou Liou, David S. L. Wei:
  Task Clustering and Scheduling for Distributed Memory Parallel Architectures. 46-55
  
• Ben Kao, Hector Garcia-Molina:
  Scheduling Soft Real-Time Jobs Over Dual Non-Real-Time Servers. 56-68
  
• Masafumi Yamashita, Tsunehiko Kameda:
  Computing on Anonymous Networks: Part I-Characterizing the Solvable Cases. 69-89
  
• Masafumi Yamashita, Tsunehiko Kameda:
  Computing on Anonymous Networks: Part II-Decision and Membership Problems. 90-96
  

Volume 7, Number 2, February 1996

• Adrian Colbrook, Eric A. Brewer, Chrysanthos Dellarocas, William E. Weihl:
  Algorithms for Search Trees on Message-Passing Architectures. 97-108
  
• Aart J. C. Bik, Harry A. G. Wijshoff:
  Automatic Data Structure Selection and Transformation for Sparse Matrix Computations. 109-126
  
• Soon Myoung Chung, Jaerheen Yang:
  A Parallel Distributive Join Algorithm for Cube-Connected Multiprocessors. 127-137
  
• Yu-Chee Tseng, Dhabaleswar K. Panda, Ten-Hwang Lai:
  A Trip-Based Multicasting Model in Wormhole-Routed Networks with Virtual Channels. 138-150
  
• Sabine R. Öhring, Sajal K. Das:
  Folded Petersen Cube Networks: New Competitors for the Hypercubes. 151-168
  
• Rajendra V. Boppana, Suresh Chalasani:
  A Framework for Designing Deadlock-Free Wormhole Routing Algorithms. 169-183
  
• Ju-Young Lee Park, Hyeong-Ah Choi:
  Circuit-Switched Broadcasting in Torus and Mesh Networks. 184-190
  
• Avraham Leff, Joel L. Wolf, Philip S. Yu:
  Efficient LRU-Based Buffering in a LAN Remote Caching Architecture. 191-206
  
• Arun K. Nanda, Lionel M. Ni:
  MAD Kernels: An Experimental Testbed to Study Multiprocessor Memory System Behavior. 207-217
  
• Ivan Stojmenovic:
  Constant Time BSR Solutions to Parenthesis Matching, Tree Decoding, and Tree Reconstruction From Its Traversals. 218-224
  

Volume 7, Number 3, March 1996

• Hin-Sing Siu, Yeh-Hao Chin, Wei-Pang Yang:
  A Note on Consensus on Dual Failure Modes. 225-230
  
• Gurdip Singh:
  Leader Election in the Presence of Link Failures. 231-236
  
• Pei-Ji Yang, C. S. Raghavendra:
  Embedding and Reconfiguration of Binary Trees in Faulty Hypercubes. 237-245
  
• Joseph G. Peters, Michel Syska:
  Circuit-Switched Broadcasting in Torus Networks. 246-255
  
• Jehoshua Bruck, Luc De Coster, Natalie Dewulf, Ching-Tien Ho, Rudy Lauwereins:
  On the Design and Implementation of Broadcast and Global Combine Operations Using the Postal Model. 256-265
  
• Hee Yong Youn, Jae Young Lee:
  An Efficient Dictionary Machine Using Hexagonal Processor Arrays. 266-273
  
• Kumar N. Ganapathy, Benjamin W. Wah:
  Optimal Synthesis of Algorithm-Specific Lower-Dimensional Processor Arrays. 274-287
  
• John R. Pilkington, Scott B. Baden:
  Dynamic Partitioning of Non-Uniform Structured Workloads with Spacefilling Curves. 288-300
  
• Hwa-Chun Lin, C. S. Raghavendra:
  An Approximate Analysis of the Join the Shortest Queue (JSQ) Policy. 301-307
  
• Lin Chen:
  Graph Isomorphism and Identification Matrices: Parallel Algorithms. 308-319
  

Volume 7, Number 4, April 1996

• Dilip K. Saikia, Ranjan K. Sen:
  Two Ranking Schemes for Efficient Computation on the Star Interconnection Network. 321-327
  
• Nian-Feng Tzeng, Gui Liang Feng:
  Resource Allocation in Cube Network Systems Based on the Covering Radius. 328-342
  
• Benjamin Charny:
  Matrix Partitioning on a Virtual Shared Memory Parallel Machine. 343-355
  
• Eli Upfal, Sergio A. Felperin, Marc Snir:
  Randomized Routing with Shorter Paths. 356-362
  
• Ming-Syan Chen, Jeng-Chun Chen, Philip S. Yu:
  On General Results for All-to-All Broadcast. 363-370
  
• Renzo Davoli, Luigi-Alberto Giachini, Özalp Babaoglu, Alessandro Amoroso, Lorenzo Alvisi:
  Parallel Computing in Networks of Workstations with Paralex. 371-384
  
• Fredrik Dahlgren, Per Stenström:
  Evaluation of Hardware-Based Stride and Sequential Prefetching in Shared-Memory Multiprocessors. 385-398
  
• Minjoong Rim, Rajiv Jain:
  Valid Transformations: A New Class of Loop Transformations for High-Level Synthesis and Pipelined Scheduling Applications. 399-410
  
• Sanjay Kamat, Wei Zhao:
  An Efficient Optimal Reconfiguration Algorithm for FDDI-Based Networks. 411-424
  
• Gary Lewandowski, Anne Condon, Eric Bach:
  Asynchronous Analysis of Parallel Dynamic Programming Algorithms. 425-438
  
• Brian Tung, Leonard Kleinrock:
  Using Finite State Automata to Produce Self-Optimization and Self-Control. 439-448
  

Volume 7, Number 5, May 1996

• Jean Frédéric Myoupo, Anne-Cécile Fabret:
  A Modular Systolic Linearization of the Warshall-Floyd Algorithm. 449-455
  
• Dina Kravets, C. Greg Plaxton:
  All Nearest Smaller Values on the Hypercube. 456-462
  
• Ding-Kai Chen, Pen-Chung Yew:
  On Effective Execution of Nonuniform DOACROSS Loops. 463-476
  
• Douglas H. Summerville, José G. Delgado-Frias, Stamatis Vassiliadis:
  A Flexible Bit-Pattern Associative Router for Interconnection Networks. 477-485
  
• David M. Koppelman:
  A Family of Interconnection Networks for Nonuniform Traffic. 486-492
  
• Sang Kyu Lee, Hyeong-Ah Choi:
  Embedding of Complete Binary Trees into Meshes with Row-Column Routing. 493-497
  
• Yu-Chee Tseng, Sandeep K. S. Gupta:
  All-to-All Personalized Communication in a Wormhole-Routed Torus. 498-505
  
• Yu-Kwong Kwok, Ishfaq Ahmad:
  Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors. 506-521
  
• Kai Hwang, Zhiwei Xu, Masahiro Arakawa:
  Benchmark Evaluation of the IBM SP2 for Parallel Signal Processing. 522-536
  
• Cheng-Zhong Xu, Francis C. M. Lau:
  Efficient Termination Detection for Loosely Synchronous Applications in Multicomputers. 537-544
  

Volume 7, Number 6, June 1996

• Dharmavani Bhagavathi, Himabindu Gurla, Stephan Olariu, James L. Schwing, Jingyuan Zhang:
  Square Meshes Are Not Optimal for Convex Hull Computation. 545-554
  
• Sajal K. Das, Maria Cristina Pinotti, Falguni Sarkar:
  Optimal and Load Balanced Mapping of Parallel Priority Queues in Hypercubes. 555-564
  
• Ge-Ming Chiu, Cheng-Ru Young:
  Efficient Rollback-Recovery Technique in Distributed Computing Systems. 565-577
  
• Richard T. Hurley, Soon Aun Yeap:
  File Migration and File Replication: A Symbiotic Relationship. 578-586
  
• Rajeev Thakur, Alok N. Choudhary, J. Ramanujam:
  Efficient Algorithms for Array Redistribution. 587-594
  
• Ashoke Deb:
  Multiskewing-A Novel Technique for Optimal Parallel Memory Access. 595-604
  
• John R. Feehrer, Lars H. Ramfelt:
  Packet Synchronization for Synchronous Optical Deflection-Routed Interconnection Networks. 605-611
  
• Si-Qing Zheng, Shahram Latifi:
  Optimal Simulation of Linear Multiprocessor Architectures on Multiply-Twisted Cube Using Generalized Gray Codes. 612-619
  
• Christopher J. Glass, Lionel M. Ni:
  Fault-Tolerant Wormhole Routing in Meshes without Virtual Channels. 620-636
  
• Wei Shu, Min-You Wu:
  Runtime Incremental Parallel Scheduling (RIPS) on Distributed Memory Computers. 637-649
  
• G. N. Srinivasa Prasanna, Bruce R. Musicus:
  Generalized Multiprocessor Scheduling and Applications to Matrix Computations. 650-664
  
• Paul Ammann, Sushil Jajodia, Phyllis G. Frankl:
  Globally Consistent Event Ordering in One-Directional Distributed Environments. 665-670
  

Volume 7, Number 7, July 1996

• Hsien-Kuang Chiou, Willard Korfhage:
  Enhancing Distributed Event Predicate Detection Algorithms. 673-676
  
• Benjamín Barán, Eugenius Kaszkurewicz, Amit Bhaya:
  Parallel Asynchronous Team Algorithms: Convergence and Performance Analysis. 677-688
  
• Manish Gupta, Edith Schonberg, Harini Srinivasan:
  A Unified Framework for Optimizing Communication in Data-Parallel Programs. 689-704
  
• Manhoi Choy, Ambuj K. Singh:
  Localizing Failures in Distributed Synchronization. 705-716
  
• Tzung-Shi Chen, Yu-Chee Tseng, Jang-Ping Sheu:
  Balanced Spanning Trees in Complete and Incomplete Star Graphs. 717-723
  
• Kang G. Shin, Chao-Ju Hou:
  Evaluation of Load Sharing in HARTS with Consideration of Its Communication Activities. 724-739
  
• Nian-Feng Tzeng, Harish Kumar:
  Traffic Analysis and Simulation Performance of Incomplete Hypercubes. 740-754
  
• Chiung-San Lee, Tai-Ming Parng:
  A Subsystem-Oriented Performance Analysis Methodology for Shared-Bus Multiprocessors. 755-767
  

Volume 7, Number 8, August 1996

• Haigeng Wang, Alexandru Nicolau, Stephen Keung, Kai-Yeung Siu:
  Computing Programs Containing Band Linear Recurrences on Vector Supercomputers. 769-782
  
• Arshad Ali, Ramachandran Vaidyanathan:
  Exact Bounds on Running ASCEND/DESCEND and FAN-IN Algorithms on Synchronous Multiple Bus Networks. 783-790
  
• Andrea C. Arpaci-Dusseau, David E. Culler, Klaus E. Schauser, Richard P. Martin:
  Fast Parallel Sorting Under LogP: Experience with the CM-5. 791-805
  
• Ten-Hwang Lai, Ming-Jye Sheng:
  Constructing Euclidean Minimum Spanning Trees and All Nearest Neighbors on Reconfigurable Meshes. 806-817
  
• James D. Allen, David E. Schimmel:
  Issues in the Design of High Performance SIMD Architectures. 818-829
  
• Joseph JáJá, Kwan Woo Ryu:
  The Block Distributed Memory Model. 830-840
  
• José Duato:
  A Necessary and Sufficient Condition for Deadlock-Free Routing in Cut-Through and Store-and-Forward Networks. 841-854
  
• Jong Won Park, David T. Harper III:
  An Efficient Memory System for the SIMD Construction of a Gaussian Pyramid. 855-860
  
• Peter Steenkiste:
  Network-Based Multicomputers: A Practical Supercomputer Architecture. 861-875
  
• Yih-jia Tsai, Philip K. McKinley:
  A Broadcast Algorithm for All-Port Wormhole-Routed Torus Networks. 876-885
  
• Emmanouel A. Varvarigos, Ayan Banerjee:
  Routing Schemes for Multiple Random Broadcasts in Arbitrary Network Topologies. 886-895
  

• Sajal K. Das, Maria Cristina Pinotti, Falguni Sarkar:
  Correction to "Optimal and Load Balanced Mapping of Parallel Priority Queues in Hypercubes". 896
  

Volume 7, Number 9, September 1996

• Kees van Reeuwijk, Will Denissen, Henk J. Sips, Edwin M. R. M. Paalvast:
  An Implementation Framework for HPF Distributed Arrays on Message-Passing Parallel Computer Systems. 897-914
  
• Oliver E. Theel, Brett D. Fleisch:
  A Dynamic Coherence Protocol for Distributed Shared Memory Enforcing High Data Availability at Low Costs. 915-930
  
• D. L. Tao, Carlos R. P. Hartmann, Yunghsing S. (Sam) Han:
  New Encoding/Decoding Methods for Designing Fault-Tolerant Matrix Operations. 931-938
  
• Garng M. Huang, Shan Zhu:
  A New HAD Algorithm for Optimal Routing of Hierarchically Structured Data Networks. 939-953
  
• Francis C. M. Lau, Guihai Chen:
  Optimal Layouts of Midimew Networks. 954-961
  
• Debashis Basak, Dhabaleswar K. Panda:
  Designing Clustered Multiprocessor Systems under Packaging and Technological Advancements. 962-978
  
• Amnon Barak, Eugen Schenfeld:
  Embedding Classical Communication Topologies in the Scalable OPAM Architecture. 979-992
  

Volume 7, Number 10, October 1996

• Soo-Young Lee, Kyung-Geun Lee:
  Synchronous and Asynchronous Parallel Simulated Annealing with Multiple Markov Chains. 993-1008
  
• Stephan Olariu, Albert Y. Zomaya:
  A Time- and Cost-Optimal Algorithm for Interlocking Sets-With Applications. 1009-1025
  
• Debanjan Saha, Sampath Rangarajan, Satish K. Tripathi:
  An Analysis of the Average Message Overhead in Replica Control Protocols. 1026-1034
  
• Ravi Prakash, Mukesh Singhal:
  Low-Cost Checkpointing and Failure Recovery in Mobile Computing Systems. 1035-1048
  
• Virginia Mary Lo, Sanjay V. Rajopadhye, Jan Arne Telle, Xiaoxiong Zhong:
  Parallel Divide and Conquer on Meshes. 1049-1058
  
• Patrick Sobalvarro:
  Analytical Modeling of Multistage, Multipath Networks. 1059-1064
  
• Theodora A. Varvarigou, Vwani P. Roychowdhury, Thomas Kailath, Eugene L. Lawler:
  Scheduling In and Out Forests in the Presence of Communication Delays. 1065-1074
  
• Nils Nieuwejaar, David Kotz, Apratim Purakayastha, Carla Schlatter Ellis, Michael L. Best:
  File-Access Characteristics of Parallel Scientific Workloads. 1075-1089
  
• Phillip M. Dickens, Philip Heidelberger, David M. Nicol:
  Parallelized Direct Execution Simulation of Message-Passing Parallel Programs. 1090-1105
  
• Dan Picker, Ronald D. Fellman:
  Successive Superposition: A Technique for the Exact Modeling of Deterministic Packet Queuing Networks. 1106-1120
  

Volume 7, Number 11, November 1996

• Paul Petersen, David A. Padua:
  Static and Dynamic Evaluation of Data Dependence Analysis Techniques. 1121-1132
  
• Ramaswamy Govindarajan, Erik R. Altman, Guang R. Gao:
  A Framework for Resource-Constrained Rate-Optimal Software Pipelining. 1133-1149
  
• Nelson L. Passos, Edwin Hsing-Mean Sha:
  Achieving Full Parallelism Using Multidimensional Retiming. 1150-1163
  
• Shiow-yang Wu, Daniel P. Miranker, James C. Browne:
  Decomposition Abstraction in Parallel Rule Languages. 1164-1184
  
• Craig S. Freedman, Josef Burger, David J. DeWitt:
  SPIFFI-A Scalable Parallel File System for the Intel Paragon. 1185-1200
  
• Dannie Durand, Thierry Montaut, Lionel Kervella, William Jalby:
  Impact of Memory Contention on Dynamic Scheduling on NUMA Multiprocessors. 1201-1214
  

Volume 7, Number 12, December 1996

• Nageswara S. V. Rao:
  On Parallel Algorithms for Single-Fault Diagnosis in Fault Propagation Graph Systems. 1217-1223
  
• Evan Torrie, Margaret Martonosi, Chau-Wen Tseng, Mary W. Hall:
  Characterizing the Memory Behavior of Compiler-Parallelized Applications. 1224-1237
  
• Chun Gong, Rami G. Melhem, Rajiv Gupta:
  Loop Transformations for Fault Detection in Regular Loops on Massively Parallel Systems. 1238-1249
  
• David Koufaty, Xiangfeng Chen, David K. Poulsen, Josep Torrellas:
  Data Forwarding in Scalable Shared-Memory Multiprocessors. 1250-1264
  
• José N. Amaral, Joydeep Ghosh:
  A Concurrent Architecture for Serializable Production Systems. 1265-1280
  
• Kemal Efe, Antonio Fernández:
  Mesh-Connected Trees: A Bridge Between Grids and Meshes of Trees. 1281-1291
  
• Pascal Berthomé, Afonso Ferreira, Stephane Perennes:
  Optimal Information Dissemination in Star and Pancake Networks. 1292-1300
  
• Po-Jen Chuang:
  CGIN: A Fault Tolerant Modified Gamma Interconnection Network. 1301-1306
  
• Sol M. Shatz, Shengru Tu, Tadao Murata, Sastry Duri:
  An Application of Petri Net Reduction for Ada Tasking Deadlock Analysis. 1307-1322
  
• Vijay K. Garg, Brian Waldecker:
  Detection of Strong Unstable Predicates in Distributed Programs. 1323-1333