Параллельный метод умножения матрицы на вектор

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

Вторая проблема связана с удаление последней копии. Как и в машине CC-NUMA, строка кэш-памяти может находиться одновременно в нескольких узлах. Если происходит промах кэша, строку нужно откуда-то вызвать, а это значит, что ее нужно отбросить. А что произойдет, если выбранная строка окажется последней копией? В этом случае ее нельзя отбрасывать.

Одно из возможных решений - вернуться к каталогу и проверить, существуют ли другие копии. Если да, то строку можно смело выбрасывать. Если нет, то ее нужно переместить куда-либо еще. Другое решение - пометить одну из копий каждой строки кэш-памяти как главную копию и никогда ее не выбрасывать. При таком подходе не требуется проверка каталога. Машина COMA обещает обеспечить лучшую производительность, чем CC-NUMA, но дело не в том, что было построено очень мало машин COMA, и нужно больше опыта. До настоящего моменты создано всего две машины COMA: KSR-1 и Data Diffusion Machine.

2.1.2 Мультикомпьютеры

Мультикомпьютеры (многопроцессорные системы с распределенной памятью) уже не обеспечивают общий доступ ко всей имеющейся в системах памяти (no-remote memory access or NORMA) - см. рис. 2.3. При всей схожести подобной архитектуры с системами с распределенной общей памятью (рис. 2.4, б), мультикомпьютеры имеют принципиальное отличие - каждый процессор системы может использовать только свою локальную память, в то время как для доступа к данным,

располагаемых на других процессорах, необходимо явно выполнить операции передачи сообщений (message passing operations). Данный подход используется при построении двух важных типов многопроцессорных вычислительных систем - массивно-параллельных систем (massively parallel processor or MPP) и кластеров (clusters). Среди представителей первого типа систем - IBM RS/6000 SP2, Intel PARAGON, ASCI Red, транспьютерные системы Parsytec и др.; примерами кластеров являются, например, системы AC3 Velocity и NCSA NT Supercluster.

Следует отметить чрезвычайно быстрое развитие многопроцессорных вычислительных систем кластерного типа. Под кластером обычно понимается множество отдельных компьютеров, объединенных в сеть, для которых при помощи специальных аппаратно-программных средств обеспечивается возможность унифицированного управления (single system image), надежного функционирования (availability) и эффективного использования (performance). Кластеры могут быть образованы на базе уже существующих у потребителей отдельных компьютеров, либо же сконструированы из типовых компьютерных элементов, что обычно не требует значительных финансовых затрат. Применение кластеров может также в некоторой степени снизить проблемы, связанные с разработкой параллельных алгоритмов и программ, поскольку повышение вычислительной мощности отдельных процессоров позволяет строить кластеры из сравнительно небольшого количества (несколько десятков) отдельных компьютеров (lowly parallel processing). Это приводит к тому, что для параллельного выполнения в алгоритмах решения вычислительных задач достаточно выделять только крупные независимые части расчетов (coarse granularity), что, в свою очередь, снижает сложность построения параллельных методов вычислений и уменьшает потоки передаваемых данных между компьютерами кластера. Вместе с этим следует отметить, что организация взаимодействия вычислительных узлов кластера при помощи передачи сообщений обычно приводит к значительным временным задержкам, что накладывает дополнительные ограничения на тип разрабатываемых параллельных алгоритмов и программ.

Рисунок 2.3 - Архитектура многопроцессорных систем с распределенной памятью

Отдельные исследователи обращают особое внимание на отличие понятия кластера от сети компьютеров (network of workstations или NOW). Для построения локальной компьютерной сети, как правило, применяют более простые сети передачи данных (порядка 100 Мбит/сек). Компьютеры сети обычно более рассредоточены и могут быть использованы пользователями для выполнения каких-либо дополнительных работ.

2.2 Сетевая технология Marynet 2000

Скорость передачи данных - 2Гбит/с и 10Гбит/с соответственно. Для MPI-приложений достигается скорость 247 Мбайт в сек и 1,2Гбайт в сек, латентность - 2,6 мкс. и 6 мкс. Данная технология использует оптоволоконное соединение. При построении сети используют коммутаторы, которые можно соединить между собой. Драйверы и программное обеспечение распространяются бесплатно. Стандарт Myrinet существует довольно давно, поэтому и широко поддерживается. Технология Myrinet в течение уже многих лет активно используется в Межведомственном суперкомпьютерном центре РАН для построения нескольких поколений суперкомпьютерных кластерных систем.

2.3 Характеристика типовых схем коммуникации в многопроцессорных вычислительных системах

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

2.3.1 Примеры топологий сети передачи данных

Структура линий коммутации между процессорами вычислительной системы (топология сети передачи данных) определяется, как правило, с учетом возможностей эффективной технической реализации. Немаловажную роль при выборе структуры сети играет и анализ интенсивности информационных потоков при параллельном решении наиболее распространенных вычислительных задач. К числу типовых топологий обычно относят следующие схемы коммуникации процессоров (см. рисунок 2.4):

Рисунок 2.4 - Примеры топологий многопроцессорных вычислительных систем

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

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

Кольцо (ring) - данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки;

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

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

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

- два процессора имеют соединение, если двоичные представления их номеров имеют только одну различающуюся позицию;

- в N - мерном гиперкубе каждый процессор связан ровно с N соседями;

- N -мерный гиперкуб может быть разделен на два (N ? 1) -мерных гиперкуба (всего возможно N различных таких разбиений);

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

3. Выбор языка управления вычислительными процессами

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

MPI расшифровывается как "Message passing interface" ("Взаимодействие через передачу сообщений"). Несколько путает дело тот факт, что этот термин уже применяется по отношению к аппаратной архитектуре ЭВМ. Программный инструментарий MPI реализован в том числе и для ЭВМ с такой архитектурой.

MPI предоставляет программисту единый механизм взаимодействия ветвей внутри параллельного приложения независимо от машинной архитектуры (однопроцессорные / многопроцессорные с общей/раздельной памятью), взаимного расположения ветвей (на одном процессоре / на разных) и API операционной системы.

(API = "applications programmers interface" = "интерфейс разработчика приложений")

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

Минимально в состав MPI входят: библиотека программирования (заголовочные и библиотечные файлы для языков Си, Си++ и Фортран) и загрузчик приложений.

Дополнительно включаются: профилирующий вариант библиотеки (используется на стадии тестирования параллельного приложения для определения оптимальности распараллеливания); загрузчик с графическим и сетевым интерфейсом для X-Windows и проч.

Структура каталогов MPI привычна глазу: bin, include, lib, man, src, ... Минимальный набор функций прост в освоении и позволяет быстро написать надежно работающую программу. Использование же всей мощи MPI позволит получить БЫСТРО работающую программу - при сохранении надежности.

MPI становится стандартом. Несколько вычислительнх устройств (процессоров), по нынешней терминологии, могут быть объединены одним из трех способов:

1. через общую память. В Юниксе существуют средства для работы с ней (разные для BSD- и ATT-клонов Юникса);

2. через скоростную внутримашинную сеть на ЭВМ с аппаратной архитектурой MPI. Здесь стандарта нет;

3. через сеть, как правило, работающую по протоколу TCP/IP.

Программный инструментарий MPI разрабатывался как долгожданный стандарт для машин с одноименной аппаратной архитектурой. Задачей-максимум было "подмять" под него и стандарты из соседних пунктов: MPI может работать на базе любого из трех способов соединений. Тем не менее, первая редакция MPI стандартом не стала в силу следующего ограничения: все процессы, сообщающиеся между собой посредством функций MPI, начинают и заканчивают свое выполнение ОДНОВРЕМЕННО. Это не мешает использовать MPI как скелет для параллельных приложений, но системы массового обслуживания (клиент-серверные приложения и проч.) приходится разрабатывать на базе старого инструментария.

Проблема устранена в MPI-II: он гарантировано станет стандартом в категории 2. Не исключено, что и стандарты категорий 1 и 3 со временем потеряют интерес для программиста и будут использоваться только как интерфейс между "железом" и MPI-II.

Сравнение с низкоуровневыми пересылками. Часто приходится слышать утверждение, что низкоуровневые пересылки через разделяемую память и семафоры предпочтительнее применения таких библиотек как MPI, потому что работают быстрее. Против такой точки зрения существует 4 очень веских довода:

1. В хорошо распараллеленном приложении на собственно взаимодействие между ветвями (пересылки данных и синхронизацию) тратится небольшая доля времени - несколько процентов от общего времени работы. Таким образом, замедление пересылок, допустим, в два раза не означает общего падения производительности вдвое - она понизится на несколько процентов. Зачастую такое понижение производительности является приемлемым и с лихвой оправдывается прочими соображениями;

2. MPI - это изначально БЫСТРЫЙ инструмент. Для повышения скорости в нем используются приемы, о которых прикладные программисты зачастую просто не задумываются. Например:

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

- MPI использует многопоточность (multi-threading), вынося большую часть своей работы в потоки (threads) с низким приоритетом. Буферизация и многопоточность сводят к минимуму негативное влияние неизбежных простоев при пересылках на производительность прикладной программы;

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

- и так далее...

И все-все скрупулезно отлажено и протестировано!

3. Перенос - отныне не требует переписывания и повторной отладки. Незаменимое качество для программы, которой предстоит пользоваться широкому кругу людей. Следует учитывать и то обстоятельство, что УЖЕ появляются машины, на которых из средств межпрограммного взаимодействия есть только MPI - и ничего более.

Отладка - ей посвящена оставшаяся часть раздела.

Перечисление, иллюстрации и способы избежания типовых ошибок, допускаемых при параллельном программировании - тема отдельного трактата. Сразу следует оговориться, что панацеи от них пока не придумано - иначе о таковой тотчас стало бы общеизвестно. MPI ни от одной из типовых ошибок (кроме "нарушения ордера") не страхует - но он уменьшает вероятность их совершить!

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

Сравнение с PVM. PVM - это изначально исследовательский проект. Его несомненными достоинствами являются простота использования (в теории) и почтенный возраст - он появился на свет в 1989 году, и, таким образом, на 6 лет старше MPI.

Надо признать, по сравнению с PVM, MPI - это СЛОЖНЫЙ пакет. То, что в PVM реализовано одним-единственным способом, в MPI может быть сделано несколькими, про которые говорится: способ А прост в использовании, но не очень эффективен; способ Б сложнее, но эффективнее; а способ В сложнее и эффективнее при определенных условиях. Изложение в доступных через Интернет учебниках рассчитано на профессиональных программистов, а не на прикладников, потому что упорядочено по областям применения (способы А, Б и В в одной главе), а не по уровням сложности (способ А в первой главе, способ Б в следующей, способ В и вовсе вынесен в приложения).

Главным недостатком MPI является отсутствие правильно упорядоченного описания для непрофессионалов.

Заключение

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

MPI-программа - это множество параллельных взаимодействующих процессов. Все процессы порождаются один раз, образуя параллельную часть программы. В ходе выполнения MPI-программы порождение дополнительных процессов или уничтожение существующих не допускается (в MPI-2.0 такая возможность появилась). Каждый процесс работает в своем адресном пространстве, никаких общих переменных или данных в MPI нет. Основным способом взаимодействия между процессами является явная посылка сообщений.

Список литературы

1. Антонов А.С. "Параллельное программирование с использованием MPI".-М.: Изд-во МГУ, 2004.-71 с.

2. Гергель В.П. "Теория и практика параллельных вычислений". Учебное пособие, 2007.- 44с.

3. Воеводин В.В. "Вычислительная математика и структура алгоритмов".-М.: Изд-во МГУ, 2006.-112с.

4. www.intuit.ru

5. www.parallel.ru

Приложение - Листинг программы

Размещено на Allbest.ru