Methods for Computation Planning in the Parallel Dataflow Computing System "Buran"
The project of the parallel dataflow computing system (PDCS) "Buran" implements a new dataflow computing model with a dynamically formed context. This computing model has a number of features in comparison with the computing models used in traditional computing systems. The PDCS "Buran" is multi-core and scalable system. The computational core of the PDCS includes an execution unit, a matching processor, a token commutator, a hash block and other blocks. The content addressable memory of keys and token memory, which are part of the matching processor, have a limited capacity. This can cause memory overflow and, as a result, block the computational process. In order to ensure the solving of tasks in the PDCS, it is necessary to effectively manage local memory filling in the computational core. Computation planning allows the management of the computational process in automatic mode and the creation of possibility to solve large tasks, while having a limited capacity of content addressable memory. The article describes the planning methods associated with the distribution of computations by time. The first method spools and swaps tokens dynamically, using a special token-"lock" that sends all the tokens that are matched to it to the memory of spooled tokens. The programmer determines the ranges of spooled tokens by specifying the relevant key and the mask of the token-"lock". Simplicity of hardware support is an advantage of this method. The second method of computation planning uses spooling and swapping of active and passive stages. The group of tokens, which is a separate part of the program, is combined under a certain stage number. The task is divided into stages by the programmer using hash functions which generate the stage number by key. For the functioning of this method at the hardware level the followings are added: a block of hashing by time (generates the stage number), the stage table, the spooled memory, and the memory of the postponed tokens. This method is more versatile than the previous one, but it requires a lot of hardware and efforts from programmer to divide the task into stages. The third method is using only postponed stages. It is a development of the previous one, but with the refusal of the procedure of token spooling. This eliminates the potential of an overflow of the content addressable memory. Only tokens of active and postponed stages are involved in computation. The application of the methods described in the article makes it possible to solve tasks of large dimension, excluding the blocking of the computational process associated with overflow of the content addressable memory of keys.