Beiträge von Blubberblase

Hallo Forum,
ich habe zwei Algorithmen gemessen und in folgendem Diagramm dargestellt:

Um herauszubekommen ob die Komplexitäten diesselben sind habe ich den Laufzeitwert von solve an der Stelle 3000 mit einem konstanten Faktor F multipliziert, sodass das Produkt dem Laufzeitwert von solveBPB entspricht.

Nun alle Messwerte von solve mit diesem Faktor F multipliziert und folgenden Graph erhalten:

Die Kurve des gelben graphen steigt ja nun scheinbar viel stärker an als die kurve des roten graphen. Kann ich schlussfolgern, dass die Komplexität von solveBPB geringer ist als von solve (da F*solve stärker ansteigt) und solve bpb für diese werte somit nur durch einen konstanten faktor geringer ist?

Okay, bei den Messungen mag das vllt. nicht funktionieren.
Ich habe durch Berechnungen folgendes festgestellt:

Sei B als Blockgröße definiert. (Größe einer Speicherzelle).

Es werden genau (1/B) * N^3 Operationen ausgeführt.

Die Laufzeit hat also die Komplexität von:

c * (1/B) * N^3

Nun bringe ich 1/B einfach in den Exponenten.
1/B = N^(log von 1/B zur Basis N)

Einsetzen:

c * N^(log von 1/B zur Basis N) * N^3

Zusammenfassen:

c * N^(3 + log von 1/B zur Basis N)

EDIT: Vereinfacht: c * N^(3 - log von B zur Basis N)

Leider weiß ich nicht ganz wie ich das N aus dem exponenten bekomme aber damit kann ich doch zeigen, dass für große Blockgrößen (z.B. 64 Bit) die Komplexität verringert werden kann(denn die Ordnung verringert sich ja), oder?

Beispielrechnung für N = 800

Ohne Faktor (1/B): N^3

Mit Faktor (1/B): N^2,48

Wenn ich also nachweisen möchte, dass die Komplexität durch einen Faktor gesenkt wird, sollte ich dann diesen Faktor einfach in den Exponenten bringen um so den Unterschied in der Ordnung nachzuweisen, statt den Faktor vor das N zu schreiben?

Hallo Forum!
Ich habe die Laufzeiten zweier Algorithmen in Abhängigkeit von der Eingabegröße gemessen und die Messwerte anschließend in einem Diagramm abgetragen (und jeweils eine Kurve generiert).
Die Kurve von Algorithmus 1 wächst steiler als von Algorithmus 2 (beide Algorithmen haben eine kubische Komplexität).

Beim Ausrechnen der Komplexität gibt es ja einen konstanten Faktor c, der hardwarespezifisch ist. Je nach Prozessor kann ein Algorithmus ja schneller oder langsamer laufen und das c kann somit kleiner oder größer sein.
Algorithmus 1 und 2 wurden jeweils unter selben Bedinungen gemessen. Der hardwarespezifische Faktor c müsste also bei beiden gleich sein. Da Algorithmus 1 jedoch schneller wächst (meinetwegen 3n^3) als Algorithmus 1(z.B. 1n^3), kann man doch behaupten, dass die Komplexität von Algorithmus 1 größer ist als von Algorithmus 2, oder? Ich habe bis jetzt immer nur gesehen, dass die Komplexität durch den Exponenten festgelegt wird. Dann wäre sie ja bei beiden Algorithmen gleich...

Danke für die Antworten...
Ich habe mit meinem Betreuer vereinbart dass ich Fußnoten für Quellenverweise verwende, da das den Vorteil hat dass man nicht erst jedes mal umblättern muss, wenn man nach der Quelle suchen möchte.
Die Variante mit den Kurzbezeichnungen schein vllt. gar nicht so schlecht zu sein.

Also sollte ich für die Begriffserklärungen das meinetwegen so angehen
Begriff1*
Begriff2**
usw. ?

Hallo Forum!
Ich verwende in meiner Arbeit Fußnoten um auf Quellen zu verweisen. Diese Fußnoten befinden sich dann am unteren Rand jeder Seite. Nun habe ich zwei fragen:

Ich möchte in meinem Text schreiben, dass ich ein Beispiel verwende, was in einer wissenschaftlichen Arbeit aufgetaucht ist. Wie organisiere ich das am besten? Meinetwegen steht in meinem Text: "Ich verwende das Beispiel aus der Vorstellung über ... von ... [FUßNOTE]."
Jetzt steht am unteren Seitenrand:
[FUßNOTE] Name, Vorname, Titel, Datum der Veröffentlichung

Nun muss ich aber noch ein Literaturverzeichnis angeben. Dort stehen ja dann alle Quellen alphabetisch aufgelistet. Welche Daten müssen dann dort rein?
Also wieder Name, Vorname, Titel, Datum der Veröffentlichung, vllt. noch Seitenzahl?

Meine zweite Frage ist: Ich habe in einem Text fußnoten (also zahlen) für Quellen verwendet. Nun schreibe ich von einem begriff, den ich nicht extra im Text erklären möchte, sondern gesondert auch am unteren Rand erklären möchte. Ich kann ja jetzt nicht ebenfalls mit zahlen als fußnoten den begriff markieren und unten erklären. Was kann man stattdessen machen?

Super, bis dahin konnte ich alles nachvollziehen.
Wie kann man eigentlich herausbekommen wie groß diese Cacheline ist?

Nun noch zu einem anderem Problem. Jetzt habe ich folgende Funktion wieder für verschiedene Blockgrößen gemessen:

typedef unsigned int BLOCK;
//typedef uint8_t BLOCK;
//typedef uint16_t BLOCK;


const int BITS_PER_BLOCK = sizeof(BLOCK)*8;


int N = 60000;


int creatematrix(BLOCK *pos) {
 BLOCK shift=0; int BPB = BITS_PER_BLOCK -1;
    int row, col;
 for(row = 0; row < N; row++) {
   for(col = 0; col < N; col++) {
    if(col&1)
       shift |= (1 << (col & (BPB)));

   }     
 }
 return 0; 
}

(Das col&1 ist wie eine Art Platzhalter für eine sehr viel komplexere Bedingung, die aber unabhängig von der Blockgröße ist, aber zur Vereinfachung bei den Messungen weggelassen wurde)
Der Sinn der Funktion sei jetzt mal unwichtig.

Ich habe folgende Messergebnisse bei einem N von 60000 für die Blockgröße 32 Bit, 16 Bit und 8 Bit erhalten:

32 Bit: 8,15
16 Bit: 8,57
8 Bit: 9,22

Das Ergebnis verblüfft mich ehrlich gesagt etwas.
Die einzigen Variablen, die abhängig von der Blockgröße sind, sind shift und BPB. Aber warum ist diese Operation shift |= (1 << (col & (BPB))); für 32 Bit schneller als für kleinere Blockgrößen?
Ich habe einen 32 Bit Prozessor. Vielleicht füllt der Rechner ja dieses shift mit zusätzlichen Nullen, damit es im 32 Bit Prozessor gut verarbeitet werden kann. Und das kostet Zeit? Während das beim 32 Bit-shift ja nicht möglich ist...
Jetzt habe ich folgendes gemacht: Ich habe bei der Deklaration von shift ein "register" mit beigefügt. Das bewirkt seltsamerweise, dass für alle(!!) Laufzeiten der Wert etwa bei 7,08 liegt. Also fällt meine Erklärung schoneinmal weg, denn offensichtlich wird shift in der obigen Funktion nicht als Registerobjekt behandelt.
An dieser Stelle bin ich mit meinen Erklärungen am Ende und weiß leider nicht mehr weiter...

Vielen Dank für die Hilfe!
Die optimierte Variante scheint wirklich viel besser zu sein.
Also kann ich zusammenfassen, dass die Zeit vor allem ersteinmal durch den Zugriff auf den Cache zu verzeichnen ist.
Dauert es also länger wenn ich auf ein Double Word im Cache zugreife, als auf ein Word?

Zitat

Edit: Das sollte ich vielleicht etwas qualifizieren. Wie alle anderen Objekte im Speicher wird auch dein Array stückweise durch den Cache geschleift werden, aber auch zwischen Cache und Speicher bleiben bei größerer Blockgröße mehr Speicheroperationen über.

Nun kann ich ja davon ausgehen, dass bei kleinerer Blockgröße der Cache weniger nachgeladen werden muss. Angenommen das Nachladen kostet eine gewisse Zeit t. Meinst du damit, dass für eine kleinere Blockgröße das Nachladen im einzelnen weniger Zeit brauch?

Wegen dem C-Code... Das mit dem Deklaration in der for Schleife ist mir beim Beitragschreiben passiert (ich habe den Code nach dem Einfügen noch etwas verändert). Aber mein Compiler meckert, wenn ich das so compilieren würde. Aber ich verstehe nicht wieso man keine // als Kommentarzeichen in C verwenden kann?

Ich habe nocheinmal eine Frage bezüglich Cacheobjekten.
Meine Funktion sieht wie folgt aus:

typedef unsigned int BLOCK; // sind 32 Bit
//typedef uint8_t BLOCK;
//typedef uint16_t BLOCK;


int creatematrixBPB(BLOCK *pos) {
 int row, col;
 for (row = 0; row < N; row++) {
        for(col = 0; col < N; col++) {
            if(col&1)
                (*pos++) = (BLOCK)1;
            else (*pos++) = (BLOCK)0;
   }   
 }   
    return 0; 
}

Vor dem Funktionsaufruf habe ich schon Speicher angefordert:
BLOCK *pos = malloc(N * N * sizeof(BLOCK));

Ich habe die Funktion für verschiedene Blockgrößen getestet. Und dabei folgende Messungen erhalten(für N = 12000)

32 Bit: 0,93 s
16 Bit: 0,56 s
8 Bit: 0,41 s

Nun habe ich den Algorithmus nocheinmal gestartet, wobei ich KEINE Zeigererhöhungen (++pos) eingebaut habe, sondern nur *pos = 1 geschrieben habe.
Dabei habe ich bei einem N von 12000 eine konstante Zeit von 0,34s gemessen.

Jetzt habe ich die Zeit berechnet, die für das Zeigererhöhen draufgeht:

32 Bit: 0,93 s - 0,34 = 0,59
16 Bit: 0,56 s - 0,34 = 0,22
8 Bit: 0,41 s - 0,34 = 0,07

Eine Verdopplung der Blockgröße führt zu ganz grob zu einer Halbierung der Laufzeit?
Kann ich diesen Sachverhalt darüber erklären, dass bei 32 Bit der Cache eher voll ist und mehr Cache nachgeladen werden muss, wodurch mehr Zeit verloren geht als bei den anderen Blockgrößen? (wenn ich vorraussetzen kann, das pos ein Cacheobjekt ist)?

Oder sind die Unterschiede ganz anders zu erklären?
(PS: Mehrfachmessungen wurden durchgeführt und jeweils ein Mittelwert gebildet)

Vieelen vieelen Dank für die gute Antwort!
Das hilft mir ersteinmal weiter

Hallo Forum!
Ich habe gehört dass es drei unterschiedliche Speicherklassen gibt:
- Registerobjekte
- Hauptspeicherobjekte
- Cacheobjekte

Diese Speicherklassen würden durch den Compiler beeinflusst werden. Wie kann man diese Speicherklassen grundsätzlich beschreiben und welchen Einfluss haben sie auf die Laufzeit?

Registerobjekte werden sicher in Register der CPU geladen und lassen sich schnell verarbeiten und abrufen. Dazu zählen sicherlich Zählvariablen in Schleifen. Wie ist das eigentlich wenn ich 3 Schleifen ineinander verschachtelt habe (mit 3 Zählvariablen)? Z.b.

for(int a=0; a < N; a++)
 for(int b=0; b < N; b++)
  for(int c=0; c < N; c++)

Wird dann beim Eintritt in eine untere Schleife die Zählvariable irgendwo zwischengelagert während die Zählvariable der unteren Schleife in das Register geladen wird?

Die Hauptspeicherobjekte finden sicherlich im Hauptspeicher platz. Gibt es da etwas zu beachten was die Laufzeit betrifft? Ich habe gehört, dass es günstig ist, wenn die Zieladresse des Sprungs an den Anfang durch 32 teilbar ist. Warum ist das so?

Ich kann mir noch nicht so richtig vorstellen wie das mit dem Pufferspeicher (Cache) funktioniert. Das ist also ein Zwischenspeicher auf dem schneller zugegriffen werden kann als auf den Hauptspeicher. Es wird immer ein bestimmter Teil geladen (Cacheline?) auf den zugegriffen werden kann. Wird jedoch mehr Cache benötigt, dauert das ganze länger, weil ja erst wieder Cache aus dem Hauptspeicher geholt werden muss. Es gäbe da angeblich soetwas wie prefetching wo man gleich mehr Cache anfordern kann. Wird das vom Compiler erledigt oder kann das der Programmierer z.B. in c selbst übernehmen?

Gibt es für mich eine Möglichkeit festzustellen welche Variablen von meinem Programm welcher Speicherklasse zugeordnet werden? Werden z.B. arrays grundsätzlich als Hauptspeicherobjekte behandelt? Kann ich in der Programmiersprache C darauf Einfluss nehmen welche Variable in den Hauptspeicher kommt oder als Zählvariable in ein Register oder macht das ausschließlich der Compiler?

Nun zu dem zweiten Teil meiner Frage, dem Pipelining. Was gibt es da bei der Programmierung zu beachten? Ich habe z.B. folgenden Quelltext:

for (int a = 0; a < N; a++)
   m1[a] += m2[a];

Hier hätte der Compiler doch ersteinmal kein Problem mit den Werten von m1. Beispielweise wird m1[0] verändert und es muss auch nicht mehr damit gearbeitet werden. Also kann der Compiler ohne probleme den nächsten Befehl laden. Aber wie ist das mit der Zählvariable a? Diese muss ja immer um 1 erhöht werden und das Ergebnis wird auch gleich wieder benötigt (m1[a]).
Welche grundsätzlichen Möglichkeiten habe ich zur Verfügung in dieser Hinsicht besseren Code zu schreiben?

Hallo Forum!
Ich habe folgendes herausgefunden:

// Algorithmus 1
for(int i = 0; i < N; i++) {
a = *p;
p += N;
}

// Algorithmus 2
for(int i = 0; i < N; i++) {
a = *p;
p += B;
}

Es gilt, dass B deutlich kleiner als N ist.
Nun habe ich beobachtet, dass Algorithmus 2 schneller läuft als Algorithmus 1. Nun brauche ich noch eine "saubere" Erklärung dafür.
Mein Ansatz wäre, dass der Pointer im Algorithmus 1 ja immer einen größeren Weg zurücklegen muss um zur nächsten Speicherzelle zu kommen.
Wie könnte man das etwas "hardwarespezifischer" erklären?

Danke für die hilfreichen Antworten!
Die Folien werde ich mir alle mal anschauen. Ich wollte ursprünglich den Algorithmus schneller machen, aber das hat sich als schwierig erwiesen. Es handelt sich um einen Gaussalgorithmus im der Gruppe GF2. Urpsprünglich wollte ich die Komplexität senken mit einer Methode von Strassen. Sie basiert darauf, dass man mehr Additionen und weniger Multiplikationen benötigt. Allerdings nützt das in der Gruppe GF2 recht wenig. Denn XOR und AND Operationen nehmen sich ja nicht viel und dementsprechend würde das keine Beschleunigung bringen...

Danke, diese Verbildlichung ist echt genial!!!
Jetzt muss ich nur noch herausfinden was die CPU genau mit 64 Bit macht(um herauszufinden warum dies schneller ist als UINT8). Kann man dabei von irgendeiner konstanten Zeit ausgehen die benötigt wird um eine 64-Bit-Schaufel so vorzubereiten, dass daraus zwei 32-Bit schaufeln werden? Und wenn ja, wie macht das die CPU im Detail?

Ich habe da noch eine kleine Frage. Ich bin gerade dabei die Operationen in dem Algorithmus auszuzählen. So langsam verstehe ich auch, was eine "größere Schaufel" rechnerisch bedeutet. Jedenfalls habe ich XOR, AND, OR und SHIFT als Bitoperationen. Dann gibt es Multiplikationen, Divisionen und Additionen. Dabei weiß ich nicht wie ich Vergleiche zählen soll (also z.b. A == B oder A > b)? Also wie lange dauern Vergleiche und fallen diese überhaupt ins Gewicht? Und gilt für Wertzuweisungen das gleiche(z.b. A = B;)? Wie schnell verhalten sind Wertzuweisungen?
Ich nehme mal an Divisionen dauern am längsten. Danach kommen Multiplikationen und schließlich Additionen. Die Bitoperationen XOR, AND, OR sind wohl etwa gleichlang und relativ fix. SHIFT soll angeblich am schnellsten sein.
Ich habe mir mal ein Experiment ausgedacht, bei dem ich die Operationen etwa vergleichen könnte.
Z.B. messe ich die Zeit für
for(int i = 0; i < grosseZahl; i++)
a = OPERATION b;

Dann dividiere ich durch "grosseZahl" und erhalte etwa die Zeit für eine Operationen. Damit ließen sich doch die Operationen fair vergleichen, oder?

Hallo Forum!
Ich habe einen Algorithmus der verschiedene Bitoperationen (shift, XOR, AND) gebraucht. Es muss eine Bitmatrix bearbeitet werden. Dazu werden die einzelnen Bits in Blöcke gepackt. Ich habe verschiedene Blockgrößen getestet (UINT8, 16, 32, 64). Es ergab sich folgende Reihenfolge was die Schnelligkeit des Algorithmus betrifft:

UINT32 - am schnellsten
UINT16
UINT64
UINT8 - am langsamsten

Ich habe einen 32Bit Prozessor. Damit kann ich mir noch erklären weshalb der 32 Bit-Algorithmus am schnellsten arbeitet. Die Blöcke werden "so wie sie sind" vom Prozessor bearbeitet. Aber wie kann ich mir den Rest der Reihenfolge erklären? Was würde der Prozessor machen, wenn er z.B. mit 16-Bit-Speicherzellen (bzw. variablen) arbeiten muss?
Beim UINT64 könnte ich mir noch vorstellen, dass der Prozessor den Block ersteinmal in zwei Hälften teilt und das kostet dementsprechend Zeit.

Ich bin noch Schüler und habe leider noch keine Detailkenntnisse was solche spezifischen Sachen angeht. Vielleicht gibt es ja welche unter euch, die sich da auskennen?