Paper Info
Title
Consideration of Task’s Deadline for Scheduling Method with Used Processors Limitation
Abstract
Task scheduling is one of the distinguishing features of parallel programming versus sequential one. Scheduling technique is essential to high performance computing. Scheduling to the processors is crucial for optimizing performance. The objective of scheduling is to minimize the overall completion time or schedule the length of the parallel program. For example, in CP/MISF, when there are available tasks and idle processors, these tasks are allocated to the idle processors even if this allocation shortens processing time a little. On the other hand, this allocation decreases processors operating ratio unfortunately. For improvement of processors operating ratio, there is the limitation method of used processors, which we have proposed. In this method, we calculate a limitation from the size of task, the critical path, the earliest starting time, and the latest completion time. Available processors are limited to the limitation. As a result, processors operating ratio has been improved with limiting the number of processors which can be used. On the other hand, processing time increases a little. Its reason is that some of tasks have not been allocated even if they reach the deadline. The deadline of each task is defined as the latest starting time. In this paper, we propose new method that achieves shorter processing time than the original limitation method. This method always allocated tasks at once even if the number of used processors is equal to or more than the limitation when they reach the deadline. By this method, the improvement of processors operating ratio is possible without the increase in processing time. For example, we achieve processors operating ratio about 2 times more for random generated sets of tasks. It indicates that our method brings the significant improvement of processors operating ratio for a multiprocessor system.
Year
DOI
Venue
2001
10.1007/978-1-4419-8530-9_39
ADVANCED COMPUTER SYSTEMS, PROCEEDINGS
Keywords
Field
DocType
task scheduling,operating ratio,processing time
Supercomputer,Idle,Scheduling (computing),Parallel computing,Multiprocessing,Priority inversion,Critical path method,Earliest deadline first scheduling,Dynamic priority scheduling,Mathematics
Conference
Volume
Citations 
PageRank 
664
0
0.34
References 
Authors
2
2
Name
Order
Citations
PageRank
Koichi Kashiwagi1151.11
Shin-ya Kobayashi2388.60