ПРОГРАММИРОВАНИЕ, 2012, No 3, с. 3-10
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ -
УДК 681.3.06:519
АЛГОРИТМ ПОСТРОЕНИЯ ОПТИМАЛЬНОЙ КОМПОНОВКИ ОДИНАКОВО РАСПРЕДЕЛЕННЫХ СИСТЕМ
© 2012 г. Н.С. Коваленко*, П.А. Павлов** * Белорусский государственный экономический университет, 220070 г. Минск, Партизанский проспект,, 26 ** Полесский государственный университет, 225710 г. Пинск, ул. Днепровской Флотилии, 23 E-mail: kovalenkons@rambler.ru, pin2535@tut.by Поступила в редакцию 01.10.2011 г.
Предлагается алгоритм оптимальной компоновки блоков структурированного программного ресурса в системах распределенных конкурирующих процессов.
1. ВВЕДЕНИЕ
Одним из важнейших требований к современным вычислительным многопроцессорным системам (МС), вычислительным комплексам (ВК), базам данных, маршрутизаторам и т.д. является масштабируемость (scalability). Она подразумевает способность системы увеличивать свою производительность при изменении аппаратных и программных ресурсов. В настоящее время вопросы масштабирования находятся в поле зрения как разработчиков параллельных МС, так и распределенной среды метакомпьютинга [1]. В таких вычислительных системах использование общего программного ресурса (ПР) [2] затрудняется из-за автономности процессорных узлов и отсутствием единой политики администрирования. Общим свойством, обеспечивающим возможность повышения производительности масштабируемых вычислительных систем, является распределенность процессов вычислений и данных с использованием принципов структурирования и конвейеризации [2]. В этой связи возникает необходимость новых принципов организации вычислений и распределения ресурсов, создания эффективного аппаратного и программного обеспечения, оптимального планирования и распределения вычислительных процессов [3].
При этом особую актуальность приобретают задачи эффективного управления множеством процессов, имеющих доступ к общим ресурсам, в том числе к программным. Математическая постановка такого рода задач была предложена и исследована ранее в работах [2, 4-6].
В частности, в [2, 4-6] было показано, что оптимальная по числу процессов система распределенных конкурирующих процессов содержится среди одинаково распределенных систем и равномерных структурирований программного ресурса на параллельно выполняемые блоки. Однако на практике достичь равномерности структурирования не всегда представляется возможным, что заставляет искать альтернативные подходы. Один из них -построение оптимальных компоновок из подряд идущих блоков распределенных процессов (все основные понятия и определения, включая параметры модели, приведены ниже).
В настоящей работе предлагается алгоритм построения оптимальной компоновки распределенных процессов, конкурирующих за использование линейно структурированного программного ресурса, требующий не более О (и3) элементарных операций, где п - число вычислительных процессов исходной одинаково распределенной системы.
2. ОСНОВНЫЕ ПОНЯТИЯ И ПОСТАНОВКА ЗАДАЧИ
Как и в [2, 4-6] процесс будем рассматривать как последовательность блоков (команд, процедур) 21, 22,..., 2«, для выполнения которых используется множество процессоров (процессорных узлов, обрабатывающих устройств, интеллектуальных клиентов). При этом процесс называется распределённым, если все блоки или часть из них обрабатываются разными процессорами. Для ускорения выполнения процессы могут обрабатываться параллельно, взаимодействуя путем обмена информацией. Такие процессы называются кооперативными или взаимодействующими процессами.
Понятие ресурса используется для обозначения любых объектов вычислительной системы, которые могут быть использованы процессами для своего выполнения. Реентерабельные (многократно используемые) ресурсы характеризуются возможностью одновременного использования несколькими вычислительными процессами. Для параллельных систем характерной является ситуация, когда одну и ту же последовательность блоков или ее часть необходимо процессорам выполнять многократно, такую последовательность будем называть программным ресурсом, а множество соответствующих процессов - конкурирующими.
Математическая модель системы распределенной обработки конкурирующих процессов включает в себя: в, в > 2 - число блоков линейно структурированного программного ресурса РЕ = (2ъ22,..., 2«); п,п > 2 -число распределенных относительно РЕ конкурирующих процессов; р,р > 2 - число процессоров многопроцессорной системы; матрицу Тр = ] времен выполнения j-х блоков г-ми конкурирующими процессами г = 1,п, j = 1,в; е - время, характеризующее дополнительные системные расходы по организации структурирования и параллельного использования блоков программного ресурса РЕ.
Также как и в [4-6] будем считать, что взаимодействие процессов, процессоров и блоков
линейно структурированного программного ресурса подчинено следующим условиям:
1. Ни один из блоков РЕ не может обрабатываться одновременно более чем одним процессором;
2. Ни один из процессоров не может обрабатывать одновременно более одного блока;
3. Обработка каждого блока осуществляется без прерываний;
4. Распределение блоков программного ресурса по процессорам МС для каждого из процессов осуществляется циклически по правилу: блок с номером j = кр + г, j = 1,в, г = 1,р, к > 0, распределяется на процессор с номером г. Кроме того, введем дополнительные условия, которые определяют режимы взаимодействия процессов, процессоров и блоков РЕ :
5. Отсутствуют простои процессоров при условии готовности блоков, а также невыполнение блоков при наличии процессоров;
6. Для каждого из п процессов момент завершения выполнения j-го блока на г-м процессоре совпадает с моментом начала выполнения следующего + 1)-го блока на (г + 1)-м процессоре, г = 1,р — 1, г = 1,8 — 1;
7. Для каждого из блоков структурированного программного ресурса момент завершения его выполнения 1-м процессом совпадает с моментом начала его выполнения (1 + 1)-м процессом на том же процессоре, 1 = 1, п — 1.
Условия 1-5 определяют асинхронный режим взаимодействия процессоров, процессов и блоков, который предполагает отсутствие простоев процессоров МС при условии готовности блоков, а также невыполнение блоков при наличии процессоров.
Если к условиям 1-4 добавить условие 6, то получим первый синхронный режим, обеспечивающий непрерывное выполнение блоков программного ресурса внутри каждого из вычислительных процессов.
Второй синхронный режим, определяемый условиями 1-4, 7, обеспечивает непрерывное выполнение каждого блока всеми процессами.
Определение 1. Распределенная система п взаимодействующих конкурирующих процессов называется неоднородной, если времена выполнения блоков РЯ зависят от объемов обрабатываемых данных и/или их структуры, т.е. разные для разных процессов.
Определение 2. Система конкурирующих процессов ково распределенной,
выполнения блоков Qj, ] = ресурса РЯ каждым из г-х и равны ^ для всех г = 1 цепочка равенств Ьц = ¿¿2 всех г = 1, п.
Ниже приведен пример системы распределенной обработки конкурирующих процессов для асинхронного режима взаимодействия процессов, процессоров и блоков и ее отображение с помощью линейных диаграмм Ганта. На рис. 1 и 2 представлены несовмещенная и совмещенная линейные диаграммы, с помощью которых отражено выполнение п = 4 неоднородных распределенных конкурирующих процессов в многопроцессорной системе с р = 3 процессорами при в = 8 блоках структурированного программного ресурса. Длительности выполнения каждого из блоков указаны на диаграммах, причем для первого процесса они составляют (3,1, 4, 2,1, 4, 2,1), второго - (2, 2,1,1, 3, 3, 2, 2), третьего - (1,3,3,1,1,3,3,1), четвертого -(4,1, 2, 3,1,1, 2, 5). Для лучшей наглядности длительности блоков первого процесса выделены. Общее время выполнения Тнс(р, п, в,е) неоднородных распределенных конкурирующих процессов на несовмещенной диаграмме равно 43, а на совмещенной - 35.
Пусть ТП = ЕП=1 - суммарное время выполнения каждого из блоков Qj всеми п процессами с учетом накладных расходов е,
Ьтах = Ьг , Ьг = + е, г = 1, п.
1<г<га
В [6] доказано, что для одинаково распределенных систем конкурирующих процессов
минимальное общее время для всех трех базовых режимов в случае неограниченного параллелизма (в < р), ив случае ограниченного параллелизма (в > р), но
если ТП < рЬ^ах определяется по формуле:
T(p,n,s,e) = TfT + (s - 1)t:
max,
(1)
взаимодействующих называется одина-если времена tij = 1,s, программного процессов совпадают , n, т.е. справедлива — • • • — 'tis — ti для
а в остальных случаях общее время выполнения п одинаково распределенных процессов, использующих структурированный на в блоков программный ресурс РЯ, в вычислительной среде с р процессорами при асинхронном режиме и в режиме непрерывного выполнения каждого блока всеми процессами, составляет величину:
T (p,n,s,e) — <
kTf + (p 1)tmax,
при S — kp, k > 1, TT > Pt£max,
(k + 1)tt + (r - 1)tmax,
при s — kp + r, k > 1, 1 < r < p, Tn > Ptf
max
(2)
где TT — ^T=i tf - суммарное время выполнения каждого из блоков Qj всеми n процессами с учетом накладных расходов е, tmax — maxtf,
1<i<n
tf — ti + е, i — 1,n.
С понятием множества одинаково распределенных конкурирующих процессов свяжем понятие линейной упаковки.
Определение 3. Пусть M — {m1, m2,..., mn} -
конечное упорядоченное множество предметов. Разбиение множества M на l непересекающихся подмножеств M1, M2,..., Mi такое, что каждое подмножество есть объединение последовательных элементов множества M, будем называть линейной упаковкой множества M ранга l.
Так как времена выполнения блоков программного ресурса каждым из процессов совпадают ti1 — ti2 — • • • — tis — ti, i — 1,n, то элементами множества M будем рассматривать последовательность, например, первых блоков Q11, Q21,..., Qn1 структурированного программного ресурса одинаково распределенных процессов, которую обозначим (q1, q2,..., qn). В этом
Рис. 1. Асинхронный режим - несовмещенная диаграмма Ганта
ар
и 1 3 2 Щ 3 3 1
1 2 3 1 Ц 3 1 1 1 2 1 5
3 2 1 4 ■ 1 1 3 2 2 3 2
35 -►
Тнас(р,п,8,е)
Рис. 2. Асинхронный режим - совмещенная диагра
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.