Автор неизвестен - Адаптивный генетический алгоритм, для распределенных систем с произвольной топологией

Tпослед.

Чтобы достигнуть минимального времени выполнения задачи в ВСРП, алгоритм планирования должен обеспечить минимальную суммарную задержку выполнения всех процессов.

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

1. Генерируем случайным образом 100 генотипов планирования графа. И также 5 «лучших» — нужно для алгоритма.

2. Скрещивается каждый со случайно выбранной из генофонда (100 хромосом):

Перебираются все геномы, каждому выбранному ищется пара случайным образом из текущих, проводим скрещивание каждой хромосомы с подобной. Пример дан внизу.

3. Производим мутации с определенной вероятностью. Происходит, если текущий геном подвержен мутации, случайное изменение значений отдельных участков(генов). Фактически перегенерация генотипа.

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

• Производим сортировку по приоритетам всех пересылок в графе задачи. Приоритеты пересылок определяются по приоритетам задач для которых они нужны.

• Производим сортировку вершин по их приоритетам.

• Пока все вершины не выполнены производим:

а. Ищем вершину не выполненную, для которой получены все данные и процессор которой не был занят при текущем событийном цикле. Затем выбираем время начала максимальным из времени начала вершины и времени процессора на котором будет выполнятся вершина. Выполняем если- время конца время начала + выполнение на текущем процессоре с определенной скоростью. Присваиваем время конца процессору, помечаем вершину как законченную. Маскируем процессор (для того, чтоб не выполнялись менее приоритетные вершины для которых получены данные) и производим пересылки.

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

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

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

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

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

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

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

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

Граф задачи