Software & Systems

Введение. Распределенные вычисления – перспективная и динамично развивающаяся область организации параллелизма [1–3]. Данный термин обычно используется при параллельной обработке данных на множестве обрабатывающих устройств, удаленных друг от друга, в которых передача данных по линиям связи приводит к существенным временным задержкам. Перечисленные условия характерны, например, при организации вычислений в многомашинных вычислительных комплексах, вычислительных кластерах, многопроцессорных системах, локальных или глобальных сетях. Создание высокопроизводительных мно- гопроцессорных систем и вычислительных комплексов характеризуется широким проникновением в аппаратное и программное обеспечение фундаментальных принципов распараллеливания и конвейеризации вычислений. В связи с этим происходит пересмотр математических методов и алгоритмов решения задач в различных предметных областях вплоть до всего алгоритмического багажа прикладной математики, выдвигаются новые требования к построению и исследованию математических моделей, касающихся различных аспектов параллельной и конвейерной организации вычислений [4]. Необходимость и актуальность исследований в этих направлениях связана также с тем, что принципы структурирования, распараллеливания и конвейеризации носят достаточно общий характер и присущи процессам различной природы [5, 6].

Случай, когда в общей памяти многопроцессорных систем имеется одна копия программного ресурса, был изучен в работах [7–9] с различных точек зрения. Но, к сожалению, не найдено работ по математическому моделированию функционирования распределенных систем, в которых в общей памяти не одна, а несколько копий программного ресурса. Поэтому изучение задач, относящихся к оптимальной организации распределенных параллельных вычислений, приобретает особую актуальность, когда в общей памяти многопроцессорных систем может одновременно размещаться ограниченное число копий программного ресурса. Такое обобщение носит принципиальный характер ввиду того, что отражает основные черты мультиконвейерной обработки, а также позволяет сравнить эффективность конвейерной и параллельной обработки.

Математическая модель распределенных вычислений

Конструктивными элементами для построения математических моделей, реализующих методы распределенных вычислений, являются понятия процесса и программного ресурса. Будем рассматривать процесс как последовательность наборов команд (процедур, блоков, подпрограмм) Is = (1, 2, …, s). Процессы, влияющие на поведение друг друга путем обмена информацией, называют кооперативными или взаимодействующими. Многократно выполняемую в многопроцессорной системе программу или ее часть будем называть программным ресурсом, а множество соответствующих процессов – конкурирующими.

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

– p ³ 2 процессоров многопроцессорной системы, имеющих доступ к общей памяти;

– n ³ 2 распределенных конкурирующих процессов;

– s ³ 2 блоков структурированного на блоки программного ресурса;

– матрицу , , , времен выполнения блоков программного ресурса распределенными взаимодействующими конкурирующими процессами;

– 2 £ c £ p копий структурированного на блоки программного ресурса, которые могут одновременно находиться в оперативной памяти, доступной для всех p процессоров;

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

Предположим, что число блоков програм- много ресурса , где [x] – целая часть числа, а число процессов n кратно числу копий c структурированного программного ресурса, то есть n = mc, m ³ 2, и что взаимодействие процессов, процессоров и блоков программного ресурса подчинено следующим условиям:

1) ни один из процессоров не может обрабатывать одновременно более одного блока;

2) процессы выполняются в параллельно-конвейерном режиме группами, то есть осуществляется одновременное (параллельное) выполнение c копий каждого блока в сочетании с конвейеризацией группы из c копий Qj-го блока по процессам и процессорам, где ;

3) обработка каждого блока программного ресурса осуществляется без прерываний;

4) распределение блоков Qj, , программного ресурса по процессорам для каждого из процессов , , , где , осуществляется циклически по правилу: блок с номером j распределяется на процессор с номером .

Время выполнения неоднородных процессов при достаточном числе процессоров

В рамках математической модели распределенных вычислений при ограниченном числе копий программного ресурса исследуем первый синхронный режим взаимодействия процессов, процессоров и блоков, который обеспечивает непрерывное выполнение блоков структурированного программного ресурса внутри каждого процесса, то есть все процессы являются активными. В этом режиме в случае, когда , момент завершения выполнения j-го блока, , i-м процессом, где , , , на  процессоре совпадает с моментом начала выполнения следующего (j + 1)-го блока на (cj + + q)-м процессоре.

Система n распределенных конкурирующих процессов называется неоднородной, если времена выполнения блоков программного ресурса Q1, Q2, …, Qs зависят от объемов обрабатываемых данных и/или их структуры, то есть разные для разных процессов.

Рассмотрим случай, когда число процессоров распределенной неоднородной многопроцессорной системы является достаточным, то есть . Все множество процессов разобьем на c подмножеств по m процессов в каждом, причем в каждое q-е подмножество будут включены процессы с номерами , , , блоки которых будут выполняться на  процессорах, .

Обозначим через  время выполнения n неоднородных конкурирующих процессов, использующих c копий програм- много ресурса, структурированного на s линейно-упорядоченных блоков Q1, Q2, …, Qs с матрицей времен выполнения с учетом дополнительных системных расходов  в первом синхронном режиме. Предполагается, что выполнение процессов осуществляется в вычислительной системе с p процессорами и каждый из процессов является распределенным.

Построим диаграмму Ганта, иллюстрирующую функционирование распределенной системы (рис. 1) c параметрами p = 7, n = 6, s = 3, c = 2, .

Для вычисления времени выполнения имеет место формула

                                (1)

Здесь ,  – начало выполнения первого блока для каждого из последующих процессов, начиная с (ci + q)-го в q-м подмножестве процессов, а  – длительность выполнения последнего процесса q-го подмножества, где  [10].

Найдем по данным примера, используя формулу (1):

.

Следовательно, время выполнения , что совпадает со временем на диаграмме Ганта (рис. 1).

Время реализации неоднородных процессов в условиях ограниченного параллелизма

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

, , где .                                           (2)

На рисунке 2 изображена диаграмма Ганта для многопроцессорных систем с парамет- рами p = 7, n = 4, s = 6, c = 2,

Из анализа диаграмм Ганта (рис. 2) видно, что каждая из них отображает во времени выполнение очередных  блоков програм- много ресурса на  процессорах всеми n процессами, причем при  непрерывность выполнения блоков структурированного программного ресурса может нарушиться при переходе от j-й группы блоков к (j + 1)-й, , а внутри каждой из групп непрерывное выполнение блоков каждого процесса сохраняется.

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

▪        – время выполнения i-м процессом из q-го подмножества процессов j-го блока из j-й группы блоков с учетом параметра q, , , , ;

▪        – время выполнения q-го подмножества процессов в j-й группе блоков , ;

▪     

 – общее время выполнения f-й группы блоков всеми n процессами на  процессорах, ;

▪        – время завершения обработки i-м процессом q-го подмножества j-го блока из j-й группы блоков, где , , , .

Найдем значения , , ,  для многопроцессорной системы, изображенной на рисунке 2:

;

Если j = 1, q = 1, i = 1, имеем , , тогда

Если j = 1, q = 1, i = 2, имеем

 , тогда

Если , , , имеем , , тогда

; ;

Если , , , имеем , , тогда

Если , , , имеем    

Если , , , имеем   

Если , , , имеем   

Если , , , имеем   

Из анализа диаграмм Ганта (рис. 2) видно, что минимальное общее время выполнения неоднородных распределенных процессов, конкурирующих за использование c копий структурированного программного ресурса в случае , , , определяется как сумма длин составляющих диаграмм, то есть

Время  можно существенно сократить, если воспользоваться совмещением последовательных диаграмм Ганта по оси времени справа налево. В результате совмещения получим

,

где ,  – длина отрезка максимально возможного совмещения двух последовательных диаграмм Ганта по оси времени.

Здесь  – отрезок возможного совмещения по оси времени, который представляет собой разность между моментом начала выполнения j-го блока первым процессом q-го подмножества процессов в  группе блоков и моментом завершения выполнения j-го блока последним процессом q-го подмножества процессов в j-й группе блоков, то есть

 .

Значение  представляет собой разность между началом выполнения первого блока i-м процессом в  группе блоков и моментом завершения выполнения последнего блока i-м процессом в j-й группе блоков, то есть

Для многопроцессорных систем (рис. 2) получим

Тогда  Следовательно, время выполнения  (рис. 3).

В случае, когда , , , все множество из s блоков разбивается на  групп по  блока(ов) в каждой, за исключением последней, в которой будет только r блока(ов) программного ресурса. Тогда время выполнения n неоднородных распределенных конкурирующих процессов, использующих c копий структурированного на s блока(ов) программного ресурса в вычислительной системе с p процессорами в первом синхронном режиме, будет определяться по формулам:

где  – время выполнения (k + 1)-й группы из r блоков всеми n процессами,  – время выполнения q-го подмножества из m процессов в (k+1)-й группе блоков, , а  – величина максимально допустимого совмещения по оси времени k-й и (k + 1)-й диаграмм.

Значения ,  и  определяются по следующим формулам:

▪        ;

▪      

▪       .

Здесь

На рисунках 4 и 5 для распределенной вычислительной многопроцессорной системы с параметрами , , , ,

 построены не- совмещенные и совмещенные диаграммы Ганта. Найдем минимальное время выполнения процессов для данной многопроцессорной системы:

;

Если , , то

 тогда  

Если , , то

, тогда  

Если , , то  

, тогда  

Если , , то

 , тогда  

Следовательно, .

Тогда время выполнения n = 4 неоднородных распределенных конкурирующих процессов, использующих c = 2 копии структурированного на s = 8 блоков программного ресурса в многопроцессорной системе с p = 7 процессо- рами с учетом дополнительных системных расходов q, будет определяться по формуле

Заключение

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

Список литературы

1.   Антонов А.С., Афанасьев И.В., Воеводин Вл.В. Высокопроизводительные вычислительные платформы: текущий статус и тенденция развития // Вычислительные методы и программирование. 2021. Т. 22. С. 135–177. doi: 10.26089/NumMet.v22r210.

2.   Бурдонов И.Б., Евтушенко Н.В., Косачев А.С. Реализация распределенных и параллельных вычислений в сети SDN // Тр. ИСП РАН. 2022. Т. 34. С. 159–172. doi: 10.15514/ISPRAS-2022-34(3)-11.

3.   Роби Р., Замора Дж. Параллельные и высокопроизводительные вычисления; [пер. с англ.]. М.: ДМК Пресс, 2021. 800 с.

4.   Топорков В.В., Емельянов Д.М. Модели, методы и алгоритмы планирования в грид и облачных вычислениях // Вестн. МЭИ. 2018. № 6. С. 75–86. doi: 10.24160/1993-6982-2018-6-75-86.

5.   Zaiets N., Shtepa V., Pavlov P., Elperin I., Hachkovska M. Development of a resource-process approach to increasing the efficiency of electrical equipment for food production. Eastern-European J. of Enterprise Technologies, 2019, vol. 5/8, no. 101, pp. 59–65. doi: 10.15587/1729-4061.2019.181375.

6.   Каплун В.В., Штепа В.Н., Прокопеня О.Н. Ресурсно-процессная модель энергоменеджмента локального объекта с несколькими источниками энергии // Вестн. БрГТУ. Сер. Машиностроение. 2019. № 4. С. 86–91.

7.   Pavlov P.А. The optimality of software resources structuring through the pipeline distributed processing of competitive cooperative processes. IJMT, 2012, vol. 2, no. 1, pp. 5–10.

8.   Коваленко Н.С., Павлов П.А., Овсец М.И. Задачи оптимизации числа процессоров и построения оптимальной компоновки распределенных систем // Вестн. БГУ. Сер. 1: Физика. Математика. Информатика. 2012. № 1. С. 119–126.

9.   Kovalenko N.S., Pavlov P.А., Ovseec M.I. Asynchronous distributed computations with a limited number of copies of a structured program resource. Cybernetics and systems analysis, 2012, vol. 48, no. 1, pp. 86–98. doi: 10.1007/s10559-012-9385-z.

10. Лазарев А.А. Теория расписаний. Методы и алгоритмы. М., 2019. 408 с.

References

1. Antonov, A.S., Afanasev, I.V., Voevodin, Vl.V. (2021) ‘High-performance computing platforms: Current status and development trends’, Numerical Methods and Programming, 22, pp. 135–177 (in Russ.). doi: 10.26089/NumMet.v22r210.
2. Burdonov, I.B., Evtushenko, N.V., Kossatchev, A.S. (2022) ‘Implementation of distributed and parallel computing in the SDN network’, Proc. of ISP RAS, 34, pp. 159–172 (in Russ.). doi: 10.15514/ISPRAS-2022-34(3)-11.
3. Robey, R., Zamora, Yu. (2021) Parallel and High Performance Computing, Manning Publ., 704 p. (Russ. ed.: (2021) Moscow, 800 p.).
4. Toporkov, V.V., Emelyanov, D.M. (2018) ‘Scheduling models, methods and algorithms in grid and cloud computing’, Bull. of MPEI, (6), pp. 75–86 (in Russ.). doi: 10.24160/1993-6982-2018-6-75-86.
5. Zaiets, N., Shtepa, V., Pavlov, P., Elperin, I., Hachkovska, M. (2019) ‘Development of a resource-process approach to increasing the efficiency of electrical equipment for food production’, Eastern-European J. of Enterprise Technologies, 5/8(101), pp. 59–65. doi: 10.15587/1729-4061.2019.181375.
6. Kaplun, V.V., Pavlov, P.A., Shtepa, V.M., Prokopenya, O.N. (2019) ‘Resource-process model of local object energy management with several energy sources’, Bul. Of BrSTU. Ser. Mechanical Engineering, (4), pp. 86–91 (in Russ.).
7. Pavlov, P.А. (2012) ‘The optimality of software resources structuring through the pipeline distributed processing of competitive cooperative processes’, IJMT, 2(1), pp. 5–10.
8. Kovalenko, N.S., Pavlov, P.A., Ovseec, M.I. (2012) ‘The tasks of optimizing the number of processors and building an optimal layout of distributed systems’, Bul. of BSU, (1), pp. 119–126 (in Russ.).
9. Kovalenko, N.S., Pavlov, P.А., Ovseec, M.I. (2012) ‘Asynchronous distributed computations with a limited number of copies of a structured program resource’, Cybernetics and Systems Analysis, 48(1), pp. 86–98. doi: 10.1007/s10559-012-9385-z.
10. Lazarev, A.A. (2019) Theory of Schedules. Methods and Algorithms, Moscow, 408 p. (in Russ.).