Traditional Database Management Systems (DBMS) are designed to process a huge collection of data in rest. Queries are assumed to run once, deliver a single result set and then terminate immediately. This approach has been shown to be not suitable anymore to meet the requirements of new applications where high velocity data has to be processed continuously or complex operations are preformed on high volume data [ 1 ]. Real-time Stream Processing Systems (SPS) support high velocity and high volume [ 25 ] in combination with data flow graphs to achieve continuous computations over data streams in real-time. High throughput is achieved by distributed computing, parallelization, batching strategies and buffer management [ 1, 3, 21 ].

Research of the database community showed that the use of GPUs as co-processors are promising for data-intensive systems [ 14, 13 ]. Since a graphic card has a dedicated memory, each data to process has to be transferred from main memory to the graphic card memory and, after processing, vise versa. Since this transfer takes time, the transfer-cost might be a bottleneck for some applications [ 22 ]. A columnar DBMS is a suitable architecture for GPU acceleration, because it avoids transferring unneeded data (compared to a row store) and also favors data compression [ 5 ]. Since the content of a data stream changes rapidly, structured data-based SPSs process a stream of events as a stream of tuples [ 2, 3, 15, 21, 25 ]. Nevertheless, there is one fundamental bufferingtechnique called windowing that bounds a possible infinite data to finite portions. As stream-operators process a stream of windows either with a tuple-at-a-time or batch-at-a-time approach, we propose to focus on enabling efficient GPU accelerated operators for structured data in general and, hence, we address on-demand capabilities to convert regular lengthvariable windows into fixed-sized window portion-streams of columnar represented events.

In this paper, we address a strategy to enable this capability rather than a discussion of GPU-based operators itself. First, we show windowing in stream processing and graphic cards acceleration in DBMSs (Section 2). Afterwards, we continue with our main contributions: • We examine a concept that splits any stream of variablelength windows into a stream of fixed-size window portions with columnar representation (Section 3) • We identify open research challenges in context of coprocessor-ready stream processing (Section 4) We will finish with related work (Section 5) and our conclusion that sums up the paper’s content (Section 6). 2.

Motivated by the work of Karnagel et al., who showed a throughput increase for band join computations over streams using GPU acceleration [ 17 ], we believe that a generalpropose GPU-ready stream processing framework should be established. The reasons are (1) it enables a single system for regular row-oriented stream processing via CPU and efficient column-oriented stream processing via GPU and, hence, the load can be shared between both devices, (2) it allows us to run streaming applications on CPU, on GPU, or in mixed-mode and (3) it provides a further abstraction to achieve what should be done rather than how should it be done. Since time-based windows vary in length, it is not capable to send their contents directly to the GPU. Moreover, the current event presentation leads to memory usage overhead. To highlight these issues in more detail, we examine in the following stream processing and windowing as well as GPU acceleration in the context of DBMSs. 2.1

With the advent of general-purpose computing on graphics processing units (GPGPU), the usage of a GPU to solve arbitrary problems have become popular. Because of its high parallelism, a GPU can outperform a CPU by orders of magnitude. However, such performance improvements are only possible, if considering the special architecture of the GPU and its programming model. 2.1.1

Stream processing is a paradigm to continuously process, analyze and monitor a (possibly infinite) sequence of data, that is called a stream. Since traditional DBMSs assume data in-rest, exact results, queries initiated by humans and no realtime services for applications, they are not adequate for this task [ 1 ]. Therefore, around 2003, the database community researched adequate systems for stream processing. The academic projects Aurora and it’s fork Borealis are notable here, because they provide an innovative model to deal with data streams and provide well-engineered strategies for scheduling, load shedding, high availability, high performance, and dynamic query management capabilities [ 1 ].

Since stream processing is data-driven, a user defined query consumes streams and produces streams containing the results. Those queries are online until they are terminated manually. This is in contrast to traditional DBMS queries, which terminate after their execution automatically. Those queries over streams are a loosely coupled data-flow network of operators. 2.2.1

We introduce an operation that we call bucketing which transforms the output of windows such that they can efficiently consumed by GPU-based operators. To distinguish between what a stream-operator consumes, namely a window, we call what a GPU-operator consumes a bucket. We explore the differences in the following sub section. In contrast to windowinng l=ogick,*t,hese buckets are fixed-size in length independent from the window they listen to, such that we can pipe the woiffnd0ow content bucket by bucket to the GPU-based = 0 operators. Moreover, we will examine how to flip the event itemrepresentation from row to column and vise versa efficientUlys,ing relative a 1to avoid unnecessary transfer costs to the graphic card. if the newest tu position p, eac

We target fixed-sized bucketing of windows with a dedAif-terwards offs icteamted operator since this task should not be in the respontsoi-offset_i + siz b2ility of any GPU-based operator for several reasons, such as redundant logicomffi2ght occur otherwise. To show our strategy, we will introduce it step by step. We explore the differences to windowing first and show afterwards how buckets can be created efficiently. The latter approach is more general since we not address the representation-flipping here. How the transformaotffio1n between row- and column-orientation could be achieved is explained afterwards. k3.11 Motivation

Since SPSs are tuple-oriented, their primary data structure to express an entity’s content is a tuple. Although it is a common structure, it might not be efficient in terms of GPU data transfer cost and memory consumption. Consider for example a stream R with schema R = {A, B} where dom(A) = char(50) and dom(B) = int. R could contain a tuple (the, 268) for instance. Further assume a size of 54 bytes per tuple, where 4 bytes are used for the int data type. If an operation only requires B-values, sending entire tuples will waste ≈ 93% of data transfer time and graphic card memory. Therefore, we focus on flipping the event representation and bounding the size of windows to avoid out-of-memory situations when employing the graphic card. 3.2

Windowing is one of the fundamental concepts of stream processing. To be clear about where our proposed operator is different, we examine similiarities and differences of buckets and windows.

First of all, the purpose of both concepts is different. Window operators are used to bound a (infinite) stream of data to a collection of data, called a window, that can be processed by set-oriented operators. Hence, a window operator consumes a stream of events and produces a stream of windows. As mentioned earlier, the actual window length can vary depending on a given policy, such as in the time-based approach. In contrast, our operator consumes a stream of windows, each might vary in length, and partitions each window into portions of a user-defined size k. At the same time, the row-wise representation is changed to columnar representation. Each such portion is called a bucket.

Assume a stream R with schema R = {A, B} and consider the right hand side of Figure 1. As one can see, regular batching with a batch-size k = 3 contains at most tree tuples (a, b, c) ∈ R per batch entry, while a bucket of size three contains exactly |R| tuples each with most k components. These components per tuple are from the same domain, while the components of a window tuple are mixed-domains. Therefore, a bucket’s tuple t with components from a domain T can forwarded directly to GPU since t is, sloppy saying, an array of length k and type T . 3.3

Whereas windowing a continuous data stream leads to several strategies to match different policies, bucketing a window is relatively straightforward. At any time, during runtime or initialization, the subscribers S1, ..., Sm that request to consume buckets are known. Also their individual bucket sizes ki = size(Si) ∈ N+ are known. We receive a window ω of some size. Therefore, our task is to forward ω in portions of size ki to each Si until ω is completely consumed. We assume here w.l.o.g. that the bounds of each window are marked and that the length of each row-oriented tuple is fixed. 3.3.1

We showed how to achieve an efficient window splitting without changes in the event representation in the previous sub section. Now, we will utilize our approach to flip roworiented windows into a stream of column-oriented buckets.

Since the complexity of portioning any variable-length window is mainly driven by the actual window length, we suppose to utilize this concept for representation flipping.

The schema S = {A1, . . . , An} for the contents in a window is known. Hence, maintaining one circular buffer as in Section 3.3 for each attribute Ai ∈ S splits each incoming tuple into its components. We propose to use a bucketing-operator that is responsible for portioning the incoming windows such that it holds n circular buffers, each buffering one attribute of the incoming tuple. Since external subscribers S1, ..., S` are known to the bucketing-operator, the operator adds itself as ”internal” subscriber to each 1 ≤ j ≤ n circular buffers, delegates the desired sizei for each external Si to all buffers. This leads to notification of all circular buffers to the operator at the same time once sizei is achieved for some external subscriber Si. Now, the operator packages the n portions delivered to it into a collection, that is send to the external subscriber.

This allows a chain of operators where each consumes and produces a column-oriented event representation. To convert back to row-oriented event representation, another operator performs the described operations backwards. Hence, to revert the representation flip, another operator reads buckets and outputs them as a stream of regular tuples.

We propose to run these constructions in dedicated operators, since this allows sharing the costs of window portioning between several external subscribers and reverting the operation.

Based on existing research and related work, we cannot completely answer all relevant aspects. Therefore, we present two open research challenges in the following section. 4.1

We propose an additional bucketing-operator to support event representation changes and window portioning to target GPU-specialized counterparts of existing stream operators. On the other hand, current trends in hardware bring further co-processors (e.g., Intel Xeon Phi or FPGA) with special characteristics into view. Consequently, these co-processors could be used to accelerate stream processing in addition to the GPU. With the increasing amount of different devices, we have to take care of optimized algorithms and execution models for the respected processor to also reach optimized performance [ 7, 8 ]. An essential part is to tune a given operator to the used (co-)processor, because each processing device has its own set of optimizations that can be applied [ 9 ]. Furthermore, with the availability of different devices, we have to decide where to execute a given operator to reach optimal performance. Here, it is not only important to find the device with the best performance for the given operator, but also to distribute the load between the devices similar to the work of Breß et al. [ 6 ]. As far as we can see, further research should be investigated to find limitations and benefits for applied modern hardware in this context. 4.2

As proposed by Breß et al. [ 6 ], in the context of GPU acceleration for columnar databases, heterogeneous devices with dedicated memory are an opportunity since data transfer from one memory to another is optional. Utilizing OpenCL’s possibility to execute kernels on different devices, Karnagel et al. suggest to use a unified kernel and a load balancer that partitions the incoming data and distributes them either to the CPU or GPU depending on the load [ 18 ]. This load balancer contains a job queue and a dictionary that maps tasks to several states. OpenCL takes free jobs as soon as a device is available and deploys it to a specific device on its own. An interesting question is, how an advanced load balancer improves execution performance even further, if the targeted device runs a specialized kernel. This could be achieved with a more high-level load balancer that could decide on its own when to send jobs to device with an unified kernel, and when to to a dedicated device with highly optimized execution code that fits most to the device architecture. 5.

The design space of DBMSs using GPU as co-processor is well explored [ 5, 26 ] and already applied in many applications [ 4, 10, 13, 22 ]. He et al. present a novel design and implementation of relational join algorithms for GPUs by introducing a set of data-parallel primitives [ 14 ]. Stream processing could benefit from this research results in context of DBMSs, but first progress is made. Karnagel et al. show that a stream band-join might be computed faster with a speedup of nearly 70x using a graphic card [ 18 ]. For Complex Event Processing, an approach similar to stream processing, Cugola et al. suggest in 2012 to run the pattern detection automaton on parallelized hardware. They conclude that GPU acceleration can bring speedups in this context but also highlight limitations due to memory restrictions [ 12 ]. Hence, current approaches for GPU accelerated stream processing focus on specific topics; instead, we suggest an approach to enable GPU-ready stream processing in general. While we focus on a strategy to handle variable-length windows to enable GPU-operators over fixed-sized batches with a column-orientation (”buckets”), Karnagel et al. use a load balancer that mainly deploys band-join computation tasks to both CPU and GPU. Although these tasks also contain tuple-batches from the input sources, our approach has another focus since we do not actually address load balancing and construct batches outside the responsibility of a specific operator or balancer. Hence, we provide a stream of buckets, built from a stream of windows, that can be consumed by any operator. Bucket streams can be shared by different operators and can form an operator chain before the buckets are converted back to a regular tuple stream.

To enable GPU processing capabilities it is reasonable to process batches, since a GPU might outperform a CPU only if a bulk of data is present at once. Some SPSs do only support a tuple-at-a-time approach [ 15, 25 ] such that an internal buffering per operator is required. However, our approach enables those architectures to convert tuple-at-atime windows to bucket streams. Other SPSs such as Aurora offer batch-processing. Here, each operator stores its output in an output queue that is accessible by subscribers via pointers indicating the current ranges in-use. Aurora cleans up these queues, if a tailed range is not used by any subscriber anymore [ 1 ]. Since Aurora manages windowing with output queues, these queues vary as the window content and processing performance of subscriber vary. In contrast, our approach uses a fixed-sized circular buffer and performs window portioning and event representation changes rather than managing window states as Aurora.

In this paper we motivated and introduced a concept for a dedicated stream processing operator, the bucketing-operator, that consumes a stream of length-varying windows and produces a stream of fixed-sized window portions with a columnoriented event representation. We motivated the revertible event representation transposition to match the GPU architecture better, since a GPU uses the SIMD approach and otherwise we would waste memory and increase transfer costs. However, we suggest a strategy to perform bucketing using a fixed-sized circular buffer for each attribute of a given schema. This approach is efficient in time and space, since it mainly depends linearly on the actual window content length and could be stored in a predefined sized buffer per-attribute. We ensured here, that data corruption cannot occur using our construction.

Finally, we identified two research questions for processing data streams on modern hardware and scheduling for heterogeneous devices.

We thank Bernhard Seeger for fruitful discussions that heavily influenced this work.