WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 2 | 3 ||

Алгоритм распределения заданий.

1) Вычислить величины t *,. Пусть К – заданное число (значение паTG раметра). Алгоритм запускается для следующих значений t :

tG - t * t = t * + h, h = 0, K.

K 2) Распределять на каждый процессор j, начиная с первого, нераспределённые ранее задания до тех пор, пока суммарная длительность заданий на каждом процессоре не будет превышать величины t. При этом сначала максимально загружается текущий выбранный процессор, а лишь затем происходит переход к загрузке заданий следующего. Если в какой-то момент при попытке распределить очередное задание на процессор происходит превышение величины t, то сначала производится попытка распределения на тот же процессор оставшихся нераспределённых заданий вплоть до наименее трудоёмкого (также с не превышением величины t ) и только потом – переход на загрузку следующего процессора (для каждого j = 1,..., N определять M Qi xij = 1 до тех пор, пока xij < t для данного j). Для каждого j вычислить S i =j величину Lj.

3) Назначить оставшиеся ранее нераспределённые задания согласно пп.

3-5 «жадного» алгоритма.

Для предложенных алгоритмов даётся оценка точности их вычислений.

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

Результаты ряда экспериментов с эвристическим алгоритмом 2 приведены на рис. 4.

P % 120,00% 100,00% 80,00% 60,00% P % 40,00% 20,00% 0,00% 1 2 3 4 5 6 7 8 M / N (от 1 до 9) Рис. 4. Результаты ряда экспериментов с эвристическим алгоритмом Pj max = 2 j1, j2 N.

Pj лучше, чем «жадный» алгоритм % опытов, где эвристический алгоритм Проведённые эксперименты показали, что с используемыми механизмами калибровки (а) мультиоценочный алгоритм целесообразно применять при соотношении числа заданий к числу процессоров, не превосходящем 7.

(б) в дополнение к мультиоценочному алгоритму следует использовать также и «жадный» алгоритм, поскольку оба алгоритма работают достаточно быстро и при разных данных могут давать различные по точности результаты.

В Приложении 1 приведён пример применения САПР ВСРВ для решения в реальном времени задачи многомерной линейной регрессии.

В Приложении 2 - тексты программной реализации предлагаемых эвристических алгоритмов для многопроцессорного варианта САПР «СРВКонструктор».

В заключении сформулированы основные теоретические и практические результаты диссертационного исследования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ Основные результаты диссертационной работы заключаются в следующем:

1. Для однопроцессорных персональных ЭВМ типа IBM PC создан инструментальный программный комплекс автоматизации проектирования систем реального времени «СРВ-Конструктор», позволяющий в автоматизированном режиме проектировать вычислительные системы реального времени.

В рамках создания данной САПР решены следующие задачи:

• формального описания на языке высокого уровня программы выполнения прикладных модулей пользователя с учётом состава и периодов поступления информации в каждый модуль;

• трансляции этой программы (используется разработанная в ВЦ РАН система построения компиляторов «Супер»);

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

• генерации кодов и сборки исполнимых модулей готовой к выполнению ВСРВ.

2. С целью дальнейшего совершенствования указанной САПР для многопроцессорных вычислительных комплексов разработаны и реализованы новые эвристические алгоритмы решения задачи построения оптимального по быстродействию расписания без прерываний. Данные алгоритмы основаны на мультиоценке и калибровке получаемых результатов и выборе наилучшего среди сгенерированных результатов.

Основные результаты диссертации опубликованы в работах:

1. Сушков Б.Г., Фуругян М.Г., Гончар Д.Р., Кондратьев О.Л. Методология и программные средства мониторинга чрезвычайных ситуаций. //Тез. докл. конф.

"Проблемы управления в чрезвычайных ситуациях", Москва, ИПУ РАН, 1992, С.

62-63.

2. Сушков Б.Г., Фуругян М.Г., Гончар Д.Р., и др. САПР систем реального времени на базе IBM PC "СРВ-конструктор" //Тез.докл. III научной школы "Автоматизация создания мат. обеспечения и архитектуры систем реального времени".

Саратовский филиал Института машиноведения РАН, Саратов, 1992. С. 3-4.

3. Гончар Д.Р., САПР систем реального времени для IBM PC (сборник трудов). М., ВЦ РАН, 1993. С. 83-87.

4. Сушков Б.Г., Фуругян М.Г., Гончар Д.Р. и др. САПР вычислительных систем реального времени для IBM PC. // Тез. межд. конф. "Проблемы регионального и муниципального управления". Москва: РГГУ, 1999, 1 с.

5. Сушков Б.Г., Фуругян М.Г., Гончар Д.Р. и др. Система автоматизации программирования вычислительных систем реального времени. - В сб. "Теория и реализация вычислительных систем реального времени". М.: ВЦ РАН, 1999, 8 с.

6. Сушков Б.Г., Белый Д.В., Фуругян М.Г., Гончар Д.Р., Кондратьев О.Л. и др.

Автоматизация программирования вычислительных систем реального времени. //В сб.: Моделирование обработки информации и процессов управления. М.: МФТИ, 1999, 10 с.

7. Gonchar D., Fourougyan M. The decision of one problem of distribution of resources at presence of uncertain factors. Тез. 3-й Моск. межд. конф. по исследованию операций. Москва, ВЦ РАН, 2001 г., 1 с.

8. Гончар Д.Р., Фуругян М.Г. Автоматизация проектирования систем реального времени для испытаний и мониторинга сложных технических объектов. - Материалы 9-й межд. конф. "Проблемы управления безопасностью сложных систем", М., ИПУ РАН, 2001, 4 с.

9. Гончар Д.Р., Фуругян М.Г. Алгоритмы анализа и синтеза многопроцессорных систем реального времени. Тез. конф. "Математические модели сложных систем и междисциплинарные исследования". М: ВЦ РАН, 2002. 1 с.

10. Гончар Д.Р., Эвристические алгоритмы распределения заданий в многопроцессорной системе реального времени. Труды XLV науч. конф. МФТИ (ГУ), 2002 г., часть VII, М.-Долгопрудный: МФТИ, 2002. 1 с.

11. Гончар Д.Р., Гуз Д.С., Красовский Д.В., Фуругян М.Г. Эффективные алгоритмы планирования вычислений в многопроцессорных системах. // Проблемы управления безопасностью сложных систем: Труды 10-й международной конференции. Книга 2. /ИПУ РАН. – М., 2002 – С. 207-211.

12. Gonchar D. Multiboumds Heuristic Algorithm for Design of Scheduling M Tasks on N Equal Processors.// Труды 4-й Моск. межд. конф. по исследованию операций (ORM 2004). Москва: (ВМиК МГУ), 2004 г. С. 97-98.

13. Гончар Д.Р. Мультиоценочный эвристический алгоритм распределения M заданий на N процессоров// Моделирование процессов управления. М.:МФТИ, 2004 – С. 170-173.

14. Гончар Д.Р. Мультиоценочный эвристический алгоритм распределения M заданий на N одинаковых процессорах // В сб. Процессы и методы обработки информации. М.: МФТИ, 2005. 3 c.

15. Гончар Д.Р. Мультиоценочный эвристический алгоритм распределения M заданий на N процессоров. // II Всероссийская научная конференция «Методы и средства обработки информации». М.: МГУ, 2005. С. 537-539.

16. Гончар Д.Р. Мультиоценочный эвристический алгоритм распределения M заданий на N процессоров. // Сообщения по прикладной математике. М.: ВЦ РАН, 2005, 16 с.

17. Гончар Д.Р. Мультиоценочный алгоритм решения минимаксной задачи составления расписания // Системы управления и информационные технологии № 1.3 (27), 2007. Москва-Воронеж: Научная книга, 2007. С. 324-328.

18. Фуругян М.Г., Гончар Д.Р. Мультиоценочный алгоритм решения минимаксной задачи составления расписания // Проблемы управления безопасностью сложных систем: Труды XV-й международной конференции. Часть 2. /ИПУ РАН. – М., 2007 – С. 149-153.

19. Фуругян М.Г., Гончар Д.Р. Мультиоценочный алгоритм решения минимаксной задачи составления расписания // Сборник научных трудов– Моделирование процессов обработки информации. М.: МФТИ, 2007. С. 202-209.

ЛИЧНЫЙ ВКЛАД При построении инструментальной системы «СРВ-Конструктор» были приняты за основу и использованы после соответствующей переработки ряд разработок по предыдущей версии данной системы для ЕС ЭВМ, а именно формальный язык описания пользовательской СРВ для системы «СРВКОНСТРУКТОР», система автоматизированного построения компиляторов «Супер», ряд конкретных, специфичных для СРВ технических решений (при организации монитора реального времени, генерации кода и т.п.).

Сама идея создания САПР «СРВ-Конструктор» принадлежит основателю сектора проектирования ВСРВ Сушкову Б.Г. Идеи некоторых эвристических алгоритмов выдвинуты совместно с М.Г. Фуругяном. В совместных работах автору принадлежит теоретическая часть, постановки задач, разработка, испытания и исследования предложенных в диссертации подходов и алгоритмов. О.Л.Кондратьеву, Д.В.Белому, Д.С. Гузу и Д.В. Красовскому принадлежит рассмотрение ряда других алгоритмов управления и анализа систем реального времени, не вошедших в данную диссертацию.

Гончар Дмитрий Русланович МЕТОДЫ ПЛАНИРОВАНИЯ ВЫЧИСЛЕНИЙ В САПР СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ Подписано в печать 05.06.Формат 60х84 1/16. Бумага офсетная. Усл. печ. л. 1,0.

Тираж 100 экз. Заказ № Вычислительный центр им. А.А.Дородницына РАН 119991, г. Москва, ул. Вавилова,

Pages:     | 1 |   ...   | 2 | 3 ||






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