【作者】 张威；

【导师】 何云峰；

【作者基本信息】 华中科技大学 ， 计算机应用技术， 2023， 硕士

【摘要】 Gremlin是一种函数式、具有数据流特性的图数据库查询语言,使用者可以用Gremlin编写复杂的查询任务,但Gremlin执行查询的过程没有利用自身数据流的特性,没有充分使用执行机器的多核资源。数据流编程模型是一种并行模型,它通过将程序的计算过程与通信过程分离暴露程序的并行性,以数据流图的形式执行程序,实现程序的并行加速。Gremlin执行时递归调用的特点,使得数据流编程模型难以直接应用在Gremlin上。针对Gremlin没有利用多核资源并行化的问题,设计了基于数据流图的Gremlin并行优化框架。框架对Gremlin进行扩展,设计新的数据结构打破查询语句执行时形成的递归调用链,将查询语句分解成多个子语句,子语句之间可以并行执行。在此基础上,利用Gremlin数据流的特性,根据数据流编程模型,将查询语句映射为数据流图,用数据流图表示整个查询任务,采用不同的数据流图实现让查询任务以不同方式执行。最后在数据流图的基础上进行任务划分、任务调度过程,以数据流图的方式并行执行查询任务,每个子任务分配到不同CPU核上,每个核按照调度策略执行子任务。选取典型的图查询语句,在多核处理器上进行实验测试,对比优化前后Gremlin查询性能的差别。实验结果表明,采用基于数据流图的优化方法后,Gremlin能够利用多核资源执行查询任务,部分查询语句的执行效率有明显的提升,在8核条件下加速比能够达到4.0x。更多还原

【Abstract】 Gremlin is a functional graph database query language with data flow properties,users can use Gremlin to write much complex query tasks.However,Gremlin does not take advantage of its own data flow properties and can not make full use of multi-core resources of executing machines in the process of querying.The data flow programming model is a parallel model,which exposes the parallelism of the program by separating the calculation process and the communication process of the program.The model executes the program in data-flow-graph form,which utilize parallelism accelerating the execution processes.The recursive calls during Gremlin execution make it difficult to directly apply the data flow programming model to Gremlin.Focus on the problem that Gremlin does not use multi-core resources to parallelize querying,this paper design a Gremlin parallel optimization framework based on data flow graph.The framework extends Gremlin,designing new data structures to break the recursive call chain during query execution,and decompose the query into multiple sub-queries,which can be executed in parallel.Then,the framework map the query to a data flow graph according to the data flow programming model,and the entire query task is represented by the data flow graph,different graph structure implementations lead to different query execution process.Finally,the task division and task scheduling process are performed on the the data flow graph,and the query tasks are executed in parallel in the form of the data flow graph: each subtask is assigned to a different CPU core,and each core executes subtasks according to the scheduling policy.This paper selects typical graph queries,conducts experimental tests on multi-core processor machine,and compares the performance difference of Gremlin before and after optimization.The result shows that after adopting the optimization,Gremlin makes use of multi-core resources,and a part of queries execution efficiency has been significantly improved,the speedup ratio of which can reach 4.0x under the condition of 8 cores.更多还原