PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphLab: A New Framework for Parallel Machine Learning

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

arXiv:1006.4990v1cs.LGcs.DC

TL;DR

Parallel ML algorithms are difficult to design because low-level tools expose implementation burdens and high-level abstractions such as MapReduce cannot express key structured and iterative computations. GraphLab addresses this gap with sparse dependency representation, configurable consistency, and flexible scheduling, and the paper reports state-of-the-art performance across real-world ML case studies. Its scope is shared-memory execution with non-failing processors and all data resident in shared memory.

  • Problem

    Parallel ML is difficult because low-level tools leave users to solve hardware and parallel data-representation challenges, while MapReduce fails to represent dependencies in structured models.

  • Method

    GraphLab is a parallel ML framework that represents sparse computational dependencies and supports asynchronous iterative computation, configurable consistency models, and flexible scheduling.

  • Results

    Across real-world case studies, GraphLab implementations of popular ML algorithms achieved state-of-the-art performance.

  • Takeaways & Limitations

    GraphLab supports structured data dependencies, iterative computation, and flexible scheduling while combining usability, expressiveness, and performance.

  • Takeaways & Limitations

    The implementation assumes non-failing processors and shared-memory data, while distributed fault-tolerant implementation remains ongoing research.

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 addresses the difficulty of parallel ML by combining expressive data dependencies and scheduling with consistency guarantees. The framework supports several ML algorithms and achieves state-of-the-art performance on a 16-processor system.

  • Motivation and contribution: Low-level tools such as MPI and Pthreads expose powerful primitives but leave users responsible for hardware and parallel data-representation challenges.
  • Motivation and contribution: MapReduce can simplify parallel design, but its restrictions may force simplifying assumptions or inefficient algorithms requiring many processors to compete with sequential methods.
  • Motivation and contribution: GraphLab targets sparse computational patterns in ML to help experts design efficient, scalable parallel algorithms.It composes problem-specific computation, data dependencies, and scheduling in a shared-memory implementation.
  • Evaluation: On a 16-processor system, GraphLab implementations of parameter learning, inference, Gibbs sampling, Co-EM, Lasso, and compressed sensing achieved state-of-the-art performance on real-world problems.
  • Main contributions: GraphLab provides a graph-based data model, concurrent access models, modular scheduling, and aggregation for parallel ML.

2 EXISTING FRAMEWORKS

Existing parallel abstractions each support some ML computation but impose important limitations on dependencies, iteration, scheduling, or system assumptions. These constraints can make rich structured models and efficient ML algorithms difficult to express at scale.

  • MapReduce: MapReduce performs well for independent computations but fails to represent computational dependencies needed by structured models.Large-scale applications may therefore favor simpler models that fit the abstraction.
  • MapReduce: MapReduce does not directly encode iterative computation, limiting sophisticated scheduling, automatic termination assessment, and data persistence.
  • MapReduce: MapReduce implementations incur fault-tolerant, disk-centric overhead that is costly in typical ML cluster and multicore settings.
  • MapReduce: The paper’s GraphLab implementation assumes processors do not fail and data resides in shared memory, while distributed fault-tolerant implementation remains ongoing research.
  • DAG: DAG abstractions permit rich dependencies but do not naturally express iterative algorithms or dynamically prioritized computation.The dataflow structure depends on the number of iterations, which must be known beforehand.
  • Systolic: Systolic abstractions support iteration but cannot express the wide range of update schedules used by ML algorithms, including dynamic schedules for BP.

3 THE GRAPHLAB ABSTRACTION

GraphLab targets sparse dependencies and asynchronous iteration to balance abstraction-level usability with expressive parallel ML computation. Its data graph, consistency models, and scheduling primitives represent structured dependencies and dynamic iterative algorithms.

  • Design goals: GraphLab targets sparse data dependencies and asynchronous iterative computation common in ML.
  • Design goals: GraphLab insulates users from synchronization, data races, and deadlocks through high-level data representation and automatically maintained consistency guarantees.
  • Core abstraction: The data graph expresses complex computational dependencies, while scheduling primitives support iterative algorithms with dynamic scheduling.
  • Running example: Loopy belief propagation on pairwise Markov Random Fields serves as the running example, iteratively recomputing edge messages until convergence.

3.1 DATA MODEL

GraphLab represents ML problems through a directed data graph and a shared data table. The graph stores sparse structure and mutable state, while the table stores globally shared values such as hyperparameters and convergence progress.

  • Data model: The GraphLab data model combines a directed data graph with a shared data table.
  • Data graph: The data graph encodes sparse computational structure and modifiable program state by associating arbitrary data blocks with vertices and directed edges.
  • Loopy BP representation: In loopy BP, vertices store node potentials and directed edges store messages; sparse MRF structure consequently provides parallelism.
  • Loopy BP representation: The shared data table stores shared hyperparameters and global convergence progress for the computation.

3.2 USER DEFINED COMPUTATION

GraphLab separates local neighborhood computation from global aggregation: update functions mutate graph data, while sync combines vertex data into shared state. This design supports concurrent updates and approximate background statistics.

  • Update Functions: Update functions perform local, state-mutating computation over a vertex neighborhood and read-only shared data.Their accessible scope includes the vertex, adjacent edges, neighboring vertices, and the shared data table.
  • Sync Mechanism: The sync mechanism aggregates data across vertices, optionally using parallel tree reduction, then applies the result before storing it in the shared data table.
  • Sync Mechanism: Sync can run periodically in the background or on demand, but background aggregation may produce globally inconsistent values.Many ML applications are described as robust to approximate global statistics.
  • Loopy BP Example: In Loopy BP, update functions recompute outbound messages from inbound messages, while sync monitors convergence using aggregated residuals.

3.3 DATA CONSISTENCY

GraphLab addresses races caused by overlapping computation scopes through configurable consistency models. These models trade parallelism against guarantees that support sequentially consistent parallel execution.

  • Motivation: Overlapping scopes can cause race conditions, inconsistent data, or corrupted shared-edge values during concurrent updates.
  • Consistency Models: GraphLab prevents simultaneous execution when update functions have overlapping exclusion sets, with larger sets reducing available parallelism.
  • Consistency Models: Full consistency excludes all concurrent reads or modifications within a vertex scope, permitting parallelism only among vertices without a common neighbor.
  • Consistency Models: Edge consistency protects a vertex and its adjacent edges, allowing parallel execution only on non-adjacent vertices.
  • Correctness: Sequential consistency is sufficient to transfer correctness from a sequential algorithm when every parallel execution has an equivalent sequential execution.
  • Correctness: GraphLab guarantees sequential consistency under full consistency, restricted edge consistency, or restricted vertex consistency conditions.

3.4 SCHEDULING

GraphLab represents update order with modular schedulers ranging from synchronous and sequential patterns to dynamically prioritized tasks. Its set scheduler compiles dependencies into parallel execution plans that can safely expose earlier work.

  • Scheduler Model: The scheduler represents a dynamic list of vertex-function tasks and determines the order in which update functions execute.
  • Base Schedules: GraphLab provides synchronous scheduling for Jacobi-style algorithms and round-robin scheduling for Gauss-Seidel-style algorithms.
  • Task Schedulers: Task schedulers support task creation and, for prioritized schedules, task reordering for algorithms requiring finer control over execution.FIFO schedules avoid reordering overhead, whereas prioritized schedules incur increased overhead.
  • Loopy BP Example: Different schedules produce different BP algorithms: synchronous scheduling gives classical BP, while priority scheduling gives Residual BP.
  • Set Scheduler: The set scheduler accepts vertex-set and update-function pairs, executing each function across its set in parallel before proceeding.
  • Set Scheduler: Causal dependencies allow tasks in future sets to execute early while preserving an equivalent result, reducing unnecessary waiting.
  • Set Scheduler: The set scheduler rewrites execution sequences as dependency DAGs, whose partial ordering can be compiled into parallel schedules.

3.5 TERMINATION ASSESSMENT

GraphLab provides two termination-assessment methods for iterative ML algorithms: scheduler-based completion and a second method for conditions involving global state.

  • Scheduler-Based Termination: GraphLab can terminate when a task scheduler has no remaining tasks, which suits algorithms that stop generating tasks after convergence.Residual BP is given as an example of this pattern.
  • Global-State Termination: A second termination method addresses iterative algorithms whose standard stopping conditions require reasoning about global state.

3.6 SUMMARY AND IMPLEMENTATION

GraphLab programs combine a data graph, local updates, global aggregation, consistency guarantees, and dynamic scheduling. Its shared-memory implementation uses locking and systems optimizations, while exposing reusable infrastructure to ML and systems communities.

  • A GraphLab program combines a data graph, update functions, synchronization, a consistency model, and scheduling primitives.
  • The data graph represents both data and computational dependencies, while consistency models determine how computation may overlap.
  • Scheduling primitives express computation order and may depend dynamically on the data.
  • The C++ implementation uses PThreads, race-free and deadlock-free ordered locking, and optimizations for allocation, random-number generation, and cache efficiency.
  • GraphLab provides an interface through which ML algorithms can benefit from improved parallel data structures and scheduling primitives.

4 CASE STUDIES

GraphLab expresses complete ML pipelines and diverse algorithms through graph-based computation, synchronization, consistency models, and scheduling. Across case studies, it delivers substantial parallel speedups while exposing trade-offs involving graph density, scheduling, and consistency.

  • GraphLab was evaluated on large real-world problems using a 16-core computer to demonstrate abstraction expressiveness and parallel performance.
  • 4.1 MRF Parameter Learning: A retinal denoising pipeline combines graph construction, global statistics, parameter learning, and Loopy BP inference on a 256x64x64 voxel MRF.
  • 4.1 MRF Parameter Learning: 15x speedup on 16 cores was achieved for sequential parameter learning with the Splash scheduler.
  • 4.2 Gibbs Sampling: 10x speedup on 16 processors was achieved for Gibbs sampling using a planned set schedule with planning optimization.The execution plan took 0.05 seconds to compute, an immaterial fraction of the 16-processor runtime.
  • 4.2 Gibbs Sampling: Loopy BP achieved 15x speedup on 16 processors, benefiting from expensive updates and a fully asynchronous schedule.
  • 4.3 Co-EM: CoEM schedulers achieved nearly linear scaling and similar belief estimates, while dynamic scheduling provided no substantial convergence benefit.
  • 4.3 Co-EM: GraphLab completed three Round-robin iterations on the large CoEM dataset in under 30 minutes on 16 processors, versus approximately 7.5 hours for comparable Hadoop.

5 CONCLUSIONS AND FUTURE WORK

GraphLab addresses limitations of existing parallel abstractions by representing structured dependencies, iterative computation, and flexible scheduling for machine learning. Its optimized shared-memory implementation achieved state-of-the-art performance in real-world case studies, while distributed extension remains future work.

  • Conclusions: GraphLab supports structured data dependencies, iterative computation, and flexible scheduling unlike existing parallel abstractions.Its data graph encodes computational structure and dependencies, while schedulers manage dynamic iterative computation.
  • Conclusions: GraphLab combines update functions, data consistency models, and schedulers to express parallel machine learning algorithms without requiring users to build complex locking protocols.Update functions transform graph data, consistency models specify access guarantees, and schedulers coordinate dynamic computation.
  • Results: An optimized shared-memory GraphLab implementation achieved state-of-the-art performance across case studies on popular machine learning algorithms and large real-world datasets.The evaluation covered parameter learning and inference, Gibbs sampling, CoEM, Lasso, and compressed sensing.
  • Future Work: Extending GraphLab to distributed computation is ongoing and requires efficient graph partitioning, load balancing, distributed locking, and fault tolerance.The distributed setting is intended to support computation on even larger datasets, but introduces these challenges.
Loading 1006.4990v1…