Валерий Костенко / Кунцьо С. (4 курс) opt-sem

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

Модератор: staff

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

Валерий Костенко / Кунцьо С. (4 курс) opt-sem

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

Алгоритмы планирования обменов для вычислительных систем реального времени, построенных на основе коммутаторов FIBRE CHANNEL.

Данная работа является продолжением работы выполненной студентом на 3-м курсе. Расшифровка темы полностью совпадает с прошлогодней.

На 4-м курсе студент должен решить следующие задачи:
1. Разработать генератор исходных данных для задачи построения расписаний. Генератор должен позволять получать набор исходных данных с заданными характеристиками и для этого набора должно существовать корректное расписание, которое содержит все работы или известно максимальное число работ, которые могут быть включены в расписание.
2. Разработать семейство алгоритмов для решения задачи построения расписания обменов. Актуальность разработки семейства алгоритмов связана с тем, что задача является NP-трудной (NP-трудность задачи доказана на 3-м курсе). Однако, можно выделить классы исходных данных (класс определяется значениями характеристик исходных данных) для которых существуют оптимальные полиномиальные алгоритмы.
3. Для каждого алгоритма выделить класс исходных данных, на которых он наиболее эффективен по критериям точность и вычислительная сложность. Для определения классов исходных данных предполагается использовать метод статистической проверки гипотез.

Пункты 1-3 являются планируемыми результатами, но выполняться они должны итерационно. При выделении классов исходных данных, возможно, потребуется введение новых характеристик с целью сужения или расширения классов, что соответственно потребует модификации генератора исходных данных. Также в ходе исследования возможно добавление новых алгоритмов и классов исходных данных.
Кунцьо Степан
Выпускник
Сообщения: 1
Зарегистрирован: 19 дек 2008 12:31 pm

Сообщение Кунцьо Степан »

Тема работы
Разработка и исследование алгоритма планирования обменов в системах реального времени на основе коммутируемой среды Fibre Channel

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

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

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

Цели на 4 курс
В рамках данной курсовой работы мне необходимо:
1) Разработать генератор исходных данных для тестирования
2) Разработать семейство алгоритмов для решения задачи построения расписания обменов
3) Для каждого алгоритма выделить класс исходных данных, на которых он наиболее эффективен по критериям точность и вычислительная сложность.

Отчет о выполненной работе за прошедший семестр
За прошедший семестр мною была проведена следующая работа:
1) Генератор исходных данных: подробный анализ исходных данных с целью выявления эффективного и простого алгоритма, позволяющего генерировать данные, пригодные для тестирования алгоритма планирования расписания. Для этого был написан ряд утилит для построения и просмотра различных профилей исходных данных данных задачи. Было выяснено, что задача построения расписания/генерирования тестовых исходных данных для системы реального времени на коммутаторе принципиально отличается от аналогичной задачи для шины. Были проведены исследования особенностей генерации исходных данных для данной задачи, показавшие неприменимость существующих алгоритмов генерации.

2) Разработка семейчства алгоритмов для решния задачи, анализ классов исходных данных: Мною был разработан и формально описан алгоритм, условно названный "Алгоритм японских кроссвордов". За его основу взят классический алгоритм решения японских кроссвордов, адаптированный и модифицированный для данной задачи. Основная идея данного алгоритма заключается в инкрементальном выделении областей (промежутков времени) точного размещения и точного неразмещения сообщений, то есть таких временных промежутков, для которых нам точно известо, что в них передается либо не передается заданное сообщение. Недостатком данного алгоритма является тот факт, что он не способен разрешать неоднозначности, в следствие чего был разработан ряд эвристик, задача которых разрешать неоднозначности так, чтобы после них алгоритм японских кроссвордов мог продолжать свою работу. Применимость данного алгоритма зависит от количества сообщений в исходных данных задачи, для которых длина директивного интервала не превышает удвоенного времени передачи сообщения. Так же была начата реализация описанного алгоритма.

В следующем семестре предполагается:
1) закончить реализацию алгоритма
2) провести анализ и тестирование на исходных данных, сгенерированных для тестирования жадного алгоритма в предыдущем семестре и сравнить оба алгоритма
3) возможно получится придумать упрощенную версию генератора тестов для узкого класса задач. в этом случае - реализация данного генератора теста

Список использованной литературы:
1. 10GFC Fibre Channel стандарт 10Gbit/s [HTML] http://www.t11.org/t11/stat.nsf/1158203 ... enDocument
2. Технические заметки о технологии Fibre Channel [DOC] http://www.vilcomspb.ru/data/2802_Fibre_Channel.doc
3. FC-SW~--- стандарт Fibre Channel ''Switch Fabric`` [PDF] http://www.t11.org/ftp/t11/member/fc/sw/fcsw330.pdf

Дополнительные материалы
Статьи по алгоритму решения японских кроссвордов, взятые за основу разработанного алгоритма:
* http://ru.wikipedia.org/wiki/Японский_кроссворд - википедия, общая информация
* http://absite.ru/japan/how.html - как люди решают эти кроссворды
* http://program.rin.ru/razdel/html/975.html - алгоритм машинного решения
* http://algolist.manual.ru/misc/japancross.php - еще одна статья с алгоритмом машинного решения
* Посов И.А. Решение японских кроссвордов с использованием конечных автоматов // Компьютерные инструменты в образовании. - СПб.: Изд-во ЦПО "Информатизация образования", 2007, N3, С. 57-65.
Бычков Иван
Аспирант
Сообщения: 179
Зарегистрирован: 23 сен 2008 01:19 pm

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

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

В чем состоит принципиальное отличие?

2) Генератор исходных данных реализован?

Замечания к работе высылаю по почте.
Закрыто