Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Управление распределенными вычислениями на основе оценки сложности задач Бабичев Антон Михайлович

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

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Бабичев Антон Михайлович. Управление распределенными вычислениями на основе оценки сложности задач: диссертация ... кандидата Технических наук: 05.13.01 / Бабичев Антон Михайлович;[Место защиты: ФГБОУ ВО Тамбовский государственный технический университет], 2017

Введение к работе

Актуальность темы исследования. Крупные задачи, критичные к точности расчетов, возникают в самых разнообразных областях. Классификация таких задач, приведенная в табл. 1, предложена В. В. Воеводиным, К. С. Ису-повым, Ш. А. Оцоковым и др. Некоторые из них требуют двукратного увеличения точности, другие – четырехкратного, третьи же требуют сотни и более разрядов для получения численно значимых результатов. Компьютерным расчетам свойственно такое явление, как накопление ошибки вычислений. В большинстве случаев это происходит из-за ошибок округления. В таких ситуациях необходимо использование программной обработки чисел большой (превышающей длину машинного слова) разрядности, что позволит либо вообще избавиться от ошибки округления, либо свести ее к минимуму.

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

1. Классификация высокоточных задач

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

Степень разработанности темы исследования. Проблемы анализа алгоритмов на устойчивость относительно ошибок округления описываются в работах Д. Голдберга, Д. Каханера, Дж. Х. Уилкинсона, М. Овертона, К. Мо-улера, С. Нэша, С. К. Годунова, В. В. Воеводина, К. С. Исупова и др. Исследованию оценки сложности исходного кода программ посвящены работы В. В. Колдовского, А. Ю. Кулакова, В. В. Липаева, И. Н. Ледовских, А. В. Изосимова, А. Л. Рыжко, А. Н. Новичкова и др., в которых уделяется большое внимание метрикам оценки сложности программного обеспечения – количественным, графа потока управления, сложности потока данных и т.д. Однако совершенно не уделяется внимание вопросам оценки высокоточных распределенных вычислений. Вопросам организации параллельных вычислений посвящены работы В. Э. Малышкина, И. Е. Федотова, В. Б. Мараховско-го, Л. Я. Розенблюма, А. В. Яковлева и др., при этом в этих работах не обращается внимание на высокоточные вычисления, оценку их сложности и продолжительности выполнения. Фактически в вышеупомянутых работах предлагается применять методы распараллеливания и оценки сложности к вычислительным процессам, осуществляющим большие по объему вычисления, но без учета точности и длительности производимых в них операций.

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

Диссертация выполнена в рамках проекта № 1346 из реестра государственных заданий высшим учебным заведениям и научным организациям в сфере научной деятельности «Разработка теории, методов и алгоритмов организации и проведения облачных вычислений для прецизионно-доверительного решения сложных задач математического моделирования», в рамках научной школы НШ 01.2012.09 ТГТУ «Распределенные вычислительные системы в учебном процессе, научной работе и управлении».

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

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

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

определение количества параллельных процессов при решении таких задач с заранее заданной точностью;

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

Объект исследования – программное обеспечение, осуществляющие высокоточные вычисления.

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

Научная новизна:

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

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

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

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

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

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

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

Основные результаты исследования, выносимые на защиту:

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

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

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

Степень достоверности и апробация результатов исследования. Достоверность полученных результатов подтверждается корректным использованием методов оценки сложности программного обеспечения, теории графов, теории сетей Петри, непротиворечивостью результатов экспериментальных и теоретических оценок продолжительности работы программного обеспечения, работающего в последовательном и параллельном режимах. Результаты работы подтверждены актами о внедрении в организациях ООО «КомИн-форм» и ООО «Мирантис ИТ», а также тремя свидетельствами о государственной регистрации программ для ЭВМ.

Работа соответствует п. 4, 5, 11 паспорта специальности 05.13.01 «Системный анализ, управление и обработка информации (информационные технологии)».

По материалам диссертации опубликовано девять работ, в том числе две работы в журналах из списка SCOPUS и одна из списка Web of Science, три работы в журналах из списка ВАК РФ, получено три свидетельства о государственной регистрации программ для ЭВМ.

В публикациях, написанных в соавторстве, лично автору принадлежат результаты: анализа предметной области [1, 4, 9], формулировки и постановки задач [2], разработки методов и модели оценки скорости и сложности параллельных высокоточных вычислений [3, 5], выносимых на защиту, итоги оценки эффективности использования полученных результатов [10 – 12].

Диссертация включает введение, четыре главы, выводы, заключение, библиографический список из 119 наименований публикаций отечественных и зарубежных авторов, приложения. Диссертационная работа изложена на 140 страницах (без приложений), содержит 57 рисунков и 10 таблиц.