Схема с распределенной памятью: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Схема с распределенной памятью''' (''Scheme with distributed memory'') - Имеется два основн...) |
KEV (обсуждение | вклад) Нет описания правки |
||
(не показаны 3 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
'''Схема с распределенной памятью''' ('' | '''Схема с распределенной памятью''' (''[[Schema with distributed memory]]'') — | ||
Имеется два основных способа идентификации взаимовлияний | Имеется два основных способа идентификации взаимовлияний | ||
операторов и переменных в ''схеме программ'' | операторов и переменных в [[схема программ|''схеме программ'']] — так | ||
называемая общая и распределенная память. В схемах над общей | называемая общая и распределенная память. В схемах над общей | ||
памятью, называемых также ''О-схемами'' (такой способ | памятью, называемых также ''[[О-Схема|О-схемами]]'' (такой способ | ||
описан в определении ''крупноблочной схемы''), | описан в определении ''крупноблочной схемы''), | ||
переменные однозначно сопоставляются раскраской с операндами | переменные однозначно сопоставляются [[раскраска|раскраской]] с операндами | ||
операторов и оператор, засылая значение в переменную, не | операторов и оператор, засылая значение в переменную, не | ||
"интересуется", где это значение будет использовано, а | "интересуется", где это значение будет использовано, а | ||
Строка 17: | Строка 17: | ||
переменных. В схемах | переменных. В схемах | ||
над распределенной памятью, называемых | над распределенной памятью, называемых | ||
также ''Р-схемами'', вместо раскраски используется | также ''[[P-Схема|Р-схемами]]'', вместо раскраски используется | ||
''информационный граф'', вершинами которого являются операнды | ''[[информационный граф]]'', [[вершина|вершинами]] которого являются операнды | ||
операторов, а дуги отражают пересылку значений от выходов к | операторов, а [[дуга|дуги]] отражают пересылку значений от [[выход|выходов]] к | ||
входам. Таким образом, при распределенной памяти оператор, | [[вход|входам]]. Таким образом, при распределенной памяти оператор, | ||
вырабатывая результат, знает, для каких операторов он | вырабатывая результат, знает, для каких операторов он | ||
предназначен, а воспринимая результат, знает, какой оператор | предназначен, а воспринимая результат, знает, какой оператор | ||
Строка 28: | Строка 28: | ||
представлением программ с распределенной памятью является | представлением программ с распределенной памятью является | ||
<math>SSA</math>-''форма''. | <math>SSA</math>-''форма''. | ||
[[Файл:Scheme with distributed memory.gif|700px]] | |||
Любая О-схема может быть реализована Р-схемой, но обратное | Любая О-схема может быть реализована Р-схемой, но обратное | ||
Строка 35: | Строка 38: | ||
О-схемой. | О-схемой. | ||
См. также ''Крупноблочная схема программ, Неинтерпретированные схемы, Стандартные схемы, Схема программ, Схема с косвенной адресацией, Схемы Мартынюка.'' | ==См. также == | ||
* ''[[Крупноблочная схема программ]],'' | |||
* ''[[Неинтерпретированные схемы]],'' | |||
* ''[[Стандартные схемы]],'' | |||
* ''[[Схема программ]],'' | |||
* ''[[Схема с косвенной адресацией]],'' | |||
* ''[[Схемы Мартынюка]].'' | |||
==Литература== | ==Литература== | ||
* Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
[ | [[Категория:Теория схем программ]] |
Текущая версия от 12:00, 12 сентября 2011
Схема с распределенной памятью (Schema with distributed memory) — Имеется два основных способа идентификации взаимовлияний операторов и переменных в схеме программ — так называемая общая и распределенная память. В схемах над общей памятью, называемых также О-схемами (такой способ описан в определении крупноблочной схемы), переменные однозначно сопоставляются раскраской с операндами операторов и оператор, засылая значение в переменную, не "интересуется", где это значение будет использовано, а используя значение, не "интересуется", какой из операторов это значение выработал. В отличие от общей памяти, где элементы памяти равнодоступны как входам, так и выходам операторов, при распределенной памяти переменные сопоставляются с входами операторов взаимно однозначно, а значение, выработанное на выходе оператора, засылается уже не в одну переменную, а копируется и рассылается в несколько переменных. В схемах над распределенной памятью, называемых также Р-схемами, вместо раскраски используется информационный граф, вершинами которого являются операнды операторов, а дуги отражают пересылку значений от выходов к входам. Таким образом, при распределенной памяти оператор, вырабатывая результат, знает, для каких операторов он предназначен, а воспринимая результат, знает, какой оператор его подготовил. Оба способа присутствуют в современных языках программирования и используются в промежуточных представлениях программ. Наиболее известным промежуточным представлением программ с распределенной памятью является [math]\displaystyle{ SSA }[/math]-форма.
Любая О-схема может быть реализована Р-схемой, но обратное
неверно. Однако за счет добавления в схему операторов,
пересылающих значения с входа на выход, любую
Р-схему можно преобразовать в эквивалентную, реализуемую
О-схемой.
См. также
- Крупноблочная схема программ,
- Неинтерпретированные схемы,
- Стандартные схемы,
- Схема программ,
- Схема с косвенной адресацией,
- Схемы Мартынюка.
Литература
- Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977.
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.