Естественный параллелизм алгоритмов
При рассмотрении стилей программирования выяснилось, что зачастую линейный порядок исполнения операторов программы навязывается ей извне и служит лишь подпоркой, необходимой для реализации в конкретной системе.
Обратимся к классическим примерам, когда вычислительный алгоритм хорошо распараллеливается.
Пример 15.1.1. Умножение матриц - это случай, на котором достаточно широкие массы программистов и заказчиков вычислительных программ осознали потенциальную выгодность распараллеливания. Если разбить матрицу произведения k*m x l*n на подматрицы размера m x n, то для вычисления каждой такой подматрицы достаточно иметь m строк первого сомножителя и n столбцов второго. Разделив вычисления по независимым процессорам, мы можем ценой некоторого дублирования исходных данных значительно быстрее получить результат.
Аналогично распараллеливается задача решения системы линейных уравнений.
Пример 15.1.2. Пусть задача представляется как совокупность нескольких взаимодействующих автоматов (таким образом, в принципе она укладывается в рамки автоматного программирования, но единая система структурируется на подсистемы, и большинство действий работают внутри подсистем). Тогда у нас возникает естественный параллелизм.
Таковы многие игровые задачи, в которых задействовано несколько персонажей, таково же и большинство задач синтаксического разбора.
Уже на этих двух примерах видно, что имеются принципиально различные случаи. В первом примере задачи индифферентны по отношению к тому, как будет вычисляться результат. В таком случае мы используем для распараллеливания свойства конкретного алгоритма вычислений, который имеет множество потенциально подходящих для реализации информационных взаимосвязей в соответствующей сети данных вычислительных структур (последовательная обязательно находится среди них).
Во втором примере параллелизм естественно диктуется самой задачей, поскольку система распадается на подсистемы. Надеюсь, у Вас не вызывает удивления то, что в данном случае естественное с теоретической точки зрения решение оказывается практически почти никогда не реализуемым. Нынешние параллельные системы имеют фиксированное (как правило, небольшое) число процессоров, если же процессоров много, то они завязаны в жесткую структуру. Поэтому задачи с естественным параллелизмом очень редко помещаются в прокрустово ложе такой системы. Гораздо легче запихнуть туда то, что не является параллельным по природе, но может быть распараллелено, поскольку в этом случае структуру реализации алгоритма можно подогнать к требованиям конкретной системы.
Таким образом, основная беда параллелизма состоит в том, что программирование и архитектура машин вступают в концептуальное противоречие.
В жизни каждый из Вас встречался с простейшим видом параллелизма: длительный и относительно автономный процесс печати запускается, как правило, параллельно с выполнением других программ. Случай, когда Вы одновременно запустили несколько программ, как правило, настоящим параллелизмом не является (это рассматривается чуть ниже).
