Quando usar o DAG (Directed Acyclic Graph) na programação?

36

Recentemente, encontrei um framework chamado ecto .

Neste framework, um componente básico chamado "plasma" , que é o ecto Directed Acyclic Graph.In ecto, o plasmídeo pode ser operado pelo ecto scheduler.

Eu estou querendo saber qual é a vantagem desse mecanismo e em quais outras situações podemos explorar o conceito de DAG?

    
por Po-Jen Lai 28.10.2012 / 17:39
fonte

8 respostas

28

Boa pergunta.

  • O código pode ser representado por um DAG descrevendo o entradas e saídas de cada uma das operações aritméticas realizadas dentro do código; esta representação permite que o compilador execute eliminação de subexpressão comum de forma eficiente.
  • A maioria dos sistemas de gerenciamento de controle de origem implementam as revisões como DAG.
  • Várias linguagens de programação descrevem sistemas de valores que são relacionados uns aos outros por um gráfico acíclico dirigido. Quando um valor mudanças, seus sucessores são recalculados; cada valor é avaliado como uma função de seus predecessores no DAG.
  • Os DAG são úteis na detecção de impasses, pois ilustram a dependências entre um conjunto de processos e recursos.
  • Em muitos algoritmos aleatórios em geometria computacional, o algoritmo mantém uma história DAG representando características de alguns construção geométrica que foram substituídos por uma escala mais fina características; consultas de localização de ponto podem ser respondidas, como para o acima duas estruturas de dados, seguindo caminhos neste DAG.
  • Quando tivermos o DAG na memória, podemos escrever algoritmos para calcular o tempo máximo de execução de todo o conjunto.
  • Ao programar sistemas de planilha, o gráfico de dependência que conecta uma célula a outra se a primeira célula armazena uma fórmula que usa o valor na segunda célula deve ser um gráfico acíclico direcionado. Ciclos de dependências não são permitidos porque causam as células envolvidos no ciclo para não ter um valor bem definido. Além disso, exigir que as dependências sejam acíclicas permite uma ordem topológica para ser usado para agendar os recálculos de valores de células quando o a planilha é alterada.
  • Usando o DAG, podemos escrever algoritmos para avaliar os cálculos em a ordem correta.

EDITAR:

  • Ordenação da avaliação da célula de fórmula ao recomputar valores de fórmulas em planilhas podem ser feitas usando DAGs
  • O Git usa DAGs para armazenamento de conteúdo, ponteiros de referência para cabeçalhos, representação de modelo de objeto e protocolo remoto.
  • Os DAGs são usados no Agendamento de traços: a primeira abordagem prática para programação global, o agendamento de rastreio tenta otimizar o controle caminho de fluxo que é executado com mais frequência.
  • Ecto é uma estrutura de processamento e usa o DAG para modelar o processamento gráficos para que os gráficos ordenem a execução síncrona. Plasm in O Ecto é o DAG e o Scheduler que opera nele.
  • Os DAGs são usados no pipelining de software, que é uma técnica usada para otimizar loops, de uma maneira paralela ao pipelining de hardware.

Bons recursos:

por 28.10.2012 / 18:25
fonte
12

A resposta é que não tem muito a ver com programação. Tem a ver com a resolução de problemas.

Assim como as listas vinculadas são estruturas de dados usadas para certas classes de problemas, os gráficos são úteis para representar certos relacionamentos. Listas vinculadas, árvores, gráficos e outras estruturas abstratas só têm uma conexão com a programação em que você pode implementá-las no código. Eles existem em um nível mais alto de abstração. Não se trata de programação, trata-se de aplicar estruturas de dados na solução de problemas.

Se você ainda quiser alguma relação com a programação, considere os seguintes pontos:

por 28.10.2012 / 18:03
fonte
6

Outras pessoas aplicaram o DAG a dados, mas acho que é no mínimo aplicável (se não mais) ao código. Mahbubur R Aaman menciona isso, então isso é mais um adendo à sua resposta do que uma resposta completa por si só.

Ocorre-me que qualquer programa de computador imperativo livre de loops infinitos (obrigado @AndresF.) é um Directed Acyclic Graph (DAG). Isso significa que os possíveis caminhos de execução do código são direcionados (primeiro isto, depois aquilo) e acíclico (não formando loops infinitos). Eles são um gráfico porque o caminho através de qualquer código significativo raramente é tão simples quanto uma lista ou uma árvore.

Eu trabalhei em XSLT por talvez 4 anos. Tive um tempo terrível tentando explicar por que não era uma boa linguagem de programação de uso geral, mas o DAG é o motivo. Especificamente, o XSLT é uma linguagem orientada por dados. Você define funções (sim, no sentido de programação funcional), mas não necessariamente chama essas funções de seu código. Em vez disso, o XSLT configura uma combinação de seleção e iteração pelos nós de um documento XML de entrada. Isso permite que a estrutura dos dados de entrada determine quais funções são chamadas e em qual ordem.

Isso foi muito interessante e muito legal até que seu programa encontrou uma condição de dados que você não testou às 2h30 da manhã e teve que acordar e consertá-lo. Quando você permite que os dados definam o DAG, a definição do DAG se torna todas as possíveis condições de entrada - que, para qualquer aplicativo de negócios não trivial, são além de incalculáveis; eles são inimagináveis.

A princípio, eu pensei que a programação funcional pode não ser um DAG, porque a ordem de execução, às vezes, não é clara ou até pensada pelo programador. Mas um programa funcional define dependências. De fato, a natureza declarativa da programação funcional poderia ser pensada como definindo apenas dependências (a ^ 2 = b ^ 2 + c ^ 2) sem especificar a ordem de execução (não importa se 'b' ou 'c' é quadrado primeiro , desde que sejam ambos ao quadrado antes de serem adicionados juntos).

Mas enquanto a programação funcional pode ser deliberadamente vaga sobre a ordem das operações em um nível detalhado, é perfeitamente claro sobre as dependências. Estas são as mesmas características que o tornam tão receptivo à concorrência. Em qualquer caso, ainda há um gráfico de caminhos através do código, e esse gráfico ainda é direcionado (as dependências devem ser avaliadas antes de tarefas dependentes), então acho que o DAG também se aplica lá.

Boa pergunta - obrigado por postar!

    
por 29.10.2012 / 02:56
fonte
5

Atualmente, o DAG é subestimado na programação. Historicamente, muitas coisas relacionadas ao desenvolvimento foram feitas com árvores e hierarquias, porque mover algo em uma caixa é conveniente para o nosso cérebro para tornar as coisas complexas mais fáceis de gerenciar. Mas se você olhar para eventos e como eles dependem de outros eventos e estados, então você receberá DAG porque qualquer coisa em nossa vida e no programa pode depender de qualquer coisa no passado, mas não no futuro, então você obteria perfeitamente "acíclico" relações sejam aplicáveis ao conceito DAG. Embora isso raramente seja usado explicitamente no desenvolvimento, ter isso em mente ajudaria a entender melhor as coisas

    
por 28.10.2012 / 20:38
fonte
2

I am wondering what's the advantage of Plasm in Ecto...

O DAG pode ser usado para modelar uma coleção de tarefas em uma sequência com a restrição de que certas tarefas devem ser executadas antes das outras. Ecto é uma estrutura de processamento e usa o DAG para modelar gráficos de processamento para que os gráficos façam a execução síncrona ordenada. Plasm em Ecto é o DAG e o Scheduler opera nele.

in what other situations can we exploit the concept of DAG?

  • DAWG é uma estrutura de dados que representa um conjunto de strings e permite uma operação de consulta que testa se uma dada string pertence ao conjunto no tempo proporcional ao seu comprimento.
  • Git usa DAGs para armazenamento de conteúdo, ponteiros de referência para cabeçalhos, representação de modelo de objeto e protocolo remoto.
por 29.10.2012 / 03:08
fonte
0

Como um exemplo do mundo real, nosso software é semelhante a um IDE, no qual o usuário final pode definir uma série de operações a serem executadas em uma imagem (inspeção de visão de máquina). Essas inspeções podem ter dependências de outras inspeções ou podem ter inspeções dependentes delas. Como tudo isso é configurável pelo usuário final, não podemos fazer otimizações para o processamento paralelo no tempo de design. Ao representar essas inspeções e dependências como um DAG, podemos otimizar o paralelismo da inspeção geral para obter o máximo desempenho em tempo de execução.

    
por 29.10.2012 / 03:09
fonte
-1

Apenas por outro exemplo, as regras de gerenciamento de memória nos aplicativos Cocoa são feitas para que todas as referências strongs formem um gráfico acíclico direcionado, o que é feito para garantir a ausência de vazamentos.

    
por 29.10.2012 / 07:07
fonte
-2

Adicionando outra resposta, pois não vimos uma referência para criar sistemas como make , que usa o DAG para descobrir dependências para a criação.

Mais detalhes aqui

    
por 31.01.2016 / 19:03
fonte