Введение
Как-то стояла задача отсортировать уникальный массив строк с использованием GPU с минимум кода и максимально возможной скоростью…
В данном посте опишу основную идею ее решения. В качестве элементов массива сортировки в данном посте выступают числа.
Случай с уникальными элементами небольшого массива
В качестве платформы была выбрана CUDA по причинам, которые можно считать брэндовыми или индвидуальными. По факту, здесь много примеров именно на CUDA, и она на данный момент получила большее развитие в GPU-вычислениях, чем аналогичные платформы от ATI и OpenCL.
Поиск в сети по алгоритмам сортировки на CUDA дал разные результаты. Вот наиболее интересный. Там есть рисунок
, из которого видно, что наилучший результат дал алгоритм QSORT, который дает сложность порядка от O(NlogN) до O(N^2). И хотя распараллеливание на GPU дало лучший в статье результат, закралось сомнение, что QSORT — не лучший способ использовать ресурсы видеокарты для данной задачи (особенно испугал размер приведенного кода). Далее описывается решение задачи, по сути «в одну строчку» ссложностью временной сложностью O(N) в худшем случае.
Как-то стояла задача отсортировать уникальный массив строк с использованием GPU с минимум кода и максимально возможной скоростью…
В данном посте опишу основную идею ее решения. В качестве элементов массива сортировки в данном посте выступают числа.
Случай с уникальными элементами небольшого массива
В качестве платформы была выбрана CUDA по причинам, которые можно считать брэндовыми или индвидуальными. По факту, здесь много примеров именно на CUDA, и она на данный момент получила большее развитие в GPU-вычислениях, чем аналогичные платформы от ATI и OpenCL.
Поиск в сети по алгоритмам сортировки на CUDA дал разные результаты. Вот наиболее интересный. Там есть рисунок
, из которого видно, что наилучший результат дал алгоритм QSORT, который дает сложность порядка от O(NlogN) до O(N^2). И хотя распараллеливание на GPU дало лучший в статье результат, закралось сомнение, что QSORT — не лучший способ использовать ресурсы видеокарты для данной задачи (особенно испугал размер приведенного кода). Далее описывается решение задачи, по сути «в одну строчку» с
Это вторая часть из серии Hg Init: Учебное пособие по Mercurial от Джоэля Спольски (
Mercurial — это система контроля версий. Разработчики используют ее для администрирования исходного кода. У нее два основных назначения:
Для начала, я начал приводить всевозможные тупые причины, по которым нам не надо ничего менять. «Мы должны хранить репозиторий на центральном сервере, так безопаснее», — сказал я. Знаете что? Я был неправ. При работе с Mercurial у каждого разработчика на жестком диске хранится полная копия репозитория. Это, на самом деле, безопаснее. В любом случае, почти в каждой команде, использующей Mercurial, центральный репозиторий тоже существует. И вы можете делать резервное копирование этого репозитория со всей необходимой одержимостью. А еще можете устроить трехступенчатую защиту с 
Исходя из того, что первая статья насобирала много плюсов и попала в избранное большого количества человек, я понял что тема актуальна и во-первых призываю подтянуться сообщество (ведь я не могу знать абсолютно все библиотеки и решения), а во-вторых буду продолжать своими силами рассказывать о том какие библиотеки можно подтянуть, если необходимо что-то сделать вместо того чтобы делать все новые и новые велосипеды, состоящие из водопроводных труб.
Этим постом я начинаю серию статей, которые должны помочь каждому разработчику избавиться от велосипедов в своих последующих и текущих проектах. Усилить код и увеличить функционал. Каждый из нас хочет внести в свою программу нечто, что сделает ее богаче, но зачастую решение либо не находится, либо лень тратить время на поиски… Либо внутри сидит глупая уверенность что это можно реализовать быстро и не менее функционально. В любом случае я хочу чтобы каждый пробежался глазами по спискам библиотек, которые я вам предоставлю на суд, и чтобы у каждого эти библиотеки отложились в памяти. И когда их функционал пригодится в будущем, я очень надеюсь что вы вспомните этот пост и поищите эти библиотеки вместо того чтобы писать все новые и новые велосипеды, полные палок в колесах.
