18. SPAA 2006: Cambridge, Massachusetts, USA

Phillip B. Gibbons, Uzi Vishkin (Eds.): SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30 - August 2, 2006. ACM 2006, ISBN 1-59593-452-9 BibTeX

Games and learning

Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-Shamir:
Tell me who I am: an interactive recommendation system. 1-10
Electronic Edition (ACM DL) BibTeX
Zvi Lotker, Boaz Patt-Shamir, Mark R. Tuttle:
Publish and perish: definition and analysis of an n-person publication impact game. 11-18
Electronic Edition (ACM DL) BibTeX
Alexis C. Kaporis, Paul G. Spirakis:
The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions. 19-28
Electronic Edition (ACM DL) BibTeX
Ho-Lin Chen, Tim Roughgarden:
Network design with weighted players. 29-38
Electronic Edition (ACM DL) BibTeX

Compilers, supercomputing and quantum computing

Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi:
Towards automatic parallelization of tree reductions in dynamic programming. 39-48
Electronic Edition (ACM DL) BibTeX
Arun Kejariwal, Alexandru Nicolau, Hideki Saito, Xinmin Tian, Milind Girkar, Utpal Banerjee, Constantine D. Polychronopoulos:
A general approach for partitioning N-dimensional parallel nested loops with conditionals. 49-58
Electronic Edition (ACM DL) BibTeX
John W. Romein, P. Chris Broekema, Ellen van Meijeren, Kjeld van der Schaaf, Walther H. Zwart:
Astronomical real-time streaming signal processing on a Blue Gene/L supercomputer. 59-66
Electronic Edition (ACM DL) BibTeX
François Le Gall:
Exponential separation of quantum and classical online space complexity. 67-73
Electronic Edition (ACM DL) BibTeX

Scheduling

Ami Litman, Shiri Moran-Schein:
Smooth scheduling under variable rates or the analog-digital confinement game. 74-83
Electronic Edition (ACM DL) BibTeX
Brighten Godfrey, Richard M. Karp:
On the price of heterogeneity in parallel systems. 84-92
Electronic Edition (ACM DL) BibTeX
C. Greg Plaxton, Yu Sun, Mitul Tiwari, Harrick Vin:
Reconfigurable resource scheduling. 93-102
Electronic Edition (ACM DL) BibTeX
Arnaud Legrand, Alan Su, Frédéric Vivien:
Minimizing the stretch when scheduling flows of biological requests. 103-112
Electronic Edition (ACM DL) BibTeX

Parallel programming models: need, study & position papers

Geoff Lowney:
Why Intel is designing multi-core processors. 113
Electronic Edition (ACM DL) BibTeX
Lorin Hochstein, Victor R. Basili:
An empirical study to compare two parallel programming models. 114
Electronic Edition (ACM DL) BibTeX
Elena Riccio Davidson:
The FG programming environment: good and good for you. 115
Electronic Edition (ACM DL) BibTeX
Franklin E. Powers Jr., Gita Alaghband:
Introducing the hydra parallel programming system. 116
Electronic Edition (ACM DL) BibTeX
Jonathan Leighton Brown, Sue Goudy, Mike Heroux, Shan Shan Huang, Zhaofang Wen:
An envolutionary path towards virtual shared memory with random access. 117
Electronic Edition (ACM DL) BibTeX

Communication networks

Michael T. Goodrich, Daniel S. Hirschberg:
Efficient parallel algorithms for dead sensor diagnosis and multiple access channels. 118-127
Electronic Edition (ACM DL) BibTeX
Amotz Bar-Noy, Panagiotis Cheilaris, Shakhar Smorodinsky:
Conflict-free coloring for intervals: from offline to online. 128-137
Electronic Edition (ACM DL) BibTeX
Hagit Attiya, David Hay, Isaac Keslassy:
Packet-mode emulation of output-queued switches. 138-147
Electronic Edition (ACM DL) BibTeX
Robert Elsässer:
On the communication complexity of randomized broadcasting in random-like graphs. 148-157
Electronic Edition (ACM DL) BibTeX

Processing and scheduling

Martha Mercaldi, Steven Swanson, Andrew Petersen, Andrew Putnam, Andrew Schwerin, Mark Oskin, Susan J. Eggers:
Modeling instruction placement on a spatial architecture. 158-169
Electronic Edition (ACM DL) BibTeX
Lisa Higham, LillAnne Jackson:
Translating between itanium and sparc memory consistency models. 170-179
Electronic Edition (ACM DL) BibTeX
John Augustine, Sudarshan Banerjee, Sandy Irani:
Strip packing with precedence constraints and strip packing with release times. 180-189
Electronic Edition (ACM DL) BibTeX
David P. Bunde:
Power-aware scheduling for makespan and flow. 190-196
Electronic Edition (ACM DL) BibTeX

Graphs and networks

David Steurer:
Tight bounds for the Min-Max boundary decomposition cost of weighted graphs. 197-206
Electronic Edition (ACM DL) BibTeX
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi:
On space-stretch trade-offs: lower bounds. 207-216
Electronic Edition (ACM DL) BibTeX
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi:
On space-stretch trade-offs: upper bounds. 217-224
Electronic Edition (ACM DL) BibTeX
Philippe Duchon, Nicolas Hanusse, Emmanuelle Lebhar, Nicolas Schabanel:
Towards small world emergence. 225-232
Electronic Edition (ACM DL) BibTeX

Routing and scientific applications

Arthur Brady, Lenore Cowen:
Compact routing with additive stretch using distance labelings. 233
Electronic Edition (ACM DL) BibTeX
Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton:
Semi-oblivious routing. 234
Electronic Edition (ACM DL) BibTeX
Marc Moreno Maza, Yuzhen Xie:
An implementation report for parallel triangular decompositions. 235
Electronic Edition (ACM DL) BibTeX
Rezaul Alam Chowdhury, Vijaya Ramachandran:
The cache-oblivious gaussian elimination paradigm: theoretical framework and experimental evaluation. 236
Electronic Edition (ACM DL) BibTeX

Distributed computing

Joachim Gehweiler, Christiane Lammersen, Christian Sohler:
A distributed O(1)-approximation algorithm for the uniform facility location problem. 237-243
Electronic Edition (ACM DL) BibTeX
R. C. Chakinala, Abishek Kumarasubramanian, Kofi A. Laing, R. Manokaran, C. Pandu Rangan, Rajmohan Rajaraman:
Playing push vs pull: models and algorithms for disseminating dynamic data in networks. 244-253
Electronic Edition (ACM DL) BibTeX
Julia Lipman, Quentin F. Stout:
A performance analysis of local synchronization. 254-260
Electronic Edition (ACM DL) BibTeX
David Pritchard, Santosh Vempala:
Symmetric network computation. 261-270
Electronic Edition (ACM DL) BibTeX

Caches, registers and load balancing

Matteo Frigo, Volker Strumpen:
The cache complexity of multithreaded cache oblivious algorithms. 271-280
Electronic Edition (ACM DL) BibTeX
Chryssis Georgiou, Nicolas C. Nicolaou, Alexander A. Shvartsman:
Fault-tolerant semifast implementations of atomic read/write registers. 281-290
Electronic Edition (ACM DL) BibTeX
Niv Buchbinder, Joseph Naor:
Fair online load balancing. 291-298
Electronic Edition (ACM DL) BibTeX
Mette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Patrascu, Milan Ruzic, Peter Tiedemann:
Deterministic load balancing and dictionaries in the parallel disk model. 299-307
Electronic Edition (ACM DL) BibTeX

Peer-to-peer networks

Peter Mahlmann, Christian Schindelhauer:
Distributed random digraph transformations for peer-to-peer networks. 308-317
Electronic Edition (ACM DL) BibTeX
Baruch Awerbuch, Christian Scheideler:
Towards a scalable and robust DHT. 318-327
Electronic Edition (ACM DL) BibTeX

Multicores, multiprocessor systems and grids

Jaime H. Moreno:
Chip-level integration: the new frontier for microprocessor architecture. 328
Electronic Edition (ACM DL) BibTeX
Tali Moreshet, R. Iris Bahar, Maurice Herlihy:
Energy implications of multiprocessor synchronization. 329
Electronic Edition (ACM DL) BibTeX
Vasileios Liaskovitis, Shimin Chen, Phillip B. Gibbons, Anastassia Ailamaki, Guy E. Blelloch, Babak Falsafi, Limor Fix, Nikos Hardavellas, Michael Kozuch, Todd C. Mowry, Chris Wilkerson:
Parallel depth first vs. work stealing schedulers on CMP architectures. 330
Electronic Edition (ACM DL) BibTeX
Quentin F. Stout:
Minimizing peak energy on mesh-connected systems. 331
Electronic Edition (ACM DL) BibTeX
Krzysztof Rzadca, Denis Trystram:
Promoting cooperation in selfish grids. 332
Electronic Edition (ACM DL) BibTeX