Использование многопоточности оптимизирует время выполнения (простой пример)

Question

У меня есть следующий код:

#include <boost/date_time/posix_time/posix_time.hpp> 
#include <boost/cstdint.hpp> 
#include <iostream> 

int main() 
{ 
  boost::posix_time::ptime start = boost::posix_time::microsec_clock::local_time(); 

  boost::uint64_t sum = 0; 
  for (int i = 0; i < 1000000000; ++i) 
    sum += i; 

  boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time(); 
  std::cout << end - start << std::endl; 

  std::cout << sum << std::endl; 
}

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

Вот мое решение:

#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/thread.hpp>
#include <boost/cstdint.hpp> 
#include <iostream> 


boost::uint64_t s1 = 0;
boost::uint64_t s2 = 0;

void sum1() 
{ 
  for (int i = 0; i < 500000000; ++i) 
    s1 += i; 
} 

void sum2()
{ 
  for (int i = 500000000; i < 1000000000; ++i) 
    s2 += i; 
}


int main() 
{ 
    boost::posix_time::ptime start = boost::posix_time::microsec_clock::local_time();

    boost::thread t1(sum1); 
    boost::thread t2(sum2); 

    t1.join(); 
    t2.join();

    boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time(); 
    std::cout << end - start << std::endl; 

    std::cout << s1+s2 << std::endl; 
} 

Пожалуйста, просмотрите, а также ответьте на следующие вопросы: 1. Почему этот код на самом деле не оптимизирует время выполнения? :) (Я использую процессор Intel Core i5 и 64-битную систему Win7) 2. Почему, когда я использую одну переменную s для хранения суммы вместо s1 и s2 , сумма становится неверной?

Заранее спасибо.

Answer 1

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

s += i;

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

Это связано с тем, что ОС планирует и отключает потоки на ЦП, и невозможно предсказать, как потоки будут чередовать выполнение своих команд.

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

Answer 2

Ответ на 1 должен быть следующим: запустить в профилировщике и посмотреть, что он говорит вам.

Но есть, по крайней мере, один обычный подозреваемый: ложный обмен. Ваши s1 и s2, скорее всего, окажутся на одной и той же линии кеша, поэтому ваши 2 ядра (если ваши 2 потока действительно оказываются на разных ядрах) должны синхронизироваться на уровне кешлины. Убедитесь, что 2 uint64_t находятся на разных линиях кэша (размер которых зависит от архитектуры, на которую вы ориентируетесь).

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

Answer 3

Самый простой способ реорганизовать программу (с точки зрения кода) для вычисления суммы с использованием нескольких потоков - это использовать OpenMP :

// $ g++ -fopenmp parallel-sum.cpp && ./a.out
#include <stdint.h>
#include <iostream>

const int32_t N = 1 << 30;

int main() {
  int64_t sum = 0;
#pragma omp parallel for reduction(+:sum)
  for (int32_t i = 0; i < N; ++i)
    sum += i;

  std::cout << sum << " " << static_cast<int64_t>(N)*(N-1)/2 << std::endl;
}

выход

576460751766552576 576460751766552576

---

Вот параллельное сокращение, реализованное с использованием потоков c ++ 11:

// $ g++ -std=c++0x -pthread parallel-sum-c++11.cpp && ./a.out
#include <cstdint>
#include <iostream>
#include <thread>

namespace {
  std::mutex mutex;

  void sum_interval(int32_t start, int32_t end, int64_t &sum) {
    int64_t s = 0;
    for ( ; start < end; ++start) s += start;

    std::lock_guard<std::mutex> lock(mutex);
    sum += s; 
  }
}

int main() {
  int64_t sum = 0;
  const int num_threads = 4;
  const int32_t N = 1 << 30;
  std::thread t[num_threads];

  // fork threads; assign intervals to sum
  int32_t start = 0, step = N / num_threads;
  for (int i = 0; i < num_threads-1; ++i, start += step)
    t[i] = std::thread(sum_interval, start, start+step, std::ref(sum));
  t[num_threads-1] = std::thread(sum_interval, start, N, std::ref(sum));

  // wait for result and print it
  for (int i = 0; i < num_threads; ++i) t[i].join();
  std::cout << sum << " " << static_cast<int64_t>(N)*(N-1)/2 << std::endl;
}

Примечание. Доступ к sum защищен, поэтому его может изменить только один поток за раз. Если sum равно std::atomic<int64_t>, блокировка может быть опущена.

Answer 4

Я отвечу первым:

Создание потока занимает гораздо больше времени, чем бездействие (базовое).

компилятор преобразует это:

for (int i = 0; i < 1000000000; ++i) 
     sum += i; 

в это:

//    << optimized away >>

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

Параллельная версия уменьшает способность компилятора оптимизировать программу при добавлении работы.