Организация параллельно-конвейерных сбис-структур с реконфигурируемой микроядерной архитектурой на основе арифметики разрядных срезов
На правах рукописи
ОСИНИН Илья Петрович
ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ СБИС-СТРУКТУР
С РЕКОНФИГУРИРУЕМОЙ МИКРОЯДЕРНОЙ АРХИТЕКТУРОЙ
НА ОСНОВЕ АРИФМЕТИКИ РАЗРЯДНЫХ СРЕЗОВ
Специальности:
05.13.15 – Вычислительные машины, комплексы и компьютерные сети
05.13.05 – Элементы и устройства вычислительной техники и систем управления
А в т о р е ф е р а т
диссертации на соискание ученой степени
кандидата технических наук
ПЕНЗА 2013
Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Вятский государственный университет».
| Научный руководитель | доктор технических наук, профессор Князьков Владимир Сергеевич |
| Официальные оппоненты: | Галанина Наталия Андреевна, доктор технических наук, профессор кафедры «Математическое и аппаратное обеспечение информационных систем» ФГБОУ ВПО «Чувашский государственный университет»; Бикташев Равиль Айнулович, кандидат технических наук, доцент кафедры «Вычислительные машины и системы» ФГБОУ ВПО «Пензенский государственный технологический университет» |
| Ведущая организация | ФГУП «Российский федеральный ядерный центр – Всероссийский научно-исследовательский институт экспериментальной физики», (г. Саров) |
Защита состоится «19» декабря 2013 г., в 13 часов, на заседании диссертационного совета Д 212.186.01 в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Пензенский государственный университет» по адресу: 440026, г. Пенза, ул. Красная, 40.
С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Пензенский государственный университет».
Автореферат разослан «____» ноября 2013 г.
Ученый секретарь
диссертационного совета Гурин Евгений Иванович
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Вычислительные мощности компьютеров наращиваются постоянно. Сегодня интенсивно ведутся научные исследования в области микроархитектуры процессоров нового поколения. Приоритетной задачей является построение арифметического устройства высокого быстродействия. Актуальной является задача повышения скорости вычислений путем совершенствования устройств на архитектурном уровне.
Одним из подходов к решению этой задачи является использование арифметики разрядных срезов и непозиционной системы счисления – системы остаточных классов (СОК).
Естественный параллелизм устройств, функционирующих на основе СОК, позволяет распараллелить процесс вычислений, как на программном, так и на аппаратном уровне, а модульность и однородность обеспечивает эффективное проектирование структур в сверхбольшом интегральном исполнении (СБИС).
С другой стороны, использование в вычислительном ядре СБИС-процессора реконфигурируемой однородной вычислительной среды (ОВС), то есть среды, аппаратура которой может реконфигурироваться, меняя свои функции, в зависимости от решаемых вычислительной системой задач, позволяет эффективно адаптировать архитектуру системы под структуру решаемой задачи, обеспечивая тем самым высокий уровень скорости вычислений. В общем случае ОВС представляет собой массив вычислительных ячеек структуры, которые объединены регулярными связями. Такая архитектура в силу своей регулярности весьма эффективна при проектировании и производстве устройств. При этом её производительность увеличивается практически пропорционально с увеличением числа ячеек в силу естественного параллелизма их работы.
Данной тематике посвящен ряд работ отечественных и зарубежных ученых – Варшавского В.И., Фета Я.И., Каляева A. B., Каляева И. А.,
Князькова В.С., Flynn M., Moore G., MacSorley L., Salown S. и других.
Однако сдерживающими факторами широкого использования структур с естественным параллелизмом являются отсутствие широкой элементной базы и формальных описаний устройств на языках проектирования аппаратуры. При этом остаются мало изученной возможность организации арифметико-логического устройства на основе динамически реконфигурируемого вычислительного пространства, а не статического, как в большинстве известных процессоров.
Цель диссертационной работы состоит в повышении быстродействия при сокращении аппаратных затрат однородных параллельно-конвейерных СБИС-структур с реконфигурируемой микроядерной архитектурой, выполняющих арифметические операции с фиксированной и плавающей точкой в базисе арифметики разрядных срезов.
Для достижения поставленной цели решаются следующие задачи:
1. теоретическое обоснование и исследование способов выполнения массовых операций мультиоперандного суммирования, умножения, деления и выравнивания мантисс на основе арифметики разрядных срезов;
2. теоретическое обоснование и исследование параллельно-конвейерных реализаций выполнения массовых операций мультиоперандного суммирования, умножения, деления и выравнивания мантисс на основе однородных высокопроизводительных СБИС-структур с реконфигурируемой микроядерной архитектурой;
3. разработка и исследование высокопроизводительного параллельно-конвейерного СБИС-процессора с реконфигурируемой микроядерной архитектурой для высокоскоростной модульной и немодульной арифметической обработки чисел с фиксированной точкой.
Объектом исследования диссертационной работы являются устройства выполнения арифметических операций с фиксированной и плавающей точкой в модулярном и позиционном форматах представления чисел на основе арифметики разрядных срезов, реконфигурируемые микроядерные СБИС-структуры для массовых параллельно-конвейерных арифметических вычислений, а также их характеристики по быстродействию и аппаратным затратам при технической реализации.
Предметом исследования являются способы и устройства ускоренного выполнения арифметических операций, способы организации параллельно-конвейерных СБИС-структур с реконфигурируемой микроядерной архитектурой, а также методы оценки их эффективности.
Соответствие паспорту научной специальности. Область исследования соответствует паспорту специальности 05.13.05 – Элементы и устройства вычислительной техники и систем управления, п. 1 "Разработка научных основ создания и исследования общих свойств и принципов функционирования элементов, схем и устройств вычислительной техники и систем управления" и п. 3 "Разработка принципиально новых методов анализа и синтеза элементов и устройств вычислительной техники и систем управления с целью улучшения их технических характеристик", и паспорту специальности 05.13.15 – Вычислительные машины, комплексы и компьютерные сети, п. 3 "Разработка научных методов и алгоритмов организации арифметической, логической, символьной и специальной обработки данных, хранения и ввода-вывода информации" и п. 4 "Разработка научных методов и алгоритмов организации параллельной и распределенной обработки информации, многопроцессорных, многомашинных и специальных вычислительных систем".
Методы исследования. Для решения поставленных в работе научных задач использованы основы теории чисел, абстрактной и линейной алгебры, дискретной математики, теории проектирования ЭВМ и систем, теории математического моделирования вычислительных устройств и систем, методы и средства экспериментального моделирования СБИС-структур и систем.
Достоверность и обоснованность полученных в работе результатов подтверждается корректностью применения математического аппарата, 6 патентами на новые способы и устройства вычислений в базисе арифметики разрядных срезов [12-17], результатами экспериментальной апробации на ПЛИС разработанных СБИС-структур, по результатам которой получены 2 свидетельства государственной регистрации программ конструирования СБИС-процессоров на языке описания VHDL [18, 19].
Научная новизна диссертационной работы заключается в создании новых способов выполнения массовых параллельно-конвейерных арифметических операций над массивами чисел с фиксированной и плавающей точкой в модулярном и позиционном формате представления чисел в базисе новых операций арифметики разрядных срезов и разработке технических средств их реализации на базе реконфигурируемых однородных вычислительных СБИС-структур и сред. Новыми являются следующие работы:
- способы выполнения арифметических операций мультиоперандного суммирования, умножения, деления нацело и выравнивания мантисс на основе арифметики разрядных срезов, отличающиеся тем, что операция, выполняемая последовательно над разрядами операндов, заменена параллельно исполняемыми операциями сжатия и анализа разрядных срезов операндов, что по сравнению с известными способами обеспечивает повышение скорости их выполнения;
- способы организации параллельно-конвейерных СБИС-структур с реконфигурируемой микроядерной архитектурой для выполнения арифметических операций мультиоперандного суммирования, умножения, деления нацело и выравнивания мантисс с фиксированной и плавающей точкой в модулярном и позиционном формате представления чисел в базисе новых операций арифметики разрядных срезов, которые при их технической реализации обеспечивают большее быстродействие и сокращение аппаратных затратах по сравнению с известными аналогами;
- организация многоядерного СБИС-процессора с реконфигурируемой микроядерной параллельно-конвейерной архитектурой для выполнения арифметических модульных и немодульных операций в базисе арифметики разрядных срезов над числами с фиксированной точкой в позиционной системе счисления и в системе остаточных классов. В отличие от известных аналогов, вычислительное ядро процессора динамически реконфигурируется на необходимое количество микроядер в зависимости от количества и разрядности обрабатываемых операндов путем его микропрограммной настройки, обеспечивая большее быстродействие и сокращение аппаратных затратах по сравнению с известными аналогами.
Основные научные положения, выносимые на защиту:
- способы выполнения арифметических операций мультиоперандного суммирования, умножения, деления нацело и выравнивания мантисс на основе арифметики разрядных срезов;
- организация параллельно-конвейерных микроядерных СБИС-структур для выполнения арифметических операций мультиоперандного суммирования, умножения, деления нацело и выравнивания мантисс с фиксированной и плавающей точкой в модулярном и позиционном формате представления чисел на базе предложенных способов;
- организация динамически реконфигурируемого многоядерного СБИС-процессора для выполнения модульных и немодульных операций над числами с фиксированной точкой.
Практическая ценность результатов диссертационной работы заключается в том, что применение новых параллельно-конвейерных СБИС- структур позволяет повысить скорость выполнения арифметических операций, уменьшить производственные и эксплуатационные расходы на аппаратуру.
Реализация и внедрение. Теоретические и практические результаты диссертационной работы внедрены (что подтверждается соответствующими актами о внедрении): в ФБГОУ ВПО «ВятГУ» (г. Киров) в рамках выполнения проекта по ФЦП «Научные и научно-педагогические кадры инновационной России» (2009-2013 годы), шифр №14.B37.21.0590, проекта по аналитической ведомственной целевой программе Министерства образования науки РФ «Развитие научного потенциала высшей школы» (2009-2010 годы), шифр №2.2.1.1/3302; в ООО "Центр компетенции и обучения" (г. Саров) в рамках выполнения проекта по ФЦП Министерства образования науки РФ «Исследование и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы», шифр №2012-2.4-07-524-0006-002; в учебный процесс ФБГОУ ВПО «ВятГУ». По результатам исследований предложены способы организации вычислений и технические решения СБИС-процессоров, защищенные патентами на изобретение РФ
[12-17] и свидетельствами об официальной регистрации программы для ЭВМ [18, 19].
Личный вклад. Все основные научные результаты, приведенные в диссертации и сформулированные в положениях, выносимых на защиту, получены автором лично.
Апробация результатов работы. Основные теоретические и практические результаты диссертационной работы обсуждались и докладывались на: двух Международных выставках информационных и телекоммуникационных технологий «CEBIT», Ганновер, Германия, 2011 г., 2013 г.; III, IV, V Испано-Российском Международном форуме по информационным и коммуникационным технологиям, 2010 г., 2011 г., 2012 г.; Международной суперкомпьютерной конференции «Научный сервис в сети интернет», Новороссийск, 2012 г.; XIV Международной конференции «Супервычисления и математическое моделирование», Саров, 2012 г.; IV Международной научной конференции «Суперкомпьютерные системы и их применение (SSA-2012)», Минск, Беларусь, 2012 г.; первом Национальном суперкомпьютерном форуме (НСКФ-2012), Переславль-Залесский, 2012 г.; трех Всероссийских научно-технических конференциях «Общество, наука, инновации», Киров, 2011 г., 2012 г., 2013 г.,; Всероссийской научной конференции «Проведение научных исследований в области обработки, хранения, передачи и защиты информации», Москва, 2011 г.; V сессии научной школы-практикума «Технологии высокопроизводительных вычислений и компьютерного моделирования», Санкт-Петербург, 2012 г.; VI Всероссийской молодежной научно-инновационной школы «Математика и математическое моделирование», Саров, 2012 г.; Всероссийской научно-практической конференции «Высокопроизводительные вычисления на графических процессорах», Пермь, 2012 г.; Международной молодежной конференция «Информационные системы и технологии», Москва, 2012 г.; XI научно-технической конференции «Молодежь в науке», Саров, 2012 г.
Публикации. По материалам диссертационных исследований опубликовано: 11 статей, из них 3 в ведущих рецензируемых журналах из перечня ВАК; 7 тезисов докладов; 6 патентов РФ на изобретение; 2 свидетельства на регистрацию программы для ЭВМ.
Объем и структура диссертации. Полный объем диссертации составляет 119 страниц, в том числе: 69 иллюстраций, 18 таблиц, 7 приложений, список литературы из 141 источников (в том числе 41 авторских).
СОДЕРЖАНИЕ РАБОТЫ
В первой главе приведена классификация современных высокопроизводительных вычислительных структур, на основе анализа которой выявлены пути повышения производительности. Например, актуальными способами повышения быстродействия являются подходы, основанные на применении естественного параллелизма вычислений.
Исследование параллелизма такого рода показало, что им обладает система счисления остаточных классов (СОК), где вычисления над исходным вектором X(m) по каждому модулю p1, p2,…pn для получения результата Y осуществляются независимо друг от друга (рисунок 1), однако, отсутствие эффективных программных и схемотехнических средств реализации немодульных операций является основной причиной ограниченного применения модулярных принципов обработки цифровой информации.
Рисунок 1 – Организация традиционной модулярной структуры
При этом остатки операндов по каждому модулю, а также промежуточные результаты выполнения немодульных операций являются позиционными числами, над которыми в большинстве случаев выполняются такие операции, как двухоперандное суммирование, мультиоперандное суммирование и умножение. Традиционные технические реализации устройств для их выполнения обладают гетерогенной структурой, что приводит к снижению быстродействия и сложности масштабирования.
Операция мультиоперандного суммирования является также актуальной и в современных вычислительных задачах, например, в вычислительной математике, кроме того, она является типовой, так как арифметические операции мультиоперандного вычитания, двухоперандные операции сложения, вычитания, умножения являются частными случаями мультиоперандного суммирования, в том числе и в СОК.
Естественным параллелизмом также обладают однородные вычислительные среды, обеспечивающие максимальный темп конвейерной обработки информации при простоте масштабирования структур и высокой технологичности их производства. Таким образом, перспективной задачей является реализация модулярных вычислительных структур на базе однородных вычислительных сред.
Вторая глава посвящена разработке способов мультиоперандного алгебраического суммирования массивов M целых положительных позиционных двоичных чисел [1, 9-11]. Эти способы могут быть применимы также в случае обработки чисел разного знака, чисел с плавающей точкой и при представлении чисел в системе остаточных классов. Их отличие от известных способов состоит в том, что последовательная операция суммирования заменяется параллельно исполняемыми: расчетами числа единиц в разрядных срезах, сжатиями разрядных срезов и пирамидальными выделениями переносов в разрядных срезах слагаемых.
Массив М представим приведенной ниже битовой матрицей A размерностью m строк и n столбцов, где m - число слагаемых, n – разрядность модулей чисел.
(1)
При таком представлении строка матрицы A является скалярным значением модуля числа в двоичном представлении, а столбец – разрядным срезом SRi чисел суммируемого массива M, i[1;n]. Каждый разрядный срез является одномерным булевым вектором из m элементов.
Предлагается выполнять обработку матрицы A не по строкам – операндам, как это реализуется в известных способах суммирования, а по столбцам – разрядным срезам операндов массива M.
Первый способ состоит в том, что в специализированной однородной вычислительной среде параллельно выполняется расчет числа единиц в разрядных срезах SRi в двоичном коде, i[1;n]. Разряды искомой суммы определяются из младшего разряда результата подсчета единиц в разрядных срезах слагаемых, остальные разряды являются переносами в следующий разрядный срез. Данный способ позволяет повысить быстродействие в N раз по сравнению с традиционным итерационным способом:
(2)
где m – количество слагаемых.
Ячейка однородной среды, входящая в состав СБИС-структуры, организующей данный способ, реализует систему логических функций:
(3)
где a, b – одноразрядные информационные входы, c – вход синхронизации,
Q1, Q2 – одноразрядные информационные выходы.
Временная сложность после заполнения конвейера m+q ступеней конвейера составляет:
(4)
где n – разрядность слагаемых, t – время срабатывания элемента И-НЕ, q=]log2m[. Аппаратная сложность составляет:
(5)
Второй способ отличается от первого тем, что параллельный расчет в разрядных срезах SRi производится в унитарном коде, что позволяет повысить быстродействие в m раз по сравнению с итерационным способом, i[1;n]. Разряды суммы двоичных векторов определяются из четности, либо нечетности разрядных срезов слагаемых, которые дополняются единицами переносов. Число переносов в i-й разрядный срез определяется половиной четного числа единиц (i-1)-го разрядного среза, i[2;n].
Ячейка однородной среды, входящая в состав СБИС-структуры, организующей данный способ, реализует систему логических функций:
(6)
где a, b – одноразрядные информационные входы, c – вход синхронизации,
Q1, Q2 – одноразрядные информационные выходы.
Временная сложность после заполнения конвейера m+2 ступеней конвейера составляет:
(7)
где n – разрядность слагаемых, t – время срабатывания элемента И-НЕ. Аппаратная сложность составляет:
(8)
Третий способ основан на операции пирамидального выделения переносов в разрядных срезах SRi, i[1;n]. Это операция заключается в том, что в специализированной однородной вычислительной среде параллельно выполняется свертка редукционным суммированием соседних пар разрядов исходного m-разрядного вектора с учетом (m-1)-разрядного вектора переносов С*. На каждом шаге свертки разрядность исходного вектора уменьшается и через p шагов свертки исходный вектор становится одноразрядным вектором B и (m-1)-разрядным вектором С переносов, которые являются результатами операции, p=log2m.
Ячейка однородной среды, входящая в состав СБИС-структуры, организующей данный способ, реализует систему логических функций:
(9)
где a, b – одноразрядные информационные входы, c – вход синхронизации,
s – одноразрядный информационный выход, q – канал переноса.
Временная сложность после заполнения конвейера ]log2m[ ступеней конвейера составляет:
(10)
где n – разрядность слагаемых, t – время срабатывания элемента И-НЕ. Аппаратная сложность составляет:
(11)
В конвейерном режиме работы быстродействие новых СБИС-процессоров для мультиоперандного суммирования не зависит от количества слагаемых. Простота масштабирования позволяет динамически изменять количество и разрядность слагаемых.
Благодаря простоте ячейки однородной вычислительной среды и параллельно-конвейерному режиму работы, достигается высокое быстродействие устройства.
На рисунке 2 приведен график зависимости временной сложности устройств от разрядности слагаемых, где n=64 – разрядность операндов, m=64 – количество операндов, t – время срабатывания элемента И-НЕ, Q – временная сложность. Например, для 64-х слагаемых с разрядностью 64 бита вычисления будут выполняться в 16 раз быстрее, чем в устройстве на базе итерационного способа с ускоренным переносом и в шесть раз быстрее, чем в устройстве на базе бинарного дерева и дерева Уоллеса.
Использование предложенных способов суммирования обеспечивает снижение уровня аппаратных затрат. На рисунке 3 приведен график зависимости аппаратной сложности устройств от разрядности слагаемых, где n=64 – разрядность операндов, m=64 – количество операндов. Например, для 64-х слагаемых с разрядностью 64 бита аппаратные затраты от двух до пяти раз меньше, чем в устройстве на базе итерационного способа с ускоренным переносом и от четырех до 40 раз меньше, чем в устройстве на базе бинарного дерева и дерева Уоллеса.
Рисунок 2 – График зависимости временной сложности устройств от разрядности слагаемых
Рисунок 3 – График зависимости аппаратной сложности устройств от разрядности слагаемых
Таким образом, наиболее выгодным с точки зрения соотношения быстродействия и аппаратных затрат является СБИС-процессор для мультиоперандного суммирования на базе пирамидального выделения переносов. С точки зрения регулярности структуры наиболее предпочтительным является СБИС-процессор на базе сжатия векторов, что обеспечивает высокую технологичность производства и простоту масштабирования вычислительной среды. С точки зрения скорости заполнения конвейера наиболее предпочтителен СБИС-процессор на базе анализа числа единиц.
В третьей главе исследована возможность применения разработанных мультиоперандных сумматоров в качестве устройств умножения и деления
[2, 6-8].
Операцию алгебраического умножения чисел можно представить в виде операции алгебраического суммирования n (2n)-разрядных частичных произведений, образующих массив М, где под j-ым частичным произведением Aj понимается множимое, сдвинутое на (j-1) разрядов влево (свободные разряды заполняются нулями) и логически умноженное на j-ый разряд множителя, где n – разрядность операндов, j[1,n]. Тогда для нахождения искомого произведения достаточно вычислить сумму разрядных срезов чисел массива M с помощью одного из рассмотренных способов мультиоперандного суммирования.
Ячейка однородной среды, входящая в состав СБИС-структуры, организующей данный способ, реализует систему логических функций:
(12)
где a, b, d – одноразрядные информационные входы, c – вход синхронизации,
Q1, Q2, Q3 – одноразрядный информационный выход. Временная сложность после заполнения конвейера ]log2m[ ступеней конвейера составляет:
(13)
где n – разрядность слагаемых, t – время срабатывания элемента И-НЕ, q=]log2m[. Аппаратная сложность составляет:
(14)
Предложен способ деления двоичных положительных чисел нацело, отличающийся от известных тем, что деление производится с помощью операции мультиоперандного суммирования по разрядным срезам, начиная с младших разрядов делителя. Операцию деления чисел можно представить в виде операции алгебраического суммирования n n-разрядных частичных делителей, образующих массив М, где под j-ым частичным делителем Aj понимается делитель, сдвинутый на (j-1) разрядов влево (свободные разряды заполняются нулями) и логически умноженный на j-ый разряд вычисляемого искомого частного, n – разрядность операндов, j[1,n].
Данный способ позволяет повысить быстродействие в N раз по сравнению с традиционным итерационным способом:
(15)
где n – разрядность операндов.
Временная сложность после заполнения конвейера ]log2m[ ступеней конвейера составляет:
(16)
где n – разрядность операндов, t – время срабатывания элемента И-НЕ. Аппаратная сложность составляет:
(17)
Предложена организация формирователя разрядных срезов операндов, который позволяет сводить операцию умножение и деление нацело к операции мультиоперандного суммирования. Также предложена организация вычислений с использованием разрядных срезов массивов чисел с плавающей точкой. Предложены структурные организации спецпроцессоров на базе однородных вычислительных сред, проведена оценка их эффективности по сравнению с известными техническими решениями.
Предложен способ параллельного выравнивания мантисс чисел, отличающийся от известных тем, что поиск наибольшей характеристики и последующее вычисление разности характеристик происходит параллельно и независимо по их разрядным срезам.
Ячейка однородной среды, входящая в состав СБИС-структуры, организующей данный способ, реализует систему логических функций:
(18)
где a, b – одноразрядные информационные входы, c – вход синхронизации, d – состояние внутреннего триггера, Q – одноразрядный информационный выход.
Временная сложность после заполнения конвейера m+q ступеней конвейера составляет:
(19)
где n – разрядность слагаемых, t – время срабатывания элемента И-НЕ. Аппаратная сложность устройства для выравнивания m операндов составляет:
(20)
Использование СБИС-структур, сконструированных на базе предложенных способов, обеспечивает повышение быстродействия, например, для 64-х разрядных операндов быстродействие алгебраического умножения в 64 раза выше, чем в устройстве на базе алгоритма Бута и в два раза выше, чем в умножителе Брауна; быстродействие деления без остатка в три раза выше, чем в устройстве деления на базе способа SRT; быстродействие выравнивания мантисс в пять раз выше при разрядности сомножителей n=256 бит и количестве операндов m=64, чем в устройстве на базе итерационного способа.
Аппаратные затраты сопоставимы с техническими решениями на базе алгоритма Бута и способа деления SRT, аппаратные затраты устройства алгебраического умножения в 25 раз меньше, чем в умножителе Брауна; аппаратные затраты устройства выравнивания на базе предложенного способа его в три раза меньше при разрядности сомножителей n=256 бит и количестве операндов m=64, чем для устройства на базе итерационного способа выравнивания.
Четвертая глава посвящена разработке вычислительных ядер, предназначенных для выполнения модульных и немодульных операций
на базе обработки массивов данных по разрядным срезам в системе
остаточных классов [3-5].
Разработана организация вычислительного ядра, предназначенного для выполнения как модульных (сложение, умножение, деление нацело), так и немодульных операций (прямое и обратное преобразование, вычисление приближенной позиционной характеристики, коррекция результата) на базе обработки массивов данных по разрядным срезам в системе остаточных классов.
При этом обеспечивается повышение быстродействия, например, в отличие от итерационного аналога обратного модулярного преобразователя, где выдача результата обеспечивается за время
(21)
а новое вычислительное ядро обеспечивает выдачу результата преобразования за
(22)
после заполнения N ступеней конвейера, где
(23)
где k – разрядность константы преобразования, p – количество оснований СОК, t – время срабатывания ячейки структуры, ]*[ – округление выражения * до большего целого.
В отличие от итерационного аналога, где выдача результата обеспечивается за nt для операций сложение, вычитание и n2t для операций умножение и деление нацело, вычислительная среда обеспечивает выдачу результата за один такт работы устройства после заполнения конвейера n+1 ступени конвейера, где n – разрядность основания системы остаточных классов
При разрядности позиционных операндов n=256 бит временные затраты предложенных СБИС-процессоров от 70 до 199 раз меньше чем для устройств на базе известных способов при сопоставимых аппаратных затратах.
Разработана динамически реконфигурируемая микроядерная архитектура СБИС-процессора для выполнения параллельно-конвейерных операций над числами с фиксированной точкой, включающая аппаратную реализацию предложенных способов выполнения арифметических операций. Его структурная схема приведена на рисунке 4.
Процессор имеет четыре ядра, выполняющие операции из набора команд, как в позиционной системе счисления, так и в системе остаточных классов.
Рисунок 4 - Структурная схема процессора
MIMD-архитектура с распределенной кэш-памятью позволяет выполнять массовую арифметико-логическую обработку чисел с фиксированной точкой. Микроархитектура процессора позволяет динамически изменять разрядность обрабатываемых операндов, что бывает необходимо для повышения точности в процессе вычислений. Например, каждое из четырех процессорных ядер может вести независимую обработку 32-разрядных операндов, либо они могут группироваться парами для обработки 64-разрядных чисел, либо все ядра могут объединиться для обработки 128-разрядных операндов.
Даная группировка возможна как для позиционной системы, так и СОК, причем, она не требует временных затрат, так как реконфигурация процессора происходит динамически и может выполняться до начала обработки каждой следующей пары операндов. Подобное техническое решение отсутствует как в современных универсальных микропроцессорах, так и в сопроцессорах. Данное решение поддержано патентом РФ [15] и зарегистрированным VHDL-кодом [19].
Другой отличительной особенностью микропроцессора является распараллеливание обработки каждой пары операндов на двух уровнях.
Первый уровень обеспечивается независимостью обработки по каждому основанию числа в СОК. Так, например, время вычисления 128-разрядного числа сокращается в 16 раз за счет одновременного вычисления по 20 восьмиразрядным остаткам исходных чисел (модулярность структуры).
Второй уровень обеспечивается пространственно-временным параллелизмом вычислений по каждому основанию на базе ОВС (систоличность структуры).
Таким образом, параллельно-конвейерное выполнение операций над независимыми остатками чисел позволяет сократить время вычислений до времени срабатывания одного логического элемента. Например, вычисления над числами разрядности 128, 64 и 32 бита выполняются одинаково быстро и на предельной частоте работы устройств, что недостижимо в известных аналогах, функционирующих в ПСС. В них быстродействие обеспечивается наращиванием количества ядер, что в итоге сильно сужает класс задач, так как необходимо избегать зависимостей по данным.
Для обеспечения своевременной подачи исходных операндов на входы арифметико-логического устройства предусмотрено повышение быстродействия кэш-памяти за счет 96-кратного расслоения доступа и частично-ассоциативного доступа, а также одновременного доступа в распределенные банки памяти, которые соответствуют независимым основаниям СОК.
Показано, что при выполнении операций в СОК временная сложность не зависит ни от типа операции, ни от разрядности операндов. Так, например, быстродействие операции суммирования двух 64-разрядных чисел в предлагаемом процессоре в 7,11 раз выше при выполнении операции в СОК по сравнению с ПСС. Аналогично, быстродействие умножения двух 64-разрядных чисел в 455,11 раз выше при выполнении операции этой в СОК.
В заключении приведены основные результаты диссертации.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В результате проведенных исследований в диссертации созданы новые способы и технические средства выполнения мультиоперандных арифметических операций в параллельно-конвейерных СБИС-структурах с реконфигурируемой микроядерной архитектурой.
- Разработаны параллельные способы вычисления суммы m чисел на базе операции подсчета количества единичных элементов, операции сжатия разрядных срезов, операции пирамидального выделения переносов в разрядных срезах. По сравнению с известным итерационным способом, они позволяют повысить быстродействие в m раз. Предложен способ умножения и способ деления нацело двоичных чисел на базе операции мультиоперандного суммирования, по сравнению с известным итерационным способом, они позволяют повысить быстродействие в n и n/log2n раз соответственно, где n – разрядность операндов.
- Разработаны параллельно-конвейерные реализации новых способов выполнения массовых операций мультиоперандного суммирования, умножения, деления и выравнивания мантисс на основе однородных высокопроизводительных СБИС-структур с реконфигурируемой микроядерной архитектурой. При этом обеспечивается повышение производительности, например, для мультиоперандного суммирования 64-х слагаемых с разрядностью 64 бита вычисления будут выполняться в 16 раз быстрее, чем в устройстве на базе итерационного способа с ускоренным переносом и в шесть раз быстрее, чем в устройстве на базе бинарного дерева и дерева Уоллеса. Использование предложенных способов обеспечивает снижение уровня аппаратных затрат, например, для мультиоперандного суммирования 64-х слагаемых с разрядностью 64 бита аппаратные затраты от двух до пяти раз меньше, чем в устройстве на базе итерационного способа с ускоренным переносом и от четырех до 40 раз меньше, чем в устройстве на базе бинарного дерева и дерева Уоллеса.
- Разработана архитектура модулярно-систолического процессора с реконфигурируемой микроядерной архитектурой. В отличие от аналогов, данное решение построено на базе параллельно-конвейерных СБИС-структур, где обеспечена возможность формирования нужного числа вычислительных ядер в зависимости от формата обрабатываемых операндов. Реализовано высокоскоростное прямое и обратное модулярное преобразование операндов, вычисления приближенной позиционной характеристики и арифметические операции, выполняемые, как в позиционной, так и в модулярной системе счисления. Показано, что при выполнении операций в СОК временная сложность не зависит ни от типа операции, ни от разрядности операндов. Так, например, быстродействие операции суммирования двух 64-разрядных чисел в предлагаемом процессоре в 7,11 раз выше при выполнении операции в СОК по сравнению с ПСС. Аналогично, быстродействие умножения двух 64-разрядных чисел в 455,11 раз выше при выполнении операции этой в СОК.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
ПУБЛИКАЦИИ В ИЗДАНИЯХ, РЕКОМЕНДУЕМЫХ ВАК РФ
|
|
|
ПУБЛИКАЦИИ В ДРУГИХ ИЗДАНИЯХ
|
|
|
|
|
|
|
ПАТЕНТЫ
|
|
|
|
|
|
СВИДЕТЕЛЬСТВА О РЕГИСТРАЦИИ ПРОГРАММ ДЛЯ ЭВМ
|
|
Научное издание
ОСИНИН Илья Петрович
Организация параллельно-конвейерных СБИС-структур
с реконфигурируемой микроядерной архитектурой
на основе арифметики разрядных срезов
Специальности:
05.13.15 – Вычислительные машины, комплексы и компьютерные сети
05.13.05 – Элементы и устройства вычислительной техники и систем управления
Подписано в печать 12.11.2013.
Формат 60841/16. Усл. печ. л. 1,04.
Тираж 110. Заказ № 2044.
__________________________________
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
«Вятский государственный университет»
610000, г. Киров, ул. Московская, 36.
Тел.: (8332) 64-23-56, http://vyatsu.ru
