Еще с 1990-х годов меня поражало, что проектирование всей мировой цифровой микроэлектроники контролируется двумя конторами в Калифорнии, которые находятся в 10 минутах езды друг от друга — Synopsys и Cadence. В те времена четверть мирового проектирования делалось в Японии (континентальный Китай тогда находился в примитивном состоянии), и все эти Sony, Hitachi, Fujitsu и другие гиганты ездили на поклон в Америку и платили несчетные миллионы долларов за программы, которые потом использовали японские проектировщики. Сейчас это продолжается с Samsung, Huawei и даже с российскими конторами, которые проектируют микросхемы для космоса.
Русская земля умудрилась вырастить Yandex супротив Гугла, так почему бы и не попробовать создать какие-нибудь программы для проектирования микросхем? Начать можно с малого: популяризовать конкурсы и хакатоны по разработке алгоритмов автоматизации проектирования (Electronic Design Automation — EDA). Эти алгоритмы удобны тем, что у них много уровней сложности: простейшую программу Place & Route может написать студент за выходные, но вот на продвинутую потребуются десятилетия работы сотен людей и миллиарды долларов на R&D.
Сейчас в Иннополисе возле Казани делают мероприятие для студентов в формате «две недели подготовки + хакатон». Одной из тем стала традиционная задача EDA — размещение и трассировка графа электронной схемы на ряды стандартных ячеек. Будет интересно увидеть, что за это короткое время сможет осуществить небольшая команда студентов-программистов с базовым пониманием C++/Java/Python, методов парсирования текста, алгоритмов работы с графами и навыками визуализации структур данных с помощью GUI.
Итак — постановка задачи: