OpenAI Five versus Dota

https://blog.openai.com/openai-five/

• Отличное оформление блога: интерактивные картинки, поясняющие текущее состояние модели, цели, …
• OpenAI - это некоммерческая исследовательская организация
• OpenAI Five - команда из 5 нейронных сетей
• Начала побеждать новичков в Dota2.
• Сейчас играют с ограничениями, но цель - победить на мировом соревновании “The International”
• Dota2 - одна из самых сложных электронных игр в мире
• OpenAI Five играет 180 лет сама против себя каждый день
• Использует Reinforcement Learning, и работает на 256GPUs, и 128000 CPU cores
• Использует LSTM для каждого героя, без данных от человека, алгоритм вырабатывает сам узнаваемые стратегии
• => Reinforcement learning может создавать долгосрочные цели
• 28 Июля - будет очередной матч с топовой командой, чтобы проверить уровень
• Одна из целей OpenAI - превзойти человека в сложных видеоиграх (StarCraft/Dota2).
• По сравнению с предыдущими целями (Шахматы, Го), сложные видеоигры - уже повторяют хаос и продолжительную структуру реального мира. Поэтому есть надежда, что достижения в видеоиграх помогут в других областях (т.е. получится более генеральное решение)
• ИИ, играющий в Dota2 должен управлять:
  • Долгосрочным планированием: 30rps * 45 min (average) = 80k ticks per game. Отдельный приказ - мало влияет на игру в целом, есть отдельные стратегические приказы, которые сильно воздействуют на игру (town portal). Стратегии могут продолжаться всю игру. Шахматы в среднем 40 ходов, Go - 150
  • Частично-доступным обзором. Видна только часть информации, нужно делать выводы и предполагать, что сейчас делает противник. Chess/Go - видно все
  • Высоко-размерная, длительная область действий игрока: десятки возможных действий, разные цели для действий (башня, персонаж, координата). Они описали область действий - 170к возможных действий (не все активны все время), в среднем ~1k валидных действий каждый тик. В шахматах - 35, в Go 250
  • Огромная область вариантов. Игра описывается 10 игроками, десятки зданий, NPC юнитов, деревьев, руны, … Их модель игры описывает состояние с помощью 20k чисел (в основном, с плавающей точкой)
• Боты учатся только на собственном опыте,
• ожидали, что потребуются ухищрения, чтобы делать долгосрочное планирование (hierarchical reinforcement learning), в целом оказалось, что даже текущие алгоритмы дают хорошее планирование (жертвование краткосрочными целями ради достижения каких-то более стратегических целей)
• Выводы, интересные наблюдения про отличия от человека и т.д.

С - это НЕ низкоуровневый язык

https://queue.acm.org/detail.cfm?id=3212479

• Meltdown, Spectre: спекулятивное выполнение + просмотр результатов через side channel.
• Фичи, необходимые для этого, были добавлены в язык, чтобы люди продолжали думать, что они программируют на низкоуровневом языке
• Low-Level: by “computer science pioneer Alan Perlis”
“A programming language is low level when its programs require attention to the irrelevant.”
• C - был низкоуровневым для PDP-11, где:
  • Программа исполнялась последовательно
  • память была плоским пространством (не иерархическая)
  • и т.д.
• Главная причина уязвимостей - что архитекторы процессора старались построить быстрый процессор, который был подобен PDP-11. Это позволяло программистам верить, что C - близок нижестоящей платформе.
• Си предоставляет в основном последовательную абстрактную машину, создание нового потока - дорогое удовольствие.
• Поэтому производительный код полагается на ILP (instruction-level parallelism): соседние операции проверяются, и независимые выполняются впараллель.
• Чтобы написать по настоящему “последовательный” код - нужно сильно захотеть, и это добавит сложности.
• Квест по достижению высокого ILP - привело непосредственно к Spectre и Meltdown.
• Современные Intel-процессоры имеют вплоть до 180 инструкций “в полете” в любой момент времени. (сравните с последовательной машиной, где следующая инструкция выполняется только после окончания предыдущей)
• Эвристика: ветвление на каждые 7 инструкций, чтобы наполнить работой пайплайн, вы должны предсказать следующие 180/7 ~ 25 переходов. Это опять добавляет сложности
• Неправильное предположение о ветвлении - работу выкинуть, что не очень хорошо для потребления памяти
• И не очень хорошо с точки зрения уязвимостей :)
• Переименователь регистров - потребляет кучу энергии, добавляет сложности, нужно только для реорганизации выполнения, для создания параллелизма из последовательного выполнения (нет на GPU, где все выполняется впараллель)
• Плоская модель памяти - неправда уже на протяжении 20 лет (3 уровня кэша для уменьшения latency)
• Кэш спрятан от программиста, не виден в C. Для эффективной программы - нужно знать, как кэш работает, и как в него поместиться (архитектурно-зависимо)
• ОПТИМИЗАЦИЯ С
• Приписывают скорость low-level языкам
• Несложный компилятор должен уметь транслировать программу в быстрый код
• Вообще, любой язык можно сделать быстрым, достаточно иметь очень хороший компилятор!
• Но для Си не работает эта аксиома: простой компилятор не сделает быстрый код.
• Только сложные оптимизации, только хардкор!
• CLang - 2M LOC
• Пример: обработка большого массива данных - это цикл с пробеганием по одному элементу.
• Чтобы оптимально отработать на современных CPU - компилятор сперва определяет, что итерации независимы (restrict ключевое слово может помочь)
• Если доказал - векторизует результат (4x-8x растет производительность на векторных инструкциях)
• Потом Оптимизатор борется с гарантиями расположения C-памяти (нельзя менять местами поля структуры, добавлять padding, etc). Это свойство низкоуровневого языка, но не свойство быстрого языка, конфликт интересов налицо :)
• сравнение структур по стандарту можно делать с помощью memcpy, поэтому копирование структур делается с копированием padding. В некоторых тестах это занимает значительную часть времени. Опять конфликт интересов
• loop unswitching: оптимизация, когда цикл с условием в теле преобразуется в условие + два цикла по обоим путям условия. Это ускоряет (нет сравнения в цикле), но одновременно расходится с понятием “низкоуровневого языка”, когда ты точно знаешь, что происходит в твоей программе. По сути - мы меняем flow control.
• В итоге, можно заставить код работать быстро, но надо тысячи человеко лет на построение хорошего компилятора. “близкий к металлу” язык, но компилятор генерирует код, который имеет совершенно другое поведение, чтобы заставить работать код “быстро”
• ПОНИМАНИЕ С
• ключевая особенность низкоуровневого языка - программисты легко могут понять, как абстрактная машина языка использует физическую машину.
• это было верно для PDP-11, для современности - это совсем не так
• пример: опрос 2015 года для си-программистов, писателей компиляторов и членов программного комитета. Вопрос: язык позволяет добавлять padding в структуру, чтобы поля были выровнены. Если вы обнуляете структуру и затем устанавливаете некоторые поля - будут ли padding-биты все еще нулями? 36% - были уверены, что да, 29% - не знали. Это зависит от компилятора и уровня оптимизации.
• Это простейший пример, и то большАя часть не знает правильного ответа
• Указатели добавляют сложности:
  • Выделили и освободили память, выделили снова, попали на эту же область. Сравнение указателей дает true?
  • pointer -> cast integer -> cast pointer, сравнение указателей дает true?
  • Везде - зависит от компилятора, даже если побитное сравнение указателей совпадает
• Это не чистая академичность, это попытка защититься от уязвимостей
• Поэтому тяжело ожидать, что все понимают, как на низком уровне работает их программа на си
• ПРЕДСТАВИМ НЕ-С ПРОЦЕССОРЫ
• Meltdown/Spectre заставили внести изменения, которые СИЛЬНО замедляют выполнение всех программ.
• Хватит развивать архитектуру по пути “сделаем код на си быстрым”, и вместо этого понять - какая программная модель должна быть на хорошем быстром процессоре?
• Есть много альтернативных архитектур, которые не создавались для “С-кода”.
  • Sun UltraSPARC Tx серия - не требует много кэша, чтобы заполнить все модули процессора работой. можно замораживать потоки, которые ожидают данных, и выполнять другую работу.
  • ARM SVE (Scalar Vector Extensions) - предоставляют векторные операции, компилятор их должен заполнять. Программист при этом описывает уровень параллелизма. Хорошо подходит функциональный код
  • Самая сложная часть системы памяти - поддержка когерентности кэша. Все из-за программ, где данные одновременно мутабельные и расшаренные. Вместо этого можно рассмотреть модель, где данные либо мутабельны но для одного потока, либо иммутабельны, но общие. Erlang.
  • Иммутабельные объекты могут упростить кэш еще больше. Project Maxwell (Sun Labs). Если данные уже мертвы - их не нужно синхронизировать из кэша в память, можно хитрее работать с GC (generational GC), мутабельные данные - только на стэке, упрощается архитектура
• ВЫВОДЫ:
• Процессор, оптимизированный только на скорость, не на поддержку Си - будет проще, сможет поддерживать большое количество потоков, сможет использовать векторные вычисления шире и т.д. Проблема - не сможет хорошо работать с Си
• Общий миф, что параллельное программирование сложно. Алан Кей смог учить школьников акторной модели. Эрлангисты пишут программы с тысячами потоков. Правильный факт: Параллельное программирование на С-подобной абстракции - это сложно. И то, как машины все больше уходят в параллельность, GPUs, multiCores -> Си плохо ложится на современную архитектуру и будет ложится все хуже