В качестве простого примера декомпозиции данных, рассмотрим сложение
двух векторов: A[1..N] и B[1..N], в результате чего получится
вектор C[1..N]. Если предположить, что над этой задачей работает
P процессов, разбиение данных приведет к распределению N/P элементов
каждого вектора для каждого процесса, который вычисляет соответствующие
N/P элементы результирующего вектора. Такое распределение данных может
быть сделано либо "статически", когда каждый процесс "априори"
знает (по крайней мере, в терминах переменных N и P) свою долю рабочей
нагрузки, либо "динамически", когда контролирующий процесс (т.е.
ведущий процесс) распределяет подблоки рабочей нагрузки для процессов
- как и когда они освободятся. Принципиальная разница между этими
двумя подходами - это "диспетчеризация". При статической диспетчеризации,
индивидуальная рабочая нагрузка процесса фиксирована; при динамической
диспетчеризации, она варьирует в зависимости от состояния вычислительного
процесса. В большинстве мультипроцессорных сред статическая диспетчеризация
эффективна для таких задач, как пример сложения векторов; однако в
обобщенной среде ПВМ статическая диспетчеризация не столь необходима.
Смысл заключается в том, что среды ПВМ, базирующиеся на сетевых кластерах,
восприимчивы к внешним воздействиям; поэтому статически диспетчеризированные
задачи с разделенными данными могут конфликтовать с одним или более
процессами, которые реализуют свою порцию рабочей нагрузки намного
быстрее или намного медленнее, чем другие. Эта ситуация может также
возникнуть когда машины в системе ПВМ гетерогенны, обладают различными
скоростями ЦПУ, различной памятью и прочими системными атрибутами.
При реальном исполнении даже упомянутой тривиальной задачи сложения
векторов, проявляется, что ввод и вывод не могут быть проигнорированы.
Другими словами, как заставить описанные выше процессы принять свою
рабочую нагрузку и что им делать с результирующим вектором? Ответ
на этот вопрос зависит от самого приложения и обстоятельств его частичного
выполнения, но в общем можно сказать:
Индивидуальные процессы генерируют свои собственные данные внутренне,
например, используя генераторы случайных чисел или статически заданные
величины. Это возможно только в очень специфических ситуациях или
применяется в целях тестирования.
Индивидуальные процессы независимо вводят подмножества своих данных
из внешних устройств. Такой метод является значащим во многих случаях,
но возможен только при поддержке услуг параллельного ввода/вывода.
Контролирующий процесс посылает индивидуальные подмножества данных
каждому процессу. Это наиболее обобщенный сценарий, особенно полезный
при отсутствии услуг параллельного ввода/вывода. Кроме того, этот
метод также применим при вводе подмножеств данных, полученных при
предыдущих вычислениях, относящихся к данному приложению.
Третий метод распределения индивидуальной рабочей нагрузки также придерживается
динамической диспетчеризации для приложений, в которых межпроцессные
взаимодействия в процессе вычислений редки или не существуют вообще.
Однако, нетривиальные алгоритмы обычно требуют непосредственных обменов
значениями данных и поэтому только изначальное назначение порций данных
удовлетворяет таким схемам. Например, рассмотрим метод разбиения данных,
изображенный на рис. 4.2. Чтобы умножить две матрицы A и B, в первую
очередь порождается группа процессов - согласно парадигме "ведущий-ведомый"
или "только станции". Этот набор процессов предназначен для
формирования петли. Каждая подматрица матриц A и B помещается в соответствующий
процесс, с помощью одной декомпозиции данных и одной из перечисленных
выше стратегий распределения рабочей нагрузки. В процессе вычисления,
подматрицы требуют передачи или обмена между процессами, тем самым,
преобразуя оригинальную карту распределения, как показано на рисунке.
В конце вычисления, однако, подматрицы результирующей матрицы "разбросаны"
по индивидуальным процессам в соответствие занимаемой позиции в сети
процессов и наполнены данными согласно карте разбиения результирующей
матрицы C. Предшествующая дискуссия показала основы декомпозиции данных.
В следующем разделе будут представлены программы-образцы, выдвигающие
на передний план подробности этого подхода.
Знаете ли Вы, что математическое программирование - это (1) раздел математики, исследующий методы решения задач отыскания экстремума на заданном множестве допустимых значений переменных; (2) формализм, используемый для представления знаний о структуре моделируемых объектов в форме задачи отыскания экстремума на заданном множестве допустимых значений переменных.
