카테고리 보관물: Programming

Back propgation에서의 전치행렬(transpose matrix) – 2편

1편이 너무 길어 져서 $\frac{\partial L}{\partial W} = X^T \cdot \frac{\partial L}{\partial Y}$ 에 대한 유도는 여기로 나누었다.

이제 $\frac{\partial Y}{\partial W}$ 를 보면, 얘들도 모두 matrix이니 $\frac {\partial Y}{\partial W}$ 는 다음과 같이 생겼다.

$\frac{\partial Y}{\partial W} = \begin{bmatrix}\frac{\partial Y}{\partial w_{1,1}} & \frac{\partial Y}{\partial w_{1,2}} & \frac{\partial Y}{\partial w_{1,3}} \\\\ \frac{\partial Y}{\partial w_{2,1}} & \frac{\partial Y}{\partial w_{2,2}} & \frac{\partial Y}{\partial w_{2,3}} \end{bmatrix}$

첫번째 원소인 $\frac{\partial Y}{\partial w_{1,1}}$ 을 구하기 위해 이전 처럼, W에 대해 Y로 편미분하면 다음과 같이된다.

$\frac{\partial Y}{\partial w_{1,1}}=\begin{bmatrix}x_{1,1} & 0 & 0 \\\\ x_{2,1} & 0 & 0\end{bmatrix} \\\\ \frac{\partial Y}{\partial w_{1,2}}=\begin{bmatrix}0 & x_{1,1} & 0 \\\\ 0 & x_{2,1} & 0\end{bmatrix} \\\\ \frac{\partial Y}{\partial w_{1,3}}=\begin{bmatrix}0 & 0 & x_{1,1} \\\\ 0 & 0 & x_{2,1}\end{bmatrix} \\\\ \frac{\partial Y}{\partial w_{2,1}}=\begin{bmatrix}x_{1,2} & 0 & 0 \\\\ x_{2,2} & 0 & 0\end{bmatrix} \\\\ \frac{\partial Y}{\partial w_{2,2}}=\begin{bmatrix}0 & x_{1,2} & 0 \\\\ 0 & x_{2,2} & 0\end{bmatrix} \\\\ \frac{\partial Y}{\partial w_{2,3}}=\begin{bmatrix}0 & 0 & x_{1,2} \\\\ 0 & 0 & x_{2,2}\end{bmatrix}$

Matrix W의 각 원소들 역시 scalar이므로 1편에서 X의 경우 처럼, 다음과 같이 나타낼 수 있다.

$\frac{\partial L}{\partial w_{1,1}} = \sum_{i=1}{N} \sum_{j=1}{M}\frac{\partial L}{\partial y_{i,j}} \cdot \frac{\partial y_{i,j}}{\partial w_{1,1}}$

$\frac{\partial L}{\partial w_{1,1}} = (\frac{\partial L}{\partial y_{1,1}} \times x_{1,1}) + (\frac{\partial L}{\partial y_{2,1}} \times x_{2,1}) \\\\ \frac{\partial L}{\partial w_{1,2}} = (\frac{\partial L}{\partial y_{1,2}} \times x_{1,1}) + (\frac{\partial L}{\partial y_{2,2}} \times x_{2,1}) \\\\ \frac{\partial L}{\partial w_{1,3}} = (\frac{\partial L}{\partial y_{1,3}} \times x_{1,1}) + (\frac{\partial L}{\partial y_{2,3}} \times x_{2,1}) \\\\ \frac{\partial L}{\partial w_{2,1}} = (\frac{\partial L}{\partial y_{1,1}} \times x_{1,2}) + (\frac{\partial L}{\partial y_{2,1}} \times x_{2,2}) \\\\ \frac{\partial L}{\partial w_{2,2}} = (\frac{\partial L}{\partial y_{1,2}} \times x_{1,2}) + (\frac{\partial L}{\partial y_{2,2}} \times x_{2,2}) \\\\ \frac{\partial L}{\partial w_{2,3}} = (\frac{\partial L}{\partial y_{1,3}} \times x_{1,2}) + (\frac{\partial L}{\partial y_{2,3}} \times x_{2,2})$

이것을 2X3인 matrix로 나타내면

$\frac{\partial L}{\partial W} = \begin{bmatrix}(\frac{\partial L}{\partial y_{1,1}} \times x_{1,1}) + (\frac{\partial L}{\partial y_{2,1}} \times x_{2,1}) & (\frac{\partial L}{\partial y_{1,2}} \times x_{1,1}) + (\frac{\partial L}{\partial y_{2,2}} \times x_{2,1}) & (\frac{\partial L}{\partial y_{1,3}} \times x_{1,1}) + (\frac{\partial L}{\partial y_{2,3}} \times x_{2,1}) \\\\ (\frac{\partial L}{\partial y_{1,1}} \times x_{1,2}) + (\frac{\partial L}{\partial y_{2,1}} \times x_{2,2}) & (\frac{\partial L}{\partial y_{1,2}} \times x_{1,2}) + (\frac{\partial L}{\partial y_{2,2}} \times x_{2,2}) & (\frac{\partial L}{\partial y_{1,3}} \times x_{1,2}) + (\frac{\partial L}{\partial y_{2,3}} \times x_{2,2}) \end{bmatrix}$

Matrix X와 W원소의 위치를 바꿔서 나타내면

$\frac{\partial L}{\partial W} = \begin{bmatrix}(x_{1,1} \times \frac{\partial L}{\partial y_{1,1}}) + (x_{2,1} \times \frac{\partial L}{\partial y_{2,1}}) & (x_{1,1} \times \frac{\partial L}{\partial y_{1,2}}) + (x_{2,1} \times \frac{\partial L}{\partial y_{2,2}}) & (x_{2,1} \times \frac{\partial L}{\partial y_{1,3}}) + (x_{1,1} \times \frac{\partial L}{\partial y_{2,3}}) \\\\ (x_{1,2} \times \frac{\partial L}{\partial y_{1,1}}) + (x_{2,2} \times \frac{\partial L}{\partial y_{2,1}}) & (x_{1,2} \times \frac{\partial L}{\partial y_{1,2}}) + (x_{2,2} \times \frac{\partial L}{\partial y_{2,2}}) & (x_{1,2} \times \frac{\partial L}{\partial y_{1,3}}) + (x_{2,2} \times \frac{\partial L}{\partial y_{2,3}}) \end{bmatrix}$

Matrix X와 Y로 구분하면

$\frac{\partial L}{\partial W} = \begin{bmatrix}x_{1,1} & x_{2,1} \\\\ x_{1,2} & x_{2,2}\end{bmatrix} \cdot \begin{bmatrix}\frac{\partial L}{\partial y_{1,1}} & \frac{\partial L}{\partial y_{1,2}} & \frac{\partial L}{\partial y_{1,3}} \\\\ \frac{\partial L}{\partial y_{2,1}} & \frac{\partial L}{\partial y_{2,2}} & \frac{\partial L}{\partial y_{2,3}}\end{bmatrix} = X^T \cdot \frac{\partial L}{\partial Y}$ 이 성립한다.

Back propgation에서의 전치행렬(transpose matrix) – 1편

3 댓글

실제로 전개해보면 다음 식이 도출됩니다([식 5.13]으로 이끄는 과정은 생략합니다).
– p172, 5.6.1 Affine 계층, 밑바닥부터 시작하는 딥러닝

아니! 그걸 생략하면 어떡해요!!

“밑바닥부터 시작하는 딥러닝”을 읽으면서 딥러닝의 개념을 잡는데 많은 도움을 받고 있지만 굳이 단점을 들자면 주요한 공식 들에 대해 설명하지 않고 그냥 넘어 가버리는 경우가 가끔 있다. 위에서 말하는 [식 5.13]은 back propagataion에서 입력에 대한 loss function의 영향과 weight에 대한 loss function의 영향을 계산하는 다음 식을 의미한다.

$\frac{\partial L}{\partial X} = \frac{\partial L}{\partial Y} \cdot W^T \\\\ \frac{\partial L}{\partial W} = X^Y \cdot \frac{\partial L}{\partial Y}$

이 식이 도대체 어떻게 유도된 것인지 이리 저리 찾다가 마침 이 부분을 자세히 설명해 주고 있는 미국 어느 대학(!)의 훌륭한 문서(Backpropagation for a Linear Layer, Justin Johnson, April 19, 2017)를 발견했다. 이 포스팅은 해당 문서에 대한 나름의 이해를 정리한 것이다.

밑밥 깔기

Matrix인 입력 X, Weight W가 있다고 할 때, 이 둘의 dot product인 Y는 다음과 같은 모습이다.

$X = \begin{bmatrix}x_{1,1} & x_{1,2}\\x_{2,1} & x_{2,2}\end{bmatrix} W = \begin{bmatrix}w_{1,1} & w_{1,2} & w_{1,3}\\w_{2,1} & w_{2,2} & w_{2,3}\end{bmatrix}$ $Y = X \cdot W = \begin{bmatrix}x_{1,1}w_{1,1} + x_{1,2}w_{2,1} & x_{1,1}w_{1,2} + x_{1,2}w_{2,2} & x_{1,1} w_{1,3} + x_{1,2}w_{2,3} \\\\ x_{2,1}w_{1,1} + x_{2,2}w_{2,1} & x_{2,1}w_{1,2} + x_{2,2}w_{2,2} & x_{2,1}w_{1,3} + x_{2,2}w_{2,3}\end{bmatrix}$

Back propagation을 통해 최종으로 구하고자 하는 것은 입력의 변화에 따른 loss function의 변화량 $\frac{\partial L}{\partial X}$ 과 Weight 변화에 따른 loss function의 변화량 $\frac{\partial L}{\partial W}$ 이다. 이것과 관련해 연쇄 법칙(chain rule)에 따라 이전 layer에서 전달 받은 $Y = X \cdot W$ 의 변화에 따른 loss function의 변화량인 $\frac{\partial L}{\partial Y}$ 를 고려하면 다음이 성립한다.

$\frac{\partial L}{\partial X} = \frac{\partial L}{\partial Y} \cdot \frac{\partial Y}{\partial X} \\\\ \frac{\partial L}{\partial W} = \frac{\partial L}{\partial Y} \cdot \frac{\partial Y}{\partial W}$

Y의 변화에 따른 Loss function의 변화 $\frac{\partial L}{\partial Y}$

여기에서 $\partial L$ 은 scalar 값 이고 $Y$ 는 matrix이므로 $\frac{\partial L}{\partial Y}$ 의 모습은 다음과 같다.

$\begin{bmatrix}\frac{\partial L}{\partial (x_{1,1}w_{1,1} + x_{1,2}w_{2,1})} & \frac {\partial L}{\partial (x_{1,1}w_{1,2} + x_{1,2}w_{2,2})} & \frac {\partial L}{\partial (x_{1,1} w_{1,3} + x_{1,2}w_{2,3})} \\\\ \frac{\partial L}{\partial (x_{2,1}w_{1,1} + x_{2,2}w_{2,1})} & \frac{\partial L}{\partial (x_{2,1}w_{1,2} + x_{2,2}w_{2,2})} & \frac{\partial L}{\partial (x_{2,1}w_{1,3} + x_{2,2}w_{2,3})}\end{bmatrix}$

복잡하니까 조금 간단히 다음과 같이 인덱스로 나타내자.

$\frac{\partial L}{\partial Y} = \begin{bmatrix}\frac{\partial L}{\partial y_{1,1}} & \frac {\partial L}{\partial y_{1,2}} & \frac {\partial L}{\partial y_{1,3}} \\\\ \frac{\partial L}{\partial y_{2,1}} & \frac{\partial L}{\partial y_{2,2}} & \frac{\partial L}{\partial y_{2,3}}\end{bmatrix}$

이제, $\frac{\partial Y}{\partial X}$ 와 $\frac{\partial Y}{\partial W}$ 가 남았다.

행렬 X의 원소들에 대한 행렬 Y의 편미분 $\frac{\partial Y}{\partial X}$

먼저 $\frac{\partial Y}{\partial X}$ 를 보면, X와 Y 모두 matrix이니 $\frac {\partial Y}{\partial X}$ 는 다음과 같이 생겼다.

$\frac{\partial Y}{\partial X} = \begin{bmatrix}\frac{\partial Y}{\partial x_{1,1}} & \frac{\partial Y}{\partial x_{1,2}} & \frac{\partial Y}{\partial x_{1,3}} \\\\ \frac{\partial Y}{\partial x_{2,1}} & \frac{\partial Y}{\partial x_{2,2}} & \frac{\partial Y}{\partial x_{2,3}} \end{bmatrix}$

각 원소들은 scalar 값인데 그 중 첫번째 원소인 $\frac{\partial Y}{\partial x_{1,1}}$ 를 구하기 위해 Y의 원소들을 $x_{1,1}$ 로 편미분 하면 다음과 같이 된다.

$\frac{\partial Y}{\partial x_{1,1}}=\begin{bmatrix}w_{1,1} & w_{1,2} & w_{1,3} \\\\ 0 & 0 & 0 \end{bmatrix}$

응? 갑자기 이건 뭐냐!

예를 들어 $y_{1,1}$ 에 있는 $x_{1,1}w_{1,1} + x_{1,2}w_{2,1}$ 를 $x_{1,1}$ 로 편미분하면 $w_{1,1}$ 가 되고, $x_{1,1}w_{1,2} + x_{1,2}w_{2,2}$ 에 대해서도 같은 방식으로 하면 $w_{1,2}$ 가 되는 식으로 Y의 모든 6개의 원소에 적용한 것이다. 이런 짓을 matrix X의 모든 원소인 $x_{1, 2}, x_{2,1}, x_{2,2}$ 에 대해서도 모두 구하면 다음과 같이 된다.

$\frac{\partial Y}{\partial x_{1,1}}=\begin{bmatrix}w_{1,1} & w_{1,2} & w_{1,3} \\\\ 0 & 0 & 0\end{bmatrix} \\\\ \frac{\partial Y}{\partial x_{1,2}}=\begin{bmatrix}w_{2,1} & w_{2,2} & w_{2,3} \\\\ 0 & 0 & 0 \end{bmatrix} \\\\ \frac{\partial Y}{\partial x_{2,1}}=\begin{bmatrix} 0 & 0 & 0 \\\\ w_{1,1} & w_{1,2} & w_{1,3} \end{bmatrix} \\\\ \frac{\partial Y}{\partial x_{2,2}}=\begin{bmatrix} 0 & 0 & 0 \\\\ w_{2,1} & w_{2,2} & w_{2,3} \end{bmatrix}$

행렬 X에 대한 scalar L의 편미분 $\frac {\partial L}{\partial X}$

$\frac{\partial Y}{\partial x_{1,1}}$ 은 matrix X를 구성하는 element인 scalar값이다. 위에서 말한것 처럼 연쇄법칙(Chain rule)에 의해 Y의 모든 원소들에 대하여 다음과 같이 나타낼 수 있다.

$\frac{\partial L}{\partial x_{1,1}} = \sum_{i=1}^{N} \sum_{j=1}^{M} \frac{\partial L}{\partial y_{i,j}} \cdot \frac{\partial y_{i,j}}{\partial x_{1,1}}$

Matrix X의 첫번째 원소는 ${\partial L}$ 를 matrix Y의 각 원소들로 나눈 값들에 Y의 각원소들을 X의 첫번째 원소로 편미분한 값들을 곱한 것을 모두 더한 것이다. 말이 드럽게 복잡해 보이지만, 예를들어, 첫번째 원소인 $\frac{\partial L}{\partial x_{1,1}}$ 의 값이 다음과 같이 계산된다는 뜻이다.

$\frac{\partial L}{\partial x_{1,1}} = (\frac{\partial L}{\partial y_{1,1}} \times \frac{\partial y_{1,1}}{\partial x_{1,1}}) + (\frac{\partial L}{\partial y_{1,2}} \times \frac{\partial y_{1,2}}{\partial x_{1,1}}) + (\frac{\partial L}{\partial y_{1,3}} \times \frac{\partial y_{1,3}}{\partial x_{1,1}}) + (\frac{\partial L}{\partial y_{2,1}} \times \frac{\partial y_{2,1}}{\partial x_{1,1}}) + (\frac{\partial L}{\partial y_{2,2}} \times \frac{\partial y_{2,2}}{\partial x_{1,1}}) + (\frac{\partial L}{\partial y_{2,3}} \times \frac{\partial y_{2,3}}{\partial x_{1,1}})$

이것도 뭐 딱히 깨끗해 보이진 않지만… 여튼, matrix Y의 각원소들에 대해 $x_{1,1}$ 로 편미분한 결과를 위 식에 적용해 보면 다음과 같이 된다.

같은 방법을 $\frac{\partial L}{\partial X}$ 의 모든 원소들에 적용하면

$\frac{\partial L}{\partial x_{1,1}} = (\frac{\partial L}{\partial y_{1,1}} \times w_{1,1}) + (\frac{\partial L}{\partial y_{1,2}} \times w_{1,2}) + (\frac{\partial L}{\partial y_{1,3}} \times w_{1,3}) \\\\ \frac{\partial L}{\partial x_{1,2}} = (\frac{\partial L}{\partial y_{1,1}} \times w_{2,1}) + (\frac{\partial L}{\partial y_{1,2}} \times w_{2,2}) + (\frac{\partial L}{\partial y_{1,3}} \times w_{2,3}) \\\\ \frac{\partial L}{\partial x_{2,1}} = (\frac{\partial L}{\partial y_{2,1}} \times w_{1,1}) + (\frac{\partial L}{\partial y_{3,2}} \times w_{1,2}) + (\frac{\partial L}{\partial y_{3,3}} \times w_{1,3}) \\\\ \frac{\partial L}{\partial x_{2,2}} = (\frac{\partial L}{\partial y_{2,1}} \times w_{2,1}) + (\frac{\partial L}{\partial y_{3,2}} \times w_{2,2}) + (\frac{\partial L}{\partial y_{3,3}} \times w_{2,3})$

이것을 matrix의 형태로 나타내면

$\frac{\partial L}{\partial X}=\begin{bmatrix}(\frac{\partial L}{\partial y_{1,1}} \times w_{1,1}) + (\frac{\partial L}{\partial y_{1,2}} \times w_{1,2}) + (\frac{\partial L}{\partial y_{1,3}} \times w_{1,3}) & (\frac{\partial L}{\partial y_{1,1}} \times w_{2,1}) + (\frac{\partial L}{\partial y_{1,2}} \times w_{2,2}) + (\frac{\partial L}{\partial y_{1,3}} \times w_{2,3}) \\\\ (\frac{\partial L}{\partial y_{2,1}} \times w_{1,1}) + (\frac{\partial L}{\partial y_{3,2}} \times w_{1,2}) + (\frac{\partial L}{\partial y_{3,3}} \times w_{1,3}) & (\frac{\partial L}{\partial y_{2,1}} \times w_{2,1}) + (\frac{\partial L}{\partial y_{3,2}} \times w_{2,2}) + (\frac{\partial L}{\partial y_{3,3}} \times w_{2,3})\end{bmatrix}$

Matrix Y와 W를 구분해 보면

$\frac{\partial L}{\partial X}=\begin{bmatrix}\frac{\partial L}{\partial y_{1,1}} & \frac{\partial L}{\partial y_{1,2}} & \frac{\partial L}{\partial y_{1,3}} \\\\ \frac{\partial L}{\partial y_{2,1}} & \frac{\partial L}{\partial y_{2,2}} & \frac{\partial L}{\partial y_{2,3}}\end{bmatrix} \cdot \begin{bmatrix} w_{1,1} & w_{2,1} \\\\ w_{1,2} & w_{2,2} \\\\ w_{1,3} & w_{2,3}\end{bmatrix}$

Weight matrix W의 전치행렬(transpose matrix)를 곱하는 것이 되므로,

$\frac{\partial Y}{\partial X}=\frac{\partial L}{\partial Y} \cdot W^T$ 이 성립한다.

Weight에 대한 loss function의 변화인 $\frac{\partial L}{\partial W} = X^T \cdot \frac{\partial L}{\partial Y}$ 도 기본적으로 같은 방법으로 유도 되는데 너무 길어져서 2편에서 간단히 다루도록 한다.

AWS Lightsail에 둥지 틀기

WordPress hosting은 더 비싸다

대안으로 생각한 것은 1) wordpress.com hosting과 2) AWS Lightsail이었는데, 발견한 한 가지 놀.라.운. 사실은 WordPress hosting에서 플러그인을 설차하려면 한달에 $25 짜리 business plan 이상을 계약해야 한다는 것이다. 한달에 $25라니!!! 멋 모르고 카드 결재를 하고 이리저리 플러그인 설치를 시도하다가 아래의 표를 발견하고는 미련 없이 ‘refund’ 버튼을 눌렀다.

AWS Lightsail은 한 달간 무료 시험기간을 주기 때문에 Siteground 계정이 종료하기 전에 미리 설치를 마쳤다. 인스턴스 리전을 한국으로 할까 하다가 이전 Siteground와 같은 위치인 싱가포르로 선택했고 WordPress의 export/import 기능 덕에 마이그레이션은 수월하게 진행되었다. Domain name은 호스팅 업체와 같은 곳으로 이전하는게 좋다고 해서 AWS Route 53으로 이전 및 1년 연기 등록을 했는데 상위 도메인에 따라 다르지만 .com의 경우 $13.2(세금포함)가 소요된다. 어라? 그러고 보니 Siteground에서 도메인을 연장하는 서비스는 $15.95였는데? 이눔 시키들…

도메인 이전과 새로운 IP 연결

도메인 이전을 요청하니 이전 관리자였던 Siteground에서 확인 메일이 왔고, 수락한 이후에는 하루 후에 AWS로 도메인이 이전되었다. 그 후에는 Lightsail의 네트워킹 탭에서 고정 IP와 DNS 영역을 생성해서 A 레코드를 추가하고 IP와 도메인 이름을 연결 시켜 주었다.

그리고 나서 한참을 DNS가 업데이트 되기를 기다렸다. nslookup은 여전히 예전 IP를 보여줬지만 48시간 까지 걸릴 수 있다는 말에 이틀정도를 기다렸는데도 IP가 업데이트 되지 않았다. AWS Route 53에 가보니 ‘registered domains > [domain name]’ 아래에 Name Servers 항목이 있는데 혹시 이것 때문인가 싶어서 고정 IP를 만들때 나왔던 네임서버 목록으로 업데이트를 해주었다. 그리고 나서 잠시 후 드디어 새로운 IP로 접속되었다!

계속 예전 IP로 돌아가는 도메인 문제와 해결

기쁜 마음으로 꿀잠에 들었는데 다음날 아침에 보니 Jetpack에서 서버연결 붙었다가 끊어졌다가 했다는 연락이 와 있었다. 혹시나 싶어서 서버를 재부팅 해봤더니 재부팅하는 순간 잠깐 IP가 새 것으로 붙었다가 다시 예전 IP로 돌아가는게 보였다. “그니까 누가 AWS가 알고 있는 것과 다른 예전 정보를 자꾸 준다는 거지…” 혹시나 하는 마음에 Siteground의 cPannel > Advanced DNS zone editor에 들어가 봤더니 역시나 얘가 예전 주소를 꼭 쥐고 있었다. 예전 사업자의 도메인 서버를 AWS 고정 IP로 수정해 주고 났더니 Jetpack이 사이트 살아났다고 축하한댄다. 다행히 그 후로는 다시 끊어지는 일은 없었다.

도메인 관리자를 변경하고 새로운 IP를 연결 했으니 이전 네임 서버에서는 자동으로 놔 주겠거니 하고 잘 못 생각하고 있었던게 문제 였던듯 싶다.

Travis CI 설정과 docker image 사용

삽질1: Travis CI의 Ubuntu이용

빌드와 Google test를 이용한 unit test만 할 것이니까 OS를 크게 타지 않을테니 기본으로 제공되는 Ubuntu 환경에 필요한 도구들만 설치 하면 가장 빠르지 않을까?

일견 타당해 보이기는 하지만 문제는 의존성이다. Pre-compile된 Google test를 download 받는다 해도, 2019년 1월 현재 아직 Travis CI에서 제공하는 Ubuntu의 가장 최신 버전은 Xenial이다. CMake version이 안맞아서 최신버전으로 설치하고 Intel LibVA, Intel MediaSDK등의 의존 package들을 컴파일한 후 빌드를 하고 unittest를 하도록 하는데 14분이 넘게 걸렸다. 다음은 사용한 .travis.yml file이다.

language: cpp 

compiler:  - gcc 

dist: xenial 

env:   
  global:    
- EA_INSTALL_PREFIX=${TRAVIS_BUILD_DIR}/local    
- PATH=${EA_INSTALL_PREFIX}/bin:$PATH before_install:  
- mkdir -p ${TRAVIS_BUILD_DIR}/local  
- sudo apt-get install curl wget autoconf libtool libdrm-dev \
libboost-all-dev libgstreamer1.0-0 libasound-dev \
libgles2-mesa-dev gstreamer1.0-plugins-base \
gstreamer1.0-plugins-good gstreamer1.0-plugins-bad \
gstreamer1.0-plugins-ugly gstreamer1.0-libav gstreamer1.0-doc \
gstreamer1.0-tools gstreamer1.0-x gstreamer1.0-alsa \
gstreamer1.0-pulseaudio
- cd ${TRAVIS_BUILD_DIR}&& \
wget https://github.com/Kitware/CMake/releases/download/v3.13.2\
/cmake-3.13.2.tar.gz \
&& tar xvf cmake-3.13.2.tar.gz&&cd cmake-3.13.2&&./configure --\
prefix=${EA_INSTALL_PREFIX}&&make&&make install  
- cd ${TRAVIS_BUILD_DIR}&& \
wget https://github.com/intel/libva/archive/2.3.0.tar.gz&&\
tar xvf 2.3.0.tar.gz \
&&cd libva-2.3.0&&./autogen.sh&&./configure --\
prefix=${EA_INSTALL_PREFIX}&&make&&make install  
- cd ${TRAVIS_BUILD_DIR}&& \
wget https://github.com/Intel-Media-SDK/MediaSDK/archive/\
intel-mediasdk-18.3.1.tar.gz \
&& tar xvf intel-mediasdk-18.3.1.tar.gz&&\
cd MediaSDK-intel-mediasdk-18.3.1/&& \
cmake -DCMAKE_INSTALL_PREFIX=/usr -DENABLE_OPENCL=OFF -DBUILD_SAMPLES=OFF .&&make&&\
make install 

script:  
- cd ${TRAVIS_BUILD_DIR} && \
cmake . && make && make install && test/ea_test

삽질2: Clear Linux docker image 사용

시간만 오래 안 걸렸어도 기본 Ubuntu OS로 어떻게든 해보는 건데, 14분이면 시간이 너무 오래 걸린다. 이왕 시간이 오래 걸리는 거라면 타겟인 Clear Linux docker image를 사용해보자.

Clear Linux docker image를 생성하기 위한 dockerfile을 다음과 같이 작성해준 다음

FROM clearlinux 
RUN clrtrust generate 
RUN swupd bundle-add software-defined-cockpit-dev

.travis.yml file을 다음과 같이 선언해 준다.

language: cpp
services:
 - docker
before_install:
 - docker build -t clearlinux_ea .
 - docker run -d -v ${TRAVIS_BUILD_DIR}:/src clearlinux_ea /bin/sh -c "cd /src;cmake .;make;make install"

script:	 	 
 - docker run -d -v ${TRAVIS_BUILD_DIR}:/src clearlinux_ea /bin/sh -c "cd /src;test/ea_test"

총 소요된 시간은 17분 41초 그 중에 docker 설정하는데 걸린 시간만 16분이 넘는다. 나머지 시간에 unit test. 대부분의 시간이 docker를 빌드 하고 설정하는데 사용 되고 있었다.

삽질3: 만들어 둔 Docker image 다운로드

빌드하는데 시간이 오래 걸린다면 이미 만들어 둔 docker image를 저장소에 넣어두고 pull해서 사용하면 좀 빠르지 않을까? Docker 빌드 vs Docker 다운로드.

이미 빌드 한 docker image를 공개 저장소인 docker hub에 넣어두고 Travis CI에서 pull하도록 변경하면 시간은 8분정도로 줄어든다.

language: cpp

services:
 - docker
	
before_install:
 - docker pull litcoder/clearlinux_ea
 - docker run -v ${TRAVIS_BUILD_DIR}:/src litcoder/clearlinux_ea /bin/sh -c "cd /src;cmake .;make;make install;"
	
script:
 - docker run -v ${TRAVIS_BUILD_DIR}:/src litcoder/clearlinux_ea /bin/sh -c "cd /src;test/ea_test"

흠.. 일단은 이걸로.

결론

Travis CI에서 제공되는 연산 성능은 매우 떨어져서 컴파일이나 도커 빌드를 효율적으로 수행하지 못한다. 반면, 이미 만들어진 이미지의 다운로드는 상대적으로 빠르게 수행 할 수 있다. Travis CI에서 Docker를 이용한 테스트 환경을 구성하고자 한다면 미리 만들어 둔 이미지를 Docker Hub에 올려두고 CI script에서 pull 해서 사용하는 방법이 가장 고려해 볼 만한 선택이다.

Heap tree 만들기

예제

임의의 정렬되지 않은 배열 { 2, 7, 5, 4, 1, 6, 10, 3, 9, 8}을 예로들어 보자. 10개의 node를 가지는 tree를 배열로 구현 할 때, 부모 node들의 index는 소숫점_버림(N/2) – 1로 계산할 수 있다. 따라서 10개의 node를 가지는 이 tree의 부모 node들의 위치는 [0], [1], [2], [3], [4]이다. (C/C++로 구현 할때는 N/2한 값을 그냥 int형 변수에 넣으면 된다)

각 부모 node들과 자식 node들을 subtree라고 하면 이 예제는 다음과 같이 5개의 subtree들로 구분될 수 있다.

Heapify – Subtree A

부모인 4번째 index의 값과 하나 밖에 없는 자식인 9번째 index의 값을 비교한다. 자식의 값이 더 크므로 부모와 swap()한다.

Heapify – Subtree B

부모인 3번째 index와 왼쪽 자식인 7번째, 오른쪽 자식인 8번째를 비교해서 가장 큰 오른쪽 자식과 부모 node를 swap()한다.

Heapify – Subtree C

오른쪽 자식인 index 6번과 부모인 index 2번을 교체한다.

Heapify – Subtree D

1번 index의 왼쪽 자식이 더 크므로 부모와 swap()한다.

Heapify – Subtree E

2번 index의 값이 더 커서 부모인 0번 index와 swap()하고 보니 2번 index를 부모로 하는 subtree가 더이상 max heap이 아니게 된다.

그래서 다시 한번 heapify()를 호출해서 max heap을 만든다.

Code

/*
  Name: buildHeapTree
  Desc.: Makes sure all sub-trees to be max heapified.
  Args.:
    - arr : Pointer to array to be sorted.
    - arrSize : Size of the array.
*/
static void buildHeapTree(int* arr, int arrSize)
{
    int parentIdx = (arrSize / 2) - 1;
    int arrayLastIdx = arrSize - 1;
 
    for(; parentIdx >= 0; parentIdx--)
    {
        maxHeapify(arr, arrayLastIdx, parentIdx);
    }
}

/*
  Name: swap
  Desc.: Exchanges two elements of the array 'arr' that two given indices indicates.
  Args.:
    - arr: Pointer to array to be sorted.
    - idx1, idx2 : Two indices to be swapped.
*/
static void swap(int* arr, int idx1, int idx2)
{
    int t = std::move(arr[idx1]);
    arr[idx1] = std::move(arr[idx2]);
    arr[idx2] = std::move(t);
}

 
/*
  Name: maxHeapify
  Desc.: Makes given tree and it's sub-trees to be max heap trees.
  Args:
    - arr : Pointer to array to be sorted.
    - arrayLastIdx : Last index of the given array.
    - parentIdx : Index of the parent node of the tree.
*/
static void maxHeapify(int* arr, int arrayLastIdx, int parentIdx)
{
    int lcIdx = (parentIdx * 2) + 1;  // Index for left child node.
    int rcIdx = lcIdx + 1;            // Index for right child node.
    int biggerChildIdx = lcIdx;       // Index for child that has bigger value.
 
    // Stop recursion if left child index exceeds last index of the array.
    if(lcIdx > arrayLastIdx)
        return;
 
    // Left child would be the only one if there's no right child. 
    if(rcIdx > arrayLastIdx)
        biggerChildIdx = lcIdx;
    else   // Which of left/right is bigger if both are exits?
        biggerChildIdx = (arr[lcIdx] < arr[rcIdx]) ? rcIdx : lcIdx;
 
    // Swap and heapify if child is bigger than parent.
    if(arr[parentIdx] < arr[biggerChildIdx])
    {
        swap(arr, parentIdx, biggerChildIdx);
        maxHeapify(arr, arrayLastIdx, biggerChildIdx);
    }
 
    return;
}

Litcoder

기억은 짧고 불완전 하다