LINUX.ORG.RU

Многопоточный поиск пути

 , ,


1

3

Умные люди, помогите, пожалуйста, с алгоритмом:

  • Имеем 7 измерений, по которым можно двигаться, с шагом в 1.
  • Одномоментно можно пройти только по одному измерению.
  • При переходе надо сделать расчет можем ли мы здесь находиться, если можно, ок, идем дальше, нельзя - по этому пути прохода нет.
  • Начальные условия задаются при старте, как далеко можно зайти зависит только от начальных условий

Хочу узнать как далеко можно зайти. Если делать в один поток, то вырисовывается простая рекурсивная функция, которая рано или поздно все обойдет.
Думал как можно распараллелить сие, пока что пришел к мысли хранить контейнер с мьютексом для хранения уже пройденных состояний. При переходе проверять наличие исследуемого элемента в контейнере. Если его нет, тут же добавлять его в контейнер, чтобы другие потоки не делали дублирующую работу.
Вопрос собственно в том, а не фигню ли я придумал?
Интересует есть ли более быстрые/простые способы запускать от 1 до N потоков, чтобы они не делали лишную работу и не мешались друг другу


Прежде чем что-то параллелить, попробуй просто запилить нормальный алгоритм поиска пути, хотя бы простейший вариант A*. Твоя «простая рекурсивная функция» называется поиском в глубину, и это далеко не самый лучший способ это делать.

Gvidon ★★★★
()

Интересует есть ли более быстрые/простые способы запускать от 1 до N потоков, чтобы они не делали лишную работу и не мешались друг другу

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

Отслеживать, что вся очередь обработана можно счётчиком. Каждый обработанный элемент - +1.

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

Если нужно делать много поисков одновременно, то делаешь, например, очередь очередей.

Ivan_qrt ★★★★★
()

Обычный обход, например, дерева, таков: берём очередь, добавляем туда начальную вершину, запускаем на ней пул потоков, поток берёт вершину из очереди и начинает её обходить, на развилках идёт по одной ветке, другие добавляет в очередь. Возьми его и модифицируй для своего случая.

Если у тебя бывают циклы, значит дополнительно нужно проверять чтобы потоки не ходили по одним и тем же путям. Тут будет трейдофф «потоки делают одно и ту же работу» vs. «оверхед на синхронизацию», есть широкое поле для экспериментов. Скажем, раз в N вершин потокам нужно будет полностью синхронизировать глобальное состояние (т.е. смержить данные о проходимости и посещённых вершинах, прекратив те потоки которые находятся внутри посещённой территории). Эффективность этого можно улучшить статистически, заставляя потоки предпочитать разные направления обхода чтобы меньше сталкиваться.

Другой подход - разделить пространство на сетку с более крупными ячейками, для каждой ячейки своя очередь и свой поток. Здесь может страдать параллельность (если лабиринт мало ветвится то будет работать мало потоков), зато не нужно согласовывать глобальное состояние и оверхед на синхронизацию минимальный (по мьютексу на ячейку это весьма fine-grained → минимум контеншона). Опять же, могут помочь эвристики - внутри ячейки нужно предпочитать направления ведущие к неизведанным стенам, чтобы скорее найти путь до них и запустить поток соседней ячейки.

А так гугли параллельный обход графа, я это на коленке придумал, а наверняка есть более монументальные труды.

slovazap ★★★★★
()
Ответ на: комментарий от Gvidon

нормальный алгоритм поиска пути

Не описан критерий «нормальности». Может быть это поиск кратчайшего пути, или сложность поиска (по времени, по памяти и др ресурсов), или чего нибудь другого. Если поиск кратчайшего пути, то его можно распараллелить по слоям. А вот поиск в глубину практически невозможно (А* как частный случай).

anonymous
()
Ответ на: комментарий от Gvidon

Может быть я не достаточно точно донес мысль, но A* и Дейкстра мне не подходят.
Вершин графа еще нету, они будут сгенерированы в зависимости от начального состояния. Т.е. цель не пройтись по графу от А до Б, а сгенерировать граф целиком и узнать как далеко он распространяется. Чем лучше начальные условия, тем больше будет граф.

ia666
() автор топика
Ответ на: комментарий от Ivan_qrt

Спасибо за мысль, заинтересовало. Диву даюсь, что сам не допер. Плюс можно регулировать количество обработчиков, что неплохо. Насчет счетчика - CAS'ы вроде есть для этого и std::atomic подходит для этого.

ia666
() автор топика

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

OxiD ★★★★
()
Ответ на: комментарий от OxiD

Но вообще если у тебя случай почти непрерывного пространства, то там есть свои алгоритмы типа rrt деревьев, возможно есть параллельные

OxiD ★★★★
()
Ответ на: комментарий от OxiD

Вообще может все не так, и тебе нужен обычный dfs однопоточный, но вершины заранее препроцессить во много потоков?

OxiD ★★★★
()

Это давно всё реализовано. Посмотри как работают современные рендереры. Luxrender, например, или ещё какой.

Там обрабатываются пути прохода фотонов и в камеру от источника света и из камеры в источник света и т.п.

anonymous
()

Ищи в нете - волновой алгоритм. Хотя вообще это графы.

HIS
()
Ответ на: комментарий от Ivan_qrt

Создаёшь на старте пул потоков

Допустим. И сколько потоков?

Если нужно делать много поисков одновременно, то делаешь, например, очередь очередей.

Это не эффективно.

HIS
()

Вобщем для задачи нужно использовать волновой алгоритм по теории графов.

Далее создаём количество потоков не большее чем количество аппаратных вычислительных потоков на компьютере (или там гетерогенной системе вычисления).

Каждый проход вычисляет следующий шаг +1 для каждой вычислительной единице.

HIS
()

Муравьиный алгоритм предлагали уже?

anonymous
()
Ответ на: комментарий от HIS

Допустим. И сколько потоков?

По кол-ву ядер. Лучше дать возможность задавать настройками пользователю.

Это не эффективно.

Чем неэффективно?

Ivan_qrt ★★★★★
()
Ответ на: комментарий от Ivan_qrt

Чем неэффективно?

Если по количеству ядер - всё ок.

В начале небыло обозначено просто.

HIS
()

Всем большое спасибо, остановился на такой схеме:

  • Есть очередь состояний, которые нужно просчитать, можно ли из него пройти дальше по любому направлению.
  • Если пройти можно, для каждого следующего состояния кидается задача в очередь
  • Пул потоков по кол-ву ядер(хотя тут можно регулировать) будет разбирать очередь(по порядку или случайным образом как в rrt) и тем самым порождать новые задачи.
    Когда задачи иссякнут - мы закончили
  • Дублирование работы не будет, все тяжелые расчеты будут производиться 1 раз, а дальше будет проверка, обсчитано данное состояние или нет.

На выходе получится как раз граф, по коротому уже можно искать пути как душе угодно.
Не совсем ясно, что делать когда очередь разрастется и займет всю оперативку. Пока что единственно разумный вариант это подключить базу данных, к примеру sqlite\mysql\postgres и хранить очередь там, как и результаты обработки, но это заметно скажется на производительности я думаю.

Кто нибудь в курсе, есть ли смысл в postgres\mysql или sqlite потянет вполне такое?
Я с ним не работал до этого, только mysql\postgres знаю, но мне они кажутся слишком монструозными для этой задачи. Или есть альтернативы вместо базы данных?

ia666
() автор топика
Ответ на: комментарий от ia666

A* и Дейкстра мне не подходят.
Вершин графа еще нету, они будут сгенерированы
в зависимости от начального состояния.

Плохая отмазка. Виртуальность вершин графа не мешает алгоритму A*

Einstok_Fair ★★☆
()
Ответ на: комментарий от ia666

Сколько элементов (поворотов) в схеме (или что там) предполагается? если несколько миллионов то в пару гигов всё влезет нормально (если не сильно мудрить с хранением структуры данных). Если миллиарды - то тут нужно будет посмотреть.... или памяти вкинуть нормально. Несколько десятков/сотен гигов.

HIS
()
Ответ на: комментарий от ia666

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

HIS
()
Ответ на: комментарий от HIS

хз, завтра думаю его опробовать вместо линейного.
12 элементов всего, но обычно 6-7, в зависимости от начального состояния там от пары тысяч элементов до пары сотен миллионов.
Мне 16 гигов бывает не хватет, из них обычно 14-15 свободно, втыкать больше некуда.
Пока что пощупал sqlite, не вытягивает он. Почти половина времени процессора уходит на sqlite, плюс он фигово реагирует на попытки использовать его в несколько потоков, ускорения считай нету вообще, что 1, что 5, что 10 потоков.
Буду пробовать другие варианты, потестирую постгрес, марию. Если кто нибудь выдаст 50 тысяч записей в секунду, я буду рад неимоверно.

ia666
() автор топика
Ответ на: комментарий от ia666

LMDB попробуй. Не забудь только базы с флагом MDB_NOSYNC открывать, иначе LMDB будет фиксировать транзакции на диск. А это медленно.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

Спасибо, вообще не знал про LMBD. Попробую, выглядит многообещающе.

ia666
() автор топика
Ответ на: комментарий от HIS

Ну мне надо ее запускать не только там, где 16 гигов.Еще ноут есть, где 4 гигабайта за радость.

ia666
() автор топика
Ответ на: комментарий от ia666

В любом случае БД будет узким местом по скорости. Нужно продумать хранение данных в памяти оптимально. Например по 4/8 байт на элемент (хотя зная конкретно задачу, можно оптимизировать очень жёстко) и влезет в 4 гига вполне вместе с операционкой.

HIS
()
Ответ на: комментарий от i-rinat

LMDB попробуй

Как-то это не совсем по поиску оптимального/кратчайшего пути.

HIS
()

На самом деле пока ничего оптимальнее чем поиск кратчайшего пути по ветвям графа ничего не придумано.

Тут задача построить граф правильно и вкинуть некоторые оптимизации в зависимости от задачи.

HIS
()
Ответ на: комментарий от HIS

Вот вот, главное корректно и оптимально построить граф, а LMDB тут будет как база данных для генерируемых вершин графа, это уже часть реализации.

ia666
() автор топика
Ответ на: комментарий от ia666

Может быть и так. Но я не уверен.

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

Могу чуть позже выложить визуализацию обхода пространства по волновому алгоритму в графах. Чуток конечно более специализированному.

HIS
()

Вот например посмотри этот упоротый ужас:

https://www.youtube.com/watch?v=YKiQTJpPFkA

Там всего-то 20 точек обхода оптимизированным волновым алгоритмом. Они начудили тысячи ветвей.

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

HIS
()

Вот тоже чудо-юдо... https://www.youtube.com/watch?v=Ob3BIJkQJEw

Тот же бессмысленный алгоритм, который делает тысячи переборов вместо десятков как можно было бы обычным оптимизированным волновым в 20-30 точек.

HIS
()

Ты упарываешься в визуальные спецэффекты на экране или в скорость работы и занимаемую память?

HIS
()
Ответ на: комментарий от i-rinat

Попробовал, в итоге остановился на MDB_NOSYNC | MDB_MAPASYNC | MDB_WRITEMAP
Быстрее sqlite в разы, мне от нее по сути нужен только mdb_put с MDB_NOOVERWRITE и без оного.
У меня такая картинка, при 3 и более потоков работают в основном 2 потока, остальные ждут в mdb_txn_begin.
Эту ситуацию можно улучшить?

ia666
() автор топика
Ответ на: комментарий от ia666

Не сталкивался. Возможно, у тебя много записей и они вынужденно сериализуются? Попробуй перестроить работу так, чтобы нити копили данные и сохраняли их пачкой.

На всякий случай уточню, ты ведь транзакции, в которых только чтение происходит, с MDB_RDONLY создаёшь?

i-rinat ★★★★★
()
Ответ на: комментарий от ia666

Если у тебя до 100 миллионов узлов (их можно вполне скомпоновать по 4 байта наверняка) и 4 гига памяти, не стоит притягивать БД.

HIS
()
Ответ на: комментарий от HIS

Для каждой сгенерируемой вершины у меня получается 64 байта данных. Предельно можно ужаться до 36 наверное, но очень не хочется.
Для сотен миллионов вариантов уже нужно 6 гигов, что не всякий комп потянет
Использование баз может снять с меня заботу об уникальности просчитанных вершин, не надо писать свой контейнер под это дело.
Хотя в целом ты прав, при малых количествах можно обойтись без базы, как таковой, и всё держать в памяти, хотя в конце все равно выгружать придется

ia666
() автор топика

Та даже по 8 байт можно. Туда можно напихать вообще много чего.

1 гиг вместе с прогой и дополнительных промежуточных данных.

HIS
()
Ответ на: комментарий от HIS

Научи, а? у меня есть 14 чисел, которые плавают от 0 до 65000, и 2 числа от 0 до пары миллиардов. Как это впихнуть в 8 байт?

ia666
() автор топика
Ответ на: комментарий от ia666

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

HIS
()
Ответ на: комментарий от ia666

даже если взять 16 байт - то это меньше 2х гигов для 100 миллионов узлов.

HIS
()
Ответ на: комментарий от ia666

в 16 байт можно впихнуть всё что ты описал + останется куча пустого места.

HIS
()

Все написано до тебя

anonymous
()
Ответ на: комментарий от i-rinat

У меня нет таких транзакций, только 1 метод на запись( с перезаписью значения и без)
Каждую новую вершину надо проверить на уникальность, иначе количество расчетов растет лавинообразно. А для этого приходится писать в базу. Можно конечно попробовать проверять, есть ли значение в базе через mdb_get, но сильно сомневаюсь, что это как то поменяет ситуацию, т.к. в случае отсутствия записи ее надо тут же создать.
Тем самым получить read-only transaction не видится возможным
С другой стороны, скорость и так выросла, мб этого хватит, и дальше пыхтеть смысла нету

ia666
() автор топика
Ответ на: комментарий от ia666

иначе количество расчетов растет лавинообразно.

Ты куда-то не туда полез.

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

HIS
()
Ответ на: комментарий от HIS

Ага, пошел почитал литературу, нашел ошибку у себя. Пойду исправлять.
Но опять же, храня карту графа в памяти, имеем у каждой вершины 12 координат, по 2-4 байта на вершину + до 4 байт для значения вершины . Как ты предлагаешь сжать это все в 16 байт, я без понятия.

ia666
() автор топика
Ответ на: комментарий от ia666

Как ты предлагаешь сжать это все в 16 байт, я без понятия.

Я задачу не знаю.

И даже если ты впихнёшь в 20 байт всё равно оно около двух гигов получится.

HIS
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.