CN104317751B - Data flow processing system and its data flow processing method on a kind of GPU - Google Patents

Abstract

The invention discloses data flow processing system and its data flow processing method on a kind of GPU, belong to the technical field of Data Stream Processing on GPU, data flow processing system on a kind of GPU, the data flow of data source passes through data flow processing system to client, and data flow processing system includes CPU main frame and GPU equipment；CPU main frame includes CPU end and loads engine modules, CPU end buffer module, data flow pretreatment module, data flow Reduction of Students' Study Load module and visualization model；GPU equipment includes GPU end and loads engine modules, GPU end buffer module, data flow summary abstraction module, data Stream Processing Model storehouse data stream process module；CPU end loads the loading of engine modules or memory element passes through interacting of internet and data source, the loading of GPU end loading engine modules or memory element and client.The present invention has significant speed advantage, meets the real-time demand of High Dimensional Data Streams well, can be widely used in High Dimensional Data Streams excavation applications as general analysis method.

Description

A data stream processing system and data stream processing method on GPU

technical field

The present invention relates to the technical field of data flow processing on GPU, in particular to a data flow processing system on GPU and a data flow processing method thereof.

Background technique

GPU (Graphic Processing Unit), the Chinese translation is "graphics processing unit". The GPU is the "heart" of the graphics card, which is equivalent to the role of the CPU in the computer. The GPU has a fairly high memory bandwidth and a large number of execution units, which can help the CPU to perform some complex calculations, reducing the graphics card's dependence on the CPU.

Traditionally, the application of GPU is limited to processing graphics rendering computing tasks, which is undoubtedly a great waste of computing resources. With the continuous improvement of GPU programmability, the research on using GPU to complete general computing is gradually becoming active. Computing that uses GPUs for areas other than graphics rendering is called GPGPU (General-purpose computing on graphics processing units, GPU-based general computing). GPGPU computing usually adopts the CPU+GPU heterogeneous mode. The CPU is responsible for performing complex logic processing and transaction management and other calculations that are not suitable for data parallelism, and the GPU is responsible for computing-intensive large-scale data parallel computing. This computing method, which uses the powerful processing power of GPU and high bandwidth to make up for the lack of CPU performance, has significant advantages in terms of cost and cost performance in exploring the potential performance of computers. However, the traditional GPGPU is restricted by hardware programming and development methods, the application field is limited, and the development is very difficult.

In 2007, CUDA (Compute Unified Device Architecture, unified computing device architecture) launched by NVIDIA, this programming interface makes up for the shortcomings of traditional GPGPU. Using the CUDA programming interface, you can directly call GPU resources in C language without mapping them to graphics APIs, which removes obstacles for the popularization of GPU non-graphics programming.

The CUDA model uses the CPU as the host (Host), and the GPU as a co-processor (co-processor) or device (device), and the two work together. The CPU is responsible for logical transaction processing and serial computing, while the GPU focuses on executing highly threaded parallel processing tasks. The CPU and GPU each have independent memory address spaces: the host-side memory and the device-side video memory. Once the parallel calculation function (kernel) in the program is determined, consider handing over this part of the calculation to the GPU.

(Definition of data flow) A data flow is actually a continuously moving procession of elements, where elements are composed of collections of related data. Let t represent any time stamp, and at represent the data arriving at that time stamp, and stream data can be expressed as {..., at-1, at, at+1, ...}. Different from the traditional application model, the stream data model has the following 4 points of commonality: (1) The data arrives in real time; (2) The order of data arrival is independent and not controlled by the application system; (3) The data scale is huge and its maximum value cannot be predicted; (4) Once the data is processed, unless it is specially saved, Otherwise, it cannot be retrieved and processed again, or it is expensive to retrieve the data again.

At the same time, the stream appears in a double capacity: (1) exists as a program variable visible to the software. (2) It exists as a hardware-visible management unit. In practical applications, streams often have many attributes. When the stream is mapped to the hardware, these attributes are still maintained or changed to be seen by the hardware.

In data mining of the prior art, in order to eliminate erroneous data such as noise, null value and outlier value in the data, to guarantee the accuracy of the result, preprocessing operation is usually performed before mining the static data set in the database; of course, the data Various erroneous data cannot be avoided in the stream. In order to improve the accuracy of mining results, it is also necessary to preprocess them. However, data stream mining is generally carried out online, and data cannot be preprocessed before mining.

How is GPU parallel computing applied in the field of data stream mining? In an environment with limited computing resources, how to ensure the real-time and versatility of data flow processing?

Contents of the invention

The technical task of the present invention is to provide a data processing method on a GPU that has a significant speed advantage, satisfies the real-time requirements of high-dimensional data streams, and can be widely used as a general analysis method in the field of high-dimensional data stream mining. A stream processing system and a data stream processing method thereof.

Technical task of the present invention is realized in the following manner,

The output of the data source is a high-dimensional time series data stream. After being processed by the data stream processing system, the frequent pattern or query result of the data stream is output to the client.

A data flow processing system on a GPU, the data flow of data sources passes through the data flow processing system to the client (client), and the data flow processing system includes a CPU host (CPU-Host) and a GPU device (GPU-Device) ;

The CPU host includes CPU-Side Load Engine Area, CPU-Side Buffer Area, Data Stream Preprocessing Area, Data Stream Load Shedding Area) and visualization module (Visual Area), the CPU-side loading engine module is provided with a loading or storage unit (Load/Store Unit), the CPU-side buffer module is provided with a memory (MainMemory, MM), and the loading or storing of the CPU-side loading engine module The unit, the data stream preprocessing module, the data stream load reduction module and the visualization module all interact with the memory connection of the CPU-side buffer module, and the loading or storage unit of the CPU-side loading engine module connects and interacts with the visualization module;

GPU devices include GPU-Side Load Engine Area, GPU-Side Buffer Area, Data Stream Synopsis Extraction Area, Data Stream Processing Model Library (Data Stream Processing Model Library) and data stream processing module (Data Stream Processing Area), GPU-side loading engine module is provided with loading or storage unit (Load/Store Unit), GPU-side buffer module is provided with video memory (Device Memory, DM), data flow summary The extraction module is used to integrate the summary extraction method for the call of the data flow processing module, the data flow processing model library is used to integrate the data flow processing algorithm for the call of the data flow processing module, the loading or storage unit of the GPU-side loading engine module, and the data flow processing module are both Interact with the video memory connection of the GPU-side buffer module, the data stream summary extraction module, and the data stream processing model library are all connected to the loading or storage unit of the GPU-side loading engine module, and a storage space is opened in the video memory of the GPU-side buffer module as a sliding window;

The loading or storing unit of the CPU-side loading engine module interacts with the data source, the loading or storing unit of the GPU-side loading engine module, and the client through the Interconnection Network.

The CPU end buffer module is also provided with a memory manager for managing memory, and the memory manager is provided with an input monitor, which is used to monitor the unprocessed data streams temporarily stored in the memory; the CPU end load engine module includes a speed regulator ( Speed Regulator), loading or storage unit (Load/Store Unit) and initialization integrator (Initialization Integrator); the speed regulator is used to adjust the data flow of the data source to flow into the loading or storage unit of the CPU-side loading engine module according to the cache state of the memory The speed regulator is equipped with a feedback mechanism (Feedback Mechanism); the initialization integrator is used to integrate the initialization operation of the CPU host and GPU device.

A data stream processing method on the GPU, in which the data stream output by the data source is processed by the data stream processing system and the data result is transmitted to the client; the data stream processing flow is as follows:

(1), loading data stream: the data stream in the data source flows into the loading or storage unit of the CPU-side loading engine module, and the loading or storage unit of the CPU-side loading engine module stores the data stream into the memory of the CPU-side buffer module;

(2), data stream preprocessing: the data stream preprocessing module preprocesses the original data stream in the memory, and stores the preprocessed data stream into the memory;

(3) Transmission data stream: the preprocessed data stream is sent from the memory to the loading or storage unit of the CPU-side loading engine module, from the loading or storage unit of the CPU-side loading engine module to the Internet, and through the Internet to the GPU side for loading The loading or storage unit of the engine module is loaded into the sliding window of the video memory by the loading or storage unit of the engine module on the GPU side;

(4), data flow summary extraction: call the summary extraction method in the data flow summary extraction module by the data flow processing module, carry out summary extraction to the data flow in the sliding window, and store the final summary data structure in the display memory;

(5), data flow processing: the data flow processing algorithm in the data flow processing model library is invoked by the data flow processing module to process the summary data, and store the processed data results in the video memory;

(6) Transmission of data results: the data results are sent from the video memory of the GPU-side buffer module to the loading or storage unit of the GPU-side loading engine module, sent to the Internet by the loading or storage unit of the GPU-side loading engine module, and then reach the CPU via the Internet The load or storage unit of the load engine module on the CPU side loads the data result into the memory by the load or storage unit of the load engine module on the CPU side, or sends the data result to the visualization module by the load or storage unit of the load engine module on the CPU side;

(7) Result visualization: the visualization module normalizes the data results and sends them to the loading or storage unit of the CPU-side loading engine module, and the loading or storage unit of the CPU-side loading engine module displays the data results to the client.

A data stream processing method on a GPU, in step (2), the data stream preprocessing module preprocesses the original data stream in the memory using a preprocessing method, and the preprocessing method includes a data cleaning method, a data integration method, and a data transformation method As with the data reduction method, the preprocessing method used can be one of the above methods, or a combination of multiple methods can be selected.

(1) Data cleaning method: filling missing values, smoothing noise data, removing outliers and solving data inconsistencies; data cleaning is a very important process in data preprocessing, but it is also the most time-consuming process; missing values, noise and inconsistency All will lead to inaccurate data, and data cleaning can effectively avoid this situation;

(2) Data integration method: pattern integration and object matching, removal of redundant data, detection and processing of data value conflicts; data integration refers to the integration of data originally stored in multiple data sources to form a data source, and to Centralized storage in a unified format to facilitate subsequent data processing;

3. Data transformation methods: data smoothing, data aggregation, data generalization, data normalization and attribute construction; data transformation is to convert data into a form suitable for data mining; for example, the dimensions between data items may be inconsistent, then it is necessary Reduce the dimensions of high-dimensional data items to reduce the differences between them and facilitate processing;

(iv) Data reduction methods: data cube aggregation, attribute subset selection, dimension reduction, numerical reduction, discretization, and concept hierarchy; data reduction is also known as data reduction technology.

A method for processing data streams on a GPU. After step (2), when the data stream is overloaded, the data stream is subjected to load reduction processing through a data stream load reduction module. The specific steps are:

Ⅰ. The input monitor of the memory manager of the CPU side buffer module monitors the temporary storage of unprocessed data streams in the memory, and determines whether the volume of the new data stream exceeds the data stream processing module of the GPU device within a time unit. processing capacity;

Ⅱ. If the data stream processing module of the GPU device can handle all the data streams, then transmit the data stream; if the volume of the new data stream exceeds the processing capacity of the data stream processing module of the GPU device, that is, the data stream is overloaded, then Transfer the data flow to the data flow offloading module;

Ⅲ. The data stream load reduction module performs load reduction processing on the data stream;

Ⅳ. The data stream load reduction module transfers the remaining data streams into the memory for the next step of transmitting data streams.

A method for processing data streams on a GPU, wherein the data stream offloading module adopts one or more combinations of the following strategies for offloading the data streams:

i. Data-based discarding: among the received and unprocessed data in the time series data stream, find the data with the longest length and discard them;

ⅱ. Attribute-based trimming: each data in the data stream has d attributes, and among the data, remove the attribute with the lowest frequency, so as to trim the attributes of the data;

ⅲ. Priority-based discarding: Each new incoming data stream is assigned a priority, among the received and unprocessed data streams, select those with the lowest priority and discard them. Each of the three strategies has its own purpose; the data-based discarding strategy discards the long data that the system takes a lot of time to process, and tries to reduce the system load as quickly as possible, which is efficiency-oriented; the attribute-based trimming strategy , the least frequent attributes that have no significant impact on the processing results are deleted from the data; the priority-based discarding strategy deletes the data with the lowest priority from the data; in comparison, the latter Both strategies are precision-oriented because they try to preserve high-precision mining results.

A data flow processing method on the GPU. The video memory uses the global memory (Global Memory) to store various data (such as summary data, intermediate data, result data, etc.), and the sliding window (Sliding Window, SW) opened in the video memory is used. The data flow from the CPU host to the GPU device is saved (due to the infinite data flow and the limited storage space, in order to reduce the data copy between the memory and the video memory and obtain more effective mining results, a part of the space is divided in the video memory as Sliding window temporarily stores data), the sliding window uses a sliding window defined based on the number of tuples, that is, a sliding window with a fixed window size, which is used to save the recently arrived K data streams;

The data flow processing method of the sliding window uses the rewritable loop sliding window method. When updating, the new data directly covers the data to be expired, and a format transformation function is provided to maintain the logical format state of the data in the sliding window.

A method for processing data streams on a GPU. The data stream summary in step (4) is extracted, and the data stream is obtained by a summary data structure through the summary extraction method. The summary extraction method includes sampling (Sampling) method, wavelet (Wavelet) method, sketch (Sketch) ) method and histogram method. Compress the data stream and construct a data structure much smaller than the data size of the entire data stream to save the main characteristics of the data stream, which is called a summary data structure. The approximate value obtained through the summary data structure is within the acceptable range of users within.

A data stream processing method on the GPU. The data stream processing model library integrates various data stream processing algorithms during data stream processing, including query processing algorithms, clustering algorithms, and classification algorithms. ), frequent itemsets mining algorithm (frequent itemsets mining algorithm) and correlation analysis algorithm between multiple data streams (correlation analysis algorithm).

A data stream processing method on the GPU, the task of the data stream processing module is to call the summary extraction method of the data stream summary extraction module to extract the summary data from the data stream, and to call the data stream processing algorithm in the data stream processing model library to extract the summary data Parallel computing; the data stream processing module includes a data stream input assembler (Data Stream Input Assembler), a global thread block scheduler (Global Block Scheduler) and a computing array (Compute Array), and a shared memory, loading or storage unit is set in the computing array; The data stream input assembler is responsible for reading the data in the video memory into the shared memory of the data stream processing module. The global thread block scheduler is responsible for scheduling and allocating the thread blocks, threads and instructions in the shared memory. The computing array is used for thread The calculation of the calculation; the load or storage unit in the calculation array loads data from the video memory to the shared memory during calculation.

A data stream processing system and a data stream processing method thereof on a GPU of the present invention have the following advantages:

1. Versatility: The previous data stream processing system using GPU acceleration was limited to a certain task during data stream processing, either clustering, classification or others; however, the data stream processing system of the present invention is suitable for Multiple high-dimensional time series data streams in various application fields, which cover multiple functions such as data stream preprocessing, load reduction, summary extraction, and mining processing. The data stream processing model library included in the GPU device part integrates various data streams. Stream processing algorithms, such as query processing algorithms, clustering algorithms, classification algorithms, frequent itemset mining algorithms, and correlation analysis algorithms, can complete multiple tasks during data stream processing, thereby endowing the present invention with versatility;

2. Efficiency: The summary extraction method of the present invention and the parallel parts of all data flow processing algorithms are accelerated by GPU, which makes full use of the powerful processing capability and pipeline characteristics of GPU, and further improves the execution efficiency;

3. Control of additional I/O overhead: In the data stream processing system, the sliding window is opened in the video memory, so that the frequent copying of data between the memory and the video memory is avoided when the data stream summary is extracted; in addition, when performing the summary When extracting and data stream processing, video memory is used, which greatly reduces the number of times to read and write data from memory;

4. Because the initial data flow is too large, if the data stream is directly sent to the GPU device for data stream preprocessing, the I/O overhead will be greatly increased. Therefore, the present invention designs the data stream preprocessing process in the data stream of the CPU host. In the stream preprocessing module, data stream preprocessing is performed to eliminate error data such as noise, null values, and abnormal values in the data, and reduce I/O overhead;

5. In the prior art, when the sliding window is not full, new data directly fills the window. When the window is full, as the window slides, new data entering the window will cause other data already in the window to move forward, covering The previous data; yet, the sliding window method of the rewritable cycle that the present invention adopts does not need to move data at the full stage of the sliding window, it directly covers (rewrites) the data to be expired with new data, and provides The pattern transformation function is used to maintain the logical pattern state of the data in the sliding window, which saves a lot of time.

Description of drawings

The present invention will be further described below in conjunction with the accompanying drawings.

Accompanying drawing 1 is a frame diagram of a data stream processing system on a GPU.

detailed description

A data stream processing system on a GPU and a data stream processing method thereof according to the present invention will be described in detail below with reference to the accompanying drawings and specific embodiments.

Example 1:

In the data flow processing system on a GPU of the present invention, the data flow of data sources (data sources) passes through the data flow processing system to the client (client), and the data flow processing system includes a CPU host (CPU-Host) and a GPU device (GPU -Device);

The CPU host includes CPU-Side Load Engine Area, CPU-Side Buffer Area, Data Stream Preprocessing Area, Data Stream Load Shedding Area) and visualization module (Visual Area), the CPU-side loading engine module is provided with a loading or storage unit (Load/Store Unit), the CPU-side buffer module is provided with a memory (MainMemory, MM), and the loading or storing of the CPU-side loading engine module The unit, the data stream preprocessing module, the data stream load reduction module and the visualization module all interact with the memory connection of the CPU-side buffer module, and the loading or storage unit of the CPU-side loading engine module connects and interacts with the visualization module;

GPU devices include GPU-Side Load Engine Area, GPU-Side Buffer Area, Data Stream Synopsis Extraction Area, Data Stream Processing Model Library (Data Stream Processing Model Library) and data stream processing module (Data Stream Processing Area), GPU-side loading engine module is provided with loading or storage unit (Load/Store Unit), GPU-side buffer module is provided with video memory (Device Memory, DM), data flow summary The extraction module is used to integrate the summary extraction method for the call of the data flow processing module, the data flow processing model library is used to integrate the data flow processing algorithm for the call of the data flow processing module, the loading or storage unit of the GPU-side loading engine module, and the data flow processing module are both Interact with the video memory connection of the GPU-side buffer module, the data stream summary extraction module, and the data stream processing model library are all connected to the loading or storage unit of the GPU-side loading engine module, and a storage space is opened in the video memory of the GPU-side buffer module as a sliding window;

The loading or storing unit of the CPU-side loading engine module interacts with the data source, the loading or storing unit of the GPU-side loading engine module, and the client through the Interconnection Network.

The CPU end buffer module is also provided with a memory manager for managing memory, and the memory manager is provided with an input monitor, which is used to monitor the unprocessed data streams temporarily stored in the memory; the CPU end load engine module includes a speed regulator ( Speed Regulator), loading or storage unit (Load/Store Unit) and initialization integrator (Initialization Integrator); the speed regulator is used to adjust the data flow of the data source to flow into the loading or storage unit of the CPU-side loading engine module according to the cache state of the memory The speed regulator is equipped with a feedback mechanism (Feedback Mechanism); the initialization integrator is used to integrate the initialization operation of the CPU host and GPU device.

Example 2:

In the data stream processing method on a GPU of the present invention, the data stream output by the data source is processed by the data stream processing system and the data result is transmitted to the client; the processing flow of the data stream is as follows:

(1) Loading data flow: the data flow in the data source flows into the loading or storage unit of the CPU-side loading engine module (the data flow direction is shown in Figure 1 in ①), and the loading or storage unit of the CPU-side loading engine module will The data stream is stored in the memory of the buffer module on the CPU side (the data stream flow is shown in Figure 1 as shown in ②);

(2), data stream preprocessing: the data stream preprocessing module preprocesses the original data stream in the memory (the data stream flows as shown in ③ in Figure 1), and stores the preprocessed data stream into the memory (data The flow direction is shown as ④ in Fig. 1);

(3) Transmission data stream: the preprocessed data stream is loaded from the memory to the loading or storage unit of the CPU-side loading engine module (the data flow direction is shown in Figure 1 as ⑦), and is loaded or stored by the CPU-side loading engine module The unit goes to the Internet (the data flow direction is shown in Figure 1 as ⑧), and through the Internet, it reaches the loading or storage unit of the GPU-side loading engine module (the data flow direction is shown in Figure 1 as ⑨), and then the GPU-side loads the engine The loading or storage unit of the module loads it into the sliding window of the video memory (the data flow direction is shown in Figure 1 as shown in ⑩);

(4), data flow summary extraction: call the summary extraction method in the data flow summary extraction module by the data flow processing module, carry out summary extraction to the data flow in the sliding window (data flow flow direction as shown in Figure 1), and The final summary data structure is stored in the video memory (the data flow direction is shown in Figure 1);

(5), data flow processing: the data flow processing algorithm in the data flow processing model library is invoked by the data flow processing module to process the summary data (the flow direction of the data flow is shown in Figure 1), and the processed data results are stored in In video memory (data flow direction is shown in Figure 1);

(6), transfer data result: the data result is loaded or stored by the video memory of the GPU-side buffer module to the loading or storage unit of the GPU-side loading engine module (the data flow direction is shown in Figure 1), and is loaded or stored by the GPU-side loading engine module The unit is sent to the Internet (the data flow direction is shown in Figure 1), and then reaches the loading or storage unit of the CPU-side loading engine module through the Internet (the data flow direction is shown in Figure 1), and then the CPU-side loads the engine module The load or store unit of the load or store unit loads the data result into the memory (the flow of data flow is shown in Figure 1), or the load or store unit of the load engine module on the CPU side sends the data result to the visualization module (the flow of data flow is shown in Figure 1 shown in);

(7) Result visualization: the visualization module normalizes the data results and sends them to the loading or storage unit of the CPU-side loading engine module (the data flow direction is shown in Figure 1), and the loading or storage unit of the CPU-side loading engine module will The data result is displayed to the client (the data flow direction is shown as 2○1 in Figure 1).

Example 3:

In the data stream processing method on a GPU of the present invention, the data stream output by the data source is processed by the data stream processing system and the data result is transmitted to the client; the processing flow of the data stream is as follows:

(1) Loading data flow: the data flow in the data source flows into the loading or storage unit of the CPU-side loading engine module (the data flow direction is shown in Figure 1 in ①), and the loading or storage unit of the CPU-side loading engine module will The data stream is stored in the memory of the buffer module on the CPU side (the data stream flow is shown in Figure 1 as shown in ②);

(2), data stream preprocessing: the data stream preprocessing module preprocesses the original data stream in the memory (the data stream flows as shown in ③ in Figure 1), and stores the preprocessed data stream into the memory (data The flow direction is shown as ④ in Fig. 1);

(3) Transmission data stream: the preprocessed data stream is loaded from the memory to the loading or storage unit of the CPU-side loading engine module (the data flow direction is shown in Figure 1 as ⑦), and is loaded or stored by the CPU-side loading engine module The unit goes to the Internet (the data flow direction is shown in Figure 1 as ⑧), and through the Internet, it reaches the loading or storage unit of the GPU-side loading engine module (the data flow direction is shown in Figure 1 as ⑨), and then the GPU-side loads the engine The loading or storage unit of the module loads it into the sliding window of the video memory (the data flow direction is shown in Figure 1 as shown in ⑩);

(4), data flow summary extraction: call the summary extraction method in the data flow summary extraction module by the data flow processing module, carry out summary extraction to the data flow in the sliding window (data flow flow direction as shown in Figure 1), and The final summary data structure is stored in the video memory (the data flow direction is shown in Figure 1);

(5), data flow processing: the data flow processing algorithm in the data flow processing model library is invoked by the data flow processing module to process the summary data (the flow direction of the data flow is shown in Figure 1), and the processed data results are stored in In video memory (data flow direction is shown in Figure 1);

(6), transfer data result: the data result is loaded or stored by the video memory of the GPU-side buffer module to the loading or storage unit of the GPU-side loading engine module (the data flow direction is shown in Figure 1), and is loaded or stored by the GPU-side loading engine module The unit is sent to the Internet (the data flow direction is shown in Figure 1), and then reaches the loading or storage unit of the CPU-side loading engine module through the Internet (the data flow direction is shown in Figure 1), and then the CPU-side loads the engine module The load or store unit of the load or store unit loads the data result into the memory (the flow of data flow is shown in Figure 1), or the load or store unit of the load engine module on the CPU side sends the data result to the visualization module (the flow of data flow is shown in Figure 1 shown in);

(7) Result visualization: the visualization module normalizes the data results and sends them to the loading or storage unit of the CPU-side loading engine module (the data flow direction is shown in Figure 1), and the loading or storage unit of the CPU-side loading engine module will The data result is displayed to the client (the data flow direction is shown as 2○1 in Figure 1).

In step (2), the data stream preprocessing module preprocesses the original data stream in the memory using a preprocessing method. The preprocessing method includes a data cleaning method, a data integration method, a data transformation method, and a data reduction method. The preprocessing method used The method can be one of the above methods, or a combination of several methods can be selected.

(1) Data cleaning method: filling missing values, smoothing noise data, removing outliers and solving data inconsistencies; data cleaning is a very important process in data preprocessing, but it is also the most time-consuming process; missing values, noise and inconsistency All will lead to inaccurate data, and data cleaning can effectively avoid this situation;

(2) Data integration method: pattern integration and object matching, removal of redundant data, detection and processing of data value conflicts; data integration refers to the integration of data originally stored in multiple data sources to form a data source, and to Centralized storage in a unified format to facilitate subsequent data processing;

3. Data transformation methods: data smoothing, data aggregation, data generalization, data normalization and attribute construction; data transformation is to convert data into a form suitable for data mining; for example, the dimensions between data items may be inconsistent, then it is necessary Reduce the dimensions of high-dimensional data items to reduce the differences between them and facilitate processing;

(iv) Data reduction methods: data cube aggregation, attribute subset selection, dimension reduction, numerical reduction, discretization, and concept hierarchy; data reduction is also known as data reduction technology.

After step (2), when the data flow is overloaded, the data flow is offloaded through the data flow offloading module. The specific steps are:

Ⅰ. The input monitor of the memory manager of the CPU side buffer module monitors the temporary storage of unprocessed data streams in the memory, and determines whether the volume of the new data stream exceeds the data stream processing module of the GPU device within a time unit. processing capacity;

Ⅱ. If the data stream processing module of the GPU device can handle all the data streams, then transmit the data stream; if the volume of the new data stream exceeds the processing capacity of the data stream processing module of the GPU device, that is, the data stream is overloaded, then Transfer the data flow to the data flow load reduction module (the data flow direction is shown as ⑤ in Figure 1);

Ⅲ. The data stream load reduction module performs load reduction processing on the data stream;

IV. The data stream offloading module transfers the remaining data streams into the memory (the data stream flow direction is shown as ⑥ in FIG. 1 ), and transmits the data stream in the next step.

The data stream offloading module adopts one or more combinations of the following strategies to offload the data stream:

i. Data-based discarding: among the received and unprocessed data in the time series data stream, find the data with the longest length and discard them;

ⅱ. Attribute-based trimming: Each data in the data stream has an attribute. In the data, the attribute with the lowest frequency is removed, so as to trim the attribute of the data;

ⅲ. Priority-based discarding: Each new incoming data stream is assigned a priority, among the received and unprocessed data streams, select those with the lowest priority and discard them. Each of the three strategies has its own purpose; the data-based discarding strategy discards the long data that the system takes a lot of time to process, and tries to reduce the system load as quickly as possible, which is efficiency-oriented; the attribute-based trimming strategy , the least frequent attributes that have no significant impact on the processing results are deleted from the data; the priority-based discarding strategy deletes the data with the lowest priority from the data; in comparison, the latter Both strategies are precision-oriented because they try to preserve high-precision mining results.

The video memory uses the global memory (Global Memory) to store various data (such as summary data, intermediate data, result data, etc.), and the sliding window (Sliding Window, SW) opened in the video memory is used to transfer the data flow from the CPU host to the GPU device Save it (due to the infinite data flow and the limited storage space, in order to reduce the data copy between the memory and the video memory and obtain more effective mining results, a part of the space in the video memory is divided as a sliding window to temporarily store data), sliding window Use a sliding window defined based on the number of tuples, that is, a sliding window with a fixed window size, which is used to save the recently arrived K data streams;

The data flow processing method of the sliding window uses the rewritable loop sliding window method. When updating, the new data directly covers the data to be expired, and a format transformation function is provided to maintain the logical format state of the data in the sliding window.

The data stream summary extraction in step (4) is to obtain the summary data structure through the data flow through the summary extraction method, the summary extraction method includes sampling (Sampling) method, wavelet (Wavelet) method, sketch (Sketch) method and histogram (Histogram) method . Compress the data stream and construct a data structure much smaller than the data size of the entire data stream to save the main characteristics of the data stream, which is called a summary data structure. The approximate value obtained through the summary data structure is within the acceptable range of users within.

The data stream processing model library integrates various data stream processing algorithms in data stream processing, including query processing algorithm (query processing algorithm), clustering algorithm (clustering algorithm), classification algorithm (classification algorithm), frequent itemset mining algorithm ( frequent itemsets mining algorithm) and correlation analysis algorithm between multiple data streams (correlation analysis algorithm).

The task of the data flow processing module is to call the summary extraction method of the data flow summary extraction module to extract the summary of the data flow, and to call the data flow processing algorithm in the data flow processing model library to perform parallel calculation on the summary data; the data flow processing module includes data Stream input assembler (Data Stream Input Assembler), global thread block scheduler (Global Block Scheduler) and computing array (Compute Array), the computing array is set with shared memory, loading or storage unit; data stream input assembler is responsible for the video memory The data in the data flow processing module is read into the shared memory of the data flow processing module. The global thread block scheduler is responsible for scheduling and allocating the thread blocks, threads and instructions in the shared memory. The computing array is used for the calculation of threads; the loading in the computing array Or the storage unit loads data from the video memory to the shared memory during calculation.

In the data stream processing system, the data stream is processed, and the processing steps at the CPU host side are as follows:

1. Start CUDA (abbreviation for data stream processing system);

2. Allocate MM (memory) for the input data;

3. The CPU-side loading engine module obtains input data from the data source and initializes it;

4. The data stream preprocessing module performs preprocessing such as data cleaning and integration on the input data stream;

5. When the system is overloaded, the data stream load reduction module performs load reduction processing on the data stream;

6. Allocate a sliding window of video memory for the GPU device to store input data;

7. The initialization integrator initializes the summary extraction method and data flow processing algorithm;

8. Copy the data in the memory to the sliding window of the video memory;

9. Allocate video memory for the GPU device to store the summary data extracted by the data stream processing module;

10. Call the parallel calculation function (kernel) of the data stream processing algorithm on the GPU device side to perform parallel calculations, obtain summary data, and write it to the corresponding area in the video memory;

11. Allocate video memory for the GPU device to store the returned output data;

12. Read back the results in the video memory to the memory;

13. Use the visualization module to perform subsequent processing on the data, such as normalization, visualization, etc.;

14. Release memory and video memory space;

15. Quit CUDA.

The processing steps on the GPU device side are as follows:

1. Allocate shared memory (Shared Memory);

2. Read the data in the global memory of the video memory into the shared memory;

3. Perform calculations and write the results to the shared memory;

4. Write the result in the shared memory to the global memory.

The following introduces the code of each module in the data stream processing system:

1. Initialize the various function codes of the integrator:

First, start and exit the data stream processing system (CUDA for short) environment:

CUT_DEVICE_INIT(argc,argv);//Start CUDA

CUT_EXIT(argc,argv);//Exit CUDA;

Next, allocate memory and video memory:

Allocate memory on the CPU host, h_ indicates the CPU host side, i indicates input, o indicates output, mem_size indicates the memory size allocated for data,

float*h_idata=(float*)malloc(mem_size);

float*h_odata=(float*)malloc(mem_size);

Allocate video memory on the GPU device, d_ indicates the GPU device side,

float*d_idata; CUDA_SAFE_CALL(cudaMalloc((void**)&d_idata, mem_size));

float*d_odata; CUDA_SAFE_CALL(cudaMalloc((void**)&d_odata, mem_size));

Next, task division, that is, the dimension design of two-dimensional grid and block:

dim3grid(gridDim.x,gridDim.y,1);//The third dimension is always 1;

dim3block(blockDim.x, blockDim.y, 1);//The third dimension may not be 1, because the block is two-dimensional, so it is set to 1;

testKernel<<<grid,block>>>(d_idata,d_odata);//Call the kernel function for parallel computing;

Then, data copy between memory and video memory:

Read the value in memory into video memory,

CUDA_SAFE_CALL(cudaMemcpy(d_idata,h_idata,mem_size,cudaMemcpyHostToDevice));

Write the result from video memory to memory,

CUDA_SAFE_CALL(cudaMemcpy(h_odata, d_odata, mem_size, cudaMemcpyDeviceToHost));

The following code is used to release the storage space of memory and video memory.

free(h_idata);//release memory;

free(h_odata);

CUDA_SAFE_CALL(cudaFree(d_idata));//Release video memory;

CUDA_SAFE_CALL(cudaFree(d_odata));

In addition to the functions mentioned above, the initialization integrator also selects the data stream processing algorithm (specifically to a certain algorithm in a certain type of algorithm), selects the summary extraction method, and initializes various data stream processing algorithms and summary extraction methods (such as Haar Wavelet is to obtain the number of decomposition layers when performing a complete decomposition, and k-means is the function of initializing the cluster center point).

2. The formal expression of the sliding window is: CircularSW=<w, num, front, fun>;

Among them, w is the width of the sliding window (SW); num is the data volume of the data stream in the current sliding window; front is the mark of the end data in the sliding window, and the newly arrived data is placed in this position; fun is the pattern transformation of the sliding window function, which determines the pattern change of the existing data in the sliding window when new data arrives. The definition of fun is shown in Table 1 below:

Table 1. Pattern transformation function of rewritable circular sliding window

The novelty of the rewritable circular sliding window is that it directly calculates the position of expired data (to be removed from the data), and the newly arrived data is placed in this position, directly covering the original data in the window. The front value needs to be modified so that it points to the end of the data in the window, that is, the front always points to new data. Compared with the previous sliding window, the rewritable circular sliding window can improve the efficiency of the data flow processing system. It uses the same storage space, avoids the movement of data in the window, and allows finer-grained concurrency control.

3. In order to improve the processing efficiency, the summary extraction methods all need GPU acceleration, such as the wavelet decomposition in the wavelet method, the hash map in the sketch method, etc. In the following, Haar wavelet (Haar Wavelet) in the wavelet method is taken as an example to introduce in detail. The wavelet method is an important data compression method. By performing wavelet transformation on the original data set and saving some important wavelet coefficients, the original data set can be restored approximately. Haar Wavelet is the simplest type of wavelet. A two-dimensional or three-dimensional (2D or 3D) wavelet transform can be decomposed into two or three one-dimensional (1D) wavelet transforms. One-dimensional HaarWavelet decomposition is to transform the vector into wavelet coefficients. Table 2 demonstrates the Haar Wavelet transform of this sequence.

Table 2 Haar Wavelet transform of sequence X

The specific calculation is as follows: For the hierarchy in the Resolution column, the original sequence is in the Averages column. Calculate the mean value of the original sequence data in pairs to obtain the Averages in the hierarchy;

Obviously, in the process of finding the Averages, we lost some information in the original sequence. The original sequence cannot be reconstructed by the average value alone. The average value is only an approximation. Therefore, in order to reconstruct the original data, we also need to save the detail coefficients. That is, the difference between the average value of each pair of data and the second data is stored in the Detail Coefficients column;

Go on in turn. The wavelet coefficients of this sequence consist of the mean value of layer 0 and all detail coefficients.

Taking the one-dimensional Haar wavelet transform as an example, the core code of the GPU device is given as follows:

4. The k-means algorithm of the clustering algorithm in the data stream processing algorithm:

The k-means algorithm is the most representative clustering algorithm. Its main purpose is to divide the sample data with the same data type according to the shortest distance rule, and finally obtain the equivalence classes. In this paper, distance is used to represent the similarity between data. However, due to the particularity of data streams, traditional clustering algorithms are difficult to implement on data streams, so we use Haar wavelet as an example to perform summary extraction in the data stream processing model library. Based on this wavelet summary, approximate distances between data streams and cluster centers can be quickly calculated. In this way, the k-means algorithm is much easier to implement.

In clustering, Euclidean distance (that is, Euclidean distance) has a very intuitive meaning.

The distance between a data item and a data set is defined as the minimum distance between the data item and all data items in the data set.

This problem corresponds to a computationally intensive task (that is, solving a large number of "distances"), so there is not much room for optimization in the algorithm. And making a fuss about "enhanced parallelism" will undoubtedly bring significant acceleration effects, because the calculations between different distances are completely independent. It can be said that this is a task occasion where the GPU has an absolute advantage.

The dimensionality of each data item in a high-dimensional data stream is usually very high, so we use a custom matrix to store data during implementation. When clustering, the GPU needs to frequently calculate the transposition of the matrix, the sum of the squares of the distances between data items and other extremely time-consuming operations. The core code of the device-side k-means algorithm is as follows. Among them, each thread corresponds to a distance.

5. The thread grid (Grid), thread block (Block) and thread (Thread) in the computing array are respectively loaded into the stream processor array (SPA), stream multiprocessor (SM) and stream processor ( SP). Data is exchanged between thread grids through video memory, and each thread block is executed in parallel and cannot communicate with each other, but can only share data through video memory; threads in the same thread block can communicate through shared memory (Shared Memory) and synchronization.

Due to the high-dimensional nature of the data flow, we designed the dimensions of the thread grid (Grid) and thread block (Block) to be two-dimensional when performing task division. The following is the CPU host-side code, which is used to set the running parameters, that is, the shape of the thread grid and the shape of the thread block. Among them, gridDim, blockDim, blockIdx, threadIdx are built-in variables in CUDA C.

dim3grid(gridDim.x,gridDim.y,1);//The third dimension is always 1

dim3block(blockDim.x,blockDim.y,1);//The third dimension may not be 1, because the block is two-dimensional, so it is set to 1

Among them, blockIdx.x∈[0, gridDim.x－1], blockIdx.y∈[0, gridDim.y－1], threadIdx.x∈[0, blockDim.x－1], threadIdx.y∈[0 ,blockDim.y-1].

There are two levels of parallelism in the figure, that is, the parallelism among the thread blocks (Block) in the thread grid (Grid) and the parallelism among the threads (Thread) in the thread block (Block). (N+1) represents the total number of thread blocks (block), and (M+1) represents the total number of threads (thread).

(N+1)=gridDim.x*gridDim.y≤65535*65535, where gridDim.x≤65535, gridDim.y≤65535.

(M+1)=blockDim.x*blockDim.y≤1024, where blockDim.x≤512, blockDim.y≤512.

Since the thread grid (Grid) and the thread block (Block) are two-dimensional, a two-dimensional index is also used in the kernel function. The following is the code on the device side, which is used to calculate the thread index, that is, to determine the position of the thread (Thread) in the entire thread grid (Grid).

unsigned int bid_in_grid = blockIdx.x + blockIdx.y * gridDim.x;

unsigned int tid_in_block = threadIdx.x + threadIdx.y * blockDim.x;

unsigned int tid_in_grid_x = threadIdx.x + blockIdx.x * blockDim.x; //x

unsigned int tid_in_grid_y = threadIdx.y + blockIdx.y * blockDim.y; //y

unsigned int tid_in_grid = tid_in_grid_x + tid_in_grid_y * blockDim.x * gridDim.x; //offset.

In addition, in order to effectively utilize the execution unit, when designing a thread block (Block), the number of threads in each block should be an integer multiple of 32, preferably between 64 and 256. In order to make full use of GPU resources and improve its execution efficiency, we must pay special attention to the dimensional design of the thread grid (Grid) and thread block (Block) when implementing the code.

The above description is only a preferred embodiment of the present invention, but the scope of protection of the present invention is not limited thereto, any changes or substitutions that can be easily conceived by those skilled in the art within the technical scope disclosed in the present invention, All should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be based on the protection scope of the claims.

Claims (10)

1. A data stream processing system on a GPU, characterized in that the data stream of a data source passes through the data stream processing system to the client, and the data stream processing system includes a CPU host and a GPU device; The CPU host includes a CPU-side loading engine module, a CPU-side buffer module, a data stream preprocessing module, a data stream load reduction module, and a visualization module. The CPU-side loading engine module is provided with a loading or storage unit, and the CPU-side buffer module is provided with a memory. The loading or storage unit of the loading engine module, the data stream preprocessing module, the data stream offloading module and the visualization module all interact with the memory connection of the buffer module on the CPU side, and the loading or storage unit of the loading engine module on the CPU side interacts with the visualization module; The GPU device includes a GPU-side loading engine module, a GPU-side buffer module, a data flow summary extraction module, a data flow processing model library, and a data flow processing module. The GPU-side loading engine module is provided with a loading or storage unit, and the GPU-side buffer module is provided with a video memory , the data flow summary extraction module is used to integrate the summary extraction method for the data flow processing module to call, the data flow processing model library is used to integrate the data flow processing algorithm for the data flow processing module to call, the loading or storage unit of the GPU-side loading engine module, data The stream processing module interacts with the video memory connection of the GPU-side buffer module, the data stream summary extraction module, and the data stream processing model library are all connected to the loading or storage unit of the GPU-side loading engine module, and a storage space is opened up in the video memory of the GPU-side buffer module is a sliding window; The loading or storage unit of the CPU-side loading engine module interacts with the data source, the loading or storage unit of the GPU-side loading engine module, and the client through the Internet; The loading or storage unit of the CPU-side loading engine module is used to store the data stream of the data source in the memory of the CPU-side buffer module, and is used to send the preprocessed data flow back from the memory to the GPU-side loading engine through the Internet The loading or storage unit of the module is used to load the data results returned by the loading or storage unit of the GPU-side loading engine module into the memory, and to send the data results to the visualization module, and to display the normalized data results of the visualization module to the client; The data stream preprocessing module is used to preprocess the original data stream in the memory of the CPU-side buffer module, and store the preprocessed data stream into the memory; The memory of the CPU-side buffer module is used to interact with the load or storage unit of the CPU-side load engine module, and to interact with the data stream preprocessing module; The loading or storing unit of the loading engine module on the GPU side is used to load the preprocessed data stream transmitted by the loading or storing unit of the loading engine module on the CPU side through the Internet into the sliding window of the video memory of the buffering module on the GPU side, and used for Send the data result returned by the video memory to the loading or storage unit of the loading engine module on the CPU side through the Internet; The data flow processing module is used to call the summary extraction method in the data flow summary extraction module, extract the summary of the data flow in the sliding window, and store the final summary data structure in the video memory; and the data flow processing module is used to call The data flow processing algorithm in the data flow processing model library processes the summary data and stores the processed data results in the video memory; The video memory of the GPU-side buffer module is used to interact with the loading or storage unit of the GPU-side loading engine module, and is used to interact with the data stream processing module; The visualization module is used to normalize the data result and send it to the load or store unit of the CPU-side load engine module. 2. the data flow processing system on a kind of GPU according to claim 1, it is characterized in that CPU end buffer module is also provided with the memory manager that is used to manage internal memory, is provided with input monitor in the memory manager, input monitor is used for Monitor the temporary storage of unprocessed data streams in the memory; the CPU-side load engine module includes a speed regulator, a load or store unit, and an initialization integrator; the speed regulator is used to adjust the data flow of the data source to flow into the CPU-side load engine according to the cache state of the memory The flow rate in the loading or storage unit of the module has a feedback mechanism in the speed regulator; the initialization integrator is used to integrate the initialization operation of the CPU host and GPU device. 3. A data stream processing method on a GPU, characterized in that the data stream output by the data source is processed by any one of the data stream processing systems in claim 1 or 2, and the data result is transmitted to the client; the processing flow of the data stream is as follows : (1) Loading data stream: the data stream in the data source flows into the loading or storage unit of the CPU-side loading engine module, and the loading or storage unit of the CPU-side loading engine module stores the data stream into the memory of the CPU-side buffer module; (2) Data stream preprocessing: the data stream preprocessing module preprocesses the original data stream in the memory, and stores the preprocessed data stream into the memory; (3) Transmission data stream: the preprocessed data stream is sent from the memory to the loading or storage unit of the CPU-side loading engine module, from the loading or storage unit of the CPU-side loading engine module to the Internet, and then to the GPU side for loading via the Internet. The loading or storage unit of the engine module is loaded into the sliding window of the video memory by the loading or storage unit of the engine module on the GPU side; (4) Data flow summary extraction: the data flow processing module calls the summary extraction method in the data flow summary extraction module, performs summary extraction on the data stream in the sliding window, and stores the final summary data structure in the video memory; (5) Data stream processing: the data stream processing module calls the data stream processing algorithm in the data stream processing model library to process the summary data, and stores the processed data results in the video memory; (6) Data transmission results: The data results are sent from the video memory of the buffer module on the GPU side to the loading or storage unit of the loading engine module on the GPU side, and then sent to the Internet by the loading or storage unit of the loading engine module on the GPU side, and then reach the CPU via the Internet The load or storage unit of the load engine module on the CPU side loads the data result into the memory by the load or storage unit of the load engine module on the CPU side, or sends the data result to the visualization module by the load or storage unit of the load engine module on the CPU side; (7) Result visualization: the visualization module normalizes the data results and sends them to the loading or storage unit of the CPU-side loading engine module, and the loading or storage unit of the CPU-side loading engine module displays the data results to the client. 4. A data stream processing method on GPU according to claim 3, characterized in that in step (2), the data stream preprocessing module preprocesses the original data stream in the memory using a preprocessing method, and the preprocessing method Including data cleaning methods, data integration methods, data transformation methods and data specification methods, the preprocessing method used can be one of the above methods, or a combination of multiple methods can be selected. 5. A data stream processing method on a GPU according to claim 3, characterized in that after step (2), when the data stream is overloaded, the data stream is subjected to load reduction processing through the data stream load reduction module, and the specific steps are: Ⅰ. The input monitor of the memory manager of the CPU side buffer module monitors the temporary storage of unprocessed data streams in the memory, and determines whether the volume of the new data stream exceeds the data stream processing module of the GPU device within a time unit. processing capacity; Ⅱ. If the data stream processing module of the GPU device can handle all the data streams, then transmit the data stream; if the volume of the new data stream exceeds the processing capacity of the data stream processing module of the GPU device, that is, the data stream is overloaded, then Transfer the data flow to the data flow offloading module; Ⅲ. The data stream load reduction module performs load reduction processing on the data stream; Ⅳ. The data stream load reduction module transfers the remaining data streams into the memory for the next step of transmitting data streams. 6. The data stream processing method on a GPU according to claim 5, wherein the data stream load reduction module adopts one or more combinations of the following strategies for data stream load reduction processing: i. Data-based discarding: among the received and unprocessed data in the time series data stream, find the data with the longest length and discard them; ⅱ. Attribute-based trimming: Each data in the data stream has an attribute. In the data, the attribute with the lowest frequency is removed, so as to trim the attribute of the data; ⅲ. Priority-based discarding: Each new incoming data stream is assigned a priority, among the received and unprocessed data streams, select those with the lowest priority and discard them. 7. the data flow processing method on a kind of GPU according to claim 3, it is characterized in that display memory uses global memory to store various data, and the sliding window that opens up in display memory is used for saving the data flow that arrives at GPU device from CPU host Up, the sliding window uses a sliding window defined based on the number of tuples, that is, a sliding window with a fixed window size, which is used to save the recently arrived data stream; The data flow processing method of the sliding window uses the rewritable loop sliding window method. When updating, the new data directly covers the data to be expired, and a format transformation function is provided to maintain the logical format state of the data in the sliding window. 8. A data stream processing method on a GPU according to claim 3, characterized in that the data stream summary extraction in step (4), the data stream is obtained through a summary extraction method to obtain a summary data structure, and the summary extraction method includes a sampling method, Wavelet method, sketch method and histogram method. 9. The data stream processing method on a GPU according to claim 3, wherein the data stream processing model library integrates various data stream processing algorithms during data stream processing, including query processing algorithms, clustering algorithms, classification algorithm, frequent itemset mining algorithm and correlation analysis algorithm among multiple data streams. 10. A data stream processing method on a GPU according to claim 3, 7, 8 or 9, wherein the task of the data stream processing module is to call the summary extraction method of the data stream summary extraction module to extract the summary of the data stream , and call the data stream processing algorithm in the data stream processing model library to perform parallel calculations on the summary data; the data stream processing module includes a data stream input assembler, a global thread block scheduler and a computing array, and the computing array is provided with shared memory, loading or storage unit; the data stream input assembler is responsible for reading the data in the video memory into the shared memory of the data stream processing module, and the global thread block scheduler is responsible for scheduling, allocating and managing the thread blocks, threads and instructions in the shared memory, computing The array is used for the calculation of the thread; the load or storage unit in the calculation array loads data from the video memory to the shared memory during calculation.