이번 학기에 듣는 문수복 교수님의 분산처리특강 프로젝트로 그 유명한 PageRank를 구현하였다. (혹시나 모르시는 분들을 위해 살짝 덧붙이면 Google 검색 엔진의 기초가 되는 웹페이지 중요도 판단 알고리즘이다) Google의 창업자 세르게이 브린과 래리 페이지가 썼던 PageRank 논문을 바탕으로 크기가 수백~수천만 단위인 sparse 행렬과 벡터의 곱셈을 계산하기 위해 matrix 계산 방식을 바꾼 power method를 활용하여 Hadoop 기반 MapReduce 방식으로 구현하였다.

특히 이번 수업에서는 여름방학부터 9월까지 NexR에서 인턴하면서 개발한 CCI:U Open CourseLabs (오픈소스 프로젝트도 참조) 및 KAIST 클라우드 컴퓨팅 테스트베드를 활용하여 작년에 했던 같은 수업보다 좀더 넉넉한 환경에서 쓸 수 있었다. 학과 자체에서도 가상화 클러스터를 만든 게 있어서 40코어 / RAM 32GB * 5 정도를 사용하고 여기에 CCI:U 클러스터는 48코어 / RAM 2GB * 48 규모로 함께 사용하였다.

PageRank에 대해 간단히 설명하면, 이전까지의 웹 검색은 키워드를 입력하면 그 키워드와 웹문서들을 분석하여 연관성이 높은 것을 뽑아주는 것이 기본 아이디어였지만 PageRank는 웹문서들 사이의 연결 관계를 주목했다는 점이다. 웹을 이루는 네트워크의 구조 자체를 랭킹에 포함시킨 것은 혁신적인 발상이었다. 원래 개념은 어떤 페이지에서 다른 페이지로 나가는 링크를 이용해 그 링크된 문서들의 PageRank 값을 그 각각이 가진 링크의 개수로 나눈 것을 모두 더한 것이 자신의 PageRank가 되는 것이다. 정의를 잘 살펴보면 상호 의존적인 정의이기 때문에 바로 값을 구할 수는 없다는 것을 알 수 있는데, 처음에 임의로 값을 초기화하고 몇 가지 조건을 더 고려하여 이 계산을 계속 반복해서 돌리면 어떤 값에 수렴하게 할 수 있고 그 결과가 PageRank 순위가 되는 것이다. 수학적으로는 연결 관계를 정의하는 거대한 행렬(행과 열의 개수가 인덱싱한 문서의 개수와 같은...)과 그 행렬과 곱해질 크기의 벡터를 이용하여 위 내용을 수식으로 표현할 수 있고, 이 거대한 행렬을 효과적으로 분산처리하기 위해 power method(링크된 글의 맨 끝 식이 실제로 사용한 것)라는 것을 이용한다.

NexR에서 인턴하면서 이런저런 실습을 하기도 했었고 MapReduce에 어느 정도 익숙하였기 때문에 처음 예상으로는 한 5일이면 되겠다 싶었는데, 웬걸 열흘이 넘게 걸려버렸다. 대상 데이터는 위키백과에서 XML 형식으로 제공되는 dump였는데 총 20GB 분량을 200여개의 파일로 나누어 놓은 것이었다. 알고리즘 구현은 4일 만에 끝났지만 최적화와 디버깅에만 3일이 넘게 걸렸고, 프로젝트 듀가 있던 주말에는 CCI:U 클러스터의 각 노드가 로그 파일로 인해 디스크가 꽉 차는 문제가 발생하여 이를 해결하느라 과제 진행을 못하기도 했다. PageRank 특성 상 어느 정도 수렴할 때까지 계속 반복(iteraion)해야 하는데 처음 짠 버전은 한 번 도는 데 6시간(!)이 넘게 걸렸지만 온갖 최적화와 삽질 끝에 완성한 최종 버전은 불과 2분밖에 걸리지 않았다. (좀 심하게 어이없는 버그가 하나 있었다. 돌아갔던 게 더 신기하달까 싶은...-_-) 허나 거기서 끝난 게 아니라 실제 검색엔진처럼 웹 상에서 키워드 입력하면 결과를 볼 수 있게 만들어야 하는데 결과로 나온 PageRank 벡터 및 문서 ID와 제목의 mapping 등을 DB에 올리는 과정에서 워낙 큰 용량으로 인해 몇 시간씩 돌렸던 것이 중간에 깨지고 버그로 중단되는 등 추가로 하루를 더 소요하였다.

참고로 위키백과의 각종 meta page와 redirection page들을 제외하고 총 3백만개가 약간 넘는 양의 문서에 대한 link graph와 PageRank를 계산하였다. 첨부한 파일은 처리한 데이터를 바탕으로 상위 100개의 페이지들을 모아본 것으로, 주로 나라·지명·년도가 많은 링크가 걸리고 있음을 확인할 수 있다. (좀 예전 데이터를 바탕으로 했기 때문에 현재의 위키백과하고는 다소 다를 수 있음) 원래는 iteration을 적어도 20~30회 이상은 돌려야 하지만 시간 부족 관계로 10번만 돌렸기 때문에 좀 부정확할 수도 있다.

상위 100개 보기

    1: 0.004602 United States
    2: 0.002517 France
    3: 0.001938 England
    4: 0.001836 Germany
    5: 0.001792 World War II
    6: 0.001686 2007
    7: 0.001589 India
    8: 0.001581 Japan
    9: 0.001562 Australia
    10: 0.001556 Canada
    11: 0.001485 London
    12: 0.001484 United Kingdom
    13: 0.001364 2006
    14: 0.001317 2008
    15: 0.001236 Poland
    16: 0.001145 Russia
    17: 0.001129 Italy
    18: 0.001129 New York City
    19: 0.001107 Europe
    20: 0.001066 California
    21: 0.001060 Spain
    22: 0.001031 Paris
    23: 0.001019 2005
    24: 0.000926 Animal
    25: 0.000854 New York
    26: 0.000839 World War I
    27: 0.000827 Brazil
    28: 0.000792 China
    29: 0.000767 Romania
    30: 0.000755 2004
    31: 0.000737 New Zealand
    32: 0.000703 Scotland
    33: 0.000692 Gmina
    34: 0.000656 BBC
    35: 0.000651 European Union
    36: 0.000647 Sweden
    37: 0.000645 Latin
    38: 0.000640 United Nations
    39: 0.000634 United States Census Bureau
    40: 0.000629 Soviet Union
    41: 0.000621 Mexico
    42: 0.000620 Austria
    43: 0.000587 Switzerland
    44: 0.000579 2003
    45: 0.000566 Israel
    46: 0.000562 The New York Times
    47: 0.000560 Washington, D.C.
    48: 0.000555 Netherlands
    49: 0.000552 Texas
    50: 0.000534 Pakistan
    51: 0.000523 (id:17416221, missing title)
    52: 0.000518 North America
    53: 0.000511 Rome
    54: 0.000500 Norway
    55: 0.000490 Turkey
    56: 0.000486 2002
    57: 0.000484 2001
    58: 0.000479 Philippines
    59: 0.000475 Egypt
    60: 0.000463 Ontario
    61: 0.000453 Islam
    62: 0.000452 Greece
    63: 0.000451 Pennsylvania
    64: 0.000450 Ireland
    65: 0.000450 Chicago
    66: 0.000449 2009
    67: 0.000449 Iran
    68: 0.000448 Belgium
    69: 0.000442 Indonesia
    70: 0.000433 Florida
    71: 0.000428 Africa
    72: 0.000414 Berlin
    73: 0.000408 2000
    74: 0.000405 Hungary
    75: 0.000403 Denmark
    76: 0.000398 Portugal
    77: 0.000397 Allmusic
    78: 0.000395 (id:18951905, missing title)
    79: 0.000391 Hong Kong
    80: 0.000385 Finland
    81: 0.000376 Asia
    82: 0.000376 Moscow
    83: 0.000372 Virginia
    84: 0.000371 1999
    85: 0.000371 Los Angeles
    86: 0.000371 (id:19827221, missing title)
    87: 0.000369 South Korea
    88: 0.000363 Ukraine
    89: 0.000359 Wales
    90: 0.000358 Illinois
    91: 0.000357 Christianity
    92: 0.000355 (id:19344515, missing title)
    93: 0.000353 People's Republic of China
    94: 0.000352 (id:21786641, missing title)
    95: 0.000344 Quebec
    96: 0.000342 Iraq
    97: 0.000341 American Civil War
    98: 0.000338 Massachusetts
    99: 0.000334 (id:18618239, missing title)
    100: 0.000329 1998

중간에 missing title이라고 된 것은 Redis라는 key-value storage를 검색엔진 구현에 사용하다가 너무 많은 데이터(대략 레코드 수 560만개?)가 들어가니 32bit 메모리 영역을 초과하여 더 이상 들어가지 못해 발생한 것이다. 문제는 이 프로젝트 때문에 지난 주와 이번 주 내내 거의 아무것도 못하고 밤샘하다가 수업을 5차례나 째는(...) 로드가 걸렸다는 것. 작곡 2번, 로보틱스 2번, 분산처리 1번...; ㅠ_ㅠ

PageRank 논문을 보면 1999년 당시 사용한 페이지 수가 7천5백만개였으니 내가 해본 데이터 크기가 대략 이것의 4% 크기인데, 그때와 지금의 컴퓨터 성능 차이를 생각해보면 Google이 얼마나 대단한지 알 수 있다. 3백만개의 원소를 가지는 벡터 2개 정도는 대충 1GB 메모리에 다 올려놓고 계산해버릴 수 있지만 저 정도 되면 논문에서 이야기한 것처럼 여러 pass에 걸쳐 계산하도록 만들어야 할 것이다.

어쨌든 이번 프로젝트를 통해 대용량 데이터를 다루는 작업이 얼마나 어려운지--조금만 실수해도 몇시간 분량의 작업을 날려먹으니--뼈저리게 깨달을 수 있었고, 또한 어떤 점들을 조심해서 짜야 하는지, Hadoop 사용·설정 노하우 등을 얻을 수 있었다. 3명이서 팀으로 하는 기말프로젝트 proposal로는 GPU 가속을 이용한 행렬 연산과 MapReduce programming model의 결합에 관한 아이디어를 발표했는데 이건 또 얼마나 삽질을 하게 될런지 모르겠다. ㅠ_ㅠ

덧: 교수님이 왤케 자꾸 밤새면서 작업하냐고 물으시길래 '연속적으로 집중할 수 있는 시간'을 확보하기 위한 거라고 말씀드렸다. 학생들끼리 같이 무얼 해보려고 해도 보통 낮에는 시간이 안 맞는 경우가 많아 밤에 뭘 하는 경우가 많다보니 낮엔 각자 다른 일을 하고 밤에 모여있는 것이 습관화되어 어쩔 수 없이 생활리듬도 그렇게 바뀌어가는 듯하다. 하는 일을 줄이면 괜찮을 텐데 새로운 일을 추가하지 않아도 이미 있는 일들만으로도 충분히 빡센 것도 문제인 듯.

URP 포스터 제작 듀가 내일이었다니! orz 요즘 한창 textcube.org 작업한답시고 정신없었던 지라 완전 까맣게 있고 있었는데, 어제인가 갑자기 연락이 와서 부랴부랴 만드는 중이다.

최종 제출한 포스터. 자세한 내용은 생략 =3

사실 이 연구 과제도 참 우여곡절이 많았다. 원래 한 과제 당 최대 3명만 한 팀이 될 수 있기 때문에 로봇 제작과 시뮬레이션 두 팀으로 나눠 총 6명을 모집했고, 그 중 한 명이 중도탈락하여 5명이서 끝까지 진행하게 되었다. 처음에는 호주의 모 대학에서 개발한 개발 키트 비스무리(?)한 것을 이용하려고 관련 매뉴얼을 스터디하다가 실제 구입하려고 알아보니 구입 후 배송 기간이 URP 연구 기간과 맞먹는(...) 바람에 겨울방학을 안드로메다로 날려보낸 후 봄학기 개강과 함께 그 악명높은 소프트웨어공학 개론과 씨름하다보니 어느새 5월(....). 그제서야 새로 잡힌 방향대로 주문했던 장비들이 도착하기 시작했고 5월 말이 되어서야 겨우 전자회로 조립을 시작할 수 있었다.

...뭐 그래서 결국은 센서 몇 개 연결하다가 조립은 끝났고, 시뮬레이션 쪽은 Subsim이라는 시뮬레이션 프로그램을 이용하여 간단한 모델 몇 가지 테스트해보는 것으로 마무리되었다. 나는 서류 상으로는 시뮬레이션 팀이었지만 로봇을 만드는 MR 동아리에 있다는 이유(?)로 제작팀에 차출(?)되어 마지막엔 로봇 제작만 했다. 대신 시뮬레이션 쪽은 완전히 신경을 꺼도 좋다는 허락을 받기는 했는데, 그래서 포스터를 만들려고 보고서를 보니 먼산(...).. 그나마 다행인 건 Subsim을 한창 다루기 시작할 때 나도 참여를 했었기 때문에 내용 이해가 어렵지는 않다는 것. 문제는 보고서가 영어라서 귀찮다는 것. -_-;

이 연구를 순수 바뇌과 3명(그 중 한명은 고등학교 동기다)이서 이어받아 하고 있지만, 교수님은 너무 바쁘셔서 말로만 '무인잠수정 대회 나가야지' 이러면서 막상 실질적 도움은 거의 안 되고 조교님들도 로봇 제작 경험이 전무하기 때문에 결국 모든 삽질은 학부생이 해야 하는 상황인지라 앞날이 어떻게 될지는 잘 모르겠다. 그래도 랩에서 몇 년 동안 계속 할 연구라서 언젠가 빛(...)을 보리라 생각(하고 싶)다.;;

고등학교 때 R&E 사사연구를 했던 경험에 비추어보면, 당시에는 연구 기간이 똑같이 6개월이었어도 정규 학기가 먼저고 방학이 나중이었는데, URP는 방학에 시작해서 정규 학기와 함께 끝나는 방식이었다. 다들 방학 때 열심히 하고 학기 중에는 놀아야지라고 생각하며 시작하지만 연구라는 게 그렇지가 않아서, 아무리 주제를 미리 잡고 시작한다고 해도 우리처럼 장비 구입에 수 개월이 소요되는 경우도 생기고 여러 자료를 찾아보다가 연구 방향이 바뀔 수도 있는 것이어서, 결국 막판 스퍼트를 해야 한다. 근데 정규 학기 중에 막판이라면 기말고사와 각종 기말프로젝트가 다 겹치는 기간이라서 그게 사실상 불가능한 것이고, 이 점은 URP 만족도 설문조사에서도, 또 담당자한테 직접 내가 몇 차례 건의한 부분이기도 하다.

어쨌든 이 포스터만 제출하면 사실상 URP는 끝나는 거나 마찬가지다. 많은 과목들을 들으며 학점 관리를 병행해야 하고, 또한 동아리 활동 등에도 참여해야 하는 학부생 특성상 연구 과제를 수행한다는 것이 시간적인 면에서 쉽지는 않다. (아놔 망할 SE ㅠ_ㅠ) 그래도 이런 제도가 있다는 것은 환영할 만한 일이고, 돌이켜 생각해보면 고등학교 때 R&E를 해서 정보과학회에 논문까지 냈던 게 지금 봐도 대단한 일이다. URP 연구가 좀더 제대로 수행되는 사례가 많아지길 바라면서 끝마친다.

간만에 그린 그림. 그린 지는 좀 된 것인데 마침 생각나서 올려본다.

주제 1

주제 2

주제 3

앞서 모종의 테스트 목적 및 개인 사용 목적으로 명함을 하나 만든다고 했었다. 지난 주 목요일에 주문, 드디어 도착했다. 드디어 공개한다.

명함 작업본

실제 인쇄 결과물

확실히 그라데이션 처리한 부분이 인쇄는 의도대로 잘 되었음에도 눈으로 보기에는 모니터보다 훨씬 연하다. (자세히 들여다보면 잉크 망점이 찍혀는 있으나 너무 작아서..-_-) 색깔은 RGB 빛으로 색을 내는 모니터에 비해 조금 덜 화사하게 나왔지만 어느 정도 예상했던 바였고, 룸메 말로는 오히려 인쇄한 게 낫다고(...) 하니 이 정도면 만족.

다만 살짝 아쉬운 것은 진한 검정 배경에 컬러 글자를 찍으면서 검정과 다른 색상들의 위치가 정확하게 맞지 않아 0.1mm 이하 정도로 어긋나는 바람에 자세히 보면 글자 획의 오른쪽 방향으로 흰줄들이 아주 가늘게 보인다는 것. 그래도 이 정도면 만족할 만한 품질이다.

뒷면의 비트맵 이미지는 아마 이 블로그를 계속 봐온 사람이라면 알 것이다. 새로 이사 간 집의 부엌에 달기 위해 그린 그림인데, 단면으로 만들자니 심심하고, 양면으로 만들자니 딱히 뒷면에 넣을 만한 것(개인 명함이다보니 회사 약도나 로고를 넣는다거나 할 것도 없고 하니까)이 없어서, 내 개성을 살리자는 뜻에서 내가 직접 그린 작품을 넣은 것이다.

비트맵의 해상도는 권장 300dpi보다 낮은 240dpi 정도인데, 잉크 망점들로 인쇄가 되어 있어서 계단 현상은 전혀 보이지 않는다. 어떻게 나올까 가장 걱정했던 부분인데 깔끔하게 잘 나왔다. 재단선 처리도 작업할 때 생각하고 했던 것하고 거의 똑같다.

자, 그럼 이제 다음 번 블로거 모임 등에 나갈 때부터 이 명함을 쓰면 되겠지. 우선 동아리 사람들한테 좀 돌려야겠다. :D

덧. 살짝 이름의 위치를 조금 더 왼쪽으로 했으면 좋았을 걸 하는 생각이 든다.;

참고: 디카로 찍은 사진을 다시 모니터로 보니 실제 종이를 눈으로 보는 것과는 또 다르다. 그래도 이 정도면 대충 차이를 알 수 있을 듯?;;

푸르지오 아파트 로고가 걸려있던 부엌 벽의 퓨즈함 그림을 대체하기 위해 그린 그림이다. A4 용지에 원래 그림 크기를 맞춰서 잘라 그렸고 아트펜을 사용하였다. 푸르지오 로고로부터 영감을 얻었다. (화원 같지만 그렇다고 현실 속에 존재하지는 않는 그런 것이랄까.)

부엌에 건 그림 작품.

ps. 원하시는 분은 가져가서 바탕화면 등으로 사용하셔도 좋습니다. (좀 어지러우려나요-_-) 사이즈가 1024x768에 맞춰져 있지 않지만 살짝 편집해주시면 될 겁니다.

ps2. 불펌은 금지합니다. 퍼가실 땐 이 글에 대한 링크를 명시해주셔야 하며, 그림을 재처리하거나 다른 작품에 사용하게 될 때에는 댓글로 해당 작품을 볼 수 있는 링크를 걸어주시면 고맙겠습니다.

원래 시험 기간이 되면 이런 짓을 하고싶은 법. 오랜만에 그림을 그려봤다.

해산물 (by 휘아)

어렸을 때, 그러니까 컴퓨터를 접하기 전인 초등학교 3학년 정도까지, 내 하루 일과 중 가장 중요하고도 빼먹지 않았던 것이 바로 8절지 스케치북에 그림 그리는 것이었다. 그때 우주과학에 대한 관심이 많아서, 주로 우주 정거장이나 전쟁 모습 등을 사인펜 및 로트링 펜(만화가나 건축가들이 쓰는 매우 가느다란 독일제 펜으로 꽤나 비싸다 -_-)을 이용해 그렸었다. 그 후 초등학교 5학년 무렵부터 그 로트링 펜 0.3 mm짜리를 가지고 부모님께 눈나빠진다는 소리 들어가며 엄청난 양의 미로를 그려댔었다. (미로 길의 너비가 평균 2 mm가 안 넘었을 거다)

얼마 전에 봤던 몰스킨 이야기도 생각나고, 요즘 필기용으로 쓰는 펜이 아버지께서 선물해주신 아트펜이라는 것이 생각나 일전에 유키구라모토 연주회 갔다가 앨범 사면서 받아온 노트에 그려보았다. 그냥 생각나는 대로 그린 것인데, 그려놓고 보니 상상 속의 동식물(?)들도 보이고, 도저히 뭔지 알 수 없는 것들도 보인다. (....)

쩝쩝. 그림이 의미하는 바가 뭔지는 알아서들 생각하시길. (이게 내 정신 세계라든가 하는 농담은 사절 -_-)