大规模图数据由于数据来源的差异及内部关联的限制，实际生活生产中获得的图数据往往存在结构不完整以及属性不精确的情况。传统图算法问题的定义在非确定图数据上并不适用。当前非确定图数据研究在特定算法上开展了大量工作，但相关努力缺乏合理的并行模型理论支撑，仍存在同步开销和缓存空间过大等问题。面向搭载现代SIMD协处理器（如GPU）环境，本项目力求建立新的非确定图数据分析并行模型，并以此为基础开展系统架构和设计。具体研究内容涵括四个方面：（1）建立新的混合粒度GPU并行模型，从理论上分析并行计算粒度；（2）基于CPU/GPU多层级异构内存，提供SIMD硬件适用的图结构、概率数据缓存结构；（3）依据并行模型设计，实现了非确定图分析计算任务调度以及粒度并行执行策略；（4）设计易用的非确定图数据处理编程框架，并对系统进行实验测试和验证。申请人在图计算研究方面具有丰富经验，课题能广泛应用于行业网络挖掘。

Due to the data source difference and the limitation of internal dependency, uncertain (or probabilistic) graphs have been ubiquitously used to represent noisy, incomplete and inaccurate linked data in many emerging applications. In this literature, many uncertain graph analytic algorithms are #P-hard problems, and the conventional certain graph defined problem cannot be directly applied in these situations. The state-of-the-art makes great contributions to theory and specific algorithms of uncertain graphs, however, there still exists serve performance problems on the scalable model. By exploiting modern multi-accelerator systems, this project seeks to discover a novel parallel analytic model on uncertain graphs, and build an efficient and scalable framework. The following four aspects will be incorporated in this project: i) building a novel hybrid GPU parallel model on uncertain graph analytics, and theoretically evaluate these models; ii) constructing hierarchical storage for the structural and probability data of uncertain graphs, which is GPU-Friendly; iii) implement several GPU thread scheduling and execution strategies on uncertain graphs based on the parallel model; iv) designing a user-friendly programming model to express the uncertain graph algorithms more easily and finally evaluating our frameworks with the state-of-the-arts. The applicant has a rich experience in large-scale graph processing, and this project can be applied in industries and meet the need of large scale real-world network mining.