Кластеризация на основе эффективности: различия между версиями

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

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

'''Определение''' 2. Пусть дана комбинационная сеть G = (V, E) с весовой функцией <math>w: V \to R^+ \;</math>, весовой емкостью M и функцией задержки <math>\delta: V \to R^+ \;</math>. Мы говорим, что кластеризация <math>\Gamma = (H, \phi, \Sigma ) \;</math> является '''допустимой''', если для каждого кластера <math>C \in \Sigma \;</math> значение W(C) не превышает M. '''Задача кластеризации схемы''' заключается в вычислении допустимой кластеризации <math>\Gamma \;</math> сети G, такой, что задержка <math>\Gamma \;</math> минимальна среди всех допустимых кластеризаций G.

* ''[[Технологическое отображение ППВМ]]

[[Категория: Совместное определение связанных терминов]]== Литература ==