Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
22 слайда
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
268.20 kB
Просмотров:
48
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Есть ли у вас вопросы?](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img0.jpg)
Содержание слайда: Есть ли у вас вопросы?
№2 слайд![Краткое содержание этой серии](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img1.jpg)
Содержание слайда: Краткое содержание этой серии
Фокусы
Оптимизация компилятором
№3 слайд![Фокус Создаю глобальный](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img2.jpg)
Содержание слайда: Фокус №1
Создаю глобальный двухмерный массив
Заполняю его случайными числами
Вычисляю сумму всех элементов:
sum += array[i][j]
sum += array[j][i]
На ПК вариант а быстрее почти в 5 раз!
На МК никакой разницы нет.
ПОЧЕМУ?
№4 слайд![Фокус А как лежит в памяти](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img3.jpg)
Содержание слайда: Фокус №1
А как лежит в памяти двумерный массив?
№5 слайд![](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img4.jpg)
№6 слайд![Все дело в кэш-памяти Зачем](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img5.jpg)
Содержание слайда: Все дело в кэш-памяти
Зачем нужен кэш?
Чтобы ускорить доступ к часто используемым данным, т.к. оперативная память слишком медленная.
На МК кэш-памяти нет – поэтому нет никакой разницы между вариантами а и б.
№7 слайд![А как работает кэш? Кэш](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img6.jpg)
Содержание слайда: А как работает кэш?
Кэш состоит из «линий» (cache lines) -
при каждом обращении в память кэшируется несколько последовательных байт (64-128).
Если при обращении в память нужный элемент уже есть в кэше, то все хорошо (кэш-попадание).
Если нужного элемента в кэше нет – нужно пойти в память и считать линию (кэш-промах).
Кэш не бесконечен! Поэтому чтобы записать в него новую линию, нужно стереть старую.
№8 слайд![Кэш Вывод? Последовательный](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img7.jpg)
Содержание слайда: Кэш
Вывод?
Последовательный доступ к памяти гораздо быстрее, чем случайный.
С точки зрения железа самая быстрая структура данных – обычный массив (на не слишком большом количестве данных).
№9 слайд![Кэш В современных процессорах](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img8.jpg)
Содержание слайда: Кэш
В современных процессорах есть:
кэш данных (D-cache)
кэш инструкций (I-cache)
буфер ассоциативной трансляции (TLB)
Как правило, существует несколько уровней кэша.
№10 слайд![Кэш в современном процессоре](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img9.jpg)
Содержание слайда: Кэш в современном процессоре
№11 слайд![Кэш в современном процессоре](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img10.jpg)
Содержание слайда: Кэш в современном процессоре
Время чтения из памяти для Core i7-9xx:
L1 - 4 такта.
L2 - 11 тактов.
L3 - 39 тактов.
Основная ОЗУ – 107 тактов.
№12 слайд![Кэш Допустим, что два ядра](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img11.jpg)
Содержание слайда: Кэш
Допустим, что два ядра процессора обращаются к одной и той же переменной.
Тогда соответствующий кусок памяти будет закэширован дважды в двух кэшах L1.
А что будет, если одно ядро что-нибудь в эту переменную запишет?
Что тогда прочитает другое ядро?
Если доступ к переменной организован правильно, то все будет в порядке. Для программиста кэш в этом смысле «прозрачен».
Но за это придется платить скоростью работы..
№13 слайд![Кэш Допустим, что два ядра](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img12.jpg)
Содержание слайда: Кэш
Допустим, что два ядра процессора обращаются к двум разным переменным, которые расположены в памяти рядом.
Одна и та же кэш-линия опять-таки будет находится в двух кэшах.
Прозрачность кэша гарантирует, что значения переменных будут корректными.
Но для этого при каждой записи эта линия будет записываться в основную память и читаться опять! И скорость работы программы упадет.
Это называется «false sharing» (ложное разделение памяти).
№14 слайд![Фокус . Возьмем неудачный](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img13.jpg)
Содержание слайда: Фокус №1.5
Возьмем неудачный способ сложения элементов массива (по столбцам).
Логично предположить, что чем больше массив – тем больше времени занимает его обход.
Массив 4100х4100 обходится быстрее чем 4096х4096.
Степени двойки – это плохо?
№15 слайд![Ассоциативность кэша А как](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img14.jpg)
Содержание слайда: Ассоциативность кэша
А как узнать, закэширована переменная или нет?
Кэш прямого отображения - каждый адрес памяти может быть закэширован в одно, заранее определенное место в кэше.
Легко подвергается конфликтам.
Полностью ассоциативный кэш – любая переменная может быть закэширована в любой участок кэша.
Очень сложная реализация.
Частично ассоциативный кэш – каждая переменная может находится в нескольких, заранее определенных участках кэша.
Компромисс, используется на практике.
№16 слайд![Частично ассоциативный кэш](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img15.jpg)
Содержание слайда: Частично ассоциативный кэш
Например, 16-входовой частично ассоциативный кэш – линии кэша делятся на 16 групп.
Каждая переменная входит в одну группу и может входить только в линии кэша из этой группы.
Номер группы, как правило, определяется адресом переменной.
Переменные с адресами, кратными определенному числу, будут входить в одну группу и соревноваться за одни и те же линии кэша!
№17 слайд![Кэш для инструкций Линейный](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img16.jpg)
Содержание слайда: Кэш для инструкций
Линейный код (без переходов) выполняется быстрее
Маленькие программы (которые целиком помещаются в кэш) выполняются быстрее
№18 слайд![Выводы При оценке](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img17.jpg)
Содержание слайда: Выводы
При оценке быстродействия алгоритма нужно помнить про кэш.
Писать быстродействующие программы – это сложно.
Тестировать быстродействие – это сложно (разные процессоры, разные входные данные, «прогрев» кэша..).
№19 слайд![Фокус Вариант А Заполним](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img18.jpg)
Содержание слайда: Фокус №2
Вариант А:
Заполним одномерный массив случайными элементами.
Много раз найдем сумму всех элементов больше 128.
Вариант Б:
Заполним одномерный массив случайными элементами.
Отсортируем массив
Много раз найдем сумму всех элементов больше 128.
На МК вариант Б занимает больше времени.
На ПК вариант Б занимает существенно меньше времени.
Но почему?
№20 слайд![Предсказание переходов](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img19.jpg)
Содержание слайда: Предсказание переходов
Ключевой момент:
if (data[c] >= 128)
sum += data[c];
Если массив отсортирован – то переходы очень предсказуемы, предсказатель редко ошибается.
Если массив не отсортирован – предсказатель ошибается постоянно!
№21 слайд![Оптимизация Критерии](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img20.jpg)
Содержание слайда: Оптимизация
Критерии оптимизации:
по объему кода (бинарного файла)
по скорости исполнения
Иногда можно (и хочется) оптимизировать сразу по двум критериям, но не всегда.
№22 слайд![Оптимизация на пальцах У](/documents_6/2230f75dc5cf8589895052d4bcfbaf6b/img21.jpg)
Содержание слайда: Оптимизация «на пальцах»
У компилятора есть некая «область просмотра» (scope), в пределах которой он оптимизирует код:
одна строка
несколько строк, цикл
функция
файл
весь проект
Грубо говоря, чем больше эта область, тем лучше оптимизация.