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

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

ФЕДЮИИН Роман Николаевич

КОНВЕЙЕРНО-МОДУЛЯРНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СТРУКТУРЫ С НАСТРАИВАЕМОЙ ЛОГИКОЙ ДЛЯ АРИФМЕТИЧЕСКИХ ВЫЧИСЛЕНИЙ

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

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

ПЕНЗА 2006

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

Научный руководитель - доктор технических наук,

профессор Князьков В. С. Официальные оппоненты: доктор технических наук,

профессор Чижухин Г. Н.;

кандидат технических наук, доцент Бикташсв Р. А.

Ведущая организация - ОАО НПП «РУБИН», г. Пенза.

Защита состоится 19 декабря 2006 г., в 14 часов, на заседании диссертационного совета Д 212.186.01 в государственном образовательном учреждении высшего профессионального образовать «Пензенский государственный университет» по адресу: 440026, г. Пенза, ул. Красная, 40.

С диссертацией и авторефератом можно ознакомиться в библиотеке государственного образовательного учреждения высшего профессионального образования «Пензенский государственный университет» и на сайге университета: wwwrpnzgu.ru.

Автореферат разослан « » иОлУ^-ё- 2006 г.

Ученый секретарь диссертационного совета кандидат технических наук, профессор / ШашковБ, Д.

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

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

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

Для достижения поставленной цели решаются следующие задачи:

1. Исследование способов организации вычислений с фиксированной точкой в современных арифметико-логических устройств АЛУ и повышения их быстродействия.

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

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

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

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

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

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

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

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

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

2, Предложены конвейерно-модулярпые однородные вычислительные структуры с настраиваемо!! логикой для выполнения потока

операций с фиксированной точкой в системах счисления в остаточных классах, для:

• арифметического сложения; эта структура отличается от известных тем, что при 64-128-разрядном представлении чисел скорость вычислений увеличивается в среднем в 3-13 раз при одновременном сокращении аппаратных затрат в среднем в 2-18 раз.

• арифметического умножения; струюура отличается от известных тем, что при 64-128-разрядном представлении чисел скорость вычислений увеличивается в среднем в 3-12 раз при одновременном сокращении аппаратных затрат в среднем в 4-18 раз.

• арифметического деления; структура отличается от известных тем, что при 64-128-разрядном представлении чисел скорость вычислений увеличивается примерно в 2 раза при одновременном сокращении аппаратных затрат в среднем в 2-6 раз.

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

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

Реализация и внедрение. Диссертация является теоретическим обобщением научно-исследовательских работ, выполненных автором в ГОУ ВПО ПТУ и ФГУП ПНИЭИ. Теоретические результаты работы применены при выполнении ОКР «Трамплин-АС» в ФГУП ПНИЭИ, о чем имеется акт внедрения. Достоверность полученных теоретиче-

ских оценок подтверждается совпадением с результатами экспериментального моделирования вычислительных структур различного типа, проведенного в рамках ОКР «Трамплин-АС» в ФГУП ПНИЭИ.

По результатам исследований предложены технические решения, защищенные патентами на изобретение РФ [1], [2].

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

1. Модель арифметико-логического устройства с настраиваемой логикой.

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

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

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

5. Методика формальной оценки временной и аппаратной сложности реализации арифметико-логических операций с фиксированной точкой в однородных вычислительных структурах.

Апробация работы. Результаты работы обсуждались и докладывались на: VI Международной научно-технической конференции «Новые информационные технологии и системы», 2004, ПТУ, г. Пенза; научно-технической конференции «Специальная техника средств связи», 2004, ФГУП ПНИЭИ, г. Пенза; Всероссийской научной конференции молодых ученых «Наука, Технологии, Инновации», 2004, Н1ГУ, г. Новосибирск; X Всероссийской НТК студентов молодых ученых и специалистов, 2005, Рязанская гос. радиотехническая академия, г. Рязань; конференции «Антикризисное управление в России в современных условиях», 2005, МГТУ им. Баумана, г. Москва; 1-м Международном форуме «Актуальные проблемы современной науки», 2005, СГТУ, г. Самара.

Публикации. Основные результаты диссертационной работы опубликованы в 7 статьях, 8 сборниках тезисов докладов. По материалам работы получено два патента на изобретение РФ [1], [2].

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 136 наименований н .четырех приложений Основная часть работы изложена на 160 страницах машинописного текста. Работа содержит 76 рисунков и 36 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность данной работы, сформулированы цели и задачи исследований, научная новизна, практическая ценность и основные научные положения, выносимые на защиту.

В первой главе проведен анализ современных направлений развития архитектуры АЛУ различных классов. Анализ показывает, что сегодня интенсивно ведутся научные исследования в области макро- и мик-роархигекгуры процессоров нового поколения. Одной из приоритетных задач является задача построения АЛУ высокого быстродействия.

Комплексный анализ показывает, что на сегодняшний день для повышения скорости вычислений основным решением является использование «дублирования» в АЛУ исполнительных устройств (ИУ), но это ведет к нерациональному использованию ресурсов кристалла. Решением задачи повышения скорости вычислений в АЛУ при приемлемых аппаратных затратах является построение АЛУ, операционная часть которых представляет собой универсальное вычислительное пространство, перестраиваемое для выполнения конвейерно-парал-лельной обработки различных арифметико-логических операций. Исследования АЛУ этих типов показали, что основным недостатком гетерогенных решений является их высокая топологическая иррегулярность, что приводит к сложностям при масштабировании их операционных частей. Таким образом, актуальна задача создания АЛУ нового типа, которые были бы масштабируемы и более эффективны как с точки зрения скорости вычислений, так и с точки зрения объема аппаратных ресурсов. Доказано, что для решения такой задачи целесообразно использовать концепцию однородных вычислительных структур (ОВС), важными достоинствами которых является простота масштабирования и высокая технологичность производства (рис. 1).

Поток команд управления

Входной поток данных

.. .',' V.'Л".'./ V!.. "... "

Сортирован* входного I—-----------

I

иишма шва

Выходной поток данных

Рис. 1. Вариант АЛУ на базе ОВС

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

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

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

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

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

Для формальной оценки эффективности вычислений в ИУ АЛУ с фиксированной точкой (см. рис. 1) в качестве их математических моделей используются модели марковских процессов (рис. 2) и модели пространственной сложности. Временная сложность в данной модели

Рис. 2. Граф модели АЛУ на базе ОВС

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

Вычислительный процесс в АЛУ представляется состояниями марковского графа: 5„ - состояние, в котором находится вычислитель до запуска вычислительного процесса; ¿>1 - состояние, характеризующее работу сортировщика входного потока данных; Зг^т — состояния вычислительного процесса, характеризующие буферизацию входных данных с последующей их обработкой и сохранением в регистрах временного хранения; & — состояние, в котором сортировщик входного потока принимает решение, куда направить данные -в выходной поток данных или обратно на обработку в ОВС; - финальное состояние, соответствующее полному завершению вычислительного процесса и его останов. При этом Рц — вероятность перехода из состояния 51, в

При однократной и результативной реализации процесса среднее

число попаданий процесса ¿¡^ в состояния Бг, 55. 5е> £7, определяется (см. рис. 2) следующим образом:

^ РХ1 Рзл Рхг Ра (8)

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

(1) (2)

(3)

(4)

(5)

(6) (7)

ак=а?рг

(9)

менной сложности каждого из к подпроцессов ди Яг, <7з, #4, ф, ф,

дь. В результате средняя временная сложность вычислительного процесса определяется по выражению

+ Яа <Г? +Я$ ¿V +Я6 +?7 +Яг +Як

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

- операционные части исследуемых ОВС выполняют однотипные операции;

- настройка операционной среда выполняется устройством управления ОВС, а ход выполнения операции, в операционной части ОВС (04 ОВС), определяется промежуточными значениями обрабатываемых данных.

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

Аппаратные затраты на реализацию ОЧ ОВС в позиционной системе счисления и ОВС в СОК рассчитываются по данным, частично представленным в табл. 1.

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

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

Теоретические исследования, проведенные в данной главе, доказывают целесообразность использования сумматоров ОВС на базе СОК, так как они обеспечивают увеличение быстродействия вычис-

лений при сокращении аппаратных затрат операционной части вычислителя (табл. 2).

Таблица I

Аппаратные затраты на реализацию ОВС

Разрядность данных, поступивших на обработку в позиционную ОВС 1|| || | я в* 1 и й 3 т я а II 111* я « 2. д, 3 ¡1 Количество ячеек ОВС в позиционной системе счисления, необходимое для обработки данных Ш 3 г о - и к о ¡3 н 0 Й Й1 11 3 II | м1 81 а Ю о ю 5 о ч й 3 § 1 5 ° В. и Количество ячеек ОВС в СОК, необходимое для обработки данных

К 8x8 64 1+7 1x3 и 7x7 50

16 16x16 256 2+7 2x6 и 7x7 65

32 32x32 1024 4-7+6+2 7x7 и бхб и 1x3 235

64 64x64 4096 1+2 6+8-7 1x3 и 6x6 и 7x7 467

128 128x128 16384 8-7+7-6+ 7-5+2*4+2-3+1 7x7 и 6x6 я 5x5 и4х4 и 3x3 и 1x3 872

Таблица 2

Временные затраты на реализацию алгоритмов сложения чисел с фиксированной точкой

Разрядность данных, биты Сумматор в СОК, число шагов вычислительного процесса Сумматор в позиционной системе, счисления, число шагов вычислительного процесса

8 18,5 21

16 18,5 37

32 18,5 69

64 18,5 133

128 18,5 261

На основании теоретических исследований разработана структура

сумматора [1] на базе ОВС в СОК (рис. 3). ОВС содержит Л'2 полных сумматоров - в каждом столбце ОВС по N сумматоров, где N — разрядность обрабатываемых данных; а\, а2, аЗ, 61, Ь2, АЗ, с1, с2, сЗ ~ группа информационных входов; л1, з2> ¿3,р\,р2,р3 - группа

Рис. 3. Пример выполнения сложения в ОВС в СОК

информационных выходов. Элементы И и элемент ИЛИ« — представляют собой коммутаторы между столбцами; jyl, >2, уЗ - управляющие входы коммутатора между столбцами для включения каналов переносов с выходов переносов сумматоров предыдущего столбца на входы переноса сумматоров следующего столбца.

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

Режим коммутации всегда выполняется первым, так как он является режимом настройки, определяющим, по какому модулю будет выполняться арифметическая операция. Рис. 3 иллюстрирует пример работы ОВС по модулю 5, для пего на входы >>1, у2, уЗ подается управляющий вектор «001», включающий цепи переносов сумматора SM5 и SM8, далее выполняется операция сложения над операндами А = 4ю и В = 4ю, для этого на группу входов а 1, dl, стЗ подается первое слагаемое, на группу входов 61, ¿2, ¿3 подается второе слагаемое, на группу информационных входов с\, с2, сЗ подается сигнал «0». Частичные результаты сложения, полученные в каждом столбце, выделены пунктирной линией. Окончательный результат формируется на группе выходов суммы Jj-sj, что соответствует равенству 3 = 8(mod 5).

Теоретические расчеты подтверждаются экспериментальным моделированием сумматоров ОВС СОК на ПЛИС ЭраЛапЗ (табл. 3).

Таблица 3

Временные и аппаратные затраты алгоритмов сложения чисел с фиксированной точкой реализованных на базе ПЛИС

Разрядность данных, биты Сумматор в СОК Сумматор в позиционной системе счисления

Временная задержка обработки данных, не Аппаратные затраты, количество логических ячеек ПЛИС Временная задержка обработки данных, не Аппаратные затраты, количество логических ячеек ПЛИС

8 12,5 31 22,5 39

16 17,5 43 45 156

32 20 146 90 , 624

64 20 285 180 2496

128 20 536 360 9984

В результате проведенного во второй главе диссертационной работы практического исследования и анализа:

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

2. Установлено, что использование в параллельно-конвейерных сумматорах с настраиваемой логикой алгоритмов арифметического сложения чисел с фиксированной точкой, сконструированных в базисе систем счисления в остаточных классах, обеспечивает повышение скорости вычислений в среднем в 18 раз при использовании форматов данных более 128 разрядов, примерно в 3 раза при использовании форматов данных менее 64 разрядов и на 20 % при обработке 8-разрядных данных.

3. Показано, что использование базиса модулярной арифметики при построении конвейерных сумматоров обеспечивает сокращение аппаратных затрат примерно в 18 раз при форматах данных более 128 разрядов и в среднем в 4 раза при использовании форматов менее 64 разрядов.

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

5. Показано, что временная сложность выполнения операции арифметического сложения чисел с фиксированной точкой при различных форматах данных, рассчитанная теоретически, полностью совпадает с результатами экспериментального моделирования разработанных технических решений модулярно-конвейерных сумматоров с настраиваемой логикой, реализованных в среде САПР ALDEC ACTIVE HDL на микросхемах XILINX SPARTAN 3.

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

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

Таблица 4

Временные затраты на реализацию алгоритмов умножения чисел с фиксированной точкой

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

8 18.5 21

16 18,5 37

■ 32 18,5 69

64 18,5 133

128 18,5 261

На основании теоретических исследований разработана структура устройства умножения на базе ОВС в СОК. Основой предложенного решения является ячейка однородной структуры (ЯОС) [2], реализующая систему логических функций:

i = / í; k-bth,

ас+D ■= Q,(I) ív 0i(0¿_v_b! h

F = m(,Q,bcvQ¡ bcvQ, bevQ,bc)w (15)

va(abcva6eva6cva¡!c)v

vj'íyicvyücvj'icvj'ie);

G = m(Q, bcvQtbcvQibcvQ, bc)v va (a b с vab cvab с va b c)v v y (y b с v b с v j> Ь с v y t с); i = J(A»víf(avjiv m)i

где л, >>, f, m, h, d - управляющие сигналы ЯОС, поступающие на одноименные входы; а, Ь, с — информационные сигналы, поступающие на одноименные входы; s, р - сигналы, формируемые на соответствующих информационных выходах; z и к — сигналы, формируемые на соответствующих выходах управления; QiO) — состояние триггера ЯОС; F и G — сигналы, формируемые на выходе суммы и переноса сумматора ЯОС.

Основными режимами работы ОВС является: режим настройки ОВС, режим загрузки и режим выполнения арифметического умножения.

Режим настройки ОВС (рис. 4) решает задачу настройки ОВС на работу с заданным модулем, для чего используются коммутаторы, расположенные между соседними столбцами. Для настройки рабочего модуля среды на управляющие входы Y¡...Y„ подается вектор, единичные биты которого включают канал коррекции Н—К промежуточных результатов вычисления и конечного результата.

Режим загрузки данных в триггеры ЯОС ОВС (см. рис. 4) решает задачу загрузки в ЯОС ОВС множимого, для чего на группу информационных входов А\...А„ первого столбца подается вектор данных, необходимых для загрузки, а на управляющий вход L подается активный сигнал «1». В результате данные с группы входов A¡...A„ первого столбца считываются в триггеры ОВС по каналам A-Z. Пример выполнения операции загрузки данных представлен также на рис.4, где на входы А\-Аг подан вектор «110», который по активному сигналу на управляющем входе L = 1 сохраняется в ЯОС ОВС,

Рис. 4. Пример реализации операций настройки и загрузки в ОВС Режим выполнения арифметического умножения представлен на рис. 5,о-в, где приведен пример операции умножения по модулю 7ю, при этом множимое равно 6ю (рис, 5,а), а множитель равен 5ю. Предварительно ОВС была настроена на работу с модулем 7 (см. рис. 4), и в ЯОС ОВС были занесены значения множимого. На выходах ¿1-.Г3 последнего столбца (рис. 5,в) получается окончательный результатом^ , что равно 5-6 = 30 = 2(тос17) .

а

Рис. 5. Пример реализации операции умножения в ОВС (начало)

£

коррекция сложить

«

Рис. 5. Пример реализации операции умножения в ОВС (окончание)

Теоретические расчеты подтверждаются практической реализацией ОВС СОК на ПЛИС ЭраЛапЭ (табл. 5).

В результате проведенного в третьей главе диссертационной работы практического исследования и анализа:

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

Таблица 5

Временные и аппаратные затраты на реализацию алгоритмов умножения чисел с фиксированной точкой, реализованных на Базе ПЛИС

Разрядность данных, биты Устройство умножения в СОК Устройство умножения в позиционной системе счисления

Временная задержка обработки данных, не Аппаратные затраты, количество логических ячеек ПЛИС Временная задержка обработки данных, не Аппаратные затраты, количество логических ячеек ПЛИС

8 12,5 31 22,3 39

16 17,5 43 45 156

32 20 146 90 624

64 20 285 180 2496

128 20 536 360 9984

2. Установлено, что использование в параллельно-конвейерных устройствах умножения с настраиваемой логикой, алгоритмов арифметического умножения чисел с фиксированной точкой, реализованных в базисе систем счисления в остаточных классах, обеспечивает повышение скорости вычислений примерно в 12 раз при использовании форматов данных более 12S разрядов; в среднем в 3 раза — при использовании форматов данных менее 32 разрядов; при использовании 8-разрядного формата преимущество СОК перед позиционной арифметикой составляет 15 %.

3. Показано, что использование базиса модулярной арифметики при построении конвейерных устройств умножения обеспечивает сокращение аппаратных затрат в среднем в 18 раз при форматах более 128 бит; а при использовании форматов менее 64 разряда в среднем в 2...4 раза.

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

5. Показано, что временная сложность выполнения операции арифметического умножения чиссл с фиксированной точкой, при различных форматах данных, рассчитанная теоретически по предложенному в первой главе диссертации формальному способу, полностью совпадает с результатами экспериментального моделирования разработанных технических решений модулярно-конвейерных сумматоров с настраиваемой логикой, реализованных в среде САПР ALDEC ACTIVE HDL на микросхемах XILINX SPARTAN 3.

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

Теоретические исследования доказывают целесообразность использования в АЛУ ОВС на базе СОК устройств деления при обработке данных свыше 64 разрядов, так как они обеспечивают увеличение быстродействия вычислений при сокращении аппаратных за* трат операционной части вычислителя только в данном случае. При использовании форматов менее 64 разрядов целесообразности в использовании устройств деления в СОК нет (табл. 6).

Таблица 6

Временные затраты на реализацию алгоритма деления

Разрядность данных, число бит Устройство деления в СОК, число тактов машинного времени Устройство деления в позиционной системе счисления, число тактов машинного времени

8 160 30

16 160 54

32 160 102

64 160 198

128 160 390

На основании теоретических исследований разработана структура устройства деления на базе ОВС в СОК (рис. 8), где вычислительные блоки — Блок А и Блок В являются набором матриц с клеточной топологией, в которых выполняется процесс обработки делимого и делителя по заданным модулям.

РЕЗУЛЬТАТ

Рис. 8. Структура устройства деления на базе ОВС в СОК

Данные в блоки поступают по шинам данных А и В, разрядность которых определяется модулями, по которым работают вычислительные матрицы. Управляющий сигнал «Конец итерации» определяет зависимость вычислительного процесса в Блоке А от результата вычислений в Блоке В: как только результат в Блоке В станет равным 1 - в Блок А требуется подать сигнал «Конец итерации». Устройство управления предназначено для контроля вычислительного процесса в Блоке В и Блоке А и однозначного определения промежуточного результата деления, так как для однозначного определения частного требуются дополнительные характеристики числа — характер и след числа. Данные характеристики определяет устройство управления. Корректор - устройство формирования промежуточного частного и анализа продолжения или окончания процесса деления. Шина данных промежуточного частного при условии, что деление не завершено, передает промежуточное частное в Блок А для выполнения следующей итерации деления. Функционально корректор представляет собой набор сумматора — вычитателя и умножителя. Сумматор-накопитель складывает поступающие к нему промежуточные частные, тем самым накапливая конечный результат, который поступает на шину данных «РЕЗУЛЬТАТ» после подачи управляющего сигнала «Конец деления».

Теоретические расчеты подтверждаются практической реализацией ОВС СОК на ПЛИС ЗраПапЗ (табл. 7).

Таблица 7

Временные и аппаратные затраты на реализацию алгоритма деления чисел с фиксированной точкой,реялнзованного на ПЛИС

Разрядность данных, биты Устройство деления в СОК Устройство деления в позиционной системе счисления

Временная задержка результата относительно данных, не Аппаратные затраты, количество логических ячеек ПЛИС Временная задержка результата относительно данных, tic Аппаратные затраты, количество логических ячеек ПЛИС

8 135 639 37,5 273

16 195 834 52,5 1092

32 195 3015 97,5 4368

64 195 6100 195 17472

128 195 11205 390 69888

В результате проведенного в четвертой главе диссертационной работы практического исследования и анализа:

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

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

3. Показано, что использование базиса модулярной арифметики при построении конвейерных устройств деления обеспечивает сокращение аппаратных затрат в 6 раз при форматах более 128 разрядов, в среднем в 1 раза при использовании форматов 32.-.64 разряда, а при использовании форматов менее 16 бит увеличение аппаратных затрат по сравнению с аналогами в позиционной системе счисления составляет 1,5.. .3 раза.

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

5. Показано, что временная сложность выполнения операции арифметического деления чисел с фиксированной точкой при различных форматах данных, рассчитанная теоретически по предложенному в первой главе диссертации формальному способу, полностью совпадает с результатами экспериментального моделирования разработанных технических решений модулярио-конвейерных делителей с настраиваемой логикой, реализованных в среде САПР AL-DEC ACTIVE HDL, на микросхемах X1LINX SPARTAN 3.

В приложении приведены подробное описание статических, гетерогенных и однородных вычислительных блоков АЛУ, сведения и аналитические выражения по основным системам счисления и алгоритмам операций производимых в них, а также листинги программ на языке VHDL реализации ИУ АЛУ на базе ОВС в позиционной системе счисления и СОК.

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

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

2. Разработан параллельно-конвейерный сумматор с настраиваемой логикой для арифметического сложения чисел с фиксированной точкой в базисе систем счисления в остаточных классах, обеспечивающий повышение скорости вычислений в 18 раз при использовании форматов данных более 128 разрядов, в 3 раза при использовании форматов данных менее 32 разрядов, на 20% при обработке 8-разрядных данных. При этом конвейерный сумматор обеспечивает сокращение аппаратных затрат в 18 раз при форматах более 128 разрядов, в 2 раза при использовании форматов менее 32 разрядов.

3. Разработано параллельно-конвейерное устройство умножения с настраиваемой логикой для арифметического умножения чисел с фиксированной точкой, реализованных в базисе систем счисления в остаточных классах, обеспечивающее повышение скорости вычислений в 12 раз при использовании форматов данных более 128 разрядов, в 3 раза при использовании форматов данных менее 32 разрядов, на 15 % при обработке 8-разрядных данных. При этом обеспечивается сокращение аппаратных затрат при форматах более 128 разрядов в 18 раз, при использовании форматов менее 32 разрядов в среднем в 4 раза.

4. Разработано параллельно-конвейерное устройство деления с настраиваемой логикой для арифметического деления чисел с фиксированной точкой, реализованное в базисе систем счисления в остаточных классах, которое обеспечивает повышение скорости вычислений в 2 раза при использовании форматов данных более 128 разрядов. При форматах менее 64 разрядов, предложенное решение неэффективно по сравнению с аналогичными решениями в позиционной системе счисления и понижает производительность вычислительной системы в среднем в 3 раза. При этом параллельно-конвейерное устройство деления обеспечивает сокращение аппаратных затрат в б раз при форматах более 128 разрядов, в 2 раза - при использовании фор-магов 32-64 разряда. При использовании форматов менее 16 разря-

дов увеличение аппаратных затрат по сравнению с аналогами в позиционной системе счисления составляет 1,5.„3 раза.

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

6. Получен набор аналитических выражений для количественной оценки временной и аппаратной сложности выполнения арифметических операций умножения, сложения, деления с фиксированной точкой в конвейерно-модулярных вычислительных структурах с настраиваемой логикой для арифметических вычислений. На основе полученной совокупности количественных оценок временной и аппаратной сложности различных ИУ АЛУ доказана перспективность и целесообразность реализации ИУ АЛУ на базе однородных вычислительных структур и применения в качестве базовой системы счисления в остаточных классах.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ СТАТЬИ, ОПУБЛИКОВАННЫЕ В ИЗДАНИЯХ,РЕКОМЕНДУЕМЫХ ВАК РФ

1. Федюнин Р. Н. Ячейка однородной вычислительной среды / Р. Н. Федюнин, В. С. Князьков // Патент РФ 2284568. - Опубл. 27.09.2006. - Бюл. № 27.

2. Федюнин Р. Н. Ячейка однородное среды / Р. И. Федюнин, В. С. Князьков // Патент РФ 2285285. - Опубл. 10.10.2006. - Бюл. № 28.

ПУБЛИКАЦИИ В ДРУГИХ ИЗДАНИЯХ

3. Федюнин Р. Н. Регулярная итеративно-битовая структура с перестраиваемой логикой для массовых арифметико-логических вычислений 1 Р. Н. Федюнин, В. С. Князьков И Актуальные проблемы науки и образования: Тр. Междунар. юбнл. симп. (АПНО-2003). - Пенза: Ийф.-изд. центр Пенз. гос. ун-та, 2003. - С. 402-406.

4. Федюнин Р. Н. Реализация арифметического сложения в регулярных итеративно-битовых структурах с перестраиваемой логикой для выполнения массовых арифметико-логических вычислений / Р, Н. Федюнин, В. С. Князьков И Новые информационные технологии и системы: Тр. VI науч.-техн. конф. - Пенза: Инф.-изд. центр Пенз. гос. ун-та, 2004. - С. 85-92.

5. Федюнин Р. Н, Современные направления микропроцессорных систем ПНИИЭИ // Специальная техника средств связи: Тр. науч.-техн. конф. — Пенза, 2004. - С. 250-254.

6. Федюнин Р. Н. Тенденции развития специализированной микропроцессорной техники в России И Антикризисное управление в России в современных условиях: Материалы конф. — М,: МГТУ им, Баумана, 2005. — С. 316-317.

7. Федюнин Р. Н. Однородная вычислительная структура для анализа битовых векторов / Р. Ы. Федюнин, B.C. Князьков // Наука. Технологии. Инновации: Материалы Всерос, науч. конф. молодых ученых. - Новосибирск: НГТУ, 2004. - С. 74-75.

8. Федюнин Р, Н. Процессорный элемент для организации гетерогенных вычислительных структур // Системы обработки информации и управления: Тез. докл. науч.-техн. конф. - Пенза: ОАО НПН «Рубин», 2005. - С. 24-25.

9. Федюнин Р. Н. Устройство анализа битовых векторов / Р. Н. Федюнин Я X Всерос. науч.-техв. конф. студентов,молодых ученых и специалистов. - Рязань: Рязанская гос. радиотехн. акад., 2005. - С. 75-76.

10. Федюнин Р. Н. Устройство массового сложения двоичных чисел // X Всерос. науч.-техн. конф. студентов, молодых ученых и специалистов. — Рязань: Рязанская гос. радиотехн. акад., 2005. -С. 76-78.

11. Федюнин Р. Н. Высокопроизводительный делитель И X Всерос. на-уч.-техн. конф. студентов, молодых ученых и специалистов.- Рязань: Рязанская гос. радиотехн. акад., 2005. — С. 79-80.

12. Федюнин Р. Н. Операция конкатенации в регулярных итеративно-битовых структурах с перестраиваемой логикой / Р. Н, Федюнин, В. С. Князьков И Актуальные проблемы современной науки: Тр. 1-го Междунар. форума. - Самара: СГГУ, 2005,- С. 124-127.

13. Федюнин Р. Н, Коммутационно-логическая ячейка для построения итеративно-битовых процессоров с перестраиваемой логикой / Р. Н. Федюнин, В. С. Князьков Н Актуальные проблемы современной науки; Тр. 1-го Междунар. форума. - Самара: СГГУ, 2005.-С. 127-130.

14. Федюнин Р. Н. Арифметическое умножение в регулярных итеративно-битовых структурах с перестраиваемой логикой / Р. Н. Федюнин, В. С. Князьков // Актуальные проблемы современной науки: Тр. 1-го Междунар. форума.-Самара: СГТУ,2005,-С. 130-132.

15. Федюнин Р. Н. Устройства конвейерно-параллельной обработки информации // Научное обозрение. - 2005. б. - С. 72-80.

16. Федюнин Р. Н. Способы организации и сложность массовых вычислений в конвейерных вычислительных системах // Научное обозрение. -2006.— № З.-С. 89—100.

17. Федюнин Р. И. Оценка пространственно-временной сложности и способы повышения скорости двоичных арифметических операций // Научное обозрение. - 2006. -ХаЗ.-С. 100-111.

Федюнин Роман Николаевич

КОНВЕЙЕРНО-МОДУЛЯРНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СТРУКТУРЫ С НАСТРАИВАЕМОЙ ЛОГИКОЙ ДЛЯ АРИФМЕТИЧЕСКИХ ВЫЧИСЛЕНИЙ

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

Редактор Т. В, Веденеева Технический редактор Н. А. Вьялкта

Корректор Ж. А. Лубенцова Компьютерная верстка С. П. Черновой

ИД № 06494 от 26.12.01 Сдано в производство 15.11.06. Формат 60х84'/1б. Бумага писчая. Печать офсетная. Усл. печ. л. 1,39. Заказ № 664. Тираж 100.

Издательство Пензенского государственного университета. 440026, Пенза, Красная, 40,

Содержание.

Введение.

1. Современные методы и способы реализации высокоскоростных арифметических вычислений.

1.1 Анализ влияния способов представления числовых данных на скорость арифметических вычислений и объем аппаратных затрат.

1.2. Структурно-аппаратные способы повышения быстродействия АЛУ.

1.3 Способы оценки производительности и эффективности вычислений функциональных блоков АЛУ.

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

2. Однородные конвейерно-модулярные сумматоры с настраиваемой логикой.

2.1 Марковские модели алгоритмов арифметического сложения чисел с фиксированной точкой и пути повышения скорости вычислений.

2.2 Однородные модулярно-конвейерные сумматоры с настраиваемой логикой.

2.3 Экспериментальное моделирование однородного модулярно-конвейерного сумматора с настраиваемой логикой.

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

3. Однородные конвейерно-модулярные устройства умножения с настраиваемой логикой.

3.1 Марковские модели алгоритмов арифметического умножения чисел с фиксированной точкой и пути повышения скорости вычислений.

3.2 Однородные модулярно-конвейерные устройства умножения с настраиваемой логикой.

3.3 Экспериментальное моделирование однородного модулярноконвейерного устройства умножения с настраиваемой логикой.

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

4. Однородные конвейерно-модулярные устройства деления с настраиваемой логикой.

4.1 Марковские модели алгоритмов арифметического деления чисел с фиксированной точкой и пути повышения скорости вычислений.

4.2 Однородные модулярно-конвейерные устройства деления с настраиваемой логикой.

4.3 Экспериментальное моделирование однородного модулярноконвейерного устройства деления с настраиваемой логикой.

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

Актуальность проблемы. Создание фирмой Intel первого микропроцессора в 1971 году положило начало эпохе всеобщей компьютеризации. «Благодаря микропроцессорам компьютеры стали массовым, общедоступным продуктом», - заявил Тед Хофф, один из изобретателей первого микропроцессора [54]. В микропроцессорах - наиболее сложных микроэлектронных устройствах, воплощены самые передовые достижения научной и инженерной мысли.

За чуть более чем четвертьвековую историю микропроцессоры прошли поистине гигантский путь. Первый чип Intel 4004 работал на частоте 750 КГц, содержал 2300 транзисторов и стоил около $200. Производительность его оценивалась в 60 тыс. операций в секунду. На сегодняшний день тактовая частота процессоров превысила 2 ГГц, количество транзисторов более 50 млн., пиковая производительность более 7 млрд. операций в секунду. Но и это еще не предел. К 2009 году прогнозируется достигнуть технологии, при которой количество транзисторов на кристалле составит порядка Ю9-Ю10. Что практически вплотную подходит к технологическому пределу современной технологической базы [34].

Выше сказанное объясняет поиск ведущими мировыми фирмами производителями (Intel, AMD, HP, IBM) путей увеличения производительности за счет разработки, как новых технологий изготовления кристалла, так и за счет повышения качества и количества устройств в микропроцессоре, в частности увеличение количества конвейеров, размеров КЭШ, количества исполняемых устройств (сумматоров, умножителей и.т.д.) в АЛУ - это количественные показатели; качественные, в свою очередь, предполагают разработку новых алгоритмов реализации функциональных блоков процессора и в первую очередь - арифметико-логического блока. Что в свою очередь предполагает возврат к фундаменту микропроцессорной техники - машинной арифметике, данная тенденция широко прослеживается в потоке диссертационных работ и публикаций, ведущих ученых запада - М. Флинн, С. Оберман и.т.д[1],[2], [79], [80], [81], [86], [90].

Анализ данных работ показывает что, несмотря на глубину проработки вопроса организации арифметико-логических блоков, остается еще много неизученных проблем. В частности - способность организации АЛУ на динамических функциональных блоках [12], а не статических, как это сделано практически во всех современных микропроцессорах и возможность использования эффективной системы счисления для ускорения выполнения операций в функциональных блоках АЛУ, в частности, системы счисления в остаточных классах [24].

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

Для достижения поставленной цели решаются следующие задачи:

2. Исследование способов организации вычислений с фиксированной точкой в современных арифметико-логических устройств АЛУ и повышения их быстродействия.

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

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

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

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

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

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

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

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

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

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

• арифметического сложения; эта структура отличается от известных тем, что при 64—128-разрядном представлении чисел скорость вычислений увеличивается в среднем в 3-13 раз при одновременном сокращении аппаратных затрат в среднем в 2-18 раз. н

• арифметического умножения; структура отличается от известных тем, что при 64-128-разрядном представлении чисел скорость вычислений увеличивается в среднем в 3-12 раз при одновременном сокращении аппаратных затрат в среднем в 4-18 раз.

• арифметического деления; структура отличается от известных тем, что при 64-128-разрядном представлении чисел скорость вычислений увеличивается примерно в 2 раза при одновременном сокращении аппаратных затрат в среднем в 2-6 раз.

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

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

Реализация и внедрение. Диссертация является теоретическим обобщением научно-исследовательских работ, выполненных автором в ГОУ ВПО ПГУ и ФГУП ПНИЭИ. Теоретические результаты работы применены при выполнении ОКР «Трамплин-АС» в ФГУП ПНИЭИ, о чем имеется акт внедрения. Достоверность полученных теоретических оценок подтверждается совпадением с результатами экспериментального моделирования вычислительных структур различного типа, проведенного в рамках ОКР «Трамплин-АС» в ФГУП ПНИЭИ.

По результатам исследований предложены технические решения, защищенные патентами на изобретение РФ [72], [73].

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

1. Модель арифметико-логического устройства с настраиваемой логикой.

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

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

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

5.Методика формальной оценки временной и аппаратной сложности реализации арифметико-логических операций с фиксированной точкой в однородных вычислительных структурах.

Апробация работы. Результаты работы обсуждались и докладывались на: VI Международной научно-технической конференции «Новые информационные технологии и системы», 2004, ПГУ, г. Пенза; научно-технической конференции «Специальная техника средств связи», 2004, ФГУП ПНИЭИ, г. Пенза; Всероссийской научной конференции молодых ученых «Наука, Технологии, Инновации», 2004, НГТУ, г. Новосибирск; X Всероссийской НТК студентов молодых ученых и специалистов, 2005, Рязанская гос. радиотехническая академия, г. Рязань; конференции «Антикризисное управление в России в современных условиях», 2005, МГТУ им. Баумана, г. Москва; 1-м Международном форуме «Актуальные проблемы современной науки», 2005, СГТУ, г. Самара.

Публикации. Основные результаты диссертационной работы опубликованы в 7 статьях, 8 сборниках тезисов докладов. По материалам работы получено два патента на изобретение РФ [72], [73].

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 136 наименований и четырех приложений. Основная часть работы изложена на 160 страницах машинописного текста. Работа содержит 76 рисунков и 36 таблиц.

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

В результате проведенного в четвертой главе диссертационной работы практического исследования и анализа:

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

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

3. Показано, что использование базиса модулярной арифметики при построении конвейерных устройств деления обеспечивает сокращение аппаратных затрат в 6 раз при форматах более 128 разрядов, в среднем в 2 раза при использовании форматов 32.64 разряда, а при использовании форматов менее 16 бит увеличение аппаратных затрат по сравнению с аналогами в позиционной системе счисления составляет 1,5.,.3 раза.

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

5. Показано, что временная сложность выполнения операции арифметического деления чисел с фиксированной точкой при различных форматах данных, рассчитанная теоретически по предложенному в первой главе диссертации формальному способу, полностью совпадает с результатами экспериментального моделирования разработанных технических решений модулярно-конвейерных делителей с настраиваемой логикой, реализованных в среде САПР ALDEC ACTIVE HDL, на микросхемах XILINX SPARTAN 3.

Заключение

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

1. Разработаны структурные и схемотехнические решения для АЛУ и ИУ АЛУ на базе конвейерно-модулярных вычислительных структур с настраиваемой логикой для арифметических вычислений, позволяющие повысить эффективность обработки данных с фиксированной точкой в среднем в 6 раз, при сокращении аппаратных затрат в среднем в 9 раз за счет реализации конвейерно-параллельной обработки информации в системе остаточных классов.

2. Разработан параллельно-конвейерный сумматор с настраиваемой логикой для арифметического сложения чисел с фиксированной точкой в базисе систем счисления в остаточных классах, обеспечивающий повышение скорости вычислений в 18 раз при использовании форматов данных более 128 разрядов, в 3 раза при использовании форматов данных менее 32 разрядов, на 20 % при обработке 8-разрядных данных. При этом конвейерный сумматор обеспечивает сокращение аппаратных затрат в 18 раз при форматах более 128 разрядов, в 2 раза при использовании форматов менее 32 разрядов.

3. Разработано параллельно-конвейерное устройство умножения с настраиваемой логикой для арифметического умножения чисел с фиксированной точкой, реализованных в базисе систем счисления в остаточных классах, обеспечивающее повышение скорости вычислений в 12 раз при использовании форматов данных более 128 разрядов, в 3 раза при использовании форматов данных менее 32 разрядов, на 15 % при обработке 8-разрядных данных. При этом обеспечивается сокращение аппаратных затрат при форматах более 128 разрядов в 18 раз, при использовании форматов менее 32 разрядов в среднем в 4 раза.

4. Разработано параллельно-конвейерное устройство деления с настраиваемой логикой для арифметического деления чисел с фиксированной точкой, реализованное в базисе систем счисления в остаточных классах, которое обеспечивает повышение скорости вычислений в 2 раза при использовании форматов данных более 128 разрядов. При форматах менее 64 разрядов, предложенное решение неэффективно по сравнению с аналогичными решениями в позиционной системе счисления и понижает производительность вычислительной системы в среднем в 3 раза. При этом параллельно-конвейерное устройство деления обеспечивает сокращение аппаратных затрат в 6 раз при форматах более 128 разрядов, в 2 раза - при использовании форматов 32-64 разряда. При использовании форматов менее 16 разрядов увеличение аппаратных затрат по сравнению с аналогами в позиционной системе счисления составляет 1,5.,3 раза.

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

6. Получен набор аналитических выражений для количественной оценки временной и аппаратной сложности выполнения арифметических операций умножения, сложения, деления с фиксированной точкой в конвейерно-модулярных вычислительных структурах с настраиваемой логикой для арифметических вычислений. На основе полученной совокупности количественных оценок временной и аппаратной сложности различных ИУ АЛУ доказана перспективность и целесообразность реализации ИУ АЛУ на базе однородных вычислительных структур и применения в качестве базовой системы счисления в остаточных классах.

162

1. Вашкевич Н.П., Сергеев Н.П. «Основы вычислительной техники» 2-е переработанное и дополненное издание, М., В. шк., 1988, -311 с

2. Вашкевич Н.П. Синтез микропрограммных управляющих автоматов: Учеб. пособие. Пенза: Пенз.политехн.ин-т,1990.

3. Головкин Б.А. Параллельные вычислительные системы. М., Наука; Главная редакция физмат литературы, 1980, - 517 с

4. Высокоскоростные вычисления, под редакцией ЯМ. Ковалика. М., Радио и связь, 1988,431с.

5. Коуги П.М., Архитектура конвейерных ЭВМ. М., Радио и связь 1981,357 с.

6. Карцев М.А,. Брик В.А. Вычислительные системы и синхронная арифметика, М., Радио и связь, 1981,-359 с.

7. Карцев М. А. Арифметика цифровых машин. М.: Наука, 1979. — 575 с.

8. Карцев М. А. Архитектура ЦВМ. — М.: Наука, 1978. — 295 с.

9. Строганов А. Проектирование топологии заказных КМОП БИС // Chip News. 2003. №2.

10. Ю.Волин В., Рудометов В., Столярский Е. Организация подкачки кода в VLIW-процессоре // Информационные технологии и вычислительные системы. 1999, № 1, с. 58-64.

11. И.Останевич А. В. Экспериментальное исследование поддержки предметных вычислений в архитектуре с явно выраженным параллелизмом // Информационные технологии и вычислительные системы. 1999, № 1

12. Костин А.Е., В.Ф. Шангин. Организация и обработка структур данных в вычислительных системах. М., Высшая школа, 1987 г., 245 с.

13. Князьков B.C. Аппаратное обеспечение конвейерных вычислительных систем. Пенза, Издательство Пензенского политехнического ин-та1992, уч.пособие, -79 с.

14. Князьков B.C., Бикташев Р.А. Параллельные вычислительные системы с ОКМД архитектурой. - Пенза,. РИО Пензенского политехническое ин-та, 1991, - уч. пособие, - 51 с.

15. Князьков B.C., Волченская Т.В. Классификация средств обработав данных, -Деп.рук., ВИНИТИ, N 8873-В88 от.21.12.88, Минвуз РСФСР, Пенза, Пензенский политехнический ин-т, 1988, 24 с.

16. Князьков B.C., Волченская Т.В. Способы построения конвейерных вычислительных структур с управлением коммутации потоков данных, -Деп.рук, ВИНИТИ, N 5581-В9Д от.31.10.90, Минвуз РСФСР, Пенза, Пензенский политехнический ин-т, 1988, 10 с.

17. Князьков B.C., Волченская Т.В. Быстродействующие процессоры на базе однородных сред.// В кн.: Распараллеливание обработки информации; Тез.докл. VII Всесоюз.шк. семинара 9-14 окт. 1989 года, Львов. Львов, >89,с.2,4.

18. Плотников А.В, Князьков B.C., Волченская Т.В. Основные типы архитектур средств обработки данных // Электронное моделирование, N 2,989, с. 38-42.

19. Престон К. и др. Основы клеточной логики с приложениями к образке изображений в медицине // ТИИЭР, т.67, N 5, 1979, с. 149-183.

20. Прангишвнли И.В. и др. Параллельные вычислительные системы. -М, Энергоатомиздат, 1983,311 с.

21. Калмыков И.А, Бережной В.В, Оленев А.А. «Систолический процессор ДПФ с коррекцией ошибки». Патент РФ № 2018950 // Открытия. Изобретения, 1994. Бюл. №16.

22. Червяков Н.И, Сахнюк П.А, Шапошников А.В. «Иерархическая модульная нейронная сеть с деградацией структуры, функционирующая в СОК» // Нейрокомпьютер, 2000. № 2. С. 52-62.

23. Акушский И.Я., Юдицкий Д.И. «Машинная арифметика в остаточных классах.» М., Сов.Радио, 1968, 439 с.

24. Акушский И.Я., Амербаев В.М., Пак И.Т. «Основы машинной арифметики комплексных чисел.» Алма-Ата, Наука, 1973, 192 с.

25. Синьков М.В., Синькова Т.В., Федоренко А.В., Чапор А.А. «Нетрадиционная система остаточных классов и ее основоположник И. Я. Акушский» Киев, Украина 2005

26. Синьков М.В., Губарени Н.М. «Непозиционные представления многомерных числовых систем.» Киев, Наукова думка, 1977, стр. 149

27. В.Г. Евстигнеев «Недвоичные компьютерные арифметики» Зеленоград, 5-я НТК «Немодулярная арифметика», 2005г, стр. 34 36.

28. Евстигнеев В.Г. Евстигнеева О.В. «Устройство для сложения п-разрядных чисел в избыточной системе счисления.» Авторское свидетельство № 1188731.

29. Евстигнеев В.Г. «Сумматор в знакоразрядной позиционно-остаточной системе счисления.» Авторское свидетельство № 1383349.

30. А.А. Евдокимов «Реализация модулярных нейронных вычислительных структур на базе ПЛИС» Зеленоград, 5-я НТК «Немодулярная арифметика», 2005г, стр. 32 34.

31. С. А. Инютин «Модулярные вычисления для задач большой алгоритмической сложности» Зеленоград, 5-я НТК «Немодулярная арифметика», 2005г, стр. 90 96.

32. В.П. Ирхин «Табличная реализация операций модулярной арифметики» Зеленоград, 5-я НТК «Немодулярная арифметика», 2005г, стр. 105 107.

33. М.Д. Корнев "О структурных решениях в проекте ЭВМ 5Э53" Зеленоград, 5-я НТК «Немодулярная арифметика», 2005г, стр. 107 111.

34. Н. Музыченко «Методы синтеза логических схем модульного контроля в унитарных непозиционных двоичных кодах» Зеленоград, 5-я НТК «Немодулярная арифметика», 2005г, стр. 111-115.

35. Ю.Д. Полисский «Сравнение чисел в системе остаточных классов» 5-я НТК «Немодулярная арифметика», 2005г, стр. 122- 127.

36. А. Финько «Параллельные логические вычисления — прикладная область модулярной арифметики» « 5-я НТК «Немодулярная арифметика», 2005г, стр. 128- 138.

37. Авгуль J1.B. Высокопроизводительные системы параллельной обработки информации / Авгуль J1.B., Белоус A.M., Гречишников А.И. // Под ред. Грицыка В.В. Киев., 1988.-286 с.

38. Поспелов Д. А. Введение в теорию вычислительных систем. «Советское радио», 1972, 289 с.

39. ДроздовЕ. А., Пятибратов А. П. Основы построения и функционирования вычислительных систем. «Энергия», 1973., 321 с.

40. Липаев В. В., Колин К. К., Серебровский Л. А. Математическое обеспечение управляющих ЦВМ. «Советское радио», 1972., 458 с.

41. Липаев В. В., Яшков С. С. Эффективность методов организации вычислительного процесса в АСУ. «Статистика», 1975., 121 с.

42. Бусленко Н. П., Калашников В. В., Коваленко И. Н. Лекции по теории сложных систем. «Советское радио», 1973., 66 с.

43. Снапелев Ю. М., Старосельский В. А. Моделирование и управление в сложных системах. «Советское радио», 1974.

44. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения. Пер. с англ. «Мир», 1965.

45. Саати Т. JI. Элементы теории массового обслуживания и ее приложения. Пер. с англ. «Советское радио», 1971.

46. Голубков Ю. А. Вероятностные модели последовательного выполнения алгоритма. «Труды семинара отдела структурных и логических схем». Сб. № 5. М., ИТМиВТ АН СССР, 1968.

47. Голубков Ю. А. Анализ вычислительной трудоемкости алгоритма и некоторые смежные задачи. «Труды семинара отдела структурных и логических схем». Сб. ,№ 5. М., ИТМиВТ АН СССР, 1968

48. Лавров С. С, Гончарова JI. И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. «Наука», 1971.

49. Дегтяр С. А. Выбор критерия для сравнения ЦВМ различных типов. «Труды Ленинградского политехнического института», 1971, № 320.

50. Евреинов Э. В., Косарев Ю. Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука. 1966. 308 с.

51. Корнеев В. Параллельные вычислительные системы. М.: Нолидж. 1999.

52. Кручинин С. Стандартные тесты измерения производительности // COMPUTER WEEK. Москва. 5(211), 8-14 февраля. 1996.

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

54. B.C.// ПензГУ 2004, Труды VI НТК «Новые информационные технологии и системы» стр. 85-92

55. Федюнин Р.Н. Современные направления микропроцессорных систем ПНИИЭИ, Пенза, 2004, Труды Научно- технической конференции «Специальная техника средств связи», стр. 250 254

56. Федюнин Р.Н. Тенденции развития специализированной микропроцессорной техники в России, Москва МГТУ им. Баумана, Материалы конференции «Антикризисное управление в России в современных условиях», 2005, стр. 316-317

57. Федюнин Р.Н. Однородная вычислительная структура для анализа битовых векторов /Федюнин Р.Н. Князьков B.C.// Новосибирск, НГТУ, 2004, Материалы всероссийской научной конференции молодых ученых «Наука, Технологии, Инновации», стр. 74 75

58. Федюнин Р.Н. Процессорный элемент для организации гетерогенных вычислительных структур, г. Пенза, ОАО НПН «Рубин», Тезисы докладов НТК «системы обработки информации и управления», 2005, стр. 24 -25.

59. Федюнин Р.Н. Устройство анализа битовых векторов, Рязань, Рязанская Гос. Радиотехническая академия, 2005, X Всероссийская НТК студентов молодых ученых и специалистов, стр. 75 76

60. Федюнин Р.Н. Устройство массового сложения двоичных чисел, Рязань, Рязанская Гос. Радиотехническая академия, 2005, X Всероссийская НТК студентов молодых ученых и специалистов, стр. 76 78

61. Федюнин Р.Н. Высокопроизводительный делитель, Рязань, Рязанская Гос. Радиотехническая академия, 2005, X Всероссийская НТК студентов молодых ученых и специалистов, стр. 79 80

62. Федюнин Р.Н. Операция конкатенации в регулярных итеративно-битовых структурах с перестраиваемой логикой. / Федюнин Р.Н. Князьков B.C.// Самара, СамГТУ, Труды 1-ого Международного форума «Актуальные проблемы современной науки», 2005, стр. 124-127

63. Федюнин Р.Н. Арифметическое умножение в регулярных итеративно-битовых структурах с перестраиваемой логикой. / Федюнин Р.Н. Князьков B.C.// Самара, СамГТУ, Труды 1-ого Международного форума «Актуальные проблемы современной науки», 2005,стр. 130-132

64. Федюнин Р.Н. Устройства конвейерно-параллельной обработки информации. Москва, «Научное обозрение», 6.2005, стр. 72-80

65. Федюнин Р.Н.Способы организации и сложность массовых вычислений в конвейерных вычислительных системах. Москва, «Научное обозрение», 3.2006, стр. 89-100

66. Федюнин Р.Н. Оценка пространственно-временной сложности и способы повышения скорости двоичных арифметических операций. Москва, «Научное обозрение», 3.2006, стр. 100-111

67. Федюнин Р.Н. Ячейка однородной вычислительной среды./Князьков B.C., Федюнин Р.Н. // Патент РФ № 2004136518/09 от 12 мая 2006г.

68. Федюнин Р.Н. Ячейка однородной среды./Князьков B.C., Федюнин Р.Н. // Патент РФ №2004136518/09 от 15 мая 2006г.

69. Matthew J. Adiletta, Richard L. Doucette, John H. Hackenberg, Dale H. Leuthold, and Dennis M. Litwinetz. «Semiconductor Technology in a High-Performance VAX System.» Digital Technical Journal, 2(4):43-60, Fall 1990.

70. Sohi G, Breach S., Vijaykumar T. Multiscalar Processors // Proceeding the 22nd Annual International Symposium on Computer Architecture, June 22—24, 1995, Santa Margherita Ligure, Italy, pp. 414 425.

71. Krishnan V, Torrellas J. A Chip-Multiprocessor Architecture with Multithreading // IEEE Transactions on Computers. 1999. Vol. 48, No 34

72. Kol R., Ginosar R. Kin: A High Perfomance Asynchronous Processor Architecture // Proceedings of International Conference on Supercomputing. July 13-17, 1998, Melbourne, Australia. pp. 433-440

73. A. R. Alvarez. «BiCMOS Technology and Applications.» Kluwer Academic Publishers, 1989.

74. G. Bewick, P. Song, G De Micheli, and M. J. Flynn. «Approaching a Nanosecond: a 32 Bit Adder» In Proceedings of the 1988 IEEE International Conference on Computer Design, pages 221-226, 1988.

75. Gary Bewick and Michael J. Flynn. «Binary Multiplication Using Partially Redundant Multiples.» Technical Report CSL-TR-92-528, Stanford University, June 1992.

76. A. D. Booth. A Signed Binary Multiplication Technique. Quarterly Journal of Mechanics and Applied Mathematics, 4(2):236-240, June 1951.

77. С. T. Chuang. NTL with Complementary Emitter-Follower Driver : A High-Speed Low-Power Push-Pull Logic Circuit. In 1990 IEEE Symposium on VLSI Circuits, pages 93-94. IBM Research Division, Thomas J. Watson Research Center, 1990.

78. L. Dadda. Some Schemes for Parallel Multipliers. Alta Frequenza, 36(5):349—356, May 1965.

79. Bob Elkind, Jay Lessert, James Peterson, and Gregory Taylor. A sub 10ns Bipolar 64 Bit Integer/Floating Point Processor Implemented on Two Circuits. In IEEE 1987 Bipolar Circuits and Technology Meeting, pages 101-104, 1987.

80. G. Goto, T. Sato, M. Nakajima, and T. Sukemura. A 54*54-b Regularly Structured Tree Multiplier. IEEE Journal of Solid-State Circuits, 27(9): 12291236, September 1992.

81. IEEE Standard for Binary Floating-Point Arithmetic, 1985. ANSI/IEEE Std 7541985.

82. Norman P. Jouppi. «MultiTitan Floating Point Unit.» In MultiTitan: Four Architecture Papers. Digital Western Research Laboratory, April 1988.

83. Earl E. Swartzlander Jr., editor. Computer Arithmetic, volume 1. IEEE Computer Society Press, 1990.

84. H. Ling. High-Speed Binary Adder. IBM Journal of Research and Development, 25(2 and 3): 156-166, May 1981.

85. L. MacSorley. «High-Speed Arithmetic in Binary Computers.» Proceedings of the IRE, 49(1):67-91, Jan 1961.

86. Meta-Software. «HSPICE User's Manual» H9001. Meta-Software Inc., 1990.

87. Motorola. «MECL System Design Handbook. Motorola Semiconductor» Products Inc., 1988.

88. Michael S. Paterson and Uri Zwick. Shallow Multiplication Circuits. « In 10th Symposium on Computer Arithmetic », pages 28-34, 1991.

89. Marc Rocchi, «High Speed Digital 1С Technologies.» Artech House, 1990.

90. M. R. Santoro, G. Bewick, and M. A. Horowitz. «Rounding Algorithms for IEEE Multipliers» In Proceedings of 9th Symposium on Computer Arithmetic, pages 176-183, 1989.

91. Mark Santoro. «Design and Clocking of VLSI Multipliers» PhD thesis, Stanford University, Oct 1989.

92. Mark Santoro and Mark Horowitz. «SPIM: A Pipelined 64x64b Iterative Array Multiplier» IEEE International Solid State Circuits Conference, pages 35-36, February 1988.

93. N. R. Scott. «Computer Number Systems & Arithmetic» Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1985.

94. С. E. Shannon. «А Symbolic Analysis of Relay and Switching Circuits» Trans. Am. Inst. Electr. Eng., 57:713-723, 1983.

95. С. E. Shannon. The Synthesis of Two-Terminal Switching Circuits. Bell Syst. Tech. J., 28(1), 1949.

96. J. Sklansky. «Conditional Sum Addition Logic» Transactions of the IRE, EC-9(2):226-230, June 1960.

97. Naofumi Takagi, HirotoYasuura, and ShuzoYajima. «High-speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree» IEEE Transactions on Computers, C-34(9), Sept 1985.

98. JefferyY.F. Tang and J. Leon Yang. «Noise Issues in the ECL Circuit Family» Technical report, Digital Western Research Laboratory, January 1990.

99. Stamatis Vassiliadis. «Six-Stage 64-Bit Adder» IBM Technical Disclosure Bulletin, 30(6):208-212, November 1987.

100. StamatisVassiliadis. «Adders With Removed Dependencies» IBM Technical Disclosure Bulletin, 30(10):426-429, March 1988.

101. Stamatis Vassiliadis. «А Comparison Between Adders with New Defined Carries and Traditional Schemes for Addition.» International Journal of Electronics, 64(4):617-626, 1988.

102. C. S. Wallace. «А Suggestion for a Fast Multiplier» IEEE Transactions on Electronic Computers, EC-13:14-17, February 1964.

103. S. Waser and M. J. Flynn. «Introduction to Arithmetic for Digital Systems Designers.» Holt, Rinehart andWinston, 1982.

104. A. Weinberger. «4-2 Carry-Save Adder Module.» IBM Technical Disclosure Bulletin, 23(8):3811-3814, January 1981.

105. A. Weinberger and J. L. Smith. «А One-Microsecond Adder Using One-Megacycle Circuitry» IRE Transactions on Electronic Computers, EC-5:65-73, June 1956.

106. S. Winograd. «On the Time Required to Perform Addition» Journal of the ACM, 12(2):227—285, 1995.

107. S. Winograd. «On the Time Required to Perform Multiplication» Journal of the ACM, 14(4):793—802, 1967.

108. Gary W. Bewick «Fast multiplication algorithms and implementation» a dissertation submitted to the department of EEC of Stanford University for the degree of doctor of philosophy February 1994

109. Beuchat J.-L, Muller J.-M. Modulo «Multiplication-addition: algorithms and FPGA implementation» // ELECTRONICS LETTERS 27th May 2004 Vol. 40 No. 11.

110. Batcher K. STARAN Parallel Processor System Hardware // 1974 National Computer Conference, AFIPS Conference Proceedings, Vol. 43. — pp. 405—410.

111. C. S. Wallace. A Suggestion for a Fast Multiplier. IEEE Transactions on Electronic Computers, EC-13:14-17, February 1964.

112. A. Weinberger and J. L. Smith. A One-Microsecond Adder Using One-Megacycle Circuitry. IRE Transactions on Electronic Computers, EC-5:65-73, June 1996.

113. D. E. Dadda. A Fast Multiplier. IEEE Transactions on Electronic Computers, EC-13:20-27, March 1964.

114. Eduardo Costa, Sergio Bampi, Jos'e Monteiro A New Pipelined Array Architecture for Signed Multiplication, IEEE Transactions on Electronic Computers, EC-17:78-85, March 1996.

115. Eric Schwarz, Revisions to the IEEE 754 Standard for Floating-Point Arithmetic, Proceedings of the 16th IEEE Symposium on Computer Arithmetic (ARITH'03), pp 45 46

116. Reto Zimmermann, Computer Arithmetic: Principles, Architectures, and VLSI Design, Integrated Systems Laboratory Swiss Federal Institute of Technology (ETH) CH-8092 Zurich, Switzerland, March 16, 1999

117. I. Koren, Computer Arithmetic Algorithms, Prentice Hall, 1993.

118. R. Zimmermann, Binary Adder Architectures for Cell-Based VLSI and their Synthesis, PhD thesis, Swiss Federal Institute of Technology (ETH) Zurich, Hartung-Gorre Verlag, 1998.

119. R. Zimmermann, "VHDL Library of Arithmetic Units", http://www.iis.ee.ethz.ch/~zimmi/arith lib.html.

120. W. N. Holmes, "Composite arithmetic: Proposal for a new standard", IEEE Computer, vol. 30, no. 3, pp. 65-73, Mar.

121. Z. Wang, G. A. Jullien, and W. C. Miller, "A new design technique for column compression multipliers", IEEE Trans. Comput., vol. 44, no. 8,-pp. 962-970, Aug.1995.