Ein klassisches Map-Reduce-Problem mit OpenCL lösen?

Question

Ich versuche, ein klassisches Map-Reduce-Problem (das gut mit MPI parallel mit MPI) mit OpenCL, nämlich der AMD-Implementierung, parallel zu sein. Aber das Ergebnis stört mich.

Lassen Sie mich zuerst über das Problem informieren. Es gibt zwei Datenart, die in das System fließen: den Feature -Satz (jeweils 30 Parameter) und die Probensätze (9000+ Dimensionen für jeweils). Es ist ein klassisches Map-Reduce-Problem in dem Sinne, dass ich die Punktzahl jeder Funktion auf jeder Probe (Karte) berechnen muss. Fassen Sie dann die Gesamtpunktzahl für jedes Merkmal zusammen (reduzieren). Es gibt rund 10.000 Features und 30K -Proben.

Ich habe verschiedene Möglichkeiten versucht, das Problem zu lösen. Zuerst habe ich versucht, das Problem durch Funktionen zu zerlegen. Das Problem ist, dass die Score -Berechnung aus dem Zufallsspeicherzugriff besteht (wählen Sie einige der über 9000 Dimensionen und plus/Subtraktionsberechnungen). Da ich den Speicherzugriff nicht verschleiern kann, kostet dies. Dann versuchte ich, das Problem durch Proben zu zerlegen. Das Problem ist, dass alle Threads um nur wenige Punktzahlvariablen konkurrieren, um die Gesamtpunktzahl zusammenzufassen. Es überschreibt die Punktzahl, die sich als falsch herausstellt. (Ich kann nicht zuerst die individuelle Punktzahl durchführen und später zusammenfassen, da es 10k * 30k * 4 Bytes benötigt).

Die erste Methode, die ich ausprobiert habe, gibt mir die gleiche Leistung auf i7 860 CPU mit 8 Threads. Ich denke jedoch nicht, dass das Problem unlösbar ist: Es ist dem Problem der Strahlenverfolgung bemerkenswert ähnlich (für die Sie Berechnung durchführen, dass Millionen von Strahlen gegen Millionen von Dreiecken). Irgendwelche Ideen?

Außerdem poste ich einen Teil des Code, den ich habe:

zersetzen durch Feature (funktioniert, aber langsam):

__kernel void __ccv_cl_pos_error_rate(__global unsigned int* err_rate,
__constant int* feature, __constant int* data, int num, __constant
unsigned int* w, int s, int isiz0, int isiz01, int step0, int step1)
{
    int igrid = get_global_id(0);
    __constant int* of = feature + igrid * 30;
    unsigned int e = 0;
    int k, i;
    int step[] = { step0, step1 };
    for (k = 0; k < num; k++)
    {
        __constant int* kd = data + k * isiz01;
        int pmin = kd[of[0] * isiz0 + of[1] + of[2] * step[of[0]]];
        int nmax = kd[of[3] * isiz0 + of[4] + of[5] * step[of[3]]];
        for (i = 0; i < 5; i++)
        {
            if (of[i * 6] >= 0)
                pmin = min(pmin, kd[of[i * 6] * isiz0 + of[i * 6 + 1] + of[i * 6 + 2] * step[of[i * 6]]]);
            if (of[i * 6 + 3] >= 0)
                nmax = max(nmax, kd[of[i * 6 + 3] * isiz0 + of[i * 6 + 4] + of[i * 6 + 5] * step[of[i * 6 + 3]]]);
        }
        if (pmin <= nmax)
            e += w[s + k];
    }
    err_rate[igrid] += e;
}

zersetzen durch Probe, nicht funktionieren:

__kernel void __ccv_cl_pos_error_rate(__global unsigned int* err_rate,
__constant int* feature, __constant int* data, int num, __constant
unsigned int* w, int s, int isiz0, int isiz01, int step0, int step1,
__local int* shared)
{
    int igrid = get_global_id(0);
    int lsize = get_local_size(0);
    int lid = get_local_id(0);
    unsigned int e = 0;
    int k, i;
    int ws = w[s + igrid];
    int step[] = { step0, step1 };
    for (k = 0; k < isiz01; k += lsize)
        if (k + lid < isiz01)
            shared[k + lid] = data[igrid * isiz01 + k + lid];
    barrier(....);
    for (k = 0; k < num; k++)
    {
        __constant int* of = feature + k * 30;
        int pmin = shared[of[0] * isiz0 + of[1] + of[2] * step[of[0]]];
        int nmax = shared[of[3] * isiz0 + of[4] + of[5] * step[of[3]]];
        for (i = 0; i < 5; i++)
        {
            if (of[i * 6] >= 0)
                pmin = min(pmin, shared[of[i * 6] * isiz0 + of[i * 6 + 1] + of[i * 6 + 2] * step[of[i * 6]]]);
            if (of[i * 6 + 3] >= 0)
                nmax = max(nmax, shared[of[i * 6 + 3] * isiz0 + of[i * 6 + 4] + of[i * 6 + 5] * step[of[i * 6 + 3]]]);
        }
        if (pmin <= nmax)
            err_rate[k] += ws; // here is wrong.
    }
    barrier(....);
}

Answer 1

Andrew Cooke von HN hier. Von Ihrem ersten Versuch verstehe ich jetzt das Problem besser und sehe, dass die Auswahl der Probe von der Funktion abhängt, was Sie dort umbringt.

Ist die Auswahl der Stichprobe durch Feature vollständig zufällig oder können Sie Regelmäßigkeiten in dieser (Bestellfunktionen so, dass diejenigen, die dieselben Proben verwenden, zusammen verarbeitet werden)? Dies ist offensichtlich, also denke ich, dass es nicht möglich ist.

Leider verstehe ich Ihren zweiten Versuch nicht.