Устройство для упорядочивания объектов

Устройство для упорядочивания объектов

Иллюстрации

Показать все

Реферат

 

ОПИСАЙИЕ

ИЗОБРЕТЕНИЯ «1 467346

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Зависимое от авт. свидетельства (22) Заявлено 25.05.73 (21) 1922675/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 15.04.75. Бюллетень № 14

Дата опубликования описания 06.08,75 (51) М. Кл. б 06f 7/24

Государственный комитет

Совета Министров СССР ло делам изобретений и открытий (53) УДК 681.14-523.8 (088.8) (72) Авторы изобретения

В. ф. Жиров, В. Л, Ли, А. А. Соколов и В. И. Смирнов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧИВАНИЯ ОБЪЕКТОВ

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

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

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

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

10 очереди, вход которого соединен с выходом регистра совпадений. Выход схемы сравнения соединен со входом регистра совпадений.

На чертеже представлена блок-схема устройства.

15 Предлагаемое устройство содержит входной регистр 1, схему выборки 2, регистры очереди

3, выходной регистр 4, первую схему записи 5, регистр совпадений 6, вторую схему записи 7, регистр начала очереди 8, схему сравнения 9

20 и регистр конца очереди 10.

Количество элементов У предлагаемого устройства может быть приближенно равно:

N = n.log,ï, 25 в то же время для устройства фиксации приоритета информации и объектов:

N = nàj 2

Каждому объекту ставится в соответствие

З0 регистр очереди, т. е. номер объекта равен но10

0- 2- 3- 1.

60 меру регистра очереди. Для отображения упорядоченности объектов в регис;р очереди, соответствующий данному объекту, помещается номер того объекта, который в очереди непосредственно следует за данным объектом.

В двух регистрах указываются номера объектов, находящихся в начале и в конце очереди, эти регистры называются соответственно регистрами начала и конца очереди.

Для упрощения описания работы устройства принимаются некоторая конкретная очередь для четырех объектов.

Для этого упорядоченность объектов представляется следующей строкой 2 0 3 1, где целое число указывает номер объекта, т. е. в начале очереди стоит второй объект, затем— нулевой, затем — третий, а в конце — первый.

В таком случае регистры очереди РО; (где

i=0, 1, 2, 3) содержат следующие номера:

РО, 3) РО, Х,РО, 0>РО, 1) где Х вЂ” объект, находящийся в конце очереди, P O — регистр очереди.

Содержимое регистра конца очереди в данном случае равно: РК=1, содержимое регистра начала очереди — РН=2, где РК вЂ” регистр конца очереди, PH — регистр начала очереди. Перестройка очереди задается указанием номера объекта, который должен быть помещен в начало очереди, а упорядоченность остальных объектов сохраняется. Номер объекта, который должен быть помещен в начало очереди, устанавливается на входном регистре.

Предположим, что содержимое входного регистра 1 равно «О», т. е. очередь должна стать следующей:

Содержимое регистров также должно измениться:

PO,=2, РО,=Х, РО,=Ç, РО,=1, РН=О, РК=1.

Для рассматриваемого примера в начальный момент состояние регистров следующее:

РО,=З,РО,=Х,РО,= — О,Р0,=-1, РК=1, РН =2, и содержимое входного регистра 1 равно «О», следовательно, на выходной регистр выдается содержимое нулевого регистра очереди, т. е.

«3». Содержимое регистра совпадений равно

«2», так как «О» на входном регистре совпадает с «О» во втором регистре очереди (РО ).

Входной регистр 1 соединен со второй схемой записи 7, так что содержимое регистра начала очереди 8 записывается в тот регистр очереди

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

Для рассматриваемого примера регистр начала содержит «2», а входной регистр — «О», таким образом, в нулевой регистр очереди 3 записывается число «2» (РОС вЂ” — 2) .

Первая схема записи 5, записывая содержимое выходного регистра 4, равное «3», в регистр очереди 3, номер которого указан на регистре совпадений 6, равным «2», изменяет содержимое второго регистра очереди PO> — — 3.

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

PO,=2, РО,=,Х, РО,=З, PO,=1.

Остается изменить содержимое регистра начала очереди 8, куда помещается содержимое входного регистра 1

РН= О.

Необходимость регистра конца очереди 10 ясна из следующей ситуации: пусть на каждом регистре появляется номер объекта, который состоит в конце очереди. Например, для очереди 203 — 1 появление на входном регистре «1» вызывает некоторые дополнительные действия. Регистр совпадений содержит вместе с номером регистра очереди 3, в котором содержится ссылка на конец очереди, и признак конца очереди, как результат сравнения входного регистра 1 с регистром конца очереди 10.

Под управлением признака конца очереди в регистр конца очереди 10 записывается содержимое регистра совпадений 6, равное «3».

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

РО,=З, РО,=Х, РО,=О, РО,=1, РН=2, РК =1, переходим к состоянию, представленному:

РОю =3 РО =2 РОа =О, РОз = Х, РН=1, РК=З.

Регистр начала очереди 8 также соединен схемой сравнения 9 с входным регистром 1 (при фиксации совпадения с регистром начала никаких действий по перестройке очереди не выполняется).

Предмет изобретения

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

Составитель А. Козлин

Техред Т, Миронова

Редактор Е. Семанова

Корректор А. Степанова

Заказ 1810!2 Изд, Ко 1364 Тираж 679 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, Ж-35, Раушская наб., д. 4/5

Типография, пр. Сап нова, 2 дений, причем выход первой схемы записи соединен со входами регистров очереди, выход входного регистра — со входом регистра начала очереди и с первым входом второй схемы записи, со вторым входом которой соединен выход регистра начала очереди, выход второй схемы записи соединен со входами регистров очереди, выход входного регистра — с первым входом схемы сравнения, со вторым входом которой соединены выходы регистров очереди, с третьим входом — выход регистра начала очереди, с четвертым входом — выход регистра конца очереди, вход которого соединен с выходом регистра совпадений, причем выход схемы сравнения соединен со входом регистра совпадений.