№ 5 УДК 681.124.2 МИНИМИЗАЦИЯ КОЛИЧЕСТВА ВРЕМЕННЫХ МАССИВОВ В ЗАДАЧЕ РАЗБИЕНИЯ ЦИКЛОВ © 2011 г. О.Б. Штейнберг Южный федеральный университет, ул. <...> Мильчакова, 8, г. Ростов-на-Дону, 344090 Southern Federal University, Milchakov St., 8, Rostov-on-Don, 344090 Описывается алгоритм разбиения циклов, использующий в качестве вспомогательного преобразования введение временных массивов. <...> Он построен таким образом, чтобы количество введений временных массивов было минимальным. <...> Эта задача решается с помощью графовых моделей программ, а точнее с использованием графа информационных связей и построенного на его основе фактор-графа. <...> Результаты этой статьи могут быть использованы при разработке распараллеливающих компиляторов. <...> Написана программная реализация этого алгоритма в рамках проекта «Диалоговый высокоуровневый оптимизирующий распараллеливатель». <...> Разбиение цикла – одно из наиболее важных преобразований программ, которое может быть использовано при распараллеливании. <...> Иногда вместо термина «разбиение» используется термин «разрезание» или «распределение» (loop distribution). <...> Некоторые циклы невозможно разбить в исходном виде, и тогда можно попытаться применить вспомогательные преобразования. <...> Таким преобразованием, приводящим цикл к разбиваемому виду, может являться введение временных массивов. <...> С другой стороны, это преобразование приводит к увеличению количества операторов и расходу памяти. <...> В данной работе рассматривается задача минимизации использования временных массивов для разрезания. <...> Суть разбиения цикла состоит в том, чтобы заменить цикл, в теле которого много операторов присваивания, на эквивалентный фрагмент программы из нескольких циклов, в телах которых меньше операторов. <...> При распараллеливании зачастую большой цикл не может быть эффективно отображен на архитектуру параллельного компьютера (например, из-за нехватки ресурсов). <...> В этом случае есть надежда, что после разбиения все или хотя бы некоторые из результирующих циклов <...>