ДС18в08-оптимизация (1238911)

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

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

Carnegie MellonОптимизация программОсновы информатики.Компьютерные основы программированияgoo.gl/X7evFНа основе CMU 15-213/18-243:Introduction to Computer Systemsgoo.gl/Q7vgWwЛекция 8, 26 марта, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.rucs.mipt.ru/wp/?page_id=3461Оптимизация программ¢¢ОбзорОптимизации полезные в общем случа姧§§¢Вынос кода, предварительные вычисленияУменьшение «стоимости» операцийИспользование общности подвыраженийИсключение обращений к процедурамПомехи оптимизации§ Обращения к процедурам§ Псевдонимы памяти¢¢Использование параллелизма командРабота с условными конструкциями2О реальной производительности¢¢Производительность зависит не только отасимптотической сложности алгоритмаПостоянные множители тоже имеют значение!§ Легко увидеть 10-кратное изменение быстродействия кода взависимости от качества его написания§ Оптимизация должна производиться на разных уровнях:§ алгоритмы, представление данных, процедуры, циклы¢Для оптимизации требуется системное понимани姧§§Как код компилируется и исполняетсяКак работают современные процессоры и памятиКак измерить быстродействие программ и найти узкие местаКак улучшить быстродействие не ухудшив модульности и общности3Оптимизирующие компиляторы¢Обеспечивают эффективное отображение кода на машин󧧧§¢распределение регистроввыбор и упорядочение кода (планирование)исключение неисполняемого кодаисключение мелких недостатковНе улучшают (обычно) асимптотическую сложность§ выбор наилучшего алгоритма в целом – задача программиста§ улучшение оценки O-большое (часто) более важно§¢но постоянные множители тоже имеют значениеЗатрудняются преодолеть помехи оптимизации§ возможность возникновения синонимов памяти§ возможность побочного эффекта от вызова процедуры4Ограничения компиляторов¢Фундаментальное ограничение§ Сохранять поведение программы в любых условиях§ Часто не позволяет выполнять оптимизации, которые изменяютповедение только в условиях, неактуальных для вашей задачи¢Очевидное программисту поведение может быть скрыто языком истилем написания программ§ например подразумеваемый диапазон данных может быть болееограничен, чем предполагается определением типа¢Почти весь анализ выполняется внутри процедур§ Анализ программы в целом в большинстве случаев слишком дорог§ Новые версии GCC выполняют межпроцедурный анализ внутри файла§¢¢Но не между различными файламиПочти весь анализ основан на статической информации§ Компилятору проблематично предвидеть ввод во время выполненияВ сомнительной ситуации, компилятор должен быть консервативен5Оптимизации, полезные в общем случае¢¢Оптимизации, которые должны быть сделанынезависимо от процессора и/или компилятораВынос кода§ Уменьшать количество повторений одинаковых вычислени駧если они всегда выдают одинаковый результатособенно важно выносить код из циклаvoid set_row(double *a, double *b,long i, long n){long j;for (j = 0; j < n; j++)a[n*i+j] = b[j];}long j;int ni = n*i;for (j = 0; j < n; j++)a[ni+j] = b[j];6Вынос кода компилятором (-O1)void set_row(double *a, double *b,long i, long n){long j;for (j = 0; j < n; j++)a[n*i+j] = b[j];}long j;long ni = n*i;double *rowp = a+ni;for (j = 0; j < n; j++)*rowp++ = b[j];set_row:testqjleimulqleaqmovl%rcx, %rcx.L1%rcx, %rdx(%rdi,%rdx,8), %rdx$0, %eaxmovsdmovsdaddqcmpqjne(%rsi,%rax,8), %xmm0%xmm0, (%rdx,%rax,8)$1, %rax%rcx, %rax.L3.L3:.L1:############Test nIf 0, goto doneni = n*irowp = A + ni*8j = 0loop:t = b[j]M[A+ni*8 + j*8] = tj++j:nif !=, goto loopdone:rep ; ret7Снижение «стоимост軧 Замена дорогостоящих операций более простыми§ Сдвиг и сложение вместо умножения и деления16*x -->x << 4§ Выгода зависит от машины§ Зависит от «стоимости» команд умножения и деления– На Intel Nehalem, целочисленное умножение требует 3 цикла ЦПfor (i = 0; i < n; i++)for (j = 0; j < n; j++)a[n*i + j] = b[j];int ni = 0;for (i = 0; i < n; i++) {for (j = 0; j < n; j++)a[ni + j] = b[j];ni += n;}8Использование общности подвыражений§ Повторное использование частей выражений§ Компиляторы не изощряются в арифметических преобразованиях/* Сумма соседей of i,j */up =val[(i-1)*n + j ];down = val[(i+1)*n + j ];left = val[i*n+ j-1];right = val[i*n+ j+1];sum = up + down + left + right;3 умножения: i*n, (i–1)*n, (i+1)*nleaqleaqimulqimulqimulqaddqaddqaddq1(%rsi), %rax-1(%rsi), %r8%rcx, %rsi%rcx, %rax%rcx, %r8%rdx, %rsi%rdx, %rax%rdx, %r8########long inj = i*n + j;up =val[inj - n];down = val[inj + n];left = val[inj - 1];right = val[inj + 1];sum = up + down + left + right;1 умножение: i*ni+1i-1i*n(i+1)*n(i-1)*ni*n+j(i+1)*n+j(i-1)*n+jimulqaddqmovqsubqleaq%rcx, %rsi # i*n%rdx, %rsi # i*n+j%rsi, %rax # i*n+j%rcx, %rax # i*n+j-n(%rsi,%rcx), %rcx # i*n+j+n9Блокировка оптимизаций №1: процедуры¢Процедура преобразования строки в нижний регистрvoid lower(char *s){int i;for (i = 0; i < strlen(s); i++)if (s[i] >= 'A' && s[i] <= 'Z')s[i] -= ('A' - 'a');}§ Взята из лабораторной работы10Быстродействие преобразования§ Время учетверяется при удвоении длины строки§ Квадратичная зависимость200180Секунды ЦП160140120lower11008060402000100000200000300000400000500000Длина строки11Преобразуем цикл в gotovoid lower(char *s){int i = 0;if (i >= strlen(s))goto done;loop:if (s[i] >= 'A' && s[i] <= 'Z')s[i] -= ('A' - 'a');i++;if (i < strlen(s))goto loop;done:}§ strlen выполняется на каждой итерации12Обращение к strlen/* Свой вариант strlen */size_t strlen(const char *s){size_t length = 0;while (*s != '\0') {s++;length++;}return length;}¢Быстродействие strlen§ Единственный способ определить длину строки – просканировать её повсей длине в поисках символа конца строки¢Общая сложность для строки длиной N§ N обращений к strlen§ Требует N, N-1, N-2, …, 1 операций§ Полная сложность - O(N2)13Улучшение производительностиvoid lower(char *s){int i;int len = strlen(s);for (i = 0; i < len; i++)if (s[i] >= 'A' && s[i] <= 'Z')s[i] -= ('A' - 'a');}§ Вынос из цикла обращения к strlen§ Возможно, т.к.

никакой результат не зависит от итерации§ Вариант выноса кода14Быстродействие преобразования§ Время удваивается при удвоении длины строки§ Линейная сложность lower2200180Секунды ЦП160140120lower110080604020lower200100000200000300000400000500000Длина строки15Помеха оптимизации: вызовы процедур¢Почему компилятор не может вынести strlen из цикла?§ Процедура может иметь побочный эффект§Изменение общего состояния при каждом вызове§ Функция может возвращать разные результаты для одинаковых аргументовВ зависимости от других частей общего состояния§ Вызывающая может взаимодействовать с вызываемой помимо аргументов§¢Предупреждение:§ Компилятор интерпретирует вызовпроцедуры как «чёрный ящи껧 Слабая оптимизация в его окрестности¢Лекарство:§ Вынос кода вручную§ Используйте inline функции§int lencnt = 0;size_t strlen(const char *s){size_t length = 0;while (*s != '\0') {s++; length++;}lencnt += length;return length;}GCC делает это с ключом –O1– Внутри одного файла16О памяти/* Суммировать строки матрицы n X nи сохранить в векторе b */void sum_rows1(double *a, double *b, long n) {long i, j;for (i = 0; i < n; i++) {b[i] = 0;for (j = 0; j < n; j++)b[i] += a[i*n + j];}}# sum_rows1 внутренний цикл.L4:movsd(%rsi,%rax,8), %xmm0addsd(%rdi), %xmm0movsd%xmm0, (%rsi,%rax,8)addq$8, %rdicmpq%rcx, %rdijne.L4# загрузка ЧПТ# сложение ЧПТ# выгрузка ЧПТ§ Код обращается к b[i] на каждой итерации§ Почему компилятор на может оптимизировать это выносом кода?17Псевдонимы памяти/* Суммировать строки матрицы n X nи сохранить в векторе b */void sum_rows1(double *a, double *b, long n) {long i, j;for (i = 0; i < n; i++) {b[i] = 0;for (j = 0; j < n; j++)b[i] += a[i*n + j];}}Значения B:double A[9] ={ 0,1,2,4,8, 16},32, 64, 128};init:double B[3] = A+3;i = 1: [3, 22, 16]sum_rows1(A, B, 3);i = 2: [3, 22, 224][4, 8, 16]i = 0: [3, 8, 16]§ Код изменяет b[i] на каждой итерации§ Компилятор должен учитывать возможность влияния этогоизменения на поведение всей программы целиком18Исключение псевдонимов/* Суммировать строки матрицы n X nи сохранить в векторе b */void sum_rows2(double *a, double *b, long n) {long i, j;for (i = 0; i < n; i++) {double val = 0;for (j = 0; j < n; j++)val += a[i*n + j];b[i] = val;}}# sum_rows2 inner loop.L10:addsd(%rdi), %xmm0addq$8, %rdicmpq%rax, %rdijne.L10# загрузка и суммирование ЧПТ§ Компилятор обнаружил, что нет необходимости сохранятьпромежуточный результат в памяти!19Помеха оптимизации: псевдонимы памяти¢Псевдонимы§ Два различных обращения в память, обращаются к одной ячейке§ Легко случается именно в Сиразрешена адресная арифметика§ прямой доступ к структурам хранения§ Возьмите за привычку использование локальных переменных§ для накопления в циклах§ способ исключить возможность псевдонимов как помехуоптимизации§20Использование параллелизма команд¢Необходимо общее понимание конструкциисовременных процессоров§ Аппаратура может выполнить несколько команд параллельно¢¢Быстродействие ограничено зависимостями данныхПростые изменения могут привести к радикальномуулучшению быстродействия§ Компиляторы часто неспособны выполнить такие изменения§ Отсутствие ассоциативности и дистрибутивности у арифметикис плавающей точкой21Пример оценки: тип данных в векторах/* структура данных для вектора */typedef struct{size_t len;data_t *data;} vec;¢Типы данных§ Используем различныеопределения data_t§ int§ long§ float§ doublelendata01len-1/* выбирает элемент вектораи сохраняет в val */int get_vec_element(*vec v, size_t idx, data_t *val){if (idx >= v->len)return 0;*val = v->data[idx];return 1;}22Вычисление оценокvoid combine1(vec_ptr v, data_t *dest){long int i;*dest = IDENT;for (i = 0; i < vec_length(v); i++) {data_t val;get_vec_element(v, i, &val);*dest = *dest OP val;}}¢Варианты типов данных§ int§ double¢Вычислить суммуили произведениеэлементов вектораВарианты операций§ Различные определенияOP и IDENT§ + / 0§ * / 123Циклов на элемент, Cycles Per Element (CPE)¢¢¢Удобный способ отображения быстродействия программы,работающей с массивами или спискамиДлина = nВ нашем случае: CPE = циклов на операциюT = CPE*n + накладные§ CPE – наклон прямой1000900vsum1: наклон = 4.0800700600Циклы¢500400vsum2: наклон = 3.53002001000050100150200n = количество элементов24Оценки быстродействияvoid combine1(vec_ptr v, data_t *dest){long int i;*dest = IDENT;for (i = 0; i < vec_length(v); i++) {data_t val;get_vec_element(v, i, &val);*dest = *dest OP val;}}Тип данныхОперацияintВычислить суммуили произведениеэлементов вектораdoubleсложение умножениесложение умножениеCombine1неоптимизирована22.6820.0219.9820.18Combine1 –O110.1210.1210.1711.1425Простейшие оптимизацииvoid combine4(vec_ptr v, data_t *dest){int i;int length = vec_length(v);data_t *d = get_vec_start(v);data_t t = IDENT;for (i = 0; i < length; i++)t = t OP d[i];*dest = t;}¢¢¢Вынос обращения к vec_length из циклаИсключение контроля границ в каждой итерацииНакопление во временной переменной26Эффект простейших оптимизацийvoid combine4(vec_ptr v, data_t *dest){int i;int length = vec_length(v);data_t *d = get_vec_start(v);data_t t = IDENT;for (i = 0; i < length; i++)t = t OP d[i];*dest = t;}Тип данныхОперацияCombine1 –O1Combine4¢intdoubleсложение умножениесложение умножение10.1210.1210.1711.141.273.013.015.01Исключены причины накладных в цикле27Конструкция современного ЦПУправлениеАдресаУправлениевыборкойУстройствозавершенияБлокрегистровКэшкомандДекодирование КомандыкомандОперацииИзменения регистровПредсказание верно?ПереходАрифм.Арифм.

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

Тип файла PDF

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

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

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