che alla dimensione del blocco sarà cedere al meglio le prestazioni utilizzando master-lavoratore con MPI?

Question

Im usando MPI ad parrlel un programma che sta cercando di risolvere il problema metrica TSP. Ho processori P e N le città per passare.

Ogni thread richiede lavoro dal master, riceve un pezzo - che è un intervallo di permutazione che deve controllare e calcola il minimo fra loro. Sto ottimizzando questo potatura percorsi cattivi in ??anticipo.

Ci sono totale (N-1)! percorsi da calcolare. ogni lavoratore ottiene un pezzo con un numero che represnt il primo percorso che deve controllare e anche l'ultimo. Inoltre il maestro di lui il miglior risultato più recente conosciuto manda, così può itinerari cattivi facilmente inclini in anticipo con qualche limite inferiore per appenderci resti.

Ogni volta che un lavoratore sta trovando risultato che è meglio che il globale, manda asyncrounsly agli tutti gli altri lavoratori e al master.

Im non in cerca di una migliore soluzione- Sto solo cercando di determinare quale dimensione del blocco è il migliore.

La dimensione miglior pezzo che ho trovato finora è (n!) / (N / 2)! , Ma doesnt cedere così buon risultato.

ti prego, aiutami a capire che grandezza del chunk è il migliore qui. Sto cercando di equilibrio tra la quantità di calcolo e comunicazione grazie

Answer 1

Questo dipende fortemente da fattori fuori dal vostro controllo: implementazione MPI, carico totale sulla macchina, ecc, tuttavia, mi piacerebbe azzardare un'ipotesi che anche fortemente dipende da quanti lavoratori ci sono processi. In tal senso, comprendere che i processi genera MPI, non le discussioni.

In definitiva, come è spesso il caso con la maggior parte delle domande di ottimizzazione, la risposta è semplicemente "test un sacco di impostazioni diverse e vedere qual è il migliore". Si consiglia di eseguire questa operazione manualmente, o scrivere un'applicazione tester che implementa una sorta di euristica (ad esempio un algoritmo genetico).