maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2020-2-164-179mais-1323Research ArticleTheory of ComputingДинамически изменяющийся параллелизм с асинхронно-последовательными потоками данныхDynamically Changing Parallelism with the Asynchronous Sequential Data Flowshttps://orcid.org/0000-0002-5487-0699ЛегаловАлександр ИвановичLegalovAlexander I.

Руководитель научно-учебной лаборатории технологий программирования, профессор кафедры вычислительной техники, доктор технических наук, профессор

660041, Красноярский край, г. Красноярск, пр. Свободный, 79

Head of the scientific and educational laboratory of programming technologies, professor of the department of computer engineering, doctor of technical sciences, professor

79 Svobodny pr., 660041 Krasnoyarsk

legalov@mail.ruhttps://orcid.org/0000-0002-4801-7982МатковскийИван ВасильевичMatkovskiiIvan V.

Старший преподаватель

 660041, Красноярский край, г. Красноярск, пр. Свободный, 79

Senior teacher

79 Svobodny pr., 660041 Krasnoyarsk

alpha900i@mail.ruhttps://orcid.org/0000-0003-4234-2714УшаковаМария СергеевнаUshakovaMariya S.

Ассистент кафедры вычислительной техники

660041, Красноярский край, г. Красноярск, пр. Свободный, 79

Assistent of the department of computer engineering

79 Svobodny pr., 660041 Krasnoyarsk

ksv@akadem.ruhttps://orcid.org/0000-0002-9020-4802РомановаДарья СергеевнаRomanovaDarya S.

Аспирант

660041, Красноярский край, г. Красноярск, пр. Свободный, 79

Graduate student

79 Svobodny pr., 660041 Krasnoyarsk

daryaooo@mail.ruСибирский федеральный университетРоссияSiberian Federal UniversityRussian Federation202024062020272164179Copyright © Легалов А.И., Матковский И.В., Ушакова М.С., Романова Д.С., 20202020Легалов А.И., Матковский И.В., Ушакова М.С., Романова Д.С.Legalov A.I., Matkovskii I.V., Ushakova M.S., Romanova D.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1323

Предлагается статически типизированная версия модели функционально-потоковых параллельных вычислений, которая за счет использования асинхронных последовательных потоков обеспечивает представление динамически изменяющегося параллелизма. Рассмотрены особенности синтаксиса и семантики статически типизированного языка функционально-потокового параллельного программирования Smile, обеспечивающие поддержку асинхронных последовательных потоков. Основная идея подхода базируется на использовании концепции взаимодействующих последовательных процессов Т. Хоара применительно к управлению по готовности данных. Предполагается, что готовность данных сопровождается выдачей управляющих сигналов, информирующих процессы о свершении тех или иных событий. Отличительной особенностью подхода является включение в модель специальных асинхронных контейнеров, которые могут порождать события по частичному заполнению. Этими контейнерами являются поток и рой, каждый из которых имеет свою специфику. Поток используется для обработки данных одного типа, поступающих последовательно и асинхронно в произвольные промежутки времени. Размерность поступающих данных изначально неизвестна, поэтому завершение обработки осуществляется по признаку конца потока. Рой используется для описания независимых данных одного типа, над которыми возможно выполнение массовых параллельных операций. В отличие от потока, его размерность фиксирована и известна заранее. В работе описаны общие принципы организации асинхронных последовательных потоков с произвольным поступлением данных. Рассматривается использование потоков и роев в различных ситуациях. Предлагаются языковые конструкции, позволяющие описывать работу с роями и потоками и особенности их применения. Представлены примеры функций, при реализации которых использованы различные подходы к описанию параллелизма: рекурсивная обработка асинхронных потоков, обработка потоков при недетерминированном и упорядоченном выполнении операций, прямое и ссылочное обращение к элементам потоков и роев, конвейеризация вычислений. Дается предварительная оценка параллелизма в зависимости от временных соотношений между темпом поступления данных и скоростью их обработки. Предложенные методы могут быть использованы при разработке перспективных языковых и инструментальных средств архитектурно-независимого параллельного программирования.

A statically typed version of the data driven functional parallel computing model is proposed. It enables a representation of dynamically changing parallelism by means of asynchronous serial data flows. We consider the features of the syntax and semantics of the statically typed data driven functional parallel programming language Smile that supports asynchronous sequential flows. Our main idea is to apply the Hoar concept of communicating sequential processes to the computation control on the data readiness. It is assumed that on the data readiness a control signal is emitted to inform the processes about the occurrence of certain events. The special feature of our approach is that the model is extended with the special asynchronous containers that can generate events on their partial filling. These containers are a stream and a swarm, each of which has its own specifics. A stream is used to process data which have identical type. The data comes sequentially and asynchronously at arbitrary time moments. The number of the incoming data elements is initially unknown, so the processing completes on the signal of the end of the stream. A swarm is used to contain independent data of the same type and may be used for the massive parallel operations performing. Unlike a stream, the swarm’s size is fixed and known in advance. General principles of the operations with the asynchronous sequential flows with an arbitrary order of data arrival are described. The use of the streams and the swarms in various situations is considered. We propose the language constructions which allow us to operate the swarms and streams and describe the specifics of their application. We provide the sample functions to illustrate the use of the different approaches to description of the parallelism: recursive processing of the asynchronous flows, processing of the flows in an arbitrary or predefined order of operations, direct access and access by the reference to the elements of the streams and swarms, pipelining of calculations. We give a preliminary parallelism assessment which depends on the ratio of the rates of data arrival and their processing. The proposed methods can be used in the development of the future languages and tool-kits of architecture-independent parallel programming.

параллельные вычисленияасинхронные вычислениястатическая типизациядинамически изменяющийся параллелизмparallel computationsasynchronous computationsstatic typingdynamically changing parallelismReferencesA. I. Legalov, “The Usage of Asynchronous Lists within the Dataflow Model of Computations”, in The Third Siberian School Seminar on Parallel Computations, In Russian, 2006, pp. 113–120.A. I. Legalov, “The Usage of Asynchronous Lists within the Dataflow Model of Computations”, in The Third Siberian School Seminar on Parallel Computations, In Russian, 2006, pp. 113–120.C. A. R. Hoar, Communicating Sequential Processes, 8. Communications of the ACM, 1978, vol. 21, pp. 666–677.C. A. R. Hoar, Communicating Sequential Processes, 8. Communications of the ACM, 1978, vol. 21, pp. 666–677.M. Diaz, Petri Nets: Fundamental Models, Verification and Applications. UK: ISTE Ltd, 2009.M. Diaz, Petri Nets: Fundamental Models, Verification and Applications. UK: ISTE Ltd, 2009.A. I. Legalov, “About Computation Control in Parallel System and Programming Languages”, Nauchiy Vestnik NGTU, vol. 18, no. 3, pp. 63–72, 2004, In Russian.A. I. Legalov, “About Computation Control in Parallel System and Programming Languages”, Nauchiy Vestnik NGTU, vol. 18, no. 3, pp. 63–72, 2004, In Russian.A. I. Legalov, V. S. Vasiliev, and I. V. Matkovsky, “Changing Computing Management Strategies for Architecture-Independent Parallel Programming”, in Proceedings of the XIX All-Russian Scientific Conference “Scientific Service on the Internet”, In Russian, 2017, pp. 341–350.A. I. Legalov, V. S. Vasiliev, and I. V. Matkovsky, “Changing Computing Management Strategies for Architecture-Independent Parallel Programming”, in Proceedings of the XIX All-Russian Scientific Conference “Scientific Service on the Internet”, In Russian, 2017, pp. 341–350.A. V. Redkin and A. I. Legalov, “Event Based Control of Computations for Functional Dataflow Programming”, Scientific Bulletin of Novosibirsk State Technical University, vol. 32, no. 3, pp. 111–120, 2008, In Russian.A. V. Redkin and A. I. Legalov, “Event Based Control of Computations for Functional Dataflow Programming”, Scientific Bulletin of Novosibirsk State Technical University, vol. 32, no. 3, pp. 111–120, 2008, In Russian.A. I. Legalov, A. V. Redkin, and I. V. Matkovsky, “Data Driven Functional Parallel Programming with Data Coming Asynchronously”, in Parallel Computing Technologiws (PCT’2009), In Russian, 2009, pp. 573–578.A. I. Legalov, A. V. Redkin, and I. V. Matkovsky, “Data Driven Functional Parallel Programming with Data Coming Asynchronously”, in Parallel Computing Technologiws (PCT’2009), In Russian, 2009, pp. 573–578.A. I. Legalov, I. A. Legalov, and I. V. Matkovsky, “Specifics of Semantics of a Statically Typed Language of Functional and Dataflow Parallel Programming”, in Scientific Conference “Scientific Service on the Internet”, 2019, pp. 489–500.A. I. Legalov, I. A. Legalov, and I. V. Matkovsky, “Specifics of Semantics of a Statically Typed Language of Functional and Dataflow Parallel Programming”, in Scientific Conference “Scientific Service on the Internet”, 2019, pp. 489–500.A. I. Legalov, “Functional Language for Architecture-Independent Programming”, Computation technologies, vol. 10, no. 1, pp. 71–89, 2005, In Russian.A. I. Legalov, “Functional Language for Architecture-Independent Programming”, Computation technologies, vol. 10, no. 1, pp. 71–89, 2005, In Russian.

The authors declare that there are no conflicts of interest present.