Микроэлектроника, 2022, T. 51, № 1, стр. 71-79

1. ВВЕДЕНИЕ

Стандартные методы проектирования в базисе ПЛИС и реконфигурируемых систем на кристалле предполагают использование унифицированных трассировочных элементов, таких, как проходные ключи или ключи с буферами на выходе. Наличие в гетерогенных схемах сложно-функциональных блоков, блоков памяти, блоков логических элементов и др. приводит к необходимости применения различных вариантов трассировочных ресурсов, включающих, наряду с проходными ключами и буферами, более сложные элементы, реализующие логические функции инвертора, мультиплексора, буфера с третьим состоянием и пр. Это приводит к размыванию границы между этапами логического синтеза и топологического синтеза в классическом понимании этих задач. В этом случае этап топологического синтеза включает по необходимости решение задач логического ресинтеза [1] на этапе трассировки или после него, что требует разработки новых математических моделей и новой формализации задачи трассировки с элементами логического ресинтеза.

Разработка архитектуры проблемно-ориентированных гетерогенных программируемых логических интегральных схем и реконфигурируемых систем на кристалле представляет собой актуальную сложную задачу, решать которую нужно при условии жестких технологических ограничений и экономических требований [2–5]. Методам и моделям, используемым в процессе создания новых архитектур, посвящен ряд научных исследований [6–9]. В подходе, используемом в данной работе, при поиске архитектуры проблемно-ориентированных кристаллов ПЛИС и реконфигурируемых СнК предполагается учитывать конкретные задачи и специфику целевого потребителя путем внедрения специального этапа программного прототипирования.

Программное прототипирование представляет собой новый этап в маршруте проектирования гетерогенных программируемых логических интегральных схем и реконфигурируемых систем на кристалле. Этот этап позволяет использовать набор типичных пользовательских проектных схем в качестве основы для определения базовых параметров архитектуры кристаллов от производителя. Реализация этого этапа на основе имеющихся программных средств проектирования на ПЛИС становится мотивацией для исследования и разработки новых математических моделей, методов и средств для автоматической настройки САПР на изменения архитектуры проектируемого базового кристалла с учетом потребностей конечного пользователя.

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

Далее, приведены основные обозначения и термины обобщенного описания базового проекта реконфигурируемой или программируемой гетерогенной системы и пользовательских проектируемых схем от конечного заказчика, функциональность которых требуется запрограммировать в кристалле от производителя. Предложено формальное описание коммутационных ресурсов базового кристалла, выполнена постановка задачи трассировки пользовательской схемы. Рассмотрены некоторые аспекты определения трассируемости пользовательских схем в базисе гетерогенной ПЛИС или реконфигурируемой СнК.

2. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ И ТЕРМИНОЛОГИЯ ДЛЯ ОПИСАНИЯ БАЗОВОГО КРИСТАЛЛА И ПРОЕКТНОЙ СХЕМЫ

Обобщенное иерархическое описание проекта (как базового кристалла, так и пользовательской схемы) можно определить как триплет $\Pi = \left( {S,~L,~{{s}_{m}}} \right)$, где $S = \left\{ {{{s}_{i}},~~~i = 1, \ldots ,\left| S \right|} \right\}$ – множество схем в иерархическом описании проекта; $L \subset S$ – базис или подмножество базисных библиотечных подсхем для текущего уровня (или этапа) проектирования; ${{s}_{m}} \in S,~~{{s}_{m}} \notin L$ – главная схема или схема верхнего уровня.

Каждое из схемных описаний в иерархии проекта можно определить кортежем длины 5:

где $\mu \left( s \right)$ – уникальное имя схемы (строка символов); $E\left( s \right) = \left\{ {{{e}_{i}},~~~i = 1, \ldots ,\left| {E\left( s \right)} \right|} \right\}$ – множество элементов в схеме; $N\left( s \right) = \left\{ {{{n}_{i}},~~~i = 1, \ldots ,\left| {N\left( s \right)} \right|} \right\}$ – множество цепей (электрических узлов) в схеме; $P\left( s \right) = \left\{ {{{p}_{i}},~~~i = 1, \ldots ,\left| {P\left( s \right)} \right|} \right\}$ – множество внешних выводов схемы; $~C\left( s \right) = \left\{ {{{с}_{i}},~~~i = 1, \ldots ,\left| {C\left( s \right)} \right|} \right\}$ – множество соединений (коммутаций) схемы.

Множество элементов схемы может быть представлено как:

где $\mu \left( e \right)$ – уникальное имя элемента (строка символов); $m\left( e \right) \in S$ – модель элемента, представленная в иерархическом описании схемой более низкого уровня иерархии; $P\left( e \right) = \left\{ {{{p}_{i}},~~~i = 1, \ldots ,\left| {P\left( e \right)} \right|} \right\}$ – множество выводов элемента, совпадающее по составу с множеством внешних выводов модели, связанных с ним взаимно-однозначным соответствием

Множество внешних выводов схемы описывается следующим образом:

где $\mu \left( p \right)$ – уникальное имя вывода; $\tau \left( p \right) \in \left\{ {{{\tau }_{{inp}}},{{\tau }_{{out}}},{{\tau }_{{bi}}}} \right\}$ – тип вывода: вход, выход или двунаправленный.

Множество цепей схемы характеризуется именем $\forall n \in N\left( s \right){\kern 1pt} :~~\mu \left( n \right)$ и соответствующим цепи набором соединений $C\left( s \right)$, определяемым как подмножество пар:

Для любого контакта цепь единственная или не существует вовсе, таким образом, множество соединений в схеме определяется как однозначное отображение:

При этом обратное отображение определяет собственно список соединений конкретной цепи и не может быть однозначным – количество соединений у каждой цепи должно быть не менее двух, в противном случае цепь будет считаться ошибочной или ложной:

Как правило, внешний вывод может быть у цепи только один:

Для текущего этапа проектирования подсхемы базисного библиотечного уровня не содержат внутренних данных и представляют собой “черные ящики”:

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

В библиотеке L базового проекта следует выделить логические элементы ${{L}_{{LE}}}$, периферийные элементы ввода-вывода ${{L}_{{IO}}}$, сложно-функциональные макроблоки ${{L}_{M}},$ трассировочные элементы ${{L}_{{Ro}}}$ и иные вспомогательные элементы ${{L}_{{BB}}}$, не содержащие в своем составе элементов перечисленных типов ${{L}_{{LE}}},~~{{L}_{{IO}}}$, ${{L}_{M}},$ ${{L}_{{Ro}}}$, выполняющие вспомогательные функции (например, для программирования памяти), не связанные с непосредственным отображением элементов пользовательской проектируемой схемы:

Иерархическое описание проекта может быть преобразовано в соответствующее ему “плоское” представление путем рекурсивной процедуры раскрытия. Для заданного проекта ${\text{П}} = \left( {S,~L,~{{s}_{m}}} \right)$ в “плоском” представлении целесообразно сохранить только те подсхемы, которые фактически применялись в главной схеме ${{s}_{m}}$. Обозначим через $\varphi \left( {s,{{s}_{t}}} \right)$ логическую функцию, определенную на Декартовом произведении $S \times S$, принимающую значение 1 тогда и только тогда, когда $s$ фактически используется в s_t:

т.е.

Таким образом, для заданного ${\text{П}} = \left( {S,~L,~{{s}_{m}}} \right)$ проекта “плоское” ${{{\text{П}}}_{f}}({\text{П}}) = \left( {{{S}_{f}},~{{L}_{f}},~{{s}_{f}}} \right)$ представление можно построить по следующим правилам:

Имена элементов $\mu (e),e \in E({{s}_{f}})$ и имена цепей $\mu (n),n \in N({{s}_{f}})$ в “плоском” представлении должны быть уникальными и содержать информацию об именах элементов более высоких уровней иерархии, в состав которых входили подсхемы, содержащие рассматриваемый элемент, до раскрытия иерархии. Это достигается, например, за счет конкатенации имен элементов иерархии с использованием уникального разделителя.

3. ТЕОРЕТИКО-ГРАФОВАЯ МОДЕЛЬ ОПИСАНИЯ КОММУТАЦИОННЫХ РЕСУРСОВ ГЕТЕРОГЕННОЙ ПРОГРАММИРУЕМОЙ ИС

В соответствии с введенной терминологией для отображения цепей и коммутаций пользовательского проекта применяются элементы подсхем базового проекта $e{\kern 1pt} :m\left( e \right) \in {{L}_{{Ro}}}$. Как и схемы библиотечного уровня $s \in {{L}_{{LE}}} \cup {{L}_{{IO}}} \cup {{L}_{M}} = L{{\backslash }}\{ {{L}_{{BB}}} \cup {{L}_{{Ro}}}\} $, элементы трассировки могут программироваться. Принципиальное отличие состоит в том, что библиотечные элементы могут быть запрограммированы и характеризованы однократно для различных вариантов пользовательских схем. В то же время трассировочные элементы программируются индивидуально под конкретный набор коммутаций пользовательского проекта:

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

При этом элементы ${{s}_{u}} \in {{L}_{u}}$, ${{s}_{u}} = \left( {\mu \left( {{{s}_{u}}} \right),~\not {0},\not {0},P\left( {{{s}_{u}}} \right),\not {0}} \right)$ пользовательской библиотеки ${{L}_{u}}~$ проекта ${{{\text{П}}}_{u}} = \left( {{{S}_{u}},~{{L}_{u}},~{{s}_{{mu}}}} \right)$ реализованы путем установки следующих соответствий для выводов библиотечных схем базового кристалла $P\left( s \right) = \left\{ {{{p}_{i}},~~~i = 1, \ldots ,\left| {P\left( s \right)} \right|} \right\},~~s \in {{L}_{{LE}}} \cup {{L}_{{IO}}} \cup {{L}_{M}},$

где ${{P}_{0}},{{P}_{1}},{{P}_{z}}~$ – условные обозначения вводов, предполагающие внешние соединения с узлом земли, питания или висячим узлом, соответственно. При этом обратное отображение $~P\left( {{{s}_{u}}} \right) \to $ ${{P}_{r}}\left( s \right)$ не обязательно однозначно и может отражать различные варианты внешних подключений.

Следовательно, не только каждому элементу пользовательской схемы поставлен в соответствие элемент базового проекта, но и каждому контакту (выводу) библиотечного элемента пользовательского проекта поставлены в соответствие контакты $P\left( {{{e}_{i}}} \right)~$ библиотечных элементов базового проекта ${{e}_{i}} \in E\left( {{{s}_{f}}} \right)$, и, следовательно, узлы базового проекта:

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

По аналогии со схемами библиотечного уровня, множество внешних выводов трассировочных элементов $P\left( s \right) = \left\{ {{{p}_{i}},~~~i = 1, \ldots ,\left| {P\left( s \right)} \right|} \right\},~~s \in {{L}_{{Ro}}}$ можно разделить на два независимых подмножества по функциональному назначению: $P\left( s \right) = {{P}_{r}}\left( s \right) \cup {{P}_{m}}\left( s \right)$, где ${{P}_{r}}\left( s \right)$ – подмножество сигнальных или трассировочных выводов для соединения трассировочных элементов между собой и с выводами библиотечных элементов базового проекта; ${{P}_{m}}\left( s \right)$ – подмножество программируемых выводов для управления проводимостью трассировочных элементов путем назначения логических элементов программируемой памяти: ${{P}_{m}}\left( s \right) \to {{\mathcal{B}}^{{\left| {{{P}_{m}}\left( s \right)} \right|}}}$, $\mathcal{B} = \left\{ {0,1} \right\}$. Кроме того, среди сигнальных или трассировочных выводов $p \in {{P}_{r}}\left( s \right)$ следует различать выводы по направлению распространения сигнала: $\tau \left( p \right) \in \left\{ {{{\tau }_{{inp}}},{{\tau }_{{out}}},{{\tau }_{{bi}}}} \right\}$ – вход, выход или двунаправленный.

Введем следующие обозначения:

пусть $\nu \left( p \right),~~p \in {{P}_{r}}\left( s \right) \cup {{P}_{m}}\left( s \right)$ – логическое значение на выводе p, т.е. $\nu {\kern 1pt} :~P\left( s \right) \to \mathcal{B}$, $\mathcal{B} = \left\{ {0,1} \right\}$;

${{c}_{i}} = \nu \left( p \right),\,\,\,\,p \in {{P}_{m}}\left( s \right)$ – логическое значение управляющего сигнала;

${{y}_{i}} = \nu \left( p \right),~~p \in {{P}_{r}}\left( s \right),~$ $~~\tau \left( p \right) \in \left\{ {{{\tau }_{{out}}},{{\tau }_{{bi}}}} \right\}$ – логическое значение входа;

${{x}_{i}} = \nu \left( p \right),~~p \in {{P}_{r}}\left( s \right),~$ $~~\tau \left( p \right) \in \left\{ {{{\tau }_{{inp}}},{{\tau }_{{bi}}}} \right\}$ – логическое значение входа;

$\phi \left( {{{c}_{i}}} \right)$ – логическая функция управления открыванием трассировочного элемента, принимающая значение 1 для открытого состояния, 0 – для закрытого;

$\chi \left( {{{x}_{i}}} \right)$ – не константная логическая функция выхода в терминах входа для открытого состояния трассировочного элемента (в унарном варианте это инверсия или эквивалентность);

${{\rho }_{i}}\left( {{{c}_{i}},~{{y}_{i}},{{x}_{i}}} \right):~\mathcal{B} \times \mathcal{B} \times \mathcal{B} \to \mathcal{B}$, $\mathcal{B} = \left\{ {0,1} \right\}$ – характеристическая функция проводимости от x_i к y_i, принимающая значение 1 при корректных значениях и 0 в противном случае.

Корректными трассировочными элементами будем считать те, для которых совокупность характеристических функций проводимости может быть определена в импликативной форме (в форме конъюнкции импликаций) в следующем виде:

где $ \Rightarrow $ – символ операции импликации.

Среди различных вариантов корректных трассировочных элементов можно выделить следующие:

– проходной ключ: $\rho \left( {g,s,d} \right) \equiv \rho \left( {g,d,s} \right) \equiv \left( {g \Rightarrow s = d} \right)$;

– буфер: $\rho \left( {\not {0},y,x} \right) \equiv \left( {1 \Rightarrow y = x} \right)$;

– инвертор: $\rho \left( {\not {0},y,x} \right) \equiv \left( {1 \Rightarrow y = \sim x} \right)$;

– мультиплексор без инверсии:

$\rho \left( {c,y,x} \right) \equiv \left( {\sim {\kern 1pt} c \Rightarrow y = {{x}_{1}}} \right) \wedge \left( {c \Rightarrow y = {{x}_{2}}} \right)$, $x = {{\left( {{{x}_{1}},{{x}_{2}}} \right)}^{T}}$;

– мультиплексор с инверсией:

$\rho \left( {c,y,x} \right) \equiv \left( {\sim {\kern 1pt} c \Rightarrow y = \,\,\sim {\kern 1pt} {{x}_{1}}} \right) \wedge \left( {c \Rightarrow y = \,\,\sim {\kern 1pt} {{x}_{2}}} \right),{\text{\;\;}}x = {{\left( {{{x}_{1}},{{x}_{2}}} \right)}^{T}}$;

– буфер с третьим состоянием: $\rho \left( {c,y,x} \right) \equiv \left( {c \Rightarrow y = \,\,\sim {\kern 1pt} x} \right)$;

– резистор: ${{\rho }}\left( {\not {0},m,p} \right) \equiv {{\rho }}\left( {\not {0},p,m} \right) \equiv \left( {1 \Rightarrow p = m} \right)$.

Совокупность корректных трассировочных элементов базового проекта ${{{\text{П}}}_{f}}\left( {\text{П}} \right) = \left( {{{S}_{f}},~{{L}_{f}},~{{s}_{f}}} \right)$, ${{s}_{f}} = \left( {\mu \left( {{{s}_{f}}} \right),~E\left( {{{s}_{f}}} \right),N\left( {{{s}_{f}}} \right),P\left( {{{s}_{f}}} \right),C\left( {{{s}_{f}}} \right)} \right)$ может быть преобразована в трассировочный смешанный граф или ориентированный граф (с преобразованием каждого из двунаправленных ребер в пару дуг противоположного направления) ${{G}_{{Ro}}}\left( {\text{П}} \right) = \left( {{{V}_{{Ro}}},{{A}_{{Ro}}}} \right)$ по правилам, представленным далее.

Множество вершин ${{V}_{{Ro}}}$ графа ${{G}_{{Ro}}}\left( {\text{П}} \right)$ взаимно однозначно соответствует подмножеству таких и только таких узлов $n \in N\left( {{{s}_{f}}} \right)$, для которых существует хотя бы одно соединение с элементом из подмножества трассировочных элементов:

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

Множество дуг графа ${{G}_{{Ro}}}\left( {\text{П}} \right)$ формируется из импликативных форм характеристических функций проводимости трассировочных элементов $\left( {{{\phi }_{i}}\left( {{{c}_{i}}} \right) \Rightarrow \left( {{{y}_{i}} = {{\chi }_{i}}\left( {{{x}_{i}}} \right)} \right)} \right)$. Для каждой пары (y_i = χ_i(x_i)) создается новая дуга ${{a}_{{xy}}} = (v\left( x \right),v\left( y \right)$) между вершинами, соответствующими узлам $x \in N\left( {{{s}_{f}}} \right)$, $y \in N\left( {{{s}_{f}}} \right)$, имеющим соединения с соответствующими выводами трассировочных элементов. При этом дуги ${{a}_{{xy}}} = (v\left( x \right),v\left( y \right)$) наследуют следующие характеристики трассировочного элемента:

$\phi \left( {{{a}_{{xy}}}} \right)$ – логическую функцию управления открыванием трассировочного элемента, принимающую значение 1 для открытого состояния дуги ${{a}_{{xy}}} = (v\left( x \right),v\left( y \right)$), 0 – для закрытого;

$\chi \left( {{{a}_{{xy}}}} \right)$ – логическую функцию состояния вершины, для которой дуга ${{a}_{{xy}}}$ трассировочного графа является входящей, заданную в терминах состояния вершин, для которых дуга ${{a}_{{xy}}}$ графа является исходящей, при открытом состоянии трассировочного элемента.

Таким образом, задача трассировки для реализации пользовательского проекта сводится к нахождению путей в трассировочном графе ${{G}_{{Ro}}}\left( {\text{П}} \right) = \left( {{{V}_{{Ro}}},{{A}_{{Ro}}}} \right)$, соединяющих его вершины в соответствии с набором коммутаций узлов пользовательской схемы $n \in N\left( {{{s}_{{mu}}}} \right)$:

При этом направление искомых путей распространения сигнала определяется типом выводов коммутируемых элементов: от выходов ${{p}_{x}} \in P\left( {{{e}_{i}}} \right),~\tau \left( {{{p}_{x}}} \right) \in \left\{ {{{\tau }_{{out}}},{{\tau }_{{bi}}}} \right\}~$ к входам ${{p}_{y}} \in P\left( {{{e}_{i}}} \right),~$ $\tau \left( {{{p}_{y}}} \right)$ $ \in \left\{ {{{\tau }_{{inp}}},{{\tau }_{{bi}}}} \right\}$.

Предположим, что $\tau = \left\{ {{{v}_{0}},{{v}_{1}}, \ldots ,{{v}_{n}}} \right\},~~{{v}_{i}} \in {{V}_{{Ro}}}$ –один из таких путей (маршрутов) с дугами ${{a}_{i}} = \left( {{{v}_{i}},{{v}_{{i + 1}}}} \right),\,\,\,\,i = 0,1, \ldots \left( {n - 1} \right),~\,\,\,\,{{a}_{i}} \in {{A}_{{Ro}}}$, тогда:

$\phi \left( \tau \right) = \mathop \bigwedge \limits_{n - 1}^{i = 0} {{\phi }_{i}}\left( {{{a}_{i}}} \right)$ – логическая функция управления открыванием трассировочного пути, определяющая назначение соответствующих элементов программируемой памяти, а

$\chi (\tau ) = {{\chi }_{{n - 1}}} \circ {{\chi }_{{n - 2}}} \circ \ldots \circ {{\chi }_{0}} = {{\chi }_{{n - 1}}}\left( {{{\chi }_{{n - 2}}}\left( { \ldots \left( {{{\chi }_{0}}({{\nu }_{0}})} \right)} \right)} \right)$ – логическая функция состояния концевой вершины пути – композиция (суперпозиция) соответствующих функций передачи сигнала для последовательности дуг.

В унарном варианте не константная логическая функция выхода в терминах входа – это отрицание (инверсия) или эквивалентность. В этом случае конечное значение $\chi \left( \tau \right)$ определяется подсчетом четности инверсных элементов в пути. При этом результирующая функция – отрицание при нечетном количестве отрицаний в пути и эквивалентность – при четном. Само по себе изменение логической функции пути с эквивалентности на любую другую требует переопределения (ресинтеза) логического элемента, соединенного с узлом схемы, соответствующим конечной вершине пути ${{v}_{n}}$ по результатам трассировки.

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

4. ОЦЕНКА ТРАССИРУЕМОСТИ ПОЛЬЗОВАТЕЛЬСКОЙ СХЕМЫ В БАЗИСЕ ГЕТЕРОГЕННОЙ ПЛИС ИЛИ РЕКОНФИГУРИРУЕМОЙ СнК

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

Основополагающей идеей программного прототипирования является анализ наборов пользовательских схем для определения требований и спецификаций разрабатываемого базового кристалла. Для задачи анализа пользовательских схем посредством автоматически настроенного САПР поле ПЛИС может быть представлено двумя способами: упрощенно в виде плоской матрицы логических элементов заранее определенного вида (например, 4-входовой LUT-элемент, реализующий таблицу истинности, с триггером); в виде двухуровневого блочного представления. Как правило, потенциал двухуровневого представления наилучшим образом раскрывается для описания островного типа архитектуры. В этом случае верхний уровень архитектуры кристалла может быть представлен в виде матрицы блоков LAB [10] логических элементов.

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

Перечислим основные характеристики пользовательских схем:

– требуемое количество элементарных (одноразрядных) связей между двумя логическими элементами или кластерами элементов (при превышении требуемого числа связей над фактически имеющимися в базовом кристалле в N раз, оценка трассируемости такой схемы будет различаться [16]), а также требуемая пропускная способность [11] канала (или переключательной коробки), требуемая связность переключательной коробки с каналами в маршруте для островной архитектуры;

– требуемая пропускная способность сечения по вертикали для заданного X, требуемая пропускная способность сечения по горизонтали для заданного Y (соответствующая характеристика базового кристалла – фактическая пропускная способность вертикальных и горизонтальных сечений);

– ограничение на задержку критического пути (частоту работы устройства);

– степень ветвления цепей пользовательской схемы (может быть использована для быстрой сортировки списка проектных соединений [12]);

– степень перегруженности отдельных трассировочных элементов, а также каналов для островной архитектуры, возникающая в процессе трассировки пользовательской схемы на каждом из этапов трассировки [13, 14], или как предварительная оценка результатов трассировки в целом на этапах глобальной трассировки [15] и размещения;

– остаточный путь до приемника, рассчитываемый динамически в процессе трассировки для ускорения трассировки за счет направленности поиска пути [12].

Выведем соотношение между требуемой для пользовательских схем и фактической пропускной способностью базового кристалла. Пусть задано двухуровневое блочное представление базового кристалла ${{{\text{П}}}_{b}}\left( {\text{П}} \right) = \left( {{{S}_{b}},~{{L}_{b}},~{{s}_{b}}} \right)$, содержащее следующие компоненты:

Рассматривается пользовательская схема ${{{\text{П}}}_{u}} = \left( {{{S}_{u}},~{{L}_{u}},~{{s}_{{mu}}}} \right)$, где ${{s}_{{mu}}} = \left( {\mu \left( {{{s}_{{mu}}}} \right),~E\left( {{{s}_{{mu}}}} \right),N\left( {{{s}_{{mu}}}} \right),} \right.$ $\left. {P\left( {{{s}_{{mu}}}} \right),C\left( {{{s}_{{mu}}}} \right)} \right).$ Применительно к кластерному разбиению пользовательской схемы среди ее соединений (цепей $N\left( {{{s}_{{mu}}}} \right)$), помимо внутренних и внешних, можно выделить смежные цепи, которые связаны с элементами как внутри, так и вне кластера (также с внешними выводами схемы):

Тогда количество внешних выводов кластера или его степень можно определить как количество смежных цепей (узлов) $d\left( {{{K}_{i}}} \right) = \left| {{{N}_{{adj}}}\left( {{{K}_{i}}} \right)} \right|.$

Количество выходов или исходящую степень кластера ${{d}^{ - }}\left( {{{K}_{i}}} \right)~$ можно определить как количество смежных цепей (узлов), источником которых является элемент внутри кластера:

• Аналогично можно определить количество входов или входящую степень кластера ${{d}^{ + }}\left( {{{K}_{i}}} \right)~$ как количество смежных цепей (узлов), источником которых является элемент вне кластера или внешний вход схемы. В этом случае, количество входов/выходов кластера пользовательской схемы должно соответствовать количеству входов/выходов блока базового кристалла:

Одним из критических условий, обеспечивающих полноту трассировки межсоединений и проверяемых как в процессе поиска решения задачи размещения на блочном уровне, так и по ее окончании, является соблюдение ограничений на фактическое количество цепей, пересекающих сечение (разрез) по вертикали для заданного X, и фактическое количество цепей, пересекающих сечение (разрез) по горизонтали для заданного Y.

С учетом выбранного размещения блоков ${{\mathcal{P}}_{{\text{b}}}}:{\text{\;K}} \to {\text{B}};{\text{\;b}}_{{{\text{ij}}}}^{{}} = {{\mathcal{P}}_{{\text{b}}}}\left( {{{{\text{K}}}_{{\text{k}}}}} \right)$ можно вычислить реальные координаты портов блоков (или центров блоков) и, следовательно, граничные координаты цепей пользовательской схемы:

Следовательно, для заданной пользовательской схемы ${{s}_{{mu}}}$ требуемая пропускная способность сечений $X_{S}^{k},~Y_{S}^{k}~$ вычисляется по формулам:

Для обеспечения полной разводимости всего списка проектных цепей необходимо, чтобы требуемое для реализации пользовательской схемы число цепей, пересекающих сечение, превышало фактическую пропускную способность сечения в базовом кристалле не более, чем в ${{p}_{X}}$ и ${{p}_{Y}}$ раз:

Предполагается, что коэффициенты ${{p}_{X}}$ и ${{p}_{Y}}$ могут быть подобраны эмпирически для заданного набора пользовательских схем. Выведенное соотношение может быть использовано как во время этапа размещения для оценки трассируемости текущего варианта, так и перед началом процедуры трассировки для определения целесообразности ее выполнения.

5. ЗАКЛЮЧЕНИЕ

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