Гибридная реализация алгоритма MST с использованием CPU и GPU

[@sunnyfox]

Скажите, а чему-то подобному в отечественных вузах учат?

[@voidnugget]

Minimum Spaning Tree — это просто дефолтная задача которую учат во всех ВУЗах на факультетах компьютерных наук и компьютерной инженерии, в основном учат «в теории» алгоритмы Прима, Крускала и Соллина (Борувки). Естественно, о реализации на gpgpu и речи быть не может, в некоторых особо весёлых заведениях ничего из вышеперечисленного даже до каких-либо исходников не доходит, а реализация на gpgpu «тянет» на бакалаврскую.

[@spice_harj]

может магистерскую? бакалавриат — это стандарт!

[@voidnugget]

На магистерскую, по моим меркам не тянет…
Хоть я и сам не заканчивал ВО, но имхо большая часть магистерских работ должна подразумевать практический выхлоп и хотя бы пару грамм инноваций, а так же ответ на вопрос «а чем ваша работа отличается от сотни других работ по этой же теме ?».

Вопрос MST на gpgpu действительно никем раньше толком не освящался, просто потому что обычно для этого отдельно пилят свои ASIC'и с требуемым выхлопом.

[@spice_harj]

раз не заканчивали ВО, то для уточнения: бакалавриат — это обычный диплом.

[@voidnugget]

Если не заканчивал ВО — не значит что не было научных работ, и не знаю что значит бакалаврская.

[@spice_harj]

сейчас принято, что в дипломы пишут всякую ерунду, поэтому для магистерской очень даже, а если ещё на gpgpu то и на кандидатскую с лихвой!!!

[@voidnugget]

Вот это собственно и печалит, что в каком-нить MIT / Berkeley это скорее лабораторная нежели кандидатская…

[@spice_harj]

В мыслях не было Вас обидеть. Я про отечественный «автопром». Ну Вы сравнили MIT, Ха!

[@voidnugget]

Да не обиделся я — просто требования у нас ниже плинтуса, и это чуток поднадоело, и на грусть местами тянет.

[@voidnugget]

Недавно набрёл на такую весёлую структуру данных как AF-heap — можно MST за линейное время выполнить.
Это будет пошустрее Борувки и, вполне так, можно приспособить к GPGPU.

[@ALEX_k_s]

очень странно, что статья 1991-1994 годов и до сих пор нигде не применили такую структуру и не написали MST за линейное время

[@voidnugget]

В журналах IEEE проскакивало, эта структура сейчас точно используется в броадкомовских свитчах типа томагавка.
Про вендорное Juniper/Cisco ничего не могу сказать. А вообще такие вещи принято реализовывать на ПЛИСках / ASIC'ах.

[@ALEX_k_s]

Структуры типа AF-heap или атомарной кучи — это сугубо теоретический способ понизить асимптотическую сложность некоторых алгоритмов. В статье, где определяется AF-heap, несколько раз подчёркивается, что к реальному миру это никакого отношения не имеет, а работать эта куча будет при числе элементов 2^12^20. Кстати, алгоритм MST при этом всё равно не линейной сложности. Существование линейного нерандомизированного алгоритма для MST всё ещё под вопросом. Алгоритм Chazelle (2000 год) имеет среднюю линейную сложность, однако константа там по факту получается настолько большой, что в реальном мире всё равно гораздо выгоднее считать алгоритмами со сложность O(m ln n).