(개인 프로젝트) OpenMP를 이용하여 멀티 스레드로 작동하는 정렬 및 검색 프로그램

소개

• 인원 : 1인
• 담당 : 프로그램 구현 전체
• 개발 환경 : Visual Studio 2015, OpenMP 2.0
• 문제
  • Input
    • Data : 0~RANGE 범위, 1,073,741,824개의 floating point number
    • 화면 입력 : 2개의 정수 값 – 예) 4 9
  • Output
    • 화면 출력 : Sorting에 걸린 시간, Search에 걸린 시간
    • 파일 출력 : 정렬한 리스트, 검색한 숫자의 개수와 리스트
• 소스코드 : OpenMP를 이용하여 멀티 스레드로 작동하는 정렬 및 검색 프로그램

내용

1. 일상에서의 접근

문제를 먼저 우리 주변에 있을 수 있는 일로 가져와서 생각해보려고 합니다. 만약 1부터 100까지 숫자가 적힌 카드가 왼쪽처럼 섞여 있을 때, 오름차순으로 정리하려면, 방법은 크게 두 가지 정도 있을 거라고 생각합니다. 하나씩 숫자를 확인하면서 정리된 카드와 비교하고 정리하는 방법과 110, 1120…으로 미리 분류하고 각각 정리하는 방법입니다. 아마도 카드의 개수가 적으면 방법1이 더 빠르겠지만 일정 개수를 넘어간다면 방법2가 더 빠를 것이라고 생각합니다.

2. 실제 문제에 적용

가장 큰 숫자의 크기만큼 배열을 만들어서 이렇게 분류하고, 각 배열을 정렬하는 방법을 생각했습니다. 이 방법을 적용하기 위해서 미리 랜덤 숫자들의 분포를 세서 0번째는 17개, 1번째는 6개….이런 식으로 동적 할당을 해야 합니다. 이렇게 하면 랜덤 수를 저장할 배열 4GB와 숫자를 정리할 배열 4GB로 총 8GB가 필요하고, 메모리 16GB정도의 컴퓨터라면 충분히 실행할 수 있습니다.

3. 병렬화 부분

각 배열을 정렬하는 부분을 병렬로 처리하였습니다. 만약 정렬을 하는 알고리즘을 병렬화 한다면 스레드 사이에 동기화가 필요해서 성능에 좋지 않은 영향을 줄 수 있지만, 이 방법은 각 배열을 정렬하기 때문에 동기화가 전혀 필요하지 않아서 각 스레드가 제 성능을 온전히 발휘할 수 있습니다.

4. 검색 알고리즘
정렬할 때 정수 인덱스를 기준으로 정렬하였고, 각 배열의 크기를 알고 있기 때문에 정수 범위로 검색된 데이터는 단순하게 출력만 하면 됩니다. 따라서 바로 출력만 하면 되기 때문에 시간 복잡도는 O(1)입니다.

5. 결과 분석 (Intel i7-6700K @ 4.00GHz & 16GB RAM 기준)

시리얼 시간을 병렬 시간으로 나누어서 계산한 차트입니다.
스레드가 2개일 때는 약 1.8배, 4개일 때는 2.99배, 8개일 때는 4.09배 정도 성능이 향상되었습니다. 아무래도 물리적인 코어 수는 4개라서 스레드를 8개를 사용하면 효율이 떨어지게 되는 것 같습니다. 그리고 4개를 사용할 때에는 이 프로그램 뿐 만 아니라 다른 백그라운드 프로그램도 프로세서를 사용해야 하기 때문에 2개를 사용했을 때 보다 효율이 떨어질 수밖에 없습니다.

어려웠던 점

처음 구현할 때는 벡터나 리스트를 이용해서 구현하려고 했지만 숫자가 너무 많아서 컴퓨터의 메모리 용량을 초과하는 문제가 발생했습니다. 이에 따라 최적화를 진행하게 되었고, 한 번 파일을 모두 읽은 뒤에 동적할당을 함으로써 이 문제를 해결하였습니다.

배운 점

4학년이 되기 전까지 모든 프로젝트는 싱글코어를 활용한 프로그램들이었지만, 이번에 OpenMP를 배우게 되어 처음으로 멀티코어를 활용한 프로그램을 만들게 되었습니다. 정렬은 정렬할 개수가 많을 수록 오랜 시간이 소요되는 작업인데, 멀티코어를 활용하여 프로그램을 제작하니 빠른 속도로 결과를 얻을 수 있었습니다. 또한, 항상 빠른 정렬 알고리즘을 사용한다고 해서 병렬 처리를 할 때 더 좋은 결과를 얻는 것은 아니라는 사실도 깨달았습니다.