# Strategyproof and Proportional Chore Division for Piecewise Uniform
Preferences

David Francis
Department of Computer Science
University of Toronto
<EMAIL_ADDRESS>

###### Abstract

Chore division is the problem of fairly dividing some divisible, undesirable
bad, such as a set of chores, among a number of players. Each player has their
own valuation of the chores, and must be satisfied they did not receive more
than their fair share. In this paper, I consider the problem of strategyproof
chore division, in which the algorithm must ensure that each player cannot
benefit from mis-representing their position. I present an algorithm that
performs proportional and strategyproof chore division for any number of
players given piecewise uniform valuation functions.

_Keywords_ Cake cutting $\cdot$ Strategy-proofness $\cdot$ Chore division
$\cdot$ Mechanism design $\cdot$ Fair division

##  1 Introduction

Cake cutting is the problem of dividing a heterogeneous, divisible good such
as a cake among some number of players such that each player is satisfied with
their piece. A valid algorithm must ensure that each player must value their
piece at at least $\frac{1}{n}$ the value of the whole cake (the
proportionality condition). The two-player solution “I cut, you choose” is
ancient. Solutions for any number of players date back to at least 1949
(Steinhaus (1949)).

Chore division is the inverse problem to cake cutting, in which the object to
be divided is undesirable and each player must receive at most their fair
shore (confusingly, the term chore division is also used to refer to the
division of indivisible bads, the inverse of the estate division problem).
Chore division might model the allocation of chores within a household, work
shifts at a hospital, or liabilities in a bankrupt company. Chore division and
cake cutting are surprisingly distinct problems; algorithms from one cannot
easily be applied to the other. For most questions in cake cutting there exist
parallel questions in chore division; for instance, an $n$-person envy-free
cake cutting algorithm, in which each player is satisfied that no other player
has received a bigger piece in their estimation, was found by Brams and Taylor
(1995), while the equivalent chore-division result was found by Peterson and
Su (2009). There have also been some work in the modeling of mixed manna or
burnt cakes: goods which may have positive or negative value, such as the
existence results of Bogomolnaia et al. (2017) and Segal-Halevi (2017).

Strategyproofness is a concept in mechanism design for many problems of group
decision making. A strategyproof algorithm (also known as a truthful or
incentive compatible algorithm) is one in which no player can improve their
position by lying about their preferences. For example, a strategyproof voting
algorithm would not allow voters to change the result of the election to a
more preferred candidate by submitting a ballot containing anything other than
their true ranking of the candidates.

To apply strategyproofness to cake cutting and chore division algorithms, some
restrictions must be placed on the players’ valuations. The standard model of
cake cutting is to treat the interval $[0{,}1]$ as the cake and have the
pieces of cake allocated to each player be subsets of that interval. Under
this model, a players’ preferences can be represented by a valuation function,
which assigns a marginal value (or cost, in the case of chore division) to
each real number in the cake interval.

Two common restricted classes of valuation function are piecewise constant and
piecewise uniform. A piecewise constant valuation function divides the cake
into some number of intervals, with the marginal value constant in each
interval. A piecewise uniform valuation function is the same, with the
additional restriction that the marginal values in each interval must either
be $0$ or $1$. In other words, a piecewise uniform valuation function divides
the cake into two sections: one with uniformly distributed value and one with
zero value. These kinds of restricted valuation functions are necessary in the
discussion of strategyproof algorithms; Mossel and Tamuz (2010) proved that
for arbitrary valuation functions, no deterministic strategyproof cake cutting
algorithm exists.

Maya and Nisan (2012) characterized the problem of strategyproof cake cutting
with piecewise uniform valuation functions, finding a bound on the social
welfare. Chen et al. (2013) found the first strategyproof algorithm for cake
cutting with piecewise uniform valuation functions, which was extended by Aziz
and Ye (2014). The algorithm in Chen et al. (2013) is also envy-free.

As cake cutting and chore division algorithms have continuous inputs and
outputs, a specialized complexity model is needed to measure their complexity.
The standard approach is the model of Robertson and Webb (1998). This treats
an algorithm as a series of cut and evaluate queries. A cut query asks a
player to divide some piece of cake into two pieces such that the values of
the pieces in that player’s estimation are in some given ratio. An evaluate
query asks a player to give their valuation of some given piece of cake.

There is an important distinction between bounded algorithms and unbounded
algorithms. A bounded algorithm is one for which there is some function $f(n)$
such that running the algorithm with $n$ players will never take more than
$f(n)$ queries. The envy-free allocation algorithms found by Brams and Taylor
(1995) and Peterson and Su (2009) are unbounded. Bounded envy-free algorithms
for cake cutting and chore division were found by Aziz and Mackenzie (2016)
and Dehghani et al. (2018) respectively. The algorithm from Chen et al. (2013)
is unbounded; in fact Kurokawa et al. (2013) proved that there is no cake
cutting algorithm that is strategyproof, bounded, and envy-free.

###  1.1 My Results

I present a deterministic algorithm for chore division with piecewise uniform
valuation functions that is strategyproof and proportional. The algorithm
allocates all of the chores with no overlap between assignments. It is pareto-
efficient, but not envy-free.

##  2 Preliminaries

The chores to be divided will be represented by intervals of the real numbers.
A segment of chores is the union of a finite number of finitely large disjoint
intervals. The length of the segment of chores $C$, written $|C|$, is the sum
of the lengths of its component intervals $\sum_{[x_{i}{,}y_{i}]\in
C}y_{i}-x_{i}$. The union of or intersection of two segments of chores is
itself a segment of chores. I will use $\bar{C}$ to denote the set of real
numbers not in $C$.

There is a segment of chores $C$ that must be divided among $n$ players
$\\{P_{1},P_{2},...,P_{n}\\}$. $C$ must be partitioned into $n$ segments of
chores $\\{D_{1},D_{2},...D_{n}\\}$.

Each player has their own valuation of the chores; they might consider some
chores deeply unpleasant and want to avoid them at all costs, while seeing
other chores as relatively painless. In the general case, this can be
represented by a valuation function that assigns a real marginal cost to each
point in $C$. However, in this paper I will consider only the case of
piecewise uniform valuations. Each player divides the chores into two
segments: a segment to which they assign uniformly distributed cost and a
segment to which they assign zero cost.

The segment of chores that the player $P_{i}$ assigns positive cost to is
$P_{i}$’s valuation set $V_{i}$, a (possibly empty) subset of $C$. If $P_{i}$
is assigned the segment $D_{i}$, the cost to $P_{i}$ is $|D_{i}\cap V_{i}|$ of
a possible $|V_{i}|$.

The canonical version of the problem has each player trying to receive at most
$\frac{1}{n}$ of the chores in their estimation, but it will be convenient to
define the problem more generally, with each player having an assigned
workload of the chores $w_{i}$, with the $\\{w_{1},w_{2},...,w_{n}\\}$
positive and summing to $1$.

A chore division algorithm is a function $f$. The arguments to the function
are a segment of chores to be divided $C$, an integer number of players $n$,
$n\geq 2$, a valuation set for each player $V=\\{V_{1},V_{2},...V_{n}\\}$,
with each valuation set a segment and a subset of $C$, and an assigned
workload for each player $w=\\{w_{1},w_{2},...,w_{n}\\}$, with each workload a
positive real number and the workloads all summing to $1$. The result of the
function is a partition of $C$ into $n$ segments $\\{D_{1},D_{2},...D_{n}\\}$.

An algorithm is proportional if each player receives at most $w_{i}$ of the
chores they wanted to avoid. For all $i$, $|V_{i}\cap D_{i}|\leq
w_{i}|V_{i}|$.

Given some result of the algorithm
$f(C,n,V,w)=\\{D_{1},D_{2},D_{3},...,D_{i},...\\}$, player $P_{i}$ might
attempt to improve their standing by reporting a false valuation set
$V_{i}^{*}$. If $V^{*}$ is the list of valuation sets that is the same as $V$
except that $V_{i}$ is replaced by $V_{i}^{*}$, the result of the deception is
the new partition
$f(C,n,V^{*},w)=\\{D_{1}^{*},D_{2}^{*},D_{3}^{*},...,D_{i}^{*},...\\}$. An
algorithm $f$ is strategyproof if, for any $C$, $n$, $V$, $p$, and
$V_{i}^{*}$, $|V_{i}\cap D_{i}|\leq|V_{i}\cap D_{i}^{*}|$.

##  3 The Split Rulership Algorithm

The algorithm has as its input a segment of chores to be divided $C$, an
integer number of players $n$, $n\geq 2$, a valuation set for each player
$V=\\{V_{1},V_{2},...V_{n}\\}$, with each valuation set a segment and a subset
of $C$, and an assigned workload for each player
$w=\\{w_{1},w_{2},...,w_{n}\\}$, with each workload a positive real number and
the workloads all summing to $1$. The algorithm is recursive and asymmetrical;
the ordering of the players is relevant.

The first two players, $P_{1}$ and $P_{2}$, split the chores $C$ at a point
$k$ into two segments. $P_{1}$ rules the left segment $(-\infty{,}k)\cap C$,
and $P_{2}$ rules the right segment $[k{,}\infty)\cap C$.

$P_{1}$ is exempted from doing any of the chores they marked as having cost
within the segment they rule. In exchange, they are assigned all of the chores
within the segment they rule that they did not mark. Similarly, $P_{2}$ is
exempted from $[k{,}\infty)\cap C\cap V_{2}$ but must take $[k{,}\infty)\cap
C\cap\bar{V_{2}}$.

$k$ is chosen such that $P_{1}$ and $P_{2}$ exempt themselves from equal
length of chores, weighted by their assigned workload.

$\text{Let }k\text{ be the lowest real number such that
}w_{1}|(-\infty{,}k)\cap V_{1}|=w_{2}|[k{,}\infty)\cap V_{2}|$

Call the chores $P_{1}$ has exempted themselves from $C_{L}$ and the chores
$P_{2}$ has exempted themselves from $C_{R}$.

$C_{L}=(-\infty{,}k)\cap V_{1}$ $C_{R}=[k{,}\infty)\cap V_{2}$

$C_{L}$ must be divided among the $n-1$ players other than $P_{1}$, and
$C_{R}$ among the $n-1$ players other than $P_{2}$.

If $n=2$, there is only one player remaining for $C_{L}$ and for $C_{R}$. That
player is assigned all of that segment.

$\text{If }n=2\text{, }D_{1}=((-\infty{,}k)\cap\bar{V_{1}}\cap C)\cup C_{R}$
$\text{If }n=2\text{, }D_{2}=([k{,}\infty)\cap\bar{V_{2}}\cap C)\cup C_{L}$

Otherwise $P_{2}$, who ruled the right segment in the division of $C$, will
rule the right segment in the division of $C_{L}$, with the next player in
line $P_{3}$ ruling the left segment. Similarly $P_{1}$ will rule the left
segment in the division of $C_{R}$, with $P_{3}$ ruling the right segment.

$V_{L}=\\{V_{3}\cap C_{L},V_{2}\cap C_{L},V_{4}\cap C_{L},...\\}$
$V_{R}=\\{V_{1}\cap C_{R},V_{3}\cap C_{R},V_{4}\cap C_{R},...\\}$

Since $P_{1}$ is not participating in the division of $C_{L}$, someone must
take on their assigned workload $w_{1}$ to keep the workloads adding to $1$.
$P_{2}$ will do so; their assigned workload in $C_{L}$ will be $w_{1}+w_{2}$.
All other players’ workloads are unchanged. Symmetrically, in $C_{R}$ $P_{1}$
will instead take on $P_{2}$’s workload.

$w_{L}=\\{w_{3},w_{1}+w_{2},w_{4},...\\}$
$w_{R}=\\{w_{1}+w_{2},w_{3},w_{4},...\\}$

The algorithm is then run recursively on $C_{L}$ and on $C_{R}$.

$\\{D_{3}^{L},D_{2}^{L},D_{4}^{L},...\\}=f(C_{L},n-1,V_{L},w_{L})$
$\\{D_{1}^{R},D_{3}^{R},D_{4}^{R},...\\}=f(C_{R},n-1,V_{R},w_{R})$

$\text{If }n>2\text{, }D_{1}=((-\infty{,}k)\cap\bar{V_{1}}\cap C)\cup
D_{1}^{R}$ $\text{If }n>2\text{, }D_{2}=([k{,}\infty)\cap\bar{V_{2}}\cap
C)\cup D_{2}^{L}$ $\text{If }n>2\text{, for any }i>2\text{,
}D_{i}=D_{i}^{L}\cup D_{i}^{R}$

$V_{1}$$V_{2}$$V_{3}$$C$$C_{L}$$C_{R}$$D_{1}$$D_{2}$$D_{3}$$k$$k$$k$ Figure 1:
A sample run of the split rulership algorithm. $w_{1}=w_{2}=w_{3}=\frac{1}{3}$

###  3.1 Proportionality

######  Lemma 1.

The split rulership algorithm is proportional for $n=2$

First, consider the case of $P_{1}$. $D_{1}$, the chores assigned to $P_{1}$,
consist of the chores to the left of $k$ that $P_{1}$ has not marked and the
the chores to the right of $k$ that $P_{2}$ has marked.

$D_{1}=(\bar{V_{1}}\cap(-\infty{,}k)\cap C)\cup(V_{2}\cap[k{,}\infty))$

The cost paid by $P_{1}$ in their own estimation is $|V_{1}\cap D_{1}|$. As
$P_{1}$ is exempted from all chores they have marked to the left of $k$,
$V_{1}\cap D_{1}$ lies entirely to the right of $k$.

$|V_{1}\cap D_{1}|=|V_{1}\cap((\bar{V_{1}}\cap(-\infty{,}k)\cap
C)\cup(V_{2}\cap[k{,}\infty)))|$ $|V_{1}\cap D_{1}|=|V_{1}\cap
V_{2}\cap[k{,}\infty)|$

These chores are a subset of $C_{R}$.

$|V_{1}\cap D_{1}|\leq|V_{2}\cap[k{,}\infty)|$

We have that $w_{1}|V_{1}\cap(-\infty{,}k)|=w_{2}|V_{2}\cap[k{,}\infty)|$

$|V_{1}\cap D_{1}|\leq\frac{w_{1}}{w_{2}}|V_{1}\cap(-\infty{,}k)|$

Adding $\frac{w_{1}}{w_{2}}|V_{1}\cap D_{1}|$ to each side,

$(1+\frac{w_{1}}{w_{2}})|V_{1}\cap
D_{1}|\leq\frac{w_{1}}{w_{2}}(|V_{1}\cap(-\infty{,}k)|+|V_{1}\cap D_{1}|)$

Since $V_{1}\cap D_{1}$ is entirely to the right of $k$,
$V_{1}\cap(-\infty{,}k)$ and $V_{1}\cap D_{1}$ are non-intersecting subsets of
$V_{1}$.

$(1+\frac{w_{1}}{w_{2}})|V_{1}\cap D_{1}|\leq\frac{w_{1}}{w_{2}}|V_{1}|$

Using the fact that, if $n=2$, $w_{1}+w_{2}=1$.

$\frac{1}{w_{2}}|V_{1}\cap D_{1}|\leq\frac{w_{1}}{w_{2}}|V_{1}|$ $|V_{1}\cap
D_{1}|\leq w_{1}|V_{1}|$

A similar, symmetrical argument holds for $P_{2}$.

######  Theorem 2.

The split rulership algorithm is proportional

Since the $n=2$ case is already taken care of, we may assume $n>2$. Beginning
with $P_{1}$, $D_{1}$ consists of the chores to the left of $k$ that $P_{1}$
did not mark and $P_{1}$’s assigned chores from the division of $C_{R}$,
$D_{1}^{R}$.’

$|V_{1}\cap D_{1}|=|V_{1}\cap((\bar{V_{1}}\cap(-\infty{,}k))\cup D_{1}^{R})|$

Once again, all of $V_{1}\cap D_{1}$ lies entirely to the right of $k$.

$|V_{1}\cap D_{1}|=|V_{1}\cap D_{1}^{R}|$

The division of $C_{R}$ was between $n-1$ players. By induction on the number
of players, we may take as given that the algorithm is proportional when
dividing among $n-1$ players. $P_{1}$’s assigned workload within $C_{R}$ is
$w_{1}+w_{2}$, so $P_{1}$ must have received at most $w_{1}+w_{2}$ of
$V_{1}\cap C_{R}$.

$|V_{1}\cap D_{1}^{R}|\leq(w_{1}+w_{2})|V_{1}\cap V_{2}\cap[k{,}\infty)|$

$V_{1}\cap V_{2}\cap[k{,}\infty)$ is a subset of $C_{R}$, and
$|C_{R}|=\frac{w_{1}}{w_{2}}|C_{L}|$

$|V_{1}\cap
V_{2}\cap[k{,}\infty)|\leq|V_{2}\cap[k{,}\infty)|=\frac{w_{1}}{w_{2}}|V_{1}\cap(-\infty{,}k)|$

Adding $\frac{w_{1}}{w_{2}}|V_{1}\cap V_{2}\cap[k{,}\infty)|$ to each side,

$(1+\frac{w_{1}}{w_{2}})|V_{1}\cap
V_{2}\cap[k{,}\infty)|\leq\frac{w_{1}}{w_{2}}(|V_{1}\cap(-\infty{,}k)|+|V_{1}\cap
V_{2}\cap[k{,}\infty)|)$

Since $|V_{1}\cap(-\infty{,}k)|$ and $|V_{1}\cap V_{2}\cap[k{,}\infty)|$ are
non-intersecting subsets of $V_{1}$,

$(1+\frac{w_{1}}{w_{2}})|V_{1}\cap
V_{2}\cap[k{,}-\infty)|\leq\frac{w_{1}}{w_{2}}|V_{1}|$
$(w_{1}+w_{2})|V_{1}\cap V_{2}\cap[k{,}\infty)|\leq w_{1}|V_{1}|$ $|V_{1}\cap
D_{1}|\leq w_{1}|V_{1}|$

Symmetrically, the same argument holds for $P_{2}$.

All that remains is the case of players other than $P_{1}$ and $P_{2}$. For
any $P_{i}$, $i>2$, $D_{i}$ consists of $P_{i}$’s assigned portions from the
division of $C_{L}$ and $C_{R}$, $D_{i}^{L}$ and $D_{i}^{R}$.

$|V_{i}\cap D_{i}|=|V_{i}\cap D_{i}^{L}|+|V_{i}\cap D_{i}^{R}|$

$P_{i}$’s assigned workload in both of those division is $w_{i}$. By
induction, we may take as given that both of these divisions were
proportional, and that $P_{i}$ received at most $w_{i}$ of their marked chores
in each of those segments.

$|V_{i}\cap D_{i}|\leq w_{i}(|V_{i}\cap V_{1}\cap[-\infty{,}k)|+|V_{i}\cap
V_{2}\cap[k{,}\infty)|)$

Since those two segments are non-intersecting subsets of $V_{i}$,

$|V_{i}\cap D_{i}|\leq w_{i}|V_{i}|$

###  3.2 Strategyproofness

Consider first the case of $P_{1}$, the first player. For some input to the
split rulership algorithm $(C,n,V,w)$ and some alternate valuation set for
$P_{1}$ $V_{1}^{*}$, let $V^{*}$ be the same as $V$ except $V_{1}$ is replaced
by $V_{1}^{*}$, $\\{D_{1},D_{2},...,D_{n}\\}=f(C,n,V,w)$, and
$\\{D_{1}^{*},D_{2}^{*},...,D_{n}^{*}\\}=f(C,n,V^{*},p)$.

$P_{1}$ rules the left segment of $C$ and so is exempted from $C_{L}$, but
must participate in the division of $C_{R}$. If $C_{RL}$ and $C_{RR}$ are the
left and right exempted segments in the division of $C_{R}$, $P_{1}$ is
exempted from $C_{RL}$ and participates in the division of $C_{RR}$. $P_{1}$
also exempts themself from $C_{RRL}$, $C_{RRRL}$, and so on for all $n-1$
rounds. In the $n-1$th round of division, $P_{1}$ and $P_{n}$ will be the only
two players remaining, and $P_{1}$ will be assigned some of the chores $P_{n}$
rules.

Let us introduce some more convenient notation. Let $C_{1}$ be the original
$C$, and $k_{1}$ the $k$ where it is divided. Let $C_{2}$ be the $C_{R}$ in
the division of $C$, $C_{3}$ the $C_{R}$ in the division of $C_{2}$, and so
on. We may ignore the division of the $C_{L}$ of each of these iterations, as
$P_{1}$ is not assigned any of them.

$C_{1}=C$ $C_{j+1}=C_{j}\cap V_{j+1}\cap[k_{j}{,}\infty)$

Or, non-recursively defined,

$C_{j}=C\cap V_{2}\cap V_{3}\cap...\cap V_{j}\cap[k_{j-1}{,}\infty)$

With $C_{1}^{*},C_{2}^{*},...C_{n-1}^{*}$ and
$k_{1}^{*},k_{2}^{*},...k_{n-1}^{*}$ defined equivalently for the algorithm as
run on $V^{*}$. Note that all the valuation sets except $P_{1}$’s are
unchanged in this case.

$C_{j}^{*}=C\cap V_{2}\cap V_{3}\cap...\cap V_{j}\cap[k_{j-1}^{*}{,}\infty)$

$D_{1}$$C_{n-1}$$C_{3}$$C_{2}$$C_{1}$$V_{1}$$k_{1}$$k_{2}$$k_{3}$$k_{n-1}$$...$$...$
Figure 2: The split rulership algorithm as seen by $P_{1}$

From $C_{1}$ up to $C_{n-1}$, $P_{1}$ is assigned the chores to the left of
$k_{i}$ that are outside of $V_{1}$. In the division of $C_{n-1}$, $P_{1}$ is
also assigned the chores that $P_{n}$ exempts themselves from to the right of
$k_{n-1}$.

$D_{1}=(C_{1}\cap(-\infty{,}k_{1})\cap\bar{V_{1}})\cup(C_{2}\cap[k_{1}{,}k_{2})\cap\bar{V_{1}})\cup...\cup(C_{n-1}\cap[k_{n-2}{,}k_{n-1})\cap\bar{V_{1}})\cup(C_{n-1}\cap[k_{n-1}{,}\infty)\cap
V_{n})$

All the chores $P_{1}$ is assigned that $P_{1}$ assigns cost to are to the
right of $k_{n-1}$.

$V_{1}\cap D_{1}=C_{n-1}\cap[k_{n-1}{,}\infty)\cap V_{n}\cap V_{1}$

These are precisely the chores that all players marked that lie to the right
of $k_{n-1}$.

$V_{1}\cap D_{1}=V_{1}\cap V_{2}\cap...\cap V_{n}\cap[k_{n-1}{,}\infty)$

######  Lemma 3.

If $k_{n-1}^{*}<k_{n-1}$, $|V_{1}\cap D_{1}|\leq|V_{1}\cap D_{1}^{*}|$

Suppose $k_{n-1}^{*}<k_{n-1}$. $P_{1}$ will be assigned all chores to the
right of $k_{n-1}^{*}$ that all players other than $P_{1}$ marked.

$D_{1}^{*}\supseteq C_{n-1}^{*}\cap[k_{n-1}^{*}{,}\infty)\cap V_{n}$
$D_{1}^{*}\supseteq V_{2}\cap V_{3}\cap...\cap
V_{n}\cap[k_{n-1}^{*}{,}\infty)$ $|V_{1}\cap D_{1}^{*}|\geq|V_{1}\cap
V_{2}\cap...\cap V_{n}\cap[k_{n-1}^{*}{,}\infty)|$

As $k_{n-1}^{*}$ is to the left of $k_{n-1}$

$|V_{1}\cap D_{1}^{*}|\geq|V_{1}\cap V_{2}\cap...\cap
V_{n}\cap[k_{n-1}{,}\infty)|$ $|V_{1}\cap D_{1}^{*}|\geq|V_{1}\cap D_{1}|$

Then, for $P_{1}$ to get any advantage from their deception, $k_{n-1}^{*}\geq
k_{n-1}$, and from this point on I will assume that this is true. Some of the
$k_{i}^{*}$ may be less than the equivalent $k_{i}$, some may be greater, and
some may be the same. Let $k_{q}^{*}$ be the first of these $k_{i}^{*}$ for
which all the $k_{i}^{*}$ from $k_{q}^{*}$ up to $k_{n-1}^{*}$ are greater
than or equal to their respective $k_{i}$.

$k_{q-1}^{*}<k_{q-1}\text{ or }q=1$ $\text{For all }j\geq q\text{,
}k_{j}^{*}\geq k_{j}$

If $q=1$, the argument proceeds slightly differently. In that case, replace
$k_{q-1}$ and $k_{q-1}^{*}$ with $-\infty$ wherever they appear below.

The portion of $D_{1}$ that lies within $C_{q}$ is

$D_{1}\cap
C_{q}=(C_{q}\cap[k_{q-1}{,}k_{q})\cap\bar{V_{1}})\cup(C_{q+1}\cap[k_{q}{,}k_{q+1})\cap\bar{V_{1}})\cup...\cup(C_{n-1}\cap[k_{n-2}{,}k_{n-1})\cap\bar{V_{1}})\cup(C_{n-1}\cap[k_{n-1}{,}\infty)\cap
V_{n})$ $D_{1}\cap
C_{q}=(\bar{V_{1}}\cap((C_{q}\cap[k_{q-1}{,}k_{q}))\cup(C_{q+1}\cap[k_{q}{,}k_{q+1}))\cup...\cup(C_{n-1}\cap[k_{n-2}{,}k_{n-1})))\cup(C_{n-1}\cap[k_{n-1}{,}\infty)\cap
V_{n})$

Let $C_{H}$ be defined as follows

$C_{H}=(C_{q}\cap[k_{q-1}{,}k_{q}))\cup(C_{q+1}\cap[k_{q}{,}k_{q+1}))\cup...\cup(C_{n-1}\cap[k_{n-2}{,}k_{n-1}))$
$D_{1}\cap C_{q}=(\bar{V_{1}}\cap C_{H})\cup(C_{n-1}\cap[k_{n-1}{,}\infty)\cap
V_{n})$

And similarly,

$C_{H}^{*}=(C_{q}^{*}\cap[k_{q-1}^{*}{,}k_{q}^{*}))\cup(C_{q+1}^{*}\cap[k_{q}^{*}{,}k_{q+1}^{*}))\cup...\cup(C_{n-1}^{*}\cap[k_{n-2}^{*}{,}k_{n-1}^{*}))$
$D_{1}^{*}\cap C_{q}^{*}=(\bar{V_{1}^{*}}\cap
C_{H}^{*})\cup(C_{n-1}^{*}\cap[k_{n-1}^{*}{,}\infty)\cap V_{n})$

######  Lemma 4.

$C_{H}\subseteq C_{H}^{*}$

Suppose $h$ is a real number in $C_{H}$. $k_{q-1}<h<k_{n-1}$, and there is
some integer $i$, $q\leq i\leq n-1$, for which $k_{i-1}\leq h<k_{i}$.

$h\in C_{i}\cap[k_{i-1}{,}k_{i})$ $h\in C\cap V_{2}\cap V_{3}\cap...\cap
V_{i}$

$k_{q-1}^{*}\leq k_{q-1}$ and $k_{n-1}^{*}>k_{n-1}$, so
$k_{q-1}^{*}<h<k_{n-1}^{*}$. Then there is also some integer $j$, $q\leq j\leq
n-1$, for which $k_{j-1}^{*}\leq h<k_{j}^{*}$. Because all of the $k_{j}^{*}$
are to the right of their respective $k_{j}$, $i\leq j$.

$h\in C\cap V_{2}\cap V_{3}\cap...\cap V_{j}$ $h\in
C_{j}^{*}\cap[k_{j-1}^{*}{,}k_{j}^{*})$ $h\in C_{H}^{*}$

As this is true for any real number in $C_{H}$,

$C_{H}\subseteq C_{H}^{*}$

######  Lemma 5.

$C_{n-1}\cap[k_{n-1}{,}k_{n-1}^{*})\subseteq
C_{H}^{*}\cap[k_{n-1}{,}k_{n-1}^{*})$

Suppose $g$ is a real number in $C_{n-1}\cap[k_{n-1}{,}k_{n-1}^{*})$.

$g\in C_{n-1}\cap[k_{n-1}{,}k_{n-1}^{*})$ $g\in C\cap V_{2}\cap
V_{3}\cap...\cap V_{n-1}\cap[k_{n-1}{,}k_{n-1}^{*})$

Since $k_{q-1}^{*}<g<k_{n-1}^{*}$, there must be some $j\leq n-1$ such that
$k_{j-1}^{*}\leq g<k_{j}^{*}$

$g\in C\cap V_{2}\cap V_{3}\cap...\cap V_{j}\cap[k_{n-1}{,}k_{n-1}^{*})$ $g\in
C_{j}^{*}\cap[k_{j-1}^{*}{,}k_{j}^{*})\cap[k_{n-1}{,}k_{n-1}^{*})$ $g\in
C_{H}^{*}\cap[k_{n-1}{,}k_{n-1}^{*})$

As this is true for any real number in $C_{n-1}\cap[k_{n-1}{,}k_{n-1}^{*})$,

$C_{n-1}\cap[k_{n-1}{,}k_{n-1}^{*})\subseteq
C_{H}^{*}\cap[k_{n-1}{,}k_{n-1}^{*})$

######  Lemma 6.

For any integer $j$, if $q\leq j\leq n-1$, $|[k_{j-1}^{*}{,}k_{j}^{*})\cap
V_{1}^{*}\cap C_{j}^{*}|\leq|[k_{j-1}{,}k_{j})\cap V_{1}\cap C_{j}|$

For any integer $j$, $q\leq j\leq n-1$, we have from the split decision
algorithm applied to the division of $C_{j}$

$|[k_{j-1}{,}k_{j})\cap V_{1}\cap
C_{j}|=\frac{w_{j+1}}{w_{1}^{j}}|[k_{j}{,}\infty)\cap C_{j}\cap V_{j+1}|$
$|[k_{j-1}^{*}{,}k_{j}^{*})\cap V_{1}^{*}\cap
C_{j}^{*}|=\frac{w_{j+1}}{w_{1}^{j}}|[k_{j}^{*}{,}\infty)\cap C_{j}^{*}\cap
V_{j+1}|$

Where $w_{1}^{j}$ is the workload assigned to $P_{1}$ in the division of
$C_{j}$.

$|[k_{j-1}{,}k_{j})\cap V_{1}\cap
C_{j}|=\frac{w_{j+1}}{w_{1}^{j}}|[k_{j}{,}\infty)\cap V_{2}\cap
V_{3}\cap...\cap V_{j}\cap V_{j+1}|$ $|[k_{{}_{j}-1}^{*}{,}k_{j}^{*})\cap
V_{1}^{*}\cap C_{j}^{*}|=\frac{w_{j+1}}{w_{1}^{j}}|[k_{j}^{*}{,}\infty)\cap
V_{2}\cap V_{3}\cap...\cap V_{j}\cap V_{j+1}|$

As $k_{j}^{*}\geq k_{j}$, $[k_{j}^{*}{,}\infty)\subseteq[k_{j}{,}\infty)$, and
we have

$|[k_{j-1}^{*}{,}k_{j}^{*})\cap V_{1}^{*}\cap
C_{j}^{*}|\leq|[k_{j-1}{,}k_{j})\cap V_{1}\cap C_{j}|$

######  Lemma 7.

$|V_{1}\cap\bar{V_{1}^{*}}\cap
C_{H}^{*}\cap[k_{q-1}{,}k_{n-1})|\geq|V_{1}^{*}\cap
C_{H}^{*}\cap[k_{n-1}{,}k_{n-1}^{*})|$

Using lemma 4, we have

$|[k_{q-1}{,}k_{n-1})\cap V_{1}\cap C_{H}^{*}|\geq|[k_{q-1}{,}k_{n-1})\cap
V_{1}\cap C_{H}|$ $|[k_{q-1}{,}k_{n-1})\cap V_{1}\cap C_{H}^{*}|\geq|V_{1}\cap
C_{q}\cap[k_{q-1}{,}k_{q})|+|V_{1}\cap
C_{q+1}\cap[k_{q}{,}k_{q+1})|+...+|V_{1}\cap C_{n-1}\cap[k_{n-2}{,}k_{n-1})|$

Using lemma 6 on each of those terms,

$|[k_{q-1}{,}k_{n-1})\cap V_{1}\cap C_{H}^{*}|\geq|V_{1}^{*}\cap
C_{q}^{*}\cap[k_{q-1}^{*}{,}k_{q}^{*})|+|V_{1}^{*}\cap
C_{q+1}^{*}\cap[k_{q}^{*}{,}k_{q+1}^{*})|+...+|V_{1}^{*}\cap
C_{n-1}^{*}\cap[k_{n-2}^{*}{,}k_{n-1}^{*})|$ $|[k_{q-1}{,}k_{n-1})\cap
V_{1}\cap C_{H}^{*}|\geq|V_{1}^{*}\cap
C_{H}^{*}\cap[k_{q-1}^{*}{,}k_{n-1}^{*})|$

Using the fact that $k_{q-1}^{*}<k_{q-1}$

$|[k_{q-1}{,}k_{n-1})\cap V_{1}\cap C_{H}^{*}|\geq|V_{1}^{*}\cap
C_{H}^{*}\cap[k_{q-1}{,}k_{n-1}^{*})|$

Splitting the right side at $k_{n-1}$,

$|[k_{q-1}{,}k_{n-1})\cap V_{1}\cap C_{H}^{*}|\geq|V_{1}^{*}\cap
C_{H}^{*}\cap[k_{q-1}{,}k_{n-1})|+|V_{1}^{*}\cap
C_{H}^{*}\cap[k_{n-1}{,}k_{n-1}^{*})|$ $|[k_{q-1}{,}k_{n-1})\cap V_{1}\cap
C_{H}^{*}|-|V_{1}^{*}\cap C_{H}^{*}\cap[k_{q-1}{,}k_{n-1})|\geq|V_{1}^{*}\cap
C_{H}^{*}\cap[k_{n-1}{,}k_{n-1}^{*})|$

For any two segments $A$ and $B$, $|A\cap\bar{B}|\geq|A|-|B|$.

$|V_{1}\cap\bar{V_{1}^{*}}\cap
C_{H}^{*}\cap[k_{q-1}{,}k_{n-1})|\geq|V_{1}^{*}\cap
C_{H}^{*}\cap[k_{n-1}{,}k_{n-1}^{*})|$

######  Lemma 8.

If $k_{n-1}^{*}\geq k_{n-1}$, $|V_{1}\cap D_{1}|\leq|V_{1}\cap D_{1}^{*}|$

Now we can put it all together.

$|V_{1}\cap D_{1}|=|[k_{n-1}{,}\infty)\cap C_{n-1}\cap V_{n}\cap V_{1}|$
$|V_{1}\cap D_{1}|=|[k_{n-1}{,}k_{n-1}^{*})\cap C_{n-1}\cap V_{n}\cap
V_{1}|+|[k_{n-1}^{*}{,}\infty)\cap C_{n-1}\cap V_{n}\cap V_{1}|$ $|V_{1}\cap
D_{1}|\leq|[k_{n-1}{,}k_{n-1}^{*})\cap C_{n-1}\cap
V_{1}|+|[k_{n-1}^{*}{,}\infty)\cap C_{n-1}\cap V_{n}\cap V_{1}|$

Using lemma 5,

$|V_{1}\cap D_{1}|\leq|[k_{n-1}{,}k_{n-1}^{*})\cap C_{H}^{*}\cap
V_{1}|+|[k_{n-1}^{*}{,}\infty)\cap C_{n-1}\cap V_{n}\cap V_{1}|$ $|V_{1}\cap
D_{1}|\leq|[k_{n-1}{,}k_{n-1}^{*})\cap C_{H}^{*}\cap
V_{1}\cap\bar{V_{1}^{*}}|+|[k_{n-1}{,}k_{n-1}^{*})\cap C_{H}^{*}\cap V_{1}\cap
V_{1}^{*}|+|[k_{n-1}^{*}{,}\infty)\cap C_{n-1}\cap V_{n}\cap V_{1}|$
$|V_{1}\cap D_{1}|\leq|[k_{n-1}{,}k_{n-1}^{*})\cap C_{H}^{*}\cap
V_{1}\cap\bar{V_{1}^{*}}|+|[k_{n-1}{,}k_{n-1}^{*})\cap C_{H}^{*}\cap
V_{1}^{*}|+|[k_{n-1}^{*}{,}\infty)\cap C_{n-1}\cap V_{n}\cap V_{1}|$

Using lemma 7,

$|V_{1}\cap D_{1}|\leq|[k_{n-1}{,}k_{n-1}^{*})\cap C_{H}^{*}\cap
V_{1}\cap\bar{V_{1}^{*}}|+|[k_{q-1}{,}k_{n-1})\cap C_{H}^{*}\cap
V_{1}\cap\bar{V_{1}^{*}}|+|[k_{n-1}^{*}{,}\infty)\cap C_{n-1}\cap V_{n}\cap
V_{1}|$ $|V_{1}\cap D_{1}|\leq|[k_{q-1}{,}k_{n-1}^{*})\cap C_{H}^{*}\cap
V_{1}\cap\bar{V_{1}^{*}}|+|[k_{n-1}^{*}{,}\infty)\cap C_{n-1}\cap V_{n}\cap
V_{1}|$

$C_{n-1}\cap V_{n}\cap V_{1}$ is the intersection of $[k_{n-1}{,}\infty)$ with
all $n$ valuation sets. $C_{n-1}^{*}\cap V_{n}\cap V_{1}$ is the same but to
the right of $k_{n-1}^{*}$. As $k_{n-1}^{*}\geq k_{n-1}$,
$[k_{n-1}^{*}{,}\infty)\cap C_{n-1}\cap V_{n}\cap
V_{1}=[k_{n-1}^{*}{,}\infty)\cap C_{n-1}^{*}\cap V_{n}\cap V_{1}$.

$|V_{1}\cap D_{1}|\leq|[k_{q-1}{,}k_{n-1}^{*})\cap C_{H}^{*}\cap
V_{1}\cap\bar{V_{1}^{*}}|+|[k_{n-1}^{*}{,}\infty)\cap C_{n-1}^{*}\cap
V_{n}\cap V_{1}|$ $|V_{1}\cap
D_{1}|\leq|V_{1}\cap(([k_{q-1}{,}k_{n-1}^{*})\cap
C_{H}^{*}\cap\bar{V_{1}^{*}})\cup([k_{n-1}^{*}{,}\infty)\cap C_{n-1}^{*}\cap
V_{n}))|$ $|V_{1}\cap D_{1}|\leq|V_{1}\cap D_{1}^{*}|$

With both the $k_{n-1}^{*}<k_{n-1}$ and $k_{n-1}^{*}\geq k_{n-1}$ cases
covered, we have that no matter the $V_{1}^{*}$, $P_{1}$ can never benefit
from deception.

######  Lemma 9.

For any input to the split decision algorithm $C,n,V,w$ and any valuation set
$V_{2}^{*}$, if $V^{*}$ is the same as $V$ expect that $V_{2}$ is replaced by
$V_{2}^{*}$, if $\\{D_{1},D_{2},...,D_{n}\\}=f(C,n,V,w)$, and
$\\{D_{1}^{*},D_{2}^{*},...,D_{n}^{*}\\}=f(C,n,V^{*},w)$, $|V_{2}\cap
D_{2}|\leq|V_{2}\cap D_{2}^{*}|$

The same argument as for $P_{1}$ applies for $P_{2}$, with left and right
swapped.

######  Theorem 10.

The split rulership algorithm is strategyproof

As we have solved the cases of $P_{1}$ and $P_{2}$, all that remains is the
other $n-2$ players. Suppose that $P_{i}$ submits some $V_{i}^{*}$, $i>2$,
with $V^{*}$ the same as $V$ except $V_{i}$ is replaced by $V_{i}^{*}$. In the
split decision algorithm, only $V_{1}$ and $V_{2}$ are used in the choice of
$k$ and creation of $C_{L}$ and $C_{R}$, and so when the algorithm is run with
$V^{*}$ as input the same $C_{L}$ and $C_{R}$ are produced. Let $D_{i}^{L}$
and $D_{i}^{R}$ be the chores assigned to $P_{i}$ in the divisions of $C_{L}$
and $C_{R}$ when the input is $V$, and $D_{i}^{L*}$ and $D_{i}^{R*}$ be the
same but with $V^{*}$ as input. We may proceed by induction on the number of
players. Taking as given that the split decision algorithm is strategyproof
when dividing among $n-1$ players, we have that

$|V_{i}\cap D_{i}^{L}|\leq|V_{i}\cap D_{i}^{L*}|\text{ and }|V_{i}\cap
D_{i}^{R}|\leq|V_{i}\cap D_{i}^{R*}|$ $|V_{i}\cap D_{i}|\leq|V_{i}\cap
D_{i}^{*}|$

##  4 Discussion

A chore division algorithm is envy-free if, when run with
$w=\\{\frac{1}{n},\frac{1}{n},...,\frac{1}{n}\\}$ each player believes that,
not only is their assigned chores at most $\frac{1}{n}$ of the total chores,
but they have the least costly assigned chores among all players. That is, for
any two players $P_{i}$ and $P_{j}$, $|V_{i}\cap D_{i}|\leq|V_{i}\cap D_{j}|$.
The split rulership algorithm is not envy-free. In general, envy-freeness is
harder to achieve for chore division than for cake division, and I suspect
that envy-freeness and strategyproofness are incompatible for chore division.

A chore division algorithm is Pareto efficient if there is no alternate way
the chores could be divided in which at least one player is more satisfied and
no players are less satisfied. That is, if the algorithm produces the division
$\\{D_{1},D_{2},...D_{n}\\}$, for any other partition of $C$
$\\{D_{1}^{\prime},D_{2}^{\prime},...D_{n}^{\prime}\\}$, if there is some
player $P_{i}$ such that $|V_{i}\cap D_{i}|>|V_{i}\cap D_{i}^{\prime}|$, there
must also be some player $P_{j}$ such that $|V_{i}\cap D_{i}|<|V_{i}\cap
D_{i}^{\prime}|$. The split rulership algorithm is Pareto efficient. The only
chores in the $V_{i}\cap D_{i}$ are those chores that all players have marked,
so the total cost paid by all players is $|V_{1}\cap V_{2}\cap...\cap V_{n}|$.
Any other partition of the chores must have a total cost at least this great.
However, if at least one player paid less cost and no players paid more cost,
the total cost paid would be lower.

Piecewise uniform valuation functions are the most restrictive class of
valuation functions for which chore division as a problem makes sense. Other
classes of valuation functions that have been proposed include piecewise
constant (in which each interval has a constant marginal cost, but those
marginal costs need not be equal) and piecewise linear (in which each interval
has a marginal cost that is a linear function). A very simple extension might
have players’ marginal valuations restricted to a finite set of values. No
deterministic strategyproof algorithms have been found for these less
restrictive class of valuation functions for either cake cutting or chore
division.

The split rulership algorithm is incompatible with the Robertson-Webb query
model of algorithm complexity (Robertson and Webb (1998)). The placement of
$k$ is dependent on both $P_{1}$ and $P_{2}$’s valuations; no finite number of
cut and evaluation queries is guaranteed to find it. Kurokawa et al. (2013)
found that no strategyproof, envy-free algorithm for cake cutting with
piecewise uniform valuation functions using a bounded number of queries
exists; it is possible a similar result is true for chore division.

## References

  * Steinhaus [1949] Hugo Steinhaus.  The problem of fair division.  _Econometrica_ , 17:315–319, 1949.
  * Brams and Taylor [1995] Steven J Brams and Alan D Taylor.  An envy-free cake division protocol.  _The American Mathematical Monthly_ , 102(1):9–18, 1995.
  * Peterson and Su [2009] Elisha Peterson and Francis Edward Su.  N-person envy-free chore division.  _arXiv preprint arXiv:0909.0303_ , 2009.
  * Bogomolnaia et al. [2017] Anna Bogomolnaia, Hervé Moulin, Fedor Sandomirskiy, and Elena Yanovskaya.  Competitive division of a mixed manna.  _Econometrica_ , 85(6):1847–1871, 2017.
  * Segal-Halevi [2017] Erel Segal-Halevi.  Fairly dividing a cake after some parts were burnt in the oven.  _arXiv preprint arXiv:1704.00726_ , 2017.
  * Mossel and Tamuz [2010] Elchanan Mossel and Omer Tamuz.  Truthful fair division.  In _International Symposium on Algorithmic Game Theory_ , pages 288–299. Springer, 2010.
  * Maya and Nisan [2012] Avishay Maya and Noam Nisan.  Incentive compatible two player cake cutting.  In _International Workshop on Internet and Network Economics_ , pages 170–183. Springer, 2012.
  * Chen et al. [2013] Yiling Chen, John K Lai, David C Parkes, and Ariel D Procaccia.  Truth, justice, and cake cutting.  _Games and Economic Behavior_ , 77(1):284–297, 2013.
  * Aziz and Ye [2014] Haris Aziz and Chun Ye.  Cake cutting algorithms for piecewise constant and piecewise uniform valuations.  In _International conference on web and internet economics_ , pages 1–14. Springer, 2014.
  * Robertson and Webb [1998] Jack Robertson and William Webb.  _Cake-cutting algorithms: Be fair if you can_.  AK Peters/CRC Press, 1998.
  * Aziz and Mackenzie [2016] Haris Aziz and Simon Mackenzie.  A discrete and bounded envy-free cake cutting protocol for any number of agents.  In _2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 416–427. IEEE, 2016.
  * Dehghani et al. [2018] Sina Dehghani, Alireza Farhadi, MohammadTaghi HajiAghayi, and Hadi Yami.  Envy-free chore division for an arbitrary number of agents.  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 2564–2583. SIAM, 2018.
  * Kurokawa et al. [2013] David Kurokawa, John Lai, and Ariel Procaccia.  How to cut a cake before the party ends.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 27, pages 555–561, 2013.


∎

11institutetext: R. Aaij 22institutetext: D. H. Cámpora Pérez 33institutetext:
Nikhef National Institute for Subatomic Physics, Amsterdam, Netherlands
44institutetext: J. Albrecht 55institutetext: L. Funke 66institutetext: H.
Stevens 77institutetext: Fakultät Physik, Technische Universität Dortmund,
Dortmund, Germany 88institutetext: M. Belous 99institutetext: N. Kazeev
1010institutetext: S. Popov 1111institutetext: A. Ustyuzhanin
1212institutetext: National Research University Higher School of Economics,
Moscow, Russia 1313institutetext: M. Belous 1414institutetext: N. Kazeev
1515institutetext: D. Pliushchenko 1616institutetext: S. Popov
1717institutetext: A. Ustyuzhanin 1818institutetext: Yandex School of Data
Analysis, Moscow, Russia 1919institutetext: P. Billoir 2020institutetext: D.
vom Bruch 2121institutetext: V. V. Gligorov 2222institutetext: F. Reiss
2323institutetext: R. Quagliani 2424institutetext: LPNHE, Sorbonne Université,
Paris Diderot Sorbonne Paris Cité, CNRS/IN2P3, Paris, France
2525institutetext: T. Boettcher 2626institutetext: D. C. Craik
2727institutetext: M. Williams 2828institutetext: Massachusetts Institute of
Technology, Cambridge, United States 2929institutetext: A. Brea Rodríguez
3030institutetext: A. Casais Vidal 3131institutetext: D. Martínez Santos
3232institutetext: Instituto Galego de Física de Altas Enerxías (IGFAE),
Universidade de Santiago de Compostela, Santiago de Compostela, Spain
3333institutetext: D. H. Cámpora Pérez 3434institutetext: Faculty of Science
and Engineering, Maastricht University, Maastricht, Netherlands
3535institutetext: P. Fernandez Declara 3636institutetext: F. Pisani
3737institutetext: R. Schwemmer 3838institutetext: European Organization for
Nuclear Research (CERN), Geneva, Switzerland 3939institutetext: P. Fernandez
Declara 4040institutetext: Department of Computer Science and Engineering,
University Carlos III of Madrid, Madrid, Spain 4141institutetext: B. Jashal
4242institutetext: C. Sánchez Mayordomo 4343institutetext: Instituto de Física
Corpuscular, Centro Mixto Universidad de Valencia - CSIC, Valencia, Spain
4444institutetext: F. Pisani 4545institutetext: INFN Sezione di Bologna,
Bologna, Italy 4646institutetext: F. Pisani 4747institutetext: Università di
Bologna, Bologna, Italy 4848institutetext: D. Pliushchenko 4949institutetext:
National Research University Higher School of Economics, Saint-Petersburg,
Russia 5050institutetext: S. Popov 5151institutetext: A. Ustyuzhanin
5252institutetext: National University of Science and Technology MISIS,
Moscow, Russia 5353institutetext: M. Rangel 5454institutetext: Instituto de
Física, Universidade Federal do Rio de Janeiro (UFRJ), Rio de Janeiro, Brazil
5555institutetext: M. Sokoloff 5656institutetext: University of Cincinnati,
Cincinnati, OH, United States 5757institutetext: X. Vilasís Cardona
5858institutetext: DS4DS, la Salle, Universitat Ramon Llull, Barcelona, Spain

# Allen: A high level trigger on GPUs for LHCb

R. Aaij * Corresponding authors<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>J. Albrecht  M. Belous  P. Billoir  T. Boettcher  A. Brea
Rodríguez  D. vom Bruch  D. H. Cámpora Pérez  A. Casais Vidal  D. C. Craik  P.
Fernandez Declara  L. Funke  V. V. Gligorov  B. Jashal  N. Kazeev  D. Martínez
Santos  F. Pisani  D. Pliushchenko  S. Popov  R. Quagliani  M. Rangel  F.
Reiss  C. Sánchez Mayordomo  R. Schwemmer  M. Sokoloff  H. Stevens  A.
Ustyuzhanin  X. Vilasís Cardona  M. Williams

(Received: 18 December 2019 / Accepted: 3 April 2020)

###### Abstract

We describe a fully GPU-based implementation of the first level trigger for
the upgrade of the LHCb detector, due to start data taking in 2021. We
demonstrate that our implementation, named Allen, can process the 40 Tbit/s
data rate of the upgraded LHCb detector and perform a wide variety of pattern
recognition tasks. These include finding the trajectories of charged
particles, finding proton-proton collision points, identifying particles as
hadrons or muons, and finding the displaced decay vertices of long-lived
particles. We further demonstrate that Allen can be implemented in around 500
scientific or consumer GPU cards, that it is not I/O bound, and can be
operated at the full LHC collision rate of 30 MHz. Allen is the first complete
high-throughput GPU trigger proposed for a HEP experiment.

###### Keywords:

GPU real time data selection trigger LHCb

††journal: Computing and Software for Big Science

##  1 Introduction

The LHCb detector LHCb-DP-2014-002  at CERN is currently being upgraded for
Run 3 of the LHC. It is due to begin data taking in 2021 at an instantaneous
luminosity of $\mathcal{L}$ $=2\times
10^{33}\,\textrm{cm}^{-2}\,\textrm{s}^{-1}$, corresponding to an average of
around 6 proton-proton ($pp$) collisions per LHC bunch crossing. At this
luminosity, the rates of beauty and charm hadrons, which are of interest for
most LHCb analyses, reach the MHz level in the LHCb detector’s geometrical
acceptance Fitzpatrick2014 . The majority of them decays into fully hadronic
final states. Thus, efficiently reducing the output data rate requires finding
charged particle trajectories (tracking) at the first level of the real-time
reconstruction (trigger).

As most of LHCb’s data comes from its tracking detectors, which are
responsible for the majority of readout channels, the upgraded detector
operates a triggerless readout, in which all subdetectors are read out at the
full bunch crossing rate of 30 MHz, or a maximum data rate of 40 Tbit/s. Event
selection relies on two software stages. In the first stage, called HLT1,
events are primarily selected using inclusive one- and two-track based
algorithms, in some cases requiring the track to be identified as a muon. At
this stage, the close to optimal alignment and calibration constants from the
previous run are used. HLT1 allows for an efficient reduction of the event
rate by a factor 30 to 60, depending on the desired working point. In the
second stage, called HLT2, the detector is aligned and calibrated in near-
real-time and the remaining events undergo offline-quality track
reconstruction, full particle identification and track fitting. Because of the
high signal rate, HLT2 does not only classify bunch crossings (events) as
interesting or uninteresting. Rather in most cases HLT2 identifies a decay of
interest and associates it to one of the reconstructed $pp$ collisions.
Subsequently for most physics analyses HLT2 outputs a reduced event format one
order of magnitude smaller than the raw data, consisting of only objects
related to the decay of interest and the associated $pp$ collision, following
the approach pioneered in Run 2 LHCb-DP-2016-001 ; Aaij:2019uij ;
LHCbCollaboration:2319756 . This approach relies on the near-real-time
detector alignment and calibration to maintain the ultimate detector
performance without the need for costly “offline” reprocessing of the data,
and results in a total output data volume of 80 Gbit/s.

Performing full track reconstruction at 30 MHz and 40 Tbit/s poses a
significant computing challenge. In the baseline proposal of the upgrade data
acquisition system Albrecht:2310579 ; LHCb-TDR-016 , data from the different
LHCb subdetectors are received and combined to full events by about 250 event
building x86 servers. Complete events are then sent to a separate “event
filter farm” (EFF) of x86 servers, where both the HLT1 and HLT2 stages are
executed. Fig 1 shows this sequence of data processing units.

Figure 1: In the baseline proposal for the upgraded LHCb data acquisition
system, x86 event building units receive data from the subdetectors and build
events by sending and receiving event fragments over a 100G Infiniband (IB)
network. The full data stream of built events is sent to x86 event filter
servers to process both stages of the high level trigger.

As track reconstruction is an inherently parallel problem, tracking algorithms
can be designed to map well to the many-core architecture of graphics
processing units (GPUs). Furthermore, GPUs map well onto LHCb’s data
acquisition architecture, because the event building servers which host the
$\sim 500$ FPGA cards required to receive data from the detector at 30 MHz can
also host two GPU cards each. Therefore, if the track reconstruction required
for HLT1 could be processed with at most 500 GPUs, LHCb could execute HLT1
already inside the event building servers and reduce the data volume by a
factor 30-60, significantly reducing the networking cost associated with
sending data to the EFF.

In recent years, several particle physics experiments have studied the
performance of track reconstruction on GPUs. So far only the ALICE experiment
at CERN has employed GPUs in their trigger, where tracks from a single
subdetector are reconstructed on the GPU, but data reduction occurs on x86
CPUs Rohr_2012 . All other R&D efforts are intended for future experiments or
upgrades. In most proposals, data from a single sub-detector is analyzed on
the GPU at a significantly lower data rate than 40 Tbit/s Sen2015 ; Funke2014
; VomBruch2017 . For some, the GPU coprocessor performs track reconstruction,
but event selection or data reduction occur on x86 CPUs Funke2014 . In other
cases, event selection for a single physics signature runs on the GPU Sen2015
; VomBruch2017 . For Run 3, ALICE plans to perform track reconstruction of
more than one subdetector and data compression on the GPU, at a data rate of 5
Tbit/s Rohr2017 .

In this paper, we show that for LHCb it is possible to execute a full trigger
stage, including track reconstruction for several subdetectors and a variety
of physics selections, at 40 Tbit/s on about 500 GPUs. We describe our
implementation, named Allen after Frances E. Allen, following the LHCb
convention of naming software projects after renowned scientists.

##  2 Mapping the first trigger stage to graphics processing units

###  2.1 Characteristics of graphics processing units

Developed for the graphics processing pipeline, GPUs excel at data parallel
tasks under the SIMT paradigm Lindholm2008 . An algorithm executed on the GPU
is called a kernel. Every kernel is launched with many threads on the GPU
executing the same instruction on different parts of the data in parallel,
independently from each other. These threads are grouped into blocks within a
grid, as illustrated in Fig 2. Threads within one block share a common memory
and can by synchronized, while threads from different blocks cannot
communicate. The threads are mapped onto the thousands of cores available on
modern GPUs for processing.

Figure 2: Threads are grouped into blocks, forming a grid that executes one
kernel on the GPU.

Typically, a GPU is connected to its CPU host server via a PCIe connection,
which sets a limit on the bandwidth between the GPU and the CPU: 16 lanes of
PCIe 3.0 and PCIe 4.0 provide 128 Gbit/s and 256 Gbits/s, respectively. From
these parameters we conclude that 500 GPUs are able to consume the 40 Tbit/s
data rate of the upgraded LHCb detector. The total memory on a GPU is on the
order of hundreds of Gbits nowadays. Consequently, 500 GPUs should also be
able to process the full HLT1 sequence if enough data processing tasks fit
into GPU memory at the same time and if the tasks can be sufficiently
parallelized to fully unlock the TFLOPs theoretically available on the GPU.

###  2.2 The Allen concept

Figure 3: In the GPU-enhanced proposal for the upgraded LHCb data acquisition
system x86 event building units receive data from the subdetectors and build
events by sending and receiving event fragments over a 100G Infiniband (IB)
network. The same x86 servers also host GPUs which process HLT1. Only events
selected by HLT1 are sent to the x86 servers processing HLT2. The data rate
between the two x86 server farms is therefore reduced by a factor 30 - 60.

In our proposal, a farm of GPUs processes the full data stream, as shown in
Fig 3, which can be compared to the baseline x86-only architecture of Fig 1.
Every GPU receives complete events from an event building unit and handles
several thousand events at once. Raw detector data is copied to the GPU, the
full HLT1 sequence is processed on the GPU and only selection decisions and
objects used for the selections, such as tracks and primary vertices, are
copied back to the CPU. This approach is motivated by the following
considerations:

  * •

LHCb raw events have an average size of 100 kB. When copying raw data to the
GPU, the PCIe connection between the CPU and the GPU poses no limitation to
the system, even when several thousand events are processed in parallel.

  * •

Since single events are rather small, several thousand events are required to
make full use of the compute power of modern GPUs.

  * •

As the full algorithm sequence is processed on the GPU, no copies between the
CPU and the GPU are required, apart from the raw input and selection output,
and quantities needed to define the grid sizes of individual kernels.

  * •

Intra-GPU communication is not required because events are independent from
one another and small enough in memory footprint to be processed on a single
GPU.

The project is implemented in CUDA, Nvidia’s API for programming its GPUs cuda
. Allen111https://gitlab.cern.ch/lhcb/Allen Version 0.8 was used for the
results in this publication. includes a custom scheduler and GPU memory
manager, which will be described in a companion publication.

###  2.3 Main algorithms of the first trigger stage

A schematic of the upgraded LHCb forward spectrometer is shown in Fig 4. The
information from the tracking detectors and the muon system is required for
HLT1 decisions, as described in section 1. The tracking system consists of the
vertex detector (Velo) LHCb-TDR-013  and the upstream tracker (UT) LHCb-
TDR-015  before the magnet and tracking stations behind the magnet which are
made of scintillating fibres (SciFi) LHCb-TDR-015 . The measurements from the
muon detector are used to perform muon identification. The LHCb coordinate
system is such that z is along the beamline, y vertical and x horizonal. The
dipole magnet bends charged particle trajectories along x. Fig 4 indicates the
magnitude of the y-component of the magnetic field, which extends into the UT
and SciFi regions. As a consequence, tracks in the Velo detector form straight
lines, while those in the UT and SciFi detectors are slightly bent.

Figure 4: Upgraded LHCb detector. The y-component of the magnetic field
$B_{y}$ is overlaid to visualize in which parts of the detector trajectories
are bent. The maximum $B_{y}$ value is 1.05 T.

The following recurrent tasks are performed at various stages of the HLT1
sequence:

  * •

Decoding the raw input into coordinates in the LHCb global coordinate system.

  * •

Clustering of measurements caused by the passage of the same particle into
single coordinates (“hits”), depending on the detector type.

  * •

Finding combinations of hits originating from the same particle trajectory
(pattern recognition).

  * •

Describing the track candidates from the pattern recognition step with a track
model (track fitting).

  * •

Reconstructing primary and secondary vertices from the fitted tracks (vertex
finding).

Raw data Global Event Cut Velo decoding and clustering Velo tracking Simple
Kalman filter Find primary vertices UT decoding UT tracking SciFi decoding
SciFi tracking Parameterized Kalman filter Muon decoding Muon ID Find
secondary vertices Select events Selected events

Figure 5: Full HLT1 sequence implemented in CUDA to run on GPUs. Raw data is
copied as input to the GPU, selected events are copied back to the host CPU as
output. Rhombi represent algorithms reducing the event rate, while rectangles
represent algorithms processing data.

Fig 5 shows the full HLT1 sequence. In most cases, a single event is assigned
to one block, while intra-event parallelism is mapped to the threads within
one block. This ensures that communication is possible among threads
processing the same event. Typically, the raw input is segmented by readout
unit (for example a module of the vertex detector), so naturally the decoding
can be parallelized among the readout units. During the pattern recognition
step, many combinations of hits are tested and those are processed in
parallel. The track fit is applied to every track and therefore parallelizable
across tracks. Similarly, extrapolating tracks from one subdetector to the
next is executed in parallel for all tracks. Finally, combinations of tracks
are built when finding vertices and those can be treated in parallel.

Initially, events are preselected by a Global Event Cut (GEC) based on the
size of the UT and SciFi raw data, removing the 10 % busiest events. This
selection is not essential for the viability of the proposed GPU architecture.
It is also performed in the baseline x86 processing LHCb-TDR-016 , because
very busy events have a less efficient detector reconstruction and their
additional physics value to LHCb is not proportionate to the computing cost of
reconstructing them. The subsequent elements of the HLT1 sequence are now
described in turn.

####  2.3.1 Velo detector

The Velo detector consists of 26 planes of silicon pixel sensors placed around
the interaction region. Its main purpose lies in reconstructing the $pp$
collisions (primary vertices or PVs) and in creating seed tracks to be further
propagated through the other LHCb detectors. The Velo track reconstruction is
fully described in an earlier publication CamporaPerez2019  and is recapped
here for convenience.

The reconstruction begins by grouping measurements caused by the passage of a
particle within each silicon plane into clusters, an example of a more general
process known as connected component labeling. Allen uses a clustering
algorithm employing bit masks, which searches for clusters locally in small
regions. Every region can be treated independently, allowing for parallel
processing.

Straight-line tracks are reconstructed by first forming seeds of three hits
from consecutive layers (“triplets”), and then extending these to the other
layers in parallel. We exploit the fact that prompt particles produced in $pp$
collisions traverse the detector in lines of constant $\phi$ angle (within a
cylindrical coordinate system where the cylinder axis coincides with the LHC
beamline) and sort hits on every layer by $\phi$ for fast look-up when
combining hits to tracks.

Velo tracks are fitted with a simple Kalman filter Kalman1960  assuming that
the x- and y-components are independent from one another and assigning a
constant average transverse momentum of 400 MeV to all tracks for the noise
contribution from multiple scattering.

Finally, we search for PVs in a histogram of the point of closest approach of
tracks to the beamline, where a cluster indicates a PV candidate. We refrain
from a one-to-one mapping between a track and a vertex, which would introduce
dependencies between the fitting of individual vertex candidates and would
require sequential processing. Instead, every track is assigned to every
vertex based on a weight, so that all candidates can be fitted in parallel.

####  2.3.2 UT detector

Four layers of silicon strip detectors make up the UT detector, the strips of
the two outer layers are aligned vertically, the two inner layers are tilted
by +5∘ and $-5^{\circ}$ around the z-axis respectively. Since more than 75 %
of the hits consist of only one fired strip, no clustering is performed in
this subdetector. The UT hits are decoded into regions based on their
x-coordinate. Every region is then sorted by the y-coordinate. This allows for
a fast look-up of hits around the position of an extrapolated Velo track. Velo
tracks are extrapolated to the UT detector based on a minimum momentum cut-off
of $3$ GeV, resulting in a maximal bending allowed between the Velo and UT
detectors.There is no requirement on the transverse momentum. Subsequently, UT
hits are assigned to Velo tracks and the track momentum is determined from the
bending between the Velo and UT fitted straight-line track segments with a
resolution of about 20 %. The UT decoding and tracking algorithms are
described in more detail in Ref. 8756134 .

####  2.3.3 SciFi detector

The SciFi detector consists of three stations with four layers of
scintillating fibres each, where the four layers of every station are in x-u-
v-x configuration. The u- and v-layers are tilted by +5∘ and $-5^{\circ}$,
respectively, while the x-layers are vertical. The clustering of the SciFi
hits and sorting along x is performed on the readout board; therefore, sorted
clusters are obtained directly when decoding.

Tracks passing through both the Velo and UT detectors are extrapolated to the
SciFi detector using a parameterization based on the track direction and the
momentum estimate obtained after the UT tracking. This avoids loading the
large magnetic field map into GPU memory. A search window defined by the UT
track properties and a maximum number of allowed hits is determined for every
UT track and every SciFi layer.

The hit efficiency of the scintillating fibres is 98–99%; therefore, several
seeds are allowed per UT track, so that the track reconstruction efficiency is
not limited by requiring hits from specific layers. Seeds are formed combining
triplets of hits from within the search windows of one x-layer in each of the
three SciFi stations. The curvature of tracks inside the SciFi region due to
the residual magnetic field tails from the LHCb dipole is taken into account
when selecting the best seeds. Only the seeds with the lowest $\chi^{2}$
relative to a parameterized description of the track within the SciFi volume
are then extended by adding hits from the remaining x-layers, using the same
track description. Since only the information of three hits is used for the
$\chi^{2}$, its discriminating power is limited. Therefore, multiple track
seeds are processed per UT track.

The magnetic field inside the SciFi detector can be expressed as
$B_{y}(z)=B_{0}+B_{1}\cdot z$ and it is found that at first order
$\frac{B_{1}}{B_{0}}$ is a constant. Using this parameterization, tracks are
projected onto the remaining x and u/v-layers, and hits that deviate the least
from the reference trajectory, within a track-dependent acceptance, are added.
Only the U/V-layers provide information on the track motion in the y-z plane.
Thus, a parameterization accounting for the small curvature in the y-z plane
is also taken into account in the track model, once all hits have been added.

Finally, a least means square fit is performed both in →x and →y. Every track
is assigned a weight based on the normalized x-fit $\chi^{2}$, y-fit
$\chi^{2}$, and the number of hits in the track. Only the best track is
accepted per UT track, reducing fake tracks as much as possible.

####  2.3.4 Muon detector

The muon system LHCb-TDR-014  consists of four multiwire proportional chambers
interleaved with iron walls. Every station is divided into four regions with
chambers of different granularity. Hits are read out with pads and strips,
while strips from the same station can overlap to give a more accurate
position measurement. During the decoding of muon measurements, such crossing
strips are combined into a single hit. For muon identification, the “isMuon”
algorithm described in Ref. LHCb-DP-2013-001  is employed: tracks are
extrapolated from the SciFi to the muon stations and muon hits are matched to
a track within a region defined by the track properties. Depending on the
track momentum, hits in different numbers of stations are required for a track
to be tagged as a muon.

####  2.3.5 Kalman filter

A Kalman filter is applied to all tracks to improve the impact parameter
resolution, where the impact parameter (IP) is the distance between the point
of closest approach of a track and a PV. The nominal LHCb Kalman filter uses a
Runge-Kutta extrapolator to propagate track states between measurements and a
detailed detector description to determine noise due to multiple scattering.
In order to increase throughput and limit memory overhead, these costly
calculations are replaced with parameterizations. Two versions of the
parameterized Kalman filter are implemented in Allen: one which takes into
account the whole detector and one which fits only the Velo track segment but
using the estimated momentum from the full track passing through the Velo, UT
and SciFi detectors. Since the impact parameter is mainly influenced by the
measurements nearest to the interaction region, the Velo-only Kalman filter is
used in the HLT1 sequence. This results in a significant computing speedup
compared to applying the full Kalman filter.

####  2.3.6 Selections

Given the momentum, impact parameter and position information from the track
fit as well as the muon identification, selections are applied on single
tracks and two-track vertices similarly to the HLT1 selections used in Run2 of
LHCb Aaij:2652801 ; Likhomanenko:2015aba ; BBDT . Secondary vertices are
fitted in parallel from combinations of two tracks each, providing a momentum
and mass estimate for the hypothetical decaying particle, assigning the pion
mass hypothesis to all tracks except for those identified as muons, for which
the muon mass is assigned. The following five selection algorithms, which
cover the majority of the LHCb physics programme and which are similar to
lines accounting for about 95 % of the HLT1 trigger rate in Run 2 Aaij:2652801
, are implemented in Allen:

  * •

1-Track: A single displaced track with $p_{\mathrm{T}}>1$ GeV.

  * •

2-Track: A two-track vertex with significant displacement and $pt>700$ MeV for
both tracks.

  * •

High-$p_{T}$ muon: A single muon with $p_{\mathrm{T}}>10$ GeV for electroweak
physics.

  * •

Displaced dimuon: A displaced dimuon vertex with $p_{\mathrm{T}}>500$ MeV for
both tracks.

  * •

High-mass dimuon: A dimuon vertex with mass near or larger than the $J/\Psi$
mass with $p_{\mathrm{T}}>750$ MeV for both tracks.

##  3 Results

(a)  (b)

(c)  (d)

(e)  (f)

Figure 6: Track reconstruction efficiency versus transverse momentum
$p_{\mathrm{T}}$ (left) and momentum $p$ (right) of reconstructed tracks
passing through the Velo (a, b), Velo and UT (c, d), Velo, UT and SciFi
detectors (e, f) with respect to reconstructible non-electron tracks passing
through the Velo, UT and SciFi detectors and produced from $B$ decays within
the pseudorapidity coverage of the LHCb detector, $2<\eta<5$, for all signal
samples combined. The $p_{\mathrm{T}}$ and $p$ distributions are overlaid as
histograms.

The performance of Allen is studied both with respect to the computing
throughput per GPU and the physics outcome in terms of track reconstruction
efficiency and event selection efficiency for various representative LHCb
analyses.

###  3.1 Physics performance

For physics studies, simulated samples enhanced with decay channels of
interest for the LHCb physics program are employed, namely a combination of
5000 events of each of the following decays:
${{B}^{0}}\rightarrow{{K}^{*0}}{\mu^{+}\mu^{-}}$,
${{B}^{0}}\rightarrow{{K}^{*0}}e^{+}e^{-}$,
${{B}^{0}_{s}}\rightarrow\phi\phi$,
$D^{+}_{s}\rightarrow{{K}^{+}}{{K}^{-}}{{\pi}^{+}}$ and
$Z\rightarrow\mu^{+}\mu^{-}$. Efficiencies of track and vertex reconstruction,
muon identification and trigger selections, as well as the momentum resolution
are determined directly within the Allen framework.

In LHCb, tracks are defined as correctly reconstructed if at least 70 % of the
hits match those of the Monte Carlo (MC) particle associated to the track in
simulation. Only MC particles resulting in the following minimum numbers of
hits are considered as “reconstructible tracks”: at least one hit in at least
three different Velo modules and at least one hit in an x- and a u/v- layer in
the UT detector and every station in the SciFi detector. Fig 6 shows the track
reconstruction efficiency of correctly reconstructed tracks in the Velo (top),
Velo and UT (middle), Velo, UT and SciFi (bottom) detectors versus transverse
momentum $p_{\mathrm{T}}$ and momentum $p$ with respect to reconstructible
tracks originating from $B$ decays. A reconstructed PV is matched to a
simulated PV if the distance is less than five times the uncertainty of the
reconstructed PV along the z-axis. Fig 7 shows the reconstruction efficiency
of PVs versus the track multiplicity of the MC PV. As displayed in Fig 8, a
relative momentum resolution better than 1 % is achieved which is sufficient
for the selections of HLT1 and can be compared to a resolution of 0.5-1 %
obtained from offline-quality track reconstruction during Run 2. The muon
identification efficiency is shown in Fig 9. It is determined with respect to
”reconstructible muons”, defined as reconstructed tracks which were matched to
a muon MC particle.

Figure 7: PV reconstruction efficiency versus track multiplicity of the MC PV
for minimum bias events. The track multiplicity distribution is overlaid as a
histogram. Figure 8: Relative momentum resolution of tracks passing through
the Velo, UT and SciFi detectors versus momentum for all signal samples
combined. Points represent the mean, error bars the width of a Gaussian
distribution fitted to the resolution in every momentum slice. The momentum
distribution is overlaid as a histogram. Figure 9: Muon identification
efficiency versus momentum for tracks passing through the Velo, UT and SciFi
detectors with respect to all reconstructible muons (explained in the text),
for all signal samples combined. The momentum distribution is overlaid as a
histogram. Figure 10: Efficiency of the 1-Track and 2-Track trigger lines when
calculating the IP $\chi^{2}$ (see text for definition) from tracks fitted
with the simple and parameterized Kalman filter, using the
${{B}^{0}_{s}}\rightarrow\phi\phi$ sample. Varying the selection criteria of
the IP $\chi^{2}$ results in rate and efficiency changes. The efficiency is
calculated from subsets of the sample, the central value and error band
correspond to the mean and standard deviation respectively.

Finally, the trigger rates for the five selections are shown in Table 1. The
total HLT1 output rate is about 1 MHz, therefore, reducing the event rate by a
factor 30. For this output rate, the selection efficiencies for various decay
channels are given in Table 2. We quote the efficiency of the GEC, as well as
for “TIS” events, with at least one passing trigger candidate not associated
with a true signal decay product, and for “TOS” events, where the signal decay
products must pass the trigger selection themselves.

Fig 10 illustrates the difference in efficiency and rate for the 1-Track and
2-Track trigger lines for the ${{B}^{0}_{s}}\rightarrow\phi\phi$ sample
between fitting tracks with the simple Kalman filter versus the parameterized
Kalman filter, when varying the selection criteria of the IP $\chi^{2}$. The
IP $\chi^{2}$ is defined as the difference between the $\chi^{2}$ of the PV
reconstructed with and without the track under consideration and serves as
estimate for the track displacement. Especially the efficiency of the 2-Track
line improves when using the parameterized Kalman filter, since the momentum
threshold for individual tracks is lower compared to the 1-Track line.

Trigger | Rate [kHz]
---|---
1-Track | 215 $\pm$ 18
2-Track | 659 $\pm$ 31
High-$p_{T}$ muon | 5 $\pm$ 3
Displaced dimuon | 74 $\pm$ 10
High-mass dimuon | 134 $\pm$ 14
Total | 999 $\pm$ 38
Table 1: Rates of the five trigger selections implemented in Allen and the total HLT1 output rate, determined with minimum bias events. Signal | GEC | TIS -OR- TOS | TOS | $\mathrm{GEC}\times\mathrm{TOS}$
---|---|---|---|---
${{B}^{0}}\rightarrow{{K}^{*0}}{\mu^{+}\mu^{-}}$ | 88.9 $\pm$ 2.0 | 90.6 $\pm$ 2.0 | 88.8 $\pm$ 2.1 | 79.0 $\pm$ 2.6
${{B}^{0}}\rightarrow{{K}^{*0}}e^{+}e^{-}$ | 84.2 $\pm$ 2.7 | 69.1 $\pm$ 3.8 | 61.7 $\pm$ 4.0 | 52.0 $\pm$ 3.8
${{B}^{0}_{s}}\rightarrow\phi\phi$ | 83.2 $\pm$ 2.6 | 75.8 $\pm$ 3.2 | 68.5 $\pm$ 3.5 | 57.0 $\pm$ 3.4
$D^{+}_{s}\rightarrow{{K}^{+}}{{K}^{-}}{{\pi}^{+}}$ | 82.5 $\pm$ 3.6 | 58.5 $\pm$ 5.1 | 42.6 $\pm$ 5.1 | 35.1 $\pm$ 4.5
$Z\rightarrow\mu^{+}\mu^{-}$ | 77.8 $\pm$ 1.2 | 99.5 $\pm$ 0.2 | 99.5 $\pm$ 0.2 | 77.4 $\pm$ 1.2
Table 2: Efficiencies of the total HLT1 selection. The TIS -OR- TOS and TOS
efficiencies are calculated using events passing the GEC (definitions for TIS,
TOS and GEC are in the text). All efficiencies and their uncertainties are
quoted in percentages and are determined from the different signal samples,
with selections resulting in the rates given in Table 1. Signal events are
selected with the following criteria: b and c hadrons have a
$p_{\mathrm{T}}>2$ GeV and a lifetime $\tau>0.2$ ps. Children of b and c
hadrons have $p_{\mathrm{T}}>200~{}$MeV. Children of Z bosons have
$p_{\mathrm{T}}>20~{}$GeV.

###  3.2 Computing performance

For throughput studies, simulated samples of minimum bias events are used,
representing the physics conditions expected for Run 3. The computing
performance is compared among different Nvidia GPU cards. In all cases, Allen
is compiled with gcc 8.2 gcc  and CUDA 10.1. The HLT1 sequence is run on a
configurable number of concurrent threads. Each thread employs a GPU stream to
asynchronously execute kernels and perform data transmission between CPU and
GPU, such that memory transmissions do not impact throughput. The timer is
started prior to processing a sequence in the first stream, and it is stopped
after all streams have returned.

For most measurements, 12 thread-stream pairs with 1000 events each were
processed 100 times, allocating 700 MB of GPU memory for every stream. Only in
the case of the GTX 670, GTX 680 and the GTX 1060 6GB two thread-stream pairs
were used instead. The measurement was performed 10 times with different sets
of 1000 events each. The mean and standard deviation of the 10 measurements
are shown for various Nvidia GPU cards as a function of their theoretical peak
32-bit FLOPS performance in Fig 11. The minimum rate per GPU necessary for
processing the 30 MHz input rate with 500 GPUs is 60 kHz. Three cards surpass
this threshold with a margin, namely the RTX 2080 Ti, the V100 and the Quadro
RTX 6000, currently the best cards in the consumer, scientific and
professional lines of Nvidia, respectively. Analyzing the performance as a
function of theoretical peak 32-bit FLOPS performance reveals how the
application scales to the hardware under study. The linear dependence visible
in Fig 11 shows that the Allen code makes efficient use of the computing
architecture and is likely to scale well to future generations of GPU
processors.

The throughput as a function of the occupancy in the SciFi detector is
depicted in Fig 12. The slower throughput decrease in the high occupancy
region gives confidence that Allen can be adapted to real data taking
conditions, where the detector occupancy might be higher than in simulation
(as observed consistently during Runs 1 and 2). If the GEC removing the 10%
busiest events is deactivated and all events are processed, the Allen
throughput drops by about 20%.

Figure 11: Allen throughput on various GPUs with respect to their reported
peak 32-bit FLOPS performance. The mean and standard deviation of 10
measurements with different sets of 1000 events each are shown in the figure,
with the measurement setup as described in the text. Figure 12: Throughput of
the Allen sequence as a function of the SciFi raw data volume, which is
proportional to the SciFi occupancy. The measurement setup is described in the
text. For every data point, 1000 different events within the range of the
SciFi raw data volume bin are processed. The GEC removing the 10% busiest
events was deactivated for these measurements.

##  4 Conclusions

We present Allen, an implementation of the first trigger stage of LHCb for Run
3 entirely on GPUs. This is the first complete high-throughput GPU trigger
proposed for a HEP experiment. Allen covers the majority of the LHCb physics
programme, using an analogous reconstruction and selection sequence as in Run
2. The demonstrated event throughput shows that the full HLT1 sequence can run
on about 500 of either one of the RTX 2080 Ti, V100 or Quadro RTX 6000 Nvidia
GPU cards. Consequently, the GPUs can be hosted by the event building servers,
significantly reducing the network cost associated with sending HLT1 output to
the EFF. We show that the performance in terms of track and vertex
reconstruction efficiencies, muon identification and momentum resolution are
sufficient for efficient trigger selections for analyses representative of the
LHCb physics programme.

## Acknowledgements

We would like to thank N. Neufeld and T. Colombo for many fruitful
discussions. We also thank the LHCb RTA team for supporting this publication
and reviewing this work. We thank the technical and administrative staff at
the LHCb institutes. We acknowledge support from CERN and from the national
agencies: CAPES, CNPq, FAPERJ and FINEP (Brazil); MOST and NSFC (China);
CNRS/IN2P3 (France); BMBF, DFG and MPG (Germany); INFN (Italy); NWO
(Netherlands); MNiSW and NCN (Poland); MEN/IFA (Romania); MSHE (Russia);
MinECo (Spain); SNSF and SER (Switzerland); NASU (Ukraine); STFC (United
Kingdom); DOE NP and NSF (USA). We acknowledge the computing resources that
are provided by CERN, IN2P3 (France), KIT and DESY (Germany), INFN (Italy),
SURF (Netherlands), PIC (Spain), GridPP (United Kingdom), RRCKI and Yandex LLC
(Russia), CSCS (Switzerland), IFIN-HH (Romania), CBPF (Brazil), PL-GRID
(Poland) and OSC (USA). We are indebted to the communities behind the multiple
open-source software packages on which we depend. Individual groups or members
have received support from AvH Foundation (Germany); EPLANET, Marie
Skłodowska-Curie Actions and ERC (European Union); ANR, Labex P2IO and OCEVU,
and Région Auvergne-Rhône-Alpes (France); Key Research Program of Frontier
Sciences of CAS, CAS PIFI, and the Thousand Talents Program (China); RFBR, RSF
and Yandex LLC (Russia); GVA, XuntaGal and GENCAT (Spain); the Royal Society
and the Leverhulme Trust (United Kingdom). J. Albrecht acknowledges support of
the European Research Council Starting grant PRECISION 714536. D. vom Bruch,
V. V. Gligorov, F. Reiss and R. Quagliani acknowledge support of the European
Research Council Consolidator grant RECEPT 724777. H. Stevens, L. Funke
acknowledge support of the Collaborative Research Center SFB 876. T. Boettcher
and M. Williams are supported by US NSF grant PHY-1912836. D. Craik is
supported by US NSF grants OAC-1836650 and PHY-1904160. A. Ustyuzhanin is
supported by the Russian Science Foundation grant agreement n∘ 19-71-30020. D.
Martínez Santos and A. Brea Rodríguez acknowledge support from the European
Research Council Starting grant BSMFLEET 639068.

## Conflict of Interest

The authors declare that they have no conflict of interest.

## References

  * (1) LHCb collaboration, R. Aaij et al. , _LHCb detector performance_ , Int. J. Mod. Phys. A30 (2015) 1530022
  * (2) C. Fitzpatrick and V. V. Gligorov, _Anatomy of an upgrade event in the upgrade era, and implications for the lhcb trigger_ , Tech. Rep. LHCb-PUB-2014-027. CERN-LHCb-PUB-2014-027, CERN, Geneva, 2014
  * (3) R. Aaij et al. , _Tesla: an application for real-time data analysis in High Energy Physics_ , Comput. Phys. Commun. 208 (2016) 35
  * (4) R. Aaij et al. , _A comprehensive real-time analysis model at the LHCb experiment_ , JINST 14 (2019) P04006
  * (5) LHCb Collaboration, _Computing Model of the Upgrade LHCb experiment_ , Tech. Rep. CERN-LHCC-2018-014. LHCB-TDR-018, CERN, Geneva, 2018
  * (6) J. Albrecht et al. , _Upgrade trigger & reconstruction strategy: 2017 milestone_, Tech. Rep. LHCb-PUB-2018-005. CERN-LHCb-PUB-2018-005, CERN, Geneva, 2018
  * (7) LHCb Collaboration, _LHCb Trigger and Online Technical Design Report_ , Tech. Rep. CERN-LHCC-2014-016, CERN, Geneva, 2018
  * (8) D. Rohr et al., _ALICE HLT TPC tracking of pb-pb events on GPUs_ , Journal of Physics: Conference Series 396 (2012) 012044
  * (9) P. Sen and V. Singhal, _Event selection for MUCH of CBM experiment using GPU computing_ , pp. 1–5, IEEE, 2015
  * (10) D. Funke et al., _Parallel track reconstruction in CMS using the cellular automaton approach_ , Journal of Physics: Conference Series 513 (2014) 052010
  * (11) D. vom Bruch, _Online Data Reduction using Track and Vertex Reconstruction on GPUs for the Mu3e Experiment_ , EPJ Web of Conferences 150 (2017) 00013
  * (12) D. Rohr, S. Gorbunov, and V. Lindenstruth, _GPU-accelerated track reconstruction in the ALICE High Level Trigger_ , Journal of Physics: Conference Series 898 (2017) 032030
  * (13) E. Lindholm, J. Nickolls, S. Oberman, and J. Montrym, _NVIDIA Tesla: A Unified Graphics and Computing Architecture_ , IEEE Micro 28 (2008) 39
  * (14) _CUDA Toolkit_ , https://docs.nvidia.com/cuda/
  * (15) LHCb collaboration, _LHCb VELO Upgrade Technical Design Report_ , Tech. Rep. CERN-LHCC-2013-021, CERN, Geneva, 2013
  * (16) LHCb collaboration, _LHCb Tracker Upgrade Technical Design Report_ , Tech. Rep. CERN-LHCC-2014-001, CERN, Geneva, 2014
  * (17) D. H. Cámpora Pérez, N. Neufeld, and A. Riscos Núñez, _A fast local algorithm for track reconstruction on parallel architectures_ , 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) (2019) 698
  * (18) R. E. Kalman, _A new approach to linear filtering and prediction problems_ , Journal of Basic Engineering 82 (1960) 35
  * (19) P. Fernandez Declara et al., _A parallel-computing algorithm for high-energy physics particle tracking and decoding using gpu architectures_ , IEEE Access 7 (2019) 91612
  * (20) LHCb collaboration, _LHCb PID Upgrade Technical Design Report_ , Tech. Rep. CERN-LHCC-2013-022, CERN, Geneva, 2013
  * (21) F. Archilli et al., _Performance of the muon identification at LHCb_ , JINST 8 (2013) P10020
  * (22) R. Aaij et al. , _Design and performance of the LHCb trigger and full real-time reconstruction in Run 2 of the LHC._ , JINST 14 (2018) P04013
  * (23) T. Likhomanenko et al., _LHCb Topological Trigger Reoptimization_ , J. Phys. Conf. Ser. 664 (2015) 082025
  * (24) V. V. Gligorov and M. Williams, _Efficient, reliable and fast high-level triggering using a bonsai boosted decision tree_ , JINST 8 (2013) P02013
  * (25) _GCC, the Gnu Compiler Collection_ , https://gcc.gnu.org