초록 ▼

병렬처리 가능한 응용 프로그램들을 다중처리기 상에서 신속히 처리하기 위한 여러가지 다중처리기 스케쥴링 기법들이 제안되어 왔으나, 이 방법들 대부분은 특정 시스템의 하드웨어 특성에 맞게 설계되어 있기 때문에 매우 한정적이고 제한적으로 밖에는 사용될 수 없다. 본 연구에서는 이러한 문제점을 해결하는 하나의 방법으로 Polynomial-time에 최적해에 근접할 수 있으면서 여러 종류의 응용 프로그램과 다양한 형태의 다중처리기 시스템에 효율적으로 적용할 수 있는 범용적 스케쥴링 알고리즘을 개발하고자 하였다.
이를 위해, 먼저

병렬처리 가능한 응용 프로그램들을 다중처리기 상에서 신속히 처리하기 위한 여러가지 다중처리기 스케쥴링 기법들이 제안되어 왔으나, 이 방법들 대부분은 특정 시스템의 하드웨어 특성에 맞게 설계되어 있기 때문에 매우 한정적이고 제한적으로 밖에는 사용될 수 없다. 본 연구에서는 이러한 문제점을 해결하는 하나의 방법으로 Polynomial-time에 최적해에 근접할 수 있으면서 여러 종류의 응용 프로그램과 다양한 형태의 다중처리기 시스템에 효율적으로 적용할 수 있는 범용적 스케쥴링 알고리즘을 개발하고자 하였다.
이를 위해, 먼저 다중처리기 스케쥴링을 위한 그래프 모델을 이용하여 병렬 계산 수조와 다중처리기 시스템을 각각 계산 그래프와 다중처리기 구조 그래프로 표현한 다음 선형 군집화와 연속 정제 알고리즘을 적용하여 주어진 병렬 계산 구조에 가장 적합한 다중처리기 구조를 나타내는 가상 구조 그래프를 생성하였다. 여기서 선형 군집화란 병렬 계산 구조를 구성하는 계산 단위들 중에서 서로 종속적인 계산 단위들은 하나의 선형 군집에 포함시켜 병렬성을 상실하지 않고서 통신 오버헤드를 줄일 수 있으며 서로 독집적인 계산 단위들은 서로 다른 군집에 포함시킴으로써 내재된 병렬성을 극대화 할 수 있는 기법으로 다중처리기 스케쥴링시 상충하는 두개의 목표를 적절히 조절할 수 있다. 그 다음 가상 구조 그래프에서 여러가지 형태의 다중처리기 시스템으로의 최적 대응을 위해 본 연구에서는 여러가지 휴리스틱 알고리즘에 의존하여 실용적이고 일반적으로 응용 가능한 Polynimial-time 스케쥴링 알고리즘을 개발하였다. 또한 본 연구에서는 동종 및 이종 시스템으로의 대응을 위해 새로운 코스트 함수를 제안하였다. 다양한 형태의 동종 다중처리기 시스템으로의 최적 대응을 위해 Weak Homomorphism과 Acceptable Mapping 대응 전략을 이용한 대응 알고리즘을 제안하였다. 제안된 대응 알고리즘은 빠른 시간내에 최적에 근접하기 위한 Initial 대응 단계와 국지해를 annealing 통해 좀 더 가까이 최적해에 접근하기 위한 Improvement 단계로 구성되어 있다. 마지막으로 이종 다중처리기 시스템으로의 대응을 위해 Dotminant Service Tree 개념을 도입하였으며 노드 정보를 이용하여 서로 다른 계산 능력을 가진 처리기들을 효율적으로 이용할 수 있도록 하였다.

Abstract ▼

We propose a general-purpose multiprpcessor scheduling technique which is broadly and effectively applicable to scheduling of parallel applications upon various multiprocessor systems. The fundamental idea of our research is that multiprocessor scheduling can be regarded as a mapping between graphs.

We propose a general-purpose multiprpcessor scheduling technique which is broadly and effectively applicable to scheduling of parallel applications upon various multiprocessor systems. The fundamental idea of our research is that multiprocessor scheduling can be regarded as a mapping between graphs. We define the medel for computation graphs and architecture graphs. Based on the models, we propose new scheduling techniques based on linear clusters. Linear clustering is an effectual heuristic to compromise between two conflicting goals of multiprocessor scheduling:
minimization of interprocessor communication and maximization of potential parallelism. A computation graph is transformed into a virtual architecture graph by linear clustering. The virtual architecture graph in fact represents an optimal multiprocessor system for the computation graph and can be constructured independently of the target multiprocessor system. We propose a more meaningful cost function to evaluate the optimality of mapping of a virtual architecture graph onto a phisical architecture graph. For homogeneous mappings, we utilize the homomorphism and acceptable mapping strategy based on resonable heuristic mechanism. The proposed mapping procedure is composed of two phases: the initial mapping phase & the improvement phase. The former is used for reaching to a suboptimal solution as fast fast as possible. The latter attempts to improve the quality of sub-optimal solution by pairwise exchanges. For heterogeneous mappings, we introduce Dorminant Service Tree which provides a limited amount of global information on resources in a heterogeneous multiprocessor and discuss various issues related to its generation.
Finally, we propose and justify heuristic algorithms for heterogeneous mappings.

목차 Contents

• 1장. 서론...9
• 2장. 다중처리기 스케쥴링 문제...16
• 1절. 스케쥴링 환경...16
• 2절. 문제 기술...17
• 3장. 다중처리기 스케쥴링을 위한 그래프 모델...19
• 1절. 계산 그래프 모델...19
• 2절. 다중처리기 구조 그래프 모델...20
• 4장. 다중처리기 스케쥴링의 복잡도...22
• 5장. 접근 방법...26
• 1절. 기존의 접근방법...26
• 2절. 선형 군집화 기법...27
• 3절. 최적 군집화 할 수 있는 계산 그래프 종류...46
• 6장. 동종 대응...57
• 1절. 정의...57
• 2절. 코스트 함수...59
• 3절. 대응 순서...61
• 4절. 대응 절차...63
• 5절. 시뮬레이션...70
• 7장. 이종 대응...77
• 1절. 자원의 특성...77
• 2절. Dorminant Service Tree...79
• 3절. 이종 대응에 관한 고찰...81
• 4절. 이종 대응시 고려사항...84
• 5절. 이종 대응 알고리즘...90
• 8장. 결론...103
• 참고 문헌...106