company_banner

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


    Всем привет!
    Последняя неделя на Хабре ознаменовалась серией хакерских постов — взламывали как 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 для лучших участников из России и СНГ.

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

    Организаторы и судьи конкурса готовы ответить на любые ваши вопросы в комментариях.
    Intel
    186,00
    Компания
    Поделиться публикацией

    Комментарии 42

      +3
      Видеокарты можно использовать?
        +2
        Нет, только CPU.
        А разве эта задача может быть эффективна решена на GPU?
          +2
          Вот это я и хотел выяснить, если б можно было использовать GPU.
            +2
            А есть ли смысл обрабатывать на GPU несколько последовательностей в МБ-ГБ весом?
            В память все не засунуть, гонять по шине — не большое удовольстве. Только со значительной предобработкой на том же CPU…
        • НЛО прилетело и опубликовало эту надпись здесь
            +1
            Да, в этот раз только студенты и закончившие в прошлом году. Либо можно поучаствовать в качестве руководителя команды. В общем, там на форуме писали варианты :)
              +1
              В конкурсе могут принимать участие команды из 1 или 2 человек. Все участники конкурса должны быть студентами (включая аспирантов) или выпускниками 2011 года.
                0
                Вот это облом.
                А онлайн курсы не считаются? :)
                  0
                  Как я понял объяснения Бориса, можно «шествовать» над командой, делясь опытом и советами с разработкой. Но не делать за них. Т.е. что-то типа преподавателя в учебном заведении, помогающему талантливым ученикам.
                  Как к этой возможности поучаствовать можно привести курсы онлайн не представляю.

                  Я вот и не студент и знакомых таких нет. Так что являюсь сторонним независимым наблюдателем :)
                    0
                    А вы давно закончили учиться? Думаю, можно зарегистрироваться, указав вуз, который закончили, и попробовать поучаствовать.
                      0
                      В 2009.
                0
                А школьникам можно?
                  +2
                  Можно, приходите, будем рады :)
                  0
                  Можете обновить дату на странице? А то там стоит 20.02, кажется, будто уже опоздал.
                  0
                  В архиве с примером в readme отсылка на французский сайт. Это международный конкурс?
                    0
                    Конкурс проводится отдельно для России+СНГ и для региона EMEA (Европа, Средняя Азия, Африка). Задача в обоих регионах одинаковая, но призы будут выдаваться независимо.
                    Так что да, конкурс международный, на главной странице справа есть ссылки на Английскую, Французскую и Немецкую страницы конкурса.
                    +3
                    Получил посылку от Intel c Поло и внутри было две брошюрки на участие в данном конкурсе. Пойду завтра кину в педагогический информатикам и в Дальневосточный Федеральный универ.
                      +2
                      Спасибо, когда я клал листовки в посылку для вас, я знал, что они не пропадут ;)
                      +4
                      Для тех, у кого еще нет ультрабука и SSD-диска:
                      1. берем книгу «The Algorithm Design Manual» by Stiven S. Skiena
                      2. открываем страницу 94
                      3. курим 3.9 War Story: String 'em Up
                        0
                        4. Завистливо смотрим на людей, который выиграли ультрабук и SSD диск.

                        Потому что:
                        -Это не та задача (да, она оперирует тем же алфавитом, но делает она другое)
                        -Она, конечно, использует не тот алгоритм
                        -Для строки в 65к символов (а это в 65000 раз меньше ограничений решаемой задачи) она работает 11 с лишним часов

                        Я так думаю, что тут нужно думать головой серьёзно больше, чем «да ну, можно скопипастить алгоритм из конспекта».
                          0
                          Конечно нужно. С другой стороны, знать про еще один существющий алгоритм, чтобы учесть его плюсы и минусы при разработке собственного, тоже нужно.
                        0
                        А есть ли пару реальных примеров тестовых данных? Ну, чтобы представлять, что придётся парсить.
                          0
                          Конечно, есть. Полное описание задачи (включая ограничения на входные данные) есть на странице с задачей, а пример входных данных в архиве с референсным решением.
                            0
                            Я неверно выразился. Имелось в виду не «хоть какие» данные, а реальные, больших объёмов, на которых можно было бы локально потестировать производительность алгоритмов.
                            Плюс вопрос в догонку — будет ли (и если да — то когда) автоматический бенчмарк вставлять в письма данные о времени выполнения задач. Т.е. смогу ли я оценить, что вот была версия №1, которая у вас там прошла тесты за 30 секунд, а версия №2 — за 25 секунда (и сделать выводы по поводу оптимальности алгоритмов).
                        0
                        Уточните пожалуйста соотношение размеров и количества ref и input данных.

                        В примере лежит Homo_sapiens.GRCh37.66.dna.chromosome.19.fa размером 60 Мб и две последовательности примерно по 2Кб.

                        То есть у нас есть одна большая ref строка и много (сколько примерно?) маленьких input последовательностей, важно то, что размер ref существенно больше чем размеры input. Правильно ли я все понял?
                          +1
                          software.intel.com/ru-ru/articles/contest-accelerate-2012-problem/

                          Точное описание входных параметров
                          Ваше решение будет вызываться со следующими параметрами:
                          K — количество потоков, которые ваша программа может порождать, 1≤K≤40
                          M — минимальная длина подстрок, которые вам нужно найти, 6≤M≤2^32
                          ref — имя ref-файла, содержащего одну референсную строку (длина референсной строки менее 2^32 символов)
                          in — одно или несколько имен input-файлов, каждый из которых содержит одну или несколько input-строк. Число input-строк во всех файлах вместе — меньше, чем 2^32. Суммарная длина всех input-строк менее 2^32 символов.
                            0
                            Я не очень понял про Homo Sapiens. Если вы про пример в посте вверху, то это совпадение, я его брал почти из головы.

                            Вот ограничения на входные данные:
                            • M — минимальная длина подстрок, которые вам нужно найти, 6≤M≤232
                            • одна референсная строка длиной менее 232 символов
                            • одна или несколько input-строк. Число input-строк — меньше, чем 232. Суммарная длина всех input-строк менее 232 символов
                              +1
                              в readme:
                              A large input file is available from:
                              intel-software-academic-program.com/contests/ayc/early2012/test_input_1.tar.bz2

                              Homo Sapiens оттуда, там файл так называется )
                                0
                                Ого! Интересно, 2 дня назад там этой строчки не было. Спрошу у коллег, спасибо.
                                  0
                                  Этак выходит, что 6≤M≤226, а референсы вообще уровня 211.
                                  Интересный архивчик, словом :)
                                    0
                                    И того референсный код потребует 130 Гб ОЗУ :)
                                      0
                                      Ага, там в readme.txt (test_input_1.tar.bz2) написано:
                                      >>In order to process big files, you need to be less greedy than our sample program.

                                      Вообще можно ж хранить по 2 бита, а то и вообще строить что-то типа дерева словарного сжатия (Хаффман и т.п.). Участникам решать :)
                                        0
                                        Серьёзно упадет скорость доступа к данным. Одно дело — прямая адресация в массиве, другое дело — поиск под дереву или пара лишних битовых операции ради получения каждого элемента.
                                        Но в принципе, конечно, выкрутиться можно :)
                              0
                              На форуме соревнования участниками показано, что код в примере НЕ решает задачу в поставленной формулировке. Есть целая куча примеров неоднозначного поведения — когда кода в примере трактует задачу по-одному, хотя её вполне можно понимать и по-другому (например, вопрос сдвига найденной последовательности вправо, вопрос вывода не всех найденных последовательностей — см. примеры «АААА» + «АААА» и «АСАС»+«АСАС»).

                              Внимание, вопрос: эти неоднозначности будут исправлены, или нужно написать код, жестко делающий то же самое, что код в примере?
                                0
                                Референсный код является главным источником информации о задаче и превалирует над текстовым словесным описанием.
                                Ваше решение будет сравниваться именно с референсным решением.
                                  +1
                                  Спасибо за ответ, теперь хоть что-то понятно.
                                  Вообще, грустно, что в конкурсе такого уровня не нашлось времени вычитать условие задачи на соответствие коду в примере. Ну да ладно.
                                  0
                                  Предполагается поступить проще. Таких нехороших последовательностей в тестовом примере просто не будет.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое