NDLI: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '16)

Please wait, while we are loading the content...

Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation)

On Computational Thinking, Inferential Thinking and Data Science

Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers

RUBIC: Online Parallelism Tuning for Co-located Transactional Memory Applications

Cache-Adaptive Analysis

General Profit Scheduling and the Power of Migration on Heterogeneous Machines

A Multicore Path to Connectomics-on-Demand

Robust and Probabilistic Failure-Aware Placement

Just Join for Parallel Ordered Sets

Universal Shape Formation for Programmable Matter

Lock-free Transactions without Rollbacks for Linked Data Structures

The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets

The Cost of Unknown Diameter in Dynamic Networks

Parallel Shortest Paths Using Radius Stepping

Parallel Algorithms for Summing Floating-Point Numbers

A Practical Solution to the Cactus Stack Problem

Extending TM Primitives using Low Level Semantics

Parallel Algorithms for Asymmetric Read-Write Costs

The Power of Migration in Online Machine Minimization

Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks

Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis

Asymptotically Optimal Gathering on a Grid

Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?

Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration

Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity

Latency-Hiding Work Stealing: Scheduling Interacting Parallel Computations with Work Stealing

Investigating the Performance of Hardware Transactions on a Multi-Socket Machine

Brief Announcement: Preserving Happens-before in Persistent Memory

Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines

Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time

Parallel Approaches to the String Matching Problem on the GPU

Better Bounds for Coalescing-Branching Random Walks

Fast and Robust Memory Reclamation for Concurrent Data Structures

Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures

Fast Distributed Algorithms for Connectivity and MST in Large Graphs

Parallelism in Randomized Incremental Algorithms

Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications

Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs

Brief Announcement: Transactional Data Structure Libraries

Brief Announcement: Approximating the I/O Complexity of One-Shot Red-Blue Pebbling

Scheduling Parallelizable Jobs Online to Minimize the Maximum Flow Time

Brief Announcement: Improved Approximation Algorithms for Scheduling Co-Flows

Brief Announcement: MIC++: Accelerating Maximal Information Coefficient Calculation with GPUs and FPGAs

Brief Announcement: Benchmarking Concurrent Priority Queues:

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond

Brief Announcement: A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications

Brief Announcement: Dynamic Determinacy Race Detection for Task Parallelism with Futures

Brief Announcement: A QPTAS for Non-preemptive Speed-scaling

Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables

Brief Announcement: Relaxed Byzantine Vector Consensus

Brief Announcement: Energy Optimization of Memory Intensive Parallel Workloads

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '16)

Content Provider	ACM Digital Library
Editor	Gilbert, Seth Scheideler, Christian
Copyright Year	2016
Abstract	It is my great pleasure to welcome you to the 28thACM Symposium on Parallelism in Algorithms and Architectures. The goal of SPAA is to develop a deeper understanding of parallelism in all its forms, bringing together the theory and practice of parallel computing. This year's program reflects that goal, with a diverse selection of papers at the cutting edge of parallel computing. The program includes 38 regular papers and 14 brief announcements, as well as keynote talks by Michael I. Jordan and Nir Shavit. Traditional topics in parallelism are well represented at SPAA this year. The program includes papers on parallel algorithms for classical questions (e.g., sorting and graph problems, see Sessions 9 and 14). It includes papers on scheduling parallel computations (see Session 3) and scheduling tasks in parallel systems (see Sessions 6 and 8). The program also includes papers on concurrent data structures (see Session 11), and on parallelism in distributed systems (see Session 13). These topics all have a long history at SPAA. Over the last several years, the study of parallelism has expanded to include new models of parallel computation (e.g., Map-Reduce, see Session 1), new architectures (e.g., GPUs, see Session 9), new techniques for managing parallelism (e.g., transactional memory, see Session 4), and new types of parallel systems (e.g., programmable matter, see Session 10). These increasingly important topics are represented at SPAA this year. The best paper award for SPAA 2016 is awarded to a paper focusing on the limitations of certain new models of parallel computation: Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation) by Tim Roughgarden, Sergei Vassilvitskii and Joshua Wang. The authors develop lower bounds on the speed of large-scale parallel computation in a model meant to capture the capabilities of Map-Reduce and Hadoop. They discover an important connection between these computations and polynomials representing boolean functions, and use this fact to show lower bounds for a variety of natural and important problems. We would also like to recognize (in no particular order) three finalists for the best paper award: Randomized approximate nearest neighbor search with limited adaptivity by Mingmou Liu, Xiaoyin Pan and Yitong Yin. Robust and Probabilistic Failure-Aware Placement by Madhukar Korupolu and Rajmohan Rajaraman. Lock-free Transactions without Aborts for Linked Data Structures by Deli Zhang and Damian Dechev These papers highlight the variety of exciting work in parallelism that is represented at SPAA 2016.
ISBN	9781450342100
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-11
Access Restriction	Subscribed
Content Type	Text
Resource Type	Conference Proceedings

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA '15)

Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (SPAA '14)

Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '17)

Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '06)

Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '04)

Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '05)

Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '13)

Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '12)

Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures (SPAA '11)

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '16)

Similar Documents

Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA '15)

Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (SPAA '14)

Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '17)

Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '06)

Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '04)

Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '05)

Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '13)

Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '12)

Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures (SPAA '11)

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '16)