Василий Балашов / Пётр Шестов, 5 курс, opt-sem

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

Модератор: staff

Закрыто
Бычков Иван
Аспирант
Сообщения: 179
Зарегистрирован: 23 сен 2008 01:19 pm

Василий Балашов / Пётр Шестов, 5 курс, opt-sem

Сообщение Бычков Иван »

= Постановка задачи для П. Шестова, 5 курс =

== Тема работы ==

Алгоритмы формирования рекомендаций при статическом планировании информационного обмена с различными эвристиками планирования.

// тема может быть уточнена в деталях

== Контекст ==

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

== Цель работы ==

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

== Задачи ==

Для достижения поставленной цели необходимо решить следующие задачи:
* выполнить обзор эвристик статического планирования информационного обмена по общей шине с централизованным управлением
* // в рамках данной работы акцент будет сделан на жадных эвристиках, которыми параметризуется конструктивный алгоритм планирования, строящий расписание "слева направо" по временной оси.
* провести анализ функционирования существующих алгоритмов формирования рекомендаций при планировании информационного обмена с различными рассмотренными эвристиками; сделать выводы о классах исходных данных, в которых алгоритмы формирования рекомендаций недостаточно эффективны (по числу итераций, по точности решения)
* разработать алгоритмы формирования рекомендаций, учитывающие специфику конкретных эвристик планирования обмена
* // новые алгоритмы должны применяться в сочетании с существующими
* выполнить исследование разработанных алгоритмов по критериям точности и вычислительной сложности (чило итераций для получения решения, сложность отдельной итерации, стабильность значений этих критериев)
* // исследование должно проводиться с применением метода проверки статистических гипотез, т.к. некоторые из существующих алгоритмов являются рандомизированными, а значит, и сочетание алгоритмов будет включать рандомизированые элементы

== Ожидаемые результаты ==

* обзор эвристик статического планирования (может быть полезен при адаптации существующих алгоритмов планирования к новым задачам)
* // это практически полезный результат, пусть он и не вписывается в требования "результатов дипломной работы"
* новые алгоритмы формирования рекомендаций
* экспериментальная реализация алгоритмов
* результаты экспериментального исследования
Пётр Шестов
Аспирант
Сообщения: 8
Зарегистрирован: 13 сен 2008 01:31 pm
Контактная информация:

Сообщение Пётр Шестов »

Отчет по проделанной за семестр работе

Выполнил: студент 522 группы Шестов П.Е.
Научный руководитель: м.н.с. Балашов В.В.

Постановка задачи дипломной работы
Задача построения расписания информационного обмена по каналу с централизованным управлением в составе встроенной системы реального времени (ВСРВ) является NP-трудной задачей. Поэтому для её решения на практике применяются различные эвристические алгоритмы. При этом для одного и того же набора исходных данных, один алгоритм может построить расписание, а другой – нет. Для некоторых других данных второй построит, а первый – нет. При этом теоретически расписание может существовать в обоих случаях, но не строится каким-то конкретным алгоритмом. Необходимо изменить требования к информационного обмену так, чтобы используемый алгоритм строил полное расписание.
В настоящее время разработаны отдельные алгоритмы автоматического формирования рекомендаций по изменению требований к информационному обмену по каналу для обеспечения их совместимости. Однако ни один из них не учитывает специфику применяемой эвристики планирования. Вместе с тем, эксперименты на ряде наборов реальных данных показывают, что решения, находимые существующими алгоритмами, отклоняются по значению целевой функции от оптимума на 25% и более. Это позволяет говорить об актуальности разработки алгоритмов формирования рекомендаций, учитывающих выбор эвристики планирования.
Целью работы является разработка алгоритмов формирования рекомендаций по обеспечению совместимости требований при планировании информационного обмена по каналу с централизованным управлением, учитывающих специфику используемых эвристик (алгоритмов) планирования обмена. Для достижения поставленной цели необходимо решить следующие задачи:
1. выполнить обзор эвристик статического планирования информационного обмена по общей шине с централизованным управлением;
2. провести анализ функционирования существующих алгоритмов формирования рекомендаций при планировании информационного обмена с различными рассмотренными эвристиками; сделать выводы о классах исходных данных, в которых алгоритмы формирования рекомендаций недостаточно эффективны (по числу итераций, по точности решения);
3. разработать алгоритмы формирования рекомендаций, учитывающие специфику конкретных эвристик планирования обмена;
4. выполнить исследование разработанных алгоритмов по критериям точности и вычислительной сложности (число итераций для получения решения, сложность отдельной итерации, стабильность значений этих критериев).

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

Работы на следующий семестр
1. Завершение исследования существующих алгоритмов формирования рекомендаций.
2. Разработка новых алгоритмов формирования рекомендаций, учитывающих специфику эвристики планирования.
3. Программная реализация на С++.
4. Исследование алгоритмов, в том числе на реальных данных.
5. Написание текста дипломной работы.

Литература
1. Государственный стандарт РФ «Интерфейс магистральный последовательный системы электронный модулей» ГОСТ Р 52070-2003.
2. Xu J. and Parnas D.L., «On Satisfying Timing Constraints in Hard-Real-Time Systems» IEEE Transactions on Software Engineering, Vol. 19, No. 1, January, 70-84, 1993.
3. Xu J. and D. L. Parnas D.L., «Priority Scheduling Versus Pre-Run-Time Scheduling» International Journal of Time-Critical Systems, 18, 7-23, Kluwer Academic Publishers, 2000
4. Балашов В.В. Алгоритмы формирования рекомендаций при планировании информационного обмена по каналу с централизованным управлением. // Известия РАН. Теория и системы управления, 2007, N.6, с. 76-84.
5. Мину М. Математическое программирование. Теория и алгоритмы // М.: Наука. Гл. ред. физ.-мат. лит., 1990.
6. Костенко В.А., Гурьянов Е.С. Алгоритм построения расписаний обменов по шине с централизованным управлением и исследование его эффективности. // М., Программирование, 2005, No. 6, стр. 340-346.
7. Балашов В.В. Формирование рекомендаций по изменению требований к информационному обмену при невозможности построения циклограммы обменов по мультиплексному каналу // Труды Третьей международной конференции "Параллельные вычисления и задачи управления" (РАСО'2006). М.: ИПУ им. В.А.Трапезникова РАН. 2006. С. 422-437.
8. Балашов В.В. Шестов П.Е. Формирование рекомендаций по обеспечению совместимости требований к обмену по общей шине во встроенных системах реального времени // Труды Четвертой международной конференции "Параллельные вычисления и задачи управления" (РАСО'2008). М.: ИПУ им. В.А.Трапезникова РАН. 2008. С. 1385-1404
9. Balashov V.V., Kostenko V.A., Smeliansky R.L.. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Avionics Systems // Proceedings of the Second European Conference For Aero-Space Science, 2007.
10. Bate I.J. Scheduling and Timing Analysis for Safety Critical Real-Time Systems. // Department of Computer Science, University of York, 1999.
11. Liu C.L., Layland J.W. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment // Journal of the ACM.1973. 20. № 1. P. 46 – 61.
Закрыто