К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 45
Текст из файла (страница 45)
о х 224 !Ш ! >" к с о : :$ Ш О. и и и а ',. о н О о и 3 и о о в с с : :С3 !а :'Ш 3 3- и с О3 в с о к с о Ф Ф Б Х Ф с о. о с Ф о. Ф с о :'й :; о :: ьс Ф о о~ а 'О' Ю3 Ф Ф ~~ 5 % О о й о+ в =О О 'о мъ С 33, о + О3 О > о 3О о + в + о о о И :, о , :о х 3О Ф о т о о Б й в Ф 33 с с 31 Б Ф в х о.
Б с Ф в Б к х о л к в о. о. : с о3о ь с о! о о Х в о ". а Ф с о Ф 3О к х 33 в о. Б О3 Ф Ф О3 О3 к О3 33 а О3 Ф Ф в Ф в Х Ф в о. Б Ф Ф Х 3О Б о!в :., о к :, о к ! о ! а вк , :з с Б 3Ф у О3 !Д о Глава 2 Оперативная память 225 о О о о С О3 о о х о. с ~ о О О Ф ь СО :О Ф 3- , .х 03 03 'С 3О Ф с 35 + о + 03 О ,:ш ,:. со 3 3 ;н 0 Зй 03 хФ о Ф с > о 3О о + и + о О .Й .а :: а.
03 О. 3Х а с с Ф с. Ф с О Ф :; о Ф $ о о 4 Ф о ::о1 ! 3 а 33 ! о 33 Ф 03 х Ф ! Ф х, :х Ф Ф х с Ф Е'.,й х:. х 'О ФЗФ 03Х:Й !о х1х '.Ф х!О :со Я;;О Глава 2 Поэтому целесообразнее пользоваться вашими собствениььии реализациями строковьп функций, вылизанньп "дальше ие куда".
Если этого не сделаете вы, никео не оптимизирует вашу программу за вас! Оптимизация блочных алгоритмов Если с потоковыми алгоритмами все было предельно просто (хотя и не без тонкостей), то оптимизация блочных алгоритмов — это вешь сама по себе нетривиальная. Если потоковая обработка данных предполагает, что данные запрашиваются последовательно и ничего не стоит организовать оптимальную (с точки зрения подсистемы памяти) трансляцию виртуальных адресов, то блочные алгоритмы могут в хаотичном порядке запрашивать любые ячейки в границах отведенного им блока. До тех пор, пока размер блока не превосходит эти пресловутые ()ч — 1)*з, т. е. составляет порядка 4 — 6 Кбайт, — никаких проблем не возникает, особенно если разрядность обрабатываемых данных сопоставима с величиной пакетного цикла обмена с памятью.
В противном случае возникают штрафные задержки при попадании в регенерируюшиеся ОКАМ-банки, плюс издержки от упреждающего чтения ланных, к которым никто не обращается. В идеале следовало бы посоветовать сократить размер блоков до нескольких килобайт, но — увы — такое решение не всегда возможно. Что ж, тогда придется прибегать к механизму виртуализации адресов. Пусть слово "виртуальный" не вводит вас в заблуждение относительно механизма реализации такого приема. Для этого вовсе не обязательно иметь наивысшие привилегии и доступ к системным таблицам. Виртуальную трансляцию вполне можно организовать и программным способом, один из которых мы уже рассмотрели выше при оптимизации потоковых алгоритмов.
К сожалению, эта тема не имеет прямого отношения к полсистеме оперативной памяти и не может быть подробно рассмотрена в рамках этой книги. Давайте отложим этот вопрос, по крайней мере, до будущей, третьей, книги, посвяшенной автоматической кодогенерации. Спекулятивная загрузка данных Алгоритм спекулятивной загрузки данных родился в те незапамятные времена, когда вычислительными залами владели "динозавры", т. е. ЭВМ, а роль внешней памяти выполняла до ужаса "тормозная" магнитная лента. Первые программы работали приблизительно так; ЗАГРУЗИТЬ БЛОК ДАННЫХ С ЛЕНТЫ вЂ” ОБРАБОТАТЬ ДАННЫŠ— ПОВТОРИТЬ. Во время загрузки данных бобины с лентой бешено вращались, а на время вычислений покорно останавливались. На обывателя это зрелише, действительно, действовало неотразимо, но для достижения наибольшей производительности ленточный накопитель должен работать не урывками, а непрерывно.
Оперативная память гг7 История не сохранила имя первого человека, которого осенила блестящая мысль: совместить обработку данных с загрузкой следующего блока. Если время выполнения неоптимизированной программы в общем случае равно: Т = )4*(Т,~р, + Тор), где Т,„р, — время загрузки блока данных с ленты, Тар— время обработки блока, а Х вЂ” количество блоков, то оптимизированный алгоритм может быть выполнен за время, определяемое как: Торпвам = Х*(щах (Т,гр, + Тор)).
Максимальный выигрыш достигается в том случае, когда время загрузки данных с ленты в точности равно времени вычислений. Как нетрудно подсчитать: Т/ Т,рь „, = Х*(Т, р, + Тор) /Х*Т,„р, = 2, т. е. время обработки сокращается в два раза. И хотя бобины магнитной ленты уже давно вышли из употребления, — они до сих пор готовы преподнести всем нам хороший урок. Задумайтесь: как работает подавляющее большинство современных блочных алгоритмов? Какую программу ни возьми, всюду встречаешь сценарий: "загрузить— обработать — повторить".
Пускай быстродействие оперативной памяти не идет ни в какое сравнение со скоростью магнитной ленты, но ведь и тактовая частота процессоров не стоит на месте! Простое смешивание команд загрузки содержимого ячеек памяти с вычислительными инструкциями (подробнее см. разд. 'Труппировка операций чтения с операциями записи" этой главы) еше не обеспечивает их параллельного выполнения, — ведь вычислительные инструкции начинают выполняться только после окончания загрузки обрабатываемых данных! Вспоминая сценарий работы с лентой, давайте усовершенствуем стратегию загрузки данных, обращаясь к следующему обрабатываемому блоку задолго до того, как он будет реально востребован.
Этим мы устраним зависимость между командами загрузки и обработки данных, благодаря чему они смогут выполняться параллельно, и если время обработки данных не превышает времени их загрузки (как часто и бывает), обмен с памятью станет происходить непрерывно, вплотную приближаясь к ее максимальной пропускной способности (см. такзке разд. "Параллельная обработка данных" этой главы). Рассмотрим следующий пример типового не оптимизированного алгоритма обработки данных (листинг 2.41).
неоптиызировыек Х вариене ~ь =- о; ь < вьоск агав; ь += зг~ Глава 2 ггв // загружаем ячейки х += (*(апт *)((зпт ) р + а))) // 6 зта команда блокирует асс остальные х т= (*(тпт *)((1пт ) р т а (- 4))) х += (*(1пг *)((зпг. ) р т а т 8))) х += (*(1пт *)((апс ) р ь а + 12))) х += (*(ьпт *) ((ьпт ) р т а т 16) ) ) х я= (*(1пл *) ((1пт ) р + а + 20)); х += (*(щт ") ((1пт ) р т а + 24) )) х += (*(1пт *) ((зпт ) р т а + 28))) // аыпслняем некоторые еычисления х += а/х/666) Основной его недостаток заключается в том, что вычислительная процедура х += а/х/ббб ВЫНУжДЕНа дОжИДатЬСЯ ВЫПОЛНЕНИЯ ВСЕХ ПРЕдЫДущИХ КОМаНд, а они, в свою очередь, вынуждены дожидаться окончания загрузки требуемых данных из памяти.
Таким образом, первая строка цикла хе=*(зпт*)((1пт)р + а) блокирует все остальные (а еще говорят, что семеро одного не ждут). Можно ли устранить такую зависимость по данным? Да, можно. Достаточно, например, загружать данные со сдвигом на одну или несколько итераций (подробнее о вычислении предпочтительной величины сдвига см. равд. "Планирование диса)анции лредвыборки" главы 3).
Образно говоря, мы как бы смещаем команды загрузки данных относительно инструкций их обработки (рис. 2.51). Рис. 2.51. устранение зависимости по данным путем упреждающей загрузки следующего обрабатываемого блока Оперативная память В результате этого мы получаем приблизительно следуюший код (листинг 2.42). (Обратите внимание, исходный текст программы практически не изменен! Полный исходный текст программы читатель найдет в файле ~зги[2)лпеп)о(у~бреси!ат!уе.ген.с, который находится на прилагаемом компакт-диске.) оптимизированный вариант оо опекулятивиой загрузкой // загружаем первую порцию данных х += (*(1пт. )( ггпп) р + а)): Гог(а = б; а < В1ССК 8128; а т= Зг) // упреждакиая загрузка очередной порп)тя данных у = (*(1пт *) ((1пт) р + а к 32)); // Е- *** // обрабатываем ранее загружеииые ячейки х ч (*(1пп *) ((1пт) р + а т я)); х ч= (*(1пт *) ((ьпт) р е а е 8) ); х + (*(ьпт *) ((ьпт) р + а а 12)); х + (*(1пп *) ((1пт) р + а + 16) ); х += (*(ьпт *) ((ьпт) р + а + 20) ): х += (*сапе *) ((апт) р + а а 24) ) ) х + (*Гале *) ((1пт) р + а + 28)); // выполняем некоторые вычиолеиия х += а/х/666; // востребуем упреждеихо-загруаеииые данные х ~ у) На Р-111/!33/100/18!5ЕР такой несложный трюк уменьшает время обработки данного цикла приблизительно на 25%.
Глава 2 2ЗЦ Оптимизация сортировки больших массивов данных "По оценкам производителей компьютеров в 60-х годах в среднем более четверти машинного времени тратилось на сортировку. оо многих вычислительных системах на нее уходит болыае половины машинного времени" Дональд Э. Кнут "Искусство программирования. Том 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
