Come attraversare la "lista collegata" come struttura con nodi paralleli

0

Sto lavorando a un progetto di elaborazione dei segnali che consente l'elaborazione parallela su flussi di dati nonché input e output da e verso più endpoint.

La catena del segnale è suddivisa in "endpoint" e "nodi".

Gli endpoint possono essere dichiarati input o output e i nodi sono qualsiasi cosa in mezzo.

È possibile dichiarare che i due tipi di oggetti dipendono l'uno dall'altro, tutti i tipi possono contenere dipendenze eccetto per gli endpoint dichiarati come input.

Un esempio di catena del segnale potrebbe essere:

input1 --  + --  node1 --  + -- node3 --output1
input2 -- /    \ node2 -- /          \--output2

Una versione testuale:

  • output1 dipende dal nodo 3
  • output2 dipende dal nodo 3
  • node3 dipende dai nodi 1 e amp; 2 (riassunto)
  • I nodi
  • 1 e 2 dipendono dagli ingressi 1 e amp; 2 (riassunto)

I nodi / endpoint attualmente contengono un puntatore agli oggetti da cui dipendono.

Sto cercando di sviluppare un algoritmo in grado di tracciare il grafico partendo dagli output e determinare l'ordine in cui i dati devono essere elaborati tenendo conto dei dati che possono essere elaborati in parallelo.

Risultato di esempio:

  1. leggi input1 & input2 (parallelo)
  2. somma input
  3. esegue processi sui nodi 1 & 2 (parallelo)
  4. sommano i risultati dei nodi 1 e amp; 2
  5. esegue i processi sul nodo 3
  6. scrivi uscite 1 & 2 (parallelo)

Non sono sicuro da dove iniziare quando si sviluppa un algoritmo per analizzarlo, o se il maniero che ho collegato i nodi è sufficiente per farlo. Attualmente è impostato come un elenco collegato singolarmente in cui ogni oggetto conosce gli oggetti precedenti

Sto lavorando in C ++.

    
posta Alex Zywicki 21.05.2016 - 08:42
fonte

1 risposta

2

Questo è un semplice grafico aciclico diretto , il che significa che la valutazione dei nodi non dovrebbe essere terribilmente complicata. Gli algoritmi citati nella sezione "Ordinamento e riconoscimento topologico" dell'articolo di Wikipedia consentono di suddividere la valutazione del grafico in una sequenza lineare di passaggi. Vedi anche questa risposta .

    
risposta data 21.05.2016 - 09:02
fonte

Leggi altre domande sui tag