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

СОЮЗ СОВЕТСНИСОЦИАЛИСТИЧЕСНРЕСПУБЛИК 9)8 О( 40705 151)5 С 06 Р 13/37 ОСУДАРСТВЕННЫЙ НПО ИЗОБРЕТЕНИЯМ ИПРИ ГННТ СССР ИТЕТРЫТИЯМ ксан РЕТЕНИ 2 Ж 4 ь 3(46) 07.04.91. Бюп. Ь 13 (71) 11 ензенский политехнический институт(56) Авторское свидетельство СССР В 1282150, кл, С 06 Е 15/16, 1985.Авторское свидетельство СССР Кф 1336024, кл, Ь 06 Е 15/16, 1986. (54) УСТРОЙСТВО У 11 РАБЛЕНИЯ 11 ЕРЕДАЧЕЙ ИНФОРМАЦИИ И МНОГО 11 РОЦЕССОРНОЙ СИСТЕМЕ,(57) Изобретение относится к вычислительной технике и может быть использовано для децентрализованного управления передачей инФормации между компонентами вычислительной системы. Цель изобретения - уменьшениевремени ожидания начала передачи сообщений за счет обеспечения возможности источникам информации выходана обмен вне собственного интервала.Цель достигается тем, что в устройство, содержащее ключ 1, элемент И 2,адаптер 3, элемент ИЛИ-НЕ 4, элемент ИЛИ 5, генератор 6, делитель 7частоты, регистр 8 сдвига,.счетчик9, дешиФратор 10, триггер 11, блок 12запуска, элемент ИЛИ 13, элементыИ 14 - 16, введены блок 7 синхронизации, элемент ИЛИ 18, триггер 19,мультиплексор 20, счетчик 21, узел2 сравнения, триггер 23, регистр 2группа элементов И 25, 3 ил, 1640705Изобретение относится к вычисли"тельной технике и может быть использовано для децентрализованного управления передачей информации между компонентами вычислительных систем.Целью изобретения является уменьшение времени оидания начала. передачи сообщений за счет обеспечения источникам сообщений возможности выхо 10да на обмен вне собственного интервала.На фиг,1 приведена Функциональная схема устройства; на Фиг.2 - функциональная схема блока запуска; нафиг.3 вФункциональная схема узласравнения.Устройство (Фиг.1) содержит ключ1, элемент И 2, адаптер 3, элементИЛИ-НЕ 4, элемент ИЛИ 5, генератор6, делитель 7 частоты, регистр 8 сдвига, счетчик 9, дешифратор 10, триггер11, блок 12 запуска, элемент ИЛИ 13,элемент И 14-16, блок 17 синхронизации, элемент ИЗБ 18, триггер 19, муль типлексор 20, счетчик 21, узел 22сравнения, триггер 23., регистр 24,группу элементов И 25, вход 26 разрешения запуска, информационный вход 27,информационный вход-выход 28, выход.29 разрешения передачи, вход 30 запроса передачи, вход 31 тактовых импульсов, выход 32 столкновения.Блок запуска (Фиг.2) содержит элемент И 33 генератор одиночных имЭ35пульсов 34, Формирователь 35.Узел сравнения (Фиг.З) содержитэлементы ИСКЛЮЧАЮЩЕЕ ИЛИ 36, элементИЛИ 37 Формирователь 38.Всем устройствам, подключенным кобщей шине, присваивают в циклическом порядке номера, В соответствиис количеством устройств, а также сучетом предполагаемой интенсивностипоявления сообщений, передаваемых 4через них, выбирается длина регистра8 сдвига и определяются конкретные, установочные входы для регистра 8 каждого устройства,Устройство работает следующим образом,В начале работы многопроцессорнойсистемы от ведущего источника информации приходит сигнал пуска по входу26 разрешения запуска устройства.55Адаптер 3 выдает информацию о состоянии общей шины на входы элементаИЛИ-НЕ 4 и, если шина свободна, разрешается прием блоком 12 запуска сигнала разрешения запуска. На выходе блока 12 Формируется одиночный импульс, который устанавливает в исходное состояние регистр 24, регистр 8 сдвига, счетчики 9 и 21, и через элемент ИЛИ 13 сбрасывает триггеры 11, 19 и 23. Регистр 24 в каждом из устройств или группе устройств устанавливается в разное состояние. 11 ри установке регистра 8 сдвига у первого в цикле опроса устройства в последнем разряде устанавливается единица. Этим готовится к открытию элемент И 14. Счетчик 9 ведет счет импульсов, поступающих с выхода блока 7. Дешифратор 10подключенный к его выходам, устанавливает поочередно единицы на своих выходах. Если устройство имеет запрос на передачу, то через элемент И 14 сигнал с входа 30 установит в единичное состояние триггер 11. Этим сигналом через элемент ИЛИ 5 будет выдано разрещение передачи источнику, откроется ключ 1, обеспечи-. вая прохождение информации с информационного входа на выход, Входной адаптер 3 непрерывно выдает информацию о состоянии общей шины на входы элемента ИЛИ-НК 4. Если у источника информация имеется, то он осуществляет передачу информации в общую шину, Элемент ИЛИ-НЕ 4 в этом случае выдает нулевой потенциал на вход элемента И 2, не разрешая ему открываться,Триггер 11 продолжает оставаться в единичном состоянии после снятия сигнала на первом выходе дешифратора 10. Счетчик 9 продолжает считать, сигналы появляются на последующих выходах дешифратора 10, в зависимос" ти от состояния второго счетчика 21 и наличия единицы на соответствующем входе мультиплексора 20 могут готовиться к открытию элементы И 15, 16 и элементы И 25, Однако при наличии информации у источника, которому принадлежит данный интервал, элемент И 2, запертый нулевым потенциалом с выхода элемента ИЛИ-НК 4, не выдаст сигнал на установку в единичное состояние триггера 23, поэтому у данного источника в течение его интервала триггер 19 не будет установлен в единичное состояние. Передача информации данным источником будет продолжаться, При получении счетчиком 9 комбинации, соответствующей его коэффициенту счета, он обнуляется, появляется импульс на последнем выходе дешифратора 10, которым сбрасывается в нулевое состояние триггер 11 и подтверждается такое состояние у триггеров 19 и 23. Снимается разрешение на передачу данному источнику и закрывается ключ 1. Одновременно импульсом с выхода делителя 7 происходит сдвиг единицы в регистре 8 сдвига. Из последнего разряда она записывается в первый, у остальных устройств передвигается в сторону последнего разряда. Если у закончившего передачу устройства в регистре 8 не было двух единиц подряд, то управление передается следующему устройству и т,д,Устройство, не являющееся обладателем данного интервала передачи, у которого в это же время есть запрос 20 на передачу (устройство-обладатель интервала имеет информацию и ведет передачу), работает следующим образом.Из-за отсутствия сигнала на входе элементаИ 14 в таком устройстве не будет установлен триггер 11 и в первом такте разрешение на передачу оно не вырабатывает. Во втором такте, соответствующем сигналу на втором выходе дешифратора 10, нулевой потенциал с элемента ИЛИ-НЕ 4 не даст открыться элементу И 2, поэтому не будет установлен в единичное состояние триггер 23, в связи. с чем разрешение на передачу не .будет выработано ни в третьем, ни в последующих тактах. 11 ри35 этом срабатывает узел 22 сравнения, что приводит к срабатыванию счетчика 21 и возможному появлению единицы на выходе мультиплексора 20. Вырабатываемый для источника сигнал столкновения заставит его снять сигнал запроса передачи. Завершение интервала происходит аналогично завершению у устройства, проводившего передачу, 45 за исключением того, что триггер 11 не будет переводиться из единичного состояния в нулевое, а у него будет подтверждаться нулевое состояние.Устройство, не имеющее в отведенномему интервале информации для передачи, работает следующим образом.У такого устройства сигнал запроса передачи по входу 30 отсутствует, поэтому в начале интервала, когда 55 появится сигнал на первом выходе дешифратора 10 и на выходе последнего разряда регистра 8, элемент И 14 не сработает и триггер 11 не установит 16407056ся в единичное положение. 11 оэтому разрешение на передачу источнику выданоне будет, информация на информационный вход 27 устройства не поступит.Ключ 1 закрыт, 11 ри появлении импульса на втором выходе дешифратора 10из-за отсутствия сигнала запроса передачи элемент И 2 не будет открыт.,триггер 23 останется сброшенным, поэтому данное устройство не выработаетразрешения на передачу своему источнику до конца интервала. В конце интервала в данном устройстве импульсом с последнего выхода дешифратораО подтвердится нулевое состояниетриггеров 11, 19 и 23, произойдетсдвиг единицы в регистре 8 из последнего разряда в первый и т.д.В устройствах, которые имеют информацию для передачи, но не являютсяобладателями этого интервала, триггер не будет установлен в единичноесостояние в начале интервала при появлении импульса на первом выходе дешифратора 10 из-за отсутствия сигнала на втором входе элемента И 14.Адаптер 3, выдающий непрерывно информацию о состоянии общей шины на входыэлемента ИЛИ-НЕ 4, зафиксирует отсутствие ее в общей шине. Элемент И 2при появлении импульса на втором выходе дешифратора 10 откроется и установится в единичное состояние третийтриггер 23, который выдаст на входыэлементов И 15 и 16 и входы элементовИ 25 разрешающий сигнал. В общем случае это может произойти у несколькихустройств, имеющих запрос на переда"чу, но не являющихся обладателями данного интервала. Для этого в устройстве предусмотрена воэможность разнесения моментов начала передач дляразличных источников. Это осуществляется таким образом, что во всехустройствах в начальный момент време"ни регистры 24 устанавливаются в различные начальные состояния, Емкостьвторого счетчика 21, т.е. коэффициентего счета, а следовательно, и количество входов мультиплексора 20 и выходов регистра 24, а в конечном счетеи число элементов И, включая второй,третий элементы 15 и 16, а также элементы И 25, выбирается на этапе реализации конкретной системы, исходя1из устанавливаемого в ней количествапопыток предоставляемых каждому источнику в подобном режиме, для кача 1 б 40705ла передачи в данном интервале, оказавшемся свободным и используемым для свободной передачи. Чем больше будет количество попыток, тем ниже вероятность столкновений сообщений, С учетом выбранного числа попыток определяется и длина интервала передачи, а значит и емкость, т.е, коэффициент счета первого счетчика 9 и длина дешифратора 10 и емкость делителя 7.Длина интервала передачи выбирается при реализации конкретной системы по следующей формуле:. Тг= Т+ Т 2 + (К) Т, + шТ;+Т,5 где Т длительность первого такта, когда при отсутствии информации у источника-обладателя другие устройства обнаруживают Факт отсутствия передачи в общей шине;длительность второго такта, во время которого устройства готовятся к первой попыт ке свободного выходаколичество сдвинутых во времени моментов начал передач при свободном выходе источников, которое выбирается на З 0 .этапе реализации каждой конкретной системы в зависимости от количества устройств в системе, предполагаемой интенсивности их работы, зада 35 ваемых временных ограничений по доставке сообщений и др.; длительность одного текущего такта;количество тактов, отводимых непосредственно под передачу сообщения. Т2 К При отсутствии информации у источника"обладателя два первых такта от 45 водятся на подготовку к свободному.выходу, затем начинаются попытки выхода на передачу. Если источник начал успешно передавать с первой попытки, то в течение ш.тактов идет передача информации, а затем в течение (К-) такта идет завершение интервала, если со второй, то вначале идут три такта, затем ш, затем (К) и т,д. Если передача пошла с последней возможной попытки, то в последнем пустом такте у источников снимается сигнал столкновения и восстанавливается запрос. 11 ри установке регистров 24 в различные состояния единица на выходе мультиплексора 20 будет только у одного (если число попыток и входов мультиплексора равно числу устройств) или нескольких из всех устройств системы, если в регистре 24 единица установлена не только в одном разряде, например, для высокоприоритетных источников, или же вторые счетчики 21 в разных устройствах установились так, что у нескольких устройств на выходе мультиплексоров 20 подаются единицы с соответствующих, разных у каждого из устройств, входов. Допустим, что единица есть на выходах мультиплексоров 20 нескольких устройств, нозапрос на передачу имеет только одно устройство из тех, у кого единица выставлена на выходе мультиплексора 20, Тогда при появлении импульса на третьем выходе дешифратора. через элемент И 5 и элемент ИЛИ 8 триггер 19 будет установлен в единичное состояние, данное устройство выдаст своему источнику разрешение на передачу и через открытый ключ 1 начнется передача информации, При этом узел 22 сравнения данного устройства не будет Фиксировать столкновений и не будет вырабатывать блокирующий сигнал, У других устройств информация в общей шине и на информационном входе 27 при этом будет отличаться от той, которую передает получивший интервал источник, так как они не получат разрешения на передачу и не выставят информацию на информационный вход 27 устройства. Узел 22 сравнения этих устройств будет срабатывать, счетчики 21 изменять свои состояния, а источники будут получать блокирующий сигнал столкновения, при наличии которого они должны снимать сигнал запроса передачи, если был у них. До К-го такта вкпючительно и далее до конца передачи сообщения выработка сигнала запроса передачи у таких устройств будет заблокирована сигналом столкновения, Но окончании передачи сообщения наступает пауза до конца интервала и у данных устройств сигналом столкновения снимается, поэтому сигнал запроса передачи у них может быть восстановлен и источниками, если у них есть информация. Таким образом происходит восстановление возмощости участия в со 1 б 40705 10бытиях в следующем временном интервале: гарантированной передач , если устройство является обладателем этого интервала, или свободному выходу, если оно не является обладателем, а у последнего нет инФормации для передачи.Если же из числа пытающихся осуществить не в своем интервале передачу устройств единица на выходе муль типлексора 20 выставлена у нескольких устройств, то у них у всех через элемент И 15 и элемент ИЛИ 18 будет установлен триггер 19, все они получат разрешение на передачу, Однако при попытке передавать произойдет наложение информации в общей шине и все они выработают сигнал столкновения, по которому источники снимут сигнал запроса передачи с выхода 29 и информацию с входа 26. Второй счетчик 21 перейдет в следующее состояние, в мультиплексоре 20 осуцествится коммутация на выход следующего входа. В 25 устройствах, которые пытались осуществить выход на передачу, это приведет к снятию единицы с выхода мультиплексора (если только они не являются высокоприоритетными и у них при реализации была предусмотрена возможность начальной установки в регистр 24 нескольких единиц подряд или вразбивку) и они потеряют возможность дальнейших выходов на передачу. Если жеони имеют единицу и на последую 35 щем входе мультиплексора 20, то они будут участвовать в очередной попытке выхода. Таким образом, у этих устройств произойдет очередная коммутация в мультиплексоре 20 и через очередной иэ элементов И 15, 1 б или из группы элементов И 25 и ИЛИ 18 установится триггер 19 и будет выработано разрешение на передачу и открыт ключ 1.с Формула изобретенияУстройство управления передачей информации в многопроцессорной системе, содержащее ключ, адаптер, элемент ИЛИ-НЕ, два элемента ИЛИ, генератор, делитель частоты, регистр сдвига, счетчик, дешиФратор, триггер, блок запуска, четыре элемента И,причем информационный вход ключа является информационным входом устрой" ства, выход ключа подключен к входу адаптера и является инФормационным входом-выходом устройства, выход адаптера поразрядно подключен к входам элемента ИЛИ-НЕ, выход делителя частоты подключен к входам синхронизации блока запуска, вход разрешения запуска которого является одноименным входом устройства, выход блока запуска подключен к установочным входам регистра сдвига, выход переноса последнего разряда которого подключен к входу переноса первого разряда регистра сдвига и к первому входу первого элемента И, информационный выход счетчика подключен к входу дешифратора, о т л и ч а ю щ е е с я тем, что, с целью уменьшения времени ожидания начала передачи сообщения путем обеспечения возможности источникам сообщения выхода на обмен вне собственного интервала , в него введены блок синхронизации, элемент ИЛИ, два .триггера, мультиплексор, счетчик, узел сравнения, регистр, группа элементов И, причем управляющий вход ключа соединен с выходом первого элемента ИЛИ и является выходом разрешения передачи устройства, информационный вход ключа подключен к первому инФормационному входу узла сравнения, второй инФормационный вход которого соединен с выходом адаптера, выход элемента ИЛИ-НЕ соединен с входом блокировки блока запуска и первым входом второго элемента И, второй вход которого подключен к второму входу первого элемента И, первым входам второго и третьего элементов И, первым входам элементов И группы и является. входом запроса передачи устройства, третий вход второго элемента И соединен с вторым выходом дешиФратора, первый выход которого подключен к третьему входу первого элемента И, третий выход дешиФратора подключен к второму входу третьего элемента И, четвертый вход дешифратора подключен к второму входу четвертого элемента И, выходы дешиФратора, с пято го по К-й подключены к вторым входам элементов И группы, последний выход дешиФратора подключен к первому входу второго элемента ИЛИ, выход второго элемента И. соединен с входом установки первого триггера, второй вход второго элемента ИЛИ соединен с входом начальной установки первого счет"чика установочным входом второго12 1640705 счетчика, установочным входом регистра и выходом блока запуска, вход сдви 1 га регистра сдвига соединен с входом запуска блока запуска вход делиЭ5 теля частоты соединен со счетным входом первого счетчика и подключен к выходу блока синхронизации, первый вход которого подключен к выходу генератора, а второй вход .является вхо дом тактовых импульсов устройства, выход .первого элемента И соединен с входом установки второго триггера, вход сброса которого соединен с выходом второго элемента ИЛИ,входами сброса первого и третьего триггеров, выход первого триггера подключен к первому входу первого элемента ИЛИ, второй вход которого подключен к выходу второго триггера, вход установэлеиента й И-нес 5 ноуужены паузы Составитель Б.Резванктор А,Мотыль Техред С,Мигунова К ор Н. Ревская Подписи зобретениям и открытиям при ГКНТ СС Распекая наб., д. 4/5 изводственно-из ский комбинат "Патент", г, ужгород, ул. Гага 1017 Тираж 412Государственного каятета по 1 13035, Москва, Б-З ки которого подключен к выходу третьего элемента ИЛИ, входы которого сое"динены соответственно. с выходамитретьего и четвертого элементов И ивыходами элементов И группы, выходмультиплексора соединен с третьимивходами третьего и четвертого элементов И и третьими входами элементов Игруппы, информационный вход мультиплексора подключен к выходу регистра,управляющий вход мультиплексора подключен к выходу второго счетчика,счетный вход которого подключен к выходу узла сравнения и является выходом признака столкновения устройства,выход третьего триггера соединен счетвертыми входами третьего и четвертого элементов И ичетвертыми входами элементов И группы.