'마방진'에 해당되는 글 2건

  1. 2007.05.06 스레드를 이용한 병렬처리 프로그래밍 – 2
  2. 2006.04.09 알고리즘에 따른 속도차이 (4)

스레드를 이용한 병렬처리 프로그래밍 – 2

예전에 "스레드를 이용한 병렬처리 프로그래밍"이라는 이름으로 스레드를 이용, 멀티코어를 위한 프로그래밍에 대해 간단히 이야기 한 적이 있습니다. 하지만 그 때에는 단순히 "CPU를 동시에 이용이 가능하다" 까지만 이야기를 해서 이번엔 멀티코어에 맞춰 만들어진 프로그램이 어느 정도 성능에 이득이 있을까를 두고 실험을 해 봤습니다.

지난번과 마찬가지로 Java로 구현을 했습니다. 구현 알고리즘은 "홀수 마방진"(알고리즘에 따른 속도차이편의 알고리즘을 사용했음)이고, 측정 기준은 선언부와, 출력부 기타 등등을 모두 제외한 순수 연산부분만을 측정했습니다.

우선 첫 번째로 스레드가 1개(스레드가 없을 때와 동일)일 때 상황입니다.

사용자 삽입 이미지
344ms군요. 32bit에서는 405ms에 처리했었습니다.

그럼 다음으로 스레드가 2개일 때 상황입니다. 듀얼코어나 그 이상의 프로세서를 가진 컴퓨터에서라면 효과가 있겠죠?

사용자 삽입 이미지
187ms입니다. 32bit에서는 218ms에 처리했었습니다. 2배까지는 아니더라도 2배 가까이 빨라졌습니다.

이것으로 잘만 작성하면 멀티코어 CPU를 지원할 수 있다는 것이 입증이 되었습니다 ^^ 혹시 이걸 사용해보실 분은 받아가서 사용해 보세요. 혹시 버그가 있으면 말씀해 주시고요 ^^

Trackback 0 Comment 0

알고리즘에 따른 속도차이

요즘 객체지향 프로그래밍을 공부를 하고 있는데 문득 “같은 목적의 프로그램이지만 라인과 코딩숫자가 다를 경우의 속도차이는 어떠할까?”라는 궁금 점이 들더군요.
그래서 최근 배우고 있는 Java를 이용해서 홀수 마방진 프로그램을 만들었습니다.

첫 번째 알고리즘은 보통 사람들이 많이 구현하고, 제가 고등학교 때 구현했던 알고리즘입니다.


그림에서 보시다시피 맨 처음 시작은 상단의 정 중앙에서 시작합니다. 그 뒤 우측 위쪽으로 1칸씩 이동을 하며 만약 공간을 벗어났을 경우 벗어난 곳의 반대쪽에 지정을 합니다. 그리고 지정한 곳에 숫자가 있으면 이전 곳의 아래를 지정하는 순으로 만들어지게 됩니다.

두 번째 알고리즘은 첫 번째 알고리즘의 기초가 되는 알고리즘인데 제가 오늘 안 돌아가는 머리 굴려가며 구현한 알고리즘입니다.


지정된 공간에서 벗어난 지점을 포함해서 대각선으로 숫자를 넣은 뒤 벗어난 지역의 숫자를 반대편으로 넣는 방식으로 만들어집니다.

두 알고리즘의 결과는 약간 다르지만 두 개 모두 같은 목적을 가진 알고리즘입니다.

각 알고리즘별 출력 결과


이제 이 두 개의 알고리즘을 놓고 속도, 컴파일 시 용량을 측정해 보겠습니다.

속도 측정은 999 * 999짜리 마방진을 100번 만들어내는 속도로 측정을 했습니다.

첫 번째 결과

두 번째 결과


두 결과 모두 0.5초, 0.8초 차이로 두 번째 알고리즘의 승리입니다.

그럼 컴파일 시 용량이 어떻게 되는지 알아보겠습니다.


18바이트 차이로 두 번째 알고리즘의 승리군요.

알고리즘 선택에 따라 이렇게 미묘한 차이가 있을 수 있다는 것을 이번 실험에서 알아낼 수 있었습니다. 하지만 이 미묘한 차이가 쌓이고 쌓이면 엄청나한 차이가 있을 수 있다는 사실을 잊어서는 안될 것 같습니다.

여기서 보너스~

두 번째 알고리즘을 구현하기 위해 머리를 싸맸던 흔적을 공개하겠습니다 >.<

단 한줄 때문에 이런 삽질을...

Trackback 0 Comment 4
  1. Favicon of http://www.signpen.pe.kr BlogIcon 싸인펜 2006.04.10 03:24 address edit & del reply

    자바로 마방진을 구현하는 것에 대해선 생각해 본적이 없었는데, 글을 보고 관심이 생겨버려 흥미 있게 봤습니다^^
    글 중에서 속도를 측정했던 부분은 마방진 프로그램 내부에 코드를 추가 하신 건가요, 아니면 따로 측정하는 프로그램이 있는 건가요??

    • Favicon of http://www.myhyuny.net BlogIcon 화현 2006.04.10 07:48 address edit & del

      제가 간단한 코딩으로 넣은것입니다.
      방법은 "실행 후 시간 - 실행 전 시간"으로 단위는 1/1000초입니다.
      예전에 C로 게임짰을때 많이 써먹은 방법입니다 ^^;

  2. Favicon of http://rukxer.net/root/ BlogIcon Rukxer 2006.04.11 22:19 address edit & del reply

    씨부럴 우리는 객체랍시고 C++하는데 이것도 조낸 머리에 쥐난다

    • Favicon of http://www.myhyuny.net BlogIcon 화현 2006.04.12 01:03 address edit & del

      C++ 최강이죠 ㅠ.ㅠ
      포인터에 객체지향까지
      사람 골머리 썩히는것의 집합체 ㅠ.ㅠ