Управляющий-рабочие (распределенный портфель задач)

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

Глава 9. Модели взаимодействия процессов                                                                    329

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

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

9.1.1. Умножение разреженных матриц

Пусть А и В — матрицы размером n x п. Нужно определить произведение матриц А х в = С. Для этого необходимо вычислить п2 скалярных произведений векторов (сумм, образованных произведениями соответствующих элементов двух векторов длины п).

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

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

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

Разреженная матрица А представляется информацией о ее строках:

int lengthA[n]; pair *elementsA[n];

Значение lengthAfi] является числом ненулевых элементов в строке i матрицы А. Пере­менная elementsAfi] указывает на список ненулевых элементов строки 1. Каждый элемент представлен парой значений (записью): целочисленным индексом столбца и значением соот­ветствующего элемента матрицы (числом удвоенной точности). Таким образом, если значе­ние lengthAfi] равно 3, то в списке elementsAfi] есть три пары. Они упорядочены по возрастанию индексов столбцов. Рассмотрим конкретный пример. lengthA elementsA



1             (3,   2.5) О

О

2             (1,   -1.5)      (4,   0.6) О

1           (0,   3.4)

Здесь записана матрица размерами 6 на б, в которой есть четыре ненулевых элемента: в стро­ке 0 и столбце 3, в строке 3 и столбце 1, в строке 3 и столбце 4, в строке 5 и столбце 0.

Матрицу с представим так же, как и А. Чтобы упростить умножение, представим матрицу в не строками, а столбцами. Тогда значения в lengths будут указывать число ненулевых элементов в каждом столбце матрицы в, а в elementsB — храниться пары вида (номер стро­ки, значение элемента).



330                                                                            Часть 2. Распределенное программирование

Для вычисления произведения матриц а и в, как обычно, нужно просмотреть п2 пар строк и столбцов. Для разреженных матриц самый подходящий объем задачи соответствует одной строке результирующей матрицы с, поскольку вся эта строка представляется одним вектором пар (столбец, значение). Таким образом, нужно столько задач, сколько строк в мат­рице А. (Очевидно, что для оптимизации можно пропускать строки матрицы А, полностью состоящие из нулей, т.е. строки, для которых lengthA [ i ] равно 0, поскольку соответствующие строки матрицы С тоже будут нулевыми. Но в реальных задачах это встречается редко.)

В листинге 9.1 показан код, реализующий умножение разреженных матриц с помощью одного управляющего и нескольких рабочих процессов. Предполагается, что матрица А в управляющем процессе уже инициализирована, а у каждого рабочего есть инициализиро­ванная копия матрицы в. Процессы взаимодействуют с помощью примитивов рандеву (см. главу 8), что упрощает программу. Для использования асинхронной передачи сообщений управляющий процесс должен быть запрограммирован в стиле активного монитора (см. раз­дел 7.3), а вызовы call в рабочих процессах нужно заменить вызовами send и receive.





332                                                                            Часть 2. Распределенное программирование

фала функции f (х) на интервале от а до Ь. В разделе 3.6 было показано, как реализовать адаптивную квадратуру с помощью разделяемого портфеля задач.

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


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

В листинге 9.2 приведен код управляющего и рабочих процессов. Поскольку управляю­щий процесс, по существу, является серверным, для его взаимодействия с рабочими процес­сами здесь также используются рандеву. Таким образом, управляющий процесс имеет ту же структуру, что и в листинге 9.1, а, и также экспортирует операции getTask и putResult, но параметры операций отличаются. Теперь задача определяется конечными точками интервала (переменные left и right), а результатом вычислений является площадь под графиком f (х) на этом интервале. Предполагается, что значения переменных а, Ь и numlntervals заданы, например, как аргументы командной строки. По этим значениям управляющий про­цесс вычисляет ширину интервалов. Затем он выполняет цикл, принимая вызовы операций getTask и putTask, пока не получит по одному результату вычислений для каждого интер­вала (каждой задачи). Отметим использование условия синхронизации "st x< Ь" в ветви ••для операции getTask оператора ввода— оно предохраняет операцию getTask от выдачи следующей задачи, когда портфель задач уже пуст.





Рабочие процессы в листинге 9.2 разделяют или имеют собственные копии кода функций f и quad (рекурсивная функция quad приведена в разделе 1.5). Рабочий процесс циклически получает задачу от управляющего, вычисляет необходимые для функции quad аргументы, вызывает ее для аппроксимации значения площади под графиком функции от f (left) до f (right), а затем отсылает результат управляющему процессу.

Когда программа в листинге 9.2 завершается, рабочие процессы блокируются в своих вы­зовах функции getTask. Обычно это безопасно, как и здесь, но в некоторых случаях этот способ завершения выполнения рабочих процессов может привести к зависанию. Задача реа­лизации нормального завершения рабочих процессов оставляется читателю. (Указание. Из­мените функцию getTask, чтобы она возвращала true или false.)

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


Содержание раздела

---