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

Ульяновский ГосударственныйУниверситет

2000

Записка по курсовой работе

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

                                                 Выполнил:           студент группы ПМ-52

                                                                                            НикифоровЮ.В.

                                                              Преподаватель:     Дулов Е.В.

2000

1. Модель среды параллельного программирования

Вкачестве физической архитектуры параллельного компьютера используется локальнаясеть LAN Ethernet. Таким образом, параллельный компьютер состоит изнекоторого количества процессоровP, соединенных между собой линией передачи данных.

<img src="/cache/referats/3556/image002.gif" v:shapes="_x0000_s1027">

Вмодели параллельного программирования используются две абстракции: задача(task)и канал(channel).

<img src="/cache/referats/3556/image004.gif" v:shapes="_x0000_s1029">

Даннаямодель характеризуется следующими свойствами:

1.<span Times New Roman"">     

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

2.<span Times New Roman"">     

Задача — этопоследовательная программа с локальными данными. Задача имеет входные ивыходные порты, которые служат интерфейсом к среде процесса.

3.<span Times New Roman"">     

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

4.<span Times New Roman"">     

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

5.<span Times New Roman"">     

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

6.<span Times New Roman"">     

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

Время выполненияпрограммы – время, прошедшее с момента запуска первого процессора до моментазавершения выполнения последнего (получения результата).

T = f  (N, P, U, …)

гдеN — размерностьзадачи, P — количество процессоров, U — количество задач параллельногоалгоритма.

Во время выполнения каждый процессор можетнаходиться в трёх состояниях: вычисление(computation), обмен данными(communication)и ожидание(idle). Соответственно, определяется время нахождения процессора в каждом изних:

<img src="/cache/referats/3556/image006.gif" v:shapes="_x0000_s1031">
Следовательно, время выполнения Tможет быть определено следующим образом:

<img src="/cache/referats/3556/image008.gif" v:shapes="_x0000_s1033">

или

<img src="/cache/referats/3556/image010.gif" v:shapes="_x0000_s1034">

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

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

Время передачи пакета данных между процессорамиможно представить в виде следующего выражения:

<img src="/cache/referats/3556/image012.gif" v:shapes="_x0000_s1037">

где ts– время инициализациипередачи, tw–времяпередачиединицы (слова) данных.Таким образом, в идеале имеемлинейную зависимость времени передачи от длины данных.

Но в сети типа Ethernetдля обмена данными для всех процессоровиспользуется единственный канал связи. Если два процессора хотят передатьданные в одно и то же время, реально будет передавать только один из них, а второйбудет ожидать окончания передачи первого. Т.е. имеет место разделение каналасвязи во времени. Если S– количество конкурирующих процессоровнуждающихся в передаче данных, то предыдущая формула изменится следующимобразом:

<img src="/cache/referats/3556/image014.gif" v:shapes="_x0000_s1038">

Таким образом, реальная пропускная способностьканала равна S-1.

Время ожидания (простоя) алгоритма Tidle. Процессор может простаивать в одном из двухслучаев:

·<span Times New Roman"">       

приотсутствии загруженных на него задач;

·<span Times New Roman"">       

приотсутствии входных данных задачи.

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

Более удобной мерой качества параллельнойпрограммы, чем время выполнения, является эффективность.Она характеризует полноту использования алгоритмом ресурсов параллельноговычислительной среды независимо от размерности самой задачи. Относительнаяэффективность определяется как:

<img src="/cache/referats/3556/image016.gif" v:shapes="_x0000_s1039">

где T1–времявыполнения на одном процессоре, Tp–время выполнения на Pпроцессорах.

Относительное ускорение:

<img src="/cache/referats/3556/image018.gif" v:shapes="_x0000_s1040">

— это коэффициент уменьшения времени выполненияна P процессорах.

3. Методы измерения временных характеристик в реальном времени

Имеется три вида методов сбора информации опроизводительности параллельной программы:

·<span Times New Roman"">       

рабочий профиль программы (execution profile) представляет собой общее время, проведенное вразличных участках программы;

·<span Times New Roman"">       

счетчикисобытий или совокупного времени;

·<span Times New Roman"">       

трассировка событий.

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

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

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

Информация, накопленная счетчиками, можетиспользоваться в рабочих профилях программы.

Трассировка событий предоставляет наиболее детальнуюнизкоуровневую информацию о производительности параллельной программы. Этаинформация представляет собой записи с отметкой о времени наступления события,типом события, именем задачи, взаимодействующей задаче и др.

Трассировка событий может использоваться длялокализации источников простоя и временной перегрузки программы, и такназываемых «узких мест» в каналах передачи данных.

Полученные трассировочные данные могут такжеиспользоваться в рабочем профиле программы и счетчиках.

4. Реализация

Метрики. Измеряемые параметры производительности программыбудем называть метриками, по сути,они те же счетчики. Каждая метрика представляет собой целое беззнаковое 32-битное число или unsignedlong. Для каждого канала, задачии процессора имеется стандартный внутренний набор метрик, который вычисляетсяавтоматически или с участием программиста задач. Также имеется дополнительныймассив ячеек для нестандартных метрик, размер его ограничен.

Ссылка на ячейки производится путем указанияномера ячейки, аналогично массивам, начиная с нуля.

Для вычисления метрик используются триабстракции:

·<span Times New Roman"">       

точки контроля– это места вызова функций сбора данных о производительности (вход/выходпроцедуры и др.);

·<span Times New Roman"">       

примитивы – функции изменения значений метрик, запуска/останова таймеров;

·<span Times New Roman"">       

предикаты – условия вызова примитивов, основанные на метриках или локальных данныхзадачи.

Примитивы:

·<span Times New Roman"">       

установка счетчикав данное значение (setCounter);

·<span Times New Roman"">       

увеличение счетчикана заданную величину (addCounter);

·<span Times New Roman"">       

уменьшение счетчикана заданную величину (subCounter);

·<span Times New Roman"">       

установкатаймера на данный счетчик (setTimer);

·<span Times New Roman"">       

запусктаймера (startTimer);

·<span Times New Roman"">       

остановтаймера (stopTimer).

Пример: сколько времени данная функция проводит, посылаясообщения?

     void foo ()

     {

       add (fooFlag); // fooFlagявляется признаком входа в функцию

       .. .

 

       sub (fooFlag);

     }

     sendMessage ()

     {

       if (fooFlag)

          startTimer ();

       .. .

       if (fooFlag)

          stopTimer ();

     }

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

<img src="/cache/referats/3556/image020.gif" v:shapes="_x0000_s1047">
Пример иерархии каналов показан на рисунке.

Иерархии ресурсов позволяют определитьдетализацию собираемой информации о производительности. Каждый более высокийуровень базируется на информации предоставляемой более низким уровнем. Впримере с иерархией каналов, на самом нижнем уровне вычисляются метрикиконкретных каналов. На уровне процессоров вычисляются общие метрики, такие как усредненныеили суммарные значения метрик всех каналов на конкретном процессоре. На самомвысоком уровне – всей системы – вычисляются общие метрики для всех каналов всистеме.

Кроме иерархии каналов определены иерархии ресурсовпроцессоров и задач.

Иерархическая организация информации используетсяпри анализе характеристик и производительности параллельных программ в реальномвремени.

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

<img src="/cache/referats/3556/image022.gif" v:shapes="_x0000_s1052">
Кольцослужебных каналов. Сборинформации о текущей производительности производится главным процессором (илизадачей), называемой диспетчером или менеджером. Для этого используютсяслужебные каналы, которые равноценны определенным ранее каналам. Из возможных структурсети служебных каналов, две из которых показаны на рисунке, выбрано “кольцо”.

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

Целесообразность использования кольца служебныхканалов (по сравнению с “веником”):

1.<span Times New Roman"">     

Небольшое общееколичество односторонних каналов (N+1 вместо2N);

2.<span Times New Roman"">     

Какследствие, разгрузка канала обмена диспетчера (нагрузка распределяется междувсеми процессорами системы);

3.<span Times New Roman"">     

Более низкиетребования к производительности диспетчера (есть время на обработку информациимежду соседними сэмплами);

4.<span Times New Roman"">     

Простотаконтроля загруженности канала сэмплирования (наряду со стандартными метрикамиканалов введены счетчики посланных и принятых запросов в диспетчере, взаголовок запроса включено поле – время отправления, по которому при возвращениизапроса определяется время его осуществления);

5.<span Times New Roman"">     

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

6.<span Times New Roman"">     

Простотасбора данных.

В каждом запросе указывается объект определеннойиерархии и запрашиваемая метрика:

·<span Times New Roman"">       

вид ресурсов;

·<span Times New Roman"">       

уровень иерархии;

·<span Times New Roman"">       

номеробъекта на данном уровне иерархии;

·<span Times New Roman"">       

код запрашиваемойметрики для данного объекта.

Структура получаемой информации однозначно определяетсятипом объектов указанных в запросе.

Возможно получение информации сразу по всемобъектам и/или всем метрикам – при указании специальных значений последних двух полей. В данном случае в ответ на запросвозвращается массив однотипных структур.

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

Таким образом, диспетчер поддерживает рабочий профильпараллельной программы. Общий вид структуры информации представляет собойдвумерную матрицу. Одна размерность состоит из наименований однотипныхобъектов, другая – из наименований метрик, измеряемых для данных объектов. Вкачестве объектов используются процессоры, задачи и каналы. Таким образом,имеется три матрицы текущих параметров параллельной программы. Также, имеютсявектора средних и общих параметров.

Для процессора вычисляются, например, следующиепараметры: загруженность, количество памяти, время простоя и др.

Для задач вычисляются общее время вычисления,время обмена данными и др.

Для каналов: счетчики входов в процедуры обмена send/recv, объем переданных/принятых данных, среднее время нахождения в режимеприема/передачи и др.

5. Контроль производительности.

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

Накопленная диспетчером информация – рабочий профиль– может использоваться для анализа выполнения параллельной программы. Далееописан примерный сценарий анализа.

Пусть задан вопрос: работает ли программа эффективно.

Гипотеза H0: программа работает эффективно.

Гипотеза H1: программа работает неэффективно.

Проверку гипотез производим из следующихсоображений. Выделим основные типы неэффективной работы параллельной программы,один из них:

·<span Times New Roman"">       

большая долявремени простоя задач от общего времени работы.

Упрощенно это выражается следующим выражением:

<img src="/cache/referats/3556/image024.gif" v:shapes="_x0000_s1041">
           

Можно взять критерий: Eп< 0,8.

Итак, если время простоя занимает более 20процентов общего времени работы программы, то есть основания считать работупрограммы неэффективной.

Подтвердив данную гипотезу – первого уровня, –переходим к анализу гипотез второго уровня. Предположим, в программе имеется«узкое место» в плане обмена данных. Рассмотрим участок графа потоков данных программы, показанный нарисунке.

<img src="/cache/referats/3556/image026.gif" v:shapes="_x0000_s1053">
Взаимодействуют две задачи через канал. ЗадачаT1генерирует данные, они передаются поканалу, являющемуся выходным дляT1, а задача T2 принимает их на свой входной порт и обрабатывает.

Существует два типа «узких мест»:

1.<span Times New Roman"">     

T2 неуспевает обрабатывать входные данные, T1 находится в состоянии ожидания обработки выходных данных. При этомнаблюдается:

a)<span Times New Roman"">     

загруженностьT2высока (> 90 %), загруженность T1 низка (< 50%),

b)<span Times New Roman"">     

количествосгенерированных L1 иобработанных L2 данных находятсяв отношении L1 – L2 > d > 0,

c)<span Times New Roman"">     

длинаочереди данных входного канала для T2велика.

2.<span Times New Roman"">     

T1 генерируетмало данных, T2 находится всостоянии ожидания входных данных. При этом наблюдается:

a)<span Times New Roman"">     

загруженностьT1высока (> 90 %), загруженность T2 низка (< 50%),

b)<span Times New Roman"">     

длинаочереди данных входного канала для T2мала.

В данном случае можно выдвинуть две соответствующиегипотезы. Их проверку можно осуществить из следующих соображений.

Рассмотрим метрику канала связи процессоров – среднеевремя обмена. Для первой задачи это функция send, для второй – recv.

Пусть процесс изменения этих метрик во времени выглядятпримерно так, как показано на рисунке.

<img src="/cache/referats/3556/image028.gif" v:shapes="_x0000_s1054">

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

Если имеет место вторая причина, то все наоборот.

Для подтверждения тех или иных гипотез можно применитьметоды анализа случайных процессов.

Заключение

Описанная система параллельного программированияявляется основой для создания программ визуализации, анализа производительности,оптимального начального распределения задач, динамической оптимизации выполненияпараллельных программ.

Программы визуализации и анализа производительностимогут использоваться для изучения параллельных алгоритмов, как таковых.

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

Преимущество данной системы состоит в том, что онане требует применения мощных компьютерных систем, вместо этого она полноценноиспользует ресурсы любых локальных сетей на базе ОСWindows95.

Литература:

1.<span Times New Roman"">     

Сервер ВЦ РАН http://www.ccas.ru/paral/

2.<span Times New Roman"">     

IanFoster,“Designing and Building Parallel Programs”, 1995

3.<span Times New Roman"">     

BartonP. Miller and others, “The Paradyn Parallel Performance Measurement Tools” ComputerSciences Department, University of Wisconsin-Madison. www.cs.wisc.edu/paradyn/

4.<span Times New Roman"">     

“Сети передачи данных”, 1989.
еще рефераты
Еще работы по менеджменту (теория управления и организации)