Что предпочтительнее - читать линейно или писать линейно ?

Тема в разделе "WASM.A&O", создана пользователем v_mirgorodsky, 7 мар 2007.

  1. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Немного теории. Обработка изображений осуществляется небольшими участками - блоками. В зависимости от алгоритма размер блока может составлять 4x4, 8x8 или 16x16 точек растра. Для последующей обработки логично данные уложить поблочно так, чтобы данные одного блока лежали подряд. Исходное изображение может иметь любые размеры. Логично, что буфер обработки находится как минимум в L2 кэше - уж слишком часто он используется в работе. Еще момент - данные обрабатываются словами по 16 бит, а хранятся в изображении восьмибитными. Таким образом есть два варианта реализации алгоритма раскладки. Для определенности возьмем блок 8x8, тогда общее место занимаемое одним блоком - 128 байт.

    Вариант 1. Сканируем изображение строками слева на право и сверху вниз по 8 точек за итерацию. Данные каждого блока укладываем по мере поступления в буфер соответствующего блока. Таким образом имеем чтение подряд по восемь байт за такт (movq), имеем запись с шагом 128 байт по 8 байт за раз. Один поток на чтение, один поток на запись - просто идеальные условия для блоков Hardware Prefetch :) При этом P4 умеет писать данные прямо в L2, если их нет в L1 - что еще более улучшает ситуацию.

    Вариант 2. Сканируем изображение блоками слева на право и сверху вниз по 64 точки за итерацию. Данные каждого блока укладываем по мере поступления в буфер соответствующего блока. Таким образом имеем 8 потоков чтения и один поток записи. Чтение идет с шагом равным ширине изображения, запись идет подряд. BTW, количество потоков чтения практически не важно - можно подымать две строки блоков практически с той же эффективностью - еще один сложно объяснимый факт, т.к. аппаратно отслеживается только восемь потоков чтения и записи. Ситуация в L1 кэше должна напоминать восточный базар - данные постоянно должны вытеснять друг друга в связи с конечной ассоциативностью кэша.

    На первый взгляд кажется, что Вариант 1 будет быстрее в силу лучшей организации потоков. Однако это не так. Вариант 1 проигрывает Варианту 2 порядка 20% производительности :o) Ситуация наблюдалась на нескольких процессорах линейки P4 с разными частотами ядра и системной шины - результат везде был одинаков. Отличался только проигрыш Варианта 1 Варианту 2.

    Понятно, что подымать данные можно квадратиками - ничего сложного в этом нет. Немного больше размер кода, собственно по этой причине и была начата переделка существующих модулей. Однако интересует вопрос причины такого неестественного поведения. И будет ли аналогичное поведение наблюдаться и на других процессорах Intel и AMD?
     
  2. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Опять ты увлекаешься одним фактором и забываешь о других пресловутых resource constraints ;) Поведение может и не очень "естественное", но к хардварному префетчу оно имеет весьма отдаленное отношение.
    Во-первых, в варианте 2 реализуется естественный софтварный префетч, поэтому никакая хардварная поддержка ему не нужна (она может даже мешать). В топике Эффективность block-prefetch техник я уже говорил, что задача любого префетча это упреждающее формирование запросов чтения памяти, позволяющее скрыть существенную латентность самих запросов на фоне передачи данных. Во втором варианте так и происходит - один за другим идут 8 запросов к разным линейкам кэша и латентность их оверхедов прячется внутри предыдущих, поэтому в P4 блок 8*128=1К и так грузится на макс.скорости, поэтому если даже хардварный префетч не рулит, то латентность запроса может проявляться только при переходе к след. 1К блоку.
    Во-вторых, в варианте 2 "восточный базар" в L1 будет только в случае, когда длина строки изображения кратна алиасингу L1 и число строк в блоке превышает его ассоциативность. В противном случае все 8 строк будут попадать или в разные линейки L1 или в разные way и никакого "базара" не будет. В P4E, PM и Core ассоциативность L1 = 8, поэтому и "базара нет" при любой длине строки. В AMD ассоциативность = 2, но размер кэша = 64 К, поэтому для строк изображения < 8К конфликтов быть не может, а для бОльших может при условии, что адреса блоков из 3 строк будут различаться на величины, кратные 32К, что маловероятно. Пожалуй только для первых "недоделанных" P4 c размером кэша 8К и ассоциативностью 4 существует вероятность конфликта более 4-х блоков с кратностью 2К.
    Поэтому дело тут не в префетче и порядке чтения, а в порядке записи данных в L2. Тут нужно копать в сторону известных ограничений - ошибок store-to-load forwarding'а и конфликта данных в L1 из-за частичной проверки адреса, конфликта банков, ограничений на число outstanding misses и write combining buffers. Если немного "помозговать" и поэкспериментировать с разными вариантами записи при последовательном чтении, то можно прийти к выводу, что дело по всей видимости в write combining'е при записи в L2. Например, в P4 Northwood 6 WC-буферов, поэтому если производить запись только в 1-6 блоков, то скорость чтения получается примерно такой же как и в варианте 2 с последовательной записью, а вот при увеличении числа записываемых блоков свыше 6-ти получаем падение скорости на 20-25% (для твоего алгоритма обработки 8->16 на mmx). Из этого можно сделать вывод, что при L1-miss записываемые данные сразу сбрасываются в один из WC-буферов не дожидаясь проверки в L2 и затем в сл. L2-hit сбрасываются в L2, а при L2-miss продолжают сидеть в буфере в ожидании RFO (read for ownership) из ОЗУ. Поэтому при последовательной записи (или параллельно-последовательной с числом записываемых линеек <= числа буферов) данные какое-то время могут накапливаться в WC-буферах и сбрасываться в L2 реже большими порциями. А при "рваной" записи приходится чаще сбрасывть буферы в L2 и чаще нарываться на конфликты чтения-записи (и возможно на латентность доступа к L2)