划分点定位并行排序算法

提出并分析了划分点定位并行排序 ( parallel sorting by divide- point locating)算法 .在算法中 ,输入数据被平均划分并分配给所有处理机 ,因而每个处理机具有相同的工作负载 .给出了网络分布计算环境下 PSDL算法的实验结果 ,并与 PSRS算法进行了对比 .理论分析和实验结果表明 ,PSDL算法是一种高效率。

一类新的并行排序算法(英文)

提出了两种新的并行排序算法,在第一部分设计了一种有效的异步并行算法,可应用于多指令和多数据流计算机,且提供了该算法的最小和最大的运算时间.第二部分给出了一种新的并行排序网络,对于n个元素的排序序列,可以使用n(n-1) 2个比较元素和n(n-1) 2个反转换元素及n个转换元素能达到常数数量级的运行时间进行快速排序,同时给出了以{0,1}元素组成的序列的排序过程.

并行排序蚁群算法规划仓库AGV路径研究

针对智能仓库中的AGV路径规划问题,提出了一种基于并行排序蚁群算法的路径规划方法,该方法通过多个子蚁群之间较优蚂蚁释放的信息素交互,提高蚁群整体的搜索能力。建立以路径最短和AGV转弯次数最少为优化目标的多目标函数模型,用并行排序蚁群算法求解,再对生成的初始路径通过减少中间节点的方式进行平滑处理。在MATLAB上进行多次仿真,对比实验结果表明,该算法在进行仓库AGV路径规划时收敛速度更快,稳定性更好,且平滑处理后的路径更优。

用于分组和集函数计算的并行排序方法

本文考虑在并行数据库系统中基于归并排序的分组操作和集函数计算。为消除结点间数据分布倾斜对并行排序效果的影响，采用静态或动态数据平衡方法。通过实验模拟，比较了采用不平衡方法。

最优并行排序算法

本文考虑在P台机上对n元序列的排序算法。[2]给出了一种效率O(1)的算法(除串行算法外,它是最优的),需O(log n)台处理机和O(n)步。本文给出了一种效率O(1)的并行排序算法,需O(n^(1/2))台处理机和O(n^(1/2)logn)个并行步,显著地改进了[2]的结果。

一种新的并行排序算法研究

讨论了一种新的并行排序算法．基于前馈阈值神经网络结构，该排序模型利用Ｏ（ｍｎ￣２）个神经元经６个时间步（６级前馈）即可完成排序。

基于三维时空状态图-并行排序蚁群算法的多机器人路径协同规划

为了得到多机器人系统在无碰撞前提下的较优路径,设计了分层协同规划系统。该系统包括3个子模块,分别为全局最优路径规划模块、碰撞检测模块和避撞模块。在全局路径规划方面,在蚁群算法中加入了多子群并行搜索策略和基于信息素的子群经验交流策略,提出了基于并行排序蚁群算法的路径规划方法。在碰撞检测方面,提出了三维时空状态图的概念,基于机器人路径栅格在三维时空状态图的分布给出了碰撞检测结果。在避撞方面,建立了避撞的博弈论模型,基于博弈论得到了集体代价最小的避撞策略。在30 m×30 m的复杂栅格环境中验证,并行排序蚁群算法规划路径的目标函数平均值比传统蚁群算法减小了5.25%,比改进蚁群算法减小了3.66%,验证了并行排序蚁群算法在全局路径规划中的优越性。在20 m×20 m栅格环境中利用4个机器人进行避撞策略检测,从结果可以看出,基于博弈论的避撞策略可以有效避免机器人间的碰撞,实现机器人的安全行驶。

线性阵列上的一种新的并行排序算法

首先介绍了分治方式的并行处理方法,并以超立方网络上的并行排序为例说明了这种方法的应用.然后在此基础上,给出了作者在线性阵列上发现的一种新的并行排序算法.

三个并行排序算法的可扩充性分析

可扩充性分析是评价并行算法或并行系统性能的重要工作，特别是在大规模并行处理环境下更是如此。本文利用新近提出的扩张串行分量分析技术，研究了三个并行排序算法的可扩充性，以及这些算法在超立方体结构上的实现的可扩充性。给出了使三种算法都为可扩充的条件，解释了每个算法的适用范围。展示了算法的实质性质，计算了它们的扩张串行分量、扩张效率以及扩张加速比。本文的解析分析结果与其它文献中的实验结果一致。

线性递归并行排序算法

应用左递归二叉树构造一个新的并行排序算法，对ｐ个有序块进行排序．从而，将ｎ元素的分类问题转化为对ｐ个有序块的并行排序问题．算法在最坏情况下并行步为Ｏ（（ｎ／ｐ）ｌｏｇｎ／ｐ），是目前比较好的排序算法．

SIM-DEREW模型上的最优并行排序算法

给出两种在 SIMD EREW计算模型上的最优并行排序算法 .为了避免存储访问冲突 ,算法采用了基于并行归并的并行排序方法 .对于长度为 n的序列 ,在 nε 个处理单元上 ,算法的排序时间为O( n1-εlb n) ,成本为 O( n lb n) ,已达到了最优 。

修正枢轴选取的并行排序

本文利用修正枢轴选取，给出一种适合所有基本排序算法的并行化方法，对均匀数据模型排序具有理想的并行加速及效率．

采用折叠-展开技术的一种并行排序算法

给出ｎ×ｎ网孔环接式阵列处理机上的一种并行排序算法，它将ｎ×ｎ阵列上的数据折叠成ｎ×ｎ／ｋ子阵列，排序后再展开到整个ｎ×ｎ阵列上，实现ｎ×ｎ项数据的行主序排序，其平均时间复杂度为（２＋１／ｋ）ｎ＋ｏ（ｎ）．若采用ｎ×ｎ／ｋ阵列模型，且各处理器初始、结束状态允许有ｋ项数据时，该算法的平均时间复杂度只有（１＋２／ｋ）ｎ＋ｏ（ｎ）．

一种在r台机上的并行排序算法

本文给出一个在ｒ台机上的实用并行排序算法，井行步数不超过Ｔｒ＝Ｏ（（ｎ／ｒ）ｌｏｇ２ｒ·ｌｏｇ２ｎ），１≤ｒ≤ｎ。

一种新型膜计算方法在并行排序中的应用

膜计算作为一种新型的分布式、并行计算理论,是目前计算机科学、数学、生物学和人工智能等多学科交叉的研究热点.本文应用基本膜计算理论并结合泼水算法,提出了一种新型生物催化的膜计算方法解决并行排序问题,该方法充分利用了膜计算最大并行执行的特点,最后通过实例以验证该方法的可行性.

一种适用于多处理机系统的并行排序方法DCPM

本文给出一种适用于多处理器系统的并行排序方法——PCPM(Divide Conquer Parallel Merge)。证明了该方法的正确性;算出了它的时间复杂度为0(n^(1/2) log n^(1/2) log√n);最后,简单地说明了本方法的特点。

THSORT:单机并行排序算法

排序是计算机事务处理的重要操作之一.前人已经就内部排序、外部排序和并行排序提出各种方法.从一种全新的视角研究了排序算法,提出一种在单机上实现的并行排序算法THSORT(Tsinghua SORT).它用多个进程分别控制不同的硬件部件,使输入、排序和输出能够同时进行,从而大大提高了硬件部件的并行性和运行效率.在带有双磁盘阵列的硬件平台上进行的测试表明,THSORT的性能达到了NTSORT(new technology SORT)的1倍左右,并成为2002年PennySort(Daytona类)世界排序纪录的保持者.

布尔表达式的化简与并行排序网络验证

为设计出能够验证并行排序网络正确性的有效工具,根据[0,1]原理和布尔函数的特点和性质,提出一种布尔表达式的化简算法,并根据此算法设计出验证工具。对[0,1]原理和布尔函数的特点和性质进行了讨论,指出有利于化简操作的性质。设计出的工具能够根据并行排序网络的参数显示网络图形、自动生成布尔表达式并实现化简验证,工具的输出有利于对排序网络的分析,也可以用于辅助排序网络的设计和优化。实验结果表明了该工具的有效性。

适合多处理机MPSCU的并行排序算法

本文给出了一个适合多处理机MPSCU的并行排序算法。它用k个处理机能在O((N/k)log_2N/k+N)时间内完成N点排序。

基于SIMD——SM模型的并行排序算法设计

文章介绍了并行排序算法的设计,仅是从检测和开拓现有串行算法中的固有并行性而直接将其并行化入手,基于SIMD-SM模型(如图1),没有涉及共享存储器的互斥操作.对插入排序中直接排序、二分法插入排序、树形选择排序进行了研究.