Parallel Computation of the Topology of Level Sets

This paper introduces two efficient algorithms that compute the Contour Tree of a three-dimensional scalar field F and its augmented version with the Betti numbers of each isosurface. The Contour Tree is a fundamental data structure in scientific visualization that is used to pre-process the domain mesh to allow optimal computation of isosurfaces with minimal overhead storage. The Contour Tree can also be used to build user interfaces reporting the complete topological characterization of a scalar field, as shown in Figure~\ref{fig:top}. Data exploration time is reduced since the user understands the evolution of level set components with changing isovalue. The Augmented Contour Tree provides even more accurate information segmenting the range space of the scalar field into regions of invariant topology. The exploration time for a single isosurface is also improved since its genus is known in advance. Our first new algorithm augments any given Contour Tree with the Betti numbers of all possible corresponding isocontours in linear time with the size of the tree. Moreover, we show how to extend the scheme introduced in [3] with the Betti number computation without increasing its complexity. Thus, we improve on the time complexity in our previous approach from O(m log m) to O(n log n + m), where m is the number of cells and n is the number of vertices in the domain of F. Our second contribution is a new divide-and-conquer algorithm that computes the Augmented Contour Tree with improved efficiency. The approach computes the output Contour Tree by merging two intermediate Contour Trees and is independent of the interpolant. In this way we confine any knowledge regarding a specific interpolant to an independent function that computes the tree for a single cell. We have implemented this function for the trilinear interpolant and plan to replace it with higher-order interpolants when needed. The time complexity is O(n + t log n), where t is the number of critical points of F. For the first time we can compute the Contour Tree in linear time in many practical cases where t = O(n^1–). We report the running times for a parallel implementation, showing good scalability with the number of processors.     

The Digital Topology of Sets of Convex Voxels

Classical digital geometry deals with sets of cubical voxels (or square pixels) that can share faces, edges, or vertices, but basic parts of digital geometry can be generalized to sets S of convex voxels (or pixels) that can have arbitrary intersections. In particular, it can be shown that if each voxel P of S has only finitely many neighbors (voxels of S that intersect P), and if any nonempty intersection of neighbors of P intersects P, then the neighborhood N(P) of every voxel P is simply connected and without cavities, and if the topology of N(P) does not change when P is deleted (i.e., P is a “simple” voxel), then deletion of P does not change the topology of S.     

多核计算机上的并行计算

研究了多核计算机上0penMP＋Vc＋＋编程模式的并行程序,并在双核和四核计算机上分别使用传统算法和并行算法计算数列求和、矩阵乘积及矩阵Cholesky分解。试验表明,传统串行程序只能利用多核计算机的一个核资源,而采用OpenMP程序的并行效率很高。     

利用并查集实现电力系统结线的动态分析

提出利用并查集实现电力系统结构动态分析的方法。将电力系统结线中的支路作为开关,将电力系统结线中的元件分析为并查集的元素,将电力系统结线中的开关作为等价对,从而利用并查集对电力系统的结线进行分析。通过对一个电力系统模型的分析,表明了该方法的可行性和有效性。     

Parallel Algorithms for Maximal Acyclic Sets

Given a graph G=(V,E), the well-known spanning forest problem of G can be viewed as the problem of finding a maximal subset F of edges in G such that the subgraph induced by F is acyclic. Although this problem has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset U of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. In this paper we present NC algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vertices, the problem can be solved in time with O(n) processors on an EREW PRAM. Second, we show that the problem is solvable in NC if the input graph G has only vertex-induced paths of length polylogarithmic in the number of vertices of G. As a consequence of this result, we show that certain natural extensions of the well-studied maximal independent set problem remain solvable in NC. Moreover, we show that, for a constant-degree graph with n vertices, the problem can be solved in time with O(n ² ) processors on an EREW PRAM. Received July 3, 1995; revised April 1, 1996.     

用布尔代数方法计算最小碰集

在基于模型的诊断中,模型一般都是用布尔代数来表示,而计算碰集(hitting sets)则采用HS-树或图,这就使得诊断系统采用多种不同的数据结构,给编程实现带来了不便．本文用布尔代数变量表示待诊断系统的部件,并给出了用布尔代数直接计算最小碰集的算法．数据结构更为简单,只需要布尔表达式,相当于字符串,效率上比其他的一些研究结果也要好,同时可克服丢失正确解的问题,具有通用性．     

判断集合包含关系的安全计算协议

研究了安全计算中关于集合的问题:A拥有一个秘密的集合SA,B拥有一个秘密的集合SB(SA和SB来自一个全集),双方希望知道SA是否包含SB,但是不希望泄漏关于集合SA和SB的其它有用信息.针对此问题,提出了3个具有不同效率和安全性的安全计算协议.设集合SB的大小为NB.第1个协议基于叠加密(或者支持门限解密的加法同态加密方案),需要NB轮通信.另外两个协议基于普通的加法同态加密方案,仅需一轮通信.与同类成果比,前两个协议使用了新的集合表示法,第3个协议在输出结果阶段不需要门限解密,通信效率较好.     

并行计算在高超声速流场数值模拟中的应用

采用计算流体力学方法,对高超声速流场进行了多区并行计算研究。基于MPI消息传递库采用Fortran语言编制了CFD并行计算程序,对NS方程采用AUSMPW+格式和LU-SGS方法求解。针对流场采用多区剖分,将每一个子区分配给相应节点进行计算。每一迭代步,相邻子区域间交换边界数据。计算表明,本文所建立的程序和方法是可行的,能够进一步延伸到大规模并行计算和工程应用中。     

Superlinear Performance in Real-Time Parallel Computation

Can a parallel computer with n processors solve a computational problem more than n times faster than a sequential computer? Can it solve it more than n times better? New computational paradigms offer an affirmative answer to the above questions through concrete examples in which the improvement in speed or quality is superlinear in the number of processors used by the parallel computer. Furthermore, the improvement is consistent and provable. All examples are characterized by the presence of one or several real-time input streams. In one of the examples, an exponential improvement in speed is achieved despite the fact that the processors of the parallel computer are significantly slower than their sequential counterpart. In another example, the improvement in quality is unbounded. A metaphor from everyday life motivates each computational paradigm in which a superlinear improvement in performance is exhibited.     

多核微机基于OpenMP的并行计算

随着四核微机走向市场和八十核处理器在实验室研制成功,多核正引领软件研发发生基础性变化。开发人员需要在代码中添加线程来利用系统所提供的多个内核,从而提升PC应用软件的功能和性能。文中探讨在多核微机上进行并行计算的实现技术。介绍了共享存储系统并行编程接口OpenMP的模型、指令和库函数,以及Intel C 编译器9.1和Microsoft Visual Studio 2005等对OpenMP的支持;着重探讨了二维离散快速傅里叶变换并行算法的设计、实现与优化技术;展望了高性能并行计算软构件库的开发前景。     

CRC校验码并行计算的FPGA实现

用软件实现CRC校验码计算很难满足高速数据通信的要求，基于硬件的实现方法中，有串行经典算法LFSR电路以及由软件算法推导出来的其它各种并行计算方法。以经典的LFSR电路为基础，研究了按字节并行计算CRC校验码的原理，并以常见的CRC-16和CRC-CCITT为例，用VHDL语言进行了可综合设计。结果表明这种实现方法在速度和占用资源方面优于常见的设计，适合在FPGA中实现CRC校验码的计算。     

CRC校验码并行计算的FPGA实现

用软件实现CRC校验码计算很难满足高速数据通信的要求,基于硬件的实现方法中,有串行经典算法LFSR电路以及由软件算法推导出来的其它各种并行计算方法。以经典的LFSR电路为基础,研究了按字节并行计算CRC校验码的原理,并以常见的CRC-16和CRC-CCITT为例,用VHDL语言进行了可综合设计。结果表明这种实现方法在速度和占用资源方面优于常见的设计,适合在FPGA中实现CRC校验码的计算。     

并行网络模拟中拓扑抽象算法的研究

并行网络模拟是研究网络的一个重要方法,由于有限的硬件资源的限制,无法完成大规模的网络模拟。提高模拟的抽象度是一种减少资源、提高模拟性能的好方法,它的基本思想是精简网络模拟模型。为了提高并行网络模拟的规模,本文提出一种简化拓扑算法,该算法抽象了拓扑中的所有主机和部分路由器,提高了并行网络模拟的性能。     

电力系统并行计算研究

介绍PC机群计算环境下的电力系统潮流计算模型,结合基于节点分割的网络分块方法和PC机群环境的特点,提出了一种基于网络数学分割的电力系统潮流分解协调算法.测试结果表明此算法具有较高的加速度和计算精度,适合在网络计算环境中实现.     

Parallel Computation of Wavelet Transforms Using the Lifting Scheme

The lifting scheme [14] is a method for construction of biorthogonal wavelets and fast computation of the corresponding wavelet transforms. This paper describes a message–passing parallel implementation in which high efficiency is achieved by a modified data–swapping approach allowing communications to overlap computations. The method illustrated by application to Haar and Daubechies (D4) wavelets. Timing and speed–up results for the Cray T3E and the Fujitsu AP3000 are presented.     

Digital Topology: Regular Sets and Root Images of the Cross-Median Filter

In the study of topological properties of digital images, which is the central topic of digital topology, one is often interested in special operations on object boundaries and their properties. Examples are contour filling or border following. In classical topology there exists the strong concept of regularity: regular sets in R² show no exotic behaviour and are extensively used in the theory of boundary value problems. In this paper we transfer the concept of regularity to digital topology within the framework of semi-topology. It is shown that regular open sets in (a special) semi-topology can be characterized graphically. A relationship between digital topology and image processing is established by showing that regular open digital sets, interpreted as digital pictures, are left unchanged when the cross-median filter is applied.     

Computation of Feasible and Invariant Sets for Interpolation-based MPC

The terminal invariant set plays a key role in the stabilizing MPC (Model Predictive Control) formulation. When control gains of the terminal local control laws and corresponding feasible and invariant sets are given, the existing interpolation methods unite them to enlarge the stabilizable region and enhance performance. In this paper, when an invariant set is given, an algorithm is proposed to find another invariant set such that their convex hull is maximized and also invariant. Numerical examples show that the set of the stabilizable initial state of the MPC is enlarged by the terminal constraint set computed by an interpolation-based approach.

     

水声宽带信号波形预报的并行算法

针对利用频域方法实现水声宽带信号波形预报过程中计算量较大的问题,引入频域宽带近似展开模型,研究了适合该宽带模型特点的并行算法,将串行模型并行化,并对宽带信号波形并行算法的可行性和有效性进行了分析,通过仿真分析利用模型的并行算法,在典型浅海负跃层和深海声道环境下,波形预报速度分别提高了26倍和24.6倍,计算效率都在75%以上,有效的实现了水下宽带声场的快速准确预报,为实现大规模信号级仿真奠定基础。     

Parallel Biomolecular Computation: Models and Simulations

This paper is concerned with the development of techniques for massively parallel computation at the molecular scale, which we refer to as molecular parallelism. While this may at first appear to be purely science fiction, Adleman [Ad1] has already employed molecular parallelism in the solution of the Hamiltonian path problem, and successfully tested his techniques in a lab experiment on DNA for a small graph. Lipton [L] showed that finding the satisfying inputs to a Boolean expression of size n can be done in O(n) lab steps using DNA of length O(n log n) base pairs. This recent work by Adleman and Lipton in molecular parallelism considered only the solution of NP search problems, and provided no way of quickly executing lengthy computations by purely molecular means; the number of lab steps depended linearly on the size of the simulated expression. See [Re3] for further recent work on molecular parallelism and see [Re4] for an extensive survey of molecular parallelism. Our goal is to execute lengthy computations quickly by the use of molecular parallelism. We wish to execute these biomolecular computations using short DNA strands by more or less conventional biotechnology engineering techniques within a small number of lab steps. This paper describes techniques for achieving this goal, in the context of well defined abstract models of biomolecular computation. Although our results are of theoretical consequence only, due to the large amount of molecular parallelism (i.e., large test tube volume) required , we believe that our theoretical models and results may be a basis for more practical later work, just as was done in the area of parallel computing. We propose two abstract models of biomolecular computation. The first, the Parallel Associative Memory (PAM) model, is a very high-level model which includes a Parallel Associative Matching (PA-Match) operation, that appears to improve the power of molecular parallelism beyond the operations previously considered by Lipton [L]. We give some simulations of conventional sequential and parallel computational models by our PAM model. Each of the simulations use strings of length O(s) over an alphabet of size O(s) (which correspond to DNA of length O(s log s) base pairs). Using O(s log s) PAM operations that are not PA-Match (or O(s) operations assuming a ligation operation) and t PA-Match operations, we can: 1. simulate a nondeterministic Turing Machine computation with space bound s and time bound 2 ^O(s) , with t = O(s) , 2. simulate a CREW PRAM with time bound D, with M memory cells, and processor bound P, where here s = O( log (PM)) and t = O(D+s), 3. find the satisfying inputs to a Boolean circuit constructible in s space with n inputs, unbounded fan-out, and depth D, where here t = O(D+s). We also propose a Recombinant DNA (RDNA) model which is a low-level model that allows operations that are abstractions of very well understood recombinant DNA operations and provides a representation, which we call the complex , for the relevant structural properties of DNA. The PA-Match operation for lengthy strings of length s cannot be feasibly implemented by recombinant DNA techniques directly by a single step of complementary pairing in DNA; nevertheless we show this Matching operation can be simulated in the RDNA model with O(s) slowdown by multiple steps of complementary pairing of substrings of length 2 (corresponding to logarithmic length DNA subsequences). Each of the other operations of the PAM model can be executed in our RDNA model, without slowdown. We further show that, with a further O(s)/ log (1/ε) slowdown, the simulations can be done correctly with probability 1/2 even if certain recombinant DNA operations (e.g., Separation) can error with a probability ε. We also observe efficient simulations can be done by PRAMs and thus Turing Machines of our molecular models. Received December 30, 1995; revised December 30, 1996, and January 22, 1998.