http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Heterogeneous환경을 위한 태스크 스케쥴링 알고리즘
우성호(S.H. Woo),이현수(H.S. Lee),양성봉(S.B. Yang),한탁돈(T.D. Han),김신덕(S.D. Kim) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A
본 논문에서는 heterogeneous환경하에서 작업의 효율적인 스케쥴링을 위하여 유전자 알고리즘(GA)을 최적화의 도구로 이용한 새로운 알고리즘을 제안한다. 태스크 스케쥴링 문제는 NP-complete문제로서 프로세서간의 heterogeneous성질이 추가 되므로써 더 복잡하게 된다. 이 문제의 해결을 위해 heuristic과 approximation을 이용한 다양한 연구들이 진행되어 왔다.[5,8] 본 논문에서는 태스크들을 성질이 다른 프로세서에 할당시켜 수행시간을 최소화시키는 스케쥴링 알고리즘을 GA를 사용하여 설계하였고 heterogeneous환경의 특성을 고려하여 x-pocket이라는 새로운 crossover연산자를 소개한다. 그리고 다양한 crossover연산자들을 이용한 GA와 x-pocket을 이용한 스케쥴링의 결과를 비교 분석하였고 GA의 성능을 향상시키기 위해 restart방법을 사용하였다.
맹혜선(H.S. Maeng),이현수(H.S. Lee),권오영(O.Y. Kwon),양성봉(S.B. Yang),김신덕(S.D. Kim),한탁돈(T.D. Han) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A
병렬처리 분야에서는 워크스테이션 네트워크(WN)가 일반적인 컴퓨팅 환경으로 자리잡아 가고 있다. WN 환경에서는 자원을 요구하는 작업들이 시간이 지남에 따라 변화하기 때문에 특정 작업에 이용될 수 있는 CPU time, 즉 프로세서의 가용한 처리 능력이 변화한다. 따라서 이 환경에서 데이타 병렬 문제를 효율적으로 병렬 수행시키기 위해서는 실행시간 동안 변화하는 프로세서의 가용한 처리 능력에 따라서 각각의 프로세서에 작업량을 재할당 시키는 동적 부하 조정이 필요하다. 이 논문에서는 외부 작업이 유입될 때 효율적으로 대응할 수 있도록 부하 조정 시점을 실행 시간 동안 동적으로 변화시키는 방법을 제안하였다. 이 방법을 통하여 부하 불균형으로 인하여 여러 프로세서들이 동기화 시점 수행을 멈추고 특정 프로세서를 기다리면서 발생하는 대기 시간을 감소시키고 따라서 전체 수행시간을 단축시킨다. ISING 문제를 대상으로한 실험에서 본 논문의 방법은 부하 조정을 수행하지 않는 경우와 비교하여 최대 30%까지 수행시간을 감소시켰음을 보였다.
요구량의 지역성에 기반을 둔 섹터링을 통한 마지막 도착 허용 시간을 가지는 차량 라우팅 문제
김병욱(B.U. Kim),양성봉(S.B. Yang) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.1A
마지막 도착 허용 시간을 가지는 차량 라우팅 문제는 전통적인 차량 라우팅 문제에 마지막 도착 허용 시간의 시간적 제약 조건을 가진다. 따라서 서비스를 받는 소비자의 지역적인 특성과 시간적인 특성을 고려해야 한다는 어려움이 따른다. 또한 이러한 시간적 제약 조건을 가지는 문제는 N-P hard한 문제로서 최적의 해 또는 그 근사값을 유용한 시간안에 구할 수 있는 효과적인 라우팅을 위한 경험적 방법이 주 연구 대상이 되어 왔다. 본 논문에서는 소비자 요구량의 지역성을 기반으로 하는 섹터링을 통해 라우팅의 범위를 각 섹터당으로 제안하여 계산 복잡도를 줄이고 또한 전체 라우팅 길이와 지연 소비자의 최소화를 위한 알고리즘을 제안한다. TNEWSEN을 통해 생성된 데이터 셋에 대해 기존의 경험적인 알고리즘의 대표적인 갈망 방법에 기반을 둔 DSH와의 성능 평가에 따르면 전체 라우팅 길이가 15% ~ 20% 정도 향상되었음을 알 수 있다.
이동 공유 데이터를 위해 변형한 적응 캐쉬 일관성 프로토콜
김효선(H.S. Kim),양성봉(S.B. Yang) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.2Ⅳ
같은 프로세서가 공유 데이터를 읽고 바로 쓰기 작업을 하는 경우 그리고 이런 수행이 다른 프로세서로 이동하면서 반복적으로 일어나면 이런 일련의 수행들을 메모리에 읽기 요청 후 쓰기 요청을 한다. 이런 특징을 나타내는 공유 데이터를 이동 공유 데이터라고 한다. 그런데 쓰기 요청을 받은 디렉토리 메모리는 그 공유 데이터를 캐쉬에 가지고 있는 노드(프로세서 + 지역캐쉬)에 무효화 요구를 보내는데, 공유 데이터를 가지고 있는 노드가 하나이기 때문에 무효화 요구도 하나가 발생한다. 이처럼, 이동 공유 데이터는 캐쉬 접근 실패 후 하나의 무효화 요구를 야기시킨다. 이동 공유 데이터의 특징을 나타내는 블록은 캐쉬 접근 실패시 읽기 요구와 무효화 요구를 합하므로써 캐쉬간의 오퍼래이션(operation)의 수를 줄일 수 있다. 다른 블록에 대해서는 보통의 쓰기 무효화 프로토콜을 적용시키므로써 동적으로 프로토콜을 적용시킬 수 있다. 본 논문에서는 이동 공유 데이터를 더 빨리 발견하므로써 프로토콜을 보다 효율적으로 적용시켰다.
서충원(Choong-Won Seo),강윤식(Y.S. Kang),양성봉(S.B. Yang) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.2A
본 논문에서는 메타 테이블(meta table)을 이용한 광선(ray)과 삼각형(triangle)들의 교차검사를 할 수 있는 효율적인 레이트레이싱 알고리즘을 제안한다 기존의 kd-tree 탐색은 깊이 우선 탐색을 하면서 이미 방문했던 노드들을 방문하지 않기 위해서 스택을 이용하는 방법을 택하고 있는데, 본 논문에서 제안하는, 알고리즘은 스택을 사용하지 않고 읽기 전용으로만 쓰이는 메타 테이블을 둠으로써 기존의 트리 탐색 과정보다 효율적으로 트리의 리프 노드들에 접근할 수 있도록 하였다 실험결과 제안된 레이트레이싱 알고리즘이 기존의 kd-tree의 트리 탐색보다 노드 방문을 5배 이상 적게 하였고, 이미지 렌더링 시간도 총 2배 정도 향상됨을 볼 수 있었다.