Кластеризация на основе эффективности

Ключевые слова и синонимы

Разбиение схем; кластеризация схем

Постановка задачи

Процесс разбиения схемы заключается в разделении схемы на фрагменты, каждый из которых может быть реализован как отдельный компонент (например, чип), удовлетворяющий конструктивным ограничениям. Раджамаран и Вонг [5] рассматривают задачу разделения схемы на компоненты в соответствии с ограничениями по площади – такими как минимизация максимальной задержки на выходе.

Комбинационная схема может быть представлена в виде ориентированного ациклического графа G = (V, E), где V – множество вершин, а E – множество ориентированных ребер. Каждая вершина представляет вентиль в сети, а каждое ребро (u, v) из множества E – взаимодействие между вентилями u и v в сети. Обозначим за fanin («разветвление на входе») вершины количество инцидентных ей входящих дуг, а за fanout («разветвление на выходе») – количество инцидентных ей исходящих дуг. Первичным входом (primary input, PI) является вершина с fanin = 0, а первичным выходом (primary output, PO) – вершина с fanout = 0. С каждой вершиной ассоциированы вес и задержка.