Педагогические науки/Современные методы преподования

Жунусова Л.Х.,

г.Алматы, КазНПУ им. Абая

Жумаханова А.С.

г.Астана, КазАУ им. С. Сейфуллина

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ КАК ОПТИМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА

Современный подход к образованию в области параллельного программирования в России и Казахстана, по мнению авторов, имеет достаточно яркую «технологическую» направленность: основной упор при изложении учебного материала делается на аспекты параллельных вычислительных архитектур и практических технологий параллельного программирования (MPI, OpenMP, HPF, HPC). При этом прикладные возможности параллельных вычислений иллюстрируются в основном на хрестоматийных примерах 60-80х гг. прошлого века (матричные вычисления, обход графов). Несмотря на очевидную значимость этих алгоритмов при реализации ряда критических технологий, их бессистемное перечисление не приводит к развитию у слушателей творческих способностей в области разработки параллельных алгоритмов и программ для решения прикладных задач, диктуемых особенностями их собственной предметной области [1].

В те времена, когда параллельное программирование ассоциировалось с доступом к мощным суперкомпьютерам, владение способами конструирования таких алгоритмов оставалось уделом избранных; рядовому пользователю предлагались типовые алгоритмические решения и (или) программное обеспечение. Однако интенсивное развитие кластерных систем на основе стандартных комплектующих, а главное – проникновение на «бытовой» рынок систем на основе многоядерных процессоров перевело проблему параллельного программирования в разряд повседневных. Иными словами, вопрос создания параллельного программного обеспечения становится лишь одним из аспектов более общей дисциплины – инженерии прикладного параллельного математического обеспечения, как совокупности математических моделей, численных методов их реализации, параллельных алгоритмов и программных кодов. В рамках этой дисциплины должны быть разработаны рекомендаций по применению, содержащие иллюстрационные и обучающие примеры.

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

Параллельная программа содержит несколько процессов, работающих совместно над выполнением некоторой задачи. Каждый процесс — это последовательная программа, а точнее — последовательность операторов, выполняемых один за другим. Последовательная программа имеет один поток управления, а параллельная — несколько. Совместная работа процессов параллельной программы осуществляется с помощью их взаимодействия. Взаимодействие программируется с применением разделяемых переменных или пересылки сообщений. Если используются разделяемые переменные, то один процесс осуществляет запись в переменную, считываемую другим процессом. При пересылке сообщений один процесс отправляет сообщение, которое получает другой [2-3].

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

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

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

Под производительностью (performance) понимают количество операций, выполняемых на данной вычислительной системе в единицу времени. Быстродействие(speed) – величина, обратная среднему времени выполнения одной операции.

Производительность измеряется в миллионах команд в секунду MIPS (millionsinstructionspersecond) или миллионах операций с плавающей запятой в секунду MFLOPS (millionsfloatingpointoperationspersecond).

Кроме производительности важными характеристиками вычислительных систем являются масштабируемость вычислительной системы (scalability) - способность вычислительной системы к наращиванию и сокращению ресурсов (прежде всего, производительности и оперативной памяти), реконфигурируемость вычислительной системы (programmability) – варьирование числа узлов и графа их связей, надежность и живучесть вычислительной системы (reliabilityandrobustness). Хорошо масштабируемая система обеспечивает линейный рост производительности с ростом количества процессоров в ней.

Для выполнения операции сложения векторов , требуется время

(1)

где - фиксированное время запуска конвейера, - время "разгона" конвейера.

После запуска конвейера и его "разгона" конвейер выдает результат через каждый такт . Т.е. максимальная скорость выдачи результатов конвейером равна

(2)

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

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

При работе конвейера в последовательном режиме, очевидно, максимальная скорость выдачи результатов равна

(3)

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

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

Относительная производительность различных алгоритмов на данной параллельной вычислительной системе определяется длиной полупроизводительности.

Введем в рассмотрение величину

где – средняя длина обрабатываемых векторов. Тогда означает, что данный алгоритм может быть эффективно распараллелен для решения на данной вычислительной системе, 1 - означает противоположное.

Заключение. Быстродействие векторно-параллельной системы и MIMD-системы приближается к асимптотическому быстродействию в случае, когда в формуле (4) можно пренебречь коммуникационной составляющей и когда величина n кратна количеству процессоров в системе . Заметим, что пренебрежение коммуникационными расходами предполагает также, что команды не конфликтуют между собой при доступе к памяти. Смыслы асимптотического быстродействия и длины полупроизводительности различны. Асимптотическое быстродействие, главным образом, характеризует технологию изготовления ЭВМ, в то время как длина полупроизводительности представляет собой критерий степени параллелизма системы.

Литература

1. Топорков В.В. Совместное планирование и назначение процессов как метод оптимизации архитектурных решений вычислительных систем // Автоматика и телемеханика. — 2001. — № 12. — С. 107—116.

2. Котляров Д.В., Кутепов В.П., Осипов М.А. Граф-схемное потоковое параллельное программирование и его реализация на кластерных системах // Известия РАН. Теория и системы управления. — 2005, — № 1. —С. 75—96.

3. Message Passing Interface Forum www.mpi-forum.org.