20. SPAA 2008: Munich, Germany

Friedhelm Meyer auf der Heide, Nir Shavit (Eds.): SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures, Munich, Germany, June 14-16, 2008. ACM 2008, ISBN 978-1-59593-973-9 BibTeX

Special track: multicores

Zvika Guz, Idit Keidar, Avinoam Kolodny, Uri C. Weiser:
Utilizing shared data in chip multiprocessors with the nahalal architecture. 1-10
Electronic Edition (ACM DL) BibTeX
Edya Ladan-Mozes, Charles E. Leiserson:
A consistency architecture for hierarchical shared caches. 11-22
Electronic Edition (ACM DL) BibTeX
Guy E. Blelloch, Phillip B. Gibbons, S. Harsha Vardhan:
Combinable memory-block transactions. 23-34
Electronic Edition (ACM DL) BibTeX
Olatunji Ruwase, Phillip B. Gibbons, Todd C. Mowry, Vijaya Ramachandran, Shimin Chen, Michael Kozuch, Michael Ryan:
Parallelizing dynamic information flow tracking. 35-45
Electronic Edition (ACM DL) BibTeX

Algorithms on graphs

Christoph Lenzen, Yvonne Anne Oswald, Roger Wattenhofer:
What can be approximated locally?: case study: dominating sets in planar graphs. 46-54
Electronic Edition (ACM DL) BibTeX
Andrzej Czygrinow, Michal Hanckowiak, Wojciech Wawrzyniak:
Distributed packing in planar graphs. 55-61
Electronic Edition (ACM DL) BibTeX
Pierre Fraigniaud, Cyril Gavoille:
Polylogarithmic network navigability using compact metrics with small stretch. 62-69
Electronic Edition (ACM DL) BibTeX

Broadcasting in networks

Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks:
Online multicast with egalitarian cost sharing. 70-76
Electronic Edition (ACM DL) BibTeX
Emanuele G. Fusco, Andrzej Pelc:
Trade-offs between the size of advice and broadcasting time in trees. 77-84
Electronic Edition (ACM DL) BibTeX
Baruch Awerbuch, Rohit Khandekar:
Cost sharing mechanisms for near-optimal traffic aggregation and network design. 85-90
Electronic Edition (ACM DL) BibTeX
Yaacov Fernandess, Dahlia Malkhi:
On spreading recommendations via social gossip. 91-97
Electronic Edition (ACM DL) BibTeX

Brief announcements

Victor Luchangco:
Against lock-based semantics for transactional memory. 98-100
Electronic Edition (ACM DL) BibTeX
Amitabha Roy, Keir Fraser, Steven Hand:
A transactional approach to lock scalability. 101-103
Electronic Edition (ACM DL) BibTeX
Shantanu Gupta, Florin Sultan, Srihari Cadambi, Franjo Ivancic, Martin Rötteler:
RaceTM: detecting data races using transactional memory. 104-106
Electronic Edition (ACM DL) BibTeX
Behram Khan, Matthew Horsnell, Ian Rogers, Mikel Luján, Andrew Dinn, Ian Watson:
A first insight into object-aware hardware transactional memory. 107-109
Electronic Edition (ACM DL) BibTeX
Kunal Agrawal, I.-Ting Angelina Lee, Jim Sukha:
Safe open-nested transactions through ownership. 110-112
Electronic Edition (ACM DL) BibTeX
Torsten Hoefler, Peter Gottschling, Andrew Lumsdaine:
Leveraging non-blocking collective communication in high-performance applications. 113-115
Electronic Edition (ACM DL) BibTeX
Daniel Greenfield, Simon W. Moore:
Fractal communication in software data dependency graphs. 116-118
Electronic Edition (ACM DL) BibTeX

Graph algorithms

Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, Mark R. Tuttle:
Many random walks are faster than one. 119-128
Electronic Edition (ACM DL) BibTeX
Zvi Lotker, Boaz Patt-Shamir, Seth Pettie:
Improved distributed approximate matching. 129-136
Electronic Edition (ACM DL) BibTeX
Ioannis Koutis, Gary L. Miller:
Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning. 137-145
Electronic Edition (ACM DL) BibTeX
Warren J. Schudy:
Finding strongly connected components in parallel using o(log²n) reachability queries. 146-151
Electronic Edition (ACM DL) BibTeX

Special track -- transactional memory

Torvald Riegel, Christof Fetzer, Pascal Felber:
Automatic data partitioning in software transactional memories. 152-159
Electronic Edition (ACM DL) BibTeX
Eric Koskinen, Maurice Herlihy:
Checkpoints and continuations instead of nested transactions. 160-168
Electronic Edition (ACM DL) BibTeX
Richard M. Yoo, Hsien-Hsin S. Lee:
Adaptive transaction scheduling for transactional memory systems. 169-178
Electronic Edition (ACM DL) BibTeX

Brief announcements

Kai Shen, Alex Zhang, Terence Kelly, Christopher Stewart:
Operational analysis of processor speed scaling. 179-181
Electronic Edition (ACM DL) BibTeX
Xiongfei Liao, Wu Jigang, Thambipillai Srikanthan:
A temperature-aware virtual submesh allocation scheme for noc-based manycore chips. 182-184
Electronic Edition (ACM DL) BibTeX
Reza Dorrigiv, Alejandro López-Ortiz, Alejandro Salinger:
Optimal speedup on a low-degree multi-core parallel architecture (LoPRAM). 185-187
Electronic Edition (ACM DL) BibTeX
Yongwook Choi, Maleq Khan, V. S. Anil Kumar, Gopal Pandurangan:
Energy-optimal distributed algorithms for minimum spanning trees. 188-190
Electronic Edition (ACM DL) BibTeX
André Brinkmann, Sascha Effert:
Data replication in p2p environments. 191-193
Electronic Edition (ACM DL) BibTeX
Vittorio Bilò, Angelo Fanelli, Michele Flammini, Luca Moscardelli:
Graphical congestion games with linear latencies. 194-196
Electronic Edition (ACM DL) BibTeX

Special track -- multicore algorithms

Lars Arge, Michael T. Goodrich, Michael Nelson, Nodari Sitchinava:
Fundamental parallel algorithms for private-cache chip multiprocessors. 197-206
Electronic Edition (ACM DL) BibTeX
Rezaul Alam Chowdhury, Vijaya Ramachandran:
Cache-efficient dynamic programming algorithms for multicores. 207-216
Electronic Edition (ACM DL) BibTeX
Milind Kulkarni, Patrick Carribault, Keshav Pingali, Ganesh Ramanarayanan, Bruce Walter, Kavita Bala, L. Paul Chew:
Scheduling strategies for optimistic parallel execution of irregular programs. 217-228
Electronic Edition (ACM DL) BibTeX

Parallel and distributed scheduling

Alessandro Panconesi, Mauro Sozio:
Fast distributed scheduling via primal-dual. 229-235
Electronic Edition (ACM DL) BibTeX
Nedialko B. Dimitrov, Indrajit Roy:
A primal-dual resource augmentation analysis of a constant approximate algorithm for stable coalitions in a cluster. 236-245
Electronic Edition (ACM DL) BibTeX
Christopher Y. Crutchfield, Zoran Dzunic, Jeremy T. Fineman, David R. Karger, Jacob Scott:
Improved approximations for multiprocessor scheduling under uncertainty. 246-255
Electronic Edition (ACM DL) BibTeX
Tak Wah Lam, Lap-Kei Lee, Isaac Kar-Keung To, Prudence W. H. Wong:
Competitive non-migratory scheduling for flow time and energy. 256-264
Electronic Edition (ACM DL) BibTeX

Special track -- STM design and locks

Richard M. Yoo, Yang Ni, Adam Welc, Bratin Saha, Ali-Reza Adl-Tabatabai, Hsien-Hsin S. Lee:
Kicking the tires of software transactional memory: why the going gets tough. 265-274
Electronic Edition (ACM DL) BibTeX
Michael F. Spear, Maged M. Michael, Christoph von Praun:
RingSTM: scalable transactions with a single atomic instruction. 275-284
Electronic Edition (ACM DL) BibTeX
Adam Welc, Bratin Saha, Ali-Reza Adl-Tabatabai:
Irrevocable transactions and their applications. 285-296
Electronic Edition (ACM DL) BibTeX
Eric Koskinen, Maurice Herlihy:
Dreadlocks: efficient deadlock detection. 297-303
Electronic Edition (ACM DL) BibTeX

STM analysis and semantics

Rachid Guerraoui, Michal Kapalka:
On obstruction-free transactions. 304-313
Electronic Edition (ACM DL) BibTeX
Vijay Menon, Steven Balensiefer, Tatiana Shpeisman, Ali-Reza Adl-Tabatabai, Richard L. Hudson, Bratin Saha, Adam Welc:
Practical weak-atomicity semantics for java stm. 314-325
Electronic Edition (ACM DL) BibTeX
Rui Zhang, Zoran Budimlic, William N. Scherer III:
Commit phase in timestamp-based stm. 326-335
Electronic Edition (ACM DL) BibTeX

Algorithms

Hagit Attiya, Rachid Guerraoui, Eric Ruppert:
Partial snapshot objects. 336-343
Electronic Edition (ACM DL) BibTeX
Ioannis Caragiannis, Christos Kaklamanis, Evangelos Kranakis, Danny Krizanc, Andreas Wiese:
Communication in wireless networks with directional antennas. 344-351
Electronic Edition (ACM DL) BibTeX
Wing-Kai Hon, Rahul Shah, Peter J. Varman, Jeffrey Scott Vitter:
Tight competitive ratios for parallel disk prefetching and caching. 352-361
Electronic Edition (ACM DL) BibTeX

Posters

Mark Moir, Kevin Moore, Daniel Nussbaum:
The adaptive transactional memory test platform: a tool for experimenting with transactional code for rock (poster). 362
Electronic Edition (ACM DL) BibTeX
JaeWoong Chung, Jiwon Seo, Woongki Baek, Chi Cao Minh, Austen McDonald, Christos Kozyrakis, Kunle Olukotun:
Improving software concurrency with hardware-assisted memory snapshot. 363
Electronic Edition (ACM DL) BibTeX
Waleed Alsalih, Kamrul Islam, Yurai Núñez Rodríguez, Henry Xiao:
Distributed voronoi diagram computation in wireless sensor networks. 364
Electronic Edition (ACM DL) BibTeX
Fei Wei, Huazhong Yang:
Directed transmission method, a fully asynchronous approach to solve sparse linear systems in parallel. 365
Electronic Edition (ACM DL) BibTeX
JaeWoong Chung, Woongki Baek, Nathan Grasso Bronson, Jiwon Seo, Christos Kozyrakis, Kunle Olukotun:
Ased: availability, security, and debugging support usingtransactional memory. 366
Electronic Edition (ACM DL) BibTeX