Устройство для вычисления полинома Советский патент 1981 года по МПК G06F7/544 

1

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

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

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

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

Недостаток указанного устройства состоит в низком быстродействии, обусловленном последовательным выполнением шагов суммирования приращений

to и доведением результата суммирования до однорядного кода.

Наиболее близким к предлагаемому является устройство для параллельноги вычисления полинома, содержа15щее запоминающее устройство, группа выходных шин которого соединена с третьей группой входных шин первого коммутатора, группа выходных шин коммутатора содержит подгруппы вы20ходных шин, подключенных ко входам активных регистров, группы выходных шин регистров соединены с соответствуюдими входами умножителей, ыхрды регистров подключены к соответствую25щим входам второго коммутатора, группа выходных шин умножителей соединена с группой входных шин второго коммутатора, группы выходных шин регистров подключены к группам входных шин 30 второго коммутатора, первая группа выходных шин второго коммутатора под ключена к первой группе входных шин первого коммутатора, вторая группа выходных шин второго коммутатора под ключена к группе входных шин сумматоров , выходы которых соединены соот ветственно со второй и четвертой группой входных шин первого коммутатора. Третья группа выходных шин второго коммутатора подключена к пятой группе входных шин первого коммутатора. Выходные управляющие шины устройства управления подключены к управляющим запоминающего устройства первого и второго коммутаторов 3. Недостатком описанного устройства является большое время вычисления полинома. Цель изобретения - повышение быст родействия. Поставленная цель достигается тем что в устройство, содержащее блок па мяти, два коммутатора, входной комму татор, два выходных коммутатора, три регистра, сумматор и регистр результата, причем выход блока памяти соединен с первым входом входного комму татора, первый выход входного коммутатора соединен с управляющим входом первого регистра второй выход входн го коммутатора соединен с информационными входами второго и третьего регистров, выходы первого и второго регистров соединены соответственно с первым и вторым входами первого коммутатора, выход третьего регистра соединен с первым входом второго ком мутатора, первый выход второго выход ного коммутатора соединен со входом сумматора, выход которого соединен с информационным входом регистра резул тата, дополнительно введены блок управления, первый и второй преобразователи кода частичных произведений в двухрядный код, первая и вторая группы элементов И, первая, вторая и третья группы входных и первая и вторая группы выходных регистров, каждая из которых состоит из двух ре гистров , причем информационные входы регистров первой группы входных регистров соединены с выходом первого выходного коммутатора, информационные ВХОДЫ регистров второй группы входных регистров соединены с первым выходом входного коммутатора и втбрым выходом второго выходного коммутатора, информационные входы ре ri CTpoB третьей группы входных регис ровсоединены с третьим выходом второго выходного коммутатора, выходы регистров первой группы входных регистров соединены с третьим входом первого коммутатора, выходы регистров второй и третьей группы входных регистров соединены соответственно с вторым и третьим входами второго ком мутатора, первый, второй и третий выходы первого коммутатора и первый выход второго коммутатора подключены к первому, второму, третьему и четвертому входам соответственно элементов И первой группы, выходы элементов которой соединены со входами первого преобразователя кода частичных произведений в двухрядный код, первый, второй, третий выходы второго , коммутатора и первый выход первого коммутатора подключены к первому, второму, третьему и четвертому входам сОотТвётственно элементов И второй группы, четвертые выходы первого и второго коммутаторов и выходы элементов И второй группы соединены со входами второго преобразователя кода частичных произведений в двухрядный код, выходу первого и второго преобразователей кода частичных произведений в двухрядный код соединены сч информационными входами регистров со ответственно .первой и второй групп выходных регистров, выходы которых соединены соответственно с первыми входами первого и второго выходных коммутаторов, первый выход блока управления соединен со входом блока памяти, (второй - со вторым входом второго выходного коммутатора, третий и четвертый - соответственно со вторым и третьим входами входного коммутатора, пятый - со вторым и третьим входами соответственно первого и второго выходных коммутаторов, шестой - с четвертым входом второго выходного коммутатора, седьмой и восьмой - с четвертыми и пятыми входами соответственно первого и второго ко1чмутаторов, девятый - с управлякацими входами всех регистров, десятый и одиннадцатый - с шестыми и седьмыми входами соответственно первого и второго коммутаторов, двенадцатый выход блока управления соединен с восьмым входом второго коммутатора. Блок управления содержит генератор импульсов, элемент ИЛИ, счетчик и двадцативосьмивыходной элемент задержки, причем выход генератора импульсов соединен со входом элемента задержки и первым входом элемента ИЛИ, второй,, третий и четвертый входы которого соединены соответственно с четвертым, девятым и четырнадцатым выходами элемента задержки, выход элемента ИЛИ, соединен с первым входом счетчика, второй вход которого соединен с двадцать выходом элемента задержки, выход счетчика подключен к первому выходу блока управления и первому, шестому, десятому и пятнадцатому выходам элемента задержки, второй выход блока управления соединен с двадцать седьмым выходом э пемента задержки, третий со вторым, четвертый - с шестым, одиннадцатым и шестнадцатым выходами элемента задержки, пятый - с двенадцатым, семнадцатым, двадцать первым, двадцать третьим и двадцать пятым, шестой - с седьмым, седьмойс третьим, восьмой - с восьмью и тринадцатым, девятый - с двадцать восьмым, десятый - е восемнадцатым, одиннадцатый - с двадцать шестым, двенадцатый выход блока управления соединен с двадцатым, двадцать вторым и двадцать четвертым выходами элемента задержки.

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

Устройство содержит блок 1 памяти, блок 2 управления, входной коммутахор 3f регистры 4,5 и 6, группы 7, 8 и 9 входных регистров, группы элементов И 10 и 11, выходной коммутатор 12, преобразователь 13 кода частичных произведений в двухрядный код, сумматор 14, регистры 15 и 16, коммутаторы 17 и 18, преобразователь

19кода частичных произведений в двурядный код, группы 20 и 21 выходных регистров, выходной коммутатор 22, регистр 23 результата, выходы блока управления 24-35, регистры 36-43.

Блок управления содержит генератор 44 импульсов, элемент 45 задержк элемент ИЛИ 46 и счетчик 47.

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

- Р Сх)-(Co-t-x(Ci4X CC2-«-t fc3 -x {C4+x%))))} (-/;

Этот полином может быть использован для вычисления, например, функции синуса с относительной погрешностью не более 0,5- 10.

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

В исходном состоянии в блоке 1 памяти размещены значение аргумента X и коэффициенты (i 0,5). , необходимые для вычислений значения полинома. В регистрах 4-6 и 23, группах 7, 8 и 9 входных регистров, группах

20и 21 выходных регистров - нулевая информация. По сигналу Пуск генератор 44 одиночных импульсов выдает импульс, который поступает на вход элемента 45 задержки и одновременно через элемент ИЛИ 46 - на счетчик 47 для формирования адреса. Сформированный в счетчике 47 адрес и управлякяций сигнал пуска блока 1 памяти

с первого выхода элемента 45 задержки поступают в блок 1 памяти для считывания аргумента х. Прием считанного аргумента х в первый регистр 4 и во вторую группу 8 входных регистров осуществляется по управляющему сигналу, формируемому на втором выходе элемента 45 задержки и поступающему на второй вход входного коммутатор З.По управляющему сигналу,сформированному на третьем выходе элемента 45 задержки и поступающему на входы первого и второго коммутаторов 17 и 18, содержимое первого регистра 4 и второй группы 8 входных регистров передается соответственно на первый и второй входы второй группы элементов И 11, в которой осуществляется формирование матрицы частичных произведений х-х. Полученная матрица частичных произведений : поступает на входы второго преобразователя 19 кода, где сворачивается до двухрядного кода с последующей записью во вторую группу 21 выходных регистров.

, Одновременно с формированием двух-рядного кода пр011эведения ХсХ ПРОИЗВОДИТСЯ считывание констант с, с и их прием во второй и третий регистры 5 и 6 соответственно. Это осуществляется по сигналам, получае1.1ым на четвертом, пятом, шестом выходах 45 задержки. Сигналом, возникающим на четвертом выходе элемента 45 задержки, производится форьшрование в счетчике 47 адреса констант, который вместе с управляющим сигналом с пятого выхода элемента 45 задержки поступает в блок 1 памяти. Прием считанных констант С2., с 5 во второй и третий регистры 5 и 6 осуществляется по управляющему сигналу, приходящему на третий вход входного коммутатора 3 с шестого выхода элемента 45 задержки. По управлягацему сигналу, сформированному на седьмом выходе элемента 45 задержки и поступающему на вход выходного коммутатора 12, двухрядный коД произведения ХХ передается из второй выходной группы 21 регистров во втору группу 8 входных регистров. На этом заканчивается подготовительный этап. Далее начинается итерационный процесс вычисления значения полинома по формуле

Р(Х) X(Co-«-)))+)f(C3+)()),

полученной из исходной формулы (1).

Процесс вычисления значения полинома включает итерации первого, второго, третьего и четвертого вида. Сначала выполняются итерации первого вида, затем второго и т.д. По управляющему сигналу, формируемому на восьмом выходе элемента 45 задержки и поступакяцему на первый и второй коммутаторы 17 и 18, начинается выполнение первой итерации первого вида. В результате на первую и вторую группы элементов И 1Q, 11 через второй коммутатор 18 со второй группы 8 входных регистров поступает х fв виде двухрядного кода, а со второго и третьего регистров .5 и 6 через первый и второй коммутаторы 17 и 18 соответственно поступают коэффициенты с .cj. а также результаты выполнения предше ствующей итерации ( равные нулю для первоЯ итерации) из первой и. т зетьей групп 7 и 9 входных регистров. На вы-;. ходе первой и второй групп элементов И 10,. 11 получаются матрицы частичных произведений, представляющие с„Х., Cg-y., 0-х соответственно. Первая матрица частичных произведений поступает на вход первого преобразователя 13 кода, а вторая - на вход второго преобразователя 19 кода, где они преобразуются в двухрядные коды и заносятся, соответственно, в первую и вторую группы 20 и 21 выходных регистров. По сигналу, формируемому на двенадцатом выходе элемента 45 задерж ки и поступающему на входы первого и второго выходных коммутаторов 22 и 12 содержимое первой и второй групп 20 и 21 выходных регистров передается со ответственно в первую и третью группы 7 и 9 входных регистров как результат )выполнения текущейитерации. Одновременно с преобразованием матриц частичных произведений в двухрядные коды из блока 1 памяти производится считывание констант с, с и их прием во второй и третий активные регистры 5 и 6 соответственно. Это осуществляется по управляющим сигналам, формируемым на девятом, десятом, одиннадцатом выходах элемента задержки 45, Вторая итерация первого вида аналогична первой итерации и заключается в умножении результатов выполнения предшествующей итерации и коэффициентов с сд преобразования матрицы частичных произведений в двухрядный код, прием их соответствен но в первую и третью группы 7 и 9 : входных регистров как результатов выполнения текущей итерации, а также считывание коэффициентов Сд, сд из блока 1 памяти и прием их во второй и третий регистры 5 и 6 соответст венно. После выполнения всех итераций первого вида по сигналу, сформированному на выходе 33 блока 2 управления и поступающему на входы первого и Второго коммутаторов 17 и 18, начинается выполнение по двум пара.ллвль- ным ветвям одной итерации второго вида, зак.шочающейся в умножении на X результатов выполнения последней ктерации первого вида и коэффициентов Си, и с 2:;-CoX 2;, z;--c x z;iX, Выполнение итерации второго вида осу ществляется путем подачи на первую и вторую группы элементов И 10, 11 и первого регистра 4 значения х, из первой и третьей групп 7 и 9 входных регистров результатов выполнения последней итерации первого вида 2,2 и 2.,2.. из второго и третьего регистров з и б коэффициентов с о и с з соответственно. На выходах групп элементов И 10, 11 формируется многорядные коды, представляющие матрицы частичных произведений , и X соответственно, которые преобразуются в двухрядные коды с помощью первого и второго преобразователей 13- и 19 кода, заносятся в первую и вторую группы 20 и 21 выходных регистров и по сигналу, сформированному на выходе 28 блока 2 управления и поступающему на входы первого и второго выходных коммутаторов 22 и 12, принимаются в первую и третью группы 7 и 9 входных регистров соответственно. Содерхсанием каждой из трех итераций третьего вида является умножение резуль. тата предшествующей итерации на х и вычисление выражения х7(сз+х-2 (, Выполнение произвольной итерации третьего вида начинается по сигналу, формируемому на выходе 35 блока 2 управления и поступающему на вход второго коммутатора 18. По этому сигналу через второй коммутатор 18 на вторую группу элементов И 11 вьщается содержимое второй и третьей групп 8и 9 входных регистров.Катрицы частичных произведений,формируемых на выходе второй группы элементов И 11,с помощью второго преобразователя 19 кода сворачиваются до двухрядного кода и подаются во вторую группу 21 выходных регистров. А по сигналу, поступа:ющему на вход второго выходного коммутатора 12 с выхода 28 блока 2 управления, содержимое второй группы 21 выходных регистров подается в третью группу 9 входных регистров. Содержанием единственной итерации четвертого вида является получение значения полинома Р( (.,)) , Выполнение, итерации начинается по сигналу, поступающему с выхода 34 блока 2 управления на входы первого и второго коммутаторов 17 и 18. По этому сигналу содержимое первой и тре-;тьей групп 7 и 9 входных регистров, в которых содержатся, соответственно, значения X()) и X{C5+X(C4fxSJf);, поступает на входы второго преобразователя 19 кода через первый и вто рой коммутаторы 17 и 18, сворачивае ся до двухрядного кода и по сигналу поступакнцему с выхода 25 блока 2 уп равления на вход второго выходного коммутатора 12, подается на суммато 14. Полученный на выхода сумматора 14 однорядный код, представляющий значение вычисляемого полинома, записывается в регистр 23 результата ,На выходе 32 блока 2 управления фор мируется сигнал, обеспечивающий уст новку в исходное нулевое состояние всех регистров. Таким образом, предлагаемое устройство позволяет повысить быстродействие. Действительно, время вычи ления полинома в известном устройст ве равно 8Ы5 К тг+71у +31сд . Г 1, t - время выборки из блока где памяти; -время задержки в коммута торе; -время срабатывания тригг ра; -время умножения в умножи теле , -время сложения в суммато ре. Принимая , , получим -r-.fijt +7t +3t П -П где t - время задержки в элементе Таким образом ,,«+3tc Время вычисления полинома в пред лагаемом устройстве определяется с отношением T,4tB,+20t +20Vr+7tn+8 +V где t-..- время преобразования мно горядного кода в двухрядный . Принимая также t, tn, ,2t „ И ЬПАЛК 20ь„ , получим Ty 231tn + t ch . Выигрыш во времени определяется от ношением Т 64 .ta+rta J tc . 231tn + t Полагая время умножения равным t, i(m-1)tc (m г разность операндов а время сложения для сумматора со сквозным переносом равным t 2ty, (m-1)+4tf,, п олучаем T 14mSn+70tj,-8mtn , Tv 233trt+2mtn / Тогда выигрыш, достигаемый при выч лении полинома при vn 32 разрядам получается равным LI Тп 14150tn „Л1 W -s: - -т-гттг 47 Т,, 297tn Бели использовать сумматор со сквозным групповым переносом и одновременным переносом внутри группы то -СА ) разрядов вгруппе Принимая Е 4, получаем W In 4 24jtn,,,g TV 249tn Формула изобретения Устройств.о для вычисления полинома, содержащее блок памяти, два коммутатора, входной коммутатор, два выходных коммутатора, три регистра, сумматор и регистр результата, прнчем выход блока памяти соединен с первым входом входного коммутатора, первый выход входного коммутатора соединен с управляювгим вxoдo i первого регистра, второй выход входного коммутатора соединен с информадионными входами второго и третьего регистров, выходы первого и второго регистров соединены соответственно с пёр-. вым и вторым входами первого коммутатора , выход третьего регистра соединен с первым входом второго коммутатора, первый выход второго выходного коммутатора соединен со входом cy iмaтopa, выход которого соединен с информационным входом регистра результата, отличающееся тем, что, с целью повьяаения быстродействия, в него введены блок управления, первый и второй преобразователи кода частичных произведений в двухрядный код, первая и вторая группы элементов И, первая, вторая и третья группы входных и первая и вторая группы выходных регистров, каждая из которых состоит из двух регистров, причем информационные входы регистров первой группы входных регистров соединены с выходом первого выходного комл утатора, информационные входы регистров вто-:: рой группы входных регистров соединены с первым выходом входного коммутатора и вторым выходом второго выходного коммутатора, информационные входы регистров третьей группы входных регистров соединены с третьим выходом второго выходного коммутатора, выходы регистров первой группы входных регистров соединены с третьим входом первого коммутатора, выходы регистров второй и третьей группы входных регистров соединены соответственно со вторым и третьим входами второго коммутатора, первый, второй и третий выходы первого коммутатора и первый выход второго коммутатора подключены к первому, второму, третьему и четвертому входам соответственно элементов И первой группы, выходы элементов которой соединены со входами первого преобразователя кода частичных произведений в двухрядный код, первый, второй, третий выходы второго коммутатора и первый выход первого коммутатора подключены к первому, второму, третьм и четвертому входам соответственно элементов И второй группы, четвертые выходы первого и второго коммутаторов и выходы элементов И второй группы соединены со входами второго преобразователя кода частичных произведений в двухрядный код, выходы первого и второго преобразователей кода частичных произведений в двухрядный код соединение информационными входами регистров соответственно первой и второй групп выходных регистров, выходы которых соединены соответственно с первыми входами первого и второго выходных коммутаторов, первый выход блока управления соединен со входом блока памяти, второй - со вторым входом второго выходного коммутатора, третий и четвертый - соответственно со вторым и третьим входами входного коммутатора, пятый - со вторым и третьим входами соответственно первого и второго выходных коммутаторов, шестой - с четвертым входом второго выходного коммутатора, седьмой и восьмой-с четвертыми и пятыми входами соответственно первого и второго коммутаторов, девятый - с управлякмдами входами всех регистров, десятый и одиннадцатый - с шестыми и седьмыми входами соответственно первого и второго коммутаторов, двенадцатый выход блока управления соединен с восьмым входом второго коммутатора.

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

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

Источники информации, принятые во внимание при экспертизе

1.Авторское свидетельство СССР 474811, кл. G Об F 15/34, 1975.

2.Авторское свидетельство СССР 616638, кл. G 06 F 15/34, 1978.

3.Пьявченко О.Н., Сурженко И.Ф.1 РОММ Я.К., Метод распараллеливания схемы Горнера и его приложение к цифровым вычислительным устройствам. Автоматика и вычислительная техника, 1978, вып.5, с.73-78 (поототип).

9,1,2