Research On Characteristic Based Optimization Technologies Of Iterative Processing

Iterative algorithms are proposed to handle raw data round by round until its results are converged. They were widely used in numerical analysis, e.g., linear equations and differential equations, which have been extended to data mining, machine learning and scientific simulations. In the era of big data, the data is generated with an explosive growth. It becomes an urgent task to efficiently support the large-scale iterative algorithm to rapidly extract the useful information from the raw data.Currently, many iterative processing systems are proposed to efficiently support them. However, the iterative algorithms have different characteristics, where the asynchronous feature and Power-law Dependence Graph (PDG) feature have the most impacts on their performance. An iterative algorithm with the asynchronous feature is often called asynchronous iterative algorithm, which can converge to the desired results without synchronization between iterations. PDG feature refers to its data dependence graph with highly skewed power-law degree distributions. Due to the existing methods do not take into account the diversity of iterative algorithms, they may suffer from slow convergence rate, high overhead, significant skew, respectively.In details, the asynchronous iterative algorithm with PDG feature may face suboptimal convergence for slow state propagation. Second, the asynchronous iterative algorithm also may have much redundant computation and communication overhead for speculative execution. Third, the synchronous iterative algorithm with or without the PDG feature may encounter high computational skew for different reasons. Fourth, the synchronous iterative algorithm suffer from the accumulation of skew’s negative effects due to the synchronization between iterations. In order to solve these challenges, a number of specific strategies are proposed to optimize the runtime system, which can efficiently support different kinds of iterative algorithms.First, a core-graph processing model is proposed for asynchronous iterative algorithm with PDG feature to get the optimal convergence rate. Because of the PDG feature, some vertices play a more important role than others on the convergence of these algorithms. However, with the existing solutions, the states of these important vertices are slowly propogated, inducing slow convergence. We discover that the states can be propagated between vertices much faster when the vertices are divided into the same partition and are processed sequentially along the graph path, following what we call the cascade effect. Based this observation, it constructs a core graph, consisting of the important vertices and the paths between them, aiming to translate most inter-partition state propagations into intra-partition ones. On this basis, a forward and backward sweeping execution way is proposed to make the vertex state quickly propagated within each partition via exploiting cascade effect, further accelerating the convergence. Specifically, the vertices in each partition are arranged according to the paths, then are processed in a forward and backward order along each path until their values converge.Second, a group-based execution model is put forward for asynchronous iterative algorithm to reduce the redundancy overhead caused by the speculative execution. We observe that its intermediate results can be merged and be processed in any order without affecting the correctness. Based on this observation, it manages, schedules and processes the intermediate results with group as the unit, avoiding each intermediate data to individually trigger communication and computation in successive iterations. Besides, a scheduling algorithm is also designed that allows to choose the tradeoff point between the benefits and overhead of speculative execution so as to achieve maximum efficiency.Third, a locality-aware incremental load balancing method is proposed to efficiently redress the frequent and significant load imbalance caused by the group migration in behavioral simulation. Based on the observed localized mobility property in behavioral simulation, it updates the load of each domain (corresponding to a task) according to its neighbor domains, and incrementally partitions domains to get balanced load with low overhead.Fourth, a load balancing mechanism is proposed to resist computational skew for social network analysis based on computing decomposition. Because of the PDG feature in these algorithms, the computation of some feature extraction tasks is several multiples of that of all tasks on average, and a large number of feature extraction tasks may converge at runtime, inducing computational skew. We observe that the straggling feature is the summary of a large number of data objects because of PDG feature. Based on this observation, it dynamically indentifies straggling feature extraction task and decomposes its most computation into multiple sub-tasks for parallel processing. Then a dynamic task allocation strategy is adopted to balance the load among computing units.Finally, a skew-tolerance mechanism is proposed for synchronous iterative algorithm to resist the accumulation of skew’s negative effects based on fine-grained parallelism. Based on our observed objects’ local effects, it exploits the parallelism among iterations. This way, it employs the idle time caused by skew to proceed the calculation in successive iterations, reducing the negative effects of skew within each current iteration.In summary, the optimization mechanisms can significantly speed up the convergence rate and reduce the runtime overhead of the existing asynchronous iterative algorithm, and also redress and tolerate the skew for the synchronous iterative algorithm.