Адаптивный метод распределения SPMD-заданий в грид Паньшенсков Михаил, 545 группа Научный руководитель: Лукичев А.С. Рецензент: Демьянович Ю.К июня 2007 года

Введение Грид – современная среда для выполнения распределенных вычислений SPMD (Single Program Multiple Data) задача Вход задачи: множество данных; Исполнение: цикл по множеству данных; Вход подзадачи: элемент данных; Исполнение: одна программа; SPMD-задача с гомогенным входом Время исполнения на одной целевой системе для всех подзадач одинаково

Примеры SPMD-задач с гомогенным входом задачи визуализации – визуализация фрактала Жюлиа математическое моделирование методом Монте-Карло – моделирование поверхностных реакций задачи информационного поиска – проект - поиск сигналов внеземных цивилизаций

Постановка задачи оптимального распределения Предоставлены n процессоров и m подзадач. Задача оптимального распределения подзадач: распределить блоки подзадач между процессорами так, что сумма общего времени выполнения вычислений и затрат на коммуникацию будет минимальной. Обратная связь Целевые системы … Балансировщик Распределение Разделитель Объединитель ДанныеРезультат

Схема работы для целевой системы На целевой системе параллельно выполняются: – Загрузка/Выгрузка данных – Выполнение подзадач На балансировщике последовательно выполняются: – Оценка параметров – Выбор размера блока

Алгоритмы Оценки производительности и стоимости коммуникаций – Метод наименьших квадратов Вычисление оптимальной длины блока – Обмен данными параллельно с вычислениями Распределение подзадач между целевыми системами – Многопоточная схема управления

Апробация предлагаемого алгоритма балансировки Среда запуска задач, моделирующая грид – На основе RMI Аппаратные ресурсы – 6 машин с разной производительностью Тестовое SPMD- приложение – Визуализация фрактала Жюлиа

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

Результаты Проведены эксперименты в среде моделирующей грид – На основе Java RMI Исследованы технологические аспекты применения в грид-системах: – Grid Programming Environment

Заключение Результаты работы приняты к докладу на международной конференции ICCSA'2007 Планируется дополнить и расширить применимость алгоритма: – Одновременное исполнение нескольких SPMD- задач – Более сложные схемы оценивания коммуникации Планируется реализация алгоритма для грид- систем GPE и EGEE

СПАСИБО!