company_banner

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

    Продолжая неделю высказывания мнений о высшем образовании на Хабре, расскажу о конкурсе, который находится где-то посередине, между работой (так отрицаемой уважаемым AlexanderLarin) и умением учиться (так продвигаемым хабрапользователем Alexnn).
    Конкурс параллельного программирования Acceler8 2011
    А расскажу я о конкурсе параллельного программирования Acceler8. Да, это конкурс, в котором есть возможность не только научиться, но и заработать один из «небольших» призов: 2 мощных лэптопа HP и 10 нетбуков Asus.
    Хотите попробовать свои силы?

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

    Кратко о задаче


    Дана двумерная матрица значений, нужно найти в ней прямоугольную подматрицу с максимальной суммой элементов в ней среди всех подматриц.
    Подробнее о задаче можно прочитать на странице конкурса.

    Кратко о решении


    Понятно, что последовательным перебором в лоб задача решается, однако решение будет слишком медленным:
    int maxSum = A[0][0];
    int maxI0 = 0, maxJ0 = 0, maxI1 = 1, maxJ1 = 1;
    for (int i = 0; i < M; i++) 
    	for (int j = 0; j < N; j++) 
    	  for (int width = 1; width <= M - i; width++)
    		for (int height = 1; height <= N - j; height++)
    		{
    		  int currentSum = sum_subarray(A, i, j, i + width, j + height);
    		  if (currentSum > maxSum)
    		  {
    			maxSum = currentSum;
    			maxI0 = i;
    			maxJ0 = j;
    			maxI1 = i + width - 1;
    			maxJ1 = j + height - 1;
    		  }
    		}
    cout << "Max subarray: [" << maxI0 << "][" << maxJ0 << "] .. [" << maxI1 << "][" << maxJ1 << "]";
    cout << endl <<  "Max value = " << maxSum << endl;
    cout << "Area = " << (maxI1 - maxI0 + 1) * (maxJ1 - maxJ0 + 1) << endl;
    

    Очевидно, что такой подход — «совсем не epic».

    Как решать по-умному


    Существует множество подходов к этой задаче.
    • Во-первых, можно использовать интересное кеширование (основанное на свойствах матриц), описанное в Daily One Algorithm:
      Для начала создадим промежуточную матрицу B, изначально заполенную нулями, в которой в каждом элементе B[i][j] хранится сумма элементов подматрицы от верхнего левого угла (A[0][0]) до A[i][j].
      Теперь сумма элементов в любой подматрице может быть найдена как
      
      sum = B[i2][j2]- B[i1-1][j2] - B[i2][j1-1] + B[i1-1][j1-1]
      

    • Во-вторых, можно попробовать применить алгоритм Кадане, изначально написанный для одномерного массива или портировать и параллелизовать модифицированный алгоритм, приведенный одним из пользователей stackoverflow.com
    • В-третьих, можно немного подумать и написать красивое, параллельное и быстрое решение ;)

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

    Как мы будем оценивать масштабируемость?


    Есть много подходов и много флуда по этому вопросу. Мы решили взять самое простое в реализации, но и самое близкое к реальности решение:
    Код будет тестироваться на двух разных платформах. Первая — 40-ядерная машина Manycore Testing Lab, с известными хардварными характеристиками, известной маркой процессора и известным размером кэша второго уровня (см. «Конфигурация MTL»). Вторая — маленькая система, о которой неизвестно почти ничего (2-4 ядра, несколько гигов памяти — вот и вся информация).
    Сложно ли в такой ситуации оптимизировать решение? Да.
    С другой стороны — можно работать быстрее всех на «маленькой машине» и средне на MTL — этого может быть достаточно для выигрыша.
    А может быть кто-то добьется лучшего результата на обеих машинах? Это покажет время.
    Итак, для заинтересовавшихся, маленькая ссылка: регистрация на конкурс. Вопросы можете писать в комментариях или оставлять на форуме конкурса.

    И, это, be epic! ;)
    Intel
    Company

    Comments 31

      +1
      Если я не ошибаюсь первый алгоритм не понижает на степень объёма вычислений? Объём так и остается O(n4). Второй же алгоритм опускает сложность до O(n3)?
        0
        Да, вроде как кэш уменьшает только константу. А алгоритм Кадане пока вообще непонятно, как перенести на двумерный случай. Есть идеи?
          0
          Я сегодня практически додумался до снижения константы…
          Получилось почти как в первом случае, только в N раз сложнее))
          Разберусь с одномерным — подумаю над двумерным))
        +4
        Продолжая «образовательную дискуссию» рассуждениями о совсем уж идеальном мире, на месте преподавателей я бы засчитывал участие в подобных конкурсах как курсовую или что-то в этом духе. Конкурс/олимпиада = оценка в зачетку, строчка в резюме и приз в семейный бюджет = PROFIT*3 ;)
          0
          Должно быть: sum = B[i2][j2]- B[i1-1][j2]- B[i2][j1-1]+ B[i1-1][j1-1]
            0
            Верно, опечатка, спасибо за поправку.
            +2
            Загрузить 40 ядер? Да не вопрос, 1 индус вам в помощь.
              0
              «интересное кеширование» — это известный прием (например, тут)- называется чаще интегральное представление изображений. Попробую принять участие.
                +2
                А главное на имаге троллфэйс уместен :)
                  +3
                  Установите Windows и Касперского на максимум паранои, ядра загрузятся сами. Где мне забрать ноутбук?
                    +1
                    А матрицы-то, с матрицами что?
                    0
                    ну и название конечно) нет, не слабо
                    mpirun -n 8 helloWorld.exe :-)
                      0
                      тьфу, т.е. -n 40
                      +1
                      Борис, у меня вопрос (я задал его в письме, но не уверен, что оно дошло :) ):
                      после логина на intel я получаю всегда nginx 400 вместо страниц. Что-то не так с регистрацией или это временно?
                        0
                        Ответил в приват.
                        Регистрация работает, видимо это было временный Хабраэффект.
                        0
                        Доступ к MKL предоставляется через SSH over VPN. Насколько я понимаю это 1 сервер. Каким образом 1000 участников смогут одновременно тестировать твои программы на 40 ядрах? Ведь при каждом из запусков будет разное время выполнения… Память тоже одна на всех…

                        Я, конечно, понимаю что с финальным тестированием всё пройдёт гладко…
                          +1
                          Троллфейс на картинке вверху видели? Шутка :)
                          Если открыть документ, который вам прислали админы MTL, то становится понятно, что во-первых, сервер не один, их много одинаковых, а во-вторых, задачи все запускают через шедулер, который рулит очередью задач и не дает им конфликтовать.
                            0
                            Не обратил внимания. Хорошо, что всё так поставлено)
                          +1
                          Какой-то не честный конкурс в плане оценки.
                          1. 0-150 очков за решение задачи.
                          2. 0-25 очков за социальную активность
                            • 1 балл начисляется Команде за каждое содержательное сообщение в Форумах Intel® Software Network от одного из ее участников.
                            • 10 баллов начисляется Команде за одну содержательную статью или пост в блог Intel® Software Network от одного из ее участников.
                          3. 25 очков за присланное Командой Описание работы.

                          т.е. можно идеально написать программу + описание (150 очков + 25 очков), но проиграть команде, которая занималась только написанием тем и сообщений (а задачу решила наихудшим путём)
                            +1
                            За написание тем и сообщений команда может получить максимум 25 очков за весь конкурс. Разве это не понятно из таблицы выше? Я постараюсь убрать эту двусмысленность asap.
                            Лучше написать 'Максимум 25 очков за социальную активность'?
                              +1
                              Ну да, пометка — но не более 25 очков, будет кстати.
                                0
                                Я вот всё равно не уверен, что до конца понял систему оценки. Можно ещё раз уточнить формулу по которой оценивается команда?
                                  +1
                                  Легко!
                                  Команда может набрать максимум 200 очков.
                                  Из них 150 — за код (скорость, масштабируемость, правильность) — формула пока не разглашается.
                                  Еще максимум 25 — за форум или посты в блог (1 форумный пост дает команде 1 балл, один блог — 10 баллов)
                                  Еще 25 очков, если команда пришлет «Описание работы».
                              +1
                              Как я понял не важно на каком писать языке?
                                +1
                                Там написано что на сервере: GNU compilers, Intel® C++ Compiler Professional Edition for Linux так что наверное намек на Си и С++
                                  0
                                  Верно, намек на Си и поддерживать мы будем Си. Но если вы найдёте на MTL питон или java — велкам, можете писать и на них.
                                0
                                Кстати, а какие ограничения на входные данные? Тип элемента массива (int16/int32/int64/float и тому подобные) и какой размер массива может быть? Без этих данных довольно сложно что-то делать, т.к. при некоторых данных размер матрицы может быть такого размера, что не поместится в ОЗУ и тогда уже совершенно по другому придется всё делать.
                                  0
                                  Не совсем понятно про минимальный разрешенный размер итоговой матрицы.
                                  Судя по этому
                                  >>в первой паре оба числа должны быть меньше или равны соответственным числам во второй паре, т.е. сначала описывается координаты левого верхнего, а потом правого нижнего угла
                                  итоговая матрица может (чисто теоретически) вырождаться в единствунную ячейку.

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

                                    Only users with full accounts can post comments. Log in, please.