Аннотация.

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

Ключевые слова:

автоматическое распараллеливание, локальность данных, модель многогранников, линейное целочисленное программирование.

Стр. 19-32.

Полная версия статьи в формате pdf. 

A.S. Lebedev

"On choosing space-time mappings during automatic parallelization of loop nests with static control flow"

Problems of affine scheduling and spatial distribution for programs composed of loop nests with static control flow are considered as multi-objective optimization problems with no uncertainty in context of data locality optimization. Presented method based on polyhedral model appliance computes space-time mapping to expose parallelism while minimizing data reuse latency in time domain and data reuse distance in space domain for each data dependence on the assumption of subjective preferences of the decision maker on optimization quality for each dependence. Subjective preferences are defined by weighting coefficients in linear form of scalarized multi-objective problem. Finding Pareto-optimal solution is reduced to solving of integer linear programming problem. The method allows to specify subjective preferences more precisely (notably for weakly parameterized programs or for programs with artificially de-emphasized parameterization during Just-In-Time compilation) in contradistinction to classic methods relying on  lexicographic optimization such as  Pluto. Application of  the  method is illustrated with parallelization of LU-decomposition algorithm. Parallel version of the algorithm obtained with presented method outperforms the result obtained with Pluto compiler.

Keywords: automatic parallelization, locality optimization, polyhedral model, integer linear programming.