Хабрахабр

Расставляем стандартные ячейки (заметки постороннего)

Натолкнувшись на статью “Уничтожим монополию …”, автор, как человек пусть от EDA очень далёкий, но от природы любознательный, не поленился пройтись по ссылкам и невольно поймал себя на мысли, что одно из основных технических решений — использование рядов стандартных ячеек (standard cell layout) — выглядит довольно спорно.

С другой стороны, при этом возникает непростая комбинаторная задача, требуется разрезать схему на линейные куски и расположить эти куски таким образом, чтобы (грубо) минимизировать общую длину соединений. Да, такое расположение интуитивно понятно, ведь мы пишем и читаем похожим образом, кроме того, технологически просто располагать ячейки именно рядами, так удобно стыковать шины VDD и GND.

И конечно же возник вопрос, нет ли альтернативных решений, … вот что если …

Фиг.1 типичные ряды стандартных ячеек (отсюда)

А что если

С точки зрения уменьшения общей длины связей было бы полезно расположить стандартные ячейки вдоль какой-то из заметающих кривых ex: Пеано или Гильберта.

Эти кривые состоят из массы разнообразных “закоулков”, наверняка есть конфигурация в которой связанные стандартные ячейки в среднем окажутся недалеко друг от друга.
Или это может служить нулевой итерацией для дальнейшей оптимизации.

Фиг.2 Кривая Гильберта, поля 8X8 и 64X64

  1. Заметающие кривые самоподобны, что хорошо укладывается в общую концепцию.
  2. Они имеют высокую локальность т.е. точки, находящиеся где-то рядом на кривой скорее всего находятся недалеко и в пространстве.
  3. Содержат иерархически организованную сеть каналов.
  4. Для логической схемы можно подобрать подходящий квадрат или прямоугольник 1х2,2х1, в котором она размещается с избытком и «подвигать» ее вдоль заметающей кривой (см. Фиг.3) чтобы подобрать оптимальную геометрию, ведь это всего одна степень свободы с довольно дешевой функцией стоимости.
  5. Сохранится удобство стыковки шин (VDD/GND).

Фиг.3 Три куска кривой Гильберта с разными сдвигами.

Итак:

  • экспериментировать будем с кривой Гильберта
  • экспериментировать будем в квадрате 64X64 (Фиг.3)
  • в элементарном шаге кривой может быть несколько стандартных ячеек и пробелов — сколько именно и в каком порядке — параметр эксперимента
  • все элементарные шаги устроены одинаково
  • элементарные шаги идут с нахлёстом т.е. если шаг начинается со стандартной ячейки, в конце его должен быть пробел, и наоборот
  • все пробелы и стандартные ячейки имеют один размер — 1X1
  • все ячейки сериализованы в каком-то порядке, этот порядок тоже является параметром
  • еще один параметр — сдвиг от начала кривой (точки (0,0)), начиная с которого мы будем располагать стандартные ячейки в определенном порядке
  • длины связей между стандартными ячейками считаются по L1 (манхэттенское расстояние)
  • сумма длин всех связей и является искомой величиной, определив минимальную сумму мы и найдем оптимальное расположение

А в качестве подопытного кролика возьмём 8-разрядный сумматор. Он достаточно прост, но не тривиален. В нём достаточно много элементов и связей, чтобы почувствовать потенциальные плюсы и минусы. В тоже время их достаточно немного для того, чтобы можно было экспериментировать “на коленке”.

Сумматор

Фиг.4 принципиальная схема полного одноразрядного сумматора

Фиг.5 Так видит это граф утилита Neato из graphwiz

Фиг.6 8-разрядный знаковый сумматор, взято здесь

Но мы будем работать только с целыми числами, без флага ошибки W.

Фиг.7 Так 8-разрядный сумматор видит утилита dot из graphwiz.

Выглядит как танец маленьких лебедей.

Фиг.8 тот же граф после оптимизации с помощью neato.

граф в формате DOT

digraph sum8

Эксперимент 1

  • элементарный шаг кривой Гильберта — (пропуск, ячейка, ячейка, пропуск)
  • вершины графа (элементарные ячейки) отсортированы по алфавиту

Фиг.9 по X — сдвиг от начала, по Y — длина всех путей

Минимальное расстояние (первое из) при сдвиге 207 (Общая длина всех связей — 1968), посмотрим как выглядит это оптимальное расположение.

Фиг.10 оптимальный граф для сдвига 207, выглядит не очень красиво.

Эксперимент 2

  • элементарный шаг кривой Гильберта — (пропуск, ячейка, ячейка, пропуск)
  • вершины графа (элементарные ячейки) в естественном порядке (как пришло в описании графа, см. описание графа выше) -

Фиг.11 по X — сдвиг от начала, по Y — длина всех путей

Фиг.12 оптимальный граф для сдвига 11 длина 750

Эксперимент 3

  • элементарный шаг кривой Гильберта — (пропуск, ячейка, ячейка, пропуск)
  • порядок вершин определён обходом графа в ширину, вершины без ссылок в начале списка, выходные — в конце

Фиг.13 по X — сдвиг от начала, по Y — длина всех путей

Фиг.14 Оптимальное расположение — сдвиг 3, общая длина 1451
Расположить все input вершины в начале, а output — в конце было не очень хорошей
идеей.

Эксперимент 4

  • элементарный шаг кривой Гильберта — (пропуск, ячейка, ячейка) Sic!
  • порядок вершин естественный, как в эксперименте 2

Фиг.15 по X — сдвиг от начала, по Y — длина всех путей

Фиг.16 Оптимальное расположение — сдвиг 10, общая длина 503

Эксперимент 5

С IO надо что-то делать, определим их в пост-процессинге, т.е. для каждого сдвига
построим расположение без IO вершин, потом построим поглощающий экстент-рамку вокруг графа, нанесем IO вершины на ближайшую незанятую точку рамки и посчитаем финальную длину

  • элементарный шаг кривой Гильберта — (пропуск, ячейка, ячейка)
  • порядок вершин определяется просмотром в ширину, но без IO вершин

Фиг.17 по X — сдвиг от начала, по Y — длина всех путей

Фиг.18 Оптимальное расположение — сдвиг 607, общая длина 484, средняя 3.33793

У них размерность разная, поэтому будем считать, что подсчитываем не длину пути, а площадь под путями. Выглядит неплохо, а что если оптимизировать не общую длину путей, а её сумму с площадью занятого прямоугольника.

Эксперимент 6

Параметры те же что и в эксперименте 5, оптимизируем площадь.

Фиг.19 по X — сдвиг от начала, по Y — длина всех путей

Фиг.20 Оптимальное расположение — сдвиг 966, общая длина 639, средняя 3.30345

А что если учитывать не площадь прямоугольника, а квадрат гипотенузы, подталкивая к более квадратным формам? Прямоугольник получился довольно вытянутым.

Эксперимент 7

Параметры те же что и в эксперименте 5, оптимизируем квадрат гипотенузы.

Фиг.21 по X — сдвиг от начала, по Y — длина всех путей

Фиг.22 Оптимальное расположение — сдвиг 70, общая длина 702, средняя 3.46207

Выводы

Предварительный “выбор редакции” — эксперимент 6.

Было бы неплохо упорядочить IO-вершины, но для этого нужна подсказка со стороны,
где именно (направление) следует расположить данный класс вершин.

Но прежде хотелось бы услышать мнение специалистов.

S.: спасибо YuriPanchul и andy_p за отсутствие рефлекторной отрицательной реакции. P.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть