К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 39
Текст из файла (страница 39)
е., попросту говоря, // указатель смещен на 1 байт вправо относительно // выровненного по границе 32 байт адреса, // общее решение данной задачи без использования // циклов )цикгм — снижают произволительность] О невозможно! // единственный вариант — вручную создать свой "обработчик" для каждой ситуации // всего их будет 32 — 32/4 = 24, что слишком // громоздко лля книжного варианта пакт-диске.) Обратите внимание: общих решений поставленная задача не имеет.
Максимальное количество двойных слов в типичном пакете всего восемь, а при работе с невыровненными адресами и того меньше! Цикл из нескольких интеракций — крайне медленная штука и во избежание падения производительности он должен быть развернут целиком. В этом-то и заключается основная проблема; поскольку количество итераций зависит от величины смещения указателя в пакетном цикле обмена, нам необходимо соз- датЬ Ваву ЬВН вЂ” Ваат ьай/з ое ) Писка] раЗЛИЧНЫХ ЦИКЛОВ, КаждЫй ИЗ которых будет обрабатывать "свое" смещение указателя. Для экономии места в книге приведен лишь один вариант, поскольку остальные реализуются практически аналогично.
Глава 2 (((гдп)актау З 15)! 1) евябн("-ейн: Недопустимое выравниваниеМ Гог(а = 0) а < и) а а= 8) // копируем вое двойные слова, которые // не пересекают границы пакетных циклов // обмена х+=аггау[а + 0)) к+=актау[а + 1)) х+=аггау[а + 2); хе=актау(а + 3)) к+=актау[а т )]) х+=аггау(а з З]) к+=актау[а + 6]) // двойное слово, пересекающее пакетньзл цикл, // копируем во временный боер по байтам карга Ьувез[0]=*((сна *) актау т (аа7)*зггеоб(гпп) О) зпрга ьугез[1)=*((сьаг *) актау + (а+7)*загеоу(гпг) т 1)) зпрга Ьутез(2]=*((сьаг ') актау + (аа7) з1геос(гпв) е 2); зцрга Ьугез[З]=*((сьаг *) актау + (ат7) з1хеог( пг) + 3)) // извлекаем зорка-байты и обрабатываем их как двойное слово хт=*(1пт )зорка Ьувез; геппгп х) И вот тут нас ждет неожиданный и весьма неприятный сюрприз.
"Оптимизированная" про(рамма выполняется намного медленнее первоначального варианта! На Р-Ш?33/133/100/1815ЕР падение производительности составляет 15% !рис. 2.36), а на АМ!3 А[[]1оп 1050/100/100/Ч1А КТ133 аж 130%[1[ Ничего себе "оптимизация"! В чем же причина? Дело в том, что предотвращение пересечения пакетных циклов обмена достается нам "дорогой ценой", а именно — увеличением количества обращений к памяти.
Это-то и снижает производительность! Тем не менее, автор отнюдь не собирается выбрасывать предложенный алгоритм на помойку. Тут еще есть над чем подумать! 'А почему б(н нам не подумать вместе.у", — как сказал герой мультфильма © котенок Гав. 189 Оперативная память Рис. 2.36. Описанная методика "аффективной" обработки невыровненного двухсловного потока данных нв самом деле снижает производительность.
Самое интересное, что невыровненный поток нв АМО Атюоп обрабатывается даже быстрее, чем выровненный! Выравнивание байтовых потоков данных Эффективная обработка байтовых потоков данных двойными словами (см. равд. "Обработка памяти байтаии, двойными и учетверенными словами" этой главы) возможна лишь в том случае, если адрес начала блока выровнен по границе четырех байт.
А так, к сожалению, бывает не всегда. Ведь байтовые потоки не требуют выравнивания по определению, и компилятор (или программист) может располагать их в любом лтесте в памяти, т. е. где ему больше заблагорассудится. К счастью, самостоятельно выровнять такой поток вызываемой функции не составит большого труда! Поскольку байтовый поток однороден, то мы можем начать читать его с любого места. Вычисляем адрес ближайшей границы пакетного цикла (в обшем случае он равен р ь ~вкзт ькн — (< ы р ь вкзт ькл~ ~) и "гоним" двойными словами в полную силу, не забывая, конечно, о том, что размер блока не всегда бывает кРатен зтьеот 1ововс).
Постойте! А как же первые ~вкзт ькн — (гьпт) р ь ввзт ькн~ ~ байтов?! Ведь они остались необработанными! Что ж, добавить дополнительный цикл обработки — это не проблема! (рис. 2.37). Возврашаясь к листингу 2.23, реализуюшему простейший шифровальный алгоритм, давайте научим его выравнивать обрабатываемый блок данных. Глава к Один из возможных способов приведен в следующем примере (листинг 2.25). (Полный исходный текст программы читатель найдет в файле ~его'42).птетпогу~а!)~п.Ьеггеап1.с, который находится на прилагаемом компактдиске,) // — ~Я1шр1е Ьуле-птурс~в // Ако: — указатель на шифруемыл блок — маска шифрования (байт~ втс ОЕРЕМСЕ: ппа11дп птурс лова а11оп стуре(спал *втс, ап1 и, Епл шавх) ьпс а; сват *к; 1пл и ца1лсы; // // // // // // О // О О- Рис.
2.37. Техника выравнивания байтовых потоков данных. В отличие от выравнивая двухсловных потоков, она действительно эффективна Тф' '„' ' ' Я 'И 'Фю ' " ' ' ", ' в Я~вес 3'фиг ' *11пв функция самостоятельно выравнивает шифруемые данные Оперативная память // вычисляем велнчньгу, на которую следует "догнать" блок, О чтобы он стал выровненньы блоком и иа1гдп= 32 — Ы гпс! вгс а 1Ы; // шнфруем пока не достигнем границы пакетного цикла обмена шпа1гдп огури(вгс, и па1гдп, шавхы // смело шнфруем все остальное // т.
к. вгсьп ца11дп — гарантированно выровненный указатель! цпа1гдп сгурс1вгсьи ца1гдп, п-и па1гдп, шазы; /' не забываем уменьшить "" """"" "" ко-во шнфруеных байтов */ Прогон программы показывает, что оптимизированный вариант с одинаковой эффективностью обрабатывает как выровненные, так и невыровненные блоки данных (рис.
2.38), в то время как неоптимизированный теряет на невыровненных блоках от 17% до 69% производительности (на Р-Н1 733/ 133/100/1815ЕР и АМО Ат!1!оп 1050/100/100/Ч1А КТ !33 соответственно). КСТВТИ, фуНКЦИЯ а1гдп стуре (КВК ВЫ, НВВЕрНОЕ, УЖЕ ОбраТИЛИ ВНИМаНИЕ) ПрЕдСтаВЛяЕт СОбОй НЕ бОЛЕЕ ЧЕМ "ОбЕртКу" дЛя фуНКНИИ ппа1гдп огури, Т. Е. она легко может быть адаптирована под ваши собственные нужды. Для ЗтОГО ДОСтатОЧНО ЛИШЬ ЗаМЕНИтЬ ВЫЗОВ ФУНКЦИИ цпазьдп сгург На ВЫЗОВ Вашей функции. Рис.
2.38. Демонстрация эффективности выравнивания байтовых потоков данных. Легко видеть, что предложенная техника выравнивания на 100% эффективна юг Глава г Комбинирование вычислений с доступом к памяти В современных процессорах обращение к оперативной памяти уже не приводит к остановке вычислительного конвейера. Отослав чипсету запрос на загрузку ячейки, процессор временно приостанавливает выполнение текущей машинной инструкции и переходит к следующей. Это обстоятельство, в частности, позволяет посылать очередной запрос чипсету до завершения предыдущего (см. равд.
"Параллельная обработка данных" этой главы). Однако параллелизм чипсета весьма невысок и при обработке больших объемов данных процессор все равно вынужден простаивать, ожидая загрузки ячеек из оперативной памяти. Так почему бы не избавить процессор от скуки и не занять его вычислениями? Предположим, нам необходимо загрузить Х ячеек памяти и к раз вычислить синус угла. Предпочтительнее выполнять зти действия не последовательно, а объединить их в одном цикле.
Тогда вычисления синуса будут происходить параллельно с загрузкой ячеек из памяти, сокращая тем самым время выполнения задачи. Сразу же возникает вопрос: в какой именно пропорции целесообразнее всего смешивать вычисления и обращения к памяти? Достаточно очевидно, что в идеале время выполнения вычислительных инструкций должно быть равно времени загрузки ячеек из памяти, — в этом случае достигается наивысшая степень параллелизм. Проблема состоит в том, что соотношение скорости доступа к памяти и скорости выполнения машинных инструкций на различных системах варьируется в очень широких пределах, и потому универсальных решений поставленной задачи нега (см.
подробное обсуждение этой проблемы в равд. "Планирование дистанции лредвыборхи" главы 3). С другой стороны, полного параллелизма добиваться вовсе не обязательно, да и зачастую он вообще невозможен в принципе. Так, например, количества вычислений может оказаться просто недостаточно для покрытия всех задержек загрузки данных из памяти. Попробуем оценить выигрыш, достигаемый при полном и частичном параллелизме. Для этого напишем следующую несложную тестовую программу, исследующую различные "концентрации" вычислительных операций на ячейку памяти.
Далее для зкономии места приведен лишь ее фрагмент (листинг 2.26). Обратите внимание: цикл, обращающийся к памяти, в оптимизированном варианте должен быть развернут. В противном случае мы не получим никакого выигрыша в производительности, и хорошо если еще не окажемся в убытке. Почему? Так ведь свернутый цикл нельзя исполнять параллельно. Это, во-первых. А, во-вторых, циклы с небольшим количеством итераций крайне невыгодны хотя бы уже потому, что исполняются на одну итерацию больше, чем следует. Оперативная память (Стратегия предсказания ветвлений такова, что в последней итерации цикла процессор, "не догадываясь" о том, что цикл уже завершен, действует "как раньше", передавая управление на первую команду цикла; потом, конечно, он распознает свою ошибку и выполняет откат, но время выполнения от этого не уменьшается.) Необходимость разворота циклов приводит к колоссальному увеличению размеров тестовой программы, — поскольку язык С не поддерживает циклические макросы, весь код приходится набивать на клавиатуре вручную.
Вот, кстати, хороший пример задачи, которую невозможно элегантно решить штатными средствами языка С (макроассемблер с этим бы справился на ура). Но довольно лирики, перейдем к исследованиям (Полный исходный текст программы читатель найдет в файле ((згс(Д2(лпепюгу((тет.ппх.с, который находится на прилагаемом компакт-диске.) неоптиы<зированнь» вариант ре~16( // 16 загрукаеьых байт на одно вычисление синуса // цикл загрузки ячеек из памяти // этот цикл исполняется крайне неоптимально, поскольку неповоротливая // подсистема памяти просто не успевает за процессором и тому приходится скучать тот(а = О; а < ВООСК Зтае( а/= Н г += *(1пт*(((1пп(р1 + а(( // цикл вычисления синусов тот(а=б( а < (ВООСК Зтаа/рег(; аь+( х+=сов(х(( неоптнмизированный вариант // обвий цикл, комбинирухщий обраиение к памяти с вычислениями синуса гог(а = О; а < Вьсск 61ее( а += рег) Глава 2 794 // внимание: цикл обращения к памяти дслкен быть развернут, // иначе оппаензация обернется проигрнщем в производительности з += *)1пг*) ) Ггпг)р1 + а); з +- * (1пс*) ) Ыпс)р1 + а + 4) ь з += *Мпз ) ) Гапт)р1 + а + 8); з += * рыле*) ) гьпс)р1 + а + 12) ) // вычисление синуса будет происходить параллельно // с загрузкой предыдузмх ячеек, за счет чего достигается // увеличение производительности к+=сов(х); Прогон данной программы под системой АМЕ) А11)1оп ! 050/100/100/ ')/1А КТ133 (рис.
2.39) позволил установить, что наивысший параллелизм достигается, когда на каждые 32 загруженных байта приходится одна операция вычисления синуса. В этом случае оптимизированный вариант исполняется практически на треть быстрее. Еще больший выигрыш наблюдается на Р-П1/733/133/100/1815ЕР: при концентрации 25б байт на один синус, мы добиваемся чуть ли не двукратного увеличения производительности! Рис. 2.39. Демонстрация эффективности комбинирования вычислительных операций с командами, обращающихся к памяти Оперативная память Правда, платой за это становится размер программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
