中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
科学计算可视化系统及非张量积区域HFFT算法
作者: 姚继锋
答辩日期: 2004
专业: 计算机软件与理论
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
关键词: 科学计算可视化系统 ; 油藏数值模拟 ; 分子模拟 ; 并行HFFT ; 平行六边形区域 ; 平行十二面体区域
其他题名: Scientific Visualization System and HFFT over Non-Tensor Product Domains
摘要: 近些年来,随着计算机硬件技术的飞速发展,利一学计算的能力越来越强,随之产生了规模庞大的计算数据,如何对这些海量数据进行有效、快捷的可视化,是急需解决的问题。它不仅包括如何更快的去处理数据,还包括如何更好的表达数据。基于Clus七er和投影设备的显示墙技术是最近研究的热点,它不仅通过多个显示设备的拼接实现大屏幕输出,而且Cluster作为后台的驱动设备有利于可视化的并行处理。我们对此技术进行了探讨,并提出了基于大屏幕显示的可视化系统模型。传统的可视化系统采用Client-Server结构,这种结构降低了系统的灵活性,不利于可视化Cliellt端和计算Server端的扩展和更新。我们在两者之间引入通讯中间件(Commware),隐藏Client和Server之间的通讯细节,使得它们成为彼此独立的子系统,这给系统的维护、扩充和重用带来了很大的便利。作为Cliellt-Commware-Server结构的应用实例,我们分别研制了两个大规模科学计算可视化系统:PRIS-Exlorer(油藏模拟后处理系统)和SMSP(分子模拟系统)。前者开发的关键在于大规模并行计算数据的处理和面向对象技术的运用;后者的关键则是一个基于OPenGL的分子建模系统的实现。无论是作为科学计算可视化的研究课题,还是作为自主版权行业应用软件的开发,这两个系统的实现都有着重要的意义。数据处理是大规模科学计算可视化中的难点和关键,它包括了对海量离散数据的压缩、存储、传输和绘制,而快速傅立仆卜变换(FF)则是处理上述问题的重要算法之一。作为公认的上个世纪最重要的基础算法之一,FFT在包括可视化尤其是大规模科学计算可视化在内的众多领域有着广泛的应用。但无论是一维还是高维情形,现有的傅立叶变换均是基于张量积方法将高维问题转化为低维问题进行处理,这大大限制了傅立叶变换的应用范围。如何定义非规则区域上的傅立叶变换并实现相应的FFT算法,一直是棘手的问题。本文在理论上的主要贡献就是利用多色排序、区域分解和多重网格的思想,设计了二维三方向平行六边形区域和三维四方向平行+二面体区域上广义离散傅立叶变换的快速算法并给出它在PC Linux机群上的并行实现。我们把这类二维三方向、三维四方向以及一般的m维m+1方向区域上的广义离散傅立叶变换统一记为HFFT(High-dimellsionFast Fourier Transfor-mation)。HFFT是典型的数据密集型计算,通讯在计算过程中占绝对的主导地位,获得高性能并行算法的关键在于如何尽可能减少数据通讯。通过选用特定的数据结构,并充分利用HFFT算法的内在并行性,本文提出了一种基于分布式存储的并行HFFT算法。在多达128个CPU的微机机群上的数值实验表明,此算法具有较好的并行性能。本文的主要贡献如下:提出了使用大屏幕显示技术、适用于大规模科学计算可视化系统的Client-Commwal-Server模型;实现了油藏数值模拟和分子模拟两个大规模科学计算的可视化系统;给出了二维三方向六边形区域、三维四方向十二面体区域上的HFFT算法。将变换的计算复杂度分别从直接计算的O(N4)和O(N6)量级降到了快速算法的O(N2 logN)和O(N3logN)量级;最后,本文给出了一种基于分布式存储的并行HFFT算法,并对影响、提高并行算法的若干因素进行了分析。
英文摘要: Scientists nowadays have unprecedented computing and instrumental capability for studying natural phenomena at greater accuracy, resulting in an explosive growth of data. However, current data handling and visualization capacities still seem orders of magnitude too small for scientists to interpret the voluminous and complex data they are capable of producing routinely. This dissertation presents our efforts on this topic. First, we propose a visualization system model based on large-format display technology and so called Client-Commware-Server structure. The large-format display system based on clusters and projectors , which is now an area of active research, can not only provides high-resolution displays but also is suitable for parallel processing. Compared with the traditional Client-Server structure which is widely used in scientific visualization systems, our Client-Commware-Server structure decreases the connection between the server for computing and the client for visualization and makes the whole system more independent and flexible, which brings great convenience for system maintenance, expansion and reuse. We have accomplished two visualization systems: PRIS-Explorer (a postprocessing system for reservoir simulation) and SMSP(Scalable Materials Simulation Package). They are not only the implementations of the model we give above, but also meaningful for developing the practical software with our own copyrights. The key technologies for developing PRIS-Explorer are how to handle the large-scale data set produced by parallel programs and the implementation of the Object-Oriented technology. For SMSP, the main difficulty is how to build a Molecule-Building System based on OpenGL. Data storage,compression,transmission and processing are the key elements in large-scale visualization and FFT is one of the most important algorithms to handle these. In fact,FFT is one of the top 10 algorithms in the last century, and it plays an important role in lots of areas. But it can only be used in tensor-product domains, and how to generalize the approach into high dimensions, beyond box domain, is always an open problem. In this dissertation we propose a set of fast algorithms for computing the DGFT (Discrete Generalized Fourier Transforms) over the hexagon domains and the parallel dodecahedron domains and give the parallel implementation on Linux clusters.We call this set of fast algorithms over 2-dimension with 3-directions, 3-dimension with 4-directions, and generally m-dimension with m+1-directions domains HFFT(High-Dimension Fast Fourier Transformations). HFFT is a typical data-dense computation, and the communications are dominant during the parallel processing, which makes the efforts on how to reduce the data communication the key element to obtain high performance. By giving a specific recursive data structure we given and making full use of the parallelity of HFFT, we propose a parallel HFFT algorithm on distributed memory computers. The experiments on a Linux cluster up to 128 CPUS show that our algorithm has good parallel performance. The main contributions of this dissertation are In chapter 2, we propose a scientific visualization system modal which is based on large-format display technology and Client-Commware-Server structure. In chapter 3 and chapter 4, we accomplish two large-scale scientific visualization systems. In chapter 5 and chapter 6, we propose HFFT on hexagon and parallel dodec ahedron domains, and reduce the computational complexity from O(N4) and 0{N6} to O(N~4) and O(N~6) to O(N~2 log N) and O(N~3 log N). Lastly, we propose a parallel HFFT on distributed memory computers.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/5830
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW013919.pdf(1563KB)----限制开放-- 联系获取全文

Recommended Citation:
姚继锋. 科学计算可视化系统及非张量积区域HFFT算法[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2004-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[姚继锋]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[姚继锋]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace