Метод вычисления функций в неавтономном режиме

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2009
Hauptverfasser:	Дичка, И.А., Жабина, В.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2009
Schlagworte:	Прикладные интеллектуальные системы
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/8205
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Метод вычисления функций в неавтономном режиме / И.А. Дичка, В.В. Жабина // Штучний інтелект. — 2009. — № 4. — С. 409-414. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-8205
record_format	dspace
spelling	irk-123456789-82052010-05-17T12:01:44Z Метод вычисления функций в неавтономном режиме Дичка, И.А. Жабина, В.В. Прикладные интеллектуальные системы Предложен таблично-алгоритмический метод вычисления функций с использованием смещенных избыточных систем счисления, который позволяет совмещать процессы поразрядного ввода аргумента и поразрядного формирования результата. Это дает возможность использования метода для неавтономного выполнения зависимых по данным операций в режиме совмещения. Показана зависимость времени вычислений от параметров систем счисления. Запропоновано таблично-алгоритмічний метод обчислення функцій з використанням зміщених надлишкових систем числення, що дозволяє суміщення процесів порозрядного введення аргументу і порозрядного формування результату. Це дає можливість використання методу для неавтономного виконання залежних за даними операцій у режимі суміщення. Показано залежність часу обчислень від параметрів систем числення. Tabular and algorithmic method for function calculation using shifted redundant numerical systems is proposed. It permits to combine processes of digit-by-digit argument input and digit-by-digit result formation. It enables to use the method for on-line realization of data-dependent operations in on-line mode. The dependence of the time of calculations on numerical system parameters is shown. 2009 Article Метод вычисления функций в неавтономном режиме / И.А. Дичка, В.В. Жабина // Штучний інтелект. — 2009. — № 4. — С. 409-414. — Бібліогр.: 4 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/8205 004.3 ru Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Прикладные интеллектуальные системы Прикладные интеллектуальные системы
spellingShingle	Прикладные интеллектуальные системы Прикладные интеллектуальные системы Дичка, И.А. Жабина, В.В. Метод вычисления функций в неавтономном режиме
description	Предложен таблично-алгоритмический метод вычисления функций с использованием смещенных избыточных систем счисления, который позволяет совмещать процессы поразрядного ввода аргумента и поразрядного формирования результата. Это дает возможность использования метода для неавтономного выполнения зависимых по данным операций в режиме совмещения. Показана зависимость времени вычислений от параметров систем счисления.
format	Article
author	Дичка, И.А. Жабина, В.В.
author_facet	Дичка, И.А. Жабина, В.В.
author_sort	Дичка, И.А.
title	Метод вычисления функций в неавтономном режиме
title_short	Метод вычисления функций в неавтономном режиме
title_full	Метод вычисления функций в неавтономном режиме
title_fullStr	Метод вычисления функций в неавтономном режиме
title_full_unstemmed	Метод вычисления функций в неавтономном режиме
title_sort	метод вычисления функций в неавтономном режиме
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2009
topic_facet	Прикладные интеллектуальные системы
url	http://dspace.nbuv.gov.ua/handle/123456789/8205
citation_txt	Метод вычисления функций в неавтономном режиме / И.А. Дичка, В.В. Жабина // Штучний інтелект. — 2009. — № 4. — С. 409-414. — Бібліогр.: 4 назв. — рос.
work_keys_str_mv	AT dičkaia metodvyčisleniâfunkcijvneavtonomnomrežime AT žabinavv metodvyčisleniâfunkcijvneavtonomnomrežime
first_indexed	2025-07-02T10:57:33Z
last_indexed	2025-07-02T10:57:33Z
_version_	1836532476514664448
fulltext	«Штучний інтелект» 4’2009 409 8Д УДК 004.3 И.А. Дичка, В.В. Жабина Национальный технический университет Украины «Киевский политехнический институт», г. Киев, Украина dychka@scs.ntu-kpi.kiev.ua, val_zhabina@mail.ru Метод вычисления функций в неавтономном режиме Предложен таблично-алгоритмический метод вычисления функций с использованием смещенных избыточных систем счисления, который позволяет совмещать процессы поразрядного ввода аргумента и поразрядного формирования результата. Это дает возможность использования метода для неавтономного выполнения зависимых по данным операций в режиме совмещения. Показана зависимость времени вычислений от параметров систем счисления. Введение При реализации последовательно-параллельных алгоритмов в параллельных вы- числительных системах можно выделить последовательность (цепочку) операций (функ- ций), которые нельзя распараллелить ввиду их зависимости по данным. Следующую операцию в цепочке можно начать выполнять только после получения результата пре- дыдущей операции. Аналогичная ситуация возникает при реализации итерационных вычислительных процессов, когда на очередном шаге вычислений используется резуль- тат, по крайней мере, одного предыдущего шага. Для ускорения вычислений в данном случае может быть использован метод неав- тономного вычисления цепочки зависимых операций в режиме частичного совмещения. Зависимые операции, принадлежащие критическому пути на графе алгоритма, выпол- няются в цепочке операционных устройств, между которыми данные передаются по- разрядно [1]. В каждом устройстве реализован метод выполнения операции, позволяющий на каждом шаге совмещать во времени ввод операндов, их обработку и выдачу одного разряда результата в следующее устройство. При таком режиме вычислений следующая операция начинает выполняться сразу после получения первого разряда предыдущей операции. За счет этого обеспечивается частичное совмещение зависимых операций, что создает предпосылки для ускорения вычислений [2]. Современные методы проектирования вычислительных систем на основе ПЛИС дают возможность на одной микросхеме создавать композицию устройств переработки информации, позволяющую выполнять одновременно операции над многими операндами. Эффективность использования ресурсов ПЛИС во многом зависит от способов обмена данными между компонентами системы. Последовательная передача данных между компонентами сокращает необходимое число внутренних и внешних связей ПЛИС, что при прочих равных условиях позволяет улучшить характеристики использования ресурсов ПЛИС. Наличие в составе ПЛИС блоков памяти дает возможность для ускорения вычисле- ния функциональных зависимостей использовать таблицы функций. Известны методы неавтономного воспроизведения функций с использованием таблиц для симметричных систем счисления с цифрами {-m,…,-1,0,1,…,m} [3]. Однако наличие цифр с отрицатель- ными знаками приводит к расширению разрядной сетки для представления промежу- Дичка И.А., Жабина В.В. «Искусственный интеллект» 4’2009 410 8Д точных результатов и к увеличению объема аппаратуры, причем как для устройства воспроизведения функций, так и для других устройств, работающих совместно с данным устройством для неавтономного выполнения цепочки операций, зависимых по данным [4]. Устранение указанных недостатков является актуальной задачей, решение которой позво- лит повысить эффективность неавтономных вычислений. Ниже предлагается таблично-алгоритмический метод, который обеспечивает воспроизведение функций в смещенных системах счисления с различными основаниями. Обоснование метода Пусть функция )(' XfY  задана в первом квадранте и является непрерывной. Функция может иметь экстремумы в области определения. Для определенности будем считать, что аргумент и функция представлены в избыточной смещенной системе счис- ления в виде:    n i i ikxX 1 ,    n i i ikyY 1 ' , (1) где }},0{, myx ii  – цифры; k – основание системы счисления. Соотношение mk  определяет избыточность системы. Учитывая, что цифры результата формируются после обработки входных дан- ных, то есть с запаздыванием, будем рассматривать функцию )(XfkY p . Здесь p – задержка в числе шагов формирования разрядов результата относительно ввода соот- ветствующих разрядов аргумента. Естественно, что для получения n разрядов после запятой функции 'Y не- обходимо сформировать pnm  разрядов функции Y . Значение функции, зависящее только от i старших разрядов аргумента, обозначим )( i p i XfkY  , (2) где iX – код аргумента, представленный i старшими разрядами. Если на каждом шаге вычислений значение iY выбирать из условия i ii p i kYXfkY   )( , (3) то на n -м шаге погрешность вычисления будет меньше nk  . Введя обозначение i ii p i kYXfkR   )(1 , (4) условие (3) можно записать в виде .10  iR (5) С учетом (2) и (4) можно заключить, что перед началом вычислений )0( i условие (5) выполняется. Предположим, что оно выполняется на i -м шаге. Опреде- лим, как обеспечить выполнение на следующем шаге условия .10 1  iR (6) Для )1( i -го шага с учетом (1) и (4) можно записать 11 1 1 1 1 1 )()(        ii i i ii ip i kkyYkxXfkR . (7) Значение функции )( 1 1   i ii kxXf представим в виде 1 1)(   i ii kXf , то есть через значение функции на предыдущем шаге и приращение, отнесенное к разряду с весом 1ik . Тогда (7) преобразуется к виду 111     ii p ii ykkRR . (8) Метод вычисления функций в неавтономном режиме «Штучний інтелект» 4’2009 411 8Д Введя обозначение 11     i p ii kkRH , (9) условие (6) с учетом (8) запишем как 11 10   ii yH . (10) Левое соотношение в (10) выполняется, поскольку функция рассматривается в первом квадранте. Для выполнения правого неравенства необходимо обеспечить вы- полнение соотношения max 1    kmk p , (11) которое получено с учетом (5) и (9). Выражение (11) дает возможность определить значение задержки p, если из- вестно максимальное значение приращения функции max в области ее определения, или определить диапазон изменения цифр избыточной системы, то есть максимальное значение m при заданном значении p . Таким образом, подбором значений p и m можно обеспечить выполнение усло- вия (3) на каждом шаге вычисления функции, что гарантирует получение результата с заданной погрешностью. Несложный анализ формулы (11) показывает, что система счисления обязатель- но должна быть избыточной ( km  ), а задержка формирования разрядов результата не может быть меньше единицы. Заметим, что увеличение диапазона изменения значений цифр нежелательно, поскольку это приводит к увеличению разрядности шины для пере- дачи цифр между устройствами. Формирование таблицы приращений Когда формирование приращений функции на каждом шаге нельзя вычислить аналитическим путем или это приводит к большим затратам времени, целесообразно использовать таблицу приращений, хранящуюся в памяти. Таблица формируется следующим образом. 1. Строится ярусно-параллельный граф перехода значений аргумента, состоящий из 1n яруса (включая 0-й). Каждая вершина графа i -го яруса соединяется дугами с 1m вершиной )1( i -го яруса в соответствии со значениями цифр аргумента },0{ mxi  , которые приписываются указанным дугам. Каждая вершина имеет обозначение i jG , где ),0( ni – номер яруса, а }1,0{  ikj – номер вершины на i -м ярусе. 2. Каждой вершине n -го яруса присваивается вес )(' n nn j XYkG  . 3. Для ярусов с номерами ni  веса вершин определяются по формулам 0),...,2(),1(, ),...,1,0\|min( ent 1 )1(              nni k mrG G i rmji j . 4. Для каждой дуги графа, соединяющей вершину i jG с вершиной 1i qG , опре- деляется приращение i j i q i q i j kGGGG   11),( . Приращениям i -го яруса придается вес ik  . Покажем, что сумма всех приращений, принадлежащих дугам каждого пути от началь- ной вершины до каждой конечной, равна значению функции для соответствующего значения аргумента в избыточном представлении. Дичка И.А., Жабина В.В. «Искусственный интеллект» 4’2009 412 8Д Пусть путь проходит через вершины n d n cba GGGGG ,,...,,, 1210 0  . Тогда сумму S прира- щений с учетом их весов можно записать в виде nn c n daba kkGGkkGGkkGGS   )()()( 121210 0 1 . Раскрывая скобки и учитывая, что 00 0 G , получим )(' n nn d XYkGS   , то есть сумма приращений дает действительное значение функции для заданного значения аргу- мента. Адрес приращения в таблице однозначно определяется дугой графа, а дуга, в свою очередь, определяется совокупностью верхнего и нижнего индексов вершины i jG , для которой дуга является входящей. Алгоритм и пример вычисления функции Для аппаратной реализации целесообразно использовать основание системы, равное ...)3,2,1(2 gg . В этом случае могут использоваться обычные двоичные аппа- ратные компоненты (сумматоры, регистры и т.д.), а умножение на величину основа- ния заменяется сдвигом. Полученные табличные значения приращений могут превышать значение макси- мально допустимой цифры m избыточной системы счисления. Поэтому алгоритм вы- числений предусматривает преобразование суммы приращений в последовательность цифр },0{ myi  . Процесс вычисления функции на каждом i -м шаге определяется формулами (8) и (9). В соответствии с формулой (9) находится iH . Целая часть этой величины яв- ляется очередной цифрой результата, то есть iy ent iH , а сдвинутая влево на один разряд дробная часть используется на следующем шаге в качестве iR . Начальным яв- ляется значение 00 R . Пусть необходимо вычислить непрерывную функцию )(' XfY  , заданную в пер- вом квадранте, с использованием смещенной избыточной системы счисления с основа- нием 4k и цифрами }4,0{, ii yx . Для представления аргумента ограничимся 3n разрядами. Полный граф в данном случае имеет 5 вершин на 1-м ярусе, 25 вершин на 2-м ярусе и 125 вершин на 3-м ярусе. Для примера рассмотрим фрагмент графа, который определяется частью таблицы значений (табл. 1). Таблица 1 – Фрагмент таблицы задания функции Значение аргумента Значение функции 2k 4k 2k 4k 0,110000 0,234 0,111111 0,333 0,101111 0,233 0,111000 0,320 0,101110 0,232 0,110000 0,300 0,101101 0,231 0,111011 0,323 0,101100 0,230 0,111100 0,330 На рис. 1 показан фрагмент графа, полученный в соответствии с приведенной выше процедурой формирования таблицы приращений. Нижняя дуга каждого разветвления соответствует цифре аргумента 0ix , а верхняя – 4ix (чтобы не загромождать рису- нок, цифры аргумента приписаны только двум дугам первого яруса). Приращения, соот- ветствующие дугам, показаны жирным шрифтом. Метод вычисления функций в неавтономном режиме «Штучний інтелект» 4’2009 413 8Д 0-й ярус 00 0 G 1-й ярус 2-й ярус 3-й ярус 33 20 0 23 30 10 20 10 2 0 1 1 2 3 41 x 01 x 2 302 13 G 21̀ 1 G 11̀ 2 G 31 0 G 11 3 G 21 4 G 202 12 G 122 11 G 102 10 G 202 14 G 3003 67 G 3233 66 G 3303 65 G 3203 68 G 3333 69 G Рисунок 1 – Фрагмент графа Для полученного фрагмента графа максимальное приращение в десятичном пред- ставлении равно 15max  . По формуле (11) определяем минимальную задержку фор- мирования цифр результата 2p . Для получения значения функции )(' XfY  необ- ходимо выполнить 5 np шагов. Для значения аргумента 234X процесс вычислений иллюстрируется табл. 2. Таблица 2 – Состояния переменных i ix i )2( kH i )4( kH i iy Микрооперация 0 – – 00,0000 0,00 – – 1 2 1 +00,0001 00,0001 00,0100 +0,01 0,01 0,10 0 суммирование сдвиг 2 3 20 +00,1000 00,1100 11,0000 +0,20 0,30 3,00 0 суммирование сдвиг 3 4 33 +00,1111 11,1111 11,1100 +0,33 3,33 3,30 3 суммирование сдвиг 4 – – +00,0000 11,1100 11,0000 +0,00 3,30 3,00 3 суммирование сдвиг 5 – – +00,0000 11,0000 00,0000 +0,00 3,00 0,00 3 суммирование сдвиг Целая часть iH , показанная жирным шрифтом, является очередной цифрой результата. После выполнения 5 шагов получено 5 дробных разрядов функции 00333,0)(2   XfkY . Начиная с третьего шага формируются разряды функции 333,0)('  XfY . Полученный результат соответствует указанному в табл. 1 значению функции для заданного аргумента. Дичка И.А., Жабина В.В. «Искусственный интеллект» 4’2009 414 8Д Заключение Предложенный таблично-алгоритмический метод воспроизведения функций по- зволяет совмещать процессы поразрядного ввода аргумента и поразрядного формирова- ния результата в смещенной избыточной системе счисления. Это дает возможность использовать метод для неавтономного выполнения зависимых операций в режиме сов- мещения, когда другие операции в цепочке выполняются также в смещенной системе счисления. По сравнению с методами, использующими симметричные системы счисления, в данном случае упрощается аппаратная реализация и уменьшается время вычислений, поскольку нет необходимости работать с отрицательными приращениями. На практике широко применяются вычислительные методы, например, численного интегрирования, цифровой обработки сигналов, вычисления полиномов, которые в ряде случаев могут быть реализованы в смещенных системах счисления. Благодаря поразрядной передаче информации уменьшается число связей между компонентами системы по сравнению с использованием методов параллельной арифме- тики. Это особенно важно при реализации систем на ПЛИС, поскольку повышает надеж- ность систем и более экономично использует ресурсы интегральных схем. Литература 1. Жабин В.И. Некоторые машинные методы вычисления рациональных функций многих аргументов / В.И. Жабин, В.И. Корнейчук, В.П. Тарасенко // Автоматика и телемеханика. – 1977. – № 12. – С. 145-154. 2. Жабин В.И. Методы быстрого неавтономного воспроизведения функций / В.И. Жабин, В.И. Корней- чук, В.П. Тарасенко // Управляющие системы и машины. – 1977. – № 3. – С. 96-101. 3. Жабин В.И. Построение быстродействующих специализированных вычислителей для реализации многоместных выражений / В.И. Жабин, В.И. Корнейчук, В.П. Тарасенко // Автоматика и вычислительная техника. – 1981. – № 6. – С. 18-22. 4. Дичка И.А. Совмещение зависимых операций на уровне обработки разрядов операндов / И.А. Дичка, В.В. Жабина // Искусственный интеллект. – 2008. – № 3. – С. 649-654. І.А. Дичка, В.В. Жабіна Метод обчислення функцій у неавтономному режимі Запропоновано таблично-алгоритмічний метод обчислення функцій з використанням зміщених надлишкових систем числення, що дозволяє суміщення процесів порозрядного введення аргументу і порозрядного формування результату. Це дає можливість використання методу для неавтономного виконання залежних за даними операцій у режимі суміщення. Показано залежність часу обчислень від параметрів систем числення. I.A. Dychka, V.V. Zhabina Method of Function Calculation in On-line Mode Tabular and algorithmic method for function calculation using shifted redundant numerical systems is proposed. It permits to combine processes of digit-by-digit argument input and digit-by-digit result formation. It enables to use the method for on-line realization of data-dependent operations in on-line mode. The dependence of the time of calculations on numerical system parameters is shown. Статья поступила в редакцию 07.07.2009.

Метод вычисления функций в неавтономном режиме

Institution

Ähnliche Einträge