Разработка параллельного алгоритма построения оптимальной сети наземного цифрового телевизионного вещания

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

ВВЕДЕНИЕ

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

В работе [1] предложен подход к построению проекта сети наземного цифрового телевизионного вещания с минимальной стоимостью на единицу площади формируемой сети. В этой работе сеть формируется с регулярно расположенными на территории заданной площади (Sнсо = 177 756 км2) передающими станциями. Множество допустимых проектов сетей включает более 19 миллионов вариантов.

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

В связи с тем что последовательная программа требует больших временных затрат (более 12 часов расчетов на IntelXeonE5420), существует необходимость уменьшить время выполнения программы.

В данной работе разработаны параллельные алгоритмы построения оптимальной сети телевизионного цифрового вещания.



ПОСТРОЕНИЕ СЕТЕЙ ЦИФРОВОГО ТЕЛЕВИЗИОННОГО ВЕЩАНИЯ

Задача построения оптимальной сети ЦТВ

Одним из важнейших аспектов оптимального построения сети наземного цифрового телерадиовещания является рассмотрение способов построения такой сети:

- из мощных передатчиков и высоко подвешенных антенн;

- из маломощных передатчиков и низко (150 метров и ниже) подвешенных антенн;

- комбинированной сети из мощных и маломощных передатчиков.

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

- все радиовещательные станции идентичны с точки зрения их параметров;

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

- все они в равных условиях по количеству и уровню помех;

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

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

При этом критерием оптимальности построения такой сети предлагается принять затраты на сеть, приведённые к км2зоны обслуживания.

Таким образом, сеть формируется с регулярно расположенными на территории заданной площади (Sнсо = 177 756 км2) передающими станциями. Множество допустимых проектов сетей включает более 19 миллионов вариантов.

Рисунок 2.1 - Схема НСО с расположенными передающими станциями

Для решения поставленной задачи оптимального построения сети цифрового телерадиовещания необходимы исходные данные:

- площадь заданного региона (территории) Sтерр;

- рабочие диапазоны частот D;

- позиционность модуляции M;

- скорость свёрточного кода Rk;

- высоты подвеса передающих антенн h1.

Для заданных выше параметров нужно определить:

- необходимые мощности передатчиков Pпд(h1), обеспечивающие минимальную напряжённость поля Емин на расстоянии прямой видимости Rпр;

- зоны обслуживания Sобсл(h1) таких передатчиков с учётом перекрытия зон обслуживания соседних передатчиков (для однородной сети при 100 % обслуживании площадь зон перекрытия составляет 16.8 %);

- необходимое количество передающих станций Nст(h1) для обслуживания заданной территории;

- размерность кластера (необходимое количество частотных каналов) Скл(h1).

Необходимо также получить зависимости капитальных затратК(h1) и эксплуатационных расходов С(h1) для: антенно-мачтовых сооружений; передатчиков; антенн; фидеров; частотных каналов.

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

где г = h1.

Алгоритм полного перебора

Создана последовательная программа DTV поиска оптимального проекта сети методом полного перебора

Основу программы составляет блок перебора комбинаций пяти параметров (4 вложенных цикла), которые задают проект сети.

p - мощность передатчиков

f - частота радиовещания

h - высота подвеса передающих антенн

G - коэффициент усиления передающих антенн

m - позиционность модуляции

Остальные параметры и показатели в программе рассчитываются на основе значений этих параметров.

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

И в случае допустимого радиуса зоны рассчитывается стоимость сети. Целевая функция C(p, f, h, G, m) нелинейная и характеризует затраты на обслуживание 1 км2 покрываемой территории.

Листинг 2.1 - Блок перебора комбинаций параметров на псевдокоде

foreachpin [100..5 кВт] do

foreachfin [475..860 МГц] do

foreachh in [37,5..300 м] do

for each Gin [12, 18] do

for each min [1..15] do

/*…*/

r = compute_radius(p, f, h, G, m)

ifr<= R_прямой_видимостиthen

/*…*/

cost = compute_cost(p, f, h, G, m)

if cost <cost_minthen

cost_min = cost

end if

end if

end for

end for

end for

end for

endfor

Всего в программе обрабатывается более 19•106 проектов сетей.

Основные функции программы

В программе можно выделить следующие основные функции:

Функция search

Данная функция перебирает все возможные конфигурации проектов сетей.

Функция pfhgm (используется только в параллельных программах)

Данная функция вычисляет значения параметров p, f, h, G, mот номера проекта.

Функция compute_radius

Данная функция вычисляет радиус действия передатчика.

Функция compute_nclusters

Данная функция вычисляет размер кластера.

Функция compute_nstations

Данная функция вычисляет количество необходимых станций.

Функция compute_netcost

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

Блок-схемы

На рисунках 2.2-2.4 представлены блок-схема последовательной программы, и блок-схемы основных функций программы.



Рисунок 2.2- Блок-схема выполнения последовательной программы



Рисунок 2.3- Блок-схема функции вычисления радіуса действия передатчика

Рисунок 2.4- Блок-схема функции вычисления стоимости сети



ПОНЯТИЯ О РАСПРЕДЕЛЕННЫХ ВС

Распределенные ВС

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

1) параллельности функционирования сосредоточенных ВС (ЭМ в простейшем случае);

2) программируемости структуры (возможности автоматической настройки сети связи);

3) гомогенности состава (программной совместимости).

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

К структурам современных ВС предъявляется ряд требований [1].

1) Простота вложения параллельного алгоритма решения сложной задачи в структуру ВС. Структура ВС должна быть адекватна достаточно широкому классу решаемых задач; настройка проблемно-ориентированных виртуальных конфигураций не должна быть связана со значительными накладными расходами.

2) Удобство адресации элементарных машин и “переноса” подсистем в пределах вычислительной системы. Вычислительная система должна предоставлять возможность пользователям создавать параллельные программы с виртуальными адресами ЭМ. Следовательно, структура ВС должна позволять реализовать простейший “механизм” преобразования виртуальных адресов ЭМ в реальные (физические) адреса машин системы. Необходимость организации одновременного решения нескольких задач на ВС (т.е необходимость разделения пространства элементарных машин между задачами) обосновывает требование простоты перемещения подсистем в пределах системы (при сохранении их топологических свойств).

3) Осуществимость принципа близкодействия и минимума задержек при межмашинных передачах информации в ВС. Принцип близкодействия предопределяет реализацию обменов информацией между “удалёнными” друг от друга ЭМ через промежуточные машины системы. Следовательно, в условиях ограниченности числа связей у каждой ЭМ структура должна обеспечивать минимум задержек при “транзитных” передачах информации.

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

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

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

6) Живучесть структуры ВС. Важным требованием к ВС в целом является обеспечение работоспособности при отказе её компонентов или даже подсистем. Основой функциональной целостности ВС как коллектива элементарных машин является живучесть структуры. Под последним понимается способность структуры ВС обеспечить связность требуемого числа работоспособных ЭМ в системе при ненадёжных линиях межмашинных связей.

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

Структурные задержки при передачах информации между машинами ВС определяются расстоянием (в смысле теории графов) между вершинами структуры, сопоставленными взаимодействующим машинам [1, 3]. Для оценки структурных задержек в вычислительных системах используются диаметр и средний диаметр структуры. Диаметр есть максимальное расстояние, определённое на множестве кратчайших путей между парами вершин структуры ВС:

,	(3.1)

а средний диаметр -

,	(3.2)

где - расстояние, т.е. минимальное число рёбер, образующих путь из вершины в вершину ; ; - число вершин, находящихся на расстоянии от любой выделенной вершины (однородного) графа .

Показателем оценивающим структурную коммутируемость ВС, является вектор-функция

, ,	(3.3)

в которой координата есть вероятность реализации в системе при заданных структуре и коэффициентах готовности s и , соответственно, одной ЭМ и линии связи одновременных непересекающихся межмашинных взаимодействий (обменов информацией между ЭМ); - целая часть числа x.

Структурная живучесть ВС оценивается вектор-функцией

, ,	(3.4)

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

Наиболее полно перечисленным выше требованиям удовлетворяют однородные структуры (т.е. описываемые однородными графами) [1, 4, 5, 3]. Такие структуры являются перспективными для формирования масштабируемых и больше масштабных вычислительных систем (в частности, ВС с программируемой структурой).

В компьютерной индустрии получили распространение n-мерные структуры вычислительных систем, известные сейчас как циркулянтные (Circulant Sructures). Впервые они были определены и исследованы в Отделе вычислительных систем Института математики СО АН СССР в начале 70-х годов и первоначально назывались _графами [1]. По определению -граф или циркулянтная структура есть граф вида: , в котором:

- число вершин или порядок графа;

вершины помечены целыми числами по модулю , следовательно,

вершина соединена ребром (или является смежной) с вершинами

- множество целых чисел, называемых образующими, таких, что а для чисел наибольшим общим делителем является 1;

- размерность графа;

2n - степень вершины в графе.

В качестве примера рассмотрим -граф или двумерный циркулянт вида: , который изображен на рисунке 3.1.



Рисунок 3.1 --граф:

Графы вида , т.е. -графы или циркулянты с единичной образующей (Loop Networks - петлевые структуры) интенсивно изучаются в последнее время. Циркулянтные структуры широко внедрены в практику вычислительных систем.

Целые числа отмечающие вершины -графа, называют адресами. Адресация вершин в таких структурах называется диофантовой (в честь древнегреческого математика из Александрии Диофанта, Diophantos, 3 век). В циркулянтных структурах при полном переносе какой-либо подструктуры (всех вершин подструктуры на одно и то же расстояние в одном из направлений) сохраняются все её свойства и адресация вершин. Следовательно, при диофантовой адресации элементарных машин ВС можно простыми средствами реконфигурации осуществить виртуальную адресацию вершин-машин и, следовательно, создавать отказоустойчивые параллельные программы, реализовывать мультипрограммные режимы обработки информации, исключать отказавшие вершины-машины из подсистем, а значит обеспечить живучесть ВС.

При этом алгоритм работы реконфигуратора структуры ВС сводится к изменению адресов у всех машин подсистемы по формуле:

, ,	(3.5)

где i - номер ЭМ, исключаемой из подсистемы, а j - номер машины, включаемый в подсистему,

В качестве структур ВС, допускающих масштабирование (изменение числа машин) без коренной перекоммутации уже имеющихся межмашинных связей, используются -графы [1, 4, 5] (введённые также в Отделе вычислительных систем ИМ СО АН СССР). В такие графы вкладываются -графы; -граф - это неориентированный однородный граф с числом и степенями вершин, соответственно, и v и значением обхвата g. Примеры изображены на рисунке 3.2.

а - б - 

Рисунок 3.2 - Фрагменты-графов

В -графах каждая вершина при входит в не менее v кратчайших простых циклов длиной (длина кратчайшего цикл в графе называется обхватом). При -граф является простым циклом с вершинами.

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

В монопрограммном режиме для решения задачи используются все ресурсы ВС. Задача представляется в виде параллельной программы, число ветвей в которой либо фиксировано, либо допускает варьирование в заданном диапазоне. В качестве единицы ресурса выступает элементарная машина ВС. Все машины используются для решения задачи. Если максимальное число ветвей в параллельной программе менее общего числа ЭМ в системе, то “избыточные” машины используются для повышения надёжности функционирования ВС.

К мультипрограммным относят режимы [1, 3]:

1) обработки наборов задач;

2) обслуживания потоков задач.

При работе ВС в этих режимах одновременно решается несколько задач, следовательно, ресурсы системы делятся между ним.

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

Обслуживание потока задач на ВС - принципиально отличается от обработки наборов: задачи поступают в случайные моменты времени, их параметры случайны, следовательно, детерминированный выбор подсистем для решения тех или иных задач исключён. Для режима потока задач применяются методы и алгоритмы [3], обеспечивающие стохастически оптимальное функционирование вычислительных систем.

При работе ВС в любом из мультипрограммных режимов система представляется в виде композиции подсистем различных рангов. По мере решения задач эта композиция “автоматически” (с помощью операционной системы) реконфигурируется так, чтобы обеспечить её адекватность текущей мультипрограммной ситуации. Любая подсистема обладает всеми архитектурными свойствами системы, поэтому её организация при решении выделенной ей задачи может осуществляться теми же методами, что и организация работы всей ВС в первом режиме.

Кластерные ВС

Кластерные технологии стали логическим продолжением развития идей, заложенных в архитектуре MPP систем. Если процессорный модуль в MPP системе представляет собой законченную вычислительную систему, то следующий шаг напрашивается сам собой: почему бы в качестве таких вычислительных узлов не использовать обычные серийно выпускаемые компьютеры. Развитие коммуникационных технологий, а именно, появление высокоскоростного сетевого оборудования и специального программного обеспечения, такого как система MPI , реализующего механизм передачи сообщений над стандартными сетевыми протоколами, сделали кластерные технологии общедоступными. Сегодня не составляет большого труда создать небольшую кластерную систему, объединив вычислительные мощности компьютеров отдельной лаборатории или учебного класса.

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

Конечно, о полной эквивалентности этих систем говорить не приходится. Производительность систем с распределенной памятью очень сильно зависит от производительности коммуникационной среды. Коммуникационную среду можно достаточно полно охарактеризовать двумя параметрами: латентностью - временем задержки при посылке сообщения, и пропускной способностью - скоростью передачи информации. К примеру для компьютера Cray T3D эти параметры составляют соответственно 1 мкс и 480 Мб/сек, а для кластера, в котором в качестве коммуникационной среды использована сеть FastEthernet, 100 мкс и 10 Мб/сек. Это отчасти объясняет очень высокую стоимость суперкомпьютеров. При таких параметрах, как у рассматриваемого кластера, найдется не так много задач, которые могут эффективно решаться на достаточно большом числе процессоров.

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

Для создания кластеров обычно используются либо простые однопроцессорные персональные компьютеры, либо двух- или четырех- процессорные SMP-серверы. При этом не накладывается никаких ограничений на состав и архитектуру узлов. Каждый из узлов может функционировать под управлением своей собственной операционной системы. Чаще всего используются стандартные ОС: Linux, FreeBSD, Solaris, Tru64 Unix, Windows NT. В тех случаях, когда узлы кластера неоднородны, то говорят о гетерогенных кластерах.

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

Разработано множество технологий соединения компьютеров в кластер. Наиболее широко в данное время используется технология FastEthernet. Это обусловлено простотой ее использования и низкой стоимостью коммуникационного оборудования. Однако за это приходится расплачиваться заведомо недостаточной скоростью обменов. В самом деле, это оборудование обеспечивает максимальную скорость обмена между узлами 10 Мб/сек, тогда как скорость обмена с оперативной памятью составляет 250 Мб/сек и выше. Разработчики пакета подпрограмм ScaLAPACK, предназначенного для решения задач линейной алгебры на многопроцессорных системах, в которых велика доля коммуникационных операций, формулируют следующим образом требование к многопроцессорной системе: "Скорость межпроцессорных обменов между двумя узлами, измеренная в Мб/сек, должна быть не менее 1/10 пиковой производительности вычислительного узла, измеренной в Mflops". Таким образом, если в качестве вычислительных узлов использовать компьютеры класса Pentium III 500 Мгц (пиковая производительность 500 Mflops), то аппаратура FastEthernet обеспечивает только 1/5 от требуемой скорости. Частично это положение может поправить переход на технологии GigabitEthernet.

Ряд фирм предлагают специализированные кластерные решения на основе более скоростных сетей, таких как SCI фирмы ScaliComputer (~100 Мб/сек) и Mirynet (~120 Мб/сек). Активно включились в поддержку кластерных технологий и фирмы-производители высокопроизводительных рабочих станций (SUN, HP, SiliconGraphics).

Параллельные программы и алгоритмы

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

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

Методы и алгоритмы обработки информации, решения задач, как правило, - последовательные. Процесс “приспособления” методов к реализации на коллективе вычислителей или процесс “расщепления” последовательных алгоритмов решения сложных задач называется распараллеливанием.

Теоретическая и практическая деятельность по созданию параллельных алгоритмов и программ обработки информации называется параллельным программированием.

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

Рисунок 3.3 - Схемы параллельных алгоритмов

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

Пусть - количество операций, которые необходимо выполнить при решении задачи на ВС; n - число параллельных ветвей или число вычислителей, на которых решается задача, ; Тогда задачу, для которой выполняется условие

,	(3.6)

будем называть сложной, или системной, или трудоемкой, или с большим объемом вычислений [1].

В соотношении (3.6) - эмпирический коэффициент, . Очевидно, что имеет место зависимость от быстродействия каналов связей между вычислителями: при, где - время обращения к локальной памяти в вычислителе.

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

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

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

Стандарт MPI

Название "интерфейс передачи сообщений", говорит само за себя. Это хорошо стандартизованный механизм для построения параллельных программ в модели обмена сообщениями. Существуют стандартные "привязки" MPI к языкам С/С++, Fortran 77/90. Существуют бесплатные и коммерческие реализации почти для всех суперкомпьютерных платформ, а также для сетей рабочих станций UNIX и Windows. В настоящее время MPI - наиболее широко используемый и динамично развивающийся интерфейс из своего класса.[7,10,11]

Стандартизацией MPI занимается MPIForum. Последняя версия стандарта - 2.2. В этой версии к MPI добавлены такие важные элементы функциональности, как динамическое управление процессами, односторонние коммуникации (Put/Get), параллельный ввод/вывод. [8, 9]

Стандарт MPI-2.2. включает следующие основные группы функций:

Дифференцированные обмены

Коллективные обмены

Контексты, группы и коммуникаторы

Топологии процессов

Динамическое порождение процессов и управление процессами

Односторонние коммуникации

Параллельный Ввод/Вывод

Обзор коммуникационных операций типа точка-точка

К операциям этого типа относятся две представленные в предыдущем разделе коммуникационные процедуры. В коммуникационных операциях типа точка-точка всегда участвуют не более двух процессов: передающий и принимающий. В MPI имеется множество функций, реализующих такой тип обменов. Многообразие объясняется возможностью организации таких обменов множеством способов[11]. Описанные в предыдущем разделе функции реализуют стандартный режим с блокировкой.

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

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

Как для блокирующих, так и неблокирующих операций MPI поддерживает четыре режима выполнения. Эти режимы касаются только функций передачи данных, поэтому для блокирующих и неблокирующих операций имеется по четыре функции посылки сообщения. В таблице 3.1 перечислены имена базовых коммуникационных функций типа точка-точка, имеющихся в библиотеке MPI.

Таблица 3.1 - Список коммуникационных функций типа точка-точка

Режимы выполнения	С блокировкой	Без блокировки
Стандартная посылка	MPI_Send	MPI_Isend
Синхронная посылка	MPI_Ssend	MPI_Issend
Буферизованная посылка	MPI_Bsend	MPI_Ibsend
Согласованная посылка	MPI_Rsend	MPI_Irsend
Прием информации	MPI_Recv	MPI_Irecv

Из таблицы хорошо виден принцип формирования имен функций. К именам базовых функций Send/Recv добавляются различные префиксы.

Префикс S (synchronous) - означает синхронный режим передачи данных. Операция передачи данных заканчивается только тогда, когда заканчивается прием данных. Функция нелокальная.

Префикс B (buffered) - означает буферизованный режим передачи данных. В адресном пространстве передающего процесса с помощью специальной функции создается буфер обмена, который используется в операциях обмена. Операция посылки заканчивается, когда данные помещены в этот буфер. Функция имеет локальный характер.

Префикс R (ready) - согласованный или подготовленный режим передачи данных. Операция передачи данных начинается только тогда, когда принимающий процессор выставил признак готовности приема данных, инициировав операцию приема. Функция нелокальная.

Префикс I (immediate) - относится к неблокирующим операциям.

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



Обзор коллективных операций

Набор операций типа точка-точка является достаточным для программирования любых алгоритмов, однако MPI вряд ли бы завоевал такую популярность, если бы ограничивался только этим набором коммуникационных операций. Одной из наиболее привлекательных сторон MPI является наличие широкого набора коллективных операций, которые берут на себя выполнение наиболее часто встречающихся при программировании действий. Например, часто возникает потребность разослать некоторую переменную или массив из одного процессора всем остальным. Каждый программист может написать такую процедуру с использованием операций Send/Recv, однако гораздо удобнее воспользоваться коллективной операцией MPI_Bcast. Причем гарантировано, что эта операция будет выполняться гораздо эффективнее, поскольку MPI-функция реализована с использованием внутренних возможностей коммуникационной среды[3].

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

Набор коллективных операций включает:

Синхронизацию всех процессов с помощью барьеров (MPI_Barrier).

Коллективные коммуникационные операции, в число которых входят:

рассылка информации от одного процесса всем остальным членам некоторой области связи (MPI_Bcast);

сборка (gather) распределенного по процессам массива в один массив с сохранением его в адресном пространстве выделенного (root) процесса (MPI_Gather, MPI_Gatherv);

сборка (gather) распределенного массива в один массив с рассылкой его всем процессам некоторой области связи (MPI_Allgather, MPI_Allgatherv);

разбиение массива и рассылка его фрагментов (scatter) всем процессам области связи (MPI_Scatter, MPI_Scatterv);

совмещенная операция Scatter/Gather (All-to-All), каждый процесс делит данные из своего буфера передачи и разбрасывает фрагменты всем остальным процессам, одновременно собирая фрагменты, посланные другими процессами в свой буфер приема (MPI_Alltoall, MPI_Alltoallv).

Глобальные вычислительные операции над данными, расположенными в адресных пространствах различных процессов:

с сохранением результата в адресном пространстве одного процесса (MPI_Reduce); алгоритм сеть цифровой вещание

с рассылкой результата всем процессам (MPI_Allreduce);

совмещенная операция Reduce/Scatter (MPI_Reduce_scatter);

префиксная редукция (MPI_Scan).

Работа с группами и коммуникаторами

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

Группа представляет собой упорядоченное множество процессов. Каждый процесс идентифицируется переменной целого типа. Идентификаторы процессов образуют непрерывный ряд, начинающийся с 0. В MPI вводится специальный тип данных MPI_Group и набор функций для работы с переменными и константами этого типа. Существует две предопределенных группы:

MPI_GROUP_EMPTY - группа, не содержащая ни одного процесса;

MPI_GROUP_NULL - значение возвращаемое, когда группа не может быть создана.

Созданная группа не может быть модифицирована (расширена или усечена), может быть только создана новая группа. Интересно отметить, что при инициализации MPI не создается группы, соответствующей коммуникатору MPI_COMM_WORLD. Она должна создаваться специальной функцией явным образом.

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

В MPI существует два типа коммуникаторов:

intracommunicator - описывает область связи некоторой группы процессов;

intercommunicator - служит для связи между процессами двух различных групп.



ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ

Параллельные алгоритмы построения сети ЦТВ

Разработаны параллельные версии алгоритма и его различные программные реализации (в стандартах MPIи OpenMP). В общем случае, в алгоритмах вместо 5 циклов реализован 1 цикл, в котором идёт перебор номеров всех проектов сетей. Итерации этого цикла распределены между параллельными ветвями. Способы же распределения итераций по ветвям различны и будут описаны ниже.

Каждая ветвь, зная номер проекта (итерации), получает по номеру параметры - значения p, f, h, Gи m, через специальную функцию.

Листинг 4.1 - Основной цикл перебора проектов на псевдокоде

foreachprojectdo

p = get_p_by_project_no(project)

f = get_f_by_project_no(project)

h = get_h_by_project_no(project)

G = get_G_by_project_no(project)

m = get_m_by_project_no(project)

r = computer_radius(p, f, h, G, m)

/* ... */

endfor

При прямом (“наивном”) распараллеливании циклов (например, цикла по параметру p) масштабируемость алгоритма будет ограничена количеством значений, которые может принимать параметр p(в текущей версии 50).

В нашем же случае ВС имеет 144 вычислительных ядра, и такой способ распараллеливания цикла не является оптимальным. При организации одного цикла с перебором количества итераций больше 19•106, позволяет задействовать большее количество процессорных ядер.

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

Далее, после того как все ветви прекратят свою работу и корневая ветвь собрав информацию со всех ветвей, выбирает оптимальный проект и выводит на экран его параметры.

Реализованы следующие версии параллельных программ:

OpenMP.1

OpenMP-версия программы без использования директивы schedule. В данной программе все итерации равномерно (и поровну) распределяются между всеми процессами

0

…

…

…

…

…

…

…

…

…

…

~19 млн

Thread 0

Thread 1

…

Thread N

Рисунок 4.1 - распределение итераций в OpenMP-версии программы без использования директивы schedule.

Отражена подсистема состоящая из трёх вычислительных ядер и трёх ветвей параллельной программы

OpenMP.Static,4

OpenMP-версия программы с использованием директивы schedule(static,m).

Schedule определяет способ распределения итераций по ветвям. В данном случае используется тип static, который означает что итерации будут распределяться между нитями статически по алгоритму round robin, порциями размером в m итераций.



ветви	Thread_0	Thread_1	Thread_2	Thread_0	Thread_2	Thread_3	Thread_0
№ Итера- ции	0	1	2	3	4	5	6	…	~19 млн

Рисунок 4.2 - распределение итераций в OpenMP-версии программыс использованим директивы schedule(static,3).

OpenMP.Dynamic

OpenMP-версия программы с использованием директивы schedule(dynamic).

Schedule определяет способ распределения итераций по ветвям. Используется тип dynamic, который означает что итерации будут распределяться между ветвям таким образом, что если какая-либо ветвь заканчивает вычисления, ей динамически выделится следующая итерация.

MPI.S

MPI-версия программы,в которой все итерации равномерно (и поровну) распределяются между всеми процессами.

Принцип распределения итераций между процессами соответствует OpenMP-версии без использования директивы schedule. (рисунок 1).

На рисунке 4.13 видно, что в программе MPI.Sнаблюдается дисбаланс ветвей. Чтобы избавиться от этого эффекта была реализована программа MPI.-1.

MPI.-1

MPI-версия программы,в которой выделен один управляющий процесс который занимается исключительно распределением итераций по порядку остальным ветвям.

ветви	Thread_1	Thread_2	Thread_3	Thread_1	Thread_2	Thread_3	Thread_1
Итера- ции	0	1	2	3	4	5	6	…	~19 млн

Рисунок 4.3 - Принцип распределение итераций в MPI.1 программе при 4 процессах.

На рисунке 4.14 видно, что в данной программе исчез дисбаланс ветвей. Однако ускорение заметно меньше линейного.

MPI.NB

MPI-версия программы с алгоритмом работы напоминающим алгоритм используемый в OpenMP-версии программыс использованием директивы schedule(dynamic).

Дабы ускорить время выполнения программы MPI.-1, в программе MPI.NBиспользуются неблокирующие операции обмена типа точка-точка между корневой ветвью и остальными. Кроме того, чтобы минимизировать время на отправку итераций из корневого процесса и занять его вычислениями в свободное время, корневой процесс стал рассылать итерации «пачками».

Принцип работы программы:

1)0-ой процесс рассылает свою часть проектов каждому процессу (кроме 0-го) от первых 25% итераций от общего количества проектов.

0

…

…

…

…

…

…

…

…

…

…

~19 млн

25%

OGR

100%

Рисунок 4.4 - распределение итераций в MPI.NB программе

ogr =количество итераций - 1000 * количество выделенных процессорных ядер

2) Пока обработанных итераций менее чем ogr, нулевой процесс, помимо раздачи «пачек»итераций другим процессам, во время простоя (в ожидании запроса на следующую «пачку» итераций)ещё самостоятельно считает необработанные итерации.

3) Пока обработанных итераций меньше чем ogr (т.е. пока нулевому процессу разрешено не только рассылать итерации, но и считать самому), нулевой процесс рассылает итерации «пачками» по 1000 штук.Как только барьер ogr преодолён, размер «пачки»уменьшается до 10 итераций.

Организация экспериментов

Измерения производились на вычислительном кластере F (Jet).

Кластер Jet укомплектован 18 вычислительными узлами, управляющим узлом, вычислительной и сервисной сетями связи, а также системой бесперебойного электропитания. Узлы построены на базе серверной платформы Intel SR2520SAF. На каждом узле размещено два процессора Intel Quad Xeon E5420 с тактовой частотой 2.5 GHz. Пиковая производительность кластера - 1.4 TFLOPS. В таблицах 4.1, 4.2 и 4.3 показаны конфигурации вычислительного узла, управляющего узла и коммуникационной среды соответственно.

Таблица 4.1 - Конфигурация вычислительного узла

Системная плата	Intel S5000VSA (Сервернаяплатформа Intel SR2520SAF)
Процессор	2 x Intel Xeon E5420 (2,5 GHz; Intel-64)
Оперативная память	8 GB (4 x 2GB PC-5300)
Жесткий диск	SATAII 500GB (Seagate 500Gb Barracuda)
Сетевая карта	2 x Intel Gigabit Ethernet (Integrated Intel PRO/1000 EB, 80003ES2LAN Gigabit Ethernet Controller) 1 x Intel PRO/1000 MT Server Adapter (PWLA8490MT, 82572EI Gigabit Ethernet Controller)
Корпус	Rack mount 2U

Таблица 4.2 - Конфигурация управляющего узла

Системная плата	Intel S5000VSA (Серверная платформа Intel SR2520SAFR)
Процессор	2 x Intel Xeon E5420 (2,5 GHz; Intel-64)
Оперативнаяпамять	16 GB (8 x 2GB PC-5300)
Жесткий диск	3 x SATAII 500 GB (Seagate 500Gb Barracuda)
Сетеваякарта	1 x Intel PRO/1000 MT Server Adapter (82572EI Gigabit Ethernet Controller) 1 x Intel PRO/1000 Server Adapter (82545GM Gigabit Ethernet Controller) 1 x Dual Port Gigabit Ethernet Adapter (2 x Intel 80003ES2LAN Gigabit Ethernet Controller)
Корпус	Rack mount 2U
Привод DVD	DVD+/-RW

Таблица 4.3 - Конфигурация коммуникационной среды

Сервисная сеть	Коммутатор Gigabit Ethernet (D-Link DGS-1224T)
Коммутатор	Fast Ethernet (3Com OfficeConnect, 8 ports)
Вычислительная сеть	Коммутатор Gigabit Ethernet (D-Link DGS-1224T)

Кластер размещен в 19'' телекоммуникационном шкафу AESP Black Premium 48U. Система бесперебойного электропитания имеет мощность 12kVA и построена на базе источников бесперебойного питания APC Smart-UPS XL Modular 3000VA (SUM3000RMXLI2U).

На рисунке 4.5 приведена структура коммуникационной среды вычислительного кластера Jet.

Рисунок 4.5 - Структура коммуникационной среды кластера Jet



Результаты экспериментов

Для измерения времени выполнения ветвей и/или программы целиком в OpenMP-версиях программ использовалась функция omp_get_wtime; в MPI-версиях программ функция gettimeofday.

Рисунок4.6- Зависимость коэффициента S ускорения параллельной OpenMP-программы от количества n потоков



Рисунок4.7- Зависимость коэффициента S ускорения параллельной MPI-программы от количества n



Рисунок4.8- Зависимость времени работы параллельной OpenMP-программы от количества n потоков



Рисунок4.9-Зависимость времени работы параллельной MPI-программы от количества n потоков

Рисунок 4.10 - Время работы программ



Рисунок 4.11 - Ускорение параллельных программ относительно последовательной

Рисунок 4.12 -Коэффициент Eэффективности для различных параллельных программ.



Рисунок 4.13 -Время выполнения ветвей MPI-программы в которой итерации равномерно распределены между всеми процессами

Рисунок 4.14 - Время выполнения ветвей MPI-программы в которой один процесс выделен для распределения итераций остальным



Рисунок 4.15 - Время выполнения ветвей MPI-программы в которой один процесс выделен для распределения итераций «пачками» остальным (с отправкой подтверждения выполнения).



РАСЧЕТ ЭКОНОМИЧЕСКИХ ПОКАЗАТЕЛЕЙ ИССЛЕДОВАНИЯ

Расчёт себестоимости и цены программного продукта

Под себестоимостью программного продукта понимаются затраты, необходимые для его производства.

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

В данном случае период разработки программного продукта можно разделить на следующие основные этапы:

проектирование (определение и анализ требований к программному продукту, поиск необходимой информации по теме, составление алгоритма);

написание программы;

отладка и тестирование;

Для каждого этапа на основании экспертных оценок определяется средняя величина затрат времени по формуле

, (5.1)

где - среднее время, полученное на основании экспертных оценок;

- оценка затрат времени, данная руководителем проекта;

- оценка затрат времени, данная разработчиком.

Экспертные оценки времени рассчитываются по каждому этапу разработки программного продукта для трех ситуаций:

- - наименее возможная величина затрат;

- - наиболее вероятная величина затрат;

- - наиболее возможная величина затрат.

Результаты расчета средней оценки затрат времени приведены в таблице 5.1.

Таблица 5.1. Оценка затрат времени на разработку программного продукта.

Этапы разработки программного продукта	Наименее возможные затраты, , дни	Наиболее вероятные затраты, , дни	Наиболее возможные затраты, , дни
Проектирование	5	3	3.8	6	4	4.8	6	5	5.2
Написание программы	20	18	18.8	24	22	22.8	26	24	24.8
Тестирование и отладка	10	7	8.2	12	8	9.6	11	9	9.8
Итого	35	38	30.8	42	34	37.2	43	38	39.8

Далее определяется величина математического ожидания затрат времени по формуле

,	(5.2)

где - математическое ожидание затрат времени для i-го этапа;

, , - средние оценки.

Стандартное отклонение для каждого этапа определяется по формуле

,	(5.3)

где - стандартное отклонение для i-го этапа;

, - средние оценки.

Общая оценка затрат на разработку программного продукта вычисляется по формуле

,	(5.4)

где - общая оценка затрат времени;

- математическое ожидание затрат времени для i-го этапа, где

i меняется от 1 до n (количество этапов).

Стандартное отклонение общей оценки затрат на разработку программного продукта определяется по формуле

,	(5.5)

где - стандартное отклонение общей оценки затрат времени;

- стандартное отклонение оценки затрат времени для i-го этапа, где i меняется от 1 до n (количество этапов).

Для определения согласованности мнений экспертов определяется коэффициент вариации по формуле

,	(5.6)

где - коэффициент вариации для i-го этапа;

- стандартное отклонение для i-го этапа;

- математическое ожидание затрат времени для i-го этапа,

где i меняется от 1 до n (количество этапов).

Если коэффициент вариации меньше либо равен 0,3, то мнения экспертов считаются согласованными. Результаты расчетов затраты времени, математическое ожидание, стандартное отклонение, коэффициент вариации приведены в таблице 5.2.

Таблица 5.2. Результаты расчетов.

Этапы разработки программы	Средняя величина затрат времени, дни	Оценка затрат времени,MOi дни	Стандартное отклонение, Gi	Коэффициент вариации, Vi
Проектирование	3.8	4.8	5.2	4.7	0.23	0.049
Написание программы	18.8	22.8	24.8	22.4	1	0.045
Тестирование и отладка	8.2	9.6	9.8	9.4	0.26	0.028
Итого	30.8	7.2	9.8	36.5	1.5	0.041

Так как коэффициент вариации равен 0.041, что меньше, чем 0.3, то мнения экспертов считаются согласованными.

Себестоимость программного продукта определяется тремя составляющими:

оплата труда разработчика

оплата машинного времени

оплата работы в Интернет

Расчётная формула себестоимости имеет следующий вид:

,	(5.7)

где - себестоимость программного продукта;

- среднемесячная заработная плата разработчика с учетом районного коэффициента (примем рублей);

- количество рабочих дней в месяце (примем дням);

- трудозатраты на проектирование ( дней);

- трудозатраты на написание программного кода ( дней);

- трудозатраты на тестирование и отладку программного продукта ( дней);

- коэффициент, учитывающий отчисления во внебюджетные фонды ;

- коэффициент, учитывающий накладные расходы (примем );

- количество дней работы на компьютере;

- себестоимость одного часа машинного времени;

- количество дней работы в Интернете ( = 36.5 дней);

- себестоимость одного часа работы в Интернете по данным Новосибирского филиала ОАО “Ростелеком” (1,0 рубль).

Себестоимость машинного времени рассчитывается по формуле:

СМаш= (Згоа+ Зп э/э + Зг рем + Зг мат + Згпр) / Тг ПК, (5.8)

где Згоа - затраты на амортизационные отчисления;

Зп э/э - затраты на электричество;

Зг рем - затраты на ремонт ПК;

Зг мат - затраты на материалы к ПК;

Згпр - прочие затраты;

Тг ПК - годовой фонд полезного рабочего времени.

Амортизационные отчисления рассчитываются по формуле:



Згоа = ЦПК * (1 + Кц) * На ,(5.9)

где ЦПК - рыночная стоимость ПК;

Кц - коэффициент учитывающий затраты персонального времени (Кц = 0,7)

На - норма амортизации;

Рассчитаем амортизационные отчисления. Стоимость компьютера, на котором проводилась разработка программного обеспечения, равна 20000 руб. Амортизационный период для компьютерной техники составляет от 3 до 5 лет. В данном случае примем амортизационный период равный 3 годам. Тогда норму амортизации годовую можно принять в размере 0.33%.

Згоа = 20000 * (1 + 0,7) * 0,33 = 11220 р/год

Затраты на электроэнергию рассчитываются так: