【摘 要】
：
在电子商务网络、社交网络和生物网络等领域,图在表示网络中实体以及实体间的关系方面起着至关重要的作用。给定图中两个顶点s和t,图数据库中的一个基本问题是研究s和t之间的关系,而在该领域中一个很重要的研究方向是k跳约束下的的s点到t点的简单路径枚举问题。然而,所有针对此问题的现有算法都遵循基于DFS（深度优先搜索）框架,导致这些算法可伸缩性低下。此外,近十年来,使用FPGA等硬件设备加速图算法已成为一
论文部分内容阅读
在电子商务网络、社交网络和生物网络等领域,图在表示网络中实体以及实体间的关系方面起着至关重要的作用。给定图中两个顶点s和t,图数据库中的一个基本问题是研究s和t之间的关系,而在该领域中一个很重要的研究方向是k跳约束下的的s点到t点的简单路径枚举问题。然而,所有针对此问题的现有算法都遵循基于DFS（深度优先搜索）框架,导致这些算法可伸缩性低下。此外,近十年来,使用FPGA等硬件设备加速图算法已成为一种流行的趋势。受以上认识启发,本文旨在研究并提出首个基于CPU-FPGA异构架构的算法PEFP,以有效解决k跳约束下的s-t简单路径枚举问题。在CPU端,本文开发了一个预处理算法Pre-BFS来减小图规模的大小和搜索空间。在FPGA端,本文设计了一种基于DFS的批处理技术,可有效节省FPGA片上内存空间的占用。此外,我们还采用缓存技术在FPGA BRAM（FPGA片上内存）中缓存部分必要的数据,以克服从FPGA DRAM（FPGA外存）进行读写操作带来的延迟瓶颈。最后,本文提出了一种数据解耦技术来实现路径验证模块流处理优化,使得该模块中的子阶段可以并行执行。本文在12个真实数据集上进行了大规模实验,实验结果显示,PEFP算法与现有最先进的CPU算法JOIN相比,在预处理时间、查询处理时间和总时间上平均有1个数量级的加速比,最高有2个数量级的加速比。
其他文献
电动车低能耗、低污染的特点以及全天路权开放和政府补贴政策共同促进了电动车在多个领域的快速发展,其中一个重要领域为医药冷链配送。但由于电池容量和基础设施的限制,纯电动冷藏车在配送途中存在续航里程短,充电和等待时间长的特性。如何在满足纯电动冷藏车的充电需求下,实现低碳下的利润最大化,成为医药冷链配送企业需要解决的新问题。基于此,本文提出了纯电动冷藏车的医药配送路径优化模型,该模型旨在实现包含环境和经济
二吡咯烯低聚物由于其能够为金属离子和有机分子提供结合位点,而受到广泛关注。其中二吡咯的硼络合物（BODIPY）是研究最多的二吡咯络合物之一。BODIPY在可见光区域具有很强的吸收及荧光量子效应,同时其具有较高的化学稳定性以及相对长的激发态寿命,使得其在荧光传感器、染料敏化太阳能电池等领域受到广泛的研究。同时卟啉是研究最广泛的含氮类大环芳香族化合物,由于其在紫外波长区间有优良的吸收和发射性能,使得其
在能源危机、环境污染和严苛的汽车尾气污染物排放法规的大背景下,混合动力汽车在提高燃油经济性和减少排放等方面具有显著优势;另一方面,智能交通系统的快速发展实现了混合动力汽车的网联化,将车联网技术与混合动力汽车的能量管理技术相结合,可以大幅度改善车辆的整体性能。本文针对一辆车联网环境下的混合动力汽车,在跟车场景下进行了考虑污染物排放的多目标能量管理优化,具体研究内容如下:（1）对一辆单轴并联式混合动力
随着社会的发展,对能源的需求不断增大,人们对风能,太阳能等新型可再生能源进行了很多研究并投入了应用,但可再生能源的电源系统往往存在负载扰动大,供电不稳定,准确建模困难等问题。而在现代的各种电子产品设计中,需要体积更小,质量更高的稳定电源。开关电源DC-DC变换器可以通过提高工作频率的方式来减小电路中储能元件体积,使得DC-DC变换器的体积更小,质量更轻,因此在各个领域受到了广泛的应用。由于滑模控制
地膜等农用塑料制品的大量使用导致农田土壤塑料残留,废弃塑料可进一步破碎化成微塑料（<5 mm）。作为新型污染物,微塑料具有数量多、尺寸小和比表面积大等特征,其对农田土壤生态环境具有潜在风险。揭示农田土壤微塑料污染特征,分析塑料地膜在土壤中次生微塑料的环境行为对阐明微塑料的生态环境风险十分重要。尽管目前已有地域性土壤中微塑料的报道,但全国尺度大范围农田土壤微塑料调查数据缺乏。另外,关于不同类型地膜在
近年来,随着人口的增长和工业的发展,各种外源性的新兴污染物伴随着人类的生产及生活行为不断地输入环境,使得生态系统的承载能力下降。长期以往下去,将对生态系统的稳定性与服务功能以及生物健康构成极大的威胁。因此,十分有必要针对环境中的新兴污染物或微生物污染标记物发展高灵敏、高时空分辨的环境分析检测平台。随着配位化学与超分子化学的结合与发展,金属有机配位聚合物（Metal-organic coordina
金属有机骨架（MOFs）是由金属离子/团簇)和具有自组装配位键的有机配体组成的多孔晶体材料。由于具有比表面积大、孔隙率高、结构和功能较好等优异特性使其在多个领域有着广泛的应用,例如:分离储存、催化、传感、生物医学等。特别是在传感领域,MOFs材料因具有发光,催化,磁性和选择性吸附等功能优于其他化学感应材料,已被广泛用于构造分析传感器。因此合理设计MOFs材料在拓展传感的发展方面有着十分重要的研究意
双离合器自动变速器（Dual Clutch Transmission,DCT）目前在汽车自动变速器领域得到了广泛关注。DCT与电控机械式无级变速器（Continuous Variable Transmission,CVT）和电控液力自动变速器（Automatic Transmission,AT）相比,具有结构简单、动力无中断、传动效率高、燃油经济性好以及制造成本低等优点。湿式离合器作为湿式DCT的
最高阶导数前带有小参数的微分方程或微分系统一直是动力系统研究的热点,并逐渐发展成为了其一个重要分支.当小参数趋于零甚至取零时,方程阶数的降低导致方程结构及相应的动力学行为发生本质的变化,这就产生了一个奇摄动问题,这样的问题还时常表现出多时间或空间尺度的特性.在奇摄动发展初期,大多时候关注点在于边值问题的渐近分析.1970s,N.Fenichel开创性的工作“Geometric Singular P
新生儿由于刚从母胎中脱离出来,其脑部极其容易受到伤害,而惊厥是最常见的新生儿脑功能异常。临床上,EEG信号是一种记录方便、记录成本低且能够一定程度反应大脑活动的信号,因此EEG信号常用于惊厥检测。但观察EEG信号需要耗费专家大量时间且非常容易出错。针对此问题,论文提出了一种结合深度特征与传统特征的惊厥检测模型。论文的主要工作和贡献有以下几点:第一,为了充分利用人类识别惊厥的经验,针对惊厥发作特性提