К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 36
Текст из файла (страница 36)
е. закрыть активную страницу. Таким образом, крайне нежелательно обрабатывать более четырех потоков данных параллельно, в противном случае вы столкнетесь с проблемами производительности. "Да, да, — хмыкнет читатель, — советовать что-либо не делать — проще всего". Гораздо сложнее найти решение как именно это делать! Положим, нам необходимо обрабатывать более четырех потоков данных одновременно, причем, расплачиваться производительностью за постоянные открытия/закрытия РВАМ-страниц мы категорически не хотим. Тупик? Вылезаем, мы приехали? Вовсе нет! [70 Глава 2 Первое, что приходит на ум, — это перейти на оперативную память типа КРКАМ. В сочетании с чипсетом !п[е! 850 это обеспечит восемь реально открытых страниц, а это — восемь потоков данных! Удовлетворяет вас такое решение? В общем-то, да, но далеко не во всех случаях. КОКАМ на сегодняшний день (точнее, момент написания этих строк) — не самый дешевый и распространенный тип памяти, На самом деле, даже на обычной ЯРКАМ-памяти можно обрабатывать практически неограниченное количество потоков данных, ничем не расплачиваясь взамен.
Ведь никто не требует обрабатываемые именно физические потоки. Вот и давайте, создав один физический поток, разобьем его на несколько логических (виртуальных) потоков или, другими словами говоря, используем [п[ег!еаке-трансляцию адресов. Тогда между адресами логического и физического потоков будет установлено следующее соответствие: [*1*[ /* 2 */ р[кч [а] а*мак в + в р[а! а вод мах и где: р — массив указателей на адреса начала логических потоков; р — указатель на адрес начала физического потока; в — индекс логического потока; а — индекс элемента логического потока в; мхх в — количество логических потоков.
"Живой" пример !п[ег1еаре-трансляции изображен на рис. 2.28. Смотрите, до оптимизации у нас было два обособленных блока памяти а. и Ь., каждый из которых хранил восемь ячеек памяти, обозначенных аО, а1а7 и ЬО, ЫЬ7 соответственно. В оптимизированном варианте программы эти два блока объединены в один непрерывный блок, составленный из шестнадцати чередующихся ячеек блоков а и Ь, — аО, ЬО, а1, Ы а7, Ь7. Теперь, при параллельной обработке логических потоков а и Ь запрашиваемые данные сливаются в один физический поток т, что; во-первых, позволяет избежать постоянного открытия/закрытия РВАМ-страниц; во-вторых, гарантирует, что смежные ячейки потоков а и Ь не попадут на различные страницы одного и того же РКАМ- банка, находящегося в момент обращения на регенерации.
И, в-третьих, облегчает работу системе аппаратной предвыборки (если таковая имеется), поскольку большинство таких систем оптимизированы всего под один поток (это легче реализовать, да и увеличение пакетного цикла обмена с памятью эффективно лишь при последовательном обращении к ней). Причем, заметьте, все эти блага достаются практически даром и не слишком "утяжеляют" алгоритм. Правда, тут есть одна тонкость. Поскольку переход от физического адреса потока к логическому неизбежен без взятия остатка, Оперативная память то слелует полумат)я как избавиться от машинной команды оту, выполняющей целочисленное деление.
Дело в том, что деление — очень медленная операция, по времени приблизительно сопоставимая с закрытием одной РКАМ- страницы. Если количество потоков соответствуе~ степени двойки, то взятие остатка можно осуществить и быстрыми битовыми операциями. Другой путь — заменить взятие остатка умножением )слс разд. "Деление" главы 4).
Рис. 2.28. Виртуализация потоков данных. Несколько исходных потоков (слева) сливаются в один физический поток. сконструированный по принципу чередования адресов, что фактически равносильно его расщеплению на два логических потока Теперь давайте воочио убелимся, насколько эффективной может быть оптимизация потоков при большом их числе. Для этого напишем следующую несложную программу (листинг 2.19) и посмотрим на ее результат.
(Полный исхолный текст программы читатель найдет в файле ьтягст,~2)лпешогут, япеагп.у)ппа).с, который находится на прилагаемом компакт-диске.) Фбетьпе ВЬОСК ятяя убег пе МЛХ М Оят гзег е мли, яоотпа~ ,'2 М) ГУ макс, объем вирччального потока уу макс. кол-во виртуальньм потоков данньх тот)а = 2; а = млх и оят; аем " начинаем с двух виртуальннх потоков *у пС а, Ь, г, х=я; ьпт 'р, *ох)мю: ч оят,'; Г/ лапка ргьпттгн ратх ятяяяЧГЧ; МЛП, ВООВиа~ ргьпстм'умвбча;рт1пвм"',и"); обработка потоков классическим (неоплвееевированньм) опоообои */ ~ З)ИСтмлнйй19;яФрьа)тбЕНтПрОГрта)аМЫ "дВМОИСтрмрув)ЛЕй)афф~)Ю)йй'ВПНОрт)уя".,~",, '4': ВйРтУаПИЗбЩИИ.ПОТОКОВ В,,ааааа)МОЛСтм От ИК2ЧИада,:", „;, " -' Глава 2 Г72 О выделяем память всем потокам тот (а = О: а < МЯХ Н Оэт( а+т) рх(а) = (1па *) иа11осЗВ(ВЬССК Н1ЕЕ)ь ргыптт("сьйвэгС")) МатЬ НСОЬ(г) /* начало замера времени выполнение */ А ВЕБ?Н (0) тот(а = О) а < Вцсск ягееь а += е1теое(1пь) ) тат(ь = о; ь < г: ьт+) х +=.
*(1по *) ((гпт)рх(Ь) т а ) ) // перебор всех потоков адин эа другим // причем, как легко убедиться, ячейки // всех потоков находятся в различных // страницах ОНАМ, поэтому при обработке // более четырех потоков ОННМ-с раницы // будут постоянно закрываться/открываться // снижая тем самым производительность // В)НЕЯАНИЕ! в данном случае циклы а и Ь // в принципе возможно обменять местами, // увеличив тем саььм производительность, // но мы же договорились обрабатывать // потоки параллельно /* конец замера вреьени выполнеюьн */ Д ЕНН(0) // вывод времени обработки потока ргьптт("~ГЪП",Ах СЕТ(0))( ) рггпбт("~п")) /* епб тот */ оптьвеееироввннан обработка виртуальных потоков // выделяем память физическому потоку р = (1пт*) кнььосве(вьссе Вьве*мйх н оэт)) ргьпот("СрттМЕЕЕО-)) МйьЬ ЫЮЬ(г) ( А ВЕ61Н(1) /* начало замера времени выполнении */ Оперативная память бог (а = О) а ч ВЬССК Отав * г; а «- (вггеот(гпг) *г) ) // что иэменипоаьт Смотрите, " — щаг приращения // теперь равен кол-ву виртуальных потоков Гог(Ь = О) Ь < г; Ь ,) х = *(гпа *)((Епг)р « а « Ь*вггеот(гпг))) // теперь ячейки всех потоков раапопавены рядом // поэтому, вреыя их обработки — минимально й енс(() /* конец эанера времени выполнения «/ р пгт( ";Гьб", й- СЕт Н ) ) ) О вывод времени обработки патока рггпгт("цп")) /* епб Гог */ Ого! Нет, конечно, мы догадывались, что оптимизирующий вариант обгонит классический, но кто же мог представить; насколько он его обгонит! (рис.
2.29, 2.30). Вообще-то, на Р-Н1 733/133/100/1б'15ЕР/2?4 вплоть до четырех потоков /максимально возможного количества одновременно открытых РВАМ-страниц) оптимизированный вариант заметно отставал от неоптимизированного. Рис. 2.29. Демонстрация эффективности виртуапизвции потоков данных на системе Рсв 733/133/100/(815ЕР/2«4. Уже на 16 потоках оптимизация дает более чем трехкратный выигрыш 174 Глава 2 Рис. 2.30. Демонстрация эффективности виртуапиэации потоков данных на системе Р-1П/1815ЕР/2к4 АМО А1ыопрЛА КТ183/4к4 Но уже на пяти потоках оба варианта сравнялись в скорости, а дальше с добавлением каждого нового потока время работы неоптимизированного варианта стало стремительно взлетать вверх. А у оптимизированного, напротив, — росло практически линейно !небольшие осцилляции !биения) объясняются особенностями кэш-подсистемы, о которых мы поговорим чуть позже, в главе 3).
Так, уже на шестнадцати потоках (вполне реальная величина для типичных вычислительных задач) оптимизация дала более чем трехкратный выигрыш в скорости! И все это — повторяюсь — без значительных изменений базового алгоритма. Оптимизацию потоков необязательно закладывать на этапе проектирования программы, — это можно сделать в любое удобное для разработчика время.
К тому же, это далеко не предел производительности! Быстродействие программы можно значительно увеличить, если использовать параллельную обработку данных !см. разд. "Параллельная обработка данных" этой главы). А вот и тесты системы АМ!3 Абт!оп 1050/100/100/у'1А КТ133/4х4 (см. рис. 2.30). Забавно, но в данном случае оптимизированный вариант значительно обогнал неоптимизированный во всех случаях, даже при обработке всего двух потоков. Как же такое могло произойти? Помнится, документация обещала аж 16 одновременно открытых страниц, а на практике "сваливалась" всего лишь на двух.
Оперативная память 175 Верно, было нам такое обещано, но ведь в то же самое время утверждалось, что: "Боиг сагйе бнез (32 г/нпд когй) о/' Ср(/ (о !)лАМ геад рге~е!сп Щегг"— "Буфер предварительной выборки из 2)БАМ, рпзмером в четыре кзш-линии (32учетвереннык слова) центрального пропессора (25б байт — К. К.)". Для уменьшения латентности инженеры из Н!А решились на весьма ответственный шаг, т. е. на осуществление упреждающего чтения из оперативной памяти.
Алгоритм предвыборки должен умеешь распознавать регулярные шаблоны обращения к данным и на их основе с высокой вероятностью предсказывать, к каким именно ячейкам произойлет следующее обращение. В про~ианом случае от предвыборки будут олни убытки — ведь в момент чтения оперативная память недоступна и вместо уменыпения латентности мы многократно увеличим ее! К сожалению, локументация вообще ничего не говорит о сценарии предвыборки, но ведь никто не запрещает нал1 догпдываться, правда? Судя по всему, алгоритм упреждающего чтения в чипсете Ч!А КТ!33 даже и не пытаетсл распознать стратегию обращения к памяти, а просто загружает послелуюглие 32 учетверенных слова при обращении ко всякой ячейке. Как следствие— при работе с несколькими потоками данных содержимое буфера предвыборки будет вытесняться прежде, чем к нему произойлет реальное обращение и "упрежденныс" данные окажутся "упрежлены" вхолостую.
Отсюда и снижение произволнтельности. Поэтому на чипсете Н1А КТ!33 (и подобных ему) крайне не рекомендуется работать более чем с одним физическим потоком данных. Причем, выигрыш в оптимизации даже превосходит систему на базе Р-!!!/1815, — уже при 10 потоках наблюдается более чем пятикратный выигрыш! Не правда ли, Н!А КТ!33 — хороший чипсет? Особые случаи виртуализации потоков Однако на этом сюрпризы не заканчиваются. Все что мы вилим — это верхушка айсберга. А если копнуть вглубь? Вот, например, как вы думаете: на каком лтнинальноги расстоянии потоки данных могут располагаться друг от друга? Здравый смысл подсказывает: чем ближе — тем лучше.
А вот как бы не так! Особенности буферизации некоторых чипсетов (попросту говоря: "криво" реализованный механизм буферизации и/или неинтеллектуальной предвыборки) способен вызывать значительное снижение произволительности, если происходит попеременное обращение к "близким" (с точки зрения чипсета) ячейкам памяти. Рассмотрим пример, представленный в листинге 2.20. ; Пистинг2,20, Пример неэффективного кода (ие учитьгвающего,рсобвниостиг . 6уФеризаЦии,некоторых.'чипсвтсв,;:,' -.: '.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
