Se ognuno degli N Thread piglia un nodo e sputa i figli (che terminologia tecnica, eh!?
) e parti dalla radice di un albero direi che la condizione che termina il computo è "ognuno degli N thread ha di fronte una coda vuota".
Hai ragione da vendere quando dici che non basta che la coda dei nodi da esaminare sia vuota perchè potrebbe esserlo nel momento in cui un Thread abbia prelevato un nodo ma non abbia ancora inserito i figli.
Quando alla struttura di controllo direi che siamo di fronte ad una via di mezzo tra una barriera ed un countdown.
Tieni conto anche della soluzione di gugo perchè se l'operazione compiuta dal singolo Thread è sufficientemente rapida l'incidenza sui tempi di esecuzione della sincronizzazione richiesta per l'accesso alla coda e alla struttura di controllo potrebbe essere sensibile.
Considera inoltre che collegare il numero di Thread al numero di CPU potrebbe non sfruttare pienamente la capacità della piattaforma perchè anche una singola CPU può eseguire istruzioni in parallelo - o almeno questo è quanto mi pare di ricordare dal buon vecchio Patterson-Hennessy.