Принципы работы системы правления параллельными процессами в локальных сетях компьютеров
Ульяновский Государственный ниверситет
1
ЗАПИСКА ПО КУРСОВОЙ РАБОТЕ
Студент группы ПМ-42а Никифоров Ю.В.
Далее описаны принципы работы системы правления параллельными процессами в локальных сетях компьютеров.
1
1. множение матриц. (гипотетический пример)
A * B =: C
Где А (m*s), B (s*n), C(m*n)
лгоритм:
For i := 1 to s do
<Умножить вектор-строку на матрицу - A[i]*B = C[i]>
Граф зависимостей по данным (Data Flow Graph)
|
1 |
 |
A[1] C[1]
|
2 |
 |
A[2] C[2]
|
Д |
|
П |
 |
A, B C
A[k] C[k]
|
k |
Д - диспетчер. Коммутирует каналы связи и распределяет строки 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. Итерационные алгоритмы.
Общий случай графа потоков данных.
циклическая связь k
процессоров
|
1 |
|
2 |
|
3 |
|
Д |
Каждый процессора (P1..Pk) или группа процессоров выполняет свою задачу (интегрирование, множение, дифференцирование, минимизация, решение СЛУ и т.п.).
Диспетчер ДФ обеспечивает запуск итерационного процесса путём передачи исходных данных (нелевой итерации) в циклическую цепь.
Перегрузка цепи
Предположим что процессор Р1 обрабатывает поток данных быстрее по сравнению с Р2, также обеспечивается его эффективаная загруженность (на вход Р1 быстро поступают данные). Медленная обработка данных может быть вызвана низкой скоростью передачи данных по каналу P1-P2, низкой вычислительной мощностью процессора Р2 или сложностью задачи выполняющейся на Р2.
Следовательно, в результате работы итерационного алгоритма на выходе Р1 и на входе Р2 скапливаются данные, которые ожидают дальнейшей обработки.
Далее, если Р2 работает медленнее, чем Р3 (или Р2 вообще один из самых медленных процессоров), то простаивают все P(i), iа ³ 3 и Р1 (или работают с малой загруженностью).
В таком случае эффективность работы данной параллельной схемы резко снижается.
Действия.
Причиной снижения скорости вычислений является узкое место в цепочке процессоров, именно медленный поцессор Р2.
Одним из способов странения данного недостатка является динамическое изменение графа потоков данных.
Параллельно Р2 включается в работу дополнительный процессор РТ, выполняющий ту же задачу (рабочую функцию), что и Р2.
|
3 |
|
2 |
|
1 |
циклическая связь k
процессоров
|
Т |
 |
Таким образом в 2 раза повышается скорость обработки на дуге 1-2.
4. Принципы реализации.
Система реализована для ОС Windows 95 (NT), в виде исполняемой программы и дополнительной библиотеки динамической компоновки (DLL). Программа должна быть запущена на всех машинах локалной сети, частвующих в вычислениях. Дополнительная библиотека может использоваться программами, осуществляющими конкретные вычислительные и правляющие задачи.
Возможности.
1) Получение данных о системе:
Количество процессоров (машин), частвующих в вычислениях
Ресурсы каждого из процессоров (тип процессора, объём памяти, быстродействие)
Пропускная способность каналов связи с каждым из процессоров (при передаче потоков данных с текущей машины)
2) правление каналами потоков данных между процессорами (дугами):
Создание канала между любыми двумя процессорами, как из одной из них, так и из сторонней машины
Уничтожение, перенаправление каналов
Получение информации о скорости обработки данных на определённой дуге (обнаружение зких мест)
Установка желаемой скорости потока данных на дуге.
3) Запуск задач на любом из процессоров из сторонней машины.
4) Опрос состояния задачи, выполняющейся на процессоре (завершился с ошибкой, завис и т.п.)
5) Одновременная посылка данных группе процессоров посредством использования возможностей широковещания в локальных сетях, т.е. сразу по нескольким каналам связи.
Реализация.
Для управления каналами связи, также для получения информации о потоках данных в них, используется сетевой протокол TCP/IP и сетевой интерфейс правления Windows Sockets (версия 1.1).
Зауск задач на далённой машине осуществляется посредством использования библиотеки динамической компоновки, которая и должна содержать все процедуры-задачи в распараллеленной программе. Основная идея состоит в том, что при динамической компоновке файла, лежащего на сетевом диске (это каталок жёсткого диска компьютера, сделанный доступным из других машин сети), он не полностью передаётся по сети. Как известно, явная компоновка состоит из двуха шагов: загрузка библиотеки и присоединение процедуры, находящейся в ней. Загрузка библиотеки с сетевого диска влечет передачу по сети только заголовка небольшого размера. При присоединении процедуры передаётся только её тело плюс код, который она использует.
Таким образом, в какой то мере это довлетворяет требованиям.
Как же говорилось, на начальном этапе работы системы на всех машинах сети должна работать программа, т.е. программа-сервер. Для запуска распараллеленной программы необходимо одну из машин перевести в режим главной машины (диспетчера), казать файл распараллеленной программы, также требуется управляющая программа.
Управляющая программа должна, используя граф потоков данных распараллеленного алгоритма и описываемую здесь систему:
Создать каналы связи (дуги) между процессорами
Запустить задачи на процессорах (не более одной на каждом)
Передать начальные данные по соответствующим каналам
Организовать приём результативных данных.
*********************
Интерфейс с системой правления параллельными процессами подробно описан в спецификации программы.