|
Anzeige
|
Multiprozessorsysteme und klassische Komplexitätsprobleme
Gast
#1829975
Hallo an das Forum, ich hätte mal eine Grundsatzfrage. Ich würde gerne wissen, wie sich künftige Multiprozessorsystem, auf klassische Probleme aus Komplexitätstheorie auswirken (z.b polynomielle oder exponentielle Probleme)? Was denke ihr wie sich die Schranken verändern ?? Gruß Andre Andre schrieb: > Ich würde gerne wissen, wie sich künftige Multiprozessorsystem, auf > klassische Probleme aus Komplexitätstheorie auswirken (z.b polynomielle > oder exponentielle Probleme)? Ungefähr ab unendlich vieler paralleler Prozessoren wird sich substantiell etwas an der Theorie verändern. ;-)
Gast
#1830045
GPUs haben schon viele hundert bis knapp über tausend kleine Rechenkerne. Supercomputer haben mehrere hunderttausend Rechenkerne. Alles schon jetzt verfügbar. Das ändert an der Theorie aber nix ;-)
Gast
#1830103
Komplexitätsberechnungen werden immer anhand gewisser Rechnermodelle gemacht, typischerweise die detereministische Turingmaschine (= 1-Kern-Prozessor), die nichtdeterministische Turingmaschine (= Prozessor, der alle Rechenwege gleichzeitig ausprobiert bzw. sich immer für den richtigen Rechenweg entscheidet) und dann noch Netzwerkmodelle, wo eine Anzahl Knoten über eine klar definierte Kommunikation (Message Passing oder Shared Memory) das Problem lösen. Die Theorie ist auch für Multiprozessorsysteme weitgehend untersucht und bekannt. Theoretisch gesehen bringt ein Multiprozessorsystem bestenfalls einen Speed-up von n bei n Prozessoren, die Komplexität ändert sich also vom Ein- zum n-Kernsystem bestenfalls von O(x) nach O(x/n). Tatsächlich verringert sich der Speed-up noch stark, da die Prozessoren kommunizieren und aufeinander warten müssen und gewisse Berechnungen nicht parallelisiert werden können.
Gast
#1830128
Dabei fällt mir ein... P != NP http://www.scribd.com/doc/35539144/pnp12pt Das wäre schon der Hammer wenns stimmen sollte...
Gast
#1830161
IGCT schrieb: > Dabei fällt mir ein... P != NP > > http://www.scribd.com/doc/35539144/pnp12pt Das wäre schon der Hammer > wenns stimmen sollte... Das ist doch nun schon ein alter Hut. Der Thread dazu findet sich hier etwas weiter hinten und es stimmt ziemlich wahrscheinlich. Ihr wisst doch nach dem Problem ist vor dem Problem und ein gelöstes ist immer leicht. IGCT schrieb: > Dabei fällt mir ein... P != NP > > http://www.scribd.com/doc/35539144/pnp12pt Das wäre schon der Hammer > wenns stimmen sollte... Sieht eher schlecht aus, war wohl nur ein Sturm im Wasserglas: http://www.newscientist.com/article/dn19313-tide-turns-against-milliondollar-maths-proof.html Andreas Antwort schreibenBitte melde dich an, um einen Beitrag zu schreiben. |
Anzeige
|
