Zulässigen Abweichungen

[xshisdi32]

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]

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

[xshisdi32]

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

[mw1039]

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]

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]

Mit HIV Input würde es wahrscheinlich gar nicht laufen, da es nicht genug Local memory gibt.

Notfalls z.B. auf 500 Sequenzen gekuerzt.

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]

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]

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]

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]

Also unabhaengig davon, ob man ueber die Genauigkeit von double und float diskutiert, ist eine Abweichung von

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

0.000999210623592 %

ist doch vollkommen OK. Sie liegt doch deutlich unter 0,1%

[xshisdi32]

Also unabhaengig davon, ob man ueber die Genauigkeit von double und float diskutiert, ist eine Abweichung von

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.

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]

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

[mw1039]

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]

Hallo,

ist eine relative Abweichung von unter 5% akzeptabel ?

viele Gruesse

[kbraden]

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.