| Entering the era of big data, the parallel machine architectures, scalable ability of computing resources and industry application mode are changed greatly and rapidly, which bring both opportunities and challenges for parallel computing. As a bridge be-tween hardware and software, parallel computational model is an important technology to promote the research and development of big data. Recently, industry has proposed several big data programming models which are widely used on terabyte and petabyte data processing, while academics are studying big data computation models which can reflect the parallel machine architectures, reveal the principle of computation, com-munication and I/O behavior of big data jobs, analyzes the popular big data systems theoretically, and provide optimization guidelines for big data applications.Inspired by traditional parallel computational model, popular big data program-ming model and current big data computational model, we conclude that there are three theoretical problems needed to be solved. They are three-elements (parameters, behav-iors, and cost functions) problem, scalability and fault-tolerance problem and perfor-mance optimization problem. Focusing on these problems, on the one hand, we study the big data computational model and its optimization methods theoretically; on the other hand, we apply these methods in real big data case studies. Specifically, the main research contents, contributions and innovations of this dissertation are as follows:1. Abstract a parallel computational model of big data:We propose a compu-tational model p-DOT for big data analytics. This model consists p phases, each phase contains Data Layer (D), Computation Layer (O) and Communication Layer (T), and represented by matrix formulas. It chooses Input Size w and Number of Machines n as two main parameters, constructs a cost function by considering computation, com-munication and I/O behaviors, and implies that for a fixed algorithm and workload, the optimal number of machines n*is near-linear to the square root of input size (?)w. Be-sides, for a software framework F, if any job of F can be represented by p-DOT model, the processing paradigm of F is scalable and fault-tolerant.2. Certify the cost function, scalability and fault-tolerance of model:For cost function and its corollary, we restrict the memory of single machine, number of total machines and elapsed time of whole job to make them effective in practice, and con-duct large scale MPI and MapReduce experiments to demonstrate their correctness. For scalability, we exploit ISO-efficiency function, one of many parallel performance met-rics, to certify that the processing paradigm of p-DOT model is scalable, but not highly scalable. For fault-tolerance, given the assumption that input data D is available to be accessed in an archived storage, we certify that the processing paradigm of p-DOT model is fault-tolerance.3. Design optimization methods under the model and exploit them in case studies:We design three optimization methods under three layers of p-DOT model respectively. For D-Layer, we propose that using data replicas method is not only a necessary condition for fault-tolerance, but also can improve the I/O performance. For O-Layer, we present that using multi-core method can improve the computational per-formance of single machine without extra communication cost. For T-Layer, we put forward that using partial barrier method can effectively improve the communication performance, but it can only be used in the condition where the difference of conver-gence before/after optimization is less than threshold8. Moreover, we choose three real big data cases, exploit above methods in them and conduct experiments to demonstrate their acceleration. The three cases are a) Queries in Earthquake Precursor Network, b) Training in Face Recognition, and c) Training in Deep Learning. |
PDF Full Text Request