一个选择算法及其并行化

文中用合并选择的思想及堆上的最佳算法，给出了求解选择问题的一个新算法及其相应的并行化。将串行合并选择算法的复杂度ｎＬｏｇｋ＋Ｏ（ｎ）降低到（ｎＬｏｇｋ）／２＋（ｎＬｏｇＬｏｇｋ）／２＋Ｏ（ｎ），并保持了原并行算法的结构，在ＳＩＭＤ树型机器的并行计算模型上，并行运行时间也有相应的改善，其中ｎ为问题的大小，ｋ为所找元素的序号。

优先队列上的快速并行算法

利用上浮路径、下沉路径的概念，采用二分查找定位技术，提出了堆上并行插入删除的新算法；最坏情况下使得原有并行插入算法的ｌｏｇＮ次加锁操作降低到ｌｏｇｌｏｇＮ＋θ（１）次；原有并行删除算法的２ｌｏｇＮ次加锁操作降低到ｌｏｇＮ＋ｌｏｇｌｏｇＮ＋θ（１）次，其中Ｎ为堆中元素的个数．最大限度地扩展了堆上操作的并行度．

HASH线性探测并行算法

本文设计了一个在P台处理机运行环境下的HASH线性探测并行算法,其并行计算模型为CREW[1];该算法既保持传统串行算法的优点又使速度提高P倍,并且没有聚集问题。

双向堆选择排序并行算法

在a1,a2，……，an中，ai到an-i＋1部分记为A[i：n-i＋1]，在A[i：n-i＋1]上建立小顶堆和大项堆将第i小、第i大的数分别放在第i个位置和第n—i＋1个位置，i=1,2，……，└n/2┘，实现双向堆选择排序，并设计了并行算法，分析了并行算法的复杂度。

多处理器上(m,n)选择问题的一个并行算法

给出求解从任意给定的n个数据中选取m个最小(最大)者即(m,n)选择问题的一个并行算法(m<n).该算法易于在基于共享内存的单指令流多数据流(SIMD)机器上实现,所需处理器数为n/2m,并行时间复杂性在最坏和平均情况下均为O(log(n/2m)logm·m),其并行执行代价为O(n/2log(n/2m)logm).

基于大值堆的自调整粗粒度并行遗传算法模型

一般粗粒度并行遗传算法(CGGA)的性能受诸多因素的影响表现不尽如人意。以降低通信代价为主要目标,受物种金字塔模型的启发,设计了一种双阈值限制下的自调整堆结构,并对其堆调整具体操作进行了改进,以期望改进后算法中种群间的通信代价大幅度降低,优化收敛速度,提高算法效率。通过对遗传算法的几个典型测试函数通信量的分析和实验表明,基于该模型的并行遗传算法在降低通信代价、提高收敛速度、优化最终解方面收效明显。

基于MapReduce模型遗传算法的一种改进与实现

遗传算法的内在隐并行性决定了其能够以少量的问题编码进而处理大量模式,不少处理更大规模且复杂问题的并行遗传算法也提了出来。本文给出了在Hadoop中MapReduce并行计算框架下简单遗传算法的并行化处理流程,结合框架处理输入和输出键值对的特点提出了基于最小堆的最优个体保留策略的遗传算法在的设计与实现,进一步优化了算法的收敛速度。实验结果表明:运用框架的并行处理能力及堆的线性操作时间,应用于较大规模复杂问题该算法实现在收敛速度上呈良好特性。

基于图形处理器的形态学重建系统

形态学重建是医学图像处理中非常基础和重要的操作。它根据掩膜图像的特征对标记图像反复进行膨胀操作,直到标记图像中的像素值不再变化为止。对于传统基于中央处理器(CPU)的形态学重建系统计算效率不高的问题,提出了使用图形处理器(GPU)来加速形态学重建。首先,设计了适合GPU处理的数据结构:并行堆集群;然后,基于并行堆集群,设计和实现了一套基于GPU的形态学重建系统。实验结果表明,相比传统基于CPU的形态学重建系统,基于GPU的形态学重建系统可以获取超过20倍的加速比。基于GPU的形态学重建系统展示了如何把基于复杂数据结构的软件系统高效地移植到GPU上。

多波束测深数据并行滤波算法

针对提高节结合不确定度的水深评估算法执行速度的问题,该文在传统的CUBE滤波算法基础上提出一种适用于多核架构的并行滤波算法。把测深数据滤波分解为构造CUBE网格和估算网格节点水深两个环节,然后针对各环节特点设计对应的并行计算方法。通过两种方法提高滤波速度:一是通过合理的并行策略把计算任务分配到多个处理器核上并行执行;二是引入基于堆结构的排序方法提高数据滤波速度。实验结果表明,所设计算法在四核处理器上运行时,能够将滤波速度提高约2.74倍。