Архитектура графа узлов

Узлы шейдеров в Blender

Архитектура графа узлов — это конструкция программного обеспечения , построенная на основе понятия графа узлов . И исходный код , и пользовательский интерфейс разработаны с учетом редактирования и композиции (или связывания) атомарных функциональных блоков. Графы узлов — это тип визуального языка программирования .

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

программного Пользовательский интерфейс приложения часто визуально отображает пользователю граф узлов. Это часто достигается за счет использования графического процессора для выполнения рендеринга, который впоследствии отображается пользователю на рабочем столе. Распространенными API для графического процессора являются OpenGL и DirectX . Узлы часто изображаются в виде прямоугольников, а соединения между узлами изображаются линиями или сплайнами.

Использование архитектуры графа узлов началось в 1960-х годах. Сегодня использование графов узлов резко возросло. Области графики, игр и машинного обучения являются основными потребителями этого дизайна программного обеспечения, при этом большинство инструментов используют архитектуру графа узлов.

По сей день ведутся споры о преимуществах визуального программирования и архитектуры графа узлов. Сторонники подчеркивают, как абстракция, обеспечиваемая графами узлов, упрощает использование инструмента. Критики подчеркивают, что визуальное программирование является слишком ограничительным и что им приходится прибегать к модификации исходного кода или сценариев для выполнения своих задач.

История

постоянно работает Эрик Хосик над X по сбору снимков всех пользовательских интерфейсов графов узлов в большинстве программных приложений . Целью проекта является попытка задокументировать эволюцию и взрывной рост пользовательских интерфейсов графов узлов, начиная с их первоначальных корней. Эта визуальная история размещена на странице блога под названием Visual Programming Languages ​​— Snapshots . Работы, ведущие к архитектуре графов узлов и визуальному программированию, похоже, начались в 1960-х годах в области, известной как «человеко-машинная связь».

В диссертации Уильяма Роберта Сазерленда в Массачусетском технологическом институте (1966) «Онлайн-графическая спецификация процедур» он описывает и анализирует темы, связанные с языком двумерных изображений. Это одно из первых исследований основанных на потоках данных рабочих процессов или программ, . С тех пор его диссертация использовалась как «предшествующий уровень техники», чтобы отменить сегодняшние судебные иски по поводу идей потоков данных. Многие считают, что его работа проложила путь к тому, что сегодня известно как автоматизированное проектирование (САПР) .

1. Графическая программа — естественный способ изображения параллельных процессов. Двумерная природа языка помогает визуализировать множество вещей, происходящих одновременно.
2. Легкость отладки программ, особенно параллельных, будет повышена за счет графической формы языка. Возможность подключать датчики данных и видеть работу программы дает возможность понять детали, которые трудно получить каким-либо другим способом.
3. Выполнение программы не обязательно должно контролироваться обычными явными соглашениями о последовательном потоке. Перемещение данных через программу может определять ее работу. Соглашение об управлении данными близко соответствует нашим интуитивным представлениям о том, как должна работать графическая программа, а также допускает параллельное программирование без явного обозначения потока.

В 1969 году Т. О. Эллис, Дж. Ф. Хифнер и У. Л. Сибли опубликовали статью о языке графического ввода (GRAIL) . Их работа была связана с RAND Tablet , которая началась с исследования Sketchpad , системы, где пользователи могли писать компьютерные команды прямо на планшете, проведенного Иваном Сазерлендом . Система GRAIL использовала язык графического программирования на основе блок-схем и могла распознавать рукописные буквы и жесты. Алан Кей предоставил ряд демонстраций системы GRAIL , однако он не участвовал в создании системы.

1. Важными организационными концепциями в системе GRAIL являются последовательный поток управления, иерархия подпрограмм и язык (блок-схемы) для графического связывания организации в рамках концепций первых двух.
2. Последовательный характер контроля позволяет человеку представить себе изолированные процессы, адаптированные к конкретным функциям, что, в свою очередь, позволяет организатору думать об общей программе в терминах управляемых частей.
3. Иерархия подпрограмм еще сильнее подчеркивает идею изолированных процессов.
4. Блок-схемы помогают человеку представить варианты управления и взаимосвязь между процессами, выражая эти взаимосвязи в двух измерениях.

Граф узлов Blender, 2006 г.

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

• Катана, Литейный цех
• Гудини, SideFX
• Ядерное оружие, литейное производство
• Мари, Литейный цех
• Майя, Аутодеск
• Blender (программное обеспечение) § Узлы геометрии — Официальная документация
• Кузнечик, МакНил и партнеры
• Динамо, Аутодеск

Абстракция и сложность

В статье «Иерархические маленькие миры в архитектуре программного обеспечения». автор Сержи Вальверде утверждает, что большинство крупных программных систем построены по модульному и иерархическому принципу и что графы узлов можно использовать для анализа больших программных систем. Многие другие статьи по анализу программного обеспечения часто используют графы узлов для анализа больших программных систем, предполагая, что графы узлов являются хорошими моделями внутренней структуры и работы программного обеспечения.

Дебаты по визуальному программированию

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

• Сторонники визуального программирования обычно подчеркивают, насколько оно упрощает программирование, поскольку абстрагирует многие детали и предоставляет только те элементы управления, которые необходимы для их предметной области. Эти элементы управления представляют собой параметры узлов, которые управляют их поведением и связями между узлами.
• Критики визуального программирования обычно подчеркивают, что оно не обеспечивает достаточного контроля и что для более сложных задач возникает необходимость создания исходного кода . Однако эти более сложные задачи часто выходят за рамки предполагаемого использования или области графа узлов.

Это остается активной областью дискуссий, и по сей день на открытых форумах происходят новые дискуссии. Ниже приведены некоторые из крупнейших дискуссий на сегодняшний день.

• Обсуждение на Hacker News, 2014 г.
• Обсуждение на Hacker News, 2019
• Обсуждение на Reddit, 2019 г.

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

Граф узлов

Пример графа узлов

Граф узлов в контексте архитектуры программного обеспечения относится к организации функциональности программного обеспечения в виде атомарных единиц, известных как узлы, и где узлы могут быть связаны друг с другом посредством ссылок. Манипулирование узлами и ссылками в графе узлов часто можно осуществлять с помощью программируемого API или посредством визуального интерфейса с помощью мыши . На диаграмме выше граф узлов отображается справа.

В современном использовании термин «граф узлов» представляет собой открытое сложное слово. Однако в более старых версиях программного обеспечения его называли «узлом», закрытым составным словом.

• Nodegraph, Программное обеспечение Valve
• Нодеграф, Нотч

Узел

Узлы выполняют тот или иной тип вычислений. Они инкапсулируют эту исполняемую функциональность и часто принимают входные данные и производят выходные данные как побочный продукт выполнения . Простой пример — узел, который складывает два числа. Входные данные — это два числа, которые нужно сложить, а выходные данные — сумма этих двух чисел.

Узлы аналогичны математическим функциям следующего вида.

${outputs}_{nodeA}=f_{nodeA}({inputs}_{nodeA})$,

где $f_{nodeA}$ это вычисление узла, $inputs_{nodeA}$ - вектор входных значений узла и ${outputs}_{nodeA}$ — вектор выходных значений узла.

Визуально узлы часто представляются прямоугольниками. Однако это не соглашение, которому следуют все приложения. На диаграмме выше есть три узла с надписью «Видео», «Добавить звезду» и «Добавить круг».

Параметры узла

Узлы часто имеют дополнительные параметры, определяющие их выполнение . Эти параметры поддерживаются типами данных узла в исходном коде .

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

Визуально параметры узла часто отображаются после того, как пользователь щелкает узел. Это помогает визуально уменьшить загромождение графа узлов. На диаграмме выше мы видим окно параметров, открывающееся рядом с узлом «Добавить звезду».

Входы и выходы узла

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

Математически входы и выходы узла аналогичны входным и выходным значениям функций.

${outputs}_{nodeA}=f_{nodeA}({inputs}_{nodeA})$,

где $f_{nodeA}$ это вычисление узла, $inputs_{nodeA}$ - вектор входных значений узла и ${outputs}_{nodeA}$ — вектор выходных значений узла.

Визуально входы и выходы узлов часто изображаются кружками.

Ссылки на узлы

Ссылки передают значения, хранящиеся в типах данных, между разными узлами. Они аналогичны математической композиции. Например, если узел A передает свои выходные данные узлу B, математически это можно представить следующим образом.

${outputs}_{nodeB}=f_{nodeB}(f_{nodeA}({inputs}_{nodeA}))$,

где $f_{nodeB}$ и $f_{nodeA}$ — операции, выполняемые узлом B и узлом A, $inputs_{nodeA}$ - вектор входных значений узла A и $outputs_{nodeB}$ — вектор выходных значений узла B.

Типы узлов

Тип узла указывает, какую вычислительную операцию он будет выполнять при выполнении . В графе узлов часто участвует множество различных типов узлов. Ниже приведены некоторые примеры:

• Nuke , популярная программа для создания визуальных эффектов , включает в себя сотни узлов. каждый выполняет определенные задачи, связанные с композитингом.
• Katana, популярное программное обеспечение для создания внешнего вида и освещения, включает в себя сотни узлов. каждый выполняет определенные задачи, связанные с освещением сцен компьютерной графики.
• Mari, популярное программное обеспечение для 3D-рисования, включает в себя сотни узлов. каждый выполняет определенные задачи, связанные с 3D-рисованием.

Наиболее важным типом узла для управления сложностью является узел группы. Этот тип узла не выполняет программный код так же, как другие узлы. Этот узел просто группирует подмножество связанных узлов и управляет входами и выходами в группу или из нее. Это скрывает сложность внутри узлов группы и ограничивает их связь с другими узлами вне группы. Это приводит к иерархии, в которой графы меньшего размера встроены в узлы группы. Ниже приведены примеры групповых узлов, которые используются для группировки подмножества связанных узлов и упрощения графа.

• Групповые узлы в Nuke.
• Групповые узлы в Katana.

Пользовательский интерфейс

Программные приложения, использующие архитектуру графа узлов, обычно предоставляют пользователю граф узлов визуально или графически, позволяя пользователю вносить изменения в граф узлов. С помощью мыши пользователи обычно могут:

• создавать новые узлы
• редактировать параметры на узлах
• соединить узлы вместе
• оценить граф до определенного узла
• просмотреть текущие выходные значения на узлах

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

• Графики узлов на Dribbble
• Узлы на Dribbble

Направленные ациклические графы

Пример направленного ациклического графа

Многие теоретические результаты теории графов применимы к графам узлов, особенно в отношении топологии . Эта предметная область, в которой узлы соединяются вместе для формирования графов , хорошо изучена.

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

Использование в компьютерной графике

Пример пользовательского интерфейса на основе графа узлов

Использование архитектуры графа узлов при разработке программного обеспечения особенно популярно в киноиндустрии и видеоиграх . На диаграмме выше показан упрощенный пользовательский интерфейс художественного инструмента для редактирования и создания видео. Узлы представлены в виде прямоугольников и соединены друг с другом изогнутыми линиями ( кривыми Безье ). В операционной модели этого программного обеспечения видеопоследовательность передается по линиям на следующий узел, и каждый узел выполняет некоторые дополнительные модификации видеопоследовательности. В этом примере одно видео переводится в 2D, другое пикселизируется и, наконец, оба потока объединяются.

Ниже приведены некоторые примеры программного обеспечения, использующего архитектуру графа узлов в киноиндустрии и видеоиграх .

• Катана, Литейный цех
• Гудини, SideFX
• Ядерное оружие, литейное производство
• Мари, Литейный цех
• Майя, Аутодеск
• Блендер

Использование в машинном обучении

Простые слои нейронной сети

Использование архитектуры графа узлов при разработке программного обеспечения в последнее время стало очень популярным в приложениях машинного обучения . На диаграмме выше показана простая нейронная сеть, состоящая из трех слоев. Три слоя — это входной слой, скрытый слой и выходной слой. Элементы в каждом слое являются весами и связаны с весами в других слоях. Во время вывода алгоритм машинного обучения оценивает веса в выходном слое посредством последовательности функциональных оценок весов из предыдущих слоев. Во время обучения алгоритм машинного обучения использует оптимизацию для минимизации функции потерь, где функция потерь зависит от разницы между весами в выходном слое и ожидаемыми значениями. Графы узлов используются для визуализации, настройки и отладки этих слоев нейронной сети.

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

• PyTorch, GitHub, Facebook
• TensorFlow, GitHub, Google

Ниже приведены некоторые примеры программного обеспечения для машинного обучения , использующего архитектуру графа узлов .

• Графбук, Цербрек
• ПерцептиЛабс, KDnuggets
• Глубокое познание, Deep Congition Inc.
• Разработчик моделей нейронных сетей, IBM
• Консоль нейронной сети, Sony
• Цифры, nVIDIA

См. также

• Adobe Substance Designer

Ссылки

• Метрики изменений архитектуры программного обеспечения на основе структурного расстояния
• Представление и анализ программного обеспечения
• «Грамматики графов и решение ограничений для стилей архитектуры программного обеспечения». 1998: 69–72. CiteSeerX   10.1.1.108.9362 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
• Палсингх, Риши; Вандана, Вандана (2014). «Применение теории графов в информатике и технике». Международный журнал компьютерных приложений . 104 (1): 1–4. Бибкод : 2014IJCA..104a..10P . CiteSeerX   10.1.1.800.2735 . дои : 10.5120/18165-9025 .
• Торат, Сушрут; Чоудхари, Варад (2016). «Реализация обратного словаря на основе определений слов с использованием архитектуры узлового графа» (PDF) . arXiv : 1606.00025 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
• «Представление и анализ программного обеспечения». CiteSeerX   10.1.1.394.4865 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
• История визуального программирования: от базового до пузыря
• Скретч-программное обеспечение
• Блочное программное обеспечение
• Что такое визуальное программирование