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

[MetaQuotes]

Лекция 11. Распределение памяти

Лекция 11. Распределение памяти

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

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

• 00:00:00 В этом разделе лектор обсуждает распределение памяти, которое включает в себя как выделение памяти, так и ее освобождение. Простейшей формой хранения является стек, в котором память выделяется путем увеличения указателя стека и освобождается путем уменьшения указателя стека. Однако стек имеет ограниченное применение, поскольку он может освободить только то, что было выделено последним, и не может освободить ничего в середине используемой области. Также лектор отмечает, что из соображений эффективности компиляторы обычно не проверяют переполнение стека.
  
  
• 00:05:00 В этом разделе лектор рассказывает о двух видах хранения: стек и куча. Стек представляет собой хранилище фиксированного размера, которое является эффективным, но не может использоваться для всего, в то время как куча является более общей, но ее трудно организовать и эффективно использовать. Для выделения кучи можно использовать функции malloc и free C, но, поскольку C и C++ не предоставляют сборщика мусора, программистам приходится самим управлять памятью, что может привести к утечкам памяти, висячим указателям и двойному освобождению. Лектор предлагает использовать средства проверки памяти, такие как address sanitizer и Valgrind, чтобы уменьшить количество ошибок памяти в программе.
  
  
• 00:10:00 В этом разделе спикер обсуждает различные способы распределения хранилища, начиная с выделения фиксированного размера, при котором каждая часть хранилища имеет одинаковый размер, и некоторые блоки используются, а другие не используются. Неиспользуемые блоки хранятся в списке, который называется свободным списком, и каждый блок в свободном списке имеет указатель на следующий блок в списке. Чтобы выделить один объект из списка свободных, программа устанавливает указатель как свободный, а затем устанавливает указатель свободных мест так, чтобы он указывал на следующий объект в списке свободных, возвращая указатель на первый объект в списке свободных. Чтобы освободить, нужно просто установить следующий указатель объекта на свободный и установить свободный равный объекту, который нужно освободить. В свободном списке выделение и освобождение занимают постоянное время, а также достигается хорошая временная локальность.
  
  
• 00:15:00 В этом разделе вводится понятие внешней фрагментации, которая возникает, когда блоки используемой памяти рассредоточены по пространству всей памяти. Это может привести к увеличению размера таблицы страниц, что может вызвать перегрузку диска и снизить эффективность поиска переводов. Чтобы уменьшить внешнюю фрагментацию, можно использовать свободный список или растровое изображение для каждой страницы диска, а также можно выполнять выделение из самой полной страницы, освобождение блоков историй и разбиение на страницы пустых страниц. Выделение кучи фиксированного размера также может быть полезно для уменьшения внешней фрагментации. Наконец, выделение кучи переменного размера можно использовать со списками свободных ячеек, которые используют эффективность списков свободных мест для разных размеров выделенной памяти.
  
  
• 00:20:00 В этом разделе представлена схема хранения блоков памяти разного размера в системе распределения памяти. Схема включает в себя деление блоков на ячейки в зависимости от их размера, причем каждая ячейка содержит блоки определенного размера, которые являются степенью двойки. При выделении памяти соответствующий бин выбирается на основе запрошенного размера, и если он пуст, больший непустой бин разбивается на более мелкие фрагменты для получения желаемого размера. Однако эта схема может привести к внутренней фрагментации памяти, что является расточительным, поэтому количество используемых ячеек ограничено, а небольшие блоки группируются в страницы для уменьшения накладных расходов. Операционная система может использоваться для предоставления большего объема памяти, если это необходимо, и для этой цели доступны системные вызовы.
  
  
• 00:25:00 В этом разделе видео обсуждается, как работает выделение памяти, и отмечается, что стандартные реализации malloc полагаются на такие команды, как break, для получения памяти из операционной системы. ОС выделяет большой кусок памяти, и система распределения памяти должна разбивать его на более мелкие блоки. В этом разделе также рассматриваются варианты распределителя памяти, в том числе различные схемы хранения размеров блоков и то, как адресное пространство виртуальной памяти размещается в программе. Он отмечает, что стек и куча растут навстречу друг другу, но никогда не пересекаются. Наконец, упоминается, что предварительное вычисление больших таблиц констант в программе может увеличить время загрузки, так как требует чтения из сегмента данных.
  
  
• 00:30:00 В этом разделе обсуждается проблема фрагментации виртуальной памяти, которая может привести к внешней фрагментации, ухудшению производительности таблицы страниц, перегрузке диска и низкой частоте попаданий TLB, если память распределена. Цель выделения памяти состоит в том, чтобы использовать как можно меньше виртуальной памяти, сохраняя при этом компактность используемых частей памяти. Анализируется схема распределения списка свободных бинов с помощью теоремы, утверждающей, что объем виртуальной памяти, потребляемой хранилищем кучи, ограничен сверху M log M. Объединение меньших блоков в более крупные может улучшить схему списка свободных бинов, но накладные расходы этот метод может быть высоким по сравнению со стандартным алгоритмом списка свободных бинов, который, согласно статье Чарльза Лейзерсона, лишь на постоянный множитель хуже, чем оптимальный распределитель.
  
  
• 00:35:00 В этом разделе спикер объясняет концепцию выделения памяти и то, как она может уменьшить фрагментацию при работе с хранилищем в куче. Он также обсуждает идею сборки мусора, которая избавляет программиста от необходимости вручную освобождать объекты. Докладчик объясняет три типа объектов памяти — корни, живые объекты и мертвые объекты — и как сборщик мусора может перерабатывать последние. Наконец, он описывает подсчет ссылок, простую форму сборки мусора, которая подсчитывает количество указателей, ссылающихся на объект, чтобы определить, можно ли его освободить.
  
  
• 00:40:00 В этом разделе спикер представляет концепцию подсчета ссылок как схемы сборки мусора и объясняет, как работает алгоритм подсчета ссылок. Однако указывается ограничение алгоритма, при котором циклы в эталонном графе не могут быть собраны. Затем докладчик обсуждает использование сильных и слабых указателей в некоторых языках программирования, чтобы обойти это ограничение. Наконец, выступающий анонсирует две другие схемы сборки мусора, «отметить и очистить» и «остановить и скопировать», которые позволяют избежать ограничения подсчета ссылок при работе с циклами в графе ссылок.
  
  
• 00:45:00 В этом разделе спикер обсуждает использование алгоритма поиска в ширину для поиска всех живых объектов в памяти. Массив с двумя указателями используется для представления очереди FIFO для поиска, и алгоритм отмечает каждый активный объект, доступный из корней. После завершения поиска непомеченные объекты доступны для сборки мусора. Процедура пометки и очистки включает два этапа: помеченный этап, который включает алгоритм поиска в ширину, и этап сканирования, который включает сканирование памяти для освобождения немаркированных объектов. Однако у этой схемы есть ограничения, такие как необходимость сканирования всей памяти и накладные расходы, связанные с просмотром объектов, на которые нет ссылок.
  
  
• 00:50:00 В этом разделе видео представляет процедуру сборки мусора "остановить и скопировать", которая имеет дело с фрагментацией. Эта процедура аналогична алгоритму маркировки и очистки, но использует другой подход, чтобы гарантировать непрерывность живых объектов в памяти. Процедура использует два отдельных пространства памяти — пространство from и пространство to — и выделяет и освобождает объекты из пространства from до тех пор, пока оно не заполнится. Затем запускается алгоритм сборки мусора, и два пространства используются в качестве очереди для поиска в ширину для идентификации живых объектов, которые будут размещены в памяти непрерывно в двух пространствах. Однако использование этого алгоритма может привести к возможной проблеме с корректностью, когда указатели, указывающие на объекты в пространстве from, могут больше не быть правильными. Чтобы решить эту проблему, процедура сохраняет указатель пересылки в соответствующем объекте в пространстве from и обновляет все указатели, следуя этим указателям пересылки при удалении объекта из очереди при поиске в ширину.
  
  
• 00:55:00 В этом разделе спикер обсуждает алгоритм остановки и копирования сборки мусора, его временную сложность и то, как он справляется с внешней фрагментацией. Алгоритм остановки и копирования включает в себя копирование объектов из пространства from в пространство to и последующее обновление указателей этих объектов в пространстве to. Этот алгоритм является линейным во времени и пространстве, что делает его более эффективным и действенным способом сборки мусора. Когда пространство from заполняется, пользователь может запросить новое пространство кучи и удвоить размер пространства from. Объем виртуальной памяти, требуемый этой схемой, постоянно оптимален, и этот алгоритм устраняет внешнюю фрагментацию.
  
  
• 01:00:00 В этом разделе спикер обсуждает другие темы, связанные с динамическим выделением памяти, такие как система Buddy для объединения, варианты процедуры маркировки и очистки, оптимизации для повышения производительности, сборка мусора на основе поколений, сборка мусора в реальном времени. , многопоточное выделение памяти и параллельная сборка мусора. Генерационный сбор мусора основан на идее, что многие объекты недолговечны, поэтому большую часть времени сканируются только более молодые объекты. Сборка мусора в реальном времени работает в фоновом режиме во время работы программы, но может привести к проблемам с корректностью, если граф объектов и указателей меняется. Многопоточное выделение памяти и параллельная сборка мусора имеют несколько запущенных потоков, что делает алгоритмы более сложными для борьбы с гонками и другими проблемами корректности. Докладчик также резюмирует различные типы распределения памяти, включая стек и кучу, и различные способы сборки мусора, такие как подсчет ссылок, пометка и очистка и остановка и копирование.
  
  
• 01:05:00 В этом разделе преподаватель упомянул, что они углубятся в схемы распределения памяти и что у студентов будет возможность опробовать некоторые из них в предстоящем домашнем задании. Затем инструктор закончил лекцию и предоставил слово для дальнейших вопросов.

[MetaQuotes]

Лекция 12. Параллельное выделение памяти

Лекция 12. Параллельное выделение памяти

В видео обсуждаются различные стратегии выделения памяти и их компромиссы. Объясняется использование malloc и выровненного распределения, а также важность правильного освобождения памяти с помощью free. Также рассматривается использование Mmap для выделения виртуальной памяти, а также вопросы внешней фрагментации и низкой производительности. Исследуется концепция стеков в программировании на C и C++ с упором на подход стека кактусов на основе кучи для выделения кадров стека, который может привести к лучшим доказательствам с ограниченным пространством и верхним границам. Также обсуждается использование пула линейных стеков, а также важность оптимизации для небольших блоков для минимизации фрагментации. Видео завершается обсуждением глобальных и локальных подходов к куче и связанных с ними потенциальных проблем, а также таких подходов, как списки свободных бинов и периодическая перебалансировка памяти для решения этих проблем.

В видео также обсуждаются решения для параллельного выделения памяти и в качестве решения представлен распределитель запасов. Распределитель запасов использует комбинацию локальных и глобальных куч и больших суперблоков, которые можно перемещать между кучами, чтобы уменьшить ложное совместное использование, улучшить масштабируемость и уменьшить внешнюю фрагментацию. Максимальное хранилище, выделенное в глобальной куче, не превышает максимального хранилища, выделенного в локальных кучах, а занимаемая площадь ограничивается сверху размером пользовательской области плюс выделенное, но неиспользуемое хранилище в локальных кучах. В видео также кратко обсуждаются другие распределители, такие как Je malloc и Super malloc, а результаты тестов показывают, что Super malloc работает лучше, чем Je malloc и Hoard. Обсуждение завершается ссылкой на онлайн-слайды для получения подробной информации о сборке мусора.

• 00:00:00 В этом разделе лектор рассматривает примитивы выделения памяти, включая malloc и выровненное выделение. Выровненное распределение можно использовать для выравнивания памяти по строкам кэша, чтобы для доступа к объекту в строке кэша требовался только один доступ к кэшу, что снижает количество промахов кэша. Лектор также обсуждает важность правильного освобождения памяти с помощью функции free и предотвращения утечек памяти и двойного освобождения. Наконец, лектор представляет системный вызов Mmap, который можно использовать для выделения виртуальной памяти без резервного файла.
  
  
• 00:05:00 В этом разделе спикер объясняет процесс выделения памяти с помощью карты M, которая представляет собой системный вызов, который находит непрерывную неиспользуемую область в адресном пространстве приложения, достаточно большую, чтобы вместить запрошенный объем памяти, и обновляет таблица страниц, содержащая запись для выделенных страниц. В отличие от malloc, который является библиотечным вызовом и частью кода управления кучей библиотеки C, M map не сразу выделяет физическую память для запрошенной памяти, а заполняет таблицу страниц записями, указывающими на специальную нулевую страницу, которая изменяется и транслируется в физическую память только тогда, когда пользователь впервые записывает в нее. Более того, M map отвечает за получение памяти от операционной системы, а malloc отвечает за повторное использование ранее выделенной памяти для уменьшения фрагментации и улучшения временной локальности.
  
  
• 00:10:00 В этом разделе видео обсуждаются различия между использованием MMAP и MALLOC для выделения хранилища, подчеркивая, что MMAP является относительно тяжелым и выделяет целые страницы даже для небольших выделений, что приводит к внешней фрагментации и снижению производительности. В видео также рассматривается процесс преобразования адресов, когда виртуальный адрес используется для доступа к памяти, а аппаратное обеспечение ищет соответствующий физический адрес в таблице страниц. Видео объясняет, как работают TLB, кэшируя недавние поиски в таблице страниц, и отмечает, что программы с пространственной или временной локализацией будут иметь много недавних обращений, хранящихся в TLB, что приводит к более высокой производительности.
  
  
• 00:15:00 В этом разделе спикер обсуждает, как работает трансляция адресов на современных машинах, а также углубляется в концепцию стеков в программировании на C и C++. Стеки используются для отслеживания вызовов функций и локальных переменных и следования линейному порядку. Докладчик подчеркивает одно правило указателей в традиционных линейных стеках: родитель может передавать указатели на свои переменные стека своим дочерним элементам, но не наоборот, чтобы избежать перезаписи переменных. Спикер также предлагает варианты, такие как выделение памяти в куче или в родительском стеке, для передачи памяти из дочерней функции обратно в родительскую.
  
  
• 00:20:00 правильное параллельное выделение кучи, потенциальная проблема с использованием стека кактусов на основе кучи — это фрагментация памяти, когда может не хватить непрерывной памяти для будущих распределений, что приводит к напрасной трате места и потенциальному исчерпанию память или сбой программы. Хотя ранние системы для параллельного программирования использовали эту стратегию, важно оптимизировать код, чтобы свести к минимуму влияние на производительность и учесть последствия фрагментации памяти.
  
  
• 00:25:00 В этом разделе видео обсуждается использование стека кактусов на основе кучи для выделения кадров стека без ограничения верхней границы максимальной глубины. Однако функциональная совместимость является проблемой при попытке использовать традиционный код линейного стека с этим стеком кактусов на основе кучи. Это можно исправить с помощью подхода, называемого отображением локальной памяти потока, но этот подход требует внесения изменений в операционную систему. Несмотря на это, подход к кактусовому стеку на основе кучи по-прежнему хорош на практике и может использоваться для доказательства ограниченности пространства программы Silk, которая его использует. Это ограничение пространства показывает, что пространство стека выполнения рабочего процесса P с использованием стека cactus на основе кучи ограничено сверху значением P, умноженным на s1, где s1 — это пространство стека, необходимое для последовательного выполнения программы Silk. Это хорошая особенность подхода стека кактусов на основе кучи.
  
  
• 00:30:00 В этом разделе анализируется код умножения матриц по принципу «разделяй и властвуй», чтобы понять, как его можно применить к теореме о компромиссе между пространством и временем. Код делает восемь рекурсивных вызовов, каждый из которых имеет размер N/2, и перед каждым вызовом он выполняет malloc для получения временного пространства порядка N в квадрате, которое затем освобождается непосредственно перед возвратом из функции. Так как распределение следует дисциплине стека, даже при выделении вне кучи пространство, ограниченное предыдущим слайдом, может использоваться для верхней границы рабочего пространства P. Работа равна N в кубе, а размах — порядка логарифма в квадрате N. Повторяемость для пространства равна s от N/2 + тета от N в квадрате, что дает N в квадрате. Таким образом, свойство занятых листьев и теорема об ограничении пространства показывают, что на P процессорах пространство ограничено числом P, умноженным на N в квадрате.
  
  
• 00:35:00 В этом разделе спикер рассказывает аудитории, как доказать более сильную пространственную границу для алгоритма, обсуждавшегося в предыдущем разделе. Проанализировав структуру алгоритма и сосредоточившись на максимально возможном ветвлении в верхней части дерева рекурсии, докладчик может продемонстрировать пространственную границу P с точностью до одной трети, умноженной на N в квадрате, что лучше, чем предыдущие верхние границы. . Докладчик отмечает, что анализ структуры алгоритма может привести к более сильным доказательствам, ограниченным пространством, чем простое применение общей теоремы. Раздел завершается обсуждением того, как параллельные функции не могут взаимодействовать с устаревшими и сторонними последовательными двоичными файлами.
  
  
• 00:40:00 В этом разделе спикер обсуждает использование пула линейных стеков при распределении памяти, которое можно использовать для поддержки пула стеков для устаревшего кода. Количество стеков в пуле должно быть постоянным, умноженным на количество процессоров, чтобы сохранить ограниченное пространство. Однако эта стратегия может повлиять на временные рамки алгоритма кражи работы, потому что рабочий может не иметь возможности украсть, если больше нет доступных стеков. Затем докладчик рассказывает об основных свойствах распределителей памяти в куче, в том числе о скорости распределителя и занимаемой пользователем площади, подчеркивая важность оптимизации для небольших блоков из-за потенциальной фрагментации и накладных расходов при распределении. Фрагментация определяется как площадь, занимаемая распределителем, деленная на площадь, занимаемая пользователем.
  
  
• 00:45:00 В этом разделе видео спикер обсуждает, как максимально приблизить выделенный след к пользовательскому, чтобы минимизировать их соотношение. Одним из решений является использование так называемого M-совета, который сообщает операционной системе, что определенная страница памяти больше не нужна и должна храниться в виртуальной памяти. Докладчик также упоминает теорему из предыдущей лекции о том, что фрагментация для списков свободных ячеек представляет собой логарифмический порядок по основанию два от U, где U — общий объем выделенной памяти, и объясняет различия между накладными расходами пространства, внутренней фрагментацией и внешней фрагментацией. Наконец, докладчик отмечает, что современные 64-битные процессоры предоставляют от 2 до 48 байт виртуального адресного пространства, что достаточно для большинства программ, но все же больше, чем физическая память на типичной машине.
  
  
• 00:50:00 В этом разделе видео рассматривается стратегия параллельного выделения кучи с использованием глобальной кучи с защитой от мьютексов, как работает распределитель C++ по умолчанию. Минус этой стратегии в том, что она не требует дополнительного места по сравнению с последовательным распределителем. Однако потенциальная проблема с этим подходом заключается в снижении производительности, поскольку получение блокировки для каждого выделения и освобождения происходит медленно и ухудшается с увеличением числа процессоров. Конкуренция за блокировку является основной причиной плохой масштабируемости, которая более проблематична для небольших выделений из-за более высокой частоты запросов, а для больших выделений блоков требуется больше работы.
  
  
• 00:55:00 В этом разделе видео обсуждается потенциальная проблема с использованием подхода с локальной кучей, заключающаяся в том, что это может привести к дрейфу памяти и неограниченному увеличению размера. По сути, если вы выделяете всю свою память в одном потоке, но освобождаете ее в другом, в системе может оставаться неиспользуемая память, которую распределитель не может использовать повторно. В результате ваша программа, работающая на нескольких процессорах, может в конечном итоге исчерпать память, но этого не произойдет, если она работает только на одном ядре. В видео предлагается использовать подход со списком свободных ячеек для решения этой проблемы, который включает в себя установку указателей в структуре данных списка свободных ячеек, чтобы освобождаемый блок мог появиться в одном из связанных списков. Другая стратегия заключается в периодической перебалансировке памяти, но обсуждается и более простой подход.
  
  
• 01:00:00 В этом разделе видео обсуждается, как изменить распределитель памяти, чтобы добиться желаемого поведения, когда каждый поток обращается к своей собственной куче без необходимости в глобальной куче. Один из подходов состоит в том, чтобы пометить каждый объект владельцем и вернуть его в кучу владельца после его освобождения. Таким образом, локальные объекты получают быстрое выделение и освобождение, в то время как удаленные объекты требуют некоторой синхронизации, но не такой сильной, как с глобальной кучей. Максимальный объем памяти, который может быть выделен, ограничен X, объемом, используемым последовательной программой, а коэффициент расширения ограничен сверху P, количеством куч. Этот подход также устойчив к ложному совместному использованию, когда несколько процессоров обращаются к разным участкам памяти, но к одной и той же строке кэша.
  
  
• 01:05:00 В этом разделе спикер обсуждает, как параллельное выделение кучи может привести к ложному совместному использованию, и в качестве решения представляет распределитель памяти. Распределитель запасов использует комбинацию локальных и глобальных куч, организуя память в большие суперблоки, которые можно перемещать между кучами. Этот подход является быстрым, масштабируемым и устойчивым к ложному совместному использованию. Когда выделение сделано, распределитель проверяет наличие свободного объекта в локальной куче и получает его, если он существует. Если нет, он отправляется в глобальную кучу, чтобы получить больше памяти.
  
  
• 01:10:00 В этом разделе спикер объясняет, как аллокатор Horde уменьшает внешнюю фрагментацию, выделяя свободный объект из самого полного неполного суперблока, чтобы уплотнить движение суперблоков. Если объект не найден в локальной куче, он проверяет глобальную кучу и, если глобальная куча пуста, вызывает из ОС новый суперблок. Распределитель Horde поддерживает инвариант, когда куча используется не более чем наполовину, и если он обнаруживает, что куча используется недостаточно, он перемещает полупустой суперблок в глобальную кучу. Затем выступающий представляет лемму, утверждающую, что максимальный объем памяти, выделенный в глобальной куче, не превышает максимальный объем памяти, выделенный в локальных кучах. Наконец, спикер доказывает теорему о том, что объем памяти распределителя Horde ограничен сверху порядком u плюс SP, где u — объем пользователя для программы, а SP — выделенное, но неиспользуемое хранилище в локальных кучах. Затем рассчитывается раздутие как один плюс SP порядка, деленный на u.
  
  
• 01:15:00 В этом разделе спикер обсуждает различные распределители, включая Je malloc и Super malloc. Je malloc имеет отдельные глобальные блокировки для разных размеров распределения и освобождает пустые страницы, используя рекомендации em, что делает его устойчивым к различным трассировкам распределения. С другой стороны, Super malloc имеет очень мало строк кода и развивается очень быстро. Спикер делится результатами тестов, в которых Super malloc работает лучше, чем J malloc, который работает лучше, чем Horde, в то время как аллокатор по умолчанию имеет низкую производительность. Обсуждение также распространяется на сбор мусора, однако спикер откладывает подробности этого до онлайн-слайдов.

[MetaQuotes]

Лекция 13. Система Cilk Runtime

Лекция 13. Система Cilk Runtime

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

Система Cilk Runtime System использует установленный протокол перехода и длинный переход для обработки кражи вычислений из исполнительных колод процессов-жертв. Абстракция Cactus Stack позволяет процессу-вору иметь собственный стек вызовов, чтобы предотвратить повреждение стеков жертвы. Протокол синхронизации системы использует дерево вычислений и стек Cactus, чтобы обеспечить синхронизацию только между вложенными вычислениями внутри функции. Полное дерево кадров поддерживает отношения родитель-потомок между вычислениями с незавершенными подвычислениями, чтобы упростить процесс синхронизации. Кроме того, система выполнения оптимизирует распространенный случай, когда текущая функция не имеет невыполненных дочерних вычислений и все рабочие процессы заняты. Другие поддерживаемые функции включают исключения C++, гиперобъекты редукторов и родословные.

• 00:00:00 В этом разделе Тиби рассказывает о системе времени выполнения Cilk, которая отвечает за планирование и вычисления балансировки нагрузки на параллельных процессорах. Система среды выполнения использует рандомизированный планировщик кражи работы для сопоставления вычислений с процессорами во время выполнения, обеспечивая эффективное выполнение. Тиби отмечает, что исполняющая система Cilk представляет собой сложную часть программного обеспечения, но ее основное волшебство реализуется за счет совместной работы компилятора Cilk и исполняющей библиотеки. Кроме того, он показывает псевдокод простой программы Cilk после компиляции, что подчеркивает сложный процесс, лежащий в основе системы времени выполнения Cilk.
  
  
• 00:05:00 В этом разделе спикер объясняет функциональные возможности, необходимые для системы времени выполнения Cilk, а также вопросы производительности. Он использует пример распараллеленной подпрограммы Фибоначчи, чтобы проиллюстрировать, как программа Cilk выполняет вычислительный dag, который динамически развертывается по мере выполнения программы на одном процессоре. Однако, когда встречается оператор порождения шелка, создается новый кадр для вымысла 3, и для параллельного выполнения доступна другая цепочка. Затем процессор начинает выполнять fib of 3, как если бы это был обычный вызов функции. Процесс повторяется, когда указатель инструкции возвращается к началу подпрограммы fib.
  
  
• 00:10:00 В этом разделе мы видим, как несколько процессоров параллельно выполняют подпрограмму fib с помощью системы времени выполнения Cilk. Каждый процессор переходит в середину выполняемой функции и начинает ее выполнение, несмотря на наличие независимых регистров, что вызывает вопрос о том, как система Silk позволяет процессорам начинать выполнение с середины выполняемой функции. Кроме того, синхронизация между процессорами усложняется при достижении оператора синхронизации, который не может выполняться дальше точки, поскольку определенные процессоры все еще ожидают завершения вычислений, что требует мелкозернистой синхронизации в рамках вложенного шаблона.
  
  
• 00:15:00 В этом разделе спикер обсуждает вопросы реализации системы времени выполнения Cilk. Они упоминают три основных соображения: возможность выполнения программы одним исполнителем, возможность перейти в середину выполнения функций и продолжить работу с того места, где остановились другие процессоры, и синхронизация. Кроме того, в Silk есть понятие стека кактусов, которое необходимо правильно реализовать, чтобы сделать все представления стека доступными и согласованными. Наконец, система должна допускать кражу работы, позволяя процессорам воровать кадры друг у друга.
  
  
• 00:20:00 В этом разделе спикер обсуждает функциональность, необходимую для Cilk Runtime System, которая включает в себя последовательное выполнение, воров, прыгающих в середину запущенных функций, синхронизацию для синхронизации вложенным мелкозернистым способом, стек кактусов для все рабочие, чтобы видеть, и иметь дело со смесями порожденных кадров и вызванных кадров, которые могут быть доступны, когда они воруют вычисления. Затем раздел переходит к рассмотрению производительности системы, где нам нужен достаточный параллелизм, бесконечность T1 над T должна быть намного больше, чем P, и мы хотим линейного ускорения при увеличении числа процессоров для запуска программы. В этом разделе также рассматривается ожидаемое время работы TCP на процессорах P, которое пропорционально работе вычислений, деленной на количество процессоров, плюс что-то порядка диапазона вычислений.
  
  
• 00:25:00 В этом разделе мы узнаем о системе Cilk Runtime System и ее цели поддерживать высокую эффективность работы в программах с достаточным параллелизмом. Система Silk Runtime System соблюдает принцип работы в первую очередь, оптимизируя последовательное выполнение программы даже за счет некоторых дополнительных затрат на сталь. Системная библиотека времени выполнения обрабатывает проблемы с параллельным выполнением и обрабатывает более медленные пути выполнения при возникновении стали. Рабочий процесс поддерживает отдельную структуру данных колоды, которая содержит указатели на кадры стека и использует указатели начала и конца. Кадры, доступные для кражи, имеют дополнительную локальную структуру, которая содержит необходимую информацию для кражи, когда колода является внешней по отношению к стеку вызовов.
  
  
• 00:30:00 В этом разделе мы узнаем об устройстве Cilk Runtime System и ее основных структурах данных. Система генерирует вспомогательную функцию порождения для каждого вычисления, которая поддерживает рабочую структуру и структуру кадра стека Silk для каждого экземпляра порождающей функции и вспомогательной функции порождения соответственно. Кадр стека Silk RTS содержит такие поля, как буфер и целое число флагов для суммирования состояния фрейма стека Silk, а также указатель на родительский фрейм стека Silk в стеке вызовов. Рабочая структура поддерживает колоду и указатель на текущий кадр стека Silk RTS. Эти структуры данных являются основой системы времени выполнения Cilk, над которой работает система времени выполнения Intel so+.
  
  
• 00:35:00 В этом разделе в видео исследуется код функции порождения "foo" и вспомогательной функции порождения. Код для «foo» включает в себя вызов для инициализации фрейма стека, настроенный для порождения с помощью процедуры set jump, вызов вспомогательной функции порождения «панель спавна», условный блок кода для приемника в Silk RTS, и вызывает всплывающие и листовые фреймы для очистки. Код помощника порождения включает в себя вызов для инициализации кадра стека и вызов для отсоединения Silk RTS с дополнительными функциями очистки структуры стека. Процедура настройки описывается как функция, которая позволяет ворам украсть продолжение функции, взяв в качестве аргумента буфер для хранения необходимой информации для возобновления расположения функции.
  
  
• 00:40:00 В этом разделе спикер обсуждает, как ограничить набор регистров и сохранить их в заданный набор для вызова функции. Ответственность за сохранение регистров ложится на функцию, но указатель команд и указатели стека сохраняются в буфере. Далее в разделе обсуждается вспомогательная функция порождения и то, как она обновляет рабочие структуры и текущие кадры стека. Наконец, в этом разделе объясняется, как быстрая подпрограмма ввода кадра устанавливает родительский указатель в стеке вызовов и обновляет текущий кадр стека рабочего процесса, чтобы он указывал на дно.
  
  
• 00:45:00 В этом разделе расшифровка видео на YouTube под названием «Система времени выполнения Cilk» объясняет, как функция отсоединения Silk RTS позволяет украсть вычисления, где после того, как шелковое художественное исполнение завершено, вор может прийти и украсть продолжение шелковой икры. Всплывающий кадр отвечает за очистку структуры кадра стека и обновление текущего кадра стека, чтобы он указывал на родителя. Этот вызов функции может возвращаться или не возвращаться, и какой из этих двух случаев важнее для оптимизации системы выполнения, — это случай успеха, основанный на двух принципах работы.
  
  
• 00:50:00 В этом разделе спикер обсуждает оптимизацию исполняющей системы Cilk при выполнении рабочих операций в первом случае, когда предполагается, что рабочие выполняют обычное последовательное выполнение. Они также объясняют, как работает воровство рабочих, когда вор нацеливается на верхнюю часть колоды жертвы, удаляет предмет из очереди и обновляет заголовок колоды и текущий указатель фрейма стека. Результат порожденной функции возвращается в кадр родительского стека в исходном коде SIL.
  
  
• 00:55:00 В этом разделе спикер объясняет подход Cilk Runtime System к обработке параллельного доступа с участием нескольких процессоров с использованием протокола, называемого протоколом THC. Протокол включает в себя два набора протоколов: один для работника, выполняющего работу, и один для вора. Протокол рабочего оптимизируется за счет попытки вытолкнуть что-нибудь из нижней части колоды, и только в случае неудачи он получает блокировку на колоде, в то время как вор всегда захватывает замок перед выполнением каких-либо операций с колодой. Затем вор волшебным образом возобновляет украденное продолжение, вызывая функцию длинного перехода, передавая буфер кадра стека, полученный из функции set jump, и устанавливая состояние его регистра в состояние украденного продолжения.
  
  
• 01:00:00 В этом разделе спикер обсуждает взаимодействие между вызовами set jump и long jump в системе времени выполнения Cilk. Они объясняют, как, когда вызывается процедура длинного перехода, она эффективно возвращается из установленного перехода во второй раз, на этот раз с другим значением, указанным во втором аргументе. Используя соответствующий буфер и второй аргумент, вор может выполнить длинный переход, чтобы пропустить определенное вычисление в коде жертвы. Докладчик отмечает, что можно статически вычислить расстояние, необходимое для перехода через вызов, и использовать другой подход, но протокол set jump и long jump служит более гибким методом для системы времени выполнения Cilk. В целом спикер выделяет различные методы, доступные вору для кражи вычислений из колоды жертвы с помощью Cilk.
  
  
• 01:05:00 В этом разделе обсуждается необходимость абстракции стека cactus для системы времени выполнения Cilk. Объясняется, что использование стека жертвы может привести к повреждению стека жертвы и вызвать проблемы с поддержанием согласованности между всеми воркерами. Поэтому для вора нужен отдельный стек вызовов. Реализация стека кактусов предполагает, что вор крадет продолжение и устанавливает указатель стека на свой собственный стек, сохраняя при этом возможность доступа к состоянию функции в стеке жертвы через смещения от RB p.
  
  
• 01:10:00 В этом разделе спикер объясняет, как система времени выполнения SIL обрабатывает синхронизацию вычислений на разных процессорах. Система использует стек кактуса и дерево вычислений, чтобы гарантировать, что синхронизация происходит только между вложенными подвычислениями в функции, а не в программе в целом. Когда рабочий процесс достигает оператора шелковой синхронизации до того, как все подвычисления возвращаются, он становится вором и продолжает работать с кадром стека украденного вычисления. Это позволяет системе избежать ненужной траты рабочих ресурсов и обеспечить правильную синхронизацию вложенных вычислений. Система специально указывает компилятору не использовать оптимизацию, которая может конфликтовать с этим подходом.
  
  
• 01:15:00 В этом разделе система Cilk Runtime System описывается как поддерживающая дерево состояний, называемое полными кадрами, которое отслеживает, какие вычисления ожидают завершения других вычислений. Эта система использует полное дерево фреймов для отслеживания большого количества информации для параллельного выполнения, включая указатели на родительские фреймы, возможно, на дочерние фреймы и то, как незавершенные подвычисления связаны друг с другом. Когда рабочий процесс сталкивается с синхронизацией, если у него есть незавершенные дочерние вычисления, он не может синхронизироваться и должен приостановить свой полный кадр, пока он не станет вором, чтобы украсть больше работы. Эта система позволяет программе иметь достаточный параллелизм и упрощает протоколы синхронизации.
  
  
• 01:20:00 В этом разделе спикер обсуждает, как Cilk Runtime System оптимизирует распространенный случай, когда у исполняемой функции нет невыполненных дочерних элементов, а все работники в системе заняты своими собственными задачами. Система среды выполнения использует биты из поля флага связанного кадра стека, чтобы оценить, необходима ли синхронизация для шелковой синхронизации. Докладчик также упомянул несколько других функций, поддерживаемых системой выполнения, включая исключения C++, гиперобъекты-редюсеры и родословные.

[MetaQuotes]

Лекция 14. Кэширование и кэш-эффективные алгоритмы

Лекция 14. Кэширование и кэш-эффективные алгоритмы

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

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

• 00:00:00 В этом разделе, посвященном кэшированию и алгоритмам эффективного использования кэша, инструктор обсуждает иерархию кэша современных машин, которая включает частные кэши данных и инструкций L1 для каждого процессора, частный кэш L2 и кэш последнего уровня, который распределяется между всеми процессорами. Размеры этих кэшей увеличиваются по мере продвижения вверх по иерархии памяти, при этом DRAM является самым медленным и самым большим. Ассоциативность кэша и задержка также увеличиваются по мере продвижения вверх по иерархии памяти, при этом кэш L1 является самым быстрым и наиболее ассоциативным. Преподаватель также упоминает о важности протоколов когерентности кэша для обеспечения согласованности доступа к адресам памяти для параллельной обработки. Понимание того, как использовать локальность в программах, может помочь эффективно использовать более быстрые кэши памяти.
  
  
• 00:05:00 В этом разделе обсуждаются различия между полностью ассоциативным кэшем и кэшем с прямым отображением. Полностью ассоциативный кеш требует поиска всего кеша, чтобы найти блок, который может быть медленным и неэффективным, поскольку поиск блока может потребовать доступа к нескольким строкам. Кэш с прямым отображением, с другой стороны, имеет только одно возможное местоположение для каждого блока, что делает доступ к блокам намного быстрее и с меньшим количеством конфликтов. Три компонента адресного пространства: смещение, набор и тег также объясняются при разделении адреса виртуальной памяти для определения местоположения блока кэша. Тег определяет, какому блоку памяти соответствует блок кеша, а набор определяет, в какую позицию в кеше помещается блок, с общим адресным пространством W бит.
  
  
• 00:10:00 В этом разделе видео обсуждаются преимущества и недостатки кешей с прямым отображением, которые работают быстро, потому что нужно искать только в одном месте в кеше, но склонны к конфликтным промахам, когда блоки кеша продолжают вытеснять друг друга, снижение производительности. Затем в видео представлены наборы ассоциативных кэшей, гибридное решение, в котором каждый набор содержит несколько строк, что позволяет использовать более одного возможного местоположения в кэше для каждого блока кэша. В видео также упоминается таксономия различных типов промахов кеша, включая холодные промахи, которые происходят при первом доступе к блоку кеша и их нельзя избежать.
  
  
• 00:15:00 В этом разделе видео обсуждаются различные типы промахов кеша, в том числе промахи емкости, промахи конфликтов и промахи совместного использования. Промахи емкости происходят, когда кеш заполнен и не может вместить все блоки кеша, к которым необходимо получить доступ, в то время как пропуски конфликтов происходят в ассоциативных кешах наборов, когда слишком много блоков из одного и того же набора сопоставляются с кешем. Наконец, промахи при совместном использовании происходят в параллельном контексте, когда несколько процессоров обращаются к одной и той же строке кэша, и по крайней мере один из них выполняет запись в нее. Видео также представляет собой пример плохого случая промахов конфликта при доступе к подматрице в более крупной матрице, хранящейся в основном порядке строк.
  
  
• 00:20:00 В этом разделе спикер обсуждает кэширование и алгоритмы эффективного кэширования. Они используют пример доступа к подматрице в более крупной матрице и того, как могут возникать конфликтные промахи, когда кеш является только 4-канальным ассоциативным. Докладчик предлагает добавить постоянное количество пробелов в конец каждой строки в матрице, чтобы каждая строка была длиннее 2^15 байт, что может помочь уменьшить конфликтные промахи.
  
  
• 00:25:00 В этом разделе спикер обсуждает идеальную модель кэша, которая используется для анализа производительности кэша алгоритмов. Эта модель предполагает двухуровневую иерархию кэша, полностью ассоциативный кэш и оптимальную политику замены Нишанта. Докладчик объясняет, что важны два показателя производительности: порядок N и количество промахов в кэше, где идеальным сценарием является небольшое количество промахов в кэше без увеличения объема работы по сравнению с традиционным стандартным алгоритмом. Также упоминается лемма LRU, которая была доказана в 1985 году и утверждает, что алгоритм, который подвергается Q промахов кэша в идеальном кэше размера M, будет нести 2Q промахов кэша в полностью ассоциативном кэше размером 2M, который использует политику LRU.
  
  
• 00:30:00 В этом разделе спикер знакомит с концепцией алгоритмов, эффективных с кэшированием, и с тем, как они могут повысить производительность программы за счет сведения к минимуму количества промахов кэша. Он объясняет политику замены наименее недавно использованного (LRU), которая гласит, что полностью ассоциативный кеш, в два раза превышающий размер идеального кеша с использованием LRU, вызовет не более чем удвоенное количество промахов кеша. Это позволяет упростить анализ промахов кэша при выполнении асимптотического анализа. Докладчик также представляет лемму о промахах в кеше, утверждая, что если программа читает набор сегментов данных, размер которых меньше одной трети размера кеша и средний размер которых равен по крайней мере размеру строки кеша, то количество число промахов кэша для чтения их всех не превышает трехкратного общего размера сегментов, деленного на размер строки кэша.
  
  
• 00:35:00 В этом разделе видео обсуждаются два предположения, связанные с кэшированием — лемма промаха кеша и предположение о длинном кеше. Лемма о промахах в кеше утверждает, что если средняя длина сегментов данных больше, чем размер блока кеша, это увеличивает количество промахов в кеше только на постоянный коэффициент. Предположение о высоком кеше предполагает, что высота кеша превышает его ширину, и на практике это обычно выполняется. Видео также объясняет лемму о кэшировании подматриц, в которой обсуждается проблема с короткими кэшами при подгонке подматриц к строкам кэша и почему предположение о длинном кэше полезно при решении этой проблемы.
  
  
• 00:40:00 В этом разделе спикер обсуждает кэширование и алгоритмы эффективного кэширования. Они анализируют количество промахов из кэша, возникающих при чтении квадратной подматрицы в кэш, и используют лемму промахов в кэше, чтобы показать, что количество промахов в кэше, необходимое для чтения всех элементов матрицы в кэш, не превышает 3n^2/B. . Затем они анализируют количество промахов кеша, возникающих в стандартном алгоритме умножения кубической рабочей матрицы, предполагая, что матрица находится в основном порядке строк, и они удовлетворяют допущению о длинном кеше. Они рассматривают три случая и предполагают LRU для второго и третьего случаев, что в конечном итоге демонстрирует важность оптимизации кэша при разработке алгоритма.
  
  
• 00:45:00 В этом разделе спикер обсуждает кэширование и алгоритмы эффективного кэширования. Они анализируют два случая умножения матриц, когда n больше, чем M над B, и когда n меньше, чем C, умноженное на M над B. Они используют политику замены LRU и вычисляют количество промахов кэша, возникающих при доступе к матрице B. В первом В этом случае они обнаруживают, что им требуется тета из n кэш-промахов в кубе, что не дает никакой выгоды от наличия локальности в алгоритме. Во втором случае они могут использовать пространственную локальность и уменьшить количество промахов в кэше в B раз, в результате чего тета n умножается на B промахов в кэше, что является более эффективным.
  
  
• 00:50:00 В этом разделе видео спикер обсуждает кэширование и кэш-эффективные алгоритмы. Сначала они анализируют случай, когда вся матрица помещается в кэш, что приводит к общему количеству промахов в кэше, равному тета n в квадрате над B. Затем они обсуждают оптимизацию путем изменения порядка двух внутренних циклов, чтобы извлечь выгоду из пространственной локальности и уменьшить общее количество промахов кеша до тета n в кубе над B. Однако они отмечают, что можно добиться большего успеха, используя оптимизацию, называемую тайлингом, где шесть циклов for используются для перебора тайлов, а вычисления выполняются для каждого подпункта. -matrix, прежде чем перейти к следующему. Затем работа для подматрицы размера s на s возводится в куб s.
  
  
• 00:55:00 В этом разделе вводится и подробно обсуждается концепция мозаичного матричного умножения. Цель этого алгоритма — разместить подматрицы в кеше, чтобы все вычисления могли выполняться в кеше без промахов кеша. Анализируется количество промахов кеша, и обнаруживается, что количество промахов кеша равно n/s^3, умноженному на s^2/B, всего n^3/B * sqrt(M) промахов кеша. Это число очень важно для улучшения производительности кода матричного умножения. Однако с алгоритмом возникает проблема: он не переносим, так как сильно зависит от размера кеша машины, на которой он запущен. Кроме того, оптимизация многомерной настройки становится намного дороже, а код становится более беспорядочным при оптимизации для нескольких уровней кэша.
• 01:00:00 В этом разделе лекции рассматриваются алгоритмы кэширования и эффективного использования кэша. Докладчик обсуждает проблемы настройки параметров алгоритма кэширования и его оптимизации для конкретной машины. Они вводят алгоритм рекурсивного умножения матриц, в котором входные матрицы делятся на четыре подматрицы или квадранта. Для каждого квадранта выходной матрицы сумма двух матричных умножений происходит рекурсивно. Наконец, спикер анализирует работу этого алгоритма и приходит к выводу, что это более простая конструкция, которая при этом сохраняет хорошую производительность кэша.
  
  
• 01:05:00 В этом разделе спикер обсуждает кэширование и алгоритмы эффективного использования кэша, а также использует пример матричного умножения, чтобы объяснить разницу между анализом работы и кэш-промахами. Докладчик рисует дерево рекурсии, чтобы визуализировать проблему размера и ветвления подзадач, и отмечает, что количество уровней до листьев равно логарифмической основе 2 числа n. Количество листьев рассчитывается как восемь в логарифмическом основании 2 числа n, что равно n в кубе. Объем работы просто тэта-н-куб, а кэш-промахи анализируются с использованием другого базового случая, когда подматрица помещается в кэш-память, и используется тета-квадрат N по кэш-промахам. Докладчик подчеркивает, что количество уровней не просто равно логарифмическому основанию 2 от n, но также зависит от размера кэша, что приводит к различному количеству листьев, тэта n в кубе по m к трем половинам.
  
  
• 01:10:00 В этом разделе спикер объясняет, как анализировать количество промахов кэша в кэш-эффективном алгоритме на примере кода рекурсивного умножения матриц. Код не обращает внимания на кеш, то есть он не имеет никаких явных сведений о кешах и пассивно автоматически настраивается на конкретный размер кеша машины, на которой он работает. Докладчик также упомянул, что лучшие на сегодняшний день кэширующие забывающие коды работают с произвольными прямоугольными матрицами и выполняют двоичное разбиение вместо разбиения по восьми путям. Докладчик обсуждает параллельный контекст и объясняет, как анализировать количество промахов кэша в детерминированных вычислениях ячеек, которые выполняются на нескольких процессорах с частными кэшами.
  
  
• 01:15:00 В этом разделе спикер обсуждает кэширование и алгоритмы эффективного кэширования. Минимизируя промахи кэша в последовательной иллюзии, мы можем по существу свести к минимуму их при параллельном выполнении для алгоритмов с малым интервалом. Динамик обеспечивает ограничение кэш-промаха для параллельного рекурсивного алгоритма умножения матриц, который аналогичен последовательному выполнению. Цель состоит в том, чтобы разработать алгоритмы, которые имеют явное представление о кэше или не обращают внимания на кэш. Докладчик приводит примеры того и другого и упоминает, что в следующей лекции будет проведено дальнейшее обсуждение разработки алгоритма без учета кеша.

[MetaQuotes]

Лекция 15. Алгоритмы Cache-Oblivious

Лекция 15. Алгоритмы Cache-Oblivious

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

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

• 00:00:00 В этом разделе видео обсуждаются алгоритмы без учета кеша, которые представляют собой алгоритм, который автоматически настраивается на размер кеша на машине и обеспечивает хорошую эффективность кеша, при этом коду не нужно знать параметры кеша машина. В видео используется пример моделирования диффузии тепла с помощью дифференциальных уравнений, чтобы показать, как научные вычисления часто полагаются на дифференциальные уравнения для описания физических процессов, а затем должны написать эффективный код для моделирования процесса. Видео демонстрирует, как написать код на основе метода аппроксимации конечных разностей для моделирования одномерного уравнения теплопроводности.
  
  
• 00:05:00 В этом разделе спикер рассказывает, как написать код для уравнения моделирования, который позволяет выполнять аппроксимацию конечных разностей с использованием метода шаблона. В уравнении используются частные производные U по T и X, и докладчик показывает, как получить эти частные производные с помощью методов аппроксимации. Двухмерное пространство представлено с помощью матрицы со значениями X и T, представленными по горизонтали и по вертикали соответственно. Докладчик объясняет границы матрицы и вычисляет U, используя уравнение.
  
  
• 00:10:00 В этом разделе ведущий объясняет трафаретные вычисления — метод, широко используемый в научных вычислениях для различных целей. В этом методе каждая точка массива обновляется с использованием фиксированного шаблона, называемого трафаретом. Вычисление зависит от трех других значений, и это известно как трехточечная позиция. Хотя вычисления трафарета можно использовать для больших значений X, производительность может снизиться из-за кэширования, что приведет к промахам кэша. Более того, память, необходимая для хранения данных, может быть уменьшена за счет сохранения только двух строк, текущей и предыдущей, для обновления значений точек.
  
  
• 00:15:00 работает: на каждом временном шаге мы обновляем значения X только для определенной строки, используя значения из предыдущей строки. Таким образом, мы можем чередовать, какую строку мы обновляем и какую строку мы используем в качестве предыдущей строки, и нам нужно только сохранить одну дополнительную строку значений. Однако этот код не очень эффективен для кэширования, и мы можем сделать его более эффективным, используя тайлинг или алгоритмы забывания кэша. Идеальная модель кэша предполагает наличие полностью ассоциативного кэша с оптимальной политикой или политикой замены LRU и фиксирует пропуски емкости, но не конфликтные пропуски при последовательном выполнении. Тем не менее, он по-прежнему полезен для разработки эффективных алгоритмов, использующих временную и пространственную локальность.
  
  
• 00:20:00 В этом разделе спикер объясняет, как алгоритм без кэширования можно использовать для вычисления точек внутри трапециевидного пространства в 2D-матрице, не глядя за его пределы. Вычисление включает функцию ядра, которая принимает указатель на UT mod в X и возвращает значение W, равное 0, плюс значение альфа, умноженное на W, равное минус 1, минус 2, умноженное на W, равное 0, плюс W, равное 1. Поведение кэширования анализируется с учетом политики замены LRU, и количество промахов кеша равно Theta NT над B для каждой строки. Однако спикер отмечает, что с тайлингом можно добиться лучшей производительности, но продолжают обсуждение варианта без кэширования. Трапеция имеет верхнее основание в точке Т1 и нижнее основание в точке Т0. Алгоритм вычисляет все точки внутри трапеции, используя условия неравенства, которые включают T, t0, t1, X, x0, x1, DX0, DX1, где DX0 и DX1 равны -1, 0 или 1, представляющим наклоны.
  
  
• 00:25:00 В этом разделе спикер описывает подход «разделяй и властвуй» для алгоритма правила трапеции. Подход имеет базовый случай, когда высота трапеции равна 1, а цикл вычисляет все значения в зависимости от порядка вычисления. Алгоритм имеет два рекурсивных случая, а именно разрез по пространству и разрез по времени, которые зависят от ширины и высоты трапеции соответственно. Когда трапеция слишком широкая, применяется пространственный разрез там, где трапеция разрезается вертикально линией с отрицательным наклоном, проходящей через центр трапеции. Напротив, временной разрез применяется, когда трапеция слишком высока, и разрезается горизонтальной линией, проходящей через центр. Рекурсивный алгоритм выполняет два вызова, которые обходят левую и правую стороны трапеции, а также нижнюю и верхнюю часть соответственно в определенном порядке, чтобы предотвратить взаимозависимость между точками.
  
  
• 00:30:00 В этом разделе спикер обсуждает сложность кеша алгоритмов без кеша. Они анализируют подход с использованием рекурсивного дерева и обнаруживают, что алгоритм разделяется на две подзадачи на каждом уровне, пока не достигает базового случая, который представляет тета точек HW, где H — это тета W. Количество промахов кеша на лист — это тета W. над B, а число листьев равно Theta NT над HW. Внутренние узлы не вносят существенного вклада в сложность кэша. Сложность кэша обобщается более чем на одно измерение, и если d равно единице, это приводит к NT сверх МБ.
  
  
• 00:35:00 В этом разделе спикер объясняет разницу между циклическим кодом и трапециевидным кодом, который имеет гораздо лучшую сложность кэша за счет экономии коэффициента M, где M — количество строк кэша. Моделирование показывает, что трапециевидный код вызывает меньше промахов кэша по сравнению с циклическим кодом, благодаря чему вычисления завершаются намного быстрее. Однако спикер отмечает, что эта симуляция была только для одного измерения, и продолжает демонстрировать демонстрацию того, что происходит в двух измерениях.
  
  
• 00:40:00 В этом разделе ведущий демонстрирует моделирование в реальном времени диффузии тепла в двумерном пространстве, где цвета на экране соответствуют температурам. Докладчик сравнивает производительность циклического кода и трапециевидного кода и показывает, что, хотя трапециевидный код подвергается гораздо меньшему количеству промахов кэша, он лишь незначительно быстрее, чем циклический код. Предполагается, что это может быть связано с тем, что аппаратная предварительная выборка помогает коду зацикливания, поскольку его шаблон доступа является регулярным и легко предсказуемым.
  
  
• 00:45:00 В этом разделе спикер обсуждает взаимодействие кэширования и параллелизма. Они объясняют теорему, которая утверждает, что минимизация промахов кэша при последовательном выполнении может по существу минимизировать их при параллельном выполнении, предполагающем алгоритм с малым интервалом. Затем они демонстрируют, как трапециевидный алгоритм может работать параллельно, используя V-образный разрез, где две независимые трапеции выполняются параллельно, а затем выполняется серая трапеция. Они также упоминают перевернутый V-образный вырез, который используется для перевернутых трапеций.
  
  
• 00:50:00 В этом разделе докладчик обсуждает производительность кода с параллельным циклом и параллельного трапециевидного кода по сравнению с их последовательными аналогами. Параллельный зацикленный код достигает менее половины потенциального ускорения, несмотря на то, что потенциальный параллелизм выше, чем у трапециевидного кода. Это связано с тем, что в параллельном случае существует узкое место в пропускной способности памяти, что не позволяет предварительной выборке помочь коду параллельного цикла по сравнению с последовательным случаем, где пропускная способность памяти достаточна. Напротив, трапециевидный код обеспечивает почти линейное ускорение, что согласуется с тем фактом, что эффективность кэша играет гораздо большую роль при больших размерах входных данных, где кэш настолько мал по сравнению с размером входных данных.
  
  
• 00:55:00 В этом разделе выступающий обсуждает, как диагностировать узкое место в параллельном ускорении, и определяет несколько причин, которые могут его вызвать, например недостаточный параллелизм, накладные расходы планирования, недостаточная пропускная способность памяти и конкуренция. Они предлагают несколько способов диагностики этих проблем, включая использование Silk Scale для измерения параллелизма в коде и использование аппаратных счетчиков для измерения пропускной способности памяти. Однако диагностика разногласий особенно сложна, и выступающий советует рассмотреть первые три возможные причины, прежде чем оценивать, является ли разногласие проблемой. Наконец, спикер переходит к обсуждению вычисления трафарета.
  
  
• 01:00:00 В этом разделе докладчик обсуждает анализ сложности кеша при сортировке слиянием, сначала анализируя сложность слияния двух отсортированных входных массивов. Время на это пропорционально сумме размеров входных массивов. Количество промахов в кэше при слиянии n элементов равно тета n по B, где B — количество байтов в строке кэша. Сортировка слиянием имеет два рекурсивных вызова для входных данных вдвое меньшего размера и объединяет отсортированные выходные данные своих рекурсивных вызовов. Общая работа сортировки слиянием представляет собой тета n log n, которая анализируется с использованием метода рекурсивного дерева. Также обсуждается сложность кеша при сортировке слиянием, и показано, что количество промахов кеша пропорционально количеству блоков кеша, необходимых для хранения данных, которое равно тета n по B log M, где M — максимальный размер a. подблок может иметь.
  
  
• 01:05:00 В этом разделе спикер объясняет повторяемость сложности кеша при сортировке слиянием. Базовый случай возникает, когда размер проблемы помещается в кеш, что приводит к промахам кеша Θ (n / B). В противном случае алгоритм имеет два рекурсивных вызова размера n/2 и Θ(n/B) кэш-памяти для объединения результатов. Анализ включает количество уровней дерева рекурсии, которое является логарифмическим основанием 2 n / CM, где CM - константа. Количество промахов кеша на лист равно Θ(M/B * n/CM), что дает общее количество промахов кеша Θ(n/B * log (n/CM)), сохраняя множитель B в первом члене . Однако для задач большего размера мы экономим только коэффициент B по сравнению с работой, в то время как мы сохраняем коэффициент B log n для задач небольших размеров. Спикер спрашивает, есть ли лучшее решение, и ответ всегда положительный.
  
  
• 01:10:00 В этом разделе спикер объясняет, как использовать многостороннее слияние для объединения отсортированных подмассивов, и вводит идею турнирного дерева для определения минимального количества элементов подмассивов. Они также объясняют сложность работы и кэширования этого подхода, который используется в алгоритмах сортировки, не обращающих внимания на кэш. Сложность работы многостороннего слияния такая же, как у бинарной сортировки слиянием, а сложность кеша определяется количеством промахов кеша, необходимых для заполнения турнирного дерева и доступа к входным массивам, которые можно оптимизировать, если R меньше C*M/B для небольшой константы C.
  
  
• 01:15:00 В этом разделе докладчик обсуждает сложность кэша алгоритма многофакторной сортировки слиянием и сравнивает ее с алгоритмом бинарной сортировки слиянием. Алгоритм многофакторной сортировки слиянием включает в себя разделение задачи на подзадачи размера n/R и оплату n/B промахов кеша для их слияния. Число уровней дерева рекурсии равно логарифмической базе R, равной n/см, а размер листа равен сантиметрам. Спикер устанавливает R равным тета M/B, делая его как можно большим, и анализирует сложность кэша, которая оказывается равной тета n log n, деленному на B log M. По сравнению с бинарным алгоритмом сортировки слиянием, множественный Алгоритм сортировки слиянием сохраняет коэффициент log M в кэш-промахах. Однако алгоритм не игнорирует кеш, и значение R необходимо настраивать для конкретной машины, что может быть проблемой, если выполняются другие задания, конкурирующие за кеш.
  
  
• 01:20:00 В этом разделе докладчик обсуждает алгоритм воронкообразной сортировки, который представляет собой алгоритм сортировки без учета кеша, который может объединять K элементов в квадрате и K отсортированных списков. Показано, что стоимость этого слияния такая же, как и у алгоритма многофакторной сортировки слиянием, но алгоритм воронкообразной сортировки игнорирует кеш, и его граница оптимальна. Докладчик представляет картину того, как выглядит воронка K, и объясняет, что алгоритм рекурсивно построен с квадратным корнем из K воронок, которые подают элементы в буферы, которые, в свою очередь, передают элементы в окончательный выходной квадратный корень из K воронки, производя выход для воронки K. Докладчик также упоминает, что существует множество других алгоритмов и структур данных, не обращающих внимания на кеш, таких как b-деревья, упорядоченное обслуживание файлов и приоритетные очереди, и предлагает зрителям узнать о них больше в Интернете.

[MetaQuotes]

Лекция 16. Недетерминированное параллельное программирование

Лекция 16. Недетерминированное параллельное программирование

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

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

• 00:00:00 В этом разделе лектор знакомит с концепцией детерминизма в программировании и его отношением к параллельным вычислениям. Программа является детерминированной, если каждая ячейка памяти обновляется одной и той же последовательностью значений при каждом выполнении, и программа всегда ведет себя одинаково. Преимущество детерминированных программ в том, что они повторяемы, что упрощает их отладку. Лектор подчеркивает важность того, чтобы никогда не писать недетерминированные параллельные программы, поскольку они могут демонстрировать аномальное поведение, которое трудно отладить. Однако на практике может быть сложно избежать недетерминизма при параллельных вычислениях.
  
  
• 00:05:00 В этом разделе спикер обсуждает недетерминированное параллельное программирование и тот факт, что иногда оно может привести к повышению производительности, но его все же следует избегать, если в этом нет необходимости. Докладчик рекомендует разработать стратегию тестирования для управления недетерминизмом, если вы должны написать программу таким образом. Примеры стратегий включают отключение недетерминизма, использование одного и того же начального числа для случайных чисел или предоставление фиксированных значений для входных данных программы, которые в противном случае могли бы изменяться случайным образом. Докладчик подчеркивает важность наличия способа обработки ошибок в программе, вызванных недетерминизмом.
  
  
• 00:10:00 В этом разделе спикер рассказывает о стратегиях работы с недетерминированным программированием, таких как воспроизведение записи, инкапсуляция недетерминизма, замена детерминированной альтернативы, использование инструментов анализа и модульное тестирование. Спикер подчеркивает важность контроля недетерминизма для повышения шансов обнаружения ошибок в коде. Докладчик также приводит пример использования взаимного исключения и атомарности в хэш-таблице, чтобы проиллюстрировать, как обращаться с недетерминированным программированием.
  
  
• 00:15:00 В этом разделе спикер обсуждает, как параллельные инструкции, обращающиеся к одному и тому же местоположению, могут привести к ошибкам гонки и разрушить целостность системы. Стандартное решение состоит в том, чтобы сделать некоторые инструкции атомарными, что означает, что они либо полностью выполняются, либо вообще не выполняются остальной частью системы. Для этого используется блокировка взаимного исключения или блокировка мьютекса, которая представляет собой объект с функциями-членами блокировки и разблокировки. Каждый слот превращается в структуру с блокировкой мьютекса и указателем на контекст слота, что позволяет использовать функции блокировки и разблокировки перед доступом к списку, тем самым обеспечивая корректность системы.
  
  
• 00:20:00 В этом разделе видео рассматривается использование мьютексов для реализации атомарности и то, как это связано с гонками детерминированности. Блокировки мьютексов могут гарантировать, что критические секции являются атомарными, но результирующий код будет недетерминированным из-за гонки детерминированности, что может быть желательным в некоторых случаях. В видео подчеркивается важность понимания разницы между гонками данных и гонками детерминированности, а также отмечается, что простое устранение гонок данных не обязательно означает отсутствие ошибок в коде. Важно иметь способ обнаружения недетерминизма, чтобы избежать ложных срабатываний или отсутствующих гоночных ошибок в коде.
  
  
• 00:25:00 В этом разделе спикер объясняет, что отсутствие гонок данных не обязательно означает, что в коде нет ошибок. Хотя отсутствие гонок данных является положительным аспектом кода, пример блокировки для обеспечения атомарности может привести к нарушению атомарности. Кроме того, могут возникать безобидные гонки, например, когда два параллельных процесса обращаются к одному и тому же значению, что может привести к одному и тому же результату, но также может привести к неправильным значениям на некоторых архитектурах. Спикер утверждает, что, хотя некоторые люди считают доброкачественные расы безвредными, все же важно их выявлять и избегать.
  
  
• 00:30:00 В этом разделе спикер объясняет опасности недетерминированного программирования, особенно из-за условий гонки, которые могут возникнуть, когда несколько процессов пытаются установить значения в одном и том же месте. Спикер представляет концепцию «Шелков», которая допускает преднамеренные гонки, но может быть опасной, если ее неправильно использовать. Сложность гонок также может затруднить отладку и запутать инструменты, предназначенные для обнаружения правильного кода. Докладчик также обсуждает, как реализация мьютексов и их параметров может повлиять на их поведение, например, на уступчивость или вращение.
  
  
• 00:35:00 В этом разделе в видео объясняются три основных свойства мьютексов в параллельном программировании: вращение и уступка, повторный вход и неповторный вход, справедливость и несправедливость. Концепция вращения против уступки заключается в том, что поток не будет бездействовать и постоянно проверять доступ к блокировке, а скорее уступит управление операционной системе для более эффективного выполнения. Реентерабельный мьютекс позволяет потоку, который уже удерживает блокировку, получить ее снова, в то время как нереентерабельные блокировки заблокируются, если поток попытается повторно получить мьютекс, который у него уже есть. И, наконец, честный мьютекс гарантирует, что поток, который ждал дольше всего, получит блокировку первым, чтобы предотвратить возможность проблемы голодания. В видео также представлена реализация простого вращающегося мьютекса на языке ассемблера.
  
  
• 00:40:00 В этом разделе видео обсуждается использование мьютекса в параллельном программировании и почему вместо простого получения мьютекса используется инструкция обмена. Объясняется, что операция обмена аналогична праву, и для реализации права кассовая линия, на которой оно находится, должна быть признана недействительной на других линиях и находиться в модифицированном или исключительном состоянии. Это создает трафик в сети памяти и замедляет процесс. С другой стороны, при использовании инструкции обмена строки кэша переводятся в совместно используемое состояние, тем самым ускоряя процесс и генерируя меньше трафика.
  
  
• 00:45:00 В этом разделе спикер обсуждает разницу между вращающимся мьютексом и уступающим мьютексом. В вращающемся мьютексе программа продолжает проверять, не будет ли мьютекс разблокирован, а в уступающем мьютексе программа передает управление операционной системе, что позволяет ей планировать что-то еще. Докладчик отмечает, что существует еще один тип мьютексов, называемый конкурентным мьютексом, который позволяет достичь как вращающегося мьютекса, так и уступающего мьютекса. Докладчик также исследует использование передачи сообщений или прерываний для информирования ожидающих потоков, но отмечает, что более простым решением было бы использование механизма взаимного исключения.
  
  
• 00:50:00 В этом разделе спикер объясняет концепцию переключения контекста, то есть как часто операционная система переключается между потоками на доступных процессорах. Как правило, система переключает контекст примерно 100 раз в секунду, то есть каждое переключение занимает около 10 миллисекунд. Однако это более чем на порядок превышает время выполнения простой инструкции, а это означает, что есть много инструкций, которые могут быть выполнены до того, как поток сможет вернуться и захватить блокировку. Эту проблему можно решить, используя комбинацию прядения и уступки. Спикер называет это «проблемой проката лыж» в теоретической литературе.
  
  
• 00:55:00 В этом разделе видео рассматривается процесс принятия решения о покупке или аренде инвентаря для конкретной задачи на примере покупки или аренды спортивного инвентаря. Оратор призывает зрителей подумать о затратах на аренду и покупку и предлагает арендовать до тех пор, пока стоимость не сравняется со стоимостью покупки, а затем совершить покупку. В видео также рассматривается концепция времени переключения контекста, времени доступа к диску и проблема взаимоблокировки при одновременном удерживании нескольких блокировок. В целом, этот сегмент охватывает основные принципы повышения производительности многоядерных процессоров.
• 01:00:00 В этом разделе спикер объясняет взаимоблокировку, когда два потока удерживают ресурсы, которые требуются другому потоку, что приводит к потере производительности. Существует три основных условия взаимоблокировки: взаимное исключение (монопольный контроль над ресурсами), отказ от вытеснения (ресурсы удерживаются до завершения) и циклическое ожидание (цикл потоков, ожидающих ресурсов, удерживаемых следующим потоком). Удаление любого из этих ограничений может решить проблему взаимоблокировки. Спикер использует «Обедающие философы», историю, рассказанную Тони Хоаром на основе экзаменационного вопроса Эдсгера Дейкстры, чтобы проиллюстрировать проблему с тупиком. В этой истории философы сидят за столом и едят лапшу палочками для еды, где каждая тарелка с лапшой находится между двумя палочками для еды, и им нужны две палочки для еды, чтобы есть лапшу. Философы хватают палочки для еды слева и справа, чтобы есть лапшу. Однако, если они все возьмут левую палочку для еды слева от себя, они в конечном итоге умрут с голоду.
  
  
• 01:05:00 В этом разделе спикер обсуждает проблему взаимной блокировки в параллельном программировании и предлагает решение, обеспечивающее невытеснение и избегающее взаимоблокировки: линейное упорядочение мьютексов. Нумеруя каждый мьютекс и стратегически блокируя их в соответствии с порядковым номером, программисты могут гарантировать, что цикл ожидания (необходимое условие взаимоблокировки) не может возникнуть. Тем не менее, он предостерегает программистов, чтобы они знали об инкапсуляции блокировок системой выполнения в Silk, поскольку введение дополнительной недетерминированности через эти блокировки может привести к проблемам. Он приводит пример, когда тупиковая ситуация может возникнуть только с одной блокировкой, подчеркивая важность тщательного рассмотрения при разработке параллельных программ.
  
  
• 01:10:00 В этом разделе спикер углубляется в тему транзакционной памяти, недавней методики исследовательского уровня, которая включает в себя транзакции базы данных, в которых атомарность происходит неявно, без необходимости указывать блокировки. Докладчик приводит пример того, как транзакционная память полезна при параллельных вычислениях графа, а именно при исключении Гаусса, когда одновременное удаление двух узлов приводит к нарушению атомарности. Идея транзакционной памяти состоит в том, чтобы представить критическую область как транзакцию, и после фиксации все обновления памяти в критической области выглядят так, как будто они произошли одновременно.
  
  
• 01:15:00 В этом разделе докладчик обсуждает разрешение конфликтов, разрешение конфликтов, продвижение вперед и пропускную способность транзакционной памяти. Они вводят алгоритм, который использует подход на основе блокировки с конечным массивом владельцев и методом требования сортировки освобождения для предотвращения взаимоблокировок и голодания без необходимости глобальной блокировки. Алгоритм регистрирует чтение и запись, чтобы разрешить откат или атомарную фиксацию, когда транзакция прерывается. Массив блокировок используется для блокировки местоположения, на которое сопоставляется хеш-функция, что позволяет осуществлять справедливое получение блокировок. Этот алгоритм позволяет выполнять параллельные транзакции без ущерба для производительности и без взаимоблокировок.
  
  
• 01:20:00 В этом разделе спикер обсуждает алгоритм, который называется сортировкой освобождения и повторным захватом. Алгоритм работает, жадно пытаясь получить блокировку области памяти, и если возникает конфликт, транзакция откатывается, не освобождая удерживаемые блокировки. После этого алгоритм снимает все блокировки с индексами, превышающими индекс местоположения, к которому он пытается получить доступ. Затем он получает желаемую блокировку и, наконец, получает снятые блокировки в отсортированном порядке. Этот процесс повторяется до тех пор, пока транзакция не будет успешной. Алгоритм предназначен для предотвращения попыток одновременного получения блокировки несколькими блокировками, что может привести к проблемам с производительностью.

[MetaQuotes]

Лекция 17. Синхронизация без блокировок

Лекция 17. Синхронизация без блокировок

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

Во второй части видео обсуждается использование ограждений памяти и инструкций синхронизации для предотвращения ошибок в параллельных программах. Докладчик исследует различные способы реализации ограждений памяти, явно или неявно, а также важность тщательного проектирования и координации между различными командами, работающими над различными аспектами процессора. Кроме того, лектор обсуждает использование инструкций CAS как части алгоритма без блокировок в стандарте языка C11 для реализации мьютексов n-поточных алгоритмов взаимного исключения без взаимоблокировок, использующих только константное пространство. Чарльз Лейзерсон объясняет проблему использования блокировок в многопоточной системе и решение с использованием вместо этого CAS, поскольку поток, удерживающий блокировку в течение длительного времени, потенциально может заблокировать другие потоки, ожидающие доступа к тому же ресурсу. Кроме того, видео освещает потенциальную проблему ABA-проблемы со сравнением и обменом и побуждает тех, кто интересуется этой темой, узнать больше об алгоритмах без блокировки.

• 00:00:00 , и их инструкции чередуются для создания глобального линейного порядка всех инструкций. В этом заключается идея модели последовательной согласованности памяти, которая является наиболее важной моделью памяти с теоретической точки зрения. Важно понимать модели памяти, потому что при отсутствии блокировок поведение параллельных программ зависит от модели памяти. Один пример, представленный в лекции, иллюстрирует этот момент, задавая вопрос, возможно ли, чтобы два процессора имели значение 0 после параллельного выполнения их кода, что зависит от используемой модели памяти.
  
  
• 00:05:00 В этом разделе Чарльз Лейзерсон обсуждает концепцию синхронизации без блокировок, при которой загрузки и сохранения должны подчиняться некоторому глобальному линейному порядку, чтобы выполнение было последовательным. Он использует пример чередования различных значений, чтобы продемонстрировать различные пути выполнения, которые могут возникнуть, и то, как аппаратное обеспечение может делать все, что захочет. Он также объясняет, что, несмотря на то, что может быть много разных способов чередования значений, это должно выглядеть так, как если бы загрузки и сохранения следовали линейному порядку, чтобы выполнение было последовательным. В конечном счете, Лейзерсон заключает, что не существует выполнения, которое заканчивается, когда оба значения равны нулю, и интересно отметить, что ни один из современных компьютеров не обеспечивает последовательной согласованности.
  
  
• 00:10:00 В этом разделе обсуждается концепция последовательной согласованности, которая включает в себя понимание взаимосвязи между инструкциями и их порядком, линейной зависимости между соединением со стрелкой вправо, порядком процессора и последовательностью инструкций. Кроме того, взаимное исключение можно выполнить без использования ресурсоемких инструкций или блокировок, если подумать о последовательной согласованности и реализовать общую структуру данных с помощью операций загрузки и сохранения. В примечаниях к лекциям описываются методы, использующие специализированные операции, такие как проверка и установка или сравнение и замена, но представленное решение позволяет избежать взаимоблокировок или других нежелательных явлений, возникающих при использовании блокировок.
  
  
• 00:15:00 В этом разделе Чарльз Лейзерсон объясняет алгоритм Петерсона для достижения взаимного исключения в параллельной программе, использующей только операции загрузки и сохранения. Алгоритм позволяет двум параллельным процессам, Алисе и Бобу, выполнять код, не мешая друг другу, используя набор переменных и механизм очередности. Код гарантирует, что только один процесс одновременно может войти в критическую секцию и изменить общий ресурс. В отличие от блокировок, алгоритм Петерсона не полагается на получение или освобождение блокировки, а вместо этого использует загрузки и сохранения для достижения взаимного исключения.
  
  
• 00:20:00 В этом разделе спикер обсуждает алгоритм Петерсона для достижения взаимного исключения в критической секции без использования блокировок. Он объясняет, что только один человек может войти в критическую секцию за раз, и алгоритм гарантирует, что любой, кто хочет войти в критическую секцию, может сделать это, если он единственный, кто хочет войти. Затем спикер представляет доказательство алгоритма, в котором предполагается, что и Алиса, и Боб вместе находятся в критической секции, и получается противоречие. Доказательство основано на отношении «происходит до» и программном порядке выполнения инструкций.
  
  
• 00:25:00 В этом разделе спикер объясняет процесс синхронизации без блокировок. Они устанавливают цепочки инструкций и следят за тем, чтобы они выполнялись в правильном порядке, чтобы избежать ошибок синхронизации. В качестве демонстрации они используют пример Боба и Алисы, желающих получить доступ к общему ресурсу. Они объясняют, что при синхронизации инженеры должны быть осторожны и проверять, что «происходит до событий», чтобы убедиться, что они происходят в правильном порядке.
  
  
• 00:30:00 В этом разделе Чарльз Лейзерсон обсуждает концепцию проверки моделей и ее использование при анализе сетевых протоколов, протоколов безопасности и кэширования. Затем он продолжает объяснять свойства алгоритма Петерсона, который гарантирует свободу от голодания, но не работает более чем с двумя процессами. Лейзерсон также исследует проблемы синхронизации через память и отсутствие последовательной согласованности в современных процессорах, что приводит к ослаблению согласованности памяти и трудностям в правильной синхронизации.
  
  
• 00:35:00 безопасно ли менять порядок инструкций, не вызывая проблем с задержкой загрузки? Второе ограничение возникает, когда между инструкциями нет зависимости данных, что означает, что инструкции не используют общие данные или не используют одно и то же место в памяти. Переупорядочивание инструкций в этом случае может повысить производительность и покрыть задержку загрузки, поскольку загрузка может быть выполнена раньше, а другая работа может быть выполнена в ожидании результата. Понимание этих концепций аппаратного уровня может помочь в рассуждениях о программном обеспечении и оптимизации производительности.
  
  
• 00:40:00 В этом разделе Чарльз Лейзерсон объясняет концепцию переупорядочивания при синхронизации без блокировок. Он поясняет, что переупорядочивание безопасно выполнять до тех пор, пока нет параллелизма, особенно когда процессор работает или в потоке инструкций есть пузыри. Это связано с тем, что в современных процессорах аппаратное обеспечение хранит данные в буфере и обходит нагрузки, обращаясь непосредственно к системе памяти. Однако этот обход может привести к проблемам с корректностью, если загружается одно из хранилищ.
  
  
• 00:45:00 В этом разделе Чарльз Лейзерсон объясняет, как происходит аппаратное переупорядочивание и почему оно не удовлетворяет последовательной согласованности, а также как x86 имеет модель согласованности памяти, называемую общим порядком хранения, которая слабее, чем последовательная согласованность. Правила для общего порядка хранения включают в себя никогда не переупорядочивать загрузки вместе с загрузками, загрузки, видимые в одном и том же порядке внешними процессорами, никогда не переупорядочивать закладки вместе с загрузками и переупорядочивать загрузки только с предшествующими загрузками в другое место, но не с предшествующими загрузками в другое место. то же место. Инструкции блокировки и порядок памяти соблюдают общий порядок.
  
  
• 00:50:00 В этом разделе спикер обсуждает, как изменение порядка инструкций может нарушить последовательную согласованность и привести к неверным значениям. Переупорядочение может происходить как в оборудовании, так и в компиляторе, и важно знать, что инструкции блокировки не будут перемещены перед другими инструкциями. Спикер также отмечает, что грузы могут идти раньше магазинов, если они находятся по другому адресу. Опасность переупорядочения продемонстрирована в алгоритме Петерсона, который может полностью испортиться, если произойдут определенные переупорядочения. Поэтому важно писать детерминированный код, чтобы избежать этих проблем при синхронизации через память.
  
  
• 00:55:00 В этом разделе Чарльз Лейзерсон обсуждает проблему переупорядочивания при написании параллельного и параллельного кода, когда важно избежать определенной загрузки перед сохранением. Чтобы справиться с такими сценариями, инженеры вводят барьеры памяти, которые поддерживают относительный порядок с другими инструкциями, но за это приходится платить повышенной сложностью и потенциальными ошибками. Лейзерсон также утверждает, что параллельным машинам выгодно поддерживать последовательную согласованность, но это сложная задача для разработчиков аппаратного обеспечения.
  
  
• 01:00:00 В этом разделе докладчик обсуждает важность барьеров памяти и инструкций синхронизации для предотвращения ошибок параллельных программ. Докладчик описывает различные способы реализации ограждений памяти, например, явно в виде инструкции или неявно через другие инструкции синхронизации, такие как блокировка и обмен. Однако бывают случаи, когда ограничение памяти может фактически замедлить работу программы, что свидетельствует о важности тщательного проектирования и координации между разными командами, работающими над разными аспектами процессора. Кроме того, спикер советует использовать изменчивые переменные и барьеры компилятора, чтобы компилятор не оптимизировал переменные и не вызывал ошибок в параллельном коде.
  
  
• 01:05:00 В этом разделе лектор обсуждает синхронизацию без блокировок в стандарте языка C11. Стандарт определяет слабую модель памяти, которая позволяет объявлять вещи атомарными, требуя использования дорогостоящих операций, таких как ограничение памяти или атомарное сравнение и замена для алгоритма взаимного исключения без взаимоблокировок. Здесь инструкция CAS (сравнение и замена) рассматривается как часть алгоритма без блокировки. Инструкция проверяет, совпадает ли значение в памяти со старым значением, прежде чем заменить его новым значением, и все это делается атомарно. Использование CAS позволяет реализовать мьютексы n-поточных алгоритмов взаимного исключения без взаимоблокировок, используя только константное пространство. Инструкция блокировки, которая вращается до тех пор, пока не получит значение true, используется для замены true, утверждая, что кто-то удерживает блокировку.
  
  
• 01:10:00 В этом разделе профессор Чарльз Лейзерсон объясняет, как использовать функцию сравнения и замены (CAS) для решения проблем синхронизации. Он демонстрирует, как использовать CAS в качестве блокировки, и исправляет ошибку в коде, представленном студентом. Затем он представляет неправильный код, используемый для вычисления суммы значений в массиве, что приводит к состоянию гонки. Он представляет блокировку мьютекса в качестве типичного решения и объясняет потенциальную проблему выгрузки потока после получения блокировки, что приводит к тому, что другие потоки ожидают блокировки, что препятствует прогрессу.
  
  
• 01:15:00 В этом разделе Чарльз Лейзерсон объясняет проблему использования блокировок в многопоточной системе и решение проблемы с использованием CAS. С блокировками поток потенциально может удерживать блокировку в течение длительного времени, блокируя другие потоки, ожидающие доступа к тому же ресурсу. Однако в CAS за загрузкой x следует сохранение x после вычисления temp, а также имеются переменные old и new для хранения старого результата и добавления временного результата к этому старому значению для получения нового значения, которое можно заменяется, если старое значение не изменилось. Чарльз также упоминает проблему ABA со сравнением и обменом и призывает тех, кто интересуется этой темой, узнать больше об алгоритмах без блокировок.

[MetaQuotes]

Лекция 18. Языки предметной области и автонастройка

Лекция 18. Языки предметной области и автонастройка

В этом видео профессор Саман Амарасинхе из отдела EECS в Массачусетском технологическом институте обсуждает преимущества использования предметно-ориентированных языков (DSL) и автонастройки при проектировании производительности. Он подчеркивает важность DSL, которые охватывают специфические области, которые трудно описать на языках общего назначения, что позволяет программистам использовать знания экспертов в предметной области для повышения производительности. Сингх обсуждает оптимизацию графовых процессов с использованием DSL, включая разбиение графа и важность формы графа в вычислениях. Он представляет DSL Halide для обработки изображений, который обеспечивает быструю оптимизацию кода и переносимость между машинами. Он обсуждает использование Halide в различных отраслях, таких как Google и Adobe. В конечном счете, он подчеркивает важность экспериментов с различными подходами к оптимизации кода, уделяя особое внимание параллелизму, локальности и избыточной работе.

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

• 00:00:00 В этом разделе профессор Саман Амарасинхе, профессор кафедры EECS в Массачусетском технологическом институте, рассказывает о предметно-ориентированных языках и автонастройке. Он объясняет, что эти языки имеют инженерные преимущества, поскольку они охватывают определенные области, которые трудно описать на языке общего назначения. Предметно-ориентированные языки намного легче понять и поддерживать, и они позволяют программисту воспользоваться знаниями экспертов предметной области для получения действительно хорошей производительности. Кроме того, если построен правильно, предметно-ориентированный язык может оставить компилятору решение более низкого уровня, что значительно упростит процесс оптимизации.
  
  
• 00:05:00 В этом разделе докладчик обсуждает использование предметно-ориентированных языков (DSL) в разработке производительности. Они поощряют, когда это возможно, оставлять производительность компилятору и вводят три различных языка/среды программирования для обработки графов: Graffiti, Halide и OpenTuner. Они отмечают, что графики есть везде, от поиска Google до систем рекомендаций, и углубляются в алгоритм PageRank, используемый Google для ранжирования веб-страниц. Алгоритм PageRank просматривает соседей веб-страницы и вычисляет новый рейтинг на основе их влияния, показывая важность обработки графа в обеспечении производительности.
  
  
• 00:10:00 В этом разделе спикер обсуждает графовые алгоритмы, которые могут включать обработку огромных объемов данных и итерацию вычислений для всего графа. Чтобы оптимизировать код для повышения производительности, можно использовать DSL. Тип алгоритмов, используемых для обработки графа, включает алгоритмы, управляемые топологией, когда весь граф участвует в вычислениях, и алгоритмы, управляемые данными, когда обработка выполняется на небольшой области или части графа. Существует также несколько способов разворота графика, и каждый из них имеет разный набор результатов.
  
  
• 00:15:00 В этом разделе обсуждается тема разбиения графа, когда большой граф делится на более мелкие части. Преимущество секционирования графа заключается в том, что оно допускает параллелизм, а также обеспечивает хорошую локальность, а это означает, что обрабатываемые узлы достаточно малы, чтобы поместиться в кэш. Разделение графа также оказывает влияние на графы социальных сетей, поскольку они имеют отношение степенного закона. Это означает, что некоторые узлы имеют больше соединений или большее влияние, чем другие, и при обработке этих графиков необходимо уделять больше внимания определенным соединениям и узлам, учитывая их важность.
  
  
• 00:20:00 В этом разделе спикер обсуждает важность формы графа в вычислениях, в частности, как размер и локальность графа могут повлиять на эффективность алгоритмов параллелизма. Такие факторы, как параллелизм, локальность и необходимость дополнительной работы, должны быть тщательно сбалансированы для достижения наилучшей производительности для данного алгоритма, и правильный метод должен быть выбран в зависимости от типа графа, типа алгоритма и используемого оборудования. Был разработан предметно-ориентированный язык, чтобы отделить постоянный алгоритм от методов обработки, чтобы лучше оптимизировать эти факторы.
  
  
• 00:25:00 В этом разделе спикер обсуждает, как можно использовать предметно-ориентированные языки (DSL) для написания кода на более высоком уровне, делая его более простым и элегантным. Они приводят примеры различных алгоритмов и того, как DSL обеспечивают простой способ их вычисления. Кроме того, спикер объясняет, как можно оптимизировать планирование DSL, чтобы получить максимально возможную скорость, даже с учетом параллельной обработки. Код можно варьировать в зависимости от изменений графа или машины, но алгоритм остается прежним. Докладчик подчеркивает важность того, что DSL обеспечивают простоту программирования и в то же время являются достаточно мощными для создания оптимизированных расписаний.
  
  
• 00:30:00 В этом разделе спикер обсуждает другой предметно-ориентированный язык, Halide, который фокусируется на обработке изображений с плотными регулярными структурами. Halide помогает сократить объем программирования, необходимого для достижения оптимальной производительности, и повышает переносимость программы на разные машины. Докладчик приводит пример размытия три на три, чтобы продемонстрировать, как работает Halide. Halide имеет аналогичный графовому языку шаблон, обсуждавшийся ранее, с точки зрения оптимизации производительности за счет различных комбинаций различных методов.
  
  
• 00:35:00 В этом разделе спикер обсуждает использование предметно-ориентированных языков (DSL) и автонастройку для оптимизации производительности кода. Он приводит пример фильтра изображений, который работает быстрее с использованием DSL под названием Halide по сравнению с допустимым кодом C. Halide позволяет отделить алгоритм от расписания, что обеспечивает простую оптимизацию конвейера выполняемых чистых функций. Наконец, спикер подчеркивает необходимость компромисса между локальностью, параллелизмом и избыточной работой для достижения наилучшей производительности доступных вычислительных ресурсов.
  
  
• 00:40:00 В этом разделе спикер обсуждает важность локальности при обработке изображений. При обработке большого изображения неэффективно применять фильтры, которые работают сразу со всем изображением, потому что оно не помещается в кэш. Вместо этого спикер предлагает разбить изображение на более мелкие участки и применить фильтры к каждому участку, ориентируясь на локальность и параллелизм. Этого можно достичь с помощью структуры планирования и оптимизации пропускной способности вычислений и детализации хранилища. Это также может потребовать некоторой избыточной работы для достижения лучшей локальности и параллелизма.
  
  
• 00:45:00 В этом разделе спикер обсуждает доменные языки и автонастройку, уделяя особое внимание использованию Halide. Halide может объединять библиотечные функции, что быстрее, чем вызов библиотек, потому что существует больше локальности. Докладчик показывает, как Halide может оптимизировать вычислительные процессы, такие как вычисление билатерального фильтра и алгоритмы сегментации. В одном примере алгоритм сегментации, написанный на MATLAB, который вызывал оптимизированные вручную библиотеки, был в 70 раз быстрее, когда был написан на Halide. Halide — важная часть Google, она была интегрирована в телефоны Android и использовалась в Google Glass.
  
  
• 00:50:00 В этом разделе спикер обсуждает эффективность использования Halide для предварительной обработки и то, как он становится широко используемым в различных отраслях. Halide может похвастаться приростом скорости на 4-5% по сравнению с предыдущими версиями, что важно для Google, учитывая количество загруженных видео. Adobe также объявила, что все фильтры Photoshop написаны на Halide. Процессор обработки изображений Snapdragon и Intel также начинают использовать Halide. Докладчик также обсуждает сходство Halide и Graph с точки зрения возможности автоматизации оптимизации, облегчающей работу инженера по производительности. Однако когда дело доходит до алгоритмической оптимизации, это изменение более высокого уровня, требующее специальных контекстуальных знаний, что затрудняет автоматизацию. Тем не менее, такие инструменты, как запланированные языки, дают пользователям возможность попробовать разные подходы и добиться более высокой производительности.
  
  
• 00:55:00 В этом разделе спикер обсуждает сложность современных компьютерных систем и то, что не существует единственно правильного способа оптимизации кода. Они подчеркивают важность опробования различных подходов и значения кэшей, локальности и параллелизма. Они также обсуждают, как люди в различных областях, таких как биология и физика, тратят много времени на оптимизацию кода, а не на исследования, потому что они не могут писать программы достаточно быстро из-за сложности кода. Спикер предполагает, что поиск областей, в которых люди проводят большую часть своего времени, взламывая и придумывая абстракции, может быть интересной областью для исследования. В целом пространство для оптимизации программ включает в себя параллелизм, локальность и избыточную работу, и игра в этом пространстве имеет решающее значение для инженеров по производительности.
• 01:00:00 В этом разделе спикер обсуждает проблемы проектирования производительности, которые включают поиск правильных параметров для оптимальной работы программы. Он объясняет, что существует множество параметров, которые можно настроить, например выделение памяти и размер блока, но определить правильные значения каждого параметра для каждой программы может быть сложно. Однако выступающий предполагает, что автонастройка может решить эту проблему путем автоматического поиска оптимальных значений в большом пространстве параметров. Он объясняет, что решения, основанные на эвристике, которые включают жестко запрограммированные правила для определенных ситуаций, могут работать в большинстве случаев, но не всегда могут быть оптимальными. Спикер также отмечает, что построение моделей системы может быть проблематичным, так как модель не учитывает все важные факторы, что может привести к неоптимальным результатам.
  
  
• 01:05:00 В этом разделе спикер обсуждает проблемы поиска оптимальных решений в условиях меняющихся технологий или меняющихся требований. Он отмечает, что существует множество «эвристик», которые программисты используют для управления своими решениями, часто основанные на рекомендациях или эмпирических правилах, которые могут больше не применяться. Одним из вариантов является исчерпывающий поиск, но он может быть нецелесообразным, учитывая огромное количество возможных перестановок. Чтобы решить эту проблему, спикер рекомендует использовать автонастройку как способ сократить пространство поиска и быстрее найти оптимальные решения. Автонастройка включает в себя определение пространства допустимых значений, случайный выбор значения для тестирования, а затем итерацию на основе результатов производительности. OpenTuner является одним из примеров фреймворка, в котором для ускорения этого итеративного процесса используется набор методов, таких как поиск по холмам и случайный поиск.
  
  
• 01:10:00 В этом разделе спикер обсуждает концепцию автонастройки и то, как ее можно применить при создании расписаний для Try. Понимая используемые графики и ритм, автонастройку можно использовать для создания расписания более эффективно и действенно, чем полный поиск. Этот метод позволял составлять расписания менее чем за два часа, а в некоторых случаях даже лучше, чем то, что первоначально считалось наилучшим возможным расписанием.

[MetaQuotes]

Лекция 19. Leiserchess Codewalk

Лекция 19. Leiserchess Codewalk

В этом видео на YouTube под названием «19. Leiserchess Codewalk» Хелен Сюй объясняет правила Lesierchess, игры, в которую играют две команды с целью выстрелить в короля противоположной команды или убить своего короля. В игре есть два типа ходов: базовые и ударные, а также правило Ко, которое делает ход незаконным, если он отменяет последний ход противника. Сюй погружается в различные аспекты игры, включая метод контроля времени Фишера, нотацию Форсайта-Эдвардса, облачный автотестер и организацию проекта, оценку и сравнение ботов с использованием рейтингов Эло, генерации ходов, статической оценки и алгоритмов поиска, таких как альфа-бета, принципиальная вариация, обрезка поддеревьев и таблицы транспонирования. Она также обсуждает важность тестовой инфраструктуры для оптимизации программы и файла eval.c, который содержит эвристики, оценивающие каждую клетку на доске в зависимости от типа фигуры и ее цвета.

Спикер также углубляется в аспект игры с лазерным покрытием, объясняя сложную систему генерации всех возможных ходов для позиции на основе цвета игрока с использованием оператора while true. Они также объясняют важность правильности кода и способы ее проверки, предлагая преобразование представления для обеспечения правильности перед оптимизацией для повышения производительности. Спикер также обсуждает большую гибкость, обеспечиваемую интерфейсом Leiserchess UCI, который позволяет пользователям редактировать таблицы и команды по своему вкусу и заверяет зрителей, что мертвый код будет очищен, а о любых других ошибках следует сообщать для исправления.

• 00:00:00 В этом разделе Хелен рассказывает о правилах игры Lesierchess и о том, как в нее играть. В игре участвуют две команды, оранжевая и лиловая, каждая из которых имеет семь пешек и короля. Цель игры состоит в том, чтобы выстрелить в короля противоположной команды или выстрелить в своего короля. В игре есть два типа движений: базовые и ударные. Кроме того, в игре есть правило Ко, которое делает ход незаконным, если он отменяет последний ход противника, просто возвращаясь туда, где была команда противника. Ничья происходит, если каждая команда сделала 50 ходов без потери пешки, повторяется одна и та же позиция или две команды соглашаются на ничью.
  
  
• 00:05:00 В этом разделе спикер объясняет метод контроля времени Фишера, используемый в leiserchess. Каждый игрок начинает с начального бюджета времени и увеличения времени. В используемом примере каждый игрок начинает с 60 секунд, а когда он заканчивает свой ход, он получает дополнительные 0,5 секунды. Но реальный срок может быть любым. Затем спикер демонстрирует, как играть в leiserchess, прося аудиторию предложить ходы для мандарина, чтобы убить пешку в F5, избегая контратак. Однако спикер предупреждает о тонкостях игры, таких как наивное убийство всех фигур, поскольку это может открыть противника.
  
  
• 00:10:00 В этом разделе Хелен Сю обсуждает нотацию Форсайта-Эдвардса как инструмент для представления шахматной позиции с помощью строки, которая полезна для целей отладки, позволяя легко вернуться к определенной позиции. Она также объясняет, как читать журналы шахматных партий, где она разбирает каждый ход и соответствующие аннотации. Кроме того, она демонстрирует, как использовать сервер схватки для тестирования ботов с другими командами в классе, а также как бросать вызов другим командам и просматривать сыгранные матчи.
  
  
• 00:15:00 В этом разделе Хелен Сю обсуждает облачный автотестер и организацию проекта для Lesierchess. В то время как сервер схватки разрешает только одну игру за раз, облачный автотестер может запускать несколько игр и двоичных файлов с контролем времени, который можно настроить в соответствии с предпочтениями каждого пользователя. Организация проекта в репозитории включает каталоги doc, auto tester, pgnstates,tests, player и webgui. Автотестер — это локальный автотестер Java, используемый для локального тестирования изменений, в то время как в каталоге тестов можно указать конфигурации для автотестирования. Хелен Сюй также представляет универсальный нагрудный интерфейс (UCI), протокол связи, используемый Lesierchess для взаимодействия с автоматическим тестером.
  
  
• 00:20:00 В этом разделе спикер обсуждает, как боты будут измеряться и сравниваться с использованием рейтингов Эло, которые представляют собой рейтинговую систему, основанную на относительном уровне навыков в играх с нулевой суммой. Рейтинг Elo основан не только на времени, но и на количестве узлов, просматриваемых в секунду с использованием UCI. Затем спикер более подробно рассказывает об игре, например о создании ходов, представлении доски и структуре, используемой для хранения позиции. Кроме того, ход представлен с использованием 28 битов, включая тип фигуры, ориентацию, от квадрата, промежуточного квадрата и двух квадратов. Эталонная имплантация генерирует все ходы в зависимости от того, чья сейчас очередь, путем итерации по доске и создания всех ходов этой конкретной фигуры. Докладчик упоминает об использовании функции отладки perft, чтобы убедиться, что измененная генерация ходов возвращает одни и те же ходы из каждой позиции.
  
  
• 00:25:00 В этом разделе спикер обсуждает, как определить, является ли ход хорошим, с помощью статической оценки, которая генерирует оценку на основе позиции с использованием эвристики. Эвристики включают те, которые сосредоточены на короле, пешках и расстоянии, и могут помочь определить, хороша позиция или нет. Спикер также рассказывает о том, как игровые программы используют деревья поиска, чтобы играть в игру и выбирать лучший ход на основе оценки. Чтобы уменьшить количество узлов, спикер подробно описывает поиск в режиме покоя и поиск минимум-максимум, что может увеличить количество оцениваемых узлов и повысить производительность.
  
  
• 00:30:00 В этом разделе спикер обсуждает алгоритм под названием альфа-бета, который используется при поиске из узла с окном альфа-бета. Если значение поиска падает ниже альфы, ход недостаточно хорош, и вы продолжаете поиск. Бета по существу означает, что одна сторона пытается максимизировать, а другая пытается минимизировать. Следовательно, если значение падает выше бета, то вы генерируете бета-отсечку, потому что противник не позволит вам сделать этот ход, так как это было бы слишком хорошо. Затем спикер объясняет принцип поиска вариантов, который предполагает, что первый ход является лучшим, и вы запускаете предварительный поиск, который также называется поиском в нулевом окне, на оставшихся ходах, чтобы убедиться, что они хуже. Этот способ поиска является разновидностью алгоритма альфа-бета.
  
  
• 00:35:00 В этом разделе обсуждается концепция сокращения поддеревьев в алгоритмах минимаксного поиска. Идея обрезки поддеревьев состоит в том, чтобы удалить поддеревья, оценки которых ниже наилучшего из найденных на данный момент. Это уменьшает количество оцениваемых узлов и ускоряет процесс поиска. Противник также ищет лучший ход и пытается минимизировать очки игрока. Баланс между максимизацией очков игрока и минимизацией очков противника имеет решающее значение, и цель состоит в том, чтобы найти ход, который будет хорош для игрока, а также такой, который позволил бы противник.
  
  
• 00:40:00 В этом разделе Хелен Сюй объясняет концепцию отсечения основных вариантов, когда делается предположение, что самое левое поддерево является лучшим путем, и если предположение верно, используются ранние выходы. Если предположение неверно, необходимо просмотреть все поддерево. Поиск-разведчик используется для рекурсивного применения этого к нижним поддеревьям с начальными проходами для проверки предположений. Этот метод улучшает обрезку и обрабатывает большую часть дерева игры без поиска окон.
  
  
• 00:45:00 В этом разделе мы узнаем об оптимизации поиска для программы Leiserchess. Одной из наиболее важных оптимизаций является использование таблицы транспонирования для хранения ранее встреченных позиций, что экономит время, избегая ненужных поисков. Другие оптимизации включают в себя использование хеширования Зобриста для создания уникальных хэшей для каждой позиции, таблицы ходов-убийц для хранения хороших ходов, чтобы их не нужно было пересчитывать, и отсечение бесполезности, чтобы пропустить ходы исследования, которые не увеличили бы альфа-счет. Также рекомендуется реализация более качественной открывающей книги для хранения заранее рассчитанных позиций в начале игры и экономии времени на поиск.
  
  
• 00:50:00 В этом разделе спикер обсуждает некоторые полезные инструменты для оптимизации шахматной программы, в том числе открывающие книги и базы данных эндшпиля, которые можно предварительно вычислить. Важно тестировать и иметь хорошую инфраструктуру для тестирования, чтобы иметь возможность внедрять инновации и добиваться прогресса без проблем с отладкой. Использование таблиц транспонирования в параллельном программировании делает важной возможность их отключения для целей тестирования, и при тестировании рекомендуется выполнять поиск с фиксированной глубиной. В целом наличие хорошей тестовой инфраструктуры имеет решающее значение для достижения прогресса и предотвращения серьезных проблем с отладкой.
  
  
• 00:55:00 В этом разделе спикер обсуждает файл eval.c в проекте Leiserchess и то, как он может показаться на первый взгляд ошеломляющим из-за своего размера и сложности. Однако по мере того, как пользователи знакомятся с ним, они обретают уверенность в работе с кодом приличного размера. Файл eval.c содержит эвристики, такие как p between, p center, k face и k Avengers, которые оценивают каждую клетку на доске в зависимости от типа фигуры и ее цвета. Эвристика p между определяет, находится ли пешка между обоими королями, в то время как p центральный дает бонус в зависимости от того, насколько близко пешка находится к центру доски. Эвристики k-face и k-агрессивно дают бонусы в зависимости от ориентации короля и его расстояния от противника и краев доски.
  
  
• 01:00:00 В этом разделе спикер объясняет лазерное покрытие, которое является сложным аспектом игры. Лазерное покрытие генерирует все возможные ходы конкретной позиции в зависимости от цвета игрока. Затем он предоставляет список ходов, и спикер уточняет, как эта карта выполняет свою функцию, с помощью оператора while-true. Лазерный путь отскакивает от некоторых фишек при рисовании пути и увеличивает расстояние для каждого квадрата. После создания карты процесс повторяется, и расстояние делится на фактическое расстояние от лазера. Эта сложная система оптимизирует итерации, необходимые в методе оценки для нахождения каждой фигуры на доске, что замедляет процесс, и выступающий добавляет, что представление доски по-разному и утверждение, что обе функции преобразования дают один и тот же результат, является хорошим способом сделать оптимизационные решения.
  
  
• 01:05:00 В этом разделе видео спикеры обсуждают важность поддержания корректности в коде и способы ее проверки. Они объясняют, что преобразование из одного представления в другое может замедлить процесс, но необходимо для обеспечения правильности перед оптимизацией для повышения производительности. Один из способов проверки правильности — отслеживать количество узлов и следить за тем, чтобы они оставались неизменными после внесения изменений. Они также демонстрируют, как запускать код, и показывают интерфейс UCI в Lesierchess.c, который позволяет вам устанавливать значения для различных вещей без необходимости каждый раз перекомпилировать двоичный файл. Наконец, они просматривают таблицу эвристик и объясняют, как задавать значения для автоматического тестера.
  
  
• 01:10:00 В этом разделе спикер обсуждает большую гибкость, которую предоставляет игра Leiserchess для редактирования таблиц и команд через интерфейс UCI. Это позволяет пользователям получать доступ к любым командам, включая новые эвристики, и выполнять их, а также контролировать синтаксический анализ и реализацию. Хотя некоторый мертвый код существует, профессор заверяет зрителей, что он будет очищен, а о любых других ошибках следует сообщать, чтобы они были исправлены. Наконец, он заявляет, что, хотя проект не может доставлять удовольствие каждую минуту, в целом он доставляет массу удовольствия.

[MetaQuotes]

20. Спекулятивный параллелизм и Leiserchess - A Laser-Chess Game

20. Спекулятивный параллелизм и Leiserchess

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

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

• 00:00:00 В этом разделе инструктор знакомит с концепцией спекулятивного параллелизма как способа оптимизации кода и ускорения его выполнения. Это включает в себя предположение, что определенные задачи могут выполняться параллельно, даже если они по своей сути являются последовательными, что может привести к некоторым напрасным усилиям, если предположение окажется неверным. Преподаватель приводит пример порогового значения суммы и показывает простую оптимизацию путем досрочного выхода, если частичная сумма когда-либо превысит пороговое значение, хотя это вводит предсказуемую ветвь, которая все же может замедлить код.
  
  
• 00:05:00 В этом разделе спикер обсуждает, как смягчить проблему добавления слишком большого количества данных во внутренний цикл при параллельной работе. Они объясняют, что интеллектуальный анализ полос можно использовать для замены цикла из n итераций на цикл из n в течение четырех итераций с внутренним циклом из четырех итераций, а также для проверки того, был ли превышен порог на каждой четвертой итерации, чтобы минимизировать стоимость чек. Чтобы распараллелить короткозамкнутый цикл, спикер добавляет в код флаг прерывания и рекурсивно использует его, чтобы проверить, превышает ли сумма предел, и не был ли он прерван перед установкой флага в значение true. Проверяя флаг перед его установкой, они избегают гонки детерминированности и предотвращают настоящую гонку обмена.
  
  
• 00:10:00 В этом разделе видео обсуждается спекулятивный параллелизм, когда программа предсказывает, что ей нужно будет выполнять параллельную работу, и упреждающе порождает эту работу. Этот код не является детерминированным и должен использоваться только в целях повышения производительности, когда это необходимо. Крайне важно сбросить флаг прерывания и не порождать спекулятивную работу, если нет других возможностей для параллелизма и велика вероятность того, что он понадобится. Видео предостерегает от использования спекулятивного параллелизма в тех случаях, когда можно использовать лучший последовательный код, поскольку этот подход часто приводит к увеличению объема работы без ускорения. Наконец, упоминается теорема, в которой подчеркивается, что для параллелизма вероятность того, что работа не нужна, должна быть меньше числа используемых процессоров.
  
  
• 00:15:00 В этом разделе обсуждаются параллельные альфа-бета-поиски, которые включают обрезку дерева игры для оптимизации времени поиска. Буркхардт Манин и его ученики заметили, что в наилучшем дереве степень каждого узла либо равна 1, либо максимальна. Их идея состояла в том, чтобы предположить, что лучший ход был выбран после того, как первый ребенок не смог сгенерировать бета-отсечку. Это позволяет параллельно искать оставшихся дочерних элементов, не теряя при этом никакой работы. Эвристика в коде помогает гарантировать, что все выполняется в правильном порядке, например, использование алгоритма взвешивания молодых братьев и сестер для выбора наилучшего хода, даже если он выполняется на меньшую глубину. Алгоритм также прерывает подвычисления, когда они оказываются ненужными.
  
  
• 00:20:00 В этом разделе видео спикер обсуждает механизм периодического лазания вверх по дереву, чтобы проверить наличие прерванных предков в распараллеливании и избежать лишней работы. Они предлагают иметь счетчик или параметр вуду, чтобы определить, как часто проверять, потому что подтягивание дерева имеет свою стоимость. Спикер также рассказывает о структурах данных, используемых при поиске, таких как таблица транспонирования, которые могут вызывать гонки при распараллеливании. Они предлагают реплицировать его для каждого воркера или заблокировать, чтобы избежать гонок данных. Наконец, спикер рекомендует иметь способ отключить спекуляции и другие недетерминированные части кода, чтобы упростить отладку.
  
  
• 00:25:00 В этом разделе спикер рассказывает о программе, которая чуть не выиграла чемпионат мира по компьютерным шахматам в 1999 году. Они предложили изменение правил, на которое все согласились, но потом проиграли знаменитому компьютеру IBM Deep Blue. Они работали на суперкомпьютере с 1824 узлами в Sandia National Labs и проиграли только Deep Blue. Они решили допустить гонку в таблице транспонирования в своей программе, не включая блокировки для доступа к таблице, потому что это замедлит работу программы. Они подсчитали, что шансы гонки, влияющие на ценность, которую они выберут, и в конечном итоге на результат турнира, были низкими.
  
  
• 00:30:00 В этом разделе видео спикер обсуждает три структуры данных, которые важны для принятия решений в шахматном ИИ. Первая — это «убийственная» эвристика, которая отслеживает лучшие ходы на заданной глубине кода и имеет тенденцию повторяться по своей природе. Вторая - это таблица «лучших ходов», в которой все ходы более низкого порядка упорядочиваются на основе статистических данных. Обе структуры данных являются общими и требуют правильного управления при распараллеливании кода. Окончательная структура данных — это вводная книга, которая предварительно вычисляет лучшие ходы в начале игры. Тем не менее, спикер предполагает, что есть более низкие висящие плоды, чем вступительная книга, и что по статистике большинство игр не длятся достаточно долго, чтобы вводная книга была выгодной.
  
  
• 00:35:00 В этом разделе спикер обсуждает стратегию построения дебютных книг в Leiserchess, игре, в которой команды пытаются создать сильнейших шахматных ботов. Спикер отмечает, что некоторые команды добились успеха, создав сильную дебютную книгу, которая позволяет им побеждать благодаря фантастическому старту. Они также предполагают, что более эффективно хранить отдельные вводные книги для каждой стороны, чем использовать одну для обеих сторон. Кроме того, спикер рекомендует добавить в код небольшую случайность, чтобы избежать предсказуемости, но предупреждает, что нет необходимости оптимизировать для этого во время бета-тестирования. Наконец, они предлагают стратегию итеративного углубления, которая включает в себя выполнение поиска на разных глубинах, пока не истечет контроль времени. Спикер отмечает, что это хорошая стратегия, так как объем работы с каждой глубиной растет в геометрической прогрессии, но важная информация накапливается в течение первых нескольких глубин.
  
  
• 00:40:00 В этом разделе видео рассказывает о преимуществах итеративного углубления и о том, как оно приводит к лучшему упорядочению ходов при поиске. Проходя итеративное углубление, таблица транспонирования может хранить информацию о наилучшем порядке перемещений для всех промежуточных позиций, что делает сокращение более эффективным на большей глубине. Кроме того, итеративное углубление также обеспечивает хороший механизм контроля времени. В видео также затрагивается игровая база данных и почему создание базы данных эндшпиля выгодно, а также обсуждается, как избежать зацикливания в базе данных эндшпиля, сохраняя расстояние до мата, а не простое логическое значение.
  
  
• 00:45:00 В этом разделе докладчик обсуждает различные эвристики, используемые в процессе оценки алгоритмов поиска, в частности, чтобы избежать зацикливания и поиска в состоянии покоя. Спикер упоминает о важности сохранения дистанции до победы и избежания зацикливания путем поиска дистанции выигрыша, которая на единицу меньше текущей дистанции. Другая используемая эвристика - это сокращение ходов, когда сидеть на месте обычно не так хорошо, как делать ход, и сокращение без движения, когда нулевой ход применяется для упрощения поиска, когда позиция настолько хороша, что даже бездействие приведет к выигрышу. . Спикер также обсуждает Zoogs Wang в Chess и то, как расширения ходов используются в поиске лжи в Chess, когда есть только один вынужденный ход.
  
  
• 00:50:00 В этом разделе спикер рассказывает об использовании таблицы транспонирования в алгоритме поиска, который на самом деле представляет собой даг (направленный ациклический граф), так как одна и та же позиция может быть достигнута с помощью транспонированных ходов. В таблице транспонирования хранятся оценки качества, определяемые глубиной поиска, чтобы установить ценность перемещения, чтобы избежать повторного поиска той же позиции. Крайне важно не использовать ходы слишком низкого качества, так как это не позволит провести полный поиск, а сохраненное значение может быть менее точным. Кроме того, используется специальный код для хранения позиций сопряжения, рассчитанных путем вычитания некоторого очень большого числа из глубины, чтобы получить сопряжение. Также обсуждается хеширование Зобриста, метод оптимизации, используемый в алгоритмах поиска, включающий уникальное значение хеш-функции для каждой позиции на доске с одинаковыми фигурами.
  
  
• 00:55:00 В этом разделе профессор Лейзерсон объясняет концепцию хэширования Зобриста, которое используется для эффективного обновления хеш-функции, представляющей положение различных фигур на шахматной доске. Хэш-функция включает в себя создание таблицы случайных чисел, соответствующих различным комбинациям типа фигуры, строки, столбца и ориентации. Хеш-функция использует операции XOR для вычисления хэша, используя XOR значений всех частей и их ориентаций. Хеширование Zobrist использует свойство XOR для удаления фрагментов из хэш-функции путем XOR значения удаляемого фрагмента для получения хэша для оставшихся фрагментов. Это позволяет дешево и эффективно обновлять хеш-функцию всего двумя операциями XOR для любого сделанного хода.
• 01:00:00 В этом разделе спикер обсуждает различные методы оптимизации для шахматных движков. Он говорит о таблице транспонирования, в которой хранятся записи о ключе Зобриста, счете, качестве и связанном типе хода, а также о старении старых ходов. Кроме того, он упоминает концепцию сокращения поздних ходов, при которой менее перспективные ходы ищутся менее глубоко, чтобы сэкономить время. Докладчик также рассказывает о представлении доски и о том, как использование битовых досок может ускорить генерацию ходов и другие концепции шахмат за счет использования битовых трюков для эффективного выполнения таких операций, как сдвиг и подсчет битов.
  
  
• 01:05:00 В этом разделе спикер обсуждает тему «спекулятивного параллелизма и Leiserchess». Он объясняет, что одна из основных оптимизаций, которую можно сделать при работе с лазером, — это оценка того, влияет ли движение на путь лазера или нет. Кроме того, спикер предлагает заняться «лазерным покрытием», так как это очень дорого. Он также советует программистам оставить в коде старое представление и вставлять утверждения, говорящие об эквивалентности, и использовать такие программы, как Perfectiy, чтобы узнать, были ли внесены какие-либо изменения. Наконец, он обсуждает, как программа должна работать с точки зрения приближения лазера к королю и важности позиции в игре.
  
  
• 01:10:00 В этом разделе спикер обсуждает новую эвристику, которую они разработали для измерения того, насколько близко лазер приближается к королю противника в Лейзершахс. Они оценивают каждый ход, вычисляя расстояние лазера от короля, подсчитывая единицу для каждой позиции, в которой он удаляется, и дополнительное значение, если он отскакивает от противника. Они берут минимальное число, которое они могут получить на каждом поле, и используют множитель, чтобы взвесить, насколько хорошо быть рядом с королем. Они суммируют все это и умножают на магический постоянный множитель, чтобы представить значение в виде доли пешки. Полученное число колеблется в среднем до четырех.
  
  
• 01:15:00 В этом разделе спикер обсуждает различные способы повышения эффективности шахматного движка. Одно из предложений состоит в том, чтобы найти лучший способ оценить близость противника к лазеру игрока, поскольку текущий метод требует больших вычислительных ресурсов. Еще одна область оптимизации — сортировка ходов, которая также может быть дорогостоящей, особенно если нужно просеять много ходов. Спикер предлагает найти способ оптимизировать сортировку, чтобы сортировались только релевантные ходы и избегалась ненужная сортировка. Спикер также упоминает, что изменение представления для платы может быть болезненным процессом, но существуют альтернативы представлению на битовой плате, которые могут быть более эффективными.
  
  
• 01:20:00 В этом разделе видео обсуждается важность рефакторинга кода и его надлежащего тестирования, чтобы убедиться, что изменения вносятся правильно, не нарушая код. Докладчик предлагает реорганизовать доступ платы к вызову функции перед ее изменением, чтобы упростить изменение представления платы без обширного рефакторинга. Надлежащее тестирование также важно, чтобы убедиться, что изменения вносятся правильно и не нарушают код, и важно сделать код детерминированным, чтобы избежать непредсказуемости. Спикер также упоминает предстоящую лекцию Джона Бентли как ценную возможность встретиться со знаменитостью и узнать больше об этой области.