ACM Transactions on

Parallel Computing (TOPC)

Latest Articles

About TOPC

ACM Transactions on Parallel Computing (TOPC) is a forum for novel and innovative work on all aspects of parallel computing, including foundational and theoretical aspects, systems, languages, architectures, tools, and applications. It will address all classes of parallel-processing platforms including concurrent, multithreaded, multicore, accelerated, multiprocessor, clusters, and supercomputers. 

read more
Forthcoming Articles

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity

Efficient Race Detection for Reducer Hyperobjects

A multithreaded Cilk program that is ostensibly deterministic may nevertheless behave nondeterministically due to programming errors in the code. For a Cilk program that uses reducers, a general reduction mechanism supported in various Cilk dialects, such programming errors are especially challenging to debug, because the errors can expose the nondeterminism in how the Cilk runtime system manages a reducer.

We identify two unique types of races that arise from incorrect use of reducers in a Cilk program and present two algorithms to catch them. The first algorithm, called the Peer-Set algorithm, detects view-read races, which occur when the program attempts to retrieve a value out of a reducer when the read may result a nondeterministic value, such as before all previously spawned subcomputations that might update the reducer have necessarily returned. The second algorithm, called the SP+ algorithm, detects determinacy races, instances where a write to a memory location occurs logically in parallel with another access to that location, even when the raced-on memory locations relate to reducers. Both algorithms are provably correct, asymptotically efficient, and can be implemented efficiently in practice. We have implemented both algorithms in our prototype race detector, Rader. When running Peer-Set, Rader incurs a geometric-mean multiplicative overhead of
2.56 over running the benchmark without instrumentation. When running SP+, Rader incurs a geometric-mean multiplicative overhead of 16.94.

Robust and Probabilistic Failure-Aware Placement

Motivated by the growing complexity and heterogeneity of modern data centers, and the prevalence of commodity component failures, this paper studies the failure-aware placement problem of placing tasks of a parallel job on machines in the data center with the goal of increasing availability. We consider two models of failures: adversarial and probabilistic. In the adversarial model, each node has a weight (higher weight implying higher reliability) and the adversary can remove any subset of nodes of total weight at most a given bound W and our goal is to find a placement that incurs the least disruption against such an adversary. In the probabilistic model, each node has a probability of failure and we need to find a placement that maximizes the probability that at least K out of N tasks survive at any time.

For adversarial failures, we first show that (i) the problems are in Sigma_2, the second level of the polynomial hierarchy, (ii) a basic variant, that we call RobustFAP, is co-NP-hard, and (iii) an all-or-nothing version of RobustFAP is Sigma_2-complete. We then give a PTAS for RobustFAP, a key ingredient of which is a solution that we design for a fractional version of RobustFAP. We then study fractional RobustFAP over hierarchies, denoted HierRobustFAP, and introduce a notion of hierarchical max-min fairness and a novel Generalized Spreading algorithm which is simultaneously optimal for all W. These generalize the classical notion of max-min fairness to work with nodes of differing capacities, differing reliability weights and hierarchical structures. Using randomized rounding, we extend this to give an algorithm for integral HierRobustFAP.

For the probabilistic version, we first give an algorithm that achieves an additive µ approximation in the failure probability for the single level version, called ProbFAP, while giving up a (1+µ) multiplicative factor in the number of failures. We then extend the result to the hierarchical version, HierProbFAP, achieving an µ additive approximation in failure probability while giving up an (L+µ) multiplicative factor in the number of failures, where L is the number of levels in the hierarchy.

Better Bounds for Coalescing-Branching Random Walks

Coalescing-branching random walks, or {\em cobra walks} for short, are a natural variant of random walks on graphs that can model the spread of disease through contacts or the spread of information in networks. In a $k$-cobra walk, at each time step a subset of the vertices are active; each active vertex chooses $k$ random neighbors (sampled independently and uniformly with replacement) that become active at the next step, and these are the only active vertices at the next step. A natural quantity to study for cobra walks is the cover time, which corresponds to the expected time when all nodes have become infected or received the disseminated information.

In this work, we extend previous results for cobra walks in multiple ways. We show that the cover time for the 2-cobra walk on $[0,n]^d$ is $O(n)$ (where the order notation hides constant factors that depend on $d$); previous work had shown the cover time was $O(n \cdot \polylog(n))$. We show that the cover time for a 2-cobra walk on an $n$-vertex $d$-regular graph with conductance $\phi_G$ is $O(d^4 \phi_G^{-2} \log^2 n)$, significantly generalizing a previous result that held only for expander graphs with sufficiently high expansion. And finally we show that the cover time for a 2-cobra walk on a graph with $n$ vertices is always $O(n^{11/4} \log n)$; this is the first result showing that the bound of $\Theta(n^3)$ for the worst-case cover time for random walks can be beaten using 2-cobra walks.

Introduction to Special Issue on SPAA '15

Fast Distributed Algorithms for Connectivity and MST in Large Graphs

Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where $k \geq 2$ machines jointly perform computations on graphs with $n$ nodes (typically, $n \gg k$). The input graph is assumed to be initially randomly partitioned among the $k$ machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation.

Our main result is an (almost) optimal distributed randomized algorithm for graph connectivity. Our algorithm runs in $\tilde{O}(n/k^2)$ rounds ($\tilde{O}$ notation hides a $\polylog(n)$ factor and an additive $\polylog(n)$ term). This improves over the best previously known bound of $\tilde{O}(n/k)$ [Klauck et al., SODA 2015], and is optimal (up to a polylogarithmic factor) in light of an existing lower bound of $\tilde{\Omega}(n/k^2)$. Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. Using the connectivity algorithm as a building block, we then present fast randomized algorithms for computing minimum spanning trees, (approximate) min-cuts, and for many graph verification problems. All these algorithms take $\tilde{O}(n/k^2)$ rounds, and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of $\tilde{\Omega}(n/k^2)$ rounds for many graph verification problems by leveraging lower bounds in random-partition communication complexity.

Lock-free Transactional Transformation

Non-blocking data structures allow scalable and thread-safe accesses to shared data.
They provide individual operations that appear to execute atomically.
However, it is often desirable to execute multiple operations atomically in a transactional manner.
Previous solutions, such as software transactional memory (STM) and transactional boosting, manage transaction synchronization in an external layer separated from the data structure's own thread-level concurrency control.
Although this reduces programming effort, it leads to overhead associated with additional synchronization and the need to rollback aborted transactions.

In this work, we present a new methodology for transforming high-performance lock-free linked data structures into high-performance lock-free transactional linked data structures without revamping the data structures' original synchronization design.
Our approach leverages the semantic knowledge of the data structure to eliminate the overhead of false conflicts and rollbacks.
We encapsulate all operations, operands, and transaction status in a transaction descriptor, which is shared among the nodes accessed by the same transaction.
We coordinate threads to help finish the remaining operations of delayed transactions based on their transaction descriptors.
When transaction fails, we recover the correct abstract state by reversely interpreting the logical status of a node.

In our experimental evaluation using transactions with randomly generated operations, our lock-free transactional lists and skiplist outperform the transactional boosted ones by 40% on average and as much as 125% for large transactions.
They also outperform the alternative STM-based approaches by a factor of 3 to 10 across all scenarios.
More importantly, we achieve 4 to 6 orders of magnitude less spurious aborts than the alternatives.
We also present an obstruction-free version of our algorithm which can be applied to dynamic execution scenarios, and an example of our approach applied to a hash map.


Publication Years 2014-2018
Publication Count 85
Citation Count 76
Available for Download 85
Downloads (6 weeks) 514
Downloads (12 Months) 4217
Downloads (cumulative) 15344
Average downloads per article 181
Average citations per article 1
First Name Last Name Award
Grey Ballard ACM Doctoral Dissertation Award
Honorable Mention (2013) ACM Doctoral Dissertation Award
Honorable Mention (2013)
Guy Blelloch ACM Fellows (2011)
James C Browne ACM Fellows (1998)
James Demmel ACM Paris Kanellakis Theory and Practice Award (2014)
ACM Fellows (1999)
Jack Dongarra ACM-IEEE CS Ken Kennedy Award (2013)
ACM Fellows (2001)
Phillip B Gibbons ACM Fellows (2006)
William D Gropp ACM-IEEE CS Ken Kennedy Award (2016)
SIAM/ACM Prize in Computational Science and Engineering (2014)
ACM Fellows (2006)
David Paul Grove ACM Fellows (2012)
ACM Distinguished Member (2010)
ACM Senior Member (2006)
Rachid Guerraoui ACM Fellows (2012)
Maurice Herlihy ACM Fellows (2005)
Charles E Leiserson ACM-IEEE CS Ken Kennedy Award (2014)
ACM Paris Kanellakis Theory and Practice Award (2013)
ACM Fellows (2006)
ACM Doctoral Dissertation Award (1982)
Michael Mitzenmacher ACM Fellows (2014)
John Douglas Owens ACM Distinguished Member (2017)
Mooly Sagiv ACM Fellows (2015)
Vijay Saraswat ACM Doctoral Dissertation Award (1989)
Michael Scott ACM Fellows (2006)
Nir N Shavit ACM Fellows (2013)
Julian Shun ACM Doctoral Dissertation Award (2015)
Aravind Srinivasan ACM Fellows (2014)
Guy L Steele ACM Fellows (1994)
ACM Grace Murray Hopper Award (1988)
Guy L Steele ACM Fellows (1994)
ACM Grace Murray Hopper Award (1988)

First Name Last Name Paper Counts
Grey Ballard 3
Nicholas Knight 3
Charles Leiserson 3
Benjamin Moseley 2
Joseph Naor 2
Tao Schardl 2
Peter Kling 2
James Demmel 2
Dan Alistarh 2
Andrew Davidson 2
John Owens 2
Nir Shavit 2
William Hasenplaugh 2
Guy Blelloch 2
Chinmoy Dutta 1
Gopal Pandurangan 1
Andrea Vattani 1
Thomas Groß 1
Christian Scheideler 1
Yves Robert 1
Hafiz Sheikh 1
Ishfaq Ahmad 1
Rachid Guerraoui 1
Rupesh Nasre 1
Charles Bachmeier 1
Tim Harris 1
William Gropp 1
Gokcen Kestor 1
Serdar Tasiran 1
Maurice Herlihy 1
Xavier Martorell 1
Olivier Tardieu 1
Walther Maldonado 1
Paul Thomson 1
Dave Dice 1
Aurélien Bouteiller 1
Thomas Hérault 1
William Gropp 1
Andrew Grimshaw 1
Jianjia Chen 1
Ishai Menache 1
Stephen Siegel 1
Bo Zhao 1
Mahesh Ravishankar 1
Ponnuswamy Sadayappan 1
Xing Wu 1
Matthieu Dorier 1
Gabriel Antoniu 1
Sungjin Im 1
William Leiserson 1
Davide Bilò 1
Luciano Gualà 1
Yu Wang 1
Kadir Akbudak 1
Oguz Selvitopi 1
Sergei Vassilvitskii 1
Shenchen Xu 1
Minjia Zhang 1
Saurabh Kalikar 1
Bradley Kuszmaul 1
Yuan Tang 1
Yuechao Pan 1
Yuduo Wu 1
Carl Yang 1
James Dinan 1
Wickus Nienaber 1
Guy Steele 1
Paolo Romano 1
Darko Petrović 1
George Teodoro 1
Adam Betts 1
Oliver Sinnen 1
Torsten Hoefler 1
Johannes Hagemann 1
Youtao Zhang 1
Jagannathan Ramanujam 1
Francis O'Connell 1
Robert Sisneros 1
Tim Kaler 1
Bruce Mealey 1
Rajeev Barua 1
Kirk Pruhs 1
Eric Torng 1
Tareq Malas 1
Ioana Bercea 1
David Harris 1
Raoul Steffen 1
Scott Roche 1
Vijaya Ramachandran 1
Mooly Sagiv 1
Jeffrey Blanchard 1
Erik Opavsky 1
Lukas Arnold 1
Aurélien Cavelan 1
Aritra Sengupta 1
Marina Papatriantafilou 1
Rezaul Chowdhury 1
Weitang Liu 1
Santosh Mahapatra 1
Zhiyu Liu 1
Vijay Saraswat 1
Mandana Vaziri 1
Pascal Felber 1
Étienne Rivière 1
Lionel Eyraud-Dubois 1
Frédéric Vivien 1
Paul Sack 1
Santiago Pagani 1
Moran Feldman 1
Liane Lewin-Eytan 1
Yi Xu 1
Jun Yang 1
Louis Pouchet 1
Scott Pakin 1
Pradip Bose 1
Erin Carson 1
Phillip Gibbons 1
Aapo Kyrola 1
Michele Scquizzato 1
Chaodong Zheng 1
I Lee 1
Jim Sukha 1
Joseph Izraelevitz 1
Zoltan Majo 1
Anne Benoit 1
Hongyang Sun 1
Ioannis Koutis 1
Ulrich Meyer 1
Armando Solar-Lezama 1
Brandon Lucia 1
Leyuan Wang 1
Muhammad Osama 1
Chenshan Yuan 1
Rajeev Thakur 1
Jean Tristan 1
Nuno Diegues 1
Osman Ünsal 1
Eduard Ayguadé 1
Alba De Melo 1
Avraham Shinnar 1
Mikio Takeuchi 1
Virendra Marathe 1
Michael Garland 1
Laxmikant Kale 1
Stephan Kramer 1
Jörg Henkel 1
Andrew Siegel 1
Atanas Rountev 1
Frank Mueller 1
Timothy Heil 1
Anil Krishna 1
Roberto Gioiosa 1
Marc Snir 1
Shadi Ibrahim 1
Leigh Orf 1
Ronghua Liang 1
Navin Goyal 1
Guido Proietti 1
Aravind Srinivasan 1
Cevdet Aykanat 1
Rajmohan Rajaraman 1
Michael Scott 1
Felix Wolf 1
Uday Bondhugula 1
Yiannis Nikolakopoulos 1
Man Cao 1
Swarnendu Biswas 1
Syed Haider 1
Yangzihao Wang 1
Thomas Ropars 1
Guillermo Miranda 1
Julia Lawall 1
Duane Merrill 1
Ehsan Totoni 1
Nikhil Jain 1
Adam Hammouda 1
John Eisenlohr 1
Farnaz Toussi 1
Ashay Rane 1
Francisco Cazorla 1
Franck Cappello 1
Jeremy Fineman 1
Georg Hager 1
Hatem Ltaief 1
Sem&idot;h şah&idot;n 1
Buǧra Ged&idot;k 1
Jun Wang 1
Seth Gilbert 1
Peter Sanders 1
Jochen Speck 1
Ravi Kumar 1
Guy Golan-Gueta 1
Ganesan Ramalingam 1
Felix Voigtlaender 1
Vincenzo Gulisano 1
Daniel Cederman 1
Philippas Tsigas 1
Aleksandar Dragojević 1
Mary Hall 1
Patrick Marlier 1
Jack Dongarra 1
Loris Marchal 1
George Bosilca 1
Jonathan Yaniv 1
Sebastian Kobbe 1
Ciaran McCreesh 1
Bastian Degener 1
Friedhelm Heide 1
Julian Shun 1
Steven Vanderwiel 1
Sudipto Guha 1
Jiayang Jiang 1
Michael Mitzenmacher 1
David Keyes 1
Alex Druinsky 1
Harsha Simhadri 1
Alexander Matveev 1
Gianfranco Bilardi 1
Eran Yahav 1
Peter Pietrzyk 1
Richard Cole 1
Emircan Uysaler 1
David Böhme 1
Markus Geimer 1
Michael Bond 1
Georgios Chatzopoulos 1
Jesmin Tithi 1
Stephen Tschudi 1
Andy Riffel 1
Pavan Balaji 1
Keith Underwood 1
Xin Yuan 1
Edans De O. Sandes 1
Benjamin Herta 1
David Grove 1
Prabhanjan Kambadur 1
Alastair Donaldson 1
Saeed Maleki 1
Kookjin Ahn 1
Madanlal Musuvathi 1
Todd Mytkowicz 1
Peng Du 1
Navendu Jain 1
Janmartin Jahn 1
Patrick Prosser 1
James Browne 1
Orcun Yildiz 1
Tom Peterka 1
Justin Thaler 1
Timothy Creech 1
Stefano Leucci 1
Francesco Silvestri 1
Zhunping Zhang 1
Martina Eikel 1
Roshan Dathathri 1
Ravi Mullapudi 1
Saman Ashkiani 1
Pramod Ganapathi 1
Brian Barrett 1
Wei Zhang 1
David Cunningham 1
Adrián Cristal 1
André Schiper 1
Gilles Muller 1
Barbara Kempkes 1
Nicholas Lindberg 1
Víctor Jiménez 1
Alper Buyuktosunoglu 1
Edgar Solomonik 1
Oded Schwartz 1
Jiaquan Gao 1

Affiliation Paper Counts
IBM, Japan 1
Lawrence Livermore National Laboratory 1
University of Sassari 1
Universite de Bordeaux 1
Microsoft Research Cambridge 1
Fudan University 1
Huawei Technologies Co., Ltd., USA 1
University of California , Merced 1
Yahoo Research Labs 1
University of Puerto Rico 1
Wake Forest University 1
University of Wisconsin Madison 1
Michigan State University 1
Hebrew University of Jerusalem 1
University of California, San Diego 1
Tel Aviv University 1
University of California, Los Angeles 1
University of Roma Tor Vergata 1
Goethe University Frankfurt 1
Louisiana State University 1
University of Auckland 1
Technical University of Darmstadt 1
University of Houston 1
RWTH Aachen University 1
Los Alamos National Laboratory 1
Twitter, Inc. 1
Georgia Institute of Technology 1
Nanjing Normal University 1
University of Erlangen-Nuremberg 1
University of Virginia 1
University of Connecticut 1
University of Delaware 1
Koc University 1
Georgetown University 1
University of Utah 1
Spanish National Research Council 1
Institute of Science and Technology Austria 1
Universite de Lyon 2
King Abdullah University of Science and Technology 2
University of Gottingen 2
Northeastern University 2
University of Rochester 2
Zhejiang University of Technology 2
Indian Institute of Technology, Madras 2
Pacific Northwest National Laboratory 2
New York University 2
University of L'Aquila 2
National University of Singapore 2
Brown University 2
Washington University in St. Louis 2
Sandia National Laboratories, New Mexico 2
University of Pennsylvania 2
Google Inc. 2
Instituto Superior Tecnico 2
North Carolina State University 2
University of Texas at Arlington 2
University of Glasgow 2
University of Padua 3
Florida State University 3
Lawrence Berkeley National Laboratory 3
Universitat Politecnica de Catalunya 3
Harvard University 3
INRIA Institut National de Rechereche en Informatique et en Automatique 3
Indian Institute of Science, Bangalore 3
Imperial College London 3
University of Brasilia 3
Stony Brook University 3
Grinnell College 3
Barcelona Supercomputing Center 3
Swiss Federal Institute of Technology, Zurich 4
Bilkent University 4
University of Neuchatel 4
University of Texas at Austin 4
Ecole Normale Superieure de Lyon 4
Chalmers University of Technology 5
Intel Corporation 5
Swiss Federal Institute of Technology, Lausanne 5
Technion - Israel Institute of Technology 5
University of Maryland 5
University of Tennessee, Knoxville 5
University of Pittsburgh 5
Carnegie Mellon University 6
Massachusetts Institute of Technology 6
Microsoft Research 7
University of California, Berkeley 7
Ohio State University 7
Karlsruhe Institute of Technology 8
University of Illinois at Urbana-Champaign 8
MIT Computer Science and Artificial Intelligence Laboratory 8
University of Paderborn 8
Argonne National Laboratory 8
IBM Thomas J. Watson Research Center 11
University of California, Davis 14

ACM Transactions on Parallel Computing (TOPC)

Volume 4 Issue 4, May 2018  Issue-in-Progress
Volume 4 Issue 3, April 2018

Volume 4 Issue 2, October 2017 Special Issue: Invited papers from PPoPP 2016, Part 2
Volume 4 Issue 1, October 2017 Special Issue: Invited papers from PPoPP 2016, Part 1
Volume 3 Issue 4, March 2017 Special Issue on PPoPP 2015 and Regular Papers

Volume 3 Issue 3, December 2016
Volume 3 Issue 2, August 2016
Volume 3 Issue 1, June 2016 Special Issue for SPAA 2014
Volume 2 Issue 4, March 2016 Special Issue on PPOPP 2014

Volume 2 Issue 3, October 2015 Special Issue for SPAA 2013
Volume 2 Issue 2, July 2015
Volume 2 Issue 1, May 2015 Special Issue on SPAA 2012
Volume 1 Issue 2, January 2015 Special Issue on PPOPP 2012

Volume 1 Issue 1, September 2014 Inaugural Issue and Special Section on Top Papers from PACT-21, and Regular Papers
All ACM Journals | See Full Journal Index

Search TOPC
enter search term and/or author name