Начинаем конкурс параллельного программирования Threading Challenge

    Коллега Boomburum уже показывал скриншот диспетчера задач похожего монстра. Четыре сокета, в каждом их них по процессору Intel® Xeon® E7-4860 с 24MB кэша, а сверху – 64 гигабайта оперативки. Что со всем этим богатством делать? У меня есть пара идей!



    Мы начинаем конкурс параллельного программирования Threading Challenge 2011. Участники получат доступ к этой машине, а победители отправятся на IDF в Сан-Франциско, где нам, надеюсь, еще и не такие картинки покажут. Задача конкурса сводится к тому, чтобы загрузить все доступные ядра на 100%, снять скриншот и поместить на Хабре! Шутка. Не все так просто.



    Итак, о конкурсе



    Конкурс Threading Challenge проводится четвертый год подряд. Я долго пытался красиво перевести это название на русский язык, но… Если будут идеи – делитесь, а пока прошу прощения за англицизмы. Конкурс международный, но победа русских программистов в нем стала доброй традицией. Например, в прошлом году главный приз взял Дмитрий Вьюков, а в 2008 – Петр Трифонов. Стоит ли говорить, что победы соотечественников нам очень, очень приятны! Чтобы поддержать хорошую традицию и облегчить участия тем, кто не особо силен в Английском, в этом году мы принимаем решения на русском языке.

    Правила конкурса такие: есть две категории сложности, «начальный уровень» и «продвинутый уровень». В каждой категории будет по три серьезных алгоритмических задачки. На каждую задачку дается 22 дня, за решения начисляются баллы. Разумеется, в основном за скорость, замеренную на той самой машине, но есть и всякие бонусные. Те трое, кто набрал больше баллов в своей категории, получат небольшие призы (от $150 до $500).

    Как только судьи закончат оценку последнего, третьего задания, мы посчитаем общую сумму по участникам и объявим двоих победителей – один в «начальной» категории и один – в «продвинутой». Они-то и поедут на IDF 2011 в Калифорнию.

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

    Первое задание в категории «начальный уровень»



    Надеюсь, все знают о игре «жизнь»? Для тех, кто не знает — есть некая поверхность, разбитая на клетки. Клетка может находиться в двух состояниях: быть живой или мертвой. Клетка имеет восемь соседей. Задача «жизни» — смоделировать будущие поколения клеток по следующим правилам: мертвая клетка, рядом с которой ровно три живые клетки, оживает. Живая клетка, у которой два или три живых соседа, продолжает жить. Если соседей меньше двух или больше трех, то клетка умирает соответственно от одиночества или от перенаселённости. Про алгоритмы моделирования «жизни» можно почитать, к примеру, на rsdn.ru. Там есть большой простор для оптимизации, как с точки зрения хранения данных, так и с точки зрения распараллеливания.

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

    Первое задание в категории «продвинутый уровень»



    Решить очень большую головоломку «Masyu». Суть головоломки: в ячейках прямоугольного поля расположены белые и черные круги, надо соединить круги вертикальными и горизонтальными отрезками так, чтобы получилась замкнутая линия. Линия не должна пересекать саму себя, ветвиться или проходить через одну клетку дважды. Есть два дополнительных условия: линия, проходящая через ячейку с черным кругом, должна повернуть в ней на 90 градусов, а следующую и предыдущую ячейки надо пройти прямо, поворачивать нельзя. В ячейках с белым кругом наоборот – надо пройти ячейку прямо, не меняя направления, и повернуть на 90 градусов в следующей ЛИБО в предыдущей ячейке (то есть хотя бы с одной стороны). На картинке ниже – пример решения маленькой головоломки Masyu. Тестовые наборы данных по понятным причинам будут существенно больше. Побеждает тот, кто быстрее решит головоломку.

    Threading Challenge Masyu path example

    Подробное описание конкурсных заданий с примерами исходных данных и требованиях к файлам с результатами, и также подробные правила и перечень призов доступны на сайте конкурса.

    Вопросы (замечания, пожелания) можно задавать прямо здесь, либо в специальном форуме. Прием конкурсных работ заканчивается в знаменательный день 9-го мая.

    UPD: поправил картинку.

    Всем удачных алгоритмических находок! И пожалуйста, не планируйте на сентябрь ничего важного – возможно кто-то из вас поедет на Intel® Developers Forum.
    Intel
    177,00
    Компания
    Поделиться публикацией

    Комментарии 65

      +8
      А можно попросить скрин с этой машины моего BarsWF, в SSE2-only версии?
      3.14.by/ru/md5

      3.14.by/files/BarsWF_SSE2_x64.zip (32-х битная версия там тоже лежит)

      Командная строка:

      BarsWF_SSE2_x64.exe -h 21685d282d79098b89bdf5a916b66c90 -c 0aA~
        +1
        Можно. Хотя, если вы сотрудник учебного заведения, — можете совершенно официально получить доступ к этим системам. Есть такая лаборатория Manycore testing Lab (гуглится), — тестируйте в свое удовольствие.
          +2
          К сожалению, я не сотрудник учебного заведения, и не учащийся
            +1
            Ок. Я что-нибудь придумаю.
              +3
              Своими постами вы дали новую жизнь пониманию этого смайла :).
          +2
          4 *Zeon?
            +5
            there is no spoon ©
            0
            42
              +2
              Ничего про инструментарий не сказано. Хотя подозреваю что си/плюсы.
                0
                Тоже озадачился вопросом. Судя по спецификации тестовой машины, доступен dotnet 4.0 и java 6.0.
                  0
                  Тут написано. Никаких ограничений, в рамках здравого смысла. Если требуется какой-то очень уж специфический рантайм — спрашивайте, поставим.
                  +1
                  Удачи вам с чем-либо кроме Си/плюсов :)
                    0
                    Зря вы так. В прошлых сезонах у нас в числе лидеров был участник, использующий один из многопоточных диалектов C#.
                  0
                  Маловато. У AMD-то настоящих (не HT) ядер поболе будет…
                    +1
                    Там ядро менее производительное. Тут настоящих уже 10.
                      +4
                      А вот можно я скепсис нарисую, насчёт того, какие у amd медленные ядра?

                      Кроме того, AMD уже анонсировала 16-ядерные решения. В 4 сокетах это уже 64 ядра.
                        0
                        Нарисуй, интересно. Я думал, что интел со своей Core «впереде».
                          –2
                          > Я думал

                          Ключевое слово.
                            0
                            Есть что по делу сказать?
                          +3
                          Вы же, конечно, не серьезно? В Interlagos 16 почти-ядер на 8 модулях в одном процессоре на максимальной частоте 1.8ГГц. Это раз. Они еще не вышли. Это два. Нужны хотя бы синтетические тесты с новинками от обоих компаний. Это три. Хороших выходных. Это четыре. 8)
                          • НЛО прилетело и опубликовало эту надпись здесь
                              +11
                              При чем тут побитовый сдвиг? ;)
                                +1
                                Это математический знак «много больше»
                          0
                          как говорил на конференции одной: Intel не гонится за количеством ядер, а гонится за производительностью
                            0
                            Тогда зачем intel изобрела HT, который позволяет сделать в два раза больше ядер, каждое из которых примерно в полтора раза тормознутее, чем обычные ядра (при загрузке)?

                            Противоречие…
                              0
                              Чтобы поднять на халяву производительность многопоточных приложений или системы в целом.
                          +8
                          Очень символично — вот мы тут сначала наколбасили многоядерную хрень, а теперь давайте подумайте как она взлетает.
                            +4
                            ну у спарков давно столько ядер. и как-то взлетают. 4 сокета в Т3, по 16 ядер, в каждом по 16 тредов итого 1024 треда для баловства.
                              –2
                              хотел бы я глянуть на «Диспетчер задач» с 1024 ядрами :D
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  +6
                                  не 1024, но тем не менее:
                                    +2
                                    Есть ощущение, что через несколько лет величиной для определения производительности процессора будут уже не герцы, а количество ядер, типа, новый процессор от бла-бла компании на 700 килоядер или, скажем, на 2,4 мегаядра :)
                                      +2
                                      уже так и есть, фактически.
                                      –2
                                      Крузис с пацанами запускали?
                                    0
                                    Если продолжить аналогию — взлетают без пассажиров на борту, ну а толку от этого баловства как вы его назвали?
                                      0
                                      почему без пассажиров. его на LDOMs делят. да и орокле съест сколько дашь.
                                  +2
                                  Да прикольно, но может что-то более близкое к реальной жизни придумать в качестве заданий? Зачем все эти задачи? Как их можно применить потом на таком сервере?
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                      0
                                      Ответил ниже. Обсуждаемо.
                                      +2
                                      Виртуализация. Чем больше ядер, тем выше scalability.
                                        0
                                        Ну, вы же писали, что CPU самый дешёвый ресурс. Не более ли правдоподобна ситуация, что память уже занята вся, а процессор можно втыкнуть ещё один, но нет смысла, так как он всё равно не будет задействован?
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                            +2
                                            М… Там есть ещё одна проблема, я пока не знаю как её количественно описывать, но суть проблемы в том, что не смотря на низкую загрузку процессора при большом числе виртуальных машин на хосте (>>100) наблюдаются неприятные эффекты увеличения задержек. Насколько я понимаю, это связано во-первых с cache trashing, во-вторых с чрезмерным количеством event'ов, которые проходят в dom0. Чем больше ядер, тем меньше это заметно.
                                              0
                                              Может это связано с возможностью контроллера прерываний распределять прерывания между ядрами?
                                          +2
                                          Хороший комментарий. Я как-то давным-давно уже поднимал этот вопрос.

                                          Прикладные задачи (математика, финансы, физика) неизбежно дадут фору тем, кто на подобных заданиях специализируется. Конкурс международный, а там «форы» очень не любят. Хотя, если есть действительно достойные задачки — запросто можно организовать локальный, русский конкурс.

                                          В данном раскладе конкурс скорее студенческо-аспирантский. Поэтому и задачки такие учебные. Хотя… Люди с учеными степенями тоже были замечены в участии.
                                            0
                                            Можно же как-то вывести проблему на общий уровень — чтобы фору нивелировать. Хотя ну что там можно придумать с многопоточностью, по сути мастерство распаралеливания алгоритмов решает.
                                              +1
                                              Тонкая материя. Постоянно сталкиваюсь с установкой «был бы алгоритм подходящий — как распараллелить придумаем». Собственно, для чего конкурс-то? Чтобы и алгоритм подходящий нашли, и как распараллелить придумали ;).

                                              Но я серьезно — нет проблем организовать другой конкурс, на базе специализированных задач. Только надо сесть и хорошенько подумать. А пока имеем то, что уже имеем.
                                                –1
                                                Да я не в претензии, просто было бы полезнее :) А ещё было бы интересны задачи по максимальной загрузке всех блоков процессора. Но не просто максимальной, а именно всех блоков. Не так уж и сложно дать нагрузку 100%, но вот чтобы работой были заняты все АЛУ, ФПУ, MMX/SSE регистры, чтобы гипертрединг грамотно задействовался и т.д. Насколько я помню программы проверки разгона процессоров умеют так нагружать. Измерять можно по потребляемой мощности или температуре процессора. Вот уж будет максимальная оптимизация.
                                          0
                                          Интересно как OpenCL себя покажет одновременно на такой системе плюс пару Nvidia Tesla?
                                            +4
                                            Моя гипотеза — завязнет намертво в перекидывании прерываний между ядрами. Шина-то общая.
                                            +1
                                            bitcoin можно генерить.
                                              +1
                                              включить генератор биткоинов в решения для заданий, не выиграл так хоть биткоинов нагенерил :)
                                              0
                                              и повернуть на 90 градусов в следующей ЛИБО в предыдущей ячейке (то есть хотя бы с одной стороны) странное противоречие, можно ли с двух сторон от белой поворачивать?
                                                0
                                                сорри, на примере увидел, можно
                                                  0
                                                  Да, можно. Раза три переписывал текст этого условия, но так и не добился предельной ясности формулировки ;)
                                                    0
                                                    Можно было написать «и/или»
                                                –1
                                                Извините, что почти оффтоп — а почему Xeon-ы, которые в русской транскрипции надо бы называть «ксеоны» очень многие называют «зеоны»? Чтобы сгазом не путать? То же самое с Xen-ом — многие говорят «Зен» вместо «Ксен».
                                                  0
                                                  Правильно читать — «зион» и «зен».
                                                    0
                                                    Типа так правильно по-английски. Xerox — он ведь тоже «зиракс». Что-то там с закрытыми и открытыми слогамих. Точно не скажу — учил не по учебникам ;)
                                                      +1
                                                      X в начале слова перед гласной читается как Z

                                                      И, кстати, неправильно название сериала «Xena: Warrior Princess» переводили. По идее должно быть «Зина: принцесса-воин».
                                                      0
                                                      У E7-4860 исходя из ark.intel.com/Product.aspx?id=53571&processor=E7-4860 10 ядер,
                                                      а на представленном скриншоте не 4*10 а 4*16.
                                                        0
                                                        Вобщето 5*16=80.
                                                          0
                                                          тогда да, 5*16=80=(4*10)/2
                                                        +2
                                                        Кстати, платформа интеловская? Сколько юнитов?
                                                          0
                                                          одной такой машинки мне бы хватило потянуть свой проект целиком, сейчас трудятся почти десяток на 2*Xeon 54**

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

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