Устройство управления передачей информации в многопроцессорной системе Советский патент 1991 года по МПК G06F13/376 G06F15/16 

о

Јь

Изобретение относится к вычислительной технике и может быть использовано для децентрализованного управления передачей информации между компонентами вычислительной системы. Цель изобретения - уменьшение времени ожидания начала передачи сообщений за счет обеспечения возможности источникам информации выхода на обмен вне собственного интервала,, Цель достигается тем, что в устройство, содержащее ключ 1, элемент И 2, адаптер 3, элемент ИЛИ-НЕ 4, элемент ИЛИ 5, генератор 6, делитель 7 частоты, регистр 8 сдвига,.счетчик 9, дешифратор 10, триггер 11, блок 12 запуска, элемент ИЛИ 13, элементы И 14 - 16, введены блок 17 синхрони- з ации, элемент ИЛИ 18, триггер 19, мультиплексор 20, счетчик 21, узел 22 сравнения, триггер 23, регистр 24, группа элементов И 25 , 3 ил„ to (Л

2

сд

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

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

На фиг.1 приведена функциональная схема устройства; на - функциональная схема блока запуска; на фиг.З - функциональная схема узла сравнения

Устройство (фиг„О содержит ключ

I,элемент И 23 адаптер 3, элемент ИЛИ-НЕ 4, элемент ИЛИ 5, генератор

6, делитель 7 частоты, регистр 8 сдвига, счетчик 9, дешифратор 10, триггер

II,блок 12 запуска, элемент ИЛИ 13, элемент И 14-16, блок 17 синхронизации, элемент ИЛИ 18, триггер 19, муль типлексор 20, счетчик 21, узел 22 сравнения, триггер 23, регистр 24, группу элементов И 25, вход 26 разрешения запуска, информационный вход 27 информационный вход-выход 28, выход 29 разрешения передачи, вход 30 запроса передачи, вход 31 тактовых импульсов, выход 32 столкновенияо

Блок запуска (фиг02) содержит элемент И 33, генератор одиночных импульсов 34, формирователь 350

Узел сравнения (фигоЗ) содержит элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 36, элемент ИЛИ 37, формирователь 38.

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

Устройство работает следующим об- разомо

В начале работы многопроцессорной системы от ведущего источника информации приходит сигнал пуска по входу 26 разрешения запуска устройства,, Адаптер 3 выдает информацию о состоянии общей шины на входы элемента ИЛИ-НЕ 4 и, если шина свободна, разрешается прием блоком 12 запуска сиг

0

5

0

5

0

5

0

5

нала разрешения запуска На выходе блока 12 формируется одиночный импульс, который устанавливает в исходное состояние регистр 24, регистр 8 сдвига, счетчики 9 и 21, и через элемент ИЛИ 13 сбрасывает триггеры 11, 19 и 230 Регистр 24 в каждом из устройств или группе устройств устанавливается в разное состояние При установке регистра 8 сдвига у первого в цикле опроса устройства в последнем разряде устанавливается единица. Этим готовится к открытию элемент И 14 Счетчик 9 ведет счет импульсов, поступающих с выхода блока 17„ Дешифратор 10, подключенный к его выходам, устанавливает поочередно единицы на своих выходах. Если устройство имеет запрос на передачу, то через элемент И 14 сигнал с входа 30 установит в единичное состояние триггер 11. Этим сигналом через элемент ИЛИ 5 будет выдано разрещение передачи источнику, откроется ключ 1, обеспечивая прохождение информации с информационного входа на выходс Входной адаптер 3 непрерывно выдает информацию о состоянии общей шины на входы элемента ИЛИ-НЕ 4 о Если у источника информация имеется, то он осуществляет передачу информации в общую шину. Элемент ИЛИ-НЕ 4 в этом случае выдает нулевой потенциал на вход элемента И 2, не разрешая ему открываться

Триггер 11 продолжает оставаться в единичном состоянии после снятия сигнала на первом выходе дешифратора 10 Счетчик 9 продолжает считать, сигналы появляются на последующих выходах дешифратора 10, в зависимости от состояния второго счетчика 21 и наличия единицы на соответствующем входе мультиплексора 20 могут готовиться к открытию элементы И 15, 16 и элементы И 250 Однако при наличии информации у источника, которому принадлежит данный интервал, элемент И 2, запертый нулевым потенциалом с выхода элемента ИЛИ-НЕ 4, не выдаст сигнал на установку в единичное состояние триггера 23, поэтому у данного источника в течение его интервала триггер 19 не будет установлен в единичное состояние. Передача информации данным источником будет продолжаться0 При получении счетчиком 9 комбинации, соответствующей коэффициенту счета, он обнуляется, появляется импульс на последнем выходе дешифратора 10, которым сбрасывается в нуле- вое состояние триггер 11 и подтверждается такое состояние у триггеров 19 и 23 Снимается разрешение на передачу данному источнику и закрывается ключ 1 о Одновременно импульсом с выхода делителя 7 происходит сдвиг единицы в регистре 8 сдвига Из последнего разряда она записывается в первый, у остальных устройств передвигается в сторону последнего разряда Если у закончившего передачу устройства в регистре 8 не было двух единиц подряд, то управление передается следующему устройству и т0д0

Устройство, не являющееся обладателем данного интервала передачи, у которого в это же время есть запрос на передачу (устройство-обладатель интервала имеет информацию и ведет предачу) , работает следующим образом0

Из-за отсутствия сигнала на входе элемента И 14 в таком устройстве не будет установлен триггер 11 и в первом такте разрешение на передачу оно не вырабатываете Во втором такте, соответствующем сигналу на втором выходе дешифратора 10, нулевой потенциал с элемента ИЛИ-НЕ 4 не даст открыться элементу И 2, поэтому-не будет установлен в единичное состояние триггер 23, в связи с чем разрешение на передачу не будет выработано ни в третьем, ни в последующих тактах При этом срабатывает узел 22 сравнения, что приводит к срабатыванию счетчика 21 и возможному появлению единицы на выходе мультиплексора 20„ Вырабатываемый для источника сигнал столкновения заставит его снять сигнал запроса передачио Завершение интервала происходит аналогично завершению у устройства, проводившего передачу, за исключением того, что триггер 11 не будет переводиться из единичного состояния в нулевое, а у него будет подтверждаться нулевое состояние0

Устройство, не имеющее в отведенном ему интервале информации для передачи, работает следующим образом.

У такого устройства сигнал запроса передачи по входу 30 отсутствует, поэтому в начале интервала, когда появится сигнал на первом выходе дешифратора 10 и на выходе последнего разряда регистра 8, элемент И 14 не сработает и триггер 11 не установит10

15

20

ся в единичное положение Поэтому разрешение на передачу источнику выдано не будет, информация на информационный вход 27 устройства не поступит Ключ 1 закрыт. При появлении импульса на втором выходе дешифратора 10 из-за отсутствия сигнала запроса передачи элемент И 2 не будет открыт триггер 23 останется сброшенным, поэтому данное устройство не выработает разрешения на передачу своему источнику до конца интервала В конце интервала в данном устройстве импульсом с последнего выхода дешифратора 10 подтвердится нулевое состояние триггеров 11, 19 и 23, произойдет сдвиг единицы в регистре 8 из последнего разряда в первый и

В устройствах, которые имеют информацию для передачи, но не являются обладателями этого интервала, триггер не будет установлен в единичное состояние в начале интервала при появ25 лении импульса на первом выходе дешифратора 10 из-за отсутствия сигнала на втором входе элемента И 14 Адаптер 3, выдающий непрерывно информацию о состоянии общей шины на входы элемента ИЛИ-НЕ 4, зафиксирует отсутствие ее в общей шине0 Элемент И 2 при появлении импульса на втором выходе дешифратора 10 откроется и установится в единичное состояние третий триггер 23, который выдаст на входы элементов И 15 и 16 и входы элементов И 25 разрешающий сигнал В общем случае это может произойти у нескольких устройств, имеющих запрос на передачу, но не являющихся обладателями данного интервала Для этого в устройстве предусмотрена возможность разне- сения моментов начала передач для различных источников. Это осущест45 вляется таким образом, что во всех устройствах в начальный момент времени регистры 24 устанавливаются в различные начальные состояния,, Емкость второго счетчика 21, коэффициент его счета, а -следовательно, и количество входов мультиплексора 20 и выходов регистра 24, а в конечном счете и число элементов И, включая второй, т.ретий элементы 15 и 16, а также элесс менты И 25, выбирается на этапе реализации конкретной системы, исходя из устанавливаемого в ней количества попыток,, предоставляемых каждому источнику в подобном режиме, для нача-1

30

35

40

50

ла передачи в данном интервале, оказавшемся свободным и используемым для свободной передачи,. Чем больше будет количество попыток, тем ниже вероятность столкновений сообщений С уче- том выбранного числа попыток определяется и длина интервала передачи, а значит и емкость, т0е. коэффициент счета первого счетчика 9 и длина де- шифратора 10 и емкость делителя 70

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

Тинт Т, + Тг + (К-1) Т; + га .Т;+Т

где Т - длительность первого такта, когда при отсутствии информации у источника-обладателя другие устройства обнару- живагот факт отсутствия передачи в общей шине;

Т - длительность второго такта, во время которого устройства готовятся к первой попыт- ке свободного выхода;

К - количество сдвинутых во времени моментов начал передач при свободном выходе источников, которое выбирается на этапе реализации каждой конкретной системы в зависимости от количества устройств в системе, предполагаемой интенсивности их работы, задаваемых временных ограничений по доставке сообщений и др„;

Т - длительность одного текущего такта;

зп - количество тактов, отводи- мых непосредственно под передачу сообщенияо

При отсутствии информации у источника-обладателя два первых такта от- водятся на подготовку к свободному выходу, затем начинаются попытки выхода на передачу,, Если источник начал успешно передавать с первой попытки, то в течение m тактов идет передача информации, а затем в течение (К-1) такта идет завершение интервала, если со второй, то вначале идут три такта, затем т, затем (К-2) и твд« Если передача пошла с последней возможной попытки, то в последнем пустом такте у источников снимается сигнал столкновения и восстанавливается запрос

,

При установке регистров 24 в различные состояния единица на выходе мультиплексора 20 будет только у одного (если число попыток и входов мультиплексора равно числу устройств) или нескольких из всех устройств системы, если в регистре 24 единица установлена не только в одном разряде, например, для высокоприоритетных источников, или же вторые счетчики 21 в разных устройствах установились так, что у нескольких устройств на выходе мультиплексоров 20 подаются единицы с соответствующих, разных у каждого из устройств, входов. Допустим, что единица есть на выходах мультиплексоров 20 нескольких устройств, но запрос на передачу имеет только одно устройство из тех, у кого единица выставлена на выходе мультиплексора 20„ Тогда при появлении импульса на третьем выходе дешифратора через элемент И 15 и элемент ИЛИ 18 триггер 19 будет установлен в единичное состояние, данное устройство выдаст своему источнику разрешение на передачу и через открытый ключ 1 начнется передача информации При этом узел 22 сравнения данного устройства не будет фиксировать столкновений и не будет вырабатывать блокирующий сигнал, У других устройств информация в общей шине и на информационном входе 27 при этом будет отличаться от той, которую передает получивший интервал источник, так как они не получат разрешения на передачу и не выставят информацию на информационный вход 27 устройства,, Узел 22 сравнения этих устройств будет срабатывать, счетчики 21 изменять свои состояния, а источники будут получать блокирующий сигнал столкновения, при наличии которого они должны снимать сигнал запроса передачи, если был у них До К-го такта включительно и далее до конца передачи сообщения выработка сигнала запроса передачи у таких устройств будет заблокирована сигналом столкновения,, Но окончании передачи сообщения наступает пауза до конца интервала и у данных устройств сигналом столкновения снимается, поэтому сигнал запроса передачи у них может быть восстановлен и источниками, если у них есть инфор™ мация. Таким образом происходит восстановление возможности участия в событиях в следующем временном интервале: гарантированной передаче, если устройство является обладателем этого интервала, или свободному выходу, если оно не является обладателем, а у последнего нет информации для передачи 0

Если же из числа пытающихся осуществить не в своем интервале передачу устройств единица на выходе муль типлексора 20 выставлена у нескольких устройств, то у них у всех через элемент И 15 и элемент ИЛИ 18 будет установлен триггер 19, все они получат раарешение на передачу Однако при попытке передавать произойдет наложение информации в общей шине и все они выработают сигнал столкновения, по которому источники снимут сигнал запроса передачи с выхода 29 и информацию с входа 26о Второй счетчик 21 перейдет в следующее состояние, в мультиплексоре 20 осуществится коммутация на выход следующего входа,, В устройствах, которые пытались осуществить выход на передачу, это приведет к снятию единицы с выхода мультиплексора (если только они не являются высокоприоритетными и у них при реализации была предусмотрена возможность начальной установки в регистр 24 нескольких единиц подряд или вразбивку) и они потеряют возможность дальнейших выходов на передачуо Если же они имеют единицу и на последующем входе мультиплексора 20, то они будут участвовать в очередной попытке выхода Таким образом, у этих устройств произойдет очередная коммутация в мультиплексоре 20 и через очередной из элементов И 15, 16 или из группы элементов И 25 и ИЛИ 18 установится триггер 19 и будет выработано разрешение на передачу и открыт ключ 1.

Формула изобретения

Устройство управления передачей информации в многопроцессорной сие

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

10

15

20

25

30

35

40

45

50

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

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

С выхода делителя 7

С Выхода

элемента 4 И-не обнаружены паузы

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

А ус/пановомь/м Јходам

t T f/ rw/jw

элемента 13ИМ , Входа начальной ус/поноем счетчи/ а 9

Фиг 2