Трассировка silicon-а в формате хакатона. Без Physical Design не будет Айфона
Все смотрели фильм Дудя про стартапы Силиконовой Долины? А вы знаете, какой стартап Долины был самый силиконовый в 1977 году? Это был Silicon Valley Research, также известный как SVR и Silvar-Lisco. Стартап делал программы, которые автоматически размещали транзисторы на площадке чипа и соединяли их дорожками. Стартап вышел на биржу и даже дожил до 21 века, но не смог конкурировать с новыми лидерами — сначала Daisy/Mentor/Valid, а потом Synopsys и Cadence.
Программы, которые делал SVR, назывались программами размещения и трассировки, по английски Place & Route — P&R. Они сильно повысили производительность труда инженеров — до P&R программ чертежи маски чипа клеили из цветного картона (Intel 4004), рисовали карандашами на бумаге, или бегали курсором по текстовому экрану и соединяли плюсиками и минусиками элементарные блоки, которые изображались звездочками (так проектировали чипы в IBM/370-совместимых компьютерах Amdahl, продвинутых родственниках советских ЕС ЭВМ).
SVR основал профессор из Стенфорда Билл ван Климпат, которого я знал лично, так как он был ангел-инвестором и членом совета директоров моего собственного стартапа. Билл периодически воспитывал меня за плохое поведение на заседаниях и прокрастинацию, а также рассказывал байки про патентные суды, по которым он постоянно ходил в качестве эксперт-свидетеля.
Поэтому когда в казанском Иннополисе мне предложили организовать проект на их хакатоне для студентов по CASE Tools, я вспомнил Билла и предложил сделать на хакатоне минимальную программу трассировки. Этот пост — отчет о результатах этого экспериментального хакатона. Их также наверное стоит обсудить на zoom-конференции в Иннополисе по Open Source проектам, которая будет через неделю.
Понимание алгоритмов физического проектирования микросхем — это ключевая компетенция. Во всех группах по разработке микросхем (silicon development group) в Apple, NVidia, Intel, AMD, Cisco, Juniper, Huawei, Samsung, Tesla, Google, MediaTek, Broadcom — есть группа PD Team (Physical Design Team), которая работает с тулами от Synopsys и Cadence, которые делают это. Причем эти тулы сложные, в них больше тысячи команд и сотни подсистем, они обходятся каждой компании в миллионы или десятки миллионов долларов в год. Без наличия большего количества специалистов по PD (как на уровне юзеров, так и на уровне разработчиков custom PD tools) у России нет вообще никаких шансов стать значимой на международном рынке микросхем в смартфонах, ИИ ускорителях и самоуправляющихся авто. Примерно как у какой-нибудь африканской страны, в которой в вузах не учат биохимию, нет вообще никаких шансов стать лидером в лекарствах (каких-нибудь ингибиторах протизы) против короновируса.
Обсуждения и возражения
Мы обсудили идею P&R хакатона в рассылке silicon-russia, где к ней отнеслись с осторожным скепсисом. В частности мне возразил Михаил Шуплецов, который занимается алгоритмами EDA (Electronic Design Automation) на ВМК МГУ:
Михаил Шуплецов: «Есть сомнение, что формат Хакатона подходит для таких задач. Хороший результат по задачам автоматизации проектирования можно получить только, если соревнование идет продолжительное время (не менее 6-ти месяцев). В предложенном формате, на мой взгляд, можно будет только запустить готовые инструменты, но не создать какое-то новое решение.»
на что я ответил:
Юрий Панчул: «Я согласен, что для написания алгоритмов с приемлемой алгоритмической сложностью, capacity (способностью обрабатывать большие дизайны) и features (работая с реальными ASIC libraries) нужно время порядка шести месяцев. Но я не согласен, что формат хакатона не годится! Я лет 20 назад получил большое удовольствие, когда написал за викенд маленькие программки для floorplanning и для maze router. На Си и с визуализацией на Tcl/Tk. Без особых ухищрений, все по вводному учебнику по алгоритмам EDA. Это отличная тренировка в программировании для студентов младших курсов + это может заинтересовать копать область дальше.»
Урезание задачи или «Инжиниринг — это искусство возможного»
Задача заинтересовала трех студентов Иннополиса. Главная интрига была как урезать формулировку задачи, чтобы было реально ее выполнить быстро, за две недели подготовки и четыре часа хакатона. Исходная постановка задачи выглядела вот так. Она состояла из трех частей:
- Парсирования текстового файла на урезанном подмножестве языка описания аппаратуры Verilog.
- Применения древнего алгоритма волновой трассировки Ли.
- Графического вывода результата.
После обсуждения со студентами мы решили парсирование верилога заменить на упрощенный ввод координат ячеек из текстового файла. Дальше студенты распределили обязанности и ниже — их три отчета про эксперимент.
Параллельно со студентами я решил написать решение и сам, чтобы прикинуть, сколько это займет времени для одного человека. Студенты писали свое решение, используя объектно-ориентированные client-server фреймворки на Java и веб-графику. Я просто написал программку на Си, которая берет данные из инициализированного статического массива и выводит результат, печатая картинку звездочками и точками, как в программах 1970-х годов. Это заняло у меня 4 с половиной часа.
Код моей (не студенческой) программки
Полная выдача
Теперь предоставим слово студентам:
Отчет Софии Ермолаевой
Хакатон проходил среди студентов университета Иннополис 19го Октября 2019 года.
На выбор было представлено 11 кейсов, из которых каждый должен был выбрать 3 и расставить приоритет от наиболее предпочтительного до наименее предпочтительного.
По нашим предпочтениям и количестве людей выбравшим каждый кейс – организаторы формировали команды.
За неделю до хакатона меня и еще двух студентов распределили в проект от компании MIPS BU.
Изображение 1. Кейс от компании MIPS BU на сайте хакатона
Наша команда оказалась самой немногочисленной, в сравнении другие команды были 5-7 человек. Соответственно нам сразу стало понятно что скоуп задачи поставленный для выполнения в течении 8ми часов мы вряд ли осилим. Сложностью было еще и то, что у нас единственных был удаленный заказчик да еще и с 10 часами разницы во времени.
По правилам хакатона, после распределения команд разрешалось провести ряд встречи с заказчиком для выяснения требований и ознакомления с технологиями в случае если они являются не знакомыми для команд (что было применимо к нашей команде).
Мы впервые встретились с заказчиком 11 Октября 2019 года. Для встречи мы подготовили вопросы для проведения Elicitation Interview (еще во время подготовки вопросов мы понимали что совсем не понимаем как выполнить задачу, но от этого было еще интереснее). Первоначальный список вопросов представлен на Изображении 2. Пришлось очень много шерстить интернет для того чтобы получить какой-либо уровень знаний по теме.
Изображение 2. Elicitation interview questions.
Во время встречи у нас появились более подробный вопросы касающиеся решения (см. Изображение 3).
Изображение 3. Вопросы связанные с реализацией.
По итогам встречи мы выяснили собрали требования и их приоритеты чтобы было понятно каким образом нам уменьшить скоуп (см Изображение 4).
Изображение 4. Требования и их приоритеты собранные во время первой встречи.
Нас не покидало чувство что втроем за 8 часов это не успеть, мы поделились переживаниями с заказчиком. Оказалось что об ограничении в 8 часов он не знал. Поэтому мы вместе начали думать об упрощении задачи и о разработке прототипа.
Упрощения в основном коснулись функционального требования №1 (см. Изображение 4). В нашем итоговом Requirements Document требования к прототипу разделены по функциональности: File reader (см. Изображение 5), Placement (см. Изображение 6), Routing (см. Изображение 7), Graphical representation (см. Изображение 8). По правилам Requirements document нужно было заверить подписью заказчика, но так как у нас заказчик был удаленным подтверждение мы решили сделать по фото (см. Изображение 9).
Изображение 5. Требования к File Reader
Изображение 6. Требования к Placement
Изображение 7. Требования к Routing
Изображение 8. Требования к Graphical representation
[Изображение 9. Подтверждение требований заказчиком.]
После сбора требований мы начали продумывать особенности реализации и выбор технологий. Стоит отметить что наша команда состояла из: 1 С# разработчика (Михаил), 1 Python разработчика (Максим) и 1 Frontent разработчика (София). Для отображения мы выбрали React.js так как у меня было достаточно уверенности в том, что используя эту технология в короткий срок я смогу имплементировать отображение. Для остальных компонентов было тяжело выбрать технологию так как знания сильно разнились, мы сошлись на Java так как на этом языке у каждого был хотя бы минимальный опыт.
Мы разделили ответственность следующим образом:
- Отображение, связывание бэка и фронта, подготовка презентации, менеджмент команды – София,
- Placement и Routing – Михаил
- File reader – Максим.
Во время хакатона закaзчикам необходимо было презентовать кейсы, но в связи с разницей во времени (у нас было ранее утро а у заказчика поздняя ночь) мы продемонстрировали видео подготовленное заказчиком.
После презентаций мы направились кодить наше решение. Мы сидели вместе но каждый работал над своей частью (cм. Изображение 10). Конечно до Хаккатона мы тренировались писать алгоритм Ли для понимания его работы.
[Изображение 10. Мы с Михаилом работаем над решением задачи (Максим в кадр не попал но он тоже работал рядом).]
Для общения бэка и фронта я выбрала Spring. Для тестирования решения мы подготовили несколько примеров простых входных файлов (пример подобных файлов представлен на Изображении 11).
Изображение 11. Входящий файл и его отображение.
Тестирование на простых файлах отрабатывало так как мы ожидали. Проблемы возникли когда мы решили для красивой картинки на слайдах сделать пример посложнее. Я придумала пример представленный на Изображении 12. По не известным нам причинам алгоритм уходил в бесконечный цикл. До конца хакатона оставался час. Мы уже во всю работали над презентацией, так как ее нужно было еще и прогнать для качественного выступления. Пока я работала над презентацией, мои сокомандники выяснили что в бесконечный цикл программа попадает не каждый раз, то есть при запуске на одном и том же файле – программа иногда все же работает. Мы поняли что наше решение не стабильно. Но времени исправлять уже не было. Подтверждением не стабильности алгоритма стало еще и то, что построение схемы для одного и того же файла было разным (см. Изображение 13).
Изображение 12. Пример придуманный во время хакатона для демонстрации работы алгоритма.
Изображение 13. Вывод для второго примера (во время хакатона и после хакатона).
Хакатон мы не выиграли. Стоит отметить что остальные кейсы были связаны с анализом качества и с тестированием продуктов, в то время как мы реализовывали решение с нуля. Мы были белыми воронами на хакатоне. По правде говоря, я этому очень рада, так как полученный опыт был очень полезным.
[Изображение 14. Презентация нашего решения на хакатоне.]
[Изображение 15.Наша команда с сертификатами об участии.]
[Изображение 16.Наша команда участвует в оценивании других кейсов.]
Post mortem
После хакатона мы отправили свое решение заказчику в качеcтве ссылки на гит.
4го Ноября я получила письмо от заказчика о том что у него не удается запустить наш проект. Проблема была в том что мы разрабатывали на MacOS и Windows, соответственно инструкцию мы тоже писали исходя из того как мы запускали на своих платформах.
Изображение 17. Изначальная инструкция по запуску приложения.
Заказчик пытался запустить через консоль и получал следующую ошибку:
Изображение 18. Ошибка №1.
Воспроизвела все ошибки и проблема оказалась в том что для запуска проекта через консоль как jar необходимо было добавить manifest файл чтобы maven знал какой из файлов является main классом. Так что я добавила конфигурационные файлы и отправила обновление заказчику.
Следующее письмо от заказчика пришло 15го Апреля 2020го года. У заказчика во время сборки проекта появлялась следующая ошибка:
Изображение 19. Ошибка №2.
Мне пришлось снова разбираться с проектом. После нескольких часов проб и ошибок все же удалось выяснить проблему. Оказалось что javafx.util.Pair даже при добавлении библиотеки javafx.util как зависимости в pom.xml при сборке не добавляеться в проект. После гугления оказалось что такая проблема есть у всех пользователей данной библиотеки. Сперва я пыталась разными способами решить эту проблему, но в результате оказалось проще имплементировать класс вручную. Оказалось что в Python (а именно Python разработчик из нашей команды работал над этой частью) подобные классы используются как стандартное решение, но в Java для хранения ключ-значение существует множество других структур данных (HashMap etc.). В результате мой код для Pair который помог все исправить выглядел следующим образом:
Изображение 20. Pair implementation.
После того как я исправила ошибку, решила написать подробную инструкцию по запуску приложения через консоль. После тестирования инструкции. Мы созвонились с заказчиком и запустили проект. Вот так спустя 5 месяцев заказчик смог увидеть плоды нашей работы.
Изображение 21. Финальная инструкция по запуску проекта.
Начальная версия проекта находится в репозитории на гитхабе.
Финальная версия проекта находиться в моей репозитории github.
Отчет Максима Костина
После изучения всех требований к проекту, мы разделили задачу на 3 основные части.
Я был ответственен за обработку входного файла и упаковку его в удобный, для дальнейшей обработки формат. Самой очевидной и удобной структурой данных для этой задачи, на мой взгляд, можно считать граф (вершинами мы представляем элементы, а рёбрами соединения между ними).
Реализовать граф можно разными способами, но для данной задачи Я выбрал вариант реализации графа на списках (реализация графа на матрице смежностей получилась бы довольно разряженной и расходовала бы большее количество памяти, хотя и обходя граф на списках по скорости в операциях добавления рёбер).
Изначально планировалось обрабатывать входные файлы, написанные с использованием синтаксиса языка Verilog, но в дальнейшем мы опустили этот аспект, и начали использовать упрощённый формат входных данных.
Так же мы сделали ряд упрощений (из-за ограничения на время хакатона) на размеры элементов (мы считали все элементы одинаковыми по размеру), полное упрощение на физическую природу элементов (задержки сигналов, влияние от соседних ячеек, энергопотребление — к каким-то элементам подходят более толстые дорожки и прочее).
В целом, критичных ошибок в реализации самого графа не было, но в процессе парсинга файла возник ряд ошибок по невнимательности, так, например для элемента NOT изначально было создано два входа (очевидно программа крашилась).
Так же возник ряд мелких ошибок (неправильно был указан размер подложки) при объединении с кодом Михаила (Михаил занимался размещением элементов графа на подложке, и трассировкой), но в целом всё решилось «быстро и безболезненно». Михаил написал очень хороший код, который позволил ощутимо быстро приблизится к цели.
Но у нас с Михаилом ничего бы не получилось, не будь в нашей команде Софии. Она не побоялась, и взяла на себя самую важную часть — визуализацию результатов (то, без чего наш проект практически не имел бы смысла), и замечательно справилась с поставленной задачей.
В целом, за время работы над проектом Я узнал много новой и полезной информации о том, как создаются печатные платы и SoC, а также какие алгоритмы и люди стоят за этим. Я уверен, что данный навык может пригодится мне в дальнейшем, т.к. Я периодически балуюсь с электроникой и иногда собираю разного рода прототипы. Теперь же Я смогу использовать нашу программу, что бы сделать трассировку дорожек, и посмотреть как это может выглядеть в реальности.
Отчет Михаила Шейнберга
Причиной моего выбора данного проекта была его связь с примером из книги Эрика Эванса “Предметно ориентиованное прогамирование” которую я на тот момент читал. Хотя забегая вперед можно сказать что никакого серьезного применения моим знаниям о DDD, и опыту из примера приведенного в книге на хакатоне не нашлось, я считаю что опыт полученный на хакатоне был полезным и интересным для меня.
После изучения всех требований к проекту, мы разделили задачу на 3 основные части.
Я был ответственен за построение схемы, Максим взял на себя написание парсера а софия взяла ответственность за визуализацию результатов.
Совмсестно с командой и заказчиком нами был выбран алгоритм Флойда для оптимального размещения проводов на схеме. Для хранения построенной схемы была использована трехмерная матрица где координатой по вертикали выступал номер слоя. Совместно с командой было принято упрощение — каждому элементу схемы придаваля размер 5х5 клеток и пространством между элементами в 3 клетки. Принятые упрощения были связанны со временем хакатона (оно было ограниченно) и ограничением в свободном времени до начала хакатона (в раене хакатона был ряд курпных асайментов которые тоже нужно было сделать).
В поцессе объединения результатов моей работы с результатами работы Максима возник ряд досадных проблем возникших по причине спешки и невнимательности связанных с ограниченностью сроковкоторые к счастью были быстро обнаруженны и устранены.
Отдельно хочется отметить качество визуалтзации выполненое Софией. Ее часть рботала без ошибок и дала хороший материал для информативной презентации результатов.
В целом, за время работы над проектом я узнал много новой и полезной информации о том, как устроен процесс построения микросхем и используемых в этой сфере алгоритмах, которые смогу применить в будущем.
Приложение A: Возражение Михаила Шуплецова из МГУ (на снимке слева)
Команда Михаил Шуплецов из МГУ выиграла престижное международное соревнование IC-CAD 2015, причем информация об этом вызвала эмоциональную реакцию даже у бывшего посла США в России Майкла Макфола.
Из обсуждения в рассылке silicon-russia.
Михаил Шуплецов: Уже было высказано несколько предложений от коллег, что имеет смысл брать за основу существующие проекты. На мой взгляд, стоит упомянуть о многолетнем опыте проведения подобных соревнований в рамках международных конференций:
1. http://iccad-contest.org
2. http://www.ispd.cc/?page=contestsВ рамках этих соревнований студенческие команды из разных стран уже предложили множество инструментов для решения отдельных задач автоматизации проектирования (как логического, так и физического). Есть проект, который интегрирует все эти инструменты в рамках одного маршрута проектирования:
1. https://arxiv.org/pdf/1810.01078.pdf
2. https://github.com/jinwookjungs/datc_robust_design_flowСчитаю, что инициатива проведения соревнований по разработке алгоритмов автоматизации проектирования является очень полезной. У меня самого есть опыт руководства командами, которые участвовали в подобных соревнованиях. Мне самомы было бы интересно поучаствовать в качестве организатора подобных соревнований.
Единственное, что немного расстроило, что пост о мероприятии в Иннополисе появился уже после того, как регистрация на мероприятие завершилась. Так же есть сомнение, что формат Хакатона подходит для таких задач. Хороший результат по задачам автоматизации проектирования можно получить только, если соревнование идет продолжительное время (не менее 6-ти месяцев). В предложенном формате, на мой взгляд, можно будет только запустить готовые инструменты, но не создать какое-то новое решение.
И второе:
Уважаемый Юрий!
Спасибо за лестные слова в мой адрес. Хотя я все же более скромно оцениваю свои заслуги. Мне во многом повезло найти талантливых студентов, которым было интересно участвовать в соревнованиях и было желание победить. Честно говоря, в последнее время искать студентов стало намного сложнее в связи с большей популярностью других направлений (машинное обучение и искусственный интеллект) и больших призовых сумм, в рамках соревнований по этим направлениям.
Думаю, что в группы смогу написать, хотя для меня этот формат немного непривычный.
На счет Хакатонов. У каждого формата есть свои плюсы и минусы. В текущей ситуации, на мой взгляд, любые начинания в области EDA в России имеют смысл и будут в чем-то полезны. Я под впечатлением от названия статьи отметил, что для задач из области EDA больше подходит формат долгосрочных соревнований, который показал свою состоятельность в рамках ICCAD и ISPD. При этом я понимаю, что в России пока может и не быть достаточной инфраструктуры для проведения подобных соревнований (хотя тоже момент спорный). Если помечтать, то было бы интересно увидеть в будущем соревнование в России подобное соревнованиям в формате ICCAD и ISPD под эгидой, например, конференции МЭС (http://www.mes-conference.ru/) и при поддержке компаний, которые занимаются проектированием интегральных схем и EDA.
С наилучшими пожеланиями,
Михаил
Приложение B: Инструкция Софии Ермолаевой как воспроизвести результаты
Required:
Maven
Npm
Clone repository
git clone https://github.com/keepYourHairOn/HackathonProject.git
In the repository folder:
cd edap
cd ASICdrawer
npm install
npm start
In the browser open:
localhost:8008
In the new tab of the command line (because node should stay working).
To build new jar:
cd edap
mvn package
Copy input.txt file from {repository folder}/edap/input.txt and paste a file into: edap/target
To run the existing jar:
cd target
java -jar edap-1.0-SNAPSHOT.jar
Ссылки
Над Силикон Вэлли заходит солнце, а над Иннополисом восходит, на чем я свою речь прекращаю. А вы что думаете?
