Время: 15 дней (10 апреля — 24 апреля 2011 г.)
Конкурс завершён. Посмотреть итоги.
Посмотреть таблицу участников.

Предлагаю принять участие в седьмом любительском конкурсе по программированию. Вам будет предложено написать программу, работающую на GPU и на двух ядрах CPU. Конечно, вовсе не обязательно участвовать с программой, написанной для видеокарты, вы можете задействовать только процессор. Но идея соревнования заключается в том, кто лучше сможет запрограммировать трудную для распараллеливания программу на видеокарте. Побеждает тот, чья программа окажется самой быстрой.

Задача

Задан неориентированный граф G=(V,E). Количество вершин равно n, количество рёбер равно m. Вершины нумеруются числами от 1 до n. Требуется посчитать распределение количества простых циклов в заданном графе по их длинам.

Подробное описание задачи предлагаю посмотреть в видео-презентации. Скачать с narod.yandex.ru (202 Мб). Видео есть и на RuTube.ru. Можно также смотреть через Яндекс (но качество текста все равно лучше в исходном файле):

 

Ссылки из видео:

Что значит «посчитать распределение количества простых циклов»? Нужно ответить на вопрос о том сколько в графе простых циклов, имеющих длину 3, 4, …, n.

Что такое простой цикл? Это цикл, проходящий через каждую вершину графа не более одного раза (то есть не пересекает сам себя по вершинам). Например, последовательность [3,5,9] будет циклом, если в графе есть рёбра (3,5), (5,9) и (9,3). При этом последовательность вершин [9,3,5] будет соответствовать тому же самому циклу. Всего такой цикл может быть записан 6-ю различными способами (в зависимости от того, что считать начальной вершиной и в какую сторону — по часовой стрелке или против — перечислять его вершины). Все такие записи в рамках конкурса считаются одним и тем же циклом (подробнее смотрите в видео).

Требования к программе

Требуется написать программу, которая считывает из файла входные данные, и выводит в другой файл ответ. Формат входных и выходных данных указан ниже в примере. Программа может задействовать процессор и видеокарту для своих расчетов. Имеющиеся ресурсы будут также указаны ниже.

Предлагается два варианта проверки решения участников.
(1) В почтовый ящик конкурса (см. ниже) присылается работающая программа, которая будет прогоняться по всем имеющимся тестам.
(2) Присылается программа, написанная на C/C++ (возможно с использованием библиотеки MPI из Microsoft HPC Pack 2008 SDK) которая будет откомпилирована на компьютере конкурса. В этом случае я не гарантирую, что программа будет скомпилирована. Вы должны будете объяснить то, как её компилировать, нужно ли для этого что-то устанавливать и как это сделать. В данный момент кроме CUDA Toolkit 3.2 (и драйвера видекарты) никаких специальных средств для компилирования приложения под GPU не установлено.

Пример и пояснения к формату ввода / вывода

Входной файл задаётся в качестве первого параметра при запуске вашей программы. Например

> Prog.exe filename.in

Ваша программа должна будет выдать ответ в файл, который получается из «filename.in» добавлением суффикса «.a». То есть «filename.in.a» (в данном случае). Во входном файле в первой строке задаются числа n и m. В остальных m строках записаны пары чисел (a,b), означающие, что вершины a и b связаны ребром. Например,

Входной файл "test1"
—————-
6 9
1 4
1 6
2 3
2 5
3 4
3 6
4 5
4 6
5 6
—————-

В выходном файле в первой строке должно быть записано количество циклов длиной 3, во второй — количество циклов длиной 4 и т. д. Например,

Выходной файл "test1.а"
—————-
3
5
2
2
—————-

Это означает, что в предложенном графе 3 цикла длиной 3, 5 циклов длиной 4 и по 2 цикла с длинами 5 и 6. Других простых циклов в графе нет.

Категории участия

Поскольку задача достаточно сложная, предлагается участвовать в двух категориях. В первой категории ограничение на число вершин в графе n=21 (для тех, кто может придумать достаточно нетривиальный алгоритм, отличающийся от полного перебора). Вторая категория — ограничение на число вершин n=14 (для тех участников, кто не разбирается в алгоритмах, но умеет программировать и хочет посоревноваться с другими в распараллеливании алгоритмов полного перебора). В первой категории гарантируется, что ответ умещается в 64 бита без знака. (именно поэтому мы ограничились 21 вершиной).

[ Дополнение 11.04.2011 ] Введена нулевая категория участия: ограничение на число вершин до n=25. Графы уже не плотные, а такие, чтобы ответ умещался дважды в 64 бита без знака.

Измерение времени

Поскольку конкурс проводится на видеокарте, то участникам придётся самим встроить в свои программы функции измерения времени. Давайте поступим честно. В начале работы вашей программы нужно включить таймер измерения времени (такой таймер должен быть, наверно, в любом языке программирования), а после вывода данных таймер можно выключить и вывести время работы программы на консоль. К сожалению, в данном случае я пока не придумал как измерить время работы вашей программы точно, как если бы она работала на одном ядре. Прошу поступить честно и выводить правильное время работы программ. В данном конкурсе при указанных ограничениях вряд ли программы разных участников будут работать за почти одинаковое время, поэтому такое измерение времени должно оказаться вполне честным.

Положения

С целью предотвращения недоразумений я вынужден требовать соблюдения некоторых ограничений.

Общие правила и ограничения

  1. Операционная система, на которой будет проходить тестирование: либо  — Windows 7 — 32 бита, либо Ubuntu 10.04 — 64 бита. Можете выбрать любую систему и присылать готовый исполняемый файл под неё.
  2. Тестирование производится на компьютере с процессором Intel Core 2 Duo 8400 (3000 MHz) 4GB DDR2-800 + Видеокарта GeForce 250 GTS (128 ядер по 738 MHz) 1 Gb памяти.
  3. Программа может задействовать все ресурсы компьютера. Я обещаю, что в процессе тестирования вашей программы отключу все лишние сервисы и прочие программы.
  4. Время работы программы на каждом тесте не должно превышать 1200 секунд.
  5. Максимальный порядок графа — n=21 вершина (для первой категории) и n=14 вершин (для второй категории)
  6. Программа должна работать в консольном режиме, то есть никаких графических интерфейсов писать не нужно. Ваша программа считывает данные из входного файла (который будет находится в той же директории), решает задачу и выводит ответ в другой файл (в ту же директорию).
  7. Конкурс завершается 24 апреля ровно в 18 ч. 00 м. (по московскому времени).
  8. Я НЕ принимаю участия в конкурсе и НЕ вмешиваюсь в рассуждения участников и их решения от начала конкурса и до его завершения. Никому ничего не советую и не помогаю найти / понять / написать / скачать и т. д. Буду ограничиваться лишь общими комментариями по мере необходимости.
  9. Я оставляю за собой право менять правила проведения конкурса, если в них обнаружатся неточности.

Порядок проведения конкурса

  1. Во время проведения конкурса участники посылают на электронный адрес «zealint.comp@gmail.com» письмо с темой «Статистика циклов — Конкурс». В теме необходимо указать свой ник. Прикрепите к письму исполняемый файл или CPP/CU файл с указанием желаемых ключей компиляции. Внимание: gmail не пропускает EXE файлы даже в сжатом виде, поэтому нужно переименовать их, например, в MP3.. Также не забудьте указать, в какой категории вы планируете участвовать.
  2. По мере тестирования поступающих программ, результат их работы будет указываться в таблице рейтинга, внизу этой страницы. Один участник не должен присылать программу более одного раза в сутки. Почта проверяется 4-5 раз в сутки.
  3. Победившим считается тот участник, программа которого оказалась самой быстрой на момент завершения конкурса.

Пожелания

Прочтите FAQ (кроме вопросов о призах, которых в этом конкурсе нет).

По мере проведения конкурса привлекайте ваших друзей, которые не увидели объявлений. Возможно им тоже будет интересно.

После окончания конкурса я, по вашему желанию, установлю ссылки с этой страницы на главную страницу вашего сайта, при условии, что вы установите ссылку со своей не главной страницы на эту. Все ссылки без noindex и nofollow. Также любой участник может поделиться своим исходным кодом, который я выложу для общего доступа вместе с моими тестами и программами всех участников.

Если пишете комментарии, то подписывайтесь тем ником, который у вас отображается в таблице рейтинга (если отображается).

Недоброжелателей, троллей, и пр. прошу себя никак не проявлять.

Текущий рейтинг

Конкурс завершён. Посмотреть итоги.

Таблица ниже будет постоянно обновляться по мере поступления новых программ. Внимание: прежде чем присылать программу, убедитесь, пожалуйста, что она укладывается в отведённое время на самом большом тесте (видимо, это будет полный граф). Удачи!

Нулевая категория (довольно сложные алгоритмы)

  1. Andrey Khalyavin :: 17.04 :: 1 ядро CPU + GPU :: Win32 :: 2,99 c
  2. Andrey Khalyavin :: 13.04 :: 2 ядра CPU :: Lin64 :: 18,63 c
  3. Andrey Khalyavin :: 12.04 :: 2 ядра CPU :: Lin64 :: 29,40 c

Первая категория (не самые сложные алгоритмы, но и не перебор)

  1. Andrey Khalyavin :: 16.04 :: 1 ядро CPU + GPU :: Win32 :: 0,24 c
  2. Andrey Khalyavin :: 13.04 :: 2 ядра CPU :: Lin64 :: 0,89 c
  3. Andrey Khalyavin :: 12.04 :: 2 ядра CPU :: Lin64 :: 1,38 c
  4. Andrey Khalyavin :: 11.04 :: 1 ядро CPU :: Win32 :: 2,40 c

Вторая категория (переборные методы)
Здесь пока нет участников.

Информационные спонсоры

dxdy — Научный форум.

Обсуждение конкурса на моём форуме.