К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 31
Текст из файла (страница 31)
А что может быть быстрее линейного доступа? (Аналогичный вопрос: что может быть короче, чем путь по прямой). Вот с поиска ответов на такие вопросы и начинается проникновение в истинную сущность предмета обсуждения. В обработке независимых данных есть одна тонкость. Попытка одновременного чтения двух смежных ячеек в подавляющем большинстве случаев инициирует один, а не два запроса к подсистеме памяти. Это не покажется удивительным, если вспомнить, что минимальной порцией обмена с памятью является отнюдь не не байт, а целый покет, длина которого в зависимости от типа процессора варьируется от 32 до 128 байт.
Таким образом, линейное чтение независимых данных еи1е не обеспечивает их параллельной обработки (обстоятельство, о котором популярные руководства по оптимизации склонны умалчивать). Вернемся к нашей программе (см, листинг 2.9). Вот процессору потребовалось узнать содержимое ячейки *)СьЬ .) ) ЫьЬ) р1 + ь). ОН фОРМИРУЕт ЗаПРОС И НаПРаВЛЯЕт ЕГО ЧИПСЕтУ, а Саы тем временем приступает к обработке следующей команды — х ч= *) . ь *) ) ))чс)р1 ч а ч 4).
Ага, — думает процессор, — зависимости по данным нет и это хорошо! Но, с другой стороны, эта ячейка и без того возвратится с предыдущим запрошенным блоком, и посылать еще один запрос нет необходимости (чипсет, сколько его ни подгоняй, он быстрее работать не будет). Что ж, придется отложить выполнение данной команды до лучших времен. Так, что там у нас дальше?" Следую)цая команда- х ч= Ыьь ") ))сч~)р1 ч а ь 8) тоже отправляется на "консервацию", поскольку пытается прочесть ячейку из уже запрошенного блока. В общем, до тех пор, пока чипсет не обработает вверенный ему запрос, процессор (при линейном чтении данных!) ничего не делает, а только "складирует".
Затем, по мере готовности операндов, команды "размораживаются" и процессор завершает их выполнение. В конце концов процессору встречается команда, обращающаяся к ячейке, следующей за окончанием последнего запрошенного блока. "Эх, — "вздыхает" процессор, — если бы она мне встретилась раньше, я бы смог отправить чипсету сразу два запроса)" Более эффективный алгоритм обработки данных выглядит так: при первом проходе цикла память читается с вагам 32 байта (или б4/128 байт, если программа оптимизируетсн исключительно под АЯоп/Р-4), «то заставляет процессор генерировать запросы чипсету при каждом обрагцепии к памяти.
В результате на шине постоянно присутствуют несколько перекрывающихся запросов/ответов, обрабатывающихся параллельно (ну, почти параллельно). Во втором проходе цикла считываются все остальные ячейки, адреса которых не кратны 32 байтам. Поскольку на момент завершения первого прохода они уже находятся в каше, обращение к ним не вызовет больших задержек (рис. 2.16).
Оперативная память Рис. 2.16. Два варианта чтения ячеек памяти. По возможности избегайте линейного чтения ячеек. Лучше на первом проходе цикла читать ячейки с шагом, кратным размеру пакетного цикла обмена, а оставшиеся ячейки обрабатывать как обычно Рассмотрим усовершенствованный вариант программы параллельного чтения независимых данных (листинг 2.10). (Полный исходный текст программы читатель найдет в файле ~Бгс'([2).гпегпо(у~рагапе!.(еБ(.с, который находится на прилагаемом компакт-диске.) ьм измерение пропускной способности при параллельном чтении данных ()бе11пе В1~ХК 812Е (32*и) // размер обрабатываемого блока ()бегхпе Бтег Бгзе Вз сасне Бгзе О размер обрабатываемого полблока Гог (Ь=сг Ь < ВЬССК 812Е; Ь т= БтЕР 818Е) ( // первьй проход цикла, в котором осуществляется // параллельная загрузка данных Гог (а Ь| а < (Ь ь ВТЕР 81ЕЕ)г а += 128) ( // загружаем первую ячейку; // поскольку ее пока нет в кэще, Гпааа и // процессор отправляет чипсету // запрос на ее чтение х += * Ипб *) ( Ипо) р + а + О); // загружаем следукхш/ю ячейку // поскольку зависимости по данным нет, // процессор может выполнять эту команду, // не дожидаясь результатов предмпущей // но поскольку процессор "видит", что // данная ячейка не возвратится с // только что запрошенным блоком, // он направляет чипсету еще один запрос, // не дожидаясь завершения предыдущего х += *Ипс *) (Ипс)р + а + 32)( // на шину отправляется четвертый запрос, // причем первый запрос возможно еще и // не завершен х += *Ипс *)((1пс)р + а т 96); бог (а = Ь; а < (Ь + кткг 818к); а += 32) // следующую ячЕйку читать не надо // т.
к. она уже прочитана в первом цикле // х + * Ипс *)( Ипс)р + а + О)) эти ячейки уке будут в кэше( они смогут загрузиться быстро-быстро! *Ипв *) (Ипе)р + а т 4); *(3лб *) (Ипс)р + а + 8) ) *Иле *) ( Ипв) р + а + 12); *ипс *) (()лс)р т а + 16) ) *Ипб *) (Ипе)р + а т 20) у *Иле *) ((кпв)р т а + 24); *(1пе *) ((клв)Р т а + 28) 4 // а // и х + О аналогично — теперь на шине уже три запроса! Х + * (1ПС *) ((кпе) р + а + 64) ) Оперативная память 145 На Р-П1 733/133/100 такой трюк практически в полтора раза обгоняет алгоритм линейного чтения, достигая пропускной способности порядка 600 Мбит/с, что лишь на 25% меньше теоретической пропускной способности (рис. 2.17).
Еше лучший результат наблюдается на А1)!1оп, всего на 20% не дотянувшем до идеала. Смотрите, латентность его неповоротливого чипсета практически полностью компенсирована, а сама система прямо-таки дышит мощью и летает, будто ей в вентилятор залетел шмель! И это притом, что сама тестовая программа написана на чистом С без каких-либо "хаков" и ассемблерных вставок! (То есть резерв для увеличения производительности еше есть!) Рис.
2.17. Демонстрация эффективности параллельного чтения. На Ан!О А!Шоп 1050/100/100/Ч!А КТ133 этот простой и злегантный трюк обеспечивает более чем двукратный прирост производительности. На Р-!П 733/133/100/!815ЕР выигрыш, правда, гораздо меньше — 20%, но все равно более чем ощутим Оптимизация ссылочных структур данных Итак, если мы не хотим, чтобы наша программа ползала со скоростью черепахи в летний полдень и на полную использовала преимушества высоко- 146 Глава 2 производительной ПВК- и КОКАМ-памяти, то следует обязательно устранить зависимость по данным. Как это сделать? Вот, скажем, графический файл в формате ВМР, действительно, можно обрабатывать и параллельно, поскольку он представляет собой однородный массив данных фиксированного размера.
Совсем иная ситуация складывается с двоичными деревьями, списками и прочими ссылочными структурами, хранящими разнородные данные. Расщепление списков (деревьев) Рассмотрим список, "связывающий" пару десятков мегабайт текстовых строк переменной длины. Как оптимизировать прохождение по списку, если адрес следующего элемента заранее неизвестен, а список к тому же сильно фрагментирован? Первое, что приходит на ум: разбить один сливок на несколько независимых квасков, обработка которых осу(кесталяется лараллвльио. Остается выяснить: какая именно стратегия разбиения наиболее оптимальна.
В этом нам поможет следующая тестовая программа, последовательно прогоняющая списки с различной степенью дробления (1:1, 1:2, 1:4, 1:6 и 1:8). Ниже, по соображениям экономии бумажного пространства, приведен лишь фрагмент, реализую(ций комбинации 1:1 и 1;2 (листинг 2.11). Остальные же степени дробления реализуются полностью аналогично. (Полный исходный текст программы читатель найдет в файле ~кгс~[2]лпетоту~11какр11пас, который находится на прилагаемом компакт-диске.) Фбегтпе ВЬССК 3222 (тг*м( // размер обрабатываемого бдона атгпсс мтыкт( // элемент списка асгпсс муывт *пенс; тпе гаги Фбеттпе М КККМ (вкоск вткк/атэеот(асгпст мтызт(( обработка одного списка (/пвратианая память // инициализация тот (а = 0) а с М ЕЪЕМ; атт) опе 11зт(а] .пехс = опе 11вт + а + 1; опе 11зг(а].ча1 = а! ) опе 11зг[м елен-1].пехт = 0) // трассировка р = опе 11зс) им11е(р = р(0).пехл); обработка двух расщепленных списков // инициализация гог (а = 0; а < и елен/2) а++) зр1 11вл 1(а).пехт = зр1 11зк 1 + а + 1ь зр1 11зл 1[а).
га1 а) зр1 11зс 2(а).пехс = зр1 11вс 2 + а + 1; зр1 11вг 2[а].ча1 = а! ) зр1 аавт 1[М ЕЛЕЕ/2-1).пехт = 0; зр1 )азс г(М ЕЛЕМ/2-1).пехс = а; // трассировка р1 = зр1 11зт 1; р2 = зр1 11зл 2; им11е((р1 = р1[0).пехт) зз (р2 = р2(0].пенс)) // внимание( Данный способ трассировки предполагает, что оба // списка равнм по количеству элементов, в противном случае // потребуется слегка доработать код, например, так: // ипгле(р1 (( рг) // // 11 (р1) р1 = р1(0) .пехт> // 12 (р2) р2 = р2[0].пехс; // ) // однако это сделает его менее нагляднька, поэтому в книге // приводится первый вариант Глава 2 На Р-Ш 733/133/100/1815ЕР (рис. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
