Устройство планирования топологии логических интегральных схем

Устройство планирования топологии логических интегральных схем

Иллюстрации

Показать все

Реферат

Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании вычислительных систем (ВС).

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 1291957 СССР кл. G06F 7/00, опубл. 23.02.87, БИ №7).

Недостатком указанного элемента является узкая область применения, обусловленная отсутствием средств для планирования топологии программируемых интегральных схем (ПЛИС).

Наиболее близким к предлагаемому устройству по технической сущности является устройство для формирования субоптимального размещения и его оценки, содержащее блок формирования перестановок, блок постоянной памяти, коммутатор, арифметико-логическое устройство (АЛУ), блок запоминания лучшего варианта, введены дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, группа элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, второй и третий элементы задержки, два регистра сдвига, элемент ИЛИ и группу элементов ИЛИ, электронную модель графа (ЭМГ), содержащую m электронных моделей дуги, причем 1-я электронная модель дуги (l=1, 2, …, m) содержит триггер блокировки дуги, регистр веса дуги, регистр блокировки дуги, первый элемент И, второй элемент И, элемент ИЛИ (Патент РФ №2193796, кл. G06F 17/10, 7/38, опубл. 27.11.2002, БИ №33).

Недостатком указанного устройства является узкая область применения, обусловленная отсутствием средств для планирования топологии программируемых интегральных схем (ПЛИС) по критерию минимизации интенсивности взаимодействия процессов и данных.

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

Техническая задача решается тем, что в устройство поиска нижней оценки размещения в матричных системах при двунаправленной передаче информации (фиг.1), содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок (БФП), блок постоянной памяти, блок запоминания лучшего варианта (БЗЛВ), коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу с 1-го по n-й элементов ИЛИ, группу с 1-го по n-й элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, второй и третий элементы задержки, первый блок элементов ИЛИ, причем выходы БФП соединены с соответствующими входами блока постоянной памяти и соответствующими входами БЗЛВ, сигнализирующий выход БФП соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом АЛУ, выход которого соединен с информационным входом БЗЛВ, а выход БЗЛВ соединен с первым информационным входом АЛУ, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы первого и второго регистров сдвига с первого по n-й подключены к первым и вторым входам элементов ИЛИ 1-го по n-й соответственно, выход переполнения регистра сдвига соединен с управляющим входом АЛУ и с управляющим входом БФП, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом БФП и с первыми входами первого и второго элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход первого элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом третьего элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход первого элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом второго элемента И, третий вход первого элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом второго элемента И, выход второго элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход которого подключен к первому входу умножителя, выход счетчика расстояний подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу регистра минимальной длины связей и к второму входу вычитателя, выход сумматора подключен к входу данных регистра минимальной длины связей, выход элемента задержки подключен к синхровходу регистра минимальной длины связей, выход второго элемента И и счетный вход счетчика расстояний подключены к входу третьего элемента задержки, выход второго одновибратора подключен к синхровходу счетчика расстояний, выход переполнения которого подключен к счетным входам счетчика топологии, счетчика расстояний и к входу второго одновибратора, выход счетчика топологии подключен к входу счетчика расстоянии, вход данных устройства подключен ко входу данных счетчика топологии, синхровход счетчика топологии подключен к входу установки устройства, прямой выход триггера задания топологии подключен к разрешающему входу счетчика топологии, установочный вход триггера задания топологии подключен к входу установки устройства, вход сброса триггера задания топологии подключен к входу установки устройства, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, выход регистра длины связей подключен ко второму входу элемента сравнения и к первому входу вычитателя, первый вход элемента сравнения подключен к выходу АЛУ и входу данных регистра длины связей, выход одновибратора подключен к синхровходу регистра длины связей, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l=1, 2, …, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ и l-м входом блока элементов ИЛИ, l-й выход элемента И группы элементов И с l-го по m-й соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом АЛУ, выход элемента сравнения соединен с входом первого одновибратора, выходы элементов с 1-го по n-й ИЛИ подключены к соответствующим входам элементов И 1-го по m-й, выход вычитателя соединен с выходом длины связей устройства, дополнительно введен блок устройства планирования топологии логических интегральных схем, содержащий микропроцессор (МП), оперативную память (ОП), контроллер прямого доступа в память (КПРДП), параллельный порт (Прпорт), последовательный порт (Ппорт), блок планирования топологии ПЛИС (БПТПЛИС), матрицу смежности (МС), матрицу цепей (МЦ) блока БНО, блок поисковых перестановок (БПГ1), блок нахождения минимальной нижней оценки (БНО), блок поиска начального значения коммуникационной задержки (БНЗ), сумматор нижней оценки суммарной длины межсоединений модулей ПЛИС, регистр временного хранения суммы блока БНО, счетчик вычисления адреса строки матрицы цепей (МЦ) блока БНО, счетчик вычисления адреса столбца матрицы цепей (МЦ) блока БНО, генератор импульсов, RS-триггер выбора работы матрицы цепей (МЦ) блока БНО, матрицу цепей (МЦ) блока БНЗ, сумматор степени близости максимальной задержки, регистр временного хранения промежуточных данных в процессе вычисления степени близости максимальной задержки, счетчик подсчета степени загрузки канала в текущей строке МЦ блока БНЗ, счетчик строк МЦ блока БНЗ перебора номеров контактов модуля ПЛИС, элемент задержки выбора работы блока «Начальные значения», RS-триггер выбора работы матрицы цепей (МЦ) блока БНЗ, делитель вычисления ηн, регистр хранения кода значения T₀, ОЗУ временного хранения копии матрицы МЦ блока БНО, счетчик кода k хранения кода переменной k, счетчик кода i хранения кода переменной i, счетчик столбцов подсчета адреса столбцов в ОЗУ временного хранения копии матрицы МЦ блока БНО, счетчик строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО, вычитатель единицы из N, ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки», элемент сравнения элементов матрицы МЦ с кодом значения единицы, элемент сравнения кода i со значением единица, элемент сравнения результата вычитания кодов k и i с кодом единица, вычитатель кодов k и i, регистр хранения кода числа i блока «Анализ необходимости перестановки», RS-триггер выбора режима работы блока «Анализ необходимости перестановки», элемент ИЛИ выбора номера сравнения в вычитателе единицы из N, элемент ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки», элемент ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки», элемент сравнения значения k из блока «Анализ необходимости перестановки» с единицей, регистр хранения кода числа k блока «Анализ необходимости перестановки», ОЗУ моделирования матрицы M1, ОЗУ моделирования матрицы МСМ, компаратор сравнения Ti и i, компаратор сравнения Ti и k, компаратор сравнения Tk и k, компаратор сравнения Ti и Tk, счетчик подсчета столбцов адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М, счетчик подсчета строк адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М, счетчик текущего значения i блока «Целенаправленные поисковые перестановки», счетчик моделирования изменения параметра PromStr исследуемого метода, счетчик текущего значения k блока «Целенаправленные поисковые перестановки», счетчик моделирования изменения параметра PromStolb исследуемого метода, ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы M1, реализуемую в алгоритме, ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М, реализуемую в алгоритме, сумматор суммирования кодов значений T₁, делитель получения кода значения η, элемент сравнения кодов значений Т₁ и Т₀, элемент сравнения кодов значений η и η_н, счетчик подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, счетчик для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, счетчик для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, счетчик для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, RS-триггер режима работы схемы, элемент ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, элемент ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, регистр временного хранения кодов при подсчете значения Т₁ алгоритма, причем Прпорт соединен с устройством БПТПЛИС, генератор тактовых импульсов блока БНО соединен с тактовым входом счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО, выход переполнения счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО соединен с тактовым входом счетчика вычисления адреса столбца матрицы цепей (МЦ) блока БНО, выход переполнения которого соединен со входом разрешения работы счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО, а также со входом R RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНО, выход счетчика вычисления адреса столбца матрицы цепей (МЦ) блока БНО соединен со входом a1 матрицы цепей (МЦ) блока БНО, выход счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО соединен со входом а2 матрицы цепей (МЦ) блока БНО, выход out матрицы цепей (МЦ) блока БНО соединен со входом D1 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, выход которого соединяется со входом D регистра временного хранения суммы блока БНО, выход которого соединен со входом D2 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, а также на второй вход делителя вычисления η_н и регистра хранения кода значения T₀, обратный выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНО соединен со входом разрешения выдачи кода матрицы цепей (МЦ) блока БНО, генератор тактовых импульсов блока БНО соединен с тактовым входом счетчика строк МЦ блока БНЗ перебора номеров контактов модуля, выход переполнения счетчика строк МЦ блока БНЗ перебора номеров контактов модуля ПЛИС соединен с тактовым входом счетчика подсчета степени загрузки канала в текущей строке МЦ блока БНЗ, выход переполнения которого соединен со входом разрешения работы счетчика строк МЦ блока БНЗ перебора номеров контактов модуля, а также со входом RS-триггера выбора работы матрицы цепей (МЦ) блока БНЗ, выход счетчика подсчета степени загрузки канала в текущей строке МЦ блока БНЗ соединен со входом a1 матрицы цепей (МЦ) блока БНЗ, выход счетчика строк МЦ блока БНЗ перебора номеров контактов модуля соединен со входом а2 матрицы цепей (МЦ) блока БНЗ, выход out матрицы цепей (МЦ) блока БНЗ соединен со входом D1 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, выход которого соединяется со входом D регистра временного хранения суммы блока БНЗ, выход которого соединен со входом D2 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, а также на второй вход делителя вычисления η_н, выход делителя вычисления η_н соединяется со входом элемента сравнения кодов значений η и η_н, обратный выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БМЗ 108 соединен со входом разрешения выдачи кода матрицы цепей (МЦ) блока БНЗ, а также с элементом задержки выбора работы блока «Начальные значения», который соединяется с входом е ОЗУ временного хранения копии матрицы МЦ блока «Начальные установки», прямой выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНЗ соединен со входом разрешения выдачи кода регистра хранения кода значения Т₀ блока БНЗ, выход которого соединяется с первым входом делителя получения кода значения η, тактовый вход счетчика столбцов подсчета адреса столбцов в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен с выходом переполнения счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО, тактовый вход счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен с выходом генератора импульсов, выход счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен со входом а2 ОЗУ временного хранения копии матрицы МЦ блока БНО, выход счетчика столбцов подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен со входом a1 ОЗУ временного хранения копии матрицы МЦ блока БНО, счетчик кода k хранения кода переменной k, счетчик кода i хранения кода переменной i, вход a1 ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом элемента ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки», вход а2 ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом элемента ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки», первый вход элемента ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом счетчика текущего значения i блока «Целенаправленные поисковые перестановки», второй вход элемента ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом регистра хранения кода числа k блока «Анализ необходимости перестановки», первый вход элемента ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом счетчика текущего значения k блока «Целенаправленные поисковые перестановки», второй вход элемента ИЛИ выбора столбца ОЗУ временного хранения копии матрицы M1 i блока «Анализ необходимости перестановки» соединен с выходом счетчика текущего значения k блока «Целенаправленные поисковые перестановки», выход out ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен со входом элемента сравнения элементов матрицы МЦ с кодом значения единицы, нулевой выход которого соединяется с тактовым входом счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО, а единичный выход элемента сравнения элементов матрицы МЦ с кодом значения единицы соединен со входом элемента ИЛИ выбора номера сравнения в вычитателе единицы из N, выход которого соединен со входом е вычитателе единицы из N, на вход которого поступает код числа N, выход вычитателя единицы из N соединяется с входом регистра хранения кода числа i блока «Анализ необходимости перестановки», а также с входом регистра хранения кода числа k блока «Анализ необходимости перестановки », выход регистра хранения кода числа i блока «Анализ необходимости перестановки» соединяется с входом элемента сравнения кода i со значением единица, выход которого соединяется с разрешающим входом е регистра хранения кода числа k блока «Анализ необходимости перестановки», выход регистра хранения кода числа k блока «Анализ необходимости перестановки» соединяется с входом элемента сравнения кода k со значением единица, выход регистра хранения кода числа i блока «Анализ необходимости перестановки» соединяется со вторым входом вычитателя кодов k и i, выход регистра хранения кода числа k блока «Анализ необходимости» перестановки соединяется с первым входом вычитателя кодов k и i, выход которого соединен со входом элемента сравнения результата вычитания кодов k и i с кодом единица, единичный выход которого соединяется с входами е счетчика текущего значения k блока «Целенаправленные поисковые перестановки» и счетчика моделирования изменения параметра PromStolb исследуемого метода, единичный выход элемента сравнения кода k со значением единица соединяется с RS-триггером выбора режима работы блока «Анализ необходимости перестановки», обратный выход которого соединяется с входом элемента ИЛИ выбора номера сравнения в вычитателе единицы из N, нулевой выход элемента сравнения результата вычитания кодов k и i с кодом единица соединяется с тактовым входом счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО, вход a1 ОЗУ моделирования матрицы M1 соединен с выходом счетчика моделирования изменения параметра PromStr исследуемого метода, вход а2 ОЗУ моделирования матрицы M1 соединен с выходом счетчика моделирования изменения параметра PromStolb исследуемого метода, выход переполнения счетчика моделирования изменения параметра PromStr исследуемого метода соединен с тактовым входом счетчика текущего значения i блока «Целенаправленные поисковые перестановки», выход которого соединен с первым входом компаратора сравнения Ti и i, выход переполнения счетчика моделирования изменения параметра PromStolb исследуемого метода соединен с тактовым входом счетчика текущего значения PromStr блока «Целенаправленные поисковые перестановки», выход которого соединен со вторым входом компаратора сравнения Ti и i, выход компаратора сравнения Ti и i соединен с разрешающим входом е компаратора сравнения Ti и k, выход которого соединен с разрешающим входом е компаратора сравнения Tk и k, выход которого соединен с разрешающим входом в компаратора сравнения Ti и Tk, выход которого соединен с разрешающим запись входом we ОЗУ моделирования матрицы M1, и с входом ое ОЗУ моделирования матрицы МСМ, а также с тактовым входом счетчика подсчета строк адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М, выход которого соединен с входом а2 ОЗУ моделирования матрицы МСМ, выход переполнения счетчика подсчета строк адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М соединен с тактовым входом счетчика подсчета столбцов адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М, выход которого соединен со входом a1 ОЗУ моделирования матрицы МСМ, выход которого соединен со входом D ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы M1, первый вход компаратора сравнения Ti и k соединен с выходом счетчика текущего значения PromStr блока «Целенаправленные поисковые перестановки», второй вход компаратора сравнения Ti и k соединен с выходом счетчика текущего значения k блока «Целенаправленные поисковые перестановки», первый вход компаратора сравнения Tk и k соединен с выходом счетчика моделирования изменения параметра PromStolb исследуемого метода, второй вход компаратора сравнения Tk и k соединен с выходом счетчика текущего значения k блока «Целенаправленные поисковые перестановки», выход счетчика моделирования изменения параметра PromStr исследуемого метода соединен с первым входом компаратора сравнения Ti и Tk, выход счетчика моделирования изменения параметра PromStolb исследуемого метода соединен со вторым входом компаратора сравнения Ti и Tk, выход out ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединен со входом D ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, а также со входом D1 сумматора суммирования кодов значений Т₁, выход которого соединяется с входом регистра временного хранения кодов при подсчете значения Т₁ алгоритма, выход которого соединен со входом D2 сумматора суммирования кодов значений Т₁ значений, а также с первым входом элемента сравнения кодов значений T₁ и Т₀, выход которого соединен с разрешающим входом делителя получения кода значения η, выход которого соединен с первым входом элемента сравнения кодов значений η и η_н, выход которого соединен с входом е счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, а также с входом е ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход счетчика подсчет строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен со входом а2 ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен со входом a1 ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен со вторым входом элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен с первым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход генератора тактов соединен с входом счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход которого соединен с первым входом элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход переполнения счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен с тактовым входом счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход которого соединен со первым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединен со вторым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход переполнения счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединен с входом е счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, а также с входом R RS-триггера режима работы схемы и входом е элемента сравнения кодов значений Т₁ и Т₀, выход переполнения счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединен с тактовым входом счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, обратный выход RS-триггера режима работы схемы соединен с входом ое ОЗУ моделирования матрицы M1, а также с входом е элемента сравнения кодов значений η и η_н, выход генератора тактов соединен с входом счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М и тактовым входом счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход переполнения которого соединяется с тактовым входом счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединяется с входом а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединяется с входом a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход регистра временного хранения промежуточных данных в процессе вычисления степени близости максимальной задержки соединяется с входом делимого делителя получения кода значения η.

Программу (подпрограмму) будем представлять направленным графом взаимодействия задач

G = < X , E > ,   где  X = { x 1 .1 x 1.2 … x 1. k … x 1. n x 2.1 x 2.2 … x 2. k … x 2. n … x q .1 x q .1 … x q . k … x q . n … x n .1 x n .2 … x n . k … x n . n } −            (1)

множество вершин графа G, вершины x_qk∈X которого соответствуют задачам, а дуги e_ij∈E связям между ними при i,j=(q-1)·n+k взвешиваются объемами данных m_ij, которые передаются между подзадачами и могут быть сведены в матрицу смежности (МС) M = ‖ m i j ‖ N × | E | , где N=|Х|.

Пример графа взаимодействия задач и соответствующей ей МС показан на фиг.1 и фиг.2 соответственно.

Топологию ПЛИС будем задавать графом И, который представим в виде прямоугольника H = { p 1.1 p 1.2 … p ϖ . θ … p 1. n p 2.1 p 2.2 … p ϖ . θ p 2. n … p m .1 p m .2 … p ϖ . θ … p m . n } , где P_ω.θ - это отдельные модули ПЛИС, причем ( ϖ = 1, m ¯ , θ = 1. n ¯ )

Модуль P_ω.θ представляется в виду функции F(O.X), т.е.

P ϖ . θ = F ( O , X ) ,                       (2)

где O=о₁, о₂, …, o_p - это множество входных выводов модуля, а X=х₁, x₂, …,x_p - это множество выходных выводов. Выводы модулей ПЛИС соединяется с выводами других модулей. При этом общее количество сигналов, которые передаются в ПЛИС от одного модуля к другому, определяют итоговую коммуникационную задержку, которую необходимо минимизировать для увеличения производительности ПЛИС. Схематично модуль ПЛИС может быть представлен так, как показано на фиг.3.

Как видно из фиг.3, величина p, представленная в (2), зависит от схемной реализации модуля ПЛИС и не может быть известна заранее. Далее введем понятие канала и матрицы цепей. Под каналом в модуле ПЛИС будем понимать проложенную трассу от одного вывода o_i или x_j=(i=(1,p),j=(1,р)) модуля к другому. На фиг.4 проиллюстрировано понятие канала. На фиг.4 черными кружками обозначены выводы гипотетических модулей ПЛИС. Числа над пунктирными линиями обозначают степени загрузки каналов между парами смежных контактов.

Матрицей цепей (МЦ) называется описывающая вариант размещения модулей ПЛИС прямоугольная матрица V = | ν i . j | n . α , где i = 1, N ¯ , j = 1, α ¯ , n=|X|, α представляет собой суммарное количество каналов, полученных в результате размещения подпрограмм в модулях ПЛИС. Гипотетический вариант МЦ приведен на фиг.5.

На фиг.5 приведена матрица цепей, соответствующая варианту размещения, представленному на фиг.4. В данном случае строкам соответствуют выводы модуля(ей) ПЛИС, а столбцам соответствуют каналы, соответствующих данному варианту размещения.

Мощность |Р| в конечном итоге зависит от числа каналов, полученных в

результате размещения модулей в ПЛИС. Параметр а фактически соответствует количеству каналов, заранее неизвестен, и чем он меньше, тем оптимальнее вариант размещения. То есть, очевидно, что должно выполняться соотношение:

∑ α → min               (3)

Тогда размещение модулей в ПЛИС может быть описано отображением:

β s = { x S 1.1 x S 1.2 … x S 1. k … x S 1. α x S 2.1 x S 2.2 … x S 2. k … x S 2. α … x S q .1 x S q .1 … x S q . k … x S q . α … x S n .1 x S n .2 …