УСТРОЙСТВО АНАЛИЗА ПЕРЕКРЫТИЙ КАНАЛОВ ПРИ РАЗМЕЩЕНИИ ПАРАЛЛЕЛЬНЫХ ПОДПРОГРАММ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ Российский патент 2012 года по МПК G06F17/00 

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

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

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

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

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

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

Техническая задача решается тем, что в устройство анализа перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах, содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок (БФП), блок постоянной памяти, блок запоминания лучшего варианта (БЗЛВ), коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу с 1-го по n-й элементов ИЛИ, группу с 1-го по m-й элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, второй и третий элементы задержки, первый блок элементов ИЛИ, причем выходы БФП соединены с соответствующими входами блока постоянной памяти и соответствующими входами БЗЛВ, сигнализирующий выход БФП соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом АЛУ, выход которого соединен с информационным входом БЗЛВ, а выход БЗЛВ соединен с первым информационным входом АЛУ, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы первого и второго регистров сдвига с первого по n-й подключены к первым и вторым входам элементов ИЛИ 1-го по n-й соответственно, выход переполнения регистра сдвига соединен с управляющим входом АЛУ и с управляющим входом БФП, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом БФП и с первыми входами первого и второго элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход первого элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом третьего элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход первого элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом второго элемента И, третий вход первого элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом второго элемента И, выход второго элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход которого подключен к первому входу умножителя, выход счетчика расстояний подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу регистра минимальной длины связей и к второму входу вычитателя, выход сумматора подключен к входу данных регистра минимальной длины связей, выход элемента задержки подключен к синхровходу регистра минимальной длины связей, выход второго элемента И и счетный вход счетчика расстояний подключены к входу третьего элемента задержки, выход второго одновибратора подключен к синхровходу счетчика расстояний, выход переполнения которого подключен к счетным входам счетчика топологии, счетчика расстояний и к входу второго одновибратора, выход счетчика топологии подключен к входу счетчика расстояний, вход данных устройства подключен ко входу данных счетчика топологии, синхровход счетчика топологии подключен к входу установки устройства, прямой выход триггера задания топологии подключен к разрешающему входу счетчика топологии, установочный вход триггера задания топологии подключен к входу установки устройства, вход сброса триггера задания топологии подключен к входу установки устройства, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, выход регистра длины связей подключен ко второму входу элемента сравнения и к первому входу вычитателя, первый вход элемента сравнения подключен к выходу АЛУ и входу данных регистра длины связей, выход одновибратора подключен к синхровходу регистра длины связей, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l=1, 2,…, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ и l-м входом блока элементов ИЛИ, l-й выход элемента И группы элементов И с l-го по m-й соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом АЛУ, выход элемента сравнения соединен с входом первого одновибратора, выходы элементов с 1-го по n-й ИЛИ подключены к соответствующим входам элементов И 1-го по m-й, выход вычитателя соединен с выходом длины связей устройства, дополнительно введен блок анализа списка перекрытий, содержащий ОЗУ базы данных, ОЗУ коммуникационных задержек, счетчик адреса строки, счетчик адреса столбца, счетчик элементов строки базы данных, первый элемент сравнения, второй элемент сравнения, третий элемент сравнения, четвертый элемент сравнения, первый и второй регистры идентификатора кратчайшего канала, первый и второй регистры адреса коммуникационной задержки, регистр суммарной задержки, регистр минимальной суммарной задержки, регистр максимального значения, второй сумматор, триггер записи адреса, триггер запрета, четвертый элемент задержки, пятый элемент задержки, шестой элемент задержки, седьмой элемент задержки, восьмой элемент задержки, первый многовходовой элемент И с инверсными входами, второй многовходовой элемент И с инверсными входами, первый трехвходовой элемент И с инверсными входами, многовходовой элемент И, второй трехвходовой элемент И, двухвходовой элемент И, двухвходовой элемент ИЛИ, двухвходовой элемент ИЛИ с инверсными входами, первый инвертор, второй инвертор, причем тактовый вход устройства подключен к счетному входу счетчика элементов строки базы данных, к счетному входу счетчика адреса столбца и к входу синхронизации триггера записи адреса, вход сброса R счетчика элементов строки базы данных подсоединен к третьему входу первого трехвходового элемента И с инверсными входами, к выходу многовходового элемента И, к первому входу двухвходового элемента ИЛИ, к первому входу двухвходового элемента И и ко входу пятого элемента задержки, выход счетчика адреса столбца подсоединен ко второму адресному входу А₂ ОЗУ базы данных, первый вход которого соединен с выходом счетчика адреса строки, счетный вход которого подключен к выходу переполнения счетчика адреса столбца, первый выход счетчика элементов строки базы данных подключен ко входу первого инвертора и к первому входу второго многовходового элемента И с инверсными входами, второй выход счетчика элементов строки базы данных соединен со вторым входом первого многовходового элемента И с инверсными входами и с входом второго инвертора, выход первого инвертора соединен с первым входом первого многовходового элемента И с инверсными входами, входы с третьего по n-й которого соединены с входами с третьего по n-й второго многовходового элемента И с инверсными входами, а также подключены к соответствующим выходам счетчика элементов строки базы данных, выход второго инвертора соединен со вторым входом второго многовходового элемента И с инверсными входами, выход первого многовходового элемента И с инверсными входами подключен ко входу седьмого элемента задержки, второму входу первого трехвходового элемента И с инверсными входами, а также к разрешающему е входу первого элемента сравнения, выход второго многовходового элемента И с инверсными входами соединен со входом восьмого элемента задержки, с первым входом первого трехвходового элемента И с инверсными входами, а также с разрешающим е входом второго элемента сравнения, первый вход которого подключен к выходу второго регистра идентификатора кратчайшего канала, разрешающий w вход которого подключен к выходу восьмого элемента задержки, вход записи второго регистра идентификатора кратчайшего канала подключен к выходу ОЗУ базы данных, ко входу многовходового элемента И, ко входу записи первого регистра идентификатора кратчайшего канала, ко второму входу первого элемента сравнения, ко второму входу второго элемента сравнения, а также ко входу записи первого и второго регистра адреса коммуникационной задержки, выход седьмого элемента задержки подсоединен ко входу w разрешения записи первого регистра идентификатора кратчайшего канала, выход которого соединен с первым входом первого элемента сравнения, выход которого подключен к первому входу двухвходового элемента ИЛИ с инверсными входами, второй вход которого соединен с выходом второго элемента сравнения, выход двухвходового элемента ИЛИ с инверсными входами подсоединен ко второму входу второго трехвходового элемента И и ко входу четвертого элемента задержки, первый вход второго трехвходового элемента И подсоединен ко второму входу двухвходового элемента ИЛИ и к прямому выходу триггера запрета, вход записи которого подключен к выходу двухвходового элемента ИЛИ, выход второго трехвходового элемента И соединен с входом w разрешения записи регистра максимального значения, вход записи которого подключен к первому входу четвертого элемента сравнения, к выходу регистра минимальной суммарной задержки и ко второму входу третьего элемента сравнения, первый вход которого соединен с входом записи регистра минимальной суммарной задержки, с выходом регистра суммарной задержки и со вторым входом второго сумматора, первый вход которого подключен к выходу ОЗУ коммуникационных задержек, первый адресный A₁ вход которого соединен с выходом первого регистра адреса коммуникационной задержки, второй адресный А₂ вход ОЗУ коммуникационных задержек соединен с выходом второго регистра адреса коммуникационной задержки, вход разрешения выдачи ое ОЗУ коммуникационных задержек подключен к выходу шестого элемента задержки, вход которого подключен ко входу w разрешения записи второго регистра адреса коммуникационной задержки, к инверсному выходу триггера записи адреса и ко входу записи триггера записи адреса, разрешающий вход которого соединен с выходом первого трехвходового элемента И с инверсными входами, прямой выход триггера записи адреса подключен к входу w разрешения записи первого регистра адреса коммуникационной задержки, выход второго сумматора подключен к входу записи регистра суммарной задержки, вход сброса R которого подсоединен к выходу пятого элемента задержки, выход третьего элемента сравнения подключен ко второму входу двухвходового элемента И, выход которого соединен с входом w разрешения записи регистра минимальной суммарной задержки, вход сброса R которого подключен к выходу четвертого элемента задержки, третий вход второго трехвходового элемента И подсоединен к выходу четвертого элемента сравнения, второй вход которого соединен с выходом регистра максимального значения и с выходом показателя.

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

Сущность изобретения поясняется чертежами, где на фиг.1 изображена функциональная схема устройства анализа перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах; фиг.2 поясняет сущность использования электронной модели графа; фиг.3 иллюстрирует принцип работы блока 58 анализа списка перекрытий; фиг.4. поясняет принцип работы предлагаемого устройства.

Общие особенности изобретения состоят в следующем.

Предлагаемое устройство аналогично прототипу используется при моделировании комбинаторных задач проектирования РЭА. Устройство позволяет размещать невзвешенные графы в линейную топологическую модель (размещение в линейку). Дополнительно устройство может применяться для анализа перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах.

Общие особенности изобретения состоят в следующем.

Предлагаемое устройство аналогично прототипу используется при моделировании комбинаторных задач проектирования РЭА. Устройство позволяет выполнять анализ перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах. Подмножество взаимодействующих подпрограмм описывается графом воздействия задач G=<X,E>, где - множество вершин графа G, вершины x_i∈X которого соответствуют задачам, а взвешенные дуги e_ij∈Е описывают связи между задачами и задают объемы данных m_ij (в байтах), передаваемых при обмене между задачами.

Граф G представляется матрицей обмена информацией (МОИ): , где m_ij - вес дуги e_ij.

Мультиконтроллер представляется топологической моделью в виде графа H=<P,V>, где - множество идентификаторов процессорных модулей, организованных в матрицу |P|_n×n, где мощность |P|=N=n² - число процессоров; V - множество межпроцессорных связей, задаваемых матрицей смежности размером n²×n².

Размещение пакета программ (комплекса задач), описываемых графом G, может быть аналитически описано отображением

где

Здесь s - это номер очередной перестановки, соответствующий s-му варианту размещения. Мощность множества ψ={β_S} всевозможных отображений равна числу всевозможных перестановок задач {x_qk} в матрице X:|ψ|=N!. Введем матрицу МОИ , описывающую матрицу G, где N=n²=|X|, и матрицу минимальных расстояний (ММР) , N=n²=|Н|.

ММР строится по матрице смежности графа Н. Если непосредственной связи между модулями в базовом блоке нет, то элемент ММР: d_ij - минимальное межмодульное топологическое расстояние, которое вычисляется как кратчайший путь от вершины p_i до вершины p_j в графе Н, измеренный числом последовательно соединенных каналов.

Задача размещения параллельных подпрограмм решается посредством целенаправленной перестановки строк и столбцов в матрице обмена информацией. При этом критерием оптимальности искомого варианта размещения является величина максимальной задержки в линиях связи между процессорами мультиконтроллера. Таким образом, задача размещения сформулирована как поиск отображения β^*∈Ψ, такого, что

,

где - коммутационная задержка при передаче данных между модулями p_a,b и p_x,y, соответствующая отображению β_s, которая пропорциональна произведению d_ij·m_ij, где i=(а-1)·n+b, j=(x-1)·n+y.

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

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

На фиг.4а изображена матричная система из 9 процессоров. Рассмотрим кратчайшие маршруты от процессора 1 до всех остальных процессоров системы. В соответствии с описанным выше форматом фрагмент базы данных избыточных кратчайших путей для данной системы выглядит следующим образом:

ID кратчайше-
го канала Избыточные пути Списки перекрытий 1-2 1-2 1-2 1-4 1-4 1-4 1-3 1-2-3 1-2, 2-3, 1-3 1-5 1-2-5 1-2, 2-5, 1-5 1-5 1-4-5 1-4, 4-5, 1-5 1-7 1-4-7 1-4, 4-7, 1-7 1-6 1-2-3-6 1-2, 2-3, 3-6, 1-3, 2-6, 1-6 1-6 1-2-5-6 1-2, 2-5, 5-6, 1-5, 2-6, 1-6 1-6 1-4-5-6 1-4, 4-5, 5-6, 1-5, 4-6, 1-6 1-8 1-2-5-8 1-2, 2-5, 5-8, 1-5, 2-8, 1-8 1-8 1-4-5-8 1-4, 4-5, 5-8, 1-5, 4-8, 1-8 1-8 1-4-7-8 1-4, 4-7, 7-8, 1-7, 4-8, 1-8 1-9 1-2-3-6-9 1-2, 2-3, 3-6, 6-9, 1-3, 2-6, 3-9, 1-6, 2-9, 1-9 1-9 1-2-5-6-9 1-2, 2-5, 5-6, 6-9, 1-5, 2-6, 5-9, 1-6, 2-9, 1-9 1-9 1-4-5-6-9 1-4, 4-5, 5-6, 6-9, 1-5, 4-6, 5-9, 1-6, 4-9, 1-9 1-9 1-2-5-8-9 1-2, 2-5, 5-8, 8-9, 1-5, 2-8, 5-9, 1-8, 2-9, 1-9 1-9 1-4-5-8-9 1-4, 4-5, 5-8, 8-9, 1-5, 4-8, 5-9, 1-8, 4-9, 1-9 1-9 1-4-7-8-9 1-4, 4-7, 7-8, 8-9, 1-7, 4-8, 7-9, 1-8, 4-9, 1-9

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

Для этого вначале расставим веса дуг графа исходного алгоритма, которые связывают подпрограммы, расположенные в соседних процессорах (фиг.4в). Таким образом, на канал 1-2 накладывается 20 байт, на канал 2-3 - 15 байт, на канал 2-5 - 20 байт, на канал 1-4 - 30 байт, на канал 4-5 - 30 байт, на канал 5-6 - 20 байт, на канал 3-6 - 20 байт, на канал 4-7 - 20 байт, на канал 5-8 - 20 байт, на канал 7-8 - 30 байт, на канал 8-9 - 15 байт и на канал 6-9 - 15 байт.

Далее проложим дуги, для которых имеется только 1 кратчайший путь: x₁-x₇ и x₂-х₈ (фиг.4г). При прокладке дуги x₁-x₇ по пути 1-4-7 на канале 1-4 становится 30+40=70 байт передаваемых данных, на канале 4-7, соответственно, 20+40=60 байт. Аналогично при прокладке дуги x₂-x₈ по пути 2-5-8 на каналах 2-5 и 5-8 становится 20+30=50 байт.

Дуга x₁-x₅ имеет 2 варианта кратчайшего маршрута: 1-2-5 и 1-4-5. Сумма уже наложенных объемов данных на каналы единичной длины, составляющие путь 1-2-5, равна 70 байт. На пути 1-4-5 данная сумма равна 100 байт. Таким образом, путь 1-2-5 является менее загруженным, поэтому проложим дугу x₁-x₅ по пути 1-2-5 (фиг.4д). Соответственно, на канал 1-2 накладывается 20+40=60 байт, на канал 2-5 накладывается 50+40=90 байт.

Аналогично выберем путь для прокладки дуги x₄-x₈. Сумма объемов данных на пути 4-5-8 равна 80 байт, на пути 4-7-8 - 90 байт. Поэтому дуга прокладывается по пути 4-5-8 как наименее загруженному маршруту. Тогда на канале 4-5 становится 30+30=60 байт, на канале 5-8, соответственно, 50+30=80 байт.

Для дуги x₁-x₈ существует 3 варианта кратчайшего пути: 1-2-5-8, 1-4-5-8 и 1-4-7-8. Рассчитаем суммарные объемы передаваемых данных на этих маршрутах:

1-2-5-8: 60+90+80=230 байт

1-4-5-8: 70+60+80=210 байт

1-4-7-8: 70+60+30=160 байт

Наименее загруженным является путь 1-4-7-8, поэтому проложим дугу x₁-x₈ по этому пути (фиг.4е). Тогда на канале 1-4 становится 100 байт, на канале 4-7 - 90 байт, на канале 7-8 - 60 байт.

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

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

где S - номер очередной перестановки задач в МОИ в процессе поиска;

φ={β_S} - множество всевозможных отображений вершин графа задач на множество идентификаторов процессоров;

β_S - отображение, соответствующее S-й перестановке задач в МОИ;

k - номер кратчайшего пути (канала) между процессорами P_ab и P_xy;

t - номер избыточного пути длиной, равной кратчайшему каналу между процессорами P_ab и P_xy;

Z_t - номер кратчайшего пути в любой паре процессоров длиной d^(Zt)≤d^(k), меньшей или равной k-му кратчайшему пути между процессорами P_ab и P_xy, перекрывающегося с k-м каналом;

n_kt - число кратчайших путей с длинами d^(Zt)≤d^(k), в том числе и основной k-й путь, перекрывающихся с k_t-м избыточным путем длины d^(k);

T_βs ^(Zt)(P_ab,P_xy)=d_ij ^(Zt)·m_ij·c≠o при m_ij≠0 - задержка при передаче данных в паре процессоров по Z_t-му кратчайшему пути в β_S-м варианте отображения после S-й перестановки задач в МОИ, в том числе и задержка в k-м кратчайшем пути по матрице ММР при Z_t=k:T_βS ^(k)(P_ab,P_xy)=d_ij ^(k)·m_ij·c;

- суммарная задержка на t-ом избыточном пути, равном по длине k-ому кратчайшему каналу d^(t)=d^(k), с учетом перекрытия t-го пути другими Z_t-ми путями длины d^(Zt)≤d^(k). Если перекрытий нет, то суммарная задержка на любом t-ом избыточном пути k-го канала равна задержке на k-ом кратчайшем пути: T_βS ^(k)(P_ab,P_xy)=d_ij ^(k)·m_ij·c.

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

1. По матрицам МОИ и ММР вычисляются задержки на всех k-x кратчайших неизбыточных каналах без учета перекрытий:

{T_βS ^(k)(P_ab,P_xy)}={m_ij·d_ij ^(k)}, , где при c=const величина с опускается.

2. Используется база данных избыточных путей для всех k-x кратчайших каналов, предварительно создаваемая по матрице смежности физической топологии мультиконтроллера. Для каждого k_t-го избыточного пути вычисляется суммарная задержка:

где (m_ijd_ij}_Zt - задержка, вносимая одним Z_t-каналом, перекрывающимся с данным избыточным k_t-м каналом, выбираемая из множества рассчитанных на первом шаге задержек. Количество слагаемых n_kt определяется длиной списка перекрытий k_t-го избыточного пути.

3. По каждому k-му каналу, т.е. одному элементу ММР вычисляется

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

Найденный в данном шаге поиска максимум сравнивается с предыдущим максимумом, найденным в предыдущем шаге поиска, и принимается решение об успешности или неудаче на S-м шаге перестановок.

Устройство анализа перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах (фиг.1) содержит первый регистр 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 анализа списка перекрытий, содержащий ОЗУ 59 базы данных, ОЗУ 60 коммуникационных задержек, счетчик 61 адреса строки, счетчик 89 адреса столбца, счетчик 62 элементов строки базы данных, первый 63 элемент сравнения, второй 64 элемент сравнения, третий 65 элемент сравнения, четвертый 66 элемент сравнения, первый 67 и второй 68 регистры идентификатора кратчайшего канала, первый 69 и второй 70 регистры адреса коммуникационной задержки, регистр 71 суммарной задержки, регистр 72 минимальной суммарной задержки, регистр 73 максимального значения, второй 74 сумматор, триггер 75 записи адреса, триггер 76 запрета, четвертый 76 элемент задержки, пятый 77 элемент задержки, шестой 78 элемент задержки, седьмой 79 элемент задержки, восьмой 80 элемент задержки, первый 81 многовходовой элемент И с инверсными входами, второй 82 многовходовой элемент И с инверсными входами, первый 83 трехвходовой элемент И с инверсными входами, многовходовой 84 элемент И, второй 85 трехвходовой элемент И, двухвходовой 86 элемент И, двухвходовой 87 элемент ИЛИ, двухвходовой 88 элемент ИЛИ с инверсными входами, первый 90 инвертор, второй 91 инвертор, причем тактовый 57 вход устройства подключен к счетному 62 входу счетчика элементов строки базы данных, к счетному входу счетчика 89 адреса столбца и к входу синхронизации триггера 75 записи адреса, вход сброса R счетчика 62 элементов строки базы данных подсоединен к третьему входу первого 83 трехвходового элемента И с инверсными входами, к выходу многовходового 84 элемента И, к первому входу двухвходового 87 элемента ИЛИ, к первому входу двухвходового 86 элемента И и ко входу пятого 77 элемента задержки, выход счетчика 89 адреса столбца подсоединен ко второму адресному входу А₂ ОЗУ 59 базы данных, первый вход которого соединен с выходом счетчика 61 адреса строки, счетный вход которого подключен к выходу переполнения счетчика 89 адреса столбца, первый выход счетчика 62 элементов строки базы данных подключен ко входу первого 90 инвертора и к первому входу второго 82 многовходового элемента И с инверсными входами, второй выход счетчика 62 элементов строки базы данных соединен со вторым входом первого 81 многовходового элемента И с инверсными входами и с входом второго 91 инвертора, выход первого 90 инвертора соединен с первым входом первого 81 многовходового элемента И с инверсными входами, входы с третьего по n-й которого соединены с входами с третьего по n-й второго 82 многовходового элемента И с инверсными входами, а также подключены к соответствующим выходам счетчика 62 элементов строки базы данных, выход второго 91 инвертора соединен со вторым входом второго 82 многовходового элемента И с инверсными входами, выход первого 81 многовходового элемента И с инверсными входами подключен ко входу седьмого 79 элемента задержки, второму входу первого 83 трехвходового элемента И с инверсными входами, а также к разрешающему е входу первого 63 элемента сравнения, выход второго 82 многовходового элемента И с инверсными входами соединен со входом восьмого 80 элемента задержки, с первым входом первого 83 трехвходового элемента И с инверсными входами, а также с разрешающим е входом второго 64 элемента сравнения, первый вход которого подключен к выходу второго 68 регистра идентификатора кратчайшего канала, разрешающий w вход которого подключен к выходу восьмого 80 элемента задержки, вход записи второго 68 регистра идентификатора кратчайшего канала подключен к выходу ОЗУ 59 базы данных, ко входу многовходового 84 элемента И, ко входу записи первого 67 регистра идентификатора кратчайшего канала, ко второму входу первого 63 элемента сравнения, ко второму входу второго 64 элемента сравнения, а также ко входу записи первого 69 и второго 70 регистра адреса коммуникационной задержки, выход седьмого 79 элемента задержки подсоединен ко входу w разрешения записи первого 67 регистра идентификатора кратчайшего канала, выход которого соединен с первым входом первого 63 элемента сравнения, выход которого подключен к первому входу двухвходового 88 элемента ИЛИ с инверсными входами, второй вход которого соединен с выходом второго 64 элемента сравнения, выход двухвходового 88 элемента ИЛИ с инверсными входами подсоединен ко второму входу второго 85 трехвходового элемента И и ко входу четвертого 76 элемента задержки, первый вход второго 85 трехвходового элемента И подсоединен ко второму входу двухвходового 87 элемента ИЛИ и к прямому выходу триггера 93 запрета, вход записи которого подключен к выходу двухвходового 87 элемента ИЛИ, выход второго 85 трехвходового элемента И соединен с входом w разрешения записи регистра 73 максимального значения, вход записи которого подключен к первому входу четвертого 66 элемента сравнения, к выходу регистра 72 минимальной суммарной задержки и ко второму входу третьего 65 элемента сравнения, первый вход которого соединен с входом записи регистра 72 минимальной суммарной задержки, с выходом регистра 71 суммарной задержки и со вторым входом второго 74 сумматора, первый вход которого подключен к выходу ОЗУ 60 коммуникационных задержек, первый адресный A₁ вход которого соединен с выходом первого 69 регистра адреса коммуникационной задержки, второй адресный А₂ вход ОЗУ 60 коммуникационных задержек соединен с выходом второго 70 регистра адреса коммуникационной задержки, вход разрешения выдачи ое ОЗУ 60 коммуникационных задержек подключен к выходу шестого 78 элемента задержки, вход которого подключен ко входу w разрешения записи второго 70 регистра адреса коммуникационной задержки, к инверсному выходу триггера 75 записи адреса и ко входу записи триггера 75 записи адреса, разрешающий вход которого соединен с выходом первого 83 трехвходового элемента И с инверсными входами, прямой выход триггера 75 записи адреса подключен к входу w разрешения записи первого 69 регистра адреса коммуникационной задержки, выход второго 74 сумматора подключен к входу записи регистра 71 суммарной задержки, вход сброса R которого подсоединен к выходу пятого 77 элемента задержки, выход третьего 65 элемента сравнения подключен ко второму входу двухвходового 86 элемент И, выход которого соединен с входом w разрешения записи регистра 72 минимальной суммарной задержки, вход сброса R которого подключен к выходу четвертого 76 элемента задержки, третий вход второго 85 трехвходового элемента И подсоединен к выходу четвертого 66 элемента сравнения, второй вход которого соединен с выходом регистра 73 максимального значения и с выходом 92 показателя.

Электронная модель 31 графа (фиг.1) содержит 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 веса дуги.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Регистр 25 длины связей предназначен для хранения значения длины связей L для наилучшего варианта размещения, сохраненного в БЗЛВ 5.

Второй элемент 26 сравнения предназначен для сравнения значения длины связей L лучшего на данный момент варианта размещения из регистра 25 с текущей длиной связи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Электронная модель 31.l дуги служит для моделирования l-й дуги орграфа 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 анализа списка перекрытий необходим для анализа перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах. Он состоит из следующих элементов и блоков.

ОЗУ 59 базы данных предназначено для хранения базы данных избыточных кратчайших путей.

ОЗУ 60 коммуникационных задержек предназначено для хранения матрицы коммуникационных задержек без учета перекрытий. Матрица коммуникационных задержек является квадратной матрицей, размерность которой равна N+1, где N - количество процессоров мультиконтроллера. При этом первая строка и первый столбец матрицы содержат порядковые номера процессоров, а коммуникационные задержки начинаются со следующей строки и следующего столбца.

Счетчик 61 адреса строки и счетчик 89 адреса столбца предназначены для последовательного перебора ячеек ОЗУ 4 базы данных.

Счетчик 62 элементов строки базы данных предназначен для хранения номера текущего элемента строки базы данных избыточных кратчайших путей.

Первый 63 элемент сравнения предназначен для сравнения содержимого первого 67 регистра идентификатора кратчайшего канала с кодом, поступающим из ОЗУ 59 базы данных.

Второй 64 элемент сравнения предназначен для сравнения содержимого второго 68 регистра идентификатора кратчайшего канала с кодом, поступающим из ОЗУ 59 базы данных.

Третий 65 элемент сравнения предназначен для сравнения содержимого регистра 71 суммарной задержки с содержимым регистра 27 минимальной суммарной задержки.

Четвертый 66 элемент сравнения предназначен для сравнения содержимого регистра 72 минимальной суммарной задержки с содержимым регистра 73 максимального значения.

Первый 67 и второй 68 регистры идентификатора кратчайшего канала предназначены для хранения идентификатора кратчайшего канала, соответствующего текущей строке базы данных избыточных кратчайших путей.

Первый 69 и второй 70 регистры адреса коммуникационной задержки предназначены для хранения адресов элементов матрицы коммуникационных задержек, хранимой в ОЗУ 60 коммуникационных задержек.

Регистр 71 суммарной задержки предназначен для хранения суммы коммуникационных задержек для одной строки базы данных избыточных кратчайших путей.

Регистр 72 минимальной суммарной задержки предназначен для хранения минимального значения суммарной задержки для одного кратчайшего канала.

Регистр 73 максимального значения предназначен для хранения максимального значения из множества минимальных задержек.

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

Триггер 75 записи адреса задержки предназначен для попеременной записи значений списка перекрытий избыточного кратчайшего пути в первый 69 и второй 70 регистры адреса коммуникационной задержки.

Триггер 93 запрета предназначен для запрета записи нового максимального значения в регистр 73 максимального значения при чтении кода, хранящегося в первой и второй ячейках ОЗУ 59 базы данных.

Четвертый 76 элемент задержки предназначен для задерживания сигнала возврата регистра 72 минимальной суммарной задержки в первоначальное состояние на время, достаточное для записи текущего состояния регистра 72 минимальной суммарной задержки в регистр 73 максимального значения.

Пятый 77 элемент задержки предназначен для задерживания сигнала сброса регистра 71 суммарной задержки на время, достаточное для записи текущего состояния регистра 71 суммарной задержки в регистр 72 минимальной суммарной задержки.

Шестой 78 элемент задержки предназначен для задерживания сигнала с инверсного выхода триггера 75 записи адреса задержки на ое вход разрешения выдачи ОЗУ 60 коммуникационных задержек.

Седьмой 79 элемент задержки предназначен для задерживания сигнала с выхода первого 81 многовходового элемента И с инверсными входами на время, достаточное для срабатывания первого 63 элемента сравнения и появления на его выходе импульса, поступающего на первый вход элемента 88 ИЛИ с инверсными входами.

Восьмой 80 элемент задержки предназначен для задерживания сигнала с выхода второго 82 многовходового элемента И с инверсными входами на время, достаточное для срабатывания второго 64 элемента сравнения и появления на его выходе импульса, поступающего на второй вход элемента 88 ИЛИ с инверсными входами.

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

Второй 82 многовходовой элемент И с инверсными входами предназначен для обнаружения кода двойки на выходе счетчика 62 элементов строки базы данных.

Первый 83 трехвходовой элемент И с инверсными входами предназначен для формирования сигнала разрешения работы триггера 75 записи адреса задержки.

Многовходовой 84 элемент И предназначен для определения окончания текущей строки базы данных избыточных кратчайших путей.

Второй 85 трехвходовой элемент И предназначен для формирования сигнала разрешения записи нового максимального значения в регистр 73 максимального значения.

Двухвходовой 86 элемент И предназначен для формирования сигнала разрешения записи нового значения минимальной суммарной задержки в регистр 72 минимальной суммарной задержки.

Двухвходовой 87 элемент ИЛИ предназначен для формирования сигнала на информационном входе триггера 76 запрета.

Двухвходовой 88 элемент ИЛИ с инверсными входами предназначен для формирования сигнала перехода к новому кратчайшему каналу.

Первый 90 инвертор предназначен для инвертирования сигнала с первого выхода счетчика 62 элементов строки базы данных.

Второй 91 инвертор предназначен для инвертирования сигнала со второго выхода счетчика 62 элементов строки базы данных.

Выход 92 показателя необходим для выдачи на ВУУ показателя коммуникационной задержки.

Рассмотрим работу предлагаемого устройства.

Первоначально в регистрах 29, 30 и 25 содержатся значения «11…1». В регистре 16 и счетчиках 27, 9 содержится нулевой код. Триггеры 19 и 23 находятся в состоянии логического нуля; состояние триггера 24 либо нулевое, что соответствует топологии кольца, либо единичное, что соответствует топологии линейки. Значение с прямого выхода триггера 24 подается на разрешающий вход счетчика 11 и если это значение - единица, то работа счетчика 11 разрешена, а если ноль, то работа запрещена (на выходе счетчика 11 будет константный код). Первоначально в счетчике 11 хранится код общего числа обрабатываемых элементов матрицы расстояний D (его запись осуществляется со входа 51 устройства по импульсу со входа 52 устройства). В счетчиках 12, 13 содержатся нулевые значения. Триггеры 20.l модели 31.l, l=1, 2,…, m, находятся либо в состоянии логической единицы, либо в состоянии логического нуля (что определяется соответственно наличием или отсутствием l-й дуги в графе). В регистрах 21.l содержатся либо значения весов соответствующих дуг, либо нулевые коды (если соответствующие дуги отсутствуют в исходном графе). Если размещается граф с невзвешенными дугами, то регистры 21.l содержат либо коды «00…01» либо нулевые коды. Запись информации о размещаемом графе осуществляется путем подачи комбинаций сигналов на входы 56.1-56.n устройства и весов дуг на входы 54.l устройства. Появление единичных сигналов на входах 56.i-1 и 56.1 означает наличие в графе дуги e_i-1,i (вес этой дуги подается на вход 54 соответствующей модели дуги)…

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

Задача размещения невзвешенных графов с топологической моделью в виде линейки решается в устройстве аналогично прототипу. В данном случае работает только так называемая «верхняя» часть схемы, в которую входит ЭМГ 31, регистры 1 и 2, группа элементов ИЛИ 32.1-32.n, группа элементов И 33.1-31.m, блок элементов ИЛИ 46, регистр 25, элемент 26 сравнения, одновибратор 41, а также БФП 3, блок 4 постоянной памяти, БЗЛВ 5, коммутатор 6 и АЛУ 7.

Регистр 1 и регистр 2 последовательно выбирают пары вершин по мере поступления импульсов с входа 57 устройства. Сигналы выбранной пары вершин проходят через два соответствующих элемента группы элементов ИЛИ 32.1-32.n и далее формируют единичный сигнал на выходе соответствующего элемента И группы 33.1-33.m (допустим элемента 33.l). Единичный сигнал с элемента И 33.l поступает на элемент ИЛИ 40.l (модели 31.l дуги) и, попадая далее на разрешающий вход (ое) регистра 21.l, разрешает тем самым появление данных (веса 1-й дуги) на выходе этого регистра. Поскольку размещаемый граф невзвешен, в регистре 21.l содержится либо код «00…01» либо код «00…00» (отсутствие дуги). Будем считать данный код ненулевым. Код «00…01» с выхода регистра 21.l поступает на блок элементов ИЛИ 46 и далее через него - в АЛУ 7. В это же время блок 3 формирования перестановок определяет для выбираемых вершин позиции, а АЛУ 7 вырабатывает команду определения расстояния между позициями, в которые следует поместить выбранные вершины графа. Это расстояние определяется по формуле d_i,j=|i-j|. Одновременно в АЛУ 7 происходит и накопление суммарной длины связей L. Подсчет суммарной длины связей для текущего варианта размещения завершается, когда на выходе переполнения регистра 2 появляется сигнал переполнения. Одновременно этот же сигнал поступает на БФП 3, подготавливая его к формированию новой перестановки.

Перестановки формируются в пространственно-временной форме, то есть в каждый тактовый момент времени единичный сигнал инициируется только на одном (q-м) выходе БФП 3, а их последовательность задает соответствующую перестановку. Например, перестановка (3 1 2) означает, что первый тактовый импульс появляется на втором выходе БФП, второй - на третьем, третий - на первом. В соответствии с этим из блока 4 постоянной памяти (в блок 4 постоянной памяти заносятся двоичные коды номеров позиций) через коммутатор 6 в АЛУ 7 будут последовательно списываться коды второй позиции, третьей и первой. Это, в свою очередь, означает, что первая вершина помещается во вторую позицию, вторая в третью и третья в первую. Лучший вариант размещения переписывается в блок 5 и соответствующее ему значение длины связей L - в регистр 25. Появление сигнала на сигнализирующем выходе БФП 3 свидетельствует о том, что все перестановки сформированы, а лучший вариант размещения зафиксирован в БЗЛВ 5.

Значение L в регистре 25 формируется следующим образом. С выхода АЛУ 7 значение длины связей очередного варианта размещения поступает на вход данных регистра 25 и первый вход элемента 26 сравнения. Код с выхода регистра 25 поступает на второй вход элемента 26 сравнения. В первом такте работы в регистре 25 содержится код «11…1», поэтому при первом сравнении в элементе 26 сравнения результат будет положительным и, следовательно, на выходе этого элемента будет единичный сигнал. Единица с выхода элемента 26 сравнения поступает на одновибратор 41 и формирует импульс на его выходе. Данный импульс поступает на синхровход регистра 25 и по заднему фронту заносит в него новое значение длины связей. Последнее снова поступает на второй вход элемента 26 сравнения для сравнения с длиной связей L очередного варианта размещения и т.д., пока в регистре 25 не будет зафиксировано значение наилучшего варианта размещения.

Задача размещения взвешенных графов в линейной и кольцевой топологических моделях решается в устройстве аналогично (как и в рассмотренном выше случае работает только «верхняя» часть схемы, только в отличие от невзвешенных графов вес дуги - либо нулевой код (дуга отсутствует), либо произвольный ненулевой код).

Задача оценки степени близости сформированного размещения к оптимальному решается следующим образом (в данном случае работает только «нижняя» часть схемы, включающая дешифраторы 8 и 28, элемент 17 сравнения, счетчики 27, 9, 11, 12 и 13, блок 10 оперативной памяти, регистры 16, 25, 29 и 30, триггеры 19, 23 и 24, умножитель 14, сумматор 15, вычитатель 18, блок элементов ИЛИ 36, элементы И 34, 35 и 37, элементы 43, 44 и 45 задержки и одновибратор 42).

При появлении единичного сигнала на сигнализирующем выходе БФП 3 триггер 19 устанавливается в единицу. Единичный сигнал с прямого выхода триггера 19 поступает на вторые входы элемента И 34 и элемента И 35. Так как триггер 23 режима находится в нулевом состоянии, элемент 35 по-прежнему остается закрытым, а элемент 34 открывается для прохождения тактовых импульсов.

Первый тактовый импульс проходит через элемент И 34, откуда этот импульс поступает на счетный вход счетчика 27 и передним фронтом устанавливает его в значение «00…01». Код с выхода счетчика 27 поступает на вход данных регистра 29 и на вход дешифратора 8, инициируя появление единицы на его первом выходе. Эта единица поступает на второй вход элемента И 39.1 (модели 31.1). Если на первом входе элемента 39.1 присутствует единица (триггер 20.1 находится в единичном состоянии), то на выходе элемента 39.1 появляется единичный сигнал выбора дуги. С выхода элемента И 39.1 этот сигнал проходит через элемент ИЛИ 40.1, поступает на разрешающий вход регистра 21.1 и открывает его выход. В результате вес дуги с регистра 21.1 проходит через блок элементов ИЛИ 36, откуда попадает на первый вход элемента 17 сравнения, на втором входе которого присутствует код из регистра 30 (первоначально «11…1»). Если код с блока элементов ИЛИ 36 (вес выбранной дуги) меньше уже имеющегося в регистре 30, на выходе элемента 17 образуется единичный сигнал. Этот единичный сигнал поступает на первый вход элемента И 37 и обеспечивает прохождение тактового импульса с элемента И 34, задержанного на элементе 44 задержки. Импульс с элемента И 37 поступает на синхровходы регистра 29 и регистра 30 и по переднему фронту записывает в них значение с выхода счетчика 27 (номер текущей дуги) и код веса выбранной дуги с блока 36 (как минимальный на данный момент) соответственно. В случае присутствия на выходе элемента 17 нуля, элемент И 37 заблокирован и поэтому импульс с элемента 44 задержки не поступает на синхровходы регистров 29 и 30.

Очередной тактовый импульс аналогично проходит через элемент И 34, снова попадает на счетный вход счетчика 27 и увеличивает значение этого счетчика до «00…010». С выхода счетчика 27 код снова попадает на дешифратор 8, чем вызывает появление единицы на его втором выходе. Эта единица аналогично поступает в модель 31.2 взвешенной дуги, и со второго выхода веса дуги модели 31 на блок элементов ИЛИ 36 поступает код веса второй дуги. Если такая дуга существует, то соответствующий ей код попадает на первый вход элемента 17 сравнения, на второй вход которого поступает с регистра 30 вес, записанный на предыдущих шагах. Если новый вес меньше предыдущего, то единичный сигнал, свидетельствующий об этом, поступает на первый вход элемента И 37 и пропускает через него импульс с элемента 44 задержки. С выхода элемента И 37 импульс снова попадает на синхровходы регистров 29 и 30 и по переднему входу записывает в регистр 30 новый вес дуги (вес второй дуги), а в регистр 29 значение счетчика 27 как номер дуги с наименьшим на данный момент весом.

Так происходит до тех пор, пока на выходе переполнения счетчика 27 не появится сигнал (импульс) переполнения, сигнализирующий о том, что все дуги просмотрены и наименьший вес содержится в регистре 30, а номер соответствующей дуги - в регистре 29.

При этом счетчик 27 сбрасывается в нулевое состояние, а сигнал переполнения одновременно поступает на вход записи блока 10 оперативной памяти на элемент 43 задержки и первый счетный вход счетчика 9. По заднему фронту сигнала переполнения счетчик 9 увеличивает свое значение до «00…01». В результате в блок 10 оперативной памяти по адресу «00…01» заносится минимальный вес дуги с регистра 30. Сигнал переполнения от счетчика 27 одновременно поступает на разрешающий вход дешифратора 28, обеспечивая выбор его выхода в зависимости от кода, подаваемого с выхода регистра 29. Сигнал с выбранного выхода дешифратора 28 (например, l-го) поступает на вход сброса триггера 20.l модели 31.l, устанавливая его в нулевое состояние (обеспечивается блокировка l-й дуги для следующих циклов работы устройства). К тому времени, когда минимальный вес дуги уже записан в блок 10 оперативной памяти, сигнал переполнения с выхода элемента 43 задержки поступает на входы установки (S) регистров 29 и 30 и устанавливает эти регистры в исходное состояние «11…1». Текущий цикл работы устройства завершается.

Следующий импульс, проходящий через элемент И 34, заставляет устройство снова работать по вышеописанному алгоритму. В регистре 30 сохраняется наименьший вес дуги без учета заблокированных в предыдущих циклах дуг. При выборе дешифратором 8 незаблокированной дуги устройство работает так, как описано выше. Когда дешифратор 8 выбирает уже заблокированную дугу, сигнал с выхода дешифратора 8 не проходит через элемент И 39.1 (на прямом выходе триггера 20.l присутствует ноль). В то же время сигнал с прямого выхода триггера 20.l поступает на разрешающий вход регистра 22.l. В результате нулевой код (записанный в этот регистр с входа 55.l) с выхода регистра 22.l поступает через блок элементов ИЛИ 36 на первый вход элемента 17 сравнения и, будучи заведомо меньше любого другого кода, находящегося в регистре 30, обеспечивает нулевой сигнал на выходе элемента 17 и блокировку элемента 37.

При повторном появлении сигнала переполнения на счетчике 27 происходит увеличение значения счетчика 9 до кода «00…010». Сигнал переполнения поступает на вход записи блока 10 оперативной памяти и записывает туда по адресу «00…010» код веса дуги с выхода регистра 30 из счетчика 9. Таким образом, происходит последовательная запись в блок 10 оперативной памяти весов дуг графа G по возрастанию соответствующих значений. Так происходит до тех пор, пока счетчик 9 не выдаст сигнал переполнения. Этот сигнал поступает на установочный вход триггера 23, устанавливает его в единицу и тем самым разрешает прохождение тактовых импульсов через элемент И 35, запрещая их прохождение через элемент И 34. Сам счетчик 9 реверсивно переводится из суммирующего в вычитающий. Таким образом, начинается этап подсчета минимально возможной длины L*. Этот этап решается так же, как в прототипе, и поэтому здесь не рассматривается.

Работа блока 58 анализа перекрытий происходит следующим образом.

База данных избыточных кратчайших путей хранится в ОЗУ 59 в виде списка записей (строк) следующего формата:

где N_н и N_к - номера начального и конечного процессоров конкретного избыточного пути соответственно, представляющие собой идентификатор кратчайшего канала, которому соответствует избыточный путь; N_н1N_к1, N_н2N_к2,…, N_нnN_кn - список перекрытий избыточного пути, т.е. список идентификаторов кратчайших каналов, которые можно выделить в данном избыточном пути. Каждый номер процессора занимает отдельную ячейку памяти. Все записи (строки) базы данных следуют в памяти друг за другом разделяемые специальным кодом 11…1, то есть после каждого числа N_кn следует код 11…1, поэтому разрядность ячеек ОЗУ 59 должна быть достаточной для того, чтобы код 11…1 не входил в диапазон двоичных номеров процессоров. Для удобства и ускорения обработки база данных предварительно отсортирована по ID_кан т.е. сначала идут все избыточные пути канала ID_кан1 затем все избыточные пути канала ID_кан2 и т.д.

Последовательное чтение данных из ОЗУ 59 организуется двумя счетчиками адреса строки 61 и адреса столбца 89, сигналы которых подаются на соответствующие адресные входы A₁ и А₂. Еще один счетчик 62 считает номера элементов в пределах одной записи (строки) базы данных и сбрасывается при обнаружении кода 11…1 в ОЗУ 59, означающего конец записи (строки) базы данных. Код 11…1 обнаруживается многовходовым элементом И на выходе ОЗУ 59.

Так как в любой строке базы данных идентификатором кратчайшего канала являются первое и второе число, запись этих чисел в соответствующие регистры 67 и 68 должна происходить, когда на выходе счетчика номеров элементов строки базы данных присутствует код единицы (00…01) или код двойки (00…10) соответственно. Определение данных кодов выполняется посредством многовходовых элементов И с инверсными входами 81 и 82 соответственно, что обращает нули на входах в единицы. Чтобы обратить единицу в ноль в разряде Q₀ или Q₁, соответствующие сигналы подаются на вход элемента И через инверторы 90 и 91 соответственно. Таким образом, данные комбинационные схемы будут давать единичный сигнал только при наличии кода 00…01 и кода 00…10 соответственно на выходе счетчика номеров элементов. Данные сигналы подаются на входы разрешения записи W соответствующих регистров 67 и 68, разрешая запись значения с выхода ОЗУ 59 в нужный регистр.

Так как списку перекрытий соответствует отсутствие кода 11…1 на выходе ОЗУ, а также любой код на выходе счетчика номеров элементов, кроме кода единицы и двойки (код нуля не участвует в счете), запись в регистры 69 и 70 адреса ОЗУ 60 следует выполнять при нулевом сигнале на выходах:

1) элемента И 84, обнаруживающего код 11…1 на выходе ОЗУ 59.

2) элемента И 81, обнаруживающего код 00…01 на выходе счетчика номеров элементов.

3) элемента И 82, обнаруживающего код 00…10 на выходе счетчика номеров элементов.

Описанные сигналы подаются на инверсные входы трехвходового элемента И 83, который, в свою очередь, разрешает работу D-триггера 75 попеременной записи в регистры 69 и 70, подачей единичного импульса на вход разрешения е триггера 75.

Так как пары чисел в списке перекрытий в соответствии с методикой вычисления величины минимаксиминного критерия используются в качестве адресов элементов матрицы коммуникационных задержек, вычисленных без учета перекрытий, то есть посредством поэлементного произведения МОИ и ММР, каждая пара чисел подается на адресные входы ОЗУ 60, содержащей матрицу коммуникационных задержек. Так как из ОЗУ 59 числа можно читать только по одному, триггер попеременной записи обеспечивает попеременную запись сначала в регистр 69, затем в регистр 70. Попеременная запись реализуется посредством инвертирования состояния триггера в каждом такте приема данных, для чего информационный вход триггера 75 соединен с его инверсным выходом. Инверсный выход триггера также соединен с входом разрешения записи W регистра 70, а вход W регистра 69 соединен с прямым выходом триггера 75.

Таким образом, запись в регистр 69 осуществляется при единичном состоянии триггера 75, в регистр 70 - при нулевом. Начальное состояние триггера определяется по условию, что по приходу разрешающего сигнала на вход е триггер 75 должен быть установлен в единичное состояние (либо длительность фронта тактового сигнала должна позволить триггеру успеть установиться в единицу, либо начальное состояние триггера должно быть единичным). Так как факт записи в регистр 70, исходя из описанного выше, можно считать окончанием формирования адреса, инверсный выход триггера 75 соединяется также с входом ое разрешения выдачи ОЗУ 60. Чтобы значение, поступающее из ОЗУ 59, успело записаться в регистр 70, сигнал на вход разрешения выдачи ое ОЗУ 60 подается через элемент задержки 78.

Вычисление суммарной задержки выполняет сумматор 74. На первый вход сумматора подается слагаемое, получаемое из ОЗУ 60, а на второй вход - содержимое регистра промежуточной суммы 71. Первоначально значение в этом регистре равно нулю, а новые значения в процессе чтения списка перекрытий дает сумматор 74.

Вычисление суммарной задержки продолжается до тех пор, пока не закончится строка базы данных, о чем сообщает код 11…1 на выходе ОЗУ 59. Следовательно, при наличии единичного сигнала с выхода элемента И 84, обнаруживающего код 11…1, регистр 71 сбрасывается. Однако перед сбросом регистр должен передать вычисленную сумматором сумму для сравнения компаратором 65 со значением регистра 72, который хранит минимальное значение, и, если полученная сумма меньше значения хранящегося в регистре 72, она записывается в данный регистр. Поэтому сигнал сброса регистра 71 подается через элемент задержки 77. Регистр 72 первоначально хранит код 11…1, то есть максимально возможное значение, от которого начинается поиск минимума.

Изменение значения хотя бы в одном из регистров 67 и 68, хранящих идентификатор кратчайшего канала, которому соответствует рассматриваемый избыточный путь, является признаком перехода к следующему кратчайшему каналу, что означает окончание определения минимальной суммарной задержки предыдущего кратчайшего канала. Изменение значения регистров определяется соответствующими компараторами 63 и 64, которые дают нулевой сигнал на выходе, если поступающее из ОЗУ 59 значение не равно текущему значению соответствующего регистра. Чтобы каждый компаратор работал в нужный момент, используются разрешающие входы е, на которые подаются те же сигналы, что и на входы записи регистров 67 и 68. Чтобы соответствующий компаратор успел сработать, импульс подается через элементы задержки 79 и 80.

Определяет наличие нулевого сигнала на выходе любого из компараторов двухвходовой элемент ИЛИ с инверсными входами 88. Элемент формирует сигнал, по которому значение регистра минимальной суммы 72, передающего свое значение регистру 73, записывается в регистр 73, если оно больше текущего значения регистра 73. Для проверки описанного условия используется компаратор 66, выходной сигнал которого объединяется с сигналом изменения содержимого регистров 67 и 68, описанным выше, посредством элемента И 85. Первоначально регистр 73 хранит код 00…0, то есть минимально возможное значение, от которого начинается поиск максимума. Так как регистр 72 по сигналу изменения содержимого регистров 67 и 68 должен также вернуться в первоначальное состояние для поиска следующей минимальной суммы, используется элемент задержки 76 сигнала сброса в первоначальное состояние регистра 72, чтобы минимальная сумма успела записаться в регистр 73, если это необходимо.

Так как первое изменение регистров 67 и 68 произойдет в самом начале чтения базы данных, когда регистр 72 будет хранить код 11…1 ввиду отсутствия вычисленной минимальной суммы, то для предотвращения записи этого кода в регистр 73 в начале чтения (данное действие приведет к тому, что код 11…1 так и останется в регистре 73 без изменений) вводится дополнительный D-триггер 93. Сигнал прямого выхода данного триггера объединяется через 3-входовой элемент И 85 с выходным сигналом компаратора 66 сравнения содержимого регистров 72 и 73 и сигналом изменения содержимого регистров 67 и 68. Триггер обеспечивает разрешение записи в регистр 73 только после первого обнаружения кода 11…1 в ОЗУ 59. Реализуется это следующим образом:

1) Чтобы перевести D-триггер 93 в режим хранения текущего состояния, сигнал с прямого выхода подается на информационный вход через 2-входовой элемент ИЛИ 87, на другой вход которого подается сигнал с выхода элемента И 84 обнаружения кода 11…1 на выходе ОЗУ 59.

2) Начальное состояние триггера 93 равно 0, что дает 0 на выходе 3-входового элемента И 84 и запрещает запись в регистр 73. Пока на выходе элемента И 85 обнаружения кода 11…1 на выходе ОЗУ 59 присутствует 0, на выходе элемента ИЛИ также 0, поэтому триггер хранит нулевое состояние.

3) Когда встречается код 11…1 на выходе ОЗУ 59 и приходит единичный сигнал на соответствующий вход элемента ИЛИ 87, на его выходе также появляется единичный сигнал, переводящий триггер в единичное состояние.

4) Когда сигнал на выходе элемента И 84 обнаружения кода 11…1 на выходе ОЗУ 59 возвращается в нулевое состояние, элемент ИЛИ 87, выход которого соединен с информационным входом триггера 93, продолжает давать единичный сигнал, так как триггер 93 находится в единичном состоянии, подаваемом на один из входов элемента ИЛИ 87.

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

Конечное значение регистра 73 является искомым значением локального максимума, подаваемым на выход 92 устройства.

Таким образом, предлагаемое устройство аналогично прототипу позволяет формировать оптимальное размещение невзвешенных графов в линейной топологической модели (что необходимо при проектировании РЭА). Кроме того, в устройстве возможно размещение взвешенных графов (такая задача возникает при поиске оптимального отображения сетей алгоритмов в однородных системах в рамках синтеза АСУ и СЭВТ), причем допускается выбор двух моделей области размещения - линейной или кольцевой. Найденное субоптимальное размещение сопоставляется с предельным вариантом путем подсчета и сравнения значений длин связей L и L*. Сказанное обеспечивает существенное расширение области применения устройства. Дополнительно предлагаемое устройство позволяет выполнять анализ перекрытия каналов при размещении параллельных подпрограмм в многопроцессорных системах.

Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании вычислительных систем (ВС), например для размещения процессов. Техническим результатом является расширение области применения устройства за счет введения средств анализа перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах по критерию минимизации интенсивности взаимодействия процессов и данных. Устройство содержит два регистра сдвига, блок формирования перестановок (БФП), блок постоянной памяти, блок запоминания лучшего варианта (БЗЛВ), коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, два счетчика расстояний, умножитель, сумматор, регистр минимальной длины связей, два элемента сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу из n элементов ИЛИ, группу из m элементов И, два одновибратора, три элемента задержки, первый блок элементов ИЛИ, блок анализа списка перекрытий. 1 з.п. ф-лы, 4 ил.

1. Устройство анализа перекрытий каналов при размещении параллельных подпрограмм в многопроцессорных системах, содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок (БФП), блок постоянной памяти, блок запоминания лучшего варианта (БЗЛВ), коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу с l-го по n-й элементов ИЛИ, группу с l-го по m-й элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, второй и третий элементы задержки, первый блок элементов ИЛИ, причем выходы БФП соединены с соответствующими входами блока постоянной памяти и соответствующими входами БЗЛВ, сигнализирующий выход БФП соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом АЛУ, выход которого соединен с информационным входом БЗЛВ, а выход БЗЛВ соединен с первым информационным входом АЛУ, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы первого и второго регистров сдвига с первого по n-й подключены к первым и вторым входам элементов ИЛИ l-го по n-й соответственно, выход переполнения регистра сдвига соединен с управляющим входом АЛУ и с управляющим входом БФП, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом БФП и с первыми входами первого и второго элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход первого элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом третьего элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход первого элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом второго элемента И, третий вход первого элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом второго элемента И, выход второго элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход которого подключен к первому входу умножителя, выход счетчика расстояний подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу регистра минимальной длины связей и к второму входу вычитателя, выход сумматора подключен к входу данных регистра минимальной длины связей, выход элемента задержки подключен к синхровходу регистра минимальной длины связей, выход второго элемента И и счетный вход счетчика расстояний подключены к входу третьего элемента задержки, выход второго одновибратора подключен к синхровходу счетчика расстояний, выход переполнения которого подключен к счетным входам счетчика топологии, счетчика расстояний и к входу второго одновибратора, выход счетчика топологии подключен к входу счетчика расстояний, вход данных устройства подключен ко входу данных счетчика топологии, синхровход счетчика топологии подключен к входу установки устройства, прямой выход триггера задания топологии подключен к разрешающему входу счетчика топологии, установочный вход триггера задания топологии подключен к входу установки устройства, вход сброса триггера задания топологии подключен к входу установки устройства, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, выход регистра длины связей подключен ко второму входу элемента сравнения и к первому входу вычитателя, первый вход элемента сравнения подключен к выходу АЛУ и входу данных регистра длины связей, выход одновибратора подключен к синхровходу регистра длины связей, вход сброса триггера, начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l=1, 2,…, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ и l-м входом блока элементов ИЛИ, l-й выход элемента И группы элементов И с l-го по m-й соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом АЛУ, выход элемента сравнения соединен с входом первого одновибратора, выходы элементов с l-го по n-й ИЛИ подключены к соответствующим входам элементов И l-го по m-й, выход вычитателя соединен с выходом длины связей устройства, отличающееся тем, что в него дополнительно введен блок анализа списка перекрытий, содержащий ОЗУ базы данных, ОЗУ коммуникационных задержек, счетчик адреса строки, счетчик адреса столбца, счетчик элементов строки базы данных, первый элемент сравнения, второй элемент сравнения, третий элемент сравнения, четвертый элемент сравнения, первый и второй регистры идентификатора кратчайшего канала, первый и второй регистры адреса коммуникационной задержки, регистр суммарной задержки, регистр минимальной суммарной задержки, регистр максимального значения, второй сумматор, триггер записи адреса, триггер запрета, четвертый элемент задержки, пятый элемент задержки, шестой элемент задержки, седьмой элемент задержки, восьмой элемент задержки, первый многовходовой элемент И с инверсными входами, второй многовходовой элемент И с инверсными входами, первый трехвходовой элемент И с инверсными входами, многовходовой элемент И, второй трехвходовой элемент И, двухвходовой элемент И, двухвходовой элемент ИЛИ, двухвходовой элемент ИЛИ с инверсными входами, первый инвертор, второй инвертор, причем тактовый вход устройства подключен к счетному входу счетчика элементов строки базы данных, к счетному входу счетчика адреса столбца и к входу синхронизации триггера записи адреса, вход сброса R счетчика элементов строки базы данных подсоединен к третьему входу первого трехвходового элемента И с инверсными входами, к выходу многовходового элемента И, к первому входу двухвходового элемента ИЛИ, к первому входу двухвходового элемента И и ко входу пятого элемента задержки, выход счетчика адреса столбца подсоединен ко второму адресному входу А₂ ОЗУ базы данных, первый вход которого соединен с выходом счетчика адреса строки, счетный вход которого подключен к выходу переполнения счетчика адреса столбца, первый выход счетчика элементов строки базы данных подключен ко входу первого инвертора и к первому входу второго многовходового элемента И с инверсными входами, второй выход счетчика элементов строки базы данных соединен со вторым входом первого многовходового элемента И с инверсными входами и с входом второго инвертора, выход первого инвертора соединен с первым входом первого многовходового элемента И с инверсными входами, входы с третьего по n-й которого соединены с входами с третьего по n-й второго многовходового элемента И с инверсными входами, а также подключены к соответствующим выходам счетчика элементов строки базы данных, выход второго инвертора соединен со вторым входом второго многовходового элемента И с инверсными входами, выход первого многовходового элемента И с инверсными входами подключен ко входу седьмого элемента задержки, второму входу первого трехвходового элемента И с инверсными входами, а также к разрешающему е входу первого элемента сравнения, выход второго многовходового элемента И с инверсными входами соединен со входом восьмого элемента задержки, с первым входом первого трехвходового элемента И с инверсными входами, а также с разрешающим е входом второго элемента сравнения, первый вход которого подключен к выходу второго регистра идентификатора кратчайшего канала, разрешающий w вход которого подключен к выходу восьмого элемента задержки, вход записи второго регистра идентификатора кратчайшего канала подключен к выходу ОЗУ базы данных, ко входу многовходового элемента И, ко входу записи первого регистра идентификатора кратчайшего канала, ко второму входу первого элемента сравнения, ко второму входу второго элемента сравнения, а также ко входу записи первого и второго регистров адреса коммуникационной задержки, выход седьмого элемента задержки подсоединен ко входу w разрешения записи первого регистра идентификатора кратчайшего канала, выход которого соединен с первым входом первого элемента сравнения, выход которого подключен к первому входу двухвходового элемента ИЛИ с инверсными входами, второй вход которого соединен с выходом второго элемента сравнения, выход двухвходового элемента ИЛИ с инверсными входами подсоединен ко второму входу второго трехвходового элемента И и ко входу четвертого элемента задержки, первый вход второго трехвходового элемента И подсоединен ко второму входу двухвходового элемента ИЛИ и к прямому выходу триггера запрета, вход записи которого подключен к выходу двухвходового элемента ИЛИ, выход второго трехвходового элемента И соединен с входом w разрешения записи регистра максимального значения, вход записи которого подключен к первому входу четвертого элемента сравнения, к выходу регистра минимальной суммарной задержки и ко второму входу третьего элемента сравнения, первый вход которого соединен с входом записи регистра минимальной суммарной задержки, с выходом регистра суммарной задержки и со вторым входом второго сумматора, первый вход которого подключен к выходу ОЗУ коммуникационных задержек, первый адресный A₁ вход которого соединен с выходом первого регистра адреса коммуникационной задержки, второй адресный А₂ вход ОЗУ коммуникационных задержек соединен с выходом второго регистра адреса коммуникационной задержки, вход разрешения выдачи ое ОЗУ коммуникационных задержек подключен к выходу шестого элемента задержки, вход которого подключен ко входу w разрешения записи второго регистра адреса коммуникационной задержки, к инверсному выходу триггера записи адреса и ко входу записи триггера записи адреса, разрешающий вход которого соединен с выходом первого трехвходового элемента И с инверсными входами, прямой выход триггера записи адреса подключен к входу w разрешения записи первого регистра адреса коммуникационной задержки, выход второго сумматора подключен к входу записи регистра суммарной задержки, вход сброса R которого подсоединен к выходу пятого элемента задержки, выход третьего элемента сравнения подключен ко второму входу двухвходового элемента И, выход которого соединен с входом w разрешения записи регистра минимальной суммарной задержки, вход сброса R которого подключен к выходу четвертого элемента задержки, третий вход второго трехвходового элемента И подсоединен к выходу четвертого элемента сравнения, второй вход которого соединен с выходом регистра максимального значения и с выходом показателя.

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