Мое почтение всем. Читаю сейчас про работу кэша, есть несколько вопросов. В 486 длина строки кэша 16 байт, кэш содержит 4 направления, каждое направление -- 128 строк. Как я понял, младшие 4 бита выбирают конкретный DWORD в строке кэша в множестве, следующие 7 выбирают конкретное множество, верхние 21 -- конкретную строку кэша в множестве. Первый вопрос из разряда философии -- почему не сделать большее кол-во напрвлений? Ведь это, как я понял, позволит более "честно" судить последние используемые. И второй: мониторинг частоты использования ведется только для конкретного множества. Получается, что для наилучшей оптимизации при заполненности кэша я должен либо стараться поместить одновременно используемые данные в одну строку, либо стараться разнести одновременно используемые участки памяти по разным множествам (т.е. использовать для этого разные адреса, кратные 2048), а используемые по очереди стараться поместить в одно множество с используемыми одновременно. Например: mov eax, [0x0] add [0x10], eax ;Сейчас значение по адресу [0x10] в кэшэ, возможно, было перезаписано предыдущей операцией. mov eax, [0x0] add [0x2048], eax ;А сейчас лучше -- значения находятся в разных множествах. Если это все так, то знают ли об этом компиляторы? Или выигрышь будет настолько мал, что нет смысла задумываться об этом? Если этот бред неясен -- скажите, просто у меня пока не получается точнее сформулировать...
Тут скорее вопрос про дискресное считывание в кэш кода и данных. Когда эти аромарные считывания складываются в кэш-лайн это есть гуд. Директива ALIGN n этим и занимается, что подгоняет под красные адреса, в коде же это как раз то что надо для интенсивны циклов, чтобы не засирать кэш не плодить разные линии кода/данных да в цикле ещё. Если код цикла умещается в 1 линию то это ещё лучше чем унролить цикл! Доказано,сам видел
asmfan Кстати, а как это работает с данными? Я имею ввиду, почему тормоза? EvilsInterrupt Григорьев вперемешку с мануалами от Интел.
Ну надо, к примеру, OWORD (XMMWORD) зачесть, а он находится не по адресу с какого заполняется кэш-линия, а со смещением от начала. Знач. нада процу 2 раза счесть. Короче говоря, данные лежат на пересечении 2х кэш-линий (более толково не могу сказать Посмотри описание команд считывания вырваных и нет данных. И ещё 1й команды загрузки невыравненых данных из SSE3 ld** (не помню) она как раз для таких случаев как описал выше. Там много понятнее...
Mika0x65 Из соображений быстродействия и целесообразности Учти, что для выбора одного из 4-х направлений процессор должен одновременно считать из кэша 4 тега по N бит и сравнить их с соответствующими N старшими битами запрашиваемого адреса, для 8-way ес-но вдвое больше. Разумеется это нетривиальная задача, особенно на больших частотах (да еще с учетом размера физ.адреса > 32 бит в PAE36 и EM64). Поэтому быстрый L1 обычно имеет ассоциативность 2 (в AMD) или 4, максимум 8 (самый тормозной кэш P4E) , а "медленный", но более объемный L2 4-8-16. И по логике использования L1 и L2 это оправдано. L1 работат с ограниченным объемом данных (или кода) одного потока, поэтому 4-х направлений (множеств адресов) для него вполне достаточно (AMD вообще считают, что и 2-х хватает . А универсальный L2 может работать помедленнее, но должен вмещать побольше кода и данных (возможно разных потоков), поэтому и ассоциативность у него должна быть побольше. Что касается оптимизации размещения данных в кэше, то этой "фигней" имеет смысл заниматься только при одновременной обработке нескольких массивов (матриц). Эти вопросы затрагиваются, например, в книге К.Касперски - чего-то там про эффективное использование памяти (где-то на форуме должна быть ссылка на его ftp). А твои примеры с [0x10] и [0x2048], во-первых, сами по себе не очень понятны (с какой стати адрес 0x10 может быть вытесен, а 2048 "уже лучше"). Во-вторых, проблема быстродействия обращения к TLB, кэшу и store-to-load буферу действительно серьезная, поэтому в процессорах могут использоваться дополнительные хитрости типа предварительной проверки hit\miss по мини-тегу (сокращенному числу разрядов) и соответственно могут быть "нехорошие" кратности адресов типа 64К в P4 (модели <= 2) или 4К в P6, при которых процессор может ошибаться при предварительной проверке с соответствующими пенальти
Что значит самый тормозной? Т.е. данные из него извлекаются не по первому требованию? Да, в примерах совсем плохо... Что хотел сказать: если мне требуется одновременно иметь два значения в кэше при его заполненности, то, как я понимаю, нужно либо держать эти данные в одной строке, либо в разных множествах. Т.е. примерно так: младшие четыре бита содержат 0 -- т.е. в строку кэша они не попадут (длина строки -- 16), а след. семь бит содержат 0 и 1, т.е. они попадают в разные множества. Тогда, когда в кэш попадает первое значнение, а за ним второе -- второе гарантированно не вытеснит первое. (Когда написал, задался вопросом: какой приоритет будет у вновь заполненной строки? Если выше, чем у всех остальных в множестве, что скорее всего, то такая разноска совсем не нужна...) В общем, примерно такая картина получается (у меня в голове): 1. Большое кол-во ассоциаций (кстати, а почему ассоциацитвное?) в множестве, тем "честнее" проходит арбитраж "кого выгнать", но это бьет по скорости. 2. Если сильно вложиться в ассоциативность, то труднее разносить данные по множествам (если все же потребуется держать их в разных). P.S. А как называется книга?
Сравни задержки, 3 для Л1 или 11 тактов для Л2. Типичная ассоциативность у Л1 2-4 (у конро 8?), у Л2 - 8-16. Теперь разберемся. Кэш работает по принципу прямого отображения (ему некогда данные искать он должен доставать их мгновенно), т.е. кэш содержит: 1. Строки кэша - сами данные. Размер обычно 16-64 байта. 2. Тэг кэша (часть адреса) для каждой строки кэша. Разберем как происходит обращение по адресу, допустим адрес XXXXYYZZ (256 байт = строка, 256 строк = кэш (64КБ), кэшируемое пространство 4ГБ). ZZ - адрес внутри строки кэша. YY - номер строки кэша, которая может хранить искомые данные. Отсюда видно, что данные расположенные на расстоянии размера кэша YYZZ не могут быть одновременно закэшированы. XXXX - должно быть равно тэгу этой строки. Логика: --- if (cache_tag[YY] == XXXX) data = cache_data[YY][ZZ]; // работа кэша else { data = memory_read(XXXXYYZZ); // чтение данных из памяти // после того как данные ушли, можно обновить кэш load_string(cache_data[YY], XXXXYY00); cache_tag[YY] = XXXX; } --- Многоассоциативный кэш это фактически несколько кэшей. Например, 64КБ 16-напр. это 16 кэшей по 4КБ. Приемущество его в том, что может быть закэшировано несколько строк на адресах кратных размеру кэша, и хотя фатически размер кэша стал меньше (в 16 раз), такой подход как минимум не хуже (не считая накладных расходов на напр.), а в 99% лучше. Накладные расходы это: 1. Увеличившееся кол-во сравнений. 2. Увеличившийся тэг. Кол-во строк в кэше не увеличилось, кол-во тэгов осталось прежним, но из-за уменьшения кэша разрядность тэга возросла. XXXXXYZZ 3. Опеределение "крайней" ассоциативности при загрузке данных в кэш. --- for (way=0; way < 16; way++) { if (cache_tag[way][Y] == XXXXX) { data = cache_data[way][Y][ZZ]; // работа кэша goto hit; } } data = memory_read(XXXXXYZZ); // чтение данных из памяти // после того как данные ушли, можно обновить кэш load_string(cache_data[obsolete_way][Y], XXXXYY00); // obsolete_way выбирается... cache_tag[obsolete_way][Y] = XXXXX; hit: ---
Три? Я просто здесь прочитал что за один. Да, это я понял. Вопрос немного в другом был: получается, что строки в одном множестве (т.е. адреса, не кратные Y) при заполненности кэша не могут гаратированно находится в кэше одновременно. Поэтому подумалось, что для максимальной производительности надо либо размещать одновременно используемые данные в одной строке, либо размещать их в разных множествах. Правда, если я правильно понял, товарищ Фог меня опередил . Кстати, меня удивляет, что, как я понял, при записи данных в память, при условии, что они были вытеснены из кэша данные сначала будут считаны в кэш, а потом записаны в память. Что не производительно. Если я не ошибся, конечно.
Процессор имеет команды для некэшируемой записи - если данные в ближайшем будущем не будут использоваться это лучшее решение. Команды movnt* (non temporal)
Mika0x65 Это throughput = 1, т.е. можно выдавать запросы на чтение в каждом такте, и соответственно данные будут приходить в каждом такте, но с задержкой latency > 1 (2-3 такта в P6, 2 в P4, 7 в P4E). Режим write allocate (или write fill) как раз используется для повышения средней производительности при работе с памятью. Кэш-линейки придуманы не только для упрощения организации кэша и синхронизации данных, но и потому что обмен с ОЗУ большими пакетами осуществляется быстрее, чем мелкими. Дело в том, что при записи мы должны гарантировать синхронизацию (непротиворечивость) данных в кэше и в ОЗУ. Если мы обмениваемся с ОЗУ только линейкаи в режиме write allocate, то при любой записи в линейку достаточно установить один единственный флаг dirty (= modified) и можно спокойно работать дальше - пока данная строка находится в кэше процессор работает только с этой модифицированной, но достоверной копией данных (т.к. запись производится поверх ранее прочитанных данных, то неважно сколько байт и в каком порядке были изменены). Если линейка вытесняется, то первым делом процессор проверяет ее флаг dirty - если данные не изменялись, то они просто выбрасываются, если изменялись, то вся линейка выгружается в ОЗУ. Теперь представь как эта кухня будет работать, если при записи не производить чтение линейки из ОЗУ. Во-первых, одним флагом не обойдешься - нужно контролировать модификацию и валидность каждого байта линейки (т.е. вместо одной пары флагов valid+dirty имеем N = размеру линейки). Во-вторых, если после записи в линейку читаются немодифицированные (и значит инвалидные) байты из этой же линейки, то по любому приходится читать данные из ОЗУ - читать отдельные байты накладно, поэтому опять приходится читать всю линейку и затем объединять по маске с модифицированными байтами. В-третьих, если линейка вытесняется и в ней лишь модифицирована часть байт, то вместо одного большого пакета записи приходится формировать фиг-знает сколько мелких пакетов записи в ОЗУ. Справедливости ради нужно заметить, что все эти 3 механизма в процессоре реализованы, но не на уровне кэша, а на уровне небольшого числа буферов чтения\записи линеек кэша. Дело в том, что при записи в отсутствующую линейку процессор выдает запрос на ее чтение из ОЗУ, но чтобы не тормозить исполнение программы, он временно помещает записываемые данные в специальные WC-буферы (write combining). Каждый буфер расчитан на одну кэш-линейку и поддерживает отслеживание всех модифицированных байтов (dirty = valid). Данные из ОЗУ тоже читаются не прямо в кэш, а в специальные line-fill буферы. Перед тем как данные из fill-буфера записываются в кэш, осуществляется проверка наличия изменений в WC-буферах и наложение данных по маске измененных байтов. Поскольку этих буферов мало (обычно 4, 6, 8 штук), то проверки и наложения реализуются просто и быстро. WC-буферы также поддерживают и 3-й механизм - частичные транзакции записи в ОЗУ. Дело в том, что эти буферы используются не только для ожидания line-fill при обычной записи, но и для накопления и объединения данных для некэшируемых записей movnt*. Если WC-буфер заполняется полностью, то и запись в ОЗУ осуществляется целиком всей линейки (т.е."быстро"), если же частично (пусть даже один байт остался не записан), то - отдельными транзакциями (т.е."медленнее"). Поэтому movnt* рекомендуется использовать при записи\копировании достаточно больших блоков памяти, чтобы гарантировать заполнение целых линеек. Опять ты за свое ) Товарищ Фог и мануалы говорят не о "максимальной производительности", а о том чего не надо делать, чтобы не снизить производительность. Козе понятно, что N-way кэш не может одновременно хранить более N линеек, с совпадающими Y. Но с другой строны механизм (псевдо) LRU гарантирует, что N последовательных записей (без промежуточных чтений более старых значений) никогда не вытеснят друг друга независимо от значений адреса. Исключением из этого правила являются только дебильные P4, у которых вообще невозможно хранить в L1 две строки с адресами, кратными 2^16 = 64К (model <= 2) или 2^22=4Мб (model >= 3). Поэтому и задумываться об "оптимальном размещении данных" приходится только в особых случаях - в основном когда работаешь одновременно с несколькими массивами (или частями одного большого массива). А тот вывод, к которому ты приходишь соответсвует обычной практике локализации размещения данных - как идут они у тебя последовательно по нарастающим адресам в data или в стеке - так и идут, чего тут думать-то )
leo Одкуда такая жестокая информация? Я что-то пропустил? Гляжу на свой рабочий Prescott(F-4-3) L1: 16K, 8-way, line-size=64 т.е. 8x32x64, на одну строку претендуют адреса на расстоянии 2K; L2: 2M, 8-way, l-s=64 (8x4096x64), конкурируют адреса +-256K... не представляю, при чем здесь 4M [offtop] что же так жестоко, как будто заставили под них оптимизировать [/offtop] AlB80 Оптимистично... это разве что для AMD / PM... на монстрах типа моего (см. выше) L1 - 4, L2 - 30... 8-[ ]
leo Спасибо за столь полный ответ . Не, я понимаю что это полезно будет только для массивов и только в определенных случаях. Только я один момент не уловил: Почему независимо? Как я понимаю, если адреса "ведут" в одно множество, и допустим ассоциативностей 4, то пятая запись так или иначе вытеснит какую-то строку (точнее, если я правильно понял, строку, запись/чтение которой происходило последний раз относительно этого множества). Или не так?
Ustus Видимо, да Загляни еще раз в IA-32 Optimization в раздел General optimization...\Memory...\...Aliases in Caches или проще поиском "Data conflict" Оптимизировать никто особо не заставляет, но и вляпаться на ровном месте в навоз тоже не хочется. Не понимаю какому идиоту могла придти в голову идея искусственно создавать конфликт данных, различающихся на 64К - стандартный чанк VirtualAlloc и MapView, затем с умным видом давать рекомендации по смещению адресов VirtualAlloc'ов, а через годик-другой с гордостью перечислять улучшения, введенные в очередном детище. Интересно почему в первых моделях размер минитега составляет именно 10 бит (с 6-го по 15-й), а не 11 или 12 - места на чипе не хватило для двух проводочков (правда х4) ? А про Prescott'ину и говорить нечего Ради чего конвеер в полтора раза увеличивали и тайминги загрубляли не понятно - до 3.2Ггц (а может и выше ?) и Northwood'ы без проблем подтянулись, вот если бы их совершенствовали, а не гнались за призрачный горизонт 4Г, тогда еще можно было о чем то говорить, а так ... одни эмоции ) Mika0x65 Видимо и ты, "что-то упустил" Придется процитировать самого себя и далее по тексту
Ustus Забыл пояснить насчет data conflict в P4. Из прочтения мануала можно сразу не понять при чем тут линейные адреса, т.к. во всех "нормальных" процессорах кэши работают с физическими. Так вот в "дебильных" P4 из-за проблем с быстродействием TLB одновременно с лукапом делается предварительная проверка L1-hit\miss по части линейного адреса - по минитегу, отсюда и возможные конфликты линейных адресов, несмотря на то что физические адреса различны. Ителы эту фи(гню)чу называют "virtually addressed and physicaly tagged"
