N - 큐브 다중프로세서 시스템에서 태스크 할당 기법 = Task Allocation in an N - Cube Multiprocessor System

국문 초록 (Abstract)

하이퍼큐브 다중프로세서는 그들의 상호연결특징에 의하여 이상적인 병렬구조로 알려지고 있다. 하이퍼큐브에서 하나의 테스크를 수행하기위해서는 다중프로세서들 중에서 한 서브큐브에 테스크를 할당해야하는데, 이러한 할당문제는 시스템성능에 중요한 영향을 미치고 있다. 본 논문에서는 테스크를 할당하기위하여 하나의 서브큐브를 탐색하는 알고리즘을 제시하고자 한다. 전체 하이퍼큐브가 어느 테스크에게도 할당되지않은 자유로운 상태라면, 어떤 크기의 서브큐브라도 쉽게 탐색할 수 있지만, 일부의 프로세서가 어느 테스크에 할당이 되어있으면 이러한 문제는 NP-Complete이다. 제시하고자하는 알고리즘의 기본방향은 일단 하이퍼큐브를 2차원의 격자구조로 변환하여 서브큐브를 이루는 프로세서들을 결정론적으로 탐색하는 것이다. 이 알고리즘이 지금까지 알려진 방법들보다 향상된 서브큐브 인지능력이 있음을 보였다.

다국어 초록 (Multilingual Abstract)

The n-dimensional hypercube multiprocessor is considered as ideal parallel architectures for their powerful interconnection features. A task arriving at a hypercube must be assigned to a subcube in the multiprocessor for execution. Efficient allocation of processors in a hypercube is a key to its performance and utilization. The purpose of this paper is to study how to find a free subcube to allocate an incoming task. When the entire hypercube is free, subcubes of arbitrary dimension can be imbedded in it. But if some processors have been assigned to other tasks, then the general mapping problem is NP-complete. The idea of the proposed algorithm is to map a hypercube to a two-dimensional grid structure and then deterministically find a set of free processors which form a subcube. We show that the proposed algorithm has enhanced subcube recognition capability than any existing algorithms.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. Introduction
• 2. Theoratical Characterizations
• 3. Mapping a Hypercube To a Grid
• 4. The Algorithm
• 5. Comparison
• 6. Conclusions
• References
• 저자소개