Устройство анализа и перестановки числовых полей Советский патент 1987 года по МПК G06F7/00 

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

1

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

В вычислительной технике час.то встречается операция анализа возможности перестановки числовых полей и

нт данных 3

связи О

1

2

(попе 3

0 число поле 2 )

1 число

О ; число О число 000.. , 00, I

h--i

Поле элемента данных представляет собой целое число со знаком. Обозначим j-e поле 1-го элемента данных П.. , значение знакового разряда этого поля - ЗП;; , значение числовых разрядов

- чп...

Условием возможности

перестановки числовых полей в устройстве анализа и перестановки числовых полей является истинность выражения () Л(ЗП11-0) Л() А (ЧЛ10/11,,.11)Л ()Л (ЗП21-1) Л () Л (ЧП20/11...11) л ((ЧП12 ЧП23)©() Л () Л Л() л (() 0(ЧП20 ЧП13))..

Операция перестановки для элементов данных ШЗ П12 П11 П10 и П23 П22 П21 П20 дает результат П13 П12 П21 111..,01 или П13 П12 П20 111. ..11 или П13 П11 П2Г111...11 или П13 П11 П20 111.., 11. Выполнение таких операций с использованием устройства засдвигаются на размер одного поля, а освободившееся поле заполняется признаком Пусто, С выходов блоков коррекции вьщеленные поля Подаются на входы группы элементов ИЛИ, где объединяются и поступают на первый выход устройства, 6 ил.

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

поля связи

: поле 1 поле О 1.11 11 ...11,

п I 1 число

0000.,,01 ) 0000,..10

h-1

h-1

25

мены числовых полей не обеспечивает приемлемого времени обработки из-за необходимости программного анализа возможности перестановки числовых

полей и формирования маски,

Целью изобретения является повышение быстродействия устройства. На фиг,1 изображена функциональ30 ная схема устройства анализа и перестановки числовых полей; на фиг,2 - то же, блока формирования масок; на фиг,3 - то же, первого блока коррекции; на фиг,4 - то же, второго блока

35 коррекции; на фиг.5 - то же, группы элементов ИЛИ; на фиг,6 - то же, группы элементов НЕ.

Устройство (фиг.1) содержит первы 40 входной регистр 1, второй входной регистр 2, блок 3 формирования масок, первьй регистр 4 маски, второй регистр 5 маски, первую группу 6 эле:31317429

ментов И, вторую группу 7 элементов И,- первый блок 8 коррекции, второй блок 9 коррекции, группу 10 элементов ИЛИ.

Блок формирования масок (фиг.2) содержит первый 11 и второй 12 элементы НЕ, второй элемент И 13, третий элемент НЕ.14, третий элемент И 15, четвертую, третью, первую, втония масок для осуществления перестановки. Первый элемент И 26 (фиг.2) осуществляет формирование результата анализа возможности перестановки как конъюнкции значения (), представляемого выходом первого элемента НЕ 11, значения (), представляемого выходом второго элемента НЕ 12, значения (), представляерую, пятую и шестую схемы 16-21 срав- 0 мого (п-1)-м разрядом первого входа

нения, первьй 22 и второй 23 элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, пятый 24 и четвертый 25 элементы НЕ, первый элемент И 26, шестой 27 и седьмой 28 элементы НЕ, элемент ИЛИ 29.

Первый блок коррекции (фиг.З) содержит . группу 30 элементов НЕ, группу 31 элементов ИЛИ, а второй (фиг .4) группу 3-2 элементов ИЛИ.

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

Первый и второй элементы данных поступают на входы первого и второго (фиг.1) входных регистров 1 и 2 соответственно, а с их выходов - на входы соответственно первой 6 и второй 7 групп элементов И, на другие входы которых поступают первая и вторая маски с выходов первого 4 и вто- рого 5 регистров маски соответственно. Вьщеленные с помощью масок в группах элементов И поля элементов данных поступают на входы первого 8 и второго 9 блоков коррекции, где соответствующим образом сдвигаются и подаются на входы группы 10 элементов ЮТИ, где осуществляется формирование из них единого элемента данных, который появляется на выходе группы 10 элементов ИЛИ, являющемся первым выходом устройства. При этом соответствующие разряды (фиг.1) выходов первого 1 и второго 2 входных регистров поступают на первьй и вто- рой входы блока 3 формирования масок с первого и третьего выходов которого сформированные маски поступают соответственно на входы первого 4 и второго 5 регистров маски. Второй выход блока формирования масок является одновременно вторым выходом устройства и сигнализирует о положительном результате анализа возможности перестановки числовых полей.

Блок формирования масок предназначен для анализа возможности перестановки числовых полей и формирования масок для осуществления перестановки. Первый элемент И 26 (фиг.2) осуществляет формирование результата анализа возможности перестановки как конъюнкции значения (), представляемого выходом первого элемента НЕ 11, значения (), представляемого выходом второго элемента НЕ 12, значения (), представляе5

0

5

0 5 0 5 0 5

блока формирования масок, значения ( 1 ... 11) , представляемого инл+ 1

версным выходом второго элемента И 13, значения (), представляемого выходом третьего элемента НЕ 14, значения (), представляемого (2п-1)-м разрядом второго входа блока формирования масок, значения (), представляемого (п-1)-м. разрядом второго входа блока формирования масок, значения (ЧП20 1... 11) представляемого инверсным

tt -t

выходом третьего элемента И 15, значения (), представляемого выходом совпадения первой схемы 18 сравнения, значения () @ Ф(), представляемого выходом первого элемента ИСКЛЮЧАЩЕЕ ШШ 22, значения (), представляемого выходом совпадения второй схемы 19 сравнения, значения () ©(), представляемого выходом второго элемента ИСКЛЮЧАЮЩЕЕ ШШ 23. При этом значение ЧП10 поступает на входы второго элемента И 13 и на первьй вход первой схемы 18 сравнения с разрядов, начиная с нулевого по (п-2)-й включительно, первого входа блока формирования масок, значение ЧП11 поступает на первый вход третьей схемы 17 сравнения с разрядов, начиная с п-го по (2п-2)-й, первого входа блока формирования масок, значение ЗП11 поступает на вход второго элемента НЕ 12 с (2п-1)-го разряда первого входа блока формирования масок, значение ЧП12 поступает на первый вход четвертой схемы 16 сравнения с разрядов, начиная с 2п-го по (Зп-2)-й, первого входа блока формирования масок, зна-- чение ЗП12 поступает на вход первого элемента НЕ 11 с (Зп-1)-го разряда первого входа блока формирования масок, значение ЧП13 поступает на первые входы второй 19, пятой 20, шестой 21 схем сравнения с разрядов, начиная

с 3 n-го по (4п-2)-й, первого входа блока формирования масок, значение ЧП20 поступает на входы третьего элемента И 15 и второй вход шестой схемы 21 сравнения с разрядов, начиная с нулевого по (п-2)-й, второго входа блока формирования масок, значение ЧП21 поступает на второй вход пятой схемы 20 сравнения с разрядов, начиная с п-го по (2п-2)-й, второго входа блока формирования масок, значение ЧП22 поступает на второй вход второй Схемы 19 сравнения с разрядов начиная с 2п-го по (Зп-2)-й, второго входа блока формирования масок, значения ЧП23 поступают на вторые входы четвертой 16, третьей 17 и на первьй вход 18 схем сравнения с разрядов, начиная с Зп-го по (4п-2)-й, второго входа блока формирования масок. Выходы совпадения четвертой 16 и третьей 17, пятой 20 и шестой 21 схем

сравнения поступают на первьй и второй входы первого 22 и второго 23 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, образуя на их выходах значения ()0 ©() и () © ( ЧП13), и на входы пятого 24, чет.вертого 25, шестого 27 и седьмого 28 элементов НЕ соответственно, выходы которых ус1 анавливают разряды, начиная с п-го по (Зп-1)-й, первой маски и разряды, начиная с нулевого по (2п-1)-й, второй маски в О или 1 в зависимости от того, на какой схеме сравнения зафиксировано совпадение числовых кодов (фиг.2), Остальные разряды масок устанавливаются стандартно в О или 1 (фиг.2) прямым и инверсньм выходами элемента ИЛИ 29, которые имеют постоянные значения, так как его входы связаны с прямым и инверсным выходами первого элемента И 26, прямой выход которого сигнализирует о результате анализа возможности перестановки числовых полей и является вторым йыходом формирователя и одновременно устройства Первый блок коррекции осуществляет вьщачу вьщеленного числового поля во втором элементе данных в поле П21 так как -вьщеленное поле связи может находиться в П21 и П20, и заполнение поля П20 единицами с помощью группы элементов НЕ 30 (фиг. 3), которая ин вентирует значение П22, равное .000.. .00. Формирование на выходе первого блока коррекции поля 1121 осуществляется с помощью группы элементов ИЛИ 31, которая объединяет на, своих входах поля П21 и П20 входа первого блока коррекции, так как в

одном из них находятся нули.

Второй блок коррекции осуществляет вьщачу выделенных числовых полей в первом элементе данных в полях Л13 и П12, так как выделенное поле

связи может находиться в П12 или П11. Формирование на выходе второго блока коррекции П12 осуществляется с помощью группы элементов ИЛИ 32 (фиг.4), которая объединяет на своих входах

поля П12 и П11, так как в одном из них находятся нули. Освобождаемое поле П11 заполняется нулями (фиг.4) из поля П10.)

20

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

Устройство анализа и перестановки

числовых полей, содержащее два входньгх регистра, два регистра маски,

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

но, выходы элементов ИЛИ группы образуют первьй выход устройства, причем разряд (Зп-1)-й выхода первого входного регистра подключен к входу первого элемента НЕ блока формирования

масок, выход которого соединен с первым входом первого элемента И блока формирования масок, разряд (2п-1)-й выхода первого входного регистра подключен к входу второго элемента НЕ

блока формирования масок, выход которого соединен с вторым входом первого элемента И блока формирования масок, с нулевого поля по (п-2)-й разряды выхода первого входного регистра соединены поразрядно с входами второго элемента И блока формирования масок, с нулевого по (п-2)-й разряды выхода второго входного регистра соединены поразрядно с входами

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

ИСКЛЮЧАЮЩЕЕ ИЛИ, в первый блок коррекции введены (п-1) элементов НЕ, причем с нулевого по (п-2)-й разряды выхода первого входного регистра соединены поразрядно с входами второй группы первой схемы сравнения, с п-го по (2п-2)-й разряды выхода первого входного регистра соединены поразрядно с входами первой группы третьей схемы сравнения, с 2 п-го по (Зп-2)-й разряды выхода первого входного ре- гистра соединены поразрядно с входами первой группы четвертой схемы сравнег НИН, с Зп-го по (4п-2)-й разряды выхода первого входного регистра соединены поразрядно с входами первых групп пятой и шестой схем сравнения, с нулевого по (п-2)-и разряды выхода второго входного регистра соединены поразрядно с входами второй группы шестой схемы сравнения, с п-го по (2п-2)-й разряды выхода второго входного регистра соединены поразрядно с входами второй группы пятой схемы сравнения, (Зп-1)-й разряд выхода второго входного регистра соединен

с входом третьего элемента НЕ блока формирования масок, с Зп-го по (4п-2)-й разряды выхода второго входного регистра соединены поразрядно с входами вторых групп третьей и четвертой схем сравнения, выходы Равно которых соединены соответственно с первым и вторым входами первого элемента ИСКЛЮЧАЩЕЕ ИЛИ входами соответственно четвертого и пятого элементов НЕ блока формирования масок, выходы Равно пятой и шестой схем сравнения соединены соответственно с первым и вторым входами второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и с входами соответственно шестого и седьмого элементов НЕ блока формирования масок, причем (п-1)-и разряд выхода второго входного регистра, выход третьего элемента НЕ блока формирования масок, инверсный выход второго элемента И блока формирования масок, (п-1)-и разряд выхода первого входного регистра, выходы первого и второго элементов ИСКЛЮЧАЩЕЕ Р1ПИ соединены поразрядно с седьмым, восьмым, девятым, десятым, одиннадцатым и двенадцатым входами первого элемента И блока формирования масок, причем выходы четвертого и пятого элементов НЕ блока формирования масок соединены соответственно с п-го по (2п-1)-й и с 2п-го по (Зп-1)-й разрядами входа первого регистра маски, выходы шестого и седьмого элементов НЕ блока формирования масок соединены со- ответственно с п-го по (2п-1)-й и с нулевого по (п-1)-й разрядами входа второго регистра маски, инверсньй выход элемента ИЛИ блока формирования масок соединен с нулевого по (п-1)-й разрядами входа первого регистра маски, выхО;п;ы элементов ШШ группы первого блока коррекции со- единены поразрядно с вторыми входами с п-го по (2п-1)-й элементов ИЛИ группы, выходы с 2п-го по (Зп-1)-й элементов И второй группы соединены поразрядно с входами элементов НЕ первого блока коррекции, выходы кото

рых соединены поразрядно с вторыми входами с нулевого по (п-1)-й элементов ИЛИ группы, выходы с нулевого по (п-1)-й элементов И первой группы соединены поразрядно с первыми входами с п-го по (2п-1)-й элементов ИЛИ группы, выходы с п-го по (2п-1)-й элементов И первой группы соединены поразрядно с первыми входами элементов ИЛИ группы второго блока коррек- ции, с вторыми входами которых соединены поразрядно выходы с 2п-го по (Зп-1)-й элементов И первой группы, выходы элементов ИЛИ группы второго блока коррекции соединены поразрядно с первыми входами с 2п-го по (Зп-1)-й элементов ИЛИ группы.

Изобретение относится к области цифровой вычислительной техники и может использоваться при обработке структурно сложной информации (графов, таблиц), анализе структур алгоритмов и программ, оптимизации цик;лических участков граф-схем алгорит- JMOB. Оно позволяет вьшолнять часто встречаемую операцию анализа и перестановки числовых полей, которыми кодируется списковое представление графов. Цель изобретения - повышение быстродействия устройства. Устройство анализа и перестановки числовых полей содержит два входных регистра 1 и 2, блок формирования масок 3, два регистра маски 4, 5, две группы элементов И 6, 7, два блока коррекции 8, 9, группу элементов ИЛИ 10. Два элемента данных, которые необходимо проанализировать, поступают на входные регистры, а с них - на входы блока формирования масок и, кроме того, на входы первой и второй групп элементов И. С помощью блока формирования масок анализируется возможность перестановки числовых полей в соответствии с правилом обобщения циклических участков граф-схем, и результат анализа представляется на его втором выходе, являющемся вторым выходом устройства, а также формиру 2 iS (Л . J4/ J с 1Г со М 4 Ю СО

сриг.з

4-..

л

фиг А

Л

п п

П-1

/7-П1/ Ё

п-г

41

фиг. 5

I

V

/7-/

Л-Z

/7-/

«

E.

w.

«7

Составитель О.Берещикова Редактор А.Маковская Техред А.Кравчук КорректорМ.Шароши

Заказ 2424/43

Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полигрфическое предприятие, г.Ужгород, ул.Проектная,