The Mechanism of Branches in the Dataflow Metalanguage UPL and Methods of Its Implementation in the PDCS “Buran”

 
Klimov A.V., Levchenko N.N. (IPPM RAS)
 
Abstract - Branches in the dataflow language for parallel programming UPL (Universal Parallel Language) are considered as well as methods of their imple-mentation for Parallel Dataflow Computing System (PDCS) "Buran". A node with P inputs can have several branches, each of which is activated by a subset of input tokens. This extension allows to introduce flexible controlled nondeterminism into algorithms. The use of branches is demonstrated by five dining philosophers problem as an exam-ple. Also the necessary information on the seman-tics of the language UPL is presented. For implementation of branches the matching device must be able to detect whether tokens are present on all the required (for a particular branch) input ports. To provide this ability, to-kens should contain some extra bits of information (in addition to the port number and the usage bit indicating that the port is used by a branch) using which one can decide on the completeness of a set of relevant inputs for each branch. Three ways to put this information in tokens are considered. The first way is to simply place in each token for each relevant branch the to-tal number of ports needed for that branch. Thus k bits for each relevant branch are required while maximum number of ports per branch is 2k . The second way is to put this number only into the token directed to the branch’s main port while all other ports get just a single bit indicating it is not the main. Finally, the third way, which is op-timal in number of bits, we allocate for each rele-vant branch just k extra bits for a number of one of K&#8804;2k colours. Colours are assigned such that the completeness of a subset of ports could be al-ways established. We propose an optimal way of assigning colors which allows for any number of ports-per-branch N<A(k,0), where A(m,n) is a very fast growing Akkerman function. The important result of the paper is the very formulation of a new interesting practical prob-lem, in which the Ackerman function is involved in the solution.

Keywords - dataflow computation model, dataflow language, nodes with branches, activation on subset of tokens, dining philoso-phers, Join calculus, token structure, Akkerman function.

Механизм ветвей в потоковом метаязыке UPL и методы его реализации в ППВС "Буран"

 
Климов А.В., Левченко Н.Н. (Институт проблем проектирования в микроэлектронике РАН, г. Москва)
 
Аннотация - В статье рассматриваются методы реализации ветвей в потоковом языке параллельного программирования UPL (Universal Parallel Language) на архитектуре ППВС «Буран». Узел с P входами может иметь несколько ветвей, каждая из которых активируется своим подмножеством входных токенов. Использование ветвей демонстрируется на примере задачи о пяти обедающих философах. Приводятся необходимые сведения о семантике языка UPL. Задача реализация механизма ветвей требует, чтобы в токенах содержалась дополнительная информация (помимо номера входа и его нужности для каждой ветви) для решения вопроса о полноте набора нужных входов для каждой ветви. Рассматриваются три способа внесения этой информации в токены: два простые и третий оптимальный. Последний требует только k бит в каждом токене на каждую ветвь при максимальном числе входов (в каждой ветви) N<A(2k,0), где A(m,n) – очень быстро растущая функция Аккермана, тогда как первые годятся только при N&#10877;2k. Для каждого способа описан алгоритм работы системы по определению достаточности набора принятых токенов для активации той или иной ветви. Важным результатом статьи является сама постановка задачи, в построении решения которой участвует функция Аккермана.

Ключевые слова - потоковая модель вычислений, потоковый язык, узлы с ветвями, активация по подмножеству входов, обедающие философы, Join calculus, структура токена, функция Аккермана.