异构计算平台下高效大图数据处理的运行时支撑环境研究

Graph computing is one of the most important technical means to solve the majority of real-world problems. With the advent of “Internet +” and the further development of social economy, big graph is increasingly exhibiting a series of remarkable features with large scale, complex correlation and dynamic variation. On account of the relatively simple procedure of data analysis and processing, the off-the-shelf graph processing systems are no longer meeting the demands of this important change. Recently, a major breakthrough has been made in novel heterogeneous architectures, which provide a wealth of on-chip resources, a high degree of parallelism and very low data latency, opening a great opportunity to better support the high performance big graph processing. Nevertheless, in illusion to the variation and rebuilding of resources of emerging heterogeneous architectures, the traditional resource management models, runtime scheduling, runtime optimization and programming supporting library, cannot no longer be adaptive. In particular, for the typical graph computing scenarios, the traditional runtime is not closely combined with the inherent demand characterization of graph computing, leading to the inefficient utilization of heterogeneous resources and the significant limitation of parallelism exploitation. All of these introduce enormous challenges for the efficient processing of big graph. At present, there still lacks the matching runtime support environment to make full use of the potential of emerging heterogeneous architectures...As a consequence, this project conducts the targeted research. Through observing the inherent runtime characteristics of graph iteration, we rethink the deficiencies of the theory and practices of off-the-shelf runtime techniques on heterogeneous platforms. In an effort to match the hardware capacity, we present a series of new runtime supporting techniques, ranging from resource management models, runtime collaborative scheduling and optimization, as well as requisite programming interfaces, to bridge the gap between underlying hardware and high-level graph applications. We believe that this project can provide the key runtime supporting techniques for the high performance big data processing on heterogeneous computing platform.

图数据日益呈现巨量规模、复杂关联、动态多变等显著特征，现有图计算系统相对简单的数据分析与处理过程已不再适应这一重大现实需求的转变。近些年新型异构体系结构已取得重大突破，提供了丰富的片上资源、超高并行性与极低数据传输延时，为更好地支撑大图数据的高效处理带来了新的契机，但是，随着新型体系结构资源结构上的变化与重塑，传统运行时已凸显不适应性，尤其是针对图计算典型应用场景，更是未紧密结合其固有的运行时特征，导致异构资源利用和并行性攫取大幅受限，对大图数据高效处理带来了巨大的挑战。..项目拟开展针对性的研究，紧紧围绕大图数据处理的运行时特征，再思考新型异构体系结构下传统运行时基础理论与方法的不足，探索适应新型异构体系结构大图数据处理的资源管理模型、运行时调度与优化以及编程接口支撑库等，力求形成一套可充分匹配底层硬件优势与上层图应用特征的高效运行时支撑环境，为大图数据的高效处理提供运行时异构关键支持。

以图计算为代表的大数据市场迅猛增长，由于其体量庞大、结构多变、依赖复杂的特征，对计算机体系结构的处理能力提出了更高的要求。CPU/GPU等传统体系结构遵循统一设计理念，通用于各类计算领域的控制流处理架构在新的需求面前陷入困境，存在着并行效率差、访存随机性强、数据冲突频度高、以及性能功耗比低等突出问题，开展以处理架构创新为主的图计算技术与系统研究对提升其性能、能效比等技术水平有着重要的现实意义。针对图计算灵活设计和高度并行的现实需求，重点解决了面向图计算的新型体系结构及系统软件方面的技术挑战，逐步在图计算加速器架构设计、运行方法与工具环境方面取得了进展。1) 提出了高能效图计算加速器，.针对图计算在传统控制流体系结构上所面临的并行效率低、存储效率差、同步开销大“两墙一锁”问题，提出了基于数据流的加速器架构设计思路，以数据驱动指令执行，实现高度并行与乱序执行，破解了控制流体系结构固有的同步通信开销大、异构并行效率低的难题，设计了高并发流水线结构、乱序访存机制、以及两级并行累加器。2) 提出了面向图计算的高效运行系统，针对图计算复杂数据依赖对计算并行性的影响，提出了“符号迭代”的新模式，相比传统数值计算，符号迭代允许利用符号值替代具体数值参与计算，解决了图计算非规则关联特征和加速设备众核化趋势所引发的并行关系管理难题，研发了基于符号迭代的图计算系统，提出了基于符号执行的关联关系并行表达的编程模型、图划分机制、以及运行时调度方法。3) 提出了基于图计算技术的工具环境，针对多线程程序并发分析效率低的问题，提出了程序图抽象理论，将复杂的并发分析问题转化为图并行计算问题，解决了大型复杂软件系统在线跟踪和演化重现的难题，提出了基于图计算的超大规模并发分析、调试与优化框架。