소개

• 인원 : 1인
• 담당 : 프로그램 구현 전체
• 개발 환경 : Visual Studio 2015, CUDA 9.0
• 문제
  • Input
    • Data : 비트맵 이미지의 R, G, B 값
    • 화면 입력 : 불러올 이미지 파일 이름, 적용 필터
  • Output
    • 화면 출력 : 필터 적용에 걸린 시간, 저장된 파일 이름
    • 파일 출력 : 필터가 적용된 이미지
• 소스코드 : CUDA를 이용해서 멀티 스레드로 작동하는 Image Filter 프로그램

내용

1. 전부 다 늘릴 때와 각각을 늘릴 때의 차이

두 필터는 RGB에 일정 비율을 곱했다는 공통점이 있습니다. 이 중에 밝기 필터는 단순하게 모든 픽셀의 RGB값을 일정 비율만큼 더하면 되지만, 저희가 만든 필터는 채도를 올리는 방식이라서 붉은 계열 색상이라면 더 붉게 만들고, 푸른 계열 색상이라면 더 푸르게 만들어야 합니다.

2. 적용 방법

RGB 값을 비교하고, 가장 많이 쓰인 색을 높이는 방식으로 필터를 구현했습니다.

3. 병렬화 부분

그리드와 블록은 단순하게 설계하였습니다, 먼저 총 픽셀 수를 구하고, 블록 당 스레드 수를 지정하게 됩니다. 그리고 각 스레드는 한 픽셀 씩 맡아서 RGB값을 처리하게 됩니다. 이렇게 스레드가 한 픽셀을 맡게 되면 동기화 문제는 해결됩니다.

5. 결과 분석 (Intel i7-7700 & GTX 1070 기준)



각 필터 마다 CPU 시간을 GPU 시간으로 나누어서 계산한 차트입니다.
평균적으로 10배 이상의 성능 향상을 보이고, 그레이 필터는 다른 필터보다 더 빠른 23배 정도의 성능향상이 있었습니다.
아무래도 CPU나 GPU 둘 다 높은 성능 이라서 큰 차이가 보이지 않는 것 같습니다.

어려웠던 점

무작정 큰 값만 늘리다보니 문제가 발생했습니다. 이 주변은 하늘이라서 주로 파란색 값이 크지만, 이 부분은 구름과 겹쳐서 파란색보다 녹색이 더 많았습니다. 그래서 이 픽셀만 녹색이 더 증가하는 문제가 생기게 된다는 사실을 알았습니다.

이 문제를 해결하기 위해 허용 범위를 지정하였습니다. RGB 값의 차이가 일정 범위 이내라면 비슷한 값들을 한 번에 증가시켰습니다. 이렇게 증가시켰더니 이전 사진에서 구름 일부가 녹색으로 바뀌던 문제를 해결할 수 있었습니다.

배운 점

이전에 OpenMP만 사용할 때에는 CPU만 사용했기 때문에 스레드가 많아야 겨우 8개 정도였지만, 이번에는 그래픽 카드를 이용했기 때문에 훨씬 많은 수의 스레드를 생성하고 제어하였습니다. 이 프로젝트에서는 사진 파일이 가진 픽셀 수 만큼 스레드를 생성하였는데, 1024 X 1024의 사이즈를 가진 사진이라면 100만개 이상의 스레드를 생성하게 됩니다. 너무 많은 수의 스레드를 생성하다보니 이를 제어하는 것이 처음에는 어려웠지만, 점점 익숙해져서 잘 다룰 수 있게 되었습니다.

소개

• 인원 : 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를 배우게 되어 처음으로 멀티코어를 활용한 프로그램을 만들게 되었습니다. 정렬은 정렬할 개수가 많을 수록 오랜 시간이 소요되는 작업인데, 멀티코어를 활용하여 프로그램을 제작하니 빠른 속도로 결과를 얻을 수 있었습니다. 또한, 항상 빠른 정렬 알고리즘을 사용한다고 해서 병렬 처리를 할 때 더 좋은 결과를 얻는 것은 아니라는 사실도 깨달았습니다.