iCTS: Iterative and Hierarchical Clock Tree Synthesis With Skew-Latency-Load Tree [
ссылка]
Прикольная статья, в которой китайцы предлагают интересный метод оптимизации тактового дерева.
Если кратко, то синхронная цифровая схема держится на одном допущении: каждый триггер видит фронт тактового сигнала одновременно (иначе данные защёлкнутся раньше, чем вычисление закончилось, и триггер захватит некорректный результат).
Но "одновременно" физически невозможно. Сигнал идёт от одного источника до тысяч триггеров по металлическим проводам с сопротивлением и емкостью, разные триггеры находятся на разном расстоянии, и сигнал приходит в разное время (эта разница называется skew).
Решение - буферы. Они восстанавливают деградировавший фронт и добавляют контролируемую задержку, и если вставить буферы в нужных точках сети, суммарная задержка по всем путям выравнивается и каждый триггер получает фронт в +/- одно и то же время. Собственно, автоматическое построение такого дерева буферов и называется Clock Tree Synthesis.
Звучит как инженерная задача с однозначным решением, но внутри три цели, которые конфликтуют между собой: минимальный skew, минимальная длина проводов и минимальная latency. Получить всё три одновременно - NP-hard.
Стандартный CTS flow разбит на два независимых шага без обратной связи: сначала DME (алгоритм балансировки топологии тактового дерева) фиксирует структуру дерева: где провода соединяются и как ветвятся. Потом отдельный алгоритм (как правило, ван Гинекен) вставляет буферы уже в готовую структуру: обходит дерево снизу вверх, в каждом узле оценивает варианты буферов с учётом ёмкостной нагрузки downstream и выбирает лучший. Топологию изменить уже нельзя, поэтому алгоритм подстраивается под то, что есть.
Чтобы выровнять задержки на коротких ветках, DME добавляет wire elongations - буквально удлиняет провода змейкой, из-за чего растёт ёмкость и мощность. Буферы потом сайзятся под худший случай нагрузки, часто избыточно.
И это бьёт не только по мощности. Буферы занимают площадь кристалла, тактовые провода съедают ресурсы роутинга, рядом с кластерами буферов нужны decap-ячейки. Место, которое могло быть вычислениями, занято инфраструктурой доставки сигнала.
Тактовое дерево переключается каждый такт, независимо от того что делает логика. На высокопроизводительных процессорах это может отъедать до 50% от TDP, то есть если чип греется на 100 Вт, то до 50 Вт уходит только на доставку тактового сигнала, а не на вычисления (пара статей про это - [
тык], [
тык], [
тык])
Исследователи из CUHK и Pengcheng Lab предложили строить топологию и буферизацию одновременно с явным trade-off между skew, latency и wirelength. В классическом DME точка слияния двух поддеревьев единственная, где задержки выравниваются, и никакого выбора нет. iCTS расширяет это до отрезка допустимых точек слияния, где любая точка даёт skew в пределах заданной границы, и на этом отрезке алгоритм выбирает точку, минимизирующую сумму с явными весами для latency и wirelength.
Поверх этого иерархическая кластеризация группирует синки не по геометрической близости, а по ёмкостной нагрузке, потому что физически близкие синки могут нагружать дерево по-разному и ломать балансировку. Результат кластеризации дополнительно оптимизируется отжигом. Буферы оцениваются до вставки, что позволяет отсекать плохие варианты раньше. После буферизации ISCA итеративно перезапускает BST-DME на зафиксированной топологии, каждый раз уточняя оценки задержек, пока skew не достигает целевого значения.
На бенчмарках ISCAS'89, OpenLane, OpenCores и ysyx (от 1248 до 22810 flip-flop) при 28nm результат такой: коммерческий P&R инструмент проигрывает iCTS на 39.5% по skew, 13.0% по latency и 18.5% по capacitance, OpenROAD - на 101.6%, 50.7% и 25.5% соответственно. По clock power коммерческий инструмент потребляет в среднем на 32% больше, OpenROAD - на 81% больше.
Хоть в максимальном бенчмарке всего ~23к триггеров, иерархическая архитектура iCTS должна масштабироваться. Не знаю, применит ли это кто-нибудь в продакшене, но звучит многообещающе
