ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2012, № 3, с. 76-83
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 519.68
АЛГОРИТМ СИНТЕЗА АРХИТЕКТУРЫ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ С УЧЕТОМ ТРЕБОВАНИЙ К НАДЕЖНОСТИ
© 2012 г. Д. А. Зорин, В. А. Костенко
Москва, МГУ Принята в редакцию 22.09.11 г., после доработки 01.11.11 г.
Рассматривается задача построения вычислительной системы реального времени с минимальным числом процессоров. При этом требуется соблюдение директивных сроков на время выполнения программы, а также должны быть выполнены требования к надежности системы, которые подразумевают, что система должна выдерживать как аппаратные, так и программные отказы. Приведена формальная постановка данной задачи, предложен метод ее решения с использованием итерационного алгоритма построения расписания, основанного на методе имитации отжига, и проведено экспериментальное исследование предложенного алгоритма.
Введение. В [1, 2] предложен подход к построению алгоритмов на основе схемы имитации отжига для решения задачи построения расписания с минимальным временем выполнения на заданном числе процессоров. Алгоритмы на основе схемы имитации отжига последовательно изменяют расписание с целью уменьшения времени его выполнения. Основными проблемами, которые необходимо решить для построения алгоритма, является введение системы операций преобразования расписания и разработка стратегии применения этих операций на каждой итерации алгоритма. Система преобразования операций должна допускать существование цепочки операций конечной длины, позволяющей преобразовать произвольный корректный вариант расписания в оптимальный вариант расписания, и при этом все промежуточные расписания должны быть корректными. Стратегия применения операций на каждой итерации алгоритма определяет его сложность и точность.
В данной работе подход к построению системы операций преобразования расписаний и стратегии их применения расширен для решения задачи синтеза архитектуры вычислительной системы реального времени, а именно определения минимального необходимого числа процессоров и построения статического расписания выполнения прикладных программ. При этом должны соблюдаться заданные ограничения на время выполнения расписания и надежность вычислительной системы. Повышать надежность системы можно с помощью введения резервных элементов — как процессоров, так и копий программных модулей. В данной работе для повышения надежности вычислительной системы используется горячее резервирование процессоров и многоверсионное программирование. Задачи такого типа возникают при проектировании систем жесткого реального времени.
1. Задача построения расписания с минимизацией числа используемых процессоров. 1.1. Модель системы. Аппаратная часть системы состоит из множества процессоров, соединенных друг с другом посредством коммутатора. Все процессоры одинаковы, т.е. время выполнения одной и той же программы будет одинаково на любом процессоре, и надежность процессоров одинакова. Известно время передачи единицы данных от одного процессора к другому. Коммутатор устроен таким образом, что если к нему подключено N процессоров, то гарантируется наличие N/2 свободных каналов в любой момент времени, таким образом, для любой передачи всегда найдется канал. Существуют реальные коммутаторы, удовлетворяющие данным требованиям, в частности, это коммутатор Р1ЪгеСИаппе1.
Программа, для которой строится расписание, состоит из конечного множества взаимодействующих заданий. Для каждого из заданий известно, какие вычисления оно производит и каков объем результата, получаемого на выходе. Программу можно представить в виде графа потока данных. Формально модель системы состоит из следующих объектов:
М — счетное множество процессоров,
О = {V, Е} — граф потока данных программы, ориентированный граф без циклов,
V — множество вершин, соответствующих заданиям,
E — множество ребер; в графе есть ребро (vb v2), если задание v2 принимает на вход результаты работы задания vb
F : E ^ [R — функция, задающая объем передаваемых данных для каждой взаимодействующей пары заданий,
A : M х M ^ [ — функция, задающая время передачи единицы данных между двумя процессорами; если первый аргумент равен второму, то значение этой функции равно нулю: передача данных в пределах одного процессора не занимает времени,
C : V х M ^ [ — функция, задающая время работы задания на определенном процессоре; для каждого задания определена мера вычислительной сложности, по которой можно рассчитать время выполнения на конкретном процессоре.
В работе введены следующие ограничения:
Уш, Mj е M, v е V: C( v, m) = C( v, m) (функция C не зависит от m, поэтому в дальнейшем будем для простоты писать C( V));
Уш, Mj е M, MjФ mj: A(m, mj) = 1. Время передачи единицы данных между любыми двумя процессорами одинаково. Далее для простоты время передачи данных от одного задания к другому вместо F(v1, v2) • A(mb m2) будем обозначать F(v1, v2).
1.2. Модель надежности. Рассмотрены два метода повышения отказоустойчивости: резервирование для процессоров и многоверсионное программирование. Резервирование процессоров заключается в том, что в систему добавляется новый процессор, на котором выполняются те же задания, что и на другом. В этом случае система отказывает, только если отказывают оба процессора. Дублирующий процессор работает в режиме горячего резерва, т.е. принимает все те же данные и выполняет те же вычисления, что и основной, но передает данные только в случае отказа основного. Устройство коммутатора таково, что введение резервного процессора не вызывает никаких задержек в работе системы.
Ут верждение 1. Пусть на процессоре m j выполняются задания v^.. vn. Тогда добавление резервного процессора mr и дублирование на нем всех заданий v^.. vn обеспечивает надежность не меньшую, чем добавление резервных процессоров mr..mr + k и дублирование на каждом из них некоторых из заданий v^.. vn.
При многоверсионном программировании создается несколько версий реализации какого-либо задания и считается, что если больше половины из них выдали идентичный результат, то задание завершается успешно.
Для задания модели надежности системы необходимо, чтобы были известны величины P(m) — надежность отдельного процессора, Vers(vj) — множество доступных версий каждого из заданий, P( v) — надежность отдельного задания с учетом количества версий. Формулы для вычисления P(vj) при различных конфигурациях версий приведены в [3—6]. Надежность всей системы определяется как произведение надежностей всех ее компонентов.
1.3. Модель расписания. Будем считать, что для программы задано расписание, если для каждого из заданий определены привязка — однозначно известно, на каком процессоре оно выполняется, и порядок — для каждого процессора известно, в какой очередности выполняются задания. Если используется многоверсионное программирование, то помимо указания задания необходимо указывать номер его версии, т.е. привязка и порядок определяются не для задания, а для пары "задание—версия".
Формально расписание (для системы с резервированием и многоверсионным программированием) определяется как пара (S, D). Здесь S — множество четверок (v, k, m, n), где v е V, k е е Vers(v), m е M, n e N, такое, что
Vv e W& e Vers (v): 3! s = (vh kh mh щ) e S : vt = v, k = k;
VSf = (v;, k, mi, щ) e S, Vsj = (v, kj, mj, nj) e S : (st ф Sj л mt = mj) ^ щ Ф nj.
Второй элемент, D — мультимножество, состоящее из элементов множества процессоров M. Содержательно m и n задают соответственно привязку к процессору и порядок выполнения для каждой версии каждого задания. Мультимножество D обозначает резервируемые процессоры.
Расписание можно представить в виде графа. Вершинами этого графа являются элементы множества S. Если между соответствующими заданиями есть дуга в графе G, то она добавляется в граф расписания, также в граф расписания добавляются дуги между вершинами, назначенны-
ми на один процессор и имеющими соседние номера. Элемент расписания s2 будем называть зависимым от sj, если либо (vb v2) е E, либо m1 = m2 л n1 < n2. Иначе говоря, s2 зависит от sx, если s2 не может начать выполняться раньше s1 из-за зависимости по данным или порядка выполнения на процессоре.
Из определения следует, что каждая версия каждого задания может присутствовать в расписании в единственном экземпляре, а также на каждом процессоре у всех заданий различные номера и как минимум одна версия каждого задания должна быть включена в расписание. Помимо этих ограничений необходимо ввести еще одно, чтобы гарантировать завершимость программы. Будем говорить, что расписание S корректно, если его граф является ациклическим. Множество всех корректных расписаний обозначим S. Для каждого корректного расписания определены функции t(S) — время выполнения расписания, R(S) — надежность системы при заданном расписании и M(S) — количество процессоров, требуемых для работы по данному расписанию.
1.4. Постановка задачи. Пусть заданы программа G, td'r — срок, к которому программа должна быть выполнена, и Rd'r — надежность, которой должна обладать система. Требуется построить расписание S, для которого требуется минимальное количество процессоров, но при этом удовлетворяются ограничения на время выполнения и надежность:
minM(S); t(S) < tdir, R(S) > Rdir. (1.1)
S e S
Ут вер жд е н и е 2. Задача (1.1) является NP-трудной.
Данное утверждение может быть доказано путем сведения к задаче о разбиении множества чисел на два подмножества с равной суммой [7]. Каждому числу а, в задаче о разбиении ставится в соответствие задание v, со временем выполнения C(v,) = а,, связей между заданиями нет, Rd'r = 0, директивный срок td'r равен полусумме всех чисел {а,}.
1.5. Операции преобразования расписания. Введем следующие обозначения: Dup(m,) — кратность процессора m, в мультимножестве D; Dep(s) — множество таких элементов s,, что в графе G есть ребро (v,, v), т.е. множество вершин — непосредственных предшественников s; Succ(s) — множество заданий, косвенно зависящих от s. По определению, s, е Succ(sj), если либо в графе G есть путь из vj в v,
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.