计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2008年第05期杂志 文档列表

计算机学报杂志研究论文与技术报告

MINI——一种可减小变更影响范围的本体演化算法711-720

摘要：本体演化会影响依赖本体的服务，使其重新修订和重新部署．面对同一变更需求，不同演化实现方法造成的影响范围差别很大．当前的本体演化研究主要集中在如何实现变更需求以及维护变更前后本体的一致性，对于如何降低演化影响范围关注甚少．文中提出了一种可以有效减小变更影响范围的本体演化算法MINI．该算法首先分析了本体实体和服务之间的依赖关系并提出了量化变更影响范围的数学公式．根据这一公式，MINI算法将本体演化过程转变为图的启发式搜索过程，通过搜索一条影响值最小的变更路径来减小本体演化的影响范围．实验结果表明，MINI算法导致的平均变更影响范围大大小于现有的本体演化算法．该算法已在某实际项目中得以应用和验证．

集成对象数据库的科学工作流服务框架中的数据跟踪721-732

摘要：文中提出了一个集成数据库的科学工作流服务框架，它采用对象模型描述一系列科学任务的执行过程，使得工作流管理操作以类似于传统数据库管理操作的方式来完成．同时，基于对象数据库中的双向指针机制，文中提出了一种新的数据跟踪方法，该方法能提供比注释或反向方法更高的性能，不仅节省了大量的存储空间，而且减少了额外的计算代价，为了进一步提高数据跟踪的高效性，文中也提出了一种部分物化中间数据模式，实验显示它具有较好的系统性能．

基于任务复制的分簇与调度算法733-740

摘要：针对并行与分布式系统中相关任务的静态调度问题，以最小化调度长度为主要目标，以减少资源数为次要目标，对待复制的重要祖先集定义了新的选择策略，提出了基于任务复制的动态关键前驱调度算法．改进了粒度的定义，证明了对任意DAG，算法有优于前人的性能下界．实验结果优于典型任务复制算法，特别是对经典EZ算例的解（调度长度为8）好于前人认为的理论最优解（调度长度为8．5），并证明了新的解为最优解．定义了DAG的补图，讨论了不允许任务复制时树型DAG的2-优度算法．

一种基于数据相关性的优化数据一致性维护方法741-754

摘要：针对数据一致性中的数据相关性问题，提出一种优化的数据一致性维护方法．在该方法中，数据对象按固定大小分块，并以数据块作为数据管理的基本单位；数据更新利用Bloomfilter技术压缩表示，并进行双路径传播；发起方和协商方在一致性维护过程中，分别调用各自的协商算法检测和解决更新冲突；动态数据管理算法调节数据更新过程中的动态数据块变化，对数据块进行合并或分解．模拟测试结果表明，在选取适当范围内的分块大小时，该方法在一致性维护开销、动态性和鲁棒性方面均具有较好的性能．文中给出了选定适当分块大小的指导性方法．

大规模流媒体应用中关键技术的研究755-774

摘要：支持大规模用户在线使用的流媒体应用是Internet中极富潜力的一项“重磅级应用”，但由于Internet缺乏服务质量（QoS）与相应的安全保障，并且网络和终端系统又存在着较大的异构性，这使得在Internet上构建支持大规模用户的在线流媒体应用面临很多的挑战．该文从支持该应用的流媒体编码技术和网络技术两个角度出发，针对其面临的挑战，深入、全面地综述了编码技术与网络技术的发展与现状．提出了一个新的流媒体应用体系结构，以同时解决大规模流媒体应用中的性能瓶颈、异构性、安全传输以及服务质量等问题，并指出了大规模流媒体应用中关键技术的研究方向．

PFWRR：能实现比例公平的增强型WRR775-782

摘要：为了实现比例公平原则，在加权轮循调度（WRR）算法的基础上提出了比例公平WRR调度算法——PFWRR．PFWRR依据各队列的平均分组到达率，调整各队列的调度权值，从而在当队列长度小于等于缓冲长度时，保证各队列的平均分组排队时延符合给定比例；当队列长度大于缓冲时，保证各队列的平均分组丢失率符合给定比例．PFWRR的计算负荷是合理的，因为它仅当系统超载且平均分组到达率发生变化时，才调整各队列的服务率．实测性能显示：当系统超载且不出现分组丢失时，PFWRR实现了比例平均分组排队时延保证，当系统出现分组丢失时，PFWRR实现了比例平均分组丢失率保证．

不同置换矩阵对基于分块H矩阵的LDPC码性能的影响783-792

摘要：研究了三种结构的循环移位置换矩阵，分别称为定义在GF（2）有限域上的J矩阵、D矩阵和Q矩阵，讨论了这些置换矩阵的结构特征和性质，主要研究了D和Q矩阵对基于单位矩阵J的规则QC-LDPC码和IEEE802．16e标准草案中推荐的不规则QC-LDPC码性能的改进．该文的另一个贡献是以Q矩阵为分块矩阵，构造了S-LDPC码新码族．S-LDPC码在性能和编码计算复杂度方面都略优于IEEE标准中的不规则QC—LDPC码．

基于延迟部分推理的快速前向规划系统793-802

摘要：根据动作组件诱发关系的存在和抵制计算的必要性，提出一个计算松弛规划解的新方法——延迟部分推理．该方法在考虑动作删除效果的假定下，构造不包含任何互斥关系的组件规划图，通过定义“松弛诱发”关系预测后续规划过程中可能出现的组件诱发现象，在松弛规划解提取阶段判断动作组件间的“松弛诱发”关系并选择抵制动作避免可能发生的消极作用．基于延迟部分推理方法定义了新的启发式函数和剪枝策略，设计了规划系统FFc并在多个国际通用的测试域上进行实验．结果表明，FFc较之Fast-Forward在求解效率和求解质量方面都有显著的提高．

基于特征可分性的核函数自适应构造803-809

摘要：核函数的选择与构造是支撑向量机研究中的关键问题和难点．该文针对该问题，首先讨论了特征空间的线性可分性，推导了其判别条件．然后，根据特征完全可分条件，基于函数逼近论和核函数的基本性质，提出了自适应多项式核函数和B-样条核函数模型，给出了模型参数的估计算法．实测数据仿真实验结果表明，与经典的核函数相比，该文提出的算法在分类性能上取得了明显改善．

多维背包问题的一个蚁群优化算法810-819

摘要：蚁群优化（ACO）是一种通用的启发式方法，已被用来求解很多离散优化问题．近年来，已提出几个ACO算法求解多维背包问题（MKP）．这些算法虽然能获得较好的解但也耗用太多的CPU时间．为了降低用ACO求解MKP的复杂性，文章基于一种已提出但未实现过的MKP的信息素表示定义了新的选择概率的规则和相应的基于背包项的一种序的启发式信息，从而提出了一种计算复杂性较低、求解性能较好的改进型蚁群算法．实验结果表明，无论串行执行还是虚拟并行执行，在计算。相同任务时，新算法耗用时间少且解的价值更高．不仅如此，在实验中，文中的新算法获得了ORLIB中测试算例5．250—22的两个“新”解．

一种基于内容相关性的跨媒体检索方法820-826

摘要：针对传统基于内容的多媒体检索对单一模态的限制，提出一种新的跨媒体检索方法．分析了不同模态的内容特征之间在统计意义上的典型相关性，并通过子空间映射解决了特征向量的异构性问题，同时结合相关反馈中的先验知识，修正不同模态多媒体数据集在子空间中的拓扑结构，实现跨媒体相关性的准确度量．实验以图像和音频数据为例验证了基于相关性学习的跨媒体检索方法的有效性．

基于WDDL和行波流水技术的抗功耗攻击高性能分组密码协处理器设计与实现827-834

摘要：该文结合WDDL逻辑和行波流水技术，给出了分组密码协处理器的设计方法和设计流程．该设计流程实现简单，最大限度地利用了现有的成熟EDA工具．这种协处理器不仅能有效抗功耗攻击，而且具有运算性能高和功耗低的优势．文中以DES算法为例，给出了基于WDDL和行波流水技术的协处理器．实验结果表明，文中给出的分组密码协处理器设计方法以一定的芯片面积为代价获得了抗功耗攻击的能力，具有高运算性能和低功耗的优势．

基于正反控制模型的可逆逻辑综合835-844

摘要：对一般Toffoli门进行了衍变和推广，给出了一个正反控制可逆级联模型（PNCRC），该模型拥有五种基本线型，并能正反控制目标位的输出．基于该模型给出了相应的可逆综合算法．对输入数不大于16的NCMC Benchmark函数进行测试并与已有的可逆综合方法比较，结果表明，利用该模型进行的可逆综合，垃圾信息数和可逆门数的优化效果都具有一定程度的改善．

基于线程感知寄存器重命名的SMT处理器资源分配845-857

摘要：SMT处理器的资源分配一般是通过调控各线程的取指过程间接实现的，这种间接调控有时会导致资源滥用和饥饿，从而严重浪费资源并降低整体性能．以往的改进措施往往实现代价较大，且不能消除资源分配的“不均衡性”，因此效果不太理想．文中提出一种新的SMT处理器资源调控机制——线程感知寄存器重命名TSRR（Thread-Sensmve Register Renaming），消除了资源分配的“不均衡性”，其优点如下：（1）资源分配自动适应线程运行状态的变化，实现“按需分配”；（2）通过调控重命名寄存器文件（RRF）的分配来间接控制其它资源分配，实现代价较低；（3）兼顾资源分配的效率和公平，既防止了资源滥用和饥饿，又充分发掘各线程的性能潜力．此外，TSRR还可以间接降低RRF的尺寸要求和取指逻辑的复杂度．

一种智能网络磁盘（IND）存储系统结构858-867

摘要：针对当前计算机存储系统结构中存在的若干问题，文中提出了一种新型的智能网络磁盘（Intelligent Network Disk，IND）存储系统结构．分别给出了IND内部数据的读／写控制、容错处理、负载平衡等智能控制算法，已经构建了一个IND结构的模拟原型IND存储系统．IND存储系统中各个IND都是直接与网络连接，若干个IND组成一个集群存储系统，给用户提供了一个虚拟化的海量存储系统．另外，由于各IND都具有一定的智能度，所以它是一种灵活可变的智能型网络存储器系统．

基于元胞自动机算法的三维玻璃微流控芯片湿法刻蚀模拟研究868-874

摘要：以二维动态元胞自动机理论为基础，提出一种针对玻璃各向同性刻蚀特性的三维动态元胞自动机（Cellular automata）算法．利用创建刻蚀链表的方式代替传统的元胞搜索，提高了算法效率，并通过改进元胞信息的存储方式，使得三维元胞阵列得以存储于二维矩阵中．最后利用Open GL技术对刻蚀结果进行三维成像．该算法在个人计算机上实现了较高分辨率（4000×4000像素）的三维刻蚀模拟与显示．通过对比玻璃刻蚀的实验结果和前人的研究评估模型，模拟结果完全能够实现对刻蚀结果的预测．文中的研究表明：建立的三维元胞自动机算法可以有效地应用于玻璃刻蚀过程的模拟．

基于局部对比度的自适应PCNN图像融合875-880

摘要：提出了一种结合人眼视觉特性的自适应PCNN图像融合新方法，使用图像逐像素的局部对比度做为PC-NN对应神经元的链接强度，经过PCNN点火获得参与融合图像的点火映射图，再通过判决选择算子，选择各参与融合图像中的明显特征部分生成融合图像．该方法除几个主要参数外，其它参数如阈值调整常量等对于融合结果影响很小，解决了PCNN用于图像处理时参数多且调整困难的问题．实验结果表明，融合效果优于经典的小波变换方法和Laplacian塔型方法．

《计算机学报》编辑委员会F0004-F0004