후로링의 프로그래밍 이야기

Heap은 기초적인 내용이지만 Binomial Heap을 다루기 위해 내용을 확실히 숙지해야 하므로 설명하고 넘어가도록 하겠습니다. Heap 이란? 다음 조건을 만족하는 key값을 저장한 Binary Tree 입니다. 1. Heap-Order : 모든 노드는 자신의 부모노드보다 작거나 큰 값을 가진다. 2. Complete Binary Tree : 항상 왼쪽부터 꽉 채워져 있는 형태의 Binary Tree여야 한다. Heap과 Priority Queues(우선순위 큐) 우리는 힙을 우선순위 큐, 다시말해 우선순위가 높은것을 먼저 나가게 하는데에 쓸 수 있습니다. Min heap은 key값을 오름차순 정렬 하는데 쓰일 수 있습니다. Heap에서의 Insert 힙에서의 구조적 조건과 순서적 조건을 맞춰주면 ..

Data structure 자체가 알고리즘을 구현하는 방법이 될 수 있습니다. Skip List 정렬된 linked list에 대해 적용하는 알고리즘으로 빠른 검색및 삽입 삭제를 가능하게 해주는 자료구조입니다. Skip List는 key와 element쌍으로 되어있는 리스트가 여러 레이어에 걸쳐 있는 형태입니다. 각 레이어는 플러스 무한대와 마이너스 무한대를 항상 키 값으로 가지고있고 가장 하위 레이어인 S0는 오름차순으로 정렬되어 있습니다. 그리고 하위레이어는 상위 레이어를 포함하는 형태입니다. 그림으로 살펴보면 아래 그림과 같습니다. Skip List에서의 Search Skip List에서의 Search는 최상단 list의 첫번째 위치에서부터 시작합니다. 만약 현재 위치의 다음 element가 찾으려..

알고리즘에 대해 공부 및 정리를 하며 포스팅을 하려 합니다. 일반적으로 학부때 배우는 간단한 알고리즘이 아닌 Advanced한 부분에 대한 걸 다루려 하니 많은 관심 부탁드립니다. 기본적으로 Introduction to Algorithms 3rd edition을 참고하여 작성하게 될 것입니다. 정렬, Dynamic Programming, Greedy Algorithms등등 을 하고 NP-Complete까지 다뤄볼 작정입니다. 먼저 알고리즘에 대해 간단히 정의하고 알고리즘에 쓰이는 자료구조에 대해 설명하도록 하겠습니다. 컴퓨터 공학에서의 알고리즘이란? "문제를 푸는 잘 정의된 과정"입니다. 어떤 미사여구나 수식어구도 필요없이 위 정의만으로도 컴팩트 하게 알고리즘을 정의 할 수 있습니다. 컴퓨터 공학전공이거..

히스토그램(Histogram) 도수분포표를 그래프로 나타낸 것을 히스토그램이라고 합니다. 간단히 얘기하면 히스토그램은 해당 항목에 대한 빈도수를 구해 그래프로 나타낸 것이라고 할 수 있습니다. 히스토그램은 자료를 분석하는데 있어서 아주 기본적인 도구입니다. 히스토그램 연산 예를들어 1부터 10 사이의 임의의 정수로 이루어진 100의 크기를 가진 배열이 있다고 하면 histogram[10]의 배열에 각 정수의 빈도수를 저장 하는 것입니다. 간단하지만 대상 자료의 크기가 커진다면? 이미지의 해상도에 따라 적게는 100만부터 1000만번씩 연산을 하게 됩니다. 여러개의 데이터에 대해 하나의 연산을 적용하는것이기 때문에 OpenCL로 최적화 하기 아주 좋은 케이스 입니다. 메모리 충돌 스레드 프로그래밍을 배울때..

Median FIlter Median Filter는 픽셀 주변을 둘러싼 픽셀 중 중간값을 찾아서 대체해주는 필터 입니다. 극대값과 극소값을 제거할 수 있습니다. 신호처리 나 이미지 처리에 자주 쓰이는 것으로 대표적으로는 이미지의 소금&후추 잡음을 없애는데 많이 쓰입니다. 다음 예에서는 이미지의 극대값을 없애는데 사용 하였습니다. Median Filter 연산 Median FIlter연산은 연산의 대상이 되는 픽셀 주변의 픽셀을 한줄로 세워 가운데 서있는 픽셀의 값을 취하는 형태입니다. 다시말해 정렬을 해야합니다. 다들 아시다시피 정렬 연산의 Optimal은 O(n*logn)입니다. 수만 픽셀에 대해 정렬을 수행하는 것이라면 GPU를 이용하면 Optimal은 O(logn)입니다. 하지만 Median FIl..

루프 언롤링(Loop Unrolling) 이전 포스트에서 루프 언롤링을 통해 최적화 하는 코드를 잠깐 보았습니다. 루프언롤링이란 for문이나 while문과같은 루프문을 직접적인 명령어의 나열로 바꾸는 기법입니다. 루프를 코드의 나열로 바꾸게 되면 루프 제어를 위한 증가연산, 비교연산이 생략되어 연산량을 감소 시킬 수 있습니다. 또한, GPU에서 실행하는 코드를 컴파일하게 되면 명령어를 묶어 덩어리로 실행하게 되는데, 루프를 사용하지 않으면 명령어가 끊기지않고 담기게 되어 연산속도가 향상됩니다. 코드로 간단히 살펴보면 다음과 같습니다. 먼저 Not unrolled 코드 입니다. 보시는 바와 같이 일반적인 for문입니다. 1234567// Not unrolled for(int i = localRow; i

전체 CL 코드 Local Memory를 이요한 Convolution Filter의 CL 코드 전부 입니다. 복잡해 보이지만 크게 두부분으로 나눌 수 있습니다. barrier(CLK_LOCAL_MEM_FENCE); 를 기준으로 Local Memory에 이미지를 쪼개 넣고 실제로 필터 연산을 수행하는 부분으로 나누어져 있다는 것만 기억하신 후 세부적인 코드로 넘어가도록 하겠습니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969..

Convolution Filter란? 출력화소를 만들기 위해서 주변의 화소값을 이용하여 계산하는 작업을 말합니다. 블러링, 샤프닝, 미분처리, 미디언필터, 평균값필터 등등이 convolution filter에 포함됩니다. 픽셀값을 결정하기위해서 픽셀 주변에 필터에 적용하는 NxN크기의 배열을 convolution kernel이라고 합니다. 예를들어 9개 픽셀의 평균값으로 픽셀의 값을 정하는 연산을 하고싶다면 이 연산에 적용되는 커널은 각 1의 원소를 가진 3X3 크기의 배열입니다. Convolution FIlter와 복잡도 단순하게 생각했을때, 한 이미지에 대해 각 픽셀당 한번씩의 연산을 수행하는 시간이 10ms라면 3x3 크기의 필터를 사용하게되면 연산량이 9배 , 9x9 필터를 사용하게 되면 81배 ..

아마 OpenCL의 전체적인 워크 플로우가 머릿 속에 들어오지 않아 세부적인 이해가 되지 않는 분이 있으리라 생각됩니다. 전체적인 작업의 흐름이 머릿속에 들어오는 것이 무엇보다 중요하므로 확실히 알 수 있도록 정리를 하고 이미지 프로세싱에 들어가려 합니다. Initialization initialization 부분은 GPU에서 병렬처리 작업을 할 수 있도록 CPU와 GPU간의 인터페이스를 정의하고 GPU에서 실행할 함수를 정의하는 부분입니다. 아래 6개의 설정을 마침으로서 OpenCL을 통해 GPU에 작업을 명령할 수 있는 환경을 갖출 수 있게 됩니다. 각 용어에 대한 설명은 본 블로그 OpenCL 튜토리얼 초반부에 잘 설명되어 있으니 참고하시기 바랍니다. -Platform 선택-Device 선택-선택한..

시간이 날 때마다 이전에 공부해 두었던 유니티 셰이더에 대해 꾸준히 포스팅을 하려 합니다. 유니티를 통해 셰이더를 공부하는 것에는 많은 이점이 있습니다. 그중에 가장 큰 장점은 셰이더에 대한 이해를 빠르고 쉽고 명확하게 할 수 있다는 것입니다. OpenGL이나 DIrectX를 통해 셰이더를 처음 공부해 보려고 하시는 분들이 셰이더를 사용 해 보기위해 디바이스를 설정하고 물체를 만들고 하는 등의 일 때문에 포기하게 되는것을 주변에서 여럿 보았습니다. 유니티를 통해 셰이더를 공부하는 것은 새로운 프레임워크를 배우기 위해 공부해야할 부분에 대한 부담감을 확 낮추는 효과가 있습니다. 또한 유니티를 통해 게임을 개발하려는 프로그래머, 아티스트가 유니티 내에 개발되어 있는 셰이더를 사용하지 않고 직접 자신이 원하는..