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.     

Horizons of Parallel Computation

This paper considers the ultimate impact of fundamental physical limitations-notably, speed of light and device size-on parallel computing machines. Although we fully expect an innovative and very gradual evolution to the limiting situation, we take here the provocative view of exploring the consequences of the accomplished attainment of the physical bounds. The main result is that scalability holds only for neighborly interconnections, such as the square mesh, of bounded-size synchronous modules, presumably of the area-universal type. We also discuss the ultimate infeasibility of latency hiding, the violation of intuitive maximal speedups, and the emerging novel processor-time tradeoffs.     

并行计算模型

1.引言为提高系统性能,并行机系统设计者在体系结构上采用了多种新技术,然而目前并行软件(包括系统软件和应用软件)的研究和开发远远落后于体系结构的进步,即体系结构上的进步并未充分反映到并行软件的设计中。相比之下,串行计算和串行软件的研究是成功的,原因之一在于有一个简单而又代表了串行计算主要性能特征的计算模型(Random Ac-cess Machines,RAM)。而并行计算缺少这样一个简单、被广泛接受并在并行计算中起同等重要作用的模型。“确定少量的并行计算模型以作为程序设计语言的自然基础,并有助于高性能硬件的实现”,这一课题仍是国际公认的并行处理中具挑战性课题之一。     

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程序的并行效率很高。     

并行计算性能的“双流”分析

The generalized speed-up is estimated according to the "double-stream" analyses. The term"decreasing ratio" is used to describe the influence of the hierarchical memory and the characteristics of parallel application on the performance. The optimization principles for parallel computation are also given.     

基于模糊粗糙集的粒度计算

粒度计算是一种新的智能计算的理论和方法,目前受到很多学者的关注。但是,具体可行的粒表示模型和不同粒的推理方法研究相对较少。本文将模糊粗糙集纳入粒度计算这种新的理论框架,对于处理复杂信息系统,求解复杂问题无疑具有重要的意义。首先利用笛卡尔积,构建了模糊关系下的信息粒;然后给出不同粒度下模糊粗糙算子的表示方法,进而形成一个分层递阶结构;最后考虑了对于模糊信息系统粒度粗细的选择问题,并给出一个实例,从而为粒度计算提供一个具体而实用的框架。     

并行计算模型对比分析

随着集群式系统的发展,并行计算模型在估计和评价系统的性能、引导集群的体系结构以及指导并行算法和程序的设计等方面都显得越来越重要。对于目前已有的并行计算模型的设计思想和原理的了解和分析,非常有利于新的模型的设计与研究。本文首先介绍了目前比较常见的5种并行计算模型,接着在同步性、通信方式和参数等3个方面分析比较了它们的异同和优缺点,最后得出结论,指出了下一代并行计算模型的发展趋势是与具体应用相关的并行计算模型。     

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

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

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

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

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

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

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.     

Krylov子空间方法及其并行计算

Krylov子空间方法在提高大型科学和工程计算效率上起着重要作用。本文阐述了Krylov子空间方．法产生的背景、Krylov子空间方法的分类,在此基础上,研完了分布式并行计算环境下Krylov子空间方法的并行计算方法,给出了Krylov子空间方法的并行化策略。     

WCNS高精度并行软件的大规模计算研究

本文通过求解任意坐标系下的定常雷诺平均N-S方程和SST两方程湍流模型,采用五阶精度的加权紧致非线性格式(WCNS-E-5),实现流场的高精度数值模拟;基于分布式存储系统,采用MPI并行编程环境、非堵塞通信机制和遗传算法负载平衡,实现高精度模拟软件的并行化。在国防科学技术大学高性能计算应用研究中心的"天河"系统上完成软件移植、测试,通过对DLR-F6翼身组合体的模拟,说明软件并行策略和开发的正确性。最后,实现某民机全机的高精度并行模拟,网格规模达到1亿,为下一步WCNS高精度并行软件的大规模工程实际应用打下了坚实基础。     

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

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

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

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

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.     

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校验码的计算。     

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.