О проблеме распараллеливания вычислений

Abstract

Статья посвящена некоторым теоретическим и прикладным вопросам, касающимся распараллеливания вычислений. Она начинается с неформального обсуждения возможных формализаций таких понятий, как вычислительная среда и программа. В выбранной формализации используется понятие программы по Скотту. Полученная формализация используется для конструирования эффективного алгоритма распараллеливания выполнения программ, который может быть реализован на практике.

Стаття присвячена деяким теоретичним та прикладним питанням, що стосуються розпаралелювання обчислень. Вони починаються з неформального обговорення можливих формалізацій таких понять, як обчислювальна середа та програма. У вибраної формалізації використовується поняття програми за Скоттом. Отримана формалізація використовується для конструювання ефективного алгоритму розпаралелювання виконання програм, який може бути реалізовано на практиці.

This article is devoted to some theoretical and applied problems connected with parallel calculations. It starts from non-formal discussion up to formalizations of the notions like computing space and of a program. In particular, for formalizing the notion of program Scott’s approach is used. Then, obtained formalizations are used for constructing an effective algorithm of paralleling of executing programs, which can be implemented in practice. Also, some properties of this algorithm are investigated.