Матричное умножение в ПВМ. Параллельная виртуальная машина, PVM

В следующем примере программируется алгоритм матричного умножения, предложенный Фоксом (Fox)[8]. Программа mmult может быть найдена в конце данного подраздела. Программа mmult будет вычислять

, где

- все квадратные матрицы. С целью упрощения, предполагается, что для вычисления результата будут использоваться $m\times m$ задач. Каждая задача будет вычислять подблок результирующей матрицы

. Размер блока и значение

передаются программе как аргументы командной строки. Матрицы

также устанавливаются в виде блоков, распределенных в среде из $m^{2}$ задач. Перед тем, как начать "копаться" в программных деталях, позвольте сначала описать алгоритм на высоком уровне.

Предположим, что существует "сеть" из $m\times m$ задач. Каждая из задач ( $t_{i,j}$ , где $0\leq i,j<m$ ) первоначально содержит блоки $C_{i,j}$ , $A_{i,j}$ и $B_{i,j}$ . Первым шагом алгоритма, задачи, расположенные по диагонали ( $t_{i,j}$ , где

), передают свои блоки $A_{i,i}$ всем остальным задачам в строке

. После передачи $A_{i,i}$ , каждая из задач вычисляет $A_{i,i}\times B_{i,j}$ и добавляет результат к $C_{i,j}$ . Следующим шагом, блоки

поворачиваются по столбцам. Так, задача $t_{i,j}$ передает свой блок

задаче $t_{i-1,j}$ (задача $t_{0,j}$ передает свой блок

задаче $t_{m-1,j}$ ). Затем задачи возвращаются к первому шагу: $A_{i,i+1}$ широковещательно передается всем другим задачам в строке

- алгоритм продолжается. После

итераций матрица

будет содержать $A\times B$ , а матрица

вернется к исходному состоянию.

В ПВМ не накладывается ограничений на то, как задача может связываться с любой другой задачей. Однако, для данной программы, хотелось бы представлять задачи в виде двумерной модели тора. Чтобы учесть задачи, каждая из них включается в группу mmult. Групповые идентификаторы используются для отображения задач на наш тор. При включении в группу первой задачи она получает групповой идентификатор 0. В программе mmult, задача с нулевым групповым идентификатором порождает остальные задачи и передает параметры матричного умножения этим задачам. Такими параметрами являются m и bklsize - квадратный корень числа блоков и размер блока соответственно. После того, как все задачи порождены, а параметры переданы, вызывается pvm_barrier() - для того, чтобы удостовериться, что все задачи присоединились к группе. Если барьер не организован, то последующий вызов pvm_gettid() может завершиться ненормально, т.к. некоторая задача к тому моменту может быть еще не в составе группы.

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

, который будет вычисляться. Это основывается на значениях групповых идентификаторов - в диапазоне от

до

включительно. Так, если допустить построчное отображение групповых идентификаторов задач, целочисленное деление даст строку задач, а mygid mod m - даст столбец. С использованием подобного отображения определяется групповой идентификатор задачи, расположенной непосредственно "выше" или "ниже" в торе, и сохраняется соответственно в up и down.

Далее блоки инициализируются вызовом InitBlock(). Эта функция просто инициализирует

случайными числами,

- идентичной матрицей, а

-нулями. Это позволит нам верифицировать вычисление в конце программы простой проверкой равенства

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

другим задачам в своих строках. Отметим, что массив myrow в действительности содержит идентификаторы задач, выполняющих широковещательные передачи. При повторных вызовах pvm_mcast() сообщения будут передаваться всем задачам из массива, исключая делающую вызов задачу. Для задач mmult эта процедура великолепно срабатывает - чтобы напрасно не обрабатывать "лишнее" сообщение, поступающие самой широковещательно передающей задаче при "лишнем" pvm_recv(). Как широковещательно передающая задача, так и задачи, принимающие блок, вычисляют $A\times B$ с использованием и диагонального блока

и блоков

, принадлежащих задачам.

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

, вертикально сдвигаются блоки

. Особенным образом блок

упаковывается в сообщение, передается задаче с идентификатором задачи up и, затем, принимается новый блок

от задачи с идентификатором задачи down.

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

и блоков

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

Как только вычисление завершено, проверяется

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

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

В вызове pvm_lvgroup() нет необходимости, поскольку ПВМ выгрузит отработавшие задачи и удалит их из группы. Однако, хорошим тоном является "явный" выход из группы перед вызовом pvm_exit(). Команда консоли ПВМ reset "сбросит" все группы ПВМ. Команда pvm_gstat выведет на экран статус любой из существующих групп.

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