Taeguk's Blog

결론부터 말하면, OpenMP for loop scheduling 방법으로서 제공되는 것 중 하나인 static이 이상하게 구현된 것 같다. (거지같다) 서로 처리 시간이 같은 task들이 있을 때 이 것들을 scheduling할 때는 static이 제일 빨라야 정상이다. 근데 내가 실험을 하는데 guided가 더 빨라서, 그것도 월등히 빨라서 정말 혼란이 왔었다. static의 chunk size가 1이여서 그런가? 하고 chunk size를 늘리며 실험했더니 빠르게 작동했다. 사실 chunk size가 작으면, cache miss가 뜰 확률이 높아져서 성능이 하락하기 때문에 guided가 더 빠를 수 있다. 그러나, 좀 심각하게 느렸다. 그래서 내가 직접 static을 구현해서 실험을 다시 해보니까... 이론대로 나온다. 그래 my static처럼 결과가 나와야 정상이지... chunk size가 최대일 때는 당연히 guided보다 빨라야하고, chunk size가 최소인 1일 때는 cache miss를 고려해서 guided보다 약간 느려야 이론대로 잘 나오는 것이다. 그런데, OpenMP static은 정말 '비상식적인' 결과를 보여주고 있다... 흠.... 뭐 사실 이 case 하나만 가지고 OpenMP의 static은 쓰레기다!!! 라고 단정지을 수 없지만... 아무래도 실망스러움을 감출수가 없다....ㅠㅠ https://github.com/taeguk/dist-prog-assignment/issues/4   에 가면 좀 더 자세한 나의 한풀이를 들을 수 있다. 어쨌든, 대체 OpenMP의 static이 구체적으로 어떻게 구현되었는지 알아보고 싶다... 나중에 시간되면 binary나 까서 분석해볼까 한다... 참고로 실험에 사용한 OpenMP는 3.0버전이다.

요즘 학교 고급소프트웨어실습 (이하 고소실) 이라는 과목에서 cache friendly code를 작성하는 것을 해보고 있다. 평소에도 memory access pattern에 따라 성능 차이가 극심하게 날 수 있고 어쩌구~저쩌구~.... 개념적으로는 알고 있었지만 실제로 cache를 고려하면서 code를 작성하고, 간단한 코드를 memory access pattern을 다양하게 바꿔보면서 성능을 실험해본 것은 처음이다. 실제로 실험해보니 matrix multiplication 함수를 그냥 짰을 때랑 cache friendly하게 짰을 때 성능 차이가 극심하게 났다. (정확하게 얼마나 났는지는 기억이 안 나는데 아마 열 몇 배 빨랐던 것 같다. 기억이 틀릴 수 도 있다. ㅠㅜ 어쨌든 많이 빨라졌다..) 뭐, cache friendly code는 CPU뿐만 아니라 GPU에서도 상당히 중요하다. CUDA Programming에서, cache friendly 하지 않은 어떤 코드를 800ms정도 걸리는 걸 cache를 고려해서 수정을 하니까 200ms정도로 최적화를 시킬 수 있었다. 물론 GPU는 SIMD구조고, block, warp등 CPU와는 상당히 다른 아키텍처를 가지고 있기 때문에 CPU와는 cache friendly code를 짜는 법이 좀 차이가 났다. 어쨌든 이렇듯 cache friendly code를 작성하는 것은 상당히 중요하다. memory access pattern을 계속 고려하면서 최적화를 하는 작업은 상당히 노가다처럼 느껴지기도 하지만 참 재밌다.. 최적화쪽으로 공부를 한 번 해볼까하는 생각도 든다.. 또 한편으로 과연 그러나 이런 최적화기법들을 얼마나 실제에 적용할 수 있을 지에 대한 생각도 든다. 다른 모듈과 종속성이 별로 없는 특정 모듈이나 알고리즘들은 적용할 만하겠지만, 특정 자료구조가 예를 들어 다양한 곳에서 쓰이는 경우, 이 자료구조를 특정 memory access pattern을 가정해서 최적화하거나 하는게 ...

Story 01. 프로그래머가 프로세서도 알아야 해요? - 병렬 프로그래밍의 중요성이 대두 되면서 하드웨어를 exploit해야 할 필요성이 커짐. - 소프트웨어 개발에 쓰일 수 있는 다양한 알고리즘 / 아이디어를 습득할 수 있음. Story 02. 프로세서의 언어 : 명령어 집합 구조 (ISA) CISC의 탄생  - 범용 목적 마이크로 프로세서가 처음 나온 1970년대에는 컴파일러의 도움이 크지 못했다. -> 다양한 기능을 제공  - 그리고 메모리가 비싸고 부족했다. -> 짧은(가변) 길이의 명령어 형태  - 그래서 최초의 ISA는 CISC형태를 띔. RISC의 탄생  - CISC의 명령어들 중 자주 사용되는 것은 일부분에 불과했다.  - 제한되고 간단한 형태의 명령어들만 제공함으로서 더 저렴하다. 혹은 다른 것에 트랜지스터들을 투자 가능.  - Make Common Case Fast RISC vs CISC  - RISC는 하드웨어의 복잡함을 컴파일러나 프로그래머에 넘겼다. (레지스터 수가 많고 하드웨어 구현이 더 간단, 슈퍼컴퓨터에 적합)  - CISC는 프로그램의 복잡함을 하드웨어가 도맡아 처리한다.  - 이제는 RISC와 CISC경계가 모호해졌다. CISC인 x86의 경우 CISC 명령어를 내부적으로 micro-op으로 쪼개서 처리한다. (겉은 CISC, 속은 RISC) Story 03. 프로세서의 기본 부품과 개념들 마이크로 아키텍처 : 마이크로 프로세서 하나를 만드는 데 필요한 알고리즘 및 회로 수준의 구조를 자세히 정의 한 것. Story 04. 암달의 법칙과 프로세서의 성능 지표 성능 향상을 위해 해야 할 일 - 명령어 개수 N을 줄이자    * 컴파일러 최적화 : Common Sub-expression Elimination, Constant Propagation, Dead Store El...

이번에 하고 있는 프로젝트에서 분산시스템을 구현하는 데 zeromq를 사용하게 되었다. 그래서 zeromq의 기본적이지만 헷갈릴 수 있는 내용들을 한 번 정리해보았다. 공식 guide document는 http://zguide.zeromq.org/ 이다. 여기에 쓴 내용들은 공식 guide에 설명된 내용을 포함해서 내가 추가적으로 여러가지 실험을 통해 알아낸 것들을 포함하고 있다. 그리고 내 개인적인 생각들도 포함되어 있다. Valid Combination PUB and SUB REQ and REP REQ and ROUTER (take care, REQ inserts an extra null frame) DEALER and REP (take care, REP assumes a null frame) DEALER and ROUTER DEALER and DEALER ROUTER and ROUTER PUSH and PULL PAIR and PAIR 출처) zquide.zeromq.org Asynchronous Request & Response REQ, REP, PAIR같은 애들은 비동기 request-response가 불가능하다. 그냥 패킷 하나 주고 하나 받고 하나 주고 하나 받고 이렇게 동기적으로 해야한다. 그래서 비동기 req-res를 하려면 ROUTER나 DEALER를 사용해야한다. DEALER나 ROUTER의 특징은 아래쪽에 써놧으니 읽어보면 된다. 만약 비동기적인 PAIR to PAIR 를 구현하려면 DEALER to DEALER 를 사용하면 된다. 만약 비동기적인 REQ to REP 를 구현하려면 DEALER to ROUTER 를 사용하면 된다. 근데 DEALER나 ROUTER는 이름에서 알 수 있듯이 각각 연상되는 활용처가 있는 법인데, 단순히 비동기 req/res를 하기 위해서 이걸 사용해야한다는 점이 네이밍 측면에서 좀 안좋게 느껴진다. ASYNC_REQ 뭐 이런 네이밍의 socket ty...

NN(Neural Network) K(X) = sigmoid(XW₁ + b1) H(X) = sigmoid(K(X)W₂ + b2) Back propagation 딥 네트워크에서 나온 결과물에서 나온 error(또는 cost)를 역으로 전파시키면서 weight들에게 그 것을 반영시키는 것. 미분과 chain rule을 이용하여 각 weight가 결과에 미치는 영향(변화량)을 계산하여 그 것만큼 반영시킨다. (Back propagation) Geoffrey Hinton's summary of findings up to today 1. Our labeled datasets were thousands of times too small. 2. Our computers were millions of times too slow. 3. We initialized the weights in a stupid way. 4. We used the wrong type of non-linearity. (Activate Functions) Vanishing gradient (NN winter2 : 1986-2006) 깊은 NN일 경우, back propagation이 진행되면서 점점 초반 부분의 layer들의 영향력이 작아지는 문제.  sigmoid를 사용할 경우 이 문제가 크게 발생한다. ReLU등의 다른 activation functions을 사용하면서 어느정도 해결할 수 있다. Activation Functions 종류 : Sigmoid, tanh, ReLU, Leaky ReLU, Maxout, ELU, ... ReLU (Rectified Linear Unit) = max(H(x), 0) 비교 : https://hunkim.github.io/ml/lec10.pdf 24페이지 Initializing weights wisely - Not all 0's - challenging issue 비교 : https:/...

Supervised Learning : learning with labeled data Unsupervised learning : learning with un-labeled data 즉, supervised는 이미 정답이 있는 문제들을 가지고 학습시키는 것을 말하고, unsupervised는 정답(라벨)을 지정해 주지 않은 문제들(데이터들)을 가지고 학습하는 것을 말한다. Supervised Learning의 종류 regression : 연속적인 결과에 대한 예측 binary classification : 2개의 결과 중에서 예측 multi-label classification : 여러가지의 결과들중에서 예측. Linear Regression Linear한 모델로서 regression을 하는 것. H(x) = Wx + b Cost function 우리의 모델에서 나온 예측값과 실제 결과값의 차이를 계산하는 함수. cost = 1/m *  Σ {H(x) - y} (m = 데이터 개수,  Σ  : 총 m개의 x에 대해 괄호안의 수식값들을 합하는 함수.) Gradient descent algorithm cost function을 minimize하는 algorithm중 하나. W := W - αΔcost(W) (α = learning rate,  Δ = W에 대한 미분 ) convex function에만 적용할 수 있다. Multi-variable Linear Regression 변수가 여러개인 Linear Regression H(x) = w1*x1 + w2 * x2 + ... + b = (행렬의 곱으로 표현) W =  [ b  w1  w2  ... ] X =  [ 1  x1  x2  ... ] H(X) = transpose(W) * X Sigmoid g(z) = 1/(1+e^(-z)) (0, 1) 범위로 output을 낸다. Logistic Binary Cla...

Chapter 9. 그 밖의 이야기들 (항목 53 ~ 55) 드디어 마지막 Chapter입니다!! 씬난다~ 씬나@@ 항목 53. 컴파일러 경고를 지나치지 말자. [이것만은 잊지 말자] - 컴파일러 경고를 쉽게 지나치지 맙시다. 여러분의 컴파일러에서 지원하는 최고 경고 수준에도 경고 메시지를 내지 않고 컴파일되는 코드를 만드는 쪽에 전력을 다 하십시오. - 컴파일러 경고에 너무 기대는 인생을 지양하십시오. 컴파일러마다 트집을 잡고 경고를 내는 부분들이 천차만별이기 때문입니다. 지금 코드를 다른 컴파일러로 이식하면서 여러분이 익숙해져 있는 경고 메시지가 온 데 간 데 없이 사라질 수도 있습니다. 항목 54. TR1을 포함한 표준 라이브러리 구성요소와 편안한 친구가 되자. TR1을 얘기하기에는 요즘 시대가 너무 흘렀죠? ㅎㅎ 그래서 제가 한번 항목을 수정해보겠습니다. Modern C++은 선택이 아니라 필수다! 항목 55. 갓 부스트! 부스트를 늘 여러분 가까이에! 갓 부-스트! 부스트 차냥해! 포스팅 거저먹는 마지막 췝터! 씬난다 씬나 지금까지 포스팅에서 사용했던 코드들은 Github에 올려놨습니다!! ( https://github.com/taeguk/Effective-Cpp-Series )

Chapter 8. new와 delete를 내 맘대로 (항목 49 ~ 52) 항목 49. new 처리자의 동작 원리를 제대로 이해하자. [new와 delete 키워드] new/new[] 키워드 : (알맞는 operator new 호출 -> 생성자 호출) + 알파 (operator new와 생성자를 적절하게 호출하고 메타데이터등을 저장하고 관리하는 코드. 여기서 메타데이터는 new[]할때 객체의 갯수등을 의미.) delete/delete[] 키워드 : 위와 비슷한 맥락. [new 처리자 - new handler] operator new의 역할 : 필요한 메모리를 적절하게 할당해서 반환해주는 역할. new 처리자 : operator new가 메모리를 할당하는데 실패했을 때 호출되는 함수. [new 처리자가 해야하는 동작 (아래중 하나를 해야한다.)] - 사용할 수 있는 메모리를 더 많이 확보한다. - 다른 new 처리자를 설치한다. - new 처리자의 설치를 제거한다. - 예외를 던진다. - 복귀하지 않는다. (abort나 exit을 호출) #include <new> // RAII방식으로 new handler을 관리하는 클래스 class NewHandlerRAII { public: explicit NewHandlerRAII(std::new_handler nh) noexcept { old = std::set_new_handler(nh); } ~NewHandlerRAII() noexcept { std::set_new_handler(old); } NewHandlerRAII(const NewHandlerRAII&) = delete; NewHandlerRAII& operator=(const NewHandlerRAII&) = delete; private: std::new_handler old; }; // class별로 new...

Chapter 7. 템플릿과 일반화 프로그래밍 (항목 41~ 48) 항목 41. 템플릿 프로그래밍의 천릿길도 암시적 인터페이스와 컴파일 타임 다형성부터. [이것만은 잊지 말자] - 클래스 및 템플릿은 모두 인터페이스와 다형성을 지원합니다. - 클래스의 경우, 인터페이스는 명시적이며 함수의 시그너처를 중심으로 구성되어 있습니다. 다형성은 프로그램 실행 중에 가상 함수를 통해 나타납니다. - 템플릿 매개변수의 경우, 인터페이스는 암시적이며 유효 표현식에 기반을 두어 구성됩니다. 다형성은 컴파일 중에 템플릿 인스턴스화와 함수 오버로딩 모호성 해결을 통해 나타납니다. 항목 42. typename의 두 가지 의미를 제대로 파악하자. // 중첩 의존 이름은 기본적으로 타입이 아니라고 가정된다. // 중첩 의존 이름이 타입임을 알려주기 위해서는 typename 키워드를 사용해야한다. template <class T> void example(void) { int a; // 비의존 이름(non-dependent name) T b; // 의존 이름(dependent name) auto c = T::variable; // 중첩 의존 이름(nested dependent name) typename T::type d; // 중첩 의존 타입 이름(nested dependent type name) } // typename은 중첩 의존 이름을 식별하는 데에만 사용할 수 있다. template <class T> void func(const T& obj); // typename 쓰면 안 됨. // 중첩 의존 이름이 '문맥상' 타입일 수 밖에 없는 경우에는 typename을 쓰면 안된다. template <class T> class Derived :public Base<T>::musttype { Derived(int val) : Base<T...

Chapter 6. 상속, 그리고 객체 지향 설계 (항목 32~40) 항목 32. public 상속 모형은 반드시 "is-a(...는 ...의 일종이다)"를 따르도록 만들자. 상속 관계를 설계할 때 자연어 혹은 직관을 따르는 경우가 많다. 하지만 가끔 그것이 엄밀하지 못해서 문제가 생길 때가 있다. 따라서 public 상속을 할 때 is-a관계가 성립하는 지 철저히 따져봐야한다. 그리고 개인적으로 클래스 설계에 있어서 직관과 논리가 일치할 수 있도록 설계하는 게 정말 중요하다고 생각한다. [이것만은 잊지 말자] - public 상속의 의미는 is-a입니다. 기본 클래스에 적용되는 모든 것들이 파생 클래스에 그대로 적용되어야 합니다. 왜냐하면 모든 파생 클래스 객체는 기본 클래스 객체의 일종이기 때문입니다. 항목 33. 상속된 이름을 숨기는 일은 피하자. // using 선언을 이용한 방법. // public 상속시, 가려진 이름을 볼 수 있게 하기 위해 사용. namespace using_declaration { class Base { public: void f() {} void f(int x) {} }; class Derived : public Base { public: using Base::f; // this statement must be public. void f(int x, int y) {} }; } // forwarding function을 이용한 방법. // private 상속시, 가려진 이름을 가진 것들중 일부분만을 볼 수 있게 하기 위해 사용. namespace forwarding_function { class Base { public: void f() {} void f(int x) {} }; class Derived : private Base { ...

Chapter 5. 구현 (항목 26~31) 항목 26. 변수 정의는 늦출 수 있는 데까지 늦추는 근성을 발휘하자. 변수를 함수 처음에 다 정의할 때가 있다. 하지만 이러면 함수 내부에서 분기가 됨에 따라 특정 변수를 사용하지 않을 수 도 있기때문에 비효율적이다. 그래서 변수 정의도 효율을 고려하여 최적의 위치에 해야한다. // 방법 1 // 생성자 1번 + 소멸자 1번 + 대입 n번 for (Data data, int i = 0; i < n; ++i) { data = func(i); } // 방법 2 // 생성자 n번 + 소멸자 n번 for (int i = 0; i < n; ++i) { Data data = func(i); } // 방법 1 if cost(대입) > cost(생성자 + 소멸자), // 방법 2 otherwise. [이것만은 잊지 말자] - 변수 정의는 늦출 수 있을 때까지 늦춥시다. 프로그램이 더 깔끔해지며 효율도 좋아집니다. 항목 27. 캐스팅은 절약, 또 절약! 잊지 말자. [C style cast] (T) expression  <=>  T(expression) [C++ style cast] const_cast, dynamic_cast, reinterpret_cast, static_cast 캐스팅은 공짜가 아니다. (런타임시 실행되는 코드가 증가한다.) 따라서 절약할 수 있는 한 절약해야한다. 특히 dynamic_cast는 주의해야한다. [이것만은 잊지 말자] - 다른 방법이 가능하다면 캐스팅은 피하십시오. 특히 수행 성능에 민감한 코드에서 dynamic_cast는 몇 번이고 다시 생각하십시오. 설계 중에 캐스팅이 필요해졌다면, 캐스팅을 쓰지 않는 다른 방법을 시도해 보십시오. - 캐스팅이 어쩔 수 없이 필요하다면, 함수 안에 숨길 수 있도록 해 보십시오. 이렇게 하면 최소한 사용자는 자신의 코드에 캐스팅을 넣지 않고 이 함수를 호출할 수 있...

Chapter 4. 설계 및 선언 (항목 18~25) 하하하 하루에 2개씩 포스팅한다고 해놓고 한 개도 안했었네요~ ㅎㅎㅎ 하하하ㅏㅎㅎㅎ하하 항목 18. 인터페이스 설계는 제대로 쓰기엔 쉽게, 엉터리로 쓰기엔 어렵게 하자. class BadDate { public: BadDate(int month, int day, int year); }; class Month { public: static Month Jan; // Incorrect! static const Month& Feb() { // Case 1 static Month m(2); return m; } static Month Mar() { return Month(3); } // Case 2 private: explicit Month(int m) : month(m) {} int month; }; Month Month::Jan(1); struct Day { explicit Day(int d) : day(d) {} int day; }; struct Year { explicit Year(int y) : year(y) {} int year; }; class Date { public: Date(Month month, Day day, Year year); }; int main() { BadDate badDate(1996, 2, 2); // mistake of user! Date date(Month::Feb(), Day(2), Year(1996)); }   위 코드를 봐보자. BadDate의 경우 날짜를 그냥 int로만 받으면 사용자의 실수로 인해 parameter의 순서가 바뀌는 일이 생길 수 있다. 따라서 사용자가 명시적으로 타입을 지정하도록 강제하면 사용자에게 실수를 컴파일타임에 알려줄...