Acceleration of huge data analysis, especially an analysis of huge, and fast streaming data is one of the major issues in recent computer science. Proper modeling, and understanding of streaming data analysis are indispensable for speed-up, scale out, and faster response time of streaming data analysis. Especially for the research on scheduling, or load balancing algorithms, a model of the target application truly impacts on the performance of the scheduling, or load balancing algorithms, however, there is no study on the realistic models, or the actual behaviors of streaming data analysis yet. This paper proposes a task graph for stream mining algorithms with some examples of actual applications. A task graph represents a workload of the target application with data dependencies, and control flows. This is the first proposal of task graphs for stream mining algorithms, and the task graphs play an important role as a benchmarking tool for the development of scheduling, or load balancing algorithms targeting on stream mining algorithms.
Big data applications utilize often stream mining algorithms, while data intensive applications process huge data in a batch. That is, big data application often tries to analyze data stream, which is a sequence of data arriving in chronological order, on the fly. As the data stream flows very fast, stream mining algorithms are developed with the purpose of the perfect analysis over such fast data flows. Once the delay of the analysis arises, and the analysis fails to keep up with the data arrival, the whole process will be forced to drop some of the arriving data. As many of the streaming analysis processes place emphasis on the real-time analysis in chronological order, a drop of the arrival data is highly critical.
As big data applications scale up with such a severe requirement for extremely low latency, big data applications become to run on the parallel and distributed computing environment such as the computing cloud. In order to exploit parallelism, and speed up the applications, scheduling is indispensable. Scheduling algorithms in parallel and distributed computing environment have been studied intensively for a long time especially in HPC, and these researches often validate, and compare the scheduling algorithms with task graphs. A task graph represents a workload of a target application, which is often synthetic workload generated randomly. As the quality of task graphs heavily impacts on validation of scheduling algorithms, the methodology to generate task graphs have been studied as well with a strong focus on data intensive applications in HPC.
This paper proposes task graphs generated from the actual implementations of stream mining algorithms in order to contribute to a development of effective, and practical scheduling algorithms for stream mining algorithms. The contributions of this paper are 1) the first proposal of task graphs for stream mining algorithms, 2) the practical and realistic workloads extracted from the existing implementations, 3) task graphs as representations of the behaviors of stream mining algorithms to open up unexplored problems for conventional scheduling algorithms, and 4) task graphs as a benchmarking tool to accelerate the development of scheduling algorithms for stream mining algorithms.
The rest of this paper is organized as follows. Section 2 gives a generic model of stream mining algorithms in order to clarify data dependencies of the process. Section 3 describes the procedure of task graph generation, and proposes a format of task graphs for stream mining algorithms. Section 4 overviews actual stream mining algorithms analyzed in this paper, and represents corresponding task graphs. Section 5 briefly introduces the related work, and Section 6 concludes this paper.
A stream mining algorithm is an algorithm specialized for a data analysis over data streams on the fly. There are many variations of stream mining algorithms, however, general stream mining algorithms share a fundamental structure, and a data access pattern as shown in Figure 1 [1].
A stream mining algorithm consists of two parts; a stream processing part, and a query processing part. First, the stream processing module picks the target data unit, which is a chunk of data arrived in a limited time frame, and executes a quick analysis over the data unit. The quick analysis here can be a preconditioning process such as a morphological analysis, or a word counting. Second, the stream processing module updates the data cached in one or more sketches with the latest results through the quick analysis. That is, the sketches keep the intermediate analysis, and the stream processing module updates the analysis incrementally as more data units are processed. Third, the analysis module reads the intermediate analysis from the sketches, and extracts the essence of the data in order to complete the quick analysis in the stream processing part. Finally, the query
. processing part receives this essence for the further analysis, and the whole process for the target data unit is closed.
Based on the modeling above, we can conclude that the major responsibility of the stream processing part is to process each data unit for the further analysis, and that the stream processing part has the huge impact over the latency of the whole process. The stream processing part needs to finish the preconditioning of the current data unit before the next data unit arrives, otherwise, the next data unit will be lost as there is no storage for buffering the incoming data in a stream mining algorithm. On the other hand, the query processing part takes care of the detailed analysis such as a frequent pattern analysis, or a hot topic extraction based on the intermediate data passed by the stream processing part. The output by the query processing part is usually pushed into a database system, and there is no such an urgent demand for an instantaneous response. Therefore, only the stream processing part needs to run on a real-time basis, and the successful analysis over all the incoming data simply relies on the speed of the stream processing part.
The model of a stream mining algorithm shown in Figure 1 also indicates that the data access pattern of the stream mining algorithms is totally different from the data access pattern of socalled data intensive applications, which is intensively investigated in HPC. The data access pattern in the data intensive applications is a write-once-read-many [9]. That is, the application refers to the necessary data many times during the computation; therefore, the key for the speedup of the application is to place he necessary data close to the computational nodes for the faster data accesses. On the other hand, in a stream mining algorithm, a process refers to its data unit only once, which is a read-oncewrite-once style. Therefore, a scheduling algorithm for the data intensive applications is not simply applicable or the purpose of the speedup of a stream mining algorithm.
In Figure 2, there are three data dependencies in total as follows, and all of these three dependencies are essential to keep the analysis results consistent, and correct. 1. 2. 3.
The processing module in the preceding process should finish updating the sketches before the processing module in the successive process starts reading the sketches (Dep.1 in Figure 2).
The processing module should finish updating the sketches before the analysis module in the same process starts reading the sketches (Dep.2 in Figure 2).
The analysis module should finish reading the sketches before the processing module in the successive process starts updating the sketches (Dep.3 in Figure 2).
As discussed in Section 2, a model of a stream mining algorithm has data dependencies both across the processes, and inside one process. Therefore, a task graph or a stream mining algorithm should consist of a data dependency graph, and a control flow graph. We already modeled both the data dependencies, and the control flows for stream mining algorithms in Section 2, however, a task graph is a finer grained model for a specific algorithm and implementation.
A data dependency graph is drawn via an analysis of the actual implementation of the target algorithm. Figure 3(a) is an example of a data dependency graph of the training stage of Naïve Bayes classifier[2] implemented by MOA project [8]. Figure 4 represents a pseudo code for the data dependency graph in Figure 3(a). A data dependency graph is a directed acyclic graph (DAG). In a data dependency graph, each node represents a basic block, or ... ...
2
2
360
2
360
2
2
2
...
285
...
for all training data do
(
(
In a data dependency graph, each node has a number, and the
number indicates that the particular node represents which basic
block in the pseudo code, such as shown in Figure 4. In this
example, node 1 represents the line starting with “(
A control flow graph has a computational cost for each node. A computational cost shown in a control flow graph is the average of the actual computational costs measured in the actual computations, however, this version of the control flow graphs do not contain communication costs. As the control flow graphs here are fine-grained, it is not beneficial to scatter one control flow graph over the distributed computing environment. That is, pipelining control flow graphs according to the speed of the input data is a more realistic, and practical solution. Communication costs for pipelining in the distributed computing environment contains further discussions, and we reserve this topic for the future work.
Figure 5 is the XML schema for a task graph, and Figure 6 is an
example representation of XML for Figure 3. Task graphs should
for all input data items do
(
This section introduces task graphs extracted from the actual popular methodologies. One is top-k implemented as a Java 1.7 application. The other is Hoeffding tree algorithm[6], which is one of decision tree algorithms, and implemented as MOA module[8].
We implemented top-k based on min summary algorithm proposed by Lam et al.[7], and the base proposal by Calders et al. [3]. Figure 7 is the pseudo-code of the corresponding algorithm. Figure 8 (a) represents the extracted data dependency graph, and Figure 8(b) represents the extracted control flow graph. As we already saw through the generic model of the stream mining algorithms in Section 2, each node processing one data unit basically depends on the results of the previous node. That is, each node is a consumer of the previous node. The exception is node 1 (data fetching), and node 6 (update of the pruning threshold). Especially, node 6 updates the pruning threshold based on the length of the summary, and node 6 has to wait for the elimination of the obsolete border points, which is node 5. On the other hand, the process represented from node 2 to node 5 is independent across the distinct items appeared during the observation, and this part is capable of parallel execution. When we focus on the dependency between the preceding process, and the successive process, node 2 in the successive process depends on node 5 in the preceding process. Node 5 in the preceding process deletes the obsolete border points, while node 2 adds a new border point, or increment the counter of the existing border point according to the input. There is no dependency when node 2 adds a new border point, however, node 2 needs to decide which border point should be updated when node 2 increments the count of the existing border point. This is the reason why node 2 in the successive process behaves as a consumer of node 5 in the preceding process.
One more thing we would note here is that the computational cost of node 6 is relatively huge compared to the computational costs of the other nodes. The major reason of the heavy load of node 6 is that node 6 needs to calculate the maximum relative frequency of the least appeared item during the observation. Because of this process, node 6 is a consumer of node 5, needs to sweep all the data in the summary, and consumes more time for completion. 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 ... ... ... ... ... ... ... ...
2 3 4 5 2 3 4 5 1355 2322 1143 694 1355 2322 ... ... ... ...
...
This tendency of the computational cost implies that the execution in a pipeline is really effective for min summary algorithm. In fact, the computational cost of node 6 is almost equivarent to the total cost of the single path of nodes 1-5, and node 6 is independent from these nodes. Therefore, node 1-5, and node 6 are capable of running in a pipeline, and consumes almost the same computational time. That is, there is a chance to hide almost half of the execution time of the process time of one data unit, and improve the throughput by pipelining.
We also extracted a task graph of Hoeffding tree algorithm from
MOA implementation. Figure 9 is the pseudo-code of the
algorithm, and Figure 10 represents the extracted data dependency
graph. The control graph is omitted for the page limitation. We
skip the detailed discussion for the page limitation again, however,
we can observe similar tendency of the application as we saw in
the generic model in Section 2, Naïve Bayes in Section 3, and min
summary algorithm in this section. One major difference from the
previous cases is that node 1 depends on node 9, therefore, the
effect of the pipelining is not huge compared to the other cases.
Here, we need to discuss computational costs in the control flow
graph. This version of the task graph represents a computational
cost as the average of actual executions. This is in a sort of the
simplified model as the computational cost of stream mining
algorithms easily varies depending on the input data. We need to
Let HT be a tree with a single leaf (the root)
for all training data do
(
using HT for all attributes for v do
(
statistics end for end if end if end for
2 4 Figure 10. A data dependency graph for Hoeffding tree algorithm. develop the better methodology for the computational model, however, we reserve this issue as a future work.
There are several studies on task graph generation, mainly focusing on random task generation. A few projects reported task graphs generated based on the actual well-known applications, however, those applications are from numerical applications such as Fast Fourier Transformation, or applications familiar to HPC community for a long time.
Task Graphs for Free (TGFF) provides pseudo-random task graphs [5,11]. TGFF allows users to control several parameters, however, generates only directed acyclic graphs (DAGs) with one or multiple start nodes, and one or multiple sink nodes. Each task graph is assigned a period, and a deadline based on the length of the maximum path in the graph, and the user specified parameter. GGen is another random task graph generator proposed by Cordeiro et al [4]. GGen generates random task graphs according to the well-known random task generation algorithms. In addition to the graph generator, GGen provides a graph analyzer, which characterizes randomly generated task graphs based on the longest path, the distribution of the out-degree, and the number of edges. Task graph generator provides both random task graphs, such as Fast Fourier Transformation, Gaussian Elimination, and LU Decomposition [12]. The random task graph generator supports variety of network topologies, including star, and ring. Task graph generator also provides scheduling algorithms as well. Tobita et al. proposed Standard Task Graph Set (STG), evaluated several scheduling algorithms, and published the optimal schedules for STG [10,13]. STG is a set of random task graphs, which are ready to download. Tobita et al. also provides task graphs from numerical applications such as a robot control programs, a sparse matrix solver, and SPEC fpppp.
Besides the studies on task graph generation, Cordeiro et al. pointed out that randomly generated task graphs can create biased results, and that the biased results can mislead the analysis of scheduling algorithms[4]. According to the experiments by Cordeiro et al., a same scheduling algorithm man obtain a speedup of 3.5 times only by changing the graph generation algorithm for the performance evaluation.
Random task graphs contributes positively for evaluation of scheduling algorithms, however, do not perfectly cover all the domains of parallel and distributed applications as Cordeiro et al. figured out in their work. Especially for stream mining applications, which focus on in this paper, the characteristic of the application behaviors are quite different from the characteristic of the applications familiar to the conventional HPC community as we discussed in Section 2. Task graphs generated from the actual stream mining applications have profound significance in the better optimization of the applications in parallel computing environment for wider area of applications.
This paper proposed task graphs for stream mining algorithms. This is the first clear proposal of task graphs modeling stream mining algorithms, and the task graphs are extracted from the actual implementations of the popular existing methodologies. Task graphs proposed in this paper play an important role as the benchmarking tool to evaluate scheduling algorithms, or load balancing algorithm, which is indispensable for the research of scheduling, or load balancing algorithms truly effective for stream mining algorithms. In fact, in this paper, the proposed task graphs represent apparently different characteristics, and dependencies compared to the data intensive applications in HPC, and this fact points out we need to consider scheduling methodologies focusing on stream mining algorithms. For the better set of task graphs, we are working on more stream mining algorithms. [12] TGG, Task graph generator.
http://taskgraphgen.sourceforge.net/.