8.3. Граф вычислений

Для общего представления автоматического дифференцирования нам понадобится граф вычислений. Это ориентированный граф для представления последовательности вычислений, скажем, функции \(f\).

Обычно вершинами графа являются операции или их аргументы, а рёбра связывают операции с аргументами. Мы же воспользуемся упрощённым описанием, которого хватит для наших целей. Так, в вершины графа мы будем помещать значения, возникающие в ходе вычислений (включая аргументы \(f\) и итоговое значение), а рёбра (дуги) графа будут соединять аргументы операции с её результатом.

Рассмотрим несколько примеров.

Рис. 8.2 Граф вычислений \(f(x) = \sin x\).

На Рисунке 8.2 показан граф вычисления унарной функции (функции одного аргумента). В этом случае \(x_1 \equiv x\), а \(x_2 \equiv f(x)\).

Рис. 8.3 Граф вычислений для операции суммы.

На Рисунке 8.3 показан граф вычисления суммы \(x_1 + x_2\) с хранением результата в \(x_3\). С формальной точки зрения, операцию сложения можно представить в виде функции двух аргументов (бинарной функции). В таком случае стоки вершины \(x_3\) соединяют её с аргументами операции, а саму операцию мы будем подписывать рядом с вершиной-результатом.

Рис. 8.4 Граф вычислений функции \(f(x_1, x_2, x_3) = (x_1 x_2 + \sin{x_3})/x_3\).

На Рисунке 8.4 показан граф вычисления функции трёх переменных

\[f(x_1, x_2, x_3) = \frac{x_1 x_2 + \sin{x_3}}{x_3},\]

которую мы будем в качестве примера в последующих разделах. Значения \(x_1\), \(x_2\) и \(x_3\) являются аргументами функции, а \(x_7\) — значением функции в точке \([x_1, x_2, x_3]^\top\). Промежуточные значения функции приведены ниже.

function f(x₁, x₂, x₃)
    @show x₁
    @show x₂
    @show x₃
    @show x₄ = x₁ * x₂
    @show x₅ = sin(x₃)
    @show x₆ = x₄ + x₅
    @show x₇ = x₆ / x₃
    return x₇
end

f(1, 2, 3)

x₁ = 1
x₂ = 2
x₃ = 3
x₄ = x₁ * x₂ = 2
x₅ = sin(x₃) = 0.1411200080598672
x₆ = x₄ + x₅ = 2.1411200080598674
x₇ = x₆ / x₃ = 0.7137066693532891

0.7137066693532891

Те же промежуточные значения \(x_4\), \(x_5\), \(x_6\), \(x_7\) создаёт компилятор языка. Они обозначаются как %номер в Julia.

f2(x₁, x₂, x₃) = (x₁ * x₂ + sin(x₃)) / x₃
@code_lowered f2(1, 2, 3)

CodeInfo(
1 ─ %1 = x₁ * x₂
│   %2 = Main.sin(x₃)
│   %3 = %1 + %2
│   %4 = %3 / x₃
└──      return %4
)

В нашем случае x₄ = %1, x₅ = %2, x₆ = %3 и x₇ = %4.

Для создания машинного (или промежуточного представления) кода из исходного компилятор строит синтаксическое дерево. Если не вдаваться в технические детали, синтаксическое дерево напоминает граф вычислений, который мы описывали выше. Однако, в синтаксическом дереве содержатся не только «привычные» математические операции, но и операторы языка, например, операторы ветвления, циклов или вызова функций. Кроме того, на разных платформах (железе или операционной системе) машинный код может быть разным, но синтаксические деревья (и исходный код) могут совпадать ввиду более высокого уровня абстракции вычисления.

В следующих разделах мы воспользуемся графом вычисления, показанном на Рисунке 8.4, для классификации методов автоматического дифференцирования.