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 122,66
    Компания
    Поделиться публикацией
    Комментарии 42
    • +3
      Видеокарты можно использовать?
      • +2
        Нет, только CPU.
        А разве эта задача может быть эффективна решена на GPU?
    • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        Да, в этот раз только студенты и закончившие в прошлом году. Либо можно поучаствовать в качестве руководителя команды. В общем, там на форуме писали варианты :)
        • +1
          В конкурсе могут принимать участие команды из 1 или 2 человек. Все участники конкурса должны быть студентами (включая аспирантов) или выпускниками 2011 года.
          • 0
            Вот это облом.
            А онлайн курсы не считаются? :)
            • 0
              Как я понял объяснения Бориса, можно «шествовать» над командой, делясь опытом и советами с разработкой. Но не делать за них. Т.е. что-то типа преподавателя в учебном заведении, помогающему талантливым ученикам.
              Как к этой возможности поучаствовать можно привести курсы онлайн не представляю.

              Я вот и не студент и знакомых таких нет. Так что являюсь сторонним независимым наблюдателем :)
              • 0
                А вы давно закончили учиться? Думаю, можно зарегистрироваться, указав вуз, который закончили, и попробовать поучаствовать.
        • 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
                            Предполагается поступить проще. Таких нехороших последовательностей в тестовом примере просто не будет.

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

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