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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1317429 А 1

Ио 4 С 06 F 7/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ;;:.К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

СЮ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР .

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3943288/24-24 (22) 06,08.85 (46) 15,06.87. Бюл. № 22 (71) Белорусский государственный университет им.В.И.Ленина (72) А.B.Соболев, Г.Н.Черников и В.А.Чудовский (53) 681 ° 3(088.8) (56) Авторское свидетельство СССР № 1132284, кл. G 06 F 7/00, 1983.

Авторское свидетельство СССР № 1280606, кл. G 06 F 7/00, 25.07.85. (54) УСТРОЙСТВО АНАЛИЗА И ПЕРЕСТАНОВКИ ЧИСЛОВЫХ ПОЛЕЙ (57) Изобретение относится к области цифровой вычислительной техники и может использоваться при обработке структурно сложной информации (графов, таблиц), анализе структур алгоритмов и программ„ оптимизации цик,лических участков граф-схем алгорит1мов. Оно позволяет выполнять часто встречаемую операцию анализа и перестановки числовых полей, которыми кодируется списковое представление графов. Цель изобретения — повышение быстродействия устройства. Устройство анализа и перестановки числовых полей содержит два входных регистра

1 и 2, блок формирования масок 3, два регистра маски 4, 5, две группы элементов И 6, 7, два блока коррекции 8, 9, группу элементов ИЛИ 10.

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

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

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

10 (элемент данных >

<поле 3 > (поля связи > (поле 0 >

= (поле 3> — О (число>

= (поле 2 >

1 (число > (поля связи >

<поле 1> < поле 01

I1111...11 и 1 <число > (поле 1 >

< поле 2> (число >

= 0(число>

0 (число>

= 000...00 !

И-1

OOOO...О1 0000...10 —

1111...10

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

П, значение знакового разряда этого

ij поля — ЗП;, значение числовых разрядов — ЧП; . Условием возможности перестановки числовых полей в устройстве анализа и перестановки числовых полей является истинность выражения (ЗП12=0) Л (ЗП11=0) h (ЗП10=1)

h (ЧП10 11...11)Л (ЗП22=0) Л (ЗП21=-1)

rL(ЗП20=1) и (ЧП20у 11...11) и ((ЧП12=

=ЧП23) 0 (ЧП11=ЧП23) Л (ЧП10=ЧП23)

Л (ЧП22=ЧП13) ((ЧП21=ЧП13) 0+ (ЧП20=

=ЧП13)) ..

Операция перестановки для элементов данных П13 П12 П11 П10 и П23 П22 П21 П20 дает результат П13 П12 П21

111...01 или П13 П12 II20 111...11 или П13 П11 П21 111...11 или П13 П11

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

В вычислительной технике часто встречается операция анализа возможности перестановки числовых полей и сдвигаются на размер одного поля, а освободившееся поле заполняется признаком "Пусто". С выходов блоков коррекции выделенные поля подаются на входы группы элементов ИЛИ, где объединяются и поступают на первый выход устройства. 6 ил. мены числовых полей не обеспечивает приемлемого времени обработки из-за необходимости программного анализа

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

Целью изобретения является повышение быстродействия устройства.

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

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

Устройство (фиг. 1) содержит первый

40 входной регистр 1, второй входной регистр 2, блок 3 формирования масок, первый регистр 4 маски, второй регистр 5 маски, первую группу 6 эле131742

3 ментов И, вторую группу 7 элементов

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

Блок формирования масок (фиг.2) содержит первый 11 и второй 12 элементы НЕ, второй элемент И 13, третий элемент НЕ.14, третий элемент И

15, четвертую, третью, первую, вторую, пятую и шестую схемы 16-21 срав-10 нения, первый 22 и второй 23 элементы

ИСКЛЮЧАЮЩЕЕ ИЛИ, пятый 24 и четвертый 25 элементы НЕ, первый элемент

И 26, шестой 27 и седьмой 28 элементы НЕ, элемент ИЛИ 29. 15

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

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

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

НЕ 11, значения (ЗП11=0), представляемого выходом второго элемента НЕ

12, значения (ЗП10=1), представляемого (и-1)-м разрядом первого входа блока формирования масок, значения (ЧП10Ф11...11), представляемого uuIl + 1 версным выходом второго элемента И

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

H -1 выходом третьего элемента И 15, значения (ЧП10=ЧП23), представляемого выходом совпадения первой схемы 18 сравнения, значения (ЧП12=ЧП23) O+

9 (ЧП11=ЧП23), представляемого выходом первого элемента ИСКЛЮЧАКМЦЕЕ

ИЛИ 22, значения (ЧП22=ЧП13), представляемого выходом совпадения второй схемы 19 сравнения, значения (ЧП21=ЧП13) 67(ЧП20=ЧП13), представляемого выходом второго элемента

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

ЧП12 поступает на первый вход четвертой схемы 16 сравнения с разрядов, начиная с 2п-го по (Зп-2)-й, первого входа блока формирования масок, зна-чение ЗП12 поступает на вход первого элемента НЕ 11 с (3n-1)-го разряда первого входа блока формирования масок, значение ЧП13 поступает на первые входы второй 19, пятой 20, шестой

21 схем сравнения с разрядов, начиная

131742

5 с 3 и-го по (4n-2)-й, первого входа блока формирования масок, значение

ЧП20 поступает на входы третьего элемента И t5 и второй вход шестой схемы

21 сравнения с разрядов, начиная с нулевого по tn-2)-й, второго входа блока формирования масок, значение

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

0+ (ЧП12=ЧП23) и (ЧП21=ЧП13) 0+ (ЧП?О=

=ЧП13), и на входы пятого 24, чет.вертого 25, шестого 27 и седьмого 28 элементов НЕ соответственно, выходы которых усг анавливают разряды, начиная с n-ro по (Зп-1) -й, первой маски и разряды, начиная с нулевого по (2п-1) -й, второй маски в "0" или "1" в зависимости от того, на какой схе- 35 ме сравнения зафиксировано совпадение числовых кодов (фиг.2). Остальные разряды масок устанавливаются стандартно в "0" или "1" (фиг.2) прямым и инверсным выходами элемента 40

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

Первый блок коррекции осуществляет выдачу выделенного числового поля 50 во втором элементе данных в поле П21, так как выделенное поле связи может находиться в П21 и П20, и заполнение поля П20 единицами с помощью группы элементов HE 30 (фиг. 3), которая ин- 55 вентирует значение П22, равное

000...00. Формирование на выходе первого блока коррекции поля П21 осу9

6 ществляется с помощью группы элементов ИЛИ 31, которая объединяет на своих входах поля П21 и П20 входа первого блока коррекции, так как в одном из них находятся нули.

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

П13 и П12, так как выделенное поле связи может находиться в П12 или П11.

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

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

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

НЕ, первый, второй и третий элементы

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

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

13 17429 третьего элемента И блока формирования масок, инверсный выход которого соединен с третьим входом первого элемента И блока формирования масок, (2п-1)-й разряд выхода второго входного регистра соединен с четвертым входом первого элемента И блока формирования масок, с Зп-ro по (4n-2)-й разряды выхода второго входного регистра соединены поразрядно с входами 10 первой группы первой схемы сравнения, выход "Равно" которой соединен с пятым входом первого элемента И блока формирования масок, с 3n-ro по (4n2)-й разряды выхода первого входного регистра соединены поразрядно с входами первой группы второй схемы сравнения, с (2n)-го по (Зп-2)-й разряды выхода второго входного регистра соединены поразрядно с входами второй 20 группы второй схемы сравнения, выход Равно" которой соединен с шестым входом первого элемента И блока формирования масок, прямой и инверсный выходы которого соединены соответственно с первым и вторым входами элемента ИЛИ блока формирования масок, а прямой выход первого элемента И блока формирования масок является вторым выходом устройства, прямой 30 выход элемента ИЛИ блока формирования масок соединен с 3п-го по (4n-1)-й разрядами входа первого регистра маски, инверсный выход элемента ИЛИ блока формирования масок соединен с 35

2п-го по (4n-1)-й разрядами входа второго регистра маски, причем с нулевого по (и-1)-й выходы элементов

И второй группы соединены поразрядно с первыми входами элементов ИЛИ груп- 40 пы первого блока коррекции, с и-го по (2n-1)-й выходы элементов И второй группы соединены поразрядно с вторыми входами элементов ИЛИ группы первого блока коррекции, с нулевого 45 по (n-1)-й и с 3п-го по (4n-1)-й выходы элементов И первой группы соединены поразрядно с первыми входами соответствующих элементов ИЛИ группы, с 2п-го по (4n-1)-й выходы элементов 50

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

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

НЕ блока формирования масок соединены соответственно с п-го по (2п-1)-й и с 2п-го по (3n-1)-й разрядами вхо1317429 да первого регистра маски, выходы шестого и седьмого элементов HE блока формирования масок соединены со- ответственно с n-ro по (2n-1)-й и с нулевого по (n-1) -й разрядами входа второго регистра маски, инверсный выход элемента ИЛИ блока формирования масок соединен с нулевого по (n-1)-й разрядами входа первого регистра маски, выходы элементов ИЛИ группы первого блока коррекции соединены поразрядно с вторыми входами с и-го по (2n-1)-й элементов ИЛИ группы, выходы с 2п-го по (3n-1)-й элементов И второй группы соединены поразрядно с входами элементов НЕ первого блока коррекции, выходы кото10

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

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

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

1317429

1317429

Составитель О.Берещикова

Техред А.Кравчук Корректор M..Ulapоши

Редактор А.Маковская

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

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

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

Заказ 2424/43

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