Эффективность block-prefetch техник при работе с памятью

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

  1. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Пусть имеется восьмибитное изображение шириной 720 точек и высотой 8. Таким образом общий размер блока составляет 5760 байт, что меньше размера L1 кеша на P4 Prescott. Далее, информацию из этого блока изображения необходимо разбить на квадраты 8x8 и разложить подряд для последующей обработки. Для максимально эффективного решения этой задачи был сдела двухстадийный алгоритм - в первой части выполнялся prefetch всего блока изображения предположительно в L1 кэш (?), а далее эти данные раскладывались уже в буффер для обработки. Поскольку объем данных для обработки невелик, то запись предположительно осуществлялась в L2 кэш. Следующий кусочек кода демонстрирует эту технику:

    Код (Text):
    1. m_frame_2_cell_mmx macro    CellBuffer:req,FrameBuffer:req,FrameBlkSize:req,FrameLineStride:req,PrefetchStride:req
    2. local           cell_prefetch, cell_copy
    3.  
    4.                 ; Prefetch cell data to L1 data cache ====================================================================
    5.                 mov         eax,FrameLineStride                             ; eax = FrameLineStride
    6.                 mov         esi,FrameBuffer                                 ; eax = src data pointer
    7.                 lea         edi,[esi + 8 * eax]                             ; edi = next cell block pointer
    8.  
    9. cell_prefetch:  mov         ebx,[esi]                                       ; 32 * PrefetchStride bytes
    10.                 mov         ebx,[esi + PrefetchStride]                      ; 2x unrolled loop
    11.                 lea         esi,[esi + 2 * PrefetchStride]                  ; Advance src data pointer
    12.                 cmp         esi,edi                                         ; Last line ?
    13.                 jb          cell_prefetch
    14.  
    15.                 ; Copy cell-by-cell ======================================================================================
    16.                 mov         eax,FrameLineStride                             ; eax = FrameLineStride
    17.                 lea         ebx,[eax + 2 * eax]                             ; ebx = 3 * FrameLineStride
    18.                 mov         ecx,FrameBlkSize                                ; ecx = frame block size in bytes
    19.                 mov         esi,FrameBuffer                                 ; esi = src data pointer
    20.                 mov         edi,CellBuffer                                  ; edi = dst data pointer
    21.  
    22. cell_copy:      movq        mm0,[esi]                                       ; mm0 = [ Y07 Y06 Y05 Y04 Y03 Y02 Y01 Y00 ]
    23.                 movq        mm1,[esi + eax]                                 ; mm1 = [ Y17 Y16 Y15 Y14 Y13 Y12 Y11 Y10 ]
    24.                 movq        mm2,[esi + 2 * eax]                             ; mm2 = [ Y27 Y26 Y25 Y24 Y23 Y22 Y21 Y20 ]
    25.                 movq        mm3,[esi + ebx]                                 ; mm3 = [ Y37 Y36 Y35 Y34 Y33 Y32 Y31 Y30 ]
    26.                 lea         esi,[esi + 4 * eax]                             ; Advance src data pointer
    27.  
    28.                 punpcklbw   mm4,mm0                                         ; mm4 = [ Y03   x Y02   x Y01   x Y00   x ]
    29.                 punpckhbw   mm5,mm0                                         ; mm5 = [ Y07   x Y06   x Y05   x Y04   x ]
    30.                 psrlw       mm4,8                                           ; mm4 = [     Y03     Y02     Y01     Y00 ]
    31.                 psrlw       mm5,8                                           ; mm5 = [     Y07     Y06     Y05     Y04 ]
    32.                 movq        [edi + 0 * 16 + 0],mm4                          ; Save  [     Y03     Y02     Y01     Y00 ]
    33.                 movq        [edi + 0 * 16 + 8],mm5                          ; Save  [     Y07     Y06     Y05     Y04 ]
    34.  
    35.                 punpcklbw   mm4,mm1                                         ; mm4 = [ Y13   x Y12   x Y11   x Y10   x ]
    36.                 punpckhbw   mm5,mm1                                         ; mm5 = [ Y17   x Y16   x Y15   x Y14   x ]
    37.                 psrlw       mm4,8                                           ; mm4 = [     Y13     Y12     Y11     Y10 ]
    38.                 psrlw       mm5,8                                           ; mm5 = [     Y17     Y16     Y15     Y14 ]
    39.                 movq        [edi + 1 * 16 + 0],mm4                          ; Save  [     Y13     Y12     Y11     Y10 ]
    40.                 movq        [edi + 1 * 16 + 8],mm5                          ; Save  [     Y17     Y16     Y15     Y14 ]
    41.  
    42.                 punpcklbw   mm4,mm2                                         ; mm4 = [ Y23   x Y22   x Y21   x Y20   x ]
    43.                 punpckhbw   mm5,mm2                                         ; mm5 = [ Y27   x Y26   x Y25   x Y24   x ]
    44.                 psrlw       mm4,8                                           ; mm4 = [     Y23     Y22     Y21     Y20 ]
    45.                 psrlw       mm5,8                                           ; mm5 = [     Y27     Y26     Y25     Y24 ]
    46.                 movq        [edi + 2 * 16 + 0],mm4                          ; Save  [     Y23     Y22     Y21     Y20 ]
    47.                 movq        [edi + 2 * 16 + 8],mm5                          ; Save  [     Y27     Y26     Y25     Y24 ]
    48.  
    49.                 punpcklbw   mm4,mm3                                         ; mm4 = [ Y33   x Y32   x Y31   x Y30   x ]
    50.                 punpckhbw   mm5,mm3                                         ; mm5 = [ Y37   x Y36   x Y35   x Y34   x ]
    51.                 psrlw       mm4,8                                           ; mm4 = [     Y33     Y32     Y31     Y30 ]
    52.                 psrlw       mm5,8                                           ; mm5 = [     Y37     Y36     Y35     Y34 ]
    53.                 movq        [edi + 3 * 16 + 0],mm4                          ; Save  [     Y33     Y32     Y31     Y30 ]
    54.                 movq        [edi + 3 * 16 + 8],mm5                          ; Save  [     Y37     Y36     Y35     Y34 ]
    55.  
    56.                 movq        mm0,[esi]                                       ; mm0 = [ Y47 Y46 Y45 Y44 Y43 Y42 Y41 Y40 ]
    57.                 movq        mm1,[esi + eax]                                 ; mm1 = [ Y57 Y56 Y55 Y54 Y53 Y52 Y51 Y50 ]
    58.                 movq        mm2,[esi + 2 * eax]                             ; mm2 = [ Y67 Y66 Y65 Y64 Y63 Y62 Y61 Y60 ]
    59.                 movq        mm3,[esi + ebx]                                 ; mm3 = [ Y77 Y76 Y75 Y74 Y73 Y72 Y71 Y70 ]
    60.                 sub         esi,ebx                                         ;
    61.                 sub         esi,eax                                         ; Restore src data pointer original value
    62.                 lea         esi,[esi + 8]                                   ; Advance src data pointer to next cell
    63.  
    64.                 punpcklbw   mm4,mm0                                         ; mm4 = [ Y43   x Y42   x Y41   x Y40   x ]
    65.                 punpckhbw   mm5,mm0                                         ; mm5 = [ Y47   x Y46   x Y45   x Y44   x ]
    66.                 psrlw       mm4,8                                           ; mm4 = [     Y43     Y42     Y41     Y40 ]
    67.                 psrlw       mm5,8                                           ; mm5 = [     Y47     Y46     Y45     Y44 ]
    68.                 movq        [edi + 4 * 16 + 0],mm4                          ; Save  [     Y43     Y42     Y41     Y40 ]
    69.                 movq        [edi + 4 * 16 + 8],mm5                          ; Save  [     Y47     Y46     Y45     Y44 ]
    70.  
    71.                 punpcklbw   mm4,mm1                                         ; mm4 = [ Y53   x Y52   x Y51   x Y50   x ]
    72.                 punpckhbw   mm5,mm1                                         ; mm5 = [ Y57   x Y56   x Y55   x Y54   x ]
    73.                 psrlw       mm4,8                                           ; mm4 = [     Y53     Y52     Y51     Y50 ]
    74.                 psrlw       mm5,8                                           ; mm5 = [     Y57     Y56     Y55     Y54 ]
    75.                 movq        [edi + 5 * 16 + 0],mm4                          ; Save  [     Y53     Y52     Y51     Y50 ]
    76.                 movq        [edi + 5 * 16 + 8],mm5                          ; Save  [     Y57     Y56     Y55     Y54 ]
    77.  
    78.                 punpcklbw   mm4,mm2                                         ; mm4 = [ Y63   x Y62   x Y61   x Y60   x ]
    79.                 punpckhbw   mm5,mm2                                         ; mm5 = [ Y67   x Y66   x Y65   x Y64   x ]
    80.                 psrlw       mm4,8                                           ; mm4 = [     Y63     Y62     Y61     Y60 ]
    81.                 psrlw       mm5,8                                           ; mm5 = [     Y67     Y66     Y65     Y64 ]
    82.                 movq        [edi + 6 * 16 + 0],mm4                          ; Save  [     Y63     Y62     Y61     Y60 ]
    83.                 movq        [edi + 6 * 16 + 8],mm5                          ; Save  [     Y67     Y66     Y65     Y64 ]
    84.  
    85.                 punpcklbw   mm4,mm3                                         ; mm4 = [ Y73   x Y72   x Y71   x Y70   x ]
    86.                 punpckhbw   mm5,mm3                                         ; mm5 = [ Y77   x Y76   x Y75   x Y74   x ]
    87.                 psrlw       mm4,8                                           ; mm4 = [     Y73     Y72     Y71     Y70 ]
    88.                 psrlw       mm5,8                                           ; mm5 = [     Y77     Y76     Y75     Y74 ]
    89.                 movq        [edi + 7 * 16 + 0],mm4                          ; Save  [     Y73     Y72     Y71     Y70 ]
    90.                 movq        [edi + 7 * 16 + 8],mm5                          ; Save  [     Y77     Y76     Y75     Y74 ]
    91.  
    92.                 add         edi,128                                         ; Advance dst data pointer
    93.                 sub         ecx,64                                          ; Decrement loop counter
    94.                 jnz         cell_copy
    95.  
    96.                 endm
    А вот тут и возникают вопросы. Судя по потокам данных, скорость работы кода должна ограничиваться только пропускной способностью шины памяти. Для проверки этого предположения макрос был последовательно вызван в цикле для участка памяти ~12МБ. Адрес буфера приемника не менялся. Скорость обработки даных макросом составила всего 50-60% от пропускной способности памяти. Более того, комментирование цикла предвыборки несколько ухудшает общее быстродействие, но очень незначительно. Комментирование цикла обработки с функционирующим циклом предвыборки также не приводит к значительному увеличению скорости.

    Где же грабли? Чувствую, что происходит cache-trashing, но где он берется и как бы его пофиксить - не понимаю.
     
  2. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    А ты на сколько % расчитывал ? Если вх.и вых.данные находятся в кэше, то у тебя сама обработка выполняется ~4000 тактов. Если входные данные не в кэше то к этому добавляется еще примерно столько же, точнее > или ~FrameBlkSize*Fcpu/(Fram*8) тиков - зависит от соотношения частот ОЗУ и ЦПУ. Если и выходной буфер не в L2, то еще столько же или несколько меньше. Ну а если еще и страницы не инициализированы, то сам понимаешь ;)
     
  3. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Ну я рассчитывал на полную входную пропускную способность по шине памяти. Иными словами, 720 * 288 = 207360 - размер одного фрейма, тогда 3200 / 0.207360 ~ 15400 фреймов в секунду.

    На практике данный подход находит свое подтверждение в алгоритме копирования. При копировании я зачитываю в L1 кэш 4кБ даных при помощи префетч-цикла, а далее, собственно выполняю копирование с non-temporal stores. По результатам тестирования общая производительность составляет ~1.55ГБ/с - умножая эту цифру на 2 получаем ~3.1ГБ/с > 96% от теоретически возможной пропускной способности шины памяти.

    Тоже самое хотелось получить и при вышеприведенной обработке. Поскольку приемник просто жестко должен сидеть в L2 кэше - ну больше некуда ему деваться - слишком уж часто я к нему обращаюсь ;) а входные данные я постоянно подчитываю циклом предвыборки, то я полагаю, что скорость обработки должна стремиться к вышеозначенным 15400 фреймам в секунду - я где-то не прав? На практике получается всего лишь 8200-8400 - вот и возникает вопрос - где же грабли? Система ведет себя так, как если бы она постоянно сбрасывала содержимое L2 кэша в память или перечитывала исходный фрейм по два раза. Сбрасывать L2 кэш в память процессору смысла нет - его об этом не просят, да и перечитывать исходный фрейм по два раза не должен - 5760 последовательных байт заведомо меньше размеров L1 кэша любого современного процессора и начало буффера не должно вытесняться его окончанием. Я где то ошибаюсь?
     
  4. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    v_mirgorodsky
    Во-первых, определись с цифрами, а то сначала речь шла о изображении 720*8, теперь уже 720*288. Каков размер CellBuffer - 780*8*2 или сколько ? Память насколько я понял PC3200 (DDR400), а частота CPU - ?

    Во-вторых, я уже пытался пояснить, но ты похоже не слушаешь. С какой стати "скорость обработки должна стремиться к вышеозначенным 15400 фреймам в секунду" ? За это время у тебя только префетч выполняется, а время самой обработки-перетасовки ты не учитываешь ? А ведь оно на частоте <~3ГГц сравнимо с временем префетча - вот у тебя и получается ~50% (это при условии, что приемник в кэше). Или ты думаешь, что префетч и обработка могут чудным образом праллелиться ?
    PS: Приведу свои цифры для P4 3.2ГГц DDR400, теоретически пропускная способность памяти = 3.2/3.2 = 1 байт за такт, т.е. блок 720*8 должен грузиться ~5760 тиков. На деле так и получается - один префетч без обработки занимает ~5.5-6.0 тыс. тиков. Одна обработка, когда источник и приемник в кэше, занимает ~4 тыс. тиков (< 6 тиков на qword). Ну а в сумме ес-но ~9-10 тыс. когда приемник в кэше и 15-16 тыс. когда не в кэше. Чего тут непонятного ?
     
  5. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Изображение действительно 720*288, обрабатывается блоками по 720*8*2, т.к. каждый байт исходного изображения преобразуется к знаковому слову. В каждом изображении 36 блоков по 8 строк. Память действительно DDR400, процессор P4 Prescott, 3GHz. Если учитывать только обработку, то мой процессор в состоянии "перекидать" что-то в районе ~21000 фреймов в секунду ;) Если учитывать только подсистему памяти, то при условии нахождения CellBuffer'а в L2 кэше должно получиться 15400 фреймов в секунду. Таким образом имеем в качестве "узкого" места подсистему памяти. Далее, вышеозначенный макрос вызываем следующим образом:
    Код (Text):
    1. m_frame_2_cell_mmx CellBuffer,(FrameBuffer + 0 * 5760),5760,720,64               ; M0
    2. m_frame_2_cell_mmx CellBuffer,(FrameBuffer + 1 * 5760),5760,720,64               ; M1
    3. m_frame_2_cell_mmx CellBuffer,(FrameBuffer + 2 * 5760),5760,720,64               ; M2
    4. ...
    5. m_frame_2_cell_mmx CellBuffer,(FrameBuffer + 35 * 5760),5760,720,64              ; M35
    Теперь, собственно, основная идея перекрытия обработки и префетча. Пусть на данный момент выполняется cell_prefetch - он имеет огромные дыры в своей работе, поскольку его итерация занимает несколько тактов, тогда как подчитка даных из памяти занимает гораздо больше времени. Цикл cell_copy независим от результатов работы cell_prefetch - ну не знаю, что может помешать им перекрыться :-\

    Подобную технику обсуждает AMD в приаттаченном файле, подобной же техникой пользуется оптимизированный memcpy() от самого Интела. Вот и вопрос - если работает у них, то почему не работает у меня? С начала я думал, что построчная работа в пределах блока изображения сбивает префетчеры и вытесняет данные из кэша, но потом переписал макрос в режиме построчной работы и никакого выигрыша не получил.
     
  6. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Собственно, аттач - глючит форум, аттач не цепляется. Сейчас выложу на рапиду, а здесь дам линк.

    http://rapidshare.com/files/7621975/AMD_block_prefetch_paper.pdf

    BTW, нечто подобное, на похожую тему есть и в аппнотах от Интела. Сейчас просто не вспомню номера аппнота, но и там они говорят о перекрытии циклов предвыборки и циклов обработки. Иначе в чем же был бы смысл цикла предвыборки?
     
  7. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    v_mirgorodsky
    Мда, похоже уроки по планированию инструкций не пошли на пользу ;))
    Им помешает перекрыться блокировка конвеера из-за пресловутых resource constraints - ограниченного числа буферов чтения, объема ROB и очередей планировщиков. Если префетч осуществляется линейками по 64 байта, то на 720*8 байт приходится 90 чтений = 45 циклов по 5 инструкций, итого 225 мопов. В P4 объем ROB составляет 128 мопов, причем мопов чтения из них м.б.только 48 = количеству буферов чтения (при вкл.НТ все ес-но делится пополам). Вот цитата из IA-32 (для тех кто не утруждает себя изучением первоисточников и наивно верит в чудесный неограниченный конвеер ;)
    Т.к. буферов вдвое меньше, чем нужно для цикла префетча, то во время его работы периодически происходят блокировки, "он имеет огромные дыры в своей работе", но во время этих дыр процессор просто ждет загрузки данных, ухода в отставку выполненных мопов и освобождения ресурсов для новой партии мопов из Т-кэша. Повторю прописные истины: мопы поступают в ROB строго последовательно и сидят в нем пока не уйдут в отставку, отставка тоже идет строго последовательно, т.е. lea\cmp\jcc не уйдут пока не выполнятся предыдущие mov, а они будут сидеть до тех пор пока данные не поступят из ОЗУ. Если все load-буферы заняты, то поступление новых мопов в ROB блокируется (не только мопов чтения, а вообще всех). Когда наконец придут данные для двух последовательных mov, они будут помечены как выполненные и все мопы одной итерации за пару тактов уйдут в отставку и освободят буферы чтения и место в ROB для еще одной итерации. Уже отсюда следует, что мопы первой итерации цикла cell_copy даже в ROB не смогут попасть, пока не выполнится по крайней мере половина цикла cell_prefetch.
    На самом деле ситуация еще хуже, т.к. кроме буферов чтения есть еще более жесткое ограничение на число ожидающих кэш-промахов L1 (DCU) и на глубину очереди MEM-планировщика:
    В переводе на русский это означает, что в цикле префетча мувы не только забивают все свободные буферы чтения и ROB, но и из планировщика выходят на исполнение не за пару тактов, как ты думаешь, а через интервал равный времени загрузки линейки кэша из ОЗУ (первые 4 или 8 проскакивают быстро, а следующие получают отказ, ждут освобождения соотв.буфера L1 и дальше выходят из планировщика по однму по мере поступления данных из ОЗУ). Окно МЕМ-планировщика в P4 младших моделей составляет всего 8 мопов, для старших может и больше, но не значительно. Поэтому если даже мопы mov цикла cell_copy и попадут в ROB где-то на середине цикла префетча, но на исполнение они смогут попасть только в конце этого цикла, когда попадут в планировщик (т.к.загрузка мопов из ROB в планировщик идет последовательно). Поэтому в лучшем случае их исполнение может начаться за 8-1=7 мопов mov до конца префетча, а это всего лишь 7*64 ~ 450 байт или ~8% от общего времени загрузки 720*8 байт.

    Выводы:
    1) Циклы cell_prefetch и cell_copy параллелиться не могут и выполняются практически последовательно с макс.перекрытием < 10%. Поэтому время обработки примерно равно их сумме и никаких подводных камней и экзотических объяснений тут искать не нужно ;)
    2) Не стоит пренебрегать первоисточниками и уже пройденным материалом, чтобы не наступать на одни и теже грабли по нескольку раз и не искать несуществующих черных кошек в темных комнатах ;)))))

    Уф-ф, устал... Поэтому о действительном смысле блок-префетча как-нибудь потом ;)
     
  8. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    leo
    Спасибо за пояснения. Да, MEM-планировщик - о нем я читал, но налагаемые ним ограничения на выполняемый код как-то выпали из головы :dntknw:

    Хорошо, тогда как все же перекрыть загрузку данных из ОЗУ и выполнение операций распаковки? Я пробовал заменить мовы в префетч цикле на prefetchnta - ничего кардинально не поменялось. Пробовал так же ходить подряд по всем строкам исходного буфера и предвыбирать prefetchnta за 256 байт от того места с которым я работаю - не помогает.

    Самым большим разочарованием стал встроенный аппаратный префетчер процессора. В режиме работы по строкам - как бы все нормально, но скорость все равно кардинально не растет. Ну с ним-то я выполнил все условия его включения - access pattern - линейный в сторону возрастания адресов, даные читаются подряд, без дырок и прыжков, во время обработки данных однозначно происходит "two successive cache misses" - значит он должен был бы включиться, а значит должно было произойти перекрытие операций загрузки из памяти и выполнения.

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

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Ну что же, вопрос о истинном смысле блок-префетча так и остался без ответа. Господин leo либо забыл о своем обещании ответить на него, либо не знает ответа :o) Ну что, придется мне, как начавшему эту нить ответить на свой же вопрос ;)

    Понимание истинного смысла работы блок-префетча лежит в плоскости понимания алгоритмов функционирования микросхем динамической памяти. Современная динамическая память организована на чипах с четырех банковой архитектурой. В пределах каждого банка может быть активирована всего одна строка. Перед работой со строкой ее необходимо активировать, после окончания работы со строкой ее необходимо деактивировать. Как один, так и второй процесс требует времени, специфицированного производителем конкретной микросхемы памяти. Длинна активной строки зависит от типа и объема микросхемы. Максимальный объем строки составляет всего 2048 ячеек. Т.е. для стандартного дима с разрядностью 64 бита получаем прямой доступ всего к 32kB памяти в пределах одной активной строки, или к 128kB в пределах одного дима. Очевидно, что при объеме дима в 512MB окно непосредственно адресуемой памяти очень незначительно. Активные строки в пределах банка могут активироваться и деактивироваться параллельно с чтением/записью ячеек в других банках. Таким образом, производительность шины памяти очень зависит от последовательности операций и от паттерна доступа к памяти. DDR400 в теории позволяет получить около 3200MB/s пропускной способности, однако достижима она только при линейном способе доступа к памяти, когда активация и деактивация следующей строки "прячется" во время работы с текущей.

    Теперь о блок-префетче. Как обычно циклы блок-префетча построены очень линейным образом. Их задача поднять в кэш первого или второго уровня данные из системной памяти на максимальной скорости. Далее процессор начинает их пересортировывать/обрабатывать в том порядке, как это предусмотрено программой. Фишка в том, что кэш сам по себе является статической памятью и практически не имеет ограничений на паттерны доступа к данным. Таким образом, единственным предназначением циклов блок-префетча является увеличение длинны последовательных данных при работе с системной памятью. Соответственно и выигрыш от их применения может быть очень разным.

    P.S. При проектировании собственной подсистемы памяти я обтыкиваю контроллер памяти разнообразнейшими фифо для увеличения количества подряд идущих данных на одну транзакцию. В то же время, пытаясь писать высокопроизводительные процедуры обработки данных на компьютер я начисто забываю о таких "простых" железячных вопросах ;) Такой вот феномен ;)
     
  10. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    v_mirgorodsky
    Извини, времени не было, хотя вопрос в общем-то простой и видимо нужно было сразу "послать тебя" к IA-32 Optim и книжке Касперски "чего-то там: Эффективное использование памяти" (Code Optimization: Effective Memory Usage)

    Общий вывод об "увеличении длинны последовательных данных" ты делаешь правильный, но вот объяснить пытаешься частными "фишками", имеющими лишь косвенное отношение к делу ;) А с общих позиций это обясняется просто различием понятий латентности и пропускной способности, которые применимы ко всем устройствам современных процессоров. Возьми например операцию imul - ее латентность на разных процах может составлять от 3 до 10-14 тактов, но за счет буферизации\конвееризации (pipelining) независимые imul могут выполняться в каждом такте, т.е. для одной imul ты получишь результат через, скажем 4 такта, а для серии из n операций всего за 3+n тактов - чем больше n, тем меньше влияет латентность на общее время выполнения. Тоже самое относится и к загрузке данных из кэша - общая латентность mov r,m складывается из 1 такта вычисления адреса плюс 2-4 такта латентность доступа к L1, а случае промаха плюс еще 7-18 тактов латентность L2. Но за счет буферизации независимые mov могут выполняться на пеньках в каждом такте, а в атлонах аж по две за такт. Разумеется аналогичную картину мы имеем и при доступе к ОЗУ - при промахе L2 формируется запрос к ОЗУ и к указанной латентности добавляются задержки формирования запроса, арбитража шины, передачи запроса и его обработки в чипсете\контроллере памяти и т.д. и т.п. (подробности см. у Касперски). Для примера в IA-32 приводятся цифры для P4: 12 тактов CPU + 6-12 тактов FSB, а в качестве ориентира при расчете расстояния префетча берется значение латентности запроса ~60 тактов CPU. По сравнению с этой цифрой задержки активации строки DRAM (RAS precharge, RAS-ToCAS delay) мягко говоря не выглядят доминирующими, а реально их вклад при последовательном доступе может быть вообще незначительным, т.к. строку совершенно не обязательно закрывать после каждого запроса и она может оставаться открытой достаточно долгое время (тут все зависит от "умности\хитрости" контроллера памяти). Вывод: задача любого префетча - заранее формировать запросы доступа к памяти, чтобы латентность его обработки скрывалась за счет буферизации во время обработки предыдущего запроса и\или во время передачи предыдущего блока данных. Если запросы формируются заблаговременно, то данные поступают из ОЗУ практически непрерывно без "дыр\пузырей" и тем самым достигается максимальная средняя скорость передачи.
    А различие между "эффективностью" обычного чтения и блок-префетча объясняется ограниченными ресурсами процессора, рассмотренными выше. Если не брать в расчет хардварный префетч (который кстати появился только в старших моделях PIII и К7), то при обычном чтении мы пытаемся многократно обращаться к одной и той же отсутствующей линейке кэша, при этом очереди ожидающих мопов быстро переполняются, конвеер останавливается и процессор просто "не видит" последующих мопов чтения и ес-но не может сформировать запрос следующей линейки кэша. В результате запросы на чтение линеек формируются последовательно или с небольшим перекрытием, образуя "дыры" в потоке передачи данных. А "фишка" блок-префетча заключается в том, что во-первых, данные читаются в кэш в отдельном цикле (меньше мопов, меньше ограничений ресурсов) и второе, самое главное, производится по одному чтению для каждой линейки кэша. В результате до момента переполнения очереди процессор "видит" обращения к нескольким линейкам (4 или 8 = кол-ву поддерживаемых outstandig misses и line-fill buffers) и может формировать запросы к памяти с нужным упреждением. После переполнения по мере прихода данных один моп mov выходит из очереди и его место занимает другой, но за счет очереди в 3 или 7 предыдущих запросов у процессора остается достаточно времени для упреждающего формирования нового запроса. В итоге латентность обработки запросов "прячется" во время передачи данных и тем самым обеспечивается максимальная пропускная способность.

    PS: В современных процессорах преимущества блок-префетча (также как и софтварного prefetchXXX) при однопоточном последовательном чтении без копирования нивелируются хардварным префетчем, который должен заблаговременно запрашивать данные из ОЗУ с определенным упреждением (в P4 256 байт = на 4 линейки вперед относительно обрабатываемых данных). Поэтому основным применением блок-префетча является копирование больших блоков памяти, т.к. тут он решает еще одну задачу - устраняет проблему конкурирующих запросов на чтение и запись в память