Optimal scheduling of parallel tasks of tracking problem onto multiprocessors

Author

Piriyakumar, D. Antony Louis ; Murthy, C. Siva Ram

Author_Institution

Dept. of Comput. Sci., Pondicherry Univ., India

Volume

32

Issue

2

fYear

1996

fDate

4/1/1996 12:00:00 AM

Firstpage

722

Lastpage

731

Abstract

The optimal scheduling of the tasks of a multitarget tracking problem onto multiprocessors to minimize the schedule length is considered. The main impediments of the recent A* algorithm for optimal scheduling of the tasks of this problem, the space and time requirements, are reduced using three new techniques, viz. processor isomorphism, duplicated node deletion, and lower bound on completion time. The effectiveness of these techniques is analyzed and demonstrated with the above real-time critical problem.

Keywords

computational complexity; parallel processing; processor scheduling; signal processing; software performance evaluation; target tracking; telecommunication computing; tracking; completion time; duplicated node deletion; effectiveness; multiprocessors; multitarget tracking; optimal scheduling; optimisation; parallel tasks; processor isomorphism; real-time critical problem; schedule length; space requirements; time requirements; tracking; Computer science; Impedance; Job shop scheduling; Multiprocessing systems; Optimal scheduling; Processor scheduling; Read-write memory; Real time systems; Scheduling algorithm; Space technology;

fLanguage

English

Journal_Title

Aerospace and Electronic Systems, IEEE Transactions on

Publisher

ieee

ISSN

0018-9251

Type

jour

DOI

10.1109/7.489515

Filename

489515