서지주요정보
Approximation algorithms for scheduling parallel tasks = 병렬 태스크의 스케쥴링을 위한 근사적 알고리즘
서명 / 저자 Approximation algorithms for scheduling parallel tasks = 병렬 태스크의 스케쥴링을 위한 근사적 알고리즘 / Oh-Heum Kwon.
저자명 Kwon, Oh-Heum ; 권오흠
발행사항 [대전 : 한국과학기술원, 1996].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8006388

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 96012

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

등록번호

9002238

소장위치/청구기호

서울 학위논문 서가

DCS 96012 c. 2

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

A parallel task is one that can be executed by multiple processors. All the processors allotted to a task are required to execute that task in unison and simultaneously. A non-malleable parallel task is one that requires a specific number of processors for a specific units of time, while a malleable task is one that can be executed on any number of processors, with its execution time being a function of the number of processors allotted to it. A malleable task is said to have a linear speedup if the task execution time describes a linear speedup up to some specified maximum degree of parallelism, and is constant thereafter. This thesis deals three different problems, and presents approximation algorithms for solving each of the problems. We first consider the problem of minimizing makespan on hypercube systems. For non-malleable tasks, we propose an algorithm with an approximation factor of 1.875. This is the first algorithm achieving an approximation factor less than 2 by a constant for this problem. For non-malleable tasks with linear speedups, we propose another algorithm with an approximation factor of $\frac{5}{3}$ We also consider on-line scheduling problems, and present some partial results. Second, we consider the parallel tasks which are associated with individual deadlines on a PRAM. The objective is to maximize the sum of the works of the tasks that are completed before their deadlines in the schedule. For non-malleable tasks, we present an algorithm with an approximation factor of 5+ε epsilon for any constant epsilon ε > 0, and, for malleable tasks with linear speedups, present another algorithm with an approximation factor of 4.5. Third, we introduce a new kind of parallel tasks of which the execution times depend on not only the number of processors but also the processors themselves on which the tasks are to be executed. This problem captures such aspects of the real systems as the non-homogeneity of the processors or the data locality between the processors. We present approximation algorithms for solving this problem on the several parallel systems including PRAMs, 1-dimensional meshes, and 2-dimensional meshes.

서지기타정보

서지기타정보
청구기호 {DCS 96012
형태사항 v, 96 p. : 삽도 ; 25 cm
언어 영어
일반주기 저자명의 한글표기 : 권오흠
지도교수의 영문표기 : Kyung-Yong Chwa
지도교수의 한글표기 : 좌경룡
학위논문 학위논문(박사) - 한국과학기술원 : 전산학과,
서지주기 Reference : p. 90-96
주제 Scheduling
Parallel Tasks
Approximation Algorithm
스케쥴링
병렬 태스크
근사적 알고리즘
QR CODE qr code