Полное использование параллелизма оборудования
Следующий пример иллюстрирует, как использовать ожидание по необходимости для извлечения максимальной пользы от параллелизма в оборудовании. Он показывает изощренную форму балансировки загрузки компьютеров в сети. Благодаря понятию процессора, можно опереться на механизм параллельности для автоматического выбора компьютеров.
Сам этот пример - вычисление числа вершин бинарного дерева - имеет небольшое практическое значение, но иллюстрирует общую схему, которая может быть чрезвычайно полезна для больших, сложных вычислений, встречающихся в криптографии или в машинной графике, для которых разработчикам нужны все доступные ресурсы, но не хочется вручную заниматься назначением абстрактных вычислительных единиц реальным компьютерам.
Рассмотрим сначала набросок класса, без параллелизма:
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, - от сложений, которые по своему смыслу должны ждать готовности своих операндов. |
