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

    Попарные взаимодействия.

В данном примере используется похожая структура ГПД как в примере с конечными разностями, но требуется более сложный алгоритм обмена данных. Многие задачи требуют вычисление всех N(N-1) попарных взаимодействий I (Xi, Xj) между N векторами Xo, X1, …XN-1. В случае, когда взаимодействия симметричны, I (Xi, Xj) = ± I (Xi, Xj), и требуется вычислить только N(N-1) / 2 взаимодействий. Например, в молекулярной динамике требуется вычислить суммарный вектор сил воздействующих на атом Xi, определённый как:

F(Xi, Xj) означает взаимное притяжение или отталкивание между атомами Xi и Xj; в данном случае, F (Xi, Xj) = - F (Xi, Xj), взаимодействия симметричны. Простой параллельный алгоритм для общей задачи попарных взаимодействий состоит из N задач. Задача i получает значение Xi и вычисляет набор i № j . Сначала можно подумать, так как задача требует информацию от каждой другой задачи, для этого должно быть создано N(N-1) каналов. Однако, более экономичная структура ГПД использует только N каналов. Они соединяют все задачи в однонаправленное кольцо, так что каждая задача имеет по одному входному и выходному порту. Каждая задача сначала инициализирует буфер (для хранения локальной переменной) и аккуммулятор, в котором будет содержаться результат вычислений. Затем задача периодически: посылает значение из буфера в свой выходной порт;

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

Этот цикл посылки-приёма-вычисления повторяется N-1 раз, осуществляя перемещение по кольцу всех N значений Xi. Каждая задача видит их всех и способна вычислить все N-1 взаимодействия. Алгоритм выполняет N-1 операцию на каждую задачу. Если взаимодействия симметричны, то можно уменьшить в два раза количество вычислений и обменов данных путём улучшения структуры ГПД. Предположим для простоты, что N четно. Добавляется дополнительные N каналов, соединяющих каждую задачу с задачей, расположенной через [N / 2] по кольцу. Каждый раз, когда вычисляется I (Xi, Xj) между локальным Xi и принятым Xj, вычисленное значение не только суммируется в аккумуляторе для Xi, но и в другом аккумуляторе, который является противоположным с Xj. После [N / 2] итераций аккумуляторы, ассоциированные со своими противоположными значениями, возвратятся в свои начальные задачи через новые каналы и обхединятся с локальными аккумуляторами. Следовательно, каждое симметричное взаимодействие вычислится только раз: либо как I (Xi, Xj) на вершине содержащей Xi, либо I (Xj, Xi) на вершине содержащей Xj.

    Параметрическое исследование

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

Если время выполнения одинаково и процессоры идентичны, то достаточно разпределить задачи по ровну на каждый процессор. В другой ситуации, можно выбрать структуру ГПД показанную на рисунке. Задачи I (входная) и O (выходная) должны считывать и записывать входной и выходной файл, соответственно. Каждая рабочая задача W периодически запрашивает значения параметров от задачи I, вычисляет используя их, а затем отсылает результаты задаче O. Так как время выполнения варьируется, входная и выходная задачи не могут расчитвать на правильный порядок поступления сообщений от рабочих задач. Используется соединение типа много-к-одному. Возможный в этом случае недетерминизм влияет всего лишь на порядок записи результатов в выходной файл, но не на сами вычисляемые результаты. Входная задача посылает следующий набор параметров после того как получит запрос от рабочей задачи. В это время рабочая задача просто ждёт поступления входных данных. Поэтому, иногда эффективность можно улучшить с помощью раннего запроса, когда следующий набор параметров запрашивается до того как они потребуются.

    В данной работе

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

    Постановка задачи
    Модель вычислительной среды
    Задан набор идентичных процессоров:
    P = { P1, P2, … PN }

Между любыми процессорами Pi и Pj (i № j) существует общий канал связи. Если объем передаваемых данных в единицу времени между Pi и Pj равен fij, тогда ограничение на пропускную способность сети выражается как: , где fij – максимальная пропускная способность сети.

    Модель вычислительной задачи

Под вычислительной задачей понимается последовательная программа, которая может выполняться на любом из процессоров сети. Она реализует какую-либо фиксированную операцию: вычислительный процесс, загрузку данных, вывод на экран и т. п. Назовем эту программу задачей. Задача z имеет наборы входных и выходных портов, посредством которых она получает входные данные и выдает результаты своей работы, соответственно. Задача может не иметь входных портов, когда она является стартовой. При этом она должна иметь хотя бы один выходной порт. Но обратное неверно – признак стартовой задачи может иметь и задача с входными портами. А если задача не имеет выходных портов, то она является завершающей или замыкающей. При этом она должна иметь хотя бы один входной порт. Стартовые задачи обычно осуществляют загрузку входных данных из файлов или запрашивая их у пользователя, либо самостоятельно генерируя их. Замыкающие задачи, как правило сохраняют результаты работы параллельного алгоритма в файл или выводят их на экран. Но, вообще, содержание задач не играет большой роли в данной модели, – это предоставляется решать программисту параллельного алгоритма. Роль генераторов данных и интерпретации результатов может выполнять любая из задач. В программе обязательно должна быть хотя бы одна стартовая задача, но может совсем не быть замыкающих. Параллельный алгоритм завершается, если завершены все задачи, помеченые признаком стартовая. С другой стороны завершить выполнение параллельного алгоритма можно прерыванием выполнения всех задач.

Входные и выходные данные представляются порциями определенного размера. Рассмотрим задачу с несколькими входными и выходными портами. Схематическое изображение задачи показано на рисунке. В момент, когда поступают порции данных во все входные порты, задача приступает к их обработке. Пусть это будет какой-то вычислительный процесс. После окончания вычислений, их результаты направляются в соответствующие выходные порты, также в виде порций данных определенного размера. Процесс обработки данных в задаче должен быть периодическим. Т. е. после обработки очередной порции данных задача ожидает следующей. При этом во время этого ожидания процессорное время данной задачей не используется. Рассмотрим математические соотношения для модели простой вычислительной задачи – с единственным входным и выходным портом. Пусть входные порции данных поступают в моменты времени { ti } и имеют объем в байтах { Mi }, i = 0, 1, 2, …. Время обработки i -той порции данных ti. Последовательность { qi } представляет собой интервалы поступления входных данных. Заметим, что так как в модели предполагается, что данные не могут накапливаться во входном буфере, и это соответствует реальному программному механизму передачи данных. Подробнее, это значит, что скорость выдачи данных задачей генератором будет равняться скорости обработки данных задачей приемником. Задача генератор может приступить к выдаче очередной порции данных до того момента, как задача приемник запросит входные данные. В этом случае протокол обмена данных затормозит выдачу, а этим и саму задачу генератор, т. к. операция посылки данных в порт является блокирующей. Временная диаграмма процесса поступления и обработки данных показана на рисунке. Процесс обмена по каналу данных характеризуется скоростью обмена или потоком F, который определяется следующими соотношениями:

, где Fi – мгновенный поток в момент времени ti, F – средний поток на интервале [t0, tk);

, где Fmax – средний максимальный поток, который может обрабатывать задача при текущем времени обработки ti. Эффективность работы задачи при заданном входном потоке определяется отношением чистого времени вычислений ко всему времени работы: где t – чистое время вычислений, q – интервал работы задачи; таким образом, (q - t) – время простоя задачи,

где e – эффективность работы задачи на интервале времени [t0, tk). Существует прямо-пропорциональная зависимость между входным и выходным потоками задачи. Это следует из характера обработки данных – на каждую порцию входных данных вычисляется порция выходных, определенного размера. Если Ni – размер i-той порции выходных данных, тогда:

где Fout – средний выходной поток за время q. Следовательно, коэффициент обработки стремится к следующему среднему значению s при q®µ:

Коэффициент s является постоянным для данной задачи, при фиксированных размерах входных и выходных порций данных, т. е. Mi=Mj и Ni=Nj для "i№j.

Как видно из (2. 2) период поступления данных не может превышать периода их обработки, поэтому входной поток F ограничен максимальным потоком Fmax. Из пропорциональности выходного потока входному следует, что и выходной ограничен:

где 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. Данное определение ГПД не делает ограничений на наличие кратных дуг и петель. Т. е. две задачи могут быть связаны несколькими однонаправленными каналами. А также канал может соединять собой выходной и входной порт одной и той же задачи. Ниже будет осуществляться переход к более удобному для анализа представлению ГПД.

    Характеристики параллельных вычислительных процессов (ПВП)

Страницы: 1, 2, 3