Subdeadline assignment for real-time tasks with multiple parallelization options on multiprocessor systems
Autor: | Chin-Fu Kuo, Yung-Feng Lu, Ya-Ju Yu, Shu-Ping Lu |
---|---|
Rok vydání: | 2017 |
Předmět: |
Optimization problem
Heuristic (computer science) Computer science Distributed computing 0211 other engineering and technologies 021107 urban & regional planning Multiprocessing 02 engineering and technology Parallel computing Task (project management) Instruction set Set (abstract data type) 03 medical and health sciences Automatic parallelization 0302 clinical medicine 030212 general & internal medicine Assignment problem |
Zdroj: | 2017 International Conference on Applied System Innovation (ICASI). |
DOI: | 10.1109/icasi.2017.7988206 |
Popis: | The purpose of this paper is to study the deadline assignment for the segments of tasks on multiprocessor systems. Each task consists of sequential and parallel segments. A parallel segment needing more computation power can be parallelized and executed on more than one processor simultaneously. When a task is only executed on a unique processor, the overall execution time will be more than its deadline and miss its deadline. Therefore, we should try to parallelize the execution of parallel segments into multiple processors. However, for a task a higher parallelization option implies larger parallelization overheads. Parallelization overheads result in that the required total execution time for a task become longer. We propose a mechanism to derive the subdeadline for each segment of a task. First, the deadline assignment problem is modelled as an optimization problem to minimize the total density of all the segments of the tasks in the task set. Then, the problem is transformed to minimize the total density of all the segments of each task. Finally, we propose a method to solve the formulated problem. After the deadlines for the segments of the tasks are computed, we can derive the density for each subtask. The subtasks can be assigned to a proper processor with an assignment heuristic. |
Databáze: | OpenAIRE |
Externí odkaz: |