Proceedings of IPPS 96
`
`The 10th Internationall Parallel Processing
`Symposium
`
`April 15 19 1996
`
`Honolulu Hawaii
`
`The IEEE Computer Society Technical Committee on Parallel Processing
`
`Sponsored by
`
`In cooperation with
`The Association for Computing Machinery SIGARCH
`
`IEEE Computer Society Press
`Los Alamitos California
`
`Washington
`
`Brussels
`
`Tokyo
`
`Petitioner IBM – Ex. 1069, p. 1
`
`

`
`Petitioner IBM – Ex. 1069, p. 2
`
`

`
`Petitioner IBM – Ex. 1069, p. 3
`
`

`
`Petitioner IBM – Ex. 1069, p. 4
`
`

`
`IEEE Computer Society Press
`10662 Los Vaqueros Circle
`P.O Box 3014
`Los Alamitos CA 90720-1264
`
`Copyright
`
`1996 by The Institute of Electrical
`All rights reserved
`
`and Electronics Engineers Inc
`
`Copyright and Reprint Permissions
`to the source Libraries may
`Abstracting
`photocopy beyond the limits of US copyright
`those articles in this volume
`law for private use of patrons
`code at
`the bottom of the first page provided that the per-copy fee indicated in the code is paid
`that carry
`through the Copyright Clearance Center 222 Rosewood Drive Danvers MA 01923
`
`is permitted with credit
`
`to IEEE Copyrights Manager
`Other copying reprint or republication requests
`should be addressed
`Service Center 445 Hoes Lane P.O Box 1331 Piscataway NJ 08855-1331
`
`IEEE
`
`reflect
`
`The papers in this book comprise the proceedings of the meeting mentioned on the cover and title page They
`are published as presented and
`opinions and in the interests of timely dissemination
`the authors
`endorsement by the
`inclusion
`does not necessarily constitute
`change Their
`without
`in this publication
`editors the IEEE Computer Society Press or the institute of Electrical and Electronics Engineers
`Inc
`
`IEEE Computer Society Press Order Number PR07255
`ISBN 0-8186-7255-2
`
`IEEE Order Plan Catalog Number 96TB 100038
`Microfiche ISBN 0-8186-7257-9
`
`Additional copies may be ordered from
`
`IEEE Computer Society Press
`Customer Service Center
`
`IEEE Service Center
`
`445 Hoes Lane
`
`10662 Los Vaqueros Circle
`P.O Box 3014
`Los Alamitos CA 90720-1264
`Tel 1-714-821-8380
`Fax 1-714-821-4641
`Email cs.booksc4computer
`
`org
`
`P.O Box 1331
`Piscataway NJ 08855-1331
`Tel 1-908-981-1393
`Fax 1-908-981-9667
`
`IEEE Computer Society
`13 Avenue de lAquilon
`B-1200 Brussels
`BELGIUM
`Tel 32-2-770-2198
`Fax 32-2-770-8505
`
`IEEE Computer Society
`Ooshima Building
`2-19-1 Minami-Aoyama
`
`Minato-ku Tokyo 107
`JAPAN
`Tel 81-3-3408-3118
`Fax 81
`tokyoofc@computer.org
`
`3408-3553
`
`mis.custserv@computer.org
`
`euro.ofc@computer.org
`
`Kavanaugh
`Editorial production by Mary
`Cover design by Mike Nomura
`Printed in the United States of America by KNI Inc
`
`The Institute of Electrical and Electronics Engineers Inc
`
`Petitioner IBM – Ex. 1069, p. 5
`
`

`
`Proceedings of JPPS 96
`
`Table of Contents
`
`Message from the General Chair
`Message from the Program Chair
`
`Message from the Steering Committee Chair
`Program and Organizing Committees
`
`Reviewers
`
`xv
`
`xvii
`
`xviii
`
`xix
`
`xxiii
`
`Keynote Address Can Multithreaded Programming Save Massively Parallel
`Compuffng
`Speaker Charles
`
`Institute of Technology
`
`Leiserson
`
`Massachusetts
`
`Session
`Compiler Optimization
`Chair Prith Banerjee
`University of Illinois Urbana
`
`Eliminating Stale Data References through Array Data-Flow Analysis
`Ghoi and P-C Yew
`
`Commutativity Analysis
`
`Technique for Automatically Parallelizing Pointer-Based
`
`Computations
`Rinard and
`
`Diniz
`
`Profiling Dependence Vectors for Loop Parallelization
`S-I Tseng C-T King and C-
`Tang
`
`Method for Register Allocation to Loops in Multiple Register File Architectures
`D.J Kolson
`Dutt and
`Nicolau
`Kennedy
`
`Affine-by-Statement Transformations
`Xue
`
`of Imperfectly Nested Loops
`
`The Combined Effectiveness of Unimodular Transformations Tiling and
`
`Software Prefetching
`R.H Saavedra
`
`Mao
`
`Park
`
`Giame and
`
`Moon
`
`Session
`Scientific Engineering Applications
`Chair José D.P Rolim University of Geneva
`
`Ocean Circulation on the Intel Paragon Modeling and Implementation
`Ahmad and H-M Hsu
`K-C Leung
`
`Implementation of an Automatic Semi-Fluid Motion Analysis Algorithm on Massively
`Parallel Computer
`Kambhamettu and AF Hasler
`Palaniappan
`Faisal
`NAS Experiences of Porting CM Fortran Codes to HPF on IBM SP2 and SGI Power
`Challenge
`
`Saini
`
`14
`
`23
`
`28
`
`34
`
`39
`
`47
`
`55
`
`56
`
`Petitioner IBM – Ex. 1069, p. 6
`
`

`
`Dynamic Alignment and Distribution of Irregularly Coupled Data Arrays for Scalable
`Parallelization of Particle-in-Cell Problems
`W-K Liao C-W Ou and
`
`Ranka
`
`Hierarchical Parallel Processing System for the Multipass-Rendering Method
`Toh and
`Yamauchi
`Nakamura
`Kobayashi
`
`Performance Modeling and Composition
`Yang and
`Steinberg
`Yelick
`
`Case Study in Cell Simulation
`
`Session
`
`Distributed Memory Systems
`Chair Behrooz Shirazi
`
`University of Texas Arlington
`
`Study of High-Performance Communication Mechanism for Multicomputer Systems
`Murayama
`Yoshizawa
`Aimoto
`Murase
`Hayashi
`Inouchi
`and
`Iwamoto
`
`in 1996 The ASCI TFLOP System
`TeraFLOP Supercomputer
`Wheat
`Scott and
`T.G Mattson
`Experience with Parallel Computing on the AN2 Network
`Burrows and CA Thekkath
`D.J Scales
`Balanced Low-Cost Architecture
`for Mass Storage Management
`Achieving
`Multiple Fast Ethernet Channels on the Beowuif Parallel Workstation
`Savarese M.R Berry and
`Sterling D.J Becker
`Reschke
`
`through
`
`Exploiting the Capabilities of Communications Co-Processors
`KE Schauser C.J Scheiman J.M Ferguson and P.Z Kolano
`Effects of Multithreading on Data and Workload Distribution for Distributed-Memory
`
`Multiprocessors
`Sohn
`
`Sato
`
`Yoo and J-L Gaudiot
`
`Session
`
`Shared Memory Systems
`Technische Universität München
`Chair Rudolf
`Hackenberg
`
`Formal Verification of Delayed Consistency Protocols
`Dubois
`Pong and
`
`Dag-Consistent Distributed Shared Memory
`Fri go CF Joerg C.E Leiserson and K.H Randall
`R.D Blumofe
`Categorizing Network Traffic in Update-Based Protocols on Scalable Multiprocessors
`Bianchini T.J LeBlanc and J.E Veenstra
`
`Implementing the Data Diffusion Machine Using Crossbar Routers
`H.L Muller P.W.A Stallard and D.H.D Warren
`
`Memory Controller for Improved Performance of Streamed Computations on
`Symmetric Multiprocessors
`S.A McKee and WA Wuif
`Kiloprocessor Extensions to SCI
`Kaxiras
`
`vi
`
`57
`
`62
`
`68
`
`76
`
`84
`
`94
`
`104
`
`109
`
`116
`
`124
`
`132
`
`142
`
`152
`
`159
`
`166
`
`Petitioner IBM – Ex. 1069, p. 7
`
`

`
`Session
`
`Algorithms
`Chair Joseph JáJá University of Maryland
`
`Approximate Compaction and Padded-Sorting on Exclusive Write PRAMs
`Kurylowski and Wierzbicki
`
`174
`
`Parallel Solution to the Extended Set Union Problem with Unlimited Backtracking
`Pinotti V.A Crupi and S.K Das
`
`............
`
`182
`
`Parallel Algorithm for Minimization of Finite Automata
`Ravikumar and
`
`Xiong
`
`Randomized Algorithm for Voronoi Diagram of Line Segments on Coarse-Grained
`
`Multiprocessors
`Deng and
`
`Zhu
`
`Post-Optimization for Static Multiprocessor Schedules
`Self-Timed Resynchronization
`Sriram and E.A Lee
`S.S Bhattacharyya
`
`the Spanners of Graphs in Parallel
`Constructing
`Liang and R.P Brent
`
`Session
`
`Programming Languages
`Chair Gul Agha University of Illinois Urbana
`
`Converse An Interoperable Framework for Parallel Programming
`Krishnan and
`Kale
`Bhandarkar
`Jagathesan
`Yelon
`Dome Parallel Programming in Distributed Computing Environment
`Lowekamp
`J.N
`Arabe
`Seligman
`Beguelin
`Starkey
`and
`
`Stephan
`
`Nested Parallel Call Optimization
`Pontelli and
`Gupta
`The Parallel Break Construct or How to Kill an Activity Tree
`Exman
`Y.J Friedman D.G Feitelson and
`Optimizing COOP Languages
`Zhang
`Karamcheti
`
`Study of Protein Dynamics Program
`Ng and A.A Ozien
`
`Support
`
`for Extensibility and Reusability in Concurrent Object-Oriented Programming
`Language
`Pandey and
`
`Browne
`
`Session
`Communication
`Chair Cho-Li Wang
`
`University of Hong Kong
`
`Modeling the Communication Performance of the IBM SP2
`G.A Abandah and E.S Davidson
`
`Adaptive Source Routing in Multistage Interconnection Networks
`Aydogan c.B Stunkel
`Aykanat and
`Abali
`
`The Effects of Network Contention on Processor Allocation Strategies
`Moore and L.M Ni
`
`ServerNet Deadlock Avoidance and Fractahedral Topologies
`
`Horst
`
`vii
`
`187
`
`192
`
`199
`
`206
`
`212
`
`218
`
`225
`
`230
`
`235
`
`241
`
`249
`
`258
`
`268
`
`274
`
`Petitioner IBM – Ex. 1069, p. 8
`
`

`
`Analysis of Memory Interference in Buffered Multiprocessor Systems in Presence of
`Hot Spots and Favorite Memories
`S.K Das and S.K Sen
`
`Benefits of Processor Clustering in Designing Large Parallel Systems When and How7
`Basak D.K Panda and
`Banikazemi
`
`Session
`
`Implementation of Primitive Operations
`Chair Gregory Plaxton University of Texas Austin
`
`Practical Parallel Algorithms for Dynamic Data Redistribution Median Finding and
`Selection
`
`DA Bader and
`Parallel Implementation of Bordvka Minimum Spanning Tree Algorithm
`ChungandA Condon
`
`JáJd
`
`Practical Algorithms for Selection on Coarse-Grained Parallel Computers
`Ranka
`Aluru Goil and
`Al-furiah
`
`Parallel Multilevel Graph Partitioning
`Kumar
`Karypis and
`PACK/UNPACK on Coarse-Grained Distributed Memory Parallel Machines
`Bae and
`Ranka
`
`Random Seeking
`Load Balancing
`N.R Mahapatra and
`
`Duff
`
`General Efficient and Informed Randomized Scheme for Dynamic
`
`Session
`
`Resource Allocation and Management
`Chair Rafael
`Saavedra
`University of Southern California
`
`in Torus-Based Networks
`Bose
`
`Resource Placement
`M.M Eae and
`Simultaneous Compression of Makespan and Number of Processors Using CRP
`GeandD.Y.Y Yun
`
`Implementation of Scalable Blocking Locks Using an Adaptive Thread Scheduler
`Schwan
`Mukherjee and
`
`Hector Automated Task Allocation for MPI
`and
`S.H Russ
`Flachs
`Robinson
`
`Heckel
`
`An Adaptive Approach to Data Placement
`D.K Lowenthal and G.R An4rews
`
`Complete Parallelization of Computations Integration of Data Partitioning and Functional
`Parallelism for Dynamic Data Structures
`Browne
`Banerfee and
`
`Keynote Address MPPs versus Clusters
`Speaker Charles
`Seitz Myricom Inc
`
`viii
`
`281
`
`286
`
`292
`
`302
`
`309
`
`314
`
`320
`
`325
`
`327
`
`332
`
`339
`
`344
`
`349
`
`354
`
`362
`
`Petitioner IBM – Ex. 1069, p. 9
`
`

`
`Session 10 Communication II
`
`Chair Louise Moser
`
`University of California Santa Barbara
`
`Generating Realignment-Based Communication for HPF Programs
`Tamura and
`Kamachj
`Kusano
`Seo
`Suehiro
`
`Sakon
`
`for Virtual Memory-Mapped Communication
`Software Support
`Felten and
`Dubnicki
`Li
`Iftode
`How to Optimize Residual Communications
`Rand riamaro and
`Dion
`Robert
`
`Comparative Study of Methods for Time-Deterministic Message Delivery in
`Multiprocessor Architecture
`Jonsson and
`Vasell
`ECO Efficient Collective Operations for Communication on Heterogeneous Networks
`B.B Lowekamp and
`Beguelin
`Software Techniques for Improving MPP Bulk-Transfer Performance
`E.A Brewer
`Gauthier
`Fox and
`Schuett
`
`Session 11
`
`Algorithms Implementation
`
`Chali- Mikhail Atallah
`
`Purdue University
`
`Parallel Algorithms for Image Enhancement and Segmentation by Region Growing with
`an Experimental Study
`D.A Bader
`JáJá
`
`Harwood and L.S Davis
`
`The Chessboard Distance Transform and the Medial Axis Transform are Interchangeable
`Y-H Lee and S-f Horng
`
`Parallel Algorithms for Image Processing Practical Algorithms with Experiments
`Bäumker and
`Dittrich
`
`Study of Scalable Declustering Algorithms for Parallel Grid Files
`Moon
`Acharya and
`
`Saltz
`
`Inference
`Parallel Algorithm for Text
`S.M Harabagiu and D.I Moldovan
`
`Direct Block-Five-Diagonal System Solver
`
`for the VLSI Parallel Model
`
`VajterJic
`
`Session 12
`
`Chair John Gustafson
`
`Pertormance Evaluation and Prediction
`Ames Laboratory
`
`Efficient Execution of Parallel Applications in Muitiprogrammed Multiprocessor
`
`Systems
`K.K Yue and D.J Lilf
`
`The Relation of Scalability and Execution Time
`X-H Sun
`
`through Self-Tuning of Processor Allocation
`Maximizing Speedup
`TD Nguyen
`Vaswani and
`Zahorjan
`Profiling System for an HPF Compiler
`Profiling Optimized Code
`Kaneshiro and
`Shindo
`
`ix
`
`364
`
`372
`
`382
`
`392
`
`399
`
`406
`
`414
`
`424
`
`429
`
`434
`
`441
`
`446
`
`448
`
`457
`
`463
`
`469
`
`Petitioner IBM – Ex. 1069, p. 10
`
`

`
`Toward Symbolic Performance Prediction of Parallel Programs
`Fahringer
`
`Performance Prediction with Benchmaps
`Toledo
`
`Industrial Track
`
`Invited Presentations
`
`Organizer John
`
`Antonio
`
`Texas Tech University
`
`Session-I Parallel Architectures
`Performance
`
`Implementation Programming and
`
`Chair John
`
`Antonio
`
`Texas Tech University
`
`Cray Research Inc
`Communication Latency and Bandwidth on the Cray Research T3E
`FW Chism
`IBM SystemI39O Division
`
`Overview of IBM SystemI39O Parallel Sysplex
`System
`J.M Nick i-I Chung and N.S Bowen
`
`Litton Guidance and Control Systems Inc
`
`Commercial Parallel Processing
`
`Implementing Parallel Processing in Rugged Embeddable Environment
`A.L Smeyne
`
`Mercury Computer Systems Inc
`
`Planned Direct Transfers
`
`Vichniac
`
`Isenstein
`
`Programming Model for Real-Time Applications
`Lund and
`Pool
`
`Session-Il Networking and Distributed Computing
`Chair Richard
`Rome Laboratory
`
`Metzger
`
`Centre for Development of Advanced Computing
`
`DS-Link over Fiber
`
`Abhyankar
`
`Degwekar
`
`High-Speed Interconnect
`and
`Karandikar
`
`for Cluster Computing
`
`Electronics and Telecommunications Research Institute
`
`Multiprocessor Server with New Highly Pipelined Bus
`Ki K-W Rim and S-W Kim
`W-J Hahn
`
`Tandem Computers Incorporated
`
`Performance Modeling of ServerNetTM Topologies
`Horst
`Avrcsky
`Wilkinson
`Jewett
`
`Watson
`
`Young and
`
`Cwzrungham
`
`Virtual Computer Corporation
`
`Distributed Virtual Computing
`Thornburg and
`Schewel
`
`Casselinan
`
`474
`
`479
`
`487
`
`488
`
`496
`
`502
`
`507
`
`512
`
`518
`
`524
`
`Petitioner IBM – Ex. 1069, p. 11
`
`

`
`Session 13
`Synchronization Virtual Memory and Illuntime System Support
`Chair Francine Berman University of California San Diego
`
`CoCheck Checkpointing
`Steliner
`
`and Process Migration for MPI
`
`Tulip
`
`Portable Run-Time System for Object-Parallel Systems
`Beckman and
`Gannon
`
`Virtual Memory Model for Parallel Supercomputers
`VL.M Reis and LD Scherson
`
`Partitioning Programming Environment for Novel Parallel Architecture
`Kress and
`Becker
`Herz
`Hartenstein
`Nageldinger
`
`An Integrated Synchronization
`and Consistency Protocol
`High-Level Parallel Programming Language
`M.C Rinard
`
`for the Implementation of
`
`Implementation and Evaluation of Prefetching in the Intel Paragon Parallel File System
`Choudhary and
`Arunachalam
`Ruilman
`
`Session 14
`
`Chair Oscar
`
`Arrays and Hypercubes
`Ibarra University of California Santa Barbara
`
`Permutation in the Hypercube by Two Sets of Edge-Disjoint Paths
`Routing
`Q-P Gu and
`Tamaki
`
`Determining Asynchronous Acyclic Pipeline Execution Times
`Donaldson and .1 Ferrante
`
`Distributing Tokens on Hypercube without Error Accumulation
`B.S Chiebus J.D.P Rolim and
`Slutzki
`
`On Some Global Operations in Faulty SIMD Hypercubes
`Sen gupta and C.S Raghavendra
`An Improved Approximation Algorithm for Scheduling Task Trees on Linear Arrays
`H.K Tadepalli and E.L Lloyd
`
`Mapping Linear Recurrences onto Systolic Arrays
`Rajan and R.K Shyamasundar
`Kazerouni
`
`Session 15
`
`Mathematical Methods
`
`Chair Dan Moldovan
`
`Southern Methodist University
`
`Jacobi-like Algorithms for Eigenvalue Decomposition of Real Normal Matrix Using
`Real Arithmetic
`B.B Zhou and R.P Brent
`
`An Element-Based Concurrent Partitioner for Unstructured Finite Element Meshes
`H.Q Ding and R.D Ferraro
`
`Analysis of the Numerical Effects of Parallelism on
`W.E Hart
`Baden R.K Belew and
`Kohn
`Compiling MATLAB Programs to ScaLAPACK Exploiting Task and Data Parallelism
`Ramaswamy
`Hodges IV and
`Banerjee
`
`Parallel Genetic Algorithm
`
`Mapping Techniques for Parallel Evaluation of Chains of Recurrences
`Zima K.R Vadivelu and T.L Casavant
`
`xi
`
`526
`
`532
`
`537
`
`544
`
`549
`
`554
`
`561
`
`568
`
`573
`
`579
`
`584
`
`591
`
`593
`
`601
`
`606
`
`613
`
`620
`
`Petitioner IBM – Ex. 1069, p. 12
`
`

`
`Performance of Asynchronous Linear Iterations with Random Delays
`Dubois
`Moga and
`
`For Massive Number of Massively Parallel Machines
`Panel
`What are the Target Applications Who are the Target Users and
`What New RD is Needed to Hit
`the TargeV
`Moderator Howard Jay Siegel
`Purdue University
`
`Panelists William Farmer
`Integrated Computing Engines Inc
`Richard Freund NRaD
`
`Mark Furtney Cray Research
`Paul Mess ma Caltech
`
`Inc
`
`Lionel
`
`Charles
`
`Marc Snir
`
`Ni National Science Foundation
`
`Seitz Myricom Inc
`IBM T.J Watson Research Center
`
`Keynote Address
`Architecture
`
`Clusters for Commercial Computing An Invisible
`
`Speaker Gregory
`
`Pfister
`
`IBM Server Group Austin
`
`Session 16
`Interconnection Networks
`Chair D.K Panda Ohio State University
`
`for Deadlock-Free Routing
`Generic Methodologies
`Park and D.P Agrawal
`Partitionability of the Multistage Interconnection Networks
`
`Chang
`
`On Embedding Various Networks into the Hypercube Using Matrix Transformations
`l-iamdi and
`Song
`
`Optimal Subcube Fault Tolerance in Circuit-Switched Hypercube
`B.A Izadi and
`
`Ozgllner
`
`Fault-Tolerant Ring Embedding in Star Graphs
`Y-C Tseng S-H Chang and J-P Sheu
`An Optical Interconnect Model for k-ary n-cube Wormhole Networks
`and TM Pinkston
`Raksapatcharawong
`
`Session 17
`Bus-Based Algorithms
`Chair Sartaj Sahni
`
`University of Florida
`
`Fault-Tolerant Multiple Bus Networks for Fan-In Algorithms
`Vaidyanathan and
`Nadella
`Coping with Sparse Inputs on Enhanced Meshes
`COMMON CRCW Buses
`Damaschke
`
`Semigroup Computation with
`
`An Optimal Algorithm for the Angle-Restricted All Nearest Neighbor Problem on the
`Reconfigurable Mesh
`Nakano and Olariu
`
`xii
`
`625
`
`631
`
`636
`
`638
`
`644
`
`650
`
`655
`
`660
`
`666
`
`674
`
`682
`
`687
`
`Petitioner IBM – Ex. 1069, p. 13
`
`

`
`Parallel Algorithms Using Unreliable Broadcasts
`Matthews and
`Martel
`
`Efficient Algorithms for the Hough Transform on Arrays with Reconfigurable
`Optical Buses
`Pave and
`
`Aki
`
`Integer and Floating Point Matrix-Vector Multiplication on the Reconfigurable Mesh
`J.L Trahan C-M Lu and
`Vaidyanathan
`
`Session 18
`
`Chair
`
`Image and Radar Processing
`Martinez MIT Lincoln Laboratory
`
`Some Image Processing Algorithms on RAP with Wider Bus Networks
`S-S Lee S-J Horng H-R Tsai and Y-H Lee
`Parallel Synthetic Aperture Radar Processing on Workstation Networks
`P.G Meisi M.R ito and LG Cumming
`The Evolution of Massively Parallel Vision System for Real-Time Automotive Image
`
`Processing
`
`Broggi
`2D Object Recognition on Reconfigurable Mesh
`Guerra
`
`Space-Time Adaptive Processing on the Mesh Synchronous Processor
`IS McMahon and
`Teitelbaum
`An Experimental Study of Input/Output Characteristics of NASA Earth and Space
`Sciences Applications
`M.R Berry and TA El-Ghazawi
`
`Session 19
`
`Chair Kang
`
`Special-Purpose Applications
`University of Michigan Ann Arbor
`
`Shin
`
`Bitonic Sorting on Benel Networks
`B.M Gocal and K.E Batcher
`
`Designing Adaptable Real-Time Fault-Tolerant Parallel Systems
`C.E Moron
`
`Improving Memory Performance for Indirect Accesses
`J.D Allen and D.E Schimmel
`
`on SIMID Computers
`
`New Approach to Pipeline FF1 Processor
`He and
`Torkelson
`
`Implementation of SliM Array Processor
`tiM Chang M.H Sunwoo and T-H Cho
`Temporal Characterization of Demands for Data Movement on Parallel Programs
`Jordan and
`Alaghband
`Rodriguez
`
`Session 20
`
`Communication ill
`
`Chair Jean-Luc Gaudiot University of Southern california
`
`Broadcasting Multiple Messages in the Multiport Model
`Bar-Noy and C-T Ho
`
`xlii
`
`692
`
`697
`
`702
`
`708
`
`716
`
`724
`
`729
`
`734
`
`741
`
`749
`
`754
`
`759
`
`766
`
`771
`
`776
`
`781
`
`Petitioner IBM – Ex. 1069, p. 14
`
`

`
`The Necessary Conditions for Cbs-Type Noablocking Multicast Networks
`Yang and G.M Masson
`
`Class of Interconnection Networks for Multicasting
`
`Yang
`Performance Prediction of PVM Programs
`M.R Steed and M.J Clement
`
`Algorithms for All-to-All Personalized Exchange in 2D and 3D Tori
`V-f Suh and
`Yalamanchili
`
`Generalized Theory for Deadlock-Free Adaptive Wormhole Routing and its Application
`to Disha Concurrent
`A.K Venkatramani TM Pinkston and
`
`Duato
`
`Clusters and Domain Decomposition
`Session 21
`Chair Susamma Barua California State University Fullerton
`
`Efficient Run-Time Support for Irregular Task Computations with Mixed Granularities
`Fu and
`Yang
`New Technique for 3-D Domain Decomposition
`
`on Multicomputers which Reduces
`
`Message-Passing
`Gil andA Wagner
`Application Load Imbalance on Parallel Processors
`Govindan and M.A Franklin
`Native ATM Application Programmer Interface Testbed for Cluster-Based Computing
`P.W Dowd TM Carrozzi F.A Pellegrino andA.X Chen
`SWEB Towards
`Scalable World Wide Web Server on Multicomputers
`Holmedahi and OH Ibarra
`Andresen
`Yang
`of Irregular Problems Using High-Level Actor Language
`Parallel Implementations
`Kim and G.A Agha
`R.B Panwar
`
`Additional Papers
`
`Author Index
`
`789
`
`796
`
`803
`
`808
`
`815
`
`823
`
`831
`
`836
`
`843
`
`850
`
`857
`
`863
`
`899
`
`xiv
`
`Petitioner IBM – Ex. 1069, p. 15