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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова Факультет вычислительной математики и кибернетики

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

'Г

ЗОРИН Даниил Александрович

СИНТЕЗ АРХИТЕКТУР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ С УЧЕТОМ ОГРАНИЧЕНИЙ НА ВРЕМЯ ВЫПОЛНЕНИЯ И ТРЕБОВАНИЙ К НАДЕЖНОСТИ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

005552660

МОСКВА-2014

005552660

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

Научный руководитель: кандидат технических наук,

ведущий научный сотрудник Костенко Валерий Алексеевич.

Официальные оппоненты: доктор технических наук,

профессор Топорков Виктор Васильевич; кандидат технических наук, Гончар Дмитрий Русланович.

Ведущая организация:

Научно-исследовательский институт вычислительных комплексов им. М.А. Карцева (НИИВК)

Защита диссертации состоится 10 октября 2014 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М. В.Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ имени М. В. Ломоносова, с текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://www.cmc.msu.ru в разделе «Наука» - «Работа диссертационных советов» - «Д 501.001.44».

Автореферат разослан " ^ " _20№г.

Ученый секретарь

диссертационного совета Д 501.001.44 в.н.с.

В.А. Костенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

К бортовым вычислительным система реального времени (ВСРВ) на стадии проектирования кроме жестких ограничений на время выполнения программ и требований надежности также предъявляются повышенные требования к мас-

1

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

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

• Наличие одновременно двух ограничений (время выполнения программы и надежность вычислительной системы);

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

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

Цель работы

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

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

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

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

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

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

Основные результаты диссертационной работы следующие:

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

2

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

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

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

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

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

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

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

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

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

Методы исследования

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

Апробация работы

Результаты работы докладывались на научно-исследовательском семинаре кафедры автоматизации систем вычислительных комплексов (АСВК) факультета ВМК МГУ, на научном семинаре лаборатории вычислительных комплексов кафедры АСВК, а также на следующих конференциях:

1. XVII Международная молодежная конференция студентов, аспирантов и молодых ученых (Москва, 2010 г.)

2. XVIII Международная молодежная конференция студентов, аспирантов и молодых ученых (Москва, 2011 г.)

3. 1 Ith IFAC/IEEE International Conference on Programmable Devices and Embedded Systems (Брно, Чехия, 2012 г.)

4. Международная конференция «Параллельные вычисления и задачи управления» (Москва, 2012 г.)

5. XX Международная молодежная конференция студентов, аспирантов и молодых ученых (Москва, 2013 г.)

6. 7th Spring/Summer Young Researchers' Colloquium on Software Engineering (Казань, 2013 г.)

7. VII Moscow International Conference on Operations Research (Москва, 2013 г.)

8. 3rd International Conference on Operations Research and Enterprise Systems (Анже, Франция, 2014 г.)

Работа выполнена при поддержке стипендии Президента Российской Федерации.

Публикации

По теме диссертации опубликовано 16 печатных работ, в том числе работы в журналах «Известия РАН. Теория и системы управления», «Вестник МГУ. Вычислительная математика и кибернетика», «Прикладная информатика» входящих в перечень ведущих рецензируемых научных журналов ВАК РФ, а также 2

работы, индексируемых системой Scopus. Список работ приведен в конце автореферата.

Структура и объем диссертации

Диссертация состоит из введения, пяти глав, заключения, списка литературы и четырех приложений. Объем работы - 103 страницы, с приложениями - 133 страницы. Список литературы содержит 109 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность диссертационной работы и дано краткое описание задачи.

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

В разделе 1.3 вводятся используемые механизмы обеспечения отказоустойчивости, позволяющие повышать надежность системы. Резервирование процессоров заключается в том, что к некоторому процессору в системе добавляется дублирующий процессор, на котором выполняются те же задания. В этом случае система отказывает, только если отказывают оба процессора. Дублирующий процессор работает в режиме горячего резерва, то есть принимает все те же данные и выполняет те же вычисления, что и основной, но передает данные только в случае отказа основного. Обосновывается необходимость выполнять на дублирующем процессоре все задания в том же порядке, что и на основном. При N-версионном программировании создается N версий реализации какого-либо задания. Число версий всегда нечетно (обычно 3 либо 5), и результаты подвергаются простому сравнению, итоговым результатом объявляется тот, который выдали больше половины версий. Таким образом, при отказе не более чем (N + 1)/2 версий отказа не происходит. Разные версии обычно разрабатываются разными

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

В разделе 1.4 вводится понятие расписания.

Определение 1. Расписание (для системы с резервированием и многоверси-онным программированием) определяется как пара (5,0), где $ - множество четверок (у,к,т,п), где V 6 V,к 5 Кегх(^),тбМ.пеЯ, такое, что Vv еУЭк е Уег5(у): 35 = (у^к^т^щ) £ 5: = V, к1 = к]

~ (у1,китип1') е 5,Уз, = (г?у,/с;-,т.¡,П]) 6 5: (г^ = V] А /с£ = кр =>5^ 5,;

= (и(,/с(,т(,п() = (у6 5: Ф Ь т1 — т]) => п(

й - мультимножество, состоящее из элементов множества процессоров М. Общее число процессоров в системе М(5) = |£>|. Оир(т() - кратность процессора Ш[ в мультимножестве О.

Содержательно 17 и к определяют задание и номер его версии, тип задают соответственно привязку к процессору и порядок выполнения для каждой версии каждого задания. Ограничения, записанные выше логическими условиями, означают, что 1) у каждого задания хотя бы одна версия должна присутствовать в расписании, 2) каждая версия каждого задания может присутствовать в расписании только один раз, 3) у всех заданий, назначенных на один процессор, разные номера. Мультимножество О задает резервируемые процессоры.

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

Определение 2. Расписание 5 является корректным, если его граф является ациклическим.

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

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

Определение 4. Время выполнения t(S) - это максимальное значение времени завершения задания во временной диаграмме.

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

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

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

fR(S,v):S,v -» К

Определение 6. Надежность системы R(S) - это следующая величина:

Я(5) = J~[ (1 - (1 - P(.rni))DuHm°) ■ ¡~| fRtf.Vi).

m<EM (vi.ki.mt,nt)es

Первый множитель соответствует совокупной надежности процессоров. Если P(mj) - вероятность безотказной работы, то 1 — P(mf) - вероятность отказа. Вероятность отказа всех Dup(mf) дублирующих процессоров есть (1 — P(mi))Dup(mt>. Соответственно, надежность группы дублирующих друг друга процессоров равна 1 — (1 — P(mi))Duptm,i. Второй множитель соответствует совокупной надежности всех заданий с учетом использующихся версий.

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

В разделе 1.7 приводится формальная постановка задачи. Пусть заданы программа G, td,r - срок, к которому программа должна быть выполнена, и Rd,r -надежность, которой должна обладать система. Пусть также фиксированы функция интерпретации ft (5) и функция оценки надежности задания fR(S, р). Необходимо построить расписание 5 из множества корректных расписаний 5, для которого требуется минимальное количество процессоров, и при этом выполняются ограничения на время выполнения программы и требования к надежности системы:

min M(5)

ses t(S) < tdir ß(5) > Rdir

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

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

В разделах 2.2-2.6 рассматриваются такие методы решения оптимизационных задач, как полный перебор, метод ветвей и границ, жадные алгоритмы, алгоритмы имитации отжига и генетические алгоритмы. Поскольку ни один из существующих алгоритмов не подходит к рассматриваемой задаче в исходном виде, необходимо выбрать подход для построения такого алгоритма. Методы полного перебора и ветвей и границ неприменимы из-за чрезмерно высокой вычислительной сложности, поэтому остается выбор из трех методов: жадные алгоритмы, алгоритмы имитации отжига и генетические алгоритмы. Жадные алгоритмы работают быстро, но неприемлемы по точности, в общем случае их результат может быть очень далек от оптимального. Генетические алгоритмы потенциально позволяют получать более точные результаты, но в условиях необходимости вычислять время выполнения расписания многократно на каждой итерации требуют очень много времени на работу. Метод имитации отжига лишен этих недостатков, поэтому было решено использовать в качестве основы его.

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

В разделе 3.1 описана общая схема алгоритма имитации отжига.

Шаг 1. Задать начальное корректное решение (50,О0) ES и считать его текущим вариантом решения ((5, D) = (50, Do)).

Шаг 2. Установить начальную температуру Т0, приняв ее текущей (Т = Т0).

Ш а г 3. Применить операции преобразования решения к текущему решению (5,£)) и получить новый корректный вариант решения (5', Д') е 5, если это решение является лучшим из ранее найденных решений, то запомнить его.

Шаг 4. Найти изменение функционала оценки качества решения ЛР = ру, О') — 0). Если АГ <0 (решение улучшилось), то новый вариант решения считать текущим ((5,0) = (5', О')). Если Д/^ > 0 (решение ухудшилось), то принять с вероятностью р = в качестве текущего решения новый ва-

риант решения (5', О').

Шаг 5. Повторить заданное число раз шаги 3 и 4 без изменения текущей температуры.

Шаг 6. Если критерий останова выполнен, то завершение работы алгоритма.

Шаг 7. Понизить текущую температуру в соответствии с выбранным законом и перейти к шагу 3.

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

Утверждение 1. Замкнутость системы операций. Если (5,0) - корректное расписание, то после применения любой из операций также получается корректное расписание.

Утверждение 2. Для каждой операции, переводящей расписание А в расписание В, существует обратная операция, переводящая расписание В в расписание А.

Утверждение 3. Полнота системы операций. Если (5], 0{), (52, 02) ~~ К0Р" ректные расписания, то существует последовательность операций, приводящая (51( £>!) к (52,02), такая, что все промежуточные расписания корректны.

В разделе 3.3 описаны стратегии применения операций на шаге 3 алгоритма. Стратегия определяет, какая из операций применяется на текущем шаге и с какими параметрами. Для операции переноса задания предложены три основных стратегии: стратегия уменьшения задержек, стратегия заполнения простоев и смешанная стратегия. Также описана случайная стратегия, с которой сравниваются остальные. Стратегия уменьшения задержек (стратегия Б1) основана на

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

В разделе 3.4 определяются условия перехода и останова. Приводятся различные законы понижения температуры на шаге 7 алгоритма.

В разделе 3.5 дается оценка вычислительной сложности одной итерации алгоритма. Она составляет 0(ЛГ ■ Е) + О (/С), где N - число заданий, Е - число ребер в графе программы, О (/С) - сложность вычисления функции интерпретации.

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

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

г

Теорема 1. Пусть значения температуры таковы, что £к > [ ^^ Г > О, к0 > 2. Тогда цепь Маркова, соответствующая алгоритму имитации отжига, сходится к стационарному распределению вида q^ = > где 3 — множество

оптимальных решений.

В разделе 4.2 вводятся метрики в пространстве расписаний, используемые в дальнейшем в экспериментальном исследовании. Метрика ¿(Л, В) определяется как длина минимальной цепочки операций, переводящей расписание А в расписание В. Доказано следующее утверждение.

Утверждение 4. S, L{A, В) - метрическое пространство.

Так как вычисление метрики L(A,B~) имеет экспоненциальную сложность, вводится аппроксимирующая метрика Н(Д В). Эта метрика определяется с помощью понятия перестановки. Пусть заданы два расписания Л и В, использующие равное число процессоров без учета резервных. Пусть между процессорами в первом и втором расписании установлено биективное соответствие /(т).

Определение 7. Если в расписании А задание (у, к) расположено на процессоре тди а в расписании В - на процессоре тВ2, таком что тВ2 ^ f(mA1), то будем называть это перестановкой для (у, к).

Определение 8. Если в расписании А задание (v, к) расположено на процессоре тЛ1, а в расписании В - на процессоре тв2 , таком что тВ2 = f(mAl), но порядок (у, к) относительно других заданий не совпадает, то будем также называть перестановкой для {у, к).

Определение 9. Если тА1 и f(mA1) имеют число резервов, отличающееся на £, то будем говорить, что задано i перестановок для тА1.

Определение 10. Если в одном из расписаний А, В есть пара версий (у, ki), (v, к2), а в другом ее нет, то будем говорить, что задана перестановка для версий (у, fei), (v, к2).

Обозначим через Hf(A,B) общее число перестановок для двух расписаний при условии, что соответствие между процессорами задается функцией /.

Определение 11. Н(А,В) — argminfHf(A,B).

Утверждение 5. 5, Н(А, В) - метрическое пространство.

Значение метрики Н(А,В) может быть вычислено алгоритмом с полиномиальной сложностью.

Связь между двумя метрики задается следующими соотношениями.

Утверждение 6. Н(А,В) < 1{А,В).

Утверждение 7. И (А, В) > L(A,B)/2.

В разделе 4.3 описано экспериментальное исследование алгоритма. В подразделе 4.3.1 алгоритм исследуется на случайно созданных модельных данных. Приведена классификация исходных данных по таким параметрам как N - число заданий, Q — отношение между количеством ребер и количеством вершин в графе программы, отношение директивного срока и оценки нижней границы времени выполнения программы, а также отношение требуемой надежности и оценки верхней границы надежности. При исследовании использовался математический

11

аппарат проверки статистических гипотез, кратко описанный в данном подразделе. Для значений размерности выборки и уровня значимости л = 100, Ь = 0.05 проверялись статистические гипотезы следующего вида (здесь - значение целевой функции (количество процессоров), получаемое алгоритмом с использованием стратегии 57.):

• Результат стратегии 51 лучше результатов стратегии 5/ при любых

• При любых ЯЛ1Г и (} выполняется некоторое соотношение на разницу результатов: /?е5г — КеБ^ < с;

• Локальная оптимальность: если А - расписание, построенное алгоритмом, то УВ:Ь(А,В) = 1: М(В) > М(А), то есть результат, найденный алгоритмом, не может быть улучшен применением одной операции.

Следующие гипотезы имеют место:

• Результат стратегий и БЗ лучше результатов стратегий Э2 и при любых и (}■. > Не52,Че5г > йе50,Ке53 > Яе$2, Яев3 > Яез0\

• При любых ЯШг и (}: Дех3 - Дех! < 1;

• Локальная оптимальность алгоритма (имеет место в 100% случаев на рассмотренных выборках).

В подразделе 4.3.2 приведены результаты исследования алгоритма на совместимых исходных данных. Описан алгоритм создания графа программы, для которого известно оптимальное расписание, и результаты, полученные алгоритмом, сравниваются с оптимальным расписанием по метрике из раздела 4.2. Различия в работе стратегий проявляются с ростом значения (}. При малых () различия в работе стратегий не проявляются, тогда как с ростом <2 стратегия 83 показывает лучшие результаты. Кроме того на рассматриваемых в этом подразделе примерах стратегия Э2 работает лучше, чем на случайно созданных исходных данных.

В подразделе 4.3.3 сравниваются различные законы понижения температуры. Сделан вывод о том, что смешанный закон понижения температуры в среднем позволяет получать более точные результаты, чем законы Больцмана и Ко-ши, однако это преимущество невелико, в то время как закон Больцмана дает

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

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

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

• Наличие графического интерфейса пользователя;

• Возможность ввода исходных данных как из заранее созданного файла, так и с использованием графического интерфейса;

• Возможность запускать алгоритм, менять его настройки, визуализировать на экране результаты;

• Возможность править результаты алгоритма в ручном режиме. При изменении решения автоматически должна проверяться его корректность;

• Возможность задавать различные модели вычислительной системы для оценки времени и различные методики расчета надежности;

• Возможность создавать специализированные подсистемы для построения вычислительных систем для конкретных практических задач;

• Возможность генерации кода процедур обмена.

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

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

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

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

В Приложении А описаны различные схемы оценки надежности вычислительных систем.

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. Zorin D. A., Kostenko V. A. Job Shop Scheduling and Co-design of Real-Time Systems with Simulated Annealing // Proceedings of the 3rd International Conference on Operations Research and Enterprise Systems. Angers, France: ESEO. -2014. - P. 17-26.

2. Зорин Д. А. Оценка сходимости алгоритма имитации отжига для задачи построения многопроцессорных расписаний // Вестник МГУ. Вычислительная математика и кибернетика. - 2014. — № 2. - С. 53-59.

3. Zorin D. A., Kostenko V. A. Co-design of Real-time Embedded Systems under Reliability Constraints // IFAC Proceedings Volumes (IFAC-PapersOnline) 11 (PART 1).-2013.-P. 424-428.

4. Зорин Д. А., Костенко В. А. Алгоритм синтеза архитектуры вычислительной системы реального времени с учетом требований к надежности // Известия РАН. Теория и системы управления. -2012. — № 2. - С. 76-83.

5. Зорин Д. А. Инструментальная система структурного синтеза вычислительных систем реального времени и построения расписаний // Программные системы и инструменты. Тематический сборник № 13. М.: Изд-во факультета ВМиК МГУ. - 2012. - С. 117-124.

6. Волканов Д.Ю., Зорин Д. А. Исследование применимости моделей оценки надежности для разработки программного обеспечения с открытым исходным кодом // Прикладная информатика. -2011. -№2. - С. 26-32.

7. Зорин Д. А. Способ представления и преобразования расписаний в итерационных алгоритмах структурного синтеза вычислительных систем реального времени // Программные системы и инструменты. Тематический сборник № 12. М.: Изд-во факультета ВМиК МГУ. - 2011. - С. 163-171.

8. Волканов Д. Ю., Зорин Д. А. Исследование применимости моделей оценки надежности для разработки программного обеспечения с открытым исходным кодом // Программные системы и инструменты. Тематический сборник № 10. М.: Изд-во факультета ВМиК МГУ. - 2009. - С. 125-134.

9. Zorin D. A. Convergence and Accuracy Measurement of Scheduling on Multiprocessors with Simulated Annealing // VII Moscow International Conference on Operations Research (ORM2013): Proceedings, Vol. 1. Moscow: MAK.S Press.-2013.-P. 94-97.

10. Zorin D. A. Scheduling Signal Processing Tasks for Antenna Arrays with Simulated Annealing // Proceedings of the 7th Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE). Kazan, Russia: Kazan National Research Technical University. -2013. - P. 122-127.

11. Зорин Д. А. Преобразование расписаний в итерационных алгоритмах структурного синтеза вычислительных систем // XX Международная молодежная конференция студентов, аспирантов и молодых ученых; секция «Вычислительная математика и кибернетика»: Сб. тезисов. М.: Издательский отдел факультета ВМиК МГУ; МАКС Пресс. -2013. - С. 24-25.

12. Зорин Д. А. Сравнение различных стратегий применения операций в алгоритме имитации отжига для задачи построения расписаний для многопроцессорных систем // Параллельные вычисления и задачи управления

РАСО'2012. Шестая международная конференция, Москва, 24-26 окт. 2012 г., Труды: в 3 т. М.: ИПУ РАН. - 2012. -Том 1. - С. 278-291.

13. Zorin D. A., Kostenko V. A. Co-design of Real-time Embedded Systems under Reliability Constraints //Proceedings of 11th IF AC/IEEE International Conference on Programmable Devices and Embedded Systems (PDeS). Brno, Czech Republic: Brno University of Technology. - 2012. - P. 392-396.

14. Зорин Д. А. Метод синтеза архитектуры вычислительной системы реального времени при ограничениях на надежность // Сборник тезисов лучших дипломных работ 2011 года. М.: Издательский отдел факультета ВМиК МГУ; МАКС Пресс. - 2011. - С. 99-100.

15. Зорин Д. А. Метод синтеза архитектуры вычислительной системы реального времени при ограничениях на надежность // XVIII Международная молодежная конференция студентов, аспирантов и молодых ученых; секция «Вычислительная математика и кибернетика»: Сб. тезисов. М.: Издательский отдел факультета ВМиК МГУ; МАКС Пресс. - 2011. - С. 141142.

16. Зорин Д. А. Исследование применимости моделей оценки надежности для разработки программного обеспечения с открытым исходным кодом // XVII Международная молодежная конференция студентов, аспирантов и молодых ученых; секция «Вычислительная математика и кибернетика»: Сб. тезисов. М.: Издательский отдел факультета ВМиК МГУ; МАКС Пресс.-2010.-С. 121-122.

Подписано в печать: 01.07.14

Объем: 1,0 п.л. Тираж: 100 экз. Заказ № 543 Отпечатано в типографии «Реглет» г. Москва, Ленинский проспект, д.2 (495) 978-66-63, www.reglet.ru