计算机学报杂志社
分享到:
《计算机学报》杂志在全国影响力巨大,创刊于1978年,公开发行的月刊杂志。创刊以来,办刊质量和水平不断提高,主要栏目设置有:研究论文与技术报告、短文、学术通信、学术活动、中国计算机学会学术动态等。
  • 主管单位:中国科学院
  • 主办单位:中国计算机学会;中国科学院计算技术研究所
  • 国际刊号:0254-4164
  • 国内刊号:11-1826/TP
  • 出版地方:北京
  • 邮发代号:2-833
  • 创刊时间:1978
  • 发行周期:月刊
  • 期刊开本:A4
  • 复合影响因子:3.18
  • 综合影响因子:2.580
相关期刊
服务介绍

计算机学报 2013年第04期杂志 文档列表

计算机学报杂志车联网

车载自组网移动模型综述

摘要:车载自组网已经在学术界和工业界受到广泛重视,新型应用和协议在实际工况条件下的测试需要很多人力和物力,并且不易控制,因此通常采用软件模拟方式进行实验验证.准确的移动模型是提高车载自组网模拟结果置信度的关键技术之一.文中从对交通特征的刻画粒度、移动模型的依赖与限制条件和移动模型的建立方法3个方面对已有的移动模型进行综合分析,提出若干面向宏观行为的统计特征量,并选取典型移动模型对其设计原理、微观特征和宏观特征等进行详细对比分析.微观方面,分析了各移动模型车辆的单次移动时间、单次移动距离、单次暂停时间和单次连接时间等特征量,结果发现不同模型在上述特征量的补累积分布下具有相似特征,而对应特征量的概率分布则具有一定差别.宏观方面,分析了各移动模型单个车辆的平均速度、总移动距离、总移动时间、平均邻居数量和平均加速度等特征量,结果表明不同模型在上述特征量的补累积分布下也体现出近似的相变行为,但各自的相变点不同,各模型对应特征量的概率分布具有明显的泊松分布特征,但均值差异较大.另外,也分析了各移动模型所有车辆的瞬时平均速度、瞬时移动距离、瞬时移动车辆数目、瞬时平均邻居节点数和瞬时平均加速度等特征量,结果表明各移动模型瞬时特性曲线的抖动强度和抖动趋势均不同,各模型特征量的平均值对车辆数量变化的敏感度也不尽相同.
677-700

车载自组织网络中一种连通度感知的可靠数据分发机制

摘要:车载自组织网络可以通过多跳无线广播实现远距离的数据传输,但网络拓扑的快速变化和无线通信质量的不稳定会导致数据传输性能的不稳定.为了应对这些挑战,文中提出了一种适用于城市场景的可靠的、连通度感知的数据分发机制.该机制利用实时收集的交通流量数据,建立路口车辆排队长度变化的马尔可夫模型,并基于此模型估算路段间无线网络连通度的实时变化,以便数据沿最小延迟路径进行转发.该机制还考虑到城市环境对无线信号的干扰,用覆盖消除规则改进了贪心广播算法,通过多候选转发策略增强了路段间数据传输的可靠性.模拟实验结果表明,与基于传染病的数据分发协议、基于静态节点的自适应数据分发协议相比,文中提出的机制能实现高可靠、低延迟的数据分发.
701-715
计算机学报杂志社会计算

PrivateCheckIn:一种移动社交网络中的轨迹隐私保护方法

摘要:移动设备的发展及无线网络的普及促使移动社交网络的出现及发展.签到服务作为移动社交网络中的主流应用,存在着严重的轨迹隐私泄露风险.文中针对签到服务中假名用户的轨迹隐私泄露问题,提出了一种轨迹隐私保护方法PrivateCheckIn.该方法设计了一种签到序列缓存机制,通过为缓存的签到序列建立前缀树、对前缀树进行剪枝及重构形成k-匿名前缀树,遍历k-匿名前缀树得到k-匿名签到序列,达到了轨迹k-匿名的隐私保护效果.文中证明了PrivateCheckIn方法既能保护假名用户的轨迹隐私,又确保损失签到位置最少,有效地保证了用户体验.通过构建前缀树的方式获取轨迹k-匿名集降低了计算代价.最后,文中在真实数据集上与(k,δ)-anonymity方法进行了充分的对比实验,验证了PrivateCheckIn方法的准确性与有效性.
716-726

移动社交网的生命周期评估模型研究

摘要:类似于自然界中的其它系统,移动社交网(MSN)也会存在一个从生到死的"生命周期".文中着重研究MSN的生命周期及其评估模型,并探究处于不同生命周期阶段的MSN用户行为特征.提出了一个基于波士顿矩阵的移动社交网生命周期模型.该模型通过分析用户点击流数据,判断某个移动社交网站所处的生命周期阶段:幼年期、成长期、成熟期或衰老期.模型从移动互联网的用户访问行为中提取出两个参数指标,分别表征竞争地位与竞争实力,避免了以往需要通过长期市场调研的方法来判断分析对象所处生命周期阶段的困难,可以快速有效地判断一个移动社交网所处的生命周期阶段.根据实地采集的某移动互联网运营商的数据集,分析和验证了文中模型的有效性.此外,从6个方面分析了移动社交网用户在不同生命周期阶段的行为特征.
727-737
计算机学报杂志计算机体系结构

SimHPC:一种基于执行驱动的大规模并行系统模拟器

摘要:模拟实验方法对高性能计算机系统的性能评价和优化设计有着重要的意义,然而由于目标系统规模庞大,传统的体系结构模拟器难以满足模拟性能方面的要求.文中提出了一种专门用于高性能计算系统的模拟器——SimHPC,该模拟器采用执行驱动的全系统模拟方法,支持操作系统和应用程序的模拟运行.通过采用与目标系统同构的节点作为宿主节点以及并行模拟的方法,使得模拟性能相比传统的体系结构模拟器大幅提高,与现有的几种大规模并行系统模拟器相比,SimHPC在通用性和模拟性能方面也具有一定的优势.
738-746

考虑电压/温度变化的电热综合分析及其并行加速技术

摘要:受限于计算能力,在现有的电热分析研究中,无法考虑电压变化对电热分析的影响,从而降低了分析的精度.基于已有的研究成果,文中分析了芯片的功耗/电压/温度分布向量之间的相互关系,指出了在电热综合分析中考虑电压/温度变化的必要性,进而提出了一种迭代式的并行电热综合分析方法ETA_VT,该方法基于功耗与电压/温度之间的递归关系,进行迭代计算,最后将收敛后的功耗/电压/温度分布向量作为求解结果同时输出.基于多核CPU+众核GPU异构计算机系统所提供的并行计算资源,为了提高电热综合分析的运行效率,文中不仅设计了一个具有主辅双进程的ETA_VT算法流程,而且还分别采用CPU多线程并行计算、GPU并行计算、CPU+GPU协同并行计算技术对ETA_VT算法进行加速研究.实验数据表明:(1)考虑电压/温度变化的电热综合分析不仅可以获得较为精确的分析结果,而且可以同时计算出芯片的功耗/电压/温度分布;(2)采用并行计算技术、并合理分配计算资源,不仅可以解决电热综合分析中存在的功耗/电压/温度多参量相互影响的问题,而且还可以有效地提高电热综合分析的速度,获得多达44倍的加速效果.文中工作是将高性能计算引入电子设计自动化(EDA)算法研究的一次有益尝试,表明高性能计算技术不仅可以提高EDA算法的执行效率,而且可以促进芯片设计中存在的多参量相互影响综合分析问题的研究和解决.
747-756

图形处理器通用计算关键技术研究综述

摘要:当前图形处理器的通用计算取得长足发展,为适应通用计算图形处理器在硬件体系结构和软件支持方面完成相应调整和改变,面对各种应用领域中数据规模增大的趋势,多GPU系统和GPU集群的研究应用日趋增多.以流处理器及图形处理器硬件体系为依据,介绍学术和工业领域中流处理器及图形处理器体系变化趋势.从软件编程环境、硬件计算与通信等方面展开讨论,阐述通用计算中图形处理器的关键问题,包括编程模型及语言的发展和方向,存储模型的量化研究、访存模式和行为的优化以及分布式存储管理的热点问题,典型通信原型系统的对比及通信难点的分析,GPU片内和片间的负载均衡,可靠性和容错计算,GPU功耗评测及低功耗优化的研究进展.综述在海量数据处理、智能计算、复杂网络、集群应用领域中图形处理器的研究进展及成果.总结在通用计算发展中存在的技术问题和未来挑战.
757-772

性能非对称多核处理器上的自适应调度

摘要:现有的性能非对称多核调度算法要么不能充分利用其体系结构而吞吐量低,要么能充分利用其体系结构但扩展性差.有些算法即使考虑了扩展性,但也局限于CPU核数目,没有考虑到任务数方面的扩展性.为了解决这些问题,作者提出了一个自适应调度算法(称为AS4AMS).在任务的每一次调度中,AS4AMS首先通过分析任务运行时的平均停驻时间得出任务的计算需求,然后根据这些需求以及各CPU核的负载情况将任务分配到合适的CPU核上运行.另外,该算法任务结束前,会不断重复上述过程以适应任务需求的不断变化.实验结果表明:与现有方法相比,所提出的方法扩展性更好并且吞吐量也更大.
773-781

迭代方法中基于渐近规模的通信与计算比分析

摘要:迭代方法是科学计算中求解大规模稀疏线性代数方程组最常用的方法.大量实际应用表明,迭代方法通常具有较高的通信与计算比,只有在粗粒度并行下才能取得较好的并行可扩展性能.而实际应用大规模计算的需求和当前多核/众核体系结构的发展趋势要求迭代方法具备细粒度并行可扩展能力.文中引入渐近规模,即满足加速条件的计算规模下界,来反映并行迭代方法适应细粒度并行的能力,并由此刻画通信与计算比.基于矩阵的稀疏模式及其通信模式、机器的通信参数和迭代方法的基本运算,给出了渐近规模的理论预测公式.在一台包含128个双路4核计算节点的并行机上,分别基于纯进程并行(MPI)和进程/线程混合并行(MPI/OpenMP),以实际应用中3种常用迭代方法Jacobi、CG、BiCGSTAB为例,分析其渐近规模.并行可扩展性测试表明了渐近规模用于刻画迭代方法通信与计算比的准确性.对于纯进程情形,给出了渐近规模的理论预测与实际测试的对比,表明了理论预测结果的正确性.最后,基于这些结果,从迭代方法的算法设计和并行实现等方面讨论了面向未来更大规模的计算系统,降低通信与计算比的途径.
782-789

面向通用HPC的高性能DSP设计权衡

摘要:GPU由于其计算能力高达数TFLOPS,被高性能计算领域用于加速并行运算.但GPU较低的峰值性能利用率和功耗效率,已经成为了系统性能进一步提升的瓶颈.为了解决这个问题,作者开始研究将高性能DSP用于通用高性能计算领域.为了高效支撑通用高性能计算,文中提出了高性能DSP的结构框架,并通过映射GotoBLAS库到该结构上,建立了GEMM在该结构上的性能模型.作者研究了影响GEMM效率的主要因素,包括性能、存储层次、核的大小以及核的数量.文中总结了一些有指导意义的结论用于构建面向通用高性能计算的高效DSP.实验结果表明,通过尽可能少的硬件代价,可以在TFLOPS DSP上获得接近峰值的性能.
790-798

针对组相联缓存的无效缓存路访问混合过滤机制研究

摘要:近年来,功耗成为处理器设计领域的关键问题之一.传统应对功耗的方法如DVFS(Dynamic VoltageFrequency Scaling)目前遭遇了收益递减律.随着多核/众核处理器的普及化,片上缓存占有了越来越多的CPU芯片面积和功耗.针对降低功耗的问题,文中提出了通过过滤不必要的缓存路访问来降低缓存动态功耗的方法.该方法包括采用无效访问过滤器(Invalid Filter)来消除对含无效数据块的缓存路的访问;采用指令数据访问过滤器(I/D Filter)来消除对与访问类型(指令或数据)不匹配的数据块所在的缓存路的访问;以及采用tag低位过滤器(Tag-2Filter)来消除对tag低位不匹配的数据块所在的缓存路的访问.文中提出将以上3种方法合并,称为Invalid+I/D+Tag-2Filter,以期取得更好的效果.通过分析和实验验证了3种方法的有效性和互补性.同时,实验也表明,与Invalid+I/D Filter相比,Invalid+I/D+Tag-2Filter在64KB 4路组相联缓存上可以取得19.6%~47.8%(平均34.3%)的效果提升,在128KB 8路组相联缓存上可以取得19.6%~55.2%(平均39.2%)的效果提升;与Invalid+Tag-2Filter相比,Invalid+I/D+Tag-2Filter在64KB 4路组相联缓存上可以取得16.1%~27.7%(平均16.6%)的效果提升,在128KB 8路组相联缓存上可以取得6.9%~44.4%(平均25.0%)的效果提升.
799-808
计算机学报杂志计算机理论

Quine空间与二相不确定度量

摘要:Pearl指出:不确定是智能系统所面临的核心问题.存在形式是不确定的基本问题,而至今未见不确定的存在形式的报道.文中试图建立一种有关不确定的一般理论框架和度量方法.在区分不确定和不确定性之后,采用向量描述不确定的独立属性,构造不确定的存在形式——Quine空间;在建立属性标准度后,提出单相不确定和二相不确定的度量模型.作为度量模型应用的示例,以中介真值程度讨论模糊性度量,以现代概率理论讨论随机性度量,以模糊随机性讨论二相不确定度量.结果表明:文中所提出的方法具有自然、普适的特征,且具有计算机可以处理的定量形式.文中试图使各种不确定性的度量值归一化,使得它们在程度方面具有可比性.
809-817

基于信号驱动的多批处理综合调度算法

摘要:针对以往综合调度中批处理调度算法只能处理2个工序的批量调度,进行批量调度的工序不能具有2个以上的紧前工序,使综合调度具有局限性问题,提出基于信号驱动的多批处理综合调度算法.该算法先建立设备和调度2个子系统,并通过相互间传递的信号驱动;为了预判断可批处理工序,将工序分为可调度工序和准可调度工序,采用组合策略将可批量处理的工序形成组合工序一同加工;当可调度工序超过设备批处理量时,按最大并行性选择策略选择调度;当准可调度工序成为批处理工序时,无需考虑前续工序对工序批处理的影响,即对批处理工序的紧前工序数无限制;循环以上可批处理工序判断,实现多批量处理.
818-828

可满足性问题的巨磁电阻型DNA计算模型

摘要:DNA计算是一种新的计算模式,因其海量的信息存储能力、高度的并行性及低能耗等优点而被广泛地应用于求解各类NP完全问题.文中利用免疫磁标记和巨磁电阻(GMR)效应,对生物特异性反应进行检测,构建了可满足性问题的巨磁电阻型DNA计算模型,并用实例说明了模型的有效性和可行性.与传统的荧光标记法DNA计算模型相比,巨磁电阻型DNA计算模型的输出结果是电信号形式,因而具有检测信号易处理、检测时间短、解可靠性高、无需标记和读解简单等优点.
829-835

考虑边位置信息的求解ETSP问题改进贪婪算法

摘要:分析了贪婪算法(Greedy algorithm,GRA)求解欧几里德旅行商问题(Euclidean Traveling SalesmanProblem,ETSP)的求解质量和求解耗时的特点,发现边位置信息是影响GRA的求解质量和求解耗时的主要因素,在Michael模型基础上提出了一种考虑添加边所在位置信息的改进贪婪算法(Improved Greedy algorithm,IMGRA),并阐述了IMGRA的设计思想和相应的构造方法.分别采用IMGRA和GRA求解了90个算例,结果表明:固定参数下的IMGRA平均求解质量较GRA提高55%,求解耗时降低20%.为此,对IMGRA比GRA求解质量更高和求解耗时更短的原因进行了分析.
836-850

L3^*中逻辑公式的范式表示及对称逻辑公式的构造方法

摘要:将符号化计算树逻辑中Boole函数的Shannon展开式做了推广,研究了三值逻辑系统L3*中由公式导出的三值R0函数的展开式,给出了L3*中逻辑公式的准析取范式和准合取范式表示.研究了n元三值R0函数以及n元逻辑公式逻辑等价类的计数问题.在此基础上,给出了L3*中对称逻辑公式的构造方法.
851-861

命令式模糊程序语言的语义

摘要:文中关注计算机语言的形式语义学,旨在建立一种命令式模糊程序语言的指称语义与最弱(线性)前置条件语义.首先,借助模糊逻辑中的三角模、三角余模、非、蕴含以及模糊关系的合成等成功地完成了这两种语义的建模.这种方法为形式语义学的研究提供了一个新的视角.其次,证明了该语言的一些重要性质并讨论了最弱前置条件语义与最弱线性前置条件语义之间的关系.最后,证明了指称语义与最弱(线性)前置条件语义之间的对偶,该对偶表明了这两种语义可以相互诱导.
862-869
计算机学报杂志信息安全

ARJ:一种可变干扰半径的IEEE802.11g全频道干扰机

摘要:针对传统全频道干扰需利用单一频道干扰机进行相对费时的频道跳转,提出了一种全频道IEEE 802.11g干扰机(ARJ),ARJ利用临频干扰,尤其是非交叠信道临频干扰实现对全频道的覆盖.与单一频道干扰机相比,ARJ在一个固定频道上便可实现全频道干扰,可调节干扰信号发射功率实现可变的干扰半径,通过设置干扰频度达到能量有效.引入信道比特错误率的DCF马尔可夫链模型的理论分析和模拟场景的仿真实验表明:ARJ可以实现对IEEE 802.11g全频道的干扰,其在真实实验中得到实现和验证.
870-881