Проблема : Я разбираюсь в сетке данных вокруг заданной области. Страницы будут поступать из нескольких источников и заполняться несколькими шагами. Эти шаги могут включать диск, сеть, графический процессор, рабочие потоки, фактически любую форму асинхронной обработки. Что наиболее важно, страница может потребовать, чтобы другие страницы были на определенном этапе, прежде чем она сможет обработаться. Например, для страницы на go через этап обработки графическим процессором может потребоваться, чтобы несколько соседних страниц (и она сама) уже были загружены с диска или сети.
Решение : I решил, что DAG решает мою проблему. На каждой странице будет несколько узлов DAG, по одному для каждого возможного шага. Когда я запрашиваю страницу на определенном этапе, я действительно найду узел DAG, связанный с этим шагом, тогда этот узел DAG найдет соседние узлы DAG, на которые он опирается (которые будут соседними страницами, но с DAG узел для необходимого шага). Генерируемые им ребра изначально были бы «ожидающими», и когда ссылка на страницу завершает этот этап обработки, она будет каскадно обновляться в этой точке в группе обеспечения доступности баз данных. Затем на всех ссылочных страницах будет замечено, что все ребра группы обеспечения доступности баз данных находятся на стадии «завершения», и сможет обработать свой собственный узел группы обеспечения доступности баз данных, что приведет к успешному завершению работы группы обеспечения доступности базы данных.
Итак, пример: клиент создает ребро для узла обработки GPU страницы в 0,0. Этот узел создает ребра для шага ЗАГРУЗКИ (с диска / сети) страниц на 0,1, 1,0, -1,0, 0, -1. Все эти шаги начинают обработку, поэтому края находятся в состоянии ожидания. Когда каждый из них завершается, узел 0,0 проверяет, все ли ожидаемые ребра являются «завершенными». В конце концов, все они завершены, так что этот узел начинает свой шаг графического процессора и устанавливает начальный фронт в «ожидание». Когда этот шаг завершен, начальное ребро от клиента становится «завершенным», и группа обеспечения доступности баз данных разрешается.
Помимо этого, ребра имеют 3 состояния: «начальный», «ожидающий» и «завершенный» и рабочие потоки разрешат группу обеспечения доступности баз данных, найдя конечные узлы в «начальном» состоянии, установив для него значение «в ожидании», выполнив работу, а затем установив для нее «выполнено», когда работа будет завершена. Кроме того, в дополнение к этому, любое обновление любого узла с «завершенного» до «ожидающего» могло бы каскадно перемещаться по дереву, вызывая потенциальную повторную обработку всех родительских узлов, поскольку в их зависимостях есть изменения. Наконец, может быть несколько узлов root, указывающих на разные области группы обеспечения доступности баз данных.
Вопрос : Существует ли имя или какая-либо существующая работа над такого рода структурой данных? Это кажется знакомым, почти как DAG "цепочки поставок", за исключением того, что часть работы может быть переработана и каскадно перемещаться вверх по дереву. Однако наличие нескольких узлов на странице, где узел может даже создать ребро для другого узла на одной странице, кажется немного новым.