автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Кратные логические вычисления и их применение при моделировании дискретных объектов

РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт проблем управления

На правах рукописи

Выхованец Валерий Святославович

КРАТНЫЕ ЛОГИЧЕСКИЕ ВЫЧИСЛЕНИЯ И ИХ ПРИМЕНЕНИЕ ПРИ МОДЕЛИРОВАНИИ ДИСКРЕТНЫХ ОНЬЕКТОВ

. Специальность: 05.13.13 - Вычислительные машины, комплексы, системы и сети! 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва, 1998

Работа выполнена в Институте проблем управления РАН.

Научный руководитель:

доктор технических наук, профессор В.Д. Малюгин.

Официальные опоненты:

доктор технических наук, профессор Н.Г. Топольский, кандидат технических.наук А.И. Потехин.

Ведущая организация:

Институт проблем передачи информации РАН (г. Москва).

Защита состоится 1998 г. в 11.00 на заседании

диссертационного совета Д002.68.01 Института проблем управления по адресу: 117806, г. Москва, Профсоюзная, 65.

С диссератцией можно ознакомиться в библиотеке Института проблем управления.

Автореферат разослан 5 марта 1998 г.

Ученый секретарь диссертационного совета, к. т.н.

Е.В. Юркевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

^туальнос'ть_„темЫ--- Для таких задач, как' управление сложными объектами, обработка изображений и распознавание образов, принятие решений, дискретная оптимизация, моделирование дискретных устройств - основная проблема ополитея к обработке бинарных и многозначных (логических) данных и заключается в эффективном вычислении (реализации) логических функций.

Традиционная архитектура ЭВМ не предусматривает специализированных средств для логических вычислений. Поддержка логических вычислений сводится • к булевым Операциям, выполняемым арифметико-логическим устройством (АЛ') - на аппаратном уровне, и к командам условного перехода - на уровне программ.

Известна реализация логической обработки данных посредством параллельных логических вычислений, когда одновременно вычисляется система логических функций на одном наборе переменных, со сменой переменных вычисления :'^вторяпгсл. Наименее изученными остаются вопросы, ■-.вязанные с разновидностью параллельных логических вычислений - кратными вычислениями, когда одновременного внчисляртсп несколько значений одной или системы логических функций на разных наборах ее аргументов. Величина кратности ш пежит гз диапазоне от 1 до 2П, где п - 'число аргументов, что означает соответственно однократные и полнократные логические вычисления.

Кратнно логические вычисления возникают при параллельном управлении несколькими одинаковыми объектами, находящимися в разных физических состояниях; при моделиро-г-атш ( рог произведении) системы на нескольких входных в'^лейстк» <, например вычисление модели при тестировании и технической диагностике дискретных устройств; в системах упг«ч!!<-'!п:ч, где т^б^етоя быстрая реакция на изменение внешних, условии, можно с упреждением просчитать нужные действия на возможных (вероятных) входных наборах, напри-

мер, находящихся на единичном расстоянии по Хемыингу от текущего, и при поступлении нового набора уже иметь нужную реакцию.

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

Целью работы является разработка и исследование методов кратных логических вычислений и их эффективная техническая реализация. Для достижения данной цели решаются следующие задачи:

1) разработка средств формального описания кратных вычислений;

2) обоснование методов кратных вычислений и исследование их эффективности;

3) техническая реализация кратных вычислений на современных вычислительных средствах.

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

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

Практическая ценность полученных результатов состоит

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

Внедрение результатов исследования проводилось в рамках научно-исследовательских работ и опытно-конструкторских разработок, выполненных в 1993-1997 гг. в научно-исследовательской лаборатории "Математическое моделирование" Тираспольского университета. Результаты исследования приняты к реализации в АО "Электромаш" (г. Тирасполь) и используются в учебном процессе.

Апробация работы. Основные положения диссертации докладывались и обсуждались на научно-технических конференциях профессорско-преподавательского состава Тираспольского университета (1994-1997 тт.), на расширенных семинарах 3] лаборатории Института проблем управления (19951997 гг. ), Всероссийской конференции "Информационно-управляющие системы и специализированные вычислительные устройства для обработки и передачи данных" (Махачкала, 1996 г.), на семинаре кафедры ИУ-3 МГТУ им. Н.Э. Баумана (1997 г. ).

Публикации. По теме диссертации опубликовано б работ.

Структура и объем диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 123 наименований и двух приложений, изложена на 173 страницах машинописного текста и иллюстрируется 21 рисунком и 7 таблицами.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, сформулированы цель и задачи исследования.

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

Показано, что современное состояние информационной технологии характеризуется принципиальным изменением роли логической обработки данных. Решение логических задач формализуется в алгебре логики и реализуется в виде системы логических функций в конечно-автоматном виде (рис. 1), где X - вектор независимых переменных (входное воздействие), Г - вектор наблюдаемых значений (состояние выхода), о -вектор внутренних переменных (состояние объекта), о+ -вычисляемое следупцее состояние, г - система логических функций.

У X

---------- = г ........

О

Рис. 1. Логическая обработка данных

Логическая обработка данных разделяется на задачи синтеза, моделирования, анализа и вычисления (табл. 1).

Таблица 1

Задача Исходные данные Результат

Вычисление X, 0, Т? У, 0+

Анализ у, 0*- X, 0

Синтез X, 0, У, о+ Г

Моделирование X, У Т, 0, О4"

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

логическому синтезу и кратным лотческим вычислениям.

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

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

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

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

Введены критерии эффективности кратных вычислений: эффективность по времени вычисления эффективность по сложности вычисления 11 (обратно пропорциональна аппаратным

затратам ут) и комплексная эффективность 8=4 ■ л, определяемые относительно однократного случая. К параллельным вычислениям во времени отнесены такие методы, при реализации которых комплексный критерий эффективности 8 больше единицы, а исходные данные (результаты) вычислений подаются (снимаются) одновременно.

Таблица 2

Во времени

П о с л е д о в а т

.(1)

.(2)

(1*1)

-( 1)

и+1)

.(2)

а+2)

5-1,. 1,-1, 8=1

В пространстве

Х(1)(Ь)

с!=2

К, р,

1 2

АЪ АЪ

К

У111^!)

5=ат/(п1-1), ч=1, 8=<±п/(га-1)

П а

Р а л л е л ь н о

X<Z1(t)

р

'дъ

Y(1'(t+Дt)

У,2>(Ь+Д1;)

Х(2>(1:)

а=ш/у АЬ

т=2

У,2)(Ъ+1) -->

£=т, ч=1/т, 8=1

Современные высокопроизводительные системы обработки данных анализируются на трех уровнях: крупноблочном (программном), среднеблочном (командном) и мелкоблочном (операционном), отличающихся мерой крупности операций обработки. Показано, что наиболее распространенными методами структурной организации кратных вычислений являются повторение, конвейеризация и распараллеливание.

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

ченной совокупности (кортеже) логических функций, наборов переменных и их ортогонального объединения; Традиционная реализация одной булевой функции вида :£(Х)=У представлена как операция

£<ХЦ) )=Уа), 1=0, 2п-1, что означает нахождение значения функции У'1) при подстановке в последнюю аргумента X11>. Более сложный '-пучай - параллельные логические вычисления над полиномом Р(У)-У, что означает операцию

Р(Х(1) )= * У!*1, >1 3

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

Кратные вычисления функции £(X)=У определены как

< щерация

г(Лх(11)=5

1=1 1=1

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

И наконец, вычисление системы я функций с кратностью т, представленных в некоторой форме описания Р(Х)=У, означает операцию

1=1 3=1 1=1 3

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

Во второй главе исследуются формы представления и методы реализации кратных вычислений в булевой алгебре. Рассматривается алгебра поразрядных логических операций Фга, в которой значения логических данных интерпретируются как числа в двоичной т-разрядной позиционной системе счисления.

Доказывается изоморфизм между алгеброй Фт и булевой алгеброй В2. Это позволяет интерпретировать формулы В2 в Фт, причем при т=1 Фт вырождается в В2.

Показывается, что кратные вычисления системы функций ^(Х^, Хх, Х0), Хи £^{0, 1}, (3=0,

могут быть описаны в замкнутом классе функций к-значной логики, порождаемом функционально полной в Фга системой операций:

(I, Х^Х-}, Х1+Х3, Х^Х,), где-1 - логическая единица, 1=2"-1; Х1, Xje{0, ..., I}; 0 -некоторая поразрядная булева операция (конъюнкция, дизъюнкция, неэквиваленций); +• (-) - арифметическое сложение (вычитание). Для этого каждая функция представляется в виде арифметико-логического полинома р^ (например в конъюнктивном базисе):

2п-1 2а-1

I I

1=0 ■ 1=0 где а^ - 1-ый коэффициент полинома для ;)-ой функции, а^й, Ъ - множество целых чисел; вА(Х) - логическая часть полинома; 1=(1П_1 ... 1! 10 > 2 - двоичное представление числа 1. Определение степенной операции задано следующим образом:

I, при з=0, т.е. переменная Х1 не входит в 01(Х); при з*0, т.е. переменная входит в 01(Х).

Объединение pj производится с помощью производящей функции 4-1

Р(Х)= I р (Х)-(1+1)Э, (1+1)°=1. j=0 .

После приведения подобных слагаемых получается арифметико-логический полином в алгебре Фт: 2"-1

Р(Х)= £ А^Х), [

1=0 j=0 при вычислении которого реализуются кратные вычисления.

Для определения затрат на представление полинома

оценивается диапазон изменения его коэффициентов

.............л.ГЛЦ'Уг--,.......: ...........

где е(1) - когогтество единиц в двоичном представлении 1, и опре-деляются информационные характеристики: емкость Тр и энтропия Яр:

2п-1 I

1= Г 1од.(2|А.|+1), [Сиг], [бит/коэф.].

1.0 2" Рассматриваются процедуры кратных вычислений, для которых операционным элементом является АЛУ, а аппаратные затраты определяются информационной емкостью полинома. 'Комплексная эффективность процедур больше единицы, но ее асимптотическое поведение при увеличении кратности (9 стремится к единице) позволяет заключить, что вычисление полинома в алгебре Фт реализует параллельные в пространстве кратные вычисления.

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

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

1=0

где а; | - .1-ый коэффициенты для ]-й функции; » - логические операции; - переменная Х; в степени

1-(!„_! ... 10)к - к-ичное представление 1. Синтез полиномиальных форм рассмотрен в гл. 4.

Для объединения функций р^ на наборах переменных Х(г) полином записывается для всех т наборов:

kn-l _

Pj(X<")= I a^f^i,,-...«)/ -1).

i=0

и полученные выражения объединяются в виде взвешенной суммы с коэффициентами кФ <г > ^1, порожденными весовой функцией j):

m-1 q-1 kn-l

. P(X)=£ I k<p<r'J,{ I a e^x'i')}. r=0 j=0 i=0

Для обеспечения ортогональности объединения на вид весовой функции накладывают ограничения. Дискретная функция Ф называется весовой, если в различных точках области определения ее значения различны. Она задает размещение значений функций на разных наборах переменных в разрядной сетке: • номер k-ичного разряда, в котором располагается значение j-й функции Pj от г-го набора переменных Х<г> равен ф(г, j).

В результате представления весовой функции в виде суммы двух функций ц и о: <p(r, j)=n(r)+o(j), выводится выражение

кп-1

Р(Х)= £ и),

i=0

q-1 m-1

где Xt(o)-£ ku,i,a1Jf a S^X, ц)= £ к^(г>в.<Х(г>), которое

j=0 r=0

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

Комплексная эффективность кратных вычислений оценивается следующим образом. Для однократного случая необходимо кЛУ с разрядностью не меннее q, время вычисления равно з(-с(п)+1х+т+), где з - вычислительная сложность полинома (количество ненулевых коэффициентов); t(n) - среднее время вычисления логической части Oj; (тх) - время

выполнения _ сложения (умножения). Для последовательных н-времени кратных вычислений разрядность А тт.*- равна q-m, а комплексная эффективность определяется как

ms(T(n)+xx+T ) mt(n) T(n)

5=-----------------* ... , t|= -í- -1/m, ,

S(l(n)Kx+T ) T(n) Ф* t (li I

где т(п) - среднее время вычисления 0j (кратный случай). Той же величине равна и комплексная эффективность параллельных в пространстве кратных вычислений.

Анализ последнего выражения показал, что ллч реализации парад-лельных во времени кратных вычислений следует уменьшать аппаратные затраты vm (см. табл. 1). Для таких вычислений в пространстве необходимо обеспечить равенство времен т(п) и т(п), что достигается путем использования поразрядных.операций при вычислении полинома: kn-l ~ - ..

Р(Х)= I i=0

q-1 ш-1 m-1

где А.= у ku' j'а. ., X - Г k»lmX. , i - Г к»"11 i .. При

i L и' j L ]J ' i L i r

j=0 r=0 r=0

ц=г и u=mj получают полином в алгебре Фт. Последнее выражение может быть минимизировано путем выбора различных весовых функций. Исследован случай, когда кратность вычислений изменяется от вычисления к вычислению и найдрна форма, коэффициенты которой не зависят от кратности. В этом случае весовые функции имеют вид: n(r)=-qr, i>(j)-j.

Для абсолютной оценки эффективности кратных вычислений рассмотрен табличный способ реализации k-значной функции. Последний определен ^ак самый быстродействующий, что тррбупт т.,—<7 операций выборки из памяти, а его аппаратные затраты v,-qkM соответствуют пГуыму памяти для хранения таблицы истинности. Для абсолютной комплексной эффективности подучено внрагснип

где R - {\1зрпдность А.ЛУ, я - вычислительная сложность

полинома, Нр - его информационная энтропия, т(п) - среднее время вычисления Ё^. Абсолютная эффективность 8а не зависит от кратности, а ее повышение возможно как путем увеличения разрядности Я, так и за счет уменьшения энтропии Нр, что достигается минимизацией коэффициентов формы.

Проверка эффективности кратных вычислений осуществляется путем сравнения сложности полинома з с эффективной сложностью

<£Усп

Нр(1+Нр+Т(п))

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

эф 0,8

0,6

0,4

0,2

0,0

к=2

к=3

к=5

3 4 5 б п

Рис. 2. Эффективная вычислительная сложность полинома

В четвертой главе рассматривак/гся аналитические методы синтеза полиномиальных форм и исследуется син л. < форм вида:

к"-1 ки-1

р(х'= I а1(сА<гЛ-1 ••• 5<А>"Ь Е аА(Хь 1=0 !=-,() где а^ - коэффициенты формы; с1 - некоторые произвольны!.'

константы; - логические операции; Х^ - переменная Х1 в логической степени 1,; ±-{±п_1, ..., - к-ичнос

представление числа 1; 01(Х) - полиномиальные ортогональные функции. Порядок выполнения операций справа налево с приоритетом возведения в степень, а сами операции таковы, что область значения предыдущей операции совпадает или включается в область определения следующей.

Методика синтеза полиномиальных форм основана на дискретном ортогональном преобразовании:

^пЧА,

где Р - характеристический вектор функвди, А ■ вектор коэффициентов формы, О и 0~! - матрицы прямого и обратного преобразования размерности кпхкп. Последние попучат1 следующим образом:

1). Задается ядро, которое определяет степенные операции и соответствующие матрицы VI ь размерностью кхк с плементами

.1)-=оА (I, ) !1, к-1, Ь=б, 'п-1), где х (3) - номер стрбки (столбца). Отроки (столбцы) матрицы должны быть линейно независимы;

2). Строится матрица Р"1 по рекуррентному правилу:

"'ЧДА-!' <^0, П-2),

где - обобщенная операция кронекеровского произведения; С,! - матрица констант, Состоящая из к11 одинаковых строк к" произвольных констант из области определения 6ц. Операция обобщенного кронекеровского произведения определена следующим образом:

«^<0,0)8^ ^(1,0)8^

V (1,1)8^

1,1)^(3,

где I - лох'ическая единица алгебры, 1=к-1. Выбор операций и их последовательности не должны вести к линейной зависимости строк (столбцов) а константы сх задаются так, чтобы ощ^еделитель О"1 был отличен от нуля;

3). Матрица И определяется из условия ортогональности: 0хР-1=Е, где Е - единичная матрица размерности кпхкп.

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

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

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

(к

л-1

•к0)-1

Р.,(Х) =

Г а , [с 8 Х1""18 , ... бХ°1.

и 1 п п-1 п-1 0 0;

1-0

ядро преобразования строится с учетом значностей к, иг.ц-меншгх Xi( а операции 8 ¡задаются при. различной знача: у/ч и операндов. Ортогональное о&ьедмнение функций p-j со анлчн'. тями kf. осуществляется с помощью производящей функции: q-1 j-1

Р(Х) = f Pj(X) Ц kft, Pj(X)e(0, 1, ..., k£j-H. j=0 t--0

Исследована зависимость эффективности rio времени i/i вида аналитической конструкции. Эффективность аналитической конструкции у определяется отношением времени вычисления полинома в булевой алгебре к времени вычисления пгнщномл хг при сметанной значности:

Tl Sxd+Tj)

Г=-

з2(1+т2)

где з1( з2 - вычислительные сложности полиномов; I,, '¿г -средние времена вычисления логической части. Для произвольной таблицы логических данных построены оптимальные аналитические конструкции (табл. 3). ("метанная значн'яч-функций, в свою очередь, уменьшает -"энтропию полинома т ■ уменьшения значений коэффициентов.

Таблица 3

Длина таблицы

8 9 10

11 12

13

14

15

16 17 1R 19 ¿0 ?1

'Значность переменных k j

(2, 2, /)

(3, 3) (2, 5)

(2, 2, 3) (2, 2, 1) (2, 7)

7)

2, 2, 2)

2, 2, 2)

3, 3)

3, 3)

(2,1 2, 5)

(2,12, 5) (3,17)

(2, (2, (2,

(2,

(2,

1.000 1.454 1.54а 1.200 1.200 1.0GG 1.066 1.000 1.000 1.493 1.493 1.555 1. 555 1. 317

Пятая, заключительная глава посвящена вопросам технической реализации кратных вычислений.

Любая реализация лотческого вычисления предполагает

'! .и-, y. оптимальиих форм представления логических данных. • ;пн< :ывается комплекс прадрамм для логических исследований, < i*.-'гоящий ич следующих программных средств: LOGIC начисление характеристических векторов; BACK - обращение M-vrpiui; CRON - обобщенное кронекеровское произведение натрии; РЕТ - вычисление определителей; MUL - умножение матриц; RANDOM - генеращ-м псевдослучайных матриц; GEN -г—н^шщя степенных операций; MEMORY - подсчет информационной емкости матрицы; SPECTR1 - минимизация информационной энтропии полинома; SPECTR2 - минимизация вычислительной сложности полинома. Использование комплекса программ основано на методике синтеза полиномиальных форм (гл. 4).

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

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

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

кратности. ~ ----------- .........

Реализация перечисленных припиши ж < ,> уще1 .тип^нн > разных этапах проектирования. Виртуализаций иычисщггельн'Ч' средства осуществлена на этапе проектирования I тгшдарп. ч"~ программного обеспечения; отражение формы в г тру 1 туру вычислительного средства и ее инвариантность при изменении кратности реализованы на этапе создания библиотеки классов, а синтез и мидамизация осуществляются на этапе проектирования прикладной программы.

Программные средства кратных вычислений представп^чп т> виде библиотеки классов (рис. 3).

Производные классы прикладных программ

Рис. 3. Иерархия классов для кратных вычислений

Основу иерархии составляет класс ARRAY, обеспечивают«' работу с динамически выделяемыми областями оперативной памяти. Класс INTEGER реализует целые числа с управляемой разрядность представления, а класса MATRIX - целочисленные матрицы с переменной размерностью. Завершает иерархию класс POLINCM, выполняющий кратные вычисления. Класс C0EFTC1 Ftrr является базовым для класса POLINOM и реализует однонаправленный список объектов INTEGER, Двойной линией показаны связи между базовыми и производными классами, а одинарной . связь между взаимодействующими классами.

Рассмотрена рл пмзация кратных вычислений на мелкоблочнпм уровне в мультипликативной форме. Приведена структур! логического процессорного элемента при последовательном вычислении полинома (рис. 4), включавшая нлкапли-гавдий сумматор (£, RG), блок определения степенных ortepa-

unit P, блок коэффициентов А, блок возведения в степень X1, мультипликатор MUL, мультиплексор МОХ и блок номеров коэффициентов I. Разрядности данных имеют следующие значения:

п-1 q-1

r.=]log2k.[, r=£rj/ gt=]log2kft[, g= [ gfc, j=0 t=0 где r( (kj) - разрядность (значность) j-ой переменной, gt (1:(t) - разрядность (значность) t-ой функции, r (g) разрядность входных (выхбдных) данных. Здесь ]х[ обозначает наименьшее целое, большее или равное х.

D---

X

X

1

Y1 n MITT, 1 MUX

1 '

ч-

RG

9о

q-i

* Y

q-l

Рис. 4. Последовательное вычисление полинома

В каждом такте блок I выдает номер текущего коэффициента, который используется блоком Р и X1 для возведения входных переменных в соответствующие степени, а блоком А - для выборки требуемого (очередного) коэффициента. На выход блока МОХ подается коэффициент из блока А только при неравенстве нулю результата вычисления в блоке М1Л/, на вход которого подаются значения степеней входных переменных. Блоки памяти Р и А организованы в виде очереди, что позволяет параллельно с обработкой загружать по шине Б очередные значения. Пропускноая способность тины Н должна удовлетворять условию:

п-1

Н й Нр+(п+1) I 1°д2кг >0

При отказе от параллельной подгрузки данных получаются минимизированные конструкции блоков . Р и А для жестко

g

заданной системы функций. o»c;4Jtwiv ижл-ом Р, l ч Л ь • и

I]) чае 'этим,Ult-'H I H:i ¡•»Vj^ny ||.;м,Н!1 • i. fnii-ьг и- ! и I

и =- г ("'■•'' У• м, г' У, м,---т, -и>- ' ' ' ¡'о

На рис. 5 представлена структура л^гпч^ к.. прои«> >•• иг«! - • •iitcMc-iipa ttpt! п.1|>>ч1»-'1ЬН';м ьм-ик >г mm •>• мш . ма. В ОТЯИЧИе ОТ rik'te.liU.Hi.iHCÜ ЛИ'" I, Ol''.'yi'.

Слз1" Т, р,"!и'-л--ни(:> производится за один такт и подгрузка силъряшого Г. йогов Р и А иоушеих'шшотся злблаговремимнч. Расположив меаду блоками X1, MUL и MUX буферные регистры получают процессорный элемент для конвейерной обработки > комплексной эффек тикног.тьм 9~-1.

D ----

Т.

М7Т

А

' М.

[ ' X ч f X - [ X' з-п иш, MUX

*»-1 :'n L ^ 'ь }

h^g h

Рис. 5. Параллельное вычисление полинома

Ддя "пространственно!« распа^ллелиплния вычислении устройства на рис. 4 и рис. 5 дублируют. Если блоки Р, I и А сделать общими для ivex каналом, -щ pai чае« ¡Ш'ливани^ осуществляется во времени и комплексна« зффгкгинн'чч f больше единицы (аппаратные затраты растут медленнее кратности). Для структуры на рис. 5 реализовано совмещение двух чего дел* кратных вычислений: параллельного во времени и ¡юо'лрдолателыюга н пгюфчвнеггве, что ;Л">онечиБлет компп^ь• :чуч --Фиктивность, рНянуг) произведению эффективнеллел калдчт из методов.

На среднеблочном уровне реализация кратных вычислений осуществляется в рамках архитектурных принципов построения' процессоров. В состав процессора вводится несколько опера-

цпонных устройств, в том числе и требумцих более одного глкта для обработки данных. Занятость устройства, разделяемо«) между процессами или командами вызывает контекстное переключение процессора. Каждое разделяемое устройство, в гон числе и участвующее в образовании мультиплексного конвейера или/и построенное по конвейерному принципу, по •завершении обработки вызывает контекстное переключение на процесс, ожидающий результат. При этом у компилятора появляется возможность генерации кода параллельных вычислений как на уровне процессов, так и на уровне команд. Для уве-пнчения быстродействия путем параллельной в пространстве обработки данных предлагается использование нескольких однотипных операционных устройств. Если при этом дублировании существуют общие блоки, то реализуются параллельные во времени кратные вычисления.

В заключении подводится итог выполненных

исследований и делаются вывода по работе в целом.

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

2. Проанализирована эффективность кратных вычислений и найдено: дня оценки эффективности необходимо использование абсолютных и относительных критериев эффективности: по времени вычисления, по сложности вычислений и комплексной; абсолютная комплексная эффективность не зависит от кратности, а ее повышение возможно как путем увеличения разрядности &ЛУ, так и при уменьшении энтропии полинома; синтез форм представления может быть осуществлен в расширенной базисе операций и при смешанной значности переменных и функций.

3. Разработаны принципы реализации кратных вычислений

и показано: эффективная реализация крат1шх вычислений возможна на трех уровнях вычислительных средств: программном, командном и операционном; на программном уровне крат ные вычисления позволяет? интенсифицировать исиолььовашш вычислительных средств, а на командном и операционном уровне совмещение методов структурной организации кратны* вычислений обеспечивает наибольшую ¡эффективность.

Основные результаты диссертации опубликованы в работах:

1. Выхованец B.C., Гордиенко К.П. Процессор с сокращенным набором команд // Вестник Приднестровского университета. Тирасполь, 1994. № 1. С. 124-128;

2. Выхованец B.C. Многократные параллельные логические вычисления // Информационно-управляющие системы и специализированные вычислительные устройства для обработки и передачи данных: Труды Всероссийской конференции Махачкала, 1996. С. 105-106;

3. Выхованец B.C. Кратные, логические вычисления и их применение в управлении, обработке информации и других областях / Приднестровский государственно-корпоративный, университет им. Т.Г. Шевченко. Тирасполь, 1997. 18 с Деи, в ВИНИТИ 5.6.97, № 1851-В97;

4. Выхованец B.C. Дискретное преобразование Фурье и его применение при логических вычислениях / Приднестровский юсударственно-корпоративный университет им. Т. Г. Шевченко. Тирасполь, 1997. 15 с. Деп. в-ВИНИТИ 5.6.97, И 1852-В97;

5. Выхованец B.C. Многократные параллельные логические вычисления // Вестник Приднестровского университета. 1997. № 2. С. 64-74;

6. Малюгин В.Д., выхованец B.C. Кратные логические вычисления // Автоматика |и телемеханика. 1998. № 4.

_Личный j3KJiafl,_ Все научные результаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работы, выполненные в соавторстве, внесен следующий вклад: в [ 1. ] - предложен способ взаимодействия операционных устройств; в [б] -" арифметико-логическая форма предсташюния кратных вычислений. -

М w w 2.4