Отрицательное ускорение при многопоточности моей программы

Question

На моем ноутбуке с двухъядерным процессором Intel Pentium T2370 (Acer Extensa) я провел простой тест многопоточности. Я использую Linux. Код вставлен ниже. Хотя я ожидал ускорения в 2-3 раза, я был удивлен, увидев замедление в 2 раза. Я пробовал то же самое с уровнями оптимизации gcc -O0 ... -O3, но каждый раз я получил тот же результат. Я использую pthreads. Я также попробовал то же самое только с двумя потоками (вместо 3 потоков в коде), но производительность была схожей.

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

ПРИМЕЧАНИЕ. Этот код содержит много ошибок (в действительности он не имеет особого смысла, поскольку выходные данные последовательной и параллельной версий будут отличаться). Намерение было просто «получить» сравнение ускорения для того же количества инструкций.

#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>

class Thread{
    private:
            pthread_t thread;
            static void *thread_func(void *d){((Thread *)d)->run();}
    public:
            Thread(){}
            virtual ~Thread(){}

            virtual void run(){}
            int start(){return pthread_create(&thread, NULL, Thread::thread_func, (void*)this);}
            int wait(){return pthread_join(thread, NULL);}
};


#include <iostream>

const int ARR_SIZE = 100000000;
const int N = 20;
int arr[ARR_SIZE];

int main(void)
{

    class Thread_a:public Thread{
            public:
                    Thread_a(int* a): arr_(a) {}
                    void run()
                    {
                            for(int n = 0; n<N; n++)
                            for(int i=0; i<ARR_SIZE/3; i++){ arr_[i] += arr_[i-1];}
                    }
            private:
                    int* arr_;
    };
    class Thread_b:public Thread{
            public:
                    Thread_b(int* a): arr_(a) {}
                    void run()
                    {
                            for(int n = 0; n<N; n++)
                            for(int i=ARR_SIZE/3; i<2*ARR_SIZE/3; i++){ arr_[i] += arr_[i-1];}
                    }
            private:
                    int* arr_;
    };

    class Thread_c:public Thread{
            public:
                    Thread_c(int* a): arr_(a) {}
                    void run()
                    {
                            for(int n = 0; n<N; n++)
                            for(int i=2*ARR_SIZE/3; i<ARR_SIZE; i++){ arr_[i] += arr_[i-1];}
                    }
            private:
                    int* arr_;
    };

    {
            Thread *a=new Thread_a(arr);
            Thread *b=new Thread_b(arr);
            Thread *c=new Thread_c(arr);

            clock_t start = clock();

            if (a->start() != 0) {
                    return 1;
            }

            if (b->start() != 0) {
                    return 1;
            }
            if (c->start() != 0) {
                    return 1;
            }

            if (a->wait() != 0) {
                    return 1;
            }

            if (b->wait() != 0) {
                    return 1;
            }

            if (c->wait() != 0) {
                    return 1;
            }

            clock_t end = clock();
            double duration = (double)(end - start) / CLOCKS_PER_SEC;

            std::cout << duration << "seconds\n";
            delete a;
            delete b;

    }
    {
            clock_t start = clock();
            for(int n = 0; n<N; n++)
            for(int i=0; i<ARR_SIZE; i++){ arr[i] += arr[i-1];}
            clock_t end = clock();
            double duration = (double)(end - start) / CLOCKS_PER_SEC;

            std::cout << "serial: " << duration << "seconds\n";
    }

    return 0;
  }

---

См. Также: Что может замедлить работу программы при использовании большего количества потоков?

Answer 1

Время, которое вы сообщаете, измеряется с помощью функции часов:

Функция clock() возвращает приблизительное время процессора, используемое программой.

$ time bin/amit_kumar_threads.cpp
6.62seconds
serial: 2.7seconds

real    0m5.247s
user    0m9.025s
sys 0m0.304s

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

Когда вы используете несколько потоков, работа может выполняться более чем одним процессором, но объем работы одинаков, и, кроме того, могут быть некоторые издержки, такие как конфликт за ограниченные ресурсы. clock() измеряет общее время процессора, которое будет работать + любые конкурентные издержки. Таким образом, оно никогда не должно быть меньше времени процессора для выполнения работы в одном потоке.

Немного трудно определить из вопроса, знали ли вы это, и были удивлены, что значение, возвращаемое clock(), было вдвое больше, чем для одного потока, а не немного больше, или вы ожидали, что оно будет меньше.

Использование clock_gettime() вместо этого (вам понадобится библиотека реального времени librt, g++ -lrt и т. Д.) Дает:

$ time bin/amit_kumar_threads.cpp
2.524 seconds
serial: 2.761 seconds

real    0m5.326s
user    0m9.057s
sys 0m0.344s

, который по-прежнему меньше ускорения, чем можно было бы надеяться, но, по крайней мере, числа имеют некоторый смысл.

100000000 * 20 / 2.5s = 800 Гц, частота шины 1600 МГц, поэтому я подозреваю, что при чтении и записи для каждой итерации (при условии некоторого кэширования) пропускная способность памяти ограничена, как предполагает tstenner, и * Значение 1028 * показывает, что большую часть времени некоторые ваши процессоры ждут данных. (кто-нибудь знает, включает ли clock() время такие киоски?)

Answer 2

Единственное, что делает ваш поток, это добавляет некоторые элементы, поэтому ваше приложение должно быть привязано к IO. Когда вы добавляете дополнительный поток, у вас есть 2 ЦП, разделяющих шину памяти, поэтому он не будет работать быстрее, вместо этого у вас будут пропадать кеш и т. Д.

Answer 3

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

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

Answer 4

Также см. статью травы о том, как многопроцессорные и кэш-строки взаимодействуют в многопоточном коде, особенно в разделе «Весь обмен плох - даже для« неразделенных »объектов ...»

Answer 5

Не связано с вашими проблемами с потоками, но в вашем коде есть ошибка границ. У вас есть:

for(int i=0; i<ARR_SIZE; i++){ arr[i] += arr[i-1];}

Когда i равен нулю, вы будете делать

arr[0] += arr[-1];

Answer 6

Цтеннер понял это правильно.

Это, в основном, эталон алгоритма вашей операционной системы "выделить и отобразить новую страницу". Это распределение массива выделяет 800 МБ виртуальной памяти; ОС на самом деле не будет выделять реальную физическую память, пока она не понадобится. «Выделение и отображение новой страницы» обычно защищено мьютексом, поэтому больше ядер не поможет.

Ваш эталонный тест также оказывает нагрузку на шину памяти (минимум 800 МБ передано; в ОС, где объем памяти равен нулю непосредственно перед тем, как вы отдаете ее, в худшем случае это 800 МБ * 7 передач). Добавление большего количества ядер на самом деле не поможет, если узким местом является шина памяти.

У вас есть 3 потока, которые растоптаны по всей памяти. Строки кэша читаются и записываются разными потоками, поэтому будет происходить пинг-понг между кэшами L1 на двух ядрах процессора. (Строка кэша, в которую следует записать, может находиться только в одном кэше L1, и это должна быть кэш L1, который присоединен к коду ЦП, который выполняет запись). Это не очень эффективно. Ядра процессора, вероятно, проводят большую часть своего времени в ожидании передачи строки кэша, поэтому с потоками это происходит медленнее, чем при однопоточности.

Кстати, код также содержит ошибки, потому что один и тот же массив читается и записывается с разных процессоров без блокировки. Правильная блокировка повлияет на производительность.

Answer 7

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

Answer 8

Потоки перенесут вас в обещанную страну повышения скорости (TM), когда у вас будет правильная векторная реализация. Это означает, что вам нужно иметь:

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

Трудно придумать первое. Вам необходимо иметь избыточность и следить за тем, чтобы это не сказывалось на вашей производительности, правильном объединении данных для обработки следующей партии данных и т. Д.

Но тогда это только теоретическая точка зрения.

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