Ирина Эланс

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

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

Анотація

Робота присвячена оцінці розміру можливого підвищення продуктивності початково послідовної програми після перетворення її алгоритму в паралельний. У якості послідовного алгоритму розглядається обчислення певного інтеграла.

Робота викладена на 42 сторінках, містить 11 рисунків, 1 додаток.

Аннотация

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

Работа изложена на 42 страницах, содержит 11 рисунков, 1 приложение.

The summary

The work is devoted to an evaluation of possible increase size of the initially consecutive program productivity after transformation of its algorithm in parallel. As a successive algorithm the calculation of certain integral is examined.

The work is stated on 42 pages, contains 11 figures, 1 application.

Содержание

Введение 5

1 Описание предметной области 6

1.1 Конвейерная обработка 6

1.2 Параллельная обработка 10

1.3 Постановка задачи 12

2 Эскизный проект 14

2.1 Диаграмма вариантов использования 14

2.2 Диаграммы взаимодействий 16

2.2.1 Диаграмма последовательности 16

2.2.2 Диаграмма кооперации 17

2.3 Осуществление передачи данных при виртуальном соединении 18

3 Технический проект 20

4 Полученные результаты 25

Выводы 28

Список использованной литературы 29

Приложение А - Текст программы 30

Введение

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

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

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

1 Описание предметной области

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

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

1.1 Конвейерная обработка

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

Выполнение типичной команды можно разделить на следующие этапы:

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

декодирование команды / выборка операндов из регистров - ID;

выполнение операции / вычисление эффективного адреса памяти - EX;
обращение к памяти - MEM;
запоминание результата - WB.

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

Номер команды	Номер такта
Номер команды	1	2	3	4	5	6	7	8	9
Команда i	IF	ID	EX	MEM	WB
Команда i+1		IF	ID	EX	MEM	WB
Команда i+2			IF	ID	EX	MEM	WB
Команда i+3				IF	ID	EX	MEM	WB
Команда i+4					IF	ID	EX	MEM	WB

Рисунок 1 – Диаграмма работы конвейера

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

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

В качестве примера рассмотрим неконвейерную машину с пятью этапами выполнения операций, которые имеют длительность 50, 50, 60, 50 и 50 нс соответственно (рис. 5.5). Пусть накладные расходы на организацию конвейерной обработки составляют 5 нс. Тогда среднее время выполнения команды в неконвейерной машине будет равно 260 нс. Если же используется конвейерная организация, длительность такта будет равна длительности самого медленного этапа обработки плюс накладные расходы, т.е. 65 нс. Это время соответствует среднему времени выполнения команды в конвейере. Таким образом, ускорение, полученное в результате конвейеризации, будет равно:

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

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

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

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

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

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

Известны три возможных конфликта по данным в зависимости от порядка операций чтения и записи. Рассмотрим две команды i и j, при этом i предшествует j. Возможны следующие конфликты:

RAW (чтение после записи) - j пытается прочитать операнд-источник данных прежде, чем i туда запишет. Таким образом, j может некорректно получить старое значение. Это наиболее общий тип конфликтов.

WAR (запись после чтения) - j пытается записать результат в приемник прежде, чем он считывается оттуда командой i, так что i может некорректно получить новое значение. Этот тип конфликтов как правило не возникает в системах с централизованным управлением потоком команд, обеспечивающих выполнение команд в порядке их поступления, так как последующая запись всегда выполняется позже, чем предшествующее считывание. Особенно часто конфликты такого рода могут возникать в системах, допускающих выполнение команд не в порядке их расположения в программном коде.

WAW (запись после записи) - j пытается записать операнд прежде, чем будет записан результат команды i, т.е. записи заканчиваются в неверном порядке, оставляя в приемнике значение, записанное командой i, а не j. Этот тип конфликтов присутствует только в конвейерах, которые выполняют запись со многих ступеней (или позволяют команде выполняться даже в случае, когда предыдущая приостановлена) [1].

1.2 Параллельная обработка

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

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

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

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

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

Программные объекты A и B (команды, операторы, программы) являются независимыми и могут выполняться параллельно, если выполняется следующее условие:

(InB ^ OutA) ν (InA ^ OutB) ^ (OutA ^ OutB) = 0, (1.1)

где In(A) — набор входных, а Out(A) — набор выходных переменных объекта A. Если условие (1.1) не выполняется, то между A и B существует зависимость и они не могут выполняться параллельно.

Если условие (1.1) нарушается в первом терме, то такая зависимость называется прямой. Приведем пример:

A: R = R1 + R2

B: Z = R + C

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

Если условие нарушено во втором терме, то такая зависимость называется обратной:

A: R = R1 + R2

B: R1 = C1 + C2

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

Наконец, если условие не выполняется в третьем терме, то такая зависимость называется конкуренционной:

A: R = R1 + R2

B: R = C1 + C2

Здесь одновременное выполнение операторов дает неопределенный результат.

Увеличение параллелизма любой программы заключается в поиске и устранении указанных зависимостей [3].

Казалось бы конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. Однако увеличив в несколько раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость [2].

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

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

Первым суперскалярным процессором x86 архитектуры был Pentium. В нем исполнительный блок был реализован в виде двух параллельных конвейеров (u и v). u-конвейер — основной, выполняет все операции над целыми и вещественными числами; v-конвейер — вспомогательный, выполняет только простые операции над целыми и частично над вещественными [6].

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

1.3 Постановка задачи

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

Для вычисления приближения к определенному интегралу от функции ƒ по отрезку [a, b] используем составную формулу трапеций:

где h = (b - a)/n, а параметр n задает точность вычислений.

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

где a_i = a = i * l, b_i = a_i + l, l = (b - a)/p. Использовав для приближенного определения каждого из слагаемых f(x) dx этой суммы составную формулу трапеций, взяв n/p в качестве n, и поручив эти вычисления своему процессору, мы получим p-кратное ускорение программы.

Чтобы написать параллельную программу, необходимо выделить в ней части, которые могут одновременно вычисляться разными процессорами, функциональными устройствами или же разными ступенями конвейера. Возможность разбиения программы на части определяется наличием или отсутствием в ней истинных информационных зависимостей. Две операции программы (в данном случае под операцией можно понимать как отдельный оператор, так и более крупные куски кода) называются информационно зависимыми, если результат выполнения одной операции используется в качестве аргумента в другой. Таким образом, чтобы распараллелить программу, нам нужно найти в ней информационно независимые операции, распределить их между вычислительными устройствами и обеспечить их синхронизацию и коммуникацию [5].

Для исследования осуществим подсчет суммы ряда несколькими способами: последовательным и параллельным.

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

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

2 Эскизный проект

2.1 Диаграмма вариантов использования

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

Рисунок 2 – Диаграмма вариантов использования программы дешифрования

Спецификация вариантов использования

Вариант использования “Открыть файл”

Назначение: данный вариант использования предназначен для того чтобы ввести интервалы интеграла для его вычисления.

Сценарий:

1) Ввести интервалы определенного интервала в программу.

Результаты: дальнейшее вычисление интеграла.

Точка завершения: интервалы введены в программу.

Вариант использования “Подсчитать интеграл”

Назначение: данный вариант использования предназначен для подсчета интеграла.

Предусловия: интервалы интеграла должны быть введены.

Стартовая точка: проверка наличия интервалов.

Сценарий:

Получить интервалы интеграла
Вычислить значение интеграла
Сохранить результат вычисления

Результаты: значение интеграла.

Точка завершения: значение интеграла.

Вариант использования “Запустить сервер”

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

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

Стартовая точка: проверка соединения.

Сценарий:

1) Инициализация TCP-сервера;

2) Ожидание подключения клиента;

3) Создание отдельного потока для обслуживания клиента;

4) Передача диапазона вычисления;

5) Получение результата от клиента;

6) Уничтожение потока

7) Остановка TCP-сервера

Аварийные условия: обрыв соединения с удалённой машиной.

Результаты: значение интеграла.

Точка завершения: завершение соединения.

Вариант использования “Разбить интеграл по интервалам”

Назначение: данный вариант использования предназначен для разбиения диапазона интервалов на части.

Предусловия: интервалы интеграла должны быть введены.

Сценарий:

1) Определить диапазон интервалов;

2)Разбить диапазон;

Результаты: диапазон интервалов разбитый на части.

Вариант использования “Сохранить результат”

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

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

Сценарий:

1) Создать файл;

2) Записать результаты в файл;

Аварийные условия: ошибка доступа к диску.

Результаты: текстовый файл, содержащий значение интеграла.

2.2 Диаграммы взаимодействий

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

2.2.1 Диаграмма последовательности

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

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

Рисунок 3 – Диаграмма последовательности

2.2.2 Диаграмма кооперации

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

На рисунке 4 представлена диаграмма кооперации.

Рисунок 4 – Диаграмма кооперации

2.3 Осуществление передачи данных при виртуальном соединении

Клиент:

- создает сокет;

- подсоединяется к серверу, предоставляя адрес удаленного сокета (адрес Internet сервера и номер сервисного порта). Это соединение автоматически присваивает клиенту номер порта;

- осуществляет считывание или запись на сокет;

- закрывает сокет.

Сервер:

- создает сокет;

- связывает сокет-адрес (адрес Internet и номер порта) с сервисной программой: "binding";

- переводит себя в состояние "прослушивания" входящих соединений;

- для каждого входящего соединения:

- принимает соединение (создается новый сокет с теми же характеристиками, что и исходный;

- считывает и записывает на новый сокет;

- закрывает новый сокет.

Осуществление передачи данных с использованием сокетов изображено на рисунке 5.

Рисунок 5- Использование сокетов с установлением логического соединения.

Некоторые вызовы способные заблокировать программу :

Клиент:

- connect () до того, как сервер осуществит accept ();

- write () при переполнении буфера передачи;

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

Сервер:

- accept () до того, как клиент осуществит connect ();

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

- write () при переполнении буфера передачи.

3 Технический проект

Исследование повышения производительности последовательной программы после преобразования ее алгоритма в параллельный 📙 Курсовая → 🆔 96336