International Conference on Parallel Processing (ICPP '85), University Park, PA, USA, August 1985. IEEE Computer Society Press, 1985

Session 1a: Parallel Algorithms -I

• 
  Albert G. Greenberg, Udi Manber: A Probabilistic Pipeline Algorithm for K-Selection on the Tree Machine. 1-5
• 
  Edward W. Felten, Steve W. Otto, Scott Karlin: The Traveling Salesman Problem on a Hypercubic, MIMD Computer. 6-10
• 
  Larry Rudolph, William L. Steiger: Subset Selection in Parallel. 11-13
• 
  Richard C. Paige, Clyde P. Kruskal: Parallel Algorithms for Shortest Path Problems. 14-20

Session 1b: Vector/Array Processing

• 
  Eugene D. Brooks III: Performance of the Butterfly Processor-Memory Interconnection in a Vector Environment. 21-24
• 
  Daniel A. Reed, Merrell L. Patrick: Iterative Solution of Large, Sparse, Linear Systems on a Static Data Flow Architecture: Performance Studies. 25-32
• 
  Wilfried Oed, Otto Lange: On the Effective Bandwidth of Interleaved Memories in Vector Processor Systems. 33-40
• 
  Abhiram G. Ranade: Interconnection Networks And Parallel Memory Organizations For Array Processing. 41-47

Session 1c: Problem Mapping and Scheduling

• 
  H. Barad, Dan I. Moldovan: A Systems Approach to Mapping a Karhunen-Loeve Transform into a Systolic Array. 48-55
• 
  Manoel Fernando Tenorio, Dan I. Moldovan: Mapping Production Systems into Multiprocessors. 56-62
• 
  Lionel M. Ni, Ching-Farn Eric Wu: Design Trade-offs for Process Scheduling in Tightly Coupled Multiprocessor Systems. 63-70

Session 2a: Parallel Architectures

• 
  John C. Peterson, Jesus O. Tuazon, Don Lieberman, Moshe Pniel: The Mark III Hypercube-Ensemble Concurrent Computer. 71-73
• 
  Mary Diane Palmer Leland: On the Power of the Augmented Data Manipulator Network. 74-78
• 
  Renben Shu, Peter C. Patton: BCA : A Bus Connected Architecture. 79-88
• 
  Arndt Bode, Gerhard Fritsch, Wolfgang Händler, Wolfgang Henning, Fridolin Hofmann, Jens Volkert: Multi-Grid oriented Computer Architecture. 89-95

Session 2b: Systolic Systems

• 
  Mark A. Shell, Donald W. Bouldin, Paul D. Manhardt: Design and Implementation of a VLSI Systolic Array for Solving Nonlinear Partial Differential Equations. 96-98
• 
  Allan L. Fisher: Memory and Modularity in Systolic Array Implementations. 99-101
• 
  Kai Hwang, Zhiwei Xu: Remps: A Reconfigurable Multiprocessor for Scientific Supercomputing. 102-111
• 
  Amos Fiat, Adi Shamir, Ehud Y. Shapiro: Polymorphic Arrays: An Architecture for a Programmable Systolic Machine. 112-117

Session 2c: Logic Programming

• 
  Ehud Y. Shapiro, Shmuel Safra: Fast Multiway Merge Using Destructive Operation. 118-122
• 
  Guo-Jie Li, Benjamin W. Wah: MANIP-2 : A Multicomputer Architecture for Evaluating Logic Programs. 123-130
• 
  Jim A. Crammond: A Comparative Study of Unification Algorithms For Or-Parallel Execution of Logic Languages. 131-138

Session 3a: Operating System Problems

• 
  Ahmed K. Ezzat, Rakesh Agrawal: Making Oneself Known in a Distributed World. 139-142
• 
  Heinz Mühlenbein, S. Warhaut: Concurrent Mulitgrid Methods in an Object-Oriented Environment: A Case Study. 143-146
• 
  Steven P. Levitan: Evaluation Criteria for Communication Structures in Parallel Architectures. 147-154
• 
  Ariel J. Frank, Larry D. Wittie, Arthur J. Bernstein: Maintaining Weakly-Consistent Replicated Data on Dynamic Groups of Computers. 155-162
• 
  Mehdi R. Zargham, Ralph D. Purcell: A Protocol for Load Balancing on CSMA Networks. 163-165
• 
  Marsha J. Berger, Shahid H. Bokhari: A Partitioning Strategy for PDEs Across Multiprocessors. 166-170

Session 3b: Parallel Algorithms/ Simulation

• 
  Mark A. Yoder, Leah H. Jamieson: Simulation of a Word Recognition System on Two Parallel Arcitectures. 171-179
• 
  Clyde P. Kruskal, Larry Rudolph, Marc Snir: The Power of Parallel Prefix. 180-185
• 
  Shaunak Pawagi, I. V. Ramakrishnan: Parallel Updates of Graph Properties in Logarithmic Time. 186-193
• 
  Ten-Hwang Lai, Alan P. Sprague: Performance of Parallel Branch-and-Bound Algorithms. 194-201

Session 3c: Parallel Computation

• 
  David Lefkovitz, Roger Y. Lee, Philip R. Nelson: An Embedded Software Design Simulator for ADA Multitasking. 202-209
• 
  Alan M. Schwartz, Michael C. Loui: Dictionary Machines on Cube-Class Networks. 210-216
• 
  Bruce P. Lester: Analysis of Firing Rates in Petri Nets Using Linear Algebra. 217-224
• 
  Sang Hyun Han: Exploitation of Parallelism in Array Loopback Test. 225-231

Session 4a: languages for Parallel Processing

• 
  James T. Kuehn, Howard Jay Siegel: Extensions to the C Programming Language for SIMD/MIMD Parallelism. 232-235
• 
  Christian Fraboul, Nourredine Hifdi: Expressing and Exploiting Parallelism on an Experimental MIMD System. 236-238
• 
  Mark R. Headington, Arthur E. Oldehoeft: Open Predicate Path Expressions and their Implementation in Highly Parallel Computing Environments. 239-246
• 
  Hungwen Li, Ching-Chy Wang, Mark A. Lavin: Structured Process: A New Language Attribute for Better Interaction of Parallel Architecture and Algorithm. 247-254
• 
  David Gelernter, Nicholas Carriero, Sarat Chandran, Silva Chang: Parallel Programming in Linda. 255-263

Session 4b: Memory Management

• 
  Mary E. Mace, Robert A. Wagner: Globally Optimum Selection of Memory Storage Patterns. 264-271
• 
  Bruce M. Bigler, Stephen J. Allan, R. R. Oldehoeft: Parallel Dynamic Storage Allocation. 272-275
• 
  Jean Marc Frailong, William Jalby, Jacques Lenfant: XOR-Schemes: A Flexible Data Organization in Parallel Memories. 276-283

Session 4c: Numeric Processing

• 
  David Barkai, K. J. M. Moriarty, Claudio Rebbi: A Modified Conjugate Gradient Solver for Very Large Systems. 284-290
• 
  Ravi Mehrotra, Edward F. Gehringer: Superlinear Speedup Through Randomized Algorithms. 291-300
• 
  Miron Livny, Udi Manber: Shift Arithmetic on a Token Ring Network. 301-304
• 
  Carlos Cardelino, Pin-Yee Chen: A New Parallel Algorithm for Solving a Complex Function F(Z)=0. 305-311
• 
  Jack S. Walicki, M. Andrews: Parallel Implementation of the LMS Algorithm. 312-316

Session 5a: Interconnection Networks - I

• 
  Chin-Tau A. Lea: A Load-Sharing Banyan Network. 317-324
• 
  Takeshi Kumagai, Kazuo Ikegaya: The Two-Dimensional Inverse Omega Network. 325-327
• 
  Anujan Varma, C. S. Raghavendra: Realization of Permutations on Generalized Indra Networks. 328-333
• 
  Tse-Yun Feng, Wei Young: An O(log²N) Control Algorithm. 334-340

Session 5b: Data Flow

• 
  K. Culick: Towards a Theory of Control-Flow and Data-Flow Algorithms. 341-348
• 
  Yang-Chang Hong, Thomas H. Payne, Le Baron O. Ferguson: An Architecture for a Dataflow Multiprocessor. 349-355
• 
  Sharilyn A. Thoreson, Arlen N. Long: A Feasibility Study of a Memory Hierarchy in a Data Flow Environment. 356-360

Session 5c: Parallel Algiorithms

• 
  A. Yavuz Oruç, M. Yaman Oruç: On Testing Permutation Network Isomorphisms. 361-368
• 
  Heonshik Shin, Miroslaw Malek: Parallel Garbage Collection with Associative Tag. 369-375
• 
  I. V. Ramakrishnan, Peter J. Varman: An Optimal Family of Matrix Multiplication Algorithms on Linear Arrays. 376-383

Session 6a: Interconnection Networks

• 
  A. J. Field, M. D. Cripps: Self-Clocking Networks. 384-387
• 
  Alexander A. Sawchuk, Bob K. Jenkins, C. S. Raghavendra, Anujan Varma: Optical Interconnection Networks. 388-392
• 
  Charles E. Leiserson: Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing. 393-402
• 
  Nathaniel J. Davis IV, William Tsun-Yuk Hsu, Howard Jay Siegel: Fault Location in Distributed Control Interconnection Networks. 403-410

Session 6b: Numeric Computing

• 
  Mikhail J. Atallah, Michael T. Goodrich: Efficient Parallel Solutions to Geometric Problems. 411-417
• 
  Peter R. Cappello: A Mesh Automaton for Solving Dense Linear Systems. 418-425
• 
  Tsutomu Hoshino, Takeshi Kamimura, Toshihiro Iida, Tomonori Shirakawa: Parallelized ADI Scheme Using GECR (Gauss-Elimination-Cyclic-Reduction) Method and Implementation of Navier-Stokes Equation in the PAX computer. 426-433

Session 6c: Parallel Programming

• 
  Guo-Jie Li, Benjamin W. Wah: Systolic Processing for Dynamic Programming Problems. 434-441
• 
  Henry G. Dietz, David Klappholz: Refined C: A Sequential Language for Parallel Programming. 442-449
• 
  Ron Cytron: Useful Parallelism in a Multiprocessing Environment. 450-457

Session 7a: Network Performance

• 
  Nian-Feng Tzeng, Pen-Chung Yew, Chuan-Qi Zhu: The Performance of a Fault-Tolerant Multistage Interconnection Network. 458-465
• 
  Tan Hsiao-Nan: RSESS Interconnection Network. 466-473
• 
  Anujan Varma, C. S. Raghavendra: Performance Analysis of a Redundant-Path Interconnection Network. 474-479

Session 7b: Aspects of Parallel Systems

• 
  Haim E. Mizrahi, Israel Koren: Evaluating the Cost-Effectiveness of Switches in Processor Array Architectures. 480-487
• 
  Lawrence Snyder: An Inquiry into the Benefits of Multigauge Parallel Computation. 488-492
• 
  Robert M. Lougheed, David L. McCubbrey: Multi-Processor Architectures For Machine Vision and Image Analysis. 493-497
• 
  Bernard L. Menezes, Roy M. Jenevein: KYKLOS : A Linear Growth Fault-Tolerant Interconnection Network. 498-502

Session 7c: Data Flow -II

• 
  V. Ashok, Neelam Soundararajan, Roger L. Costello: : Distributed Discrete Event Simulation using Dataflow. 503-510
• 
  Michael L. Campbell: Static Allocation for a Data Flow Multiprocessor. 511-517
• 
  E. Levin: Suitability of a Data Flow Architecture for Problems Involving Simple Operations on Large Arrays. 518-520

Session 8a: Performance Measurement

• 
  Trevor N. Mudge, Humoud B. Al-Sadoun: A Semi-Markov Model for the Performance of Multiple-Bus Systems. 521-530
• 
  William R. Crowther, J. Goodhue, E. Starr, Robert H. Thomas, W. Milliken, T. Blackadar: Performance Measurements on a 128-Node Butterfly Parallel Processor. 531-540
• 
  Elizabeth Williams, Frank Bobrowicz: Speedup Predictions on Large Scientific Parallel Programs on Cray X MP Like Architectures. 541-543

Session 8b: Logic Programming / Production Systems

• 
  Shimon Edelman, Ehud Y. Shapiro: Quadtrees in Concurrent PROLOG. 544-551
• 
  Hisao Tamaki: A Distributed Unification Scheme for Systolic Logic Programs. 552-559
• 
  G. Jack Lipovski, Manuel V. Hermenegildo: B-Log: A Branch and Bound Methodology for the Parallel Execution of Logic Programs. 560-567
• 
  Toru Ishida, Salvatore J. Stolfo: Towards the Parallel Execution of Rules in Production System Programs. 568-575

Session 8c: Parallel Systems - II

• 
  Randy H. Steinvorth, G. F. Taylor, Jack F. McDonald, T. Hunter: An Architecture for a Video Rate Fuzzy Golay Processor. 576-582
• 
  Nobuhiko Koike, Kenji Ohmori: MAN-YO : A Special Purpose Parallel Machine for Logic Design Automation. 583-590
• 
  Chita R. Das, Laxmi N. Bhuyan: Reliability Simulation of Multiprocessor Systems. 591-598
• 
  Martin T. Hagan, Howard B. Demuth, Paul Hartono Singgih: Parallel Signal Processing Research on the HEP. 599-606

Session 9a: Expressing Parallelism

• 
  Gyungho Lee, Clyde P. Kruskal, David J. Kuck: The Effectiveness of Automatic Restructuring on Nonnumerical Programs. 607-613
• 
  Alexandru Nicolau: Uniform Parallelism Exploitation in Ordinary Programs. 614-618
• 
  Aloysius K. Mok: A Graph-Based Computation Model for Real-Time Systems. 619-623
• 
  James C. Browne: Formulation and Programming of Parallel Computations: A Unified Approach. 624-631
• 
  Robert E. Strom, Shaula Yemini: Synthesizing Distributed and Parallel Programs through Optimistic Transformations. 632-642

Session 9b: Parallell Systems - II

• 
  Jouko O. Viitanen, Pertti Vanni: The TAMIPS Multiprocessor. 643-645
• 
  Michel Dubois: A Cache-Based Multiprocessor with High Efficiency. 646-648
• 
  Lee D. Coraor, Paul T. Hulina: A Reconfigurable Multiprocessor. 649-651
• 
  Wolfgang Händler, Erik Maehle, Klaus Wirl: Dirmu Multiprocessor Configurations. 652-656
• 
  Ping-Sheng Tseng, Kai Hwang, Viktor K. Prasanna: A VLSI-Based Multiprocessor Architecture for Implementing Parallel Algorithms. 657-664
• 
  James C. Browne: Characterization of Parallel Architecture. 665
• 
  Jesus O. Tuazon, John C. Peterson, Moshe Pniel, Don Lieberman: Caltech/JPL MARK II Hypercube Concurrent Processor. 666-673
• 
  Ran Ginosar, Dwight D. Hill: Design and Implementation of Switching Systems for Parallel Processors. 674-680
• 
  Creve Maples: Pyramids, Crossbars and Thousands of Processors. 681-688
• 
  William Robertson, D. Pincock, David N. Swingler: A Reconfigurable Architecture for Digital Time Domain Beamforming. 689-696

Session 10a: Mesh-Structured Systems

• 
  Russ Miller, Quentin F. Stout: Varying Diameter and Problem Size in Mesh-Connected Computers. 697-699
• 
  Laxmikant V. Kalé: Lattice-Mesh: A Multi-Bus Architecture. 700-702
• 
  P. S. Gopalakrishnan, I. V. Ramakrishnan, Laveen N. Kanal: Computing Tree Functions on Mesh-Connected Computers. 703-710
• 
  P. S. Gopalakrishnan, I. V. Ramakrishnan, Laveen N. Kanal: An Efficient Connected Components Algorithm on a Mesh-Connected Computer. 711-714
• 
  David A. Carlson: Performing Tree and Prefix Computations on Modified Mesh-Connected Parallel Computers. 715-718

Session 10b: Problem Mapping Techniques

• 
  Tsair-chin Lin, Dan I. Moldovan: Tradeoffs in Mapping Algorithms to Array Processors. 719-726
• 
  Quentin F. Stout: Tree-Based Graph Algorithms for Some Parallel Computers. 727-730
• 
  Francine Berman, Michael A. Goodrich, Charles Koelbel, W. J. Robison III, Karen Showell: Prep-P: A Mapping Preprocessor for CHiP Architectures. 731-733
• 
  Woei Lin, Chuan-lin Wu: Design of Configuration Algorithms of Commonly-Used Topologies for a Multiprocessor : STAR. 734-741

Session 10c: Systolic Systems

• 
  David Y. Y. Yun, Chang Nian Zhang: A Programmable Systolic Array for Arithmetic Operations in Galois Fields. 742-747
• 
  Anwar Khurshid, P. David Fisher: Algorithm Implementation on Reconfigurable Mixed Systolic Arrays. 748-755
• 
  Karel Culik II, Sheng Yu: Translation of Systolic Algorithms between Systems of Different Topology. 756-763

Session 11a: The IBM Research Parallel Processor

• 
  Gregory F. Pfister, William C. Brantley, David A. George, Steve L. Harvey, Wally J. Kleinfelder, Kevin P. McAuliffe, Evelin S. Melton, V. Alan Norton, Jodi Weiss: The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture. 764-771
• 
  V. Alan Norton, Gregory F. Pfister: A Methodology for Predicting Multiprocessor Performance. 772-781
• 
  William C. Brantley, Kevin P. McAuliffe, Jodi Weiss: RP3 Processor-Memory Element. 782-789
• 
  Gregory F. Pfister, V. Alan Norton: "Hot Spot" Contention and Combining in Multistage Interconnection Networks. 790-797

Session 11b: Fault Tolerance and Reliability

• 
  M. Ümit Uyar, Anthony P. Reeves: Fault Reconfiguration in a Distributed MIMD Environment with a Multiusage Network. 798-806
• 
  Chita R. Das, Laxmi N. Bhuyan: Computation Availability of Multiple-Bus Multiprocessors. 807-813
• 
  Prathima Agrawal: RAFT: A Recursive Algorithm for Fault Tolerance. 814-821

Session 12a: Functional / Numeric Programming

• 
  Robert H. Halstead Jr., Juan R. Loaiza: Exception Handling in Multilisp. 822-830
• 
  Paul Hudak, Benjamin Goldberg: Efficient Distributed Evaluation of Functional Programs Using Serial Combinators. 831-839
• 
  David Hemmendinger: Lazy Evaluation and Cancellation of Computations. 840-842
• 
  S. Lakshmivarahan, Sudarshan K. Dhall: New Parallel Algorithms for Solving First-Order and Certain Classes of Second-Order Linear Recurrences. 843-845

Session 12b: Sorting

• 
  John M. Marberg, Eli Gafni: Sorting and Selection in Multi-Channel Broadcast Networks. 846-850
• 
  Yijie Han: A Family of Parallel Sorting Algorithms. 851-853
• 
  Sai Choi Kwan, Jean-Loup Baer, G. Zick, T. Snyder: Parallel Tag-Distribution Sort. 854-861
• 
  Dharma P. Agrawal, P. Ja-SongLeu, Cai TaoNie: Parallel Sorting on the B-HIVE Machine. 862-864
• 
  Pin-Yee Chen, Miguel Nussbaum: Sorting with Systolic Architecture. 865-868