2x cross versus 2x dot product

Moderator: Graphische Datenverarbeitung 1

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

2x cross versus 2x dot product

Beitrag von Red*Star »

Hallo, da ich nicht weiß wo es sonst reinpasst:

Ich lese immer immer wieder, z.B. auch hier - http://softsurfer.com/Archive/algorithm ... t-Triangle -, dass es aus Performancegründen Sinn macht ein doppeltes Kreuzprodukt gemäß der BAC-CAB-Regel durch zwei Skalarprodukte zu ersetzen:

\(\vec{a}\times(\vec{b}\times\vec{c}) = \vec{b}\,(\vec{a}\cdot\vec{c})-\vec{c}\,(\vec{a}\cdot\vec{b})\,\)

Wenn ich mich aber nun nicht verrechnet habe, dann hat die cross-cross-Variante auf der CPU 18 Flops (6 Additionen, 12 Multiplikationen), während die andere (empfohlene!) Variante 19 Flops (7 Additionen, 12 Multiplikationen) verbrät.

Hm. Hat dazu schon mal jemand was gelesen? Gibt es noch einen versteckten Grund, warum der Einsatz der Regel Sinn macht (auf der CPU, wohlgemerkt, sofern man spezialisierte Hardware hat, z.B. eine GPU, kommen ja eh wieder zusätzliche Faktoren ins Spiel)?

Anderenfalls:
Nimmt man die Erfahrungen von einigen "großen" ;) Computerwissenschaftlern hinzu - "Premature optimization is the root of all evil." oder "The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet." *) -, dann stellt sich mir die Frage, ob die Leute, die obige Regel empfehlen, nicht vielleicht einfach nur Angst vor dem Kreuzprodukt haben ;), oder zumindest ohne zu denken einfach irgendwas nachplappern, was sie mal wo gehört haben, was aber eigentlich gar nichts bringt, sondern nur den Quellcode unverständlicher macht.


*) Zitate von http://en.wikipedia.org/wiki/Optimizati ... ce)#Quotes
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: 2x cross versus 2x dot product

Beitrag von MisterD123 »

liegt an der paralellisierbarkeit würd ich sagen, das rechte kannst du in drei schritten ausrechnen (beide werte in den klammern multiplizieren, beide werte außerhalb der klammer multiplizieren, subtraktion) während du links vier schritte brauchst (pro kreuzproduktrechnung einmal: multiplizieren (a1*b2 und a2*b1 zB) und die ergebnisse dann subtrahieren)

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Re: 2x cross versus 2x dot product

Beitrag von Red*Star »

Aber auf einer Single-Core-CPU klappt das mit dem Parallelisieren schlecht, oder? Na gut, es gibt da ja noch diese MMX extensions seit dem Pentium, und bestimmt auch sonst noch ganz viele tolle Chipsatz-Features... (für solche Hardwaresachen hab ich mich bislang nie sonderlich interessiert) - dann müsste man allerdings einen Compiler haben, der genau solche Optimierungen durchführt, damit das mit der BACCAB-Sache Sinn macht.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: 2x cross versus 2x dot product

Beitrag von MisterD123 »

letzendlich führt ja aber doch der renderer, in dem fall deine grafikkarte, die rechnung durch, und das ist dann nunmal hardware ;) renderer die in software rechnen sind normalerweise für einzelbilder, und da ist dann auch nicht mehr jedes einzelne gesparte befehl gold wert.

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Re: 2x cross versus 2x dot product

Beitrag von Red*Star »

Hehe, naja, wir machen gerade Raytracing in GDVI, und in dem Zusammenhang ist bei mir auch die Frage aufgetaucht ;)
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Benutzeravatar
Render
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 12. Okt 2008 17:21

Re: 2x cross versus 2x dot product

Beitrag von Render »

Soweit ich das auf der verlinkten Seite verstehe wird dort das zweifach Kreuzprodukt durch das zweifach Skalarprodukt ersetzt um die Berechnung von s und t umformen zu können und dort einige Multiplikationen zu sparen weil viele Skalarprodukte mehrfach auftauchen.

ykaerflila
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 9. Mai 2006 22:01
Wohnort: Mainz
Kontaktdaten:

Re: 2x cross versus 2x dot product

Beitrag von ykaerflila »

Die empfohlene Variante könnte beim PIPELINING schneller sein - auch auf Single-Core-CPUs. Geprüft habe ich es aber nicht :-)
icq# 117752728
email: 7pinacoladas@gmx.net

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Re: 2x cross versus 2x dot product

Beitrag von Red*Star »

Okay, genug Faktoren um mit dem Problem eine ganze Bachelorarbeit zu füllen... ich glaube ich *teste* es einfach mal, wenn ich Zeit hab. Empirisch. :D
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Antworten

Zurück zu „Graphische Datenverarbeitung 1“