# DePa: Simple, Provably Efficient, and Practical Order Maintenance for Task
Parallelism

Sam Westrick  Department of Computer ScienceCarnegie Mellon
UniversityPittsburghPAUSA<EMAIL_ADDRESS>,  Larry Wang  Department of
Computer ScienceCarnegie Mellon UniversityPittsburghPAUSA
<EMAIL_ADDRESS>and  Umut A. Acar  Department of Computer
ScienceCarnegie Mellon UniversityPittsburghPAUSA

###### Abstract.

A number of problems in parallel computing require reasoning about the
dependency structure in parallel programs. For example, dynamic race detection
relies on efficient “on-the-fly” determination of dependencies between
sequential and parallel tasks (e.g. to quickly determine whether or not two
memory accesses occur in parallel). Several solutions to this “parallel order
maintenance” problem has been proposed, but they all have several drawbacks,
including lack of provable bounds, high asymptotic or practical overheads, and
poor support for parallel execution.

In this paper, we present a solution to the parallel order maintenance problem
that is provably efficient, fully parallel, and practical. Our
algorithm—called _DePa_ —represents a computation as a graph and encodes
vertices in the graph with two components: a _dag-depth_ and a _fork-path_. In
this encoding, each query requires $O(f/\omega)$ work, where $f$ is the
minimum dynamic nesting depth of the two vertices compared, and $\omega$ is
the word-size. In the common case (where $f$ is small, e.g., less than 100),
each query requires only a single memory lookup and a small constant number of
bitwise instructions. Furthermore, graph maintenance at forks and joins
requires only constant work, resulting in no asymptotic impact on overall work
and span. DePa is therefore work-efficient and fully parallel.

parallelism, sp-order maintenance, race detection

††copyright: none

##  1\. Introduction

With the mainstream availability of multicore computers, parallel programming
today is important, relevant, and challenging. One of the chief factors that
make it challenging is race conditions, which are difficult to avoid, debug,
and fix. To help address this challenge, researchers have developed a variety
of _dynamic race detection_ algorithms which instrument a program to identify
data races dynamically, i.e., while the program is running [42, 19, 36, 49,
30, 17, 15, 8, 18, 40, 41, 45, 48]. At a high level, these approaches broadly
fall into two camps: those targeting general, coarse-grained concurrency [42,
19, 36, 49], and those targeting fine-grained, structured parallelism [30, 17,
15, 8, 18, 40, 41, 45, 48]. In this paper, we focus on the latter,
specifically for nested fork-join parallelism (e.g. nested parallel-for
loops), provided by systems such as Cilk [21, 11, 33], ParlayLib [9], OpenMP
[38], Microsoft TPL [27], Intel TBB [24], Fork/Join Java [26], various forms
of Parallel ML [20, 37, 39, 32, 22, 46, 6], and many others. Programs written
in these languages and libraries typically consist of many (e.g., millions of)
fine-grained tasks which are spawned and synchronized in a structured fashion.

At the heart of existing race-detection algorithms is an _order maintenance_
data structure which encodes sequential dependencies between tasks [30, 17,
15, 8, 18, 40, 41, 45, 48, 47]. The purpose of this data structure is to
enable efficient queries, to quickly determine whether or not two tasks are
logically concurrent with one another.111Two tasks are _logically concurrent_
if there exists a schedule in which their operations could be interleaved.
Race detection then can be performed by monitoring individual reads and
writes: a data race is detected when two (logically) concurrent tasks both
access the same memory location, and at least one of these tasks modifies the
location.

In practice, the overheads of race detection are largely determined by the
performance characteristics (and implementation details) of this order
maintenance structure. As such, many solutions have been developed,
specifically with the goals of low overhead both in theory and practice, and
support for parallel execution. However, existing solutions come with a range
of drawbacks. Some do not support parallel execution, or only provide limited
support for it [17, 40, 8]. Others support parallel execution but incur either
high theoretical overhead per query [30] or present no bound on this cost
[41]. For nested fork-join programs, Utterback et al.’s algorithm [45] is
asymptotically optimal; however, it is complex and difficult to implement, as
it requires a custom scheduler which is tailored specifically to order
maintenance. We therefore seek a solution which has provably low overhead, is
fully parallel, and is simple to implement in practice.

Our solution is a “depths-and-paths” data structure, or _DePa_ for short,
which encodes the computation as a graph and performs precendence
(reachability) queries between vertices. The DePa structure maintains only the
dynamic task tree instead of the whole computation graph, and annotates each
tree node with two quantities: (1) its _depth_ in the graph, and (2) its
_path_ from the root of the task tree. We then prove that the depth and the
path are sufficient for answering precedence queries on the computation graph.
Essentially, the depth and path serve as two “coordinates” in a computation
graph: together, these not only uniquely identifying a vertex, but also enable
us to efficiently determine whether or not there is a path between two
vertices.

For most computations the depth and path can fit into a few machine words and
therefore the cost of precedence queries is a small constant. In particular,
we prove (Theorem 3.8) that our algorithm requires only
$O(\min(f_{u},f_{v})/\omega)$ work for a query between two graph vertices $u$
and $v$. Here, $f_{u}$ and $f_{v}$ are (respectively) the dynamic nesting
depths of $u$ and $v$, and $\omega$ is the word size of the machine. This is
effectively a constant bound in practice: with proper load-balancing and
granularity control, dynamic nesting depths are typically small (e.g., less
than 100). In terms of space, we show that the overhead of the algorithm is
small: storing the depth and path of a vertex $v$ requires only
$O(f_{v}/\omega)$ space, and any additional data required by the algorithm is
bounded by $O(PF+PF/\omega)$ where $P$ is the number of processors and $F$ is
the maximum dynamic nesting depth of the computation.

In addition to supporting queries efficiently, our DePa algorithm is fully
parallel. Maintaining the task tree requires only local computation with
constant cost at each fork and join to update depths and paths. The work and
span of a program therefore stays asymptotically unchanged by DePa
maintenance, and hence so does its parallelism (the ratio of work to span).
Queries are also parallel, as they can be implemented almost entirely with
simple bitwise operations and arithmetic, and do not require any
synchronization. Finally, to improve efficiency in practice, we present an
optimization technique which integrates DePa with a work-stealing scheduler to
improve data locality at queries. This optimization—although not essential—is
easy to implement and requires only small changes to the scheduler itself.

In summary, the contributions of this paper include the following.

  * •

The “depth-and-paths” (DePa) data structure for representing and querying task
graphs for series-parallel ordering, along with a correctness proof (Section
3).

  * •

Asymptotic analysis establishing work, span, and space bounds for DePa
(Section 3.4).

  * •

Optimization techniques for improving practical efficiency by integrating with
work-stealing scheduling (Section 4).

##  2\. Preliminaries

#### Fork-join

We consider _fork-join_ parallel programs which are based on _tasks_ organized
in a dynamic _task tree_. Initially, there is a single “root” task. At any
moment, any leaf (a task with no children) may _fork_ , which creates two
child tasks. While the children are executing, the parent task is suspended.
As soon as both children have completed, they _join_ with the parent, which
deletes the children from the tree and resumes execution of the parent task.
At any point of program execution, the tasks at leaf nodes of the task tree
are said to be _running_ while the tasks at internal nodes are said to be
_suspended_. Any task which is either suspended or running is said to be
_active_. We say that two tasks are _concurrent_ if neither is an ancestor of
the other. That is, in the task tree, concurrent tasks could be siblings,
cousins, etc.

#### Dags (Computation Graphs)

A fork-join computation can be summarized with a directed, acylic graph called
a _dag_ [4]. The dag represents the history of a completed computation: each
vertex represents a sequence of executed instructions uninterrupted by a fork
or join, and edges are ordering constraints. We can construct a dag
dynamically during execution by (1) creating new outgoing edges to two new
vertices at each fork, and (2) creating two incoming edges to a single new
vertex at each join. We say that vertex $u$ _precedes_ vertex $v$, denoted
$u\preccurlyeq v$, if there exists a path in the dag from $u$ to $v$. Note
that $\preccurlyeq$ is a partial order.

#### Series-Parallel Dags

The computation graphs of (nested) fork-join parallel programs are _series-
parallel_ graphs, i.e. inductively constructed by sequential and parallel
composition. This is illustrated in Figure 3.

##  3\. DePa Algorithm

We present an order maintenance data structure which efficiently supports
queries of the form $u\preccurlyeq_{G}v$, i.e., determining whether or not
there is a path from $u$ to $v$ in computation graph $G$. At a high level, our
algorithm assigns each vertex a unique _vertex identifier_ consisting of two
components: a _dag-depth_ and a _fork-path_. Together, the dag-depths and
fork-paths of vertices allow us to identify vertices and efficiently determine
their relative positions in the dag. We call our algorithm DePa for its
combined use of depths and paths.

###  3.1. Dag-Depths and Fork-Paths

The _dag-depth_ of a vertex is the length of the longest path that ends at
that vertex. The _fork-path_ of a vertex encodes the nesting of its
corresponding task as a sequence of bits. Each bit is one of L or R, to
respectively indicate a fork either on the left or the right. We denote dag-
depths with $\mathop{\text{D}}({v})$ and fork-paths with
$\mathop{\text{P}}({v})$. Furthermore, we denote the longest common prefix
between two fork-paths with $\mathop{\text{LCP}}({p_{1}},{p_{2}})$.

Dag-depths and fork-paths can be computed solely in terms of a vertex’s
immediate predecessors, as shown in Figure 3. When a vertex $u$ forks into $v$
and $w$, the new vertices have depth
$\mathop{\text{D}}({v})=\mathop{\text{D}}({w})=1+\mathop{\text{D}}({u})$, and
their paths are extended with L and R; that is,
$\mathop{\text{P}}({v})=\mathop{\text{P}}({u})\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{L}}$
and
$\mathop{\text{P}}({w})=\mathop{\text{P}}({u})\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{R}}$
(where $\mathbin{{+}\mspace{-8.0mu}{+}}$ denotes concatenation). When two
vertices $u$ and $v$ join, they must be siblings, i.e. their paths must be
$p\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{L}}$ and
$p\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{R}}$ for some common prefix $p$. The
new vertex then has path $p$ and depth
$1+\max(\mathop{\text{D}}({u}),\mathop{\text{D}}({v}))$. An example of a full
dag is shown in Figure 3, where we write “—” for the empty path.

Figure 1. Series-parallel computation graphs. Sequential composition (left)
overlaps the sink of $G_{1}$ with the source of $G_{2}$. Parallel composition
(right) has no overlap.

Figure 2. Computing fork-paths (left, red) and dag-depths (right, blue) at
each fork and join.

Figure 3. Example fork-paths and dag-depths.

Intuitively, it’s helpful to think of the dag-depth and fork-path as two
“coordinates” into a dag. When illustrating a dag with edges pointing down,
the dag-depth serves as a vertical position, and the fork-path is a horizontal
position. Together, these uniquely identify a vertex.222We leave this to
intuition, and prove a more general result in Lemma 3.1.

###  3.2. Identifying Precedence

When two vertices have the same fork-path, one must precede the other in the
dag. More generally, whenever one vertex’s fork-path is a prefix of another,
one of the two vertices must precede the other. This precendence can be
determined by comparing their dag-depths, as stated in Lemma 3.1.

###### Lemma 3.1.

Let $u$ and $v$ be any two vertices in dag $G$ such that
$\mathop{\text{P}}({u})$ is a prefix of $\mathop{\text{P}}({v})$. Then (1)
$u\preccurlyeq_{G}v$ if and only if
$\mathop{\text{D}}({u})\leq\mathop{\text{D}}({v})$, and (2)
$v\preccurlyeq_{G}u$ if and only if
$\mathop{\text{D}}({v})\leq\mathop{\text{D}}({u})$.

###### Proof.

We will only present a proof of (1), as (2) is symmetric. The forward
direction is straightforward: if $u\preccurlyeq_{G}v$, then there exists a
path in the dag from $u$ to $v$, so
$\mathop{\text{D}}({u})\leq\mathop{\text{D}}({v})$. To prove the reverse
direction, we induct over the structure of $G$. Consider $u$ and $v$ such that
$\mathop{\text{P}}({u})$ is a prefix of $\mathop{\text{P}}({v})$ and
$\mathop{\text{D}}({u})\leq\mathop{\text{D}}({v})$. There are three cases for
the structure of $G$:

  * •

If $G$ is a single vertex, the lemma holds trivially.

  * •

Suppose $G$ is the serial composition of $G_{1}$ and $G_{2}$. If $u$ and $v$
either both occur in $G_{1}$ or both occur in $G_{2}$, then
$u\preccurlyeq_{G}v$ by induction. Otherwise, due to
$\mathop{\text{D}}({u})\leq\mathop{\text{D}}({v})$, we must have that $u$
occurs in $G_{1}$ and $v$ occurs in $G_{2}$. Consider the vertex $r$ where the
two sub-dags overlap. This vertex $r$ is the sink of $G_{1}$, so
$u\preccurlyeq_{G_{1}}r$. Similarly, $r$ is the source of $G_{2}$, so
$r\preccurlyeq_{G_{2}}v$. Together, these imply $u\preccurlyeq_{G}v$.

  * •

Suppose $G$ is the parallel composition of $G_{1}$ and $G_{2}$. If $u$ is the
source vertex of $G$ or if $v$ is the sink vertex of $G$, then clearly we have
$u\preccurlyeq_{G}v$. If $u$ and $v$ either both occur in $G_{1}$ or both
occur in $G_{2}$, then $u\preccurlyeq_{G}v$ by induction. Otherwise, suppose
WLOG that $u$ occurs in $G_{1}$ and $v$ occurs in $G_{2}$. This violates the
assumption that $\mathop{\text{P}}({u})$ is a prefix of
$\mathop{\text{P}}({v})$, because all fork-paths of vertices in $G_{1}$ begin
with $p\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{R}}$ and all in $G_{2}$ begin
with $p\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{L}}$ (where $p$ is the fork-
path of the source of $G$).

∎

A direct application of this lemma reveals that our vertex identifiers do
indeed uniquely identify vertices.

######  Corollary 0.

For any two vertices $u$ and $v$, $u=v$ if and only if
$\mathop{\text{P}}({u})=\mathop{\text{P}}({v})$ and
$\mathop{\text{D}}({u})=\mathop{\text{D}}({v})$.

We can also obtain a method for checking precedence between any two arbitrary
vertices. To do so, we identify a special _critical_ vertex, denoted
$\textsf{C}(u,v)$, defined below. Note that the critical vertex is always
well-defined for any pair of vertices, because for every prefix of a vertex’s
fork-path there exists a vertex with less-or-equal dag-depth.

###### Definition 0 (Critical Vertex).

Consider any two vertices $u$ and $v$, and WLOG assume
$\mathop{\text{D}}({u})\leq\mathop{\text{D}}({v})$. The critical vertex
$\textsf{C}(u,v)$ is defined as the vertex $c$ such that
$\mathop{\text{P}}({c})=\mathop{\text{LCP}}({\mathop{\text{P}}({u})},{\mathop{\text{P}}({v})})$
and $\mathop{\text{D}}({c})$ is maximized s.t.
$\mathop{\text{D}}({c})\leq\mathop{\text{D}}({v})$.

As formalized below in Lemma 3.4, the critical vertex is special in that if a
path $u\preccurlyeq v$ exists, then $\textsf{C}(u,v)$ will certainly lie on
the path. Additionally, if there is not a path between the two vertices, then
the critical vertex serves as proof that the path does not exist.

###### Lemma 3.4.

Let $u$ and $v$ be any two vertices, and let $c=\textsf{C}(u,v)$ be their
critical vertex. Then $u\preccurlyeq v$ if and only if
$\mathop{\text{D}}({u})\leq\mathop{\text{D}}({c})\leq\mathop{\text{D}}({v})$.

###### Proof.

We separately consider the “if” and “only-if” directions. For the “if”
direction, suppose
$\mathop{\text{D}}({u})\leq\mathop{\text{D}}({c})\leq\mathop{\text{D}}({v})$.
Then by Lemma 3.1, we have both $u\preccurlyeq c$ and $c\preccurlyeq v$, and
therefore $u\preccurlyeq v$. Note that the Lemma is applicable because
$\mathop{\text{P}}({c})$ is a prefix of both $\mathop{\text{P}}({u})$ and
$\mathop{\text{P}}({v})$. For the “only-if” direction, suppose $u\preccurlyeq
v$, i.e. that there exists a path from $u$ to $v$ in the dag. Consider the
sequence of vertices in order along the path from $u$ to $v$. For each
adjacent pair of vertices, their fork-paths differ only by either pushing or
popping one element at the end. Therefore, at least one vertex along the path
has fork-path
$\mathop{\text{LCP}}({\mathop{\text{P}}({u})},{\mathop{\text{P}}({v})})$. The
last such vertex along the path is $c$, as it has maximum dag-depth. Because
$c$ is on the path, and because dag-depths strictly increase along each path,
we have
$\mathop{\text{D}}({u})\leq\mathop{\text{D}}({c})\leq\mathop{\text{D}}({v})$.
∎

#### Relationship with Task Trees

Observe that whenever a leaf task suspends (i.e. when it forks), at that
moment its current vertex has larger dag-depth than any task which has ever
had the same fork-path. The vertices of suspended ancestors are therefore
critical vertices for their children in the task tree, as these vertices cover
all possible prefixes of the fork-path and have maximum dag-depths for those
fork-paths. In particular, for queries of the form $u\preccurlyeq_{G}v$ where
$v$ is the current vertex of a leaf task (which are exactly the sort of
queries needed for entanglement detection), the critical vertex
$\textsf{C}(u,v)$ will be the current vertex of one of the task’s suspended
ancestors.

###  3.3. Algorithm

The DePa order maintenance algorithm is presented in Figure 4. It consists of
three components: forks, joins, and precedence queries. As described in Lemma
3.4, precedence queries rely on knowing the depths of critical vertices.
Accordingly, the algorithm maintains a global lookup data structure called
SuspendedDepths which maps fork-paths of suspended ancestors to their dag-
depths. (In theory, this could be implemented simply as a hash table; we
provide a detailed discussion of an optimized implementation in practice to
Section 4.)

At each fork, the algorithm initializes new vertex identifiers for the two new
tasks, and updates the SuspendedDepths data structure to remember the dag-
depth of the task that forked (which is now suspended). At each join, in
preparation of resuming the parent task, the algorithm constructs a new vertex
identifier for the parent and removes the old value from the SuspendedDepths
data structure. At each query, the algorithm computes the longest-common-
prefix of the vertices’ fork paths and looks up the appropriate dag-depth to
infer precedence.

⬇

1Fork vertex $u$:

2 let $v,w$
$\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}=$
fresh vertices

3 $\mathop{\text{P}}({v})$ $\leftarrow$
$\mathop{\text{P}}({u})\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{L}}$ //
concatenate

4 $\mathop{\text{P}}({w})$ $\leftarrow$
$\mathop{\text{P}}({u})\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{R}}$

5 $\mathop{\text{D}}({v})$ $\leftarrow$ $\mathop{\text{D}}({u})+1$

6 $\mathop{\text{D}}({w})$ $\leftarrow$ $\mathop{\text{D}}({u})+1$

7 SuspendedDepths[$\mathop{\text{P}}({u})$] $\leftarrow$
$\mathop{\text{D}}({u})$

8 // now can start executing child tasks

9 // with $v$ and $w$

⬇

10// note: $u$ and $v$ must be vertices of sibling leaf tasks

11Join vertices $u$ and $v$:

12 let $w$
$\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}=$
fresh vertex

13 let $p$
$\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}=$
remove L from end of $\mathop{\text{P}}({u})$

14 // note:
$\mathop{\text{P}}({u})=p\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{L}}$ and
$\mathop{\text{P}}({v})=p\mathbin{{+}\mspace{-8.0mu}{+}}\textsf{{R}}$

15 $\mathop{\text{P}}({w})\leftarrow p$

16
$\mathop{\text{D}}({w})\leftarrow\max(\mathop{\text{D}}({u}),\mathop{\text{D}}({v}))+1$

17 delete SuspendedDepths[$p$]

18 // now can resume parent with $w$

⬇

19// note: $v$ must be the vertex of a leaf task

20Checking $u\preccurlyeq v$:

21 let
$p=\mathop{\text{LCP}}({\mathop{\text{P}}({u})},{\mathop{\text{P}}({v})})$ //
longest common prefix

22 if $p=\mathop{\text{P}}({v})$:

23 return $\mathop{\text{D}}({u})\leq\mathop{\text{D}}({v})$

24 return $\mathop{\text{D}}({u})$ $\leq$ SuspendedDepths[$p$]

Figure 4. DePa order maintenance algorithm

###### Theorem 3.5 (DePa Correctness).

Let $v$ be the current vertex of some leaf task. Then for any other vertex
$u$, the order maintenance algorithm will correctly report that $u$ precedes
$v$ if and only if $u\preccurlyeq v$.

###### Proof.

Let
$p=\mathop{\text{LCP}}({\mathop{\text{P}}({u})},{\mathop{\text{P}}({v})})$.
There are two cases to consider: when $p=\mathop{\text{P}}({v})$ and when
$p\neq\mathop{\text{P}}({v})$. If $p=\mathop{\text{P}}({v})$, then
$\textsf{C}(u,v)=v$. In this case, the algorithm reports (Figure 4, line 23)
that there is a path according to
$\mathop{\text{D}}({u})\leq\mathop{\text{D}}({v})$. By Lemma 3.4, since
$\textsf{C}(u,v)=v$, this is correct. Next, suppose
$p\neq\mathop{\text{P}}({v})$. Then there is a suspended ancestor whose fork-
path is $p$; let $c$ be the vertex of this ancestor, and note that
SuspendedDepths[$p$] stores $\mathop{\text{D}}({c})$. We know that
$c=\textsf{C}(u,v)$ and also that
$\mathop{\text{D}}({c})\leq\mathop{\text{D}}({v})$ because $v$ occurs in a
descendant task. Therefore, by Lemma 3.4, the algorithm correctly reports
(Figure 4, line 24) that there is a path according to
$\mathop{\text{D}}({u})\leq\texttt{SuspendedDepths[p]}$. ∎

###  3.4. Cost Analysis

###### Lemma 3.6 (Vertex Identifier Space).

Each vertex identifier can be compactly represented using $O(f/\omega)$ words,
where $f$ is the dynamic nesting depth of the corresponding task, and $\omega$
is the word-size.

###### Proof.

The dag-depth component requires one word, and the fork-path is a bit sequence
of length $f$. Together, these require $1+\lceil f/\omega\rceil$ words. ∎

###### Theorem 3.7 (DePa Space).

At any point in a $P$-processor execution, the algorithm requires
$O(PF+PF/\omega)$ additional space, where $F$ is the maximum dynamic nesting
depth of the computation.

###### Proof.

There are two sources of space overhead: (1) each running task stores its
current vertex identifier, and (2) the SuspendedDepths data structure. We
assume here that the scheduler guarantees at most $O(P)$ running tasks at any
moment (typical schedulers such as work-stealing have this guarantee). Each of
these stores a vertex identifier, requiring $O(PF/\omega)$ space. In the
SuspendedDepths data structure, each running task has at most $F$ suspended
ancestors, therefore the size of SuspendedDepths at any moment is at most
$O(PF)$. ∎

###### Theorem 3.8 (DePa Query Cost).

A query between vertices $u$ and $v$ costs $O(\min(f_{u},f_{v})/\omega)$ work,
where $f_{u}$ and $f_{v}$ are the dynamic nesting depths of $u$ and $v$,
respectively.

###### Proof.

Using the representation of Lemma 3.6, computing the longest common prefix
between fork-paths requires $O(\min(f_{u},f_{v})/\omega)$ work. We can perform
the SuspendedDepths lookup within the same bound by representing it as a hash
table. The rest of the operations require constant work. ∎

###### Theorem 3.9 (DePa Fork and Join Cost).

DePa requires $O(1)$ work and span at each fork and join to update depths and
paths.

###### Proof.

By representing paths as a linked list of words, we can update paths at forks
and joins with $O(1)$ work. The SuspendedDepths data structure can be
implemented as a hash table with paths as keys. Each vertex can additionally
store its own hash, so that insertions and deletions (at forks and joins) are
$O(1)$. ∎

##  4\. Integration with Work-Stealing

For SP-order maintenance to be fast in practice, it is important not only to
optimize individual checks, but also to make sure that forks and joins are
fast. Much of the work of our order-maintenance algorithm at forks and joins
is “local” in the sense that it only requires accessing the data of a task and
its children, which should be fast in practice and parallelize well. There is
one operation, however, which could potentially incur a significant overhead:
updating the SuspendedDepths lookup data structure of the DePa algorithm
(Figure 4).

In the cost theorem (Theorem 3.9), we assume that the SuspendedDepths data-
structure provides $O(1)$ updates and deletions, with no contention. In
practice, a straightforward implementation such as a global shared hash table
may incur significant contention on concurrent accesses. In this section, we
describe how to improve efficiency by integrating the SuspendedDepths data
structure with a work-stealing scheduler. The basic idea is avoid contention
with a “copy-on-steal” approach, where each processor locally stores the
portion of the data-structure it needs.

#### Implementing SuspendedDepths

Throughout execution, each processor’s current task is a leaf in the task
tree. A key observation is that, for our order-maintenance algorithm, each
processor only needs access to the dag-depths of tasks along its root-to-leaf
path in the tree. Therefore, we can implement SuspendedDepths in a distributed
fashion, using one array stored locally on each processor, where each array
(of length up to $F$, the maximum nesting depth) stores a root-to-leaf path of
suspended depths.

Each processor-local array operates like a stack. Immediately before each
fork, the current processor pushes the current dag-depth onto its local array.
Immediately after each join, the current processor pops one element. To
guarantee that processors locally have the suspended depths of all ancestor
tasks, we copy a small amount of data on each steal: when a processor steals a
task that has $K$ ancestors, it copies $K$ suspended depths from the victim
into its own local array. This requires $O(F)$ work on each steal, which in
practice is effectively free, because $F$ is typically small, and the cost of
steals is often well-amortized with appropriate granularity control.

##  5\. Related Work

In 1974, Brent proved that a parallel program with total work $W$ and span
(depth) $S$ can be executed on $P$-processor, in $T_{P}\leq W/P+S$ time. This
seminal result has underpinned decades of research on scheduling algorithms
for task parallelism. This research have shown that this bound is not purely
theoretical and can in fact be realized efficiently in practice [14, 23, 21,
12, 35, 7, 1, 16, 2, 3], usually by using a variant of work stealing. Recent
work has also made some progress extending this scheduling theory to account
for latency [31] and competition among tasks, by allowing tasks to declare
priorities [34, 43].

The advances on scheduling algorithms it turn lead to the development of many
task-parallel programming languages and systems in both functional and
procedural languages.

An important concern is all these task-parallel systems is race detection.
Because data races usually cause incorrect behavior, especially at scale [5,
13], there has been much work on detecting races in task parallel, such as
fork-join programs, have been proposed [30, 17, 15, 8, 18, 40, 41, 45, 48].
These algorithms all revolve around an ordering data structure, that allows
determining whether two instructions are sequentially dependent or can be
executed in parallel. The basic idea is to check at each memory access whether
the instruction performing the access creates a race with the instructions
that accessed the same location in the past by using the ordering data
structure. The theoretical and practical efficiency of these algorithms
therefore critically depend on the series-parallel order data structure. Of
the prior approaches, some do not guarantee constant work/time bounds [30, 40,
41, 29]. Others run only sequentially [17, 15] or limit parallelism with non-
constant overheads [8]. More recent work can guarantee constant overheads by
carefully integrating the ordering data structure and the scheduler but this
comes with significant complexity in managing concurrency [45]. All of the
above work considers nested parallelism with fork-join and async-finish
constructs, which result in similar dependency structures. More recent work
considers race detection for futures and establishes worst-case bounds, though
the overheads are no longer constant [48].

In comparison to this related work, our DePa algorithm is perhaps most similar
to Mellor-Crummey’s _offset-span_ vertex labeling technique [30]. An offset-
span labeling for a vertex $v$ requires $O(f_{v})$ space, where $f_{v}$ is the
dynamic nesting depth of that vertex; similarly, the worst-case time required
for a query is $O(F)$ where $F$ is the maximum dynamic nesting depth. These
bounds may at first appear essentially identical to those achieved by DePa, if
one ignores the factor $\omega$ (the word-size) in our bounds. However, we
specifically included this factor in the bounds as it contributes to a
significant savings in practice. For any vertex $v$, the offset-span label of
$v$ requires approximately $2f_{v}$ words; in contrast, the DePa label for the
same vertex requires only $1+\lceil f_{v}/\omega\rceil$ words. For typical
word sizes (e.g. $\omega=64$), this is between one and two orders of magnitude
improvement in space. The cost of queries is likely also reduced, although a
direct comparison will be needed to determine the exact difference in
overhead.

Race detection has also been studied extensively in the more general
concurrency setting, where programs countain a small number of coarse-grained
threads that may synchronize by using locks, synchronization variables, etc.
Techniques from this second line of work do not scale to task-parallel
programs, because of their coarse-grained threads assumption (e.g,. [41]), and
is less directly relevant to this paper.

Early work on coarse-grained threads proposes the lock-set algorithm [42],
which can lead to false positives. Subsequent work proposed precise techniques
by using vector-clocks to capture the happens-before relations between threads
[19]. Followup work has proposed hybrid approaches that combine lock sets and
vector clocks, trading off efficiency and precision [36, 49]. Most approaches
use dynamic, on-the-fly race detection though there has also been some work on
predicting data races [44, 25].

Dynamic race-detection techniques in coarse-grained multithreaded programs are
typically sensitivity to scheduling decisions: because they track actual
threads, the techniques detect races in the run being checked and remain
sensitive to scheduling decisions. In contrast, prior race detection
techniques for task parallel programs are able to account for logical
(potentially unrealized) parallelism [30, 17, 15, 8, 40, 41, 29, 45].

#### Pedigrees and DPRNGs

Any scheme which uniquely identifies individual “vertices” of a computation
graph while ignoring details of scheduling is known as a _pedigree_ scheme
[28]. Pedigrees are potentially useful for a variety of applications. One such
application is a deterministic parallel random-number generator (or _DPRNG_ ,
for short), where pedigrees can be used as seeds for the generator. For
example, Leiserson et al. [28] describe a particular pedigree scheme and use
these pedigrees to implement a DPRNG with low overhead in practice. DPRNGs
make it possible to write parallel randomized algorithms with repeatable
behavior: because pedigrees are independent of scheduler decisions, this
approach is deterministic under parallel execution. This kind of repeatable
behavior is a form of _internal determinism_ , which provides a number of
benefits, such as simplifying the process of debugging and performance tuning
[10].

Because DePa provides a unique labeling of vertices within a computation
graph, it could be used as an efficient pedigree scheme for a DPRNG. In
comparison to the pedigree scheme of Leiserson et al. ([28]), one potential
advantage of DePa is in reducing the size of pedigrees; specifically, DePa
labels are approximately a factor $\omega$ smaller, where $\omega$ is the
word-size of the machine.

##  6\. Conclusion

We present _DePa_ , a novel solution to the so-called _SP maintenance_ problem
which is key to the efficiency of techniques such as dynamic race detection.
The gist of our approach is to represent a computation as a graph, where each
vertex is labeled with both is _depth_ in the graph as well as the _fork path_
of its corresponding nested task. This encoding is compact and enables fast
precendence queries between vertices. DePa therefore provides a number of
advantages in comparison to prior techniques: (1) it is provably efficient
with low overhead in terms of both space and time, (2) it is fully parallel,
and (3) it is simple to implement.

## References

  * [1] Umut A. Acar, Guy E. Blelloch, and Robert D. Blumofe.  The data locality of work stealing.  Theory of Computing Systems, 35(3):321–347, 2002.
  * [2] Umut A. Acar, Arthur Charguéraud, and Mike Rainey.  Scheduling parallel programs by work stealing with private deques.  In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’13, 2013.
  * [3] Umut A. Acar, Arthur Charguéraud, and Mike Rainey.  Oracle-guided scheduling for controlling granularity in implicitly parallel languages.  Journal of Functional Programming (JFP), 26:e23, 2016.
  * [4] Umut A. Acar, Arthur Charguéraud, Mike Rainey, and Filip Sieczkowski.  Dag-calculus: A calculus for parallel computation.  In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, ICFP 2016, pages 18–32, 2016.
  * [5] Sarita V. Adve.  Data races are evil with no exceptions: technical perspective.  Commun. ACM, 53(11):84, 2010.
  * [6] Jatin Arora, Sam Westrick, and Umut A. Acar.  Provably space efficient parallel functional programming.  In Proceedings of the 48th Annual ACM Symposium on Principles of Programming Languages (POPL)”, 2021.
  * [7] Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton.  Thread scheduling for multiprogrammed multiprocessors.  Theory of Computing Systems, 34(2):115–144, 2001.
  * [8] Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles E. Leiserson.  On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs.  In 16th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 133–144, 2004.
  * [9] Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala.  Parlaylib - A toolkit for parallel algorithms on shared-memory multicore machines.  In Christian Scheideler and Michael Spear, editors, SPAA ’20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 507–509. ACM, 2020.
  * [10] Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Julian Shun.  Internally deterministic parallel algorithms can be fast.  In PPoPP ’12, pages 181–192, 2012.
  * [11] Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou.  Cilk: An efficient multithreaded runtime system.  Journal of Parallel and Distributed Computing, 37(1):55 – 69, 1996\.
  * [12] Robert D. Blumofe and Charles E. Leiserson.  Scheduling multithreaded computations by work stealing.  J. ACM, 46:720–748, September 1999.
  * [13] Hans-Juergen Boehm.  How to miscompile programs with ”benign” data races.  In 3rd USENIX Workshop on Hot Topics in Parallelism, HotPar’11, Berkeley, CA, USA, May 26-27, 2011, 2011.
  * [14] F. Warren Burton and M. Ronan Sleep.  Executing functional programs on a virtual tree of processors.  In Functional Programming Languages and Computer Architecture (FPCA ’81), pages 187–194. ACM Press, October 1981.
  * [15] Guang-Ien Cheng, Mingdong Feng, Charles E. Leiserson, Keith H. Randall, and Andrew F. Stark.  Detecting data races in Cilk programs that use locks.  In Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architectures, SPAA ’98, 1998.
  * [16] Dror G. Feitelson, Larry Rudolph, and Uwe Schwiegelshohn.  Parallel job scheduling - A status report.  In Job Scheduling Strategies for Parallel Processing, 10th International Workshop, JSSPP 2004, New York, NY, USA, June 13, 2004, Revised Selected Papers, pages 1–16, 2004.
  * [17] Mingdong Feng and Charles E. Leiserson.  Efficient detection of determinacy races in Cilk programs.  In Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1–11, June 1997.
  * [18] Jeremy T. Fineman.  Provably good race detection that runs in parallel.  Master’s thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, Cambridge, MA, August 2005.
  * [19] Cormac Flanagan and Stephen N. Freund.  Fasttrack: efficient and precise dynamic race detection.  SIGPLAN Not., 44(6):121–133, June 2009.
  * [20] Matthew Fluet, Mike Rainey, John Reppy, and Adam Shaw.  Implicitly threaded parallelism in Manticore.  Journal of Functional Programming, 20(5-6):1–40, 2011.
  * [21] Matteo Frigo, Charles E. Leiserson, and Keith H. Randall.  The implementation of the Cilk-5 multithreaded language.  In PLDI, pages 212–223, 1998.
  * [22] Adrien Guatto, Sam Westrick, Ram Raghunathan, Umut A. Acar, and Matthew Fluet.  Hierarchical memory management for mutable state.  In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2018, Vienna, Austria, February 24-28, 2018, pages 81–93, 2018.
  * [23] Robert H. Halstead.  Multilisp: a language for concurrent symbolic computation.  ACM Transactions on Programming Languages and Systems, 7:501–538, 1985.
  * [24] Intel.  Intel threading building blocks, 2011.  https://www.threadingbuildingblocks.org/.
  * [25] Dileep Kini, Umang Mathur, and Mahesh Viswanathan.  Dynamic race prediction in linear time.  In Albert Cohen and Martin T. Vechev, editors, Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, Barcelona, Spain, June 18-23, 2017, pages 157–170. ACM, 2017.
  * [26] Doug Lea.  A Java fork/join framework.  In Proceedings of the ACM 2000 conference on Java Grande, JAVA ’00, pages 36–43, 2000.
  * [27] Daan Leijen, Wolfram Schulte, and Sebastian Burckhardt.  The design of a task parallel library.  In Proceedings of the 24th ACM SIGPLAN conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’09, pages 227–242, 2009.
  * [28] Charles E. Leiserson, Tao B. Schardl, and Jim Sukha.  Deterministic parallel random-number generation for dynamic-multithreading platforms.  In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’12, 2012.
  * [29] Li Lu, Weixing Ji, and Michael L. Scott.  Dynamic enforcement of determinism in a parallel scripting language.  In Michael F. P. O’Boyle and Keshav Pingali, editors, ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, Edinburgh, United Kingdom - June 09 - 11, 2014, pages 519–529. ACM, 2014.
  * [30] John Mellor-Crummey.  On-the-fly detection of data races for programs with nested fork-join parallelism.  In Proceedings of Supercomputing’91, pages 24–33, 1991.
  * [31] Stefan K. Muller and Umut A. Acar.  Latency-hiding work stealing: Scheduling interacting parallel computations with work stealing.  In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA, USA, July 11-13, 2016, pages 71–82, 2016.
  * [32] Stefan K. Muller, Umut A. Acar, and Robert Harper.  Responsive parallel computation: Bridging competitive and cooperative threading.  In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, pages 677–692, New York, NY, USA, 2017. ACM.
  * [33] Stefan K. Muller, Kyle Singer, Noah Goldstein, Umut A. Acar, Kunal Agrawal, and I-Ting Angelina Lee.  Responsive parallelism with futures and state.  In Alastair F. Donaldson and Emina Torlak, editors, Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2020, London, UK, June 15-20, 2020, pages 577–591.
  * [34] Stefan K. Muller, Sam Westrick, and Umut A. Acar.  Fairness in responsive parallelism.  In Proceedings of the 24th ACM SIGPLAN International Conference on Functional Programming, ICFP 2019, 2019.
  * [35] Girija J. Narlikar and Guy E. Blelloch.  Space-efficient scheduling of nested parallelism.  ACM Transactions on Programming Languages and Systems, 21, 1999\.
  * [36] Robert O’Callahan and Jong-Deok Choi.  Hybrid dynamic data race detection.  In Rudolf Eigenmann and Martin C. Rinard, editors, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2003, June 11-13, 2003, San Diego, CA, USA, pages 167–178. ACM, 2003.
  * [37] Atsushi Ohori, Kenjiro Taura, and Katsuhiro Ueno.  Making sml# a general-purpose high-performance language, 2018.  Unpublished Manuscript.
  * [38] OpenMP Application Programming Interface, Version 5.0, November 2018.  Accessed in July 2018.
  * [39] Ram Raghunathan, Stefan K. Muller, Umut A. Acar, and Guy Blelloch.  Hierarchical memory management for parallel programs.  In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, ICFP 2016, pages 392–406, New York, NY, USA, 2016\. ACM.
  * [40] Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin Vechev, and Eran Yahav.  Efficient data race detection for async-finish parallelism.  In Howard Barringer, Ylies Falcone, Bernd Finkbeiner, Klaus Havelund, Insup Lee, Gordon Pace, Grigore Rosu, Oleg Sokolsky, and Nikolai Tillmann, editors, Runtime Verification, volume 6418 of Lecture Notes in Computer Science, pages 368–383. Springer Berlin / Heidelberg, 2010.
  * [41] Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin Vechev, and Eran Yahav.  Scalable and precise dynamic datarace detection for structured parallelism.  In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, pages 531–542, 2012.
  * [42] Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson.  Eraser: A dynamic race detector for multi-threaded programs.  In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles (SOSP), October 1997.
  * [43] Kyle Singer, Noah Goldstein, Stefan K. Muller, Kunal Agrawal, I-Ting Angelina Lee, and Umut A. Acar.  Priority scheduling for interactive applications.  In Christian Scheideler and Michael Spear, editors, SPAA ’20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 465–477.
  * [44] Yannis Smaragdakis, Jacob Evans, Caitlin Sadowski, Jaeheon Yi, and Cormac Flanagan.  Sound predictive race detection in polynomial time.  In John Field and Michael Hicks, editors, Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2012, Philadelphia, Pennsylvania, USA, January 22-28, 2012, pages 387–400. ACM, 2012.
  * [45] Robert Utterback, Kunal Agrawal, Jeremy T. Fineman, and I-Ting Angelina Lee.  Provably good and practically efficient parallel race detection for fork-join programs.  In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA, USA, July 11-13, 2016, pages 83–94, 2016.
  * [46] Sam Westrick, Rohan Yadav, Matthew Fluet, and Umut A. Acar.  Disentanglement in nested-parallel programs.  In Proceedings of the 47th Annual ACM Symposium on Principles of Programming Languages (POPL)”, 2020.
  * [47] Yifan Xu, Kunal Agrawal, and I-Ting Angelina Lee.  Efficient parallel determinacy race detection for structured futures.  In Kunal Agrawal and Yossi Azar, editors, SPAA ’21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pages 398–409. ACM, 2021.
  * [48] Yifan Xu, Kyle Singer, and I-Ting Angelina Lee.  Parallel determinacy race detection for futures.  In Rajiv Gupta and Xipeng Shen, editors, PPoPP ’20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, California, USA, February 22-26, 2020, pages 217–231. ACM, 2020.
  * [49] Yuan Yu, Tom Rodeheffer, and Wei Chen.  Racetrack: efficient detection of data race conditions via adaptive tracking.  In Andrew Herbert and Kenneth P. Birman, editors, Proceedings of the 20th ACM Symposium on Operating Systems Principles 2005, SOSP 2005, Brighton, UK, October 23-26, 2005, pages 221–234. ACM, 2005.


s_{4}}(\vec{y}_{4})\rangle_{1}=&-\pi\lambda({\delta^{I}}_{K}{\delta^{J}}_{L}+{\delta^{I}}_{L}{\delta^{J}}_{K})\delta(s_{1}+s_{2}-s_{3}-s_{4})\\\
&\times\left(\prod_{i=1}^{4}\mathcal{C}_{\Delta_{s_{i}}}\right)D_{\Delta_{s_{1}},\Delta_{s_{2}},\Delta_{s_{3}},\Delta_{s_{4}}}(\vec{y}_{i})\end{split}$
(5.62)

Again, for the case when all $\\{s_{1},s_{2},s_{3},s_{4}\\}>0$, above contact
interaction is only non-zero when
$\Delta_{s_{1}}+\Delta_{s_{2}}=\Delta_{s_{3}}+\Delta_{s_{4}}$ and the
decomposition in (5.57) can be used. Using that, and adding the result of the
disconnected pieces from (5.15), we can see that in the symmetric sector, we
have the following anomalous dimension matrix

$\Delta_{\alpha\beta}^{s,m}=\begin{cases}\frac{2}{(N+4)(s+2m+1)}&\text{if
$\alpha\neq\beta$ and neither $\alpha$ nor $\beta$ is $\frac{s}{2}-v$ }\\\
\frac{\sqrt{2}}{(N+4)(s+2m+1)}&\text{if $\alpha\neq\beta$ and either $\alpha$
or $\beta$ is $\frac{s}{2}-v$ }\\\
\frac{2}{(N+4)(s+2m+1)}+\frac{v(v-1)(N+1)s}{2(N+4)(\alpha+v)(s-\alpha-v)}&\text{if
$\alpha=\beta\neq\frac{s}{2}-v$}\\\
\frac{1}{(N+4)(s+2m+1)}+\frac{2v(v-1)(N+1)}{s(N+4)}&\text{if
$\alpha=\beta=\frac{s}{2}-v$}.\end{cases}$ (5.63)

####  $\mathbb{Z}_{2}$ monodromy defect

For completeness, we also specialize this four-point function calculation to
the case of $\mathbb{Z}_{2}$ twist defect where $v=1/2$. We consider N real
scalars and the monodromy is defined such that they pick up a minus sign as
they go around the defect. We have the full unbroken $O(N)$ invariance. We
only need to talk about one set of operators on the defect since the reality
condition on scalars implies $\bar{\Psi}_{s}=\Psi_{-s}$. These defect
operators have the two-point function given by

$\begin{split}&\langle\Psi^{I}_{s}(\vec{y}_{1})\Psi^{J}_{-s}(\vec{y}_{2})\rangle=\frac{\delta^{IJ}\mathcal{C}_{\Delta_{s}}}{(\vec{y}^{2}_{12})^{\Delta_{s}}},\hskip
28.45274pt\mathcal{C}_{\Delta_{s}}=\frac{\Gamma\left(\Delta_{s}\right)}{4\pi^{d/2}\Gamma\left(\Delta_{s}+2-\frac{d}{2}\right)},\\\
&\Delta_{s}=1+|s|-\frac{\epsilon}{2}+\frac{v(v-1)(N+2)}{2(N+8)|s|}\epsilon.\end{split}$
(5.64)

where $s$ is an half-integer now. We then consider the following four-point
function in the $12\rightarrow 34$ channel

$\begin{split}\langle\Psi^{I}_{s_{1}}(\vec{y}_{1})\Psi^{J}_{s_{2}}(\vec{y}_{2})\Psi^{K}_{s_{3}}(\vec{y}_{3})\Psi^{L}_{s_{4}}(\vec{y}_{4})\rangle&=\delta^{IJ}\delta^{KL}\mathcal{G}_{S}+\left(\frac{\delta^{IK}\delta^{JL}+\delta^{IL}\delta^{JK}}{2}-\frac{\delta^{IJ}\delta^{KL}}{N}\right)\mathcal{G}_{T}\\\
&+\frac{\delta^{IK}\delta^{JL}-\delta^{IL}\delta^{JK}}{2}\mathcal{G}_{A}\end{split}$
(5.65)

and we have now decomposed it into singlet, traceless symmetric and anti-
symmetric representations of $O(N)$. We restrict to the case with
$s_{1},s_{2}>0$ and $s_{3},s_{4}<0$ and consider operators of the form
$O^{s,m}_{\alpha}=\Psi_{\alpha+\frac{1}{2}}(\vec{\partial}^{2})^{m}\partial^{l}\Psi_{s-\alpha-\frac{1}{2}}$
for $\alpha=0,1\ldots\lfloor\frac{s-1}{2}\rfloor$. These operators are
normalized to have unit two-point function as before.

As in the previous case, we can calculate the correlator as

$\begin{split}\langle\Psi^{I}_{s_{1}}(\vec{y}_{1})\Psi^{J}_{s_{2}}(\vec{y}_{2})\Psi^{K}_{s_{3}}(\vec{y}_{3})\Psi^{L}_{s_{4}}(\vec{y}_{4})\rangle_{0}&=\mathcal{C}_{\Delta_{s_{1}}}\mathcal{C}_{\Delta_{s_{2}}}\bigg{[}\frac{\delta^{IK}\delta^{JL}\delta_{s_{1},-s_{3}}\delta_{s_{2},-s_{4}}}{(\vec{y}_{13}^{2})^{\Delta_{s_{1}}}(\vec{y}_{24}^{2})^{\Delta_{s_{2}}}}+\frac{\delta^{IL}\delta^{JK}\delta_{s_{1},s_{4}}\delta_{s_{2},s_{3}}}{(\vec{y}_{14}^{2})^{\Delta_{s_{1}}}(\vec{y}_{23}^{2})^{\Delta_{s_{2}}}}\bigg{]}\\\
&=\left(\delta^{IK}\delta^{JL}\delta_{s_{1},-s_{3}}\delta_{s_{2},-s_{4}}(-1)^{l}+\delta^{IL}\delta^{JK}\delta_{s_{1},-s_{4}}\delta_{s_{2},-s_{3}}\right)\\\
&\times\mathcal{C}_{\Delta_{s_{1}}}\mathcal{C}_{\Delta_{s_{2}}}\sum_{n,l}c_{0}^{(12)}(n,l)W_{\Delta=\Delta_{s_{1}}+\Delta_{s_{2}}+2n+l,l}(\vec{y}_{i})\end{split}$
(5.66)

and the first order correction

$\begin{split}\langle\Psi^{I}_{s_{1}}(\vec{y}_{1})\Psi^{J}_{s_{2}}(\vec{y}_{2})\Psi^{K}_{s_{3}}(\vec{y}_{3})\Psi^{L}_{s_{4}}(\vec{y}_{4})\rangle_{1}&=-4\pi\lambda(\delta^{IJ}\delta^{KL}+\delta^{IK}\delta^{JL}+\delta^{IL}\delta^{JK})\delta(s_{1}+s_{2}+s_{3}+s_{4})\\\
&\times\left(\prod_{i=1}^{4}\mathcal{C}_{\Delta_{s_{i}}}\right)D_{\Delta_{s_{1}},\Delta_{s_{2}},\Delta_{s_{3}},\Delta_{s_{4}}}(\vec{y}_{i}).\end{split}$
(5.67)

We can extract the anomalous dimension from the above results similar to the
previous cases, and in the $O(N)$ singlet sector, we find

$\Delta_{\alpha\beta}^{s,m}=\begin{cases}\frac{2(N+2)}{(N+8)(s+2m+1)}&\text{if
$\alpha\neq\beta$ and neither $\alpha$ nor $\beta$ is $\frac{s-1}{2}$ }\\\
\frac{\sqrt{2}(N+2)}{(N+8)(s+2m+1)}&\text{if $\alpha\neq\beta$ and either
$\alpha$ or $\beta$ is $\frac{s-1}{2}$ }\\\
\frac{2(N+2)}{(N+8)(s+2m+1)}-\frac{(N+2)s}{2(N+8)(2\alpha+1)(2s-2\alpha-1)}&\text{if
$\alpha=\beta\neq\frac{s-1}{2}$}\\\
\frac{(N+2)}{(N+8)(s+2m+1)}-\frac{(N+2)}{2s(N+8)}&\text{if
$\alpha=\beta=\frac{s-1}{2}$}.\end{cases}$ (5.68)

For $N=1$, they give the results for the twist defect in Ising model, which
were also discussed in [13]. The authors in [13] did not discuss the case in
the second line of the above equation.

##  6 Conclusion

In this paper, we studied monodromy defects in free and critical $O(N)$ model.
We used conformal symmetry to map the problem to $S^{1}\times H^{d-1}$, and
saw that the hyperbolic space is well suited to many of the calculations. In
particular, we computed the expectation value of a spherical monodromy defect
(in 3d CFT, a circular defect) from the free energy on the hyperbolic
cylinder, and also from an alternative approach based on mapping to $S^{d}$.
We then studied a defect RG flow related to choosing alternate boundary
conditions on $H^{d-1}$, and verified the conjectured “defect C-theorem” for
this RG flow. We studied the monodromy defect in the critical $O(N)$ model
both in an large $N$ expansion keeping $d$ arbitrary and in $d=4-\epsilon$
dimensions with $\epsilon$ expansion techniques keeping $N$ arbitrary. We
performed several consistency checks among these two approaches.

As a next step, it would be interesting to do a systematic study of the bulk
data (the bulk one-point functions for instance). In [8], a defect CFT
inversion formula was used to learn more details about the bulk data for twist
defect in the Ising model. It would be interesting to extend the techniques to
the more general monodromy defect we considered. It would also be interesting
to get more analytic control over the large $N$ results. We relied on numerics
to solve the saddle point equation (4.11), but there might be a way to do this
analytically. Understanding the large $N$ solution better may also be a useful
first step towards understanding the holographic description of the system
141414A holographic description of a similar defect was discussed in [56]..
Moreover, as we saw in section 4, an interacting unitary fixed point does not
exist in $d=3$ when we choose $\Delta^{-}$ boundary condition for $s=v$ mode.
However, there does not seem to be any issues in describing it close to $d=4$.
It would be useful to understand why this happens, and an analytic
understanding of the large $N$ solution may help us understand it better. It
would be also interesting to go beyond the leading order at large $N$, which
would entail including the $\sigma$ fluctuations around the saddle point and
finding the corresponding propagator. Such analysis in the BCFT case was done
in [39] (see also [32]), and similar techniques may apply in this case.

## Acknowledgments

We thank Xinan Zhou and Nathan Benjamin for discussions on related topics.
This research was supported in part by the US NSF under Grants No.
PHY-1914860.

##  Appendix A Spectrum of Laplacian on $S^{d}$ with twisted boundary
conditions

In this appendix, we determine the spectrum of Laplacian on $S^{d}$ with
twisted boundary conditions. In the coordinate system specified in (2.59), we
may write the eigenfunctions of Laplacian as
$e^{im_{\theta}\theta}f(\tau)\kappa_{S^{d-2}}$, where $\kappa_{S^{d-2}}$ is
the eigenfunction of Laplacian on $S^{d-2}$ with the usual periodic boundary
condition. The required monodromy in $\theta$ direction implies
$m_{\theta}\in\mathbb{Z}+v$. The eigenvalues and their degeneracies for the
Laplacian with periodic boundary condition on $S^{d-2}$ , are well known

$-m_{\phi}(m_{\phi}+d-3),\ \ \
d_{m_{\phi}}=\frac{(2m_{\phi}+d-3)\Gamma(m_{\phi}+d-3)}{m_{\phi}!\Gamma(d-2)},\
\ \ m_{\phi}=0,1,2,...$ (A.1)

Hence, the eigenfunction equation for $f(\tau)$ is

$f^{\prime\prime}(\tau)+((d-2)\cot{\tau}-\tan\tau)f^{\prime}(\tau)-\bigg{(}\frac{m_{\theta}^{2}}{\cos^{2}\tau}+\frac{m_{\phi}(m_{\phi}+d-3)}{\sin^{2}\tau}\bigg{)}f(\tau)=\lambda
f(\tau).$ (A.2)

The solution regular at $\tau=\pi/2$ looks like

$\begin{split}f(\tau)=(\cos\tau)^{|m_{\theta}|}(\sin\tau)^{3-d-m_{\phi}}\
{}_{2}F_{1}\bigg{(}\frac{5-d+2|m_{\theta}|-2m_{\phi}-\sqrt{(d-1)^{2}-4\lambda}}{4},&\\\
\frac{5-d+2|m_{\theta}|-2m_{\phi}+\sqrt{(d-1)^{2}-4\lambda}}{4},|m_{\theta}|+1,\cos^{2}(\tau)\bigg{)}&.\end{split}$
(A.3)

We also want the solution to be regular at $\tau=0$ in all dimensions. The
eigenvalue $\lambda$ can be parametrized as

$\lambda=-n(n+d-1),\ \ \ $ (A.4)

and regularity of the solution at $\tau=0$ demands

$n=|m_{\theta}|+m_{\phi}+2a,\ \ \ a\in\mathbb{N}$ (A.5)

where $\mathbb{N}$ represents the set of non-negative integers (includes $0$).
As mentioned previously, the definition of defect requires
$m_{\theta}\in\mathbb{Z}+v$ which implies that $n=k+v$ or $n=k+1-v$ with $k$
being a non-negative integer. Using the degeneracies of $m_{\phi}$ in (A.1),
it is easy to count the degeneracies of $n$

$\begin{split}n&\in\mathbb{N},\ \ \
d_{n}=\frac{(2n+d-1)\Gamma(n+d-1)}{n!\Gamma(d)}\\\ n&=k+v,\ \ \
k\in\mathbb{N},\ \ \ d_{n}=\frac{\Gamma(k+d)}{k!\Gamma(d)}\end{split}.$ (A.6)

When summing over the eigenvalues, we need to sum over both $n=k+v$ and
$n=k+1-v$. When $v=1/2$, they both coincide. This effectively means that for
$v=1/2$, the degeneracy of a given $n$ is twice of what we wrote above.

##  Appendix B  Bulk Integrals

###  B.1 For bulk two-point function

In order to calculate the one-point function of $\bar{\Phi}\Phi$ to leading
order in $\epsilon$ in subsection 5.2, we need to do the following integral

$J=\int\frac{drdydz}{r}\frac{(r^{\prime})^{2}(4r^{\prime}r)^{2-2v}(d_{+}+d_{-})^{2v}(e_{+}+e_{-})^{2v}}{d_{+}d_{-}e_{+}e_{-}\left((d_{+}+d_{-})^{2}(e_{+}+e_{-})^{2}-(4r^{\prime}r)^{2}\right)}+(v\rightarrow
1-v)$ (B.1)

where the integral runs over $0\leq
r<\infty,-\infty<y<\infty,-\infty<z<\infty$ and

$d_{\pm}=\sqrt{\left(y-\frac{y^{\prime}}{2}\right)^{2}+z^{2}+(r\pm
r^{\prime})^{2}},\hskip
28.45274pte_{\pm}=\sqrt{\left(y+\frac{y^{\prime}}{2}\right)^{2}+z^{2}+(r\pm
r^{\prime})^{2}}.$ (B.2)

This integral was analyzed in the limit $\mu\rightarrow 0$ in [13] for
$v=1/2$. The same method goes through for arbitrary values of $v$, with some
changes. We will do that here. First, let’s make the integral over
dimensionless variables by making a substitution
$y=r^{\prime}a,z=r^{\prime}b,r=r^{\prime}c$, and then extend the integration
over all of $\mathbb{R}^{3}$

$\begin{split}&J=2^{3-4v}\int_{\mathbb{R}^{3}}dadbdc\frac{(c^{2})^{\frac{1}{2}-v}(\tilde{d}_{+}+\tilde{d}_{-})^{2v}(\tilde{e}_{+}+\tilde{e}_{-})^{2v}}{\tilde{d}_{+}\tilde{d}_{-}\tilde{e}_{+}\tilde{e}_{-}\left((\tilde{d}_{+}+\tilde{d}_{-})^{2}(\tilde{e}_{+}+\tilde{e}_{-})^{2}-(4c)^{2}\right)}+(v\rightarrow
1-v)\\\ &\tilde{d}_{\pm}=\sqrt{\left(a-\frac{\mu}{2}\right)^{2}+b^{2}+(c\pm
1)^{2}},\hskip
28.45274pt\tilde{e}_{\pm}=\sqrt{\left(a+\frac{\mu}{2}\right)^{2}+b^{2}+(c\pm
1)^{2}}.\end{split}$ (B.3)

When $\mu\rightarrow 0$, this integral has logarithm divergences around
$(a,b,c)=(0,0,\pm 1)$. So we expect the integral to be of the form
$\alpha\log\mu+\beta$ up to terms that vanish as $\mu\rightarrow 0$. We are
interested in calculating $\alpha$ and $\beta$. To do that, we introduce an
auxiliary parameter $\mathcal{N}$ and divide the integration region into two
parts and write the integral as
$J=J_{1}(\mu,\mathcal{N})+J_{2}(\mu,\mathcal{N})$. $J_{1}(\mu,\mathcal{N})$ is
the integral over spheres of radius $\mu\mathcal{N}$ around the two points
$(a,b,c)=(0,0,\pm 1)$ and $J_{2}(\mu,\mathcal{N})$ is the integral over rest
of $\mathbb{R}^{3}$. The integrals $J_{1,2}(\mu,\mathcal{N})$ simplify in the
limit $\mathcal{N}\rightarrow\infty,\mu\mathcal{N}\rightarrow 0$ if we do not
care about the terms that vanish as $\mu\rightarrow 0$. Let’s first look at
$J_{1}(\mu,\mathcal{N})$ and focus on the sphere around $(0,0,1)$. Making a
substitution $a=\mu x,b=\mu y,c=1+\mu z$ gives

$\begin{split}&\tilde{d}_{+}=\tilde{e}_{+}=2+\mu z+O(\mu^{2})\\\
&\tilde{d}_{-}=\mu\sqrt{\left(x-\frac{1}{2}\right)^{2}+y^{2}+z^{2}}+O(\mu^{2}),\hskip
28.45274pt\tilde{e}_{-}=\mu\sqrt{\left(x+\frac{1}{2}\right)^{2}+y^{2}+z^{2}}+O(\mu^{2}).\end{split}$
(B.4)

Similar things can also be said about the sphere around $(0,0,-1)$. The
integral, up to terms that vanish as $\mu\rightarrow 0$ then becomes

$\begin{split}J_{1}(\mu,\mathcal{N})&=\frac{1}{2}\int_{x^{2}+y^{2}+z^{2}\leq\mathcal{N}^{2}}dxdydz\frac{1}{f_{+}f_{-}(f_{+}+f_{-})};\hskip
28.45274ptf_{\pm}=\sqrt{\left(x\pm\frac{1}{2}\right)^{2}+y^{2}+z^{2}}\\\
&=2\pi\int_{0}^{\mathcal{N}}dx\frac{x+\frac{1}{2}-|x-\frac{1}{2}|+\sqrt{\mathcal{N}^{2}+\frac{1}{4}-x}-\sqrt{\mathcal{N}^{2}+\frac{1}{4}+x}}{2x}\\\
&=\pi\log 2\mathcal{N}+O(1/\mathcal{N}).\end{split}$ (B.5)

Now, let’s shift our attention to $J_{2}(\mu,\mathcal{N})$ which runs over the
domain $D=\\{(a,b,c)\in\mathbb{R}^{3}|a^{2}+b^{2}+(c\pm
1)^{2}\geq(\mu\mathcal{N})^{2}\\}$. In the limit
$\mathcal{N}\rightarrow\infty$, we can take
$\tilde{d}_{\pm}=\tilde{e}_{\pm}=\sqrt{a^{2}+b^{2}+(c\pm 1)^{2}}$ and hence
$4c=\tilde{d}^{2}_{+}-\tilde{d}^{2}_{-}$. The integral then simplifies to

$\begin{split}J_{2}(\mu,\mathcal{N})&=2^{3-4v}\int_{D}dadbdc\frac{(c^{2})^{\frac{1}{2}-v}(\tilde{d}_{+}+\tilde{d}_{-})^{4v}}{(\tilde{d}_{+}\tilde{d}_{-})^{2}\left((\tilde{d}_{+}+\tilde{d}_{-})^{4}-(4c)^{2}\right)}+(v\rightarrow
1-v)\\\
&=\frac{1}{2}\int_{D}dadbdc\frac{1}{(\tilde{d}_{+}\tilde{d}_{-})^{3}}\left(\frac{\tilde{d}_{+}+\tilde{d}_{-}}{|\tilde{d}_{+}-\tilde{d}_{-}|}\right)^{2v-1}+(v\rightarrow
1-v).\end{split}$ (B.6)

We then scale the variables by two followed by an inversion to change the
variables as

$\begin{split}a^{\prime\prime}=\frac{2a}{a^{2}+b^{2}+(c-1)^{2}},\ \
b^{\prime\prime}=\frac{2b}{a^{2}+b^{2}+(c-1)^{2}},\ \
c^{\prime\prime}-\frac{1}{2}=\frac{2(c-1)}{a^{2}+b^{2}+(c-1)^{2}}\\\
\implies\tilde{d}_{+}=2\sqrt{\frac{a^{\prime\prime 2}+b^{\prime\prime
2}+\left(c^{\prime\prime}+\frac{1}{2}\right)^{2}}{a^{\prime\prime
2}+b^{\prime\prime 2}+\left(c^{\prime\prime}-\frac{1}{2}\right)^{2}}},\ \
\tilde{d}_{-}=\frac{2}{\sqrt{a^{\prime\prime 2}+b^{\prime\prime
2}+\left(c^{\prime\prime}-\frac{1}{2}\right)^{2}}}\end{split}$ (B.7)

and the integral simplifies to

$\begin{split}J_{2}(\mu,\mathcal{N})&=\frac{1}{16}\int_{D^{\prime\prime}}da^{\prime\prime}db^{\prime\prime}dc^{\prime\prime}\frac{1}{r_{+}^{3}}\left(\left(\frac{r_{+}+1}{|r_{+}-1|}\right)^{2v-1}+\left(\frac{r_{+}+1}{|r_{+}-1|}\right)^{1-2v}\right),\\\
r_{+}&=\sqrt{a^{\prime\prime 2}+b^{\prime\prime
2}+\left(c^{\prime\prime}+\frac{1}{2}\right)^{2}}.\end{split}$ (B.8)

When we scale by two, the integration domain gets mapped to everywhere outside
the spheres centered at $(0,0,1/2)$ and $(0,0,-1/2)$ with radius
$\mu\mathcal{N}/2$. Then, when we invert about $(0,0,1/2)$, to leading order
in $\mu\mathcal{N}$, it gets mapped to everywhere between the sphere of radius
$\mu\mathcal{N}/2$ centered at $(0,0,-1/2)$ and the sphere of radius
$2/\mu\mathcal{N}$ centered at $(0,0,1/2)$. So
$D^{\prime\prime}=\\{(a^{\prime\prime},b^{\prime\prime},c^{\prime\prime})\in\mathbb{R}^{3}|a^{\prime\prime
2}+b^{\prime\prime 2}+(c^{\prime\prime}\pm
1/2)^{2}\gtrless(\mu\mathcal{N}/2)^{\pm 2}\\}$. Again, to leading order in
$\mu\mathcal{N}$, we can shift the outer sphere of radius $2/\mu\mathcal{N}$
so that it is also centered at $(0,0,-1/2)$ so the integration domain becomes
everywhere between concentric spheres with radii inverse of each other and the
integral becomes

$\begin{split}J_{2}(\mu,\mathcal{N})&=\frac{\pi}{4}\int_{\frac{\mu\mathcal{N}}{2}}^{\frac{2}{\mu\mathcal{N}}}dr_{+}\frac{1}{r_{+}}\left(\left(\frac{r_{+}+1}{|r_{+}-1|}\right)^{2v-1}+\left(\frac{r_{+}+1}{|r_{+}-1|}\right)^{1-2v}\right)\\\
&=\frac{\pi}{2}\left(-2\log
2-\left(H^{1-v}+H^{v}\right)+\frac{1}{v(1-v)}-4\log\mu\mathcal{N}\right)\end{split}$
(B.9)

So $\mathcal{N}$ cancels and the full integral is

$J=\frac{\pi}{2}\left(-2\log\mu-\left(H^{1-v}+H^{v}\right)+\frac{1}{v(1-v)}\right).$
(B.10)

For the same calculation with $\Delta^{-}$ boundary condition, we need an
additional integral

$J^{-}=\int\frac{drdydz}{r}\frac{(r^{\prime})^{2}}{d_{+}d_{-}e_{+}e_{-}}\frac{((d_{+}+d_{-})(e_{+}+e_{-}))^{2v}}{(4r^{\prime}r)^{2v}}-(v\rightarrow-v).$
(B.11)

Doing the same subsitutions as before, we get

$J^{-}=2^{-1-4v}\int_{\mathbb{R}^{3}}dadbdc\frac{(c^{2})^{-\frac{1}{2}-v}(\tilde{d}_{+}+\tilde{d}_{-})^{2v}(\tilde{e}_{+}+\tilde{e}_{-})^{2v}}{\tilde{d}_{+}\tilde{d}_{-}\tilde{e}_{+}\tilde{e}_{-}}-(v\rightarrow-v).$
(B.12)

This integral in fact does not have diverge as $\mu\rightarrow 0$, so we can
just plug in $\mu=0$, since we are only interested in $\mu$ independent piece
for this calculation. For $\mu=0$, we have
$\tilde{d}_{\pm}=\tilde{e}_{\pm}=\sqrt{a^{2}+b^{2}+(c\pm 1)^{2}}$ and
$4c=\tilde{d}^{2}_{+}-\tilde{d}^{2}_{-}$ which gives a simpler integral

$J^{-}=2\int_{\mathbb{R}^{3}}dadbdc\frac{(\tilde{d}_{+}+\tilde{d}_{-})^{2v-1}}{(\tilde{d}_{+}\tilde{d}_{-})^{2}|\tilde{d}_{+}-\tilde{d}_{-}|^{2v+1}}-(v\rightarrow-v).$
(B.13)

We then do a change of variables as in (B.7) to get

$\begin{split}J^{-}&=\frac{1}{4}\int_{\mathbb{R}^{3}}da^{\prime\prime}db^{\prime\prime}dc^{\prime\prime}\frac{(r_{+}+1)^{2v-1}}{r_{+}^{2}|r_{+}-1|^{2v+1}}-(v\rightarrow-v),\hskip
28.45274ptr_{+}=\sqrt{a^{\prime\prime 2}+b^{\prime\prime
2}+\left(c^{\prime\prime}+\frac{1}{2}\right)^{2}}\\\
&=\pi\int_{0}^{\infty}dr_{+}\frac{(r_{+}+1)^{2v-1}}{|r_{+}-1|^{2v+1}}-(v\rightarrow-v)\\\
&=-\frac{\pi}{v}.\end{split}$ (B.14)

###  B.2 For coefficient of displacement

For extracting the coefficient of the displacement in subsection 5.3, we have
to perform the following integral

$\mathcal{I}=\int
drdydz\frac{(r^{\prime})^{6}r^{3}}{d_{+}^{2}d_{-}^{2}e_{+}^{2}e_{-}^{2}(d_{+}+d_{-})^{2}(e_{+}+e_{-})^{2}}$
(B.15)

in the limit $\kappa=r^{\prime}/y^{\prime}\rightarrow 0$. As before, we
rescale the coordinates as $y=ay^{\prime},z=by^{\prime},r=cy^{\prime}$ to
rewrite the integral as

$\begin{split}&\mathcal{I}=\kappa^{6}I,\hskip
28.45274ptI=\frac{1}{2}\int_{\mathbb{R}^{3}}dadbdc\frac{(c^{2})^{3/2}}{\tilde{d}_{+}^{2}\tilde{d}_{-}^{2}\tilde{e}_{+}^{2}\tilde{e}_{-}^{2}(\tilde{d}_{+}+\tilde{d}_{-})^{2}(\tilde{e}_{+}+\tilde{e}_{-})^{2}}\\\
&\tilde{d}_{\pm}=\sqrt{\left(a-\frac{1}{2}\right)^{2}+b^{2}+(c\pm\kappa)^{2}},\hskip
28.45274pt\tilde{e}_{\pm}=\sqrt{\left(a+\frac{1}{2}\right)^{2}+b^{2}+(c\pm\kappa)^{2}}.\end{split}$
(B.16)

As before, this integral has a logarithmic divergence as $\kappa\rightarrow 0$
at $(a,b,c)=(\pm 1/2,0,0)$ and we want to evaluate the integral $I$ up to
terms that vanish as $\kappa\rightarrow 0$. As before, we divide the
integration region into two parts
$I=I_{1}(\kappa,\mathcal{N})+I_{2}(\kappa,\mathcal{N})$ with
$I_{1}(\kappa,\mathcal{N})$ being the integral within two spheres of radius
$\kappa\mathcal{N}$ around $(\pm 1/2,0,0)$. We will look at the integral in
the limit $\mathcal{N}\rightarrow\infty,\mathcal{N}\kappa\rightarrow 0$
ignoring the terms that vanish in this limit. Focusing on the sphere around
$(1/2,0,0)$, we make a substitution $a=1/2+\kappa x,b=\kappa y,c=\kappa z$,
and note that $\tilde{e}_{\pm}=1+O(\kappa)$

$I_{1}(\kappa,\mathcal{N})=\frac{1}{4}\int_{{x^{2}+y^{2}+z^{2}\leq\mathcal{N}^{2}}}dxdydz\frac{(z^{2})^{3/2}}{f_{+}^{2}f_{-}^{2}(f_{+}+f_{-})^{2}},\hskip
28.45274ptf_{\pm}=\sqrt{x^{2}+y^{2}+(z\pm 1)^{2}}$ (B.17)

The integral over $x,y$ can be directly performed, and the rest can be
performed after we expand in large $\mathcal{N}$. Up to terms that vanish as
$\mathcal{N}\rightarrow 0$, we get

$\begin{split}I_{1}(\kappa,\mathcal{N})&=-\frac{\pi}{16}\int_{0}^{\mathcal{N}}dz\left(z\log\left(\frac{|z-1|(z+1)}{2z^{2}}\right)+z\log
2+\frac{z^{3}}{\mathcal{N}^{4}}\right)\\\
&=\frac{\pi}{16}\log\mathcal{N}-\frac{\pi}{64}.\end{split}$ (B.18)

Let’s now look at the other part of the integral

$I_{2}(\kappa,\mathcal{N})=\frac{1}{2}\int_{D}dadbdc\frac{(c^{2})^{3/2}}{\tilde{d}_{+}^{2}\tilde{d}_{-}^{2}\tilde{e}_{+}^{2}\tilde{e}_{-}^{2}(\tilde{d}_{+}+\tilde{d}_{-})^{2}(\tilde{e}_{+}+\tilde{e}_{-})^{2}}$
(B.19)

where the domain of the integral is $D=\\{(a,b,c)\in\mathbb{R}^{3}|(a\pm
1/2)^{2}+b^{2}+c^{2}\geq(\kappa\mathcal{N})^{2}\\}$. At large $\mathcal{N}$,
we can use $\tilde{d}_{+}=\tilde{d}_{-},\tilde{e}_{+}=\tilde{e}_{-}$, so the
integral becomes

$I_{2}(\kappa,\mathcal{N})=\frac{1}{32}\int_{D}dadbdc\frac{(c^{2})^{3/2}}{r_{+}^{6}r_{-}^{6}},\hskip
28.45274ptr_{\pm}=\sqrt{\left(a\pm\frac{1}{2}\right)^{2}+b^{2}+c^{2}}.$ (B.20)

Next, we do an inversion centered at $(1/2,0,0)$ which maps the integration
domain to $D^{\prime}$ which is the region between a sphere of radius
$\kappa\mathcal{N}$ centered at $(-1/2,0,0)$ and a sphere of radius
$1/\kappa\mathcal{N}$ centered at $(1/2,0,0)$ up to terms of order
$\kappa\mathcal{N}$. Under this inversion, the integral simplifies to

$I_{2}(\kappa,\mathcal{N})=\frac{1}{32}\int_{D^{\prime}}dadbdc\frac{(c^{2})^{3/2}}{r_{+}^{6}}.$
(B.21)

We can then shift the outer sphere so that it is also centered at $(-1/2,0,0)$
which only changes the result at subleading order in $\kappa\mathcal{N}$. Then
the integral can be evaluated to be

$I_{2}(\kappa,\mathcal{N})=-\frac{\pi}{16}\log\kappa\mathcal{N}\implies\mathcal{I}=-\frac{\pi\kappa^{6}}{16}\left(\log\kappa+\frac{1}{4}\right).$
(B.22)

###  B.3 For bulk OPE coefficient

In this appendix, we show how to calculate the bulk OPE coefficient
${C_{\bar{\Phi};{\Phi}};}^{\bar{\Phi}\Phi}$. It can be extracted from the bulk
four-point function of $\Phi$ in the absence of the defect in flat space. As
we saw in section 5.4, such a four-point function can be decomposed into
singlet and adjoint representations of $U(N)$

$\langle\bar{\Phi}_{I}(x_{1})\Phi^{J}(x_{2})\bar{\Phi}_{K}(x_{3})\Phi^{L}(x_{4})\rangle={\delta_{I}}^{J}{\delta_{K}}^{L}\mathcal{G}_{\textrm{sing}}+\left({\delta_{I}}^{L}{\delta_{J}}^{K}-\frac{{\delta_{I}}^{J}{\delta_{K}}^{L}}{N}\right)\mathcal{G}_{\textrm{adj}}.$
(B.23)

We expect the operator $\bar{\Phi}\Phi$ to be present in the singlet sector.
For simplicity, we place the four operators on a line with
$|x_{12}|=|x_{34}|=r$, and $|x_{13}|=|x_{24}|=r/\mu$ and look at it in the
limit $\mu<<1$ when we expect

$\mathcal{G}_{\textrm{sing}}=\frac{1}{r^{4\Delta_{\Phi}}}\left[C^{2}_{\Phi}+({C_{\bar{\Phi};{\Phi}};}^{\bar{\Phi}\Phi})^{2}C_{\bar{\Phi}\Phi}\mu^{\Delta_{\bar{\Phi}\Phi}}(1+O(\mu))\right].$
(B.24)

In the following, we fix the normalization of the operator such that
$C_{\bar{\Phi}\Phi}=NC^{2}_{\Phi}.$ In the free theory, we have
$\Delta_{\Phi}=d/2-1,\Delta_{\bar{\Phi}\Phi}=d-2$. The result for
$\Delta_{\Phi}$ does not get corrected to first order in interaction. In the
free theory, the correlator is just

$\langle\bar{\Phi}_{I}(x_{1})\Phi^{J}(x_{2})\bar{\Phi}_{K}(x_{3})\Phi^{L}(x_{4})\rangle_{0}=\frac{{\delta_{I}}^{J}{\delta_{K}}^{L}C^{2}_{\Phi}}{r^{4\Delta_{\Phi}}}+\frac{\mu^{4\Delta_{\Phi}}{\delta_{I}}^{L}{\delta_{J}}^{K}C^{2}_{\Phi}}{r^{4\Delta_{\Phi}}(1-\mu^{2})^{2\Delta_{\Phi}}}.$
(B.25)

In the interacting theory, it gets corrected to

$\begin{split}\langle\bar{\Phi}_{I}(x_{1})\Phi^{J}(x_{2})\bar{\Phi}_{K}(x_{3})\Phi^{L}(x_{4})\rangle_{1}&=-\frac{\lambda}{2}({\delta_{I}}^{J}{\delta_{K}}^{L}+{\delta_{I}}^{L}{\delta_{J}}^{K})\int
d^{4}x_{0}\frac{C^{4}_{\Phi}}{x_{01}^{2}x_{02}^{2}x_{03}^{2}x_{04}^{2}}\\\
&=-\frac{\lambda\pi^{2}}{2}({\delta_{I}}^{J}{\delta_{K}}^{L}+{\delta_{I}}^{L}{\delta_{J}}^{K})\frac{\mu^{4}}{r^{4}}C^{4}_{\Phi}\bar{D}_{1,1,1,1}(u,v)\end{split}$
(B.26)

where we used the fact that this conformal integral can be performed in terms
of well known $\bar{D}$ functions (see for instance [57]). Conformal cross-
ratios $u,v$ can be defined by

$u=\frac{x_{12}^{2}x_{34}^{2}}{x_{13}^{2}x_{24}^{2}}=\mu^{4},\hskip
14.22636ptv=\frac{x_{14}^{2}x_{23}^{2}}{x_{13}^{2}x_{24}^{2}}=(1-\mu^{2})^{2}.$
(B.27)

This $\bar{D}$ function can be expanded into a power series around $u=0,v=1$
as [53, 58]

$\bar{D}_{1,1,1,1}(u,v)=\sum_{m,n=0}^{\infty}\frac{((m+n)!)^{2}}{n!(2m+n+1)!}u^{m}(1-v)^{n}\left(2\psi(2+2m+n)-2\psi(1+m+n)-\log
u\right)$ (B.28)

The singlet sector correlator, to leading order in interaction, and to leading
order in $\mu$ is thus given by

$\begin{split}\mathcal{G}_{\textrm{sing}}&=\frac{C^{2}_{\Phi}}{r^{d-2}}\left(1+\frac{\mu^{d-2}}{N}\right)-\frac{\lambda\pi^{2}(N+1)}{2N}\frac{\mu^{4}}{r^{4}}C^{4}_{\Phi}\bar{D}_{1,1,1,1}(u,v)\\\
&=\frac{C^{2}_{\Phi}}{r^{2d-4}}\left(1+\frac{\mu^{2d-4}}{N}\right)-\frac{2\pi^{4}(N+1)\epsilon}{N(N+4)}\frac{\mu^{4}}{r^{4}}C^{4}_{\Phi}\left(-4\log\mu+2\right).\end{split}$
(B.29)

Using our convention that

$C_{\Phi}=\frac{\Gamma\left(\frac{d}{2}-1\right)}{2\pi^{d/2}}$ (B.30)

we get

$\begin{split}\Delta_{\bar{\Phi}\Phi}&=2-\frac{3}{N+4}\epsilon\\\
{C_{\bar{\Phi};{\Phi}};}^{\bar{\Phi}\Phi}&=\frac{1}{N}\left(1-\frac{N+1}{2(N+4)}\epsilon\right).\end{split}$
(B.31)

## References

  * [1] M. Billò, V. Gonçalves, E. Lauria, and M. Meineri, “Defects in conformal field theory,” JHEP 04 (2016) 091, 1601.02883.
  * [2] A. Gadde, “Conformal constraints on defects,” JHEP 01 (2020) 038, 1602.06354.
  * [3] E. Lauria, M. Meineri, and E. Trevisani, “Radial coordinates for defect CFTs,” JHEP 11 (2018) 148, 1712.07668.
  * [4] M. Lemos, P. Liendo, M. Meineri, and S. Sarkar, “Universality at large transverse spin in defect CFT,” JHEP 09 (2018) 091, 1712.08185.
  * [5] S. Guha and B. Nagaraj, “Correlators of Mixed Symmetry Operators in Defect CFTs,” JHEP 10 (2018) 198, 1805.12341.
  * [6] M. Isachenkov, P. Liendo, Y. Linke, and V. Schomerus, “Calogero-Sutherland Approach to Defect Blocks,” JHEP 10 (2018) 204, 1806.09703.
  * [7] E. Lauria, M. Meineri, and E. Trevisani, “Spinning operators and defects in conformal field theory,” JHEP 08 (2019) 066, 1807.02522.
  * [8] P. Liendo, Y. Linke, and V. Schomerus, “A Lorentzian inversion formula for defect CFT,” 1903.05222.
  * [9] C. P. Herzog and A. Shrestha, “Two Point Functions in Defect CFTs,” 2010.04995.
  * [10] E. Lauria, P. Liendo, B. C. Van Rees, and X. Zhao, “Line and surface defects for the free scalar field,” 2005.02413.
  * [11] T. Nishioka and Y. Sato, “Free energy and defect $C$-theorem in free scalar theory,” 2101.02399.
  * [12] M. Billò, M. Caselle, D. Gaiotto, F. Gliozzi, M. Meineri, and R. Pellegrini, “Line defects in the 3d Ising model,” JHEP 07 (2013) 055, 1304.4110.
  * [13] D. Gaiotto, D. Mazac, and M. F. Paulos, “Bootstrapping the 3d Ising twist defect,” JHEP 03 (2014) 100, 1310.5078.
  * [14] S. Yamaguchi, “The $\epsilon$-expansion of the codimension two twist defect from conformal field theory,” PTEP 2016 (2016), no. 9 091B01, 1607.05551.
  * [15] A. Söderberg, “Anomalous Dimensions in the WF O($N$) Model with a Monodromy Line Defect,” JHEP 03 (2018) 058, 1706.02414.
  * [16] A. Kapustin, “Wilson-’t Hooft operators in four-dimensional gauge theories and S-duality,” Phys. Rev. D 74 (2006) 025005, hep-th/0501015.
  * [17] L.-Y. Hung, R. C. Myers, and M. Smolkin, “Twist operators in higher dimensions,” JHEP 10 (2014) 178, 1407.6429.
  * [18] I. R. Klebanov, S. S. Pufu, S. Sachdev, and B. R. Safdi, “Renyi Entropies for Free Field Theories,” JHEP 04 (2012) 074, 1111.6290.
  * [19] H. Casini and M. Huerta, “Entanglement entropy for the n-sphere,” Phys. Lett. B 694 (2011) 167–171, 1007.1813.
  * [20] H. Casini, M. Huerta, and R. C. Myers, “Towards a derivation of holographic entanglement entropy,” JHEP 05 (2011) 036, 1102.0440.
  * [21] L.-Y. Hung, R. C. Myers, M. Smolkin, and A. Yale, “Holographic Calculations of Renyi Entropy,” JHEP 12 (2011) 047, 1110.1084.
  * [22] S. Balakrishnan, S. Dutta, and T. Faulkner, “Gravitational dual of the Rényi twist displacement operator,” Phys. Rev. D 96 (2017), no. 4 046019, 1607.06155.
  * [23] L. Bianchi, S. Chapman, X. Dong, D. A. Galante, M. Meineri, and R. C. Myers, “Shape dependence of holographic Rényi entropy in general dimensions,” JHEP 11 (2016) 180, 1607.07418.
  * [24] A. Belin, A. Maloney, and S. Matsuura, “Holographic Phases of Renyi Entropies,” JHEP 12 (2013) 050, 1306.2640.
  * [25] A. Belin, L.-Y. Hung, A. Maloney, S. Matsuura, R. C. Myers, and T. Sierens, “Holographic Charged Renyi Entropies,” JHEP 12 (2013) 059, 1310.4180.
  * [26] A. Belin, L.-Y. Hung, A. Maloney, and S. Matsuura, “Charged Renyi entropies and holographic superconductors,” JHEP 01 (2015) 059, 1407.5630.
  * [27] L. Bianchi, M. Meineri, R. C. Myers, and M. Smolkin, “Rényi entropy and conformal defects,” JHEP 07 (2016) 076, 1511.06713.
  * [28] M. F. Paulos, J. Penedones, J. Toledo, B. C. van Rees, and P. Vieira, “The S-matrix bootstrap. Part I: QFT in AdS,” JHEP 11 (2017) 133, 1607.06109.
  * [29] D. Carmi, L. Di Pietro, and S. Komatsu, “A Study of Quantum Field Theories in AdS at Finite Coupling,” JHEP 01 (2019) 200, 1810.04185.
  * [30] C. P. Herzog and I. Shamir, “On Marginal Operators in Boundary Conformal Field Theory,” JHEP 10 (2019) 088, 1906.11281.
  * [31] C. P. Herzog and N. Kobayashi, “The $O(N)$ model with $\phi^{6}$ potential in ${\mathbb{R}}^{2}\times{\mathbb{R}}^{+}$,” 2005.07863.
  * [32] S. Giombi and H. Khanchandani, “CFT in AdS and boundary RG flows,” JHEP 11 (2020) 118, 2007.04955.
  * [33] O. Aharony, M. Berkooz, A. Karasik, and T. Vaknin, “Supersymmetric field theories on AdS${}_{p}\times$ Sq,” JHEP 04 (2016) 066, 1512.04698.
  * [34] D. Rodriguez-Gomez and J. G. Russo, “Free energy and boundary anomalies on $\mathbb{S}^{a}\times\mathbb{H}^{b}$ spaces,” JHEP 10 (2017) 084, 1708.00305.
  * [35] A. Pittelli, “Supersymmetric localization of refined chiral multiplets on topologically twisted $H^{2}$ × $S^{1}$,” Phys. Lett. B 801 (2020) 135154, 1812.11151.
  * [36] I. R. Klebanov and E. Witten, “AdS / CFT correspondence and symmetry breaking,” Nucl. Phys. B 556 (1999) 89–114, hep-th/9905104.
  * [37] N. Kobayashi, T. Nishioka, Y. Sato, and K. Watanabe, “Towards a $C$-theorem in defect CFT,” JHEP 01 (2019) 039, 1810.06995.
  * [38] S. Giombi and I. R. Klebanov, “Interpolating between $a$ and $F$,” JHEP 03 (2015) 117, 1409.1937.
  * [39] D. M. McAvity and H. Osborn, “Conformal field theories near a boundary in general dimensions,” Nucl. Phys. B455 (1995) 522–576, cond-mat/9505127.
  * [40] M. Beccaria and A. Tseytlin, “On induced action for conformal higher spins in curved background,” Nucl. Phys. B 919 (2017) 359–383, 1702.00222.
  * [41] R. Camporesi and A. Higuchi, “Spectral functions and zeta functions in hyperbolic spaces,” Journal of Mathematical Physics 35 (1994), no. 8 4217–4246, https://doi.org/10.1063/1.530850.
  * [42] A. A. Bytsenko, G. Cognola, L. Vanzo, and S. Zerbini, “Quantum fields and extended objects in space-times with constant curvature spatial section,” Phys. Rept. 266 (1996) 1–126, hep-th/9505061.
  * [43] D. E. Diaz and H. Dorn, “Partition functions and double-trace deformations in AdS/CFT,” JHEP 05 (2007) 046, hep-th/0702163.
  * [44] A. Lewkowycz and J. Maldacena, “Exact results for the entanglement entropy and the energy radiated by a quark,” JHEP 05 (2014) 025, 1312.5682.
  * [45] E. Witten, “Multitrace operators, boundary conditions, and AdS / CFT correspondence,” hep-th/0112258.
  * [46] S. Giombi, “Higher Spin — CFT Duality,” in Theoretical Advanced Study Institute in Elementary Particle Physics: New Frontiers in Fields and Strings, pp. 137–214, 2017.  1607.02967.
  * [47] A. Petkou, “Conserved currents, consistency relations and operator product expansions in the conformally invariant O(N) vector model,” Annals Phys. 249 (1996) 180–221, hep-th/9410093.
  * [48] M. A. Metlitski, C. A. Fuertes, and S. Sachdev, “Entanglement Entropy in the O(N) model,” Phys. Rev. B 80 (2009), no. 11 115122, 0904.4477.
  * [49] K. G. Wilson, “Quantum Field - Theory Models in Less Than 4 Dimensions,” Phys. Rev. D 7 (May, 1973) 2911–2926.
  * [50] A. L. Fitzpatrick and J. Kaplan, “Unitarity and the Holographic S-Matrix,” JHEP 10 (2012) 032, 1112.4845.
  * [51] H. Liu and A. A. Tseytlin, “On four point functions in the CFT / AdS correspondence,” Phys. Rev. D 59 (1999) 086002, hep-th/9807097.
  * [52] E. D’Hoker, D. Z. Freedman, S. D. Mathur, A. Matusis, and L. Rastelli, “Graviton exchange and complete four point functions in the AdS / CFT correspondence,” Nucl. Phys. B 562 (1999) 353–394, hep-th/9903196.
  * [53] F. A. Dolan and H. Osborn, “Conformal four point functions and the operator product expansion,” Nucl. Phys. B599 (2001) 459–496, hep-th/0011040.
  * [54] E. Hijano, P. Kraus, E. Perlmutter, and R. Snively, “Witten Diagrams Revisited: The AdS Geometry of Conformal Blocks,” JHEP 01 (2016) 146, 1508.00501.
  * [55] C. B. Jepsen and S. Parikh, “Propagator identities, holographic conformal blocks, and higher-point AdS diagrams,” JHEP 10 (2019) 268, 1906.08405.
  * [56] G. T. Horowitz, N. Iqbal, J. E. Santos, and B. Way, “Hovering Black Holes from Charged Defects,” Class. Quant. Grav. 32 (2015) 105001, 1412.1830.
  * [57] S. Giombi, V. Kirilin, and E. Perlmutter, “Double-Trace Deformations of Conformal Correlations,” JHEP 02 (2018) 175, 1801.01477.
  * [58] F. A. Dolan and H. Osborn, “Implications of N=1 superconformal symmetry for chiral fields,” Nucl. Phys. B593 (2001) 599–633, hep-th/0006098.