Содержание к диссертации
Введение
Глава 1. Обзор способов представления распределенных структур и методов их обработки 32
1.1. Ориентированные, взвешенные графы и деревья 33
1.2. Матричные алгоритмы на графах 43
1.3. Технологии обработки разреженных матриц 44
1.4. Методы определения трудоемкости алгоритмов 51
1.5. Оптимизация вычислений за счет распараллеливания алгоритмов 57
Выводы 61
Глава 2. Методы преобразования разреженных прямоугольных матриц с сохранением первоначальных значений 64
2.1. Примеры задач, сводимых к разреженным матрицам 64
2.2. Приведение разреженной матрицы к односторонне окаймляющей блочной диагональной форме 67
2.3. Приведение разреженной матрицы к треугольной форме 70
2.3.1. Метод ненулевой диагонали 71
2.3.2. Метод уплотнения вниз 77
Выводы 83
Глава 3. Организация последовательных и параллельных вычислений 84
3.1. Матричный метод перебора путей в графе 87
3.2. Построение параллельного алгоритма на основе его последовательного аналога с последующей оптимизацией по числу процессоров 88
3.2.1. Матричное преобразование алгоритмов и их оптимизация по числу процессоров 88
3.2.2. Оптимизация алгоритмов по ширине с применением списков смежности 99
3.2.3. Оптимизация алгоритмов по ширине с применением списков следования 104
3.3. Оптимизация параллельных алгоритмов по времени выполнения 109
3.3.1. Матричное преобразование алгоритма с целью
оптимизации по времени выполнения 111
3.3.2. Оптимизация алгоритма по времени выполнения с
применением списков следования 117
3.4. Оптимизация алгоритмов по нескольким параметрам 132
Выводы 138
Глава 4. Методы конструирования реляционных схем на основе метаданных функциональных зависимостей 140
4.1. Проблемы аномалии избыточности в различных моделях данных 140
4.2. Функциональные зависимости реляционных отношений 141
4.2.1. Представление функциональных зависимостей с помощью графов 141
4.3. Построение реляционной модели на основе орграфа функциональных зависимостей 150
4.4. Декомпозиция отношения на основе орграфа простых функциональных зависимостей 157
4.5. Метод получения новых функциональных зависимостей на основе декларированных 164
4.6. Определение ключей по орграфу функциональных зависимостей 170
4.7. Декомпозиция отношения на основе орграфа составных функциональных зависимостей 176
Выводы 179
Глава 5. Применение разработанных методов на различных прикладных задачах 181
5.1. Задача 1. Распараллеливание алгоритма конструирования реляционных схем 181
5.1.1. Построение информационного графа алгоритма 181
5.1.2. Оптимизация информационного графа алгоритма нормализации реляционных отношений 194
Выводы 208
5.2. Задача 2. Организация преобразований в системах, основанных на расписании 210
5.2.1. Выполнение параллельных процессов в системе 210
5.2.2. Графовый метод распределения задач на кластере 213
5.2.3. Матричный метод распределение задач 225
5.2.4. Применение онтологии при организации процесса распределения задач на кластере
Выводы 243
5.3. Задача 3. Тестирование разработанных методов на модели управления процессом электролиза алюминия 245
5.3.1. Структурная идентификация процесса получения алюминия 245
5.3.2. Выбор метода решения системы линейных уравнений 249
5.3.3. Применение методов распараллеливания к алгоритму по приведению разреженной матрицы к форме BDF на модели управления процессом электролиза алюминия 260
Выводы 271
5.4. Задача 4. Применение матричных методов в теории принятия решений 273
5.4.1. Особенности алгоритмов построения дерева решений 273
5.4.2. Применение методов распараллеливания к алгоритму ID3 276
5.4.3. Матричный метод построения дерева решений 286
Выводы 293
Заключение 294
Список литературы
- Матричные алгоритмы на графах
- Приведение разреженной матрицы к односторонне окаймляющей блочной диагональной форме
- Матричное преобразование алгоритмов и их оптимизация по числу процессоров
- Построение реляционной модели на основе орграфа функциональных зависимостей
Введение к работе
I. Актуальность темы исследования В настоящее время параллельное программирование, несмотря на интенсивное развитие вычислительных систем, новых методов и языков программирования, по-прежнему остается областью, в которой проблема разбиения программы на процессы ложится на разработчика, от квалификации которого, следовательно, зависит качество получаемых в результате решений прикладных задач. Отрицательно сказывается на качестве работы вручную разрабатываемой параллельной программы также рост алгоритмической сложности решаемых задач, что можно объяснить следующими обстоятельствами: чрезвычайно быстрый рост сложности объектов моделирования; необходимость управления сложными промышленными и технологическими процессами в режиме реального времени и в условиях неопределенности; рост числа задач, для решения которых необходимо обрабатывать гигантские объемы информации.
Уменьшить влияние человеческого фактора на процесс разработки параллельных программ возможно, если переложить на ЭВМ функции по расчету числа необходимых для решения прикладной задачи процессоров и построение модели будущей параллельной программы.
Актуальность темы исследования обусловлена следующими факторами.
1. Ограниченность вычислительных ресурсов. Вычислительные системы
развиваются очень быстро. Размер оперативной памяти и скорость работы про
цессора растет год от года, но еще быстрее растут требования к качественной
стороне математических моделей, что ведет к увеличению числа параметров
моделей. В результате появляется необходимость поиска методов системных
переходов от существующих последовательных систем вычислений к распреде
ленным системам обработки данных.
2. Отсутствие аппарата по анализу эффективности параллельных про
грамм. Параллельное программирование, как и обычное программирование,
опирается на алгоритмы и структуры данных. Не эффективно работающая про
грамма – это прямые потери производительности компьютера, средств на его
приобретение и усилий на решение задач. Таких потерь хотелось бы избежать
или, по крайней мере, их минимизировать. Для этого необходимы апробирован
ные методы исследования, разработки и эквивалентных преобразований алго
ритмов.
К основным недостаткам существующих методов разработки и эквивалентных преобразований параллельных алгоритмов можно отнести:
– отсутствие этапа анализа структуры алгоритма, для реализации которого проектируется параллельная программа — вместо этого предлагается применять различные эвристики;
– необходимость на каждом шаге поиска оптимальной структуры вычислительной системы решать задачу построения по возможности оптимального расписания организации вычислительного процесса (являющуюся, в общем случае, NP-полной задачей);
– зависимость качества получаемых с помощью эвристик решений от начального приближения и структуры исследуемого алгоритма обработки информации.
3. Неполнота совокупности всех существующих алгоритмов, предназна
ченных для решения прикладных задач. В процессе длительного использования
последовательных компьютеров был накоплен и тщательно отработано огром
ное количество алгоритмов для самых разных прикладных задач. Среди них,
применительно к области параллельного программирования, необходимо выде
лить следующие алгоритмы и связанные с ними пробелы:
Алгоритмы на графах имеют пробелы в решении проблем, связанных с реструктуризацией систем при заданных ограничениях на структуру системы и необходимостью промежуточного сбора и анализа метаданных системы.
Алгоритмы на разреженных матрицах. Отсутствие алгоритмов преобразования прямоугольной разреженной матрицы к новой форме с сохранением первоначальных значений параметров математической модели, несмотря на потребность в таких алгоритмах не только в области параллельных вычислений, но и теории принятия решений, синтеза систем управления производственными процессами и других областях.
-
Неэффективность использования кластеров. Кластерная архитектура занимает лидирующие позиции среди суперкомпьютеров, но современные кластеры, приобретаемые с запасом масштабируемости для решения самых больших задач организации, обычно большую часть времени простаивают, либо загружены незначительно. Повысить эффективность работы кластера возможно, если автоматизировать процесс распределения нагрузки между процессорами.
-
Отсутствие автоматизированных систем построения нормальных реляционных схем. Разработка эффективных алгоритмов обработки данных не может исключить этап построения качественной структуры хранения данных. От того, насколько удачно спроектирована система хранения данных напрямую зависит и скорость доступа к данным и работа приложений по обработке данных. На сегодняшний день требуется высококачественно проектировать и внедрять базы данных за весьма небольшое время. Необходимость управления сложными промышленными и технологическими процессами в режиме реального времени и в условиях неопределенности требует высокой степени надежности хранения информации и высокой скорости ее обработки. Ни одна из современных СУБД не проверяет схему базы данных на наличие аномалий, не смотря на
то, что современный аппарат прикладной математики позволяет автоматизировать этот процесс.
Разработка научных основ анализа и синтеза систем управления сложными многосвязными системами на основе метаданных об информационных зависимостях в них, с целью повышения качества работы в условиях повышенных требований ко времени отклика систем и объему обрабатываемых данных является своевременной и актуальной.
Объектом диссертационного исследования являются параллельные вычисления на кластерных системах.
Предметом диссертационного исследования являются модели, методы и алгоритмы эффективных параллельных вычислений на кластерных системах.
Целью диссертационного исследования является построение, теоретическое обоснование и практическое подтверждение применимости системы методов проектирования оптимальных по числу процессоров и времени исполнения параллельных программ и реляционных схем, а также методов их анализа и преобразований с сохранением первоначальных информационных зависимостей.
Основные задачи исследования
-
Анализ существующих методов и инструментальных средств, предназначенных для формализованного представления параллельных алгоритмов и реляционных схем, а также расчета количественных и качественных характеристик.
-
Получение оценки минимального количества необходимых процессоров для решения вычислительной задачи при фиксированном времени решения с помощью параллельного алгоритма.
-
Разработка методов проектирования параллельных алгоритмов, оптимальных по времени выполнения и числу процессоров, задействованных в решении поставленной задачи.
-
Разработка матричного представления операций реляционной алгебры и методов создания на их основе реляционных схем по декларированным функциональным зависимостям.
-
Разработка программного обеспечения для тестирования полученных методов и методики их применения в зависимости от количественных характеристик параллельного алгоритма и параметров очередного шага проектирования программы.
-
Применение разработанных методов и программного обеспечения к задачам принятия решений на основе эмпирических данных, масштабирования математической модели управления процессом электролиза алюминия, реструктуризации произвольно заданной базы данных и построения математической
модели выполнения параллельных программ на ЭВМ с кластерной архитектурой.
Методы исследования. Для решения поставленных задач использовались методы теории графов; параллельных вычислений, матричной алгебры, баз данных, синергетики, методы анализа алгоритмов и программ и численные методы.
Основные положения, выносимые на защиту
-
Методы обработки разреженных матриц с сохранением первоначальных значений математической модели;
-
Методы разработки и эквивалентных преобразований параллельных алгоритмов с учетом:
времени выполнения;
количества процессоров;
времени выполнения и числа процессоров.
-
Формулы расчета количества процессоров, необходимых для решения вычислительной задачи с помощью параллельного алгоритма;
-
Методы преобразования ориентированного графа в дерево функциональных зависимостей и создания реляционных схем на основе атрибутов предметной области и декларированных функциональных зависимостей;
-
Методы распределения задач на вычислительной системе кластерного типа;
-
Матричный метод построения дерева решений и формула, позволяющая оценить вероятность срабатывания каждого правила.
Научная новизна работы
К наиболее существенным научным результатам относятся следующие:
1. Разработан метод приведения разреженной матрицы к треугольному
виду, отличающийся сохранением первоначальных значений элементов, что яв
ляется необходимым требованием при задачах оптимизации параллельных алго
ритмов.
2. Разработаны методы построения и оптимизации информацион
ного графа параллельного алгоритма по ширине. Методы состоят из двух час
тей, которые могут применяться независимо друг от друга в зависимости от ре
зультатов исследования на промежуточном этапе метаданных. Методы основа
ны на матрице смежности, списках смежности и списках следования и отлича
ются.
3. Получены и обоснованы граничные условия числа задействованных
в параллельных вычислениях процессоров, по которым можно принимать реше
ние о дальнейшей разработке или эквивалентном преобразовании параллельной
программы.
-
Разработаны методы оптимизации параллельного алгоритма по времени выполнения, позволяющие осуществлять равномерную загрузку процессоров, сокращать время решения поставленной задачи и уменьшать ширину информационного графа, соответствующего данному алгоритму. Методы основаны на матрицах, списках смежности и списках следования.
-
Предложено представление функциональных зависимостей реляционных схем в матричном виде и получены матричные аналоги свойств функциональных зависимостей. В отличие от известных ранее способов представления и обработки функциональных зависимостей, предложенные матричные свойства позволяют дополнить современные СУБД отсутствующей в них функцией проверки реализуемых физических баз данных на корректность структуры и отсутствие аномалии избыточности.
-
Разработан метод построения реляционной схемы на основе атрибутов предметной области и декларированных функциональных зависимостей. Все получаемые схемы удовлетворяют нормальной форме Бойса-Кодда и имеют минимум аномалии избыточности.
-
Разработаны матричные методы построения замыкания функциональных зависимостей и нахождения первичного ключа реляционного отношения на основе функциональных зависимостей.
-
Разработан матричный метод построения дерева решений, который позволяет получать более широкую совокупность правил по сравнению с эвристическими методами. Совокупность правил может быть отрегулирована с помощью выведенных формул, позволяющих также оценить вероятность срабатывания правила. Разработанный матричный метод предпочтительнее эвристических методов за счет более низкой трудоемкости, компактной формы хранения данных и полноты получаемой совокупности правил.
9. Разработан программный комплекс для тестирования полученных методов и проведения дальнейших исследований в области параллельных вычислений, реляционных баз данных и теории принятия решений.
Обоснованность и достоверность полученных результатов обеспечивается корректностью применяемого математического аппарата, строгими доказательствами предложенных утверждений, результатами вычислительного эксперимента.
Практическая значимость результатов исследования
-
Разработанные методы проектирования реляционных отношений можно применять для автоматизированного построения новой и проверки существующей схемы базы данных на оптимальность по скорости доступа к данным и компактности хранения данных.
-
Разработанные методы построения и эквивалентного преобразования параллельных алгоритмов можно применять в целях упрощения и ускорения
процессов разработки, анализа и сравнения параллельных программ и принятия решения о необходимости преобразования исходной программы.
-
Разработанное программное обеспечение можно применять для получения заключения о возможности распараллеливания вычислительной задачи, получения модели параллельной программы, проведения дальнейших исследований в области параллельных вычислений с применением информационных графов, строить реляционные схемы, удовлетворяющие нормальным формам, находить эвристические зависимости на основе большого объема эмпирических данных.
-
Разработанные методы преобразования разреженных матриц можно применять в любой прикладной задаче по преобразованию сложной многосвязной системы, представимой в виде графа.
-
Разработанный метод построения дерева решений может быть применен как в задачах принятия решений, так и в задачах установления связи между статистическими выборками, значения которых могут быть одновременно как непрерывными, так и дискретными и состоящими всего из нескольких значений, что делает применение классических методов статистического корреляционного анализа невозможным.
Реализация результатов исследования
Теоретические и практические результаты диссертационной работы используются в программных средствах ОАО «РУСАЛ-Братск» (Братский алюминиевый завод), ОАО «Концерн «Океанприбор» и ГУ «Санкт-Петербургский центр по гидрометеорологии и мониторингу окружающей среды с региональными функциями», что подтверждено актами о применении. Результаты работы используются в учебном процессе кафедры дискретной математики и защиты информации ФГБОУ ВПО «Братский государственный университет» при преподавании курсов «Теория алгоритмов», «Параллельное программирование», «Численные методы», матричные методы принятия решений и разработанное программное применяются при формализованном подходе к формированию заявки на контрольные цифры приема в ФГБОУ ВПО «Братский государственный университет».
Материалы работы использованы в Федеральной целевой программе
«Научные и научно-педагогические кадры инновационной России» на 2009– 2013 годы в рамках проекта «Создание высокопроизводительных вычислительных технологий для интеллектуальных систем оперативной обработки и визуализации гидроакустической информации» (шифр «2012-1.1-12-000-2010-011» соглашение №14.В37.21.0589) и в проекте 4.3 этапа 2013 года программы фундаментальных исследований Президиума РАН №14 «Проблемы создания национальной научной распределенной информационно-вычислительной среды на
основе GRID технологий, облачных вычислений и современных телекоммуникационных сетей».
Апробация результатов исследования
Результаты работы обсуждались на конференциях: научно-технические конференции в г.Братске «Естественные и инженерные науки – развитию регионов» (БрГУ, 2004, 2005, 2009гг.), всероссийская научная конференция молодых ученых в г.Новосибирске (НГТУ, 2004г.), конференция «Математическое моделирование, численные методы и комплексы программы» в г.Санкт-Петербург (ФГБОУ ВПО «СПбГАСУ», 2004, 2009, 2011гг.), международной конференции «Наука в информационном пространстве» в г.Днепропетровск (2009г.), Научно-технических семинарах ФГБОУ ВПО «НовГУ» (2011г.), ФГБУН СПИИРАН, ФГБОУ ВПО «ИТМО», ФГБОУ ВПО «СПбГЭТУ» (2012), II национальный суперкомпьютерный форум «НСКФ» в г.Переславль-Залесский (2013г) и др.
Публикации
Основное содержание диссертационной работы опубликовано в 31 печатных работах общим объемом 13 п.л. (личный вклад автора – 12 п.л.), из них 16 статей в изданиях из перечня ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК РФ (из них 2 в соавторстве).
Структура и объем
Диссертация состоит из введения, 5 глав с выводами по каждой главе, заключения, 20 приложений и списка литературы, содержащего 171 наименование. Общий объем работы составляет 359 страниц машинописного текста, включая 114 рисунков, 21 таблицу.
Матричные алгоритмы на графах
К наиболее существенным научным результатам относятся следующие:
1. Разработан метод приведения разреженной матрицы к треугольному виду, отличающийся сохранением первоначальных значений элементов, что является необходимым требованием при задачах оптимизации параллельных алгоритмов.
2. Разработаны методы построения и оптимизации информационного графа параллельного алгоритма по ширине. Методы состоят из двух частей, ко торые могут применяться независимо друг от друга в зависимости от результа тов исследования на промежуточном этапе метаданных. Методы основаны на матрице смежности, списках смежности и списках следования и отличаются.
3. Получены и обоснованы граничные условия числа задействованных в параллельных вычислениях процессоров, по которым можно принимать решение о дальнейшей разработке или эквивалентном преобразовании параллельной программы.
4. Разработаны методы оптимизации параллельного алгоритма по времени выполнения, позволяющие осуществлять равномерную загрузку процессоров, сокращать время решения поставленной задачи и уменьшать ширину информационного графа, соответствующего данному алгоритму. Методы основаны на матрицах, списках смежности и списках следования.
5. Предложено представление функциональных зависимостей реляционных схем в матричном виде и получены матричные аналоги свойств функциональных зависимостей. В отличии от известных ранее способов представления и обработки функциональных зависимостей предложенные матричные свойства позволяют дополнить современные СУБД отсутствующей в них функцией проверки реализуемых физических баз данных на корректность структуры и отсутствие аномалии избыточности.
6. Разработан метод построения реляционной схемы на основе атрибутов предметной области и декларированных функциональных зависимостей. Все получаемые схемы удовлетворяют нормальной форме Бойса-Кодда и имеют минимум аномалии избыточности.
7. Разработаны матричные методы построения замыкания функциональных зависимостей и нахождения первичного ключа реляционного отношения на основе функциональных зависимостей.
8. Разработан матричный метод построения дерева решений, который позволяет получать более широкую совокупность правил по сравнению с эвристическими методами. Совокупность правил может быть отрегулирована с помощью выведенных формул, позволяющих также оценить вероятность срабатывания правила. Разработанный матричный метод предпочтительнее эвристических методов за счет более низкой трудоемкости, компактной формы хранения данных и полноты получаемой совокупности правил.
9. Разработан программный комплекс для тестирования полученных методов и проведения дальнейших исследований в области параллельных вычислений, реляционных баз данных и теории принятия решений.
Обоснованность и достоверность полученных результатов обеспечивается корректностью применяемого математического аппарата, строгими доказательствами предложенных утверждений, результатами вычислительного эксперимента.
Практическая значимость результатов исследования
1. Разработанные методы проектирования реляционных отношений можно применять для автоматизированного построения новой и проверки существующей схемы базы данных на оптимальность по скорости доступа к данным и компактности хранения данных.
2. Разработанные методы построения и эквивалентного преобразования параллельных алгоритмов можно применять в целях упрощения и ускорения процессов разработки, анализа и сравнения параллельных программ и принятия решения о необходимости преобразования исходной программы. 3. Разработанное программное обеспечение можно применять для получения заключения о возможности распараллеливания вычислительной задачи, получения модели параллельной программы, проведения дальнейших исследований в области параллельных вычислений с применением информационных графов, строить реляционные схемы, удовлетворяющие нормальным формам, находить эвристические зависимости на основе большого объема эмпирических данных.
4. Разработанные методы преобразования разреженных матриц можно применять в любой прикладной задаче по преобразованию сложной многосвязной системы, представимой в виде графа.
5. Разработанный метод построения дерева решений может быть применен как в задачах принятия решений, так и в задачах установления связи между статистическими выборками, значения которых могут быть одновременно как непрерывными, так и дискретными и состоящими всего из нескольких значений, что делает применение классических методов статистического корреляционного анализа невозможным.
Реализация результатов исследования
Теоретические и практические результаты диссертационной работы используются в программных средствах ОАО «РУСАЛ-Братск» (Братский алюминиевый завод), ОАО «Концерн «Океанприбор» и ГУ «Санкт-Петербургский центр по гидрометеорологии и мониторингу окружающей среды с региональными функциями», что подтверждено актами о применении. Результаты работы используются в учебном процессе кафедры дискретной математики и защиты информации ФГБОУ ВПО «Братский государственный университет» при преподавании курсов «Теория алгоритмов», «Параллельное программирование», «Численные методы», матричные методы принятия решений и разработанное программное применяются при формализованном подходе к формированию заявки на контрольные цифры приема в ФГБОУ ВПО «Братский государственный университет».
Приведение разреженной матрицы к односторонне окаймляющей блочной диагональной форме
При построении математических моделей управления технологическими процессами на производстве часто приходится решать системы линейных уравнений, в результате которых должны быть получены не фиксированные значения переменных системы, а зависимости одних переменных от других. Матрица такой системы линейных уравнений соответствует весовым показателям не технологических параметров, а связям между ними. Если изменить в ходе решения системы одни коэффициенты матрицы системы на другие, то в результате будут изменены исходные связи между технологическими параметрами, что приведет к нарушению всего технологического процесса.
Например, в результате построения математической модели процесса получения алюминия электролизом криолит-глиноземных расплавов получается система линейных уравнений, представленная в приложении L. Матрица системы имеет размер 43 х 56 и, как показывает анализ матрицы, она содержит 36 строк, в каждой из которых всего по два ненулевых элемента.
Основная цель построенной матричной модели - получить на ее основе зависимостей напряжения питания электролизера и количества выливаемого алюминия из электролизной ванны от остальных параметров процесса получения алюминия.
Получаемую систему линейных уравнений можно решить наиболее эффективно, если ее матрицу привести к блочной диагональной (BDF) или односторонне окаймляющей блочной диагональной форме SBBDF.
Основное условие при решении системы - сохранность первоначальных значений ее элементов. Это связано с тем, что ненулевые значения матрицы характеризуют взаимосвязи между элементами системы. В матрице присутствуют только константы 1 и -1, обозначающие наличие зависимостей между параметрами и их направления, и передаточные функции Wi. Изменение в результате преобразования матрицы этих значений приведет к новой системе не эквивалентной исходной. Информация об истинных связях между параметрами системы будет утеряна, а новые связи не будут соответствовать действительности. Поэтому сохранность первоначальных значений элементов матрицы является важным условием при решении системы.
В результате преобразования матрицы получаются зависимости: - напряжения питания электролизера: U = Х2 + W31 X13 + W4 X14 + W10 X16 +W38 X77 - количества выливаемого алюминия из электролизной ванны: Q = W14 X4 + W17 X5 + W20 X6 + W23 X7 +W25 X8 +W1 X14 + W6 X15 +W11 X16 +W34 X76. Существует несколько методов приведения разреженных матриц к BDF с сохранением первоначальных значений их элементов. Наиболее известные из них описаны Р.Тьюарсоном [114] (1971г.) для квадратной разреженной матрицы, Х.Д.Икрамовым [54-55] (1987г.) для квадратных симметричных разреженных матриц, Эстербю О., Златевым 3. [128] (1987г.) для квадратных симметричных положительно определенных разреженных матриц.
В математической модели процесса получения алюминия матрица не является симметричной, положительно определенной и квадратной. Ни один из этих методов не подходит для приведения матрицы в модели процесса получения алюминия к BDF. Наиболее близок метод, предложенный Р.Тьюарсоном [114] (1971г.) для квадратных матриц, который можно модифицировать для матриц прямоугольной формы.
Эта задача показывает необходимость разработки методов для преобразования разреженных матриц произвольной структуры к специальному виду с обязательным сохранением первоначальных значений ее элементов. Задача 2. Построение параллельного алгоритма на основе его последовательного аналога
Одним из способов разработки параллельных алгоритмов является их получение на основе их последовательных аналогов, которые являются уже хорошо отработанными и проверенными на практике. Алгоритм в свою очередь представляет сложную многосвязную распределенную системы, представимую с помощью графов. Часто для исследований свойств алгоритма применяют информационный граф.
Информационному графу, как и любому другому, можно поставить в соответствие матрицы смежности, инцидентности и другие. В большинстве случаев матрица информационного графа является разреженной.
Чтобы преобразовать последовательный алгоритм к параллельному алгоритму с применением информационного графа необходимо привести его к одной из возможных и приемлемых для условий решаемой задачи параллельных форм. При этом структура графа не должна измениться, т.к. в ней заложена информация об информационных взаимосвязях операций алгоритма.
В результате появляется, как и в предыдущей задаче, проблема преобразования разреженной матрицы информационного графа с обязательным сохранением первоначальных значений ее элементов. Можно привести еще множество задач, в которых возникают проблемы приведения матриц к эквивалентным матрицам с сохранением первоначальных значений их элементов.
Матричное преобразование алгоритмов и их оптимизация по числу процессоров
Условия неограниченного параллелизма - это идеальные условия, которые на практике не существуют. В связи с этим хотелось бы на основе полученных алгоритмов найти новые, которые были бы приближены к реальным условиям.
Как было сказано выше, эффективность параллельного алгоритма зависит от многих параметров. Одним из таких параметров является равномерная загрузка процессоров вычислительной системы. При этом важно с одной стороны сохранив высоту параллельного алгоритма минимизировать его ширину. Эту проблему можно решить с помощью матричного метода, представленного в п.3.3.1. Другим важным параметром является время выполнения процессов. Если предполагать, что время выполнения всех процессов, отраженных в информационном графе в виде отдельных вершин, одинаково, тогда ориентированный ациклический информационный граф является наиболее подходящим инструментом для построения оптимального по высоте и ширине параллельного алгоритма. Но на практике такие условия -крайняя редкость. Следовательно, из-за неравномерности выполнения отдельных процессов, часть процессоров будет простаивать в ожидании результатов от своих предшественников. Поэтому, сама собой напрашивается замена ориентированного ациклического информационного графа его взвешенным аналогом, в котором в качестве весов будет выступать время выполнения процессов.
Один из таких подходов представлен в [23]: для заданных поведения программы и директивного срока ее выполнения выбирается минимально достаточное число процессов в вычислительной системе и расписание выполнения программы. Модель поведения программы задается историей выполнения программы и набором ограничений. На первом шаге метода строится вычислительная система с максимально возможным числом процессоров - каждый процесс программы назначается на свой процессор. Поскольку архитектура полносвязная, то вместо процессоров рассматриваются ассоциации процессов - упорядоченное множество рабочих интервалов процессов, назначенных на один и тот же процессор. На каждом последующем шаге происходит просмотр всех возможных пар ассоциаций, среди них выбирается наилучшая пара для объединения, проверяется выполнение временных ограничений и выполняется коррекция числа ассоциаций. На некотором шаге будет невозможно произвести объединение какой-либо пары ассоциаций без нарушения директивного срока или останется лишь одна ассоциация. На этом метод заканчивает свою работу.
Недостатком данного подхода является сильная зависимость качества получаемых решений от набора и порядка использования пошаговых критериев оптимизации. Но, как показали исследования, эти недостатки возможно устранить или свести к минимуму.
Можно ли сократить ширину алгоритма путем уменьшения времени простоев процессоров за счет объединения мелких (по времени работы) операций в более крупные?
Оптимизировать данный информационный граф с помощью метода, описанного в п.3.3.1 невозможно. Поэтому, для ответа на эти вопросы построим сначала временную диаграмму (рисунок 3.8), где t - время выполнения каждого процесса, п - номер процессора, задействованного в вычислении. п 3-2-1 t 1 2 3 4 5 6 Рисунок 3.8 - Временная диаграмма работы процессоров. Из рисунка 3.8 видно, что: - суммарное время работы алгоритма равно 6 ед.; - первый процессор простаивает дважды, и суммарное время простаивания составляет 3 ед., второй процессор простаивает единожды 1 ед., третий - дважды и суммарное время простаивания равно 2 ед. Таким образом, оптимизация процесса только по числу процессоров не является конечным результатом улучшения качества параллельного алгоритма. Также, из рисунка 3.8 видно, что два процесса, вычисляемы на одном процессоре (А и В) можно объединить в одни, тем самым, произведя укрупнение схемы вычислений (рисунке 3.9).
Построение реляционной модели на основе орграфа функциональных зависимостей
Нередко проектирование тех или иных моделей баз данных усложняется появлением аномалий - проблем, связанных с избыточностью, доступностью информации и т.п., проблем, мешающих нормальной работе базы данных.
Изучение и устранение аномалий является самым важным аспектом даталогического этапа проектирования базы данных в целом, которое позволяет значительным образом усовершенствовать ранее созданную модель. Реляционные модели данных чаще других подвержены аномалиям. Разновидности аномалий, с которыми приходится иметь дело наиболее часто, перечислены ниже. 1. Аномалия избыточности - одинаковые элементы информации повторяются многократно в нескольких кортежах. 2. Аномалия изменения - один и тот же фрагмент данных изменяется в одном кортеже, но остается нетронутым в другом. 3. Аномалия удаления - удаление какого-то фрагмента приводит к потере целого кортежа.
Пример 4.1. Рассмотрим отношение Заказы ( заказа, заказчика, имя заказчика, улица, город, штат, индекс, фильма, название фильма, количество, срок) [34]. Ключом этого отношения является совокупность атрибутов: { заказа, фильма!. Очевидно, что по адресу с одним и тем же индексом может проживать множество заказчиков, а т.к. индекс однозначно определяет город и штат, то для этого множества заказчиков будет повторяться не только значение индекса, но и значения атрибутов «город» и «штат». Таким образом, данное отношение содержит аномалию избыточности.
Устранить полностью аномалию избыточности часто не представляется возможным, но свести к минимуму ее можно. Например, данное отношение можно разбить на два отношения: Заказы К заказа, заказчика, имя заказчика, улица, индекс, фильма, название фильма, количество, срок) и Заказы2 (город, штат, индекс), тем самым уменьшив аномалию избыточности.
Этот пример хорошо иллюстрирует, как анализ зависимостей одних атрибутов от других позволяет улучшить качество проектируемой схемы отношения. Анализ схемы на наличие аномалий избыточности проводится с помощью функциональных зависимостей. К сожалению, этот процесс -оптимизации схемы отношения - на сегодняшний день является единственным неавтоматизированным этапом в проектировании баз данных. Большинство проектировщиков баз данных этот этап просто пропускают, другие тратят достаточно много времени на исследование функциональных зависимостей, больше полагаясь на свой опыт и интуицию, чем на математический аппарат. В то же время существуют инструментарий в области математики, который позволяет не только формализовать этот этап, но и выстроить алгоритм, с одной стороны, обеспечивающий нахождение оптимального решения задачи сведения к минимуму аномалии избыточности, с другой стороны, позволяющий переложить решение этой задачи на «плечи» компьютера, тем самым сделав процесс создания базы данных автоматизированным на всех этапах проектирования: от построения ER-модели (например, в ERWin) до создания физической базы данных на SQL-сервере.
Проблеме формализованного представления функциональных зависимостей посвящен следующий параграф. Функциональные зависимости реляционных отношений 4.2.1. Представление функциональных зависимостей с помощью графов
Независимо от вида модели одними из важных характеристик являются зависимости одних атрибутов от других. В реляционной теории существует понятие функциональной зависимости.
Определение 4.1. Функциональная зависимость для отношения R - это утверждение следующего вида: «Если два кортежа отношения R совпадают в 141 атрибутах д,д,..., д (т.е. кортежи обладают одинаковыми значениями компонентов для каждого из названных атрибутов), то они должны совпадать и в другом атрибуте, В». Формально такая FD записывается как д, А,,..., д - в и свидетельствует, что « Д, Д,..., Д функционально обусловливают В».
Теория графов достаточно хорошо развита, однако прямое ее применение для представления данных до сих пор встречало затруднения, вызванные следующими обстоятельствами: 1) связи в моделях представления данных относительно просты, матрицы смежности получаются разреженными, что снижает ценность их использования; 2) в графах отражается чаще всего один тип связи (например, 1:1); 3) при постановке задачи представления (моделирования) данных, в отличие от теории управления и математики, в которой широко используются начальные предположения, велик объем неформальной составляющей. В настоящее время разработано достаточно много алгоритмов, позволяющих при работе с разреженными матрицами, экономить не только память, но и расчетное время. Поэтому первое затруднение становится скорее преимуществом применения теории графов. Второе затруднение отсутствует в применении теории графов для отображения функциональных зависимостей, которые лежат в основе данных исследований. Третье затруднение, к сожалению, остается, т.к. при наличии двух одинаковых с математической точки зрения решений, они могут нести совсем разный информационный смысл, и выбор в подобных ситуациях будет всегда оставаться за человеком. Таким образом, для отображения функциональных зависимостей и проведения их анализа теория графов представляет наиболее полный инструментарий.
