О проблеме распараллеливания вычислений
Статья посвящена некоторым теоретическим и прикладным вопросам, касающимся распараллеливания вычислений. Она начинается с неформального обсуждения возможных формализаций таких понятий, как вычислительная среда и программа. В выбранной формализации используется понятие программы по Скотту. Полученная...
Збережено в:
| Дата: | 2004 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2004
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83892 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О проблеме распараллеливания вычислений / А.В. Деревянченко, А.А. Лялецкий // Мат. машини і системи. — 2004. — № 2. — С. 3-14. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859661576045330432 |
|---|---|
| author | Деревянченко, А.В. Лялецкий, А.А. |
| author_facet | Деревянченко, А.В. Лялецкий, А.А. |
| citation_txt | О проблеме распараллеливания вычислений / А.В. Деревянченко, А.А. Лялецкий // Мат. машини і системи. — 2004. — № 2. — С. 3-14. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| description | Статья посвящена некоторым теоретическим и прикладным вопросам, касающимся распараллеливания вычислений. Она начинается с неформального обсуждения возможных формализаций таких понятий, как вычислительная среда и программа. В выбранной формализации используется понятие программы по Скотту. Полученная формализация используется для конструирования эффективного алгоритма распараллеливания выполнения программ, который может быть реализован на практике.
Стаття присвячена деяким теоретичним та прикладним питанням, що стосуються розпаралелювання обчислень. Вони починаються з неформального обговорення можливих формалізацій таких понять, як обчислювальна середа та програма. У вибраної формалізації використовується поняття програми за Скоттом. Отримана формалізація використовується для конструювання ефективного алгоритму розпаралелювання виконання програм, який може бути реалізовано на практиці.
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.
|
| first_indexed | 2025-11-30T10:01:26Z |
| format | Article |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
3
УДК 51:681.03
А.В. ДЕРЕВЯНЧЕНКО, А.А. ЛЯЛЕЦКИЙ
О ПРОБЛЕМЕ РАСПАРАЛЛЕЛИВАНИЯ ВЫЧИСЛЕНИЙ
Аbstract: 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.
Key words: term, algorithm, paralleling.
Анотація: Стаття присвячена деяким теоретичним та прикладним питанням, що стосуються
розпаралелювання обчислень. Вони починаються з неформального обговорення можливих формалізацій
таких понять, як обчислювальна середа та програма. У вибраної формалізації використовується поняття
програми за Скоттом. Отримана формалізація використовується для конструювання ефективного
алгоритму розпаралелювання виконання програм, який може бути реалізовано на практиці.
Ключові слова: терм, алгоритм, розпаралелювання.
Аннотация: Статья посвящена некоторым теоретическим и прикладным вопросам, касающихся
распараллеливания вычислений. Она начинается с неформального обсуждения возможных формализаций
таких понятий как вычислительная среда и программа. В выбранной формализации используется понятие
программы по Скотту. Полученная формализация используется для конструирования эффективного
алгоритма распараллеливания выполнения программ, который может быть реализован на практике.
Ключевые слова: терм, алгоритм, распараллеливание.
1. Введение
Одной из основных проблем современного прикладного программирования является следующая
задача:
Рассматриваются «сложные» вычислительное устройства U , составленные из нескольких
своих вычислительных подустройств, не имеющих обязательно одинаковые мощностные
характеристики. Для каждой программы P и вычислительного устройства U написать алгоритм,
который во время выполнения программы P вычислительным устройством U так распределяет
возникающие задания между его подустройствами, чтобы время выполнения этой программы было
наименьшим.
Эта задача имеет как самостоятельный математический интерес, поскольку для её
решения необходимо формализовать понятие «параллельного» вычисления, так и прикладной,
поскольку задачи распараллеливания стали особо актуальными с развитием сетевых технологий и
различных форм мультипроцессорности [1].
В данной работе проводится теоретическое исследование, направленное на решение
поставленной задачи (или на доказательство, что в некоторых определённых смыслах такого
решения не существует). Изложение материала базируется на «наивной» теории множеств. В
общем случае может быть взята любая «обычная» аксиоматическая система, формализующая
теорию множеств, в которой истинна аксиома выбора. Несмотря на то, что авторы стремятся
решать поставленную задачу конструктивными методами, некоторые из теоретических результатов
данной работы получены неконструктивным путём (например, пункт (б) теоремы 1).
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
4
2. Формализация программы в логике Скотта
Для решения поставленной задачи прежде всего надо выбрать одну из возможных формализаций
понятия программы и понятия сложного вычислительного устройства (или, как мы для краткости
будем говорить в дальнейшем, сложного вычислителя). Этот выбор будет проводиться в
соответствии с критериями интуитивной ясности выбираемой формализации, её удобства с точки
зрения описания нужного нам алгоритма и достаточной её общности.
Исходя из этого, мы будем придерживаться формализации понятия программы,
предложенной в [2]. Эта формализация имеет ещё одно преимущество: в ней явно выписываются
все функциональные символы; при оценке сложности с фиксированной семантикой этих символов
функциям, которые им соответствуют, могут быть явно приписаны их «сложностные»
коэффициенты. Кроме этого, поскольку в данной формализации явно зафиксированы синтаксис и
семантика, то подобный подход можно рассматривать как логический [6].
Излагая данную формализацию, будем придерживаться следующей последовательности
действий. Вначале формально изложим синтаксис (т.е. опишем алфавит и некоторый язык в нём,
слова которого мы будем называть термами), далее – семантику (т.е. покажем, как при заданных
значениях символов алфавита вычислять значения термов), а затем выведем взаимосвязь между
подходом Скотта и уже давно ставшим классическим подходом – теорией частично рекурсивных
функций.
Синтаксис определяется следующим образом. Вначале фиксируются алфавит A; он в
нашем случае всегда состоит из множества символов, типизированных следующим
образом: ,..., 10 ff – функциональных символов, ,..., 10 pp – предикатных символов, символов
*,,CS , которые мы будем называть символами соответственно операции суперпозиции, операции
(условного) разветвления и операции (условного) циклирования, а также из вспомогательных
символов – левой скобки (правой скобки) и обычной запятой. В данном случае совокупности
функциональных и предикатных символов не предполагаются не более чем счётными; тем не
менее, для наглядности, при обозначении этих символов в качестве индексов будут
использоваться натуральные числа.
Понятие терма (в алфавите A) определим индуктивно:
1. Каждый функциональный символ if есть терм.
2. Если if – функциональный символ и ntt ,...,1 – термы, то слово ( )ni ttfS ,..., 1 – терм.
3. Если 0t и 1t – термы и ip – предикатный символ, то ( )10 ,, ttpC i – терм.
4. Если 0t – терм и ip – предикатный символ, то ( )0,* tpi – терм.
5. Слово в алфавите A является термом тогда и только тогда, когда оно может быть
построено только с помощью правил 1 – 4.
Грубо говоря, терм – это синтаксическая формализация понятия «метапрограммы»:
фиксируя значения символов *,,CS как некоторые специальные функционалы и фиксируя
значения символов, входящих в запись терма, т.е. сопоставляя функциональным символам
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
5
операции, предикатным символам – предикаты и, наконец, символам отношений порядка –
отношения полного порядка, мы сможем получать конкретные примеры программ. Значения всех
этих символов образуют семантику рассматриваемого терма. Сейчас мы более детально покажем,
какие объекты можно выбирать в качестве значений этих символов и как вычислять при этих
выбранных значениях символов значение самого терма.
Зафиксируем некоторое множество M . Задать интерпретацию функционального
символа if во множестве M – это значит сопоставить ему некоторую унарную, возможно,
частичную операцию iF на множестве M . Аналогично, под интерпретацией предикатного
символа ip во множестве M будем понимать любой унарный, возможно, частичный предикат iP ,
заданный на M . Если 0t – терм в некотором алфавите A и }{
nm jjii ppff ,...,,,...,
00
– множество
всех функциональных и предикатных символов терма 0t , а также его символов отношений
порядка, то интерпретацией терма t во множестве M называется любое отображение ι ,
которое каждому функциональному символу mjf
ji ≤≤1, , и предикатному символу nkp
ki
≤≤1, ,
сопоставляет их некоторые интерпретации
jiF и
ki
P в M .
Наконец, для каждого терма 0t индукцией по его построению определим, что такое
значение терма 0t при его некоторой фиксированной интерпретации ι . Пусть 0t – терм в
алфавите A и ι его интерпретация в некотором множестве M . Тогда:
1) если терм 0t имеет простейший вид, т.е. if , где if – функциональный символ, то
значение терма 0t при интерпретации ι определяется как iF , где iF – значение функционального
символа if при интерпретации ι ;
2) если терм 0t имеет вид ( )ntttS ,..., 1 , причём термы nttt ,...,, 1 имеют значения при
интерпретации ι, равные nTTT ,...,, 1 соответственно, и если, кроме того, арность операции iF
равна n, то значением терма 0t при интерпретации ι называется функция, которая на каждом
элементе m множества M принимает значение, равное ( ) ( )( )mTmTF ni ,...,1 , а если арность
операции iF отлична от n, то значением этого терма считается заданная над M всюду
неопределённая функция;
3) если терм 0t имеет вид ( )21,, ttpC i , где ip – предикатный символ со значением при
интерпретации ι , равным iP , а термы 1t и 2t имеют значения при интерпретации ι , равные 1T и
2T соответственно, то значением терма 0t при интерпретации ι называется функция 0T , которая
на каждом элементе m множества M принимает значение, равное:
а) ( )mT1 , если элемент m удовлетворяет частичному предикату iP ;
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
6
b) ( ) ( )mTmT 20 = , если m не удовлетворяет предикату iP ;
c) неопределённости, если значение предиката iP на m неопределено;
4) если терм 0t имеет вид ( )1,* tpi , где ip – предикатный символ, а 1t – терм со
значениями при интерпретации ι , равными iP и 1T соответственно, то значением терма 0t при
интерпретации ι называется функция 0T , которая для каждого элемента m множества M
определяется следующим образом: если в последовательности
m, ( )mT1 , ( )( )mTT 11 ,..., ( )( )( )...... 11 mTT ,... элемент ( )( )( )...... 11 mTT - её первый такой элемент, что на
нём предикат iP истинен, то полагаем ( )mT0 равным значению этого элемента, если же такого
элемента вида ( )( )( )...... 11 mTT нет, то значение ( )mT0 считаем неопределённым.
Назовём терм 0t согласованным с его интерпретацией ι в том и только том случае, когда
все подслова терма 0t , тоже являющиеся термами (т.е. так называемые подтермы), которые
имеют вид ( )ntttS ,..., 1 , удовлетворяют такому условию: если операция iF – интерпретация
функционального символа if , то арность этой операции равна n .
Таким образом, как уже неформально отмечалось выше, каждый терм, рассматриваемый
вместе с некоторой его фиксированной интерпретацией, выступает в качестве модели понятия
программы. Моделью называется упорядоченная тройка Pr,,OpM , где M – некоторое
множество, Op и Pr – совокупности заданных над ним частичных операций и частичных
предикатов соответственно; множество M мы будем также называть носителем модели. Ясно,
что если рассматривается алфавит символов A и если с каждым функциональным и предикатным
символами этого алфавита связать соответственно частичную операцию из Op и частичный
предикат из Pr модели Pr,,OpM , то для каждого терма над алфавитом A можно естественным
образом однозначно определить его интерпретацию. При этом последняя называется
интерпретацией терма в модели; значение терма при интерпретации, которая задаётся некоторой
фиксированной моделью, мы будем называть значением терма в модели.
3. Взаимосвязь логики Скотта и теории частично рекурсивных функций
Укажем на взаимосвязь между предлагаемым здесь подходом и теорией частично рекурсивных
функций [4].
Через n
mηδθ ,, ( m и n – натуральные числа, причём nm ≤ ) будем обозначать следующие
операции, арностей соответственно 1, 1 и n , заданные на натуральном ряде N :
– ( ) 0=kθ для любого натурального числа k;
– ( ) 1+= kkσ для любого натурального числа k;
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
7
– ( ) mn
n
m kkk =,...,1η для любой n-ки натуральных чисел nkk ,...,1 .
Операции n
mηδθ ,, n будем называть элементарными. Через S , R , M обозначим
операторы суперпозиции, примитивной рекурсии и минимизации соответственно. В соответствии с
классическим определением операция g , заданная на натуральном ряде N , называется
частично рекурсивной в классе операций F над N тогда и только тогда, когда g может быть
получена из элементарных операций и из операций из F с помощью операторов суперпозиции,
примитивной рекурсии и минимизации; если при этом =F ∅, то функция g также называется
просто частично рекурсивной. Отметим, что значения символа S в формализации Скотта (когда
рассматриваются модели с натуральным рядом в качестве носителя) и в теории частично
рекурсивных функций совпадают.
Если рассматривается модель, носитель которой состоит из всевозможных n-ок
натуральных чисел при нефиксированном n и совокупность операций которой содержит все
элементарные операции, то ясно, что каждой частично рекурсивной функции можно сопоставить
терм и модель так, что последние будут задавать эту частично рекурсивную функцию: при этом
оператору суперпозиции отвечает он сам, оператору минимизации отвечает оператор
циклирования и, наконец, оператор примитивной рекурсии, очевидно, выражается через
суперпозицию, разветвление и циклирование. Наоборот, если зафиксирована такая модель,
причём Op обозначает её совокупность всех операций и задан некоторый терм, то функция,
которая задаётся этим термом интерпретацией в рассматриваемой модели, можно сопоставить
частично рекурсивную относительно Op функцию.
4. Построение формальной модели параллельных вычислительных сред
И, наконец, всё готово к формализации и решению поставленной в самом начале задачи. Прежде
всего, потребуется формализовать понятие сложного вычислителя и понятие сложности
программы. Это будет происходить следующим образом: фиксируется некоторое положительное
натуральное число n , которое интерпретируется как количество всех «простейших» вычислителей,
составляющих первоначальное вычислительное устройство U . Также будет рассмотрен случай,
когда n есть «плюс бесконечность», т.е. первое бесконечное ординальное число ω . Далее, если
заданы алфавит A, причём F и Р обозначают множества всех функциональных и предикатных
символов, входящих в A, и модель M, в которой интерпретируются все «интерпретируемые»
символы из этого алфавита, то под сложностной функцией будем понимать любую функцию
{ } ( ) NPFns →∪×,...,1: (если ω=n , то эта функция s имеет вид ( ) NPFN →∪× ). Эту
функцию можно понимать как такую, которая сопоставляет каждому функциональному символу if
(предикатному символу ip ) и «простейшему» вычислителю с номером n время, которое займёт
вычисление каждого значения частичной операции iF (частичного предиката iP ), где iF – это
интерпретация символа if ( iP – это интерпретация символа ip ) в рассматриваемой модели.
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
8
Упорядоченную четвёрку snMA ,,, , где A – алфавит; M – модель, интерпретирующая
символы алфавита A; n – элемент множества { }( ) { }ω∪0\ N , и, наконец, s – это сложностная
функция, будем называть вычислительной средой.
Вычислительная среда snMA ,,, называется монотонной тогда и только тогда, когда
сложностная функция s монотонна по второму аргументу, т.е. для любой пары натуральных чисел
0m , 1m , не больших чем n , и для любых функциональных символов f и g алфавита A из
( ) ( )gmsfms ,, 00 ≤ следует ( ) ( )gmsfms ,, 11 ≤ и для любых предикатных символов p и q алфавита
A из ( ) ( )qmspms ,, 00 ≤ следует ( ) ( )qmspms ,, 11 ≤ .
Опишем теперь процесс вычисления терма на основном, «сложном» вычислителе. Для
этого обычно вводят так называемые состояния [3], затем вводят понятие конфигурации, а сам
процесс вычисления терма определяется как последовательность конфигураций,
удовлетворяющая некоторым специальным условиям. Но прибегнем к другой схеме. Откажемся
формально вводить понятие состояния, правда, в некотором смысле состояниями можно считать
моменты времени – такты работы «сложного» вычислителя, однако, с нашей точки зрения, одним
из основных свойств состояний является способность использовать их либо при записи терма,
либо при определении понятия его вычисления. Вместо этого, каждой вычислительной среде,
каждому терму в ней и каждому входному значению сопоставим специальное помеченное дерево,
которое при этих входных значениях указывает, когда и сколько раз должны вычисляться
интерпретации вхождений функциональных и предикатных символов в рассматриваемый терм.
Затем определим понятие конфигурации и, наконец, основываясь на этом понятии и на
упоминаемых выше помеченных деревьях, определим, что такое вычисления терма.
Под помеченным деревом будем понимать упорядоченную пару вида θ,∆ , где ∆ –
«обычное» дерево (с фиксированным корнем), а θ – любая функция, определённая на вершинах
дерева ∆ . Элементы множества значений θ будут называться метками помеченного дерева
θ,∆ . Если ∆ – дерево, то для любого множества a под { }a×∆ будем понимать (единственное)
дерево, изоморфное ∆ относительно взаимно однозначного отображения, которое каждой
вершине v дерева ∆ относит пару av, .
Пусть snMAS ,,,= – вычислительная среда, 0t – терм в алфавите A и ,..., 10 mm=π –
счётная последовательность элементов носителя модели M . Индукцией по длине терма 0t
построим специальное помеченное дерево θ,∆ , метками которого являются пары-элементы
множества ( )( ) NSTermsPF ×∪∪ , где ( )STerms обозначает множество всех термов в
вычислительной среде S (при этом будем считать, что строящееся дерево «растёт снизу вверх»):
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
9
1) если терм 0t имеет простейший вид, т.е. if , где if – функциональный символ, а iF
обозначает интерпретацию символа if в модели M , то полагаем ∆ состоящей из единственной
вершины, которой функция θ сопоставляет пару 1,iF ;
2) если терм 0t имеет вид ( )ni ttfS ,..., 1 , причём символ операции if интерпретируется как
iF и для термов nTT ,...,1 уже построены помеченные деревья nn θθ ,,...,, 11 ∆∆ , то объединяем
деревья { } { }nn ×∆×∆ ,...11 под общей вершиной { }0 , и для каждой вершины iv дерева i∆
полагаем ( ) ( )iii viv θθ =, и ( ) 1,iFa =θ ;
3) если терм 0t имеет вид ( )21,, ttpC i , где ip – предикатный символ со значением при
интерпретации ι , равным iP , а термы 1t и 2t имеют значения при интерпретации ι , равные 1T и
2T , которым соответствуют помеченные деревья 11,θ∆ и 22 ,θ∆ , то полагаем:
а) { } { }011 ∪×∆=∆ , причём вершина 0 расположена «ниже» всех остальных вершин
дерева ∆ , и ( ) 1,0 iP=θ , ( ) ( )111 1, vv θθ = для любой вершины 1v из 1∆ , если значение
выражения ( )ki mmmP ,...,, 10 суть истинна (k – арность предиката iP );
б) { } { }012 ∪×∆=∆ , причём вершина 0 расположена «ниже» всех остальных вершин
дерева ∆ , и ( ) 1,0 iP=θ , ( ) ( )222 1, vv θθ = для любой вершины 2v из 2∆ , если значением
выражения ( )ki mmmP ,...,, 10 является ложь;
в) ∅∅=∆ ,,θ , если значение выражения ( )ki mmmP ,...,, 10 не определено;
4) если терм 0t имеет вид ( )1,* tpi , где ip – предикатный символ, 1t – терм со значениями
при интерпретации ι , равными iP и 1T соответственно, причём 2T , рассматриваемый как функция,
имеет арность n и ему соответствует помеченное дерево 22 ,θ∆ , то полагаем:
а) { } { } { }1022 ∪∪×∆=∆ причём вершина 1 расположена «ниже» всех остальных
вершин дерева ∆ , кроме 0, ( ) ( )222 2, vv θθ = для любой вершины 2v из 2∆ , ( ) kpi ,0 =θ и
( ) kTi ,1 =θ , где k – такой наименьший номер элемента последовательности
( )110 ,...,, −ni mmmP , ( )( )111101 ,...,,,...,, −− nni mmmmmTP ,
( )( )( ),...,,...,,,...,,,...,, 111111011 −−− nnni mmmmmmmTTP
которому соответствует элемент, равный истине;
б) ∅∅=∆ ,,θ , если такого натурального числа k не существует.
Построенное помеченное дерево θ,∆ мы будем называть деревом вычисления терма 0t
в вычислительной среде S при интерпретации, определяемой последовательностью π .
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
10
Пусть F и P обозначают множества всех функциональных и предикатных символов
алфавита A, а N обозначает множество всех натуральных чисел.
Конфигурационной функцией вычислительной среды snMA ,,, будет называться любая
частичная функция k , которая действует из множества { }n,...,1 во множество { }( ) NPF ×∪∪ # , и
такая, что для любого nmm ≤≤1, , ( )mk имеет значение 0,x тогда и только тогда, когда #=x ;
понятие конфигурации будем отождествлять с понятием конфигурационной функции. Каждая
конфигурационная функция k показывает, какой «простейший» вычислитель, какую операцию или
предикат, сопоставленный функциональным символам алфавита A, выполняет в некоторый
момент времени; если iF – операция, соответствующая функциональному символу if ,
и ( ) iii tfmk ,= , то it означает время, которое необходимо потратить im -му «простейшему»
вычислителю, чтобы завершить выполнение операции iF (аналогично для предикатов). При этом,
равенство 0=it означает, что в данный некоторый момент времени ни один из «простейших»
вычислителей не выполняет никакую из операций iF и предикатов iP .
Пусть S – вычислительная среда, t – терм, θ,∆ – произвольное дерево вычисления
терма 0t в S и ,..., 10 kkk = – произвольная, не более чем счётная последовательность
конфигураций. Для каждого вхождения s некоторого символа из множества ( )PF ∪ в терм t
пусть ss θ,∆ обозначает дерево выполнения наименьшего подтерма терма t , которое содержит
вхождение s . (В дальнейшем будем отождествлять вхождение символа в терм и сам этот символ.)
Положим ( ) ∅=0kD , ( )1kD равным множеству всех меток листов дерева θ,∆ , и для каждого её
индекса последовательности k , строго большего 1, через ( )iDk обозначим множество
( )( ){ }qqj qбольшевеннонепосредстqqmkijmjPF θ, дереве в &1,& q '' ∆=<∃∃∪∈
Содержательно множества kD можно описать следующим образом. Если каждый элемент
рассматриваемой последовательности k конфигураций интерпретировать как последовательность
«состояний» простейших вычислителей в процессе выполнения некоторого терма, то каждое kD ,
кроме 0-го, является множеством всех операций, функций и термов либо уже выполненных, либо
доступных для выполнения.
Пусть t – терм в алфавите A; тогда вычислением терма 0t в вычислительной среде
snMAS ,,,= на входных данных, определяемой последовательностью ,..., 10 mm=π
называется любая не более чем счётная последовательность конфигурационных функций
,..., 10 kkk = , которая удовлетворяет следующим условиям:
1) функция 0k совпадает с функцией тождественно элементу 0,# ;
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
11
2) для каждого положительного натурального числа i последовательность ikkk ,...,, 10
удовлетворяет условиям 1 и 2, причём если ik не является последним элементом
последовательности π , то 1+ik суть любая такая функция, что для каждого натурального
положительного числа m , не большего чем n :
а) из ( ) PFqsqmki ∪∈= ,, и 1>s следует ( ) 1,1 −=+ sqmki ;
б)из ( ) ( )qmsqmki ,,1 =+ следует
( ) { } ( ) ( ){ }( )ijjDiDqPFqssqmk kki <∪+∈∪∪∈∈= \1,#,1,0,, '''' ;
3) i является последним индексом последовательности P тогда и только тогда, когда
( ){ } FimiDk =≤≤∪ 1 и из ij < следует ( ){ } FjmjDk =≤≤∪ 1 (если же такого числа i не
существует, то последовательность является счётной).
Сложностью вычисления терма называется длина (т.е. число всех индексов)
соответствующей последовательности k . Нас интересует алгоритм, который для каждой
вычислительной среды по входному терму и его входным данным (т.е. последовательности π )
строит его вычисление наименьшей длины.
5. Алгоритм распараллеливания выполнения программ и его свойства
Пусть snMA ,,, – вычислительная среда, 0t – терм в алфавите A и π – входные данные для
этого терма и θ,∆=T соответствующее дерево вычислений терма 0t . Весом ( )VW каждой
ветви V такого дерева T будем называть число, определяемое по формуле ( ) ( ){ }∑ ∈⋅ VvvkvW ,
где ( )vk – такое число, что ( ) Tvkv ∈, , причём если PFv ∪∈ v ∈ F ∪ P, то ( ) ( )1,vsvW = .
Пусть snMAS ,,,= – монотонная вычислительная среда, вычислители которой
расположены по убыванию эффективности их работы. Если известно, что для каждого из
подтермов it вида ( )ii tp ,* терма 0t соответствующий цикл длится не более чем iI итераций, то
рассматриваем следующий процесс, который будет называться алгоритмом
распараллеливания вычисления терма (или просто алгоритмом распараллеливания) и
обозначать через A:
1) строим дерево '',θ∆ , получающееся из дерева θ,∆ выполнения 0t в S путём
замены всех его меток вида kpi , и kf j , (т.е. вершин, «отвечающих» циклам) на вершины
ii Ip , и ij If , соответственно;
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
12
2) в дереве '',θ∆ выбираем все его максимальные ветви (т.е. ветви, которые не
содержаться ни в каких других ветвях, отличных от самих себя) и располагаем их в список 1S в
соответствии с их весом относительно этого дерева;
3) полагаем ( ) ( )0,#0 =mk для каждого nmm ≤, ;
4) если последовательность конфигурационных функций ikkk ,...,, 10 уже построена, 'T –
поддерево дерева '',θ∆ , и «есть» «свободные» вычислители, т.е. существуют такие m, что
( ) 11 =mk , то вычислитель с таким минимальным числом m сопоставляем, «загружаем» самой
нижней первой ветви в списке 1+iS операцией или предикатом, затем отнимаем от приписанного к
нему справа числа единицу и заново упорядочиваем список (преобразованных) максимальных
ветвей дерева в этом дереве или предикатом; повторяем так до тех пор, пока не останется
«свободных» вершин. Таким образом мы однозначно определили 1+ik ;
5) если последовательность ikkk ,...,, 10 является вычислением терма 0t , то алгоритм
заканчивает свою работу, иначе переходит к пункту 4.
Для каждого алгоритма B через Bt обозначим функцию, которая сопоставляет каждому
«входному данному» нашего алгоритма «время», которое занимает выполнение нашего алгоритма
на этом входном данном.
Теорема 1. В каждой монотонной вычислительной среде S алгоритм распараллеливания
является самым эффективным в следующих смыслах:
(а) если оценки nII ,...,1 являются точными, то сложность вычисления каждого терма
является наименьшей в смысле нашего определения (т.е. вычисление термов происходит
«быстрее всего»);
(б) для любого другого алгоритма B, удовлетворяющего пункту (а), существует такая
нумерация входных данных и такая линейная функция h , что ( ) ( ) ( ) ( )( )iBiAiBiA dtdthdtdt ÷≤÷ ++ 11 ,
где id – входное данное с номером i , а ÷ – это так называемая усечённая разность: бинарная
операция на множестве натуральных чисел, которая каждой паре nm, натуральных чисел
сопоставляет их разность nm − , если nm ≥ , и равна нулю, в противном случае
Доказательство пункта (a) ведётся индукцией по построению терма; доказательство пункта
(б) имеет неконструктивный характер и существенным образом опирается на теорему компактности
для разбиений [5], и, следовательно, на аксиому выбора.
Также можно показать, что если вычислительная среда S не является монотонной, то
предложенный алгоритм является неверным. Выполнение ,..., 10 kkk = терма t в вычислительной
среде snMAS ,,,= называется предоптимальным в том и только том случае, когда:
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
13
1) мощность множества ( ){ }0,#1 ≠mkm совпадает с числом, равным минимальному из
чисел n и количеству всех листочков дерева выполнения терма t в S ;
2) для каждого натурального числа ( )nii <<1 выполняется равенство
( ){ } ( ) ( ){ }( ){ }ijjDiDnmkm kk <∪=≠ \min0,#1 .
То есть, предоптимальное выполнение терма – это такое выполнение терма, что в каждый
момент времени количество всех загруженных простых вычислителей является максимальным.
Используя изложенную формализацию, применённую к первоначальной задаче, также не
трудно убедиться в следующем утверждении:
Теорема 2. При условии, что имеются точные оценки nII ,...,1 количеств итераций,
поставленная задача в общем случае (когда вычислительная система S является произвольной)
является, с одной стороны, разрешимой, а, с другой, для любого алгоритма, решающего её,
существует такая вычислительная среда S , что сумма сложностей его выполнения и (любого)
предоптимального выполнения каждого терма строго меньше, чем минимальная (т.е. «самая»
эффективная) сложность выполнения этого терма.
Интуитивно это можно объяснить так: чтобы самым эффективным образом
«распараллелить» выполнение терма, нужно прежде его (произвольным образом) выполнить.
Чтобы доказать этот факт, достаточно в качестве контр- примера для утверждения, обратного
второй части теоремы 2, рассмотреть предложенный алгоритм.
В случае, когда значения оценок nII ,...,1 неизвестны или они сильно отличаются от точных
значений, и даже предполагая рассматриваемую вычислительную среду S монотонной, нельзя
построить «по существу» самый эффективный алгоритм.
Теорема 3. Не существует алгоритма, который по (монотонной) вычислительной системе
по терму «распараллеливает» (не имея оценок nII ,...,1 ) выполнение этого терма в системе и
который удовлетворяет пункту (б) теоремы 1.
Для доказательства следует рассмотреть наш алгоритм, обратив внимание на то, что в нём
оценки nII ,...,1 дать невозможно, не зная аналогичных оценок для входного терма этого
алгоритма.
6. Выводы
Полученные результаты позволяют моделировать параллельные системы, которые понимаются в
достаточно широком смысле. В частности, они могут включать в себя различные
мультипроцессорные системы [7], а также сетевые топологии. Предложен эффективный алгоритм
распараллеливания термов (программ) для монотонных (т.е. однородных) сред, который может
быть реализован на практике. Изучены теоретические свойства этого алгоритма, а также всего
класса алгоритмов, которые решают задачу, поставленную во введении. В частности, оказалось,
что для того, чтобы эффективно распараллелить некоторый терм, необходимо знать достаточно
ISSN 1028-9763. Математичні машини і системи, 2004, № 2
14
много информации о нём и о системе, в которой будет проводиться его параллельное вычисление.
Теорема 1 утверждает, что в этом случае возможно самое эффективное распараллеливание. Если
же информации недостаточно, то теорема 3 указывает, что тогда универсального алгоритма
распараллеливания не существует. Всё это указывает на то, что при практическом
конструировании той или иной программы программист должен выбрать из следующей
альтернативы. С одной стороны, построение универсальной распараллеливающей системы, равно
как и программы, которая позволяет эффективно распараллеливать вычисления, часто является
сама по себе довольно трудной задачей, поскольку в этом случае необходимы точные оценки
сложности работы этой программы. С другой стороны, если программа, которую планируется
моделировать [8], будет использоваться в каждой вычислительной системе малое число раз и
сложность её выполнения является относительно небольшой, время, затраченное на эффективное
распараллеливание, плюс её (параллельное) выполнение может оказаться меньше, чем просто её
выполнение. В связи с этим, с практической точки зрения, на первый план выходит задача
построения оценок сложности работы распараллеливающих алгоритмов. Это авторы планируют
сделать в следующих работах.
СПИСОК ЛИТЕРАТУРЫ
1. Шоу А. Логическое проектирование операционных систем. – М.: Мир, 1981. – С. 69 –136.
2. Scott D.S. The Lattice of Flow Diagrams // Lecture Notes in Mathematics. – 1971. – N 188. – C. 311–366.
3. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – К.: Наукова думка, 1989. –
376 с.
4. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1986. – 368 с.
5. Protasov I.V. Combinatorics of numbers. – Lviv: VNTL, 1997. – 70 c.
6. Редько В.Н., Гришко В.Н., Редько И.В. Дескриптологическая среда программирования // Проблемы
программирования. – 2002. – № 1–2. – С. 7 – 14.
7. Воеводин В. Параллельные вычисления. – М.: BHV, 2002. – 603 c.
8. Анисимов А.В., Деревянченко А.В. Построение виртуального параллельного пространства с
использованием технологии ПАРУС-JAVA // Тезисы конференции ІБС, ШІ. – Дивноморское. – 2003. – 22–27. –
C. 18 – 19.
|
| id | nasplib_isofts_kiev_ua-123456789-83892 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-11-30T10:01:26Z |
| publishDate | 2004 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Деревянченко, А.В. Лялецкий, А.А. 2015-06-28T08:35:11Z 2015-06-28T08:35:11Z 2004 О проблеме распараллеливания вычислений / А.В. Деревянченко, А.А. Лялецкий // Мат. машини і системи. — 2004. — № 2. — С. 3-14. — Бібліогр.: 8 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83892 51:681.03 Статья посвящена некоторым теоретическим и прикладным вопросам, касающимся распараллеливания вычислений. Она начинается с неформального обсуждения возможных формализаций таких понятий, как вычислительная среда и программа. В выбранной формализации используется понятие программы по Скотту. Полученная формализация используется для конструирования эффективного алгоритма распараллеливания выполнения программ, который может быть реализован на практике. Стаття присвячена деяким теоретичним та прикладним питанням, що стосуються розпаралелювання обчислень. Вони починаються з неформального обговорення можливих формалізацій таких понять, як обчислювальна середа та програма. У вибраної формалізації використовується поняття програми за Скоттом. Отримана формалізація використовується для конструювання ефективного алгоритму розпаралелювання виконання програм, який може бути реалізовано на практиці. 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. ru Інститут проблем математичних машин і систем НАН України Обчислювальні системи О проблеме распараллеливания вычислений Про проблему розпаралелювання обчислень About the problem of paralleling computing Article published earlier |
| spellingShingle | О проблеме распараллеливания вычислений Деревянченко, А.В. Лялецкий, А.А. Обчислювальні системи |
| title | О проблеме распараллеливания вычислений |
| title_alt | Про проблему розпаралелювання обчислень About the problem of paralleling computing |
| title_full | О проблеме распараллеливания вычислений |
| title_fullStr | О проблеме распараллеливания вычислений |
| title_full_unstemmed | О проблеме распараллеливания вычислений |
| title_short | О проблеме распараллеливания вычислений |
| title_sort | о проблеме распараллеливания вычислений |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83892 |
| work_keys_str_mv | AT derevânčenkoav oproblemerasparallelivaniâvyčislenii AT lâleckiiaa oproblemerasparallelivaniâvyčislenii AT derevânčenkoav proproblemurozparalelûvannâobčislenʹ AT lâleckiiaa proproblemurozparalelûvannâobčislenʹ AT derevânčenkoav abouttheproblemofparallelingcomputing AT lâleckiiaa abouttheproblemofparallelingcomputing |