日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

Extending Fregel for Functional Vertex-centric
Graph Processing with Remote AccessYongzhe Zhang

Kento Emoto

Zhenjiang Hu

Fregel provides a functional interface and a clear functional semantics to let users easily write vertex-centric
programs. Unfortunately, Fregel is limited in its lack of support for remote access (reading or writing attributes of other vertices through reference), which makes it hard to describe a class of important graphalgorithms that communicate over dynamic internal data structures. In this paper, we propose to extend
Fregel to support remote access by introducing more language constructs to concisely represent remotereads and writes. We show how this extension can be eﬃciently implemented and evaluate it through some
practical examples.

tuitive for programmers to implement graph algo-

1 Introduction

rithms in Pregel’s imperative and message-passing

Nowadays, more and more real-world applica-

style [3, 6, 17], especially when the algorithm con-tions rely on the big graph data, which makes par-sists of multiple stages and complicated data de-allel processing of large-scale graphs very impor-pendencies.

tant.

To handle graphs in such scale, Google’s

need to write an exceedingly complicated vertex

For such algorithms, programmers

Pregel [10] system adopts the vertex-centric pro-

program, which encodes all the stages of the al-gramming model (also known as ”think like a ver-gorithm.

tex” paradigm), which supports scalable big graphharder to maintain, because one has to trace where

processing through iterative supersteps that exe-

the messages are from and what information theycute in parallel a user-defined vertex program overcarry in each superstep. To address this problem,

each vertex of a graph. There are several open-

several domain-specific languages are proposed tosource graph processing frameworks that are influ-

provide a more intuitive way of Pregel program-

enced by Pregel, such as GraphLab [9], Giraph [1]ming, such as Green-Marl [7], Fregel [3], s6raph [11]and Pregel+ [15].

and Palgol [17]. In these DSLs, instead of the mes-

Despite the power of Pregel, it is however unin-

Message passing makes the code evensage passing interface, programmers are provided
with a more convenient abstraction so that theyThis is an unrefereed paper. Copyrights belong to
the Author(s).
Yongzhe Zhang, Zhenjiang Hu, 総合研究大学院大学複合科学研究科情報学専攻/国立情報学研究所, Department of Informatics, School of Multidisciplinary Sciences, SOKENDAI; National Institute of Informatics (NII).
Kento Emoto, 九 州 工 業 大 学, Kyushu Institute ofTechnology.

can directly access data from a vertex’s neighborhood, then the compiler helps to generate a correctvertex-centric Pregel program in terms of supersteps and message passing.
Although the core idea of these DSLs are
similar, they have diﬀerent focuses and designs,
which makes them distinguishable from each other.

Among them, Fregel provides a purely functional

Pregel.

model for Pregel, modeling the Pregel computa-

In this paper, we propose an extension of Fregeltion as a special higher-order function fregel, andwhich fully integrates the remote access capacities

letting users to declaratively specify the step func-

to Fregel, and thus provides a more powerful func-

tions (used in fregel) to update a vertex’s statetional interface for vertex-centric graph processing.

using the information from the vertex’s neighbor-

Our technical contributions can be summarized as

hood. In spite of the functional interface and thefollows.

clear semantics that make Fregel programs suitable• We extend Fregel to support remote access byfor reasoning, its restriction of data access only toallowing each vertex to store and update refer-the neighborhood makes it hard to describe many

ence values. To deal with remote writing ininteresting graph algorithms that need global com-a functional manner, we propose a two-stepmunicate, say through dynamic internal data struc-

method showing that a remote write can betures.

realized by composition of two remote reads.

Fortunately, Palgol [18], a new domain spe-

• We show that the extended Fregel can be eﬃ-

cific language for vertex-centric computation, in-ciently implemented by defining a transforma-

troduces a good mechanism for remote (data) ac-tion from this extened Fregel to Palgol. As an

cess, which highly improves the expressiveness ofapplication, we demonstrate its use in parallel

the excising languages with powerful communica-

computation of a class of interesting graph al-tion capability. This remote access makes it possi-

gorithms using the pointer jumping technique.

ble to describe those eﬃcient algorithms that need

The organization of the rest of the paper is as fol-the pointer jumping technique (a representative ex-lows. Section 2 explains the background of Pregel,

ample will be presented in Section 3. 4). However,

Fregol and remote access. Section 3 describes the

Palgol is an imperative language and its seman-extension of Fregel, then Section 4 explains thetics with remote access is not clearly defined, whichtransformation from the extended Fregel to Palgol.

makes Palgol programs diﬃcult to reason about.

We discuss related work in Section 5, and conclude

A natural question arises: can we have a DSL

the paper in Section 6.

that combines the advantages of both Fregel and
Palgol? Or put it in another way, is it possible to2 Backgrounddesign a DSL that can have both a functional in-

In this section, after briefly reviewing the Pregel-terface (for easy reasoning) and the remote accesslike systems, we give an overview of Fregel, the tar-capacity (for high expressiveness)? A straightfor-

get language to be extended, and explain the re-ward idea is to extend Fregel with the remote ac-

mote access capability in Palgol.

cess capacity Palgol has. However, there are twochallenges in this extension. One challenge is how

2. 1 The Pregel-like Systems

to express the remote access (remote reads and re-Pregel [10] is a framework proposed for process-mote writes) as a pure function of a vertex updat-

ing large-scale graphs in the vertex-centric manner,

ing function. Remote writing, a destructive action,and there are several Pregel-like open-source frame-

does not seem to fit to a functional setting. The

works [1, 5, 9, 12, 15] that have been implemented.

other challenge is how to transform this high-level

In Pregel, the computation is divided into finite

remote access to the lower-level message passing in

number of supersteps, and within in each superstep,every vertex computes the same user-defined function in parallel to accomplish the logic of a given al-}
type Edge a b = (b, Vertex a b)

gorithm. The same user-defined function typicallywhere an edge is a pair of its label and the vertex

does the following things in a superstep:

it points to. Then, a graph is represented by a list

• read the messages sent from the previous superstep;• perform the local computation and change
current vertex’s state;• send messages to other vertices.
When all the vertices finish the local computationin each superstep, all vertices perform the bulk synchronization, where the messages sent in the lastsuperstep are handled by the system, and are delivered before the next superstep. In addition to
the message exchange, Pregel provides an interface

of vertices:
type Graph a b = [ Vertex a b]

For instance, the following is an example of a graphg containing 5 vertices:g :: Graph Bool Int
g = letv0 = Vertex 0 True []v1 = Vertex 1 True [(1 , v0 )]v2 = Vertex 2 True [(1 , v0 )]v3 = Vertex 3 True [(1,v1),(1,v2),(1,v4 )]v4 = Vertex 4 False []in [v0 , v1 , v2 , v3 , v4]

called aggregator, where users can provide an opera-

Since every vertex stores its neighbors, such repre-tion, such as sum or max, to collectively processing

sentation forms a potentially cyclic data structure.

global information from all vertices. Furthermore,

2. 2. 2 Core of Fregelvertex inactivation is also provided for terminat-

Figure 1 presents the core part of the syntax ofing the computation or optimizing the program byFregel. A Fregel program defines a function thatskipping some vertices.

takes a single input graph and returns a resultant
graph. The expressions in Fregel are standard ones

2. 2 Fregel: Functional DSL for Pregelin Haskell: a combine function applied to a compre-

Fregel [3] is a high-level functional DSL for

hension with specific generators, table access on aPregel, but it does not use explicit message passing

vertex v followed by the field selection operator de-

like Pregel. Instead, it provides a more convenient

noted by “.ˆ ”), and a graph expression with higher-

abstraction that enables a vertex to update itself

order functions on graphs such as fregel. Thereby accessing its neighbors’ state. Fregel is equipped

are three generators in Fregel: a graph variable towith a compiler that can transform Fregel programs

generate all vertices, and is v / rs v to generatewith neighbor access to Pregel codes with message

every pair of v’s adjacent vertex u connected bypassing. Fregel is a subset of Haskell, so it is pos-an incoming or reversed edge and the value on thissible to execute a Fregel program using an Haskell

edge.

intepreter for debugging or testing.

There are two kinds of definitions in let-

2. 2. 1 Graph Model

expressions: ones for a definition of a normal func-

In Fregel, a vertex has the following type, con-tion or constant including an initialization func-

taining its own unique id, the vertex value, and its

tion and ones for a step function, which is the only

incoming neighbors:higher-order function that a user can define. A step

data Vertex a b = Vertex {vid :: Int ,val :: a,is :: [Edge a b]function takes two tables, prev and curr, as well asvertex v, which repeatedly executes the step function. There is another table val that is used to

prog
e

table
tc
comb

:=
:=
|
|
|
|
|
|
|
|
:=
|
:=
|
|
:=
:=
:=

f g = elet decl 1 · · · decl n in e
if e1 then e2 else e3
f e 1 · · · encomb [ e | gen , e1 , . . . , en ]table v .ˆ fld 1 .ˆ · · · .ˆ fld nfregel f1 f2 tc g
gmap f g
gzip g1 g2
giter f1 f2 tc g
f x1 · · · xn = e
f v prev curr = eu ← g(ed, u) ← is v
(ed, u) ← rs v
prev | curr | val
Fix | Until (λ g.e) | Iter e
max | or | · · ·

f
g
u, v
ed
fld

:=
:=
:=
:=
:=

variable representing a function/operator
variable representing a graphvariable representing a vertex
variable representing an edge
field name

図1

Core part of Fregel syntax.

decl
gen

1 data RVal = RVal { rch :: Bool }2
3 reAll g =4
let init v = RVal (vid v == 0)5step v prev curr =6
let newrch =7
prev v .ˆ rch ||8or [ prev u .ˆ rch
9| (e, u) ← is v ]10
in RVal newrch
11
in fregel init step Fix g

図2

A Fregel Program

we thus define a record RVal that contains only thisBoolean value at the rch field in this record (Line1).
The function reAll is the main part of the program, and it defines the initialization and step functions. The initialization function, init, returns an
RVal record in which the rch field is True only if
the vertex is the staring point (vertex identifier iszero). The vertex identifier can be obtained by us-

access the values in the input graph. There areing a special predefined function, vid. The step

three kinds of termination conditions for higher-

function, step, collects data at the previous clockorder functions fregel and giter.

from every adjacent vertex connected by an incom-

It is worth noting that Fregel is equipped withing edge. This is done by using the syntax of com-four higher-order functions for graphs that provide

prehension, in which the generator is is v. For every

ways to concisely write various graph computa-

adjacent vertex u, this program obtains the result

tions. Function fregel corresponds to Pregel’s exe-at the previous clock by prev u and accesses its

cution logic, which execute an initialization step f1

rch field. Then step combines the results of all ad-

at the beginning, then execute a step function f2

jacent vertices by using the or function and returns

until a termination condition is satisfied. Function

the disjunction of the combined value and its own

giter is similar to fregel except that f2 is now arch value at the previous clock.

graph transformation. Function gzip pairs values
on every corresponding vertices in two graphs ofthe same shape, and gmap applies a given vertex
function to every vertex.
As a simple example, the Fregel program in Fig-

2. 3 Remote Access
Remote access is introduced in Palgol [17] forsupporting flexible communications between nonneighboring vertices.

Essentially, it extends theure 2 is to mark True of those vertices that are

peek-based functional model by introducing the fol-reachable from vertex 0, and False otherwise. Notelowing two abstract constructs:that since the step function for this problem returns• global field access: a vertex can access thea Boolean value indicating whether the vertex thatstate of an arbitrary vertex as long as it holds

calls the step function is currently reachable or not,a reference of that vertex. Moreover, users canexpress chain access, which accesses some re-Fregel has the table lookup interface for represent-

mote data by following the references several

ing data access, but only with its list comprehen-times.

sion syntax we can extract its neighbors’ vertex• remote write: a vertex can modify the state ofidentifier and perform neighborhood data access.

another vertex by specifying the update value,

To enable remote read from an arbitrary vertex,

the destination vertex, the field to update, as

we slightly modify our model that allow a vertex

well as a unique reduce operator. Then, an

to store a reference to some other vertex, and pro-additional superstep is attached at the end ofvide a table lookup interface to enable remote data

current logic superstep to transfer the messages

access through reference. To achieve so, we extend
the definition of the step function f †1 in Figure 1

and perform the update accordingly.
With these two construct, more Pregel algo-fromrithms with non-ordinary communication patterns
can be implemented, including a class of eﬃcientf v prev = e
toPregel algorithms that apply the pointer jumping
technique [2, 16].

f v prev refs = ewhere the step function has the new type of
StepFunc defined sa follows:

3 Extension of FregelIn this section, we describe our extension ofFregel to support remote access. We first show how
to extend Fregel to describe remote reads and re-data VRef = VRef { idx :: Int }type StepFunc a b r = Vertex a b-> ( Vertex a b -> a)-> (VRef -> a)-> rmote writes. Then, we present a Haskell implemen-First, we introduce a new data type VRef, whichtation of our extended Fregel to help user better un-

is essentially a simple wrap of some other vertex’s

derstand the semantics of this extension. Finally,

identifier (which has type Int). A value with this

we provide an example to show how we can easily

type exactly represents a reference to other vertex.

describe algorithms using our extension of remote

Then, two tables are passed into the step function,access.

which are:
• A prev table with type Vertex a b -> a al-

3. 1 Remote Reads through Referencelows a vertex to access the state of a neighbor-

Palgol introduces a special syntax called field ac-

ing vertex in the previous logical step. This is

cess for representing remote reads through refer-exactly the same as the original Fregel’s prev

ence, which is in the form of FieldName[exp]. In

table.

this expression, FieldName is a user-specified field,• A refs table with type VRef -> a allows aand exp is an expression with a special type calledvertex to access the state of an arbitrary ver-reference (and physically, it is just the vertex identi-

tex in the previous logical step via a reference.

fier) which refers to some vertex. Then, the seman-

To see how this new interface works, consider antics of such field access expression is to fetch the

input graph having the form of a rooted tree where

specified field from the designated vertex. Could

each vertex initially has a reference to is parent

we add the concepts of field access and reference to(root vertices point to themselves), and we want ev-

Fregel?
The solution turns out to be natural. Initially,†1 We omit the argument curr in f , since curr isplanned to be removed in Fregel.

ery vertex to compute its grandparent (the parent

3. 3 Haskell Implementationof parent). Suppose the input data structure has

As mentioned in Section 2. 2, Fregel is a subset ofa field parent to store the reference to the parent,

Haskell, and a concrete implementation of Fregel inwe can obtain the grandparent using the following

Haskell given by the authors can not only help pro-step function:

grammers understand the behavior of Fregel better,data VD = VertexData {parent :: VRef ,grandp :: VRef}step :: StepFunc VD Int VD
step v prev refs =let
p = prev v.ˆ parentg = refs p.ˆ parent
in VertexData p g

but also make them easier to test and debug theFregel programs. Following this methodology, we
provide a Haskell implementation for our extension
on Fregel. The new implementation turns out tobe incremental: we just slightly change the definition of fregel, introduce a new high-order function
called gmaps to convert a step function to a singlestep graph transformation, and add an auxiliary
function getVertexRef to create a reference from a

3. 2 Remote Writes

vertex, as seen in Figure 3.

In the Fregel’s functional model, each vertex

The semantics of gmaps is explained in terms ofbasically executes a pure function which collects

the slightly revised higher-order function fregel

data from its neighbors and generates a new vertex

that is adapted from the original definition in [3]state, therefore it is hard to model remote writes infor coping with the new step function having theFregel where a vertex directly modifies other ver-reference table. Essentially, the fregel function

tices’ states. To support Pregel algorithms thatsimulates a pregel computation. It takes four argu-

require the remote write capacity, we introduce aments as input (fregel h f t g) and produces an

new approach that uses two steps to simulate theoutput graph. More detailed, h is an initialization

remote writes in the functional model.

function that executes just once beginning, and f

The basic idea is simple. Recall that a remote

is a step function that is applied to the graph again

write essentially requires a vertex to specify theand again. Finally, the t provides diﬀerent ways

destination vertex, the value to update, and theof terminating a computation, and we can just use

operation that is performed on the destination ver-

“Iter 1” to say that the step function executes ex-

tex to handle the updates. So, in our functional

actly once.

model, we can use two logical steps to achieve this:

The importance of introducing such gmaps is to• In the previous logical step, a vertex stores thebetter support the remote writes: when specify-

reference to the remote vertex and the update

ing two consecutive step functions, the gmaps func-

value in the vertex value.

tion can turn each step into a graph transformation,• In the consequent logical step, we use theand functions in such types are much easier to belist comprehension syntax with a special global

composed together. In the following, we will see

generator (u <- g) to let a vertex v update it-

how this function helps writing concise and intu-

self (i.e., write) by collecting all those vertices

itive Fregel code.

that store a reference to v.
We will see a concrete example in Section 3. 4.

fregel :: ( Vertex a b -> r) -> StepFunc a b r -> Term ( Graph r b) -> Graph r bfregel h f t g =let rs0 = map h g
step rs = let rs ’ = map (\v -> f v prev refs) g
prev u = rs !! ( getVertexId u)
refs r = rs !! (idx r)
in rs ’
rss = iterate step rs0
in termination t (map ( graphy g) rss)
gmaps :: StepFunc a1 b a2 -> Graph a1 b -> Graph a2 b
gmaps f g = fregel default_init f (Iter 1) g
where default_init Vertex { val = v } = v
getVertexRef :: Vertex a b -> Ref
getVertexRef Vertex { idx = r } = VRef r
図3

Defintions of revised fregel and gmaps.

3. 4 An Application

point to t if t < D[u] (to guarantee the correct-

As an application, let us consider a slightly

ness of the algorithm). When having multiple

more complex example called Shiloach-Vishkin con-choices in choosing the neighbors’ parent p, or

nected component algorithm [16], which requires

when diﬀerent vertices try to modify the same

both remote reads and writes in its algorithm de-parent vertex’s pointer, the algorithm always

scription.

uses the “minimum” as the tiebreaker for fast

In the S-V algorithm, the connectivity informa-convergence.

tion is maintained using the classic disjoint set data

• pointer jumping: if D[u] is not a root ver-structure [4]. Specifically, the data structure is atex, then u modifies its own pointer to its

forest, and vertices in the same tree are regarded as

current “grandfather” (D[u]’s current pointer).

belonging to the same connected component. EachThis operation reduces u’s distance to the root

vertex maintains a parent pointer that either points

vertex, and will eventually make u a direct

to some other vertex in the same connected com-child of the root vertex so that it can perform

ponent, or points to itself, in which case the vertex

the above tree merging operation.

is the root of a tree. We henceforth use D[u] to

The algorithm terminates when all vertices’ point-

represent this pointer for each vertex u. The S-V

ers do not change after an iteration, in which casealgorithm is an iterative algorithm that begins withall vertices point to some root vertex and no more

a forest of n root nodes, and in each step it tries totree merging can be performed. Readers interested

discover edges connecting diﬀerent trees and merge

in the correctness of this algorithm are referred tothe trees together. In a vertex-centric way, every

the original paper [16] for more details.

vertex u performs one of the following operations

Figure 6 shows the implementation of this algo-depending on whether its parent D[u] is a root ver-rithm in our extended Fregel. The whole program istex:represented by the expression giter init ss Fix• tree merging: if D[u] is a root vertex, theng, where init is the initialization function that setsu chooses one of its neighbors’ current parent

the parent pointer to itself at the beginning, and(to which we give a name t), and makes D[u]the ss is a graph transformation which implements

data VD1 = VD1 { p1 :: VRef }data VD2 = VD2 { p2 :: VRef , p3 :: VRef , gr :: VRef }sv g = letinit v = VD1 ( getVertexRef v);
step1 g = let
s1 v prev refs =let gr = refs (prev v.ˆ p1 ).ˆ p1
t = minimum ( ( getVertexRef v) :[( prev w.ˆ p1) | (e, w) <- is v])
in VD2 (prev v.ˆp1) t gr
in gmaps s1 g
step2 g = let
s2 v prev refs =let t = minimum (( prev v.ˆ gr) :[ prev u.ˆ p3| u <- g,prev u.ˆ p2 == getVertexRef v,
prev v.ˆ p2 == getVertexRef v])
in VD1 t
in gmaps s2 g
ss = step2 . step1
in giter init ss Fix g
図4

The S-V algorithm in extended Fregelthe main function in the iteration. This program
terminates when the graph does not change after
an iteration.
Let us first focus on the ss, which is composedcurrent parent in a temporary data type VD2.
Next, we look at step2, which exactly follows
step1 and finishs the remote write described in
the algorithm.

In detail, every root vertex col-by two smaller graph transformations step1 andlects those vertices that are trying to write data

step2, each containing a single logical step. step1

to itself, and further takes the minimum of thoseis firstly performed to collect the id of grandpar-

update values as the final vertex state. This com-ent as well as all neighbors’ parents. The expres-putation is exactly encoded in the calculation ofsion gr = refs (prev v.ˆp1).ˆp1 calculates thevariable t. Semantically, every vertex uses a list

grandparent: prev v.ˆp1 is current vertex v’s par-comprehension with generator u <- g to look atent, which is stored as a reference on v; then we

the whole graph, and uses the filters to find thosefetch the parent node’s state via the refs table, andones pointing to it (prev u.ˆp2 == getVertexRef

further get the parent field p1, and bind it to a vari-v) as well as checks whether the vertex itself is aable gr. According to the algorithm, if a vertex is aroot vertex (prev u.ˆp2 == getVertexRef v). In

root, we need to perform a remote write to modify

the case where v is not a root vertex, the vertex

the parent pr’s pointer, but in our implementation

performs the pointer jumping that sets its parent

we delay the checking and just prefetch the neigh-as the grandparent calculated in the previous step.

bors’ minimum parent value, which is achievedby the expression minimum ( (getVertexRef v) :4 Code Transformation[(prev w.ˆp1) | (e, w) <- is v]). Finally, we

In this section, we sketch how to transform thestore the grand parent, the update value, and the

major part of our extended Fregel to Pregel code,based on the fact that Palgol is equipped with re-of code contains two steps, where the first one

mote access capacity with high eﬃciency, and that(lines 1–3) performs simple initialization, and thewe can use Palgol’s compiler to generate the Pregelother (lines 5–13) is inside an iteration as the maincode. The purpose of this transformation is justcomputation.

to verify the feasibility of our extended Fregel, andthe pointer to the parent vertex.

show its potential to be compiled to eﬃcient Pregel

checks whether u’s parent is a root, by just writ-code.

We also use the field D to store
First, line 6

ing D[D[u]] == D[u], i.e., whether the pointer ofthe parent vertex D[D[u]] is equal to the parent’s

4. 1 The Palgol Language

id D[u].

Palgol [18] is a high-level imperative DSL forlist containing all neighboring vertices’ parent id

Pregel, where the vertex-centric graph applications(D[e.ref ]), and then bind the minimum one to theare described in terms of atomic Palgol steps andvariable t (line 7). Now t is either inf if the neigh-combinators. A Palgol step is basically a simple

bor list is empty or a vertex id; in both cases wegraph transformation described in a vertex-centric

can use it to update the parent’s pointer (lines 9–

way, where a vertex can use several pre-defined con-10) via a remote assignment. One important thing

structs to fetch data from neighbors or through ref-is that the parent vertex (D[u]) may receive many

erence, perform local computation just like an ordi-

remote writes from its children, where only one ofnary imperative programming language, generate athe children providing the minimum t can success-new vertex state and/or write to the other vertices.

fully perform the updating. Here, the statement a

Then, such atomic steps can be composed or iter-<?= b is an accumulative assignment, whose mean-

ated, so that control flows including sequences anding is the same as a := min(a, b). Finally, for theiterations can be implemented.

else branch, we (locally) assign u’s grandparent’s

Figure 5 presents the essential syntax of Palgol.

If u’s parent is a root, we generate a

id to u’s D field.

Regarding its unique remote access capacities, in
Palgol we can read a field of an arbitrary vertex

4. 2 Compiling Extended Fregel to Palgolusing a global field access expression of the form

The transformation from our extended Fregel tofield [ exp ], where field is a user-specified field name

Palgol is conceptually direct, because of the simi-

and exp should evaluate to a vertex id. Such ex-larity in the structures of these two languages. In

pression can be further updated by an remote as-

the extended Fregel, a vertex-centric computation

signment, which consists of a remote field, a value

is represented by a pure step function that takes

and an “accumulative” assignment (like += and |=).

a graph as input and produces a new vertex state;

According to Palgol’s high-level model, such remotethese functions are further combined by a set of pre-assignment are handled in an additional superstep

defined higher-order functions to implement a com-

attached at the end of current step, and the field ofplete graph algorithm. Palgol borrows this idea inthe destination vertex is then modified by execut-

the language design by letting programmers write

ing the assignment with the value on its right-handatomic vertex-centric computations called Palgol

side.

steps, and similarly, we can put them together using

To give a feeling of the Palgol language, we

two combinators, namely sequence and iteration.

present the original Palgol code for the S-V al-

The transformation can be generally divided into

gorithm, which is shown in Figure 6. This piecetwo steps. First, we need to recover the dependen-

prog

::=

step | prog1 . . . progn | iter

iter

::=

do ⟨ prog ⟩ until fix [ field1 , . . . , fieldn ]|iter var in range (int, int) ⟨ prog ⟩ end

step

::=

for var in V ⟨ block ⟩ end

block

::=

stmt1 . . . stmtn

stmt

::=

if exp ⟨ block ⟩ | if exp ⟨ block ⟩ else ⟨ block ⟩|for (var ← exp) ⟨ block ⟩|let var = exp|

localopt field [ var ] oplocal exp|

remote field [ exp ] opremote exp::=

int | float | var | true | false | inf|

fst exp | snd exp | (exp, exp)|

exp.ref | exp.val | {exp, exp} | {exp}|exp ? exp : exp | ( exp ) | exp opb exp | opu exp|

field [ exp ]|funcopt [ exp | var ← exp, exp1 , . . . , expn ]::=maximum | minimum | sum | . . .

exp

func

図5

Essential part of Palgol’s syntax.

giter init ss Fix g
1
2
3
4
5
6
7
8
9
10
11
12
13
14

for u in V
D[u] := u
end
dofor u in V
if (D[D[u]] == D[u])let t = minimum [ D[e.ref]| e <- Nbr[u] ]if (t < D[u])remote D[D[u]] <?= telse
D[u] := D[D[u]]enduntil fix[D]図6

The S-V algorithm in Palgol

in Figure 4 which says that, from the original graphg, the init function is first executed, then we iteratively execute the graph transformation ss until
the graph stabilize, which corresponds to Palgol’s
iteration construct
do ..

until fix[..]We just need to put init before the iteration, put
ss inside the iteration and put all of g’s fields inside
fix[..], which means the iteration ends when thespecified fields stabilize.
Next, according to the code ss = step2 .
step1, we know that ss is actually composed bycies of graphs from the higher-order functions, thentwo smaller steps, while step1 and step2 cannot be

we transform each step function to a corresponding

further divides since each of them contains just a

Palgol step, and combine them in a proper order

step function.

with Palgol’s combinator. Rather than diving into

Eventually, we obtain the structure of the Palgol

formal definition of the transformation, we shall use

program, which is shown below:

the code in Figure 4 to illustrate how the transfor-[init is compiled here]
do[s1 is compiled here][s2 is compiled here]mation is performed.
Let us starting by condiering the code.

until fix [..]

The compilation of each step function is performed by converting the communication primitives
in the extended Fregel to the corresponding onesin Palgol, and transforming the functional code toequivalent imperative ones. Let us return to thecode in Figure 4. For example, the neighborhood
access expression in Fregel[(prev w.ˆp1) | (e, w) <- is v]
iterates over the neighboring list and collects theirpreviously calculated p1 field; in Palgol, the representation is basically the same. It is transformed
to Palgol as

the vertex. Having recognized such intension, we
naturally transform this expression by two steps.
In the first step, all vertices write a value (which
is P3 according to the Fregel code) to vertex P2,
and the remote write is made to a temporary fieldT with a minimum operation which can be found in
the Fregel program. Then in the second step, allvertices just read the T field to collect the result of
remote write, and then move on to the consequent
computation.
Finally, we get the following transformed result
for the S-V program. Although it looks diﬀerent
from the Palgol’s original implementation of the SV algorithm, it actually does the same job.

[ P1[e.ref] | e <- Nbr[u] ]where Nbr is the neighboring list, e.ref is the reference to a neighboring vertex, and P1[e.ref] fetch
the value of P1 field†2 of the neighboring vertex.
Then, the expression for remote read refs (prevv.ˆp1).ˆp1 (which can also be written as p1 (refs(p1 (prev v)))) is transformed to a Palgol expression P1[P1[u]], which follows the reference toparent (P1 field) twice to get the grandparent. In
Fregel, local access and remote reads use two different tables prev and refs, but Palgol just has aunified interface P1[..] for both local and remotefield access.
One tricky transformation is caused by the remote access in our extended Fregel, and an example
is the following expression:[ prev u.ˆ p3 | u <- g,prev u.ˆ p2 == getVertexRef v,
prev v.ˆ p2 == getVertexRef v ]for u in V
let t = minimum [ e.ref | e <- Nbr[u] ]P1[u] := (u < t ? u : t)
end
dofor u in V
let t = minimum [ P1[e.ref]| e <- Nbr[u] ]P3[u] := (u < t ? u : t)Gr[u] := P1[P1[u]]P2[u] := P1[u]endfor u in V
T[u] := inf
if (P2[u] == Gr[u])remote T[P2[u]] <?= P3[u]endfor u in V
P1[u] := (Gr[u] < T[u] ? Gr[u] : T[u])enduntil fix[P1]

It is worth noting that despite the similarity inthese two languages, there are several diﬀerences
between them which should be carefully taken into

Briefly speaking, a vertex is now collecting dataconsideration when designing the transformationfrom all vertices in the graph, which is usually notalgorithm. Here, we summarize them and give an

so realistic in real graph applications, but from theidea of how they can be solved.

filter prev u.ˆp2 == getVertexRef v we can re-• Dependency: Palgol program has a clear ex-cover the real intension: u is going to perform aecution order, while the extended Fregel canremote write to v and stores a link in its P2 field inspecify the computation in a declarative way,

†2 in Palgol, field name should be capital letterfor example, the gzip function combines two

graphs together without saying which one

ming, many DSLs have been proposed, such as

evaluates first. Therefore, dependency check

Palovca [8], s6raph [11], Fregel [3] and Green-

should be perform to generate a valid struc-

Marl [7]. We briefly introduce each of them below.

ture of the Palgol program.

Green-Marl [6] is a DSL that allows program-• Vertex fields: Palgol is an imperative language

mers to describe a graph algorithm at a higherthat exposes all vertex fields to the program-level. Originally proposed for graph processing on

mers at the beginning, and a vertex can manip-

shared-memory multi-processors, it is extended [7]ulate arbitrary vertex fields in any part of theto support Pregel systems, where the compilation

program. In contrast, Fregel has a functional

to Pregel relies on discoveringmodel where each step function can only accesspatterns. Since it does not have a Pregel-specificthe fields of the input graph feed to it. To filllanguage design, programmers may easily get com-this gap, we should calculate a mapping frompilation errors if they are not familiar with the im-

the graph in Fregel to a set of corresponding

plementation of the compiler. Besides, there is still

fields in Palgol in advance.

a wide range of Pregel algorithms that cannot be

Pregel-canonical

It should also be noted that there is still a few

implemented or eﬃciently expressed in Green-Marl,constructs in Fregel that cannot be directly trans-

due to the limitation in expressing remote access.

lated to Palgol, such as the termination condition

Fregel [3] is a functional DSL for declarative pro-

Until. Nevertheless, this is mainly due to the lim-

gramming on big graphs. In Fregel, a vertex-centric

itation in Palgol’s high level combinator and cancomputation is represented by a pure function thatbe easily fixed by hand-written some code. Basedtakes a graph as input and produces a new vertex

on the transformation algorithm described in thisstate; such functions can then be composed using a

subsection as well as Palgol’s own compiling algo-

set of predefined combinators to implement a com-rithm [17], it is our future work to directly compile

plete graph algorithm. This approach not only pre-our extended Fregel to Pregel code.

vents programmers from writing invalid programs,
but also helps people to better understand the be-

5 Related Workhavior of a vertex-centric program. However, dueGoogle’s Pregel [10] proposed the vertex-centric

to the same reason as Green-Marl, it is also limited

computing paradigm, which allows programmers toin expressiveness.

think naturally like a vertex when designing dis-

S6raph [11] is a special graph processing frame-

tributed graph algorithms. Some graph-centric (orwork with a functional interface. It models a partic-

block-centric) systems like Giraph++ [13] and Blo-ular type of iterative svertex-centric computation

gel [14] extends Pregel’s vertex-centric approach byby six functions, which are specified by program-

making the partitioning mechanism open to pro-mers to implement diﬀerent algorithms. Comparedgrammers, but it is still unclear how to optimize

to Green-Marl and Fregel, s6raph can only repre-

general vertex-centric algorithms (especially thosesent graph algorithms that contain a single iterativecomplicated ones containing non-trivial communi-

computing (such as PageRank and Shortest Path),

cation patterns) using such extension.

while many practical Pregel algorithms are far more

Domain-Specific Languages (DSLs) are a wellknown mechanism for describing solutions in specialized domains.

To ease Pregel program-complicated. In exchange, s6raph programs can be
written concisely and executed eﬃciently.
Palgol [17] is an imperative DSL which is inte-grated with the remote access capacities. Similar
to Fregel, a Palgol program is composed by vertex
programs and high-level combinators, but a vertex
program in Palgol contains an additional remotewrite phase, which allows a vertex to send the updates to other vertices. In addition, it proposesa new abstraction, chain access, for representing
fetching data from a reference, which is useful fora class of Pregel algorithms.

6 Conclusion
In this paper, we report our work-in-progress toextend Fregel with remote access to enhance its
expressiveness.

The basic idea is to enrich ver-tex attributes with reference and to treat the reference as the first class value during each iteration.
We formally define the semantics of this extension, demonstrate a nontrivial application, and informally show how this extension can be eﬃciently
compiled to Pregel though Palgol.

We are now

working on the implementation and will give morepractical evaluation in the future.
参 考 文 献[ 1 ] : Apache Giraph, http://giraph.apache.org/.
[ 2 ] Chung, S. and Condon, A.: Parallel implementation of Borůvka’s minimum spanning tree algorithm, IPPS, IEEE, 1996, pp. 302–308.
[ 3 ] Emoto, K., Matsuzaki, K., Morihata, A., andZhenjiang, H.: Think like a vertex, behave like afunction! A functional DSL for vertex-centric big
graph processing, ICFP, ACM, 2016, pp. 200–213.
[ 4 ] Gabow, H. N. and Tarjan, R. E.: A linear-timealgorithm for a special case of disjoint set union, J.
Comput. System Sci., Vol. 30, No. 2(1985), pp. 209–
221.
[ 5 ] Gonzalez, J. E., Low, Y., Gu, H., Bickson, D.,
and Guestrin, C.: PowerGraph: distributed graphparallel computation on natural graphs, OSDI,

2012, pp. 17–30.
[ 6 ] Hong, S., Chafi, H., Sedlar, E., and Olukotun,
K.: Green-Marl: a DSL for easy and eﬃcient graphanalysis, ASPLOS, ACM, 2012, pp. 349–362.
[ 7 ] Hong, S., Salihoglu, S., Widom, J., and Olukotun, K.: Simplifying scalable graph processing
with a domain-specific language, CGO, ACM, 2014,
pp. 208.
[ 8 ] Lesniak, M.: Palovca: describing and executing
graph algorithms in Haskell, PADL, Springer, 2012,
pp. 153–167.
[ 9 ] Low, Y., Bickson, D., Gonzalez, J., Guestrin,C., Kyrola, A., and Hellerstein, J. M.: Distributed GraphLab: a framework for machine learning and data mining in the cloud, PVLDB, Vol. 5,
No. 8(2012), pp. 716–727.
[10] Malewicz, G., Austern, M. H., Bik, A. J., Dehnert, J. C., Horn, I., Leiser, N., and Czajkowski, G.:
Pregel: a system for large-scale graph processing,
SIGMOD, ACM, 2010, pp. 135–146.
[11] Ruiz, O. C., Matsuzaki, K., and Sato, S.:
s6raph: vertex-centric graph processing framework with functional interface, FHPC, ACM, 2016,
pp. 58–64.
[12] Salihoglu, S. and Widom, J.: GPS: a graph processing system, SSDBM, No. 22, ACM, 2013.
[13] Tian, Y., Balmin, A., Corsten, S. A., Tatikonda,
S., and McPherson, J.: From think like a vertex
to think like a graph, PVLDB, Vol. 7, No. 3(2013),
pp. 193–204.
[14] Yan, D., Cheng, J., Lu, Y., and Ng, W.: Blogel: A block-centric framework for distributed computation on real-world graphs, PVLDB, Vol. 7,
No. 14(2014), pp. 1981–1992.
[15] Yan, D., Cheng, J., Lu, Y., and Ng, W.: Eﬀective techniques for message reduction and load balancing in distributed graph computation, WWW,
ACM, 2015, pp. 1307–1317.
[16] Yan, D., Cheng, J., Xing, K., Lu, Y., Ng, W.,
and Bu, Y.: Pregel algorithms for graph connectivity problems with performance guarantees, PVLDB,
Vol. 7, No. 14(2014), pp. 1821–1832.
[17] Zhang, Y., Ko, H.-S., and Hu, Z.: Palgol: A
High-Level DSL for Vertex-Centric Graph Processing with Remote Data Access, Asian Symposium on
Programming Languages and Systems, 2017.
[18] Zhang, Y., Ko, H.-S., and Hu, Z.: Palgol: A
High-Level DSL for Vertex-Centric Graph Processing with Remote Data Access, 15th Asian Symposium on Programming Languages and Systems,
LNCS, Spinger, 2019.