Amir Payberah, profile picture
Uploaded byAmir Payberah
1,034 views

Graph processing - Graphlab

The document describes GraphLab, a new framework for parallel machine learning. GraphLab allows parallel processing of large-scale graph problems more efficiently than general data-parallel systems by exploiting the graph structure. It uses a vertex-centric programming model that allows update functions to read and modify data within a vertex's scope, addressing limitations of the Pregel model. GraphLab implements consistency models to ensure correctness and employs techniques like graph partitioning and distributed locking to enable parallel execution across multiple machines.

Downloaded 55 times
GraphLab: A New Framework For Parallel Machine Learning Amir H. Payberah amir@sics.se Amirkabir University of Technology (Tehran Polytechnic) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 1 / 42
Reminder Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 2 / 42
Data-Parallel Model for Large-Scale Graph Processing The platforms that have worked well for developing parallel applica- tions are not necessarily effective for large-scale graph problems. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 3 / 42
Graph-Parallel Processing Restricts the types of computation. New techniques to partition and distribute graphs. Exploit graph structure. Executes graph algorithms orders-of-magnitude faster than more general data-parallel systems. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 4 / 42
Data-Parallel vs. Graph-Parallel Computation Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 5 / 42
Pregel Vertex-centric Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 6 / 42
Pregel Vertex-centric Bulk Synchronous Parallel (BSP) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 6 / 42
Pregel Vertex-centric Bulk Synchronous Parallel (BSP) Runs in sequence of iterations (supersteps) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 6 / 42
Pregel Vertex-centric Bulk Synchronous Parallel (BSP) Runs in sequence of iterations (supersteps) A vertex in superstep S can: • reads messages sent to it in superstep S-1. • sends messages to other vertices: receiving at superstep S+1. • modifies its state. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 6 / 42
Pregel Limitations Inefficient if different regions of the graph converge at different speed. Can suffer if one task is more expensive than the others. Runtime of each phase is determined by the slowest machine. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 7 / 42
Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 8 / 42
Data Model A directed graph that stores the program state, called data graph. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 9 / 42
Vertex Scope The scope of vertex v is the data stored in vertex v, in all adjacent vertices and adjacent edges. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 10 / 42
Programming Model (1/3) Rather than adopting a message passing as in Pregel, GraphLab allows the user defined function of a vertex to read and modify any of the data in its scope. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 11 / 42
Programming Model (2/3) Update function: user-defined function similar to Compute in Pregel. Can read and modify the data within the scope of a vertex. Schedules the future execution of other update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 12 / 42
Programming Model (3/3) Sync function: similar to aggregate in Pregel. Maintains global aggregates. Performs periodically in the background. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 13 / 42
Execution Model Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 14 / 42
Execution Model Each task in the set of tasks T , is a tuple (f, v) consisting of an update function f and a vertex v. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 14 / 42
Execution Model Each task in the set of tasks T , is a tuple (f, v) consisting of an update function f and a vertex v. After executing an update function (f, g, · · ·) the modified scope data in Sv is written back to the data graph. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 14 / 42
Example: PageRank GraphLab_PageRank(i) // compute sum over neighbors total = 0 foreach(j in in_neighbors(i)): total = total + R[j] * wji // update the PageRank R[i] = 0.15 + total // trigger neighbors to run again foreach(j in out_neighbors(i)): signal vertex-program on j R[i] = 0.15 + j∈Nbrs(i) wjiR[j] Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 15 / 42
Data Consistency (1/3) Overlapped scopes: race-condition in simultaneous execution of two update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 16 / 42
Data Consistency (1/3) Overlapped scopes: race-condition in simultaneous execution of two update functions. Full consistency: during the execution f(v), no other function reads or modifies data within the v scope. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 16 / 42
Data Consistency (2/3) Edge consistency: during the execution f(v), no other function reads or modifies any of the data on v or any of the edges adja- cent to v. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 17 / 42
Data Consistency (3/3) Vertex consistency: during the execution f(v), no other function will be applied to v. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 18 / 42
Sequential Consistency (1/2) Proving the correctness of a parallel algorithm: sequential consistency Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 19 / 42
Sequential Consistency (1/2) Proving the correctness of a parallel algorithm: sequential consistency Sequential consistency: if for every parallel execution, there exists a sequential execution of update functions that produces an equivalent result. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 19 / 42
Sequential Consistency (2/2) A simple method to achieve serializability is to ensure that the scopes of concurrently executing update functions do not overlap. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 20 / 42
Sequential Consistency (2/2) A simple method to achieve serializability is to ensure that the scopes of concurrently executing update functions do not overlap. • The full consistency model is used. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 20 / 42
Sequential Consistency (2/2) A simple method to achieve serializability is to ensure that the scopes of concurrently executing update functions do not overlap. • The full consistency model is used. • The edge consistency model is used and update functions do not modify data in adjacent vertices. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 20 / 42
Sequential Consistency (2/2) A simple method to achieve serializability is to ensure that the scopes of concurrently executing update functions do not overlap. • The full consistency model is used. • The edge consistency model is used and update functions do not modify data in adjacent vertices. • The vertex consistency model is used and update functions only access local vertex data. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 20 / 42
Consistency vs. Parallelism Consistency vs. Parallelism [Low, Y., GraphLab: A Distributed Abstraction for Large Scale Machine Learning (Doctoral dissertation, University of California), 2013.] Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 21 / 42
GraphLab Implementation Shared memory implementation Distributed implementation Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 22 / 42
GraphLab Implementation Shared memory implementation Distributed implementation Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 22 / 42
Tasks Schedulers (1/2) In what order should the tasks (vertex-update function pairs) be called? Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 23 / 42
Tasks Schedulers (1/2) In what order should the tasks (vertex-update function pairs) be called? • A collection of base schedules, e.g., round-robin, and synchronous. • Set scheduler: enables users to compose custom update schedules. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 23 / 42
Tasks Schedulers (2/2) How to add new task in the queue? Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 24 / 42
Tasks Schedulers (2/2) How to add new task in the queue? • FIFO: only permits task creation but do not permit task reordering. • Prioritized: permits task reordering at the cost of increased overhead. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 24 / 42
Consistency Implemented in C++ using PThreads for parallelism. Consistency: read-write lock Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 25 / 42
Consistency Implemented in C++ using PThreads for parallelism. Consistency: read-write lock Vertex consistency • Central vertex (write-lock) Edge consistency • Central vertex (write-lock) • Adjacent vertices (read-locks) Full consistency • Central vertex (write-locks) • Adjacent vertices (write-locks) Deadlocks are avoided by acquiring locks sequentially following a canonical order. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 25 / 42
GraphLab Implementation Shared memory implementation Distributed implementation Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 26 / 42
Distributed Implementation Graph partitioning • How to efficiently load, partition and distribute the data graph across machines? Consistency • How to achieve consistency in the distributed setting? Fault tolerance Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 27 / 42
Graph Partitioning Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 28 / 42
Graph Partitioning - Phase 1 (1/2) Two-phase partitioning. Partitioning the data graph into k parts, called atom. • k number of machines Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 29 / 42
Graph Partitioning - Phase 1 (1/2) Two-phase partitioning. Partitioning the data graph into k parts, called atom. • k number of machines meta-graph: the graph of atoms (one vertex for each atom). Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 29 / 42
Graph Partitioning - Phase 1 (1/2) Two-phase partitioning. Partitioning the data graph into k parts, called atom. • k number of machines meta-graph: the graph of atoms (one vertex for each atom). Atom weight: the amount of data it stores. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 29 / 42
Graph Partitioning - Phase 1 (1/2) Two-phase partitioning. Partitioning the data graph into k parts, called atom. • k number of machines meta-graph: the graph of atoms (one vertex for each atom). Atom weight: the amount of data it stores. Edge weight: the number of edges crossing the atoms. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 29 / 42
Graph Partitioning - Phase 1 (2/2) Each atom is stored as a separate file on a distributed storage system, e.g., HDFS. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 30 / 42
Graph Partitioning - Phase 1 (2/2) Each atom is stored as a separate file on a distributed storage system, e.g., HDFS. Each atom file is a simple binary that stores interior and the ghosts of the partition information. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 30 / 42
Graph Partitioning - Phase 1 (2/2) Each atom is stored as a separate file on a distributed storage system, e.g., HDFS. Each atom file is a simple binary that stores interior and the ghosts of the partition information. Ghost: set of vertices and edges adjacent to the partition boundary. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 30 / 42
Graph Partitioning - Phase 2 Meta-graph is very small. A fast balanced partition of the meta-graph over the physical ma- chines. Assigning graph atoms to machines. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 31 / 42
Consistency Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 32 / 42
Consistency To achieve a serializable parallel execution of a set of dependent tasks. • Chromatic engine • Distributed locking engine Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 33 / 42
Consistency - Chromatic Engine Construct a vertex coloring: assigns a color to each vertex such that no adjacent vertices share the same color. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 34 / 42
Consistency - Chromatic Engine Construct a vertex coloring: assigns a color to each vertex such that no adjacent vertices share the same color. Edge consistency: executing, synchronously, all update tasks asso- ciated with vertices of the same color before proceeding to the next color. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 34 / 42
Consistency - Chromatic Engine Construct a vertex coloring: assigns a color to each vertex such that no adjacent vertices share the same color. Edge consistency: executing, synchronously, all update tasks asso- ciated with vertices of the same color before proceeding to the next color. Full consistency: no vertex shares the same color as any of its dis- tance two neighbors. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 34 / 42
Consistency - Chromatic Engine Construct a vertex coloring: assigns a color to each vertex such that no adjacent vertices share the same color. Edge consistency: executing, synchronously, all update tasks asso- ciated with vertices of the same color before proceeding to the next color. Full consistency: no vertex shares the same color as any of its dis- tance two neighbors. Vertex consistency: assigning all vertices the same color. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 34 / 42
Consistency - Distributed Locking Engine Associating a readers-writer lock with each vertex. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
Consistency - Distributed Locking Engine Associating a readers-writer lock with each vertex. Vertex consistency • Central vertex (write-lock) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
Consistency - Distributed Locking Engine Associating a readers-writer lock with each vertex. Vertex consistency • Central vertex (write-lock) Edge consistency • Central vertex (write-lock), Adjacent vertices (read-locks) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
Consistency - Distributed Locking Engine Associating a readers-writer lock with each vertex. Vertex consistency • Central vertex (write-lock) Edge consistency • Central vertex (write-lock), Adjacent vertices (read-locks) Full consistency • Central vertex (write-locks), Adjacent vertices (write-locks) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
Consistency - Distributed Locking Engine Associating a readers-writer lock with each vertex. Vertex consistency • Central vertex (write-lock) Edge consistency • Central vertex (write-lock), Adjacent vertices (read-locks) Full consistency • Central vertex (write-locks), Adjacent vertices (write-locks) Deadlocks are avoided by acquiring locks sequentially following a canonical order. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
Fault Tolerance Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 36 / 42
Fault Tolerance - Synchronous The systems periodically signals all computation activity to halt. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 37 / 42
Fault Tolerance - Synchronous The systems periodically signals all computation activity to halt. Then synchronizes all caches (ghosts) and saves to disk all data which has been modified since the last snapshot. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 37 / 42
Fault Tolerance - Synchronous The systems periodically signals all computation activity to halt. Then synchronizes all caches (ghosts) and saves to disk all data which has been modified since the last snapshot. Simple, but eliminates the systems advantage of asynchronous com- putation. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 37 / 42
Fault Tolerance - Asynchronous Based on the Chandy-Lamport algorithm. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
Fault Tolerance - Asynchronous Based on the Chandy-Lamport algorithm. The snapshot function is implemented as an update function in vertices. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
Fault Tolerance - Asynchronous Based on the Chandy-Lamport algorithm. The snapshot function is implemented as an update function in vertices. The snapshot update takes priority over all other update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
Fault Tolerance - Asynchronous Based on the Chandy-Lamport algorithm. The snapshot function is implemented as an update function in vertices. The snapshot update takes priority over all other update functions. Edge Consistency is used on all update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
Fault Tolerance - Asynchronous Based on the Chandy-Lamport algorithm. The snapshot function is implemented as an update function in vertices. The snapshot update takes priority over all other update functions. Edge Consistency is used on all update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
Summary Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 39 / 42
GraphLab Summary Asynchronous model Vertex-centric Communication: distributed shared memory Three consistency levels: full, edge-level, and vertex-level Partitioning: two-phase partitioning Consistency: chromatic engine (graph coloring), distributed lock engine (reader-writer lock) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 40 / 42
GraphLab Limitations Poor performance on Natural graphs. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 41 / 42
Questions? Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 42 / 42

More Related Content

PDF
Graph processing - Powergraph and GraphX
byAmir Payberah
 
PDF
Graph processing - Pregel
byAmir Payberah
 
PDF
Spark Stream and SEEP
byAmir Payberah
 
DOC
Uma Sagar_c
byUmaSagar Sagar
 
PDF
Fault-tolerant topology and routing synthesis for IEEE time-sensitive network...
byVoica Gavrilut
 
PDF
Portfolio control version sn_v5
bySamuel Narcisse
 
PDF
Advanced Process Monitoring IMF
byAlkis Vazacopoulos
 
PPT
Aws100 ch06 thermal
bychowdavaramsaiprasad
 
Graph processing - Powergraph and GraphX
byAmir Payberah
 
Graph processing - Pregel
byAmir Payberah
 
Spark Stream and SEEP
byAmir Payberah
 
Uma Sagar_c
byUmaSagar Sagar
 
Fault-tolerant topology and routing synthesis for IEEE time-sensitive network...
byVoica Gavrilut
 
Portfolio control version sn_v5
bySamuel Narcisse
 
Advanced Process Monitoring IMF
byAlkis Vazacopoulos
 
Aws100 ch06 thermal
bychowdavaramsaiprasad
 

What's hot

PPTX
FEA- Introduction
byAswathaman R
 
PDF
Design and Implementation of Single Precision Pipelined Floating Point Co-Pro...
bySilicon Mentor
 
PDF
Advanced property tracking Industrial Modeling Framework
byAlkis Vazacopoulos
 
PPTX
Learning ANSYS Fluent R19 using modeling a Fluidized Bed with nano particles
byHamed Hoorijani
 
PPT
AHF_IDETC_2011_Jie
byMDO_Lab
 
PDF
Novel high functionality fault tolerant ALU
byTELKOMNIKA JOURNAL
 
PDF
J045075661
byIJERA Editor
 
DOCX
Comparative analysis of cascade h-bridge multilevel Voltage source inverter
byPvrtechnologies Nellore
 
PDF
Advanced Data Science with Apache Spark-(Reza Zadeh, Stanford)
bySpark Summit
 
PDF
[Capella Day 2019] Model execution and system simulation in Capella
byObeo
 
PDF
M.G.Goman, A.V.Khramtsovsky (2008) - Computational framework for investigatio...
byProject KRIT
 
PDF
ACES_Journal_February_2012_Paper_07
byMark Patrick Cheeseman
 
PDF
Estimation of Base Drag On Supersonic Cruise Missile
byIRJET Journal
 
PPT
CFD & ANSYS FLUENT
byMD SHUJAN ALI
 
PDF
Iaetsd 128-bit area
byIaetsd Iaetsd
 
PDF
Component Based Control System Design
byM Reza Rahmati
 
PDF
(8) modeling of transfer function characteristic of rlc circuit
byAl Al
 
PDF
Pid output fuzzified water level control in mimo coupled tank system
byIAEME Publication
 
PDF
IRJET- A Study on Algorithms for FFT Computations
byIRJET Journal
 
PDF
Supporting Flight Test And Flight Matching
byj2aircraft
 
FEA- Introduction
byAswathaman R
 
Design and Implementation of Single Precision Pipelined Floating Point Co-Pro...
bySilicon Mentor
 
Advanced property tracking Industrial Modeling Framework
byAlkis Vazacopoulos
 
Learning ANSYS Fluent R19 using modeling a Fluidized Bed with nano particles
byHamed Hoorijani
 
AHF_IDETC_2011_Jie
byMDO_Lab
 
Novel high functionality fault tolerant ALU
byTELKOMNIKA JOURNAL
 
J045075661
byIJERA Editor
 
Comparative analysis of cascade h-bridge multilevel Voltage source inverter
byPvrtechnologies Nellore
 
Advanced Data Science with Apache Spark-(Reza Zadeh, Stanford)
bySpark Summit
 
[Capella Day 2019] Model execution and system simulation in Capella
byObeo
 
M.G.Goman, A.V.Khramtsovsky (2008) - Computational framework for investigatio...
byProject KRIT
 
ACES_Journal_February_2012_Paper_07
byMark Patrick Cheeseman
 
Estimation of Base Drag On Supersonic Cruise Missile
byIRJET Journal
 
CFD & ANSYS FLUENT
byMD SHUJAN ALI
 
Iaetsd 128-bit area
byIaetsd Iaetsd
 
Component Based Control System Design
byM Reza Rahmati
 
(8) modeling of transfer function characteristic of rlc circuit
byAl Al
 
Pid output fuzzified water level control in mimo coupled tank system
byIAEME Publication
 
IRJET- A Study on Algorithms for FFT Computations
byIRJET Journal
 
Supporting Flight Test And Flight Matching
byj2aircraft
 

Viewers also liked

PDF
MapReduce
byAmir Payberah
 
PDF
Introduction to stream processing
byAmir Payberah
 
PDF
Process Management - Part3
byAmir Payberah
 
PDF
Linux Module Programming
byAmir Payberah
 
PDF
Process Management - Part1
byAmir Payberah
 
PDF
MegaStore and Spanner
byAmir Payberah
 
PDF
Introduction to Operating Systems - Part3
byAmir Payberah
 
PDF
Threads
byAmir Payberah
 
PDF
Mesos and YARN
byAmir Payberah
 
PDF
IO Systems
byAmir Payberah
 
PDF
Main Memory - Part2
byAmir Payberah
 
PDF
Process Management - Part2
byAmir Payberah
 
PDF
Introduction to Operating Systems - Part2
byAmir Payberah
 
PDF
Cloud Computing
byAmir Payberah
 
PDF
Security
byAmir Payberah
 
PDF
Protection
byAmir Payberah
 
PDF
Storage
byAmir Payberah
 
PDF
CPU Scheduling - Part2
byAmir Payberah
 
PDF
The Stratosphere Big Data Analytics Platform
byAmir Payberah
 
PDF
Process Synchronization - Part2
byAmir Payberah
 
MapReduce
byAmir Payberah
 
Introduction to stream processing
byAmir Payberah
 
Process Management - Part3
byAmir Payberah
 
Linux Module Programming
byAmir Payberah
 
Process Management - Part1
byAmir Payberah
 
MegaStore and Spanner
byAmir Payberah
 
Introduction to Operating Systems - Part3
byAmir Payberah
 
Threads
byAmir Payberah
 
Mesos and YARN
byAmir Payberah
 
IO Systems
byAmir Payberah
 
Main Memory - Part2
byAmir Payberah
 
Process Management - Part2
byAmir Payberah
 
Introduction to Operating Systems - Part2
byAmir Payberah
 
Cloud Computing
byAmir Payberah
 
Security
byAmir Payberah
 
Protection
byAmir Payberah
 
Storage
byAmir Payberah
 
CPU Scheduling - Part2
byAmir Payberah
 
The Stratosphere Big Data Analytics Platform
byAmir Payberah
 
Process Synchronization - Part2
byAmir Payberah
 

Similar to Graph processing - Graphlab

PDF
Updating PageRank for Streaming Graphs
byJason Riedy
 
PPTX
ABSTRACT GRAPH MACHINE: MODELING ORDERINGS IN ASYNCHRONOUS DISTRIBUTED-MEMORY...
byThejaka Amila Kanewala, Ph.D.
 
PPTX
Graph processing
byyeahjs
 
PDF
Ling liu part 01：big graph processing
byjins0618
 
PDF
Ling liu part 02：big graph processing
byjins0618
 
PDF
Time-evolving Graph Processing on Commodity Clusters: Spark Summit East talk ...
bySpark Summit
 
PPTX
MathWorks Interview Lecture
byJohn Yates
 
PPTX
Automatic Scaling Iterative Computations
byGuozhang Wang
 
PPTX
Unit II_Graph.pptxkgjrekjgiojtoiejhgnltegjte
bypournima055
 
PPTX
ExtraV - Boosting Graph Processing Near Storage with a Coherent Accelerator
byJinho Lee
 
PDF
Application of Graph Theory in Computer science using Data Structure.pdf
byNancy Ideker
 
PPTX
Semantic Data Management in Graph Databases: ESWC 2014 Tutorial
byMaribel Acosta Deibe
 
PPTX
Large-Scale Graph Computation on Just a PC: Aapo Kyrola Ph.D. thesis defense
byAapo Kyrölä
 
PDF
Graph Analysis Beyond Linear Algebra
byJason Riedy
 
PDF
[2D3]TurboGraph- Ultrafast graph analystics engine for billion-scale graphs i...
byNAVER D2
 
PPT
Graphs.pptGraphs.pptGraphs.pptGraphs.pptGraphs.pptGraphs.ppt
bybabanazar7204
 
PPTX
Data Structures and Agorithm: DS 21 Graph Theory.pptx
byRashidFaridChishti
 
PPTX
PREGEL a system for large scale graph processing
byAbolfazl Asudeh
 
PDF
Joey gonzalez, graph lab, m lconf 2013
byMLconf
 
PPTX
Semantic Data Management in Graph Databases
byMaribel Acosta Deibe
 
Updating PageRank for Streaming Graphs
byJason Riedy
 
ABSTRACT GRAPH MACHINE: MODELING ORDERINGS IN ASYNCHRONOUS DISTRIBUTED-MEMORY...
byThejaka Amila Kanewala, Ph.D.
 
Graph processing
byyeahjs
 
Ling liu part 01：big graph processing
byjins0618
 
Ling liu part 02：big graph processing
byjins0618
 
Time-evolving Graph Processing on Commodity Clusters: Spark Summit East talk ...
bySpark Summit
 
MathWorks Interview Lecture
byJohn Yates
 
Automatic Scaling Iterative Computations
byGuozhang Wang
 
Unit II_Graph.pptxkgjrekjgiojtoiejhgnltegjte
bypournima055
 
ExtraV - Boosting Graph Processing Near Storage with a Coherent Accelerator
byJinho Lee
 
Application of Graph Theory in Computer science using Data Structure.pdf
byNancy Ideker
 
Semantic Data Management in Graph Databases: ESWC 2014 Tutorial
byMaribel Acosta Deibe
 
Large-Scale Graph Computation on Just a PC: Aapo Kyrola Ph.D. thesis defense
byAapo Kyrölä
 
Graph Analysis Beyond Linear Algebra
byJason Riedy
 
[2D3]TurboGraph- Ultrafast graph analystics engine for billion-scale graphs i...
byNAVER D2
 
Graphs.pptGraphs.pptGraphs.pptGraphs.pptGraphs.pptGraphs.ppt
bybabanazar7204
 
Data Structures and Agorithm: DS 21 Graph Theory.pptx
byRashidFaridChishti
 
PREGEL a system for large scale graph processing
byAbolfazl Asudeh
 
Joey gonzalez, graph lab, m lconf 2013
byMLconf
 
Semantic Data Management in Graph Databases
byMaribel Acosta Deibe
 

More from Amir Payberah

PDF
P2P Content Distribution Network
byAmir Payberah
 
PDF
Data Intensive Computing Frameworks
byAmir Payberah
 
PDF
The Spark Big Data Analytics Platform
byAmir Payberah
 
PDF
File System Implementation - Part2
byAmir Payberah
 
PDF
File System Implementation - Part1
byAmir Payberah
 
PDF
File System Interface
byAmir Payberah
 
PDF
Virtual Memory - Part2
byAmir Payberah
 
PDF
Virtual Memory - Part1
byAmir Payberah
 
PDF
Main Memory - Part1
byAmir Payberah
 
PDF
Deadlocks
byAmir Payberah
 
PDF
CPU Scheduling - Part1
byAmir Payberah
 
PDF
Process Synchronization - Part1
byAmir Payberah
 
PDF
Introduction to Operating Systems - Part1
byAmir Payberah
 
P2P Content Distribution Network
byAmir Payberah
 
Data Intensive Computing Frameworks
byAmir Payberah
 
The Spark Big Data Analytics Platform
byAmir Payberah
 
File System Implementation - Part2
byAmir Payberah
 
File System Implementation - Part1
byAmir Payberah
 
File System Interface
byAmir Payberah
 
Virtual Memory - Part2
byAmir Payberah
 
Virtual Memory - Part1
byAmir Payberah
 
Main Memory - Part1
byAmir Payberah
 
Deadlocks
byAmir Payberah
 
CPU Scheduling - Part1
byAmir Payberah
 
Process Synchronization - Part1
byAmir Payberah
 
Introduction to Operating Systems - Part1
byAmir Payberah
 

Recently uploaded

PPTX
Session 6 Specialized AI Associate Series: The GenAI Experience in UiPath Doc...
byDianaGray10
 
PDF
CymruSec 2025 - Wales' Inaugural Cyber Summit
byRay Bugg
 
PPTX
sustainability_digital_transformation-slidershare.pptx
byAlokGope
 
PDF
Top Features of Effective Executive BI Dashboards for Business Success.pdf
bybullseye enagegement
 
PPTX
Artificial Intelligence lecture slides.pptx
bymaimelabernard6
 
PPTX
Introduction to WordPress Workshop - WCEH 2025
byShanta Nathwani
 
PDF
ChatGPT Ain't Got $%@& On Me! by Andy Pavlo
byScyllaDB
 
PDF
Keynote: X-rAI Specs, Submarines and Juice
byAll Things Open
 
PPTX
Flutter for Beginners widgets types.pptx
byKongu Engineering College, Perundurai, Erode
 
PPTX
Session 5 - Specialized AI Associate Series: Build a Document Understanding ...
byDianaGray10
 
PPTX
Stop Worrying, Start Wiring: Azure Serverless for the AI Era
byMuralidharan Deenathayalan
 
PDF
ClipsField AI - Transform Static Images Into Cinematic Videos in Minutes.pdf
bySOFTTECHHUB
 
PDF
AI Enabled Task Automation Technology Trends in the IT Industry
byManish Chopra
 
PDF
Agentic Automation in Action - Future Skills and Opportunities.pdf
byanabulhac
 
PPTX
Strategic Briefing - Supply-Chain and Autonomous AI Convergence - October-18-...
bySergio De Gregorio
 
PDF
Linux Day Prato 2025: NixOS spiegato ammiocuggino - NixOS for Human Beings
byPeter Bittner
 
PDF
BSides NYC 2025: Inside Cloud Attack Paths End-to-End Adversary Simulation
byMauricio Velazco
 
PDF
Memo No.3006141 dt.25.10.2025- SOP for Grant of Online Change Of Land Use
byRaghu Ram
 
PDF
From Data Chaos to Copilot Confidence: A Step-by-Step Microsoft 365 Copilot R...
byNikki Chapple
 
PDF
Framework for Measuring Semantic Fidelity: Tracking Drift, Tone, and Intent i...
bySemantic Fidelity Lab
 
Session 6 Specialized AI Associate Series: The GenAI Experience in UiPath Doc...
byDianaGray10
 
CymruSec 2025 - Wales' Inaugural Cyber Summit
byRay Bugg
 
sustainability_digital_transformation-slidershare.pptx
byAlokGope
 
Top Features of Effective Executive BI Dashboards for Business Success.pdf
bybullseye enagegement
 
Artificial Intelligence lecture slides.pptx
bymaimelabernard6
 
Introduction to WordPress Workshop - WCEH 2025
byShanta Nathwani
 
ChatGPT Ain't Got $%@& On Me! by Andy Pavlo
byScyllaDB
 
Keynote: X-rAI Specs, Submarines and Juice
byAll Things Open
 
Flutter for Beginners widgets types.pptx
byKongu Engineering College, Perundurai, Erode
 
Session 5 - Specialized AI Associate Series: Build a Document Understanding ...
byDianaGray10
 
Stop Worrying, Start Wiring: Azure Serverless for the AI Era
byMuralidharan Deenathayalan
 
ClipsField AI - Transform Static Images Into Cinematic Videos in Minutes.pdf
bySOFTTECHHUB
 
AI Enabled Task Automation Technology Trends in the IT Industry
byManish Chopra
 
Agentic Automation in Action - Future Skills and Opportunities.pdf
byanabulhac
 
Strategic Briefing - Supply-Chain and Autonomous AI Convergence - October-18-...
bySergio De Gregorio
 
Linux Day Prato 2025: NixOS spiegato ammiocuggino - NixOS for Human Beings
byPeter Bittner
 
BSides NYC 2025: Inside Cloud Attack Paths End-to-End Adversary Simulation
byMauricio Velazco
 
Memo No.3006141 dt.25.10.2025- SOP for Grant of Online Change Of Land Use
byRaghu Ram
 
From Data Chaos to Copilot Confidence: A Step-by-Step Microsoft 365 Copilot R...
byNikki Chapple
 
Framework for Measuring Semantic Fidelity: Tracking Drift, Tone, and Intent i...
bySemantic Fidelity Lab
 

Graph processing - Graphlab

  • 1.
    GraphLab: A NewFramework For Parallel Machine Learning Amir H. Payberah amir@sics.se Amirkabir University of Technology (Tehran Polytechnic) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 1 / 42
  • 2.
    Reminder Amir H. Payberah(Tehran Polytechnic) GraphLab 1393/9/8 2 / 42
  • 3.
    Data-Parallel Model forLarge-Scale Graph Processing The platforms that have worked well for developing parallel applica- tions are not necessarily effective for large-scale graph problems. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 3 / 42
  • 4.
    Graph-Parallel Processing Restricts thetypes of computation. New techniques to partition and distribute graphs. Exploit graph structure. Executes graph algorithms orders-of-magnitude faster than more general data-parallel systems. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 4 / 42
  • 5.
    Data-Parallel vs. Graph-ParallelComputation Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 5 / 42
  • 6.
    Pregel Vertex-centric Amir H. Payberah(Tehran Polytechnic) GraphLab 1393/9/8 6 / 42
  • 7.
    Pregel Vertex-centric Bulk Synchronous Parallel(BSP) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 6 / 42
  • 8.
    Pregel Vertex-centric Bulk Synchronous Parallel(BSP) Runs in sequence of iterations (supersteps) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 6 / 42
  • 9.
    Pregel Vertex-centric Bulk Synchronous Parallel(BSP) Runs in sequence of iterations (supersteps) A vertex in superstep S can: • reads messages sent to it in superstep S-1. • sends messages to other vertices: receiving at superstep S+1. • modifies its state. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 6 / 42
  • 10.
    Pregel Limitations Inefficient ifdifferent regions of the graph converge at different speed. Can suffer if one task is more expensive than the others. Runtime of each phase is determined by the slowest machine. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 7 / 42
  • 11.
    Amir H. Payberah(Tehran Polytechnic) GraphLab 1393/9/8 8 / 42
  • 12.
    Data Model A directedgraph that stores the program state, called data graph. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 9 / 42
  • 13.
    Vertex Scope The scopeof vertex v is the data stored in vertex v, in all adjacent vertices and adjacent edges. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 10 / 42
  • 14.
    Programming Model (1/3) Ratherthan adopting a message passing as in Pregel, GraphLab allows the user defined function of a vertex to read and modify any of the data in its scope. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 11 / 42
  • 15.
    Programming Model (2/3) Updatefunction: user-defined function similar to Compute in Pregel. Can read and modify the data within the scope of a vertex. Schedules the future execution of other update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 12 / 42
  • 16.
    Programming Model (3/3) Syncfunction: similar to aggregate in Pregel. Maintains global aggregates. Performs periodically in the background. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 13 / 42
  • 17.
    Execution Model Amir H.Payberah (Tehran Polytechnic) GraphLab 1393/9/8 14 / 42
  • 18.
    Execution Model Each taskin the set of tasks T , is a tuple (f, v) consisting of an update function f and a vertex v. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 14 / 42
  • 19.
    Execution Model Each taskin the set of tasks T , is a tuple (f, v) consisting of an update function f and a vertex v. After executing an update function (f, g, · · ·) the modified scope data in Sv is written back to the data graph. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 14 / 42
  • 20.
    Example: PageRank GraphLab_PageRank(i) // computesum over neighbors total = 0 foreach(j in in_neighbors(i)): total = total + R[j] * wji // update the PageRank R[i] = 0.15 + total // trigger neighbors to run again foreach(j in out_neighbors(i)): signal vertex-program on j R[i] = 0.15 + j∈Nbrs(i) wjiR[j] Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 15 / 42
  • 21.
    Data Consistency (1/3) Overlappedscopes: race-condition in simultaneous execution of two update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 16 / 42
  • 22.
    Data Consistency (1/3) Overlappedscopes: race-condition in simultaneous execution of two update functions. Full consistency: during the execution f(v), no other function reads or modifies data within the v scope. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 16 / 42
  • 23.
    Data Consistency (2/3) Edgeconsistency: during the execution f(v), no other function reads or modifies any of the data on v or any of the edges adja- cent to v. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 17 / 42
  • 24.
    Data Consistency (3/3) Vertexconsistency: during the execution f(v), no other function will be applied to v. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 18 / 42
  • 25.
    Sequential Consistency (1/2) Provingthe correctness of a parallel algorithm: sequential consistency Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 19 / 42
  • 26.
    Sequential Consistency (1/2) Provingthe correctness of a parallel algorithm: sequential consistency Sequential consistency: if for every parallel execution, there exists a sequential execution of update functions that produces an equivalent result. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 19 / 42
  • 27.
    Sequential Consistency (2/2) Asimple method to achieve serializability is to ensure that the scopes of concurrently executing update functions do not overlap. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 20 / 42
  • 28.
    Sequential Consistency (2/2) Asimple method to achieve serializability is to ensure that the scopes of concurrently executing update functions do not overlap. • The full consistency model is used. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 20 / 42
  • 29.
    Sequential Consistency (2/2) Asimple method to achieve serializability is to ensure that the scopes of concurrently executing update functions do not overlap. • The full consistency model is used. • The edge consistency model is used and update functions do not modify data in adjacent vertices. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 20 / 42
  • 30.
    Sequential Consistency (2/2) Asimple method to achieve serializability is to ensure that the scopes of concurrently executing update functions do not overlap. • The full consistency model is used. • The edge consistency model is used and update functions do not modify data in adjacent vertices. • The vertex consistency model is used and update functions only access local vertex data. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 20 / 42
  • 31.
    Consistency vs. Parallelism Consistencyvs. Parallelism [Low, Y., GraphLab: A Distributed Abstraction for Large Scale Machine Learning (Doctoral dissertation, University of California), 2013.] Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 21 / 42
  • 32.
    GraphLab Implementation Shared memoryimplementation Distributed implementation Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 22 / 42
  • 33.
    GraphLab Implementation Shared memoryimplementation Distributed implementation Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 22 / 42
  • 34.
    Tasks Schedulers (1/2) Inwhat order should the tasks (vertex-update function pairs) be called? Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 23 / 42
  • 35.
    Tasks Schedulers (1/2) Inwhat order should the tasks (vertex-update function pairs) be called? • A collection of base schedules, e.g., round-robin, and synchronous. • Set scheduler: enables users to compose custom update schedules. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 23 / 42
  • 36.
    Tasks Schedulers (2/2) Howto add new task in the queue? Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 24 / 42
  • 37.
    Tasks Schedulers (2/2) Howto add new task in the queue? • FIFO: only permits task creation but do not permit task reordering. • Prioritized: permits task reordering at the cost of increased overhead. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 24 / 42
  • 38.
    Consistency Implemented in C++using PThreads for parallelism. Consistency: read-write lock Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 25 / 42
  • 39.
    Consistency Implemented in C++using PThreads for parallelism. Consistency: read-write lock Vertex consistency • Central vertex (write-lock) Edge consistency • Central vertex (write-lock) • Adjacent vertices (read-locks) Full consistency • Central vertex (write-locks) • Adjacent vertices (write-locks) Deadlocks are avoided by acquiring locks sequentially following a canonical order. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 25 / 42
  • 40.
    GraphLab Implementation Shared memoryimplementation Distributed implementation Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 26 / 42
  • 41.
    Distributed Implementation Graph partitioning •How to efficiently load, partition and distribute the data graph across machines? Consistency • How to achieve consistency in the distributed setting? Fault tolerance Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 27 / 42
  • 42.
    Graph Partitioning Amir H.Payberah (Tehran Polytechnic) GraphLab 1393/9/8 28 / 42
  • 43.
    Graph Partitioning -Phase 1 (1/2) Two-phase partitioning. Partitioning the data graph into k parts, called atom. • k number of machines Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 29 / 42
  • 44.
    Graph Partitioning -Phase 1 (1/2) Two-phase partitioning. Partitioning the data graph into k parts, called atom. • k number of machines meta-graph: the graph of atoms (one vertex for each atom). Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 29 / 42
  • 45.
    Graph Partitioning -Phase 1 (1/2) Two-phase partitioning. Partitioning the data graph into k parts, called atom. • k number of machines meta-graph: the graph of atoms (one vertex for each atom). Atom weight: the amount of data it stores. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 29 / 42
  • 46.
    Graph Partitioning -Phase 1 (1/2) Two-phase partitioning. Partitioning the data graph into k parts, called atom. • k number of machines meta-graph: the graph of atoms (one vertex for each atom). Atom weight: the amount of data it stores. Edge weight: the number of edges crossing the atoms. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 29 / 42
  • 47.
    Graph Partitioning -Phase 1 (2/2) Each atom is stored as a separate file on a distributed storage system, e.g., HDFS. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 30 / 42
  • 48.
    Graph Partitioning -Phase 1 (2/2) Each atom is stored as a separate file on a distributed storage system, e.g., HDFS. Each atom file is a simple binary that stores interior and the ghosts of the partition information. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 30 / 42
  • 49.
    Graph Partitioning -Phase 1 (2/2) Each atom is stored as a separate file on a distributed storage system, e.g., HDFS. Each atom file is a simple binary that stores interior and the ghosts of the partition information. Ghost: set of vertices and edges adjacent to the partition boundary. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 30 / 42
  • 50.
    Graph Partitioning -Phase 2 Meta-graph is very small. A fast balanced partition of the meta-graph over the physical ma- chines. Assigning graph atoms to machines. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 31 / 42
  • 51.
    Consistency Amir H. Payberah(Tehran Polytechnic) GraphLab 1393/9/8 32 / 42
  • 52.
    Consistency To achieve aserializable parallel execution of a set of dependent tasks. • Chromatic engine • Distributed locking engine Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 33 / 42
  • 53.
    Consistency - ChromaticEngine Construct a vertex coloring: assigns a color to each vertex such that no adjacent vertices share the same color. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 34 / 42
  • 54.
    Consistency - ChromaticEngine Construct a vertex coloring: assigns a color to each vertex such that no adjacent vertices share the same color. Edge consistency: executing, synchronously, all update tasks asso- ciated with vertices of the same color before proceeding to the next color. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 34 / 42
  • 55.
    Consistency - ChromaticEngine Construct a vertex coloring: assigns a color to each vertex such that no adjacent vertices share the same color. Edge consistency: executing, synchronously, all update tasks asso- ciated with vertices of the same color before proceeding to the next color. Full consistency: no vertex shares the same color as any of its dis- tance two neighbors. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 34 / 42
  • 56.
    Consistency - ChromaticEngine Construct a vertex coloring: assigns a color to each vertex such that no adjacent vertices share the same color. Edge consistency: executing, synchronously, all update tasks asso- ciated with vertices of the same color before proceeding to the next color. Full consistency: no vertex shares the same color as any of its dis- tance two neighbors. Vertex consistency: assigning all vertices the same color. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 34 / 42
  • 57.
    Consistency - DistributedLocking Engine Associating a readers-writer lock with each vertex. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
  • 58.
    Consistency - DistributedLocking Engine Associating a readers-writer lock with each vertex. Vertex consistency • Central vertex (write-lock) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
  • 59.
    Consistency - DistributedLocking Engine Associating a readers-writer lock with each vertex. Vertex consistency • Central vertex (write-lock) Edge consistency • Central vertex (write-lock), Adjacent vertices (read-locks) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
  • 60.
    Consistency - DistributedLocking Engine Associating a readers-writer lock with each vertex. Vertex consistency • Central vertex (write-lock) Edge consistency • Central vertex (write-lock), Adjacent vertices (read-locks) Full consistency • Central vertex (write-locks), Adjacent vertices (write-locks) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
  • 61.
    Consistency - DistributedLocking Engine Associating a readers-writer lock with each vertex. Vertex consistency • Central vertex (write-lock) Edge consistency • Central vertex (write-lock), Adjacent vertices (read-locks) Full consistency • Central vertex (write-locks), Adjacent vertices (write-locks) Deadlocks are avoided by acquiring locks sequentially following a canonical order. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 35 / 42
  • 62.
    Fault Tolerance Amir H.Payberah (Tehran Polytechnic) GraphLab 1393/9/8 36 / 42
  • 63.
    Fault Tolerance -Synchronous The systems periodically signals all computation activity to halt. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 37 / 42
  • 64.
    Fault Tolerance -Synchronous The systems periodically signals all computation activity to halt. Then synchronizes all caches (ghosts) and saves to disk all data which has been modified since the last snapshot. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 37 / 42
  • 65.
    Fault Tolerance -Synchronous The systems periodically signals all computation activity to halt. Then synchronizes all caches (ghosts) and saves to disk all data which has been modified since the last snapshot. Simple, but eliminates the systems advantage of asynchronous com- putation. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 37 / 42
  • 66.
    Fault Tolerance -Asynchronous Based on the Chandy-Lamport algorithm. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
  • 67.
    Fault Tolerance -Asynchronous Based on the Chandy-Lamport algorithm. The snapshot function is implemented as an update function in vertices. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
  • 68.
    Fault Tolerance -Asynchronous Based on the Chandy-Lamport algorithm. The snapshot function is implemented as an update function in vertices. The snapshot update takes priority over all other update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
  • 69.
    Fault Tolerance -Asynchronous Based on the Chandy-Lamport algorithm. The snapshot function is implemented as an update function in vertices. The snapshot update takes priority over all other update functions. Edge Consistency is used on all update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
  • 70.
    Fault Tolerance -Asynchronous Based on the Chandy-Lamport algorithm. The snapshot function is implemented as an update function in vertices. The snapshot update takes priority over all other update functions. Edge Consistency is used on all update functions. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 38 / 42
  • 71.
    Summary Amir H. Payberah(Tehran Polytechnic) GraphLab 1393/9/8 39 / 42
  • 72.
    GraphLab Summary Asynchronous model Vertex-centric Communication:distributed shared memory Three consistency levels: full, edge-level, and vertex-level Partitioning: two-phase partitioning Consistency: chromatic engine (graph coloring), distributed lock engine (reader-writer lock) Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 40 / 42
  • 73.
    GraphLab Limitations Poor performanceon Natural graphs. Amir H. Payberah (Tehran Polytechnic) GraphLab 1393/9/8 41 / 42
  • 74.
    Questions? Amir H. Payberah(Tehran Polytechnic) GraphLab 1393/9/8 42 / 42