Методы создания и эквивалентных преобразований параллельных программ с учетом информационных зависимостей тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Шичкина, Юлия Александровна

• Шичкина, Юлия Александровна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Шичкина, Юлия Александровна

СОДЕРЖАНИЕ

Введение 6 Глава 1. Обзор способов представления распределенных структур и

методов их обработки

1.1. Ориентированные, взвешенные графы и деревья

1.2. Матричные алгоритмы на графах

1.3. Технологии обработки разреженных матриц

1.4. Методы определения трудоемкости алгоритмов

1.5. Оптимизация вычислений за счет распараллеливания алгоритмов

Выводы 61 Глава 2. Методы преобразования разреженных прямоугольных матриц с

сохранением первоначальных значений

2.1. Примеры задач, сводимых к разреженным матрицам

2.2. Приведение разреженной матрицы к односторонне окаймляющей блочной диагональной форме

2.3. Приведение разреженной матрицы к треугольной форме

2.3.1. Метод ненулевой диагонали

2.3.2. Метод уплотнения вниз 77 Выводы

Глава 3. Организация последовательных и параллельных вычислений

3.1. Матричный метод перебора путей в графе

3.2. Построение параллельного алгоритма на основе его последовательного аналога с последующей оптимизацией по числу процессоров

3.2.1. Матричное преобразование алгоритмов и их

оптимизация по числу процессоров

3.2.2. Оптимизация алгоритмов по ширине с применением

списков смежности

3.2.3. Оптимизация алгоритмов по ширине с применением

списков следования

3.3. Оптимизация параллельных алгоритмов по времени выполнения

3.3.1. Матричное преобразование алгоритма с целью

оптимизации по времени выполнения

3.3.2. Оптимизация алгоритма по времени выполнения с

применением списков следования

3.4. Оптимизация алгоритмов по нескольким параметрам

Выводы

Глава 4. Методы конструирования реляционных схем на основе метаданных функциональных зависимостей

4.1. Проблемы аномалии избыточности в различных моделях

данных

4.2. Функциональные зависимости реляционных отношений

4.2.1. Представление функциональных зависимостей с

помощью графов

4.2.2. Преобразование орграфа функциональных

зависимостей в дерево

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

4.4. Декомпозиция отношения на основе орграфа простых функциональных зависимостей

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

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

4.7. Декомпозиция отношения на основе орграфа составных функциональных зависимостей

Выводы

Глава 5. Применение разработанных методов на различных прикладных задачах

5.1. Задача 1. Распараллеливание алгоритма конструирования реляционных схем

5.1.1. Построение информационного графа алгоритма

5.1.2. Оптимизация информационного графа алгоритма нормализации реляционных отношений

Выводы

5.2. Задача 2. Организация преобразований в системах, основанных на расписании

5.2.1. Выполнение параллельных процессов в системе

5.2.2. Графовый метод распределения задач на кластере

5.2.3. Матричный метод распределение задач

5.2.4. Применение онтологий при организации процесса распределения задач на кластере

Выводы

5.3. Задача 3. Тестирование разработанных методов на модели управления процессом электролиза алюминия

5.3.1. Структурная идентификация процесса получения алюминия

5.3.2. Выбор метода решения системы линейных уравнений

5.3.3. Применение методов распараллеливания к алгоритму по приведению разреженной матрицы к форме ВЭР на модели управления процессом электролиза алюминия

Выводы

5.4. Задача 4. Применение матричных методов в теории принятия решений

5.4.1. Особенности алгоритмов построения дерева решений

5.4.2. Применение методов распараллеливания к

алгоритму ID3

5.4.3. Матричный метод построения дерева решений

Выводы

Заключение

Список литературы

Приложение А. Примеры перебора путей графа 316 Приложение В. Примеры приведения отношений к нормальным формам

Приложение С. Примеры вывода ключа отношения 324 Приложение D. Апробация методов оптимизации параллельного

алгоритма 331 Приложение Е. Матрица смежности информационного графа алгоритма

нормализации реляционного отношения

Приложение F. Ранние сроки выполнения алгоритма

Приложение G. С-граф процесса получения алюминия 339 Приложение Н. Модель управления процессом электролиза алюминия

Приложение I. Разреженная матрица, приведенная к форме BDF 341 Приложение J. Система линейных уравнений в модели управления

процессом электролиза алюминия

Приложение К. Преобразованная система линейных уравнений

Приложение L. Решение системы линейных уравнений в Maple

Приложение М. Отделение передаточных функций

Приложение N. Построение блочной диагональной формы системы

Приложение О. Реализация подстановки в Maple

Приложение Р. Матрица смежности алгоритма BDF

Приложение R. Ранние сроки выполнения алгоритма BDF

Приложение S. Последовательная программа ID3 353 Приложение Т. Код распараллеленной главной функции

программы ЮЗ

Приложение U. Код распараллеленной функции Gain

Введение диссертации (часть автореферата) на тему «Методы создания и эквивалентных преобразований параллельных программ с учетом информационных зависимостей»

Введение

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

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

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

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

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

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

- Алгоритмы на разреженных матрицах, оптимизирующие процесс решения задач дискретной математики, математической физики и других областей научных исследований. Литература, посвященная разреженным матрицам, ограничивается переводными [115, 129] и отечественными [16,54-56, 92, 95, 97] книгами, в каждой из которых рассматривается лишь какая-нибудь одна задача линейной алгебры, а подчас даже ее специальный случай — симметричный спектральный анализ, решение симметричных положительно определенных систем, несимметричные системы, создание программного обеспечения САПР на основе компактной обработки разреженных матриц.

Среди методов эффективного хранения матриц в памяти ЭВМ необходимо назвать применение нестандартных вейвлет-преобразований для сжатия матриц и построение циркулянтных предобуславливателей для общих и теплице-вых матриц [95].

Методы хранения разреженных матриц, итерационные и проекционные методы на подпространствах Крылова и их распараллеливание рассмотрены Баландиным М.Ю. и Шуриной Е.П. [16].

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

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

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

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

Среди работ, посвященных эвристическим алгоритмам необходимо выделить [15, 98, 102].

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

- Матричные алгоритмы. Алгоритмы по преобразованию матриц, как правило, применяются в численных методах линейной алгебры и задачах, сводимых к ним. Вопросами распараллеливания алгоритма решения системы линейных уравнений с разреженной матрицей общего вида и большого размера, примерно 750000 х 750000, занимались специалисты Московского государственного университета им. М. В. Ломоносова: Д. Е. Александров, В. В. Галкин, А. И. Зобнин, М. В. Левин [13] - 2009г. В работах Демьяновича Ю.К. [42-44] описаны отдельные методы линейной алгебры в концепции неограниченного параллелизма, в частности параллельные алгоритмы ЬИ - разложения трехдиа-

тональной матрицы, умножения матрицы на вектор, отыскания обратной матрицы.

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

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

В последнее время параллельным вычислениям было посвящено много работ. В целом все эти работы можно было бы условно разделить на три основные категории:

- Работы в области теории параллельного программирования. Это работы: Воеводина В. и Воеводина Вл. [30, 31], Эндрюс Г.Р. [128] с описанием в качестве примеров достаточно сложных задач и алгоритмов, например, многосеточных методов; Богданова A.B. и др. [24], Богачева А.Ю. [23].

- Работы, посвященные построению параллельных алгоритмов для задач узкого класса из некоторой области с примерами параллельных алгоритмов вычислительной математики: Ортега Дж. [94]; Миллер Р., Боксер Л. [88]; Гергель В.П. [36-38].

- Работы, посвященные формальным моделям параллельных вычислений. Это зарубежные исследователи Я.Фостер, Ч.Хоар, Р.Милнер, К.Петри, Г.Винскель, М.Нильсен, Э.Гобо, М.Беднарчик и другие [2-10], которыми были предложены формальные модели, позволяющие описывать функционирование последовательных процессов, исполняющихся параллельно.

Построением формальных моделей распределенных вычислений занимались отечественные ученые: В.Воеводин и Вл.Воеводин [30-31], О.Омаров, В.Котов [69], И.Вирбицкайте, А.Барский, В.Бочаров, В.Корнеев [62-63], Н.Миренкова.

Наиболее общими математическими моделями параллельных вычислений являются: граф алгоритма, информационный граф алгоритма, граф зависимости и граф процесса [30].

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

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

- Работы с исследованиями в области методов автоматизации построения параллельных алгоритмов для вычислительной системы заданной структуры, к которым можно отнести: «жадные» алгоритмы и сети Хопфилда для решения задачи построения расписаний и эвристические и эволюционные алгоритмы, настраиваемые на конкретный вариант постановки задачи [28-29].

Широкое освещение результатов решения проблемы планирования вычислительного процесса можно найти в работах Коффмана Э.Г.[71], Левина В.И.[79], Топоркова В.В.[112-113], Костенко В.А.[67-68]. Ряд решений вопросов

планирования был предложен в рамках теории расписаний в работах Конвея Р.В., Танаева B.C., Brucker Р.

Вопросы разработки средств автоматизированного анализа производительности параллельных программ, которые способны в той или иной степени самостоятельно находить узкие места для последующего удаления их программистами, рассматривались в работах Андреева Н.Е., Афанасьева К.Е. [14]. В работах Корячко В. П. и Скворцова С. В. [64] представлены модели и метод глобальной оптимизации объектного кода для RISC-процессоров с управлением по технологии VLIW, основанные на использовании дизъюнктивных графов информационно-структурных зависимостей. Курносов В.Г. [76] предложил алгоритмы оптимизации вложения параллельных программ в современные мульти-архитектурные распределенные ВС, характеризующиеся иерархической организацией коммуникационных сред. В работах [1, 104] предложены алгоритмы вложения параллельных программ, в которых ВС представлена в виде графа межмашинных связей. Предполагается, что информация между ЭМ передается по кратчайшему пути и все каналы связи однородны. В качестве показателя производительности канала связи между ЭМ используется длина пути (в смысле теории графов).

Следует отметить существующие оптимизирующие и распараллеливающие компиляторы, позволяющие автоматизировать процесс распараллеливания программ: GNU Compiler Collection (GCC), SUIF Compiler и Intel С++ Compiler. В отечественной науке наиболее известными в этой области являются V-Ray, система ПРОГРЕСС, DVM-система, Т-система, среда ParJava. Существуют следующие исследовательские университетские распараллеливающие системы: POLARIS, PIP, Открытая распараллеливающая система на основе решетчатых графов, разрабатываемая Южным федеральным университетом, мехмат.

В работе Штейнберга Б.Я. [126-127] описан класс распараллеливаемых рекуррентных циклов для суперкомпьютеров с распределенной памятью. Опи-

сываемая им открытая распараллеливающая система может служить для разработки распараллеливающих компиляторов.

Следует отметить, что полная автоматизация процесса распараллеливания на уровне компиляторов проблематична по следующим причинам:

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

- Наличие в циклах неизвестных заранее количеств итераций.

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

Частично решить эти проблемы можно, если:

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

- Создать интерактивную систему компиляции, в работе которой принимал бы участие человек. Такие системы созданы в рамках подпроекта «SUIF Explorer»

К основным недостаткам существующих методов оптимизации параллельных вычислений можно отнести:

- отсутствие этапа анализа структуры алгоритма, для реализации которого проектируется параллельная программа — вместо этого предлагается применять различные эвристики;

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

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

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

В настоящее время имеется достаточно много моделей представления данных, но первенство по востребованности, начиная с 80-х годов, удерживают реляционные модели. Проектирование реляционных моделей баз данных нередко усложняется появлением аномалий [34]. Изучение и устранение аномалий является самым важным аспектом даталогического этапа проектирования базы данных в целом, которое позволяет значительным образом усовершенствовать ранее созданную реляционную модель. К сожалению, этот этап является наименее автоматизированным. Ни одна из современных СУБД не проверяет схему базы данных на наличие аномалий, не смотря на то, что современный аппарат прикладной математики позволяет формализовать этот процесс.

Вопросы построения оптимальных реляционных баз данных рассматриваются в сфере управления базами данных, интеллектуального анализа и аналитической обработки данных. Разработками в данной области занимаются специалисты: Л.А.Калиниченко, М.Ш.Цаленко, Ю.Г.Карпов, С.А.Ступников, М.Р.Когаловский, С.Д.Кузнецов, Б.А.Новиков, Д.Мейер, М.Франклин, Г. Гарсия Молина, Д.Ульман, С.Г.Попов [34, 58, 65, 72-75, 81, 100].

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

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

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

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

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

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

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

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

Объектом диссертационного исследования являются параллельные вычисления на кластерных системах.

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

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

Основные задачи исследования

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

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

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

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

5. Разработка программного обеспечения для тестирования полученных методов и методики их применения в зависимости от количественных характе-

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

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

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

Основные положения, выносимые на защиту

1. Методы обработки разреженных матриц с сохранением первоначальных значений математической модели;

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

■ времени выполнения;

■ количества процессоров;

■ времени выполнения и числа процессоров.

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

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

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

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

Научная новизна работы

К наиболее существенным научным результатам относятся следующие:

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

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

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

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

5. Предложено представление функциональных зависимостей реляционных схем в матричном виде и получены матричные аналоги свойств функциональных зависимостей. В отличии от известных ранее способов представления и обработки функциональных зависимостей предложенные матричные свойства позволяют дополнить современные СУБД отсутствующей в них функцией проверки реализуемых физических баз данных на корректность структуры и отсутствие аномалии избыточности.

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

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

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

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

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

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

Практическая значимость результатов исследования

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

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

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

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

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

Реализация результатов исследования

Теоретические и практические результаты диссертационной работы используются в программных средствах ОАО «РУСАЛ-Братск» (Братский алюминиевый завод), ОАО «Концерн «Океанприбор» и ГУ «Санкт-Петербургский центр по гидрометеорологии и мониторингу окружающей среды с региональными функциями», что подтверждено актами о применении. Результаты работы используются в учебном процессе кафедры дискретной математики и защиты информации ФГБОУ ВПО «Братский государственный университет» при преподавании курсов «Теория алгоритмов», «Параллельное программирование», «Численные методы», матричные методы принятия решений и разработанное программное применяются при формализованном подходе к формированию заявки на контрольные цифры приема в ФГБОУ ВПО «Братский государственный университет».

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Шичкина, Юлия Александровна

Выводы

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

2. Разработана программа, реализующая эвристический алгоритм построения дерева решений ID3. Программа написана на fortran 90 под управлением ОС Linux Slakeware и откомпилирована с помощью mpif90 с целью последующего распараллеливания.

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

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

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

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

Заключение

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

Можно выделить следующие основные результаты диссертационной работы:

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

2. Разработан метод построения реляционной схемы на основе атрибутов предметной области и декларированных функциональных зависимостей. Все получаемые схемы удовлетворяют нормальной форме Бойса-Кодда.

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

4. Выведены оценки теоретической и практической минимальной ширины информационного графа, по которым можно принимать решение о дальнейшем преобразовании информационного графа.

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

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

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

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

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

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

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

11. Разработан матричный метод построения дерева решений, который позволяет получать более широкую совокупность правил по сравнению, к примеру, с методом ID3. Совокупность правил может быть отрегулирована с

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

Список литературы диссертационного исследования кандидат наук Шичкина, Юлия Александровна, 2014 год

Список литературы

1. Agarwal, Т. Topology-aware task mapping for reducing communication contention on large pa-rallel machines / T. Agarwal // Parallel and Distributed Processing Symposium. - 2006. - P. 10

2. Ahmad, I. A Parallel Algorithm for Optimal Task Assignment in Distributed Systems /1. Ahmad, M. Kafil // Proceedings of the 1997 Advances in Parallel and Distributed Computing Conference. - 1997. - P. 284.

3. Bhanot, G. Optimizing task layout on the Blue Gene/L supercomputer / G. Bhanot // IBM Journal of Research and Development. - 2005. - Vol. 49, № 2. -P. 489-500.

4. Bokhari, S. H. On the mapping problem / S.H. Bokhari // IEEE Transactions on Computers. - 1981. - Vol. 30, № 3. - P. 207 - 214.

5. Chen, Hu. MPIPP: An Automatic Profileguided Parallel Process Placement Toolset for SMP Clusters and Multiclusters / Hu.Chen // Proceedings of the 20th annual international conference on Super-computing. - 2006. - P. 353 -360.

6. Jose, A. An approach to mapping parallel programs on hypercube multiprocessors / A. Jose // Proceed-ings of Workshop Parallel and Distributed Processing. - 1999. - P. 221 - 225.

7. Rauber, N., Runger, G. Parallel Programming: for Multicore and Cluster Systems. / N. Rauber, G. Runger. - Springer, 2010. - 450p.

8. Schloegel, K. Graph partitioning for high-performance scientific simulations / K. Schloegel, G. Karypis, V. Kumar // Sourcebook of parallel computing. -San Franciso: Morgan Kaufmann Publish, 2003. - P. 491 - 541.

9. Taniar, D., Leung, C.H.C., Rahayu, W., Goel, S. High Performance Parallel Database Processing and Grid Databases. / D. Taniar, C.H.C. Leung, W. Rahayu, S. Goel - John Wiley & Sons, 2008. - 278p.

10. Thakur, R. Optimization of collective communication operations in MPICH / R.Thakur, R.Rabenseifner, W. Gropp // Int. Journal of High Performance Computing Applications. - 2005. - Vol. 19, No. 1. - P. 49-66.

11. Авдиенков, О.А. Архитектурные аспекты использования облачной платформы Microsoft Windows Azuré Platform для параллельного программирования. / О.А. Авдиенков, В.Н. Маланин. // Материалы шестого Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах», Санкт-Петербург, 12-17 декабря 2006г. - СПб: Санкт-Петербургский госуниверситет, 2007. - Том1. - С.253-258.

12. Аветисян, А.И. Возможности оптимального выполнения параллельных программ, содержащих простые и итерированные циклы, на неоднородных параллельных вычислительных системах с распределенной памятью / А.И.Аветисян, С.С.Гайсарян, О.И.Самоваров. // Программирование, 2002. - №1. - С.38-54.

13. Александров, Д. Е. Распараллеливание матричных алгоритмов вычисления базисов Грёбнера. / Д.Е.Александров, В.В.Галкин, А.И.Зобнин, М.В. Левин. // Фундаментальная и прикладная математика, 2008, том 14, № 4, С. 35—64.

14. Андреев, Н.Е. Продуктивный анализ производительности параллельных приложений на мультиядерных и многоядерных архитектурах. / Н.Е.Андреев, К.Е.Афанасьев // Сборник статей региональной научно-практической конференции «Многоядерные процессы и параллельное программирование». - Барнаул.: АлтГУ,2011. - С.28-33.

15. Ахо. А.В., Хопкрофт, Д.Э, Ульман, Д.Д., Структуры данных и алгоритмы / А.В.Ахо, Д.Э.Хопкрофт, Д.Д.Ульман. - Изд-во: Вильяме, 2010. -400с.

16. Баденко, В. Л. Высокопроизводительные вычисления: учеб. пособие / В.Л. Баденко - СПб.: Изд-во Политехи, ун-та, 2010. - 180с.

17. Баландин, М.Ю., Шурина, Е.П. Методы решения СЛАУ большой размерности / М.Ю.Баландин, Е.П.Шурина - Новосибирск: Изд-во НГТУ, 2000.-70с.

18. Бабошин, A.A. Автоматизация разработки распределенных приложений / A.A. Бабошин // Материалы XI Санкт-Петербургской междунар. конф. «Региональная информатика-2008 (РИ-2008)». Санкт-Петербург, 22-24 октября 2008 г. СПб. 2008. - С.300-335.

19. Барский, А. Б. Параллельные информационные технологии / А.Б. Барский - М.:Бином, 2007. - 504с.

20. Беллман, Р. Введение в теорию матриц / Р.Беллман - М.: Наука, 1978.-367с.

21. Берж, К. Теория графов и ее применение / К.Берж - М.: Изд-во иностр. лит. 1962 - 319с.

22. Биркгоф, Г., Барти, Т. Современная прикладная алгебра. 2-е изд., стер./Пер. с англ. Ю.И.Манина./ Г.Биркгоф, Т.Барти - СПб.: Издательство «Лань», 2005. -400с.

23. Богачев, К. Ю. Основы параллельного программирования / К.Ю. Богачев - М: Бином, 2010. - 344 с.

24. Богданов, A.B., Корхов, В.В., Мареев, В.В., Станкова, E.H. Архитектуры и топологии многопроцессорных вычислительных систем / А.В.Богданов, В.В.Корхов, В.В.Мареев, Е.Н.Станкова - М.: Изд-во «Интернет-университет информационных технологий - Интуит.ру», 2004. -176с.

25. Бурова, И.Г., Демьянович, Ю.К. Лекции по параллельным вычислениям / И.Г.Бурова, Ю.К.Демьянович -СПб., 2003. - 132с.

26. Бухановский, A.B. Интеллектуальные высокопроизводительные программные комплексы моделирования сложных систем: концепция, архитектура и примеры реализации / А.В.Бухановский, С.В.Ковальчук, С.В.Марьин // Изв. Вузов. Приборостроение, т. 52, № 10, 2009 - С.5-24.

27. Бухановский, A.B. Технологии высокопроизводительных вычислений и компьютерного моделирования / А. В. Бухановский // Изв. Вузов. Приборостроение, 2009 г. - Т.52, №10 - С.56-68.

28. Вавинов, C.B., Костенко, В.А. Параметризованный жадный алгоритм построения статических расписаний / C.B. Вавинов, В.А. Костенко - M.: Изд-во МГУ, 2003. - 124с.

29. Винокуров, A.B., Костенко, В.А. Использование сетей Хопфилда для построения расписаний / A.B. Винокуров , В.А. Костенко - М.: Изд-во МГУ, 2001,- 145с.

30. Воеводин, В.В., Воеводин, В л.В. Параллельные вычисления /

B.В.Воеводин, Вл.В.Воеводин -СПб.:БХВ-Петербург, 2004. - 608с.

31. Воеводин, Вл. В., Жуматий, С. А. Вычислительное дело и кластерные системы / Вл.В. Воеводин, С.А. Жуматий - М.: Изд-во МГУ, 2007. -150с.

32. Воробьев, В.И. Онтологическая модель описания параллельных процессов / В.И.Воробьев, М.Ю.Петров, Ю.А.Шичкина, Е.Л.Евневич // Информационно-измерительные и управляющие системы. No7, т.8, 2010. -

C.127-133

33. Вьюкова, Н.И. Генерация эффективного кода для процессорных архитектур с явным параллелизмом / Н.И. Вьюкова, В.А.Галатенко, С.В.Самборский, С.М.Шумаков //Программирование. 2002. №5. С.27-51.

34. Гарсиа-Молина, Г., Ульман, Д., Уидом, Д. Системы баз данных. Полный курс. : Пер.с англ. / Г.Гарсиа-Молина, Д.Ульман, Д.Уидом - М.: Издательский дом «Вильяме», 2003. - 1088с.

35. Гатчин, Ю.А., Коробейников, А.Г. Проектирование интегрированных автоматизированных технологических комплексов, монография / Ю.А.Гатчин, А.Г.Коробейников - СПб, СПбГИТМО(ТУ), 2000. - 171с.

36. Гергель, В.П. Теория и практика параллельных вычислений / В.П.Гергель - М.: Интернет-университет информационных технологий.; БИНОМ: Лаборатория знаний, 2007 - 423с.

37. Гергель, A.B. Адаптивные параллельные алгоритмы для многомерной экстремальной оптимизации / A.B.Гер гель, Д.В.Гнатюк //

Материалы конференции «Высокопроизводительные параллельные вычисления на кластерных системах». 2009. С.92-96.

38. Гергель, В. П., Стронгин Р. Г. Основы параллельных вычислений для многопроцессорных вычислительных систем / В. П.Гергель, Р. Г.Стронгин - Н.Новгород: Изд-во ННГУ, 2003. - 302с.

39. Голенков, Е.А. Методы автоматического построения модели параллельной программы в терминах сетей Петри / Е.А.Голенков, A.C. Соколов // Вычислительные методы и программирование, 2005. - Т.6. -С.196-201

40. Грин, Д., Кнут, Д. Математические методы анализа алгоритмов / Д.Грин, Д.Кнут — Пер. с англ. — М.: Мир, 1987. — 120с.

41. Дейкстра, Э. Дисциплина программирования / Э.М.Дейкстра. -«Мир», 1978.-280с.

42. Демьянович, Ю.К., Евдокимова, Т.О. Теория распараллеливания и синхронизация. Учебное пособие / Ю.К.Демьянович, Т.О.Евдокимова. - Изд-во СПбГУ, 2005.- 108 с.

43. Демьянович, Ю.К., Иванцова, О.Н. Технология программирования для распределенных параллельных систем / Ю.К.Демьянович, О.Н.Иванцова,- Изд. СПбГУ. 2005. - 93с.

44. Демьянович, Ю. К., Бурова, И.Г. Алгоритмы параллельных вычислений и программирование. Курс лекций / Ю.К.Демьянович, И.Г.Бурова - СПб: Изд-во С.-Петерб. ун-та, 2007. - 206 с.

45. Джон, Э. Сэвидж. Сложность вычислений / Э. Джон — М.: Факториал, 1998. — 368с.

46. Дунаев, A.B. Инструментальная оболочка поддержки принятия решений разработчика высокопроизводительных приложений в Грид / A.B. Дунаев, A.B. Ларченко, A.B. Бухановский // Научно-технические ведомости СПбГПУ — 2008,— №5. — С.98-104.

47. Дунаев, A.B. Инструментальная оболочка проектирования высокопроизводительных приложений в Грид. Часть II: Архитектура,

реализация и применение / A.B. Ларченко, A.B. Дунаев, A.B. Бухановский // Научно-технический вестник СПбГУ ИТМО: Технологии высокопроизводительных вычислений и компьютерного моделирования. — 2008. — Вып. 54. — С. 37-45.

48. Евреинов, Э. В., Хорошевский, В. Г. Однородные вычислительные системы / Э.В.Евреинов, В.Г.Хорошевский - Новосибирск: Наука. Сибирское отд-е, 1978.-319с.

49. Евреинов, Э. В., Косарев, Ю. Г. Однородные универсальные вычислительные системы высокой производительности / Э.В.Евреинов, Ю.Г.Косарев - Новосибирск: Наука. Сибирское отд-е, 1966. - 308с.

50. Евстигнеев, В., Касьянов, В. Толковый словарь по теории графов в информатике и программировании / В.Евстигнеев, В.Касьянов -Нововсибирск: Наука. Си. Предприятие РАН, 1999. - 291с.

51. Емеличев, В. А., Мельников, О. И., Сарванов, В. И., Тышкевич, Р. И. Лекции по теории графов. Изд.2, испр. / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р. И.Тышкевич . - М.: УРСС, 2009. 392с.

52. Иванов, C.B. Идентификация параметрически связанных моделей сложных систем. / C.B. Иванов // Научно-технический вестник СПбГУ ИТМО. Выпуск 54. Технологии высокопроизводительных вычислений и компьютерного моделирования. - СПб.: СПбГУ ИТМО, 2008. - С. 100-107.

53. Иванов, A.B. Формализация задачи оптимальной организации параллельных вычислений в системах обработки сигнальной информации реального времени / А.В.Иванов, В.А.Овчинников // Вычислительные сети, теория и практика. - 2009. - №1 (14). - С. 168-176

54. Икрамов, Х.Д. Численные методы для симметричных линейных систем: прямые методы / Х.Д.Икрамов - М.: Наука, 1988. - 157с.

55. Икрамов, Х.Д. Численные методы линейной алгебры (Решение линейных уравнений) / Х.Д.Икрамов - М.: Знание, 1987. - 46с.

56. Икрамов, Х.Д. Вычислительные методы линейной алгебры (Решение больших разреженных систем уравнений прямыми методами) / Х.Д.Икрамов - М.: Знание, 1989.-48с.

57. Икрамов, Х.Д. Разреженные матрицы / Х.Д.Икрамов - М.: сб. "Итоги науки и техники. Математический анализ", т. 20, 1982. - С. 179-260.

58. Калиниченко, J1.A. Методы и средства интеграции неоднородных баз данных / Л.А.Калиниченко - М.: Наука, 1983. - 424с.

59. Касьянов, В.Н., Евстигнеев, В.А. Графы в программировании: обработка, визуализация и применение / В.Н.Касьянов, В.А.Евстигнеев -СПб.: БХВ-Петербург, 2003. - 1104с.

60. Ковальчук, С.В Особенности построения масштабируемых композитных вычислительных приложений для моделирования сложных систем /C.B. Ковальчук, C.B. Иванов, A.B. Бухановский // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции (21-26 сентября 2009 г., г. Новороссийск). - М.: Изд-во МГУ, 2009. - С.53-57.

61. Когаловский, М. Р. Концептуальное и онтологическое моделирование в информационных системах / М. Р. Когаловский, Л. А. Калиниченко // Программирование. - 2009. - N 5. - С.3-25

62. Корнеев, В.Д. Параллельные алгоритмы решения задач линейной алгебры / В.Д.Корнеев - Новосибирск, 1998. - 27с. - (Препринт / РАН. Сиб. отд-ние. ИВМиМГ; 1124)

63. Корнеев, В.Д. Параллельное программирование в MPI / В.Д.Корнеев - Новосибирск: Издательство СО РАН, 2000. - 220с.

64. Корячко, В. П. Иерархическая модель глобальной оптимизации у параллельных объектных программ / В.П.Корячко, C.B. Скворцов // Наука и образование, 2006. - №8. - С. 156-164.

65. Костенецкий, П.С. Технологии параллельных систем баз данных для иерархических многопроцессорных сред / П.С.Костенецкий,

А.В.Лепихов, Л.Б.Соколинский // Автоматика и телемеханика. -2007. -Том 68, №5. -С.847-859.

66. Костенко, В.А. Алгоритмы оптимизации, опирающиеся на метод проб и ошибок, в совместном проектировании аппаратных и программных средств ВС / В.А. Костенко // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения». - М.: Изд-во МГУ, 2000. - С.86-94.

67. Костенко, В.А., Смелянский, Р.Л., Трекин, А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов / В.А.Костенко, Р.Л.Смелянский, А.Г.Трекин - М.: Изд-во МГУ, 2000.-98с.

68. Костенко, В.А., Романов, В.Г., Смелянский, Р.Л. Алгоритмы минимизации аппаратных ресурсов ВС / Костенко В.А., Романов В.Г., Смелянский Р.Л. - М.: Изд-во МГУ, 2000. - 86с.

69. Котов, В.Е. Сети Петри / В.Е.Котов- М.: Наука, 1984. - 160с.

70. Кормен, Т. X. Алгоритмы: построение и анализ, 2-е издание; пер. с англ. под ред. И. В. Красикова / Т.Х.Кормен - М.: Издательский дом "Вильяме", 2005.- 1296с.

71. Коффман, Э.Г. Теория расписаний и вычислительные машины/ Под редакцией Э.Г. Коффмана. -М.: Наука, 1984. -335с.

72. • Крёнке, Д. Теория и практика построения баз данных. 8-е изд./ Д.Крёнке - СПб.: Питер, 2003. -800с.

73. Кузнецов, С.Д. Транзакционные параллельные СУБД: новая волна. / С.Д. Кузнецов //Труды Института системного программирования. - М.: ИСП РАН, 2011,- Т.20. - С. 189-251.

74. Кузнецов, С.Д. Год эпохи перемен в технологии баз данных / С.Д. Кузнецов // Труды Института системного программирования, - М.: ИСП РАН, 2010.-Т.19.-С.9-33.

75. Кузнецов, С.Д. Объектно-реляционные базы данных: прошедший этап или недооцененные возможности? / С.Д. Кузнецов // Труды Института

системного программирования. - М.: ИСП РАН, 2007. - Т. 13, часть 2. -С.115-140.

76. Курносов, М.Г. Алгоритмы вложения параллельных программ в иерархические распределённые вычислительные системы / М.Г.Курносов // Вестник СибГУТИ. - 2009. - № 2 (6). - С.20-45.

77. Кутепов, В.П. Среда объектно-ориентированного граф-схемного потокового параллельного программирования для многоядерных кластеров. / В.П.Кутепов, Д.В.Котляров, В.Н.Маланин, H.A. Панков // Материалы шестого Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». - СПб: Санкт-Петербургский госуниверситет, 2007. - Т.1. - С.253-258.

78. Лацис, А. О. Параллельная обработка данных: учебное пособие / Лацис А. О. - М.: Академия, 2010 .- 336с.

79. Левин, В.И. Структурно-логические методы в теории расписаний /

B.И.Левин - Пенза: Изд-во Пенз. гос. технол. акад., 2006. - 128с.

80. Лиходед, H.A. Распределение операций и массивов данных между процессорами / Лиходед H.A. // Программирование. 2003. - №3. - С.73-80.

81. Лепихов, A.B. Стратегия размещения данных в многопроцессорных системах с симметричной иерархической архитектурой / A.B. Лепихов, Л.Б.Соколинский // Научный сервис в сети Интернет: технологии параллельного программирования: Труды Всероссийск. науч. конф. (18-23 сентября 2006 г., г. Новороссийск). - М.: Изд-во МГУ. 2006.

C.39-42.

82. Лупин, С. А., Посыпкин, М. А. Технологии параллельного программирования / С.А.Лупин, М.А.Посыпкин - М.: Инфра-М, 2008. - 208с.

83. Макконелл, Дж. Основы современных алгоритмов / Дж. Макконелл - Изд. 2 доп. — М.: Техносфера, 2004. — 368 с.

84. Макконелл, С. Совершенный код. Мастер-класс / пер. с англ / С.Макконелл - М.: Издательско-торговый дом «Русская редакция»; СПб: Питер,-2005.-896с.

85. Малышкин, В.Э. Основы параллельных вычислений/ В.Э. Малышкин - Методическое пособие, Изд-во НГТУ, 1999. - 55с.

86. Математический энциклопедический словарь. - М.: Советская энциклопедия, 1988. - 548с.

87. Мейер, Д. Теория реляционных баз данных / Мейер Д. - М.: Мир, 1987.-608с.

88. Миллер, Р., Боксер, JI. Последовательные и параллельные алгоритмы с описанием параллельных алгоритмов на графах, умножения матриц, обработки изображений, вычислением многочленов / Р.Миллер, Л.Боксер - Изд-во.: Бином.Лаборатория знаний., 2006. - 408с.

89. Монахов, О.Г., Монахова, Э.А. Параллельные системы с распределенной памятью: управление ресурсами и заданиями / О.Г.Монахов, Э.А.Монахова - Новосибирск: Изд-во ИВМиМГ СО РАН, 2001. - 168с.

90. Муромцев, Д.И. Онтологический инжиниринг знаний в системе Protégé / Д.И.Муромцев - СПб: СПб ГУ ИТМО, 2007. - 62с.

91. Немнюгин, С.А., Стесик, О.Л. Параллельное программирование для многопроцессорных вычислительных систем / С.А.Немнюгин, О.Л.Стесик - СПб.: БХВ-Петербург, 2002. - 400с.

92. Николаев, Е.С. Разреженные матрицы. Библиотека программ / Е.С.Николаев - М.: МГУ, 1986. - 120с.

93. Ope, О. Теория графов / О.Ope - M.: 2-е изд., Наука, 1980. - 336с.

94. Ортега, Дж. Введение в параллельные и векторные методы линейных систем: Пер. с англ. / Дж.Ортега- М.: Мир, 1991. - 367с.

95. Оселедец, И.В. Применение разделенных разностей и В-сплайнов для построения быстрых дискретных преобразований вейвлетовского типа на неравномерных сетках / И.В.Оселедец // Мат.заметки, 2005. - 75:5, С.743-752.

96. Панкратьев, Е. В. Элементы компьютерной алгебры / Панкратьев Е. В. - М.: Интернет-университет информационных технологий, 2007. - 306с.

97. Писсанецки, С. Технология разреженных матриц: Пер. с англ. / Писсанецки С. - М.: Мир, 1988,- 410с.

98. Плотников, А.Д. Эвристический алгоритм для поиска наибольшего независимого множества. / А.Д.Плотников // Кибернетика и системный анализ. 2012. №5. - С.41-48.

99. Питерсон, Дж. Теория сетей Петри и моделирование систем / Дж.Питерсон - М., «Мир», 1984. - 264с.

100.Роб, П., Коронел, К. Системы баз данных: проектирование, реализация и управление / П.Роб, К.Коронел — 5-е изд., перераб. и доп. -СПб.: БХВ-Петербург, 2004. - 1040с.

101.Рудикова, J1.B. Базы данных. Разработка приложений / Л.В.Рудикова-СПб.: БХВ-Петербург, 2006. - 496с.

102.Сигал, И, Иванова, А. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы / И. Сигал,

A.Иванова - М.: Физматлит, 2003. - 304с.

ЮЗ.Сигорский, В.П. Математический аппарат инженера/

B.П.Сигорский - Киев: Техника, 1975.-766с.

104.Скворцов, C.B. Оптимизация кода для суперскалярных процессоров с использованием дизъюнктивных графов / C.B.Скворцов // Программирование. 1996. № 2. С.41—52.

105.Соколинский, Л.Б. Классификация и анализ параллельных архитектур систем баз данных / Л.Б. Соколинский // Алгоритмы и программные средства параллельных вычислений: [Сб. науч. Тр.]. Екатеринбург: УрО РАН. 2003. -Вып. 7. - С.185-216.

106.Соколинский, Л.Б. Обзор архитектур параллельных систем баз данных / Л.Б.Соколинский // Программирование. -2004.№6. -С.49-63.

107. Соколинский, Л.Б. Организация параллельного выполнения запросов в многопроцессорной машине баз данных с иерархической архитектурой / Л.Б. Соколинский // Программирование. - 2001.№6. -С. 13-29.

108.Стефанов, К.С. Система анализа информационной структуры программ./ Стефанов К.С. // Вычислительные методы и программирование, 2005. - Т.6. - С.142-154.

109.Таненбаум Э.С. Распределенные системы. Принципы и па-радигмы / Э.С. Таненбаум - Санкт-Петербург: Питер, 2003. — 876с.

ПО.Тарков, М.С. Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем / М.С.Тарков // Автометрия. - 2003. - Том 39, № 3. - С.84 - 96.

Ш.Толстобров, А.П. Управление данными. Учебное пособие. / А.П. Толстобров - Воронеж: Изд-во Воронежского ГУ, 2007 - 205с.

112.Топорков, В.В. Модели распределенных вычислений / В.В.Топорков — М.: Физматлит, 2004. — 315с.

113.Топорков, В.В. Управление заданиями в распределенных средах с неотчуждаемыми ресурсами / В.В.Топорков //Изв. РАН. Сер. Теория и системы управления . 2011. - С. 164-178.

114.Турусов, С. Н. Разработка оптимальных алгоритмов управления процессом получения алюминия по заданным критериям. Спец. 05.13.01 : диссертация на соискание ученой степени канд. тех. наук / С. Н. Турусов // -Братск : БрГТУ, 2000. - 142с.

115.Тьюарсон, Р.Разряженные матрицы Под редакцией Икрамова Х.Д. / Р.Тьюарсон - М.: Мир, 1977. - 190с.

116.Форсайт, Дж., Малькольм, М., Моулер, К. Машинные методы математических вычислений / Дж.Форсайт, М.Малькольм, К.Моулер - М.: Мир, 1980.-290с.

117.Хаггарти, Р. Дискретная математика для программистов / Р.Хаггарти-М.: Техносфера, 2005.- 400с.

118.Харари, Ф. Теория графов: Пер. с англ./ Ф.Харари - М.: Мир, 1973. -254с.

119.Хомоненко, А.Д. Базы данных/ А.Д. Хомоненко - Санкт-Перербург: "КОРОНА-принт", 2003. -416с.

120.Хорошевский, В.Г. Архитектура вычислительных систем / В.Г.Хорошевский - М. : МГТУ им. Н. Э. Баумана, 2008. - 520с.

121.Цымблер, M.JI. Методы организации управления данными в многопроцессорных вычислительных системах с массивно-параллельной архитектурой / М.Л.Цымблер // Вестник молодых ученых. Серия "Технические науки", 2002. - № 9. - С. 75-87.

122.Цымблер, М.Л., Соколинский, Л.Б. Организация распределенной обработки больших массивов данных в вычислительных системах с массовым параллелизмом / М.Л.Цымблер, Л.Б.Соколинский // Высокопроизводительные вычисления и их приложения: Труды Всероссийск. науч. конф. (30 октября - 2 ноября 2000 г., г. Черноголовка). - М.: Изд-во МГУ, 2000. - С.186-190.

123.Шамакина, A.B., Соколинский, Л.Б. Методика тестирования инструментальных комплексов для построения параллельных программ / А.В.Шамакина, Л.Б.Соколинский // Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ: Труды Всероссийск. науч. конф. (24-29 сентября 2007 г., Новороссийск). - М.: Изд-во МГУ, 2007. - С. 227-230.

124.Швецов, В.И., Визгунов, А.Н., Мееров, И.Б. Базы данных. Учебное пособие/ В.И.Швецов, А.Н.Визгунов, И.Б.Мееров. - Н.Новгород: Изд-во ННГУ. - 2004. -271с.

125.Штейнберг, Б.Я. Преобразования программ для открытой распараллеливающей системы / Б.Я.Штейнберг, Д.Н.Черданцев, С.А.Науменко, А.Э.Бутов, В.В.Петренко // Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. - Украина, Донецк, ДонДИШИ, Наука и Освита, 2003. -№3. - С.97-104.

126.Штейнберг, Б.Я. Оптимальные параллельные переразмещения двумерных массивов / Б.Я.Штейнберг // Программирование. 1993. - №6. -С.81-88.

127.Штейнберг, Б.Я. Математические методы распараллеливания рекуррентных циклов для суперкомпьютеров с параллельной памятью / Б.Я.Штейнберг - Ростов н/Д: Изд-во Рост.ун-та, 2004. - 192с.

128.Эндрюс, Г.Р. Основы многопоточного, параллельного и распределенного программирования.: пер.с англ. / Г.Р.Эндрюс -М.:Издательский дом «Вильяме», 2003. - 512с.

129.Эстербю Оле, Златев Захарий. Прямые методы для разреженных матриц. Перевод с англ. Икрамов Х.Д. / Оле Эстербю, Захарий Златев. - М.: Мир, 1987. - 118с.

130.Шичкина, Ю.А. Программное обеспечение по работе с разреженными матрицами / Ю.А.Шичкина, Ю.Н.Алпатов // Естественные и инженерные науки - развитию регионов: Материалы межрегиональной НТК.

- Братск, БрГТУ , 2003 - С.39-40.

131.Шичкина, Ю.А. Машинная реализация алгоритма приведения разреженной матрицы к форме BDF. / Ю.А.Шичкина, Ю.Н.Алпатов // Естественные и инженерные науки - развитию регионов: Материалы межрегиональной НТК. - Братск, БрГТУ, 2003 - С.38-39.

132.Шичкина, Ю.А. Разработка методики решения больших разреженных систем линейных алгебраических уравнений (СЛАУ) / Ю.А.Шичкина // Естественные и инженерные науки - развитию регионов: Материалы межрегиональной НТК. - Братск, БрГТУ , 2003 - С.48-49.

133.Шичкина, Ю.А. Разреженные матрицы в синтезе систем управления методом структурных графов / Ю.А.Шичкина //Естественные и инженерные науки - развитию регионов: Материалы межрегиональной НТК.

- Братск, БрГТУ , 2003 - С.45-46.

134.Шичкина, Ю.А. Разработка прямого метода для приведения матрицы в модели управления процессом получения алюминия к форме BDF. / Ю.А.Шичкина // Естественные и инженерные науки - развитию регионов: Материалы межрегиональной НТК. - Братск, БрГТУ , 2003 - С.47-48.

135.Шичкина, Ю.А. Применение параллельной формы информационного графа в задачах распараллеливания с использованием разреженных матриц. / Ю.А.Шичкина // Информационно-измерительные и управляющие системы. - 2008. - № 4, т. 6. - С.63-67.

136.Шичкина, Ю.А. Применение матричной алгебры для оптимизации параллельных алгоритмов. / Ю.А.Шичкина // Информационно-измерительные и управляющие системы. - 2008. - № 10, т. 6. - С.72-77.

137.Шичкина, Ю.А. Сокращение высоты информационного графа параллельного алгоритма. / Ю.А.Шичкина // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. -2009. - №3(80). -С.148-152.

138.Шичкина, Ю.А. Применение онтологического моделирования для описания параллельных процессов. / Ю.А.Шичкина // Информационно-измерительные и управляющие системы. - 2009. - №4, т.7. - С.27-28.

139.Шичкина, Ю.А. Применение онтологического моделирования для описания параллельных процессов. / Ю.А.Шичкина // Программируемые инфокоммуникационные технологии. Сборник статей /под ред. В.В.Александрова, В.А.Сарычева.-М..-Радиотехника, 2009. - С.27-28.

ИО.Шичкина, Ю.А., Преобразование информационного графа параллельного алгоритма / Ю.А.Шичкина //Современные технологии. Системный анализ. Моделирование. -2010-№1(25) - С.133-137

141.Шичкина, Ю.А. Управление данными. Учебное пособие./ Ю.А.Шичкина - Братск: ГОУ ВПО БрГУ, 2007. - 138с.

142.Шичкина, Ю.А. Проектирование баз данных в среде Delphi 7.0 Учебное пособие / Ю.А.Шичкина - Братск: ГОУ ВПО БрГУ, 2008. - 132с.

НЗ.Шичкина, Ю.А. Определение функции времени выполнения алгоритма. / Ю.А.Шичкина // Математическое моделирование, численные методы и комплексы программ: Межвуз.темат.сб.тр. - СПб.:СПбГАСУ. -2004,- Вып. 10. - С.218-220.

144.Шичкина, Ю.А. Проблема улучшения качества проектирования реляционных баз данных. / Ю.А.Шичкина // Математическое моделирование и комплексы программ: Межвузовский тематический сборник трудов. -СПб.:СП6ГАСУ, 2005. - Вып. 11. - С. 124-127.

145.Шичкина, Ю.А. Оптимизация параллельного алгоритма по числу процессов. / Ю.А.Шичкина, В.И.Воробьев // Вестник гражданских инженеров,- 2008. - № 2(15). - С.92-97

146.Шичкина, Ю.А. Применение формализованного метода неограниченного хаоса в реляционных моделях баз данных / Ю.А. Шичкина // Математическое моделирование и комплексы программ: Межвузовский тематический сборник трудов. - СПб.:СПбГАСУ. -2009. - Вып.15. - С.199-204.

147.Шичкина, Ю.А. Декомпозиция реляционного отношения методом ограниченного хаоса / Ю.А.Шичкина // Системы. Методы. Технологии. Братск:БрГУ,2010, №3. - С. 152-156

148.Шичкина Ю.А. От метода неограниченного хаоса к матричному методу оптимизации реляционных моделей баз данных / Ю.А.Шичкина // Наука в информационном пространстве: материалы V Между нар. науч.-практ.конф,30-31 окт.2009.: В6 т. - Т.1. - Днепропетровск, 2009. - С. 120-124.

149.Шичкина, Ю.А. Временные оценки параллельного алгоритма / Ю.А. Шичкина // Труды Братского государственного университета: Сер.: Естественные и инженерные науки - развитию регионов Сибири. - Братск: БрГУ, 2009. - С.86-87.

150.Шичкина, Ю.А. Временная сложность алгоритмов / Ю.А. Шичкина // Естественные и инженерные науки - развитию регионов: Материалы межрегиональной НТК.-Братск:БрГТУ,2004. - С. 112-113.

151.Шичкина, Ю.А. Разреженные матрицы в базах данных / Ю.А. Шичкина // Естественные и инженерные науки - развитию регионов: Материалы межрегиональной НТК.-Братск:БрГТУ,2004. - Cl 13-114.

152.Шичкина, Ю.А. Автоматизация процесса нормализации реляционных баз данных / Ю.А. Шичкина // Наука.Технологии.Инновации. Материалы всеросийской научной конференции молодых ученых в 6-ти частях. - Новосибирск:Изд-во НГТУ, 2004. Часть 1. - С. 176-179.

153.Шичкина, Ю.А. Взвешенные графы в параллельных вычислениях / Ю.А. Шичкина // Современные наукоемкип технологии. - 2009 - №11. -С.93-97.

154.Шичкина, Ю.А., Построение информационного графа нормализации реляционных отношений. / Ю.А. Шичкина // Системы. Методы. Технологии. - Братск:БрГУ, 2010. - №1(5). - С.74-84.

155.Шичкина, Ю.А., Распараллеливание алгоритма нормализации реляционных отношений. / Ю.А. Шичкина // Системы. Методы. Технологии. . - Братск:БрГУ, 2010. - №2(6). - С.69-11.

156.Шичкина, Ю.А., Комбинированный метод многопараметрической оптимизации взвешенного информационного графа / Ю.А. Шичкина //Системы. Методы. Технологии, 2010 - №3(7). - С.76-82.

157.Шичкина, Ю.А. Алгоритмизация процесса получения новых функциональных зависимостей на основе декларированных. / Ю.А. Шичкина // Автоматизация и современные технологии. 2010, №8 - С.144-150.

15 8. Шичкина, Ю.А. Преобразование разреженной матрицы к треугольному виду. / Ю.А.Шичкина, М.С.Куприянов // Вестник гражданских инженеров. 2013. -№3 (38). - С.233-236.

159.Шичкина, Ю.А. Применение блочной треугольной формы разреженной матрицы для преобразования информационного графа алгоритма / Ю.А. Шичкина // Вестник гражданских инженеров.- 2012 -№4(33). - С.259-263.

160.Шичкина, Ю.А. Применение списков следования для преобразования информационного графа по высоте / Ю.А. Шичкина // Системы. Методы. Технологии. 2011. - № 9. - С. 68-77.

161.Шичкина, Ю.А. Применение теории графов для разработки прямого метода построения деревьев решений / Ю.А.Шичкина, М.С.Куприянов // Системы. Методы. Технологии. 2012. - № 4(16). - С.62-65.

162.Шичкина, Ю.А. Распределение параллельных программ между ролями-сотрудниками в облачном кластере / Ю.А. Шичкина // Системы. Методы. Технологии. 2012. - № 2. - С.59-63.

163. Шичкина, Ю.А. Применение блочной треугольной формы разреженной матрицы для преобразования информационного графа алгоритма / Ю.А. Шичкина // Современные технологии. Системный анализ. Моделирование. 2010. - № 4. - С. 117-120.

164. Шичкина, Ю.А. Применение теории графов для разработки прямого метода построения деревьев решений / Ю.А.Шичкина, М.С.Куприянов // Известия СПбГЭТУ "ЛЭТИ". 2012. - № 9. - С.68-74.

165. Шичкина, Ю.А, Математическое моделирование системы качества как механизм улучшения его показателей / Ю.А. Шичкина, Ю.В.Планкова // Системы. Методы. Технологии. 2012. -№ 3. - С.53-55.

166.Шичкина Ю.А. Применение методов автоматического анализа при формировании контрольных цифр приема в учреждения профессионального образования / Ю.А. Шичкина, Ю.В.Планкова // Системы. Методы. Технологии. 2013. - № 2 (18). - С.82-87.

167.Шичкина Ю.А. Проектирование баз данных в среде С# Учебное пособие. / Ю.А. Шичкина, В.С.Кедрин. - Братск: ГОУ ВПО БрГУ, 2011. -122с.

168.Шичкина, Ю.А. Организация вычислений на распределенных системах / Ю.А. Шичкина. - ФГБОУ ВПО БрГУ, 2013. - 176с.

169. Шичкина Ю.А. Преобразование разреженных матриц (ВОР+) VI.0: программа для ЭВМ. Св. ГР. №2012618115 Рос. Федерация; зарег. в реестре Федер. службы по интеллектуальной собственности, пат. и товарным знакам 10.11.2012.

170. Шичкина Ю.А. Построитель реляционных схем (Create Scheme) vl.O: программа для ЭВМ. Св. ГР. №2012618116 Рос. Федерация; зарег. в реестре Федер. службы по интеллектуальной собственности, пат. и товарным знакам 10.11.2012.

171. Шичкина Ю.А. Распараллеливание последовательных алгоритмов vl.O: программа для ЭВМ. Св. ГР. №2012618117 Рос. Федерация; зарег. в реестре Федер. службы по интеллектуальной собственности, пат. и товарным знакам 10.11.2012.

Примеры перебора путей графа

Пример 1. Дан информационный граф.

С Р

Найти кратчайший путь от вершины А к вершине Н. Решение.

Матрица смежности:

А в с р Е V в и

А 0 2 3 0 1 0 0 0

В 0 0 0 2 2 0 0 0

С 0 0 0 0 0 3 0 0

Р 0 0 0 0 0 0 1 3

Е 0 0 1 0 0 3 0 0

? 0 0 0 0 0 0 1 0

С 0 0 0 0 0 0 0 1

Н 0 0 0 0 0 0 0 0

Алгоритм:

А В С О Е Е в И

АЕ 0 0 2 0 0 4 0 0

АВ 0 0 0 4 0 0 0 0

АС 0 0 0 0 0 6 0 0

А В с Е Е в и

АЕС 0 0 0 0 0 0 0 0

АЕЕ 0 0 0 0 0 0 5 0

АВй 0 0 0 0 0 0 5 7

АСЕ 0 0 0 0 0 0 7 0

Пути АЕЮН=7

А В С О Е Е н

АЕЕв 0 0 0 0 0 0 0 6

АВОС 0 0 0 0 0 0 0 6

АС Ей 0 0 0 0 0 0 0 8

Пути

АЕЕСН=6 АСЕСН=6

Алгоритм закончен. Минимальный путь: АЕРСН, с1[АЕГСН]=6

Пример 2. Дан информационный граф.

С Р

Найти кратчайший путь от вершины А к вершине Н. Решение.

Матрица смежности:

А А в с О Е р в н

0 2 3 0 1 0 0 0

В 0 0 0 1 2 0 0 0

С 0 0 0 0 0 3 0 0

Э 0 0 0 0 0 0 1 2

Е 0 0 1 0 0 3 0 0

Р 0 0 0 0 0 0 1 0

в 0 0 0 0 0 0 0 2

Н 0 0 0 0 0 0 0 0

1)

А В С й Е р с Н

АЕ 0 0 2 0 0 4 0 0

АВ 0 0 0 3 0 0 0 0

АС 0 0 0 0 0 6 0 0

А В с й Е Р й н

АЕС 0 0 0 0 0 0 0 0

АЕР 0 0 0 0 0 0 5 0

АВО 0 0 0 0 0 0 4 5

АСР 0 0 0 0 0 0 7 0

Пути АЕЮН=5

3)

А В С й Е р н

АЕРС 0 0 0 0 0 0 0 7

АВОв 0 0 0 0 0 0 0 0

АСРС 0 0 0 0 0 0 0 9

Пути

АЕРСН=7 АСРСН=9

Алгоритм закончен. Минимальный путь: АВйН, с![АВОН]=5