Лекции по дисциплине «параллельные вычисления» - Лекции.

Параллельная обработка данных

Информатика, кибернетика и программирование

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

Лекция 1

Параллельная обработка данных

План

1. Ярусно-параллельная форма алгоритма.

2. Автоматическое обнаружение параллелизма.

3. Степень и уровни параллелизма.

4. Виды параллелизма.

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

Производительность параллельных ВС зависит от многих факторов и в значительной степени от архитектуры и структуры системы (рисовать структуру параллельной системы и объяснять):

От степени и уровня параллелизма в системе;

От организации передачи данных между параллельно работающими процессорами;

От системы коммутации;

От взаимодействия процессоров и памяти;

От соотношения между аппаратной и программной реализацией макрооперации.

В основу параллельной обработки могут быть положены различные принципы:

Пространственный параллелизм;

Временной параллелизм:

1. Конвейеризация.
2. Векторизация.
3. Матричный.
4. Систолический.
5. Организация структуры обработки потока данных.
6. Организация системы на основе структуры гиперкуб.
7. Динамическая перестройка структуры ВС.

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

1. Ярусно-параллельная форма алгоритма

Наиболее общей формой представления алгоритмов является информационно-управляющий граф алгоритма, который отражает зависимость по данным между операторами алгоритма и безусловные и условные переходы в программе. Такой граф в неявной форме содержит все виды параллелизма для выбранного метода решения задачи. Более определенной формой представления параллелизма задач является аппарат ярусно-параллельной формы (ЯПФ).

Алгоритм в ярусно-параллельной форме представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви) независящие друг от друга.

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

При построении ЯПФ опираются на базовый набор примитивных операций (БНО). Ярусно-параллельная форма характеризуется следующими параметрами :

1. Длина графа (количество ярусов) – L .

2. Ширина i -го яруса - b i .

3. Ширина графа ярусно-параллельной формы – B = max (b i ).

4. Средняя ширина графа ЯПФ – В ср – .

5. Коэффициент заполнения i -го яруса – k i – .

6. Коэффициент разброса операций в графе - Q j i – , j БНО , где - количество j -го типа операций в i -м ярусе.

7. Минимальное необходимое количество вычислителей (из БНО) для реализации алгоритма, представленного данным графом в ЯПФ.

8. Минимальное время решения алгоритма (сумма времен срабатывания вычислителей с максимальным объемом вычислений по каждому ярусу) – Т min .

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

2. Автоматическое обнаружение параллелизма

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

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

Характер изменения степени параллелизма при подготовке машинной программы показан на рис. 2.2.

потенциальный параллелизм

Метод

решения

Исходный текст

Машинная программа

Рис. 2.2. Изменение потенциального параллелизма при разработке программы:

1 – система параллельного программирования;

2 – последовательное программирование и

векторизующий компилятор

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

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

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

Явная параллельная обработка может быть обнаружена среди процессов i и j (i ≠ j ), удовлетворяющих следующим условиям:

входные данные одного процесса не должны модифицироваться (записываться) другим процессом

никакие два процесса не должны модифицировать общие переменные

а) R i W j =;

б) W i R j =;

в) W i W j =;

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

а) уменьшение высоты деревьев арифметических выражений (рис.2.3). Для арифметических выражений с n переменными или константами уменьшение высоты дерева позволяет достигнуть ускорения обработки порядка O (n / log 2 n ) при использовании O (n ) процессоров;

б) преобразование линейных рекуррентных соотношений;

((a + b) + c) + d

(a + b)+ (c + d )

Рис. 2.3. Уменьшение высоты дерева

в) замена операторов;

г) преобразование блоков условных переходов и циклов к каноническому виду;

д) распределение циклов.

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

При преобразовании параллелизма программы учитывают: 1) схему размещения данных в памяти; 2) адресацию памяти (индексирование); 3) выбор маршрута данных (способ соединения процессоров и ЗУ).

Рис.2.4. Хранение

матрицы со сдвигом

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

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

3. Степень и уровни параллелизма

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

1) Низкая степень: от 2 до 10 процессоров.

2) Средняя степень: от 10 до 100 процессоров.

3) Высокая степень: от 100 до 10 4 процессоров.

4) Сверхвысокая степень: от 10 4 до 10 6 процессоров.

Рис. 2.5. Профиль параллелизма

Графическое представление параметра D (t ) как функции времени называют профилем параллелизма программы . Изменения в уровне загрузки процессоров за время наблюдения зависят от многих факторов (алгоритма, доступных ресурсов, степени оптимизации, обеспечиваемой компилятором и т.д.). На рис. 2.5 показан типичный профиль параллелизма.

В прикладных программах имеется широкий диапазон потенциального параллелизма. В вычислительно интенсивных программах в каждом цикле параллельно могут выполнятся от 500 до 3500 арифметических операций, если для этого имеется существующая вычислительная среда. Однако даже правильно спроектированный суперскалярный процессор способен поддерживать от 2 до 5,8 команды за цикл. Такое падение связано в первую очередь с коммуникационными и системными издержками.

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

Рассматривают алгоритмический и схемный уровни параллелизма.

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

1. Уровень заданий:

а) между заданиями;

б) между фазами заданий.

2. Программный уровень:

а) между частями программы (части одной задачи выполняются на множестве вычислителей);

б) в пределах циклов.

(Если отдельные итерации в цикле на зависят друг от друга. Например: For I:=1 to N do A(I):=B(I) + C(I))

3. Командный уровень:

а) между фазами выполнения команд.

4. Арифметический и разрядный уровень:

а) между элементами векторной операции;

б) внутри логических схем АЛУ.

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

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

Параллельная обработка может быть реализована на следующих схемных уровнях:

1. На уровне логических вентилей и элементов памяти. Это низший уровень – уровень транзисторов. Здесь из логических вентилей строят параллельные логические схемы (ЛС ) (например: параллельный сумматор).

2. Уровень логических схем и простых автоматов с памятью. Из логических схем строят параллельный элементарный автомат (ЭА ).

3. Уровень регистров и интегральных схем памяти. На элементарных автоматах получают параллельные схемы микропроцессоров (МП ).

4. Уровень элементарных микропроцессоров. Из микропроцессоров строят параллельные макропроцессоры для выполнения среднеблочных операций (МАП ).

5 . Уровень макропроцессоров, реализующих крупные операции. Здесь реализуется параллелизм макроопераций. На макропроцессорах строят параллельные многопроцессорные системы (МПС ).

6. Уровень вычислительных машин, процессоров и программ. Высший уровень параллелизма – из многопроцессорных систем получают параллельные вычислительные системы (ВС ).

4. Виды параллелизма

4.1. Естественный параллелизм и

параллелизм множества объектов

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

Задача обладает естественным параллелизмом , если в её исходной постановке она сводится к операции над многомерными векторами, многомерными матрицами или над решётчатыми функциями (рис.2.6). Здесь не используются промежуточные результаты задач. Каждая задача программируется независимо от других. Этот вид параллелизма не требует объединения ЭВМ в комплексы. Однако увеличение числа независимых задач в СОД повышает пропускную способность системы. Например: обработка транзакций к БД на многопроцессорных серверах.

1 задача

2 задача

Рис. 2.6. Информационный граф задания, характеризующегося естественным параллелизмом

Орi

Орi

Орi

Орi

Орi+1

Орi+1

Орi+1

Орi+1

у 1

у 2

у 3

у 4

Рис. 2.7. Информационный граф

задачи, характеризующейся

параллелизмом множества объектов

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

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

включает два типа операций: попарное произведение компонент векторов и затем "интегральную операцию" (операция над n-мерным вектором) суммирование между собой всех компонент этого вектора.

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

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

Параллелизм множества объектов характеризуется следующими параметрами :

1. Суммарная длина программы L – суммируются длины всех операторов по всем ветвям.

2. Средняя длина программы L ср – вычисляется исходя из ранга задачи.

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

3. Величина расхождения задачи D

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

4.2. Параллелизм независимых ветвей

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

Ветвь программы Y не зависит от ветви X , если:

Рис. 2.8. Информационный граф задачи, характеризующейся

параллелизмом независимых ветвей

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

1. между ними нет связи по рабочим полям памяти ;
2. они должны выполняться по разным программам ;
3. независимы по управлению , т.е. условие выполнения ветви Y не должно зависеть от признаков, вырабатываемых при выполнении ветви X или ветви, от нее зависящей.

4.3. Параллелизм смежных операций или

локальный параллелизм

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

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

1. Показатель связности смежных операций – это вероятность того, что результат некоторой операции будет использован в следующей за ней операции. Чем меньше связность операции, тем больше для нее глубина параллелизма смежных операций. Обычно величина имеет значения 0,10,5.

2. Вероятность того, что, начиная от данной операции, имеется цепочка длиной не менее l l

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

4. Глубина параллелизма смежных операций L ПСО – это математическое ожидание длины цепочки операций, которые можно выполнять одновременно

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

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

________________________________________________________________________________________________

Курс «Организация ЭВМ»

10 -

(курсовой проект)

Таким образом, основные признаки, характеризующие супер-ЭВМ , следующие:

• самая высокая производительность;
• самый современный технологический уровень (например, GaAs -технология);
• специфические архитектурные решения, направленные на повышение быстродействия (например, наличие операций над векторами);
• цена, обычно свыше 1-2 млн. долларов.

Какой из факторов является решающим в достижении современных фантастических показателей производительности? Обратимся к историческим фактам. На одном из самых первых компьютеров EDSAC (1949 г.), имевшем время такта 2 мкс, можно было выполнить в среднем 100 арифметических операций в секунду. А пиковая производительность суперкомпьютера CRAY C90 с временем такта порядка 4 нс - около 1 миллиарда арифметических операций в секунду. Таким образом, производительность компьютеров за этот период возросла примерно в 10 миллионов раз, а время такта уменьшилось лишь в 500 раз. Следовательно, увеличение производительности происходило и за счет других факторов, важнейшим среди которых является использование новых архитектурных решений, в частности - принципа параллельной обработки данных .

Имеет две разновидности: конвейерность и параллельность.

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

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

Закон Амдала

Закон Амдала

S<= 1/

где S - ускорение, f - доля операций, которые нужно выполнить последовательно, p - число процессоров.

Следствие из закона Амдала : для того чтобы ускорить выполнение программы в q раз, необходимо ускорить не менее чем в q раз и не менее чем (1-1/q) -ую часть программы. Следовательно, если нужно ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение на не менее чем 99,99 % кода!

История появления параллелизма в архитектуре ЭВМ

Все современные процессоры используют тот или иной вид

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

Северо - Казахстанский государственный университет им. М. Козыбаева

Факультет информационных технологии

Кафедра Информационных систем

Процесс параллельной обработки данных

Выполнила: Махкамбаева А.С.

Проверил: Касимов И. Р.

Петропавловск, 2014

Введение

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

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

В 1967 году Джин Амдал сформулировал закон ограничения роста производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время ее выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». Согласно этому закону, ускорение выполнения программы за счет распараллеливания её инструкций ограничено временем, необходимым для выполнения её последовательных инструкций.

Классификация по Флинну

процесс синхронизация доступ планирование

В основе классификации лежат два понятия: потоки команд и потоки данных. Система с N процессорами имеет N счетчиков команд и, следовательно, N потоков команд.

SISD (Single Instruction, Single Data) -- архитектура компьютера, в которой один процессор выполняет один поток команд, оперируя одним потоком данных. Для данного класса возможен только псевдопараллелизм.

SIMD (Single Instruction, Multiple Data) -- архитектура компьютера, позволяющая обеспечить параллелизм на уровне данных. Основная идея подхода, основанного на параллелизме данных, заключается в том, что одна операция выполняется сразу над всеми элементами массива данных. Эти системы обычно имеют большое количество процессоров, от 1024 до 16384, которые могут выполнять одну и ту же инструкцию, созданную единственным блоком управления, относительно разных данных. В любой момент в каждом процессоре выполняется одна и та же команда, но обрабатываются различные данные. Реализуется синхронный параллельный вычислительный процесс.

MISD (Multiple Instruction, Simple Data) -- архитектура компьютера, где несколько функциональных модулей (два или более) выполняют различные операции над одними данными. Отказоустойчивые компьютеры, выполняющие одни и те же команды избыточно с целью обнаружения ошибок, как следует из определения, принадлежат к этому типу.

MIMD (Multiple Instruction, Multiple Data) -- архитектура компьютера, где несколько независимых процессоров работают как часть большой системы. Обработка разделена на несколько потоков (обеспечивается параллелизм), каждый с собственным аппаратным состоянием процессора, в рамках единственного определённого программным обеспечением процесса или в пределах множественных процессов.

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

OpenMP (Open Multi-Processing) -- открытый стандарт для распараллеливания программ на языках С, С++ и Фортран. Описывает совокупность команд, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью. OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» поток создает набор подчиненных потоков и задача распределяется между ними.

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

Следующий цикл складывает массивы «a» и «b» поэлементно. Все, что требуется для параллельного выполнения в этом случае - одна прагма, вставленная непосредственно перед циклом.

#pragma omp parallel for

for (i=0; i < numPixels; i++)

c[i] = a[i]+b[i];

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

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

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

#pragma omp parallel for

for (i=2; i < 10; i++)

factorial[i] = i * factorial;

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

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

MPI (Message Passing Interface) -- программный интерфейс для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. В первую очередь MPI ориентирован на системы с распределенной памятью. Существуют реализации для языков Фортран, С и С++.

В первой версии MPI количество процессов (ветвей) задается в момент запуска программы, т.е. не существует возможности порождать ветви динамически. В версии 2.0 эта возможность появилась.

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

Для C, общий формат имеет вид

rc = MPI_Xxxxx(parameter, ...);

Заметим, что регистр здесь важен. Например, MPI должно быть заглавным, так же как и первая буква после подчеркивания. Все последующие символы долны быть в нижнем регистре. Переменная rc - есть некий код возврата, имеющий целый тип. В случае успеха, он устанавливается в MPI_SUCCESS. Программа на C должна включать файл "mpi.h".

Сообщения MPI состоят из двух основных частей: отправляемые/получаемые данные, и сопроводительная информация (записи на конверте /оболочке/), которая помогает отправить данные по определенному маршруту.

Данным соответствует старт буфера, число, тип данных. Буфер - это просто память, которую компилятор выделил для переменной (часто массива) в вашей программе. Старт буфера - адрес, где данные начинаются. Например, начало массива в вашей программе. Число - количество элементов (не байтов!) данных в сообщении. Тип данных определяет размер одного элемента.

К информации «на обложке» относятся ранг в коммуникаторе - идентификатор процесса в коммуникационном поле, тег - произвольное число, которое помогает различать сообщения и сам коммуникатор, проверка которого обеспечивает передачу внутри одного коммуникационного поля.

Параллельная обработка данных

Существует несколько способов разделения обязанностей между процессами:

* делегирование («управляющий-рабочий»);

* сеть с равноправными узлами;

* конвейер;

* «изготовитель-потребитель».

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

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

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

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

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

Синхронные и асинхронные процессы

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

Асинхронные процессы выполняются независимо один от другого. Это означает, что процесс А будет выполняться до конца безотносительно к процессу В. Между асинхронными процессами могут быть прямые родственные («родитель-сын») отношения, а могут и не быть. Если процесс А создает процесс В, они оба могут выполняться независимо, но в некоторый момент родитель должен получить статус завершения сыновнего процесса. Если между процессами нет прямых родственных отношений, у них может быть общий родитель.

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

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

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

Межпроцессное взаимодействие

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

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

Сообщение - метод взаимодействия, когда один процесс посылает сообщение второму, а тот получает его. Если сообщение не пришло - второй процесс блокируется (ожидает сообщения) или сразу возвращает код ошибки.

С системами передачи сообщения связано большое количество проблем. Например, сообщение может потеряться. Чтобы избежать потери, получатель отсылает обратно сообщение с подтверждением приема. Если отправитель не получает подтверждения через некоторое время, он отсылает сообщение еще раз.

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

Семафор -- объект, позволяющий войти в заданный участок кода (обычно - критическую секцию) не более чем n процессам.

С семафором возможны три операции:

1) init(n); - инициализация счетчика (число, переданное счетчику, является количеством процессов, которые могут одновременно обращаться к критической секции)

2) wait(); - ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу.

3) leave(); - увеличить счетчик на единицу.

Перед обращением процесса к критической секции необходимо вызвать метод wait(), после выполнения которого гарантировано, что количество процессов, одновременно обращающихся к ней не превышает n-1. Тогда процесс может продолжить работу и выполнить метод leave() после работы с критической секцией, тем самым дав знать остальным процессам, что “место освободилось”.

Если количество вызовов методов wait() и leave() не совпадает, то работа системы будет не корректной так же, как и в случае взаимной блокировки процессов - ситуации, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами:

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

Мьютексы -- это простейшие двоичные семафоры, которые могут находиться в одном из двух состояний -- отмеченном или неотмеченном (открыт и закрыт соответственно). Когда какой-либо поток, принадлежащий любому процессу, становится владельцем объекта mutex, последний переводится в неотмеченное состояние. Если задача освобождает мьютекс, его состояние становится отмеченным.

Задача мьютекса -- защита объекта от доступа к нему других потоков, отличных от того, который завладел мьютексом. В каждый конкретный момент только один поток может владеть объектом, защищённым мьютексом. Если другому потоку будет нужен доступ к переменной, защищённой мьютексом, то этот поток засыпает до тех пор, пока мьютекс не будет освобождён.

Test-and-set -- простая неразрывная (атомарная) процессорная инструкция, которая копирует значение переменной в регистр, и устанавливает некое новое значение. Во время исполнения данной инструкции процессор не может прервать её выполнение и переключится на выполнение другого потока. Если используется многопроцессорная архитектура, то пока один процессор выполняет эту инструкцию с ячейкой памяти, то другие процессоры не могут получить доступ к этой ячейке.

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

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

Одним из преимуществ алгоритма является то, что он не требует специальных Test-and-set инструкций и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость к случаю только с двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).

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

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

Общий принцип алгоритмом Петерсона для 2-х потоков:

Размещено на http://www.allbest.ru/

Планирование процессов

Планирование - обеспечение поочередного доступа процессов к одному процессору.

Планировщик - отвечающая за это часть операционной системы.

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

Алгоритм планирования с вытеснением (приоритетный) - требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.

Процессы размещаются в приоритетных очередях в соответствии со стратегией Планирования. В системах UNIX/Linux используются две стратегии планирования: FIFO (сокр. от First In First Out, т.е. первым прибыл, первым обслужен) и RR (сокр. От round-robin, т.е. циклическая).

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

RR-планирование совпадает с FIFO-планированием с одним исключением: после истечения кванта времени процесс помещается в конец своей приоритетной очереди, и процессору назначается следующий (по очереди) процесс.

Для обеспечения параллельной работы процессов может подойти приоритетное планирование. Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом. Приоритет может быть динамический и статический. Динамический приоритет может устанавливаться так: П=1/Т, где Т- часть использованного в последний раз кванта (если использовано 1/50 кванта, то приоритет 50. Если использован весь квант, то приоритет 1).

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

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

Подобные документы

Структура, специфика и архитектура многопроцессорных систем; классификация Флинна. Организация взаимного исключения для синхронизации доступа к разделяемым ресурсам. Запрещение прерываний; семафоры с драйверами устройств. Кластеры распределения нагрузки.

курсовая работа , добавлен 07.06.2014


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

презентация , добавлен 24.01.2014


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

курсовая работа , добавлен 02.12.2009


Основные функции и процессы подсистемы управления процессами. Диспетчеризация процессов (потоков). Алгоритмы планирования выполнения потоков. Назначение и разновидности приоритетов в операционных системах. Функции подсистемы управления основной памятью.

презентация , добавлен 20.12.2013


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

дипломная работа , добавлен 09.09.2010


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

курсовая работа , добавлен 21.06.2013


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

курсовая работа , добавлен 21.06.2013


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

лекция , добавлен 05.02.2009


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

презентация , добавлен 24.07.2013


Классификация параллельных ВС. Системы с общей и распределенной памятью. Конвейеры операций. Производительность идеального конвейера. Суперскалярные архитектуры. VLIW-архитектура. Предсказание переходов. Матричные процессоры. Законы Амдала и Густафсона.

">Лекция " xml:lang="en-US" lang="en-US">6

">Параллельная обработка данных

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

В основу параллельной обработки могут быть положены различные принципы:

Пространственный параллелизм;

Временной параллелизм:

1. Конвейеризация.
2. ">Векторизация.
3. ">Матричный.
4. ">Систолический.
5. ">Организация структуры обработки потока данных.
6. ">Организация системы на основе структуры гиперкуб.
7. ">Динамическая перестройка структуры ВС.

">Описание любого алгоритма является иерархическим, основанным на свойстве вложенности. При программировании выделяют уровни вложенности: задания, задачи, подзадачи (процессы), макрооперации, операции.

">1. Ярусно-параллельная форма алгоритма

">Наиболее общей формой представления алгоритмов является информационно-управляющий граф алгоритма. Более определенной формой представления параллелизма задач является аппарат ярусно-параллельной формы (ЯПФ).

">Алгоритм в ярусно-параллельной форме представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви) независящие друг от друга.

">На графе можно обозначить переходы, означающие передачу результатов вычисления примитивной операции из одного яруса к операции из следующего яруса. Ярусы делятся по переходам. Могут быть «пустые» переходы и «пустые» примитивные операции.

">При построении ЯПФ опираются на базовый набор примитивных операций (БНО). Ярусно-параллельная форма характеризуется следующими параметрами:

">1. Длина графа (количество ярусов) – " xml:lang="en-US" lang="en-US">L ">.

">2. Ширина " xml:lang="en-US" lang="en-US">i ">-го яруса - " xml:lang="en-US" lang="en-US">b ;vertical-align:sub" xml:lang="en-US" lang="en-US">i ">.

">3. Ширина графа ярусно-параллельной формы – " xml:lang="en-US" lang="en-US">B ">= " xml:lang="en-US" lang="en-US">max ">(" xml:lang="en-US" lang="en-US">b ;vertical-align:sub" xml:lang="en-US" lang="en-US">i ">).

">4. Средняя ширина графа ЯПФ – В ;vertical-align:sub">ср "> – ">.

">5. Коэффициент заполнения " xml:lang="en-US" lang="en-US">i ">-го яруса – " xml:lang="en-US" lang="en-US">k ;vertical-align:sub" xml:lang="en-US" lang="en-US">i "> – ">.

">6. Коэффициент разброса операций в графе - " xml:lang="en-US" lang="en-US">Q ;vertical-align:super" xml:lang="en-US" lang="en-US">j ;vertical-align:sub" xml:lang="en-US" lang="en-US">i "> – ">, " xml:lang="en-US" lang="en-US">j ">БНО, где ">- количество " xml:lang="en-US" lang="en-US">j ">-го типа операций в " xml:lang="en-US" lang="en-US">i ">-м ярусе.

">7. Минимальное необходимое количество вычислителей (из БНО) для реализации алгоритма, представленного данным графом в ЯПФ.

">8. Минимальное время решения алгоритма (сумма времен срабатывания вычислителей с максимальным объемом вычислений по каждому ярусу) – Т ;vertical-align:sub" xml:lang="en-US" lang="en-US">min ">.

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

">2. Автоматическое обнаружение параллелизма

">Возможны два пути построения параллельного алгоритма: непосредственно из постановки задачи или путем преобразования последовательного алгоритма.

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

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

">В последовательной программе различают явную и скрытую параллельную обработку.

">При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных " xml:lang="en-US" lang="en-US">R "> и выходных (записываемых) переменных " xml:lang="en-US" lang="en-US">W "> каждого процесса.

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

">а) уменьшение высоты деревьев арифметических выражений (рис.6.3);

">б) преобразование линейных рекуррентных соотношений;

">в) замена операторов;

">г) преобразование блоков условных переходов и циклов к каноническому виду;

">д) распределение циклов.

">Параллельные архитектуры достигают высокой производительности, если преобразование параллелизма учитывает особенности архитектуры ВС, на которой предполагается выполнение алгоритма.

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

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

">3. Степень и уровни параллелизма

">Степень параллелизма "> (" xml:lang="en-US" lang="en-US">D ">) "> – это порядок числа параллельно работающих устройств в системе при реализации алгоритма задач, при условии, что количество процессоров (обрабатывающих устройств) не ограничено.

">1) Низкая степень: от 2 до 10 процессоров.

">2) Средняя степень: от 10 до 100 процессоров.

">3) Высокая степень: от 100 до 10 ;vertical-align:super">4 "> процессоров.

">4) Сверхвысокая степень: от 10 ;vertical-align:super">4 "> до 10 ;vertical-align:super">6 "> процессоров.

">Графическое представление параметра " xml:lang="en-US" lang="en-US">D ">(" xml:lang="en-US" lang="en-US">t ">) как функции времени называют профилем параллелизма программы. На рис.6.5 показан типичный профиль параллелизма.

">В прикладных программах имеется широкий диапазон потенциального параллелизма. В вычислительно интенсивных программах в каждом цикле параллельно могут выполнятся от 500 до 3500 арифметических операций, если для этого имеется существующая вычислительная среда. Однако даже правильно спроектированный суперскалярный процессор способен поддерживать от 2 до 5,8 команды за цикл. Такое падение связано в первую очередь с коммуникационными и системными издержками.

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

Рассматривают алгоритмический и схемный уровни параллелизма.

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

1. Уровень заданий:

а) между заданиями;

б) между фазами заданий.

2. Программный уровень:

а) между частями программы;

б) в пределах циклов.

3. Командный уровень (между фазами выполнения команд).

4. Арифметический и разрядный уровень:

">а) между элементами векторной операции;

">б) внутри логических схем АЛУ.

">Каждый из уровней характеризуется определенными свойствами, исходя из которых, разработаны специальные структуры вычислительных средств. Командный уровень реализуется в любых современных ЭВМ, включая и персональные ЭВМ.

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

">Параллельная обработка может быть реализована на следующих схемных уровнях:

">1. На уровне логических вентилей и элементов памяти (рис.6.6).

">2. Уровень логических схем и простых автоматов с памятью (рис.6.7).

">3. Уровень регистров и интегральных схем памяти (рис.6.8).

4. Уровень элементарных микропроцессоров (рис.6.9).

">5. Уровень макропроцессоров, реализующих крупные операции (рис.6.10).

6. Уровень вычислительных машин, процессоров и программ (рис.6.11).

">4. Виды параллелизма

">4.1. Естественный параллелизм и

">параллелизм множества объектов

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

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

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

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

">4.2. Параллелизм независимых ветвей

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

">Ветвь программы Y не зависит от ветви X, если:

">- между ними нет функциональных связей, т.е. ни одна из входных переменных ветви Y не является выходной переменной ветви X либо какой-нибудь ветви, зависящей от X;

">- между ними нет связи по рабочим полям памяти;

">- они должны выполняться по разным программам;

">- независимы по управлению, т.е. условие выполнения ветви Y не должно зависеть от признаков, вырабатываемых при выполнении ветви X или ветви, от нее зависящей.

">4.3. Параллелизм смежных операций или

">локальный параллелизм

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

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

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

">5. Модель задачи

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

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

1. скалярных участков (СК);
2. участков с параллелизмом независимых ветвей (ВТ);
3. векторных участков (ВК).

Модель задачи – это совокупность параметров, характеризующих параллельную программу

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

">Рис.6.15. Соотношение общего числа вычислений, приходящихся на разные участки алгоритма в модели задачи

" xml:lang="en-US" lang="en-US">W ">ск

" xml:lang="en-US" lang="en-US">Wвт

" xml:lang="en-US" lang="en-US">W ">вк

" xml:lang="en-US" lang="en-US">m ;vertical-align:sub">ск

" xml:lang="en-US" lang="en-US">m ;vertical-align:sub" xml:lang="en-US" lang="en-US">вт

" xml:lang="en-US" lang="en-US">m ;vertical-align:sub">вк

" xml:lang="en-US" lang="en-US">А

" xml:lang="en-US" lang="en-US">В

" xml:lang="en-US" lang="en-US">C

объем вычислений

относительная длина

лекции (34 часа), зачет

Кафедра, отвечающая за курс : АСВК

Составитель программы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.,

Лекторы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.

Аннотация

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

Программа

2. Основные классы современных параллельных вычислительных систем. Компьютеры с общей памятью, примеры, причины снижения производительности на реальных программах. Архитектуры SMP, NUMA, ccNUMA. Коммутация процессоров и модулей памяти, шина, матричный коммутатор, омега-сеть. Векторно-конвейерные вычислительные системы, примеры, причины снижения производительности. Компьютеры с распределенной памятью, примеры, причины снижения производительности. Топология связи между процессорами: звезда, решетка, трехмерный тор, двоичный гиперкуб, их свойства. Вычислительные кластеры, примеры, латентность и пропускная способность различных коммуникационных технологий. Архитектуры с параллелизмом на уровне машинных команд, VLIW, суперскалярность.

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

4. Производительность параллельных вычислительных систем. Универсальность и специализация компьютеров, производительность спецпроцессоров. Закон Мура. Методы оценки производительности. Введение единого числового параметра, Mflops, MIPS. Пиковая и реальная производительность компьютеров. Тест Linpack и его варианты. Наборы взаимодополняющих тестовых программ, STREAM и NPB.

5. Графовые модели программ. Граф управления и информационный граф программы. Информационная и операционная история реализации программ. Граф алгоритма как компактная параметрическая форма представления информационной истории. Информационная независимость операций и возможность их параллельного исполнения. Длина критического пути графа алгоритма как мера степени параллельности. Конечный и массовый параллелизм, координатный и скошенный параллелизм. Эквивалентные преобразования программ, элементарные преобразования циклов.

6. Неоднородные распределенные вычислительные системы. Метакомпьютеры и метакомпьютинг, существующие метакомпьютерные проекты. Отличительные свойства метакомпьютеров. Понятие GRID, базовые компоненты и сервисы, существующие проекты GRID-сегментов, понятие виртуальной организации.

Литература

2. Королев Л.Н. Архитектура процессоров электронных вычислительных машин. – М.: Изд. факультета ВМК МГУ, 2003.

3. В.В.Корнеев. Параллельные вычислительные системы. – М.: Изд-во "Нолидж", 1999. – 320с.

4. Материалы информационно-аналитического центра по параллельным вычислениям Parallel.ru.

Дополнительная литература

MPI: Учебное пособие. – М.: Изд-во МГУ, 2004. - 71 с.