Анализируя комментарии здесь все больше прихожу к выводу, что было бы неплохо написать вообще обзор параллельных алгоритмов сортировки. Потому как те алгоритмы, которые в пространстве последовательного выполнения хороши, могут оказаться не столь эффективны в параллельном, как например тот же qsort.
Но с такой яростной критикой хабрапользователей уже сомневаюсь, что правильно поймут суть поста и назначение.
Как вообще определение O(f(x)) соотносится с ограничением x<1000?
В посте хотел показать что рассматривались алгоритмы сортировки в диапазоне ArraySize <= MaxThreads. И если так ограничить размер исходного массива, то выбор используемого алгоритма сортировки следует осуществлять несколько «переосмыслив» их эффективность. И в качестве критерия выбора предложил функцию сложности, которой все и недовольны. :)
Если такой критерий не вводить, то становится трудно сравнивать алгоритмы в поставленных рамках задачи. А общепринятое понятие сложности временной сложности лучше всего подходит для понимания.
А с чего Вы решили, что алгоритмы имеющие сложность O(N*logN) не будут параллелиться?
Если вы внимательно читали пост, то вначале я привел пример распараллеленного qsort.
Если считаете что qsort в частности хорошо параллелится, то приведите пожалуйста пример и его временную (да любую) сложность для сравнения. Раз вы задали такой вопрос и продолжаете писать комментарии, то ясно что причина в нехватке знаний. Цитирую:
Основные ограничения CUDA:
* отсутствие поддержки рекурсии для выполняемых функций;
* минимальная ширина блока в 32 потока;
2
Если он при этом работает эффективнее, то почему не должно быть желания его использовать?
При разработке, когда у вас есть желание использовать чужой якобы эффективный код необходимо его:
а) протестировать
б) осмыслить, проверить и проанализировать (вдруг там есть презент на пасху)
Для этого вам необходимо иметь свободное время и потратить определенное количество человеко-часов на проведение этих операций. Только по их окончании вы можете быть уверены что используемый код работает (и то не факт). У меня такого желания что-то не возникло… :).
Потому и решил поделиться с хабрасообществом простым решением в одну строку, решающим поставленную задачу.
И рад, что хоть кому-то оно понравилось! :-D
А вам потому и минус, что отсутствует желание думать, вникать и понимать. Хотя, может это и просто ваша невнимательность. Далее, претензии — в личку, а то вы уже перешли на оскорбления и начинаете троллить.
Всего хорошего!
Временная сложность алгоритма (в худшем случае) — это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера. В задачах, где размер выхода не превосходит или пропорционален размеру входа, можно рассматривать временную сложность как функцию размера только входных данных.
То есть, такие алгоритмы имеют временную сложность O(N).
Точного названия сложности сравнения в посте сказано не было, но позже было пояснено в комментарии от
edeldm * 17 декабря 2010, 19:54 *
Поэтому замечание ваше неверное.
И еще момент. Да, операции выполняются параллельно. Вы хотите сказать что параллельный алгоритм и последовательный — это одинаковые алгоритмы? И методы сортировки для последовательных алгоритмов эффективно применимы к параллельным?
Вам же желаю успешного окончания ПГТУ, советую пройти этот курс и выучить эту книгу, и хотя бы пролистать еще один не авторитетный источник.
Нет, т.к. после синхронизации п.4 выполняется параллельно и A[tid] до выполнения текущим потоком мог уже затереться другим потоком. Если бы A[] был локальным то можно было, а он в __shared__ потому и нельзя.
в первом потке A[4] = A[0];
во втором A[0] = A[4] (а он уже A[0]);
И при сортировке массива 5 1 получим 5 5 или 1 1.
Может быть и такой случай 1 3 2 даст 1 2 2, и т.д.
Для этого и проводится запоминание текущего элемента в B_tid чтобы избежать перезатирания его соседом.
Во первых, те кто занимается таким поиском и найдет более быстрое решение — то и не заявит. Тем более не напишет статью на хабре о своем решении.
Во вторых, O(N²/количество_ядер) когда количество_ядер = N, значительно лучшем чем просто O(N^2) или O(N log N).
И если нет желания использовать большойсложный код для простой и быстрой сортировки, то можно использовать предлагаемый алгоритм. О чем и был пост, а не о постулатах сложности алгоритмов.
Минимум кода, максимум результата. Знаете другой алгоритм в одну строку с более быстрой скоростью работы в многопоточном режиме? С удовольствием прочту ваш пост про него (а такие алгоритмы наверняка есть, просто никто о них не заявляет на хабре).
Да, алгоритм действительно можно называть и «сортировкой выбором», адаптированной под многопоточность.
Но следует понимать, что все-таки это два разных алгоритма. И время выполнения одного != времени выполнения другого при использовании в решении указанной мной задачи (вместе с ее ограничениями).
И почему-то и авторы приведенной статьи, и другие, используют qsort и другие алгоритмы, т.к. они в старом смысле имеют лучшую стоимость (сложность) чем более медленные «сортировки выбором».
Но как я показал в данном посте, при многопоточных вычислениях понятие стоимости (сложности) несколько меняется и эффективнее использовать алгоритмы более медленные на CPU, но дающие более лучшие временные характеристики вычислений на GPU, чем общепринятые алгоритмы.
При создании квантовых же компьютеров или вычислений на графенах опять-таки картина может измениться.
Полностью согласен! Про «любые» массивы сразу все оговорки были сделаны :)
Сейчас настала пора облачных вычислений, потому и
>>задачу коммивояжера за линейное время можно решить.
Вопрос только в том, что больше «любой» размер массива, или «любое» количество вычислителей в облаке.
Вопрос о сложности был еще со времен создания RSA. Где математики считали что будет неимоверно сложно раскладывать числа на сомножители. Но время показало, что понятие сложность имеет свою размерность. И если данных для вычислений мало, мощности много, то сложностью можно и пренебречь.
Одобряю и поддерживаю OpenCL т.к. видеокарты ATI быстрее чем NVidia. И тенденция преимущества производительности ATI идет уже очень давно. Но вот поддержка драйверов, да и вообще суппорт у ATI слабее, чем у NVidia. Так, когда CUDA только зарождалась и завоевывала рынок, у ATI все только начиналось. Теперь же, пару лет спустя, CUDA значительно сильнее развилась чем конкуренты. Появились такие средства, как parallel nsight monitor, изначально созданные и соптимизированные именно для CUDA.
Каждый же производитель видеокарт оптимизирует свою продукцию под свою технологию разработки ПО. Потому если хочется писать на CUDA — сейчас приходится выбирать Nvidia и терять в 5% (по разному конечно, вопрос спорный) производительности.
Понимая что долго так не продолжится, обе компании поддерживают OpenCL, но так… чтобы было. А предпочтение отдадут своим продуктам. И так будет долго, так как Nvidia не допустит конкуренцию у разработчиков игр и программ, которые на данный момент пишут в основном для CUDA, а не Stream.
и то, только в случае, если количество элементов равно количеству ядер процессора.
Если будете применять, пожалуйста не забывайте, что данный алгоритм применим только для GPU, когда количество потоков равно количеству сортируемых элементов. Чем мощнее видеокарта — тем больший массив без потери скорости можно сортировать.
Ваш алгоритм выполняется в одном потоке? Если так — то у него виден сразу вложенный «for». Это значит что его сложность O(N^2). Это крайне медленно.
Если бы Вы написали на С++ (MSVS2010 + STD::TR1) и вместо первого «for» поставили бы parallel_for, то это был бы описанный алгоритм со временем выполнения для O(N).
Дело в том что задача возникла, когда выполнение УЖЕ идет в ядре видеопроцессора, и необходимо было быстро отсортировать память находясь там без выхода наружу. Соглашусь что потери на копирование данных имеют место когда надо копировать. Но когда память уже была там и мы просто запускаем kernel и выходим из него используя данные уже находящиеся там — то qsort там нет.
И действительно, можно вообще избавиться от K[tid]. И соптимизировать по скорости. Добавил UPD2.
Хм, каждая СММ модель — узел вершины графа дерева, переходя от узла к узлу определяем лучшую модель?
Если так, да и вообще, так или не так — это неплохая идея семантического графа скрытых марковских моделей для решения сложных задач.
Каждая СММ в узле графа может отвечать за свой конкретный вопрос, и передвигаясь по СММ узлам дерева можно реализовать и экспертную систему и нейронные сети (СММ в роли функции нейрона) да и вообще!
Я так понимаю есть минимум 2 СММ модели. 1-лицо. 2-не лицо. СММ выдает вероятность принадлежности ей выборки. Для того чтобы выбрать ответ «да лицо» или нет, не лицо — надо сравнивать с порогом выход. Например СММ1 дал 5% а СММ2 дал 3%, то есть рисунок не похож ни на лицо ни на что иное. Или же другой пример. СММ1 дал 75% а СММ2 дал 65%. Достаточно ли 75% для определения что да, наш рисунок содержит лицо? Т.е. стоит вопрос 0.75>K или нет? и чему равно K?
Но с такой яростной критикой хабрапользователей уже сомневаюсь, что правильно поймут суть поста и назначение.
функциюсложности, которой все и недовольны. :)Если такой критерий не вводить, то становится трудно сравнивать алгоритмы в поставленных рамках задачи. А общепринятое понятие
сложностивременной сложности лучше всего подходит для понимания.1
Если вы внимательно читали пост, то вначале я привел пример распараллеленного qsort.
Если считаете что qsort в частности хорошо параллелится, то приведите пожалуйста пример и его временную (да любую) сложность для сравнения. Раз вы задали такой вопрос и продолжаете писать комментарии, то ясно что причина в нехватке знаний. Цитирую:
2
При разработке, когда у вас есть желание использовать чужой якобы эффективный код необходимо его:
а) протестировать
б) осмыслить, проверить и проанализировать (вдруг там есть презент на пасху)
Для этого вам необходимо иметь свободное время и потратить определенное количество человеко-часов на проведение этих операций. Только по их окончании вы можете быть уверены что используемый код работает (и то не факт). У меня такого желания что-то не возникло… :).
Потому и решил поделиться с хабрасообществом простым решением в одну строку, решающим поставленную задачу.
И рад, что хоть кому-то оно понравилось! :-D
А вам потому и минус, что отсутствует желание думать, вникать и понимать. Хотя, может это и просто ваша невнимательность. Далее, претензии — в личку, а то вы уже перешли на оскорбления и начинаете троллить.
Всего хорошего!
То есть, такие алгоритмы имеют временную сложность O(N).
Точного названия сложности сравнения в посте сказано не было, но позже было пояснено в комментарии от
Поэтому замечание ваше неверное.
И еще момент. Да, операции выполняются параллельно. Вы хотите сказать что параллельный алгоритм и последовательный — это одинаковые алгоритмы? И методы сортировки для последовательных алгоритмов эффективно применимы к параллельным?
Вам же желаю успешного окончания ПГТУ, советую пройти этот курс и выучить эту книгу, и хотя бы пролистать еще один не авторитетный источник.
Разговор с вами окончен. Всего хорошего!
Но сами видеокарты шустрее чем от Nvidia.
habrahabr.ru/blogs/algorithm/110177/#comment_3505922
Спасибо за внимание!
в первом потке A[4] = A[0];
во втором A[0] = A[4] (а он уже A[0]);
И при сортировке массива 5 1 получим 5 5 или 1 1.
Может быть и такой случай 1 3 2 даст 1 2 2, и т.д.
Для этого и проводится запоминание текущего элемента в B_tid чтобы избежать перезатирания его соседом.
Во вторых, O(N²/количество_ядер) когда количество_ядер = N, значительно лучшем чем просто O(N^2) или O(N log N).
И если нет желания использовать большой сложный код для простой и быстрой сортировки, то можно использовать предлагаемый алгоритм. О чем и был пост, а не о постулатах сложности алгоритмов.
Минимум кода, максимум результата. Знаете другой алгоритм в одну строку с более быстрой скоростью работы в многопоточном режиме? С удовольствием прочту ваш пост про него (а такие алгоритмы наверняка есть, просто никто о них не заявляет на хабре).
Временная сложность O(N), а не вычислительная. Вычислительная O(N^2).
Спасибо за линк!
Но следует понимать, что все-таки это два разных алгоритма. И время выполнения одного != времени выполнения другого при использовании в решении указанной мной задачи (вместе с ее ограничениями).
И почему-то и авторы приведенной статьи, и другие, используют qsort и другие алгоритмы, т.к. они в старом смысле имеют лучшую стоимость (сложность) чем более медленные «сортировки выбором».
Но как я показал в данном посте, при многопоточных вычислениях понятие стоимости (сложности) несколько меняется и эффективнее использовать алгоритмы более медленные на CPU, но дающие более лучшие временные характеристики вычислений на GPU, чем общепринятые алгоритмы.
При создании квантовых же компьютеров или вычислений на графенах опять-таки картина может измениться.
Вычислительная же сложность, как и у алгоритма сортировки выбором равна O(N^2).
Если бы при решении задачи использовался алгоритм «сортировки выбором» это было бы максимум в N раз дольше, либо в log N раз дольше (случай с qsort).
Сейчас настала пора облачных вычислений, потому и
>>задачу коммивояжера за линейное время можно решить.
Вопрос только в том, что больше «любой» размер массива, или «любое» количество вычислителей в облаке.
Вопрос о сложности был еще со времен создания RSA. Где математики считали что будет неимоверно сложно раскладывать числа на сомножители. Но время показало, что понятие сложность имеет свою размерность. И если данных для вычислений мало, мощности много, то сложностью можно и пренебречь.
Каждый же производитель видеокарт оптимизирует свою продукцию под свою технологию разработки ПО. Потому если хочется писать на CUDA — сейчас приходится выбирать Nvidia и терять в 5% (по разному конечно, вопрос спорный) производительности.
Понимая что долго так не продолжится, обе компании поддерживают OpenCL, но так… чтобы было. А предпочтение отдадут своим продуктам. И так будет долго, так как Nvidia не допустит конкуренцию у разработчиков игр и программ, которые на данный момент пишут в основном для CUDA, а не Stream.
Если будете применять, пожалуйста не забывайте, что данный алгоритм применим только для GPU, когда количество потоков равно количеству сортируемых элементов. Чем мощнее видеокарта — тем больший массив без потери скорости можно сортировать.
Для CPU он не подходит.
Если бы Вы написали на С++ (MSVS2010 + STD::TR1) и вместо первого «for» поставили бы parallel_for, то это был бы описанный алгоритм со временем выполнения для O(N).
И действительно, можно вообще избавиться от K[tid]. И соптимизировать по скорости. Добавил UPD2.
Если так, да и вообще, так или не так — это неплохая идея семантического графа скрытых марковских моделей для решения сложных задач.
Каждая СММ в узле графа может отвечать за свой конкретный вопрос, и передвигаясь по СММ узлам дерева можно реализовать и экспертную систему и нейронные сети (СММ в роли функции нейрона) да и вообще!
Вам + за мысль :)