Технология быстрого прототипирования программ на основе многовариантных программных компонент тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Сиднев Алексей Александрович

• Сиднев Алексей Александрович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Сиднев Алексей Александрович

ВВЕДЕНИЕ

Актуальность темы

Цели работы

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

Практическая значимость

Основные результаты

Структура работы

1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1. Определение предметной области

1.2. Состояние дел в предметной области на примере задачи решения СЛАУ

1.2.1. Введение

1.2.2. Форматы хранения исходных данных

1.2.3. Методы решения СЛАУ

1.2.4. Программные пакеты для решения СЛАУ

1.2.5. Взаимозаменяемость программных пакетов

1.3. Обзор существующих подходов

1.3.1. СТАНДАРТИЗАЦИЯ

1.3.2. ШАБЛОНЫ ПРОЕКТИРОВАНИЯ

1.3.3. Средства автоматизации сборки

1.3.4. Автоматическая трансформация программ

1.4. Заключение

2. ТЕХНОЛОГИЯ БЫСТРОГО ПРОТОТИПИРОВАНИЯ

2.1. Терминология

2.2. Общая характеристика технологии быстрого прототипирования

2.3. Общая схема макромодульного подхода

2.4. Проектирование структурных элементов макромодульного подхода

2.4.1. Макроязык описаний подпрограмм

2.4.2. Организация сборки приложений

2.4.3. Планировщик

2.4.4. Организация исполнения макропрограмм

2.4.5. Конвертеры типов данных

2.4.6. Адаптеры библиотек

2.5. Проекты стандартов

2.5.1. Проект стандарта базовых операций линейной алгебры

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

3. РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА СБОРКИ И ИСПОЛНЕНИЯ

МАКРОМОДУЛЬНЫХ ПРОГРАММ

3.1. Принципы организации программного комплекса

3.1.1. Назначение и основные задачи

3.1.2. Высокоуровневая архитектура

3.1.3. Программные компоненты уровня исполнения

3.1.4. Программные компоненты уровня планирования

3.1.5. Программные компоненты уровня сборки

3.1.6. Требования к программному и аппаратному окружению

3.2. Реализация программного комплекса

3.2.1. ОБЩИЕ ПРИНЦИПЫ РЕАЛИЗАЦИИ ПРОГРАММНОГО КОМПЛЕКСА

3.2.2. Реализация адаптеров библиотек

3.2.3. Реализация конвертеров типов данных

3.2.4. Реализация компонент уровня планирования

3.2.5. Реализация макропроцессора

3.2.6. Реализация модуля интеграции в Microsoft Visual Studio

4. АПРОБАЦИЯ МАКРОМОДУЛЬНОГО ПОДХОДА РАЗРАБОТКИ

ПРОГРАММ

4.1. Применение макромодульного подхода

4.2. Примеры использования макромодульного подхода

4.2.1. Умножение матриц

4.2.2. Быстрое преобразование Фурье

4.3. Эффективность использования макромодульного подхода

4.4. Эффективность планировщика макромодульного подхода

4.4.1. Время планирования

4.4.2. Точность оценок и качество выбора

4.5. Применение макромодульного подхода для унификации доступа к переупорядочивателям при решении СЛАУ

4.6. Применение макромодульного подхода при разработке программной системы «Кристалл»

4.7. Заключение

ЛИТЕРАТУРА

ПРИЛОЖЕНИЕ 1. MKL ВЕРСИЯ УМНОЖЕНИЯ МАТРИЦ

ПРИЛОЖЕНИЕ 2. CUBLAS ВЕРСИЯ УМНОЖЕНИЯ МАТРИЦ

ПРИЛОЖЕНИЕ 3. ФРАГМЕНТЫ ИСХОДНЫХ ТЕКСТОВ ПРОГРАММНОГО

КОМПЛЕКСА

ВВЕДЕНИЕ

Введение диссертации (часть автореферата) на тему «Технология быстрого прототипирования программ на основе многовариантных программных компонент»

Актуальность темы

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

• поддержка нескольких библиотек;

• замена и добавление новых библиотек;

• выбор наиболее оптимальной библиотеки под текущие задачи проекта.

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

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

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

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

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

Указанные выше моменты и определяют актуальность диссертационной работы.

Цели работы

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

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

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

При выполнении работы получены следующие основные новые результаты:

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

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

Практическая значимость

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

Исследования по теме диссертации выполнялись при поддержке Министерства образования и науки РФ (тема Н-465-99) в рамках НИЛ "Суперкомпьютерные технологии в решении наукоемких прикладных задач". Работа поддержана грантом (соглашение от 27 августа 2013г. № 02.В.49.21.0003 между МОН РФ и ННГУ).

Практическая полезность разработанного комплекса подтверждена апробацией при создании программной системы «Кристалл», предназначенной для решения задач планирования процесса изготовления больших интегральных схем с субмикронными топологическими нормами, в НИИ измерительных систем им. Ю.Е. Седакова.

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

Основные результаты

Результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: конференция «SYRCoSE» (Нижний

Новгород, 2010), международная конференция «Высокопроизводительные параллельные вычисления на кластерных системах» (Пермь, 2010, 2014), международная суперкомпьютерная конференция «Научный сервис в сети Интернет» (Новороссийск, 2014), конференция «Разработка ПО» СЕЕ-БЕСЯ (Москва, 2014), семинар Института системного программирования РАН (Москва, 2014), семинар научно-исследовательского вычислительного центра МГУ (Москва, 2015), научный семинар «Методы суперкомпьютерного моделирования» ИКИ РАН (Таруса, 2015), научные конференции и семинары Нижегородского государственного университета (Нижний Новгород, Саров).

По теме диссертации опубликовано 12 работ. Среди них 11 печатных работ, включая 2 статьи в изданиях, рекомендованных ВАК. Имеется 1 свидетельство о государственной регистрации программ для ЭВМ.

Структура работы

Диссертационная работа состоит из введения, 4 глав, заключения, списка использованной литературы из 87 наименований и приложений. Основная часть работы изложена на 122 странице текста, содержит 38 рисунков и 13 таблиц.

1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1. Определение предметной области

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

Дальнейший анализ состояния дел в предметной области выполняется на примере задачи решения СЛАУ.

1.2. Состояние дел в предметной области на примере задачи решения СЛАУ

1.2.1. Введение

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

Ах = Ь,

где А - матрица коэффициентов, Ь - вектор правых частей уравнений, а х -искомое решение. Например:

• решение дифференциальных уравнений с помощью разностной схемы (например [20]),

• моделирование задачи о смещении механической структуры под воздействием внешних сил,

• вычисления трёхмерного электромагнитного поля в частотной области при расчётах различных волновых устройств [19] и пр.

Для каждого класса решаемых задач матрицы коэффициентов могут иметь определённую структуру:

• симметричные положительно определённые,

• симметричные незнакоопределённые,

• ленточные,

• разреженные общего вида,

• зависящие от 0(п) независимых параметров [18] и пр.

такое большое разнообразие типов систем породило множество методов решения СЛАУ.

1.2.2. Форматы хранения исходных данных

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

Формат хранения выбирается в первую очередь с целью минимизировать объём памяти, необходимый для хранения матрицы [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].

1.2.3. Методы решения СЛАУ

Все методы решения СЛАУ можно разделить на две большие группы: прямые и итерационные. Прямые методы находят точное решение (в отсутствии ошибок округления) за конечное число шагов [35]. Итерационные - на каждом шаге уменьшают величину ошибки между точным решением и найденным на текущей итерации [21, 22].

Большая часть прямых методов построена на основе метода Гаусса, который позволяет находить решение системы общего вида с частичным выбором главного элементом (GEPP) или с полным (GECP) [17]. Обладая информацией о структуре решаемой системы, можно использовать методы, которые сходятся быстрее и требуют меньше памяти: алгоритм Холецкого [17], модификации метода Гаусса, метод прогонки, ленточный алгоритм Холецкого и пр.

Среди множества специальных матриц стоит отметить разреженные (матрица содержит большое количество нулевых элементов), которые часто получаются в реальных задачах. Важным моментом при решении подобных систем является выбор правильного порядка обработки строк и столбцов для экономии памяти и времени работы. Для достижения подобного эффекта используют переупорядочиватели [23]: обратный алгоритм Катхилл-Макки, алгоритм минимальной степени и пр.

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

Для ряда практических задач прямые методы неприменимы, так как работают либо слишком долго, либо требуют много памяти. В таких случаях используют итерационные методы [21, 24]: Якоби, Гаусса-Зейделя, последовательной верхней релаксации (Б0Я(ш)), симметричной последовательной верхней релаксации (550^(^)), чебышевского ускорения c 5Б0Я(ш), блочной циклической редукции, многосеточные и пр. Отдельно стоит выделить методы подпространства Крылова [22, 24], в которых для решения СЛАУ не обязательно знать матрицу А, а достаточно иметь функцию, способную вычислять матрично-векторное умножение А • Ь для заданного вектора Ь. К методам крыловского типа относят: метод

сопряженных градиентов (CG), метод бисопряженных градиентов (BCG), метод минимальных невязок (MINRES), метод квазиминимальных невязок (ОМЯ) и пр.

Скорость сходимости итерационных методов зависит от числа обусловленности матрицы. Чем лучше обусловлена матрица коэффициентов, тем быстрее сходится метод. Если матрица обусловлена плохо, то исходную СЛАУ можно заменить другой, которая предполагает сходимость итерационного метода за меньшее число шагов. Для построения новой СЛАУ используются предобуславливатели: диагональный, блочно-диагональный, Якоби, неполное разложение Холецкого, неполный LU предобуславливатель и пр.

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

Рис. 1.1. Соотношение методов решения СЛАУ и форматов хранения

матриц

1.2.4. Программные пакеты для решения СЛАУ

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

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

В таблице 1 представлены сведения о некоторых математических библиотеках, предназначенных для решения СЛАУ, с перечислением методов, которые они реализуют (прямые и/или итерационные), поддерживаемых форматах хранения матриц (плотные и/или разреженные), даты последнего обновления, доступности исходных кодов библиотеки, возможности параллельных вычислений и о программной платформе, под которую библиотека реализована. Таблица построена диссертантом на основании информации о библиотеках, доступной на начало 2014 года.

Таблица 1. Краткие сведения о математических библиотеках

решения СЛАУ

Библиотека Дата последнего обновления Операционные системы Доступна в исходных кодах Параллелизм Решение СЛАУ

Unix/ Linux Windows Прямые методы Итер. методы Разр. матр. Плотн. матр.

A Parallel Sparse Direct Solver 1.0.3 9-May-1999 Да Нет Да MPI Да Нет Да Нет

Aztec 2.1 15-Dec-1999 Да Нет Да MPI, Intel Paragon, nCUBE Нет Да Да Нет

BlockSolve 95 v3.0 8-Jul-1997 Да Нет Да MPI Да Да Да Нет

BPKIT2 1-Sep-1996 Да Нет Да MPI Нет Да Нет Нет

CXML 1-Aug-2001 Да Нет Нет OpenMP Да Да Да Да

GotoBLAS2 1.13 5-Feb-2010 Да Да Да Threads, OpenMP Да Нет Нет Да

Hypre 2.9.0b 30-0ct-2012 Да Нет Да MPI, OpenMP Нет Да Да Нет

Intel Math Kernel Library 11.1 27-Sep-2013 Да Да Нет OpenMP, MPI Да Нет Да Да

LAPACK 3.4.2 25-Sep-2012 Да Да Да Нет Да Нет Нет Да

MA41 1.2.0 1-May-2011 Да Нет Да Нет Да Нет Да Нет

MUMPS 4.10.0 1-May-2011 Да Да Да MPI Да Нет Да Нет

NL 1.0.3 8-0ct-2006 Нет Да Да Нет Да Да Да Да

OpenBLAS 0.2.8 1-Aug-2013 Да Да Да Threads, OpenMP Да Нет Нет Да

PETSc 3.4 13-May-2013 Да Да Да MPI, POSIX threads, NVIDIA GPUs Да Да Да Да

ScaLAPAC K 2.0.2 1-May-2012 Да Да Да MPI Да Нет Нет Да

SuperLU 4.3 14-Dec-2011 Да Да Да Нет Да Нет Да Нет

SuperLU D IST 3.3 31-Mar-2013 Да Да Да MPI Да Нет Да Нет

SuperLU M T 2.1 20-Mar-2013 Да Да Да POSIX threads, OpenMP Да Нет Да Нет

Trilinos 11.4.2 22-Oct-2013 Да Да Да MPI, OpenMP Да Да Да Да

UMFPACK 5.6.2 25-Apr-2013 Да Да Да Нет Да Нет Да Нет

1.2.4.1. Специализация программных пакетов

Наиболее обширно представлены библиотеки, которые специализируются на решении СЛАУ определёнными методами (например, только прямые методы). На рис. 1.2 показано распределение методов решения СЛАУ по библиотекам на основании данных из таблицы 1. Универсальных библиотек, которые предоставляют наиболее полный набор методов для решения СЛАУ, не так много. Среди таковых можно выделить PETSc и пакет Trilinos.

Рис. 1.2. Распределение методов решения СЛАУ по библиотекам

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

Разреженные

Рис. 1.3. Тип поддерживаемых СЛАУ в библиотеках

1.2.4.2. Актуальность программных пакетов

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

• потребность в новых методах решения СЛАУ;

• «устаревание» используемой библиотеки;

• переход на новую программно-аппаратную платформу.

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

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

Рис. 1.4. Последние обновления библиотек по годам

На рис. 1.4 видно, что большая группа библиотек имеет актуальное состояние. С 2010 года выходили обновлённые версии 13 библиотек. Остальные 7 можно считать устаревшими. Таким образом, библиотеки могут устаревать:

• методы, реализованные в библиотеки, перестали быть актуальными,

• разработчики библиотеки покинули этот проект,

• прекратился выпуск программно-аппаратной платформы, для которой разрабатывалась библиотека и др.

1.2.4.3. Адаптация программных пакетов для разных программно-аппаратных платформ

Разработка ПО - это дорогостоящая работа, поэтому реализовать поддержку всего многообразия программно-аппаратных платформ практически невозможно. Разработчики пишут библиотеки под весьма ограниченный набор ОС и аппаратных платформ. Более того, часть библиотек специализируется на поддержке только определённой программно-аппаратной платформы. Например, разработчики аппаратуры выпускают математические библиотеки, оптимизированные для их процессоров: CXML, Intel MKL.

Linux- или Unix-подобные операционные системы широко используются для научных вычислений. Эта тенденция прослеживается и у разработчиков библиотек. На рис. 1.5 показана диаграмма ОС, которые поддерживают библиотеки (на основании данных из таблицы 1).

■ Только Linux

■ Только Windows

■ Windows и Linux

Рис. 1.5. ОС, поддерживаемые библиотеками

Практически все рассматриваемые библиотеки имеют реализацию под Linux (только одна выбивается из этого правила). Большая часть библиотек имеет реализации как под Linux, так и под Windows. В первую очередь это связано с тем, что библиотеки доступны в исходных кодах (рис. 1.6, на основании данных из таблицы 1). Чаще всего, основная разработка ведётся под Linux, а для сборки библиотеки под Windows требуется предпринять некоторые усилия (широко используется сборка из среды cygwin [27]).

■ Библиотеки в исходных кодах

■ Библиотеки без исходных кодов

Рис. 1.6. Библиотеки с открытым/закрытым исходным кодом

Наиболее перспективным направлением увеличения

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

Рис. 1.7. Параллельные и последовательные библиотеки

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

• SMP-системы - системы с общей памятью (разработка с помощью POSIX threads, OpenMP, TBB и др.);

• Ускорители - специализированные вычислители, устанавливающиеся дополнительно (часто в виде PCI-Express карточки) в вычислительные системы (например, NVIDIA Tesla, ATI FireStream, Intel Xeon Phi);

• Кластеры (MPI, PVM и др.).

На рис. 1.8 представлена диаграмма параллельных платформ, для которых реализованы библиотеки на основании данных из таблицы 1.

14

<U 12

S 10 ю £ а

m

Т 4

8

1

SMP-системы Ускорители Кластеры Рис. 1.8. Платформы параллельных реализаций библиотек

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

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

Наиболее высокопроизводительные суперкомпьютеры представлены в списке TOP 500 [5], который обновляется два раза в год. На основании этого списка можно проследить развитие и обновление архитектур суперкомпьютеров (рис. 1.9). Почти 50% суперкомпьютеров первого списка составляли системы с общей памятью (SMP), 23.8% - массово-параллельные системы (MPP), 19.4% - однопроцессорные суперкомпьютеры и 7% -векторные. Спустя 10 лет массово-параллельные системы составляли 42.2%, а остальную часть занимали кластера разделённые на два класса в зависимости от количества ядер/процессоров, используемых в вычислительных узлах. В настоящее время подавляющая часть суперкомпьютеров - это кластеры, а доля систем с массово-параллельной архитектурой сократилась до 17.8%. Наиболее высокопроизводительные современные кластеры устроены по гибридной архитектуре: наравне с вычислительной мощностью процессоров общего назначения используются спецвычислители (например, GPU общего назначения).

Стоит отметить, что помимо архитектуры суперкомпьютеры отличаются используемой операционной системой: Windows, Linux-подобные, Unix-подобные.

Рис. 1.9. Развитие архитектур суперкомпьютеров1

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

В качестве примера можно рассмотреть вычислительный центр МГУ, который использовал такие вычислительные системы как: «Стрела», «М-20», БЭСМ-4, БЭСМ-6, «Сетунь» (использовалась троичную систему счисления). В новейшей истории России в его состав были добавлены (и обновлены) кластера: SCI, AQUA, LEO, ANT, Twinl, Twin2, «Чебышев» , «Ломоносов» ,

Список литературы диссертационного исследования кандидат наук Сиднев Алексей Александрович, 2016 год

ЛИТЕРАТУРА

1. Джосьютис Н. C++ Стандартная библиотека. Для профессионалов. — СП Питер, 2004. — 730 с.

2. NAS overview. URL: http://www.hec.nasa.gov/news/brochures/NAS 25th.pdf (дата обращения: 15.07.2014).

3. Intel® Math Kernel Library (Intel® MKL). URL: http : //software. intel. com/en-us/articles/intel-mkl/ (дата обращения: 15.07.2014).

4. NAS Software & Datasets. URL: http : //www. nas. nasa. gov/publications/software datasets. html (дата обращения: 15.07.2014).

5. TOP 500. URL: http://www.top500.org/lists/2012/11/ (дата обращения: 15.07.2014).

6. Message Passing Interface Forum. URL: http : //www. mpi-forum. org/ (дата обращения: 15.07.2014).

7. MPICH-A Portable Implementation of MPI. URL: http : //www. mcs. anl. gov/research/proj ects/mpi/mpich 1-old/ (дата обращения : 15.07.2014).

8. Intel® MPI Library. Message Passing Interface Library. URL: http://software.intel.com/en-us/articles/intel-mpi-library/ (дата обращения: 15.07.2014).

9. Open MPI: Open Source High Performance Computing. URL: http://www.open-mpi.org/ (дата обращения: 15.07.2014).

10.CUBLAS. URL: http://developer.nvidia.com/cublas (дата обращения: 15.07.2014).

11.BLAS (Basic Linear Algebra Subprograms). URL: http://www.netlib.org/blas/ (дата обращения: 15.07.2014).

12.Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток: Пер. с англ. — М.: Радио и связь, 1985. — 248 с.

123

13.The Intel® Math Kernel Library and its Fast Fourier Transform Routines. URL: http://software.intel.com/en-us/articles/the-intel-math-kernel-library-and-its-fast-fourier-transform-routines/ (дата обращения: 15.07.2014).

14.Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. — СПб: Питер, 2001. — 368 с.

15. Сверхсложные вычислительные задачи, решаемые на суперкомпьютерах. URL: http: //parallel. ru/research/chal l en ges. html (дата обращения: 15.07.2014).

16.Махоткин А. GNU Autotools — инфраструктура для сборки программ: Automake. 2001. URL: http://squadette.ru/autotools-ru/article1.html (дата обращения: 15.07.2014).

17.Деммель Дж. Вычислительная линейная алгебра. Теория и приложения. Пер. с англ. — М.: Мир, 2001. — 430 с.

18.Kailath Sayed. Displacement Structure: Theory and Applications. — SIAM Review, vol. 37, no. 3, 1995. Pp. 297-386.

19.Бутюгин Д. С. Алгоритмы решения СЛАУ на системах с распределенной памятью в применении к задачам электромагнетизма // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. №46. 2012. С. 5-18.

20.Ильин А. М. Разностная схема для дифференциального уравнения с малым параметром при старшей производной. Матем. заметки, 6:2 (1969), 237-248.

21.Saad Y. Iterative methods for sparse linear systems. — 2nd edition. — SIAM Society for Industrial & Applied Mathematics, 2003. — С. 477.

22.Axelsson O. Iterative Solution Methods. Cambridge University Press (March 29, 1996). 672 pp.

23. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. - М.: Мир, 1982.

24.Hackbush W. Iterative Solution of Large Sparse Systems of Equations. Springer-Verlag, Berlin, 1994.

25.Barrett R. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. 1993. 112 pp.

26.Freely Available Software for Linear Algebra (May 2013). URL: http://www.netlib.org/utk/people/JackDongarra/la-sw.html (дата обращения: 15.07.2014).

27.Cygwin. URL: http://www.cygwin.com/ (дата обращения: 15.07.2014).

28. Садовничий В. Стратегия развития супервычислений в МГУ и их место в инновационном образовании и научных исследованиях. URL: http://www.msu.ru/projects/supercomp.html (дата обращения: 15.07.2014).

29.Чемберс М. Запись компакт-дисков и DVD для "чайников", 2-е издание. Пер. с англ. — М.: Издательский дом "Вильяме", 2004. — 304 С.

30.Rajkumar Buyya. High Performance Cluster Computing. Volume 1: Architectures and Systems. Volume 2: Programming and Applications. Prentice Hall PTR, Prentice-Hall Inc., 1999.

31.Gregory R. Andrews. Foundations of Multithreading, Parallel and Distributed Programming. Addison-Wesley, 2000.

32.Гергель В.П. Теория и практика параллельных вычислений. Бином, 2007 г. 33.International Standard ISO/IEC 9945-1 (ANSI/IEEE Std 1003.1) Second

Edition. 1996-07-12. Information Technology - Portable Operating System Interface (POSIX) - Part 1: System Application Program Interface (API) [C Language].

34.Oberhuber Tomás, Suzuki Atsushi, Vacata Jan. New Row-grouped CSR format for storing the sparse matrices on GPU with implementation in CUDA. eprint arXiv:1012.2270, 2010.

35.Голуб Дж., Ван Лоун Ч. Матричные вычисления. - М.: Мир, 1999.

36.Прасолов В. В. Задачи и теоремы линейной алгебры. — М.: Наука, 1996.

37.Kaufman Linda. Matrix Methods for Queueing Problems. SIAM Journal on Scientific and Statistical Computing. Vol 4., No. 3, 1983. Pp. 525-552.

38.Писсанецки С. Технология разреженных матриц. — М.: Мир,1988.

39.Ицыксон В.М., Зозуля А.В. Автоматизированная трансформация программ при миграции на новые библиотеки. Программная инженерия. 2012. № 6. С. 8-14.

40.Ицыксон В.М. Автоматизация реинжиниринга программного обеспечения при портировании на новые библиотеки с помощью частичных спецификаций. Информационно-управляющие системы. №2, 2012. -СПб:РИЦ ГУАП. C. 31-38.

41.Shved P., Silakov D. Binary Compatibility of Shared Libraries Implemented in C++ on GNU/Linux Systems. SYRCoSE, 2009.

42.Ponomarenko A., Rubanov V., Khoroshilov A. A system for backward binary compatibility analysis of shared libraries in Linux // Proc. of Software Engineering Conference in Russia (CEE-SECR). 5th Central and Eastern European. Moscow, 2009. P. 25—31.

43.Rubanov V. Automatic Analysis of Applications for Portability Across Linux Distributions // Proc. of the Third International Workshop on Foundations and Techniques for Open Source Software Certification (OpenCert 2009). Electronic Communications of EASST. 2009. Vol. 20. Р. 1—9.

44.Автоматизированный реинжиниринг программ / Под. ред. проф. А. Н. Терехова и А. А. Терехова. СПб.: Изд-во С.-Петербургского университета, 2000. 332 с.

45.DMS Software Reengineering Toolkit. URL: http://www.semdesigns.com/products/DMS/DMSToolkit.html (дата обращения: 15.07.2014).

46.Klint P., van der Storm T., Vinju J. RASCAL: A Domain Specific Language for Source Code Analysis and Manipulation // Proc. of Ninth IEEE International

Working Conference on Source Code Analysis and Manipulation. 2009. P. 168—177.

47.Cordy J. R. The TXL source transformation language // Science of Computer Programming, 2006. N 61 (3). P. 190—210.

48.Bravenboer M., van Dam A., Olmos K.Eelco Visser Program Transformation with Scoped Dynamic Rewrite Rules. Technical Report UU-CS-2005-005. Department of Information and Computing Sciences. Utrecht University.

49.Scowen R. S. Extended BNF | A generic base standard. URL: http: //www. cl. cam. ac. uk/~mgk25/iso-14977-paper.pdf (дата обращения: 15.07.2014).

50.Don Schwarz. Peeking Inside the Box: Attribute-Oriented Programming with Java 1.5, Part 1. 06/30/2004.

51.Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. Второе издание. - Бином, 1998.

52.randomForest: Breiman and Cutler's random forests for classification and regression. URL: http://cran.r-project.org/web/packages/randomForest/index.html (дата обращения: 15.07.2014).

53.Rserve - Binary R server. URL: http://rforge.net/Rserve/ (дата обращения: 15.07.2014).

54.Charnes A., Frome E. L., Yu P. L. The Equivalence of Generalized Least Squares and Maximum Likelihood Estimates in the Exponential Family // Journal of the American Statistical Association 71 (353), 1976. 169-171.

55.Rice J. R. The algorithm selection problem // Advances in Computers, 15, 1976. 65-118.

56.Gomes C. P., Selman B., Crato N., Kautz H. Heavy-tailed phenomena in satisfiability and constraint satisfaction problems // Journal of Automated Reasoning, 24(1), 2000. 67-100.

57.Hutter F., Xu L., Hoos H.H., Leyton-Brown K. Algorithm Runtime Prediction: Methods & Evaluation // Artificial Intelligence vol. 206, 2014. 79-111.

58.Fink E. How to solve it automatically: Selection among problem-solving methods // In Proceedings of the Fourth International Conference on AI Planning Systems. AAAI Press, 1998. 128-136.

59.Howe A. E., Dahlman E., Hansen C., Scheetz M., Mayrhauser A. Exploiting competitive planner performance // In S. Biundo & M. Fox (Eds.), Recent Advances in AI Planning (ECP'99), volume 1809 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2000. 62-72.

60.Roberts M., Howe A. Learned models of performance for many planners. In ICAPS 2007 Workshop AI Planning and Learning. 2007.

61.Xu L., Hutter F., Hoos H., Leyton-Brown K. SATzilla2009: an automatic algorithm portfolio for SAT. Solver description, SAT competition 2009. 2009.

62.Gagliolo M., Schmidhuber J. Dynamic algorithm portfolios. In International Symposium on Artificial Intelligence and Mathematics (ISAIM'06). 2006.

63.Kotthoff L., Gent I. P., Miguel I. An evaluation of machine learning in algorithm selection for search problems // AI Commun., 25(3), 2012. 257-270.

64.Brewer E. A. High-level optimization via automated statistical modeling // In Proceedings of the 5th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (PPOPP-95). 1995. 80-91.

65.Goto K., Van De Geijn R.A.. Anatomy of highperformance matrix multiplication. ACM Transactions on Mathematical Software, 34 (3), art. no. 12., 2008.

66.Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Clifford. Introduction to Algorithms, 3rd. MIT Press, 2009.

67.Intel Processor Identification and CPUID Instruction. Application Node 485. August 2009.

68.Agner Fog. Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs. URL:

http: //www.agner. org/optimize/instruction_tables.pdf (дата обращения: 25.07.2014).

69.Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer series in statistics. Springer, 2001.

70.Rifai S., Bengio Y., Dauphin Y., Vincent P. A Generative Process for Sampling Contractive Auto-Encoders. ICML'2012. Edinburgh, Scotland, U.K, 2012.

71.Intel Threading Building Blocks. URL:

https://www.threadingbuildingblocks.org/ (дата обращения: 25.07.2014).

72.OpenBLAS. URL: http://www.openblas.net/ (дата обращения: 25.07.2014).

73.Стронгин Р. Г., Гергель В. П., Гришагин В. А., Баркалов К. А. Параллельные вычисления в задачах глобальной оптимизации: Монография/ Предисл.: В. А. Садовничий. - М.: Издательство Московского университета, 2013. - 280 с.

74.FFTW. URL: http://www.fftw.org/ (дата обращения: 25.07.2014).

75.Leo Breiman. Random Forests. Machine Learning 45 (1): 5-32. 2001.

76.Press William H., Teukolsky Saul A., Vetterling William T., Flannery B. P. Section 16.5. Support Vector Machines. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press, 2007.

77.Broomhead D. S., Lowe David. Multivariable functional interpolation and adaptive networks // Complex Systems 2, 1988. 321-355.

78.Rasmussen C. E., Williams C. K. I. Gaussian Processes for Machine Learning. The MIT Press, 2006.

79.Дрейпер Н., Смит Г. Прикладной регрессионный анализ. М.: Издательский дом «Вильямс», 2007.

80.Marcus G. F. Rethinking eliminative connectionism // Cognitive Psychology, 37, 1998. 243-282.

81.Pin - A Dynamic Binary Instrumentation Tool. URL: https: //software. intel. com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool (дата обращения: 25.07.2014).

82.Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация: Учебное пособие. Нижний Новгород: Изд-во ННГУ, 2007. 489 с.

83.Гришагин В.А. Об условиях сходимости для одного класса алгоритмов глобального поиска. В сб.: Тезисы докл. III Всес. семинара «Численные методы нелинейного программирования». - Харьков, 1979. С. 82-84.

84.Karipis G. METIS. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices. Version 5.0. // Technical report, University of Minnecota, Department of Computer Science and Engeneering. - 2011. URL: [http: //glaros. dtc.umn.edu/gkhome/fetch/sw/metis/manual .pdf].

85.Pirova A., Meyerov I. MORSy - a new tool for sparse matrix reordering // An International Conference on Engineering and Applied Sciences Optimization (Kos Island, Greece, 4-6 June 2014). (abstract is accepted).

86.Старостин Н.В., Филимонов А.В. Разработка и реализация параллельного многоуровневого алгоритма равномерного разбиения нераспределенного графа. Сборник трудов HPC 2013. 243-248.

87.Галатенко В.А. Программирование в стандарте POSIX. Курс лекций. Учебное пособие. Часть 1. Интернет-Университет Информационных Технологий, 2004. 560.

ПРИЛОЖЕНИЕ 1. MKL ВЕРСИЯ УМНОЖЕНИЯ МАТРИЦ

#include "mkl.h" #include "stdio.h" #include "windows.h"

#pragma comment(lib,"C:/Program

Files/Intel/MKL/10.2.6.037/ia32/lib/libguide.lib")

#pragma comment(lib,"C:/Program

Files/Intel/MKL/10.2.6.037/ia32/lib/mkl_core.lib")

#pragma comment(lib,"C:/Program

Files/Intel/MKL/10.2.6.037/ia32/lib/mkl_intel_thread.lib")

#pragma comment(lib,"C:/Program

Files/Intel/MKL/10.2.6.037/ia32/lib/mkl_intel_c.lib")

int main(int argc, char* argv[]) {

float *a, *b, *c;

LARGE_INTEGER start, finish, freq;

if(argc!=2) {

printf("Usage: mmult <size>"); return 1;

}

int size = atoi(argv[1]);

a = (float*) malloc ( size b = (float*) malloc ( size c = (float*) malloc ( size

* size * sizeof float

* size * sizeof float

* size * sizeof float

for(int i=0; i<size*size; i++) {

a[i]=rand()/36000.f; b[i]=rand()/36000.f; c[i]=0.;

}

QueryPerformanceFrequency(&freq); QueryPerformanceCounter(&start);

char nt = 'N'; float alpha = 1.0; float beta = 0.0;

sgemm(&nt, &nt, &size, &size, &size, &alpha, b, &size, a, &size, &beta, c, &size);

QueryPerformanceCounter(&finish);

printf("Time = %f\n", (finish.QuadPart-start.QuadPart) /

(float)freq.QuadPart);

free(a); free(b); free(c);

return 0;

}

ПРИЛОЖЕНИЕ 2. CUBLAS ВЕРСИЯ УМНОЖЕНИЯ МАТРИЦ

#include "cublas.h" #include "stdio.h" #include "windows.h"

#pragma comment(lib,"cublas.lib")

int main(int argc, char* argv[]) {

float *a, *b, *c; float *_a, *_b, *_c; LARGE_INTEGER start, finish, freq;

if(argc!=2) {

printf("Usage: mmult <size>"); return 1;

}

int size = atoi(argv[1]);

a = (float*) malloc ( size * size * sizeof ( float ) ); b = (float*) malloc ( size * size * sizeof ( float ) ); c = (float*) malloc ( size * size * sizeof ( float ) );

for(int i=0; i<size*size; i++) {

a[i]=rand()/36000.f; b[i]=rand()/36000.f; c[i]=0.;

}

QueryPerformanceFrequency(&freq); QueryPerformanceCounter(Sstart);

cublasStatus status;

cublasInit();

status = cublasAlloc ( size* size, sizeof(float), (void**)& a); status = cublasAlloc ( size * size, sizeof(float), (void**)& b); status = cublasAlloc ( size * size, sizeof(float), (void**)& c);

cublasSetMatrix ( size, size, sizeof(float), (void *) a, size, (void *) a, size);

cublasSetMatrix ( size, size, sizeof(float), *) b, size);

cublasSetMatrix ( size, size, sizeof(float), *) _c, size);

QueryPerformanceCounter(&start);

char nt = 'N'; float alpha = 1.0; float beta = 0.0;

cublasSgemm(nt, nt, size, size, size, alpha, beta, _c, size);

cublasGetMatrix ( size, size, sizeof(float), (void *) c, size );

QueryPerformanceCounter(&finish);

printf("Time = %f\n", (finish.QuadPart-start.QuadPart) /

(float)freq.QuadPart);

cublasFree( a); cublasFree( b); cublasFree( c);

cublasShutdown();

free(a); free(b); free(c);

return 0;

}

void *) b, size, (void void *) c, size, (void

b, size, _a, size, void *) _c, size,

ПРИЛОЖЕНИЕ 3.

ФРАГМЕНТЫ ИСХОДНЫХ ТЕКСТОВ ПРОГРАММНОГО КОМПЛЕКСА

#include "MmtKernellnner.h" #include "KernelUtils.h" #include "Kernel.h" #include "Logger.h" #include "Time.h" #include "Statistics.h" #include "ExecutionPredictor.h" #include "MmtExceptions.h" #include <string> #include <algorithm>

GarbageCollector MmtKernelInner::gGlobalGc;

bool MmtKernelInner::GetConverters(MetaVar &in, MetaVar &out,

vector<ConverterId> &convs) {

VarHash inHash = in.GetHash(); VarHash outHash = out.GetHash();

if(inHash == outHash) return true;

return KernelUtils::GetConverter(inHash, outHash, convs);

}

string ToString(ConverterPlan &conv) {

string rez;

for(vector<ConverterId>::iterator it = conv.converters.begin(); it

!= conv.converters.end(); ++it) {

rez += to string(*it) + " ";

}

return rez;

}

int MmtKernelInner::PredictPlanExecutionTime(Plan &plan, double &time)

double predictTime; int status = MMT_OK;

time = 0.;

//Predict in converters time

for(vector<ConverterPlan>::iterator conv =

plan.inConverters.begin(); conv != plan.inConverters.end(); conv++) {

status = PredictConverterExecutionTime(&(*conv), predictTime);

if(status != MMT_OK) {

LOGGER WARNING(logger, (string("Predict error for converter with id = (")+ToString(*conv) + ")").c_str()) return MMT_PREDICTION_ERROR;

}

time += predictTime;

}

//Predict implementation time

status = PredictImplementationExecutionTime(plan.implementation, predictTime);

if(status != MMT_OK) {

LOGGER_WARNING(logger, (string("Predict error for

")+KernelUtils::GetModuleForAdapter(plan.implementation)).c str()) return MMT_PREDICTION_ERROR;

}

time += predictTime; //Predict out converters time

for(vector<ConverterPlan>::iterator conv =

plan.outConverters.begin(); conv != plan.outConverters.end(); conv++) {

status = PredictConverterExecutionTime(&(*conv), predictTime);

if (status != MMT_OK) {

LOGGER WARNING(logger, (string("Predict error for converter with id = (")+ToString(*conv) + ")").c_str()) return MMT_PREDICTION_ERROR;

}

time += predictTime;

}

return MMT OK;

// Select plan with minimum converters

Plan* MmtKernellnner::SelectPlanAlternative() {

Plan *selectedPlan = NULL; int minConvsCount = LONG_MAX;

for(vector<Plan>::iterator it = plans.begin(); it != plans.end();

it++) {

int convsCount = 0;

for(vector<ConverterPlan>::iterator conv = it'

>inConverters.begin(); conv != it->inConverters.end(); conv++) convsCount += conv->converters.size();

for(vector<ConverterPlan>::iterator conv = it-

>outConverters.begin(); conv != it->outConverters.end(); conv++) convsCount += conv->converters.size();

LOGGER_INFO(logger, (string("Plan \"")+

KernelUtils::GetModuleForAdapter(it->implementation) + "\" need " + to string(convsCount)+ " conversions").c str())

if(minConvsCount > convsCount) {

minConvsCount = convsCount; selectedPlan = &(*it);

}

}

return selectedPlan;

}

Plan* MmtKernelInner::SelectPlan() {

Plan *selectedPlan = NULL;

double minTime = std::numeric limits<double>::infinity();

for(vector<Plan>::iterator it = plans.begin(); it != plans.end();

it++) {

double time; int status;

status = PredictPlanExecutionTime(*it, time);

if (status != MMT_OK) {

LOGGER WARNING(logger,"Runtime prediction error. Try alternative prediction.")

return SelectPlanAlternative();

}

LOGGER_INFO(logger, (string("Plan \"") +

KernelUtils::GetModuleForAdapter(it->implementation) + "(" +

to string(it->implementation->GetId()) +

")\" predicted execution time " + to string(time)+ s").c_str())

if(minTime > time) {

minTime = time; selectedPlan = &(*it);

}

}

return selectedPlan;

}

bool MmtKernelInner::CreateConvertPlan(MetaVar* src, MetaVar* dst, vector<ConverterPlan> &inConverters, vector<ConverterPlan>

&outConverters, set<Ident> &inUsed, set<Ident> &outUsed) {

if(src == 0)

throw MmtException("CreateConvertPlan: src == 0");

if(src->specs.size() != 0) {

for(TypeSpecifications::iterator it = src->specs.begin(); it !=

src->specs.end(); it++) {

MetaVar* src2=0, *dst2 = 0;

src2 = src->GetVar(it->second);

if(dst->specs.find(it->first) != dst->specs.end()) dst2 = dst->GetVar(dst->specs[it->first]);

if (src2 == 0 || dst2 == 0) continue; // return false

if(CreateConvertPlan(src2,dst2,inConverters,outConverters, inUsed, outUsed) == false) return false;

}

}

if(src == 0)

throw MmtException("CreateConvertPlan: dst == 0");

if(dst->directions == MMT_IN || dst->directions == MMT_INOUT) {

ConverterPlan pIn; pIn.dst=dst; pIn.src=src;

if(GetConverters(*src,*dst,pIn.converters) == false)

return false; inConverters.push back(pIn);

inUsed.insert(inUsed.end(),src->GetName());

}

if(dst->directions == MMT_OUT || dst->directions == MMT_INOUT) {

ConverterPlan pOut; pOut.dst=src; pOut.src=dst;

if(GetConverters(*dst,*src,pOut.converters) == false)

return false; outConverters.push back(pOut);

outUsed.insert(outUsed.end(),dst->GetName());

}

return true;

}

int MmtKernelInner::PerformConvertion(vector<ConverterPlan> &convs,

GarbageCollector &gc) {

for(vector<ConverterPlan>::iterator it = convs.begin(); it !=

convs.end(); it++) {

MetaVar *src = it->src; MetaVar *dst = it->dst;

if(it->converters.size() == 0) {

//copy var

dst->value = src->value;

else if (it->converters.size() == 1) {

int conv = it->converters[0]; int status;

ConverterStatistics stat; TimeStamp s, f;

Converter *c = KernelUtils::GetConverter(conv);

if(c == NULL)

return MMT_CONVERTER_NOT_FOUND;

stat.converterId = c->GetId(); c->ExtractParams(src, dst, stat.parameters);

c->ExtractAsymptoticParams(src, dst,

stat.asymptoticParameters);

GetTime(s);

status = c->Apply(src, dst, gc); GetTime(f);

if(status != CONVERTER_OK) {

LOGGER_ERROR(logger, ("Converter failed from " + src->type + " to " + src->type).c str())

return MMT_CONVERTER_ERROR;

}

stat.time = GetTimeSpan(s,f);

gStatisticsWriter.AddConverterStatistics(stat);

}

else {

int tmpCount = it->converters.size() - 1; MetaVar **tmpVars; VarsContainer *tmpContainers;

tmpContainers = new VarsContainer[tmpCount]; tmpVars = new MetaVar*[tmpCount+2];

tmpVars[0] = src; tmpVars[tmpCount+1] = dst;

for(int i=1; i<tmpCount+1; ++i)

tmpVars[i] = new MetaVar(tmpContainers[i-1],"");

for(int i = 0; i < it->converters.size(); ++i) {

int conv = it->converters[i]; int status;

ConverterStatistics stat; TimeStamp s, f;

Converter *c = KernelUtils::GetConverter(conv); if (c == NULL)

return MMT_CONVERTER_NOT_FOUND;

if(i != tmpCount) {

VarsContainer tmpFromContainer;

MetaVar tmpFromVar(tmpFromContainer, "");

c-

>GetTypes(tmpFromVar,tmpFromContainer,*tmpVars[i+1],tmpContainers[i],g c);

}

stat.converterId = c->GetId();

c->ExtractParams(tmpVars[i], tmpVars[i+1], stat.parameters); c->ExtractAsymptoticParams(tmpVars[i], tmpVars[i+1],

stat.asymptoticParameters);

GetTime(s);

status = c->Apply(tmpVars[i], tmpVars[i+1], gc); GetTime(f);

if(status != CONVERTER_OK) {

LOGGER ERROR(logger, ("Converter failed from " + src->type + " to " + src->type).c str())

return MMT_CONVERTER_ERROR;

}

stat.time = GetTimeSpan(s,f);

gStatisticsWriter.AddConverterStatistics(stat);

}

for(int i=1; i<tmpCount+1; ++i)

delete tmpVars[i]; delete[] tmpVars; delete[] tmpContainers;

}

return MMT_OK;

}

int MmtKernelInner::PerformPlan(Plan &plan) {

GarbageCollector localGc; GarbageCollector *gc; plan.implementation->Clean(); int status;

if(a.gcMode == LOCAL_MEM_RELEASE)

gc= &localGc; else

gc = &gGlobalGc; PerformConvertion(plan.inConverters, *gc); //Stat begin

ImplementationStatistics stat; TimeStamp s, f;

stat.moduleName

KernelUtils::GetModuleName(KernelUtils::GetModuleForAdapter(plan.imple mentation));

stat.implementationId = plan.implementation->GetId();

plan.implementation->ExtractParams(stat.parameters); plan.implementation->ExtractAsymptoticParams(stat.asymptoticParameters);

GetTime(s);

if(plan.implementation->Apply(*gc) != 0)

return MMT_IMPLEMENTATION_ERROR; GetTime(f);

stat.time = GetTimeSpan(s,f);

gStatisticsWriter.AddImplementationStatistics(stat); //Stat end

PerformConvertion(plan.outConverters, *gc); return MMT_OK;

}

int GetConvertersCount(vector<ConverterPlan> &convs) {

int sum = 0;

for(vector<ConverterPlan>::iterator conv = convs.begin(); conv != convs.end(); conv++)

sum += conv->converters.size();

return sum;

}

int MmtKernelInner::CreatePlans(bool printErrors) {

VarsContainer &vars = a.vars; vector<Implementation*> implementations; vector<Plan> allPlans, preferedPlans;

KernelUtils::GetAdapters(a.name, implementations);

if(implementations.size() == 0)

return MMT_IMPLEMENTATION_NOT_FOUND;

for(int i=0; i<implementations.size(); i++) {

Plan plan;

plan.implementation = implementations[i];

if(plan.implementation->IsWorkingState() == false) continue;

set<Ident> inUsed, outUsed;

bool isCorrect = true;

for(int j=0; j<implementations[i]->params.size();j++) {

MetaVar* src = a.vars[a.params[j]];

MetaVar* dst = implementations[i]->vars[implementations[i]->params[j]];

if(CreateConvertPlan(src, dst, plan.inConverters,

plan.outConverters, inUsed, outUsed) == false) {

isCorrect = false;

if(printErrors)

printf("No converter for \"%s\" from %s to %s\n",src->GetName().c str(), src->type.c str(), dst->type.c str());

LOGGER_WARNING(logger, (string("No converter for ") + src->GetName() + string(" from ") + src->type +" ("+ src->GetFullType()+ string(") to ") + dst->type +" ("+dst->GetFullType() + ")").c_str())

break;

}

}

if(isCorrect) {

LOGGER_INFO(logger, (string("Converters

std::to string(GetConvertersCount(plan.inConverters)) to string(GetConvertersCount(plan.outConverters)) +

string(") for module

KernelUtils::GetModuleForAdapter(plan.implementation) ")).c_str())

allPlans.push back(plan);

(") +

+ string(", ") + \"") +

+ string("\"

string moduleName =

KernelUtils::GetModuleName(KernelUtils::GetModuleForAdapter(plan.imple mentation));

transform(moduleName.begin(), moduleName.end(),

moduleName.begin(), toupper);

string preferedName = preferedModule;

transform(preferedName.begin(), preferedName.end(),

preferedName.begin(), toupper);

if(moduleName.find(preferedName) != string::npos)

{

if(preferedId == plan.implementation->GetId()) //Use only one!

{