WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     || 2 |

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

-- [ Страница 1 ] --

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«Южно-Уральский государственный университет»

(национальный исследовательский университет)

На правах рукописи

Голодов Валентин Александрович

Интервальный подход к регуляризации неточно заданных систем линейных уравнений 05.13.17 – Теоретические основы информатики Диссертация на соискание ученой степени кандидата физико - математических наук

Научный руководитель доктор физико - математических наук, профессор А. В. Панюков Челябинск Содержание Введение 1 Интервальная неопределённость в математическом моделировании 1.1 Источники интервальной неопределенности............ 1.2 Некорректные задачи........................ 1.3 Интервальные системы линейных алгебраических уравнений.. 1.4 Линейная задача о допусках для ИСЛАУ............. 1.4.1 Исследование пустоты допускового множества...... 1.4.2 Коррекция правой части системы.............. 1.5 Примеры математических моделей приводящих к решению интервальных систем линейных алгебраических уравнений.... 1.5.1 Линейное уравнение межотраслевого баланса....... 1.5.2 Определение компонентов бинарных смесей методом Фирордта............................. 1.5.3 Доказательные вычисления и интервалы......... 1.6 Основные выводы........................... 2 Псевдорешение интервальной системы. Существование. Алгоритм поиска 2.1 Новизна предлагаемого подхода.................. 2.2 Предпосылки рассматриваемого подхода.............. 2.3 Понятие псевдорешения ИСЛАУ.................. 2.4 Вопрос единственности псевдорешения.............. 2.5 Наилучшее возможное псевдорешение............... 2.5.1 Поиск наилучшего псевдорешения............. 2.6 Выводы................................ 3 Программный комплекс вычисления псевдорешения интервальной системы 3.1 Параллельный алгоритм нахождения псевдорешения интервальной системы........................... 3.2 Точные вычисления в существующих программных пакетах.. 3.3 Описание разработанного программного комплекса поддержки дробно-рациональных вычислений................. 3.3.1 Особенности гетерогенных систем с GPU......... 3.3.2 Дробно-рациональные вычисления в гетерогенных системах............................. 3.3.3 Параллельные алгоритмы для базовых арифметических операций. Реализация на GPU nVidia.......... R 3.4 Схема работы с программным комплексом для вычисления псевдорешения............................ 3.4.1 Входные данные....................... 3.4.2 Выходные данные....................... 3.4.3 Запуск приложения и параметры.............. 3.5 Выводы................................ 4 Численные эксперименты 4.1 Производительность программного обеспечения для точных вычислений в гетерогенных средах с графическими ускорителями 4.1.1 Производительность сравнения............... 4.1.2 Производительность сложения (вычитания)........ 4.1.3 Производительность умножения.............. 4.2 Примеры решения ИСЛАУ небольшой размерности....... 4.3 Линейное уравнение межотраслевого экономического баланса. 4.4 Определение компонентов бинарных и тернарных смесей методом Фирордта............................. 4.5 Результаты нагрузочного тестирования.............. 4.6 Выводы................................ Заключение Основные обозначения Список рисунков Список таблиц Приложение А Свидетельство о государственной регистрации программы для ЭВМ. Библиотека классов «Exact Computation 2.0» Приложение Б Свидетельство о государственной регистрации программы для ЭВМ «ExactLinPSolutor 1.0» Приложение В Свидетельство о государственной регистрации программы для ЭВМ «ExactISLAYPSolutor 1.0» Приложение Г Фрагмент выходного файла для эксперимента с интервальной моделью Леонтьева Приложение Д Пример выходного файла для случая анализа смеси Система линейных алгебраических уравнений используется при математическом моделировании объектов различной природы. В частности, физических, химических и социально-экономических процессов, процессов управления. В ходе качественного анализа и/или использования математических моделей необходимо решать различные системы линейных алгебраических уравнений.

В данной работе предлагается считать моделью неточно заданной системы линейных алгебраических уравнений интервальную систему линейных алгебраических уравнений, т.е. СЛАУ с интервальными коэффициентами. Таким образом, интервальная неопределённость [, + ] является следствием природы самой математической модели. В том случае, когда система линейных алгебраических уравнений возникает как результат промежуточных вычислений, например, в ходе качественного и/или количественного исследования математических моделей, интервальная неопределённость является следствием аналитических оценок приближённых величин, выступающих в роли коэффициентов.



На практике необходимо решать плохо обусловленные и даже вырожденные системы линейных алгебраических уравнений, неустойчивых к возмущениям и погрешностям входных данных. Для решения сильно вырожденных или несовместных СЛАУ применяют различные методы решения некорректных задач, например, псевдорешение по М.М. Лаврентьеву, регуляризация А.Н. Тихонова, матричной коррекции (И.И. Еремин, В.А. Горелик, В.И. Ерохин и др. [18–20]).

В данной работе предлагается подход к регуляризации исходной СЛАУ за счет её погружения в интервальную СЛАУ, данный подход назван интервальной регуляризацией. Классическим примером плохо обусловленной матрицы является матрица Гильберта.

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

чисел; (2) распространение свойства непрерывной зависимости от параметров решения системы, полученной после «эквивалентных» преобразований, на исходную систему. Это присутствует в популярных коммерческих пакетах «MatLab», «MathCad» и т.п., а также свободно распространяемом пакете «SciLab». Использование в параллельных вычислениях разного числа процессоров во многих случаях дает существенно различающиеся результаты, демонстрируя необходимость применения надежных, а в некоторых случаях доказательных вычислений (см. работы К.И. Бабенко [1–3], П.С. Панков [30], А.Н. Малышев [28] С.К. Годунов [9, 11, 12], Э.А. Бибердорф и Н.И. Попова [4, 5]).

Несмотря на богатую и длительную историю, результаты упомянутых исследований сравнительно недавно вышли за рамки учебников, монографий и решения конкретных прикладных задач, результатом стал «GALA–2.0 — пакет для решения задач линейной алгебры с гарантированной оценкой точности» [6]. Все алгоритмы приведённые в работах выше, а также многие упомянутые в работе У. Кулиш, Д. Рац, Р. Хаммер, М. Хокс [21] направлены на то, чтобы по известной погрешности в исходных данных в рамках предполагаемой точности проводимых вычислений дать оценки на погрешность результата и, соответственно, гарантированные оценки точности предлагаемого приближённого решения.

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

Иной подход, весьма доступно изложенный, например, в работе М.М. Максимова применительно к разрешимости интегральных уравнений [27], диссертационной работе В.А. Шишкина, а также в работах А.В. Панюкова и М.И. Германено [31], состоит в применении рациональных вычислений и вычислений с произвольной точностью. Как подчеркивается, например, в работах В.П. Максимова [27] многие выкладки при данном подходе существенно зависят от точности, предоставляемой рациональным типом данных, и не могут быть выполнены стандартными вычислениями с двойной точностью. Получение гарантированного результата здесь требует вычислительных и программных средств, точно оперирующих с рациональными числами. «...

По этой причине реализация описанной схемы исследований требует значительных усилий и соответствующей квалификации. Как замечено в (Х.Д. Икрамов Численные методы линейной алгебры.), существует «контраст между простотой описания метода и сложностями грамотной его программной реализации»...» [27].

В данной работе предлагается новый теоретический подход к решению систем неточно заданных систем, как систем с интервальной неопределённостью исходных данных, позволяющий решать плохо обусловленные системы, неустойчивые к погрешностям во входных данных. Подход основан на погружении СЛАУ в интервальную СЛАУ, учитывающую существующие интервальные неопределенности в данных еще на этапе постановки задачи, и поиска решения из допускового множества решений интервальной СЛАУ.

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

Поиск решения СЛАУ с интервальной неопределённостью как точечного решения интервальной СЛАУ, принадлежащего допусковому множеству решений, обусловлен его структурой, обеспечивающей максимальную устойчивость среди всех возможных множеств решений интервальной СЛАУ. В рамках предлагаемого подхода требуется точное решение соответствующей задачи линейного программирования большой размерности.

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

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

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

Распространение данных схем на программное обеспечение (software) оказывается нерациональным.

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

Задача решения интервальной системы в данной работе сводится к решению соответствующей задачи линейного программирования. Эффективное решение задачи линейного программирования за счет параллельных вычислений является хорошо изученным вопросом (см. работы V.Y. Pan и J.H. Reif [58], Ju. Hall [53], Ю.Г. Евтушенко, А.И. Голиков, В.А. Гаранжа [38], А.В. Панюков и В.В. Горбик [35, 61, 62]).

Степень разработанности темы исследования. На сегодняшний день разработаны различные теоретические и практические подходы для гарантированного решения систем линейных алгебраических уравнений с условиях интервальной неопределенности исходных данных: П.С. Панков [30], А.Н. Малышев [28], С.К. Годунов [9, 11, 12], Э.А. Бибердорф и Н.И. Попова [4, 5], У. Кулиш, Д. Рац, Р. Хаммер, М. Хокс [21].

Для решения несовместных и плохо обусловленных систем были предложены различные подходы, например, псевдорешение СЛАУ М.М. Лаврентьев, регуляризация А.Н. Тихонова.

Интервальные системы линейных алгебраических уравнений рассматривались в работах J. Rohn, С.П. Шарого, И.А. Шарой [48, 64–66] и др., подробный обзор современного состояния исследований в данной области можно найти в [49]. Предложены методики для грубого исследования разрешимости системы [46, 47], а так же полного исследования разрешимости и коррекции исходных данных системы в случае ее несовместности путем оптимизации негладких выпуклых функционалов специального вида [48].

Целями диссертационной работы являются:

1) предложение нового подхода к регуляризации СЛАУ за счет погружения в ИСЛАУ и перехода к поиску точки из допускового множества решений ИСЛАУ, 2) развитие концепции псевдорешения интервальной системы линейных алгебраических уравнений и ее применение в математическом моделировании, 3) создание масштабируемого алгоритма для вычисления псевдорешения интервальной системы линейных алгебраических уравнений, 4) применение технологии GPGPU для развития программного обеспечения безошибочных дробно-рациональных вычислений для распределённых параллельных вычислительных систем с графическими процессорами (гетерогенных вычислительных систем), 5) применение разработанного параллельного программного обеспечения для вычисления псевдорешения интервальной системы.

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

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

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

3) Применение методов программирования в многопроцессорных и распределённых средах для реализации алгоритма нахождения псевдорешения.

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

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

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

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

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

Научная новизна заключается: (1) в создании подхода к регуляризации неточно заданных систем за счет погружения в интервальную СЛАУ, в создании нового подхода к коррекции правой части системы в задаче о допусках для интервальной системы линейных алгебраических уравнений, учет интервальной неопределенности в исходных данных повышает адекватность математического моделирования, (2) в разработке и реализации параллельного программного обеспечения для эффективного решения поставленной задачи в распределённых вычислительных системах с графическими ускорителями, (3) в разработке и реализация программного комплекса для безошибочных дробно-рациональных вычислений в гетерогенных вычислительных системах, реализации программного комплекса для численного решения задач математического моделирования.

Теоретическая значимость. Предлагаемый подход сводит задачу решения неточно заданной системы линейных уравнений к задаче поиска точки из допускового множества решений интервальной системы, подобная техника применяется впервые, метод решения нахождения точки из допускового множества ИСЛАУ продолжает ряд исследований М.М. Лаврентьева, Н.А. Хлебалина, J. Rohn, O. Beaumont, B. Philippe позволяет, вместе с определением совместности задачи о допусках для интервальной системы, решать задачу коррекции правой части системы. Предлагаемый метод решения продолжает работы по применению техники линейного программирования в задачах интервального анализа. Коррекция задачи о допусках осуществляется за полиномиальное время. Расширение допустимых интервалов правой части системы позволяет предложить решение в том случае, когда допусковое множество интервальной системы пусто.

Комплекс программ для безошибочных дробно-рациональных вычислений продолжает и существенно развивает работы А.Н. Румянцева [27], библиотеки GMP [52] на техническую базу современных кластерных решений с графическими ускорителями. Разработаны параллельные масштабируемые алгоритмы для эффективного использования GPGPU ускорителей.

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

Работа выполнена в рамках соглашения № 14.В37.21.0395 с Министерством образования и науки Российской Федерации от 06 августа 2012 года. Правообладателем разработанного в рамках данной модели программных комплексов [13–15]является ЮУрГУ.

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

Предложен новый подход к регуляризации СЛАУ за счет погружения в ИСЛАУ и перехода к поиску точки из допускового множества решений ИСЛАУ.

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

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

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

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

1. Третья научная конференция аспирантов и докторантов ЮУрГУ. (г. Челябинск, 2011).

2. Алгоритмический анализ неустойчивых задач. Международная конференция, посвященная памяти В. К. Иванова (г. Екатеринбург, 2011).

3. Четвертая научная конференция аспирантов и докторантов ЮУрГУ. (г. Челябинск, 2012).

4. 15th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Verified Numeric (г. Новосибирск, 2012).

5. Параллельные вычислительные технологии (ПаВТ’2012) (г. Новосибирск, 2012).

6. Параллельные вычисления и задачи управления (PACO’2012). Шестая международная конференция (г. Москва, 2012).

7. Информационные технологии и системы.(оз. Банное, респ. Башкортостан, 2013).

8. Пятая научная конференция аспирантов и докторантов ЮУргУ. (г. Челябинск,2013).

9. GPU Technology Conference-2013 (San Jose, California, 2013).

Публикации. По теме работы опубликовано 15 работ (6 статей, 2 постера, тезисов конференци – 4, 3 свидетельства о государственной регистрации программы для ЭВМ). В их числе 2 статьи из перечня ведущих российских рецензируемых изданий [33, 34], а также 1 статья в рецензируемом международном научном журнале [60].

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

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

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

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

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

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

На основе разработанных алгоритмов, а также методов для вычислений с применением безошибочных дробно-рациональных вычислений на графических ускорителях, адаптированных для распределенной гетерогенной среды, созданы программные комплексы «ISLinPSolutor 1.0» (для решения задачи линейного программирования) и «ISLAYSolutor 1.0» (для вычисления псевдорешения интервальной системы) с применением дробно-рационального типа данных. В данной главе приводятся вычислительные эксперименты с программным комплексом и описана схема работы с ним.

В заключении сформулированы основные результаты диссертации.

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

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

Представление чисел. При вычислениях, как правило, мы можем эффективно оперировать лишь объектами, которые имеют конечное описание (с конечной конструктивной сложностью). Например, Если для дробно-рациональных чисел возможны точные машинные представления [13, 16, 32, 52], то, например, вещественные числа точных аналогов в современных ЭВМ не имеют.

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

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

[0.66666, 0.66667], 2 [1.4142, 1.4143], [3.1415926, 3.1415927]. (1.2) Частным случаем ошибок представления являются ошибки машинного представления чисел в формате с плавающей точкой IEEE-754-1985/754Многие десятичные числа (к примеру, 0.1) не имеют точного конечного представления в формате с плавающей точкой одинарной и двойной точности [55], с которыми оперируют современные цифровые ЭВМ. При вводе подобных чисел в ЭВМ они неизбежно заменяются их некоторыми приближением.

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

Замечание. Ошибки округления можно ПОЛНОСТЬЮ исключить за счет точных вычислений.

Физические константы и результаты измерений. Чаще всего они известны неточно. К примеру, современные значения атомных весов некоторых химических элементов рекомендуется принимать интервальнозначными, например, для кислорода установлен интервал [15.99903; 159977] [68]. Для некоторых физических констант серьезные источники указывают стандартное (среднеквадратичное) отклонение, например, для гравитационной постоянной.

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

Допуски. Допуски (техн.) – допускаемые отклонения (т.е. интервал, прим. автора) числовой характеристики какого-либо параметра, например, размеров деталей машин и механизмов, физико-химические свойства материалов) от его номинального расчетного значения в соответствии с заданным классом точности [42].

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

Замечание. Интервалы в такой математической модели являются существенной ее частью, переход к точечной постановке приводит к искажению модели.

Неопределённость в физических законах и явлениях. Ограниченные по величине неопределённости и неоднозначности естественно возникают при математическом моделировании многих механических, физических, химических и пр. явлений. Интересным примером является сила сухого трения, играющая важнейшую роль в технике. Хорошо известно, что её максимальная величина пропорциональна силе, с которой прижаты соприкасающиеся поверхности. Но, вообще говоря, если движение одной поверхности по другой не наступило, то абсолютная величина силы трения покоя может принимать любое значение из интервала [0, ]. Аналогично коэффициент силы трения покоя может задаваться некоторым интервалом [43].

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

Неопределённости в технических, экономических и пр. системах.

Здесь имеются в виду величины, точные значения которых неизвестны или же могут изменяться. На протяжении нескольких столетий вплоть до второй половины XX века для их описания преимущественно использовалась теория вероятностей. Основоположником исследования ограниченных неопределённостей, для которых известны лишь границы изменения, является Л.В.Канторович, впервые сформулировавший идею их использования в работе [25] и наметивший основы математического аппарата для их обработки.

Показательный пример даёт понятие управления. Управление по смыслу подразумевает неоднозначность параметров объекта, которые можно выбирать из некоторого множества значений для достижения тех или иных желаемых целей управления. С другой стороны, даже цели управления и параметры функционирования объекта могут быть определены неточно. Эти соображения приводят к задаче так называемого робастного управления [49].

Замечание. Здесь интервальных характер входных данных и результата существенен, поэтому исследование имеет смысл проводить интервальными методами.

Внутриматематические потребности. Помимо прикладной (практической) значимости интервальных методов решения задач существует также ВНУТРИМАТЕМАТИЧЕСКИЕ ПОТРЕБНОСТИ, которые ощущаются в математике и естественно приводят к необходимости допущения в различных ситуациях интервальных величин и оперирования ими как с частным случаем числовых множеств. Таковыми являются, например, РАСШИРЕНИЕ ПОНЯТИЯ ПРЕДЕЛА,

ИНТЕРВАЛЬНОЕ ИНТЕГРИРОВАНИЕ, ТЕОРЕМЫ БРАУЭРА И МИРАНДЫ, ЗАДАЧИ ГЛО­

БАЛЬНОЙ ОПТИМИЗАЦИИ, ПРЕДСТАВЛЕНИЕ ОСТАТОЧНЫХ ЧЛЕНОВ ПРИБЛИЖЁННЫХ

ФОРМУЛ.

Замечание. Учет интервальной неопределённости позволяет провести численное исследование математической модели в виде доказательного эксперимента и повысить её качество.

Рассмотрим операторное уравнение =, – линейный оператор, действующий из гильбертова пространства в гильбертово пространство.

Французским математиком Ж. Адамаром были сформулированы следующие условия корректности постановки математических задач, примере записанного операторного уравнения. Задача решения операторного уравнения называется корректно поставленной (по Адамару), если выполнены следующие три условия:

решение существует ;

решение единственно;

Многочисленные обратные (в том числе и некорректные) задачи можно найти в различных областях физики. Так, астрофизик не может активно воздействовать на процессы, происходящие на далеких звездах и галактиках, ему приходится делать заключения о физических характеристиках весьма удаленных объектов по их косвенным проявлениям, доступным измерениям на Земле или вблизи Земли (на космических станциях). Прекрасные примеры некорректных задач можно найти в медицине, прежде всего, нужно отметить вычислительную (или компьютерную) томографию. Хорошо известны приложения некорректных задач в геофизике (на самом деле, легче и дешевле судить о том, что делается под поверхностью Земли, решая обратные задачи, чем заниматься бурением глубоких скважин), радиоастрономии, спектроскопии, ядерной физике и т.д., и т.п. [Спец. курс для аспирантов МГУ им.

М.В.Ломоносова, Москва, Лектор: профессор Ягола А.Г., 21 с.].

Хорошо известным примером некорректно поставленной задачи является интегральное уравнение Фредгольма 1-го рода, когда оператор имеет вид:

Ядро интегрального оператора (, ) - функция, непрерывная по совокупности аргументов [, ], [, ], а решение () - непрерывная на отрезке [, ] функция.

Приведем пример простой системы линейных алгебраических уравнений, для которой традиционные методы решения некорректных задач, такие Нормальное псевдорешение СЛАУ есть (, ) = (1/2, 1/2), однако в случае минимальных колебаний значений коэффициентов, например, > 0, система имеет единственное точное решение (, ) = (0, 1), и сходимости при 0 к нормальному псевдорешению нет.

Если же принять изначально интервальную постановку, то есть допустить колебание элемента 11 в закрытом интервале [1, 1 + ], то, вычислив псевдорешение интервальной СЛАУ (см. ниже определение [1.2.1]), мы получим точку (, ) = (0, 1), которая является точным решением для любой системы из семейства СЛАУ описываемых соотношениями (1.7), то есть является устойчивым к колебаниям коэффициентов в рамках заданных интервалов, тем самым можно устранить влияние возможных колебаний коэффициентов на результат.

В данной работе предлагается способ поиска решения подобных некорректных задач исходя из следующего определения Определение 1.2.1. Псевдорешениями интервальной системы линейных уравнений = назовем точки допускового множества системы = () с расширенной правой частью () =, +, где, – константные положительные векторы, определяющие характер расширения исходя из содержательного смысла задачи, 0 – параметр, отвечающий за величину расширения.

Различные возможные интервальные постановки для системы (1.6) и их псевдорешения интервальных систем приведены ниже.

[1.000; 1.000] * 1 + [1.000; 1.000] * 2 = [1.000; 1.000] [1.000, 1.000] * 1 + [0.990, 1.010] * 2 = [1.000, 1.000] [0.990, 1.010] * 1 + [0.990, 1.010] * 2 = [1.000, 1.000] [0.990, 1.010] * 1 + [0.990, 1.010] * 2 = [1.000, 1.000] Для решения некорректных задач, в частности, вырожденных и плохо обусловленных СЛАУ, разработан очень эффективный прием, называемый регуляризацией (по А.Н Тихонову). В его основе лежит учет дополнительной априорной информации о структуре решения (векторе априорной оценки 0 ), которая очень часто присутствует в практических случаях.

Задачу решения СЛАУ = можно заменить задачей отыскания минимума функционала Тихонова:

Здесь – малый положительный параметр регуляризации, который необходимо подобрать некоторым оптимальным способом. Можно показать, что задачу минимизации функционала Тихонова можно, в свою очередь, свести к решению другой СЛАУ:

Которая при 0 переходит в исходную плохо обусловленную систему, а при больших, будучи хорошо обусловленной, имеет решение 0.

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

Определение [1.2.1] также содержит параметр параметр, отвечающий за расширение интервалов в правой части системы. Значение параметра имеет смысл выбирать минимизируя расширения вектора правой части системы, то есть самого значения из определения [1.2.1].

1.3 Интервальные системы линейных алгебраических линейных алгебраических уравнений кратко, Как и в случае систем общего вида, следующие хорошо изученные множества решений интервальных линейных систем — объединённое множество решений допусковое множество решений управляемое множество решений это крайние точки обширного семейства 2(+1) всевозможных множеств AEрешений для интервальных линейных систем вида (1.9).

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

Введенo и исследовано Л.Т. Ащепковым и Д.В. Давыдовым, определяется как точка, обеспечивающая минимальное в некоторой норме расхождение правой части и образа по всем возможным точечным системам в рамках заданных интервалов.

Однако подход не учитывает положение интервалов в правой части системы относительно начала координат из-за чего «полоса разброса» [, +] такая что | | < для любых, может содержать большой «зазор».

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

1.4 Линейная задача о допусках для ИСЛАУ В этом пункте все внимание будет уделено линейной задаче о допусках и допусковому множеству решений интервальной линейной системы уравнений.

Задачей о допусках для ИСЛАУ (1.9) называется поиск решений принадлежащих допусковому множеству решений или в эквивалентной форме В представлении (1.15) квантор всеобщности эквивалентен теоретико-множественной операции пересечения. Поэтому из (1.16) следует, что допусковое множество наименеее чувствительно среди всех других множеств решений ИСЛАУ к изменению интервальной матрицы системы =, так как (1.16) не шире чем множество решений { R :

( )( = )} самой «лучшей» и самой робастной (устойчивой) матрицы. Хотя некоторые матрицы могут быть плохо обусловленными или вырожденными влияние «хороших» матриц обеспечивает ограниченность и оценки для. Следовательно мы можем использовать допусковое множество как инструмент регуляризации для неустойчивых и плохо обусловленных систем, когда необходимо сгладить эффект изменения решения задачи, вызванный неточностями или возмущениями в данных. Подобный подход назван интервальной регуляризацией.

В качестве областей приложений, в которых напрямую возникает допусковое множество решений ИСЛАУ можно привести задачи из математической экономики, технологического проектирования, автоматического управления, исследования асимптотической устойчивости динамических систем, естественно-научных исследований.

Допусковое множество решений системы линейных алгебраических уравнений обладает следующими свойствами.

Предложение 1.4.1. Допусковое множество решений интервальной линейной системы уравнений есть выпуклое многогранное множество в R.

Прямое описание допускового множества решений интервальной линейной системы уравнений, при котором выписываются все ограничивающие его гиперплоскости, является трудоёмким и практически бесполезным: его сложность растёт пропорционально · 2. Следовательно на практике прибегают к оцениванию множества вместо его полного описания, в частности нахождению (по-возможности, большего) бруса, который содержится в допусковом множестве решений данной интервальной линейной системы уравнений.

Специфической особенностью задачи о допусках является возможность для допускового множества решений оказаться пустым даже для простых интервальных данных, например, = для одномерного уравнения [1, 2] = [2, 3] или двумерной системы В подобных случаях будем линейная задача о допусках (ЛЗД) считается неразрешимой или несовместной, исследование разрешимости ЛЗД является отдельной подзадачей, которая автоматически решается предлагаемым в данной диссертационной работе подходом.

Один из подходов к полному описанию допускового множества решений дает следующая теорема.

Теорема 1.4.1 (И.А. Шарой о допусковом множестве решений). Точка R принадлежит допусковому множеству решений интервальной линейной системы = тогда и только тогда, когда она является решением системы двусторонних линейных неравенств где вектор-строки пробегают всевозможные вершины интервальных строк матрицы. Количество неравенств в этой системе не превосходит суммы числа вершин во всех интервальных векторах vert, = 1,...,, и, тем более, не превосходит · 2.

Решение систем линейных неравенств может быть выполнено различными способами, и один из наиболее популярных состоит в применении развитых методов линейного программирования. В стандартной форме задачи линейного программирования система линейных неравенств имеет специальный вид, требующий неотрицательности переменных. Очень удобен для представления допускового множества решений ИСЛАУ в таком виде результат полученный И.Роном в [64].

Теорема 1.4.2 (теорема Рона о допусковом множестве решений). Точка R принадлежит допусковому множеству решений интервальной линейной системы = тогда и только тогда, когда =, где -векторы и удовлетворяют системе линейных неравенств Ограниченность допускового множества определяется по следующему критерию:

Теорема 1.4.3 (критерий неограниченности допускового множества). Непустое допусковое множество решений (, ) интервальной линейной системы уравнений = неограничено тогда и только тогда, когда в матрице A существуют линейно зависимые точечные столбцы.

Ниже будет рассмотрен вопрос о методах исследования разрешимости и коррекции задачи в случае пустого.

1.4.1 Исследование пустоты допускового множества Для исследования пустоты допускового множества существует ряд методов основанных как на эмпирических предпосылках, так и позволяющих исследовать на пустоту в самом общем случае, см., например, [23].

Кратко упомянем эмпирические методики и чуть подробнее остановимся на методах работающих для всех ИСЛАУ:

Разрешимость некой «средней» системы (mid ) = mid. Контрпримером может служить простейшая ИСЛАУ из одного уравнения с = [1, 2], = [2, 6]. Здесь = [1, 2], но решение «средней системы» = 4.

Несколько более точный критерий дает следующая теорема.

Теорема 1.4.4. Пусть в системе уравнений = интервальная матрица и интервальный -вектор таковы, что для некоторого {1, 2,..., } выполнены следующие условия:

Тогда допусковое множество решений (, ) пусто, доказательство см., например, в [49].

В то же время, невыполнение условий Теоремы [1.4.4] не обязательно влечёт разрешимость линейной задачи о допусках. Например, второе условие из формулировки теоремы неверно для системы Однако, её допусковое множество решений всё-таки пусто. Информацию о разрешимости задачи (1.9) для всех ИСЛАУ дают методы приведенные ниже.

Метод «распознающего» функционала, предложенный С.П. Шарым [48], основан на максимизации функционала задаваемого следующим образом:

Предложение 1.4.2. Пусть даны интервальная -матрица и интервальный -вектор правой части, а выражением определяется функционал : R R. Тогда принадлежность (, ) равносильна (;, ) 0, т. е. допусковое множество решений интервальной линейной системы = есть множество уровня { R | (;, ) 0} функционала Tol.

Функционал обладает следующими свойствами:

Функционал () вогнутый.

Функционал () достигает конечного максимума на всём пространстве R.

В силу указанных свойств функционала, алгоритм выяснения разрешимости задачи о допусках состоит в следующем: пусть = Arg maxR (;, ), если 0, то (, ) =, т. е. линейная задача о допусках для интервальной линейной системы = совместна и точка лежит в допусковом множестве решений;

если > 0, то int (, ) =, и принадлежность точки допусковому множеству решений устойчива к малым возмущениям данных матрицы и правой части системы;

если < 0, то int (, ) =, т. е. линейная задача о допусках для интервальной линейной системы = несовместна.

Одним из первых и важных результатов сводящих задачу выяснения непустоты допускового множества к задаче линейного программирования является теорема [1.4.2] (Рона) о допусковом множестве. Следует подчеркнуть, что этот результат показал возможность решения постановок интервальных задач неинтервальными методами, причем, результат применим для любых ИСЛАУ.

Для исследования непустоты (, ) достаточно решить задачу совместности системы неравенств размерности 2, например, развитыми методами линейного программирования [22, 35].

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

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

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

Для ИСЛАУ c точечной абсолютно неособенной матрицей системы формальной решение единственно для любой интервальной правой части. Что касается интервальных систем уравнений с существенно интервальными матрицами, то для них единственность формальных решений является в настоящее время сравнительно малоисследованной. В рамках данной работы формальные решения не рассматривались.

Помимо информации о разрешимости или неразрешимости ИСЛАУ важной является возможность провести коррекцию правой части системы, т.е. скорректировать вектор «ожиданий».

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

Следовательно, где = ([1, 1],..., [1, 1]).

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

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

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

В [49] приводятся также соображения по коррекции матрицы системы, для обеспечения ее совместности при фиксированной правой части.

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

1.5.1 Линейное уравнение межотраслевого баланса В качестве примера возникновения множеств AE-решений интервальных линейных систем на практике приведем задачу математического моделирования в экономике. Рассмотрим линейное уравнение межотраслевого экономического баланса т. е. классическое уравнение Леонтьева [29], в котором R — вектор объёмов продукции по отраслям, R — вектор потребления в непроизводственной сфере по этим отраслям = ( ) R — матрица коэффициентов прямых производственных Разумно считать, что коэффициенты прямых производственных затрат заданы интервалами, т.е. и = ( ),, = 1,...,, аналогично, требование на вектор конечного потребления также естественно сформулировать в интервальной форме: как правило, любая ситуация, когда реальное потребление будет выдерживаться в пределах некоторого интервала IR является приемлемой.

В вещественном случае решение системы (1.24) относительно позволяет спрогнозировать объёмы производства по отраслям, необходимые для получения запланированного конечного потребления.

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

В интервальном случае вместо (1.24) получится уравнение Если же интервалы некоторых коэффициентов прямых производственных затрат представляют пределы их возможного управления, то задача определения объёмов производства, которые обеспечивают конечное потребление, приводит уже к рассмотрению множеств AE-решений интервальной линейной системы ( ) =, где – единичная матрица соответствующего размера. (1.26) 1.5.2 Определение компонентов бинарных смесей методом В спектрофотометрическом анализе смесей при наложении полос поглощения их компонентов используют метод Фирордта (МФ). Предварительно определяют молярные (или удельные) коэффициенты поглощения каждого компонента на аналитических длинах волн (АДВ). К сожалению, неизбежные погрешности при определении коэффициентов и при измерениях оптической плотности смеси ведут к тому, что точность метода невысока. Погрешности определения компонентов реальных смесей обычно не меньше 5-10% отн. и быстро растут при увеличении числа компонентов в смеси или соотношения их концентраций. Одна из причин неточности МФ - неаддитивность светопоглощения некоторых смесей. Это означает, что оптическая плотность смеси не равна сумме оптических плотностей компонентов, измеренных порознь в тех же условиях. Для смеси веществ и абсолютное отклонение от аддитивности () можно найти как разность + ( + ). Величина зависит от условий проведения анализа, прежде всего от длины волны, на которой измеряют оптическую плотность. Очевидно, при разработке методик спектрофотометрического анализа смесей методом Фирордта выбирать АДВ необходимо с учетом возможных отклонений от аддитивности. Обычно такие отклонения рассматривают как следствие случайных погрешностей фотометрических измерений. Однако значения могут быть и хорошо воспроизводимыми, статистически значимыми. Причинами появления воспроизводимых отклонений должны быть постоянно действующие факторы, например химическое или сольватационное взаимодействие компонентов, влияние примесей, некорректная градуировка измерительного прибора (нелинейная функция преобразования) и др. Какова бы ни была причина возникновения подобных отклонений, применение МФ к анализу соответствующих смесей должно вести к систематическим погрешностям.

Введем следующие допущения (ограничения модели):

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

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

3. Случайные погрешности фотометрических измерений и коэффициентов поглощения на обеих АДВ пренебрежимо малы.

Анализ смеси методом Фирордта ведут, решая систему линейных уравнений: { Здесь и далее 1, 2, 1, 2 – молярные коэффициенты поглощения веществ и, соответственно при и –молярные концентрации и в смеси, – толщина поглощающего слоя, 1 и 2 – поглощение смеси на сответствующих длинах волн. Выбор АДВ должен обеспечивать хорошую обусловленность матрицы коэффициентов 1, 2, 1, 2, определитель матрицы должен быть как можно большим. В противном случае, при линейной или близкой к ней корреляции коэффициентов, определитель будет близок к нулю, и решение системы может привести к заведомо неверным или даже абсурдным результатам [7].

Для более точного определения величин 1, 2, 1, 2, которое проводят решая одномерные уравнения · · =, соответствующие измерения проводят многократно. В том случае, когда проведение большого числа измерений затруднено или невозможно имеет смысл решать интервальную постановку задачи, когда величины 1, 2, 1, 2 представляют собой интервалы 1, 2, 1, 2 которые включают известную погрешность измерительного прибора. Также можно рассматривать систему с числом уравнений превосходящим число неизвестных, за счет рассмотрения большего числа (АДВ).

1.5.3 Доказательные вычисления и интервалы Доказательные вычисления — целенаправленные вычисления на ЭВМ, комбинируемые с аналитическими исследованиями, которые приводят к строгому установлению новых фактов и доказательству теорем [1].

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

Ведущим среди специализирующихся на интервальной тематике изданий, отражающих современное состояние исследований, является международный журнал «Reliable Computing».

Примеры доказательных вычислений в различных разделах математики:

В теории чисел – опровержение гипотезы Л. Эйлера предполагавшего, что уравнение: 5 + 5 + 5 + 5 = 5 не имеет решений в целых положительных числах. Решение найдено перебором на компьютере.

В теории графов был достигнут один из наиболее известных успехов – решение проблемы четырёх красок. Это была первая крупная математическая теорема, доказанная с помощью компьютера [40].

В математических задачах гидродинамики – доказана теорема о неустойчивости течения Пуазёйля при некоторых параметрах для спектральной задачи Орра-Зоммерфельда [3].

Задача исследования разрешимости линейного интегрального уравнения Фредгольма и вариационных задач для квадратичных функционалов (под руководством В.П. Максимова).

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

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

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

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

Это явление было замечено еще в конце 60-х годов прошлого века и заставило многих специалистов по численному анализу без достаточных оснований отвергнуть эту полезную и необходимую технологию вычислений. С другой стороны, применяемая изолированно, высокая точность вычислений бывает неоправданно расточительна. Однако ее объединение с интервальными методами позволяет получать конечные результаты с высокой и гарантированной точностью [21].

Заметим в заключение, что проверка правильности алгоритма в общепринятом смысле вовсе не гарантирует корректность вычисленных с его помощью результатов. Чтобы убедиться в этом, достаточно вспомнить общеизвестный пример решения СЛАУ = с матрицей Гильберта = решение такой системы дает вектор состоящий из целых чисел, тогда как численное решение в арифметике двойной точности IEEE-754-1985/754-2008, например, методом -разложения системы размерности = 7, уже не является целочисленным = (7.000000, 336.000000, 3780.000004, 16800.000013, 34650.000023, 33264.000019, а с ростом размерности системы порядок ошибки растет экспоненциально.

Этот простой пример демонстрирует разницу между математическим результатом и его численным аналогом, полученным на ЭВМ.

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

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

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

1) Погружение неточно заданной СЛАУ в интервальную СЛАУ и переход к поиску точки допускового множества ИСЛАУ позволяет получить устойчивое решение исходной СЛАУ, это обусловлено свойствами допускового множества.

2) Учет интервальной неопределённости повышает адекватность математических моделей.

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

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

Псевдорешение интервальной системы.

Существование. Алгоритм поиска 2.1 Новизна предлагаемого подхода В данной главе описывается подход к решению неточно заданных систем линейных уравнений за счет погружения в интервальную систему и переходу к поиску точки из допускового множества интервальной системы.

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

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

Применение проверенного временем и детально исследованного симплекс-метода, достаточно простого в реализации и доказавшего свою эффективность [53, 61], упрощает кодирование и оптимизацию программного обеспечения воплощающего данную разработку.

2.2 Предпосылки рассматриваемого подхода В соответствии с теоремой Рона [1.4.2] любая точка допускового множества может быть представлена в виде =, где, являются решением системы неравенств Во многих практических задачах система неравенств (2.1) оказывается плохо обусловленной или вообще несовместной. В этом случае по аналогии с псевдорешением СЛАУ М.М. Лаврентьева, работами [24,45] разумным представляется введение понятия псевдорешения интервальных систем линейных алгебраических уравнений.

Задачами данной диссертационной работы являются введение и исследование понятия псевдорешения интервальных систем линейных алгебраических уравнений и способы построения инструментальных программных средств поиска псевдорешения ИСЛАУ.

Определение 2.3.1 ( 1.2.1). Псевдорешениями интервальной системы линейных уравнений = назовем точки допускового множества системы = () с расширенной правой частью () =, +, где, – константные положительные векторы, определяющие характер расширения исходя из содержательного смысла задачи, 0 – параметр, отвечающий за величину расширения.

Существование объекта из определения [2.3.1] подтверждает следующая теорема Теорема 2.3.1. Для любой системы интервальных уравнений = при всех max{0, max /, min / } множество (, ()) =.

Доказательство. В соответствии с теоремой Рона условие (, ()) = эквивалентно совместности системы линейных неравенств Полагая в (2.2) – (2.4) + = = 0, получим что эквивалентно Таким образом, для всех max{0, max /, min / } имеет место включение 0 (, ()). Теорема доказана.

2.4 Вопрос единственности псевдорешения Рассмотрим вопрос единственности объекта из определения [2.3.1] объекта. Очевидно, что для случая совместной интервальной системы линейных уравнений, то есть, когда (, ) =, псевдорешение может быть не единственным. Приведем соответствующий пример.

Решением данной системы является множество точек изображенное на Рисунок [2.1].

Рисунок 2.1. Допусковое множество системы (2.5) Поскольку это множество непусто, то любая его точка является псевдорешением, соответствующим минимально возможному * = 0.

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

Покажем влияние выбора параметров,, отвечающих за вид расширения интервалов правой части системы, на получаемое точечное решение. В случае на Рисунок [2.2] = = 1, = 1,...,, то есть расширение всех интервалов одинаковое и равно [ * · 1, * · 1], = 1,...,.

Рисунок 2.2. Пример несовместной системы. Нормальное псевдорешение (М.М. Лаврентьев), псевдорешения интервальной системы 1, Рассмотрим другой способ выбора векторов параметров,, отвечающих за вид расширения интервалов в правой части, – пропорциональное расширение Рисунок [2.3], в этом случае = | |, = | |, = 1,...,.

2.5 Наилучшее возможное псевдорешение В случае несовместности системы (1.10), то есть, когда (, ) =, наибольший интерес представляет не всякое расширение правой части, +, а наилучшее, то есть соответствующее * = Далее, если не оговорено иное, под псевдорешением ИСЛАУ будет подразумеваться наилучшее возможное псевдорешение ИСЛАУ.

()2 = [1.714, 2.286] Рисунок 2.3. Пример несовместной системы. Нормальное псевдорешение (М.М. Лаврентьев), псевдорешение интервальной системы (пропорциональное расширение интервалов) Способ нахождения псевдорешения * интервальной системы линейных уравнений =, а также значения * параметра дает теорема ниже.

Теорема 2.5.1. Существует решение +, R, * R задачи линейного программирования при этом * = + является псевдорешением системы =.

Доказательство. Сначала докажем существование оптимального решения +, R, * R задачи линейного пограммирования (2.6) – (2.9).

Из теоремы 2.3.1 и теоремы Рона 1.4.2 следует, что множество решений рассматриваемой задачи не пусто. Задача, двойственная рассматриваемой, имеет вид Легко заметить, что решение 1 = 2 = 0, = 1, 2,..., является допустимым решением задачи (2.10) – (2.14). Таким образом, показано существование решений прямой (2.6) – (2.9), и двойственной (2.10) – (2.14)) задач линейного программирования. Из теоремы двойственности в линейном программировании следует существование у этих задач оптимальных решений [44].

Пусть +,, * оптимальное решение задачи (2.6) – (2.9). Из теоремы Рона следует, что * = + является допустимым решением системы = ( * ). Из оптимальности * следует, что * является наилучшим возможным псевдорешением интервальной системы линейных уравнений =. Теорема доказана.

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

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

Утверждение 2.5.1. Если точечная система = невырождена, то ее решение и псевдорешение интервальной системы =, где = [, ], = [, ] совпадают.

Доказательство. В данном случае система неравенств из теоремы Рона о точках допускового множества Примет вид Допусковое множество системы (, ) =, следовательно, * = 0. Подставим * = 0 в (2.15) – (2.16), получим.

Затем, очевидно.

Сделав замену = + = 1,..., получим обычную точечную систему =, решение которой * существует и единственно. Возвращаясь обратно к переменным +, получим единственное псевдорешение интервальной системы =, с = [, ], = [, ]. Утверждение доказано.

В том случае когда (, ( * )) неограниченно, см. критерий [1.4.3] является конечным пересечением гиперполос отличным от точки (ответом на задачу линейного программирования является грань или ребро симплекса), имеет смысл ставить дополнительную оптимизационную задачу, которая может обеспечить единственность выбора оптимального псевдорешения интервальной системы. Для решения совместной задачи о допусках имеет смысл применять методы интервального анализа, дающие оценку (, ).

Полученная задача линейного программирования (2.6)-(2.9) и двойственная (2.10) – (2.14)) потенциально имеют высокую степень вырожденности, что будет приводить, при использовании приближенных вычислений, к зацикливанию симплекс-метода и погрешностям при применении других методов решения задачи линейного программирования.

Выходом является использование рациональных вычислений без округления [52, 59], подобные разработки были предложены в совместной работе А.В. Панюкова, М.И. Германенко, В.В. Горбика библиотеке классов – «Exact Computation» 2009 года. В работах А.В. Панюкова и В.В. Горбиком доказывается что количество требуемых на каждой итерации бит памяти полиномиально зависит от числа бит, достаточных для представления элемента матрицы исходных данных. Симплекс допускает эффективное распараллеливание, при этом эффективность (т.е. отношение ускорения к числу процессоров) в асимптотике близка к 100 % [36].

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

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

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

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

Программный комплекс вычисления псевдорешения интервальной системы Основным инструментом программного комплекса является модуль решения задачи линейного программирования с помощью безошибочных вычислений, не подверженных погрешностям округления и представления. Таким фундаментальным инструментом является разработанная и реализованная автором диссертационной работы библиотека поддержки точных дробнорациональных вычислений в гетерогенных вычислительных средах с графическими ускорителями. Существующие программные продукты, использующие представление действительных чисел в формате с плавающей точкой IEEE-754-1985/754-2008, следует весьма осторожно применять для решения сложных практических задач, чувствительных к накоплению погрешностей округления.

Напомним, что требуемое количество памяти для хранения исходных данных задачи и промежуточных вычислений можно оценить заранее. Для широко известного симплекс-метода решения задачи линейного программирования на каждой итерации количество требуемых бит памяти не превосходит величины 44 + (3 ), где – минимальная из размерностей задачи, – число бит, достаточных для представления одного элемента матрицы исходных данных. Даже современные условно настольные ПК позволяют проводить решение задач размерностей порядка нескольких тысяч переменных и уравнений. Ключевым фактором является ресурс параллелизма системы, для производительных суперкомпьютеров объем оперативной памяти уже давно не является сдерживающим фактором, на одно «лезвие» (blade) может устанавливаться до терабайта оперативной памяти.

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

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

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

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

(1) распространение свойства ассоциативности операций сложения и умножения в поле действительных чисел на конечное множество машинных «действительных» чисел; (2) распространение свойства непрерывной зависимости от параметров решения системы, полученной после «эквивалентных» преобразований, на исходную систему.

Использование в параллельных вычислениях разного числа процессоров во многих случаях даёт существенно различающиеся результаты, демонстрируя необходимость применения надежных, а в некоторых случаях доказательных вычислений (см. работы К.И. Бабенко, Э.А. Бибердорф, В.А. Гаранжа, С.К. Годунов, А.И. Голиков, Ю.Г. Евтушенко, А.Н. Малышев, П.С. Панков, Н.И. Попова, Ju. Hall, J.H. Reif [1, 4, 11, 12, 22, 38, 53, 58, 69]).

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

Другой подход – вычисления с произвольной точностью. Точные вычисления могут использовать многие востребованные программные пакеты, среди которых известные инженерные пакеты (MatLab, SciLabи др.) Возможность использования точных вычислений представляет достаточно известная библиотека GMP(The GNU Multiple Precision Arithmetic Library) [52]. Библиотека распространяется под лицензией GNU LGPL, актуальная версия библиотеки GMP 6.0.1 доступна для загрузки с официального сайта проекта. Программный код оптимизирован под большинство существующих архитектур центральных процессоров, однако библиотека не предоставляет возможности использовать ее объекты в распределённых вычислениях. Надстройки именно над этим программным продуктом используют специализированные части пакетов MatLab, SciLabи пр. Объекты библиотеки изначально не предназначены для использования в распределённых параллельных вычислениях. Написание эффективной реализации оболочки для пересылок объектов в рамках коммуникационной среды является нетривиальной задачей для разработчика алгоритмов и представляет непреодолимое препятствие для большинства пользователей библиотеки.

Гораздо менее известный проект (gpuprec) посвящен поддержке вычислений высокой точности на графических процессорах (Supporting High Precision on Graphics Processors). Данный проект не получил пока широкой огласки и является концептуальной попыткой портировать часть функциональности библиотеки GMP на новое оборудование.

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

Одним из преимуществ, вытекающим из парадигмы ООП, является использование различных представлений чисел, а также переключение между представлениями, например, в зависимости от различных конфигураций оборудования. Например, уже известные алгоритмы Шёнхаге-Штрассена, Фюрера быстрого умножения длинных чисел оперируют комплексными чисел для вычисления произведения операндов, а алгоритм Тоома-Кука оперирует последовательностью бит.

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

В рамках исследований был создан комплекс поддержки дробнорациональных вычислений. Интерфейсные классы overlong и rational реализованы в объектно-ориентированной парадигме на языке C++, программный комплекс реализован в виде библиотеки классов Exact Computation 2.0 [13] с возможностью динамической загрузки.

Классы библиотеки Exact Computation 2.0 [13] позволяют производить безошибочные дробно-рациональные вычисления в любых современных операционных системах и имеют следующие характеристики.

Класс overlong расширяет возможности целочисленных вычислений в гетерогенной вычислительной среде.

Объектами класса rational являются обыкновенные дроби /, где, – объекты класса overlong.

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

Объекты класса overlong по умолчанию используют позиционную систему счисления по основанию 232.

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

Для объектов классов overlong и rational описаны все необходимые операции для пересылки в распределенной вычислительной среде с помощью функций библиотеки MPI.

Для облегчения сопровождения и модификации классов операции с памятью инкапсулированы в отдельный класс MemHandle, а выполнение базовых арифметических операций над числами полностью производится в рамках реализации класса ArifRealization (см. фрагмент листинга [3.1]).

Современная версия комплекса – библиотека классов «Exact Computation 2.0», зарегистрирована в Федеральной службе по интеллектуальной собственности. Основные особенности комплекса «Exact Computation 2.0» с технологической точки зрения:

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

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

Для пользователя библиотеки все нюансы, связанные с различными вычислительными элементами, скрыты интерфейсом библиотеки, интерфейс независим от конкретной реализации.

Для объектов классов overlong и rational определены все операторы, операции и бинарные отношения, используемые для стандартных числовых типов данных языка C++.

Поскольку увеличение показателей производительности микропроцессоров начиная с 2004 года происходит не за счет роста тактовых частот процессоров, а за счет увеличения количества параллельно работающих блоков(ядер, мультипроцессоров и т.п.) [57], то на первый план выходит разclass overlong { private : static ArifRealization realization ;

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

Самые мощные гетерогенные системы для научных вычислений строятся на базе двух специализированных ускорителей: семействе продукции IntelXeon PhiTM [41] и графических ускорителях nVidia [54]. Xeon Phi является высокоинтегрированным кластером, состоящим из процессоров архитектуры x86. CUDA устройства от Nvidiaотличаются массовым параллеR лизмом и большим количеством легковесных ядер, объединенных в блоки.

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

Программная модель CUDA (Compute Unified Device Architecture) [26, 39, 63] включает описание вычислительного параллелизма и иерархической структуры памяти непосредственно в язык программирования. С точки зрения программного обеспечения, реализация CUDA представляет собой кроссплатформенную систему компиляции и исполнения программ, части которых одновременно работают на CPU и GPU. Платформа CUDA предназначена для разработки GPGPU-приложений без привязки к графическим API и поддерживается всеми GPU nVidia, начиная с серии GeForce8.

GPGPU – General-purpose graphics processing units, техника использования графического процессора видеокарты в приложениях для общих вычислений.

Концепция CUDA отводит GPU роль массивно-параллельного сопроцессора. В литературе о CUDA основная система к которой подключен GPU называется термином хост (host), а GPU термином устройство (device).

CUDA-программа задействует как CPU, так и GPU, на CPU выполняется последовательная часть кода и подготовительные стадии для GPU-вычислений.

Параллельные участки кода выполняются на GPU одновременно большим множеством нитей (threads). Важно отметить ряд принципиальных отличий нитей на GPU от обычных потоков на CPU:

Нить на GPU чрезвычайно легковесна, ее контекст минимален, регистры распределены заранее;

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

В целом работа нитей на GPU соответствует принципу SIMD, однако есть существенное различие. Только нити в пределах одной группы (для GPU архитектуры Fermi/Kepler - 32 нити), называемой варпом (warp) выполняются физически одновременно. Нити различных варпов могут находиться на разных стадиях выполнения программы. Такой метод обработки данных получил название SIMT (Single Instruction - Multiple Threads). Управление работой варпов производится на аппаратном уровне.

Новые возможности современных версий платформы CUDA демонстрируют тенденцию к постепенному превращению GPU в самодостаточное устройство, полностью замещающее обычный CPU за счет реализации некоторых системных вызовов (в терминологии GPU системными вызовами являются, например, malloc и free, реализованные в CUDA 3.2) и добавления облегченного энергоэффективного CPU-ядра в сам GPU (архитектура Maxwell).

Важным преимуществом платформы CUDA является использование для программирования GPU языков высокого уровня. В настоящее время существуют компиляторы языков C/C++ и Fortran. Эти языки расширяются небольшим множеством новых конструкций: атрибуты функций и переменных, встроенные переменные и типы данных, оператор запуска ядра.

Ключевым приемом программирования для CUDA устройств является группировка множества нитей в блоки. На это есть две причины. Во-первых, очень мало параллельных алгоритмов имеют эффективную реализацию с помощью набора полностью независимых нитей: результат одной нити может зависеть от результата некоторых других, исходные данные нити могут частично совпадать с данными соседних. Во-вторых, размер одной выборки данных из глобальной памяти намного больше размера вещественного или целочисленного типа, т.е. одна выборка может покрыть запросы группы из нескольких нитей, работающих с подряд идущими в памяти элементами. В результате группировки нитей исходная задача распадается на независимые друг от друга подзадачи (блоки нитей) Рисунок [3.1]. Нити в рамках одного блока могут взаимодействовать, а запросы в память объединяются в рамках варпов. Разбиение нитей на варпы происходит независимо для каждого блока. Объединение в блоки является удачным компромиссом между необходимостью обеспечить взаимодействие нитей между собой и возможностью сделать соответствующую аппаратную логику эффективной и дешевой.

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

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

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

В рамках предшествующих данной работе исследований были созданы первые упрощенные версии классов overlong и rational, реализованные в объектно-ориентированной парадигме на языке C++ как библиотека классов Exact Computation [59].

Современная версия программного комплекса – библиотека классов«Exact Computation 2.0», зарегистрированная в Федеральной службе по интеллектуальной собственности, выполнена с учетом возможности использования рациональных чисел в гетерогенных распределённых компьютерных системах и имеет гибкую масштабируемую на различные архитектуры процессоров и сопроцессоров архитектуру [13].

Для более полноценного использования ресурсов современных процессорных архитектур классы overlong и rational хранят и оперируют числами по основанию 232, это позволяет эффективно использовать современные существующие 32-х и 64-х битные процессоры. Программный код операций оптимизирован для системы счисления по основанию степень числа два как того требует двоичный характер современных ЭВМ.

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

Ключевым фактором достижения эффективности вычислений является минимизация количества операций пересылки данных операндов от места хранения к арифметико-логическому устройству вычислителя. Хранение данных операндов организуется с учетом устройства, на котором производятся вычисления. При наличии в системе GPU nVidia, все данные (разR ряды) чисел хранятся непосредственно на GPU, там же выполняются арифметические операции над числами, это снижает до минимума количество пересылок данных по PCI шине, копирование в основную оперативную память системы происходит лишь для вывода во внешний источник (поток вывода, файл). Для систем без GPU вычисления проводятся на процессоре, данные хранятся непосредственно в оперативной памяти системы. Описанную методику обеспечивает реализация специальных классов MemHandle и ArifRealization.

Техника разбиения класса overlong, на три части «интерфейс-памятьарифметика», позволяет гибко использовать возможности вычислительной системы. Учтена возможность использовать современные гетерогенные вычислительные среды, например, системы с GPU ускорителями nVidia. Язык енные графические ускорителей, например, Intel HD Graphics, однако эксR перименты показали большую трудоемкость процесса кодирования при малом ускорении и, следовательно, малом приросте эффективности приложений в целом.

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

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

3.3.3 Параллельные алгоритмы для базовых арифметических Алгоритм сравнения чисел разной длины или разного знака тривиален, поэтому остановимся подробнее на алгоритме сравнения двух чисел одинаковой длины в разрядов, напомним, что разряд числа в современной версии библиотеки [13] составляет 232.

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

Основной идеей, заложенной в параллельный алгоритм, является то, что сравнение чисел требует лишь узнать номер старшего разряда, в котором числа различны. В такой постановке задача уже может быть эффективно решена параллельными методами, можно сконструировать параллельный алгоритм [3.1], граф которого не будет иметь последовательных зависимостей длины более log2. Предлагаемый ниже алгоритм [3.1–3.2] для сравнения двух чисел длины может эффективно выполняться вычислителем с массовым параллелизмом.

Алгоритм 3.1. Алгоритм операции параллельного сравнения. Часть 1.

Предусловия: Ядро запущено блоком в = 1024 нитей.

Постусловия: [] содержит результат редукции блока Процедура KERNEL_CMP(Число [], Число [], Длина, Указатель *) Выделить в shared памяти массив из /32 ячеек типа 32.

относительный индекс нити в блоке глобальный индекс нити в сетке блоков индекс блока в сетке блоков Конец условия _ () каждый бит 32хбитного числа _ равен значению выражения = Если нить имеет индекс 0 в тогда Конец условия Синхронизация всех нитей в блоке Конец условия Конец условия Конец процедуры Алгоритм 3.2. Алгоритм операции параллельного сравнения. Часть 2.

Предусловия:, имеют одинаковую длину Постусловия: Результат сравнения двух чисел 1: Функция CMP_GPU(Число [], Число [], Длина ) Выделить на GPU ячеек типа 32 () KERNEL_ Дождаться завершения _ REDUCTIONMAX(, ) Освободить память, связанную с указателем Возвратить Результат сравнения и 10: Конец функции Оценку количества шагов данного алгоритма дает утверждение [3.3.1].

Утверждение 3.3.1. Алгоритм [3.1–3.2] требует менее log2 3 параллельных шага, где длина сравниваемых чисел. При этом быстрее выполнить операцию сравнения теоретически невозможно.

Доказательство.

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

Редукция данных одного warp (32 нити) осуществляется полностью параллельно за 1 шаг.

Редукция данных массива data (32 целых) осуществляется за 5 параллельных шагов, т.е. за log2 32 шагов.

Редукция данных массива outptr(/2 целых) осуществляется за log2 (/2 ) параллельных шагов.

Итого сравнение требует log2 /2 + ((log2 25 ) + 2) = log2 + 3 = log2 3 параллельных шага, выбирается исходя из ограничений на оборудование и соотношения >= 10.

Таким образом для алгоритма сравнения достигнута теоретическая нижняя оценка для алгоритмов с входными данными [8] с применением метода сдваивания [50].

cudaDeviceSynchronize ( ) ;

checkCudaErrors ( cudaFree ( d_ptr_outp ) ) ;

ния на интервале [0, ] длина переноса, как правило, не более 2 разрядов Для обеспечения корректности вычислений требуется следить за тем, чтобы поразрядное сложение выполнялось до распространения переносов. То есть операция сложения будет выполняться в два этапа, на первом этапе производится поразрядное сложение и сохранение переносов, на втором этапе выполняется распространение переносов одновременно из всех разрядов. Этот подход требует дополнительной памяти для сохранения переносов, но прост в реализации.



Pages:     || 2 |


Похожие работы:

«УДК 94 (574): 323.331 АЙТМУХАМБЕТОВ АЙДАР АБАЕВИЧ Казахские служащие Российской империи: формирование, профессиональная и общественно-политическая деятельность в XIX – начале XX вв. (исторический аспект) 07.00.02 – Отечественная история (История Республики Казахстан) Диссертация на соискание ученой степени доктора исторических наук Научный консультант : доктор исторических наук, профессор Кабульдинов З.Е....»

«. Со Чжо Ту. РАЗРАБОТКА МЕТОДА РАСЧЕТА НЕЛИНЕЙНЫХ СИЛ ВТОРОГО ПОРЯДКА, ВОЗНИКАЮЩИХ ПРИ КАЧКЕ СУДНА НА МЕЛКОВОДЬЕ. Теория корабля и строительная механика. 05.08.01Диссертация на соискание ученой степени кандидата технических наук. Санкт-Петербург 2014. 2 Оглавление Введение.. Глава 1. Обзор методов определения линейных и нелинейных сил, возникающих при колебаниях плоских...»

«Сайдумов Джамбулат Хамидович СУД, ПРАВО И ПРАВОСУДИЕ У ЧЕЧЕНЦЕВ И ИНГУШЕЙ (ХVIII–ХХ вв.) Диссертация на соискание ученой степени доктора юридических наук Специальность – 12.00.01-теория и история права и государства; история учений о праве и государстве Грозный – 2014 1 СОДЕРЖАНИЕ: ВВЕДЕНИЕ ГЛАВА I. ИСТОРИЧЕСКИЙ ГЕНЕЗИС И ЭВОЛЮЦИЯ ТРАДИЦИЙ ПРАВА И ПРАВОСУДИЯ У ЧЕЧЕНЦЕВ И ИНГУШЕЙ §1....»

«Каян Владислав Витальевич РАЗРАБОТКА БЕЗОПАСНЫХ СПОСОБОВ МАНЕВРИРОВАНИЯ СУДНА ПРИ ВЫПОЛНЕНИИ БУКСИРНЫХ ОПЕРАЦИЙ Специальность 05.22.19 – Эксплуатация водного транспорта, судовождение Диссертация на соискание учёной степени кандидата технических наук Научный руководитель : д-р техн. наук, профессор Ю. И. Юдин Мурманск – 2   ...»

«ЗАЙКИН ОЛЕГ АРКАДЬЕВИЧ Совершенствование приводов транспортно-технологических машин использованием зубчатого бесшатунного дифференциала Специальность 05.02.02 – Машиноведение, системы приводов и детали машин Диссертация на соискание ученой степени кандидата технических наук Научный...»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Андреев, Юрий Александрович Влияние антропогенных и природных факторов на возникновение пожаров в лесах и населенных пунктах Москва Российская государственная библиотека diss.rsl.ru 2007 Андреев, Юрий Александрович.    Влияние антропогенных и природных факторов на возникновение пожаров в лесах и населенных пунктах [Электронный ресурс] : Дис. . д­ра техн. наук  : 05.26.03. ­ М.: РГБ, 2007. ­ (Из фондов Российской Государственной Библиотеки)....»

«БРИЧКИН АНДРЕЙ СЕРГЕЕВИЧ ВЛИЯНИЕ SP-D ОБМЕННОГО ВЗАИМОДЕЙСТВИЯ НА ЭКСИТОННЫЕ СОСТОЯНИЯ В ПОЛУМАГНИТНЫХ ПОЛУПРОВОДНИКОВЫХ КВАНТОВЫХ ЯМАХ И ТОЧКАХ 01.04.07 – физика конденсированного состояния ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук Научный руководитель : Доктор физико-математических наук, профессор Кулаковский Владимир Дмитриевич Черноголовка Оглавление: Введение 1. Литературный обзор....»

«ФЕДОРОВА ГАЛИНА АФАНАСЬЕВНА Оптимизация метода ВЭЖХ для терапевтического лекарственного мониторинга противосудорожных препаратов, метотрексата и циклоспорина А 05.11.11 – хроматография и хроматографические приборы Диссертация на соискание ученой степени кандидата химических наук Научный руководитель : доктор химических наук Г.И.Барам Научный консультант : кандидат медицинских наук А.В.Стародубцев Иркутск-...»

«Бышевская Анастасия Владимировна ТРАНСФОРМАЦИЯ ПРИДОРОЖНЫХ ТЕХНОГЕОСИСТЕМ НА ТЕРРИТОРИИ СМОЛЕНСКОЙ ОБЛАСТИ Специальность 25.00.36 – геоэкология (Науки о Земле) ДИССЕРТАЦИЯ на соискание ученой степени кандидата географических наук Научный руководитель : Шкаликов Виктор Андреевич доктор географических наук, профессор Научный консультант : Краснов Евгений...»

«Карягина Татьяна Дмитриевна ЭВОЛЮЦИЯ ПОНЯТИЯ ЭМПАТИЯ В ПСИХОЛОГИИ 19.00.01 – Общая психология, психология личности, история психологии Диссертация на соискание ученой степени кандидата психологических наук Научный руководитель : доктор психологических наук, профессор Василюк Ф.Е. Москва – ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ГЛАВА 1. ОСНОВНЫЕ ПОДХОДЫ К ОПРЕДЕЛЕНИЮ ЭМПАТИИ 1.1. Эмпатия...»

«Бурменская Ольга Владимировна МОЛЕКУЛЯРНО-ГЕНЕТИЧЕСКИЕ МАРКЕРЫ ИММУННОГО ОТВЕТА ПРИ ВОСПАЛИТЕЛЬНЫХ ЗАБОЛЕВАНИЯХ ОРГАНОВ ЖЕНСКОЙ РЕПРОДУКТИВНОЙ СИСТЕМЫ 03.03.03 – иммунология Диссертация на соискание ученой степени доктора биологических наук Научные консультанты: доктор медицинских наук,...»

«КАМИНСКАЯ Татьяна Леонидовна ОБРАЗ АДРЕСАТА В ТЕКСТАХ МАССОВОЙ КОММУНИКАЦИИ: семантико-прагматическое исследование специальность 10.01.10 - журналистика Диссертация на соискание ученой степени доктора филологических наук Научный консультант доктор филологических наук, профессор В.И. Коньков Санкт-Петербург 2009 2 СОДЕРЖАНИЕ ВВЕДЕНИЕ.. Глава I. ОБРАЗ АДРЕСАТА КАК ТЕКСТОВАЯ КАТЕГОРИЯ 1.1. Проблема адресации текстов в современной...»

«Гашкина Наталья Анатольевна ПРОСТРАНСТВЕННО-ВРЕМЕННАЯ ИЗМЕНЧИВОСТЬ ХИМИЧЕСКОГО СОСТАВА ВОД МАЛЫХ ОЗЕР В СОВРЕМЕННЫХ УСЛОВИЯХ ИЗМЕНЕНИЯ ОКРУЖАЮЩЕЙ СРЕДЫ 25.00.27 – гидрология суши, водные ресурсы, гидрохимия диссертация на соискание ученой степени доктора географических наук Научный консультант :...»

«Коробейников Юрий Викторович Исторический опыт осуществления общественной помощи нуждающимся органами местного самоуправления России в 1864 – 1917г.г. 07.00.02. – Отечественная история Диссертация на соискание учёной степени кандидата исторических наук Научный руководитель – доктор исторических наук Шебзухова Т.А. Ставрополь – 2003 План ВВЕДЕНИЕ..4-36 РАЗДЕЛ I. Исторические предпосылки и основные этапы формирования...»

«Паршина Татьяна Юрьевна Морфофункциональная характеристика черепа как индикатора адаптогенеза наземных беличьих в условиях Южного Приуралья Диссертация на соискание ученой степени доктора биологических наук 06.02.01 – диагностика болезней и терапия животных, патология, онкология и морфология животных Научный...»

«                  УДК 524.3, 524.4, 524.6 Глушкова Елена Вячеславовна КОМПЛЕКСНОЕ ИССЛЕДОВАНИЕ РАССЕЯННЫХ ЗВЁЗДНЫХ  СКОПЛЕНИЙ ГАЛАКТИКИ Специальность 01.03.02 – астрофизика и звёздная астрономия Диссертация на соискание ученой степени доктора физико­математических наук Москва – 2014 Оглавление...»

«1 УЛЬЯНОВСКАЯ ГОСУДАРСТВЕННАЯ СЕЛЬСКОХОЗЯЙСТВЕННАЯ АКАДЕМИЯ ИМЕНИ П.А. СТОЛЫПИНА НА ПРАВАХ РУКОПИСИ ВОЕВОДИН ЮРИЙ ЕВГЕНЬЕВИЧ АНТИОКСИДАНТНАЯ ДОБАВКА ЛИПОВИТАМ БЕТА В РАЦИОНАХ КОРОВ ЧЁРНО-ПЕСТРОЙ ПОРОДЫ И ЕЁ ВЛИЯНИЕ НА ИХ ПРОДУКТИВНОСТЬ И ТЕХНОЛОГИЧЕСКИЕ СВОЙСТВА МОЛОКА 06.02.08 –кормопроизводство, кормление сельскохозяйственных животных и технология кормов 06.02.10 –частная зоотехния, технология производства продуктов животноводства ДИССЕРТАЦИЯ на соискание ученой степени кандидата...»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Соловьев, Сергей Владимирович Экологические последствия лесных и торфяных пожаров Москва Российская государственная библиотека diss.rsl.ru 2006 Соловьев, Сергей Владимирович.    Экологические последствия лесных и торфяных пожаров  [Электронный ресурс] : Дис. . канд. техн. наук  : 05.26.03, 03.00.16. ­ М.: РГБ, 2006. ­ (Из фондов Российской Государственной Библиотеки). Пожарная безопасность Экология Полный текст:...»

«Ластовкин Артём Анатольевич Исследование спектров излучения импульсных квантовых каскадных лазеров терагерцового диапазона и их применение для спектроскопии гетероструктур на основе HgTe/CdTe с...»

«Лапина Валентина Васильевна АГРОЭКОЛОГИЧЕСКОЕ ОБОСНОВАНИЕ ЗАЩИТЫ ЯРОВЫХ ЗЕРНОВЫХ КУЛЬТУР ОТ КОРНЕВЫХ ГНИЛЕЙ В УСЛОВИЯХ ЮГА НЕЧЕРНОЗЕМНОЙ ЗОНЫ РОССИИ Специальность 06.01.07 – защита растений Диссертация на соискание ученой степени доктора сельскохозяйственных наук Научный консультант –...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.