Система фрагментированного программирования Перепелкин В.А. Всероссийская молодежная школа по параллельному программированию МО ВВС ИВМиМГ 2009 г.

План Модель фрагментированной программы Динамические свойства Система фрагментированного программирования

Модель фрагментированной программы Множество фрагментов данных Множество фрагментов вычислений Управление (

Фрагментированный алгоритм и фрагментированная программа

Отношение соседства и балансировка загрузки

Шаблоны исполнения Слишком большая непроцедурность программы влечет сложности исполнения В таких случаях используется исполнение по шаблону –Fork / Join –Конвейер –Разделяй и властвуй –Массовые вычисления –…

Фрагментированное умножение матриц

Дополнительное управление

PIC метод и привязка к модели Множество модельных частиц Частицы взаимодействуют с полем Поле представляется пространственной сеткой значений Частицы распределены по ячейкам

Требуемые динамические свойства Масштабируемость Балансировка загрузки Настройка на аппаратные ресурсы –Коммуникации одновременно с вычислениями Переносимость Учет поведения модели

Масштабируемость Масштабируемость алгоритма – забота пользователя Масштабируемость исполнения программы – забота исполняющего окружения

Балансировка загрузки Причины дисбаланса: –Скопления частиц и разреженные области –Динамический временной шаг –Адаптивные сетки Балансировка загрузки осуществляется путем перераспределения фрагментов данных и вычислений

Система фрагментированного программирования Язык представления фрагментов и фрагментированных программ –Ориентированный на человека, визуальный Компилятор Исполнительная система –Разные системы для разных классов компьютеров Библиотека фрагментов и фрагментированных подпрограмм Профилировщик Средства разработки и отладки

Система Фрагментированного Программирования Визуальная среда разработки Исполняемый фрагментированный код Исполнительное окружение Компилятор Параллельная библиотека

Язык представления фрагментированных программ Запрограммировать алгоритм Задать рекомендации: –Распределение данных и отношение соседства –Способ балансировки загрузки –Шаблон исполнения –Динамика поведения модели –…

Компилятор Статический анализ и оптимизация программы Подстановка подходящих фрагментов и процедур из библиотеки Генерация исполняемого фрагментированного кода Создание плана исполнения фрагментированной программы

Исполнительная система Инкапсулирует системную составляющую исполнения программы в соответствии со спецификой аппаратного обеспечения Исполняет фрагментированную программу –Порождение фрагментов вычислений и данных по мере необходимости –Перемещение фрагментов между процессорами –Запуск вычислений в соответствии с управлением –Обеспечение и синхронизация доступа к данным –Балансировка загрузки Переносимость программ достигается реализацией ИС для различных архитектур

Настройка на ресурсы Архитектурные особенности: –Производительность процессоров –Объемы оперативной и кэш-памяти –Расширения и спец. вычислители –Пропускная способность и топология сети –Размер буфера отправки сообщений –... Настройку осуществляет исполнительная система

Библиотека Набор оптимизированных и отлаженных –Фрагментов –Подпрограмм Различные реализации для разных случаев

Профилировщик Исследование характеристик исполнения программы Подстройка параметров на основе профиля исполнения –Размер и количество фрагментов –Набор процедур и подпрограмм –Шаблоны исполнения –Распределение данных –Способ балансировки –…

Жизненный цикл программы Пользователь Программа Компилятор Программа Исполнительная система РекомендацииДанныеПрофиль

Резюме Представление программы параллельное –фрагмент – «гранула» параллелизма Фрагментированность программы сохраняется во время исполнения –Возможны манипуляции с программой во время исполнения Системная составляющая программы сконцентрирована в исполнительной системе –Не требуется специализированных знаний в программировании Круг задач ограничен численным моделированием –Используются регулярности в данных и вычислениях для эффективного исполнения Используются (интегрируются) существующие библиотеки и технологии

Спасибо за внимание!

Промежуточное представление фрагментированной программы Язык ФП Другой Язык ФП Промежуточное представление Исполнительная система 1 Исполнительная система 2

Система Фрагментированного Программирования Визуальная среда разработки Исполняемый фрагментированный код Исполнительное окружение Компилятор Параллельная библиотека

Разный порядок исполнения в задаче LU разложения матрицы