Введение

В моем предыдущем блоге я рассказывал о простой реализации модуля символьной дифференциации (SD), однако эта реализация была неоптимальной по своей природе, поскольку основная цель статьи заключалась в том, чтобы объяснить SD и прояснить несколько различий и нюансов. между SD и алгоритмической дифференцировкой (AD). Поэтому в этом коротком блоге я хотел бы обсудить метод улучшения вычислительной производительности SD-модуля.

В запрограммированной среде, в основном, если нужно вычислить производную математического выражения, тогда нужно будет вычислить SD выражения, используя метод «differ» с относительно переменной оптимизации и для оценки полученного выражения необходимо было вызвать метод «eval». Несмотря на то, что реализация работает хорошо и вывод правильный, было ясно видно, что есть несколько повторений подвыражений, и при вычислении нескольких вложенных производных можно было столкнуться с набуханием выражения. Разветвление в этом случае заключается в том, что функция «eval» должна пробираться через каждый повторяющийся узел подвыражения, тем самым сжигая гораздо больше компьютерных циклов для оценки производных. Для простого выражения эффект может быть не очень заметен, однако для более крупного выражения задержка вычислений весьма заметна и может даже остановить выполнение программы. Поэтому необходимо соблюдать особую осторожность, чтобы избежать этой ситуации.

II. Концепция

Чтобы уменьшить вычислительную сложность по отношению к оценке выражения, как упоминалось в моем предыдущем блоге, повышение производительности заключается в преобразовании дерева выражений (ET) в направленный ациклический граф (DAG). Наряду с преобразованием из ET в DAG, я также модифицировал вычисление хеш-функции для механизма кэширования, что позволило бы разумно избежать повторного создания новых узлов подвыражений (по крайней мере, в меру своих возможностей). Во-первых, давайте начнем с части преобразования с примером, показанным на рис.1.

ET для приведенного выше выражения показан ниже на рис. 2. Совершенно очевидно, что произведение двух членов sin имеет один и тот же аргумент, то есть x1+x2+x3, за исключением того факта, что порядок суммирования разный. При реализации ET может случиться так, что каждый узел подвыражения будет иметь отдельный адрес из-за плохого механизма кэширования, и это может привести к нескольким различным узлам подвыражения, однако на практике это может быть необязательно, поскольку можно использовать предварительно вычисленная версия того же подвыражения. Таким образом, если не принять надлежащих мер, то ET может иметь несколько повторений подвыражений, и это будет дополнительно просачиваться в производные SD, что приведет к появлению нескольких отдельных узлов подвыражения, что может быть неоптимальным решением.

С помощью интеллектуального механизма кэширования, использующего обновленную функцию хеширования, ET выражения, показанного на рис. 2, можно преобразовать в DAG, и в этом случае значения адресов повторяющихся узлов подвыражения кэшируются должным образом, и это можно использовать соответствующим образом. DAG показан на рис.3.

После внедрения метода интеллектуального кэширования единственным изменением является режим обхода, то есть обход в предварительном порядке с отмеченными состояниями. Логическая переменная поддерживается для каждого узла подвыражения, чтобы отметить, был ли он посещен или нет. Если узел не был посещен, оцените выражение и сохраните оцененный результат, а если узел посещен, пропустите оценку и верните сохраненный результат.

III. Выполнение

В следующем видео обсуждается реализация описанной выше концепции на C++ и в основном модификации, примененные к предыдущему неоптимальному подходу.

IV. Заключение

В этой статье я объяснил шаг оптимизации, который можно использовать для повышения вычислительной производительности символьного дифференцирования. Однако построение большой структуры выражения с использованием вызова differ может увеличить время компиляции для этого подхода и даже привести к полной остановке выполнения. В AD этого избегают, и я расскажу об AD в следующей статье.