ДОСЛІДЖЕННЯ СПОСОБУ ПЛАНУВАННЯ ОБЧИСЛЕНЬ НА ОСНОВІ АЛГОРИТМУ БУЛЬБАШКОВОГО РОЗПОДІЛУ В РІЗНИХ ТОПОЛОГІЯХ
COMPARISON OF PLANNING RESULTS USING BUBBLE SCHEDULING AND ALLOCATION (BSA) ALGORITHM FOR DIFFERENT TOPOLOGIES
Сторінки: 89-96. Номер: №2, 2021 (295) 
Автори:
П.Г. РЕГІДА, І.А. КОМІСАРОВ
Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського
P.H. REHIDA, I.A. KOMISAROV
National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”
DOI: https://www.doi.org/10.31891/2307-5732-2021-295-2-89-96
Рецензія/Peer review : 06.04.2021 р.
Надрукована/Printed : 02.06.2021 р.
Анотація мовою оригіналу
У цій роботі досліджено алгоритм бульбашкового планування та розподілення для різних типів топологій: решітки, гіперкубу, топології де Бруйна, розширеної топології де Бруйна на основі надлишкового коду. Проаналізовано статичні алгоритми планування, результати сформовані у вигляді порівняльної таблиці за критеріями складності, необхідності знаходження критичного шляху, наявності таблиці маршрутизації та ефективності. Дослідження способу планування обчислень проведено на основі задачі знаходження коренів систем лінійних та нелінійних рівнянь за допомогою методів Крамера та Ньютона. Для даної задачі синтезовано відповідні графи ярусно-паралельної форми. Проведено експериментальні дослідження занурення отриманих графів в синтезовані топології за допомогою способу бульбашкового розподілу, представлено результати планування для вказаних топологій.
Ключові слова: планувальник BSA, система рівнянь, топологія де Бруйна.
Розширена анотація англійською мовою
In this article, the bubble scheduling and allocation algorithm is considered for different types of topologies: grid, hypercube, de Bruijn topology, extended de Bruijn topology based on ternary code. Static planning algorithms are analyzed; the results are presented in the form of a comparative table on the criteria of complexity, the need to find a critical path, the presence of a table of routing and efficiency. The study of the method of planning calculations is carried out based on the problem of finding the roots of systems of linear and nonlinear equations using Cramer’s and Newton’s methods. The corresponding graphs of tier-parallel form are synthesized for these methods.
The principles of synthesis for 4 types of topologies are shown. The synthesis of the grid, hypercube, and de Bruijn graph is considered in the classical form. The synthesis of the extended de Bruijn topology is a synthesis of de Bruijn topology [1, 2] using a ternary code. That is, with the same number of processors, the number of connections increases.
Experimental studies of the scheduling of the obtained graphs in the synthesized topologies using the method of bubble scheduling and allocation are conducted; the results of scheduling are presented for these topologies.
The best results were shown by extended de Bruijn topology based on ternary code due to the increased degree of units, which is especially noticeable for Newton’s method where there are much more data transfers than in Cramer’s method. The topology of a hypercube and de Bruijn topology demonstrated just about same results but hypercube topology did a little better. In addition to this, having a smaller diameter and cost, the hypercube is the most optimal topology and still used today. However, when constructing fail-safe topological organizations, it is better to use topologies based on ternary code, such as the topology based on the extended de Bruijn graph.
Keywords: bubble scheduling, systems of equations, de Bruijn topology.
References
- Loutskii, A. Volokyta, P. Rehida, O. Honcharenko, B. Ivanishchev and A. Kaplunov, “Increasing the fault tolerance of distributed systems for the Hyper de Bruijn topology with excess code,” 2019 IEEE International Conference on Advanced Trends in Information Theory (ATIT), Kyiv, Ukraine, 2019, pp. 1–6.
- Loutskii, H., Volokyta, A., Rehida, P., Goncharenko, O. (2019). Using excess code to design fault-tolerant topologies. Technical sciences and technologies, 1 (15), 134–144.
- Bogdanov A. Arhitektury i topologii mnogoprocessornykh vychislitel’nykh sistem / A. Bogdanov, V. Korkhov, V. Mareev, E. Stankova // Mnogoprocessornye komp’yuternye sistemy. – 2004. – S. 25-26.
- Kwok Y., Ahmad I. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors. Static scheduling algorithms. 1998. P. 11–14, 55–65.
- Kwok Y., Ahmad I. Bubble Scheduling: A Quasi Dynamic Algorithm for Static Allocation of Tasks to Parallel Architectures. Computer Systems. 1995. P. 36–42.
- Metod Kramera [Elektronnij resurs]. – 2016 – Rezhim dostupu : http://cyclowiki.org/wiki/Metod_Kramera
- Shokhin K. Metod N’yutona dlya sistem nelinejnykh uravnenij [Elektronnij resurs] / Shokhin K., Lebedev A. – 2018. – Rezhim dostupu : https://algowiki-project.org/ru/Metod_N’yutona_dlya_sistem_nelinejnykh_uravnenij
