Zulässigen Abweichungen

xshisdi32
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 10. Apr 2011 17:24
Wohnort: Bessungen, Darmstadt
Kontaktdaten:

Zulässigen Abweichungen

Beitrag von xshisdi32 » 19. Jan 2012 16:32

Code: Alles auswählen

line ['x=185 y=1007: 0.000110168', 'x=185 y=1007: -2.14978e-08'] differs by 512561.740271 %
one value was too small ['x=187 y=1007: 0.000110168', 'x=187 y=1007: -2.14978e-08']
line ['x=187 y=1007: 0.000110168', 'x=187 y=1007: -2.14978e-08'] differs by 512561.740271 %
one value was too small ['x=175 y=1008: 6.61027e-05', 'x=175 y=1008: -2.95595e-08']
line ['x=175 y=1008: 6.61027e-05', 'x=175 y=1008: -2.95595e-08'] differs by 223725.907069 %
one value was too small ['x=184 y=1008: 6.61027e-05', 'x=184 y=1008: -2.95595e-08']
[...]
comparison of 510555 entries finished
maximum relative deviation was 1.02234433339e+15 %, average relative deviation was 28946305211.0 %
Ich vermute dass auch solche kleine Abweichungen nicht zulaessig sind?

Ich weiss schon dass 223725 % nicht deutlich unterhalb von 0,1% liegen. Natürlich geht es dann nicht, wenn die Regeln wirklich so buchstäblich interpretiert werden sollen.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Zulässigen Abweichungen

Beitrag von mw1039 » 19. Jan 2012 18:59

Welche Seite ist denn welche? Ist der erste Wert der von der CPU-Loesung oder der aus deiner Loesung?

xshisdi32
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 10. Apr 2011 17:24
Wohnort: Bessungen, Darmstadt
Kontaktdaten:

Re: Zulässigen Abweichungen

Beitrag von xshisdi32 » 19. Jan 2012 19:49

Links ist meine. Aber macht es in diesem Fall ein Unterschied? Der Differenz ist schon über 0,1% in beiden Fälle.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Zulässigen Abweichungen

Beitrag von mw1039 » 20. Jan 2012 10:27

Ist an der Stelle 185, 1007 deine erste Abweichung oder gibt es vorher schon andere?
Versuch mal bitte das UCLA-HIV-File (http://bioinfo.mbi.ucla.edu/HIV/ ganz unten) durchlaufen zu lassen. Notfalls z.B. auf 500 Sequenzen gekuerzt. Kommst du dann auf das gleich Ergebnis wie die CPU?

xshisdi32
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 10. Apr 2011 17:24
Wohnort: Bessungen, Darmstadt
Kontaktdaten:

Re: Zulässigen Abweichungen

Beitrag von xshisdi32 » 20. Jan 2012 15:30

mw1039 hat geschrieben:Ist an der Stelle 185, 1007 deine erste Abweichung oder gibt es vorher schon andere?
Versuch mal bitte das UCLA-HIV-File (http://bioinfo.mbi.ucla.edu/HIV/ ganz unten) durchlaufen zu lassen. Notfalls z.B. auf 500 Sequenzen gekuerzt. Kommst du dann auf das gleich Ergebnis wie die CPU?
Nein, das ist nur ein Beispiel. Fast alle Zeilen haben Abweichungen. Insgesamt 25000 Zeilen im Comparatoroutput, das heisst ca. 12500 Zeilen mit grosse Unterschieden. Es gibt aber 510555 Zeilen insgesamt. Ich habe diese Zielen gewählt, weil ich wissen wollte, ob die Prozent-Abweichung auch mit solche kleine Zahlen relevant ist. Mit Zahlen die nicht fast 0 sind habe ich 1-3% Abweichung (natürlich nicht akzeptabel). Ich bin mir sicher, das ich genau solche Abweichungen mit HIV Input bekommen würde. Ich habe nähmlich die OnePointProbs mit ushort's (als Fraktion von 0-USHRT_MAX) repräsentiert (halfes haben slechte NVIDIA Unterstützung, AFAIK), um alles in Local memory (49K) halten zu können.

EDIT: Mit HIV Input würde es wahrscheinlich gar nicht laufen, da es nicht genug Local memory gibt. Das ist aber egal, im Aufgabe steht dass das Abgabe-Program nur mit test.fasta getestet wird.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Zulässigen Abweichungen

Beitrag von mw1039 » 20. Jan 2012 16:01

xshisdi32 hat geschrieben:Mit HIV Input würde es wahrscheinlich gar nicht laufen, da es nicht genug Local memory gibt.
mw1039 hat geschrieben:Notfalls z.B. auf 500 Sequenzen gekuerzt.
xshisdi32 hat geschrieben:Das ist aber egal, im Aufgabe steht dass das Abgabe-Program nur mit test.fasta getestet wird.
Bzgl. des Testats und der Geschwindigkeit mag das egal sein aber nicht bzgl. der Korrektheit. Vielleicht kann man darueber feststellen, ob test.fasta irgendwie besonders boesartig ist, deine Loesung aber vielleicht mit anderen Files funktioniert.
Probiers am besten einfach mal. So lange dauert es ja nicht.

xshisdi32
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 10. Apr 2011 17:24
Wohnort: Bessungen, Darmstadt
Kontaktdaten:

Re: Zulässigen Abweichungen

Beitrag von xshisdi32 » 20. Jan 2012 19:29

mw1039 hat geschrieben: Bzgl. des Testats und der Geschwindigkeit mag das egal sein aber nicht bzgl. der Korrektheit. Vielleicht kann man darueber feststellen, ob test.fasta irgendwie besonders boesartig ist, deine Loesung aber vielleicht mit anderen Files funktioniert.
Probiers am besten einfach mal. So lange dauert es ja nicht.
Ich nehme an, dass Sie mit "500 Sequenzen gekuerzt" meinen, dass ich die Anzahl von Sequenzen von 45161 in 500 reduzieren (einfach Zeilen wegschmeißen) soll. Das würde aber kein Sinn machen, da onePointProbs die Länge sequenceLength * NUMPROTEINCHARS hat. Das heisst, die Länge ist unabhängig von Anzahl von Sequenzen.

Deshalb habe ich angenommen dass Sie die Sequenzlänge von 1443 bis 500 reduzieren wollte, so dass es genug Speicher gibt. 500*22 chars *2 bytes = 22000 bytes. 22000 bytes < 49K bytes. Um nicht so viel Daten zu verlieren, habe ich es aber nur bis 1020 reduziert. 1020*22*2 = 44880.

Ich habe die Sequenzlänge so gekürzt (17 * 60 (Zielenlänge) = 1020):

Code: Alles auswählen

grep -E '^>' -A 17 < speciality.fasta  | grep -vE '^--$' > newspeciality.fasta
Ich habe Quelldaten und Ergebnisse in diese Archiv gepackt: /home_export/LABACCOUNTS/gdi3user174/janus/localmem/prak5/build/pack.tar.bz2
Online hier: http://clientssh1.rbg.informatik.tu-dar ... ck.tar.bz2

Excerpt:

Code: Alles auswählen

line ['x=285 y=1019: 0.000118874', 'x=285 y=1019: 0.000355921'] differs by 199.410299981 %
[...]
line ['x=1012 y=1019: 0.00902593', 'x=1012 y=1019: 0.00920905'] differs by 2.02882140677 %
line ['x=1013 y=1019: 0.00850136', 'x=1013 y=1019: 0.00869023'] differs by 2.22164453687 %
line ['x=1014 y=1019: 0.0125235', 'x=1014 y=1019: 0.0127581'] differs by 1.87327823691 %
line ['x=1015 y=1019: 0.0149186', 'x=1015 y=1019: 0.0151561'] differs by 1.59197243709 %
line ['x=1016 y=1019: 0.014326', 'x=1016 y=1019: 0.0145536'] differs by 1.58871981014 %
comparison of 520710 entries finished
maximum relative deviation was 505666.561514 %, average relative deviation was 270.026753712 %

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Zulässigen Abweichungen

Beitrag von mw1039 » 23. Jan 2012 10:35

Mit deinem Testfile kriege ich als Abweichung zur CPU-Referenz folgendes raus:

Code: Alles auswählen

comparing cpureferenceresult and newspeciality.fasta.MI.out
comparison of 520710 entries finished
maximum relative deviation was 0.000992999354551 %, average relative deviation was 1.14252870618e-07 %
Im Grunde gibt es die Abweichungen nur, weil die FPU eine andere als die der CPU ist und weil im parallelen Algorithmus wahrscheinlich in einer anderen Reihenfolge aufaddiert wird als im sequentiellen Algorithmus.
Das mit den 0,1% war in der Aufgabenstellung sehr sehr konservativ geschaetzt und eigentlich sollten die Abweichungen (so wie oben) deutlich darunter liegen.

Alles was darueber liegt, deutet nicht auf numerische Abweichungen hin, sondern darauf, dass der Algorithmus fehlerhaft implementiert wurde.

xshisdi32
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 10. Apr 2011 17:24
Wohnort: Bessungen, Darmstadt
Kontaktdaten:

Re: Zulässigen Abweichungen

Beitrag von xshisdi32 » 26. Jan 2012 09:46

Ich weiss schon warum es diese Abweichungen gibt. Wie vorher gesagt: ich repräsentiere OnePointProbs mit ushorts. Wenn es absolut nicht mehr als 0.1% unterschiedlich sein darf, glaube ich, dass es nur mit float (oder größer) Datentypen geht. Ich finde es merkwürdig dass die Abweichung nicht als Epsilon angegeben wurde. Wenn man eine Repräsentation mit doubles hat, ist die Unterschied im Ergebnis (zwischen Ergebnis mit onePointProbs als float und onePointProbs als double) schon durchschnittlich ~0.00099%, aber die Genauigkeit von double-Berechnungen ist theoretisch größer! Das heißt, es geht überhaupt nicht, die mathematische Formel komplett genau zu implementieren, da es "zu genau" wäre, in Fällen wo IEEE 764 sehr slechte genauigkeit hat.

Hier ist die Unterschied zwischen zwei CPU aufgaben, eine mit onePointProbs als float (original), die andere mit double:

Code: Alles auswählen

comparing cpu and fasta.MI.out
comparison of 510555 entries finished
maximum relative deviation was 0.000999210623592 %, average relative deviation was 5.7878007794e-06 %

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Zulässigen Abweichungen

Beitrag von mw1039 » 26. Jan 2012 10:21

Also unabhaengig davon, ob man ueber die Genauigkeit von double und float diskutiert, ist eine Abweichung von
xshisdi32 hat geschrieben:505666.561514 %
indiskutabel.
Was spricht denn dagegen fuer die onePointProbs floats zu benutzen? Die onePointProbs machen sicher nicht den Loewenanteil des Speicherverbrauchs im lokalen Speicher eines Kernels aus. Da sind die (sofern du analog zur CPU-Loesung vorgehst) twoPointOccurences wesentlich bedeutsamer. Und damit bei denen keine Ungenauigkeiten passieren, werden sie als ints aufsummiert. Da das test-Sequenzfile weniger als \(2^{16}\) Sequenzen hat, kannst du da aber gerne auch shorts benutzen.
Deine CPU-CPU-Abweichung
xshisdi32 hat geschrieben:0.000999210623592 %
ist doch vollkommen OK. Sie liegt doch deutlich unter 0,1%

xshisdi32
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 10. Apr 2011 17:24
Wohnort: Bessungen, Darmstadt
Kontaktdaten:

Re: Zulässigen Abweichungen

Beitrag von xshisdi32 » 26. Jan 2012 11:54

mw1039 hat geschrieben:Also unabhaengig davon, ob man ueber die Genauigkeit von double und float diskutiert, ist eine Abweichung von
xshisdi32 hat geschrieben:505666.561514 %
indiskutabel.
Was spricht denn dagegen fuer die onePointProbs floats zu benutzen?
Es gibt nicht genug __local memory. (4 bytes *1020*22) = 89760 bytes. Es gibt nur 49152 bytes. Mit shorts passt es: 2*1020*22=44880.
mw1039 hat geschrieben:Die onePointProbs machen sicher nicht den Loewenanteil des Speicherverbrauchs im lokalen Speicher eines Kernels aus. Da sind die (sofern du analog zur CPU-Loesung vorgehst) twoPointOccurences wesentlich bedeutsamer.
twoPointOccs hat die Länge NUMCHARS*NUMCHARS. Das heisst, es ist nur 4*22*22 = 1936 bytes.

oliver_g
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 17. Nov 2008 16:27

Re: Zulässigen Abweichungen

Beitrag von oliver_g » 26. Jan 2012 13:15

Du kannst die onePointProbs auch gut im globalen Speicher lassen. Bei einer ordentlichen Implementierung ist der Zugriff darauf nicht der Flaschenhals.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Zulässigen Abweichungen

Beitrag von mw1039 » 26. Jan 2012 13:26

xshisdi32 hat geschrieben:Es gibt nicht genug __local memory. (4 bytes *1020*22) = 89760 bytes. Es gibt nur 49152 bytes. Mit shorts passt es: 2*1020*22=44880.
Du brauchst nicht die gesamten Ein-Punkt-Wahrscheinlichkeiten in den lokalen Speicher jeder Workgroup kopieren. Jede Workgroup interessieren eigentlich nur die Ein-Punkt-Wahrscheinlichkeiten der Spalten, auf denen sie arbeitet. Wenn z.B. eine Workgroup 1 Matrixeintrag berechnet, interessiert sie nur 2 Spalten und der Speicherverbrauch ist 2*22*sizeof(welchen_Datentyp_auch_immer_du_benutzen_magst).
Oliver hat Recht. Du hast wahrscheinlich nur einen Vorteil davon die onePointProbabilities in den lokalen Speicher zu kopieren, wenn man auf einem Datensatz mit erheblich mehr Sequenzen (z.B. dem vollstaendigen Specialty-sequences-Datensatz) arbeitet, oder wenn man so parallelisiert, dass jede Workgroup \(\Delta_i\cdot\Delta_j\) Matrixeintraege berechnet.

charfi90
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 8. Sep 2010 15:40

Re: Zulässigen Abweichungen

Beitrag von charfi90 » 27. Jan 2012 10:14

Hallo,

ist eine relative Abweichung von unter 5% akzeptabel ?

viele Gruesse

kbraden
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 15. Okt 2010 20:35

Re: Zulässigen Abweichungen

Beitrag von kbraden » 27. Jan 2012 10:25

Nope.

Punkt 3.5 (Testfiles & Beurteilung der Korrektheit) der Aufgabenstellung sagt: Ihre maximale Abweichung (der erste Wert der letzten Zeile der Ausgabe von outfilecomparer.py) zur reinen CPU-Version sollte deutlich unterhalb von 0.1% liegen.

Antworten

Zurück zu „Archiv“