집밖은 위험해

2020-07-29

• 지난 시간에는 영상에 존재하는 경계점인 에지와 선분 검출 알고리즘, 그리고 지역 특징에 대한 개요에 대한 내용을 살펴보면서 비전 분야 학습을 진행하였고, 이외에 해킹 관련 기본 개념들과 바이너리 에디터로 기계어 코딩을 직접하여 부팅 가능한 이미지를 구현해보았습니다. 이번 시간에는 대표적인 지역 특징 검출 알고리즘인 SIFT와 SURF에 대해서 살펴보고, 영역 분할 알고리즘 그리고 이러한 특징에 대한 추가 정보인 특징 기술자가 무엇인지 살펴보았습니다. 또 병렬 프로그래밍 플랫폼인 openmp에 대한 개요적인 내용과 사용법을 학습하고, 키보드 후킹과 이미지 파일을 해킹하는 윈도우 어플리케이션 해킹 예제들을 통한 학습을 진행하였습니다.
• 우선 대표적인 지역 특징 검출 알고리즘인 SIFT와 SURF에 대해서 학습하였습니다. 우선 SIFT는 영상의 크기에 불변하는 지역 특징 알고리즘이라 할수 있는데, 입력 영상이 주어지면 이를 다양한 스캐일로 만들고, 여러 분포에 대한 가우시안 영상을 차분한 차분 영상을 획득합니다. 다중 스케일 차분 영상들에서 구한 특징들이 SIFT 키포인트가 되었습니다. 하지만 SIFT 알고리즘에서는 여러개의 영상에 대해 가우시안 마스크를 적용하고 차분 영상을 얻기까지에 대한 과정은 상당히 많은 계산량을 요구하여 시간이 오래걸리는 단점이 있었습니다. 이러한 문제를 극복한 SURF 알고리즘은 가우시안 필터를 박스 필터로 근사화하여 적분 영상을 이용해 박스필터들을 적용하는 방법을 사용하여, 기존의 SIFT 검출 알고리즘보다 훨씬 빠른 시간에 크기에 불변한 특징점들을 검출할수 있었습니다.
• SIFT와 SURF 지역 특징 검출 알고리즘 다음으로 이미지의 영역을 분할하는 방법에 대해서 살펴보았습니다. 가장 간단한 것으로 임계치를 이용한 이진화, 색상 영역을 이용한 분할, 최소 신장 트리나 정규화 영상을 사용한 그래프 기반 방법 그리고 민시프트로 대표되는 클러스터링 알고리즘 기반 영역 분할 방법들이 존재하였습니다. 그래프 기반 방법 중에 최소 신장 트리 방법에서는 영상을 그래프의 형태로 구현하고, 이 그래프에 대한 최소 신장 트리를 만듦으로서 영상 영역들을 구분하는 방법이었습니다. 정규화 절단 방법의 경우 입력 영상을 유사도 그래프와 인접 행렬로 표현하고 연결 요소들을 분할되도록 계산하는 과정을반복하여 비슷한 영역들을 분할하는 방법이었습니다.
• 이 외에 추가적인 클러스터링 기반 영역 분할 방법들도 살펴보았습니다. 일단 클러스터링에 앞서 샘플들과 이 샘플들을 나타내는 확률 밀도 함수 그리고 그 함수의 봉우리인 모드의 개념을 보고, 클러스터링 문제를 다루기 시작하였습니다. 클러스터링 알고리즘 중 가장 대표적인 알고리즘이 kmeans 부터, 물체 추적에 자주 사용되는 민시프트, 그리고 DBSCAN까지 각 클러스터링 알고리즘의 특성과 장단점을 살펴보고, 민시프트 알고리즘이 물체 추적과 영상 분할에 어떻게 사용되는지 이해하는데 도움되었습니다.
• 영상처리의 마지막으로 특징 기술자에 대해서 학습을 진행하였습니다. 기술자란 지역 특징이 제공하지 못한 특징에 관한 추가적인 정보로 지역 특징이 해당 점의 위치와 스케일 정보만 제공한다면 기술자는 방향과 특징 벡터를 제공한다고 할수 있습니다. 이전에 살펴본 SIFT, SURF 특징은 스케일에 불변하는 특징이나 회전 불변에 필요한 정보들을 가지고 있지 않습니다. 그런 문제를 개선하기 위해서 특징 기술자가 필요하게 됩니다. 특징 기술자는 키포인트를 중심으로 커널을 씌워 윈도우 내부에 있는 픽셀들의 그라디언트 영상을 만들고, 이를 8단계로 양자화하여 그라디언트 방향 히스토그램을 만들어 주요방향을 찾습니다. 이 그라디언트 방향 히스토그램이 기술자 특징 벡터가 됩니다. 그래서 SIFT 기술자를 추출한다는 것은 기존의 키포인트, 특징점이 주어지면 이 키포인트에 주요 방향과 특징 벡터가 추가된 키포인트를 기술자라고 할수 있겠습니다.
• 오늘 영상 학습 하는 동안 영상 특징과 기술자, 분할 기술에 대해서 살펴보고, 나머지 시간에는 병렬 프로그래밍 플랫폼인 openmp와 윈도우 해킹에 대해서 학습을 했습니다. 이전에 openmp는 opencv를 빌드하거나 다른 오픈소스를 빌드하면서 종종 본 이름이고, 병렬프로그래밍을 수행한다는것은 알고 있었으나 이게 어떻게 한다는것인지 잘 몰랐습니다. 우연히 openmp 수업에 참여할수 있는 기회를 얻게 되어 수업에 참관하면서 openmp가 무엇인지 병렬프로그래밍을 어떻게 하고, 성능 개선이 이루어지는지 등에 대해 배울수 있었습니다.
• 마지막으로 윈도우 해킹과 관련된 내용들을 학습하였습니다. 32비트 윈도우에서는 자원을 제어하기 위한 WIN32API를 제공하고 있었습니다. 이 API와 제공하는 DLL을 통해 메시지를 후킹을 해보았으며, 별개로 이미지 파일을 임의로 수정하여 자바스크립트를 삽입하는 실습을 진행하였습니다. 먼저 키보드 후킹 예제를 연습해 보았습니다. kernel32.dll로부터 후킹 함수를 가져와 키로거 클래스를 정의하여 키 입력들이 오면 출력하고 ctrl을 누르면 종료되도록 구현하였습니다. 이미지 해킹 과정으로 기존의 비트맵 이미지를 파일 입출력 함수로 읽어들여 데이터 부분들을 주석처리하고 뒤에 알람을 띄우는 js 코드를 추가하도록 수정하였습니다. 이 수정된 비트맵 파일을 간단한 html에서 로드하면 이미지 파일 내에 존재하는 js코드가 실행되는 모습을 확인하였고, 악의적인 코드를 입력한다면 상당히 위험할수도 있을것 같아보였습니다.
• 이번시간에는 특징점, 영상분할, 기술자 등 비전 분야 내용들과 openmp의 기본사용법 그리고 간단한 윈도우 어플리케이션 해킹 실습을 해보았습니다. 내일은 openmp 나머지 내용을 학습하고, 이전에 기계어로 부팅 이미지를 만들었던것을 개선하여 어셈블리어로 구현하기, 영역 기술자, 주성분 분석 등 영상 파트 내용들을 학습할 예정입니다.

테스크 데이터 유효범위

- 지정하지 않은것들은 기본적으로 shared

- parallel에서 bde tid가 private -> a와 c는 shared

- single에서 스레드 하나만 a=2, b=3, c=4, d=5, e=6으로 할당.

- a와 c는 shared이므로 다른 스레드도 영향받음, 나머지 bde는 그대로 0

#include <stdio.h>
#include <omp.h>

int main()
{
        int a=1, b=2, c=3, d=4, e=5, tid;

        omp_set_num_threads(4);
#pragma omp parallel private(b,d,e, tid)
{
        tid = omp_get_thread_num();
        printf("tid=%d a=%d b=%d c=%d d=%d e=%d\n", tid, a, b, c, d, e);
        #pragma omp single
        {  printf("in single: %d \n", tid);
           a=2, b=3, c=4, d=5, e=6; }
        #pragma omp task private(e)
        {
                printf("task tid=%d a=%d b=%d c=%d d=%d e=%d\n", omp_get_thread_num(), a, b, c, d, e);
        }
}
}

단순 피보나치

#include <stdio.h>

int fibon(int n) // f(n) = f(n-1) + f(n-2)
{
   int x, y;
   if(n<2) return n;
   x=fibon(n-1);
   y=fibon(n-2);
   return (x+y);
}

int main()
{
   int result = fibon(MAX);
   printf("Fibonacci (%d) = %d\n", MAX, result);
   return 0;
}

재귀 프로그래밍으로 구현한 피보나치 태스크

- 9.485s 소요

#include <stdio.h>

int fibon(int n) // f(n) = f(n-1) + f(n-2)
{
   int x, y;
   if(n<2) return n;
   #pragma omp task shared(x)
   { x=fibon(n-1); }
   #pragma omp task shared(y)
   { y=fibon(n-2); }
   #pragma omp taskwait

   return (x+y);
}

int main()
{

#pragma omp parallel
{
#pragma omp single nowait
{
   printf("Fibonacci (%d) = %d\n", MAX, fibon(MAX));
}
}
   return 0;
}

재귀 프로그래밍으로 구현한 피보나치 태스크

- n < 30구문 아래의 x,y 계산은 조건문 안의 함수가 다 호출된 후 순서대로 시작 => n<30인 경우 시리얼로 처리

- n >= 30은 테스크로 처리

#include <stdio.h>

long int fibon(int n) // f(n) = f(n-1) + f(n-2)
{
   long int x, y;
   if(n<2) return n;

   if(n<30){
      return fibon(n-1)+fibon(n-2);
   }
   else
   {
   #pragma omp task shared(x)
   { x=fibon(n-1); }
   #pragma omp task shared(y)
   { y=fibon(n-2); }
   #pragma omp taskwait

   return (x+y);
   }
}

int main()
{

#pragma omp parallel
{
#pragma omp single nowait
{
   printf("Fibonacci (%d) = %ld\n", MAX, fibon(MAX));
}
}
   return 0;
}

테스크

- 암시적 묶음(스레드당 하나)

- 스레드 팀 발생

- 팀내 각 스레드에 테스크 하나씩 할당( 스레드 하나에 테스크가 묶임)

- 모든 태스크가 멈출때까지 마스터 스래드 대기

태스크의 개념

- 태스크 스캐줄링 = 은행 번호표 시스템

- 태스크 = 은행 업무

- 스레드 = 은행원

태스크 라이프사이클

1. 태스크 생성

2. 태스크 실행

3. 경우에 따라 일시 정지 후 재실행 등

4. 실행 완료

테스크 예제 1

- 32개의 스레드가 모두 ABCD 다 출력

#include <stdio.h>
#include <omp.h>

int main()
{
#pragma omp parallel num_threads(32)
{
        printf("A ");
        printf("B ");
        printf("C ");
        printf("D ");
        printf("\n");
} // pragma omp parallel
}

테스크 예제2

- ABCD다 19번스레드가 수행

#include <stdio.h>
#include <omp.h>

int main()
{
#pragma omp parallel num_threads(32)
{
        #pragma omp single
        {
                printf("A tid=%d\n", omp_get_thread_num() );
                printf("B tid=%d\n", omp_get_thread_num() );
                printf("C tid=%d\n", omp_get_thread_num() );
                printf("D tid=%d\n", omp_get_thread_num() );
        }
}
}

테스크 예제3

- 스래드 32개 준비됨

- A는 10번 스레드가 수행

- B와 C 테스크에 20, 10번 스레드가 수행

- 마무리 후 D는 1번 스레드가 수행

#include <stdio.h>
#include <omp.h>

int main()
{
#pragma omp parallel num_threads(32)
{
        #pragma omp single
        {
                printf("A tid=%d\n", omp_get_thread_num() );
                #pragma omp task
                {
                        printf("B tid=%d\n", omp_get_thread_num() );
                }
                #pragma omp task
                {
                        printf("C tid=%d\n", omp_get_thread_num() );
                }
                printf("D tid=%d\n", omp_get_thread_num() );
        }
}
}

테스크 예제 4

- taskwait : 태스크가 끝날떄까지 대기 = wait

- A를 23이 수행, 태스크 B와 C를 18, 25가 수행, 태스크가 끝나면 D를 23번이 수행

=> taskwait한 탓에 테스크 예제3번보다 0.003s 더 오래 걸림

#include <stdio.h>
#include <omp.h>

int main()
{
#pragma omp parallel num_threads(32)
{
        #pragma omp single
        {
                printf("A tid=%d\n", omp_get_thread_num() );
                #pragma omp task
                {
                        printf("B tid=%d\n", omp_get_thread_num() );
                }
                #pragma omp task
                {
                        printf("C tid=%d\n", omp_get_thread_num() );
                }
                #pragma omp taskwait
                printf("D tid=%d\n", omp_get_thread_num() );
        }
}
}

스캐줄링 정책 scheduling clauses

- 루프 실행에서 분배 방식을 지정

- 기본적인 스캐줄링 정책은 : 실행 횟수를 균등 분배

- 작업 균등 분배를 하기 위해서 스캐쥴링 정책을 사용

스캐줄링 정책 종류

- 정적 정책 static [, chunk_size] : 반복 실행 횟수를 스레드 마다 균일하게 할당(기본 스캐줄링 정책)

- 동적 정책 dynamic [, chunk_size] : 반복 실행 회수를 chunk_size로 나누어 chunk 생성.

                                              먼저  작업 끝난 스레드에 다음 chunk 할당

- 안내 정책 guided [, chunk_size] : 동적 스캐줄링으로, 반복 중에 chunk의 크기가 변함

- 실행 시간 정책 runtime : 프로그램 실행중에 환경변수 OMP_SCHEDULE 값을 참조하,

                                재컴파일 없이 여러 스캐줄링 방식 사용

                          => ex. export OMP_SCHEDULE="dynamic"

만델브로트

- 순차 프로그램 

- 13.261s 소요

#include <stdio.h>

#define         X_RESN  4000       /* x resolution */
#define         Y_RESN  4000       /* y resolution */
#define         X_MIN   -2.0
#define         X_MAX    2.0
#define         Y_MIN   -2.0
#define         Y_MAX    2.0


typedef struct complextype
{
        float real, imag;
} Compl;


int main ( int argc, char* argv[])
{

        /* Mandlebrot variables */
        int i, j, k;
        Compl   z, c;
        float   lengthsq, temp;
        int maxIterations;
        int res[X_RESN][Y_RESN];

        maxIterations = 1000;
        for(i=0; i < Y_RESN; i++) {
                for(j=0; j < X_RESN; j++) {
                        z.real = z.imag = 0.0;
                        c.real = X_MIN + j * (X_MAX - X_MIN)/X_RESN;
                        c.imag = Y_MAX - i * (Y_MAX - Y_MIN)/Y_RESN;
                        k = 0;

                        do  {
                                temp = z.real*z.real - z.imag*z.imag + c.real;
                                z.imag = 2.0*z.real*z.imag + c.imag;
                                z.real = temp;
                                lengthsq = z.real*z.real+z.imag*z.imag;
                                k++;

                        } while (lengthsq < 4.0 && k < maxIterations);

                        if (k >= maxIterations) res[i][j] = 0;
                        else res[i][j] = 1;

                }
        }
}

- 정적 병렬 프로그램

 -> 1.305s 소요

#include <stdio.h>

#define         X_RESN  4000       /* x resolution */
#define         Y_RESN  4000       /* y resolution */
#define         X_MIN   -2.0
#define         X_MAX    2.0
#define         Y_MIN   -2.0
#define         Y_MAX    2.0


typedef struct complextype
{
        float real, imag;
} Compl;


int main ( int argc, char* argv[])
{

        /* Mandlebrot variables */
        int i, j, k;
        Compl   z, c;
        float   lengthsq, temp;
        int maxIterations;
        int res[X_RESN][Y_RESN];

        maxIterations = 1000;
#pragma omp parallel for shared(res,maxIterations) private(i,j,z,c,k,temp,lengthsq) schedule(static)
        for(i=0; i < Y_RESN; i++)
                for(j=0; j < X_RESN; j++) {
                        z.real = z.imag = 0.0;
                        c.real = X_MIN + j * (X_MAX - X_MIN)/X_RESN;
                        c.imag = Y_MAX - i * (Y_MAX - Y_MIN)/Y_RESN;
                        k = 0;

                        do  {

                                temp = z.real*z.real - z.imag*z.imag + c.real;
                                z.imag = 2.0*z.real*z.imag + c.imag;
                                z.real = temp;
                                lengthsq = z.real*z.real+z.imag*z.imag;
                                k++;

                        } while (lengthsq < 4.0 && k < maxIterations);

                        if (k >= maxIterations) res[i][j] = 0;
                        else res[i][j] = 1;

                }
}

- 병렬 프로그래밍 동적

 -> 0.507s 소요

#include <stdio.h>

#define         X_RESN  4000       /* x resolution */
#define         Y_RESN  8000       /* y resolution */
#define         X_MIN   -2.0
#define         X_MAX    2.0
#define         Y_MIN   -2.0
#define         Y_MAX    2.0


typedef struct complextype
{
        float real, imag;
} Compl;


int main ( int argc, char* argv[])
{

        /* Mandlebrot variables */
        int i, j, k;
        Compl   z, c;
        float   lengthsq, temp;
        int maxIterations;
        int res[X_RESN][Y_RESN];

        maxIterations = 1000;
#pragma omp parallel for shared(res,maxIterations) private(i,j,z,c,k,temp,lengthsq) schedule(dynamic,5)
        for(i=0; i < X_RESN; i++)
                for(j=0; j < Y_RESN; j++) {
                        z.real = z.imag = 0.0;
                        c.real = X_MIN + j * (X_MAX - X_MIN)/X_RESN;
                        c.imag = Y_MAX - i * (Y_MAX - Y_MIN)/Y_RESN;
                        k = 0;

                        do  {

                                temp = z.real*z.real - z.imag*z.imag + c.real;
                                z.imag = 2.0*z.real*z.imag + c.imag;
                                z.real = temp;
                                lengthsq = z.real*z.real+z.imag*z.imag;
                                k++;

                        } while (lengthsq < 4.0 && k < maxIterations);

                        if (k >= maxIterations) res[i][j] = 0;
                        else res[i][j] = 1;

                }
}

2020-07-28(화)

• 지난 시간에는 컴퓨터 비전에 관하여 개요 적인 내용과 다양한 연산에 대해서 살펴보았습니다. 오늘은 이러한 기본 연산을 이용하여 영상 내부에 존재하는 에지와 선분 검출 방법, 지역 특징 등에 대해서 간단히 살펴보고, 이와 별개로 컴퓨터 해킹과 관련된 일부 내용과 바이너리 에디터를 이용한 부팅 가능 이미지 만드는 과정에 대해서 학습을 진행하였습니다.
• 우선 지난번에 모폴로지 연산까지 학습한 데에 이어서 오늘은 에지 검출부터 시작하였습니다. 에지란 영상의 기울기가 급격히 변하는 부분으로 영상에 존재하는 모서리, 선과 같은 요소들이라 할수 있으며 영상의 미분을 통해 구할수 있습니다. 에지를 구하는데 있어 x와 y방향에 대한 기울기 영상, 그라디언트 벡터를 만들게 됩니다. 여기서 이러한 기울기 영상에 마스크를 적용하기도 하는데 로버츠 연산자, 프레윗 연산자, 그리고 가장 유명한 소벨 연산자가 존재합니다. 이러한 연산자와 더불어 가장 대중적으로 사용하는 에지 검출 방법로 캐니 에지가 있으며, 이전의 에지 연산자들이 영상 미분 마스크였다면 캐니 에지는 에지 영상을 검출하는대 최적화 방법을 사용하는것이 차이점이라 할수 있겠습니다. 이러한 다양한 에지들과 특성에 대해서 간단히 살펴보았습니다.
• 다음으로는 이러한 에지를 이용한 선분 검출 알고리즘에 대해서 살펴보았습니다. 에지를 그대로 선분으로 사용할수 있지 않을까 생각되기도 하였으나 에지는 잡음의 영향을 크게 받으며, 에지가 경계 요소를 나타낸다 하더라도 중간에 끊어지는 등의 문제로 에지 자체를 선분으로 사용하기에는 어렵습니다. 그래서 이러한 에지 요소들을 이용해 선을 검출하는 대표적인 방법인 허프 변환과 ransac에 대해서 알아보았습니다. 허프 변환은 에지 영상에 존재하는 에지들을 극좌표계 상으로 표현하여 극좌표계상 에지들의 교점을 원래 y-x 평면에서의 선분 요소로 사용하는 방법이며, 번호판 검출이나 다양한 알고리즘에서 사용되고 있습니다. ransac의 경우 샘플 데이터로부터 노이즈의 영향을 제거한 가장 근사화된 모델을 구하는 알고리즘으로 아웃라이어가 존재하더라도 실제에 가까운 모델에 구하는 과정을 살펴보았습니다.
• 영상처리중 가장 중요한 분야중 하나인 지역 특징에 대해서도 학습하였습니다. 지역 특징은 영상 내에 존재하는 물체간 매칭에 사용될 점이라고 할수 있으며, 영상의 크기인 스케일과 위치, 방향 특징 벡터 등으로 구성되어 있습니다. 지역 특징은 다른 특징들과 구분가능하며 다른 변형된 영상에서도 검출가능하며, 가려진 상황에서도 대처할수 있어야 하는 성질이 필요합니다. 이러한 지역 특징을 구하는 모라벡, 헤리스 코너 등의 알고리즘을 간단히 살펴보고 이러한 연산 과정에 필요한 그라디언트, 자코비안, 헤시안, 라플라시안 등에 대해서 학습을 진행하였습니다.
• 컴퓨터 비전 분야의 학습은 여기까지 마무리하고 다음으로는 해킹 관련 분야에 대한 학습을 시작하였습니다. 컴퓨터를 다루면서 컴퓨터 구조에 대해서 간단하게는 이제 알게 되었으나 컴퓨터의 통신 방식이나 내부 동작과정에 있어서 아직 막연함이 컷습니다. 파일을 만져볼일이 없으니 파일의 구조가 정확하게 어떤지, 패킷을 다뤄보지 않으니 패킷이 어떤 정보로 실제로 이루어져있고 저에게는 막연한 영역이라 추루 임베디드 개발 등에 있어서 해킹 측면에서의 학습이 많은 도움이 될것 같아 이 분야에 대해서도 학습을 시작하였습니다.
• 우선 해킹에 대해 다루면서 가장 먼저 해커와 크래커의 차이, 해커가 하는일, 그리고 해킹에 어떤것들이 있는지 살펴보았습니다. 저는 컴퓨터 소프트웨어에 웹 어플리케이션, 모바일, 임베디드 정도로만 분류할수 있었지 그 이상에 대해서는 잘 모르고 있었습니다. 컴퓨터 소프트웨어를 이와 유사한 관점에서 해킹의 종류들을 분류하였으며 각 분야의 해킹에 어떤 방식으로 취약점을 찾아 공격을 수행하는지 이전에 얼핏 듣기만 했던 공격 방식들에 대해서 조금 명확하게 파악할수 있었습니다. 그리고 내일부터 해킹에 대해서 제대로 살펴보기에 앞서 관련된 용어들을 정리하였습니다. 컴퓨터 구조부터 프로세스와 메모리, 프로토콜 등 개념과 구성들을 다시 반복하면서 어느 부분에 집중을 해야할지 이해하는데 많은 도움이 되었습니다.
• 마지막으로 운영체제 개발 관련된 학습의 일환으로 바이너리 에디터로 부팅가능한 이미지 파일을 생성하였습니다. 해킹 공부를 시작한것과 비슷한 취지로 저는 바이너리와 실제 프로그래밍 영역에 대해서 아주 깊은 이해도를 가지고 있지는 않았습니다. 그나마 결과물을 만들었던 GUI나 웹 어플리케이션의 경우에도 예제 코드를 제가 원하는 방향대로 수정하고 기능을 추가시켜서 만들었지 소프트웨어 개발에서 어떠한 철학이나 확고한 생각을 가지고 구현한 것은 아니라 예제를 수정하는것 이상에 대한 개발 지식이 전무하다 싶었습니다. 그런 목표로 운영체제 개발하는 좋은 자료를 찾아 학습을 시작하였으며, 가장 기본적인 단계로 이전에 가끔 보던 핵스 덤프를 조작하는 바이너리 에디터로 어떻게 동작되는지는 잘 모르겠지만 순수한 기계어로 hello world를 출력하는 간단한 부팅 이미지를 만들어 가상화 머신 QEMU와 bochs 상에서 돌려보는 실습을 진행하였습니다. 기계어 부터 시작하여 어셈블리어, 실제 운영체제 기능을 하나하나씩 구현해나가다보면 운영체제에 대한 전반적인 이해도 뿐만 아니라 구조체 정의 방법과 컴퓨터 소프트웨어 설계 등 좋은 개발자가 되는데 한번 거쳐볼만한 과정인것 같았습니다.

ordered

- ciritical + 순서대로 수행

- 스레드가 순서대로 수행되는걸 볼수있음

#include <stdio.h>
#include <omp.h>

int main()
{
        int i, a[10];
        omp_set_num_threads(4);
#pragma omp parallel private(i)
{
        #pragma omp for //ordered
        for(i=0; i<10; i++) {
                a[i] = i * 2;
//              #pragma omp ordered
                printf("a[%d] = %d\n", i, a[i]);
        }
}
}

lock

- critical과 동일하나 더 유용하며, 쓰임새가 다양함

- 동기화 영역을 지정 -> set_lock, unset_lock

#include <stdio.h>
#include <omp.h>

int main()
{
        int x = 1;
        omp_lock_t lock;

        omp_init_lock(&lock);

        omp_set_num_threads(4);
#pragma omp parallel
{
        omp_set_lock(&lock);
        x++;
        printf("x = %d\n", x);
        omp_unset_lock(&lock);
} // pragma omp parallel
}

동기화

- nowait

- ordered, lock, flush

nowait

- 베리어 기능이 있는 명령어 사용시 작업이 끝날떄까지 기다림 => 시간 낭비 발생

- nowait 구문이 있을시 대기하지 않게함.

nowait 사용 예제 1

- 사용 안한경우

 -> 2번이 먼저 들어오나 이후 들어오는 작업들을 대기후, 같이 수행하여 늦게 종료됨

#include <stdio.h>
#include <omp.h>
#define N 20

int main()
{
        int i, a[N];

        omp_set_num_threads(4);
#pragma omp parallel private(i)
{
        if( omp_get_thread_num() != 2 )
                sleep(5);
        #pragma omp for
        for(i=0; i<N; i++) {
                a[i] = i;
                printf("a[%d]=%d tid=%d\n", i, a[i], omp_get_thread_num());
        }
        printf("end %d thread\n", omp_get_thread_num());
} // pragma omp parallel private(i)
}

- 사용한 경우

 2번이 먼저 들어오므로 먼저 마무리하고 나머지 스래드들의 연산 분할

 => 사용안한 경우보다 조금빨리종료

#include <stdio.h>
#include <omp.h>
#define N 20

int main()
{
        int i, a[N];

        omp_set_num_threads(4);
#pragma omp parallel private(i)
{
        if( omp_get_thread_num() != 2 )
                sleep(2);
        #pragma omp for nowait
        for(i=0; i<N; i++) {
                a[i] = i;
                printf("a[%d]=%d tid=%d\n", i, a[i], omp_get_thread_num());
        }
        printf("end %d thread\n", omp_get_thread_num());
} // pragma omp parallel private(i)
}

nowait 사용 예제 2 section

- 사용 안한경우

#include <stdio.h>
#include <omp.h>
#define N 4

int main()
{
        int i, tid;
        omp_set_num_threads(4);
#pragma omp parallel private(i, tid)
{
        tid = omp_get_thread_num();
        #pragma omp sections
        {
                #pragma omp section
                {
                        for(i=0; i<N; i++)
                                printf("L1 tid=%d\n", tid);
                }
                #pragma omp section
                {
                        for(i=0; i<N; i++)
                                printf("L2 tid=%d\n", tid);
                        sleep(2);
                }
        }
        printf("end tid=%d\n", tid);
} // pragma omp parallel
}

- 사용한 경우

#include <stdio.h>
#include <omp.h>
#define N 4

int main()
{
        int i, tid;
        omp_set_num_threads(4);
#pragma omp parallel private(i, tid)
{
        tid = omp_get_thread_num();
        #pragma omp sections nowait
        {
                #pragma omp section
                {
                        for(i=0; i<N; i++)
                                printf("L1 tid=%d\n", tid);
                }
                #pragma omp section
                {
                        for(i=0; i<N; i++)
                                printf("L2 tid=%d\n", tid);
                        sleep(2);
                }
        }
        printf("end tid=%d\n", tid);
} // pragma omp parallel
}

작업 분할지시어

-do/for : 전체 스래드들에게 일을 분담하여 맡김. 노는 스래드 x

-sections : 스레드 하나씩에게 일 할당. 나머지 스레드는 대기

-single : 하나의 스레드에게만 일시킴. 나머지는 대기

-workshare : fortran 명령어

section

- 스레드 하나에게 작업을 할당해주는 구문

- 모든 section이 종료될때까지 대기함

- 문제점 : 스레드가 10개가 존재하는데, section이 2개뿐이라면 -> 8개는 쉬고 있음

section 예제

#include <stdio.h>
#include <omp.h>

int main()
{
        int i, a[10], b[20];

        omp_set_num_threads(2);
#pragma omp parallel private(i)
{
        #pragma omp sections
        {
                #pragma omp section
                for(i=0; i<10; i++)
                        a[i] = i*10+5;
                #pragma omp section
                for(i=0; i<20; i++)
                        b[i] = i*5+10;
        }
} // pragma omp parallel private(i)

        for(i=0; i<10; i++)
                printf("%d ", a[i]);
        printf("\n");
        for(i=0; i<20; i++)
                printf("%d ", b[i]);
        printf("\n");
}

single

- 하나의 스레드만 들어와서 작업

- 먼저 도착하는 스레드가 일함

- 다른 스레드는 싱글에 도착한 스레드가 작업 끝날때까지 대기(베리어)

single 예제

#include <stdio.h>
#include <omp.h>

int main()
{
        omp_set_num_threads(4);
#pragma omp parallel
{
        #pragma omp single
        {
                printf("hello world\n");
        }
} // pragma omp parallel
}

master

- single이랑 동일함

- 마스터 스래드에서만 실행함

- 다른 스레드들은 싱글과 달리 베리어가 없어 넘어감

master 예제

#include <stdio.h>
#include <omp.h>

int main()
{
        omp_set_num_threads(4);
#pragma omp parallel
{
        #pragma omp master
        {
                sleep(1);
                printf("hello world\n");
        }
        printf("tid = %d\n", omp_get_thread_num());
} // pragma omp parallel
}

2020-07-27

• 지난 시간에는 고유치와 고유 벡터에 대해서 간단히 복습 후 뉴턴 방법과 비선형 시스템에서의 해를 구하기 위한 비선형 최소 자승법에 대해서 살펴보고 여기서 근사해를 구하기 위한 가우스 뉴턴 방법과 레벤버그-마퀴트 방법에 대해서 살펴보면서 최적화 이론 학습을 마무리 할수 있었습니다.
• 이번 시간에는 그동안 학습한 공업 수학 이론과 최적화 이론, 수치 해석 등의 내용들을 활용하는 응용 분야중 하나인 영상처리에 대해서 학습을 시작하였습니다. 이전에 영상처리를 공부할때에는 이런 수학적 배경지식이 없이 학습을 진행하다보니 영상에는 어떤 종류가 있고, 관련 연산이 어떤게 있는지 정도만 파악하고 실제 내부 동작 과정에 대한 이해도가 많이 부족했었으나 이전 보다는 조금 더 깊이 들어갈수 있었습니다.
• 가장 처음으로는 컴퓨터 비전의 개요에 대해서 살펴보았습니다. 컴퓨터 비전이 무엇인지와 응용분야 그리고 처리과정에 대해서 정리하고, 이러한 컴퓨터 비전을 다루기 위한 배경 지식들이 어떤것들을 있는지 파악하였습니다. 또 컴퓨터 비전 어플리케이션을 구현하기 위한 설계과정 즉, 문제 파악, 자료 수집, 알고리즘 설계와 구현, 성능 평가 등 전반적인 내용과 컴퓨터 비전과 영상 처리, 컴퓨터 그래픽스 등 관련 응용분야와의 관계를 살펴볼수 있었습니다. 지난 시간에 학습할때에는 급한 마음에 개요를 학습할 여유가 없었지만 개요를 이해하고 시작하면서 어느 부분에 주의를 해야할지 어느정도 파악하게 되었습니다.
• 다음으로 히스토그램과 이진 영상에 대해서 학습하였습니다. 앞으로 다룰 영상은 컬러영상도 있지만 흑백인 명암영상 그리고, 0과 1로만 이루어진 이진 영상등이 있었습니다. 여기서 히스토그램이란 명암 영상에서 명암 정도를 2차원 그래프 상으로 나타낸 것이라 할수 있는데, 이후 특징 기술자나 히스토그램 역투영을 통한 특정 색상 영역 검출 등에 활용되는것들을 살펴보았습니다. 또 이진 영상은 임계치를 이용하여 이진화를 통해 얻을수 있었는대 최적의 임계치를 찾는 오츄 알고리즘이 대표적이었습니다.
• 이후 이러한 다양한 영상들을 처리하기 위해 어떠한 연산들이 있는지 파악하였습니다. 영상을 구성하는 점 하나하나에 대한 점연산과 커널(마스크)를 이용하여 일부 영역에 대해서 수행하는 영역 연산, 그리고 영상 전체적인 형태가 바뀌는 기하학적 연산이 있었으며, 특히 이러한 기하학적인 연산에 어떤 변환들이 존재하는지 정리하는 시간을 가졌습니다.
• 마지막으로 영상 연산에서 사용되는 연결 요소에 대해서 간단하게 살펴보았습니다. 연결 요소는 대표적으로 상하좌우를 다루는 4연결성과 대각선영엮가지 다루는 8연결 성이 있었습니다. 당연히 4연결성을 사용하는것이 계산량을 줄일수 있는 장점이 있으나 대각선에 대한영향을 반영하지 못하는 문제가 있었습니다. 이러한 연결 요소를 이용하여 범람 채움 알고리즘을 통해 영상 일부분을 채워나가는 과정을 알아보고 또한 번호판 검출 알고리즘에 사용되는 모폴로지 연산에 대해서 학습하였습니다. 모폴로지는 특정 마스크를 이용해 이진 영상을 팽창시키거나 침식시킬수 있었는데 잡음을 제거하거나 특정한 형태를 얻는대 유용함이 있었습니다.
• 오늘은 영상처리 관련 개념들을 위주로 전반적으로 간략히 살펴보았습니다. 영상 인식까지 가기위해서 살펴보아야할 내용들은 많으나, 한번에 완벽히 이해하기 보다는 지난번 보다 조금이라도 더 이해하기 위해 편하게 보고자 합니다. 다음 시간부터는 컴퓨터 해킹과 관련된 개념들과 바이너리 에디터로 부팅가능한 이미지를 만드는 과정에 대해서도 학습할 예정입니다.

중첩 스레드

- 루프 안에 루프가 나오는경우를 -> 중첩 루프문이라 함

- 스레드 안에 스레드가 생성되는 경우

 => 병렬 구문 안에 다시 병렬 구문 쓰기

중첩 스레드문 작성

- omp_set_nested(1); 중첩 스레드 기능 on 

 * 런타임 라이브러리 말고, 환경변수로도 지정가능 OMP_NESTED=TRUE(or 1)

- 중첩 스레드 기능 확인하기 : get_nested() -> 0은 꺼짐, 1은 켜짐

#include <stdio.h>
#include <omp.h>

int main()
{
        int tid;

        omp_set_nested(1);
        omp_set_num_threads(2);
#pragma omp parallel private(tid)
{
        tid = omp_get_thread_num();
        printf("thread id = %d\n", tid );
        if( tid == 1) {
                #pragma omp parallel private(tid)
                {
                        tid = omp_get_thread_num();
                        printf("\t thread id = %d\n", tid );
                }
        }
} // end #pragma omp parallel
}

중첩 스레드문 실행 결과

- 스레드 갯수 2개 설정하여 처음 2개 생성

- tid == 1인 경우 스레드 다시 생성 -> 1번 스레드 내부에서 2개 또 생성

- tid == 1 조건이 없는 경우 -> 1번 스레드, 2번 스래드 둘다 내부에서 2개 생성

더 많은 중첩 스레드

- 스레드 4개 생성, tid와 level private 처리

- tid가 2번인 경우 중첩 스레드 생성

- 중첩 스래드 내부 tid다시 private

- 이 중첩 스래드들의 조상은 2번 스레드(tid == 2 조건에 의해)

#include <stdio.h>
#include <omp.h>

int main()
{
        int tid, level;

        omp_set_nested(1);
        omp_set_num_threads(4);
#pragma omp parallel private(tid, level)
{
        tid = omp_get_thread_num();
        level = omp_get_level();
        printf("tid = %d level = %d\n", tid, level);
        if( tid == 2) {
                #pragma omp parallel private(tid) num_threads(tid+2)
                {
                        tid = omp_get_thread_num();
                        printf("\ttid = %d ancestor_thread_num(%d)=%d\n", tid, level, omp_get_ancestor_thread_num(level) );
                }
        }
} // end #pragma omp parallel
}

중첩 스레드문 데이터 범위

1. 스래드 갯수

- 바깥 스레드에서 y, tid만 private, 스래드 갯수는 4개

- 내부 스레드에서 x, tid가 private, 내부 스레드 갯수는 2개

2. 중첩 스래드 영역 x, y, z(shared)

- 중첩 스레드 영역 x = 10

- 중첩 스레드 tid = 0일때, 상위에서 y = 12 -> y++ -> y = 13이됨.

- 중첩 스레드 tid = 1일때, y = 13 -> y++ -> y= 14가 됨

- 중첩 스레드 상위에서 z = 22 -> 4개의 스레드가 중첩 스래드 2개씩 생성 총 8개

 => 22 ~ 30까지 z가 상승

3. 중첩 스레드 밖, 스래드 안

- z는 shared이므로 30으로 고정

- x = 1 -> x++을 스래드 4개 반복 -> x = 5가 출력

- y = 12 -> 중첩 스레드에서 2번 y++ -> y = 14로 출력

- tid = 0 ~3 까지 x = 5, y = 14, z = 30

4. 스래드 밖

- z는 shared로 30

- x는 4번 ++했으므로 5

- y는 스레드 구문에서 private이므로, 초기화 10 그대로

=> x = 5, y = 10, z = 30

#include <stdio.h>
#include <omp.h>

int main()
{
        int x=1, y=10, z=20, tid;

        omp_set_nested(1);
        omp_set_num_threads(4);
#pragma omp parallel private(y, tid)
{
        tid = omp_get_thread_num();
        x++;
        y = 12;
        z = 22;
        #pragma omp parallel num_threads(2) private(x,tid)
        {
                tid = omp_get_thread_num();
                x = 10;
                y++;
                z++;
                printf("\t tid=%d x=%d y=%d z=%d\n", tid, x, y, z);
        }
        printf("tid=%d x=%d y=%d z=%d\n", tid, x, y, z);
} // end #pragma omp parallel

        printf("x=%d y=%d z=%d\n", x, y, z);
}