ACM DL

ACM Transactions on

Parallel Computing (TOPC)

Menu
Latest Articles

Multidimensional Intratile Parallelization for Memory-Starved Stencil Computations

A Lower Bound Technique for Communication in BSP

NEWS

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
Efficiently Detecting Races in Cilk Programs That Use 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.

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.

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.

ThreadScan: Automatic and Scalable Memory Reclamation

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.

C-Stream: A Coroutine-based Elastic Stream Processing Engine

Stream processing is a computational paradigm for on-the-fly processing of live data. This paradigm lends itself to implementations that can provide high throughput and low latency, by taking advantage of various forms of parallelism that is naturally captured by the stream processing model of computation, such as pipeline, task, and data parallelism. In this paper, we describe the design and implementation of C-Stream, which is an elastic stream processing engine. C-Stream encompasses three unique properties. First, in con- trast to the widely adopted event-based interface for developing streaming operators, C-Stream provides an interface wherein each operator has its own driver loop and rely on data availability APIs to decide when to perform its computations. The self-control based model significantly simplifies development of operators that require multi-port synchronization. Second, C-Stream contains a dynamic scheduler that manages the multi-threaded execution of the operators. The scheduler, which is customizable via plug-ins, enables the execution of the operators as co-routines, using any number of threads. The base scheduler implements back-pressure, provides data availability APIs, and manages preemption and termination handling. Last, C-Stream provides elastic parallelization. It can dynamically adjust the number of threads used to execute an application, and can also adjust the number of replicas of data-parallel operators to resolve bottlenecks. We provide an experimental evaluation of C-Stream. The results show that C-Stream is scalable, highly customizable, and can resolve bottlenecks by dynamically adjusting the level of data parallelism used.

Bibliometrics

Publication Years 2014-2018
Publication Count 83
Citation Count 76
Available for Download 83
Downloads (6 weeks) 474
Downloads (12 Months) 4223
Downloads (cumulative) 14943
Average downloads per article 180
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
Charles Leiserson 3
Grey Ballard 3
Nicholas Knight 3
Joseph Naor 2
Tao Schardl 2
Peter Kling 2
James Demmel 2
Andrew Davidson 2
Benjamin Moseley 2
John Owens 2
William Hasenplaugh 2
Guy Blelloch 2
Benjamin Herta 1
Prabhanjan Kambadur 1
Todd Mytkowicz 1
Alastair Donaldson 1
Saeed Maleki 1
Madanlal Musuvathi 1
Peng Du 1
Janmartin Jahn 1
Patrick Prosser 1
Navendu Jain 1
James Browne 1
Orcun Yildiz 1
Tom Peterka 1
Timothy Creech 1
Stefano Leucci 1
Francesco Silvestri 1
Justin Thaler 1
Zhunping Zhang 1
Martina Eikel 1
Roshan Dathathri 1
Ravi Mullapudi 1
Dan Alistarh 1
Saman Ashkiani 1
Pramod Ganapathi 1
Brian Barrett 1
Wei Zhang 1
Adrián Cristal 1
André Schiper 1
David Cunningham 1
Gilles Muller 1
Barbara Kempkes 1
Nicholas Lindberg 1
Alper Buyuktosunoglu 1
Víctor Jiménez 1
Oded Schwartz 1
Edgar Solomonik 1
Jiaquan Gao 1
Mahesh Ravishankar 1
Ponnuswamy Sadayappan 1
Luciano Gualà 1
Ishai Menache 1
Xing Wu 1
Matthieu Dorier 1
Gabriel Antoniu 1
Davide Bilò 1
Kadir Akbudak 1
Oguz Selvitopi 1
Yu Wang 1
Sungjin Im 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
Oliver Sinnen 1
Adam Betts 1
Johannes Hagemann 1
Youtao Zhang 1
Jagannathan Ramanujam 1
Francis O'Connell 1
Robert Sisneros 1
Rajeev Barua 1
Tareq Malas 1
Tim Kaler 1
Bruce Mealey 1
Eric Torng 1
Kirk Pruhs 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
Marina Papatriantafilou 1
Aritra Sengupta 1
Rezaul Chowdhury 1
Weitang Liu 1
Santosh Mahapatra 1
Chinmoy Dutta 1
Gopal Pandurangan 1
Andrea Vattani 1
Thomas Groß 1
Christian Scheideler 1
Hafiz Sheikh 1
Ishfaq Ahmad 1
Yves Robert 1
Rachid Guerraoui 1
Rupesh Nasre 1
Charles Bachmeier 1
Tim Harris 1
Serdar Tasiran 1
Torsten Hoefler 1
William Gropp 1
Gokcen Kestor 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
Stephen Siegel 1
Bo Zhao 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
Yi Xu 1
Jun Yang 1
Louis Pouchet 1
Scott Pakin 1
Moran Feldman 1
Liane Lewin-Eytan 1
Pradip Bose 1
Erin Carson 1
Michele Scquizzato 1
Phillip Gibbons 1
Aapo Kyrola 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
Nir Shavit 1
Michael Garland 1
Stephan Kramer 1
Laxmikant Kale 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
Cevdet Aykanat 1
Guido Proietti 1
Ronghua Liang 1
Navin Goyal 1
Aravind Srinivasan 1
Rajmohan Rajaraman 1
Michael Scott 1
Uday Bondhugula 1
Felix Wolf 1
Yiannis Nikolakopoulos 1
Swarnendu Biswas 1
Man Cao 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
Georg Hager 1
Hatem Ltaief 1
Jun Wang 1
Jeremy Fineman 1
Seth Gilbert 1
Peter Sanders 1
Jochen Speck 1
Ravi Kumar 1
Guy Golan-Gueta 1
Ganesan Ramalingam 1
Felix Voigtlaender 1
Philippas Tsigas 1
Vincenzo Gulisano 1
Daniel Cederman 1
Aleksandar Dragojević 1
Mary Hall 1
Kookjin Ahn 1
Sudipto Guha 1
Patrick Marlier 1
Loris Marchal 1
George Bosilca 1
Jack Dongarra 1
Friedhelm Heide 1
Bastian Degener 1
Sebastian Kobbe 1
Ciaran McCreesh 1
Jonathan Yaniv 1
Steven Vanderwiel 1
Julian Shun 1
David Keyes 1
Alex Druinsky 1
Gianfranco Bilardi 1
Harsha Simhadri 1
Jiayang Jiang 1
Michael Mitzenmacher 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
Stephen Tschudi 1
Jesmin Tithi 1
Andy Riffel 1
Pavan Balaji 1
Keith Underwood 1
Xin Yuan 1
David Grove 1
Edans De O. Sandes 1

Affiliation Paper Counts
IBM, Japan 1
Spanish National Research Council 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
Lawrence Livermore National Laboratory 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
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
University of Sassari 1
Universite de Lyon 2
King Abdullah University of Science and Technology 2
NVIDIA 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
Bilkent University 3
Imperial College London 3
Massachusetts Institute of Technology 3
University of Brasilia 3
Stony Brook University 3
Grinnell College 3
Barcelona Supercomputing Center 3
Swiss Federal Institute of Technology, Zurich 4
University of Texas at Austin 4
University of Neuchatel 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
Microsoft Research 7
University of California, Berkeley 7
IBM, USA 7
Ohio State University 7
MIT Computer Science and Artificial Intelligence Laboratory 8
University of Illinois at Urbana-Champaign 8
Karlsruhe Institute of Technology 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)
Archive


2018
Volume 4 Issue 3, February 2018  Issue-in-Progress
Volume 4 Issue 4, January 2018  Issue-in-Progress

2017
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

2016
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

2015
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

2014
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