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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Анотація

 

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

Робота викладена на 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 работы с несколькими потоками команд и одним потоком данных.