Реферат: Принципы работы системы управления параллельными процессами в локальных сетях компьютеров
Ульяновский Государственный Университет
1999
ЗАПИСКА ПО КУРСОВОЙ РАБОТЕ
Студент группыПМ-42 Никифоров Ю.В.
Далее описаныпринципы работы системы управления параллельными процессами в локальных сетяхкомпьютеров.
1999
1. Умножение матриц. (гипотетический пример)
A * B =: C
Где А (m*s), B (s*n), C(m*n)
Алгоритм:
For i := 1to s do
<Умножить вектор-строку на матрицу – A[i]*B = C[i]>
Граф зависимостей по данным (Data Flow Graph)
1
<img src="/cache/referats/11326/image001.gif" v:shapes="_x0000_s1026 _x0000_s1027 _x0000_s1028">A[1] C[1]
2
<img src="/cache/referats/11326/image002.gif" " v:shapes="_x0000_s1029">A[2] C[2]
Д
П
<img src="/cache/referats/11326/image003.gif" v:shapes="_x0000_s1032 _x0000_s1031"> <img src="/cache/referats/11326/image004.gif" v:shapes="_x0000_s1033 _x0000_s1030">A, B C
<img src="/cache/referats/11326/image005.gif" v:shapes="_x0000_s1034"> <img src="/cache/referats/11326/image006.gif" v:shapes="_x0000_s1036"> <img src="/cache/referats/11326/image007.gif" v:shapes="_x0000_s1035"> <img src="/cache/referats/11326/image008.gif" v:shapes="_x0000_s1038"> <img src="/cache/referats/11326/image009.gif" v:shapes="_x0000_s1037">
A[k] C[k]
k
<img src="/cache/referats/11326/image010.gif" v:shapes="_x0000_s1039">Д – диспетчер. Коммутирует каналы связи и распределяетстроки A[i] попроцессорам.
П – приёмник (вполне может быть тем же диспетчером),формирует матрицу С из полученных строк.
K –число процессоров минус 2 (или 1), которые выполняют умножение строки наматрицу.
1) Если k ³ m. Тогда каждый процессородин раз выполняет перемножение A[i]*Bи передаёт результат процессору “П”. Далее процесс “П” формирует матрицу С и выдаёт результат пользователю.
2) Если k < m, то вначале просчитываютсяпервые k строк.
Когда вычисления закончится на одной из kпроцессоров, то ей передаётся следующая строка – т.е. A[k+1].
И так далее, в освободившиесяпроцессоры передаются строки
A[k + i], i = 1 … m-k.
Достоинства данной схемы.
1) B в процессоры-вычислители, и дальнейшаязагрузка только векторов-строк A[i] (минимизация потока данных).
2) k < m).
2. Цели оптимизации параллельныхвычислений.
1) DFG.
2)
3)
4) DFG в реальном времени (пояняется на следующем примереитерационных методов).
далее на следующейстранице…
3. Итерационные алгоритмы.
Общий случай графа потоков данных.
<img src="/cache/referats/11326/image011.gif" v:shapes="_x0000_s1040"><img src="/cache/referats/11326/image012.gif" v:shapes="_x0000_s1041"> циклическаясвязь k
процессоров
1
2
3
Д
<img src="/cache/referats/11326/image013.gif" v:shapes="_x0000_s1044 _x0000_s1045 _x0000_s1043 _x0000_s1046 _x0000_s1042 _x0000_s1048 _x0000_s1047">Каждый процессор (P1..Pk) или группа процессоров выполняетсвою задачу (интегрирование, умножение, дифференцирование, минимизация, решениеСЛУ и т.п.).
Диспетчер “Д” обеспечивает запуск итерационного процессапутём передачи исходных данных (нелевой итерации) в циклическую цепь.
Перегрузка цепи
Предположим что процессор Р1 обрабатывает поток данныхбыстрее по сравнению с Р2, а также обеспечивается его эффективанаязагруженность (на вход Р1 быстро поступают данные). Медленная обработка данныхможет быть вызвана низкой скоростью передачи данных по каналу P1-P2, низкой вычислительной мощностьюпроцессора Р2 или сложностью задачи выполняющейся на Р2.
Следовательно, в результате работы итерационного алгоритмана выходе Р1 и на входе Р2 скапливаются данные, которые ожидают дальнейшейобработки.
Далее, если Р2 работает медленнее, чем Р3 (или Р2 вообщеодин из самых медленных процессоров), то простаивают все P(i), i ³ 3 и Р1 (или работают с малойзагруженностью).
В таком случае эффективность работы данной параллельнойсхемы резко снижается.
Действия.
Причиной снижения скорости вычислений является “узкое место”в цепочке процессоров, а именно медленный поцессор Р2.
Одним из способов устранения данного недостатка являетсядинамическое изменение графа потоков данных.
Параллельно Р2 включается в работу дополнительный процессорР2’, выполняющий ту же задачу(рабочую функцию), что и Р2.
<img src="/cache/referats/11326/image014.gif" v:shapes="_x0000_s1049"><img src="/cache/referats/11326/image015.gif" v:shapes="_x0000_s1050"><img src="/cache/referats/11326/image016.gif" v:shapes="_x0000_s1051">
3
<img src="/cache/referats/11326/image017.gif" v:shapes="_x0000_s1052">2
<img src="/cache/referats/11326/image018.gif" v:shapes="_x0000_s1053">1
<img src="/cache/referats/11326/image019.gif" v:shapes="_x0000_s1054"><img src="/cache/referats/11326/image020.gif" v:shapes="_x0000_s1055"> циклическаясвязь kпроцессоров
2’
<img src="/cache/referats/11326/image021.gif" v:shapes="_x0000_s1058 _x0000_s1056 _x0000_s1057">Таким образом » в 2 раза повышается скорость обработки на дуге 1-2.
4. Принципы реализации.
Системареализована для ОС Windows 95 (NT), в виде исполняемой программы идополнительной библиотеки динамической компоновки (DLL). Программа должна бытьзапущена на всех машинах локалной сети, участвующих в вычислениях.Дополнительная библиотека может использоваться программами, осуществляющимиконкретные вычислительные и управляющие задачи.
Возможности.
1) Получение данных о системе:
· Количествопроцессоров (машин), участвующих в вычислениях
· Ресурсыкаждого из процессоров (тип процессора, объём памяти, быстродействие)
· Пропускнаяспособность каналов связи с каждым из процессоров (при передаче потоков данныхс текущей машины)
2) Управление каналами потоков данныхмежду процессорами (дугами):
· Созданиеканала между любыми двумя процессорами, как из одной из них, так и из стороннеймашины
· Уничтожение,перенаправление каналов
· Получениеинформации о скорости обработки данных на определённой дуге (обнаружение узкихмест)
· Установкажелаемой скорости потока данных на дуге.
3) Запуск задач на любом из процессоровиз сторонней машины.
4) Опрос состояния задачи,выполняющейся на процессоре (завершился с ошибкой, завис и т.п.)
5) Одновременная посылка данных группепроцессоров посредством использования возможностей широковещания в локальныхсетях, т.е. сразу по нескольким каналам связи.
Реализация.
Дляуправления каналами связи, а также для получения информации о потоках данных вних, используется сетевой протокол TCP/IP и сетевой интерфейс управленияWindows Sockets (версия 1.1).
Зауск задачна удалённой машине осуществляется посредством использования библиотекидинамической компоновки, которая и должна содержать все процедуры-задачи враспараллеленной программе. Основная идея состоит в том, что при динамическойкомпоновке файла, лежащего на сетевом диске (это каталок жёсткого дискакомпьютера, сделанный доступным из других машин сети), он не полностьюпередаётся по сети. Как известно, явная компоновка состоит из двух шагов: загрузка библиотеки и присоединениепроцедуры, находящейся в ней. Загрузка библиотеки с сетевого диска влечетпередачу по сети только заголовка небольшого размера. При присоединениипроцедуры передаётся только её тело плюс код, который она использует.
Такимобразом, в какой то мере это удовлетворяет требованиям.
Как ужеговорилось, на начальном этапе работы системы на всех машинах сети должнаработать программа, т.е. программа-сервер. Для запуска распараллеленнойпрограммы необходимо одну из машин перевести в режим главной машины(диспетчера), указать файл распараллеленной программы, а также требуетсяуправляющая программа.
Управляющаяпрограмма должна, используя граф потоков данных распараллеленного алгоритма иописываемую здесь систему:
· Создатьканалы связи (дуги) между процессорами
· Запуститьзадачи на процессорах (не более одной на каждом)
· Передатьначальные данные по соответствующим каналам
· Организоватьприём результативных данных.
*********************
Интерфейс ссистемой управления параллельными процессами подробно описан в спецификации программы.