Как распараллелить поиск ближайшего соседа с помощью OpenMP - PullRequest
Новая
       3

Как распараллелить поиск ближайшего соседа с помощью OpenMP

0 голосов
/ 31 января 2020

По сути, у меня есть коллекция std::vector<std::pair<std::vector<float>, unsigned int>>, которая содержит пары шаблонов std::vector<float> размера 512 (2048 bytes) и соответствующий им идентификатор unsigned int.

Я пишу функцию, в которой мне предоставляется шаблон, и мне нужно вернуть идентификатор наиболее похожего шаблона в коллекции. Я использую скалярное произведение для вычисления сходства.

Моя наивная реализация выглядит следующим образом: 

// Should return false if no match is found (ie. similarity is 0 for all templates in collection)
bool identify(const float* data, unsigned int length, unsigned int& label, float& similarity) {
    bool found = false;
    similarity = 0.f;

    for (size_t i = 0; i < collection.size(); ++i) {
        const float* candidateTemplate = collection[i].first.data();
        float consinSimilarity = getSimilarity(data, candidateTemplate, length); // computes cosin sim between two vectors, implementation depends on architecture. 

        if (consinSimilarity > similarity) {
            found = true;
            similarity = consinSimilarity;
            label = collection[i].second;
        }
    }

    return found;
}

Как я могу ускорить это с помощью распараллеливания. Моя коллекция может содержать потенциально миллионы шаблонов. Я читал, что вы можете добавить #pragma omp parallel for reduction, но я не совсем уверен, как его использовать (и если это даже лучший вариант).

Также обратите внимание: для моей реализации точечного продукта, если базовая архитектура поддерживает AVX и FMA, я использую это реализация. Повлияет ли это на производительность, когда мы распараллеливаемся, поскольку количество регистров SIMD ограничено?

1 Ответ

2 голосов
/ 03 февраля 2020

Поскольку у нас нет доступа к примеру, который на самом деле компилируется (что было бы неплохо), я на самом деле не пытался скомпилировать пример ниже. Тем не менее, некоторые незначительные опечатки (возможно) в стороне, общая идея должна быть ясной.

Задача состоит в том, чтобы найти наибольшее значение подобия и соответствующую метку, для этого мы действительно можем использовать reduction, но, поскольку нам нужно найти максимум одно значение и затем сохранить соответствующую метку, мы используйте пару для хранения обоих значений одновременно, чтобы реализовать это как reduction в OpenMP.

Я немного переписал ваш код, возможно, немного затруднил чтение с оригинальным именованием (temp) переменной. По сути, мы выполняем поиск параллельно, поэтому каждый поток находит оптимальное значение, затем мы просим OpenMP найти оптимальное решение между потоками (reduction), и все готово. 

//Reduce by finding the maximum and also storing the corresponding label, this is why we use a std::pair. 
void reduce_custom (std::pair<float, unsigned int>& output, std::pair<float, unsigned int>& input) {
    if (input.first > output.first) output = input;
}
//Declare an OpenMP reduction with our pair and our custom reduction function. 
#pragma omp declare reduction(custom_reduction : \
    std::pair<float, unsigned int>: \
    reduce_custom(omp_out, omp_in)) \
    initializer(omp_priv(omp_orig))

bool identify(const float* data, unsigned int length, unsigned int& label, float& similarity) {
    std::pair<float, unsigned int> temp(0.0, label); //Stores thread local similarity and corresponding best label. 

#pragma omp parallel for reduction(custom_reduction:temp)
    for (size_t i = 0; i < collection.size(); ++i) {
        const float* candidateTemplate = collection[i].first.data(); 
        float consinSimilarity = getSimilarity(data, candidateTemplate, length);

        if (consinSimilarity > temp.first) {
            temp.first = consinSimilarity;
            temp.second = collection[i].second;
        }
    }

    if (temp.first > 0.f) {
        similarity = temp.first;
        label = temp.second;
        return true;
    }

    return false;
}

Что касается вашей озабоченности по поводу ограниченного количества регистров SIMD, их количество зависит от используемого вами c ЦП. Насколько я понимаю, каждое ядро ​​имеет установленное количество доступных векторных регистров, так что, пока вы не использовали больше, чем было доступно, прежде чем все должно быть в порядке, к тому же AVX512, например, предоставляет 32 векторных регистра и 2 arithemti c единиц для векторных операций на ядро, поэтому нехватка вычислительных ресурсов не тривиальна, вы, скорее всего, пострадаете из-за плохой локализации памяти (особенно в вашем случае, когда векторы сохраняются повсеместно). Конечно, я могу ошибаться, если да, пожалуйста, не стесняйтесь поправлять меня в комментариях.

...