Methods for Computation Planning in the Parallel Dataflow Computing System "Buran"

 
Zmejev D.N., Klimov A.V., Levchenko N.N., Okunev A.S. (IPPM RAS)
 
Abstract - 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. The compu-tational 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 of local memory filling in the computa-tional core. Computation planning allows the management of the computational process in automatic mode and the crea-tion of possibility to solve large tasks, while having a limited capacity of content addressable memory. The article de-scribes 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 computa-tion planning uses spooling and swapping of active and pas-sive 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 follow-ings 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 versa-tile 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 de-velopment 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 over-flow of the content addressable memory of keys. This work was carried out with the partial financial support of the RFBR grants 17-07-00478 и 17-07-00324.

Keywords - computation planning, parallel dataflow computing system, dividing into stages, dataflow computing model.

Методы планирования вычислений в параллельной потоковой вычислительной системе «Буран»

 
Змеев Д.Н., Климов А.В., Левченко Н.Н., Окунев А.С. (Институт проблем проектирования в микроэлектронике РАН, г. Москва)
 
Аннотация - Параллельная потоковая вычислительная система «Буран» реализует потоковую модель вычислений с динамически формируемым контекстом. Для обеспечения эффективного распараллеливания задач на большое число ядер системы необходимо управлять вы-числительным процессом в автоматическом режиме и решать задачи с большим объемом данных, имея ограниченный объем локальной памяти вычислительного ядра. В статье описываются методы планирования вычислений, которые позволяют преодолеть, а в ряде случаев и исключить саму возможность, переполнения ассоциативной памяти ключей вычислительного ядра системы. Такими методами являются: метод с использованием токенов-заглушек; метод, использующий разбиение токенов на этапы (активные и пассивные) и откачку пассивных этапов в соответствующую память; метод с использованием только отложенных этапов (без откачки). Эти методы повышают эффективность решения задач и увеличивают надежность работы вычислительных средств.

Ключевые слова - планирование вычислений, параллельная потоковая вычислительная система, разбиение на этапы, потоковая модель вычислений