Распараллеливание вычислительных алгоритмов

Министерство науки и образования  Российской Федерации

Федеральное государственное бюджетное образовательное учреждение  
высшего профессионального образования

оренбургский государственный  университет

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

Кафедра программного обеспечения вычислительной техники

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

 

 

 

 

 

 

 

 

Отчет

по расчетно-графической работе

 

«Распараллеливание вычислительных алгоритмов»

по дисциплине теория вычислительных процессов

 

ГОУ ОГУ 230105.65.9012.04 О

 

 

 

 

 

 

Руководитель

_______________Ишакова Е.Н.

"____"_________________2012 г.

Исполнитель

студент группы З-09ПОВТ(у)

_______________Богданова О.А.

"____"_________________2012 г.

 

 

 

 

 

 

 

 

Оренбург 2012

 

Содержание

 

Введение  3

1 Теоретические предпосылки  поставленной проблемы 5

2 Разработка программного  средства 12

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

2.2 Спецификация основных  процедур и функций 13

2.3 Спецификация данных 14

2.3.1 Структура входных  данных 15

2.4 Разработка алгоритма  решения задачи 15

2.4.1 Укрупненная схема  алгоритма программного средства 15

2.5 Установка и эксплуатация  программного средства 16

2.6 Работа с программным  средством 16

Заключение 19

Список использованных источников 20

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

Приложение Б –  Контрольный пример 31

 

 

 

Введение

 

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

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

Цель расчетно-графического задания:

- закрепление теоретических знаний в области теории распараллеливания вычислительных алгоритмов;

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

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

Задача расчетно-графического задания:

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

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

1. ввод и редактирование информационно-логической граф-схемы вычислительного алгоритма;
2. нахождение транзитивных связей и связей логической несовместимости операторов;
3. нахождение транзитивных связей логической несовместимости операторов и независимости операторов;
4. нахождение ранних и поздних сроков окончания выполнения операторов для конкретной ветви алгоритма;
5. построение диаграммы выполнения операторов для конкретной ветви алгоритма.

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

Индивидуальный вариант  задания:

W=5(M+O²) – (3L + 4K)*N/2, где

  

 

1 Теоретические предпосылки  поставленной проблемы

 

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

На схеме два типа операторов: логические и арифметические. Логические операторы определяют связи между операторами по управлению, задавая состав и порядок выполнения операторов. После выполнения логического оператора получает право выполнения лишь один из тех операторов, которые связаны стрелками, исходящими из него. Другими словами, преемственность операторов после выполнения логических операторов осуществляется по схеме «исключающего или».

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

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

Составим блок-схему алгоритма  указанной задачи, в котором каждый блок соответствует неделимому оператору. Блок схема представлена на рисунке 1.

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

 

Рисунок 1 – Схема алгоритма

 

 

Рисунок 2 – Информационно-логическая граф-схема алгоритма

 

Граф-схему алгоритма удобно представлять в виде матриц.

Матрица следования S, отражающая множество задающих связей в графе, изображена на рисунке 3.

 

 

 

 

 

Рисунок 3 - Матрица следования S

 

Данная матрица в нашем случае имеет треугольный вид, что упрощает дальнейшие расчёты.

Матрица транзитивности S^t, отражающая множество транзитивных связей, которые определены задающими связями и заданы неявно, представлена на рисунке 4.

 

 

Рисунок 4 – Матрица транзитивности

 

По данной матрице можно судить о наличии контуров в графе: об этом свидетельствуют ненулевые  элементы на главной диагонали. В  данном случае, контуров в графе нет.

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

Матрица транзитивных связей логической несовместимости L^t представлена на рисунке 5.

 

 

 

Рисунок 5 - Матрица транзитивных связей  
логической несовместимости L^t

 

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

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

 

 

Рисунок 6 - Матрица независимости М

 

 

2 Разработка программного  средства

 

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

 

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

1 Составить алгоритм ввода граф-схемы алгоритма (добавления и соединения вершин)

2 Составить алгоритм вычисления матрицы следования для введенной граф-схемы.

3 Составить алгоритм вычисления матрицы транзитивности для введенной граф-схемы.

4 Составить алгоритм вычисления матрицы транзитивных связей логической несовместимости для введенной граф-схемы.

5 Составить алгоритм вычисления матрицы независимости для введенной граф-схемы.

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

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

 

2.2 Спецификация основных процедур  и функций

 

Спецификация  основных процедур и функций представлена в таблице 1.

 

Таблица 1 – Спецификация процедур и функций

 

public int Vertex_size()	Возвращает число вершин в граф-схеме
public void DrawGraph(Graphics gr)	Функция отображения в PictureBox граф-схемы
public void AddVertex(Point P)	Добавление новой вершины в список вершин
public void FillMatrT()	Функция заполнения матрицы  транзитивности
public void FillMatrL()	Функция заполнения матрицы  логической несовместимости и дополнения ее связями транзитивной логической несовместимости
public void FillMatrN()	Функция заполнения матрицы независимости операторов
public void GetMaxVNO()	Функция нахождения максимального  множества ВНО
public int FindFT()	Функция нахождения ранних сроков выполнения операторов
public void FindLtT(int MaxT)	Функция нахождения поздних  сроков выполнения операторов
public void Renum()	Функция перенумерования  вершин
public void MatrSwap(int x, int y)	Функция изменения матрицы  следования
public void VertexMouseClick(object sender, System.Windows.Forms.MouseEventArgs e)	Обработчик нажатия  кнопок мыши
public void VertexMouseUnclick(object sender, System.Windows.Forms.MouseEventArgs e)	Обработчик отпускания кнопок мыши
public void VertexMouseMove(object sender, System.Windows.Forms.MouseEventArgs e)	Обработчик перемещения  мыши

 

 

 

2.3 Спецификация данных

 

Рассмотрим структуру входных  и выходных данных, используемых в программном средстве. Базовые единицы данных вынесены в таблицу 2.

 

Таблица 2 – Спецификация данных программы

 

Сlass Round
public int num	Номер вершины
public Point p	Объект класса точки связанный с вершиной
public bool selected	Признак активности вершины
public List<round> next	ссылка на следующую  вершину
public int Time	Время выполнения оператора, заданного вершиной
private int size=15;	Размер отображаемой на экране вершины графа-схемы
Сlass Node
private int DX,DY	Координаты нажатия  на PictureBox
public Form1 f	Форма
public int[] Tau	Массив данных ранних сроках
public int[] LTau;	Массив данных поздних  сроках
public int[,] mtr , S , L , N	Матрицы транзитивности, логической несовместимости и независимости операторов

 

2.4 Разработка алгоритма решения  задачи

 

2.4.1 Укрупненная схема  алгоритма программного средства

 

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

 

 

Рисунок 7 – Укрупненная схема алгоритма

 

2.5 Установка и эксплуатация  программного средства

 

Для установки программного средства необходимо скопировать исполняемый файл «WindowsFormsApplication2.exe» на жесткий диск.

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

Минимальные требования к программно-аппаратной конфигурация компьютера:

- Pentium 4-совместимого процессора;

- 256 Мб оперативной памяти;

- 1 Мб места на жестком диске для хранения программы;

- цветной SVGA-совместимый монитор с поддержкой разрешений 1024x768 точек и более;

- наличие в системе набора библиотек Microsoft .NET Framework 2.0;