Erste Performancemessungen von OMA

Erste Performancemessung von OMA

Einleitung

• MSA wird mit -g und -b aufgerufen: "gleiche Gewichtung" und "TermGaps zaehlen". Das heuristische Alignment von MSA liefert die obere Schranke fuer die OMA Algorithmen.
• GDUS ist eingeschaltet, SmartPrio wird verwendet
• Eine Segmentierung oder Iteration ueber die Segmentlaengen findet nicht statt

Sequenzdaten

Alle Tests wurden mit der Kostenmatrix dayhoff.cost durchgefuehrt.

Die verwendeten Sequenzdaten haben folgende Merkmale:

• prot5.seq, prot6.seq und prot7.seq: 5, 6 und 7 Protein-Sequenzen mit Laengen um etwa 70
• diplom.2.fasta: Gleichnamiger Datensatz aus [GSA2], meiner Dipl.; 5 Sequenzen mit Laengen um etwa 120
• diplom.8.fasta: (oder auch diplom.4.fasta) [GSA2]; 8 Sequenzen mit Laengen ab 420-460
• diplom.9.fasta: (oder auch diplom.5.fasta) [GSA2]; 9 Sequenzen mit Laengen ab 420-460

Testreihe 1

• cost: Kosten des berechnet Alignments. "=" heisst das das Programm den gleichen Wert lieferte.
• Objects: Anzahl der konstruierten (OMA-Library) Objekte insgesamt
• Edge: Anzahl der konstruierten Edge-Objekte
• reins E: Durch die Verwendung von GDUS mehrfach in die Queue eingefuegte Edges.
• Vertex: Anzahl der konstruierten Vertex-Objekte
• face invalid: Anzahl der mindestens einmal besuchten Gitterpunkte, die ausserhalb des face gueltigen Bereichs liegen und fuer die daher kein Vertex kreiert wurde.
• time real/user: mit time angezeigte Zeit in [s]
• mem[8kb]: Maximal angeforderter Speicher in 8kb-Pages
• htX: Performancemessungen bei den Hashtables, die an zwei Stellen im Programm verwendet werden; Q steht fuer die PriorityQueue und T fuer den Trie
  • gets/puts: Anzahl der get/put-Operationen. Die angegebenen Werte sind ohne die benoetigten Operationen waehrend Rehashings angegeben.
  • probes: Es wird open adressing verwendet. Das Verhaeltnis von "probes" zu "gets+puts" ist ein Mass fuer die Performance.

Hashtable-Performance

• k1 = "Speicheradresse dieses TrieBranch" und
• k2 = "Ordinate dieses ChildNodes in dieser Triedimension"

• /1.0: h2 = (k2<<4)^(k2<<1) | 1; Wurde auch fuer die Messungen von Tbl.1 verwendet.
• /1.1: h2 = k1 ^ k2; h2 = (h2<<4) ^ (h2<<1) | 1;

  union union_long_double {
    long   longvalue;
    double doublevalue;
  };
  union_long_double ld;
  ld.doublevalue = (((double)k1)+PI) * hashA1; // hashA1 is a "good" float number
  h1 = ld.longvalue;

Testreihe 2

Es wurde eine "Final Release" des Programms testMsa erstellt, d.h. alle zeitkritischen Debug-Ausgaben und -Messungen wurden entfernt. Daher koennen nur noch Zeit- und Speichermasse fuer die Performance angegeben werden. Es wurde mit Optimierung (mit dem SunPro-Compiler) compiliert.

Einige kleinere Aenderungen duerften die Performance noch leicht verbessert haben.

Ausserdem wurde der Speicherverbrauch an einer wichtigen Stelle noch gezielt auf die Tests optimiert: Grosse Teile der Distanzmatrizen werden vor den Start des Hauptalgorithmus entfernt.

Der verwendete Hashfunktion ist h2/1.1 aus Tabelle 2.

Der verwendete Rechner fuer die Messungen war q.

Diese Programmversion nennen wir testMsa/2.1/final.

Protokoll Erlaeuterung

[ 1]    EQVertexmap: gets:1359582, puts:565378, probes:4567433, rehashes:2
[ 2] Counted reinserted edges: 200
[ 3] Visited different face invalid Vertex's (hull of search space): 975567
[ 4]    TrieChildmap: gets:160767463, puts:1763856, probes:290449756, rehashes:5
[ 5] 
[ 6] gsa2-cost: 221276
[ 7] Object:+1385652-1385651=1
[ 8] Exception:+0-0=0
[ 9] Edge:+565378-565378=0
[10] Vertex:+47897-47897=0
[11] #MemAfter:
[12]  F S   UID   PID  PPID  C PRI NI     ADDR     SZ    WCHAN TTY      TIME CMD
[13]  8 S  1613  8016  7973  9  99 20 7ad064f8  65648 7ad06568 pts/14  33:35 testMsa
[14] 
[15] real    33m43.220s
[16] user    33m29.500s
[17] sys     0m12.150s

• [1] Performance der Hashtable der EdgeQueue. Sie dient zum Auffinden eines Edges anhand seiner beiden Endpunkt-Vertices. Angegeben ist die Zahl der Basisoperationen des Hashtables ausserhalb von Rehashings.
• [2] Bei GDUS werden Kanten auch nach dem Ausfuegen aus der Queue wieder eingefuegt. Hier die Anzahl dieser Faelle.
• [3] Bei der Aufzaehlung der Nachbarn eines Vertextes wird jeder Nachbar geprueft, ob er face gueltig ist. Hier ist die Anzahl der besuchten Vertices, die nicht face gueltig waren. Fuer jeden dieser ungueltigen Vertices wird ein Element in den Trie eingetragen (siehe htT).
• [4] Performance der Hashtabelle des Tries, mit dem die Koordinaten der Vertices verwaltet werden. Die Tabelle implementiert die Beziehung: "Adresse des Kindknotens" = get("Adresse Vaterknoten", "Ordinate Kindknoten").
• [6] Kosten des berechneten Alignments.
• [7] Gezaehlte OMA-Objekte: "+" aufgerufene Konstruktoren, "-" Destruktoren, "=" MemLeaks und statische Objekte.
• [8] Gezaehlte OMA-Exceptions.
• [9] Gezaehlte Edge-Objekte.
• [10] Gezaehlte Vertex-Objekte.
• [11-13] Ausgabe von "ps" zum Programmaufruf, kurz vor Ende. Unter SZ steht die Anzahl der angeforderten Speicherzeiten, hier zu je 8kb Groesse.
• [15-17] Ausgabe von "time" zum Programmaufruf.

Literatur