그냥 그런 블로그

원문 : Summation of primes

계속해서 나오는 소수 문제네요. [ 3. Largest prime factor ] 에서는 가장 큰 소인수를, [ 7. 10001 st pime ] 에서는 n 번째 소수를, 이 번에는 일정 이하의 소수의 합을 구하는 겁니다.

Brute-Force

def sum_primes_until( max ) : primes = list() primes.append( 2 ) primes.append( 3 ) primes.append( 5 ) i = 7 # second prime number, and odd number. sum = 2 + 3 + 5 while( i < max ) : is_prime = True for p in primes : # for each prime number if 0 == ( i % p ) : # i is evenly divided by prime number is_prime = False # i is not prime number break if is_prime : primes.append( i ) sum += i i += 2 # select next odd number if 0 == ( i % 5 ) : # if next odd number is multiple of 5 i + 2 # select next odd number return sum print( sum_primes_until( 2000000 ) )

일단 답은 142913828922 입니다.

나름대로 최적화를 한다고 했지만 O( mn ) 의 시간 복잡도를 가집니다. m 과 n 의 크기가 크므로 비용이 장난이 아닙니다. 한 10 분은 걸린 것 같군요.

소수와 관련해서 점점 더 극악한 조건을 제시하면서 결국에는 최적화를 더 하게 만드는군요.

Others Optimization

[ 7. 10001 st pime ] 의 공식 [ PDF ] 에서 최적화를 위해 사용한 전제들은 다음과 같습니다.

• 1 은 소수가 아님.
• 2 를 제외한 모든 소수는 홀수임.
• 3 보다 큰 모든 소수는 6k+/-1 로 작성될 수 있음.
• 어떤 수 n 은 루트 n 보다 큰 소수를 하나만 가지고 있을 수 있음.
• 어떤 수 n 에 대한 소수 테스트를 하기 위한 수열은 : n 을 나누는 루트 n 보다 작거나 같은 숫자 f 를 발견하지 못한다면, n 은 소수임 : n 의 유일한 소인수는 n 자체임.

뭔가 최적화의 여지가 상당히 많군요.

import math def isprime( n ) : if 1 == n : # 1 is not prime. return False elif n < 4 : return True # 2, 3 elif 0 == ( n % 2 ) : return False # even is not prime. elif n < 9 : return True # even is excluded, reamins 5, 7, 9. elif 0 == ( n % 3 ) : return False # multiple of 3 is excluded else : r = math.floor( math.sqrt( n ) ) f = 5 while f <= r : # check if n is divided by other prime( form of 6k+/-1 ) if 0 == ( n % f ) : return False if 0 == ( n % ( f + 2 ) ) : return False f += 6 return True sum = 2 for n in range( 3, 2000001, 2 ) : if isprime( n ) : sum += n print( sum )

실행해 보니 정상적인 결과가 나왔고, 무진장 빠르군요. 이것도 사실 O( mn ) 의 비용이 듭니다만, Brute-Force 방식보다는 m 과 n 의 크기가  작으므로 매우 빠릅니다. 거의 20 초 정도면 끝나는군요.

원문 : Special Pythagorean triplet

Brute-Force

일단 연립방정식으로 풀 수 있는지 확인을 해 봤습니다만, 방정식이 하나가 부족해서 풀수가 없네요. 어떻게든 하나의 변수값은 알아야 나머지를 풀 수 있는 형태입니다.

결국 삼중 루프를 도는 수밖에 없습니다. 

다음을 만족하는 값들을 찾아야 합니다. 그런데 a 와 b 를 알면 c 를 구할 수 있으므로, 이중 루프만 돌아도 됩니다.

def find_pythagorean_product( sum ) : for b in range( 1, sum ) : b_2 = b * b for a in range( 1, b ) : # a < b a_2 = a * a c = sum - a - b # a + b + c = sum if ( b < c ) and ( ( c * c ) == ( a_2 + b_2 ) ) : # b < c, a^2 + b^2 = c^2 print( "a = {0}, b = {1}, c = {2}".format( a, b, c ) ) return a * b * c print( find_pythagorean_product( 1000 ) )

답은 31875000 입니다.

Others Solution

Math Blog 의 [ A 1000 Pythagorean triplets – Problem 9 ] 에 수학적인 접근이 있더군요. 궁금하면 확인해 보시기 바랍니다.

원문 : Largest product in a series

일단 간단하게 생각하면 그냥 루프를 돌면서 15 개씩 묶어서 곱해보는 것이 가장 단순합니다. 먼저 하나의 1000 자리 숫자를 여러 개의 1 자리 숫자로 나누는 작업이 필요하겠죠.

그런데 이 작업을 하려면 1000 자리가 들어 갈 수 있는 자료형이 필요합니다. 컴퓨터는 데이터를 이진수로 저장하기 때문에, 이를 표현하기 위해서는 얼마나 큰 비트가 필요할까요?

계산을 해 보도록 하겠습니다.

이진수로 자리수를 올리는 것은 한 비트씩 옮기는 겁니다. 아래 첨자가 2 라고 되어 있으면 이진수를 그렇지 않으면 십진수를 의미합니다.

그렇다면 십진수는 어떨까요( 아래에서 왼쪽 항을 볼 때 주의할 점은 십진수 표현이라는 것입니다. 줄을 맞추려고 앞에 0 을 넣었습니다. 아래 첨자가 없다는 점에 주의하세요 ).

그럼 10 의 멱승을 이진수로 표현해 보죠.

뭔가 규칙이 있을까요? 십진수가 1 자리 올라갈 때마다, 이진수는 3 자리나 4 자리가 올라가는 것을 알 수 있습니다. 이렇게 볼 때 십진수로 표현했을 때 1000 자리가 되려면 이진수로 고쳤을 때 최대 4000 자리( 즉 4000 비트 )가 필요함을 알 수 있습니다.

즉 1000 자리 숫자는 현재의 이진수 컴퓨팅 환경에서 표현하는 것이 불가능한 숫자입니다.

Brute-Force

그래서 이를 그냥 문자열로 표현하기로 했습니다. 그리고 계산할 때마다 형변환하는 것을 피하기 위해서 미리 형변환해서 리스트에 넣었습니다. 계산 방식 자체는 단순합니다. 그냥 처음부터 13 개씩 계산하면 됩니다.

str_num = ( "73167176531330624919225119674426574742355349194934" "96983520312774506326239578318016984801869478851843" "85861560789112949495459501737958331952853208805511" "12540698747158523863050715693290963295227443043557" "66896648950445244523161731856403098711121722383113" "62229893423380308135336276614282806444486645238749" "30358907296290491560440772390713810515859307960866" "70172427121883998797908792274921901699720888093776" "65727333001053367881220235421809751254540594752243" "52584907711670556013604839586446706324415722155397" "53697817977846174064955149290862569321978468622482" "83972241375657056057490261407972968652414535100474" "82166370484403199890008895243450658541227588666881" "16427171479924442928230863465674813919123162824586" "17866458359124566529476545682848912883142607690042" "24219022671055626321111109370544217506941658960408" "07198403850962455444362981230987879927244284909188" "84580156166097919133875499200524063689912560717606" "05886116467109405077541002256983155200055935729725" "71636269561882670428252483600823257530420752963450" ) nums = list() for c in str_num : nums.append( int( c ) ) max_product = 0 offset = 0 num_adjacency = 13 max_offset = len( nums ) - num_adjacency - 1 while( offset < max_offset ) : product = 1 for i in range( offset, offset + num_adjacency ) : product *= nums[ i ] max_product = max( max_product, product ) offset += 1 print( max_product )

답은 23514624000 입니다.

Optimization

하지만 다른 문제들처럼 뭔가 다른 빠른 방법이 있을 것이라는 강박관념이 들더군요.

MathBlog 의 [ Solution to Problem 8 of Project Euler ] 의 댓글을 보니, 마지막 곱들을 저장해 놓는 것에 대한 이야기가 있었습니다. 

그렇다면 이전의 곱셈 결과에서 이전의 시작값을 나누고 다음에 올 값을 곱한다면, 문제가 해결될 수 있겠다는 생각이 들더군요. 그런데 실제 해 보니 안 됐습니다. 중간에 0 이 있으면 모든 값이 무산된다는 것을 고려하지 않은거죠. 만약 0 인 숫자가 하나도 없다면 가능할 것 같네요.

Other's Solution

[ Project Euler 8: Find the largest product of 13 consecutive digits ] 에서는 파이썬의 언어특성을 잘 이용해서 매우 짧은 코드를 작성하고 있습니다.

#Project Euler Problem 8 from operator import mul d = map(int, ''.join(line.rstrip() for line in open('pe8.txt'))) L = 13 print 'Greatest product of', L, 'consecutive \ndigits =', print "None." if L>len(d) else \ max(reduce(mul, d[i:i+L]) for i in xrange(len(d)-L+1))

솔직히 파이썬 자료구조와 알고리즘에 대한 공부를 많이 안해서 이해하기가 힘드네요.

원문 : Smallest multiple

일단 특정 범위의 숫자로 나눴을 때 나머지가 없다는 이야기는 그 숫자들이 곱해져있다는 의미일 겁니다.

예를 들어 1 부터 10 까지의 숫자로 곱해진 숫자라면 어떤 수로 나눠도 나머지가 없는 수가 나오겠죠.

그런데 여기에서 우리는 규칙을 하나 알 수 있습니다. 합성수는 소수의 곱으로 되어 있기 때문에, 소수가 중복된다는 겁니다. 

예를 들어 10 은 2 * 5 로 구성되었기 때문에 2 와 5 가 중복됩니다. 그러면 2 와 5 를 한 번씩 빼도 2, 5, 10 으로 나누어 떨어질 수 있죠.

소인수 분해를 해 보도록 하겠습니다. 1 은 소수가 아니고 곱셈에 영향을 주지 않으므로 배제합니다.

여기에서 우리는 일련의 규칙을 발견할 수 있습니다. 소인수 분해를 했을 때 합성수를 만들기 위해서 필요한 최대 소수의 개수를 알 수 있다는 것입니다.

예를 들자면 4 로 나누기 위해서는 적어도 2 가 2 개가 존재해야 합니다. 6 으로 나누기 위해서는 적어도 2 가 1 개, 3 이 1 개가 존재해야 합니다. 8 로 나누기 위해서는 적어도 2 가 3 개가 존재해야 합니다. 9 로 나누기 위해서는 적어도 3 이 2 개는 존재해야 합니다. 10 으로 나누기 위해서는 적어도 2 가 1 개, 5 가 1 개가 존재해야 합니다. 그 이외의 소수들( 여기에서는 7 )은 1 개씩만 존재하면 되죠.

정리하면 2 가 3 개, 3 이 2 개, 5 가 1 개, 7 이 1 개가 필요합니다.

위의 문제와 동일한 답이 나오는군요.

Brute-Force

이제 알고리즘을 세워 보도록 하겠습니다.

• 2 부터 20 까지의 모든 수를 돌면서 소인수 분해를 합니다.
• 소인수 분해를 했을 때, 각 소인수의 개수를 세서, 소수의 최대 횟수를 구합니다.
• 소수의 최대 횟수만큼 곱합니다.

일단 소인수들을 구하는 함수는 [ 3. Largest prime factor ] 에서 가지고 왓습니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 if 0 == ( i % 2 ) else 2 return prime_factors

이제 각 factor 의 카운트를 세서 곱하는 구현을 합니다.

total_max_count = dict() for i in range( 2, 21 ) : max_count = dict() prime_factors = get_prime_factors( i ) for p in prime_factors : if p in max_count : max_count[ p ] += 1 else : max_count[ p ] = 1 max_count_keys = max_count.keys() for key in max_count_keys : if key in total_max_count : total_max_count[ key ] = max( total_max_count[ key ], max_count[ key ] ) else : total_max_count[ key ] = max_count[ key ] smallest_number = 1 total_max_count_keys = total_max_count.keys() for key in total_max_count_keys : for c in range( total_max_count[ key ] ) : smallest_number *= key print( smallest_number )

조금 코드가 길지만 첫 번째 최상위 루프를 통해서 소인수들을 얻어서 최대 카운트를 셉니다. 그리고 두 번째 루프에서는 최대 카운트만큼 소인수들을 곱해줍니다.

결과는 232792560 입니다.

Other's solution

다른 해법이 있는지 찾아 봤습니다. 공식 PDF 에서는 뭔가 엄청 단순한 형태로 푸는군요. 뭔 sqrt 와 log 가 나오고 난리입니다. 기본적으로 반복횟수를 이용해서 푸는 것은 동일한데, 위의 식을 다음과 같이 표현하는데서 알고리즘을 시작합니다.

i 번째 소수를 pi 라고 하고 지수를 ai 라 할 때 N 은 다음과 같습니다.

여기에서 pi^ai 을 k 라고 하면, ai 는 다음과 같습니다.

예를 들어, k = 20 이라고 하면, 첫 번째 소수인 p1 = 2 입니다. 그러면 다음과 같이 a1 을 구할 수 있습니다.

정수여야 하므로 floor 를 사용합니다. 최적화를 위해서 pi <= sqrt( k ) 인 경우의 ai 만을 계산한다고 합니다.

이것을 일반화해서 다음과 같이 계산한다고 합니다.

자세한 건 pdf 에서 확인해 보시기 바랍니다.

원문 : Largest palindrome product

Brute-Force

일단 제가 생각한 알고리즘은 다음과 같습니다.

• 세 자리 수의 곱으로 표현할 수 있는 수들을 검색합니다.
• 그 중에서 대칭수를 찾습니다.
• 가장 큰 대칭수로부터 내림차순으로 소인수분해를 해서 세 자리 수의 곱으로 표현된다면 그것이 가장 큰 대칭수입니다.

세 자리 수 중에서 가장 큰 것은 999 이고 가장 작은 것은 100 입니다. 그러므로 대상이 될 수 있는 수의 범위는 [ 100 * 100, 999 * 999 ] 입니다; [ 10,000, 998,001 ].

일단 가장 먼저 할 일은 어떤 숫자를 자리수로 쪼개는 함수를 만드는 거겠죠. 만드는 김에 두 번째 인자로 진법( numeral_system )을 넣도록 해 봤습니다.

def split_value( value, numeral_system ) : values = list() quotient = value while( 0 != quotient ) : remainder = quotient % numeral_system values.append( int( remainder ) ) quotient = quotient // numeral_system values.reverse() return values

15 부터 25 까지 십진법과 이진법으로 출력해 보면 결과는 다음과 같습니다.

이제 해당 숫자가 대칭수인지 확인하는 함수가 필요하겠죠. 어떤 숫자가 있을 때 중심이 되는 인덱스를 구하고 하나는 오름차순으로 하나는 내림차순으로 인덱싱하면서 값을 비교합니다. 만약 홀수개로 구성된 숫자가 있다면, 중간값은 항상 한 개이므로 비교할 필요가 없겠죠.

def is_palindrome_number( value ) : values = split_value( value, 10 ) num_values = len( values ) count = num_values // 2 for i in range( count ) : a = values [ i ] b = values [ num_values - 1 - i ] if a != b : return False return True

이제 루프를 돌면서 대칭수를 전부 출력해 보겠습니다. 

for i in range( 10000, 998002 ) : if( is_palindrome_number( i ) ) : print( i )

엄청나게 많군요... 그래서 여기에 올리지는 않았습니다. 어쨌든 가장 큰 대칭수는 997799 입니다. 물론! 이것이 답은 아닙니다. 왜냐하면 세 자리 수의 곱으로 표현될 수 있어야 하기 때문입니다.

성능을 고려하면 이것을 큰 수부터 내림차순으로 해야 합니다. 파이썬의 for 는 이런 부분에서 참 불편하군요. 범위가 헷갈립니다.

for i in range( 998001, 9999, -1 ) :

자 이제 [ 3. Largest prime factor ] 에서 만들었던 소인수분해해서 소인수 리스트를 반환하는 함수를 가지고 와서 사용할 겁니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 if 0 == ( i % 2 ) else 2 return prime_factors

리스트로 받은 소인수들을 곱해가지고 두 개의 세 자리 수를 만들어야 합니다. 여기가 가장 어려운데요...

• 일단 세 자리수가 나오는 경우의 수를 모두 찾습니다. 앞에서부터 곱해도 되고 뒤에서부터 곱해도 되겠죠. 아마도 뒤에서부터 곱하는 것이 빠를 겁니다. 왜냐하면 리스트의 뒤쪽으로 갈 수록 큰 소인수이기 때문입니다.
• 하나의 세 자리 수가 나오면 나머지 소인수들을 모두 곱했을 때, 그 결과가 세 자리 수가 아니면 실패입니다.

저는 뒤에서부터 숫자를 곱해 봤습니다.

def can_make_3_digit_product( val, factors ) : temp = factors.copy() factor_1 = 1 factor_2 = 1 while( 0 < len( temp ) ) : factor_1 *= temp.pop() if 99 < factor_1 < 1000 : break while( 0 < len( temp ) ) : factor_2 *= temp.pop() if ( 99 < factor_1 < 1000 ) and ( 99 < factor_2 < 1000 ) : print( "%d = %d * %d" % ( val, factor_1, factor_2 ) ) return True return False

물론 이렇게 하는 건 잘못된 결과를 산출합니다. 왜냐하면 다음과 같은 경우를 생각해 보죠.

2 * 79 = 158 이고 3 * 83 = 249 로 해야지 세 자리 수의 곱이 나옵니다. 결국 모든 경우의 수를 찾지 않으면 정확한 결과를 구할 수가 없습니다. 결국 세 자리를 만들수 있는 경우의 수를 모두 구해야 합니다.

친구( 햄짱 )에게 이걸 해결할 쌈박한 아이디어가 있는지 물어 봤습니다. 그런데 "경우의 수를 모두 구하는 건 너무 복잡하니 세 자리 수를 모두 곱해서 대칭수가 나오는 것을 찾는 게 낫지 않겠냐"는 대답을 들었습니다. 

생각해 보니, 문제가 "특정 수를 대칭으로 만드는 세 자리 수의 곱을 찾아라" 가 아니기 때문에, 그렇게 하는 게 낫겠다는 생각이 들었습니다.

result = 0 for i in range( 999, 99, -1 ) : for j in range( 999, 99, -1 ) : number = i * j if is_palindrome_number( number ) : result = max( number, result ) print( result )

답은 906609 입니다.

Optimization

그런데 제가 만든 식은 성능에 문제가 있습니다. 왜냐하면 코드를 보면 알 수 있겠지만, 중간에 break 를 하지 않습니다. 그 이유는 이중 루프를 사용했을 때 먼저 나오는 수가 가장 큰 수라고 보장할 수 없기 때문입니다.

예를 들면, 가장 먼저 나오는 수는 995 * 583 = 580085 입니다. 이것은 993 * 913 = 906609 보다 작습니다. 그래서 루프를 다 돌 수 밖에 없는데요, 이를 최적화할 수 있는 방법이 필요합니다. 

문제를 풀고 나면 나오는 Lster 이라는 사람이 작성한 PDF 를 보면, 다음과 같이 일반식을 찾습니다.

세 자리 수를 곱했을 때 나오는 대칭수는 최대 xyzzyx 형태의 여섯자리 수가 됩니다. 이를 식으로 정리하면 다음과 같습니다.

즉 11 의 배수 형태가 나온다는 것입니다. 그러므로 둘 중의 하나는 소인수분해를 했을 때 반드시 11 을 포함해야 합니다.

그러면 아래와 같이 코드를 작성해 볼 수 있습니다.

result = 0 for i in range( 999, 99, -1 ) : for j in range( 999, 99, -1 ) : if ( 0 == ( i % 11 ) ) or ( 0 == ( j % 11 ) ) : number = i * j if is_palindrome_number( number ) : result = max( number, result ) print( result )

해당 문서에서는 조금 더 복잡한 최적화를 하고 있는데, 관심이 있으면 살펴 보시기 바랍니다.

원문 : Largest prime factor

Prime factor

일단 소인수가 뭔지 알아야 합니다. 일단 제가 알고 있는있는 소인수의 정의는 다음과 같습니다.

자신과 1 을 제외하고는 나눠지지 않는 않는 수.

실제 정의를 찾아 보았습니다만, 위에서 제가 한 정의는 "소수( prime number )" 에 대한 정의군요. 그리고 자연수여야 한다는 조건도 빠졌구요.

소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. ( 중략 ) 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

출처 : [ 1 ].

구글 사전에서는 소인수를 다음과 같이 정의하더군요.

어떤 정수(整數)를 소수(素數)만의 곱으로 나타낸 때의 각 인수(因數).

구글 사전에서는 인수를 다음과 같이 정의하고 있습니다.

정수 또는 정식(整式)을 몇 개의 곱의 형태로 하였을 때, 그것의 각 구성 요소. 인자(因子).

즉 소인수는 "소수인 인수" 를 의미하는 거군요.

Generate prime numbers

그럼 가장 먼저 생각해 봐야 할 부분은 소수를 검사할 수 있는 방법이겠네요. 일단 소수값들을 나열해 봤습니다.

2 가 유일한 짝수이고 나머지는 홀수입니다. 그렇다면 계산의 시작은 더 이상 2 로 나눠질 수 없을 때까지 2 로 나누는 거겠죠.

예를 들어 60 이라는 수는 2 * 2 * 15 로 구성됩니다. 그러면 15 라는 수가 남네요. 이제 다음 소수인 3 으로 같은 작업을 반복할 수 있을 것입니다. 그러면 15 는 3 * 5 로 구성됩니다. 그러면 5 라는 수가 남네요. 이제 다음 소수인 5 로 같은 작업을 수행합니다. 그러면 5 * 1 이 되고, 1 은 나눌 수 없으니 계산이 종료될 겁니다. 결국 2, 3, 5 가 60 을 구성하는 소인수들이 됩니다. 

그런데 이건 합성수의 소인수를 찾는 것( 소인수분해 )이지 소수 자체를 구하는 것이 아닙니다. 그런데 이 소인수분해를 하는 과정자체가 소수를 찾는 과정이 아닐까라는 생각이 들었습니다.

왜냐하면 "자신과 1 을 제외한 자연수로 나눌 수 없는 자연수" 라는 정의를 생각하면 다음과 같은 가정을 깔 수 있을 것이기 때문입니다.

자신보다 작은 소수로 나눠봤을 때 나누어 떨어지면 그것은 소수가 아니다.

그러면 아래와 같이 소수를 생성해 볼 수 있습니다.

prime_numbers = [ 2 ] def generate_prime_numbers( max ) : for i in range( 3, max + 1) : is_prime_number = True for p in prime_numbers : if 0 == ( i % p ) : is_prime_number = False break if is_prime_number : prime_numbers.append( i ) generate_prime_numbers( 100 ) print( prime_numbers )

대충 살펴 보니 맞는 것 같군요.

그런데 여기에서 우리가 목표로 하는 600,851,475,143 을 넣고 generate_prime_factors() 를 호출하면 상상도 못할 시간이 걸리게 됩니다. 아무리 기다려도 끝날 생각을 하지 않습니다.

왜냐하면 이것의 시간복잡도는 O( i * p ) 이기 때문입니다; 여기에서 i 는 max 이고 p 는 i 보다 작은 소수의 개수입니다. 그러므로 최악의 경우라도 O( i^2 ) 보다는 작습니다만 max 가 워낙 크기 때문에 답이 없습니다.

그러므로 이건 적어도 이 문제를 풀기 위해서는 사용할 수 없는 함수입니다. 물론 언젠가는 계산이 끝나기는 하겠죠.

최적화를 위해서 병렬화를 고민해 볼 수도 있겠지만, 그건 너무 나간 것 같구요, 알고리즘적으로 해결할 수 있는 방법을 찾아 봐야 합니다.

Optimization : Only odd numbers

일단 단순하게 생각했을 때 2 의 배수인 숫자들( 즉, 짝수 )를 배제하면 대상이 절반이 줄어듭니다.

3 에서 시작한 것이니 for 문의 증가값을 2 로 하면 홀수만 나오게 되죠.

for i in range( 3, max + 1, 2 ) :

Optimization : Reduction

하지만 여전히 검사해야 할 숫자의 개수가 많습니다. 그런데 더 생각나는 방법은 없더군요. 그래서 참고자료를 찾아 봤습니다. [ 1 ] 에서는 다음과 같이 언급하고 있더군요.

그렇군요. 대상을 아예 없애 버리면 됩니다. 하지만 두 가지 문제가 있습니다.

• 메모리 문제 : 메모리가 버텨 줄 것인가?
• list operation : append, remove 등의 연산의 비용은 어떻게 할 것인가?

일단 메모리 문제를 검증해 봤습니다. 2 의 배수만을 배제한다고 가정했을 때, 배열의 크기는 1 GB 정도입니다. 5 의 배수까지 배제한다면 더 줄어들 수 있겠죠. 이 정도는 크게 문제가 없을 것이라는 판단을 했습니다.

두 번째로 list 관리 문제인데요, 소수가 아닌 것들에는 -1 값을 넣어 두면 되기 때문에 별 문제는 없을 것으로 보입니다. 게다가 저는 대상을 배제하는 기법을 사용하는 것이 아니라 소수인지 여부를 검사하는 기법을 사용하고자 합니다. 왜냐하면 대상을 배제하는 기법은 자신보다 큰 값들에 대해서 루프를 검사하는 비용이 들기 때문입니다. 결국에는 소수의 루프를 돌면서 검사하는 것과 크게 다르지 않은 비용이 나올 것이라고 생각합니다. 둘다 이중 루프로 시간복잡도는 거의 동일하기 때문입니다.

def generate_prime_numbers( max ) : prime_numbers = [ 2 ] # gather target numbers except multiples of 2 or 5 targets = list() for i in range( 3, max + 1, 2 ) : if 1 == ( i % 5 ) : targets.append( i ) # check if each item is not a prime number for i in targets : is_prime_number = True for p in prime_numbers : if 0 == ( i % p ) : is_prime_number = False break if is_prime_number : prime_numbers.append( int( i ) ) # return result. return prime_numbers

꽤 많이 배제한 상태임에도 불구하고, i7-4770K 에서 2 분이 지나도록 끝이 안 나더군요. 이것이 list 의 append() 에 드는 비용이 아닌가라는 의심이 들기 시작했습니다. 찾아 보니까, [ 간단한 구문 변경으로 속도를 향상시키기 ] 에서 백만개를 돌리는데 109 ms 를 소비하더군요. 물론 2015 년 자료니 머신의 성능이 어떤지는 모르겠지만, 시간이 많이 걸리는 건 사실입니다. 우리의 목표는 6000 억개이기 때문에 홀수만 따져도 3000 억개입니다. 단순하게 산술계산을 하면 60 만배이고 1000 ms 가 1 초이므로, 6 만초( 16.6 시간 )가 걸립니다. 그러므로 절대 append() 를 많이 사용해서는 안 되는 상황인 것입니다.

링크의 문서에 나온 것처럼 루프 밖에서 append 함수를 미리 선언하는 방식을 사용해 봤습니다( 마치 함수 포인터같은 녀석입니다 ).

target_append = targets.append for i in range( 3, max + 1, 2 ) : if 1 == ( i % 5 ) : target_append( i )

비용이 30 % 정도 줄어든다고 하니 기대시간은 약 11.62 시간입니다. 이것도 용납할 수 없는 수치입니다.

이걸 빠르게 할 수 있는 방법이 있으면 누군가 공유해 줬으면 좋겠군요.

추가 : [ 7. 10001st Euler ] 를 풀면서, 2 의 배수, 5 의 배수를 배제하고 소수를 뽑아 봤는데, 예상한 것과는 다르게 1 ~ 2 분 정도밖에 안 걸리더군요. 그러므로 위에서 예측한 비용은 잘못된 것으로 보입니다.

Prime Factorization

뭐 굳이 소수의 리스트가 없어도 문제를 해결할 방법은 있습니다.

원래 값을 2 부터 시작해서 나눕니다. 그리고 나머지가 0 이 아니면 다음 숫자로 넘어 갑니다. 나머지를 0 으로 만드는 수는 소인수라 생각할 수 있습니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 return prime_factors prime_factors = get_prime_factors( 600851475143 ) print( prime_factors ) print( prime_factors[ len( prime_factors ) -1 ] )

답은 6857 입니다.

다른 사람들은 어떻게 풀었는지 확인해 봤는데 별 차이는 없네요. 단지 MathBlog 에서는 0 ms 에 가까운 대안을 소개하고 있습니다( 앞에서 소개했던 짝수배제 기법입니다 ). 

근데 컴퓨터가 좋아서인지 최적화를 안 해도 저는 0.0107 ms 가 나오는군요. 어쨌든 빠르면 좋은거니 저도 홀수를 배제해 봤습니다. 

i += 1 if 0 == ( i % 2 ) else 2

그랬더니 0.0058 ms 로 반쯤 줄어드는군요. 여기에서 5 의 배수도 배제해 봤습니다.

next = i + 1 i += 2 if ( 0 == ( next % 2 ) ) or ( 0 == ( next % 5 ) ) else 1

그런데 조건문이 두 개가 되지 비용만 더 올라갑니다( 0.0068 ms ). 너무 작은 비용에 대한 부적절한 최적화는 오히려 해가 된다는 사실을 알게 되네요.

전체 소인수 리스트를 수집하기 위해서 append() 를 사용하고 있습니다. 이를 배제하고 마지막 소인수만 반환한다면 더 빠른 결과를 볼 수 있습니다( 0.0048 ms ). 하지만 기본 while 비용이 있으므로 여기에서 드라마틱하게 내려가지는 않네요.

def get_last_prime_factor( target ) : quotient = target last_prime_factor = -1 i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i last_prime_factor = i else : i += 1 if 0 == ( i % 2 ) else 2 return last_prime_factor

참고자료

[ 1 ] 소수 ( 수론 ), 위키피디아.

[ 2 ] 소인수분해, 위키피디아.

원문 : Even Fibonacci numbers

문제 의도 해석

피보나치 수열에서 어떤 항은 앞의 두 수를 더해서 나온 것입니다.

• 3 = 1 + 2
• 5 = 2 + 3
• 8 = 5 + 3
• ...

문제에서는 짝수값만 더하라는 것이죠. 위의 예에서는 2 + 8 + 34 = 44 가 됩니다.

print_fibonacci function

일단 피보나치 수열의 값을 출력하는 함수를 만들어 보았습니다. 재귀적으로 호출하는 형식입니다. 단 100 을 넘지 않는 값을 출력하도록 했죠.

def print_fibonacci( a, b, max_term ) : if b > max_term : print( a ) return print( a ) print_fibonacci( b, a + b, max_term )

이를 실행하면 다음과 같은 결과가 나오죠.

물론 재귀 함수가 아니라 for 문을 통해서 구현하는 것도 가능합니다.

def print_fibonacci_with_while( a, b, max_term ) : a_val = a b_val = b while( b_val <= max_term ) : print( a_val ) temp = a_val a_val = b_val b_val = temp + b_val print( a_val )

sum_fibonacci function

이제 이 결과를 합쳐 보겠습니다. 결과를 더하는 건 결국 출력하는 순서와 동일하게 더해 가는 겁니다. 그런데 문제는 함수 내에서 a + b 가 발생하면, 다음 재귀 함수에서 b + next_term 를 하기 때문에( a' 로서 b, b' 로서 next_term, 그러므로 b 누적 ) 요소가 한 번씩 누적될 수 있다는 겁니다. 이에 주의해야 합니다.

def sum_fibonacci( a, b, max_term ) : if b > max_term : return a return a + sum_fibonacci( b, a + b, max_term )

sum_even_fibnoacci function

이제 문제의 의도대로 짝수값만 더하는 함수를 만듭니다. 임시 변수를 만들어서 홀수인 경우에는 0 취급을 해 주면 기존의 함수의 형태에서 크게 달라지지 않습니다.

def sum_even_fibonacci( a, b, max_term ) : a_val = 0 if ( a % 2 ) else a # a_val = ( a % 2 ) ? 0 : a if b > max_term : return a_val return a_val + sum_even_fibonacci( b, a + b, max_term )

파이썬 삼항 연산자가 좀 맘에 안 들기는 하지만, 어쨌든 비슷한 형태가 나옵니다.

4,000,000 까지의 피보나치 수열의 짝수항들을 더한 결과는 4613732 입니다.

More Efficient Method?

근데 재귀함수의 복잡도는 O( n ) 보다는 무조건 크게 나오는 것으로 보입니다; O( logn ), O( n^2 ), O( n^3 ). 그러므로 가급적이면 O( n ) 이 나오는 whlie 문을 사용하는 것이 좋을 것같습니다.

그런데 O( 1 ) 상수복잡도를 가지는 식은 없을까요? 왠지 불가능할 것 같습니다. 혹시 알고 계시다면 제보를 부탁드립니다.

우리는 짝수가 "홀수와 홀수" 혹은 "짝수와 짝수"를 더했을 때 나온다는 것을 알고 있습니다. 그래서 이를 이용해서 뭔가 간단한 규칙을 만들어 보려고 했습니다만, 어떻게 해야 할지 모르겠더군요. 그런데 이미 이걸 하신 분이 있더군요( F3 부터 세 번째 항들( F6, F9, ... )이 짝수라는 겁니다 ). 

"홀수 + 홀수 = 짝수" 이고 짝수 앞뒤에는 항상 홀수가 오니까 세 번째마다 반복되는 것으로 보입니다. 물론 이분은 "1, 1" 에서 시작하는 피보나치 수열을 가지고 계산한 것입니다.

이 분의 최종 코드는 다음과 같습니다( C# 으로 구현한 겁니다. 정확한 방식에 대해 알고자 하신다면 MathBlog 의 [ Project Euler - Problem 2 ] 를 참조하시기 바랍니다 ).

long[] fib = {2,0}; int i = 0; long summed = 0; while (fib[i] < 4000000) { summed += fib[i]; i = (i + 1) % 2; fib[i] = 4 * fib[(i + 1) % 2] + fib[i]; }

Where is Fibonacci Sequences?

피보나치 수열은 황금비를 형성한다고 합니다. [ 왜 자연은 피보나치 수열과 황금비를 택했을까 ] 를 읽어 보시면 재밌습니다. 엄청나게 세부적인 설명을 보려면 [ Fibonacci Numbers and Nature ] 라는 글을 참고하시면 좋습니다.

원문 :  Multiples of 3 and 5.

가장 쉽게 생각해 볼 수 있는 것은 루프를 돌면서 3 이나 5 의 배수이면 더하는 겁니다. 사실 이거 말고는 별 생각이 안 나더군요.

sum = 0 for i in range( 1000 ): if ( 0 == i % 3 ) | ( 0 == i % 5 ) : sum += i print( sum )

결과는 233168 입니다. 이것을 빅오 표기법으로 하면 O( N ) 이겠죠( 빅오 표기법에 대해서 더 자세히 알고자 하신다면, [ 강의노트 25. 자료구조, 알고리즘 - 성능측정 (Big-O ) ] 를 참조하시면 좋을 것 같네요 ).

다른 방식으로 푸는 사람이 있는지 확인해 봤습니다.

제가 푼 방법은 "brute-force" 방식이더군요. "geometric/arithmetic approach" 로 스마트하게 푸는 사람들이 있었습니다.

[ Project Euler - Problem 1 ] 에 의하면, 3 의 배수를 더한 것과 5 의 배수를 더한 것을 합하는 방식으로 문제 해결을 하더군요. 단순하게 생각해 봐도 전체 값에 대한 루프를 도는 것 보다는 훨씬 효율적인 것을 알 수 있었습니다.

거기에 더 나아가서 수학적인 기법을 이용해서 문제를 풀고 있었습니다. 아래는 우리가 많이 봤던 정수 덧셈에 대한 식이죠( 여러 가지 방법으로 생각해 볼 수 있는데, 궁금하다면 [ 정수의 합 공식 ] 을 참조하세요 ).

이걸 좀 변형해서 K 의 배수를 더한다고 해 보죠.

그럼 3 의 배수의 합과 5 의 배수의 합은 다음과 같습니다.

하지만 여기에서 끝이 아닙니다. 3 의 배수와 5 의 배수에는 두개의 최소 공배수인 15 의 배수가 겹쳐서 들어 가고 있습니다. 그러므로 15 의 배수를 빼 쭤야 정상적인 결과가 나옵니다.

def sum_of_multiples( base_value, max_value ) : num_values = int( max_value / base_value ) return int( base_value * num_values * ( num_values + 1 ) / 2 ) solution = sum_of_multiples( 3, 999 ) + sum_of_multiples( 5, 999 ) - sum_of_multiples( 15, 999 ) print( solution )

어떤 숫자든간에 sum_of_multiples 는 상수시간에 문제를 해결합니다. 한 마디로 어떤 값을 넣어도 일정한 시간이 걸린다는거죠. 빅오 표기법으로 하면 O( 1 ) 입니다.

역시 알아야 면장이라도 한다고.... 어떻게 하느냐에 따라서 성능에 큰 영향을 줄 수 있군요. 공부를 더 열심히 해야겠습니다.

p.s. 형변환 없이 다음과 같이 코드를 쓸 수도 있습니다.

def sum_of_multiples( base_value, max_value ) : num_values = max_value // base_value return base_value * num_values * ( num_values + 1 ) // 2 solution = sum_of_multiples( 3, 999 ) + sum_of_multiples( 5, 999 ) - sum_of_multiples( 15, 999 ) print( solution )

파이썬에서 "//" 연산자는 소수점을 버리는 나누기 연산자더군요.

주의 : 이 문서는 초심자 튜토리얼이 아닙니다. 기본 개념 정도는 안다고 가정합니다. 초심자는 [ Vulkan Tutorial ] 이나 [ Vulkan Samples Tutorial ] 을 보면서 같이 보시기 바랍니다.

주의 : 완전히 이해하고 작성한 글이 아니므로 잘못된 내용이 포함되어 있을 수 있습니다.

주의 : 이상하면 참고자료를 확인하세요.

저는 벌칸에 대해서 공부하면서 RenderMonkey 와 유사한 VulkanMonkey 라는 셰이더 편집 도구를 만든다는 최종 목표를 가지고 있습니다. 이 연구 시리즈도 그것을 구현하는 과정에서 발생하는 여러 가지 의문들에 대해서 스스로 답을 내면서 만들어지고 있는 것입니다.

하지만 프로젝트를 진행하다가 벽에 부딪히게 되었습니다. 기존의 D3D9 이나 OpenGL 과는 다르게 Vulkan 은 여러 개의 큐를 가질 수 있으며 커맨드들이 비동기적으로 실행될 수 있기 때문에, RenderMonkey 와 같은 TreeView 구조의 워크스페이스 관리는 비직관적입니다.

이 때문에 구조가 맘에 안 들어 디바이스 생성후 더 이상 진행을 못하고 있었습니다. 물론 마샬링 구조를 결정하는 문제 때문에 프로젝트를 3 차례나 엎고 다시 만드는 데 걸리는 시간이 꽤 길긴 했지만( 현재는 C# <--> C++/CLI <---> C++ 의 구조를 가집니다. 이 부분에 대해서는 나중에 한 번 공유하도록 하겠습니다 ), 그건 과거의 문제이고 미래로 나아가지 못하는 원인은 워크스페이스 구조였습니다.

그런데 오늘 갑자기 나아가야 할 방향이 떠 올랐습니다. 벌칸은 매우 높은 수준으로 파이프라인화되어 있는 API 입니다. 이미 이런 형태를 잘 반영하고 있는 도구들이 존재하고 있는데 삽질을 했다는 생각이 들었습니다. 그건 바로 Graphics Profiler 들입니다. 예를 들어 NSight Graphics 를 보면 다음과 같습니다.

Scrubber View 에서 큐당 커맨드의 흐름을 확인할 수 있습니다. 그리고 이벤트 뷰와 API 인스펙터 뷰에서 세부사항을 확인할 수 있죠.

VulkanMonkey 에서는 커맨드 단위가 아니라 렌더 패스 단위의 흐름을 파악할 수 있도록 만들면 되겠다는 생각이 들었습니다. 커맨드 버퍼 내부에서 동기화를 해야 하는 경우는 거의 없을 것이라고 생각하기 때문입니다.

그러면 아래와 같은 형태로 렌더 패스를 배치할 수 있습니다. 물론 실제 걸리는 시간은 알 수 없으니 적절히 너비를 사용자가 조정하게 만들어야겠죠. 아래 그림에서는 세마포어를 사용해서 "Light Accumulation" 렌더 패스가 시작되기 전에 "CSM3Depth" 렌더 패스에 대해 웨이트하도록 하는 상황을 상정했습니다. 물론 실제 구현 측면에서 보면, "Light Accumulation" 의 첫 번째 커맨드 버퍼를 Submit 할 때 Wait 를 하는 상황이겠죠.

그리고 각각의 렌더 패스의 인스펙터창에서는 세부적인 설정들을 할 수 있도록 하는 거죠. 이렇게 하면 전체적인 흐름을 볼 수 있습니다. 

여기에다가 특정 시점까지의 렌더 패스 실행 결과만을 실행할 수 있는 기능까지 추가하면, 프레임 디버거처럼 중간과정을 확인하는 것도 가능할 것입니다. 

좀 더 나아가면 렌더 패스 내의 커맨드 퍼버들까지 가시화해 줄 수 있으면 금상첨화라는 생각이 듭니다. 그러면 하나씩 그리는 과정도 추적할 수 있겠죠.

이제 좀 앞으로의 구현 방향이 잡히는 기분입니다. 물론 이런 UX 를 구현하려고 생각하니 끔찍하긴 하지만 말이죠.

더 좋은 아이디어가 있으면 댓글 남겨 주시면 감사하겠습니다.

주의 : 번역이 개판이므로 이상하면 원문을 참조하세요.

주의 : 번역이 너무 껄끄러우면 원문을 그대로 사용하겠습니다.

주의 : 허락받고 번역한 것이 아니므로 언제든 내려갈 수 있습니다.

원문 : Performance Tweets series: Barriers, fences, synchronization. GpuOpen.

DX12 시리즈에 오신 걸 환영합니다. 가장 화끈한 주제 중 하나로 들어 가 보죠: 동기화, 즉 배리어와 펜스입니다!

Barriers

배리어는 이전에는 드라이버 단에 숨겨져 있지만 개발자에게 노출된 새로운 개념입니다. 만약 여러분이 이것을 동기화라고 생각한다면, 아주 크게 벗어는 것은 아닙니다. 왜냐하면 이것 또한 배리어의 일부이기 때문입니다. 동기화 부분은 CPU 측에 대해서는 잘 알려져 있습니다: 버퍼를 갱신하는 다중의 쓰기 스레드를 가지고 있고, 모든 쓰기 작업이 종료되도록 만들기 위해서 동기화를 하고, 다중의 읽기 쓰레드를 사용해 데이터를 처리할 수 있습니다. 하지만 그것이 전부는 아닙니다. GPU 배리어가 존재합니다( ResourceBarrier 와 vkCmdPipelineBarrier ). 전체적으로 볼 때 3 가지 기능들이 있습니다:

• Synchronization 은 새로운 작업을 시작하기 전에 이전의 의존성 작업이 완료되는 것을 보장합니다.
• Visibility 는 특정 유닛에서 캐싱되어야 하는 데이터가 그것을 확인하고자 하는 다른 유닛에서 가시적임을 보장합니다.
• Reformatting 은 유닛에 의해서 읽어들여진 데이터가 유닛이 이해할 수 있는 형식임을 보장합니다.

여러분은 리포매팅이 발생하는 경우에 대해서 궁금할 겁니다. 이는 압축을 하는 경우에 종종 요구됩니다. 예를 들어 전통적으로 렌더 타깃은 읽기와 쓰기를 위해 요구되는 대역폭을 줄이기 위해서 압축이 됩니다. GPU 의 어떤 유닛들은 모든 압축 모두를 제공하지는 않으며, 압축해제를 요구합니다. 보통 배리어는 캐시 플러시( cache flush )( 컬러 버퍼, 깊이 버퍼같은 개별 유닛에 붙어 있는 L1 캐시나 좀더 일원화된( unified ) L2 캐시 )로 변환됩니다. 그리고 나서 대기하고( 예를 들어, 결과를 사용하고자 하는 그래픽스 셰이더 이전에 컴퓨트 셰이더가 완료되기를 기다립니다 ), 압축을 해제합니다.

이제 배리어가 뭔지 알게 되었습니다. 그런데 그게 왜 중요할까요? 배리어는 보통 Direct3D 12 와 Vulkan 에서 버그의 온상이 됩니다. 흔들림( flickering ), 깨짐( blocky artifact ), 데이터 손상( corrupted data ), 깨진 지오메트리와 같은 많은 현상들이 잘못된 배리어의 책임일 수 있습니다. 일단, 서브리소스 당 트래킹( per-subresource tracking )을 포함하는 100 % 올바른 배리어가 있다고 가정해 봅시다. 즉 여러분이 텍스쳐 배열의 한 레이어에 쓰기 작업을 하면, 이 레이어는 올바른 상태로 전이( transition )될 필요가 있습니다 -- subresources are often overlooked. You also have to make sure to have all required transitions in place. Some might be easy to overlook like transitioning for presentation.

배리어를 만들었으면, 이제 최적화를 할 시간입니다. Barriers are expensive and every barrier counts. 그것을 요구하는 리소스들만 트랜지션 해야 합니다 -- 그 예로는 텍스쳐로서 읽어들여지는 렌더 타깃이 있습니다. 일반적으로는 쓰기 작업을 하는 리소스보다 더 많은 배리어를 만들어서는 안 됩니다. 다른 모든 리소스들은 프레임 당 트랜지션을 하지 말아야 합니다. 특히 리소스에 대해서 쓰기 작업이 한 번만 수행되고 여러 방식으로 읽어들여진다면, 다중의 읽기-읽기( read-read ) 상태 트랜지션들을 사용하기 보다는, 대부분의 읽기 상태에 대해 리소스를 한 번만 트랜지션하십시오.

배리어를 배칭하는 것도 좋은 성능을 내는 데 있어 중요합니다. 배리어는 GPU 플러싱( flushing )을 요구하므로 배리어 호출 당 더 많은 리소스들을 트랜지션 하십시오. 그러면 배리어를 필요로 하는 모든 리소스들에 대해 단 한 번의 플러싱만이 수행될 것입니다. 이는 성능 향상에 많은 도움이 됩니다 -- 그러므로 가능한 한 배리어 호출들을 배칭하십시오.  이를 구현하는 한 가지 방법은 상태를 식별하는 것입니다. 모든 리소스들은 커맨드 리스트에 존재해야 하며, 커맨드 리스트 시작이나 이전 커맨드 리스트의 끝에서 그것들을 모두 함께 트랜지션하는 것입니다. 물론 실제 및 트랜지션 작업이 실행되기 바로 전에 리소스 상태를 검사하는 안 좋은 패턴은 피해야 할 것입니다 -- 이는 필요한 것 보다 더 많은 트랜지션 호출이 발생하도록 만들 것입니다.

Fences

배리어와 관련이 있는 것으로 펜스가 있습니다( CreateFence 와 vkCreateFence ). 이것들은 CPU 와 GPU 뿐만 아니라 GPU 상의 큐들을 동기화하기 위해서 사용됩니다. 펜스는 매우 무거운 동기화 개체입니다. 왜냐하면 그것은 적어도 GPU 가 모든 캐시들을 플러싱할 것을 요구하며, 잠재적으로 일부 추가적인 동기화를 요구합니다. 그런 비용들 때문에, 펜스는 드물게 사용되어야 합니다. 특히, 프레임 당 리소스들을 그룹화하고, 미세한( fine-grained ) 리소스 당 트래킹을 사용하는 대신에, 단일 펜스를 사용해 함께 트래킹하도록 시도하십시오. 예를 들어, 한 프레임 내에서 사용되는 모든 프레임 버퍼들은 커맨드 버퍼 당 펜스를 사용하기 보다는 하나의 펜스를 사용해서 보호되어야 합니다.

펜스는 컴퓨트 큐, 카피 큐, 그래픽스 큐들을 프레임 단위에서 동기화하기 위해서 드물게 사용될 수도 있습니다. 이상적으로는, 모든 잡들이 종료되는 조짐이 보이는 끝 부분에서 단일 펜스를 사용해서 비동기 컴퓨트 잡들의 큰 배치를 제출하려고 시도하시기 바랍니다. 카피에 대해서도 동일합니다. 가장 가능성있는 성능을 획득하기 위해서 모든 카피의 끝에서 단일 펜스를 사용해서 시그널링을 하십시오.

늘 그렇듯이, 질문이 있으면 편한하게 댓글을 남기거나 Twitter 에 알려 주세요 : @NThibieroz & @NIV_Anteru.

Tweets

02 : 배리어 개수는 쓰기 작업을 하는 리소스 개수와 대충 비슷해야 합니다.

12 : 각 펜스는 ExecuteCommandList 와 비슷한 비용이 듭니다( CPU 와 CPU 비용 ).

22 : 읽기-읽기 배리어를 사용하지 마십시오. 올바른 상태의 리소스를 먼저 획득하십시오.

31 : 항상 리소스를 그것을 작성하는 마지막 큐에서 트랜지션하십시오.

Matthäus Chajdas is a developer technology engineer at AMD. Links to third party sites, and references to third party trademarks, are provided for convenience and illustrative purposes only. Unless explicitly stated, AMD is not responsible for the contents of such links, and no third party endorsement of AMD or any of its products is implied.

주의 : 이 문서는 초심자 튜토리얼이 아닙니다. 기본 개념 정도는 안다고 가정합니다. 초심자는 [ Vulkan Tutorial ] 이나 [ Vulkan Samples Tutorial ] 을 보면서 같이 보시기 바랍니다.

주의 : 완전히 이해하고 작성한 글이 아니므로 잘못된 내용이 포함되어 있을 수 있습니다.

주의 : 이상하면 참고자료를 확인하세요.

정보 : 본문의 소스 코드는 Vulkan C++ exmaples and demos 를 기반으로 하고 있습니다. 

Vulkan 명세 [ 6. Synchronization and Cache Control ] 에서 소개하고 있는 주요 동기화 메커니즘은 다음과 같습니다. 

• Fences : 펜스는 디바이스 상에서 실행되는 어떤 태스크가 완료되었음을 호스트에게 알려주기 위해서 사용될 수 있습니다.
• Semaphores : 세마포어는 여러 개의 큐 사이에서 리소스에 대한 접근을 제어하기 위해서 사용될 수 있습니다.
• Events : 이벤트는 미세한 작업 단위의 동기화( fine-grained synchronization )이며, 단일 큐 내에서만 사용이 가능합니다. 작업의 순서를 지정하기 위해서 사용됩니다.
• Pipeline Barriers : 파이프라인 베리어는 같은 큐에 제출되는 커맨드들이나 같은 서브패스 내의 커맨드들 사이에 종속성을 주입하기 위해 사용됩니다.
• Render passes : 렌더 패스는 거의 대부분의 렌더링 태스크를 위한 유용한 동기화 프레임워크를 제공합니다. 다른 동기화 요소들을 사용하기 보다는 렌더 패스 단위로 동기화하는 것이 효율적입니다.

일단 이 문서에서는 커맨드 제어를 위해서 가장 많이 사용되는 펜스, 세마포어, 배리어에 대해서 알아보도록 하겠습니다.

[ 1 ] 에서는 동기화 개체에 대해 아래와 같이 다이어그램으로 잘 정리해 뒀습니다.

동기화 용례 : 출처 : [ 1 ].

위의 다이어그램에서는 다음과 같은 용례를 보여 줍니다.

• 이벤트를 사용해서 커맨드 버퍼 내의 커맨드들 끼리의 동기화를 보장합니다.
  
• 세마포어를 사용해 큐 사이의 동기화를 보장합니다.
• 펜스를 사용해 호스트와 디바이스 사이의 동기화를 보장합니다.

그런데 멀티스레딩에 대해 "제대로" 공부해 보지 않은 분들은 펜스, 이벤트, 세마포어, 배리어 등의 개념에 익숙하지 않을 겁니다( 저도 그렇습니다 ). 그러므로 그 개념들에 대해서 살펴 보고 오시는 것을 추천합니다. 저같은 경우에는, 이벤트나 세마포어같은 걸 스레드 동기화에 대해 공부하면서 종종 접해 봤지만, 펜스와 배리어라는 개념은 그래픽스를 하면서 처음 봤습니다. 

동기화 개체들에 대해서 대해서 간단하게( ? ) 잘 정리한 분들이 있는데, 아래 링크를 확인하시면 좋을 것 같습니다.

• [ 운영체제 스레드(Thread)는 무엇인가요? ], L2MEN Research Blog.
• [ 운영체제 프로세스 동기화가 무엇인가요? ], L2MEN Research Blog.
• [ 운영체제에서 세마포어(Semaphore)란? ], L2MEN Research Blog.
• [ 세마포어(Semaphore)와 뮤텍스(Mutex) ], 이것저것 내 이야기.
• [ 쓰레드(Thread) 실행순서 동기화 ], hacker dakuo.

사실 뮤텍스와 이벤트는 모두 세마포어의 변종이라고 할 수 있습니다. 뮤텍스는 키가 한개인 세마포어이고, 이벤트는 통지 기능을 가진 뮤텍스나 세마포어죠. 그리고 [ 2 ] 에 의하면 배리어와 펜스는 기존의 드라이버 단에 존재하던 동기화 기법이 호스트단에 노출된 것에 불과합니다.

그러므로 동기화 메커니즘에 사용되는 동기화 개체들에 대해서 사고할 때, 원래의 의미에 대해서 너무 깊게 생각하는 것은 Vulkan 에서 동기화 개체를 사용할 때 혼란의 여지를 준다고 생각합니다. 그래서 어떤 오브젝트에 대해 어떤 시점에 어떤 방식으로 동기화 개체들이 사용되는지를 이해하는 것이 중요하다고 생각합니다.

세마포어

Vulkan 에서 세마포어는 큐들에 제출된 배치들( batches submitted to queues ) 사이에 의존성을 삽입하는 데 사용될 수 있습니다. 세마포어는 시그널( signaled )과 언시그널( unsignaled ) 상태를 가집니다.

세마포어는 커맨드 배치가 완료된 후에 시그널 상태가 변할 수 있습니다. 일반적으로 어떤 배치를 실행하기 전에 세마포어가 시그널 상태로 되기를 기다렸다가, 배치를 실행하기 전에 세마포어를 언시그널 상태로 설정할 수 있습니다. 이 과정을 통해서 순서대로 배치가 실행되도록 보장하는거죠.

다음과 같이 두 개의 커맨드 버퍼가 있다고 가정해 보죠; A 와 B. 그런데 A 와 B 가 순차적으로 제출되는데 반드시 A 의 작업이 종료된 후에 B 가 제출되었으면 한다고 합시다. 그렇다면 동기화를 걸 필요가 있겠죠. 이럴 때 세마포어를 사용할 수 있습니다.

예를 들면  "deferredshadows" 샘플에서는 다음과 같은 식으로 세마포어를 사용해 커맨드버퍼들의 제출 시점을 제어합니다.

void draw() { VulkanExampleBase::prepareFrame(); // Offscreen rendering // Wait for swap chain presentation to finish submitInfo.pWaitSemaphores = &semaphores.presentComplete; // Signal ready with offscreen semaphore submitInfo.pSignalSemaphores = &offscreenSemaphore; // Submit work // Shadow map pass submitInfo.commandBufferCount = 1; submitInfo.pCommandBuffers = &commandBuffers.deferred; VK_CHECK_RESULT(vkQueueSubmit(queue, 1, &submitInfo, VK_NULL_HANDLE)); // Scene rendering // Wait for offscreen semaphore submitInfo.pWaitSemaphores = &offscreenSemaphore; // Signal ready with render complete semaphpre submitInfo.pSignalSemaphores = &semaphores.renderComplete; // Submit work submitInfo.pCommandBuffers = &drawCmdBuffers[currentBuffer]; VK_CHECK_RESULT(vkQueueSubmit(queue, 1, &submitInfo, VK_NULL_HANDLE)); VulkanExampleBase::submitFrame(); }

VkSubmitInfo 에다가 pWaitSemaphores 와 pSignalSemaphores 를 지정하는 것을 확인하실 수 있습니다. pWaitSemaphores 는 종료될 때까지( 시그널링될 때까지 ) 대기해야 하는 세마포어이고, pSignalSemaphores 는 자신이 완료되면 시그널링시킬 세마포어입니다.

배리어와 펜스

배리어와 펜스의 개념에 대해서는 잘 정리한 글들이 있으므로 제가 직접 정리하기 보다는 그것들을 참조하는 게 좋을 것 같습니다.

[ 번역 : Vulkan barriers expained ].

[ 번역 : Performance Tweets series : Barrier, fences, synchronization ].

커맨드 풀

[ 1 ] 에서는 커맨드 풀을 프레임 단위로 유지함으로써 커맨드 버퍼의 라이프사이클을 유지하는 수단으로 사용할 수 있다고 이야기하고 있습니다. 왜냐하면 커맨드 풀을 통째로 리셋함으로써 커맨드 버퍼를 모두 지워버릴 수 있기 때문입니다.

커맨드 풀 자체는 동기화 개체는 아닙니다. 하지만 어떻게 보면 커맨드 버퍼가 삭제되지 않도록 만드는 일종의 배리어같은 역할을 한다는 생각이 듭니다.

정리

벌칸은 여러 종류의 동기화 개체를 가지고 있습니다. 대표적인 것이 세마포어, 배리어, 펜스, 이벤트 등인데요, 각각의 사용처가 다릅니다. 적절한 위치에서 사용하는 것이 중요합니다. 

안타깝게도 이벤트같은 경우에는 자세한 설명이나 샘플을 찾아 볼 수가 없어서 여기에서 정리를 하지 못했습니다.

일단은 개념적인 부분들에 대해서 살펴 보았지만, 기회가 되면 나중에 실제로 구현해 보고 공유하도록 하겠습니다( 아직까지 렌더러 구조에 대해 고민하는 중이라 샘플을 못 만든 상태입니다 ).

참고자료

[ 1 ] Muti-Threading in Vulkan. arm Community.

[ 2 ] Performance Tweets series: Barriers, fences, synchronization. GPU Open.

[ 3 ] Vulkan 1.1 Specification. Khronos Group.

주의 : 이 문서는 초심자 튜토리얼이 아닙니다. 기본 개념 정도는 안다고 가정합니다. 초심자는 [ Vulkan Tutorial ] 이나 [ Vulkan Samples Tutorial ] 을 보면서 같이 보시기 바랍니다.

주의 : 완전히 이해하고 작성한 글이 아니므로 잘못된 내용이 포함되어 있을 수 있습니다.

주의 : 이상하면 참고자료를 확인하세요.

Vulkan 명세의 [ 2.6. Threading Behavior ] 에서는 다음과 같이 이야기하고 있습니다.

Vulkan 은 다중 호스트 스레드를 사용할 때 확장가능한 성능을 제공하도록 설계되어 있습니다. 모든 커맨드들은 다중 스레드에서 동시적으로 호출되도록 지원하고 있습니다. 하지만 특정 파라미터나 파라미터의 요소들은 외부적으로 동기화되도록( externally synchronized ) 정의되어 있습니다. 이는 호출자가 그런 파라미터를 동시에 하나 이상의 스레드에서만 호출되도록 보장해야만 한다는 것을 의미합니다.

좀 더 정확하게 이야기하자면, Vulkan 커맨드들은 Vulkan 오브젝트의 상태를 갱신하기 위한 단순한 저장소( simple stores )들을 사용합니다. 외부적으로 동기화되도록 선언된 파라미터들은 호스트가 커맨드를 실행하는 동안에 언제든 갱신될 수 있습니다. 만약 같은 오브젝트에 대해 동작하는 두 개의 커맨드가 있는데, 둘 중의 하나라도 외부적으로 동기화되도록 오브젝트를 선언했다면, 호출자는 커맨드들이 동시적으로 실행되지 않도록 보장해야할 뿐만 아니라, 그 두 개의 커맨드들이 ( 필요하다면 ) 적절한 메모리 배리어에 의해서 분리되도록 보장해야만 합니다.

요약하자면, Vulkan 은 커맨드를 다중의 스레드에서 실행함으로써 동시성을 보장한다는 것입니다. 하지만 외부 동기화를 요구하는 파라미터( externally synchronized parameter )들을 사용하는 커맨드들은 동시에 실행되서는 안 된다는거죠. 

매우 단순한 예를 하나 들어 보겠습니다. 버퍼 A 와 A 에 쓰기 작업을 하는 두 개의 스레드가 존재한다고 합시다. 그리고 각각의 스레드에서는 개별적으로 커맨드들을 생성했다고 가정하겠습니다. 그러면 각각의 스레드에서 생성한 커맨드들은 서로 관계가 없으므로 동시적으로 실행될 수 있습니다. 하지만 A 에 동시에 쓰기를 할 수는 없겠죠. 그러므로 이런 커맨드들이 동시적으로 실행되지 않도록 보장해 줄 필요가 있습니다.

External Synchronization

"외부적으로 동기화된다( externally synchronized )" 는 의미는 상당히 혼란스럽습니다. 저로서는 상당히 생소한 개념인데요, 일단 구글링을 해 봤습니다. 

그런데 이 용어 자체에 대해서 근본적으로 설명하는 글들은 없고, 대부분이 "Clock Synchronization" 혹은 "Time Synchronization" 에 대한 글들이더군요.

[ 1 ] 에 의하면 internal synchronization 과 external synchronization 의 차이는 다음과 같습니다.

분산 시스템에서 클락 동기화는 보통 하나나 두 개의 목적을 가집니다: (1) 분산 시스템을 구성하는 모든 노드들이 같은 내부 시계( clock )을 소유하는 것을 보장하고, (2) 그 분산 시스템이 다른 외부 시계와 동기화되는 것을 보장합니다.

내부 동기화는 보통 컴퓨팅 클러스터들이 자신들의 로컬 시계들로 동기화되도록 허용하는 동기화 프로토콜을 통해서 수행됩니다. 그 머신은 공통 시간을 사용한다고 동의하는거죠. 하지만, 이 그들이 동의한 시간은 외부 시계와 동기화될 필요는 없습니다. 예를 들면 특정 타임존( time-zone )에 대해서 말이죠.

외부 동기화는 컴퓨팅 시스템들이 NTP 프로토콜을 사용하여 제공되는 서버와 같은 외부 시간에 자신들의 시계가 동기화되도록 만듭니다. 이것의 목적은 컴퓨팅 시스템의 시간을 특정 타임존과 동기화시키는 것입니다. 만약 정확한 시간이 요구된다면, 원자 시계( atomic clock )으로부터 시간을 생성하는 NTP 시스템들이 사용됩니다.

두 경우 모두, NTP 프로토콜이 사용될 수 있으며, 광범위하게 사용됩니다.

결국 Vulkan 명세에서 이야기하는 외부 동기화는 이런 의미가 아니라는 것을 알 수 있습니다. 좀 더 구글링을 해 보니, 다음과 같은 질문이 있었습니다[ 2 ].

컬렉션 프레임워크( collection framework )에서, 왜 외부 동기화가 내부 동기화( Vector, HashTable 등 )보다 빠른가요? 심지어는 같은 메커니즘을 사용함에도 불구하구요?

정확히 내부 동기화와 외부 동기화의 의미가 무엇이며, 그것들이 왜 다른가요?

누가 예제를 가지고 설명해 주면 정말 도움이 될 것 같네요.

답변에서는 외부 동기화에 대해 다음과 같이 설명하고 있더군요.

외부 동기화는 호출자가 synchronized 키워드나 lock 을 사용해서 다중 스레드에서 접근되는 다른 클래스를 보호하는 것을 의미합니다. 이것은 보통 클래스가 자체적으로 동기화되지 않을 때 사용됩니다.

즉 Vulkan 에서의 "외부 동기화"는 오브젝트의 동기화를 오브젝트 외부에서 보장해야 한다는 것을 의미한다고 볼 수 있습니다. 

예를 들자면, 버퍼 A 는 자체적인 동기화 기능을 가지고 있지 않기 때문에, 쓰기 커맨드가 다른 스레드에서 동시에 실행되지 않도록 외부에서 동기화해 줘야 한다는 겁니다. 또한 생성되면 다시는 수정되지 않는 immutable( non-writable ) 속성의 오브젝트들도 다른 스레드에서 사용중일 때 파괴되지 않도록 외부 동기화를 해 줘야만 합니다.

Internal Synchronization

명세에 의하면 어떤 오브젝트들은 내부 동기화를 사용한다고 합니다. 예를 들면 vkCreateGraphicsPipelines() 과 vkCreateComputePipelines() 에서의 VkPipelineCache 파라미터가 있습니다. 이 경우에는 외부 동기화를 하는게 무겁기 때문에 내부 동기화를 한다고 하는군요.

커맨드 파라미터에 대해서 명시적으로 "외부 동기화된다"고 적혀 있지 않다면, 해당 파라미터들은 내부 동기화를 한다고 합니다.

Implicit External Synchronization

명세에 의하면 동기화해야 할 오브젝트가 한 종류 더 있습니다. 묵시적인 외부 동기화인데요, 이 경우는 커맨드의 파라미터와 연관되어 있는 오브젝트들에 대한 외부 동기화를 의미합니다. 예를 들면 Command Pool 과 Descriptor Pool 이 있습니다.

Which objects are externally synchronized?

이제 내부 동기화와 외부 동기화의 개념에 대해서 알게 되었습니다. 하지만 어떤 오브젝트가 외부 동기화되는지 알 수 있을까요?

기본적으로 외부 동기화되거나 묵시적으로 외부 동기화되는 커맨드나 오브젝트의 리스트는 [ 2.6. Threading Behavior ] 섹션에서 찾아볼 수 있습니다. "Externally Synchronized Parameters", "Externally Synchronized Parameter Lists", "Implicit Externally Synchronized Parameters" 라는 항목들에서 그 리스트를 볼 수 있습니다.

물론 이 리스트를 뽑아 놓고 지금 파라미터가 동기화되어야 하는지 찾아 보는 방법도 있지만, 특정 함수에 대해서 동기화 여부를 찾아 볼 수도 있습니다.

예를 들어 "Externally Synchronized Parameters" 리스트에 있는 vkDestroyInstance() 명세에 가보면 "Host Synchronization" 이라는 항목을 볼 수 있습니다.

만약 동기화가 필요하다면 "Host Synchronization" 항목이 반드시 있으므로 이를 확인하시면 됩니다.

정리

Vulkan 오브젝트들은 일부 오브젝트를 제외하고는 외부 동기화를 요구하게 됩니다. VkPipelineCache 같은 특정 오브젝트를 제외한 대부분의 오브젝트가 자체적인 동기화 기능을 내장하고 있지 않으므로, 반드시 외부에서 동기화를 해 줘야 합니다.

외부 동기화의 실례는 다음 글에서 다루도록 하겠습니다.

참고자료

[ 1 ] What is the difference between internal clock synchronization and external clock synchronization in distributed systems?, stack overflow.

[ 2 ] why external synchronization is faster than internal one?, stack overflow.

[ 3 ] Vulkan Specification 1.1, Khronos Group.