Tag zusammen,
ich hoffe, dass es hier im Forum jedmanden gibt der sich mit CUDA auskennt und der mir weiter helfen kann.
Hintergrund meines Problems:
Ich schreibe an einem CUDA-Programm, das mit Hilfe eines evolutionären Algorithmus, Lösungen für ein TSP (Traveling Salesman Problem) suchen soll. Innerhalb dieses Algorithmus sollen die bereits erzeugten Lösungen mutiert werden, indem zufällige Werte aus der Lösung gewählt werden und dann rotiert werden.
Beispiel:
Ausgangssituation:
1 2 3 4 5 6 7 8 9 (Die Unterstrichenen Werte sollen die ausgewählten sein)
Situation nach den Rotieren:
1 2 3 5 7 6 4 8 9
Umsetzung in CUDA:
Um diese Rotation auszuführen möchte ich pro Wert einen Thread laufen lassen, der bestimmt ob der Wert an der Rotation beteiligt, ist und einen der nötigen Kopiervorgänge durchführt.
Als Dimensionen der Böcke haben ich x=8 ; y=1 ; z=1 gewählt
Als Dimension des Grids x=(anzahl_der_werte+7)/8 ; y=anzahl_der_datensätze
Die Daten liegen linear im Speicher (mehere Datensätze liegen direck hintereinander), und jeder Thread kann auf alle Bereiche der Daten zugreifen.
Jeder Thread soll nun aus seinen Indizes und den Indizes seines Block berechnen für welchen Wert er zuständig ist. Anschließend erzeugt er eine "Zufallszahl". Liegt diese Zahl unter eine bestimmten Grenze kopiert er den Wert für den er aktuelle verantwortlich ist in einem anderen Speicherbereich, der genauso aufgebaut ist wie der aus dem er den Wert ausliest. Anschließend soll jeder Thread mit einer Schleife über die umkopierten Werte der anderen Threads laufen und den ersten Wert der nicht -1 ist umkopieren (-1 verwende ich um anzuzeigen das der Wert eines Threads nicht kopiert werden soll).
Problem:
Für die meisten Threads funktioniert dieses Vorgehen. Allerdings nicht für alle.
Um das Kopieren zu testen habe ich 100 Datensätze mit jeweils 52 Werten erzeugt. Alle Werte eines Datensatz sollen an der Rotation beteiligt werden.
Somit sollten die Datensätze bei einer Testausgabe wie folgt aussehen:
1 2 3 .... 50 51 0
Einzelne Positionen erhalten jedoch den Wert 0.
Die falschen Werte haben innerhalb eines Datensatz jeweils einen Index nach dem Muster (X*8)-1
Der erste falsche Wert tritt im 7 Datensatz an der Position 47 auf. Von da an enthält jeder 7te Datensatz einen Fehler wobei der Index immer um 8 kleiner wird. Nachdem der Index bis auf 7 herunter ist sind die nächsten 12 Datensätze fehlerfrei und dann beginnt der Zyklus neu.
Programmcode:
Berechnung der Dimensionen:
Rotation:
So ich hoffe, ich konnte das Problem verständlich beschreiben und jemand kann mir helfen.
Gruß Nimmer
ich hoffe, dass es hier im Forum jedmanden gibt der sich mit CUDA auskennt und der mir weiter helfen kann.
Hintergrund meines Problems:
Ich schreibe an einem CUDA-Programm, das mit Hilfe eines evolutionären Algorithmus, Lösungen für ein TSP (Traveling Salesman Problem) suchen soll. Innerhalb dieses Algorithmus sollen die bereits erzeugten Lösungen mutiert werden, indem zufällige Werte aus der Lösung gewählt werden und dann rotiert werden.
Beispiel:
Ausgangssituation:
1 2 3 4 5 6 7 8 9 (Die Unterstrichenen Werte sollen die ausgewählten sein)
Situation nach den Rotieren:
1 2 3 5 7 6 4 8 9
Umsetzung in CUDA:
Um diese Rotation auszuführen möchte ich pro Wert einen Thread laufen lassen, der bestimmt ob der Wert an der Rotation beteiligt, ist und einen der nötigen Kopiervorgänge durchführt.
Als Dimensionen der Böcke haben ich x=8 ; y=1 ; z=1 gewählt
Als Dimension des Grids x=(anzahl_der_werte+7)/8 ; y=anzahl_der_datensätze
Die Daten liegen linear im Speicher (mehere Datensätze liegen direck hintereinander), und jeder Thread kann auf alle Bereiche der Daten zugreifen.
Jeder Thread soll nun aus seinen Indizes und den Indizes seines Block berechnen für welchen Wert er zuständig ist. Anschließend erzeugt er eine "Zufallszahl". Liegt diese Zahl unter eine bestimmten Grenze kopiert er den Wert für den er aktuelle verantwortlich ist in einem anderen Speicherbereich, der genauso aufgebaut ist wie der aus dem er den Wert ausliest. Anschließend soll jeder Thread mit einer Schleife über die umkopierten Werte der anderen Threads laufen und den ersten Wert der nicht -1 ist umkopieren (-1 verwende ich um anzuzeigen das der Wert eines Threads nicht kopiert werden soll).
Problem:
Für die meisten Threads funktioniert dieses Vorgehen. Allerdings nicht für alle.
Um das Kopieren zu testen habe ich 100 Datensätze mit jeweils 52 Werten erzeugt. Alle Werte eines Datensatz sollen an der Rotation beteiligt werden.
Somit sollten die Datensätze bei einer Testausgabe wie folgt aussehen:
1 2 3 .... 50 51 0
Einzelne Positionen erhalten jedoch den Wert 0.
Die falschen Werte haben innerhalb eines Datensatz jeweils einen Index nach dem Muster (X*8)-1
Der erste falsche Wert tritt im 7 Datensatz an der Position 47 auf. Von da an enthält jeder 7te Datensatz einen Fehler wobei der Index immer um 8 kleiner wird. Nachdem der Index bis auf 7 herunter ist sind die nächsten 12 Datensätze fehlerfrei und dann beginnt der Zyklus neu.
Programmcode:
Berechnung der Dimensionen:
Code:
dim3 dimBlock( 8, 1, 1);
dim3 dimGrid( (staedteAnzahl+7)/8, populationsUmfang, 1); //staedteAnzahl ist die Anzahl der WerteRotation:
Code:
int tmp = -1;
//Berechnung der Posoition im Speicher
int individuum = blockIdx.y;
int genotypAnfang = individuum * staedteAnzahl;
int genotypKoord = blockDim.x * blockIdx.x + threadIdx.x;
if(genotypKoord < staedteAnzahl){ //staedteAnzahl ist die Anzahl der Werte
/* Berechnen der Zufallszahl random_inter */
//random_inter liegt momentan im Interval [0, 999] wahrscheinlichkeit hat den Wert 1000
if(random_inter < wahrscheinlichkeit){
flags[genotypAnfang + genotypKoord] = genotypen[genotypAnfang + genotypKoord];
}else{
flags[genotypAnfang + genotypKoord] = -1;
}
}
__syncthreads();
if(genotypKoord < staedteAnzahl){
for( int i=1 ; i<=staedteAnzahl ; i++){
tmp = flags[ genotypAnfang + ( ( genotypKoord + i ) % staedteAnzahl ) ];
if(tmp != -1){
genotypen[genotypAnfang + genotypKoord] = tmp;
break;
}
}
}
__syncthreads();So ich hoffe, ich konnte das Problem verständlich beschreiben und jemand kann mir helfen.
Gruß Nimmer
Zuletzt bearbeitet:
