Stream processing

Stream processing is essentially a compromise, driven by a data-centric model that works very well for traditional DSP or GPU-type applications (such as image, video and digital signal processing) but less so for general purpose processing with more randomized data access (such as databases). By sacrificing some flexibility in the model, the implications allow easier, faster and more efficient execution. Depending on the context, processor design may be tuned for maximum efficiency or a trade-off for flexibility.

Stream processing is especially suitable for applications that exhibit three application characteristics:

• Compute intensity, the number of arithmetic operations per I/O or global memory reference. In many signal processing applications today it is well over 50:1 and increasing with algorithmic complexity.
• Data parallelism exists in a kernel if the same function is applied to all records of an input stream and a number of records can be processed simultaneously without waiting for results from previous records.
• Data locality is a specific type of temporal locality common in signal and media processing applications where data is produced once, read once or twice later in the application, and never read again. Intermediate streams passed between kernels as well as intermediate data within kernel functions can capture this locality directly using the stream processing programming model.

Examples of records within streams include:

• In graphics, each record might be the vertex, normal, and color information for a triangle;
• In image processing, each record might be a single pixel from an image;
• In a video encoder, each record may be 256 pixels forming a macroblock of data; or
• In wireless signal processing, each record could be a sequence of samples received from an antenna.

For each record we can only read from the input, perform operations on it, and write to the output. It is permissible to have multiple inputs and multiple outputs, but never a piece of memory that is both readable and writable.

By way of illustration, the following code fragments demonstrate detection of patterns within event streams. The first is an example of processing a data stream using a continuous SQL query (a query that executes forever processing arriving data based on timestamps and window duration). This code fragment illustrates a JOIN of two data streams, one for stock orders, and one for 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 from the Orders stream.

SELECT DataStream
   Orders.TimeStamp, Orders.orderId, Orders.ticker,
   Orders.amount, Trade.amount
FROM Orders
JOIN Trades OVER (RANGE INTERVAL '1' SECOND FOLLOWING)
ON Orders.orderId = Trades.orderId;

Another sample code fragment detects weddings among a flow of external "events" such as church bells ringing, the appearance of a man in a tuxedo or morning suit, a woman in a flowing white gown and rice flying through the air. A "complex" or "composite" event is what one infers from the individual simple events: a wedding is happening.

WHEN Person.Gender EQUALS "man" AND Person.Clothes EQUALS "tuxedo"
FOLLOWED-BY
  Person.Clothes EQUALS "gown" AND
  (Church_Bell OR Rice_Flying)
WITHIN 2 hours
ACTION Wedding

Basic computers started from a sequential execution paradigm. Traditional CPUs are SISD based, which means they conceptually perform only one operation at a time. As the computing needs of the world evolved, the amount of data to be managed increased very quickly. It was obvious that the sequential programming model could not cope with the increased need for processing power. Various efforts have been spent on finding alternative ways to perform massive amounts of computations but the only solution was to exploit some level of parallel execution. The result of those efforts was SIMD, a programming paradigm which allowed applying one instruction to multiple instances of (different) data. Most of the time, SIMD was being used in a SWAR environment. By using more complicated structures, one could also have MIMD parallelism.

Although those two paradigms were efficient, real-world implementations were plagued with limitations from memory alignment problems to synchronization issues and limited parallelism. Only few SIMD processors survived as stand-alone components; most were embedded in standard CPUs.

Consider a simple program adding up two arrays containing 100 4-component vectors (i.e. 400 numbers in total).

for (int i = 0; i < 400; i++)
    result[i] = source0[i] + source1[i];

for (int el = 0; el < 100; el++) // for each vector
    vector_sum(result[el], source0[el], source1[el]);

// This is a fictional language for demonstration purposes.
elements = array streamElement([number, number])[100]
kernel = instance streamKernel("@arg0[@iter]")
result = kernel.invoke(elements)

Stanford University stream processing projects included the Stanford Real-Time Programmable Shading Project started in 1999.[7] A prototype called Imagine was developed in 2002.[8] A project called Merrimac ran until about 2004.[9] AT&T also researched stream-enhanced processors as graphics processing units rapidly evolved in both speed and functionality. Since these early days, dozens of stream processing languages have been developed, as well as specialized hardware.

 // A particle in a three-dimensional space.
struct particle_t {
    float x, y, z;          // not even an array!
    unsigned byte color[3]; // 8 bit per channel, say we care about RGB only
    float size;
    // ... and many other attributes may follow...
};

struct particle_t {
    float *x, *y, *z;
    unsigned byte *colorRed, *colorBlue, *colorGreen;
    float *size;
};

#include <raft>
#include <raftio>
#include <cstdlib>
#include <string>

class hi : public raft::kernel
{
public:
    hi() : raft::kernel()
    {
       output.addPort<std::string>("0"); 
    }

    virtual raft::kstatus run()
    {
        output["0"].push(std::string("Hello World\n"));
        return raft::stop; 
    }
};

int main(int argc, char **argv)
{
    /** instantiate print kernel **/
    raft::print< std::string > p;
    /** instantiate hello world kernel **/
    hi hello;
    /** make a map object **/
    raft::map m;
    /** add kernels to map, both hello and p are executed concurrently **/
    m += hello >> p;
    /** execute the map **/
    m.exe();
    return EXIT_SUCCESS;
}

• The Blitter in the Commodore Amiga is an early (circa 1985) graphics processor capable of combining three source streams of 16 component bit vectors in 256 ways to produce an output stream consisting of 16 component bit vectors. Total input stream bandwidth is up to 42 million bits per second. Output stream bandwidth is up to 28 million bits per second.
• Imagine,[10] headed by Professor William Dally of Stanford University, is a flexible architecture intended to be both fast and energy efficient. The project, originally conceived in 1996, included architecture, software tools, a VLSI implementation and a development board, was funded by DARPA, Intel and Texas Instruments.
• Another Stanford project, called Merrimac,[11] is aimed at developing a stream-based supercomputer. Merrimac intends to use a stream architecture and advanced interconnection networks to provide more performance per unit cost than cluster-based scientific computers built from the same technology.
• The Storm-1 family from Stream Processors, Inc, a commercial spin-off of Stanford's Imagine project, was announced during a feature presentation at ISSCC 2007. The family contains four members ranging from 30 GOPS to 220 16-bit GOPS (billions of operations per second), all fabricated at TSMC in a 130 nanometer process. The devices target the high end of the DSP market including video conferencing, multifunction printers and digital video surveillance equipment.
• GPUs are widespread, consumer-grade stream processors designed mainly by AMD and Nvidia. Various generations to be noted from a stream processing point of view:
  • Pre-R2xx/NV2x: no explicit support for stream processing. Kernel operations were hidden in the API and provided too little flexibility for general use.
  • R2xx/NV2x: kernel stream operations became explicitly under the programmer's control but only for vertex processing (fragments were still using old paradigms). No branching support severely hampered flexibility but some types of algorithms could be run (notably, low-precision fluid simulation).
  • R3xx/NV4x: flexible branching support although some limitations still exist on the number of operations to be executed and strict recursion depth, as well as array manipulation.
  • R8xx: Supports append/consume buffers and atomic operations. This generation is the state of the art.
• AMD FireStream brand name for product line targeting HPC
• Nvidia Tesla brand name for product line targeting HPC
• The Cell processor from STI, an alliance of Sony Computer Entertainment, Toshiba Corporation, and IBM, is a hardware architecture that can function like a stream processor with appropriate software support. It consists of a controlling processor, the PPE (Power Processing Element, an IBM PowerPC) and a set of SIMD coprocessors, called SPEs (Synergistic Processing Elements), each with independent program counters and instruction memory, in effect a MIMD machine. In the native programming model all DMA and program scheduling is left up to the programmer. The hardware provides a fast ring bus among the processors for local communication. Because the local memory for instructions and data is limited the only programs that can exploit this architecture effectively either require a tiny memory footprint or adhere to a stream programming model. With a suitable algorithm the performance of the Cell can rival that of pure stream processors, however this nearly always requires a complete redesign of algorithms and software.

Most programming languages for stream processors start with Java, C or C++ and add extensions which provide specific instructions to allow application developers to tag kernels and/or streams. This also applies to most shading languages, which can be considered stream programming languages to a certain degree.

Non-commercial examples of stream programming languages include:

• Ateji PX Free Edition, enables a simple expression of stream programming, the actor model, and the MapReduce algorithm on JVM
• Auto-Pipe, from the Stream Based Supercomputing Lab at Washington University in St. Louis, an application development environment for streaming applications that allows authoring of applications for heterogeneous systems (CPU, GPGPU, FPGA). Applications can be developed in any combination of C, C++, and Java for the CPU. Verilog or VHDL for FPGAs. Cuda is currently used for Nvidia GPGPUs. Auto-Pipe also handles coordination of TCP connections between multiple machines.
• ACOTES programming model: language from Polytechnic University of Catalonia based on OpenMP
• BeepBeep, a simple and lightweight Java-based event stream processing library from the Formal Computer Science Lab at Université du Québec à Chicoutimi
• Brook language from Stanford
• CAL Actor Language: a high-level programming language for writing (dataflow) actors, which are stateful operators that transform input streams of data objects (tokens) into output streams.
• Cal2Many a code generation framework from Halmstad University, Sweden. It takes CAL code as input and generates different target specific languages including sequential C, Chisel, parallel C targeting Epiphany architecture, ajava & astruct targeting Ambric architecture, etc..
• DUP language from Technical University of Munich and University of Denver
• HSTREAM: a directive-based language extension for heterogeneous stream computing[12]
• RaftLib - open source C++ stream processing template library originally from the Stream Based Supercomputing Lab at Washington University in St. Louis
• SPar - C++ domain-specific language for expressing stream parallelism from the Application Modelling Group (GMAP) at Pontifical Catholic University of Rio Grande do Sul
• Sh library from the University of Waterloo
• Shallows, an open source project
• S-Net coordination language from the University of Hertfordshire, which provides separation of coordination and algorithmic programming
• StreamIt from MIT
• Siddhi from WSO2
• WaveScript functional stream processing, also from MIT.
• Functional reactive programming could be considered stream processing in a broad sense.

Commercial implementations are either general purpose or tied to specific hardware by a vendor. Examples of general purpose languages include:

• AccelerEyes' Jacket, a commercialization of a GPU engine for MATLAB
• Ateji PX Java extension that enables a simple expression of stream programming, the Actor model, and the MapReduce algorithm
• Embiot, a lightweight embedded streaming analytics agent from Telchemy
• Floodgate, a stream processor provided with the Gamebryo game engine for PlayStation 3, Xbox360, Wii, and PC
• OpenHMPP, a "directive" vision of Many-Core programming
• PeakStream,[13] a spinout of the Brook project (acquired by Google in June 2007)
• IBM Spade - Stream Processing Application Declarative Engine (B. Gedik, et al. SPADE: the system S declarative stream processing engine. ACM SIGMOD 2008.)
• RapidMind, a commercialization of Sh (acquired by Intel in August 2009)
• TStreams,[14][15] Hewlett-Packard Cambridge Research Lab

Vendor-specific languages include:

• Brook+ (AMD hardware optimized implementation of Brook) from AMD/ATI
• CUDA (Compute Unified Device Architecture) from Nvidia
• Intel Ct - C for Throughput Computing
• StreamC from Stream Processors, Inc, a commercialization of the Imagine work at Stanford

Event-Based Processing

• Apama - a combined complex event and stream processing engine by Software AG
• Wallaroo
• WSO2 stream processor by WSO2
• Apache NiFi

Batch file-based processing (emulates some of actual stream processing, but much lower performance in general)

• Apache Kafka
• Apache Storm
• Apache Apex
• Apache Spark

Continuous operator stream processing

• Apache Flink
• Walmartlabs Mupd8[16]
• Eclipse Streamsheets - spreadsheet for stream processing

Stream processing services:

• Amazon Web Services - Kinesis
• Google Cloud - Dataflow
• Microsoft Azure - Stream analytics
• Datastreams - Data streaming analytics platform
• IBM streams
  • IBM streaming analytics
• Eventador SQLStreamBuilder