Блог

В настоящее время я пытаюсь представить 2D-массив с помощью tbb::concurrent_vector<T> . К этому 2d-массиву будет обращаться множество разных потоков, и именно поэтому я хочу, чтобы он обрабатывал параллельные обращения максимально эффективно.

Я придумал 2 решения:

• Используйте tbb::concurrent_vector<tbb::concurrent_vector<T> > для его сохранения.

• Храните все в tbb::concurrent_vector<T> и получайте доступ к элементам w/ x * width y

У меня было предпочтение второму, потому что я не хочу блокировать всю строку для доступа к одному элементу (поскольку я предполагаю, что для доступа к элементу array[x][y] реализация tbb заблокирует x -ю строку, а затем y -й элемент).

Я хотел бы знать, какое решение кажется вам лучшим.

Во-первых, я думаю, что может возникнуть некоторая путаница в отношении tbb::concurrent_vector . Этот контейнер похож на std::vector , но с потокобезопасным изменением размера, но с более медленным доступом к элементам из-за расположения внутреннего хранилища.

Вы можете прочитать больше об этом здесь.

В вашем случае, из-за предложенного вами второго решения (1D массив с x * width y индексацией), я предполагаю, что ваш алгоритм не предполагает интенсивного многопоточного изменения размера массива. Следовательно, вы не выиграете от tbb::concurrent_vector сравнения с однопоточным контейнером, подобным std::vector .

Я предполагаю, что вы предполагали, что tbb::concurrent_vector гарантированный потокобезопасный доступ к элементу, но это не так — цитата из tbb::concurrent_vector ::operator[] документа:

Получить ссылку на элемент с заданным индексом.

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

Если вы не изменяете размер массива, вас интересует только первая часть: потокобезопасное одновременное чтение. Но std::vector или даже необработанный массив C дает вам то же самое. С другой стороны, ни один из них не обеспечивает потокобезопасный произвольный доступ (чтение / запись элементов).

Вам придется реализовать это с помощью блокировок или найти другую библиотеку, которая сделает это за вас (возможно std::vector из STLPort, но я не уверен). Хотя это было бы довольно неэффективно, поскольку каждый доступ к элементу из вашего 2D-массива будет связан с затратами на синхронизацию потоков. Хотя я не знаю, что именно вы пытаетесь реализовать, вполне возможно, что синхронизация займет больше времени, чем ваши фактические вычисления.

Теперь, чтобы ответить на ваш вопрос, даже в однопоточной настройке всегда лучше использовать 1D-массив для представления ND-массивов, потому что вычисление индекса (x * width y) выполняется быстрее, чем требуется дополнительный доступ к памяти для истинного ND-массива. Для параллельных векторов это еще более верно, потому что в лучшем случае у вас будет вдвое больше накладных расходов на блокировку (без конфликтующего доступа к строке) и намного больше в случае возникновения конфликтов.

Итак, из двух предложенных вами решений я бы, не колеблясь, выбрал второе: 1D массив (не обязательно tbb::concurrent_vector ) с адекватной блокировкой для доступа к элементам.

В зависимости от вашего алгоритма и шаблона доступа различными потоками, другой подход, используемый в программах для редактирования изображений (gimp, photoshop …), основан на плитке:

 template<typename T> struct Tile {
    int offsetX, int offsetY;
    int width, height;
    Not_ThreadSafe_Vector<T> data;
};
ThreadSafe_Vector< Tile<T> > data
  

Где Not_ThreadSafe_Vector может быть любой контейнер без блокировки доступа к элементу, например, std::vector ; и ThreadSafe_Vector является контейнером с потокобезопасным доступом к элементу чтения / записи (не tbb::concurrent_vector !).
Таким образом, если у вас есть некоторая локальность в вашем шаблоне доступа (поток, скорее всего, получит доступ к элементу, близкому к его предыдущему доступу, чем удаленному), тогда каждый поток можно заставить большую часть времени работать с данными из одного тайла, и у вас будут накладные расходы на синхронизацию только при переключении на другой тайл.

tbb::concurrent_vector полностью потокобезопасен для доступа к элементам (чтение, запись, получение адреса) и увеличения вектора. Проверьте ответ от сотрудника Intel Арча Д. Робисона здесь.

Однако операции по очистке или уничтожению вектора не являются потокобезопасными (см. PDF-документ Intel TBB Tutorial от $ 6.2.1). То есть не вызывать, clear() если на tbb::concurrent_vector выполняются другие операции.

Как упоминал Антуан, обработка ND-массива как 1D-массива всегда предпочтительнее из-за эффективности и производительности.