2021年 第58卷 第3期
2021, 58(3): 445-457.
DOI: 10.7544/issn1000-1239.2021.20180601
摘要：
稀疏矩阵向量乘和卷积作为高性能计算的两大计算核心, 是非规则和规则访存的典型代表.目前已经做了许多针对性的优化工作, 但是对于大量运行着不同指令集和拥有不同计算和访存性能的机器, 仍然无法判定在特定的体系结构下导致性能效率无法被完全释放的主要原因及性能瓶颈, 同时也很难准确预测出程序在特定机器上可达到的最佳性能.通过使用性能模型方法, 建模程序在真实机器上的运行细节, 可以得出更加精确的性能预测, 并且根据模型输出的反馈信息提出针对性的优化指导.提出了PPR(probability-process-ram)模型, 并在一个通用处理器上建模程序内指令执行和数据传输开销, 其中包括使用模型预测各种指令数量及内存层次之间的数据传输大小去分析程序各个阶段的性能瓶颈, 并且根据模型反馈的信息提出优化方案以及优化后的性能期望.最终使用PPR建模和优化2个计算核心, 同时也比较了与常用的Roofline和ECM模型的区别.
稀疏矩阵向量乘和卷积作为高性能计算的两大计算核心, 是非规则和规则访存的典型代表.目前已经做了许多针对性的优化工作, 但是对于大量运行着不同指令集和拥有不同计算和访存性能的机器, 仍然无法判定在特定的体系结构下导致性能效率无法被完全释放的主要原因及性能瓶颈, 同时也很难准确预测出程序在特定机器上可达到的最佳性能.通过使用性能模型方法, 建模程序在真实机器上的运行细节, 可以得出更加精确的性能预测, 并且根据模型输出的反馈信息提出针对性的优化指导.提出了PPR(probability-process-ram)模型, 并在一个通用处理器上建模程序内指令执行和数据传输开销, 其中包括使用模型预测各种指令数量及内存层次之间的数据传输大小去分析程序各个阶段的性能瓶颈, 并且根据模型反馈的信息提出优化方案以及优化后的性能期望.最终使用PPR建模和优化2个计算核心, 同时也比较了与常用的Roofline和ECM模型的区别.
2021, 58(3): 458-466.
DOI: 10.7544/issn1000-1239.2021.20200090
摘要：
大数据时代, Graph500是评测超级计算机处理数据密集型应用能力的重要工具, E级验证系统的图遍历处理能力主要受限于内存空间和访存带宽, 尤其是内存空间利用率直接决定了图的测试规模和测试性能.针对天河E级验证系统小内存特征, 提出了基于双向位图的大规模图数据压缩存储方法(bidirectional-bitmap based CSR, Bi-CSR), Bi-CSR在CSR矩阵压缩的基础上引入行方向位图和列方向位图协同完成稀疏矩阵压缩存储, 行方向位图主要负责行方向位图的压缩存储与索引, 列方向位图除了进一步压缩图存储空间, 还负责为顶点遍历向量并行优化提供加速空间.Bi-CSR大幅度减少了稀疏矩阵存储空间.面向天河E级验证系统, 当图输入规模为2\+\{37\}时, Graph500的图存储空间节约效率接近70%, 全系统稳定测试性能为2.131E+12TEPS, 性能最大加速比超过100倍.
大数据时代, Graph500是评测超级计算机处理数据密集型应用能力的重要工具, E级验证系统的图遍历处理能力主要受限于内存空间和访存带宽, 尤其是内存空间利用率直接决定了图的测试规模和测试性能.针对天河E级验证系统小内存特征, 提出了基于双向位图的大规模图数据压缩存储方法(bidirectional-bitmap based CSR, Bi-CSR), Bi-CSR在CSR矩阵压缩的基础上引入行方向位图和列方向位图协同完成稀疏矩阵压缩存储, 行方向位图主要负责行方向位图的压缩存储与索引, 列方向位图除了进一步压缩图存储空间, 还负责为顶点遍历向量并行优化提供加速空间.Bi-CSR大幅度减少了稀疏矩阵存储空间.面向天河E级验证系统, 当图输入规模为2\+\{37\}时, Graph500的图存储空间节约效率接近70%, 全系统稳定测试性能为2.131E+12TEPS, 性能最大加速比超过100倍.
2021, 58(3): 467-478.
DOI: 10.7544/issn1000-1239.2021.20190679
摘要：
图计算已成为大数据处理领域的主流应用, 采用特定硬件加速可以显著提高图计算的性能和能效.众所周知, 硬件代码的编写和验证十分耗时, 尽管通用高层次综合(high level synthesis, HLS)系统允许用户使用高级语言(如C语言)特性自动生成硬件结构, 但是对于图计算这种不规则算法, 其仍缺乏有效的并行性和访存技术支撑, 存在综合效果不理想、效率不高等突出问题.提出一种面向图计算的高效HLS方法, 结合图算法嵌套循环、随机访存、数据冲突以及幂律分布等特性, 采用数据流架构实现高效的并行流水线, 保证处理单元的负载均衡.通过提供的编程原语, 提出的方法可将通用图算法转化为模块化的数据流中间表示形式, 进而映射到参数化的硬件模板.在Xilinx Virtex UltraScale+XCVU9P的实现验证了方法的正确性, 不同类型的图算法在多个数据集上的实验结果表明, 相比国际上通用的Spatial HLS系统, 提出的方法可达到7.9~30.6倍的性能提升.
图计算已成为大数据处理领域的主流应用, 采用特定硬件加速可以显著提高图计算的性能和能效.众所周知, 硬件代码的编写和验证十分耗时, 尽管通用高层次综合(high level synthesis, HLS)系统允许用户使用高级语言(如C语言)特性自动生成硬件结构, 但是对于图计算这种不规则算法, 其仍缺乏有效的并行性和访存技术支撑, 存在综合效果不理想、效率不高等突出问题.提出一种面向图计算的高效HLS方法, 结合图算法嵌套循环、随机访存、数据冲突以及幂律分布等特性, 采用数据流架构实现高效的并行流水线, 保证处理单元的负载均衡.通过提供的编程原语, 提出的方法可将通用图算法转化为模块化的数据流中间表示形式, 进而映射到参数化的硬件模板.在Xilinx Virtex UltraScale+XCVU9P的实现验证了方法的正确性, 不同类型的图算法在多个数据集上的实验结果表明, 相比国际上通用的Spatial HLS系统, 提出的方法可达到7.9~30.6倍的性能提升.
2021, 58(3): 479-496.
DOI: 10.7544/issn1000-1239.2021.20200489
摘要：
作为目前主流的大数据流式计算平台之一, Storm在设计之初以性能为目的进行研究而忽视了高能耗的问题, 但是其高能耗问题已经开始制约着平台的发展.针对这一问题, 分别建立了任务分配模型、拓扑信息监控模型、数据恢复模型以及能耗模型, 并进一步提出了基于Storm平台的数据恢复节能策略(energy-efficient strategy based on data recovery in Storm, DR-Storm), 包括吞吐量检测算法与数据恢复算法.其中吞吐量检测算法根据拓扑信息监控模型反馈的拓扑信息计算集群吞吐量, 并通过信息反馈判断是否终止整个集群内拓扑的任务.数据恢复算法根据数据恢复模型选择备份节点用于数据存储, 并通过拓扑信息监控模型反馈的信息判断集群拓扑是否进行数据恢复.此外, DR-Storm通过备份节点内存恢复集群拓扑内的数据, 并根据大数据流式计算的系统延迟与能效评估DR-Storm.实验结果表明：与现有研究成果相比, DR-Storm在减少系统计算延迟、降低集群功率的同时, 有效节约了能耗.
作为目前主流的大数据流式计算平台之一, Storm在设计之初以性能为目的进行研究而忽视了高能耗的问题, 但是其高能耗问题已经开始制约着平台的发展.针对这一问题, 分别建立了任务分配模型、拓扑信息监控模型、数据恢复模型以及能耗模型, 并进一步提出了基于Storm平台的数据恢复节能策略(energy-efficient strategy based on data recovery in Storm, DR-Storm), 包括吞吐量检测算法与数据恢复算法.其中吞吐量检测算法根据拓扑信息监控模型反馈的拓扑信息计算集群吞吐量, 并通过信息反馈判断是否终止整个集群内拓扑的任务.数据恢复算法根据数据恢复模型选择备份节点用于数据存储, 并通过拓扑信息监控模型反馈的信息判断集群拓扑是否进行数据恢复.此外, DR-Storm通过备份节点内存恢复集群拓扑内的数据, 并根据大数据流式计算的系统延迟与能效评估DR-Storm.实验结果表明：与现有研究成果相比, DR-Storm在减少系统计算延迟、降低集群功率的同时, 有效节约了能耗.
2021, 58(3): 497-512.
DOI: 10.7544/issn1000-1239.2021.20200501
摘要：
集中式集群资源管理系统既能够确保全局资源状态的一致性亦拥有多种调度模型, 因此被广泛应用于实际系统中.但是, 当集中式资源管理器在接收并处理大规模的周期性心跳信息时, 由于其采用单一节点来维护全局资源状态, 所以资源管理器的负载压力急剧增加, 导致调度能力降低, 影响了集群系统的可扩展性.针对上述问题, 提出一种“没有变化就不更新”的思想, 取代集中资源管理的定时更新机制, 改善了集中式资源管理系统的可扩展性.首先, 通过计算节点引入基于差分的心跳信息处理模型, 使得未发生状态变化的节点不必发送心跳消息, 从而减少消息发送的规模和次数； 其次, 针对节点宕机监测过程, 提出基于环形监视的节点监控模型, 让各个计算节点之间互相监视对方的宕机状态, 从而将周期性监测压力转移到计算节点； 最后, 给出这2种模型在集中式资源管理系统YARN上的实现, 并针对改进前后的系统进行实验测试.通过实验验证, 当集群达到1万个节点且心跳时间间隔3 s时, 改进后YARN系统的心跳信息处理效率以及资源更新效率相比原YARN系统提高40%左右.另外, 改进后YARN系统管理集群节点规模相比原YARN系统扩大1.88倍以上.
集中式集群资源管理系统既能够确保全局资源状态的一致性亦拥有多种调度模型, 因此被广泛应用于实际系统中.但是, 当集中式资源管理器在接收并处理大规模的周期性心跳信息时, 由于其采用单一节点来维护全局资源状态, 所以资源管理器的负载压力急剧增加, 导致调度能力降低, 影响了集群系统的可扩展性.针对上述问题, 提出一种“没有变化就不更新”的思想, 取代集中资源管理的定时更新机制, 改善了集中式资源管理系统的可扩展性.首先, 通过计算节点引入基于差分的心跳信息处理模型, 使得未发生状态变化的节点不必发送心跳消息, 从而减少消息发送的规模和次数； 其次, 针对节点宕机监测过程, 提出基于环形监视的节点监控模型, 让各个计算节点之间互相监视对方的宕机状态, 从而将周期性监测压力转移到计算节点； 最后, 给出这2种模型在集中式资源管理系统YARN上的实现, 并针对改进前后的系统进行实验测试.通过实验验证, 当集群达到1万个节点且心跳时间间隔3 s时, 改进后YARN系统的心跳信息处理效率以及资源更新效率相比原YARN系统提高40%左右.另外, 改进后YARN系统管理集群节点规模相比原YARN系统扩大1.88倍以上.
2021, 58(3): 513-527.
DOI: 10.7544/issn1000-1239.2021.20200402
摘要：
电子病历是医院信息化发展的产物, 其中包含了丰富的医疗信息和临床知识, 是辅助临床决策和药物挖掘等的重要资源.因此, 如何高效地挖掘大量电子病历数据中的信息是一个重要的研究课题.近些年来, 随着计算机技术尤其是机器学习以及深度学习的蓬勃发展, 对电子病历这一特殊领域数据的挖掘有了更高的要求.电子病历综述旨在通过对电子病历研究现状的分析来指导未来电子病历文本挖掘领域的发展.具体而言, 综述首先介绍了电子病历数据的特点和电子病历的数据预处理的常用方法； 然后总结了电子病历数据挖掘的4个典型任务(医学命名实体识别、关系抽取、文本分类和智能问诊), 并且围绕典型任务介绍了常用的基本模型以及研究人员在任务上的部分探索； 最后结合糖尿病和心脑血管疾病2类特定疾病, 对电子病历的现有应用场景做了简单介绍.
电子病历是医院信息化发展的产物, 其中包含了丰富的医疗信息和临床知识, 是辅助临床决策和药物挖掘等的重要资源.因此, 如何高效地挖掘大量电子病历数据中的信息是一个重要的研究课题.近些年来, 随着计算机技术尤其是机器学习以及深度学习的蓬勃发展, 对电子病历这一特殊领域数据的挖掘有了更高的要求.电子病历综述旨在通过对电子病历研究现状的分析来指导未来电子病历文本挖掘领域的发展.具体而言, 综述首先介绍了电子病历数据的特点和电子病历的数据预处理的常用方法； 然后总结了电子病历数据挖掘的4个典型任务(医学命名实体识别、关系抽取、文本分类和智能问诊), 并且围绕典型任务介绍了常用的基本模型以及研究人员在任务上的部分探索； 最后结合糖尿病和心脑血管疾病2类特定疾病, 对电子病历的现有应用场景做了简单介绍.
2021, 58(3): 528-538.
DOI: 10.7544/issn1000-1239.2021.20200288
摘要：
针对非可控环境下人脸表情识别面临的诸如种族、性别和年龄等因子变化问题, 提出一种基于深度条件随机森林的鲁棒性人脸表情识别方法.与传统的单任务人脸表情识别方法不同, 设计了一种以人脸表情识别为主, 人脸性别和年龄属性识别为辅的多任务识别模型.在研究中发现, 人脸性别和年龄等属性对人脸表情识别有一定的影响, 为了捕获它们之间的关系, 提出一种基于人脸性别和年龄双属性的深度条件随机森林人脸表情识别方法.在特征提取阶段, 采用多示例注意力机制进行人脸特征提取以便去除诸如光照、遮挡和低分辨率等变化问题； 在人脸表情识别阶段, 根据人脸性别和年龄双属性因子, 采用多条件随机森林方法进行人脸表情识别.在公开的CK+, ExpW, RAF-DB, AffectNet人脸表情数据库上进行了大量实验：在经典的CK+人脸库上达到99%识别率, 在具有挑战性的自然场景库(ExpW, RAF-DB, AffectNet组合库)上达到70.52%的识别率.实验结果表明：与其他方法相比具有先进性, 对自然场景中的遮挡、噪声和分辨率变化具有一定的鲁棒性.
针对非可控环境下人脸表情识别面临的诸如种族、性别和年龄等因子变化问题, 提出一种基于深度条件随机森林的鲁棒性人脸表情识别方法.与传统的单任务人脸表情识别方法不同, 设计了一种以人脸表情识别为主, 人脸性别和年龄属性识别为辅的多任务识别模型.在研究中发现, 人脸性别和年龄等属性对人脸表情识别有一定的影响, 为了捕获它们之间的关系, 提出一种基于人脸性别和年龄双属性的深度条件随机森林人脸表情识别方法.在特征提取阶段, 采用多示例注意力机制进行人脸特征提取以便去除诸如光照、遮挡和低分辨率等变化问题； 在人脸表情识别阶段, 根据人脸性别和年龄双属性因子, 采用多条件随机森林方法进行人脸表情识别.在公开的CK+, ExpW, RAF-DB, AffectNet人脸表情数据库上进行了大量实验：在经典的CK+人脸库上达到99%识别率, 在具有挑战性的自然场景库(ExpW, RAF-DB, AffectNet组合库)上达到70.52%的识别率.实验结果表明：与其他方法相比具有先进性, 对自然场景中的遮挡、噪声和分辨率变化具有一定的鲁棒性.
2021, 58(3): 539-547.
DOI: 10.7544/issn1000-1239.2021.20200324
摘要：
信用欺诈数据分布极度不均衡时, 信息失真、周期性统计误差和报告偏倚所产生的噪声错误对训练模型干扰凸显, 且易产生过拟合现象.鉴于此, 提出一种深度信念神经网络集成算法来解决类极度不均衡的信用欺诈问题.首先, 提出双向联合采样算法克服信息缺失和过拟合问题； 然后, 构造2阶段基分类器簇, 针对支持向量机(support vector machine, SVM)对不均衡数据分布所表现的分类超平面向少数类偏移问题, 利用增强(boosting)算法生成SVM与随机森林(random forest, RF)结合的基分类器簇； 利用深度信念网络(deep belief network, DBN)整合基分类器簇的多元预测, 输出分类结果.考虑传统精度评价指标过度关注多数类样本, 忽视信用欺诈存在违约损失高于利息收益事实, 引入成本-效益指数兼顾正类和负类样本的识别能力, 提高模型对少数类样本预测精度.通过对欧洲信用卡欺诈数据检测发现, 相比于其他相关算法成本-效益指数均值提高3个百分点, 同时, 实验比较样本不均衡比例对算法精度影响, 结果表明在处理极端不均衡数据时所提算法效果更优.
信用欺诈数据分布极度不均衡时, 信息失真、周期性统计误差和报告偏倚所产生的噪声错误对训练模型干扰凸显, 且易产生过拟合现象.鉴于此, 提出一种深度信念神经网络集成算法来解决类极度不均衡的信用欺诈问题.首先, 提出双向联合采样算法克服信息缺失和过拟合问题； 然后, 构造2阶段基分类器簇, 针对支持向量机(support vector machine, SVM)对不均衡数据分布所表现的分类超平面向少数类偏移问题, 利用增强(boosting)算法生成SVM与随机森林(random forest, RF)结合的基分类器簇； 利用深度信念网络(deep belief network, DBN)整合基分类器簇的多元预测, 输出分类结果.考虑传统精度评价指标过度关注多数类样本, 忽视信用欺诈存在违约损失高于利息收益事实, 引入成本-效益指数兼顾正类和负类样本的识别能力, 提高模型对少数类样本预测精度.通过对欧洲信用卡欺诈数据检测发现, 相比于其他相关算法成本-效益指数均值提高3个百分点, 同时, 实验比较样本不均衡比例对算法精度影响, 结果表明在处理极端不均衡数据时所提算法效果更优.
2021, 58(3): 548-568.
DOI: 10.7544/issn1000-1239.2021.20200360
摘要：
图像隐写是信息安全领域的研究热点之一.早期隐写方法通过修改载体图像获得含密图像, 导致图像统计特性发生变化, 因此难以抵抗基于高维统计特征分析的检测.随着深度学习的发展, 研究者们提出了许多基于深度学习的图像隐写方法, 使像素修改更隐蔽、隐写过程更智能.为了更好地研究图像隐写技术, 对基于深度学习的图像隐写方法进行综述.首先根据图像隐写过程, 从3个方面分析了基于深度学习的图像隐写方法:1)从生成对抗网络和对抗样本2个角度介绍载体图像获取方法； 2)分析基于深度学习的隐写失真设计方法； 3)阐述基于编码-解码网络的含密图像生成方法.然后, 分析和总结了无载体图像隐写方法的优缺点, 该类方法无需载体图像即可实现图像隐写, 因此在对抗统计分析方面存在天然优势.最后, 在深入分析与总结基于深度学习的图像隐写与无载体图像隐写2类方法优缺点的基础上, 对图像隐写的发展方向进行了探讨与展望.
图像隐写是信息安全领域的研究热点之一.早期隐写方法通过修改载体图像获得含密图像, 导致图像统计特性发生变化, 因此难以抵抗基于高维统计特征分析的检测.随着深度学习的发展, 研究者们提出了许多基于深度学习的图像隐写方法, 使像素修改更隐蔽、隐写过程更智能.为了更好地研究图像隐写技术, 对基于深度学习的图像隐写方法进行综述.首先根据图像隐写过程, 从3个方面分析了基于深度学习的图像隐写方法:1)从生成对抗网络和对抗样本2个角度介绍载体图像获取方法； 2)分析基于深度学习的隐写失真设计方法； 3)阐述基于编码-解码网络的含密图像生成方法.然后, 分析和总结了无载体图像隐写方法的优缺点, 该类方法无需载体图像即可实现图像隐写, 因此在对抗统计分析方面存在天然优势.最后, 在深入分析与总结基于深度学习的图像隐写与无载体图像隐写2类方法优缺点的基础上, 对图像隐写的发展方向进行了探讨与展望.
2021, 58(3): 569-582.
DOI: 10.7544/issn1000-1239.2021.20200448
摘要：
兴趣泛洪攻击(interest flooding attack, IFA)和合谋兴趣泛洪攻击(conspiracy interest flooding attack, CIFA)是命名数据网络(named data networking, NDN)面临的典型的安全威胁.针对现有检测方法的检测特征单一因此不能有效地辨别攻击种类以及检测率不够高等问题, 提出一种基于关联规则算法和决策树算法联合检测NDN中攻击的方法.首先, 通过提取NDN路由节点的内容缓存(content cache, CS)中的数据信息挖掘CS中新的检测特征“缓存增长率”, 实验发现“CS数据包增长率”是辨别IFA还是CIFA的有利依据.其次, 使用关联规则算法将新的检测特征与待定兴趣表(pending interest table, PIT)中多个检测特征联合, 寻找各个特征之间的关联性并将其作为决策树的输入.最后, 使用决策树算法检测攻击.该方法使用决策树算法和关联规则算法联合检测NDN中的攻击, 不仅避免了单一特征检测攻击造成的误判并且丰富了决策树的分类属性.分析仿真结果表明该检测方法可以精确地区分并检测IFA和CIFA并且提高了检测率.
兴趣泛洪攻击(interest flooding attack, IFA)和合谋兴趣泛洪攻击(conspiracy interest flooding attack, CIFA)是命名数据网络(named data networking, NDN)面临的典型的安全威胁.针对现有检测方法的检测特征单一因此不能有效地辨别攻击种类以及检测率不够高等问题, 提出一种基于关联规则算法和决策树算法联合检测NDN中攻击的方法.首先, 通过提取NDN路由节点的内容缓存(content cache, CS)中的数据信息挖掘CS中新的检测特征“缓存增长率”, 实验发现“CS数据包增长率”是辨别IFA还是CIFA的有利依据.其次, 使用关联规则算法将新的检测特征与待定兴趣表(pending interest table, PIT)中多个检测特征联合, 寻找各个特征之间的关联性并将其作为决策树的输入.最后, 使用决策树算法检测攻击.该方法使用决策树算法和关联规则算法联合检测NDN中的攻击, 不仅避免了单一特征检测攻击造成的误判并且丰富了决策树的分类属性.分析仿真结果表明该检测方法可以精确地区分并检测IFA和CIFA并且提高了检测率.
2021, 58(3): 583-597.
DOI: 10.7544/issn1000-1239.2021.20200321
摘要：
顾名思义, 前向安全的代理签名具备前向安全性和可代理性, 因而, 自提出以来, 已被广泛应用在移动通信、电子拍卖等众多应用场景中.目前现有的前向安全的代理签名基本上都是基于离散对数难题亦或是大整数分解问题.而这些问题随着量子计算机逐渐成为现实, 将会变得不再困难.因而, 寻找量子计算环境下前向安全的代理签名已迫在眉睫.现存的量子安全的公钥密码体制有4类, 分别为基于Hash的密码体制、基于编码的密码体制、多变量公钥密码体制以及格公钥密码体制.在这4类公钥密码体制中, 格公钥密码以其量子免疫性, 计算简单高效, 任意实例下的安全性和最坏实例下的安全性相当等优势在近10年得到了快速发展, 并已经取得了显著成就.在格上引入前向安全的代理签名这一概念并给出其安全性模型, 基于格上已知NP困难的小整数解问题(small integer solution, SIS)提出了2个前向安全的格基代理签名.在这2个签名中, 其中1个签名在随机预言机模型下被证明是不可伪造的, 能够抵抗恶意原始签名人和未被授权代理签名人攻击, 且与之前格基代理签名相比较, 以牺牲效率为代价, 达到了实现前向安全性的目的； 另外1个签名在标准模型下是安全的, 且能实现前向安全性.
顾名思义, 前向安全的代理签名具备前向安全性和可代理性, 因而, 自提出以来, 已被广泛应用在移动通信、电子拍卖等众多应用场景中.目前现有的前向安全的代理签名基本上都是基于离散对数难题亦或是大整数分解问题.而这些问题随着量子计算机逐渐成为现实, 将会变得不再困难.因而, 寻找量子计算环境下前向安全的代理签名已迫在眉睫.现存的量子安全的公钥密码体制有4类, 分别为基于Hash的密码体制、基于编码的密码体制、多变量公钥密码体制以及格公钥密码体制.在这4类公钥密码体制中, 格公钥密码以其量子免疫性, 计算简单高效, 任意实例下的安全性和最坏实例下的安全性相当等优势在近10年得到了快速发展, 并已经取得了显著成就.在格上引入前向安全的代理签名这一概念并给出其安全性模型, 基于格上已知NP困难的小整数解问题(small integer solution, SIS)提出了2个前向安全的格基代理签名.在这2个签名中, 其中1个签名在随机预言机模型下被证明是不可伪造的, 能够抵抗恶意原始签名人和未被授权代理签名人攻击, 且与之前格基代理签名相比较, 以牺牲效率为代价, 达到了实现前向安全性的目的； 另外1个签名在标准模型下是安全的, 且能实现前向安全性.
2021, 58(3): 598-608.
DOI: 10.7544/issn1000-1239.2021.20190567
摘要：
相似性连接技术在数据清洗、数据集成等领域中具有重要意义, 近年来引起了学术界的广泛关注.随着数据量的不断增大、数据处理实时性的要求逐渐提高以及处理器性能提升瓶颈的出现, 传统的串行相似性连接方法已经不能满足当前大数据处理的需求.近些年, GPU作为协处理器在机器学习等领域取得了良好的加速效果, 因此基于GPU的并行算法开始成为解决各类性能问题的有效解决方案.为此, 提出了基于CPU-GPU异构体系的并行相似性连接方法.首先, 方法使用GPU构建倒排索引, 索引采用SoA(struct of arrays)结构, 从而解决了传统索引结构在并行模式下读写效率低的问题.其次, 针对串行算法的性能问题, 提出基于过滤验证框架的并行双重长度过滤算法, 其中利用前缀过滤和构建好的倒排索引提升过滤效果.方法中相似度精确计算验证过程使用CPU计算执行, 从而充分利用CPU-GPU的异构计算资源.最后, 在多个数据集上进行实验验证性能.通过与串行相似性连接算法进行对比, 实验结果表明所提出方法相对于已有方法具有更好的过滤效果和更低的索引生成代价, 并在相似性连接上具有更好的性能和良好的加速比.
相似性连接技术在数据清洗、数据集成等领域中具有重要意义, 近年来引起了学术界的广泛关注.随着数据量的不断增大、数据处理实时性的要求逐渐提高以及处理器性能提升瓶颈的出现, 传统的串行相似性连接方法已经不能满足当前大数据处理的需求.近些年, GPU作为协处理器在机器学习等领域取得了良好的加速效果, 因此基于GPU的并行算法开始成为解决各类性能问题的有效解决方案.为此, 提出了基于CPU-GPU异构体系的并行相似性连接方法.首先, 方法使用GPU构建倒排索引, 索引采用SoA(struct of arrays)结构, 从而解决了传统索引结构在并行模式下读写效率低的问题.其次, 针对串行算法的性能问题, 提出基于过滤验证框架的并行双重长度过滤算法, 其中利用前缀过滤和构建好的倒排索引提升过滤效果.方法中相似度精确计算验证过程使用CPU计算执行, 从而充分利用CPU-GPU的异构计算资源.最后, 在多个数据集上进行实验验证性能.通过与串行相似性连接算法进行对比, 实验结果表明所提出方法相对于已有方法具有更好的过滤效果和更低的索引生成代价, 并在相似性连接上具有更好的性能和良好的加速比.
2021, 58(3): 609-623.
DOI: 10.7544/issn1000-1239.2021.20200285
摘要：
针对现有的高维空间近似k近邻查询算法在数据降维时不考虑维度间关联关系的问题, 首次提出了基于维度间关联规则进行维度分组降维的方法.该方法通过将相关联维度分成一组进行降维来减少数据信息的损失, 同时针对Hash降维后产生的数据偏移问题, 设置了符号位并基于符号位的特性对结果进行精炼； 为提高维度间关联规则挖掘的效率, 提出了一种新的基于UFP-tree的频繁项集挖掘算法.通过将数据映射成二进制编码来进行查询, 有效地提高了近似k近邻查询效率, 同时基于信息熵筛选编码函数, 提高了编码质量； 在查询结果精炼的过程, 基于信息熵对候选集数据的编码位进行权重的动态设定, 通过比较动态加权汉明距离和符号位碰撞次数返回最终近似k近邻结果.理论和实验研究表明, 所提方法能够较好地处理高维空间中近似k近邻查询问题.
针对现有的高维空间近似k近邻查询算法在数据降维时不考虑维度间关联关系的问题, 首次提出了基于维度间关联规则进行维度分组降维的方法.该方法通过将相关联维度分成一组进行降维来减少数据信息的损失, 同时针对Hash降维后产生的数据偏移问题, 设置了符号位并基于符号位的特性对结果进行精炼； 为提高维度间关联规则挖掘的效率, 提出了一种新的基于UFP-tree的频繁项集挖掘算法.通过将数据映射成二进制编码来进行查询, 有效地提高了近似k近邻查询效率, 同时基于信息熵筛选编码函数, 提高了编码质量； 在查询结果精炼的过程, 基于信息熵对候选集数据的编码位进行权重的动态设定, 通过比较动态加权汉明距离和符号位碰撞次数返回最终近似k近邻结果.理论和实验研究表明, 所提方法能够较好地处理高维空间中近似k近邻查询问题.
2021, 58(3): 624-637.
DOI: 10.7544/issn1000-1239.2021.20200319
摘要：
基于本地差分隐私的用户数据收集与分析算法已延伸到了键-值数据类型.然而, 该类数据值域大小与稀疏性以及本地扰动机制直接制约着收集与分析精度.针对现有机制难以有效应对该类数据收集的不足, 提出了一种基于直方图技术的有效收集与分析算法HISKV(histogram-based key-value data collection), 该算法首先结合用户分组策略寻找最优截断长度, 利用最优截断-抽样技术处理值域过大与稀疏性问题, 然后结合截断结果随机抽取单个键-值对进行离散化处理.针对离散化结果, 设计一种高效的本地扰动机制LRR_KV(local random response for key-value data), 该机制结合具体的键分配不同的本地扰动概率.每个用户利用LRR_KV机制扰动离散化的键-值对之后发送给收集者, 收集者结合用户的报告值对每个键的频率及其值所对应的均值进行估计.理论分析了HISKV算法的无偏性、所产生的方差以及最大偏差, 并与现有的键-值收集算法在真实与合成的数据集上进行比较, 实验结果表明HISKV算法优于同类算法.
基于本地差分隐私的用户数据收集与分析算法已延伸到了键-值数据类型.然而, 该类数据值域大小与稀疏性以及本地扰动机制直接制约着收集与分析精度.针对现有机制难以有效应对该类数据收集的不足, 提出了一种基于直方图技术的有效收集与分析算法HISKV(histogram-based key-value data collection), 该算法首先结合用户分组策略寻找最优截断长度, 利用最优截断-抽样技术处理值域过大与稀疏性问题, 然后结合截断结果随机抽取单个键-值对进行离散化处理.针对离散化结果, 设计一种高效的本地扰动机制LRR_KV(local random response for key-value data), 该机制结合具体的键分配不同的本地扰动概率.每个用户利用LRR_KV机制扰动离散化的键-值对之后发送给收集者, 收集者结合用户的报告值对每个键的频率及其值所对应的均值进行估计.理论分析了HISKV算法的无偏性、所产生的方差以及最大偏差, 并与现有的键-值收集算法在真实与合成的数据集上进行比较, 实验结果表明HISKV算法优于同类算法.
2021, 58(3): 638-650.
DOI: 10.7544/issn1000-1239.2021.20200298
摘要：
程序生成是人工智能的核心研究问题之一, 当前输入-输出样例驱动的神经网络模型是非常流行的研究方法.面临的主要挑战是泛化能力差、生成程序准确率保证、难以处理复杂程序结构(如分支、循环、递归等), 主要原因是模型的输入信息单一(输入-输出对)和完全依赖神经网络.显然单一地通过输入输出样例倒推程序行为存在歧义性, 而神经网络的记忆容量很难满足常规程序的变量存储需求.提出一种人工与神经网络生成相协作的编程模型, 融合神经网络和程序员各自的优势, 其中程序员用高级编程语法编写程序框架, 神经网络自动学习生成程序局部的琐碎细节, 从而促进自动化程序生成方法更好地应对实际应用挑战.实验表明, 研究方法是有效的, 跟同类代表性研究方法相比表现出更好的学习性能.
程序生成是人工智能的核心研究问题之一, 当前输入-输出样例驱动的神经网络模型是非常流行的研究方法.面临的主要挑战是泛化能力差、生成程序准确率保证、难以处理复杂程序结构(如分支、循环、递归等), 主要原因是模型的输入信息单一(输入-输出对)和完全依赖神经网络.显然单一地通过输入输出样例倒推程序行为存在歧义性, 而神经网络的记忆容量很难满足常规程序的变量存储需求.提出一种人工与神经网络生成相协作的编程模型, 融合神经网络和程序员各自的优势, 其中程序员用高级编程语法编写程序框架, 神经网络自动学习生成程序局部的琐碎细节, 从而促进自动化程序生成方法更好地应对实际应用挑战.实验表明, 研究方法是有效的, 跟同类代表性研究方法相比表现出更好的学习性能.
2021, 58(3): 651-667.
DOI: 10.7544/issn1000-1239.2021.20200186
摘要：
Linux内核提供了灵活的内核配置项机制, 便于针对不同的应用场景进行个性化定制.但内核配置项的数量巨大且增长快速, 配置项的默认值在不同内核版本中经常改变, 即使专业的内核团队设置配置项也面临很多挑战.针对上述问题, 提出基于多标签的内核配置图, 该图包含内核配置项间的依赖关系、功能标签、性能标签、安全标签和配置项使能率.此外, 该图提供了可视化功能, 更加直观、高效、人性化.该内核配置图在内核配置项异常值检测、内核启动优化、内核裁剪、内核安全增强、内核性能优化、内核配置项智能问答等场景均可应用.且将内核配置图应用到检索场景, 实现了面向内核配置项的检索框架KCIR(kernel config information retrieval), 该框架基于内核配置图对查询语句和内核配置项描述文本进行了扩展, 实验评估表明KCIR和传统检索框架相比, 检索效果有显著提升, 验证了内核配置图在实际应用中的有效性和实用性.
Linux内核提供了灵活的内核配置项机制, 便于针对不同的应用场景进行个性化定制.但内核配置项的数量巨大且增长快速, 配置项的默认值在不同内核版本中经常改变, 即使专业的内核团队设置配置项也面临很多挑战.针对上述问题, 提出基于多标签的内核配置图, 该图包含内核配置项间的依赖关系、功能标签、性能标签、安全标签和配置项使能率.此外, 该图提供了可视化功能, 更加直观、高效、人性化.该内核配置图在内核配置项异常值检测、内核启动优化、内核裁剪、内核安全增强、内核性能优化、内核配置项智能问答等场景均可应用.且将内核配置图应用到检索场景, 实现了面向内核配置项的检索框架KCIR(kernel config information retrieval), 该框架基于内核配置图对查询语句和内核配置项描述文本进行了扩展, 实验评估表明KCIR和传统检索框架相比, 检索效果有显著提升, 验证了内核配置图在实际应用中的有效性和实用性.
2021, 58(3): 668-680.
DOI: 10.7544/issn1000-1239.2021.20190728
摘要：
编译器性能是计算机系统架构充分发挥优势的体现, 编译器优化受机器平台与编译器特征的影响.编译器分析是在目标编译器与多参照编译器、目标平台与多参照平台之间进行的, 即编译器与平台的组合是分析的基础.只有在多组合情况下才能为目标编译器优化提供最大可能的性能提升空间和详细的优化方案, 但增加编译器与平台的组合往往会增加无法计量的分析工作量.为此, 提出了一种基于峰值架构的面向跨平台跨编译器分析方法.基于峰值架构集为目标编译器构建理想性能空间, 结合细粒度优势优化定位技术为目标编译器提供优势优化选项和优化方向, 并实现编译器优化.最后通过实验验证了该分析技术的实用性与普适性, 并为Intel平台上的目标编译器gcc提供了优化方向.
编译器性能是计算机系统架构充分发挥优势的体现, 编译器优化受机器平台与编译器特征的影响.编译器分析是在目标编译器与多参照编译器、目标平台与多参照平台之间进行的, 即编译器与平台的组合是分析的基础.只有在多组合情况下才能为目标编译器优化提供最大可能的性能提升空间和详细的优化方案, 但增加编译器与平台的组合往往会增加无法计量的分析工作量.为此, 提出了一种基于峰值架构的面向跨平台跨编译器分析方法.基于峰值架构集为目标编译器构建理想性能空间, 结合细粒度优势优化定位技术为目标编译器提供优势优化选项和优化方向, 并实现编译器优化.最后通过实验验证了该分析技术的实用性与普适性, 并为Intel平台上的目标编译器gcc提供了优化方向.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
