enter search term and/or author name
Executing Dynamic Data-Graph Computations Deterministically Using Chromatic Scheduling
Tim Kaler, William Hasenplaugh, Tao B. Schardl, Charles E. Leiserson
Article No.: 2
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
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
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
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...
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...
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...
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...