Title :
A heuristic scheduling algorithm of imprecise multiprocessor system with 0/1 constraint
Author :
Yun, Kyongok ; Song, Kihyun ; Choi, Kyunghee ; Jung, Gihyun ; Park, Seungkyu ; Manpyo Hong ; Choi, Dugkyoo
Abstract :
The scheduling problem to satisfy both 0/1 constraint and timing constraints with minimizing the total error is NP-complete when the optional parts have arbitrary processing times. In this paper, we present a heuristic scheduling algorithm of imprecise systems with 0/1 constraint which consist of the communicating tasks running on several processors. The algorithm is based on the program graph which is similar to the one presented in by Natale and Stankovic (1994). To check the schedulability, we apply the Lawler and Moore´s theorem. An intensive simulation is done to analyze the performance of suggested algorithm. The results of simulation show that the longest processing first selection strategy outperforms the random or minimal laxity policies
Keywords :
computational complexity; heuristic programming; multiprocessing systems; processor scheduling; real-time systems; 0/1 constraint; NP-complete; communicating tasks; heuristic scheduling algorithm; imprecise multiprocessor system; longest processing first selection strategy; minimal laxity policies; random laxity policies; timing constraints; Algorithm design and analysis; Analytical models; Image processing; Multiprocessing systems; Multitasking; Performance analysis; Processor scheduling; Scheduling algorithm; Time factors; Timing;
Conference_Titel :
Real-Time Computing Systems and Applications, 1996. Proceedings., Third International Workshop on
Conference_Location :
Seoul
Print_ISBN :
0-8186-7626-4
DOI :
10.1109/RTCSA.1996.554991
