Проблема времени выполнения многопоточности C++

Question

Я изучаю многопоточность C++ и задаю вопрос об этом.

Вот что я понимаю о многопотоках. Одной из причин, по которым мы используем многопоточность, является сокращение времени выполнения, правильно? Например, я думаю, что если мы используем два потока, мы можем ожидать половину времени выполнения. Итак, я попытался выполнить код, чтобы доказать это. Вот код.

#include <vector> 
#include <iostream> 
#include <thread> 
#include <future> 

using namespace std; 
#define iterationNumber 1000000 

void myFunction(const int index, const int numberInThread, promise<unsigned long>&& p, const vector<int>& numberList) { 
    clock_t begin,end; 
    int firstIndex = index * numberInThread; 
    int lastIndex = firstIndex + numberInThread; 
    vector<int>::const_iterator first = numberList.cbegin() + firstIndex; 
    vector<int>::const_iterator last = numberList.cbegin() + lastIndex; 

    vector<int> numbers(first,last); 

    unsigned long result = 0; 

    begin = clock(); 
    for(int i = 0 ; i < numbers.size(); i++) { 
     result += numbers.at(i); 
    } 
    end = clock(); 
    cout << "thread" << index << " took " << ((float)(end-begin))/CLOCKS_PER_SEC << endl; 

    p.set_value(result); 

} 


int main(void) 
{ 
    vector<int> numberList; 
    vector<thread> t; 
    vector<future<unsigned long>> futures; 
    vector<unsigned long> result; 
    const int NumberOfThreads = thread::hardware_concurrency() ?: 2; 
    int numberInThread = iterationNumber/NumberOfThreads; 

    clock_t begin,end; 


    for(int i = 0 ; i < iterationNumber ; i++) { 
     int randomN = rand() % 10000 + 1; 
     numberList.push_back(randomN); 
    } 

    for(int j = 0 ; j < NumberOfThreads; j++){ 
     promise<unsigned long> promises; 
     futures.push_back(promises.get_future()); 
     t.push_back(thread(myFunction, j, numberInThread, std::move(promises), numberList)); 
    } 

    for_each(t.begin(), t.end(), std::mem_fn(&std::thread::join)); 

    for (int i = 0; i < futures.size(); i++) { 
     result.push_back(futures.at(i).get()); 
    } 

    unsigned long RRR = 0; 

    begin = clock(); 
    for(int i = 0 ; i < numberList.size(); i++) { 
     RRR += numberList.at(i); 
    } 
    end = clock(); 
    cout << "not by thread took " << ((float)(end-begin))/CLOCKS_PER_SEC << endl; 

} 

Поскольку аппаратное обеспечение параллельности моего ноутбука 4, он будет создавать 4 темы, и каждый занимает четверть Numberlist и суммировать числа.

Однако результат был другим, чем я ожидал.

thread0 took 0.007232 
thread1 took 0.007402 
thread2 took 0.010035 
thread3 took 0.011759 
not by thread took 0.009654 

Почему? Почему это заняло больше времени, чем серийная версия (не по потоку).

Answer 1

Например, я думаю, что если мы используем два потока, мы можем ожидать половину времени выполнения .

Вы бы так подумали, но, к сожалению, это часто бывает не на практике. Идеальный сценарий «N ядер означает 1/Nth время исполнения» возникает только тогда, когда N ядер могут выполняться полностью параллельно, без каких-либо действий ядра, влияющих на производительность других ядер.

Но то, что ваши потоки делают, просто суммирует различные подразделы массива ... конечно, что может быть полезно для выполнения параллельно? Ответ заключается в том, что в принципе он может, но на современном процессоре простое добавление настолько ослепительно быстро, что оно не является фактором в том, сколько времени требуется для завершения цикла. Что действительно делает ограничение скорости выполнения цикла - это доступ к ОЗУ. По сравнению со скоростью процессора доступ к ОЗУ очень медленный, и на большинстве настольных компьютеров каждый процессор имеет только одно соединение с ОЗУ независимо от того, сколько ядер оно имеет. Это означает, что то, что вы действительно измеряете в своей программе, - это скорость, с которой большой массив целых чисел можно считывать из ОЗУ в CPU, и эта скорость примерно такая же - равная пропускной способности шины памяти процессора - независимо от того, является ли это одним ядром, выполняющим чтение в памяти, или четыре.

Чтобы продемонстрировать, какой объем доступа к ОЗУ является фактором, ниже приведена модифицированная/упрощенная версия вашей тестовой программы. В этой версии программы я удалил большие векторы, и вместо этого вычисление представляет собой всего лишь последовательность вызовов (относительно дорогостоящей) функции sin(). Обратите внимание, что в этой версии цикл имеет доступ только к нескольким ячейкам памяти, а не к тысячам, и, следовательно, ядру, на котором выполняется цикл вычисления, не придется периодически ждать, пока больше данных будет скопировано из ОЗУ в его локальный кеш:

#include <vector> 
#include <iostream> 
#include <thread> 
#include <chrono> 
#include <math.h> 

using namespace std; 

static int iterationNumber = 1000000; 

unsigned long long threadElapsedTimeMicros[10]; 
unsigned long threadResults[10]; 

void myFunction(const int index, const int numberInThread) 
{ 
    unsigned long result = 666; 

    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); 
    for(int i=0; i<numberInThread; i++) result += 100*sin(result); 
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); 

    threadResults[index] = result; 
    threadElapsedTimeMicros[index] = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count(); 

    // We'll print out the value of threadElapsedTimeMicros[index] later on, 
    // after all the threads have been join()'d. 
    // If we printed it out now it might affect the timing of the other threads 
    // that may still be executing 
} 

int main(void) 
{ 
    vector<thread> t; 
    const int NumberOfThreads = thread::hardware_concurrency(); 
    const int numberInThread = iterationNumber/NumberOfThreads; 

    // Multithreaded approach 
    std::chrono::steady_clock::time_point allBegin = std::chrono::steady_clock::now(); 
    for(int j = 0 ; j < NumberOfThreads; j++) t.push_back(thread(myFunction, j, numberInThread)); 
    for(int j = 0 ; j < NumberOfThreads; j++) t[j].join(); 
    std::chrono::steady_clock::time_point allEnd = std::chrono::steady_clock::now(); 

    for(int j = 0 ; j < NumberOfThreads; j++) cout << " The computations in thread #" << j << ": result=" << threadResults[j] << ", took " << threadElapsedTimeMicros[j] << " microseconds" << std::endl; 
    cout << " Total time spent doing multithreaded computations was " << std::chrono::duration_cast<std::chrono::microseconds>(allEnd - allBegin).count() << " microseconds in total" << std::endl; 

    // And now, the single-threaded approach, for comparison 
    unsigned long result = 666; 
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); 
    for(int i = 0 ; i < iterationNumber; i++) result += 100*sin(result); 
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); 

    cout << "result=" << result << ", single-threaded computation took " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " microseconds" << std::endl; 
    return 0; 
} 

Когда я бегу выше программы на моем двухъядерном Mac mini (i7 с технологией HyperThreading), вот результаты я получаю:

Jeremys-Mac-mini:~ lcsuser1$ g++ -std=c++11 -O3 ./temp.cpp 
Jeremys-Mac-mini:~ lcsuser1$ ./a.out 
The computations in thread #0: result=1062, took 11718 microseconds 
The computations in thread #1: result=1062, took 11481 microseconds 
The computations in thread #2: result=1062, took 11525 microseconds 
The computations in thread #3: result=1062, took 11230 microseconds 
Total time spent doing multithreaded computations was 16492 microseconds in total 
result=1181, single-threaded computation took 49846 microseconds 

Так что в этом случае результаты больше похожи на то, что вы ожидаете - поскольку доступ к памяти не был узким местом, каждое ядро ​​могло работать на полной скорости и завершить свою 25% -ую долю общих вычислений примерно в 25% o в то время, когда для завершения 100% вычислений потребовался один поток ... и поскольку четыре ядра работали по-настоящему параллельно, общее время, затрачиваемое на вычисления, составляло около 33% времени, (в идеале это будет 25%, но есть некоторые накладные расходы, связанные с запуском и выключением потоков и т. д.).

Answer 2

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

Многопоточность - это своего рода сложная концепция, но вы можете легко найти связанные с ней материалы в Интернете. Сначала вы должны прочитать один из них. Но я попытаюсь дать простое объяснение с примером.

Независимо от того, сколько у вас ЦП (или ядер), , общая вычислительная мощность ЦП будет всегда одинаковой, независимо от того, используете ли вы многопоточность или нет, верно? Затем, откуда возникает разница в производительности?

Когда программа запускается на устройстве (компьютере), в ней используются не только процессор, но и другие системные ресурсы, такие как сети, оперативная память, жесткие диски и т. Д. Если поток программы будет сериализован, будет определенная точка когда процессор находится в режиме ожидания, ожидая выполнения других системных ресурсов. Но в случае, если программа работает с несколькими потоками (несколько потоков), если поток переходит в режим ожидания (ожидание некоторых задач, выполняемых другими системными ресурсами), другие потоки могут использовать CPU. Таким образом, вы можете свести к минимуму время простоя CPU и повысить производительность. Это один из самых простых примеров многопоточности.

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

FYI, parallel processing не то же самое, что и многопоточность.

Answer 3

Это очень хорошо, чтобы указать на проблемы с маками.

При условии, что вы используете o.s. который может планировать потоки в полезной манере, вам нужно подумать, если проблема в основном является продуктом 1 проблемы много раз. Примером является умножение матрицы. Когда вы умножаете 2 матрицы, есть некоторые ее части, которые не зависят от других. Матрица 3х3, умноженная на другую 3х3, требует 9 точечных произведений, которые могут вычисляться независимо от других, которые сами требуют 3 умножения и 2 дополнения, но здесь необходимо сначала произвести умножение. Поэтому мы видим, хотим ли мы использовать многопоточный процессор для этой задачи, мы могли бы использовать 9 ядер или потоков и учитывая, что они получают равное время вычисления или имеют одинаковый уровень приоритета (который настраивается на окнах), вы сократили время, чтобы умножить матрицы 3x3 на 9.Это связано с тем, что мы по существу делаем что-то 9 раз, что может быть сделано в то же время 9 людьми.

сейчас для каждого из 9 нитей мы могли бы иметь 3 ядра, которые выполняют умножения на 3x9 = 24 ядра вместе. Сокращение времени на t/24. Но у нас есть 18 дополнений, и здесь мы не можем получить прибыль от большего количества ядер. Одно дополнение должно быть подключено к другому. И проблема занимает время t с одним ядром или временем t/24 в идеальном случае с 24 ядрами, работающими вместе. Теперь вы можете понять, почему проблемы часто искажаются, если они являются «линейными», потому что их можно сделать параллельно довольно хорошо, например, для графики (некоторые вещи, такие как отбраковка задней поверхности, являются проблемами сортировки и по своей сути не линейными, поэтому параллельная обработка уменьшает повышение производительности) ,

Затем добавляются накладные расходы на начальные темы и их назначение на o.s. и процессор. Надеюсь это поможет.

Answer 4

Это объяснение для новичка.

Это не технически точно, но ИМХО не так далеко от него, что любой человек получает урон от его чтения.

Он обеспечивает вход в понимание условий параллельной обработки.

Темы, задачи и процессы

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

Наличие нескольких ядер означает, что каждый из них работает процесс может выполняться на любом незанятом ядре. Итак, в основном одна программа работает на одном ядре, другая программа работает на втором ядре, а фоновое обслуживание делает что-то для вас, работает на третьем (и т. Д. И т. Д.).

Нити - это что-то другое. Например, все процессы будут выполняться в основном потоке. Операционная система реализует планировщик, который должен выделять время процессора для программ. В принципе он скажет:

• Программа A, получите 0.01 секунды, чем пауза!
• Программа B, получить 0,01 секунды, затем приостановить!
• Программа A, получить 0,01 секунды, затем приостановить!
• Программа B, получить 0,01 секунды, затем приостановить!

вы получите идею ..

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

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

Доступ к другому кешу ядра не так быстр, (даже если это возможно без прохождения через ОЗУ), поэтому в общем планировщике не будет разбиваться процесс на несколько ядер. В результате все потоки, относящиеся к процессу, работают на одном ядре.

| Core 1    | Core 2    | Core 3    | 
| Process A, Thread 1 | Process C, Thread 1 | Process F, Thread 1| 
| Process A, Thread 2 | Process D, Thread 1 | Process F, Thread 2| 
| Process B, Thread 1 | Process E, Thread 1 | Process F, Thread 3| 
| Process A, Thread 1 | Process C, Thread 1 | Process F, Thread 1| 
| Process A, Thread 2 | Process D, Thread 1 | Process F, Thread 2|  
| Process B, Thread 1 | Process E, Thread 1 | Process F, Thread 3| 

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

Имеет смысл порождать потоки в процессе, если у вас есть приложение, которое должно отвечать на то, что не может контролировать время. I.E. пользователи нажимают кнопку отмены или пытаются переместить окно, в то время как приложение выполняет расчеты, которые занимают много времени.

Отзывчивость пользовательского интерфейса требует, чтобы приложение проводило время на чтение и обработку того, что пользователь пытается сделать. Это может быть достигнуто в основном цикле, если программа выполняет части вычисления на каждой итерации. Тем не менее, это сложно сделать быстро, поэтому вместо кода вычисления выйдите из центра вычислений, чтобы проверить пользовательский интерфейс и обновить интерфейс, а затем продолжить. Вы запускаете код вычисления в другом потоке. Затем планировщик следит за тем, чтобы поток пользовательского интерфейса и поток вычислений получали процессорное время, поэтому пользовательский интерфейс реагирует на ввод пользователя, а расчет продолжается. И ваш код остается довольно простым.

Но я хочу, чтобы запустить мои расчеты другого ядра, чтобы набрать скорость

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

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

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

Для расчетов, которые занимают всего несколько секунд, файловая система работает медленно, и ее ожидание почти удалит полученную производительность при использовании процессов вместо использования потоков. Поэтому в реальной жизни используется другое более эффективное использование памяти. Например, создание области общей памяти в ОЗУ.

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

Задачи Ну «задачи» неоднозначны.

В целом это означает «Процесс или поток, который решает задачу».

Однако, на некоторых языках, таких как C#, это то, что реализует нить , например, что планировщик может рассматривать как процесс. Другие языки, которые предоставляют подобную функцию, обычно дублируют это либо задачи, либо рабочие.

Таким образом, с работниками/задачами он появляется программисту, как если бы это был просто поток, который можно легко обменивать память через ссылки и управлять, как и любой другой поток, путем вызова методов в потоке.

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

Это часто упоминается как «Гибридная резьба» или просто «параллельные нити»