Содержание к диссертации
Введение
1. Анализ предметной области 9
1.1. Определение предметной области 9
1.2. Состояние дел в предметной области на примере задачи решения слау
1.2.1. Введение 9
1.2.2. Форматы хранения исходных данных 10
1.2.3. Методы решения слау 11
1.2.4. Программные пакеты для решения слау 13
1.2.5. Взаимозаменяемость программных пакетов 24
1.3. Обзор существующих подходов 28
1.3.1. Стандартизация 29
1.3.2. Шаблоны проектирования 32
1.3.3. Средства автоматизации сборки 35
1.3.4. Автоматическая трансформация программ 37
1.4. Заключение 38
2. Технология быстрого прототипирования 41
2.1. Терминология 41
2.2. Общая характеристика технологии быстрого прототипирования 41
2.3. Общая схема макромодульного подхода 44
2.4. Проектирование структурных элементов макромодульного подхода
2.4.1. макроязык описаний подпрограмм 47
2.4.2. Организация сборки приложений 51
2.4.3. Планировщик 53
2.4.4. Организация исполнения макропрограмм 68
2.4.5. Конвертеры типов данных 69
2.4.6. Адаптеры библиотек 71
2.5. Проекты стандартов 72
2.5.1. Проект стандарта базовых операций линейной алгебры 72
2.5.2. Проект стандарта характеристически представимых методов глобальной оптимизации 74
3. Разработка программного комплекса сборки и исполнения макромодульных программ 77
3.1. Принципы организации программного комплекса 78
3.1.1. Назначение и основные задачи 78
3.1.2. Высокоуровневая архитектура 79
3.1.3. Программные компоненты уровня исполнения 81
3.1.4. Программные компоненты уровня планирования 81
3.1.5. Программные компоненты уровня сборки 82
3.1.6. Требования к программному и аппаратному окружению 83
3.2. Реализация программного комплекса 83
3.2.1. Общие принципы реализации программного комплекса 83
3.2.2. Реализация адаптеров библиотек 84
3.2.3. Реализация конвертеров типов данных 86
3.2.4. Реализация компонент уровня планирования 88
3.2.5. Реализация макропроцессора 92
3.2.6. Реализация модуля интеграции в microsoft visual studio 2012 94
4. Апробация макромодульного подхода разработки программ 97
4.1. Применение макромодульного подхода 97
4.2. Примеры использования макромодульного подхода
4.2.1. Умножение матриц 98
4.2.2. Быстрое преобразование фурье
4.3. Эффективность использования макромодульного подхода 101
4.4. Эффективность планировщика макромодульного подхода
4.4.1. Время планирования 106
4.4.2. Точность оценок и качество выбора
4.5. Применение макромодульного подхода для унификации доступа к переупорядочивателям при решении слау 119
4.6. Применение макромодульного подхода при разработке программной системы «кристалл» 121
4.7. Заключение 121
Литература 123
- Взаимозаменяемость программных пакетов
- Проектирование структурных элементов макромодульного подхода
- Программные компоненты уровня сборки
- Примеры использования макромодульного подхода
Введение к работе
Актуальность темы диссертационной работы. Разработка программной системы это сложная техническая и аналитическая задача. Методы разработки программного обеспечения являются областью активных научных исследований. Можно выделить работы советских, российских и зарубежных ученых М.И. Кахро, А.П. Калья, Э.Х. Тьтугу, В.М. Глушков, В.Э. Малышкин, Б. Мейер, Дж.Р. Корбин, Дж. Сигел и др. Подход к разработке программ, использующий модули и компоненты, которые оформляются в библиотеки, является на данный момент общепризнанным.
Одна из основных проблем модульной разработки - отсутствие стандартов на интерфейсы модулей. Разработчик библиотеки сам определяет удобные ему структуры хранения данных и интерфейсы функций, которые их обрабатывают. В результате, каждая реализация получается уникальной и возникает сложность, связанная с заменой используемых библиотек.
Разработка программной системы включает в себя обоснованный выбор используемых технологий и библиотек среди множества обладающих близкой функциональностью. Существует широкий класс базовых задач, таких как решение СЛАУ, вычисление преобразования Фурье и многих других, которые используются во многих прикладных проектах. Развитие вычислительных систем, программных платформ, технологий разработки программ и многообразие методов решения этих задач привело к тому, что для них разработано множество библиотек. Принять окончательное решение об используемой библиотеке можно только после детального анализа и разработки прототипа системы с использованием множества реализаций. Разработка подобного прототипа в части использования библиотек требует решения следующих задач: выбор наиболее оптиматьной библиотеки под текущие задачи проекта; поддержка нескольких библиотек; замена и/или добавление новых библиотек.
Каждая библиотека имеет свою сложность внедрения, эффективность реализации, удобство использования структур данных и поддержку различных программно-аппаратных платформ. Задача выбора библиотеки часто является многокритериальной, в связи с чем приходится идти на компромисс, выбирая некоторое «среднее» решение. Окончательный выбор одной или нескольких реализаций может быть выполнен только после разработки прототипа и проведения экспериментов по решению наиболее типичных задач проекта. При эволюционной разработке программной системы могут возникнуть задачи, которые нельзя решить, используя текущие библиотеки, например, переход на новую программно-аппаратную платформу, повышение эффективности, увеличение функциональных возможностей и т.д., тогда может возникнуть необходимость замены и/или добавления новых библиотек.
Указанные выше моменты и определяют актуальность диссертационной работы.
Предметом исследования являются методы прототипирования программного обеспечения, библиотеки решения вычислительных задач, методы и алгоритмы прогноза времени выполнения программ.
Основной целью работы является разработка технологии быстрого прототипирования для сокращения времени разработки программного обеспечения при условии необходимости выбора из множества близких по функциональности компонент (вычислительных библиотек). Предлагаемый подход должен обеспечивать бинарную совместимость библиотек и единообразие программного кода. Для описания алгоритмов и использующихся структур данных необходимо предложить макроязык, который бы позволил устранить зависимость описания от конкретного языка программирования и исключить модификацию существующего кода. Среди всех реализаций библиотек должна использоваться наиболее эффективная для текущей программно-аппаратной платформы, выбираемая автоматически, или любая, выбранная пользователем. Для задачи автоматического выбора необходимо привести формальную постановку задачи и предложить метод её решения.
Основные задачи диссертационной работы:
-
Разработать метод построения оценки времени выполнения программ.
-
Предложить технологию быстрой разработки прототипов при условии необходимости выбора из множества близких по функциональности компонент.
-
Разработать и реализовать программный комплекс, обеспечивающий сборку и исполнение программ, реализованных с использованием предлагаемого подхода быстрой разработки прототипов.
-
Подтвердить практическую полезность предложенного подхода результатами исследования трудозатрат при разработке и модификации программного обеспечения.
-
Внедрить результаты работы в программную систему «Кристалл», предназначенную для решения задач планирования процесса изготовления больших интегральных схем с субмикронными топологическими нормами, в НИИ измерительных систем им. Ю.Е. Седакова.
Научная новизна. При выполнении работы получены следующие основные новые результаты:
Разработан новый метод оценки времени выполнения программ, основанный на методах машинного обучения.
Предложена новая технология быстрой разработки прототипов, позволяющая сократить время разработки при условии необходимости выбора из множества близких по функциональности компонент.
Практическая ценность заключается в следующем.
Разработан и реализован программный комплекс, обеспечивающий сборку и исполнение программ, реализованных с использованием предлагаемого подхода. Программный комплекс может использоваться для разработки прототипов программ, которые требуют поддержки нескольких вычислительных биб-
лиотек и автоматического (или ручного) выбора наиболее эффективной реализации для заданных параметров запуска.
Практическая полезность предложенного подхода подтверждена результатами исследования трудозатрат при разработке и модификации программного обеспечения.
Методология и методы исследования. Методологическую основу диссертации составили принципы формализации, обобщения, проведение экспериментальных исследований и анализ их результатов. Работа основана на модульном подходе разработки программного обеспечения, подходах, применяющихся при решении задачи миграции программного обеспечения, а так же методах машинного обучения, обеспечивающих построение оценок времени выполнения программ.
На защиту выносятся следующие положения:
-
Метод построения оценки времени выполнения программ, основанный на методах машинного обучения.
-
Технология быстрой разработки прототипов на основе многовариантных программных компонент.
-
Программный комплекс сборки и исполнения прототипов программ.
-
Результаты численных экспериментов по оценке качества предсказания времени выполнения алгоритмов.
Обоснованность и достоверность научных положений и выводов, полученных в диссертации, подтверждается строгостью постановки задачи выбора наиболее эффективной реализации алгоритма, результатами экспериментов и их статистическим анализом, обоснованностью применения математического аппарата, обсуждением на научных конференциях и экспертизой при публикации в научной печати.
Внедрение результатов работы. Исследования по теме диссертации выполнялись при поддержке Министерства образования и науки РФ (тема Н-465-99) в рамках НИЛ "Суперкомпьютерные технологии в решении наукоемких прикладных задач". Работа поддержана грантом (соглашение от 27 августа 2013г. № 02.В.49.21.0003 между МОН РФ и ННГУ).
Практическая полезность разработанного комплекса подтверждена апробацией при создании программной системы «Кристалл», предназначенной для решения задач планирования процесса изготовления больших интегральных схем с субмикронными топологическими нормами, в НИИ измерительных систем им. Ю.Е. Седакова.
Апробации работы. Результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: конференция «SYRCoSE» (Нижний Новгород, 2010). международная конференция «Высокопроизводительные параллельные вычисления на кластерных системах» (Пермь, 2010, 2014), международная суперкомпьютерная конференция «Научный сервис в сети Интернет» (Новороссийск, 2014), конференция «Разработка ПО» CEE-SECR (Москва, 2014), семинар Института системного программирования
РАН (Москва, 2014), семинар научно-исследовательского вычислительного центра МГУ (Москва, 2015), научный семинар «Методы суперкомпьютерного моделирования» ИКИ РАН (Таруса, 2015), научные конференции и семинары Нижегородского государственного университета (Нижний Новгород, Сэров).
Публикации. По теме диссертации опубликовано 12 работ. Среди них 11 печатных работ, включая две статьи в изданиях, рекомендованных ВАК. Имеется одно свидетельство о государственной регистрации программ для ЭВМ. Список публикаций приведен в конце автореферата.
Свидетельства о регистрации программ для ЭВМ. В рамках диссертационной работы получено свидетельство о регистрации программы для ЭВМ.
Личный вклад соискателя. Постановка задачи и методика исследования принадлежат руководителю. Соискателю принадлежит разработка новой формулировки задачи построения оценки времени выполнения программ, метода её' решения, разработка программного обеспечения, выполнение исследования трудозатрат, обработка и интерпретация результатов.
Структура и объем работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка использованной литературы из 87 наименований и приложений. Основная часть работы изложена на 122 страницах текста, содержит 38 рисунков и 13 таблиц.
Взаимозаменяемость программных пакетов
Многообразие типов матриц коэффициентов, возникающих в реальных задачах, породило множество форматов их хранения. При этом для матрицы одного типа могут существовать несколько различных форматов хранения.
Формат хранения выбирается в первую очередь с целью минимизировать объём памяти, необходимый для хранения матрицы [35]. Так, в большинстве случаев, не хранят нулевые элементы матриц, если известна их структура. Для диагональных матриц достаточно хранить только элементы, расположенные на диагонали. Аналогично поступают при работе с двухдиагональными и трёхдиагональными матрицами, которые возникают при решении многих задачах математики и физики [36]. Все эти типы матриц содержатся в более широкой группе ленточных - все ненулевые элементы заключены внутри ленты, образованной между диагоналями, параллельными главной. На практике также очень часто встречаются симметричные матрицы, для которых достаточно хранить только верхнедиагональные или нижнедиагональные элементы.
Важным фактором, который определяет формат хранения, является эффективность реализации конкретного алгоритма при его использовании. Кроме того, формат хранения может учитывать особенности аппаратной платформы [34]. Так, для ряда задач очень удобен блочный формат хранения матриц [35], позволяющий снизить объём передаваемых данных. Кроме того, блочные матрицы возникают на практике при дискретизации дифференциальных операторов, а в марковских процессах кластеры состояний могут взаимодействовать специальным образом, порождая блочно-структурированную задачу [37].
Рассмотренные выше форматы использовали информацию о структуре матриц. Существует большой класс задач, в которых матрицы коэффициентов содержат большое количество нулевых элементов без ярко выраженной структуры. Для хранения подобных разреженных матриц общего вида используют следующие форматы [25]: Compressed Row Storage (CRS), Compressed Column Storage (CCS), Block Compressed Row Storage (BCRS), Compressed Diagonal Storage (CDS), Jagged Diagonal Storage (JDS) и т.д. Дополнительная информация о структуре матрицы позволяет построить ещё более оптимальные форматы хранения, например для симметричных ленточных матриц с большим количеством нулевых элементов используется профильный формат хранения [38].
Все методы решения СЛАУ можно разделить на две большие группы: прямые и итерационные. Прямые методы находят точное решение (в отсутствии ошибок округления) за конечное число шагов [35]. Итерационные – на каждом шаге уменьшают величину ошибки между точным решением и найденным на текущей итерации [21, 22]. Большая часть прямых методов построена на основе метода Гаусса, который позволяет находить решение системы общего вида с частичным выбором главного элементом (GEPP) или с полным (GECP) [17]. Обладая информацией о структуре решаемой системы, можно использовать методы, которые сходятся быстрее и требуют меньше памяти: алгоритм Холецкого [17], модификации метода Гаусса, метод прогонки, ленточный алгоритм Холецкого и пр.
Среди множества специальных матриц стоит отметить разреженные (матрица содержит большое количество нулевых элементов), которые часто получаются в реальных задачах. Важным моментом при решении подобных систем является выбор правильного порядка обработки строк и столбцов для экономии памяти и времени работы. Для достижения подобного эффекта используют переупорядочиватели [23]: обратный алгоритм Катхилл-Макки, алгоритм минимальной степени и пр.
Существует множество методов решения СЛАУ. Они отличаются скоростью работы, объёмом используемой памяти и применимостью к определённым типам матриц. Чем больше информации известно о структуре СЛАУ, тем более подходящий метод решения можно выбрать.
Для ряда практических задач прямые методы неприменимы, так как работают либо слишком долго, либо требуют много памяти. В таких случаях используют итерационные методы [21, 24]: Якоби, Гаусса-Зейделя, последовательной верхней релаксации ( ), симметричной последовательной верхней релаксации ( ), чебышевского ускорения c , блочной циклической редукции, многосеточные и пр. Отдельно стоит выделить методы подпространства Крылова [22, 24], в которых для решения СЛАУ не обязательно знать матрицу , а достаточно иметь функцию, способную вычислять матрично-векторное умножение для заданного вектора . К методам крыловского типа относят: метод сопряженных градиентов (CG), метод бисопряженных градиентов (BCG), метод минимальных невязок (MINRES), метод квазиминимальных невязок (QMR) и пр.
Скорость сходимости итерационных методов зависит от числа обусловленности матрицы. Чем лучше обусловлена матрица коэффициентов, тем быстрее сходится метод. Если матрица обусловлена плохо, то исходную СЛАУ можно заменить другой, которая предполагает сходимость итерационного метода за меньшее число шагов. Для построения новой СЛАУ используются предобуславливатели: диагональный, блочно-диагональный, Якоби, неполное разложение Холецкого, неполный LU предобуславливатель и пр.
Методы решения СЛАУ не зависят от формата хранения матрицы коэффициентов, поэтому каждый метод может быть реализован с использованием любого из них (рис. 1.1). Заметим, что используемые структуры данных часто определяют эффективность и удобство реализации конкретного алгоритма.
Проектирование структурных элементов макромодульного подхода
На практике поддержка рассмотренных четырёх положений во многих областях отсутствует. Исключением из этого правила является интерфейс передачи сообщений MPI, рассмотренный в разделе 1.3.1, который является хорошим примером предлагаемого подхода. MPI является стандартом и все его реализации поддерживают строго определённый набор функций и структур данных, поэтому приложение пользователя может быть собрано с использованием любой из реализаций, а переход с одной библиотеки на другую становится очень простым. Заметим, что и тут возникают проблемы, т.к. на практике часть реализаций MPI отходят от стандарта, что приводит к трудностям при их использовании (и это требует высокой квалификации исполнителей для преодоления трудностей).
Пример с MPI является исключением из общей тенденции отсутствия стандартов. В разделе 1.2.5 рассматриваются проблемы, возникающие при переходе между библиотеками, реализующими методы BLAS и преобразования Фурье. Библиотека FFTW де-факто является стандартом на вычисление преобразования Фурье. В результате, многие другие библиотеки реализуют интерфейсы FFTW. Например, библиотека MKL кроме собственных функций предоставляет эти интерфейсы через специальные обёртки (wrappers), которые обеспечивают связывание интерфейса FFTW с собственным интерфейсом MKL. Заметим, что MKL поддерживает несколько интерфейсов и для каждого реализована своя обёртка.
Таким образом, можно сделать вывод о том, что на практике поддержка рассмотренных четырёх положений во многих областях либо отсутствует, либо неполна. Рассматриваемое решение предлагает метод построения программного обеспечения, который объединяет рассмотренные положения и позволяет, таким образом, снизить остроту проблем, возникающих при разработке модульных программ. Предлагаемая технология быстрого прототипирования основана на развитии модульного подхода разработки программ, поэтому в дальнейшем будем использовать обозначение макромодульная технология и макромодульный подход разработки программ.
Схема сборки и исполнения программ, разработанных с использованием технологии быстрого прототипирования. Цифрами указано соответствие элементов рассматриваемого подхода и этапов разработки и выполнения макропрограммы
Первое, с чем сталкивается разработчик при использовании макромодульного подхода – это описание модели вычислений с помощью макроязыка. Макроязык является языком моделирования, который предназначен для описания алгоритмов и структур данных, использующихся в программе. При этом описывается не вся программа, а только вычислительные участки. Описание на макроязыке может выноситься в метафайл описания программы.
После разметки приложения на макроязыке выполняется трансляция исходных кодов программы с помощью макропроцессора. Макропроцессор выполняет генерацию выходного кода за счёт замены макрокоманд на макрорасширения. Сборка сгенерированных кодов может быть выполнена любыми стандартными средствами.
Полученный исполняемый модуль содержит макрорасширения. Для их выполнения требуется среда времени исполнения макропрограмм. Выполнение макрорасширений состоит из следующей последовательности действий: 1. Определяется, требуется ли выполнять макрокоманду. Если нет, то выполняется код пользователя, который ей соответствует, иначе переходим к шагу 2. 2. С помощью планировщика определяется наиболее подходящая из доступных библиотек. 3. Выполняется инициализация библиотеки, преобразование структур данных и вызов требуемого метода из библиотеки через адаптеры. Планировщик выполняет выбор наилучшей библиотеки с требуемой реализацией метода. Выбор может осуществляться как статически (на этапе сборки программы), так и динамически во время её работы.
Для приведения интерфейсов библиотек к стандартному виду используются адаптеры библиотек. Отметим, что в задачу адаптера входит не только связывание вызовов функций, но и такие этапы как инициализация и завершение библиотеки. В том случае, если структуры данных, используемые в приложении, отличаются от тех, которые используются в библиотеке, выполняется их преобразование с помощью конвертеров. 2.4. Проектирование структурных элементов макромодульного подхода
Макроязык является декларативным языком моделирования и предназначен для описания вычислительной модели участков программы, которая содержит в себе алгоритм и аргументы, участвующие в вычислении. Алгоритм определяется действием, которое необходимо выполнить (например, умножение матриц, вычисление преобразования Фурье, решение СЛАУ), и задаётся стандартизированным обозначением. Все аргументы – это переменные, которые будут использоваться в вычислительном участке программы. Каждый аргумент содержит описание используемой структуры данных, формата, в котором она хранится, и дополнительную априорную информацию (например, вид матрицы: диагональная, трёхдиагональная, верхнетреугольная и пр.). Каждый независимый вычислительный участок программы описывается отдельно, формируя макрокоманду (рис. 2.3). Иными словами, макрокоманда описывает один алгоритм.
Программные компоненты уровня сборки
Ручной и автоматический выбор наиболее оптимальной реализации алгоритма по заданному макроописанию с учётом временных затрат на преобразование форматов хранения типов данных, использующихся в алгоритме - подробнее обсуждается в 3.2.4.3.
Корректная обработка ошибочных ситуаций, которые могут произойти при выполнении макрорасширений, и возврат к выполнению пользовательского кода.
При проектировании архитектуры программного комплекса обеспечивающего исполнение и сборку макромодульных программ решались следующие задачи: выполнение требований макромодульной разработки программ, описанных в главе 2; выполнение требований к функциональности, представленных в 3.1.1; возможность функционирования среды исполнения в системах под управление различных программно-аппаратных платформ; максимальное упрощение расширения функциональности за счёт поддержки новых библиотеки и форматов хранения.
При проектировании архитектуры разработанного программного комплекса использовались компонентный и объектно-ориентированный подходы: произведена объектная декомпозиция предметной области [51], выделены ключевые абстракции, выявлены связи между ними, выполнена группировка и объединение в компоненты по функциональному принципу. В результате, была разработана системы, состоящая из трёх уровней: уровень компоненты уровня исполнения сборки, уровень планирования и уровень исполнения (рис. 3.1). Планирование вычислений может быть выполнено как на этапе разработки программы, так и на этапе её выполнения. Каждый из уровней детализируется далее программными компонентами, подсистемами и модулями. Уровень исполнения представляет собой набор динамических библиотек выполняющих преобразование форматов хранения с помощью Конвертеров и сопряжение интерфейсов с помощью Адаптеров. На уровне планирования, используя доступные Конвертеры и Адаптеры уровня исполнения, выполняется определение наиболее эффективной реализации и корректная обработка ошибочных ситуаций. На уровне сборки осуществляется трансляция исходных кодов программ, написанных с использованием макроязыка и подготовка их к дальнейшей сборке стандартными средствами. 3.1.3. Программные
Структуры данных, полученные в результате объектной декомпозиции предметной области, сгруппированы по функциональности и оформлены в виде программных компонентов уровня исполнения.
Компонент Адаптер выполняет преобразование интерфейсов алгоритмов, реализованных в библиотеке, к стандартному виду. Компонент Конвертер выполняет преобразование форматов хранения. Программный комплекс может содержать несколько Адаптеров и Конвертеров в виде динамических библиотек. Таким образом, компоненты каждого типа должны обладать единым интерфейсом для бинарной совместимости и автоматической идентификации (рис. 3.2). Рис. 3.2. Интерфейсы адаптеров и конвертеров Каждый компонент реализует три публичные функции. Функция получения версии необходима для обеспечения совместимости макромодульной программы и компонент уровня исполнения. Остальные две функции необходимы для получения всех доступных реализаций и конкретных экземпляров реализации для заданных параметров.
Уровень планирования вычислений состоит из 3-х компонент (рис. 3.3). Компонент Менеджер реализаций выполняет автоматическое обнаружение совместимых Адаптеров и Конвертеров и обеспечивает быстрый доступ к ним после начальной инициализации. Менеджер статистики обеспечивает сбор накапливаемой информации о времени работы реализаций алгоритмов и времени преобразования форматов хранения. Планировщик выполняет автоматический или ручной выбор наиболее эффективной реализации алгоритма.
Макропроцессор является основным компонентом сборки макромодульных программ. Он выполняется трансляцию исходных кодов программ, написанных с использованием макроязыка (рис. 3.4). Полученные после трансляции программные коды должны быть собраны стандартными средствами сборки. Снижение времени разработки программного обеспечения является одной из основных целей макромодульной разработки программ, поэтому для автоматизации процесса сборки программ в рамках данной работы был разработан модуль интеграции макропроцессора в среду разработки Microsoft Visual Studio. Модуль задаёт необходимые параметры для запуска макропроцессора и автоматически применяет его ко всем исходным кодам программы перед началом построения проектов. После окончания сборки модуль удаляет все созданные макропроцессором файлы.
Разработанный программный комплекс функционирует на процессорах архитектуры x86, которые являются наиболее популярными при построении вычислительных систем общего назначения (так, доля систем в списке Top500 [5], построенных на базе процессоров данного типа составляет последние годы порядка 80%). Разработанный комплекс может функционировать как в ОС семейства Windows, так и Linux.
Примеры использования макромодульного подхода
Итак, эксперименты на 84 вычислительных системах и 5 библиотеках с использование случайного леса показали, что средняя относительная ошибка предсказания не превосходит 8% для матричного умножения, 3% для сортировки, 11% для решения СЛАУ, 23% для быстрого преобразования Фурье. Предложенный подход позволяет выполнять выбор наиболее эффективной реализации с точностью более 80%, а потери времени от ошибочного выбора не превосходят 6%.
Рассмотренный подход оценки времени выполнения алгоритмов способен выполнять качественную экстраполяцию и может успешно применяться при наличии небольшого количества экспериментальных данных малой размерности. Эксперименты при обучении на данных малой размерности показали, что средняя относительная ошибка предсказания не превосходит 12% для матричного умножения, 9% для сортировки, 18% для решения СЛАУ, 39% для быстрого преобразования Фурье.
Апробация макромодульного подхода выполнялась при решении задачи унификации доступа к переупорядочивателям при решении СЛАУ, которая рассматривалась в 1.2.3. Напомним, что при решении разреженных СЛАУ, которые содержат большое количество нулевых элементов, важным моментом является выбор правильного порядка обработки строк и столбцов для экономии памяти и времени работы. Для достижения подобного эффекта используют переупорядочиватели [23]: обратный алгоритм Катхилл-Макки, алгоритм минимальной степени и пр.
Программный код решателя СЛАУ был предоставлен коллективом ВМК ННГУ, который выполнил ОКР с РФЯЦ-ВНИИЭФ «Разработка математических моделей и инструментальных средств для пакетов программ проектирования и имитационного моделирования на суперЭВМ» в 2012 г. Результат выполнения проекта - оптимизация решателя MUMPS для сокращения времени счета при решении задач с матрицами специального вида.
Целью данной работы является разработка унифицированного интерфейса для переупорядочивателей и адаптация под этот интерфейс существующих реализаций с использование макромодульного подхода. Программа, реализующая макромодульный подход, должна быть совместима по интерфейсам с пакетом MUMPS, переупорядочивателями METIS [84], О-MATRUZ [86], MORSY [85].
Результатом выполненной работы является программная система, которая обеспечивает использование требуемого переупорядочивателя для решателя СЛАУ без сборки проекта. Выбор осуществляется в ручном режиме или автоматически. Реализованы компоненты, обеспечивающие работу с переупорядочивателями METIS, O-MATRUZ, MORSY. Работа поддержана грантом (соглашение от 27 августа 2013г. № 02.В.49.21.0003 между МОН РФ и ННГУ).
Применение макромодульного подхода при разработке программной системы «Кристалл» Программная система «Кристалл» предназначена для решения задач планирования процесса изготовления больших интегральных схем с субмикронными топологическими нормами в НИИ измерительных систем им. Ю.Е. Седакова. Разработанное программное средство позволяет получать решения при долгосрочном планировании процессом изготовления СБИС. Результатом решения является расписание выполнения заказов, в котором определены сроки начала и окончания выполнения каждой операции каждого изделия каждого заказа. Решение этой задачи позволяет определить контрольные сроки завершения выполнения каждого заказа, согласовывать сроки выполнения заказов с возможностями оборудования, формировать графики исполнения с учетом блочно-иерархической структуры представления исходных данных и резервирования времени, предоставлять отчеты по требуемым материалам и запасным частям.
Заключение, выданное НИИ измерительных систем им. Ю.Е. Седакова свидетельствует о том, что использование подсистемы «Сборки и исполнения макромодульных программ MMT» во время выполнения проекта привело к сокращению трудозатрат на разработку программной системы.
В работе предлагается технологии быстрого прототипирования для сокращения времени разработки программ при условии необходимости выбора из множества близких по функциональности компонент. Подход основан на развитии модульного подхода разработки программ (макромодульный подход) и позволяет упростить разработку программного обеспечения за счёт сокращения затрат на внедрение библиотек.
При использовании макромодульного подхода выполняется описание программы с использованием набора стандартных действий (таких как «Умножение матриц», «Вычисление быстрого преобразования Фурье», «Решение СЛАУ») и стандартных структур хранения, которые участвуют в операциях. На основании подобного описания выполняется вызов соответствующих функций из библиотек через специальный адаптер, уникальный для каждой библиотеки. В том случае, если структуры хранения данных в программе и библиотеке отличаются, с помощью конвертера выполняется их преобразование. Выбор используемой библиотеки осуществляется вручную или автоматически из установленных библиотек. В результате решается проблема с выбором наиболее оптимальной библиотеки, а переход на использование новой значительно упрощается.
Макромодульный подход может применяться как технология разработки новых программ, так и для модификации уже реализованного пользователем приложения (например, для перехода на новую программно-аппаратную платформу). В обоих случаях разработчику достаточно сделать макроописание вычислительных модулей независимо от того, существует ли их реализация.