СПОСОБ АВТОМАТИЧЕСКОГО РАСПАРАЛЛЕЛИВАНИЯ ПРОГРАММ

Способ автоматического распараллеливания цикловых областей в алгоритмической части программы, позволяющий максимизировать количество параллельных циклов путем применения межпроцедурных и внутрипроцедурных оптимизаций, характеризующийся встраиванием в программу динамических проверок на эффективность распараллеливания, включающий следующие шаги:
предварительно, на этапе промежуточного представления программы при выполнении преобразований строят любыми известными способами, а если уже построены, то используют по крайней мере следующие аналитические структуры данных: граф потока управления, дерево доминаторов, дерево циклов, граф потока данных;
выполняют подстановки промежуточного представления процедур в места вызовов;
выполняют межпроцедурный анализ потока данных,
для обнаружения эквивалентных операций выполняют анализ потока данных, предпочтительно способом нумераций значений;
выполняют анализ переменных цикла на инвариантность и индуктивность;
выполняют анализ операций доступа в массивы, строят индексы доступа в массивы в виде канонических форм сумм произведений;
выполняют слияния циклов;
выполняют вынос инвариантных условий;
изменяют порядок обхода итерационного пространства циклов,
выполняют анализ параллельных циклов,
причем при выполнении межпроцедурного анализа потока данных применяют метод, чувствительный к контексту и чувствительный к потоку управления,
причем подстановку осуществляют в цикловых областях для получения максимального количества циклов, не содержащих вызовы процедур,
причем способ нумераций значений дополнительно проверяют анализом, уточняющим эквивалентность для операций доступа в память,
причем при построении канонических форм используют результаты анализа потока данных методом нумераций значений,
причем при анализе параллельных циклов дерево циклов обходят рекурсивно от корневого узла с проверкой на возможность распараллеливания текущего цикла, при этом выполняют следующие виды анализа:
анализ структуры цикла на наличие единственного выхода, поскольку распараллеливать возможно только циклы с одним выходом, управление которым осуществляется индуктивной переменной с инвариантными верхней и нижней границами, а также инвариантным шагом;
анализ на наличие редукций цикла, распознанные редукции исключают при анализе межитерационных зависимостей;
анализ межитерационных зависимостей в цикле, преимущественно с помощью решения диофантовых уравнений;
анализ массивов на локальность,
причем для параллельных циклов осуществляют построение копии цикла и динамически осуществляют проверку на время исполнения итераций и сравнение этого времени с затратами ресурсов на запуск параллельного цикла
причем для параллельных циклов выполняют построение операций, которые обеспечат параллельное исполнение циклов, при параллельном исполнении выполняют запуск нескольких потоков, каждый из которых выполняет часть итераций цикла
причем тело параллельных циклов выделяют в новую процедуру, параметрами которой назначают нелокальные данные итераций цикла, а локальные структуры данных итераций цикла назначают локальными структурами данных созданной процедуры.