Параллельные механизмы выделения памяти

Создать новую статью

23.11.2009 13:00


При распараллеливании приложений на С/С++ часто оказывается, что функция malloc() (или new) является узким местом, ограничивающим максимальную производительность приложения. В данной статье объясняются четыре основные проблемы, которые может решить хороший параллельный механизм выделения памяти:

  1. Потокобезопасность
  2. Дополнительные издержки (Overhead)
  3. Соревновательность
  4. Дрейф памяти

Потокобезопасность

Базовые механизмы выделения памяти (storage allocators) не являются потокобезопасными, хотя в результате недавних усилий разработчиков данная проблема решается для многих параллельных платформ. В двух словах, из-за гонок во внутренних структурах данных механизма выделения памяти возникает вероятность неправильного поведения программы, когда два потока одновременно пытаются занять или освободить память. Если потоки имеют неограниченный доступ к механизму распределения памяти, как показано ниже, то они начинают «наступать друг другу на пятки», что приводит к ненормальному поведению системы.

Простым решением данной проблемы является применение мьютексной блокировки (mutex, mutual exclusion, взаимное исключение) к аллокатору перед вызовом malloc() или free(), что позволяет только одному потоку получить доступ к внутренним структурам данных механизма выделения памяти за раз.

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

Издержки и соревнование

У потокобезопасных механизмов выделения памяти с использованием блокировок возможны две проблемы: во-первых, выделение и освобождение памяти могут замедляться вследствие дополнительных издержек на установку блокировки. Во-вторых, при доступе к аллокатору может возникнуть соревнование, что приводит к замедлению работы приложения и ограничению его масштабируемости. Соревнование само по себе  не является большой проблемой при 2 или 4 ядрах, но, по закону Мура, скоро можно ожидать десятков и даже сотен ядер в одном процессоре, и тогда «соревновательность» может сильно подкосить масштабируемость.

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

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

Дрейф памяти

К сожалению, использование локальных потоков создает другую проблему, особенно на платформах, в которых память активно распределяется между потоками, или в которых происходит активное перераспределение вычислительной нагрузки между потоками. Представим, что поток А постоянно требует выделения  памяти в своем локальном пуле и затем передает полученную память потоку Б, который использует ее в своем локальном пуле. Когда пул потока А истощается, он запрашивает дополнительную память из глобального пула. Эта память снова передается потоку Б, и он опять же использует ее в своем локальном пуле. С течением времени локальный пул памяти потока Б неограниченно разрастается, создавая что-то вроде утечки памяти, при которой объем виртуальной памяти приложения все время растет.

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

Выводы

Существуют и другие проблемы, возникающие в параллельных механизмах выделения памяти. Например, ложное общее использование памяти (false sharing) является особенно разрушительным состоянием, при котором два потока обращаются к независимым блокам памяти, которые случайно оказываются на одной и той же линии кэша, что ведет к перегрузке протокола когерентности кэша в процессоре. Аллокатор памяти, не уделяющий должного внимания границам линий кэша и раздающий разным потокам блоки памяти, лежащие на одной линии, может вызывать ложное разделение, которое трудно отловить, поскольку логика кода говорит, что потоки обращаются к независимым блокам памяти.

Можно привести два примера параллельных отводчиков памяти – это Hoard, написанный Эмери Бергером (Emery Berger) из университета Массачусетса, и Miser, распространяемый Cilk Arts как часть пакета Cilk++.

Дополнительные ресурсы по Cilk++

Данная статья является переводом блога Чарльза Лизерсона (Charles Leiserson).
Оригинал доступен по адресу http://www.cilk.com/multicore-blog/bid/7904/Multicore-Storage-Allocation.