Стратегия распределения данных по кэш-банкам
В выравнивании данных есть еще один далеко неочевидный момент, по непонятным обстоятельствам, упущенный составителями оригинальных руководств по оптимизации под процессоры Pentium и AMD, а потому практически не известный программистской общественности.
Руководство по оптимизации под Pentium MMX – Pentium-II (Order Number 242816-003) содержало лишь следующую скудную информацию: "The data cache consists of eight banks interleaved on four-byte boundaries. On Pentium processors with MMX technology, the data cache can be accessed simultaneously from both pipes, as long as the references are to different cache banks. On the P6-family processors, the data cache can be accessed simultaneously by a load instruction and a store instruction, as long as the references are to different cache banks….
…If both instructions access the same data-cache memory bank then the second request (V-pipe) must wait for the first request to complete. A bank conflict occurs when bits 2 through 4 are the same in the two physical addresses. A bank conflict incurs a one clock penalty on the V-pipe instruction"
("Кэш данных состоит из восьми банков, чередующихся по четырех байтовым адресам. Кэш данных процессоров Pentium MMX одновременно доступен с обоих конвейеров при условии, что они обращаются к различным кэш-банкам. На процессорах семейства P6 (Pentium Pro, Pentium-II), кэш данных доступен и на чтение, и на запись, при условии, что обращение происходит к различным кэш-банкам…
…если обе инструкции [речь идет о спариваемых инструкциях – КК] обращаются к одному и тому же банку кэш-памяти, следующей запрос (V-труба) будет вынужден дожидаться завершения выполнения предыдущего. Конфликт банков происходит всякий раз, когда биты со второго по четвертый в двух физических адресах совпадают. Конфликт банков возлагает штрафную задержку в один такт, задерживающую выполнение инструкции находящейся в V-трубе"
В руководстве оптимизации под P-III второй абзац загадочным образом исчезает.
Но это еще что, – "Intel Pentium 4 Processor Optimization Reference Manual P-4" о кэш-банках вообще не обмолвливается ни словом! Ничуть не разговорчивее оказывается и "AMD Athlon Processor x86 Code Optimization Guide", уделяющее этому вопросу едва ли не дюжину слов: "The data cache and instruction cache are both two-way set-associative and 64-Kbytes in size. It is divided into 8 banks where each bank is 8 bytes wide" ("Кэш данных и кэш инструкций двух ассоциативны и имеют размер по 64 Кб каждый. Они поделены на 8 банков, шириной по 8 байт"). Понять последнее предложение может только тот, кто хорошо знаком с архитектурой расслоенной памяти и хотя бы в общих чертах представляет себе как на аппаратном уровне устроен и работает кэш. К тому же возникает досадная терминологическая путаница: разновидностей кэш-банков насчитывается по меньшей мере две.
Ассоциативный кэш делится на независимые области, называемые банками, число которых и определяет его ассоциативность. На физическом уровне, эти банки состоят из нескольких матриц статической памяти, так же именуемых банками. Расслоение памяти подробно разбиралось на страницах данной книги (см. "Часть I. Оперативная память. Устройство и принципы функционирования оперативной памяти. SDRAM (Synchronous DRAM) – синхронная DRAM") и внимательным читателям навряд ли стоило большого труда догадаться какой именно "банк" составители руководства имели ввиду. Да! Но насколько хреново приходится тем, кто только начинает изучать программирование!
А ведь когда-то фирма AMD славилась качеством совей документации. Откроем, например, замечательное руководство "AMD-K5 Processor Technical Reference Manual", которое я частенько перелистываю перед сном, поскольку это гораздо больше, чем просто руководство по безнадежно устаревшему процессору. Это – исчерпывающее описание архитектуры, к которой вплоть до последних времен не добавилось ничего революционно нового.
Даже супер современный Hammer основан на тех же самых принципах и почти том же самом ядре.
В частности, организация и назначение кэш-банков объясняются так: "The data cache overcomes load/store bottlenecks by supporting simultaneous accesses to two lines in a single clock, if the lines are in separate banks. Each of the four cache banks contains eight bytes, or one-fourth of a 32-byte cache line. They are interleaved on a four-byte boundary. One instruction can be accessing bank 0 (bytes 0-3 and 16-19), while another instruction is accessing bank 1, 2, or 3 (bytes 4-7 and 20-23, 8-11 and 24-27, and 12-15 and 28-31 respectively)".
("Кэш данных преодолевает заторы чтения/записи путем поддержки возможности одновременной записи двух кэш-линеек за один такт, при условии, что эти линейки расположены в различных банках. Каждый из четырех кэш-банков состоит из восьми байтов, или другими словами говоря, одной четвертной длины 32?байтной кэш-линейки. Они (банки) чередуются с четырех байтовым диапазоном. Одна инструкция может обращаться к банку 0 (байты 0-3 и 16-19), в то время как другая инструкция может параллельно обращаться к банку 1, 2 или 3 (байты 4 – 7 и 20 – 23, 8 – 11, и 24 – 27, и 12 – 15, и 28 – 31 соответственно").
Вот теперь все более или менее ясно. Остается лишь вопрос: а для чего такие извращения? Ответ: реализация двух портовой матрицы статической памяти обходится дорого, т.к. требует для своего создания восьми CMOS-транзисторов вместо шести. Поэтому, конструкторы поступили проще: разбили статическую память на несколько независимых банков и подцепили к ней двух портовый интерфейс. Таким образом, на 64 Кб кэше экономится порядка миллиона транзисторов, правда временами такая экономия оборачивается дорогой ценой, – ведь двух портовое ядро памяти способно одновременно обрабатывать два любых запроса, а кэш с двух портовым интерфейсом может распараллеливать только те запросы, которые направляются в различные банки.
Итак, для достижения наивысшей скорости обработки данных, мы должны соблюдать ряд определенных предписаний и планировать поток данных с таким расчетом, чтобы не возникало паразитных задержек за счет по парного обращения к одним и тем же кэш-банкам.
Рисунок 27 0х021 Схема проецирования матриц кэш-памяти на кэш-линейки
Итак, кэш-линейка не представляет собой изотропное целое, а состоит их четырех или восьми независимых 32-, 64- или 128-битных банков (см. рис 0х021). Их независимость выражается в том, что чтение/запись в каждый из банков может происходить параллельно в течение одного такта процессора. Степень параллелизма зависит от количества функциональных устройств, подцепленных к исполнительным конвейерам микропроцессора и количества портов самого кэша. В частности, микропроцессоры P-II могут выполнить одну запись и одну чтение двух различных банков за каждый такт. Более подробные сведения об особенностях реализации кэш-банках в популярных моделях процессоров можно подчеркнуть из таблицы….
Таким образом, если у нас имеются две 32-битовых переменных, каждая из которых расположена в "своем" банке, операция присвоения одной переменной другой может быть выполнена всего за один такт! Напротив, если переменные пересекают границы банков – как показано на рис. 0х022 – возникает задержка: процессор не может писать в тот банк, который в данный момент обрабатывает запрос на чтение. Величина задержки варьируется в зависимости от модели процессора, например, на P-II составляет пять тактов.
Но вернемся к нашим баранам (оптимальной стратегии выравнивания данных). В свете новых воззрений, все данные (включая переменные размером в байт) лучше располагать по адресам кратным по меньшей мере четырем, тем самым обеспечивая возможность их параллельной обработки, т.к. каждая переменная будет "монопольно" владеть соответствующим ей банком. Правда, помимо собственно самого выравнивания еще потребуется убедиться, что биты, "ответственные" за смещение данных в кэш-линейке у параллельно обрабатываемых ячеек не равны, иначе они с неизбежностью попадут в одну и ту же матрицу статической памяти, хотя и будут находиться в различных линейках кэша. (Замечание: данное ограничение не распространяется на операцию чтения, последующую за записью, – в этом случае записываемые данные направляются в буфер записи и к кэш-памяти происходит только одно обращение, да и то, лишь когда считываемых данных не окажется в буфере, – подробнее см.
"Буфера записи").
С другой стороны: такое выравнивание приводит к "разрыхлению" упаковки данных и требует значительного большего количества памяти, в результате чего вполне может статься так, что данные просто не влезут в кэш первого (а то и второго) уровня. Тем самым мы рискуем вместо ожидаемого увеличения скорости нарваться на большие тормоза, съедающие весь выигрыш параллельной обработки!
Рисунок 28 0х022 Чтение/запись ячеек, расположенных в различных кэш-банках (т.е. в различных матрицах статической памяти) осуществляется за один такт. В противном случае, каждая переменная будет обрабатываться последовательно, что потребует вдвое больше тактов.
Насколько значительными будут последствия конфликта кэш-банков? А вот сейчас и увидим! Чтобы выяснить это мы напишем следующую программу, учитывая при ее проектировании следующие обстоятельства:
а) на P-III конфликт кэш-банков приводит к падению производительности только
в случае комбинирования операций чтения с операциями записи (т.е. на P-III всего одно устройство чтения, загрузить две ячейки за такт даже из двух различных банков он увы не сможет);
б) цикл обработки памяти должен быть развернут минимум на четыре итерации, т.к. в противном случае буферизация записи позволит переждать задержки, вызванные конфликтом банков и отложить выгрузку данных "до лучших времен", а единственной инструкции записи просто будет не с чем спариваться!
Хорошо! Давайте же вызовем джина из бутыли. "Ало, джин ибн Конфликт Кэш Банков" появись!" Как вы думаете, он появится?
//============================================================================
// НЕТ КОНФЛИКТОВ
//----------------------------------------------------------------------------
// Распределение переменных по кэш-банкам на P-III
// ===============================================
// !<bank0>!<bank1>!<bank2>!<bank3>!<bank4>!<bank5>!<bank6>!<bank7>!
// !0 1 2 3!4 5 6 7!8 9 0 1!2 3 4 5!6 7 8 9!0 1 2 3!4 5 6 7!8 9 0 1!<- offset
// !-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!
// !*-*-*-*! ! ! ! ! ! <<-- ((int)_p32 + a + 0);
// ! !*-*-*-*! ! ! ! ! <<-- ((int)_p32 + a + 4);
// ! ! ! !*-*-*-*! ! ! <<-- ((int)_p32 + a +12);
// ! ! ! ! !*-*-*-*! ! <<-- ((int)_p32 + a +16);
//============================================================================
//
// Распределение переменных по кэш-банкам на AMD Athlon
// ====================================================
// !<-- bank 0 -->!<-- bank 1 -->!<-- bank 2 -->!<-- bank 3 -->!...
// !0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 ...
// !-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!-!...
// !*-*-*-* ! ! ! <<-- ((int)_p32 + a + 2);
// ! *-*-*-*! ! ! <<-- ((int)_p32 + a + 6);
// ! ! *-*-*-*! ! <<-- ((int)_p32 + a +12);
// ! ! !*-*-*-* ! <<-- ((int)_p32 + a +16);
//============================================================================
optimize(int *_p32)
{
int a;
int _tmp32 = 0;
for(a = 0; a < BLOCK_SIZE; a += 32)
{
_tmp32 += *(int *)((int)_p32 + a + 0); // bank 0 [Athlon: bank 0]
*(int *)((int)_p32 + a +12) = _tmp32; // bank 3 [Athlon: bank 1]
_tmp32 += *(int *)((int)_p32 + a + 4); // bank 1 [Athlon: bank 0]
*(int *)((int)_p32 + a +16) = _tmp32; // bank 4 [Athlon: bank 2]
}
}
//============================================================================
// ДЕМОНСТРАЦИЯ КОНФЛИКТА БАНКОВ
//----------------------------------------------------------------------------
// Распределение переменных по кэш-банкам на P-III
// ===============================================
// !<bank0>!<bank1>!<bank2>!<bank3>!<bank4>!<bank5>!<bank6>!<bank7>!
// !0 1 2 3!4 5 6 7!8 9 0 1!2 3 4 5!6 7 8 9!0 1 2 3!4 5 6 7! 8 9 0 1 <- offset
// !-+-+-+-+-+-+-+-!-+-+-+-+-+-+-+-!-+-+-+-+-+-+-+-!-+-+-+-+-+-+-+-
// ! *-*-*-* ! ! ! ! ! <<-- ((int)_p32 + a + 2);
// ! !^ *-*-*-* ! ! ! ! <<-- ((int)_p32 + a + 6);
// ! !| !^ !*-*-*-*! ! ! <<-- ((int)_p32 + a +12);
// ! !| !| ! !*-*-*-*! ! <<-- ((int)_p32 + a +16);
// | |
// +-------+--- <- КОНФЛИКТ
//============================================================================
//
// Распределение переменных по кэш-банкам на AMD Athlon
// ====================================================
// !<-- bank 0 -->!<-- bank 1 -->!<-- bank 2 -->!<-- bank 3 -->!
// !0 1 2 3 4 5 6 7!8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
// !-+-+-+-+-+-+-+-!-+-+-+-+-+-+-+-!-+-+-+-+-+-+-+-!-+-+-+-+-+-+-+-+
// ! *-*-*-* ! ! ! <<-- ((int)_p32 + a + 2);
// ! *-*-*-* ! ! <<-- ((int)_p32 + a + 6);
// ! ^ *-*-*-*! ! <<-- ((int)_p32 + a +12);
// ! | !*-*-*-* ! <<-- ((int)_p32 + a +16);
// ! КОНФЛИКТ ! !
//
//============================================================================
conflict(int *_p32)
{
int a;
int _tmp32 = 0;
for(a = 0; a < BLOCK_SIZE; a += 32)
{
_tmp32 += *(int *)((int)_p32+a+2); // bank 0 + 1 [Athlon: bank 0]
*(int *)((int)_p32+a+12) = _tmp32; // bank 3 * [Athlon: bank 1]
// *
// "*" MARK BANKS CONFLICT
// * *
_tmp32 += *(int *)((int)_p32+a+6); // bank 1 + 2 [Athlon: bank 0 + 1]
*(int *)((int)_p32+a+16) = _tmp32; // bank 4 [Athlon: bank 2]
}
}
Листинг 6 [Cache/banks.c] Демонстрация последствий конфликта кэш-банков
На P-III "джин" появляется, да какой джин (см. рис. graph 0x008)! Чтением двух смежных 32- разрядных ячеек, смещенных относительно начала первого банка на 16 бит, мы вызвали более чем трех кратное падение производительности, что и неудивительно, т.к. в этом случае чтение двух ячеек происходит не за два такта как это должно быть, а за 2 + penalty
тактов. Поскольку на P-III величина пенальти составляет пять тактов, мы проигрываем = 350%, что вполне близко к экспериментальному значению – 320% (завышенная оценка объясняется тем, что мы не учли накладных расходов на запись и организацию цикла).
На AMD Athlon последствия конфликта кэш-банков оказались гораздо меньшими, всего на 9% увеличив время выполнения программы. Такое преимущество над P-III объясняется тем, что благодаря двойному превосходству в ширине кэш-банков, мы перекрыли всего лишь два из них и вместо полного затора (как на P-III) на Athlon'e образовалась лишь маленькая, быстро рассасывающая пробка. Разумеется, это отнюдь не означает, что на AMD Athlon вызвать затор невозможно, – возможно, еще как! Достаточно добиться перекрытия сразу нескольких банков, но для этого понадобится совсем другая программа, которая окажется непригодной для тестирования P-III. Тем не менее, вероятность спонтанного конфликта кэш-банков на AMD Athlon все-таки ниже.
Рисунок 29 graph 0x008 Демонстрация конфликта кэш-банков на P-III и AMD Athlon
