Вы упускаете торговые возможности:
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Регистрация
Вход
Вы принимаете политику сайта и условия использования
Если у вас нет учетной записи, зарегистрируйтесь
Лекция 11. Распределение памяти
Лекция 11. Распределение памяти
В этом видео лектор обсуждает выделение памяти, включая выделение и освобождение памяти. Рассматриваются различные типы хранилищ, включая стек и кучу, а также схемы выделения фиксированного и переменного размера. Также обсуждается внешняя фрагментация, вызванная рассредоточением блоков памяти, с такими решениями, как списки свободных мест или растровые изображения на странице диска. Также вводится понятие сборки мусора, включая подсчет ссылок и ограничения этого алгоритма. Также объясняются процедуры сборки мусора «пометить и очистить» и «остановить и скопировать», уделяя особое внимание тому, как последняя решает проблему фрагментации и возможную проблему корректности, создаваемую обновлениями указателя. Видео завершается примечаниями о временной и пространственной сложности алгоритма остановки и копирования и его устранении внешней фрагментации.
В этом видеоролике рассматриваются различные темы, связанные с динамическим выделением памяти, в том числе системой Buddy, процедурами маркировки и очистки, оптимизацией, сборкой мусора в режиме генерации и в реальном времени, многопоточным выделением памяти и параллельной сборкой мусора. Лектор объясняет, что генерационная сборка мусора основана на идее, что более молодые объекты сканируются чаще, а сборка мусора в реальном времени выполняется в фоновом режиме во время выполнения программы, но может привести к проблемам с корректностью, если граф объектов и указателей продолжает меняться. Наконец, лекция обобщает различные типы распределения памяти, включая стек и кучу, а также различные методы сборки мусора, такие как подсчет ссылок, пометка и очистка и остановка и копирование. Лектор упоминает, что студенты смогут попробовать некоторые из этих методов в своем домашнем задании.
Лекция 12. Параллельное выделение памяти
Лекция 12. Параллельное выделение памяти
В видео обсуждаются различные стратегии выделения памяти и их компромиссы. Объясняется использование malloc и выровненного распределения, а также важность правильного освобождения памяти с помощью free. Также рассматривается использование Mmap для выделения виртуальной памяти, а также вопросы внешней фрагментации и низкой производительности. Исследуется концепция стеков в программировании на C и C++ с упором на подход стека кактусов на основе кучи для выделения кадров стека, который может привести к лучшим доказательствам с ограниченным пространством и верхним границам. Также обсуждается использование пула линейных стеков, а также важность оптимизации для небольших блоков для минимизации фрагментации. Видео завершается обсуждением глобальных и локальных подходов к куче и связанных с ними потенциальных проблем, а также таких подходов, как списки свободных бинов и периодическая перебалансировка памяти для решения этих проблем.
В видео также обсуждаются решения для параллельного выделения памяти и в качестве решения представлен распределитель запасов. Распределитель запасов использует комбинацию локальных и глобальных куч и больших суперблоков, которые можно перемещать между кучами, чтобы уменьшить ложное совместное использование, улучшить масштабируемость и уменьшить внешнюю фрагментацию. Максимальное хранилище, выделенное в глобальной куче, не превышает максимального хранилища, выделенного в локальных кучах, а занимаемая площадь ограничивается сверху размером пользовательской области плюс выделенное, но неиспользуемое хранилище в локальных кучах. В видео также кратко обсуждаются другие распределители, такие как Je malloc и Super malloc, а результаты тестов показывают, что Super malloc работает лучше, чем Je malloc и Hoard. Обсуждение завершается ссылкой на онлайн-слайды для получения подробной информации о сборке мусора.
Лекция 13. Система Cilk Runtime
Лекция 13. Система Cilk Runtime
Система времени выполнения Cilk отвечает за планирование и балансировку нагрузки вычислений на параллельных процессорах, используя рандомизированный планировщик кражи работы для сопоставления вычислений с процессорами во время выполнения. Система предназначена для оптимизации последовательного выполнения программы даже за счет дополнительных затрат на кражи. Рабочий процесс поддерживает отдельную структуру данных колоды, которая содержит указатели на кадры стека и использует указатели начала и конца. Кадры, доступные для кражи, имеют дополнительную локальную структуру, которая содержит необходимую информацию для кражи, когда колода является внешней по отношению к стеку вызовов. В этом разделе объясняется, как система позволяет процессорам начинать выполнение с середины выполняемой функции и как усложняется синхронизация между процессорами при достижении оператора синхронизации, который не может выполняться дальше точки, поскольку определенные процессоры все еще ожидают завершения вычислений. Кроме того, выступающий обращается к производительности системы, проектным соображениям и структурам данных, а также к тому, как система оптимизирует выполнение с использованием протокола THC, включая два набора протоколов: один для исполняющего работу работника, а другой для вора.
Система Cilk Runtime System использует установленный протокол перехода и длинный переход для обработки кражи вычислений из исполнительных колод процессов-жертв. Абстракция Cactus Stack позволяет процессу-вору иметь собственный стек вызовов, чтобы предотвратить повреждение стеков жертвы. Протокол синхронизации системы использует дерево вычислений и стек Cactus, чтобы обеспечить синхронизацию только между вложенными вычислениями внутри функции. Полное дерево кадров поддерживает отношения родитель-потомок между вычислениями с незавершенными подвычислениями, чтобы упростить процесс синхронизации. Кроме того, система выполнения оптимизирует распространенный случай, когда текущая функция не имеет невыполненных дочерних вычислений и все рабочие процессы заняты. Другие поддерживаемые функции включают исключения C++, гиперобъекты редукторов и родословные.
Лекция 14. Кэширование и кэш-эффективные алгоритмы
Лекция 14. Кэширование и кэш-эффективные алгоритмы
В видеоролике о кэшировании и алгоритмах, эффективных с использованием кэша, инструктор объясняет иерархию кэша современных машин, различия между полностью ассоциативным кэшем и кэшем с прямым отображением, а также преимущества и недостатки ассоциативного кэша с набором. Видео также знакомит с идеальной моделью кэша и концепцией алгоритмов эффективного кэширования. Докладчик обсуждает лемму промаха кеша, предположение о длинном кеше и лемму о кэшировании подматрицы. Они также анализируют промахи в кэше, возникающие при чтении подматрицы и во время умножения матриц. Видео завершается представлением концепции мозаичного матричного умножения и того, как оно может значительно повысить производительность, но также отмечается, что оно не является переносимым и может быть дорогостоящим для оптимизации для нескольких уровней кэша.
В лекции рассматриваются алгоритмы кэширования и эффективного использования кэша на примере рекурсивного умножения матриц. Докладчик подчеркивает важность отдельного анализа как работы, так и промахов кеша, и отмечает, что алгоритмы с учетом кеша могут не быть оптимальными для всех машин из-за разных размеров кеша. Докладчик также обсуждает алгоритмы, не обращающие внимания на кеш, которые автоматически настраиваются для любого размера кеша, и упоминает разработки в области параллельного кода, не обращающего внимания на кеш. Наконец, цель состоит в том, чтобы спроектировать алгоритмы, которые либо учитывают кеширование, либо не обращают внимания на кеш, и обсуждение разработки алгоритмов без кеша будет продолжено в следующей лекции.
Лекция 15. Алгоритмы Cache-Oblivious
Лекция 15. Алгоритмы Cache-Oblivious
В видео обсуждаются алгоритмы без учета кеша, которые могут автоматически подстраиваться под размер кеша на машине, достигать хорошей эффективности кеша и не требуют знания параметров кеша машины. В видео показано, как написать код для моделирования диффузии тепла с помощью дифференциальных уравнений с использованием метода шаблона на двумерной матрице. Код имеет как циклическую, так и трапециевидную версии, причем последняя более эффективна с точки зрения кэширования, но не значительно быстрее в 2D-моделировании из-за предсказуемости шаблона доступа циклического кода. В видео также обсуждается взаимодействие между кэшированием и параллелизмом и диагностика потенциальных узких мест параллельного ускорения. Наконец, спикер объясняет вычисления шаблона и то, как каждая точка в массиве обновляется с использованием фиксированного шаблона, называемого шаблоном, который может страдать от промахов кеша и имеет требования к памяти, которые можно уменьшить с помощью эффективных алгоритмов, использующих временную и пространственную локальность.
Во второй части видео обсуждаются алгоритмы сортировки и слияния без кэширования. В частности, в видео рассказывается о сложности кеша при сортировке слиянием, вводится понятие многостороннего слияния и объясняется сложность кеша алгоритма многостороннего слияния. В видео также обсуждается алгоритм воронкообразной сортировки, который представляет собой алгоритм сортировки без учета кеша, который может объединять K элементов в квадрате и K отсортированных списков. Алгоритм воронкообразной сортировки является оптимальным и рекурсивно построен с квадратным корнем из K воронок. В видео объясняется, что существует множество других алгоритмов и структур данных, не обращающих внимания на кеш, таких как b-деревья, упорядоченное обслуживание файлов и приоритетные очереди. В целом, видео представляет собой введение в алгоритмы без кэширования для тех, кто хочет узнать больше об этой теме.
Лекция 16. Недетерминированное параллельное программирование
Лекция 16. Недетерминированное параллельное программирование
В этом видео обсуждаются различные концепции, связанные с детерминированным и недетерминированным параллельным программированием. Докладчик подчеркивает важность предотвращения недетерминизма, поскольку он может привести к аномальному поведению и трудностям в отладке. Стратегии управления недетерминизмом включают использование фиксированных значений, воспроизведение записи, инструменты анализа, инкапсуляцию и модульное тестирование. Подробно исследуется использование мьютексов, в том числе вращающиеся и уступающие, реентерабельные и нереентерабельные, справедливые и нечестные. Спикер также затрагивает концепцию переключения контекста и «проблему проката лыж» в контексте параллельного программирования. Сегмент завершается обсуждением основных принципов повышения производительности многоядерных процессоров.
Вторая часть видео посвящена проблеме взаимоблокировки в параллельном программировании и предлагает решения, позволяющие ее избежать, такие как линейное упорядочение мьютексов, гарантирующее отсутствие цикла ожидания. Кроме того, спикер представляет концепцию транзакционной памяти, которая обеспечивает атомарность, представляя критическую область как транзакцию, которая фиксирует все обновления сразу. Затем в видео представлен алгоритм, использующий подход на основе блокировки с конечным массивом владельцев и методом требования сортировки освобождения для предотвращения взаимоблокировок и голодания без необходимости глобальной блокировки. Наконец, объясняется алгоритм сброса сортировки и повторного захвата, который предотвращает попытки одновременного получения блокировки несколькими блокировками, что позволяет избежать проблем с производительностью.
Лекция 17. Синхронизация без блокировок
Лекция 17. Синхронизация без блокировок
Чарльз Лейзерсон исследует концепцию синхронизации без блокировки в видео на YouTube. Он приводит пример, демонстрирующий необходимость глобального линейного порядка инструкций для обеспечения последовательного выполнения, и обсуждает, как можно добиться взаимного исключения за счет последовательной согласованности, избегая трудностей и потенциальных проблем, связанных с использованием блокировок. Лейзерсон представляет алгоритм Петерсона как решение, использующее только операции загрузки и сохранения для доступа к критическим разделам без вмешательства параллельных процессов. В видео также рассматриваются проблемы синхронизации через память из-за аппаратного переупорядочивания и концепция ограждений памяти для поддержания относительного порядка с другими инструкциями. Лейзерсон утверждает, что поддержка последовательной согласованности для параллельных машин выгодна, но трудна для разработчиков оборудования.
Во второй части видео обсуждается использование ограждений памяти и инструкций синхронизации для предотвращения ошибок в параллельных программах. Докладчик исследует различные способы реализации ограждений памяти, явно или неявно, а также важность тщательного проектирования и координации между различными командами, работающими над различными аспектами процессора. Кроме того, лектор обсуждает использование инструкций CAS как части алгоритма без блокировок в стандарте языка C11 для реализации мьютексов n-поточных алгоритмов взаимного исключения без взаимоблокировок, использующих только константное пространство. Чарльз Лейзерсон объясняет проблему использования блокировок в многопоточной системе и решение с использованием вместо этого CAS, поскольку поток, удерживающий блокировку в течение длительного времени, потенциально может заблокировать другие потоки, ожидающие доступа к тому же ресурсу. Кроме того, видео освещает потенциальную проблему ABA-проблемы со сравнением и обменом и побуждает тех, кто интересуется этой темой, узнать больше об алгоритмах без блокировки.
Лекция 18. Языки предметной области и автонастройка
Лекция 18. Языки предметной области и автонастройка
В этом видео профессор Саман Амарасинхе из отдела EECS в Массачусетском технологическом институте обсуждает преимущества использования предметно-ориентированных языков (DSL) и автонастройки при проектировании производительности. Он подчеркивает важность DSL, которые охватывают специфические области, которые трудно описать на языках общего назначения, что позволяет программистам использовать знания экспертов в предметной области для повышения производительности. Сингх обсуждает оптимизацию графовых процессов с использованием DSL, включая разбиение графа и важность формы графа в вычислениях. Он представляет DSL Halide для обработки изображений, который обеспечивает быструю оптимизацию кода и переносимость между машинами. Он обсуждает использование Halide в различных отраслях, таких как Google и Adobe. В конечном счете, он подчеркивает важность экспериментов с различными подходами к оптимизации кода, уделяя особое внимание параллелизму, локальности и избыточной работе.
В видео также рассказывается о задачах, связанных с проектированием производительности и поиском оптимальных параметров для эффективной работы программы. Докладчик предполагает, что автонастройка может решить эту проблему путем автоматического поиска оптимальных значений в большом пространстве параметров. Он отмечает, что исчерпывающий поиск может быть непрактичным, а решения, основанные на эвристике, могут быть неоптимальными. Автонастройка, которая определяет пространство допустимых значений и выполняет итерации на основе результатов производительности, может ускорить процесс поиска оптимальных решений. Спикер также обсуждает применение автонастройки при генерации расписаний для Try, которая смогла генерировать расписания более эффективно и результативно, чем полный перебор.
Лекция 19. Leiserchess Codewalk
Лекция 19. Leiserchess Codewalk
В этом видео на YouTube под названием «19. Leiserchess Codewalk» Хелен Сюй объясняет правила Lesierchess, игры, в которую играют две команды с целью выстрелить в короля противоположной команды или убить своего короля. В игре есть два типа ходов: базовые и ударные, а также правило Ко, которое делает ход незаконным, если он отменяет последний ход противника. Сюй погружается в различные аспекты игры, включая метод контроля времени Фишера, нотацию Форсайта-Эдвардса, облачный автотестер и организацию проекта, оценку и сравнение ботов с использованием рейтингов Эло, генерации ходов, статической оценки и алгоритмов поиска, таких как альфа-бета, принципиальная вариация, обрезка поддеревьев и таблицы транспонирования. Она также обсуждает важность тестовой инфраструктуры для оптимизации программы и файла eval.c, который содержит эвристики, оценивающие каждую клетку на доске в зависимости от типа фигуры и ее цвета.
Спикер также углубляется в аспект игры с лазерным покрытием, объясняя сложную систему генерации всех возможных ходов для позиции на основе цвета игрока с использованием оператора while true. Они также объясняют важность правильности кода и способы ее проверки, предлагая преобразование представления для обеспечения правильности перед оптимизацией для повышения производительности. Спикер также обсуждает большую гибкость, обеспечиваемую интерфейсом Leiserchess UCI, который позволяет пользователям редактировать таблицы и команды по своему вкусу и заверяет зрителей, что мертвый код будет очищен, а о любых других ошибках следует сообщать для исправления.
20. Спекулятивный параллелизм и Leiserchess - A Laser-Chess Game
20. Спекулятивный параллелизм и Leiserchess
В этом видео на YouTube под названием «20. Спекулятивный параллелизм и Leiserchess» инструктор знакомит с концепцией спекулятивного параллелизма, которая, по сути, заранее предполагает, что определенные задачи могут выполняться параллельно и могут привести к более быстрому коду. Однако спикер предупреждает, что этот код не является детерминированным и его следует использовать только при необходимости, а также предостерегает от его использования в тех случаях, когда можно использовать лучший серийный код. Значительная часть видео вращается вокруг обсуждения параллельных альфа-бета-поисков, которые включают обрезку дерева игры для оптимизации времени поиска, а также рассказывают о различных структурах данных и эвристике, используемых в процессе оценки алгоритмов поиска, в частности, чтобы избежать циклов и бездействия. поиск. В видео также затрагиваются преимущества итеративного углубления и то, как оно приводит к лучшему порядку ходов при поиске, а также обсуждается хеширование Зобриста, метод оптимизации, используемый в алгоритмах поиска, включающий уникальное значение хеш-функции для каждой позиции на шахматной доске с одинаковыми фигурами.
В этом видео также обсуждаются различные методы оптимизации для шахматных движков, такие как таблицы транспонирования, сокращение поздних ходов и использование битовых досок для генерации ходов. Спикер также затрагивает тему «спекулятивного параллелизма и Leiserchess», где советует программистам оценивать, влияет ли ход на путь лазера, и ориентироваться на «покрытие лазера». Спикер предлагает оставить в коде старые представления и использовать программы для тестирования изменений. Они также разработали эвристику для измерения того, насколько близко лазер находится к королю в Leiserchess. Дополнительные предложения по оптимизации включают поиск лучшего способа оценки близости противника к лазеру игрока и оптимизацию сортировки ходов. Наконец, обсуждается важность правильного рефакторинга и тестирования кода.