К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 65
Текст из файла (страница 65)
3.32. Зависимость времени обработки двухмерных массивов в зависимости от шага чтения Поскольку обмен с кэшем и основной оперативной памятью осуществляется не отдельными ячейками, а пакетами, достигаюшими в длину от 32 до 128 байт, то при последовательной обработке ячеек время доступа к ним оказывается крайне неоднородным.
Задержки возникают лишь при чтении первой ячейки пакета, а остальные ячейки пакета обрабатываются практически мгновенно. Нз этого в частности следует, что болыиие многомерные массивы Гт. е. неумещающиесн в кэш-памяти первого, а тем более второго уровней) выгоднее обрабатывать не но столбцам, а но строкам. Массивы, целиком помещающиесп в «эш, можно обрабатывать как угодно — от этого хуже не будет. Кэш зго Особенности буферизации записи "Волчьи ямь]н опережающей записи Начиная с К5, процессоры семейства х86 используют прозрачную буферизацию записи (см.
разд. "Буфера записи" зл)ой главы), причем, буферы записи доступны не только лля записи, но для чтения. То есть результат работы команды становится доступным сразу же, как только он попадает в буфер, — дожидаться завершения его выгрузки в кэш-память нет никакой нужды! Очевидно, что такой трюк, именуемый разработчиками процессоров опережающий записью ГБ/оге-Рог)наг/у)лд), значительно сокра)цает время доступа к данным.
Рассмотрим это на следующем примере. Пусть у нас имеется цикл вида. Гоп<а = О; а < ВЬССК Зтгс; а += зьхеоб)тпрЗ2)) р)а] + спр 1; спр 2 -= р]а); Вместо того, чтобы гонять данные по "большому кругу кровообращения": вычислительное устройство -+ блок записи -а кэш -+ блок чтения -+ вычислительное устройство, процессор АМО Аг])!оп направляет данные по "малому кругу кровообращения": вычислительное устройство -а буфер записи -+ вычислительное устройство. Как видно, малый круг намного короче! Репйшп-процессоры судя по всему ведут себя точно так же, хотя ничего вразумительного на этот счет в документации не говорится.
Разумеется, буферизации записи присущи определенные ограничения и она эффективна лишь в тех случаях, когда читаются именно л)е данные, которые были записаны. В противном случае процессор выставляет пенальти и быстродействие программы значительно падает. Продемонстрируем это на следующем примере (рис.
3.33 слева): // запись данных а буфер О байтов ]рь2/ рьа] нет а буфере ]Гпп *) )(ьпп)р) = х; у = *]гпс *)))гпп)р ~ 2); Грубо говоря, мы записываем в буфер ячейки О, 1, 2 и 3, а затем запрашиваем ячейки 2, 3, 4 и 5. Легко сообразить, что ячеек 4 и 5 просто нет в буфере и для их загрузки процессору необходимо обратиться к кашу.
Но ведь в кэше еше нет ячеек 2 и 3, — т. к. они не успели покинуть буфер! Доподлинно неизвестно как процессор выходит из этой ситуации. Возможно, часть ячеек он считывает из буфера, а часть — из кэша и объелиняет обе Глава 3 "половинки" в олну. Возможно (и более вероятно на мой взгляд), процессор "сбрасывает" содержимое буфера в кэш и уже оттуда безо всяких ухищрений извлекает запрошенные данные. Рис. 3.33. Возникновение задержки при перекрытии областей чтения/записи Но, так или иначе, все это требует дополнительных тактов, снижающих производительность.
(Для процессора Р-)И величина пенальти составляет шесть тактов, а АМ 0 Аг)т!оп — десять.) Другое ограничение. Даже если запрошенные данные целиком содержатся в буфере, но адреса читаемой и записываемой ячеек не совпадают, — все равно возникает задержка, т. к. процессору приходится выполнять определенные преобразования, отсекая "лишние" биты из записанного результата (см. рис. 3.33 справа). Наконец, если адреса ячеек совпадают, но они имеют различную разрядность, при этом задержки опять-таки не миновать. Логично, что если размер записываемой ячейки меньше читаемой (рис.
3.34 справа), — только часть запрашиваемых данных попадает в буфер, а все остальное содержится в кэше, т. е. ситуация сводится к рассмотренной выше. Рис. 3.34. Возникновение задержки при несоответствии разрядности данных Природу задержки, возникающей при записи ячейки большей разрядности (см.
рис. 3.34 слева), понять сложнее. Несмотря на то, что данные непосредственно извлекаются из буфера, минуя кэш, отсечение лишних битов требует какого-то времени (по меньшей мере одного такта). Кэш То же самое справедливо и для нескольких коротких записей, перекрывае- мых последующим длинным чтением. Разберем следующий пример: *(сват *)((1пе)р + О) = 'В'; *(сват *)((ьпе)р т 1) 'О'; "(сват *)((ьпс)р т 2) 'Г'; *(сват *)((1пс)р + 3) 'Н'; ВОГН = * (тпь *) ((1пь)р + О) ) // а" аадеркка! читахтся не те ке // самые данные, которые только что // были эаписаны На первый взгляд, все здесь вполне корректно — ведь запрашиваемые данные целиком содержатся в буфере записи.
Тем не менее, задержка в шесть тактов все равно возникает — ведь записываемые и читаемые ячейки имеют различную разрядность. Попросту говоря, загружаются отнюдь не те же самые данные, которые только что были записаны! Буфер записи адресуется совсем не так, как кзш-память, и процессор не может мгновенно установить: расположены ли записываемые байты в соседних ячейках или нет. Отсюда правило.
Чтение данных, следующее за их записью, должно иметь тот же самый стартовый адрес и не большую, а лучше такую же точно разрядность. )Уоэтому при возможности лучи|в вообще не работайте со смешанными типами данных (например, байтаии и двойными словами), а сводите их к единому типу наибольшей разрядности. Если же прочесть небольшую порцию только что записанных данных просто жизненно необходимо, — воспользуйтесь, как и рекомендует !п(е(, битовыми операциями: Ч/'1/ 1з пессззагу |о ех|гас| а поп-а1)йпейрогйоп о1'з(огед да/а, гвалт ои| Йе зтайез| а11епед рог|юп Йа| сотр!е|е/у сотатз Йе дага апд зЬ|4/таза йе да(а аз песеззагу. 11)е ренару 1ог по| до(пя йсз 1з тисй Ы~6ег йап Йе сом о) Йе з/)1/й". Допустим, неоптимизированный пример выглядел так: // неоптимиэированный код сот(а = О; а < ВЬССК Шгш а +- вьвеогсьпш) *(1пь *) ((ьпт)р т а) т= х) у += я (с|1ак *) ((лпк)р + а + 2) ) ) Выделенная жирным ц)рифтом строка "навлекает страшный гнев" процессо- ра и становится самым "узким" местом в цикле.
Глава 3 ззг Попробуем исправить проблему так: // опкикмаироааииый код ток(а = О; а < ВООСК Зташ а а= а1ааоз(1по)) *( пд *) ((апо)р а а)а= к) Пар = *(5.пп *) ! (1пп)р + а) ) // чанюв во армены)м стоешеем // ке ае смен данае // "вручмуе выкуоамаем" // нудную нам ячейку х а [(Пвр а ОхООУУОООО) » Ох10) ) "(зпо *)((кпС)р) к; *(зпп *) ((1по)р + Ш СДСНВ Зтеа/1) СДСНВ Кйт дэасегдтГЩ = у) к = *(1пп *) ((зпп) р); // (- аадарака Поскольку записываемые данные имеют идентичные установочные адреса, процессор не может осуществить опережающее чтение из буфера и вынужден дожидаться, пока обе ячейки не попадут в кэш. Расчитывая на наименьший Вопреки заявлениям фирмы !п)е!, на процессоре Р-Ш мы получим даже худисее быстродействие по сравнению с первоначальным вариантом! Остается лишь гадать, кто ошибся: парни из 1п(е1 или мы? Быть может, на процессоре Р-4 расклад вещей окажется совсем иной и ручные битовые "махинации" возьмут верх над неоптимизированным вариантам, но, в любом случае, учитывая, что вашу программу планируется исполнять не только на Р-4, но и на младших моделях процессоров семейства х86, не слишком-то "закладывайтесь" на эту рекомендацию.
До сих мы говорили о записи/чтении одних и тех же данных. Однако нронессор, нроверлн наличие занрашиваемых данных в бу(рере, анализирует не все биты адреса, а только те из них, которые "отвечают" за выбор конкретной кэш-линейки в кэш-памяти верного уровни (так называемые установочные адреса). Отсюда следует, что если адреса записываемых/читаемых ячеек кратны размеру кэш-банка (который можно вычислить, поделив размер кэша на его ассоциативность), процессор "дезорганизуется" и не может определить: какую именно порцию ланных ему следует извлекать.
Возникает вынужденная задержка на время, пока "одноименные" ячейки не будут выгружены из буфера записи в кэш первого уровня, на что уходят те же самые шесть (Р-Ш) или десть (АМ!) А()(1оп) тактов процессора. Рассмотрим следующий пример: Кэш возможный размер кэш-банка (2 Кбайт для прцессора Р-4), располагайте все интенсивно "передергиваемые" переменные в пределах ! Кбайт. Заметим, что все вышесказанное не раснрвстраннетсн нн заннса, следующую за нгненисм, т. е. далее приведенный код будет исполняться вполне эффективно: ссп(а = вьаесггтпе); а < Бьсск Бггг; а ь= вьвесг(1пс) ) я ь *(сьал *) ((1пс)р + а - (аьгесг(гпс) /2) ) ) *(1пе *) ((1пп)р а) += у) И в заключение раздела — наш традиционный эксперимент, позволяющий количественно оценить степень падения производительности при неправильном обращении к данным.
Для наглядности мы последовательно переберем все шесть комбинаций (листинг 3.13), упомянутых в руководстве по оптимизации от 1пге1 (кстати, руководство по оптимизации от АМ0 крайне поверхностно и "туманно" освещает эту проблему, поэтому даже если вы убежденный поклонник АМ)3, не побрезгуйте обратиться к!пге!, тем более, что в этом вопросе оба процессора ведут себя одинаково). (Полный исходный текст программы (см, листинг 3.13) читатель найдет в файле ~згсь, (3!.сас!)е)изет.зга!!.с, который находится на прилагаемом компакт-диске.) // выделяем паьиеь р = (1пп*) аа11сс32(ВЬОСК 31гк); оптимизированный вариант пппб Ильва/Ьспд Ваас)(вваа а<в)л) -*/ гсл(а - О; а < ВЬССК Бьгк) а += вьгесг(1 р32)) * Нпе *)((ьпв)р + а) = Парзг) епр32 ь= (1пе *)((1пе)р + а); Глава 3 ЗЗ4 НЕОПТИМИЗИРОВАННЫЙ ВАРИАНТ ЗАогс И<1<а/вопр Неаб (аале ас(с(г) Рог(а = О) а < 8)оск 5155) а += 51гео1(гпр32)) ( *(<Ьаг *) ((1пс)р + а) = Глр8) Гпр32 += *(1пг ) ((гес)р + а)) НЕОПТННИЗИРОВАННЫЙ ВАРИАНТ ЗПог1 Иг1ге/Поп8 Аеас( (очег1ар арапе) Рог(а = *Тгео1(гспр32) ) а < 81~хк 5гееу а += а1геот(ггр32) ) *(оПаг *)((гпс)р + а (а1геой(слр32)/2)) = Глр8; сар32 += *(гпс *)((гпг)р с а)) НЕОПТИНИЗИРОВАНВЬЙ ВАРИАНТ Поев а)г1ее/ВНоге Аеас( (еаам асЫг) Рог(а = О) а < ВЬОСК 51КЕ) а += а1геог(глр32)) ( *(1пг *) ((Тпг)р + а) = Гпр32) Слр8;-= *(ОЛаг *) ( Гапс) р + а); /*- НЕОПТСЕЕИВИР<ВАННБВ( ВАРИАНТ Т.опд Иг1ее/ВЬоге Влас( (оеег1ер арапе! */ Кэш 335 Еог(а = а1геоЕ(тар32) ) а < В1~ХК 512Ег а += 511ЕО1(еар32) ) ( " ВЕп1 *)((1пт)р + а) еор32) ттр8 += "(осаг *) ((1пт)р + а + (атаао1(тюр32)/2))) /*- ННОВТИИИЭИРСВАННЬЙ ВАРИАНТ Т.опо а)?1аа/Еопв Неас1 (ооепХар арапе) 1от(а = етаеот(тар32) ) а < 810ск 512е) а -)= а11еог(кор32) ) ( *(1п1 *) ((и а)р + а) = епр321 кпр32 += *(1пт ) ((1пт)р + а — (*1геот(тар32)/2)); Рис.
З.ЗВ. Возникновение задержек при обработке данных различной разрядности (в кеше первого/второго уровня) Глава 3 ЗЗБ Результат прогона этой программы на процессорах АМВ А(Ыоп 1050 и РП! 733 представлен далее. При условии, что обрабатываемый блок не превышает размера каша первого (второго уровня), попытка чтения отсутствующих в буферах данных приводит к пяти-шестикратному падению производительности грие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
