Some properties of procedures with re-entry scheduling. Planning C language

Pekunov Vladimir Viktorovich Doctor of Technical Science Software Engineer, JSC "Informatika" 153000, Russia, Ivanovskaya oblast', g. Ivanovo, ul. Tashkentskaya, 90 pekunov@mail.ru Other publications by this author

Введение

Активный прогресс в области теории и практики программирования, появление новых задач в этой области (например, связанных с широким применением машинного обучения при анализе больших массивов данных) стимулирует нас к поиску и анализу новых решений. При этом особенно актуальны задачи определения теоретической и практической ценности появляющихся новых подходов. В данной статье рассматривается новый формализм в области программирования — процедуры/функции с планированием повторного входа (ПППВ/ФППВ) ^{[1, 2]}, свойства которых до сих пор недостаточно описаны в научной литературе. Целью данной работы является определение описательных свойств формализма ПППВ/ФППВ. Для достижения данной цели поставим следующие задачи: рассмотреть свойства формализма с теоретической точки зрения; сформулировать практические выводы по его применению.

Процедуры и функции с планированием повторного входа

Процедура/функция с планированием повторного входа отличается от обычной процедуры/функции наличием пополняемого (как изнутри, так и извне) плана исполнения. Каждый этап плана содержит комплекс специфических значений параметров ПППВ/ФППВ. При вызове ПППВ/ФППВ план содержит, как минимум, совокупность значений параметров, указанных при вызове (инициализационный этап). ПППВ/ФППВ последовательно вызывается для каждого этапа плана, при каждом таком вызове из начала плана извлекается очередной этап, а соответствующие ему значения помещаются в параметры вызова ПППВ/ФППВ. При выполнении тела ПППВ/ФППВ в план могут быть помещены новые этапы, как в начало, так и в конец. Согласованная работа на различных этапах работы ПППВ/ФППВ обеспечивается, во-первых, взаимодействием через глобальные данные, во-вторых, передачей данных с этапа на этап через специальные «туннелирующие» ссылочные параметры. Такая идеология работы ПППВ/ФППВ особенно уместна при решении задач, предполагающих явное или неявное использование стека, дека, очереди, массива, дерева (а также любых иных структур данных, для которых возможно построение последовательного алгоритма обхода), но может быть успешно применена и для реализации иных алгоритмов.

Параллельное исполнение

Отметим, что работа ПППВ/ФППВ может быть легко распараллелена в идеологии «портфеля задач» ^[3], при которой параллельная система набирает на вычислительные узлы, по мере их освобождения, задачи из некоторого пополняемого множества. В роли «портфеля» выступает план, в роли задачи — этап плана.

Более сложные виды параллелизма (как минимум векторный и конвейерный ^[4]) могут быть реализованы с помощью специальной конструкции — цепи процедур/функций, в которой все процедуры/функции запускаются параллельно и, в случае конвейера, могут передавать данные путем стандартного механизма планирования, с той разницей, что ПППВ/ФППВ пополняет не свой план, а план следующей по цепи ПППВ/ФППВ. Прочие параллельные режимы могут рассматриваться как расширения векторного, если имеет место обмен данными между элементами вектора.

С помощью ПППВ/ФППВ могут быть представлены произвольные параллельные вычислительные топологии, которые в таком случае описательно представляются множеством цепей с повторяющимися элементами. При этом рассматриваются цепи с прямым и обратным порядком передачи данных. На обратные цепи поставлено ограничение — они могут быть исключительно двухэлементными. Передачи данных при этом также осуществляются путем удаленного планирования (ПППВ/ФППВ помещает данные в начало или конец плана иной ПППВ/ФППВ). Конструкции синхронизации могут быть реализованы с применением стандартных примитивов (семафоров, барьеров, критических секций), характерных для работы в реальной/виртуальной общей памяти параллельной системы.

Реализуемость классических управляющих конструкций

Данную проблему можно рассмотреть с применением двух подходов: а) конструктивно, построив эквиваленты ключевых алгоритмических конструкций с помощью ПППВ/ФППВ; б) теоретически, воспользовавшись элементами теории алгоритмов.

Конструктивный подход

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

Ветвление вида «если <условие> то A иначе B» при наличии сокращенного вычисления логических выражений записывается (в синтаксисе C++ и дополнительных конструкций) следующим образом:

reenterable bool procA(<параметры A>)

{ A; return true; }

reenterable bool procB(<параметры B>)

{ B; return true; }

<условие> && procA(<параметры A>) || procB(<параметры B>);

Пусть конструкции планирования в начало и конец плана исполнения являются функциями, возвращающими истинное значение. Тогда основной цикл вида «пока <условие> повторять A» запишется так:

reenterable bool procA(<параметры A>)

{ A; return true; }

reenterable while_loop(<параметры>)

{ <условие> && plan_last(<параметры>) && procA(<параметры A>); }

while_loop(<параметры>);

Известно, что с помощью такого цикла с предусловием можно реализовать любые циклы.

Таким образом, ФППВ/ПППВ являются достаточными предельными средствами программирования, с помощью которых можно реализовать произвольные алгоритмы обработки данных. Более того, концепция ПППВ/ФППВ поддерживает идею «отчуждаемых планов», согласно которой заголовок ПППВ/ФППВ может рассматриваться как декларация типа плана -- линейной структуры данных (стека, дека, очереди, массива, в частном случае -- одиночной переменной), состоящей из однотипных элементов, каждый из которых имеет набор полей, совпадающих по типу и названию с параметрами ПППВ/ФППВ. Типы плана и элемента плана могут использоваться для декларации произвольных переменных, поэтому, средства ПППВ/ФППВ позволяют успешно заменить конструкторы сложных типов данных в большинстве случаев.

Теоретический подход

Рассмотрим проблему формально.

Теорема о предельной ПППВ. Предельной ПППВ является параллельная расширенная машина Тьюринга (параллельная РМТ) ^[5]. При этом будем считать, что транзакционная память реализуется РМТ программно.

Доказательство. Приведено в работе ^[5].

Теорема устанавливает эквивалентность предельного случая ПППВ/ФППВ и параллельной РМТ. Поскольку РМТ является надмножеством ^[5] классической машины Тьюринга, способной выполнить произвольный алгоритм, то ПППВ/ФППВ действительно способна выполнить произвольный алгоритм.

Практическое применение ПППВ/ФППВ. Язык программирования Planning C

Как было показано выше, ПППВ/ФППВ позволяют реализовать произвольные последовательные алгоритмы. Поскольку данный формализм предусматривает параллельное исполнение как отдельных процедур/функций, так и этапов плана одной процедуры/функции, возможна реализация и произвольных параллельных алгоритмов, причем весьма просто могут быть реализованы такие базовые шаблоны параллелизма как «портфель задач», конвейер и вектор, несколько более сложным является процесс создания произвольной вычислительной топологии. Поэтому, рассматриваемый формализм может быть эффективно применен для решения задач вычислительной математики, предполагающей применение одного из вышеуказанных шаблонов параллелизма. Это могут быть, например, проблемы, сводимые к решению задач оптимизации методом глобального случайного поиска ^[6] или генетическими алгоритмами или полным перебором. Сюда относятся проблемы обучения глубоких нейронных сетей, ряд проблем численного моделирования процессов механики жидкости и газа ^{[7, 8]}, проблемы поиска оптимальных схем распараллеливания ^[9].

Автором разработан язык программирования Planning C ^{[10, 11]}, в полной мере реализующий все отмеченные особенности формализма ПППВ/ФППВ и расширяющий их возможности работы в условиях наличия/отсутствия транзакционной памяти. Для данного языка разработан транслятор и создан ряд экспериментальных программ на Planning C, прошедших испытания на машинах с общей памятью, кластерных, гибридных системах с многоядерными видеокартами.

В частности, разработана программа обучения глубоких нейронных сетей модифицированным методом генетического случайного поиска ^[10], являющегося развитием оригинального метода доцента С.Г.Сидорова ^[12].

Программа использует параллелизм «портфеля задач» и конвейер. Ее исполнение на системе с двумя видеоускорителями NVidia Tesla K40 (0,88 ГГц, 2880 потоков) дало ускорение в 5,09 раз по сравнению с 16-ядерной 64-потоковой системой платформы Google’s Compute Engine с процессорами Xeon 2,6 ГГц с векторными SSE-инструкциями.

Это на практике доказывает реализуемость, по меньшей мере, некоторых классических параллельных алгоритмов и дает основания утверждать практическую ценность параллелизма ПППВ/ФППВ.

Выводы

Таким образом, в настоящей работе рассмотрены описательные возможности формализма ПППВ/ФППВ по отношению к произвольным последовательным и параллельным алгоритмам. Доказано, что язык на базе ПППВ/ФППВ (в частности, Planning C) позволяет реализовать любой алгоритм. Возможности показаны теоретически, полученные выводы подкреплены опытом практического применения формализма в языке Planning C при решении задачи обучения глубоких нейронных сетей.