Содержание к диссертации
Введение
1 Обзор существующих методов оценки программ и возможностей их улучшения 15
1.1 Организация высокоточных вычислений 15
1.2 Метрики оценки сложности программ 22
1.3 Метрики размера программ, или количественные метрики
1.3.1 SLOC-метрика 25
1.3.2 Метрики Холстеда 26
1.3.3 ABC метрика 28
1.4 Метрики сложности потока управления программы 29
1.4.1 Метрика цикломатической сложности программы 30
1.4.2 Метрика Майерса 34
1.4.3 Метрика Хансена 34
1.4.4 Топологическая метрика Чена 34
1.4.5 Метрики Харрисона, Мейджела 34
1.4.6 Метрика Пивоварского 35
1.4.7 Метрика Джилба 36
1.4.8 Метрика граничных значений 36
1.5 Метрики сложности потока данных программ 39
1.5.1 Метрика Чепина 39
1.5.2 Метрика спена 40
1.5.3 Метрика обращения к глобальным переменным 40
1.6 Гибридные метрики 40
1.6.1 Метрика Кокола 41
1.6.2 Метрика Зольновского, Симмонса, Тейера 41
1.7 Сети Петри 43
1.7.1 Задача о взаимном исключении 48
1.7.2 Задача о производителе/потребителе 49
1.7.3 Задача о чтении/записи 50
1.7.4 Р - и V - операции над семафорами 51
1.7.5 Формализованное описание и характеристики сетей Петри 52
1. 8 Выводы по первой главе 54
2 метод Оценки сложности распределенных вычислений с повышенной точностью 55
2.1 Деревья формул 60
2.2 Оценка модифицированной цикломатической сложности 67
2.3 Оценка сложности программы, работающей в последовательном режиме
2.4 Метод распараллеливания программы для оценки ее с помощью модифицированной метрики цикломатической сложности 78
2.5 Оценка сложности программы, работающей в параллельном режиме 84
2.6 Выводы по второй главе 86
3 Получение экспериментальных зависимостей времени расчета от точности вычислений для определения сложности программ 87
3.1 Исследуемые функции класса HReal 87
3.2 Приложение для получения экспериментальных данных и их аппроксимации 89
3.3 Получение экспериментальных значений на эталонной системе
3.3.1 Метод четвертых разностей 96
3.3.2 Аппроксимация экспериментальных данных
3.4 Получение экспериментальных значений на тестовой системе для проверки адекватности эталонных значений 102
3.5 Выводы по третьей главе 111
4 Экспериментальная проверка выведенного метода 112
4.1 Выводы по четвертой главе 123
Заключение 125
Список сокращений и условных обозначений 126
Список литературы
- Метрики размера программ, или количественные метрики
- Задача о производителе/потребителе
- Оценка сложности программы, работающей в последовательном режиме
- Получение экспериментальных значений на тестовой системе для проверки адекватности эталонных значений
Введение к работе
Актуальность темы исследования. Крупные задачи, критичные к точности расчетов, возникают в самых разнообразных областях. Классификация таких задач, приведенная в табл. 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 таблиц.
Метрики размера программ, или количественные метрики
Поэтому для каждого производственного процесса делаются математические модели (ММ) элементов, принимающих в нем участие, особенно если этот процесс существует достаточно долгое время, то такие модели уже построены для каждого его элемента и для различных режимов работы в довольно большом количестве. Как правило, исследования этих процессов производятся перед запуском производств, в рамках написания диссертаций и т.п. Результатом таких исследования являются математические модели, состоящие из систем уравнений, описывающих процесс работы исследуемого аппарата. Такие системы уравнений легко переводятся в программный код на любом современном языке программирования, либо уже существуют в качестве программного продукта, расчет которого необходимо осуществить. Если такая ММ состоит из большого количества уравнений, ее расчет может занять значительное время, что может затянуть или отсрочить работу производства, особенно если такие расчеты нужно выполнять периодически, внося некоторые изменения. В таких случаях важно знать, какова сложность производимых вычислений, и какое время в итоге займет расчет этой ММ на различном по производительности оборудовании. Эти данные нужны для оптимального распределения времени расчета, чтобы оно удовлетворяло нуждам производства и затраты на работу вычислительных устройств были приемлемыми. Зная время выполнения расчетов и их сложность, можно определить, какое оборудование лучше всего для этого использовать, причем сложность этого оборудования может значительно варьироваться - от обычного компьютера до мощного вычислительно кластера. И если компьютер сегодня есть у каждого, то более мощные вычислительные комплексы доступны не всем, или их нужно арендовать за определенную плату, но они производят вычисления значительно быстрее, что может быть решающим фактором в ситуации, когда временные рамки на произведение расчетов сильно ограничены. Однако использование таких вычислительных мощностей может быть связано со значительным денежными затратами, поэтому крайне важно иметь представление о том, какие мощности будут требоваться для требуемых расчетов. Такие аппаратные комплексы в большинстве своем попадают под определение облачно управляемой распределенной вычислительной системы [29].
Термин «облачные технологии» можно отнести к любым сервисам, предоставляемым через Интернет, и их можно разделить на 3 основные категории [30]: - инфраструктура как сервис (Infrastructure as a Service, IaaS); - платформа как сервис (Platform as a Service, PaaS); - программное обеспечение как сервис (Software as a service, SaaS). В частности, такие комплексы предоставляют свои мощности как услугу, что в терминологии облачных вычислений называется Platform as a Service (PaaS, «платформа как услуга») – модель предоставления облачных вычислений, при которой потребитель получает доступ к использованию информационно-технологических платформ: операционных систем, систем управления базами данных, связующему программному обеспечению, средствам разработки и тестирования, размещённым у облачного провайдера [31]. В этой модели вся информационно-технологическая инфраструктура, включая вычислительные сети, серверы, системы хранения, целиком управляется провайдером. Им же определяется набор доступных для потребителей видов платформ и набор управляемых параметров платформ, а потребителю предоставляется возможность использовать платформы, создавать их виртуальные экземпляры, устанавливать, разрабатывать, тестировать, эксплуатировать на них прикладное программное обеспечение, при этом динамически изменяя количество потребляемых вычислительных ресурсов. Провайдер облачной платформы может взимать плату с потребителей в зависимости от уровня потребления, тарификация возможна по времени работы приложений потребителя, по объёму обрабатываемых данных и количеству транзакций над ними, по сетевому трафику[32]. Поэтому крайне важно заранее иметь представление о длительности аренды облачной платформы для расчета нужных данных, на основе сложности и предполагаемого времени завершения этого расчета, из чего и формируется ориентировочная стоимость арендной платы.
На настоящий момент набирает популярность использование мейнфреймов (mainframe) – больших универсальных высокопроизводительных отказоустойчивых серверов со значительными ресурсами ввода-вывода, большим объёмом оперативной и внешней памяти, предназначенных для использования в критически важных системах с интенсивной пакетной и оперативной транзакционной обработкой [33]. По последним экономическим исследованиям, широкое использование мейнфремов в крупных компаниях позволяет экономить до 30% на вычислительной стоимости [34]. Одна из последних моделей мейнфремов, представленная фирмой IBM в начале 2015 года, состоит из 141-го 8-ми ядерного процессора, производительность которых составляет более 111000 миллионов операций в секунду, и 10 терабайт оперативной памяти. Такая мощность может быть использована для решения огромного круга задач, но для этого также требуются механизмы оптимального распределения вычислительных ресурсов, чтобы стоимость работы такого мощного оборудования оправдывала решение этих задач.
Для распараллеливания программ в настоящее время существует несколько различных технологий. Одним из самых популярных решений для распараллеливания программ является OpenMP (Open Multi-Processing) – открытый стандарт для распараллеливания программ на языках C, C++ и Fortran. OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» поток создает набор «подчиненных» потоков и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами (количество процессоров не обязательно должно быть больше или равно количеству потоков) [35, 36]. Распараллеливание программ в диссертации рассматривается в общем виде, вне зависимости от используемых для этого технологий. Решение задачи определения сложности отдельных операций с числами с различным максимально возможным числом знаков в мантиссе в данной работе строится на базе использования класса HReal для языка программирования Visual C++, который предназначен для организации прецизионных вычислений с регулируемой точностью [29]. Под точностью представления понимается максимально возможное число десятичных разрядов в мантиссе.
Объект класса HReal создается с помощью конструктора типа HReal(число, точность = UNKNOWN_PRECISION). Прежде всего, следует уточнить второй параметр, точность может меняться в пределах от 24 до 5000. Верхний предел точности 5000 обусловлен участием в математических функциях ряда заранее вычисленных констант (, e и др.), хранимых в бинарном виде. Если отказаться от математических функций (sin, sqrt и др.), то ограничений на верхний предел точности практически нет (кроме ограничений на общий объем памяти, занимаемой программой в момент выполнения).
Задача о производителе/потребителе
Позиции и переходы соединяются ориентированными дугами. Дуги могут быть направлены только от позиций к переходам, называющиеся входными дугами, или от переходов к позициям, называющиеся, соответственно, выходными дугами. От позиции к переходам или от переходов к позициям может входить/выходить неограниченное число дуг, при этом эти несколько дуг можно заменить одной кратной дугой - имеющей вес (целое неотрицательное число), равный количеству простых дуг, которые она заменяет. Аналогичными терминами обозначаются входные и выходные позиции по отношению к переходам.
Позиции могут содержать маркеры – некие отметки, показывающие, что в данной позиции выполняется присущее ей условие. Маркеров в позиции может быть больше одного, что, как правило, показывает перевыполненность условия данной позиции, например, наличие нескольких входных переменных, ожидающих в очереди. Обычно обозначаются точками внутри круга-позиции и количество маркеров в каждой позиции является целым неотрицательным числом. Совокупность всех маркеров, размещенных в позициях сети Петри, называется разметкой сети. Маркеры могут перемещаться по сети во время срабатывания переходов, что соответствует совершению события. Последовательность событий образует моделируемый процесс [83].
Переходы срабатывают по определенным правилам: если для каждой позиции перехода выполняется условие Ni Ki , где Ni – число маркеров в i -ой входной позиции, а Ki – число дуг, идущих от этой позиции к переходу. После срабатывания перехода число маркеров в i -ой позиции уменьшается на количество исходящих из нее дуг Ki , а в i +1-ой выходной позиции этого перехода количество маркеров Ni+1 увеличивается на количество дуг Ki+1, связывающих этот переход с i +1-ой позицией. Пример срабатывания перехода показан на рисунке 10. єНоз орэ При этом, если у перехода существует несколько входных позиций, для его срабатывания в каждой из позиций количество маркеров должно быть больше или равно количеству дуг, соединяющих эти позиции с переходами. Если же у перехода есть несколько выходных позиций, то после его срабатывания количество маркеров в каждой из них пополняется на количество дуг, идущих к ним от перехода.
На рисунке 11 приведен пример срабатывания перехода. Маркировка сети на рис. а) записывается в виде (2, 2, 3, 1). Маркировка сети после срабатывания перехода показана на рис. б) и записывается в виде (0, 1, 0, 3).
Считается, что простые переходы срабатывают мгновенно, но не могут срабатывать одновременно с другими переходами, поэтому возможна конфликтная ситуация, когда несколько входных позиций соединены с несколькими переходами, и условие наличия достаточного количества маркеров выполняется для всех переходов, таким образом сработать может любой из них [84]. Выбор срабатывания перехода определяется вне сети и может быть осуществлен на основе ожидания аппаратного события, события завершения длительного процесса, выбора пользователем и т.п. Подобная конфликтная ситуация изображена на рисунке 12.
После срабатывания любого из переходов меняется разметка сети, а вместе с ней изменяется количество разрешенных переходов. Сеть Петри существует до тех пор, пока в ней существуют разрешенные переходы.
Сети Петри широко используются для моделирования различных параллельных процессов. Одна из самых распространенных и простых задач распараллеливания изображена на рисунке 13. Переход fork разделяет один процесс на две "ветви", путем создания дополнительной ветви вдобавок к существующей, а переход join соединяет две ветви в одну, путем уничтожения созданной параллельной ветви после их выполнения [85]. Рисунок 13 – Конструкция fork/join
Другие задачи синхронизации также легко моделируются по аналогии с вышеописаной конструкцией. Например, на рисунке 14 показана барьерная синхронизация нескольких процессов.
Изначально есть несколько параллельных процессов, которые активируют три длительных перехода. Лишь после того, как все три задачи будут завершены, будет разрешен переход wait, после чего процессы продолжат свою параллельную работу [85].
Другой пример - моделирование ожидание завершения нескольких процессов (рис. 15). После любого длительного по времени перехода, символизирующего какой-либо вычислительный процесс, становится разрешенным переход wait. После его срабатывания дальнейшая работа продолжается, в то время как остальные процессы завершают свое выполнение. Дополнительная входная позиция перехода wait защищает его от срабатывания при завершении остальных процессов в случае, если в текущий момент ожидание не выполняется. В процессе дальнейшей работы сети маркер в эту позицию возвращается, и тем самым разрешается ожидание и обработка результатов выполнения остальных процессов [85].
Оценка сложности программы, работающей в последовательном режиме
Оценка сложности параллельных вычислительных потоков должна учитывать характер их выполнения на ЭВМ: если эти потоки обрабатываются в параллельном режиме, оценка сложности должна быть согласована с критической линией, сложность которой максимальна. На рисунке 33 приводится иллюстрация к вышесказанному [106].
В данном алгоритме можно разбить на потоки вычисления, которые выполняются в циклах в блоках 1 и 2. Построим сеть Петри, иллюстрирующую несколько параллельных вычислительных потоков и процесс обмена данными при завершении вычислений. Она показана на рисунке 34. void main()
На этом рисунке видно 4 параллельных вычислительных процесса, каждый из которых осуществляет вычисления интегрируемой функции от четных и от нечетных отрезков интервала [a, b] в цикле for. Разница между этими процессами и тем, что показан на рисунке 32 в том, что на рисунке 32 в цикле for рассчитываются вместе и четные, и нечетные отрезки интервала, а в параллельном режиме они разнесены на два разных потока: один для четных, другой для нечетных отрезков. Эти два процесса объединены в общий цикл while, которых на рисунке 34 также два - вычисляется результат работы алгоритма для n разбиений интервала и параллельно для n 2 разбиений, для ускоренного получения сигнала к остановке расчетов. В данной схеме используется барьерная синхронизация нескольких процессов, показанная ранее на рисунке 14, но при распараллеливании программы также можно использовать любую из базовых конструкций сетей Петри, описанных ранее. Здесь имеется только одна группа параллельных вычислений, объединяющая четыре вычислительных потока, однако таких групп, следующих друг за другом, или также выполняющихся параллельно, может быть бесконечное количество.
Циклы в сети обозначены белыми прямоугольниками – длительными переходами. Они обозначены таким образом, потому что циклы могут иметь различную продолжительность выполнения. В итоге маркеры из начальных позиций попадают в позиции по окончанию циклов в разное время и, если бы это были мгновенные, а не длительные переходы, то объединение расчетов из циклов могло бы сработать до того, как завершатся все циклы, что привело бы к ошибке и завершению работы программы. Весь процесс работы программы с перемещением маркеров по сети изображен на рисунке 35.
Также, в данном случае нужно отметить, что на рисунке 34 не учитываются возможные длительные по времени передачи рассчитанных данных между процессами. В теории этим временем можно пренебречь, но на практике, если передача данных осуществляется по физическим каналам связи, например, по локальной сети, то это время может оказать значительное влияние на задержки в работе программы. Обозначим его как t , на рисунке оно обозначено мгновенным переходом между процессами расчета цикла for и считается равным 0, но в реальных расчетах такое время может обозначаться как длительный по времени переход и участвовать в расчете общего времени выполнения параллельной программы. Рисунок 35 – Перемещение маркеров по сети Петри в процессе работы программы
Итак, для расчета сложности и времени работы программы в распределенном режиме не учитывается сложность всех параллельных процессов. Для этого нужно назначить один из параллельных процессов критической линией. Это должен быть тот процесс, сложность и время выполнения которого максимальны среди всех остальных. Таким образом, метод распараллеливания программ на основе модификации графов потока управления с помощью сетей Петри выглядит следующим образом:
1. Программа представляется в виде сети Петри, показывающей параллельные вычислительные процессы и обмен данными между ними;
2. В построенной сети Петри выявляется критическая линия, соответствующая максимальным по длительности параллельным вычислительным процессам;
3. По критической линии строится ГПУ программы с добавлением длительных по времени переходов, соответствующих максимально долгим процессам обмена данными между процессами, и определяющий длительность работы программы.
В примере на рисунке 34 все параллельные процессы могут отличаться друг от друга длительностью и сложностью расчетов, выполняющихся во время длительных переходов. На рисунке эти переходы обозначены одинаковыми, так как теоретически выполняют одинаковые по сложности расчеты, хотя на практике время их выполнения может и различаться. Но считается, что в данном случае вычисления в цикле делятся поровну, соответственно, среди четырех параллельных потоков можно выбрать любой и считать его критической линией, а сложность и длительность расчетов в его цикле будет равна С . Так как в этом случае рассматривается только одна критическая линия, можно сказать, что цикломатическая сложность параллельной программы равна критической сложности одного потока – критической линии. А цикломатическая сложность этого потока такая же, как и при работе в последовательном режиме, так как он также состоит из цикла while и for. Разницу в сложности между двумя режимами работы программы можно заметить, если найти модифицированную цикломатическую сложность программы в параллельном режиме: V =lg(6 + -)xV(G) = lg(506)xV (26) и время выполнения программы: Ґ =Kx(2+h\2+g\2 + I \ = Kx(2 + h(2+g(502)). { \ 2)) (27)
Как можно заметить, сложность программы в параллельном режиме значительно уменьшилась. Из этого можно сделать вывод, что для определения модифицированной цикломатической сложности параллельной программы нужно найти сумму максимальных сложностей всех параллельных друг другу потоков: Vp=\g(±max(S?,S ...,SJ))xVs (28) где п - количество максимальных по сложности потоков в программе, j -количество потоков в одной группе параллельных вычислений, У- сквозная цикломатическая сложность, основанная на ГПУ, построенному по проходящим через сеть Петри критическим линиям. А время выполнения параллельной программы находится по следующей формуле: r= xi:max (r;,r2,..,r;) +i:maxfe,r2,..,r;_1 ) , (29) где t\ - время обмена информацией между j и j + І потоками. Эта характеристика рассчитывается аналогично нахождению сложности потока -среди всех длительных по времени процессов обмена данными между потоками в одной группе параллельных вычислений ищется занимающий максимальное время.
Получение экспериментальных значений на тестовой системе для проверки адекватности эталонных значений
Технология производства эпоксидной смолы включает следующие этапы: в реактор из нержавеющей стали с пароводяной рубашкой и мешалкой загружают эпихлоргидрин и нагревают до 40–50 оС. При работающей мешалке постепенно вводят дифенилолпропан. После растворения дифенилолпропана и получения однородного раствора тонкой струей из мерника добавляют раствор едкого натра и при 60–70 оС проводят процесс конденсации, который продолжается 1,5–2 ч. Все это время мешалка должна работать. После этого выключают обогрев аппарата, загружают воду, продолжая перемешивание. После прекращения перемешивания образовавшейся смоле дают отстояться. Разделение слоев происходит быстрее при 40–50 оС. Отстоявшийся водный слой (сверху) отделяют, а оставшуюся смолу промывают теплой водой при 40–50 оС. Количество воды определяется по объему. Промывка (перемешивание, отстаивание с последующим отделением водного слоя) продолжается до полного удаления поваренной соли, образовавшейся при реакции. Промывка контролируется пробой (промывных вод) на присутствие хлора и щелочи.
Сушка смолы производится в том же аппарате. Для этого смолу нагревают до 40–50 оС, подключают холодильник по прямой схеме (с вакуумом) и сушат до прекращения конденсации воды в холодильнике и вспенивания смолы. Сушку смолы производят и без вакуума — при атмосферном давлении и температуре около 120 оС. Сушка смолы продолжается до получения прозрачной пробы смолы при 20–25 оС. Готовая смола сливается в алюминиевую тару. В зависимости от молярного соотношения исходных компонентов конечные продукты могут быть жидкими, вязкими и твердыми.
В связи с тем, что промывку жидкой (низкомолекулярной) смолы производить значительно легче, чем вязкой (высокомолекулярной), сначала получают низкомолекулярные смолы, которые затем сплавляют с необходимым по расчету количеством дифенилолпропана и при этом получают необходимые высокомолекулярные смолы [117].
От концентрации реагентов зависит агрегатное состояние конечного продукта: нужно получить жидкую (низкомолекулярную) смолу, поэтому важно следить за точным молярным соотношением исходных компонентов [118].
В производстве используется стальной емкостный реактор, снабженный гладкой приварной теплообменной рубашкой и турбинной мешалкой. Расчеты производятся для 10 производственных циклов, и состоят из: смолы; Расчета реактора синтеза эпоксидной смолы; Теплового расчета реактора; - Расчета мощности перемешивания и подбора привода.
Для оценки работы класса HReal и апробации метода оценки сложности программ, работающих в распределенном режиме, был использован расчет материального баланса стадии приготовления конденсационного раствора эпоксидной смолы, составленного в расчете на 1 тонну готовой смолы. В процессе расчетов вычисляются следующие значения:
После запуска алгоритма оценки исходный код программы анализируется с помощью простого лексического анализатора, и из строк программы формируется массив с циклическими конструкциями и формулами, которые рассчитываются в этих циклах. Каждая из формул представляется как массив операций и операндов и таким образом формируется двоичное дерево формулы, как описано во второй главе.
Используемый алгоритм лексического анализа текста чувствителен к структурированности исходного кода программы, так как в данном исследовании не стоит задача написания сложного алгоритма сканирования текста, поэтому исходный код программы должен иметь четкую структуру для быстрого выделения в нем циклических конструкций и определения сложности переменных.
На основе массива циклов строится ГПУ исследуемой программы и выводится в отдельном диалоговом окне, как показано на рисунке 49. Выводятся значения, описывающие сложность и время расчета исследуемой программы в последовательном режиме. Также выводится стоимость расчетов на основе рассчитанного времени, если была введена цена за минуту использования оборудования.
При выборе параллельного режима работы программы узлы ГПУ, в которых возможно использование распараллеливания, выделяются красным цветом. Узлы, в которых производятся вычисления, отмечены белым цветом.
При выборе узла, в котором производятся вычисления, открывается диалоговое окно со списком строк, в которых производятся вычисления. При выборе любой из них справа выводятся значения, описывающие сложность и время ее выполнения. Эти данные рассчитываются с помощью лексического анализатора, который во время исследования исходного кода изменяет точность переменных по мере их использования в операциях с другими переменными с различной точностью.