, где - загрузка отрезка.

3. Если N1>N, то N:= N1 После обработки всех интервалов, получается требуемое N. Конец описания алгоритма.

31. Алгоритм определения оценки минимального времени T выполнения заданного алгоритма на ВС, содержащий N процессоров

Алгоритм 14.

1. Вычислим

,

где ]х[ - ближайшее к х целое, не меньшее х.

2. Просматриваются интервалы , как в алгоритме 13 пункте 2.

Примечание. При таком выборе последовательности отрезков значение T можно увеличивать, не пересчитывая при этом ранее вычисленные значения d.

3. Для очередного интервала вычислим значение

, величина вычисляется по алгоритму 2.

4. Если d>0, вычислим

5. Вычислим

6. После обработки всех интервалов вычисляем значение Т - нижнюю оценку минимального времени выполнения данного алгоритма на данной ВС.

Конец описания алгоритма.

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

1) е = t/T - коэффициент накладных расходов.

t - время, расходуемое ВС на организацию и реализацию всех обменов информацией между вычислителями.

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

Рассмотрим использование алгоритмов на примере:

В каждом вычислителе выполняется k* ]M/n[ -умножение, (k-1)*]M/n[ - сложение.

При достаточно большом значении k можно считать, что на каждый принятый элемент матрицы А приходится с операций сложения и умножения:

с = ]M/n[

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

Тогда эффективность можно определить в виде:

е = tп / с(tу + tс) = e / с , где e = tп / (tу + tс).

Из этого соотношения видно, что максимум накладных расходов будет, когда с=1 или, что тоже самое n=M. Величина с=1 информирует о минимально допустимом размере матриц, при котором ещё целесообразно вычисление задачи на n вычислителях. С другой стороны при фиксированном n, увеличение размера матриц приводит к росту с, следовательно, к уменьшению накладных расходов. Ясно, что чем больше размеры матриц (чем больше размеры вычислений), тем выше эффективность параллельного алгоритма, т.е. е>0 с>?.

2) ч = ф1 /фn - коэффициент ускорения.

ф1- время выполнения алгоритма (решения задачи) на одном вычислителе.

фn - в системе из n вычислителей (распараллеленный алгоритм).

ч' = ф1' /фn , ф1'- время выполнения последовательного алгоритма.

33. Закон Амдаля и коэффициент эффективности программы

Закон Амдаля

ч'? k / (д+(1 - д)/n)

n - количество вычислителей входящих в ВС.

д - относительная доля операций параллельной программы, выполненных последовательно.

0 ? д ? 1.

д =1 - программа относительно последовательна.

д= 0 - программа относительно параллельна.

k - корректирующий коэффициент 0 ? k ? 1. Он определяет качество параллельной системы, т.е. система характеризуется временными издержками, связанными с настройкой структуры системы, синхронизацией ветвей p - программы (параллельной) и временными издержками, связанными с обменом информацией между вычислителями.

Этот закон хорошо характеризирует конвеерные ВС, но также применим для массовых параллельных систем.

3) E = ч / n - коэффициент эффективности p-программы.

ч ? n , ч' ? n

E'? 1 , E ? 1

Если p-алгоритм обеспечивает максимальное ускорение, то ч = n и E = 1.

Основной целью распараллеливания сложных задач является достижение равенства max ч = n.

Основные причины препятствующие получению этого равенства:

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

2. несбалансированность нагрузки вычислителей и/или невозможность построения p-алгоритма с числом ветвей, равным числу вычислителей ВС.

34. Понятие о сложных задачах

е(v, n) = t(v, n) / T(v, n)

коэффициент накладных расходов в развёрнутом виде.

v - количество операций, которое необходимо выполнить при решении задач на ВС.

n - число вычислителей, n ? 2.

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

T - время вычислений.

е(v, n)>0 при v>?.

v ? n*10k (2), где k- эмпирический коэффициент , который ?1. Имеется зависимость k от быстродействия каналов связи. Таким образом можно сделать вывод, что объём операции V должен на несколько порядков превышать число вычислителей n. В этом случае достигается эффективное функционирование ВС.

Задачи для которых выполняется(2) называются сложными (системными, трудоёмкими, с большим объёмом вычислений), следовательно, задача тем сложнее, чем больше объём вычислений V. Когда не выполняется (2) - простые, задачи для 1-ого вычислителя.

35. Структурная схема функционирования больших ВС с указанием назначения очереди

Упрощённая функциональная схема вычислительной системы.

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



Первые два блока в анализ и синтез ВС не входят! (как правило)

Система памяти ВС как правило имеет сложную структуру. В эту систему также входят локальные памяти процессоров. Хорошая ВС имеет и локальную и общую память.

Очередь заданий - центральное звено функционирования в этой схеме.

Супервизор - управляет очередью заданий. Это специальная программа ОС. В его функции входят: управление и перестройка очереди заданий.

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

Статическое планирование использует оптимальное планирование, не всегда возможно(например, в системах реального времени), требует много процессорного времени.

Динамическое планирование - квазиоптимальное планирование, быстрое, но не оптимальное решение (т.к. используется эвристический алгоритм).

Реализуется схема централизованного и децентрализованного диспечирования.

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

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

Недостаток нет статического (оптимального) планирования, нет динамического планирования.

Параллельные вычислительные системы на решающих полях.

ФУС -функциональное устройство.

Программа загружается в КЭШ. Диспечер определяет какая инструкция, какому ФУС'у предназначена, и соответственно рассылает потоки.

Децентрализованный - диспетчер исключается. Самим ФУСом выбирается команда.



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

Опр. Параллельный алгоритм - это описание процесса обработки информации, ориентированное на реализацию коллективом вычислителей (ВС).

Параллельный алгоритм решения задач составляет основу параллельной программы Р.

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

Существуют 3 периодики распараллеливания сложных задач:

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

2) Глобальное распараллеливание происходит на уровне процедур (на уровне программных модулей)

3) Смешанный объединение первого и второго способа

В программе создаются программные модули.

Сложность - найти параллельные участки.

С={Ci}, i=1…n.

Локальное распараллеливание:

1-й этап распараллеливания: При локальном распараллеливании на этапе трансляции транслятором выдел-ся участок проги, к-рый м. вып-ся параллельно. Реализ-ся распараллеливание с помощью аппар-х ср-в (мультискалярный процесс вычисления и мультитредовый). В мультискалярных системах имеется устройство предсказания переходов (в кэш записываются след. команды). Из КЭШа берутся 4 команды, сортируются в соответствии с типами процессоров и поступают в соотв-щие блоки переименования регистров, к-рые переназначают исп-мые переменные в регистрах. Созд-ся очереди команд для вып-я с фиксир-й и плавающей точкой. Очередные команды поступают на соотв-щие АЛУ.

2-й этап распараллеливания: Получаемые рез-ты фиксир-ся в КЭШе данных для исп-я другими командами или для передачи их в системную шину.

Мультитредовый процесс - это ВС, сост-щая из сов-ти вычислителей, содержащих планировщик. Прога разбивается на треды (программные модули) с пом-ю аппар-х и/или программных ср-в. Тред - это участок проги, к-рый м. вып-ся без передачи упр-я из внутренних его частей. Пример - процедура, функция, участок проги, расположенный на одном участке в базовом регистре, программная реализация одной итерации цикла или всего цикла. Имеется коммутатор и БД, к-рые обеспечивают своевременную подачу данных в соотв-ии с требуемой послед-ю вып-я тредов.

Большую роль при организации мультитредовых структур играет программист или транслятор. Хотя не менее важную роль м. играть и ОС, и процессор. Процессор д. вып-ть треды, но есть еще упр-е тредами, т.е. выборка, порождение, упр-е порядком вып-я, назначение ресурсов, коммуникации между тредами. Эти задачи решаются ОС. Самый сложный процесс, а именно создание тредов, д. решать программист или в крайнем случае компилятор. При этом д. формироваться спец. Указатели для аппар-х ср-в , позволяющие в дальнейшем упростить работу процессора. Важной чертой мультитредовых процессов явл-ся возм-ть эффективной реализации доступа к устр-вам I/O и к контроллерам сетевых адаптеров и коммуник-х ср-в. К мультитредовым с-мам м. отнести процессор типа транспьютер. Т.о. мультитредовая стр-ра служит след-м шагом в методах распараллеливания программных и аппаратных вычислений.

ГЛОБАЛЬНОЕ РАСПАРАЛЛЕЛИВАНИЕ хар-но тем, что анализир-ся стр-ра решаемой задачи на Ур-не программных модулей и строится на основе времен конца и начала их вып-я, а также схем обмена данными между ними, распределение программных модулей между вычислителями. Вып-я прога разбив-ся на программные модули, исп-я различные критерии (размещение модулей на 1м или 2х экранах дисплея). Задача разбиения на модули сложна и реш-ся разработчиком проги.

37. Архитектурные аспекты при создании ОС ВС

1. Архитектура ВС должна удовлетворять требованию организации в системе параллельных вычислений во всех режимах. Опыт показал, что круг задач, допускающих такое представление, достаточно широк. Более того, разработанные методики обеспечивают построение идентичных ветвей и, таких, что каждая из ветвей состоит из операторов - преобразователей данных, находящихся в памяти, выделенного для этой ветви вычислителя. И относительно редко требует обращения к памяти других вычислителей. Данное свойство снижает остроту вопроса о влиянии структуры ВС - сети межмашинных связей и, в частности, системного устройства на время обращения к общей рассредоточенной по вычислителям памяти системы.

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

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

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

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

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

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

4. Простота реализации обмена по рассмотренным схемам позволяет использовать в основном регулярные однородные структуры ВС и конфигурации - подсистемы, программно настраиваемые в пределах ВС, в виде линейки, кольца, решетки, гиперкуба и тора.

5. Для записи параллельных алгоритмов решения сложных задач эффективны версии языков высокого уровня: фортран, алгол, которые являются расширениями последовательных языков, средствами организации взаимодействия меду вычислителями. Объем системного расширения составляет несколько % от общего объема транслятора. Экспериментами установлено, что сложность программирования на параллельных языках имеет тот же порядок, что и на последовательных. Увеличение трудоемкости вкладывается в 10% от трудоемкости последовательного программирования.

6. Простота схем обмена данных по машинам ведет к простоте записи реализации параллельных программ. Затраты на взаимодействие между программами составляет <10% общего объема программы.

7. Трансляционно-циклическая, трансляционная и конверсионно-параллельная схема обмена обеспечивает одновременно ВС и составляет не менее 90% всех схем, реализуемых в процессе выполнения параллельных программ сложных задач. Время обмена информацией между ветвями параллельной программы, отнесенные к общему времени ее выполнения асимптотически стремится к 0 с ростом объема исходных данных.

39. Основы функционирования ВС типа микроc-Т

Вершины обозначаются Bj соединяются через 2 и через 3

Транспьютер - сверхбольшая интегральная схема, которая содержит

- процессор;

- коммуникационные каналы для межпроцессорной связи;

- оперативную память; и

- кэш небольшого объема.

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

40. Использование ВС для решения задачи системы линейных уравнений

Вопрос на 5, так как на лекциях не разбирался. Можно вместо него объяснить метод итераций или умножение матриц!?

Наброски, данные на консультации:

Xi(k+1) - значение i-ой переменной, рассчитываемое в k+1 стадии.

bi - вектор-столбец.

ai j - матрица коэффициентов перед переменными.

max{|xik+1 - xik |} < д - условие выхода из цикла.

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

Размещено на Allbest.ru