基于直径仲裁集的网格网络分布式互斥算法

分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的直径生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用“探测”消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。     

基于半环仲裁集的环网分布式互斥算法

分布式互斥是环网分布式系统的重要问题.根据此类系统的特点,提出了新型的分布式互斥算法.该算法以请求者自身为中心,基于半环生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理.分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.     

基于树拓扑网络的分布式互斥算法

分布式互斥是分布式系统的重要问题.根据树拓扑网络的特点,提出了新型的分布式互斥算法TNDME.算法的运行范围限制在根节点到请求节点之间,采用循径方法生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"最大残存树"探测方法进行系统的容错处理.描述了算法的模型、主要思想、数据结构、消息结构以及伪代码,并证明了算法的正确性.理论性能分析与仿真对比证明,算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.     

非稳定环境下基于竞争消息复杂度的分布式互斥节点容错算法

目前人们已经提出了很多分布式互斥算法.为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题.部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析.本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其时消息复杂度的影响进行详细讨论.在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度.     

非稳定环境下基于竞争消息复杂度的分布式互斥节点容错算法

目前人们已经提出了很多分布式互斥算法。为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题。部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析。本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其对消息复杂度的影响进行详细讨论。在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度。     

一种基于读写互斥的分布式互斥算法

分布式对象系统的容错采用对象冗余来实现,它要求冗余对象各副本具有状态一致性,状态一致性需要对象行为的确定性来保证。文章提出了一种基于读写互斥的分布式互斥算法,保证系统节点能互斥地访问临界资源,从而确保对象行为结果的确定性,尤其是在读频繁的系统中,能大大降低消息复杂度。     

多副本访问控制的分层结构分布式互斥算法

提出了一种用于分布式系统中多副本对象访问控制的分层结构分布式互斥实现方法,可以显著降低分布式系统中互斥访问算法的消息复杂度,并提高了系统和算法的容错能力和稳定性,为构建超大规模分布式系统,保证分布式系统中的多副本对象的互斥和一致访问提供了实现手段。     

一种新的分布式互斥请求集生成算法

分布式互斥请求集的长度、对称性和生成的难易程度以及生成算法占用的空间及耗费的时间直接影响着基于该请求集的分布式互斥算法的消息复杂度、对称性和算法的应用规模。本文在基于循环编码的分布式互斥请求集生成算法的基础上,提出了一种增加算法初始化节点数量的对称分布式互斥请求集生成算法。其生成的请求集长度小于2N0.5,其时间复杂度也比基于循环编码的分布式互斥请求集生成算法小。因此,该算法较已有的分布式互斥请求集生成算法在性能上具有较大提高。     

一种基于消息槽的K资源互斥算法

在分布式操作系统等一些有多个进程同时活跃的应用中,必须妥善解决不同进程对资源的需求,即同步与互斥问题.文章提出了一种基于消息槽的K资源互斥算法,介绍了该算法的原理,详细描述了该算法的运作过程,并进行了深入的分析.分析结果表明,该算法能够有效地满足K资源分布式环境下同步与互斥的要求.     

一种基于消息槽的K资源互斥算法

在银行系统等有多个实体同时活跃的分布式应用中,必须妥善解决不同实体对资源的需求,即同步与互斥。本文基于令牌的K资源互斥算法,提出了基于消息槽的K资源互斥算法,该算法能有效满足K资源分布式环境下同步与互斥的要求。     

基于子网的三维Mesh网络容错广播路由算法

在并行计算机系统中,广播通信是极为重要的通信模式之一。该文基于k-Mesh子网(子立方体)连通的概念提出一个基于局部信息和分布式的三维Mesh网络容错广播路由算法。该算法利用邻结点的状态信息,动态地构建以单个k-Mesh子网为结点的广播树,该广播树能容忍相当多的结点出错。模拟结果表明广播路由算法的广播时间步接近最优的。该算法只要求结点知道它的邻结点的状态,而无需知道整个网络状态信息,也就是说,这些算法是基于局部信息的,因而具有很好的实际意义。     

Mesh Simplification

Mesh simplification is an important stage after surface reconstruction since the models produced can contain a large number of polygons making them difficult to manipulate. In this paper we present a mesh simplification algorithm to reduce the number of vertices in a dense mesh of triangles. The algorithm is based on edge operations that are performed in the inside of independent clusters distributed over the entire mesh. The clusters are well-characterized regions that can successfully accept simplification operations. The simplification operations produce only local transformations on the mesh. This region-based, distributed approach permits to easily track and control the changes in the triangulation and avoids the appearance of particular cases that would require a special handling. The algorithm uses two user-specified parameters to guide the operations. These parameters allow various simplification strategies that are illustrated on several dense triangulations.     

异构系统动态负载平衡的扩散算法

动态负载平衡是大规模并行计算中的一个十分重要的研究领域．它的主要方法是将计算负载通过并行计算机节点间的互连网络从负载高的节点移至负载低的节点．以前的学者针对同构系统提出了扩散算法等，对于异构系统研究得很少．该文研究了在异构系统中的扩散算法，在理论上证明了该方法的守恒性与收敛性，提出了一种构造异构系统的扩散矩阵的方法，并在不同规模的二维格栅网结构上进行试验，初步试验表明，该方法能够有效地对异构系统进行负载平衡，对于规模较小的系统收敛速度较快，而对于较大的系统，收敛速度慢一些．     

一种基于单播的大规模Mesh网络容错多播路由新算法

本文基于k-Mesh子网连通的概念提出一种基于局部信息和分布式的Mesh网络容错多播路由算法：该算法的基本思想是把大规模的Mesh网络分成若干个较小的子网，多播消息只在各子网间进行路由，并由各子网独立完成操作。该算法的时间复杂性是线性的，模拟结果表明多播路由算法的多播时间步接近网络的直径。     

Weighted residual methods and the suboptimal control of distributed parameter systems†

A suboptimal control algorithm for distributed parameter systems is developed in a framework which synthesizes weighted residual methods and mathematical programming. The heat exchanger example of Koppel et al. (1968) is employed for introducing the algorithm. First, the Galerkin procedure with polynomial modes is applied to obtain a lumped ODE model for the distributed parameter system. Then the state and control variables of the lumped control problem are approximated by cubic splines on a uniform mesh. Through collocation at the knots, the ODE model is reduced to a sot of linear algebraic equations and the suboptimal control is determined from the solution of a quadratic programming problem with sparse matrices.

Numerical results for the heat exchanger example are presented and compared with those obtained by the authors (Neuman and Sen 1972) using the Ritz-Trefftz algorithm (Bosarge and Johnson 1970) for the lumped control problem. For this example, the two algorithms yield essentially identical results with comparable computational requirements. Application of the Ritz-Trefftz algorithm, however, is limited to lumped, linear-quadratic control problems without constraints on the state or control. The approach advocated in this paper, therefore, offers a viable approach to control problems in distributed parameter systems.     

结合边折叠和局部优化的网格简化算法

针对目前网格简化算法在将三维模型简化到较低分辨率时,网格模型的细节特征丢失、网格质量不佳的问题,提出一种保持特征的高质量网格简化算法。引入顶点近似曲率的概念,并将其与边折叠的误差矩阵结合,使得简化模型的细节特征在最大限度上得到保持。同时分析简化后三角网格的质量,对三角网格作局部优化处理,减少狭长三角形的数量,提高简化模型的网格质量。使用Apple模型和Horse模型进行实验,并与一种经典的基于边折叠的网格简化算法以及其改进算法之一进行对比。实验结果显示,两种对比算法三角网格分布过于均匀,局部细节模糊不清,而所提算法的三角网格在曲率大的区域稠密,在平坦处稀疏,细节特征清晰可辨;简化模型的几何误差的数量值与两种对比算法处于同一数量级;所提算法的简化网格的平均质量远高于两种对比算法。实验结果表明,在不扩大几何误差的情况下,所提算法不仅具有较强的细节特征保持能力,而且简化模型的网格质量较高,视觉效果较好。     

基于四叉树结构的数字地表模型快速生成算法设计

为了研究数字地表模型的快速生成方法，在总结传统Delaunay三角化算法的基础上，给出了一个基于四叉树结构的数字地表模型快速生成算法的详细设计，该算法的基本思想是首先利用四叉树结构来对离散点进行分割，然后对四叉树叶节点进行Delaunay三角化，再两两合并四叉树节点三角网的凸壳，以快速生成地表表格网模型，该算法是以四叉树为基本单位为实现限定边和限定多边形的快速嵌入，最后给出了算法在不同情况下的测试结果，并对测试结果进行了具体分析，给出了算法的时间效率分析和空间复杂性分析，实测数据结果表明，该算法有着较好的性能，而且也非常稳定，通过实测结果分析和算法的时间效率分析，可以得到算法的时间效率近似为O(nlog(n）），通过算法的空间复杂性分析可以看出，算法可以自动适应不同的点空间分布情况，而且采用四叉树结构也非常有利于限定边和限定多边形的嵌入。     

Incorporating object-centered sampling and Delaunay tetrahedrization for visual hull reconstruction

In this paper we present a novel shape from silhouette algorithm. For an object to be modeled, the algorithm first computes a cloud of points located on a pencil of rays and distributed evenly on the visual hull surface, inside and outside the visual hull. Then Delaunay tetrahedrization is applied to the point cloud to partition its convex hull into a set of tetrahedrons. Finally, outlier tetrahedrons are removed by tetrahedron peeling, and a mesh model of the visual hull is extracted. The algorithm is robust, free from discretization artifacts, and produces a mesh model composed of well-shaped triangles.     

异构无线网状网分布式接口和信道联合分配的研究*

研究了无线网状网络中分布式分配信道时,接口异构对网络容量的影响。提出了一种新颖的以射频链路为信道分配对象的接口和信道联合分配ILP模型,给出了一种自适应于网络流量变化的分布式贪婪算法。该算法以射频链路为信道分配对象,基于2-hop干扰模型,以队列长度为权的射频链路吞吐量之和最大为目标,寻找自适应流量变化的分布式分配方案。分析发现,该算法与目前已有的非接口异构的Dist. Greedy算法的时间复杂度相当,仿真结果表明本算法下的网络性能有明显提升。