# Fully Read/Write Fence-Free Work-Stealing with Multiplicity

Armando Castañeda  Instituto de Matemáticas, UNAMMéxico
<EMAIL_ADDRESS>and  Miguel Piña  Facultad de Ciencias,
UNAMMéxico<EMAIL_ADDRESS>
###### Abstract.

_Work-stealing_ is a popular technique to implement dynamic _load balancing_
in a distributed manner. In this approach, each process _owns_ a set of tasks
that have to be executed. The _owner_ of the set can put tasks in it and can
take tasks from it to execute them. When a process runs out of tasks, instead
of being idle, it becomes a _thief_ to steal tasks from a _victim_. Thus, a
work-stealing algorithm provides three high-level operations: Put and Take,
which can be invoked only by the owner, and Steal, which can be invoked by a
thief.

One of the main targets when designing work-stealing algorithms is to make Put
and Take as simple and efficient as possible. Unfortunately, it has been shown
that any work-stealing algorithm in the standard asynchronous model must use
expensive Read-After-Write synchronization patterns or atomic Read-Modify-
Write instructions, which may be costly in practice. Thus, prior research has
proposed _idempotent_ work-stealing, a relaxation for which there are
algorithms with Put and Take devoid of Read-Modify-Write atomic instructions
and Read-After-Write synchronization patterns; however, Put uses fences among
Write instructions, and Steal uses Compare&Swap and fences among Read
instructions. In the TSO model, in which Write (resp. Read) instructions
cannot be reordered, there have been proposed fully fence-free work-stealing
algorithms whose Put and Take have similar properties but Steal uses
Compare&Swap or a _lock_.

This paper considers work-stealing with _multiplicity_ , a relaxation in which
every task is taken by _at least_ one operation, with the requirement that any
process can extract a task _at most once_. Two versions of the relaxation are
considered and two _fully Read/Write_ algorithms are presented in the standard
asynchronous shared memory model, both devoid of Read-After-Write
synchronization patterns in all its operations, the second algorithm
additionally being _fully fence-free_. Furthermore, the algorithms have
logarithmic and constant step complexity, respectively. To our knowledge,
these are the first algorithm for work-stealing possessing all these
properties. Our algorithms are also wait-free solutions of relaxed versions of
single-enqueue multi-dequeuer queues, namely, with multiplicity and weak
multiplicity. The algorithms are obtained by reducing work-stealing with
multiplicity and weak multiplicity to MaxRegister and RangeMaxRegister, a
relaxation of MaxRegister which might be of independent interest.

An experimental evaluation shows that our fully fence-free algorithm exhibits
better performance than The Cilk, Chase-Lev and Idempotent Work-Stealing
algorithms, while a simple variant of it, with a Swap-based Steal operation,
shows a lower performance but keeps competitive.

††conference: ; ;

##  1\. Introduction

#### Context

_Work-stealing_ is a popular technique to implement dynamic _load balancing_
in a distributed manner; it has been used in several contexts, from
programming languages and parallel-programming frameworks to SAT solver and
state space search exploration in model checking (e.g. (ACDHLMTUZ09, ;
BJKLRZ95, ; CGSDKEPS05, ; FDSZ01, ; FLR98, ; L00, ; RRPBK07, )).

In work-stealing, each process _owns_ a set of tasks that have to be executed.
The _owner_ of the set can put tasks in it and can take tasks from it to
execute them. When a process runs out of tasks (i.e. the set is empty),
instead of being idle, it becomes a _thief_ to steal tasks from a _victim_.
Thus, a work-stealing algorithm provides three high-level operations: Put and
Take, which can be invoked only by the owner, and Steal, which can be invoked
by a thief.

One of the main targets when designing work-stealing algorithms is to make Put
and Take as simple and efficient as possible. Unfortunately, it has been shown
that any work-stealing algorithm in the standard asynchronous model must use
Read-After-Write synchronization patterns or atomic Read-Modify-Write
instructions (e.g. Compare&Swap or Test&Set) (AGHKMV11, ). Read-After-Write
synchronization patterns are based on the _flag principle_ (HS08, ) (i.e.
writing on a shared variable and then reading another variable), and hence
they require the use of memory _fences_ (also called _barriers_) so that the
read and write instructions are not reordered by a compiler; it is well-known
that fences that avoid read and writes to be reordered are highly costly in
real multicore architectures. While atomic Read-Modify-Write instructions,
that have high coordination power (which can be formally measured through the
_consensus number_ formalism (H91, )), are in principle slower than the simple
Read/Write instructions.111In practice, contention might be the dominant
factor, namely, an uncontended Read-Modify-Write instruction can be faster
than contended Read/Write instructions. Indeed, the known work-stealing
algorithms in the literature are based on the flag principle in their
Take/Steal operations (CL05, ; FLR98, ; HLMS06, ; HS02, ). Thus, a way to
circumvent the result in (AGHKMV11, ) is to consider work-stealing with
relaxed semantics, or to make extra assumptions on the model. As far as we
know, (MlVS09, ) and (MA14, ) are the only works that have followed these
directions.

_Idempotent_ work-stealing (MlVS09, ) relaxes the semantics allowing a task to
be taken _at least once_ , instead of _exactly once_. This relaxation is
useful in contexts where it is ensured that no task is repeated (e.g. by
checking first whether a task is completed) or the nature of the problem
solved tolerates repeatable work (e.g. parallel SAT solvers). Three idempotent
work-stealing algorithms are presented in (MlVS09, ), that insert/extract
tasks in different orders (FIFO, LIFO and double-ended queue). The relaxation
allows each of the algorithms to circumvent the impossibility result in
(AGHKMV11, ), only in its Put and Take operations as they use only Read/Write
instructions and are devoid of Read-After-Write synchronization patterns;
however, Steal uses Compare&Swap. Moreover, the algorithms are not fully
fence-free: Put uses fences among Write instructions and Steal uses fences
among Read instructions. As for progress guarantees, Put and Take are _wait-
free_ (i.e. each invocation always terminates) while Steal is only
_nonblocking_ (i.e. an invocation may be blocked by the progress of other
invocations).

It is presented in (MA14, ) two _fully fence-free_ work-stealing algorithms in
the TSO model (SSONM10, ), whose Put and Take operations use only Read/Write
instructions but Steal either uses Compare&Swap or a _lock_ ; Put and Take are
wait-free, and Steal is either nonblocking (in the Compare&Swap-based
algorithm) or _blocking_ (in the lock-based algorithm). The algorithms are
clever adaptations of the well-known THE Cilk and Chase-Lev work-stealing
algorithms (CL05, ; FLR98, ) to the TSO model. Generally speaking, in this
model Write (resp. Read) instructions cannot be reordered, hence fences among
Write (resp. Read) instructions are not needed; additionally, each process has
a local buffer where its Write instructions are stored until they are
eventually propagated to the main memory (in FIFO order). To avoid Read-After-
Write patterns, it is considered in (MA14, ) that buffers are of bounded size.

In this paper we are interested in the following theoretical question: whether
there are meaningful relaxations of work-stealing that allows us to design
fully Read/Write, fence-free and wait-free algorithms, i.e. using only
Read/Write instructions (which lay at the lowest level of the consensus number
hierarchy (H91, )) without fences, providing strong termination guarantees and
with no extra assumptions to the model of computation. In other words, if
simple synchronization mechanisms suffice to solve non-trivial relaxations of
work-stealing.

#### Contributions

First, we consider work-stealing with _multiplicity_ (CRR20, ), a relaxation
in which every task is taken by _at least_ one operation, and, differently
from idempotent work-stealing, it requires that if a task is taken by several
Take/Steal operations, then they must be _pairwise concurrent_ ; therefore, no
more than the number of processes in the system can take the same task. In our
relaxation, tasks are inserted/extracted in FIFO order. We present a fully
Read/Write algorithm for work-stealing with multiplicity, with its Put
operation being fence-free and its Take and Steal operations being devoid of
Read-After-Write synchronization patterns. As for progress, all operations are
wait-free with Put having constant _step complexity_ (i.e. the maximum number
of steps/instructions needed to complete) and Take and Steal having
logarithmic step complexity. The algorithm stands for its simplicity, based on
a single instance of a MaxRegister object, hence showing that work-stealing
with multiplicity reduces to MaxRegister. A MaxRegister object (AAC12, ;
JTT00, ) provides two operations: MaxRead that returns the maximum value
written so far in the object, and MaxWrite that writes a new value only if it
is greater than the largest value that has been written so far.

We also consider a variation of work-stealing with multiplicity in which
Take/Steal operations extracting the same task _may not be concurrent_ ,
however, each process extracts a task _at most once_ ; this variant, which
insert/extract tasks in FIFO order too, is called work-stealing with _weak
multiplicity_. For this relaxation, we present an algorithm, inspired in our
first solution, which uses only Read/Write instructions, is _fully fence-free_
and all its operations are wait-free; furthermore each operation executes a
constant number of instructions to complete. To our knowledge, this is the
first algorithm for work-stealing having all these properties. The algorithm
is obtained by a reduction to a relaxation of MaxRegister with a RMaxRead
operation that returns a value in a _range_ of values that have been written
in the register; the range always includes the maximum value written so far.
This relaxation, which might be of independent interests, is called
RangeMaxRegister.

Additionally, we show that each of our algorithms can be easily modified so
that every task is extracted by a bounded number of operations; more
specifically, by at most one Take operation and at most one Steal operation.
In the modified algorithms, Put and Take remain the same, and a single Swap
instruction is added to Steal, which remains fence-free.

We stress that our algorithms are also wait-free solutions of relaxed versions
of single-enqueue multi-dequeuer queues, namely, with multiplicity and weak
multiplicity. To the best of our knowledge, together with idempotent FIFO,
these are the only single-enqueue multi-dequeuer queue relaxations that have
been studied.

Formal specifications and correctness proofs are provided, using the
_linearizability_ (HW90, ) and _set-linearizable_ correctness formalisms
(CRR18, ; N94, ). Intuitively, set-linearizability is a generalization of
linearizability in which several concurrent operations are allowed to be
linearized at the same linearization point.

Work-stealing with multiplicity and idempotent work-stealing are closely
related, but they are not the same. We observe that the idempotent work-
stealing algorithms in (MlVS09, ) allow a task to be extracted by an unbounded
number of Steal operations; moreover, a thief can extract the same task an
unbounded number of times. This observation implies that the algorithms in
(MlVS09, ) do not solve work-stealing with multiplicity. Therefore, the
relaxations and algorithms proposed here provide stronger guarantees than
idempotent work-stealing algorithms, without the need of heavy synchronization
mechanisms.

We complement our results by studying the question if there are
implementations of our algorithms with good performance in practical settings.
We conducted an experimental evaluation comparing our algorithms to THE Cilk,
Chase-Lev and the idempotent work-stealing algorithms. In the experiments, the
fully fence-free algorithm exhibits a better performance than the previously
mentioned algorithms, while its bounded version, with a Swap-based Steal
operation, shows a lower performance but keeps competitive.

#### Related Work

To the best of our knowledge, (MlVS09, ) and (MA14, ) are the only works that
have been able to avoid costly synchronization mechanisms in work-stealing
algorithms. The three idempotent algorithms in (MlVS09, ) insert/extract tasks
in FIFO and LIFO orders, and as in a double-ended queue (the owner working on
one side and the thieves on the other). The experimental evaluation shows that
the idempotent algorithms outperform THE Cilk and Chase-Lev work-stealing
algorithms. The work-stealing algorithms in (MA14, ) are fence-free
adaptations of THE Cilk and Chase-Lev (CL05, ; FLR98, ) to the TSO model. The
model itself guarantees that fences among Write (resp. Read) instructions are
not needed, and the authors of (MA14, ) assume that write-buffers in TSO are
bounded so that a fence-free coordination mechanism can be added to the Take
and Steal operations of THE Cilk and Chase-Lev. The experimental evaluation in
(MA14, ) shows that their algorithms outperform THE Cilk and Chase-Lev and
sometimes achieve performance comparable to the idempotent work-stealing
algorithms.

The notion of multiplicity was recently introduced in (CRR20, ) for queues and
stacks. In a queue/stack with multiplicity, an item can be dequeued/popped by
several operations but only if they are concurrent. Read/Write set-
linearizable algorithms for queues and stacks with multiplicity and without
Read-After-Write synchronization patterns are provided in (CRR20, ), and it is
noted that these algorithms are also solutions for work-stealing with
multiplicity; the step complexity of Enqueue/Push, which implements Put, is
$\Theta(n)$ while the step complexity of Dequeue/Pop, which implements Take
and Steal, is unbounded, where $n$ denotes the number of processes. Our
algorithms for work-stealing with multiplicity follows different principles
than those in (CRR20, ). The weak multiplicity relaxation of work-stealing
follows the same idea as the relaxations in (CRR20, ) as it requires that any
algorithm provides “exact” responses in sequential executions, namely, the
relaxation applies only if there is no contention.

As far we know, only two single-enqueue multi-dequeuer queue algorithms have
been proposed so far (D04, ; JP05, ). The algorithm in (D04, ) is wait-free
with constant step complexity and uses Read-Modify-Write instructions with
consensus number 2, specifically, Swap and Fetch&Increment; however, the
algorithm uses arrays of infinite length. It is explained in (D04, ) that this
assumption can be removed at the cost of increasing the step complexity to
$O(n)$, where $n$ denotes the number of processes. The algorithm in (JP05, )
is wait-free with $O(\log n)$ step complexity and uses LL/SC, a Read-Modify-
Write instruction whose consensus number is $\infty$, and using a bounded
amount of memory. Our results show that there are single-enqueue multi-
dequeuer queue relaxations that can be solved using very light synchronization
mechanisms.

#### Organization

The rest of the paper is organized as follows. Section 2 describes the model
of computation and the linearizability and set-linearizability formalisms.
Section 3 formally defines work-stealing with multiplicity and presents a
solution based on a single MaxRegister object. The work-stealing with weak
multiplicity and its algorithm are presented in Section 4. Simple variants of
the algorithms that bound the number of operations that can extract the same
task are discussed in Section 5, while Section 6 shows how our algorithms can
be implemented using finite length arrays. Section 7 explain the differences
between work-stealing with multiplicity and idempotent work-stealing. Sections
8 presents the results of the experimental evaluation. The paper concludes
with a final discussion in Section 9.

##  2\. Preliminaries

#### Model of Computation

We consider a standard concurrent shared memory system with $n\geq 2$
_asynchronous_ processes, $p_{0},\ldots,p_{n-1}$, which may _crash_ at any
time during an execution. Processes communicate with each other by invoking
_atomic_ instructions of _base_ objects: either simple Read/Write
instructions, or more powerful Read-Modify-Write instructions, such as Swap or
Compare&Swap. The _index_ of process $p_{i}$ is $i$.

A _concurrent object_ , or _data type_ , is, roughly speaking, defined by a
state machine consisting of a set of states, a finite set of operations, and a
set of transitions between states. The specification does not necessarily have
to be sequential, namely, state transitions might involve several invocations.
The following subsection formalize _sequential_ and _set-sequential_ objects.

An _algorithm_ for a concurrent object $T$ is a distributed algorithm
$\mathcal{A}$ consisting of local state machines $A_{1},\ldots,A_{n}$. Local
machine $A_{i}$ specifies which instructions of base objects $p_{i}$ executes
in order to return a response, when it invokes a (high-level) operation of
$T$; each of these instructions is a _step_.

An _execution_ of $\mathcal{A}$ is a (possibly infinite) sequence of steps,
namely, instructions of base objects, plus invocations and responses of (high-
level) operations of the concurrent object $T$, with the following properties:

  1. (1)

Each process first invokes an operation, and only when it has a corresponding
response, it can invoke another operation, i.e., executions are _well-formed_.

  2. (2)

For any invocation to an operation op, denoted $inv({\sf op})$, of a process
$p_{i}$, the steps of $p_{i}$ between that invocation and its corresponding
response (if there is one), denoted $res({\sf op})$, are steps that are
specified by $\mathcal{A}$ when $p_{i}$ invokes op.

An operation in an execution is _complete_ if both its invocation and response
appear in the execution. An operation is _pending_ if only its invocation
appears in the execution. A process is _correct_ in an execution if it takes
infinitely many steps. An execution $E$ is an _extension_ of an execution $F$,
if $E$ is a prefix of $F$, namely, $E=FF^{\prime}$ for some $F^{\prime}$.

An algorithm, or an operation of it, is _nonblocking_ if whenever processes
take steps, at least one of the invocations terminates (HW90, ). Formally, in
every infinite execution, infinitely many invocations are completed. An
algorithm, or an operation of it, is _wait-free_ if every process completes
each operation in a finite number of its steps (H91, ). Formally, if a process
executes infinitely many steps in an execution, all its invocations are
completed. _Bounded wait-freedom_ (H91a, ) additionally requires that there is
a bound on the number of steps needed to terminate. Thus, a wait-free
implementation is nonblocking but not necessarily vice versa.

The _step complexity_ of an operation of an algorithm is the maximum number
steps a process needs to execute in order to return.

In a Read-After-Write synchronization pattern, a process first writes in a
shared variable and then reads another shared variable, maybe executing other
instructions in between. Note that Read-After-Write patterns can be avoided if
in each (high-level) operation of an algorithm, a process performs a sequence
of writes, or a sequence of reads followed by a sequence of writes.

We say that an algorithm, or one of its operations, is _fence-free_ if it does
not require any specific ordering among its steps, beyond what is implied by
data dependence. Thus, a fence-free algorithms does not use Read-After-Write
synchronization patterns. In our algorithms, we use the notation
$\\{O_{1}.inst_{1},\ldots,O_{x}.inst_{x}\\}$ to denote that the instructions
$O_{1}.inst_{1},\ldots,O_{x}.inst_{x}$ can be executed in any order, hence no
fence is required between any pair of them.

For sake of simplicity in the analysis, first we will present our algorithms
using arrays of infinite length, and later explain how to implement them using
arrays of finite length.

#### Correctness Conditions

_Linearizability_ (HW90, ) is the standard notion used to identify a correct
implementation. Intuitively, an execution is linearizable if its (high-level)
operations can be ordered sequentially, without reordering non-overlapping
operations, so that their responses satisfy the specification of the
implemented object.

A _sequential specification_ of a concurrent object $T$ is a state machine
specified through a transition function $\delta$. Given a state $q$ and an
invocation $inv({\sf op})$, $\delta(q,inv({\sf op}))$ returns the tuple
$(q^{\prime},res({\sf op}))$ (or a set of tuples if the machine is _non-
deterministic_) indicating that the machine moves to state $q^{\prime}$ and
the response to op is $res({\sf op}$). The sequences of invocation-response
tuples, $\langle inv({\sf op}):res({\sf op})\rangle$, produced by the state
machine are its _sequential executions_.

To formalize linearizability we define a partial order $<_{E}$ on the
completed operations of an execution $E$: ${\sf op}<_{E}{\sf op}^{\prime}$ if
and only if $res({\sf op})$ precedes $inv({\sf op}^{\prime})$ in $E$. Two
operations are _concurrent_ , denoted ${\sf op}\,||_{E}\,{\sf op}^{\prime}$,
if they are incomparable by $<_{E}$. The execution is _sequential_ if $<_{E}$
is a total order.

###### Definition 2.1 (Linearizability).

Let $\mathcal{A}$ be an algorithm for a concurrent object $T$. A finite
execution $E$ of $\mathcal{A}$ is _linearizable_ if there is a sequential
execution $S$ of $T$ such that,

  1. (1)

$S$ contains every completed operation of $E$ and might contain some pending
operations. Inputs and outputs of invocations and responses in $S$ agree with
inputs and outputs in $E$,

  2. (2)

for every two completed operations op and ${\sf op}^{\prime}$ in $E$, if ${\sf
op}<_{E}{\sf op}^{\prime}$, then op appears before ${\sf op}^{\prime}$ in $S$.

We say that $\mathcal{A}$ is _linearizable_ if each of its finite executions
is linearizable.

Roughly speaking, while linearizability requires a total order on the
operations, set-linearizability (CRR18, ; N94, ) allows several operations to
be linearized at the same linearization point. Figure 1 schematizes the
differences between the two consistency conditions where each double-end arrow
represents an operation execution. It is known that set-linearizability has
strictly more expressiveness power than linearizability. Moreover, as
linearizability, set-linearizability is _composable_ (also called _local_)
(CRR18, ).

Figure 1. Graphical description of linearizability and set-linearizability.

A _set-sequential specification_ of a concurrent object differs from a
sequential execution in that $\delta$ receives as input the current state $q$
of the machine and a set $Inv=\\{inv({\sf op_{1}}),\ldots,inv({\sf
op}_{t})\\}$ of operation invocations that happen concurrently. Thus
$\delta(q,Inv)$ returns $(q^{\prime},Res)$ where $q^{\prime}$ is the next
state and $Res=\\{res({\sf op_{1}}),\ldots,res({\sf op}_{t})\\}$ are the
responses to the invocations in $Inv$ (if the machine is non-deterministic,
$Res$ is a set of sets of responses). The sets $Inv$ and$Res$ are called
_concurrency classes_. The sequences of invocation-response concurrency
classes, $\langle INV:RES\rangle$, produced by the state machine are its _set-
sequential executions_. Observe that in a sequential specification all
concurrency classes have a single element.

###### Definition 2.2 (Set-linearizability).

Let $\mathcal{A}$ be an algorithm for a concurrent object $T$. A finite
execution $E$ of $\mathcal{A}$ is _set-linearizable_ if there is a set-
sequential execution $S$ of $T$ such that

  1. (1)

$S$ contains every completed operation of $E$ and might contain some pending
operations. Inputs and outputs of invocations and responses in $S$ agree with
inputs and outputs in $E$.

  2. (2)

For every two completed operations op and ${\sf op}^{\prime}$ in $E$, if ${\sf
op}<_{E}{\sf op}^{\prime}$, then op appears before ${\sf op}^{\prime}$ in $S$.

We say that $\mathcal{A}$ is _set-linearizable_ if each of its finite
executions is set-linearizable.

##  3\. Work-Stealing with Multiplicity

Work-stealing with _multiplicity_ is a relaxation of the usual work-stealing
in which, roughly speaking, every task is extracted _at least once_ , and if
it is extracted by several operations, they must be _concurrent_. In the
formal set-sequential specification below (and in its variant in the next
section), tasks are inserted/extracted in FIFO order but it can be easily
adapted to encompass other orders (e.g. LIFO). Figure 2 depicts an example of
a set-sequential execution of the work-stealing with multiplicity, where
concurrent Take/Steal operations can extract the same task.

Figure 2. A set-sequential execution of work-stealing with multiplicity.

###### Definition 3.1 ((FIFO) Work-Stealing with Multiplicity).

The universe of tasks that the owner can put is $\mathbf{N}=\\{1,2,\ldots\\}$,
and the set of states $Q$ is the infinite set of finite strings
$\mathbf{N}^{*}$. The initial state is the empty string, denoted $\epsilon$.
In state $q$, the first element in $q$ represents the _head_ and the last one
the _tail_. The transitions are the following:

  1. (1)

$\forall q\in Q\delta(q,{\sf Put}(x))=(q\cdot x,\langle{\sf Put}(x):{\sf
true}\rangle).$

  2. (2)

$\forall q\in Q$, $0\leq t\leq n-1$, $x\in\mathbf{N},\ \delta(x\cdot q,\\{{\sf
Take}(),{\sf Steal}_{1}(),\ldots,{\sf Steal}_{t}()\\})=\\\ (q,\\{\langle{\sf
Take}():x\rangle,\langle{\sf Steal}_{1}():x\rangle,\ldots,\langle{\sf
Steal}_{t}():x\rangle\\})$.

  3. (3)

$\forall q\in Q$, $1\leq t\leq n-1$, $x\in\mathbf{N},\delta(x\cdot q,\\{{\sf
Steal}_{1}(),\ldots,{\sf Steal}_{t}()\\})=(q,\\{\langle{\sf
Steal}_{1}():x\rangle,\ldots,\langle{\sf Steal}_{t}():x\rangle\\}).$

  4. (4)

$\delta(\epsilon,{\sf Take}())=(\epsilon,\langle{\sf Take}():{\sf
empty}\rangle).$

  5. (5)

$\delta(\epsilon,{\sf Steal}())=(\epsilon,\langle{\sf Steal}():{\sf
empty}\rangle).$

Let $\mathcal{A}$ be a linearizable algorithm for work-stealing with
multiplicity. Note that items 2 and 3 in Definition 3.1 and the definition of
set-linearizability directly imply that in every execution of $\mathcal{A}$,
the number of Take/Steal operations that take the same task is at most the
number of processes in the system, as the operations must be pairwise
concurrent to be set-linearized together. Furthermore, every _sequential_
execution of $\mathcal{A}$ looks like an “exact” solution for work-stealing,
as every operation is linearized alone, by definition of set-linearizability;
formally, every sequential execution of $\mathcal{A}$ is sequential execution
of (FIFO) work-stealing. We call this property _sequentially-exact_. Thus, in
the absence of contention, $\mathcal{A}$ provides an exact solution for work-
stealing.

###### Remark 3.1.

Every set-linearizable algorithm for work-stealing with multiplicity is
sequentially-exact.

###  3.1. Work-Stealing with Multiplicity from MaxRegister

Here we show that work-stealing with multiplicity can be reduced to
MaxRegister: a single wait-free linearizable MaxRegister object suffices to
wait-free set-linearizable solve work-stealing with multiplicity without
fences in all operations. Roughly speaking, the MaxRegister object
synchronizes the head of the queue. Therefore, there are fully Read/Write
algorithms for work-stealing with multiplicity as there are Read/Write wait-
free linearizable algorithms for MaxRegister. We also argue that using the
MaxRegister algorithm in (AAC12, ), the resulting work-stealing with
multiplicity algorithm has logarithmic step complexity and do not use Read-
After-Write synchronization patterns in Take and Steal. Section 4 shows that
the algorithm leads to fully fence-free Read/Write work-stealing algorithm
with constant step complexity in all its operations.

Figure 3 presents WS-MULT, a set-linearizable algorithm for work-stealing with
multiplicity. The algorithm is based on a single wait-free linearizable
MaxRegister object, which provides two operations: MaxRead that returns the
maximum value written so far in the object, and MaxWrite that writes a new
value only if it is greater than the largest value that has been written so
far.

Shared Variables: $Head:$ atomic MaxRegister object initialized to $1$
$Tasks[1,2,\ldots]:$ array of atomic Read/Write objects with the first two
objects initialized to $\bot$ Persistent Local Variables of the Owner:
$tail\leftarrow 0$ Operation ${\sf Put}(x)$: (01) $tail\leftarrow tail+1$ (02)
$\\{Tasks[tail].{\sf Write}(x),\ Task[tail+2].{\sf Write}(\bot)\\}$ (03)
return  true end Put Operation ${\sf Take}()$: (04) $head\leftarrow Head.{\sf
MaxRead}()$ (05) if $head\leq tail$ then (06) $\\{x\leftarrow Tasks[head].{\sf
Read}(),Head.{\sf MaxWrite}(head+1)\\}$ (07) return $x$ (08) end if (09)
return empty end Take Operation ${\sf Steal}()$: (10) $head\leftarrow
Head.{\sf MaxRead}()$ (11) $x\leftarrow Tasks[head].{\sf Read}()$ (12) if
$x\neq\bot$ then (13) $Head.{\sf MaxWrite}(head+1)$ (14) return $x$ (15) end
if (16) return empty end Steal

Figure 3. WS-MULT: a MaxRegister-based set-linearizable algorithm for work-
stealing with multiplicity.

In WS-MULT, the tail of the queue is stored in the local persistent variable
$tail$ of the owner, while the head is stored in the shared MaxRegister
$Head$. When the owner wants to put a new task, it first locally increments
$tail$ (Line 3) and then stores the task in the corresponding entry of $Tasks$
and marks one more entry with $\bot$ (Line 3); $\bot$ indicates lack of tasks.
Recall that the notation in Line 3 denotes that the instructions can be
executed in any order. When the owner wants to take a task, it first reads the
current head of the queue from $Head$ (Line 3) and then, if there are tasks
available (i.e. the head is less or equal that the tail), it reads the task at
the head, updates $Head$ and finally returns the task (Lines 3 and 3); if
there are no tasks available, the owner returns empty (Lines 3). When a thief
wants to steal a task, it first reads the current value of $Head$ (Line 3) and
then read that entry of $Tasks$ (Line 3). If it reads a task (i.e. a
non-$\bot$ value), it updates $Head$ and then returns the task (Lines 3 and
3). Otherwise, all tasks have been extracted and it returns empty (Line 3).

The semantics of MaxWrite guarantees that $Head$ contains the current value of
the head of the queue at all times, as a “slow” process cannot “move back” the
head by writing a smaller value in $Head$ (in Lines 3 or 3). Thus, the
MaxRegister $Head$ acts as a sort of barrier in the algorithm. The net effect
of this is that the only way that two Take/Steal operations return the same
task is because they are concurrent, reading the same value from $Head$.

Note that if only the first object in $Tasks$ is initialized to $\bot$ (and
hence Put is modified accordingly), it is possible that a thief reads an value
from $Tasks$ that has not been written by the owner: in an execution with a
single ${\sf Put}(x)$ operation, the steps in Line 3 could be executed
$Tasks[1].{\sf Write}(x)$ first and then $Task[2].{\sf Write}(\bot)$ with a
sequence of two Steal operations completing in between, hence the second
operations reading $Tasks[2]$ which has not been written yet by the owner,
which is a problem if $Tasks[2]$ contains a value distinct from non-$\bot$
value.

###### Theorem 3.2.

Algorithm WS-MULT is a set-linearizable wait-free fence-free algorithm for
work-stealing with multiplicity using atomic Read/Write objects and a single
atomic MaxRegister object. Moreover, all operations have constant step
complexity and Put is fully Read/Write.

###### Proof.

Clearly, the algorithm is wait-free as every operation requires a constant
number of steps to terminate, hence having constant step complexity, and
$Head$ is wait-free, by assumption. Observe that Put uses only Read/Write.
Moreover, the algorithm does not require any specific ordering among its
steps, beyond what is implied by data dependence, therefore it is fully fence-
free.

Before proving that WS-MULT is set-linearizible, we first observe that at any
time the thieves read the range of $Tasks$ that the owner has already
initialized; more specifically, every Steal operation reads from $Tasks$ (in
Line 3), a value that was written by the owner, either $\bot$ or a task.

At any time during an execution, the range $Tasks[Head,Head+1,\ldots,]$
contains a (possibly empty) sequence of tasks followed by at least one $\bot$
value, considering the entries in index-ascending order. The claim is true
initially as the first two entries if $Tasks$ are initialized to $\bot$. Every
time the owner stores a new task, it initializes a new entry of $Task$ to
$\bot$ (in Line 3); hence the claim holds at any time, as $Head$ is
incremented only if the owner or a thief sees that $Tasks[Head]$ contains a
non-$\bot$ value (in Lines 3 or 3). Note that the order of the instructions in
Line 3 is irrelevant.

We now prove that WS-MULT is set-linearizible. Consider any finite execution
$E$ of it. Since we already argued that the algorithm is wait-free, there is a
finite extension of $E$ in which all its operations are completed and no new
operations starts. Thus, we can assume that there are no pending operations in
$E$.

First, note that the semantics of MaxWrite implies that there is no pair of
non-concurrent Take/Steal operation that return the same task: if the two
operation are not concurrent, then the first one increments the value of
$Head$ (and this value can only increment), and hence the second cannot read
the same tasks from $Tasks$. Thus, we have:

###### Remark 3.2.

If a task that is returned by more than one Take/Steal operation, then these
operations are pairwise concurrent. Thus, two distinct Take operations of the
owner cannot return the same task.

The main observation for the set-linearizability proof is that at any time
during the execution, the state of the object is represented by the tasks in
the range $Tasks[Head,Head+1,\ldots]$, i.e. the sequence of non-$\bot$ values
(in index-ascending order) that written by the owner in that range. The set-
linearization ${\sf SetLin}(E)$ of $E$ is obtained as follows:

  * •

Every Put operation is set-linearized _alone_ (i.e. in a concurrency class
containing only the operation) placed at its step corresponding to
$Tasks[tail].{\sf Write}(x)$ in $E$ (Line 3).

  * •

For every task that is returned by at least one Take/Steal operation, all
these operations are set-linearized in the same concurrency class placed at
the first step $e$ in $E$ that corresponds to $Head.{\sf MaxWrite}(head+1)$
(either in Line 3 or 3) among the steps of the operations. Note that that $e$
occurs between the invocation and response of every operation in the
concurrency class: since the operations return the same task, all of them
execute the MaxRead steps in Lines 3 or 3 before $e$, and, by definition, $e$
appears in $E$ before any other operation executes its step corresponding to
$Head.{\sf MaxWrite}(head+1)$. Observe that the order in which the
instructions in Line 3 is executed is irrelevant.

  * •

Every Take operation returning empty is set-linearized alone, placed at its
step in $E$ corresponding to $Head.{\sf MaxRead}()$ (Line 3).

  * •

Every Steal operation returning empty is set-linearized alone, placed at its
step in $E$ corresponding to $Head.{\sf MaxRead}()$ (Line 3).

Every concurrency class of ${\sf SetLin}(E)$ is placed at a step of $E$ that
lies between the invocation and response of each operation in the concurrency
class, which immediately implies that ${\sf SetLin}(E)$ respects the partial
order $<_{E}$ of $E$. Thus, to conclude that ${\sf SetLin}(E)$ is a set-
linearization of $E$, we need to show that it is indeed a set-sequential
execution of the work-stealing with multiplicity.

First, note that a task can be extracted by a Take/Steal operation only if the
Put operation that stores the task executes its step corresponding to
$Tasks[tail].{\sf Write}(x)$ (in Line 3) before the Take/Steal operation reads
the entry of $Tasks$ where the task is stored. Thus, in ${\sf SetLin}(E)$
every task is inserted before it is extracted.

Now, Put stores tasks in $Tasks$ in index-ascending order. Due to the
semantics of MaxRegister, $Head$ never “moves back”, i.e. it only increments
one by one, and hence Take and Steal extract tasks in index-ascending order
too. It follows that tasks in ${\sf SetLin}(E)$ are inserted/extracted in FIFO
order. More specifically, for any concurrency class $C$ of ${\sf SetLin}(E)$
with Take/Steal operations that return the same tasks $x$, right before the
step $e$ of $E$ where $C$ is set-linearized, we have that $x$ is task with
smallest index (left-most) in the range $Tasks[Head,Head+1,\ldots]$, and thus
indeed the operations in $C$ get the oldest task in the object.

It only remains to be argued that any Take/Steal operation that returns empty,
does so correctly, i.e., each of this operations are set-linearized at a step
of $E$ at which $Tasks[Head,Head+1,\ldots]$ is empty, i.e. all its entries
initialized by the owner in that range contain $\bot$.

Consider any Take operation in $E$ that returns ${\sf empty}$. Observe that
this can happen only if the owner sees that $head>tail$, namely the
conditional is not satisfied in Line 3. Clearly, this is possible only when no
item has been inserted at all or when all items have been extracted, and hence
$Tasks[Head,Head+1,\ldots]$ is empty. Consider now any Steal operation in $E$
that returns ${\sf empty}$. This is possible only the thief reads $\bot$ from
$Tasks$ in Line 3, and since we already argued that the owner insert tasks in
ascending order, we have that at that time $Tasks[Head,Head+1,\ldots]$ is
empty.

We conclude that ${\sf SetLin}(E)$ is a valid set-sequential execution of
work-stealing with multiplicity, and as it respects the partial order $<_{E}$
of $E$, we have that it is a set-linearization of $E$, and therefore WS-MULT
is set-linearizable. The theorem follows. ∎

When we replace $Head$ with the wait-free linearizable Read/Write MaxRegister
algorithm in (AAC12, ), whose step complexity is $O(\log m)$, where $m\geq 1$
is the maximum value that can be stored in the object, the step complexity of
WS-MULT is bounded wait-free with logarithmic step complexity too. In the
resulting algorithm at most $m$ tasks can be inserted. Since the algorithm in
(AAC12, ) do not use Read-After-Write synchronization patterns, the resulting
algorithm does not uses those patterns either.

###### Theorem 3.3.

If $Head$ is an instance of the wait-free linearizable Read/Write MaxRegister
algorithm in (AAC12, ), WS-MULT is linearizable and fully Read/Write with Take
and Steal having step complexity $O(\log m)$, where $m$ denotes the maximum
number or tasks that can be inserted in an execution. Furthermore, Take and
Steal do not use Read-After-Write synchronization patterns.

###### Proof.

The algorithm remains linearizable, by composability of linearizability (HW90,
). While the step complexity of Put is clearly $O(1)$, the step complexity of
Take and Steal is $O(\log m)$ as the step complexity MaxRead and MaxWrite of
the MaxRegister algorithm in (AAC12, ) is $O(\log m)$.

We now argue that Take and Steal do not use Read-After-Write synchronization
patterns. The reason is that the MaxRegister algorithm in (AAC12, ) does not
use this synchronization mechanism. Roughly speaking, the algorithm consists
of a binary tree of height $O(\log m)$ with an atomic bit in each of its
nodes. When a process wants to perform MaxRead, it reads the bits in a path of
the tree from the root to a leaf and then returns a value, according to the
leaf it reached; the next node in the path the process reads depends on the
value of the current node. When a process wants to perform MaxWrite, it reads
the bits in a path from the root to a leaf, which is on function of the binary
representation of the value the process wants to write; then, if the new value
is larger than the current one, in a bottom-up manner, it writes 1 in every
node in the path with 0 (for the algorithm to be linearizable, the writes
should occur in this order). Thus, we have that MaxRead consists of a sequence
of reads and MaxWrite consists of a sequence of reads followed by a (possibly
empty) sequence of writes. Therefore, Take/Steal of WS-MULT consists of a
sequence of reads followed by a (possibly empty) sequence of writes, and thus
the operation does not use Read-After-Write synchronization patterns. ∎

##  4\. Work-Stealing with Weak Multiplicity

In the context of work-stealing, a logarithmic step complexity of the Take
operation may be prohibitive in practice. Ideally, we would like to have
constant step complexity, in all operations if possible, and using simple
synchronization mechanisms of course. In this section, we propose a variant of
work-stealing with multiplicity, which admits fully Read/Write fence-free
implementations with constant step complexity in all its operations.
Intuitively, the variant requires that every task is extracted at least once,
but now every process extracts a task _at most once_ , hence Take/Steal
operations returning the same task _may not_ be concurrent. Therefore, the
relaxation retains the property that the number of operations that can extract
the same task is at most the number of processes in the system. We call this
relaxation work-stealing with _weak_ multiplicity.

Figure 4. A schematic view of work-stealing with weak multiplicity.

Figure 4 depicts a schematic view of a state of work-stealing with weak
multiplicity. Intuitively, at any state, each process has its own queue of
tasks. When the owner inserts a new task, it concurrently places the task in
all queues, as shown in the figure. Therefore, in any state, for any pair of
process’ queues, one of them is suffix of the other. A Take/Steal operation
can return any task from its queue that is no “beyond” the first task of the
_shortest_ queue in the state. In the example, a Steal operation of thief
$p_{1}$, denoted ${\sf Steal}_{1}()$, can return only $x$, as $p_{1}$ has the
shortest queue in the state, while a Take operation of the owner can return
any task in $\\{u,v,w,x\\}$, which contains any task from the beginning of its
queue up to $x$.

Figure 5. A sequential execution of work-stealing with weak multiplicity.

Figure 5 shows an example of a sequential execution of work-stealing with weak
multiplicity; note that Take/Steal operations are allowed to get the same
item, although they are not concurrent.

The next _sequential_ specification formally defines work-stealing with weak
multiplicity. Without loss of generality, the specification assumes, that
$p_{0}$ is the owner, and each invocation/response of thief $p_{i}$ is
subscripted with its index, which then belongs to $\\{1,\ldots,n-1\\}$.

###### Definition 4.1 ((FIFO) Work-Stealing with Weak Multiplicity).

The universe of tasks that the owner can put is $\mathbf{N}=\\{1,2,\ldots\\}$,
and the set of states $Q$ is the infinite set of $n$-vectors of finite strings
$\mathbf{N}^{*}\times\ldots\times\mathbf{N}^{*}$, with the property that for
any two pairs of strings in a vector, one of them is a _suffix of the other_.
The initial state is the vector with empty strings,
$(\epsilon,\ldots,\epsilon)$. The transitions are the following:

  1. (1)

$\forall(t_{0},\ldots,t_{n-1})\in Q,\delta((t_{0},\ldots,t_{n-1}),{\sf
Put}(x))=((t_{0}\cdot x,\ldots,t_{n-1}\cdot x),\langle{\sf Put}(x):{\sf
true}\rangle).$

  2. (2)

$\forall(t_{0},\ldots,t_{n-1})\in Q$ such that $t_{0}=x_{1}\cdots x_{j}\cdot
q\neq\epsilon$ with $j\geq 1$ and $x_{j}\cdot q$ being the shortest string in
the state (possibly with $x_{j}\cdot q=\epsilon$),
$\delta((t_{0},\ldots,t_{n-1}),{\sf
Take}())=\\{((\widehat{t}_{0},t_{1},\ldots,t_{n-1}),\langle{\sf
Take}():x_{k}\rangle)\\}$, where $k\in\\{1,\ldots,j\\}$ and
$\widehat{t}_{0}=x_{k+1}\cdots x_{j}\cdot q$.

  3. (3)

$\forall(t_{0},\ldots,t_{n-1})\in Q$ such that $t_{i}=x_{1}\cdots x_{j}\cdot
q\neq\epsilon$ with $j\geq 1$, $i\in\\{1,\ldots,n-1\\}$ and $x_{j}\cdot q$
being the shortest string in the state (possibly with $x_{j}\cdot
q=\epsilon$), $\delta((t_{0},\ldots,t_{n-1}),{\sf
Steal}_{i}())=\\{((t_{0},\ldots,t_{i-1},\widehat{t}_{i},t_{i+1},\ldots,t_{n-1}),\langle{\sf
Steal}_{i}():x_{k}\rangle)\\}$, where $k\in\\{1,\ldots,j\\}$ and
$\widehat{t_{i}}=x_{k+1}\cdots x_{j}\cdot q$.

  4. (4)

$\forall(\epsilon,t_{1},\ldots,t_{n-1})\in Q$,
$\delta((\epsilon,t_{1},\ldots,t_{n-1}),{\sf
Take}())=((\epsilon,t_{1},\ldots,t_{n-1}),\langle{\sf
Take}():\epsilon\rangle).$

  5. (5)

$\forall(t_{0},\ldots,t_{i-1},\epsilon,t_{i+1},\ldots,t_{n-1})\in Q$ with
$i\in\\{1,\ldots,n-1\\}$,$\delta((t_{0},\ldots,t_{i-1},\epsilon,t_{i+1},\ldots,t_{n-1}),{\sf
Steal}_{i}())=\\\
((t_{0},\ldots,t_{i-1},\epsilon,t_{i+1},\ldots,t_{n-1}),\langle{\sf
Steal}_{i}():\epsilon\rangle).$

Observe that the second and third items in Definition 4.1 correspond to non-
deterministic transitions in which a Take/Steal operation can extract any task
of $\\{x_{1},\ldots,x_{j}\\}$; the value returned can be $\epsilon$ when the
shortest string in the state ($x_{j}\cdot q^{\prime}$ in the definition) is
$\epsilon$. Furthermore, the definition guarantees that every task is
extracted at least once because every Take/Steal operation can only return a
task that is not “beyond” the first task in the shortest string of the state.

The specification work-stealing with concurrent multiplicity is nearly
trivial, with solutions requiring almost no synchronization. A simple solution
is obtained by replacing $Head$ in WS-MULT with one local persistent variable
$head$ per process (each initialized to 1); Put remains the same and Take and
Steal instead of reading from $Head$, they just locally read the current value
of $head$ and increment it whenever a task is taken. It is not hard to verify
that the resulting algorithm is indeed linearizable.

To avoid this kind of simple solutions (which would very inefficient in
practice as every process is processing every task), we restrict our attention
to sequentially-exact algorithms, namely, every sequential execution of the
algorithm is a sequential execution of the specification of (FIFO) work-
stealing.222Alternatively, work-stealing with weak multiplicity can be
specified using the interval-linearizability formalism in (CRR18, ), which
allows us to specify that a Take/Steal operation can exhibit a non-exact
behavior only in presence of concurrency. Interval-linarizability would
directly imply that any interval-linearizable solution provides a exact
solution in sequential executions. Roughly speaking, in interval-
linearizability, operations are linearized at intervals that can overlap each
other. It is easy to see that the algorithm described above does not have this
property.

Finally, we stress that, differently from work-stealing with multiplicity, two
distinct non-concurrent Take/Steal can extract the same task in an execution,
which can happens only if _some_ operations are concurrent in the execution,
due to the sequentially-exact requirement. Particularly, in our algorithms,
this relaxed behaviour can occurs when processes are concurrently updating the
head of the queue.

###  4.1. Fully Read/Write Fence-Free Work-Stealing with Multiplicity

In this subsection we present WS-WMULT, a fully Read/Write fence-free
algorithm for work-stealing with weak multiplicity. The algorithm is obtained
by replacing the atomic MaxRegister object in WS-MULT, $Head$, with an atomic
RangeMaxRegister object, a relaxation of MaxRegister with a RMaxRead operation
that returns a value in a _range_ of values that have been written in the
register; the range always includes the maximum value written so far.

We present a RangeMaxRegister algorithm that is nearly trivial, however, it
allows us to solve work-stealing with weak multiplicity in an efficient
manner, with implementations exhibiting good performance in practice, as we
will see in Section 8. As above, to avoid trivial solutions, we focus on
sequentially-exact linearizable algorithms for RangeMaxRegister with each of
its sequential executions being a sequential execution of MaxRegister.
333Again, this can be alternatively specified through interval-
lineiarizability. When WS-WMULT is combined with this algorithm, it becomes
fully Read/Write, fence-free, linearizable, sequentially-exact and wait-free
with constant step complexity.

Intuitively, in RangeMaxRegister, each process has a _private_ MaxRegister and
whenever it invokes RMaxRead, the result lies in the range defined by the
value of its private MaxRegister and the maximum among the values of the
private MaxRegisters in the state. In the sequential specification of
RangeMaxRegister, each invocation/response of process $p_{i}$ is subscripted
with its index $i$.

###### Definition 4.2 (RangeMaxRegister).

The set of states $Q$ is the infinite set of $n$-vectors with natural numbers,
with vector $(1,\ldots,1)$ being the initial state. The transitions are the
following:

  1. (1)

$\forall(r_{0},\ldots,r_{n-1})\in Q$ and $i\in\\{0,\ldots,n-1\\}$, if
$x>r_{i}$,
$\delta((r_{0},\ldots,r_{n-1}),\ {\sf
RMaxWrite}_{i}(x))=((r_{0},\ldots,r_{i-1},x,r_{i+1},\ldots,r_{n-1}),\langle{\sf
RMaxWrite}_{i}(x):{\sf true}\rangle),$
otherwise
$\delta((r_{0},\ldots,r_{n-1}),{\sf
RMaxWrite}(x))=((r_{0},\ldots,r_{n-1}),\langle{\sf RMaxWrite}(x):{\sf
true}\rangle).$

  2. (2)

$\forall(r_{0},\ldots,r_{n-1})\in Q$ and $i\in\\{0,\ldots,n-1\\}$,
$\delta((r_{0},\ldots,r_{n-1}),{\sf RMaxRead}_{i}())=\\\
\\{((r_{0},\ldots,r_{i-1},x,r_{i+1},\ldots,r_{n-1}),\langle{\sf
RMaxRead}_{i}():x\rangle)\\},$ where
$x\in\\{r_{i},r_{i}+1,\ldots,\max(r_{0},\ldots,r_{n-1})\\}$.

As already mentioned, WS-WMULT is the algorithm obtained by replacing $Head$
in WS-MULT with an atomic RangeMaxRegister object initialized to 1 (hence
MaxRead and MaxWrite are replaced by RMaxRead and RMaxWrite, respectively).

###### Theorem 4.3.

Algorithm WS-WMULT is a linearizable wait-free fence-free algorithm for work-
stealing with weak multiplicity using atomic Read/Write objects and a single
atomic RangeMaxRegister object. Moreover, all operations have constant step
complexity and Put is fully Read/Write.

###### Proof.

Clearly, all operations of the algorithm are wait-free since each of them
requires a constant number of steps to terminate, hence having constant step
complexity, and $Head$ is wait-free, by assumption. Note that Put uses only
Read/Write. The algorithm does not require any specific ordering among its
steps, beyond what is implied by data dependence, therefore it is fully fence-
free.

As in the proof of Theorem 3.2, it can be argued that thieves read values from
$Tasks$ that have been written by the owner.

Consider any finite execution $E$ of the algorithm. Since the algorithm is
wait-free, there is a finite extension of $E$ in which all its operations are
completed and no new operations starts. Thus, we can assume that there are no
pending operations in $E$.

Proving that $E$ is linearizable is quite straightforward. It is enough to
observe that, at any step of $E$, the state of the object is encoded in the
state of $Head$. Let $(r_{0},\ldots,r_{n-1})$ be the state of $Head$ at a
given step of $E$. Then, the state of the object is $(t_{0},\ldots,t_{n-1})$
with each $t_{i}$ being the finite sequence of tasks in the range
$Tasks[r_{i},r_{i+1},\ldots]$ (i.e. the sequence of non-$\bot$ values written
by the owner, in index-ascending order). Thus, in a linearization of $E$, a
${\sf Put}(x)$ operation is linearized at its step $Tasks[tail].{\sf
Write}(x)$ in Line 3, while a Take/Steal operation is linearized at its step
$Head.{\sf RMaxRead}()$ in Line 3/Line 3 (observe that the non-deterministic
choice in a transition with a Take/Steal operation is resolved with the
outcome of RMaxRead). Therefore, we conclude that every execution of WS-WMULT
is linearizable, and thus the algorithm is linearizable too. ∎

Shared Variables: $R:$ atomic Read/Write object initialized to 1 Persistent
Local Variables of a Process: $r\leftarrow 1$ Operation ${\sf RMaxWrite}(x)$:
(01) $r\leftarrow\max\\{r,R.{\sf Read}()\\}$ (02) if $x>r$ then (03)
$\\{r\leftarrow x,R.{\sf Write}(x)\\}$ (04) end if (05) return  true end
RMaxWrite Operation ${\sf RMaxRead}()$: (06) $r\leftarrow\max\\{r,R.{\sf
Read}()\\}$ (07) return $r$ end RMaxRead

Figure 6. A linearizable wait-free algorithm for RangeMaxRegister.

Figure 6 contains a simple linearizable sequentially-exact wait-free algorithm
for RangeMaxRegister. All processes share a single Read/Write object $R$ and
each process has a local persistent variable $r$. The idea is very simple:
each process locally stores in $r$ the maximum value it is aware of; whenever
it discover a new largest value in RMaxWrite, it writes it in $r$ and $R$ and
since $R$ might not have the largest value, it returns the maximum among $r$
and $R$ in RMaxRead.

###### Theorem 4.4.

The algorithm in Figure 6 is a linearizable sequen-tially-exact wait-free
fence-free algorithm for RangeMaxRegister using only atomic Read/Write objects
and with constant step complexity in all its operations.

###### Proof.

It is clear form its pseudocode that the algorithm is fully Read/Write, wait-
free and fence-free, and each operations has constant step complexity.

Consider any finite execution $E$ of the algorithm. Since the algorithm is
wait-free, there is a finite extension of $E$ in which all its operations are
completed and no new operations starts. Thus, we can assume that there are no
pending operations in $E$.

To prove linearizability, it is enough to observe that at any step of $E$, the
state of the object is $(r_{0},\ldots,r_{n-1})$, where $r_{i}$ is the value
stored in the local persistent variable $r$ of process $p_{i}$ at that moment.
Thus, a ${\sf RMaxWrite}(x)$ operation with $x>r$ (hence the conditional in
Line 7 is true) is linearized at its step $R.{\sf Write}(x)$ in Line 7; if
$x\leq r$, the operation is linearized at is invocation. A ${\sf RMaxRead}()$
operation is linearizaed at its step $R.{\sf Read}()$ in Line 7; note that the
operation returns a value between the value in $r$ before Line 7 and the
maximum among the $r$’s local variables, since that is the maximum value $R$
can store at that time. Thus the algorithm is linearizable.

Suppose now that $E$ is sequential. By induction of the number of operations,
it is easy to show that $R$ contains the maximum value, at all time. Thus, $E$
is indeed a sequential execution of MaxRegister, and therefore the algorithm
is sequentially-exact. The theorem follows. ∎

We now are able to present our main result:

###### Theorem 4.5.

If $Head$ is an instance of the algorithm in Figure 6, WS-WMULT is fully
Read/Write, fence-free, wait-free, sequentially-exact and linearizable with
constant step complexity in all its operations.

###### Proof.

By composability of linearizability (HW90, ), the algorithm remains
linearizable. The algorithm is fully Read/Write and wait-free because Put uses
only Read/WS-MULT and the RangeMaxRegister algorithm in Figure 6 is fully
Read/Write and wait-free, by Theorem 4.4. Clearly, the step complexity of Put
is $O(1)$. The step complexity of Take and Steal is $O(1)$ too because the
RangeMaxRegister algorithm in Figure 6 has constant step complexity. The
resulting algorithm does not require any specific ordering among its steps,
beyond what is implied by data dependence, therefore it is fully fence-free.
Consider a sequential execution of the algorithm. By Theorem 4.4, the
algorithm in Figure 6 behaves like a MaxRegister, and hence the execution
corresponds to a sequential execution of WS-MULT (exchanging RMaxRead and
RMaxWrite with MaxRead and MaxWrite, respectively), which in turn is a
sequential execution of work-stealing, since WS-MULT is sequentially-exact, by
Remark 3.1 and Theorem 3.2. Thus, the algorithm is sequentially exact. The
theorem follows. ∎

Shared Variables: $Head:$ atomic Read/Write object initialized to 1
$Tasks[1,2,\ldots]:$ array of atomic Read/Write objects with the first two
objects initialized to $\bot$ Persistent Local Variables of the Owner:
$head\leftarrow 1$ $tail\leftarrow 0$ Persistent Local Variables of a Thief:
$head\leftarrow 1$ Operation ${\sf Put}(x)$: (01) $tail\leftarrow tail+1$ (02)
$\\{Tasks[tail].{\sf Write}(x),\ Tasks[tail+2].{\sf Write}(\bot)\\}$ (03)
return  true end Put Operation ${\sf Take}()$: (04)
$head\leftarrow\max\\{head,Head.{\sf Read}()\\}$ (05) if $head\leq tail$ then
(06) $\\{x\leftarrow Tasks[head].{\sf Read}(),Head.{\sf Write}(head+1)\\}$
(07) $head\leftarrow head+1$ (08) return $x$ (09) end if (10) return empty end
Take Operation ${\sf Steal}()$: (11) $head\leftarrow\max\\{head,Head.{\sf
Read}()\\}$ (12) $x\leftarrow Tasks[head].{\sf Read}()$ (13) if $x\neq\bot$
then (14) $Head.{\sf Write}(head+1)$ (15) $head\leftarrow head+1$ (16) return
$x$ (17) end if (18) return empty end Steal

Figure 7. WS-WMULT algorithm with the RangeMaxRegister algorithm in Figure 6
inlined.

Figure 7 contains an optimized WS-WMULT algorithm with the RangeMaxRegister
algorithm in Figure 6 inlined. Since Take and Steal first RMaxRead from and
then RMaxWrite to $Tail$, the algorithm remains sequentially-exact when
removing Line 6 of RMaxWrite in Figure 6. Our experimental evaluation in
Section 8 tested implementations of this algorithm.

##  5\. Bounding the Multiplicity

Here we discuss simple variants of our algorithms that bound the number of
operations that can extract the same task. More in detail, with the addition
of a single Swap instruction in Steal, the modified algorithms guarantee that
no two distinct Steal operations take the same task (however, a Take and a
Steal can take the same task).

We only discuss the case of WS-MULT as the variant for WS-WMULT is the same.
The modification consists in having an array $A$ of the same length of
$Tasks$, with each entry initialized to true. After Line 3, a thief performs
$A[head].{\sf Swap}({\sf false})$, and it executes Lines 3 and 3 only if the
Swap successfully takes the true value in $A[head]$; otherwise, it increments
$head$ and goes to Line 3 to start over. Therefore, Steal is only nonblocking
in the modified algorithm. This _bounded_ variant of WS-MULT is denoted B-WS-
MULT.

The set-linearization proof of B-WS-MULT is almost the same, with the
difference that for every task that is stored in $Tasks[r]$ and is returned by
one or two Take/Steal operations, the operations are set-linearized in the
same concurrency class placed at the first step $e$ in $E$ that executes
$Head.{\sf MaxWrite}(head+1)$, in case of Take (as in the proof of Theorem
3.2), or $A[r].{\sf Swap}(\top)$, in case of Steal.

##### Removing Multiplicity

The Take operation of WS-MULT can be modified similarly to obtain solutions
for exact (FIFO) work-stealing. The modification consists in using the array
$A$ mentioned above. After Line 3, the owner performs $A[head].{\sf Swap}({\sf
false})$, and it executes Lines 3 and 3 only if the Swap successfully takes
the true value in $A[head]$; otherwise, it increments $head$ and goes to Line
3 to start over.

##  6\. Implementing Arrays of Infinite Length

So far we have presented our algorithms using an infinite length array where
the tasks are stored. In this section we discuss two approaches to implement
our algorithms using arrays of finite length; both approaches have been used
in previous algorithms (e.g. (AF20, ; AKY10, ; MlVS09, ; HLMS06, ; YM16, )).
We only discuss the case of WS-MULT as the other cases are handled in the same
way. The two approaches are the following:

  1. (1)

In the first approach, the algorithm starts with $Tasks$ pointing to an array
of finite fixed length, with its two first objects initialized to $\bot$; each
time the owner detects the array is full (i.e. when $tail$ is larger the
length $Tasks$), in the middle of a Put operation, it creates a new array $A$,
duplicating the previous length, copies the previous content to $A$,
initializes the next two objects to $\bot$, points $Tasks$ to $A$ and finally
continues executing the algorithm. Although the modified Put operation remains
wait-free, its step complexity is unbounded.

  2. (2)

In the second approach, $Tasks$ is implemented with a linked list with each
node having a fixed length array. Initially, $Tasks$ consists of a single
node, with the first two objects of its array initialized to $\bot$. When the
owner detects that all entries in the linked list have been used, in the
middle of a Put operation, it creates a new node, initializes the first two
objects to $\bot$, links the new node to the end of the list and continues
executing the algorithm. An index of $Tasks$ is now made of a tuple: a pointer
to a node of the linked list and an node-index array. Thus, any pair of nodes
can be easy compared (first pointer nodes, then node-indexes) and incrementing
an index can be easily performed too (if the node-index is the last one, the
pointer moves forward and the node-index is set to one, otherwise only the
node-index is incremented). The modified Put operation remains wait-free with
constant step complexity.

Our experimental evaluation in Section 8 shows the second approach performs
better than the first one when solving a problem of concurrent nature.

##  7\. Idempotent $\neq$ Multiplicity

Idempotent work-stealing is (only) informally defined in (MlVS09, ) as: every
task is extracted _at least once_ , instead of _exactly once_ (in some order).
Three idempotent work-stealing algorithms are presented in (MlVS09, ),
inserting/extracting tasks in FIFO and LIFO order, and as a double-ended queue
(the owner puts in and takes from one side and the thieves steal from the
other side).

Figure 8. Idempotent FIFO work-stealing (MlVS09, ).

Here we explain that these algorithms does not implement work-stealing with
multiplicity, neither its non-concurrent variant. While in our relaxations
every process extracts a task at most once, and hence the number of distinct
operations that extract the same task is at most the number of processes in
the system, in idempotent work-stealing a task can be extracted an unbounded
number of times, and moreover, a thief can extract the same task an unbounded
number of times.

Figure 8 depicts the FIFO idempotent work-stealing algorithm in (MlVS09, ).
The algorithm stores the tasks in a shared array $tasks$ and shared integers
$head$ and $tail$ indicate the positions of the head and the tail. For every
integer $z>0$, we describe an execution of the algorithm in which, for every
$k\in\\{1,\ldots,z\\}$, there is a task that is extracted by $\Theta(k)$
distinct operations (possibly by the same thief), with only one of them being
concurrent with the others.

  1. (1)

Let the owner execute alone $z$ times Put. Thus, there are $z$ distinct tasks
in $tasks$

  2. (2)

Let $r=z$.

  3. (3)

The owner executes Take and stops before executing Line 5, i.e. it is about to
increment $head$.

  4. (4)

In some order, the thieves sequentially execute $r$ Steal operations; note
these Steal operations return the $r$ tasks in $tasks[0,\ldots,r-1]$.

  5. (5)

We now let the owner increment $head$. If $r>1$, go to step 3 with $r$
decremented by one, else, end the execution.

Observe that in the execution just described, the task in $tasks[i]$,
$i\in\\{0,\ldots,z-1\\}$, is extracted by a Take operation and by $i+1$
distinct non-concurrent Steal operations (possible by the same thief). Thus,
the task is extracted $\Theta(i)$ distinct times. Since $z$ is any positive
integer, we conclude that there is no bound on the number of times a task can
be extracted.

A similar argument works for the other two idempotent work-stealing algorithms
in (MlVS09, ). In the end, this happens in all algorithms because tasks are
not marked as taken in the shared array where they are stored. Thus, when the
owner takes a task and experience a delay before updating the head/tail, all
concurrent modifications of the head/tail performed by the thieves are
overwritten once the owner completes its operation, hence leaving all taken
tasks ready to be taken again.

##  8\. Experiments

In this section we discuss the outcome of the experiments we have conducted to
evaluate the performance of implementations of WS-WMULT and its bounded
version, B-WS-WMULT (see Section 5). Based on the approaches discussed in
Section 6, we implemented two versions of the algorithm, one using arrays and
another using linked lists. We mainly discuss the results of the version based
on linked lists, since it exhibited better performance than the version based
on arrays. WS-WMULT and B-WS-WMULT were compared to the following algorithms:
THE Cilk (CL05, ), Chase-Lev (FLR98, ), and the three Idempotent Work-Stealing
algorithms (MlVS09, ).

###  8.1. Platform and Environment

The experiments were executed in two machines with distinct characteristics.
The first machine has an Intel Kaby Lake processor (i7–7700HQ, with four cores
where each core has two threads of execution) and 16GB RAM. This machine was
dedicated only to the experiments. The second one is a cluster with four Intel
Xeon processors (E7–8870 v3 processor, with 18 cores where each core has two
threads of execution) and 3TB RAM. This machine was shared with other users,
where the process executions are closer to a usual situation, namely,
resources (CPU and memory) are shared by all user. We will focus mainly on the
results of the experiments in the Core i7 processor, and additionally will use
the results of the experiments in Intel Xeon to complement our analysis. The
algorithms were implemented in the Java platform (OpenJDK 1.8.0_275) in order
to test them in a cross-platform computing environment.

###  8.2. Methodology

To analyze the performance of the algorithms, we divided the analysis into the
next two benchmarks, which have been used in (FLR98, ; MlVS09, ; MA14, ):

  * •

Zero cost experiments. We test the performance of executing only the methods
provided by the algorithms. Thus, we compare the time taken by each algorithm
when performing the same set of tasks without being used as support for other
algorithms. In our experiments, we test the time required for executing by
Put-Take and Put-Steal operations

  * •

Irregular graph application. We test the performance of solving a challenging
graph problem, computing a spanning tree, where the goal is to speed up the
computation via parallel exploration of the graph.

Below, we explain in detail how we implement each benchmark.

##### Zero cost experiments

We measure the time required for performing a sequence of operations provided
by the work-stealing algorithms. We measure the time needed for Put-Take
operations, where the owner performs a sequence of Put operations followed by
an equal number of Takes. Differently from (MlVS09, ; MA14, ), we also measure
the time for Put-Steal operations. In both experiments, The number of Put
operations is $10,000,000$, followed by the same number of Take or Steal
operations; no operation performs any work associated to a task.

##### Irregular graph application

We consider the spanning-tree problem to evaluate the performance of each
algorithm. It is measured the speed up of the computation by the parallel
exploration of the input graph. This problem is used in (MlVS09, ; MA14, ) to
evaluate their work-stealing algorithms. We refer the reader to (BaderC04, )
for a detailed description of the algorithm. The spanning tree algorithm
already uses a form of work-stealing to ensure load-balancing, and we adapted
it to work with our work-stealing implementations. Further, the algorithms
were tested on many types of directed and undirected graphs:

  * •

Regular and irregular meshes

    * –

2D Torus: The vertices are on a 2D mesh, where each vertex has a connection to
its four neighbors in the mesh.

    * –

2D60 Torus: It is a random graph obtained from the previous one, where each
edge has a probability of 60% to be present.

    * –

3D Torus: The vertices are on a 3D mesh, where each vertex has a connection to
its six neighbors in the mesh.

    * –

3D40 Torus: It is a random graph obtained from the previous one where each
edge has a probability of 40% to be present.

  * •

Random: Random graph of $n$ vertices and $m$ edges, by randomly adding $m$
unique edges to the vertex set.

All graphs are represented using the adjacency lists representation. The
graphs were built with 1,000,000 of vertices for tests in core i7 and
2,000,000 for tests in Intel Xeon.

Each experiment consists of the following: take one of the previous graphs,
specify its parameters and run the spanning-tree algorithm with one of the of
the work-stealing algorithms (THE Cilk, Chase-Lev, Idempotent FIFO, Idempotent
LIFO, Idempotent DEQUE, WS-WMULT or B-WS-WMULT); the spanning tree algorithm
is executed five times with each work-stealing algorithm, using the same root
and the same graph. In each execution, it is tested the performance obtained
by increasing the number of threads from one to the total supported by the
processor, registering the duration of every execution.

For each work-stealing algorithm and number of threads, the fastest and
slowest executions are discarded, and the average of the remaining three is
calculated. All results are normalized with respect to Chase-Lev with a single
thread, as in (MlVS09, ; MA14, ).

##### Initial length of arrays

We did both experiments with distinct initial length of arrays in the array-
based algorithms, and distinct lengths of node-array in the linked-list
versions of our algorithms. The lengths we tried were $256$, $4096$, $32768$,
$100000$, $250000$, $500000$ and $1,000,000$. The performance of the
algorithms decreased with large initial lengths but the relative speedup among
the algorithms did not change. Below we discuss the results of the experiments
with arrays of length 256.

###  8.3. Results

We present a summary of the results before explaining them in detail:

##### Zero cost experiments

  1. (1)

WS-WMULT shows a slightly better performance than Idempotent FIFO in the Put-
Take experiment. This is expected as both algorithms are similar in their
Put/Take operations, with Idempotent FIFO using non-costly fences. Both
algorithms are the ones with the best performance in this experiment. However,
WS-WMULT exhibited better performance in Put-Steal experiment. This happens
due to the fact that the Steal operation of any other algorithm uses costly
primitives, like Compare&Swap or Swap.

  2. (2)

B-WS-WMULT has the worst performance among all algorithms in the Put-Steal
experiment, due to the management of the additional array for marking a task
as taken. However, this result does not precludes the algorithm for exhibiting
a competitive performance in the next benchmark.

##### Irregular graph application

  1. (1)

In general WS-WMULT has better performance than any other algorithms and in
particular it performed better than Idempotent FIFO444We stress the comparison
with respect to Idempotent FIFO, as both algorithms insert/extract tasks in
the same order. in virtually all cases.

  2. (2)

B-WS-WMULT has a lower performance than WS-WMULT but still competitive respect
to Idempotent algorithms.

Below we discuss in detail the results of the zero cost experiments and the
irregular graph application, in both cases omitting the results of THE Cilk
because its performance was similar to that of Chase-Lev. Similarly, we omit
the results of Idempotent DEQUE since in general it had the worst performance
among the Idempotent algorithms.

##### Zero cost experiments

Figure 9a depicts the result of the Put-Take experiment in the Intel Core i7
processor. The results of THE Cilk and the idempotent algorithms are similar
than those presented (MlVS09, ). As for WS-WMULT, the time required for Put
operations was similar than that of Idempotent LIFO, and slightly faster than
Idempotent FIFO. Considering the whole experiment, WS-WMULT was faster than
any other algorithm.

The results show a significant speed-up, where the gain is about 21.9% respect
to Chase-Lev, 12.5% respect Idempotent FIFO and 6% respect to Idempotent LIFO.

For the case of B-WS-WMULT, it required about twice the time of any other
algorithm. This poor performance is due to the use of an extra boolean array
for bounding multiplicity. Particularly, the Put operation writes three
entries of an array (two entries of $Tasks$ and one of the extra boolean
array), differently from WS-WMULT’s Put operations that writes only two (both
of $Taks$).

(a) Subfigure 1

(b) subfigure 2

Figure 9. Results of experiments for puts, takes and steals.

The results of the Put-Steal experiment in the processor Intel Core i7 are
shown in Figure 9b, where, as expected, Put operations exhibited a similar
performance as in the Put-Take experiment.

For Steal operations, we observe that Chase-Lev, Idempotent FIFO, and WS-WMULT
are faster than Idempotent LIFO and B-WS-WMULT. In particular, WS-WMULT is the
fastest among all algorithms, which is expected as it does not use fences and
Read-Modify-Write instructions. The speed-up is of 37%, 27.8% and 11.2%
compared to Chase-Lev, Idempotent FIFO and Idempotent LIFO, respectively. As
for total time, we observe an speed-up of 40.4%, 36%, and 19% regarding Chase-
Lev, Idempotent FIFO and Idempotent LIFO in each instance. For B-WS-WMULT , we
have a similar result than the one in the Puts-Takes experiment.

Finally, the array-based implementation of WS-WMULT, denoted WS_WMULT_ARRAY
the figures, performed much better than any other algorithm, with a speed-up
of up to 65.9%, 58.7% and 49.2% compared to Chase-Lev, Idempotent FIFO and
Idempotent LIFO, for the Put-Steal experiment. Similarly, for the Put-Take
experiment, the speed-up reached by the array-based implementation of WS-WMULT
was of 52.1% respect to Chase-Lev, 46.3% compared to Idempotent FIFO and 42.3%
for Idempotent LIFO. This implementation performs better than the linked-list
version of WS-WMULT because the latter creates a large number of arrays during
the execution.

In the next experiment, we do not discuss in detail the result of the array-
based implementations of our algorithms as the linked-list implementations
have a similar performance, and sometimes outperforming them.

(a) Subfigure 3

(b) Subfigure 4

(c) Subfigure 5

(d) Subfigure 6

Figure 10. Speedups for random graphs

##### Irregular graph application

Table 1 displays the minimum and maximum speed-up achieved by each algorithm,
normalized with respect to the one-thread execution of Chase-Lev, for every
graph and processor. Overall, WS-WMULT had a better performance with maximum
speed-up of 9.64, corresponding to a gain of 5.39%, 2.59%, 2.9% and 0.72%
respect to the maximum speed-up for Chase-Lev, Idempotent FIFO, Idempotent
LIFO and B-WS-WMULT), for the undirected random graph in the Xeon processor.
This speed-up is slightly better than the maximum speed-up achieved by
Idempotent LIFO, the best for this graph among the other algorithms. The
average of the maximum speed-up of WS-WMULT is 3.92 (corresponding to a gain
of 20.15% respect to Chase-Lev, where the average of the maximum speed-up was
of 3.13. For Idempotent FIFO, Idempotent LIFO and B-WS-WMULT the gain was of
2.04%, 8.92% and 3.31% with an average for the maximum of the speed-ups of
3.84, 3.57 and 3.79 respectively. B-WS-WMULT always showed a similar
performance than Idempotent FIFO algorithm; we expected this behavior as both
use expensive Read-Modify-Write instructions in Steal. Below we discuss the
results for each type of graph.

##### Random graphs

For the directed case (Figure 10a), we observe that WS-WMULT and Idempotent
LIFO present a slightly better performance than the other algorithm. Here, the
gains of WS-WMULT was of 1.26% and 5.97% for Idempotent FIFO and B-WS-WMULT.
For the undirected case, Idempotent FIFO and LIFO perform sightly better than
the other algorithms, as shown in figure 10b. Using the results for the Core
i7 processor, we observe the gain for Idempotent FIFO and LIFO respect to
maximum speed-up of WS-WMULT is of 0.27% and 2.46%, respectively, while the
gain of WS-WMULT respect to Chase-Lev is of 5.74%. In both cases, B-WS-WMULT
presented the lowest speed-up. All algorithms showed a similar performance for
both types of graph in the Intel Xeon processor, as shown in Figures 10c and
10d.

Graph | Graph type | Processor | Chase-Lev | FIFO | LIFO | WS-WMULT | B-WS-WMULT
---|---|---|---|---|---|---|---
Random | Directed | Core i7 | $1.0x\sim 3.22x$ | $0.78x\sim 3.14x$ | $0.91x\sim 3.33x$ | $0.78x\sim 3.18x$ | $0.74x\sim 2.99x$
Xeon | $1.0x\sim 4.49x$ | $0.81x\sim 4.82x$ | $0.88x\sim 4.84x$ | $0.8x\sim 4.95x$ | $0.79x\sim 4.87x$
Undirected | Core i7 | $1.0x\sim 3.45x$ | $0.95x\sim 3.67x$ | $0.98x\sim 3.75x$ | $0.9x\sim 3.66x$ | $0.85x\sim 3.45x$
Xeon | $1.0x\sim 9.12x$ | $0.97x\sim 9.39x$ | $1.11x\sim 9.36x$ | $0.92x\sim 9.64x$ | $0.94x\sim 9.57x$
2D Torus | Directed | Core i7 | $1.0x\sim 2.11x$ | $0.94x\sim 3.49x$ | $0.9x\sim 2.73x$ | $0.92x\sim 3.52x$ | $0.85x\sim 3.34x$
Xeon | $0.74x\sim 2.63x$ | $1.21x\sim 5.19x$ | $0.9x\sim 5.42x$ | $1.32x\sim 5.33x$ | $1.26x\sim 5.23x$
Undirected | Core i7 | $1.0x\sim 1.94x$ | $0.61x\sim 2.14x$ | $0.84x\sim 1.96x$ | $0.62x\sim 2.2x$ | $0.56x\sim 2.06x$
Xeon | $1.0x\sim 1.98x$ | $0.43x\sim 2.2x$ | $0.77x\sim 2.33x$ | $0.43x\sim 2.25x$ | $0.35x\sim 2.14x$
2D60 Torus | Directed | Core i7 | $1.0x\sim 2.06x$ | $0.59x\sim 2.21x$ | $0.87x\sim 2.15x$ | $0.6x\sim 2.32x$ | $0.56x\sim 2.13x$
Xeon | $1.0x\sim 1.95x$ | $0.66x\sim 2.38x$ | $0.86x\sim 2.09x$ | $0.64x\sim 2.39x$ | $0.6x\sim 2.43x$
Undirected | Core i7 | $1.0x\sim 2.19x$ | $0.77x\sim 2.71x$ | $0.88x\sim 2.55x$ | $0.78x\sim 2.81x$ | $0.73x\sim 2.51x$
Xeon | $1.0x\sim 2.57x$ | $0.56x\sim 3.66x$ | $0.8x\sim 3.29x$ | $0.57x\sim 3.79x$ | $0.56x\sim 3.61x$
3D Torus | Directed | Core i7 | $1.0x\sim 2.21x$ | $0.92x\sim 3.17x$ | $0.88x\sim 2.79x$ | $0.91x\sim 3.47x$ | $0.86x\sim 3.26x$
Xeon | $0.7x\sim 3.52x$ | $0.92x\sim 5.75x$ | $1.02x\sim 4.64x$ | $1.01x\sim 5.75x$ | $0.94x\sim 5.65x$
Undirected | Core i7 | $1.0x\sim 2.5x$ | $0.73x\sim 2.51x$ | $0.9x\sim 2.56x$ | $0.67x\sim 2.58x$ | $0.62x\sim 2.52x$
Xeon | $1.0x\sim 3.77x$ | $0.83x\sim 4.94x$ | $0.94x\sim 3.94x$ | $0.85x\sim 4.87x$ | $0.76x\sim 5.05x$
3D40 Torus | Directed | Core i7 | $1.0x\sim 2.95x$ | $0.88x\sim 3.19x$ | $0.91x\sim 3.06x$ | $0.86x\sim 3.26x$ | $0.82x\sim 2.99x$
Xeon | $1.0x\sim 3.63x$ | $0.8x\sim 4.46x$ | $0.88x\sim 3.99x$ | $0.8x\sim 4.47x$ | $0.8x\sim 4.43x$
Undirected | Core i7 | $1.0x\sim 2.65x$ | $0.8x\sim 3.05x$ | $0.89x\sim 2.84x$ | $0.78x\sim 3.02x$ | $0.72x\sim 2.78x$
Xeon | $1.0x\sim 3.67x$ | $0.85x\sim 4.78x$ | $0.96x\sim 3.95x$ | $0.79x\sim 4.98x$ | $0.85x\sim 4.81x$
Table 1.  Summary of speedups performed by each algorithm. We show the maximum
and the minimum obtained in each experiment.

##### 2D Torus

In the case of 2D Torus (and similarly for the 2D60 Torus), we observe a
pattern: our algorithms showed a bad performance with one or two threads, but
when the number of threads increases, our algorithms improved the speed up of
Idempotent LIFO and Chase-Lev. Additionally, the performance showed by
Idempotent FIFO is between the registered by WS-WMULT and B-WS-WMULT. We can
see this behavior in Figures 11a, 11b, 11c and 11d. In the results of the
experiments in the Core i7 processor, we observe the following: for the 2D
Directed Torus, the gains of WS-WMULT respect to the maximum average were 40%,
0.85% and 22.4% for Chase-Lev, Idempotent FIFO and LIFO respectively. Making a
similar comparison, for the 2D Undirected Torus, we observed gains of 11.82%,
2.73% and 10.91%. For the 2D60 Directed Torus, the gains of WS-WMULT were
11.21%, 4.74% and 7.33%. For the 2D60 Undirected Torus, the gains with WS-
WMULT were 22.06%, 3.56% and 9.25%.

A similar behavior can be observed in the experiments performed in the Intel
Xeon cluster. In most of the of executions, WS-WMULT has a better performance
than other algorithms, see the Figures 12a, 12b, 12c and 12d. We can also
observe a noticeable loss of performance of Chase-Lev over the directed 2D
Torus, sometimes a with performance that is worse than if it were ran using a
single thread (Figure 12a). It similarly happens for the directed and
undirected 2D60 Torus.

(a) Subfigure 7

(b) Subfigure 8

(c) Subfigure 9

(d) Subfigure 10

Figure 11. Speedups for 2D Torus on Intel Core i7

(a) Subfigure 11

(b) Subfigure 12

(c) Subfigure 13

(d) Subfigure 14

Figure 12. Speedups for 2D Torus on Intel Xeon

##### 3D Torus

For the directed 3D Torus and the 3D40 Torus (directed and undirected), we
noted a behavior similar to that of the 2D Torus (Figures 13a, 13c, 13d). In
these experiments, we observe the following gains for the maximum speed-up
performed by WS-WMULT in the directed 3D Torus: 36.61%, 8.65% and 19.6%
respect to Chase-Lev, Idempotent FIFO and Idempotent LIFO respectively. For
the directed 3D40 Torus, the gains were 9.51%, 2.15% and 6.13%, and for the
undirected version, 12.25%, -0.99%555In this case, Idempotent FIFO has a
sightly better maximum speed-up than WS-WMULT and 5.95%. For the undirected 3D
Torus, the Idempotent FIFO presents a slightly better performance than WS-
WMULT algorithm, while B-WS-WMULT has a sightly worse performance than any
other algorithms (Figure 13b). Here, the gains of WS-WMULT for the maximum
speed-ups, were of 3.1%, 2.71% and 0.78% respect to Chase-Lev, Idempotent FIFO
and Idempotent LIFO.

In the experiments in the Intel Xeon, we observe that our algorithms, together
with Idempotent FIFO, exhibit a better performance for the four versions of 3D
torus (Figures 14a, 14b, 14c and 14d).

(a) Subfigure 15

(b) Subfigure 16

(c) Subfigure 17

(d) Subfigure 18

Figure 13. Speedups for 3D Torus on Intel Core i7

(a) Subfigure 19

(b) Subfigure 20

(c) Subfigure 21

(d) Subfigure 22

Figure 14. Speedups for 3D Torus on Intel Xeon

##  9\. Final Discussion

We have studied two relaxations for work-stealing, called multiplicity and
weak multiplicity. Both of them allow a task to be extracted by more than one
Take/Steal operation but each process can take the same task at most once;
however, the relaxation can arise only in presence of concurrency. We
presented fully Read/Write wait-free algorithms for the relaxations. All
algorithms are devoid of Read-After-Write synchronization patterns and the
algorithm for the weak multiplicity case is also fully fence-free with
constant step complexity. To the best of our knowledge, this is the first time
work-stealing algorithms with these properties have been proposed, evading the
impossibility result in (AGHKMV11, ) in all operations. From the theoretical
perspective of the consensus number hierarchy, we have thus shown that work-
stealing with multiplicity and weak multiplicity lays at the lowest level of
the hierarchy (H91, ).

We have performed some an experimental evaluation comparing our work-stealing
solutions to THE Cilk, Chase-Lev and idempotent work-stealing algorithms. The
experiments show that our WS-WMULT algorithm exhibits a better performance
than the previously mentioned algorithms, while its bounded version, B-WS-
WMULT, with a Swap-based Steal operation, shows a lower performance than WS-
WMULT, but keeps a competitive performance with respect to the other
algorithms.

All our results together show that one of the simplest synchronization
mechanisms suffices to solve non-trivial coordination problems, particularly,
computing a spanning tree.

For future research, we are interested in developing algorithms for work-
stealing with multiplicity and weak multiplicity that insert/extract tasks in
orders different from FIFO. Also, it is interesting to explore if the
techniques in our algorithms can be applied to efficiently solve relaxed
versions of other concurrent objects. For example, it is worth to explore if a
multi-enqueuer multi-dequeuer queue with multiplicity (resp. weak
multiplicity) can be obtained by manipulating the tail with a MaxRegister
(resp. RangeMaxRegister) object, like the head is manipulated in our
algorithms.

## References

  * (1) Dolev Adas and Roy Friedman.  Brief announcement: Jiffy: A fast, memory efficient, wait-free multi-producers single-consumer queue.  In 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, pages 50:1–50:3, 2020.  doi:10.4230/LIPIcs.DISC.2020.50.
  * (2) Yehuda Afek, Guy Korland, and Eitan Yanovsky.  Quasi-linearizability: Relaxed consistency for improved concurrency.  In Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14-17, 2010. Proceedings, pages 395–410, 2010.  doi:10.1007/978-3-642-17653-1\\_29.
  * (3) James Aspnes, Hagit Attiya, and Keren Censor-Hillel.  Polylogarithmic concurrent data structures from monotone circuits.  J. ACM, 59(1):2:1–2:24, 2012.  doi:10.1145/2108242.2108244.
  * (4) Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov, Maged M. Michael, and Martin T. Vechev.  Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated.  In Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 487–498, 2011.  doi:10.1145/1926385.1926442.
  * (5) Eduard Ayguadé, Nawal Copty, Alejandro Duran, Jay Hoeflinger, Yuan Lin, Federico Massaioli, Xavier Teruel, Priya Unnikrishnan, and Guansong Zhang.  The design of openmp tasks.  IEEE Trans. Parallel Distrib. Syst., 20(3):404–418, 2009.  doi:10.1109/TPDS.2008.105.
  * (6) David A. Bader and Guojing Cong.  A fast, parallel spanning tree algorithm for symmetric multiprocessors.  In 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), CD-ROM / Abstracts Proceedings, 26-30 April 2004, Santa Fe, New Mexico, USA. IEEE Computer Society, 2004.  doi:10.1109/IPDPS.2004.1302951.
  * (7) Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou.  Cilk: An efficient multithreaded runtime system.  In Proceedings of the Fifth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPOPP), Santa Barbara, California, USA, July 19-21, 1995, pages 207–216, 1995.  doi:10.1145/209936.209958.
  * (8) Armando Castañeda, Sergio Rajsbaum, and Michel Raynal.  Unifying concurrent objects and distributed tasks: Interval-linearizability.  J. ACM, 65(6):45:1–45:42, 2018.  doi:10.1145/3266457.
  * (9) Armando Castañeda, Sergio Rajsbaum, and Michel Raynal.  Relaxed queues and stacks from read/write operations.  In 24th International Conference on Principles of Distributed Systems, OPODIS 2020, December 14-16, 2020, Strasbourg, France (Virtual Conference), pages 13:1–13:19, 2020.  doi:10.4230/LIPIcs.OPODIS.2020.13.
  * (10) Philippe Charles, Christian Grothoff, Vijay A. Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar.  X10: an object-oriented approach to non-uniform cluster computing.  In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2005, October 16-20, 2005, San Diego, CA, USA, pages 519–538, 2005.  doi:10.1145/1094811.1094852.
  * (11) David Chase and Yossi Lev.  Dynamic circular work-stealing deque.  In SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 18-20, 2005, Las Vegas, Nevada, USA, pages 21–28, 2005.  doi:10.1145/1073970.1073974.
  * (12) Matei David.  A single-enqueuer wait-free queue implementation.  In Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-7, 2004, Proceedings, pages 132–143, 2004.  doi:10.1007/978-3-540-30186-8\\_10.
  * (13) Christine H. Flood, David Detlefs, Nir Shavit, and Xiolan Zhang.  Parallel garbage collection for shared memory multiprocessors.  In Proceedings of the 1st Java Virtual Machine Research and Technology Symposium, April 23-24, 2001, Monterey, CA, USA, 2001.  URL: http://www.usenix.org/publications/library/proceedings/jvm01/full_papers/flood/flood.pdf.
  * (14) Matteo Frigo, Charles E. Leiserson, and Keith H. Randall.  The implementation of the cilk-5 multithreaded language.  In Proceedings of the ACM SIGPLAN ’98 Conference on Programming Language Design and Implementation (PLDI), Montreal, Canada, June 17-19, 1998, pages 212–223, 1998.  doi:10.1145/277650.277725.
  * (15) Danny Hendler, Yossi Lev, Mark Moir, and Nir Shavit.  A dynamic-sized nonblocking work stealing deque.  Distributed Comput., 18(3):189–207, 2006.  doi:10.1007/s00446-005-0144-5.
  * (16) Danny Hendler and Nir Shavit.  Non-blocking steal-half work queues.  In Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, PODC 2002, Monterey, California, USA, July 21-24, 2002, pages 280–289, 2002.  doi:10.1145/571825.571876.
  * (17) Maurice Herlihy.  Impossibility results for asynchronous PRAM (extended abstract).  In Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’91, Hilton Head, South Carolina, USA, July 21-24, 1991, pages 327–336, 1991.  doi:10.1145/113379.113409.
  * (18) Maurice Herlihy.  Wait-free synchronization.  ACM Trans. Program. Lang. Syst., 13(1):124–149, 1991.  doi:10.1145/114005.102808.
  * (19) Maurice Herlihy and Nir Shavit.  The art of multiprocessor programming.  Morgan Kaufmann, 2008.
  * (20) Maurice P. Herlihy and Jeannette M. Wing.  Linearizability: A correctness condition for concurrent objects.  ACM Transactions on Programming Languages and Systems, 12(3):463–492, July 1990.
  * (21) Prasad Jayanti and Srdjan Petrovic.  Logarithmic-time single deleter, multiple inserter wait-free queues and stacks.  In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings, pages 408–419, 2005.  doi:10.1007/11590156\\_33.
  * (22) Prasad Jayanti, King Tan, and Sam Toueg.  Time and space lower bounds for nonblocking implementations.  SIAM J. Comput., 30(2):438–456, 2000.  doi:10.1137/S0097539797317299.
  * (23) Doug Lea.  A java fork/join framework.  In Proceedings of the ACM 2000 Java Grande Conference, San Francisco, CA, USA, June 3-5, 2000, pages 36–43, 2000.  doi:10.1145/337449.337465.
  * (24) Maged M. Michael, Martin T. Vechev, and Vijay A. Saraswat.  Idempotent work stealing.  In Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2009, Raleigh, NC, USA, February 14-18, 2009, pages 45–54, 2009.  doi:10.1145/1504176.1504186.
  * (25) Adam Morrison and Yehuda Afek.  Fence-free work stealing on bounded TSO processors.  In Architectural Support for Programming Languages and Operating Systems, ASPLOS ’14, Salt Lake City, UT, USA, March 1-5, 2014, pages 413–426, 2014.  doi:10.1145/2541940.2541987.
  * (26) Gil Neiger.  Set-linearizability.  In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, Los Angeles, California, USA, August 14-17, 1994, page 396, 1994.  doi:10.1145/197917.198176.
  * (27) Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary R. Bradski, and Christos Kozyrakis.  Evaluating mapreduce for multi-core and multiprocessor systems.  In 13st International Conference on High-Performance Computer Architecture (HPCA-13 2007), 10-14 February 2007, Phoenix, Arizona, USA, pages 13–24, 2007.  doi:10.1109/HPCA.2007.346181.
  * (28) Peter Sewell, Susmit Sarkar, Scott Owens, Francesco Zappa Nardelli, and Magnus O. Myreen.  x86-tso: a rigorous and usable programmer’s model for x86 multiprocessors.  Commun. ACM, 53(7):89–97, 2010.  doi:10.1145/1785414.1785443.
  * (29) Chaoran Yang and John M. Mellor-Crummey.  A wait-free queue as fast as fetch-and-add.  In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016, Barcelona, Spain, March 12-16, 2016, pages 16:1–16:13, 2016.  doi:10.1145/2851141.2851168.