Research On Formal Description Methods Of Programming Model In Cloud Computing

Parallel programming model is a hot topic in the research area of cloud computing. Thedesign and implementation of programming models are decided by parallel algorithmstructures and distributed computing systems which they are based on. In order to developeffective parallel algorithms and improve the availability of cloud resources, parallelprogramming model should be simple to use effectively and hide the distributed details. Manydifferent programming models have been proposed recently according different problems arefaced. One of the most important programming models is MapReduce proposed by Google.The most popular programming model is Hadoop implemented by Apache according toMapReduce.As the most typical parallel programming model in cloud computing, MapReduce easesthe heavy burdens of software developers by hiding some implementation details of parallelprogramming and providing two simple-yet-effective programming interfaces. With thewidespread use of MapReduce, the design of new MapReduce based programming model hasbecome a research hotspot. These programming models extend MapReduce by different ways,one is to support parallel join algorithms and another one is to support iteration computations.However, these new programming models are not used widely now because of the loss oftheoretical analysis.This paper summarizes current researches with respect to MapReduce. Firstly, this paperintroduces the substantive characteristics of MapReduce. The problems that MapReduce canhandle are also discussed. Secondly, this paper classifies the typical MapReduce basedprogramming model according to the different application area. Comparison and analyses ofthese programming models are proposed. Especially, the programming models that canrepresent join computations and iterative computations are discussed in more detail.In this paper, we proposed a hierarchical formal description method to analyze programmingmodels in cloud computing. Especially, we choose the typical improved parallel programmingmodel Map-Reduce-Merge to be described. Map-Reduce-Merge is an improved parallelprogramming model based on Map-Reduce in cloud computing environment. Through thenew Merge module, Map-Reduce-Merge can support processing multiple relatedheterogeneous datasets more efficiently.We describe it from two aspects, one is about the interface to software development andanother one is the interface to hardware implementation. We use two formal methods for thispropose. One is functional programming language Haskell, while another is communicating sequential processes (CSP). In order to analyze this new model, we present a rigorousdescription for Map-Reduce-Merge model using Haskell and CSP. Firstly, we describe thebasic program skeleton of Map-Reduce-Merge programming model. Secondly, an abstractdescription for Map-Reduce-Merge is presented by analyzing the structure and function of theMerge module with Haskell as the description tool. Thirdly, we evaluate theMap-Reduce-Merge model on the basis of our description. On the other hand, we use CSP asthe formal method to describe the underlying communications among module Map, Reduce,and Merge. We capture the functional characteristics of the Map-Reduce-Merge model by ourabstract description, which can provide theoretical basis for designing more efficient parallelprogramming model to process join operation.