Executing functional programs on a virtual tree of processors. In Algorithms and Data Structures, volume 1663 of LNCS. Resizable arrays in optimal time and space. The anatomy of a large-scale hypertextual Web search engine. The parallel evaluation of general arithmetic expressions. In First USENIX Conference on Hot Topics in Parallelism, 2009. Parallel programming must be deterministic by default. ![]() Technical Report, University of Texas at Austin, 1999. Hood: A user-level threads library for multiprogrammed multiprocessors. Scheduling multithreaded computations by work stealing. Space-efficient scheduling of multithreaded computations. A comparison of sorting algorithms for the Connection Machine CM-2. In Proceedings of Principles and Practice of Parallel Programming, pp. Internally deterministic parallel algorithms can be fast. Technical Report CS-92-103, Carnegie Mellon University, Pittsburgh, PA, 1992. Technical Report Carnegie Mellon University-CS-90-190, School of Computer Science, Carnegie Mellon University, 1990. The PARSEC benchmark suite: Characterization and architectural implications. Parallel and Distributed Computation: Numerical Methods. Grace: Safe multithreaded programming for C/C++ In OOPSLA, 2009. CoreDet: A compiler and runtime system for deterministic multithreaded execution. The Habanero multicore software research project. phHandbook of Scheduling 1)$-coloring in linear (in Δ) time. Group formation in large social networks: membership, growth, and evolution. A fast and simple randomized parallel algorithm for the maximal independent set problem. The Fortress Language Specification Version 1.0. A multi-color SOR method for parallel computation. PRISM-R satisfies the same theoretical bounds as PRISM, but its implementation is more involved, incorporating a multivector data structure to maintain an ordered set of vertices partitioned by color. ![]() ![]() This paper also presents PRISM-R, a variation of PRISM that executes dynamic data-graph computations deterministically even when updates modify global variables with associative operations. PRISM executes the benchmarks 1.2–2.1 times faster than GraphLab's nondeterministic lock-based scheduler while providing deterministic behavior. ![]() We modified GraphLab to incorporate PRISM and studied seven application benchmarks on a 12-core multicore machine. These theoretical guarantees are matched by good empirical performance. We show that a P-processor execution of PRISM performs updates in Q using O(Χ(lg (Q/Χ)+lgΔ)+ lgP) span and Θ(size(Q)+Χ+P) work. Define size(Q)= + Σ v∈Qdeg(v), which is proportional to the space required to store the vertices of Q using a sparse-graph layout. Let G=(V,E) be a degree-Δ graph colored with Χ colors, and suppose that Q⊆V is the set of active vertices in a round. We analyze PRISM using work-span analysis. A multibag data structure is used by PRISM to maintain a dynamic set of active vertices as an unordered set partitioned by color. PRISM uses a vertex-coloring of the graph to coordinate updates performed in a round, precluding the need for mutual-exclusion locks or other nondeterministic data synchronization. This paper introduces PRISM, a chromatic-scheduling algorithm for executing dynamic data-graph computations. A dynamic data-graph computation updates only an active subset of the vertices during a round, and those updates determine the set of active vertices for the next round. During each round of a data-graph computation, an update function atomically modifies the data associated with a vertex as a function of the vertex's prior data and that of adjacent vertices. 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.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |