| [ CnUnix ] in KIDS 글 쓴 이(By): 파란거북 (...) 날 짜 (Date): 2004년 12월 9일 목요일 오전 04시 52분 48초 제 목(Title): 알고리즘을 찾습니다. 분산 처리를 할수 있는 다음과 같은 조건을 만족하는 알고리즘을 찾고 있습니다. 대충, image processing, image compression쪽에 그런 게 있지 않을까 싶은데, 제가 그쪽에 문외한이라서요. 아님, scientific computing쪽에도 candidate이 많이 있을것 같은데... CnUnix보드에 맞는 질문은 아니겠지만, "CnUnix에 물어보면 다 대답해주더라" 는 미신(?)을 믿고 있어서... #. 일단 parallelizable (분산해서 execute) 할수 있어야 하구요. #. 같은 일을 처리하기 위해 몇개의 (많으면 많을수록 좋구요) 다른 알고리즘이 존재해야하고, 이 알고리즘들이 주어진 input data나 다른 상황 변화에 의해 다른 performance를 보여주는 것이어야 합니다. #. computing-intensive해서, 분산처리를 위해 데이타를 주고받는 overhead보다 computing자체에 걸리는 시간이 충분히 길었으면 좋겠고.. 대충 위의 조건을 만족하는 알고리즘의 예로는 sorting이 있습니다. 아시다시피, sorting은 분산할 수 있고, 매우 다양한 알고리즘이 있죠. quick sort같은 것은 N log(N) 이고, insertion sort는 N^2 이고... 보통의 random data에 대해선,당연히 quick sort가 빠르지만, 만약 데이타가 거의 sort되어 있는 상태에서 들어온다면, insertion sort 가 N으로 처리할 수 있죠. (항상 winner가 정해져 있는게 아니라, 상황에 따라 다른 algorithm이 best algorithm이 될 수 있다는 것이 중요합니다.) 근데, sorting은 그렇게 computationally intensive하지는 않아서, 많은 수의 machine들에 나누어 돌릴 필요는 별로 없더라구요. 많은 수의 machine들에 분산시켜 계산할 수 있는 것이면 좋겠거든요. 어떤 research idea를 검증해보려고 그에 마땅한 경우를 찾고 있는 것이라, 질문이 좀 애매한 점도 있네요. 꼭 정답이 아니더라도 생각나는 것들을 써서 답해주시면 큰 도움 되겠습니다. |