Параллельное программирование: Учебное пособие, страница 5

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

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

Четвертый раздел описывает одну из свободно распространяемых версий пакета программирования и исполнения параллельных программ для платформ Windows 2000. Приводится порядок действий, которые необходимо выполнить, чтобы параллельная программа была запущена и выполнена.

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

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

1  Суть проблемы и основные понятия

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

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

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