Вспомним Ежи Леца – юмор у него довольно чёрный, но ведь автору и нам с Вами было бы много приятнее знать заранее, что параллельные вычисления возможны, чем противоположное!.. Ну ежели невозможны – ну так и невозможны… а самая возможность выполнимости подхлёстывает и “зовёт к работе”.
Возможно ли (хотя бы теоретически) распараллелить любой алгоритм?
Тут придётся сделать мысленный эксперимент, но несложный. Зададимся вот каким вопросом - до какой степени допусти́мо распараллелить заданный формулой алгоритм любой сложности? Ведь говорят же учёные, что существует два подхода к науке – можно подходить с априорным разрешении “делать всё что можно”, а можно с запретом “всего что нельзя”...
Кстати, какой подход будет более эффективным (по Вашему мнению)?
Однако можно доказать утверждение, состоящее в том, что возможно построить машину (разумеется, гипотетическую), которая любой заданный алгоритм будет обрабатывать максимально (полностью) параллельно. Будем рассматривать, например, формулу r=a+b/c фактически задающую преобразование чисел a,b,c в некоторое другое число r без конкретизации методов этого преобразования. Если a,b,c,r заданы в двоичном коде (это не ограничивает дальнейшие рассуждения), то возможно построить такое логическое устройство, на вход которого поступает любая допустимая битовая комбинация a,b,c, а на выходе должна появиться соответствующая результату r комбинация битов (миниатюра ниже).
Согласно алгебре логики для любой функции можно построить т.н. дизъюнктивную нормальную форму, тогда i-й двоичный разряд результата r будет рассматриваться как логическая функция ri для каждого бита результата ri=ri(a1…an, b1…bn, c1…cn), где i=1-n. Казалось бы, вопрос решён – для любого (сколь угодно сложного) арифметического выражения можно построить электронную схему (пусть тоже очень сложную, пример на миниатюре справа), позволяющую выполнять нужное преобразование, причём именно за один такт работы (фактически каждый бит операндов преобразуется в соответствующий по разряду бит результата полностью параллельно)! Разобранный пример соответствует битовому уровню параллелизма и приведён в книге Королёва Л.Н. “Структуры ЭВМ и их математическое обеспечение”. Замечу, что книга объективно хороша́ (независимо от времени выпуска) и ознакомиться с ней “во все времена полезно”.
Проблема в том, что число выражений, которые необходимо преобразовывать таким образом (т.е. распараллелить), практически бесконечно, и поэтому строить отдельное электронное устройство для каждого такого преобразования малоосмысленно. Однако в некоторых случаях (когда необходимо очень быстро многократно совершать несложные действия по преобразованию данных) описанный подход вполне применим (напр., спецпроцессоры для БПФ - Быстрого Преобразования Фурье). Давно реализованная Природой идея о предваряющей обработку данных настройке на конкретный метод обработки хороша и реализуется, однако весьма сложна как логически так и технически. Природа создаёт множество как узкоспециализированных (иногда неизменяющихся многие миллионы лет) существ, так и обладающих большой гибкостью организмов.
Кстати, сможете привести пример таких (как бы замерших в развитии на миллионы лет) существ?
Слова о максимально возможном распараллеливании вполне оправданы – бит является минимальной единицей представления информации. Правда, при имеющихся ограничениях на функциональность имеющихся в наличии логических элементов в некоторых случаях всё же требуется нескольких последовательных этапов вычислений; их число определяется теоремой (леммой) Брента (см. миниатюру ниже). Кстати, рад лицезреть (очередную) компиляцию моей “методички” аж 2006 г. (http://vbakanov.ru/metods/1441/parr.pdf - вспомнил серию изображений, над ко́ими трудился в те времена́) под эгидой Ша́хтинского института (филиал) ЮРГТУ (НПИ), изд. Шахты-2010. Т.о. можно сказать, что подавляющее большинство архитектур параллельных вычислительных систем являются компромиссом между скоростью обработки чисел и гибкостью этой обработки.
Теорема Брента утверждает, что при моделировании работы схемы глубиной d и размером n с ограниченными входными степенями элементов с использованием CREW-алгоритма (модель памяти Concurrent Read, Exclusive Write) - из каждой ячейки памяти в любой момент времени данные могут считываться параллельно любыми процессорами, но записываться только одним процессором) на р процессорах достаточно (т.е. не выше) времени O(n/p+d). Выражение O(f) говорит, что скорость роста сложности алгоритма ограничена функцией f. На миниатюре выше приведён результат моделирования схемы размером (общее количество процессоров) n=15 при глубине схемы (максимальное число элементов на каждом из уровней глубины) d=5 с числом процессоров p=2 (одновременно моделируемые элементы объединены в группы прямоугольными областями, причём для каждой группы указан шаг, на котором моделируются её элементы; моделирование происходит последовательно сверху вниз в порядке возрастания глубины, на каждой глубине по p штук за раз). Согласно теоремы Брента моделирования такой схемы на CREW-машине займёт не более ceil(15/2+1)=9 шагов.
А как Вы думаете – к какому уровню параллелизма относится параллелизм квантовых компьютеров? Подозреваю, что “an mass” (любимое выражение гр. тов. проф. Выбега́лло – ко́его принято изображать в о́бразе писателя Александра Каза́нцева с “пшено́м в бороде”) в форме би́тового (“ку́бит” ≡ “извращённый бит”) уровня… правда, неприя́тие теоремы Брента привёло к отказу от стати́чности́ решений..!
Так… показали “плюшку” и разбавили кучей проблемных комментариев..! Давайте (для разнообразия) приведём пару (довольно примитивных) примеров, из которых всё же понятно, что параллельные вычисления реальны. Одновременно с этим введём несколько новых обозначений.
Простейшие примеры распараллеливания алгоритмов. “Плюшки” и проблемы
Несмотря на нарочи́тую простоту рис. 3, он представляет собой реальную схему (план, расписание) параллельных вычислений и даже позволяет задать вопросы класса “А что, если?..”. Исходные данные (вектора A и B), хранящиеся в определённой области памяти, посредством линий передачи данных подаются для обработки к параллельным вычислителям, каждый из которых может принимать для обработки данные по двум каналам (принимать два операнда – а так именуются исходные данные для обработки - одновременно или последовательно). Режим работы каждого из 5-ти параллельных вычислителей в данном случае не столь важен (вычислители могут срабатывать по условию доставки обоих операндов на вход каждого или по условию доставки всех операндов всем вычислителям одновременно). Время выполнения операции на каждом из вычислителей определено (и - для современных процессоров - часто равно одному такту тактового генератора вычислительной системы). Результат операции сложения в виде числа (скаляра) появляется на выходе каждого вычислителя и может быть использован в дальнейшем (напр., записан по определённым адресам в память). Все вычислители данного поля могут быть гомогенными (выполнять одинаковый набор операций) или же гетерогенными (в этом случае необходимо наличие некоего диспетчера, направляющего данные согласно коду операции на соответствующий вычислитель).
Ясно, что при 5-ти независимых вычислителях за время одного такта могут быть обработаны не более 5-ти чисел (скаляров). А вот вопросы “что, если”:
- Можно на такой схеме из параллельных вычислителей сложить более 5-ти чисел? Сколько этапов обработки (та́ктов) понадобится для этого?
- А как изменится схема (вычислительный план) при реализации умножения тех же самых векторов на таком же самом числе параллельных вычислителей?
Ответ на первый вопрос несложен – да, можно, но потребуется повторное срабатывание вычислителей (каждое срабатывание даст 5 отдельных элементов результирующего вектора).
Второй вопрос более сложен даже при числе элементов умножаемых векторов более числа параллельных вычислителей. В самом деле, результатом умножения векторов является число (скаляр), равный сумме результатов частичных перемножений элементов векторов, вычислить который можно лишь после получения результата перемножений. Вследствие сказанного даже при сколь угодно большом количестве вычислителей в поле процесс перемножения векторов за один этап (такт) выполнить не удастся.
Итак, при (казалось бы!) незначительном отличии процедуры сложения векторов (рис. 3 а) от их умножения (рис. 3 б) вторая значительно сложнее – это следствие двухэтапного (умножение + сложение) режима работы собственно алгоритма (что на рис. 3 б) показано обратной связью в виде петли по часовой стрелке с выходов на входы вычислителей). Выясняется, что сложение (даже частичное) нельзя производить прежде окончания всех операций умножения! Такие “интересности” параллелизм нам часто преподносит…
Если нельзя перемножить два трёхэлементных векторов на поле из 5-ти параллельных вычислителей за один такт их работы, то, может быть, это удастся сделать на 6-ти? А на 9-ти?
Авторские ресурсы:
- Мой Мир: https://my.mail.ru/mail/e881e/