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

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

Тютюнов Дмитрий Николаевич

ПРОДУКЦИОННАЯ АЛГОРИТМИЧЕСКАЯ СХЕМА И ' УСТРОЙСТВО СУММАТОРА МАССИВА ЧИСЕЛ В

ЗНАКОРАЗРЯДНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

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

Курск - 2006

Работа выполнена в ГОУ ВПО Министерства образования и науки РФ «Курский государственный технический университет» на кафедре «Программное обеспечение вычислительной техники»

Защита диссертации состоится "27" апреля 2006 г. в14°° часов на заседании диссертационного Совета Д 212.105.02 при Курском государственном техническом университете по адресу: 305040, г.Курск, ул.50 лет Октября, 94.

Заверенные отзывы на автореферат в двух экземплярах направлять по адресу: 305040, г.Курск, ул.50 лет Октября, 94, ученому секретарю

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан марта 2006г.

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

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

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

доктор технических наук, профессор Лопин В.Н. кандидат технических наук, Онучин М.Я.

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

ОКБ «Авиаавтоматика» г. Курск

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

^ ЕТА. Титенко

zoo e a

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

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

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

Вопросам скоростной обработки числовой информации посвятили свои работы Каляев A.B., Марков A.A., Бойков В.Д., Смолов В.Б., Бандман O.A., Ачасова С.Н., Kung N.T., Book R.V. и другие отечественные и зарубежные ученые.

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

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

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

Работа выполнялась в рамках госбюджетных НИР по гранту Г02-4.2-5 «Методы системно-структурной органи ва процес-

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

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

Поставленная цель достигается решением следующих задач:

1. Создание схемы продукционного алгоритма для выполнения операций сложения массива чисел в формате с фиксированной точкой в ПЗСС.

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

3. Синтез элемента структуры сумматора и реализация его структурно-функциональной организации.

4. Исследование скоростных характеристик алгоритмов и сумматора, а также определение уровня аппаратных затрат.

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

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

Методы исследования основаны на положениях конструктивной математики, методах современной теории алгоритмов, теорий конечных автоматов и проектирования ЭЦВМ.

Научная новизна заключается в том, что впервые получены следующие результаты:

1. Разработана новая форма представления продукций, отличающаяся заданием образцов и модификаторов в виде двухмерных конструктивных объектов, что позволяет использовать методы обработки символьной информации для сложения массивов чисел, заданных в ПЗСС.

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

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

4. Синтезирован элемент однородной структуры и осуществлена системно-структурная организация конвейерного сумматора, сокращающего затраты времени на суммирование в 8 раз по отношению к устройству аналогу

за счет попарно параллельной обработки операндов массива чисел в ПЗСС с одновременным формированием переносов в старших разрядах и бит суммы в младших разрядах.

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

Апробация результатов работы. Результаты работы отражены в докладах на научных конференциях: V Научно-техническая конференция с международным участием «Материалы и упрочняющие технологии-97», Курск, Россия, 1997 год; Международная техническая конференция «Медико-экологические информационные технологии», Курск, Россия, 1998 год (2 доклада); I Всероссийская научно-техническая конференция, часть {II «Компьютерные технологии в науке, проектировании и производстве», Нижний Новгород, Россия, 1999 год (2 доклада); VIII Международная научно-техническая конференция «Физические и компьютерные технологии», Харьков, Украина, 2004 год (2 доклада); Международная научно-техническая конференция «Экология и защита окружающей среды», Курск, Россия, 2004 год (2 доклада).

Реализация результатов. Результаты работы внедрены в филиале СЭС ОАО «Курскэнерго», а также в учебный процесс Курского государственного технического университета.

Основные положения, выносимые на защиту:

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

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

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

4. Результаты исследования вычислительной сложности алгоритмов и скоростных характеристик устройства конвейерного сложения массивов чисел в ПЗСС.

Публикации по работе. По материалам диссертации опубликовано 8 печатных работ и получено три авторских свидетельства.

Личный вклад автора в работах, написанных в соавторстве, состоит в том, что им разработана продукционная алгоритмическая схема сложения массивов чисел в ПЗСС [2,3,8,10], выполнено сопоставление вычислительной сложности разработанной алгоритмической схемы сложения с известными продукционными схемами [1,4,11], синтезированы суммирующие устройства реализации подстановок и технические решения базовых блоков [5,6,7,9].

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 128 страницах машинописного текста, содержит 37 рисунков, 4 таблиц, список литературы из 99 наименований и приложений объемом в 39 страниц. Общий объем 167 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

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

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

Исходные данные (слагаемые) представляют собой массив в виде квадратной матрицы размерностью ИхЫ, состоящий из строк операндов-слагаемых фиксированной длины, записанных в ПЗСС. Каждое слагаемое имеет вид:

Х = Х1( Х2.....Хц, (1)

где х! - алфавитная переменная на алфавите {-1, 0, 1}; ! = 1, 2, ,..N5 N - длина разрядной сетки представления числа в ПЗСС.

Для исключения переполнения разрядной сетки проведено расширение матрицы операндов путем конкатенации слева к квадратной матрице треугольной матрицы размерностью +1))/2 , что порождает трапециевидный массив с нижней строкой длиной N и верхней строкой длиной 2Ы.

Введем основные понятия. Продукцией является конструктивный объект в виде слова: О —> М, где О - образец, М - модификатор, «->»- разделитель. Работа продукции заключается в обнаружении позиции образца в обрабатываемом слове и ее замены на модификатор.

Определение /. Образец О представляет собой двумерный конструктивный объект следующего вида:

0 =

О" О?

оа2 оь

(2)

где 0"0° =Оь 0202 =02, О",0?,О",0° - собственные начала и окончания одномерных слов О! и 02, входящих в образец О.

Определение 2 Модификатор М представляет собой двумерный конструктивный объект вида:

М = К М?\ (3)

где М"М® = М], М2М2 =М2, М",М°,М2- собственные начала и окончания одномерных слов М] и М2, входящих в модификатор М.

Если слова 01,02,М1,М2 содержат по одному элементу в каждой строке, то двумерные одноразрядные слова О и М будут иметь вид:

0«£ц (4)

02 м2

где О] = О0; 02=0Н, М,=М0;М2=МН. Обозначим:

О" 0°

¿Г-1

где Он, О0 - собственное начало и окончание двумерного образца;

М" М°

—; —!- = М , ' (6)

..Н н' о О' 4 '

М2 М2

где Мн, М0 - собственное начало и окончание двумерного модификатора. При этом

О. М.

—- = 0; —!-=М. (7)

о2 м2

Введем понятие пересечения двумерных объектов. Рассмотрим два типа пересечений двумерных продукций. 1-й тип:

(8)

0„ Мн

Определение 3. Пересечение двумерных конструктивных объектов вида о0 М0

—— и —— определено при истинности конструктивной дизъюнкции о„ Ми

(00 = Мн) V (0„ = М0) (9)

2-й тип.

о?о?_мгм? (10)

о\о°2

Определение 4. Пересечение двумерных конструктивных объектов ви-оГо? М,НМ?

да 1 1 и 11 определено при истинности конструктивной дизъюнк-0202 М2М2

ции:

А = (О" = М°) V (02 = М°) V (О® = М2) V(Он = М0) V(00 =Мн)у у(Он1001 = М02Мн2)У(0"2002 = М°1Мн1)У(0„ = М0)У(00=МН), 1 '

где О" равно левому столбцу образца, О0 равно правому столбцу образца, Мк равно левому столбцу модификатора, М° равно правому столбцу модификатора из продукции (10) соответственно.

Установлено, что если верным является хотя бы один член дизъюнкции (9), то продукция (8) самоактивируется, т.е. порождает завершающийся за конечное число шагов, итерационный конструктивный процесс. Аналогич-

ные рассуждения справедливы и для слов вида (2)-{3) и дизъюнкции (И). Истинность приведенных высказываний вытекает из следующего установленного положения: продукция завершает свою работу за конечное число шагов тогда, когда является ложной конструктивная дизъюнкция

(О =М) V (М = (^ОСЬ) (12)

где 01 и 02 - любые, но не одновременно пустые слова.

Таким образом, получены новые формы представления продукций (8) и (10), а также логические условия для анализа завершаемое™ и корректности их выполнения.

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

(П.);

Г1 = <

-1 -1 -1 0

0 -1 -1 0

(ПО;

(Па);

1 1 1 0

0 1 1 0

0 1 (п5); 0 -1

1 _0 -1 0

0 1 1 0 (п7); 0 -1 -1 0

0 1 0 0 0 -1 0 0

(Пз);

(п6);

I -I -> 0 1 (По); -1 1 0 -1

(п,);

(Пю).

Конечный набор продукций из П позволяет производить параллельное сложение множества операндов одновременно по всему пространству обрабатываемого массива. Все приведенные продукции завершают свою работу за конечное число шагов, поскольку для каждой из них конструктивная дизъюнкция (12) является ложной. Кроме того, продукции П1 - П8 удовлетворяют требованиям корректного параллельного применения, поскольку образцы для всех пар продукций не пересекаются. Продукции П9 и Пю служат целям однозначности представления чисел в ПЗСС и используются только к результату работы первых восьми продукций, т.е. только к числу, записанному в верхнюю строку обрабатываемого массива.

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

1 0 0 1

0 1 1 0 ; П,2 : 1 0 (13)

0 0 0

По результатам сравнительного анализа установлено, что разработанный продукционный алгоритм по числу шагов работы на массиве чисел размером 8x8 имеет скоростное преимущество в 2 раза.

Таким образом, во втором разделе решены задачи 1 и 2 данного диссертационного исследования.

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

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

Для подтверждения полученных теоретических результатов проведено экспериментальное исследование процессов сложения на массивах операндов размерностью 4x4, 8x8,16x16,32x32.

Были получены:

1) эмпирические зависимости Ь = ^(Ы), Ь- = Г (Ы) (рис.1), характе-

1

ризующие работу алгоритма на основе продукций ПрПю и работу алгоритма аналога на основе параллельных постановок, соответственно, где N — разрядность операндов; Ьу,Ь — число шагов обработки массива операндов. Полученные зависимости аппроксимируются линейными корреляционными функциями: Ьт»0,508614»N4-0,826613 и Ь = * 1,638196*N + 0,282258 ,

имеющими сравнительно высокую тесноту связи с экспериментальными зависимостями (коэффициенты корреляции гу ® 0,9564, г « 0,9893 - связи тесные; эмпирические средние квадратические отклонения су » 4,9100; а «9,2331). В результате корреляционная модель определяет преимущество продукционного алгоритма.

2) Зависимости Ц, Ь порождают функцию выигрыша времени суммирования Х. = ср(Ь/Ьу) = Ь/Ь- (рис.2) аппроксимирующуюся функцией X = 3,12 - 2,38/(0,51 ■ N + 0,83).

цСЮ

55 50 45 40 35 30 25 20 15 10 5 О

Эмпирические зависимости

Л

\

Л / ь

/ V V -

/ \ У

V

**

✓

Л, и

V-"

г'

I 2 3 4 5 6 7 8 9 10 II 12 13 14 15 16 17 I» 19 20 21 22 23 24 25 26 27 2« 29 30 31 32 Кбит

1 1 2 Рис.1

Эмпирическая зависимость X = <р(Ь/Ьу)

51 ' 5 1 1 1 1 \ 1 - "1 Т * т * 1 1 1

4 1 1 1

3 1 ; V/ 1 \ 1 / Д-1

2 И • 1 1 , \ у ГГ

I 2 3 4 5 6 7 « 9 10 И 12 13 14 15 16 17 1» 19 20 21 22 23 24 25 26 27 2« 29 30 31 32 Ы.бИТ

Рис. 2.

Анализ поведения функции показывает, что X монотонно возрастает с ростом разрядности операндов N и стремится к пределу ^тах « 3,12 при

N—>•00.

Для моделирования работы продукционного алгоритма сложения массивов чисел в ГТЗСС разработан соответствующий программный продукт.

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

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

Сумматор представляет собой матрицу элементов ЫхИ (при N = 16 или N = 32). Функциональная схема трех элементов однородной структуры сумматора изображена на рисунке 3.

Функциональная схема трех элементов однородной структуры сумматора

ВЫХОДЫ

в 1 - 2

ЕЕ

ЕЕ

входы

выходы

■е

ГШ

иг ИЯ2

' и» ' т ■и

■1 V 1

га

ггтт

из

я | И [у

ВХОДЫ

выходы

¿а

1+1

ш

из

4 I я 11Л

ЕС

¡ж

I » I

81

входы

ИЗ 1 + 2

¿3

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

Каждому состоянию триггера ставятся во взаимно однозначное соответствие символы из рабочего алфавита А = {-1, 0, 1}. Триггер имеет три установочных входа и три выхода. Каждому из трех состояний триггера соответствует сигнал низкого уровня на одном из выходов. Два других выхода в это время выдают сигнал высокого уровня. Установка триггера в необходимое состояние осуществляется подачей на соответствующий вход сигнала низкого уровня. Подача сигналов низкого уровня на два и более входов является запрещенной

Данные поступают из ОЗУ (либо промежуточного устройства, организованного по принципу стека) и заносятся в ячейки сумматора по строкам через коммутатор.

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

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

Регистр нуля хранит информацию о строках с нулевым содержимым. Информация в него поступает от индикатора нуля четной строки.

Схема приоритетов управляет коммутатором, получая информацию о строках с нулевым содержимым.

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

Работа сумматора организована по конвейерному принципу: в освобождающиеся строки постоянно подгружаются новые слагаемые до тех пор, пока не будет получен сигнал окончания входного потока данных. В сумматоре реализован набор подстановок, который при каждом горизонтальном просмотре обеспечивает полное обнуление строк, используемых для второго слагаемого пары. Строки сумматора группируются попарно (1 и 2, 3 и 4 и т.д.), - всего 16 пар. Сложение происходит в каждЬй паре одновременно, начиная со старших разрядов (слева направо), что позволяет уменьшить количество возникающих переносов. По окончании горизонтального просмотра в нечетных строках находятся промежуточные суммы, а четные строки содержат нули, следовательно, в них можно загружать следующие числа.

Структурная схема продукционного сумматора

Во время вертикальных сдвигов регистр выборки блокируется схемой управления сдвигом. Синхронизация работы осуществляется тактовым генератором ОБС.

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

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

Зависимость времени формирования суммы от объема входного потока данных (при разрядности слагаемых N=32) 140000

120000

В Я 100000

ВС

аналог 1

аналог 2

разработанное устройство

N. кол-во слагаемых

Рис.5

Зависимость времени формирования суммы от разрядности слагаемых (при сложении 1024 чисел)

140000 120000 100000 80000 60000 40000 20000 0

аналог 1

аналог 2

разработанное устройство

разрядность слагаемых Рис.6

Аппаратные затраты на реализацию суммирующего однородного массива 32x32 составляет около 682 ООО транзисторов против 750 ООО транзисторов на реализацию устройства-аналога 2.

В данном разделе диссертационной работы решены задачи 3 и 4.

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

В приложении размещены материалы вспомогательного назначения, а также листинг программ моделирования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

В ходе диссертационного исследования получены следующие результаты:

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

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

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

4. Синтезирован элемент однородной структуры суммирующего массива, отличительной особенностью которого является использование триггера с тремя установочными входами и выходами, что позволяет кодировать и обрабатывать числа в ПЗСС. Осуществлена системно-структурная организация конвейерного сумматора, который содержит трапециевидную структуру матрицы операндов для исключения ситуаций переполнения (разрядность нижней строки - N бит, разрядность верхней строки - 2N бит) и осуществляет конвейерную дозагрузку чисел в освобождающиеся (четные) строки матрицы операндов, что в совокупности обеспечивает временной выигрыш при обработке массива чисел. Подтверждено скоростное преимущество (до восьми раз) разработанного устройства сумматора по отношению к устройству

аналогу при соразмерных аппаратных затратах и созданы соответствующие технические решения его компонентов. Разработанное устройство открывает возможности для дальнейших опытно-конструкторских работ по созданию СБИС.

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Тютюнов, Д.Н. Сопоставительный анализ суммирующих параллельных подстановок с марковскими суммирующими продукциями [Текст] / Д.Н.Тютюнов, [и др.] // Сборник материалов IX Международной науч.-техн. конф. «Физические и компьютерные технологии», г. Харьков, 2004. С.97-99

2. Тютюнов, Д.Н. Система продукций суммирования массивов в двоичном знакорязрядном коде [Текст] / Д.Н.Тютюнов // Сборник материалов VII межд. техн. конф. «Медико-экологические информационные технологии», Курск, 2004. С.79-81.

3. Тютюнов, Д.Н. Особенности системы суммирующих продукций, представленных в различных системах кодирования [Текст] / Д.Н.Тютюнов // Сборник материалов XI Российской научно-технической конференции с международным участием «Материалы и упрочняющие технологии-2004», Курск, 2004. С.112-115.

4. Тютюнов, Д.Н. Сравнительный анализ системы суммирующих продукций с суммирующими параллельными подстановками [Текст] / Д.Н.Тютюнов И Сборник материалов XI Российской научно-технической конференции с международным участием «Материалы и упрочняющие технологии-2004», Курск, 2004. С.116-119.

5. A.C.1727120 СССР, МКИ G 06 F 7/38. Устройство для параллельного сложения чисел, представленных в двоичной знакоразрядной системе счисления [Текст] / Д.Н.Тютюнов [и др.] (СССР). №4772255/24; заявл. 22.12.89; опубл. 15.12.91, Бюл.№ 14.6с.: ил.

6. А.С.1741147 СССР, МКИ G 06 F 15/20. Устройство для реализации подстановок [Текст] / Д.Н.Тютюнов [и др.] (СССР). №4799324/24; заявл. 05.03.90; опубл. 15.12.92, Бюл-№22.12с.: ил.

7. A.C. 1805478 СССР, МКИ G 06 F 15/16. Устройство для реализации подстановок [Текст] / Д.Н.Тютюнов [и др.] (СССР). №4873212/24; заявл. 10.10.90; опубл. 09.10.92, Бюл.№12.14с.: ил.

8. Тютюнов, Д.Н. Исследование систем продукции A.A. Маркова для разработки суммирующих устройств [Текст] / Д.Н.Тютюнов, В.Е Абышкин,

A.Д.Тютюнов // Сборник материалов межд. техн. конф. «Медико-экологические информационные технологии», Курск, 1998. С.80-81.

9. Тютюнов, Д.Н. Разработка суммирующих устройств с использованием систем продукций [Текст] / Д.Н.Тютюнов, В.Е.Абышкин // Сборник материалов 1 Всероссийской науч-техн.конф. «Компьютерные технологии в науке, проектировании и производстве, г. Н.Новгород, 1999. С.112-115.

Ю.Тютюнов, Д.Н. Система продукций для реализации суммирования массивов в двоичном знакоразрядном коде [Текст] / Д.Н.Тютюнов,

B.М.Довгаль // Сборник материалов межд. техн. конф. «Медико-экологические информационные технологии», Курск, 2004. С.72-75.

11.Тютюнов, Д.Н. Сопоставительный анализ суммирующих продукций с суммирующими параллельными подстановками [Текст] / Д.Н.Тютюнов, О.И.Овсянников II Сборник материалов межд. техн. конф. «Медико-экологические информационные технологии», Курск, 2004. С.75-78.

ИД №06430 от 10.12.01 Подписано в печать 23,03,06формат60х84 1/16. Печать офсетная. Печ. л. 1,0, Тираж 100. Заказ а Курский государственный технический университет. Издательско—полиграфический центр Курского государственного технического университета.305040, г.Курск, ул. 50 лет Октября, 94.

Соискатель

Д.Н. Тютюнов

¿006/V

»^68 f4

Введение.

Глава 1. Аналитический обзор существующих средств сложения чисел и сущность предлагаемого подхода.

1.1. Общие сведения. Краткая историческая справка.

1.2. Классификации методов сложения.

1.3. Аппаратные средства поддержки методов сложения.

1.3.1. Аппаратная поддержка методов сложения в RISC процессорах.

1.3.2. Аппаратная поддержка методов сложения в цифровых сигнальных процессорах.

1.3.3. Аппаратная поддержка методов на основе ПЛИС.

1.3.4. Аппаратная поддержка методов сложения в специализированных устройствах.

1.4. Побудительные причины исследования и сущность предлагаемого подхода к созданию сумматоров массивов чисел.

1.5. Выводы по главе.

Глава 2. Разработка и структурно-лингвистическое исследование алгоритмической продукционной схемы сложения.

2.1. Основные положения организации процесса сложения.

2.2. Основные понятия параллельных вычислений операций.

2.3. Разработка специализированной продукционной системы для сложения чисел в знакоразрядной системе счисления.

2.3.1. Алфавит (базис), слово, языки и продукции.

2.3.2. Синтез алгоритмической схемы символьного сложения.

2.4. Структурно-лингвистический анализ продукционной схемы сложения.

2.5. Выводы по главе.

Глава 3. Разработка алгоритма, реализующего способ сложения, его проверка ^ с применением математических моделей и данных эксперимента.

3.1. Построение параллельного алгоритма сложения с помощью продукционного подхода.

3.1.1. Алгоритм Oj (продукция П]).

3.1.2. Алгоритм Ф2 (продукция П2).

3.1.3. Алгоритм Ф3 (продукция П3).

3.1.4. Алгоритм Ф4 (продукция П4).

3.1.5. Алгоритм Ф5 (продукция П5).

3.1.6. Алгоритм Ф6 (продукция П6).

3.1.7. Алгоритм Ф7 (продукция П7).

3.1.8. Алгоритм Ф8 (продукция П8).

3.1.9. Алгоритм Ф9 (продукция П9).

3.1.10. Алгоритм Фю (продукция П10).

3.2. Сочетание алгоритмов Ф] -г Ф10.

3.3. Алгоритм параллельных подставок, используемых при суммировании массива.

3.4. Реализация способа продукционного сложения.

3.5. Сравнительная оценка скорости работы продукционной алгоритмической схемы.

3.6. Выводы по главе.

Глава 4. Разработка и исследование аппаратных средств символьного сложения.

4.1.Формализация и синтез продукционного сумматора.

4.2. Базовая ячейка сумматора. Триггер с тремя устойчивыми состояниями.

4.3.Структурная схема сумматора.

4.4. Функциональные схемы узлов и блоков.

4.4.1 Функциональная схема сумматора 32X32.

4.4.2 Функциональная схема регистра выборки.

4.4.3. Функциональная схема регистра нуля.

4.4.4. Функциональная схема блока приоритетов.

4.4.5. Функциональная схема коммутатора.

4.4.6. Функциональная схема устройства управления сдвигом.

4.5. Оценка скоростных характеристик разработанного устройства и сравнение их с аналогом.

Выводы по главе.

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

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

Вопросам скоростной обработки числовой информации посвятили свои работы Каляев А.В., Марков А.А., Бойков В.Д., Смолов В.Б., Бандман О.А., Ачасова С.Н., Kung N.T., Book R.V. и другие отечественные и зарубежные ученые.

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

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

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

Работа выполнялась в рамках госбюджетных НИР по гранту Г02-4.2-5 «Методы системно-структурной организации архитектур семейства процессоров нового поколения и многопроцессорных систем высокоскоростной обработки символьной информации и исследование их скоростных характеристик» при непосредственном участии автора.

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

1. Создание схемы продукционного алгоритма для выполнения операций сложения массива чисел в формате с фиксированной точкой в ПЗСС.

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

3. Синтез элемента структуры сумматора и реализация его структурно-функциональной организации.

4. Исследование, скоростных характеристик алгоритмов и сумматора, а также определение уровня аппаратных затрат.

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

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

Методы исследования основаны на положениях конструктивной математики, методах современной теории алгоритмов, теорий конечных автоматов и проектирования ЭЦВМ.

Научная новизна заключается в том, что впервые получены следующие результаты:

1. Разработана новая форма представления продукций, отличающаяся заданием образцов и модификаторов в виде двухмерных конструктивных объектов, что обеспечивает обработку массивов чисел, заданных в ПЗСС.

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

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

4. Синтезирован элемент однородной структуры и осуществлена системно-структурная организация конвейерного сумматора, сокращающего затраты времени на суммирование в 8 раз по отношению к устройству аналогу.

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

Апробация результатов работы. Результаты работы отражены в докладах на научных конференциях: V Научно-техническая конференция с международным участием «Материалы и упрочняющие технологии-97», Курск, Россия, 1997 год; Международная техническая конференция «Медико-экологические информационные технологии», Курск, Россия, 1998 год (2 доклада); I Всероссийская научно-техническая конференция, часть {II} «Компьютерные технологии в науке, проектировании и производстве», Нижний Новгород, Россия, 1999 год (2 доклада); VIII Международная научно-техническая конференция «Физические и компьютерные технологии», Харьков, Украина, 2004 год (2 доклада); Международная научно-техническая конференция «Экология и защита окружающей среды», Курск, Россия, 2004 год (2 доклада).

Реализация результатов. Результаты работы внедрены в филиале СЭС ОАО «Курскэнерго», а также в учебный процесс Курского государственного технического университета.

Основные положения, выносимые на защиту:

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

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

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

4. Результаты исследования вычислительной сложности алгоритмов и скоростных характеристик устройств конвейерного сложения массивов чисел в ПЗСС.

Публикации по работе. По материалам диссертации опубликовано 8 печатных работ и получен патент на изобретение.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 128 страницах машинописного текста, содержит 37 рисунков, 4 таблиц, список литературы из 99 наименований и приложений объемом в 39 страниц. Общий объем диссертации 167 страниц.

4.6. Выводы по главе

1. Выполнена формализация и синтез продукционного сумматора.

2. Разработана базовая ячейка сумматора в форме триггера с тремя устойчивыми состояниями.

3. Сформирована структурная схема продукционного сумматора.

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

5. Определены количественные оценки скоростных характеристик разработанного устройства в сравнении с аналогами 1,2. Установлено, что выигрыш во времени работы достигает X = 8,5 -г 8,7 раза. Такой эффект достигается за счет распараллеливания работы сумматора.

ЗАКЛЮЧЕНИЕ

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

В ходе работы получены следующие результаты:

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

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

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

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

5. Разработан способ системно-структурной организации продукционных сумматоров и для каждого из них выполнены технические решения элементов однородной среды и обобщенные структуры устройств, обеспечивающих высокую скорость выполнения матричного алгебраического сложения. Сравнительный анализ работы матричного аналога, основанного на параллельных подстановках П^ +П12 и разработанного матричного продукционного устройства показал, что последние имеют скоростные преимущества от 3 до 4 раз, а аппаратная экономия - до 4 раз за счет однородности структур алгоритмов. Аппаратная реализация продукционных сумматоров позволяет довести преимущество в быстродействие до 6,5+8 раз за счет распараллеливания процесса суммирования путем разбиения массива операндов на массивы размерностью 2 х п, где п - длина операнда.

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Тютюнов, Д.Н. Сопоставительный анализ суммирующих параллельных подстановок с марковскими суммирующими продукциями [Текст] / Д.Н.Тютюнов, [и др.] // Сборник материалов IX Международной науч.-техн. конф. «Физические и компьютерные технологии», г. Харьков, 2004. С.97-99

2. Тютюнов, Д.Н. Система продукций суммирования массивов в двоичном знакорязрядном коде [Текст] / Д.Н.Тютюнов // Сборник материалов VII межд. техн. конф. «Медико-экологические информационные технологии», Курск, 2004. С.79-81.

3. Тютюнов, Д.Н. Особенности системы суммирующих продукций, представленных в различных системах кодирования [Текст] / Д.Н.Тютюнов // Сборник материалов XI Российской научно-технической конференции с международным участием «Материалы и упрочняющие технологии-2004», Курск, 2004. С.112-115.

4. Тютюнов, Д.Н. Сравнительный анализ системы суммирующих продукций с суммирующими параллельными подстановками [Текст] / Д.Н.Тютюнов // Сборник материалов XI Российской научно-технической конференции с международным участием «Материалы и упрочняющие технологии-2004», Курск, 2004. С.116-119.

5. А.С.1727120 СССР, МКИ G 06 F 7/38. Устройство для параллельного сложения чисел, представленных в двоичной знакоразрядной системе счисления [Текст] / Д.Н.Тютюнов [и др.] (СССР). №4772255/24; заявл. 22.12.89; опубл. 15.12.91, Бюл.№ 14.6с.: ил.

6. А.С. 1741147 СССР, МКИ G 06 F 15/20. Устройство для реализации подстановок [Текст] / Д.Н.Тютюнов [и др.] (СССР). №4799324/24; заявл. 05.03.90; опубл. 15.12.92, Бюл.№22.12с.: ил.

7. A.C.I805478 СССР, МКИ G 06 F 15/16. Устройство для реализации подстановок [Текст] / Д.Н.Тютюнов [и др.] (СССР). №4873212/24; заявл. 10.10.90; опубл. 09.10.92, Бюл.№12.14с.: ил.

8. Тютюнов, Д.Н. Исследование систем продукции А.А. Маркова для разработки суммирующих устройств [Текст] / Д.Н.Тютюнов, В.Е.Абышкин, А.Д.Тютюнов // Сборник материалов межд. техн. конф. «Медико-экологические информационные технологии», Курск, 1998. С.80-81.

9. Тютюнов, Д.Н. Разработка суммирующих устройств с использованием систем продукций [Текст] / Д.Н.Тютюнов, В.Е.Абышкин // Сборник материалов I Всероссийской науч-техн.конф. «Компьютерные технологии в науке, проектировании и производстве, г. Н.Новгород, 1999. С. 112-115.

10.Тютюнов, Д.Н. Система продукций для реализации суммирования массивов в двоичном знакоразрядном коде [Текст] / Д.Н.Тютюнов, В.М.Довгаль // Сборник материалов межд. техн. конф. «Медико-экологические информационные технологии», Курск, 2004. С.72-75.

11. Тютю нов, Д.Н. Сопоставительный анализ суммирующих продукций с суммирующими параллельными подстановками [Текст] / Д.Н.Тютюнов, О.И.Овсянников // Сборник материалов межд. техн. конф. «Медико-экологические информационные технологии», Курск, 2004. С.75-78.

1. Марков, А.А. Теория алгоритмов Текст. / А.А.Марков, Н.М.Нагорный. М.: Наука, 1984. 432 с.

2. Ачасова, С.М. Корректность параллельных вычислительных процессов Текст. / С.М.Ачасова, О.Л.Бандман. Новосибирск: Наука, Сибирское отделение, 1990. 252 с.

3. Карцев, М.А. Вычислительные системы и синхронная арифметика Текст. / М.А.Карцев, В.А.Брик. М.: Радио и связь, 1981. 360 с.

4. Байков, В.Д. Специализированные процессоры: итерационные алгоритмы и структуры Текст. / В.Д.Байков, В.Б.Смолов. М.Радио и связь, 1985. 288 с.

5. Джорждейн, Р. Справочник программиста персональных компьютеров типа IBM PC, XN и AT Текст. / Р.Джорждейн. М.: Финансы и статистика, 1992. 543 с.

6. Каляев, А.В. Микропроцессорные системы с программируемой архитектурой Текст. / А.В.Каляев. М.: Радио и связь, 1984. 360 с.

7. Довгаль, В.М. Использование асинхронных вычислителей для решения проблемы вычислительной сложности в генераторах хаотических последовательностей Текст. / В.М.Довгаль, В.В.Елагин, В.Е.Абышкин; ВИНИТИ. М., 2000. 9 с.

8. Галушкин, А.И. Некоторые исторические аспекты развития элементной базы вычислительных систем с массовым параллелизмом (80- и 90- годы) Текст. / А.И.Галушкин // Нейрокомпьютер. 2000.№1. С.68-82.

9. Довгаль, В.М. Методы модификации формальных систем обработки символьной информации Текст.: монография / В.М.Довгаль; Курск, гос. техн. ун-т Курск, 1996. 115 с.

10. Варшавский, В.И. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах Текст. / В.И.Варшавский. М.: Наука, 1986. 398 с.

11. П.Ачасова, С.М. Алгоритмы синтеза автоматов на программируемых матрицах Текст. / С.М.Ачасова. М.: Радио и связь, 1987. 134 с.

12. Бандман, О.Л. Специализированные процессоры для высокопроизводительной обработки данных Текст. / О.Л.Бандман. Новосибирск: Наука, 1988. 205 с.

13. Успенский, В.А. Теория алгоритмов: основные открытия и приложения Текст. / В.А.Успенский, А.А.Семенов. М.: Наука, 1987. 218 с.

14. Левин, В.К. Структурно-технические характеристики и направления развития высокопроизводительных вычислительных систем Текст. / В.К.Левин // Электронная вычислительная техника. Вып.2. М.: Радио и связь, 1988. С.4-16.

15. Villasenor, J. Configurable Computing Text. / J.Villasenor, W.Mangione-Smith // Scientific American, 1997. June. P.27-32.

16. Brownston, L. Programming Expert System in OPSS: An Introduction to Rule-Based Programming Text. / L.Brownston. Addison-Wesley Pube. Co, Inc., 1988. 457 p.

17. Tick, E. Towards a Pipelined Prolog Processor Text. / T.Tick, D.H.Warren // IEEE Computer Society, 1984. Febr. P.29-40.

18. Goldberg, A. Smalltalk-80. The Language and its Implementation Text. /

19. A.Goldberg, D.Robson // Addison-Wesley, 1983. 714 p.

20. Довгаль, B.M. Алгебра продукций Текст.: препринт / В.М.Довгаль; Курск, гос.техн.ун-т. Курск, 1996. 7 с.

21. Довгаль, В.М. Конструктивные процессы, порождаемые продукциями с пересекающимися образцами и модификаторами Текст.: препринт /

22. B.М.Довгаль. Курск, гос.техн.ун-т. Курск, 1996. 7 с.

23. Довгаль, В.М. Самоиндукционные процессы в схемах продукций Текст.: препринт / В.М.Довгаль. Курск, гос.техн.ун-т. Курск, 1996. 7 с.

24. Довгаль, В.М. Конструктивные процессы, порождаемые продукциями с образцами, содержащими модификатор Текст.: препринт / В.М.Довгаль. Курск, гос.техн.ун-т. Курск, 1996. 7 с.

25. Шнейдер, У. Документы за работой: рождение виртуальных документов Текст. / У.Шнейдер // Вычислительная техника. Экспресс-информация. 1996. №23. С. 17.

26. Бородин, С.Г. Арбитр ОЗУ для устройств с параллельной архитектурой Текст.: препринт/С.Г.Бородин. Курск, гос.техн.ун-т. Курск, 1997. 11 с.

27. А.С. 1455345 СССР, МКИ G 06 F 15/20. Устройство для реализации нормативных алгоритмов Маркова Текст. / В.М.Довгаль [и др.] (СССР). №4234561; заявл. 24.02.87; опубл. 30.01.89. Бюл. №4. 4 с.

28. А.С.1635192 СССР, МКИ G 06 F 15/20. Устройство для реализации подстановок слов Текст. / В.М.Довгаль [и др.] (СССР). №4684324; заявл. 03.05.89; опубл. 15.03.91. Бюл. №4. 6 с.

29. Братко, И. Программирование на языке Пролог для искусственного интеллекта Текст.: [Пер. с англ.] / И.Братко. М.:Мир, 1990. 560 с.

30. Афанасьев, М. 10. Исследование операций в конкретных ситуациях текст./ М.Ю. Афанасьев, Б.П. Суворов. М.:ТЕИС,1999. 287с.

31. Ahuja, R.K. Solution of Networks Flows (Theory, Algorithms and Applications) Text./ R.K. Ahuja , T.L. Magneti, J.B. Orlin. New York: Wiley, 2000. 312p.

32. Bertsmis, D. Introduction to Linear Optimization Text./ D. Bertsmis, John N. Tsitsiklis. McGraw-Hill, IL, 1999. 178p.

33. Feist, W.R. Managing a Global Enterprise (A Concise Guide to International Operations) Text./ W.R. Feist, J.A. Heely, M.H. Lu, R.L. Nersesian. Monmouth University, Quorum Press, 1999. 215p.

34. Glover, F. Tabu Search Text./ F. Glover, M. Laguna. University of Colorado at Boulder, 1999.262р.

35. Johuson, C. Exploring Corporate Strategy Text./ C. Johuson, K. Scholes. Prentic Hall, 1997.315р.

36. Springer, Verlag. The Logic of Logistics Text./ Verlag Springer, J. Bramel. New York: Wiley, 1997. 342p.

37. Kaminsky, LP. Designing and Managing, the Supply Chain Text./ LP. Kamin-sky, E. Simchi-Levi. Mc. Graw-Hill, IL, 1999. 273p.

38. Способ суммирования чисел текст.: пат.02145113 Рос. Федерация: МПК G 06F-7/50 / Варламов О.О.; заявитель и патентообладатель Варламов О.О.; №98119301/09; заявл. 23.10.98; опубл. 27.01.00, Бюл.№3.1с.: ил.

39. Реконфигурационный асинхронный сумматор-умножитель Текст.: пат. 02159464 Рос. Федерация: МПК G 06F-7/50, МПК G 06F 7/52 / Довгаль В.М., Селезнев М.Е., Старков Ф.А., Титов B.C.; заявитель и патентообладатель

40. Курский государственный технический университет. №99109904/09; заявл. 05.05.99; опубл. 20.11.00, Бюл.№32.4с.: ил.

41. Устройство для накопления чисел с плавающей запятой Текст.: пат. 94041149 Рос. Федерация: МПК G 06F-7/50 / Фельдман Б.Я., Германов А.В., Фельдман М.Б.; заявитель и патентообладатель Фельдман М.Б., Германов

42. A.В., Фельдман М.Б. №94041149/09; заявл. 10.11.94; опубл. 27.09.96, Бюл.№27.1с.: ил.

43. Вычислительное устройство Текст.: пат. 02132083 Рос. Федерация: МПК G 06F-7/50, МПК G 06F 7/52 / Довгаль Гребнев С.В., Дроздолв И.А., Кузнецов

44. B.Е., Лихачев A.M., Рунеев А.Ю., Федяй С.И.; заявитель и патентообладатель Военная академия связи. №90104556/09; заявл. 18.02.98; опубл. 20.06.99, Бюл.№ 17.5с.: ил.

45. Сумматор кодов «1 из N» Текст.: пат.02129730 Рос. Федерация: МПК G 06F-7/50 / Кулаковский А.Ф.; заявитель и патентообладатель Научно-технический центр «Атлас». №97118056/09. заявл. 29.10.97; опубл. 27.04.99, Бюл.№12.2с.: ил.

46. Сумматор Текст.: пат.02049346 Рос. Федерация: МПК G 06F-7/50 / Куроч-кин В.Г.; заявитель и патентообладатель Государственный научно-исследовательский институт авиационных систем. №940078226/14; заявл. 10.03.94; опубл. 27.11.95, Бюл.№33.3с.: ил.

47. Суммирующее устройство Текст.: пат.94035698 Рос. Федерация: МПК G 06F-7/50 / Ким П.А., Алынбаев К.С.; заявитель и патентообладатель Новосибирский государственный университет. №94035698/09; заявл. 27.09.94; опубл. 20.07.95, Бюл.№20.2с.: ил.

48. Суммирующее устройство Текст.: пат.02092891 Рос. Федерация: МПК G 06F-7/50 / Ким П.А.; заявитель и патентообладатель Вычислительный центр СО РАН. №94040075/09; заявл. 27.10.94; опубл. 10.10.97, Бюл.№28.1с.: ил.

49. Сумматор на КМВП транзисторах Текст.: пат.02185656 Рос. Федерация: МПК G 06F-7/50 / Лементуев В.А.; заявитель и патентообладатель Институт проблем управления им.В.А.Трапезникова РАН. №2001104563/09; заявл. 19.02.01; опубл. 20.07.02, Бюл.№20.1с.: ил.

50. Устройство для сложения Текст.: пат.02090925 Рос. Федерация: МПК G 06F-7/50 / Полян Л.Е., Учер В.Г.; заявитель и патентообладатель Центральный научно-исследовательский институт связи. №5045660/09; заявл. 07.04.92; опубл. 20.09.97, Бюл.№26.1с.: ил.

51. Суммирующее устройство Текст.: пат.94040075 Рос. Федерация: МПК G 06F-7/50 / Ким П.А.; заявитель и патентообладатель Вычислительный центр СО РАН. №94040075/09; заявл. 27.10.94; опубл. 10.09.96, Бюл.№25.1с.: ил.

52. Сумматор с переменным модулем сложения Текст.: пат.02183347 Рос. Федерация: МПК G 06F-7/50 / Чулков В.А.; заявитель и патентообладатель Пензенский технологический институт. №2000107325/09; заявл. 23.03.00; опубл. 10.06.02, Бюл.№16.1с.: ил.

53. Устройство для определения количество единиц в двоичном восьразрядном * числе Текст.: пат.02030783 Рос. Федерация: МПК G 06F-7/50 / Зухраев

54. А.А., Исмаилов Ш.-М.А., Кокаев О.Г., Хатумов В.М.; заявитель и патентообладатель Дагенстанский политехнический институт. №5015072/24; заявл. 03.07.91; опубл. 10.03.95, Бюл.№7.3с.: ил.

55. Устройство для счета импульсов Текст.: пат.01785407 Рос. Федерация: МПК Н03К-23/00, Н 03К-25/00 / Шишкин Г.И., Зубаеров Р.Ф; заявитель и

56. Уу патентообладатель Шишкин Г.И., Зубаеров Р.Ф.№4775531/21; заявл.2912.89; опубл. 30.04.95, Бюл.№12.3с.: ил.

57. Довгаль, В.М. Индикатор применимости двухпродукционных схем алгоритмов Текст.: препринт / В.М.Довгаль; Курск, гос.техн.ун-т. Курск, 1996. 8с.

58. Довгаль, В.М. Метод синтеза продукций-акселераторов конструктивных процессов Текст.: препринт / В.М.Довгаль; Курск, гос.техн.ун-т. Курск, 1996.11 с.

59. Довгаль, В.М. Процессы блокировки в системах продукций Текст.: препринт/В.М.Довгаль; Курск, гос.техн.ун-т. Курск, 1996.8 с.

60. Довгаль, В.М. Алгоритмический индикатор пересечения слов Текст.: препринт/В.М.Довгаль; Курск, гос.техн.ун-т. Курск, 1996.6 с.

61. Эйсымонт, JI.K. Компьютеры для обработки символьной информации Текст. / Л.К.Эйсымонт// Зарубежная радиоэлектроника. 1990. №4. С.3-28.

62. Klar,W. Experten system: gestern, bente, morgen Text. / W.Klar // Electronik. 1991. Vol.40. №11. P.82-85.

63. Современное состояние и тенденции развития супермини ЭВМ Текст. / Средства ВТ и оргтехники. 1990. Вып.1. С. 18-28.

64. Волш, Д.Технология программных моделей Текст. /Д.Волш // Computer Week. 1997. №32. С. 12-15.

65. Симэн, Г. Вейвлеты на программируемом кремнии Текст. / Г.Симэн // Компьютер. 1998. №9. С. 17-23.

66. Смит, Б.Э. Архитектура и программирование микропроцессора Intel 80386 Текст. /Б.Э.Смит, М.Т.Джонсон. М.: ТОО «Кондор», 1992. 334 с.

67. CORE Solutiong Products Catalog Text.: разработчик и изготовитель / Xilinx Inc. Воронеж, 1999. P. 124.

68. Минсюков, В.Г. Макромодули быстродействующих умножителей на ПЛИС Xilinx Текст. / Б.Г.Минтюков, В.Д.Капитонов. // Электроника и компоненты. 1998. №3. С.31.

69. Балашов, Ю.С. Библиотека цифровых макромодулей для средств проектирования ПЛИС Текст. / Ю.С.Балашов, В.Г.Мистюков, В.Д.Капитонов. Воронеж: Xilinx Inc., 1999. С.26.

70. Алюшин, М.В. Аппаратная реализация быстродействующих нейросетей на основе программируемой логики фирм АМВ, Altera, Xilinx. Нейроинформа-тика-99 Текст. В 3 ч. 4.2 / М.В.Алюшин. М.: МИФИ. 1999. С. 18-24.

71. Довгаль, В.М. Об одном способе сокращения затрат времени при работе нормального алгоритма Текст.: препринт / В.М.Довгаль [и др.]; ВИНИТИ. М., 1990. 5 с.

72. Довгаль, В.М. Об одном способе организации конвейера нормальных алгоритмов Текст. препринт / В.М.Довгаль [и др.]; ВИНИТИ. М., 1990. 7 с.

73. Довгаль, В.М. Проблема распознавания эквивалентности схем продукций Текст.: / В.М.Довгаль, А.В.Хитинков; // Известия Курск, гос.техн.ун-т. Курск, 1999 С.103-113.

74. А.С. 1789981 СССР, МКИ G 06 F 7/52. Устройства умножения Текст. / А.А.Шосток, В.В.Яцкевич (СССР). №5962114/24; заявл. 10.11.90; опубл. 16.02.92, Бюл.№3.7с.: ил.

75. А.С. 1833866 СССР, МКИ G 06 F 7/52. Устройства умножения по методу че-тырехквадратичного умножения Текст. / А.А.Шосток, В.В.Яцкевич (СССР). №4752154/24; заявл. 20.12.89; опубл. 15.10.91, Бюл.№30.8с.: ил.

76. А.С.1727120 СССР, МКИ G 06 F 7/38. Устройства для параллельного сложения чисел, представленных в двоичной знакоразрядной системе счисления Текст. / Д.Н.Тютюнов [и др.] (СССР). №4772255/24; заявл. 22.12.89; опубл. 15.12.91, Бюл.№ 14.6с.: ил.

77. А.С.1667097 СССР, МКИ G 06 F 15/20. Устройства для реализации подстановок с двухкомпонентными вхождениями Текст. / Д.Н.Тютюнов [и др.] (СССР). №4735877/24; заявл. 11.09.89; опубл. 01.04.91, Бюл.№28.12с.: ил.

78. A.C.I741147 СССР, МКИ G 06 F 15/20. Устройства для реализации подстановок Текст. / Д.Н.Тютюнов [и др.] (СССР). №4799324/24; заявл. 05.03.90; опубл. 15.12.92, Бюл.№22.12с.: ил.

79. А.С. 1805478 СССР, МКИ G 06 F 15/16. Устройства для реализации подстановок Текст. / Д.Н.Тютюнов [и др.] (СССР). №4873212/24; заявл. 10.10.90; опубл. 09.10.92, Бюл.№12.14с.: ил.

80. А.С. 1777134 СССР, МКИ G 06 F 7/52. Устройства умножения. Текст. / А.М.Романов, Ю.И.Шпаков (СССР). №5723367/24; заявл. 08.12.90; опубл. 15.11.92, Бюл.№43.6с.: ил.

81. Тютюнов, Д.Н. Исследование систем продукции А.А. Маркова для разработки суммирующих устройств Текст. / Д.Н.Тютюнов, В.Е.Абышкин, А.Д.Тютюнов // Сборник материалов межд.техн. конф. «Медико-экологические информационные технологии», Курск, 1998. С.80-81.

82. Тютюнов, Д.Н. Система продукций для реализации суммирования массивов в двоичном знакоразрядном коде Текст. / Д.Н.Тютюнов, В.М.Довгаль // Сборник материалов межд.техн. конф. «Медико-экологические информационные технологии», Курск, 2004. С.72-75.

83. Тютюнов, Д.Н. Сопоставительный анализ суммирующих продукций с суммирующими параллельными подстановками Текст. / Д.Н.Тютюнов, О.И.Овсянников // Сборник материалов межд.техн. конф. «Медико-экологические информационные технологии», Курск, 2004. С.75-78.

84. Тютюнов, Д.Н. Система продукций суммирования массивов в двоичном зна-корязрядном коде Текст. / Д.Н.Тютюнов // Сборник материалов VII межд.техн. конф. «Медико-экологические информационные технологии», Курск, 2004. С.79-81.

85. МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

86. Тютюнов Дмитрий Николаевич

87. ПРОДУКЦИОННАЯ АЛГОРИТМИЧЕСКАЯ СХЕМА И УСТРОЙСТВО СУММАТОРА МАССИВА ЧИСЕЛ В ЗНАКОРАЗРЯДНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

88. Специальность 05.13.05 «Элементы и устройства вычислительной техники и систем управления»