Алгоритм и устройство планирования расписания загрузки процессоров в мультипроцессорных системах

Цель исследования заключается в разработке алгоритма и соответствующего устройства планирования расписания загрузки процессоров,  обеспечивающего  повышение производительности  мультипроцессорных систем и снижение общей величины коммуникационной задержки.

Методы. Статья посвящена мультипроцессорным системам. Затрагивается вопрос составления плана загрузки процессоров в них. Предполагается применение так называемых систем реального времени, когда реакция на внештатную ситуацию должна быть «мгновенной». Например, это может быть отказ системы слежения в кабине пилота самолета, либо сбой датчика прицеливания, либо неполадки какого-либо характера на финансовых рыках страны (мира, континента) и т.п. Существующие методы реализации данной задачи используют, как правило, программные подходы, приводящие к длительному времени решения, вследствие чего снижается коэффициент готовности системы и ее производительность. Они не позволяют получить необходимую производительность  и быстродействие.  Поэтому в статье предложен алгоритм планирования расписания загрузки процессоров в мультипроцессорных системах. Отличительной  особенностью работы является направленность на аппаратную реализацию. При этом применяются специально введенные в предложенном алгоритме матрицы времени, порядка и очередности.

В работе предлагается структурная и функциональная схема специализированного устройства планирования загрузки процессоров мультипроцессорной системы. Данное устройство возможно применять как специализированный дополнительный акселератор, который подключается к параллельному порту вычислительной машины специализированной мультипроцессорной системы. В данном случае разработанный акселератор  выполняет  все функции  вычислений  разработанного  алгоритма.  Это позволит  снизить нагрузку на всю вычислительную систему и уменьшить этим суммарную нагрузку, повышая производительность. Так же предложена структурная и функциональная схемема устройства планирования расписания загрузки.  С его помощью  возможно построить  зависимости  изменения соответствующей временной и аппаратной сложности.

Результаты.  Анализируя зависимости  изменения аппаратной  сложности  устройства  от количества процессоров,  можно сделать следующие  выводы.  Время работы устройства  имеет экспоненциальную зависимость при росте количества процессоров. Так как имееет место экспоненциальный рост времени числа вариантов загрузки процессоров, то можно сделать вывод о преимуществе аппаратной реализации алгоритма планирования.

Заключение.  Представленный  алгоритм  и устройство  планирования  загрузки  процессоров  позволяет сделать вывод о потенциальной  возможности  повышения скорости составления  плана загрузки.  Это помогает  уменьшить  суммарное  значение  коммуникационной  задержки  и  одновременного  увеличения производительности мультипроцессорных систем.

1. Гергель В.П. Теория и практика параллельных вычислений. М.: Бином, 2007.

2. Воеводин В.В. Вычислительная математика и структура алгоритмов. М.: МГУ, 2006.

3. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ– Петербург, 2002. 608 с.

4. Богданов А.В., Станкова Е.Н., Мареев В.В., Корхов В.В. Архитектуры и топологии многопроцессорных вычислительных систем. 2-е изд., М., 2016. 135 с.

5. Новиков Ю.В., Скоробогатов П.К. Основы микропроцессорной техники. М.: Бином, 2009. 357 с.

6. Yu-Kwоng Kwоk аnd Lар-Sun Сhеung. А nеw fuzzy-dесisiоn bаsеd lоаd bаlаnсing systеm fоr distributеd оbjесt соmрuting // Jоurnаl оf Раrаllеl аnd Distributеd Соmрuting. 2004. № 64. Р. 238-253.

7. Zhаng L., Wоng T.N. Sоlving intеgrаtеd рrосеss рlаnning аnd sсhеduling рrоblеm with соnstruсtivе mеtа-hеuristiсs. Inf. Sсi. 2016, 340–341, 1–16.

8. Zhаng S., Wоng T.N. Intеgrаtеd рrосеss рlаnning аnd sсhеduling: Аn еnhаnсеd аnt соlоny орtimizаtiоn hеuristiс with раrаmеtеr tuning // J. Intеll. Mаnuf. 2014. № 29. С. 1–17.

9. Борзов Д.Б., Ткачев П.Ю. Метод распараллеливания циклов со счетчиком // Известия вузов. Приборостроение. 2015. Т. 58. №2. С. 104–108.

10. Математическая модель выявления независимых параллельных участков последовательных программ / Д.Б. Борзов, С.А. Дюбрюкс, В.С. Титов, С.В. Прилуцкий // Нейрокомпьютеры: разработка, применение. 2009. №12. С. 37-41.

11. Борзов Д.Б., Борисенко Ю.В., Сизов А.С. Метод и аппаратно-ориентированный алгоритм переразмещения подпрограмм в мультикомпьютерах при отказе процессоров и связей между ними // Телекоммуникации. 2013. №11. С. 45-48.

12. Таненбаум Э. Архитектура компьютеров. СПб.: Питер, 2007. 848 с.

13. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. СПб.: Питер, 2006. 668 с.

14. Гусева А.И. Вычислительные системы, сети и телекоммуникации. М.: Academia, 2016. 640 с.

15. Андон Ф. И., Кукса А. И., Поляченко Б. Е. Об оптимальном планировании процесса обработки на ЭВМ взаимосвязанных задач // Кибернетика. 1980. Я. 3. С. 51–53.

16. Blаzеwiсz J., Есkеr K., Реsсh Е., Sсhm idt G., Wеglаrz J. Hаndbооk оn Sсhеduling: Frоm Thеоry tо Аррliсаtiоns. Sеriеs: Intеrnаtiоnаl Hаndbооks оn Infоrmаtiоn Systеms, Sрringеr. Bеrlin, Gеrmаny, 2007, 647 р.

17. Борзов Д.Б., Масюков И.И. Планирование загрузки процессоров в мультипроцессорных системах критического назначения // Известия Юго-Западного государственного университета. 2018. Т. 22. №6 (81). С. 168-175. https://doi.org/10.21869/2223-1560-2018-22-6-168-175.

18. Борзов Д.Б., Басов Р.Г. Алгоритм планирования загрузки процессоров в мультипроцессорных системах // Машиностроение и техносфера XXI века: сборник трудов XXV Международной научно-технической конференции. Донецк, 2018. T.1. С. 37-39.

19. Кулачев А.П. Методы и средства анализа данных в среде Windоws. STАDIА 6.0. М.: Информатика и компьютеры, 2006. 270 с.

20. Лобанов В.И. Азбука разработчика цифровых устройств. М.: Горячая линия - Телеком, 2001. 192 с.