employee
student
student
VAC 05.17.00 Химическая технология
VAC 05.23.00 Строительство и архитектура
GRNTI 20.53 Технические средства обеспечения информационных процессов
This article describes the placement of parallel programs in multiprocessor systems problem. Concluded the inability of using scheduling software when using critical systems (system monitoring, tracking, targeting, nuclear facilities, etc.) and suggested alternative hardware to solve the problem.
processing, program, failure, critical system, reserve, accommodation
В настоящее время мультипроцессоры являются наиболее распространенным классом вычислительной техники. Они, как правило, являются системами высокого параллелизма и включают в своем составе сотни процессорных модулей, которые обычно имеют матричную топологическую организацию [1]. В случае использования мультипроцессорных систем (МС), особенно в объектах критического назначения (системы слежения, наблюдения, управления, атомные объекты различного назначения и т.п.), требования к производительности, отказоустойчивости и быстродействию возрастают.
В МС могут возникать отказы и сбои внутренних процессорных модулей и/или каналов связи. В этом случае уменьшается внутренняя коммуникационная задержка, производительность и время реакции системы. Одним из вариантов решения данной проблемы может быть внутреннее переразмещение отказавших процессорных модулей и/или каналов связи [2–4]. Работа является продолжением исследований, начатых в [5–6]. Как показал анализ [2–6], в случае отказов в критических МС использование программных средств неприменимо из-за длительного времени решения. В связи с этим целесообразным является применение специализированных аппаратных средств планирования размещения и/или переразмещения.
Предлагается структурная схема мультипроцессорной хост–системы, представленная на рисунке 1. На нем каждый из процессорных ядер системы (ПЯ1, ПЯ2,…, ПЯN) включает в себя устройство управления и арифметико-логическое устройство, ПЗУ, подключаемые к общей шине МС. Предлагаемые специализированные аппаратные средства планирования размещения программ предлагается использовать как периферийные устройства, также подключенные к общей шине, к ним относятся также внешняя память и устройства ввода-вывода.
Рис. 1. Структурная схема мультипроцессорной хост–системы
В случае выполнения задачи размещения предложен метод, методика и алгоритм [3, 4].
Пакет программ в МС представляется графом взаимодействия задач вида:
G=<X,E>, (1)
где – множество вершин графа G,
соответствуют программам, а дуги
– связям между ними и представляют объемы данных
, передаваемыми между задачами, задаваемая матрицей обмена информацией (МОИ)
, где
,
.
Матричный блок МС представляется топологической моделью в виде графа H=<P,V>, где – множество идентификаторов процессорных модулей блока, организованных в матрицу |P|n´n, где
- процессоры;
– множество связей, описываемых матрицей смежности
размером
.
Тогда размещение пакета программ графа G в МС представляется отображением
, (2)
где S – номер очередной перестановки, соответствующей s-му варианту размещения.
Мощность множества всевозможных отображений (2) равна числу всевозможных перестановок задач
в матрице
. Множество длин dij кратчайших маршрутов передачи данных в пределах блока описывается матрицей минимальных расстояний (ММР)
которую можно построить по матрице смежности.
Задача планирования размещения сводится к поиску максимальной коммуникационной задержки при передаче данных между процессорными модулями и
, соответствующей отображению b*ÎY и вычислению показателя
с последующей его минимизацией. В результате
. (3)
Отображение вычисляется как
, (4)
где и
,
а . (5)
Поиск наилучшего варианта размещения по критерию (3) является сложной переборной задачей. Вариантом ее ускорения является применение целенаправленных поисковых перестановок строк и столбцов МОИ с выбором в ней a-го места перестановки элемента по критериям (3, 4).
, (6)
где – одноименные элементы матрицы ММР;
– элемент МОИ, которому соответствует
, найденный в предыдущем шаге перестановок.
Число требуемых перестановок уменьшается, если не учитывать явно нецелесообразные из них, разрешая очередную перестановку по следующим дополнительным критериям [8, 9]:
, (7)
. (8)
Для ускорения поиска разработана методика ускоренного выполнения процедур планирования размещения программ [3, 4]:
1. Составляются две матрицы: обмена информацией (МОИ) и кратчайших маршрутов (ММР) между процессорами и коммуникационной средой процессорного блока.
2. Вычисляются минимум коммуникационной задержки Tinf и коэффициент эффективности исходного размещения задач . При нахождении Tinf веса дуг графа G назначаются на смежные процессорные модули без учета реальной топологии.
3. По порогу эффективности принимается решение о целесообразности инициализации процедуры поиска размещения. Коэффициент эффективности перестановок
определяется как отношение полученной величины задержки (3) к
.
4. Выполняются шаги целенаправленных перестановок столбцов и строк матрицы обмена информацией. Далее находится максимальное значение коммуникационной задержки (2) по предыдущему варианту перестановок программ.
5. Находится минимум (3) из максимумов по всем вариантам перестановок и вычисляется коэффициент эффективности .
6. Если оказывается менее установленного порога эффективности
, шаги поиска прекращаются и найденный вариант матрицы обмена информацией считается соответствующим полученному варианту размещения.
В результате был разработан аппаратно-ориентированный алгоритм ускоренного планирования размещения программ в МС [2].
На основе предложенного метода, методики и алгоритма планирования размещения программ в МС, разработана структурная схема устройства планирования размещения программ, представленная на рисунке 2 [7, 8, 9].
Операцию вычисления максимальной коммуникационной задержки, как одну из наиболее трудоемких, предполагается выполнять в аппаратном ускорителе: акселераторе вычисления показателя коммуникационной задержки (АВПКЗ). В блоке АВПКЗ применены конвейерный и матричный подходы для поэлементного перемножения векторов с одновременным подсчетом максимального произведения. Данные с параллельного порта поступают в блок специализированного мультиплексора (MUX). В зависимости от режима работы MUX загружает одно из ОЗУ данными соответствующей разрядности. Если идет загрузка в ОЗУ2, из 8-и разрядного порта за один цикл приема MUX принимает два 4-х разрядных слова. Если же идет загрузка в ОЗУ1, то MUX принимает два байта 16-ти разрядного слова и после их склеивания помещает целое слово в ОЗУ1. Блок умножения матрично–конвейерный (БУМК) осуществляет перемножение синхронно считанных из ОЗУ1 и ОЗУ2 двух слов и выдает результат в блок нахождения максимума (MAX). Умножение происходит конвейерно за один такт. Блок MAX находит максимум и по сигналу об окончании расчета выдает результат за три цикла вывода в порт контроллера. Устройство управления (УУ) выдает управляющие сигналы, обозначенные на рис. 2 как множество микроопераций (МО), а также значения адресов для ОЗУ1 и ОЗУ2 в режимах загрузки и вычисления.
В случае отказа процессора и/или межпроцессорной связи примем, множество программ описывается графом взаимодействия задач , где
– множество вершин, соответствующих программам,
– множество дуг, отражающих связи программам. Граф F задается матрицей смежности:
, где
. Топология мультипроцессора представляется графом
, где
– процессоры, а множество V – межмодульные связи. Множество –
, где
– основные процессоры,
– резервные процессоры, причем
,
. Множества процессоров P и L задаются матрицами
и
соответственно. Множество
представляется объединением указанных матриц. Размещение задается отображением [5, 6].
, (9)
ставящее в соответствие программам один из процессоров системы.
Тогда задача размещения программ в мультикомпьютере заключается в выборе такого отображения , которое соответствует критерию [10].
, (10)
где максимум в фигурных скобках представляет собой наибольшую частную коммуникационную задержку для заданного отображения β.
В случае отказа отдельного канала связи между процессорами нарушаются маршруты транзитной передачи данных и необходимо найти новые кратчайшие маршруты обхода отказавшего канала. Для этого случая обоснована целесообразность использования известного алгоритма Дейкстры [11].
Для предложенного метода и аппаратно–ориентированного алгоритма отказоустойчивого переразмещения бала предложена соответствующая структурная схема микропроцессорного акселератора, представленная на рис. 3 [12].
На рис. 3 приняты следующие обозначения блоков и узлов: АПРП – акселератор планирования переразмещения подпрограмм; ОП – оперативная память; КПДП – контроллер прямого доступа в память; Ппорт – последовательный порт; Прпорт – параллельный порт; УУ – устройство управления; БППОМ - блока переразмещения отказавших процессорных модулей; БПКМ - блока поиска кратчайшего маршрута; МО – микрооперации; А – адрес.
Рис. 3. Структурная организация акселератора
отказоустойчивого переразмещения
МП работает по принципу, аналогичному описанной структурной схема выше. После замены процессорного модуля резервным либо после нахождения кратчайшего пути обхода найденный вариант передается через параллельный порт обратно в контроллер и далее через последовательный порт обратно в управляющую ЭВМ.
На основе представленной структурной схемы была разработана функциональная организация соответствующего устройства оперативной замены отказавшего процессорного модуля резервным, представленная на рисунке 4 [12].
На рис. 4 приняты следующие обозначения блоков и узлов: 14 – генератор импульсов, Р1 – ОЗУ, – ОЗУ, Q – ОЗУ, регистр 18, первый 19 и второй 20 элемент сравнения, дешифратор 21 выбора, первый 22 и второй 23 счетчик строки, первый 24 и второй 25 счетчик столбца, счетчик 26 номера предназначенный для подсчета номера выбираемого счетчика 22, 23, 24, 25, необходимого для проведения операций с заменой основного процессора резервным, первый 27, второй 28 и третий 29 Элементы ИЛИ.
Предложенное устройство функционирует в соответствии с предложенным алгоритмом отказоустойчивого переразмещения [13,14].
В начальном состоянии в ОЗУ 15 хранится матрица P1 процессорных модулей и матрица L резервных процессоров. В матрице хранятся нулевые коды, свидетельствующие о полной начальной работоспособности мультикомпьютера. В матрице 7 Q также хранятся коды нулей, свидетельствующие о наличие и полной начальной работоспобности резервных процессоров. В регистре 18 хранится код нуля («0…00»), в счетчике 26 содержится код нуля («0…00»), а значит, на выходе дешифратора 21 не появляется единичного импульса. Триггер 36 находится в высокоимпедансном состоянии.
В работе были предложены специализированные устройства ускоренного планирования размещения параллельных программ в МС, обеспечивающих сокращение времени формирования планов размещения программ, минимизирующих коммуникационную задержку МП при наличии отказов внутренних процессорных модулей и/или каналов связи.
1. Voevodin V.V., Voevodin Vl.V. Parallel'nye vychisleniya // BHV- Peterburg. Sankt-Peterburg, 2002. 608 s.
2. Borzov D.B., J.A Azzeh, I.V. Zotov, D.E. Skopin, D. M.Al Hadidi. An Approach to Achieving Increased Fault-Tolerance and Availability of Multiprocessor-Based Computer Systems // Australian Journal of Basic and Applied Sciences. 8(6) April 2014. Pp. 512-522.
3. Borzov D.B., Titov V.S. Parallel'nye vychislitel'nye sistemy (arhitektura, principy razmescheniya zadach): monografiya / Kursk. gos. tehn. un-t. Kursk, 2008. 156 s.
4. Borzov D.B., Titov V.S. Voprosy proektirovaniya i dinamicheskoy rekonfiguracii topologii sistem logicheskogo upravleniya v sistemah vysokoy gotovnosti: monografiya / YuZGU. Kursk, 2015. 278 s.
5. Borzov D.B., Sokolova Yu.V., Minaylov V.V. Pererazmeschenie podprogramm v otkazoustoychivyh mul'tiprocessornyh sistemah / Izvestiya vuzov. Priborostroenie. Sankt-Peterburg. 2013. T56. №6. S. 39-44
6. Borzov D.B., Borisenko Yu.V., Sizov A.S. Metod i apparatno-orientirovannyy algoritm pererazmescheniya podprogramm v mul'tikomp'yuterah pri otkaze processorov i svyazey mezhdu nimi // Telekommunikacii. - Ezhemesyachnyy nauchno-tehnicheskiy, informacionno-analiticheskiy i uchebno-metodicheskiy zhurnal. 2013. №11. S. 45-48.
7. Borzov D.B., Chesnokova E.O. Ustroystvo poiska nizhney ocenki razmescheniya v polnosvyaznyh matrichnyh sistemah pri odnonapravlennoy peredache informacii / Patent RF №2398270, zayavl. 11.02.2009; opubl. 27.08.2010, BI 24, 21 s. 2 il.
8. Borzov D.B., Bobyncev D.O. Ustroystvo poiska nizhney ocenki razmescheniya v sistemah s matrichnoy organizaciey pri napravlennoy peredache informacii / Patent RF №2406135, zayavl. 9.02.2009, opubl. 10.12.2010, BI №34, 12 s, 2 il.
9. Borzov D.B., Chesnokova E.O., Maruhlenko A.L, A-A Mudzhib Mohammed Yah'ya. Ustroystvo poiska nizhney ocenki razmescheniya v polnosvyaznyh matrichnyh sistemah pri dvunapravleno peredachi informacii / Patent RF №2421805, zayavl. 24.11.2008, opubl. 27.06.2011, 17 s, 2 il.
10. Borzov D.B., Zotov I.V., Titov V.S. O suboptimal'nom razmeschenii processov i dannyh v kol'cevyh setyah // Izvestiya vuzov. Priborostroenie. Sankt-Peterburg. 2003. T46, №11. S. 48-54.
11. Morozov K.K., Odinokov V.G., Kureychik V.M. Avtomatizirovannoe proektirovanie konstrukciy radioelektronnoy apparatury: Uchebnoe posobie dlya vuzov. M.: «Radio i svyaz'». 1983. 280 s.
12. Pat. 2447485 Rossiyskaya Federaciya, MPK G06F7/76, G06F17/10 Ustroystvo poiska nizhney ocenki razmescheniya v matrichnyh sistemah pri dvunapravlennoy peredachi informacii / Borzov D.B., Sokolova Yu.V., zayavitel' i patentoobladatel' Federal'noe gosudarstvennoe byudzhetnoe obrazovatel'noe uchrezhdenie vysshego obrazovaniya "Yugo-Zapadnyy gosudarstvennyy universitet" (YuZGU). - №2009134208/08, zayavl. 11.09.2009; opubl. 10.04.2012, BI №10. - 5 s.
13. Borzov D.B., Sokolova Yu.V. Metodika pererazmescheniya podprogramm v otkazoustoychivyh mul'tikomp'yuterah // Sbornik trudov XVIII Mezhdunarodnoy nauchno-tehnicheskoy konferencii «Mashinostroenie i tehnosfera XXI veka. T1». Doneck, 2011. S. 86-89.
14. Borzov D.B. Sokolova Yu.V., Masyukov I.I. Algoritm pererazmescheniya podprogramm v otkazoustoychivyh mul'tikomp'yuterah // Sbornik trudov XVIII Mezhdunarodnoy nauchno-tehnicheskoy konferencii «Mashinostroenie i tehnosfera XXI veka. T1». Doneck, 2012. S. 101-103.
