Основы объектно-ориентированного проектирования

         

Полное использование параллелизма оборудования


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

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

Рассмотрим сначала набросок класса, без параллелизма:

class BINARY_TREE [G] feature left, right: BINARY_TREE [G] ... Другие компоненты ... nodes: INTEGER is -- Число вершин в данном дереве do Result := node_count (left) + node_count (right) + 1 end feature {NONE} node_count (b: BINARY_TREE [G]): INTEGER is -- Число вершин в b do if b /= Void then Result := b.nodes end end end

Функция nodes использует рекурсию для вычисления числа вершин в дереве. Эта косвенная рекурсия проходит через вызовы node_count.

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

separate class BINARY_TREE1 [G] feature left, right: BINARY_TREE1 [G] ... Другие компоненты ... nodes: INTEGER update_nodes is -- Модифицировать nodes, подсчитав число вершин дерева do nodes := 1 compute_nodes (left); compute_nodes (right) adjust_nodes (left); adjust_nodes (right) end feature {NONE} compute_nodes (b: BINARY_TREE1 [G]) is -- Модифицировать информацию о числе вершин в b do if b /= Void then b.update_nodes end end adjust_nodes (b: BINARY_TREE1 [G]) is -- Добавить число вершин в b do if b /= Void then nodes := nodes + b.nodes end end end

В этом случае рекурсивные вызовы compute_nodes будут запускаться параллельно.
Операция сложения будет ждать, пока не завершатся два параллельных вычисления.

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

Наличие двух проверок пустоты b может показаться неприятным. Однако это требуется для отделения распараллеливаемой части - вызовы процедур, запускаемых параллельно на left и right, - от сложений, которые по своему смыслу должны ждать готовности своих операндов.
В этом решении привлекает то, что все проблемы, связанные с назначением конкретных компьютеров, полностью игнорируются. Программа занимает процессоры по мере необходимости. Это происходит в не приведенных здесь командах создания, появляющихся, в частности, в процедуре вставки. Для вставки нового элемента в бинарное дерево создается вершина вызовом create new_node.make (new_element). Поскольку new_node имеет сепаратный тип BINARY_TREE1[G], для нее выделяется процессор. Связывание этих виртуальных процессоров с доступными физическими ресурсами происходит автоматически.


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