ВУЗ: Пермский национальный исследовательский политехнический университет
Категория: Учебное пособие
Дисциплина: Информатика
Добавлен: 19.10.2018
Просмотров: 12729
Скачиваний: 132
56
Рис. 9. Блок-схема
вложенных циклов
Параметры внешнего и
внутреннего циклов разные и
изменяются не одновременно:
при одном значении параметра
внешнего цикла параметр внут-
реннего цикла принимает по-
очередно все значения (рис. 9).
Затем значение параметра внеш-
него цикла изменяется на едини-
цу, и опять от начала и до конца
выполняется вложенный цикл.
И так до тех пор, пока значение параметра внешнего цикла не
станет больше своего конечного значения.
При программировании вложенных циклов необходимо со-
блюдать следующее дополнительное условие: все операторы
внутреннего цикла должны полностью располагаться в теле
внешнего цикла.
6.4. Параллельные алгоритмы
Параллельный алгоритм, противопоставляемый традици-
онным последовательным алгоритмам, – алгоритм, который мо-
жет быть реализован по частям на множестве различных вычис-
лительных устройств (процессоров) с последующим объедине-
нием полученных результатов.
Некоторые алгоритмы достаточно просто поддаются раз-
биению на независимо выполняемые фрагменты. Например,
распределение работы по проверке всех чисел от 1 до 100000 на
предмет того, какие из них являются простыми, может быть вы-
полнено путем назначения каждому доступному процессору не-
которого подмножества чисел с последующим объединением
полученных множеств простых чисел.
С другой стороны, большинство известных алгоритмов вы-
числения значения числа
не допускают разбиения на парал-
лельно выполняемые части, так как требуют результата преды-
дущей итерации выполнения алгоритма. Итерационные числен-
j = 1, n
i = 1, m
тело цикла
57
ные методы также являются сугубо последовательными алго-
ритмами. Некоторые примеры рекурсивных алгоритмов доста-
точно сложно поддаются распараллеливанию.
К 2005 г. производительность одного процессора достигла не-
которого предела, в котором дальнейший рост производительности
ограничивался физическими законами. Появление многоядерных
систем позволило преодолеть этот барьер, однако это потребовало
новой парадигмы написания приложений и алгоритмов – начали
активно развиваться и применяться параллельные алгоритмы.
Сложность последовательных алгоритмов выражается в объ-
еме используемой памяти и времени (числе тактов процессора),
необходимых для выполнения алгоритма. Параллельные алго-
ритмы требуют учета использования ещё одного ресурса: подсис-
темы связей между различными процессорами. Существует два
способа обмена между процессорами: использование общей па-
мяти и системы передачи сообщений.
Системы с общей памятью требуют введения дополнительных
блокировок для обрабатываемых данных, налагая определенные
ограничения при использовании дополнительных процессоров.
Системы передачи сообщений используют понятия каналов
и блоков сообщений, что создает дополнительный трафик на
шине и требует дополнительных затрат памяти для организации
очередей сообщений.
Еще одной проблемой, связанной с использованием парал-
лельных алгоритмов, является балансировка нагрузки. Напри-
мер, поиск простых чисел в диапазоне от 1 до 100000 легко рас-
пределить между имеющимися процессорами, однако некоторые
процессоры могут получить больший объем работы, в то время
как другие закончат обработку раньше, и будут простаивать.
Проблема балансировки нагрузки ещё больше усугубляется при
использовании гетерогенных вычислительных сред, в которых
вычислительные элементы существенно отличаются по произ-
водительности и доступности.
Разновидность параллельных алгоритмов, называемая рас-
пределенными алгоритмами, специально разрабатывается для
58
применения на кластерах и в распределенных вычислительных
системах с учетом ряда особенностей подобной обработки.
Основной стратегией развития вычислительной техники явля-
ется создание многопроцессорных вычислителей. Получается, что
параллельные алгоритмы – единственный перспективный способ
повышения производительности при решении задач.
На рис. 10 приведен пример одной из моделей написания
параллельных алгоритмов для систем с общей памятью – так
называемый fork-join-параллелизм. Суть этой модели заключа-
ется в том, что внутри последовательной программы выделяют-
ся секции, в рамках которых происходит создание некоторого
количества параллельных потоков исполнения. Операция fork в
данном подходе отвечает за создание параллельных потоков и за
распределение по ним работы. Операция join ожидает заверше-
ния всех рабочих потоков и при необходимости объединяет
результаты работы отдельных потоков в общий результат парал-
лельной секции. Примером технологии, которая реализует мо-
дель fork-join-параллелизма, является OpenMP – открытый стан-
дарт для распараллеливания программ на языках С, С++, Фор-
тран. Он дает описание совокупности директив компилятора,
библиотечных процедур и переменных окружения, которые
предназначены для программирования многопоточных прило-
жений на многопроцессорных системах с общей памятью.
Рис. 10. Модель fork-join-параллелизма
Message Passing Interface (MPI, интерфейс передачи сооб-
щений) – программный интерфейс (API) для передачи информа-
fork
join
Параллельная секция
Последовательная
секция
Последовательная
секция
59
ции, который позволяет обмениваться сообщениями между про-
цессами, выполняющими одну задачу.
MPI является наиболее распространённым стандартом ин-
терфейса обмена данными в параллельном программировании,
существуют его реализации для большого числа компьютерных
платформ. Используется при разработке программ для кластеров
и суперкомпьютеров. Основным средством коммуникации между
процессами в MPI является передача сообщений друг другу.
Стандартизацией MPI занимается MPI Forum. В стандарте
MPI описан интерфейс передачи сообщений, который должен
поддерживаться как на платформе, так и в приложениях пользо-
вателя. В настоящее время существует большое количество бес-
платных и коммерческих реализаций MPI. Существуют реализа-
ции для языков Фортран 77/90, Java, С и С++.
В первую очередь MPI ориентирован на системы с распре-
деленной памятью, т.е. когда затраты на передачу данных вели-
ки, а OpenMP ориентирован на системы с общей памятью. Обе
технологии могут использоваться совместно, чтобы оптимально
использовать в кластере многоядерные системы.
7. ПРОГРАММНЫЕ СРЕДСТВА РЕАЛИЗАЦИИ АЛГОРИТМОВ
7.1. Языки программирования
Язык программирования – искусственный язык, который име-
ет ограниченное число «слов», значение которых понятно трансля-
тору, и очень строгие правила записи команд (операторов).
Если язык программирования ориентирован на конкретный
тип процессора и учитывает его особенности (разные типы про-
цессоров имеют разные наборы команд), то он называется язы-
ком программирования низкого уровня. Таким языком является
язык ассемблера. Подобные языки обычно применяют для напи-
сания небольших системных приложений, драйверов устройств,
модулей стыковки с нестандартным оборудованием, когда од-
ним из важнейших требований становится возможность прямого
доступа к аппаратным ресурсам.
60
Языки программирования высокого уровня значительно
ближе и понятнее человеку, нежели компьютеру. Особенности
конкретных компьютерных архитектур в них не учитываются,
поэтому создаваемые программы на уровне исходных текстов
легко переносимы на другие платформы, для которых создан
транслятор этого языка.
Языками программирования высокого уровня являются:
Фортран, Кобол, Алгол, Pascal, Basic, C, C++, Java, C#.
Языки программирования, используемые в базах данных,
предназначены для работы с хранилищами данных, со встроен-
ной функциональностью для хранения и обработки данных. Для
управления большими базами данных и их эффективной обра-
ботки разработаны СУБД (системы управления базами данных).
Основным языком для работы с данными в СУБД является
структурированный язык запросов SQL.
Однако в промышленных СУБД, кроме поддержки языка
SQL, есть поддержка собственных языков, расширяющих воз-
можности SQL. Примерами таких языков могут служить в СУБД
Oracle: PL/SQL, в СУБД PostgreSQL: PL/pgSQL.
Алфавит, синтаксис и семантика
Любой язык программирования имеет три основные со-
ставляющие: алфавит, синтаксис и семантику [5].
Алфавит языка программирования – набор допустимых
символов, которые можно использовать при записи программ
(буквы, цифры и специальные символы).
Синтаксис языка программирования – совокупность пра-
вил, определяющих допустимые конструкции языка, его форму.
Пример синтаксической ошибки – неправильно записанный, на-
пример, оператор цикла.
Семантика языка – совокупность правил, определяющих
смысл синтаксически корректных конструкций языка, его со-
держание. Пример семантической ошибки – неправильно запи-
санное на языке программирования арифметическое выражение,
что приводит к неправильному порядку выполнения в нем
арифметических операций.