Я скорее всего добавлю в текст ссылку, она в принципе будет и там доступна. Да и чтобы не копировать все с того сайта, я кратко описал основное тут. А так — все будет доступно. Там даже есть архив за 2015 год с реализацией победителя.
А что так не внимательно читали?
1) пример реализации есть на С++,
2) используемый алгоритм описан в самой правой колонке таблицы.
в скором времени будет выложена реализация победителя.
В разделе Задача есть пример на языке С++, но если есть желание попробовать на чем то другом, то можно попробовать установить необходимое ПО на тестовом сервере. Тестировать на другом языке скорее всего возможно будет только на одноузловом сервере. Также придется переписать саму задачу на другой язык (пример ее реализации, или хотя бы часть функционала).
Это конечно замечательно, что вы применили ГПУ и воспользовались уже написанной библиотекой, но
1) почему для расчетов используется шарп — ведь по моему ясно, что Си для этих целей куда лучше — и портируемость и поддержка со стороны CUDA/OpenCL/ MPI
2) ваш Mani.net вполне возможно лучше бы работал, если бы был на Си, так как используя CUDA вы выходите на хорошо оптимизированные библиотеки, написанные на Си, так еще и на GPU.
Также может я что то упустил, но не заметил — параллельная ли ваша версия или последовательная? именно то, что сравнивалось на графике. По вашим цифрам получается где то в 16 раз ускорилось.
PS: еще как пожелание — график было бы лучше смотреть, если бы на нем была только ваша версия и GPU, то есть увеличенный масштаб. А то он лишь показывает, что то, с чем вы сравниваетесь — хуже, а конкретно на сколько лучше — не ясно.
Структуры типа AF-heap или атомарной кучи — это сугубо теоретический способ понизить асимптотическую сложность некоторых алгоритмов. В статье, где определяется AF-heap, несколько раз подчёркивается, что к реальному миру это никакого отношения не имеет, а работать эта куча будет при числе элементов 2^12^20. Кстати, алгоритм MST при этом всё равно не линейной сложности. Существование линейного нерандомизированного алгоритма для MST всё ещё под вопросом. Алгоритм Chazelle (2000 год) имеет среднюю линейную сложность, однако константа там по факту получается настолько большой, что в реальном мире всё равно гораздо выгоднее считать алгоритмами со сложность O(m ln n).
самый новый драйвер от NVIDIA и CUDA 7.0 поддерживает данный механизм. Другое дело — что быстрее: вычисление или передача. Скорее всего вычисления пролетают быстро, тем самым алгоритм в хорошем случае должен сводиться к копированию и выгрузке данных. Еще хотел добавить:
если алгоритм использует мало данных или вообще сохраняет их только для выгрузки/загрузки, то можно вообще не использовать глобальную память, загружая данные прямо с ЦПУ через L2 в ядро. Также можно делать и с выгрузкой. Этот механизм называется UMA или как то так. В общем передаете указатель на память ЦПУ и обращаетесь к нему как к массиву в ядре. Тогда эти ваши стадии скорее всего не понадобятся.
Мне кажется на 750 видеокарте не поддерживается двунаправленная загрузка / выгрузка. Соответственно схема не подходит для все ГПУ =)
И я думаю вряд ли производительность ГПУ линейно масштабируется, там очень много факторов.
У самого есть возможность прогнать алгоритм на GTX Titan и Xeon E5 v2, если код конечно не секретен =) а еще интересно посмотреть на оптимальность кода на ГПУ
А в чем собственно проблема? Эти данные закачиваются туда один раз. Предположим вам надо разметить граф хотя бы 32 раза. Тогда на карту будет одна закачка и 32 раза запустится алгоритм. То есть получаем, что на 32 точки 31 работает со скоростью Х, а 1 — Х / 3. Итоговая скорость с учетом копирования уменьшится примерно на 3-4%.
Если же по алгоритму планируется добавление новых дуг, то это тоже можно предусмотреть и добавлять в уже выделенное место.
На Титан помещается граф и на 4Гб, просто для его обработки не хватило памяти, так как был не эффективно написан алгоритм сортировки. Для многих карт я еще пока не думал что делать.
Всего три этапа: чтение данных сгенерированного графа в формате CSR; далее этап преобразования данных, описанные в SSSP; собственно счёт.
Какой этап вас конкретно интересует? И что понимается под разогревом?
Все величины весов имеют порядки 1016 и сравниваются именно с такой точностью при проверке полученного массива расстояний. Я не понимаю к чему вы клоните.
Порядки получаемых длин от 1,5 — 3,0, веса лежат в полуинтервале (0, 1]
Исходные данные были в double и в double они выдаются обратно. Требуется double.
Эффективное использование ресурсов GPU. Там, где производительность порядка 1 млрд дуг/сек, профилировщик NVVP показывает производительность L2 на high уровне при незначительных записях в массив dist, и чуть меньше high — при многочисленных записях. Эффективность чтения из глобальной памяти GPU — 100%, запись — где то 25% так как мало данных пишется. Производительность шины показывается на уровне выше среднего.
Да, эти оценки верны и вы правы — в параллельной версии просматривается примерно в 20 раз больше ребер. Наверно не сделал акцент на том, что последний график показывает на сколько быстрее мой алгоритм на GPU с оптимизированной версией на CPU алгоритма Дейкстры с кучей…
Для сравнения производительности на CPU использовался оптимизированный алгоритм Дейкстры. Никаких оптимизаций в виде перестановки данных перед работой на CPU не производились
:
1) пример реализации есть на С++,
2) используемый алгоритм описан в самой правой колонке таблицы.
в скором времени будет выложена реализация победителя.
1) почему для расчетов используется шарп — ведь по моему ясно, что Си для этих целей куда лучше — и портируемость и поддержка со стороны CUDA/OpenCL/ MPI
2) ваш Mani.net вполне возможно лучше бы работал, если бы был на Си, так как используя CUDA вы выходите на хорошо оптимизированные библиотеки, написанные на Си, так еще и на GPU.
Также может я что то упустил, но не заметил — параллельная ли ваша версия или последовательная? именно то, что сравнивалось на графике. По вашим цифрам получается где то в 16 раз ускорилось.
PS: еще как пожелание — график было бы лучше смотреть, если бы на нем была только ваша версия и GPU, то есть увеличенный масштаб. А то он лишь показывает, что то, с чем вы сравниваетесь — хуже, а конкретно на сколько лучше — не ясно.
если алгоритм использует мало данных или вообще сохраняет их только для выгрузки/загрузки, то можно вообще не использовать глобальную память, загружая данные прямо с ЦПУ через L2 в ядро. Также можно делать и с выгрузкой. Этот механизм называется UMA или как то так. В общем передаете указатель на память ЦПУ и обращаетесь к нему как к массиву в ядре. Тогда эти ваши стадии скорее всего не понадобятся.
И я думаю вряд ли производительность ГПУ линейно масштабируется, там очень много факторов.
У самого есть возможность прогнать алгоритм на GTX Titan и Xeon E5 v2, если код конечно не секретен =) а еще интересно посмотреть на оптимальность кода на ГПУ
Если же по алгоритму планируется добавление новых дуг, то это тоже можно предусмотреть и добавлять в уже выделенное место.
На Титан помещается граф и на 4Гб, просто для его обработки не хватило памяти, так как был не эффективно написан алгоритм сортировки. Для многих карт я еще пока не думал что делать.
Какой этап вас конкретно интересует? И что понимается под разогревом?
Исходные данные были в double и в double они выдаются обратно. Требуется double.