Пространственно-временные преобразования при распараллеливании линейных программ

Рассматриваются задачи поиска аффинных расписаний и размещений для линейных программ как задачи многокритериального выбора в условиях полной определенности с целью оптимизации локальности данных. Разработан метод, использующий аппарат модели многогранников и позволяющий минимизировать задержку и расстояние использования данных, исходя из предпочтений лица, принимающего решение (ЛПР). Предпочтения ЛПР задаются набором весовых коэффициентов линейной свертки критериев качества альтернативы. Поиск оптимальной по Парето альтернативы сводится к задаче линейного целочисленного программирования. Разработанный метод позволяет точнее осуществлять задание предпочтений ЛПР (в особенности для программ со слабой или ослабленной параметризацией при Just-In-Time компиляции) по сравнению с распространенным на момент исследования подходом, реализованным в компиляторе Pluto. Применение метода иллюстрируется примером распараллеливания алгоритма LU-разложения. Параллельный вариант алгоритма, полученный с помощью разработанного метода, показывает лучшее быстродействие по сравнению с результатом работы компилятора Pluto.