GPU와 kudeki-chain

0.

 18년 2학기에 GPU 프로그래밍을 배워서, 이참에 kudeki-chain도 풀어봤습니다. GTX 1060으로, 약 16시간 정도 돌려서 풀었습니다. 최적화를 덜 했기 때문에 더 빨라질 여지가 있긴 합니다. sha1을 GPU로 옮기는 것이 꽤나 귀찮았는데, 코딩을 오랫만에 해서 그런지 실수가 꽤 많아 오래 걸렸던 것 같습니다. 제 개같은 틀린 코드를 디버깅해준 cubelover에게 감사의 말을 전하며 시작하겠습니다.

 

1.

 kudeki-chain 문제를 한 줄로 요약하면 다음과 같습니다. "sha1 해시값의 앞 n자리가 0이 되는 (커밋)메세지를 찾아라." n은 푼 사람이 생길수록 1씩 늘어나서, 제가 문제를 풀 때는 n이 11과 12였습니다. (현재 n이 12인 경우까지 해결하였기 때문에 n=12를 기준으로 설명하겠습니다) 확률로 따지면 1/2^48쯤 되고, CPU로 초당 1억개의 sha1 해쉬값을 확인한다고 해도 32일정도 소요됩니다.

 조건을 만족하는 sha1 해쉬값을 찾는 것은 단순하고 간단한 작업입니다. 임의로 만든 메세지를 m이라고 할 때 해쉬값이 조건을 만족하는지 확인하는 함수 f(m)는,

(1) m의 sha1 해쉬값 h를 구한다.

(2) m의 앞 12개가 0이면 1, 아니면 0을 대입한다.

 

 GPU는 완벽하게 같은 프로그램으로, 다른 데이터로 연산을 할 때 매우 효율적입니다. GPU는 내부에 많은 수의 core가 있고, 각 core에서 동시에 같은 작업을 수행하는 기기입니다. 여기서, 같은 작업을 해도 데이터가 다르면 다른 결과가 나올 수 있다는 것이 중요합니다. 위에서 같은 함수 f(m)를, 다른 데이터에 대해 연산하는 것을 생각하면 될 것 같습니다. 그래서, 채굴에서만큼은 GPU가 CPU보다 효율적입니다.

 제가 사용한 GPU인 GTX 1060의 사양은 아래와 같습니다. core 수가 1152개이므로 대충 1천배정도 빠르다고 추산할 수 있습니다. (Hz 차이나, 여러 최적화 때문에 정확히 1152배 차이나지는 않을 것 같습니다) 

 

GPU 1060 사양

2.

 처음에는 귀찮아서 최적화를 덜 했는데, 너무 느려서 결국 최적화를 했습니다. 최적화 방법은 다음과 같습니다.

(1) sha1을 마지막 block만 연산하기

 sha1은 512bit block 단위로 연산하고, 앞쪽 block의 해쉬값이 뒷쪽 block의 해쉬값에 사용되는 방식입니다. 메세지의 앞쪽 해쉬값을 미리 계산한 뒤, 제일 뒤의 512bit block만 바꿔가면서 sha1값을 구했습니다. 마지막 block에는 길이 정보가 포함되어야 하기 때문에, 길이를 고정할 필요가 있었습니다.

 제 커밋의 가장 앞에 a가 있는 이유는 그 지점이 block이 나눠지는 지점이기 때문이고, 제 커밋에 @가 많은 이유는 block 길이를 고정하기 위해서입니다.

 

(2) GPU 내부 코드에서 사용하는 register 개수 줄이기

 sha1은 16개의 32bit 정수를 80개로 늘리는 작업을 합니다. 이 값을 전부 저장해서 연산했더니, 메모리 Read/Write를 하는 것 같았습니다. 모든 값이 register에 들어올 수 있도록, 항상 마지막 16개를 저장하게 해서 시간이 많이 줄었습니다.

 

 대충 이정도 최적화를 한 결과 1초에 약 30억개의 sha1 해쉬값을 확인할 수 있었습니다.

 

2-1.

 채굴은 GPU를 아무 생각 없이 최적의 효율로 사용할 수 있지만, 행렬 곱셈과 같은 메모리 접근이 필요한 작업은 최적화가 엄청나게 힘듭니다. GPU는 core가 많은데도 불구하고 GPU의 Global Memory에 접근하는 bus는 1개뿐이라, 많은 core가 메모리에 동시에 접근할 수 없기 때문입니다. 그래서 메모리 접근을 어떻게든 효율적으로 하기 위한 최적화 기법이 엄청나게 많습니다만, 여기서는 설명하지 않겠습니다.

 

3.

 다음 해쉬값을 찾는 데 필요한 시도 횟수의 기댓값은 2^52입니다. 아직은 GPU 16개를 쓰면 1일 안에 구할 수 있을 정도입니다. 하지만 GPU보다 더 빠른 방법이 있습니다. 회로를 직접 만들어서 만드는 방식을 쓰면, 아까보다 더 빠르게 값을 계산할 수 있습니다.

 GPU는 sha1 연산을 두 메세지에 대해 동시에 계산할 수 없습니다. 하지만 하드웨어로 직접 만들어서 파이프라이닝을 잘 하면, 1 clock당 1개의 sha1 해쉬값을 구할 수 있습니다. 회로를 매우 작게 만들어 같은 회로를 엄청나게 많이 만들면 1 clock에 몇만 개의 sha1 해쉬값을 구할 수 있을 것입니다. 

 시중에 있는 채굴기를 살펴보면, 1초에 53조개(53*10^15)의 해쉬 함수를 계산할 수 있습니다. (링크) 저는 이 문제를 풀기 위해 하드웨어를 만드는 사람이 나올지는 모르겠지만, 하드웨어를 괜찮게 만들면 1초내에 n=13, 14정도를 만들 수 있을 것으로 예상할 수 있습니다.

 

4.

 마지막으로 C++ 코드와 CUDA 코드입니다.