SPAA’08 Accepted Papers and Call for Participation
========================================================================
SPAA 2008 Call for Participation
20th ACM Symposium on Parallelism in Algorithms and Architectures
Munich, Germany
June 14 - 16, 2008
http://www.spaa-conference.org
========================================================================
SPAA’08 will take place in Munich, Germany from June 14-16. The
registration server is now open at http://www.spaa-conference.org/ .
Early registrations are possible till May 14. Rooms can be reserved at
a special rate till April 10.
We will have several invited talks:
Hagit Attiya, Technion
Charles Leiserson, Massachusetts Institute of Technology
Kunle Olukotun, Stanford University
Arnold Rosenberg, University of Massachusetts at Amherst
Burton Smith, Microsoft Research
Leslie Valiant, Harvard University
The list of accepted papers follows below.
Andrea Richa
SPAA Publicity Chair
——————————————————————-
REGULAR PAPERS:
Guy Blelloch, Phillip Gibbons and S. Harsha Vardhan.
Combinable Memory-Block Transactions
Moses Charikar, Howard Karloff, Claire Mathieu, Seffi Naor and Michael
Saks.
Online Multicast with Egalitarian Cost Sharing
Noga Alon, Chen Avin, Michal Koucky, Gady Kozma, Zvi Lotker and Mark R.
Tuttle.
Many Random Walks Are Faster Than One
Zvi Lotker, Boaz Patt-Shamir and Seth Pettie.
Improved Distributed Approximate Matching
Christoph Lenzen, Yvonne Anne Oswald and Roger Wattenhofer.
What Can Be Approximated Locally?
Ioannis Koutis and Gary Miller.
Graph partitioning into isolated, high conductance clusters: theory,
computation and applications to preconditioning
Mauro Sozio and Alessandro Panconesi.
Fast Distributed Scheduling via Primal-Dual
Ioannis Caragiannis, Christos Kaklamanis, Evangelos Kranakis, Danny
Krizanc and Andreas Wiese.
Communication in wireless networks with directional antennas
Vijay Menon, Steven Balensiefer, Tatiana Shpeisman, Ali-Reza
Adl-Tabatabai, Richard Hudson, Bratin Saha and Adam Welc.
Practical Weak-Atomicity Semantics for Java STM
Baruch Awerbuch and Rohit Khandekar.
Cost Sharing Mechanisms for Near-Optimal Traffic Aggregation and Network
Design
Warren Schudy.
Finding Strongly Connected Components in Parallel using O(log^2 n)
Reachability Queries
Pierre Fraigniaud and Cyril Gavoille.
Polylogarithmic Network Navigability Using Compact Metrics with Small
Stretch
Christopher Crutchfield, Zoran Dzunic, Jeremy Fineman, David Karger and
Jacob Scott.
Improved Approximations for Multiprocessor Scheduling Under Uncertainty
Hagit Attiya, Rachid Guerraoui and Eric Ruppert.
Partial Snapshot Objects
Emanuele Guido Fusco and Andrzej Pelc.
Trade-offs Between the Size of Advice and Broadcasting Time in Trees
Rui Zhang, Zoran Budimlic and William Scherer.
Commit Phase in Timestamp-based STM
Tak-Wah Lam, Lap Kei Lee, Isaac K.K. To and Prudence W.H. Wong.
Competitive Non-migratory Scheduling for Flow Time and Energy
Michal Hanckowiak, Andrzej Czygrinow and Wojciech Wawrzyniak.
Distributed packing in planar graphs
Cyril Gavoille and Andy Twigg.
Compact Forbidden-set Routing on Planar Graphs
Wing Kai Hon, Rahul Shah, Peter Varman and Jeffrey Scott Vitter.
Tight Competitive Ratios for Parallel Disk Prefetching and Caching
Yaacov Fernandess and Dahlia Malkhi.
On Spreading Recommendations via Social Gossip
Rachid Guerraoui and Michal Kapalka.
On Obstruction-Free Transactions
Indrajit Roy and Nedialko Dimitrov.
A Primal-Dual Resource Augmentation Analysis of a Constant Approximate
Algorithm for Stable Coalitions in a Cluster
SPECIAL TRACK PAPERS:
Adam Welc, Bratin Saha and Ali-Reza Adl-Tabatabai.
Irrevocable Transactions and their Applications
Edya Ladan Mozes and Charles Leiserson.
A Consistency Architecture for Hierarchical Shared Caches
Michael Spear, Maged Michael and Christoph von Praun.
RingSTM: Scalable Transactions with a Single Atomic Instruction
Torvald Riegel, Christof Fetzer and Pascal Felber.
Automatic Data Partitioning in Software Transactional Memories
Olatunji Ruwase, Phillip Gibbons, Todd Mowry, Vijaya Ramachandran,
Shimin Chen, Michael Kozuch and Michael Ryan.
Parallelizing Dynamic Information Flow Tracking
Rezaul Chowdhury and Vijaya Ramachandran.
Cache-efficient Dynamic Programming Algorithms for Multicores
Lars Arge, Michael T. Goodrich, Michael Nelson and Nodari Sitchinava.
Fundamental Parallel Algorithms for Private-Cache Chip Multiprocessors
Zvika Guz, Idit Keidar, Avinoam Kolodny and Uri C. Weiser.
Utilizing Shared Data in Chip Multiprocessors with the Nahalal
Architecture
Eric Koskinen and Maurice Herlihy.
Dreadlocks: Efficient Deadlock Detection
Eric Koskinen and Maurice Herlihy.
Checkpoints and Continuations instead of Nested Transactions
Milind Kulkarni, Keshav Pingali, Ganesh Ramanarayanan, Bruce Walter,
Patrick Carribault, Paul Chew and Kavita Bala.
Scheduling Strategies for Optimistic Parallel Execution of Irregular
Programs
Richard Yoo and Hsien-Hsin Lee.
Adaptive Transaction Scheduling for Transactional Memory Systems
Richard Yoo, Yang Ni, Adam Welc, Bratin Saha, Ali-Reza Adl-Tabatabai and
Hsien-Hsin Lee.
Kicking the Tires of Software Transactional Memory: Why the Going Gets
Tough
Brief announcements:
Kai Shen, Alex Zhang, Terence Kelly and Chris Stewart.
Operational Analysis of Processor Speed Scaling
Kunal Agrawal, ITing Lee and Jim Sukha.
Safe Open-Nested Transactions Through Ownership
Daniel Greenfield and Simon Moore.
Fractal Communication in Software Data Dependency Graphs
Xiongfei Liao, Wu Jigang and Thambipillai Srikanthan.
A Temperature-Aware Virtual Submesh Allocation Scheme for NoC-based
Manycore Chips
Reza Dorrigiv, Alejandro Lopez-Ortiz and Alejandro Salinger.
Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture
(LoPRAM)
Amitabha Roy, Keir Fraser and Steven Hand.
A Transactional Approach to Lock Scalability
Shantanu Gupta, Florin Sultan, Srihari Cadambi, Franjo Ivancic and
Martin Roetteler.
RaceTM: Detecting Data Races Using Transactional Memory
Behram Khan, Matthew Horsnell, Ian Rogers, Mikel Lujan, Andrew Dinn and
Ian Watson.
An Object Based Hardware Transactional Memory System
Andre Brinkmann and Sascha Effert.
Data Replication in P2P Environments
Torsten Hoefler, Peter Gottschling and Andrew Lumsdaine.
Leveraging non-blocking collective communication in high-performance
applications
Yongwook Choi, Maleq Khan, Anil Kumar and Gopal Pandurangan.
Work-Efficient Distributed Euclidean Minimum Spanning Tree
Victor Luchangco.
Against Lock-Based Semantics for Transactional Memory
Vittorio Bilo, Angelo Fanelli, Michele Flammini and Luca Moscardelli.
Graphical Congestion Games with Linear Latencies
POSTERS:
Mark Moir, Kevin Moore and Dan Nussbaum.
The Adaptive Transactional Memory Test Platform
Jaewoong chung, Jiwon seo, Woongki Baek, Chi Cao Minh, Christos
Kozyrakis and kunle Olukotun.
Improving Software Concurrency with Hardware-assisted memory Snapshot
Waleed Alsalih, Md. Kamrul Islam, Yurai Nunez Rodriguez and Henry Xiao.
Distributed Voronoi diagram computation in wireless sensor networks
Fei Wei and Huazhong Yang.
Directed Transmission Method, a Fully Asynchronous Approach to Solve
Sparse Linear Systems in Parallel
Jaewoong chung, Woongki Baek, Nathan Bronson, Jiwon Seo, Christos
Kozyrakis and Kunle Olukotun.
ASeD: Availability, Security, and Debugging Support using Transactional
Memory
–
Prof. Andrea W. Richa |Phone: 480-965-7555
Computer Science & Eng. Dept. |FAX: 480-965-2751
Arizona State University |E-mail: aricha@asu.edu
PO Box 878809, Tempe AZ 85287-8809|Homepage:www.public.asu.edu/~aricha
.