ACM Symposium on Parallel Algorithms and Architectures

The Digital Librarian's Digital Library

DOCIS Documents in Computing and Information Science

Home >> Journals and Conference Proceedings

ACM Symposium on Parallel Algorithms and Architectures

2005

Selfish routing with incomplete information
by: Martin Gairing, Burkhard Monien, Karsten Tiemann
Irrigating ad hoc networks in constant time
by: Devdatt P. Dubhashi, C. Johansson, Olle Häggström, Alessandro Panconesi, Mauro Sozio
On competitive online read-many parallel disks scheduling
by: Rahul Shah, Peter J. Varman, Jeffrey Scott Vitter
Autonomous virtual mobile nodes
by: Shlomi Dolev, Seth Gilbert, Elad Schiller, Alexander A. Shvartsman, Jennifer L. Welch
Value-maximizing deadline scheduling and its application to animation rendering
by: Eric Anderson, Dirk Beyer 0002, Kamalika Chaudhuri, Terence Kelly, Norman Salazar, Cipriano Santos, Ram Swaminathan, Robert Endre Tarjan, Janet L. Wiener, Yunhong Zhou
Concurrent cache-oblivious b-trees
by: Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Bradley C. Kuszmaul
Scheduling malleable tasks with precedence constraints
by: Klaus Jansen, Hu Zhang
Decentralized algorithms using both local and random probes for P2P load balancing
by: Krishnaram Kenthapadi, Gurmeet Singh Manku
Randomized qeue management for DiffServ
by: Nir Andelman
Efficient algorithms for verifying memory consistency
by: Chaiyasit Manovit, Sudheendra Hangal
Traffic engineering of management flows by link augmentations on confluent trees
by: Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S. Mirrokni, Seffi Naor, Baruch Schieber
An adaptive power conservation scheme for heterogeneous wireless sensor networks with node redeployment
by: Ioannis Chatzigiannakis, Athanasios Kinalis, Sotiris E. Nikoletseas
Oblivious routing on geometric networks
by: Costas Busch, Malik Magdon-Ismail, Jing Xi
Radio communication in random graphs: extended abstract
by: Robert Elsässer, Leszek Gasieniec
Dynamic circular work-stealing deque
by: David Chase, Yossi Lev
Dynamic page migration with stochastic requests
by: Marcin Bienkowski
Collaborate with strangers to find own preferences
by: Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-Shamir, Mark R. Tuttle
A forward planning situated protocol for data propagation in wireless sensor networks based on swarm intelligence techniques
by: Ioannis Chatzigiannakis, Sotiris E. Nikoletseas
Parallelizing time with polynomial circuits
by: Ryan Williams
Parallel scheduling of complex dags under uncertainty
by: Grzegorz Malewicz
The expansion and mixing time of skip graphs with applications
by: James Aspnes, Udi Wieder
Lexicographic QoS scheduling for parallel I/O
by: Ajay Gulati, Peter J. Varman
A space lower bound for name-independent compact routing in trees
by: Kofi A. Laing, Rajmohan Rajaraman
Is partial quantum search of a database any easier?
by: Lov K. Grover, Jaikumar Radhakrishnan
Fast construction of overlay networks
by: Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, Yitong Yin
Finding effective support-tree preconditioners
by: Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan Leung Maverick Woo
Windows scheduling of arbitrary length jobs on parallel machines
by: Amotz Bar-Noy, Richard E. Ladner, Tami Tamir, Tammy VanDeGrift
Peer-to-peer networks based on random transformations of connected regular undirected graphs
by: Peter Mahlmann, Christian Schindelhauer
Processor efficient parallel matching
by: Piotr Sankowski
Adversarial contention resolution for simple channels
by: Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson
Constant density spanners for wireless ad-hoc networks
by: Kishore Kothapalli, Christian Scheideler, Melih Onus, Andréa W. Richa
On distributed smooth scheduling
by: Ami Litman, Shiri Moran-Schein
Name independent routing for growth bounded networks
by: Ittai Abraham, Dahlia Malkhi
Broadcasting on networks of workstations
by: Samir Khuller, Yoo Ah Kim, Yung-Chun (Justin) Wan
Admission control to minimize rejections and online set cover with repetitions
by: Noga Alon, Yossi Azar, Shai Gutner
A truthful mechanism for the non-utilitarian minimum radius spanning tree problem
by: Guido Proietti, Peter Widmayer
Weighted distributed hash tables
by: Christian Schindelhauer, Gunnar Schomaker
Randomization does not reduce the average delay in parallel packet switches
by: Hagit Attiya, David Hay
Coloring unstructured radio networks
by: Thomas Moscibroda, Roger Wattenhofer
A segmented parallel-prefix VLSI circuit with small delays for small segments
by: Bradley C. Kuszmaul
Using elimination to implement scalable and lock-free FIFO queues
by: Mark Moir, Daniel Nussbaum, Ori Shalev, Nir Shavit

2004

Balanced graph partitioning
by: Konstantin Andreev, Harald Räcke
Consistent and compact data management in distributed storage systems
by: Baruch Awerbuch, Christian Scheideler
Writing-all deterministically and optimally using a non-trivial number of asynchronous processors
by: Dariusz R. Kowalski, Alexander A. Shvartsman
Cache-oblivious shortest paths in graphs using buffer heap
by: Rezaul Alam Chowdhury, Vijaya Ramachandran
DCAS is not a silver bullet for nonblocking algorithm design
by: Simon Doherty, David Detlefs, Lindsay Groves, Christine H. Flood, Victor Luchangco, Paul A. Martin, Mark Moir, Nir Shavit, Guy L. Steele Jr.
Improved combination of online algorithms for acceptance and rejection
by: David P. Bunde, Yishay Mansour
Expansion properties of (secure) wireless networks
by: Alessandro Panconesi, Jaikumar Radhakrishnan
Efficient orchestration of sub-word parallelism in media processors
by: John Oliver, Venkatesh Akella, Frederic T. Chong
Pagoda: a dynamic overlay network for routing, data management, and multicasting
by: Ankur Bhargava, Kishore Kothapalli, Chris Riley, Christian Scheideler, Mark Thober
Fighting against two adversaries: page migration in dynamic networks
by: Marcin Bienkowski, Miroslaw Korzeniowski, Friedhelm Meyer auf der Heide
Dynamic analysis of the arrow distributed protocol
by: Fabian Kuhn, Roger Wattenhofer
Scheduling against an adversarial network
by: Stefano Leonardi, Alberto Marchetti-Spaccamela, Friedhelm Meyer auf der Heide
Time complexity of practical parallel steiner point insertion algorithms
by: Daniel A. Spielman, Shang-Hua Teng, Alper Üngör
Simple efficient load balancing algorithms for peer-to-peer systems
by: David R. Karger, Matthias Ruhl
The effect of faults on network expansion
by: Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, Christian Scheideler
Lower bounds for graph embeddings and combinatorial preconditioners
by: Gary L. Miller, Peter C. Richter
Optimal early stopping uniform consensus in synchronous systems with process omission failures
by: Philippe Raipin Parvédy, Michel Raynal
The inherent queuing delay of parallel packet switches
by: Hagit Attiya, David Hay
Effectively sharing a cache among threads
by: Guy E. Blelloch, Phillip B. Gibbons
An NC algorithm for finding a maximal acyclic set in a graph
by: Aaron Windsor
On delivery times in packet networks under adversarial traffic
by: Adi Rosén, Michael S. Tsirkin
Bi-criteria algorithm for scheduling jobs on cluster platforms
by: Pierre-François Dutot, Lionel Eyraud, Grégory Mounié, Denis Trystram
The potential in energy efficiency of a speculative chip-multiprocessor
by: Yuu Tanaka, Toshinori Sato, Takenori Koushiro
Object location in realistic networks
by: Kirsten Hildrum, Robert Krauthgamer, John Kubiatowicz
Online algorithms for prefetching and caching on parallel disks
by: Rahul Shah, Peter J. Varman, Jeffrey Scott Vitter
Selfish load balancing and atomic congestion games
by: Subhash Suri, Csaba D. Tóth, Yunhong Zhou
On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs
by: Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Charles E. Leiserson
Compact name-independent routing with minimum stretch
by: Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, Mikkel Thorup
On achieving optimized capacity utilization in application overlay networks with multiple competing sessions
by: Yi Cui, Baochun Li, Klara Nahrstedt
Adaptive channel queue routing on k-ary n-cubes
by: Arjun Singh, William J. Dally, Amit K. Gupta, Brian Towles
Efficient search in unstructured peer-to-peer networks
by: Vicent Cholvi, Pascal Felber, Ernst W. Biersack
Geometric generalizations of the power of two choices
by: John W. Byers, Jeffrey Considine, Michael Mitzenmacher
Parallelism versus memory allocation in pipelined router forwarding engines
by: Fan Chung, Ronald Graham, George Varghese
Online hierarchical cooperative caching
by: Xiaozhou Li, C. Greg Plaxton, Mitul Tiwari, Arun Venkataramani
Online algorithms for network design
by: Adam Meyerson
Packet-mode policies for input-queued switches
by: Dan Guez, Alexander Kesselman, Adi Rosén
A scalable lock-free stack algorithm
by: Danny Hendler, Nir Shavit, Lena Yerushalmi
Sharing the cost of multicast transmissions in wireless networks
by: Vittorio Bilò, Chiara Di Francescomarino, Michele Flammini, Giovanna Melideo
New results on web caching with request reordering
by: Susanne Albers
How to route and tax selfish unsplittable traffic
by: Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Pino Persiano

2003

Online deadline scheduling: multiple machines and randomization
by: Jae-Ha Lee
Load balancing of unit size tokens and expansion properties of graphs
by: Robert Elsässer, Burkhard Monien
Relaxing the problem-size bound for out-of-core columnsort
by: Geeta Chaudhry, Elizabeth A. Hamon, Thomas H. Cormen
Quantifying instruction criticality for shared memory multiprocessors
by: Tong Li, Alvin R. Lebeck, Daniel J. Sorin
High throughput, parallelized 128-bit AES encryption in a resource-limited FPGA
by: Christopher Caltagirone, Kasi Anantha
Integrated prefetching and caching in single and parallel disk systems
by: Susanne Albers, Markus Büttner
Improved approximation algorithms for the freeze-tag problem
by: Esther M. Arkin, Michael A. Bender, Dongdong Ge
Off-line and on-line guaranteed start-up delay for media-on-demand with stream merging
by: Amotz Bar-Noy, Justin Goshi, Richard E. Ladner
Buffer overflows of merging streams
by: Alexander Kesselman, Yishay Mansour, Zvi Lotker, Boaz Patt-Shamir
Tree based MPLS routing
by: Anupam Gupta, Amit Kumar, Mikkel Thorup
Worst case mobility in ad hoc networks
by: Christian Schindelhauer, Tamás Lukovszki, Stefan Rührup, Klaus Volbert
On local algorithms for topology control and routing in ad hoc networks
by: Lujun Jia, Rajmohan Rajaraman, Christian Scheideler
I/O-efficient topological sorting of planar DAGs
by: Lars Arge, Laura Toma, Norbert Zeh
Scheduling policies for CIOQ switches
by: Alexander Kesselman, Adi Rosén
The complexity of verifying memory coherence
by: Jason F. Cantin, Mikko H. Lipasti, James E. Smith
Combining online algorithms for rejection and acceptance
by: Yossi Azar, Avrim Blum, Yishay Mansour
Asynchronous parallel disk sorting
by: Roman Dementiev, Peter Sanders
Information gathering in adversarial systems: lines and cycles
by: Kishore Kothapalli, Christian Scheideler
VLSI layout of trees into grids of minimum width
by: Akira Matsubayashi
Short length menger's theorem and reliable optical routing
by: Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman
Toward a decidable notion of sequential consistency
by: Jesse D. Bingham, Anne Condon, Alan J. Hu
A near optimal scheduler for switch-memory-switch routers
by: Adnan Aziz, Amit Prakash, Vijaya Ramachandran
Designing overlay multicast networks for streaming
by: Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, Ramesh K. Sitaraman
TCP is competitive against a limited adversary
by: Jeff Edmonds, Suprakash Datta, Patrick W. Dymond
The load rebalancing problem
by: Gagan Aggarwal, Rajeev Motwani, An Zhu
A polynomial-time tree decomposition to minimize congestion
by: Chris Harrelson, Kirsten Hildrum, Satish Rao
Analysis of link reversal routing algorithms for mobile ad hoc networks
by: Costas Busch, Srikanth Surapaneni, Srikanta Tirthapura
Randomized permutations in a coarse grained parallel environment
by: Jens Gustedt
Cycle stealing under immediate dispatch task assignment
by: Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, Alan Scheller-Wolf, Mark S. Squillante
Performance comparison of MPI and three openMP programming styles on shared memory multiprocessors
by: Géraud Krawezik
A proportionate fair scheduling rule with good worst-case performance
by: Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson
Novel architectures for P2P applications: the continuous-discrete approach
by: Moni Naor, Udi Wieder
Compact routing with name independence
by: Marta Arias, Lenore Cowen, Kofi A. Laing, Rajmohan Rajaraman, Orjeta Taka
Online oblivious routing
by: Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
Minimizing total flow time and total completion time with immediate dispatching
by: Nir Avrahami, Yossi Azar
Optimal sharing of bags of tasks in heterogeneous clusters
by: Micah Adler, Ying Gong, Arnold L. Rosenberg
The effect of communication costs in solid-state quantum computing architectures
by: Dean Copsey, Mark Oskin, Tzvetan Metodiev, Frederic T. Chong, Isaac L. Chuang, John Kubiatowicz
Optimal fault-tolerant linear arrays
by: Toshinori Yamada, Shuichi Ueno
Nonblocking k-compare-single-swap
by: Victor Luchangco, Mark Moir, Nir Shavit
Polynomial time algorithms for network information flow
by: Peter Sanders, Sebastian Egner, Ludo M. G. M. Tolhuizen
A practical algorithm for constructing oblivious routing schemes
by: Marcin Bienkowski, Miroslaw Korzeniowski, Harald Räcke
Can we elect if we cannot compare?
by: Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro
Bicriteria approximation algorithms for scheduling problems with communications
by: Evripidis Bampis, Alexander Kononov
Throughput-centric routing algorithm design
by: Brian Towles, William J. Dally, Stephen P. Boyd
MAPO: using a committee of algorithm-experts for parallel optimization of costly functions
by: Christine A. Shoemaker, Rommel G. Regis
Efficient galois field arithmetic on SIMD architectures
by: Raghav Bhaskar, Pradeep K. Dubey, Vijay Kumar, Atri Rudra
MST construction in O(log log n) communication rounds
by: Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, David Peleg

2002

Locality-preserving randomized oblivious routing on torus networks
by: Arjun Singh, William J. Dally, Brian Towles, Amit K. Gupta
Universal stability of undirected graphs in the adversarial queueing model
by: Carme Àlvarez, Maria J. Blesa, Maria J. Serna
Parallel dynamic programming for solving the string editing problem on a CGM/BSP
by: C. E. R. Alves, Edson Cáceres, Frank K. H. A. Dehne
Parallel scheduling problems in next generation wireless networks
by: Luca Becchetti, Suhas N. Diggavi, Stefano Leonardi, Alberto Marchetti-Spaccamela, S. Muthukrishnan, Thyagarajan Nandagopal, Andrea Vitaletti
Two processor scheduling with real release times and deadlines
by: Hui Wu, Joxan Jaffar
AT2L2 appr. equal N2/2 for fast fourier transform in multilayer VLSI
by: Chi-Hsiang Yeh
Nearest common ancestors: a survey and a new distributed algorithm
by: Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe
Exploiting flexibly assignable work to improve load balance
by: Ali Pinar, Bruce Hendrickson
Algorithms for fault-tolerant routing in circuit switched networks
by: Amitabha Bagchi, Amitabh Chaudhary, Christian Scheideler, Petr Kolman
Verifying sequential consistency using vector clocks
by: Harold W. Cain, Mikko H. Lipasti
A general compiler framework for speculative multithreading
by: Anasua Bhowmik, Manoj Franklin
Distributed streams algorithms for sliding windows
by: Phillip B. Gibbons, Srikanta Tirthapura
Optimal organizations for pipelined hierarchical memories
by: Gianfranco Bilardi, Kattamuri Ekanadham, Pratap Pattnaik
Scheduling reductions on realistic machines
by: Gautam Gupta, Sanjay V. Rajopadhye, Patrice Quinton
Compact, adaptive placement schemes for non-uniform requirements
by: André Brinkmann, Kay Salzwedel, Christian Scheideler
Õ(congestion + dilation) hot-potato routing on leveled networks
by: Costas Busch
Sequential consistency as lazy linearizability
by: Michel Raynal
High performance dynamic lock-free hash tables and list-based sets
by: Maged M. Michael
Optimal tiling for the RNA base pairing problem
by: Francisco Almeida, Rumen Andonov, Daniel González, Luz Marina Moreno, Vincent Poirriez, Casiano Rodríguez
Energy estimation of nested loop programs
by: Frank Hannig, Jürgen Teich
Energy, congestion and dilation in radio networks
by: Friedhelm Meyer auf der Heide, Christian Schindelhauer, Klaus Volbert, Matthias Grünewald
A lightweight idempotent messaging protocol for faulty networks
by: Jeremy Brown, J. P. Grossman, Tom Knight
Distributed caching independent of the network size
by: Matthias Westermann
Work dealing
by: Danny Hendler, Nir Shavit
Distributed object location in a dynamic network
by: Kirsten Hildrum, John Kubiatowicz, Satish Rao, Ben Y. Zhao
Tracking immediate predecessors in distributed computations
by: Emmanuelle Anceaume, Jean-Michel Hélary, Michel Raynal
Rapid prototyping methodology for multi-DSP TI C6X platforms applied to an Mpeg-2 coding application
by: Jean-François Nezan, Olivier Déforges, Michael Raulet
Heuristics for semi-external depth first search on directed graphs
by: Jop F. Sibeyn, James Abello, Ulrich Meyer
Scalability and resource usage of an OLAP benchmark on clusters of PCs
by: Michela Taufer, Thomas Stricker, Roger Weber
Capture of an intruder by mobile agents
by: Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro
New stability results for adversarial queuing
by: Zvi Lotker, Boaz Patt-Shamir, Adi Rosén
Gossiping to reach consensus
by: Bogdan S. Chlebus, Dariusz R. Kowalski
Two techniques for reconciling algorithm parallelism with memory constraints
by: Uzi Vishkin
Extra processors versus future information in optimal deadline scheduling
by: Chiu-Yuen Koo, Tak Wah Lam, Tsuen-Wan Ngan, Kar-Keung To
Worst-case traffic for oblivious routing functions
by: Brian Towles, William J. Dally
The lazy adversary conjecture fails
by: Enoch Peserico

2001

Towards a first vertical prototyping of an extremely fine-grained parallel programming approach
by: Dorit Naishlos, Joseph Nuzman, Chau-Wen Tseng, Uzi Vishkin
Finding large independent sets of hypergraphs in parallel
by: Hadas Shachnai, Aravind Srinivasan
Towards practical deteministic write-all algorithms
by: Bogdan S. Chlebus, Stefan Dobrev, Dariusz R. Kowalski, Grzegorz Malewicz, Alexander A. Shvartsman, Imrich Vrto
D-CAT: A distributed channel allocation strategy based on a threshold scheme for cellular mobile networks
by: Yongbing Zhang, Xiaohua Jia, Sajal K. Das
Ordering disks for double erasure codes
by: Myra B. Cohen, Charles J. Colbourn
Periodic, random-fault-tolerant correction networks
by: Marek Piotrów
Pursuit and evasion on a ring: An infinite hierarchy for parallel real--time systems
by: Stefan D. Bruda, Selim G. Akl
Columnsort lives! an efficient out-of-core sorting program
by: Geeta Chaudhry, Thomas H. Cormen, Leonard F. Wisniewski
Simple on-line algorithms for the maximum disjoint paths problem
by: Petr Kolman, Christian Scheideler
One-to-Many routing on the mesh
by: Kieran T. Herley, Andrea Pietracaprina, Geppino Pucci
Optimal prefetching and caching for parallel I/O sytems
by: Mahesh Kallahalla, Peter J. Varman
The push tree problem
by: Frédéric Havet, Marc Wennink
Estimating simple functions on the union of data streams
by: Phillip B. Gibbons, Srikanta Tirthapura
Computational power of pipelined memory hierarchies
by: Gianfranco Bilardi, Kattamuri Ekanadham, Pratap Pattnaik
Low-contention depth-first scheduling of parallel computations with write-once synchronization variables
by: Panagiota Fatourou
Room synchronizations
by: Guy E. Blelloch, Perry Cheng, Phillip B. Gibbons
Fast, minimal and oblivious routing algorithms on the mesh with bounded queues
by: Ami Litman, Shiri Moran-Schein
A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems
by: Philippas Tsigas, Yi Zhang
A work-optimal CGM algorithm for the LIS problem
by: Thierry Garcia, Jean Frédéric Myoupo, David Semé
Modeling weakly consistent memories with locks
by: Victor Luchangco
Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem
by: Gábor Ivanyos, Frédéric Magniez, Miklos Santha
Deterministic resource discovery in distributed networks
by: Shay Kutten, David Peleg, Uzi Vishkin
Stability and non-stability of the FIFO protocol
by: Josep Díaz, Dimitrios Koukopoulos, Sotiris E. Nikoletseas, Maria J. Serna, Paul G. Spirakis, Dimitrios M. Thilikos
Randomized k-set agreement
by: Achour Mostéfaoui, Michel Raynal
Approximation algorithms for data management in networks
by: Christof Krick, Harald Räcke, Matthias Westermann
Attack propagation in networks
by: Sotiris E. Nikoletseas, Grigorios Prasinos, Paul G. Spirakis, Christos D. Zaroliagis
Optimal semi-oblique tiling
by: Rumen Andonov, Stephan Balev, Sanjay V. Rajopadhye, Nicola Yanev
Competitve buffer management for shared-memory switches
by: Ellen L. Hahne, Alexander Kesselman, Yishay Mansour
Parallel controlled conspiracy number search
by: Ulf Lorenz
Latency effects on reachability in large-scale peer-to-peer networks
by: Fred S. Annexstein, Kenneth A. Berman, Mihajlo A. Jovanovic
A parallel block algorithm for exact triangularization of rectangular matrices
by: Jean-Guillaume Dumas, Jean-Louis Roch
Routing without flow control
by: Costas Busch, Maurice Herlihy, Roger Wattenhofer
A note on cycle covering
by: Jean-Claude Bermond, David Coudert, Lilian Chacon, François Tillerot
The power of duality for prefetching and sorting with parallel disks
by: David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter
A data tracking scheme for general networks
by: Rajmohan Rajaraman, Andréa W. Richa, Berthold Vöcking, Gayathri Vuppuluri
Scheduling on hierarchical clusters using malleable tasks
by: Pierre-François Dutot, Denis Trystram
Compact routing schemes
by: Mikkel Thorup, Uri Zwick
Eventually consistent failure detectors
by: Mikel Larrea, Antonio Fernández, Sergio Arévalo
Library support for orthogonal processor groups
by: Thomas Rauber, Robert Reilein, Gudula Rünger
Scheduling best-effort and real-time pipelined applications on time-shared clusters
by: Yanyong Zhang, Anand Sivasubramaniam
Automatable verification of sequential consistency
by: Anne Condon, Alan J. Hu
Finding strongly connected components in parallel in particle transport sweeps
by: Will McLendon III, Bruce Hendrickson, Steve Plimpton, Lawrence Rauchwerger
Tradeoffs between knowledge and time of communication in geometric radio networks
by: Anders Dessmark, Andrzej Pelc
New spectral bounds on k-partitioning of graphs
by: Robert Elsässer, Thomas Lücking, Burkhard Monien
On tiling space-time mapped loop nests
by: Martin Griebl
Efficient parallel exponentiation in GF(2n) using normal basis representations
by: Mun-Kyu Lee, Yoonjeong Kim, Kunsoo Park, Yookun Cho
Scheduling tasks with small communication delays for clusters of processors
by: Evripidis Bampis, Rodolphe Giroudeau, Alexander Kononov
A cost effective architecture for vectorizable numerical and multimedia applications
by: Francisca Quintana, Jesús Corbal, Roger Espasa, Mateo Valero

2000

Efficient on-line communication in cellular networks
by: Ioannis Caragiannis, Christos Kaklamanis, Evi Papaioannou
The data locality of work stealing
by: Umut A. Acar, Guy E. Blelloch, Robert D. Blumofe
Comparing the effectiveness of fine-grain memory caching against page migration/replication in reducing traffic in DSM clusters
by: An-Chow Lai, Babak Falsafi
Broadcast scheduling optimization for heterogeneous cluster systems
by: Pangfeng Liu, Tzu-Hao Sheng
Interprocessor communication with memory constraints
by: Ali Pinar, Bruce Hendrickson
An experimental study of a simple, distributed edge coloring algorithm
by: Madhav V. Marathe, Alessandro Panconesi, Larry D. Risinger
Optimal schedules for data-parallel cycle-stealing in networks of workstations (extended abstract)
by: Arnold L. Rosenberg
Scheduling Cilk multithreaded parallel programs on processors of different speeds
by: Michael A. Bender, Michael O. Rabin
Efficient, distributed data placement strategies for storage area networks (extended abstract)
by: André Brinkmann, Kay Salzwedel, Christian Scheideler
DCAS-based concurrent deques
by: Ole Agesen, David Detlefs, Christine H. Flood, Alex Garthwaite, Paul A. Martin, Nir Shavit, Guy L. Steele Jr.
Compact, multilayer layout for butterfly fat-tree
by: André DeHon
Generalized connection caching
by: Susanne Albers
An efficient self-simulation algorithm for reconfigurable meshes
by: Susumu Matsumae, Nobuki Tokura
Infinite parallel job allocation (extended abstract)
by: Petra Berenbrink, Artur Czumaj, Tom Friedetzky, Nikita D. Vvedenskaya
Algorithmic foundations for a parallel vector access memory system
by: Binu K. Mathew, Sally A. McKee, John B. Carter, Al Davis
Fault tolerant networks with small degree
by: Li Zhang
Asynchronous scheduling of redundant disk arrays
by: Peter Sanders
Multithreaded algorithms for the fast Fourier transform
by: Parimala Thulasiraman, Kevin B. Theobald, Ashfaq A. Khokhar, Guang R. Gao
A (2.954 epsilon)n oblivious routing algorithm on 2D meshes
by: Kazuo Iwama, Eiji Miyano
VLSI layout and packaging of butterfly networks
by: Chi-Hsiang Yeh, Behrooz Parhami, Emmanouel A. Varvarigos, Hua Lee
Diffusive load balancing schemes on heterogeneous networks
by: Robert Elsässer, Burkhard Monien, Robert Preis
A no-busy-wait balanced tree parallel algorithmic paradigm
by: Uzi Vishkin
Data management in hierarchical bus networks
by: Friedhelm Meyer auf der Heide, Harald Räcke, Matthias Westermann
Connection caching under vaious models of communication
by: Edith Cohen, Haim Kaplan, Uri Zwick

1999

Efficient Parallel Solutions of Linear Algebraic Circuits
by: Yosi Ben-Asher, Gadi Haber
Randomized and Adversarial Load Balancing
by: Petra Berenbrink, Tom Friedetzky, Angelika Steger
Recursive Array Layouts and Fast Parallel Matrix Multiplication
by: Siddhartha Chatterjee, Alvin R. Lebeck, Praveen K. Patnala, Mithuna Thottethodi
Simple Competitive Request Scheduling Strategies
by: Petra Berenbrink, Marco Riedel, Christian Scheideler
Some Compact Layouts of the Butterfly
by: Yefim Dinitz, Shimon Even, Roni Kupershtok, Maria Zapolotsky
Efficient Approximation Algorithms for Scheduling Malleable Tasks
by: Grégory Mounié, Christophe Rapine, Denis Trystram
Selecting Tile Shape for Minimal Execution Time
by: Karin Högstedt, Larry Carter, Jeanne Ferrante
A Closer Look at Coscheduling Approaches for a Network of Workstations
by: Shailabh Nagar, Ajit Banerjee, Anand Sivasubramaniam, Chita R. Das
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy
by: Christof Krick, Friedhelm Meyer auf der Heide, Harald Räcke, Berthold Vöcking, Matthias Westermann
A Comparison of Scalable Superscalar Processors
by: Bradley C. Kuszmaul, Dana S. Henry, Gabriel H. Loh
Fundamental Control Algorithms in Mobile Networks
by: Kostas P. Hatzis, George P. Pentaris, Paul G. Spirakis, Vasilis T. Tampakas, Richard B. Tan
Time-Constrained Scheduling of Weighted Packets on Trees and Meshes
by: Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén
Making Sparse Matrix Computations Scalable (Invited Talk Abstract)
by: James Demmel
BOS is Boss: A Case for Bulk-Synchronous Object Systems
by: Mark Goudreau, Kevin Lang, Girija J. Narlikar, Satish Rao
Communication-Processor Tradeoffs in Limited Resources PRAM
by: Adnan Agbaria, Yosi Ben-Asher, Ilan Newman
Scheduling Threads for Low Space Requirement and Good Locality
by: Girija J. Narlikar
Multidimensional, Multiprocessor, Out-of-Core FFTs
by: Lauren M. Baptist, Thomas H. Cormen
Tradeoffs Between Parallelism and Fill in Nested Dissection
by: Claudson F. Bornstein, Bruce M. Maggs, Gary L. Miller
Experience with an Adaptive Globally-Synchronizing Clock Algorithm
by: Cheng Liao, Margaret Martonosi, Douglas W. Clark
Sorting and Counting Networks of Small Depth and Arbitrary Width
by: Costas Busch, Maurice Herlihy
Post-Mortem Black-Box Correctness Tests for Basic Parallel Data Structures
by: Phillip B. Gibbons, John L. Bruno, Steven Phillips
A Simple and Efficient Parallel Disk Mergesort
by: Rakesh D. Barve, Jeffrey Scott Vitter
Scheduling Optimization for Resource-Intensive Web Requests on Server Clusters
by: Huican Zhu, Ben Smith, Tao Yang
All-to-All Routing and Coloring in Weighted Trees of Rings
by: Bruno Beauquier, Stephane Perennes, David Tóth
A System-Level Specification Framework for I/O Architectures
by: Mark D. Hill, Anne Condon, Manoj Plakal, Daniel J. Sorin
Optimal Replacements in Caches with Two Miss Costs
by: Jaeheon Jeong, Michel Dubois
On the Scheduling of Variable Latency Functional Units
by: Silva M. Mueller

1998

Dynamic Scheduling With Incomplete Information
by: Hannah Bast
Layout of the Batcher Bitonic Sorter (Extended Abstract)
by: Shimon Even, S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp
High Performance Clusters (Abstract): State of the Art and Challenges Ahead
by: David E. Culler
Analyses of Load Stealing Models Based on Differential Equations
by: Michael Mitzenmacher
In-Memory Directories: Eliminating the Cost of Directories in CC-NUMAs
by: Christopher Ho, Heidi Ziegler, Michel Dubois
How to Find It: Research Issues in Distributed Search (Abstract)
by: Udi Manber
Trace-Driven Studies of VLIW Video Signal Processors
by: Zhao Wu, Wayne Wolf
Parallel Continuous Randomized Load Balancing (Extended Abstract)
by: Petra Berenbrink, Tom Friedetzky, Ernst W. Mayr
Communication-Optimal Parallel Minimum Spanning Tree Algorithms (Extended Abstract)
by: Micah Adler, Wolfgang Dittrich, Ben H. H. Juurlink, Miroslaw Kutylowski, Ingo Rieping
Asynchronous Parallel Algorithm for Mining Association Rules on a Shared-Memory MultiPprocessors
by: David Wai-Lok Cheung, Kan Hu, Shaowei Xia
Efficient Disk Allocation for Fast Similarity Searching
by: Sunil Prabhakar, Divyakant Agrawal, Amr El Abbadi
An Adversarial Model for Distributed Dynamic Load Balancing
by: S. Muthukrishnan, Rajmohan Rajaraman
Scheduling Time-Constrained Communication in Linear Networks
by: Micah Adler, Ramesh K. Sitaraman, Arnold L. Rosenberg, Walter Unger
Computation-Centric Memory Models
by: Matteo Frigo, Victor Luchangco
Efficient Communication Strategies for Ad-Hoc Wireless Networks (Extended Abstract)
by: Micah Adler, Christian Scheideler
Broadcasting, Multicasting and Gossiping in Trees Under the All-Port Line Model
by: Johanne Cohen
Computational Bounds for Fundamental Problems on General-Purpose Parallel Models
by: Philip D. MacKenzie, Vijaya Ramachandran
Automatic Parallel I/O Performance Optimization in Panda
by: Ying Chen, Marianne Winslett, Yong Cho, Szu-Wen Kuo
Deadlock-Free Routing in Arbitrary Networks via the Flattest Common Supersequence Method
by: Ambrose Kofi Laing, Robert Cypher
A Framework for Simple Sorting Algorithms on Parallel Disk Systems (Extended Abstract)
by: Sanguthevar Rajasekaran
Detecting Data Rase in Cilk Programs That use Locks
by: Guang-Ien Cheng, Mingdong Feng, Charles E. Leiserson, Keith H. Randall, Andrew F. Stark
Lamport Clocks: Verifying a Directory Cache-Coherence Protocol
by: Manoj Plakal, Daniel J. Sorin, Anne Condon, Mark D. Hill
Blocking in Parallel Multisearch Problems (Extended Abstract)
by: Wolfgang Dittrich, David A. Hutchinson, Anil Maheshwari
``Dynamic-Fault-Prone BSP'': A Paradigm for Robust Computations in Changing Environments
by: Spyros C. Kontogiannis, Grammati E. Pantziou, Paul G. Spirakis, Moti Yung
How "Hard" is Thread Partitioning and How "Bad" is a List Scheduling Based Partitioning Algorithm?
by: Xinan Tang, Guang R. Gao
Elimination Forest Guided 2D Sparse LU Factorization
by: Kai Shen, Xiangmin Jiao, Tao Yang
Explicit Multi-Threading (XMT) Bridging Models for Instruction Parallelism (Extended Abstract)
by: Uzi Vishkin, Shlomit Dascal, Efraim Berkovich, Joseph Nuzman
Algorithmic Problems in Internet Research (Abstract)
by: George Varghese
Using "Test Model-Checking" to Verify the Runway-PA8000 Memory Model
by: Rajnish Ghughal, Abdelillah Mokkedem, Ratan Nalumasu, Ganesh Gopalakrishnan
Fast Set Operations Using Treaps
by: Guy E. Blelloch, Margaret Reid-Miller
Distributed and Parallel Computing Issues in Data Warehousing (Abstract)
by: Hector Garcia-Molina, Wilburt Labio, Janet L. Wiener, Yue Zhuge
Recovery Time of Dynamic Allocation Processes
by: Artur Czumaj
Thread Scheduling for Multiprogrammed Multiprocessors
by: Nimar S. Arora, Robert D. Blumofe, C. Greg Plaxton
Linear Programming Models for Scheduling Systems of Affine Recurrence Equations - A Comparative Study
by: Stephan Balev, Patrice Quinton, Sanjay V. Rajopadhye, Tanguy Risset

1997

On the Analysis of Randomized Load Balancing Schemes
by: Michael Mitzenmacher
Temporal Notions of Synchronization and Consistency in Beehive
by: Aman Singla, Umakishore Ramachandran, Jessica K. Hodgins
Allocating Weighted Jobs in Parallel
by: Petra Berenbrink, Friedhelm Meyer auf der Heide, Klaus Schröder
Simple, Efficient Routing Schemes for All-Optical Networks
by: Michele Flammini, Christian Scheideler
Efficient Load Balancing and Data Remapping for Adaptive Grid Calculations
by: Leonid Oliker, Rupak Biswas
Accessing Nearby Copies of Replicated Objects in a Distributed Environment
by: C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa
Thread Partitioning and Scheduling Based on Cost Model
by: Xinan Tang, J. Wang, Kevin B. Theobald, Guang R. Gao
Modeling Parallel Bandwidth: Local vs. Global Restrictions
by: Micah Adler, Phillip B. Gibbons, Vijaya Ramachandran, Yossi Matias
Optimal Weighted Loop Fusion for Parallel Programs
by: Nimrod Megiddo, Vivek Sarkar
Efficient Computations on Fault-Prone BSP Machines
by: Spyros C. Kontogiannis, Grammati E. Pantziou, Paul G. Spirakis
HARP: A Fast Spectral Partitioner
by: Horst D. Simon, Andrew Sohn, Rupak Biswas
Reactive Diffracting Trees
by: Giovanni Della-Libera, Nir Shavit
Triplex: A Multi-Class Routing Algorithm
by: Melanie L. Fulgham, Lawrence Snyder
Three-Dimensional Pattern Matching
by: Zvi Galil, Jong Geun Park, Kunsoo Park
Using Speculative Retirement and Larger Instruction Windows to Narrow the Performance Gap Between Memory Consistency Models
by: Parthasarathy Ranganathan, Vijay S. Pai, Sarita V. Adve
Can Shared-Memory Model Serve as a Bridging Model for Parallel Computation?
by: Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran
Approximation Algorithms for Structured Communication Problems
by: Dominique Barth, Pierre Fraigniaud
Fine-Grain Multithreading with the EM-X Multiprocessor
by: Andrew Sohn, Yuetsu Kodama, Jui Ku, Mitsuhisa Sato, Hirofumi Sakane, Hayato Yamana, Shuichi Sakai, Yoshinori Yamaguchi
Space-Efficient Scheduling of Parallelism with Synchronization Variables
by: Guy E. Blelloch, Phillip B. Gibbons, Girija J. Narlikar, Yossi Matias
Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms
by: Frank K. H. A. Dehne, Wolfgang Dittrich, David A. Hutchinson
Bounds to the Throughput of an Interconnection Network
by: Ludek Kucera
Efficient Detection of Determinacy Races in Cilk Programs
by: Mingdong Feng, Charles E. Leiserson
System Area Network Mapping
by: Brent N. Chun, Alan M. Mainwaring, Saul Schleimer, Daniel Shawcross Wilkerson
Better Trade-Offs for Parallel List Ranking
by: Jop F. Sibeyn
The Performance of Simple Routing Algorithms That Drop Packets
by: Suprakash Datta, Ramesh K. Sitaraman
On the Parallel Complexity of Matrix Factorization Algorithms
by: Mauro Leoncini, Giovanni Manzini, Luciano Margara
Pipelining with Futures
by: Guy E. Blelloch, Margaret Reid-Miller
Deadlock-Free Oblivious Wormhole Routing with Cyclic Dependencies
by: Loren Schwiebert
Using Tadpoles to Reduce Memory and Communication Requirements for Exhaustive, Breadth-First Search Using Distributed Computers
by: Gene Cooperman, Michael Tselman
From Algorithm Parallelism to Instruction-Level Parallelism: An Encode-Decode Chain Using Prefix-Sum
by: Uzi Vishkin
A Localized Algorithm for Parallel Association Mining
by: Mohammed Javeed Zaki, Srinivasan Parthasarathy, Wei Li
Implementation and Evaluation of an Efficient Parallel Delaunay Triangulation Algorithm
by: Jonathan C. Hardwick

1996

Optimal Latency-Throughput Tradeoffs for Data Parallel Pipelines
by: Jaspal Subhlok, Gary Vondran
Constant Time per Edge is Optimal on Rooted Tree Networks
by: Michael Mitzenmacher
Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems
by: Yonatan Aumann, Michael A. Bender, Lisa Zhang
On the Slowdown of Efficient Simulations of Multibutterflies on Butterflies and Butterfly-Derived Networks
by: Kevin J. Rappoport
Verification of FLASH Cache Coherence Protocol by Aggregation of Distributed Transactions
by: Seungjoon Park, David L. Dill
Parallel Multidimensional Search Using Approximation Algorithms: With Applications to Linear-Programming and Related Problems
by: Sandeep Sen
Improved Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract)
by: Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang
Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling
by: Richard Cole, Philip N. Klein, Robert Endre Tarjan
On the Benefit of Supporting Virtual Channels in Wormhole Routers
by: Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman
BSP vs LogP
by: Gianfranco Bilardi, Kieran T. Herley, Andrea Pietracaprina, Geppino Pucci, Paul G. Spirakis
µDatabase: Parallelism in a Memory-Mapped Environment
by: Peter A. Buhr, Anil K. Goel, Naomi Nishimura, Prabhakar Ragde
First and Second Order Diffusive Methods for Rapid, Coarse, Distributed Load Balancing (Extended Abstract)
by: Bhaskar Ghosh, S. Muthukrishnan, Martin H. Schultz
Anticipatory Instruction Scheduling
by: Vivek Sarkar, Barbara Simons
Flexible Usage of Parity Storage Space in Disk Arrays
by: Eric J. Schwabe, Ian M. Sutherland
Universal Continuous Routing Strategies
by: Christian Scheideler, Berthold Vöcking
On Multiprocessor System Scheduling
by: Xiaotie Deng, Patrick W. Dymond
On the Communication Throughput of Buffered Multistage Interconnection Networks
by: Ralf Rehrmann, Burkhard Monien, Reinhard Lüling, Ralf Diekmann
Fully Dynamic Search Trees for an Extension of the BSP Model
by: Armin Bäumker, Wolfgang Dittrich
Resource Scheduling for Parallel Database and Scientific Applications
by: Soumen Chakrabarti, S. Muthukrishnan
An Analysis of Gang Scheduling for Multiprogrammed Parallel Computing Environments
by: Mark S. Squillante, Fang Wang, Marios C. Papaefthymiou
Local Memory Requirement of Universal Routing Schemes
by: Pierre Fraigniaud, Cyril Gavoille
Deterministic Sorting and Randomized Median Finding on the BSP Model
by: Alexandros V. Gerbessiotis, Constantinos J. Siniolakis
Parallel Algorithms for Personalized Communication and Sorting with an Experimental Study (Extended Abstract)
by: David R. Helman, David A. Bader, Joseph JáJá
Scope Consistency: A Bridge Between Release Consistency and Entry Consistency
by: Liviu Iftode, Jaswinder Pal Singh, Kai Li
A Library of Basic PRAM Algorithms and its Implementation in FORK
by: Christoph W. Keßler, Jesper Larsson Träff
From AAPC Algorithms to High Performance Permutation Routing and Sorting
by: Thomas Stricker, Jonathan C. Hardwick
Load-Sharing in Heterogeneous Systems via Weighted Factoring
by: Susan Flynn Hummel, Jeanette P. Schmidt, R. N. Uma, Joel Wein
Simple Randomized Mergesort on Parallel Disks
by: Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter
Towards Efficiency and Portability: Programming with the BSP Model
by: Mark Goudreau, Kevin Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas
An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms
by: Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall
A Dynamic Load Balancing Framework for Unstructured Adaptive Computations on Distributed-Memory Multiprocessors
by: Andrew Sohn, Rupak Biswas, Horst D. Simon
Parallel Neighborhood Modeling
by: David A. Hutchinson, L. Küttner, Mark Lanthier, Anil Maheshwari, Doron Nussbaum, David Roytenberg, Jörg-Rüdiger Sack
On Trading Task Reallocation for Thread Management in Partitionable Multiprocessors
by: Lixin Gao, Arnold L. Rosenberg, Ramesh K. Sitaraman
Parallel Balanced Allocations
by: Volker Stemann
Components of Congestion Control
by: Ludmila Cherkasova, Al Davis, Robin Hodgson, Vadim E. Kotov, Ian Robinson, Tomas Rokicki
Asynchronous Shared Memory Search Structures
by: Micah Adler
A Steady State Analysis of Diffracting Trees (Extended Abstract)
by: Nir Shavit, Eli Upfal, Asaph Zemach
A Quantitative Comparison of Parallel Computation Models
by: Harry A. G. Wijshoff, Ben H. H. Juurlink
A Tight Layout of the Butterfly Network
by: Aythan Avior, Tiziana Calamoneri, Shimon Even, Ami Litman, Arnold L. Rosenberg

1995

ROMM Routing on Mesh and Torus Networks
by: Ted Nesson, S. Lennart Johnsson
Finding Connected Components on a Scan Line Array Processor
by: Ronald I. Greenberg
An Executable Specification, Analyzer and Verifier for RMO (Relaxed Memory Order)
by: Seungjoon Park, David L. Dill
LogGP: Incorporating Long Messages into the LogP Model - One Step Closer Towards a Realistic Model for Parallel Computation
by: Albert Alexandrov, Mihai F. Ionescu, Klaus E. Schauser, Chris J. Scheiman
An Optimal Randomized Planar Convex Hull Algorithm With Good Empirical Performance
by: Martin E. Dyer, Jonathan M. Nash, Peter M. Dew
On Shortest Path Routing in Single Stage Shuffle-Exchange Networks
by: Sunil Kim, Alexander V. Veidenbaum
Approximating Biconnectivity in Parallel
by: Ka Wong Chong, Tak Wah Lam
Elimination Trees and the Construction of Pools and Stacks (Preliminary Version)
by: Nir Shavit, Dan Touitou
Lower Bounds for Randomized Exclusive Write PRAMs
by: Philip D. MacKenzie
Parallel Molecular Computation
by: John H. Reif
Provably Efficient Scheduling for Languages with Fine-Grained Parallelism
by: Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias
Future Applicability of Bus-Based Shared Memory Multiprocessors
by: C. R. M. Sundaram, Derek L. Eager
On Testing Consecutive-Ones Property in Parallel
by: Fred S. Annexstein, Ramjee P. Swaminathan
Efficient Message Passing Interface (MPI) for Parallel Computing on Clusters of Workstations
by: Jehoshua Bruck, Danny Dolev, Ching-Tien Ho, Marcel-Catalin Rosu, H. Raymond Strong
Don't Be Too Clever: Routing BMMC Permutations on the MasPar MP-2
by: Thomas H. Cormen, Kristin Bruhl
Efficient Techniques for Fast Nested Barrier Synchronization
by: Vara Ramakrishnan, Isaac D. Scherson, Raghu Subramanian
Space-Efficient Routing in Vertex-Symmetric Networks (Extended Abstract)
by: Friedhelm Meyer auf der Heide, Christian Scheideler
The Communication Requirements of Mutual Exclusion
by: Robert Cypher
Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors
by: Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, Marco Zagha
Optimal Parallel Dictionary Matching and Compression (Extended Abstract)
by: Martin Farach, S. Muthukrishnan
Universal Congestion Control for Meshes
by: Jerry Stamatopoulos, Jon A. Solworth
Modeling the Benefits of Mixed Data and Task Parallelism
by: Soumen Chakrabarti, James Demmel, Katherine A. Yelick
Remote Queues: Exposing Message Queues for Pptimization and Atomicity
by: Eric A. Brewer, Frederic T. Chong, Lok T. Liu, Shamik D. Sharma, John Kubiatowicz
Upper Bounds to Processor-Time Tradeoffs under Bounded-Speed Message Propagation
by: Gianfranco Bilardi, Franco P. Preparata
Parallel Sorting with Limited Bandwidth
by: Micah Adler, John W. Byers, Richard M. Karp
A Randomized Parallel 3D Convex Hull Algorithm for Coarse Grained Multicomputers
by: Frank K. H. A. Dehne, Xiaotie Deng, Patrick W. Dymond, Andreas Fabri, Ashfaq A. Khokhar
Parallel Algorithms for the Circuit Value Update Problem
by: Charles E. Leiserson, Keith H. Randall
Applying Randomized Edge Coloring Algorithms to Distributed Communication: An Experimental Study
by: Dannie Durand, Ravi Jain, David Tseytlin
Optimal Trade-Offs Between Size and Slowdown for Universal Parallel Networks
by: Friedhelm Meyer auf der Heide, Martin Storch, Rolf Wanka
On Probabilistic Networks for Selection, Merging, and Sorting
by: Frank Thomson Leighton, Yuan Ma, Torsten Suel
A Universal Proof Technique for Deadlock-Free Routing in Interconnection Networks
by: Loren Schwiebert, D. N. Jayasimha

1994

An Analysis of Diffusive Load-Balancing
by: Raghu Subramanian, Isaac D. Scherson
An Optimal Randomized Logarithmic Time Connectivity algorithm for the EREW PRAM (Extended Abstract)
by: Shay Halperin, Uri Zwick
Minimal Adaptive Routing on the Mesh with Bounded Queue Size
by: Donald D. Chinn, Frank Thomson Leighton, Martin Tompa
Bounds on the Greedy Routing Algorithm for Array Networks
by: Michael Mitzenmacher
An W(log log n) Lower Bound for Routing in Optical Networks
by: Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie
An Optical Simulation of Shared Memory
by: Leslie Ann Goldberg, Yossi Matias, Satish Rao
Parallel Sorting by Over Partitioning
by: Hui Li, Kenneth C. Sevcik
Experiences with Parallel N-Body Simulation
by: Pangfeng Liu, Sandeep N. Bhatt
Diffracting Trees (Preliminary Version)
by: Nir Shavit, Asaph Zemach
O(log² n) Time Efficient Parallel Factorization of Dense, Sparse Separable, and Banded Matrices
by: John H. Reif
On Testing Cache-Coherent Shared Memories
by: Phillip B. Gibbons, Ephraim Korach
Improved Bounds for Routing and Sorting on Multi-Dimensional Meshes
by: Torsten Suel
Bandwidth-Based Lower Bounds on Slowdown for Efficient Emulations of Fixed-Connection Networks
by: Clyde P. Kruskal, Kevin J. Rappoport
Improved Parity-Declustered Layouts for Disk Arrays
by: Eric J. Schwabe, Ian M. Sutherland
Job Scheduling in Rings
by: Perry Fizzano, David R. Karger, Clifford Stein, Joel Wein
An Architecture for Optimal All-to-All Personalized Communication
by: Susan Hinrichs, Corey Kosak, David R. O'Hallaron, Thomas Stricker, Riichiro Take
AT2 Bounds for a Class of VLSI Problems and String Matching
by: Micah Adler, John W. Byers
Construction of the Mesh and the Torus Tolerating a Large Number of Faults
by: Hisao Tamaki
Constructive Deterministic PRAM Simulation on a Mesh-Connected Computer
by: Andrea Pietracaprina, Geppino Pucci, Jop F. Sibeyn
Dynamic Parallel Tree Contraction (Extended Abstract)
by: John H. Reif, Stephen R. Tate
Scheduling Trees using FIFO Queues: A Control-Memory Tradeoff
by: Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg
Modeling Communication in Parallel Algorithms: A Fruitful Interaction Between Theory and Systems?
by: Jaswinder Pal Singh, Edward Rothberg, Anoop Gupta
Communication Efficient Matrix Multiplication on Hypercubes
by: Himanshu Gupta, P. Sadayappan
Studying Overheads in Massively Parallel MIN/MAX-Tree Evaluation
by: Rainer Feldmann, Peter Mysliwietz, Burkhard Monien
How Much Can We Speedup Gaussian Elimination with Pivoting?
by: Mauro Leoncini
Efficient Low-Contention Parallel Algorithms
by: Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran
Efficient Compilation of High-Level Data Parallel Algorithms
by: Dan Suciu, Val Tannen
Dynamic Load Balancing in Parallel and Distributed Networks by Random Matchings (Extended Abstract)
by: Bhaskar Ghosh, S. Muthukrishnan
Efficient Algorithms for All-to-All Communications in Multi-Port Message-Passing Systems
by: Jehoshua Bruck, Ching-Tien Ho, Shlomo Kipnis, Derrick Weathersby
Programming DEC-Alpha Based Multiprocessors the Easy Way (Extended Abstract)
by: Hagit Attiya, Roy Friedman
Increasing Network Bandwidth on Meshes
by: Jerry Stamatopoulos, Jon A. Solworth
A Comparison of Parallel Algorithms for Connected Components
by: John Greiner
2d-Bubblesorting in Average time O(N lg N)
by: Doug Ierardi
A Model for Multi-Grained Parallelism (Extended Abstract)
by: John E. Savage
Segment Router: A Novel Router Design for Parallel Computers
by: Smaragda Konstantinidou
Scheduling Parallelizable Tasks to Minimize Average Response Time
by: John Turek, Walter Ludwig, Joel L. Wolf, Lisa Fleischer, Prasoon Tiwari, Jason Glasgow, Uwe Schwiegelshohn, Philip S. Yu
SIMD Instruction Cache
by: Todd E. Rockoff
List Ranking and List Scan on the Cray C-90
by: Margaret Reid-Miller

1993

Optimal Parallel Construction of Hamiltonian Cycles and Spanning Trees in Random Graphs
by: Philip D. MacKenzie, Quentin F. Stout
Parallel Construction of Optimal Alphabetic Trees
by: Lawrence L. Larmore, Teresa M. Przytycka, Wojciech Rytter
Efficient Wiring of Reconfigurable Parallel Processors
by: David S. Greenberg
Components for Computing and Communications
by: David May
Experience in Massively Parallel Discrete Event Simulation
by: Albert G. Greenberg, Boris D. Lubachevsky, Li-C. Wang
Fault-Tolerant Meshes with Small Degree
by: Jehoshua Bruck, Robert Cypher, Ching-Tien Ho
An Efficient Parallel Algorithm for the Single Function Coarsest Partition Problem
by: Joseph JáJá, Kwan Woo Ryu
New Graph Decompositions and Fast Emulations in Hypercubes and Butterflies
by: Christos Kaklamanis, Danny Krizanc, Satish Rao
An Overview of Cray Research Computers Including the Y-MP/C90 and the new MPP T3D
by: Wilfried Oed, Martin Walker
The Power of Processor Consistency
by: Mustaque Ahamad, Rida A. Bazzi, Ranjit John, Prince Kohli, Gil Neiger
Highly Efficient Dictionary Matching in Parallel
by: S. Muthukrishnan, Krishna V. Palem
Scan Grammars: Parallel Attribute Evaluation via Data-Parallelism
by: Thomas W. Reps
Scalable Hardware and Scalable Software : The nCUBE System
by: Bernd Wiesen
Bounds on the Efficiency of Message-Passing Protocols for Parallel Computers
by: Robert Cypher, Smaragda Konstantinidou
Scalable Parallel Computing: The IBM 9076 Scalable POWE