DKNNS:面向延迟敏感型应用的可扩展精确分布式K近邻搜索算法研究

为了降低用户访问延迟,延迟敏感型网络应用需要选择合适的邻近服务节点响应用户访问请求.分布式K近邻搜索通过可扩展的选择距任意用户节点邻近的K个服务节点,可以有效满足网络应用延迟优化的目的.已有工作在精确度以及可扩展性等方面存在不足.针对可扩展精确的K近邻搜索问题,文中提出了分布式K近邻搜索方法DKNNS(distributed K nearest neighbor search).DKNNS将大量的服务节点组织为邻近性感知的多级环,通过最远节点搜索机制选择优化的K近邻搜索初始化节点,然后基于回退方式快速的在目标节点邻近区域发现K个近邻.基于理论分析,模拟测试以及真实环境下的部署实验发现,在不同规模的节点集合下,DKNNS算法能够确定近似最优的K个服务节点.且DKNNS的查询延迟,查询开销均显著低于Meridian算法.最后,DKNNS的返回结果相对于Meridian具有较高的稳定性.     

SCHEDULING PARALLEL PROGRAM TASKS WITH NON-NEGLIGIBLE INTERTASK COMMUNICATIONS ON TO NUMA MULTIPROCESSOR SYSTEMS

The purpose of this paper is to examine the impact of scheduling parallel tasks onto non-uniform memory access (NUMA) shared-memory multiprocessor systems by considering non-negligible intertask communications and communication contentions. Communication contentions arise from the communication medium having insufficient capacity to serve all transmissions, thereby causing significant contention delays. Therefore, a new scheduling algorithm, herein referred to as the Extended Critical Path (ECP) algorithm is proposed. The proposed algorithm schedules parallel tasks by considering non-negligible intertask communications and the contentions among shared communication resources. Moreover, it ensures performance within a factor of two of the optimum for general directed acyclic task graphs (DATGs). Experimental results demonstrate the superiority of the ECP algorithm over the scheduling algorithms presented in previous literature.     

PERFORMANCE ANALYSIS OF TASK CLUSTERING HEURISTICS FOR SCHEDULING STATIC DAGS ON MULTIPROCESSOR SYSTEM*

CASS is a task management system that provides facilities for automatic grain-size optimization and task scheduling of parallel programs on distributed memory parallel architectures. The heart of CASS is a clustering module that partitions the tasks of a program into clusters that match the granularity of the target machine. This paper describes the clustering algorithms used by CASS and compares them with the best known algorithms reported in the literature, namely the PY algorithm (for clustering with task duplication) and the DSC algorithm (for clustering with no task duplication). It is shown that the clustering algorithms used by CASS outperform both the PY and DSC algorithms in terms of both speed and solution quality.     

COMPUTING MAXIMUM CLIQUES OF CIRCULAR ARCS IN PARALLEL*

Given a set S of n proper circular arcs, it is required to identify a largest cardinality subset K[S] of S each two of whose members intersect. This paper describes an optimal parallel algorithm to compute K[S]. The algorithm is not based on any previously known sequential solution, and is designed for the CREW PRAM model of computation. It uses 0(n/logn) processors and runs in O(logn) time. An interesting feature of the algorithm is that it transforms the computational geometric problem at hand, to a problem involving computations on 0-1 matrices, and then transforms the latter back into a ray shooting problem in computational geometry.     

无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法

无线传感器网络随节点移动组成自我维持的自组织系统,采用连通支配集的虚拟骨干技术可使平面网络系统层次化而简化节点路由、管理和维护。但大规模无线传感器网络的连通支配集节点数目依然庞大,d-hop连通支配集可以大大减小支配集节点数目。另外,由于存在节点失效、链路断裂等无线特性,虚拟骨干网需要具备一定的容错性。在单位圆盘图网络模型中为构建精简且具有容错能力的虚拟骨干网,提出d-hop 2-连通支配集的分布式构造算法,先构造d-hop独立支配集后再连通形成d-hop 2-连通支配集。并从理论和仿真上对算法的复杂度、近似比和算法性能作了进一步探讨和验证。     

运动目标检测与跟踪的DSP实现

研究了运动目标检测与跟踪的DSP（DigitalSignalProcessor）实现算法,以形心跟踪算法为整个处理系统的核心。采用目标形心跟踪算法,通过目标分割阶段的目标标记,如目标面积、周长、形心位置等信息的提取建立目标跟踪波门,实现目标的连续跟踪,并将此算法移植到sEED—VPM642硬件平台,实验结果表明能够达到预定目标。此外,为了克服形心算法的准确性和实时性缺陷,采用粒子滤波对算法进行必要的扩展,从MATLAB的仿真结果看,除个别采样点存在误差较大的情况,真实值曲线与粒子滤波跟踪曲线拟合较好。     

一种用于指针程序的形状分析方法

指针程序的分析一直是研究热点。本文提出一种基于形状图逻辑的形状分析方法,其中形状分析采用形状图来表达程序中指针的指向和相等关系,并用形状图逻辑来进行推理。形状图逻辑是一种把形状图看成有关指针的断言,并在此基础上对Hoare逻辑进行扩展而得到的程序逻辑。首先介绍所提出的形状图和形状图逻辑;然后在此基础之上,设计一种基于形状图逻辑的形状分析方法。     

基于中值滤波和梯度锐化的边缘检测

实现一种基于中值滤波和梯度锐化的边缘检测方法。首先采用既能过滤噪声又能保护边缘信息的中值滤波对图像进行平滑处理。然后采用梯度锐化加强边缘像素强度,通过简单的二值化获得图像的初始边缘,系统采用连通区域标记的方法去除位于图像封闭边界内的残留黑块。最后通过实验结果与人工提取的结果比较,进行误差分析,找出本文算法的不足之处,以便对该算法进行改进。实践证明,本文的边缘检测方法对含有噪声点且灰度分布比较均匀的图像有很好的效果。     

一种去除椒盐噪声的自适应极值中值滤波算法

针对椒盐噪声的特点,为了更好地滤除图像中的椒盐噪声同时又能较好地保护图像细节,提出一种自适应极值中值滤波算法。该算法通过对窗口内的非噪声点的检测自适应调整窗口大小,使用Max-Min算子作为噪声检测器,通过设置合理的阈值对灰度值等于极大值或者极小值的窗口中心的像素点进行噪声识别,减小将信号点误判为噪声点的概率,然后将检测出的噪声点用窗口内信号点的中值代替,而信号点保持不变直接输出。同时对超过设定的最大窗口的情况,窗口中心的像素点的灰度值用4个相邻的已处理的像素点灰度值的均值进行替换。实验仿真结果证明了该算法滤除椒盐噪声的有效性,在噪声较大时,去噪效果更明显。     

利用二进制数算法寻找5个点的Ramsey图

用二进制数来表示完全图的各种组合,借助计算机编程可从完全图的各种组合中寻找出ramsey图。5个顶点的Ramsey图是最基本的Ramsey图,这种基本方法为寻找更复杂的Ramsey图提供了基础。