Access Restriction

Author Lu, Yung-Feng ♦ Kuo, Chin-Fu
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Deadline assignment ♦ Parallelization option ♦ Parallelization overhead ♦ Multiprocessor systems ♦ Task assignment
Abstract The purpose of this paper is to study the task scheduling problem of task sets on multiprocessor systems. In the task sets there are parallel tasks and sequential tasks. Parallel tasks can not meet their deadlines if they are executed by one unique thread. However, a parallel task has several parallelization options. A good parallelization level for a parallel task can make it meet its deadline and result in the addition of extra execution time due to parallelization overhead. We propose the Best-Fit based on Equal Slack (BEES) algorithm for deadline setting and task assignment. To derive a feasible task assignment, we must select a proper parallelization level from the available parallelization options for each parallel task. Then each parallel task will be split into several subtasks. Finally, sequential tasks and generated subtasks for parallel tasks are assigned to processors. A series of experiments were conducted to evaluate the proposed algorithm. From the experimental results, we can observe that the proposed algorithm had better performance the compared algorithms. The experimental results demonstrate that the performance of the algorithms using the Equal Slack strategy is better than that using the Equal Flexibility strategy.
Description Affiliation: National University of Kaohsiung, Kaohsiung, Taiwan, R.O.C. (Kuo, Chin-Fu) || National Taichung University of Science and Technology, Taichung, Taiwan, R.O.C. (Lu, Yung-Feng)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2013-06-01
Publisher Place New York
Journal ACM SIGAPP Applied Computing Review (SIAP)
Volume Number 16
Issue Number 4
Page Count 11
Starting Page 14
Ending Page 24

Open content in new tab

   Open content in new tab
Source: ACM Digital Library