Skip to content

Highly parallel, GPU-accelerated hybrid mergesort with mmap'd IO

License

Notifications You must be signed in to change notification settings

epixoip/cudaMergeSort

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

19 Commits
 
 
 
 
 
 

Repository files navigation

cudaMergeSort

cudaMergeSort is a highly parallel hybrid mergesort for sorting large files of arbitrary ASCII text (such as password cracking wordlists.) It is intended to be a fast replacement for sort(1) for large files. A parallel radix sort is performed on each chunk of the input file on GPU (complements of Thrust), while each chunk is merged in parallel on the host CPU. Only unique lines are merged, and cudaMergeSort is therefore directly analogous to performing sort -u on an ASCII text file.

Performance depends on a number of factors, including CPU, GPU, and HDD/SSD. cudaMergeSort can sort approximately 675M lines per second on the GTX 1080, and around 205M lines per second on the Quadro P3200. However, because merging is branch-heavy and IO-intensive, the merging process takes considerably longer than sorting. Even so, cudaMergeSort can be many times faster than sort(1).

cudaMergeSort vs GNU Sort - 134MB file, 1.4M lines

Xeon E-2176M, 32GB DDR4, Quadro P3200, Samsung 960 PRO NVMe
14.3x speed-up vs. multi-thread sort
epixoip@precision:~$ time ./cudaMergeSort rockyou.txt

Device #0: Quadro P3200, 1517/6070 MB allocatable, 1240 MHz

Input file 'rockyou.txt' is 139921497 bytes
Decreased device buffer to 139923456 bytes

Device #0: Initializing host buffer
Device #0: Initialized host buffer with 14344391 lines in 1.27 seconds (11293838.43 lines/sec)
Device #0: Initialized device buffer in 84.12 ms
Device #0: Sorted 14344391 lines in 69.73 ms (205M lines/sec), Runtime 176.63 ms
Device #0: Wrote 139921497 bytes in 0.29 seconds (456.21 MB/sec)

Sorting completed in 1.77 seconds

No chunks need merging.

Sorted file saved to 'rockyou.txt.sorted'

real  0m1.817s
user  0m1.484s
sys   0m0.333s
epixoip@precision:~$ time sort -u rockyou.txt >rockyou.txt.sorted_gnu

real  0m26.088s
user  0m43.608s
sys   0m0.497s

cudaMergeSort vs GNU Sort - 9.25GB file, 266M lines

2x Xeon E5-2620 v4, 32GB DDR4, 2x GTX 1080, Samsung 850 PRO SATA3
3.96x speed-up vs. multi-thread sort
epixoip@QA-Lab4:~$ time ./cudaMergeSort test.txt

Device #0: GeForce GTX 1080, 2029/8119 MB allocatable, 1733 MHz
Device #1: GeForce GTX 1080, 2029/8119 MB allocatable, 1733 MHz

Input file 'test.txt' is 9932976481 bytes

Device #0: Initializing host buffer
Device #1: Initializing host buffer
Device #1: Initialized host buffer with 57155288 lines in 7.36 seconds (7764520.57 lines/sec)
Device #0: Initialized host buffer with 57153375 lines in 7.39 seconds (7738116.22 lines/sec)
Device #1: Initialized device buffer in 964.43 ms
Device #1: Sorted 57155288 lines in 84.62 ms (675M lines/sec), Runtime 1098.72 ms
Device #0: Initialized device buffer in 1558.36 ms
Device #0: Sorted 57153375 lines in 84.55 ms (675M lines/sec), Runtime 1691.55 ms
Device #1: Wrote 2128494582 bytes in 5.11 seconds (397.31 MB/sec)
Device #0: Wrote 2128494612 bytes in 4.79 seconds (423.88 MB/sec)
Device #0: Initializing host buffer
Device #1: Initializing host buffer
Device #0: Initialized host buffer with 57156029 lines in 7.51 seconds (7606993.95 lines/sec)
Device #1: Initialized host buffer with 57154635 lines in 7.53 seconds (7594079.49 lines/sec)
Device #0: Initialized device buffer in 1321.12 ms
Device #1: Initialized device buffer in 1320.46 ms
Device #0: Sorted 57156029 lines in 84.33 ms (677M lines/sec), Runtime 1458.82 ms
Device #1: Sorted 57154635 lines in 84.37 ms (677M lines/sec), Runtime 1455.69 ms
Device #1: Wrote 2128494584 bytes in 5.30 seconds (382.82 MB/sec)
Device #0: Wrote 2128494611 bytes in 5.45 seconds (371.96 MB/sec)
Device #0: Initializing host buffer
Device #0: Initialized host buffer with 38104066 lines in 5.03 seconds (7578078.40 lines/sec)
Device #0: Initialized device buffer in 446.02 ms
Device #0: Sorted 38104066 lines in 62.46 ms (610M lines/sec), Runtime 542.82 ms
Device #0: Wrote 1418998091 bytes in 2.42 seconds (558.64 MB/sec)

Sorting completed in 37.13 seconds

Merging 5 chunks in 3 passes...
Merge pass #1 completed in 23.15 seconds
Merge pass #2 completed in 43.76 seconds
Merge pass #3 completed in 50.28 seconds

Merging complete. Sorted file saved to 'test.txt.sorted'

real   2m35.767s
user   2m35.296s
sys    0m35.408s
epixoip@QA-Lab4:~$ time sort -u test.txt >test.txt.sorted_gnu

real   10m17.079s
user   25m48.252s
sys    0m25.784s

About

Highly parallel, GPU-accelerated hybrid mergesort with mmap'd IO

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages