Машинное обучение и нейронные сети - страница 29

[MetaQuotes]

MIT 6.172 Performance Engineering of Software Systems, Fall 2018 — 1. Введение и умножение матриц

1. Введение и умножение матриц

В этом видео на YouTube под названием «1. Введение и матричное умножение» лектор обсуждает важность разработки производительности и то, как она развивалась с течением времени. На примере умножения матриц докладчик показывает, как методы кодирования и технические характеристики машин могут сильно повлиять на производительность. Обсуждение охватывает такие темы, как порядок циклов, использование кэша и параллельное программирование. Спикер также исследует способы оптимизации кода под разные процессоры и арифметические вычисления. В целом, видео дает ценную информацию о мире инженерии производительности и ее практическом применении в современных вычислительных системах.

• 00:00:00 В этом разделе лектор обсуждает важность разработки производительности и почему ее изучают. Производительность не всегда является главным приоритетом, когда речь идет о разработке программного обеспечения. Однако это валюта вычислений, и она используется для покупки других желаемых свойств, таких как простота программирования, безопасность и корректность. Снижение производительности может привести к тому, что программное обеспечение станет непригодным для использования, и основная жалоба людей на вычислительные системы заключается в том, что они слишком медленные. Таким образом, хотя производительность может не иметь внутренней ценности, она способствует тому, что волнует разработчиков.
  
  
• 00:05:00 В этом разделе спикер обсуждает историю проектирования производительности в вычислениях и переход от первых дней интенсивного проектирования производительности из-за ограниченных машинных ресурсов к эпохе закона Мура, когда плотность чипов удваивалась каждые два года и ожидания для оборудования, чтобы догнать, было более выгодным, чем оптимизация программного обеспечения. Однако выступающий отмечает, что масштабирование Деннарда, которое позволяло увеличивать тактовую частоту за счет снижения энергопотребления, прекратило свое существование в 2004 году, и поэтому потребность в разработке производительности важна как никогда раньше. Спикер включает цитаты ученых-компьютерщиков Дональда Кнута, Билла Вулфа и Майкла Джексона о важности читаемого кода и предостережения от преждевременной оптимизации.
  
  
• 00:10:00 В этом разделе спикер обсуждает ограничения тактовых частот, которые были достигнуты в начале 2000-х из-за плотности мощности, что привело к разработке многоядерных процессоров для масштабирования производительности. Однако это означало, что производительность больше не была бесплатной и требовала параллельного программирования, чего раньше в отрасли не было. С этого момента программное обеспечение должно было адаптироваться к новым аппаратным конфигурациям, чтобы быть эффективным, и в результате повышенное внимание уделялось производительности при разработке программного обеспечения.
  
  
• 00:15:00 В этом разделе спикер начинает с объяснения практической и теоретической важности обучения написанию программного обеспечения, которое эффективно использует современное оборудование. Затем они приводят пример проектирования производительности, используя хорошо изученную проблему матричного умножения, обсуждая машину, которую они будут использовать, включая ее характеристики и возможности, такие как параллельная обработка, размер кэша и объем памяти, и заканчивая объяснением базовый код для Python для умножения матриц. Спикер подчеркивает мощность машины и потенциал для забавных проектов, использующих ее возможности.
  
  
• 00:20:00 В этом разделе лектор обсуждает производительность Python, Java и C++ в контексте умножения матриц. Лекция демонстрирует, что Python слишком медленный для умножения больших матриц, его время выполнения составляет примерно 21 000 секунд, Java быстрее и обеспечивает почти в девять раз ускорение по сравнению с Python, а C++ является самым быстрым со временем выполнения примерно 1100 секунд. , что в два раза быстрее, чем Java, и в 18 раз быстрее, чем Python.
  
  
• 00:25:00 В этом разделе спикер обсуждает различия в производительности между интерпретируемыми языками, такими как Python, компилируемыми языками, такими как C, и такими языками, как Java, которые компилируются в байт-код, а затем интерпретируются. Интерпретаторы, такие как Python, универсальны, но медленны, тогда как компиляторы, такие как C, используют аппаратные и машинные инструкции для оптимизации производительности. Компиляторы JIT, подобные используемым в Java, восстанавливают некоторую производительность, компилируя только наиболее часто выполняемые фрагменты кода. Спикер отмечает, что модель производительности Python сложна для понимания, поэтому они будут использовать C для сравнения производительности в курсе. Тем не менее, будет гостевая лекция, на которой они обсудят разработку производительности в управляемых языках, таких как Python.
  
  
• 00:30:00 В этом разделе обсуждается важность порядка цикла для производительности при умножении матриц. Порядок циклов влияет на расположение кеша, что влияет на время выполнения. Матрицы размещаются в памяти по строкам в C и по столбцам в Fortran. Шаблон доступа для порядка ijk имеет хорошую пространственную локальность для C, но плохую пространственную локальность для B. Инструмент «cachegrind» полезен для определения частоты промахов для кода, а простые изменения, такие как настройка флагов компилятора, также могут повысить производительность.
  
  
• 00:35:00 В этом разделе спикер обсуждает, как оптимизировать код, чтобы повысить производительность машины. Важно выбрать хороший флаг оптимизации, такой как -O2 или -O3, но иногда более низкий флаг оптимизации может фактически улучшить оптимизацию в зависимости от кода. Кроме того, многоядерные процессоры могут использоваться с параллельными циклами с использованием шелковой инфраструктуры, что приводит к ускорению почти в 18 раз на 18 ядрах. Спикер подчеркивает, что распараллеливание внешних циклов более эффективно, чем распараллеливание внутренних циклов, которые могут замедлить работу программы. Тем не менее, все еще есть источники возможностей для оптимизации, такие как промахи кэша и неэффективное использование векторизованных инструкций.
  
  
• 00:40:00 В этом разделе спикер обсуждает, как лучше справляться с промахами в кеше, реструктурируя вычисления для максимально возможного повторного использования данных в кеше. Используя мозаичную схему, матрицы разбиваются на более мелкие подматрицы и умножаются на блоки, чтобы уменьшить количество необходимых обращений к памяти. Докладчик объясняет, что параметр настройки необходим для определения размера подматриц, и предлагает экспериментировать — лучший способ найти оптимальное значение. С помощью этого подхода докладчик демонстрирует, что можно значительно сократить количество обращений к памяти, необходимых для вычисления того же размера, что делает вычисления более эффективными.
  
  
• 00:45:00 В этом разделе докладчик обсуждает преимущества использования блокировки или разбивки на листы при выполнении матричного умножения, такие как улучшенное использование кэша и более быстрое время выполнения. Они объясняют различные уровни кэш-памяти чипов и то, как программисты могут использовать параметры настройки для оптимизации своего кода для каждого уровня кэш-памяти. Однако процесс настройки усложняется с каждым уровнем кэша, а код становится трудным для чтения и понимания. Докладчик предлагает подход «разделяй и властвуй», который использует параллельное программирование для рекурсивного решения более мелких подзадач. Хотя этот метод улучшает использование кэша, накладные расходы на вызовы функций замедляют вычисления, подчеркивая необходимость продуманного проектирования производительности.
  
  
• 00:50:00 В этом разделе спикер обсуждает оптимизацию умножения матриц методом «разделяй и властвуй» и корректировку порога использования алгоритма. Базовый случай устанавливается, когда порог ниже определенного числа, и алгоритм использует обычное матричное умножение. Было обнаружено, что наилучшее значение для базового варианта равно 32, что дает время выполнения 1,3 секунды и 12% пиковой производительности. Кроме того, спикер представляет концепцию векторизации с использованием векторного оборудования, которое обрабатывает данные в одной инструкции, множественном формате данных. Докладчик описывает различные способы оптимизации векторизации, включая использование отчетов о векторизации, флагов для конкретных архитектур и флага быстрой математики, который позволяет компилятору переупорядочивать ассоциации. Использование встроенной в архитектуру и быстрой математики приводит к удвоению производительности при использовании любого векторизатора компилятора.
  
  
• 00:55:00 В этом разделе видео спикер обсуждает различные битовые размеры, используемые для арифметических вычислений, причем 64-битный является наиболее распространенным для вычислений линейной алгебры. Они также упоминают, что арифметика с более низкой точностью может использоваться для приложений ИИ для повышения производительности. Далее докладчик рассказывает об использовании векторных инструкций и встроенных функций AVX, которые обеспечивают пиковую производительность до 41% и ускорение примерно на 50 000. Они предупреждают, что улучшения производительности, аналогичные тем, которые достигаются при матричном умножении, могут не наблюдаться в других областях, но этот курс научит студентов, как добиться существенного улучшения производительности самостоятельно. Кроме того, курс будет посвящен многоядерным вычислениям, а не графическим процессорам или другим областям.

[MetaQuotes]

Лекция 2. Правила Bentley по оптимизации работы

2. Правила Bentley по оптимизации работы

В этом видео на YouTube обсуждаются различные методы оптимизации компьютерных программ. Вводятся правила Bentley для оптимизации работы, а оптимизации сгруппированы по структурам данных, циклам, логике и функциям. Обсуждаются различные методы, такие как кодирование значений, расширение структуры данных, предварительное вычисление, кэширование и использование разреженных матриц. Докладчик также коснулся преимуществ использования разреженного матричного представления для графиков, оптимизации логики и оптимизации обнаружения коллизий в графических программах. Реализация этих методов оптимизации помогает сократить время работы программ, делая их более эффективными.

Вторая часть видео охватывает несколько категорий методов оптимизации, включая подъем циклов, использование часовых в циклах, развертывание и слияние циклов, а также встраивание функций. Спикер не советует преждевременную оптимизацию и подчеркивает важность соблюдения корректности и использования регрессионного тестирования. В видео также рассказывается о правилах оптимизации работы Bentley — шестиэтапном руководстве по повышению производительности и эффективному достижению целей. Эти правила включают установление четких целей, разбивку задач, планирование и организацию, определение приоритетов задач, минимизацию отвлекающих факторов, а также регулярный пересмотр и корректировку своего подхода.

• 00:00:00 В этом разделе лектор вводит понятие оптимизации работы в компьютерных программах и объясняет, как сокращение работы программы может повысить ее производительность. Он также рассказывает о правилах оптимизации работы Бентли, названных в честь Джона Льюиса Бентли, написавшего книгу о написании эффективных программ. Оптимизации сгруппированы в четыре категории: структуры данных, циклы, логика и функции, и лектор планирует охватить все 22 правила в серии мини-лекций на протяжении всего курса. Хотя сокращение работы программы является хорошей эвристикой для сокращения времени ее выполнения, сложная природа компьютерного оборудования означает, что это не всегда приводит к сокращению времени выполнения, поэтому лектор также расскажет об оптимизации, специфичной для архитектуры, позже в этом разделе. курс.
  
  
• 00:05:00 В этом разделе видео спикер обсуждает концепцию упаковки и кодирования структур данных для хранения более одного значения данных в машинном слове и преобразования значений данных в представление, требующее меньшего количества битов. Уменьшая количество вещей, которые нужно перемещать в памяти, это становится хорошей эвристикой для сокращения времени работы программы. Спикер приводит пример кодирования дат для их хранения с использованием меньшего количества битов, чтобы упростить получение месяца, года или дня для определенной даты. Докладчик предлагает использовать возможности битовых полей языка C для хранения структурированных данных, что сделает их более доступными. Это представление требует немного больше битов, но гораздо эффективнее при доступе к определенным значениям данных в структуре.
  
  
• 00:10:00 В этом разделе видео обсуждаются три метода оптимизации. Первый метод заключается в том, чтобы решить, следует ли кодировать значения как последовательные целые числа или распаковывать их для более быстрого доступа. Второй метод — это увеличение структуры данных, когда добавление информации в структуру данных может оптимизировать общие операции. Примером может служить добавление хвостового указателя к односвязному списку, чтобы сделать добавление двух списков более эффективным. Третий метод — предварительное вычисление, которое заключается в выполнении расчетов заранее, чтобы избежать выполнения вычислений в критические моменты времени. Примером является использование треугольника Паскаля для предварительного вычисления биномиальных коэффициентов, чтобы ускорить программу, которая их использует.
  
  
• 00:15:00 В этом разделе спикер обсуждает, как предварительно вычислить треугольник Паскаля, используя рекурсивную формулу и код C. Они объясняют, что рекурсивная формула включает в себя вызов функции выбора и то, как предварительно вычислить таблицу во время выполнения с помощью цикла. Кроме того, они обсуждают, как инициализировать таблицу во время компиляции, помещая значения таблицы в исходный код, что экономит время во время выполнения программы. Наконец, они предоставляют пример таблицы биномиальных коэффициентов до 10, к которой можно получить доступ во время выполнения программы.
  
  
• 00:20:00 В этом разделе спикер представляет концепцию метапрограммирования как способ избежать ручного ввода в программу больших таблиц постоянных значений. Написав программу, генерирующую необходимый код, утомительную задачу можно выполнить автоматически. В качестве примера спикер приводит фрагмент кода Python. Также рассматривается тема кэширования как метода, позволяющего избежать повторения дорогостоящих вычислений за счет сохранения недавно использованных результатов в кэше. В приведенном примере вычисляется гипотенуза прямоугольного треугольника с использованием оператора квадратного корня, где кэш предварительно сохраняет предыдущие гипотенузы вместе со значениями a и b. Функция гипотенузы сначала проверяет, совпадают ли входные значения со значениями в кэше, и если да, то возвращает кэшированное значение без повторного вычисления квадратного корня.
  
  
• 00:25:00 В этом разделе спикер обсуждает концепцию кэширования для оптимизации работы в программе. Сохраняя часто вычисляемые значения в кэше, программы могут сэкономить время, поскольку им не нужно повторно вычислять одни и те же значения. Хотя аппаратное обеспечение также выполняет кэширование, программное обеспечение также может это делать, например, кэш размером 1000, в котором хранятся 1000 последних вычисленных значений. Оптимизация может ускорить программу примерно на 30%, если одни и те же значения вычисляются повторно. Затем докладчик представляет идею использования разреженности во входных данных, чтобы избежать вычислений с нулевыми элементами этих входных данных, тем самым экономя время вычислений. Они демонстрируют это на примере умножения матриц на вектор и вводят структуру данных сжатой разреженной строки (CSR), которая может ускорить умножение матриц.
  
  
• 00:30:00 В этом разделе спикер обсуждает, как оптимизировать хранение и вычислительную эффективность разреженных матриц с помощью формата Compressed Sparse Row (CSR). Формат CSR хранит ненулевые элементы матрицы в трех массивах: массив значений, массив столбцов и массив строк. Докладчик объясняет, как вычислить длину строки и как выполнить умножение матрицы на вектор с использованием формата CSR. Формат CSR может быть более компактным, чем плотное матричное представление, если количество ненулевых элементов значительно меньше, чем N^2. Однако для относительно плотных матриц представление плотной матрицы может занимать меньше места. Докладчик приводит пример кода для выполнения умножения матрицы на вектор с использованием формата CSR.
  
  
• 00:35:00 В этом разделе инструктор обсуждает преимущества использования разреженной матрицы для представления графа и то, как ее можно использовать для более эффективного запуска классических алгоритмов графа, таких как поиск в ширину и PageRank. Представление разреженного графа состоит из двух массивов: смещений и ребер, где степени каждой вершины можно получить, взяв разницу между последовательными смещениями. Вес ребер также может храниться либо в отдельном массиве, либо чередоваться с ребрами для улучшения локальности кэша. Раздел заканчивается кратким введением в логическую оптимизацию, в частности, в свертывание и распространение констант, которые оценивают константные выражения во время компиляции для сокращения времени выполнения.
  
  
• 00:40:00 В этом разделе видео спикер обсуждает различные методы оптимизации кода, в том числе свертывание и распространение констант, удаление общих подвыражений и использование алгебраических тождеств. Определяя константы во время компиляции, компилятор может оценивать их и экономить время во время выполнения. Устранение общего подвыражения позволяет избежать многократного вычисления одного и того же выражения, сохраняя результат для использования в будущем. Использование алгебраических тождеств предполагает замену более дорогих выражений более дешевыми альтернативами. Спикер подчеркивает, что, хотя компилятор обычно хорошо реализует эти оптимизации, все же важно знать их для ситуаций, когда компилятор не делает этого автоматически.
  
  
• 00:45:00 В этом разделе видео спикер обсуждает две методики оптимизации. Во-первых, сокращение использования оператора квадратного корня, который требует больших вычислительных ресурсов, за счет использования алгебраических тождеств, чтобы избежать квадратных корней. Второй метод оптимизации — это короткое замыкание, которое включает в себя остановку серии тестов, как только результат станет известен, в случае, когда массив содержит неотрицательные целые числа, а сумму значений в массиве необходимо сверить с предел. Оптимизация может устранить необходимость просмотра всех элементов в массиве и может ускорить выполнение программы, но ее следует использовать разумно, основываясь на частоте, когда тест может быть закорочен.
  
  
• 00:50:00 В этом разделе видео обсуждается концепция сокращения логических операторов и их полезность для оптимизации кода. Двойной амперсанд и двойная вертикальная черта — это короткие логические операторы, которые могут сэкономить время и ресурсы, оценивая только одну сторону аргумента. Кроме того, в видео предлагается упорядочивать тесты в зависимости от их частоты успеха и стоимости выполнения. Этот подход может использовать преимущества короткого замыкания, чтобы пропустить дорогие тесты, если менее дорогие уже не работают. Наконец, видео знакомит с идеей создания быстрого пути с использованием проверок для раннего выхода из программы, если результат уже известен. Примером этого является проверка того, пересекаются ли ограничивающие рамки двух мячей перед проверкой других условий столкновения.
  
  
• 00:55:00 В этом разделе Бентли обсуждает способы оптимизации тестов для обнаружения столкновений в графических программах. Он предлагает быстрый тест пути, чтобы определить, пересекаются ли ограничивающие прямоугольники, прежде чем выполнять более дорогой тест на столкновение. Этот тест включает в себя проверку абсолютного значения разности по каждой координате и проверку того, больше ли оно суммы двух радиусов. Бентли также отмечает, что объединение тестов с помощью одного оператора switch или даже поиска в таблице может значительно повысить производительность. В целом, эти оптимизации могут быть полезны для многих приложений и графических программ.
• 01:00:00 В этом разделе видео охватывает третью категорию оптимизаций, связанную с циклами. Первая обсуждаемая оптимизация цикла — это подъем, который включает в себя избежание повторного вычисления инвариантного кода цикла каждый раз через тело цикла. Вычисляя выражение один раз и сохраняя его в переменной, а не пересчитывая его на каждой итерации, можно сэкономить время выполнения. Вторая оптимизация цикла — это использование часовых, специальных фиктивных значений, помещенных в структуры данных для упрощения обработки граничных условий и логики обработки выходных тестов цикла. Изменив программу так, чтобы она использовала две дополнительные записи в массиве, можно использовать часовой механизм, который будет выполнять только одну проверку на каждой итерации цикла.
  
  
• 01:05:00 В этом разделе спикер обсуждает два метода оптимизации кода: граничные условия и разворачивание цикла. Для граничных условий он показывает, как модифицировать цикл, чтобы эффективно обрабатывать особый случай, когда все элементы входного массива равны нулю. Добавляя фиктивный элемент в конец массива и проверяя переполнение, код может определить, когда он должен остановиться. Для развертывания цикла он объясняет два типа: полное и частичное. В то время как развертывание полного цикла происходит редко из-за больших размеров цикла, развертывание частичного цикла уменьшает количество итераций цикла за счет объединения нескольких в один, что может повысить производительность за счет уменьшения количества выполняемых инструкций потока управления.
  
  
• 01:10:00 В этом разделе инструктор обсуждает оптимизацию развертывания и слияния циклов. Развертывание цикла включает в себя объединение нескольких итераций цикла в одну итерацию, тем самым уменьшая накладные расходы на управление циклом и обеспечивая дополнительную оптимизацию компилятора. Однако слишком большое развертывание может отрицательно сказаться на производительности, загрязняя кэш инструкций. Слияние циклов, с другой стороны, объединяет несколько циклов в одном и том же диапазоне индексов в один цикл, уменьшая накладные расходы на управление циклом и улучшая локальность кэша. Преподаватель также обсуждает устранение ненужных итераций путем изменения границ цикла, чтобы избежать выполнения итераций цикла по пустым телам цикла.
  
  
• 01:15:00 В этом разделе Бентли обсуждает оптимизацию функций, в частности концепцию встраивания, чтобы избежать накладных расходов на вызов функции. Объявив функцию статической встроенной, компилятор попытается заменить вызов функции телом самой функции, что устраняет необходимость в отдельном вызове функции. Хотя макросы также могут это делать, встроенные функции более структурированы и оценивают все свои аргументы, что позволяет избежать риска многократной вставки макросом дорогостоящего выражения в код. Bentley не рекомендует преждевременную оптимизацию и рекомендует разработчикам сначала убедиться в правильности своей программы и использовать регрессионное тестирование для поддержания правильности. Наконец, он указывает, что многие уровни оптимизации могут быть автоматизированы компилятором, и проверка ассемблерного кода может выявить любую такую оптимизацию.
  
  
• 01:20:00 В этом разделе правила Bentley по оптимизации работы изложены в виде серии из шести шагов. Эти правила состоят из постановки четких целей, разбиения задач на более мелкие части, выделения времени на планирование и организацию, определения приоритетов задач, сведения к минимуму отвлекающих факторов и регулярного пересмотра и корректировки вашего подхода. Следуя этим рекомендациям, вы сможете повысить свою продуктивность и более эффективно достигать поставленных целей. Кроме того, включение этих стратегий в вашу повседневную жизнь может помочь вам сохранить сильную рабочую этику и сосредоточиться на своих целях.

[MetaQuotes]

Лекция 3. Битовые хаки

3. Бит-хаки

В этом видео на YouTube рассматриваются различные темы, связанные с манипулированием битами, включая двоичное представление, дополнение до двух, побитовые операторы, замену переменных без временной переменной и оптимизацию кода. Видео демонстрирует различные трюки с битами, такие как нахождение минимума двух целых чисел без использования операторов if-else и как поменять местами два целых числа без использования временной переменной. Докладчик обсуждает непредсказуемые ветвления и представляет минимальную битовую хитрость без ветвлений, когда предсказуемые ветвления недоступны, и показывает, как битовые хаки могут оптимизировать код, заменяя дорогостоящие операции, такие как деление, простыми побитовыми операциями. В видео также обсуждается последовательность де Брейна и ее применение для решения таких задач, как задача N ферзей.

Во второй части обсуждается решение проблемы N ферзей с использованием битовых векторов и эффективного подсчета количества единичных битов в двоичном слове. Возврат используется для решения проблемы N ферзей, а битовые векторы используются для эффективного представления доски. Описаны три проверки для безопасного размещения ферзя в задаче о N ферзях, а также представлен метод подсчета количества единичных битов в слове путем рекурсивного исключения младшего значащего 1 бита. Кроме того, обсуждается использование поиска в таблице и манипуляции с регистрами для подсчета количества битов 1. Видео заканчивается демонстрацией метода «разделяй и властвуй» для подсчета 1 бит, который имеет производительность, пропорциональную логарифмическому основанию два длины слова. Также предоставляются ресурсы для дальнейшего обучения.

• 00:00:00 В этом разделе мы узнаем о двоичном представлении слов и о том, как из них вычислять целочисленные значения. Мы также узнаем о представлении дополнения до двух для целых чисел со знаком и особых случаях слова «все нули и все единицы». Кроме того, мы видим важное тождество для единицы, дополняющей X, и его отношение к отрицанию X в представлении с дополнением до двух.
  
  
• 00:05:00 В этом разделе ведущий объясняет Дополнение до единиц и как получить отрицательное число путем добавления 1 к Дополнению до единиц. Он также рассматривает использование шестнадцатеричных чисел для представления больших двоичных констант и дает таблицу для преобразования между шестнадцатеричными и двоичными числами. Затем в видео рассматриваются побитовые операторы в C++ и демонстрируются примеры их использования для логических и, логических или, исключающих или, а также операций сдвига влево и вправо.
  
  
• 00:10:00 В этом разделе видео обсуждаются различные распространенные идиомы, которые могут быть реализованы с помощью побитовых операторов в C. Одним из примеров является установка или очистка бита регистра в слове X с помощью сдвига, за которым следует ИЛИ или НЕ и И, соответственно. Другим примером является извлечение битового поля из слова X путем создания маски с единицами в позициях желаемых битов и нулями в других местах, затем с помощью операции AND маски с X и сдвигом извлеченных битов вправо. В видео также упоминается, что использование этих трюков может быть особенно полезным при работе со сжатыми или закодированными данными.
  
  
• 00:15:00 В этом разделе видео обсуждается, как поменять местами два целых числа без использования временной переменной с помощью некоторых битовых трюков. Код включает в себя установку X равным X XOR Y, затем Y равным X X XOR Y и, наконец, X равным X X XOR Y. Это работает, потому что XOR является обратным для самого себя, а первая строка генерирует маску с единицами, где биты в X и Y отличаются, что затем используется для перестановки битов в Y, которые отличаются от X. Это позволяет выполнять обмен без использования временной переменной. В ролике также подчеркивается важность маскировки для обеспечения безопасности при работе с этими трюками.
  
  
• 00:20:00 В этом разделе спикер обсуждает два битовых хака. Первый хак — это способ поменять местами две переменные без использования временной переменной. Хак включает в себя использование XOR и маски для перестановки битов, которые различаются между двумя переменными. Хотя этот хак классный, это не самый эффективный способ замены переменных из-за плохого параллелизма на уровне инструкций. Второй прием — это способ найти минимальное из двух целых чисел без использования операторов if-else, которые могут вызвать проблемы с производительностью из-за неправильного предсказания перехода. Вместо этого спикер показывает, как использовать побитовые операции для сравнения целых чисел и вычисления минимума без ветвления.
  
  
• 00:25:00 В этом разделе спикер обсуждает оптимизацию кода и использование ключевого слова «restrict» в подпрограмме, объединяющей два отсортированных массива. Процесс объясняется на примере, где два зеленых массива объединены в синий массив. Также обсуждается предсказуемость каждой ветви в коде, причем первая ветвь предсказуема, а вторая непредсказуема.
  
  
• 00:30:00 В этом разделе видео обсуждает предсказуемые и непредсказуемые переходы в программировании и представляет трюк с минимальными битами без переходов как решение проблемы непредсказуемых переходов. Хитрость заключается в использовании переменной с именем «comp» для хранения результата сравнения между первым элементом a и b и получении минимума a и b с помощью битового трюка. Затем минимальное значение помещается в C, а значение A или B увеличивается или уменьшается на основе значения «comp». В видео отмечается, что, хотя в некоторых случаях этот трюк может не сработать, полезно понять, что делает компилятор, и что многие взломы битов для слов могут распространяться на взломы битов и слов для векторов, поэтому полезно знать об этих трюках.
  
  
• 00:35:00 В этом разделе видео обсуждаются битовые хаки и их полезность в программировании. Приведенный пример представляет собой небольшой трюк для модульного сложения, который позволяет выполнять более быстрые операции без использования деления. Установив Z в сумму X и Y, а затем проверив, меньше или больше N, программа может вернуть Z, если оно находится в пределах диапазона, или результат Z минус N, чтобы вернуть его в диапазон. Программа использует логику, аналогичную минимальной, и имеет непредсказуемый переход, который может привести к неправильному предсказанию перехода. Другой приведенный пример - это способ округления значения до ближайшей степени двойки с использованием битовых манипуляций путем уменьшения N, выполнения побитовых или операций с N, сдвинутым вправо на разные значения, а затем увеличивая в конце.
  
  
• 00:40:00 В этом разделе видео спикер обсуждает проблемы с двумя битовыми манипуляциями. Первая задача заключается в нахождении наименьшей степени двойки, которая больше заданного значения n. Докладчик объясняет, как добиться этого, используя манипуляции с битами и уменьшая n, если оно уже является степенью двойки, чтобы гарантировать, что логарифм n минус один бит установлен. Вторая задача заключается в вычислении маски наименее значащей единицы в слове X, и выступающий объясняет, как этого добиться, присваивая результату значение X и используя побитовую операцию и с отрицательным значением X. Выступающий также представляет код для нахождения индекса бита путем умножения X на константу и поиска результата в таблице. Раздел заканчивается тем, что спикер выполняет математический фокус, включающий манипуляции с битами.
  
  
• 00:45:00 В этом разделе видео на YouTube показывает группу, выполняющую фокус с картами и колокольчиком. Исполнитель утверждает, что читает мысли зрителей и просит их разрезать колоду карт перед их раздачей. Исполнитель предсказывает масть и номер карты каждого человека и, похоже, добивается успеха. Они приписывают свои способности ношению «потрясающего комбинезона» и волшебной шляпы, а также очистке воздуха с помощью колокольчика.
  
  
• 00:50:00 В этом разделе мы узнаем о последовательности де Брюйна и ее корреляции с вычислением логарифмической базы 2 степени 2. Последовательность де Брюйна представляет собой циклическую битовую последовательность, в которой каждая возможная битовая строка длины K встречается точно один раз как подстроку в последовательности. Используя таблицу преобразования, мы можем умножить константу последовательности де Брюйне на степень 2 и извлечь подстроку, которая появляется в начале последовательности, чтобы вычислить логарифмическое основание 2 степени 2. Сдвинув последовательность влево, а затем просмотрев вверх по начальной позиции подстроки в таблице преобразования, мы можем определить логарифмическое основание 2 целого числа, с которого мы начали, что решает ранее продемонстрированный карточный фокус.
  
  
• 00:55:00 В этом разделе спикер обсуждает последовательность де Брейна, которая представляет собой циклическую последовательность двоичного алфавита, содержащую каждую возможную n-битную строку ровно один раз. Последовательность может быть использована для решения таких задач, как проблема N ферзей, и может быть сгенерирована с помощью фокуса. Докладчик также объясняет, как работает битовый трюк для определения положения подстроки последовательности де Брейна после сдвига влево. Производительность этого битового трюка ограничена производительностью умножения и поиска в таблице, но теперь есть аппаратная инструкция для его вычисления.
  
  
• 01:00:00 В этом разделе спикер обсуждает проблему N ферзей, которая включает в себя размещение N шахматных ферзей на шахматной доске NxN таким образом, чтобы никакие два ферзя не угрожали друг другу. Проблема часто решается с помощью поиска с возвратом, когда ферзи располагаются ряд за рядом, и программа выполняет возврат, когда не может быть найдена допустимая позиция. Также обсуждаются различные представления платы, наиболее компактным из которых является набор из трех битовых векторов. Нижний вектор хранит наличие ферзей в каждом столбце, левый диагональный вектор хранит присутствие ферзей на каждой левой диагонали, а правый диагональный вектор хранит присутствие ферзей на каждой правой диагонали. Использование битовых векторов позволяет более эффективно реализовать алгоритм.
  
  
• 01:05:00 В этом разделе описан процесс проверки того, является ли позиция безопасной для размещения ферзя в задаче с n ферзями с использованием битовых векторов. Три проверки включают в себя проверку того, есть ли уже ферзь в том же ряду, в том же столбце и на той же диагонали, что и позиция. Этот метод эффективен и гарантирует безопасное размещение ферзя, если он пройдет все три проверки. Другой обсуждаемой проблемой является подсчет популяции, который включает в себя подсчет количества битов 1 в слове X. Представленный метод многократно удаляет младший значащий бит 1 в слове X, пока он не станет равным нулю, а количество требуемых итераций пропорционально количеству битов. 1 бит в X.
  
  
• 01:10:00 В этом разделе спикер обсуждает использование поиска по таблице для эффективного подсчета количества битов 1 в двоичном слове. Метод поиска по таблице включает создание таблицы размером 256, в которой хранится количество единиц в каждом 8-битном слове, а затем поиск числа для каждой 8-битной подстроки в двоичном слове. Докладчик отмечает, что производительность этого метода ограничена операциями с памятью, необходимыми для доступа к таблице. Далее спикер представляет третий способ подсчета количества битов 1 с помощью регистров, где они создают маски и выполняют определенные инструкции, которые позволяют им подсчитывать количество единиц в двоичном слове без доступа к памяти. Ведущий приводит пример, чтобы объяснить, как работает этот метод.
  
  
• 01:15:00 В этом разделе спикер демонстрирует, как подсчитать количество единиц во входном слове, используя параллельный метод «разделяй и властвуй», где производительность пропорциональна логарифмическому основанию два длины слова, W. Это указал, что большинство современных машин имеют встроенную инструкцию счетчика всплывающих окон, которая быстрее, чем что-либо, что можно закодировать, и доступна через встроенные функции компилятора. Однако это может сделать код менее переносимым между разными машинами. Спикер предоставляет некоторые ресурсы для получения дополнительной информации о трюках с битами, включая веб-сайт, учебник, веб-сайт по шахматному программированию и книгу под названием Hacker's Delight.

[MetaQuotes]

Лекция 4. Язык ассемблера и архитектура компьютера

Лекция 4. Язык ассемблера и архитектура компьютера

В этом видео представлен всесторонний обзор языка ассемблера и компьютерной архитектуры. Язык ассемблера является важным интерфейсом для оптимизации производительности кода, а понимание архитектуры компьютера необходимо для освоения языка ассемблера. Докладчик рассказывает об истории архитектуры x86 64 и ее развитии, ее ключевых регистрах, типах данных, режимах адресации памяти и архитектуре набора инструкций, включая стеки, целочисленную и двоичную логику, логическую логику и подпрограммы. Они также обсуждают такие расширения, как расширение нуля и знака, а также различные режимы адресации на языке ассемблера. Кроме того, в видео обсуждаются типы с плавающей запятой, векторы и векторные единицы, традиционные инструкции и инструкции SSE, а также особенности архитектуры компьютерной архитектуры, такие как суперскалярная обработка, выполнение не по порядку и прогнозирование ветвлений.

Видео также охватывает несколько тем, связанных с языком ассемблера и компьютерной архитектурой. Одной из центральных тем является параллелизм на уровне инструкций (ILP) и остановки конвейера, вызванные такими опасностями, как зависимость данных. Докладчик обсуждает зависимости истинных, анти- и выходных данных, а также то, как суперскалярные процессоры могут использовать больший параллелизм в аппаратном обеспечении для одновременного выполнения нескольких инструкций. Однако, чтобы избежать опасностей, архитекторы реализовали такие стратегии, как переименование и изменение порядка, а также спекулятивное выполнение, чтобы угадать результат ветки и выполнить его заранее. Докладчик призывает аудиторию понять эти методы, чтобы лучше понять оптимизацию программного обеспечения.

• 00:00:00 В этом разделе инструктор рассказывает о языке ассемблера и архитектуре компьютера, которые часто не рассматриваются в современных курсах по программному обеспечению. Понимание этих концепций необходимо для оптимизации производительности кода, и язык ассемблера является лучшим интерфейсом для этого. Процесс компиляции кода включает несколько этапов, включая предварительную обработку, компиляцию, сборку и компоновку. Язык ассемблера — это мнемоническая структура машинного кода, которая делает его более удобочитаемым, а окончательный исполняемый файл создается на этапе компоновки с использованием команды LD.
  
  
• 00:05:00 В этом разделе спикер объясняет, что ассемблерный и машинный код очень похожи по структуре, а OP-коды в ассемблере соответствуют определенным битовым комбинациям в машинном коде. Докладчик знакомит с программой ABS, которая может производить дизассемблирование машинного кода, выявляя мнемонический, человекочитаемый ассемблерный код. Затем выступающий обсуждает несколько причин, по которым кто-то может захотеть взглянуть на ассемблерный код, включая выявление того, что сделал и чего не сделал компилятор, отладку ошибок компилятора и обратное проектирование программы без доступа к ее исходному коду.
  
  
• 00:10:00 В этом разделе спикер объясняет ожидания от класса, в том числе понимание того, как компилятор реализует лингвистические конструкции с инструкциями x86, способность читать язык ассемблера x86 и понимание влияния общих шаблонов сборки на производительность. Учащиеся также должны уметь писать код с нуля, если это необходимо, и достигать уровня мастерства, на котором это возможно. Затем докладчик углубляется в архитектуру набора команд x86 64, включая регистры, инструкции, типы данных и режимы адресации памяти. Ключевые регистры включают в себя регистры общего назначения и регистр флагов, который отслеживает арифметические операции и переносы. Указатель инструкций направляет аппаратное обеспечение через последовательность инструкций в программе на языке ассемблера.
  
  
• 00:15:00 В этом разделе спикер обсуждает историю архитектуры x86 64 и ее развитие от 16-битных словесных машин с ограниченной памятью к более широким словам для индексации по мере того, как стало доступно больше памяти. Докладчик также объясняет добавление векторных регистров, таких как регистры xmm и AVX, для векторизации и то, как они используются. Они также касаются темы регистров общего назначения и того, как их функциональное назначение значительно изменилось с течением времени, но их названия закрепились в силу исторических причин. Кроме того, спикер объясняет, как определенные регистры имеют одинаковые псевдонимы для нижней и верхней половин короткого слова, 32-битных или 64-битных слов.
  
  
• 00:20:00 В этом разделе спикер объясняет основы языка ассемблера x86 64 и как он работает. Регистры имеют разные имена в зависимости от того, к какой части регистра осуществляется доступ, а некоторые из них имеют определенные цели, например, RSP используется в качестве указателя стека. Формат кода инструкции x86 64 должен иметь код операции и список операндов, обычно с 0-3 операндами, которые могут быть источниками или получателями. Докладчик объясняет разницу между синтаксисом AT&T и синтаксисом Intel для обозначения операций и предоставляет список общих кодов операций, таких как «перемещение» и «условное перемещение». Кроме того, спикер объясняет важность расширения знака при переходе от 32-битного регистра значений к 64-битному регистру.
  
  
• 00:25:00 В этом разделе спикер обсуждает различные типы инструкций на языке ассемблера, включая инструкции для стеков, целочисленную арифметику, бинарную логику, логическую логику, переходы и подпрограммы. Коды операций могут быть дополнены суффиксом, который описывает тип данных операции или код состояния. Например, перемещение с «подсказкой» указывает на то, что перемещаемые данные представляют собой четверное слово, состоящее из 8 байтов или 64 битов. Также обсуждаются типы данных x86 64 и их ассемблерные суффиксы, и приводятся примеры, иллюстрирующие, как работает расширение знака. Наличие или отсутствие определенных кодов операций и мнемоники на ассемблере может сбивать с толку, но компилятор должен понимать эти инструкции для правильного выполнения программы.
  
  
• 00:30:00 В этом разделе докладчик обсуждает такие расширения, как нулевое расширение и знаковое расширение, возникающие при переносе 32-битных операций на 64-битные. Они также упоминают, как набор инструкций Intel может усложниться при добавлении новых инструкций. Выступающий продолжает объяснять различные коды условий, используемые в условных переходах и условных перемещениях, а также флаги, которые используются с ними, такие как нулевой флаг и флаг переполнения. Также обсуждается причина, по которой определенные коды условий проверяют нулевой флаг.
  
  
• 00:35:00 В этом разделе спикер обсуждает различные режимы прямой и косвенной адресации на ассемблере. Режимы прямой адресации включают немедленную адресацию, прямую память и использование регистра. Режимы косвенной адресации регистра и адресации с индексом регистра позволяют обращаться к памяти, предоставляя адрес в регистре или смещая адрес. Спикер отмечает, что доступ к памяти может быть медленным и дорогим, поэтому важно по возможности хранить значения в регистрах, чтобы ускорить процесс. Они также упоминают о важности кэширования для оптимизации доступа к памяти.
  
  
• 00:40:00 В этом разделе видео обсуждается использование относительной индексации указателя, когда указатель инструкции используется для индексации данных, а не регистра общего назначения. Также вводится метод адресации смещения масштаба базового индекса, который представляет собой сложную инструкцию, поддерживающую мягкое индексирование базового указателя. Видео содержит обзор некоторых идиом языка ассемблера, включая код операции XOR, который используется для обнуления регистров, и код операции test, который вычисляет побитовое и двух значений и сохраняет флаги регистра. Наконец, видео касается инструкций перехода и меток, которые позволяют управлять потоком в коде.
  
  
• 00:45:00 В этом разделе видео обсуждается язык ассемблера и архитектура компьютера, в том числе различные наборы инструкций и история с плавающей запятой. Наборы инструкций x86, включая x87 и SSE, поддерживают скалярные арифметические операции с плавающей запятой одинарной и двойной точности, а также векторные инструкции. Компиляторы обычно предпочитают инструкции SSE, а не x87, из-за их простоты в компиляции и оптимизации. Также объясняется цель использования инструкций без операций (nop) в ассемблере, таких как оптимизация выравнивания.
  
  
• 00:50:00 В этом разделе докладчик обсуждает типы с плавающей запятой, векторы и векторные единицы, которые используются в компьютерной архитектуре. Докладчик объясняет, что способ работы векторных блоков заключается в том, что процессор выдает инструкции всем векторным блокам, каждый из которых называется дорожкой. Дорожки содержат целочисленную арифметику или арифметику с плавающей запятой, и все они работают синхронно, то есть все они делают одно и то же. Они могут выполнять сразу несколько операций, и все это можно сделать одной инструкцией. Докладчик объясняет, что некоторые архитектуры требуют выравнивания векторных операндов, в то время как другие могут сдвигать векторы в памяти, что приводит к разнице в производительности между ними. Кроме того, существуют архитектуры, поддерживающие операции с несколькими полосами, такие как перестановка, перетасовка и разброс-сборка.
  
  
• 00:55:00 В этом разделе спикер обсуждает различия между традиционными инструкциями и инструкциями SSE и то, как их можно использовать. Они также упоминают трюк с псевдонимами, когда регистры ymm используют псевдонимы регистров xmm и расширяют их до 512 бит с помощью avx-512. Затем они переходят к обсуждению компьютерной архитектуры, в частности, к разнице между пятиэтапным конвейером и современным процессором с 14-19 этапами конвейера. Обсуждаемые ими конструктивные особенности включают векторную обработку или аппаратное обеспечение I, суперскалярную обработку, неупорядоченное выполнение и прогнозирование ветвлений, но они упоминают, что не будут углубляться в неупорядоченное выполнение из-за нехватки времени.
  
  
• 01:00:00 В этом разделе видео инструктор обсуждает параллелизм на уровне инструкций (ILP) и задержки конвейера. ILP включает в себя поиск возможностей одновременного выполнения нескольких инструкций для повышения пропускной способности. Однако останов конвейера может произойти, когда инструкция не может быть выполнена из-за опасности, такой как структурная опасность, опасность данных или опасность управления, причем опасности данных являются наиболее распространенными. Истинная зависимость возникает, когда инструкция читает после зависимости от записи, а антизависимость возникает, когда инструкция хочет записать в ячейку, но должна ждать, пока предыдущая инструкция не прочитает значение. Компилятор пытается уменьшить простои конвейера, оптимизируя код, чтобы избежать опасностей.
  
  
• 01:05:00 В этом разделе обсуждается концепция зависимостей данных в языке ассемблера. Существует три типа зависимостей данных: истинная, анти- и выходная. Арифметические операции, особенно сложные, такие как арифметика с плавающей запятой, имеют большую задержку и требуют отдельных функциональных блоков в процессоре, иногда с отдельными регистрами. Чтобы увеличить параллелизм на уровне инструкций, архитекторы внедрили такие методы, как выполнение нескольких инструкций за цикл, чтобы использовать больше параллелизма в оборудовании.
  
  
• 01:10:00 В этом разделе видео объясняется, как суперскалярные процессоры могут выполнять несколько инструкций одновременно, на примере Haswell, разбивающего инструкции на более простые операции, называемые микрооперациями, и выполняя до четырех микроопераций за цикл. Затем в видео подробно описываются стратегии освобождения процессоров от выполнения инструкций по порядку, включая обход и переименование регистров, которые позволяют выполнять независимые инструкции не по порядку, что приводит к ускорению времени обработки. Эти стратегии требуют отслеживания зависимостей и выполнения кода таким образом, чтобы избежать опасностей, таких как зависимости данных.
  
  
• 01:15:00 В этом разделе докладчик обсуждает переименование и изменение порядка — два важных метода, используемых в современных процессорах для предотвращения опасности данных. Спикер также говорит о спекулятивном выполнении, которое используется в прогнозировании ветвлений, чтобы угадать результат ветвления и выполнить его заранее, чтобы избежать зависаний. Однако, если догадка неверна, отмена вычислений будет стоить от 15 до 20 циклов. Докладчик кратко упоминает, как работают предсказатели ветвлений, но указывает, что это сложно и требует дальнейшего изучения. Несмотря на поспешное окончание, спикер призывает аудиторию разобраться в различных методах, которые помогут понять, почему те или иные оптимизации программного обеспечения работают и не работают.

[MetaQuotes]

Лекция 5. От C к ассемблеру

Лекция 5. От C к ассемблеру

В этой части видео обсуждается важность понимания языка C для языка ассемблера, а также то, как код C реализуется на языке ассемблера с помощью компилятора. Особое внимание уделяется тому, как LLVM IR транслируется в сборку в соглашении о вызовах Linux x86 64. Докладчик объясняет основные компоненты LLVM IR и то, как конструкции языка программирования C транслируются в LLVM IR. В видео также рассматривается структура виртуальной памяти, проблема координации вызовов функций между несколькими функциями и использование соглашения о вызовах Linux x86 64 двух указателей — BP и SP — для управления всеми кадрами стека.

В видео также объясняются стратегии сохранения состояний регистров в программировании C to Assembly, такие как сохранение регистров как вызывающего или вызываемого абонента, а также то, как соглашение о вызовах x86 позволяет избежать напрасной работы. В нем рассказывается, как вызовы функций работают в C и ассемблере, обсуждается процесс сохранения аргументов и локальных переменных в стеке, а также общая оптимизация использования указателя стека вместо базового указателя. В видео также показан процесс компиляции LV miR в ассемблерный код, обсуждение пролога функции, сохранение регистров, обработка условий и преобразование кода C в ассемблерный код с использованием графа потока управления. Наконец, в нем говорится об эпилоге функции, используемой для восстановления регистров перед возвратом результатов.

• 00:00:00 В этом разделе видео TB Shuttle обсуждает важность понимания C для языка ассемблера. Он отмечает, что язык ассемблера обеспечивает большую точность, чем код C, и может раскрыть детали программы, которые не очевидны из кода C. Просмотр сборки также может позволить разработчикам определить, что сделал или не сделал компилятор при оптимизации программы. Кроме того, могут возникать ошибки, которые создают неожиданное поведение только при оптимизации кода на определенных уровнях, что затрудняет обнаружение этих ошибок. Наконец, понимание ассемблера может позволить разработчикам изменять ассемблерный код вручную или реконструировать код.
  
  
• 00:05:00 В этом разделе видео обсуждается, как код C реализуется на языке ассемблера с помощью компилятора, который должен принимать сложные решения относительно того, какие инструкции ассемблера использовать, как реализовать условные выражения и циклы C и как координировать вызовы функций. Чтобы понять процесс перевода, видео представляет LVM IR, который представляет собой упрощенную сборку, которую компилятор использует для анализа программы. Затем в видео объясняется, как конструкции языка программирования C, такие как функции, условные операторы и циклы, переводятся в LVM IR. Раздел заканчивается кратким упоминанием атрибутов LVM IR.
  
  
• 00:10:00 В этом разделе основное внимание уделяется процессу преобразования LLVM ir в сборку, в частности, в соглашении о вызовах Linux x86 64. Докладчик дает краткое введение в LLVM ir, объясняя его основные компоненты функций, инструкций и регистров, которые напоминают более простую версию ассемблера. Регистры LLVM ir похожи на переменные c и различаются своими именами, а каждая функция имеет собственные имена локальных регистров. Докладчик выделяет регистры в примере фрагмента кода и отмечает, что синтаксис для регистров украден при обращении к различным базовым блокам в LLVM. Доклад завершается анализом того, как этот процесс работает для простого кода для вычисления чисел Фибоначчи.
  
  
• 00:15:00 В этом разделе спикер объясняет синтаксис инструкций LV Mir, который включает в себя имя регистра, символ равенства, код операции и список операндов. В то время как некоторые инструкции возвращают значение, которое сохраняется в локальном регистре, другие этого не делают. Набор инструкций LV Mir меньше, чем у x86, поскольку он содержит всего несколько инструкций для перемещения данных, арифметических и логических операций и потока управления. В LV Mir все представлено в виде типов, включая целые числа (с определенным количеством битов), типы с плавающей запятой, типы указателей, типы векторов и типы меток для базовых блоков. Спикер также отмечает, что векторные операции LV Mir выглядят не как SSE или AVX, а как обычные операции, которые работают с векторным типом.
  
  
• 00:20:00 В этом разделе видео обсуждается, как последовательности операций в коде C транслируются в LLVM IR, и эмпирические правила интерпретации кода в IR. Выдержка также объясняет, как LLVM IR обрабатывает примитивные и агрегатные типы, такие как массивы и структуры, и показывает примеры того, как доступ к элементам в массиве включает вычисление адресов в памяти. Кроме того, в видео объясняется, как функции C переводятся в LLVM IR, с соответствующими операторами возврата на обоих языках.
  
  
• 00:25:00 В этом разделе видео объясняет, как функции и параметры в C переводятся в LV Mir. Функции в LV Mir аналогичны функциям в C, но параметры C становятся списками параметров в LV Mir. Однако чтение LV Mir может быть затруднено, поскольку регистры не имеют правильных названий, что затрудняет их расшифровку. В видео также обсуждаются базовые блоки в LV Mir, которые представляют собой фрагменты кода, разделенные на основе инструкций потока управления. Соединения между базовыми блоками основаны на ребрах, индуцированных инструкциями ветвления. Наконец, видео затрагивает условные операторы в LV Mir, где операторы if-then-else становятся инструкциями условного перехода, которые вызывают базовые блоки и управляют границами потока.
  
  
• 00:30:00 В этом разделе видео объясняет, как работают условные операции и переходы в LLVM IR. Процесс начинается со сравнения буквального значения и значения, хранящегося в регистре, в результате чего создается однобитовое целое или логическое значение. Затем этот результат передается в действие условного перехода вместе с двумя метками базовых блоков, указывающими, куда идти, если предикат истинен или ложен. Если имеется безусловная ветвь с одним операндом, результатом является прямой переход к определенному базовому блоку. В видео также показано, как создать ромбовидную форму на графе потока управления всякий раз, когда есть условный оператор, и приведен пример цикла, написанного на языке C.
  
  
• 00:35:00 В этом разделе видео обсуждаются компоненты цикла C, включая тело цикла и управление циклом. Тело цикла выполняется на каждой итерации, а элемент управления циклом управляет всеми итерациями цикла. Цикл AC создает шаблон цикла в графе потока управления, который, в свою очередь, создает структуру цикла в LLVM ir. Затем видео анализирует код LLVM ir для управления циклом, где есть странная инструкция fie, которая обычно возникает при работе с циклами. Инструкция fie пытается решить проблему с LLVM-представлением кода, где I представлен целой кучей разных регистров, что делает неясным, куда я на самом деле попал.
  
  
• 00:40:00 В этом разделе видео обсуждается сопоставление переменной индукции в цикле с различными местоположениями в LLVM, что происходит из-за изменения значений переменной на разных итерациях цикла. Это приводит к инварианту «статического одиночного присваивания» в LLVM, согласно которому каждая инструкция определяет значение регистра только один раз, что создает проблему для переменных индукции. Инструкция "phi" решает эту проблему, определяя значение регистра, которое зависит от того, как поток управления объединяется в точке входа в цикл. В видео также обсуждаются атрибуты в LLVM и то, как они могут предоставлять дополнительную информацию для конструкций LLVM, например атрибут NSW, прикрепленный к инструкции «добавить».
  
  
• 00:45:00 В этом разделе видео основное внимание уделяется LLVM IR, который похож на ассемблер, но во многих отношениях проще, так как все вычисляемые значения хранятся в регистрах, которые похожи на обычные переменные C. LLVM IR использует парадигму статического одиночного присваивания, в которой каждая переменная записывается не более чем одной инструкцией. В видео показано, как перевести код C в LLVM IR, а затем в сборку, с некоторыми дополнительными сложностями в процессе. Компилятор выбирает фактические инструкции сборки, необходимые для операций LLVM IR, решает, какие регистры общего назначения использовать, и координирует вызовы функций между различными исходными файлами и двоичными библиотеками. Затем обсуждение переходит к соглашению о вызовах Linux x86 64.
  
  
• 00:50:00 В этом разделе обсуждается расположение виртуальной памяти для программы. Виртуальная память разделена на сегменты, такие как сегменты стека и кучи, которые организованы с использованием директив ассемблера в ассемблерном коде. Кроме того, обсуждаются различные типы директив хранения, такие как директива пробела и длинный сегмент, которые выделяют память и сохраняют значения. Затем внимание обращается на сегмент стека, где хранятся данные для управления вызовами и возвратами функций, включая хранение локальных переменных, аргументов функций, адреса возврата и, возможно, промежуточных результатов.
  
  
• 00:55:00 В этом разделе видео докладчик обсуждает проблему координации вызовов функций между несколькими функциями, некоторые из которых могут происходить из разных файлов или библиотек. Чтобы гарантировать, что все функции хорошо работают вместе, было установлено соглашение о вызовах, которому должны подчиняться все функции. Соглашение о вызовах Linux x86 64 использует два указателя — BP и SP — для управления всеми кадрами стека для каждого экземпляра функции. Когда выполняется инструкция вызова, текущее значение IP помещается в стек в качестве адреса возврата, а инструкция вызова переходит к адресу некоторой функции в памяти программы. Инструкция return отменяет операции инструкции call и выталкивает адрес возврата из стека, чтобы вернуться к выполнению вызывающей программы. Чтобы справиться с проблемой, когда несколько функций хотят использовать одни и те же регистры, в соглашении о вызовах подробно описываются правила, для которых регистры может использовать каждая функция, и то, как они должны сохранять эти регистры посредством вызовов функций.
• 01:00:00 В этом разделе видео обсуждаются стратегии сохранения состояний регистров при работе с различными функциями в программировании C to Assembly. В нем упоминаются два метода, которые можно использовать: в одном вызывающая сторона сохраняет состояние регистра перед вызовом, а в другом вызывающая сторона сохраняет все состояние регистра. Соглашение о вызовах x86 включает и то, и другое: некоторые регистры указываются как вызываемые, а другие — как вызывающие, чтобы избежать ненужной работы. В видео также показано, как организована память стека и как стек растет. Наконец, в нем обсуждается координация того, как функции будут использовать перекрывающиеся части стековой памяти.
  
  
• 01:05:00 В этом разделе видео обсуждается, как работает вызов функции в C и ассемблере. Перед вызовом функции C функция B помещает нерегистровые аргументы для функции C в зарезервированный блок компоновки в своей собственной памяти стека ниже своих локальных переменных. Он получит доступ к этим аргументам с отрицательным смещением. Когда функция C запускается, она выполняет пролог функции, который сохраняет базовый указатель для кадра стека B и устанавливает BP равным SP, поскольку он входит в новый кадр. Затем он выделяет место в стеке для своих собственных локальных переменных, а также пространство, которое B будет использовать для любых блоков связи, которые он создает для своих вызывающих объектов или для вещей, которые он вызывает. В видео также упоминается общая оптимизация, при которой компилятор может избавиться от BP и выполнить всю индексацию на основе RSP указателя стека, чтобы получить еще один регистр общего назначения.
  
  
• 01:10:00 В этом разделе инструктор знакомит аудиторию с процессом компиляции LV miR до ассемблерного кода. Первый шаг включает в себя определение функции 'fib' как глобально доступной функции с использованием некоторых директив ассемблера, таких как глобальная директива fib и выравнивание. Затем пролог функции сохраняется с очередью push var BP и очередью мобов RSP rbp. Ассемблерный код также помещает в стек пару регистров, сохраняющих Kali, перед перемещением аргумента в функцию, RTI, и помещает его в регистр RBX. Наконец, инструкция сравнения проверяет, меньше ли значение N двух, и если да, то возвращает входное значение. В противном случае он выполняет некоторый линейный код, чтобы вычислить fib of n минус один и fib of n минус два, сложить их вместе и вернуть этот результат.
  
  
• 01:15:00 В этом разделе видео обсуждаются условные переходы и различные варианты поведения, возникающие в коде в зависимости от результатов сравнения. Инструкция JGE переходит к метке ложной стороны операции ветвления LLVM, когда n больше или равно 2, а операции соответствуют истинной стороне операции, когда n меньше 2. Инструкция LEA используется для вычисление адреса, а операция перемещения сохраняет результат вызова функции в R14. Следующий набор инструкций вычисляет значение n-2, сохраняет его в RDI, а затем вызывает fib для n-2, возвращая результат в наш AX. Наконец, операция добавляет R14 к нашему AX.
  
  
• 01:20:00 В этом разделе видео обсуждается преобразование кода C в код сборки. Докладчик объясняет, что в процессе для представления кода используется граф потока управления, состоящий из базовых блоков, соединенных ребрами потока управления. Они также упоминают о сложности работы с соглашениями о вызовах в ассемблерном коде. Эпилог функции используется для восстановления регистров перед чем-либо в кадре стека перед возвратом результата. Видео завершается кратким изложением основных тем, затронутых в этом разделе.

[MetaQuotes]

Лекция 6. Многоядерное программирование

Лекция 6. Многоядерное программирование

В этой видеолекции обсуждается многоядерное программирование и появление многоядерных процессоров благодаря закону Мура и прекращению масштабирования тактовых частот. Докладчик объясняет проблему плотности мощности, с которой сталкиваются процессоры, и то, как это привело к добавлению нескольких ядер в чипы, чтобы соответствовать закону Мура. В лекции также рассматриваются основы протоколов когерентности кэша в оборудовании с общей памятью и параллельных платформах, таких как Pthreads, TBB, OpenMP и Silk, которые предоставляют абстракции для параллельного программирования. Обсуждаются плюсы и минусы каждой платформы и демонстрируются примеры реализации программ Фибоначчи. В видео представлен всесторонний обзор многоядерного программирования, а также проблем и решений, с которыми сталкиваются программисты.

Видео также охватывает различные аспекты Silk, инструмента абстракции для параллельной обработки. Спикер обсуждает такие темы, как вложенные циклы Silk for, генерация ассемблерного кода, редукция с помощью редюсеров, планировщик и оптимизация производительности. Они также предоставляют обзор экосистемы Silk и связанных инструментов, таких как Silk sanitizer и Silk Scale для отладки и анализа масштабируемости соответственно. Главный вывод заключается в том, что написание параллельных программ для многоядерных процессоров может быть сложной задачей, но Silk упрощает процесс, эффективно выполняя сложные задачи, предоставляя программистам больший контроль над выполнением своего кода.

• 00:00:00 В этом разделе инструктор обсуждает многоядерное программирование и причины появления многоядерных процессоров. С появлением закона Мура, который утверждает, что количество транзисторов, которые могут поместиться на чипе, удваивается каждые два года, и прекращения масштабирования тактовых частот примерно с 2004 по 2005 год, производители полупроводников начали производить чипы с несколькими процессорными ядрами. Это было связано с тем, что уже нельзя было увеличить частоту одиночных ядер на кристалле, что привело к необходимости перехода на модель проектирования, допускающую параллельную обработку. Инструктор также разъясняет взаимосвязь между количеством транзисторов на кристалле и максимальной частотой процессора.
  
  
• 00:05:00 В этом разделе спикер обсуждает проблему плотности мощности, с которой сталкиваются процессоры, где увеличение тактовой частоты приводит к экспоненциальному увеличению плотности мощности. Это привело к тому, что к чипам было добавлено несколько ядер, чтобы соответствовать закону Мура и не превышать пределы удельной мощности. Затем спикер представляет абстрактную многоядерную архитектуру, известную как многопроцессорный чип, и описывает лекции, посвященные аппаратным задачам и программным решениям для программирования параллельных программ на многоядерных машинах с использованием различных платформ параллелизма, таких как потоки P, потоки WinAPI, многопоточность Intel. строительные блоки, openmp и так далее.
  
  
• 00:10:00 В этом разделе спикер объясняет, как работают кэши в многоядерном программировании. Когда один процессор загружает значение в свой кеш из основной памяти, он сохраняет это значение в кеше на случай, если ему понадобится снова получить к нему доступ в будущем. Если другой процессор хочет загрузить то же значение, он также может получить его через кэш первого процессора, вместо того, чтобы проходить весь путь до основной памяти. Однако возникает проблема, когда один процессор обновляет значение в своем собственном кэше, делая значение в кэше другого процессора устаревшим. Протокол MSI является базовым решением этой проблемы, которое помечает строки кэша тремя возможными состояниями (M, S и I) для обеспечения согласованности между кэшами.
  
  
• 00:15:00 В этом разделе лекции обсуждаются основы протоколов когерентности кеша в оборудовании с общей памятью, в частности, как модификации строки кеша в кеше одного процессора могут сделать недействительными копии той же строки в других кешах. Лекция знакомит с простым протоколом и объясняет, как на практике существуют более сложные протоколы. Аппаратное обеспечение отвечает за управление конфликтами, когда несколько процессоров изменяют одну и ту же строку кэша, но это может привести к «шторму аннулирования» и снижению производительности. В лекции также отмечается, что платформы параллелизма могут абстрагироваться от этих сложностей и помочь с синхронизацией и обменом данными в параллельном программировании.
  
  
• 00:20:00 В этом разделе спикер обсуждает различные платформы параллелизма на примере чисел Фибоначчи. Программа Фибоначчи реализована с использованием рекурсивного алгоритма, который многократно вычисляет числа Фибоначчи, что делает его плохим алгоритмом. Два рекурсивных вызова можно распараллелить, поскольку они являются полностью независимыми вычислениями. Pthreads, стандартный API для многопоточности, можно использовать для реализации такого распараллеливания.
  
  
• 00:25:00 В этом разделе спикер обсуждает Pthreads, библиотеку функций, обеспечивающую параллелизм в программировании. Pthreads предоставляет самостоятельную платформу параллелизма, поскольку позволяет указать параллелизм в вашем коде, используя библиотеку функций со специальной семантикой. Каждый поток в Pthreads реализует абстракцию процессора и мультиплексируется с реальными машинными ресурсами. Pthreads также предоставляет маски, которые упрощают протоколы, участвующие в координации внутренних потоков. В библиотеке Pthreads есть ключевые функции, такие как pthread_create, которая сохраняет и идентифицирует новый поток, созданный pthread, и pthread_join, которая ожидает завершения потока, прежде чем продолжить выполнение кода. Докладчик демонстрирует, как реализовать ряд Фибоначчи с помощью Pthreads.
  
  
• 00:30:00 В этом разделе ведущий обсуждает реализацию кода Pthreads для параллельного выполнения последовательности Фибоначчи. Они объясняют, что если размер ввода достаточно мал, лучше выполнять программу последовательно из-за затрат на создание параллельных потоков. Код маршалирует входной аргумент в поток и сохраняет его в структуре arguments. Докладчик обсуждает Pthread create, Pthread join и некоторые из его недостатков, например, становится намного сложнее, если код должен рекурсивно создавать потоки. Они также упоминают, что этот код создает только один поток, поэтому максимально возможное ускорение составляет два, если он выполняется на четырех процессорах.
  
  
• 00:35:00 В этом разделе видео обсуждаются проблемы с Pthreads и кодом для последовательности Фибоначчи. Высокие накладные расходы на создание потока приводят к грубому параллелизму, а проблема масштабируемости заключается в том, что два ядра выполняют разный объем работы. Коду также не хватает модульности, так как логика Фибоначчи не инкапсулирована в одной функции, что затрудняет ее поддержку и изменение. Код также усложняется из-за сортировки аргументов, что аналогично написанию кода на ассемблере. Затем в видео рассказывается о Threading Building Blocks (TBB) — библиотеке, разработанной Intel для решения этих проблем.
  
  
• 00:40:00 В этом разделе видео обсуждается использование библиотеки Intel Thread Building Blocks (TBB) — библиотеки C++, позволяющей программистам использовать собственные потоки и алгоритм кражи работы без необходимости иметь дело с потоками напрямую. Указывая задачи, TBB распределяет нагрузку между потоками, упрощая написание кода и повышая его производительность по сравнению с потоками POSIX. В видео показан пример реализации программы Фибоначчи с использованием TBB, демонстрирующий, как она рекурсивно создает дочерние задачи, обеспечивая больший параллелизм и масштабируемость для нескольких процессоров. TBB также предоставляет шаблоны для параллелизма циклов, агрегации данных и программной конвейерной обработки, а также параллельные классы контейнеров для безопасного одновременного доступа к общим данным.
  
  
• 00:45:00 В этом разделе спикер представляет два лингвистических решения проблемы параллелизма: OpenMP и Silk. OpenMP — это спецификация, которая предоставляет лингвистические расширения для C и C++, а также Fortran, используя прагмы компилятора, чтобы указать, какие фрагменты кода должны выполняться параллельно. Он поддерживает циклический параллелизм, параллелизм задач и конвейерный параллелизм и имеет множество директив планирования и совместного использования данных, а также конструкций синхронизации. Докладчик приводит пример реализации Фибоначчи в OpenMP, который проще и работает лучше, чем использование Pthreads или TBB. OpenMP — популярное решение для написания параллельных программ, поскольку оно предоставляет множество функций и упрощает код.
  
  
• 00:50:00 В этом разделе спикер обсуждает платформу программирования шелка, которая поддерживает совместный и векторный параллелизм и включает в себя доказуемо эффективный планировщик перехвата работы. Программа также имеет библиотеку гиперобъектов для распараллеливания кода с глобальными переменными и поставляется с инструментами программирования, такими как детектор гонок на шелковом экране и анализатор масштабируемости, называемый шелковым представлением. Спикер также отмечает, что, хотя они не будут использовать шелк плюс в классе, они будут использовать лучший компилятор, известный как конусный LLVM, который производит лучший код по сравнению с его базовым компилятором, чем все другие реализации шелка.
  
  
• 00:55:00 В этом разделе на примерах обсуждается использование операторов Silk spawn и Silk Sync для включения параллельного выполнения. Первый пример — это соляная оболочка для Фибоначчи, которая включает в себя инструкции порождения шелка и синхронизации шелка, чтобы предположить, что выдумка n-1 может выполняться параллельно с функцией, вызывающей ее, пока выполняется выдумка n-2. Однако исполняющая система решает, следует ли выполнять эти задачи параллельно. Другим обсуждаемым примером является параллелизм циклов, когда оператор шелка for используется для параллельного выполнения цикла for, при этом компилятор рекурсивно делит пространство итераций пополам и использует операторы Silk spawn и Silk Sync до тех пор, пока диапазон не станет слишком мал для параллельного выполнения. Важно гарантировать, что итерации независимы для правильных результатов, а использование шелка добавляет некоторые дополнительные накладные расходы.
  
  
• 01:00:00 В этом разделе видео обсуждается использование вложенных циклов Silk for и подробности создания ассемблерного кода с использованием флага в компиляторе clang. Пример кода для суммирования значений с использованием цикла шелка for поднимает проблему гонки детерминированности, когда несколько процессоров записывают в одну и ту же ячейку памяти. Silk решает эту проблему за счет использования редукторов, которые представляют собой гиперобъекты, которые обрабатывают функцию сложения для данной переменной, регистрируя и отменяя регистрацию макросов редукторов. Это способ решения проблемы редукции, которая может возникнуть в многоядерном программировании, при этом для использования доступны многие другие операторы редукции.
  
  
• 01:05:00 В этом разделе спикер обсуждает редукторы в Silk — алгебраические структуры, которые имеют ассоциативную бинарную операцию и элемент тождества. В Silk есть несколько предопределенных редьюсеров, включая сложение, умножение, минимум, максимум и исключающее ИЛИ, и вы можете определить свой собственный редуктор. Одним из преимуществ Silk является то, что всегда существует действующая последовательная интерпретация программы, что упрощает отладку, а также имеется планировщик времени выполнения, который отслеживает и сопоставляет программу с доступными ядрами процессора, используя алгоритм планирования кражи работы для балансировки задач. равномерно. В отличие от других параллельных платформ планировщик Silk теоретически эффективен.
  
  
• 01:10:00 В этом разделе спикер представляет общий обзор экосистемы Silk для многоядерного программирования, в том числе, как компилировать исходный код Silk, тестировать параллельную и последовательную производительность, а также отлаживать проблемы с помощью таких инструментов, как silk sanitizer и silk шкала. Они также подчеркивают важность оптимизации последовательной программы для повышения производительности и того, как планировщик Silk может обрабатывать различные задачи во время выполнения программы. Кроме того, спикер объясняет, как шелковая шкала может определить максимальное количество процессоров, которые может использовать код, что делает ее полезным инструментом для анализа масштабируемости.
  
  
• 01:15:00 В этом разделе спикер резюмирует основные выводы лекции о многоядерном программировании. Они объясняют, что большинство современных процессоров имеют несколько ядер, что делает необходимым написание параллельных программ для обеспечения высокой производительности. Однако написание таких программ может быть затруднено, и здесь на помощь приходит Silk. Этот инструмент абстрагирует ядра процессора от программиста и выполняет синхронизацию, протоколы связи и балансировку нагрузки. Спикер также упоминает будущий проект, в рамках которого студенты будут реализовывать собственную параллельную заставку с помощью Silk.

[MetaQuotes]

Лекция 7. Гонки и параллелизм

Лекция 7. Гонки и параллелизм

Видео охватывает ряд тем, связанных с гонками, параллелизмом и вычислительными временами в программировании на Silk. Некоторые ключевые понятия включают операторы запуска и синхронизации для одновременного выполнения, важность предотвращения условий гонки и использование детектора гонки Silk для их идентификации. В видео также рассказывается о законе Амдала, законе работы и законе диапазона как о способах количественной оценки степени параллелизма в программе, а также о способах анализа работы и объема вычислений. Также обсуждаются потенциальное ускорение и параллелизм параллельных алгоритмов сортировки и концепция теории планирования с упором на теорему о жадном планировщике. В целом, видео дает ценную информацию для понимания и оптимизации производительности программ в программировании Silk.

Видео объясняет последствия ограничения жадного планировщика, которое, по сути, утверждает, что любой жадный планировщик достигает почти идеального линейного ускорения, пока T1/Tinfinity больше или равно P^2. Шелковый планировщик, который использует планировщик работы, может достичь почти идеального линейного ускорения, если количество процессоров намного меньше, чем у T1/Tinfinity. Система Silk Runtime работает, поддерживая рабочую колоду готовых нитей и манипулируя нижней частью колоды, как стопкой. В видео также обсуждается стек Cactus, который позволяет параллельно просматривать несколько стеков и делает возможным параллельный вызов функций. Верхняя граница пространства стека, необходимого для выполнения процессора P, часто намного слабее, чем фактически необходимый объем, поскольку каждому процессору может не потребоваться проходить весь путь вниз по графу вычислений каждый раз, когда он крадет работу.

• 00:00:00 В этом разделе инструктор знакомит с темой рас и параллелизма в Silk, которая будет важна для предстоящего домашнего задания и проекта. Рассмотрены основы операторов запуска и синхронизации Silk, которые позволяют одновременно выполнять родительские и дочерние функции. Инструктор также подчеркивает важность встречи с членами политики Массачусетского технологического института и предотвращения условий гонки в коде, которые могут привести к катастрофическим последствиям, как видно из прошлых примеров. Сложнее всего обнаружить ошибки гонки, которые привели к катастрофическим событиям, и обычное тестирование часто неэффективно. Silk предлагает инструмент, помогающий выявлять потенциальные гоночные ошибки в коде.
  
  
• 00:05:00 В этом разделе видео объясняется, что гонки являются одной из самых сложных ошибок для разработчиков, потому что они могут возникать только в редких случаях, когда логически параллельные коды обращаются к одной и той же ячейке памяти, и хотя бы один из них регистрирует запись к этому. В качестве примера видео демонстрирует простой код, использующий граф зависимостей, чтобы показать, что ошибка гонки, общая для двух параллельных путей, не всегда возникает. Гонка происходит, когда оба хранилища записывают в одну и ту же ячейку памяти, что может привести к разным результатам в зависимости от того, какой путь выполнения выполняется полностью первым.
  
  
• 00:10:00 В этом разделе спикер объясняет концепцию гонки детерминированности, которая возникает, когда две инструкции обращаются к одной и той же ячейке памяти, и по крайней мере одна из инструкций является операцией записи, что приводит к недетерминированному поведению программы. Докладчик дает советы о том, как избежать гонок, например, обеспечить независимость итераций цикла for в Silk и убедиться, что код между оператором spawn и соответствующим оператором синхронизации Silk также независим. Докладчик также отмечает, что размер машинного слова имеет значение, и следует соблюдать осторожность при чтении и записи упакованных структур данных, использующих нестандартные типы.
  
  
• 00:15:00 В этом разделе видео обсуждается «детектор гонки» платформы Silk, который может помочь определить потенциальные условия гонки в программе. Используя флаг '-f sanitized equal to silk' для создания инструментированной программы, Silk может сообщать и локализовать нарушающие расы, что помогает отлаживать код. Видео также объясняет концепцию параллелизма и то, как модель выполнения Silk использует графы вычислений, чтобы проиллюстрировать развертывание вычислений во время выполнения. Эти концепции важно понимать при попытке оптимизировать и улучшить производительность программы.
  
  
• 00:20:00 типы вершин в dag вычислений: начальная ветвь, пряди продолжения, пряди вызова функции и конечные пряди. Начальная цепочка содержит первую выполняемую команду, а конечная цепочка содержит последнюю выполняемую команду в программе. Нити продолжения представляют собой продолжение операции порождения, тогда как нити вызова функции представляют собой выполнение вызова функции. Важно отметить, что вычисление dag динамически развертывается во время выполнения и не зависит от процессора, что означает, что система среды выполнения определяет, как сопоставить задачи с процессорами во время выполнения. Таким образом, вычисление dag — это мощный инструмент для понимания параллелизма и параллелизма программы.
  
  
• 00:25:00 В этом разделе мы узнаем о вычислительных дагах и о том, как их можно использовать для анализа параллелизма в программе. Вычислительный dag представляет зависимости между различными частями программы и имеет разные типы ребер, включая ребра порождения, ребра вызова, ребра возврата и ребра продолжения. Можно использовать вычислительные даги, чтобы проанализировать степень параллелизма в программе, и мы используем закон Амдала для количественной оценки степени параллелизма. В представленном примере имеется менее семи узлов, которые необходимо выполнить последовательно, что указывает на некоторую степень параллелизма в вычислениях.
  
  
• 00:30:00 В этом разделе вводится понятие закона Амдала как способ определения максимально возможного ускорения при параллельной обработке. Определено, что последовательная часть программы составляет 3/18, что приводит к максимальному ускорению 6. Хотя закон Амдала обеспечивает верхнюю границу параллелизма, в практических случаях он часто слишком неточен. Закон работы и закон интервала вводятся как альтернативные определения параллелизма, при этом закон работы утверждает, что время выполнения на процессорах P больше или равно работе программы, деленной на P, а закон интервала утверждает, что время выполнения на P процессорах не меньше времени выполнения на бесконечном числе процессоров. Эти законы во многих случаях обеспечивают лучшие верхние границы максимального ускорения, чем закон Амдала.
  
  
• 00:35:00 В этом разделе спикер обсуждает, как составить работу и охватить объемы различных вычислений. Они объясняют, что при выполнении двух параллельных вычислений работа по-прежнему является суммой работы отдельных вычислений, а интервал — это максимум интервала отдельных вычислений. Докладчик также определяет ускорение процессоров P и обсуждает сублинейное, линейное и сверхлинейное ускорение. Они отмечают, что максимально возможное ускорение равно параллелизму вычислений, который равен среднему объему работы за шаг вычисления. В целом, этот раздел дает представление о составе вычислений и о том, как измерить их параллелизм.
  
  
• 00:40:00 В этом разделе спикер обсуждает, как проанализировать работу и объем вычислений для вычисления максимального параллелизма, используя такие примеры, как вычисление DAG и параллельный алгоритм быстрой сортировки. Докладчик представляет анализатор масштабируемости Silk Scale, который использует инструментарий компилятора для анализа последовательного выполнения программы и получения верхних границ параллельного ускорения программы. Спикер также упоминает, что анализ параллелизма больших вычислений вручную может быть утомительным, но в этом может помочь Silk Scale.
  
  
• 00:45:00 В этом разделе видео обсуждаются результаты выполнения параллельных вычислений и построения графика, показывающего наблюдаемое ускорение, а также границы диапазона и законов работы. На графике видно, что максимальное ускорение составляет около 5, что указывает на низкий уровень параллелизма в программе. Анализ показывает, что узким местом параллелизма является последовательное выполнение функции разделения, а ожидаемая работа и диапазон параллельной версии быстрой сортировки составляют порядка n log n. Максимальный параллелизм, которого можно достичь, порядка log log n, что не очень много. Чтобы увеличить параллелизм, статистическая сумма должна быть распараллелена.
  
  
• 00:50:00 В этом разделе спикер обсуждает важность реализации параллелизма в алгоритмах разделения и сортировки слиянием, чтобы увидеть значительное ускорение. Параллельные версии этих алгоритмов имеют общий диапазон, ограниченный логарифмом в квадрате n, и высоким параллелизмом n по log n. Кроме того, существует много других практических параллельных алгоритмов, которые имеют высокий параллелизм и предел работы, асимптотически равный пределу работы соответствующего последовательного алгоритма. Докладчик также представляет концепцию теории планирования, объясняя, что централизованный планировщик может сопоставлять вычислительные DAG с доступными процессорами во время выполнения, в то время как распределенный планировщик используется в программировании Silk. В качестве примера используется жадный планировщик, который делает как можно больше на каждом шаге вычислений.
  
  
• 00:55:00 В этом разделе вводится понятие жадного планировщика, который выполняет как можно больше работы на текущем временном шаге, не думая о будущем. Определены полный этап, на котором готово не менее P цепей, и незавершенный этап, на котором готово меньше P цепей. Знаменитая теорема, впервые показанная Роном Грэмом в 1968 году, утверждает, что граница времени, достигнутая жадным планировщиком, меньше или равна T1/P + T бесконечности, где T1 — это работа, а T бесконечность — промежуток. Приведено доказательство этой теоремы и показано, что любой жадный планировщик достигает оптимального времени работы с точностью до двух раз.
  
  
• 01:00:00 В этом разделе в видео объясняются следствия привязки жадного планировщика, которая в два раза превосходит оптимальный планировщик. Следствие гласит, что любой жадный планировщик достигает почти идеального линейного ускорения, когда T1/Tinfinity больше или равно P^2, где T1/P, умноженное на T бесконечность, измеряет количество параллелизма в вычислениях по сравнению с количеством процессоров. доступный. Шелковый планировщик использует планировщик кражи работы, который имеет ожидаемое время работы TP, равное T1/P плюс бесконечность порядка T, с большой буквой O перед бесконечностью T, чтобы учесть накладные расходы планирования, и может достигать почти идеальное линейное ускорение, если количество процессоров намного меньше, чем у T1/Tinfinity. Система Silk Runtime работает, поддерживая рабочую колоду готовых нитей и манипулируя нижней частью колоды, как стопкой. Инструментарий в Silk Scale позволяет измерять условия работы и интервала для определения параллелизма в программе.
  
  
• 01:05:00 В этом разделе спикер обсуждает концепцию порождения и параллелизма в процессорах. Они объясняют, что когда процессор вызывает функцию, он помещает кадр этой функции в нижнюю часть стека и может создавать кадры в нижней части стека. Несколько процессов могут происходить параллельно, а возвраты могут выполняться из порождений и вызовов. Когда у рабочих заканчивается работа, они воруют с вершины колоды другого процессора. Знаменитая теорема утверждает, что рабочие воруют очень редко, что дает почти линейное ускорение. Докладчик также отмечает, что Silk поддерживает правила C для указателей, согласно которым указатель на пространство стека может передаваться от родителя к дочернему, но не от дочернего к родительскому.
  
  
• 01:10:00 В этом разделе видео спикер обсуждает стек Cactus, который представляет собой стек, который можно увидеть задачей в графе вычислений предка программы Silk. Этот стек позволяет параллельно просматривать несколько стеков, что делает возможным параллельный вызов функций. Докладчик объясняет, что пространство стека, необходимое для программы Silk, можно найти, взяв пространство стека, необходимое для последовательного выполнения программы (S sub 1), и умножив его на количество процессоров (P), которые будут использоваться (S sub P ≤ P x S sub 1). Докладчик представляет высокоуровневое доказательство этой концепции и отмечает, что верхняя граница пространства стека, необходимого для выполнения процессора P, часто намного меньше, чем фактически необходимый объем, поскольку каждому процессору может не потребоваться проходить весь путь вниз по графу вычислений каждый раз. время крадет работу.

[MetaQuotes]

Лекция 8. Анализ многопоточных алгоритмов

Лекция 8. Анализ многопоточных алгоритмов

В этом видео обсуждается основной метод анализа повторяющихся операций «разделяй и властвуй» и применяется к многопоточным алгоритмам путем сравнения логарифмической базы B числа n с логарифмической базой B числа A с F числа N, чтобы определить их рост в n и требуемую работу. Видео представляет собой памятку с решениями для основных многопоточных алгоритмов и охватывает такие темы, как анализ работы и диапазона, эффективность работы и преодоление накладных расходов за счет оптимизации размера зерна. Подчеркивается важность эмпатии при обсуждении технических тем, и вводится концепция группы обеспечения доступности баз данных как средства балансировки работы и объема для увеличения параллелизма и сокращения времени выполнения.

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

• 00:00:00 В этом разделе инструктор начинает с напоминания учащимся о повторениях «разделяй и властвуй» и общем методе их решения, который называется мастер-методом. Метод имеет дело с повторениями и их формой T(n) = a*T(n/B) + F(n), где a — константа, B — коэффициент разделения, а F(n) — общий объем работы. разбить задачу на подзадачи размера n/B. Студентам напоминают о дереве рекурсии и о том, как каждый уровень разбивается на подзадачи размера n/B, они добавляют время выполнения по строкам, вычисляют высоту дерева и умножают ее на количество подзадач на каждом уровне (a ^к). Наконец, учащиеся подсчитывают, что n^log основания B числа A равно общему времени выполнения алгоритма.
  
  
• 00:05:00 В этом разделе спикер объясняет, как определить рост n и работу, необходимую при оценке многопоточных алгоритмов. Суть в том, чтобы сравнить логарифмическую основу B числа n с логарифмической основой B числа A и F числа N. Выступающий рассматривает три возможных случая, первый из которых — когда логарифмическое основание B n намного больше, чем F числа n. В этом случае постоянная доля веса находится в листьях, что приводит к ответу n по логарифмической основе B числа A. Второй случай — это когда логарифмическая база B n приблизительно равна F n. Для этого вы добавляете дополнительное бревно, и ответом является n в логарифмическом основании B бревна в k плюс 1 из n. Наконец, третий случай — это когда отношение к логарифмической базе B намного меньше, чем F от N, а это означает, что F должно удовлетворять условию регулярности, которому удовлетворяют все функции, которые они будут рассматривать, такие как полиномы и логарифмы.
  
  
• 00:10:00 В этом разделе спикер представляет шпаргалку с решениями основных многопоточных алгоритмов, которые обычно используются в информатике. Первый алгоритм, T(n) = T(n/2) + n, имеет решение Θ(n^2), поскольку он подпадает под первый случай. Второй алгоритм, T(n) = T(n/2) + n^2logn, имеет решение Θ(n^2logn), поскольку он подпадает под случай два с k = 0. Для третьего алгоритма T(n) = T(n/2) + n^2, решение равно Θ(n^2), поскольку оно подпадает под первый случай. Четвертый алгоритм, T(n) = 2T(n/2) - n, является сложным, поскольку он не подпадает ни под один из случаев основного метода и имеет решение Θ(n^2loglogn).
  
  
• 00:15:00 В этом разделе спикер обсуждает метод Аква Бацзы и то, насколько он сложнее мастер-метода, которого достаточно для анализа большинства программ. Затем они предоставляют пример параллельного цикла с кодом транспонирования матрицы на месте, где внешний цикл распараллелен. Докладчик подчеркивает важность правильного определения пространства итераций и балансировки нагрузки для эффективной параллельной обработки. Они также объясняют, как циклы реализуются компилятором Open Silk и системой выполнения.
  
  
• 00:20:00 В этом разделе спикер описывает рекурсивную программу для цикла, которая использует разделяй и властвуй, чтобы разделить цикл на две части и рекурсивно вызывать себя с каждой стороны, пока не будет достигнута итерация с одним элементом. Работа этого вычисления анализируется с точки зрения работы и диапазона, при этом работа листа представляет собой порядок n в квадрате, а верхняя часть представляет собой тета n, потому что каждый уровень от листьев до корня имеет только n узлов. Система Open Silk Runtime не имеет примитива цикла, поэтому циклы эффективно преобразуются в этот подход «разделяй и властвуй» параллельно.
  
  
• 00:25:00 В этом разделе спикер обсуждает работу и анализ диапазона многопоточного алгоритма. Он объясняет, что общая работа равна Θ(n²), потому что постоянная работа выполняется для каждого из n листьев полного бинарного дерева. Диапазон управления циклом равен log(n), что означает, что бесконечное количество процессоров может выполнить задачу за логарифмическое время. Однако, поскольку в вычислении (n) есть линейная составляющая, общий диапазон равен Θ(n). Следовательно, параллелизм равен Θ(n), что является хорошей величиной для большинства практических систем. Затем спикер исследует сценарий, в котором внутренний цикл также распараллелен, и обсуждает полученный объем работы.
  
  
• 00:30:00 В этом разделе видео профессор обсуждает концепцию эффективности работы в параллельных алгоритмах. Распараллеливание алгоритмов не меняет работу, но, надеюсь, должно уменьшить размах вычислений, чтобы добиться большого параллелизма. Однако иногда распараллеливание может привести к увеличению объема работы, что может быть проблематично, поскольку замедляет программу по сравнению с исходным алгоритмом. Профессор заинтересован в обучении эффективным параллельным алгоритмам, поскольку они могут уменьшить диапазон для достижения большого параллелизма без дополнительной работы. Профессор подчеркивает важность задавать вопросы и делать ошибки в процессе обучения, так как это может помочь другим, у которых могут быть такие же вопросы, но они боятся задавать. Он призывает студентов участвовать и вовлекаться в учебный процесс, даже если они не входят в 10% лучших.
  
  
• 00:35:00 В этом разделе подчеркивается важность эмпатии в общении, когда речь идет о технических темах. Профессор призывает студентов быть терпеливыми с другими в классе, которые могут быть не знакомы с изучаемым материалом. Переходя к анализу многопоточных алгоритмов, представлен алгоритм «разделяй и властвуй» для сложения векторов, и установлено, что параллелизм n превышает log n. Обсуждается взаимосвязь между параллелизмом и количеством процессоров, при этом профессор подчеркивает, что, хотя больший параллелизм может показаться лучше, он полезен только до определенного порога.
  
  
• 00:40:00 В этом разделе спикер обсуждает оптимизацию некоторых накладных расходов в многопоточном алгоритме, в частности накладных расходов на вызов подпрограммы. Они вводят понятие «размер зерна», которое предполагает, что компилятор может иметь до G элементов на фрагмент в конце процесса «разделяй и властвуй». Это позволяет амортизировать накладные расходы подпрограммы на G итераций, а не только на одну, что приводит к повышению производительности. Если размер зерна не указан, система делает наилучшее предположение, чтобы минимизировать накладные расходы. Докладчик разбирает переменные I, G и s, чтобы проанализировать работу в этом контексте и сравнить ее с работой в исходном коде без параллельного контроля.
  
  
• 00:45:00 В этом разделе спикер рассказывает об анализе многопоточных алгоритмов и о том, как дешево обходится управление циклом на современном вышедшем из строя процессоре. Они рассматривают интервал, то есть время, необходимое для выполнения алгоритма с бесконечным числом процессоров, и обсуждают накладные расходы по сравнению со стоимостью итераций. Говорящий разбивает промежутки на количество листьев и красочные операции, обозначаемые буквой «s», которые необходимо выполнить над каждым из них. Они также отвечают на вопросы о количестве внутренних узлов в полном бинарном дереве и путях, используемых для вычисления диапазона.
  
  
• 00:50:00 В этом разделе спикер обсуждает анализ многопоточных алгоритмов, в частности концепцию DAG (ориентированного ациклического графа) и то, как она влияет на путь алгоритма. Они подчеркивают необходимость независимости между различными поддеревьями DAG для обеспечения параллельной обработки. Цель состоит в том, чтобы сбалансировать работу и размах алгоритма, так как эти два фактора работают в противоположных направлениях. Суть в том, чтобы G (величина параллелизма) была намного больше, чем s по сравнению с I (последовательная часть алгоритма), что обеспечивает меньшие накладные расходы и более быструю обработку. Спикер также упоминает реализацию этой концепции, но отмечает, что она будет обсуждаться позже в серии лекций.
  
  
• 00:55:00 В этом разделе спикер представляет реализацию многопоточных алгоритмов, использующих цикл for для сложения двух векторов. В цикле используется оператор с именем V add для выполнения последовательного сложения векторов, и цикл порождает сложения в группах по G с использованием вектора размера G. Предполагая, что G равно единице, работа циклов имеет порядок n, а диапазон также равен заказать н. Параллелизм измеряется отношением объема работы к охвату, которое равно n, деленному на n, что упрощается до 1. Докладчик подчеркивает, что цель анализа многопоточных алгоритмов состоит в повышении параллелизма и уменьшении охвата для минимизации времени выполнения, и выделяет метод называется интеллектуальным анализом полос, где цикл длины N заменяется двойным вложенным циклом для распараллеливания вычислений, что является одним из способов улучшения многопоточных алгоритмов.
  
  
• 01:00:00 В этом разделе спикер анализирует производительность многопоточных алгоритмов с точки зрения работы и диапазона. Они обсуждают, как минимизировать диапазон, чтобы максимизировать параллелизм, поскольку диапазон находится в знаменателе. Ключ в том, чтобы генерировать в десять раз больше параллелизма, чем процессоры, если нужно почти идеальное линейное ускорение. Докладчик также предлагает отказаться от некоторого параллелизма, чтобы при необходимости уменьшить накладные расходы. Они рекомендуют возиться с размером зерна, пока сохраняется достаточный параллелизм.
  
  
• 01:05:00 В этом разделе спикер обсуждает использование стратегии «разделяй и властвуй» в многопоточных алгоритмах, советуя не создавать множество небольших задач одну за другой, если только они не разбиты на несколько задач, в этом случае накладные расходы Это хорошо. Как правило, должен применяться подход «разделяй и властвуй», когда количество задач, отдаваемых потокам, достаточно велико. Докладчик предупреждает о необходимости следить за планированием накладных расходов и предлагает распараллелить внешний цикл вместо внутренних циклов, которые имеют больше накладных расходов. Примеры кода, представленные здесь, показывают эффективный код, в котором планирование происходит только один раз, и плохой код, в котором накладные расходы возникают n раз. Умножение матриц используется в качестве примера многопоточного алгоритма, использующего стратегию «разделяй и властвуй» для умножения n на n матриц путем выполнения 8 умножений n на 2 на n на 2 матрицы, а затем добавления двух матриц n на n.
  
  
• 01:10:00 В этом разделе спикер обсуждает, как представлять подматрицы в двумерном кодировании и индексации, в частности, в основном порядке строк и столбцов для таких языков, как C и Fortran. Идея состоит в том, что каждая двумерная матрица может быть проиндексирована как одномерная матрица, а при работе с подматрицами нужно добавить количество строк и длину длинной матрицы, чтобы узнать, где находится элемент IJ. Кроме того, при реализации принципа «разделяй и властвуй» крайне важно знать начальные углы каждой из четырех подматриц. В конечном счете, спикер подчеркивает использование «restrict» в коде умножения матриц «разделяй и властвуй», чтобы сообщить компилятору, какие элементы могут или не могут быть псевдонимами.
  
  
• 01:15:00 В этом разделе спикер обсуждает многопоточный алгоритм умножения матриц. Алгоритм основан на рекурсивном подразделении матриц на более мелкие подматрицы, при этом каждая подматрица рекурсивно умножается для получения конечного результата. Докладчик рассказывает о небольшой хитрости, позволяющей быстро определить, является ли n степенью двойки, и использует макрос для упрощения индексации матриц. Алгоритм демонстрирует высокий уровень параллелизма, который можно уменьшить для повышения производительности. Упоминаются и другие подобные алгоритмы.

[MetaQuotes]

Лекция 9. Что могут и чего не могут компиляторы

Лекция 9. Что могут и чего не могут компиляторы

В этом видео на различных примерах обсуждается, как компиляторы могут оптимизировать код. В нем объясняется, как компиляторы могут устранить ненужные ссылки на хранилище и память и как они могут оптимизировать циклы для повышения производительности.

В этом видео также объясняется концепция проходов оптимизации компилятора и то, как их можно использовать для повышения производительности кода. Также обсуждаются ограничения компиляторов, особенно в отношении векторизации. Компиляторы могут векторизовать код только в том случае, если они могут определить, что указатели в коде не будут псевдонимами. Если указатели делают псевдоним, компилятор не сможет векторизовать код. Как программист, вы можете помочь компилятору, аннотировав свои указатели, чтобы предоставить больше информации об их использовании.

• 00:00:00 В этой лекции Тао Шардл обсуждает, что могут и чего не могут делать компиляторы. Он объясняет, что изучение оптимизаций компилятора может помочь разработчикам понять, как писать код, использующий преимущества оптимизации, и как избежать ручной оптимизации кода, который компилятор уже может оптимизировать.
  
  
• 00:05:00 Компилятор — это большая часть программного обеспечения, и он может абсолютно помочь в отладке, когда в самом компиляторе есть ошибки. Это помогает понять, где компилятор мог допустить ошибку или где компилятор просто не сделал то, что, по вашему мнению, он должен был сделать.
  
  
• 00:10:00 Компилятор может многое оптимизировать, но есть вещи, которые он сделать не может. Например, он не всегда может создать быстрый путь или оптимизировать циклы.
  
  
• 00:15:00 Компилятор может многое сделать для оптимизации кода, но есть вещи, которые он не может делать хорошо. Одним из примеров являются структуры данных — компилятор не так хорошо разбирается в них, как в функциях. Другое дело — циклы — компилятор может их оптимизировать, но есть ограничения.
  
  
• 00:20:00 В этом видео на YouTube объясняется, как компиляторы могут использовать простые операции для замены более сложных. Например, чтобы заменить операцию деления, компилятор может умножить на магическое число, а затем сдвинуть результат. В этом видео также объясняется, как работает адресный калькулятор.
  
  
• 00:25:00 В видео обсуждается, как компиляторы могут оптимизировать код, на примере простой функции "vex scale". Код сначала показан без оптимизаций, а затем с применением различных оптимизаций. Показанные оптимизации включают сокращение количества инструкций, использование векторных инструкций и использование магических чисел.
  
  
• 00:30:00 В этом видео обсуждается, как компиляторы могут оптимизировать код, исключив ненужные операции с памятью. В частности, показано, как компилятор может оптимизировать функцию, умножающую два скалярных значения, избавляя от необходимости хранить эти значения в памяти. Наконец, он показывает, как компилятор может оптимизировать функцию, работающую со структурой, избавляя от необходимости хранить структуру в памяти.
  
  
• 00:35:00 В этом видео на YouTube спикер объясняет, как компиляторы могут оптимизировать код, устраняя ненужные ссылки на хранилище и память. Он использует пример структуры с несколькими полями и демонстрирует, как компилятор может оптимизировать код, тщательно анализируя математику, связанную с вычислением адресов. Понимая, что делает каждая инструкция, компилятор может оптимизировать код и удалить ненужные операции.
  
  
• 00:40:00 Компилятор усердно работает над преобразованием структур данных и скалярных значений, чтобы хранить как можно больше только в регистрах и избегать использования любого локального хранилища, если это возможно. Для вызовов функций компилятор видит инструкцию вызова и код вызываемой функции. Затем он пытается сделать функцию в приведенном выше коде еще быстрее.
  
  
• 00:45:00 Компилятор может встраивать код, чтобы избежать накладных расходов на вызовы функций, а также оптимизировать код, удаляя ненужные операции.
  
  
• 00:50:00 В этом видео на YouTube спикер объясняет, что есть три основные причины, по которым компилятор может не встроить функцию: если функция рекурсивная, если функция находится в другой единице компиляции или если функция может увеличиваться размер кода и снижение производительности. Докладчик также дает несколько советов по управлению встраиванием функций в собственные программы.
  
  
• 00:55:00 В этом видео показано, как компиляторы могут оптимизировать циклы, чтобы программы работали быстрее. Поднятие кода или перемещение кода, не зависящее от циклов, — это одна из оптимизаций, которую можно использовать для повышения производительности.
  
  
• 01:00:00 Компилятор может оптимизировать код, выполняя последовательность проходов преобразования. Эти проходы предназначены для поиска таких свойств, как вычисление идентичных адресов, и замены их более эффективным кодом.
  
  
• 01:05:00 Компилятор умеет векторизовать этот цикл, несмотря на то, что он не знает, перекрываются ли адреса 'x' и 'y'. Это связано с тем, что структура скомпилированного кода сложнее, чем двухстрочная функция, которая была дана на вход.
  
  
• 01:10:00 В этом видео на YouTube объясняется, что могут и чего не могут делать компиляторы. Компиляторы могут векторизовать код, если код не содержит циклов. Однако, если код содержит циклы, компилятор может векторизовать код только в том случае, если цикл заполнен векторными операциями. Если цикл не заполнен векторными операциями, компилятор не сможет векторизовать код.
  
  
• 01:15:00 Вопрос о том, может ли компилятор векторизовать код, сложный, так как зависит от ряда факторов. В частности, компилятор должен иметь возможность определить, будут ли два указателя иметь псевдоним, что может быть сложной задачей. Как программист, вы можете помочь компилятору, аннотировав свои указатели, чтобы предоставить больше информации об их использовании.

[MetaQuotes]

Лекция 10. Измерение и хронометраж

Лекция 10. Измерение и хронометраж

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

Докладчик объясняет важность надежного измерения производительности в разработке программного обеспечения. Он рекомендует использовать статистику для точного измерения производительности и обсуждает различные типы сводной статистики, такие как среднее значение, которое может обеспечить полезные измерения производительности в различных контекстах. Он указывает, что использование среднего арифметического отношения не является допустимым подходом, и предлагает вместо этого использовать среднее геометрическое. Докладчик подчеркивает важность выбора правильного способа агрегирования данных при сравнении программ и предлагает брать статистику низкого порядка, такую как минимум или 10%, из нескольких прогонов для более точного сравнения производительности. Докладчик также обсуждает различные методологии измерения и сравнения производительности, в том числе непосредственное сравнение и подбор модели для получения статистики, но предупреждает о проблеме чрезмерного подбора при моделировании. В целом видео подчеркивает важность надежного измерения производительности для повышения производительности программы.

• 00:00:00 В этом разделе спикер обсуждает исследование кода сортировки, которое провел один из его бывших студентов. Код использует заголовочный файл time.h, чтобы получить доступ к процедуре получения времени для измерения времени. Процедура сортировки рассчитана по времени, и прошедшее время вычисляется и распечатывается. График измеренного времени выполнения показывает, что процедура сортировки в основном соответствует росту N log N, но измеренное время медленное даже для самых больших массивов.
  
  
• 00:05:00 В этом разделе профессор обсуждает важность наличия модели наблюдаемых данных. Он представляет пример, когда измеренные данные значительно отклоняются от ожидаемых, и просит учащихся предложить возможные гипотезы для этого отклонения. Хотя некоторые думали, что это может быть проблема с кешем или точностью синхронизации, профессор указывает, что на машине могут быть несвязанные процессы, которые вызывают отклонение. В этом случае проблема связана с мультиарендностью, когда машина используется более чем одним процессом одновременно. Профессор подчеркивает необходимость качественных измерений и четкого понимания того, что означают данные.
  
  
• 00:10:00 В этом разделе спикеры обсуждают измерение и синхронизацию в вычислениях, а также то, как внешние факторы могут повлиять на точность измерений. Особое внимание уделяется тому, как могут происходить изменения тактовой частоты из-за температуры системы и методов энергосбережения, что может существенно повлиять на результаты измерений. Динамики представляют концепцию динамического масштабирования частоты и напряжения, которая представляет собой метод снижения мощности путем регулировки тактовой частоты и напряжения на транзисторах. Они подчеркивают, что крайне важно учитывать внешние факторы при проведении измерений, чтобы избежать неточных результатов.
  
  
• 00:15:00 В этом разделе спикер обсуждает проблемы измерения производительности программного обеспечения из-за степенного закона, который используют инженеры-электрики. Степенной закон гласит, что мощность равна CV в квадрате F, где C — динамическая емкость, V — напряжение питания, а F — тактовая частота. Чтобы уменьшить мощность и тепло, можно уменьшить частоту и напряжение, что приведет к кубическому снижению мощности. Это создает проблему для надежного измерения производительности программного обеспечения, и выступающий предлагает стабилизировать системы, избавившись от части шума, чтобы проводить точные измерения. Они также обсуждают инструменты для измерения производительности программного обеспечения, такие как моделирование производительности.
  
  
• 00:20:00 В этом разделе спикер обсуждает важность уменьшения дисперсии, когда речь идет об измерении и времени, особенно в контексте разработки производительности. Снижая изменчивость, можно компенсировать систематические и случайные ошибки измерения и требовать меньше испытаний для сравнения программ. Докладчик также указывает на различные источники изменчивости компьютерных систем, в том числе на фоновые задания, прерывания и размещение потоков. Наконец, он подчеркивает важность сосредоточения внимания на снижении дисперсии, прежде чем пытаться внести изменения в систему, поскольку измерения при высокой дисперсии могут привести к ненадежным результатам.
  
  
• 00:25:00 В этом разделе спикер рассказывает о концепции гиперпоточности в процессорах и о том, как она может привести к неточным измерениям в облачных системах. Гиперпоточность запускает два потока инструкций через один функциональный блок, который выглядит как два процессора, но на самом деле обеспечивает только 20-процентное ускорение, а не два отдельных процессора. Докладчик также обсуждает другие методы, такие как турбонаддув и стабилизация системы, которые могут существенно повлиять на результаты измерений. Отключив Hyper-Threading и Turbo Boost, а также успокоив всех демонов, спикер и его группа смогли добиться исключительно надежных измерений, которые были менее чем на 1% медленнее, чем минимальное время выполнения.
  
  
• 00:30:00 В этом разделе спикер рассказывает о различных факторах, которые могут повлиять на детерминированность программы, работающей на современном оборудовании. Хотя есть определенные меры, которые можно предпринять, чтобы сделать программу более детерминированной, невозможно полностью исключить недетерминированные факторы. Большинство недетерминированных факторов, которые могут возникнуть во время выполнения программы, такие как кэширование, прерывания, многопоточность и прогнозирование ветвлений, являются детерминированными процессами. Однако случайность в оборудовании находится вне контроля пользователя и может привести к ошибке памяти. Докладчик предполагает, что выравнивание кода может повлиять на детерминизм программы, и любое изменение, сделанное в коде, может вызвать сдвиг в выравнивании кеша, влияющий на детерминизм программы.
  
  
• 00:35:00 В этом разделе спикер обсуждает, как небольшие изменения могут сильно повлиять на производительность программы. Например, вставка одного байта может линейно повлиять на все, что следует за ним, а изменение порядка появления файлов с точками в командной строке компоновщика может иметь больший эффект, чем переход между -OH- и -O3. Чтобы решить эти проблемы, компиляторы осознают проблему и проводят дополнительное согласование. LLVM имеет переключатели, которые могут выравнивать все функции и блоки в функции, но выравнивание может замедлить работу программы. Кроме того, имя программы может повлиять на ее скорость, поскольку имя исполняемого файла заканчивается в переменной среды, которая заканчивается в стеке вызовов.
  
  
• 00:40:00 В этом разделе спикер обсуждает различные инструменты и методы измерения производительности программного обеспечения, в том числе внешнее измерение программы с помощью команды time, ввод в программу вызовов времени с помощью clock get time или другими методами, прерывание программы с помощью gdb чтобы определить, какая процедура занимает больше всего времени, используя аппаратную поддержку и поддержку ОС, например те, которые используются в наборе инструментов perf, или моделируя программу, чтобы получить более глубокое понимание, но с более низкой скоростью. Докладчик объясняет разницу между прошедшим временем, пользовательским временем и системным временем при использовании команды времени, а также то, как они могут не складываться в общее время из-за распределения процессора.
  
  
• 00:45:00 В этом разделе докладчик обсуждает различные типы синхронизации и измерения, включая время настенных часов, время процессора, проведенное в пользовательском режиме, и время, проведенное в ядре. Вызов синхронизации, рекомендуемый для использования, - это время получения времени с опцией монотонности часов, которая гарантирует, что никогда не будет работать в обратном направлении. Хотя для запуска может потребоваться недетерминированное время, он более надежен, чем другие таймеры, такие как RTIDTSC, которые могут давать разные ответы на разных ядрах и могут работать в обратном направлении. Спикер предостерегает от использования get time of day.
  
  
• 00:50:00 В этом разделе спикер обсуждает различные способы измерения и времени событий в программировании, включая использование clock_gettime и измерение с помощью команды time. Они предупреждают, что со временем методы могут измениться, и инженерам, возможно, придется адаптироваться. Спикер также предлагает прерывать код в случайные моменты в качестве простого метода профилирования и упоминает, что этот метод используют крупные компании, такие как Facebook. Кроме того, спикер представляет идею аппаратных счетчиков и библиотеки livepFM4, которая обеспечивает доступ к этим счетчикам для каждого процесса. Они подчеркивают, что инженеру не всегда могут понадобиться хирургически точные инструменты и что иногда для работы может быть достаточно простого инструмента.
  
  
• 00:55:00 В этом разделе спикер обсуждает разные способы сбора измерений, включая аппаратные счетчики и симуляторы. Они предупреждают, что многие аппаратные счетчики плохо документированы и что некоторые инструменты разделяют полосу пропускания, если используется более четырех или пяти счетчиков. Симуляторы хвалят за их повторяемость, но они могут не моделировать все в кеше. Спикер рекомендует провести триангуляцию и использовать как минимум два измерения для обеспечения точности. Они также подчеркивают важность наличия модели производительности для руководства интерпретацией данных.
• 01:00:00 В этом разделе спикер объясняет процесс разработки производительного программного обеспечения, который включает в себя создание программы, внесение в нее изменений и измерение ее производительности для создания более быстрой программы. Тем не менее, надежное измерение производительности жизненно важно для внесения небольших изменений, которые суммируются и делают точные выводы. Поэтому спикер рекомендует использовать статистику для получения точной картины происходящего. Он также предлагает головоломку, включающую измерение исходной производительности детерминированной программы, и приходит к выводу, что использование минимума — лучший способ подавить шум и определить базовую производительность аппаратного обеспечения программы.
  
  
• 01:05:00 В этом разделе обсуждаются различные типы сводной статистики, включая среднее значение, которое может предоставить полезные показатели производительности в различных контекстах. При оценке веб-серверов загрузка ЦП и общее время выполнения задачи могут быть измерены с использованием среднего арифметического, в то время как время настенных часов и процентное поведение могут быть более актуальными для оптимизации удовлетворения запросов. Однако при суммировании коэффициентов, например при сравнении производительности программ A и B, использование среднего арифметического не является допустимым подходом, даже несмотря на то, что им часто злоупотребляют. Это связано с тем, что среднее значение отношений не совпадает с самим отношением, как показано в примере, приведенном в видео.
  
  
• 01:10:00 В этом разделе спикер обсуждает вопросы сравнения коэффициентов и средних при измерении эффективности. Они демонстрируют, что использование среднего арифметического отношения может привести к сомнительным результатам, и лучше использовать среднее геометрическое. Кроме того, они отмечают, что при сравнении скоростей часто полезно использовать среднее гармоническое. Подчеркивается важность выбора правильного способа агрегирования данных при сравнении программ, и спикер предлагает брать статистику низкого порядка, такую как минимум или 10%, из нескольких прогонов для более точного сравнения производительности.
  
  
• 01:15:00 В этом разделе спикер обсуждает различные методологии измерения и сравнения производительности. Один из подходов заключается в сравнении 10% самых дешевых вариантов и уменьшении шума для сравнения средних значений, хотя это может не дать убедительных доказательств. В качестве альтернативы можно провести прямое сравнение между A и B, чтобы увидеть, кто из них выигрывает чаще. Благодаря этому можно проверить нулевую гипотезу и рассчитать p-значение, чтобы определить, является ли отклонение значительным. Этот метод обычно используется в социальных науках и может быть полезен в шумной среде. Наконец, выступающий кратко затрагивает идею подгонки модели для получения статистики и обсуждает использование аппроксимации методом наименьших квадратов.
  
  
• 01:20:00 В этом разделе спикер обсуждает проблему избыточной подгонки в моделировании и то, как добавление дополнительных базовых функций может улучшить соответствие данных, но также может привести к избыточной подгонке. Решение состоит в том, чтобы удалить базисную функцию и проверить, влияет ли она на качество модели. Оратор также упоминает лорда Кельвина, известного как Гуру измерения, который заявил, что измерять — значит знать, и если нельзя измерить, нельзя улучшить. Видео заканчивается тем, что спикер желает удачи в викторине во вторник.