이기종 멀티프로세서 시스템에서 삽입과 복제를 고려한 효율적인 태스크 스케줄링 알고리즘

윤완오(WanOh Yoon),송인성(InSeong Song),이창호(ChangHo Lee),최상방(SangBang Choi) 한국정보과학회 2011 정보과학회논문지 : 시스템 및 이론 Vol.38 No.2

이기종 멀티프로세서 시스템 환경에서 방향성 비순환 그래프(DAG)의 각 태스크를 효율적으로 스케줄링 하는 것은 전체 시스템의 성능을 향상시키는데 매우 중요한 역할을 한다. 이기종 멀티프로세서 시스템 환경에서 입력 DAG로 표현되는 병렬 응용프로그램을 스케줄링 하기 위한 최적의 방법을 찾는 것은 ‘NP-complete’ 문제로, 최적에 가까운 스케줄링 결과 값을 얻기 위해서는 휴리스틱 방법으로 접근해야 한다. 본 논문에서는 프로세서선택 과정에서 각 태스크의 삽입과 복제 여부를 함께 고려하여 최적의 프로세서를 선택함으로써 전체적인 성능을 향상시키는 HMPID 알고리즘을 제안한다. 제안하는 알고리즘의 성능 분석을 위해 많은 수의 입력 그래프를 생성하여 삽입 또는 복제의 방법을 사용하는 기존의 대표적인 태스크 스케줄링 알고리즘인 HCPFD, DCPD, HEFT와 비교하였다. 비교 실험 결과 본 논문에서 제안하는 HMPID 알고리즘이 기존의 알고리즘에 비해 뛰어난 성능을 보이는 것을 확인하였다. In heterogeneous multi-processor system, efficient scheduling of tasks in DAG is a key to improve the performance of the system. Finding the best optimal scheduling method of parallel application which is modeled as an input DAG, is an NP-complete problem. So, heuristic method has to be used to find the sub-optimal method. In this paper, we propose a HMPID algorithm which considers both insertion and duplication in processor selection phase. To analyze the performance of the proposed algorithm, we generated various input graphs and compared the results with HCPFD, DCPD, HEFT, the most popular conventional task scheduling algorithms. The results show that HMPID algorithm provides superior performance than other conventional algorithms.

Task Scheduling Algorithm using Constrained Duplication in Homogeneous Systems

Myongjin Cha,Wanoh Yoon,Moonsuk Jang,Sangbang Choi 대한전자공학회 2005 ITC-CSCC :International Technical Conference on Ci Vol.2005 No.1

Differentiation of Congestion and Wireless Losses in Multi-flows

Sungyoon Ryu,Wanoh Yoon,Sangbang Choi,Kwangsik Shin 대한전자공학회 2005 ITC-CSCC :International Technical Conference on Ci Vol.2005 No.3

태스크 복제 기반 프로세서 할당 방법에 최적화된 태스크 우선순위 결정 알고리즘

송인성 ( Inseong Song ),윤완오 ( Wanoh Yoon ),이창호 ( Changho Lee ),최상방 ( Sangbang Choi ) 한국인터넷정보학회 2011 인터넷정보학회논문지 Vol.12 No.6

분산 이기종 컴퓨팅 시스템의 성능은 입력 그래프인 방향성 비순환 그래프(DAG)를 스케줄링 하는 알고리즘의 성능에 따라 좌우된다. 그러나 분산 이기종 컴퓨팅 시스템에서의 태스크 스케줄링은 NP-complete 문제로 휴리스틱 방법으로 접근해야 한다. 태스크 스케줄링 알고리즘은 우선순위 결정 단계와 프로세서 할당 단계로 구성되며, 많은 연구들이 두 단계를 함께 고려하고 있다. 본 논문에서는 태스크 우선순위 결정 단계에 초점을 맞추어 태스크 복제 기반 프로세서 할당 방법에 최적화된 태스크 우선순위 결정 알고리즘인 WPD 알고리즘을 제안한다. 제안하는 WPD 알고리즘의 성능 분석을 위해 태스크 복제 기반프로세서 할당 방법을 사용하는 기존의 태스크 스케줄링 알고리즘인 HMPID, HCPFD, HCT 알고리즘의 프로세서 할당 단계에 본 논문에서 제안하는 WPD 알고리즘을 결합하여 성능을 비교하였다. 그 결과 본 논문에서 제안하는 WPD 알고리즘이 기존태스크 우선순위 결정 방법에 비해 태스크 복제를 더욱 효율적으로 사용하여 HCPFD 알고리즘보다 9.58%, HCT 알고리즘보다 1.31% 성능 향상이 있는 것을 확인하였다. The performance of DHCS depends on the algorithm which schedules input DAG. However, as the task scheduling problem in DHCS is an NP-complete problem, heuristic approach has to be made. Task scheduling algorithm consists of task prioritizing phase and processor allocation phase, and most of studies are considering both phases together. In this paper, we focus on task prioritizing phase and propose a WPD algorithm which is optimized for task duplication based processor allocation method. For an evaluation of the proposed WPD algorithm, we combined WPD algorithm with processor allocation phase of HMPID, HCPFD, HCT algorithms, which are using task duplication based processor allocation method. The results show that WPD algorithm makes a better use of task duplication than conventional task prioritizing methods and provides 9.58% better performance than HCPFD algorithm, 1.31% than HCT algorithm.

A Hybrid Routing Algorithm for an Efficient Shortest Path Decision in Network Routing

Taehwan Cho,Kyeongseob Kim,Wanoh Yoon,Sangbang Choi 보안공학연구지원센터 2013 International Journal of Multimedia and Ubiquitous Vol.8 No.4

멀티스레드 어플리케이션을 위한 실시간 성능모니터의 구현

김진혁(JinHyuk Kim),신광식(KwangSik Shin),윤완오(WanOh Yoon),이창호(ChangHo Lee),최상방(SangBang Choi) 大韓電子工學會 2011 電子工學會論文誌-CI (Computer and Information) Vol.48 No.3

마이크로프로세서의 발전과 함께 멀티코어 시스템은 점차 보편화 되어가고 있다. 이러한 하드웨어 성능향상 패러다임의 변화로 인해 소프트웨어의 성능향상을 위해서는 기존의 싱글 스레드 어플리케이션들을 멀티 스레드 어플리케이션들로 교체하는 과정이 필수적이다. 멀티 스레드 어플리케이션 개발의 복잡성 때문에, 성능모니터링 도구는 어플리케이션의 성능 최적화를 지원하기에 유용한 도구로 사용된다. 기존의 성능모니터링 도구는 사용의 편의성이나 실시간성의 지원보다는 성능 측정 자체에 초점이 맞춰져 있다. 실시간 성능 모니터는 멀티 스레드 어플리케이션이 수행하는 동안 나타나는 문제점을 파악하는 것 뿐 아니라 실시간으로 어플리케이션의 동작 상태를 개발자가 확인 할 수 있기 때문에 단순한 성능 지표들만으로 문제점의 원인을 찾아내야하는 비 실시간 성능 모니터에 비해 효과적인 도구로 사용될 수 있다. 본 논문에서는 멀티코어 시스템을 위한 실시간 성능모니터링 도구인 RMPM(Real-time Multi-core Performance Monitor)를 제안하고 성능 측정 주기로 인한 오버헤드와 정확성 사이의 관계를 비교하여 최적의 측정 주기를 결정하였다. 제안한 성능모니터는 전체시스템의 CPU 사용량, 메모리 사용량, 네트워크 사용량 뿐아니라 시스템의 코어별, 어플리케이션의 스레드별 부하 분산상태를 나타낼 수 있다. Multi-core system is becoming more general with development of microprocessors. Due to this change in performance improvement paradigm, switching conventional single thread applications with multi thread applications. Performance monitoring tools are used to optimize application performance because of complexity in development of multi thread applications. Conventional performance monitoring tools are focused on performance itself rather than user friendliness or real-time support. Real-time performance monitor identify the problem while multi-threaded applications should be performed as well as check real-time operating status of the application. So it can be used as an effective tool compared to non-real-time performance monitor that only with simple performance indicators to find the cause of the problem. In this paper, we propose RMPM(Real-time Multi-core Performance Monitor) which is real-time performance monitoring tool for multi-core system. Observation period is optimized by comparing relation between overhead due to performance evaluation period and accuracy. Our performance monitor shows not only amount of CPU usage of whole system, memory usage, network usage but also aspect of overhead distribution per thread of an application.

비동기 분산 시스템에서의 실시간 리더 선출 알고리즘

장은미(Eunmee Jang),윤진원(Jin won Yoon),윤완오(Wanoh Yoon),송인성(Inseong Song),최상방(Sangbang Choi) 한국정보과학회 2011 정보과학회논문지 : 시스템 및 이론 Vol.38 No.6

본 논문에서는 비동기 분산 시스템에서 프로세스 그룹으로 이루어진 전체 시스템의 일부 프로세서에서 고장이 발생한 경우 이를 즉시 검출해내기 위한 고장 검출 알고리즘과, 이를 적용하여 프로세스 그룹의 리더에 고장이 발생한 경우 대신 할 수 있는 실시간으로 리더를 선출하기 위한 RTLE(Real-time Leader Election) 알고리즘을 제안한다. 실시간으로 동작중인 프로세스의 목록을 파악하고 이를 사용하여 차기 리더가 될 수 있는 프로세스의 목록을 만들도록 설계하였으며, 각 프로세스는 현재 리더 프로세스의 고장이 검출된 경우에 바로 후보자 목록을 참조하여 가장 우선순위가 높은 후보가 차기 리더가 될 수 있도록 설계하였다. 본 논문에서 제안한 고장 검출 알고리즘과 이를 적용한 리더 선출 알고리즘의 실험 결과 제안한 고장 검출 알고리즘은 비교대상인 A. Mostefaoui의 알고리즘에 비하여 네트워크의 지연이 존재하는 환경에서도 안정적인 동작을 하는 것을 확인할 수 있었다. 제안한 RTLE 알고리즘 역시 타 리더 선출 알고리즘에 비하여 연결되는 프로세스의 개수, 네트워크 지연시간, 그리고 리더 외에 추가로 고장이 발생하는 리더 후보의 변화가 존재하는 환경에 대해서도 안정적인 동작을 하는 것을 확인하였다. In this paper, a failure detection algorithm for efficient detection of failure occurred in some parts of a system consisting a process group in non-synchronized distributed system is proposed, and with applying the algorithm, a RTLE algorithm to make election of a new leader in case failure of the process working as a leader is also proposed. It is designed to make lists of currently working processes which are used for making list of next leader candidates in real-time. Each process references the list of candidates and the process with the highest priority works as a next leader in case of current leader failure. The evaluation results showed that proposed failure detection algorithm is more stable compared to A. Mostefaoui"s algorithm even in environment with network delays. Proposed RTLE algorithm is also much more stable compared to other algorithms even in environment with changes in number of processes, network delay and number of additionally crashed leader candidates.

동질 시스템에서 제한된 복제를 사용하는 스케줄링 알고리즘

차영진(Myongjin Cha),정진하(Jinha Cheong),윤완오(Wanoh Yoon),신광식(Kwangsik Shin),최상방(Sangbang Choi) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.2Ⅰ

동질 시스템에서 분산 프로그램을 스케줄링할 경우 프로세서 사이의 통신 시간으로 인해 복제를 사용하는 태스크 스케줄링 알고리즘이 복제를 사용하지 않는 방법에 비해 향상된 결과를 얻을 수 있다. 하지만 불필요한 복제로 인해 자원을 낭비하여 프로세서가 제한된 경우 전체 수행시간이 증가하게 된다. 그래서 본 논문에서 조인 노드를 스케줄링할 경우 불필요한 복제가 발생되는 문제점을 해결하는 알고리즘을 제안하였다. 이러한 문제점을 해결함으로써 프로세서의 제한이 있는 경우에 기존의 북제 알고리즘에 비해 전체 수행기간이 개선되는 결과를 얻을 수 있었다.

The Improvement of Aircraft Position Information with the Unscented Kalman Filter

Taehwan Cho,Inseong Song,Eunmee Jang,Wanoh Yoon,Sangbang Choi 보안공학연구지원센터 2012 International Journal of Database Theory and Appli Vol.5 No.2

이질 시스템에서 통신 시간을 고려한 복제 기반 태스크 스케줄링

백정규(Jungkyu Baek),정진하(Jinha Cheong),윤완오(Wanoh Yoon),신광식(Kwangsik Shin),최상방(Sangbang Choi) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.2Ⅰ

병렬 및 분산 컴퓨터 시스템에서 선후 관계의 제약을 갖는 노드들의 스케줄링은 잘 알려진 NP-complete이다. 이러한 노드들의 스케줄링을 효율적으로 수행하기 위해 많은 알고리즘이 부모 노드와 이질 프로세서에 대한 정보를 고려하여 제안되었다. 하지만 여러 개의 부모 노드와 이질 프로세서에 대한 다양한 경우를 충분히 고려 하지 못했다. 본 논문은 부모 노드에 대한 선후 관계와 이질 시스템의 특성을 고려, 이질 수행 시간을 갖는 다중 프로세서를 대상으로 태스크가 가능한 빨리 수행할 수 있는 시간과 태스크가 가능한 빨리 완료될 수 있는 시간을 이용한 복제 기반의 태스크 스케줄링 기법(DTSC)을 제안하였다. 제안된 알고리즘의 성능은 기존 STDS 알고리즘과 대표적인 입력 그래프에 대해 비교하였고, 스케줄링의 성능 향상을 보여 주었다.