주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

다음 그림은 수평 방향으로 던진 물체의 위치를 어떤 단위 시간 간격으로 측정한 기록이다.

( a ) 각 시간 구간의 평균속도 벡터를 그림에 화살표로 나타내라.

( b ) ( a ) 에서 얻은 평균속도 벡터를 각 구간 시작점 시간의 순간속도라 하자. 이때 매시간 구간의 평균가속도 벡터를 그림에 화살표로 나타내라.

( a )

( b )

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

낮은 궤도의 인공위성이 90 분에 지구를 한 바퀴 돈다고 한다. 지구 반지름을 6400 km 라 할 때, 인공위성 빠르기를 시속과 초속으로 나타내라.

낮은 궤도라고 이야기하는 것은 지구 반지름과 인공위성의 높이를 거의 유사하게 취급하겠다는 의미라고 보입니다.

그러므로 인공위성의 궤도가 원이라는 가정하에서, 그 둘레 D 는 다음과 같습니다.

속력은 [이동거리/시간] 이므로 분속 V 는 다음과 같습니다.

시간의 단위를 바꾸면 속력은 각각 다음과 같습니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

인간의 몸을 한 변의 길이가 1/2 m 인 정육면체라고 보면, 인간의 몸은 몇 개의 원자로 이루어져 있는가? 단, 원자를 한 변의 길이가 10^-10 m 인 정육면체로 취급한다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

2-12

정지한 상태에서 일정한 가속도 a 로 운동하는 경우, 거리 x 까지 이동했을 때의 속도를 v² = 2ax 로 나타낼 수 있음을 보여라.

정지한 상태에서의 a 로 등가속도 운동을 할 때 시간과 속도와의 관계를 그래프로 나타내면 아래와 같습니다.

일단 그래프의 기울기가 |a| 이기 때문에 시간 t 에서의 속도 v 는 식 1 과 같이 정의됩니다. 여기에서 식을 단순화하기 위해서 가속도 벡터 a 의 크기인 |a| 를 a 로 나타냅니다( 부연 : 볼드체는 벡터입니다 ).

식 1.

그래프의 면적은 이동거리를 나타내므로 이동거리 x 는 식 2 와 같이 정의됩니다.

식 2.

이 식을 t 에 대해 정리하면 식 3 과 같습니다.

식 3.

식 3 의 t 값을 식 1 에 대입하면 식 4 가 나옵니다.

식 4.

2-13

처음 속도 v₀ 으로 미끄러지던 썰매가 일정한 가속도 크기 |a₀| 로 멈췄다. 멈출때까지 이동한 거리가  임을 보여라.

이 상황을 그래프로 그려 보면 2-12 의 그래프와 반대가 됩니다. 

하지만 여전히 아래 면적이 이동거리입니다. 그렇다고 하면 2-12 에서 유도한 식들에다가 v₀ 와 a₀ 를 할당하면 동일한 결과를 산출할 것입니다.

식 4 를 변형하면 식 5 가 나옵니다.

식 5.

식 5 에  v₀ 와 |a₀| 를 할당하면 다음과 같습니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

2-10

다음 그림은 직선 운동에서 점점 느리게 가는 경우를 나타낸 위치 자료다.

( a ) 각 시간 구간의 속도벡터 방향과 속도벡터의 상대적 크기를 그림에 나타내라.

( b ) 이 운동에서 가속도 방향은 어느 방향인가?

( a )

딱히 "평균속도" 나 "평균가속도" 같은 단서가 붙지 않았기 때문에 두 위치를 연결한 것이 속도벡터이고 그것이 크기를 나타냅니다.

( b )

오른쪽으로 갈수록 속도가 줄어들고 있기 때문에 가속도는 왼쪽방향으로 적용되고 있습니다.

2-11

왼쪽( - ) 방향으로 운동하는 물체의 빠르기가 점점 빨라질 때 평균가속도는 어떤 방향( 부호 )인가?

왼쪽 방향으로 운동하는 물체를 더욱 빠르게 만들기 위해서는 왼쪽으로 가속도가 주어져야 합니다. 그러므로 평균가속도의 방향은 왼쪽( - ) 입니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

일정한 빠르기로 원운동을 하는 물체가 있다. 이 경우 물체가 원을 한 바퀴 도는 데 걸리는 시간을 T 라고 하고, 빠르기를 v₀ 라고 하자. 시계 방향으로 원운동을 하는 물체의 처음 위치를 A 라고 할 때, 그 위치에서의 속도는 접선 방향인 동쪽이 된다. 그리고 시간 T / 4 가 지난 후의 위치 B 에서의 속도는 남쪽을 향한다.

( a ) T / 4 구간에서 속도벡터 변화량 방향, 즉 평균가속도 방향은 어느 방향인가?

( b ) T / 4 구간에서 평균 가속도의 크기가  임을 보여라.

( a )

B 에서의 속도를 v₁ 이라고 할 때, 구간에서의 평균 속도의 방향인 Δv 는 v₁ - v₀ 입니다.

즉, 평속 속도 방향은 남서쪽을 향합니다.

( b )

일정 구간에서 평균가속도의 크기는 다음과 같습니다.

일정한 빠르기로 원운동을 하고 있기에 v₀ 의 속력과 v₁ 의 속력은 동일합니다. 그러므로 피타고라스 정리와 닮은꼴 삼각형의 성질을 이용하면 빗변의 길이를 구할 수 있습니다.√

그림에서 bold 체이면 벡터이고 그렇지 않으면 스칼라라는 점에 주의해 주시기 바랍니다. 그러므로 그림에서 |v₀| = v₀ 입니다.

이제 평균가속도 구하는 식에 값을 대입합니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

어떤 두 시각에서의 속도벡터 v1, v2 가 다음과 같다고 할 때, 평균가속도 벡터를 그림에 표시하라.

"평균가속도" 는 "속도변화량 / 시간변화량" 입니다.

표현을 단순화하기 위해서 일단

t2 - t1 = Δt 

라 하겠습니다. 그러면 평균가속도는 다음과 같습니다.

만약 Δt 가 1 이라면 평균가속도는 그냥 v2 - v1 이 되겠죠.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

달이 원운동을 한 번 하는 데는 약 28 일이 걸린다. 지구 반지름은 6,400 km 고, 지구에서 달까지의 거리는 지구 반지름의 약 60 배다. 달의 빠르기를 시속으로 나타내라.

"시속 = 이동거리 / 시간" 으로 계산되므로 이와 관련한 식을 세워야 합니다.

지구 반지름을 r 이라 하면, 지구에서 달 까지의 거리는 60 r 입니다. 그러면 달이 회전하는 궤도의 반지름이 60r 이라는 의미이며, 그 둘레는 2π * 60r 입니다.

이제 실제 계산을 해 보겠습니다.

달은 지구 주위를 시속 약 3600 km 의 속력으로 회전합니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

원운동에서 원을 한 바퀴 도는 데 걸리는 시간을 주기라 하고, 이를 T 로 나타낸다. 원운동에서 중심점을 원점으로 할 때, 

( a ) 특정 시각의 위치벡터와 그 시각에서부터 1/4 주기 후의 위치벡터를 화살표로 나타내라.

( b ) 변위 벡터를 화살표로 나타내라.

시간 t [second] 에서의 회전각을 θ [radian] 라고 할 때, 시간 T 일 때 θ 는 2pi 입니다. 즉 1 초에 2pi / T 만큼의 각도를 이동하게 됩니다.

반지름이 1 인 원에서 각 θ 일 때의 벡터 r_t 는 ( cos( θ ), sin( θ ) ) 입니다. 만약 반지름이 r 이라 한다면, r_t 는 ( r * cos( θ ), r * sin( θ ) ) 입니다.

여기에서 1/4 주기만큼 이동했다고 하면 그 각 α 는 ( 2pi / T ) / 4 입니다. 정리하면 pi / 2T 입니다.

그러면 θ + α = ( 4 * t + 1 )pi / 2T 입니다.

이제 변위 Δr 은 다음과 같습니다.

실제 벡터를 구하고자 한다면 θ 와 α 에 t 와 T 로 이루어진 식을 할당하면 됩니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

다음 물음들에 답하여라.

( a ) 두 벡터 A, B 가 있을 때, 벡터의 덧셈연산의 정의를 사용하여 다음 관계가 있음을 보여라.

즉 벡터의 덧셈연산은 '교환법칙' 을 만족시킨다.

( b ) 세 벡터 A, B, C 가 있을 때, 다음 관계가 있음을 보여라.

즉 세 벡터에서 덧셈연산은 어떤 순서로 해도 상관없으며, 따라서 '결합법칙' 도 만족시킨다.

( a )

책에서 벡터에 대한 정의를 수학적으로 하지 않은 것으로 봐서는 도식화를 해서 증명하라는 것으로 보입니다.

굳이 수학적으로 증명하자면 다음과 같습니다.

N 차원 벡터 Vn 은 { v1, v2, ..., vn } 이라는 집합으로 정의됩니다. 벡터의 덧셈은 같은 축의 성분끼리의 덧셈입니다.

그러므로 다음이 성립합니다.

각 축 요소들은 스칼라이므로 교환법칙이 성립합니다.

( b )

그림을 그리기 귀찮으니 수학적으로 증명하겠습니다.

각 축 요소들은 스칼라이므로 결합법칙이 성립합니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

2-1

무선 통신에 쓰이는 전자기 파동의 진동수는 1 GHz 다. 여기에서 1 Hz = 1 S^-1 으로 정의하는 양으로, 1 Hz( 헤르츠 ) 는 1 초에 1 번 진동하는 진동수를 뜻한다. 진동수가 1 GHz 인 파동은 1 초에 몇 번 진동하는가?

Giga 는 10⁹ 을 의미하므로 초당 10⁹ 만큼 진동합니다.

2-2

각 변의 길이가 1 nm( 나노미터 ) 인 정육면체 나노입자에는 약 몇 개의 원자가 있다고 추정되는가? 단 원자의 한 변의 길이가 10^-10, 즉 1/10 nm 인 정육면체 형태로 가정하라.

나노입자의 부피는 다음과 같습니다.

원자의 부피는 다음과 같습니다.

나노입자 안의 원자의 개수는 다음과 같이 계산합니다.

나노입자 안에는 원자가 10³ 개 만큼 들어 있습니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

인체는 약 10¹⁵ 개의 세포로 이루어져 있다고 한다. 인체를 이루는 원자의 개수가 10²⁷ 개라면 세포 하나는 약 몇 개의 원자로 이루어져 있는가?

"a" 는 "atomic" 을 의미하고 "c" 는 "cell" 을 의미합니다. 문제는 세포당 원자개수를 구하는 것이기 때문에 다음과 같이 풀수 있습니다.

세포 하나는 약 10¹² 개의 원자로 구성되어 있습니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

공이나 책과 같이 우리가 주위에서 보는 물체의 크기는 1 cm, 1 m 등과 같이 미터 단위로 측정할 수 있다. 우리가 주위에서 볼 수 있는 물체의 원자가 몇 개나 모여서 이루어진 것인지 짐작해 보자.

( a ) 정육면체 모양의 물체의 한 변의 길이를 0.1 m 라 가정하면, 그 부피는 얼마인가?

( b ) 원자의 지름은 10^-10 m 이다. 원자를 한 변의 길이가 10^-10 m 인 정육면체로 본다면, 원자를 차곡차곡 쌓아 ( a ) 의 물체를 이루었을 때 물체 속 원자 개수는 몇 개인가?

( a )

정육면체의 부피를 구하는 식은 한 변의 길이를 n 이라고 할 때 다음과 같습니다.

그러므로 한 변의 길이가 0.1 m 인 정육면체의 부피는 다음과 같습니다.

( b )

한 변의 길이가 10^-10 m 인 원자 정육면체의 부피는  10^-30 [ m³ ] 입니다. 그러므로 물체속의 원자 개수를 다음과 같이 계산할 수 있습니다. "N" 은 "Number" 를 의미합니다. 첨자 "o" 는 "object" 를 "a" 는 "atomic" 을 의미합니다.

정육면체 물체에는 원자가 10²⁷ 개가 들어 있습니다. 

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

원자핵의 반지름이 원자 반지름의 10^-5 일 때, 핵의 부피는 원자 부피의 몇 배인가?

문제를 풀기 전에 책의 설명이 좀 부실해서 부연하고자 합니다. 

[ Units of Measurement ] 에 의하면 소수점 1000 단위마다 밀리( milli ), 마이크로( micro ), 나노( nano )라는 단위로 나뉩니다( 나중에 표 2-2 로 나오기는 하네요 ).

출처 : [ Units of Measurement ].

원자의 중심에 원자핵이 있으므로 원자와 원자핵의 관계는 다음과 같습니다.

원자핵의 반지름을 r 이라 하고 원자의 반지름을 r' 이라고 할 때 다음과 같은 관계식을 만들 수 있습니다.

이를 부피를 구하는 관계식에다가 넣으면 다음과 같습니다. 여기에서 아래첨자 "a" 는 "atomic" 을 "n" 은 "nucleus" 를 의미합니다 .

그러므로 원자의 부피는 원자핵의 부피보다 10¹⁵ 만큼 큽니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

우리가 보는 달과 태양은 크기가 비슷하게 보인다. 태양이 달보다 훨씬 크지만, 달보다 더 멀리 떨어져 있어서 그렇게 보일 뿐이다. 실제로 달까지의 거리는 지구 반지름의 약 60 배이고, 태양까지의 거리는 약 23450 배이다.

( a ) 이로부터 추정되는 태양의 반지름은 달의 반지름의 몇 배인가.

( b ) 태양이 달과 같은 물질로 구성되어 있다고 가정하면( 실제로는 그렇지 않다 ), 태양의 질량은 달의 질량의 몇 배인가?

( a )

지구의 반지름을 r, 달의 반지름을 r', 태양의 반지름을 r'' 이라고 하죠. 그러면 아래와 같은 관계가 형성됩니다.

닮은꼴 삼각형이 두 개가 존재함을 알 수 있습니다. 그러므로,

입니다.

태양은 달보다 약 400 배 정도가 큽니다.

( b )

밀도를 구하는 식은 다음과 같습니다. ρ 는 밀도, M 은 질량, V 는 부피입니다. 

즉 질량은 밀도 곱하기 부피입니다. 같은 물질로 구성되었다고 가정하면 밀도는 동일하므로 결국 질량은 부피에 비례합니다.

구의 부피를 구하는 식은 다음과 같습니다. 잘 모르시는 분들은 [  구의 부피와 구의 겉넓이 ] 를 참고하세요.

그러므로 태양과 달의 질량비는 다음과 같습니다.

그러므로 이 조건에서는 태양이 달보다 약 64,000,000 배 정도 무겁습니다.

원문 : https://www.techpowerup.com/gpu-specs/docs/amd-gcn1-architecture.pdf

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

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

주의 : 우리말로 번역하기 애매한 것들은 그냥 원문으로 씁니다.

정보 : 그림은 클릭하면 새창에 나옵니다. 새창에서 그림위에 + 버튼이 나오면 누르시면 커집니다.

INTRODUCTION

지난 15 년간 ( 역주 : 이 문서는 2012 년에 작성되었습니다 ) 그래픽스 프로세서들은 지속적으로 발전해 왔으며 컴퓨팅 환경[computing landscape]의 필수 요소가 되는 첨단 기술입니다. 첫 번째 디자인들은 적은 유연성을 가진 특정 목적의 하드웨어를 사용했습니다. 그 후의 디자인들은 셰이더 프로그램들을 통해 제한된 프로그램 작성 기능을 소개했으며, 결국에는 많은 그래픽스 목적 기능들을 여전히 유지하면서 고도로 프로그래밍이 가능한 처리량 컴퓨팅 디바이스[throughput computing device]가 되었습니다.

Figure 1: GPU Evolution

GPU 들의 성능과 효율성에서의 잠재력은 믿을 수 없을 정도입니다. 게임들은 산업계 필름 영화들과 비견될 만큼의 가시 품질을 제공하며, 과학 커뮤니티의 얼리 어댑터들은 4 TFLOPS ( Floating point Operations per Second ) 를 초과하는 능력을 갖춘 최첨단 GPU 들을 사용해 크기정도[order of magnitude]( 역주 : 수학에서 서로 다른 크기를 비교할 때 사용되는 크기 등급. 몇 자리 단위의 숫자만큼 차이가 난다는 의미임. 위키백과 참고 바람 )의 성능 향상을 확인했습니다. 전력 효율도 주목할 만합니다; 예를 들면, AMD Radeon[TM] HD 7770M GPU 는 최대 45 W 의 전력 드로[power draw]에서 1 TFLOPS 이상을 달성합니다.

OpenCL[TM], DirectCompute, C++ AMP 와 같은 핵심 산업 표준들은 프로그래머들이 GPU 에 접근할 수 있도록 해 줍니다. 앞으로의 도전은 메인스트림 애플리케이션을 위한 매끄러운 이종 컴퓨팅 솔루션[seamless heterogeneous computing solution]을 제공하는 것입니다( 역주 : GPU 를 그래픽스 전용이 아니라 범용 목적으로 사용할 수 있도록 만들겠다는 의미로 보임 ). 이는 성능과 전력 효율에서의 향상을 수반하지만, 프로그래밍 가능성과 유연성의 향상도 수반할 것입니다. 메인스트림 애플리케이션들은 GPU 와 CPU 모두를 사용하는 현대의 에코시스템[echosystem]과 태블릿에서 슈퍼 컴퓨터에 이르기까지 다양한 형태 인자[form factor]들에 적용될 산업 표준을 필요로 합니다.

AMD 의 Graphics Core Next (GCN) 은 GPU 하드에어를 위한 근본적인 변화를 나타내며, 프로그래밍 가능하고 이종으로 구성된 미래의 시스템들을 위한 아키텍쳐입니다. GCN 은 28 nm 노드에서 전력 및 면적 효율성을 위해 신중하게 최적화되었으며, 몇 년 안에 향후의 공정 기술[process technology]들로 활장될 것입니다.

COMPUTE UNIT OVERVIEW

컴퓨트 유닛[compute unit]들은 GCN 아키텍쳐에서 기본이 되는 계산 빌딩 블록[computational building block]( 역주 : 빌딩 블록이라는 것은 특별한 기능을 수행하도록 미리 만들어 둔 부품을 의미 )입니다. 이러한 CU 들은 완전히 새로운 명령 집합[instruction set]들을 구현합니다. 그 명령 집합들은 이전 디자인에서보다 컴파일러나 소프트웨어 개발자들이 사용하기에 더욱 단순해졌으며 일관된 성능을 제공합니다.

이전 세대의 AMD GPU 들에서, 셰이더 배열[shader array]들은 여러 개의 SIMD 엔진들로 구성되었으며, 각 엔진들은 16 개의 ALU( 역주 : Arithmetic Logic Unit, 산술 논리 장치. 사칙연산과 논리연산을 계산하는 디지털 회로 )로 구성되었습니다. 각 ALU 는 셰이더 컴파일러를 사용해 4 개 혹은 5 개의 독립적인 명령들의 묶음[bundle]들을 VLIW ( Very Long Instruction Word ) 포맷으로 실행할 수 있었습니다. 그 셰이더 컴파일러는 동시에 발행가능한 명령들을 검색하고 스케줄링할 책임이 있었습니다. SIMD 엔진들은 웨이브프런트[wavefront]라 불리는 64 개의 작업 아이템들의 그룹들을 발행받았으며, 한 번에 하나의 웨이브프런트를 실행했습니다. 데이터 플로우 패턴[data flow pattern]에 걸맞는 이 디자인은 그래픽스 처리에서 ( 예를 들어 픽셀 셰이더에서 RGBA 컬러 값들을 조작하기 위해 ) 매우 일반적이며, 대부분의 경우에 높은 수준으로 ( 역주 : GPU 를 ) 지속적으로 활용하는 것을 가능하게 해 줍니다. 하지만 범용 목적 애플리케이션[general purpose application] 관점에서는 기저 데이터 포맷들이 더 복잡해지고 예측불가능해질 수 있습니다. 이는, 매 사이클마다 병렬적으로 실행될 수 있고 처리중인 리소스들을 완전히 활용할 수 있는, 4 개나 5 개의 연산들의 집합을 지속적으로 찾는 것을 어렵게 만듭니다.

GCN 에서는 각 CU 가 벡터 처리를 위한 4 개의 독립된 SIMD 유닛들을 포함합니다. 이러한 각 SIMD 유닛들은 16 개의 작업 아이템들에 대해 하나의 연산을 동시적에 실행합니다만, 각 유닛들은 독립된 웨이브프런트 상에서 동작합니다. 단일 웨이브프런트 내의 독립된 연산들을 찾아내기 위해서 컴파일러에 의존하지 않습니다. 이는 병렬적으로 처리될 수 있는 웨이브프런트들을 찾아내는 데 중점을 둡니다.

Figure 2: VLIW4 vs. GCN

효율성을 위해서, 각 GCN 컴퓨트 유닛 내의 SIMD 들은 전용[private] 리소스와 공유[shared] 리소스들의 조합을 소유하게 됩니다. 버퍼링, 레지스터, 벡터 ALU 같은 명령들은 높은 성능과 활용도를 유지하기 위해서 4 개의 SIMD 들 각각에 대해서 전용됩니다. 프런트-엔드, 브랜치 유닛, 데이터 캐시와 같은 다른 리소스들은 면적 및 전력 효율성을 위해서 SIMD 들간에 공유됩니다.

Figure 3: GCN Compute Unit

GCN 에서 또 다른 핵심적인 혁신은 일관성 캐싱[coherent caching]( 역주 : 여러 스레드에서 동시에 접근해도 '일관성'을 유지할 수 있다는 의미입니다 )입니다. 역사적으로 GPU 들은 메모리의 일관성 뷰[coherent view]를 유지하지 않는 ( 읽기 전용 텍스쳐 캐시들과 같은 ) 특수화된 캐시들에 의존해 왔습니다. GPU 내의 코어들 사이에서 통신하기 위해서는, 프로그래머나 컴파일러가 반드시 명시적인 동기화[explicit synchronization] 명령을 삽입해서 공유된 데이터를 메모리에 플러시[flush]해야 합니다. 이 접근법이 디자인을 단순화해 주기는 했지만, 애플리케이션이 데이터를 공유하는데 있어서 부하를 증가시켰습니다. GCN 은 범용 목적 작업[workload]들을 위해서 설계되었습니다. 이 작업들에서는 코어간 통신 알고리즘이 일반적입니다. 캐시 일관성 규약[cache coherency protocol]은 L2 캐시를 통해 데이터를 공유하며, 이는 그래픽스칩 외부 메모리를 사용하는 것보다 훨씬 더 빠르고 전력 효율이 좋습니다.

캐시 일관성과 함께, GCN 은 하드웨어와 드라이버 지원의 조합을 통해 가상 메모리[virtual memory]를 제공합니다. 가상 메모리는 메모리 관리의 관점에서 거의 대부분의 어려움들을 제거해 주며, 새로운 기능들을 열어 둡니다. 고성능 그래픽스 및 마이크로프로세서에서의 AMD 만의 전문 기술이 특히 도움이 되었습니다. 왜냐하면 GCN 의 가상 메모리 모델은 x86 과의 호환성을 유지할 수 있도록 신중하게 정의되었기 때문입니다. 이는 CPU 와 개별 GPU 사이에서 데이터를 이동시키는 것을 단순화합니다. 더욱 중요한 것은 CPU 와 GPU 에 의해 끊김없이[seamlessly] 공유되는 단일 주소 공간을 위한 길을 열었다는 것입니다. 데이터를 복사하는 것이 아니라 공유하는 것은, 성능 및 전력 효율을 위해 필수이며 AMD 의 Accelerated Processing Units (APUs) 같은 이종 시스템들에서 핵심적인 요소입니다.

CU FRONT-END

( 역주 : 이해를 돕기 위해서 이 챕터에서 설명하는 블록을 구분해 봤습니다. 어둡지 않은 부분입니다.

)

GCN 에서 각 SIMD 유닛은 10 개의 웨이브프런트를 위해 자신만의 40-bit 프로그램 카운터( 역주 : Figure 3 에서 "SIMD" 유닛의 "PC" )와 명령 버퍼(  역주 : Figure 3 에서 "SIMD" 유닛의 "IB" )를 할당받습니다. 즉 전체 CU 들은 40 개의 웨이브프런트들을 동시에 처리할 수 있으며, 각각은 잠재적으로 다양한 작업그룹[work-group]이나 커널[kernel]로부터 올 수 있습니다. 이는 이전 디자인에 비해 훨씬 더 유연합니다. 이는 32 CU 를 가진 AMD Radeon[TM] HD7970 과 같은 GCN GPU 가 동시에 81,920 개의 작업 아이템들에 대해서 동작할 수 있다는 것을 의미합니다.

4 개까지의 컴퓨트 유닛으로 구성된 클러스터[cluster]는 단일 32 KB L1 명령 캐시들을 공유하는데, 이 캐시는 4-way associative( 역주 : "Set Associative Cache" 방식중 하나인데, 간단하게는 캐시 라인이 4 개가 있다고 생각하시면 됩니다. 즉 동시에 4 개의 캐시라인에 접근이 가능합니다 )이며 L2 캐시에 의해 지원[backed by]됩니다. 캐시라인은 64 B long 이며 일반적으로 8 개의 명령들을 저장할 수 있습니다. 캐시가 가득 차면, 새로운 요청은 Least Recently Used( 역주 : 최근에 가장 덜 사용된 ) 캐시 라인을 퇴출시키고 새로운 명령들을 위한 공간을 할당합니다. 공유된 L1 명령 캐시는 4 개의 뱅크[bank]들을 가지며 4 개의 CU 에 대해서 사이클당 32 B 의 명령 전송[instruction fetch]를 유지할 수 있습니다. 명령 전송은 컴퓨트 유닛 내부 SIMD 사이에서 나이, 스케줄링 우선순위, 웨이브프런트 명령 버퍼 활용도에 따라 스케줄링[arbitrate]됩니다( 역주 : AMD 는 "schedule" 대신에 "arbitrate" 라는 용어를 사용하는 것으로 보입니다. 꼭 AMD 만 그런 것은 아닌 것 같고 일반적으로 사용하는 용어로 보입니다. 역자는 익숙함 때문에 "스케줄링"을 사용하겠습니다 ).

일단 명령들이 웨이브프런트 버퍼들에 전송되고 나면, 다음 단계는 명령들에 대한 디코딩[decoding] 및 발행[issuing]입니다. 컴퓨트 유닛은 각 사이클에 하나의 SIMD 를 선택해서 디코딩 및 발행을 수행하는데, 라운드-로빈 스케줄링[round-robin arbitration]을 사용합니다( 역주 : 프로세스들 사이의 우선순위를 두지 않고 시간단위로 작업을 할당하는 방식입니다 ). 선택된 SIMD 는 10 개의 웨이브프런트 버퍼로부터 5 개까지의 명령들을 디코딩해 실행 유닛[execution unit]으로 발행합니다. 추가적으로, 특별한 명령( 예를 들어 NOP, 배리어[barrier], 중단[halt], 예측된 벡터 명령 건너뛰기[skipping] 등 )들은 어떠한 기능 유닛[functional unit]들을 사용하지 않고 웨이브프런트 버퍼 내부에서 실행될 수 있습니다. 각 CU 들은 16 개의 버퍼를 가지고 있는데, 이는 배리어 명령들을 트래킹[track]합니다. 배리어는 웨이브프런트를 전역적으로 동기화하게 만듭니다.

CU 프런트엔드는 7 개의 다양한 종류의 명령들을 디코딩하고 발행할 수 있습니다: 브랜치[branch] 명령, 스칼라[scalar] ALU 명령, 스칼라 메모리 명령, 벡터 ALU 명령, 벡터 메모리 명령, 지역 데이터 공유[local data share] 명령. 전역 데이터 공유[global data share] 및 익스포트[export] 명령, 특수[special] 명령. SIMD 당 각 타입에 대해서 하나의 병령만이 한 번에 제출될 수 있습니다. 이는 실행 파이프라인[execution pipeline]의 한계를 초과하지 않기 위함입니다. 실행 순서를 보존하기 위해서, 각 명령들은 서로 다른 웨이브프런트로부터 와야만 합니다; 각 SIMD 에 대해서 10 개의 웨이브프런트를 가지고 있으므로, 일반적으로 그것으로부터 선택할 수 있는 많은 경우의 수가 있습니다. 이러한 두 가지 제약하에서, 모든 혼합[mix]이 허용되며, 이는 컴파일러가 다양한 방식으로 실행을 위한 명령을 발행할 수 있도록 자유도를 부여합니다.

CU 프런트엔드는 매 사이클 당 5 개의 명령들을 발행할 수 있습니다. 이는 2 개의 레지스터 파일을 사용해 여섯 개의 벡터 실행 파이프라인과 스칼라 실행 파이프라인들을 혼합합니다. 벡터 유닛들은 그래픽스 셰이더 뿐만 아니라 범용 목적 애플리케이션들을 위해서 핵심이 되는 계산 능력을 제공합니다. 명령 버퍼에서 다뤄지는 특수 명령들과 함께 두 개의 스칼라 유닛들은 GCN 아키텍스쳐에서 모든 제어 흐름[control flow]들을 담당합니다.

SCALAR EXECUTION AND CONTROL FLOW

( 역주 : 이해를 돕기 위해서 이 챕터에서 설명하고 있는 블록을 구분해 봤습니다. 어둡지 않은 부분입니다 

)

성능 및 전력 효율성을 위해서 GCN 컴퓨트 유닛에는 새로운 스칼라 파이프라인들이 필수입니다. 제어 흐름 처리는 셰이더 코어[shader core]들을 통해서 분산[distributed]되어 있는데, 이는 응답지연[latency]를 줄이고 중앙화된 스케줄러[centralized scheduler]를 사용해서 통신하기 위한 전력 부하[power overhead]를 피할 수 있게 해 줍니다. 특히 그래픽스보다는 더 복잡한 제어 흐름을 가지는 범용 목적 애플리케이션을 위해 유용합니다.

각 컴퓨트 유닛들은 8 KB 의 스칼라 레지스터 파일을 가지는데, 이것은 각 SIMD 를 위해 512 개의 엔트리[entry]들로 나뉘어 있습니다. 이 스칼라 레지스터들은 SIMD 상에 존재하는 10 개의 웨이브프런트들 모두에 의해서 공유될 수 있습니다; 웨이브프런트는 112 개의 사용자 레지스터와 구조적 상태[architectural state]를 위해 예약되어 있는 몇 가지 레지스터들을 할당할 수 있습니다. 이 레지스터의 크기는 32 비트이며, 64 비트 값을 저장할 수 있도록 하기 위해서 연속적인 엔트리들이 사용될 수 있습니다. 웨이브프런트 제어 흐름을 위해 이것이 필수적입니다; 예를 들어, 웨이브프런트 내의 64 개의 작업아이템들 각각에 대해 비교[comparison]하는 결과를 산출할 수 있습니다.

첫 번째 스칼라 파이프라인은 조건 분기[conditional branch]를 다루는데 명령에 인코딩되어 있는 16 비트 부호있는 옵셋[singed offset]을 사용합니다. 이는 또한 특정 유형의 동기화와 인터럽트[interrupt]를 다룰 책임이 있습니다. 인터럽트는 GCN 에서 추가된 완전히 새로운 기능입니다. 이는 디버깅을 위한 핵심 기능입니다. 왜냐하면 그것들은 중단점[breakpoint]을 위해 제어 흐름을 재전송[redirect]할 수 있기 때문입니다.

두 번째 스칼라 파이프라인은 완전한 정수 ALU 입니다. 이는 주소 생성 유닛[address generation unit, AGU]로 기능하여 스칼라 데이터 캐시로부터 데이터를 읽어들입니다. 실제 ALU 는 64 비트 크기입니다. 이 파이프라인은 점프[jump], 콜[call], 리턴[return]을 포함한 다양한 제어 흐름 명령들을 돕습니다. 이것들은 예전의 프로그램 카운터를 인접한 레지스터들로 구성된 64 비트 값으로 대체[replace]( 혹은 교체[swap] )함으로써 처리됩니다. 예측[prediction]도 스칼라 ALU 에 의해서 관리되는데, 분기[fork] 연산과 병합[join] 연산을 관리하기 위해서 보조 하드웨어[assist hardware]를 사용합니다.

스칼라 L1 데이터 캐시는 읽기 전용 구조입니다. 스칼라 파이프라인들은 주로 제어 흐름과 궁합이 맞기 때문에, 메모리에다가 결과를 다시 써야 할 필요가 없습니다. 그것의 구조[organization]는 L1 명령 캐시와 매우 유사합니다. 16 KB 스칼라 데이터 L1 은 4-way associative 이며 64 B 라인 및 LRU replacement( 역주 : LRU 에 의해서 페이지를 교체하는 정책 )를 가지고 있습니다; 또한 4 개까지의 컴퓨트 유닛으로 구성되어 있는 클러스터 사이에서 공유되며, L2 캐시에 의해 지원됩니다. 스칼라 읽기는 4 개의 64 B long 이며 인접한 스칼라 레지스터를 채웁니다. 그것은 4 개의 뱅크들을 가지며, 4 개의 컴퓨트 유닝에 대해서 사이클당 16 B 의 처리량을 가지고 있습니다. 스칼라 데이터 L1 캐시는 이전 세대에 존재하던 상수 캐시[constant cache]를 대체합니다. 왜냐하면 그것이 좀 더 유연하기 때문입니다.

VECTOR EXECUTION

( 역주 : 이해를 돕기 위해서 이 챕터에서 설명하고 있는 블록을 구분해 봤습니다. 어둡지 않은 부분입니다. VECTOR EXECUTION, VECTOR REGISTER, VECTOR ALUS 챕터는 모두 이 부분에 대해서 설명합니다.

)

GCN 의 엄청난 처리 성능은 고수준으로 병렬화된 SIMD 에서 나옵니다. SIMD 는 범용 목적 애플리케이션과 최신 그래픽스를 위한 계산을 수행합니다. GCN 에서는 더 나은 프로그래밍 가능성과 일관된 성능을 제공하기 위해서 SIMD 가 완전히 점검[overhaul]되었습니다.

이전의 VLIW 컴퓨트 유닛 아키텍쳐는 단일 SIMD 를 가지고 있었지만, 그것들은 단일 웨이브프런트로부터 병렬 연산들을 실행하도록 요구되었습니다. 이는 2 개의 직접적인 결과를 가지고 있었습니다. 첫째, 성능은 컴파일러에 의해서 근본적으로 제한되었습니다; 웨이브프런트 내 병렬성을 띄고 있는 작업들이 적다면 하드웨어가 별로 활용되지 못했습니다. 만약 웨이브프런트 내에 2 개의 명령만이 병렬적으로 실행될 수 있다면, 성능의 절반이 사용되고 있지 않은 것입니다. 두 번째 결과는 컴파일러가 레지스터 파일에 대한 읽기와 쓰기를 주의 깊게 스케줄링해야만 한다는 것입니다; 포트 충돌[port conflict]이 발생하면 하드웨어 활용도가 떨어지기 때문입니다. 잠재적인 포트 충돌을 제거하기 위해서, 웨이브프런트들은 ALU 연산들을 밀집해서[back-to-back] 발행할 수 없었습니다. 그래서 지연을 감추기 위한 웨이브프런트들이 끼워 넣어졌습니다[interleaved]. VLIW 아키텍쳐는 그래픽스를 위해서 상대적으로 좋기는 했지만, 복잡한 작업들에 대해서는 성능 예측이 잘 되지 않았으며 스프트웨어 튜닝을 열심히 해야 했습니다.

GCN 아키텍쳐는 더 단순하며 성능이 훨씬 더 좋습니다. 근본적인 변화는 웨이브프런트 내의 예측불가능한 명령어 수준 병렬화를 피하는 것입니다. 그리고, 하드웨어를 포화상태로 만들기 위해서, 소프트웨어가 적절한 개수의 데이터 병렬 웨이브프런트[data parallel wavefront]들을 공급하도록 하는 것입니다. 이는 GPU 들을 사용하는, 특히 범용 목적의 작업들을 위해 사용하는, 애플리케이션을 위해서 엄청난 이점을 제공합니다.

VECTOR REGISTERS

GCN 아키텍쳐의 가장 큰 이점 중 하나는 더욱 단순하고 고성능을 가진 벡터 레지스터 파일 디자인입니다. 각 SIMD 가 독립적인 웨이브프런트를 실행하고 있기 때문에, 레지스터 파일은 4 개의 독립적인 슬라이스[slice]들로 나뉠 수 있습니다.

벡터 범용 목적 레지스터들 (vGPRs) 은 64 개의 레인[lane]들을 포함하는데, 각 레인은 32 비트 크기까지 될 수 있습니다. 인접한 vGPR 들은 64 비트 혹은 128 비트 데이터들로 조합됩니다. 각 SIMD 는 64 KB 파티션[partition]으로 된 vGPR 들을 가집니다. 그래서 CU 를 위한 전체 레지스터의 개수는 일정합니다. 각 SIMD 파티션은 매우 강력하게 뱅크화되어 있으며, X 레지스터들을 읽고 Y 레지스터들을 쓸 수 있습니다.

레지스터 파일로부터의 대량의 대역폭[bandwidth]은 포트 충돌을 줄여주며, 이는 벡터 ALU 명령들이 SIMD 내에 끼워져 있지 않고 조밀하게 발행될 수 있다는 것을 의미합니다. 이는 컴파일러의 작업을 엄청나게 단순화해주며, 개발자가 고성능의 코드를 작성할 수 있도록 해 줍니다.

VECTOR ALUS

각 SIMD 는 16 개의 레인 벡터 파이프라인을 포함합니다. 이는 예측가능하며 단일 정밀도 및 배정밀도 소수점 연산, 최고 속도 비정규화[full speed denormal], 모든 올림 모드[rounding mode]를 지원하는 IEEE-754 표준과 완전하게 호환됩니다. 각 레인들은 single precision fused or unfused multiply-add 연산이나 24 비트 정수 연산을 자연스럽게 실행할 수 있습니다. 정수 multiply-add 는 작업 그룹[work-group] 내에서 주소를 계산하는데 특히 유용합니다. 웨이브프런트는 단일 사이클에서 SIMD 에 발행되지만, 64 개의 작업 아이템을 위한 연산을 모두 실행하려면 4 사이클이 걸립니다.

GCN 은 벡터 ALU 에다가 새로운 미디어[media] 및 이미지[image] 처리 명령들을 추가했습니다. 특히, 2 개의 새로운 명령들이 존재합니다: 4x1 sum-of-absolute-differnces (SAD) 와 quad SAD 인데, 이는 8 비트 색상을 가진 32 비트 픽셀 상에서 동작합니다. 이러한 새로운 명령들을 사용하면, 컴퓨트 유닛은 사이클당 64 개의 SAD 를 실행할 수 있습니다. 이는 클럭[clock]당 256 개의 연산들을 옮기는[translate] 것입니다. 이 명령들은 매우 강력하며 제스쳐 인식이나 비디오 검색과 같은 최신의 GPU 애플리케이션들을 위해 필수적입니다. 예를 들어 AMD 의 Steady Video 2.0 기술은 새로운 SAD 및 QASD 명령을 사용해 실시간에 녹화되고 스트리밍되는 비디오로부터 흔들림[shakiness]을 제거합니다.

배정밀도 및 32 비트 정수 명령들은 SIMD 내부에서는 감소된 속도로 실행됩니다. GCN 아키텍쳐는 유연하며, 배정밀도 성능은 단일 정밀도 성능에 비해 1/2 에서 1/16 이며, 그에 따라 지연도 증가합니다. 배정밀도 및 32 비트 정수 성능은 특정 GCN 구현에서는 매우 안 좋을 수 있으며, 이는 대상 애플리케이션에 의존하고 있습니다.

64 비트 초월 함수[transcendential function]나 IEEE 나누기와 같은 더 복잡한 명령들은 마이크로 코드[microcode]에 의해 지원됩니다. SIMD 는 개선된 분기 유닛의 이점을 이용해 하드웨어에서 부동소수점 예외[exception]를 제공히기도 하고, 벡터 조건 코드를 위해 스칼라 GPR 을 사용하기도 합니다.

LOCAL DATA SHARE AND ATOMICS

GCN 과 같은 처리량 컴퓨팅 플랫폼에서는, 통신 및 동기화가 고성능을 보장하기 위해 필수입니다. 특히나 최신의 범용 목적 애플리케이션에 대해서는 더욱 그러합니다. 지역 데이터 공유는 명시적으로 주소화된 메모리입니다. 이는 제 3 의 레지스터 파일로서 기능하는데, 특히 작업 그룹내에서의 동기화나 그래픽스를 위한 보간을 위해서 사용됩니다.

Figure 4: Local Data Share (LDS)

GCN 에서 LDS 용량[capacity]은 16 비트나 32 비트 뱅크를 가진 64 KB 로 두 배가 되었습니다( 제품마다 다릅니다 ). 각 뱅크는 512 개의 엔트리들을 포함하는데, 각 엔트리들의 크기는 32 비트 크기입니다. 뱅크는 모든[all-to-all] 크로스바[crossbar]에서 32 비트 값들을 읽거나 쓸수 있으며( 역주 : 크로스바는 특별한 의미는 아닌 것 같고 메모리 상에 중간중간 막대처럼 영역이 배치되어 있어서 크로스바라고 부르는 것 같습니다 ), 32 비트 아토믹 정수 유닛[atomic integer unit]을 포함한 유닛을 스위즐[swizzle]할 수 있습니다( 역주 : 스위즐은 여러 개로 구성된 컴포넌트의 값들을 선택적으로 혼합하는 기능입니다. 예를 들어 rgba 를 rrrr 로 만들수도 있고 abgr 로 만들수도 있습니다 ). 일반적으로 LDS 는 각 사이클에 서로 다른 두 개의 SIMD 로부터 16 개의 레인들을 합칩니다[coalesce]. 그래서 두 개의 웨이브프런트들이 매 4 사이클마다 완료됩니다. 웨이브프런트로부터 온 32 개의 레인들에 대해서 충돌이 자동으로 검출되며 하드웨어 내부에서 리졸브[resolve]됩니다. 같은 뱅크 내에서 서로 다른 요소에 접근하는 명령은 종료되기 위해서 추가적인 사이클을 소비합니다. 브로드캐스트[broadcast]들은 투명[transparent]하며( 역주 : 브로드캐스트하는 방식이 사용자에게 노출되어 있지 않다는 의미인듯. 아마도 비트수를 지정할 필요가 없다는 말이 아닌가 싶음. ), 8, 16, 32 비트 데이터는 어떠한 제약도 없이 벡터 ALU 명령을 위한 입력 피연산자[operand]로서 사용될 수 있습니다.

그래픽스의 경우, LDS 는 텍스쳐 데이터 상에서 최고 속도 보간을 수행하는데 사용하는데 사용되며, 접근 패턴 덕분에 충돌이 발생하지 않는다는 것이 보장됩니다. 범용 목적 컴퓨트 커널의 경우, SIMD 는 LDS 에서 데이터를 로드하고 저장할수 있습니다. 이를 통해 산란[scatter] 혹은 수집[gather] 접근을 사용하여 캐시 계층을 오염시키는 것을 피할 수 있습니다. 혹은 이를 사용해 캐시 대역폭을 증폭시킬 수도 있습니다. 추가적으로, 아토믹 유닛들은 작업 그룹 내부에서 고성능 추론[reduction]을 사는 데 있어 필수적입니다. 그리고 그것은 부동소수점 최대[max], 최소[min], 그리고 비교[compare] 및 교환[swap] 연산들을 수행할 수 있습니다.

LDS 명령들은 주소[address], 2 개의 데이터 값들, 그리고 목적지[destination]를 사용합니다. 주소는 vGPR 로부터 오고, 목적지는 vGPR 이거나 LDS 를 직접적으로 읽고 있는 SIMD 일수 있습니다. 2 개의 데이터 값들은 L1 데이터 캐시 ( LDS 에 저장하기 위해 ) 나 vGPR ( 로드하거나 저장하기 위해 ) 로부터 올 수 있습니다. 다른 디자인들과는 다르게, 전용 파이프라인은 LDS 를 레지스터에 로드하는 것과 같은 데이터 이동을 위해서 벡터 ALU 명령을 사용하지 않습니다.

EXPORT

익스포트 유닛은 고정 함수 그래픽스 하드웨어와 전역 데이터 공유 ( GDS ) 에 대한 컴퓨트 유닛의 윈도우[window]입니다. 모든 계산이 종료되었을 때, 일반적으로 그 결과는 그래픽스 파이프라인의 다른 유닛들로 전달됩니다. 예를 들어 픽셀이 셰이딩되고 나면, 그것들은 일반적으로 디스플레이에 대한 최종 출력 이전에 깊이 테스트와 스텐실 테스트, 그리고 블렌딩을 위한 렌더 백엔드[render back-end]로 전달됩니다. 익스포트 유닛은 결과들을 그래픽스 파이프라인의 프로그래밍 가능한 스테이지로부터 테셀레이션[tessellation] 스테이지나 래스터화[rasterization] 스테이지, 그리고 렌더 백엔드와 같은 고정 함수 스테이지로 전달됩니다.

GDS 는 지역 데이터 공유와 동일합니다. 단지 그것이 모든 컴퓨트 유닛에 의해 공유될 수 있어서 모든 웨이브프런트들 사이에서 명시적인 전역 동기화 지점으로서 기능한다는 차이가 있습니다. GDS 의 아토믹 유닛들은 좀 더 복잡하며 순서있는 카운트 연산들을 다룰 수 있습니다.

VECTOR MEMORY

While the SIMDs in each Compute Unit can execute 128 floating point operations per clock cycle, delivering enough bandwidth to match the impressive computational resources. GCN 에서 거의 대부분의 중요한 변화는 의심할 여지가 없이 캐시 계층에 존재합니다. 이는 그래픽 디자인에 매우 특화되어 있는 구조에서 고성능 및 프로그래밍 가능한 계층 구조로 변경되었습니다. 이 구조는 범용 목적 애플리케이션과도 잘 들어 맞고, x86 프로세서와의 통합을 위해서 준비되었습니다. 이 변화들은 컴퓨트 유닛들 내부에서 시작되었지만, 전체 시스템을 통해 확장되었습니다.

GCN 메모리 계층은 가상 메모리 지원과 훌륭한 아토믹 연산 성능을 가진 통합된[unified] 읽기/쓰기 캐싱 시스템입니다. 이는 이전 세대에서 사용되었던 독립된 읽기 캐싱 및 쓰기 버퍼링 패스[path]에 대한 중대한 개선이 있었음을 보여 줍니다. 벡터 메모리 연산들은 주소, 데이터를 위한 다양한 처리량[granularity]을 지원하는데, 이것은 32 비트부터 128 비트 쿼드[quad]까지의 범위를 가집니다.

Figure 5: Vector Memory

L1 데이터 ( L1D ) 캐시는 16 KB 이며 4-way set associative 인데, 64 B 라인들과 LRU replacement 를 가지고 있습니다. 이는 L2 및 다른 캐시들처럼 극단적으로 느슨한[relaxed] 일관성[consistency] 모델이라는 점에서 일관됩니다. 개념상으로는 L1D 캐시는 L2 캐시를 통한 궁극적인 전역 일관성과 함께 작업 그룹 일관성을 가집니다. L1D 는 더티 바이트 마스크[dirty byte mask] 를 사용하는 write-through, write-allocate 디자인을 가지고 있습니다( 역주 : write-through, write-allocate 는 캐시 쓰기 정책입니다. "문c 블로그"의 [ Cache -Policies ] 에 잘 정리되어 있습니다 ). 캐시라인은 웨이브프런트 명령의 모든 64 ( 역주 : 64 개의 레인 ) 가 저장을 완료할 때 L2 에 다시 써집니다. 더티 데이터를 가진 라인들도 역시 L1D 에 유지됩니다. 반면에 부분적으로 깨끗한 모든 라인은 L1D 캐시에서 추방됩니다. 특별한 일관성 로드 명령도 존재합니다. 그것은 L2 캐시로부터 불러와[fetch] 가장 최근의 값이 사용되었음을 보장합니다( 역주 : 실제로 사용한게 아닌데 사용했다고 우선수위를 높이는듯? ).

AGU 가 합병된 주소[coalesced address]를 계산하고 나면, 그 요청은 L1D 캐시 태그들을 탐색합니다. 맞는게 존재하면[ On a hit], 그 캐시는 전체 64 B 라인을 읽어 냅니다. 완전히 합병된 요청들을 사용하면, 이것은 웨이브프런트의 16 개의 데이터 값 혹은 1/4 와 연관됩니다. 비록 낮은 지역성[poor locality]로 인해 부가적인 사이클이 필요하긴 합니다. 계산 작업을 위해 캐시 라인은 vGPR 나 LDS 에 작성됩니다.

L1D 캐시에 저장하는 것은 약간 더 복잡합니다. 쓰기 데이터는 적절한 저장소 포맷[storage format]으로 변환되어야 하며, 그리고 나면, 맞는 캐시를 찾고 궁극적으로 L2 캐시로 쓰기를 하기 전에, 쓰기 주소가 가능하면 새로운 독립된 트랜잭션으로 합쳐집니다.

만약 메모리 요청이 L1D 캐시에서 실패하면, 그것은 통일되고 일관성 있는 L2 캐시로 전달됩니다. 이것은 셰이더 코어의 외부에 존재하며 메모리 컨트롤러들과 연관됩니다.

효율성을 증진시키고 부하를 줄이기 위해서, 약간 전용 하드웨어를 사용하는 유연한 메모리 계층이 그래픽스를 위해 재사용됩니다. 주소 생성 유닛은 사이클당 4 개의 텍스쳐 주소를 받습니다. 그리고 나서 16 개의 샘플링 주소를 가장 가까운 이웃을 위해 계산합니다. L1 데이터 캐시로부터 샘플들이 읽혀지고 텍스쳐 매핑 유닛[Texture Mapping Unit]( 혹은 TMU )에서 압축이 해제됩니다. 그리고 나서 TMU 는 클럭당 가능한 한 4 개의 보간된 텍셀[texel]을 산출하기 위해서 인접 샘플들을 필터링합니다. TMU 출력은 원하는 포맷[desired format]으로 변환되며 궁극적으로 이후의 사용을 위해 벡터 레지스터에 작성됩니다. 어떤 값들을 그래픽스 커널의 메모리로 쓰기위해서 사용되는 포맷 변환 하드웨어[format conversion hardware]도 존재합니다.

L2 CACHE, COHERENCY AND MEMORY

GCN 에서 분산된 L2 캐시는 GPU 에서 일관성의 핵심입니다. 그것은 읽기 전용 L1 명령들과 스칼라 캐시들을 위한 후방 방어벽[backstop]으로 기능합니다. 이는 CU 클러스터들에 의해 공유되며, 모든 CU 내의 L1 데이터 캐시에 의해서도 공유됩니다. L2 캐시는 물리적으로는 메모리 채널들과 쌍을 이루는 슬라이스로 구분됩니다. 그리고 컴퓨트 유닛에서 캐싱된 메모리 파티션까지 이어진 크로스바 섬유[crossbar fabric]를 통해서 흐름에 접근합니다.

Figure 6: Cache Hierarchy

L1 데이터 캐시와 마찬가지로 L2 는 가상으로 주소화되어 있습니다. 그래서 TLB( 역주 : Translation Lookaside Buffer. 가상주소를 물리 주소로 변환하는 캐시 ) 가 전혀 필요하지 않습니다. L2 캐시는 16-way associative 이며, 64 B 캐시 라인과 LRU replacement 를 가집니다. 그것은 write-back, write-allocate 디자인이며, 그래서 L1 데이터 캐시에서의 모든 쓰기 실패[write miss]를 흡수합니다. 각각의 L2 슬라이스는 64 KB 에서 128 KB 이며 L1 캐시들에 64 B 캐시 라인을 전송할 수 있습니다.

일관성 L2 캐시의 가장 큰 이점중 하나는 그것이 전역 아토믹 연산을 실행하고 서로 다른 웨이브프런트 사이에서 동기화를 하기 위한 가장 자연스런 위치라는 점입니다. 웨이브프런트 내부의 아토믹 연산을 위해서 LDS 가 사용될 수 있지만, 어떤 지점에서는, 서로 다른 웨이브프런트들로부터의 결과들이 합쳐질 필요가 있습니다. 이것이 정확히 L2 가 활동하게 되는 위치입니다. L2 슬라이스는 각 사이클에 캐시 라인에 대해 가능한 한 16 개의 아토믹 연산들을 실행할 수 있습니다.

GCN 의 전체적인 일관성 규약은 하이브리드 모델입니다. 이는 GPU 의 엄청난 성능과 대역폭을 전통 CPU 의 프로그래밍 가능성과 함께 녹여냅니다. 관점이 미래의 통합을 향해 있습니다. 개념상으로는 L1 데이터 캐시는 작업 그룹 내의 지역 접근을 위한 엄격한 일관성을 유지합니다. 웨이브프런트의 작업이 끝나는 시점이나 배리어가 실행되면, 그 데이터는 L2 로 작성되며 GPU 전체에 대해 전역적인 일관성이 됩니다.  이 모델은 종종 이완된 일관성[relaxed consistency]로서 설명되며 많은 이점을 가지고 있습니다. 수많은 지역 접근들은 낮은 부하와 높은 성능을 가지게 되지만, L2 는 프로그래머 친화적인 일관성을 제공합니다.

똑같이 중요한 것은, 캐시 계층이 x86 마이크로 프로세서들과 통합하기 위해서 설계되었다는 것입니다. GCN 의 가상 메모리 시스템은 4 KB 페이지들을 지원할 수 있으며, 이것은 x86 주소 공간을 위해 자연스러운 매핑 단위[granularity]입니다 - 미래의 공유된 메모리 공간을 위한 길을 연 것입니다. 사실 DMA( 역주 : Direct Memory Access, CPU 를 통하지 않고 메모리에 직접 접근하는 것 ) 전송을 위해 사용되는 IOMMU 가 이미 x86 주소 공간으로의 요청을 변환하여 데이터를 GPU 에 옮기는 데 도움을 주고 있으며 이 기능은 시간이 지날 수록 발전할 것입니다. 추가적으로, GCN 에서 캐시들은 64 B 라인들을 사용하는데, 이것은 x86 프로세서들에서의 크기와 같습니다. 이는 GPU 와 CPU 사이에서 전통적인 캐싱 시스템을 통해서 프로그래머가 명시적으로 제어하지 않고도 투명하게 데이터를 공유하기 위한 ( 이종 시스템들을 위한 ) 단계를 설정합니다.

메모리 컨트롤러는 GPU 들을 서로 묶으며 시스템의 거의 모든 파트들에 데이터를 제공합니다. 커맨드 프로세서, ACE, L2 캐시, PBE, DMA 엔진, PCI Express, 비디오 가속기, 크로스파이어 상호연결[Crossfire interconnection], 디스플레이 컨트롤러 등은 모두 지역 그래픽스 메모리에 대한 접근을 합니다. 각각의 메모리 컨트롤러들은 64 비트 크기이며, 두 개의 독립적인 32 비트 GDDR5 메모리 채널로 구성되어 있습니다. 저가 제품의 경우에는 GDDR5 가 DDR3 로 대체될 수도 있습니다. 메모리 처리량을 늘리기 위해서, GDDR5 컨트롤러는 채널당 두 개의 DRAM 을 사용하여 용량을 뻥튀기하기 위해 clamshell mode 에서 동작할 수도 있습니다.

PROGRAMMING MODEL

GPU 의 성능은 애플리케이션 프로그래밍 인터페이스[Application Programming Interface]( API )를 통해 발휘됩니다. 이는 개발자들을 위한 일관된 인터페이스를 제공하는 추상화입니다. 결정적으로, API 는 다양한 GPU 패밀리들 뿐만 아니라 하드웨어 세대들과 소프트웨어를 넘나 드는 호환성을 제공합니다. 그 목적은 프로그래머가 기반 하드웨어에 대한 걱정을 하지 않고 애플리케이션에만 집중할 수 있게 하는 것입니다.

업계 표준을 만족시키기 위해서 새로운 GCN ISA 가 디자인되었습니다. AMD 의 이종 시스템 아키텍쳐[Heterogeneous System Architecture] ( HSA ) 는 이종 컴퓨팅을 위한 모델로서 구상되었습니다. 그것은 CPU 와 GPU 가 통신하는 방식을 정의하며, 가상 ISA ( HSA 중간 언어[Intermediate Language] ) 를 포함합니다. 이것은 하드웨어마다 구현이 다릅니다. HSAIL 코드는 기반 하드웨어에서 동적으로 컴파일됩니다( 아마도 Vulkan 의 spir-v 같은 느낌인듯 합니다 ). 즉 모든 벤더의 CPU 와 GPU 에 대해 호환됩니다. GCN 은 HSAIL 에 대한 완벽한 지원을 제공하며, 그 이유는 부분적으로는 더욱 유연한 명령어 집합[instruction set]으로 전환하기 위함입니다.

GCN 은 산업 표준 컴퓨트 API 들에 애한 완벽한 지원을 합니다. 특히 OpenCL[TM] 1.2, DirectCompute 11.1, C++ AMP 와 호환되는 첫 번째 GPU 입니다. 이러한 표준들을 사용함으로써, 프로그래머들은 모든 운영체제를 대상으로 하고 다양한 하드웨어 상에서 호환되는 애플리케이션을 작성할 수가 있습니다. 이러한 산업 표준들은 개발자를 위해 성공적인 장기 로드맵[long term loadmap]을 보장해 주며, 불확실한 미래에 독점 프로그래밍 모델이나 하드웨어 플랫폼을 피하기 위해서 필수적입니다.

그래픽스 영역에서, GCN 은 DirectX 11.1 을 위해 준비되었으며, 이는 Windows[(R)] 8 에 소개될 것입니다. 그리고 세 가지 특별한 핵심 기능을 포함합니다. 첫 번째는 타깃-독립적인 래스터화입니다. 이것은 2D 이미지들을 위한 래스터화를 고정 함수 그래픽스 하드웨어로 이동시킵니다. 이는 CPU 로부터 2D 안티 에일리어싱[anti-aliasing]을 없애버리며, 동일한 이미지 품질을 제공하면서 전력을 줄이게 됩니다. 두 번째 변경은 범용 목적 데이터 배열 ( Unordered Access View 라 불립니다 ) 들이 6 가지 유형의 프로그래밍 가능한 셰이더와 비디오 가속을 위해서 이용될 수 있다는 것입니다. 이는 전체 GPU 프로그래밍 가능성을, 컴퓨트와 픽셀 셰이더로 국한하는 것이 아니라, 그래픽스와 비디오 API 를 통해서 확장합니다. 마지막으로 DirectX[(R)] 11.1 은 Stereo 3D 를 위한 표준 API 를 포함합니다. 이는 특정 벤더용 미들웨어나 서드 파티 미들웨어의 단편화된 에코시스템[ecosystem]들을 대체합니다.

GCN 에는 범용 목적 프로그래밍 가능성과 관련한 매우 중요한 개선점들이 많이 존재합니다만, 그것들은 그래픽스의 문맥에서도 유리합니다. 예를 들어, 개발자는 Partially Resident Texture (PRT) 를 사용하여 거의 무한대의 텍스쳐 디테일을 가진 월드를 생성할 수 있습니다. GPU 의 가상 메모리 시스템은 메모리에 필요한 부분만을 로드합니다. GCN 에서는 32 TB 까지의 가상 메모리가 텍스쳐를 위해 사용될 수 있습니다. 이것이 실제 가용 메모리를 줄이기 때문에, 드라이버와 GPU 는 텍스쳐를 64 KB 타일 단위로 필요한 만큼 페이징합니다. 이 절차는 투명하며( 역주 : 프로그래머가 제어할 수 없다는 말임 ), 프로그래머가 명시적으로 데이터를 메모리에 프리로딩해야 하는 수고를 덜어 줍니다. PRT 는 id Tech 5 와 같은 선도적인 멋진 게임 엔진들에서 이미 사용중이며, 차세대의 게임 엔진들과 히트한 게임들에서 일반적이 될 것입니다.

SYSTEM ARCHITECTURE

궁극적으로, GCN 은 2-3 W 로 제한되는 태블릿에서 전체 건물을 채우는 슈퍼컴퓨터에 이르기까지 다양한 종류의 제품에서 사용될 것입니다. 이는 성능 및 파워의 스펙트럼이 100 배 정도 차이가 남을 보여주며, 극단적으로 다른 환경들을 보여 줍니다. 고성능 GPU 들은 일반적으로 전용 고 대역폭 메모리 서브시스템을 가지고 있으며 크로스파이어로 연결되어 작동할 수도 있습니다. 여기에서 렌더링은 최대 성능을 위해 다중 GPU 들 사이에서 분할됩니다. 반대로 고도로 통합되어 있는 태블릿이나 PC 를 위한 System-On-Chip 은 CPU, GPU, 그리고 다른 On-die 컴포넌트 사이의 메모리 컨틀롤러를 공유할 것입니다. 이러한 다양성을 다루기 위해서, GCN 의 시스템 아키텍쳐는 범용 목적 셰이딩 코어들과 고정 함수 그래픽스 하드웨어에서의 범용성과 확장성을 위해 재설계되었습니다.

GCN 은 호스트 프로세서와의 인터페이싱을 위해서 PCI Express[TM] 3.0 을 사용하는 첫 번째 아키텍쳐입니다. AMD Radeon[TM] HD 7970 같은 GCN 기반 독립 GPU 들은 16 배의 링크를 사용하는데, 이것은 32 GB/s 의 대역폭을 제공합니다. 이 CPU to GPU 인터페이스는 범용 목적 작업에서는 특히 병목이 됩니다. 여기에서 거대 데이터 집합들은 두 프로세서 사이에서 움직입니다. GCN 은 두 개의 양방향 DMA 엔진들을 가지고 있어서, 두 개의 데이터 스트림들이 동시에 PCI Express[TM] 3.0 링크의 모든 방향을 사용할 수 있으며 효율적으로 가용 대역폭을 이용합니다.

DMA 엔진들은 x86 마이크로 프로세서에 대한 AMD 의 경험이 성과를 올린 영역입니다. GCN 은 I/O 메모리 관리 유닛[Memory Management Unit] (IOMMU) 를 포함하는데, 이는 GPU 를 위한 x86 주소를 투명하게 매핑할 수 있습니다. 이는 GCN 의 DMA 엔진들이 페이지화가 가능한 CPU 메모리에 쉽게 접근할 수 있으며, 데이터를 이동시키기 위해서 주소 변환을 하는 부하를 가지고 있지 않음을 의미합니다. IOMMU 는 이종 시스템 통합을 더욱 강하게 하는 단계이며 시간이 지날 수록 발전할 것입니다.

GCN 커맨드 프로세서는 고수준 API 커맨드를 드라이머로부터 받아서 다양한 처리 파이프라인으로 그것들을 매핑할 책임이 있습니다. GCN 에는 두 개의 주요 파이프라인들이 존재합니다. 비동기 컴퓨트 엔진[Asynchronous Compute Engine] (ACE) 은 컴퓨트 셰이더를 관리하며, 반면에 그래픽스 커맨드 프로세서는 그래픽스 셰이더와 고정 함수 하드웨어를 다룹니다. 각 ACE 는 커맨드의 병렬 스트림을 다룹니다. 그리고 그래픽스 커맨드 프로세서는 각 셰이더 유형을 위한 개별 커맨드 스트림을 가질 수 있으며, GCN 의 멀티 태스킹의 이점을 살리기 위해서 풍부한 작업을 생성하게 됩니다.

스케줄링은 GCN 이 산업을 발전시키고 있는 또 다른 영역입니다. 멀티 태스킹을 위해서는 가상 메모리가 필요하며, 그래서 메모리에 대한 경쟁적인 요청을 하는 애플리케이션들이 안전하게 동시에 존재할 수 있습니다. 멀티 태스킹은 1980 년대 이래로 컴퓨터에서 일반적이며, 프로그래머의 생산성을 위해서 매우 가치가 있습니다. GCN 은 기본적인 기반[infrastructure]을 생성하고 고수준으로 병렬화된 GPU 의 활용도와 효율성을 증신시키기 위해서 멀티 태스킹을 사용합니다.

ACE 는 모든 컴퓨트 셰이더 스케줄링과 리소스 할당을 다룹니다. 제품은 다수개의 ACE 를 가질 수 있으며, 그것들은 성능의 관점에서 확장하거나 축소하기 위해서 서로 독립적으로 동작하게 됩니다. 각 ACE 는 캐시나 메모리로부터 커맨드를 불러와서 태스크 큐를 형성합니다. 이는 스케줄링의 시작점입니다. 각 태스크들은 스케줄링을 위해 background 로부터 real-time 까지의 우순위 레벨을 가지고 있습니다. ACE 는 가장 높은 우선순위 태스크에 대한 하드웨어 요청을 검사하여, 리소스를 충분하게 이용할 수 있을 때 그 태스크를 GCN 셰이더 배열로 보낼[dispatch] 것입니다.

많은 태스크들이 동시에 실행될 수 있습니다; 이 제한은 하드웨어 리소스에 의해서 많아지거나 적어질 수 있습니다. 태스크는 순서없이[out-of-order] 완료되며, 이는 리소스를 일찍 릴리스하지만, 정확성을 위해서는 ACE 에서 트래킹되어야만 합니다. 태스크가 GCN 셰이더 배열에 보내질 때, 그것은 여러 개의 작업 그룹으로 분할되는데, 작업 그룹들은 실행을 위해서 개별 컴퓨트 유닛들로 보내질 수 있습니다. 매 사이클마다, ACE 는 작업그룹을 생성하고 작업그룹에서 하나의 웨이브프런트를 컴퓨트 유닛으로 보냅니다.

ACE 는 보통 독립적인 방식[fashion]으로 연산을 수행하지만, 그것들은 캐시, 메모리, 혹은 64 KB 전역 데이터 공유를 사용하여 동기화하거나 통신할 수 있습니다. 이것은 ACE 가 실제로는 태스크 그래프를 형성할 수 있다는 것을 의미하며, 여기에서 개별적인 태스크들은 서로에 대한 의존성을 가지게 됩니다. 그래서 실제로는, ACE 안의 태스크는 다른 ACE 나 그래픽스 파이프라인의 태스크들에 의존하고 있을 수 있습니다. 예를 들어, 현재 실행중인 태스크 그래프가 의존성때문에 그래픽스 파이프라인으로부터의 입력을 위해 대기하고 있다면, ACE 는 스케줄링될 준비가 되어 있는 다른 태스크 큐로 전환할 수 있습니다. ACE 는 이전 태스크와 연관된 모든 작업그룹을 플러싱할 것이고, 그리고 나서 새로운 태스크로부터의 작업그룹을 셰이더 배열에 발행할 것입니다.

GRAPHCIS ARCHITECTURE

그래픽스 커맨드 프로세서는 전통적인 렌더링 파이프라인을 형성합니다. 3D 파이프라인은 여러 유형의 프로그래밍 가능한 셰이더들( 예를 들어, vertex, hull, domain, geometry, pixel shader )과 삼각형과 픽셀을 조작하는 다양한 고정함수 하드웨어로 구성되어 있습니다. 셰이더 성능은 매우 가변적입니다. 그러므로 진짜 문제는 고정 함수 하드웨어를 확장하는 것입니다.

3D 렌더링은 클럭 당 단일 삼각형을 조립[assemble]하는 프리미티브 파이프라인에서 시작합니다. GCN 에서 프리미티브 파이프라인의 개수는 성능 요구사항과 연관되어 매우 다양합니다. 다중 프리미티브 파이프라인은 화면 공간을 분할하고 올바른 삼각형 순서를 유지하기 위해 동기화에 의존합니다. 그리고 조립된 삼각형은 버텍스 셰이딩과 헐[hull] 셰이딩을 위한 셰이더 배열로 전달됩니다. 헐 세이더는 버텍스 좌표를 테셀레이션 좌표로 옮기고 제어 정보를 설정합니다.

프리미티브 파이프라인은 도메인을 2-64 개의 더 작은 오브젝트로 실제로 분할하는 테셀레이션 스테이지를 위한 고정 함수 하드웨어도 포함하고 있습니다. GCN 의 테셀레이터는 이전 세대보다 4 배까지 빠릅니다. 훨씬 느린 off-chip 메모리 대신에 일관성 L2 캐시를  더 큰 파라미터 캐시를 이용할 수 있는 더 큰 파라미터 캐시를 사용합니다. 테셀레이션 이후에는 도메인 셰이더가 오는데, 이것은 분할된[tessellated] 출력을 표준 버텍스로 변환하고 그 결과를 지오메트리 셰이더로 넘깁니다.

다른 주요 그래픽스 함수들은 픽셀 파이프라인에 집중되어 있습니다. GCN 픽셀 파이프라인들은 스크린 공간을 독립적인 타일로 분할함으로써 확장됩니다. 버텍스를 픽셀로 변환하는 실제 레스터화가 첫 번째 작업입니다. 각 래스터라이저는 사이클당 단일 삼각형을 읽어들일 수 있으며, 16 개의 픽셀을 쓸 수 있습니다. 나중에 계층적인 Z 테스트를 통해서 이전 픽셀 셰이딩에 의해서 가려진 픽셀들을 제거하게 됩니다.

타일 안에서 조각화된[fragmented] 픽셀들이 셰이딩되고 나면, 그것들은 렌더 백엔드[Render Back-End] (RBE) 로 흘러들어 갑니다. RBE 는 뎁스 테스트, 스텐실 테스트, 알파 테스트를 적용하여 픽셀 조각이 최종 프레임에서 가시화되어야 하는지를 결정합니다. 그리고 나서 가시화된 픽셀 조각들은 커버리지[coverage] 와 컬러[color]를 샘플링해 최종 출력 픽셀을 생성합니다. GCN 의 REB 는 16 KB 컬러 캐시로부터 픽셀당 8 개 까지의 컬러 샘플들( 예를 들어 8x MSAA )에, 4 KB 의 뎁스 캐시로부터 픽셀당 16 개의 커버리지 샘플들( 예를 들어 16x EQAA 까지 )에 접근할 수 있습니다. 컬러 샘플들은 최종 안티 에일리어싱 픽셀 컬러를 생성하기 위해서 커버리지 샘플들에 의해서 결정되는 가중치[weight]들을 사용해 블렌딩될 수 있습니다. 그 결과는 메모리 컨트롤러들을 통해서 프레임 버퍼로 작성됩니다.

그래픽스 파이프라인은 ACE 와 동일한 기술 집합을 사용해서 조직되었습니다. 3D 파이프라인의 각 스테이지들은 ACE 처럼 동시에 실행될 수 있습니다. 프리미티브 및 픽셀 파이프라인들은 크로스바 섬유를 통해서 프로그래밍 가능한 GCN 셰이더에 연결됩니다. 그 태스크 큐는 다른 셰이더와 고정 함수 하드웨어에 대해 캐시나 메모리를 통해 동기화됩니다.

The advantage of GCN's flexibility is evident in the first few products that have scaled across all four dimensions. AMD Radeon[TM] HD 7970 은 스크린을 2 개의 프리미티브 파이프라인과 4 개의 픽셀 파이프라인으로 분할합니다. 그리고 셰이딩을 위해서 32 개의 컴퓨트 유닛과 384 비트의 메모리 인터페이스를 사용합니다. GCN 픽셀 파이프라인들은 2 개의 REB 와 3 개의 메모리 컨트롤러로 조직화되어, 메모리 대역폭에서 50 % 의 향상이 있었습니다. 반대로, AMD Radeon[TM] 7770 GHz 에디션은 단일 프리미티브 파이프라인, 2 개의 픽셀 파이프라인, 10 개의 컴퓨트 유닛을 가지고 있습니다. 7770 에디션에서의 픽셀 파이프라인들은 2 개의 메모리 컨트롤러로 축소되었으며, 128 비트 크기의 인터페이스를 사용합니다.

Figure 7: AMD Radeon[TM] HD 7970

Figure 8: AMD Radeon[TM] HD 7870 GHz Edition

Figure 9: AMD Radeon[TM] HD 7770 GHz Edition

PROGRAMMABLE VIDEO PROCESSING

범용 프로그래밍 가능성은 전체 GCN 아키텍쳐 사이에서 최 우선순위입니다. 특히 비디오 처리가 그러합니다. 비디오의 유일한 특징중 하나는 그것들이 매우 특정된[specific] 데이터 유형이며 고정 함수 하드웨어의 이점을 취할 수 있는 많은 기회가 존재한다는 것입니다. 비디오 전용 UVD3 디코더 엔진이 MPEG-4 와 DivX 포맷을 지원하기 위해서 추가되었으며, 이와 함께 Multi-View Codec 이 추가되어 Stereo 3D 와 HD picture-in-picture  디스플레이에서 사용됩니다.

Figure 10: Hybrid Video Encoding

GCN 은 전력 효율성을 가진 비디오 코덱 엔진[Video Code Engine] ( VCE ) 을 통합했는데, 이는 60 frames/sec 로 1080p 를 재생할 수 있는 H.264 인코딩에 대한 완벽한 하드웨어 구현을 포함합니다. 그러나 VCE 는 프로그래밍을 고려해 두고 명시적으로 설계되었습니다 - VCE 의 엔트로피 인코딩 블록[entropy encoding block] 은 소프트웨어에 완전하게 접근할 수 있습니다. AMD 의 Accelerated Parallel Programming SDK 와 OpenCL[TM] 을 사용하는 개발자는 custom motion estimation, inverse discrete cosine transform, motion compensation 을 하드웨어 엔트로피 인코딩과 함께 사용하는 하이브리드 인코더를 생성하여 실시간 인코딩보다 더 빠른 결과를 얻을 수 있습니다.

RELIABLE COMPUTING

범용 목적 컴퓨팅은 어느 정도 수준의 신뢰성을 요구하는데, 이는 전통적인 그래픽스 월드보다는 훨씬 큽니다. 하지만 AMD 에게는 매우 친숙합니다. 2003 년 이후로 AMD 의 Opteron 프로세서들은 세계에서 가장 큰 슈퍼 컴퓨터와 업무 전용 시스템[mission critical system] 들의 일부로서 사용되어 왔습니다. 이런 시스템들은 고장시간[downtime]과 데이터 손상[corruption]은 허용하지 않습니다. AMD 는 매우 신뢰도 있는 디자인을 하는 경험을 했고, 서버 룸, 슈퍼 컴퓨터, 단일 워크스테이션, 게이밍 노트북 등의 어떠한 시스템에서라도 적용이 가능한 제품을 생성하기 위해서 GCN 아키텍쳐에 그 경험을 적용했습니다. GCN 아키텍쳐의 중요한 목표는 신뢰성이지만, 보증되지 않은 상황에서의 부하는 피해야 합니다.

현대 칩들에서의 가장 큰 신뢰성은 on-chip 메모리에서의 soft errors ( 혹은 bit-flips ) 입니다. AMD Radeon[TM] HD 7970 과 같은 고성능 GPU 는 12 MB 가 넘는 SRAM 과 CU 및 캐시들을 통해 퍼져 있는 레지스터 파일들을 가지고 있습니다. GCN 은 single error correct 와 double error detect ( SECDED ) 를 모든 on-chip 메모리를 위해 완벽히 다룰 수 있도록 설계되었습니다. 이는 면적과 전력 측면에서 약간의 부하를 가지고 있습니다만, 정확하고 신뢰성있는 결과가 필수적인 전문 애플리케이션에서는 별로 중요하지 않을 수 있습니다.

두 번째 신뢰성 문제는 외부 메모리입니다. GDDR5 는 산업 표준에 기반하고 있으며 매우 다양한 서드 파티들에 의해서 제조되고 있습니다. 표준 GDDR5 메모리 인터페이스는 CRC 를 사용해서 전송된 데이터를 검사하고 손상된 데이터를 반송합니다. 그러나 ECC 는 존재하지 않습니다. 즉 DRAM 이 가지고 있는 데이터가 soft error 에 의해서  손상되었는지 여부를 알 방법이 없습니다.

GCN 메모리 컨트롤러는 SECDED 를 DRAM 에 적용하는 선택적인 모드를 가지고 있습니다. ECC 로 보호되는 데이터는 약 6% 정도 커지는데, 이는 전체적인 메모리 용량과 대역폭을 약간 감소시킵니다.

아키텍쳐로서 GCN 은 전문적인 제품이나 소비자 제품을 위해서 커스터마이징이 가능합니다. 전문적인 애플리케이션들은 최소한의 성능 저하와 함게 최대한의 신뢰성을 제공하기 위해서 on-chip SRAM 과 선택적인 외부 DRAM 을 위한 ECC 보호의 이점을 취할 수 있습니다. ECC 를 지원하는 CPU 제품은 그래픽스 드라이버를 통해 그것을 활성화하거나 비활성화할 수 있습니다.

CONCLUSION

( 역주 : 그냥 내용 요약이 아니라 AMD 자랑이라서 번역이 귀찮아졌네요. 건너 뜁니다 )

AMD's GCN Architecture comes at a time of change for the industry. Graphics is an increasingly important part of the user experience, and a crucial component for SoCs that integrate CPUs and GPU side-by-side. The mandate for GPUs is expanding to include not just 3D rendering, but new general purpose, heterogeneous applications such as facial recognition, which are only feasible using the parallel performance of the GPU.

As a company, AMD is uniquely positioned with deep expertise and a long history of excellence in both CPUs and GPUs for the PC. GCN is a marriage of these domains, melding the reliability and programmability of traditional CPUs with the efficient parallel performance of a GPU.

GCN is huge step forward, firmly placing AMD in the new era of heterogeneous computing, but without losing sight of efficiency or performance. The GCN Architecture encompasses innovations such as virtual memory, coherent caching and an elegant hybrid vector/scalar instruction set that are revolutionary. At the system level, GCN is the only discrete graphics architecture that is compatible with the x86 programming model, paving the way for future software and hardware integration.

Most importantly, AMD has carefully crafted an architecture that is a tremendous advance in programmability, but does not sacrifice performance or efficiency. Features such as a unified instruction stream and scheduling in the scalar pipelines enhance utilization and boost the achievable performance on real workloads. The first GPUs manufactured on 28nm were based on GCN and improved performance/watt and performance/mm2 by roughly 50% over the prior generation. The AMD Radeon™ HD 7970 GHz Edition achieves peak performance of over 1 TFLOPS double precision and 4 TFLOPS single precision, a testament to the underlying architecture. GCN will eventually revolutionize AMD's entire product line, from tablets to supercomputers.

DISCLAIMER

The information presented in this document is for informational purposes only and may contain technical inaccuracies, omissions and typographical errors. AMD reserves the right to revise this information and to make changes from time to time to the content hereof without obligation of AMD to notify any person of such revisions or changes.

AMD MAKES NO REPRESENTATIONS OR WARRANTIES WITH RESPECT TO THE CONTENTS HEREOF AND ASSUMES NO RESPONSIBILITY FOR ANY INACCURACIES, ERRORS OR OMISSIONS THAT MAY APPEAR IN THIS INFORMATION.

AMD SPECIFICALLY DISCLAIMS ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR

PURPOSE.

IN NO EVENT WILL AMD BE LIABLE TO ANY PERSON FOR ANY DIRECT, INDIRECT, SPECIAL OR OTHER CONSEQUENTIAL DAMAGES ARISING FROM THE USE OF ANY INFORMATION CONTAINED HEREIN, EVEN IF AMD IS EXPRESSLY ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.

원문 : Highly divisible triangular number

삼각수

일단 삼각수라는 것이 무엇인지 찾아 봤습니다. 위키백과에 따르면 삼각수란 다음과 같습니다[ 1 ].

삼각수(三角數, triangular number), 또는 "삼각형 수" 는 일정한 물건으로 삼각형 모양을 만들어 늘어 놓았을 때, 그 삼각형을 만들기 위해 사용된 물건의 총 수가 되는 수를 말한다.

예를 들어 아래와 같이 네 줄에 걸쳐 삼각형을 만들었을 때 늘어 놓은 물건의 총 수는 10 개가 되며, 10 은 삼각수의 하나가 된다.

n 번째 삼각수 N 은 1 부터 n 까지의 자연수를 모두 합한 것이고, 여기서 삼각수의 정의로 인하여 n 은 반드시 자연수여야 한다. 삼각수의 수열은 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 230... 과 같고 n 번째의 삼각수 N 은 N = n( n + 1 ) / 2 로 나타낼 수 있다. 모든 자연수는 최대 3 개의 삼각수의 합으로 표현할 수 있다는 정리가 있으며, 이는 카를 프리드리히 가우스가 1796 년( 가우스의 일기에 따르면 7월 10일 )에 증명하였다. 이 정리는 모든 자연수는 최대 n 개의 n 각수의 합으로 표현할 수 있다는 페르마의 다각수정리의 한 경우이다.

Solution

일단 먼저 n 번째 삼각수를 찾아야 합니다. 위키백과를 보지 않았다면 어쩔 수 없이 무식하게 삼각수를 더하면서 찾았겠죠. 

이 문제는 일단 해결이 되었습니다. n 번째 삼각수를 n( n + 1 ) / 2 로 나눌 수 있다고 했기 때문에 n 을 증가시켜가면서 삼각수를 찾는 것이 가능합니다. 그래도 진짜 식이 맞는 건지 확인을 해 보도록 하겠습니다. 

일단 위의 그림에서 삼각형의 1, 3, 6, 10 은 삼각수를 구성합니다. 패턴을 보니 숫자의 개수가 1, 2, 3, 4 이런 식으로 증가하는군요. 결국 삼각형의 행을 구성하는 마지막 숫자는 이것은 1 부터 n 까지의 자연수의 합을 구하는 문제와 같습니다. 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4, N = n( n + 1 ) / 2 입니다.

다음 문제는 이것의 인수를 찾는 건데요, 안타깝게도 문제에 있는 28 의 경우를 보면 소인수가 아니라 그냥 인수입니다. 일단 소인수를 다 구한다음에 그것을 곱해가면서 5 개의 인수로 만들어낼 수 있는지 찾아야 합니다.

저는 여기에서 하나의 규칙을 찾았습니다.

N = a * b 라 했을 때, a 는 [ 1, N / 2 ) 범위의 자연수입니다. 왜냐하면 a 가 1 일 때 b 가 N 이니까, a 가 2 일 때 가장 큰 b 가 나오기 때문이죠.

그리고 a 와 b 는 가능한 몫들을 나열했을 때 아래 그림처럼 대칭을 이루며 몫의 개수가 짝수가 됩니다.

하지만 28 의 경우를 보면 a 의 범위가 [ 1, 14 ) 가 되는데 그 범위에 7 이 들어 있습니다. 이렇게 되면 대칭이 안 되기 때문에 b 가 이미 a 로 선정이 된 경우에는 배제해야 합니다. 이를 자연스럽게 배제할 수 있는 방법을 생각해 봤습니다.

인수의 관점에서 생각해 봤습니다. b <= N / a 입니다. 그리고 a <= N / b 입니다. 여기에서 a == b 일 때가 a 의 최대값입니다. 그렇다면 N = a² or b² 이므로, a 는 다음과 같은 범위를 가진다고 할 수 있습니다: [ 1, root( N ) ]. 매우 간단한 사실인데 이상한 고민을 했군요.

마지막으로 몫의 개수에도 예외가 있습니다. N 이 제곱수일 경우입니다. 이 경우에는 몫이 홀수개가 나옵니다. 왜냐하면 제곱이니 a 와 b 가 동일하기 때문이죠. 위에서 1 의 몫도 홀수이고 36 의 몫도 홀수입니다. 그러니 N 이 제곱수라면 계산할 필요도 없겠죠. 문제에서 500 개의 몫을 가진다고 했기 때문에 몫의 개수가 짝수입니다. 그러므로 N 이 제곱수일 경우를 배제해야 합니다.

import math i = 0 while( True ) : tn = int( i * ( i + 1 ) / 2 ) # make triangulr number i += 1 # increase number for next loop root = math.sqrt( tn ) # get square-root nroot = int( root ) # get natural number of square-root if root == nroot : # if root is natural number continue # goto next number if( nroot < 250 ) : # if root is less than 250 continue # goto next number count = 0 # reset factor count for factor in range( 1, nroot + 1 ) : # for each number if 0 == ( tn % factor ) : # check if remainder is 0 count += 2 # add 2 factors if 500 == count : # if number of fa-ctors is 500 print( tn ) # print it break # break while

하지만 10 분이 지나도록 답이 없었습니다. 이렇게 해결하는 것은 좋은 답이 아닐 것 같다는 생각이 들더군요. 좀 더 규칙을 찾아 보기로 했습니다.

n 번째 삼각수가 n( n * 1 ) / 2 라고 하지만, 이것을 잘 살펴 보면 결국 n 번째 삼각수는 기존의 n 번째 삼각수에서 n 개 만큼 더한 것이라는 것을 알 수 있습니다.

그렇다면 다음과 같이 구현할 수 있습니다.

prev_tn = 0 i = 1 while( True ) : tn = prev_tn + i # make triangulr number prev_tn = tn # set previous triangular number i += 1 # increase number for next loop root = math.sqrt( tn ) # get square-root [ ... ] [ ... ]

그런데 아무래도 몫의 종류가 500 개라는 것을 최적화할 수 있는 방법이 떠 오르지 않더군요.

결국 다른 사람의 구현( Jason's code blog )을 찾아 봤습니다.

n 과 n + 1 의 소인수 분해를 알고 있다고 하면 그것을 다음과 같이 작성할 수 있습니다.

n 과 n + 1 은 어떤 소인수도 공유할 수 없다는 것에 주목하십시오( 왜냐하면 그것들은 연속적인 숫자이기 때문입니다 ). 그리고 우리는 pi 와 qi 가 구별되는 소수임을 알고 있습니다. 또한 n 이나 n + 1 은 둘 중에 하나만 2 로 나눠집니다. 그러므로 지수 ei 와 fi 만이 T( n ) 을 나누는 숫자를 결정하기 위해서 고려할 필요가 있는 것들입니다. T( n ) = ( n( n + 1 ) )/2 는 n 이나 n + 1 의 인수분해에서 두 숫자의 제곱을 배제할 필요가 있다는 것을 의미합니다( 둘중의 하나만의 짝수라는 것을 기억하세요 ). 일관성을 지키기 위해서 n 이 짝수이고 p = 2 라고 가정해 봅시다. 그러면 T( n ) 의 전체 인수의 개수는 다음과 같은 조합으로 표현될 것입니다:

더 개선하자면, 삼각수를 증가시킬 때, 이전의 n 은 이미 계산했기 땜누에 n + 1 만 계산해도 됩니다. 이는 실시간 비용을 조금이라도 줄여줄 것입니다.

그래서 다음과 같이 하더군요.

import time def num_divisors(n): if n % 2 == 0: n = n/2 divisors = 1 count = 0 while n % 2 == 0: count += 1 n = n/2 divisors = divisors * (count + 1) p = 3 while n != 1: count = 0 while n % p == 0: count += 1 n = n/p divisors = divisors * (count + 1) p += 2 return divisors def find_triangular_index(factor_limit): n = 1 lnum, rnum = num_divisors(n), num_divisors(n+1) while lnum * rnum < 500: n += 1 lnum, rnum = rnum, num_divisors(n+1) return n start = time.time() index = find_triangular_index(500) triangle = (index * (index + 1)) / 2 elapsed = (time.time() - start) print "result %s returned in %s seconds." % (triangle,elapsed)

결과는 76576500 입니다.

참고자료

[ 1 ] 삼각수. 위키백과.

한 동안 뜸했습니다.

개인적으로 진행하는 VulkanMonkey 라는 프로그램의 UI( WPF ) 에서 사용할 노드그래프 라이브러리를 만드느라 한 달 가까이 시간을 소비했네요.

GitHub 의 [ lifeisforu/NodeGraph ] 에 MIT 라이선스로 공개해 놨으니 필요한 분들은 사용하시면 될 것 같습니다. NUGET 에 [ Lifeisforu.NodeGraph ] 라는 항목으로도 등록되어 있습니다.

한글 소개 링크는 다음과 같습니다 : [ https://github.com/lifeisforu/NodeGraph/wiki/An-introduction-for-WPF-NodeGraph(-Koeran-) ]

문서화가 많이 안 되어 있는데, 차근차근 추가해 갈 계획입니다. 

구현을 하는 데 있어 리플렉션이 워낙 많이 들어 가기 때문에 WPF 가 아닌 UI 언어로 이런 걸 제작하는 건 상상도 못하겠군요. 어쨌든 WPF 사용하는 분들에게는 도움이 되었으면 하네요.

Frostebite 가 GDC 2017 에서 발표한 [ FrameGraph: Extensible Rendering Architecture in Frostbite ] 에 영감을 받아서 이를 위해 UI 라이브러리를 구현하는데, 완성도를 높이려고 하다가 보니 배보다 배꼽이 더 큰 상황이 되었네요.

하지만 이 라이브러리를 만들면서 기존에 WPF 와 C# 리플렉션에 대해서 더 수준높은 이해를 할 수 있었고 기존에 추상적으로 알고 있던 것들이나 헷갈리던 것들의 개념이 명확해졌습니다. 역시 실전을 겪어 봐야지 실력이 느는 것 같습니다.

이제 VulkanMonkey 를 구현하면서 다시 공부를 진행해 보려고 합니다. 이 프로젝트를 진행하면서도 Vulkan 에 대한 이해도가 한층 더 높아졌으면 좋겠네요.

원문 : Largest product in a grid.

Brute-Force

이 문제를 가시화하면 다음과 같습니다. ( i, j ) 요소를 중심으로 살펴 보시다. 그러면 아래 그림에서 검은색을 중심으로 색칠해져 있는 부분들의 곱을 구해서 가장 큰 숫자들을 찾으면 됩니다.

그런데 딱 봐도 루프를 돌 때 중복되는 부분이 많을 것 같다는 생각이 듭니다. 특정 방향은 다른 좌표를 중심으로 하는 셸을 계산할 때 서로 겹치므로 배제될 수 있습니다( 예를 들어 왼쪽과 오른쪽, 위쪽과 아래쪽, 위쪽 대각선과 아래쪽 대각선 ).

이 정도로 최적화라고 부르긴 좀 뭐해서 여기까지 Brute-Force 라 생각하도록 하겠습니다.

str_num = ( "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 " "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 " "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 " "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 " "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 " "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 " "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 " "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 " "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 " "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 " "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 " "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 " "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 " "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 " "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 " "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 " "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 " "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 " "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 " "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48" ) strs = str_num.split() count = 0 arr = [] for str in strs : arr.append( int( str ) ) def max_value( left, right ) : return left if ( left > right ) else right product = 0 for j in range( 20 ) : for i in range( 20 ) : index = j * 20 + i if i > 2 and j < 17 : current_product = arr[ index ] * arr[ index + 19 ] * arr[ index + 38 ] * arr[ index + 57 ] product = max_value( product, current_product ) if i < 17 : current_product = arr[ index ] * arr[ index + 1 ] * arr[ index + 2 ] * arr[ index + 3 ] product = max_value( product, current_product ) if j < 17 : current_product = arr[ index ] * arr[ index + 20 ] * arr[ index + 40 ] * arr[ index + 60 ] product = max_value( product, current_product ) if i < 17 and j < 17 : current_product = arr[ index ] * arr[ index + 21 ] * arr[ index + 42 ] * arr[ index + 63 ] product = max_value( product, current_product ) print( product )

답은 70600674 입니다.

Other's solution

다른 사람들의 구현을 살펴 봤는데, 루프를 도는 방식에 조금 차이가 있을 뿐이고 크게 다르지는 않더군요.

그런데 파이썬에서 동적으로 자료구조를 만드는 편리한( 코드가 짧은 ) 방법들이 있는데, 꽤 어렵네요. [ JASON'S CODE BLOG ] 에서는 다음과 같이 2 차 배열을 만듭니다.

M = [i.split() for i in L] M = [[int(j) for j in i] for i in M]

파이썬은 문법이 뭔가 살짝 괴랄하지만 익숙해지면 편하게 쓸 수 있을 것 같아 보이네요.

주의 : 공부하면서 정리한 것이라서 잘못된 내용이 포함되어 있을 수 있습니다.

WPF 작업을 하다가 보면 직접 스크롤 뷰어의 동작을 제어하고 싶을 경우가 있습니다. 예를 들어 CustomControl 에서 마우스를 드래깅하면 스크롤이 갱신되는 것과 같은 작업을 원할 수 있습니다.

이 경우에 몇 ScrollViewer 를 직접 상속하는 커스텀 컨트롤을 만드는 것도 방법이지만, 다른 컨트롤을 상속해야 하는 경우에는 이런 방법을 사용할 수 없습니다.

하지만 왠만한 건 다 구현되어 있는 WPF 답게, WPF 는 스크롤에 대한 동작을 ScrollViewer 의 Content 로 지정된 컨트롤에서 제어할 수 있도록 하는 기능을 제공하고 있습니다.

그것은 IScrollInfo 라는 인터페이스를 통해서 이루어집니다. 이것은 24 개의 프라퍼티와 메서드를 구현할 것을 요구하는데요, 개수만 보면 정말 질릴 정도입니다. 하지만 기본 개념만 알고 있다면, 매우 편리하게 사용할 수 있다는 것을 알 수 있습니다.

Layouts of ScrollViewer & Content

일단 레이아웃에 대해서 간단히 살펴 보도록 하겠습니다.

그림1. ScrollViewer 와 Content 의 레이아웃.

그림1 에서 ScrollViewer 는 자신이 Content 로 포함하고 있는 컨트롤의 일부를 보여 주고 있습니다( 그림에는 "ScrollView" 라고 되어 있는데, "ScrollViewer" 입니다 ). 일반적으로 XAML 에서 다음과 같이 표현되겠죠.

<ScrollViewer CanContentScroll="True" HorizontalScrollBarVisibility="Visible" VerticalScrollBarVisibility="Visible"> <ngv:FlowChartView DataContext="{Binding Path=FlowChartViewModel, RelativeSource={RelativeSource AncestorType={x:Type local:MainWindow}}}"/> </ScrollViewer>

FlowChartView 라는 것은 제가 개인적으로 만들고 있는 커스텀 컨트롤입니다. 다들 아실거라 생각하지만, 부연하자면, <ScrollViewer>, </ScrollViewer> 마커( marker ) 사이에 들어 가는 컨트롤은 ScrollViewer.Content 에 할당됩니다. 그래서 제가 위에서 계속 "Content 로 포함하고 있는" 이라는 표현을 쓰고 있는 겁니다. 

어쨌든 이렇게 하면 자동으로 스크롤 뷰어가 내부 내용을 인지하게 됩니다. 

하지만 안타깝게도 제가 만든 컨트롤은 크기를 지정하지 않았습니다. 내부에 Canvas 를 가지고 있으며, 그것의 크기가 결정되지 않았기 때문입니다. 그래서 ScrollViewer 는 Content 의 크기를 알 수 없습니다.

<ngv:FlowChartView Width="500" Height="500"/> 이런 식으로 크기를 지정하면 썸을 볼 수는 있습니다만, 사용자가 생성하는 노드들에 의해 크기가 결정되는 Canvas 를 만드려는 의도가 있으므로, 크기를 지정하는 것은 바람직하지 않습니다. 필자가 스크롤링하고자 하는 것은 FlowChartView 자체가 아니가 그 안에 들어 있는 Canvas 이기 때문이죠.

이야기가 다른 곳으로 샜는데, 다시 본론으로 돌아가도록 하겠습니다. 

• Content 의 좌상단을 ( 0, 0 ) 이라고 할 때, Viewport 의 위치는 ( HorizontalOffset, VerticalOffset ) 으로 표현됩니다. 위의 그림1 에서 표현한 경우라면 HorizontalOffset 과 VerticalOffset 은 모두 양수값이겠죠. 이것은 디바이스의 픽셀 값이 아니라, 사용자가 생각하는 논리적인 픽셀값을 의미합니다.
• ViewportWidth 와 ViewportHeight 는 스크롤 뷰가 보여 줘야 하는 픽셀 단위의 크기를 말합니다.
• ExtentWidth 와 ExtentHeight 는 Content 의 픽셀 단위의 크기를 의미합니다.

레이아웃 자체는 매우 단순하며 IScrollInfo 의 메서드들은 위의 세 종류의 프라퍼티들을 결정하거나 이 프라퍼티들을 사용해서 스크롤링이 가능한지 여부를 판단하는 역할을 수행합니다.

FlowChartView 에서 IScrollInfo 인터페이스를 구현하도록 하겠습니다. 

public class FlowChartView : ContentControl, IScrollInfo

먼저 위에 나온 프라퍼티의 기본값을 결정해 보도록 하죠.

• ViewportWidth : FlowChartView 의 ActualWidth.
• ViewportHeight : FlowChartView 의 ActualHeight.
• HorizontalOffset : 0.
• VerticalOffset : 0.
• ExtentWidth : 1920. 물론 나중에는 실제 Content 의 크기를 계산해서 넣어 줘야 합니다.
• ExtentHeight : 1080. 이것도 나중에는 실제 크기를 계산해서 넣어 줘야 합니다.

private void FlowChartView_SizeChanged( object sender, SizeChangedEventArgs e ) { ViewportWidth = ActualWidth; ViewportHeight = ActualHeight; CanHorizontallyScroll = ViewportWidth < ExtentWidth; CanVerticallyScroll = ViewportHeight < ExtentHeight; }

FlowChartView_SizeChanged() 메서드에서는 CanHorizontallyScroll 과 CanVerticallyScroll 을 설정하는데요, 스크롤바를 제어할 수 있는지 여부를 의미하는 파라퍼티들입니다. 만약 CanHorizontallyScroll 이 false 를 반환한다면, ScrollViewer.HorizontalScrollBarVisibility 가 Visible 일 때는 스크롤바가 딤( dim )될테고 Auto 일때는 접힐( collasped ) 것입니다.

하지만 아직까지 스크롤바를 누르거나 어떤 동작을 해도 아무 것도 변하지 않을 겁니다. 왜냐하면 입력에 대한 정의를 하나도 하지 않았기 때문입니다.

ScrollViewer Inputs

IScrollInfo 의 일부 메서드는 ScrollViewer 에 입력이 들어 왔을 때 어떤 동작을 수행해야 하는지를 결정합니다.

예를 들어 오른쪽에 있는 Vertical Scroll 영역의 썸 이외의 부분을 클릭하면 PageDown() 메서드가 호출됩니다. 

이제 PageDown() 메서드에서 적절한 동작을 해 주시면 됩니다. 예를 들어 다음과 같이 계산하는 것이 가능합니다.

즉 전체 ExtentHeight 를 ViewportHeight 크기로 분할했을 때의 시작 위치를 지정하면 됩니다. 하지만 안타깝게도 균등 분할이 될 수 없으므로, 시작 위치는 반드시 0 이어야 하고 마지막 위치는 반드시 ExtentHeight - ViewportHeight 여야겠죠.

위는 단지 예일 뿐입니다. PageDown() 으로 이동해야 할 크기를 정해 놓고 사용할 수도 있고 썸을 제외한 나머지 부분을 균등분할해서 크기를 결정할 수도 있겠죠.

public void PageUp() { SetVerticalOffset( VerticalOffset - ViewportHeight ); } public void PageDown() { SetVerticalOffset( VerticalOffset + ViewportHeight ); } public void SetVerticalOffset( double offset ) { if( ExtentHeight < ( offset + ViewportHeight ) ) offset = ExtentHeight - ViewportHeight; else if( 0 > offset ) offset = 0; VerticalOffset = offset; }

원래 PageDown() 내에서 VerticalOffset 을 결정할 수 있겠지만, 이런 메서드는 매우 많습니다. LineLeft/Right/Up/Down(), MouseWheelLeft/Right/Up/Down(), PageLeft/Right/Up/Down() 등의 메서드가 존재합니다. 그런데 이런 계산을 할 때마다 예외처리하는 것이 불편하기 때문에 SetVerticalOffset() 과 SetHorizontalOffset() 을 사용해서 최종적인 예외 처리 및 위치 결정을 수행합니다.

여기까지 하면 스크롤 바를 눌렀을 때 썸이 이동하는 것을 확인할 수 있습니다.

하지만 칸텐츠가 같이 이동하지 않고 있음을 발견할 수 있습니다. 마지막으로 구현해야 할 것이 하나 남아 있습니다. 실제로 FlowChartView 의 자식인 Canavs 위치를 이동시켜 줘야 합니다. 지금까지는 단지 ScrollViewer 와 관련한 작업만 한 거였습니다. 이것 때문에 저도 당황했었는데요, [ 1 ] 에서 답을 찾을 수 있었습니다.

현재 제가 구현하는 FlowChartView 의 ControlTemplate 에서 Canvas 요소는 다음과 같이 들어 가 있습니다. 그러므로 "PART_NodeViewsContainer" 의 위치를 변경해 주면 됩니다.

<Grid> [ ... ] <!-- Nodes --> <v:NodeViewsContainer IsHitTestVisible="True" x:Name="PART_NodeViewsContainer" ItemsSource="{Binding NodeViewModels}"> <ItemsControl.ItemsPanel> <ItemsPanelTemplate> <Canvas/> </ItemsPanelTemplate> </ItemsControl.ItemsPanel> </v:NodeViewsContainer> [ ... ]

SetVerticalOffset() 에서 InvalidateArrange() 를 호출해 주고, 다음과 같이 ArrangeOverride() 에서 위치를 갱신합니다.

public void SetVerticalOffset( double offset ) { [ ... ] InvalidateArrange(); } protected override Size ArrangeOverride( Size arrangeBounds ) { _PartNodeViewsContainer.Arrange( new Rect( -HorizontalOffset, -VerticalOffset, 0.0, 0.0 ) ); return base.ArrangeOverride( arrangeBounds ); }

제 구현에서는 Canvas 컨테이너의 크기가 중요하지 않으므로 Size 에 0 을 넣었지만, 다른 사람들은 올바른 수치를 넣으면 됩니다. 그리고 스크롤을 했을 때의 칸텐츠 위치는 Viewport 에 대해서 상대적으로 이동해야 하므로 HorizontalOffset 과 VerticalOffset 을 음수값으로 넣고 있습니다.

이제 스크롤링할 때 정상적으로 칸텐츠가 스크롤되는 것을 확인할 수 있습니다.

아! 깜박 잊은 게 하나 있는데요, FlowCharView 를 클릭하면 MakeVisible() 이 호출되면서 원래 위치로 돌아가 버립니다. 그러므로 MakeVisible() 에서도 꼭 InvalidateArrange() 를 호출해 줘야 합니다.

public Rect MakeVisible( Visual visual, Rect rectangle ) { InvalidateArrange(); return rectangle; }

참고자료

[ 1 ] C# WPF Tutorial - Implementing IScrollInfo [Advanced], C#4 ALL.

원문 : 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 )

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