Найдем y(x) (рис. 11.1).
(рис 11.1) Схема численного интегрирования
При построении программы вновь воспользуемся оптимальной схемой счета —
способом "пирамиды" (рис. 11.2),
приведенной на рис. 10.7 для
случая n = 5. Здесь $$\nu _{i}$$ — математические адреса вычислителей, причем $$\nu _{i+1} = \nu _{i} + 1$$.
(Предполагаем, что либо на адрес вычислителя указывает тег, либо он принадлежит
определенной области адресного пространства.)
(рис 11.2) Схема счёта интеграла
(рис 11.3) Программа численного интегрирования
По командам 0—2 коммутируется выполнение инструкций формирования содержимого индексных регистров-модификаторов М1—М4.
По командам 3 и 4 на вычислителе с математическим адресом $$\nu _{0}$$ формируется значение 0,5 x (y0 + yn).
Далее следует основной цикл реализации "пирамиды" — цикл на n - 1 повторений (команда 5).
По команде 6 коммутируется последовательная загрузка вычислителей $$y_{1} \Rightarrow \nu _{1}; y_{2} \Rightarrow \nu _{2}; y_{n-1} \Rightarrow \nu _{n-1}$$.
По команде 7 коммутируются операции $$(\nu _{0})+(\nu _{1}) \Rightarrow \nu _{n} , (\nu _{2})+(\nu _{3}) \Rightarrow \nu _{n+1}, \dots , (\nu _{2n-4})+(\nu _{2n-3}) \Rightarrow \nu _{2n-2}$$.
Команда 8 служит для изменения значений индексных регистров.
Команда 9 конец цикла.
По команде 10 коммутируется умножение суммы значений функции, сформированной на вычислителе с математическим адресом $$\nu _{2n-2}$$, на величину $$\delta x$$.
Напомним, что порядок использования математических адресов вычислителей
обусловлен только требованиями организации циклической обработки массива
данных с индексацией и переадресацией, т.е. продиктован законами
программирования
с учетом распараллеливания. При выполнении программы регистры буферов
вычислителей
назначаются
Воспользовавшись формулой вычисления элементов C = A x B,$$C_{ij} = \sum_{k=1}^n a_{ik}b_{kj},\text{ где }i, j = 1, ..., n,$$
(взяв для упрощения случай, когда все три матрицы — квадратные), запишем
алгоритм умножения матриц в виде программы на некотором языке высокого уровня:
for i := 1 step 1 until n do
for j := 1 step 1 until n do
begin
c[i; j] := a[i; 1] x b[1; j];
for k := 1 step 1 until n do c[i; j] := c[i; j] + a[i; j] x b[k; j]
end
(рис 11.4) Программа умножения матриц
Дадим некоторые пояснения к ходу выполнения программы.
В команде 0 значения <a00> и <b00>
являются адресами начала размещения элементов
матриц A и B в ОПД, N — имя
переменной, содержащей значение их размерности n.
По команде 1 происходит загрузка адреса начала размещения элементов матрицы C.
Команда 2 начинает цикл на n повторений (этот цикл
заканчивается командой 16). Команда 3 осуществляет настройку на первый столбец матрицы B.
Команда 4 начинает первый вложенный цикл на n повторений.
Цикл завершается командой 14. Команда 5 коммутирует счет первого слагаемого суммы (в первый раз
должно быть произведено умножение a00x b00 ). По
команде 6 производится настройка индексных регистров, в частности, в первый раз будут выполнены действия
(M5):= a00 ; (M6):= b00 ; (M7):=0.
Команда 7 начинает второй вложенный цикл (заканчивается командой 11). По
команде 8 производится коммутация переадресации по строке матрицы A, по
столбцу матрицы B и переадресации вычислителя. Команда 9 — умножение, в первый
раз выполняется коммутация действия
a01 x b10 => 1.
По команде 10 в первый раз (т.е. при ее первом выполнении) закоммутируется выполнение действия $$\nu _{1} + \nu _{2} \Rightarrow \nu _{3}$$, во второй раз — $$\nu _{1} + \nu _{3} \Rightarrow \nu _{4}$$ и т.д.
Команда 12 задает запись элемента матрицы C.
Команда 13 это переадресация по столбцу, а команда 15 переадресация по строке.
Суть метода заключается в сведении системы линейных уравнений с помощью линейных преобразований к ступенчатому виду. Тогда из последнего уравнения находится значение одного неизвестного. Поднимаясь на одно уравнение вверх, с его помощью находим значение другого неизвестного и т.д. Т.е. предполагается некоторый "проход" по уравнениям системы сверху вниз, а затем обратный проход снизу вверх.
Программу составим для произвольного значения n — числа
уравнений (неизвестных). Однако для наглядности зафиксируем n=4.
Итак, система уравнений имеет вид$$\begin{align*} \left \{ \begin{array}{rcl} a_{00} x_0 + a_{01} x_1 + a_{02} x_2 + a_{03} x_3 = a_{04} \\ a_{10} x_0 + a_{11} x_1 + a_{12} x_2 + a_{13} x_3 = a_{14} \\ a_{20} x_0 + a_{21} x_1 + a_{22} x_2 + a_{23} x_3 = a_{24} \\ a_{30} x_0 + a_{31} x_1 + a_{32} x_2 + a_{33} x_3 = a_{34} \\ \end{array} \right. \end{align*}$$
Умножим второе уравнение на r1 = a00 / a10 и вычтем из
него первое уравнение. Получим новое уравнение, в котором коэффициенты находятся из выражения$$a_{1j}^{(1)} = \frac{a_{1j} \times a_{00}}{a_{10}} - a_{0j},$$
при этом$$a_{10}^{(1)} = \frac{a_{10} \times a_{00}}{a_{10}} - a_{00} = 0.$$
Аналогично, умножая все последующие (k = 2, ...) уравнения
на соответствующие величины a00 / ak0 и вычитая первое уравнение, избавимся от
вхождения в них переменной x0.
Произведен первый шаг в получении ступенчатой системы уравнений (рис. 11.5). При этом мы, конечно, считаем, что $$a_{10} \ne 0$$. Если это не так, но выполняется известное условие существования единственного решения системы, то надо так переупорядочить (переобозначить) вхождение переменных, чтобы нужный коэффициент был отличен от нуля. Такое переупорядочение переменных в приведенной ниже программе предусмотрено.
(рис 11.5) Схема счёта методом Гаусса
На втором шаге вычитаем преобразованное второе уравнение из всех последующих
уравнений, предварительно умноженных на r2 = a11(1) /
ak1(1). Таким образом мы избавляемся от
вхождения в них второй переменной и т.д.
На последнем шаге таких преобразований получаем выражение для нахождения последней переменной. В нашем примере это
a33(3) x3 = a34(3).
Найденное значение x3 подставим в уравнение
a22(2) x2 + a23(2) x3 = a24(2).
и найдем значение x2 и т.д.
(рис 11.6a) Программа решения системы линейных уравнений
(рис 11.6b) Окончание
По команде 0 загружаются число переменных в уравнении и адреса коэффициентов. Команды $$1 \div 5$$ производят начальное формирование индексных регистров.
Команда 6 начинает основной цикл на n-1 повторений.
По команде 7 загружаются модификаторы, причем после первого выполнения будут справедливы равенства:
(M4) = a00; (M5) = a11; (M6) = a01.
Команда 8 проверяет равенство a00 = 0 и при несравнении
задает переход на выполнение команды 22.
По команде 9 также загружаются модификаторы, и после первого выполнения
(при a10 = 0 ) будут справедливы равенства: (M7) = a00; (M8) = a00; (M9) = < l0 >.
По команде 10 начинается вложенный цикл на n - 1, ..., 1
повторений поиска уравнения, у которого
По команде 11 производится переход по условию; в первый раз при a10 = 0 — переход к выполнению команды 19.
Команда 12 начинает очередной вложенный цикл. В первый раз выполняются действия:
a00 => l0, a01 => l1 и т.д. (команда 13),
a10 => a00, a11 => a01 и т.д. (команда 14),
l0 => a10, l1 => a11 и т.д.
(команда 15) — таким образом, уравнения меняются
местами. Выполнение цикла заканчивается по команде 17.
После нахождения старшего ненулевого коэффициента и перестановки уравнений поиск заканчивается, поэтому команда 18 задает принудительный выход из предыдущего цикла.
Команда 19 позволяет произвести переход к анализу следующего уравнения.
Останов по команде 21 означает, что все старшие коэффициенты нулевые и поэтому нельзя построить треугольную матрицу с определителем, не равным нулю.
Команда 22 начинает цикл на n - 1, ..., 1 повторений
преобразования уравнений. Команда 24, переход по сравнению, позволяет пропустить уравнение, у которого
Команда 26 — начало вложенного цикла на n, n - 1, ..., 2
повторений преобразования
коэффициентов одного уравнения. В первый раз по командам 27 и 28 будут
закоммутированы вычисление и отсылка:$$a_{11} \times \frac{a_{00}}{a_{10}} - a_{01} \Longrightarrow a_{11}.$$
По команде 31 увеличиваются на единицу значения индексных регистров, что позволяет при следующей итерации цикла перейти к анализу следующего уравнения.
Команда 33 в первый раз определяет переход от a00 к a11(1) ; по команде 34 происходит
уменьшение граничных значений параметров
По командам 36 и 37 изменяется содержимое индексных регистров:
(M2) = <x0>,\, (l1) = (R2) = n - 1, (M2) = <xn-1>,
а команда 38 коммутирует выполнение операции деления$$x_{n-1} = \frac{a_{n-1,n}}{a^{(n-1)}_{n-1,n-1}}$$
Команда 39 начинает цикл на n - 1 повторение, а команда 41 —
вложенный цикл на n - 1, n - 2, ..., 1 повторение.
По командам 43 последовательно в каждой итерации цикла коммутируется выполнение умножения:
an-2, n-1 x xn-1, an-3, n-1 x xn-1 и т.д.,
а по команде 44 — вычитания: an-2,n-1 := an-2, n - an-2, n-1 x xn-1, an-3, n-1 :=
an-3, n - an-3, n-1 x xn-1 и т.д.
После этого вложенный цикл заканчивается (команда 45), и изменяются значения
индексных xn-2, xn-3 и т.д. (команда 48).
В первый раз$$x_{n-2} = \frac{a_{n-2, n-1}}{a_{n-2, n-2}}.$$ Выполнение программы заканчивается по команде 49.
Выбор определенной, охарактеризованной выше, структуры ПВС (ввиду смешанного
характера реализованной в ней модели вычислений) ведет к необходимости решения
задач наилучшего выбора входного языка системы и методов трансляции программ
во внутреннее представление. В большинстве известных проектов потоковых ВС их
разработчики в качестве входных языков используют специально создаваемые
потоковые языки программирования, среди которых наиболее известны
Другими свойствами потоковых языков являются: соблюдение правила
единственного присваивания, отсутствие глобальных переменных, отказ от возможности для
программиста управлять распределением памяти. Все это позволяет предельно
снизить ограничения на порядок выполнения операторов-функций. Например, программа на
языке
В то же время базирование указанных языков на функциональной парадигме порождает ряд проблем, не находящих простого и эффективного решения. В частности, любое (даже частичное) изменение структуры данных интерпретируется как порождение новой структуры, требующей полного дублирования исходной структуры. Понятно, что это влечет многократное увеличение нагрузки на память и коммуникационные сети.
Информационные связи, существующие в программах, препятствуют параллельному и независимому исполнению операторов. Очевидно, что свойства потоковых языков, указанные выше, служат именно устранению из программ информационных связей некоторых типов.
Например, операторы (11.2) и (11.3) во фрагменте программы
a := f1 (x1, ..., xn) (11.1)
b := f2 (y1, ..., ym, a) (11.2)
a := f3 (z1, ..., zl) (11.3)
не могут быть выполнены одновременно, поскольку оператор (11.3) меняет значение
переменной a, используемой оператором (11.2). Фактически же эти
операторы независимы; зависимость возникает лишь в связи с повторным использованием
одного и того же имени. В потоковых языках, согласно правилу единственного
присваивания, каждая переменная может быть использована в левой части оператора
присваивания только один раз. Таким образом, в операторе (11.3) переменная a должна быть переименована, например, в c, и
зависимость между вторым и третьим операторами исчезнет. В то же время информационная зависимость между
операторами (11.1) и (11.2) устранена быть не может, и эти два оператора должны выполняться
именно в указанном порядке.
Очевидно (если оставить вне рассмотрения влияние принципа единственного присваивания на всю идеологию организации вычислений в некоторых моделях потоковой обработки), что точно такой метод переименования можно формально использовать и в любом традиционном процедурном языке. Причем, чтобы не налагать ограничений на использование программистом имен переменных, это переименование может быть произведено и на этапе трансляции. Методы анализа программы при этом аналогичны методам, применяемым в оптимизирующих трансляторах. Другие свойства потоковых языков, очевидно, тоже могут быть привнесены в традиционные алгоритмические языки.
При выборе входного языка ПВС необходимо принять во внимание и следующие
соображения. Любая программа на любом языке как запись выполняемого алгоритма
содержит в себе всю информацию о возможности ее параллельного исполнения. Речь
может идти лишь о сложности ее извлечения. Часть информации может быть
извлечена при трансляции и
Поэтому, учитывая преобладающую долю математического обеспечения в общей стоимости современных вычислительных систем, целесообразно оценить возможность использования существующих алгоритмических языков в рассматриваемой потоковой вычислительной системе.
Определим оператор присваивания, используя общепринятую нотацию, близкую к
<оператор присваивания> :: = <имя> := <выражение>
Имя здесь имя простой переменной (переменные с индексами для упрощения не рассматриваем). Выражения могут быть арифметическими и логическими, простыми и условными. Синтаксис их аналогичен синтаксису соответствующих конструкций языков высокого уровня:
$$<условное выражение> ::= if <отношение> then <выражение> else <выражение> \downarrow$$
Выражения в правой части определения, в свою очередь, могут быть условными.
Ограничитель " $$\downarrow$$ " введен для упрощения
определения конца условного выражения.
При трансляции условные выражения сначала преобразуются в бесскобочное
представление, в котором все ограничители if, then, else, $$\downarrow$$ сохраняют свой
порядок, а заключенные между ними арифметические и логические выражения
приобретают вид
Операторы присваивания преобразуются в бесскобочную запись так же, как и выражения, причем знак присваивания ":=" считаем относящимся к некоторой двуместной операции присваивания.
Рассмотрим оператор присваивания:
$$x := a + b \ x \ if (m+n) > p \ \ then \ \ d + if \ m < q \ \ then \ r + t \ \ else \ r \downarrow else \ \ c \downarrow$$
Его
$$xab \ if \ mn + p > then \ d \ if \ mq < then \ rt + else \ r \downarrow else \ c \downarrow + :=$$ (11.4)
(FE) бесскобочной записи. NE:=FE. N:=1. Перейти к п. 3.(NE). Если это последний элемент
бесскобочной записи, то при N > 2 перейти к п. 1, а при N <= 2
— перейти к п. 22.NE — операнд, то перейти к п. 2.NE — знак операции, то перейти к п. 8.NE — ограничитель if, то перейти к п. 16.NE — один из ограничителей $$then, else, \downarrow$$, то перейти к п. 2.NE . Если это последний элемент бесскобочной записи,
то перейти к п. 1.NE — знак операции, то перейти к п. 10.NE — операнд, то перейти к п. 13, иначе —
перейти к п. 5.NE.NE — знак операции, то перейти к п. 13.NE — операнд, то перейти к п. 2, иначе — перейти к п. 5.NE.<операнд>
<операнд> <знак>, то перейти к п. 18, иначе N := N - 3, перейти к п. 2.NE. Если это ограничитель then, то два раза взять NE и перейти к
п. 19. Иначе N := N -4, перейти к п. 2.<операнд> else, то
два раза взять NE. Перейти к п. 20. Иначе N := N - 2 и перейти к п. 2.N := N - 2 и перейти к п. 2.a, b, c,
d — операнды, а $$\otimes$$ — знак
операции отношения, подставляется математический адрес вычислителя-исполнителя,
на котором формируется результат четырехместной команды. Перейти к п. 10.В этом алгоритме N — указатель на очередной рассматриваемый
элемент бесскобочной записи. Действие "Взять NE " означает перемещение
указателя на следующий элемент, при этом значение N увеличивается на единицу. Изменение значения N, в свою очередь, означает перемещение указателя вправо или влево. Под элементом бесскобочной
записи понимаются имена переменных, знаки операций, ограничители языка и
математические адреса вычислителей. Если не указано противное, то после выполнения действий,
предписанных очередным пунктом алгоритма, происходит переход на следующий по
порядку пункт.
На рис. 11.7 представлена результирующая
(рис 11.7) Программа коммутации
Приведенный алгоритм трансляции формирует программу коммутации на основе
поярусного анализа графа, соответствующего оператору присваивания. При каждом
проходе транслятором бесскобочной записи формируются все команды, операнды
которых доступны в этот момент. При первом проходе формируются команда 0,
задающая сложение операндов m и n на вычислителе $$\nu _{0}$$, и команда 1, задающая сложение
операндов r и t на вычислителе $$\nu _{1}$$.
$$xab \ if \nu _{0}p > then \ d \ if \ mq < then \ \nu _{1} else \ r \downarrow else \ c \downarrow + :=$$.
При втором проходе не обнаруживается арифметических операций, готовых к
выполнению. Формируется пятиадресная команда 2. Она задает сравнение операндов m и q на вычислителе $$\nu _{2}$$. В
зависимости от результата сравнения итогом выполнения
данной команды (сформированной по ней инструкции) будет результат счета на
вычислителе $$\nu _{1}$$ или же r.
$$xab if \nu _{0}p > then \ d\ nu _{2} + else c \ \downarrow x + :=$$.
Последующие проходы сформируют команды 3 и 4 и
$$xab\ \nu _{4} x + :=$$.
В результате последующих проходов формируются команды 5 и 6.
Отметим, что команда 6 могла бы иметь вид $$+a\nu _{5}\nu _{6}$$, а
Вместе с тем, при необходимости использования имен вычислителей-исполнителей для именования операндов можно формировать имена в широком диапазоне выбора, имеющем два крайних случая.
Можно при каждом новом выборе значения математического адреса вычислителя использовать увеличенную (на единицу) величину ранее использованного значения. Именно так происходит в рассмотренном примере.
Другой крайний случай основан на принципе "экономии" адресов вычислителей. Он опирается на то, что результат операции используется единственный раз. Это означает, что и каждое объявленное имя вычислителя используется только один раз. Поэтому после использования это же имя может объявляться повторно, и благодаря механизму виртуализации ресурсов никакой коллизии не произойдет. Так, в команде 3 для обозначения вычислителя-исполнителя вместо $$\nu _{3}$$ можно использовать математический адрес $$\nu _{1}$$. Вместо $$\nu _{4}$$ в команде 4 повторно можно использовать адрес $$\nu _{2}$$ и т.д.
Наибольшая эффективность в работе ПВС может быть достигнута при значительном
опережении процессом коммутации процесса вычислений, благодаря чему динамически
обеспечивается достаточная загрузка вычислителей
Как показывает анализ прикладных программ, один оператор присваивания редко содержит более десяти переменных в правой части. С другой стороны, несколько подряд расположенных операторов присваивания, содержащих в общей сложности несколько десятков переменных, ситуация, которая встречается достаточно часто. Поэтому желательно иметь возможность именно такую последовательность операторов присваивания считать непрерываемым участком программы.
Рассмотрим фрагмент программы:
R := a x b + c x d; P := R + d x p; R := m x n.
При этом не обязательно соблюдается правило единственного присваивания.
Запишем соответствующие этим операторам бесскобочные записи в одну строку:
Rab x cd x + := PRdp x + := Rmn x :=. (11.5)
Пусть транслятор анализирует ее как единое целое. Тогда для сохранения информационной зависимости между операторами необходимо следовать следующим правилам:
NE — операнд, то анализируется, не совпадает ли он с какой-либо
ранее отмеченной переменной, которой производится присваивание, кроме отмеченной
последней. Если совпадает, то N := N+1. Производится дальнейший
анализ NE — переход к п. 2 изложенного выше алгоритма.NE — переменная, которой производится присваивание
(она находится правее знака ":="), то наряду с отметкой ее в списке
подобных переменных проверяется, не совпадает ли она с какой-либо ранее отмеченной
переменной, которой производится присваивание, или с любым операндом, входящим
в запись левее NE. Если совпадает, то N := N+1. Далее
по алгоритму трансляции, изложенному выше.Эти два правила, которым следует работа
В алгоритм трансляции необходимо внести еще одно изменение.
Если двуместная операция соответствует присваиванию, то после формирования
(рис 11.8) Удаление операции присваивания
После формирования команд $$0 \div 3$$
$$R\nu _{0}\nu _{1} + := PR\nu _{2} + := R\nu _{3} :=$$.
Первое вхождение в эту запись операнда R в качестве
переменной, которой присваивается значение, блокирует формирование последующих команд, использующих
этот же операнд. Поэтому при втором проходе формируется только команда 4, в
которой первоначально по третьему адресу указан адрес вычислителя-исполнителя $$\nu _{4}$$.
$$R\nu _{4} := PR\nu _{2} + := R\nu _{3} :=$$.
Во время третьего прохода уточняется команда 4 подстановкой по адресу
результата адреса переменной R. Первые три символа из записи исключаются.
Тогда открывается возможность сформировать команду 5, использующую новое значение R. При этом вместо комбинации символов $$R\nu _{2}+$$ формируется адрес
вычислителя $$\nu _{5}$$. Поскольку слева все вхождения R исключены, формируется команда 6
присваивания нового значения R.
При четвертом проходе формируется команда 7.
Задача параллельного выполнения операторов цикла может решаться посредством либо распараллеливания по итерациям, либо распараллеливания операторов внутри тела цикла. Распараллеливание по итерациям может быть применено для распределения групп повторений тела цикла по процессорам ПВС. Распараллеливание же внутри тела цикла может производиться так же, как и для последовательности операторов.
Определим оператор
<оператор
for <параметр цикла> := A1 step A2 until A3 do S
В этом определении A1, A2, A3 — арифметические выражения, а S — оператор (тело цикла).
В ПВС может быть использован подход, аналогичный "раскрутке" циклов.
Оператор цикла транслируется в программу коммутации, схема которой имеет вид, представленный на рис. 11.9.
(рис 11.9) Программа цикла
Команды $$1 \div k-1$$ соответствуют вычислению значений
арифметических выражений A1, A2 и A3, если они не являются константами или именами
переменных. Команда k — организация цикла (N — конец цикла (КЦ).
Между S. Эта часть программы коммутации образуется по правилам трансляции
соответствующей конструкции языка. В частности, если тело цикла — оператор присваивания
(последовательность операторов присваивания), то трансляция его происходит
по приведенному алгоритму.
a1, a2, a3 выражений A1, A2 и A3.
Далее осуществляется коммутация выполнения команд, составляющих тело цикла S. Если в теле цикла отсутствуют операторы перехода за границы цикла, то при
обработке процессором команды КЦ содержимое регистра СЦ уменьшается на единицу. В случае
неравенства его нулю коммутация продолжается с первой команды тела цикла.
В противном случае далее коммутируется выполнение команды N+1,
следующей за командой КЦ. Таким образом, осуществляется непрерывная коммутация всего цикла,
что обеспечивает возможность параллельного выполнения команд тела цикла.
Такому одновременному выполнению могут мешать конфликты между итерациями, связанные с использованием одной и той же переменной во всех итерациях. Например, в цикле
for i := 1 step 1 until 5 do
begin
x := a[i];
R[i] := x x b;
Q[i] := x / b;
end
все итерации фактически будут выполняться последовательно, поскольку
образуется x. В то же время очевидно, что информационно итерации друг с другом не связаны, поэтому
можно добиться их параллельного выполнения, применив переименование переменных.
Переменная х заменяется на x[i], компоненту массива x [1...5]. Цикл
принимает вид
for i := 1 step 1 until 5 do
begin
x[i] := a[i];
R[i] := x[i] x b;
Q[i] := x[i] / b;
end
Теперь все пять его итераций могут выполняться одновременно.
Очень важно, что при асинхронном выполнении итераций не возникает ошибок, которые связаны с нарушением порядка вычислений, предписываемого логическими связями между переменными. Рассмотрим следующий цикл
for i := 1 step 1 until 2 do
begin
x[i] := a[i];
R[i] := x[i] x b;
R[i + 1] := x[i] / b;
print (R[i], R[i + 1]);
end
Все вычисления в обеих итерациях могут выполняться независимо друг от друга
и одновременно. Правильная же работа операторов печати гарантирована тем,
что команды программы коммутации обрабатываются процессором последовательно и
заявки на запись и считывание к ячейке, в которой должно находиться значение R[2], выдаваемые при коммутации выполнения первой и второй итераций, будут упорядочены.
При трансляции операторов цикла итерационного типа,
<оператор цикла итерационного типа> ::= for <параметр цикла>
:= A1;A2 while B do S,
где A1, A2 — арифметические выражения, B —
логическое выражение, S —
оператор, образуется
Процесс коммутации, дойдя до команды условного перехода,
приостанавливается, ожидая прихода (после выполнения соответствующих
вычислений) информации о команде, начиная с которой его необходимо
продолжить. Таким образом, в точках условного перехода процесс вычислений
"догоняет" процесс коммутации. Подобные ситуации крайне
нежелательны, поскольку приостановление процесса коммутации прекращает загрузку
вычислителей
Найдем y(x) (рис. 11.1).
(рис 11.1) Схема численного интегрирования
При построении программы вновь воспользуемся оптимальной схемой счета —
способом "пирамиды" (рис. 11.2),
приведенной на рис. 10.7 для
случая n = 5. Здесь $$\nu _{i}$$ — математические адреса вычислителей, причем $$\nu _{i+1} = \nu _{i} + 1$$.
(Предполагаем, что либо на адрес вычислителя указывает тег, либо он принадлежит
определенной области адресного пространства.)
(рис 11.2) Схема счёта интеграла
(рис 11.3) Программа численного интегрирования
По командам 0—2 коммутируется выполнение инструкций формирования содержимого индексных регистров-модификаторов М1—М4.
По командам 3 и 4 на вычислителе с математическим адресом $$\nu _{0}$$ формируется значение 0,5 x (y0 + yn).
Далее следует основной цикл реализации "пирамиды" — цикл на n - 1 повторений (команда 5).
По команде 6 коммутируется последовательная загрузка вычислителей $$y_{1} \Rightarrow \nu _{1}; y_{2} \Rightarrow \nu _{2}; y_{n-1} \Rightarrow \nu _{n-1}$$.
По команде 7 коммутируются операции $$(\nu _{0})+(\nu _{1}) \Rightarrow \nu _{n} , (\nu _{2})+(\nu _{3}) \Rightarrow \nu _{n+1}, \dots , (\nu _{2n-4})+(\nu _{2n-3}) \Rightarrow \nu _{2n-2}$$.
Команда 8 служит для изменения значений индексных регистров.
Команда 9 конец цикла.
По команде 10 коммутируется умножение суммы значений функции, сформированной на вычислителе с математическим адресом $$\nu _{2n-2}$$, на величину $$\delta x$$.
Напомним, что порядок использования математических адресов вычислителей
обусловлен только требованиями организации циклической обработки массива
данных с индексацией и переадресацией, т.е. продиктован законами
программирования
с учетом распараллеливания. При выполнении программы регистры буферов
вычислителей
назначаются
Воспользовавшись формулой вычисления элементов C = A x B,$$C_{ij} = \sum_{k=1}^n a_{ik}b_{kj},\text{ где }i, j = 1, ..., n,$$
(взяв для упрощения случай, когда все три матрицы — квадратные), запишем
алгоритм умножения матриц в виде программы на некотором языке высокого уровня:
for i := 1 step 1 until n do
for j := 1 step 1 until n do
begin
c[i; j] := a[i; 1] x b[1; j];
for k := 1 step 1 until n do c[i; j] := c[i; j] + a[i; j] x b[k; j]
end
(рис 11.4) Программа умножения матриц
Дадим некоторые пояснения к ходу выполнения программы.
В команде 0 значения <a00> и <b00>
являются адресами начала размещения элементов
матриц A и B в ОПД, N — имя
переменной, содержащей значение их размерности n.
По команде 1 происходит загрузка адреса начала размещения элементов матрицы C.
Команда 2 начинает цикл на n повторений (этот цикл
заканчивается командой 16). Команда 3 осуществляет настройку на первый столбец матрицы B.
Команда 4 начинает первый вложенный цикл на n повторений.
Цикл завершается командой 14. Команда 5 коммутирует счет первого слагаемого суммы (в первый раз
должно быть произведено умножение a00x b00 ). По
команде 6 производится настройка индексных регистров, в частности, в первый раз будут выполнены действия
(M5):= a00 ; (M6):= b00 ; (M7):=0.
Команда 7 начинает второй вложенный цикл (заканчивается командой 11). По
команде 8 производится коммутация переадресации по строке матрицы A, по
столбцу матрицы B и переадресации вычислителя. Команда 9 — умножение, в первый
раз выполняется коммутация действия
a01 x b10 => 1.
По команде 10 в первый раз (т.е. при ее первом выполнении) закоммутируется выполнение действия $$\nu _{1} + \nu _{2} \Rightarrow \nu _{3}$$, во второй раз — $$\nu _{1} + \nu _{3} \Rightarrow \nu _{4}$$ и т.д.
Команда 12 задает запись элемента матрицы C.
Команда 13 это переадресация по столбцу, а команда 15 переадресация по строке.
Суть метода заключается в сведении системы линейных уравнений с помощью линейных преобразований к ступенчатому виду. Тогда из последнего уравнения находится значение одного неизвестного. Поднимаясь на одно уравнение вверх, с его помощью находим значение другого неизвестного и т.д. Т.е. предполагается некоторый "проход" по уравнениям системы сверху вниз, а затем обратный проход снизу вверх.
Программу составим для произвольного значения n — числа
уравнений (неизвестных). Однако для наглядности зафиксируем n=4.
Итак, система уравнений имеет вид$$\begin{align*} \left \{ \begin{array}{rcl} a_{00} x_0 + a_{01} x_1 + a_{02} x_2 + a_{03} x_3 = a_{04} \\ a_{10} x_0 + a_{11} x_1 + a_{12} x_2 + a_{13} x_3 = a_{14} \\ a_{20} x_0 + a_{21} x_1 + a_{22} x_2 + a_{23} x_3 = a_{24} \\ a_{30} x_0 + a_{31} x_1 + a_{32} x_2 + a_{33} x_3 = a_{34} \\ \end{array} \right. \end{align*}$$
Умножим второе уравнение на r1 = a00 / a10 и вычтем из
него первое уравнение. Получим новое уравнение, в котором коэффициенты находятся из выражения$$a_{1j}^{(1)} = \frac{a_{1j} \times a_{00}}{a_{10}} - a_{0j},$$
при этом$$a_{10}^{(1)} = \frac{a_{10} \times a_{00}}{a_{10}} - a_{00} = 0.$$
Аналогично, умножая все последующие (k = 2, ...) уравнения
на соответствующие величины a00 / ak0 и вычитая первое уравнение, избавимся от
вхождения в них переменной x0.
Произведен первый шаг в получении ступенчатой системы уравнений (рис. 11.5). При этом мы, конечно, считаем, что $$a_{10} \ne 0$$. Если это не так, но выполняется известное условие существования единственного решения системы, то надо так переупорядочить (переобозначить) вхождение переменных, чтобы нужный коэффициент был отличен от нуля. Такое переупорядочение переменных в приведенной ниже программе предусмотрено.
(рис 11.5) Схема счёта методом Гаусса
На втором шаге вычитаем преобразованное второе уравнение из всех последующих
уравнений, предварительно умноженных на r2 = a11(1) /
ak1(1). Таким образом мы избавляемся от
вхождения в них второй переменной и т.д.
На последнем шаге таких преобразований получаем выражение для нахождения последней переменной. В нашем примере это
a33(3) x3 = a34(3).
Найденное значение x3 подставим в уравнение
a22(2) x2 + a23(2) x3 = a24(2).
и найдем значение x2 и т.д.
(рис 11.6a) Программа решения системы линейных уравнений
(рис 11.6b) Окончание
По команде 0 загружаются число переменных в уравнении и адреса коэффициентов. Команды $$1 \div 5$$ производят начальное формирование индексных регистров.
Команда 6 начинает основной цикл на n-1 повторений.
По команде 7 загружаются модификаторы, причем после первого выполнения будут справедливы равенства:
(M4) = a00; (M5) = a11; (M6) = a01.
Команда 8 проверяет равенство a00 = 0 и при несравнении
задает переход на выполнение команды 22.
По команде 9 также загружаются модификаторы, и после первого выполнения
(при a10 = 0 ) будут справедливы равенства: (M7) = a00; (M8) = a00; (M9) = < l0 >.
По команде 10 начинается вложенный цикл на n - 1, ..., 1
повторений поиска уравнения, у которого
По команде 11 производится переход по условию; в первый раз при a10 = 0 — переход к выполнению команды 19.
Команда 12 начинает очередной вложенный цикл. В первый раз выполняются действия:
a00 => l0, a01 => l1 и т.д. (команда 13),
a10 => a00, a11 => a01 и т.д. (команда 14),
l0 => a10, l1 => a11 и т.д.
(команда 15) — таким образом, уравнения меняются
местами. Выполнение цикла заканчивается по команде 17.
После нахождения старшего ненулевого коэффициента и перестановки уравнений поиск заканчивается, поэтому команда 18 задает принудительный выход из предыдущего цикла.
Команда 19 позволяет произвести переход к анализу следующего уравнения.
Останов по команде 21 означает, что все старшие коэффициенты нулевые и поэтому нельзя построить треугольную матрицу с определителем, не равным нулю.
Команда 22 начинает цикл на n - 1, ..., 1 повторений
преобразования уравнений. Команда 24, переход по сравнению, позволяет пропустить уравнение, у которого
Команда 26 — начало вложенного цикла на n, n - 1, ..., 2
повторений преобразования
коэффициентов одного уравнения. В первый раз по командам 27 и 28 будут
закоммутированы вычисление и отсылка:$$a_{11} \times \frac{a_{00}}{a_{10}} - a_{01} \Longrightarrow a_{11}.$$
По команде 31 увеличиваются на единицу значения индексных регистров, что позволяет при следующей итерации цикла перейти к анализу следующего уравнения.
Команда 33 в первый раз определяет переход от a00 к a11(1) ; по команде 34 происходит
уменьшение граничных значений параметров
По командам 36 и 37 изменяется содержимое индексных регистров:
(M2) = <x0>,\, (l1) = (R2) = n - 1, (M2) = <xn-1>,
а команда 38 коммутирует выполнение операции деления$$x_{n-1} = \frac{a_{n-1,n}}{a^{(n-1)}_{n-1,n-1}}$$
Команда 39 начинает цикл на n - 1 повторение, а команда 41 —
вложенный цикл на n - 1, n - 2, ..., 1 повторение.
По командам 43 последовательно в каждой итерации цикла коммутируется выполнение умножения:
an-2, n-1 x xn-1, an-3, n-1 x xn-1 и т.д.,
а по команде 44 — вычитания: an-2,n-1 := an-2, n - an-2, n-1 x xn-1, an-3, n-1 :=
an-3, n - an-3, n-1 x xn-1 и т.д.
После этого вложенный цикл заканчивается (команда 45), и изменяются значения
индексных xn-2, xn-3 и т.д. (команда 48).
В первый раз$$x_{n-2} = \frac{a_{n-2, n-1}}{a_{n-2, n-2}}.$$ Выполнение программы заканчивается по команде 49.
Выбор определенной, охарактеризованной выше, структуры ПВС (ввиду смешанного
характера реализованной в ней модели вычислений) ведет к необходимости решения
задач наилучшего выбора входного языка системы и методов трансляции программ
во внутреннее представление. В большинстве известных проектов потоковых ВС их
разработчики в качестве входных языков используют специально создаваемые
потоковые языки программирования, среди которых наиболее известны
Другими свойствами потоковых языков являются: соблюдение правила
единственного присваивания, отсутствие глобальных переменных, отказ от возможности для
программиста управлять распределением памяти. Все это позволяет предельно
снизить ограничения на порядок выполнения операторов-функций. Например, программа на
языке
В то же время базирование указанных языков на функциональной парадигме порождает ряд проблем, не находящих простого и эффективного решения. В частности, любое (даже частичное) изменение структуры данных интерпретируется как порождение новой структуры, требующей полного дублирования исходной структуры. Понятно, что это влечет многократное увеличение нагрузки на память и коммуникационные сети.
Информационные связи, существующие в программах, препятствуют параллельному и независимому исполнению операторов. Очевидно, что свойства потоковых языков, указанные выше, служат именно устранению из программ информационных связей некоторых типов.
Например, операторы (11.2) и (11.3) во фрагменте программы
a := f1 (x1, ..., xn) (11.1)
b := f2 (y1, ..., ym, a) (11.2)
a := f3 (z1, ..., zl) (11.3)
не могут быть выполнены одновременно, поскольку оператор (11.3) меняет значение
переменной a, используемой оператором (11.2). Фактически же эти
операторы независимы; зависимость возникает лишь в связи с повторным использованием
одного и того же имени. В потоковых языках, согласно правилу единственного
присваивания, каждая переменная может быть использована в левой части оператора
присваивания только один раз. Таким образом, в операторе (11.3) переменная a должна быть переименована, например, в c, и
зависимость между вторым и третьим операторами исчезнет. В то же время информационная зависимость между
операторами (11.1) и (11.2) устранена быть не может, и эти два оператора должны выполняться
именно в указанном порядке.
Очевидно (если оставить вне рассмотрения влияние принципа единственного присваивания на всю идеологию организации вычислений в некоторых моделях потоковой обработки), что точно такой метод переименования можно формально использовать и в любом традиционном процедурном языке. Причем, чтобы не налагать ограничений на использование программистом имен переменных, это переименование может быть произведено и на этапе трансляции. Методы анализа программы при этом аналогичны методам, применяемым в оптимизирующих трансляторах. Другие свойства потоковых языков, очевидно, тоже могут быть привнесены в традиционные алгоритмические языки.
При выборе входного языка ПВС необходимо принять во внимание и следующие
соображения. Любая программа на любом языке как запись выполняемого алгоритма
содержит в себе всю информацию о возможности ее параллельного исполнения. Речь
может идти лишь о сложности ее извлечения. Часть информации может быть
извлечена при трансляции и
Поэтому, учитывая преобладающую долю математического обеспечения в общей стоимости современных вычислительных систем, целесообразно оценить возможность использования существующих алгоритмических языков в рассматриваемой потоковой вычислительной системе.
Определим оператор присваивания, используя общепринятую нотацию, близкую к
<оператор присваивания> :: = <имя> := <выражение>
Имя здесь имя простой переменной (переменные с индексами для упрощения не рассматриваем). Выражения могут быть арифметическими и логическими, простыми и условными. Синтаксис их аналогичен синтаксису соответствующих конструкций языков высокого уровня:
$$<условное выражение> ::= if <отношение> then <выражение> else <выражение> \downarrow$$
Выражения в правой части определения, в свою очередь, могут быть условными.
Ограничитель " $$\downarrow$$ " введен для упрощения
определения конца условного выражения.
При трансляции условные выражения сначала преобразуются в бесскобочное
представление, в котором все ограничители if, then, else, $$\downarrow$$ сохраняют свой
порядок, а заключенные между ними арифметические и логические выражения
приобретают вид
Операторы присваивания преобразуются в бесскобочную запись так же, как и выражения, причем знак присваивания ":=" считаем относящимся к некоторой двуместной операции присваивания.
Рассмотрим оператор присваивания:
$$x := a + b \ x \ if (m+n) > p \ \ then \ \ d + if \ m < q \ \ then \ r + t \ \ else \ r \downarrow else \ \ c \downarrow$$
Его
$$xab \ if \ mn + p > then \ d \ if \ mq < then \ rt + else \ r \downarrow else \ c \downarrow + :=$$ (11.4)
(FE) бесскобочной записи. NE:=FE. N:=1. Перейти к п. 3.(NE). Если это последний элемент
бесскобочной записи, то при N > 2 перейти к п. 1, а при N <= 2
— перейти к п. 22.NE — операнд, то перейти к п. 2.NE — знак операции, то перейти к п. 8.NE — ограничитель if, то перейти к п. 16.NE — один из ограничителей $$then, else, \downarrow$$, то перейти к п. 2.NE . Если это последний элемент бесскобочной записи,
то перейти к п. 1.NE — знак операции, то перейти к п. 10.NE — операнд, то перейти к п. 13, иначе —
перейти к п. 5.NE.NE — знак операции, то перейти к п. 13.NE — операнд, то перейти к п. 2, иначе — перейти к п. 5.NE.<операнд>
<операнд> <знак>, то перейти к п. 18, иначе N := N - 3, перейти к п. 2.NE. Если это ограничитель then, то два раза взять NE и перейти к
п. 19. Иначе N := N -4, перейти к п. 2.<операнд> else, то
два раза взять NE. Перейти к п. 20. Иначе N := N - 2 и перейти к п. 2.N := N - 2 и перейти к п. 2.a, b, c,
d — операнды, а $$\otimes$$ — знак
операции отношения, подставляется математический адрес вычислителя-исполнителя,
на котором формируется результат четырехместной команды. Перейти к п. 10.В этом алгоритме N — указатель на очередной рассматриваемый
элемент бесскобочной записи. Действие "Взять NE " означает перемещение
указателя на следующий элемент, при этом значение N увеличивается на единицу. Изменение значения N, в свою очередь, означает перемещение указателя вправо или влево. Под элементом бесскобочной
записи понимаются имена переменных, знаки операций, ограничители языка и
математические адреса вычислителей. Если не указано противное, то после выполнения действий,
предписанных очередным пунктом алгоритма, происходит переход на следующий по
порядку пункт.
На рис. 11.7 представлена результирующая
(рис 11.7) Программа коммутации
Приведенный алгоритм трансляции формирует программу коммутации на основе
поярусного анализа графа, соответствующего оператору присваивания. При каждом
проходе транслятором бесскобочной записи формируются все команды, операнды
которых доступны в этот момент. При первом проходе формируются команда 0,
задающая сложение операндов m и n на вычислителе $$\nu _{0}$$, и команда 1, задающая сложение
операндов r и t на вычислителе $$\nu _{1}$$.
$$xab \ if \nu _{0}p > then \ d \ if \ mq < then \ \nu _{1} else \ r \downarrow else \ c \downarrow + :=$$.
При втором проходе не обнаруживается арифметических операций, готовых к
выполнению. Формируется пятиадресная команда 2. Она задает сравнение операндов m и q на вычислителе $$\nu _{2}$$. В
зависимости от результата сравнения итогом выполнения
данной команды (сформированной по ней инструкции) будет результат счета на
вычислителе $$\nu _{1}$$ или же r.
$$xab if \nu _{0}p > then \ d\ nu _{2} + else c \ \downarrow x + :=$$.
Последующие проходы сформируют команды 3 и 4 и
$$xab\ \nu _{4} x + :=$$.
В результате последующих проходов формируются команды 5 и 6.
Отметим, что команда 6 могла бы иметь вид $$+a\nu _{5}\nu _{6}$$, а
Вместе с тем, при необходимости использования имен вычислителей-исполнителей для именования операндов можно формировать имена в широком диапазоне выбора, имеющем два крайних случая.
Можно при каждом новом выборе значения математического адреса вычислителя использовать увеличенную (на единицу) величину ранее использованного значения. Именно так происходит в рассмотренном примере.
Другой крайний случай основан на принципе "экономии" адресов вычислителей. Он опирается на то, что результат операции используется единственный раз. Это означает, что и каждое объявленное имя вычислителя используется только один раз. Поэтому после использования это же имя может объявляться повторно, и благодаря механизму виртуализации ресурсов никакой коллизии не произойдет. Так, в команде 3 для обозначения вычислителя-исполнителя вместо $$\nu _{3}$$ можно использовать математический адрес $$\nu _{1}$$. Вместо $$\nu _{4}$$ в команде 4 повторно можно использовать адрес $$\nu _{2}$$ и т.д.
Наибольшая эффективность в работе ПВС может быть достигнута при значительном
опережении процессом коммутации процесса вычислений, благодаря чему динамически
обеспечивается достаточная загрузка вычислителей
Как показывает анализ прикладных программ, один оператор присваивания редко содержит более десяти переменных в правой части. С другой стороны, несколько подряд расположенных операторов присваивания, содержащих в общей сложности несколько десятков переменных, ситуация, которая встречается достаточно часто. Поэтому желательно иметь возможность именно такую последовательность операторов присваивания считать непрерываемым участком программы.
Рассмотрим фрагмент программы:
R := a x b + c x d; P := R + d x p; R := m x n.
При этом не обязательно соблюдается правило единственного присваивания.
Запишем соответствующие этим операторам бесскобочные записи в одну строку:
Rab x cd x + := PRdp x + := Rmn x :=. (11.5)
Пусть транслятор анализирует ее как единое целое. Тогда для сохранения информационной зависимости между операторами необходимо следовать следующим правилам:
NE — операнд, то анализируется, не совпадает ли он с какой-либо
ранее отмеченной переменной, которой производится присваивание, кроме отмеченной
последней. Если совпадает, то N := N+1. Производится дальнейший
анализ NE — переход к п. 2 изложенного выше алгоритма.NE — переменная, которой производится присваивание
(она находится правее знака ":="), то наряду с отметкой ее в списке
подобных переменных проверяется, не совпадает ли она с какой-либо ранее отмеченной
переменной, которой производится присваивание, или с любым операндом, входящим
в запись левее NE. Если совпадает, то N := N+1. Далее
по алгоритму трансляции, изложенному выше.Эти два правила, которым следует работа
В алгоритм трансляции необходимо внести еще одно изменение.
Если двуместная операция соответствует присваиванию, то после формирования
(рис 11.8) Удаление операции присваивания
После формирования команд $$0 \div 3$$
$$R\nu _{0}\nu _{1} + := PR\nu _{2} + := R\nu _{3} :=$$.
Первое вхождение в эту запись операнда R в качестве
переменной, которой присваивается значение, блокирует формирование последующих команд, использующих
этот же операнд. Поэтому при втором проходе формируется только команда 4, в
которой первоначально по третьему адресу указан адрес вычислителя-исполнителя $$\nu _{4}$$.
$$R\nu _{4} := PR\nu _{2} + := R\nu _{3} :=$$.
Во время третьего прохода уточняется команда 4 подстановкой по адресу
результата адреса переменной R. Первые три символа из записи исключаются.
Тогда открывается возможность сформировать команду 5, использующую новое значение R. При этом вместо комбинации символов $$R\nu _{2}+$$ формируется адрес
вычислителя $$\nu _{5}$$. Поскольку слева все вхождения R исключены, формируется команда 6
присваивания нового значения R.
При четвертом проходе формируется команда 7.
Задача параллельного выполнения операторов цикла может решаться посредством либо распараллеливания по итерациям, либо распараллеливания операторов внутри тела цикла. Распараллеливание по итерациям может быть применено для распределения групп повторений тела цикла по процессорам ПВС. Распараллеливание же внутри тела цикла может производиться так же, как и для последовательности операторов.
Определим оператор
<оператор
for <параметр цикла> := A1 step A2 until A3 do S
В этом определении A1, A2, A3 — арифметические выражения, а S — оператор (тело цикла).
В ПВС может быть использован подход, аналогичный "раскрутке" циклов.
Оператор цикла транслируется в программу коммутации, схема которой имеет вид, представленный на рис. 11.9.
(рис 11.9) Программа цикла
Команды $$1 \div k-1$$ соответствуют вычислению значений
арифметических выражений A1, A2 и A3, если они не являются константами или именами
переменных. Команда k — организация цикла (N — конец цикла (КЦ).
Между S. Эта часть программы коммутации образуется по правилам трансляции
соответствующей конструкции языка. В частности, если тело цикла — оператор присваивания
(последовательность операторов присваивания), то трансляция его происходит
по приведенному алгоритму.
a1, a2, a3 выражений A1, A2 и A3.
Далее осуществляется коммутация выполнения команд, составляющих тело цикла S. Если в теле цикла отсутствуют операторы перехода за границы цикла, то при
обработке процессором команды КЦ содержимое регистра СЦ уменьшается на единицу. В случае
неравенства его нулю коммутация продолжается с первой команды тела цикла.
В противном случае далее коммутируется выполнение команды N+1,
следующей за командой КЦ. Таким образом, осуществляется непрерывная коммутация всего цикла,
что обеспечивает возможность параллельного выполнения команд тела цикла.
Такому одновременному выполнению могут мешать конфликты между итерациями, связанные с использованием одной и той же переменной во всех итерациях. Например, в цикле
for i := 1 step 1 until 5 do
begin
x := a[i];
R[i] := x x b;
Q[i] := x / b;
end
все итерации фактически будут выполняться последовательно, поскольку
образуется x. В то же время очевидно, что информационно итерации друг с другом не связаны, поэтому
можно добиться их параллельного выполнения, применив переименование переменных.
Переменная х заменяется на x[i], компоненту массива x [1...5]. Цикл
принимает вид
for i := 1 step 1 until 5 do
begin
x[i] := a[i];
R[i] := x[i] x b;
Q[i] := x[i] / b;
end
Теперь все пять его итераций могут выполняться одновременно.
Очень важно, что при асинхронном выполнении итераций не возникает ошибок, которые связаны с нарушением порядка вычислений, предписываемого логическими связями между переменными. Рассмотрим следующий цикл
for i := 1 step 1 until 2 do
begin
x[i] := a[i];
R[i] := x[i] x b;
R[i + 1] := x[i] / b;
print (R[i], R[i + 1]);
end
Все вычисления в обеих итерациях могут выполняться независимо друг от друга
и одновременно. Правильная же работа операторов печати гарантирована тем,
что команды программы коммутации обрабатываются процессором последовательно и
заявки на запись и считывание к ячейке, в которой должно находиться значение R[2], выдаваемые при коммутации выполнения первой и второй итераций, будут упорядочены.
При трансляции операторов цикла итерационного типа,
<оператор цикла итерационного типа> ::= for <параметр цикла>
:= A1;A2 while B do S,
где A1, A2 — арифметические выражения, B —
логическое выражение, S —
оператор, образуется
Процесс коммутации, дойдя до команды условного перехода,
приостанавливается, ожидая прихода (после выполнения соответствующих
вычислений) информации о команде, начиная с которой его необходимо
продолжить. Таким образом, в точках условного перехода процесс вычислений
"догоняет" процесс коммутации. Подобные ситуации крайне
нежелательны, поскольку приостановление процесса коммутации прекращает загрузку
вычислителей
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.