company_banner
19 апреля 2012 в 09:46

«Конкурс параллельного программирования 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 для лучших участников из России и СНГ.

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

Организаторы и судьи конкурса готовы ответить на любые ваши вопросы в комментариях.
Автор: @rozboris
Intel
рейтинг 171,46

Комментарии (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
      Предполагается поступить проще. Таких нехороших последовательностей в тестовом примере просто не будет.

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

Самое читаемое Разработка