Наверх ▲

Квадратный стол по вопросам использования многоядерных ЦП с участием представителей Google, Intel, Яндекс и Rambler

Андрей Гулин Андрей Гулин Ведущий разработчик в Яндекс. Константин Замков Константин Замков Специалист по корпоративным технологиям в компании Intel.

Наша практика в Google показывает, что потоки неизбежны. Можно их считать злом, но от него никуда не денешься. У нас даже на многих настольных системах 8 или 16 ядер, не говоря уже о серверной части.

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

Мы, естественно, используем и то, и другое. Тем не менее, приходится иметь дело с потоками.

Что мы делаем с потоками? В первую очередь, боремся за корректность работы многопоточных программ. Две наиболее распространенные проблемы, связанные с корректностью, – это взаимная блокировка (англ. deadlock) и состояние гонки (англ. races).

С проблемой взаимной блокировки мы боремся по-разному. У нас есть собственная реализация мьютекс (англ. mutex) в серверной части Google, куда встроен соответствующий детектор. Блокировки отлавливаются не в тот момент, когда они произошли, а когда они потенциально возможны. Кроме того, в C++ для поиска используется статический анализ. В Java мы используем свой собственный детектор среды выполнения (англ. run-time detector).

Что касается состояния гонки, то для решения этой проблемы у нас есть собственный инструмент ThreadSanitizer. Это инструмент среды выполнения, который обнаруживает возможные гонки. Он работает на всех трех операционных системах, которые мы используем и располагается в открытом доступе.

То же самое мы разрабатываем для Java и скоро выпустим нечто вроде бета-версии.

Кроме вопросов корректности, у нас часто возникает вопрос производительности. Если неаккуратно писать многопоточную программу, то она будет медленнее, чем однопоточная.

Почему это происходит? Во-первых, разные потоки могут излишне расходовать некоторые ресурсы. Например, самый простой случай – это мьютекс, который пытаются использовать сразу все (конфликт на шине).

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

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

Перейдем к вопросу о профилировании вообще, что имеет отношение не только к потокам. У нас вопрос преимущества решается при помощи PMU (Performance Monitoring Utility). Это необходимо для поддержки выделенного процесса. Мы используем три разных инструмента (все являются открытым программным обеспечением). OProfile, perfmon и Google Performance Tools (GPT) - такая библиотека, которая находится в программе С++).

Я примерно обрисовал, какие в Google есть проблемы и как мы с ними боремся. Хотелось бы посмотреть, послушать, что скажут коллеги. Спасибо.

Андрей Гулин: Я буду рассказывать о Lockfree и NUMA и затрону два частных аспекта общей проблемы использования CPU.

Чтобы на многоядерных процессорах все быстро работало, нам нужно решить две проблемы. Загрузить каждое ядро некой полезной работой и сделать так, чтобы ядра не "дрались" между собой, когда они хотят записать данные в одном и то же месте, например, одну и ту же переменную в одну структуру данных.

У нас есть выбор. Мы можем запускать их при помощи разных процессов. С одной стороны, это проще, но нам все равно нужно иметь какие-то общие данные для разных процессов. Мы можем сделать это с помощью потоков и сэкономить на этом.

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

Либо мы можем перейти на уровень ниже и использовать атомарные инструкции. Тогда лок сохранится на единственную инструкцию, которая прочтет из памяти значение, производет требуемую операцию и запишет обратно.

В будущем нам обещают не одиночные атомарные инструкции, а целые серии инструкций, называемые транзакционной памятью.

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

Что такое неблокирующие алгоритмы? Цитата из Википедии: «Неблокирующий алгоритм – это алгоритм, который позволяет системе двигаться вперед в ситуации, когда один или несколько потоков "подвисли" по какой-то причине..." Есть разные уровни совершенствования неблокирующих алгоритмов.

Алгоритмы без блокировок (lock-free). Гарантируется, что в целом система может какое-то время продвигаться вперед. Несколько потоков у нас приостановились, но оставшиеся будут работать дальше.

Более сильная гарантия – без ожиданий (wait-free). Оно предоставляется каждому потоку, который за фиксированное количество шагов алгоритма будет продвигаться вперед.

Самый простой пример алгоритма без блокировок (lock-free) – это атомарные счетчики (atomic counters). Можно бесплатно суммировать статистику без использования лока и обойтись без мьютексов и всем, что с ними связано.

Также было доказано, что любой алгоритм можно сделать без блокировок (lock-free). С помощью атомарной инструкции CompareAndSwap можно реализовать любой алгоритм в варианте lock-free.

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

С алгоритмом без блокировок связана проблема, которая имеет название ABA. Когда мы используем структуру в качестве состояния, то в операции ControleAndSwap используется указатель на эту структуру в качестве ее уникального идентификатора. Но из-за повторного использования памяти (мы освободили блок – он может быть повторно использован), свойств уникальности идентификатора, указателя, на самом деле, нет.

Возникает так называемая проблема ABA. Ее можно обойти при помощи способа, который был изобретен в 1996 году. Способ заключается в том, что к указателю мы добавляем счетчик. Так как счетчик всегда уникальный, то проблемы у нас нет. Можно сделать по-другому. Если интересно, могу рассказать подробно.

В исходнике основных Lockfree primitives: Stack, Queue и Hashmap.

Как мы используем алгоритмы без блокировок (lockfree), я рассказал. В распределительных задачах у нас используется lockfree вычислительных задач. Это позволяет увеличить скорость на 3-5%. Выигрыш, естественно, растет с увеличением количества ядер. Как известно, все следующие процессоры будут иметь все больше и больше ядер, поэтому выигрыш будут увеличиваться.

На самом деле, за 3-5% не стоило бы бороться, но выигрыш намного больше. Когда мы используем распределенные вычисления и считаем не на одном процессоре, а на ста, вероятность того, что кто-то уйдет в своп или по какой-то другой причине решит, что нужный поток должен быть отправлен в своп, вероятность того, что кто-нибудь зависнет из-за мьютекса, гораздо выше.

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

Поэтому выигрыш из 3-5% увеличивается в несколько десятков раз.

Самое популярное место для мьютекс – это распределитель памяти (memory allocator). В большинстве случаев мьютекс можно оттуда убрать и сделать так, чтобы он реально использовал два текста. В случае использования тех же самых алгоритмов без блокировки stack и очереди (qeues) для передачи памяти из потока в поток. Внутри потоков можно сделать локально.

Такой распределитель был тоже написан, он используется, но, к сожалению, он пока не является открытым программным обеспечением. Как правило, выигрыш от него по сравнению со свободным программны обеспечением составляет порядка 1%, в отдельных случаях – больше. Но эта программа описана неопытно. Когда из разных потоков пытаются проводить распределение, то происходит коллапс.

Когда мы пишем алгоритмы без блокировок, очень легко допустить ошибку, которая заключается в следующем. На самом деле, C++ не гарантирует порядка, в котором мы будем генерировать код. Мы пишем: A=0, B=0, но это вовсе не означает, что инструкции будут выполнены в названном порядке. Такое гарантируется только для изменчивых (volatile) переменных.

Visual C, по-моему, в этом отношении предоставляет более надежную гарантию. Соответственно, запись изменчивой переменной является барьером.

Юридически нас могла бы спасти конструкция asm volatile. Но, к сожалению, как минимум для gcc 4.2 она иногда не работает.

Дальше я хотел бы рассказать о PThread API. Он тоже приспособлен для программирования без блокировок в силу того, что в нем отсутствует примитив всех потоков без блокировки.

Существует способ, в названии которого, по-моему, фигурирует слово "broadcast". Но проблема в том, что каждый поток, "просыпаясь", получает заблокированный мьютекс. Таким образом, два потока одновременно "проснуться" не могут. Это очень неудобно. Мы нашли решение для FreeBSD, которое обслуживает другие функции, но в общем случае PThread API можно повторить.

Напоследок я хочу рассказать о NUMA. Как известно, у многих процессоров последних моделей имеется своя локальная память и доступ к памяти соседнего процессора. Их пропускная способность отличается очень сильно. Своя память работает в 3 раза быстрее.

Это можно и нужно использовать. Нам нужно, чтобы каждый поток более или менее работал на одном и том же ядре и использовал память, которая взаимодействует с его сокетами.

Это легко сделать. По умолчанию любая операционная система при вызове или аналогичных действиях распределяет в сокетах память. Таким образом, если вы передаете память от одного потока другому (например, через распределитель памяти), вы автоматически получаете желаемый результат.

Соответственно, для программы, которая здесь обозначена символом "P", занимает 90% поисковых серверов. Выигрыш от использования данного споособа составил около 2%.

Вопросы:

Вопрос из зала:
Добрый день. Александр Азимов. У меня вопрос по последнему слайду. Что здесь имеется в виду? NUMA бывают разные. Бывают когерентные, бывают нет. Что используется у вас?
Андрей Гулин:
Я не очень понял вопрос. NUMA – когерентная она или нет – это уровень (неразборчиво). Мы рассматриваем такой феномен. У нас есть (неразборчиво), что на ней стоит шина, которая между процессорами. Мы знаем, если запустить специальный тест и посчитать, что локальная память работает быстрее. Как именно это происходит, нас не очень интересует. Здесь написано, что на наших серверах она уже давно есть, можно получить выигрыш от ее использования. Как именно его сделать – очень просто. Достаточно память, которую мы выделяем, сохранять у сокетов.
Вопрос из зала:
Я поясню вопрос. Если NUMA когерентная, это дополнительные расходы. 2% - это никакого выигрыша. Соответственно, это с поддержкой когерентности оперативной памяти или без нее.
Андрей Гулин:
Термин когерентность я не очень понимаю в этом смысле.
Вопрос из зала:
Расскажите о способностях локальной копии и той, которая находится на возможной другой машине.
Андрей Гулин:
В смысле, на другой машине? Это одна и та же машина, просто двухпроцессорная. Для нее гарантируется, что все будет когерентно. Некогерентные на Intel вряд ли существуют.
Константин Замков:
Коллеги! Меня зовут Константин Замков. Я являюсь специалистом по корпоративным технологиям компании Intel. Я не буду показывать никаких слайдов. Должен поблагодарить выступающих от Яндекс и Google. Я был также на предыдущей сессии, на выступлении ВКонтакте, мне было очень интересно.
Надеюсь, вы все довольны нашей текущей линейкой продуктов процессора Minihalem. Все довольны? 
Могу сказать, очень скоро у нас будет новая микроархитектура, которая, как вы, наверное, слышали, носит кодовое название Sandy Brish. Там будет масса новинок. Тогда, я уверен, все останутся довольны, даже мой тезка из компании Google.
Сейчас можно переходить к другим вопросам нашего стола.
Игорь:
Я хочу поделиться своим видением того, как надо использовать многоядерный процессоры. Это неизбежное будущее. Частоту ускорить мы не можем. Будет увеличиваться число «корок».
На мой взгляд, использовать PThread нельзя. Этот стандарт разрабатывался лет 20 назад SAN, DEK – их уже нет. На мой взгляд, лучше не использовать Thread вообще. Использовать много ядер, начинать много процессов. Single Thread процессор и раскидывать все это.
Нужно пытаться как-то кэшировать свои данные, кэшировать соединения, пользователей. Когда вы будете раскидывать все это по отдельным процессам, работает, когда вы раскидываете на разные машины. Если данные пользователи минимально взаимосвязаны, то это как раз работает. Получается хорошая масштабируемость.
Если же жизнь заставляет вас использовать потоки выполнения в одном приложении, то нужно пытаться не использовать PThreads, а смотреть на современные библиотеки, которые позволяют скрыть PThread.
Один из таких вариантов – это lib-dispatch, которую недавно разработал Apple в рамках платформы Grand Central Dispatch. Она портирована на FreeBSD, вроде бы портируется на Linux. У этой библиотеки есть определенные недостатки. Она не масштабируется на тысячу соединений. Но если вам нужно добавить просто какую-то параллельность в свое приложение, то имеет смысл рассматривать этот вариант.
Это библиотека, которая ставит потоки в очереди. Вы работаете с очередями, при этом не видите ни одного системного вызова PThreads, но, естественно, все это построено внутри PThread. Все это от нас спрятано. Там тоже, конечно, есть подводные камни, но программировать гораздо проще. Вы не видите мьютексов, семафоров и прочего. Вы видите только очереди.
На эти очереди достаточно хорошо "ложатся" очень многие задачи. Мой совет – не используйте PThreads.
Вопрос из зала:
С многоядерностью все более или менее понятно. Но мне было бы интересно узнать, есть ли опыт использования GPU в ваших компаниях. Если есть, то какой? Если нет, то почему? Какие вообще перспективы у GPU в области веб-приложений?
Мужской голос:
Ответ от Google очень простой – я не в курсе.
Игорь:
Я этой проблемой интересовался только теоретически. Я смотрел текущие API, NVidia, CUDA. На мой взгляд, сам интерфейс очень тяжелый. Пока ты дойдешь до смысла задачи, придется сделать много непонятно чего. Это с одной стороны. С другой стороны, это очень специфичная задача. Я, честно говоря, не знаю, для чего можно использовать CUDA. На мой взгляд, это достаточно специфичные вещи. Они подходят для определенного класса задач. Безусловно, такие задачи есть. Для них это все очень быстро работает. 
Андрей Гулин:
Мы пробовали использовать CUDA несколькими способами. В частности, самый многообещающий способ – попытка посчитать ранжирующую функцию. Теоретически она смогла бы нас спасти. Но выяснилось, что с ней связано много неприятных особенностей. В частности, присутствует глобальная синхронизация и нет параллельных запросов. Мы должны все сериализовать, посчитать и получить ответ.
Позднее выяснилось, что стоимость передачи данных на этой CUDA сопоставима со стоимостью расчета ранжирующей функции. Делать ее более сложной для того, чтобы использовать CUDA, смысла особого не было. Поэтому мы решили, что пусть она подождет, пока не переедет поближе к процессору.
Есть и другие способы использования CUDA. Вся проблема в том, что на этой CUDA размещается очень мало памяти (наверное, 1 гигабайт). Такие объёмы уже не интересны. Когда у вас меньше одного гигабайта, на обычных процессорах все быстро работает. Тем более, что у нас компьютеров с данными много. Нам проще использвать сотню компьютеров и произвести быстрый подсчет, чем задействовать CUDA и получить небольшой выигрыш.
На самом деле сообщения о стократных ускорениях неоднозначны.
Вопрос из зала:
Как вам кажется, насколько вероятно, что лет через 5 следующий процессор Intel будет очень сильно похож на CL от IBM?
Константин Замков:
Я скажу еще два слова насчет CUDA и GPU. Мне кажется, тема очень интересная. Игорь правильно сказал, что разработка под GPU крайне специфическая и требует много человеческих ресурсов. Коллеги подсказывают, что, действительно, Intel делает не GPU, но сейчас работает (может быть, вы слышали) над прототипом ускорителей, которые будут иметь десятки ядер. Но ядер x86, что существенно.
С точки зрения аннотации кода, если он изначально подразумевает эффективное распараллеливание, вам нужно будет добавить в C пару строчек и прагма-код. Ваш код распараллеливается без дополнительных усилий. Может быть, потребуется оптимизация, но не существенная.
Что касается аналогии с CL. Наверное, я не обладаю настолько широким кругозором, поэтому не возьмусь давать свои комментарии. Мне кажется, что ноу-хау достаточно разные в плане того, как IBM развивает CL, а ntel - x86. Однозначного ответа дать нельзя.
Вопрос из зала:
Меня зовут Артем. Вопрос к Intel. Раз вы уже начали говорить про PThreads, то позвольте мне задать вопрос. Около трех лет назад Intel анонсировал технологию под названием Threading Building Blocs. Вы можете рассказать, как ее используют?
Константин Замков:
К сожалению, не могу, поскольку я напрямую разработкой не занимаюсь. Но, действительно, такая технология есть. Она используется в ряде продуктов Intel, связаны не с силиконом, а с инструментарием для разработчиков: компиляторами, технологией Thread Evaliser и прочим. Но об использовании судить не возьмусь, т.к. просто владею информацией.
Вопрос из зала:
Multi CPU против Multi Core – оправданы ли трудозатраты? Оптимизация, избежание пинг-понгов и пр.
Мужской голос:
Вы имеете в виду Multi Core на одном чипе или много CPU на одной машине? Практически во всех машинах, которые у нас есть, много CPU, в каждом CPU много Core, в каждом Core есть PThreading.
Вопрос из зала:
Вы считаете, что человеческие трудозатраты на автоматизацию приложения целесообразны?
Мужской голос:
Я бы так сказал. Сколько ядер даст на Intel, столько мы и загрузим.
Константин Замков:
Мы еще добавим.
Вопрос из зала:
Конкретно о SAN. Они подтверждают, что сборщик мусора не может утилизировать больше 8 Гб. 
Игорь:
Я могу прокомментировать, из-за чего возникают эти проблемы. Проблемы вообще с тем, что архитектура Intel плохо приспособлена для многоядерностьи (точнее, для многопроцессорности). Дело в том, что архитектуру Windows постарались сделать для программистов попроще.
Понимаете, это как язык высокого уровня. На Perl, PHP, Python производится сортировка массивов. При этом вы не подозреваете, что происходит в самом процессоре. А происходят в нем кошмарные вещи. Люди удивляются: почему так медленно? Если спуститься на уровень ниже и запрограммировать по-другому, скорость увеличится.
Примерно то же самое происходит в процессорах. Intel сделал архитектуру, на которой программисту достаточно просто программировать. Память когерентна практически всегда. Ему не нужно думать о том, что «мы тут что-то изменили, а теперь надо сообщить другим процессорам о том, что мы изменили эту ячейку памяти». Эту работу за вас сделает процессор.
Есть архитектуры, на которых нужно специально об этом думать. С такой архитектурой программировать сложнее. Но они легче параллелятся. Например, у PC от IBM атомарные директивы устроены немного по-другому (не как у Intel). Они лучше параллелятся, но с ними сложнее программировать.
Мне кажется, что одно из решений этой проблемы – разместить побольше Core в одном ядре. Я не могу говорить как специалист, это просто мое мнение. Когда у вас два процессора в разных сокетах, то накладные расходы на синхронизацию, на мой взгляд, должны быть больше, чем если бы в одном процессоре было 50 Core. Они используют разделяемый кэш. На мой взгляд, нужно сделать более быструю синхронизацию. Все это должно масштабироваться гораздо лучше.
Проблема в том, что должна быть атомарная инструкция, о которых рассказывал Андрей. Они тоже недешевые. Все атомарные инструкции блокируют шину, валидируют кэши на других «корках». Из-за этого возникает много расходов.
В начале октября проходила одна конференция, на которой был зачитан очень хороший доклад от MIT. Они масштабировали Linux на 48 ядер и приложения (в частности, Apache, Memcached, Postgres).

Комментарии

Нет ни одного комментария

Только пользователи могут оставлять комментарии

Возможно, вам будет интересно:

Роберт Вирдинг (Robert Virding)

Роберт Вирдинг (Robert Virding)

Главный специалист по языкам программирования в Erlang Solutions Ltd.

Роберт Вирдинг (Erlang Solutions Ltd.) рассказывает о том, как выглядит реализация Erlang изнутри и почему она масштабируется.

Евгений Эльцин

Евгений Эльцин

Разработчик ПО в Google.

Евгений Эльцин (Google) рассказывает об исполнении нативного кода в браузере посредством использования Native Client.

Роберт Трит (Robert Treat)

Роберт Трит (Robert Treat)

Возглавляет группу по работе с базами данных в компании OmniTI.

Роберт Трит (OMNTI) рассказывает о проблеме "раздувания" данных в Postgres.