Как я могу распараллелить этот решающий код

Question

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

void ExecuteAll()
{
    for(long i = TotalCount(); i >= 1; i--)
    {
        long k    = linkOrder[i];
        long link = firstLink[k];
        if (link == 0)
            continue;

        double d = 0.;
        for(; link != 0; link = nextLink[link])
        {
            long kk  = getNode(link);
            d  += fak[link]*res[kk];
        }
        d += res[k];
        double d2 = d/fak2[k];
        res[k]   = d2;
        res2[k] += d2;
    }
}

Я переработал это для работы с несколькими потоками, реализовав такой класс:

class myDemoClass
{    
    bool volatile *isDone;
public:

    void ExecuteSlice() 
    {   
        for(long i = TotalCount() - mThreadIndex; i >= 1; i -= threadCount)
        {
            long k = linkOrder[i];
            Execute(k);
        }
    }

    void Execute(long k)
    {
        long link = firstLink[k];
        if (link == 0)
        {
            isDone[k] = true;
            return;
        }
        double d = 0.;
        for(; link != 0; link = nextLink[link])
        {
            long kk  = getNode(link);

            for(int x = 0; ! isDone[kk]; x++)
                {} // Wait until data is ready. Time too short for sleep or event

            d  += fak[link]*res[kk];
        }
        d += res[k];
        double d2 = d/fak2[k];
        res[k]   = d2;
        res2[k] += d2;

        isDone[k] = true;
    }
}

Я создаю экземпляр этого классадля каждого потока, где каждый поток работает со срезом всех значений для i.Я ввел новый массив bool volatile *isDone, так как я не должен использовать результаты необработанных узлов.Я попытался вставить сон или событие вместо цикла for(;...;){}, но оказалось, что для этого состояния ожидания слишком короткие.

Кажется, это работает нормально.Только 10% всех вызовов Execute () должны входить в цикл ожидания, поскольку график все больше и больше разворачивается из начальной точки, и результаты верны.

Но, что удивительно, ощутимого увеличения производительности (или потери) нет) на 8-ядерном компьютере XEON при использовании нового кода с 8 потоками.Я знаю, что этот код не является оптимальным с точки зрения аннулирования кэша, в основном, поскольку isDone и res пишутся и читаются из нескольких ядер.Но в большинстве случаев разыменованные индексы довольно далеко друг от друга.График содержит около 1.000.000 узлов и ссылок.

Как я могу улучшить параллелизм этого кода?

Answer 1

Вы не можете просто использовать volatile, чтобы сделать код потокобезопасным. Volatile помогает с однопоточными приложениями, которые отображают переменные на внешние устройства, обеспечивая постоянное повторное чтение значения, но для потоков этого недостаточно, поскольку не только операторы могут переупорядочивать операторы, но и процессоры могут переупорядочивать инструкции. Для этого вы должны использовать надлежащий многопоточный примитив, предоставляемый библиотекой или конкретной реализацией компилятора (например, блокированные функции в Win32 или Atomic Builtins в gcc). Точно так же не ясно, что любая из ваших других структур данных безопасна для многопоточной модификации.

Что касается производительности, трудно сказать, в чем проблема, потому что мы ничего не знаем о вашей структуре графа, а ваш код слишком абстрактен, чтобы много над этим работать. Тем не менее, вы, кажется, тратите много времени на перебирание ссылок, которые еще не обработаны. В идеале вы должны сделать это с другой стороны и начать с обработки ссылки, которая не имеет зависимостей, затем, когда это будет сделано, начать с ссылок, которые зависели от этой и т. Д., Т. Е. Ждать не нужно. Возможно, здесь поможет что-то вроде топологической сортировки.

Answer 2

Несколько мыслей, которые могут быть полезны:

• Чтобы убедиться, что ваш многопоточный код работает, я бы протестировал с помощью некоторого вычисления, которое, как известно, хорошо распараллеливается (в качестве примера сразу не приходит ничего). Затем вы можете протестировать одно- и многопоточные реализации и убедиться, что ваше общее многопоточное приложение работает должным образом.
• Вы уверены, что ваш алгоритм распараллеливается хорошо или даже вообще? Как упоминает Стив, вычисления с привязкой к ЦП лучше всего подходят для параллелизма, тогда как ваш код выглядит как смесь ЦП и ввода-вывода. В зависимости от того, что getNode() делает, вы можете быть привязаны к IO, что ограничит то, что вы можете получить, используя многопоточный алгоритм. Профилирование и тестирование кода помогут определить, где могут быть применены ваши лучшие результаты оптимизации.
• Не используйте volatile для многопоточной синхронизации, как другие упомянутые авторы. Это может действительно работать для вас сейчас, но нет никаких гарантий, что это не сломается в будущем. Рассмотрим наихудший сценарий, когда через несколько месяцев он будет слегка ломаться, что немного искажает все результаты вашего моделирования, но недостаточно, чтобы быть очевидным.
• Цикл for "wait" также является подозрительным и должен быть заменен для правильного многопоточного ожидания. Когда поток «ожидает» в этом цикле, он потребляет процессорное время, которое можно было бы лучше использовать, выполняя реальную работу в другом потоке. Если этот цикл ожидания используется только в 10% случаев, ваш выигрыш, если он есть, будет небольшим, но нет гарантии, что его использование всегда будет таким маленьким.

Answer 3

OpenMP - это стандарт de facto , хорошо поддерживаемый в современных компиляторах, для распараллеливания кода обработки массива в структурно идентичные задачи, которые вы просто хотите выполнить на нескольких ядрах, не беспокоясьслишком много об управлении потоками.Взгляните на это, это может помочь прояснить ваше мышление и даже решить проблему.

Это лучше всего использовать для задач с ограниченным использованием процессора - мне не ясно, так ли это для вас, так как вы ссылаетесьждать поступления данных?В этом случае многопоточность логики может не помочь так, как вы ожидаете или надеетесь.