Il mergesort parallelo viene eseguito in modo diverso su mesh vs array lineare di processori?

Definisci i termini mesh e linear array of processors e / o fornisci riferimenti online a tali definizioni.

Esistono diversi tipi di algoritmi di fusione. Una notevole differenza è:

• Per unire due metà ordinate di maglie N/2 in un array N completamente ordinato, richiede esattamente un passaggio (eseguendo esattamente N o O(N) confronti), oppure richiede più fasi, la maggior parte comunemente O(log(N)) come molti stadi (per un numero totale di confronti O(N*log(N)) )?

• Il mergesort a thread singolo, quello in genere insegnato nell'introduzione alle classi di programmazione, si basa su scanning le due metà, "dequeuing" il valore più piccolo dei due valori frontali delle due metà . Questo richiede esattamente% confrontoN-1. Poiché è sequenziale, richiede O(N) di passaggi temporali.

• Il mergesort parallelo, che è molto probabilmente un mergesort bitonico parallelo, come
  • link
  • link
  • Richiede log(N) stages;
  • All'interno di ogni fase, vengono effettuati confronti O(N) - un confronto per elemento di elaborazione - e tutti gli elementi di elaborazione lo fanno simultaneamente.
  • Pertanto, richiede O(log(N)) di tempo, nonostante abbia eseguito molti più numeri totali di confronti di N*log(N)

Esistono altri tipi di ordinamento di unione in parallelo. Non posso rispondere a loro a meno che tu non chiarisca quale tipo di fusione di ordinamento stai imparando.