Схема с распределенной памятью: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Схема с распределенной памятью''' (''Scheme with distributed memory'') - Имеется два основн...)
 
Нет описания правки
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
'''Схема с распределенной памятью''' (''Scheme with distributed memory'') -
'''Схема с распределенной памятью''' (''[[Schema with distributed memory]]'')
Имеется два основных способа идентификации взаимовлияний
Имеется два основных способа идентификации взаимовлияний
операторов и переменных в ''схеме программ'' --- так
операторов и переменных в [[схема программ|''схеме программ'']] — так
называемая общая и распределенная память. В схемах над общей
называемая общая и распределенная память. В схемах над общей
памятью, называемых также ''О-схемами'' (такой способ
памятью, называемых также ''[[О-Схема|О-схемами]]'' (такой способ
описан в определении ''крупноблочной схемы''),
описан в определении ''крупноблочной схемы''),
переменные однозначно сопоставляются раскраской с операндами
переменные однозначно сопоставляются [[раскраска|раскраской]] с операндами
операторов и оператор, засылая значение в переменную, не
операторов и оператор, засылая значение в переменную, не
"интересуется", где это значение будет использовано, а
"интересуется", где это значение будет использовано, а
Строка 17: Строка 17:
переменных. В схемах
переменных. В схемах
над распределенной памятью, называемых
над распределенной памятью, называемых
также ''Р-схемами'', вместо раскраски используется  
также ''[[P-Схема|Р-схемами]]'', вместо раскраски используется  
''информационный граф'', вершинами которого являются операнды
''[[информационный граф]]'', [[вершина|вершинами]] которого являются операнды
операторов, а дуги отражают пересылку значений от выходов к
операторов, а [[дуга|дуги]] отражают пересылку значений от [[выход|выходов]] к
входам. Таким образом, при распределенной памяти оператор,
[[вход|входам]]. Таким образом, при распределенной памяти оператор,
вырабатывая результат, знает, для каких операторов он
вырабатывая результат, знает, для каких операторов он
предназначен, а воспринимая результат, знает, какой оператор
предназначен, а воспринимая результат, знает, какой оператор
Строка 28: Строка 28:
представлением программ с распределенной памятью является
представлением программ с распределенной памятью является
<math>SSA</math>-''форма''.
<math>SSA</math>-''форма''.
[[Файл:Scheme with distributed memory.gif|700px]]


Любая О-схема может быть реализована Р-схемой, но обратное
Любая О-схема может быть реализована Р-схемой, но обратное
Строка 35: Строка 38:
О-схемой.
О-схемой.


См. также ''Крупноблочная схема программ, Неинтерпретированные схемы, Стандартные схемы, Схема программ, Схема с косвенной адресацией, Схемы Мартынюка.''
==См. также ==
* ''[[Крупноблочная схема программ]],''
* ''[[Неинтерпретированные схемы]],''
* ''[[Стандартные схемы]],''
* ''[[Схема программ]],''
* ''[[Схема с косвенной адресацией]],''
* ''[[Схемы Мартынюка]].''
==Литература==
==Литература==
[Ершов/77],
* Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977.
 
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
 


[Касьянов/88]
[[Категория:Теория схем программ]]

Текущая версия от 12:00, 12 сентября 2011

Схема с распределенной памятью (Schema with distributed memory) — Имеется два основных способа идентификации взаимовлияний операторов и переменных в схеме программ — так называемая общая и распределенная память. В схемах над общей памятью, называемых также О-схемами (такой способ описан в определении крупноблочной схемы), переменные однозначно сопоставляются раскраской с операндами операторов и оператор, засылая значение в переменную, не "интересуется", где это значение будет использовано, а используя значение, не "интересуется", какой из операторов это значение выработал. В отличие от общей памяти, где элементы памяти равнодоступны как входам, так и выходам операторов, при распределенной памяти переменные сопоставляются с входами операторов взаимно однозначно, а значение, выработанное на выходе оператора, засылается уже не в одну переменную, а копируется и рассылается в несколько переменных. В схемах над распределенной памятью, называемых также Р-схемами, вместо раскраски используется информационный граф, вершинами которого являются операнды операторов, а дуги отражают пересылку значений от выходов к входам. Таким образом, при распределенной памяти оператор, вырабатывая результат, знает, для каких операторов он предназначен, а воспринимая результат, знает, какой оператор его подготовил. Оба способа присутствуют в современных языках программирования и используются в промежуточных представлениях программ. Наиболее известным промежуточным представлением программ с распределенной памятью является [math]\displaystyle{ SSA }[/math]-форма.

Scheme with distributed memory.gif


Любая О-схема может быть реализована Р-схемой, но обратное неверно. Однако за счет добавления в схему операторов, пересылающих значения с входа на выход, любую Р-схему можно преобразовать в эквивалентную, реализуемую О-схемой.

См. также

Литература

  • Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.