Новый сезон Threading Challenge: умножьте по-Штрассену

Всем привет!

Позор моим сединам – оказывается, есть такая премия, имени того самого Кнута, которой награждают специальных людей, которые внесли особый вклад в развитие информатики. А я и не знал! :(

Так вот, в прошлом году немецкий математик Фолкер Штрассен получил упомянутую всуе премию за титанический труд, направленный на разработку и анализ эффективных алгоритмов. Одной из первых его работ стал алгоритм перемножения матриц, пусть по современным меркам и не самый эффективный, зато простой. Точнее - несложный. А еще неплохо распараллеливающийся.  Видимо эти две причины и натолкнули моего коллегу Клэя-судью Бришерса на выбор первого задания нового сезона Threading Challenge 2009. Итак, умножение матриц по алгоритму Штрассена.

Хочу обратить ваше внимание на вот какую штуку. Все мы помним, что в прошедшем сезоне судейство конкурса зачастую затягивалось на недели. Так вот, в данном задании эта проблема решена на корню: конкурсное приложение должно само сгенерировать матрицы, само их перемножить (двумя способами), и само же проверить результаты. Судьям останется только записать время выполнения в табличку и отсортировать ее по возрастанию.  Очень надеюсь что на этот раз первую строчку наконец-то займет участник из России :)

Что же остается мне? Привести полный текст задания и пожелать вам удачи!


...
Участники конкурса должны отправить решение этой задачи до 11 сентября 2009 (11 утра 12 сентября по московскому времени).

Постановка задачи

Написать многопоточное приложение, выполняющее умножение двух матриц используя алгоритм Штрассена. Приложение должно сгенерировать две случайные матрицы A(M,P) и B(P,N) а затем перемножить их, используя: (1) последовательный метод и (2) алгоритм Фолкера Штрассена. Результатом умножений являются соответственно матрицы C и С1, размерностью (M,N). Необходимо также удостоверится в совпадении результатов двух перемножений, выполнив сравнение полученных матриц.

Три целых числа, описывающие размерности M, N, и P, должны быть соответственно первым, вторым и третьим аргументами командной строки программы.

Ограничения
К заданию прилагается простая имплементация последовательного алгоритма на языке C. Конкурсное приложение должно использовать в качестве отправной точки референсный код, а именно: включать неизменную функцию Main, функцию генерации матриц, код последовательного перемножения матриц и функцию, сравнивающую результат двух перемножений. Допустимы изменения, связанные с имплементацией задания на языках, отличных от C. Кроме того, допускаются изменения, относящиеся к механизму выделению памяти и распараллеливанию алгоритма Штрассена. Все сделанные изменения, а так же особенности имплементации алгоритма необходимо включить в описание конкурсной работы.

Таким образом, работа должна использовать параллельную имплементацию алгоритма Штрассена для перемножения двух матриц.

Время выполнения
Оценка и рейтинг конкурсной работы будет вычисляться исходя из времени выполнения алгоритма Штрассена. Конкурсные работы должны содержать код таймера и выводить время выполнения в STDOUT. В случае отсутствия кода таймера для сравнения будет использовано общее время выполнения, т.е. время, включающие генерацию матриц и последовательное перемножение.

Прилагаемые файлы и дополнительные ресурсы
Референсная имплементация алгоритма
Форум данного задания (eng), форум поддержки конкурса (rus)
Форма для отправки решения

...
For more complete information about compiler optimizations, see our Optimization Notice.
Categories: