MINZKN의 블로그

span class=postbody2진법에서의 곱셈/나눗셈의 한가지 관점에 대해서 적어두겠습니다. br / 물론 CPU가 이렇게 한다는 것은 보장할수 없지만 이렇게도 할수 있다는 것을 설명하기 위한 취지로 적었습니다. br / br / 근본적으로 이건 이미 널리 쓰이는 방법이며 원리는 간단합니다. br / 곱셈을 쉬프트와 덧셈으로 어떻게 바꿀수 있는가를 고려한 이야기 입니다. br / br / 우리 간단히 이런거 하죠? br / br / /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=codea = a * 2 ;/td /tr/tbody/tablespan class=postbody br / br / 이것을 쉬프트로 바꾸면 a = a lt;lt; 1; br / 일단 이것은 다들 아는 내용이라서 구차 설명하진 않겠습니다. br / 그러면 이건 어떻게 바꿀까요? br / br / /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=codea = a * 3;/td /tr/tbody/tablespan class=postbody br / br / 이건 /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=codea = (a * 2) + a;/td /tr/tbody/tablespan class=postbody br / br / 즉, /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=codea = (a lt;lt; 1) + a;/td /tr/tbody/tablespan class=postbody br / br / 이렇게 바꾸면 되겠군요. br / 근데 여기까지는 누구라도 생각하겠지요? (못생각하신 분은 곱셈 쓰세요) br / 근데 만약 이런거면 어떻게 하실런지요? br / br / /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=codea = a * 640;/td /tr/tbody/tablespan class=postbody br / br / 숫자가 너무 높아서 뒷머리가 뻐근하게 아파오는것이 한편으로는 궁굼하죠? .... br / (무언가 규칙이 있을법 한데 ... 그게 뭘까요?) br / br / 여기서 제가 말하고자 하는 꽁수는 조건이 있습니다. br / br / 첫째: [ 곱셈의 숫자중 1개는 반드시 상수다! ] br / 둘째: [ 또는 가변적이지만 한번 값이 결정되면 많은 루프를 수행한다. ] br / br / 이게 조건입니다. 이경우 제가 설명하는 것을 써먹어보세요. br / 그럼 위의 640의 곱을 제가 어떻게 할수 있다는 예기가 되겠죠? br / 일단 2진수 형태로 만들면 그것이 해답입니다. br / br / /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=code2 | 640 br / nbsp; +--------- br / 2 | 320 gt;gt;gt; 0 br / nbsp; +--------- br / 2 | 160 gt;gt;gt; 0 br / nbsp; +--------- br / 2 | 80 gt;gt;gt; 0 br / nbsp; +--------- br / 2 | 40 gt;gt;gt; 0 br / nbsp; +--------- br / 2 | 20 gt;gt;gt; 0 br / nbsp; +--------- br / 2 | 10 gt;gt;gt; 0 br / nbsp; +--------- br / 2 | 5 gt;gt;gt; 0 br / nbsp; +--------- br / 2 | 2 gt;gt;gt; 1 br / nbsp; +--------- br / nbsp; nbsp; nbsp;1 gt;gt;gt; 0/td /tr/tbody/tablespan class=postbody br / br / 요렇게 2진수로 바꾸는거 아시죠? br / br / 0000 0010 1000 0000 br / br / 이렇게 되겠네요. br / 일단 요기서 1이라는 숫자가 2개뿐이 없네요. br / 이건 즉, 쉬프트 두번과 그에 합으로 곱을 나타낸다는 말이죠. (왜?) br / br / 왼쪽에서 첫번째 1은 다음과 같이 바꿀수 있습니다. br / br / 1 lt;lt; 9 br / br / 왼쪽에서 두번째 1은 다음과 같이 바꿀수 있습니다. br / br / 1 lt;lt; 7 br / br / 이제 되었습니다. br / a = a * 640 이라는 식은 다음과 같이 바꿀수 있겠네요. br / br / (여기서 수학적 증명은 전공이 아니라서 묻지 마세요. 안가르쳐주는게 아니라 도망갑니다.) br / br / /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=codea = (a lt;lt; 9) + (a lt;lt; 7);/td /tr/tbody/tablespan class=postbody br / br / 하하하 드디어 뭔가 감이 오지 않나요? (안온다면 그냥 곱셈 계속 쓰시고요...) br / 근데 C언어로 해석한다면 오히려 길어졌는데 왜 빨라지냐고요? (모르겠다면 그냥 곱셈 쓰세요) br / br / [[[ PS ]]] br / 근데 이거 어디다가 쓰면 가장 좋을까요? br / 점하나 찍는 frame buffer 를 다룬다고 합시다. br / br / /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=code*(VideoRam + (y * xRESOLUTION) + x) = Color;/td /tr/tbody/tablespan class=postbody br / br / 어디서 많이 본 공식이죠? br / 여기서 xRESOLUTION이 640 이라면? br / br / /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=code*(VideoRam + ( (y lt;lt; 9) + (y lt;lt; 7) ) + x) = Color;/td /tr/tbody/tablespan class=postbody br / br / 요렇게 바꾸어보면 무지(쬐금) 빠른 그래픽 처리가 되겠네요. br / br / br / br / 아주 흥미로운 관심사이어서 Linux 에서 직접 테스트 코드를 짜봤습니다. br / br / 실제로는 완전한 Test 를 고려한다면 RealTime OS 환경이 필요한듯 싶다는 생각이 들었습니다. br / (및에 보시다 시피 TEST COUNT 한번의 clock 수가 다른 COUNT의 clock과 너무 차이 나는 경우는 Context switch가 일어난것으로 보이므로 결과를 신뢰할수 없는 경우겠지요.) br / br / 쉽게 보시도록 /* !! */ 로 붙인 부분이 각 테스트 항목마다 다른 부분입니다. br / 그리고 소스에서 volatile 변수를 사용하여 일부 원치않는(C 로 계산하는 부분) 최적화를 방지하기 위해서 사용한 것입니다. br / br / 아래의 결과화면은 완성도를 높이기 위해서 Linux에서 모든 서비스를 중지하고 커널과 init 프로세스 br / 그리고 getty 만 살려둔채 아무 영향을 받지 않도록 최소의 프로세스를 띄우고 실행한 결과입니다. br / br / 그리고 결과수치를 통계를 내보면 거의 동일한 성능을 보였습니다. br / br / br / 참고로 아래의 결과는 Intel pentium III mobile CPU 1.06GHz 에서 테스트하였습니다. br / 여기서 약 39211 clock 을 소모한 TESTCOUNT만이 테스트에 유효성을 갖는다고 할수 있을거 같군요. (왜냐하면 RealTime OS가 아니기 때문에...) br / br / /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb인용:/b/span/td /tr tr td class=quoteTEST START ! br / === TEST [1] === -------------------------------------- ( 436005 clock) br / test_0 : 158249 (result=153920) /* C source */ br / test_1 : 70457 (result=153920) /* LEA + SHL */ br / test_2 : 66659 (result=153920) /* IMUL */ br / test_3 : 140021 (result=153920) /* LEA + ADDx7 */ br / br / === TEST [2] === -------------------------------------- ( 39809 clock) br / test_0 : 10365 (result=153920) /* C source */ br / test_1 : 6719 (result=153920) /* LEA + SHL */ br / test_2 : 6685 (result=153920) /* IMUL */ br / test_3 : 15738 (result=153920) /* LEA + ADDx7 */ br / br / === TEST [3] === -------------------------------------- ( 39232 clock) br / test_0 : 10308 (result=153920) /* C source */ br / test_1 : 6433 (result=153920) /* LEA + SHL */ br / test_2 : 6527 (result=153920) /* IMUL */ br / test_3 : 15715 (result=153920) /* LEA + ADDx7 */ br / br / === TEST [4] === -------------------------------------- ( 39211 clock) br / test_0 : 10288 (result=153920) /* C source */ br / test_1 : 6432 (result=153920) /* LEA + SHL */ br / test_2 : 6527 (result=153920) /* IMUL */ br / test_3 : 15715 (result=153920) /* LEA + ADDx7 */ br / br / === TEST [5] === -------------------------------------- ( 52870 clock) br / test_0 : 10288 (result=153920) /* C source */ br / test_1 : 6432 (result=153920) /* LEA + SHL */ br / test_2 : 6527 (result=153920) /* IMUL */ br / test_3 : 29374 (result=153920) /* LEA + ADDx7 */ br / br / === TEST [6] === -------------------------------------- ( 39262 clock) br / test_0 : 10288 (result=153920) /* C source */ br / test_1 : 6423 (result=153920) /* LEA + SHL */ br / test_2 : 6527 (result=153920) /* IMUL */ br / test_3 : 15751 (result=153920) /* LEA + ADDx7 */ br / br / === TEST [7] === -------------------------------------- ( 39211 clock) br / test_0 : 10288 (result=153920) /* C source */ br / test_1 : 6432 (result=153920) /* LEA + SHL */ br / test_2 : 6527 (result=153920) /* IMUL */ br / test_3 : 15715 (result=153920) /* LEA + ADDx7 */ br / br / === TEST [8] === -------------------------------------- ( 39211 clock) br / test_0 : 10288 (result=153920) /* C source */ br / test_1 : 6432 (result=153920) /* LEA + SHL */ br / test_2 : 6527 (result=153920) /* IMUL */ br / test_3 : 15715 (result=153920) /* LEA + ADDx7 */ br / br / === TEST [9] === -------------------------------------- ( 39211 clock) br / test_0 : 10288 (result=153920) /* C source */ br / test_1 : 6432 (result=153920) /* LEA + SHL */ br / test_2 : 6527 (result=153920) /* IMUL */ br / test_3 : 15715 (result=153920) /* LEA + ADDx7 */ br / br / === TEST [10] === -------------------------------------- ( 39211 clock) br / test_0 : 10288 (result=153920) /* C source */ br / test_1 : 6432 (result=153920) /* LEA + SHL */ br / test_2 : 6527 (result=153920) /* IMUL */ br / test_3 : 15715 (result=153920) /* LEA + ADDx7 */ br / br / br / End of test./td /tr/tbody/tablespan class=postbody br / br / br / /spantable align=center border=0 cellpadding=3 cellspacing=1 width=90%tbodytr tdspan class=genmedb코드:/b/span/td /tr tr td class=code br / /* br / Code by JaeHyuk Cho lt;mailto:minzkn@infoeq.comgt; br / br / http://asmlove.co.kr br / */ br / br / #include lt;stdio.hgt; br / br / #define DEF_TESTCOUNT (10) br / br / typedef unsigned long long t_mz_qword; br / #define DEF_ASM __asm__ volatile br / #define DEF_RDTSC(m_X) DEF_ASM(rdtsc\n\t : =A(m_X)) br / br / #define __emit_x8__(m_X)nbsp; do{ {m_X}{m_X}{m_X}{m_X} {m_X}{m_X}{m_X}{m_X} }while(0) br / #define __emit_x32__(m_X) do{ __emit_x8__(m_X); __emit_x8__(m_X); __emit_x8__(m_X); __emit_x8__(m_X); }while(0) br / #define __emit_x128__(m_X) do{ __emit_x32__(m_X); __emit_x32__(m_X); __emit_x32__(m_X); __emit_x32__(m_X); }while(0) br / #define __emit_x512__(m_X) do{ __emit_x128__(m_X); __emit_x128__(m_X); __emit_x128__(m_X); __emit_x128__(m_X); }while(0) br / #define __emit_x2048__(m_X) do{ __emit_x512__(m_X); __emit_x512__(m_X); __emit_x512__(m_X); __emit_x512__(m_X); }while(0) br / br / /* Inline loop code */ br / #define __emit_code__(m_X) __emit_x2048__(m_X) br / br / /* Volatile var */ br / volatile unsigned int g_resxnbsp; nbsp;= 640; br / volatile unsigned int g_resynbsp; nbsp;= 480; br / volatile unsigned int g_xnbsp; nbsp; nbsp; = 640 gt;gt; 1; br / volatile unsigned int g_ynbsp; nbsp; nbsp; = 480 gt;gt; 1; br / volatile unsigned int g_result = 0; br / br / t_mz_qword test0(void) br / { br / /* ** */ t_mz_qword s_p_start, s_p_end; br / /* ** */ DEF_RDTSC(s_p_start); br / /* ** */ __emit_code__( br / /* !! */nbsp; g_result = (g_y * 640) + g_x; br / /* ** */ ); br / /* ** */ DEF_RDTSC(s_p_end); br / /* ** */ return(s_p_end - s_p_start); br / } br / br / t_mz_qword test1(void) br / { br / /* ** */ t_mz_qword s_p_start, s_p_end; br / /* ** */ DEF_RDTSC(s_p_start); br / /* ** */ DEF_ASM(\n\t:: d(g_x), c(g_y)); br / /* ** */ __emit_code__( br / /* ** */nbsp; DEF_ASM( br / /* ** */nbsp; nbsp;movl %%ecx, %%eax\n\t br / /* !! */nbsp; nbsp;leal (%%eax,%%eax,4),%%eax\n\t br / /* !! */nbsp; nbsp;shll $0x07, %%eax\n\t br / /* ** */nbsp; nbsp;addl %%edx, %%eax\n\t br / /* ** */nbsp; nbsp;::);nbsp; br / /* ** */ ); br / /* ** */ DEF_ASM(\n\t: =a(g_result)); br / /* ** */ DEF_RDTSC(s_p_end); br / /* ** */ return(s_p_end - s_p_start); br / } br / br / t_mz_qword test2(void) br / { br / /* ** */ t_mz_qword s_p_start, s_p_end; br / /* ** */ DEF_RDTSC(s_p_start); br / /* ** */ DEF_ASM(\n\t:: d(g_x), c(g_y)); br / /* ** */ __emit_code__( br / /* ** */nbsp; DEF_ASM( br / /* ** */nbsp; nbsp;movl %%ecx, %%eax\n\t br / /* !! */nbsp; nbsp;imul $640, %%eax, %%eax\n\t br / /* ** */nbsp; nbsp;addl %%edx, %%eax\n\t br / /* ** */nbsp; nbsp;::); br / /* ** */ ); br / /* ** */ DEF_ASM(\n\t: =a(g_result)); br / /* ** */ DEF_RDTSC(s_p_end); br / /* ** */ return(s_p_end - s_p_start); br / } br / br / t_mz_qword test3(void) br / { br / /* ** */ t_mz_qword s_p_start, s_p_end; br / /* ** */ DEF_RDTSC(s_p_start); br / /* ** */ DEF_ASM(\n\t:: d(g_x), c(g_y)); br / /* ** */ __emit_code__( br / /* ** */nbsp; DEF_ASM( br / /* ** */nbsp; nbsp;movl %%ecx, %%eax\n\t br / /* !! */nbsp; nbsp;leal (%%eax,%%eax,4),%%eax\n\t br / /* !! */nbsp; nbsp;addl %%eax, %%eax\n\t /* 1 */ br / /* !! */nbsp; nbsp;addl %%eax, %%eax\n\t /* 2 */ br / /* !! */nbsp; nbsp;addl %%eax, %%eax\n\t /* 3 */ br / /* !! */nbsp; nbsp;addl %%eax, %%eax\n\t /* 4 */ br / /* !! */nbsp; nbsp;addl %%eax, %%eax\n\t /* 5 */ br / /* !! */nbsp; nbsp;addl %%eax, %%eax\n\t /* 6 */ br / /* !! */nbsp; nbsp;addl %%eax, %%eax\n\t /* 7 */ br / /* ** */nbsp; nbsp;addl %%edx, %%eax\n\t br / /* ** */nbsp; nbsp;::); br / /* ** */ ); br / /* ** */ DEF_ASM(\n\t: =a(g_result)); br / /* ** */ DEF_RDTSC(s_p_end); br / /* ** */ return(s_p_end - s_p_start); br / } br / br / void test(int s_TestCount) br / { br / t_mz_qword s_p_start, s_p_end; br / t_mz_qword s_p_test_0, s_p_test_1, s_p_test_2, s_p_test_3; br / unsigned int s_result_0, s_result_1, s_result_2, s_result_3; br / br / /* start */ br / DEF_RDTSC(s_p_start); br / g_result = 0; s_p_test_0 = test0(); s_result_0 = g_result; br / g_result = 0; s_p_test_1 = test1(); s_result_1 = g_result; br / g_result = 0; s_p_test_2 = test2(); s_result_2 = g_result; br / g_result = 0; s_p_test_3 = test3(); s_result_3 = g_result; br / DEF_RDTSC(s_p_end); br / br / /* report */ br / fprintf(stdout, br / nbsp; === TEST [%d] === -------------------------------------- (%8llu clock)\n br / nbsp; test_0nbsp; nbsp; nbsp; : %8llu (result=%u) /* C sourcenbsp; nbsp; */\n br / nbsp; test_1nbsp; nbsp; nbsp; : %8llu (result=%u) /* LEA + SHLnbsp; nbsp;*/\n br / nbsp; test_2nbsp; nbsp; nbsp; : %8llu (result=%u) /* IMULnbsp; nbsp; nbsp; nbsp; */\n br / nbsp; test_3nbsp; nbsp; nbsp; : %8llu (result=%u) /* LEA + ADDx7 */\n br / nbsp; \n, br / nbsp; s_TestCount, s_p_end - s_p_start, br / nbsp; s_p_test_0, s_result_0, br / nbsp; s_p_test_1, s_result_1, br / nbsp; s_p_test_2, s_result_2, br / nbsp; s_p_test_3, s_result_3); br / } br / br / int main(void) br / { br / int s_TestCount; br / fprintf(stdout, TEST START !\n); br / for(s_TestCount = 1;s_TestCount lt;= DEF_TESTCOUNT;s_TestCount++)test(s_TestCount); br / fprintf(stdout, \nEnd of test.\n); br / return(0); br / } br / br / /* End of source */ /td/tr/tbody/table

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.