Параллельные методы решения вычислительно-трудоемких задач

Введение

При решении вычислительно трудоемких задач науки и техники обычно возникает проблема эффективной организации вычислений. Некоторые из этих задач характеризуются большой размерностью входных данных и поэтому требуют обработки значительных объемов информации. С другой стороны, многие задачи, связанные, например, с анализом космической информации, мониторингом работы крупных промышленных предприятий, банковских учреждений, характеризуются высокой частотой поступления информации о состоянии исследуемого объекта и требуют принятия оптимальных решений в режиме реального времени. Отметим, что рост размерности входных данных и массовость (многократное выполнение одного и того же фрагмента) вычислений приводят к увеличению сложности решения задач. Поэтому необходимо совершенствовать уже существующие и разрабатывать новые подходы к организации и выполнению вычислений на вычислительных системах высокой производительности [1, 2].
Одним из способов оптимизации процесса вычислительно трудоемких задач является его распараллеливание с целью дальнейшей реализации на системах параллельной архитектуры. Для реализации параллельных методов и алгоритмов используются вычислительные средства универсального и специального назначения. В настоящее время развитие универсальных вычислительных систем осуществляется по следующим основными направлениями [3]: SMP (Symmetric Multi-Processing), MPP (Massively Parallel Processing) и кластеры, типичным примером SMP-систем являются современные многоядерные процессоры фирмы Intel (Core Duo, Core 2Duo и т.д.). Процессоры SMP-систем имеют равноправный доступ к блоку памяти.
1. Понятие о параллельных вычислительных методах

Прежде чем перейти к рассмотрению непосредственно параллельных вычислительных методов решения вычислительно трудоемких задач рассмотрим основные понятия параллельных и распределенных вычислений.
Параллельные вычисления – способ организации компьютерных вычислений, при котором программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно (одновременно). [4]. Данное определение охватывает совокупность вопросов параллелизма в программировании, а также создание эффективно действующих аппаратных реализаций.
Распределенные вычисления - это способ решения трудоемких вычислительных задач с использованием нескольких компьютеров, чаще всего объединенных в параллельную вычислительную систему, в том числе и с помощью обычной локальной вычислительной сети [5]. Распределенные вычисления применимы также в распределенных системах управления.
Иными словами, распределенные вычисления обязательно предусматривают выполнение отдельных частей общей задачи на отдельных процессорах или компьютерах, тем или иным образом соединенных между собой. Параллельные же вычисления могут быть выполнены как на многопроцессорных системах, так и на компьютерах с одиночным процессором, которые выполняясь в режиме разделения времени для отдельных потоков одного процесса.
Но, несмотря на различия, эти два вида вычислений объединяет то обстоятельство, что в обоих случаях общая задача должна быть распараллелена для выполнения в отдельных потоках на одном процессоре или на ансамбле параллельно работающих процессоров.
В настоящее время существуют два основных подхода к распараллеливанию вычислений

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


2. Параллелизм данных и параллелизм задач как методы решения вычислительно трудоемких задач

Векторизация или распараллеливание - распределение того же исполняемого кода по процессорам, в этом случае чаще всего выполняются уже во время трансляции, то есть перевод исходного текста программы в машинные команды [6].
Роль программиста при создании таких программ, как правило, минимальная и сводится к заданию опций параллельной оптимизации компилятора, директив параллельной компиляции, использованию специализированных языков для параллельных вычислений. Даже при программировании сложных вычислительных алгоритмов можно использовать библиотеки подпрограмм, специально разработанных и оптимизированных для конкретной архитектуры компьютера.
В последнем случае программист даже может ничего не знать о том, что программа выполняется параллельно, примером таких библиотек программ может служить хорошо известный пакет математического моделирования MATLAB [7]. Мало кто знает, что язык реляционных баз данных SQL (Structured Query Language) является языком с неявной параллельностью, которая может использоваться соответствующим компилятором в распределенной системе баз данных, не требуя для этого специальных языковых конструктивов.
Кроме того, большинство транзакций SQL-программ обрабатывается различными пользователями параллельно или с разнесением временных интервалов их выполнения. SQL-инструкции могут использоваться непосредственно (интерактивным образом) в базе данных или интегрироваться в один из параллельных языков программирования в виде встроенного блока SQL.
Главными особенностями рассматриваемого подхода является то, что обработкой данных производит управление одна программа:
- пространство имен является глобальным, то есть для разработчика имеется единственная память, детали структуры данных, доступ к памяти и межпроцесорному обмену данными от него закрыты;
- низкая синхронизируемость вычислений на параллельных процессорах. Выполнение команд при этом на различных процессорах происходит, как правило, независимо и только иногда происходит согласование выполнения циклов или других программных конструкций. Каждый процессор выполняет одинаковый фрагмент программы, однако отсутствует вероятность, что в текущий момент времени на всех процессорах выполняется одна и та же машинная команда;
- параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах.
Подход, основанный на параллелизме данных, базируется на использовании в программах базового набора операций:
- операции управления данными - в определенных ситуациях возникает необходимость в управлении распределением данных между процессорами, это может понадобиться, например, для обеспечения равномерной загрузки процессоров - чем более равномерно загружены работой процессоры, тем более эффективной будет работа компьютера;
- операции над массивами в целом, а также над их фрагментами;
- аргументами этих операций являются массивы в целом или их фрагменты (сечения), при этом одна операция применяется одновременно ко всем элементам массива или к его части, например, операциями такого типа являются операции умножения элементов массива на скалярный или векторный множитель, возможны осуществления и сложных действий - вычисление функции от массива;
- условные операции - они применяются только к тем элементам массива, которые удовлетворяют определенному условию, например, в сетевых методах это могут быть элементы, соответствующие четным / нечетным номерам строк или столбцов сетки;
- операции приведения - применяются ко всем элементам массива (или к его части), а результатом является одно-единственное значение, примерами операции приведения являются операции вычисления суммы элементов массива или максимального значения его элементов;
- операции сдвига - операции сдвига массивов нужны для эффективной реализации некоторых параллельных алгоритмов, например, сдвиги часто используются в алгоритмах обработки изображений, в конечно-разностных алгоритмах и т.д .;
- операции сканирования - такие операции также называются префиксными / суфиксными операциями, например, префиксная операция суммирования выполняется следующим образом - элементы массива суммируются последовательно, а результат очередного суммирования заносится в очередную ячейку нового, результирующего массива, причем номер этой ячейки совпадает с числом суммированных элементов исходного массива;
- операции, связанные с пересылкой данных - операции могут осуществляться, например, между массивами разной формы, которые имеют разную размерность, длину по каждому измерению и др.
Реализация модели параллелизма данных нуждается в поддержке параллелизма на уровне транслятора