1 |
1
연산 시간 계산부, 분할부, 전송 시간 계산부, 연산 시간 재계산부, 재분할부, 정렬부를 포함하는 고속 정렬 장치가 수행하는, 고속 정렬 방법에 있어서, 상기 연산 시간 계산부가, 복수의 정렬 대상 데이터들을 서로 다른 기법으로 정렬하는데 소요되는 제1 및 제2 연산 예상 시간을 각각 계산하는 단계; 상기 분할부가 상기 제1 연산 예상 시간과 상기 제2 연산 예상 시간을 이용하여 상기 복수의 정렬 대상 데이터들을 제1 그룹과 제2 그룹으로 분할하는 단계;상기 전송 시간 계산부가 상기 제2 그룹에 속하는 데이터들을 전송하는데 소요되는 전송 예상 시간을 계산하는 단계;상기 연산 시간 재계산부가 상기 전송 예상 시간을 기초로 상기 제2 연산 예상 시간을 재계산하는 단계;상기 재분할부가 상기 제1 연산 예상 시간 및 상기 재계산된 제2 연산 예상 시간을 기초로 상기 복수의 정렬 대상 데이터들을 상기 제1 및 제2 그룹으로 재분할하는 단계; 및상기 정렬부가 상기 재분할된 그룹에 속하는 정렬 대상 데이터들을 정렬하는 단계를 포함하는 고속 정렬 방법
|
2 |
2
제1항에 있어서,상기 고속 정렬 장치는,그래픽 처리부를 더 포함하고,상기 제1 그룹에 속하는 데이터들은, 상기 정렬부에 의하여 CPU에서 데이터의 정렬이 수행되고,상기 제2 그룹에 속하는 데이터들은, 상기 그래픽 처리부에 의하여 GPU에서 데이터의 정렬이 수행되는 것을 특징으로 하는 고속 정렬 방법
|
3 |
3
제2항에 있어서,상기 고속 정렬 장치는,추출부, 조합부를 더 포함하고,상기 추출부가 복수의 정렬 대상 데이터들에 해당하는 인덱스 및 주소를 각각 추출하는 단계;상기 그래픽 처리부가 상기 정렬된 제2 그룹에 속하는 정렬 대상 데이터들을 전송하는 단계; 및상기 조합부가 상기 추출된 인덱스 및 주소를 기초로 상기 정렬된 제1 그룹에 속하는 정렬 대상 데이터들과 상기 정렬된 제2 그룹에 속하는 정렬 대상 데이터들을 재조합하는 단계를 더 포함하는 고속 정렬 방법
|
4 |
4
제3항에 있어서,상기 재조합하는 단계는,상기 조합부가 상기 정렬된 제1 그룹에 속하는 정렬 대상 데이터들과 상기 정렬된 제2 그룹에 속하는 정렬 대상 데이터들을 머지 정렬(MERGE SORT)을 이용하여 재조합하는 것을 특징으로 하는 고속 정렬 방법
|
5 |
5
제1항에 있어서,상기 전송 예상 시간을 계산하는 단계는,상기 전송 시간 계산부가, 상기 분할된 제2 그룹의 크기 및 GPU의 버스 속도를 이용하여 상기 전송 예상 시간을 계산하는 것을 특징으로 하는 고속 정렬 방법
|
6 |
6
제2항에 있어서,상기 계산하는 단계는,상기 연산 시간 계산부가, 상기 복수의 정렬 대상 데이터들을 퀵 정렬(QUICK SORT)하는데 소요되는 상기 제1 연산 예상 시간과 상기 복수의 정렬 대상 데이터들을 바이토닉 정렬(BITONIC SORT)하는데 소요되는 상기 제2 연산 예상 시간을 계산하고,상기 정렬하는 단계는,상기 정렬부가 상기 제1 그룹에 속하는 정렬 대상 데이터들을 상기 퀵 정렬하고,상기 그래픽 처리부가 상기 제2 그룹에 속하는 정렬 대상 데이터들을 상기 바이토닉 정렬하는 것을 특징으로 하는 고속 정렬 방법
|
7 |
7
복수의 정렬 대상 데이터들을 서로 다른 기법으로 정렬하는데 소요되는 제1 및 제2 연산 예상 시간을 각각 계산하는 연산 시간 계산부;상기 제1 연산 예상 시간과 상기 제2 연산 예상 시간을 이용하여 상기 복수의 정렬 대상 데이터들을 제1 및 제2 그룹으로 분할하는 분할부; 상기 제2 그룹에 속하는 정렬 대상 데이터들을 전송하는데 소요되는 전송 예상 시간을 계산하는 전송 시간 계산부;상기 전송 예상 시간을 기초로 상기 제2 그룹에 속하는 데이터들을 정렬하는데 소요되는 제2 연산 예상 시간을 재계산하는 연산 시간 재계산부;상기 제1 연산 예상 시간 및 상기 재계산된 제2 연산 예상 시간을 기초로 상기 복수의 정렬 대상 데이터들을 상기 제1 및 제2 그룹으로 재분할하는 재분할부; 및상기 재분할된 그룹에 속하는 정렬 대상 데이터들을 정렬하는 정렬부를 포함하는 고속 정렬 장치
|
8 |
8
제7항에 있어서,상기 재분할된 제2 그룹에 속하는 정렬 대상 데이터들을 정렬하는 그래픽 처리부를 더 포함하고,상기 정렬부는,상기 재분할된 제1 그룹에 속하는 정렬 대상 데이터들을 정렬하는 고속 정렬 장치
|
9 |
9
제8항에 있어서,복수의 정렬 대상 데이터들에 해당하는 인덱스 및 주소를 각각 추출하는 추출부; 및상기 추출된 인덱스 및 주소를 기초로 상기 정렬된 제1 그룹에 속하는 정렬 대상 데이터들과 상기 정렬된 제2 그룹에 속하는 정렬 대상 데이터들을 재조합하는 조합부를 더 포함하는 고속 정렬 장치
|
10 |
10
제7항에 있어서,상기 연산 시간 계산부는,상기 복수의 정렬 대상 데이터들을 CPU에서 퀵 정렬(QUICK SORT)하는데 소요되는 상기 제1 연산 예상 시간과 상기 복수의 정렬 대상 데이터들을 GPU에서 바이토닉 정렬(BITONIC SORT)하는데 소용되는 상기 제2 연산 예상 시간을 계산하고,상기 연산 시간 재계산부는,상기 전송 예상 시간을 기초로 상기 제2 그룹에 속하는 데이터들을 정렬하는데 소요되는 상기 제2 연산 예상 시간을 재계산하는 것을 특징으로 하는 고속 정렬 장치
|