Распараллеливание вычислительных алгоритмов
Разработка программного средства распараллеливания вычислительных алгоритмов. Нахождение транзитивных связей логической несовместимости и независимости операторов. Построение диаграммы выполнения для конкретной ветви алгоритма. Спецификация данных.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 27.05.2013 |
| Размер файла | 612,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Распараллеливание вычислительных алгоритмов
Введение
Имеется большое количество важнейших задач, решение которых требует использования огромных вычислительных мощностей, зачастую недоступных для современных вычислительных систем. К таким задачам, прежде всего, относятся задачи точных долгосрочных прогнозов климатических изменений и геологических катаклизмов (землетрясений, извержений вулканов, столкновений тектонических плит), прогнозов цунами и разрушительных ураганов, а также экологических прогнозов и т.п.
Постоянно появляются новые задачи подобного рода, и возрастают требования к точности и к скорости решения прежних задач; поэтому вопросы разработки и использования сверхмощных компьютеров (называемых суперкомпьютерами) актуальны сейчас и в будущем. К сожалению, технологические возможности увеличения быстродействия процессоров ограничены. Из-за этого приходится идти по пути создания параллельных вычислительных систем, т.е. систем, в которых предусмотрена одновременная реализация ряда вычислительных процессов, связанных с решением одной задачи. На современном этапе развития вычислительной техники такой способ, по-видимому, является одним из основных способов ускорения вычислений. Таким образом, актуальность использования технологии распараллеливания вычислительных алгоритмов в современных вычислительных системах довольно велика.
Цель расчетно-графического задания:
- закрепление теоретических знаний в области теории распараллеливания вычислительных алгоритмов;
- формирование практических умений и навыков разработки программного средства для распараллеливания вычислительных алгоритмов;
- закрепление практических навыков самостоятельного решения инженерных задач, развитие творческих способностей студентов и умений пользоваться технической, нормативной и справочной литературой.
Задача расчетно-графического задания:
В соответствии с вариантом составить схему алгоритма предложенной задачи, разбив ее на неделимые атомы.
Разработать программное средство распараллеливания вычислительных алгоритмов. Программное средство должно выполнять следующие функции:
1 ввод и редактирование информационно-логической граф-схемы вычислительного алгоритма;
2 нахождение транзитивных связей и связей логической несовместимости операторов;
3 нахождение транзитивных связей логической несовместимости операторов и независимости операторов;
4 нахождение ранних и поздних сроков окончания выполнения операторов для конкретной ветви алгоритма;
5 построение диаграммы выполнения операторов для конкретной ветви алгоритма.
Разработать контрольный пример для конкретного вычислительного алгоритма.
Индивидуальный вариант задания:
W=5 (M+O2) - (3L + 4K)*N/2,
где
1. Теоретические предпосылки поставленной проблемы
Распараллеливание алгоритма требует выполнения ряда последовательных действий, одним из которых является представление параллельного алгоритма в виде взвешенных графов.
На схеме два типа операторов: логические и арифметические. Логические операторы определяют связи между операторами по управлению, задавая состав и порядок выполнения операторов. После выполнения логического оператора получает право выполнения лишь один из тех операторов, которые связаны стрелками, исходящими из него. Другими словами, преемственность операторов после выполнения логических операторов осуществляется по схеме «исключающего или».
Все прочие операторы (в данном случае арифметические) могут определять только порядок возможного выполнения операторов на основе информационных связей между ними, так как выходная информация одних операторов может являться входной для других. Преемственность операторов при их выполнении осуществляется по схеме «И».
Данный алгоритм, обладает возможностями параллельного выполнения операторов, в процессе которого должна быть выдержана частичная упорядоченность, определенная заданной схемой.
Составим блок-схему алгоритма указанной задачи, в котором каждый блок соответствует неделимому оператору. Блок схема представлена на рисунке 1. Составим информационно-логическую граф-схему алгоритма. При составлении граф схемы будем руководствоваться действительной зависимостью между операторами, обусловленной ветвлением или преемственностью информации. При этом могут быть критически пересмотрены связи, присутствующие в исходном описании алгоритма. Все дальнейшие построения будем проводить для этой граф-схемы. Граф-схема представлена на рисунке 2.
Размещено на http://www.allbest.ru/
Рисунок 1 - Схема алгоритма
Размещено на http://www.allbest.ru/
Рисунок 2 - Информационно-логическая граф-схема алгоритма
Граф-схему алгоритма удобно представлять в виде матриц.
Матрица следования S, отражающая множество задающих связей в графе, изображена на рисунке 3.
Рисунок 3 - Матрица следования S
Данная матрица в нашем случае имеет треугольный вид, что упрощает дальнейшие расчёты.
Матрица транзитивности St, отражающая множество транзитивных связей, которые определены задающими связями и заданы неявно, представлена на рисунке 4.
По данной матрице можно судить о наличии контуров в графе: об этом свидетельствуют ненулевые элементы на главной диагонали. В данном случае, контуров в графе нет.
Далее строится матрица логической несовместимости L, задающая связи логической несовместимости. Данная матрица строится на основе управляющих связей в графе, которые прямо указывают, что образующие их операторы не могут выполняться одновременно ни при каких условиях.
Рисунок 4 - Матрица транзитивности
Матрица транзитивных связей логической несовместимости Lt представлена на рисунке 5.
Матрица Lt логической несовместимости операторов, отражающая и транзитивные связи логической несовместимости, представляет информацию о том, могут или не могут конкретно взятые операторы выполняться при одной реализации алгоритма, т.е. при некотором наборе значений логических переменных. Матрица S, дополненная транзитивными связями, отражает ограничения на порядок выполнения операторов.
Построим для графа матрицу независимости М, отражающую информационно-логические связи между операторами без учета их ориентации, а также связи логической несовместимости операторов с учетом всех транзитивных связей.
Рисунок 5 - Матрица транзитивных связей логической несовместимости Lt
Рисунок 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 Укрупненная схема алгоритма программного средства
На основе анализа требований, предъявляемых к программному средству и функций, выполняемых им, был разработан и описан алгоритм решения задачи.
Размещено на http://www.allbest.ru/
Рисунок 7 - Укрупненная схема алгоритма
2.5 Установка и эксплуатация программного средства
Для установки программного средства необходимо скопировать исполняемый файл «WindowsFormsApplication2.exe» на жесткий диск.
Программа предназначена для компьютеров IBM-совместимой платформы, работающих под управлением операционных систем Microsoft Windows XP, Vista, 7.
Минимальные требования к программно-аппаратной конфигурация компьютера:
- Pentium 4-совместимого процессора;
- 256 Мб оперативной памяти;
- 1 Мб места на жестком диске для хранения программы;
- цветной SVGA-совместимый монитор с поддержкой разрешений 1024x768 точек и более;
- наличие в системе набора библиотек Microsoft.NET Framework 2.0;
- манипулятор типа «мышь».
Программа не производит записи на диск и не требует сохранения и загрузки данных.
2.6 Работа с программным средством
Для запуска программы необходимо запустить исполняемый файл «TVP.exe», при этом откроется окно программы, представленное на рисунке 8.
Интерфейс программы представлен вкладками.
На вкладке «Граф-схема» содержатся элементы создания и редактирования граф-схемы.
Вершины граф-схемы создаются путем двойного щелчка мышью области графического представления данных на вкладке «Граф-схема».
Перемещение вершин осуществляется в соответствии с концепцией DragNDrop и аналогично перетаскиванию папок в проводнике Windows.
После размещения вершин в удобном пользователю порядке, необходимо соединить их в соответствии с двумя типами возможных связей.
Рисунок 8 - Вкладка «Граф-схема»
Связь по информации создается при выбранном переключателе «Связь по информации». Связь по управлению - при выборе переключателя «Связь по управлению».
Для создания связи необходимо зажать правую кнопку мыши на начальной вершине и, не отпуская правой кнопки, довести курсор до конечной вершины. При опускании кнопки создается связь.
Для выбора времени выполнения оператора, представленного вершиной на графе-схеме, необходимо сделать один клик на требуемой вершине, после этого появится диалоговое окно для выбора значения в единицах времени.
После построения той или иной реализации алгоритма необходимо выбрать операторы для выполнения. Выбор осуществляется щелчком по вершине правой кнопкой мыши, выбранные вершины помечаются зеленым цветом.
На каждом этапе построения пользователю предоставляется возможность просмотреть полученные матрицы следования, транзитивности, транзитивных связей логической несовместимости и матрицы независимости. Для их просмотра достаточно выбрать соответствующую вкладку.
По завершении построения можно составить диаграмму сроков выполнения операторов. Для просмотра ранних сроков выполнения достаточно выбрать вкладку «Диаграмма сроков».
Для просмотра поздних сроков выполнения, необходимо на главной вкладке ввести необходимые сроки завершения и нажать соответствующую кнопку, после чего программа автоматически переключит пользователя на диаграмму.
Заключение
Выполнение целей и задач РГР позволило закрепить теоретические знания в области теории распараллеливания вычислительных алгоритмов
Было разработано программное средство распараллеливания вычислительных алгоритмов, выполняющее функции:
- ввода и редактирования информационно-логической графа-схемы вычислительного алгоритма;
- нахождение транзитивных связей и связей логической несовместимости операторов;
- нахождение транзитивных связей логической несовместимости операторов
- нахождение матрицы независимости операторов;
- нахождение ранних и поздних сроков окончания выполнения операторов для конкретной ветви алгоритма;
- построение диаграммы выполнения операторов для конкретной ветви алгоритма.
Список источников
1. Ишакова, Е.Н.: Теория вычислительных процессов: учебное пособие. - Оренбург: ГОУ ОГУ, 2007. -160 с.
2. Либерти, Д.: Программирование на C#.-Пер. с англ.. - СПб: Символ-Плюс, 2003. - 688 с.
3. Троелсен, Э. Язык программирования С# 2005 и платформа .NET 2.0. Пер. с анг. - М.-СПб.-Киев.: «Вильямс». - 2007 г. - 1168 стр.
4. Петцольд, Ч. Программирование для Microsoft Windows на C#. В 2-х томах, Том 1-2. - Пер. с англ.-М: Издательско-торговый дом «Русская редакция», 2002
5. Марченко, А.Л. Основы программирования на C# 2.0 - М.: «Интернет-университет информационных технологий - ИНТУИТ.ру», «БИНОМ. Лаборатория знаний» - 2007 г. - 552 стр.
Размещено на Allbest.ru
...Подобные документы
Интерфейс OpenMP - системы программирования на масштабирующих SMP-системах. Разработка алгоритмов блока "Эксперт для мультипроцессора" в проекте "Экспериментальная система автоматизации распараллеливания" для генерации вариантов локализации данных.
дипломная работа [129,8 K], добавлен 15.10.2010Анализ средств построения динамически масштабируемых ВС. Разработка алгоритма, обеспечивающего устойчивость функционирования информационно-вычислительных сетей в условиях воздействий компьютерных атак, использующих фрагментированные пакеты сообщений.
дипломная работа [3,8 M], добавлен 21.12.2012Трудности использования эволюционных алгоритмов. Построение вычислительных систем, основанных на принципах естественного отбора. Недостатки генетических алгоритмов. Примеры эволюционных алгоритмов. Направления и разделы эволюционного моделирования.
реферат [187,4 K], добавлен 21.01.2014Пакетный метод как основной способ выполнения коммуникационных операций, его содержание и предъявляемые требования. Оценка трудоемкости операции передачи данных между двумя узлами кластера. Этапы разработки параллельных алгоритмов (распараллеливания).
презентация [318,1 K], добавлен 10.02.2014Аппроксимация эмпирических данных линейной и квадратичной зависимостью. Теория корреляции: расчет коэффициентов детерминированности. Построение алгоритма и вычисление приближённых функций методом наименьших квадратов в среде программирования Turbo Pascal.
курсовая работа [766,6 K], добавлен 26.12.2011Написание программного обеспечения на языке ассемблер для AVR-МК ATmega16, позволяющего осуществлять вычисление заданной функции. Введение входных данных с помощью определенного макроса с командой загрузки значений в регистры ldi. Исходный код программы.
контрольная работа [521,0 K], добавлен 23.11.2014Описание компонентов сети конфиденциальной связи. Система распределения ключей на основе линейных преобразований. Описание разработанных программ. Криптостойкость алгоритма распределения ключей. Алгоритм шифрования данных в режиме обратной связи.
курсовая работа [98,3 K], добавлен 26.09.2012Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.
курсовая работа [1,5 M], добавлен 07.07.2013Изучение особенностей создания алгоритмов вычислительных задач. Визуальное программирование стандартных компонентов среды программирования Delphi. Технология создания компонента Delphi для решения производственной задачи. Выполнение блок-схемы алгоритма.
курсовая работа [638,0 K], добавлен 30.01.2015Проектирование логической схемы данных для предметной области, физической модели базы данных. Разработка алгоритмов функциональных модулей программного приложения. Принципы тестирования спроектированного программного обеспечения, анализ эффективности.
курсовая работа [926,7 K], добавлен 20.05.2015Реализация алгоритмов вычисления математических объектов на конкретных вычислительных машинах. Числовые данные в практических задачах. Анализ математических моделей, связанных с применением вычислительных машин в различных областях научной деятельности.
курсовая работа [369,3 K], добавлен 13.01.2018Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.
курсовая работа [1,7 M], добавлен 16.04.2012Расчет издержек предприятия на разработку программного продукта и экономической эффективности от его внедрения. Топология физических связей и структуризация сети. Характеристика программного обеспечения. Средства автоматизации, описание алгоритма задачи.
дипломная работа [867,6 K], добавлен 05.11.2015Анализ характеристик объекта компьютеризации. Разработка структур данных, алгоритмов и программного обеспечения системы управления базой данных. Особенности синтеза структур данных. Разработка алгоритмов системы и оценка результатов тестирования.
курсовая работа [37,0 K], добавлен 07.12.2010Разработка собственного алгоритма сжатия и восстановления данных с использованием возможностей языка C++ в рамках программного продукта "Архиватор". Разработка алгоритма программы, ее первый запуск и тестирование. Проверка работы архивации файлов.
курсовая работа [325,7 K], добавлен 13.10.2015Комплексное исследование истории развития, основных понятий, области применения и особенностей генетических алгоритмов. Анализ преимуществ генетических алгоритмов. Построение генетического алгоритма, позволяющего находить максимум целочисленной функции.
курсовая работа [27,9 K], добавлен 23.07.2011Оценка погрешности и точности в математике. Составление программы и алгоритма для численного дифференцирования с заданной допустимой погрешностью на алгоритмическом языке Turbo Pascal 7.0. Составление алгоритма и программы аппроксимации функции.
курсовая работа [810,6 K], добавлен 24.03.2012Исследование структуры типовой вычислительной сети. Модель процесса вскрытия вычислительной сети и взаимосвязь основных его этапов. Конфликт в информационной сфере между субъектом и объектом познания. Описания алгоритмов динамического масштабирования.
дипломная работа [2,9 M], добавлен 21.12.2012Построение информационно-логической модели базы данных. Корректировка данных средствами запросов. Проектирование алгоритмов обработки данных. Реализация пользовательского интерфейса средствами форм. Разработка запросов для корректировки и выборки данных.
курсовая работа [680,9 K], добавлен 19.10.2010Исследование симметричных алгоритмов блочного шифрования. Минусы и плюсы алгоритма IDEA. Разработка программы аутентификации пользователя и сообщений на основе алгоритма IDEA. Выбор языка программирования. Тестирование и реализация программного средства.
курсовая работа [314,2 K], добавлен 27.01.2015
