基于重排序变换和循环分布的通信优化算法

针对现有通信优化算法无法使MPI自动并行化编译器生成加速比理想的消息传递程序问题,提出了一种基于重排序变换和循环分布的通信优化算法。该算法根据给出的过程间副作用集合和基于mpi_wait/mpi_irecv移动的重排序变换规则,有序地采用重排序变换和循环分布,尽可能安全地扩大点到点非阻塞通信中通信与计算的重叠窗口,使MPI自动并行化编译器生成具有更多计算重叠通信的消息传递代码。实验结果表明,该算法能够隐藏更多的点到点非阻塞通信开销,并且明显提升消息传递程序的加速比。     

基于MPSoC平台小波变换并行算法研究

快速小波变换是数字信号处理面临的一个重要问题,针对并行小波算法展开研究,缩减小波变换中卷积运算的规模,提高小波变换过程中的并行效能,以实现小波变换的快速并行计算。通过FFT矩阵代入计算,消去了并行计算过程中的同步通信,降低了乘法运算次数。对算法思想进行了理论分析,说明新算法在短小数据分段情况下能够减少50%~75%的乘法操作;通过搭建两种不同平台进行了对比测试,证明了算法的先进性与有效性。基于FFT矩阵的并行小波变换算法是一种稳定有效的经典小波并行算法。     

多核与众核上MNF并行算法与性能优化

高光谱遥感影像降维最大噪声分数变换(maximum noise fraction rotation,简称MNF rotation)方法运算量大,耗时长.基于多核CPU与众核MIC(many integrated cores)平台,研究MNF算法的并行方案和性能优化.通过热点分析,针对滤波、协方差矩阵运算和MNF变换等热点,提出相应并行方案和多种优化策略,量化分析优化效果,设计MKL(math kernel library)库函数实现方案并测评其性能;设计并实现基于多核CPU的C-MNF和基于CPU/MIC的M-MNF并行算法.实验结果显示,C-MNF算法在多核CPU取得的加速比为58.9~106.4,而基于CPU/MIC异构系统的M-MNF算法性能最好,加速比最高可达137倍.     

自动寻找使多重串行循环并行化的幺模变换

对于已知n维距离向量矩阵的多重串行循环,过去的并行化编译研究还缺乏寻找使循环外层并行化的幺模矩阵的可行算法.文章介绍了多重串行循环并行化的幺模变换方法,不仅从理论上证明满足外层并行化要求的合法幺模矩阵是存在的,而且通过构造性证明给出一个计算外层并行化幺模变换矩阵的可行算法,并探讨了扩大其适用范围于非完全嵌套和非常数相关距离循环的有效途径.     

基于线性表出的非奇异循环变换局部性优化方法

开发程序的局部性是当今并行编译优化研究的重点之一，而程序变换是开发程序时间局部性和空间局部性的重要手段之一．该文提出了一种新的利用非奇异循环变换来优化程序局部性的局部性优化方法，即基于线性表出的循环变换．该方法利用一组最少的线性无关向量组来线性表出数组访问的下标表达式，并据此构造非奇异变换矩阵来优化数组访问的时间局部性和空间局部性．该方法能充分开发数组访问的时间局部性，能简便地确定是否能对数组访问进行时间局部性或空间局部性优化，并能对给定的嵌套循环同时进行时间局部性和空间局部性优化．实验结果表明了该文所提出的基于线性表出的非奇异循环变换局部性优化方法是有效的．     

基于深度卷积神经网络的变换域通信网络抗干扰优化算法

为了有效抑制变换域通信网络干扰信号,改善信噪比,研究了基于深度卷积神经网络的变换域通信网络抗干扰优化算法。应用傅里叶变换方法将信号从时域转换到频域,并以傅里叶变换通信信号获得的参数为依据构建干扰信号模型;嵌入干扰信号模型以形成接收信号,然后对接收信号进行处理并存储在干扰数据库中,利用深度卷积神经网络完成干扰信号的特征学习与干扰估计,并根据干扰估计结果,在接收信号中去除干扰信号,完成变换域通信网络抗干扰优化。实验结果表明：该算法可有效完成变换域通信网络抗干扰优化,优化后通信信号的信噪比改善性能与误码性能均较佳,输出的通信信号几乎无干扰信号存在。     

二维宏观拟颗粒并行模拟程序通信性能优化策略

随着粒子模拟并行计算在相关领域应用的不断深入和并行节点计算能力的不断增强,粒子模拟并行程序中通信耗时对整体性能的影响越来越显著,甚至成为主要性能瓶颈.本文在分析影响并行程序通信性能多种因素的基础上,从进程划分方式选择、通信协议优化的角度,对1个典型粒子模拟并行程序——二维宏观拟颗粒并行模拟程序在千兆以太网环境下的通信性能的优化策略进行了测试研究,通过改进并行进程划分方式,采用用户级通信协议等方法,使测试程序通信性能获得明显提高,进而提出了粒子模拟并行程序通信性能优化的思路和建议.     

高性能二维9/7离散小波变换VLSI结构

为了降低二维小波变换中的存储消耗并同时提高电路处理速度,提出了一种二维并行的VLSI结构。通过充分挖掘二维变换中行变换和列变换之间的关系,优化了行变换核和列变换核的并行数据扫描输入方式,将9/7小波变换的中间存储降低至4N。同时,采用基于翻转格式的流水线技术,将电路的关键路径缩短至一级乘法器延时,有效地提高了电路处理速度,并通过伸缩电路合并的优化方法将乘法器个数降低至10个,从而有效地减少了硬件资源消耗。     

基于多核的Rijndael算法的并行优化与实现

为提高Rijndael算法的执行效率,从对Rijndael算法的核心部分-轮变换的分析入手,在多核平台下提出了一种基于数据流分解的方式对Rijndael算法进行并行优化.采用的主要方法是将轮变换的各构成变换对整个状态的作用分割成对状态的每个组成单元的作用,使得各构成变换可以并行进行.实验结果表明,采用基于数据流的分解方式对Rijndael算法分解可有效的提高其执行效率.     

多核处理平台上任务图模型的并行调度策略研究

凭借着高性能,低功耗的特性,多核处理器已经占据了目前的主要市场.提出一种多核处理平台上基于任务图模型的调度策略.建立了多核平台上任务图的空间与时间并行调度模型;针对任务图的空间并行与时间并行调度模型提出了并行节点合并、分配的优化算法与流水线并行的优化算法.最后,提出将优化的空间与时间并行调度技术相结合的并行调度策略.通过实验验证,本文提出的算法比其他多核并行调度算法降低了处理器核心间的通信与同步开销,提高了系统的计算效率与吞吐量.     

CBS型矩阵转换的并行算法设计与分析

本文对ＣＢＳ图像重建原理中矩阵转换问题的并行算法进行了设计和分析，讨论了在不同的设计方法下的并行算法时间复杂度和通信开销，并在曙光一号并行机上实现了它的多线程并行算法，测试了它的加速比和并行效率。     

A method of program transformation between variable sharing and message passing

There have been proposed and used many programming concepts for realizing interprocess communication and synchronization, and two fundamental categories among them are variable sharing (e.g. semaphores) and message passing (signals, input/output in CSP and redezvous in Ada). The aim of this paper is to investigate the relationship between these two mechanisms, and in particular, program transformation between them. We here propose a transformation method between parallel programs written in each of these two, which uses transformation schemes named monitor transformations. We exhibit the method by showing through a chain of program transformations the equivalence of two versions of a parallel algorithm called dynamic sorting array.     

一种面向大规模并发的Gatherv优化方法

MPI不规则集合通信Gatherv为描述并行通信行为提供了极大的灵活性，但其不规则特性带来了较高的实现难度。现有方法存在通信热点突出、内存开销大和访存效率低等问题，难以满足当今大规模并行应用的性能需求。提出一种面向大规模并发的Gatherv优化方法，从优化等级、缓冲区管理等多个关键问题入手，将规则集合通信实现中常用的Binomial-Tree结构用于实现Gatherv，并提出消息链调度机制，进一步降低开销，提升优化效果。测试结果表明，该方法可以有效解决现有方法存在的性能问题，实现Gatherv集合通信性能在大规模并发条件下的高效可扩展。     

MPI并行调试与优化策略在三维绕流气体运动 论数值模拟中的应用

从求解三维绕流问题的Boltzmann模型方程的数值模拟程序出发,通过研究区域分解并行计算策略,引入输入/输出、通信与CACHE等优化策略,对数值模拟程序进行MPI并行化移植与高性能计算调试。以高空稀薄过渡流区飞行器绕流状态为算例,进行了MPI大规模并行计算测试,证实了所发展的MPI并行化区域分解策略及程序优化途径的正确性。研究表明开展的并行化实现能明显地缩短模式计算时间,并取得较好的效果。     

Communication Optimizations for Parallel C Programs

This paper presents algorithms for reducing the communication overhead for parallel C programs that use dynamically allocated data structures. The framework consists of an analysis phase called possible-placement analysis, and a transformation phase called communication selection. The fundamental idea of possible-placement analysis is to find all possible points for insertion of remote memory operations. Remote reads are propagated upwards, whereas remote writes are propagated downwards. Based on the results of the possible-placement analysis, the communication selection transformation selects the “best” place for inserting the communication and determines if pipelining or blocking of communication should be performed. The framework has been implemented in the EARTH-McCAT optimizing C compiler, and experimental results are presented for five pointer-intensive benchmarks running on the EARTH-MANNA distributed-memory parallel processor. These experiments show that the communication optimization can provide performance improvements of up to 16% over the unoptimized benchmarks.     

透视和透视投影变换 --论图形变换和投影的若干问题之三

讨论了透视变换的基本原理．由于与画面成一角度的平行线簇经透视变换后交于灭点，因此可采用两种不同的方法来获得透视图：一是保持画面铅垂，通过旋转物体使之与画面构成角度达到透视变换效果，得到了三种最佳透视变换矩阵；二是通过倾斜投影画面达到透视变换效果，给出了通过倾斜画面得到三灭点透视图的齐次透视变换矩阵．两种方法的灭点都是可预先控制(即可先决定灭点再决定变换矩阵)的，比较彻底地解决了透视变换矩阵元素的产生方法．给出了“对一个空间物体，一定存在另一个空间物体，使前者在画面上的透视投影与后者的平行投影是一样的，且保留了深度方向的对应关系”的证明．这个性质可使复杂的透视投影转化成简单的平行投影，使得立体图形的处理大为简化．     

PARALLELISING COMPILERS AND SYSTEMS

In recent years, high performance computing underwent a deep transformation. In this paper, we review the state of parallel computation with detailed discussion of the current and future research issues in the area of parallel architectures and compilation methods, instruction level parallelism and optimization methods to improve the performance of the memory hierarchy.     

遥感像片中多投影变换的实现与优化

为了更好地进行遥感图像的投影变换，在对传统的投影变换方法进行比较研究的基础上，给出了优化方法，首先阐述了地图投影和投影变换的基本原理。其后分析了进行栅格图像的投影变换的必要性和不同于矢量变换的不同特征，并重点介绍了图像投影变换的算法以及优化方法；最后，采用Visual C 作为软件平台，开发了遥感图像投影变换的模块。     

移动音频带宽扩展算法计算复杂度优化

移动通信设备由于计算资源有限,对计算复杂度较为敏感。我国自主研发提出的移动音频编解码算法标准AVS P10中的带宽扩展算法有利于提高移动音频编解码质量,但其计算复杂度较高,不利于该编解码算法在移动环境中应用。通过分析该带宽扩展算法的流程,发现其计算复杂度较高的主要原因是时频变换次数过多,为此从算法和代码两个方面对该算法进行优化:算法方面通过减少快速傅里叶变换(FFT)次数来降低算法计算复杂度;而代码方面则通过空间换时间等方法来减少算法消耗时间。测试结果表明,在不降低整体音频编解码主观质量的情况下,带宽扩展模块在编码端和解码端运行时间比例分别降低了4.5和14.3个百分点,算法计算复杂度显著降低,这有利于进一步在移动音频领域推广应用该编解码算法。