Безопасная работа с памятью в OpenMP С++

[IakovA]

Добрый день.
Вопрос связан с тем как можно добавлять элементы к общему динамическому массиву в параллельных потоках.
По сути задачи приходится к созданному многомерному vector добавлять новые элементы.
Пусть есть, например, vector<vector<int>> A. Первая размерность уже проинициализрована полностью (например, 0-N-1). Есть гарантия, что внутри потоков происходит обращение к собственному набору индексов первой размерности. То есть, разные потоки не могут обращаться к одному и тому же первому индексу.
Однако заранее определить размерность второго индекса для каждого первого индекса невозможно (вычисляется внутри цикла по первому индексу).
Можно конечно взять максимально возможную оценку, но тогда никакой памяти не хватит (Сотни гигабайт). В результате пользуюсь операторами типа A[i].push_back(k) в каждый момент, когда необходимо добавить элемент (В реальности массив четырехмерный, причем основной добавляемый элемент - Structure)
Тем не менее необходимо распараллеливание (счет идет более суток).
Попробовал использовать простейшие варианты из OpenMP типа #pragma omp parallel for, однако во время работы выдает всякие ошибки так или иначе связанные с памятью.
Может ли кто-нибудь подсказать, как все-таки добавлять память внутри потоков, при этом получая выигрыш во времени счета при распараллеливании.

[waleri]

Защитить обращения к std::vector через mutex.
Использовать свой std::vector в каждом потоке и в конце объединить их.
Использовать что-то другое, вместо std::vector. Например вставка в std::list гораздо быстрее.
Использовать lock-free алгоритмы.

[IakovA]

Спасибо за ответ.
1. Если использовать mutex на каждое добавление, то все потоки будут ждать друг-друга и вряд ли я получу выигрыш от распараллеливания
2. Идея использовать в каждом потоке свой вектор - хорошая. Но тогда мне нужно точно знать, на сколько частей и как бьется цикл, который хочу распараллелить. Я предполагал, что это будет делаться динамически. У меня 64 потока и для каждого заводить здоровущий трехмерный массив... Правда наверное можно действительно завести скажем 30 трехмерных массивов. За тем сохранить их адреса в одномерный массив и по номеру потока вытягивать нужный мне адрес и потом с ним работать. Так прокатит?
3. Это интересно. А list поддерживает прямую адресацию элементов? Собственно я именно поэтому использовал vector, чтобы каждый раз не бегать по массиву и искать то, что мне нужно
4. Это конечно правильно ), я бы и рад, но что-то ничего другое в голову не приходит, когда нужно найти ВСЕ, скажем, четырехплечевые маршруты в графе изо всех вершин во все вершины

[waleri]

1. Только если все потоки будут добавлять одновременно. Предполагается, что они занимаются и другими вещами.
По 2 и 3 - я не знаю что вам надо, в смысле надо бегать по массиву или нет, нужен ли вам именно трехмерный массив и т.д. Если надо часто бегать и искать, тогда можно подумать о std::set или std::map.

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