Современные информационные технологии / 2. Вычислительная техника и программирование

Кулимбетова Ж. А.

Карагандинский Государственный Технический Университет, Казахстан

Введение в разработку параллельных программ

Вычислительное направление применения компьютеров всегда оставалось основным двигателем прогресса в компьютерных технологиях. Не удивительно поэтому, что в качестве основной характеристики компьютеров используется такой показатель, как производительность - величина, показывающая, какое количество арифметических операций он может выполнить за единицу времени. Именно этот показатель с наибольшей очевидностью демонстрирует масштабы прогресса, достигнутого в компьютерных технологиях. Так, например, производительность одного из самых первых компьютеров EDSAC составляла всего около 100 операций в секунду, тогда как пиковая производительность Earth Simulator, одного из самых мощных на сегодняшний день суперкомпьютеров, оценивается в 40 триллионов операций в секунду. Т.е. произошло увеличение быстродействия в 400 миллиардов раз! Невозможно назвать другую сферу человеческой деятельности, где прогресс был бы столь очевиден и так велик. Естественно, что у любого человека сразу же возникает вопрос: за счет чего это оказалось возможным? Как ни странно, ответ довольно прост: примерно 1000-кратное увеличение скорости работы электронных схем и максимально широкое распараллеливание обработки данных.

Идея параллельной обработки данных как мощного резерва увеличения производительности вычислительных аппаратов была высказана Чарльзом Бэббиджем примерно за сто лет до появления первого электронного компьютера. Однако уровень развития технологий середины 19-го века не позволил ему реализовать эту идею. С появлением первых электронных компьютеров эти идеи неоднократно становились отправной точкой при разработке самых передовых и производительных вычислительных систем. Без

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

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

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

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

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

Написать эффективную параллельную программу намного труднее, чем

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

Отмечу, что идеальная параллельная программа обладает следующими свойствами:

ü Длины параллельно выполняемых ветвей равны между собой;

ü Полностью исключены простои из-за ожидания данных, передачи управления и возникновения конфликтов при использовании общих ресурсов;

ü Обмен данными полностью совмещен с вычислениями.

Увеличение степени эффективности параллелизма достигается следующими способами:

ü укрупнением единиц распараллеливания;

ü уменьшением сложности алгоритмов генерации параллельных процедур;

ü изначальной подготовкой пакета различных вариантов исходных данных;

ü распараллеливанием алгоритмов генерации параллельных процедур.

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

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

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