快速算法与并行计算
实际问题大多需要庞大的计算资源支持，快速算法与并行计算是解决这一瓶颈、实现高效处理的关键技术之一。鉴于此，本中心运用二分演化思想和复制、变异、反 演技术，深入剖析Walsh、斜Haar类变换、分形、小波等现代数学方法的本质特征和内在联系，探索高性能计算中普适的演化规律，开展快速算法与并行计 算理论研究，形成了一套特色鲜明的思想体系和建模方法，研制出了高效算法相应的计算机程序。
① Walsh变换的演化生成及其快速算法设计
♦ 从对称性出发，运用二分演化思想，基于行复制和块复制技术以及反演技术，系统地研究了6种基本排序方式的Walsh变换的演化生成及其快速算法，即 Paley序、反Paley序（Hadamard序）、Walsh序、逆Walsh序（M序或X序）、反Walsh序、类Hadamard序，完善了已有 的Walsh变换的研究工作。6种排序方式相反相成，是两种对称性：平移对称和奇偶对称的不同体现，其中前四种序是文献中常见的排序方式，而反Walsh 序和类Hadamard序为文献中尚未开发的两种序。反Walsh序与逆Walsh序的矩阵互为转置，不是对称矩阵；类Hadamard序矩阵具有良好的 奇偶对称性，其快速算法可与Hadamard序算法媲美，具有潜在的应用前景。
♦ 将类Hadamard序Walsh变换推广到多值情形，研究了类Hadamard序（简称G序）广义Walsh变换的构造生成和快速算法。通过维纳滤波实 验比较G序广义Walsh变换和其它几种正交变换的性能，得出其性能和广义Hadamard变换一致的结论。相比后者，G序广义Walsh变换的对称性使 其在硬件实现时更具优势。
♦ 高维Walsh变换的快速算法设计
以一维Walsh变换算法为基础，利用块分裂的方法和嵌套思想设计了一种实用、高效的高维Walsh变换的快速算法，并将该算法推广于FFT、DCT 以及Haar变换、斜变换等正弦、非正弦类变换的高维算法设计。研究结果表明，该算法性能显著优于行列算法：数组访问次数减少一半以上，计算时间提高数 倍。图1给出了部分算法流程。
图1 快速Walsh变换的蝶形图
② 其它非正弦类变换研究
推广了Haar变换的塔式算法，提出了一类伸缩比为2的Walsh-Haar变换（简称Haar类变换）的快速算法；进一步，讨论了一般Haar类变换的 递归演化生成，并设计了相应的“塔式”算法。分析了Haar类变换、斜Haar类变换与小波的关系，构造了基于Haar类变换、斜Haar类变换的多进制 Haar小波和多进制斜Haar小波变换。将本中心提出的参数斜变换的思想应用于斜Haar类变换，导出了带参数的斜Haar类变换，设计了相应的多进制 多小波变换。结合形态小波，给出了基于Haar变换和斜变换的形态小波变换。这些变换不仅生成方便、选择灵活，而且具有快速算法。
③ 分形曲线的演化生成与高效算法研究
本中心发现Walsh变换和分形在演化机理上具有天然联系（见图2），基于此认识，我们绘制了各种序的Walsh方阵的计算机图像，发现它们具有分形意义 上的自相似结构。同时，我们以空间填充曲线SFC为对象，运用二分演化技术，研究分形的演化机制，提出了一种新的SFC生成算法。该算法应用“复制”的思 想，通过“形－数”转换，将具有“形”特征的曲线问题转化为具有“数”特征的矩阵问题。实验结果表明，该算法比现有基于递归思想和几何途径经典的L系统算 法提高了将近1倍的速度，该算法为并行计算大型空间填充曲线提出了一种有效方案。进一步，借鉴Walsh变换的“复制”思想，基于Hilbert矩阵的复 制过程，提出了Hilbert序的一种新的编码、解码方案，首次给出了三角域上的Hilbert曲线的编码、解码算法（见图3），该算法的时间复杂性、空 间复杂性较小，均优于以往文献中最快的算法-Liu算法。此外，基于演化的思想，提出了Peano曲线的一种非递归的生成算法。该算法既保持了文献中通常 采用的递归生成算法简单、清晰、易实现等优点，又克服了递归算法占用内存大、效率低的不足，而且其思想和方法可以推广到其它SFC，同时，我们还开发了 SFC生成与分析的软件包，为进一步研究SFC提供了试验平台。
图2 Walsh函数的分形演化
图3 三角域上的n阶Hilbert曲线
④ 生物信息学中的快速算法研究
为探索快速算法在生命科学中的应用，对生物信息学中的序列分析方法进行了初步研究，设计了生物多序列比对的并行算法和程序，改进了生物序列分析中系统进化 树的NJ算法，显著提高了计算速度。此外，本中心探讨了Walsh变换在元胞自动机CA行为和构象分析中的应用，将复制思想用于CDMA扩频序列的设计， 提出了一种构造周期完全互补码的新方法和一类统一的零(低)相关序列构造方法，该构造方法简单灵活，具有较强的工程应用价值。
⑤ 并行算法设计与实现
针对以上快速算法本身具有并行性的特点及计算流体力学、图像与信号处理等对庞大计算资源的需求，中心成员长期致力于并行计算机、并行算法和并行程序设计等 方面的教学、研究和推广工作。以当代可扩放并行计算机系统结构为主题，探索了对称多处理机、大规模并行处理机、机群系统和分布共享存储多处理机系统的组成 原理、结构特性、设计方法，并引入二分演化技术，研究了计算机科学中诸多常用的数值和非数值计算问题的并行算法设计及其分析方法，逐渐形成了并行算法“理 论—设计—实现—应用”一套完整的学科体系，提出了并行计算“结构—算法—编程”一体化的研究方法；同时，利用当今最先进的编程环境MPI、 OPENMP、CUDA ，在“深腾1800”机群（24个计算节点）、GPU个人高性能计算机上实现了主要算法的分布式并行计算，研制出了相应的软件；此外，还借助于Intel 编译器、VTune Analyzer 和Cluster Trace Analyzer & Collector 等软件分析、优化工具，对程序进行优化和效率分析，取得了大量有益的新成果。
⑥基于CUDA 的格子Boltzmann 方法：算法设计与程序优化
近年来，利用图形处理单元(graphic processing unit，GPU，如图4所示)进行通用计算得到广泛关注。Nvidia公司自2007年以来推出的GPU并行计算开发环境CUDA（Compute Unified Device Architecture，如图5所示）则将GPU计算推向了一个前所未有的高度。与此同时，近年来发展起来的格子Boltzmann (LB)方法由于其具有计算简单，天然并行，易于程序实现，易于处理复杂边界等优点逐渐成为流体建模和模拟的一种重要手段。LB方法所具这些优点使得它非 常适合利用GPU进行大规模流体计算，使之成为通用大规模GPU流体计算平台可能的、非常理想的计算方法之一。鉴于此，本中心成员以模拟二维方腔流、二维 圆柱绕流以及三维方腔流为例，从简单到复杂、从二维到三维、分别基于一般的DdQq和iDdQq模型自主开发了相应的CUDA环境下的LB模拟程序，着重 探讨了存储器访问优化等手段在程序设计中的应用，并对程序的一系列性能指标进行了详细分析。研究表明，不论是那种算例，基于CUDA的LB方法都取得了非 常理想的效果。 以二维方腔流为例，在Intel CPU Xeon 5520 + NVIDIA Tesla C1060环境下可以得到1200百万格子更新率/秒的计算速度，180倍以上的加速比，这一结果是目前国内外文献中最好的。研究结果不但进一步证实了 GPU与LB作为大规模并行计算硬件和软件的良好匹配关系，更为建设基于LB方法通用大规模GPU并行流体计算平台提供了重要参考。其中ID2Q9模型的 加速比如表1所示，所模拟的三维方腔流立体图如图6所示。
表1：iD2Q9模型在CPU和GPU上的运行时间（运行10000步）
图4: GPU计算显卡
图5: CUDA的线程层次结构
图6：GPU计算三维方腔流的整体效果图
