多核平台下XEN虚拟机动态调度算法研究

虚拟机调度算法对并行任务的执行效率考虑不够充分。现代处理器平台具备了多个可用的计算核心,使多个虚拟机并发执行成为了现实。针对多核平台下的并行虚拟机调度优化问题,提出一种基于任务特征虚拟机CON-Credit调度算法。该算法在调度并行任务时,使用动态方式对计算机核心进行分配,采用传统的虚拟机调度算法为执行普通任务的虚拟机进行分配;采用定制的同步算法给执行并行任务的虚拟机分进分配。相关实验显示,CON-Credit调度算法能显著提高并行任务的执行效率。     

基于PVM的并行算法研究

随着数据库规模的增长，数据挖掘技术变得非常重要，而且从数据库中挖掘隐藏的规则也变得十分必要．提出了一种在数据库中发现关联规则的并行Apriori算法，并在并行虚拟机(PVM)环境下实现了该算法．该算法是通过在处理器间分割数据来实现数据的并行化的．     

图象处理中边界转换的并行算法及其实现

本文提出了一种把图象中边界转换成区域四分树的并行方法.该方法基于MIMD模型,并在曙光1000上实际运行.整个算法用P个处理器可以在时间O((B×logB)/P)内完成其中B是循环代码长度.该算法可应用于图象处理、计算机图形学、模式识别等领域.     

具有O(n)消息复杂度的协调检查点设置算法

协调检查点设置及回卷恢复技术作为一种有效的容错手段,已广泛地运用在集群等并行/分布计算机系统中.为了进一步降低协调检查点设置的时间和空间开销,提出了一种基于消息计数的协调检查点设置算法.该算法无须对底层消息通道的FIFO特性进行假设,并使同步阶段引入的控制消息复杂度由通常的O(n²)降低到O(n),有效地提高了系统的效率和扩展性.     

EPCCL理论的求交知识编译算法

超扩展规则是对扩展规则的扩充,基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集、差集和并集,并将所得结果以EPCCL（each pair of clauses contains complementary literals）理论的形式保存.基于超扩展规则的性质,本文提出了一种新的EPCCL理论编译算法：求交知识编译算法IKCHER（intersection approach to knowledge compilation based on hyper extension rule）,该算法适合难解类SAT问题的知识编译,同时是一种可并行的知识编译算法.本文还研究了如何实现多个EPCCL理论的求交操作,证明了EPCCL理论的求交过程是可并行执行的,并设计了相应并行求交算法PIAE（parellel intersection of any number of EPCCL）.通过对输入EPCCL理论对应普通子句集的利用,设计了一种高效的并行求交算法imp-PIAE（improvement of PIAE）.基于上述算法本文还设计了两个并行知识编译算法P-IKCHER（IKCHER with PIAE）和impP-IKCHER（IKCHER withimp-PIAE）,分别采用PIAE并行合并算法和imp-PUAE并行合并算法.最后,通过实验验证了大部分情况下IKCHER算法的编译质量是目前为止所有EPCCL理论编译器中最优的,P-IKCHER算法所使用的合并策略并没有起到加速的效果,反而使得编译效率和编译质量有所下降,而impP-IKCHER算法提高了IKCHER算法的编译效率,四核并行下最高可提高两倍.     

一种基于近邻表示的聚类方法

当今社会处在信息急剧膨胀的时代,数据的规模和维度都在不断增大,传统的聚类方法有很多难以适应这一趋势.尤其是移动计算平台的高速发展,其平台自身的特性限制了算法的内存使用规模,因此,以往的很多方法若不进行改进,在这类平台上将无法运行.提出了一种基于近邻表示的聚类方法,该方法基于近邻的思想构造出新的表示形式,这种表示可以进行压缩,因此有效地减少了聚类所需要的存储开销.实现了直接对近邻表示压缩后的数据进行聚类的算法,称为Bit k-means.实验结果表明,该方法取得了较好的效果,在提高准确率的同时,大幅度降低了存储空间开销.     

无线传感器网络中基于Top-|K|查询分布式数据重构方法

针对分簇结构或多Sink节点的无线传感器网络应用场景,提出了一种基于Top-|K|查询的分布式数据重构方法.该方法包括分布式迭代硬阈值算法和基于双阈值的分布式Top-|K|查询算法两个部分.其中,管理节点和成员节点同时运行分布式迭代硬阈值算法,以分布式方式实现迭代硬阈值计算.同时,管理节点和成员节点运行基于双阈值的分布式Top-|K|查询算法,以分布式方式实现前一算法中查询绝对值最大的前K项元素和操作.实验结果表明,该方法的数据重构性能与现有方法无明显差异,同时能够有效地减少管理节点和成员节点之间的交互次数,并且降低网络中传输的数据量.     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2^n/8)的处理机在O(2^7n/16)的时间和O(2^13n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(2^5n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

多层核心集凝聚算法

许多经典的聚类算法,如平均链接,K-means,K-medoids,Clara,Clarans等,都是利用单一的聚类中心进行聚类.为克服单一聚类中心只能描述凸状聚类的缺陷,CURE,DBSCAN等算法使用多个代表点(或稠密点)表述任意形状的聚类结构,但仍难以聚类重叠和噪声数据.为此,提出一种基于多层聚类中心(称为核心集)的凝聚聚类算法(MulCA).该算法使用了多层核心集表述聚类结构,使得每一层数据集向其核心集凝聚.同时,上层的核心集自动成为下层的数据集.随着每层核心集规模按α比例迅速减少,控制了凝聚过程的迭代次数.此外,引入了基于随机采样计算ε-核心集(RBC)的技巧,将MulCA算法应用于大规模数据集.大量的数值实验充分验证了MulCA算法的有效性.     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

Optimal virtual cluster-based multiprocessor scheduling

Scheduling of constrained deadline sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good processor utilization bounds. These algorithms can be broadly classified into two categories: partitioned scheduling in which tasks are statically assigned to individual processors, and global scheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster are globally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based scheduling algorithms, and also consider properties that minimize total processor utilization of individual clusters. In the last part of this paper, we develop new virtual cluster-based scheduling algorithms. For implicit deadline sporadic task systems, we develop an optimal scheduling algorithm that is neither Pfair nor ERfair. We also show that the processor utilization bound of us-edf{m/(2m−1)} can be improved by using virtual clustering. Since neither partitioned nor global strategies dominate over the other, cluster-based scheduling is a natural direction for research towards achieving improved processor utilization bounds.

The Optimal Design of a Planar Parallel Platform for Prescribed Machining Tasks

In this paper a general methodology is presented for determining theoptimum design of a planar parallel platform to be used in machining.The method, based on a mathematical optimization approach, is used tofind a platform design and placement such that firstly, the execution ofa prescribed task path is feasible, and secondly, the actuator forcesrequired to execute the prescribed task are minimized. The applicationof the method is illustrated for two prescribed tasks, five designvariables and a number of geometrical inequality constraints such asactuator length limits. The method succeeds in finding locally optimumand feasible platform designs for which the required task lies insidethe workspace. Two optimization algorithms are implemented and theirrespective results are compared. The first algorithm is a robust andreliable trajectory algorithm, LFOPC, which is however expensive interms of the number of required function evaluations. As the simulationsperformed here in evaluating the objective and constraint functions maybe computationally intensive, an approximation method, Dynamic-Q, isalso used to find the optimum design with greater efficiency. Theeffectiveness of this approximation approach is evaluated.     

利用虚拟机技术构建计算机实践课教学实验平台

针对目前计算机实践课教学中存在的实验设备不足、实验室维护工作量大等问题,本文介绍了利用虚拟机技术,构建虚拟实验平台及网络环境的基本方法,并给出了在该平台上进行计算机实践课教学的具体应用。     

A Visibility Sphere Marching algorithm of constructing polyhedral models for haptic sculpting and product prototyping

This paper presents a Visibility Sphere Marching algorithm of constructing polyhedral models from Dexel volume models for haptic virtual sculpting. Dexel volume models are used as the in-process models representation during interactive modification in a haptic virtual sculpting system. The stock material represented in a Dexel volume model is sculpted into a designed model using a developed haptic sculpting system. The sculpted Dexel volume models are converted to polyhedral surface models in STL format by the proposed visibility sphere marching algorithm. The conversion turns out to be an interesting and challenging problem. The proposed visibility sphere marching algorithm consists of three sub-algorithms: (i) roof and floor covering, (ii) wall-building, and (iii) hole-filling algorithms. The polyhedral surface models converted from the Dexel volume models can then be input to and processed by available computer-aided manufacturing (CAM) or rapid prototyping systems. The presented technique can be used in virtual sculpting, CAD/CAM, numerically controlled machining verification and rapid prototyping.     

两种求解机械手最短时间动作路径规划的新算法及其在基于PVR技术的控制平台上的实现

针对机械手在执行点到点的工作任务中所遇到的两类最短时间动作路径规划(MTMPP)问题, 分别提出了新的混合型进化计算模拟退火(EC SA)算法以及将EC SA算法与一些优化技术结合使用的EC SA-DP算法. 通过与目前较好的求解算法(如弹性网络方法ENM)以及其它一些近似优化算法(如遗传算法和模拟退火算法等)所进行的数值仿真比较, 验证了EC SA算法在处理复杂工作任务时的高效性. 这些算法在基于投射式虚拟现实(PVR)技术的控制平台上进行了虚拟仿真实现, 仿真结果表明可有效地提高虚拟环境中的投射式操作     

多源多目标扫掠体的全六面体网格自动生成算法

为实现多源多目标扫掠体六面体网格生成,提出针对该类形体的全六面体网格自动生成算法.该算法结合虚面和虚拟分解算法,将多源多目标扫掠体自动分解为多个多源扫掠子体;再采用多源扫掠网格生成方法生成各子体网格,整体网格则由各子体网格自动组合而成.文中给出了完整的虚拟分解算法,在虚拟分解流程中的"压印"环节利用改进的边界约束Delaunay三角化方法统一处理各类情形,避免了传统算法复杂的分类讨论.最后给出多个网格实例及其网格质量数据,验证了文中算法的实用性.     

On-line scheduling of scalable real-time tasks on multiprocessor systems

The computation time of scalable tasks depends on the number of processors allocated to them in multiprocessor systems. As more processors are allocated to a scalable task, the overall computation time of the task decreases but the total amount of processors’ time devoted to the execution of the task, called workload, increases due to parallel execution overhead. In this paper, we propose a task scheduling algorithm that utilizes the property of scalable tasks for on-line and real-time scheduling. In the proposed algorithm, the total workload of all scheduled tasks is reduced by managing processors allocated to the tasks as few as possible without missing their deadlines. As a result, the processors in the system have less load to execute the scheduled tasks and can execute more newly arriving tasks before their deadlines. Simulation results show that the proposed algorithm performs significantly better than the conventional algorithm based on a fixed number of processors to execute each task.     

云平台下动态任务调度人工免疫算法

针对云计算领域的任务调度问题,提出了一种基于人工免疫(AI)理论的云计算平台动态任务调度算法。该算法首先利用排队论迅速、粗略地确定云计算平台保持稳态的条件,并为后面的计算提供基础数据;然后利用人工免疫理论中的免疫克隆选择算法,搜索出为集群中各节点上的不同虚拟机分配计算资源的近似最优配置;算法中还加入了适当的负载平衡处理,它使抗体基因更加优良。模拟实验结果表明,该调度算法能有效提高收敛速度和精度,快速搜索到合理配置,提高了集群资源利用率。     

Finding Optimal Ordering of Sparse Matrices for Column-Oriented Parallel Cholesky Factorization

In this paper, we consider the problem of finding fill-preserving sparse matrix orderings for parallel factorization. That is, given a large sparse symmetric and positive definite matrix A that has been ordered by some fill-reducing ordering, we want to determine a reordering that is appropriate in terms of preserving the sparsity and minimizing the cost to perform the Cholesky factorization in parallel. Past researches on this problem all are based on the elimination tree model, in which each node represents the task for factoring a column, and thus, can be seen as a coarse-grained task dependence model. To exploit more parallelism, Joseph Liu proposed a medium-grained task model, called the column task graph, and showed that it is amenable to the shared-memory supercomputers. Based on the column task graph, we devise a greedy reordering algorithm, and show that our algorithm can find the optimal ordering among the class of all fill-preserving orderings of the given sparse matrix A.