In computer science, stream processing (also known as event stream processing, data stream processing, or distributed stream processing) is a programming paradigm that views streams, or sequences of events in time, as the central input and output objects of computation. Stream processing encompasses dataflow programming, reactive programming, and distributed data processing. Stream processing systems use streaming algorithms to trace parallel processing for data streams. The software stack for these systems includes components such as programming models and query languages, for expressing computation; stream management systems for distribution and scheduling; and hardware components for acceleration, including floating-point units, graphics processing units, and field-programmable gate arrays. The stream processing paradigm simplifies parallel software and hardware by restricting the kinds of parallel computation that can be performed. Given a sequence of data (a stream), a series of operations (kernel functions) is applied to each element in the stream. Kernel functions are usually pipelined, and efficient local on-chip memory reuse is attempted in order to minimize bandwidth loss associated with external memory interaction. Uniform streaming, in which a single kernel function is applied to all elements in the stream, is typical. Because the kernel and stream abstractions expose data dependencies, compiler tools can fully automate and optimize on-chip management tasks. Stream processing hardware can use techniques such as scoreboarding to initiate direct memory access (DMA) when dependencies are resolved. The elimination of manual DMA management reduces software complexity, while the reduced reliance on hardware cached I/O decreases the memory footprint required by specialized computational units such as arithmetic logic units. During the 1980s stream processing was explored within dataflow programming. One example is the language SISAL.
Applications Stream processing can be viewed as a compromise, driven by a data-centric model that works well for traditional DSP- or GPU-type applications (such as image, video and digital signal processing), but less well for general purpose processing with more randomized data access (such as databases). By sacrificing some flexibility in the model, this approach can enable easier, faster, and more efficient execution. Depending on the context, processor design can be tuned for maximum efficiency or for a trade-off with flexibility. Stream processing is especially suitable for applications that exhibit three characteristics:
Compute intensity, defined as the number of arithmetic operations per I/O or global memory reference. In many signal processing applications, this ratio is well over 50:1 and continues to increase with algorithmic complexity. Data parallelism, which exists in a kernel when the same function is applied to all records of an input stream, allowing multiple records to be processed simultaneously without waiting for results from previous records. Data locality, a form of temporal locality common in signal and media processing applications, in which data is produced once, read once or twice later in the application, and then not used again. Intermediate streams passed between kernels, as well as intermediate data within kernel functions, can capture this locality directly in the stream processing programming model. Examples of records within streams include:
In graphics, each record may consist of vertex, normal, and color information for a triangle. In image processing, each record may be a single pixel from an image. In a video encoder, each record may be 256 pixels, forming a macroblock of data. In wireless signal processing, each record could be a sequence of samples received from an antenna. For each record, processing is typically limited to reading from the input, performing operations on the data, and writing the result to the output. Multiple inputs and outputs are possible, but memory is not both read and written within the same application.
Code examples By way of illustration, the following code fragments demonstrate the detection of patterns within event streams. The first example shows the processing of a data stream using a continuous SQL query: an ongoing query that processes incoming data based on timestamps and window duration. This code fragment illustrates a JOIN of two data streams: one representing stock orders and the other representing the resulting stock trades. The query outputs a stream of all orders matched by a trade within one second of the order being placed. The output stream is sorted by timestamp; in this case, the timestamp originates from the orders stream.
Another sample code fragment detects weddings within a stream of external events, such as church bells ringing, the appearance of a man in a tuxedo or morning suit, a woman in a white gown, and rice being thrown. A "complex" or "composite" event is the high-level event inferred from these constituent events: in this case, that a wedding is occurring.
Comparison to prior parallel paradigms Early computers were based on a sequential execution paradigm. Traditional CPUs utilize a single instruction, single data (SISD) architecture, meaning they conceptually perform one operation at a time. As computing demands increased, the volume of data to be processed grew rapidly, exposing the limitations of sequential programming models. Various approaches were explored to enable large-scale computation, primarily by exploiting parallel execution. One major outcome of these efforts was single instruction, multiple data (SIMD), an architecture that allows a single instruction to operate on multiple data elements simultaneously. In general-purpose microprocessors, SIMD is frequently implemented via SIMD within a register (SWAR). By incorporating distinct execution structures for separate instruction streams, multiple instruction, multiple data (MIMD) parallelism can also be achieved. Although these paradigms are effective, physical hardware implementations face strict constraints, including memory alignment requirements, synchronization overhead, and limited scaling. Consequently, relatively few SIMD processors survived as stand-alone components; most have been integrated into general-purpose CPUs. A fundamental example of these paradigms is a program that adds two arrays, each containing 100 four-component vectors (totaling 400 numerical values).
… excerpt ends here. Continue reading the full article.
