Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Branches in the Dataflow Metalanguage UPL (METAL) and Methods of their Implementation in the PDCS “Buran”
Authors
	Klimov A.V.
	Levchenko N.N.
Date of publication
	2018
DOI
	10.31114/2078-7707-2018-3-31-37
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≤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 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.
Library reference
	Klimov A.V., Levchenko N.N. Branches in the Dataflow Metalanguage UPL (METAL) and Methods of their Implementation in the PDCS “Buran” // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2018. Issue 3. P. 31-37. doi:10.31114/2078-7707-2018-3-31-37
URL of paper
	http://www.mes-conference.ru/data/year2018/pdf/D098.pdf