Publication: Heuristic Algorithms of Task Timing Groups Compaction for Parallel Execution on Programmable Devices
Дата
2020
Авторы
Journal Title
Journal ISSN
Volume Title
Издатель
Аннотация
© 2020 IEEE.time balancing heuristic algorithms are proposed to reduce operating time the set of devices. There is a variant of the tasks distribution on devices, subject to resource constraints without considering the task execution time. The first algorithm implements a sequential procedure of elements permutations of a global ordered task execution times sequence with inversely ordered local sequences for individual devices. The second algorithm uses a matrix of "time bonuses" of each devices pair. The "time bonus" determines a reduction of the time occupied by a devices pair due to the tasks permutations. Further, complied all possible chains of descending ordered device pairs and selected chain with the maximum value of elements sum. The third algorithm assumes the compilation of a weighted graph on the matrix of "time bonuses", bringing it to a bipartite graph by determining and breaking odd cycles and finding the maximum matching of bipartite graph.
Описание
Ключевые слова
Цитирование
Strelets, A. I. Heuristic Algorithms of Task Timing Groups Compaction for Parallel Execution on Programmable Devices / Strelets, A.I., Ivannikov, V.S., Yokhin, M.N. // Proceedings of the 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, EIConRus 2020. - 2020. - P. 180-184. - 10.1109/EIConRus49466.2020.9038962