«Конкурс параллельного программирования Accelerate 2012» или «6 ультрабуков и 10 SSD хватит всем!»

^[1]
Всем привет!
Последняя неделя на Хабре ознаменовалась серией хакерских постов — взламывали как VoIP ^[2], так и онлайн-пробки ^[3].
Предлагаю продолжить неделю более созидательно — решить задачу мирового масштаба ^[4] по генетике по параллельному программированию.
Сделать за месяц надо всего ничего: найти в двух строках, состоящих из нуклеотидов символов A, T, G и C, максимально длинную общую подстроку.
Призы по сравнению с предыдущим разом подросли и окрепли — сегодня на кону 6 ультрабуков Asus Zenbook UX31E ^[5] и 10 SSD-дисков суммарной емкостью 800 гигов.
Заманчиво?

О чем речь?

Вам дана reference-строка (например, такая: GATGAGCATGTGTTGAATCCTCA) и много длинных input-строк (вот одна из них: GTCCTCCAGTTTGTAGCATGTGTATTTATGTCCTCCAGTTTGTAGCATGTGTATTTAT). Нужно для каждый пары из reference- и input-строк найти максимально длинные общие подстроки и вернуть их «координаты». В примере ответом будет (5 13 15 23) и (5 13 44 52), то есть найдены две подстроки:

#код на Питоне, строки в ответе должны нумероваться от единицы, поэтому '-1'
ref = 'GATGAGCATGTGTTGAATCCTCA'
input = 'GTCCTCCAGTTTGTAGCATGTGTATTTATGTCCTCCAGTTTGTAGCATGTGTATTTAT'
ref[(5 - 1):13] == input[(15 - 1):23] #True
ref[(5 - 1):13] == input[(44 - 1):52] #True

В вашем распоряжении есть референсный код ^[6], который правильно, но очень медленно решает данную задачу брутфорсом.
Звучит просто?

Как решать?

Здесь начинается самое интересное. Предложу несколько вариантов, которые могут быть полезны:

• Самый простой способ: распараллелить референсный код по данным, например, используя OpenMP и поделив работу над входными тестами между потоками. Но делить работу можно по-разному. Только входные строки? Фрагменты референсной строки? Это сильно зависит от их размеров и количества — решать вам.
• Более интересный способ: взять референсный код, прогнать его через Intel VTune Amplifier XE ^[7] и распараллелить по-умному сам алгоритм
• Более умный подход: взять один из более чем 9000 алгоритмов поиска подстроки в строке ^[8] и попытаться найти лучше всего подходящий под эту задачу
• Самый продвинутый подход: объединить предыдущие пункты, взяв умный алгоритм и распараллелить его как по инструкциям, так и по данным

Что же выбрать? Хочу подсказку!

Что вам выбрать, мы посоветовать не можем. Кому-то нравится писать на pthreads, кому-то на OpenMP, а кто-то любит использовать параллельные функции из TBB и может быть даже MKL.
Одно известно наверняка — на нашем форуме ^[9] часто обсуждаются очень умные идеи и мысли. Например, стоит посмотреть на инструкции в SSE4.2.

На чем можно писать?

К сожалению, наша автоматическая система тестирования слишком молода для поддержи всех языков программирования.
В этот раз мы научили ее понимать C++ (несмотря на мою искреннюю любовь к питону и Java Script), поэтому писать придется на старом добром C++.
Платформа разработки может быть любой, но собираться и тестироваться код будет на машине с Linux (Debian stable — kernel 2.6.32) с установленным gcc (версия 4.6.2 для любителей pthreads) и Intel Parallel Studio XE 2011 (для тех, кто выбирает Intel Compiler, оптимизирующий код под наши процессоры).

А что с призами? Я хочу ультрабук!

Первым трем командам, написавшим самый быстрый код и отправившим решение до 16 мая, мы подарим по Asus Zenbook UX31E ^[10] на участника.
Вторым трем командам — по SSD 320 Series 80Gb ^[10].
Еще 4 участникам, которые напишут нам самые интересные посты в блоги Intel Software Network ^[11], также достанутся SSD.

Итак, еще раз: одна задача ^[4], один месяц, 6 ультрабуков и 10 SSD ^[10] для лучших участников из России и СНГ.

Всем, кто решит поучаствовать ^[12], желаем удачи!

Организаторы и судьи конкурса готовы ответить на любые ваши вопросы в комментариях.

Автор: rozboris