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

[stmuxa]

Видеокарты можно использовать?

[rozboris]

Нет, только CPU.
А разве эта задача может быть эффективна решена на GPU?

[stmuxa]

Вот это я и хотел выяснить, если б можно было использовать GPU.

[AterCattus]

А есть ли смысл обрабатывать на GPU несколько последовательностей в МБ-ГБ весом?
В память все не засунуть, гонять по шине — не большое удовольстве. Только со значительной предобработкой на том же CPU…

[davinchi]

Конечно, нет: www.cbcb.umd.edu/software/cmatch/ www.springerlink.com/content/4122nv8469858582/ lmgtfy.com/?q=GPU+substring

[AterCattus]

Да, в этот раз только студенты и закончившие в прошлом году. Либо можно поучаствовать в качестве руководителя команды. В общем, там на форуме писали варианты :)

[bazilxp]

В конкурсе могут принимать участие команды из 1 или 2 человек. Все участники конкурса должны быть студентами (включая аспирантов) или выпускниками 2011 года.

[dotsquid]

Вот это облом.
А онлайн курсы не считаются? :)

[AterCattus]

Как я понял объяснения Бориса, можно «шествовать» над командой, делясь опытом и советами с разработкой. Но не делать за них. Т.е. что-то типа преподавателя в учебном заведении, помогающему талантливым ученикам.
Как к этой возможности поучаствовать можно привести курсы онлайн не представляю.

Я вот и не студент и знакомых таких нет. Так что являюсь сторонним независимым наблюдателем :)

[rozboris]

А вы давно закончили учиться? Думаю, можно зарегистрироваться, указав вуз, который закончили, и попробовать поучаствовать.

[dotsquid]

В 2009.

[Zlobober]

А школьникам можно?

[rozboris]

Можно, приходите, будем рады :)

[tampere]

Можете обновить дату на странице? А то там стоит 20.02, кажется, будто уже опоздал.

[rozboris]

Про какую страницу вы говорите?

[tampere]

software.intel.com/ru-ru/articles/contest-accelerate-2012-problem/
20.02.2012 — это смущает.

[rozboris]

Спасибо, скрыл дату, она не имеет смысла.

[infsega]

В архиве с примером в readme отсылка на французский сайт. Это международный конкурс?

[rozboris]

Конкурс проводится отдельно для России+СНГ и для региона EMEA (Европа, Средняя Азия, Африка). Задача в обоих регионах одинаковая, но призы будут выдаваться независимо.
Так что да, конкурс международный, на главной странице справа есть ссылки на Английскую, Французскую и Немецкую страницы конкурса.

[Bakotiinii]

Получил посылку от Intel c Поло и внутри было две брошюрки на участие в данном конкурсе. Пойду завтра кину в педагогический информатикам и в Дальневосточный Федеральный универ.

[rozboris]

Спасибо, когда я клал листовки в посылку для вас, я знал, что они не пропадут ;)

[Siper]

Для тех, у кого еще нет ультрабука и SSD-диска:
1. берем книгу «The Algorithm Design Manual» by Stiven S. Skiena
2. открываем страницу 94
3. курим 3.9 War Story: String 'em Up

[tangro]

4. Завистливо смотрим на людей, который выиграли ультрабук и SSD диск.

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

Я так думаю, что тут нужно думать головой серьёзно больше, чем «да ну, можно скопипастить алгоритм из конспекта».

[rozboris]

Конечно нужно. С другой стороны, знать про еще один существющий алгоритм, чтобы учесть его плюсы и минусы при разработке собственного, тоже нужно.

[tangro]

А есть ли пару реальных примеров тестовых данных? Ну, чтобы представлять, что придётся парсить.

[rozboris]

Конечно, есть. Полное описание задачи (включая ограничения на входные данные) есть на странице с задачей, а пример входных данных в архиве с референсным решением.

[tangro]

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

[rozboris]

Из комментариев ниже и из файла readme:
A large input file is available from: intel-software-academic-program.com/contests/ayc/early2012/test_input_1.tar.bz2

Автоматический бенчмарк с каждым днем становится «умнее», скоро будет показывать и время работы.

[pogorskiy]

Уточните пожалуйста соотношение размеров и количества ref и input данных.

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

То есть у нас есть одна большая ref строка и много (сколько примерно?) маленьких input последовательностей, важно то, что размер ref существенно больше чем размеры input. Правильно ли я все понял?

[AterCattus]

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 символов.

[rozboris]

Я не очень понял про Homo Sapiens. Если вы про пример в посте вверху, то это совпадение, я его брал почти из головы.

Вот ограничения на входные данные:

• M — минимальная длина подстрок, которые вам нужно найти, 6≤M≤2³²
• одна референсная строка длиной менее 2³² символов
• одна или несколько input-строк. Число input-строк — меньше, чем 2³². Суммарная длина всех input-строк менее 2³² символов

[pogorskiy]

в readme:
A large input file is available from:
intel-software-academic-program.com/contests/ayc/early2012/test_input_1.tar.bz2

Homo Sapiens оттуда, там файл так называется )

[rozboris]

Ого! Интересно, 2 дня назад там этой строчки не было. Спрошу у коллег, спасибо.

[AterCattus]

Этак выходит, что 6≤M≤2²⁶, а референсы вообще уровня 2¹¹.
Интересный архивчик, словом :)

[tangro]

И того референсный код потребует 130 Гб ОЗУ :)

[AterCattus]

Ага, там в readme.txt (test_input_1.tar.bz2) написано:
>>In order to process big files, you need to be less greedy than our sample program.

Вообще можно ж хранить по 2 бита, а то и вообще строить что-то типа дерева словарного сжатия (Хаффман и т.п.). Участникам решать :)

[tangro]

Серьёзно упадет скорость доступа к данным. Одно дело — прямая адресация в массиве, другое дело — поиск под дереву или пара лишних битовых операции ради получения каждого элемента.
Но в принципе, конечно, выкрутиться можно :)

[tangro]

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

Внимание, вопрос: эти неоднозначности будут исправлены, или нужно написать код, жестко делающий то же самое, что код в примере?

[rozboris]

Референсный код является главным источником информации о задаче и превалирует над текстовым словесным описанием.
Ваше решение будет сравниваться именно с референсным решением.

[tangro]

Спасибо за ответ, теперь хоть что-то понятно.
Вообще, грустно, что в конкурсе такого уровня не нашлось времени вычитать условие задачи на соответствие коду в примере. Ну да ладно.

[vikky13]

Предполагается поступить проще. Таких нехороших последовательностей в тестовом примере просто не будет.