Компания
341,11
рейтинг
22 апреля 2011 в 20:13

Разное → Начинаем конкурс параллельного программирования 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.
Автор: @DmitryO
Intel
рейтинг 341,11

Комментарии (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**

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

Самое читаемое Разное