Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

О некоторых свойствах процедур с планированием повторного входа. Язык Planning C

Пекунов Владимир Викторович

доктор технических наук

Инженер-программист, ОАО "Информатика"

153000, Россия, Ивановская область, г. Иваново, ул. Ташкентская, 90

Pekunov Vladimir Viktorovich

Doctor of Technical Science

Software Engineer, JSC "Informatika"

153000, Russia, Ivanovskaya oblast', g. Ivanovo, ul. Tashkentskaya, 90

pekunov@mail.ru
Другие публикации этого автора
 

 

DOI:

10.25136/2644-5522.2019.1.25522

Дата направления статьи в редакцию:

22-02-2018


Дата публикации:

04-03-2019


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


Ключевые слова:

процедуры, планирование повторного входа, последовательные алгоритмы, параллельные алгоритмы, алгоритмическая полнота, Planning C, язык программирования, трудоемкие вычисления, глубокие нейронные сети, вычислительная математика

Abstract: The article analyzes the descriptive capabilities of procedures and functions with re-entry planning. A procedure / function with re-entry scheduling differs from the usual procedure / function by the presence of a dynamically updated (from both inside and outside) plan of execution. This is a fairly new formalism, the theoretical and practical properties of which are still poorly covered in the scientific literature. Special attention is paid to the Planning C programming language, which fully implements the procedures and functions with re-entry planning. Descriptive features of procedures / functions with re-entry planning are considered both theoretically, using extended Turing machines, and constructively, by building equivalents of basic algorithmic control structures based on these procedures. The novelty consists in proving the representability of any sequential and parallel algorithms using these procedures. It is proposed to use Planning C, which implements such procedures / functions, for solving time-consuming problems of computational mathematics on parallel computing systems. The possibility of its use in solving the problem of learning deep neural networks is shown.


Keywords:

procedures, planning re-entry, sequential algorithms, parallel algorithms, algorithmic completeness, Planning C, programming language, hard calculations, deep neural networks, computational mathematics

Введение

Активный прогресс в области теории и практики программирования, появление новых задач в этой области (например, связанных с широким применением машинного обучения при анализе больших массивов данных) стимулирует нас к поиску и анализу новых решений. При этом особенно актуальны задачи определения теоретической и практической ценности появляющихся новых подходов. В данной статье рассматривается новый формализм в области программирования процедуры/функции с планированием повторного входа (ПППВ/ФППВ) [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 при решении задачи обучения глубоких нейронных сетей.

Библиография
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

Результаты процедуры рецензирования статьи

В связи с политикой двойного слепого рецензирования личность рецензента не раскрывается.
Со списком рецензентов издательства можно ознакомиться здесь.

Предметом исследования в рецензируемой работе являются методы программирования с использованием процедур/функций планирования повторного входа.
Основой исследований является теория алгоритмов.

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

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

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

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

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

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

В качестве незначительных замечаний отмечено, оформление списка литературы (п. 9) не соответствует ГОСТ 7.0.5-2008 БИБЛИОГРАФИЧЕСКАЯ ССЫЛКА. Общие требования и правила составления