08-realworld (1238883)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

REAL WORLD CЯзык программирования C в реальном мире. Конвейермикропроцессора. Предсказания переходов. Промахи по памятиК. Владимиров, Intel, 2019mail-to: konstantin.vladimirov@gmail.comЗагадочная проблема•Следующий код суммирует все элементы массива, меньшие, чем 128for (j = 0; j < len; ++j)if (arr[j] > 128)sum += arr[j];•Проблема в том, что для несортированных массивов он (без изменений всамом коде) работает почти в четыре раза медленнее, чем длясортированных•См. пример bmystery.c в файлах к семинару•Предположим, необходимо эффективно обрабатывать именнонесортированные массивы•Значит надо понять почему происходит замедление и как это исправитьКонвейер микропроцессораInstructionfetchmovsaraddadcaddcmpInstructiondecode,register fetchebx,ebx,esi,edi,eax,eax,ecx31ecxebx4edxExecuteMemoryaccessexecuted, writes ebx backexecuting (waiting ebx)decodedfetchedRegisterwrite backПроблема переходовInstructionfetchmovcmpjlemovsaraddadcL3:Instructiondecode,register fetchecx,ecx,L3ebx,ebx,esi,edi,ExecuteMemoryaccessDWORD PTR [eax] doing memory access (LSQ)executing (waiting ecx)128ecx31ecxebxdecoded (known to be jump)fetched?Registerwrite backПредсказание переходов•Используется конечный автомат, работающий на истории переходов•Проследим работу на простом циклеfor (j = 0; j < 100; ++j) {x = (x + j) & 78;}•Предсказание для достаточно больших циклов почти всегда верноеПредсказание переходов•Теперь странности исчезаютfor (j = 0; j < len; ++j)if (arr[j] > 128) // тут случайное значениеsum += arr[j];•Вероятность правильного предсказания перехода теперь...

а кстати, какая?•Точный ответ дать тяжело. К тому же, модель автомата на прошлом слайдеочень условная: в современных процессорах стоят гораздо более сложныесхемы•Но всегда можно посмотреть, используя профайлерПредсказание переходов•Следующий скриншот получен с Intel Vtune•Итак, четверть бранчей не угадывается. Что делать?Хитрая оптимизация•Используя знание ассемблера, можно вообще убрать переходfor (j = 0; j < len; ++j) {for (j = 0; j < len; ++j) {if (arr[j] > 128)int tmp = (arr[j] > 128);sum += arr[j];}sum += (arr[j] * tmp);}Хитрая оптимизация•Используя знание ассемблера, можно вообще убрать переходL4:L3:movcmpjlemovsaraddadcecx,ecx,L3ebx,ebx,esi,edi,DWORD PTR [eax]128addcmpjneeax, 4eax, edxL4ecx31ecxebxL3:movxorcmpsetgimulcdqaddadcaddcmpjneedx,eax,edx,aleax,DWORD PTR [ecx]eax128esi,edi,ecx,ebx,L3eaxedx4ecxedxОбсуждение•В данном случае стало в несколько раз лучше•Должны ли мы рассматривать возможность делать такого рода оптимизации?•Не опасно ли их делать?Интермедия:out-of-order•Слайд с конвейером мог ввести взаблуждение•На самом деле инструкцииисполняются не так уж линейно•Важная часть конвейера –планировщик который раскидываетинструкции по ALU, учитывая ихспецифику и взаимосвязи•Это делает mispredict ещё хужеЗагадочная проблема #2•Следующий код вычисляет сумму элементов двумерного массиваfor (j = 0; j < len; ++j)for (i = 0; i < ARRSZ; ++i)sum += arr[i][j];•Он начинает работать в несколько раз (!) быстрее, если переставить местамициклыfor (i = 0; i < ARRSZ; ++i)for (j = 0; j < len; ++j)sum += arr[i][j];•Почему? Ответ будет долгий.Память с произвольным доступом•Грубо можно классифицировать память на динамическую и статическуюЯчейка Dynamic RAMЯчейка Static RAMПамять с произвольным доступом•Статическая памятьбыстрее, но намногодороже.

Поэтому то, что мыназываем "оперативкой" этообычно DRAM•В современных условиях этоDDR, реже SDR•SRAM используется, чтобыкэшировать недалеко отпроцессора частоиспользуемые данныеИдея кэширования•Допустим вы делаете обращение в памятьint b = a[0]; // около 100 наносекунд•Процессор предполагает что следующее обращение будет недалеко изагружает всю кэш-линию (около 64 байт) в L1 кэшint с = a[1]; // около 0.5 наносекунд•В современных процессорах есть много уровней кэшей и данные, которые невлезают (или вытесняются) из кэша L1 попадают в L2, а потом и в L3.•В итоге чем активнее программа использует данные, тем быстрее у неё к нимдоступИерархия памятиВид памятиПримерное время доступа Примерный размер*L1 cacheL2 cache0.5 ns7 nsL3 cacheRAM20 ns100 nsHDD (считать 4Kb) 150000 ns256 Kb1 Mb8 Mb8 Gb1 TbЦена одного branch mispredict приблизительно равна цене одного cachemiss с обращением в L2*для coffee lake, i5-8300HЛокальность данных•Теперь загадка развеивается.

Двумерные массивы лежат в памятинепрерывным куском•Следующий цикл обращается к каждому n-ному элементуfor (j = 0; j < len; ++j)for (i = 0; i < ARRSZ; ++i)sum += arr[i][j];•Он делает cache miss каждый раз•Разумеется, если его переписать, всё становится куда лучшеИспользование профилировщика•Как обычно профилировка позволяет показать довольно точноераспределение промахов по уровням кэшей для каждой строчки•После этого можно смотреть код и делать выводы•Обратите внимание: на скриншоте из-за погрешности отладочнойинформации мы видим смещение на одну строчкуБолее сложный пример•Представьте, что у вас есть код, выполняющий перемножение матрицvoid matrix_mult(const int *A, const int *B, int *C,int AX, int AY, int BY) {for(int i = 0; i < AX; i++)for(int j = 0; j < BY; j++) {C[i * BY + j] = 0;for(int k = 0; k < AY; k++)C[i * BY + j] += A[i * AY + k] * B[k * BY + j];}}•Будет ли здесь влиять перестановка строчек внешних циклов? Если да то как,если нет, то почему?Математика идёт на помощь−1•Запишем = ෍ =0••Теперь можно заметить, чтонелокальность вычисленийпроистекает из того факта, чтообращения к второй матрицепроисходят втранспонированном видеРади улучшения локальности мыможем завести дополнительнуюматрицу и транспонировать еёsize_t bsz = BIG_BY * BIG_AY * sizeof(int);int *tmp = (int *) malloc(bsz);for(int i = 0; i < AY; i++)for(int j = 0; j < BY; j++)tmp[j * AY + i] = B[i * BY + j];for(int i = 0; i < AX; i++)for(int j = 0; j < BY; j++) {C[i * BY + j] = 0;for(int k = 0; k < AY; k++)C[i * BY + j] +=A[i * AY + k] * tmp[j * AY + k];}free(tmp);Клеточное перемножение•Ульрих Дреппер в своей замечательной статье предлагает ещё болееинтересный подходint SM = L1_LINE_SIZE / sizeof (int);for (i = 0; i < AX; i += SM)for (j = 0; j < BY; j += SM)for (k = 0; k < AY; k += SM)for (i2 = 0, rres = &C[i * BY + j], rmul1 = &A[i * AY + k];i2 < SM; ++i2, rres += BY, rmul1 += AY)for (k2 = 0, rmul2 = &B[k * BY + j];k2 < SM; ++k2, rmul2 += BY)for (j2 = 0; j2 < SM; ++j2)rres[j2] += rmul1[k2] * rmul2[j2];Обсуждение•Из-за предсказания бранчей, клеточное перемножение на замерах ведёт себячуть хуже, чем подход с транспонированной матрицей•Кроме того там накладывается важное ограничение: размеры матрицдолжны нацело делиться на SM иначе нужно писать чуть больше кода чтобыучесть краевые эффекты•Зато этот метод не требует дополнительной памятиЗадача•Предположим, что вы не знаете размер кэшей на вашем компьютере•И у вас нет документации•Интернета чтобы её поискать тоже нет•Как бы вы его выяснили?Метод Монте-Карло•Предположим, у нас есть массив размера •Если к этому массиву обращаться (например инкрементировать элементы)последовательно и замерить время 1•А потом сделать такое же количество обращений по случайным адресам изамерить время 2•То что нам скажет соотношение 1 и 2 для разных ?•Можем ли мы использовать этот метод для оценки эффективного размеракэшей на своей машине?•Проведите соотв.

эксперименты и замерыЭффекты кэшей и асимптотика•Плохая кэш-локальность может снизить производительность в 20-30 раз•Предположим, что у вас есть выбор между алгоритмом O(NlogN) с хорошейлокальностью данных и алгоритмом O(N) с плохой локальностью•Каким должен быть выбор для разных N?Кэш как структура данных•Есть страницы по 64 байта, включая номерstruct page {int index;// page index: 1, 2, ... nchar data[60]; // page data};•Также существует медленная функцияvoid slow_get_page(int n, struct page *p);•Необходимо завести кэш для обращений к страницам•Считаем, что всего в кэше места не больше, чем на m страниц, m многоменьше nКэш как структура данных•Какую структуру данных выбрать для кеша?•Какую стратегию кэширования выбрать?•Например у нас есть место на 3 страницы и к нам поступают запросы:1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 3•В какой момент страница кэшируется?•В какой момент страница вытесняется из кэша?Кэш как структура данных: LRU•Стратегия LRU (least recently used) подразумевает очередь в которойэлементы индексируются хеш-таблицей•Если запрошенный элемент найден, он передвигается вперёд, если ненайден, то добавляется спереди, а задний вытесняется•Например у нас есть место на 4 страницы и к нам поступают запросы:1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 3•Тогда кэш меняется так1 → 2, 1 → 3, 2, 1 → 4, 3, 2, 1 → 1, 4, 3, 2 → 2, 1, 4, 3→ 5, 2, 1, 4 → 1, 5, 2, 4 → 2, 1, 5, 4 → 3, 2, 1, 5→ 4, 3, 2, 1 → 3, 4, 2, 1Problem LC – LRU кэш•Необходимо написать код функцииstruct page {int index;// page index: 1, 2, ...

nchar data[60]; // page data};void slow_get_page(int n, struct page *p);void get_page(int id, struct page *p) {// TODO: заполнить структуру *p используя кэш}•Функция должна обеспечивать переиспользование страниц не худшее, чемпри стратегии LRUPrefetch•Техника предвыборки (prefetch) служит для того, чтобы подкачать в кэшданныеfor (int i = 0; i < ARRSZ; ++i) {a[i] = a[i] + b[i];__builtin_prefetch(a[i+1]);__builtin_prefetch(b[i+1]);}•Здесь до перехода будут подкачаны значения для вычисления следующейитерации циклаInstruction cache•Инструкции это тоже данные•Конвейер декодировав инструкцию сохраняет её в кэш инструкций•Таким образом, кроме branch mispredict можно рассматривать instructioncache miss•Но обычно в процессоре достаточно большой кэш инструкций: речь идёт очём-то около 32 килобайт на каждое ядро и поэтому наглядно увидетьэффекты на простом приложении сложно•Сможете ли вы самостоятельно придумать эксперимент на кэш инструкций?Литература•С11 ISO/IEC – "Information technology – Programming languages – C", 2011•& Brian W.

Kernighan, Dennis Ritchie – The C programming language, 1988• Intel Software Developer Manual: intel-sdm• John Hennesy, David Patterson – Computer Architecture: A QuantitativeApproach, 2011• Ulrich Drepper – What Every Programmer Should Know About Memory, 2007• Peter van der Linden – Expert C Programming: Deep C Secrets, 1994.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций