Уровни параллелизма

Уровни параллелизма, вносимого структурными способами в работу ЭВМ или, в общем случае – вычислительных систем, могут быть различными. Так, физическое представление вычислительных систем позволяет говорить о распараллеливании вычислительного процесса на уровне отдельных ЭВМ, устройств, блоков и узлов.

Логическое представление вычислительных систем позволяет говорить о параллелизме на уровне задач, команд либо данных.

При организации параллельной обработки на этих уровнях можно выделить три основных направления.

Первое направление связано с совмещением во времени различных этапов разных задач. Подобное совмещение возможно даже в однопроцессорных ЭВМ в режиме многопрограммной обработки и широко используется в настоящее время.

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

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

Если в вычислительную систему поступает непрерывный поток не связанных по данным задач, то налицо естественный параллелизм независимых задач. Частным случаем естественного параллелизма выступает параллелизм объектов или данных. Он имеет место тогда, когда по одной и той же программе обрабатывается некоторая совокупность данных о различных, но однотипных объектах, поступающая на обработку одновременно. Такие задачи сводятся к операциям над многомерными векторами, матрицами и аналогичными объектами. Операции над объектами могут выполняться параллельно и независимо друг от друга. В этом случае считается, что задача сама по себе обладает естественным параллелизмом.

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

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