Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Существуют 3 основных направления организации параллельной обработки информации.
I. Совмещение во времени различных этапов разных задач.
II. Одновременное решение различных задач или частей одной задачи.
III. Конвейерная обработка информации.
I. Мультипрограммный, мультизадачный, многозадачный режим.
II. Этот способ возможен только при наличии нескольких процессов, при этом используется те или иные свойства задач или потоков задач, что позволяет осуществить тот или иной параллелизм.
А). Естественный параллелизм независимых задач. В систему поступает несвязанный поток задач; решение любой задачи не зависит от результатов решения другой задачи.
Б). Параллелизм независимых ветвей. При решении большой задачи могут быть выделены отдельные независимые части –ветви программы, которые могут выполняться независимо при наличии нескольких независимых устройств.
Критерии независимость ветвей.
В случае параллелизма независимых ветвей программа может быть представлена в ярусной параллельной форме.
РИСУНОК.
В). Параллелизм объектов или данных –это вид параллелизма, кода по одной и той же программе обрабатывается некоторая совокупность данных, поступающих в систему одновременно (задачи векторной алгебры, обработка измерения от датчиков).
III. Которая может быть реализована в системе с одним процессом, разделенного на некоторое количество последовательно включенных операционных блоков, каждый из которых специализируется на выполнении строго определенной операции или части операции.
Пр. Сложение 2-х чисел с плавающей точкой.
Каждому из этапов поставили в соответствие устройства. В совокупности эти устройства образуют конвейер, проходя через которой входные данные преобразуются в результат.
РИСУНОК.
При сложении двух скаляров эффект от конвейеризации не ощутим. Явный эффект возникает в том случае, если А и В вектора из n элементов.
ФОРМУЛЫ, РИСУНОК.
Классификация вычислительных систем по Флинну.
Она основана на понятиях потока команд и потока данных. Поток команд –последовательность команд программы. Поток данных –это последовательность данных, обрабатываемых программой. Классы:
2. Параллельная форма алгоритма. Ярус, высота и ширина параллельной формы алгоритма. Максимальная параллельная форма. Схема сдваивания.
Пусть операция алгоритмов разбита на группы, упорядоченные так, что каждая операция любой группы зависит от начальных данных алгоритма, либо от результатов выполнения операций, находящихся в предыдущих группах. Представление алгоритма в подобной форме называется параллельной формой алгоритма. Каждая группа операций называется ярусом параллельной формы. Число групп называется высотой параллельной формы, а максимальное число операций в ярусе –шириной параллельной формы.
Если известна параллельная форма алгоритма, то сам алгоритм можно реализовать на параллельной вычислительной системе по шагам, последовательно ярус за ярусом.
Упрощающее предположение:
.количество процессов в принципе не ограничено
.коммуникационная сеть организована таким образом, что алгоритм может быть выполнен за время пропорциональное высоте параллельной формы.
Для одной и той же задачи можно получить несколько параллельных форм, которые различаются как шириной, так и высотой, поскольку время выполнения алгоритма пропорционально высоте параллельной формы, особое значение приобретает форма минимальной высоты. Такие формы называют максимальными формами, а их высота называется высотой алгоритма.
Пример. (а1а2+а3а4)(а5а6+а7а8)
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2 а3а4 а5а6 а7а8
Ярус 2 а1а2+а3а4 а5а6+аа7а8
Ярус 3 (а1а2+а3а4)(а5а6+а7а8)
Высота = 3, ширина = 4.
Это максимальная форма для данной задачи. Плоха форма тем, что все 4 процессора задействованы только на первом ярусе. Начиная со второго яруса процессоры постепенно освобождаются и простаиваются.
Поставим задачу разработки формы, в которой процессоры будут загружены более равномерно.
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2 а3а4
Ярус 2 а5а6 а7а8
Ярус 3 а1а2+а3а4 а5а6+аа7а8
Ярус 4 (а1а2+а3а4)(а5а6+а7а8)
Эта форма хороша тем, что для ее реализации потребуется всего 2 процессора, оба из которых, за исключением последнего яруса, будут загружены.
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2 а3а4
Ярус 2 а1а2+а3а4 а5а6
Ярус 3 а7а8
Ярус 4 а5а6+а7а8
Ярус 5 (а1а2+а3а4)(а5а6+а7а8)
Эта форма наименее удачна, поскольку высота у нее максимальна из 3-х рассмотренных примеров, а процессоры загружены не равномерно.
В общем случае построение параллельных форм с заданными свойствами являются не простой задачей.
Схема сдваивания.
Требуется вычислить:
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2
Ярус 2 (а1а2)*а3
Ярус 3 (а1а2а3)*а4
…………………………………..
Ярус 7 (а1а2а3а4а5а6а7)*а8
Схема исключительно не эффективна. Более эффективен вариант реализованный по так называемой схеме сдваивания.
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2 а3а4 а5а6 а7а8
Ярус 2 (а1а2)(а3а4) (а5а6)(а7а8)
Ярус 3 (а1а2а3а4)(а5а6а7а8)
Для выполнения каждой операции из m-го яруса берутся два результата операций (m-1) яруса, n –количество входных данных.
Преимущество: высота и ширена формы предсказуемы. Высота , -округление до ближайшего целого. Ширина .
При использовании схемы сдваивания загруженность процессоров как правило уменьшается от яруса к ярусу.
Параллельная обработка информации в вычислительных системах. Конвейерная обработка. Мультипрограммный режим, формула Литтла. Ярусно-параллельная форма представления программы.
Параллельная программа –единый объект, призванный достичь цели, заданной алгоритмом задачи. Она состоит из совокупности последовательных программ, реализованных в виде отдельных модулей или ветвей, имеющими возможность для одновременного выполнения и взаимодействия м-ду собой.
Выделяют 3 основных способа организации параллельной обработки информации:
. Мультипрограммная обработка данных (возможна для однопроцессорных ЭВМ) –режим обработки данных, при котором в системе имеется одновременно несколько задач (могут выполняться одновременно различными устройствами). Число задач, одновременно находящихся в системе называется уровнем мультипрограммирования.
Уровень мультипрограммирования, производительность и время ответа связываются м-ду собой формулой Литтла.
λ=M/U λ –производительность, М-уровень мультипрогр-ния, U-время ответа.
С увеличением М увеличивается вероятность того, что большая часть устройств занята. Однако еще малой остается вероятность того, что несколько задач обращаются к одному устройству. Т.о. Λ возрастает с повышением М, а U остается практически неизменной. Однако, начиная с некоторого значения М* выясняется, что все устройства загружены, к каждому из них образуются очереди задач. Т.о. λ не увеличивается, а время ответа неограниченно возрастает. М* называют точкой насыщения мультипрограммирования. Оно определяется количеством устройств в системе и свойствами решаемых задач. Если задачи преимущественно используют одно устройство, то точка насыщения м.б. равна количеству устройств.
Коэффициент мультипрограммирования –коэффициент, определяющий количество одновременно выполняющихся программ.
) m=∑Ni=1ρi, ρi=Ti/T
ρi-загруженность i-го устройства, Ti-время, в течении которого i-тое устройство работает, T-общее время работы системы.
) m=λm/ λi - физический смысл (отношение производительности системы в мультипрограммном режиме к производительности в однопрограммном режиме).
. Конвейерная обработка.
Предполагается прохождение потока данных ч/з последовательность функциональных блоков, реализующих различные операции, выполнение которых м.б. совмещено во времени (реализуется на уровне отдельного устройства, где организован конвейерный микрооператор). Это параллелизм на уровне команд.
Примером может служить сложение двух векторов, элементами которых являются числа с плавающей точкой. Выполняется 4 операции:
. сравнивание порядков
. выравнивание порядков
. сложение мантисс
. нормализация результата
Т=n∑ki=1ti; Т- ;n –размер вектора; ti-время обработки на i-той операции; k-количество операций на конвеере.
Т=(n+k-1)*m; n –размер вектора, k-длина конвейера; m-длина максимального оператора.
. Одновременное решение различных задач или различных частей одной задачи.
Возможно только при наличии нескольких обрабатывающих устройств.
Виды параллелизма:
это наиболее явная форма программного параллелизма м.б. представлена в виде ярусно –параллельной формы.
ff 1
ff 2
ff 3
ff 4
вершины графа x1…х8 ветви программы
Каждый ярус обрабатывается независимыми ветвями, отвечающими ранее выделенным критериям. Независимые ветви могут выполняться одновременно. Дуги обозначают входные и выходные данные и промежуточные результаты, связывающие м-ду собой различные ярусы.
2. Закон Гроша. Гипотеза Минского.
Развитие многопроцессорных ВС долгое время сдерживалось. Они представляют собой критерий производительности, который используется для сопоставления традиционных однопроцессорных ЭВМ и многопроцессорных вычислительных систем.
Закон Гроша: производительность одного процессора увеличивается пропорционально квадрату его стоимости.
Однако в пределе закон Гроша оказывается не верным, т.к. рост производительности ограничивается скоростью распространения электронов в проводнике, следовательно с некоторого момента рост стоимости процессора не гарантирует рост производительности.
Гипотеза Минского: пусть в системе имеется n процессоров, производительность каждого из которых =1, общая производительность такой системы с увеличением числа процессов увеличивается как log2n из-за необходимости обмена данными м-ду процессорами. Однако в 80-90 годы на практике удалось доказать, что благодаря усовершенствованию аппаратного обеспечения и внедрению более совершенных механизмов управления м.б. достигнута большая производительность, чем log2n.
3. Законы Амдала и следствия из них.
Загруженность устройства – это отношение стоимости реально выполненной работы к максимально возможной стоимости. Пиковая производительность устройства –это максимально возможное количество операций, которые могут быть выполнены данным устройством за единицу времени. Ускорение выполнения – это безразмерная величина, которая показывает, во сколько раз уменьшается время выполнения программы в системе с заданным количеством универсальных процессоров р по сравнению с однопроцессорными системами.
Первый закон Амдала – производительность ВС, состоящая из связных м-ду собой устройств в общем случае определяется самым не производительным ее устройством.
Следствие: пусть система состоит из простых устройств и граф системы связный. Если все устройства системы имеют одинаковые пиковые производительности, то асимптотическая производительность системы будет максимальная. Потеря производительности определяется простоями в очереди к самому непроизводительному устройству. Если пиковые производительности одинаковые, то простои удается исключить. Таким образом, общая производительность системы будет максимальной.
Второй закон Амдала – пусть доля операции в программе, которые нужно выполнить последовательно, составляет 0<=f<=1. Если f=0, программа полностью параллельна, если f=1, программа полностью последовательна. Тогда при заданном значении f и количестве используемых процессоров р ускорение выполнения s оценивается следующим образом
s<=1/(f+(1-f)/p). Ускорение определяется количественным соотношением частей кода, которые могут быть выполнены последовательно и параллельно. В меньшей степени ускорение определяется количеством используемых процессоров.
Следствие: позволяет решить обратную задачу, т.е. определить, какую часть кода необходимо ускорить, т.е. распараллелить, чтобы обеспечить требуемое значение s.
Следствие: чтобы ускорить выполнение программы в q раз, необходимо ускорить не менее чем в q раз, не менее чем [1-1/q] часть программы.
10. Параллельная обработка информации в транспьютерных системах. Язык OCCAM как инструментальное средство параллельного программирования транспьютерных систем (ТС).
ТС могут рассматриваться как подкласс однородных выч. систем (ОВС). ОВС – совокупность выч. устройств или модулей, одинаковым образом связанных между собой. Кол-во выч. устройств не огранич. и м.б. сколь угодно большим, а связи между ними явл. локальными. Для ОВС характерна избыточность выч. устройств и связей между ними. Это позволяет обеспечить высокую готовность и отказоустойчивость системы, легкую перенастраиваемость на задачи различного типа. В основу положены 3 аксиомы:
1-я акс. устанав., что любая сложная задача м.б. разбита на совокупность простых подзадач, некоторые из которых возможно будут выполняться //-но.
2-я акс. базируется на первой. Поскольку решение сложных задач м.представить структурной моделью, включ. более простые подзадачи и связи между ними, данной структуре модели можно поставить в соответствие другую структур. модель, представл. собой совокупность обраб. эл-тов и связей между ними.
3. Поскольку каждая сложная задача м.б. представлена как совокупность простых подзадач, каждую задачу м. разбить на мн-во подзадач одинаковых по объему вычисл. и схемам обмена.
Транспьютерные или мультитранспьютерные системы – многомодульные выч. системы, в кот. в кач-ве модуля использ. транспьютер.
Транспьютер – однокристал. ЭВМ, облад. возможностью хранения, обработки и передачи инф.
Транспьют. системы м.б. представлены как решетчатый граф.
OCCAM.
Основными единицами OCCAM явл. простейшие действия или операции. Затем с помощью управляющих примитивов из этих действий организуются различного рода процессы:
SEQ – последоват.
PAR – парал.
ALT – альтернат.
IF – условн.
WHILE – циклич.
Принадлежность действий или процесса к какому-либо проц. опред. по величине отступа от левого края.
Простые действия:
Переменные представляют собой обозначения битовых комбинаций фиксированного размера. Переменные д.б. описаны раньше того процесса, в кот. они используются.
Описание каналов д. располагаться перед тем PAR-проц., кот. их использует.
Поддерживается только 1 тип структурных данных – массивы. Этот тип распадается на 2 типа: массивы и таблицы.
11. MPI: назначение и организация пакета MPI, принцип построения программ для MPI. Классификация ф-ций MPI. Ф-ции MPI_BCAST, MPI_BARRIER, MPI_GATHER, MPI_SCATTER.
Было установлено, что кластер м.б. построен на базе стандарт. аппарат. средств, стандарт. сетевых решений и популяр. ОС. Т.о. организация кластера возлаг. на ПО, вышележащее по отнош. к средствам ОС. В кач-ве такого ПО м. примен. програм. интерфейс MPI.
MPI фактически представ. собой технол. програм-я, т.к. пользователю представляется набор средств для разраб. прогр. В состав пакета входит биб-ка прогр-я(С/С++, Fortran), загрузчик прилож.
В соответствии с технол. MPI //-ое приложение состоит из независимых ветвей или процессов. Каждый процесс идентифиц. целым неотрицательным числом и примен. к некоторой группе процессов. Группы также идентиф. целым неотрицат. числом. Группы создаются для объед. процессов при проведении вычислений. Каждой группе соответствует своя область связи. Для предоставления доступа к области связи процессор использует описатель области. Для MPI автоматически создается группа MPI_COMM_WORLD и одноименная область связи. Эти группы и области связи объединяют все процессы данного приложения. В ходе выполнения процессы обмениваются сообщениями. Каждое сообщение идентифиц. целым неотриц. числом и имеет атрибуты, для хранения кот. использ. MPI_Status(код процесса-отправителя, номер сообщения, код ошибки).
Основные функции MPI.
Все начинаются с префикса MPI_. После выполнения любая функция MPI возвращает целочисленное значение, кот. позволяет судить об успешном выполнении функции.
Функции делятся на категории по критериям:
1)блокир.
2)локальности
3)коллективности
По 1: делятся на блокир. и неблокир. Неблокир. выпол. в фоновом режиме, т.е. возврат из функции не означ., что ф-я уже выполн. Блокир. ф-ции возвращ. управление только тогда, когда описываемые действия полностью выполнены.
По 2: делятся на те, кот. осущ. пересылку данных другим ветвям и те , кот. этого не делают.
По 3: счит., что все ф-ции, кот. выполняются всеми процессами , подключ. к данной области связи с помощью одного и того же коммуникатора. Номер коммуникатора явл. обязательным аргументом данной функции.
int MPI_Barrier (MPI_Comm comm) – ф-ция барьерной синхронизации
int MPI_Bcast(void *buf,//адрес начала буфера
int count,//число передаваемых элементов
MPI_Datatype datatype,//тип сообщения
int sourse,//номер передающего проц.
MPI_Comm comm//идентификатор группы);
Осуществляет рассылку данных всем процессам данной группы в широковещательном режиме.
int MPI_Scatter(void *sbuf,//адрес начала буфера сообщения
int scount,//число передаваемых эл-тов сообщ.
MPI_Datatype sdatatype,//тип передав. эл-тов
void *rbuf,//адрес начала буфера сборки
int rcount,//число приним. эл-тов сообщ.
MPI_Datatype rdatatype,//тип приним. эл-тов сообщ.
int sourse,//номер рассылающего процесса
MPI_Comm comm//илентифик. группы);
передает i-му процессу данные.
int MPI_Gather(void *sbuf,//адрес начала буфера посылки сообщ.
int scount,//число паредав. эл-тов сообщ.
MPI_Datatype sdatatype,//тип эл-тов сообщ.
void *rbuf,//адрес начала буфера сборки
int rcount,//число приним. эл-тов сообщ.
MPI_Datatype rdatatype,//тип эл-тов сообщ.
int dest,//номер собирающего процесса
MPI_Comm comm, //идентиф. группы);
Каждый процесс посыл. содерж. одному(определ.) процессу. Сборка осущ. собирающим процессом.
12. Виртуальные топологии. Виды виртуальных топологий. Основные функции для работы с вирт. топологиями.
Коллективное взаимодействие и взаимодействие Point_to_Point не позволяет задавать явной связи между отдельными процессами. Для задания такой связи исп. вирт. топологии, кот. ставят в соответствие рангу процесса его вирт. координаты. Различают 2 вида топологий:
Декарт. топология.
int MPI_Cart_create (MPI_Comm comm_old, int ndims, int *dims, int *periods, int reorder, MPI_Comm *comm._cart);
1)comm_old – исходный коммуникатор
2)число размер. в топол.
3)целочислен. массив размером ndims, кот. опр-т кол-во проц-в в каждом измерении
4)целочисл. массив размером ndims, кот. определяет периодичность или непериодич.(замкнутость или открытость) для каждого измерения. Период-ть опред-ся знач. TRUE, непериод. – знач. FALSE.
5)ранги м.б. перенумер., если TRUE или не м.б., если FALSE
6)новый коммуникатор
int MPI_Dims_create(int nnodes, int ndims, int *dims);
1)кол-во узлов решетки
2)мерность декарт. топол.
3)целочисл. массив, опред. кол-во узлов в кажд. размерн.
Функция позволяет выполнить сбалансированное распределение процессов по направлению координат в зависимости от числа проц. в группе.
Функция приема-передачи
int MPI_Sendrecv(void *sendbuf ,//адр.буф.перед.данных
int sendcount,//число передав.элементов
MPI_Datatype sendtype,//тип перед.элементов
int dest,//ранг получателя
int sendtag,//тэг перед.сообщ.
void *recvbuf,//адр.буф.для приема сообщ.
int recvcount,//кол-во прин.эл-тов сообщ.
MPI_Datatype recvtype,//тип данных, прин.эл-м в сообщ.
int sourse,//ранг проц.-отправит.
int recvtag,//тэг прин.сообщ.
MPI_Comm comm.,//коммуникатор
MPI_Status *status //статус сообщ.);
Топология графа позволяет создавать любые, в т.ч. и нерегулярные связи между процессами.
Функция создания топол. графа
int MPI_Graph_create(MPI_Comm commold,//исходный коммуникатор
int nnodes,//кол-во узлов графа
int *index,//целочисл. массив узлов графа
int *edges,//описание ребер графа
int reorder,//лог.аргум.опр.допуст.переупор.ранга
MPI_Comm *commgraph//новый коммуникатор);