CUDA

CUDA-并行Radix Sort

啥是Radix Sorting

Radix Sorting CPU 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define NUM_ELEM 100
void cpu_sort(int32_t* const data, const int32_t num_elements) {
	static int32_t cpu_tmp_0[NUM_ELEM];
	static int32_t cpu_tmp_1[NUM_ELEM];
    // for every bits of an element
	for (int32_t bit=0; bit<32; bit++) {
		int32_t base_cnt_0 = 0;
		int32_t base_cnt_1 = 0;
        // for every elements
		for (int32_t i=0; i<num_elements; i++){
			const int32_t d = data[i];
			const int32_t bit_mask = (1 << bit);
			if ( (d & bit_mask) > 0 ) {
				cpu_tmp_1[base_cnt_1] = d;
				base_cnt_1++;
			}
			else{
				cpu_tmp_0[base_cnt_0] = d;
				base_cnt_0++;
			}
		}
		// Copy data back to source - first the ZERO list
		for (int32_t i=0; i<base_cnt_0; i++){
			data[i] = cpu_tmp_0[i];
		}
		// Copy data back to source - then the ONE list
		for (int32_t i=0; i<base_cnt_1; i++){
			data[base_cnt_0+i] = cpu_tmp_1[i];
		}
	}
}

上述过程没有办法并行，但是可以将Radix排序作为基本算子，将待处理的数组分成若干段，段与段之间并行执行Radix排序，之后调用Merge，将所有段（每一段都是有序的）并行归于成一段。这就是基本平行排序思路。

有了这个并行思路，对于排序算子，就可以使用任何可行的排序方法了。

先实现CPU的对多个有序数组的Merge操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 合并多个有序的子序列
void merge_arrays(const int* src_array, 
					int* const dest_array,
					const int num_lists, 
					const int num_elements){

	const int num_element_per_list = (num_elements/num_lists);

	int list_indexes[5]; // 分成5段
	for (int l=0; l<num_lists; l++){
		list_indexes[l] = 0;
	}

	for (int i=0; i<num_elements; i++){
		dest_array[i] = find_min(src_array, 
								list_indexes,
								num_lists,
								num_element_per_list);
	}
	return;
}

// 遍历所有段（子序列），找到当前所有段段首的最小值，写入目标数组的对应位置。
int find_min(const int* src_array,
			int* const list_indexes,
			const int num_lists,
			const int num_elements_per_list){
	
	int min_val = INT_MAX;
	int min_idx = 0;
	// Iterate over each of the lists
	for (int i=0; i<num_lists; i++){
	// If the current list has already been emptied
	// then ignore it
		if (list_indexes[i] < num_elements_per_list){
			const int src_idx = list_indexes[i] + num_elements_per_list * i;
			const int data = src_array[src_idx];
			if (data <= min_val){
				min_val = data;
				min_idx = i;
			}
		}
	}
	list_indexes[min_idx]++;
	return min_val;
}

int main(){
    // 共有15个元素，分成5段，每一段都有序。
    vector<int> tmp = {	2,4,7,
						1,90,91,
						3,5,7,
						10,11,13,
						8,9,12};
}

Radix Sorting GPU 版本

这个在Thrust库中有相应实现。

敲黑板：每一个数与其二进制对应，Radix排序方法对二进制做判断，而在源数上做操作。