Искать в массиве с несколькими потоками, не выполняя больше дополнительной работы, чем необходимо

Question

Предположим, у вас есть большой несортированный массив длины n, который вы хотите найти, чтобы найти конкретный элемент (пусть элементы этого массива будут уникальными).Поскольку в худшем случае вам придется обязательно искать элемент по всему массиву, время выполнения будет O (n).Однако, поскольку большинство процессоров в настоящее время поддерживают несколько ядер (с гиперпоточностью), для ускорения поиска в массиве можно выполнять поиск по нескольким потокам.Таким образом, с m ядрами в вашем распоряжении будет 2 миллиона (независимых) потоков.Если бы вы делегировали только часть массива каждому потоку, т.е. дали каждому из потоков 2m n / 2m элементов массива для обработки, это было бы оптимально.Однако, когда один из потоков 2m находит элемент, другие потоки необходимо остановить (для сохранения системных ресурсов), поскольку все элементы уникальны, а другие потоки никогда не найдут элемент.

Поэтому мой вопросэто: Как вы будете искать в большом несортированном массиве с уникальными элементами с потоками 2 м, сводя к минимуму работу ваших потоков и время выполнения?Какие синхронизированные структуры данных вам понадобятся?Как остановить другие потоки 2m - 1, когда элемент найден?

Answer 1

Вероятно, самым простым способом было бы иметь атомно-логическое значение (std::atomic<bool> на C ++ - говорят) и иметь поток, который находит выходное значение, которое имеет логическое значение true перед выходом.

В дополнение кчто каждый поток делит свою часть массива на части, так что он может сделать замкнутый цикл, ища число в каждой части, затем проверить атомно-логическое значение, а затем повторять, пока не закончитсяподразделы для проверки.(Причина использования частей вместо простой проверки atomic-boolean после каждой итерации одного большого цикла for заключается в том, что даже проверка atomic-boolean будет довольно дорогой из-за проблем с когерентностью кэша, поэтому лучше амортизировать каждуюatomic-boolean-check для большего количества итераций и обменивают немного дополнительной / потраченной впустую работы в обмен на лучший параллелизм)

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