WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 ||
  • класс 1: ;
  • класс 3:.

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

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

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

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

Классификация в п.2 алгоритма осуществляется путем выделения у рассматриваемой системы определяющего признака – наличия убывающей последовательности (класс 1), либо наличия возрастающей последовательности (класс 2), либо наличия состыкованных возрастающей и убывающей последовательностей (класс 3). Для этого анализируется интервальная зависимость для ЭВМ критического пути времени выполнения всех задач от номера ЭВМ. Анализ включает аппроксимацию верхних границ этой зависимости параболой. При этом если вершина параболы оказывается слева от интервала номеров ЭВМ, то система относится к классу 1, если справа, то – к классу 2, если внутри интервала, то – к классу 3.

Оценка эффективности предложенного алгоритма осуществлялась на основе компьютерного моделирования и производилась по отношению к классу иерархических систем, структура которых описывается бинарным сбалансированным графом (все вычислительные пути в таких системах имеют одинаковую длину). В основу использованного подхода было положено случайное генерирование примеров. При этом фиксировалось число ЭВМ (m=15 или m=31), образующих иерархию, а число задач n варьировалось в интервале от 5 до 10. Для каждого значения n из этого интервала генерировалось 100 примеров. Причем времена решения задач на каждой из ЭВМ формировались как случайные величины, равномерно распределенные на заданном интервале. Для каждого получаемого примера строилось расписание на основе предложенного алгоритма и путем полного перебора (оптимальное расписание). Эти расписания сравнивались между собой по относительной разности времен выполнения. Результаты моделирования приведены на рис. 2 и 3. Результаты показывают, что, например, при n=5 и m=15 (рис. 2) предлагаемый алгоритм в 53% случаев строил расписания, которые уступали по длительности оптимальному расписанию не более 10%, а в 80% случаев были построены расписания, уступающие оптимальному не более 30 %. При использовании алгоритма в отношении системы из 31 ЭВМ не менее чем в 75% случаев строится расписание, уступающее по длительности выполнения оптимальному расписанию не более 30% (рис. 3).

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

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

Среди примененных принципов доминирующими и определяющими новизну данной разработки являются два – применение экспертного подхода для анализа диагностической информации и использование технологии баз данных (БД) для реализации этого подхода. Для упрощения процесса проектирования экспертная оболочка и сама экспертная система разрабатывались в среде С++ Builder, которая поддерживает механизм реляционных БД. В результате правила в базе знаний были представлены как записи БД, а проверка срабатывания правил осуществлена как формирование SQL-запроса. Предложенные программные средства нашли применение при разработке в ЦНИИ «Электроприбор» вычислительных систем морских навигационных комплексов, среди которых Струна – 3.1, Струна – 3.2, Сумматор – 11430.

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

  • Разработаны оптимальные алгоритмы планирования вычислительного процесса для трех базовых классов иерархических систем. Алгоритмы минимизируют общее время выполнения заданного списка задач и не требуют перебора вариантов.
  • Разработаны оптимальные алгоритмы планирования вычислительного процесса при заданных директивных сроках для трех базовых классов иерархических систем. Алгоритмы не требуют перебора вариантов и минимизируют максимальное отклонение от заданных директивных сроков.
  • Предложен субоптимальный алгоритм планирования вычислительного процесса для иерархических систем общего вида, не требующий перебора вариантов. Алгоритм учитывает особенности морских навигационных комплексов и несущественно проигрывает оптимальному алгоритму, минимизирующему время выполнения заданного списка задач.
  • Предложены принципы построения информационной системы планирования и контроля вычислительного процесса в навигационном комплексе, которая позволяет осуществлять эффективную поддержку процессов проектирования и контроля навигационных комплексов. Эти программные средства нашли практическое применение при разработке современных навигационных комплексов в ЦНИИ «Электроприбор».

СПИСОК ПУБЛИКАЦИЙ

  1. Толмачева М.В., Матросов Ю.М. Принципы диспетчеризации вычислительного процесса навигационной системы // Гироскопия и навигация, 2002, № 4. Рефераты докладов XXIII Научно-технической конференции памяти Н.Н. Острякова, СПб. С. 74.
  2. Толмачева М.В., Матросов Ю.М., Цал З.И. Универсальная программа диспетчеризации вычислительного процесса навигационной системы// Гироскопия и навигация, 2004, № 4. Рефераты докладов XXIV Научно-технической конференции памяти Н.Н. Острякова, СПб. С.99.
  3. Толмачева М.В., Колесов Н.В. Составление расписаний решения задач в конвейерных вычислительных системах // Информационно-управляющие системы, 2005 г., № 5. С. 16 – 21.
  4. Толмачева М.В., Колесов Н.В. Оптимизация расписаний работ с неопределенными временами выполнения // Рефераты докладов 6-ой международной конференции по морским интеллектуальным технологиям, СПб, 2005. С. 73 – 74.
  5. Толмачева М.В., Колесов Н.В. Оптимизация расписаний работ с неопределенными временами выполнения // Материалы докладов 6-ой международной конференции по морским интеллектуальным технологиям, СПб, 2005. С. 160 – 164.
  6. Толмачева М.В., Колесов Н.В. Построение расписаний решения задач в многопроцессорных системах при заданных директивных сроках // Материалы 6-ой международной конференции «Интеллектуальные и многопроцессорные системы», Геленджик, 2005. С. 122 – 124.
  7. Толмачева М.В., Колесов Н.В. Приближенный рекурсивный алгоритм построения расписаний для конвейерных вычислительных систем // Труды 2-ой Всероссийской научной конференции «Методы и средства обработки информации», Москва, 2005. С. 559 – 563.
  8. Толмачева М.В., Соколов А.А. Экспертная система постанализа вычислительных процессов приборов навигационного комплекса // Гироскопия и навигация, 2006, № 2. С. 109.
  9. Толмачева М.В., Колесов Н.В. Субоптимальный алгоритм построения расписаний для иерархических вычислительных систем // Информационно-управляющие системы, 2006 г., № 2. С. 14 – 20.
  10. Толмачева М.В., Колесов Н.В. Построение расписаний решения задач в микропроцессорных системах при заданных директивных сроках // Вестник компьютерных и информационных технологий, № 7, 2006 г. С. 48 – 54.
  11. Толмачева М.В., Колесов Н.В. Планирование вычислительного процесса в морских навигационных комплексах // Гироскопия и навигация, 2006, № 4. Рефераты докладов 1-й Всероссийской мультиконференции по управлению, СПб. С. 109.
  12. Толмачева М.В. Информационная система планирования, мониторинга и анализа вычислительного процесса в навигационном комплексе // Гироскопия и навигация, 2006, № 4. Рефераты докладов 1-й Всероссийской мультиконференции по управлению), СПб. С. 109.
  13. Толмачева М.В., Безмен Г.В. Специализированная экспертная оболочка для диагностирования навигационных систем // Гироскопия и навигация, 2007, № 2. С. 97.
  14. Толмачева М.В., Юхта П.В. Исследование эффективности алгоритма планирования вычислительного процесса в иерархической системе // Гироскопия и навигация, 2007, № 2. С. 101.
  15. Толмачева М.В., Юхта П.В. Программные средства для разработки и исследования вычислительного процесса в навигационном комплексе // Гироскопия и навигация, 2007, № 2. С. 101.
  16. Толмачева М.В., Колесов Н.В. Планирование вычислительного процесса в иерархических системах // Известия РАН. Теория и системы управления, № 2, 2007. С. 5 – 12.
  17. Толмачева М.В., Колесов Н.В. Планирование и контроль вычислений в навигационном комплексе // Гироскопия и навигация, 2007, № 2. С. 37 – 48.

Подписано в печать 18.04.07 Заказ №82. Тираж 100 экз. Объем 1 п.л.

Государственный научный центр РФ – ЦНИИ «Электроприбор»

197046, С.-Петербург, ул. Малая Посадская, 30

Pages:     | 1 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»