4 февраля 2013 г.

Задача с собеседования: продолжение

Поскольку в комментариях ответ нашли аж несколько раз, то сознаюсь — да, идея в том, что второй процессор это не только дополнительные 600 баксов стоимости и 70Вт энергопотребления, но еще и лишние 32Кб L1 кэша данных (а в Sandy Bridge так и лишние 256Кб L2, потому что там L2 тоже на каждое ядро). Так что, хотя в общем случае логично ожидать, что однопроцессорная версия будет быстрее (потому что не надо тратиться на синхронизацию), но если задача достаточно memory intensive (т.е. мы упираемся в скорость доступа к данным), причем фазы P1 и P2 оперируют разными данными, то в двухпроцессорном варианте данные фазы 1 будут горячими в кэше CPU1, а данные фазы 2 горячими в кэше CPU2. Получим эффективный размер L1 в 64Кб. И эффект от такого "увеличения" кэша может оказаться доминирующим, и оправдать даже расходы на синхронизацию.

Но мне стало интересно, смогу ли я этот эффект поймать в реальности. Реальность, как обычно, оказалась чуть сложнее теории, но в поединке мозга и компьютера мозг опять победил: вот этот код при базовых (тщательно подобранных) настройках дает в синхронном режиме (-Dasync=false) (690 +/- 1%) нс/сообщение, а в асинхронном (560 +/- 8%) нс/сообщение.

Хотелось бы в общих чертах понять, о чем говорит иностранецчто там происходит?

Нужно подобрать некоторую условную memory intensive задачу, и разбить ее на две фазы, каждая из которых обращается к своему куску данных. Я взял кусок данных в виде достаточно большого (сопоставимого с размером L1) массива double[]. Сама "фаза обработки сообщения" состоит из нескольких чтений/записей в ячейки этого массива. "Несколько" выбрано равным 128, и эти 128 ячеек выбираются из всего массива по псевдослучайному алгоритму (типа ЛКГ: I = (A*I) mod C). Сначала первая фаза делает это над своим массивом, потом вторая фаза делает ровно то же самое над своим — и так для каждого сообщения, коих легион 1 000 000 в каждом заходе. Да чего я код надиктовываю:
int index = message.index;
for( int i = 0; i < OPS_PER_MESSAGE; i++ ) {
  index = Math.abs( index * offset ) % DATA_SIZE;
  array[index] += amount;
}

Интересный вопрос №1: если псевдослучайное скакание по массиву заменить на проходку с фиксированным шагом, то разница в производительности практически пропадает. Скорее даже, с небольшим перевесом, почти на грани погрешности, начинает выигрывать синхронный вариант. Почему так? Интересный вопрос №2: если отставить в сторону рассмотренный вариант — какие еще эффекты могут обеспечить преимущество "распараллеленному" варианту последовательного кода? P.S. Да, кстати — мы (Дойче банк) набираем людей. Кажется, 3-4 вакансии у нас сейчас открыты. Можно прямо мне и писать — а то у меня еще много интересных идей для собеседования есть :)

4 комментария:

  1. Ответ на вопрос No 1: включается префетчинг. Дело в том, что если мы случайно бродим по массиву, то вероятность кэш-мисса зависит от размера кэша.
    Если же включается префетчинг, то кэш-миссы практически отсутствуют.

    ОтветитьУдалить
    Ответы
    1. Ага, точно. А что будет, если менять размер шага -- например, если взять шаг 1, 8, 256?

      Удалить
  2. Я думаю, что если взять шаг 1 и 8, то префетчинг включится, т.к. в это случае каждый раз будет загружаться та же или следующая кэш-линия, а в случае 256 не включится т.к. будет загружаться не следующая кэш-линия, а с пропуском. Впрочем, я слышал, что бывают префетчеры, которые распознают постоянный шаг, так что все зависит от конкретного железа.

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

    ОтветитьУдалить
    Ответы
    1. Да, в принципе верно. Вот как раз интеловский префетчер распознает сканирование памяти с постоянным шагом до 2048 байт (кажется). Так что с шагом до 256*double префетчинг будет работать.

      А вот совсем любопытный вопрос(на этот раз я сам пока ответа не знаю): почему с некоторыми шагами (например 73, 81, 97, 105, 113, 121, 127, 129...) асинхронный вариант работает в разы медленнее (в 5-8 раз), чем с остальными? Синхронный же вариант, похоже, такого эффекта не демонстрирует.

      Удалить