摘要:连续动力系统安全验证是一个重要的研究问题, 多年来各类验证方法所能处理的问题规模非常受限. 对此, 对于给定的连续动力系统, 提出通过反例制导方法生成一组组合式概率近似正确(PAC)障碍证书的算法, 最终给出无限时间范畴安全验证问题在概率统计意义下的形式化描述. 通过建立和求解基于大M法的混合整数规划方法, 将障碍证书的求解转化为约束优化问题. 通过微分中值定理将非线性不等式进行区间线性化. 最后, 实现组合式PAC障碍证书生成工具CPBC, 并在11个基准系统上评估其性能. 实验结果表明, CPBC均能成功验证每个动力系统在指定不同的安全需求阈值下的安全性. 与现有方法相比, 所提方法可以更高效地为复杂系统或高维系统生成可靠的概率障碍证书, 验证的样例规模已高达百维.

摘要:软件可追踪性被认为是软件开发过程可信的一个重要因素, 确保对软件开发过程的可见性并进行全面追踪, 从而提高软件的可信度和可靠性. 近年来, 自动化的软件可追踪性恢复方法取得了显著进展, 但在企业项目中的应用仍面临挑战. 通过调研研究和实验案例分析, 发现工业界场景中可追踪性模型表现不佳的3个关键挑战: 原始数据低质量、样本稀疏性和不平衡性, 并提出一种结合主动学习和半监督学习的软件可追踪性恢复框架STRACE(AL+SSL). 该框架通过选择有价值的标注样本和生成高质量的伪标签样本, 有效利用未标注的样本, 克服数据低质量和稀疏性挑战. 实验基于10个样本规模在几万至近百万个issue-commit跟踪对实例的企业项目, 进行多组对比实验, 结果表明该框架在当前真实企业项目软件可追踪性恢复任务上具有有效性. 其中消融实验结果表明STRACE(AL+SSL)中主动学习模块所选择的无标签样本在可追踪性恢复任务中发挥了更为重要的作用. 此外, 还验证各个模块最佳的样本选择策略组合, 包括调整后的半监督类平衡自训练样本选择策略CBST-Adjust和低成本高效率的主动学习子模块互信息SMI_Flqmi样本选择策略.

摘要:服务描述中包含的应用场景信息有限, 使得以功能相似度计算为主的Mashup服务组件Web API推荐与需求预期常存在差异, 功能匹配精确度有待进一步提高. 部分研究者虽利用Web API的协作关联提升推荐兼容性, 但忽视了功能关联对Mashup服务创建的负反馈影响, 从而限制了推荐多样性的提升. 为此, 提出一种融合潜在联合词与异质关联兼容的Mashup服务的组件Web API推荐方法. 该方法为Mashup需求和Web API提取潜在应用场景联合词并融入到功能向量的生成中, 进而提高二者功能相似度的匹配精确度, 以获得高质量的候选组件Web API集合. 将功能关联与协作关联建模为异质服务关联, 并利用异质关联兼容替代传统方法中的协作兼容, 以提升Web API的推荐多样性. 相较于对比方法, 所提方法在评价指标Recall、Precision和NDCG上分别提升了4.17%–16.05%, 4.46%–16.62%与5.57%–17.26%, 多样性指标ILS降低了8.22%–15.23%. 冷启动Web API推荐的Recall与Precision指标值分别为非冷启动Web API推荐的47.71%和46.58%. 实验结果表明所提方法不仅提升了Web API推荐质量, 而且对冷启动Web API具有很好的推荐效果.

摘要:服务器无感知计算是一种新兴的云计算范型, 它允许开发者专注于应用逻辑的开发, 而不需要负责底层复杂的任务管理. 通过这种范型, 开发者可以快速构建更小粒度的应用, 即函数级别的应用. 随着服务器无感知计算的日益流行, 各大云计算厂商相继推出各自的商业服务器无感知平台. 然而, 这些平台的特点尚未得到系统的研究和可靠的比较. 全面分析这些特点可以帮助开发者选择合适的服务器无感知平台, 并以正确的方式开发和执行基于服务器无感知计算的应用. 为此, 开展了面向主流的商业服务器无感知平台特征的实证研究. 涵盖的主流服务器无感知平台包括亚马逊Lambda、谷歌Cloud Functions、微软Azure Functions和阿里巴巴Function Compute. 研究内容主要分为两大类: 特征总结和运行时性能分析. 在特征总结中, 通过对这些服务器无感知平台的官方文档进行探究, 从开发、部署和运行时3个方面的关键特征进行总结和比较. 在运行时性能分析中, 使用代表性的基准测试程序, 从多个维度分析了这些服务器无感知平台提供的运行时性能. 具体而言, 首先分析了影响应用冷启动性能的关键因素, 如编程语言和内存大小. 其次, 探究了服务器无感知平台执行各类任务的执行性能. 基于特征总结和运行时性能分析的结果, 总结了一系列发现, 并为开发者、云计算厂商和研究者提供了具有现实指导意义的启示和潜在的研究机会.

摘要:针对安卓自动化测试工具生成的崩溃测试序列包含过多冗余事件, 造成测试回放、缺陷理解与修复困难的现状, 很多测试序列约减工作被提出. 但目前工作仅关注应用界面状态变化而忽略了程序执行过程中内部状态变化, 此外, 目前工作仅在单一抽象粒度上对应用状态进行建模, 例如控件粒度或活动粒度, 导致约减后测试序列过长或约减效率低下. 针对以上问题, 提出基于事件标记的多粒度结合的安卓测试序列约减方法, 结合安卓生命周期管理机制、程序静态数据流分析等对触发程序崩溃的关键事件进行标记, 缩小序列约减空间, 并设计了低粒度粗筛选、高粒度细约减的策略. 最后, 收集包含程序间交互、用户输入等复杂场景的崩溃测试序列集, 在此数据集上与其他测试序列约减工作的对比评估结果也验证了所提方法的有效性.

摘要:基于进化优化的消息传递接口(message-passing interface, MPI)程序路径覆盖测试中, 进化个体适应值的评价需要反复执行MPI程序, 而程序的重复执行往往需要高昂的计算成本. 鉴于此, 提出一种代理辅助多任务进化优化引导的MPI程序路径覆盖测试用例生成方法, 该方法能够显著约减MPI程序的实际执行次数, 进而提高测试效率. 首先, 面向MPI程序目标路径内每条目标子路径, 训练相应的代理模型; 然后, 基于对应每条目标子路径的代理模型, 估计相应测试用例生成优化任务中进化个体的适应值, 并形成候选测试用例集; 最后, 基于候选测试用例集及其面向每条目标子路径的真实适应值, 更新对应每条目标子路径的代理模型. 将所提方法应用于7个基准MPI程序的基本路径覆盖测试中, 并与其他若干先进方法比较. 实验结果表明, 所提方法能够在确保测试用例生成高有效性的前提下, 显著提高测试效率.

摘要:当下, 软件系统中元素间的交互错综复杂, 涵盖了包间、类间和函数间等多种关系. 准确理解这些关系对于优化系统结构以及提高软件质量至关重要. 分析包间关系有助于揭示模块间的依赖性, 有利于开发者更好地管理和组织软件架构; 而类间关系的明晰理解则有助于构建更具扩展性和可维护性的代码库; 清晰了解函数间关系则能够迅速定位和解决程序中的逻辑错误, 提升软件的鲁棒性和可靠性. 然而, 现有的软件系统交互关系预测存在着粒度差异、特征不足和版本变化等问题. 针对这一挑战, 从软件包、类和函数这3种粒度构建相应的软件网络模型, 并提出一种结合局部和全局特征的全新方法, 通过软件网络的特征提取和链路预测方式, 来增强对软件系统的分析和预测. 该方法基于软件网络的构建和处理, 具体步骤包括利用node2vec方法学习软件网络的局部特征, 并结合拉普拉斯特征向量编码以综合表征节点的全局位置信息. 随后, 利用Graph Transformer模型进一步优化节点属性的特征向量, 最终完成软件系统的交互关系预测任务. 在3个Java开源项目上进行广泛的实验验证, 包括版本内和跨版本的交互关系预测任务. 实验结果显示, 相较于基准方法, 所提方法在版本内的预测任务中, 平均AUC和AP值分别提升8.2%和8.5%; 在跨版本预测任务中, 平均AUC和AP值分别提升3.5%和2.4%.

摘要:社交网络情感数据最为显著的特征是其动态性. 针对群体文本情感漂移分析任务, 提出一种高斯混合多层自编码器(GHVAE)用于情感漂移检测. GHVAE将高斯混合分布作为潜在分布的假设先验, 对应潜在分布的多中心性质从而提高模型性能. 此外, 还对原始HVAE模型内建的漂移度量算法进行改进, 改善了高漂移值之间过于接近导致分类性能下降的问题. 采用多项对照实验和消融实验用于验证GHVAE的性能, 实验结果显示新模型的创新点为其漂移检测表现带来了提升.

摘要:强化学习在智能对话系统等决策任务中取得了令人瞩目的结果, 但其在复杂的、奖励稀疏的任务中学习效率较低. 研究人员在强化学习中引入技能发现框架, 以最大化不同技能间的差异为目标构建技能策略, 提升了智能体在上述任务中的学习效率. 然而, 受到采样轨迹数据多样性的限制, 现有的技能发现方法局限于在一个强化学习回合中学习一种技能, 导致其在一回合中具有序贯技能组合的复杂任务中表现欠佳. 针对该问题, 提出一种基于分组对比学习的序贯感知技能发现方法(group-wise contrastive learning based sequence-aware skill discovery, GCSSD), 该方法将对比学习融合到技能发现框架中. 首先, 为了提升轨迹数据的多样性, 将与环境交互的完整轨迹分段并进行分组, 利用分组轨迹构建对比损失学习技能嵌入表征; 其次, 结合技能嵌入表征与强化学习进行技能策略训练; 最后, 为了提升在具有不同序贯技能组合任务上的性能, 对采样轨迹进行分段技能表征并将其嵌入策略网络, 实现对已学技能策略的序贯组合. 实验结果表明, GCSSD方法在具有序贯技能组合的稀疏奖励任务中具有较好的训练效果, 并且在具有与训练任务不同的序贯技能组合任务中, 能够利用已学技能对该任务进行快速适应.

摘要:点云自监督表示学习以无标签预训练的方式, 探索三维拓扑几何空间结构关系并捕获特征表示, 可应用至点云分类、分割以及物体探测等下游任务. 为提升预训练模型的泛化性和鲁棒性, 提出基于双向拟合掩码重建的多模态自监督点云表示学习方法, 主要由3部分构成: (1) 逆密度尺度指导下的“坏教师”模型通过基于逆密度噪声表示和全局特征表示的双向拟合策略, 加速掩码区域逼近真值. (2) 基于StyleGAN的辅助点云生成模型以局部几何信息为基础, 生成风格化点云并与掩码重建结果在阈值约束下融合, 旨在抵抗重建过程噪声对表示学习的不良影响. (3) 多模态教师模型以增强三维特征空间多样性及防止模态信息崩溃为目标, 依靠三重特征对比损失函数, 充分汲取点云-图像-文本样本空间中所蕴含的潜层信息. 所提出的方法在ModelNet、ScanObjectNN和ShapeNet这3种点云数据集上进行微调任务测试. 实验结果表明, 预训练模型在点云分类、线性支持向量机分类、小样本分类、零样本分类以及部件分割等点云识别任务上的效果达到领先水平.

摘要:虽然卷积神经网络凭借优异的泛化性能被广泛应用在图像识别领域中, 但被噪声污染的对抗样本可以轻松欺骗训练完全的网络模型, 带来安全性的隐患. 现有的许多防御方法虽然提高了模型的健壮性, 但大多数不可避免地牺牲了模型的泛化性. 为了缓解这一问题, 提出了标签筛选权重参数正则化方法, 在模型训练过程中利用样本的标签信息权衡模型的泛化性和健壮性. 先前的许多健壮模型训练方法存在下面两个问题: 1)大多通过增加训练集样本的数量或复杂度来提高模型的健壮性, 这不仅弱化了干净样本在模型训练过程中的主导作用, 也使得训练任务的工作量大大提高; 2)样本的标签信息除了被用于与模型预测结果对比来控制模型参数的更新方向以外, 在模型训练中几乎不被另作使用, 这无疑忽视了隐藏于样本标签中的更多信息. 所提方法通过样本的正确标签和对抗样本的分类标签筛选出模型在分类该样本时起决定性作用的权重参数, 对这些参数进行正则优化, 达到模型泛化性和健壮性权衡的效果. 在MNIST、CIFAR-10和CIFAR-100数据集上的实验和分析表明, 提出的方法能够取得很好的训练效果.

摘要:社交媒体文本摘要旨在为面向特定话题的大规模社交媒体短文本(称为帖子)产生简明扼要的摘要描述. 考虑帖子表达内容短小、非正式等特点, 传统方法面临特征稀疏与信息不足的挑战. 近期研究利用帖子间的社交关系学习更好的帖子表示并去除冗余信息, 但其忽略了真实社交媒体情景中存在的不可靠噪声关系, 使得模型会误导帖子的重要性与多样性判断. 因此, 提出一种无监督模型DSNSum, 其通过去除社交网络中的噪声关系来改善摘要性能. 首先, 对真实社交关系网络中的噪声关系进行了统计验证; 其次, 根据社会学理论设计两个噪声函数, 并构建一种去噪图自编码器(denoising graph auto-encoder, DGAE), 以降低噪声关系的影响, 并学习融合可信社交关系的帖子表示; 最终, 通过稀疏重构框架选择保持覆盖性、重要性及多样性的帖子构成一定长度的摘要. 在两个真实社交媒体(Twitter与新浪微博)共计22个话题上的实验结果证明了所提模型的有效性, 也为后续相关领域的研究提供了新的思路.

摘要:针对基于图卷积神经网络(GCN)的人体姿态估计方法不能充分聚合关节点时空特征、限制判别性特征提取的问题, 构造基于平行多尺度时空图卷积的网络模型(PMST-GNet), 提高三维人体姿态估计的性能. 该模型首先设计对角占优的时空注意力图卷积(DDA-STGConv), 构建跨域时空邻接矩阵, 对骨架关节点信息进行基于自约束和注意力机制约束的建模, 增强节点间的信息交互; 然后, 通过设计图拓扑聚合函数构造不同的图拓扑结构, 以DDA-STGConv为基本单元构建平行多尺度子网络模块(PM-SubGNet); 最后, 为了更好地提取骨架关节的上下文信息, 设计多尺度特征交叉融合模块(MFEB), 实现平行子图网络之间多尺度信息的交互, 提高GCN的特征表示能力. 在主流3D姿态估计数据集Human3.6M和MPI-INF-3DHP数据集上的对比实验结果表明, 所提PMST-GNet模型在三维人体姿态估计中具有较好的效果, 优于Sem-GCN、GraphSH、UGCN等当前基于GCN网络的主流算法.

摘要:在文本和表格的数值问答任务中, 模型需要在给定的文本和表格下进行数值推理. 任务目标是生成一个包含多步数值计算的计算程序, 并将计算程序结果作为问题的答案. 为了建模文本和表格, 当前工作通过模板将表格线性化为一系列单元格句子, 再基于文本和单元格句子设计生成器以产生计算程序. 然而, 这种方法面临一个特定问题: 由模板生成的单元格句子间差异微小, 生成器难以区分回答问题所必需的单元格句子(支撑单元格句子)和回答问题无关的单元格句子(干扰单元格句子), 最终导致模型基于干扰单元格句子生成错误的计算程序. 为了解决这个问题, 在生成器上设计一个多粒度单元格语义对比方法, 其主要目的是增加支撑单元格句子和干扰单元格句子表示距离, 进而帮助生成器区分它们. 这个方法由粗粒度单元格语义对比和细粒度单元格语义构成元素对比(包括行名对比, 列名对比及单元格数值对比)共同构成. 实验结果验证所提出的多粒度单元格语义对比方法可以使生成器在FinQA和MultiHiertt数值推理数据集上取得优于基准模型的表现. 在FinQA数据集上, 多粒度单元格语义对比方法上最高可以提升答案正确率达到3.38%; 特别地, 在更为困难的层次化表格数据集MultiHiertt中, 该方法使生成器的正确率显著提高了7.8%. 同大语言模型GPT-3结合思维链相比, 基于多粒度单元格语义对比的生成器性能在FinQA和MultiHiertt上分别表现出 5.44%和1.69%的答案正确率提升. 后续分析实验进一步验证多粒度单元格语义对比方法有助于生成器区分支撑单元格句子和干扰单元格句子.

摘要:近年来, 已有多种SM2数字签名算法的两方门限计算方案被提出, 这些方案能够有效地增强SM2数字签名算法的私钥安全性. 根据不同的密钥拆分方法, 已有公开方案可以分为两类, 分别基于乘法和加法拆分, 再根据不同的签名随机数构造方法, 衍生出多种两方门限计算方案. 提出SM2数字签名算法的两方门限计算方案框架, 所提框架给出安全的两方门限计算基本过程, 又可以引入不同构造的签名随机数. 利用提出的框架, 结合随机数的不同构造, 完成所提框架的多种实例化, 即得到SM2数字签名算法多种不同的两方门限计算方案. 所提框架的实例化, 包括现有已知的23种两方门限计算方案, 也包括多种新的方案.

摘要:本地差分隐私被广泛地应用于保护用户隐私的同时收集和分析敏感数据, 但是也易于受到恶意用户的伪数据攻击. 子集选择机制和环机制是具有最优效用的频率估计本地差分隐私方案, 然而, 它们的抗伪数据攻击能力尚缺少深入地分析和评估. 因此, 针对子集选择机制和环机制, 设计伪数据攻击方法, 以评估其抗伪造攻击的能力. 首先讨论随机扰动攻击和随机项目攻击, 然后构建针对子集选择机制和环机制的攻击效用最大化伪数据攻击方法. 攻击者可以利用该攻击方法, 通过假用户向数据收集方发送精心制作的伪数据, 最大化地提高攻击者所选目标值的频率. 理论上严格分析和对比攻击效用, 并通过实验评估伪数据攻击效果, 展示伪数据攻击对子集选择机制和环机制的影响. 最后, 提出防御措施, 可缓解伪数据攻击的效果.

摘要:随着移动终端的普及和用户隐私数据保护需求的增强, 基于移动终端的身份认证研究引起了广泛关注. 近年来, 移动终端的音频传感器为设计性能优良的新颖身份认证方案提供了更大的灵活性和可拓展性. 在调研了大量相关科研文献的基础上, 首先按照依赖凭据和感知方法的不同将基于声感知的移动终端身份认证方案进行分类, 并描述相应的攻击模型; 然后梳理移动终端基于不同认证凭据和基于声感知的身份认证国内外研究进展, 并进行分析、总结和对比; 最后结合当前研究的困难和不足, 给出衡量身份认证系统性能的两大指标(安全性和实用性), 对未来的研究方向进行展望.

摘要:在联邦学习领域, 激励机制是吸引高质量数据持有者参与联邦学习并获得更优模型的重要工具. 然而, 现有的联邦学习研究鲜有考虑到参与者可能滥用激励机制的情况, 也就是他们可能会通过操纵上传的本地模型信息来获取更多的奖励. 针对这一问题进行了深入研究. 首先, 明确定义联邦学习中的参与者激励欺诈攻击问题, 并引入激励成本比来评估不同激励欺诈攻击方法的效果以及防御方法的有效性. 其次, 提出一种名为“梯度放大攻击(gradient scale-up attack)”的攻击方法, 专注于对模型梯度进行激励欺诈. 这种攻击方法计算出相应的放大因子, 并利用这些因子来提高本地模型梯度的贡献, 以获取更多奖励. 最后, 提出一种高效的防御方法, 通过检验模型梯度的二范数值来识别欺诈者, 从而有效地防止梯度放大攻击. 通过对MNIST等数据集进行详尽地分析和实验验证, 研究结果表明, 所提出的攻击方法能够显著提高奖励, 而相应的防御方法能够有效地抵制欺诈参与者的攻击行为.

摘要:DEFAULT是于2021年亚洲密码学年会中提出的一种新型轻量级密码算法, 适用于保护物联网中的微型芯片、微控制器和传感器等设备的信息安全. 基于唯密文的基本假设, 针对DEFAULT密码提出了一种基于代数关系的统计故障分析方法. 该方法使用随机半字节故障模型, 通过对代数关系的构造分析并结合故障注入前后中间状态的统计分布变化来破译密码. 此外, 采用AD检验-平方欧氏距离(AD-SEI)、AD检验-极大似然估计(AD-MLE)和AD检验-汉明重量(AD-HW)等新型区分器, 最少仅需1344个故障即可以99%及以上的成功率破解该算法的128比特原始密钥. 理论分析和实验结果表明, DEFAULT密码不能抵抗基于代数关系的统计故障分析的攻击. 该研究为其他轻量级分组密码算法的安全性分析提供了有价值的参考.

摘要:现实场景中, 电子商务、消费点评、社交网络等不同平台用户之间往往存在着丰富的交互关系, 将其构建成图结构, 并基于图神经网络GNN进行恶意用户检测已成为相关领域近几年的研究趋势. 然而, 由于恶意用户通常占比较小且存在伪装和标记成本高的情况, 导致了数据不平衡、数据不一致和标签稀缺等问题, 从而使传统GNN方法的效果受到了一定的限制. 提出基于半监督图表示学习的恶意节点检测方法, 该方法通过改进的GNN方法进行图节点表示学习并对图中节点分类. 具体地, 构造类别感知的恶意节点检测方法(class-aware malicious node detection, CAMD), 引入类别感知注意力系数、不一致图神经网络编码器、类别感知不平衡损失函数以解决数据不一致与不平衡问题. 接下来, 针对CAMD在标签稀缺情况下检测效果受限的问题, 提出基于图对比学习的方法CAMD⁺, 引入数据增强、自监督图对比学习及类别感知图对比学习, 使模型可以从未标记的数据中学习更多信息并充分利用稀缺的标签信息. 最后, 在真实数据集上的大量实验结果验证所提方法优于所有基线方法, 且在不同程度的标签稀缺情况下都表现出良好的检测效果.

摘要:随机块模型可以拟合各种网络的生成, 挖掘网络的隐含结构与潜在联系, 在社团检测中具有明显的优势. 广义随机块模型GSB是基于链接社团的思想发现广义社团的, 但其仅适用于有向无属性网络. 针对无向属性网络, 对网络拓扑信息建模的同时对节点属性进行建模, 提出一种度修正的属性网络广义随机块模型DCGSB (degree corrected general stochastic block model). 在该模型中, 假设网络拓扑信息和属性信息的生成过程都服从幂函数形式的分布, 并且引入节点的度来刻画网络的无标度特性, 可以更好地拟合真实网络的生成. 利用期望最大化算法对DCGSB模型的参数进行估计, 通过硬划分处理, 得到节点隶属度, 进而完成社团检测. 在3个含有不同结构的真实属性网络数据集上进行实验, 并与10种社团检测算法进行对比, 结果表明DCGSB模型不仅继承了GSB模型的优点, 能发现广义社团, 而且由于属性信息和节点度的引入, 使其社团检测能力优于其他10种比较算法.

摘要:持久化内存(persistent memory, PM)作为主存的补充和替代, 为数据存储提供了相对较低的价格成本, 并且保证了数据的持久化. 为PM设计的传统结构索引(如B+树等)未能充分利用数据分布特点来发挥索引在PM上的读写性能. 最近的研究尝试利用学习索引的数据分布感知能力提升索引在PM上的读写性能并实现持久化. 但在面对真实世界的数据时, 现有基于PM的持久化学习索引的数据结构设计会导致额外的内存访问, 从而影响读写性能. 针对PM学习索引在面对真实数据时读写性能下降的问题, 提出一种DRAM/PM混合架构的学习索引PLTree. 它通过以下方法提升在PM上的读写性能并减轻数据分布颠簸对性能的影响: (1)使用两阶段方法构建索引消除内部节点的局部搜索, 减少PM的访问. (2)利用模型搜索来优化PM上的查找性能并通过在DRAM存储元数据加速查找. (3)根据PM的特性设计了日志式分层溢出缓存结构, 优化写入性能. 实验结果表明, 在不同数据集上, 与现有的持久化内存索引(APEX, FPTree, uTree, NBTree和DPTree)相比, PLTree在索引构建性能上平均提升了约1.9–34倍; 单线程查询/插入性能平均提升了约1.26–4.45倍和2.63–6.83倍; 在多线程场景, 查询/插入性能最高提升了约10.2倍和23.7倍.

摘要:首次对时间有序事务数据中聚簇频繁模式的挖掘问题进行研究. 为了解决Naive算法处理该问题时存在冗余运算的问题, 提出一种改进的聚簇频繁模式挖掘算法ICFPM (improved cluster frequent pattern mining). 该算法使用2种优化策略, 一方面可以利用定义的参数minCF, 有效减少挖掘结果的搜索空间, 另一方面可以参考(n–1)项集的判别结果加速聚簇频繁n项集的判别过程, 算法还使用了ICFPM-list结构来减少候选n项集的构建开销. 基于两个真实世界数据集的仿真实验证明了ICFPM算法的有效性, 与Naive算法相比, ICFPM算法在时间和空间效率方面得到了大幅度的提高, 是解决聚簇频繁模式挖掘的有效方法.

摘要:微内核系统将系统服务迁移到用户态运行, 因其架构隔离性而具有高可靠性的优势, 这一优势与航天领域的需求相契合. SPARC架构的处理器被广泛应用于航天飞船、卫星载荷以及星球车的控制设备上, 而该架构的寄存器窗口机制会影响微内核进程间通信(inter-process communication, IPC)的性能, 其核间中断(inter-processor interrupt, IPI)也会严重影响跨核IPC的效率. IPC作为微内核系统的关键机制, 对微内核上应用程序的整体性能十分重要. 基于对SPARC寄存器窗口机制的观察, 重新设计实现寄存器组机制, 由系统内核对寄存器窗口进行分配和管理, 并藉此实现SPARC架构上的BankedIPC. 同时, 在多核场景下, 针对SPARC上IPI性能较差的问题, 设计实现FlexIPC以优化跨核IPC的性能. 使用这些方法对自研微内核ChCore上已经实现的通用的同步IPC进行优化. 测试表明, 优化后SPARC上微内核的IPC平均性能提升至原来的2倍, 应用性能提升最高可达15%.

摘要:近年来, 超导量子互连技术的研究取得了重要进展, 这为构建分布式超导量子计算架构提供了有效途径. 分布式超导架构在网络拓扑、量子比特连通性、以及量子态传输协议等方面对量子线路的执行施加了严格约束. 为在分布式架构上调度和执行量子线路, 需要通过专门的映射工序对量子线路进行适配底层架构的变换, 并将变换后的线路交由网络中多个QPU (quantum processing unit)协同运行. 分布式量子线路映射需向原始线路插入辅助的量子态移动操作, 这些操作(尤其是QPU间量子态移动操作)具有较高的错误率. 因此, 减少映射所需的量子态移动操作数对于保证分布式计算的成功率至关重要. 基于超导量子互连技术和超导QPU的技术特征构建一种抽象的分布式量子计算模型, 并基于该抽象模型提出一种分布式量子线路映射方法, 该方法由量子比特分布式映射和量子态路由两个核心模块组成, 前者以量子态路由开销为代价函数, 通过局部寻优和模拟退火相结合的策略生成近最优的初始映射; 后者根据量子门执行的不同情形构建多个启发式量子态路由策略, 并通过灵活应用这些策略最小化插入的量子态移动操作数. 所构建的分布式抽象模型屏蔽了底层架构中和量子线路映射无关的物理细节, 这使得基于该模型的映射方法可适用于一类分布式超导架构而非某个特定架构. 另外, 所提方法可作为辅助工具参与分布式网络拓扑结构的设计和评价. 实验结果表明, 所提算法可以有效降低映射所需的QPU内量子态移动操作(即SWAP门)数和QPU间量子态移动操作(即ST门)数. 相较已有算法, 在所有基准线路上平均减少69.69%的SWAP门和85.88%的ST门, 且时间开销和已有算法接近.