Research On Abstract Interpreter Of Dryad Model

Microsoft's Dryad distributed execution engine serves large-scale data processing systems in a coarse-grain data-parallel manner.Essentially it is a large-scale data processing system.As soon as Dryad appears,it draws great attention from academia and industry.Since most implementation of large-scale data processing systems are complex,improvement of systems is difficult and prone to side effects,which causes the development and maintenance of systems costly.Semantic models contribute to analysing the characteristics of programs and systems,and it has significant effects on adding system functionality and decreasing cost of development.However,to my best knowledge,semantics for Dryad have never been formally defined.Based on this,this paper proposes an abstract interpreter of Dryad model,which use the abstract interpreter method to define operational semantics of Dryad programs for further program analysis.Execution plan graph is the core element of Dryad.A task can be represented as a directed acyclic graph,which composed of several program blocks and channels.In this paper,from the perspective of language,it is separated into syntax and semantics.A task description language is defined in term of syntax,and an abstract interpreter is defined in term of semantics.Firstly,this paper introduces basic knowledge of Dryad model and abstract interpreter method and gives the grammar definition of a pure functional language,which is used as a description tool of abstract interpreter.Then,this paper specifies a task description language.It illustrates the basic framework and implementation principle,which takes data sets,function sets and task programs as inputs,interprets tasks and produces outputs.And it also defines semantic denotations as configurations.Next,this paper discusses the implementation principles of the Dryad abstract interpreter,including its parsing and executing process in functional language.Parsing process is mainly used to parse a task and produce an initial configuration,which specifies some syntactic units and defines their corresponding semantic functions.Executing process contains subprocesses of Map,Concat,Update Vs,Judge End and Output etc,which controls the configuration changes,computes the fixed point and produces the final results.Finally,this paper demonstrates rationality of the Dryad abstract interpreter by analyzing the process of a representative case ‘word counting'.This work is a research on formal semantic of Dryad program,which is mainly based on abstract interpreter method.The configuration reflects the distributed nature of Dryad accurately and parsing and executing depict the processing flow of Dryad reasonably.Actually,the result of the abstract interpreter is the semantic of a Dryad program.This research aims to achieve first steps about formalizing Dryad.It helps specify static structures and dynamic behaviors of Dryad and establishes theoretical basis for Dryad program analysis and system verification.Since Dryad is a typical large-scale data processing system,analysis about it can also apply to similar systems and further contribute to refinement,optimization and promotion of related systems.