Как влияет кеш на многопоточные приложения

    Теоретическая составляющая.

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

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

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

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


    Эксперимент.
    Для проверки были написаны 2 многопоточных программы на С++ для двух случаев пересечения рабочих областей:

    • Области не пересекаются и находятся в стеке каждой из нитей;
    • Рабочая область для нитей общая, представляет собой массив из 1, 4 и 8 байтных слов, общей длиной 1024 байта, каждая из нитей модифицирует свои слова (например только четные или только нечетные).


    Рабочих нитей – 2, каждая, меняя свои слова, проходит весь массив и, достигнув границы, возвращается к началу и так далее. Каждая из нитей делает по 100 000 000 изменений.

    UPD Спасибо mikhanoid за выявленную опечатку в названии CPU.
    Для тестирования использовалась рабочая станция HP xw4600, CPU Core 2 Quad (Q9300), OS Linux Slamd64 12.1, ядро 2.6.24.5, компилятор gcc 4.2.3. В итоге получалась 64-х битная программа, следовательно любая арифметическая операция для слов длиной 1,4 и 8 байт выполнялась за 1 такт.

    Время исполнения измерялось командой time(1), и усреднялось по 5-и экспериментам.

    Сначала была написана программа, которая просто инкрементирует слово и кладет его обратно, но оказалось что в случае массива на стеке оптимизация -O2 творит что-то непотребное. Поэтому была написана вторая программа, которая делает с данными что-то более сложное.

    Результаты.
    UPD: Thnx за замечание mt_ и Google Charts за api графиков. Результат в графической форме.
    Желающие посмотреть цифры, могут промотать дальше.

    По оси Y реальное время исполнения программы в секундах. По оси X разрядность слова (парами).

    Программа 1.

    image

    Программа 2.

    image

    Программа 2 + оптимизация -O2.

    image

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

    А вот зависимость от длины слова как-то мало заметна.

    Идея данного опуса навеяна статьей www.ddj.com/architect/208200273.

    UPD Попытка перенести в блог Совершенный код, мне кажется что это самое правильное место.

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

    Программа 1 (общая память).
    Длина слова 64 32 8
    Реальное время 1,297 1,532 0,846
    Время польз. режима 2,461 3,049 1,664


    Программа 1 (стек)
    Длина слова 64 32 8
    Реальное время 0,453 0,431 0,441
    Время польз. режима 0,851 0,842 0,866


    Программа 2 (общая память).
    Длина слова 64 32 8
    Реальное время 9,191 9,033 8,921
    Время польз. режима 18,365 18,039 17,824


    Программа 2 (стек)
    Длина слова 64 32 8
    Реальное время с 8,432 8,412 8,808
    Время польз. Режима с 16,843 16,796 17,548


    Программа 2 + оптимизация -O2 (общая память).
    Длина слова 64 32 8
    Реальное время 4,247 4,380 3,473
    Время польз. режима 8,415 8,960 6,781


    Программа 2 + оптимизация -O2 (стек)
    Длина слова 64 32 8
    Реальное время 3,282 3,718 3,308
    Время польз. режима 6,550 7,384 5,565


    Исходный код.

    Программа 1.

    #include <sys/types.h>

    #include <stdio.h>
    #include <stdlib.h>

    #include <pthread.h>

    #define TBYTES 1024
    //
    #define TOTAL 2
    // определяет тип слова u_int8_t u_int32_t u_int64_t
    #define MTYPE u_int8_t
    //
    #define MAXAR TBYTES/sizeof(MTYPE)
    #define DOIT 100000000

    MTYPE *array;

    pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;
    pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
    int workers = 2;

    // Определяет используется ли общая память
    //#define SHARED 1

    void*
    runner(void* args){
      unsigned int which = *(unsigned int*)args; delete (unsigned int*)args;
      unsigned int index = which;
      MTYPE array1[MAXAR];
      //
      for ( unsigned int i = 0; i < DOIT; ++i){
        if ( index >= MAXAR)
          index = which;
        //
    #if defined(SHARED)
        array[index] = array[index] + 1;
    #else
        array1[index] = array1[index] + 1;
    #endif
        //
        index += TOTAL;
      }
      //
      pthread_mutex_lock(&mux);
      -- workers;
      pthread_mutex_unlock(&mux);
      pthread_cond_broadcast(&cond);
      //
      return 0;
    };  

    int
    main() {
      //
      array = (MTYPE*)calloc(MAXAR, sizeof(MTYPE));
      //
      unsigned int *which;
      pthread_t t1;
      pthread_attr_t attr;
      //
      pthread_attr_init(&attr);
      pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
      //
      which = new unsigned int(0);
      pthread_create(&t1, &attr, runner, (void*)which);
      //
      which = new unsigned int(1);
      pthread_create(&t1, &attr, runner, (void*)which);
      //
      pthread_mutex_lock(&mux);
      while(!pthread_cond_wait(&cond, &mux)){
        if ( !workers)
          break;
      };
      pthread_mutex_unlock(&mux);
      //
      return 0;
    };
    //  

    * This source code was highlighted with Source Code Highlighter.



    Программа 2.

    #include <sys/types.h>

    #include <stdio.h>
    #include <stdlib.h>

    #include <pthread.h>

    #define TBYTES 1024
    //
    #define TOTAL 2
    // определяет тип слова u_int8_t u_int32_t u_int64_t
    #define MTYPE u_int64_t
    //
    #define MAXAR TBYTES/sizeof(MTYPE)
    //#define DOIT 100000000 * (sizeof(u_int64_t) / sizeof(MTYPE))
    #define DOIT 100000000

    MTYPE *array;

    pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;
    pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
    int workers = 2;

    template<typename RTYPE, int TLEN>
    RTYPE scramble(u_int16_t *seed, RTYPE a){
      int d;
      //
      for ( d = 0; d < 8; ++d){
        u_int16_t mask;
        //
        mask = (*seed & 0x1) ^ ( (*seed >> 1) &0x1);
        mask = mask & 0x1;
        *seed = (mask << 15) | (*seed >> 1);
        //
        a = a ^ ((RTYPE)mask << d);  
      }
      //
      return a;
    };

    // Определяет используется ли общая память
    //#define SHARED 1

    void*
    runner(void* args){
      unsigned int which = *(unsigned int*)args; delete (unsigned int*)args;
      unsigned int index = which;
      u_int16_t seed = 0x4a80;
      MTYPE array1[MAXAR];
      //
      for ( unsigned int i = 0; i < DOIT; ++i){
        MTYPE data;
        if ( index >= MAXAR)
          index = which;
        //
    #if defined(SHARED)
        data = array[index];
        array[index] = scramble<MTYPE, 8*sizeof(MTYPE)>(&seed, data);
    #else
        data = array1[index];
        array1[index] = scramble<MTYPE, 8*sizeof(MTYPE)>(&seed, data);
    #endif
        //
        index += TOTAL;
      }
      //
      pthread_mutex_lock(&mux);
      -- workers;
      pthread_mutex_unlock(&mux);
      pthread_cond_broadcast(&cond);
      //
      return 0;
    };  

    int
    main() {
      //
      array = (MTYPE*)calloc(MAXAR, sizeof(MTYPE));
      //
      unsigned int *which;
      pthread_t t1;
      pthread_attr_t attr;
      //
      pthread_attr_init(&attr);
      pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
      //
      which = new unsigned int(0);
      pthread_create(&t1, &attr, runner, (void*)which);
      //
      which = new unsigned int(1);
      pthread_create(&t1, &attr, runner, (void*)which);
      //
      pthread_mutex_lock(&mux);
      while(!pthread_cond_wait(&cond, &mux)){
        if ( !workers)
          break;
      };
      pthread_mutex_unlock(&mux);
      //
      return 0;
    };
    //  

    * This source code was highlighted with Source Code Highlighter.


    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 26

        0
        Спасибо. Ульрих силен, хотя бывали и у него закидоны.
          0
          Спасибо. Когда-то читал часть в html-виде, однако все статьи одним pdf-ом придутся очень кстати.
            0
            У меня некоторое время назад была мысль перевести эту серию статей Ульриха. Хочу поинтересоваться, нужно ли это хабрачеловекам? И нет ли уже перевода?
              0
              ИМХО такой труд всегда будет интересен, но если будет доведен до конца. Еще я бы спросил списаляся по этому поводу с самим Ульрихом, и внимательно посмотрел комменты на lwn.net.
                0
                Ну насколько я помню, в оригинале на lwn-е было написано что он не против. Хотя письмо отправлю. Довести до конца может помочь краудсорсинг. В частности translated.by

                В общем, я потихоньку начну это дело, а там возможно народ подтянется
                  0
                  Здесь дело, в общем-то не в разрешении. Во-первых непонятные места нужно обсуждать с автором, и во-вторых по истечении времени может всякое в голову приходить.
            +1
            Спасибо за интересное исследование. В качестве предложений, думаю что представление результатов в более удобочитаемом виде (графики, с указанием не абсолютных, а относительных приростов скорости) сделало бы статью ещё более интересной.
              0
              Согласен. Основная проблема заключается в тестовых алгоритмах. Как-то не придумался вариант с одной стороны полезный, с другой стороны мало искажающий суть проблемы.
              Хотя еще не вечер, будем искать.
              +8
              Хм… Тест вобщем-то не совсем корректный, imho. Потому что нити запускаются не одновоременно, scramble работает не за такт, да ещё и процессоры не в одну линию кэша долбятся, а последовательно в разные.

              В Core 2 Duo синхронизация кэшей поддерживается между кэшами L1, а они очень быстрые — латентность всего в три такта (не думаю, что синхронизация значительно больше времени требует: такт на то, чтобы найти нужную линию и (шина в 128 бит, линия 64 байта) 4 такта на передачу данных — в итоге задержка всего в два раза больше (в худшем случае), чем при доступе в свой кэш, при этом Core 2 Duo умеет выбирать данные из синхронизационного траффик прямо в регистры. А это всё означает, что задержки на доступ к данным в чужом кэше сравнимы со скоростью работы scramble. Это (1).

              (2) Процессоры же у нас все из себя out-of-order и суперскалярные. А циклы, которые вы приводите во втором тесте хорошо параллелятся. И множество итераций scramble-цикла будут загружены и будут выполнятся одновременно. И будут переупорядочены. Из этого выйдет вот что:

              Запросы на доступ поступят ко многим линиям данных одновременно, но первой (наиболее вероятно) в кэш ядра (0) будет затянута та линия, с которой не работает ядро (1), а такие линии есть. В итоге начнёт быстро выполнятся блок итераций цикла, который без помех проработает со своей линией кэша. Код этот работает относительно долго, поэтому параллельно с ним вполне могут быть подтянуты в кэш и другие линии. В итоге, за счёт этой самой OoOE, переупорядочивания и быстроты L1 код будет обрабатываться примерно с той же скоростью, что и в случае без общей памяти. Что и наблюдается.

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

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

              Эффекты для кода 2 на in-order процессорах, естественно, будут прявлятся ярче. Но это на ARM'ах тестировать, на PowerPC или SPARC.
                0
                >> Тест вобщем-то не совсем корректный, imho.
                Да я, в общем-то, абсолютной корректности и не добивался. Главное было понять проявится эффект или нет. С большой долей уверенности можно сказать что проявляется. Тема слишком тонкая и не такая простая для тестов.
                В основе моих тестов лежит идея о том, чтобы данные постоянно обновлялись, что приводило бы к постоянным синхронизациям и, как следствие, к столкновениям.

                >>Потому что нити запускаются не одновоременно

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

                >> scramble работает не за такт
                Да уж не самый удачный тест, но причина его использования упомянута в тексте.

                >> да ещё и процессоры не в одну линию кэша долбятся, а последовательно в разные.

                В принципе, для первого теста для случая 1 и 4-х байт должный попадать на одну линию.

                >> В Core 2 Duo синхронизация кэшей…
                Должен признать опечатку. Процессор Core 2 Quad, но судя по всему там тоже линейки по 64 байта.
                Вообще тема синхронизации достаточно сложная. С учетом ассоциативности время на определение наличия в кеше должно быть меньше одного такта (скорее всего меньше 1/2 такта). Синхронизация кешей зависит от особенностей внутренней шины, точнее арбитра шины, и скорее всего будет больше заявленных 3 тактов.
                Вообще второй тест какой-то неудачный получился.

                >> Процессоры же у нас все из себя out-of-order и суперскалярные.

                Главное правило при проектировании CPU: внутри cpu может происходить все как угодно, но программа должна исполняться в том порядке в котором она была записана в памяти. Т.е. в любом случае процессор делает работу так как если бы за такт выполнялась одна комманда и не более. Иначе получится что программы не будут давать ожидаемого результата. Если вам будет интересна эта тема, то лучше почитать отчеты WRL 1989-1991 годов по Альфе.

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

                В интелях еще 10 лет назад в у декодеров были буферы 256к. Так что код, скорее всего и из кеша только один раз выбирался, но это слишком тонкая материя, хотя нити могут мигрировать по ядрам…

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

                Хмм… Так тесты и для разной длины слов проводились. В программах менялось MTYPE на нужное значение. Если вы об этом.

                Уф. По этой теме можно писать много и вдумчиво.
                  0
                    0
                    Главное правило при проектировании CPU: внутри cpu может происходить все как угодно, но программа должна исполняться в том порядке в котором она была записана в памяти. Т.е. в любом случае процессор делает работу так как если бы за такт выполнялась одна комманда и не более. Иначе получится что программы не будут давать ожидаемого результата. Если вам будет интересна эта тема, то лучше почитать отчеты WRL 1989-1991 годов по Альфе.

                    Да, но у в приведённых программах нет же зависимостей write-after-read в разные ячейки памяти. А в Core 2 Duo есть Memory Disambiguation Unit, который как раз и позволяет отслеживать такие вот конфликты. Когда конфликтов нет, то код запускается параллельно.

                    Хмм… Так тесты и для разной длины слов проводились. В программах менялось MTYPE на нужное значение. Если вы об этом.

                    И какие цифирьки получились? Интересно же.
                      0
                      >> Да, но у в приведённых программах нет же зависимостей write-after-read в разные ячейки памяти…
                      Ну да, зависимостей нет. Однако шина чтения/записи одна и поэтому две операции с памятью параллельно невозможны. Причем, записи скорее всего в одну линейку кеша, кешировать запись нельзя, иначе можно получить гонку.
                      Здесь более интересный вопрос в том есть у коры свой кеш или нет, вот это для меня уже загадка.

                      >> И какие цифирьки получились? Интересно же.
                      За выводами будут таблицы. Первые две это для случая чтения-инкремент-запись. Вторая пара для случая чтение-скремблер-запись без оптимизации. Третья пара для случая чтение-скремблер-запись с оптимизацией -O2. Длина слова в битах.
                      В принципе Вы правы. В случае скремблера операция с данными слишком долгая, поэтому эффект мало заметен, особенно после оптимизации.
                        0
                        Про гонку не понятно, почему кешировать нельзя?
                          +1
                          Эх, описка :(, надо читать вместо кешировать — буферизовать. Если буферизовать записи от многих операций, то создается условие когда результат уже есть а еще недоступен. В многопроцессорной системе другой проц может считать старые данные при наличии новых. Явный случай гонки. Но это теоретизирование.
                            0
                            Согласен, но на обычном десктопе такое может быть только при использовании DMA, т.е. на память прикладных программ это никак не влияет, запись откладывается/комбинируется пока полоска не понадобиться под другие адреса.

                            Кстати, в пределах одного «такта» может быть параллельный доступ к разным банкам полоски кеша (4 банка по 16 байт) и на чтение и на запись.
                              +1
                              Тык. Сейчас такие ситуации считаются нормальными. Доступ к памяти нужно упорядочивать явно при помощи барьеров памяти. В x86 — это инструкции mfence, int/call или cmpxchg. Если эти инструкции не встречаются, ядра имеют право оповещать о своих операциях с памятью контроллеры других кэшей в произвольном порядке.
                    +1
                    не хочу показаться занудой, но:
                    «В многокорной и многопроцессорной системах у каждой коры или процессора есть свой персональный кеш» — может всетаки так:
                    «В многоядерной и многопроцессорной системах у каждого ядра или процессора есть свой персональный кеш»? а то «кора» как-то режет «кору» мозга :)
                      0
                      Эх, ваша правда, что-то я каким-то сленгом написал)
                      0
                      Спасибо большое за интересную статью.
                        0
                        Пожалуйста.
                      • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          >> Эксперимент хоть и грязный, но характерную особенность snooping-кешей показывает.
                          Ого, это много глубже чем мне хотелось бы залезать :). Хотя главное будет исполнение останавливаться если обнаружена некогерентность или нет, ммм где-то в глубине шевелются воспоминания о том что может и не будет.

                          >> Если не пытаться…
                          Если честно, идея инкрементировать одно и тоже слово мне не нравится, потому как, если отбросить атомарные операции, это таки ошибка. Другое дело — ограничить область памяти до одной линейки. Тут и синхронизация мало влиять должна.

                          >> Со скремблером идея неплоха, только сделайте её быстрее…
                          Спасибо ;) Ускорить можно, но на это надо потратить несколько часов, ибо последний раз я такую задачу делал лет 10 назад. Как-то мало времени.

                          Эх, пробую, но я как-то мало силен в верстке.
                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Уффф. Наверное да. Меня больше интересовали возможные последствия именно для случая массивов. Многопоточное приложение с общими данными это обыденность, причем иногда спрятанная за фасадом того или иного тулкита или библиотеки.

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

                        Самое читаемое