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