# Joins and meets in effect algebras

G. Bińczak1 1: Faculty of Mathematics and Information Sciences Warsaw
University of Technology 00-662 Warsaw, Poland  ,  J. Kaleta2 2 Department of
Applied Mathematics Warsaw University of Life Sciences 02-787 Warsaw, Poland
and  A. Zembrzuski3 3 Department of Informatics, Faculty of Applied
Informatics and Mathematics, Warsaw University of Life Sciences 02-787 Warsaw,
Poland  1<EMAIL_ADDRESS>2<EMAIL_ADDRESS>3
<EMAIL_ADDRESS>
###### Abstract.

We know that each effect algebra $E$ is isomorphic to $\pi(X)$ for some
$E$-test spaces $(X,{\bf T})$.We describe when $\pi(x)\lor\pi(y)$ and
$\pi(x)\land\pi(y)$ exists for $x,y\in{\bf E}(X,{\bf T})$. Moreover we give
the formula for $\pi(x)\lor\pi(x)$ and $\pi(x)\land\pi(y)$ using only $x,y$
and tests which are elements of ${\bf T}$. We obtain an example of finite, not
homogeneous effect algebra $E$ such that sharp elements of $E$ form a lattice,
whereas $E$ is not a lattice.

###### Key words and phrases:

effect algebra; homogeneity; sharp element

###### 2010 Mathematics Subject Classification:

81P10, 03G12

##  1\. Introduction

Effect algebras have been introduced by Foulis and Bennet in 1994 (see [4])
for the study of foundations of quantum mechanics (see [3]). Independently,
Chovanec and Kôpka introduced an essentially equivalent structure called
$D$-poset (see [9]). Another equivalent structure was introduced by Giuntini
and Greuling in [5]).

The most important example of an effect algebra is $(E(H),0,I,\oplus)$, where
$H$ is a Hilbert space and $E(H)$ consists of all self-adjoint operators $A$
on $H$ such that $0\leq A\leq I$. For $A,B\in E(H)$, $A\oplus B$ is defined if
and only if $A+B\leq I$ and then $A\oplus B=A+B$. Elements of $E(H)$ are
called effects and they play an important role in the theory of quantum
measurements ([1],[2]).

A quantum effect may be treated as two-valued (it means $0$ or $1$) quantum
measurement that may be unsharp (fuzzy). If there exist some pairs of effects
$a,b$ which posses an orthosum $a\oplus b$ then this orthosum correspond to a
parallel measurement of two effects.

In this paper we describe the join and meet in effect algebras. In order to do
this we use algebraic $E$-test spaces in the following way: we know that for
every effect algebra $E$ there exists an algebraic $E$-test space $(X,{\bf
T})$ such that $E$ is isomorphic to $\Pi(X)$ (please see [6]) so it is enough
to describe joins and meets in $\Pi(X)$.

######  Definition 1.1.

In [4] an effect algebra is defined to be an algebraic system $(E,0,1,\oplus)$
consisting of a set $E$, two special elements $0,1\in E$ called the zero and
the unit, and a partially defined binary operation $\oplus$ on $E$ that
satisfies the following conditions for all $p,q,r\in E$:

  1. (1)

[Commutative Law] If $p\oplus q$ is defined, then $q\oplus p$ is defined and
$p\oplus q=q\oplus p$.

  2. (2)

[Associative Law] If $q\oplus r$ is defined and $p\oplus(q\oplus r)$ is
defined, then $p\oplus q$ is defined, $(p\oplus q)\oplus r$ is defined, and
$p\oplus(q\oplus r)=(p\oplus q)\oplus r$.

  3. (3)

[Orthosupplementation Law] For every $p\in E$ there exists a unique $q\in E$
such that $p\oplus q$ is defined and $p\oplus q=1$.

  4. (4)

[Zero-unit Law] If $1\oplus p$ is defined, then $p=0$.

For simplicity, we often refer to $E$, rather than to $(E,0,1,\oplus)$, as
being an effect algebra.

######  Definition 1.2.

If $p,q\in E$, we say that $p$ and $q$ are orthogonal and write $p\perp q$ iff
$p\oplus q$ is defined in $E$. If $p,q\in E$ and $p\oplus q=1$, we call $q$
the orthosupplement of $p$ and write $p^{\prime}=q$. For effect algebras
$E_{1},E_{2}$ a mapping $\phi\colon E_{1}\to E_{2}$ is said to be an
isomorphism if $\phi$ is a bijection, $a\perp b\iff\phi(a)\perp\phi(b)$,
$\phi(1)=1$ and $\phi(a\oplus b)=\phi(a)\oplus\phi(b)$.

It is shown in [4] that the relation $\leq$ defined for $p,q\in E$ by $p\leq
q$ iff $\exists r\in E$ with $p\oplus r=q$ is a partial order on $E$ and
$0\leq p\leq 1$ holds for all $p\in E$. It is also shown that the mapping
$p\mapsto p^{\prime}$ is an order-reversing involution and that $q\perp p$ iff
$q\leq p^{\prime}$. Furthermore, $E$ satisfies the following cancellation law:
If $p\oplus q\leq r\oplus q$, then $p\leq r$.

An element $a\in E$ is sharp if the greatest lower bound of the set
$\\{a,a^{\prime}\\}$ equals $0$ (i.e. $a\land a^{\prime}=0$). We denote the
set of sharp elements of $E$ by $E_{S}$.

For $n\in{\mathbb{N}}$ and $x\in E$ let $nx=x\oplus x\oplus\ldots\oplus x$
($n$-times). We say that ı$(x)=\max\\{n\in{\mathbb{N}}\colon nx$ exists $\\}$
is the isotropic index of $x$.

An atom of an effect algebra $E$ is a minimal element of $E\setminus\\{0\\}$.
An effect algebra $E$ is atomic if for every non-zero element $x\in E$ there
exists an atom $a\in E$ such that $a\leq x$.

In [6] Gudder introduced algebraic $E$-test spaces:

######  Definition 1.3.

Let $X$ be a nonempty set and ${\mathbb{N}}_{0}={\mathbb{N}}\cup\\{0\\}$. For
$f,g\in{\mathbb{N}}_{0}^{X}$, we write $f\leq g$ if $f(x)\leq g(x)$ for all
$x\in X$ and define $f+g\in{\mathbb{N}}_{0}^{X}$ by $(f+g)(x)=f(x)+g(x)$. If
$f\leq g$, we define $g-f\in{\mathbb{N}}_{0}^{X}$ by $(g-f)(x)=g(x)-f(x)$.
Denote by $f_{0}\in{\mathbb{N}}_{0}^{X}$ the function $f_{0}(x)=0$ for all
$x\in X$.

A pair $(X,\bf T)$ is an $E$-test spaces if and only if ${\bf T}\subseteq
N_{0}^{X}$ and the following conditions hold:

  1. (1)

For any $x\in X$ there exists a $t\in\bf T$ such that $t(x)\not=0$.

  2. (2)

If $s,t\in\bf T$ with $s\leq t$, then $s=t$.

######  Definition 1.4.

Let ${\bf E}(X,{\bf T})=\\{f\in{\mathbb{N}}_{0}^{X}\colon f\leq t$ for some
$t\in\bf T\\}$. Let $f,g,h\in{\bf E}(X,{\bf T})$ then

  1. (1)

$f\perp g$ if $f+g\in{\bf E}(X,{\bf T})$,

  2. (2)

$f{\rm\;loc\;}g$ if $f+g\in{\bf T}$,

  3. (3)

$f\approx_{h}g$ if $f+h\in{\bf T}$ and $g+h\in{\bf T}$,

  4. (4)

$f\approx g$ if there exists $h\in{\bf E}(X,{\bf T})$ such that
$f\approx_{h}g$.

We say that $(X,{\bf T})$ is algebraic if for $f,g,h\in{\bf E}(X,{\bf T})$,
$f\approx_{h}g$ and $h\perp f$ imply that $h\perp g$.

######  Definition 1.5.

(see [8]) Let $E$ be a finite effect algebra. The atomic effect test space of
$E$ is the pair $({\rm At}(E),{\bf T})$, where ${\rm At}(E)$ is the set of all
atoms of $E$ and

${\bf T}=\\{t\in{\mathbb{N}}_{0}^{E\setminus\\{0\\}}\colon{\rm
supp}(t)\subseteq{\rm At}(E)\land\bigoplus_{a\in E}t(a)a=1\\}$

The elements of ${\bf T}$ are called atomic tests of $E$. We say that a
mapping $f\in{\mathbb{N}}_{0}^{E\setminus\\{0\\}}$ is an atomic event of $E$
iff there is a $t\in{\bf T}$ such that $t\geq f$. For an atomic event $f$ of
$E$, we write shortly $\bigoplus f$ instead of $\bigoplus_{a\in{\rm
At}(E)}f(a)a$.

Let $(X,\bf T)$ be an algebraic $E$-test space. If $f\in{\bf E}(X,{\bf T})$,
we define $\pi(f)=\\{g\in{\bf E}(X,{\bf T})\colon g\approx f\\}$ and

$\Pi=\Pi(X)=\\{\pi(f)\colon f\in{\bf E}(X,{\bf T})\\}$

We define $0,1\in\Pi$ by $0=\pi(f_{0})=\\{f_{0}\\}$ and $1=\pi(t)$ for any
$t\in\bf T$. We define $\pi(f)^{\prime}=\pi(g)$ if $g{\rm\;loc\;}f$ (such $g$
exists since there exists $t\in\bf T$ such that $f\leq t$ and then $t-f\in{\bf
E}(X,{\bf T})$ and $(t-f){\rm\;loc\;}f$). We define
$\pi(f)\oplus\pi(g)=\pi(f+g)$ when $f\perp g$.

######  Theorem 1.6.

[6, Theorem 3.2] If $(X,\bf T)$ is an algebraic $E$-test space, then $\Pi(X)$
can be organized into an effect algebra.

######  Theorem 1.7.

[6, Theorem 3.3] If $P$ is an effect algebra, there exists an algebraic
$E$-test space $(X,\bf T)$ such that $P$ is isomorphic to $\Pi(X)$.

Thanks to the above theorems the study of effect algebras can be reduced to
the study of effect algebras of the form $\Pi(X)$, where $(X,{\bf T})$ is
$E$-test space.

##  2\. Main Theorems

Theorems 2.7 and 2.11 are the main theorems which one need to prove. In order
to do this we need the following three technical lemmas:

######  Lemma 2.1.

Let $(X,\bf T)$ be an algebraic $E$-test space. Let $f,g\in{\bf E}(X,{\bf T})$
then $\pi(f)=\pi(g)\iff\exists{t_{1},t_{2}\in{\bf T}}f\leq t_{1}\land g\leq
t_{2}\land t_{1}-f=t_{2}-g$.

###### Proof.

Let $(X,\bf T)$ be an algebraic $E$-test space and $f,g\in{\bf E}(X,{\bf T})$.

Assume that there exist $t_{1},t_{2}\in{\bf T}$ such that $f\leq t_{1}$,
$g\leq t_{2}$ and $t_{1}-f=t_{2}-g$. Let $h=t_{1}-f=t_{2}-g\in{\bf E}(X,{\bf
T})$ then $f+h=t_{1}\in{\bf T}$ and $g+h=t_{2}\in{\bf T}$ so $f\approx_{h}g$
and $\pi(f)=\pi(g)$.

Assume that $\pi(f)=\pi(g)$ then there exists $h\in{\bf E}(X,{\bf T})$ such
that $f\approx_{h}g$. It follows that $t_{1}=f+h\in{\bf T}$ and
$t_{2}=g+h\in{\bf T}$. Then $f\leq t_{1}$, $g\leq t_{2}$ and
$t_{1}-f=h=t_{2}-g$. ∎

######  Lemma 2.2.

Let $(X,\bf T)$ be an algebraic $E$-test space. Let $f,g\in{\bf E}(X,{\bf T})$
then $\pi(f)\leq\pi(g)\iff\exists{h\in{\bf E}(X,{\bf T})}$ $\pi(h)=\pi(g)\land
f\leq h$.

###### Proof.

Let $(X,\bf T)$ be an algebraic $E$-test space. Let $f,g\in{\bf E}(X,{\bf T})$
.

Let $\pi(f)\leq\pi(g)$ than there exists $i\in{\bf E}(X,{\bf T})$ such that
$f\perp i$ and $\pi(f)\oplus\pi(i)=\pi(g)$ so $\pi(f+i)=\pi(g)$. Let
$h=f+i\in{\bf E}(X,{\bf T})$. Then $f\leq h$ and $\pi(h)=\pi(f+i)=\pi(g)$.

Assume that there exists $h\in{\bf E}(X,{\bf T})$ such that $\pi(h)=\pi(g)$
and $f\leq h$. Let $i=h-f\in{\bf E}(X,{\bf T})$. Then $h=f+i$ and
$\pi(f)\oplus\pi(i)=\pi(f+i)=\pi(h)$ so $\pi(f)\leq\pi(h)=\pi(g)$. ∎

The above Lemma implies that if $f,g\in{\bf E}(X,{\bf T})$ and $f\leq g$ (i.e.
$f(x)\leq g(x)$ for all $x\in X$) then $\pi(f)\leq\pi(g)$.

######  Lemma 2.3.

Let $(X,\bf T)$ be an algebraic $E$-test space. Let $f,g\in{\bf E}(X,{\bf T})$
then $\pi(f)\leq\pi(g)\iff\exists_{t_{1},t_{2}\in{\bf T}}\;g\leq t_{2}\land
f\leq(t_{1}+g)-t_{2}$

###### Proof.

Let $f,g\in{\bf E}(X,{\bf T})$ and $\pi(f)\leq\pi(g)$. By Lemma 2.2 there
exists $h\in{\bf E}(X,{\bf T})$ such that $\pi(h)=\pi(g)$ and $f\leq h$. Then
there exist $t_{1},t_{2}\in{\bf T}$ such that $h\leq t_{1}$, $g\leq t_{2}$ and
$t_{1}-h=t_{2}-g$ by Lemma 2.1. Hence $f\leq h=(t_{1}+g)-t_{2}$.

Now let $f,g\in{\bf E}(X,{\bf T})$ and assume that there exist
$t_{1},t_{2}\in{\bf T}$ such that $g\leq t_{2}$ and $f\leq(t_{1}+g)-t_{2}$.
Let $h=(t_{1}+g)-t_{2}$. Then $h=(t_{1}+g)-t_{2}\leq t_{1}+t_{2}-t_{2}=t_{1}$
so $h\in{\bf E}(X,{\bf T})$. Moreover $\pi(h)=\pi(g)$ by Lemma 2.1 since
$h\leq t_{1}$, $g\leq t_{2}$ and $t_{1}-h=t_{1}-((t_{1}+g)-t_{2})=t_{2}-g$.
Hence $\pi(f)\leq\pi(g)$ by Lemma 2.2 since $\pi(h)=\pi(g)$ and
$f\leq(t_{1}+g)-t_{2}=h$ which ends the proof.

∎

######  Definition 2.4.

Let $(X,\bf T)$ be an algebraic $E$-test space. Let $f,g\in{\bf E}(X,{\bf T})$
then

$ub(f,g)=\\{(f_{1},f_{2},f_{3},f_{4})\in{\bf T}^{4}\colon f\leq f_{1},g\leq
f_{3},f-f_{1}+f_{2}\leq f_{4},g-f_{3}+f_{4}\leq f_{2}\\}$

The set $ub(f,g)$ is non-empty since there exist $t_{1},t_{2}\in{\bf T}$ such
that $f\leq t_{1}$ and $g\leq t_{2}$ and then $(t_{1},t_{1},t_{2},t_{1})\in
ub(f,g)$.

######  Lemma 2.5.

Let ${\bf E}(X,{\bf T})$ be an algebraic $E$-test space and $f,g\in{\bf
E}(X,{\bf T})$. For every $(f_{1},f_{2},f_{3},f_{4})\in ub(f,g)$ we have

  1. (1)

$i=\max(f-f_{1}+f_{2},g-f_{3}+f_{4},f_{0})\in{\bf E}(X,{\bf T})$

  2. (2)

$\pi(f)\leq\pi(i)$ and $\pi(g)\leq\pi(i)$

On the other hand if $h\in{\bf E}(X,{\bf T})$, $\pi(f)\leq\pi(h)$ and
$\pi(g)\leq\pi(h)$ then there exists $(f_{1}.f_{2},f_{3},f_{4})\in ub(f,g)$
such that $i=\max(f-f_{1}+f_{2},g-f_{3}+f_{4},f_{0})\leq h$.

###### Proof.

Let $f,g\in{\bf E}(X,{\bf T})$ and $(f_{1},f_{2},f_{3},f_{4})\in ub(f,g)$. Let
$i\in{\mathbb{N}}_{0}^{X}$ be a function such that

$i(x)=\max(f(x)-f_{1}(x)+f_{2}(x),g(x)-f_{3}(x)+f_{4}(x),0)$

for every $x\in X$. Then

$None$ $f-f_{1}+f_{2}\leq i$

and

$None$ $g-f_{3}+f_{4}\leq i$

We have $f(x)-f_{1}(x)+f_{2}(x)\leq f_{1}(x)-f_{1}(x)+f_{2}(x)=f_{2}(x)$ and
$g(x)-f_{3}(x)+f_{4}(x)\leq f_{2}(x)$ since $(f_{1},f_{2},f_{3},f_{4})\in
ub(f,g)$. Thus $0\leq i(x)\leq f_{2}(x)$ for every $x\in X$.

Hence $i\leq f_{2}\in{\bf T}$ so $i\in{\bf E}(X,{\bf T})$ and
$\pi(f)\leq\pi(i)$ by Lemma 2.3 since $i\leq f_{2}$ and $f\leq f_{1}+i-f_{2}$
by $(1)$. Since $(f_{1},f_{2},f_{3},f_{4})\in ub(f,g)$ therefore
$f-f_{1}+f_{2}\leq f_{4}$ and $g-f_{3}+f_{4}\leq f_{3}-f_{3}+f_{4}=f_{4}$ thus
$i\leq f_{4}$ and $g-f_{3}+f_{4}\leq i$ by $(2)$ so $g\leq(f_{3}+i)-f_{4}$ and
$\pi(g)\leq\pi(i)$ by Lemma 2.3. Therefore $\pi(i)$ is an upper bound of
$\pi(f)$ and $\pi(g)$.

Now assume that $h\in{\bf E}(X,{\bf T})$, $\pi(f)\leq\pi(h)$ and
$\pi(g)\leq\pi(h)$. By Lemma 2.3 there exist $f_{1},f_{2},f_{3},f_{4}\in{\bf
T}$ such that

$None$ $h\leq f_{2},f\leq(f_{1}+h)-f_{2},h\leq f_{4},g\leq(f_{3}+h)-f_{4}.$

Hence $f\leq f_{1}-f_{2}+h\leq f_{1}-f_{2}+f_{2}=f_{1}$, $g\leq
f_{3}-f_{4}+h\leq f_{3}-f_{4}+f_{4}=f_{3}$ and $f-f_{1}+f_{2}\leq h\leq
f_{4}$, $g-f_{3}+f_{4}\leq h\leq f_{2}$ so $(f_{1},f_{2},f_{3},f_{4})\in
ub(f,g)$. Let $i\in{\mathbb{N}}_{0}^{X}$ be a function such that

$i(x)=\max(f(x)-f_{1}(x)+f_{2}(x),g(x)-f_{3}(x)+f_{4}(x),0)$

for every $x\in X$. Moreover $f-f_{1}+f_{2}\leq h$ and $g-f_{3}+f_{4}\leq h$
by (3). Hence by the definition of $i$ we have $i\leq h$. ∎

There is some connections between upper bounds of $\pi(f)$ and $\pi(g)$ and
the set $ub(f,g)$. By lemma 2.5 we can assign upper bound in the form
$\pi(\max(f-f_{1}+f_{2},g-f_{3}+f_{4},f_{0}))$ of $\pi(f)$ and $\pi(g)$ to
every $(f_{1},f_{2},f_{3},f_{4})\in ub(f,g)$. On the other hand one can assign
$(f_{1},f_{2},f_{3},f_{4})\in ub(f,g)$ to every upper bound of $\pi(f)$ and
$\pi(g)$

######  Definition 2.6.

Let $(X,\bf T)$ be an algebraic $E$-test space. Let $f,g\in{\bf E}(X,{\bf T})$
then $f,g$ satisfy J-condition for $(f_{1},f_{2},f_{3},f_{4})\in{\bf T}^{4}$
if and only if

  1. (J1)

$f\leq f_{1},\quad g\leq f_{3},\quad f-f_{1}+f_{2}\leq f_{4},\quad
g-f_{3}+f_{4}\leq f_{2}$

and

  2. (J2)

for every $g_{1},g_{2},g_{3},g_{4}\in{\bf T}$ such that
$(g_{1},g_{2},g_{3},g_{4})\in ub(f,g)$ i.e.

$f\leq g_{1},\quad g\leq g_{3},\quad f-g_{1}+g_{2}\leq g_{4},\quad
g-g_{3}+g_{4}\leq g_{2}$

we have

$\pi(\max(f-f_{1}+f_{2},g-f_{3}+f_{4},f_{0}))\leq\pi(\max(f-g_{1}+g_{2},g-g_{3}+g_{4},f_{0})).$

######  Theorem 2.7.

Let ${\bf E}(X,{\bf T})$ be an algebraic $E$-test space and $f,g\in{\bf
E}(X,{\bf T})$ then $\pi(f)\lor\pi(g)$ exists in $\Pi(X)$ if and only if there
exist $f_{1},f_{2},f_{3},f_{4}\in{\bf T}$ such that $f,g$ satisfy J-condition
for $(f_{1},f_{2},f_{3},f_{4})\in{\bf T}^{4}$. Moreover if $f,g$ satisfy
J-condition for $(f_{1},f_{2},f_{3},f_{4})\in ub(f,g)$. then

$\pi(f)\lor\pi(g)=\pi(h),$

where $h(x)=\max(f(x)-f_{1}(x)+f_{2}(x),g(x)-f_{3}(x)+f_{4}(x),0)$ for every
$x\in X$.

###### Proof.

  1. $\Rightarrow$

Let $f,g\in{\bf E}(X,{\bf T})$ and $\pi(f)\lor\pi(g)=\pi(h)$ for some
$h\in{\bf E}(X,{\bf T})$. Then $\pi(f)\leq\pi(h)$ and $\pi(g)\leq\pi(h)$. By
Lemma 2.5 there exists $(f_{1}.f_{2},f_{3},f_{4})\in ub(f,g)$ such that

$i_{1}=\max(f-f_{1}+f_{2},g-f_{3}+f_{4},f_{0})\leq h.$

We show that $f,g$ satisfy J-condition for $(f_{1},f_{2},f_{3},f_{4})\in{\bf
T}^{4}$.

We know that $(f_{1}.f_{2},f_{3},f_{4})\in ub(f,g)$ so

$f\leq f_{1},g\leq f_{3},f-f_{1}+f_{2}\leq f_{4},g-f_{3}+f_{4}\leq f_{2}$

and (J1) is fulfilled.

Now we show that $(J2)$ is also satisfied.

Assume that there exist $g_{1},g_{2},g_{3},g_{4}\in{\bf T}$ such that

$f\leq g_{1},g\leq g_{3},f-g_{1}+g_{2}\leq g_{4},g-g_{3}+g_{4}\leq g_{2}$

so $(g_{1}.g_{2},g_{3},g_{4})\in ub(f,g)$.

Let $i_{2}\in{\mathbb{N}}_{0}^{X}$ be a function such that

$i_{2}(x)=\max(f(x)-g_{1}(x)+g_{2}(x),g(x)-g_{3}(x)+g_{4}(x),0)$

for every $x\in X$. Then

    1. (a)

$i_{2}=\max(f-g_{1}+g_{2},g-g_{3}+g_{4},f_{0})\in{\bf E}(X,{\bf T})$,

    2. (b)

$\pi(f)\leq\pi(i_{2})$ and $\pi(g)\leq\pi(i_{2})$

by Lemma 2.5.

Therefore $\pi(i_{2})$ is an upper bound of $\pi(f)$ and $\pi(g)$. We know
that $\pi(h)$ is a join of $\pi(f)$ and $\pi(g)$ so $\pi(h)\leq\pi(i_{2})$. By
Lemma 2.2 we know that $\pi(i_{1})\leq\pi(h)$ since $i_{1}\leq h$. Thus
$\pi(i_{1})\leq\pi(i_{2})$ i.e.

$\pi(\max(f-f_{1}+f_{2},g-f_{3}+f_{4},f_{0}))\leq\pi(\max(f-g_{1}+g_{2},g-g_{3}+g_{4},f_{0}))$

so $f,g$ satisfy $J$-condition for $(f_{1},f_{2},f_{3},f_{4})\in{\bf T}^{4}$.

  2. $\Leftarrow$

Assume that $f,g$ satisfy J-condition for $(f_{1},f_{2},f_{3},f_{4})\in{\bf
T}^{4}$. Let

$i_{1}=\max(f-f_{1}+f_{2},g-f_{3}+f_{4},f_{0}).$

We show that $i_{1}\in{\bf E}(X,{\bf T})$ and $\pi(f)\lor\pi(g)=\pi(i_{1})$.

By (J1) we have

$f\leq f_{1},g\leq f_{3},f-f_{1}+f_{2}\leq f_{4},g-f_{3}+f_{4}\leq f_{2}$

so $(f_{1},f_{2},f_{3},f_{4})\in ub(f,g)$ and by Lemma 2.5 we have

    1. (a)

$i_{1}\in{\bf E}(X,{\bf T})$,

    2. (b)

$\pi(f)\leq\pi(i_{1})$ and $\pi(g)\leq\pi(i_{1})$.

Therefore $\pi(i_{1})$ is an upper bound of $\pi(f)$ and $\pi(g)$.

Assume that $h\in{\bf E}(X,{\bf T})$, $\pi(f)\leq\pi(h)$ and
$\pi(g)\leq\pi(h)$. By lemma 2.5 there exist $(g_{1},g_{2},g_{3},g_{4})\in
ub(f,g)$ such that

$i_{2}=\max(f-g_{1}+g_{2},g-g_{3}+g_{4},f_{0})\leq h.$

Hence $\pi(i_{2})\leq\pi(h)$ by Lemma 2.2.

By (J2) we have

$\pi(\max(f-f_{1}+f_{2},g-f_{3}+f_{4},f_{0}))\leq\pi(\max(f-g_{1}+g_{2},g-g_{3}+g_{4},f_{0}))$

so $\pi(i_{1})\leq\pi(i_{2})$.

Hence $\pi(i_{1})\leq\pi(i_{2})\leq\pi(h)$ so $\pi(i_{1})\leq\pi(h)$.
Therefore

$\pi(i_{1})=\pi(\max(f-f_{1}+f_{2},g-f_{3}+f_{4},f_{0}))=\pi(f)\lor\pi(g).$

∎

Now we deal with the meets in effect algebras.

######  Definition 2.8.

Let $(X,\bf T)$ be an algebraic $E$-test space. Let $f,g\in{\bf E}(X,{\bf T})$
then

$lb(f,g)=\\{(f_{1},f_{2},f_{3},f_{4})\in{\bf T}^{4}\colon f\leq f_{2},g\leq
f_{4},f-f_{2}+f_{1}\geq f_{0},g-f_{4}+f_{3}\geq f_{0}\\}$

The set $lb(f,g)$ is non-empty since there exist $t_{1},t_{2}\in{\bf T}$ such
that $f\leq t_{1}$ and $g\leq t_{2}$ and then $(t_{1},t_{1},t_{2},t_{2})\in
lb(f,g)$.

######  Lemma 2.9.

Let ${\bf E}(X,{\bf T})$ be an algebraic $E$-test space and $f,g\in{\bf
E}(X,{\bf T})$. For every $(f_{1},f_{2},f_{3},f_{4})\in lb(f,g)$ we have

  1. (1)

$i=\min(f-f_{2}+f_{1},g-f_{4}+f_{3})\in{\bf E}(X,{\bf T})$

  2. (2)

$\pi(f)\geq\pi(i)$ and $\pi(g)\geq\pi(i)$

On the other hand if $h\in{\bf E}(X,{\bf T})$, $\pi(f)\geq\pi(h)$ and
$\pi(g)\geq\pi(h)$ then there exists $(f_{1}.f_{2},f_{3},f_{4})\in lb(f,g)$
such that $i=\min(f-f_{2}+f_{1},g-f_{4}+f_{3},)\geq h$.

###### Proof.

Let $f,g\in{\bf E}(X,{\bf T})$ and $(f_{1},f_{2},f_{3},f_{4})\in lb(f,g)$. Let
$i\in{\mathbb{N}}_{0}^{X}$ be a function such that

$i(x)=\min(f(x)-f_{2}(x)+f_{1}(x),g(x)-f_{4}(x)+f_{3}(x))$

for every $x\in X$. Then $i\leq f-f_{2}+f_{1}\leq f_{1}\in{\bf T}$ since
$f\leq f_{2}$. Moreover $f-f_{2}+f_{1}\geq f_{0}$, $g-f_{4}+f_{3}\geq f_{0}$
since $(f_{1},f_{2},f_{3},f_{4})\in lb(f,g)$ so $i\geq f_{0}$ and $i\in{\bf
E}(X,{\bf T})$.

By the definition of $i$ we have $i\leq f-f_{2}+f_{1}$ and $i\leq
g-f_{4}+f_{3}$. Moreover $f\leq f_{2}$ and $g\leq f_{4}$ since
$(f_{1},f_{2},f_{3},f_{4})\in lb(f,g)$. Thus $\pi(i)\leq\pi(f)$ and
$\pi(i)\leq\pi(g)$ by Lemma 2.3.

Now assume that $h\in{\bf E}(X,{\bf T})$, $\pi(f)\geq\pi(h)$ and
$\pi(g)\geq\pi(h)$. By Lemma 2.3 there exist $f_{1},f_{2},f_{3},f_{4}\in{\bf
T}$ such that

$f\leq f_{2},h\leq(f_{1}+f)-f_{2},g\leq f_{4},h\leq(f_{3}+g)-f_{4}$

so

$f\leq f_{2},g\leq f_{4},f-f_{2}+f_{1}\geq f_{0},g-f_{4}+f_{3}\geq f_{0}$

and $(f_{1},f_{2},f_{3},f_{4})\in lb(f,g)$.

We know that $h\leq(f_{1}+f)-f_{2}$ and $h\leq(f_{3}+g)-f_{4}$ so $h\leq
i=\min(f-f_{2}+f_{1},g-f_{4}+f_{3})$. ∎

######  Definition 2.10.

Let $(X,\bf T)$ be an algebraic $E$-test space. Let $f,g\in{\bf E}(X,{\bf T})$
then $f,g$ satisfy M-condition for $(f_{1},f_{2},f_{3},f_{4})\in{\bf T}^{4}$
if and only if

  1. (M1)

$f\leq f_{2},\quad g\leq f_{4},\quad f-f_{2}+f_{1}\geq f_{0},\quad
g-f_{4}+f_{3}\geq f_{0}$

and

  2. (M2)

for every $g_{1},g_{2},g_{3},g_{4}\in{\bf T}$ such that
$(g_{1},g_{2},g_{3},g_{4})\in lb(f,g)$ i.e.

$f\leq g_{2},\quad g\leq g_{4},\quad f-g_{2}+g_{1}\geq f_{0},\quad
g-g_{4}+g_{3}\geq f_{0}$

we have

$\pi(\min(f-f_{2}+f_{1},g-f_{4}+f_{3}))\geq\pi(\min(f-g_{1}+g_{2},g-g_{3}+g_{4})).$

######  Theorem 2.11.

Let ${\bf E}(X,{\bf T})$ be an algebraic $E$-test space and $f,g\in{\bf
E}(X,{\bf T})$ then $\pi(f)\land\pi(g)$ exists in $\Pi(X)$ if and only if
there exist $f_{1},f_{2},f_{3},f_{4}\in{\bf T}$ such that $f,g$ satisfy
M-condition for $(f_{1},f_{2},f_{3},f_{4})\in{\bf T}$. Moreover if $f,g$
satisfy M-condition for $(f_{1},f_{2},f_{3},f_{4})\in lb(f,g)$ then

$\pi(f)\land\pi(g)=\pi(h),$

where $h(x)=\min(f(x)-f_{2}(x)+f_{1}(x),g(x)-f_{4}(x)+f_{3}(x))$ for every
$x\in X$.

###### Proof.

  1. $\Rightarrow$

Let $f,g\in{\bf E}(X,{\bf T})$ and $\pi(f)\land\pi(g)=\pi(h)$ for some
$h\in{\bf E}(X,{\bf T})$. Then $\pi(f)\geq\pi(h)$ and $\pi(g)\geq\pi(h)$ so by
Lemma 2.9 there exists $(f_{1}.f_{2},f_{3},f_{4})\in lb(f,g)$ such that

$i_{1}=\min(f-f_{2}+f_{1},g-f_{4}+f_{3},)\geq h.$

We show that $f,g$ satisfy M-condition for $(f_{1},f_{2},f_{3},f_{4})\in{\bf
T}^{4}$.

We know that $(f_{1},f_{2},f_{3},f_{4})\in lb(f,g)$ so

$f\leq f_{2},g\leq f_{4},f-f_{2}+f_{1}\geq f_{0},g-f_{4}+f_{3}\geq f_{0}$

and (M1) is satisfied.

Now we show that (M2) is also satisfied.

Assume that there exist $g_{1},g_{2},g_{3},g_{4}\in{\bf T}$ such that

$f\leq g_{2},f_{0}\leq f+g_{1}-g_{2},g\leq g_{4},f_{0}\leq g+g_{3}-g_{4}.$

so $(g_{1},g_{2},g_{3},g_{4})\in lb(f,g)$.

Let $i_{2}\in{\mathbb{N}}_{0}^{X}$ be a function such that

$i_{2}(x)=\min(f(x)+g_{1}(x)-g_{2}(x),g(x)+g_{3}(x)-g_{4}(x))$

for every $x\in X$. Then

    1. (a)

$i_{2}=\min(f-g_{2}+g_{1},g-g_{4}+g_{3})\in{\bf E}(X,{\bf T})$

    2. (b)

$\pi(f)\geq\pi(i_{2})$ and $\pi(g)\geq\pi(i_{2})$

by Lemma 2.9.

Therefore $\pi(i_{2})$ is a lower bound of $\pi(f)$ and $\pi(g)$. We know that
$\pi(h)$ is a meet of $\pi(f)$ and $\pi(g)$ so $\pi(i_{2})\leq\pi(h)$. By
Lemma 2.2 we know that $\pi(i_{1})\geq\pi(h)$ since $i_{1}\geq h$. Thus
$\pi(i_{2})\leq\pi(i_{1})$ i.e.

$\pi(\min(f-f_{2}+f_{1},g-f_{4}+f_{3}))\geq\pi(\min(f-g_{1}+g_{2},g-g_{3}+g_{4})).$

so $f,g$ satisfies M-condition for $(f_{1},f_{2},f_{3},f_{4})\in{\bf T}^{4}$.

  2. $\Leftarrow$

Assume that $f,g$ satisfy M-condition for $(f_{1},f_{2},f_{3},f_{4})\in{\bf
T}^{4}$. Let

$i_{1}=\min(f+f_{1}-f_{2},g+f_{3}-f_{4}).$

We show that $i_{1}\in{\bf E}(X,{\bf T})$ and $\pi(f)\land\pi(g)=\pi(i_{1})$.

By (M1) we have

$f\leq f_{2},\quad g\leq f_{4},\quad f-f_{2}+f_{1}\geq f_{0},\quad
g-f_{4}+f_{3}\geq f_{0}$

so $(f_{1},f_{2},f_{3},f_{4})\in lb(f,g)$ and by Lemma 2.9 we have

    1. (a)

$i_{1}=\min(f-f_{2}+f_{1},g-f_{4}+f_{3})\in{\bf E}(X,{\bf T})$

    2. (b)

$\pi(f)\geq\pi(i_{1})$ and $\pi(g)\geq\pi(i_{1})$

Therefore $\pi(i_{1})$ is an lower bound of $\pi(f)$ and $\pi(g)$.

Assume that $h\in{\bf E}(X,{\bf T})$, $\pi(h)\leq\pi(f)$ and
$\pi(h)\leq\pi(g)$. By lemma 2.9 there exists $(g_{1},g_{2},g_{3},g_{4})\in
lb(f,g)$ such that

$i_{2}=\min(f-g_{1}+g_{2},g-g_{3}+g_{4})\geq h.$

Hence $\pi(i_{2})\geq\pi(h)$ by Lemma 2.2.

By (M2) we have

$\pi(\min(f-f_{2}+f_{1},g-f_{4}+f_{3}))\geq\pi(\min(f-g_{1}+g_{2},g-g_{3}+g_{4})).$

so $\pi(i_{1})\geq\pi(i_{2})$.

Hence $\pi(i_{1})\geq\pi(i_{2})\geq\pi(h)$ so $\pi(i_{1})\geq\pi(h)$.
Therefore

$\pi(i_{1})=\pi(\min(f+f_{1}-f_{2},g+f_{3}-f_{4})=\pi(f)\land\pi(g).$

∎

In [7], a new class of effect algebras, callled homogeneous effect algebras
was introduced.

######  Definition 2.12.

An effect algebra is homogeneous if and only if, for all $u,u_{1},u_{2}$ such
that $u\leq u_{1}\oplus u_{2}\leq u^{\prime}$ there are $v_{1},v_{2}$ such
that $u=v_{1}\oplus v_{2}$, $v_{1}\leq u_{1}$ and $v_{2}\leq u_{2}$.

The following Proposition gives the simple way to check when a finite effect
algebra $E$ is homogeneous.

######  Proposition 2.13.

[8, Proposition 3.1] For every finite effect algebra $E$, the following are
equivalent:

  1. (a)

$E$ is homogeneous.

  2. (b)

Let $u,f$ be a pair of atomic events such that $\bigoplus u\leq\bigoplus
f\leq(\bigoplus u)^{\prime}$. Then $u\leq f$.

  3. (c)

For every atom $a$ and for every atomic event $f$ such that $a\leq\bigoplus
f\leq a^{\prime}$, $a\in{\rm supp}(f)$

  4. (d)

Let $f,g$ be atomic tests, let $a\in{\rm supp}(f)\cap{\rm supp}(g)$. Then
$f(a)=g(a)$.

  5. (e)

For every atom $a$ and every atomic event $f$ such that $a\in{\rm supp}(f)$,
$f(a)=$ı$(a)$.

Next Corollary gives the description of sharp elements in a homogeneous finite
effect algebra $E$.

######  Corollary 2.14.

[8, Corollary 3.2] Let $E$ be a homogeneous effect algebra, let $w$ be an
atomic event of $E$ such that $\bigoplus w\in E_{S}$. For every $a\in{\rm
supp}(w)$, $w(a)=$ı$(a)$.

It is easy to check that for finite homogeneous effect algebra $E$ and an
atomic event $w$ of $E$ we have: $\bigoplus w\in E_{S}\iff$ for every
$a\in{\rm supp}(w)$, $w(a)=$ı$(a)$.

In [10] G.Jenča posed the following problem: if $E$ is an orthocomplete
homogeneous effect algebra $E$ such that $S(E)$ is a lattice, then $E$ is a
lattice effect algebra. In [11] Wei Ji gives an affirmative answer to this
problem.

Using Theorem 2.7, Corollary 2.14 and Proposition 2.13 we created the
algorithm checking if $E$ and $E_{S}$ are lattices. The following example of
finite, not homogeneous effect algebra $E$ such that $E_{S}$ is a lattice and
$E$ is not a lattice was generated by computer making use of this algorithm.

######  Example 2.15.

Let $E$ be an effect algebra with the atomic test space given by the following
table

$\begin{array}[]{|c|c|c|}\hline\cr a&b&c\\\ \hline\cr 2&2&0\\\ \hline\cr
1&0&2\\\ \hline\cr\end{array}$

So in $E$ there are $3$ atoms $a,b,c$ and two atomic tests $t_{1},t_{2}\colon
E\setminus\\{0\\}\to{\mathbb{N}}_{0}$ such that $t_{1}(a)=t_{1}(b)=2$,
$t_{1}(c)=0$ and $t_{2}(a)=1$, $t_{2}(b)=0$, $t_{2}(c)=2$.

Then $E$ is not homogeneous by Theorem 2.13 since $t_{2}(a)=1\not=2=$ı$(a)$.

Moreover $E_{S}=\\{1,0,2a,2b\\}$. Of course, $E_{S}$ is a $4$-element lattice
but $E$ is not a lattice since $a\lor c$ does not exist due to the fact that
the set of upper bounds of $\\{a,c\\}$ consists of $1$, $a\oplus c$ and $2c$
so it does not have a smallest element.

The effect algebra $E$ is represented by the following Hasse diagram:

$\textstyle{2a\oplus 2b=a\oplus
2c=1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2a\oplus
b\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a\oplus
2b=2c\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2a\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a\oplus
b\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2b\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a\oplus
c\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{b\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{c\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$

## References

  * [1] Bush P., Lahti P.J., Mittelstadt P. The Quantum Theory of Measurement Lecture Notes in Phys. New Ser. m2, Springer-Verlag, Berlin, 1991
  * [2] Bush P., Grabowski M., Lahti P.J Operational Quantum Physics, Springer-Verlag, Berlin, 1995
  * [3] Dvurečenskij A., Pulmannová S. New Trends in Quantum Structures, Kluwer Academic Publ./Ister Science, Dordrecht-Boston-London/Bratislava, 2000.
  * [4] Foulis D. J., Bennett M. K. Effect Algebras and Unsharp quantum Logics, Foundations of Physics. 24, No. 10, 1994, 1331-1351.
  * [5] Giuntini R., Grueuling H., Toward a formal language for unsharp properties, Found. Phys, 19, 1994, 769-780.
  * [6] Gudder S. Effect test spaces and effect algebras, Foundations of Physics, 27 (2),1997, 287-304.
  * [7] G. Jenča, Blocks of homogeneous effect algebras, Bull. Austal. Math. Soc., 64, 2001, 81-98.
  * [8] Gejza Jenča, Finite homogeneous and lattice ordered effect algebras, 272 (2-3), 2003, 197214
  * [9] Kôpka F., Chovanec F., $D$-posets, Math. Slovaca, 44, 1994, 21-34.
  * [10] Mesiar R., Stupňanová A., Open problems from the 12th International Conference on Fuzzy Set Theory and Its Applications, Fuzzy Sets and Systems, 261, 112-123, 2015
  * [11] Wei Ji ,Meager projections in orthocomplete homogeneous effect algebras, Fuzzy Sets and Systems,339, 2018, 51-61


11institutetext: University of Maryland, College Park MD, USA
11email: {tbrolin<EMAIL_ADDRESS>22institutetext: Laboratory for Physical
Sciences, College Park MD, USA
22email<EMAIL_ADDRESS>
✉ Corresponding author: 22email<EMAIL_ADDRESS>
# Compiler Optimization for Irregular Memory Access Patterns in PGAS Programs

Thomas B. Rolinger 1122 Christopher D. Krieger 22 Alan Sussman 11

###### Abstract

Irregular memory access patterns pose performance and user productivity
challenges on distributed-memory systems. They can lead to fine-grained remote
communication and the data access patterns are often not known until runtime.
The Partitioned Global Address Space (PGAS) programming model addresses these
challenges by providing users with a view of a distributed-memory system that
resembles a single shared address space. However, this view often leads
programmers to write code that causes fine-grained remote communication, which
can result in poor performance. Prior work has shown that the performance of
irregular applications written in Chapel, a high-level PGAS language, can be
improved by manually applying optimizations. However, applying such
optimizations by hand reduces the productivity advantages provided by Chapel
and the PGAS model. We present an inspector-executor based compiler
optimization for Chapel programs that automatically performs remote data
replication. While there have been similar compiler optimizations implemented
for other PGAS languages, high-level features in Chapel such as implicit
processor affinity lead to new challenges for compiler optimization. We
evaluate the performance of our optimization across two irregular
applications. Our results show that the total runtime can be improved by as
much as 52x on a Cray XC system with a low-latency interconnect and 364x on a
standard Linux cluster with an Infiniband interconnect, demonstrating that
significant performance gains can be achieved without sacrificing user
productivity.

###### Keywords:

PGAS, Chapel, irregular applications, compiler optimizations

##  1 Introduction

Implementing parallel software that can effectively utilize distributed-memory
systems poses many challenges for programmers. Specifically, modifying an
existing serial or shared-memory parallelized application to run in a
distributed setting often requires significant programmer effort to
orchestrate data distribution and communication. The Partitioned Global
Address Space (PGAS) model attempts to address these challenges by providing
programmers with a view of a distributed-memory system that resembles a single
shared address space. The PGAS model has been implemented in various languages
and libraries, such as UPC [11], GlobalArrays [14] and Chapel [6]. Within PGAS
languages, details regarding data distribution and communication are often
abstracted from the programmer. For example, in Chapel simply specifying an
array as “distributed” automatically maps the data across the system and
remote communication is performed implicitly. The PGAS model therefore
encourages programmers to write code in a shared-memory manner but aims to
provide good performance on distributed-memory systems without requiring the
program to be rewritten.

Irregular memory access patterns are commonly found in applications that
perform graph analytics [13], sparse linear algebra [20] and scientific
computing operations [10]. Such access patterns pose significant challenges
for user productivity on distributed-memory systems because the access
patterns are not known until runtime, making it difficult to orchestrate
communication amongst remote processes. However, with the PGAS model coding
irregular communication patterns becomes more straightforward, as they can be
implemented via one-sided communication. Unfortunately, the performance of
such codes will be significantly hindered due to the fine-grained remote
communication that arises from the irregular memory accesses. While the
abstractions provided by the PGAS model can be manually bypassed to achieve
better performance, such an effort would significantly degrade user
productivity.

In this paper, we present the design and implementation of a compiler
optimization that automatically applies the _inspector-executor_ technique
[16] to parallel loops in PGAS programs written in the Chapel language. The
inspector performs memory access analysis at runtime to determine remote
communication to an array of interest within a loop. The executor replicates
the remote data and runs the original loop, but redirects remote accesses to
replicated local copies to avoid repeated remote communication. Our compiler
optimization automatically identifies candidate loops and array accesses, and
then performs code transformations to construct the inspector and executor
routines. As a result, the user is not required to change their original code
in order to achieve significant performance gains. The contributions of our
work are as follows:

  * •

Design and implementation of an inspector-executor based compiler optimization
for Chapel programs that specifically targets irregular memory accesses to
distributed arrays. To the best of our knowledge, this work presents the first
such optimization within the Chapel compiler.

  * •

Discussion on the unique features of Chapel, such as implicit processor
affinity, as they relate to the compiler optimization. While the inspector-
executor technique has been employed for a long time [16, 15, 17], and applied
to other PGAS languages [18, 1], our design within Chapel requires a different
approach due to Chapel’s high-level features.

  * •

Performance evaluation of our optimization across two irregular applications
and two different distributed-memory systems. Our results show that the
optimization can improve performance by as much as 52x on a Cray XC system
with a low-latency interconnect and 364x on a standard Linux cluster with an
Infiniband interconnect.

The rest of the paper is organized as follows. Section 2 presents an overview
of Chapel. We present our compiler optimization and discuss its details in
Section 3. Section 4 presents a performance evaluation of the optimization
across two irregular applications, and the Appendix contains additional
performance results. Prior work as it relates to our paper is described in
Section 5. Finally, Section 6 provides concluding remarks and discusses future
work.

##  2 Overview of the Chapel Language

Chapel is a high-level language that implements the PGAS model and is designed
for productive parallel computing at scale, providing constructs for
distributed arrays, remote communication and both data and task parallelism.
In this section we provide a brief overview of Chapel, focusing on the
features most relevant to our work. For a more in-depth description of Chapel,
we refer readers to the work by Chamberlain et al. [6].

###  2.1 Terminology: Tasks, Threads and Locales

Chapel enables parallelism through executing multiple _tasks_ in parallel,
where a task is a set of computations that can conceptually be executed in
parallel, but may or may not do so. Tasks are implemented by a tasking layer,
which provides threads on which Chapel tasks are scheduled. For distributed-
memory programming, Chapel introduces the concept of a _locale_ , which is
defined as a unit of machine resources on which tasks can execute. In
practice, a locale is mapped to an entire compute node in a cluster and the
number of locales on which a program runs is specified when launching the
program. Chapel programs initially start with a single task executing on
locale 0. Parallel loops and other constructs then create tasks that can
execute across the locales, but ultimately join back to a single task on
locale 0 when they are done. This differs from other PGAS languages, such as
UPC [11], which use a single program multiple data (SPMD) model that defines
the amount of parallelism at program startup.

###  2.2 Domains and Arrays

Chapel splits an array into two first-class objects in the language: a
_domain_ and the array itself. A domain is a representation of an index set
and can be used to define the indices in an array or the indices iterated over
by a loop. Once defined, a domain can then be used to declare an array.
Modifications to a domain (e.g., adding/removing indices) propagate to all
arrays defined over the domain. Lines 1–2 in Listing 1 present a simple
example of defining a domain D that has indices 0 through 5 and then declaring
an array of integers, data, over that domain. Of particular relevance to our
work is an _associative_ domain, which is similar to a dictionary. Lines 4–7
in Listing 1 declare an associative domain C that stores strings and adds the
key “foo” via the += operator. The associative array dict is declared over C
and provides a mapping of strings to reals. Associative domains also provide
parallel-safe modifications by default.

⬇ 1var D = {0..5}; // rectangular domain 2var data : [D] int; 3 4var C :
domain(string); // associative domain 5C += "foo"; 6var dict : [C] real;
7dict["foo"] = 2.0; Listing 1: Chapel domains and arrays ⬇ 1var D =
newBlockDom({0..15}); 2var arr : [D] int; 3 4for i in 0..15 { 5 arr[i] =
here.id; 6} Listing 2: Block distributed domain/array in Chapel

The code in Listing 1 only declares domains and arrays that are located on a
single locale. Our work focuses on _distributed arrays_ , whose data is spread
across multiple locales according to some distribution policy. Chapel provides
several built-in distribution policies, such as block, cyclic and block-
cyclic. Listing 2 shows a simple example of declaring a block-distributed
domain and then the corresponding distributed array. The block distribution
will partition the array into contiguous chunks and assign one chunk to each
locale. The underlying distribution implementation automatically handles the
index remapping, allowing users to write arr[i] to access the $i^{th}$ element
of the array, rather than having to specify which block the index is in.
Furthermore, Chapel performs implicit remote communication, which means that
users can access the remote elements of a distributed array in the same way
that they would access the local elements. This can be seen on lines 4–6 in
Listing 2, which sets the value of arr[i] to be equal to the ID of the locale
where the task is executing (here.id). The loop will execute all iterations on
locale 0, so any access to an element of arr that is not on locale 0 will
result in communication.

###  2.3 Forall Loops

Chapel provides data parallelism via a forall loop, which allows the loop
iterations to be parallelized and distributed across the system. How the
iterations are mapped to cores/locales depends on what the forall loop is
iterating over, which is referred to as the _iterand_. Non-distributed arrays
and domains have default _iterators_ defined, which partition the iterations
into contiguous chunks and assign each chunk to a task. The tasks then execute
concurrently on a single locale. For distributed arrays and domains, the
default iterator provides both shared- and distributed-memory parallelism by
executing a given iteration of the loop on the locale where that iteration’s
data element is mapped. Consider the example in Listing 3, which iterates over
the domain of a distributed array arr. This loop is similar to the non-
parallel loop on lines 4–6 in Listing 2, but it will execute the $i^{th}$
iteration on the locale on which arr[i] is stored. Therefore, here.id will
return the locale ID of where arr[i] is located. This avoids the remote
communication that would occur for the code in Listing 2. Therefore the
iterand of a forall loop implicitly controls where the computation is
performed. We refer to this as controlling the forall’s _locale affinity_ and
note that it is a feature of Chapel that differs from the more explicit
affinity-controlling constructs of languages like UPC. Furthermore, users can
define their own custom iterators to alter the way in which a forall loop is
parallelized.

⬇ 1var D = newBlockDom({0..15}); 2var arr : [D] int; 3forall i in arr.domain {
4 arr[i] = here.id; 5} Listing 3: forall loop in Chapel

##  3 Compiler Optimization

In this section we describe the design and implementation of the inspector-
executor compiler optimization for irregular memory accesses. We focus
specifically on read-only accesses with the form A[B[i]] found inside forall
loops, where A and B are arrays and A is a distributed array. However, we do
support more complex non-affine expressions if certain conditions are met (see
Section 3.3). The overall goal of the optimization is to selectively replicate
remotely accessed elements of A so that they can be accessed locally during
execution of the loop. Full replication of A can be prohibitively expensive in
terms of both memory consumption and communication overhead, but knowing which
elements are accessed remotely requires knowledge only revealed when the loop
is executed. This motivates the design of our compiler optimization that
creates an inspector to determine at runtime which accesses are remote.

The optimization targets forall loops that execute multiple times, which
allows for the cost of the inspector phase to be amortized over multiple
executions of the optimized loop (i.e., the executor). Such patterns are
commonly found in sparse iterative solvers [10], molecular dynamics
simulations [17] and some graph analytics applications [5]. Figure 1 presents
a high-level overview of Chapel’s compiler passes, where the shaded passes in
the dotted box correspond to the passes where the optimization performs static
analysis and code transformations. There are roughly 40 passes in Chapel’s
compiler to date, but most are omitted in Figure 1 to simplify the diagram.

Figure 1: High-level overview of the Chapel compiler. The shaded passes within
the dotted box represent those where our optimization performs code
transformations and static analysis.

###  3.1 High-level Overview

Our optimization operates solely on Chapel’s intermediate representation of
the program, which we refer to as the abstract syntax tree (AST). The
optimization process begins during the normalize pass, at which point the AST
has not been heavily modified, thus making the code transformation tasks
easier to perform. The optimization considers each forall loop that is present
in the program and looks for accesses of the form A[B[i]]. However, array
accesses do not have their own syntax in the AST, meaning that A[B[i]] is
represented as a call expression that is indistinguishable from a function
call. To address this issue, an irregular access candidate expression is
replaced with a compiler primitive that will be acted on during the resolve
pass, at which point the optimization can determine whether A and B are
arrays. If a forall loop has a candidate access, the optimization clones the
forall into the inspector and executor loops.

During the resolve pass of compilation, function calls and types are resolved,
which allows the optimization to carry out much of the necessary static
analysis to ensure the validity of the code transformations performed during
the normalize pass. If anything is found to invalidate the optimization then
the code transformations are removed and replaced with the original forall
loop. Otherwise, the primitive that represents A[B[i]] is replaced with a
library call to either “inspect” or “execute” the access, depending on whether
the primitive is in the inspector or executor loop. Determining which accesses
are remote is performed at runtime via the inspector. The static analysis
performed by the optimization only determines that the access is of the form
A[B[i]] and that A is a distributed array.

Finally, at the end of the cull-over references pass, the optimization
performs the remaining analysis necessary to ensure the transformations are
valid, which focuses on locating modifications (writes) to the relevant arrays
and domains for the irregular accesses in the loop. Such writes can change the
A[B[i]] access pattern, which would require the inspector runtime analysis to
be rerun to ensure that the executor has the correct elements replicated. The
cull-over references pass resolves the _intents_ of function arguments, where
an argument’s intent refers to whether it is passed by value or reference.
This pass statically sets the intent of the argument to different values
depending on whether the procedure reads or writes to the argument. Writes to
arrays are performed via Chapel procedure calls where the array is passed in
as an argument, which allows the optimization to check the intent of the array
to determine whether it is written to.

###  3.2 Code Transformations

Listing 5 presents code that is functionally equivalent to the output from our
optimization’s AST-level transformations when applied to the program in
Listing 4. We next describe the details of the code transformations and how
they support selective data replication.

⬇ 1forall i in B.domain { 2 C[i] = A[B[i]]; 3} Listing 4: Example forall loop
with an irregular memory access pattern ⬇ 1if doInspector(A, B) { 2
inspectorPreamble(A); 3 forall i in inspectorIterator(B.domain) { 4
inspectAccess(A, B[i]); 5 } 6 inspectorOff(A,B); 7} 8executorPreamble(A);
9forall i in B.domain { 10 C[i] = executeAccess(A, B[i]); 11} Listing 5:
Output of code transformations performed by the optimization for the code in
Listing 4

Internal Chapel Data Structures: For a distributed array A in a forall loop
that is being optimized, we add a Chapel record (i.e., C struct) for each
locale that contains the remote communication information about A[B[i]] on
that locale. We refer to the complete set of these records as a _communication
schedule_. A communication schedule is essentially a set of associative arrays
that map B[i] to A[B[i]] when A[B[i]] is a remote access issued from a given
locale. If A is associated with multiple forall loops that are being
optimized, the optimization will create different communication schedules for
A that are linked to each forall loop.

Inspector Loop: The compiler optimization starts by cloning the original
forall loop into two copies, one that will be transformed into the inspector
and one that will be transformed into the executor. For the inspector loop
(lines 3–5), the optimization replaces the original forall loop’s iterator
with a custom one (inspectorIterator). This custom iterator creates one task
on each locale to execute that locale’s portion of the original forall loop
serially. While this does reduce the total amount of parallelism that the
default iterator provides, it enables turning off parallel-safety for the
underlying associative arrays in the communication schedule, which generally
provides performance improvements. Once the loop structure is generated, the
optimization replaces the original expression C[i] = A[B[i]] with a call to
inspectAccess, which is a procedure we create to perform the memory access
analysis. Note that any code in the original loop that does not pertain to the
A[B[i]] access is removed to keep the inspector as lightweight as possible.
Furthermore, the call to inspectAccess does not perform the actual access to
A, but instead queries whether B[i] would be a remote access to A, since
remote accesses are expensive. Finally, the optimization inserts a call to
inspectorPreamble (line 2) before the inspector loop, which initializes some
of the communication schedule internal structures.

Turning the Inspector On/off: One of the key steps of the optimization is
determining when the inspector should execute. After the inspector runs for
the first time, it does not need to be run again unless the memory access
pattern changes. The static analysis phase (in Section 3.3) determines when
such changes occur and the optimization inserts calls to a procedure that sets
flags associated with A and B to indicate that the inspector should be
executed. The doInspector call on line 2 checks these flags and the
inspectorOff call on line 6 turns off the flags.

Executor Loop: For the executor loop, the optimization replaces the original
A[B[i]] access with a call to executeAccess (line 10), which redirects remote
accesses to the replicated copies. The optimization also inserts a call to
executorPreamble (line 8) just before the executor loop, which initializes the
replicated elements with the current values in A, ensuring that up-to-date
values will be used in the executor. While this does perform remote
communication, the optimization only communicates a remote element once,
regardless of how many times it is accessed in the loop. As a result, the cost
of the remote access is amortized over multiple local accesses.

###  3.3 Static Analysis

There are two main goals of the static analysis: (1) to detect scenarios where
the code transformations could lead to different program results compared to
the original program and (2) to only apply the optimization when performance
gains are likely. Each goal imposes different requirements that must be
resolved at compile-time, where violating any requirement will cause the
optimization to revert to the original code. We briefly describe the analysis
that is performed to achieve these two goals. We then discuss additional
analyses that were developed to increase the generality of the optimization.

Program Results: Since the optimization is applied automatically by the
compiler, it must detect scenarios where the code transformations could
produce program results that differ from the original code. The primary
scenario that could lead to different program results is not running the
inspector when necessary, resulting in communication schedules that are out of
date. To determine when the inspector needs to execute, the optimization must
be able to statically reason about the locale affinity of the forall loop and
the source/destination locales of the remote accesses for A[B[i]]. The
following criteria summarize the static checks performed for these purposes:

  1. 1.

The forall loop must iterate over a distributed array or distributed domain.

  2. 2.

The forall loop cannot be nested inside of another forall or any other
statement that could create multiple parallel tasks.

  3. 3.

The index i in A[B[i]] must be the loop index variable for the loop that
contains A[B[i]], and the loop must iterate over a domain or array.

  4. 4.

Neither A nor B, nor their domains, can be modified within the forall loop.

Check (1) ensures that the optimization can reason about the forall loop’s
locale affinity (i.e., which locales the iterations will execute on). Check
(2) ensures that multiple tasks will not execute the entire forall loop at the
same time, which would result in potential concurrent updates to the
communication schedules. Check (3) ensures that the optimization can
statically reason about the index i into B, specifically when the values of i
would change. Such changes would happen if the array/domain over which the
loop iterates is modified. Check (4) ensures that the values in B that are
analyzed by the inspector will be the same as the values used within the
executor (and the original loop). When applied to A, this check avoids the
complexities of writing to replicated elements of A and having to propagate
those values back to the original elements. If these checks are met, then the
optimization will determine all modifications to A, B, their domains and the
various other arrays/domains involved in the loop. If these objects are
modified, it indicates that A[B[i]] could exhibit an access pattern that
differs from when the inspector was last performed, whether it be different
indices used to access A or the accesses themselves being issued from
different locales. When modifications are found, the optimization will set the
corresponding flags to rerun the inspector to update the communication
schedule.

Program Performance: The goal of the optimization is to improve the runtime
performance of an input program. Therefore the static analysis attempts to
determine whether the optimization is likely to provide performance gains.
This analysis can be summarized as determining that the forall loop will
execute multiple times without requiring the inspector to be executed each
time, which would incur significant overhead. The following criteria summarize
the static checks performed for these purposes:

  1. (a)

The forall loop must be nested in an outer serial loop (i.e., for, while,
etc.).

  2. (b)

Neither B nor its domain can be modified within the outer loop that the forall
is nested in.

  3. (c)

A’s domain cannot be modified within the outer loop that the forall is nested
in.

Check (a) ensures that the forall loop is likely to be executed multiple
times, though it is not guaranteed to do so. Checks (b) and (c) ensure that
the inspector will not be executed each time the forall loop runs. Recall that
part of the code transformation phase is to “turn on” the inspector after
modifications to B, its domain or A’s domain. Such modifications have the
potential to alter the memory access pattern of A[B[i]], and therefore require
the inspector to be executed again. The array A is allowed to be modified
within the outer loop, as any changes to its values will be propagated to the
replicated copies via the executorPreamble. However, modifying A’s domain
could alter the access pattern A[B[i]] by adding/removing elements in A.

Non-affine Expression Analysis: Thus far we have focused our discussion on
accesses of the form A[B[i]]. However, the optimization can support more
complex non-affine expressions, such as A[B[i*j]%k+1], if certain conditions
are met. Specifically, the expressions must be binary operations between
immediates or variables yielded by loops that iterate over arrays/domains.
This requirement is needed so that the optimization can statically reason
about when/how the accesses to A and B could change. This is accomplished by
locating modifications to the arrays/domains that yield the variables used in
the expressions. Note that outside of our optimization, Chapel’s current
compiler does not perform affine/non-affine expression analysis.

Interprocedural and Alias Analyses: The optimization performs interprocedural
and alias analyses to support the static checks described previously. The
interprocedural analysis computes the call graph starting from the function
that contains the forall and checks for any invalid call paths. We deem a call
path invalid if there is a lack of an outer serial loop or if there is an
enclosing statement that creates multiple parallel tasks. When an invalid call
path is detected the compiler inserts flags that are set at runtime to “turn
off” the optimization temporarily along the invalid path. Also, the
interprocedural analysis detects modifications to the arrays/domains of
interest across arbitrarily nested function calls. Alias analysis is necessary
because Chapel allows users to create references to arrays/domains, which
operate similarly to pointers in C. To address this issue, we developed static
checks to detect such references and determine the original array/domain. This
analysis works for arbitrarily long alias chains (e.g., var arr = ...; ref a1
= arr; ref a2 = a1), where the optimization will detect modifications to any
of the references along the chain.

##  4 Performance Evaluation

To demonstrate the performance benefits of the compiler optimization described
in Section 3, we performed an evaluation of two irregular applications running
on two different distributed-memory systems. The applications we evaluate are
implemented in a high-level manner, consistent with Chapel’s design
philosophy, which is to separate data distribution/communication details from
the algorithm design. As a result, our exemplar applications closely match
standard shared-memory implementations and are representative of direct use of
the PGAS model. Our goal is to show that the performance of these Chapel
programs suffer from implicit fine-grained remote communication, but can be
significantly improved via automatic optimization without requiring the user
to modify the program. Therefore, users can take advantage of the productivity
benefits that Chapel provides while also achieving good performance.

###  4.1 Experimental Setup

For our evaluation, we run experiments on a Cray XC cluster and an Infiniband-
based cluster. For the Cray XC, we utilize up to 64 nodes connected over an
Aries interconnect, where each node has two 22-core Intel Xeon Broadwell CPUs
and 128 GB of DDR4 memory. For the Infiniband cluster, we utilize up to 32
nodes connected over an FDR Infiniband interconnect, where each node has two
10-core Intel Xeon Haswell CPUs and 512 GB of DDR4 memory. On the Cray XC,
Chapel is built using the ugni communication layer and the aries communication
substrate. On the Infiniband system, Chapel is built using the GASNet
communication layer and the ibv communication substrate. All applications on
both systems are compiled using the \---fast flag. For each experiment, we
execute the given application multiple times and measure the total runtime,
including the inspector overhead. The results represent the average of these
trials. We observed that the runtime variation between trials did not exceed
4%.

###  4.2 Application: NAS-CG

⬇ 1forall row in Rows { 2 var accum : real = 0; 3 for k in row.offsets { 4
accum += values[k] * x[col_idx[k]]; 5 } 6 b[row.id] = accum; 7} Listing 6:
forall loop for NAS-CG

The conjugate gradient (CG) method solves the equation $Ax=b$ for $x$, where
$A$ is a symmetric positive-definite matrix and is typically large and sparse,
and $x$ and $b$ are vectors. Unstructured optimization problems and partial
differential equations can be solved using iterative CG methods. For the
evaluation, we use the NAS-CG benchmark specification and datasets [3]. Table
2 describes the problem sizes evaluated, where each problem size corresponds
to the size of the $A$ matrix. Each iteration of NAS-CG performs a total of 26
sparse matrix-vector multiplies (SpMVs), which is the kernel of interest for
the optimization and is shown in Listing 6. The implementation uses a standard
Compressed Sparse Row (CSR) format to represent $A$, where Rows is a block
distributed array of records that contains the offsets into the distributed
array(s) containing the non-zero data values. This approach closely resembles
the Fortan+OpenMP implementation of NAS-CG [3]. The irregular access of
interest is on line 4, x[col_idx[k]]. For the optimization, the inspector only
needs to be executed once since the memory access pattern remains the same
across all SpMV operations. In regards to memory storage overhead due to
replication, we observed an average increase in memory usage of 6%.

Table 1: Datasets for NAS-CG

Name | Rows | Non-zeros | Density (%) | # of SpMVs
---|---|---|---|---
C | 150k | 39M | 0.17 | 1950
D | 150k | 73M | 0.32 | 2600
E | 9M | 6.6B | 0.008 | 2600
F | 54M | 55B | 0.002 | 2600

Table 2: Runtime speed-ups achieved by the optimization on the NAS-CG problem
sizes from Table 2 relative to the unoptimized code in Listing 6. Missing
values indicate that the problem size required too much memory to execute and
“NA” values indicate that the system did not support the specified number of
nodes/locales.

| Cray XC | Infiniband
---|---|---
Locales (Nodes) | C | D | E | F | C | D | E | F
2 | 3.2 | 2.8 | — | — | 8.9 | 6 | 357 | —
4 | 3.6 | 3.4 | 17.5 | — | 15.8 | 10.4 | 345 | —
8 | 5.7 | 6.2 | 36.7 | — | 115 | 127 | 364 | —
16 | 8.6 | 11 | 22.5 | — | 238 | 330 | 258 | 270
32 | 6.4 | 8.4 | 34 | 52.3 | 160 | 240 | 195 | 165
64 | 4.1 | 4.9 | 16.7 | 25.4 | NA | NA | NA | NA
geomean | 5 | 5.5 | 24.1 | 36.4 | 57.3 | 57.5 | 296 | 211

Table 2 presents the NAS-CG runtime speed-ups achieved by the optimization on
each system relative to the unoptimized code shown in Listing 6. We observe
large speed-ups on both systems, but most notably on the Infiniband system
because fine-grained remote communication exhibits higher latency compared to
the Aries interconnect on the Cray XC. On both systems, such speed-ups are
obtained because of a large amount of remote data reuse in the SpMV kernel,
which is due to the sparsity pattern of the matrices generated by the
benchmark. The optimization incurs the cost of reading the remote element
once, but can then access the element locally throughout the rest of the
forall loop. Without the optimization, each access to the remote element
likely pays the full latency cost of a remote access since the access pattern
is sparse and irregular. Additionally, the SpMV kernel is executed many times
during the NAS-CG benchmark, which allows for the inspector overhead to be
amortized. We observe that the percentage of runtime devoted to the inspector
is 3% on average across all locale counts for the Cray XC and 2% for the
Infiniband system.

Beyond relative speed-ups, the optimization significantly improves the overall
runtime, as can be see in Tables 6 and 6 in the Appendix. We observe very poor
runtime performance and scalability for the unoptimized code, which is due to
the implicit fine-grained remote communication required in the straightforward
implementation shown in Listing 6. On the other hand, the optimized version of
the code generally gets faster with more locales, since the optimization can
take advantage of remote data reuse. Overall, these results demonstrate the
usefulness of our optimization in automatically providing faster runtimes
without sacrificing user productivity.

###  4.3 Application: PageRank

⬇ 1forall v in Graph { 2 var val = 0.0; 3 for i in v.offsets { 4 ref t =
Graph[neighbors[i]]; 5 val += t.pr_read / t.out_degree; 6 } 7 v.pr_write =
(val * d) + ((1.0-d)/num_vertices) + sink_val; 8} Listing 7: forall loop for
PageRank

PageRank [5] is an iterative graph algorithm that provides an importance
measurement for each vertex in a graph. Listing 7 presents the PageRank kernel
and is the target of the optimization, where the irregular memory access of
interest is on line 4. Similar to NAS-CG, we use a CSR data structure to
represent the graph. The distributed array Graph stores records that
correspond to vertices, where each vertex has two importance measurements:
pr_write and pr_read. This allows for a straightforward parallel
implementation of the kernel by treating one value as read-only during an
iteration, and closely matches the GAP Benchmark Suite implementation [4].
Unlike NAS-CG, PageRank adds the complication of storing records in the array
of interest rather than base type data (i.e., int, real, etc.). The
optimization recognizes this feature and will only replicate the fields that
are accessed in the forall loop, namely, pr_read and out_degree.

We evaluate PageRank on two real web graphs obtained from the SuiteSparse
Matrix Collection [8], which are described in Table 3. The right-most column
denotes the number of iterations that are required to converge with a
tolerance value of $1e{\text{-}}7$ and a damping factor of 0.85 (d on line 7
in Listing 7). Our choice for these values matches what is used in Neo4j [19],
an open source graph database. Each PageRank iteration performs one execution
of the entire forall in Listing 7 and the inspector is only executed once
since the graph does not change throughout the execution. The memory storage
overhead of the optimization for PageRank is 40–80%, which is much larger than
what we observed for NAS-CG. For NAS-CG, the array of interest that is
replicated constitutes a small portion of the total memory required. But for
PageRank, the array of interest is much larger by comparison, resulting in a
larger relative increase in memory storage. However, the memory storage
overhead incurred by the optimization is significantly less than what full
replication would incur.

Table 3: Datasets for PageRank Name | Vertices | Edges | Density (%) | Iterations
---|---|---|---|---
webbase-2001 | 118M | 992M | $7.110-6$ | 33
sk-2005 | 51M | 1.9B | $7.510-5$ | 40
Table 4: Runtime speed-ups achieved by the optimization on PageRank for the graphs from Table 3 relative to the unoptimized implementation. “NA” values indicate that the system did not support the specified number of nodes/locales. | Cray XC | Infiniband
---|---|---
Locales (Nodes) | webbase-2001 | sk-2005 | webbase-2001 | sk-2005
2 | 0.88 | 1.2 | 5.2 | 2
4 | 0.98 | 1.6 | 8.6 | 7.1
8 | 0.97 | 1.3 | 12 | 6
16 | 0.94 | 1.7 | 9.6 | 5.4
32 | 1.3 | 1.4 | 4.5 | 4.2
64 | 1.2 | 2.1 | NA | NA
geomean | 1.04 | 1.5 | 7.3 | 4.5

Table 4 presents the runtime speed-ups for the optimization on both graphs
from Table 3, and Tables 8 and 8 in the Appendix presents the runtimes without
and with the optimization. As we observed for NAS-CG, the speed-ups on the
Infiniband system are larger than those on the Cray XC due to the Aries
interconnect. However, we observe significantly smaller speed-ups overall when
compared to NAS-CG. This is largely because the PageRank kernel is executed
fewer times than the NAS-CG kernel, and the graphs exhibit significantly less
data reuse when compared to NAS-CG. As a result, there is a larger inspector
overhead and smaller performance gains from the executor. For these reasons,
speed-ups are not achieved on the webbase-2001 graph on the Cray XC until 32
locales, which is when the remote data reuse reaches its peak. Furthermore,
due to the highly irregular nature of the graphs (whose degree distributions
follow a power law), the runtime performance fluctuates as the number of
locales increase due to the partitioning of the graph across the system. This
can change where the elements are located, which may lead to a once heavily
accessed remote element now being local. This is more significant for the
unoptimized code, as the optimization would have only incurred the cost of the
remote access once due to replication. Nevertheless, the scalability of the
optimization generally tracks the scalability of the code without the
optimization applied.

##  5 Related Work

Techniques to perform runtime optimizations for irregular memory accesses have
been worked on for many years, and of particular relevance to our work is the
_inspector-executor_ technique [16, 9, 17]. Das et al. [7] presented an
inspector-executor optimization similar to ours, but that work predates the
PGAS model, so is not directly applicable due to fundamental differences in
programming model design and implementation. For PGAS languages, Su and Yelick
[18] developed an inspector-executor optimization that is similar to ours but
for the language Titanium. However, Titanium differs from Chapel in its
execution model as well as its language constructs for parallel loops, since
it is based on Java. This leads to an overall different approach to static
analysis. Alvanos et al. [1, 2] described an inspector-executor framework for
the PGAS language UPC [11], which also differs from Chapel. UPC uses a SPMD
model and requires explicit constructs to control the processor affinity of
parallel loops. Like Titanium, these differences lead to a significantly
different approach to the static analysis used for the optimization. However,
we plan to explore some of their techniques in future work. For compiler
optimizations related specifically to Chapel, Kayraklioglu et al. [12]
presented an optimization to aggregate remote accesses to distributed arrays.
However, their optimization does not specifically target irregular memory
accesses, which leads to significantly different approaches to static analysis
and code transformation. Furthermore, the applications we evaluate in Section
4 are not candidates for their aggregation optimization.

##  6 Conclusions and Future Work

While the PGAS model provides user productivity advantages for writing
distributed irregular applications, the resulting code often has poor runtime
performance due to fine-grained remote communication. In this work we have
presented a compiler optimization for Chapel programs that specifically
targets irregular memory access patterns within parallel loops and
automatically applies code transformations to replicate remotely accessed
data. We demonstrated that the optimization provides runtime speed-ups as
large as 52x on a Cray XC system and 364x on an Infiniband system. To this
end, we have shown that significant performance gains can be achieved without
sacrificing user productivity.

For future work, we plan to improve upon our compiler optimization framework
and address some of the limitations, such as optimizing multiple irregular
accesses in the same loop. We also plan to design additional compiler
optimizations to serve as alternatives to selective data replication when that
cannot be applied, as it currently is only applicable for read-only data.
Future optimizations will specifically target writes.

## Acknowledgements

We would like to thank Brad Chamberlain, Engin Kayraklioglu, Vass Litvinov,
Elliot Ronaghan and Michelle Strout from the Chapel team for their guidance on
working with the Chapel compiler, as well as providing access to the Cray XC
system that was used in our performance evaluation.

## Appendix

In this appendix we provide additional performance results for the experiments
performed in Section 4. Table 6 presents execution runtimes for the
unoptimized implementation of NAS-CG and Table 6 presents the runtimes for the
automatically optimized implementation of NAS-CG. Due to the amount of time
required by the unoptimized code for problem sizes E and F, we project their
total runtime based on their average iteration runtime. Each iteration of NAS-
CG performs the same computation and communication, and we note that the
variation between iterations is no more than 2% on problem sizes C and D.
Tables 8 and 8 present similar data for the PageRank application.

Table 5: Execution runtimes (in minutes) for the unoptimized implementation of
NAS-CG when executed on the problem sizes from Table 2. Missing values
indicate that the problem size required too much memory to execute and “NA”
values indicate that the system did not support the specified number of
nodes/locales. Runtimes for problem sizes E and F are projected from single
iteration runtimes.

| Cray XC | Infiniband
---|---|---
Locales (Nodes) | C | D | E | F | C | D | E | F
2 | 1.8 | 3.9 | — | — | 9 | 15 | $2.3\mathrm{e}{+5}$ | —
4 | 1.7 | 3.4 | 2882 | — | 12 | 17 | $1.7\mathrm{e}{+5}$ | —
8 | 2.2 | 4.8 | 3069 | — | 58 | 131 | $1\mathrm{e}{+5}$ | —
16 | 2.7 | 6.1 | 1005 | — | 96 | 242 | $5.7\mathrm{e}{+4}$ | $4.7\mathrm{e}{+5}$
32 | 1.8 | 4 | 845 | 9927 | 64 | 156 | $3.1\mathrm{e}{+4}$ | $2.4\mathrm{e}{+5}$
64 | 1.2 | 2.6 | 285 | 3501 | NA | NA | NA | NA

Table 6: Execution runtimes (in minutes) for the automatically optimized
implementation of NAS-CG when executed on the problem sizes from Table 2.
Missing values indicate that the problem size required too much memory to
execute and “NA” values indicate that the system did not support the specified
number of nodes/locales. Runtimes for problem sizes E and F are projected from
single iteration runtimes.

| Cray XC | Infiniband
---|---|---
Locales (Nodes) | C | D | E | F | C | D | E | F
2 | 0.6 | 1.4 | — | — | 1.1 | 2.6 | 655 | —
4 | 0.5 | 1 | 165 | — | 0.7 | 1.7 | 489 | —
8 | 0.4 | 0.8 | 84 | — | 0.5 | 1 | 279 | —
16 | 0.3 | 0.6 | 45 | — | 0.4 | 0.7 | 221 | 1732
32 | 0.3 | 0.5 | 25 | 190 | 0.4 | 0.6 | 156 | 1437
64 | 0.3 | 0.5 | 17 | 138 | NA | NA | NA | NA

Table 7: Execution runtimes (in minutes) for the unoptimized implementation of
PageRank when executed on the graphs from Table 3. “NA” values indicate that
the system did not support the specified number of nodes/locales.

| Cray XC | Infiniband
---|---|---
Locales (Nodes) | webbase-2001 | sk-2005 | webbase-2001 | sk-2005
2 | 1.1 | 4.1 | 14.6 | 14
4 | 0.9 | 3.8 | 14.6 | 28
8 | 0.7 | 4.4 | 14.9 | 23
16 | 0.6 | 7.3 | 9.7 | 29
32 | 0.6 | 5.7 | 6.9 | 26
64 | 0.7 | 10 | NA | NA

Table 8: Execution runtimes (in minutes) for the automatically optimized
implementation of PageRank when executed on the graphs from Table 3. “NA”
values indicate that the system did not support the specified number of
nodes/locales.

| Cray XC | Infiniband
---|---|---
Locales (Nodes) | webbase-2001 | sk-2005 | webbase-2001 | sk-2005
2 | 1.2 | 3.3 | 2.8 | 6.9
4 | 1 | 2.4 | 1.7 | 3.9
8 | 0.8 | 3.4 | 1.2 | 3.9
16 | 0.7 | 4.2 | 1.1 | 5.5
32 | 0.5 | 4.2 | 1.5 | 6.2
64 | 0.6 | 4.7 | NA | NA

## References

  * [1] Alvanos, M., Farreras, M., Tiotto, E., Amaral, J.N., Martorell, X.: Improving communication in PGAS environments: static and dynamic coalescing in UPC. In: Proceedings of the 27th International ACM Conference on Supercomputing (ICS’13). p. 129–138. Association for Computing Machinery (2013). https://doi.org/10.1145/2464996.2465006, https://doi.org/10.1145/2464996.2465006
  * [2] Alvanos, M., Tiotto, E., Amaral, J.N., Farreras, M., Martorell, X.: Using shared-data localization to reduce the cost of inspector-execution in Unified-Parallel-C programs. Parallel Computing 54, 2–14 (2016). https://doi.org/https://doi.org/10.1016/j.parco.2016.03.002
  * [3] Bailey, D., Harris, T., Saphir, W., Van Der Wijngaart, R., Woo, A., Yarrow, M.: The NAS parallel benchmarks 2.0. Tech. rep., Technical Report NAS-95-020, NASA Ames Research Center (1995)
  * [4] Beamer, S., Asanović, K., Patterson, D.: The GAP benchmark suite (2015). https://doi.org/10.48550/ARXIV.1508.03619
  * [5] Bianchini, M., Gori, M., Scarselli, F.: Inside PageRank. ACM Transactions on Internet Technology 5(1), 92–128 (2005)
  * [6] Chamberlain, B.L., Callahan, D., Zima, H.P.: Parallel programmability and the Chapel language. The International Journal of High Performance Computing Applications 21(3), 291–312 (2007)
  * [7] Das, R., Uysal, M., Saltz, J., Hwang, Y.S.: Communication optimizations for irregular scientific computations on distributed memory architectures. Journal of Parallel and Distributed Computing 22(3), 462–478 (1994)
  * [8] Davis, T.A., Hu, Y.: The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw. 38(1), 1:1–1:25 (Dec 2011). https://doi.org/10.1145/2049662.2049663
  * [9] Ding, C., Kennedy, K.: Improving cache performance in dynamic applications through data and computation reorganization at run time. In: Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation. pp. 229–241. ACM (1999). https://doi.org/10.1145/301618.301670
  * [10] Dongarra, J., Heroux, M.A., Luszczek, P.: High-performance conjugate-gradient benchmark: A new metric for ranking high-performance computing systems. The International Journal of High Performance Computing Applications 30(1), 3–10 (2016)
  * [11] El-Ghazawi, T., Carlson, W., Sterling, T., Yelick, K.: UPC: Distributed Shared Memory Programming, Wiley Series on Parallel and Distributed Computing, vol. 40. John Wiley & Sons (2005)
  * [12] Kayraklioglu, E., Ronaghan, E., Ferguson, M.P., Chamberlain, B.L.: Locality-based optimizations in the Chapel compiler. In: Li, X., Chandrasekaran, S. (eds.) Languages and Compilers for Parallel Computing. pp. 3–17. Springer (2021)
  * [13] Lumsdaine, A., Gregor, D., Hendrickson, B., Berry, J.: Challenges in parallel graph processing. Parallel Processing Letters 17(01), 5–20 (2007)
  * [14] Nieplocha, J., Harrison, R.J., Littlefield, R.J.: Global Arrays: A nonuniform memory access programming model for high-performance computers. The Journal of Supercomputing 10(2), 169–189 (1996)
  * [15] Rauchwerger, L., Padua, D.: The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization. IEEE Transactions on Parallel and Distributed Systems 10(2), 160–180 (1999). https://doi.org/10.1109/71.752782
  * [16] Saltz, J.H., Mirchandaney, R., Crowley, K.: Run-time parallelization and scheduling of loops. IEEE Transactions on Computers 40(5), 603–612 (1991)
  * [17] Strout, M.M., Carter, L., Ferrante, J.: Compile-time composition of run-time data and iteration reorderings. In: Proceedings of the ACM SIGPLAN 2003 Conference on Programming language Design and Implementation. pp. 91–102. ACM (2003)
  * [18] Su, J., Yelick, K.: Automatic support for irregular computations in a high-level language. In: IEEE International Parallel and Distributed Processing Symposium. vol. 2, pp. 53b–53b. IEEE (2005)
  * [19] Webber, J.: A programmatic introduction to Neo4j. In: Proceedings of the 3rd Annual Conference on Systems, Programming, and Applications: Software for Humanity. p. 217–218. ACM (2012). https://doi.org/10.1145/2384716.2384777
  * [20] Williams, S., Oliker, L., Vuduc, R., Shalf, J., Yelick, K., Demmel, J.: Optimization of sparse matrix-vector multiplication on emerging multicore platforms. In: SC’07: Proceedings of the 2007 ACM/IEEE Conference on Supercomputing. pp. 1–12. IEEE (2007)