正方形Mesh中的Gossiping算法

1 介绍在并行计算和分布式计算中,处理器之间的通信是一个重要课题。在一个计算机网络中,如果网络中的每一个处理器都要把一个消息传给其他所有处理器,这样的通信问题我们称之为Gossiping。由于Gossiping问题具有大通信量的特点,它通常可以被用来衡量一个互联网络的通信能力。同时,Gos-siping也经常作为一些实际计算的嵌入式操作来使用。例如在矩阵的乘法和Load Balancing中都使用到了Gossiping算法。 Krumme等提出四种研究Gossiping问题的模型:H~*(half-duplex,all-port),H1(half-duplex,one-port),F~*(full-duplex,all-port),F1(full-duplex,one-port)。在本文中,我们     

Automatic generation of quadrilateral finite element meshes

This paper describes an efficient, accurate and simple implementation of an algorithm for generation of quadrilateral finite element meshes. An original algorithm by Talbert and Parkinson [J.A. Talbert, A. Parkinson, Development of an automatic two-dimensional finite element mesh generator using quadrilateral elements and Bezier curve boundary definition, Int. J. Numer. Meth. Eng., 29 (1990) 1551–1567], has been substantially redeveloped and modified and presented in greater detail. We cover several important issues omitted in publication mentioned and we will provide interested readers with fully documented source code of the program.     

Two-dimensional adaptive mesh generation algorithm and its application with higher-order compressible flow solver

A combined procedure for two-dimensional Delaunay mesh generation algorithm and an adaptive remeshing technique with higher-order compressible flow solver is presented. A pseudo-code procedure is described for the adaptive remeshing technique. The flux-difference splitting scheme with a modified multidimensional dissipation for high-speed compressible flow analysis on unstructured meshes is proposed. The scheme eliminates nonphysical flow solutions such as the spurious bump of the carbuncle phenomenon observed from the bow shock of the flow over a blunt body and the oscillation in the odd-even grid perturbation in a straight duct for the Quirk’s odd-even decoupling test. The proposed scheme is further extended to achieve higher-order spatial and temporal solution accuracy. The performance of the combined procedure is evaluated on unstructured triangular meshes by solving several steady-state and transient high-speed compressible flow problems.     

Planar quadrilateral quality measures

This article examines the quality assessment of planar quadrilateral mesh elements in a comprehensive way. First, an analytic characterization of quadrangular shape is provided, and existing concepts of stretching and skewness, earlier proposed for specific geometries, are generalized. Then, two triangle quality measures are extended to quadrilaterals and their respective extremal and asymptotic behaviors examined, showing in particular that even if needed they cannot detect the triangular degeneracy of a quadrilateral. An existing quality measure is then discussed, which is able to handle this case. In particular, an unbalanced asymptotic behavior is demonstrated, justifying the need for a new approach. Toward this goal, the triangle quality measure based on Frobenius norm is modified in order to replace equilateral reference element by right isosceles triangles, with control on the specific right angle. Finally, two new quadrilateral quality measures are designed and examined using these results. Numerical results illustrate the matter.     

Electron temperature control in low-pressure plasmas using a two-mesh-separation technique

Independent control over the electron temperature and ion bombarding flux has been achieved in weakly ionised discharge through the use of two electrically biased meshes. The meshes divide the discharge into two parts; a main RF plasma and dc processing plasma, the latter is sustained through controlled diffusion of particles from the main plasma. By varying the bias to each of the grids separately, and at typical pressures of 2.6 Pa in the processing chamber, the electron temperatures can be varied in the range 0.2-5.6 eV. To an electrically isolated surface, the ion bombarding fluxes can be controlled between 0.2 and 5.4×10¹⁸ m² s⁻¹. This method of electron temperature control, which gives more flexibility than the single grid separation technique, allows ion energies to be varied from 1 to 27 eV, independently of the ion flux. This is useful, both for the fundamental study of plasma-surface interactions and for developing discharges with controlled parameters to tailor the properties of materials such as polymeric surfaces.     

Enhanced fault tolerant routing algorithms using a concept of “balanced ring”

Fault rings can be used to guide messages bypass faulty nodes/links in a fault tolerant interconnection network. However, nodes on the fault ring become hot spots, thus causing uneven distribution of the traffic loads. To avoid such traffic congestion, a concept of the balanced ring is proposed in this paper. The proposed balanced ring, defined as concentric rings of a given fault ring, can be applied to the fault tolerant routing algorithms for mesh and torus topologies. By properly guiding messages to route on the balanced ring and the fault ring, more balanced link utilization and greatly reduced traffic congestion can be achieved on a fault tolerant network. Methods of applying the balanced ring concept to some published fault tolerant routing algorithms are discussed. Proof of deadlock and livelock freedom is also presented. The use of balanced ring does not need to add new virtual channels. The performance of two routing algorithms with and without the balanced ring is simulated and evaluated. The results indicate that routing algorithms with the balanced rings constantly yield larger throughput and smaller latency than those without.     

Fair webs

Fair webs are energy-minimizing curve networks. Obtained via an extension of cubic splines or splines in tension to networks of curves, they are efficiently computable and possess a variety of interesting applications. We present properties of fair webs and their discrete counterparts, i.e., fair polygon networks. Applications of fair curve and polygon networks include fair surface design and approximation under constraints such as obstacle avoidance or guaranteed error bounds, aesthetic remeshing, parameterization and texture mapping, and surface restoration in geometric models.     

Reconstruction of 3D Object Meshes from Silhouette Images

In this work we propose a method for computing mesh representations of 3D objects reconstructed from a set of silhouette images. Our method is based on the polygonization of volumetric reconstructions by using a modified version of the dual contouring method. In order to apply dual contouring on volumetric reconstruction from silhouettes we devised a method that is able to determine the discrete topology of the surface in relation to the octree cells. We also developed a new scheme for computing hermitian data representing the intersections of conic volumes with the octree cells and their corresponding normals with subpixel accuracy. Due to the discrete and extremely noisy nature of the data used in the reconstruction we had to devise a different criterion for mesh simplification that applies topological consistency tests only when the geometric error measure is beyond a given tolerance. We present results of the application of the proposed method in the extraction of a mesh corresponding to the surface of objects of a real scene.     

Data perturbation for fewer triangles in marching tetrahedra

A simple efficient method is proposed to reduce the total number of triangles in an isosurface extraction method based on tetrahedral decomposition. We slightly perturb the input volumetric data so that useless small and thin triangles are removed. The perturbed volumetric data contain the exact isovalues from which a mesh is extracted. Since the proposed method is a pre-process of an isosurface extraction, it is not necessary to modify the mesh structure unlike the other similar methods.     

Static load balancing applied to Schur complement method

A finite element method often leads to large sparse symmetric and positive definite systems of linear equations. We consider parallel solvers based on the Schur complement method on homogeneous parallel machines with distributed memory. A finite element mesh is partitioned by graph partitioning. Such partitioning results in submeshes with similar numbers of elements and, consequently, submatrices of similar sizes. The submatrices are partially factorised. The time spent on the partial factorisation can be different, i.e., disbalanced, because methods exploiting the sparsity of submatrices are used. This paper proposes a Quality Balancing heuristic that modifies classic mesh partitioning so that the partial factorisation times are balanced, which saves overall computation time, especially for time dependent mechanical and nonstationary transport problems.