Pull to refresh
0

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

Reading time 3 min
Views 33K
Коллега 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.
Tags:
Hubs:
+37
Comments 65
Comments Comments 65

Articles

Information

Website
www.intel.ru
Registered
Founded
Employees
5,001–10,000 employees
Location
США
Representative
Анастасия Казантаева