Dynamical task scheduling in the heterogeneous system with the real time limitations

Authors

DOI:

https://doi.org/10.20535/SRIT.2308-8893.2016.3.04

Keywords:

schedule, bipartite matching graph, Hungarian algorithm, task scheduler

Abstract

A method of dynamic real time scheduling of tasks in a heterogeneous system is considered. The method consists in a preliminary preparation of the initial information set, taking into account the duration of the scheduling, the complexity of tasks, as well as individual resource characteristics such as performance, memory capacity, availability of downloaded software and initial data. The algorithm of this preparation consists in forming a job time reserve matrix and performing a sequence of transformations of this matrix to the cost matrix taking into account the assignment conflict matrix. After preparation of the initial information set, the planning problem is solved by the Hungarian algorithm of finding the maximum bipartite matching.

Author Biographies

Valery P. Simonenko, Computer Science Department of NTUU "KPI", Kyiv, Ukraine

Simonenko Valery Pavlovich,

Doctor of science, professor, professor, Computer Science Department of NTUU "KPI".

Research interests: computer architecture, parallel computing, operating systems, system programming.

Anatolij M. Sergiyenko, Computer Science Department of NTUU "KPI", Kyiv, Ukraine

Sergiyenko Anatolij Mikhailovich,

Doctor of science, senior scientist, senior scientist, Computer Science Department of NTUU "KPI".

Research interests: computer architecture, computer design automation, programmable logic integrated circuits, specialized computers, digital signal processing.

References

Papadimitriou C.H. Combinatory optimization, algorithm and complexity / C.H. Papadimitriou, K. Steiglitz. — New Jersey: Prentice-Hall. —1982. — 496 p.

Berge C. Theorie des graphes et ses application / C. Berge. — Paris: Dunod. — 1958. — 275 p.

Zyl' S. Operatsionnaja sistema real'nogo vremeni QNX: ot teorii k praktike. — 2-izd. / S. Zyl'. — SPb.: BHV — Peterburg, 2004. — 192 s. ISBN 5-94157-486-H

Zyl' S. QNX Momentics. Osnovy primenenija / S. Zyl'. — SPb.: BHV-Peterburg, 2004. — 256 s.: il. ISBN 5-94157-430-4

Kerten R. Vvedenie v QNX/Neutrino 2 / R. Kerten . — SPb.: Petropolis. — 2001. — 512 S. ISBN 5-94656-025-9.

Oslender D.M. Upravljajuschie programmy dlja mehanicheskih sistem: Ob'ektno-orientirovannoe proektirovanie sistem real'nogo vremeni / D.M. Oslender, Dzh.R. Ridzhli, Dzh.D. Ringenberg. — M.: Binom. Laboratorija znanij. — 2004. — 416 s. ISBN 5-94774-097-4.

Simonenko V.P. Uluchshennyj algoritm naznachenija dlja planirovschikov zadanij v neodnorodnyh raspredelennyh vychislitel'nyh sistemah / V.P. Simonenko, A.M. Sergienko, A.V. Simonenko // Systemni doslidzhennja ta informatsijni tekhnolohiyi. — 2016. — № 2. — S. 20–35.

Kauffman A. Introduction to a la combinatorque en vue des applications / A. Kauffman. — Paris: Dunod, 1968.

Downloads

Published

2016-09-26

Issue

No. 3 (2016)

Section

Decision making and control in economic, technical, ecological and social systems

License

This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles in this journal without asking prior permission from the publisher or the author. This is in accordance with the BOAI definition of open access.