Предотвращение ложного совместного использования индексов очереди SPS C - PullRequest
Новая
       83

Предотвращение ложного совместного использования индексов очереди SPS C

2 голосов
/ 29 апреля 2020

Давайте представим параллельную очередь SPS C (один производитель / один потребитель) без блокировки.

  • Поток производителя читает head, tail, cached_tail и пишет head, cached_tail.
  • Поток потребителя читает head, tail, cached_head и записывает tail, cached head.

Обратите внимание, что cached_tail доступен только потоку производителя, просто Например, cached_head доступен только для потока пользователя. Их можно рассматривать как локальные переменные частного потока, поэтому они не синхронизированы, поэтому не определены как atomi c.

Структура данных очереди следующая: 

#include <atomic>
#include <cstddef>
#include <thread>

struct spsc_queue
{
    /// ...

    // Producer variables
    alignas(std::hardware_destructive_interference_size) std::atomic<size_t> head; // shared
    size_t cached_tail; // non-shared

    // Consumer variables
    alignas(std::hardware_destructive_interference_size) std::atomic<size_t> tail; // shared
    size_t cached_head; // non-shared

    std::byte padding[std::hardware_destructive_interference_size - sizeof(tail) - sizeof(cached_head)];
};

Так как Я хочу избежать ложного совместного использования , я выровнял head и tail по размеру строки кэша L1.

Псевдокод-i sh реализация push / pop Операции следующие: 

bool push(const void* elems, size_t n)
{
    size_t h = atomic_load(head, relaxed);

    if (num_remaining_storage(h, cached_tail) < n)
    {
        cached_tail = atomic_load(tail, acquire);

        if (num_remaining_storage(h, cached_tail) < n)
            return false;
    }

    // write from elems

    atomic_store(head, h + n, release);
    return true;
}

bool pop(void* elems, size_t n)
{
    size_t t = atomic_load(tail, relaxed);

    if (num_stored_elements(cached_head, t) < n)
    {
        cached_head = atomic_load(head, acquire);

        if (num_stored_elements(cached_head, t) < n)
            return false;
    }

    // read to elems

    atomic_store(tail, t + n, release);
    return true;
}

void wait_and_push(const void* elems, size_t n)
{
    size_t h = atomic_load(head, relaxed);

    while (num_remaining_storage(h, cached_tail) < n)
        cached_tail = atomic_load(tail, acquire);

    // write from elems

    atomic_store(head, h + n, release);
}

void wait_and_pop(void* elems, size_t n)
{
    size_t t = atomic_load(tail, relaxed);

    while (num_stored_elements(cached_head, t) < n)
        cached_head = atomic_load(head, acquire);

    // write to elems

    atomic_store(tail, t + n, release);
}

При инициализации (не перечисленной здесь) все индексы установлены на 0. Функции num_remaining_storage и num_stored_elements являются функциями const, выполняющими простые вычисления на основе переданных аргументов и неизменной емкости очереди - они не выполняют ни одного атома c чтения или записи.

Теперь вопрос в : нужно ли также выравнивать cached_tail и cached_head, чтобы полностью избежать ложного разделения любого из индексов, или все в порядке, как есть. Поскольку cached_tail является частным производителем, а cached_head является частным потребителем, я думаю, что cached_tail может находиться в той же строке кэша, что и head (строка кэша производителя), так же, как cached_head в той же строке кэша, что и tail (строка кэша потребителя) без ложного обмена, чтобы когда-либо происходить.

Я что-то упустил?

1 Ответ

2 голосов
/ 30 апреля 2020

Спасибо за предоставление псевдокода - в нем все еще отсутствуют некоторые детали, но, думаю, я понял основную идею c. У вас есть ограниченная очередь SPS C, в которую могут переходить индексы, и вы используете переменную cached_tail в push для проверки наличия свободных слотов, поэтому вы можете избежать загрузки tail из потенциально недействительной строки кэша (и наоборот для pop).

Я бы предложил поместить head и cached_tail рядом друг с другом (то есть в одну и ту же строку кэша), а также tail и cached_head на другой. push всегда читает обе переменные - head и cached_tail, поэтому имеет смысл иметь их близко друг к другу. cached_tail обновляется только в том случае, если свободных слотов больше нет, и нам нужно перезагрузить tail.

Ваш код немного тонок в деталях, но, похоже, есть место для оптимизации: 

bool push(const void* elems, size_t n)
{
    size_t h = atomic_load(head);

    if (num_remaining_storage(h, cached_tail) < n)
    {
        auto t = atomic_load(tail);
        if (t == cached_tail)
          return false;

       // we only have to update our cached_tail if the reloaded value
       // is different - and in this case it is guaranteed that there
       // is a free slot, so we don't have to perform a recheck.
        cached_tail = t;
    }

    // write from elems

    atomic_store(head, h + n);
    return true;
}

Таким образом, cached_tail обновляется только при обновлении head, так что это еще одна причина, по которой они находятся в одной строке кэша. Конечно, такой же вид оптимизации может быть применен и к pop.

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

...