где F (с чертой) – задаваемый входной поток, F - реальный входной поток. При взаимодействии двух задач соединенных каналом обмена данных, величина выходного потока первой задачи строго равна величине входного потока второй задачи:
Таким образом, при увеличении F1in, если F2in достиг максимума F2max, то F1in не может далее увеличиваться (см. рисунок). А коэффициент обработки по входу z1 и выходу z2 равен произведению коэффициентов s1 и s2 первой и второй задачи, соответственно: Модель графа потоков данных параллельного алгоритма (ГПД)
Граф потоков данных алгоритма является ориентированнным графом, в котором вершины представляют вычислительные задачи, а дуги – каналы обмена данных: G(V, U) ГПД параллельного алгоритма, V = { v1, v2, … vM } множество вершин-задач, U = { ujikl } множество дуг-каналов обмена данных, где
ujikl – канал между задачами vk и vl, соединяющий выходной порт j задачи vk со входным портом i задачи vl. Задача vk имеет mk входных портов под номерами {0, 1, …mk-1} и nk выходных -{0, 1, …nk-1}. Должны быть согласованы размеры передаваемых и принимаемых данных для каждого канала обмена. Т. е. для "ujiklО U, размер порции данных, исходящих из порта vkj, должны в точности равняться размерам входных данных в порт vli. Данное определение ГПД не делает ограничений на наличие кратных дуг и петель. Т. е. две задачи могут быть связаны несколькими однонаправленными каналами. А также канал может соединять собой выходной и входной порт одной и той же задачи. Ниже будет осуществляться переход к более удобному для анализа представлению ГПД. Характеристики параллельных вычислительных процессов (ПВП)
Любая вычислительная система состоит из набора, так называемых, функциональных устройств (ФУ) – это могут быть процессоры, каналы связи, память, накопители и т. п. – все, что участвует или влияет на процесс работы параллельного алгоритма. Для ФУ можно определить величину загруженности p на определенном интервале времени T, как отношение стоимости выполненной ФУ работы к максимальной стоимости работы, которая может быть выполнена данным ФУ за время T. Стоимость работы может измеряться, например, в количестве арифметических операций, времени и т. п. Каждое ФУ характеризуется номинальной производительностью a (далее производительность), равной максимальной стоимости работы за единицу времени.
Утверждение. Пусть в системе имеется N функциональных устройств {ФУ1, ФУ2, … ФУN} с номинальными производительностями {a1, a2, … aN}, соответственно. Тогда загруженность всей системы p выражается через загруженности pi ФУ, входящих в систему, как где еaj – номинальная производительность системы. Доказательство.
Пусть за время T ФУi выполнило работу стоимостью bi. Максимальная стоимость работы, которую может выполнить ФУi за T, равна ai T. Вся система реально выполнила еbi, а максимально может - еai T. Следовательно: ч. т. д.
Следствие 1. Если система состоит из ФУ одинаковой производительности, то её загруженность равна среднему арифметическому загруженностей ФУ.
Следствие 2. Чтобы выполнить работу заданной стоимости за минимальное время необходимо обеспечить максимальную загруженность ФУ наибольшей производительности. Доказательство. ч. т. д.
Важной характеристикой параллельного алгоритма является коэффициент ускорения (далее ускорение):
где T – время выполнения алгоритма на параллельной вычислительной системе, а To – на простом, т. е. непараллельном или эталонном, ФУ. Если принять за a0 и a - производительности эталонной и параллельной вычислительных систем, соответственно, тогда: где Rmax – максимальное ускорение, которое можно получить на данной параллельной системе; реальное ускорение зависит от степени загруженности системы:
Если R < 1, то параллельный алгоритм не имеет смысла выполнять на данной параллельной вычислительной системе. Возвращаясь к модели вычислительной задачи, выведем важное неравенство, касающееся многозадачных операционных систем ЭВМ. Это неравенство характеризует загруженность процессора, если на нем работают несколько задач, а также взаимное влияние задач. Рассмотрим случай двух задач z1 и z2, на процессоре P. Пусть они работают с периодами q1 и q2, соответственно. Времена обработки данных t1 и t2 соответствуют работе каждой задачи поотдельности на данном процессоре, т. е. без влияния другой задачи. В данном случае за стоимость берётся время выполнения задачи на данном процессоре, а точнее время чистых вычислений, т. о. стоимость задач равна t1 и t2. При выполнении задач z1 и z2 одновременно на многозадачном процессоре P, стоимость выполненой работы за время T равна: т. к. отношения T к qi равны количеству циклов обработки за время T, при T >> t1 и t2. Максимальная стоимость работы, которую мог бы выполнить процессор, выраженная в единицах времени, равна T. Следовательно, загруженность процессора:
где p1 и p2 – загруженности, вносимые каждой из задач. То же неравенство в терминах входных потоков выглядит так:
где s1 и s2 – входные потоки задач z1 и z2, а x1 и x2 – соответствующие максимальные потоки при работе задачи на данном процессоре в одиночестве. Аналогично, для k задач: Модель параллельных вычислений на основе ГПД Распределение задач по процессорам
Каждая задача должна работать на каком-либо из процессоров. Отсюда, распределение задач по процессором определяется функцией Kn (конфигурацией):
где V = { v1, v2, … vM } – набор задач параллельного алгоритма, P = { P1, P2, … PN } – набор процессоров параллельной вычислительной системы. Таким образом мощность множества всех конфигураций K: Обозначим множество задач, распределенных на процессор Pj как: Уточнение модели ГПД Преобразования и требования к графу потоков данных: Связный; Конечный;
Кратные однонаправленные дуги объединяются, сумма потоков объединяемых дуг приписывается эквивалентной дуге; Петли не будут учитываться и удаляются, т. к. замыкание задачи саму на себя можно интерпретировать как часть внутреннего алгоритма задачи.
Таким образом, получаем конечный связный ориентированный граф без кратных дуг и петель, т. е. простой орграф: G(V, U) ГПД параллельного алгоритма, V = { v1, v2, … vM } множество вершин-задач, U = { ukl} множество дуг-каналов обмена данных.
Теперь можно определить матрицу потоков ГПД следующим образом:
Следующие равенства определяют корректность задания графа потоков данных в данной модели:
где sl и qk– суммарный входной и выходной поток для каждой вершины ГПД;
постоянные матрицы – A , нормированая по строкам, и B, нормированая по столбцам, -задают отношения величин входных и выходных потоков каждой задачи:
коэффициент обработки sk задачи vk задаётся следующим равенством: Постановка задачи оптимизации Существуют следующие ограничения:
ограничение на пропускную способность сети, где W – множество дуг, соединяющих те задачи, которые в данной конфигурации распределены на разные процессоры;
- неравенство для загруженности процессора Pj, где sk – суммарный входной поток, xk – максимальный суммарный входной поток, который может обрабатывать задача vk, работая на процессоре Pj в одиночестве. Величина xk является постоянной для "j, т. к. в модели вычислительной среды все процессоры идентичны. С данными ограничениями оптимизация осуществляется на дискретном множестве конфигураций K, нужно найти конфигурацию, для которой максимизируется суммарная загруженность p вычислительной системы: где pj – загруженность процессора Pj. Отсюда формула для максимизации функционала качества D(Kn) выглядит следующим образом:
Утверждение. Матрица потоков F ГПД при любом распределении задач Kn представима в виде: где Fo –любая матрица потоков удовлетворяющая определению данного ГПД, g - скаляр, больший нуля. Доказательство. Следует из определения ГПД.
Пусть Fo нормирована так, что сумма всех её элементов равна единице. Тогда будет g равно суммарному потоку в ГПД. Входные потоки задач sk выражаются через базовые потоки как:
Таким образом, функционал качества D(Kn) записывается следующим образом:
Задача оптимизации эквивалентна максимизации скалярного коэффициента g, при ограничениях: или
где ek – является постоянной величиной, характеризующая сложность задачи vk. Суммарный поток g будет равняться минимальному из этих двух ограничений, так как больше он ничем не сдерживается. Отсюда следует, что задача оптимизации сводится к двум критериям:
По первой формуле, требуется как можно более равномерно распределить вычислительную нагрузку по процессорам вычислительной системы. Вторая говорит о том, что при этом следует минимизировать поток по сети, т. е. межпроцессорный обмен данных. 5. 4. Учёт фоновой загруженности процессоров
Фоновая загруженность процессора означает, что помимо нашего ПВП на процессорах могут работать и другие вычислительные и другого рода процессы. Фоновая загруженность (background load) поддаётся измерению, и её можно представить числом pjb, 0 Ј pjb < 1. Тогда неравенства (5. 9) принимают вид: и, соответственно, критерий (5. 16) aj – ни что иное, как цена процессора Pj. 5. 5. Регулирование процента загрузки системы
Если требуется не загружать систему как можно более полно только для выполнения нашего ПВП, а выделить под него только часть процессорных ресурсов, то можно принять в качестве предельно допустимого процента загрузки процессора число pja, 0 < pja Ј 1. Регулирование имеет смысл проводить, если для какого-то jo выполняется: то есть, наблюдается превышение предела загрузки хотя бы одного из процессоров. Тогда регулирование должно привести к такой ситуации: и при этом для jo, соответствующего максимально загруженному процессору, будет выполняться:
Это достигается снижением потока g в m раз, где m вычисляется как:
где g' – будет новый суммарный поток, а m - управление потоком. Алгоритмы оптимизации
Алгоритмы поиска оптимальной конфигурации или оптимального распределения задач по процессорам, будем называть алгоритмами распределения. Сначала приводятся статические алгоритмы распределения, для которых должны быть известны или эвристически заданы начальные параметры ГПД, такие как сложности задач ek и матрица потоков Fo. Статические алгоритмы могут использоваться для осуществоения начального распределения задач. Каждый алгоритм имеет свою специфику по сравнению с другими: в одних делается упор на первый из критерием эффективности – балансировка нагрузки между процессорами, в других на второй - минимизация потока в сети, или же на оба критерия сразу. На основе некоторых статических алгоритмов выводятся алгоритмы динамической корректировки распределения задач с учетом изменяющейся статистики потоков данных, загруженностей задач и процессоров, и т. п. Загруженность процессора вычисляется как сумма сложностей задач, распределенных на данный процессор. Во всех алгоритмах предполагается, что количество задач превышает количество процессоров, т. е. M > N. Для алгоритмов, в которых используются значения потоков в ГПД, необходимо преобразовать ГПД в неориентированный, когда дуги превращаются в рёбра. Кратные рёбра между парами вершин, если таковые имеются, объединяются, причём значения потоков суммируются. Это преобразование делается потому, что направление потоков данных между задачами безразлично – важно только его суммарное значение. На основе минимаксного критерия
Страницы: 1, 2, 3, 4
