Wait-Free Multi-Word Compare-and-Swap Using Greedy Helping and Grabbing

We present a new algorithm for implementing a multi-word compare-and-swap functionality supporting the Read and CASN operations. The algorithm is wait-free under reasonable assumptions on execution history and benefits from new techniques to resolve conflicts between operations by using greedy helping and grabbing. Although the deterministic scheme for enabling grabbing somewhat sacrifices fairness, the effects are insignificant in practice. Moreover, unlike most of the previous results, the CASN operation does not require the list of addresses to be sorted before the operation is invoked, and the Read operation can read the current value without applying helping when the word to be read is within an ongoing transaction. Experiments using micro-benchmarks varying important parameters in three dimensions have been performed on two multiprocessor platforms. The results show similar performance as the lock-free algorithm by Harris et al. for most scenarios, and significantly better performance on scenarios with very high contention. This is altogether extraordinary good performance considering that the new algorithm is wait-free.     

A Wait-Free Sorting Algorithm

Sorting is one of a set of fundamental problems in computer science. In this paper we present the first wait-free algorithm for sorting an input array of size N using P ≤ N processors to achieve optimal running time. We show two variants of the algorithm, one deterministic and one randomized, and prove that, with high probability, the latter suffers no more than contention when run synchronously. Known sorting algorithms, when made wait-free through previously established transformation techniques, have complexity O(log ³ N) . The algorithm we present here, when run in the CRCW PRAM model, executes with high probability in O(log N) time when P=N , and O((Nlog N)/P) otherwise, which is optimal amongst comparison-based sorting algorithms. The wait-free property guarantees that the sort will complete despite any delays or failures incurred by the processors. This is a very desirable property from an operating systems point of view, since it allows oblivious thread scheduling as well as thread creation and deletion, without fear of losing the algorithm's correctness. Received May 15, 1998, and in revised form November 17, 1999. Online publication November 19, 2001.     

Highly-Efficient Wait-Free Synchronization

We study a simple technique, originally presented by Herlihy (ACM Trans. Program. Lang. Syst. 15(5):745–770, 1993), for executing concurrently, in a wait-free manner, blocks of code that have been programmed for sequential execution and require significant synchronization in order to be performed in parallel. We first present an implementation of this technique, called Sim, which employs a collect object. We describe a simple implementation of a collect object from a single shared object that supports atomic Add (or XOR) in addition to read; this implementation has step complexity O(1). By plugging in to Sim this implementation, Sim exhibits constant step complexity as well. This allows us to derive lower bounds on the step complexity of implementations of several shared objects, like Add, XOR, collect, and snapshot objects, from LL/SC objects. We then present a practical version of Sim, called PSim, which is implemented in a real shared-memory machine. From a theoretical perspective, PSim has worse step complexity than Sim, its theoretical analog; in practice though, we experimentally show that PSim is highly-efficient: it outperforms several state-of-the-art lock-based and lock-free synchronization techniques, and this given that it is wait-free, i.e. that it satisfies a stronger progress condition than all the algorithms that it outperforms. We have used PSim to get highly-efficient wait-free implementations of stacks and queues.     

Wait-Free Clock Synchronization

Multiprocessor computer systems are becoming increasingly important as vehicles for solving computationally expensive problems. Synchronization among the processors is achieved with a variety of clock configurations. A new notion of fault-tolerance for clock synchronization algorithms is defined, tailored to the requirements and failure patterns of shared memory multiprocessors. Algorithms in this class can tolerate any number of napping processors, where a napping processor can fail by repeatedly ceasing operation for an arbitrary time interval and then resume operation without necessarily recognizing that a fault has occurred. These algorithms guarantee that, for some fixed k, once a processor P has been working correctly for at least k time, then as long as P continues to work correctly, (1) P does not adjust its clock, and (2) P's clock agrees with the clock of every other processor that has also been working correctly for at least k time. Because a working processor must synchronize in a fixed amount of time regardless of the actions of the other processors, these algorithms are called wait-free. Another useful type of fault-tolerance is called self-stabilization: starting with an arbitrary state of the system, a self-stabilizing algorithm eventually reaches a point after which it correctly performs its task. Two wait-free clock synchronization algorithms are presented for a model with global clock pulses. The first one is self-stabilizing; the second one is not but it converges more quickly than the first one. The self-stabilizing algorithm requires each processor's communication register contents to be a part of the processor's state. This last requirement is proven necessary. A wait-free clock synchronization algorithm is also presented for a model with local clock pulses. This algorithm is not self-stabilizing. Received December 20, 1993; revised January 1995.     

基于关联度的汉藏多词单元等价对抽取方法

针对为汉藏辅助翻译系统建立汉藏多词单元翻译词典这一任务,该文提出了CMWEPM模型。该模型首先依据关联度和结合度来确定汉语语料中多词单元的边界,然后根据词对齐信息分别抽取严格和约束多词单元等价对,从而形成汉藏多词单元等价对。CMWEPM模型根据不同长度和频次对多词单元进行分类,并为不同类型设定不同阈值,最终提高了汉藏多词单元等价对的召回率,从而能够间接地提高汉藏辅助翻译系统的翻译质量。     

基于领域类别信息C-value的多词串自动抽取

该本的多词串抽取是自然语言处理领域一项重要的研究内容。该文提出了一种多类别C-value(Multi-Class C-value)方法,利用多词串在不同领域的分布信息改善领域相关的多词串抽取的性能。在汽车、科技和旅行三个领域的数据上进行实验,评价多词串的准确率,在top-100级别上,较传统的C-value方法在三个领域中分别提高了12、12和13个百分点。实验结果验证了方法的有效性。     

维吾尔语多词领域术语的自动抽取

多词领域术语抽取是自然语言处理技术中的一个重点和难点问题, 结合维吾尔语语言特征,该文提出了一种基于规则和统计相结合的维吾尔语多词领域术语的自动抽取方法。该方法分为四个阶段: ①语料预处理, 包括停用词过滤和词性标注; ② 对字串取N元子串, 利用改进的互信息算法和对数似然比率计算子串内部的联合强度, 结合词性构成规则, 构建候选维吾尔语多词领域术语集; ③ 利用相对词频差值, 得到尽可能多的维吾尔语多词领域术语; ④ 结合C_value值获取最终领域术语并作后处理。实验结果准确率为85.08%, 召回率为 73.19%, 验证了该文提出的方法在维吾尔语多词领域术语抽取上的有效性。     

基于多词块的框架元素语义核心词自动识别研究

抽取一个句子的核心依存图是对句子进行语义理解的有效途径。在CFN自动标注的基础上,只能得到框架依存图,为了把框架依存图转换成框架核心依存图需要提取每个框架元素的语义核心词。该文提出了基于多词块标注的框架元素语义核心词识别和提取方法,通过对比分析,给出了多词块和框架元素的融合策略,并建立了在多词块标注基础上提取框架元素语义核心词的规则集。在6 771个框架元素上的实验结果显示,采用该文的方法和规则集提取框架元素核心词的平均准确率和覆盖率分别为95.58%和82.91%。     

一种基于元数据的柔性操作模型研究

首先介绍了元数据及其发展历程．然后针对行政事务处理系统，提出了一种基于元数据的柔性操作模型（MBFOM）．最后，对微操作的功能、结构和实现进行了具体研究．实践表明，MBFOM具有较强的实用性和普遍性，对提高系统的柔性以及软件重用的程度具有很强的现实意义．     

A-SMGCS系统动态工作方法

为了解决A-SMGCS指令工作方法健壮性不足的问题,提出了一种新的基于动态调整时隙结构的A-SMGCS动态工作方法,通过采用将时隙划分为多种时隙块,并对各种时隙块进行动态调整,以及允许移动站自主工作的方法以提高系统的可扩展性和健壮性.对动态调整时隙结构进行了描述,设计了基于该时隙结构的A-SMGCS动态工作方法,对比研究了上述两种工作方法下A-SMGCS系统的监视容量、监视报文间隔,以及系统健壮性,并使用网络仿真工具OPNET进行了仿真验证.仿真结果表明,A-SMGCS动态工作方法在保留指令工作方法时隙利用率高、监视系统容量大、监视报文间隔稳定的优点的同时,极大的改善了系统健壮性.     

一种带融合操作的实数多种群遗传算法

提出了一种带融合操作的实数多种群遗传算法。该算法由多个种群组成,根据各个种群中最优个体的适应值及其成长性优化计算资源分配;引入融合操作,利用各种群中的最优个体产生新个体,取代各种群中的最差个体,改善种群的遗传进程。实例计算表明该算法是有效的。     

非法计算检测的通用模型

非法计算是导致系统崩溃的一个常见故障.文中总结了Java语言中可能产生非法计算的运算符和数学库函数;建立了一个通用模型,用以检测一般函数(包括系统函数和自定义函数)在使用时是否合法;基于该通用模型提出了非法计算检测算法,并在此算法中引入区间运算.实验结果表明,文中模型及算法可以在检测出更多的非法计算故障的同时降低误报率.     

模n的大整数幂乘的一种快速算法

在RSA公钥密码体制中，要提高模n的大整数幂乘的运算效率，主要是解决两个方面的问题：（1）大整数的算术运算，特别是大整数的乘除法；（2）降低幂模运算的实际次数。文章从这两个方面进行研究，实现了大整数幂乘的一种快速计算。并给出了关键部分的算法，分析了算法的效率。     

基于GIS的公交运营仿真系统的设计与实现

本文针对公交公司对公交车辆行车方案进行直观观测的实际需求,结合MapInfo和MapX-treme地图信息软件,从电子地图、数据库和仿真流程三个方面出发,设计并实现了一个基于GIS的公交运营仿真系统。最后,以武汉公交536线路为例,给出了系统对该线路上的车辆行车方案的仿真效果,并对仿真结果进行了简要分析。     

作战行动建模资源库系统研究

该文分析了作战行动建模资源库的特点,确定了基于WEB的分布式作战行动建模资源库系统的体系结构和功能,选取了XML描述资源元数据信息,并提出了基于本体的智能搜索引擎。     

作战文书关键信息抽取方法*

作战文书关键信息抽取是实现自动标图系统的关键。现有研究多以文书处理流程设计为主,未深入分析军标用法,信息抽取不完整。为完整提取信息,提出了基于分词处理与语义角色标注（SRL）相结合的文书关键信息抽取方法,实验证明方法有效、可行。基于文中方法所设计的信息抽取系统,已在某集团军内推广、应用。     

模n的大整数幂乘的一种快速算法

在RSA公钥密码体制中,要提高模n的大整数幂乘的运算效率,主要是解决两个方面的问题:⑴大整数的算术运算,特别是大整数的乘除法;⑵降低幂模运算的实际次数。文章从这两个方面进行研究,实现了大整数幂乘的一种快速计算,并给出了关键部分的算法,分析了算法的效率。     

基于饱和度运算的快速图像去雾算法

在雾、霾等恶劣天气条件下,大气介质中悬浮粒子的散射和吸收作用会严重退化户外拍摄的图像,造成图像识别率降低.从单色大气散射模型出发,提出面向视觉感知的HSV颜色模型定义饱和度的新算法,估计大气光亮度A;利用饱和度运算估计透射率函数进而恢复场景反照率;最后经直方图拉伸得到最终的复原图像.实验结果表明,改进算法能有效地复原场景的对比度和颜色,提高图像的视觉度和计算效率.