#keywords 곱셈,나눗셈,최적화,쉬프트,이진법,소인수분해 #title 곱셈과 나눗셈의 최적화 [wiki:Home 대문] / [wiki:CategoryProgramming 프로그래밍] / [wiki:OptimizationOfMultiplicationAndDivision 곱셈과 나눗셈의 최적화] ---- == [wiki:OptimizationOfMultiplicationAndDivision 곱셈과 나눗셈의 최적화] == * 작성자 조재혁([mailto:minzkn@minzkn.com]) * 고친과정 2007년 5월 5일 : 처음씀 [[TableOfContents]] === 개요 === 2진법에서의 곱셈/나눗셈의 한가지 관점에 대해서 소개하고자 합니다.[[br]] 물론 CPU가 이렇게 한다는 것은 보장할수 없지만 이렇게도 할수 있다는 것을 설명하기 위한 취지로 적었습니다. 근본적으로 이건 이미 널리 쓰이는 방법이며 원리는 간단합니다.[[br]] 곱셈을 쉬프트와 덧셈으로 어떻게 바꿀수 있는가를 고려한 이야기 입니다. 우리 간단히 이런거 하죠? {{{#!plain a = a * 2; }}} 이것을 쉬프트로 바꾸면 a = a << 1;[[br]] 일단 이것은 다들 아는 내용이라서 구차 설명하진 않겠습니다. 그러면 이건 어떻게 바꿀까요? {{{#!plain a = a * 3; }}} {{{#!plain a = (a * 2) + a; }}} 즉, {{{#!plain a = (a << 1) + a; }}} 이렇게 바꾸면 되겠군요.[[br]] 근데 여기까지는 누구라도 생각하겠지요?[[br]] 근데 만약 이런거면 어떻게 하실런지요?[[br]] {{{#!plain a = a * 640; }}} 숫자가 너무 높아서 뒷머리가 뻐근하게 아파오는것이 한편으로는 궁굼하죠? ....[[br]] (무언가 규칙이 있을법 한데 ... 그게 뭘까요?) 여기서 제가 말하고자 하는 꽁수는 조건이 있습니다.[[br]] * 첫째: [ 곱셈의 숫자중 1개는 반드시 상수다! ] * 둘째: [ 또는 가변적이지만 한번 값이 결정되면 많은 루프를 수행한다. ] 이게 조건입니다. 이경우 제가 설명하는 것을 써먹어보세요.[[br]] 그럼 위의 640의 곱을 제가 어떻게 할수 있다는 예기가 되겠죠?[[br]] 일단 2진수 형태로 만들면 그것이 해답입니다.[[br]] {{{#!plain 2 | 640 +--------- 2 | 320 >>> 0 +--------- 2 | 160 >>> 0 +--------- 2 | 80 >>> 0 +--------- 2 | 40 >>> 0 +--------- 2 | 20 >>> 0 +--------- 2 | 10 >>> 0 +--------- 2 | 5 >>> 0 +--------- 2 | 2 >>> 1 +--------- 1 >>> 0 }}} 요렇게 2진수로 바꾸는거 아시죠? {{{#!plain 0000 0010 1000 0000 }}} 이렇게 되겠네요.[[br]] 일단 요기서 1이라는 숫자가 2개뿐이 없네요.[[br]] 이건 즉, 쉬프트 두번과 그에 합으로 곱을 나타낸다는 말이죠. (왜 그럴까요?)[[br]] 왼쪽에서 첫번째 1은 다음과 같이 바꿀수 있습니다. {{{#!plain 1 << 9 }}} 왼쪽에서 두번째 1은 다음과 같이 바꿀수 있습니다. {{{#!plain 1 << 7 }}} 이제 되었습니다.[[br]] a = a * 640 이라는 식은 다음과 같이 바꿀수 있겠네요. {{{#!plain a = (a << 9) + (a << 7); }}} 하하하 드디어 뭔가 감이 오지 않나요? (안온다면 그냥 곱셈 계속 쓰시고요...)[[br]] 근데 [wiki:LanguageC C언어]로 해석한다면 오히려 길어졌는데 왜 빨라지냐고요?[[br]] 근데 이거 어디다가 쓰면 가장 좋을까요?[[br]] 점하나 찍는 frame buffer 를 다룬다고 합시다.[[br]] {{{#!plain *(VideoRam + (y * xRESOLUTION) + x) = Color; }}} 어디서 많이 본 공식이죠?[[br]] 여기서 xRESOLUTION이 640 이라면? {{{#!plain *(VideoRam + ( (y << 9) + (y << 7) ) + x) = Color; }}} 요렇게 바꾸어보면 무지(쬐금) 빠른 그래픽 처리가 되겠네요. 아주 흥미로운 관심사이어서 Linux 에서 직접 테스트 코드를 짜봤습니다. 실제로는 완전한 Test 를 고려한다면 RealTime OS 환경이 필요한듯 싶다는 생각이 들었습니다.[[br]] (아래와 같이 TEST COUNT 한번의 clock 수가 다른 COUNT의 clock과 너무 차이 나는 경우는 Context switch가 일어난것으로 보이므로 결과를 신뢰할수 없는 경우겠지요.) 쉽게 보시도록 /* !! */ 로 붙인 부분이 각 테스트 항목마다 다른 부분입니다.[[br]] 그리고 소스에서 volatile 변수를 사용하여 일부 원치않는(C 로 계산하는 부분) 최적화를 방지하기 위해서 사용한 것입니다. 아래의 결과화면은 완성도를 높이기 위해서 Linux에서 모든 서비스를 중지하고 커널과 init 프로세스 그리고 getty 만 살려둔채 아무 영향을 받지 않도록 최소의 프로세스를 띄우고 실행한 결과입니다. 그리고 결과수치를 통계를 내보면 거의 동일한 성능을 보였습니다. 참고로 아래의 결과는 Intel pentium III mobile CPU 1.06GHz 에서 테스트하였습니다.[[br]] 여기서 약 39211 clock 을 소모한 TESTCOUNT만이 테스트에 유효성을 갖는다고 할수 있을거 같군요. (왜냐하면 RealTime OS가 아니기 때문에...) {{{#!plain TEST START ! === TEST [1] === -------------------------------------- ( 436005 clock) test_0 : 158249 (result=153920) /* C source */ test_1 : 70457 (result=153920) /* LEA + SHL */ test_2 : 66659 (result=153920) /* IMUL */ test_3 : 140021 (result=153920) /* LEA + ADDx7 */ === TEST [2] === -------------------------------------- ( 39809 clock) test_0 : 10365 (result=153920) /* C source */ test_1 : 6719 (result=153920) /* LEA + SHL */ test_2 : 6685 (result=153920) /* IMUL */ test_3 : 15738 (result=153920) /* LEA + ADDx7 */ === TEST [3] === -------------------------------------- ( 39232 clock) test_0 : 10308 (result=153920) /* C source */ test_1 : 6433 (result=153920) /* LEA + SHL */ test_2 : 6527 (result=153920) /* IMUL */ test_3 : 15715 (result=153920) /* LEA + ADDx7 */ === TEST [4] === -------------------------------------- ( 39211 clock) test_0 : 10288 (result=153920) /* C source */ test_1 : 6432 (result=153920) /* LEA + SHL */ test_2 : 6527 (result=153920) /* IMUL */ test_3 : 15715 (result=153920) /* LEA + ADDx7 */ === TEST [5] === -------------------------------------- ( 52870 clock) test_0 : 10288 (result=153920) /* C source */ test_1 : 6432 (result=153920) /* LEA + SHL */ test_2 : 6527 (result=153920) /* IMUL */ test_3 : 29374 (result=153920) /* LEA + ADDx7 */ === TEST [6] === -------------------------------------- ( 39262 clock) test_0 : 10288 (result=153920) /* C source */ test_1 : 6423 (result=153920) /* LEA + SHL */ test_2 : 6527 (result=153920) /* IMUL */ test_3 : 15751 (result=153920) /* LEA + ADDx7 */ === TEST [7] === -------------------------------------- ( 39211 clock) test_0 : 10288 (result=153920) /* C source */ test_1 : 6432 (result=153920) /* LEA + SHL */ test_2 : 6527 (result=153920) /* IMUL */ test_3 : 15715 (result=153920) /* LEA + ADDx7 */ === TEST [8] === -------------------------------------- ( 39211 clock) test_0 : 10288 (result=153920) /* C source */ test_1 : 6432 (result=153920) /* LEA + SHL */ test_2 : 6527 (result=153920) /* IMUL */ test_3 : 15715 (result=153920) /* LEA + ADDx7 */ === TEST [9] === -------------------------------------- ( 39211 clock) test_0 : 10288 (result=153920) /* C source */ test_1 : 6432 (result=153920) /* LEA + SHL */ test_2 : 6527 (result=153920) /* IMUL */ test_3 : 15715 (result=153920) /* LEA + ADDx7 */ === TEST [10] === -------------------------------------- ( 39211 clock) test_0 : 10288 (result=153920) /* C source */ test_1 : 6432 (result=153920) /* LEA + SHL */ test_2 : 6527 (result=153920) /* IMUL */ test_3 : 15715 (result=153920) /* LEA + ADDx7 */ End of test. }}} {{{#!enscript c /* Copyright (C) JAEHYUK CHO All rights reserved. Author: JAEHYUK CHO */ #include #define DEF_TESTCOUNT (10) typedef unsigned long long t_mz_qword; #define DEF_ASM __asm__ volatile #define DEF_RDTSC(m_X) DEF_ASM("rdtsc\n\t" : "=A"(m_X)) #define __emit_x8__(m_X) do{ {m_X}{m_X}{m_X}{m_X} {m_X}{m_X}{m_X}{m_X} }while(0) #define __emit_x32__(m_X) do{ __emit_x8__(m_X); __emit_x8__(m_X); __emit_x8__(m_X); __emit_x8__(m_X); }while(0) #define __emit_x128__(m_X) do{ __emit_x32__(m_X); __emit_x32__(m_X); __emit_x32__(m_X); __emit_x32__(m_X); }while(0) #define __emit_x512__(m_X) do{ __emit_x128__(m_X); __emit_x128__(m_X); __emit_x128__(m_X); __emit_x128__(m_X); }while(0) #define __emit_x2048__(m_X) do{ __emit_x512__(m_X); __emit_x512__(m_X); __emit_x512__(m_X); __emit_x512__(m_X); }while(0) /* Inline loop code */ #define __emit_code__(m_X) __emit_x2048__(m_X) /* Volatile var */ volatile unsigned int g_resx = 640; volatile unsigned int g_resy = 480; volatile unsigned int g_x = 640 >> 1; volatile unsigned int g_y = 480 >> 1; volatile unsigned int g_result = 0; t_mz_qword test0(void) { /* ** */ t_mz_qword s_p_start, s_p_end; /* ** */ DEF_RDTSC(s_p_start); /* ** */ __emit_code__( /* !! */ g_result = (g_y * 640) + g_x; /* ** */ ); /* ** */ DEF_RDTSC(s_p_end); /* ** */ return(s_p_end - s_p_start); } t_mz_qword test1(void) { /* ** */ t_mz_qword s_p_start, s_p_end; /* ** */ DEF_RDTSC(s_p_start); /* ** */ DEF_ASM("\n\t":: "d"(g_x), "c"(g_y)); /* ** */ __emit_code__( /* ** */ DEF_ASM( /* ** */ "movl %%ecx, %%eax\n\t" /* !! */ "leal (%%eax,%%eax,4),%%eax\n\t" /* !! */ "shll $0x07, %%eax\n\t" /* ** */ "addl %%edx, %%eax\n\t" /* ** */ ::); /* ** */ ); /* ** */ DEF_ASM("\n\t": "=a"(g_result)); /* ** */ DEF_RDTSC(s_p_end); /* ** */ return(s_p_end - s_p_start); } t_mz_qword test2(void) { /* ** */ t_mz_qword s_p_start, s_p_end; /* ** */ DEF_RDTSC(s_p_start); /* ** */ DEF_ASM("\n\t":: "d"(g_x), "c"(g_y)); /* ** */ __emit_code__( /* ** */ DEF_ASM( /* ** */ "movl %%ecx, %%eax\n\t" /* !! */ "imul $640, %%eax, %%eax\n\t" /* ** */ "addl %%edx, %%eax\n\t" /* ** */ ::); /* ** */ ); /* ** */ DEF_ASM("\n\t": "=a"(g_result)); /* ** */ DEF_RDTSC(s_p_end); /* ** */ return(s_p_end - s_p_start); } t_mz_qword test3(void) { /* ** */ t_mz_qword s_p_start, s_p_end; /* ** */ DEF_RDTSC(s_p_start); /* ** */ DEF_ASM("\n\t":: "d"(g_x), "c"(g_y)); /* ** */ __emit_code__( /* ** */ DEF_ASM( /* ** */ "movl %%ecx, %%eax\n\t" /* !! */ "leal (%%eax,%%eax,4),%%eax\n\t" /* !! */ "addl %%eax, %%eax\n\t" /* 1 */ /* !! */ "addl %%eax, %%eax\n\t" /* 2 */ /* !! */ "addl %%eax, %%eax\n\t" /* 3 */ /* !! */ "addl %%eax, %%eax\n\t" /* 4 */ /* !! */ "addl %%eax, %%eax\n\t" /* 5 */ /* !! */ "addl %%eax, %%eax\n\t" /* 6 */ /* !! */ "addl %%eax, %%eax\n\t" /* 7 */ /* ** */ "addl %%edx, %%eax\n\t" /* ** */ ::); /* ** */ ); /* ** */ DEF_ASM("\n\t": "=a"(g_result)); /* ** */ DEF_RDTSC(s_p_end); /* ** */ return(s_p_end - s_p_start); } void test(int s_TestCount) { t_mz_qword s_p_start, s_p_end; t_mz_qword s_p_test_0, s_p_test_1, s_p_test_2, s_p_test_3; unsigned int s_result_0, s_result_1, s_result_2, s_result_3; /* start */ DEF_RDTSC(s_p_start); g_result = 0; s_p_test_0 = test0(); s_result_0 = g_result; g_result = 0; s_p_test_1 = test1(); s_result_1 = g_result; g_result = 0; s_p_test_2 = test2(); s_result_2 = g_result; g_result = 0; s_p_test_3 = test3(); s_result_3 = g_result; DEF_RDTSC(s_p_end); /* report */ fprintf(stdout, "=== TEST [%d] === -------------------------------------- (%8llu clock)\n" "test_0 : %8llu (result=%u) /* C source */\n" "test_1 : %8llu (result=%u) /* LEA + SHL */\n" "test_2 : %8llu (result=%u) /* IMUL */\n" "test_3 : %8llu (result=%u) /* LEA + ADDx7 */\n" "\n", s_TestCount, s_p_end - s_p_start, s_p_test_0, s_result_0, s_p_test_1, s_result_1, s_p_test_2, s_result_2, s_p_test_3, s_result_3); } int main(void) { int s_TestCount; fprintf(stdout, "TEST START !\n"); for(s_TestCount = 1;s_TestCount <= DEF_TESTCOUNT;s_TestCount++)test(s_TestCount); fprintf(stdout, "\nEnd of test.\n"); return(0); } /* End of source */ }}} === 참고: 정수를 다루는데 있어서 알아둘 점 === '''질문''' 하기와 같은 singed int와 unsigned int을 비교했을 때 상황에 따라서 어떤게 효율적일까요? {{{#!enscript c int i; unsigned int j; i = i / 3; j = j / 3; }}} '''답변(해설)''' 결국 답은 아래의 어셈블리 코드를 참시면 이해될겁니다. 극적인 예를 위한 어셈블리지만 정말 잘 만든 코드들 보면요런 특징을 유념하고 있는게 많이 보입니다. 즉, 부호를 다뤄야 하는지 그렇지 않아도 되는지는 컴파일러가 판단할 수 없다는 것입니다. {{{#!enscript asm /* i = i / 3; */ mov ecx, i mov eax, 1431655766 ; 55555556H imul ecx mov eax, edx shr eax, 31 ; 0000001fH add eax, edx /* j = j / 3; */ mov eax, -1431655765 ; aaaaaaabH mul i shr edx, 1 }}}