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

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

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

Программные объекты 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. Получить интервалы интеграла
2. Вычислить значение интеграла
3. Сохранить результат вычисления

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

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

 

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

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

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

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

Сценарий:

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 Технический  проект