http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
볼쯔만 머신 모델에 기초한 마감 시간을 갖는 다중처리기 태스크의 스케쥴링 방법
김진석(Jin Snk Kim),낭종호(Jong Ho Nang),윤현수(Hyunsoo Yoon),맹승렬(Seung Ryoul Maeng) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.9
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. 실시간 특성을 갖는 다중처리기 태스크 스케쥴링은 매우 어려운 최적화 문제로 잘 알려져 있기 때문에 이 문제를 해결하기 위한 근사(approximation)기법이나 휴리스틱 알고리즘이 개발되었다. 신경망의 일종인 볼쯔만 머신은 병렬로 수행될 수 있는 근사 기법이며 많은 최적화 문제를 잘 해결할 수 있음이 알려져 있다. 본 논문에서는 실시간 특성을 갖는 다중처리기 태스크 스케쥴링 방법을 제안하였다. 또한 제안된 볼쯔만 머신의 consensus 함수를 극대화하면 스케쥴링 문제에서 한계시간내에 수행을 마치는 태스크의 갯수를 극대화 할 수 있다는 것을 증명하였다. 그리고 시뮬레이션을 통하여 볼쯔만 머신이 기존의 휴리스틱 알고리즘보다 스케쥴링을 더 잘 함을 보였다.