Почему использование более двух потоков потребляет больше времени?

Question

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

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

Я попробовал этот код, чтобы ускорить процесс градиента:

for (int n = 0; n<iter_outer; n++) 
     { 
      int chunk = 1 + ((row - 1)/num_threads); //ceiling 
      int start=0; 
      int end=0; 
      //Launch a group of threads 
      for (int tid = 0; tid < num_threads; ++tid) 
      { 
       start = tid * chunk; 
       end = start + chunk; 
       t[tid] = thread(gradient, tid, g, vx, vy, row, col, 1, start, end); 

      } 
      //Launched from the main; 
      gradient(1, g, vx, vy, row, col,0, start, end); 
      //Join the threads with the main thread 
      for (int i = 0; i < num_threads; ++i) 
      { 
       t[i].join(); 

      } 

     } 

Answer 1

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

Answer 2

Параллельное выполнение является огромным преимуществом для задач, которые легко расщепляются, а потоки не зависят от самих себя, однако создание потоков действительно связано с ценой. Представим себе, что компьютер ничего не делает, кроме запуска вашей программы (нет ОС и никаких других процессов). Процессор имеет 2 ядра, они являются процессорами по своему усмотрению и могут одновременно запускать любой код. В случае только одного потока второе ядро ​​сидит и ничего не делает, следовательно, есть потенциал для ускорения. Если вы создаете второй поток (и даете ему 50% задания), то теперь работает второе ядро, и теоретически ускорение равно 2 (игнорируя последовательные части и практические аспекты). Теперь давайте сделаем 4 потока. Подождите ... у нас есть два процессора и 4 потока? Да, теперь каждый процессор выполняет несколько операций, и перед изменением задачи, на которой он работает, ЦПУ должен переключать контексты (изменять значения регистров для хранения соответствующих значений переменных, перейти к разному разделу кода и т. Д.), Для этого требуется время и если вы создадите слишком много потоков, на самом деле это займет больше времени, чем выполнение задания. Это может оказать огромное влияние на любое поточное приложение и должно быть отмечено, прежде чем принимать решение о том, сколько потоков будет выполняться.

Обратите внимание, что это сообщение упрощает работу многих современных процессоров, которые могут эффективно выполнять более одного потока на ядро ​​(то есть HyperThreading).

Answer 3

Для любого параллельного выполнения вы должны принять во внимание Amdahl's law. В нем говорится о том, что время, необходимое, чтобы сделать некоторые задачи параллельно не масштабируется линейную с числом процессоров:

t = ((1-p) + p/n) * T 

где

T is the time needed for the task when it is done sequentially 
p fraction of time that can be parallelized 
n is the number of processors 

Обратите внимание, что я использовал несколько иную формулировку, но утверждение то же: общее ускорение, которое вы получаете, ограничено 1/(1-p) (например, если p=50% ваша параллельная версия будет работать в два раза быстрее).

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

t = ((1-p) + p/n) * T + o*p 
          ^^ overhead 

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

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