学位论文简介
本论文围绕大规模属性图子图内聚性分析处理关键算法和应用展开研究工作，主要工作内容和创新点如下：
首先，研究大规模基于语义属性图的稠密子图查询问题。针对现有基于属性图的稠密子图查询研究中对复杂属性建模和处理的不足，本研究提出了一种新的基于语义图的属性图建模方式、对应的稠密子图查询问题建模和对应查询算法的设计与实验。本研究提出的新图数据模型中，图中顶点的属性由有向无环语义图进行描述，相比于已有的关键词和画像树的语义属性描述方式，本研究提出的方式能更为通用灵活地描述图中顶点的语义特点。本研究中提出了三种在线查询算法，即逐级扩展的搜索算法、分支回溯的扩展搜索算法和基于损失函数的贪心搜索算法，和对应的剪枝策略经实验验证，能高效的得到查询结果。
然后，研究以调度时长为优化目标的大规模DAG划分问题。现有图划分与DAG调度无法高效满足许多大规模并行加速场景中划分需要使得执行时间最小化的需求。为了高效的得到以执行时间最短为目标的大规模DAG划分的可行解，本研究中设计了一种以减少关键路径划分为目标的基于路径分析的启发式的多级划分方法。此外本研究将提出的方法首先在模拟大规模DAG图上进行了验证，然后在大规模电路硬件加速验证和大规模DNN模型分布式推理（inference）两种场景中进行了应用。本研究提出的基于时序分析的划分可以有效减小划分后关键路径长度，利于后续调度任务的执行。
最后，研究多GPU中基于大规模DAG调度的DNN推理加速问题。本研究发现，在本文第二个研究中的大规模DNN模型分布式推理的DAG划分中，简单将DNN在GPU中的执行抽象为串行执行，没有充分利用GPU多流（stream）的并行能力。因此在本研究中首先对DNN模型推理在GPU中的执行进行深入分析，并发现基于GPU多流并行执行时两个关键特征：1）多流并行执行DNN模型时，每个流的启动时间不能忽略，因其数量级与许多DNN模型操作算子（operator）（如Sigmod）推理执行时间相当；2）单个流执行DNN模型操作算子并不能充分利用GPU的所有计算资源。基于上述两个特征以及DNN模型在GPU中基于流和cuDNN执行内存和时间的稳定性，本研究将DNN模型建模为属性DAG并提出DeOrd调度算法用于DNN模型在GPU中的推理加速。由于大DNN模型的内存限制，本研究设计了一种协同DeOrd调度算法将DNN模型操作算子分配于多GPU及其多流中，简化了本文研究点二中先分配GPU再调度操作算子顺序的方式。
主要学术成果
Peiying Lin, Zhichen Shi, Zheng Xiao, Cen Chen, Kenli Li. Latency-Driven Model Placement for Efficient Edge Intelligence Service[J]. IEEE Transactions on Services Computing, 2021, 15(2): 591-601. (第一作者，JCR 1区，SCI 2区，CCF A类期刊，IF：11.019)
Peiying Lin, Yangfan Li, Wensheng Luo, Xu Zhou, Yuanyuan Zeng, Kenli Li, Keqin Li. Personalized query techniques in graphs: A survey[J]. Information Sciences, 2022. (第一作者，JCR 1区，SCI 1区，CCF B类期刊，IF：8.233)
Peiying Lin, Siyang Yu, Xu Zhou, Peng Peng, Kenli Li, Xiangke Liao. Community search over large semantic-based attribute graphs[J]. World Wide Web, 2022, 25(2): 927-948. (第一作者，JCR 2区，SCI 3区，CCF B类期刊，IF：3.000)
Peiying Lin, Kenli Li, Zheng Xiao, Cen Chen, Siyang Yu. Work in Progress: Path-based Graph Partition for Parallel Hardware-accelerated Functional Verification[C]//2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 2021: 497-500. (第一作者，CCF B类会议)
Baixuan Wu, Zheng Xiao, Peiying Lin, Zhuo Tang, Kenli Li. Critical Path Awareness Techniques For Large-Scale Graph Partitioning（第三作者， 接收，IEEE Transactions on Sustainable Computing， SCI 2区，IF：4.908）
