Технологии автоматического дедуктивного распараллеливания в языке Planning C. Владимир Викторович Пекунов
труктурированных данных с применением более или менее трудоемких логических [12], символьных [11] или численных алгоритмов (см., например, [2, 14, 21]. Это, в первую очередь, технологии интеллектуальной обработки данных, к которым относятся разнообразные алгоритмы поиска логических и/или математических формальных закономерностей в данных (Big Data/Data Mining [7, 22]): деревья решения, машины поддерживающих векторов [22], нейронные сети [22, 24], МГУА [7] и иные интерполяторы и экстраполяторы [11]. Во вторую очередь, назовем элементы технологий поддержки диалога с пользователем на естественном языке (см., например, [22]). Далее назовем ряд технологий математического моделирования различных процессов, например, в сплошных средах: моделирования образования и распространения загрязнений [10, 13, 14, 35], прогнозирования погоды [41], прогнозирования изменений климата [6, 41], моделирования обтекания различных технических объектов [28], прочностные и иные трудоемкие расчеты, связанные с моделированием (см., например, [5]).
Решение (даже частичное) подавляющего большинства перечисленных выше проблем подразумевает выполнение огромных объемов расчетов. Неудивительно, что для осуществления подобных расчетов наиболее часто применяются параллельные или распределенные системы [4, 27], способные их выполнить за разумное время. Программирование таких систем, особенно в случае нетривиальных алгоритмов, является достаточно сложной задачей, к решению которой часто привлекаются специалисты в области параллельных/распределенных вычислений. Однако и в этом случае разработка и реализация параллельных алгоритмов занимает достаточно большое количество времени и требует тщательной отладки.
Далее заметим, что параллельными системами, содержащими процессор с несколькими ядрами и, нередко, многоядерные видеокарты, являются даже современные персональные ЭВМ. В простых случаях проблемой адекватного распределения нагрузки в таких ЭВМ занимается операционная система, помещая различные процессы/потоки для исполнения на различные ядра.
Это, несомненно, дает определенный эффект, однако следует заметить, что полноценная эффективная загрузка вычислительных ресурсов современной ЭВМ, в общем случае, все-таки требует, как минимум, организации многопоточности в разрабатываемых программах, а в идеальном случае – тщательного распараллеливания применяемых алгоритмов, что также требует специальных знаний в области параллельных вычислений.
Логичным является вывод о том, что эффективное применение вычислительных ресурсов (как для решения задач высокой сложности, так и для более рядовых задач) в настоящее время в большей или меньшей степени требует распараллеливания вычислений, подразумевающего наличие специальных знаний в этой области. Однако существенная часть ученых-исследователей и многие рядовые программисты не обладают ни такими знаниями, ни соответствующими навыками алгоритмизации. Отсюда можно заключить, что актуальна задача автоматического распараллеливания программ.
Итак, данная работа будет посвящена автоматическому распараллеливанию C-программ (дающих высокую эффективность исполнения кода, поскольку язык С – один из наиболее близких к машинному, уступающий, возможно, лишь языкам класса Форт), однако изложенные в ней технологии пригодны для распараллеливания программ, написанных и на иных алгоритмических языках.
Целью данной работы является повышение эффективности исполнения C-программ, исполняемых на различных типах параллельных/распределенных систем, к которым можно отнести не только суперЭВМ, но и подавляющее большинство современных рядовых ЭВМ (в том числе с SIMT-расширителями, такими как многоядерные видеокарты). Соответственно, следует стремиться: а) к максимальной многоплатформенности получаемых распараллеленных C-программ и б) к оптимальной трудоемкости разработки адекватных параллелизаторов, подразумевающей достаточную мощность средств разработки в сочетании с их простотой. Для достижения данной цели сформулируем задачи:
а) рассмотреть современные подходы к автоматизированному распараллеливанию императивных (в том числе написанных на языке C) программ;
б) выбрать платформу, предлагающую достаточно простые и мощные средства реализации автоматического распараллеливания;
в) предложить новые технологии распараллеливания, применение которых может быть автоматизировано;
г) разработать подход и алгоритмы автоматического распараллеливания C-программ;
д) провести испытания разработанных программных средств для автоматического распараллеливания на примере простых программ.
Глава 1. Подходы к распараллеливанию императивных программ
Целью данной небольшой главы является определение наиболее адекватного подхода к автоматическому распараллеливанию императивных программ. Для реализации данной цели поставим следующие задачи:
а) провести краткий обзор современных основных подходов к автоматическому/автоматизированному распараллеливанию;
б) выбрать наиболее соответствующий поставленным в работе целям подход;
в) определить средства распараллеливания и программную