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

1. Модель среды параллельного программирования В качестве физической архитектуры параллельного и спользуется локальная сеть LAN Ethernet . Таким образом , параллельный компьютер состоит из некоторого количества процессоров P , соединенных между собой линией передачи данных . В модели параллельного программирования используются две абстракции : задача ( task ) и канал ( channel ) . Данная модель характеризуется следующими свойствами : 1. Параллельное вычисление состоит из одного или более одновременно исполняющихся задач (процессов ), число которых может изменяться в течение врем ени выполнения программы . 2. Задача - это последовательная программа с локальными данными . Задача имеет входные и выходные порты , которые служат интерфейсом к среде процесса . 3. В дополнение к обычным операциям задача может выполнять следующие действия : послать сообщение через выходной порт , получить сообщение из входного порта , создать новый процесс и завершить процесс . 4. Посылающаяся операция асинхронная - она завершается сразу , не ожидая того , когда данные будут получены . Получающаяся операция син хронная : она блокирует процесс до момента поступления сообщения . 5. Пары из входного и выходного портов соединяются очередями сообщений , называемыми каналами . Каналы можно создавать и удалять . Ссылки на каналы (порты ) можно включать в сообщения , так что связность может измениться динамически . 6. Процессы можно распределять по физическим процессорам произвольным способами , причем используемое отображение (распределение ) не воздействует на семантику программы . В частности , множество процессов можно отобра зить на одиночный процессор . 2. Временные характеристики параллельной программы Время выполнения программы – время , прошедшее с момента запуска первого процессора до момента завершения выполнения последнего (получения результата ). T = f (N, P, U, … ) где N - размерность задачи , P - количество процессоров , U - количество задач параллельного алгоритма. Во время выполнения каждый процессор может находиться в трёх состояниях : вычисление ( computation ), обмен да нными ( communication ) и ожидание ( idle ) . Соответственно , определяется время нахождения процессора в каждом из них : Следовательно , время выполнения T может быть определено следующим образом : или Время вычисления алгоритма T comp может быть равн ым времени выполнения соответствующего не распараллеленного (последовательного ) алгоритма и зависит от размерности N задачи . Если параллельный алгоритм вносит дополнительные вычисления , тогда время вычисления зависит также и от количества задач U и процесс оров P . Время обмена данными алгоритма T comm это время , затраченное на прием и передачу данных между задачами . Существуют два вида обмена данными : между процессорами и внутри процессора . Первый тип обмена осуществляется между задачами находящимися на раз ных процессорах , т.е . по каналу связи . Второй тип обмена происходит , если взаимодействующие задачи находятся на одном процессоре , поэтому в данном случае обмен осуществляется гораздо быстрее , чем в первом , и по экспериментальным данным этим временем можно пренебречь. Время передачи пакета данных между процессорами можно представить в виде следующего выражения : где t s – время инициализации передачи , t w – время передачи единицы (слова ) данных . Таким образом , в идеале имеем линейную зависимость времени передачи от длины данных. Но в сети типа Ethernet для обмена данными для всех процессоров используется единст венный канал связи . Если два процессора хотят передать данные в одно и то же время , реально будет передавать только один из них , а второй будет ожидать окончания передачи первого . Т.е . имеет место разделение канала связи во времени . Если S – количество кон курирующих процессоров нуждающихся в передаче данных , то предыдущая формула изменится следующим образом : Таким образом , реальная пропускная способность канала равна S -1 . Время ожидания (простоя ) алгоритма T idle . Процессор может простаивать в одном из двух случаев : · при отсутствии загруженных на не го задач ; · при отсутствии входных данных задачи. Во втором случае избавится от простаивания можно следующим образом . Когда задача блокируется в ожидании входных данных можно на данном процессоре запустить другую задачу , для которой имеются входные данны е . Как только для первой задачи поступят данные прекратить выполнение второй . Данный метод оправдан только при низкой стоимости переключения задач . Также можно подключать разные каналы для одной и той же задачи при низкой стоимости данной операции. Более удобной мерой качества параллельной программы , чем время выполнения , является эффективность . Она характеризует полноту использования алгоритмом ресурсов параллельного вычислительной среды независимо от размерности самой задачи . Относительная эффективность определяется как : где T 1 – время выполнения на одном процессоре , T p – время выполнения на P процессора х . Относительное ускорение : - это коэффициент уменьшения времени выполнения на P процессорах. 3. Методы измерения вре менных характеристик в реальном времени Имеется три вида методов сбора информации о производительности параллельной программы : · рабочий профиль программы ( execution profile ) представляет собой общее время , проведенное в различных участках программы ; · счетчики событий или совокупного времени ; · трассировка событий . Рабочий профиль формируется автоматически для каждого процессора . При этом используется метод выборки данных через фиксированные промежутки времени , поэтому точность измерения не столь вы сока . По результатам можно построить гистограмму рабочих величин , например , определить задачу , которая забирает наибольшую часть вычислительного времени параллельного алгоритма на текущий момент. Счетчик представляет собой переменную , которая может быть увеличена каждый раз при наступлении определенного события . Счетчик может использоваться для подсчета количества вызовов данной процедуры , общего количества переданных или принятых сообщений , общего размера переданных или принятых данных для каждого проце с сора , задачи или канала . Некоторые счетчики встроены в библиотеки среды параллельного программирования , и можно заводит новые путем вставки соответствующих вызовов библиотеки в исходный код задач. Другой вариант счетчика – интервальный таймер . Он может исп ользоваться для точного измерения времени выполнения определенных участков кода программы (задачи ). Поэтому с помощью таймера можно измерять такой критичный ресурс процессора как производительность. Информация , накопленная счетчиками , может использоваться в рабочих профилях программы. Трассировка событий предоставляет наиболее детальную низкоуровневую информацию о производительности параллельной программы . Эта информация представляет собой записи с отметкой о времени наступления события , типом события , им енем задачи , взаимодействующей задаче и др. Трассировка событий может использоваться для локализации источников простоя и временной перегрузки программы , и так называемых «узких мест» в каналах передачи данных. Полученные трассировочные данные могут также использоваться в рабочем профиле программы и счетчиках. 4. Реализация Метрики . Измеряемые параметры производительности программы будем называть метриками , по сути , они те же счетчики . Каждая метрика представляет собой целое беззнаковое 32- битное число или unsigned long . Для каждого канала , задачи и процессора имеется стандартный внутренний набор метрик , который вычисляется автоматически или с участием программиста задач . Также имеется дополнительный массив ячеек для нестандартных метрик , размер его огр аничен. Ссылка на ячейки производится путем указания номера ячейки , аналогично массивам , начиная с нуля. Для вычисления метрик используются три абстракции : · точки контроля – это места вызова функций сбора данных о производительности (вход /выход процеду ры и др .); · примитивы – функции изменения значений метрик , запуска /останова таймеров ; · предикаты – условия вызова примитивов , основанные на метриках или локальных данных задачи. Примитивы : · установка счетчика в данное значение ( setCounter ); · увели чение счетчика на заданную величину ( addCounter ); · уменьшение счетчика на заданную величину ( subCounter ); · установка таймера на данный счетчик ( setTimer ); · запуск таймера ( startTimer ); · останов таймера ( stopTimer ). Пример : сколько времени данная ф ункция проводит , посылая сообщения ? void foo () add (fooFlag); // fooFlag является признаком входа в функцию . . . sub (fooFlag); sendMessage () if (fooFlag) startTimer (); . . . if (fooFlag) stopTimer (); Ресурсы – все интересующие нас объекты параллельной системы (процессоры , каналы , задачи ). Ресурсы упорядочены в некоторое количество иерархий . В каждой иерархии представлены объекты определенного типа . На нижнем уровне иерархии находятся конкретные объекты данного т ипа , существующие на данный момент в системе . На следующем более высоком уровне они собираются по определенному признаку , например в объекты , содержащие их. Пример иерархии каналов показан на рисунке. Иерархии р есурсов позволяют определить детализацию собираемой информации о производительности . Каждый более высокий уровень базируется на информации предоставляемой более низким уровнем . В примере с иерархией каналов , на самом нижнем уровне вычисляются метрики конк р етных каналов . На уровне процессоров вычисляются общие метрики , такие как усредненные или суммарные значения метрик всех каналов на конкретном процессоре . На самом высоком уровне – всей системы – вычисляются общие метрики для всех каналов в системе. Кроме иерархии каналов определены иерархии ресурсов процессоров и задач. Иерархическая организация информации используется при анализе характеристик и производительности параллельных программ в реальном времени. Для сбора информации используется метод сэмплир ования (от английского sampling ), т.е . периодического считывания текущих данных . Поступление очередного набора данных назовем сэмплом ( sample ). Кольцо служебных каналов . Сбор информации о текущей производительности производится главным процессором (или задачей ), называемой диспетчером или менеджером . Для этого используются служебные каналы , которые равноценны определенным ранее каналам . Из возможных структур сети служебных каналов , две из которых показаны на рисунке , выбрано “ кольцо ” . При необходимости определенной информации диспетчер посылает запрос по служебному каналу , который не содержит данных . Каждый процессор , принимая запрос , дополняет его своей информацией и посылает дальше по служебному каналу , следующему процессору . В результате прохождения запроса по всем процессорам системы он возвращается к диспетчеру с накопленной информацией. Целесообразность использования кольца служебных каналов (по сравнению с “веником” ): 1. Небольшое общее количество односторон них каналов ( N+1 вместо 2N ); 2. Как следствие , разгрузка канала обмена диспетчера (нагрузка распределяется между всеми процессорами системы ); 3. Более низкие требования к производительности диспетчера (есть время на обработку информации между соседними с эмплами ); 4. Простота контроля загруженности канала сэмплирования (наряду со стандартными метриками каналов введены счетчики посланных и принятых запросов в диспетчере , в заголовок запроса включено поле – время отправления , по которому при возвращении зап роса определяется время его осуществления ); 5. Контроль потока служебной информации (легко регулируется периодичность запросов ); 6. Простота сбора данных. В каждом запросе указывается объект определенной иерархии и запрашиваемая метрика : · вид ресурсов ; · уровень иерархии ; · номер объекта на данном уровне иерархии ; · код запрашиваемой метрики для данного объекта. Структура получаемой информации однозначно определяется типом объектов указанных в запросе. Возможно получение информации сразу по всем об ъектам и /или всем метрикам – при указании специальных значений последних двух полей . В данном случае в ответ на запрос возвращается массив однотипных структур. Диспетчер , – выделенный процессор , управляющий и контролирующий параллельную систему , – осуще ствляет мониторинг , и сбор необходимой информации о системе в реальном времени . Определен прикладной программный интерфейс диспетчера , который может использоваться программами начального распределения задач , визуализации , анализа производительности , динам и ческой оптимизации и др. Таким образом , диспетчер поддерживает рабочий профиль параллельной программы . Общий вид структуры информации представляет собой двумерную матрицу . Одна размерность состоит из наименований однотипных объектов , другая – из наименова ний метрик , измеряемых для данных объектов . В качестве объектов используются процессоры , задачи и каналы . Таким образом , имеется три матрицы текущих параметров параллельной программы . Также , имеются вектора средних и общих параметров. Для процессора вычис ляются , например , следующие параметры : загруженность , количество памяти , время простоя и др. Для задач вычисляются общее время вычисления , время обмена данными и др. Для каналов : счетчики входов в процедуры обмена send/recv , объем переданных /принятых данны х , среднее время нахождения в режиме приема /передачи и др. 5. Контроль производительности. В данном разделе описываются идейные соображения для построения системы , анализирующей производительность параллельных про грамм в реальном времени. Накопленная диспетчером информация – рабочий профиль – может использоваться для анализа выполнения параллельной программы . Далее описан примерный сценарий анализа. Пусть задан вопрос : работает ли программа эффективно . Гипотеза H 0 : программа работает эффективно. Гипотеза H 1 : программа работает неэффективно. Проверку гипотез производим из следующих соображений . Выделим основные типы неэффективной работы параллельной программы , один из них : · большая доля времени простоя задач от общего времени работы. Упрощенно это выражается следующим выражением : Можно взять критерий : E п < 0,8. Итак , если время простоя занимает более 20 процентов общего времени работы программы , то есть основания считать работу программы неэффективной. Подтвердив данную гипотезу – первого уровня , – переходим к анализу гипотез второго уровня . Предположим , в программе имеется «уз кое место» в плане обмена данных . Рассмотрим участок графа потоков данных программы , показанный на рисунке. Взаимодействуют две задачи через канал . Задача T 1 генерирует данные , они передаются по каналу , являющемуся выходным для T 1 , а задача T 2 принимает их на свой входной порт и обрабатывает. Существует два типа «узких мест» : 1. T 2 не успевает обрабатывать входные данные , T 1 находится в состоянии ожидания обработки выходных данных . При этом наблюдается : a) загру женность T 2 высока ( > 90 %), загруженность T 1 низка ( < 50% ), b) количество сгенерированных L 1 и обработанных L 2 данных находятся в отношении L 1 – L 2 > d > 0, c) длина очереди данных входного канала для T 2 велика. 2. T 1 генерирует мало данных , T 2 находи тся в состоянии ожидания входных данных . При этом наблюдается : a) загруженность T 1 высока ( > 90 %), загруженность T 2 низка ( < 50% ), b) длина очереди данных входного канала для T 2 мала. В данном случае можно выдвинуть две соответствующие гипотезы . Их пр оверку можно осуществить из следующих соображений. Рассмотрим метрику канала связи процессоров – среднее время обмена . Для первой задачи это функция send , для второй – recv . Пусть процесс изменения этих метрик во времени выглядят примерно так , как показан о на рисунке. Если имеет место первая причина снижения производительности , то первая метрика будет превышать вторую , т.к . первый процесс относительно долго находится в режиме передачи , а второй при этом не прини мает данные , а , скорее всего , вычисляет. Если имеет место вторая причина , то все наоборот. Для подтверждения тех или иных гипотез можно применить методы анализа случайных процессов. Заключение Описанная система параллельного программирован ия является основой для создания программ визуализации , анализа производительности , оптимального начального распределения задач , динамической оптимизации выполнения параллельных программ. Программы визуализации и анализа производительности могут использова ться для изучения параллельных алгоритмов , как таковых. В будущем , законченная система может использоваться для осуществления практических вычислительных задач большой сложности и оперирующих большими объемами данных. Преимущество данной системы состоит в том , что она не требует применения мощных компьютерных систем , вместо этого она полноценно использует ресурсы любых локальных сетей на базе ОС Windows 95.