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



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

 


Владельцы патента RU 2530275:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Юго-Западный государственный университет" (ЮЗГУ) (RU)

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

 

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

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 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-триггер выбора работы матрицы цепей (МЦ) блока БНЗ, делитель вычисления ηн, регистр хранения кода значения T0, ОЗУ временного хранения копии матрицы МЦ блока БНО, счетчик кода 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, реализуемую в алгоритме, ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М, реализуемую в алгоритме, сумматор суммирования кодов значений T1, делитель получения кода значения η, элемент сравнения кодов значений Т1 и Т0, элемент сравнения кодов значений η и ηн, счетчик подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, счетчик для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, счетчик для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, счетчик для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, RS-триггер режима работы схемы, элемент ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, элемент ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, регистр временного хранения кодов при подсчете значения Т1 алгоритма, причем Прпорт соединен с устройством БПТПЛИС, генератор тактовых импульсов блока БНО соединен с тактовым входом счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО, выход переполнения счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО соединен с тактовым входом счетчика вычисления адреса столбца матрицы цепей (МЦ) блока БНО, выход переполнения которого соединен со входом разрешения работы счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО, а также со входом R RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНО, выход счетчика вычисления адреса столбца матрицы цепей (МЦ) блока БНО соединен со входом a1 матрицы цепей (МЦ) блока БНО, выход счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО соединен со входом а2 матрицы цепей (МЦ) блока БНО, выход out матрицы цепей (МЦ) блока БНО соединен со входом D1 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, выход которого соединяется со входом D регистра временного хранения суммы блока БНО, выход которого соединен со входом D2 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, а также на второй вход делителя вычисления ηн и регистра хранения кода значения T0, обратный выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНО соединен со входом разрешения выдачи кода матрицы цепей (МЦ) блока БНО, генератор тактовых импульсов блока БНО соединен с тактовым входом счетчика строк МЦ блока БНЗ перебора номеров контактов модуля, выход переполнения счетчика строк МЦ блока БНЗ перебора номеров контактов модуля ПЛИС соединен с тактовым входом счетчика подсчета степени загрузки канала в текущей строке МЦ блока БНЗ, выход переполнения которого соединен со входом разрешения работы счетчика строк МЦ блока БНЗ перебора номеров контактов модуля, а также со входом RS-триггера выбора работы матрицы цепей (МЦ) блока БНЗ, выход счетчика подсчета степени загрузки канала в текущей строке МЦ блока БНЗ соединен со входом a1 матрицы цепей (МЦ) блока БНЗ, выход счетчика строк МЦ блока БНЗ перебора номеров контактов модуля соединен со входом а2 матрицы цепей (МЦ) блока БНЗ, выход out матрицы цепей (МЦ) блока БНЗ соединен со входом D1 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, выход которого соединяется со входом D регистра временного хранения суммы блока БНЗ, выход которого соединен со входом D2 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, а также на второй вход делителя вычисления ηн, выход делителя вычисления ηн соединяется со входом элемента сравнения кодов значений η и ηн, обратный выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БМЗ 108 соединен со входом разрешения выдачи кода матрицы цепей (МЦ) блока БНЗ, а также с элементом задержки выбора работы блока «Начальные значения», который соединяется с входом е ОЗУ временного хранения копии матрицы МЦ блока «Начальные установки», прямой выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНЗ соединен со входом разрешения выдачи кода регистра хранения кода значения Т0 блока БНЗ, выход которого соединяется с первым входом делителя получения кода значения η, тактовый вход счетчика столбцов подсчета адреса столбцов в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен с выходом переполнения счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО, тактовый вход счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен с выходом генератора импульсов, выход счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен со входом а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 сумматора суммирования кодов значений Т1, выход которого соединяется с входом регистра временного хранения кодов при подсчете значения Т1 алгоритма, выход которого соединен со входом D2 сумматора суммирования кодов значений Т1 значений, а также с первым входом элемента сравнения кодов значений T1 и Т0, выход которого соединен с разрешающим входом делителя получения кода значения η, выход которого соединен с первым входом элемента сравнения кодов значений η и ηн, выход которого соединен с входом е счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, а также с входом е ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход счетчика подсчет строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен со входом а2 ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен со входом a1 ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен со вторым входом элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен с первым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход генератора тактов соединен с входом счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход которого соединен с первым входом элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход переполнения счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен с тактовым входом счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход которого соединен со первым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединен со вторым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход переполнения счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединен с входом е счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, а также с входом R RS-триггера режима работы схемы и входом е элемента сравнения кодов значений Т1 и Т0, выход переполнения счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы 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, вершины xqk∈X которого соответствуют задачам, а дуги eij∈E связям между ними при i,j=(q-1)·n+k взвешиваются объемами данных mij, которые передаются между подзадачами и могут быть сведены в матрицу смежности (МС) 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=о1, о2, …, op - это множество входных выводов модуля, а X=х1, x2, …,xp - это множество выходных выводов. Выводы модулей ПЛИС соединяется с выводами других модулей. При этом общее количество сигналов, которые передаются в ПЛИС от одного модуля к другому, определяют итоговую коммуникационную задержку, которую необходимо минимизировать для увеличения производительности ПЛИС. Схематично модуль ПЛИС может быть представлен так, как показано на фиг.3.

Как видно из фиг.3, величина p, представленная в (2), зависит от схемной реализации модуля ПЛИС и не может быть известна заранее. Далее введем понятие канала и матрицы цепей. Под каналом в модуле ПЛИС будем понимать проложенную трассу от одного вывода oi или xj=(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 x S n . k x S n . α } { p 1,1 p 1,2 p 1, k p 1, α p 1,2 p 2,2 p 2, k p 2, α p q ,1 p q ,2 p q , k p q , α p n ,1 p n ,2 p n , k p n , α } ,         (4)

где S = 1, N ! ¯ . В (4) символ → означает отображение одной из вершин x S q , k X на один из модулей pq,k∈H. Здесь s - это номер очередной перестановки, соответствующий s-у варианту размещения. Мощность множества ψ={βS} всевозможных отображений (4) равна числу всевозможных перестановок задач xqk∈X в матрице М:|ψ|=N.

Пусть ψ - множество всевозможных отображений вида (4). Тогда задачу размещения можно сформулировать как поиск отображения β*∈ψ, такого, что

T β * = min Ψ { max β s Ψ { T β s ( | V | p q . k ) } } , ( 5 )

где T β s ( | V | p q , k ) - задержка при передаче данных в модуле pq,k, соответствующая отображению βs. В выражении (5) max β s Ψ означает поиск максимальной задержки при передаче данных в процессоре pq,k, где q = 1, n ¯ , k = 1, α ¯ ; выражение min Ψ соответствует поиску минимально возможного значения задержки для максимального max β s Ψ { T β s ( | V | p q , k ) } .

Введем понятие смежных контактов (СК) в ПЛИС.

Под СК будем понимать такое расположение выводов модулей ПЛИС, при котором выполняется соотношение

θ = | ν i , j ν i , j 1 | = 1                          (6)

Смысл этого критерия можно пояснить на фиг 6. Данному расположению выводов модуля(ей) соответствует МЦ, приведенная на фиг.5. Тогда при перестановке местами выводов 3 и 4 получаем вариант размещения, представленный на фиг.7.

В данном варианте размещения имеется один СК. Поэтому справедлив критерий при поиске субоптимального варианта размещения модулей ПЛИС.

θ max ( 7 )

Таким образом, на содержательном уровне задача размещения модулей ПЛИС согласно критерию (5) заключается в поиске такого варианта размещения, при котором выполняется условие (3) и (7).

Для поиска субоптимального варианта размещения (3), удовлетворяющего критерию (5) и (7), первоначально необходимо вычислить недостижимую минимальную оценку размещения Tinf при допущении, что топологии исходного графа G и графа связей Н между модулями тождественны. При вычислении нижней оценки будем назначать дуги графа G с наибольшим весом на самые короткие маршруты в графе Н, не обращая внимания на ограничения, накладываемые фактическими связями между задачами в графе G. С учетом того, что размещение выполняется на ПЛИС, фактически при поиске нижней оценки предполагается, что размещение выполняется на один канал α.

На содержательном уровне поиск нижней оценки состоит из следующих шагов:

1) выстроить в линейный векторный массив элементы матрицы МС по убыванию;

2) найти частные суммарное значение одноименных компонентов полученного вектора;

3) фиксировать максимальное частное произведение, как максимальную задержку, получаемую при гипотетически наилучшем размещении.

Тогда процедуру поиска минимальной нижней оценки можно представить в виде алгоритма:

1. Переписать элементы mkl≠0 ( k = 1, N ¯ , l = 1, N ¯ ) матрицы M = m i j N × | E | в вектор-строку M ' = | m k / z | , где z - это порядковый номер элемента в М', причем k = 1, N ¯ , l = 1, N ¯ . При этом z1>z2 и z1, z2 - порядковые номера элементов в М'.

2. Положить

T inf = i = 1 j = | E | m i z , ( 8 )

где i = 1, | E | ¯ , z = 1, | E | ¯ , | E | - мощность множества Е в графе G; mz- одноименные элементы вектора М'.

Для решения задачи планирования размещения в ПЛИС предлагается процедура, в которой критерием оптимальности размещения является степень отклонения η мин-максного значения критерия (5) от его нижней оценки Tinf (8), полученной по процедуре, представленной в п.2.2.2.

Цель задачи стоит в снижении по критерию (8) коммуникационной задержки, возникающей при обработке назначенных на ПЛИС программ, описываемых графом их взаимодействия G, и определяемой как максимальная задержка между обрабатываемыми в ПЛИС программами: МЕ\

T = max { i = 1 j = | E | m i z } , ( 9 )

где i , j = 1, | E | ¯ .

Процедура поиска решения включает следующие этапы.

Этап 1. Производится первичное произвольное размещение вершин графа G, представляющего исходный комплекс решаемых в ПЛИС подпрограмм, описанных графом Н. Размещение реализуется путем наложения матрицы M = m i j N × | E | на матрицу V = | ν i , j | n , α . По формуле (9) находим максимальную задержку TH, соответствующую данному начальному варианту размещения.

Этап 2. Для сопоставления вариантов размещения по критерию (5) вначале осуществляется поиск нижней оценки TH для графа G по алгоритму поиска нижней оценки, описанный в п.5 агоритма размещения подпрограмм в ПЛИС. Затем вычисляется степень близости максимальной задержки TH, соответствующей первичному варианту размещения, к нижней оценке Tinf в виде:

η H = T H T inf . ( 10 )

Этап 3. Начиная с элемента mij∈H, которому соответствует max{Σνj} в первичном варианте, пытаемся переместить строку, его содержащую, на место другой строки так, чтобы после перестановки и расчета Т по формуле (9) оценка:

η = T T inf , ( 11 )

снижалась по сравнению с ηн (10) и оценками η по предыдущим вариантам размещения.

Этап 4. Анализ достигнутой величины η (11) и оценка степени улучшения размещения выполняется по следующей формуле выигрыша в снижении коммуникационной задержки.

σ = η H η = T H T .                   (12)

Вывод результатов перестановки в виде новой матрицы МС, размещенной в ПЛИС с соответствующей новой матрицей МЦ.

Алгоритм размещения подпрограмм в ПЛИС состоит из следующих шагов:

1. Ввести M = m i j N × N , i = 1, N ¯ , j = 1, N ¯ ;

2. Ввести V = | ν i , j | n , α , i = 1, N ¯ , j = 1, N ¯ ;

3. Ввести M 1 = m 1 i j N × α , ∀m1ij=0;

4. Положить T inf = i = 1 j = | E | m i z , где z=|М'|, Е≤N2-N;

5. Положить T H = max [ i = 1 N j = 1 α ν i j ] ;

6. Принять η H = T H T inf ;

7. Принять T0=TH, M1=M;

8. Принять k=N, i=N

9. Если Vik=1, то принять i=N-1 и п.10, иначе п.19;

10. Если i<1, то принять k=N-1 и если k<1, то останов, иначе п.11;

11. Найти Vik=1, то, если k-i>1, то п.12, иначе M2ik=-1, иначе п.19;

12. Принять PromStr=1, PromStolb=1;

13. Для М выполнить i↔(k-(i+1)) и сформировать M1:

∀((PromStr,PromStolb≠i)&(PromStr,PromStolb≠k)):M1PromStr.PromStolb=Mik

∀((PromStr=i)&(PromStolb=k)):M1promStr,PromStolb=Mik;

14. Для M 1 : T 1 = max [ i = 1 N j = 1 α ν i j ] . Если T1<T0, то п.15, иначе п.17;

15. Вычислить η = T H T 1 , если η<ηн, то стоп, иначе п.16;

16. Принять М=М1;

17. Принять T=T1;

18. Принять M2ij=-1;

19. Принять k=k-1. Если k<1, то п.20, иначе п.9;

20. Принять i=i-1. Если i<1, то операция закончена, иначе п.9.

В предложенном алгоритме на шагах 1-3 выполняется инициализация исходных данных, а именно матрицы МС и МЦ и дополнительных промежуточных матрицы M1 и М2, необходимых для выполнения алгоритма. На шаге 4 вычисляется нижняя оценка T inf = i = 1 j = | E | m i z , а на шаге 5 - вычисление первоначальное значения коммуникационной задержки до начала выполнения алгоритма. На шагах 7-12 выполняется поиск необходимости перестановки строк МЦ для уменьшения показателя коммуникационной задержки. В случае необходимости на шаге 13 выполняется перестановка строк МЦ. На шагах 14-20 выполняется анализ необходимости продолжения выполнения алгоритма, т.е. сравнение нового показателя Т и первоначальным значением TH. Кроме того, на этом этапе выполняется анализ степени приближения показателя Т к первоначально полученным показателем Tinf.

Устройство поиска нижней оценки размещения в матричных системах при двунаправленной передаче информации (фиг.16) содержит первый регистр 1 сдвига, второй регистр 2 сдвига, блок 3 формирования перестановок (БФП), блок 4 постоянной памяти, блок 5 запоминания лучшего варианта (БЗЛВ), коммутатор 6, АЛУ 7, дешифратор 8 выбора дуги, реверсивный счетчик 9 ячеек, блок 10 оперативной памяти, счетчик 11 топологии, первый 12 и второй 13 счетчики расстояний, умножитель 14, сумматор 15, регистр 16 минимальной длины связей, первый элемент 17 сравнения, вычитатель 18, триггер 19 начала счета, триггер 23 режима, триггер 24 задания топологии, регистр 25 длины связей, второй элемент 26 сравнения, счетчик 27 дуг, дешифратор 28 блокировки дуги, регистр 29 номера дуги, регистр 30 минимального веса, электронную модель 31 графа, группу элементов ИЛИ 32.1-32.n, группу элементов И 33.1-33.m, первый 34 и второй 35 элементы И, второй блок элементов ИЛИ 36, третий элемент И 37, первый 41 и второй 42 одновибраторы, первый 43, второй 44 и третий 45 элементы задержки, первый блок элементов ИЛИ 46, причем выходы БФП 3 соединены с соответствующими входами блока 4 постоянной памяти и соответствующими входами БЗЛВ 5, сигнализирующий выход БФП 3 соединен с установочным входом триггера 19 начала счета, выходы блока 4 постоянной памяти соединены с соответствующими входами коммутатора 6, выход которого соединен с входом АЛУ 7, выход которого соединен с информационным входом БЗЛВ 5, а выход БЗЛВ 5 соединен с первым информационным входом АЛУ 7, выход переполнения регистра 1 сдвига соединен с входом регистра 2 сдвига, выходы регистров 1 и 2 с первого по n-й подключены к первым и вторым входам элементов ИЛИ 32.1-32.n соответственно, выход переполнения регистра 2 сдвига соединен с управляющим входом АЛУ 7 и с управляющим входом БФП 3, тактовый вход 57 устройства соединен с входом регистра 1 сдвига, с тактовым входом БФП 3 и с первыми входами элементов И 34 и 35, выход счетчика 27 дуг соединен с входом дешифратора 8 выбора дуги и входом данных регистра 29 номера дуги, выход блока элементов ИЛИ 36 подключен к первому входу элемента 17 сравнения и к входу данных регистра 30 минимального веса, выход регистра 30 минимального веса соединен с вторым входом элемента 17 сравнения и с входом данных блока 10 оперативной памяти, выход элемента 43 задержки соединен с входом установки регистра 30 минимального веса и с входом установки регистра 29 номера дуги, выход третьего элемента И 37 соединен с синхровходом регистра 30 минимального веса и с синхровходом регистра 29 номера дуги, выход регистра 29 номера дуги соединен с информационным входом дешифратора 28 блокировки дуги, выход переполнения счетчика 27 дуг соединен с разрешающим входом дешифратора 28 блокировки дуги, а также с входом элемента 43 задержки, первым счетным входом реверсивного счетчика 9 ячеек и входом записи блока 10 оперативной памяти, выход элемента И 34 соединен со счетным входом счетчика 27 дуг и со входом элемента 44 задержки, выход которого соединен со вторым входом элемента И 37, первый вход которого соединен с выходом элемента 17 сравнения, второй вход элемента И 34 соединен с прямым выходом триггера 19 начала счета, который также соединен со вторым входом элемента И 35, третий вход элемента И 34 соединен с инверсным выходом триггера 23 режима, прямой выход которого соединен с третьим входом элемента И 35, выход элемента И 35 соединен со вторым счетным входом реверсивного счетчика 9 ячеек, выход которого подключен к адресному входу блока 10 оперативной памяти, выход которого подключен к первому входу умножителя 14, выход счетчика 13 расстояний подключен к второму входу умножителя 14, выход которого подключен к первому входу сумматора 15, второй вход которого подключен к выходу регистра 16 минимальной длины связей и к второму входу вычитателя 18, выход сумматора 15 подключен к входу данных регистра 16 минимальной длины связей, выход элемента 45 задержки подключен к синхровходу регистра 16 минимальной длины связей, выход элемента И 35 и счетный вход счетчика 12 расстояний подключены к входу элемента 45 задержки, выход одновибратора 42 подключен к синхровходу счетчика 12 расстояний, выход переполнения которого подключен к счетным входам счетчика 11 топологии, счетчика 13 расстояний и к входу одновибратора 42, выход счетчика 11 топологии подключен к входу счетчика 12 расстояний, вход 51 данных устройства подключен ко входу данных счетчика 11 топологии, синхровход счетчика 11 топологии подключен к входу 52 установки устройства, прямой выход триггера 24 задания топологии подключен к разрешающему входу счетчика 11 топологии, установочный вход триггера 24 задания топологии подключен к входу 49 установки устройства, вход сброса триггера 24 задания топологии подключен к входу 50 установки устройства, выход переполнения реверсивного счетчика 9 ячеек подключен к установочному входу триггера 23 режима, вход сброса которого подключен к входу 48 установки устройства, выход регистра 25 длины связей подключен ко второму входу элемента 26 сравнения и к первому входу вычитателя 18, первый вход элемента 26 сравнения подключен к выходу АЛУ 7 и входу данных регистра 25 длины связей, выход одновибратора 41 подключен к синхровходу регистра 25 длины связей, вход сброса триггера 19 начала счета подключен к входу 47 установки устройства, l-й выход дешифратора 8 выбора дуги (l=1, 2, …, m) соединен с l-м входом выбора дуги электронной модели 31 графа, l-й выход дешифратора 28 блокировки дуги соединен с l-м входом блокировки дуги электронной модели 31 графа, l-й выход веса дуги электронной модели 31 графа соединен с l-м входом блока элементов ИЛИ 36 и l-м входом блока элементов ИЛИ 46, выход элемента И 33.l соединен с l-м управляющим входом электронной модели 31 графа, выход блока элементов ИЛИ 46 соединен со вторым информационным входом АЛУ 7, выход элемента 26 сравнения соединен с входом одновибратора 41, выходы элементов ИЛИ 32.1-32.n подключены к соответствующим входам элементов И 33.1-33.m, выход вычитателя 18 соединен с выходом 53 длины связей устройства, а также дополнительно введенный блок 58 устройства планирования топологии логических интегральных схем (фиг.8), содержащий микропроцессор (МП) (фиг.8), оперативную память (ОП) (фиг.8), контроллер прямого доступа в память (КПРДП) (фиг.8), параллельный порт (Прпорт) (фиг.8), последовательный порт (Ппорт) (фиг.8), блок планирования топологии ПЛИС (БПТПЛИС), матрицу смежности (МС), матрицу цепей (МЦ) 9.1 блока БНО, блок поисковых перестановок (БПП) (фиг.11), блок нахождения минимальной нижней оценки (БНО) 9.7, блок поиска начального значения коммуникационной задержки (БНЗ) (фиг.10), сумматор нижней оценки суммарной длины межсоединений модулей ПЛИС 9.2, регистр временного хранения суммы блока БНО 9.3, счетчик вычисления адреса строки матрицы цепей (МЦ) блока БНО 9.5, счетчик вычисления адреса столбца матрицы цепей (МЦ) блока БНО 9.4, генератор импульсов 9.6, RS-триггер выбора работы матрицы цепей (МЦ) блока БНО 9.8, матрицу цепей (МЦ) блока БНЗ 10.1, сумматор степени близости максимальной задержки 10.2, регистр временного хранения промежуточных данных в процессе вычисления степени близости максимальной задержки 10.3, счетчик подсчета степени загрузки канала в текущей строке МЦ блока БНЗ 10.4, счетчик строк МЦ блока БНЗ перебора номеров контактов модуля ПЛИС 10.5, элемент задержки выбора работы блока «Начальные значения» 10.9, RS-триггер выбора работы матрицы цепей (МЦ) блока БНЗ 10.8, делитель вычисления ηн 12.1, регистр хранения кода значения Т0 12.2, ОЗУ временного хранения копии матрицы МЦ блока БНО 12.3, счетчик кода k хранения кода переменной к 12.4, счетчик кода i хранения кода переменной i 12.5, счетчик столбцов подсчета адреса столбцов в ОЗУ временного хранения копии матрицы МЦ блока БНО 12.6, счетчик строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО 12.7, вычитатель единицы из N 13.2, ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.1, элемент сравнения элементов матрицы МЦ с кодом значения единицы 13.2, элемент сравнения кода i со значением единица 13.3, элемент сравнения результата вычитания кодов k и i с кодом единица 13.5, вычитатель кодов k и i 13.6, регистр хранения кода числа i блока «Анализ необходимости перестановки» 13.7, RS-триггер выбора режима работы блока «Анализ необходимости перестановки» 13.8, элемент ИЛИ выбора номера сравнения в вычитателе единицы из N 13.9, элемент ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.11, элемент ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.10, элемент сравнения значения k из блока «Анализ необходимости перестановки» с единицей 13.12, регистр хранения кода числа k блока «Анализ необходимости перестановки» 13.13, ОЗУ моделирования матрицы M1 14.1, ОЗУ моделирования матрицы МС М 14.2, компаратор сравнения Ti и i 14.3, компаратор сравнения Ti и k 14.4, компаратор сравнения Tk и k 14.5, компаратор сравнения Ti и Tk 14.6, счетчик подсчета столбцов адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М 14.7, счетчик подсчета строк адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М 14.8, счетчик текущего значения i блока «Целенаправленные поисковые перестановки» 14.9, счетчик моделирования изменения параметра PromStr исследуемого метода 14.10, счетчик текущего значения k блока «Целенаправленные поисковые перестановки» 14.11, счетчик моделирования изменения параметра PromStolb исследуемого метода 14.12, ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы M1, реализуемую в алгоритме 15.2, ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М, реализуемую в алгоритме 15.3, сумматор суммирования кодов значений T1 15.4, делитель получения кода значения η 15.5, элемент сравнения кодов значений T1 и Т0 15.6, элемент сравнения кодов значений η и ηн 15.7, счетчик подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.11, счетчик для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.10, счетчик для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.9, счетчик для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.8, RS-триггер режима работы схемы 15.12, элемент ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.13, элемент ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.14, регистр временного хранения кодов при подсчете значения Т, алгоритма 15.16, причем Прпорт соединен с устройством БПТПЛИС, генератор тактовых импульсов блока БНО 9.6 соединен с тактовым входом счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО 9.5, выход переполнения счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО соединен с тактовым входом счетчика вычисления адреса столбца матрицы цепей (МЦ) блока БНО 9.4, выход переполнения которого соединен со входом разрешения работы счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО 9.5, а также со входом R RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНО 9.8, выход счетчика вычисления адреса столбца матрицы цепей (МЦ) блока БНО 9.4 соединен со входом a1 матрицы цепей (МЦ) блока БНО, выход счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО соединен со входом а2 матрицы цепей (МЦ) блока БНО 9.1, выход out матрицы цепей (МЦ) блока БНО 9.1 соединен со входом D1 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС 9.2, выход которого соединяется со входом D регистра временного хранения суммы блока БНО 9.3, выход которого соединен со входом D2 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС 9.2, а также на второй вход делителя вычисления ηн 12.1 и регистра хранения кода значения Т0 12.2, обратный выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНО 9.8 соединен со входом разрешения выдачи кода матрицы цепей (МЦ) блока БНО 9.1, генератор тактовых импульсов блока БНО 9.6 соединен с тактовым входом счетчика строк МЦ блока БНЗ перебора номеров контактов модуля 10.5, выход переполнения счетчика строк МЦ блока БНЗ перебора номеров контактов модуля ПЛИС 10.5 соединен с тактовым входом счетчика подсчета степени загрузки канала в текущей строке МЦ блока БНЗ 10.4, блока БНЗ, выход переполнения которого соединен со входом разрешения работы счетчика строк МЦ блока БНЗ перебора номеров контактов модуля 10.5, а также со входом RS-триггера выбора работы матрицы цепей (МЦ) блока БНЗ 10.8, выход счетчика подсчета степени загрузки канала в текущей строке МЦ блока БНЗ 10.4 соединен со входом a1 матрицы цепей (МЦ) блока БНЗ 10.1, выход счетчика строк МЦ блока БНЗ перебора номеров контактов модуля 1 отсоединен со входом а2 матрицы цепей (МЦ) блока БНЗ 10.1, выход out матрицы цепей (МЦ) блока БНЗ 10.1 соединен со входом D1 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС 10.2, выход которого соединяется со входом D регистра временного хранения суммы блока БНЗ, выход которого соединен со входом D2 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС 10.3, а также на второй вход делителя вычисления ηн 12.1, выход делителя вычисления ηн 12.1 соединяется со входом элемента сравнения кодов значений η и ηн 15.7, обратный выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНЗ 10.8 соединен со входом разрешения выдачи кода матрицы цепей (МЦ) блока БНЗ 10.1, а также с элементом задержки выбора работы блока «Начальные значения» 10.9, который соединяется с входом е ОЗУ временного хранения копии матрицы МЦ блока «Начальные установки», прямой выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНЗ 10.8 соединен со входом разрешения выдачи кода регистра хранения кода значения Т0 блока БНЗ 12.2, выход которого соединяется с первым входом делителя получения кода значения η 15.5, тактовый вход счетчика столбцов подсчета адреса столбцов в ОЗУ временного хранения копии матрицы МЦ блока БНО 12.6 соединен с выходом переполнения счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО 12.7, тактовый вход счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО 12.7 соединен с выходом генератора импульсов 9.6, выход счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО 12.7 соединен со входом а2 ОЗУ временного хранения копии матрицы МЦ блока БНО 12.3, выход счетчика столбцов подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО 12.6 соединен со входом a1 ОЗУ временного хранения копии матрицы МЦ блока БНО 12.3, счетчик кода k хранения кода переменной, счетчик кода i хранения кода переменной i, вход a1 ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.1 соединен с выходом элемента ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.10, вход а2 ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом элемента ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.1, первый вход элемента ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.10 соединен с выходом счетчика текущего значения i блока «Целенаправленные поисковые перестановки» 14.9, второй вход элемента ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.11 соединен с выходом регистра хранения кода числа k блока «Анализ необходимости перестановки» 13.13, первый вход элемента ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.11 соединен с выходом счетчика текущего значения k блока «Целенаправленные поисковые перестановки» 14.11, второй вход элемента ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.10 соединен с выходом счетчика текущего значения i блока «Целенаправленные поисковые перестановки» 14.9, выход out ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» 13.1 соединен со входом элемента сравнения элементов матрицы МЦ с кодом значения единицы 13.3, нулевой выход которого соединяется с тактовым входом счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО 12.7, а единичный выход элемента сравнения элементов матрицы МЦ с кодом значения единицы 13.3 соединен со входом элемента ИЛИ выбора номера сравнения в вычитателе единицы из N 13.2, выход которого соединен со входом е вычитателе единицы из N 13.2, на вход которого поступает код числа N, выход вычитателя единицы из N 13.2 соединяется с входом регистра хранения кода числа i блока «Анализ необходимости перестановки» 13.7, а также с входом регистра хранения кода числа k блока «Анализ необходимости перестановки » 13.13, выход регистра хранения кода числа i блока «Анализ необходимости перестановки» 13.7 соединяется с входом элемента сравнения кода i со значением единица 13.4, выход которого соединяется с разрешающим входом е регистра хранения кода числа k блока «Анализ необходимости перестановки» 13.13, выход регистра хранения кода числа k блока «Анализ необходимости перестановки» 13.13 соединяется с входом элемента сравнения кода k со значением единица 13.12, выход регистра хранения кода числа i блока «Анализ необходимости перестановки» 13.7 соединяется со вторым входом вычитателя кодов k и i 13.6, выход регистра хранения кода числа k блока «Анализ необходимости» перестановки 13.13 соединяется с первым входом вычитателя кодов k и i 13.6, выход которого соединен со входом элемента сравнения результата вычитания кодов k и i с кодом единица 13.5, единичный выход которого соединяется с входами е счетчика текущего значения k блока «Целенаправленные поисковые перестановки» 14.11 и счетчика моделирования изменения параметра PromStolb исследуемого метода 14.12, единичный выход элемента сравнения кода k со значением единица 13.12 соединяется с RS-тригтером выбора режима работы блока «Анализ необходимости перестановки» 13.8, обратный выход которого соединяется с входом элемента ИЛИ выбора номера сравнения в вычитателе единицы из N13.2, нулевой выход элемента сравнения результата вычитания кодов k и i с кодом единица 13.5 соединяется с тактовым входом счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО 12.6, вход a1 ОЗУ моделирования матрицы M1 14.1 соединен с выходом счетчика моделирования изменения параметра PromStr исследуемого метода 14.10, вход а2 ОЗУ моделирования матрицы M1 14.1 соединен с выходом счетчика моделирования изменения параметра PromStolb исследуемого метода 14.12, выход переполнения счетчика моделирования изменения параметра PromStr исследуемого метода 14.10 соединен с тактовым входом счетчика текущего шачения i блока «Целенаправленные поисковые перестановки» 14.9, выход которого соединен с первым входом компаратора сравнения Ti и i 14.3, выход переполнения счетчика моделирования изменения параметра PromStolb исследуемого метода 14.12 соединен с тактовым входом счетчика текущего значения PromStr блока «Целенаправленные поисковые перестановки» 14.10, выход которого соединен со вторым входом компаратора сравнения Ti и i 14.3, выход компаратора сравнения Ti и i 14.3 соединен с разрешающим входом е компаратора сравнения Ti и k 14.4, выход которого соединен с разрешающим входом е компаратора сравнения Tk и k 14.5, выход которого соединен с разрешающим входом е компаратора сравнения Ti и k 14.6, выход которого соединен с разрешающим запись входом we ОЗУ моделирования матрицы M1 14.1, и с входом ое ОЗУ моделирования матрицы МСМ 14.2, а также с тактовым входом счетчика подсчета строк адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М 14.8, выход которого соединен с входом а2 ОЗУ моделирования матрицы МС М 14.2, выход переполнения счетчика подсчета строк адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М 14.8 соединен с тактовым входом счетчика подсчета столбцов адреса ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М 14.7, выход которого соединен со входом a1 ОЗУ моделирования матрицы МС М 14.2, выход которого соединен со входом D ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы M1 14.1, первый вход компаратора сравнения Ti и k 14.5 соединен с выходом счетчика текущего значения PromStr блока «Целенаправленные поисковые перестановки» 14.10, второй вход компаратора сравнения Ti и k соединен с выходом счетчика текущего значения k блока «Целенаправленные поисковые перестановки» 14.11, первый вход компаратора сравнения Tk и k соединен с выходом счетчика моделирования изменения параметра PromStolb исследуемого метода 14.12, второй вход компаратора сравнения Tk и k соединен с выходом счетчика текущего значения k блока «Целенаправленные поисковые перестановки» 14.11, выход счетчика моделирования изменения параметра PromStr исследуемого метода 14.10 соединен с первым входом компаратора сравнения Ti и Tk, выход счетчика моделирования изменения параметра PromStolb исследуемого метода 14.12 соединен со вторым входом компаратора сравнения Ti и Tk 14.6. выход out ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.2 соединен со входом D ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.3, а также со входом D1 сумматора суммирования кодов значений Т1 15.4, выход которого соединяется с входом регистра временного хранения кодов при подсчете значения Т1 алгоритма 15.16, выход которого соединен со входом D2 сумматора суммирования кодов значений Т1 значений 15.4, а также с первым входом элемента сравнения кодов значений T1 и Т0 15.6, выход которого соединен с разрешающим входом делителя получения кода значения η 15.5, выход которого соединен с первым входом элемента сравнения кодов значений η и ηн 15.7, выход которого соединен с входом е сметчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.3, а также с входом е ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.3, выход счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.11 соединен со входом а2 ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.3, выход счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.10 соединен со входом a1 ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М15.3, выход счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.11 соединен со вторым входом элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.14, выход счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.10 соединен с первым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.13, выход генератора тактов 9.6 соединен с входом счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.9, выход которого соединен с первым входом элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.14, выход переполнения счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.11 соединен с тактовым входом счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.10, выход которого соединен с первым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.13, выход счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.8 соединен со вторым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.13, выход переполнения счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.8 соединен с входом е счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.9, а также с входом R RS-триггера режима работы схемы и входом с элемента сравнения кодов значений Т1 и Т0, выход переполнения счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.9 соединен с тактовым входом счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.8, обратный выход RS-триггера режима работы схемы 15.12 соединен с входом ое ОЗУ моделирования матрицы M1 15.2, а также с входом е элемента сравнения кодов значений η и ηн 15.7, выход генератора тактов 9.6 соединен с входом счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М и тактовым входом счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.9, выход переполнения которого соединяется с тактовым входом счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М 15.10, выход элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.14 соединяется с входом а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.2, выход элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.13 соединяется с входом a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 15.2, выход регистра временного хранения промежуточных данных в процессе вычисления степени близости максимальной задержки 15.16 соединяется с входом делимого делителя получения кода значения η 15.5.

Электронная модель 31 графа (фиг.17) содержит m электронных моделей дуги, причем электронная модель 31.l дуги (l=1, 2, …, m) содержит триггер 20.l блокировки дуги, регистр 21.l веса дуги, регистр 22.l блокировки дуги, первый элемент И 38.l, второй элемент И 39.l, элемент ИЛИ 40.l, причем входы элемента И 38.l соединены с соответствующими входами 56.y и 56.z задания графа устройства (где y и z - номера соответственно начальной и конечной вершины l-й дуги графа), выход элемента И 38.l соединен с синхровходом регистра 21.l веса дуги и с установочным входом триггера 20.l блокировки дуги, вход сброса которого соединен с l-м входом блокировки дуги модели 31, вход данных регистра 21.l веса дуги соединен с входом 54.l веса дуги устройства, первый вход элемента ИЛИ 40.l соединен с l-м управляющим входом модели 31, а второй вход элемента ИЛИ 40.l соединен с выходом элемента И 39.l, первый вход которого соединен с прямым выходом триггера 20.l блокировки дуги и с разрешающим входом регистра 22.l блокировки дуги, второй вход элемента И 39.l соединен с l-м входом выбора дуги модели 31, вход сброса регистра 22.l блокировки дуги соединен с входом 55.l сброса устройства, выход регистра 22.l блокировки дуги соединен с l-м выходом веса дуги модели 31, который также соединен с выходом регистра 21.l веса дуги, выход элемента ИЛИ 40.l подключен к разрешающему входу регистра 21.l веса дуги.

Назначение элементов и блоков устройства (фиг.16) состоит в следующем.

Первый и второй регистры 1 и 2 сдвига необходимы для реализации последовательного перебора пар вершин орграфа G.

Блок 3 формирования перестановок осуществляет перебор всех возможных размещений вершин графа G по позициям заданной топологической модели.

Блок 4 постоянной памяти хранит двоичные коды номеров позиций.

Блок 5 запоминания лучшего варианта служит для запоминания лучшего на настоящий момент варианта размещения.

Коммутатор 6 обеспечивает последовательное списывание из блока 4 кодов номеров выбираемых позиций для передачи их в АЛУ 7.

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

Дешифратор 8 выбора дуги вместе со счетчиком 27 дуг предназначены для выбора из ЭМГ 31 дуги с номером, записанным в счетчике 27.

Реверсивный счетчик 9 ячеек служит для организации последовательного перебора адресов блока 10 оперативной памяти в прямом и обратном порядке соответственно при записи информации и ее считывании.

Блок 10 оперативной памяти служит для хранения весов wi,j дуг орграфа G в порядке возрастания их значений.

Счетчик 11 топологии необходим для подсчета и передачи счетчику 12 количества обрабатываемых элементов вектора d k ' с заданным значением (для кольцевой топологической модели общее число таких элементов постоянно и составляет n, для линейной это число уменьшается от n-1 для d k ' = 1 до 1 для d k ' = n 1 ).

Первый счетчик 12 расстояний и второй счетчик 13 расстояний предназначены для организации перебора в возрастающем порядке ненулевых элементов матрицы расстояний D (таким образом на выходе счетчика 13 формируется вектор d k ' ).

Умножитель 14 необходим для умножения веса дуги из блока 10 оперативной памяти на расстояние между позициями топологической модели (элемент вектора d k ' ) из счетчика 13 расстояний.

Сумматор 15 предназначен для суммирования значений с умножителя 14 и регистра 16.

Регистр 16 минимальной длины связей хранит значение минимально возможной длины связей L* для заданного графа.

Первый элемент 17 сравнения служит для сравнения веса текущей дуги с наименьшим на данный момент весом, записанным в регистре 30.

Вычитатель 18 служит для нахождения степени оптимальности размещения £, по формуле (2). Значение L* поступает с выхода регистра 16 минимальной длины связей, L поступает с выхода регистра 25 длины связей.

Триггер 19 начала счета служит для индикации перехода из режима формирования размещения в режим его оценки.

Триггер 23 режима служит для хранения признака текущей операции. Если триггер 23 установлен в ноль - это означает запись весов дуг по возрастанию в блок 10 оперативной памяти, а в единицу - нахождение минимально возможной длины L по формуле (1).

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

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

Регистр 29 номера дуги служит для хранения номера дуги с минимальным весом, выбранной в текущем цикле работы устройства.

Регистр 30 минимального веса необходим для хранения значения минимального на данный момент веса дуги.

Группа элементов ИЛИ 32.1-32.n необходима для объединения соответствующих сигналов с регистров 1 и 2.

Группа элементов И 33.1-33.m предназначена для выбора соответствующих дуг графа G по сигналам с элементов ИЛИ 32.1-32.n.

Первый и второй элементы И 34 и 35 необходимы для блокировки передачи импульсов с тактового входа 57 устройства на элементы и блоки, обеспечивающие упорядочение весов дуг графа в блоке 10.

Второй блок элементов ИЛИ 36 необходим для подключения веса текущей дуги к элементу 17 сравнения и регистру 30.

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

Электронная модель 31 графа служит для моделирования топологии графа G, представляющего размещаемый объект (фиг.17).

Первый и второй одновибраторы 41 и 42 необходимы для формирования импульсов, управляющих записью информации в регистр 25 и счетчик 12 соответственно.

Первый элемент 43 задержки служит для задержки импульса переполнения со счетчика 27 дуг на время, достаточное для обеспечения блокировки дуги дешифратором 28 и записи минимального веса из регистра 30 в блок 10 оперативной памяти.

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

Третий элемент 45 задержки обеспечивает задержку импульса, поступающего на регистр 16 минимальной длины связей, на время, достаточное для подсчета и добавления очередного слагаемого формулы (1) умножителем 14 и сумматором 15.

Первый блок элементов ИЛИ 46 необходим для подачи в АЛУ 7 веса текущей дуги.

Электронная модель 31.l дуги (фиг.17) служит для моделирования 1-й дуги орграфа G, l=1,2, …, m.

Триггер 20.l блокировки дуги служит для выдачи сигнала блокировки повторного выбора соответствующей дуги во время работы устройства.

Регистр 21.l веса дуги и регистр 22.l блокировки дуги предназначены для хранения веса текущей дуги и нулевого кода соответственно. Регистры 21.l и 22.l имеют выходы с тремя состояниями; перевод выходов в третье (высокоимпедансное) состояние обеспечивается соответственно единичным и нулевым сигналом на входах разрешения (ое).

Первый элемент И 38.l необходим для формирования сигнала наличия l-й дуги в графе.

Второй элемент И 39.l служит для формирования сигнала выбора/блокировки дуги.

Элемент ИЛИ 40.l служит для объединения сигналов с элемента И 39.l и с элемента И 33.l.

Назначение элементов блока 58 формирования нижней оценки (фиг.18) состоит в следующем.

Ведущая ЭВМ микропроцессорной или многопроцессорной системы передает в акселератор планирования топологии ПЛИС матрицы смежности (МС) и матрицу цепей (МЦ), которой соответствует вариант топологии, имеющийся в данный момент. Акселератор планирования топологии ПЛИС представляет собой аппаратный акселератор на базе микропроцессорного контроллера и функционирует на основе методики перестановочного алгоритма планирования размещения подпрограмм в ПЛИС.

Со стороны ведущей ЭВМ в акселератор передают следующие данные:

- Матрицу смежности, соответствующую исходной программе (задаче);

- Матрицу цепей (МЦ), характеризующую вариант топологии ПЛИС на данный момент.

В контроллере реализованы следующие шаги алгоритма:

- Поиск нижней оценки Tinf;

- Формирование вектора по исходной МС;

- Поиск варианта перестановки строк в МЦ и его выполнение;

- Оценка варианта размещения по полученным данным; Принятие решения о целесообразности дальнейших перестановок.

На аппаратный уровень акселератора вынесены операции, требующие больших временных затрат, а именно вычисление показателя α в соответствии с выражением (3), поиск максимального количества смежных контактов (СК) по выражению (7) и вычисления итого общего показателя коммуникационной задержки по (5). Для его нахождения используется блок акселератора вычисления показателя коммуникационной задержки (АВПКЗ), подключенный к контроллеру через параллельный порт. Для расчета в блок АВПКЗ передается исходный вариант матрицы смежности и матрицы цепей. Далее она многократно используется при поиске. АВПКЗ вычисляет показатель. По окончании обработки МЦ блок АВПКЗ передает величину найденного показателя коммуникационной задержки в контроллер акселератора.

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

Структурная схема акселератора планирования топологии ПЛИС (ПТП) представлена на фиг.8.

На фиг.8. приняты следующие обозначения блоков и узлов: БПУПЛИС

- блок планирования топологии ПЛИС, МП - микропроцессор, ОП - оперативная память, КПРДП - контроллер прямого доступа в память, Пппорт - параллельный порт, Мс - матрица смежности, МЦ - матрица цепей, БПП -блок поисковых перестановок, БНО - блок нахождения минимальной нижней оценки, БНЗ-блок поиска начального значения коммуникационной задержки.

МП контроллера работает в соответствии с программой, записанной в ОП, передает исходные вариант матрицы смежности МС и матрицы цепей МЦ в блок БПТПЛИС, соответствующих топологии ПЛИС на данный момент. В этом случае необходим оперативный поиск нового варианта топологии, т.е. переразмещению подпрограмм, соответствующих решаемой в ПЛИС программе. Если необходимо составление нового варианта топологии, то в блок БПТПЛИС передаются матрицы МС и МЦ, содержащие нули.

Функциональная схема блока поиска нижней оценки (БНО) структурной организации акселератора планирования топологии 11ЛИС, приведенного на фиг.8, показана на фиг.9.

Матрица цепей 9.1 моделирует матрицу цепей МЦ.

Сумматор 9.2 необходим для вычисления формулы (2) алгоритма поиска гипотетической нижней оценки суммарной длины межсоединений модулей ПЛИС.

Регистр 9.3 временного хранения необходим для временного хранения промежуточных данных в процессе суммирования по формуле (2).

Первый 9.4 и второй 9.5 счетчики адреса предназначены для вычисления адресов в блоке 1 МЦ и последующей их выдачи на выход.

Генератор 9.6 импульсов служит для моделирования тактовых импульсов в процессе работы блока 9.7 поиска нижней оценки.

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

RS-триггер 9.8 предназначен для выбора работы блока 9.1.

Перед началом работы элементы блока блок 9.7 находится в следующих исходных данных.

В блоке 9.1 МЦ находится исходная топология ПЛИС, подлежащая перестройке. В регистре 9.3 находится код значения 0. Первый 9.4 счетчик хранит код числа 1 («00…01»), второй 9.5, счетчики в свою очередь содержит код нуля. RS-триггер находится в 0 состоянии. В результате с обратного выхода единица поступает на вход ое блока 9.1, разрешает выдачу данных на его выход.

В начале работы единичный тактовый импульс поступает с выхода генератора 9.4 и подается на тактовый вход счетчика 9.5 и по переднему фронту устанавливает в нем код значения единицы («00..01»). В результате, так как в счетчике 9.4 уже хранится код единицы, то коды значения один поступают с выходов счетчиков 9.4 и 9.5 на соответствующие адресные входы a1 и а2 блока 1. В результате, так как на входе ое присутствует единица, значение из ячейки памяти с адресом (1,1) выдается на выход блока 9.1. Это значение поступает па первый вход сумматора 9.2, на втором входе которого присутствует код нуля с выхода регистра 9.3. В результате сумма с выхода блока 9.2 поступает на D-вход регистра 9.3 для хранения. С выхода out блока МЦ 9.1 код поступает на вход D блока «Начальные установки», рассмотренного ниже.

Аналогично новый тактовый импульс с выхода генератора 9.6 поступает на счетный вход счетчика и увеличивает его содержимое по переднему фронту до кода двойки («0…01 ()»).

Далее схема работает аналогично до тех пор, пока на выходе переполнения счетчика 9.5 не появится единица, свидетельствующая, что столбцы рассмотрены и необходимо просматривать следующую строку. Единичный импульс с выхода переполнения счетчика 9.5 подается на счетный вход счетчика 9.4 и увеличивает его содержимое по переднему фронту до кода двойки («0…010»).

Далее схема работает аналогично до тех пор, пока на выходе переполнения счетчика 9.4 не появится единичный импульс, свидетельствующий о том, что работа схемы закончена и в регистре 9.3 содержится код минимальной нижней оценки суммарной длины межсоединений модулей ПЛИС. Тот же импульс поступает на К-вход триггера 9.8 и сбрасывает его в единичное состояние, в результате которого на входе ое блока 9.1 будет присутствовать 0, что запретит выдачу хранящихся в нем значений.

Функциональная схема блока вычисления начального значения (БНЗ) коммуникационной задержки до применения блока БПТПЛИС в соответствии с алгоритмом, описанным выше, структурная организация акселератора планирования топологии ПЛИС представлена на фиг.10.

Из фиг.10 можно заметить, что организация блока БНЗ по своей структурной организации подобна организации блока БНО. Основное отличие состоит в том, что сумму необходимо находить дважды, а в блоке БНО это делается один раз, так как дуги исходного графа не взвешены, как это делается в классическом варианте метода ветвей и границ, упорядочивать дуги матрицы смежности МС не нужно, поэтому возможно найти простую сумму.

Блок БНЗ состоит из следующих элементов. Матрица цепей 10.1 моделирует матрицу цепей МЦ.

Сумматор 10.2 необходим для вычисления формулы T H = max [ i = 1 N j = 1 α ν i j ] алгоритма размещения подпрограмм в ПЛИС, описанного вначале.

Регистр 10.3 временного хранения необходим для временного хранения промежуточных данных в процессе вычисления выражения T H = max [ i = 1 N j = 1 α ν i j ]

Первый 10.4 счетчик необходим для подсчета степени загрузки канала в данной строке МЦ.

Второй 10.5 счетчик строк МЦ служит для перебора номеров строк МЦ и фактически номеров контактов модуля ПЛИС.

Генератор 10.6 импульсов служит для моделирования тактовых импульсов в процессе работы БНО поиска нижней оценки.

Блок начального значения БНЗ предназначен для поиска начального значения коммуникационной задержки до применения предложенного в данной работе метода.

RS-триггер 10.8 предназначен для выбора режима работы блока 10.1. В нулевом состоянии с обратного выхода RS-триггера 8 единичное значение подается на ое-вход блока 10.1 и разрешает выдачу хранящихся в нем кодов. В единичном состоянии на входе ое присутствует ноль и поэтому выдача кодов на выход запрещена.

Элемент задержки 10.9 предназначен для выбора работы блока «Начальные значения».

Перед началом работы элементы блока блок БНЗ находится в следующих исходных данных.

В блоке 10.1 МЦ находится исходная топология ПЛИС, подлежащая перестройке, которая содержится в МЦ. В регистре 10.3 находится код значения 0, первый 10.4 счетчик хранит код числа 1 («00…01»), второй 10.5 счетчик в свою очередь содержит код нуля. RS-триггер находится в состоянии нуля («0…00»). С обратного выхода триггера 10.8 единица поступает на вход ое блока 10.1 и разрешает выдачу данных на его выход.

Работа блока БНЗ в целом аналогична работе блока БНО, описанного выше и показанного на фиг.9. Отличие состоит в работе счетчиков 10.4 и 10.5. Счетчик 10.5 перебирает столбцы МЦ до значения показателя α и фактически отвечает за анализ ширины канала в пределах данного контакта модуля ПЛИС. За номер контакта модуля ПЛИС отвечает счетчик 10.4. Как только все столбцы в пределах данного канала вывода модуля ПЛИС будут проанализированы, на выходе переполнения счетчика 10.5 возникает сигнал переполнения, который поступает на счетный вход счетчика 10.4 и увеличивает его содержимое на единицу, тем самым выбирая следующий вывод модуля ПЛИС для анализа.

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

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

На фиг.11 шаги алгоритма размещения подпрограмм в ПЛИС 6-20 разбиты на следующие блоки. Блок «Начальные установки» выполняет шаги алгоритма размещения подпрограмм в ПЛИС 6-8; блок «Анализ необходимости перестановки» отвечает за шаги 9-12, в которых выполняется анализ необходимости выполнения целенаправленных перестановок: блок «Целенаправленная перестановка» выполняет целенаправленную поисковую перестановку; в блоке «Анализ эффективности перестановки» вычисляются значения T1 и η и принимается решение о необходимости применения дальнейших перестановок.

На фиг.12 представлена функциональная схема блока «Начальные установки», входящего в состав блока БПП, структурная схема которого показана на фиг.8.

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

Делитель 12.1 выполняет деление поступающих на его вход кодов TH на Tinf.

Регистр 12.2 хранит код значения T0.

ОЗУ 12.3 M1 предназначено для временного хранения копии матрицы

МЦ.

Счетчик 12.4 кода k необходим для хранения кода переменной k.

Счетчик 12.5 кода i предназначен для хранения кода переменной i.

Счетчик 12.6 столбцов предназначен для подсчета адреса столбцов в ОЗУ 12.3.

Счетчик 12.7 строк необходим для подсчета адреса строк ОЗУ 12.3. До работы схемы элементы блока находятся в следующих начальных состояниях. В регистре 12.2 содержится код нуля («0…00»), в счетчиках 12.4 и 12.5 содержатся также коды нулей. В счетчике адреса строк 12.6 хранится код единицы («0…01»), а в адресном счетчике столбцов 12.7 хранится код нуля.

Блок функционирует следующим образом.

В соответствии с алгоритмом планирования топологии ПЛИС, описанным выше, после получения кодов Tinf (фиг.10) и T0(фиг.11), на следующем шаге выполняются предварительные начальные установки (шаги 6-8 алгоритма размещения подпрограмм в ПЛИС). Для вычисления показателя η H = T H T inf применяется делитель 12.3, на первый вход которого код TH, а на второй Tinf. В результате выполнения операции деления

соответствующий код поступает с выхода делителя 12.1, который используется в дальнейших шагах алгоритма. Одновременно с этим код значения Tinf подается на вход регистра 12.2. На его входе разрешения е присутствует единичный сигнал с прямого выхода RS-триггера 12.8 блока БНЗ, поэтому соответствующий код сохраняется в регистре.

В процессе получения кода значения TH в блоке БНЗ (фиг.11) создается копия матрицы М. для этого в устройство вводятся два дополнительных адресных счетчика 12.6 и 12.7. Так как на входе е блока 12.3 присутствует единичный сигнал с обратного выхода RS-триггера 10.8 блока БНЗ, работа ОЗУ 12.3 разрешена.

Тактовый импульс поступает на счетный вход счетчика 12.7 и по переднему фронту увеличивает его содержимое на единицу, устанавливая в нем код единицы. Этот код подается на адресный вход А2 ОЗУ 12.3. В это время на адресном входе А1 присутствует код единицы с выхода счетчика 12.6. Таким образом в ячейку ОЗУ 12.3 заносится код из МЦ 10.1 (фиг.10).

Так продолжается до тех пор, пока на выходе переполнения счетчика 12.7 не появиться единичный сигнал, который подается на счетный вход счетчика 6 и увеличивает хранящийся в нем код на единицу, устанавливая в нем код двойки («0…010»). Соответственно выбирается вторая строка, а счетчик 12.7 сбрасывается в единицу. Затем процесс повторяется до тех пор, пока на выходе переполнения счетчика 12.6 не появится единый сигнал, свидетельствующий, что в ОЗУ 3 сохранена копия матрицы М.

Шаг 8 алгоритма размещения подпрограмм в ПЛИС моделируется счетчиками 12.4 и 12.5. Так как на входе е присутствует единица с RS-триггера 11.8 (фиг.11), то работа этих счетчиков разрешена. Соответственно в счетчике 12.4 хранится код значения k, а в счетчике 12.5 - код значения i.

Блок «Анализ необходимости перестановки» моделирует шаги 9-12 алгоритма планирования топологии ПЛИС. Функциональная схема соответствующего устройства представлена на фиг.13. В функциональную схему предлагаемого блока входят следующие элементы. Матрица 13.1 цепей (МЦ) предназначена для хранения топологии ПЛИС. Так как предлагаемое устройство разбито на блоки, то данная матрица аналогична МЦ представленной на фиг.11.

ОЗУ 13.1 предназначено для временного хранения копии матрицы МЦ.

Первый 13.2 вычитатель служит для вычитания единицы из N и присвоения полученного кода разным переменным.

Первый 13.3 элемент сравнения необходим для сравнения элемента матрицы 13.1 МЦ с кодом значения единицы.

Второй 13.4 элемент сравнения служит для сравнения кода i со значением единица.

Третий 13.5 элемент сравнения служит для сравнения результата вычитания кодов k и i с кодом единица.

Второй 13.6 вычитатель предназначен для вычитания кодов k и i.

Регистр 13.7 служит для хранения кода числа i.

RS-триггер режима 13.8 необходим для выбора режима работы блока «Анализ необходимости перестановки». В нулевом состоянии выполняется первое сравнения выбранного из МЦ кода с единицей, а в режиме нуля второе сравнение. В обоих случаях для этого используется первый 2 вычитатель.

Первый 13.9 элемент ИЛИ служит для выбора номера сравнения в первом 13.2 вычитателе.

Второй 13.10 и третий 13.11 элементы ИЛИ служат для выбора из матрицы 13.1 кодов по соответствующим адресам.

Четвертый 13.12 элемент сравнения необходим для сравнения значения k с единицей.

Регистр 13.13 служит для хранения кода числа k.

До начала работы устройства, его элементы находятся в следующих исходных состояниях. В блоке 13.1 МЦ содержится исходный вариант топологии ПЛИС, в регистре 13.9 хранится код нуля, в регистрах 13.9, 13.15 содержатся коды нулей.

С приходом кода от верхнего устройства на первый вход элемента 13.11 ИЛИ, код проходит адресный вход а2 и, так как на адресном входе a1, выбранный код с блока 13.1 подается на элемент сравнения 13.3, где происходит сравнение с кодом единицы («0…01»). Если результат отрицательный, то единичный импульс подается на устройство верхнего уровня (изображенного на фиг.12). Если результат сравнений положительный (=1), то единичный импульс проходит через элемент 13.9 ИЛИ и далее поступает на разрешающий е-вход вычитателя 13.2. В результате вычитания, результат подается для сохранения на вход вычитателя 13.2. Сохраненный код с выхода вычитателя 13.2 поступает на входы регистра 13.7 и на вход регистра 13.13, но так как на разрешающим е-входе присутствует ноль, то его работа запрещена. Одновременно код с выхода вычитателя 13.2 сохраняется в регистре 13.7 и этот код передается на элемент сравнения 13.4 с кодом числа один, на первый вход элемента 13.10 ИЛИ и на первый вход вычитателя 13.6. Так как на адресном коде а2 элемента 13.1 не присутствует кода, то дальнейших действий не происходит, а на разрешающем е-входе элемента 13.6 нет соответствующего разрешающего сигнала и этот элемент так же не работоспособен.

В это время, если результат сравнения в элементе 13.4 положительный, то единичный сигнал с выхода элемента 13.4 сравнения поступает на разрешающий е-вход регистра 13.13. В результате код с вычитателя 13.2 поступает на вход регистра 13.13, где сохраняется это значение.

Код с выхода регистра 13.13 поступает на второй вход элемента вычитателя 13.6 и второй вход элемента 13.11 ИЛИ и далее на адресный вход а2 элемента 13.1. Так как на перовом входе элемента 6 присутствует код, то в результате вычитания, соответствующий код подается на элемент 13.5 сравнения с единицей. Если соответствующее значение меньше числа один, то единичный импульс поступает на разрешающие е-входы счетчиков 14.11 и 14.12 (фиг.14).

Одновременно с этим код с регистра 13.7 поступил на первый вход элемента 10 ИЛИ. В результате этого, так как на втором адресном входе а2 уже присутствует соответствующее значение, а не его первый адресный вход a1 поступил соответствующий код, то код с выбранной ячейки поступил на вход сравнения с единицей.

Далее процесс продолжается заново, но при этом, так как на прямом выходе элемента 13.5 единица, то начинается работа блока «Целенаправленная перестановка».

Следующий основной этап предложенною алгоритма целенаправленные поисковые перестановки. Функциональная схема соответствующего блока представлена на фиг.14.

Назначение представленного на фиг.14 блока состоит в следующем.

ОЗУ 14.1 M1 предназначено для моделирования матрицы M1.

ОЗУ 14.2 М необходимо для моделирования матрицы МС М.

Первый 14.3, второй 14.4, третий 14.5 и четвертый 14.6 компараторы служат для анализа на равенство кодов значения i и k поступающих на их вход значений.

В первом 14.7 и втором 14.8 счетчиках адреса содержаться коды адреса строки и столбца соответственно, служащие для выбора значения из ОЗУ 14.2.

Счетчик 14.9 значения i необходим для хранения текущего значения параметра i.

Счетчик 14.10 параметра PromStr необходим для моделирования изменения параметра PromStr исследуемого метода.

Счетчик 14.11 значения k необходим для хранения текущего значения параметра k.

Счетчик 14.12 параметра PromStolb необходим для моделирования изменения параметра PromStolb исследуемого метода.

В исходном состоянии в матрице 14.1 M1 находится временная матрица, соответствующая текущему на данный момент состоянию алгоритма. В матрице М хранится матрица смежности исходной программы. В счетчике 14.10 хранится код значения PromStr. Счетчик 14.12 содержит код значения PromStolb, счетчики 14.9 и 14.11 содержат соответствующие коды текущих параметров i и k рассматриваемого алгоритма. Первый 14.7 счетчик адреса хранит код числа единица («0…01»), что соответствует первой строке матрицы М, второй 14.8 счетчик адреса содержит адрес столбца матрицы М и в исходном состоянии.

Предлагаемый блок функционирует следующим образом.

Данный фрагмент схемы выполняется в п.13 агоритма размещения подпрограмм в ПЛИС и на данном этапе в переменной i уже содержится номер строки, а в перемененной k номер строки с которой необходимо совершить перестановку. Необходимые коды i и k хранятся в счетчиках 14.9 и 14.11 соответственно. В счетчиках 14.10 и 14.12 хранятся индексы переменных в матрицах М и M1. Поэтому никаких дополнительных операций не нужно. В соответствии с (п.13 агоритма размещения подпрограмм в ПЛИС перед перестановкой) необходим анализ ∀((PromStr,PromStolb≠i)&(PromStr.PromStolb≠k)), ∀((PromStr=i)&(PromStolb=k)). Для этого служат элементы 14.3, 14.4, 14.5 и 14.6 сравнения. Сравнение происходит последовательно для всех возможных вариантов. В случае если результат сравнения в элементе 14.3 сравнения положительный, соответствующий единичный импульс подается на разрешающий вход элемента 14.4 сравнения, что в свою очередь разрешает его работу. В случае если результат всех сравнений положительный, то единичный импульс с с выхода элемента сравнения 6 подается на ое-вход матрицы 14.2 М. В это время на соответствующих адресных входах А1 и А2 присутствуют адреса ячейки в матрице 14.2 М, которую необходимо сохранить в промежуточной матрице 14.1 М. При этом единичный импульс с выхода элемента сравнения поступил на счетный вход счетчика 8 и увеличил содержащийся в нем код до числа единица (0…01). Тот же импульс поступил на we-вход разрешения записи и тем самым разрешил запись выбранного из матрицы 14.2 значения в матрицу M1 по адресу, который хранится в счетчиках 14.10 и 14.12. Соответствующее значение сохраняется в матрице 14.1 М.

В случае появления на выходах переполнения счетчиков 14.8, 14.11 и 14.12 единичного импульса, соответствующий сигнал поступает на счетные входы счетчиков 14.7, 14.9 и 14.10 увеличивает хранящиеся в них коды на единицу, а сами счетчики сбрасываются в исходные значения.

Так продолжается до тех пор, пока на выходах переполнения счетчиков 14.7 и 14.9 не появится единичный импульс, свидетельствующий, что перестановка завершена и необходимо переходить к анализу достигнутого результата (шаги 14-20 алгоритма размещения подпрограмм в ПЛИС).

Функциональная схема блока «Анализ эффективности перестановки», которая выполняется на заключительном этапе алгоритма планирования топологии ПЛИС (шаги 14-20 алгоритма) представлена на фиг.15.

Блок 15.1 анализа эффективности перестановки содержит следующие элементы.

ОЗУ 15.2 M1 моделирует временную матрицу M1, необходимую в процессе реализации алгоритма.

ОЗУ 15.3 М предназначена для моделирования матрицы смежности М.

Сумматор 15.4 необходим для суммирования кодов значений Т1 при выполнении п.14 алгоритма поисковых перестановок.

Делитель 15.5 служит для получения кода значения η.

Первый 15.6 элемент сравнения служит для сравнения кодов значений T1 и Т0.

Второй 15.7 элемент сравнения предназначен для сравнения кодов значений η и ηн.

Первый 15.8 и второй 15.9 счетчики адреса необходимы для подсчета адреса ячеек памяти ОЗУ 15.2 M1.

Третий 15.10 и четвертый 15.11 счетчики адреса служат для подсчета значений адреса ОЗУ 3 М.

RS-триггер 15.12 режима предназначен для выбора режима работы схемы. В состоянии 1 на инверсном выходе триггера 15.12 выполняется п.14 алгоритма поисковых перестановок, т.е. выполняется подсчет значения Т1. В состоянии ноль на прямом выходе происходят проверочные расчеты, необходимые для анализа достигнутого результата.

Первый 15.13 и второй 15.14 элементы ИЛИ служат для объединения кодов, подаваемых на первый a1 и второй а2 адресные входы ОЗУ 2 М 1.

Генератор 15.15 импульсов предназначен для возбуждения тактовых импульсов, предназначенных для работы блока 15.1 анализа эффективности.

Регистр 15.16 временного хранения необходим для временного хранения кодов при подсчете значения Т1 алгоритма.

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

Первоначально необходимо найти значение Т, как показатель достигнутой временной задержки в результате выполненной поисковой перестановки. Для этого с выхода генератора 15.15 импульсов тактовый импульс поступает на счетный вход счетчика 15.9 и по переднему фронту увеличивает его содержимое на единицу до кода единицы («0…01»). Так как в счетчике 15.8 установлено начальное значение единицы, то оба кода проходят через элементы 15.8 и 15.9 ИЛИ и поступают на соответствующие адресные входы a1 и а2 ОЗУ 2. Так как на разрешающем ое-входе присутствует единичный потенциал с инверсного выхода триггера 15.12, то код первой ячейки памяти ОЗУ 15.2 поступает на его выход и далее подается на первый вход сумматора 15.4. На втором его входе присутствует код нуля с выхода регистра 15.16.

В результате сравнения полученный результат сохраняется в регистре 15.16 и процесс повторяется до полного подсчета значения Т1. Об этом свидетельствует единичный потенциал с выход переполнения счетчика 15.8. Он подается на R-вход и на е-вход разрешения элемента 15.6 сравнения, чем разрешает его работу.

В итоге результат деления поступает на первый вход элемента 15.7 сравнения для сравнения с кодом ηн. Если в результате сравнения полученное значение η окажется меньше значения ранее полученного ηн, то работа устройства на этом завершается и соответствующий сигнал подается в ведущую ЭВМ для дальнейшего анализа и принятия решения о последующих действиях. В случае отрицательного результата (η>ηн), соответствующий результат деления поступает на разрешающий е-вход счетчика 15.11. Этот счетчик вместе с подобным счетчиком 15.10 необходимы для реализации операции записи вновь полученной временной матрицы M1 в матрицу М. Это значит что результат пробной перестановки оказался удачным и необходимо сохранение полученного результата в исходную матрицу смежности, как наилучший на данный момент вариант топологии ПЛИС.

В этом случае счетчики 15.10 и 15.11 работают как адресные входы для ОЗУ 15.3. Их работа заключается в следующем. С каждым тактовым импульсом с выхода генератора 15.15 импульсов, соответствующий сигнал подается на счетный вход счетчика 15.11 и по переднему фронту увеличивает его содержимое на единицу. Соответствующий код поступает на адресный вход А2 ОЗУ 15.2, что является адресом столбца исходной матрицы смежности М. Адрес строки хранится в счетчике 15.10 и поступает на адресный вход А1.

Процесс записи матрицы 15.2 M1 в матрицу смежности 15.3 М заключается в следующем. После каждого увеличения счетчика 15.11 на единицу, соответствующий код подается кроме адресного входа А2 ОЗУ 15.3 еще и на адресный вход а2 через элемент 15.14 ИЛИ. В то же время на элементе 15.13 ИЛИ присутствует код адреса строки со счетчика 15.10, который поступает на адресный a1 вход ОЗУ 15.2. В резулыате из выбранной ячейки памяти ОЗУ 15.2 код подается на вход D данных ОЗУ 15.3 и так как на его разрешающем е-входе присутствует единичный потенциал, то соответствующий код с выхода ОЗУ 15.2 записывается в ОЗУ 15.3.

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

1. Устройство поиска нижней оценки размещения в матричных системах при двунаправленной передаче информации, содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок (БФП), блок постоянной памяти, блок запоминания лучшего варианта (БЗЛВ), коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу с 1-го по n-й элементов ИЛИ, группу 1-го по m-й элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, второй и третий элементы задержки, первый блок элементов ИЛИ, причем выходы БФП соединены с соответствующими входами блока постоянной памяти и соответствующими входами БЗЛВ, сигнализирующий выход БФП соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом АЛУ, выход которого соединен с информационным входом БЗЛВ, а выход БЗЛВ соединен с первым информационным входом АЛУ, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы первого и второго регистров сдвига с первого по n-й подключены к первым и вторым входам элементов ИЛИ 1-го по n-й соответственно, выход переполнения регистра сдвига соединен с управляющим входом АЛУ и с управляющим входом БФП, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом БФП и с первыми входами первого и второго элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход первого элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом третьего элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход первого элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом второго элемента И, третий вход первого элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом второго элемента И, выход второго элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход которого подключен к первому входу умножителя, выход счетчика расстояний подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу регистра минимальной длины связей и к второму входу вычитателя, выход сумматора подключен к входу данных регистра минимальной длины связей, выход элемента задержки подключен к синхровходу регистра минимальной длины связей, выход второго элемента И и счетный вход счетчика расстояний подключены к входу третьего элемента задержки, выход второго одновибратора подключен к синхровходу счетчика расстояний, выход переполнения которого подключен к счетным входам счетчика топологии, счетчика расстояний и к входу второго одновибратора, выход счетчика топологии подключен к входу счетчика расстояний, вход данных устройства подключен ко входу данных счетчика топологии, синхровход счетчика топологии подключен к входу установки устройства, прямой выход триггера задания топологии подключен к разрешающему входу счетчика топологии, установочный вход триггера задания топологии подключен к входу установки устройства, вход сброса триггера задания топологии подключен к входу установки устройства, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, выход регистра длины связей подключен ко второму входу элемента сравнения и к первому входу вычитателя, первый вход элемента сравнения подключен к выходу АЛУ и входу данных регистра длины связей, выход одновибратора подключен к синхровходу регистра длины связей, вход сброса триггера начала счета подключен к входу установки устройства, 1-й выход дешифратора выбора дуги (l=1, 2, …, m) соединен с 1-м входом выбора дуги электронной модели графа, 1-й выход дешифратора блокировки дуги соединен с 1-м входом блокировки дуги электронной модели графа, 1-й выход веса дуги электронной модели графа соединен с 1-м входом блока элементов ИЛИ и 1-м входом блока элементов ИЛИ, 1-й выход элемента И группы элементов И с 1-го по m-й соединен с 1-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом АЛУ, выход элемента сравнения соединен с входом первого одновибратора, выходы элементов с 1-го по n-й ИЛИ подключены к соответствующим входам элементов И 1-го по m-й, выход вычитателя соединен с выходом длины связей устройства, отличающееся тем, что в него дополнительно введен блок устройства планирования топологии логических интегральных схем, содержащее микропроцессор (МП), оперативную память (ОП, контроллер прямого доступа в память (КПРДП), параллельный порт (Прпорт), последовательный порт (Ппорт), блок планирования топологии ПЛИС (БПТПЛИС), матрицу смежности (МС), матрицу цепей (МЦ) блока БНО, блок поисковых перестановок (БПП), блок нахождения минимальной нижней оценки (БНО), блок поиска начального значения коммуникационной задержки (БНЗ) сумматор нижней оценки суммарной длины межсоединений модулей ПЛИС, регистр временного хранения суммы блока БНО, счетчик вычисления адреса строки матрицы цепей (МЦ) блока БНО, счетчик вычисления адреса столбца матрицы цепей (МЦ) блока БНО, генератор импульсов, RS-триггер выбора работы матрицы цепей (МЦ) блока БНО, матрицу цепей (МЦ) блока БНЗ, сумматор степени близости максимальной задержки, регистр временного хранения промежуточных данных в процессе вычисления степени близости максимальной задержки, счетчик подсчета степени загрузки капала в текущей строке МЦ блока БНЗ, счетчик строк МЦ блока БНЗ перебора номеров контактов модуля ПЛИС, элемент задержки выбора работы блока «Начальные значения», RS-триггер выбора работы матрицы цепей (МЦ) блока БНЗ, делитель вычисления ηн, регистр хранения кода значения T0, ОЗУ временного хранения копии матрицы МЦ блока БНО, счетчик кода 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, реализуемую в алгоритме, ОЗУ блока «Целенаправленные поисковые перестановки» моделирования временной матрицы М, реализуемую в алгоритме, сумматор суммирования кодов значений Т1, делитель получения кода значения η, элемент сравнения кодов значений Т1 и Т0, элемент сравнения кодов значений η и ηн, счетчик подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, счетчик для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, счетчик для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, счетчик для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М1, RS-триггер режима работы схемы, элемент ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, элемент ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, регистр временного хранения кодов при подсчете значения Т1 алгоритма, причем Прпорт соединен с устройством БПТПЛИС, генератор тактовых импульсов блока БНО соединен с тактовым входом счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО, выход переполнения счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО соединен с тактовым входом счетчика вычисления адреса столбца матрицы цепей (МЦ) блока БНО, выход переполнения которого соединен со входом разрешения работы счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО, а также со входом R RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНО, выход счетчика вычисления адреса столбца матрицы цепей (МЦ) блока БНО соединен со входом a1 матрицы цепей (МЦ) блока БНО, выход счетчика вычисления адреса строки матрицы цепей (МЦ) блока БНО соединен со входом а2 матрицы цепей (МЦ) блока БНО, выход out матрицы цепей (МЦ) блока БНО соединен со входом D1 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, выход которого соединяется со входом D регистра временного хранения суммы блока БНО, выход которого соединен со входом D2 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС1, а также на второй вход делителя вычисления ηн и регистра хранения кода значения T0, обратный выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНО соединен со входом разрешения выдачи кода матрицы цепей (МЦ) блока БНО, генератор тактовых импульсов блока БНО соединен с тактовым входом счетчика строк МЦ блока БНЗ перебора номеров контактов модуля, выход переполнения счетчика строк МЦ блока БНЗ перебора номеров контактов модуля ПЛИС соединен с тактовым входом счетчика подсчета степени загрузки канала в текущей строке МЦ блока БНЗ, блока БНЗ, выход переполнения которого соединен со входом разрешения работы счетчика строк МЦ блока БНЗ перебора номеров контактов модуля, а также со входом RS-триггера выбора работы матрицы цепей (МЦ) блока БНЗ, выход счетчика подсчета степени загрузки канала в текущей строке МЦ блока БНЗ соединен со входом a1 матрицы цепей (МЦ) блока БНЗ, выход счетчика строк МЦ блока БНЗ перебора номеров контактов модуля соединен со входом а2 матрицы цепей (МЦ) блока БНЗ, выход out матрицы цепей (МЦ) блока БНЗ соединен со входом D1 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, выход которого соединяется со входом D регистра временного хранения суммы блока БНЗ, выход которого соединен со входом D2 сумматора нижней оценки суммарной длины межсоединений модулей ПЛИС, а также на второй вход делителя вычисления ηн, выход делителя вычисления ηн соединяется со входом элемента сравнения кодов значений η и ηн, обратный выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНЗ 108 соединен со входом разрешения выдачи кода матрицы цепей (МЦ) блока БНЗ, а также с элементом задержки выбора работы блока «Начальные значения», который соединяется с входом в ОЗУ временного хранения копии матрицы МЦ блока «Начальные установки», прямой выход RS-триггера выбора разрешения выдачи результата матрицы цепей (МЦ) блока БНЗ соединен со входом разрешения выдачи кода регистра хранения кода значения Т0 блока БНЗ, выход которого соединяется с первым входом делителя получения кода значения η, тактовый вход счетчика столбцов подсчета адреса столбцов в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен с выходом переполнения счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО, тактовый вход счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен с выходом генератора импульсов, выход счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен со входом а2 ОЗУ временного хранения копии матрицы МЦ блока БНО, выход сметчика столбцов подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО соединен со входом a1 ОЗУ временного хранения копии матрицы МЦ блока БНО, счетчик кода k хранения кода переменной k, счетчик кода i хранения кода переменной i, вход a1 ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом элемента ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки», вход а2 ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом элемента ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки», первый вход элемента ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом счетчика текущего значения i блока «Целенаправленные поисковые перестановки», второй вход элемента ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом регистра хранения кода числа k блока «Анализ необходимости перестановки», первый вход элемента ИЛИ выбора строки ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом счетчика текущего значения k блока «Целенаправленные поисковые перестановки», второй вход элемента ИЛИ выбора столбца ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен с выходом счетчика текущего значения i блока «Целенаправленные поисковые перестановки», выход out ОЗУ временного хранения копии матрицы МЦ блока «Анализ необходимости перестановки» соединен со входом элемента сравнения элементов матрицы МЦ с кодом значения единицы, нулевой выход которого соединяется с тактовым входом счетчика строк подсчета адреса строк в ОЗУ временного хранения копии матрицы МЦ блока БНО, а единичный выход элемента сравнения элементов матрицы МЦ с кодом значения единицы соединен со входом элемента ИЛИ выбора номера сравнения в вычитателе единицы из N, выход которого соединен со входом е вычитателя единицы из N, на вход которого поступает код числа N, выход вычитателя единицы из N соединяется с входом регистра хранения кода числа i блока «Анализ необходимости перестановки», а также с входом регистра хранения кода числа k блока «Анализ необходимости перестановки», выход регистра хранения кода числа i блока «Анализ необходимости перестановки» соединяется с входом элемента сравнения кода i со значением единица, выход которого соединяется с разрешающим входом е регистра хранения кода числа 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 сумматора суммирования кодов значений Т1, выход которого соединяется с входом регистра временного хранения кодов при подсчете значения Т1 алгоритма, выход которого соединен со входом D2 сумматора суммирования кодов значений T1 значений, а также с первым входом элемента сравнения кодов значений Т1 и Т0, выход которого соединен с разрешающим входом делителя получения кода значения η, выход которого соединен с первым входом элемента сравнения кодов значений η и ηн, выход которого соединен с входом е счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, а также с входом е ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен со входом а2 ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен со входом a1 ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен со вторым входом элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен с первым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход генератора тактов соединен с входом счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход которого соединен с первым входом элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход переполнения счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М соединен с тактовым входом счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход которого соединен со первым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, соединен со вторым входом элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход переполнения счетчика для подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединен с входом е счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, а также с входом R RS-триггера режима работы схемы и входом е элемента сравнения кодов значений Т1 и Т0, выход переполнения счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединен с тактовым входом счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, обратный выход RS-триггера режима работы схемы соединен с входом ое ОЗУ моделирования матрицы M1, а также с входом е элемента сравнения кодов значений η и ηн, выход генератора тактов соединен с входом счетчика подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М и тактовым входом счетчика для подсчета строк адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход переполнения которого соединяется с тактовым входом счетчика подсчета столбцов адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы М, выход элемента ИЛИ объединения кода а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединяется с входом а2 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход элемента ИЛИ объединения кода a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1 соединяется с входом a1 адреса ОЗУ блока «Анализ эффективности перестановки» моделирования временной матрицы M1, выход регистра временного хранения промежуточных данных в процессе вычисления степени близости максимальной задержки соединяется с входом делимого делителя получения кода значения η.

2. Устройство по п.1, отличающееся тем, что электронная модель графа содержит m электронных моделей дуги, причем l-я электронная модель дуги (l=1, 2, …, m) содержит триггер блокировки дуги, регистр веса дуги, регистр блокировки дуги, первый элемент И, второй элемент И, элемент ИЛИ, причем входы первого элемента И соединены с соответствующими входами задания графа устройства, выход первого элемента И соединен с синхровходом регистра веса дуги и с установочным входом триггера блокировки дуги, вход сброса которого соединен с l-м входом блокировки дуги электронной модели графа, вход данных регистра веса дуги соединен с l-м входом веса дуги устройства, первый вход элемента ИЛИ соединен с l-м управляющим входом электронной модели графа, а второй вход элемента ИЛИ соединен с выходом второго элемента И, первый вход которого соединен с прямым выходом триггера блокировки дуги и с разрешающим входом регистра блокировки дуги, второй вход второго элемента И соединен с l-м входом выбора дуги электронной модели графа, вход сброса регистра блокировки дуги соединен с l-м входом сброса устройства, выход регистра блокировки дуги соединен с l-м выходом веса дуги электронной модели графа, который также соединен с выходом регистра веса дуги, выход элемента ИЛИ подключен к разрешающему входу регистра веса дуги.



 

Похожие патенты:

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

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

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

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

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

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

Изобретение относится к области автоматизированного управления технологическими процессами и может применяться для многопараметрических объектов, в частности структуры системы управления (СУ) для проектирования бортовых интеллектуальных систем (БИС) обеспечения безопасности мореплавания.

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

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

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

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

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

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

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

Изобретение относится к вычислению приближенных статических давлений в скважине для одной или нескольких скважин произвольной формы в однородных и неоднородных коллекторах. Технический результат - более точное вычисление аппроксимации истинных статических давлений в скважине на каждом временном шаге имитатора, что приводит к улучшенному расчету приближенных статических давлений для скважин произвольной формы в однородных и неоднородных коллекторах и отсутствию дополнительных вычислений для расчета эффективного объема дренирования за счет расчета векторов потока флюида на каждой итерации в численном имитаторе коллектора. Определение приближенных статических давлений основано на оценивании объема дренирования одной или нескольких скважин. Причем объем дренирования, например, можно оценивать из одного или нескольких расчетных векторов потока флюида и приближенные статические давления в скважине можно затем вычислять путем взятия среднего по объему порового пространства динамических давлений блока сетки в объеме дренирования одной или нескольких скважин. При этом один или несколько векторов потока флюида можно вычислять на каждой итерации в численном имитаторе коллектора в рамках стандартных имитационных вычислений. 5 н. и 45 з.п. ф-лы, 19 ил.
Изобретение относится к области проектирования сложных механических устройств. Техническим результатом является обеспечение возможности синхронизировать множество форматов файлов CAD механического устройства с перечнем деталей. Способ содержит этап создания файла CAD, содержащего геометрическое представление элемента, и файла данных, содержащего матрицу трехмерного позиционирования для упомянутого по меньшей мере одного элемента набора вместе с по меньшей мере одним указателем на упомянутый файл CAD, содержащий геометрическое представление элемента набора, и этапы вычисления вектора трехмерного позиционирования для упомянутого элемента и создания структуры данных перечня деталей, где структура данных содержит идентификатор набора, идентификатор элемента, по меньшей мере одну связь между идентификатором элемента и файлом CAD, содержащим геометрическое представление элемента, по меньшей мере одну связь между идентификатором набора и файлом данных, содержащим матрицу трехмерного позиционирования для упомянутого по меньшей мере одного элемента набора, и вектор позиционирования. 7 н. и 2 з.п. ф-лы, 10 ил.
Изобретение относится к компьютерному проектированию технологического процесса производства металлоизделий, состоящего из последовательности процессов: получения заготовки литьем, обработки давлением и термообработки литой заготовки. Технический результат - повышение вариативности комбинирования вычислительных сред конечно-элементного анализа при компьютерном проектировании технологических циклов производства металлопродукции. В начале проводят испытания стандартных образцов материала металлоизделия для определения значений теплопроводности, теплоемкости, плотности и сопротивления деформации. Файлы базы данных, полученной по результатам компьютерного проектирования процесса получения литой заготовки, выводят на экран монитора, одновременно туда же выводят требования к данным, импортируемым в вычислительную среду конечно-элементного анализа для компьютерного проектирования процессов обработки давлением и термообработки. Из файлов базы данных выделяют данные, соответствующие требованиям, и копируют их. Затем создают пустой файл, вставляют в его скопированные данные, сохраняют полученный файл, открывают сохраненный файл в среде компьютерного проектирования процессов обработки давлением и термообработки и, используя эти данные, начинают компьютерное проектирование процессов обработки давлением и термообработки литой заготовки. 5 ил.

Изобретение относится к проектированию подводных трубопроводных систем, подверженных вызванному водородом растрескиванию под напряжением. Технический результат - вычисление локальных напряжений в элементах трубопровода путем постобработки сил и моментов модели трубы, представляющей систему трубопровода. Система для проверки того, что подводные системы трубопроводов пригодны для оценок вызванного водородом растрескивания под напряжением содержит: компонент генератора функции преобразования, создающий упомянутую функцию; компонент механизма функции преобразования, исполняющий упомянутую функцию; компонент хранения функции преобразования; анализ упомянутой оценки локального напряжения на первое заранее заданное условие пригодности, и если упомянутая оценка локального напряжения не является пригодной, то определение и выполнение трехмерной подмодели для упомянутого элемента и анализ выходных данных упомянутой трехмерной подмодели на соответствие второму заранее заданному условию пригодности. 3 н. и 11 з.п. ф-лы, 9 ил.

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

Группа изобретений предназначена для автоматического определения набора параметров для проектирования турбомашин. Технический результат - создание алгоритма оптимизации определения набора параметров настройки/калибровки для проектирования турбомашин. Для этого предложен способ, включающий ввод исходного набора параметров настройки/калибровки; вычисление количественных параметров семейства турбомашин на основе исходного набора параметров настройки/калибровки; сравнение вычисленных количественных параметров семейства турбомашин с измеренными количественными параметрами и вычисление первого расхождения между вычисленными количественными параметрами семейства и измеренными количественными параметрами; вычисление второго расхождения между исходным набором параметров настройки/калибровки и заданными по умолчанию значениями переменных турбомашины; формирование модифицированной целевой функции, которая включает как упомянутое первое, так и упомянутое второе расхождение; изменение, в течение итеративной процедуры, упомянутого исходного набора параметров настройки/калибровки таким образом, чтобы найти окончательный набор параметров настройки/калибровки, при этом упомянутый окончательный набор параметров настройки/калибровки обеспечивает (1) наилучшее соответствие между количественными параметрами семейства турбомашин и измеренными количественными параметрами, и (2) гладкий переход в упомянутом окончательном наборе параметров настройки/калибровки от одной модели упомянутого семейства к другой; и сохранение в базе данных упомянутого окончательного набора. 3 н. и 17 з.п. ф-лы, 14 ил.
Наверх