Parallel Computing (TOPC)


Search Issue
enter search term and/or author name


ACM Transactions on Parallel Computing (TOPC) - Special Issue for SPAA 2014, Volume 3 Issue 1, June 2016

Section: Special Issue for SPAA 2014

Introduction to the Special Issue on SPAA 2014
Friedhelm Meyer auf der Heide, Peter Sanders, Nodari Sitchinava
Article No.: 1
DOI: 10.1145/2936716

Executing Dynamic Data-Graph Computations Deterministically Using Chromatic Scheduling
Tim Kaler, William Hasenplaugh, Tao B. Schardl, Charles E. Leiserson
Article No.: 2
DOI: 10.1145/2896850

A data-graph computation—popularized by such programming systems as Galois, Pregel, GraphLab, PowerGraph, and GraphChi—is an algorithm that performs local updates on the vertices of a graph. During each round of a data-graph...

Trade-Offs Between Synchronization, Communication, and Computation in Parallel Linear Algebra Computations
Edgar Solomonik, Erin Carson, Nicholas Knight, James Demmel
Article No.: 3
DOI: 10.1145/2897188

This article derives trade-offs between three basic costs of a parallel algorithm: synchronization, data movement, and computational cost. These trade-offs are lower bounds on the execution time of the algorithm that are independent of the number...

Competitively Scheduling Tasks with Intermediate Parallelizability
Sungjin Im, Benjamin Moseley, Kirk Pruhs, Eric Torng
Article No.: 4
DOI: 10.1145/2938378

We introduce a scheduling algorithm Intermediate-SRPT, and show that it is O(logP)-competitive with respect to average flow time when scheduling jobs whose parallelizability is intermediate between being fully parallelizable and...

On Computing Maximal Independent Sets of Hypergraphs in Parallel
Ioana O. Bercea, Navin Goyal, David G. Harris, Aravind Srinivasan
Article No.: 5
DOI: 10.1145/2938436

Whether or not the problem of finding maximal independent sets (MIS) in hypergraphs is in (R)NC is one of the fundamental problems in the theory of parallel computing. Essentially, the challenge is to design (randomized) algorithms in which the...

Locality-Based Network Creation Games
Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti
Article No.: 6
DOI: 10.1145/2938426

Network creation games have been extensively studied, both by economists and computer scientists, due to their versatility in modeling individual-based community formation processes. These processes, in turn, are the theoretical counterpart of...

Parallel Peeling Algorithms
Jiayang Jiang, Michael Mitzenmacher, Justin Thaler
Article No.: 7
DOI: 10.1145/2938412

The analysis of several algorithms and data structures can be framed as a peeling process on a random hypergraph: vertices with degree less than k are removed until there are no vertices of degree less than k left. The...

Experimental Analysis of Space-Bounded Schedulers
Harsha Vardhan Simhadri, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Aapo Kyrola
Article No.: 8
DOI: 10.1145/2938389

The running time of nested parallel programs on shared-memory machines depends in significant part on how well the scheduler mapping the program to the machine is optimized for the organization of caches and processor cores on the machine. Recent...