Ложный обмен и pthreads - PullRequest
       17

Ложный обмен и pthreads

8 голосов
/ 30 ноября 2011

У меня есть следующая задача для демонстрации ложного обмена и я написал простую программу:

#include <sys/times.h>
#include <time.h>
#include <stdio.h> 
#include <pthread.h> 

long long int tmsBegin1,tmsEnd1,tmsBegin2,tmsEnd2,tmsBegin3,tmsEnd3;

int array[100];

void *heavy_loop(void *param) { 
  int   index = *((int*)param);
  int   i;
  for (i = 0; i < 100000000; i++)
    array[index]+=3;
} 

int main(int argc, char *argv[]) { 
  int       first_elem  = 0;
  int       bad_elem    = 1;
  int       good_elem   = 32;
  long long time1;
  long long time2;
  long long time3;
  pthread_t     thread_1;
  pthread_t     thread_2;

  tmsBegin3 = clock();
  heavy_loop((void*)&first_elem);
  heavy_loop((void*)&bad_elem);
  tmsEnd3 = clock();

  tmsBegin1 = clock();
  pthread_create(&thread_1, NULL, heavy_loop, (void*)&first_elem);
  pthread_create(&thread_2, NULL, heavy_loop, (void*)&bad_elem);
  pthread_join(thread_1, NULL);
  pthread_join(thread_2, NULL);
  tmsEnd1 = clock(); 

  tmsBegin2 = clock();
  pthread_create(&thread_1, NULL, heavy_loop, (void*)&first_elem);
  pthread_create(&thread_2, NULL, heavy_loop, (void*)&good_elem);
  pthread_join(thread_1, NULL);
  pthread_join(thread_2, NULL);
  tmsEnd2 = clock();

  printf("%d %d %d\n", array[first_elem],array[bad_elem],array[good_elem]);
  time1 = (tmsEnd1-tmsBegin1)*1000/CLOCKS_PER_SEC;
  time2 = (tmsEnd2-tmsBegin2)*1000/CLOCKS_PER_SEC;
  time3 = (tmsEnd3-tmsBegin3)*1000/CLOCKS_PER_SEC;
  printf("%lld ms\n", time1);
  printf("%lld ms\n", time2);
  printf("%lld ms\n", time3);

  return 0; 
} 

Я был очень удивлен, когда увидел результаты (я запускаю его на своем процессоре i5-430M).

  • При ложном обмене это было 1020 мс.
  • Без ложного обмена, это было 710 мс, только на 30% быстрее вместо 300% (на некоторых сайтах было написано, что это будет быстрее, чем 300-400%).
  • Без использования pthreads это было 580 мс.

Пожалуйста, покажи мне мою ошибку или объясни, почему это происходит.

Ответы [ 2 ]

21 голосов
/ 30 ноября 2011

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

Чтобы понять ложное совместное использование, вам необходимопонять кеши.В большинстве процессоров каждое ядро ​​будет иметь свой собственный кэш L1, в котором хранятся данные, к которым недавно обращались.Кэши организованы в «линии», которые выровнены по частям данных, обычно длиной 32 или 64 байта (в зависимости от вашего процессора).Когда вы читаете с адреса, которого нет в кэше, вся строка считывается из основной памяти (или из кэша L2) в L1.Когда вы записываете адрес в кеше, строка, содержащая этот адрес, помечается как «грязная».

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

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

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

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

3 голосов
/ 18 марта 2017

Функция Brief on clock () в C - показывает количество тактовых импульсов ЦП, прошедших от начала до конца. Таким образом, когда вы запускаете два параллельных потока, количество тактов ЦП будет тактовым тактом ЦП1 + тактовым тактом ЦП2. Я думаю, что вы хотите настоящие часы таймера. Для этого используйте clock_gettime (), и вы должны получить ожидаемый результат.

Я запустил ваш код с помощью clock_gettime (). Я получил это:

с ложным разделением 874,587381 мс

без ложного обмена 331,844278 мс

последовательное вычисление 604,160276 мс

...