🗊Параллельное программирование Минакова Е.О. Студентка 6 курса ОНУ им.И.И.Мечникова

Параллельное программирование Минакова Е.О. Студентка 6 курса ОНУ им.И.И.Мечникова

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

Что же нужно, чтобы достичь параллелизма? Достижение параллелизма возможно только при выполнимости следующих требований к архитектурным принципам построения вычислительной системы: независимость функционирования отдельных устройств ЭВМ - данное требование относится в равной степени ко всем основным компонентам вычислительной системы - к устройствам ввода-вывода, к обрабатывающим процессорам и к устройствам памяти; избыточность элементов вычислительной системы - организация избыточности может осуществляться в следующих основных формах: использование специализированных устройств таких, например, как отдельных процессоров для целочисленной и вещественной арифметики, устройств многоуровневой памяти (регистры, кэш); дублирование устройств ЭВМ путем использования, например, нескольких однотипных обрабатывающих процессоров или нескольких устройств оперативной памяти.

Примеры топологий многопроцессорных вычислительных систем полный граф (completely-connected graph or clique)- система, в которой между любой парой процессоров существует прямая линия связи; как результат, данная топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой при большом количестве процессоров; линейка (linear array or farm) - система, в которой каждый процессор имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами; такая схема является, с одной стороны, просто реализуемой, а с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений);

Примеры топологий многопроцессорных вычислительных систем кольцо (ring) - данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки; звезда (star) - система, в которой все процессоры имеют линии связи с некоторым управляющим процессором; данная топология является эффективной, например, при организации централизованных схем параллельных вычислений;

Примеры топологий многопроцессорных вычислительных систем решетка (mesh) - система, в которой граф линий связи образует прямоугольную сетку (обычно двух- или трех- мерную); подобная топология может быть достаточно просто реализована и, кроме того, может быть эффективно используема при параллельном выполнении многих численных алгоритмов (например, при реализации методов анализа математических моделей, описываемых дифференциальными уравнениями в частных производных); гиперкуб (hypercube) - данная топология представляет частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора (т.е. гиперкуб содержит 2N процессоров при размерности N);

КЛАССЫ ЗАДАЧ, КОТОРЫЕ МОЖНО ЭФФЕКТИВНО РАСПАРАЛЛЕЛИТЬ Одномерные массивы Двумерные массивы Клеточные автоматы Системы дифференциальных уравнений

ВЫЧИСЛЕНИЕ ЧАСТНЫХ СУММ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЛОВЫХ ЗНАЧЕНИЙ Последовательный алгоритм суммирования Традиционный алгоритм для решения этой задачи состоит в последовательном суммировании элементов числового набора Вычислительная схема данного алгоритма может быть представлена следующим образом (Рис.1).

Что все это значит Модифицированная каскадная схема Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы. В новом варианте каскадной схемы все проводимые вычисления подразделяется на два последовательно выполняемых этапа суммирования (см. Рис. 3):

МАТРИЧНОЕ УМНОЖЕНИЕ