Конкурс по распараллеливанию алгоритма задачи о подсчёте статистики распределения циклов по длинам завершён. Подведём итоги.

Итоги

Победителем объявляется единственный участник Andrey Khalyavin.

Нулевая категория (n=25)

  1. Andrey Khalyavin :: 1 ядро CPU + GPU :: Win32 :: 2,99 c

Первая категория (n=21)

  1. Andrey Khalyavin :: 1 ядро CPU + GPU :: Win32 :: 0,24 c

Вторая категория (n=14)
Победила задача!

Презентация

Описание алгоритма и прочие соображения по поводу прошедшего конкурса можно посмотреть в видео-презентации. В нормальном качестве можно скачать здесь (122 Мб). Также можно посмотреть через Яндекс.видео:

 

Решение жюри

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

Программа написана специально в учебных целях, только чтобы уловить логику алгоритма. Для n=21 работает чуть меньше 3 секунд. Для n=25 нужно внести некоторые изменения в код (см. презентацию) и компилировать под Linux-64. Работать будет около 2 м. (на моей машине).

Достаточно хорошую и простую реализацию под GPU жюри, к сожалению, написать не удалось.

Что дальше?

Неизвестно, когда я смогу провести конкурс в очередной раз, так как завершается учебный год и возрастает нагрузка. Но, по-видимому, в следующий раз конкурс будет «закрытым», то есть участники не будут знать ничего о решениях друг друга до самого окончания конкурса. В конце в виде таблицы выводятся результаты каждого. Но это при условии, что задача будет трудной. Если же будут идеи (возможно, не мои, а ваши) другого характера, то можно провести конкурс и в отрытом виде. Всё будет зависеть от сложности.

Обсуждение конкурса на форуме в этой теме.