High-Bandwidth Memory (HBM) provides lower latency on many concurrent memory accesses than regular DRAM. This is especially useful on GPUs, where thousands of lightweight threads access data on shared memory at the same time. On regular multicore CPUs, the degree of multithreaded parallelism is usually not high enough to improve performance noticeably by using HBM. However, with an increasingly rising core count inside CPUs, especially manycore processors like the Xeon Phi Knights Landing (KNL) from Intel, the properties of HBM are more and more interesting to exploit. In this paper, we want to analyze the impact of HBM for data stream processing, notably multithreaded hash joins over several input data streams as well as tuple allocation and aggregation within this memory technology. Our results show improvements on the tuple processing rate by up to a magnitude when concurrently accessed data is stored in HBM on chip instead of DDR4, considering di erent HBM con gurations of the KNL.
A widely known classi cation for performance analysis is the division into memory-bound or CPU-bound applications, allowing to tackle the right spots for optimization. In today's systems, parallelism is the key phrase to improve speedup for CPU-heavy software, which can be applied on di erent levels. Multithreading is a very common paradigm for executing independent computations in parallel, scheduled by the OS, reaching high degrees of concurrency through multicore CPUs and GPUs.
However, with an increased number of threads usually the number of concurrent memory accesses is raised at the same time. Regular memory controllers to main memory are capable of dealing with multiple memory requests of concurrent threads. They reach their limit on bandwidth very fast, though, especially with high numbers of threads, which is very common in GPUs and manycore CPU architectures.
That is a reason for HBM development, which provides
a much higher available bandwidth for parallel memory
requests, overcoming the memory wall [
With this paper, we want to tackle the following questions: How good is the performance gain of HBM compared to regular DDR4 when used for processing of data streams? Which data structures bene t the most when stored in HBM, e.g., tuples, states, or hash tables? Where is the break-even point of multithreaded memory access, until which a performance gain is achieved compared to main memory DDR4 SRAM? 2.
Since the MCDRAM was introduced by the Xeon Phi KNL processor in 2016, some research already has been done related to the KNL in other elds of science, like high performance computing or machine learning. Most of the papers try to determine the impact of a manycore CPU to their applications.
Smith et al. [
Barnes et al. [
Cheng et al. [
However, joins on a DSMS di er fundamentally from join algorithms of a DBMS. A major di erence is the streaming property where tuples arrive continuously, therefore, a join operator has to process tuples unblocked. This means that it cannot simply wait until all data has been read before producing results, hence certain stream join algorithms have been developed.
One of the rst important algorithms for joining data
streams was the Symmetric Hash Join (SHJ) [
Due to the fact that hardware and software improves by technological advance over time, applications try to adapt as e ectively as possible for better performance or new possibilities. Two main categories regarding hardware are processors and memory. Both of them have a very heterogeneous landscape in terms of available variants. To name a few, there are CPUs, GPUs, coprocessors, FPGAs, DSPs as well as registers, caches, DDR4, HBM, NVRAM and many more. A recent trend goes to manycore CPUs with integrated HBM, discussed further in this section. 3.1
After hitting the CPU clock rate wall at around 4 GHz and developing processors to use multiple cores on a single chip, a direction goes to CPUs with more and more smaller cores, so called manycore architectures. While hundreds and thousands of (lightweight) cores are already common in GPUs, regular CPUs are far o from such numbers. For multithreading, performance improvements depend mainly on the possible degree of parallelism of applications.
Both GPU and CPU threads have their own advantages
and disadvantages for parallelism, though. GPU threads are
grouped together into warps. All threads inside a warp
perform the same instructions simultaneously, ideally repeating
them multiple times, leading to an intense amount of
parallelism. However, if somehow a thread inside a warp has to
change instructions, maybe because of branching code, its
instructions get serialized, losing performance [
On CPU side, a main challenge lies in e cient scaling
of applications to hundreds of threads. This is a common
problem of traditional databases when using manycore
processors, for instance in terms of concurrency control [
A well-known example for manycore CPUs is the Xeon Phi product line from Intel. The rst Xeon Phi, called Knights Ferry, was released 2010 as a prototype for research purposes and not commercially available. Knights Ferry is a coprocessor, that means, it needs a host system with a regular CPU, like GPUs also do.
The successor was released 2012, called Knights Corner (KNC), still as coprocessor only but commercially obtainable. For database usage, the main bottleneck emerges from the PCI connection to the host system, limiting data transfer through o oading to 15GB/s. As a result, the KNC is not often found in used hardware for database systems.
With the latest release, namely Knights Landing (KNL), available since 2016, Intel addressed this bottleneck by discarding the coprocessor design, although the KNL was later additionally released as coprocessor. With a high core count for CPUs (up to 72 cores on chip) as well as HBM for higher memory bandwidth, the KNL got an increased interest for researchers as well as owners of database systems. 3.2
As already stated earlier, there are di erent variants of memory, leading to the so-called memory hierarchy (see Figure 1). It is always a tradeo between capacity and access latency (respective the price). The HBM in general has comparable latency to regular DDR4 SRAM but is more limited in size.
However, with multithreading purposes comes another requirement to memory, called memory bandwidth. Singlethreaded applications mostly do not saturate the available bandwidth of main memory (for DDR4 around 90GB/s). Nevertheless, multiple threads accessing memory in parallel can reach this limit very quickly, especially on manycore architectures where hundreds of threads can be executed simultaneously. This is also a common problem on GPUs, therefore, the HBM was developed years ago.
To overcome this limitation for intense multithreading on
CPUs, the KNL utilizes its own HBM on chip, the so-called
Multi-Channel DRAM (MCDRAM). The MCDRAM itself
is a memory variant specialized for high bandwidth, allowing
up to 420GB/s data transfer rates with slightly worse access
latency [
The utilization of the MCDRAM, however, is no trivial decision. Because of the generally higher accessing latencies, Intel provided three con gurations ( at, cache, hybrid) to allow owners to decide where the MCDRAM can be preferably used.
In cache mode, the MCDRAM is not visible to applications. Instead, the operating system uses it as a huge L3 cache, with usual advantages and disadvantages. A disadvantage to remember is the increased latency on a cache miss, where the data has to be retrieved from main memory with detour of the MCDRAM. In at mode, the MCDRAM can be addressed by the application itself, else it is not used. In this case, the programmer has to decide where the application bene ts the most from HBM. The third con guration is a hybrid mode, where the MCDRAM is partly used as cache as well as addressable memory.
It is important to mention that processors of the next generation with more cores (like server CPUs) will very likely use this HBM in addition to regular DDR4 SRAM. 3.3
With simpler core design compared to current state of the art multicore processors as well as low clock frequencies of 1.5GHz, algorithms and implementations have to adapt to manycore CPU properties to gain any performance advantage. The parallel execution of code along with data partitioning is a key to achieve this goal. By increasing the thread count as well as tting algorithms to manycore architectures e ciently, memory bandwidth typically becomes a major bottleneck very quickly. Therefore the MCDRAM as a version of HBM provides new possibilities to overcome this gap, supporting three di erent con gurations as a tuning parameter. In this paper we want to analyze its impact and bene t on typical streaming operations and semantics, which are further explained in the following section.
While relational database systems are still the most
common platforms for data storage and processing [
To give an example, join algorithms that work well in relational databases (like sort-merge joins) are impossible to use directly in a DSMS because of their blocking property. That means, they can execute only if all the data is stored in main memory, for example to sort them for joining. On data streams possibly never ending, the joins must be nonblocking, in other words, producing results continuously instead of only once.
In this section, we want to give a short overview about our used stream processing engine PipeFabric1 as well as a common join algorithm and window semantics in DSMS, relevant for our experimental analysis with HBM.
PipeFabric is a stream processing engine developed at our research group of the TU Ilmenau. It is open source and fully functional, written in C++. Data streams can be constructed via di erent network protocols, like AMQP, MQTT or ZeroMQ, to get tuples from di erent servers like Apache Kafka or RabbitMQ. It is also possible to create nite streams from les or just construct tuples through a generator function.
For queries, common operators are provided, like selection and projection or joins over multiple streams. These operators are connected like a data ow graph, where input tuples are forwarded between the query operators. This is exemplarily shown in Figure 2, where tuples from two data sources arrive. First, their key attribute (K) is speci ed, followed by window (W) operators, avoiding a memory overow caused by in nite data streams as well as keeping only recent data for further computations. After that, the tuples are forwarded to a join (J) operator, which joins tuples according to their keys. 4.2
Windows are a very common way to deal with in nite data streams. Usually data streams from various sources like sensor networks produce information continuously over long time periods. Since a few years the cost of memory dropped signi cantly, however, even if it would be theoretically possible to store all retrieved information, it would be no good idea. Finding correlations in terms of data mining is much more di cult in huge amounts of data, even if some information is already outdated, like sensor measurements weeks ago.
A window holds a certain number of tuples that are currently relevant for queries. There are di erent window algorithms, like sliding or tumbling windows, determining the data displacement strategy. A sliding window for example invalidates the oldest tuple when a new tuple arrives. The number of tuples a window holds can be xed, e.g. one million, or time based, where the size changes dynamically.
To invalidate tuples, another common algorithm is the
positive-negative approach [
For our testing purposes with HBM we used a sliding window operator with xed length for the input stream. Because of the sequential data access and processing of a window, we expect that it ideally bene ts very well from the increased available bandwidth, leading to higher tuple processing rates. 4.3
For our measurements in Section 5, we decided to show
results based on hashing, like the common Symmetric Hash
Join (SHJ). The SHJ [
Figure 3 shows the general idea of the join algorithm for two input streams. If a tuple arrives either on the left or the right input stream, it is rst inserted into its corresponding hash table. After that, it is probed against the other hash table for matches. For all partners found, tuples are produced and returned to the following operator in a single output stream.
The sizes of the hash tables are dependent on the input tuple rate of the individual stream. If a stream delivers tuples faster than another stream or the same key value occurs more frequently over time, the corresponding hash table is reoptimized regarding its hash function to avoid too many collisions. When an outdated tuple from a predecessing window operator arrives, it already has an entry inside of the hash table. Therefore it is not joined, but removed from the table, leading to no more matches from future tuples of the other stream.
It is also possible to extend the SHJ to n > 2 input streams, resulting in n hash tables. Every input tuple is probed against all the other n 1 hash tables after being inserted.
Peng et al. [
Regarding the MCDRAM con gurations, running MCDRAM as huge last level cache is the most trivial way of utilizing it, because there are no changes necessary inside an application to bene t from higher bandwidth. However, it worsens the latency on cache misses, because memory requests cannot go directly from L2 cache to main memory, instead they have to traverse MCDRAM before. The general advice2 regarding MCDRAM in performance aspects is to choose carefully which data structures should be placed in MCDRAM and which not, using the at mode. The Memkind API3 provides HBM allocators for any data type to use HBM instead of regular DDR4 SRAM.
Another possibility addressing HBM is provided by Numactl4. Numactl allows applications to run fully on a certain memory device, e.g. on MCDRAM without using DDR4. Because of the goal of our work, analyzing e ects of HBM on di erent individual data structures and operators, we did not use any test results with Numactl in this paper.
In summary, the test cases considered the following options:
Allocations can be done in MCDRAM as well as in DDR4. All tests use data streams directly streamed from main memory without any I/O from disk, with one million tuples per stream (except for joins) for calculating the tuple processing rate (tp/s) of queries. We also tested higher tuple amounts per stream, but the processing rate (tp/s) did not change, pointing out that a million tuples is enough for calculating rates. With these results, we want to show the in uence of HBM on performance regarding di erent data structures. 5.1
For our tests with HBM we used a KNL 7210 with 64 cores, 96GB DDR4 memory and 16GB MCDRAM. PipeFabric is compiled with the Intel compiler version 17.0.6 and the AVX512 instruction set support. Threads run in scattered setting, which means that each of the 64 cores gets rst a single thread before a core gets a second one. The clustering mode of the KNL runs SNC-4, that means, the core grid is divided into four NUMA sections with 24 GB main memory and 4 GB MCDRAM each.
Tuples use an integer, a double as well as a string value as format. For stable results without too much randomness, the integer is simply counted up from zero modulo 10,000 and declared as key attribute for the join tests.
5.2
Our rst measurements address the allocation of data stream tuples. Three possibilities can be explored: (1) Storing them in main memory DDR4, (2) allocate them in HBM directly with memkind API, and (3) using MCDRAM as last level cache without further modi cations. We tested all three variants regarding tuple throughput for a query with a selection operator (50% selectivity), streaming the tuples right through it in the absence of additional operators.
To utilize the bandwidth and 256 supported threads of the KNL 7210 processor, we run the same query multiple times while increasing the number of OpenMP threads. Each OpenMP thread runs a single instance of the query (InterQuery Parallelism), leading to a rising number of memory requests. Threads are created with the rst parallel pragma of OpenMP, therefore we skip the rst run for our measurements. Our results are shown in Figure 4 for all three options mentioned above. The abbreviation m expresses a million tuples per second while k stands for thousand tuples per second accordingly.
It can easily be seen that the sequential tuple access creates ideal conditions to saturate the bandwidth. Important to notice is the di erence between MCDRAM as cache and being directly addressed. In the latter case there are no cache misses in MCDRAM, saving the detour back to main memory. The increased latency costs of MCDRAM access can be hidden after each core got two threads due to hyperthreading e ects, improving performance of MCDRAM in at mode even more. 5.3
A window operator stores a sequence of tuples, de ning a range in which tuples are relevant for further processing (see Section 4.2). The elements stored in a window can be allocated in main memory and HBM as well. We investigated the performance advantage in the same way like allocating tuples in the last Section.
The window operator uses a sliding window with a size of 100,000 tuples, preventing a possible memory over ow. This is especially useful for the limited space of the MCDRAM to 16GB. In addition, a selection operator with 50% selectivity processes the valid tuples afterwards. The results are shown in Figure 5. 40m
After 20 threads requesting data from memory simultaneously, an advantage between HBM and regular DDR4 can be noticed, up to around 80% with 128 threads. Because of the window semantics, inserting new tuples and removing the oldest ones leads to a predictable memory access pattern. The cache mode cannot compensate misses and the generally higher access latencies with higher bandwidth, leading to no noticeable improvements overall. The MCDRAM seems to show best performance for 64, 128, 192 and 256 threads where each core has one, two, three or four threads, with equal load on each core. 5.4
Another chance to use HBM for improved bandwidth is the allocation of hash tables, being used regularly by join operators. Two input streams deliver 100,000 tuples each for our test case. After key speci cation, the tuples are forwarded to the join operator. Because of the speci ed workload, one million tuples are produced by joining.
Like the tests before, we run this query in parallel with OpenMP threads to show Inter-Query Parallelism performance. In Figure 6 the results of the join operator are shown. 128 #Threads
The numbers are quite disappointing, although they met our earlier expectations. With MCDRAM as a cache the rate even gets worse, caused by random memory access and cache misses. But even with directly allocating and updating only hash tables in MCDRAM, the tuple processing rate increases by 15% at most while running 64 threads (one per core). 5.5
Finally we want to improve the tuple processing rate of aggregation operators. Each operator holds a state where the aggregate is stored, e.g. in simple cases just a sum, average or current maximum. This state can also be allocated on HBM for increased bandwidth. Figure 7 shows the results of our measurements.
The observation shows that it is just possible to store small states in L1 and L2 cache of each core. This results in no improvement of performance when utilizing HBM instead of DDR4. The peak rates at 64, 128 and 192 threads can again be explained by the scattered thread setting, where threads are distributed evenly to the cores. With 128 threads, each core maximized its parallelism because each core supports two hardware threads without hyperthreading side e ects.
The questions of the introduction can be answered in the following way. First, the performance gain of HBM can increase up to a magnitude when a high count of threads is accessing memory sequentially. Instead of just running HBM as a cache without further modi cations, it is absolutely necessary to carefully store suitable data structures in HBM to avoid expensive cache misses.
In addition to this, not all data structures bene t equally from the higher available bandwidth. Random access patterns that are commonly found in hash joins cannot exploit e ectively the HBM properties with prefetching mechanisms. On the other hand, predictably removing and adding elements in a window experiences a notable boost in rate performance up to 80%. The ideal case, receiving tuples from a source and storing them directly for further processing in HBM can bene t the most from the higher bandwidth with up to a magnitude higher processing rates, which was quite surprising, though. However, it demonstrates the possible potential when algorithms get further enhanced and optimized for manycore CPUs with HBM support.
To summarize it up, the observations made with data stream processing on the KNL manycore architecture show that there is a huge gap in performance between operators with random and predictable memory access. Especially hash join operators show bad behavior and should ideally be replaced by join operators using more linear accessable data structures. Our future work will draw on these results, attending HBM characteristics for improved data structures and algorithms of database operations to maximize parallel performance.