IEEEexample:BSTcontrol

#  _SmartPQ_ : An Adaptive Concurrent Priority Queue
for NUMA Architectures

*Christina Giannoula$\dagger$ *Foteini Strati$\ddagger$$\dagger$ Dimitrios Siakavaras$\dagger$ Georgios Goumas$\dagger$ Nectarios Koziris$\dagger$ _$\dagger$ National Technical University of Athens $\ddagger$ETH Zürich _

###### Abstract

Concurrent priority queues are widely used in important workloads, such as
graph applications and discrete event simulations. However,  designing
scalable concurrent priority queues for NUMA architectures is challenging.
Even though several _NUMA-oblivious_ implementations can scale up to a high
number of threads, exploiting the potential parallelism of _insert_ operation,
_NUMA-oblivious_ implementations scale poorly in _deleteMin_ -dominated
workloads. This is because all threads compete for accessing the _same_ memory
locations, i.e., the highest-priority element of the queue, thus incurring
excessive cache coherence traffic and non-uniform memory accesses _between
NUMA_ nodes. In such scenarios, _NUMA-aware_ implementations are typically
used to improve system performance on a NUMA system.††* Christina Giannoula
and Foteini Strati are co-primary authors.

In this work, we propose an adaptive priority queue, called _SmartPQ_.
_SmartPQ_ tunes itself by switching between a _NUMA-oblivious_ and a _NUMA-
aware_ algorithmic mode to achieve high performance under all various
contention scenarios. _SmartPQ_ has two key components. First, it is built on
top of NUMA Node Delegation (_Nuddle_), a generic low-overhead technique to
construct efficient _NUMA-aware_ data structures using any arbitrary
concurrent _NUMA-oblivious_ implementation as its backbone. Second, _SmartPQ_
integrates a lightweight decision making mechanism to decide when to switch
between _NUMA-oblivious_ and _NUMA-aware_ algorithmic modes. Our evaluation
shows that, in NUMA systems, _SmartPQ_ performs best in all various contention
scenarios with 87.9% success rate, and dynamically adapts between _NUMA-aware_
and _NUMA-oblivious_ algorithmic mode, with negligible performance overheads.
_SmartPQ_ improves performance by 1.87$\times$ on average over SprayList, the
state-of-the-art _NUMA-oblivious_ priority queue.

##  1 Introduction

Concurrent data structures are widely used in the software stack, i.e.,
kernel, libraries and applications. Prior works [65, 10, 14, 9] discuss the
need for efficient and scalable concurrent data structures for commodity Non-
Uniform Memory Access (NUMA) architectures. Pointer chasing data structures
such as linked lists, skip lists and search trees have inherently low
contention, since concurrent threads search for different elements during
their operations. Recent works [10, 16, 70] have shown that lock-free
algorithms [29, 52, 24, 22, 36, 55] of such data structures can scale to
hundreds of cores. On the other hand, data structures such as queues and
stacks typically incur high contention, when accessed by many threads. In
these data structures, concurrent threads compete for the _same_ memory
elements (locations), incurring excessive traffic and non-uniform memory
accesses between nodes of a NUMA system.

In this work, we focus on priority queues, which are widely used in a variety
of applications, including task scheduling in real-time and computing systems
[79], discrete event simulations [75, 49] and graph applications [39, 43, 76],
e.g., Single Source Shortest Path [12] and Minimum Spanning Tree [60].
Similarly to skip-lists and search trees, priority queues have two main
operations: _insert_ and _deleteMin_. The _insert_ operation, concurrent
priority queues typically exhibits high levels of parallelism and low-
contention, since threads may work on different parts of the data structure.
Therefore, concurrent _NUMA-oblivious_ implementations [47, 45, 67, 74, 77,
64, 6, 80] can scale up to a high number of threads. In contrast, in
_deleteMin_ operation, _all_ threads compete for deleting the highest-priority
element of the queue, thus competing for the _same_ memory locations
(similarly to queues and stacks), and creating a contention spot. In
_deleteMin_ -dominated workloads, concurrent priority queues typically incur
high-contention and low parallelism. To achieve higher parallelism, _relaxed_
priority queues have been proposed in the literature [2, 30], in which
_deleteMin_ operation returns an element among the _first few_ (high-priority)
elements of the priority queue. However, such _NUMA-oblivious_ implementations
are still inefficient in NUMA architectures, as we demonstrate in Section 4.
Therefore, to improve performance in NUMA systems, _NUMA-aware_
implementations have been proposed [10, 65].

Figure 1: Throughput achieved by a _NUMA-oblivious_ [2, 34] and a _NUMA-aware_
[65] priority queue, both initialized with 1024 keys. We use 64 threads that
perform a mix of _insert_ and _deleteMin_ operations in parallel, and the key
range is set to 2048 keys. We use _all_ NUMA nodes of a 4-node NUMA system,
the characteristics of which are presented in Section 4.

We examine _NUMA-aware_ and _NUMA-oblivious_ concurrent priority queues with a
wide variety of contention scenarios in NUMA architectures, and find that the
performance of a priority queue implementation is becoming increasingly
dependent on both the contention levels of the workload and the underlying
computing platform. This is illustrated in Figure 1, which shows the
throughput achieved by a _NUMA-oblivious_ and a _NUMA-aware_ priority queue
using a 4-node NUMA system. Even though in a _insert_ -dominated scenario,
e.g., when having 100% _insert_ operations, the _NUMA-oblivious_
implementation achieves significant performance gains over the _NUMA-aware_
one, when contention increases, i.e., the percentage of _deleteMin_ operations
increases, the _NUMA-oblivious_ implementation incurs non-negligible
performance slowdowns over the _NUMA-aware_ priority queue. We conclude that
none of the priority queues performs best across _all_ contention workloads.

Our goal in this work is to design a concurrent priority queue that (i)
achieves _the highest performance under all various contention scenarios, and
(ii) performs best_ even when the contention of the workload _varies_ over
time.

To this end, our contribution is twofold. First, we introduce NUMA Node
Delegation (_Nuddle_), a generic technique to obtain _NUMA-aware_ data
structures, by effectively transforming _any_ concurrent _NUMA-oblivious_ data
structure into the corresponding _NUMA-aware_ implementation. In other words,
_Nuddle_ is a framework to wrap any _concurrent_ _NUMA-oblivious_ data
structure and transform it into an efficient _NUMA-aware_ one. _Nuddle_
extends _ffwd_ [65] by enabling multiple server threads, instead of only one,
to execute operations in parallel on behalf of client threads. In contrast to
_ffwd_ , which aims to provide single threaded data structure performance,
_Nuddle_ targets data structures which are able to scale up to a number of
threads such as priority queues.

Second, we propose _SmartPQ_ , an adaptive concurrent priority queue that
achieves the _highest_ performance under _all_ contention workloads and
_dynamically_ adapts itself over time between a _NUMA-oblivious_ and a _NUMA-
aware_ algorithmic mode. _SmartPQ_ integrates (i) _Nuddle_ to _efficiently_
switch between the two algorithmic modes with _very low_ overhead, and (ii) a
simple decision tree _classifier_ , which predicts the best-performing
algorithmic mode given the expected contention levels of a workload.

Figure 2 presents an overview of _SmartPQ_ , where we use the term base
algorithm to denote _any_ arbitrary concurrent _NUMA-oblivious_ data
structure. _SmartPQ_ relies on three key ideas. First, client threads can
execute operations using either _Nuddle_ (_NUMA-aware_ mode) or its underlying
_NUMA-oblivious_ base algorithm (_NUMA-oblivious_ mode). Second, _SmartPQ_
incorporates a decision making mechanism to decide upon transitions between
the two modes. Third, _SmartPQ_ exploits the fact that the actual underlying
implementation of _Nuddle_ is a _concurrent_ _NUMA-oblivious_ data structure.
Client threads in both algorithmic modes access the data structure with the
same concurrency strategy, i.e., with no actual change in the way data is
accessed, and synchronization is implemented. Therefore, _SmartPQ_ switches
from one mode to another with _no_ synchronization points between transitions.

We evaluate a wide range of contention scenarios and compare _Nuddle_ and
_SmartPQ_ with state-of-the-art _NUMA-oblivious_ [2, 47] and _NUMA-aware_ [65]
concurrent priority queues. We also evaluate _SmartPQ_ using synthetic
benchmarks that _dynamically_ vary their contention workload over time. Our
evaluation shows that _SmartPQ_ adapts between its two algorithmic modes with
negligible performance overheads, and achieves the highest performance in
_all_ contention workloads with 87.9% success rate.

Figure 2: High-level overview of _SmartPQ_. _SmartPQ_ dynamically adapts its
algorithm to the contention levels of the workload based on the prediction of
a simple classifier.

This paper makes the following contributions:

  * –

We propose _Nuddle_ , a generic technique to obtain _NUMA-aware_ concurrent
data structures.

  * –

We design a simple classifier to predict the best-performing implementation
among _NUMA-oblivious_ and _NUMA-aware_ priority queues given the contention
levels of a workload.

  * –

We propose _SmartPQ_ , an adaptive concurrent priority queue that achieves the
highest performance, even when contention varies over time.

  * –

We evaluate _Nuddle_ and _SmartPQ_ with a wide variety of contention
scenarios, and demonstrate that _SmartPQ_ performs best over prior state-of-
the-art concurrent priority queues.

##  2 NUMA Node Delegation (_Nuddle_)

###  2.1 Overview

NUMA Node Delegation (_Nuddle_) is a generic technique to obtain _NUMA-aware_
data structures by automatically transforming _any_ concurrent _NUMA-
oblivious_ data structure into an efficient _NUMA-aware_ implementation.
_Nuddle_ extends _ffwd_ [65], a client-server software mechanism which is
based on the delegation technique [8, 38, 48, 57, 73].

Figure 3 left shows the high-level overview of _ffwd_ , which has three key
design characteristics. First, _all_ operations performed by multiple client
threads are _delegated_ to one _single_ dedicated thread, called server
thread. Server thread performs operations in the data structure on behalf of
its client threads. This way, the data structure remains in the memory
hierarchy of a _single_ NUMA node, avoiding non-uniform memory accesses to
remote data. Second, _ffwd_ eliminates the need for synchronization, since the
shared data structure is no longer accessed by multiple threads: only a single
server thread directly modifies the data structure, and therefore, _ffwd_ uses
a _serial asynchronized_ implementation of the underlying data structure.
Third, _ffwd_ provides an efficient communication protocol between the server
thread and client threads that minimizes cache coherence overheads.
Specifically, _ffwd_ reserves dedicated cache lines to exchange request and
response messages between the client threads and sever thread. Multiple client
threads are grouped together to minimize the response messages from the server
thread: one response cache line is shared among multiple client threads
belonging at the same client thread group. For more details, we refer the
reader to the original paper [65].

Figure 3: High-level design of _ffwd_ [65] and _Nuddle_. _Nuddle_ locates
_all_ server threads at the _same_ NUMA node to design a _NUMA-aware_ scheme,
and associates each of them to multiple client thread groups. _Nuddle_ uses
the communication protocol proposed in _ffwd_ [65].

Figure 3 right presents the high-level overview of _Nuddle_ , which is based
on three key ideas. First, _Nuddle_ deploys _multiple_ servers to perform
operations on behalf of multiple client threads. Specifically, client threads
are grouped in client thread groups, and each sever thread serves multiple
client thread groups. This way, multiple server threads _concurrently_ perform
operations on the data structure, achieving high levels of parallelism up to a
number of server threads. Second, _Nuddle_ locates all server threads to the
_same_ NUMA node to keep the data structure in the memory hierarchy of one
_single_ NUMA node, and propose a _NUMA-aware_ approach. Client threads can be
located at any NUMA node. Third, since multiple servers can _concurrently_
update the _shared_ data structure, _Nuddle_ uses the _concurrent_ _NUMA-
oblivious_ implementation (i.e., which includes synchronization primitives
when accessing the shared data) of the underlying data structure to ensure
correctness. Third, _Nuddle_ employs the same client-server communication
protocol with _ffwd_ to carefully manage memory accesses and minimize cache
coherence traffic and latency.

_ffwd_ targets inherently serial data structures, whose concurrent performance
cannot be better than that of _single_ threaded performance. In contrast,
_Nuddle_ targets data structures that can scale up to a number of concurrent
threads. Priority queue is a typical example of such a data structure. In
_insert_ operation, priority queue can scale up to multiple threads which can
_concurrently_ update the shared data. In contrast, _deleteMin_ operation is
inherently serial: at each time only _one_ thread can update the shared data,
since _all_ threads compete for the highest-priority element of the queue.
However, as we mentioned, in relaxed priority queues (e.g., SprayList [2]),
even _deleteMin_ operation can be parallelized to some extent.

###  2.2 Implementation Details

Figures 4, 5 and 6 present the code of a priority queue implementation using
_Nuddle_. We denote with red color the core operations of the _base algorithm_
, which is used as the underlying concurrent _NUMA-oblivious_ implementation
of _Nuddle_. Note that even though in this work we focus on priority queues,
_Nuddle_ is a _generic_ framework for any type of concurrent data structure.

Helper Structures. _Nuddle_ includes three _helper_ structures (Figure 4),
which are needed for client-server communication. First, the main structure of
_Nuddle_ , called struct nuddle_pq, wraps the _base algorithm_ (nm_oblv_set),
and includes a few additional fields, which are used to associate client
thread groups to server threads in the initialization step. Second, each
client thread has its own struct client structure with a dedicated request and
a dedicated response cache line. The request cache line is exclusively written
by the client thread and read by the associated server thread, while the
response cache line is exclusively written by the server thread and read by
all client threads that belong in the same client thread group. Third, each
server thread has its own struct server structure that includes an array of
requests (my_clients), each of them is shared with a client thread, and an
array of responses (my_responses), each of them is shared with all client
threads of the _same_ client thread group.

⬇

1#define cache_line_size 128

2typedef char cache_line[cache_line_size];

3

4struct nuddle_pq {

5 nm_oblv_set *base_pq;

6 int servers, groups, clnt_per_group;

7 int server_cnt, clients_cnt, group_cnt;

8 cache_line *requests[groups][clnt_per_group];

9 cache_line *responses[groups];

10 lock *global_lock;

11};

12

13struct client {

14 cache_line *request, *response;

15 int clnt_pos;

16};

17

18struct server {

19 nm_oblv_set *base_pq;

20 cache_line *my_clients[], *my_responses[];

21 int my_groups, clnt_per_group;

22};

Figure 4: Helper structures of _Nuddle_.

Initialization Step. Figure 5 describes the initialization functions of
_Nuddle_. initPQ() initializes (i) the underlying data structure using the
corresponding function of the _base algorithm_ (line 25), and (ii) the
additional fields of struct nuddle_pq. For this function, programmers need to
specify the number of server threads and the maximum number of client threads
to properly allocate cache lines needed for communication among them.
Programmers also specify the size of the client thread group (line 27), which
is typically 7 or 15, if the cache line is 64 or 128 bytes, respectively. As
explained in _ffwd_ [65], assuming 8-byte return values, a dedicated 64-byte
(or 128-byte) response cache line can be shared between up to 7 (or 15) client
threads, because it also has to include one additional toggle bit for each
client thread. After initializing struct nuddle_pq, each running thread calls
either initClient() or initServer() depending on its role. Each thread
initializes its own helper structure (struct client or struct server) with
request and response cache lines of the corresponding shared arrays of struct
nuddle_pq. Server threads undertake client thread groups with a round robin
fashion, such that the load associated with client threads is balanced among
them. In function initServer(), it is the programmer’s responsibility to
properly pin software server threads to hardware contexts (line 56), such that
server threads are located in the _same_ NUMA node, and the programmer fully
benefits from the _Nuddle_ technique. Moreover, given that client threads of
the _same_ client thread group share the same response cache line, the
programmer could pin client threads of the _same_ client thread group to
hardware contexts of the _same_ NUMA node to minimize cache coherence
overheads. Finally, since the request and response arrays of struct nuddle_pq
are _shared_ between all threads, a global lock is used when updating them to
ensure mutual exclusion.

⬇

1struct nuddle_pq *initPQ(int servers, int max_clients) {

2 struct nuddle_pq *pq = allocate_nuddle_pq();

3 __base_init(pq->base_pq);

4 pq->servers = servers;

5 pq->clnt_per_group = client_group(cache_line_size);

6 pq->groups = (max_clients +

7 pq->clnt_per_group-1) / pq->clnt_per_group;

8 pq->server_cnt = 0;

9 pq->client_cnt = 0;

10 pq->group_cnt = 0;

11 pq->requests = malloc(groups * clnt_per_group);

12 pq->responses = malloc(groups);

13 init_lock(pq->global_lock);

14 return pq;

15}

16

17struct client *initClient(struct nuddle_pq *pq) {

18 struct client *cl = allocate_client();

19 acquire_lock(pq->global_lock);

20 cl->request = &(pq->requests[group_cnt][clients_cnt]);

21 cl->response = &(pq->responses[group_cnt]);

22 cl->pos = pq->client_cnt;

23 pq->client_cnt++;

24 if (pq->client_cnt % pq->clnt_per_group == 0) {

25 pq->clients_cnt = 0;

26 pq->group_cnt++;

27 }

28 release_lock(pq->global_lock);

29 return cl;

30}

31

32struct server *initServer(struct nuddle_pq *pq, int core)

33{

34 set_affinity(core);

35 struct server *srv = allocate_server();

36 srv->base_pq = pq->base_pq;

37 srv->my_groups = 0;

38 srv->clnt_per_group = pq->clnt_per_group;

39 acquire_lock(pq->global_lock);

40 int j = 0;

41 for(i = 0; i < pq->groups; i++)

42 if(i % pq->servers == pq->server_cnt) {

43 srv->my_clients[j] = pq->requests[i][0..gr_clnt];

44 srv->my_responses[j++] = pq->responses[i];

45 srv->my_groups++;

46 }

47 pq->server_cnt++;

48 release_lock(pq->global_lock);

49 return srv;

50}

Figure 5: Initialization functions of _Nuddle_.

Main API. Figure 6 shows the core functions of _Nuddle_ , where we omit the
corresponding functions for _deleteMin_ operation, since they are very similar
to that of _insert_ operation. Both _insert_ and _deleteMin_ operations of
_Nuddle_ have similar API with the classic API of prior state-of-the-art
priority queue implementations [2, 47, 67, 45]. However, we separate the
corresponding functions for client threads and server threads. A client thread
writes its request to a dedicated request cache line (line 75) and then waits
for the server thread’s response. In contrast, a server thread directly
executes operations in the data structure using the core functions of the
_base algorithm_ (line 82). Moreover, a server thread can serve client threads
using the serve_requests() function. A server thread iterates over its own
client thread groups and executes the requested operations in the data
structure. The server thread buffers individual return values for clients to a
local cache line (resp in lines 92 and 94) until it finishes processing all
requests for the current client thread group. Then, it writes all responses to
the _shared_ response cache line of that client thread group (line 96), and
proceeds to its next client thread group.

⬇

22int insert_client(struct client *cl, int key, int64_t value)

23{

24 cl->request = write_req("insert", key, value);

25 while (cl->response[cl->pos] == 0) ;

26 return cl->response[cl->pos];

27}

28

29int insert_server(struct server *srv, int key, int64_t value)

30{

31 return __base_insrt(srv->base_pq, key, value);

32}

33

34void serve_requests(struct server *srv) {

35 for(i = 0; i < srv->mygroups; i++) {

36 cache_line resp;

37 for(j = 0; j < srv->clnt_per_group; j++) {

38 key = srv->my_clients[i][j].key;

39 value = srv->my_clients[i][j].value;

40 if (srv->my_clients[i][j].op == "insert")

41 resp[j] = __base_insrt(srv->base_pq, key, value);

42 else if (srv->my_clients[i][j].op == "deleteMin")

43 resp[j] = __base_delMin(srv->base_pq);

44 }

45 srv->my_responses[i] = resp;

46 }

47}

Figure 6: Functions used by server threads and client threads to perform
operations using _Nuddle_.

(a)

(b)

Figure 7: Throughput achieved by _Nuddle_ (using 8 server threads) and its
underlying _NUMA-oblivious_ _base algorithm_ , i.e., _alistarh_herlihy_ [2,
34], when we vary (a) the number of threads that perform operations in the
shared data structure, and (b) the key range of the workload.

##  3 _SmartPQ_

We propose _SmartPQ_ , an adaptive concurrent priority queue which tunes
itself by _dynamically_ switching between _NUMA-oblivious_ and _NUMA-aware_
algorithmic modes, in order to perform best in _all_ contention workloads and
at _any_ point in time, even when contention varies over time.

Designing an adaptive priority queue involves addressing two major challenges:
(i) how to switch from one algorithmic mode to the other with _low overhead_ ,
and (ii) _when_ to switch from one algorithmic mode to the other.

To address the first challenge, we exploit the fact that the actual underlying
implementation of _Nuddle_ is a _concurrent_ _NUMA-oblivious_ implementation.
We select _Nuddle_ , as the _NUMA-aware_ algorithmic mode of _SmartPQ_ , and
its underlying _base algorithm_ , as the _NUMA-oblivious_ algorithmic mode of
_SmartPQ_. Threads can perform operations in the data structure using either
_Nuddle_ or its underlying _base algorithm_ , with _no actual change_ in the
way data is accessed. As a result, _SmartPQ_ can switch between the two
algorithmic modes _without_ needing a synchronization point between
transitions, and without violating correctness.

To address the second challenge, we design a simple decision tree classifier
(Section 3.1.2), and train it to select the best-performing algorithmic mode
between _Nuddle_ , as the _NUMA-aware_ algorithmic mode of _SmartPQ_ , and its
underlying _base algorithm_ , as the _NUMA-oblivious_ mode of _SmartPQ_.
Finally, we add a _lightweight_ decision making mechanism in _SmartPQ_
(Section 3.2) to dynamically tune itself over time between the two algorithmic
modes. We describe more details in next sections.

###  3.1 Selecting the Algorithmic Mode

####  3.1.1 The Need for a Machine Learning Approach

Selecting the best-performing algorithmic mode can be solved in various ways.
For instance, one could take an empirical exhaustive approach: measure the
throughput achieved by the two algorithmic modes for all various contention
scenarios on the target NUMA system, and then use the algorithmic mode that
achieves the highest throughput on future runs of the same contention workload
on the target NUMA system. Even though this is the most accurate method, it
(i) incurs _substantial_ overhead and effort to sweep over _all_ various
contention workloads, and (ii) would need a large amount of memory to store
the best-performing algorithmic mode for all various scenarios. Furthermore,
it is not trivial to construct a statistical model to predict the best-
performing algorithmic mode, since the performance of an algorithm is also
affected by the characteristics of underlying computing platform. Figure 7
summarizes these observations by comparing _Nuddle_ with its underlying _base
algorithm_ in a 4-node NUMA system. For the _base algorithm_ , we use
_alistarh_herlihy_ priority queue [2, 34], since this is the _NUMA-oblivious_
implementation that achieves the highest performance, according to our
evaluation (Section 4).

Figure 7a demonstrates that the best-performing algorithmic mode depends on
multiple parameters, such as the number of threads that perform operations in
the shared data structure. We find that the algorithmic also depends on the
size of the data structure, and the operation workload, i.e., the percentage
of _insert_ /_deleteMin_ operations. Specifically, when the number of threads
increases, we may expect that the performance of the _NUMA-oblivious_
_alistarh_herlihy_ degrades due to higher contention. In contrast, with 80%
_insert_ operations when increasing the number of threads to 29,
_alistarh_herlihy_ outperforms _Nuddle_. This is because the size of the
priority queue and the range of keys used in the workload are relatively
large, while the percentage of _deleteMin_ operations is low. In this
scenario, threads may not compete for the same elements, working on different
parts of the data structure, and thus, the _NUMA-oblivious_ _alistarh_herlihy_
achieves higher throughput compared to the _NUMA-aware_ _Nuddle_.

Figure 7b demonstrates that the best-performing algorithmic mode cannot be
straightforwardly predicted, and also depends on the characteristics of the
workload and of the underlying hardware. In _insert_ -dominated workloads, as
the key range increases, threads may update different parts of the shared data
structure. We might, thus, expect that after a certain point of increasing the
key range, the _NUMA-oblivious_ _alistarh_herlihy_ will always outperform
_Nuddle_ , since the contention decreases. However, we note that, even though
the performance of _Nuddle_ remains constant, as expected, the performance of
_alistarh_herlihy_ highly varies as the key range increases due to the
hyperthreading effect. When using more than 32 threads, hyperthreading is
enabled in our NUMA system (Section 4). The hyperthreading pair of threads
shares the L1 and L2 caches, and thus, these threads may either thrash or
benefit from each other depending on the characteristics of L1 and L2 caches
(e.g., size, eviction policy), and the elements accessed in each operation.

Considering the aforementioned non-straightforward behavior, we resort to a
machine learning approach as the basis of our prediction mechanism.

####  3.1.2 Decision Tree Classifier

We formulate the selection of the algorithmic mode as a classification
problem, and leverage supervised learning techniques to train a simple
classifier to predict the best-performing algorithmic mode for each contention
workload. For our classifier, we select decision trees, since they are
commonly used in classification models for multithreaded workloads [21, 19,
59, 51, 17, 72, 69, 3], and incur low training and inference overhead.
Moreover, they are easy to interpret and thus, be incorporated to our proposed
priority queue (Section 3.2). We generate the decision tree classifier using
the scikit-learn machine learning toolkit [56].

1) Class Definition: We define the following classes: (a) the _NUMA-oblivious_
class that stands for the _NUMA-oblivious_ algorithmic mode, (b) the _NUMA-
aware_ class that stands for the _NUMA-aware_ algorithmic mode, and (c) the
neutral class that stands for a tie, meaning that either a _NUMA-aware_ or a
_NUMA-oblivious_ implementation can be selected, since they achieve similar
performance. We include a neutral class for two reasons: (i) when using _only
one_ socket of a NUMA system, _NUMA-aware_ implementations deliver similar
throughput with _NUMA-oblivious_ implementations, and (ii) in an adaptive data
structure, which _dynamically_ switches between the two algorithmic modes, we
want to configure a transition from one algorithmic mode to another to occur
when the difference in their throughput is relatively high, i.e., greater than
a certain threshold. Otherwise, the adaptive data structure might continuously
oscillate between the two modes, without delivering significant performance
improvements or even causing performance degradation.

2) Extracted Features: Table 1 explains the four features of the contention
workload which are used in our classifier targeting priority queues. We assume
that the contention workload is known a priori, and thus, we can easily
extract the features needed for classification. Section 5 discusses how to on-
the-fly extract these features.

Feature | Definition
---|---
#Threads | The number of active threads
that perform operations in the data structure
Size | The current size of the priority queue
Key_range | The range of keys used in the workload
% _insert_ /_deleteMin_ | The percentage of _insert_ /_deleteMin_ operations

Table 1: The features of the contention workload which are used for
classification.

3) Generation of Training Data: To train our classifier, we develop
microbenchmarks, in which threads repeatedly execute random operations on the
priority queue for 5 seconds. We select _Nuddle_ , as the _NUMA-aware_
implementation, and _alistarh_herlihy_ , as its underlying _NUMA-oblivious_
implementation, since this is the best-performing _NUMA-oblivious_ priority
queue (Section 4). We use a variety of values for the features needed for
classification (Table 1). Our training data set consists of 5525 different
contention workloads. Finally, we pin software threads to hardware contexts of
the evaluated NUMA system in a round-robin fashion, and thus, the classifier
is trained with this thread placement. We leave the exploration of the thread
placement policy for future work.

4) Labeling of Training Data: Regarding the labeling of our training data set,
we set the threshold for tie between the two algorithmic modes to an empirical
value of 1.5 Million operations per second. When the difference in throughput
between the two algorithmic modes is less than this threshold, the neutral
class is selected as label. Otherwise, we select the class that corresponds to
the algorithmic mode that achieves the highest throughput.

The final decision tree classifier has only 180 nodes, half of which are
leaves. It has a very low depth of 8, that is the length of the longest path
in the tree, and thus, a _very low_ traversal cost (2-4 ms in our evaluated
NUMA system).

###  3.2 Implementation Details

⬇

50struct smartpq {

51 nm_oblv_set *base_pq;

52 int servers, groups, clnt_per_group;

53 int server_cnt, clients_cnt, group_cnt;

54 cache_line *requests[groups][clnt_per_group];

55 cache_line *responses[groups];

56 lock *global_lock;

57 int *algo; // 1: NUMA-oblivious (default),
2: NUMA-aware

58};

59

60struct client {

61 nm_oblv_set *base_pq;

62 int *algo;

63 cache_line *request, *response;

64 int clnt_pos;

65};

66

67struct client *initClient(struct smartpq *pq) {

68 ... lines 40-49 of Fig. 5 ...

69 cl->base_pq = pq->base_pq;

70 cl->algo = &(pq->algo);

71 release_lock(pq->global_lock);

72 return cl;

73}

74

75int insert_client(struct client *cl, int key, float value) {

76 if(*(cl->algo) == 1) {

77 return __base_insert(cl->base_pq,key,value);

78 } else { // *(cl->algo) == 2

79 ... lines 75-77 of Fig. 6 ...

80 }

81}

82

83void serve_requests(struct server *srv) {

84 if(*(srv->algo) == 2){

85 for(i = 0; i < srv->mygroups; i++) {

86 cache_line resp;

87 for(j = 0; j < srv->clnt_per_group; j++) {

88 key = srv->my_clients[i][j].key;

89 value = srv->my_clients[i][j].value;

90 if (srv->my_clients[i][j].op == "insert")

91 resp[j] = __base_insrt(srv->base_pq, key, value);

92 else if (srv->my_clients[i][j].op == "deleteMin")

93 resp[j] = __base_delMin(srv->base_pq);

94 }

95 srv->my_responses[i] = resp;

96 }

97 } else

98 return;

99}

100

101void decisionTree(struct server /
struct client *str, int nthreads,
int size, int key_range,
double insert\_deleteMin) {

102 int algo = 0;

103 ... code for decision tree classifier ...

104 if (algo != 0) // 0: neutral

105 *(str->algo) = algo;

106}

Figure 8: The modified code of _Nuddle_ adding the decision making mechanism
to implement _SmartPQ_.

Figure 8 presents the modified code of _Nuddle_ adding the decision making
mechanism (using green color) to implement _SmartPQ_. We extend the main
structure of _Nuddle_ , renamed to struct smartpq, by adding an additional
field, called algo, to keep track the current algorithmic mode, (either _NUMA-
oblivious_ or _NUMA-aware_). Similarly, struct client and struct server
structures are extended with an additional algo field (e.g., line 111), which
is a pointer to the algo field of struct smartpq. Each active thread
initializes this pointer either in initClient() or initServer() depending on
its role (e.g., line 119). This way, all threads share the same algorithmic
mode at _any_ point in time. In struct client, we also add a pointer to the
shared data structure (line 110), which is used by client threads to
_directly_ perform operations in the data structure in case of _NUMA-
oblivious_ mode. Specifically, we modify the core functions of client threads,
i.e., insert_client() and deleteMin_client(), such that client threads either
directly execute their operations in the data structure (e.g., line 126), or
delegate them to server threads (e.g., line 127-128), with respect to the
current algorithmic mode. In contrast, the core functions of server threads do
not need any modification. Finally, we wrap the code of serve_requests
function, i.e., the lines 86-97 of Figure 6, with an if/else statement on the
algo field (lines 133, 146 in Fig. 8), such that server threads poll at client
threads’ requests only in _NUMA-aware_ mode. In _NUMA-oblivious_ mode,
serve_requests function returns without doing nothing. This way, programmers
do not need to take care of calls on this function in their code, when the
_NUMA-oblivious_ mode is selected.

The decisionTree() function describes the interface with our proposed decision
tree classifier, where the input arguments are associated with its features.
In frequent time lapses, one or more threads may call this function to check
if a transition to another algorithmic mode is needed. If this is the case,
the algo field of struct smartpq is updated (line 154 in Fig. 8), and
_SmartPQ_ switches algorithmic mode, i.e., all active threads start executing
their operations using the new algorithmic mode. If the classifier predicts
the neutral class (line 153), the algo field is not updated, and thus
_SmartPQ_ remains at the currently selected algorithmic mode.

##  4 Experimental Evaluation

In our experimental evaluation, we use a 4-socket Intel Sandy Bridge-EP server
equipped with 8-core Intel Xeon CPU E5-4620 processors providing a total of 32
physical cores and 64 hardware contexts. The processor runs at 2.2GHz and each
physical core has its own L1 and L2 cache of sizes 64KB and 256KB,
respectively. A 16MB L3 cache is shared by all cores in a NUMA socket and the
RAM is 256GB. We use GCC 4.9.2 with -O3 optimization flag enabled to compile
all implementations.

Our evaluation includes the following concurrent priority queue
implementations:

  * –

alistarh_fraser [24, 2]: A _NUMA-oblivious_ , relaxed priority queue [2] based
on Fraser’s skip-list [24] available at ASCYLIB library [16].

  * –

alistarh_herlihy [34, 2]: A _NUMA-oblivious_ , relaxed priority queue [2]
based on Herlihy’s skip-list [34] available at ASCYLIB library [16].

  * –

lotan_shavit [47]: A _NUMA-oblivious_ priority queue available at ASCYLIB
library [16].

  * –

_ffwd_ [65]: A _NUMA-aware_ priority queue based on the delegation technique
[8, 38, 48, 57, 73], which includes _only_ one server thread to perform
operations on behalf of _all_ client threads.

  * –

_Nuddle_ : Our proposed _NUMA-aware_ priority queue, which uses
_alistarh_herlihy_ as the underlying _base algorithm_.

  * –

_SmartPQ_ : Our proposed adaptive priority queue, which uses _Nuddle_ as the
_NUMA-aware_ mode, and _alistarh_herlihy_ as the _NUMA-oblivious_ _base
algorithm_.

We evaluate the concurrent priority queue implementations in the following
way:

  * –

Each execution lasts 5 seconds, during which each thread performs randomly
chosen operations. We also tried longer durations and got similar results.

  * –

Between consecutive operations in the data structure each thread executes a
delay loop of 25 pause instructions. This delay is intentionally added in our
benchmarks to better simulate a real-life application, where operations in the
data structure are intermingled with other instructions in the application.

  * –

At the beginning of each run, the priority queue is initialized with elements
the number of which is described at each figure.

  * –

Each software thread is pinned to a hardware context. Hyperthreading is
enabled when using more than 32 software threads. When exceeding the number of
available hardware contexts of the system, we oversubscribe software threads
to hardware contexts.

  * –

We pin the first 8 threads to the first NUMA node, and consecutive client
thread groups of 7 client threads each, to NUMA nodes in a round-robin
fashion.

  * –

In _NUMA-oblivious_ implementations, any allocation needed in the operation is
executed on demand, and memory affinity is determined by the first touch
policy.

  * –

In _NUMA-aware_ implementations, since our NUMA system has 64-byte cache
lines, the response cache line is shared between up to 7 client threads, using
8-byte return values.

  * –

In _Nuddle_ , the first 8 threads represent server threads. Server threads
repeatedly execute the serve_requests function, and then a randomly chosen
operation until time is up.

  * –

We have disabled the automatic Linux Balancing [42] to get consistent and
stable results.

  * –

All reported results are the average of 10 independent executions with no
significant variance.

Figure 9: Throughput of concurrent priority queue implementations. The columns
show different priority queue sizes using the key range of double the elements
of each size. The rows show different operation workloads. The vertical line
in each plot shows the point after which we oversubscribe software threads to
hardware contexts.

###  4.1 Throughput of _Nuddle_

Figure 9 presents the throughput achieved by concurrent priority queue
implementations for various sizes and operation workloads. _NUMA-aware_
priority queue implementations, i.e., _ffwd_ and _Nuddle_ , achieve high
throughput in _deleteMin_ -dominated workloads: _Nuddle_ performs best in
_all_ _deleteMin_ -dominated workloads, while _ffwd_ outperforms _NUMA-
oblivious_ implementations in the small-sized priority queues (e.g., 100K
elements). In large-sized priority queues, _insert_ operations have a larger
impact on the total execution time (due to a longer traversal), and thus
_Nuddle_ and _NUMA-oblivious_ implementations perform better than _ffwd_ ,
since they provide _higher_ thread-level parallelism. Note that _ffwd_ has
_single-threaded_ performance, since at any point in time only _one_ (server)
thread performs operations in the data structure. Moreover, as it is expected,
the performance of both _ffwd_ and _Nuddle_ saturates at the number of server
threads used (e.g., 8 server threads for _Nuddle_) to perform operations in
the data structure. Finally, we note that the communication between server and
client threads used in _NUMA-aware_ implementations has negligible overhead;
when the number of client threads increases, even though the communication
traffic over the interconnect increases, there is _no_ performance drop.
Overall, we conclude that _Nuddle_ achieves the highest throughput in _all_
_deleteMin_ -dominated workloads, and is the most efficient _NUMA-aware_
approach, since it provides high thread-level parallelism.

On the other hand, _NUMA-oblivious_ implementations incur high performance
degradation in _high-contention_ scenarios, such as _deleteMin_ -dominated
workloads, when using more than one NUMA node (i.e., after 8 threads). As
already discussed in prior works [15, 5, 48, 81, 54, 25], the non-uniformity
in memory accesses and cache line invalidation traffic significantly affects
performance in high-contention scenarios. In _insert_ -dominated workloads,
which incur lower contention, even though _lotan_shavit_ priority queue still
incurs performance degradation when using more than one NUMA nodes of the
system, the _relaxed_ _NUMA-oblivious_ implementations, i.e.,
_alistarh_fraser_ and _alistarh_herlihy_ priority queues, achieve high
scalability. This is because relaxed priority queues decrease both (i) the
contention among threads, and (ii) the cache line invalidation traffic: the
_deleteMin_ operation returns (with a high probability) an element among the
_first few_ (high-priority) elements of the queue, and thus, threads do not
frequently compete for the same elements. Finally, we observe that
_alistarh_herlihy_ priority queue achieves higher performance benefits over
_alistarh_fraser_ priority queue, when we oversubscribe software threads to
the available hardware contexts of our system. Overall, we find that in
_insert_ -dominated workloads, the _relaxed_ _NUMA-oblivious_ implementations
significantly outperform the _NUMA-aware_ ones.

To sum up, we conclude that there is no one-size-fits-all solution, since none
of the priority queues performs best across _all_ contention workloads.
_Nuddle_ achieves the highest throughput in high contention scenarios, while
_alistarh_herlihy_ performs best in low and medium contention scenarios. It is
thus desirable to design a new approach for a concurrent priority queue to
perform best under _all_ various contention scenarios.

###  4.2 Throughput of _SmartPQ_

####  4.2.1 Classifier Accuracy

We evaluate the efficiency of our proposed classifier (Section 3.1.2) using
two metrics: (i) accuracy, and (ii) misprediction cost. First, we define the
accuracy of the classifier as the percentage of _correct_ predictions, where a
prediction is considered correct, if the classifier predicts the algorithmic
mode (either the _NUMA-aware_ _Nuddle_ or the _NUMA-oblivious_
_alistarh_herlihy_) that achieves the best performance between the two. We use
a test set of 10780 different contention workloads, where we randomly select
the values of the features in each workload. In the above test set, our
classifier has 87.9% accuracy, i.e., it mispredicts 1300 times in 10780
different contention workloads. Second, we define the misprediction cost as
the performance difference between the correct (best-performing) algorithmic
mode and the wrong predicted mode normalized to the performance of the wrong
predicted mode. Specifically, assuming the throughput of the wrong predicted
and correct (best-performing) algorithmic mode is $Y$ and $X$ respectively,
the misprediction cost is defined as $((X-Y)/Y)*100\%$. In 1300 mispredicted
workloads, the geometric mean of misprediction cost for our classifier is
30.2%. We conclude that the proposed classifier has _high_ accuracy, and in
case of misprediction, incurs low performance degradation.

####  4.2.2 Varying the Contention Workload

We present the performance benefit of _SmartPQ_ in synthetic benchmarks, in
which we vary the contention workload over time, and compare it with _Nuddle_
and its underlying _base algorithm_ , i.e., _alistarh_herlihy_ priority queue.
In all benchmarks, we change the contention workload every 25 seconds. In
_SmartPQ_ , we set one dedicated sever thread to call the decision tree
classifier _every_ second, in order to check if a transition to another
algorithmic mode is needed. Figure 10 and Figure 11 show the throughput
achieved by all three schemes, when we vary one and multiple features in the
contention workload, respectively. Table 2 and Table 3 show the features of
the workload as they vary during the execution for the benchmarks evaluated in
Figure 10 and Figure 11, respectively. Note that the current size of the
priority queue changes during the execution due to successful _insert_ and
_deleteMin_ operations.

We make three observations. First, as already shown in Section 4.1, there is
no one-size-fits-all solution, since neither _Nuddle_ nor _alistarh_herlihy_
performs best across all various contention workloads. For instance, in Figure
10(b), even though the performance of _Nuddle_ remains constant, it
outperforms _alistarh_herlihy_ , when having 15 running threads, i.e., using 2
NUMA nodes of the system. Second, we observe that _SmartPQ_ successfully
adapts to the best-performing algorithmic mode, and performs best in _all_
contention scenarios. In Figure 11, even when multiple features in the
contention workload vary during the execution, _SmartPQ_ outperforms
_alistarh_herlihy_ and _Nuddle_ by 1.87$\times$ and 1.38$\times$ on average,
respectively. Note that any of the contention workloads evaluated in Figures
10 and 11 belongs in the training data set used for training our classifier.
Third, we note that the decision making mechanism of _SmartPQ_ has very low
performance overheads. Across all evaluated benchmarks, _SmartPQ_ achieves
_only up_ to 5.3% performance slowdown (i.e., when using a range of 50M keys
in Figure 10(a)) over the corresponding baseline implementation
(_alistarh_herlihy_ priority queue). Note that since the proposed decision
tree classifier has very low traversal cost (Section 3.1.2), we intentionally
set a frequent time interval (i.e., one second) for calling the classifier,
such that _SmartPQ_ detects the contention workload change _on time_ , and
quickly adapts itself to the best-performing algorithmic mode. We also tried
large time intervals, and observed that _SmartPQ_ slightly delays to detect
the contention workload change, thus achieving lower throughput in the
transition points.

Overall, we conclude that _SmartPQ_ performs best across _all_ contention
workloads and at _any_ point in time, and incurs negligible performance
overheads over the corresponding baseline implementation.

(a)

(b)

(c)

Figure 10: Throughput achieved by _SmartPQ_ , _Nuddle_ and its underlying
_base algorithm_ (_alistarh_herlihy_), in synthetic benchmarks, in which we
vary a) the key range, b) the number of threads that perform operations in the
data structure, and c) the percentage of _insert_ /_deleteMin_ operations in
the workload. Figure 11: Throughput achieved by _SmartPQ_ , _Nuddle_ and its
underlying _base algorithm_ (_alistarh_herlihy_), in synthetic benchmarks, in
which we vary multiple features in the contention workload.

Time (sec) | Current Size | Key Range | Number of Threads | Insert - DeleteMin (%)
---|---|---|---|---
0 | 1149 | 100K | 50 | 75-25
25 | 812 | 2K | 50 | 75-25
50 | 485 | 1M | 50 | 75-25
75 | 2860 | 10K | 50 | 75-25
100 | 2256 | 50M | 50 | 75-25

(a) Varying the key range in the workload.

Time (sec) | Current Size | Key Range | Number of Threads | Insert - DeleteMin (%)
---|---|---|---|---
0 | 1166 | 20M | 57 | 65-35
25 | 15567 | 20M | 29 | 65-35
50 | 15417 | 20M | 15 | 65-35
75 | 15297 | 20M | 43 | 65-35
100 | 15346 | 20M | 15 | 65-35

(b) Varying the number of threads that perform operations in the data
structure.

Time (sec) | Current Size | Key Range | Number of Threads | Insert - DeleteMin (%)
---|---|---|---|---
0 | 1M | 5M | 22 | 50-50
25 | 140 | 5M | 22 | 100-0
50 | 7403 | 5M | 22 | 30-70
75 | 962 | 5M | 22 | 100-0
100 | 8236 | 5M | 22 | 0-100

(c) Varying the percentage of _insert_ /_deleteMin_ operations.

Table 2: Features of the contention workload for benchmarks evaluated in
Figure 10. We use bold font on the features that change in each execution
phase.

Time (sec) | Current Size | Key Range | Number of Threads | Insert - DeleteMin (%)
---|---|---|---|---
0 | 1M | 10M | 57 | 50-50
25 | 26 | 10M | 36 | 70-30
50 | 12 | 20M | 36 | 50-50
75 | 79 | 20M | 36 | 80-20
100 | 29K | 20M | 50 | 80-20
125 | 319K | 100M | 50 | 50-50
150 | 13 | 100M | 57 | 50-50
175 | 524K | 100M | 22 | 100-0
200 | 524K | 100M | 22 | 50-50
225 | 1142 | 100M | 22 | 50-50
250 | 463 | 200M | 57 | 0-100
275 | 253 | 200M | 57 | 100-0
300 | 33K | 20M | 57 | 0-100
325 | 142 | 20M | 29 | 80-20
350 | 25K | 20M | 29 | 50-50

Table 3: Features of the contention workload for benchmarks evaluated in
Figure 11. We use bold font on the features that change in each execution
phase.

##  5 Discussion & Future Work

In Section 3.1.2, we assume that the contention workload is known a priori to
extract the features needed for classification. To extract these features _on-
the-fly_ , and _dynamically_ detect when contention changes, the main
structure of _SmartPQ_ , i.e., struct smartpq, needs to be enriched with
additional fields to keep track of workload statistics (e.g., the number of
completed _insert_ /_deleteMin_ operations, the number of active threads that
perform operations on the data structure, the minimum and/or maximum key that
has been requested so far). Active threads that perform operations on the data
structure could atomically update these statistics. In frequent time lapses,
either a background thread or an active thread could extract the features
needed for classification based on the workload statistics, and call the
classifier to predict if a transition to another algorithmic mode is needed.
Finally, an additional parameter could be also added in _SmartPQ_ to configure
how often to collect workload statistics.

In our experimental evaluation, we pin server threads on a single NUMA node
and client threads on all nodes. We have chosen to do so (i) for simplicity,
given that this approach fits well with our microbenchmark-based evaluation,
and (ii) because this is par with prior works on concurrent data structures
[16, 65, 2, 10, 67, 66, 14, 46, 11, 78, 9, 71, 27, 37, 7, 22]. In a real-life
scenario, where _SmartPQ_ is used as a part of an application, client threads
do _not_ need to be pinned in hardware contexts, and they can be allowed to
run in any core of the system. However, for our approach to be meaningful
server threads need to be limited on a single NUMA node. This can easily be
done by creating the server threads when _SmartPQ_ is initialized, and pinning
them to hardware contexts that are located at the same NUMA node. In this
case, server threads are background threads that only accept and serve
requests from various client threads, which are part of the high-level
application.

Finally, even though we focus on a microbenchmark-based evaluation to cover a
_wide variety_ of contention scenarios, it is one of our future directions to
explore the efficiency of _SmartPQ_ in real-life applications, such as web
servers [63, 28], graph traversal applications [67, 12] and scheduling in
operating systems [1]. As future work, we also aim to investigate the
applicability of our approach in other data structures, that may have similar
behavior with priority queues (e.g., skip lists, search trees), and extend our
proposed classifier (e.g., adding more features) to cover a variety of NUMA
CPU-centric systems with different architectural characteristics.

##  6 Related Work

To our knowledge, this is the first work to propose an adaptive priority queue
for NUMA systems, which performs best under _all_ various contention
workloads, and even when contention varies over time. We briefly discuss prior
work.

Concurrent Priority Queues. A large corpus of work proposes concurrent
algorithms for priority queues [47, 45, 67, 74, 2, 9, 77, 64, 6, 80, 68, 66,
62], or generally for skip lists [13, 24, 23, 34, 35, 18, 46, 61, 11]. Recent
works [47, 45] designed lock-free priority queues that separate the logical
and the physical deletion of an element to increase parallelism. Alistarh et
al. [2] design a relaxed priority queue, called SprayList, in which
_deleteMin_ operation returns with a high probability, an element among the
_first_ $\mathcal{O}(p\log{}3p)$ elements of the priority queue, where $p$ is
the number of threads. Sagonas et al [66] design a contention avoiding
technique, in which _deleteMin_ operation returns the highest-priority element
of the priority queue under _low_ contention, while it enables relaxed
semantics when high contention is detected. Specifically, under high-
contention a few _deleteMin_ operations are queued, and later several elements
are deleted from the head of the queue _at once_ via a combined deletion
operation. Heidarshenas et al. [30] design a novel architecture for relaxed
priority queues. These prior approaches are _NUMA-oblivious_ implementations.
Thus, in NUMA systems, they incur significant performance degradation in high-
contention scenarios (e.g., _deleteMin_ -dominated workloads in Section 4.1).
In contrast, Calciu et al. [9] propose a _NUMA-friendly_ priority queue
employing the combining and elimination techniques. Elimination allows the
complementary operations, i.e., _insert_ with _deleteMin_ , to complete
_without_ updating the data structure, while combining is a technique similar
to the delegation technique [8, 38, 48, 57, 73] of _Nuddle_ and _ffwd_ [65].
Finally, Daly et al. [14] propose an efficient technique to obtain _NUMA-
aware_ skip lists, which however, can only be applied to skip list-based data
structures. In contrast, _Nuddle_ is a _generic_ technique to obtain _NUMA-
aware_ data structures.

Black-Box Approaches. Researchers have proposed black-box approaches: any data
structure can be made wait-free or _NUMA-aware_ without effort or knowledge on
parallel programming or NUMA architectures. Herlihy [33] provides a universal
method to design wait-free implementations of any sequential object. However,
this method remains impractical due to high overheads. Hendler et al. [31]
propose flat combining; a technique to reduce synchronization overheads by
executing multiple client threads’ requests _at once_. Despite significant
improvements [32], this technique provides high performance _only_ for a few
data structures (e.g., synchronous queues). _ffwd_ [65] is black-box approach,
which uses the delegation technique [8, 38, 48, 57, 73] to eliminate cache
line invalidation traffic over the interconnect. However, _ffwd_ is limited to
single threaded performance. Calciu et al. [10] propose a black-box technique,
named Node Replication, to obtain concurrent _NUMA-aware_ data structures. In
Node Replication, every NUMA node has replicas of the shared data structure,
which are synchronized via a shared log. Although _ffwd_ and Node Replication
are generic techniques to obtain _NUMA-aware_ data structures, similarly to
_Nuddle_ , both of them use a _serial asynchronized_ implementation as the
underlying _base algorithm_. Thus, if they are used as the _NUMA-aware_
algorithmic mode in an adaptive data structure, which dynamically switches
between a _NUMA-oblivious_ and a _NUMA-aware_ mode, both _ffwd_ and _Node
Replication_ need a synchronization point between transitions to ensure
correctness. Consequently, they would incur high performance overheads, when
transitions between algorithmic modes happen at a non-negligible frequency.

Machine learning in Data Structures. Even though machine learning is widely
used to improve performance in many emerging applications [21, 82, 58, 4, 26,
50, 41, 53, 51, 17, 69, 3, 44], there is a handful of works [20, 40] that
leverage machine learning to design _highly-efficient_ concurrent data
structures. Recently, Eastep et al. [20] use reinforcement learning to on-the-
fly tune a parameter in the flat combining technique [31, 32], which is used
in skip lists and priority queues. Kraska et al. [40] demonstrate that machine
learning models can be trained to predict the position or existence of
elements in key-value lookup sets, and discuss under which conditions learned
index models can outperform the traditional indexed data structures (e.g.,
B-trees).

##  7 Conclusion

We propose _SmartPQ_ , an adaptive concurrent priority queue for NUMA
architectures, which performs best under _all_ various contention scenarios,
and even when contention varies over time. _SmartPQ_ has two key components.
First, it is built on top of _Nuddle_ ; a generic low-overhead technique to
obtain efficient _NUMA-aware_ data structures using _any_ concurrent _NUMA-
oblivious_ implementation as its backbone. Second, _SmartPQ_ integrates a
lightweight decision making mechanism, which is based on a simple decision
tree classifier, to decide when to switch between _Nuddle_ , i.e., a _NUMA-
aware_ algorithmic mode, and its underlying _base algorithm_ , i.e., a _NUMA-
oblivious_ algorithmic mode. Our evaluation over a wide range of contention
scenarios demonstrates that _SmartPQ_ switches between the two algorithmic
modes with negligible overheads, and significantly outperforms prior schemes,
even when contention varies over time. We conclude that _SmartPQ_ is an
efficient concurrent priority queue for NUMA systems, and hope that this work
encourages further study on adaptive concurrent data structures for NUMA
architectures.

## References

  * [1] L. A. Torrey, J. Coleman, and B. Miller, “A Comparison of Interactivity in the Linux 2.6 Scheduler and an MLFQ Scheduler,” _Software Practice and Experience._ , 2007.
  * [2] D. Alistarh, J. Kopinsky, J. Li, and N. Shavit, “The SprayList: a Scalable Relaxed Priority Queue,” in _PPoPP_ , 2015.
  * [3] A. Benatia, W. Ji, Y. Wang, and F. Shi, “Sparse Matrix Format Selection with Multiclass SVM for SpMV on GPU,” _ICPP_ , 2016.
  * [4] A. Benatia, W. Ji, Y. Wang, and F. Shi, “Sparse Matrix Format Selection with Multiclass SVM for SpMV on GPU,” in _ICPP_ , 2016.
  * [5] S. Boyd-Wickizer, A. T. Clements, Y. Mao, A. Pesterev, M. F. Kaashoek, R. Morris, and N. Zeldovich, “An Analysis of Linux Scalability to Many Cores,” in _OSDI_ , 2010.
  * [6] G. S. Brodal, J. L. Träff, and C. D. Zaroliagis, “A Parallel Priority Queue with Constant Time Operations,” _J. Parallel Distrib. Comput._ , 1998\.
  * [7] N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun, “A Practical Concurrent Binary Search Tree,” in _PPoPP_ , 2010.
  * [8] I. Calciu, D. Dice, T. Harris, M. Herlihy, A. Kogan, V. J. Marathe, and M. Moir, “Message Passing or Shared Memory: Evaluating the Delegation Abstraction for Multicores,” in _OPODIS_ , 2013.
  * [9] I. Calciu, H. Mendes, and M. Herlihy, “The Adaptive Priority Queue with Elimination and Combining,” in _DISC_ , 2014.
  * [10] I. Calciu, S. Sen, M. Balakrishnan, and M. K. Aguilera, “Black-box Concurrent Data Structures for NUMA Architectures,” _ASPLOS_ , 2017.
  * [11] J. Choe, A. Huang, T. Moreshet, M. Herlihy, and R. I. Bahar, “Concurrent Data Structures with Near-Data-Processing: An Architecture-Aware Implementation,” in _SPAA_ , 2019.
  * [12] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to Algorithms, Third Edition_. The MIT Press, 2009.
  * [13] T. Crain, V. Gramoli, and M. Raynal, “No Hot Spot Non-blocking Skip List,” in _ICDCS_ , 2013.
  * [14] H. Daly, A. Hassan, M. F. Spear, and R. Palmieri, “NUMASK: High Performance Scalable Skip List for NUMA,” in _DISC_ , 2018.
  * [15] T. David, R. Guerraoui, and . V. Trigonakis, “Everything You Always Wanted to Know About Synchronization but Were Afraid to Ask,” in _SOSP_ , 2013.
  * [16] T. A. David, R. Guerraoui, and V. Trigonakis, “Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures,” _ASPLOS_ , 2015.
  * [17] L. Dhulipala, C. Hong, and J. Shun, “ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms,” in _VLDB Endowment_ , 2020.
  * [18] I. Dick, A. Fekete, and V. Gramoli, “A Skip List for Multicore,” _Concurrency and Computation: Practice and Experience_ , 2017.
  * [19] L. Doddipalli and K. Rani, “Ensemble Decision Tree Classifier For Breast Cancer Data,” _International Journal of Information Technology Convergence and Services_ , 2012.
  * [20] J. Eastep, D. Wingate, and A. Agarwal, “Smart Data Structures: An Online Machine Learning Approach to Multicore Data Structures,” in _ICAC_ , 2011\.
  * [21] A. Elafrou, G. I. Goumas, and N. Koziris, “Performance Analysis and Optimization of Sparse Matrix-Vector Multiplication on Modern Multi- and Many-Core Processors,” in _ICPP_ , 2017.
  * [22] F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel, “Non-blocking Binary Search Trees,” in _PODC_ , 2010.
  * [23] M. Fomitchev and E. Ruppert, “Lock-free Linked Lists and Skip Lists,” in _PODC_ , 2004.
  * [24] K. Fraser., “Practical Lock-Freedom,” _PhD thesis, University of Cambridge_ , 2004.
  * [25] C. Giannoula, N. Vijaykumar, N. Papadopoulou, V. Karakostas, I. Fernandez, J. Gómez-Luna, L. Orosa, N. Koziris, G. Goumas, and O. Mutlu, “SynCron: Efficient Synchronization Support for Near-Data-Processing Architectures,” in _HPCA_ , 2021.
  * [26] P. Grönquist, C. Yao, T. Ben-Nun, N. Dryden, P. Dueben, S. Li, and T. Hoefler, “Deep Learning for Post-Processing Ensemble Weather Forecasts,” _Philosophical Transactions of the Royal Society A_ , 2021.
  * [27] R. Guerraoui and V. Trigonakis, “Optimistic Concurrency with OPTIK,” in _PPoPP_ , 2016.
  * [28] M. Harchol-Balter, B. Schroeder, N. Bansal, and M. Agrawal, “Size-based Scheduling to Improve Web Performance,” _TOCS_ , 2003.
  * [29] T. Harris, “A Pragmatic Implementation of Non-Blocking Linked Lists,” in _DISC_ , 2001.
  * [30] A. Heidarshenas, T. Gangwani, S. Yesil, A. Morrison, and J. Torrellas, “Snug: Architectural support for relaxed concurrent priority queueing in chip multiprocessors,” in _ICS_ , 2020.
  * [31] D. Hendler, I. Incze, N. Shavit, and M. Tzafrir, “Flat Combining and the Synchronization-parallelism Tradeoff,” in _SPAA_ , 2010.
  * [32] D. Hendler, I. Incze, N. Shavit, and M. Tzafrir, “Scalable Flat-Combining Based Synchronous Queues,” in _DISC_ , 2010.
  * [33] M. Herlihy, “Wait-free Synchronization,” _TOPLAS_ , 1991.
  * [34] M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit, “A Simple Optimistic Skiplist Algorithm,” in _SIROCCO_ , 2007.
  * [35] M. Herlihy and N. Shavit, _The Art of Multiprocessor Programming_. Morgan Kaufmann Publishers Inc., 2008.
  * [36] S. V. Howley and J. Jones, “A Non-blocking Internal Binary Search Tree,” in _SPAA_ , 2012.
  * [37] S. V. Howley and J. Jones, “A Non-Blocking Internal Binary Search Tree,” in _SPAA_ , 2012.
  * [38] D. Klaftenegger, K. Sagonas, and K. Winblad, “Delegation Locking Libraries for Improved Performance of Multithreaded Programs,” in _EuroPar_ , 2014\.
  * [39] V. Kolmogorov, “Blossom V: A new Implementation of a Minimum Cost Perfect Matching Algorithm,” 2009.
  * [40] T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis, “The Case for Learned Index Structures,” in _SIGMOD_ , 2018.
  * [41] A. Kusum, I. Neamtiu, and R. Gupta, “Safe and Flexible Adaptation via Alternate Data Structure Representations,” in _CC_ , 2016.
  * [42] L. T. Schermerhorn. (2007) Automatic Page Migration for Linux [A Matter of Hygiene].
  * [43] D. Lasalle and G. Karypis, “Multi-threaded Graph Partitioning,” in _IPDPS_ , 2013.
  * [44] P. Li, H. Lu, Q. Zheng, L. Yang, and G. Pan, “Lisa: A learned index structure for spatial data,” in _SIGMOD_ , 2020.
  * [45] J. Lindén and B. Jonsson, “A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention,” in _OPODIS_ , 2013.
  * [46] Z. Liu, I. Calciu, M. Herlihy, and O. Mutlu, “Concurrent Data Structures for Near-Memory Computing,” in _SPAA_ , 2017.
  * [47] I. Lotan and N. Shavit., “Skiplist-Based Concurrent Priority Queues,” in _IPDPS_ , 2000.
  * [48] J.-P. Lozi, F. David, G. Thomas, J. Lawall, and G. Muller, “Remote Core Locking: Migrating Critical-Section Execution to Improve the Performance of Multithreaded Applications,” in _USENIX ATC_ , 2012.
  * [49] R. Marotta, M. Ianni, A. Pellegrini, and F. Quaglia, “A Non-Blocking Priority Queue for the Pending Event Set,” in _SIMUTOOLS_ , 2016.
  * [50] S. Memeti, S. Pllana, A. Binotto, J. Kołodziej, and I. Brandic, “Using Meta-Heuristics and Machine Learning for Software Optimization of Parallel Computing Systems: A Systematic Literature Review,” _Computing_ , 2019.
  * [51] K. Meng, J. Li, G. Tan, and N. Sun, “A Pattern Based Algorithmic Autotuner for Graph Processing on GPUs,” in _PPoPP_ , 2019.
  * [52] M. M. Michael, “High Performance Dynamic Lock-free Hash Tables and List-based Sets,” in _SPAA_ , 2002.
  * [53] D. Michie, “’Memo’ Functions and Machine Learning,” in _Nature_ , 1968.
  * [54] D. Molka, D. Hackenberg, R. Schone, and M. S. Muller, “Memory Performance and Cache Coherency Effects on an Intel Nehalem Multiprocessor System,” in _PACT_ , 2009.
  * [55] A. Natarajan and N. Mittal, “Fast Concurrent Lock-free Binary Search Trees,” in _PPoPP_ , 2014.
  * [56] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, “Scikit-learn: Machine Learning in Python,” _J. Mach. Learn. Res._ , 2011.
  * [57] D. Petrović, T. Ropars, and A. Schiper, “On the Performance of Delegation over Cache-Coherent Shared Memory,” in _ICDCN_ , 2015.
  * [58] J. C. Pichel and B. Pateiro-López, “A New Approach for Sparse Matrix Classification Based on Deep Learning Techniques,” in _CLUSTER_ , 2018\.
  * [59] K. Polat and S. Güneş, “A Novel Hybrid Intelligent Method Based on C4.5 Decision Tree Classifier and One-against-All Approach for Multi-Class Classification Problems,” _Expert Syst. Appl._ , 2009.
  * [60] R. C. Prim, “Shortest Connection Networks and some Generalizations,” _The Bell Systems Technical Journal_ , 1957.
  * [61] W. Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees,” _Commun. ACM_ , 1990.
  * [62] M. Rab, R. Marotta, M. Ianni, A. Pellegrini, and F. Quaglia, “NUMA-Aware Non-Blocking Calendar Queue,” in _DS-RT_ , 2020.
  * [63] M. Rawat and A. D. Kshemkalyani, “SWIFT: Scheduling in Web Servers for Fast Response Time,” in _NCA_ , 2003.
  * [64] H. Rihani, P. Sanders, and R. Dementiev, “MultiQueues: Simpler, Faster, and Better Relaxed Concurrent Priority Queues,” 2015.
  * [65] S. Roghanchi, J. Eriksson, and N. Basu, “Ffwd: Delegation is (Much) Faster Than You Think,” in _SOSP_ , 2017.
  * [66] K. Sagonas and K. Winblad, “The Contention Avoiding Concurrent Priority Queue,” in _LCPC_ , 2016.
  * [67] K. Sagonas and K. Winblad, “The Contention Avoiding Concurrent Priority Queue,” in _LCPC_ , 2017.
  * [68] P. Sanders, “Randomized Priority Queues for Fast Parallel Access,” _J. Parallel Distrib. Comput._ , 1998.
  * [69] N. Sedaghati, T. Mu, L.-N. Pouchet, S. Parthasarathy, and P. Sadayappan, “Automatic Selection of Sparse Matrix Representation on GPUs,” in _ICS_ , 2015.
  * [70] D. Siakavaras, K. Nikas, G. Goumas, and N. Koziris, “RCU-HTM: A Generic Synchronization Technique for Highly Efficient Concurrent Search Trees,” _CCPE_ , 2021.
  * [71] D. Siakavaras, K. Nikas, G. I. Goumas, and N. Koziris, “RCU-HTM: Combining RCU with HTM to Implement Highly Efficient Concurrent Binary Search Trees,” PACT 2017.
  * [72] J. Sloan, R. Kumar, and G. Bronevetsky, “Algorithmic Approaches to Low Overhead Fault Detection for Sparse Linear Algebra,” in _DSN_ , 2012.
  * [73] M. A. Suleman, O. Mutlu, M. K. Qureshi, and Y. N. Patt, “Accelerating Critical Section Execution with Asymmetric Multi-Core Architectures,” in _ASPLOS_ , 2009.
  * [74] H. Sundell and P. Tsigas, “Fast and Lock-free Concurrent Priority Queues for Multi-thread Systems,” _Journal of Parallel and Distributed Computing_ , 2005.
  * [75] W. T. Tang, R. S. M. Goh, and I. L.-J. Thng, “Ladder Queue: An O(1) Priority Queue Structure for Large-scale Discrete Event Simulation,” _TOMACS._ , 2005\.
  * [76] M. Thorup, “Integer Priority Queues with Decrease Key in Constant Time and the Single Source Shortest Paths Problem,” in _STOC_ , 2003.
  * [77] M. Wimmer, J. Gruber, J. L. Träff, and P. Tsigas, “The Lock-free k-LSM Relaxed Priority Queue,” in _PPoPP_ , 2015.
  * [78] K. Winblad, K. Sagonas, and B. Jonsson, “Lock-Free Contention Adapting Search Trees,” in _SPAA_ , 2018.
  * [79] Y. Xu, K. Li, and J. Hu, “A Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems using Multiple Priority Queues,” _Information Sciences_ , 2014.
  * [80] D. Zhang and D. Dechev, “A Lock-Free Priority Queue Design Based on Multi-Dimensional Linked Lists,” _TPDS_ , 2016.
  * [81] M. Zhang, H. Chen, L. Cheng, F. C. M. Lau, and C. Wang, “Scalable Adaptive NUMA-Aware Lock,” _TPDS_ , 2017.
  * [82] Y. Zhao, J. Li, C. Liao, and X. Shen, “Bridging the Gap between Deep Learning and Sparse Matrix Format Selection,” in _PPoPP_ , 2018.