НАУКА и ОБРАЗОВАНИЕ

УДК 685.32:519.68

МГТУ им. Н.Э. Баумана

kirur@bk.ru

Как было показано в [1], весьма удобным средством для изображения параллельных алгоритмов является граф-схема. В работе [2] был предложен метод построения диаграмм решения параллельной задачи, представленной информационной граф-схемой.

Построенные диаграммы (см. рисунок 6.1.2.) является удобным средством построения плана распределения операторов по ВМ вычислительной системы. Строки временной диаграммы будем интерпретировать как нити алгоритма решаемой задачи, в соответствии с установившейся терминологией. Для удобства размещения операторов алгоритма на вычислительные модули ВС, представим структуру ВС в виде матрицы дистанций между вычислительными модулями ВС, в которой указаны расстояния между ВМ, измеренные в количестве ВМ между двумя рассматриваемыми. В качестве примера возьмём обобщённый 3-х мерный гиперкуба 2х3х3, представленный на рисунке 6.2.1.

Рисунок 6.2.1. Схема представления обобщенного 3-х мерного гиперкуба 2х3х3

Построим для него матрицу дистанций, которую, в дальнейшем удобно использовать для размещения нитей решаемой задачи. Нумерация ВМ производится, как показано в таблице  6.2.1.

Матрица дистанций представлена в таблице 6.2.2. В последней строке приведены итоговые суммы по столбцам. Минимальная сумма определяет лучший ВМ, который имеет минимальное расстояние ко всем остальным вычислительным модулям. В данном случае лучшим ВМ является вычислительный модуль  с номерами 9, затем  11 и т. д.

Рассмотрим алгоритм, представленный граф-схемой на рисунке 6.2.2.

Рисунок 6.2.2. Граф-схема примера алгоритма решаемой задачи. Вершины 7, …, 16 представляют ветви цикла. Вершина 19, …, 22 отображает так же распараллеленный цикл

Для построения нитей решаемой задачи построим диаграмму ранних сроков окончания выполнения операторов. Используя алгоритм 6.1.1, вычислим t_1,1, …, t_1,27. Вычисленные данные представлены в таблице 6.2.3. Диаграмма ранних сроков окончания выполнения операторов представлена на рисунке 6.2.3.

Tак как рассматривается ВС с общей памятью, обмена данными через каналы связи между процессорами нет, и количество нитей меньше, чем число процессоров, поэтому распределение нитей между ВМ может осуществляться, например, следующим образом: первая нить загружается в первый ВМ, вторая – во второй и т. д. Процессоры с шестого по тринадцатый освобождаются в момент относительного времени Т=18 и могут быть распределены для решения других задач. Аналогично процессоры 6,7,8,9,10,11,12 также могут быть использованы другими задачами по мере их освобождения, что наглядно видно из рисунка 6.2.3. Стрелками на этом рисунке показаны связи между нитями.

 Таблица 6.2.1

Построим нити для диаграммы, представленной на рисунке 6.2.2. Нити H_i составят операторы: Н₁={1, 3, 7,  18, 24}, H₂={2, 8, 19, 23}, H₃={9, 20, 26}, H₄={10, 21, 25}, H₅={11, 22, 25}, H₆={12}, H₆={12}, H₇={13}, H₈={14}, H₉={15}, H₁₀={16}, H₁₁={4}, H₁₂={5}, H₁₃={6,14} для i =.1,…,13.

Таблица 6.2.2

Таблица  6.2.3

Рисунок 6.2.3. Диаграмма ранних сроков окончания выполнения операторов

Паузы, возникшие на  6, 7, 12, 13 моментах времени связаны с синхронизацией вычислений, определяемой структурой рассматриваемой граф-схемы. Общее время решения этой задачи составляет 28 условных единиц. 

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

Рассмотрим распределение операторов по ВМ вычислительной системы с общим полем памяти для информационно-логической граф-схемы

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

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

,

 где  r– количество логических  операторов в программе, q_j,i– количество ВМ, необходимых для реализации i-й ветви j-ого логического оператора. N – максимальное количество ВМ, необходимых для реализации логических путей решаемой задачи. В этом случае требуемое количество ВМ уменьшится на   N* =.   

Второй способ в построении некоторого динамического плана, состояние которого изменяется каждый раз, как только выполняется очередной логический оператор. Такой план в дальнейшем будем называть адаптивным. Рассмотрим построение такого плана, используя  граф-схему,  представленную на рисунке 6.2.4.      

Диаграмма для информационно-логической граф-схемы, представленной на рисунке 6.2.4 представляется множеством диаграмм по мере поступления логических переменных. Предполагаемое количество ВМ, необходимых для решения этой задачи, можно оценить с помощью формулы q_j,i, где q_j,i– количество ВМ, необходимых для реализации i-й ветви j-ого логического оператора. Если в граф-схеме, представленной на рисунке 6.2.4, логический оператор «один» выбирает движение по дуге 1.1, то очередная диаграмма будет выглядеть, как показано на рисунке 6.2.5. 

При срабатывании условного оператора «один», дуги 1.1 требуется 10 ВМ. Время решения задачи составит 22 условные единицы.

Если же в условном операторе «один» выбирается дуга 1.2, то диаграмма преобразуется, как показано на рисунке 6.2.6.  Для реализации этой диаграммы требуется всего пять ВМ, которое может быть уменьшено за счёт учёта работы  логического оператора «17», Наиболее нагруженная ветвь «17.3», поэтому представим временную диаграмму для ветви «17.3. Диаграммы для остальных ветвей строятся аналогично. 

Рисунок 6.2.4. Информационно-логическая граф-схема, реализованная в виде композиций логических функций «И» и «Исключающее ИЛИ»

Рисунок 6.2.5. Диаграмма ранних сроков окончания выполнения операторов для информационно-логической граф-схемы при срабатывании дуги 1.1.

Рисунок 6.2.6. Диаграмма ранних сроков окончания выполнения операторов при срабатывании дуги 1.2.

После учёта работы всех логических операторов, в зависимости от исходных данных, определяющих ту или иную ветвь срабатывания логических операторов, количество используемых операторов колеблется от 10 до трёх. При использовании ВС с общей памятью распределение операторов по ВМ может быть произвольным.  Например, первую нить, образованную операторами {1, 2, 4} можно загрузить в первый процессор, вторую, представленную множеством {5, 17, 21, 26}, выполнить на втором процессоре, и, наконец, третью нить {6, 27} выполнить на третьем процессоре. Варианты выполнения плана в случае использования функций «Исключающее ИЛИ» могут быть упорядочнены в порядке убывания вероятностей. Вероятность окончания решения задачи по тому или иному варианту может быть получена на основании заранее определённых вероятностей P_i,j, где i – номер рассматриваемого логического оператора, j– номер выхода в логическом операторе. Из анализа транзитивной матрицы [ 3 ] следования информационно-логической граф-схемы решаемой задачи можно определить требуемые вероятности следующим образом.  Просматривая столбцы этой матрицы, находим последние элементы столбца, содержащего конкатенацию символов, определяющих  выходы операторов «Исклющающее ИЛИ». Затем конкатенацию символов i^(r1)_v1_ i^(ri)_vi_…_ i^(rn)_vn заменяем на произведение вероятностей – P_реш=P^(r1)_v1*…* P^(rn)_vn, где  P_реш – вероятности решения задачи при том или ином варианте исходных данных решаемой задачи, P^(ri)_vi – вероятность выбора ri логическим оператором viпути.

Рисунок 6.2.7. Диаграмма ранних сроков окончания выполнения операторов при срабатывании дуги 17.3.

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

Литература

1. Руденко Ю.М. Новый подход к изображению схем алгоритмов для вычислительных систем. Информатика и системы управления в ХХ1 веке. Сборник трудов №7 молодых учёных, аспирантов, и студентов – М,: МГТУ им. Н.Э. Баумана, 2009. 167–181 с.

2. Руденко Ю.М. Построение плана выполнения параллельных алгоритмов на базе граф-схем. Аэрокосмические технологии. Научные материалы МНТК – 2009.

Реутов – Москва 2009. 179=181с.

3. Руденко Ю.М. Учёт зависимостей программных модулей по данным и последовательностям их выполнения при параллельных вычислениях. Известия высших учебных заведений. Поволжский регион. Технические науки. № 3 (11), 2009. 67–75 с.