«Слабо загрузить 40 ядер?» или простой конкурс параллельного программирования Acceler8 2011

[k06a]

Если я не ошибаюсь первый алгоритм не понижает на степень объёма вычислений? Объём так и остается O(n⁴). Второй же алгоритм опускает сложность до O(n³)?

[rozboris]

Да, вроде как кэш уменьшает только константу. А алгоритм Кадане пока вообще непонятно, как перенести на двумерный случай. Есть идеи?

[k06a]

Я сегодня практически додумался до снижения константы…
Получилось почти как в первом случае, только в N раз сложнее))
Разберусь с одномерным — подумаю над двумерным))

[DmitryO]

Продолжая «образовательную дискуссию» рассуждениями о совсем уж идеальном мире, на месте преподавателей я бы засчитывал участие в подобных конкурсах как курсовую или что-то в этом духе. Конкурс/олимпиада = оценка в зачетку, строчка в резюме и приз в семейный бюджет = PROFIT*3 ;)

[k06a]

Должно быть: sum = B[i2][j2]- B[i1-1][j2]- B[i2][j1-1]+ B[i1-1][j1-1]

[rozboris]

Верно, опечатка, спасибо за поправку.

[tronix286]

Загрузить 40 ядер? Да не вопрос, 1 индус вам в помощь.

[AndreyIvanoff]

«интересное кеширование» — это известный прием (например, тут)- называется чаще интегральное представление изображений. Попробую принять участие.

[yui_room9]

А главное на имаге троллфэйс уместен :)

[rozboris]

А матрицы-то, с матрицами что?

[razoroid]

ну и название конечно) нет, не слабо
mpirun -n 8 helloWorld.exe :-)

[razoroid]

тьфу, т.е. -n 40

[seewald]

Борис, у меня вопрос (я задал его в письме, но не уверен, что оно дошло :) ):
после логина на intel я получаю всегда nginx 400 вместо страниц. Что-то не так с регистрацией или это временно?

[rozboris]

Ответил в приват.
Регистрация работает, видимо это было временный Хабраэффект.

[k06a]

Доступ к MKL предоставляется через SSH over VPN. Насколько я понимаю это 1 сервер. Каким образом 1000 участников смогут одновременно тестировать твои программы на 40 ядрах? Ведь при каждом из запусков будет разное время выполнения… Память тоже одна на всех…

Я, конечно, понимаю что с финальным тестированием всё пройдёт гладко…

[rozboris]

Троллфейс на картинке вверху видели? Шутка :)
Если открыть документ, который вам прислали админы MTL, то становится понятно, что во-первых, сервер не один, их много одинаковых, а во-вторых, задачи все запускают через шедулер, который рулит очередью задач и не дает им конфликтовать.

[k06a]

Не обратил внимания. Хорошо, что всё так поставлено)

[rozboris]

За написание тем и сообщений команда может получить максимум 25 очков за весь конкурс. Разве это не понятно из таблицы выше? Я постараюсь убрать эту двусмысленность asap.
Лучше написать 'Максимум 25 очков за социальную активность'?

[DreamWalker]

Я вот всё равно не уверен, что до конца понял систему оценки. Можно ещё раз уточнить формулу по которой оценивается команда?

[rozboris]

Легко!
Команда может набрать максимум 200 очков.
Из них 150 — за код (скорость, масштабируемость, правильность) — формула пока не разглашается.
Еще максимум 25 — за форум или посты в блог (1 форумный пост дает команде 1 балл, один блог — 10 баллов)
Еще 25 очков, если команда пришлет «Описание работы».

[4knowledge]

Как я понял не важно на каком писать языке?

[rozboris]

Верно, намек на Си и поддерживать мы будем Си. Но если вы найдёте на MTL питон или java — велкам, можете писать и на них.

[AterCattus]

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

Поправьте, если не так.

[rozboris]

Ничему не противоречит. Итоговая матрица может вырождаться в одну ячейку или же во всю входную матрицу (при определенных входных параметрах).

[AterCattus]

Ясно, спасибо.

[ehles]

На вервый взгляд всё просто. Но если подумать, у матрицы 10х10 3025 подматриц. По правилам матрица может быть до 20000х20000 — страшно подумать сколько у ней будет подматриц О_о