Gleiches Laden für parallele Aufgabenverteilung

Question

Ich habe eine große Anzahl von unabhängigen Aufgaben, die ich ausführen möchte, und ich möchte sie auf einem parallelen System verteilen, so dass jeder Prozessor die gleiche Arbeit leistet und meine Effizienz maximiert. eine Lösung für dieses Problem zu finden, oder vielleicht nur eine gute Lösung für mein Problem genau

Ich würde gerne wissen, ob es ein allgemeiner Ansatz.

Ich habe T = 150 Aufgaben würde ich gerne laufen, und die Zeit, jede Aufgabe übernehmen wird, ist t = T. Das heißt, task1 dauert 1 eine Zeiteinheit, task2 dauert 2 Zeiteinheiten dauert ... task150 150 Zeiteinheiten. Unter der Annahme, ich habe n = 12 Prozessoren, was ist der beste Weg, um die Arbeitslast zwischen den Arbeitern zu teilen, die Zeit, vorausgesetzt, es nimmt Aufgaben zu beginnen und aufzuräumen vernachlässigbar ist?

Answer 1

Trotz meiner anfänglichen Begeisterung für @ genialen Ansatz der HighPerformanceMark, entschied ich mich GNU tatsächlich Benchmark dies unter Verwendung von parallelen mit -j 12 12 Kerne zu verwenden, und 1 Einheit der Arbeit mit 1 Sekunde Schlaf simuliert.

Zuerst erzeugt ich eine Liste der Arbeitsplätze mit vorgeschlagen:

paste <(seq 1 72) <(seq 150 -1 79) 

die wie folgt aussieht:

1 150 
2 149 
3 148 
... 
... 
71 80 
72 79 

Dann gebe ich die Liste in GNU parallel und die restlichen abholen 6 Arbeitsplätze am Ende in parallel:

paste <(seq 1 72) <(seq 150 -1 79) | parallel -k -j 12 --colsep '\t' 'sleep {1} ; sleep {2}' 
sleep 73 & 
sleep 74 & 
sleep 75 & 
sleep 76 & 
sleep 77 & 
sleep 78 & 
wait 

Th bei Läufen in 16 Minuten 24 Sekunden.

---

Dann habe ich meine etwas einfacher Ansatz, der nur große Jobs zuerst laufen, so dass Sie wahrscheinlich nicht am Ende mit allen Großen gelassen werden und dadurch Ungleichgewicht in CPU-Last, weil nur eine große Aufgabe Bedürfnisse zu laufen und der Rest Ihrer CPUs hat nichts zu tun:

time parallel -j 12 sleep {} ::: $(seq 150 -1 1) 

und das läuft in 15 Minuten 48 Sekunden, so ist es tatsächlich schneller.

---

denke ich, das Problem mit dem anderen Ansatz ist, dass nach den ersten 6 Runden 12 Paare von Arbeitsplätzen gibt es 6 Jobs links die längst davon 78 Sekunden in Anspruch nimmt, so effektiv 6 CPUs sitzen dort nichts zu tun für 78 Sekunden. Wenn die Anzahl der Aufgaben durch die Anzahl der CPUs teilbar wäre, würde dies nicht vorkommen, aber 150 teilt sich nicht durch 12.