PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphLab: A New Framework For Parallel Machine Learning

Yucheng Low, Joseph E. Gonzalez, Aapo Kyrola, Danny Bickson, Carlos E. Guestrin, Joseph Hellerstein

arXiv:1408.2041v1cs.LGcs.DC

TL;DR

Parallel ML algorithms are challenging to implement efficiently and correctly, while existing abstractions have limitations in representing structured dependencies and iterative computation. GraphLab targets common ML patterns with a graph-based framework, and its real-world case studies report state-of-the-art performance.

  • Problem

    Efficient, provably correct parallel ML is challenging, and existing abstractions have limitations in representing structured dependencies and iterative algorithms.

    Source: §1 · p. 1, §2.1 · p. 2, §2.2 · p. 2

  • Method

    GraphLab uses a graph-based framework to express sparse dependencies and asynchronous iterative computation while providing data-consistency guarantees.

    Source: §1 · p. 1, §5 · p. 10

  • Results

    The case studies report state-of-the-art performance for popular ML algorithms applied to large real-world datasets.

    Source: §1 · p. 1, §5 · p. 10

  • Takeaways & Limitations

    GraphLab supports structured dependencies, iterative computation, and flexible scheduling in a parallel ML abstraction.

    Source: §5 · p. 10

    The Gibbs sampler has a strong sequential component because the model needs 20 colors and its vertex distribution over colors is heavily skewed.

    Source: §4.2 · p. 7

Abstract

from arXiv · show

Designing and implementing efficient, provably correct parallel machine learning (ML) algorithms is challenging. Existing high-level parallel abstractions like MapReduce are insufficiently expressive while low-level tools like MPI and Pthreads leave ML experts repeatedly solving the same design challenges. By targeting common patterns in ML, we developed GraphLab, which improves upon abstractions like MapReduce by compactly expressing asynchronous iterative algorithms with sparse computational dependencies while ensuring data consistency and achieving a high degree of parallel performance. We demonstrate the expressiveness of the GraphLab framework by designing and implementing parallel versions of belief propagation, Gibbs sampling, Co-EM, Lasso and Compressed Sensing. We show that using GraphLab we can achieve excellent parallel performance on large scale real-world problems.

1 INTRODUCTION

GraphLab targets the challenge of efficient, correct parallel ML by expressing sparse dependencies and common ML patterns. The paper presents its framework and shared-memory implementation, then reports state-of-the-art performance in its evaluations.

1 INTRODUCTION

  • The shift from frequency scaling toward parallel scaling makes parallelism increasingly important as ML addresses more challenging real-world problems.Source: §1 · p. 1
  • Parallel ML is difficult to implement efficiently and correctly; MapReduce can restrict algorithms or yield inefficient parallel versions when sequential methods are coerced to fit.Low-level tools such as MPI and Pthreads leave users to address parallel-computing challenges.Source: §1 · p. 1
  • GraphLab combines problem-specific computation, data dependencies, and scheduling to help ML experts implement scalable parallel algorithms.Its contributions include a graph-based data model, consistency models, modular scheduling, and aggregation.Source: §1 · p. 1
  • On a 16-processor system, GraphLab algorithms demonstrate state-of-the-art performance.The introduction says the framework builds parallel versions of four popular ML algorithms.Source: §1 · p. 1

2 EXISTING FRAMEWORKS

The section reviews how existing parallel abstractions trade expressiveness against the needs of ML algorithms. MapReduce, DAG, and Systolic abstractions each leave important computational patterns or schedules unsupported.

2 EXISTING FRAMEWORKS

  • GraphLab is presented as a generalization of existing frameworks that addresses critical limitations in parallel ML abstractions.Source: §2 · p. 2

2.1 MAP-REDUCE ABSTRACTION

  • MapReduce suits independent parallel tasks but cannot represent overlapping data dependencies or directly encode iterative computation and its scheduling or termination.These restrictions make it difficult to represent structured models and can lead researchers to favor simpler methods.Source: §2.1 · p. 2
  • The GraphLab implementation assumes shared memory and non-failing processors, and does not address fault tolerance or parallel disk access.A distributed, fault-tolerant implementation is described as ongoing research.Source: §2.1 · p. 2

2.2 DAG ABSTRACTION

  • DAG abstractions require the iteration count to be known in advance and do not express dynamically prioritized computation.Source: §2.2 · p. 2

2.3 SYSTOLIC ABSTRACTION

  • Systolic abstractions support iteration but restrict ML schedules, including Gauss-Seidel coordinate descent and dynamic structured schedules.Their lockstep computation uses a barrier between iterations.Source: §2.3 · p. 2

3 THE GRAPHLAB ABSTRACTION

GraphLab balances high-level usability with the expressiveness needed for sparse dependencies and asynchronous iterative ML. Its data graph and consistency models address coordination concerns while scheduling supports dynamic computation.

3 THE GRAPHLAB ABSTRACTION

  • GraphLab insulates users from synchronization, data races, and deadlocks through its data graph and configurable consistency guarantees.Source: §3 · p. 2
  • Unlike MapReduce, GraphLab represents complex computational dependencies and supports iterative parallel algorithms with dynamic scheduling.Source: §3 · p. 3
  • Loopy BP on pairwise Markov Random Fields serves as the running example for the framework.BP iteratively recomputes edge messages to estimate marginal distributions.Source: §3 · p. 3

3.1 DATA MODEL

GraphLab represents both sparse computational structure and program state in a directed data graph, while a shared data table holds globally shared state.

3.1 DATA MODEL

  • The directed data graph encodes sparse computational structure and modifiable state, with arbitrary data blocks associated with vertices and directed edges.Source: §3.1 · p. 3
  • A shared data table maps keys to values for globally shared state; in Loopy BP it can hold shared hyperparameters and convergence progress.Source: §3.1 · p. 3

3.2 USER DEFINED COMPUTATION

GraphLab separates local graph-based updates from global aggregation, with scopes defining what each update can access and modify. Its sync mechanism aggregates graph-wide data into shared state, either on demand or in the background.

3.2.1 Update Functions

  • Update functions perform local computation over a vertex's scope, which includes its data, incident edges, and neighboring vertices.They are stateless user-defined functions with read-only access to the shared data table.Source: §3.2.1 · p. 3, Figure 1 · p. 4

3.2.2 Sync Mechanism

  • The sync mechanism aggregates data across vertices and stores the finalized result in the Shared Data Table under a user-provided key.A fold aggregates vertex data; an optional merge enables parallel tree reduction, and an apply function finalizes the result.Source: §3.2.2 · p. 3
  • Sync can run periodically in the background or on demand, but background results may not be globally consistent.Many ML applications are robust to approximate global statistics.Source: §3.2.2 · pp. 3–4
  • For Loopy BP, sync monitors convergence by aggregating vertex residuals and dividing the result by the number of vertices.The example runs this monitoring sync periodically in the background while BP updates recompute outbound messages from inbound messages.Source: §3.2.2 · p. 4

3.3 DATA CONSISTENCY

Overlapping update scopes can cause races and corrupted data, so GraphLab offers consistency models that trade concurrency for stronger access guarantees. Sequential consistency can extend sequential correctness to parallel execution when the model and update behavior satisfy specified conditions.

3.3 DATA CONSISTENCY

  • Overlapping scopes can cause races and inconsistent or corrupted data when concurrent updates access shared edges or changing values.For example, concurrent updates to neighboring vertices may modify the same edge, or normalization may use edge values that change during computation.Source: §3.3 · p. 4
  • GraphLab's full, edge, and vertex consistency models vary the exclusion sets for concurrent updates; larger sets reduce parallelism.Full consistency excludes overlapping scopes, edge consistency excludes adjacent vertices, and vertex consistency permits neighboring updates but can expose unsafe adjacent-data access.Source: §3.3 · p. 4
  • Sequential consistency means every parallel execution has an equivalent sequential ordering of update functions, and it is typically sufficient to transfer sequential correctness.GraphLab guarantees it with full consistency, with edge consistency when updates do not modify adjacent-vertex data, or with vertex consistency when updates access only local vertex data.Source: §3.3 · p. 4
  • For Loopy BP, edge consistency ensures sequential consistency because updates only read and modify adjacent edges.Source: §3.3 · p. 4

3.4 SCHEDULING

GraphLab schedulers determine the order of vertex-function tasks, from standard synchronous or round-robin schedules to dynamic task schedulers. The set scheduler compiles custom execution sequences into dependency plans that can release independent future tasks early while preserving equivalent results.

3.4 SCHEDULING

  • GraphLab provides synchronous and round-robin schedules for Jacobi-style and Gauss-Seidel-style algorithms, respectively.Synchronous scheduling updates all vertices simultaneously; round-robin updates them sequentially using the most recently available data.Source: §3.4 · p. 5
  • FIFO task schedulers allow task creation, while prioritized schedulers also reorder tasks at greater overhead; relaxed versions trade control for performance.The splash scheduler executes tasks along spanning trees, and different schedules can yield classical or residual BP.Source: §3.4 · p. 5

3.4.1 Set Scheduler

  • The set scheduler represents custom schedules as ordered vertex-set and update-function pairs, executing each set's updates in parallel and waiting before the next pair.The execution sequence can be compiled into a DAG whose task edges encode dependencies and whose partial order is scheduled in parallel.Source: §3.4.1 · p. 5
  • The dependency plan can run a task from a later set early when its dependencies are complete, avoiding waits for unrelated tasks while preserving an equivalent result.In the example, v4 can run after v5 without waiting for v1 and v2, whereas v3 depends on v1, v2, and v5.Source: Figure 2 · p. 5, §3.4.1 · p. 5

3.5 TERMINATION ASSESSMENT

GraphLab supports termination checks based either on an empty task queue or on user-provided functions that inspect global state.

3.5 TERMINATION ASSESSMENT

  • A scheduler can signal termination when no tasks remain, which suits Residual BP when convergence stops further task creation.Source: §3.5 · p. 5
  • User-provided termination functions can inspect the Shared Data Table and signal convergence for algorithms that rely on global statistics.Parameter learning is given as an example.Source: §3.5 · p. 5
  • The two termination approaches use different signals: absence of scheduled tasks or a user function's assessment of shared state.Source: §3.5 · p. 5

3.6 SUMMARY AND IMPLEMENTATION

GraphLab programs combine a data graph, local update functions, global synchronization, consistency rules, and scheduling primitives. Its optimized C++ implementation addresses systems-level performance and correctness challenges while offering an interface between ML and systems communities.

3.6 SUMMARY AND IMPLEMENTATION

  • Five components define a GraphLab program: a data graph, update functions, sync, a consistency model, and scheduling primitives.Scheduling can express computation order and may depend dynamically on data.Source: §3.6 · p. 6
  • Race-free, deadlock-free ordered locking protocols implement the consistency models; lock-free structures and atomic operations help reduce mutex costs.The C++ implementation also addresses parallel memory allocation, concurrent random-number generation, and cache efficiency.Source: §3.6 · p. 6
  • GraphLab can connect ML and systems communities: ML algorithms can use improvements to its parallel data structures and scheduling, while systems experts can port the API to new hardware.The API is available under the LGPL license.Source: §3.6 · p. 6

4 CASE STUDIES

The case studies evaluate GraphLab on large real-world problems using a 16-core computer, including a retinal denoising workflow that combines image statistics, MRF parameter learning, and Loopy BP inference.

4.1 MRF PARAMETER LEARNING

  • The retinal denoising workflow uses a three-dimensional MRF, computes smoothed-image statistics, and concurrently learns model parameters while running BP inference.The authors describe this as the first concurrent execution of graphical-model parameter learning and BP inference.Source: §4.1 · p. 6
  • Splash achieved a 15× speedup on 16 cores for sequential parameter learning and inference; concurrent background sync further accelerated learning while only marginally affecting learned parameters.The study also illustrates noisy and denoised retinal-image cross sections.Source: §4.1 · p. 6, Figure 4 · p. 7

4.2 GIBBS SAMPLING

  • 16 processors gave the Gibbs sampler a 10× speedup and Loopy BP a 15× speedup; the Gibbs model’s 20 skewed color classes create a strong sequential component.The planned set schedule takes 0.05 seconds to compute, an immaterial fraction of the 16-processor runtime.Source: §4.2 · p. 7, Figure 5 · p. 8

4.3 CO-EM

  • With 16 processors, GraphLab completed three Co-EM round-robin iterations on the large dataset in under 30 minutes, versus about 7.5 hours for Hadoop on an average of 95 CPUs.Both schedulers achieved nearly linear scaling and similar belief estimates; the large dataset scaled better because its update function was slower.Source: §4.3 · p. 8, Figure 6 · p. 9
  • Co-EM showed no substantial benefit from dynamic scheduling, while 16 cores still gave 12× speedup on smaller problems and scaling improved with problem size.The schedule comparison measured updates to comparable quality using L1 parameter distance to an empirical fixed-point estimate.Source: §4.3 · p. 8

4.4 LASSO

  • GraphLab represents the shooting algorithm as coordinate descent on weight vertices linked to observations, enabling an equivalent parallel schedule with full consistency.The paper presents two parallel algorithms for Lasso and notes that no parallel algorithm for fitting a Lasso model was known to the authors.Source: §4.4.1 · p. 8, §4.4 · p. 8

4.4.1 Shooting Algorithm

  • The shooting algorithm achieved 4× speedup at 16 CPUs on the sparser dataset, compared with 2× on the denser dataset, relative to the fastest single-processor runtime.The authors state that ensuring full consistency on denser graphs inevitably increases contention, reducing performance.Source: §4.4.1 · p. 9, Figure 7 · p. 9

4.5 Compressed Sensing

  • 16 processors yielded an 8× speedup for compressed sensing with round-robin scheduling.The evaluated dataset used random projections of a wavelet-transformed 256 × 256 image.Source: §4.5 · p. 9, Figure 8 · p. 10

5 CONCLUSIONS AND FUTURE WORK

GraphLab combines structured data dependencies, iterative computation, and flexible scheduling with consistency models and synchronization for shared state. Its optimized shared-memory implementation achieved state-of-the-art performance in real-world case studies, while distributed scaling remains future work.

5 CONCLUSIONS AND FUTURE WORK

  • GraphLab represents structured data dependencies and iterative computation, with consistency models and synchronization for managing overlapping updates and shared state.Users specify minimal consistency requirements rather than building complex locking protocols.Source: §5 · p. 10
  • Its schedulers support dynamic iterative computation and can be composed into custom schedules from sequences of vertex sets.Source: §5 · p. 10
  • GraphLab’s shared-memory implementation achieved state-of-the-art performance across real-world machine-learning case studies.The case studies demonstrate the framework’s performance and flexibility.Source: §5 · p. 10
  • Extending GraphLab to distributed computation is future work, with graph partitioning, load balancing, distributed locking, and fault tolerance identified as challenges.Source: §5 · p. 10
Loading 1408.2041v1…