【摘 要】
:
图(Graph)作为一种基础的数据结构,采用顶点和边的连接来表示对象之间的复杂关系。由于其结构的灵活性,图结构已经被广泛用来表达社交网络、化学和物理、以及生物信息学等多种应用领域中对象之间的复杂关系。随着不同应用领域之间的交叉融合发展,图处理作为众多应用领域的关键数据处理方法之一,在数据处理领域的重要性已经不言而喻。应用领域的数据增长和不同应用领域的深度融合,给图数据处理带来了一些新的挑战,如何应
论文部分内容阅读
图(Graph)作为一种基础的数据结构,采用顶点和边的连接来表示对象之间的复杂关系。由于其结构的灵活性,图结构已经被广泛用来表达社交网络、化学和物理、以及生物信息学等多种应用领域中对象之间的复杂关系。随着不同应用领域之间的交叉融合发展,图处理作为众多应用领域的关键数据处理方法之一,在数据处理领域的重要性已经不言而喻。应用领域的数据增长和不同应用领域的深度融合,给图数据处理带来了一些新的挑战,如何应用一些新的数据处理硬件和技术来加速图数据处理算法成为当前图计算领域的一个研究热点。近年来,GPU(Graphics Processing Unit)加速器由于具备超高并行能力,被逐渐应用于高性能计算、大规模图数据处理以及智能数据处理等多种应用场景。针对图着色算法中存在的数据依赖问题,提出了一种以颜色为中心的两阶段图着色算法。主要的优化技术包括:(1)提出了一种GPU上的两阶段着色算法Feluca,算法结合了迭代式着色方法和遍历式着色方法。在第一阶段采用迭代式着色方法快速对大部分顶点进行着色,在第二阶段采用遍历式着色方法在避免颜色冲突的基础上对剩余顶点进行着色。(2)针对颜色传递过程中的局部死循环问题,设计了一种环消除策略。算法通过修改有向边的指向,消除图数据中的环结构,进而避免着色过程中的局部死循环。在此基础上,在迭代式着色阶段提出了一种自顶向下的颜色选择机制,通过给当前冲突顶点分配其父母顶点颜色值的下一个颜色值,来避免颜色选择过程中产生的冲突。(3)针对遍历式着色过程中由于颜色选择依赖导致的并行度低的问题,设计了一种以颜色为中心的线程组织策略。算法给每一个颜色值分配一个线程组,并且采用流水线(pipeline)的方式来管理所有的线程组,消除了计算过程中的数据依赖,提高了GPU着色算法的并行度。针对介数中心度算法中存在的内存膨胀和访存过程中指针跳跃的问题,设计并实现了一种基于路径合并的介数中心度计算方法以及一种临时空间合并的内存管理方法,在降低临时内存开销的同时加速GPU上的介数中心度计算。主要的优化方法包括:(1)设计了一种路径合并策略,通过合并迭代过程中局部最短路径实现全局最短路径的计算,对计算过程进行剪枝。(2)提出了一种面向局部内存的活跃队列维护和更新策略来提高GPU内存数据的局部性,算法采用一种部分和的方法来对多个遍历过程中的活跃队列进行合并,实现多个遍历过程共享一个活跃队列,从而降低计算过程中的临时内存开销。针对社区检测算法中存在的分支分歧问题,设计并实现了一种基于B树的并行重叠社区检测算法。主要的优化方法包括:(1)提出了一种基于B树的数据组织方法,将遍历过程中的目标数据组织成一种并行查找树,提高遍历操作的并行度。(2)实现了一种缓存(cache)感知的B树管理方法,将B树节点映射到GPU的缓存行(cache line),提高GPU缓存利用率的同时降低访存开销。(3)实现了一种以线程组(Warp)为中心的线程组织策略,将B树节点和GPU线程组进行一一映射,消除了重叠社区检测算法中的分支分歧操作,从而提高GPU线程的利用率。综上所述,针对GPU上图处理算法优化过程中面临的数据依赖、内存膨胀和分支分歧等重要问题,研究了基于GPU的图着色、介数中心度和社区检测等典型算法,解决了GPU上图处理算法设计中面临的一些挑战,提高了GPU上图着色、介数中心度和社区检测算法的性能,对GPU等其他新型加速器上图处理算法的优化设计提供了技术参考。
其他文献
多模态磁共振图像(Magnetic Resonance Image,MRI)蕴含丰富的特征信息,被广泛应用于临床分析。从多模态MRI中分割出组织及病灶,将为医生诊断和治疗提供依据。基于U-Net卷积神经网络的方法被广泛地应用在MR图像的分割,对于具有不同特点的分割任务,以U-Net架构为基础进行有针对性的改进,来增强其特征提取能力,将有助于提高网络的分割精度。论文的主要研究内容是提出了新的深度特征
近年来发生的建筑施工安全事故中,90%以上是由于人的不安全行为造成的。从认知科学的角度,认知失效是引发不安全行为的重要原因。情绪与精神疲劳等心理负荷是引起建筑工人认知环节失效、导致其选择不正确行为方式,进而引发施工安全事故、造成职业伤害的重要因素。因此,进行面向建筑工人情绪与精神疲劳等维度的心理负荷干预管理具有重要意义。本文综合个体认知及安全行为科学、基于认知理论的不安全行为产生机理、基于认知神经
拓扑物态是当今凝聚态物理重要的研究领域。特别是拓扑绝缘体和超导体在过去二十年中被广泛地研究。近年来,拓扑物态的概念被推广到高阶。本文将介绍在高阶拓扑物态领域的三个工作。分别是:基于弱拓扑绝缘体实现高阶拓扑超导体;从Su-Schrieffer-Heeger堆叠中衍生出的高阶拓扑相;高阶拓扑绝缘体和超导体的一般性地构造。主要研究结果如下:(1)从弱拓扑绝缘体出发,考虑磁场和超导配对的相互作用,本文发现
化学合成中大量有机溶剂的使用对自然环境、人类健康造成严重破坏与持续威胁。学术界和化学制药行业已认识到偶极非质子溶剂和卤代溶剂大多不够绿色,是上述问题产生的根源之一,科学家要“对症下药”,找到解决问题的适宜方法。因此,前人在过去十年发展了若干有毒有害有机溶剂“任务专一性”替代或最小化使用策略。但受困于诸多原因,前人发展的方法尚难以满足复杂有机反应的多样化需求。新一代化学家仍需发展操作性强、环境友好、
和激光增材制造相比,电弧熔丝增材制造因为采用具有高导电性等离子体特性的弧光加热熔化材料,沉积效率更高,更加适用于大型构件制造,是当前研究的热点之一,但是因为电弧等离子弧柱加热面积大,能量相对分散,存在表面粗糙、二次机加工量大、复杂结构制造困难的问题。电弧增材制造和机械铣削减材的复合制造(HWMM)能够通过两者的交替加工,有效解决上述问题。其次,机器人灵活度高、空间扩展性好,能够更好地发挥HWMM的
“两个确立”是党在新时代取得的最重要的政治成果,是推动党和国家事业取得历史性成就、发生历史性变革的决定性因素,反映了全党全军全国各族人民的共同心愿,对新时代党和国家事业发展、对推进中华民族伟大复兴历史进程具有决定性意义。系统研究“两个确立”的生成逻辑,准确把握“两个确立”的内在关系,是深刻领悟“两个确立”决定性意义的必然前提。新时代新征程推进中国式现代化,必须同以习近平同志为核心的党中央保持高度一
日趋激烈的全球竞争背景下,创新被置于我国发展全局的核心位置,推动着城市创新地理空间的适配性重构。知识创新活动在创新中具有基础地位,对城市的原始创新能力提升极为关键。与一般创新活动类似,知识创新活动遵循地理集聚规律,在城市内部形成多种空间载体。创新网络的崛起,刺激知识创新活动形成网络集群的新载体形态,为城市创新地理空间的效率提升提供了新路径。因此,构建高效的知识创新地理空间需要引导创新地理-网络集聚
党的十九届六中全会以党的决议形式提出的“两个确立”,具有深刻的内涵要义,是新时代党的政治建设的根本主题和首要任务。这一命题的提出是理论、历史、实践演进的必然结果,也是时代呼唤、历史选择、民心所向的集中体现。深刻把握这一命题的内在逻辑,应放在“建设什么样的长期执政的马克思主义政党、怎样建设长期执政的马克思主义政党”这个重大时代课题中来把握其实践要求,严明党的政治纪律和政治规矩,坚决做到“两个维护”;
静电纺纳米纤维膜具有孔隙率高、曲率低和相互贯穿的孔结构等独特优点,作为基膜制备的聚酰胺薄膜复合(TFC)膜具有广阔的应用前景。近年来,基于静电纺纳米纤维膜构建的TFC膜逐步引起了研究人员们的关注,其分离性能显著优于基于传统相转化聚合物膜构建的TFC膜。但静电纺纳米纤维基膜仍然面临机械性能较差、膜表面孔径偏大和耐溶剂性能不佳等问题。为解决上述问题,本论文采用酰肼热环化改性聚酰亚胺(PI)纳米纤维基膜
<正>随着电网事业的不断发展,其变电负荷的压力进一步提升,为更好地维护城市的稳定运转和周边变电配置的安全,必须定期开展巡检和维修工作确保电气设备的运行效率。目前,很多偏远电站采用了无人化管理的模式,但也要关注日常定检和巡检的工作安排,对电网线路展开详细的安检与维护,降低电网运行风险,避免影响居民日常应用需求。因此,文章系统性地介绍电网变电运维的概念,结合运维管理的潜在风险,详细讨论在技术检修过程中