볼쯔만 머신 모델에 기초한 마감 시간을 갖는 다중처리기 태스크의 스케쥴링 방법 = A Scheduling Method for Multiprocessor Tasks with Deadlines Based on Boltzmann Machine Model

다국어 초록 (Multilingual Abstract)

Since the problem of scheduling multiprocessor tasks with deadlines is known as a hard combinatorial optimization one, an approximation or heuristic algorithm has been studied. A Boltzmann machine is such an approximation method based on neural network that can be executed in highly parallel. In this paper, we propose a mapping scheme of the scheduling problem onto a Boltzmann machine and a Boltzmann machine-based scheduling method for multiprocessor tasks with deadlines. It is proven that maximization of the consensus function of the Boltzmann machine corresponds to finding a schedule with the maximum number of tasks that can be completed without violating their deadlines. It is argued by simulations that the Boltzmann machine configured with this mapping scheme outperforms the traditional heuristic scheduling algorithms.

국문 초록 (Abstract)

실시간 특성을 갖는 다중처리기 태스크 스케쥴링은 매우 어려운 최적화 문제로 잘 알려져 있기 때문에 이 문제를 해결하기 위한 근사(approximation)기법이나 휴리스틱 알고리즘이 개발되었다. 신경망의 일종인 볼쯔만 머신은 병렬로 수행될 수 있는 근사 기법이며 많은 최적화 문제를 잘 해결할 수 있음이 알려져 있다. 본 논문에서는 실시간 특성을 갖는 다중처리기 태스크 스케쥴링 방법을 제안하였다. 또한 제안된 볼쯔만 머신의 consensus 함수를 극대화하면 스케쥴링 문제에서 한계시간내에 수행을 마치는 태스크의 갯수를 극대화 할 수 있다는 것을 증명하였다. 그리고 시뮬레이션을 통하여 볼쯔만 머신이 기존의 휴리스틱 알고리즘보다 스케쥴링을 더 잘 함을 보였다.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 2. 실시간 특성을 갖는 다중처리기 태스크 스케쥴링 문제
• 3. 볼쯔만 머신의 구조
• 4. 스케쥴링 문제를 풀기 위한 볼쯔만 머신
• 5. 시뮬레이션 및 결과의 분석
• 6. 결론
• 참고문헌
• 저자소개