基于GPU的并行排序算法的性能评估
Mohammed Alaa Ala'anzy1, Nurdaulet Tolendi1, Baizhan Baubek1
1Department of Computer Science, SDU University, Kaskelen, Kazakhstan.
PloS one
|February 3, 2026
概括
GPU加速显著加快了排序算法,如Radix,Quick和Merge Sort,在大型数据集中实现了超过100倍的加快速度. 这项研究表明,与顺序方法相比,性能有了显著的提高.
科学领域:
- 计算机科学 计算机科学
- 高性能计算 高性能计算
背景情况:
- 顺序排序方法在处理大数据集时遇到困难.
- 并行排序和GPU计算提供了显著的加速潜力.
研究的目的:
- 调查基于GPU的并行处理的合并排序,快速排序,泡排序, radix top-k选择排序和使用CUDA的慢排序.
- 在现代GPU上评估性能,并行时间复杂性和空间复杂性.
主要方法:
- 使用CUDA实现并优化了基于GPU的并行分类算法 (MS,QS,BS,RS,SS).
- 在各种数据集 (随机,反排序,排序,近排序) 上进行实验.
- 将GPU加速版本与顺序对应版本进行比较.
主要成果:
- 在1000万个随机元素上,Radix Sort实现了~50倍的加快速度,快速排序~97倍,并购排序~103倍.
- 泡泡排序显示了~17倍的改善,但整体仍然较慢.
- 慢排序演示了~18.6倍的加快速度.
- 新的单个GPU实现实现了17倍至100倍以上的加速度.
结论:
- 用GPU加速的排序算法比顺序方法提供了相当大的性能改进.
- 现代GPU和CUDA能够显著加速大规模的数据分类任务.
- 雷迪克斯,快速和合并排序显示了最有前途的并行处理加速度.
更多相关视频
09:52Setting Up a Stroke Team Algorithm and Conducting Simulation-based Training in the Emergency Department - A Practical Guide
Published on: January 15, 2017
17.9K
09:01A Method for Investigating Age-related Differences in the Functional Connectivity of Cognitive Control Networks Associated with Dimensional Change Card Sort Performance
Published on: May 7, 2014
10.6K
相关概念视频
Parallel Resonance
563
The parallel RLC circuit is an arrangement where the resistor (R), inductor (L), and capacitor (C) are all connected to the same nodes and, as a result, share the same voltage across them. The parallel RLC circuit is analyzed in terms of admittance (Y), which reflects the ease with which current can flow. The admittance is given by:
563
Parallel Processing
730
The brain processes sensory information rapidly due to parallel processing, which involves sending data across multiple neural pathways at the same time. This method allows the brain to manage various sensory qualities, such as shapes, colors, movements, and locations, all concurrently. For instance, when observing a forest landscape, the brain simultaneously processes the movement of leaves, the shapes of trees, the depth between them, and the various shades of green. This enables a quick and...
730
Trial and Error and Algorithm
424
A problem-solving strategy is a plan of action used to find a solution. Different strategies have distinct action plans. Trial and error involves trying different solutions until one works. For instance, to fix a broken printer, you might check ink levels, ensure the paper tray isn't jammed, and verify the printer's connection to your laptop. This method can be time-consuming but is commonly used. Thomas Edison, for example, used trial and error to find a suitable filament for the light...
424
Resistors In Parallel
6.3K
Resistors are in parallel when one end of all the resistors are connected to a continuous wire of negligible resistance and the other end of all the resistors are also connected to one another through a continuous wire of negligible resistance. In the case of a parallel configuration, the potential drop across each resistor is the same. Current through each resistor can be found using Ohm’s law, I = V/R, where the voltage is constant across each resistor. The sum of the individual currents...
6.3K
Series and Parallel Capacitors
9.6K
Capacitors, fundamental components in electronic circuits, can be connected in series and/or parallel configurations. Each configuration has different impacts on the overall behavior of the circuit.
First, consider capacitors connected in series to a battery. In this configuration, the plate connected to the battery's positive terminal develops a positive charge, while the plate attached to the negative terminal becomes negatively charged. An equal magnitude of charge is induced on the...
First, consider capacitors connected in series to a battery. In this configuration, the plate connected to the battery's positive terminal develops a positive charge, while the plate attached to the negative terminal becomes negatively charged. An equal magnitude of charge is induced on the...
9.6K
Parallel-axis Theorem
8.3K
The parallel-axis theorem provides a convenient and quick method of finding the moment of inertia of an object about an axis parallel to the axis passing through its center of mass. Consider a thin rod as an example. There is a striking similarity between the process of finding the moment of inertia of a thin rod about an axis through its middle, where the center of mass lies, and about an axis through its end using the conventional method. In the conventional method, the concept of linear mass...
8.3K
