Coding StudyRoom

Device API Overview : user kernel 작성 시 kernel에서 난수 생성 후 사용하기 위함 #include "curand_kernel.h" 필요 curand_init()으로 generator state initialize 후, curand() 사용 시 무작위 난수 반환. 같은 generator state에서 curand()를 호출하면 같은 값을 반환. >> thread 당 device global memory에 generator state 값을 저장하는 변수를 할당하여 난수 생성이 끝난 후 state 값을 저장해야 해당 thread 에서 다음 호출 시 해당 state 부터 난수값 반환 가능 한 것 같다 . 즉, 겹치지 않게 생성 XORWOW generator가 defalut gen..

cuRAND 라이브러리 : pseudorandom number(무작위 난수) 와 quasirandom number(준 난수) 생성을 위한 라이브러리 cuRAND 라이브러는 library on the host(CPU)와 device(GPU) 헤더 파일 두 가지로 구성 1. host에서 라이브러리 함수 호출 시 device global memory에 난수가 저장되고, 이를 host memory로 복사해 와서 사용할 수 있다. 2. device 헤더 파일은 random number generator(난수 생성기) state 세팅하기 위한 device 함수와, sequences of random numbers를 생성하는 것이 정의됨. 즉, host code에서 host library를 사용해서 device에서 ..

Nonserial Polyadic DP : next level의 optimal solution 계산을 위해 바로 이전 level의 optimal subsolution 이외에 다른 것도 필요할 수 있으며 + functional equation에 재귀 식이 여러 개 인 경우. 예제 문제1) Optimal Matrix-Parenthesization Problem (Matrix Chain Multiplication) 문제 설명 : - A1, A2 ... Ai matrix 가 존재하고 순서대로 곱했을 때 행렬 곱 연산이 가능 (row와 columm 크기가 매칭된다는 의미) 이 때 행렬 곱을 위해 행렬을 괄호로 묶었을 때 최소 연산 횟수를 찾는다. functional equation C[i, j] : A i 행렬부..

Serial Polyadic DP : next level의 optimal solution 계산을 위해 이전 level의 optimal subsolution을 사용하고, functional equation에 여러 재귀 함수가 필요한 경우. 예제 문제1) Floyd's All-Pairs Shortest-Paths Algorithm 문제 설명 : 모든 노드 간의 쌍에 대해서 최단 거리를 구하는 문제. >> 결과는 행렬로 나오고 0번 노드부터 n번 노드까지 각 노드까지 경유를 고려했을 때 최단거리를 계산해 나가면서 계산한다. functional equation 좌항 : k는 노드 번호, 0번 노드 부터 k - 1 노드 까지 고려해서 경유한 경우 최단 거리를 저장하고 있다. (각 level 마다 n^2 계산이 필..

NonSerial Monadic DP : next level의 optimal solution을 계산하기 위해서 바로 이전 level의 optimal subsolution이 아닌 다른 것을 사용 + functional equation에 재귀 식이 한번 사용되는 경우. 예제 문제1) Longest-Common-Subsequence 문제 설명 : 두 문자열의 최장 공통 부분수열을 찾는다. >> 문자열 같은 부분 건너뛰기 가능 fuctional equation F[i, j] : 한 문자열의 i index 까지, 다른 문자열의 j index 까지의 최장 공통 부분수열의 길이를 저장. * Table entries are computed in a diagonal sweep from top-left to the bot..

Serial Monadic DP : next solution의 최적 해를 구하기 위해 바로 이전 level의 subproblem의 최적 해의 값이 사용되고, 이러한 DP 식에서 재귀식이 한 개인 경우. 예제 1) The Shortest-Path Problem (최단 경로 문제) : 시작 노드(S)에서 끝 노드(R) 까지의 최단 경로를 구하는 문제이다. 문제설명 : - weighted multistage graph(다단계 그래프) 이고 r + 1 개의 levels로 구성되었다. 예시 그림) - level i의 모든 노드들은 level i + 1 의 모든 노드들과 연결되어 있다. (그림과는 다름) - level 0 은 시작 노드(S), level r 은 끝 노드(R)로 노드가 1개 뿐이다. functiona..

Dynamic Programming : Discrete optimization(이산 최적화) 문제들을 풀기 위해 일반적으로 사용됨. >> Discrete optimization : 문제의 해가 연속적이지 않다. 즉, 이산적이다. ex) 해 = [1, 2, 3, 4]

#pragma -> 컴파일러에게 뒤에 오는 내용에 따라 어떤 일을 하라는 전처리명령 1. pragma omp parallel (option) : 구문을 병렬로 실행한다. thread 수만큼 실행된다. >> 여러 thread에서 병렬로 실행할 코드인 병렬 영역을 정의한다. #pragma omp parallel // 병렬처리 할 한줄 #pragma omp parallel { // 병렬처리 할 여러줄 } - Option ▣ if(조건) : 조건이 true일 때만 병렬처리 한다. ▣ num_threads(n) : n개의 thread로만 병렬처리 한다. ▣ private(var) : 변수 var를 각각 copy 해서 사용. 병렬처리 지역 이전의 초기화가 무의미함. >> 병렬처리 지역 내부에서 초기화 필요! 각 쓰..