SPAA 2008 Program: ================== Friday, June 13: 6:00 - 9:00 pm: SPAA reception (at Technical University of Munich) Saturday, June 14: 8:30 - 9:30: Invited Talk 1 Kunle Olukotun, Stanford University Towards pervasive parallelism 9:30 - 10:50: Session 1 -- Special Track -- Multicores Chair: Nir Shavit Winner of the best paper award: Zvika Guz, Idit Keidar, Avinoam Kolodny and Uri C. Weiser. Utilizing Shared Data in Chip Multiprocessors with the Nahalal Architecture Edya Ladan Mozes and Charles Leiserson. A Consistency Architecture for Hierarchical Shared Caches Guy Blelloch, Phillip Gibbons and S. Harsha Vardhan. Combinable Memory-Block Transactions Olatunji Ruwase, Phillip Gibbons, Todd Mowry, Vijaya Ramachandran, Shimin Chen, Michael Kozuch and Michael Ryan. Parallelizing Dynamic Information Flow Tracking 10:50 - 11:20: Coffee Break 11:20 - 12:20: Session 2 -- Algorithms on Graphs Chair: Emmanuelle Lebhar Christoph Lenzen, Yvonne Anne Oswald and Roger Wattenhofer. What Can Be Approximated Locally? Michal Hanckowiak, Andrzej Czygrinow and Wojciech Wawrzyniak. Distributed packing in planar graphs Pierre Fraigniaud and Cyril Gavoille. Polylogarithmic Network Navigability Using Compact Metrics with Small Stretch 12:20 - 1:40: Lunch (provided) 1:40 - 2:40: Invited Talk 2 Arnold Rosenberg, Amherst Where is your dog's belly button? 2:40 - 4:00: Session 3 -- Broadcasting in Networks Chair: Andrea Pietracaprina Moses Charikar, Howard Karloff, Claire Mathieu, Seffi Naor and Michael Saks. Online Multicast with Egalitarian Cost Sharing Emanuele Guido Fusco and Andrzej Pelc. Trade-offs Between the Size of Advice and Broadcasting Time in Trees Baruch Awerbuch and Rohit Khandekar. Cost Sharing Mechanisms for Near-Optimal Traffic Aggregation and Network Design Yaacov Fernandess and Dahlia Malkhi. On Spreading Recommendations via Social Gossip 4:00 - 4:30: Coffee Break 4:30 - 5:30: Session 4 -- Brief Announcements Chair: Christof Fetzer Victor Luchangco. Against Lock-Based Semantics for Transactional Memory 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 Kunal Agrawal, ITing Lee and Jim Sukha. Safe Open-Nested Transactions Through Ownership Torsten Hoefler, Peter Gottschling and Andrew Lumsdaine. Leveraging non-blocking collective communication in high-performance applications Daniel Greenfield and Simon Moore. Fractal Communication in Software Data Dependency Graphs 8:30 - 10:30: Business meeting Sunday, June 15 8:30 - 9:30: Invited Talk 3 Leslie Valiant, Harvard University TBA 9:30 - 10:50: Session 5 -- Graph Algorithms Chair: Danny Hendler 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 Ioannis Koutis and Gary Miller. Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning Warren Schudy. Finding Strongly Connected Components in Parallel using O(log^2 n) Reachability Queries 10:50 - 11:20: Coffee Break 11:20 - 12:20: Session 6 -- Special Track -- Transactional Memory Chair: Panagiota Fatourou Torvald Riegel, Christof Fetzer and Pascal Felber. Automatic Data Partitioning in Software Transactional Memories Michael Spear, Maged Michael and Christoph von Praun. RingSTM: Scalable Transactions with a Single Atomic Instruction Richard Yoo and Hsien-Hsin Lee. Adaptive Transaction Scheduling for Transactional Memory Systems 12:20 - 1:40: Lunch (provided) 1:40 - 2:40: Invited Talk 4 Hagit Attiya, Technion TBA 2:40 - 3:30: Session 7 -- Brief announcements (and in parallel poster session) Chair: Faith Ellen Kai Shen, Alex Zhang, Terence Kelly and Chris Stewart. Operational Analysis of Processor Speed Scaling 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) Yongwook Choi, Maleq Khan, Anil Kumar and Gopal Pandurangan. Energy-Optimal Distributed Algorithms for Minimum Spanning Trees Andre Brinkmann and Sascha Effert. Data Replication in P2P Environments Vittorio Bilo', Angelo Fanelli, Michele Flammini and Luca Moscardelli. Graphical Congestion Games with Linear Latencies 3:30 - 4:00 Coffee Break with continuing poster session 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 4:00 - 5:00: Session 8 Special Track -- Multicore Algorithms Chair: Ravi Rajwar Lars Arge, Michael T. Goodrich, Michael Nelson and Nodari Sitchinava. Fundamental Parallel Algorithms for Private-Cache Chip Multiprocessors Rezaul Chowdhury and Vijaya Ramachandran. Cache-efficient Dynamic Programming Algorithms for Multicores Milind Kulkarni, Keshav Pingali, Ganesh Ramanarayanan, Bruce Walter, Patrick Carribault, Paul Chew and Kavita Bala. Scheduling Strategies for Optimistic Parallel Execution of Irregular Programs 8:00 - 11:00: Banquet dinner at the Spatenhaus Monday, June 16 8:30 - 9:30: Invited Talk 5 Charles Leiserson, MIT Cilk++ 9:30 - 10:50: Session 9 -- Parallel and Distributed Scheduling Chair: Susanne Albers Mauro Sozio and Alessandro Panconesi. Fast Distributed Scheduling via Primal-Dual Indrajit Roy and Nedialko Dimitrov. A Primal-Dual Resource Augmentation Analysis of a Constant Approximate Algorithm for Stable Coalitions in a Cluster Christopher Crutchfield, Zoran Dzunic, Jeremy Fineman, David Karger and Jacob Scott. Improved Approximations for Multiprocessor Scheduling Under Uncertainty Tak-Wah Lam, Lap Kei Lee, Isaac K.K. To and Prudence W.H. Wong. Competitive Non-migratory Scheduling for Flow Time and Energy 10:50 - 11:10: Coffee Break 11:10 - 12:30: Session 10 -- Special Track -- STM Design and Locks Chair: Alexandra Fedorova 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 Eric Koskinen and Maurice Herlihy. Checkpoints and Continuations instead of Nested Transactions Adam Welc, Bratin Saha and Ali-Reza Adl-Tabatabai. Irrevocable Transactions and their Applications Hagit Attiya, Rachid Guerraoui and Eric Ruppert. Partial Snapshot Objects 12:30 - 1:40: Lunch (provided) 1:40 - 2:40: Invited Talk 6 Burton Smith, Microsoft Parallel Computing at Microsoft 2:40 - 3:40: Session 11 -- STM Analysis and Semantics Chair: Pascal Felber Rachid Guerraoui and Michal Kapalka. On Obstruction-Free Transactions Vijay Menon, Steven Balensiefer, Tatiana Shpeisman, Ali-Reza Adl-Tabatabai, Richard Hudson, Bratin Saha and Adam Welc. Practical Weak-Atomicity Semantics for Java STM Rui Zhang, Zoran Budimlic, and William Scherer. Commit Phase in Timestamp-based STM 3:40 - 4:00 Coffee break 4:00 - 5:00 Session 12 -- Algorithms Chair: Rajmohan Rajaraman Eric Koskinen and Maurice Herlihy. Dreadlocks: Efficient Deadlock Detection Ioannis Caragiannis, Christos Kaklamanis, Evangelos Kranakis, Danny Krizanc and Andreas Wiese. Communication in wireless networks with directional antennas Wing Kai Hon, Rahul Shah, Peter Varman and Jeffrey Scott Vitter. Tight Competitive Ratios for Parallel Disk Prefetching and Caching