Всем привет!
Последняя неделя на Хабре ознаменовалась серией хакерских постов — взламывали как VoIP, так и онлайн-пробки.
Предлагаю продолжить неделю более созидательно — решить задачу мирового масштаба по генетике по параллельному программированию.
Сделать за месяц надо всего ничего: найти в двух строках, состоящих из нуклеотидов символов A, T, G и C, максимально длинную общую подстроку.
Призы по сравнению с предыдущим разом подросли и окрепли — сегодня на кону 6 ультрабуков Asus Zenbook UX31E и 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
В вашем распоряжении есть референсный код, который правильно, но очень медленно решает данную задачу брутфорсом.
Звучит просто?
Как решать?
Здесь начинается самое интересное. Предложу несколько вариантов, которые могут быть полезны:
- Самый простой способ: распараллелить референсный код по данным, например, используя OpenMP и поделив работу над входными тестами между потоками. Но делить работу можно по-разному. Только входные строки? Фрагменты референсной строки? Это сильно зависит от их размеров и количества — решать вам.
- Более интересный способ: взять референсный код, прогнать его через Intel VTune Amplifier XE и распараллелить по-умному сам алгоритм
- Более умный подход: взять один из более чем 9000 алгоритмов поиска подстроки в строке и попытаться найти лучше всего подходящий под эту задачу
- Самый продвинутый подход: объединить предыдущие пункты, взяв умный алгоритм и распараллелить его как по инструкциям, так и по данным
Что же выбрать? Хочу подсказку!
Что вам выбрать, мы посоветовать не можем. Кому-то нравится писать на pthreads, кому-то на OpenMP, а кто-то любит использовать параллельные функции из TBB и может быть даже MKL.
Одно известно наверняка — на нашем форуме часто обсуждаются очень умные идеи и мысли. Например, стоит посмотреть на инструкции в 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 на участника.
Вторым трем командам — по SSD 320 Series 80Gb.
Еще 4 участникам, которые напишут нам самые интересные посты в блоги Intel Software Network, также достанутся SSD.
Итак, еще раз: одна задача, один месяц, 6 ультрабуков и 10 SSD для лучших участников из России и СНГ.
Всем, кто решит поучаствовать, желаем удачи!
Организаторы и судьи конкурса готовы ответить на любые ваши вопросы в комментариях.
Автор: rozboris
