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

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

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

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

  1. множества процессоров и рабочих интервалов,
  2. привязка,
  3. порядок.

Привязка - всюду определенная на множестве рабочих интервалов функция, которая задает распределение рабочих интервалов по процессорам. Порядок задает ограничения на последовательность выполнения рабочих интервалов и является отношением частичного порядка, удовлетворяющим условиям ацикличности и транзитивности. Отношение порядка на множестве рабочих интервалов распределенных на один и тот же процессор, является отношением полного порядка. Различные варианты расписаний могут быть получены изменением привязки и порядка в заданных ограничениями пределах, которые определяются требованием не нарушения заданного отношения частичного порядка в модели поведения прикладной программы и определениями привязки и порядка.
Модель аппаратных средств определяется как совокупность исполнителей и каналов связи их объединяющих. Исполнитель обладает некоторым ресурсом: способностью выполнять заданный набор действий с определенным временем выполнения каждого действия. Канал связи может лишь обеспечивать передачу данных с некоторой задержкой. Исполнители делятся на распределенные и последовательные. Последовательный исполнитель в одно и то же время может выполнять действия, запрошенные только одним процессом. Один последовательный исполнитель может в режиме разделения времени обслуживать несколько процессов. Последовательные исполнители могут соединяться каналами связи и образовывать распределенный исполнитель.
При детализации программ на уровне взаимодействия процессов (в соответствии с определенной выше моделью поведения программ) мы выделяем следующие последовательные исполнители: процессоры, модули памяти, процессоры ввода/вывода и распределенный исполнитель: коммутационная среда. Коммутационная среда рассматривается как распределенный исполнитель, образованный из последовательных исполнителей – коммутационных узлов и узловых исполнителей (оконечных устройств). В качестве узловых исполнителей могут быть использованы процессоры, процессоры ввода/вывода, модули памяти и другие распределенные исполнители. Тип коммутационной среды определяется топологией связи и моделью синхронизации.
Синтез структуры вычислительной системы проводится в рамках некоторой параметризованной рамочной структуры (фрейм-структуры вычислительной системы). Фрейм-структура представляет собой параметрическое описание определенного класса ВСРВ и обеспечивает возможность проведения адаптации до конкретной проблемно-ориентированной структуры, наиболее эффективной для выполнения заданных прикладных программ. Использование фрейм-структур позволяет свести этапы синтеза структуры ВСРВ к решению задач условной оптимизации. В рамках фрейм-структуры вычислительной системы проведено разделение характеристик программно-аппаратных средств ВСРВ на фиксированные характеристики и варьируемые характеристики (оптимизируемые параметры), а также определены ограничения на допустимые значения варьируемых характеристик программно-аппаратных средств.
Наборы фиксированных и варьируемых характеристик, значения фиксированных характеристик и ограничения на допустимые значения варьируемых характеристик аппаратных средств определяют фрейм-структуру.
Фрейм-структуру будем задавать таким образом, чтобы выполнялось следующее требование: изменение значений варьируемых характеристик не должно приводить:
к переопределению наборов фиксированных и варьируемых характеристик;
к изменению типа целевой функции и функций ограничений.
Если фрейм-структура удовлетворяет данному требованию, то это позволяет рассматривать задачу выбора значений варьируемых характеристик как задачу условной оптимизации, и использовать для решения этой задачи разнообразные алгоритмы оптимизации.
Такой подход к решению задачи синтеза структуры ВСРВ предполагает решение следующих подзадач:

  1. Построение фрейм-структуры для заданного набора прикладных программ. Для некоторых задач может быть получено некоторое множество равноценных различных фрейм-структур.
  2. Построение в рамках выбранной на первом этапе фрейм-структуры конкретной структуры ВСРВ, наиболее эффективной для выполнения заданного набора прикладных программ. Данная задача сводится к задаче выбора конкретных значений варьируемых характеристик ВСРВ, и может быть переформулирована как задача условной оптимизации.

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

  1. число процессоров в вычислительной системе и возможно тип каждого процессора;
  2. расписание выполнения прикладной программы;
  3. возможные типы среды обмена: топология и модель обменов. Они определяются на основе трафика обменов в среде обменов без задержек связанных с конфликтами.

Полученные в рамках исходной фрейм-структуры результаты используются для построения более специализированной фрейм-структуры для следующего уровня проектирования.
Методы решения, используемые на абстрактном уровне проектирования:
жадные эвристики для построения расписаний, сложность - O(N) - O(N2), N- число процессов;
жадные эвристики для построения расписаний с одновременной минимизацией числа процессоров, сложность - O(N3) - O(N5);
локально-оптимальные алгоритмы коррекции расписаний с использованием сетей Хопфилда;
генетические и эволюционные алгоритмы для построения расписаний и для построения расписаний с одновременной минимизацией числа процессоров в случае неоднородных по типу процессоров структур, сложность - C*O(N) - C*O(N2), С=500-1000.
На системном уровне проектирования решается задача определения оптимизируемых характеристик структуры ВСРВ. При рассмотрении ВСРВ на системном уровне учитываются ограничения по аппаратным ресурсам, таким как объём памяти, быстродействие каналов данных и т.д.
В качестве оптимизируемых параметров ВСРВ могут быть выбраны:

  1. число процессоров;
  2. тип каждого процессора;
  3. характеристики аппаратных средств среды обмена и протоколов обмена;
  4. распределение памяти по узловым исполнителям и структура памяти для каждого узлового исполнителя;
  5. расписание выполнения прикладных задач и информационного обмена.

Методы решения, используемые на системном уровне проектирования:

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

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

Password: