ALEX_k_s Jun 12 2015 at 11:05

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

18 min

15K

C++*GPGPU*Concurrent computing*

+20

Comments 14

sunnyfox Jun 13 2015 at 02:44

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

voidnugget Jun 13 2015 at 04:47

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

spice_harj Jun 13 2015 at 11:36

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

voidnugget Jun 13 2015 at 11:46

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

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

spice_harj Jun 13 2015 at 11:51

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

voidnugget Jun 13 2015 at 12:29

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

spice_harj Jun 13 2015 at 12:02

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

voidnugget Jun 13 2015 at 12:31

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

spice_harj Jun 13 2015 at 12:34

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

voidnugget Jun 13 2015 at 12:56

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

voidnugget Jun 16 2015 at 12:04

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

ALEX_k_s Jun 16 2015 at 12:09

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

voidnugget Jun 16 2015 at 12:53

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

ALEX_k_s Jun 16 2015 at 14:27

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