#  Efficient Data Race Detection of Async-Finish Programs Using Vector Clocks

Shivam Kumar<EMAIL_ADDRESS>Indian Institute of Technology KanpurIndia
,  Anupam Agrawal<EMAIL_ADDRESS>Indian Institute of Technology
KanpurIndia and  Swarnendu Biswas<EMAIL_ADDRESS>Indian Institute
of Technology KanpurIndia

(2022)

###### Abstract.

Existing data race detectors for task-based programs incur significant run
time and space overheads. The overheads arise because of frequent lookups in
fine-grained tree data structures to check whether two accesses can happen in
parallel.

This work shows how to efficiently apply vector clocks for dynamic data race
detection of async-finish programs with locks. Our proposed technique,
_FastRacer_ , builds on the FastTrack algorithm with per-task and per-variable
optimizations to reduce the size of vector clocks. FastRacer exploits the
structured parallelism of async-finish programs to use a coarse-grained
encoding of the dynamic task inheritance relations to limit the metadata in
the presence of many concurrent readers. Our evaluation shows that FastRacer
substantially improves time and space overheads over FastTrack, and is
competitive with the state-of-the-art data race detectors for async-finish
programs with locks.

Concurrency bugs, data races, happens-before, dynamic program analysis, task
parallelism, async-finish

††journalyear: 2022††copyright: acmcopyright††conference: The 13th
International Workshop on Programming Models and Applications for Multicores
and Manycores; April 2–6, 2022; Seoul, Republic of Korea††booktitle: The 13th
International Workshop on Programming Models and Applications for Multicores
and Manycores (PMAM’22), April 2–6, 2022, Seoul, Republic of Korea††price:
15.00††doi: 10.1145/3528425.3529101††isbn: 978-1-4503-9339-3/22/04††ccs:
Software and its engineering Software testing and debugging††ccs: Software and
its engineering Runtime environments††ccs: Software and its engineering
Multiprocessing / multiprogramming / multitasking

##  1\. Introduction

The task-based programming abstraction helps write efficient and portable
parallel code without having to think of low-level threads. Tasks execute in
parallel as hardware-agnostic logical units of work, and programmers only
specify the dependencies among the tasks. An accompanying runtime schedules
tasks to threads and provides performance features like work-stealing to load-
balance the execution. Cilk (Blumofe et al., 1995; Frigo et al., 1998), X10
(Charles et al., 2005), Habanero-Java (Cavé et al., 2011), and Java Fork-Join
(Lea, 2000) are popular task-based frameworks.

Task-based programs are susceptible to concurrency errors such as atomicity
violations (Yoga and Nagarakatte, 2016) and data races (Raman et al., 2012;
Feng and Leiserson, 1997; Raman et al., 2010; Utterback et al., 2016; Bender
et al., 2004). A _data race_ occurs when two accesses, with at least one
write, from different tasks are incorrectly synchronized. The presence of data
races in shared-memory programs often indicates the presence of other
concurrency errors (Flanagan and Freund, 2004), and can affect an execution by
crashing, hanging, or corrupting data (Kasikci et al., 2012). Data races are
hard to detect and fix since they may occur nondeterministically under
specific thread interleavings, program inputs, and execution environments.
Data races have led to several real-world disasters (Leveson and Turner, 1993;
Poulsen, 2004; PCWorld, 2012); such high-profile failures are a testament that
data races are present even in well-tested code.

#### The problem

There exists prior work to detect data races in task-based programs (Yoga et
al., 2016; Raman et al., 2012; Cheng et al., 1998; Feng and Leiserson, 1997;
Raman et al., 2010; Mellor-Crummey, 1991; Yu and Sarkar, 2018; Bender et al.,
2004; Utterback et al., 2016). Most analysis utilize the series-parallel
structure of execution of task-based programs to check whether accesses can
potentially execute in parallel (called _series-parallel maintenance_) (Feng
and Leiserson, 1997; Raman et al., 2012; Yoga et al., 2016; Bender et al.,
2004; Utterback et al., 2016). Prior techniques are either serial (e.g., (Feng
and Leiserson, 1997; Raman et al., 2010; Cheng et al., 1998)) or are difficult
to parallelize (e.g., (Bender et al., 2004)), detect races only in a given
schedule (e.g., (Flanagan and Freund, 2009)), continue to incur high run-time
overheads (e.g., (Yoga et al., 2016; Raman et al., 2012; Mellor-Crummey,
1991)), require tight coupling with the runtime scheduler for good performance
(e.g., (Utterback et al., 2016)), or do not support lock-based synchronization
(e.g., (Utterback et al., 2016; Raman et al., 2012; Bender et al., 2004)).

#### Our approach

In this work, we focus on efficient detection of _per-input apparent data
races in task-based programs with async-finish semantics_.111Apparent data
races occur because of the usage of parallel task constructs and ignore the
per-schedule dynamic interleavings (Netzer and Miller, 1992). Feasible data
races consider the nondeterministic timing variations during execution. For a
given application and an input, per-input races include races observed in the
current schedule as well as other schedules with possibly permuted memory
operations, ignoring schedule-sensitive branches (Yoga et al., 2016). While
prior work has _ignored_ how to optimize vector clocks for efficient race
detection of task-based programs, we _argue_ that analyses based on vector
clocks are generic, inherently parallel, and have better data locality than
tree-based data structures for series-parallel (SP) maintenance. However, a
naïve application of vector-clock-based analysis to tasks results in
prohibitive memory and run-time overhead (Yoga et al., 2016; Raman et al.,
2012).

This paper presents _FastRacer_ , a vector-clock-based data race detector for
async-finish programs. FastRacer avoids the redundancy in _per-task_ vector
clocks by using auxiliary immutable data structures to maintain space- and
time-efficient lossless vector clock representations correctly. FastRacer
exploits the structured parallelism in async-finish programs to optimize the
space requirement of _per-variable_ metadata in the presence of many
concurrent readers. Prior work has shown that a careful selection of only two
“concurrent read” accesses is sufficient for detecting read-write data races
for async-finish programs (Raman et al., 2012; Yoga et al., 2016). FastRacer
uses coarse-grained encoding of dynamic task inheritance relationships to
identify the two accesses (for both reads and writes) necessary for race
detection, and uses vector clocks to check whether two accesses can race.

We evaluate the performance and correctness of FastRacer on C++applications
that use Intel TBB (Reinders, 2007) for task parallelism and compare with
prior work (Flanagan and Freund, 2009; Yoga et al., 2016; Utterback et al.,
2016). Our evaluation shows that the run time and memory overhead of FastRacer
is substantially lower compared to state-of-the-art data race detectors that
target async-finish programs.

#### Contributions

This paper makes the following contributions:

  * •

To the best of our knowledge, this work is the _first_ to show the viability
of using vector clocks for efficient dynamic analysis of task-based programs;

  * •

a race detector called FastRacer that detects per-input apparent races in
async-finish programs with locks,

  * •

publicly available implementations of FastRacer and related techniques, and an
evaluation that shows FastRacer significantly outperforms prior work.

##  2\. Background and Motivation

This section briefly reviews data race detection of multithreaded programs
using vector clocks. We also discuss closely related prior work on race
detection of async-finish programs.

###  2.1. Race Detection with Vector Clocks

Many race detectors for multithreaded programs use vector clocks to track
happens-before (HB) relations in an execution (Pozniansky and Schuster, 2007;
Bond et al., 2010; Flanagan and Freund, 2009; Serebryany et al., 2012). Each
thread maintains a scalar clock that is incremented at _synchronization
release_ operations (e.g., lock release, monitor wait, thread fork and join,
and volatile write). Each thread T also maintains a vector clock C of size
$n$, where there are $n$ threads in the application. The clock entry CT(U)
records the clock of thread U when thread T last synchronized with U. A
dynamic analysis updates per-variable vector clock metadata whenever a thread
accesses a shared data or a lock variable. Vector clock operations require
$\mathcal{O}\left(n\right)$ time and storage to monitor an execution with $n$
threads.

Algorithm 1 FastTrack analysis at synchronization operations

1:procedure Spawn $\triangleright$ Thread T spawns U

2: U.vc $\leftarrow$ T.vc $\cup$ {T.epoch}

3: T.epoch $\leftarrow$ T.epoch \+ 1 $\triangleright$ Increment T’s scalar
clock

4: U.epoch $\leftarrow$ U.epoch \+ 1

5:procedure Join $\triangleright$ Thread T joins with U

6: for all <t,c> in U.vc do

7: T.vc[t] $\leftarrow$ max(U.vc[t], T.vc[t])

8:procedure Acquire $\triangleright$ T acquires lock L

9: for all <t,c> in L.vc do

10: T.vc[t] $\leftarrow$ max(L.vc[t], T.vc[t])

11:procedure Release $\triangleright$ T releases lock L

12: L.vc $\leftarrow$ T.vc

13: T.epoch $\leftarrow$ T.epoch \+ 1

14:function CheckHB(c@u,T) $\triangleright$ Check HB between epoch

15: return c@u $\preceq$ T.vc

#### FastTrack

The _FastTrack_ algorithm tracks a single last writer and, in many cases, a
single last reader (Flanagan and Freund, 2009). The total order on writes in a
data-race-free program allows FastTrack to store only the _last_ write
information. FastTrack stores the write metadata as an epoch c@T, which is a
tuple consisting of the writer thread identifier T and the value of T’s clock
(say c) at the time of the write. The read metadata alternates between epoch
and vector clock forms. An epoch representation suffices when there is a
single reader or the current read happens after all previous reads. When there
are concurrent readers, the read metadata is a vector clock (denoted by vc).
Algorithm 1 shows the pseudocode for the dynamic analysis performed by
FastTrack at synchronization operations. Before each access to a shared
variable x by a thread T, FastTrack checks whether the current access by T
happens after the previous write and all previous reads to x (CheckHB,
Algorithm 1). A data race is reported if the current access by T is concurrent
with the last accesses. The shared data and lock variable metadata are updated
upon a thread access. FastTrack is popularly used as the basis for dynamically
sound and precise222 _Sound_ means no false negatives, and _precise_ means no
false positives. data race detection of multithreaded programs (Eizenberg et
al., 2017; Bond et al., 2010; Atzeni et al., 2016; Serebryany et al., 2012;
Wood et al., 2017; Peng et al., 2018).

###  2.2. Race Detection for Async-Finish Programs

Frameworks like X10 (Charles et al., 2005) and Habanero Java (Cavé et al.,
2011) support structured task parallelism with async-finish semantics. The
statement “async {t}” creates a new child task t that can run in series or in
parallel with its parent task. The statement “finish {t}” causes the current
task to wait for all the recursively-created tasks within the block t. The
async-finish model is terminally-strict, which means each join edge goes from
the last instruction of a task to _any_ of its ancestors in the inheritance
tree (Raman et al., 2010). In the following, we discuss dynamic data race
detection techniques for async-finish programs.

(a) An async-finish program with tasks T1–T5, shared variables var1 and var2,
and a lock variable L1.

(b) The DPST for the program in Figure 1(a).

Figure 1. An async-finish program and its DPST.

#### SPD3

SPD3 (Raman et al., 2012) uses a _dynamic program structure tree_ (DPST) to
capture the semantics of an async-finish program. A DPST consists of step,
finish, and async nodes. A step node represents the maximal sequence of
instructions without any task management. An async node represents the
spawning of a child task by a parent task. The descendants of an async node
execute asynchronously with the remainder of the parent task. A finish node is
created when a parent task spawns a child task and waits for the child, and
its descendants, to complete. A finish node is thus the parent of all async,
finish, and step nodes executed by its children or their descendants. Figure 1
shows an async-finish program and the corresponding DPST. All executions of a
data-race-free async-finish program with the same input result in the same
DPST (Raman et al., 2012).

The operational semantics of async-finish programs imply a left-to-right
computation order of sibling nodes belonging to a common parent task. Thus, a
DPST node’s children are also ordered left-to-right to reflect the computation
order in their parent. On a variable access, SPD3 searches for the _lowest
common ancestor_ (LCA) of the current access (i.e., a step node) and the last
access stored in the variable’s metadata. SPD3 reports a race if the left
child of the LCA, which is an ancestor of the step node representing the last
access, is an async node that indicates _concurrent_ execution of the last
access and the current task. The DPST allows SPD3 to maintain one metadata
location for writes and two locations for reads in shadow memory.

#### PTRacer

PTRacer extends SPD3 by detecting apparent races in async-finish programs with
locks (Yoga et al., 2016). PTRacer maintains two metadata locations each for
reads and writes to a shared variable. The metadata per variable is
proportional to the number of different locksets (i.e., set of locks held by
the tasks at any time) with which the variable is accessed, which is
reasonable in practice because variables are usually accessed with similar
locking patterns.

PTRacer selects two “last read” (“last write”) accesses from multiple parallel
accesses with the same lockset to maintain constant metadata, such that any
future write which can race with any one of the parallel reads (writes) will
race with either one of the two chosen “last readers” (“last writers”).
PTRacer makes these choices by selecting step nodes with the highest LCA among
all parallel step nodes. PTRacer detects _all_ races for a given input even in
the presence of lock-based synchronization. Consider the shared variable var1
which is updated by the parallel tasks T2, T4, and T5 in Figure 1(a). The step
nodes corresponding to these accesses are S21, S41, and S51, respectively.
Since, S21 and S51 have the highest LCA in the corresponding DPST, PTRacer
will store these two accesses and discard the access information for S41.

The race analysis in PTRacer is similar to SPD3. PTRacer will report a race on
var2 for the example in Figure 1 because the left child of the LCA of step
nodes S21 and S31 is an async node. SPD3 will report false races on the
variable var1.

PTRacer uses the DPST to maintain a constant amount of per-variable metadata
independent of the number of tasks executing the program. Furthermore, PTRacer
performs frequent lookups in the DPST to check whether two accesses can happen
in parallel. However, the DPST can be deep for programs with a recursive
pattern of task creation and large because of many step nodes. These lead to
high run time and memory overheads. PTRacer uses an array-based representation
of the DPST and caches LCA lookups to improve the performance of LCA. However,
the DPST and the LCA computation continue to be a significant bottleneck for
several benchmarks, as we show in Section 5.2. Thus, there is a need for _more
efficient_ techniques to help detect data races in async-finish programs.

##  3\. FastRacer: Efficient Dynamic Data Race Detection for Async-Finish
Programs

The thesis of this work is that vector clocks can provide better data locality
for series-parallel (SP) maintenance in task-based programs compared to tree-
based data structures used in prior work (e.g., (Utterback et al., 2016; Raman
et al., 2012; Yoga et al., 2016)). We present _FastRacer_ , a novel algorithm
that integrates the benefits of vector-clock-based analysis _and_ exploits
structured parallelism of async-finish programs to limit the amount of per-
variable metadata.

Task-based programs create more, often orders of magnitude, parallel tasks
than threads in multithreaded programs. For example, the benchmark
nearestNeigh creates up to $\sim~{}3\times 10^{6}$ tasks (Table 2). Race
detectors like FastTrack use per-thread and per-variable vector clocks to
capture the clock values of all the threads in the system. While this
representation works fine for multithreaded programs where the number of
concurrent threads is comparatively small ($\sim$#cores), it is impractical
for task-based programs and leads our FastTrack implementation to run out of
memory on several benchmarks (Section 5.2). Storing only non-zero entries in a
vector clock does not help since several concurrent tasks potentially access
shared read-only variables. Furthermore, maintaining vector clocks
proportional to the number of threads can detect only feasible data races and
misses races among concurrent tasks (Gu and Mellor-Crummey, 2018). In the
following, we discuss novel ideas to solve these challenges.

Algorithm 2 FastRacer analysis at synchronization operations

1:procedure Spawn $\triangleright$ Task T spawns task U

2: if size(T.rw_vc) $>$ THRESHOLD then

3: T.ro_vc $\leftarrow$ REF({T.ro_vc $\cup$ T.rw_vc})

4: T.rw_vc $\leftarrow$ $\emptyset$

5: else

6: U.ro_vc $\leftarrow$ T.ro_vc

7: U.rw_vc $\leftarrow$ T.rw_vc

8: U.rw_vc $\leftarrow$ U.rw_vc $\cup$ {T.epoch}

9: U.joined $\leftarrow$ T.joined

10: U.lockset $\leftarrow$ T.lockset

11: U.IVC $\leftarrow$ T.IVC $\cup$ {getClock(U.epoch)}

12: T.epoch $\leftarrow$ T.epoch \+ 1

13: U.epoch $\leftarrow$ U.epoch \+ 1

14:procedure Join $\triangleright$ Task T joins with U

15: T.joined $\leftarrow$ T.joined $\cup$ {getTaskId(U.epoch)}

16:function CheckHB(c@u,T)

17: $\triangleright$ Check HB between epoch c@u and T’s access

18: return c@u $\preceq$ T.rw_vc or c@u $\preceq$ T.ro_vc or u $\in$ T.joined

###  3.1. Adapting Vector Clocks for Task Parallelism

We analyzed the performance of FastTrack and found that operations on task
vector clocks incur high time and space overhead. For example, the task join
operation is a bottleneck because it requires comparing and merging _all_ the
clock values in the child and the parent tasks’ vector clocks. Naïvely merging
the vector clocks is not required since most vector clock entries remain
unchanged during the lifetime of a task.

#### Tracking read-only clock entries

The first insight in FastRacer is that _most_ vector clock entries for a task
remain unchanged during the lifetime of the task, and the clock values
continue to be the same as in the parent task. Thus, maintaining per-task
copies of the clock entries is mostly redundant.

In FastRacer, a task vector clock is partitioned into a read-only (denoted by
ro_vc) and a read-write portion (denoted by rw_vc). Child tasks in FastRacer
maintain a reference to the ro_vc of their parents instead of maintaining
redundant copies. During a spawn operation (Algorithm 2), FastRacer first
checks if the size of rw_vc is greater than a threshold. If yes, then
FastRacer merges ro_vc and rw_vc of the parent task into a new ro_vc for the
child task and rw_vc of child task is kept empty. Otherwise, the child ro_vc
points to the parent ro_vc and the parent’s rw_vc is copied to the child’s
rw_vc. Avoiding needless copies and redundant operations on the read-only
portions of vector clocks helps reduce space overheads _and_ improve
performance. In the common case, most vector clock entries of a task remain
unchanged, i.e., the size of rw_vc is small. Complete vector clock copies
happen only when the size of rw_vc is greater than THRESHOLD.

#### Optimizing vector clock join

An access to a shared variable by a parent task after joining with a child
task always happens after the child’s accesses, since the accesses are
synchronized by the join operation. The second insight is that FastRacer does
not need to store the clock values of the child tasks _after_ the join
operation. Instead, tracking the set of all child tasks that have joined with
the parent task suffice.

Each task in FastRacer maintains the set of child tasks that have already
joined with it in a joined data structure. No vector clock join occurs when a
task T joins with task U, instead, the child task is added to the joined of
the parent task (Algorithm 2). When a parent task spawns a new child task, the
parent joined is copied to the child joined. The size of task vector clocks
reduces significantly due to the joined optimization. Note that a trivial
implementation of joined may not give performance benefits over FastTrack. We
use efficient set implementations based on the Union-Find data structure,
which reduces the overhead of set operations.

#### Vector clock caching

The vector clocks for a few tasks can be large even after the optimizations.
FastRacer uses explicit attributes to cache recently used vector clock values
to avoid the cost of looking up the map data structure representing vector
clocks. FastRacer indexes into the vector clock map when the thread id is not
among the most recently used.

###  3.2. Specializing for Async-Finish Programs

It can be expensive to maintain all concurrent readers of a shared variable in
task-based programs. FastRacer uses coarse-grained tracking of task
inheritance relationships to select relevant accesses from parallel
readers/writers,333When tasks use locks, two writes can happen in parallel but
do not constitute a race if they are protected by the same lock. which allows
maintaining constant per-variable metadata per-lockset (i.e., the set of locks
held by the task).

Figure 2. The inheritance tree for program in Figure 1(a).

#### Maintaining constant per-variable metadata

FastRacer models the parent-child relationship among different tasks with a
_task inheritance_ tree. The nodes represent tasks, and edges represent the
creation of child tasks by the parent. Figure 2 shows the inheritance tree for
the program shown in Figure 1(a) (ignore the IVC labels for now). FastRacer
uses the inheritance tree to _efficiently_ select two accesses out of multiple
concurrent accesses with the same lockset, such that any racy future access
that races with any one of the concurrent accesses must be racy with either
one of the two chosen last accesses. For parallel tasks accessing a variable
with the same lockset, FastRacer stores the access history of the two tasks
with the highest LCA in the inheritance tree. Consider the three accesses to
var1 from tasks T2, T4, and T5 in Figure 1(a). In the inheritance tree shown
in Figure 2, task nodes T2 and T4 (or T5) have the highest LCA, and so
FastRacer stores the access histories from T2 and T4 and discards T5. Any
later access to var1, which is not parallel with both T2 and T4, will not be
parallel with T5. So, discarding T5’s access information is correct.444In
async-finish semantics, a task must join with its ancestor, either immediate
or recursive. In case a parent task calls join, all children tasks within this
join scope, either immediate or recursive, join with it. The metadata stored
per shared variable in FastRacer is proportional to the number of the
different locksets with which the variable has been accessed.

The primary difference between a DPST and FastRacer’s inheritance tree is in
the _granularity_ of the nodes. While a DPST decomposes a task into several
unsynchronized regions represented by step nodes, an inheritance tree has just
one node per task. The coarser modeling makes the inheritance tree much
smaller and shallower than the DPST. Unlike a DPST, there is no left-to-right
ordering in an inheritance tree. While PTRacer uses DPST to check the
concurrency between two accesses and select accesses with the highest LCA,
FastRacer only does the latter with the inheritance tree. FastRacer uses
vector clocks for data race detection to compensate for the coarser modeling
and loss of ordering between the nodes (Section 3.3).

#### Inheritance vector clock

Instead of building an inheritance tree, FastRacer encodes the inheritance
relations in a per-task array of clock values called _Inheritance Vector
Clock_ (IVC) for better performance. An IVC is an immutable vector clock that
contains the clock values of all the reachable parents of a task T at the time
of the creation of T. An IVC identifies the unique path in the inheritance
tree from the root task to T, since a task spawn increments the scalar clock
of the caller task. Whenever a parent task creates a child task, FastRacer
copies the parent’s IVC to the child and appends the parent’s clock value at
the end of child IVC. In Figure 2, the IVC of the parent task T3 is copied to
the child task T4 and the current clock of T3 (assumed to be one) is appended.

Both IVC labeling and the Offset-Span (OS) labeling (Mellor-Crummey, 1991)
schemes compute a unique label from the label of the immediate predecessor,
and guarantee that the length of a task’s label will always be proportional to
the depth of the task in the inheritance tree. However, there are two
differences. First, the IVC of a task, once created, is immutable. Unlike OS
labeling, any further task join operations do not modify the IVC. Second, the
Span part of OS labeling can only be assigned after the task graph is
complete, i.e., OS labels cannot be computed while building the task graph.
Intuitively, IVC labels are more similar to the Offset part, with the
constraint that they do not get updated at join operations. Whereas prior work
uses OS labels for race detection (Mellor-Crummey, 1991; Gu and Mellor-
Crummey, 2018), FastRacer uses IVC labels to identify two accesses out of
multiple parallel accesses having the highest LCA in the inheritance tree.

#### Computing tasks with the highest LCA

To compute the highest LCA among three parallel tasks, FastRacer iterates over
the IVCs of all the tasks simultaneously and stops at the first point of
difference. After that, FastRacer chooses the task with a different clock
value and any one of the other two. If all the three clock values are
different, any two out of three tasks can be chosen. If FastRacer reaches the
end of an IVC for any task T, it indicates that T must be the parent of the
other two in the inheritance tree, and so, FastRacer chooses the parent task T
and any one from the other two. The tasks so chosen will have the highest LCA
in the inheritance tree (see Lemma 3.2). The computation overhead depends on
the sizes of the IVC, which is equal to the height of the inheritance tree.
Since an inheritance tree is much shallower compared to a DPST, the
computation is relatively efficient.

In Figure 1(a), the accesses to var1 from three parallel tasks, T2, T4, and
T5, are with the same lockset {L1}. The IVCs of the corresponding task nodes,
shown in Figure 2, are IVCT2=[1], IVCT4 = [2,1], and IVCT5 = [2,2]. To select
two out of the three accesses, FastRacer iterates over the three IVCs
simultaneously. The first point of difference is at the first entry itself:
IVCT2[0]=1, IVCT4[0]=IVCT5[0]=2. So, FastRacer selects a task with a different
clock value, i.e., T2 and any one of other two, say T4 (or T5). For the
example in Figure 2, tasks T2 and T4 (or T5) indeed have the highest LCA in
the inheritance tree.

###  3.3. Detecting Data Races

FastRacer extends the FastTrack algorithm (Section 2.1) to detect races and
update metadata.

#### Metadata

(a) Metadata maintained in FastTrack.

⬇

1class PerVariableMetadata {

2 epoch wr_md, rd_md; // Write and Read epoch

3 map<taskid, clock> rd_vc; // Read vector clock

4}

5class PerLockMetadata {

6 map<taskid, clock> vc;

7}

8class PerTaskMetadata {

9 epoch epoch;

10 map<taskid, clock> vc;

11}\end{lstlisting}

12 \end{subfigure}

13 % \hspace{5pt}

14 % \begin{subfigure}[t]{.48\textwidth}

15 % \caption{Metadata maintained in \nft.}

16 % \label{fig:nft-metadata}

17 % \centering

18 % \begin{lstlisting}[style=CPPStyle]

19 % class PerVariableMetadata {

20 % epoch *wr_md, *rd_md; // Write and read epoch

21 % map<taskid, clock> rd_vc;

22 % }

23 % class PerLockMetadata {

24 % map<taskid, clock> vc;

25 % }

26 % class PerTaskMetadata {

27 % epoch epoch;

28 % map<taskid, clock> ro_vc; // Rd-only vector clock

29 % map<taskid, clock> rw_vc; // Rd-wr vector clock

30 % set<taskid> joined; // All joined child tasks

31 % }\end{lstlisting}

32 % \end{subfigure}%

33 \hspace{5pt}

34 % // Pointers to locks held during a memory access

35 \begin{subfigure}[t]{.48\textwidth}

36 \caption{Metadata maintained in \fastpar.}

37 \label{fig:fastpar-metadata}

38 \centering

39 \begin{lstlisting}[style=CPPStyle]

40class PerVariableMetadata {

41 PerLockMetadata lock[];

42}

43class PerLockMetadata {

44 set<lockID> lockset;

45 epoch rd1, rd2; // Reader 1 and 2 metadata

46 IVC* rd1_ivc, rd2_ivc; // IVC of Reader 1 and 2

47 epoch wr1, wr2; // Writer 1 and 2 metadata

48 IVC* wr1_ivc,wr2_ivc; // IVC of Writer 1 and 2

49}

50class PerTaskMetadata {

51 epoch epoch;

52 map<taskid, clock> ro_vc; // Rd-only vector clock

53 map<taskid, clock> rw_vc; // Rd-wr vector clock

54 set<taskid> joined; // All joined child tasks

55 set<lockId> lockset; // Locks held by the task

56 int IVC[];

57}\end{lstlisting}

58 \end{subfigure}

59 \caption{Comparison of metadata state maintained in \ft and \fastpar.}

60 \label{fig:metadata-states}

61\end{figure}

62

63

64%%% Local Variables:

65%%% mode: latex

66%%% TeX-master: "paper"

67%%% End:

Figure LABEL:fig:metadata-states compares the metadata maintained in FastTrack
and FastRacer. Given a task T, FastTrack uses a vector clock for storing the
epoch values of _all_ other tasks (line 10, Section 3.3). The attributes
ro_vc, rw_vc, and joined in PerTaskMetadata in LABEL:fig:fastpar-metadata
correspond to the optimizations introduced in Section 3.2. While FastTrack
uses vector clocks to track lock operations, FastRacer uses the lockset
mechanism (Savage et al., 1997). Every task in FastRacer maintains and updates
lockset at lock acquire and release operations.

The per-variable state in FastRacer is an array of lock metadata. Each lock
metadata stores the access history of the variable with the distinct set of
locks held before the access. Every per-lock metadata contains four access
history entries, two each for reads and writes, which contain the epoch value
and a reference to the IVC of the task at the time of access. Storing
references to the IVCs suffice since they remain unchanged during the lifetime
of a task.

#### Race checks

When a shared variable is accessed, FastRacer iterates over all the lock
metadata corresponding to distinct locksets with which the shared memory
variable has been accessed. An empty intersection of the lockset of the
current access and the lock metadata implies potentially parallel accesses. If
the two locksets are disjoint, FastRacer checks if the epoch values stored in
the access history happens before the current access using vector clocks
(CHECKHB, Algorithm 2). If there is no such relationship, it implies that the
prior access is concurrent with the current access. Finally, FastRacer reports
a data race if one of the two accesses is a write.

Before accessing a shared variable x, FastTrack compares the current task’s
vector clock with the epoch(s) stored in x’s access history to determine if
the current access to x happens _after_ the past accesses (CHECKHB, Algorithm
1). FastRacer, apart from the vector clock entry check, also checks if the
tasks present in x’s access history belong to joined of the current task. If
all the tasks are present in joined, FastRacer infers that the current access
happens _after_ prior accesses. Since the vector clock is spread across ro_vc,
rw_vc, and joined, CHECKHB (Algorithm 2) checks the HB relation against all of
them.

#### Metadata updates

FastRacer updates the read metadata corresponding to the current lockset if a
read does not race with prior writes. FastRacer checks if any of the read
epochs in the lock metadata corresponding to the current lockset happens
before the current task’s access. If yes, then FastRacer updates that access
entry with the current task’s epoch and IVC. Otherwise, there are three
parallel reads, and FastRacer needs to select two with the highest LCA.
FastRacer iterates over the IVC of all three access entries and stops either
at the first point of difference or if one of the IVCs end. FastRacer stores
the access history of the task corresponding to the selected IVC and any one
of the other two. Using any one of the other two works since, in both the
cases, the two chosen tasks will have the highest LCA in the inheritance tree
(Section 3.2). Figure 3 shows an example of how FastRacer updates the read
metadata. Assume tasks T2, T3, and T4 all read a shared variable x and task T5
writes x. After the reads from T2 and T3, the two readers stored for the
variable x are T2 and T3, because both these tasks can run in parallel. Since
task T4 is spawned by T1 after T1 synchronizes with T2, so the read by T4
happens after the read of T2. The read metadata entry of T2 is replaced by T4.
Next, when T5 writes x, FastRacer checks the access with all previous reads
and reports a read-write race between the accesses from T4 and T5. The steps
performed by FastRacer on a write access are similar.

#### Synchronization operations

During a spawn operation (Algorithm 2), FastRacer checks if the size of rw_vc
is greater than a threshold. If yes, FastRacer merges ro_vc and rw_vc of the
parent task into a new ro_vc for the child task and rw_vc of the child is kept
empty. Otherwise, the child ro_vc references the parent ro_vc, and the child
rw_vc is copied from parent rw_vc. Thereafter, FastRacer copies the parent’s
joined and lockset to the child’s joined and lockset, respectively. In case of
a join operation, the joined of the parent task is updated to contain the id
of the child task.

A task’s vector clock is not updated in case of lock acquire and release
operations. Instead, FastRacer uses PTRacer’s mechanism to deal with lock
operations. Each task maintains a lockset. When a task T acquires a lock L,
the lockset of T is updated to contain lock L. In case of a lock release, L is
removed from the lockset. When T accesses a shared variable x, the lockset is
copied to the variable metadata. During a race check, FastRacer checks for the
intersection of the locksets from the metadata history to infer a data race.
In practice, variables are accessed with the same set of locks, and hence
maintaining access metadata for different sets of unique locks is reasonable.
Furthermore, metadata update operations depend on the size of the IVC, but we
find that the maximum depth of the inheritance tree is small ($\leq 30$ for
our benchmarks).

Figure 3. An async-finish program with five tasks T1–T5 and the corresponding
inheritance tree.

###  3.4. Characterizing FastRacer

#### Race coverage.

While FastTrack’s race coverage is limited to the observed schedule, FastRacer
can detect per-input apparent races like PTRacer. Although both FastTrack and
FastRacer use vector clocks to track happens-before (HB) relations among
accesses, FastRacer can detect races in _other_ schedules due to the following
algorithmic differences with FastTrack.

  * •

FastTrack stores per-thread vector clocks. The races reported by FastTrack can
vary across schedules since many tasks can map to a single thread, and the
exact sequence of tasks mapped may vary across schedules. FastRacer stores
vector clocks per task, and is not impacted by the mapping of tasks to
threads.

  * •

FastTrack tracks the HB relations to establish order among synchronization
operations, which is sensitive to the order of lock operations and varies
across schedules. FastRacer uses the lockset technique to track
synchronization operations and stores two reads and two writes per lockset in
per-variable metadata. The metadata structure enables FastRacer to detect
races irrespective of the order of lock operations, so the number of races
reported is the same across schedules.

#### Correctness.

The following two lemmas help prove the correctness of FastRacer. We discuss
the proofs in the Appendix.

###### Lemma 3.1.

Storing access entries of only two tasks such that their LCA is the highest is
sufficient. A future access to the variable, which is racy with any of the
existing parallel accesses, must be racy with any one of the two access
entries with the highest LCA.

###### Lemma 3.2.

The IVC correctly computes the two tasks with the highest LCA among three
parallel tasks.

##  4\. Implementation

Our implementation extends the PTRacer artifact.555https://github.com/rutgers-
apl/PTRacer A static compiler pass using LLVM 3.7 instruments load and store
instructions in C++programs, and inserts function calls to execute the
appropriate dynamic race detection analysis. The implementation uses Intel
Threading Building Blocks (TBB) (Reinders, 2007) for task parallelism. The
public implementation of PTRacer reports wrong race results for the benchmarks
fluidanimate, kmeans, streamcluster, and sort (see Section 5.1). We found an
implementation error was corrupting the DPST built by PTRacer, and there was a
race while updating a global array data structure used for LCA hashing. After
fixing these issues, the race reports were the same across all the tools. Our
modifications have minimal ($\leq$1%) impact on the performance of PTRacer,
and we use our fixed version for the evaluation. Our prototype implementation
of FastRacer extend the same static compiler pass to ensure all the prototypes
do the same work. We have also reimplemented the FastTrack algorithm (Flanagan
and Freund, 2009, 2017).

#### Race detection for fork-join programs

Utterback et al. propose a parallel and asymptotically optimal algorithm
called WSP-Order for race detection of fork-join programs (Utterback et al.,
2016). The algorithm uses two order maintenance (OM) data structures to
maintain two total orders of all _strands_ in the computation. A strand is a
sequence of instructions that contain no parallel primitives and executes
sequentially. A strand x logically precedes strand y if and only if x precedes
y in both orderings. These orderings are sufficient to determine SP
relationships. The two OM data structures support constant-time operations
like insert and query, and _most_ concurrent updates do not need
synchronization. However, large parts of the OM data structure are updated
during relabel operations and hence require synchronization. Since relabel
operations are serialized, the algorithm modifies a work-stealing task
scheduler to prioritize the operations. Furthermore, workers blocked on an
insert or a query operation help with the relabel instead of being idle. Note
that the WSP-Order algorithm does not support lock-based synchronization and
requires tight coupling with a work-stealing scheduler for good performance
(Utterback et al., 2016).

The public implementation of WSP-Order is called
C-RACER.666https://github.com/wustl-pctg/cracer Since the original
implementation uses the Batcher runtime (Agrawal et al., 2014), we reimplement
C-RACER with Intel TBB in LLVM for a fair comparison. An important
contribution in the original C-RACER work is the parallelization of the
relabel operations. We have not implemented task scheduler support for
parallel relabel operations, relabels in our implementation are serial. The
total time taken in the serial relabel operations is small in our experiments.
The run time of the benchmarks we report for C-RACER _does not_ account for
the time taken for the relabel operations, which is a lower bound (Section
5.2). Note that our reimplementation can also differ in performance from the
original implementation because of differences in the schedulers.

We reuse eighty unit test cases from the PTRacer artifact and designed new
test cases to check the correctness of our FastTrack, FastRacer, and C-RACER
implementations. The unit tests include both racy and non-racy programs, _with
and without_ locks. All the prototypes pass the unit tests. Our
implementations are publicly
available.777https://github.com/prospar/fastracer-pmam-2022

##  5\. Evaluation

This section compares FastRacer with the closest prior work, FastTrack
(Flanagan and Freund, 2009), PTRacer (Yoga et al., 2016), and C-RACER
(Utterback et al., 2016).

###  5.1. Experimental Setup

#### Benchmarks

We reuse twelve TBB-based applications used by PTRacer for our evaluation.
These include four applications, blackscholes, fluidanimate, streamcluster,
and swaptions, from the PARSEC benchmark suite (Bienia et al., 2008), five
geometry and graphics applications, convexHull, delRefine, delTriang,
nearestNeigh, and rayCast, from the PBBS benchmark suite (Shun et al., 2012),
and three applications, karatsuba, kmeans, and sort, from the Structured
Parallel Programming book (McCool et al., 2012). We left out the PARSEC
application, bodytrack, because of a compilation error, and ignore the C-RACER
benchmarks because they use Cilk-5 (Utterback et al., 2016).

The benchmarks follow spawn-sync semantics where a child task joins with its
immediate parent (async-finish semantics are more general) and do not use
locks, so we were able to run C-RACER successfully for all the benchmarks.

#### Evaluation platform

The experiments execute on an Intel Xeon Gold 5218 system with one 16-core
processor with hyperthreading disabled, 128 GB DDR4 primary memory, running
Ubuntu Linux 20.04.3 LTS with kernel version 5.11.0.

Figure 4. Performance comparison of the different techniques normalized to the
unmodified execution time of the benchmarks.

###  5.2. Performance Results

Figure 4 reports the performance of C-RACER, PTRacer, and FastRacer for all
the benchmarks (arranged alphabetically). Every bar averages ten trials and is
normalized to the baseline, which runs the unmodified benchmarks without
instrumentation. Smaller bars mean better run times. By default, the TBB
scheduler creates $c$ threads and multiplexes the tasks to the $c$ threads,
where $c$ is the number of cores in the system. The results in Figure 4 are
with 16 threads.

Our reimplementation of C-RACER incurs an overhead of 10.66X over the
unmodified applications. The average performance slowdown incurred by PTRacer
is 7.70X, while it is 6.41X for FastRacer. FastRacer shows substantial
improvement for multiple benchmarks like convexHull, delTriang, fluidanimate,
kmeans, and rayCast. The better performance of FastRacer is due to improved
locality from vector clocks compared to cache-unfriendly tree traversals in
C-RACER and PTRacer. On average, FastRacer outperforms both C-RACER and
PTRacer by 1.66X and 1.20X, respectively.

We cannot directly compare C-RACER results to the original work (Utterback et
al., 2016) because of differences in the implementation, benchmarks, and
evaluation infrastructure. However, we reemphasize that our C-RACER results do
not include the cost of relabel operations. The original PTRacer work reports
an average slowdown of 6.7X, compared to 7.70X in our experiments. In addition
to the differences in the evaluation platforms and bug fixes, different
execution times of the benchmarks in the absence of perfect scaling will lead
to different relative overheads. We have verified that our modifications have
minimal ($\leq$1% difference) impact on the performance of PTRacer.

FastTrack successfully executed with four benchmarks that required less
memory, blackscholes, fluidanimate, karatsuba, and sort, and got killed on the
other benchmarks. The overhead of FastTrack for the four benchmarks is 50.26X,
and FastRacer outperforms FastTrack by 4.62X. Given that FastRacer builds on
FastTrack, this result shows that the task and variable vector clock
optimizations proposed in FastRacer are effective in reducing both run time
and space overheads.

| UM | FT | CR | PT | FR
---|---|---|---|---|---
blackscholes | 0.62 | 9.64 | 10.38 | 54.78 | 48.03
fluidanimate | 0.51 | 69.93 | 0.58 | 9.17 | 2.04
streamcluster | 0.84 | - | 1.17 | 22.76 | 6.91
swaptions | 0.19 | - | 0.98 | 17.34 | 3.87
convexHull | 1.69 | - | 2.97 | 19.94 | 12.71
delRefine | 3.71 | - | 6.25 | 125.37 | 125.39
delTriang | 3.63 | - | 8.19 | 113.69 | 106.77
nearestneigh | 2.19 | - | 5.60 | 106.86 | 125.26
rayCast | 1.28 | - | 4.08 | 18.37 | 14.35
karatsuba | 0.02 | 0.86 | 0.18 | 9.34 | 2.81
kmeans | 0.11 | - | 2.52 | 15.82 | 5.99
sort | 0.15 | 18.96 | 0.20 | 9.87 | 2.40
Table 1. Comparison of the memory overhead (in GBs).

#### Memory overhead

Table 1 compares the peak memory requirement of each benchmark with the four
techniques, as reported by the Massif tool in Valgrind (Nethercote and Seward,
2007). Column 2, _UM_ , shows the memory requirement of the unmodified
application, while _FT_ , _CR_ , _PT_ , and _FR_ stand for FastTrack, C-RACER,
PTRacer, and FastRacer, respectively. The results show that using IVCs for
encoding task inheritance in FastRacer compared to the fine-grained DPST
structure in PTRacer provides significant memory savings in maintaining per-
task metadata, especially for fluidanimate, karatsuba, kmeans, sort, and
swaptions. C-RACER usually requires the least memory since it maintains order
maintenance structures, but has high performance overhead compared to
FastRacer.

(a) blackscholes

(b) convexHull

(c) delRefine

(d) delTriang

(e) fluidanimate

(f) karatsuba

(g) kmeans

(h) nearestNeigh

(i) rayCast

(j) sort

(k) streamcluster

(l) swaptions

Figure 5. Scalability results of the benchmarks on the Intel Gold platform
described in Section 5.1.

#### Scalability

Figure 5 shows the scalability plots of the benchmarks as we vary the number
of threads (in powers of two) used by the TBB scheduler. Other experimental
setup are the same as in Figure 4. The _Unmodified_ configuration in the
figure shows that most applications scale well, excepting blackscholes,
convexHull, and karatsuba. FastRacer scales better than PTRacer for delTriang,
kmeans, and swaptions, for the range of thread counts we have evaluated. The
scaling behavior of C-RACER, PTRacer, and FastRacer are very similar for the
remaining benchmarks.

#### Platform sensitivity

We evaluate the sensitivity of the optimizations by re-running experiments on
an Intel Xeon Silver 4114 system with two ten core processors (twenty 2.0 GHz
cores in total) with hyperthreading turned off, 128 GB primary memory, running
Ubuntu Linux 18.04.6 LTS with kernel version 4.15.0. The rest of the
methodology is the same as Figure 4. C-RACER, PTRacer, and FastRacer incur
overheads of 11.60X, 9.44X, and 6.85X, respectively. Although, the overheads
on the multi-socket Xeon Silver platform are slightly greater compared to the
Xeon Gold platform, the general trend is the same. FastRacer outperforms both
C-RACER and PTRacer by 1.69X and 1.38X, respectively. The study confirms the
effectiveness of the proposed optimizations _across_ different platforms.

FastRacer outperforms prior work on the _same_ set of benchmarks as used in
PTRacer. Given the generic nature of the optimizations, we expect a similar
qualitative trend for benchmarks where threads join with arbitrary ancestors
(e.g., async-finish semantics). More importantly, FastRacer disproves the
assumption made in _all_ prior work that vector-clock-based analysis is not
suited for task-based programs.

###  5.3. Data Races and Run-time Statistics

Table 2 summarizes the run-time statistics. The data is the average from 10
trials with a statistic-collecting configuration. Columns 2–4 in the table
show the average number of tasks spawned by the benchmarks and the number of
read and write accesses instrumented by the static compiler pass in LLVM.
Columns 5–7 show the number of data races reported by the different tools. To
stress-test the correctness of our implementations, we introduced data races
in a few benchmarks that already did not have known races. The suffix “-r”
denotes benchmarks that have been modified to introduce races for evaluation.
All the tools are expected to report the same number of races for a given
application with a fixed input. C-RACER (CR), PTRacer (PT), and FastRacer (FR)
report the same violations for all the benchmarks. Please note that the
evaluation includes our fixes to PTRacer (Section 4).

| # Tasks |  ACC ($\times 10^{6}$) | Data Races
---|---|---|---
|  ($\times 10^{3}$) | RDs | WRs | CR | PT | FR
blackscholes | 0.20 | 90 | 50 | 21 | 21 | 21
fluidanimate-r | 1.60 | 26 | 0.7 | 40 | 40 | 40
streamcluster-r | 180 | 363 | 13 | 80 | 80 | 80
swaptions | 960 | 77 | 77 | 0 | 0 | 0
convexHull | 8.50 | 30 | 0 | 0 | 0 | 0
delRefine | 1000 | 15 | 0 | 0 | 0 | 0
delTriang | 790 | 30 | 20 | 0 | 0 | 0
nearestNeigh | 2800 | 51 | 8 | 0 | 0 | 0
rayCast | 1900 | 160 | 0 | 0 | 0 | 0
karatsuba | 1.98 | 3.4 | 0.8 | 0 | 0 | 0
kmeans-r | 35 | 570 | 10 | 75 | 75 | 75
sort | 0.70 | 11 | 0.06 | 1024 | 1024 | 1024
Table 2. Run-time statistics across different benchmarks.

##  6\. Related Work

In the following, we discuss other related work that has not already been
discussed.

#### Race detection for task-based programs

Mellor-Crummey exploited the structural property of fork-join programs to show
that tracking two readers and a single writer per memory location is
sufficient for sound data race detection (Mellor-Crummey, 1991). Since then,
there has been much work to design race detection algorithms to utilize the
serial-parallel (SP) structure of programs with constant space overhead for
metadata (Feng and Leiserson, 1997; Cheng et al., 1998). ESP-bags is an
extension to SP-bags that supports the finish construct in async-finish
programs (Raman et al., 2010). However, these approaches constrain the program
to execute serially in depth-first order, which does not scale. Tardis does
not keep track of the SP relationships among program strands (Lu et al.,
2014). Instead, Tardis maintains log-based access sets and lazily detects
races by checking for overlapping intersections of access sets of logically
parallel sub-computations at join points.

#### Race detection for multithreaded programs

Static analysis can potentially detect all _feasible_ data races across all
possible executions (i.e., no false negatives), but usually do not scale to
large programs and suffer from false positives, which developers loathe (Naik
and Aiken, 2007; Naik et al., 2006; Blackshear et al., 2018). Dynamic analyses
have the potential to be sound and precise for the _observed_ executions. Many
dynamic data race detection analyses track the happens-before relation to
infer data races (Bond et al., 2010; Wood et al., 2017; Serebryany and
Iskhodzhanov, 2009; Serebryany et al., 2012; Pozniansky and Schuster, 2007).
_Lockset_ analysis reports data races when a locking discipline is violated,
but can report false races (Savage et al., 1997; von Praun and Gross, 2001;
Choi et al., 2002; O’Callahan and Choi, 2003). Hybrid techniques integrate
both HB and lockset analysis (O’Callahan and Choi, 2003; Yu et al., 2005), but
continue to suffer from the disadvantages of both techniques. Other techniques
sacrifice soundness for performance by sampling memory accesses (Erickson et
al., 2010; Biswas et al., 2017; Bond et al., 2010; Marino et al., 2009) or
require hardware support to speed up the race detection analysis (Devietti et
al., 2012; Wood et al., 2014; Peng et al., 2017). Prior analyses have also
explored detecting a subset of data races that arise due to conflicts among
overlapping regions (Lucia et al., 2010; Biswas et al., 2015; Effinger-Dean et
al., 2012). Data race detection analyses have also been proposed for parallel
programming models such as OpenMP (Atzeni et al., 2016; Gu and Mellor-Crummey,
2018) and GPUs (Eizenberg et al., 2017; Kamath et al., 2020; Kamath and Basu,
2021).

#### Improve race detection coverage

Recent work has explored exposing as many true races as possible by observing
one or a few dynamic executions. The idea is to explore different valid
interleavings to maximize detecting data races that can occur across
schedules. Many techniques perturb the execution in an attempt to break
spurious HB relations (Eslamimehr and Palsberg, 2014; Huang et al., 2014; Sen,
2008). _Predictive_ techniques aim to detect data races that can occur in
other correct reorderings of memory accesses by observing one dynamic
execution. Such techniques use partial order relations that are weaker than HB
to allow reconstructing other valid memory reorderings (Smaragdakis et al.,
2012; Roemer et al., 2018; Kini et al., 2017; Roemer et al., 2020).

##  7\. Conclusion

Whereas prior work has overlooked the possibility of using vector clocks for
task-based programs (Utterback et al., 2016; Yoga et al., 2016; Raman et al.,
2012), FastRacer shows how to achieve competitive performance with a curated
set of optimizations. FastRacer introduces novel optimizations that reduce the
metadata redundancy and alleviate the performance bottlenecks with task vector
clocks. FastRacer also exploits the structured execution of async-finish
programs to limit the per-variable metadata overhead by using a coarse-but-
efficient encoding of task inheritance relationships. FastRacer shows
substantial performance improvements over FastTrack, and outperforms state-of-
art approaches C-RACER and PTRacer. FastRacer’s proposed vector clock
optimizations allow for efficient dynamic data race detection for task-based
async-finish programs.

###### Acknowledgements.

We thank Michael D. Bond for feedback on the text, the PTRacer authors for
help with their implementation, and Vivek Kumar for discussions and advice.
This material is based upon work supported by IITK Initiation Grant and
Sponsor Science and Engineering Research Board  under Grant Grant
#SRG/2019/000384.

## References

  * (1)
  * Agrawal et al. (2014) Kunal Agrawal, Jeremy T. Fineman, Kefu Lu, Brendan Sheridan, Jim Sukha, and Robert Utterback. 2014\.  Provably Good Scheduling for Parallel Programs That Use Data Structures through Implicit Batching. In _SPAA_. 84–95.
  * Atzeni et al. (2016) S. Atzeni, G. Gopalakrishnan, Z. Rakamaric, D. H. Ahn, I. Laguna, M. Schulz, G. L. Lee, J. Protze, and M. S. Müller. 2016.  ARCHER: Effectively Spotting Data Races in Large OpenMP Applications. In _IPDPS_. 53–62.
  * Bender et al. (2004) Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles E. Leiserson. 2004.  On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs. In _SPAA_. 133–144.
  * Bienia et al. (2008) Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh, and Kai Li. 2008.  The PARSEC Benchmark Suite: Characterization and Architectural Implications. In _PACT_. 72–81.
  * Biswas et al. (2017) Swarnendu Biswas, Man Cao, Minjia Zhang, Michael D. Bond, and Benjamin P. Wood. 2017.  Lightweight Data Race Detection for Production Runs. In _CC_. 11–21.
  * Biswas et al. (2015) Swarnendu Biswas, Minjia Zhang, Michael D. Bond, and Brandon Lucia. 2015.  Valor: Efficient, Software-Only Region Conflict Exceptions. In _OOPSLA_. 241–259.
  * Blackshear et al. (2018) Sam Blackshear, Nikos Gorogiannis, Peter W. O’Hearn, and Ilya Sergey. 2018.  RacerD: Compositional Static Race Detection.  _PACMPL_ 2, OOPSLA, Article 144 (Oct. 2018).
  * Blumofe et al. (1995) Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. 1995\.  Cilk: An Efficient Multithreaded Runtime System. In _PPoPP_. 207–216.
  * Bond et al. (2010) Michael D. Bond, Katherine E. Coons, and Kathryn S. McKinley. 2010.  PACER: Proportional Detection of Data Races. In _PLDI_. 255–268.
  * Cavé et al. (2011) Vincent Cavé, Jisheng Zhao, Jun Shirako, and Vivek Sarkar. 2011\.  Habanero-Java: the New Adventures of Old X10. In _PPPJ_. 51–61.
  * Charles et al. (2005) Philippe Charles, Christian Grothoff, Vijay Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar. 2005.  X10: An Object-Oriented Approach to Non-Uniform Cluster Computing. In _OOPSLA_. 519–538.
  * Cheng et al. (1998) Guang-Ien Cheng, Mingdong Feng, Charles E. Leiserson, Keith H. Randall, and Andrew F. Stark. 1998\.  Detecting Data Races in Cilk Programs That Use Locks. In _SPAA_. 298–309.
  * Choi et al. (2002) Jong-Deok Choi, Keunwoo Lee, Alexey Loginov, Robert O’Callahan, Vivek Sarkar, and Manu Sridharan. 2002\.  Efficient and Precise Datarace Detection for Multithreaded Object-Oriented Programs. In _PLDI_. 258–269.
  * Devietti et al. (2012) Joseph Devietti, Benjamin P. Wood, Karin Strauss, Luis Ceze, Dan Grossman, and Shaz Qadeer. 2012.  RADISH: Always-On Sound and Complete Race Detection in Software and Hardware. In _ISCA_. 201–212.
  * Effinger-Dean et al. (2012) Laura Effinger-Dean, Brandon Lucia, Luis Ceze, Dan Grossman, and Hans-J. Boehm. 2012\.  IFRit: Interference-Free Regions for Dynamic Data-Race Detection. In _OOPSLA_. 467–484.
  * Eizenberg et al. (2017) Ariel Eizenberg, Yuanfeng Peng, Toma Pigli, William Mansky, and Joseph Devietti. 2017.  BARRACUDA: Binary-level Analysis of Runtime RAces in CUDA Programs. In _PLDI_. 126–140.
  * Erickson et al. (2010) John Erickson, Madanlal Musuvathi, Sebastian Burckhardt, and Kirk Olynyk. 2010.  Effective Data-Race Detection for the Kernel. In _OSDI_. 1–16.
  * Eslamimehr and Palsberg (2014) Mahdi Eslamimehr and Jens Palsberg. 2014.  Race Directed Scheduling of Concurrent Programs. In _PPoPP_. 301–314.
  * Feng and Leiserson (1997) Mingdong Feng and Charles E. Leiserson. 1997.  Efficient Detection of Determinacy Races in Cilk Programs. In _SPAA_. 1–11.
  * Flanagan and Freund (2004) Cormac Flanagan and Stephen N Freund. 2004.  Atomizer: A Dynamic Atomicity Checker for Multithreaded Programs. In _POPL_. 256–267.
  * Flanagan and Freund (2009) Cormac Flanagan and Stephen N. Freund. 2009.  FastTrack: Efficient and Precise Dynamic Race Detection. In _PLDI_. 121–133.
  * Flanagan and Freund (2017) Cormac Flanagan and Stephen N. Freund. 2017.  _The FastTrack2 Race Detector_.  Technical Report. Williams College.
  * Frigo et al. (1998) Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. 1998\.  The Implementation of the Cilk-5 Multithreaded Language. In _PLDI_. 212–223.
  * Gu and Mellor-Crummey (2018) Yizi Gu and John Mellor-Crummey. 2018.  Dynamic Data Race Detection for OpenMP Programs. In _SC_. Article 61, 12 pages.
  * Huang et al. (2014) Jeff Huang, Patrick O’Neil Meredith, and Grigore Rosu. 2014\.  Maximal Sound Predictive Race Detection with Control Flow Abstraction. In _PLDI_. 337–348.
  * Kamath and Basu (2021) Aditya K. Kamath and Arkaprava Basu. 2021.  iGUARD: In-GPU Advanced Race Detection. In _SOSP_. 49–65.
  * Kamath et al. (2020) Aditya K. Kamath, Alvin A. George, and Arkaprava Basu. 2020\.  ScoRD: A Scoped Race Detector for GPUs. In _ISCA_. 1036–1049.
  * Kasikci et al. (2012) Baris Kasikci, Cristian Zamfir, and George Candea. 2012\.  Data Races vs. Data Race Bugs: Telling the Difference with Portend. In _ASPLOS_. 185–198.
  * Kini et al. (2017) Dileep Kini, Umang Mathur, and Mahesh Viswanathan. 2017\.  Dynamic Race Prediction in Linear Time. In _PLDI_. 157–170.
  * Lea (2000) Doug Lea. 2000.  A Java Fork/Join Framework. In _ACM Conference on Java Grande_. New York, NY, USA, 36–43.
  * Leveson and Turner (1993) N. G. Leveson and C. S. Turner. 1993.  An Investigation of the Therac-25 Accidents.  _IEEE Computer_ 26, 7 (July 1993), 18–41.
  * Lu et al. (2014) Li Lu, Weixing Ji, and Michael L. Scott. 2014.  Dynamic Enforcement of Determinism in a Parallel Scripting Language. In _PLDI_. 519–529.
  * Lucia et al. (2010) Brandon Lucia, Luis Ceze, Karin Strauss, Shaz Qadeer, and Hans-J. Boehm. 2010.  Conflict Exceptions: Simplifying Concurrent Language Semantics with Precise Hardware Exceptions for Data-Races. In _ISCA_. 210–221.
  * Marino et al. (2009) Daniel Marino, Madanlal Musuvathi, and Satish Narayanasamy. 2009\.  LiteRace: Effective Sampling for Lightweight Data-Race Detection. In _PLDI_. 134–143.
  * McCool et al. (2012) Michael McCool, James Reinders, and Arch Robison. 2012\.  _Structured Parallel Programming: Patterns for Efficient Computation_ (first ed.).  Morgan Kaufmann Publishers Inc.
  * Mellor-Crummey (1991) John Mellor-Crummey. 1991\.  On-the-Fly Detection of Data Races for Programs with Nested Fork-Join Parallelism. In _SC_. 24–33.
  * Naik and Aiken (2007) Mayur Naik and Alex Aiken. 2007.  Conditional Must Not Aliasing for Static Race Detection. In _POPL_. 327–338.
  * Naik et al. (2006) Mayur Naik, Alex Aiken, and John Whaley. 2006.  Effective Static Race Detection for Java. In _PLDI_. 308–319.
  * Nethercote and Seward (2007) Nicholas Nethercote and Julian Seward. 2007.  Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation. In _PLDI_. 89–100.
  * Netzer and Miller (1992) Robert H. B. Netzer and Barton P. Miller. 1992.  What Are Race Conditions? Some Issues and Formalizations.  _ACM Letters on Programming Language and Systems_ 1, 1 (March 1992), 74–88.
  * O’Callahan and Choi (2003) Robert O’Callahan and Jong-Deok Choi. 2003.  Hybrid Dynamic Data Race Detection. In _PPoPP_. 167–178.
  * PCWorld (2012) PCWorld. 2012.  Nasdaq’s Facebook Glitch Came From Race Conditions.  Online.  http://www.pcworld.com/article/255911/nasdaqs_facebook_glitch_came_from_race_conditions.html
  * Peng et al. (2018) Yuanfeng Peng, Christian DeLozier, Ariel Eizenberg, William Mansky, and Joseph Devietti. 2018\.  SLIMFAST: Reducing Metadata Redundancy in Sound and Complete Dynamic Data Race Detection. In _IPDPS_. 835–844.
  * Peng et al. (2017) Yuanfeng Peng, Benjamin P. Wood, and Joseph Devietti. 2017\.  PARSNIP: Performant Architecture for Race Safety with No Impact on Precision. In _MICRO_. 490–502.
  * Poulsen (2004) K. Poulsen. 2004\.  SecurityFocus News: Tracking the blackout bug.  http://www.securityfocus.com/news/8412
  * Pozniansky and Schuster (2007) Eli Pozniansky and Assaf Schuster. 2007.  MultiRace: Efficient On-the-Fly Data Race Detection in Multithreaded C++ Programs.  _CCPE_ 19, 3 (2007), 327–340.
  * Raman et al. (2010) Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin Vechev, and Eran Yahav. 2010.  Efficient Data Race Detection for Async-Finish Parallelism. In _RV_. 368–383.
  * Raman et al. (2012) Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin Vechev, and Eran Yahav. 2012.  Scalable and Precise Dynamic Datarace Detection for Structured Parallelism. In _PLDI_. 531–542.
  * Reinders (2007) James Reinders. 2007\.  _Intel Threading Building Blocks_.  O’Reilly Media, Inc.
  * Roemer et al. (2018) Jake Roemer, Kaan Genç, and Michael D. Bond. 2018\.  High-coverage, Unbounded Sound Predictive Race Detection. In _PLDI_. 374–389.
  * Roemer et al. (2020) Jake Roemer, Kaan Genç, and Michael D. Bond. 2020\.  SmartTrack: Efficient Predictive Race Detection. In _PLDI_. 747–762.
  * Savage et al. (1997) Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. 1997\.  Eraser: A Dynamic Data Race Detector for Multi-threaded Programs. In _SOSP_. 27–37.
  * Sen (2008) Koushik Sen. 2008\.  Race Directed Random Testing of Concurrent Programs. In _PLDI_. 11–21.
  * Serebryany and Iskhodzhanov (2009) Konstantin Serebryany and Timur Iskhodzhanov. 2009.  ThreadSanitizer – data race detection in practice. In _WBIA_. 62–71.
  * Serebryany et al. (2012) Konstantin Serebryany, Alexander Potapenko, Timur Iskhodzhanov, and Dmitriy Vyukov. 2012.  Dynamic Race Detection with LLVM Compiler. In _RV_. 110–114.
  * Shun et al. (2012) Julian Shun, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Aapo Kyrola, Harsha Vardhan Simhadri, and Kanat Tangwongsan. 2012\.  Brief Announcement: The Problem Based Benchmark Suite. In _SPAA_. 68–70.
  * Smaragdakis et al. (2012) Yannis Smaragdakis, Jacob Evans, Caitlin Sadowski, Jaeheon Yi, and Cormac Flanagan. 2012.  Sound Predictive Race Detection in Polynomial Time. In _POPL_. 387–400.
  * Utterback et al. (2016) Robert Utterback, Kunal Agrawal, Jeremy T. Fineman, and I-Ting Angelina Lee. 2016.  Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs. In _SPAA_. 83–94.
  * von Praun and Gross (2001) Christoph von Praun and Thomas R. Gross. 2001.  Object Race Detection. In _OOPSLA_. 70–82.
  * Wood et al. (2017) Benjamin P. Wood, Man Cao, Michael D. Bond, and Dan Grossman. 2017.  Instrumentation Bias for Dynamic Data Race Detection.  _PACMPL_ 1, OOPSLA, Article 69 (Oct. 2017), 31 pages.
  * Wood et al. (2014) Benjamin P. Wood, Luis Ceze, and Dan Grossman. 2014\.  Low-Level Detection of Language-Level Data Races with LARD. In _ASPLOS_. 671–686.
  * Yoga and Nagarakatte (2016) Adarsh Yoga and Santosh Nagarakatte. 2016.  Atomicity Violation Checker for Task Parallel Programs. In _CGO_. 239–249.
  * Yoga et al. (2016) Adarsh Yoga, Santosh Nagarakatte, and Aarti Gupta. 2016\.  Parallel Data Race Detection for Task Parallel Programs with Locks. In _FSE_. 833–845.
  * Yu and Sarkar (2018) Lechen Yu and Vivek Sarkar. 2018.  GT-Race: Graph Traversal Based Data Race Detection for Asynchronous Many-Task Parallelism. In _Euro-Par_. 59–73.
  * Yu et al. (2005) Yuan Yu, Tom Rodeheffer, and Wei Chen. 2005.  RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Tracking. In _SOSP_. 221–234.

##  Appendix A Appendix

###  A.1. Correctness of FastRacer

###### Lemma A.1.

Storing access entries of only two tasks such that their LCA using the
inheritance tree is the highest is sufficient. That is, a future access to the
variable, which is racy with any of the existing parallel accesses, must be
racy with any one of the two access entries with the highest LCA.

###### Proof.

Let tasks T1, T2, and T3 be three tasks that access shared variable var in
parallel with the same lockset. Let the two tasks with the highest LCA in the
inheritance tree be T1 and T2, their LCA be task P, and T3 be any task other
than T1 and T2. All the parallel tasks, including T1, T2, and T3 must be
immediate or recursive children of P, i.e., P is the common ancestor of all
T1,T2 and T3. An immediate child means that the task has been spawned by P and
a recursive child means that the task has been spawned by some other task
which itself is an immediate or recursive child of P.

Let us assume that in the future, another task T accesses the shared variable
var and the access is racy with task T3, but not with T1 and T2. This implies
the access to var by T _happens after_ both T1 and T2. Since T1, T2, and T3
have the same lockset, and T is racy with T3, so the intersection of their
locksets must be empty. This implies that we have two non-racy accesses from
tasks T1 and T to var even when the accesses are not protected by the same
lock. This can only happen if T1 and T are ordered by task management
constructs. That is, one of the following must hold: (i) T1 accesses var, and
then spawns T, either immediate or recursive, or (ii) T1 is present in joined
of T. By a similar argument, one can draw a similar conclusion for T2, i.e.,
one of the following must hold: (i) T2 accesses var and then spawns T, either
immediate or recursive, or (ii) T2 is present in joined of T.

Upon careful observation, one can see that constraints for T1 and T2 can hold
simultaneously if and only if both T1 and T2 are present in joined of T. Other
possibilities lead to contradictions. This can only happen if some common
ancestor P′ of tasks T1 and T2 calls join, in which all children tasks within
join scope of task P′ will join with it, and which then spawns task T copying
joined from P′ to T (P′ can be T itself). Since tasks T1 and T2 have the
highest LCA in the inheritance tree, and P′ is the common ancestor of T1 and
T2, P′ must be the ancestor of T3 as well. Therefore, T3 will be under join
scope of P′ and so should be present in the joined of P′ after join call, and
therefore to task T joined as well, like T1 and T2.

Sice T3 would be present in joined of T, current access by T will have happens
_after_ relationship with T3’s access and so would be non-racy. But we had
assumed that T3 access is racy with current T access, leading to a
contradiction. This proves our lemma that any future access to the variable,
which is racy with any of the existing parallel accesses, must be racy with at
least one of the two access entries with the highest LCA.

∎

###### Lemma A.2.

The inheritance vector clock (IVC) correctly computes the two tasks with the
highest LCA among three parallel tasks.

(a)

(b)

Figure 6. Different cases possible during LCA computation.

###### Proof.

Consider three parallel tasks T1, T2, and T3 in an inheritance tree (Figure
6). We need to consider the following two cases.

Case 1.:

LCA(T1, T2), LCA(T2, T3), and LCA(T1, T3) are the same (Figure 5(a)). Here,
any pair of tasks chosen from the set {T1,T2,T3} will have same LCA, and so
the claim holds.

Case 2.:

Without loss of generality, let LCA(T2, T3) be strictly higher than LCA(T1,
T2) (Figure 5(b)). Let LCA(T1, T2) = P1 and LCA(T2, T3) = P. Then, P will be
the ancestor of P1. By the structure of IVC, the IVC of a task contains the
IVC of its ancestor as a prefix. So, the IVCs of tasks T1 and T2 will have the
IVC of P1 as a prefix, and the IVC of tasks P1 and T3 will have the IVC of P
as a prefix. The IVCs of these tasks are as follows:

  * •:

IVC(P1) = IVC(P) + [$a$…$b$]

  * •:

IVC(T1) = IVC(P1) + [$x_{1}$…$x_{n}$] = IVC(P) + [$a$…$b$]+ [$x_{1}$…$x_{n}$]

  * •:

IVC(T2) = IVC(P1) + [$y_{1}$…$y_{m}$] = IVC(P) \+ [$a$…$b$]+ [$y_{1}$…$y_{m}$]

  * •:

IVC(T3) = IVC(P) \+ [$z_{1}$…$z_{m}$]

Here, $[x\ldots y]$ represents an array of clock values and IVC(X) represents
inheritance vector clock of task X. Since, LCA(T2, T3), i.e., P is strictly
higher than LCA(T1,T2) i.e., P1, IVC(P) cannot be equal to IVC(P1) and so [$a$
…$b$] cannot be empty. Also, either [$z_{1}$…$z_{m}$] is empty (i.e., P and T3
are the same) or $z_{1}\neq a$, otherwise P cannot be the LCA of T2 and T3.

While comparing the IVCs of tasks T1, T2, and T3, the first point of
difference is after IVC(P). If [$z_{1}\ldots z_{m}$] is empty, then the IVC of
T3 will end first and so FastRacer will choose T3 and any one of other two
tasks (say T2). Otherwise, we will have $z_{1}$ in IVC(T3) and $a$ in IVC(T1)
and IVC(T2). Since $z_{1}\neq a$, the first point of difference has T3’s clock
value as different. So, again FastRacer will choose T3 and any one of other
two (say T2). In both cases, FastRacer chose T3 and T2 out of the three tasks.
Since IVC(T2,T3) = P is the highest LCA across all tasks in the set {T1,T2,
T3}, so the claim holds.

The tasks T1, T2, and T3 can be chosen randomly, and the above cases allow for
any possible permutation.

∎


# Powered numbers in short intervals II

Tsz Ho Chan

###### Abstract

In this article, we derive a few more facts concerning powered numbers in
short intervals both unconditionally and conditionally on the
$abc$-conjecture. We make use of sieve method, a polynomial identity, and a
recent breakthrough result on density of sets with no $k$-term arithmetic
progression.

##  1 Introduction and Main Result

A number $n$ is squarefull or powerful if its prime factorization
$n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{r}^{a_{r}}$ satisfies $a_{i}\geq 2$ for
all $1\leq i\leq r$. Similarly, $n$ is $k$-full if $a_{i}\geq k$ for all
$1\leq i\leq r$. In contrast, $n$ is squarefree if $a_{i}=1$ for all $i$. For
example, $72=2^{3}\cdot 3^{2}$ is squarefull, $648=2^{3}\cdot 3^{4}$ is
$3$-full, and $30=2\cdot 3\cdot 5$ is squarefree. For any integer $n$, we
define its squarefree part $q(n)$ to be

$q(n):=\prod_{i\text{ with }a_{i}=1}p_{i}=\prod_{p\mid n,\,p^{2}\nmid n}p$

and any integer can be factored uniquely into the product of its squarefree
part and its powerful part (for example, $q(72)=1$, $q(360)=5$, and
$360=5\cdot 2^{3}\cdot 3^{2}=5\cdot 72$.) In [4], the author studied powerful
numbers in short intervals and obtained

$\mathop{\sum_{x<n\leq x+y}}_{n\text{ is powerful}}1\ll\frac{y}{\log(y+2)},$

and

$\mathop{\mathop{\sum_{x<n\leq x+y}}_{n\text{ is
powerful}}}_{p^{+}(n)\leq\sqrt{y}}1\ll y^{11/12}$ (1)

for $1\leq y\leq x$ where $p^{+}(n)$ denotes the largest prime factor of $n$.
Similarly, we let $p^{-}(n)$ denote the smallest prime factor of $n$.

Generalizing and smoothing $k$-full numbers, Mazur [11] proposed the study of
powered numbers in connection to the $abc$-conjecture: For any $\epsilon>0$,
there exists a constant $C_{\epsilon}>0$ such that, for any integers $a,b,c$
with $a+b=c$ and $\text{gcd}(a,b)=1$, the bound

$\max\\{|a|,|b|,|c|\\}\leq C_{\epsilon}\kappa(abc)^{1+\epsilon}$

holds where $\kappa(n):=\prod_{p\mid n}p$ is the squarefree kernel of $n$.

Let $k\geq 1$ be a real number (not necessarily an integer). A positive
integer $n$ is $k$-powered if

$\kappa(n)\leq n^{1/k}\;\;\text{ or }\;\;\frac{\log n}{\log\kappa(n)}\geq k.$

For example, $648$ is a $\frac{\log 648}{\log 6}=3.613147...$-powered number.
Conditional on the $abc$-conjecture, the author [5] proved that, with $k>3/2$,

$\mathop{\sum_{x<n\leq x+y}}_{n\text{ is
$k$-powered}}1\ll_{k}\frac{y}{\exp((c_{k}\log y)^{0.09})}$ (2)

for $1\leq y\leq x$; and, for integers with smooth squarefree part,

$\mathop{\sum_{x<n\leq
x+y}}_{p^{+}(q(n))\leq\log(y+1)\log\log(y+2)}1\ll\frac{y\log\log(y+2)}{\log(y+2)}.$
(3)

In this note, we obtain some new results in connection with (1), (2) and (3).

######  Theorem 1.

Let $k>1$ and $0\leq\delta<1$ be any real numbers. For $1\leq y\leq x$,

$\mathop{\mathop{\sum_{x<n\leq x+y}}_{n\text{ is
$k$-powered}}}_{p^{+}(n/\kappa(n))\leq
y^{1-\delta}}1\;\ll_{k}\;y^{\frac{3k+1}{4k}}+\frac{y^{1-\delta}}{\log(y+1)}.$

The condition $p^{+}(\frac{n}{\kappa(n)})\leq y^{1-\delta}$ means that the
powerful part of $n$ is $y^{1-\delta}$-smooth. Hence, Theorem 1 generalizes
(1) to powered numbers.

######  Theorem 2.

Let $k>1$ be any real number. For $2\leq w\leq y\leq x$ and $\log
w\leq\frac{\log y\log\log\log(y+14)}{4\log\log(y+1)}$,

$\mathop{\mathop{\sum_{x<n\leq x+y}}_{n\text{ is
$k$-powered}}}_{p^{+}(q(n))\leq w}1\;\ll\;\frac{y\log w}{\log y}.$

If one focuses on powered numbers only, then Theorem 2 improves on (3) by
allowing for a much wider range of smoothness on the squarefree part.

######  Theorem 3.

Assume the $abc$-conjecture. For $k>5/4$, there exist positive constants
$C_{k}$ and $c$ such that

$\mathop{\sum_{x<n\leq x+y}}_{n\text{ is
$k$-powered}}1\ll_{k}\frac{y}{\exp(C_{k}(\log\log y)^{c})}.$

for $1\leq y\leq x$.

In comparison with (2), Theorem 3 extends the range of $k$ to $k>5/4$ in
exchange for an inferior upper bound. It would be interesting to see if other
polynomial identities or ideas could be used to extend the range all the way
to $k>1$.

Throughout the paper, $p$, $p_{i}$ and $q_{j}$ stand for prime numbers. The
symbols $f(x)=O(g(x))$, $f(x)\ll g(x)$, and $g(x)\gg f(x)$ are equivalent to
$|f(x)|\leq Cg(x)$ for some constant $C>0$. Also, $f(x)=O_{\lambda}(g(x))$ and
$f(x)\ll_{\lambda}g(x)$ mean that the implicit constant may depend on the
parameter $\lambda$.

##  2 Smooth powerful part: Theorem 1

###### Proof of Theorem 1.

We may assume that $y>1$ for the theorem is clearly true for $y=1$. Set
$z:=y^{(k-1)/k}$. Any $k$-powered number $n$ in $[x,x+y]$ can be factored
uniquely as $n=ab$ with $a$ squarefree and $b$ squarefull. Suppose we have the
following prime factorizations:

$a=\underbrace{p_{1}\cdots p_{i}}_{a_{1}}\underbrace{p_{i+1}\cdots
p_{r}}_{a_{2}}\;\;\text{ with }\;\;p_{1}<p_{2}<\cdots<p_{r},$

and

$b=\underbrace{q_{1}^{e_{1}}\cdots
q_{j}^{e_{j}}}_{b_{1}}\underbrace{q_{j+1}^{e_{j+1}}\cdots
q_{s}^{e_{s}}}_{b_{2}}\;\;\text{ with }\;\;q_{1}<q_{2}<\cdots<q_{s}\leq y$

where $i$ and $j$ are the greatest indices such that $p_{1}\cdots p_{i}\leq
y/z$ and $q_{1}^{e_{1}}\cdots q_{j}^{e_{j}}\leq z$. Hence, $a_{1}\leq
z<a_{1}p_{i+1}$ and $b_{1}\leq z<b_{1}q_{j+1}^{e_{j+1}}$. Note that $i$ or $j$
may be $0$ (giving empty products for $a_{1}$ or $b_{1}$) if $p_{1}>y/z$ or
$q_{1}^{e_{1}}>z$. Also, $i$ and $j$ may equal to $r$ and $s$ respectively.

Case 1: $b_{1}>z^{1/2}$. The number of such $k$-powered numbers is bounded by

$\mathop{\sum\nolimits^{\prime}}_{z^{1/2}<b\leq z}\;\mathop{\sum_{x<n\leq
x+y}}_{b\mid n}1\leq\mathop{\sum\nolimits^{\prime}}_{z^{1/2}<b\leq
z}\frac{y}{b}\ll\frac{y}{z^{1/4}}$ (4)

where $\mathop{\sum\nolimits^{\prime}}$ denotes a sum over squarefull numbers
only.

Now, we claim that if $b_{1}\leq z^{1/2}$, then $b_{2}$ must be greater than
$1$. Suppose the contrary that $n=a_{1}a_{2}b_{1}$. If
$\kappa(a_{1})^{k}\kappa(b_{1})^{k}>a_{1}b_{1}$, then, as $n$ is $k$-powered,
we have

$n=a_{1}a_{2}b_{1}\geq\kappa(a_{1})^{k}\kappa(a_{2})^{k}\kappa(b_{1})^{k}=\kappa(a_{1})^{k}\kappa(b_{1})^{k}a_{2}^{k}>a_{1}b_{1}a_{2}^{k}$

which is a contradiction. If $\kappa(a_{1})^{k}\kappa(b_{1})^{k}\leq
a_{1}b_{1}$ (i.e., $a_{1}b_{1}$ itself is a $k$-powered number). Then,

$n=a_{1}a_{2}b_{1}\geq a_{1}^{k}a_{2}^{k}\kappa(b_{1})^{k}\;\;\text{ or
}\;\;a_{2}^{k-1}\leq\frac{b_{1}}{a_{1}^{k-1}\kappa(b_{1})^{k}}.$

Since $n>x$, this implies

$\Bigl{(}\frac{x}{a_{1}b_{1}}\Bigr{)}^{k-1}<\frac{b_{1}}{a_{1}^{k-1}\kappa(b_{1})^{k}}\;\;\text{
or }\;\;y\leq x<\Bigl{(}\frac{b_{1}}{\kappa(b_{1})}\Bigr{)}^{k/(k-1)}\leq
z^{\frac{k}{2(k-1)}}$

as $\kappa(b_{1})\leq\sqrt{b_{1}}$ for squarefull numbers. This contradicts
our choice $z=y^{(k-1)/k}$.

Case 2: $b_{1}\leq z^{1/2}$ and $p_{-}(b_{2})\leq z^{1/2}$. Then $p_{j+1}\leq
z^{1/2}$ and $p_{j+1}^{e_{j+1}}>z^{1/2}$ which implies
$p_{j+1}^{-e_{j+1}}\leq\min(z^{-1/2},p_{j+1}^{-2})$ as $e_{j+1}\geq 2$. Hence,
the sum

$\sum_{p_{j+1}\leq z^{1/2}}\frac{1}{p_{j+1}^{e_{j+1}}}\leq\sum_{p_{j+1}\leq
z^{1/4}}z^{-1/2}+\sum_{z^{1/4}<p_{j+1}\leq
z^{1/2}}\frac{1}{p_{j+1}^{2}}\ll\frac{1}{z^{1/4}}.$

Therefore, by replacing $p_{j+1}^{a_{j+1}}$ with a generic $p^{a}$, the number
of $k$-powered numbers in this case is bounded by

$\sum_{p\leq z^{1/2}}\;\mathop{\sum_{x<n\leq x+y}}_{p^{a}\mid
n}1\leq\sum_{p\leq
z^{1/2}}\Bigl{(}\frac{y}{p^{a}}+1\Bigr{)}\ll\frac{y}{z^{1/4}}+z^{1/2}.$ (5)

Case 3: $b_{1}\leq z^{1/2}$ and $z^{1/2}<p_{-}(b_{2})\leq y^{1-\delta}$. In
this case, there is some prime $z^{1/2}<p\leq y^{1-\delta}$ such that $p^{2}$
divides $n$. The number of such $k$-powered numbers is bounded by

$\sum_{z^{1/2}<p\leq y^{1-\delta}}\;\mathop{\sum_{x<n\leq x+y}}_{p^{2}\mid
n}1\leq\sum_{z^{1/2}<p\leq
y^{1-\delta}}\Bigl{(}\frac{y}{p^{2}}+1\Bigr{)}\ll\frac{y}{z^{1/4}}+\frac{y^{1-\delta}}{\log
y}.$ (6)

Combining (4), (5) and (6), we have Theorem 1. ∎

##  3 Smooth squarefree part: Theorem 2

Suppose $\exp((\log\log y)^{5/3+\epsilon})<z\leq y$ and set $u:=\frac{\log
y}{\log z}$. Then

$\Psi(y,z)=y\rho(u)\Bigl{(}1+O\Bigl{(}\frac{\log(u+1)}{\log
z}\Bigr{)}\Bigr{)}.$

It is known that

$\rho(u)=\exp\Bigl{(}-u\Bigl{(}\log
u+\log\log(u+2)-1+O\bigl{(}\frac{\log\log(u+2)}{\log(u+2)}\bigr{)}\Bigr{)}\Bigr{)}$

By Rankin’s method, one has the inequality

$\Psi(y,z)\ll ye^{-u/2}\;\;\text{ for }2\leq z\leq y.$

Thus, for $2\leq z\leq N$,

$\mathop{\sum_{N<n\leq 2N}}_{p^{+}(n)\leq
z}\frac{1}{n}\leq\frac{1}{N}(\Psi(2N,z)-\Psi(N,z))\ll\left\\{\begin{array}[]{ll}\exp(-(\log
N)/(2\log z))&\text{ when }2\leq z\leq N,\\\ \exp(-(\frac{\log N}{\log
z}\log\frac{\log N}{\log z}))&\text{ when }(\log N)^{2}<z\leq
N.\end{array}\right.$ (7)

###### Proof of Theorem 2.

This proof is similar to that of Theorem 1. Hence, we will highlight the
necessary modifications at times. First, we may assume that $y>c_{0}$ is
sufficient large as the theorem is clearly true for $y\leq c_{0}$ by picking a
sufficiently large implicit constant. We leave $z$ as a free parameter and
factor $n=ab\in(x,x+y]$, $a$ and $b$ in the same way as the previous section.

First, we deal with the situation where $4\log\log y\leq\log w\leq\frac{\log
y\log\log\log(y+14)}{4\log\log(y+1)}$. We set $z=w$. Then (4) from case 1
yields an upper bound $O(y/z^{1/4})=O(y/\log y)$. When $b_{1}\leq z^{1/2}$,
the same argument in Theorem 1 shows that $b_{2}>1$. Then (5) in case 2 gives
an upper bound $O(y/z^{1/4})=O(y/\log y)$. The main difference is that
$p_{-}(b_{2})\leq y$ may not hold for case 3.

Case 3(a): $b_{1}\leq\sqrt{z}$ and $\sqrt{z}<p_{-}(b_{2})\leq\sqrt{y}$. Then
(6) yields an upper bound $O(y/z^{1/4})=O(y/\log y)$.

Case 3(b): $b_{1}\leq\sqrt{z}$ and $p_{-}(b_{2})>\sqrt{y}$. Recall $a_{1}\leq
y/z<a_{1}p_{i+1}$. Then $a_{1}b_{1}\leq y/\sqrt{z}\leq y$. Since the
squarefree part $a$ is $w$-smooth, we must have $a_{1}>y/zw$ unless
$a=a_{1}\leq y/zw$. If $y/zw<a_{1}\leq y/z$, we divide this interval into
dyadic intervals and apply (7). The number of such $k$-powered numbers is
bounded by

$\sum_{y/zw<a_{1}\leq y/z}\;\sum_{b_{1}\leq z^{1/2}}\frac{y}{a_{1}b_{1}}\ll
y\log w\exp\Bigl{(}-\frac{\log(y/w^{2})}{\log w}\log\log\log y\Bigr{)}\ll
y\exp\Bigl{(}-\frac{\log y\log\log\log y}{2\log w}\Bigr{)}\ll\frac{y}{\log
y}.$

as $\log w\leq\frac{\log y\log\log\log(y+14)}{4\log\log(y+1)}$. It remains to
deal with the case $a\leq y/zw$.

Subcase 1: $a>\sqrt{y/z}$. By using dyadic intervals and (7), the number of
such $k$-powered numbers is at most

$\sum_{\sqrt{y/z}<a\leq y/z^{2}}\;\sum_{b_{1}\leq z^{1/2}}\frac{y}{ab_{1}}\ll
y\log y\exp\Bigl{(}-\frac{\log(y/z)}{2\log z}\log\log\log y\Bigr{)}\ll
y\exp\Bigl{(}-\frac{\log y\log\log\log y}{3\log w}\Bigr{)}\ll\frac{y}{\log
y}.$

Subcase 2: $a\leq\sqrt{y/z}$. Then the number of such $k$-powered numbers is
at most

$\sum_{a\leq\sqrt{y/z}}\;\sum_{b_{1}\leq
z^{1/2}}\mathop{\sum_{\frac{x}{ab_{1}}<b_{2}\leq\frac{x+y}{ab_{1}}}}_{p^{+}(b_{2})>\sqrt{y}}1\ll\sum_{a\leq\sqrt{y/z}}\;\sum_{b_{1}\leq
z^{1/2}}\frac{y}{ab_{1}\log y}\ll\frac{y}{\log y}\prod_{p\leq
w}\Bigl{(}1+\frac{1}{p}\Bigr{)}\ll\frac{y\log w}{\log y}$

by sieve bound (as $\frac{y}{ab_{1}}>\sqrt{y}$) and Merten’s estimate.

Combining all of the above bounds, we have Theorem 2 when $4\log\log y\leq\log
w\leq\frac{\log y\log\log\log(y+14)}{4\log\log(y+1)}$.

Now, we assume that $\log w\leq 4\log\log y$. We set $z=\exp(\sqrt{\log y})$.
Then case 1, case 2 and case 3(a) above yield the bound $O(y/z^{1/4})$. For
case 3(b), when $y/z^{2}<a_{1}\leq y/z$, we have the bound

$\sum_{y/z^{2}<a_{1}\leq y/z}\;\sum_{b_{1}\leq z^{1/2}}\frac{y}{a_{1}b_{1}}\ll
y\log z\exp\Bigl{(}-\frac{\log(y/z^{2})}{2\log z}\Bigr{)}\ll
y\exp\Bigl{(}-\frac{\log y}{3\log z}\Bigr{)}\ll y\exp(-\sqrt{\log y}/4)$

by (7). It remains to deal with the case $a\leq y/z^{2}$. Similar to subcase 1
above, when $a>\sqrt{y/z}$, the number of such $k$-powered numbers is at most

$\sum_{y/z^{2}<a_{1}\leq y/z}\;\sum_{b_{1}\leq z^{1/2}}\frac{y}{a_{1}b_{1}}\ll
y\log y\exp\Bigl{(}-\frac{\log(y/z^{2})}{2\log z}\Bigr{)}\ll
y\exp\Bigl{(}-\frac{\log y}{3\log z}\Bigr{)}\ll y\exp(-\sqrt{\log y}/4)$

by (7). Similar to subcase 2 above, when $a\leq\sqrt{y/z}$, the number of such
$k$-powered numbers is at most

$\sum_{a\leq\sqrt{y/z}}\;\sum_{b_{1}\leq
z^{1/2}}\mathop{\sum_{\frac{x}{ab_{1}}<b_{2}\leq\frac{x+y}{ab_{1}}}}_{p^{+}(b_{2})>\sqrt{y}}1\ll\sum_{a\leq\sqrt{y/z}}\;\sum_{b_{1}\leq
z^{1/2}}\frac{y}{ab_{1}\log y}\ll\frac{y}{\log y}\prod_{p\leq
w}\Bigl{(}1+\frac{1}{p}\Bigr{)}\ll\frac{y\log w}{\log y}.$

Combining all of the above bounds, we have Theorem 2 when $\log w\leq
4\log\log y$. ∎

##  4 Conditional result: Theorem 3

Let $r_{k}(N)$ denote the size of the largest subset of $\\{1,2,\ldots,N\\}$
with no non-trivial $k$-term arithmetic progressions. Here, non-trivial means
that the $k$-terms are not the same. Now, let us recall Gowers’ quantitative
breakthrough result on Szemerédi’s theorem [6]:

$r_{k}(N)\leq N(\log\log N)^{-c_{k}}\;\;\text{ with }\;\;c_{k}=2^{-2^{k+9}}.$

For $k=3$, there have been recent exciting activities [1], [9], [2], [3] in
getting down to

$r_{3}(N)\ll N\exp(-c(\log N)^{1/9}).$

For $k=4$, Green and Tao [7], [8] proved

$r_{4}(N)\ll N(\log N)^{-c}$

for some $c>0$. For $k\geq 5$, Leng, Sah and Sawhney [10] very recently
established the existence of some constant $c_{k}>0$ such that

$r_{k}(N)\ll N\exp(-(\log\log N)^{c_{k}}).$ (8)

###### Proof of Theorem 3.

When $k>5/4$, we set $\epsilon:=(k-5/4)/2$. Firstly, we restrict to $y\leq
x^{\frac{12k-15}{k(12k+10)}}$. We claim that there is no non-trivial $7$-term
arithmetic progression of $k$-powered numbers in the interval $(x,x+y]$ under
the $abc$-conjecture. Suppose the contrary that

$n-2d,n-d,n,n+d,n+2d,n+3d,n+4d$

are seven $k$-powered numbers in $(x,x+y]$ with some $d\geq 1$. We apply the
polynomial identity

$(n+2d)^{3}(n-2d)+16d^{3}(n+d)=n^{3}(n+4d).$

Let $D:=\gcd((n+2d)^{3}(n-2d),16d^{3}(n+d))$. Then we can apply the
$abc$-conjecture to

$\frac{(n+2d)^{3}(n-2d)}{D}+\frac{16d^{3}(n+d)}{D}=\frac{n^{3}(n+4d)}{D}$

and get

$\displaystyle\frac{x^{4}}{D}$
$\displaystyle\ll_{\epsilon}\kappa\Bigl{(}\frac{(n+2d)^{3}(n-2d)}{D}\Bigr{)}^{1+\epsilon}\kappa\Bigl{(}\frac{16d^{3}(n+d)}{D}\Bigr{)}^{1+\epsilon}\kappa\Bigl{(}\frac{n^{3}(n+4d)}{D}\Bigr{)}^{1+\epsilon}$
$\displaystyle\leq\bigl{(}\kappa(n-2d)\kappa(n)\kappa(n+d)\kappa(n+2d)\kappa(n+4d)\bigr{)}^{1+\epsilon}\Bigl{(}\frac{16d^{3}}{D}\Bigr{)}^{1+\epsilon}\ll
x^{\frac{5(1+\epsilon)}{k}}\cdot\frac{y^{3(1+\epsilon)}}{D^{1+\epsilon}}.$

From the definition of $\epsilon$, this implies
$x^{4}\ll_{k}x^{\frac{5}{2}+\frac{15}{8k}}y^{\frac{9}{8}+\frac{3k}{2}}$ or
$x^{\frac{3}{2}-\frac{15}{8k}}\ll_{k}y^{\frac{9}{8}+\frac{3k}{2}}$ which
contradicts our assumption that $y\leq x^{\frac{12k-15}{k(12k+10)}}$. Since
arithmetic progressions are invariant under translation, we may shift all the
$k$-powered numbers in $(x,x+y]$ to numbers in $(0,y]$ and there is no
$7$-term arithmetic progression among them. By (8), the number of such
$k$-powered numbers is bounded by $O(\frac{y}{\exp((\log\log y)^{c_{7}})})$
for some $c_{7}>0$.

When $y>x^{\frac{12k-15}{k(12k+10)}}$, we can cover the interval $(x,x+y]$
with a disjoint union of at most $2y/x^{\frac{12k-15}{k(12k+10)}}$
subintervals each with length $x^{\frac{12k-15}{k(12k+10)}}$. Over each
subinterval, we have at most
$O(\frac{x^{\frac{12k-15}{k(12k+10)}}}{\exp(C_{k}(\log\log x)^{c_{7}})})$
$k$-powered numbers for some $C_{k}>0$. Adding these together, we have the
upper bound $O(\frac{y}{\exp(C_{k}(\log\log x)^{c_{7}})})$. ∎

## References

  * [1] T.F. Bloom and O. Sisask, Breaking the logarithmic barrier in Roth’s theorem on arithmetic progressions, preprint, arXiv:2007.03528 (2020).
  * [2] T.F. Bloom and O. Sisask, An improvement to the Kelley-Meka bounds on three-term arithmetic progressions, preprint, arXiv:2309.02353 (2023).
  * [3] T.F. Bloom and O. Sisask, The Kelley-Meka bounds for sets free of three-term arithmetic progressions, Essential Number Theory 2 (2023), no. 1, 15-44.
  * [4] T.H. Chan, A note on powerful numbers in short intervals, Bull. Aust. Math. Soc. 108 (2023), 99-106.
  * [5] T.H. Chan, Powered numbers in short intervals, Integers: Proceedings of the Integers Conference 2023, 24A (2024), A6, 7 pp.
  * [6] T. Gowers, A new proof of Szermerédi’s theorem, Geom. Funct. Anal. 11 (2001), 465-588.
  * [7] B. Green and T. Tao, New bounds for Szemerédi’s theorem II. A new bound for $r_{4}(N)$, Analytic number theory, Cambridge Univ. Press, Cambridge, 2009, pp. 180-204.
  * [8] B. Green and T. Tao, New bounds for Szemerédi’s theorem III: a polylogarithmic bound for $r_{4}(N)$, Mathematika 63 (2017), 944-1040.
  * [9] Z. Kelley and R. Meka, Strong bounds for $3$-progressions, 2023 IEEE 64-th Annual Symposium on Foundations of Computer Science (FOCS), 2023, pp. 933-973.
  * [10] J. Leng, A. Sah and M. Sawhney, Improved bounds for Szemerédi’s theorem, preprint, arXiv:2402.17995.
  * [11] B. Mazur. Questions about powers of numbers. Notices Amer. Math. Soc. 47 (2000), no. 2, 195-202.

Department of Mathematics
Kennesaw State University
Marietta, GA 30060
<EMAIL_ADDRESS>