следующая вершина минимального пути и расстояние всего пути производится один раз при создании алгоритма. Является модифицированным алгоритмом Дейкстры) пока вершина не попадет в нужный процесс. При этом увеличиваем время каждой связи так же как время процессора(максимальное из времени связи и времени пересылки), а если связь не дуплексная то и время зеркальной связи по матрице связности(3–2 обычная,2–3 зеркальная). Для вершины которая получила данные время начала выбираем максимальным из текущего времени начала вершины и времени пересылки. Считаем что пересылка получены, и если получены все пересылки то вершина может выполнятся

с. Производим переход на два шага назад пока все вершины не будут выполнены. Выбираем максимальное время из времени процессоров и это будет нашим временем выполнения графа. Также отображаем все события на диаграмме Ганта если оно нам надо.

5. 5 худших генотипов заменяем из 5 лучших, хранящихся отдельно в «привилегии».

6. Сортировка и выбор 5 лучших по времени выполнения генотипов и занесение в «привилегию».

7. Уничтожение клонов каждые M тактов. Клоны — идентичные генотипы.

8. Пока не закончилось число эпох(циклов алгоритма, задастся в виде числа в начале планирования) переходим на шаг 2.

Экспериментальные результаты

Была разработана программа, которая произвела автоматический подсчет около 500 графов на различные структуры. Приведу пример работы программы.

Граф задачи

Граф системы

Диаграмма Ганта.

P(N) номер процессора, на котором выполнялась задача. Зеленый прямоугольник и число, номер процесса. Lnk(N) связь с процессора в процессор. Синий прямоугольник и число пересылка с процесса в процесс (могут происходить через несколько процессоров).

Статистика

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

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

В левой колонке идет «Количество вычислений/Количество пересылок», вверху количество задач. Числа в таблице, отношение спланированного времени к критическому.

Заключение

Данный алгоритм даст возможность произвести оптимальное планирование для распределенных систем. Универсальность его заключается в том, что он практически не зависит от размерности графа задачи, системы и сложности системы.

Список литературы

1. О. В. Русанова В. В. Нагорнюк «Двухпроходной эвристический алгоритм планирования и отображения для систем с распределенной памятью» УДК 681.3 Вестник НТУУ «КПИ» «Информатика, управление и вычислительная техника».

2. Вороновский Г. К., Махотило К. В., Петрашев С. Н., Сергеев С. А. «Генетические алгоритмы искусственные нейронные сети и проблемы виртуальной реальности»

3. Исаев Сергей «Популярно о генетических алгоритмах».

4. Генетические алгоритмы.

Вторая редакция 11.05.2003.

Скачать программу.

Soft: mailto: alife-soft@yandex.ru?Subject=Генетический алгоритм