mikrocontroller.net

Forum: Offtopic Multiprozessorsysteme und klassische Komplexitätsprobleme


Autor: Andre (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

: Verschoben durch User
Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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. ;-)

Autor: Student (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

Autor: klaus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: IGCT (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dabei fällt mir ein... P != NP

http://www.scribd.com/doc/35539144/pnp12pt Das wäre schon der Hammer 
wenns stimmen sollte...

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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-t...

Andreas

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.