{"id":7027,"date":"2021-06-09T10:29:47","date_gmt":"2021-06-09T07:29:47","guid":{"rendered":"http:\/\/journals.khnu.km.ua\/vestnik\/?p=7027"},"modified":"2021-08-04T14:00:15","modified_gmt":"2021-08-04T11:00:15","slug":"%d0%b4%d0%be%d1%81%d0%bb%d1%96%d0%b4%d0%b6%d0%b5%d0%bd%d0%bd%d1%8f-%d1%81%d0%bf%d0%be%d1%81%d0%be%d0%b1%d1%83-%d0%bf%d0%bb%d0%b0%d0%bd%d1%83%d0%b2%d0%b0%d0%bd%d0%bd%d1%8f-%d0%be%d0%b1%d1%87%d0%b8","status":"publish","type":"post","link":"https:\/\/journals.khnu.km.ua\/vestnik\/?p=7027","title":{"rendered":"\u0414\u043e\u0441\u043b\u0456\u0434\u0436\u0435\u043d\u043d\u044f \u0441\u043f\u043e\u0441\u043e\u0431\u0443 \u043f\u043b\u0430\u043d\u0443\u0432\u0430\u043d\u043d\u044f \u043e\u0431\u0447\u0438\u0441\u043b\u0435\u043d\u044c \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0456 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u0431\u0443\u043b\u044c\u0431\u0430\u0448\u043a\u043e\u0432\u043e\u0433\u043e \u0440\u043e\u0437\u043f\u043e\u0434\u0456\u043b\u0443 \u0432 \u0440\u0456\u0437\u043d\u0438\u0445 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0456\u044f\u0445"},"content":{"rendered":"

<\/p>\n

\u0414\u041e\u0421\u041b\u0406\u0414\u0416\u0415\u041d\u041d\u042f \u0421\u041f\u041e\u0421\u041e\u0411\u0423 \u041f\u041b\u0410\u041d\u0423\u0412\u0410\u041d\u041d\u042f \u041e\u0411\u0427\u0418\u0421\u041b\u0415\u041d\u042c \u041d\u0410 \u041e\u0421\u041d\u041e\u0412\u0406 \u0410\u041b\u0413\u041e\u0420\u0418\u0422\u041c\u0423 \u0411\u0423\u041b\u042c\u0411\u0410\u0428\u041a\u041e\u0412\u041e\u0413\u041e \u0420\u041e\u0417\u041f\u041e\u0414\u0406\u041b\u0423 \u0412 \u0420\u0406\u0417\u041d\u0418\u0425 \u0422\u041e\u041f\u041e\u041b\u041e\u0413\u0406\u042f\u0425<\/p>\n

COMPARISON OF PLANNING RESULTS USING BUBBLE SCHEDULING AND ALLOCATION (BSA) ALGORITHM FOR DIFFERENT TOPOLOGIES<\/p>\n

\u0421\u0442\u043e\u0440\u0456\u043d\u043a\u0438: 89-96. \u041d\u043e\u043c\u0435\u0440: \u21162, 2021 (295)<\/strong> \"\"<\/a>
\n\u0410\u0432\u0442\u043e\u0440\u0438:<\/strong>
\n\u041f.\u0413. \u0420\u0415\u0413\u0406\u0414\u0410, \u0406.\u0410. \u041a\u041e\u041c\u0406\u0421\u0410\u0420\u041e\u0412
\n\u041d\u0430\u0446\u0456\u043e\u043d\u0430\u043b\u044c\u043d\u0438\u0439 \u0442\u0435\u0445\u043d\u0456\u0447\u043d\u0438\u0439 \u0443\u043d\u0456\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442 \u0423\u043a\u0440\u0430\u0457\u043d\u0438 \u201c\u041a\u0438\u0457\u0432\u0441\u044c\u043a\u0438\u0439 \u043f\u043e\u043b\u0456\u0442\u0435\u0445\u043d\u0456\u0447\u043d\u0438\u0439 \u0456\u043d\u0441\u0442\u0438\u0442\u0443\u0442 \u0456\u043c\u0435\u043d\u0456 \u0406\u0433\u043e\u0440\u044f \u0421\u0456\u043a\u043e\u0440\u0441\u044c\u043a\u043e\u0433\u043e
\nP.H. REHIDA, I.A. KOMISAROV
\nNational Technical University of Ukraine \u201cIgor Sikorsky Kyiv Polytechnic Institute\u201d
\nDOI:<\/strong> https:\/\/www.doi.org\/10.31891\/2307-5732-2021-295-2-89-96<\/a>
\n\u0420\u0435\u0446\u0435\u043d\u0437\u0456\u044f\/Peer review :<\/strong> 06.04.2021 \u0440.
\n\u041d\u0430\u0434\u0440\u0443\u043a\u043e\u0432\u0430\u043d\u0430\/Printed :<\/strong> 02.06.2021 \u0440.<\/p>\n

\u0410\u043d\u043e\u0442\u0430\u0446\u0456\u044f \u043c\u043e\u0432\u043e\u044e \u043e\u0440\u0438\u0433\u0456\u043d\u0430\u043b\u0443<\/strong><\/p>\n

\u0423 \u0446\u0456\u0439 \u0440\u043e\u0431\u043e\u0442\u0456 \u0434\u043e\u0441\u043b\u0456\u0434\u0436\u0435\u043d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0431\u0443\u043b\u044c\u0431\u0430\u0448\u043a\u043e\u0432\u043e\u0433\u043e \u043f\u043b\u0430\u043d\u0443\u0432\u0430\u043d\u043d\u044f \u0442\u0430 \u0440\u043e\u0437\u043f\u043e\u0434\u0456\u043b\u0435\u043d\u043d\u044f \u0434\u043b\u044f \u0440\u0456\u0437\u043d\u0438\u0445 \u0442\u0438\u043f\u0456\u0432 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0456\u0439: \u0440\u0435\u0448\u0456\u0442\u043a\u0438, \u0433\u0456\u043f\u0435\u0440\u043a\u0443\u0431\u0443, \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0456\u0457 \u0434\u0435 \u0411\u0440\u0443\u0439\u043d\u0430, \u0440\u043e\u0437\u0448\u0438\u0440\u0435\u043d\u043e\u0457 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0456\u0457 \u0434\u0435 \u0411\u0440\u0443\u0439\u043d\u0430 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0456 \u043d\u0430\u0434\u043b\u0438\u0448\u043a\u043e\u0432\u043e\u0433\u043e \u043a\u043e\u0434\u0443. \u041f\u0440\u043e\u0430\u043d\u0430\u043b\u0456\u0437\u043e\u0432\u0430\u043d\u043e \u0441\u0442\u0430\u0442\u0438\u0447\u043d\u0456 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438 \u043f\u043b\u0430\u043d\u0443\u0432\u0430\u043d\u043d\u044f, \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0438 \u0441\u0444\u043e\u0440\u043c\u043e\u0432\u0430\u043d\u0456 \u0443 \u0432\u0438\u0433\u043b\u044f\u0434\u0456 \u043f\u043e\u0440\u0456\u0432\u043d\u044f\u043b\u044c\u043d\u043e\u0457 \u0442\u0430\u0431\u043b\u0438\u0446\u0456 \u0437\u0430 \u043a\u0440\u0438\u0442\u0435\u0440\u0456\u044f\u043c\u0438 \u0441\u043a\u043b\u0430\u0434\u043d\u043e\u0441\u0442\u0456, \u043d\u0435\u043e\u0431\u0445\u0456\u0434\u043d\u043e\u0441\u0442\u0456 \u0437\u043d\u0430\u0445\u043e\u0434\u0436\u0435\u043d\u043d\u044f \u043a\u0440\u0438\u0442\u0438\u0447\u043d\u043e\u0433\u043e \u0448\u043b\u044f\u0445\u0443, \u043d\u0430\u044f\u0432\u043d\u043e\u0441\u0442\u0456 \u0442\u0430\u0431\u043b\u0438\u0446\u0456 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0438\u0437\u0430\u0446\u0456\u0457 \u0442\u0430 \u0435\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0456. \u0414\u043e\u0441\u043b\u0456\u0434\u0436\u0435\u043d\u043d\u044f \u0441\u043f\u043e\u0441\u043e\u0431\u0443 \u043f\u043b\u0430\u043d\u0443\u0432\u0430\u043d\u043d\u044f \u043e\u0431\u0447\u0438\u0441\u043b\u0435\u043d\u044c \u043f\u0440\u043e\u0432\u0435\u0434\u0435\u043d\u043e \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0456 \u0437\u0430\u0434\u0430\u0447\u0456 \u0437\u043d\u0430\u0445\u043e\u0434\u0436\u0435\u043d\u043d\u044f \u043a\u043e\u0440\u0435\u043d\u0456\u0432 \u0441\u0438\u0441\u0442\u0435\u043c \u043b\u0456\u043d\u0456\u0439\u043d\u0438\u0445 \u0442\u0430 \u043d\u0435\u043b\u0456\u043d\u0456\u0439\u043d\u0438\u0445 \u0440\u0456\u0432\u043d\u044f\u043d\u044c \u0437\u0430 \u0434\u043e\u043f\u043e\u043c\u043e\u0433\u043e\u044e \u043c\u0435\u0442\u043e\u0434\u0456\u0432 \u041a\u0440\u0430\u043c\u0435\u0440\u0430 \u0442\u0430 \u041d\u044c\u044e\u0442\u043e\u043d\u0430. \u0414\u043b\u044f \u0434\u0430\u043d\u043e\u0457 \u0437\u0430\u0434\u0430\u0447\u0456 \u0441\u0438\u043d\u0442\u0435\u0437\u043e\u0432\u0430\u043d\u043e \u0432\u0456\u0434\u043f\u043e\u0432\u0456\u0434\u043d\u0456 \u0433\u0440\u0430\u0444\u0438 \u044f\u0440\u0443\u0441\u043d\u043e-\u043f\u0430\u0440\u0430\u043b\u0435\u043b\u044c\u043d\u043e\u0457 \u0444\u043e\u0440\u043c\u0438. \u041f\u0440\u043e\u0432\u0435\u0434\u0435\u043d\u043e \u0435\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u0456 \u0434\u043e\u0441\u043b\u0456\u0434\u0436\u0435\u043d\u043d\u044f \u0437\u0430\u043d\u0443\u0440\u0435\u043d\u043d\u044f \u043e\u0442\u0440\u0438\u043c\u0430\u043d\u0438\u0445 \u0433\u0440\u0430\u0444\u0456\u0432 \u0432 \u0441\u0438\u043d\u0442\u0435\u0437\u043e\u0432\u0430\u043d\u0456 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0456\u0457 \u0437\u0430 \u0434\u043e\u043f\u043e\u043c\u043e\u0433\u043e\u044e \u0441\u043f\u043e\u0441\u043e\u0431\u0443 \u0431\u0443\u043b\u044c\u0431\u0430\u0448\u043a\u043e\u0432\u043e\u0433\u043e \u0440\u043e\u0437\u043f\u043e\u0434\u0456\u043b\u0443, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0438 \u043f\u043b\u0430\u043d\u0443\u0432\u0430\u043d\u043d\u044f \u0434\u043b\u044f \u0432\u043a\u0430\u0437\u0430\u043d\u0438\u0445 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0456\u0439.
\n\u041a\u043b\u044e\u0447\u043e\u0432\u0456 \u0441\u043b\u043e\u0432\u0430:<\/strong> \u043f\u043b\u0430\u043d\u0443\u0432\u0430\u043b\u044c\u043d\u0438\u043a BSA, \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0440\u0456\u0432\u043d\u044f\u043d\u044c, \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0456\u044f \u0434\u0435 \u0411\u0440\u0443\u0439\u043d\u0430.<\/p>\n

\u0420\u043e\u0437\u0448\u0438\u0440\u0435\u043d\u0430 \u0430\u043d\u043e\u0442\u0430\u0446\u0456\u044f \u0430\u043d\u0433\u043b\u0456\u0439\u0441\u044c\u043a\u043e\u044e \u043c\u043e\u0432\u043e\u044e<\/strong><\/p>\n

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\u2019s and Newton\u2019s methods. The corresponding graphs of tier-parallel form are synthesized for these methods.
\nThe 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.
\nExperimental 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.
\nThe 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.
\nKeywords:<\/strong> bubble scheduling, systems of equations, de Bruijn topology.<\/p>\n

References<\/strong><\/p>\n

    \n
  1. 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\u20136.<\/li>\n
  2. Loutskii, H., Volokyta, A., Rehida, P., Goncharenko, O. (2019). Using excess code to design fault-tolerant topologies. Technical sciences and technologies, 1 (15), 134\u2013144.<\/li>\n
  3. Bogdanov A. Arhitektury i topologii mnogoprocessornykh vychislitel’nykh sistem \/ A. Bogdanov, V. Korkhov, V. Mareev, E. Stankova \/\/ Mnogoprocessornye komp’yuternye sistemy. \u2013 2004. \u2013 S. 25-26.<\/li>\n
  4. Kwok Y., Ahmad I. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors. Static scheduling algorithms. 1998. P. 11\u201314, 55\u201365.<\/li>\n
  5. Kwok Y., Ahmad I. Bubble Scheduling: A Quasi Dynamic Algorithm for Static Allocation of Tasks to Parallel Architectures. Computer Systems. 1995. P. 36\u201342.<\/li>\n
  6. Metod Kramera [Elektronnij resurs]. \u2013 2016 \u2013 Rezhim dostupu : http:\/\/cyclowiki.org\/wiki\/Metod_Kramera<\/li>\n
  7. Shokhin K. Metod N’yutona dlya sistem nelinejnykh uravnenij [Elektronnij resurs] \/ Shokhin K., Lebedev A. \u2013 2018. \u2013 Rezhim dostupu : https:\/\/algowiki-project.org\/ru\/Metod_N’yutona_dlya_sistem_nelinejnykh_uravnenij<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[46],"tags":[],"_links":{"self":[{"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=\/wp\/v2\/posts\/7027"}],"collection":[{"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=7027"}],"version-history":[{"count":3,"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=\/wp\/v2\/posts\/7027\/revisions"}],"predecessor-version":[{"id":7331,"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=\/wp\/v2\/posts\/7027\/revisions\/7331"}],"wp:attachment":[{"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=7027"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=7027"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/journals.khnu.km.ua\/vestnik\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=7027"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}