В статье представлена организация перспективного арифметического модулярнологарифмического процессора. Ключевое отличие от аналогов состоит в использовании непозиционной системы счисления на базе однородных вычислительных сред, что распараллелило вычисления вплоть до разрядов операнда, существенно повысив скорость вычислений, а также привнесло ряд уникальных свойств, значительно повысив надежность процесса счета. Применение системы остаточных классов совместно с логарифмической системой счисления вместо плавающей точки позволило использовать диапазон представления чисел аналогичный формату IEEE-754, отказавшись при этом от медленных операций округления и выравнивания порядков. Прототип процессора реализован в виде IP-блока софт-процессора на базе ПЛИС. Ключевые слова: процессор, система остаточных классов, логарифмическая система счисления, реконфигурируемая архитектура, высоконадежные вычисления.
Высоконадежный модулярно-логарифмический процессор с реконфигурируемой архитектурой ФГУП «Российский федеральный ядерный центр Всероссийский научноисследовательский институт экспериментальной физики» СБИС-процессора позволило практически пропорционально повышать производительность с увеличением числа ячеек в силу естественного параллелизма их работы.
Объединение в единой процессорной архитектуре рассмотренных форм естественного параллелизма приведено далее в данной статье:
в пункте 1 (введение) приведена проблематика исследования и обзор близких по тематике работ;
в пункте 2 рассмотрена общая организация архитектуры процессора, включающая арифметическое устройство, вычислительные ядра и преобразователи кодов;
в пункте 3 рассмотрены средства повышения надежности вычислений на уровне архитектуры модулярно-логарифмического процессора;
в пункте 4 описан прототип предлагаемого процессора, рассчитана его производительность и проведено сравнение с аналогами;
в пункте 5 (заключение) приведено обобщение результатов, полученных в ходе данного исследования. 2. Организация архитектуры процессора
Параллелизм на уровне разрядов чисел в случае использования позиционной системы счисления (ПСС) существенно ограничен фактом распространения межразрядных переносов, что негативно сказывается на скорости его работы. Данный недостаток отсутствует в системе остаточных классов (СОК), где вычисления по каждому модулю (основанию) из базиса {p1,p2,...,pn} осуществляются независимо друг от друга.
Пример. Пусть СОК состоит из двух оснований {p1=5, p2=7}. Диапазон чисел ограничен произведением модулей P in1 pi 5 7 35. Преобразуем число – найдем остатки от деления на p1 и p2, например, картеж {2,3} является уникальным представлением числа 17. Остатки, обладая существенно меньшей разрядностью, могут суммироваться, либо умножаться параллельно: 2.1 Арифметическое устройство
В разработанном и запатентованном арифметическом устройстве [
Входная таблица подстановок модуля p1
Входная таблица подстановок модуля p1
Входная таблица подстановок модуля p2
Входная таблица подстановок модуля p2 . .
.
Входная таблица подстановок модуля pn
Входная таблица подстановок модуля pn x1 y1 x2 y2 xn yn z1 z2 zn
Выходная таблица подстановок модуля p1
Выходная таблица подстановок модуля p2 Рис. 1. Организация арифметического устройства x1 y1 x2 y2 xm ym 0 0
D T R C D T R C
Q1 Q2 Важным преимуществом СОК является также то, что все основные арифметические операции могут выполняться также быстро как обычное суммирование. Для операций умножение и деление нацело это становится возможным при использовании входных и выходных таблиц подстановок (Look up table – LUT), осуществляющих однотактные преобразования операндов, вычисляя соответственно дискретные логарифмы xi log g ai p и антилогарифмы ci g zi в полях i pi Галуа GF(p), где ai и zi – i-ые остатки по модулю pi, xi и ci – результаты преобразования i-ой входной и i-ой выходной таблицей соответственно, g – порождающий элемент поля GF(p), i[1,n].
Так как операция сложение остатков является основополагающей в разработанном арифметическом устройстве, её выполнение распараллелено во второй плоскости с помощью ОВС – квадратной матрицы размерностью m+1, где m – разрядность модуля i-го вычислительного канала. В такой систолической структуре (рис. 2 (а)) базовые элементы (рис. 2 (б)) соединены регулярными связями, образуя вычислительный конвейер.
0 0 Рис. 2. Организация: (а) однородной вычислительной среды, (б) базового элемента Базовый элемент (БЭ) оптимизирован по аппаратным затратам, при этом время заполнения вычислительного конвейера ОВС составляет Tконв tБЭ (m 1) , где m – разрядность модуля i-го вычислительного канала, tБЭ max{tXOR,tAND} tDFF) – время срабатывания БЭ, которое складывается из времени работы логического элемента и D-триггера, i[1,n], n количество остатков СОК.
После заполнения конвейера время выполнения арифметической операции равно tБЭ. Таким образом, первый уровень распараллеливания обеспечен независимым счетом по каждому модулю, второй уровень – конвейерным выполнением операций в ОВС. Ускорение в общем случае достигает k раз для операций сложение и вычитание и k2 раз для операций умножение и деление нацело по сравнению с последовательными алгоритмами ПСС, где k – разрядность позиционных операндов. 2.2 Вычислительное ядро
Рассмотренное арифметическое устройство является частью вычислительного ядра (рис. 3), где для снижения задержек доступа к памяти используется иерархическая структура памяти с многократным расслоением доступа по каждому модулю. Помимо трехпортовой кэш-памяти (два порта – чтение, один – запись), имеются буферные очереди операндов и результата. Благодаря линейной структуре FIFO, они обладают высоким быстродействием, обеспечивая своевременную подкачку данных в арифметическое устройство. A B Очередь данных первого операнда Очередь данных второго операнда КЭШ-память
данных Вычислительное
ядро Вычислительное ядро Арифмическое устройство Устройство управления Очередь данных результата
C
Очередь
команд
В разработанном модулярно-логарифмическом MIMD-процессоре таких вычислительных
ядер может быть несколько. Рассмотрим вариант, когда их четыре, как представлено на рис 4.
На исходные коды четырехядерного 32-разрядного процессора получено свидетельство о
регистрации программы на языке программирования аппаратуры [
Рис. 4. Организация модулярно-логарифмического процессора В системе команд процессора используется универсальный 64-разрядный формат (рис. 5), в котором присутствуют следующие поля: смещение в сегменте данных исходных операндов и результата; вид адресации; код операции; флаг векторной команды (команда будет применена к строке данных из 8 операндов). 31 24 23 16 15 9 8 7 6 1 0 Смещение Смещение Смещение Вид Код Векторная результата операнда 2 операнда 1 адресации операции операция
Рис. 5. Формат команды Используются следующие виды адресации: непосредственная (операнд в команде); регистровая прямая (первый операнд в регистре константы); относительная прямая (смещение указано в команде); индексная автоинкрементная (смещение в адресном счетчике). Задействовано порядка 30 команд, среди которых: арифметические операции; управление процессом вычислений; передача управления прерываниям. Ключевой особенностью процессора является динамическая реконфигурация числа ядер за счет уникальности набора оснований каждого вычислительного ядра. Ядра могут работать либо параллельно и независимо (32 бита), либо объединяться парами для удвоения точности (64 бита), либо объединяться в одно ядро для учетверения точности вычислений (128 бит). Это бывает необходимо для устранения ошибки переполнения разрядной сетки в процессе счета с помощью увеличения диапазона представления чисел.
Принадлежность числа в СОК к одному из четырех наборов оснований определяется двухразрядным полем группа модулей в 32-разрядном формате данных (рис. 6).
31 2.3 Преобразователь кодов Разработанный мультиоперандный сумматор представляет собой систолическую структуру, функционирующую на базе арифметики разрядных срезов, которая также обладает естественным параллелизмом.
Массив слагаемых M представим приведенной ниже битовой матрицей A размерностью m строк и n столбцов, где m - число слагаемых, n – разрядность модулей чисел. Предлагается выполнять обработку матрицы A не по строкам – скалярным значением слагаемых в двоичном представлении, как это реализуется в известных способах суммирования, а по столбцам – разрядным срезам SRi чисел массива M, i[1;n]. Каждый разрядный срез является одномерным булевым вектором из m элементов.
Специализированная ОВС (рис. 8 (а)) выполняет подсчет количества единичных бит в
разрядном срезе, подаваемом на входы xi в параллельно-конвейерном режиме, после чего младший
разряд подсчета становится разрядом искомой суммы (выход s), а остальные являются
разрядами переноса в следующий разрядный срез SRi+1, i[1;n], n – разрядность модулей. Такая
организация вычислений позволяет добиться повышения скорости вычислений в k раз по
сравнению с традиционным последовательным способом, где k – количество слагаемых [
0 0 x1 x2 b
Q2 a D T R C Битовая матрица A массива слагаемых содержит пять разрядных срезов: SR1=11112, SR2=10012, SR3=11012, SR4=00002, SR5=00002. На первом этапе выполняется параллельное вычисление количества единиц Bi в них: B1=1002, B2=0102, B3=0112, B4=0002, B5=0002. Младший разряд B1 является младшим разрядом s1=0 итоговой суммы чисел. Затем вычисляется значение B*2=(B1→)+B2=1002, где → обозначает операцию сдвига двоичного числа на один разряд вправо. Младший разряд полученной суммы B*2 является вторым s2=0 разрядом искомой суммы S. В итоге серии аналогичных вычислений вычисляется искомая сумма S(s5,s4,s3,s2,s1)=101002.
Важным моментом является использование тех же БЭ (рис. 8(б)), что и в ОВС, входящей в состав арифметического устройства. Это позволяет значительно повысить регулярность элементов процессора, что, в конечном счете, обеспечивает высокую технологичность в случае массового производства на базе СБИС. Однако, помимо естественного параллелизма, СОК обладает свойствами, повышающими надежность процесса вычислений. Средства, которые их реализуют в разработанном процессоре, приведены в следующем разделе. 3. Надежность вычислений
Надежность является одним из основных свойств любого вычислительного устройства, во многом определяющим его пригодность для использования по назначению. На сегодняшний день в супер-ЭВМ содержатся сотни тысяч и даже миллионы процессорных ядер. Сбои и отказы в таких системах приводят к тому, что алгоритм программы становится недетерминированным и в результате расчета можно получить разный результат при одинаковых наборах входных данных. Кроме того, существуют области вычислений, где ошибка в вычислениях может привести к фатальным последствиям. Например, к ним относятся задачи наведения ракет, управления атомной электростанцией, функционирования космических аппаратов и другие. Существуют такие традиционные пути повышения надежности, как: резервирование на уровне компонент системы; дублирование вычислений; дополнительная обработка исключительных ситуаций и т.п.
Их недостаток состоит в том, что часть оборудования простаивает, либо дублирует работу, вплоть до отказа одного из компонентов системы. Данного недостатка можно избежать, внедрив средства повышения надежности на уровне архитектуры. Рассмотрим более подробно, как это реализовано в предлагаемом процессоре. 3.1 Средства повышения надежности модулярно-логарифмического процессора Сочетание корректирующих свойств системы остаточных классов и динамической реконфигурации ОВС позволили реализовать следующие средства повышения надежности.
Во-первых, это выявление и исправление ошибок за счет расширения вычислительного
диапазона путем назначения одного или нескольких вычислительных каналов в качестве
контрольных (рис. 9). Доказано [
31 Рабочий диапазон 8 7
0 Контрольный
диапазон Рис. 9. Отображение областей чисел динамического диапазона Во-вторых, при превышении заданного порога в счетчике ошибок возникает ситуация отказа и канал блокируется. Однако в отличие от повсеместно распространенных универсальных вычислительных устройств, модулярно-логарифмический процессор (МЛП) продолжает работу, сокращается лишь диапазон представления чисел. Если при этом нельзя снижать точность вычислений, то можно использовать вычислительные каналы другого ядра, в том числе и контрольные (рис. 10). Такая реконфигурация позволяет создать процессор, устойчивый к постепенной деградации. В пределе, вычисления будут продолжаться, пока хотя бы один вычислительный канал будет работоспособен. При этом разрядность обрабатываемых чисел будет равна разрядности канала. 31 31 Канал 4 В-третьих, рассмотренная в п.2.2 динамическая реконфигурация числа ядер позволяет управлять разрядностью операндов для устранения ошибок переполнения разрядной сетки. Затем, при необходимости, разрядность чисел может быть понижена до исходной.
В-четвертых, на базе предложенного процессора имеется возможность реализовать
совершенно новые подходы в области аппаратного шифровании данных, например, можно настолько
быстро менять параметры остатков, чтобы период действия ключа на базе текущих параметров
был меньше минимального времени его вскрытия [
Кроме того, в процессе счета могут возникать неявные ошибки, связанные с округлением чисел в процессе вычислений по стандарту IEEE-754. К тому же работа с плавающей точкой связана с делением чисел, что негативно сказывается на скорости выполнения операций в СОК, так как данная операция является немодульной. Эти причины привели к необходимости применении аналога плавающей точки логарифмической системы счисления (ЛСС), где в процессе вычислений отсутствуют фазы нормализации и денормализации, что избавляет от ошибок округления и необходимости деления на степень двойки. 3.2 Модулярно-логарифмический формат данных
Любое вещественное число a представлено в ЛСС его знаком и двоичным логарифмом его абсолютной величины:
log 2 с a , если a c1, L(a)
0, если a c1, где с константа для представления чисел диапазона (0,1). Такое представление чисел позволяет производить вычисления не с вещественными числами, а с их логарифмами, причем операции умножение и деление заменяются операциями сложение и вычитание логарифмов соответственно, а возведение в степень и извлечение корня операциями умножение и деление логарифмов соответственно. Этот факт позволяет значительно ускорить выполнение перечисленных операций по сравнению с плавающей точкой.
Однако за это приходится расплачиваться более сложным выполнением операций сложение и вычитание вещественных чисел x и y:
log 2 (x ± y) log 2 x log 2 (1 ± 2log2ylog2 x ), которые реализованы в предложенном процессоре с помощью аппаратной реализации алгоритма квадратичной интерполяции.
Перевод вещественного числа в модулярно-логарифмический формат (рис. 11) проходит в два этапа: порядок числа с плавающей точкой становится целой частью двоичного логарифма; вычисляется логарифм мантиссы вещественного числа, который является дробной частью логарифма;
логарифмический код числа, состоящий из целой и дробной части логарифма, преобразуется в СОК как единое целое число; в старший разряд числа записывается знак вещественного числа без изменений. 31 30 24 23 16 15 9 8 2 1 0
Остаток по Знак модулю p4 Остаток по модулю p3 Остаток по модулю p2 Остаток по модулю p1 Логарифм
Дробная часть логарифма 31 30 минимальное количество каналов, необходимых для функционирования процессора k; отказ более чем 3k+4r каналов является отказом всего процессора; отказавшие каналы не восстанавливают работоспособность; отказы каналов являются статистически независимыми событиями.
Таким образом, надежностная структура процессора соответствует модели скользящего
резервирования, где резервные элементы находятся в нагруженном состоянии [
3k+4r RМЛП P4(kr)i (1 P)i ,
0 где P(t) et вероятность безотказной работы канала, интенсивность его отказа.
Определение и оперативная коррекция ошибок в ПСС возможна лишь при условии одновременной работы нескольких устройств по принципу голосования, например, «2 из 3». Вероятность безотказной работы такой системы:
R ПСС 3 PП2СС 2 PП3СС , где PПСС (t) enПСС t , ПСС интенсивность отказа одного разряда, n разрядность позиционного процессора.
Результаты расчета надежности в течении t=2000 часов функционирования представлены графически на рис. 12. Анализ полученных зависимостей свидетельствует о преимуществе в надежности модулярно-логарифмического процессора. Например, при интенсивности отказов =210-6 он обеспечивает вероятность безотказной работы R=0,5; тогда как позиционный процессор R=0,1. Избыточность аппаратурных затрат составляет 25% и 66% соответственно. 0 1
2 3 4 Интенсивность отказов , 10-6 5 6 Рис. 12. Модулярно-логарифмический формат данных 4. Прототип и оценка производительности процессора
На данный момент модулярно-логарифмический процессор существует в виде прототипа IP-блока RISC-процессора NIOS на базе программируемой логической интегральной схемы (ПЛИС). Данный выбор обусловлен простотой реализации, так как можно использовать уже готовые функциональные блоки процессора NIOS, дополняя его систему команд и используя уже готовый компилятор, для написания и отладки программ.
Проектирование функциональных схем процессора проводилось в САПР Quartus II Web Edition фирмы Altera. Отладка и тестирование выполнялось на базе платы с ПЛИС Altera Cyclone V.
Так как элементные базы ПЛИС и СБИС существенно отличаются по скоростным
характеристикам, то при сравнительной оценке целесообразно использовать количество операций за
такт работы устройства. Аппаратные затраты блоков векторных расширений универсальных
процессоров оценены приблизительно по изображениям планировки функциональных блоков
(floorplan).
0,2
0
МЛП
ПСС
Предложенный процессор выполняет до четырех операций за такт и при увеличении
вычислительных каналов способен догнать по числу операций за такт блок векторного
расширения Intel AVX семейства Sandy Bridge при сопоставимых аппаратных затратах (рис. 13 (а)) [
Кроме того, на рис. 13 (б) проведено сравнение характеристик одного вычислительного ядра МЛП (32 бита) с софт-процессором NIOS, к которому подключен разработанный IP-блок. Из рисунка видно, что процессору NIOS требуется 3 такта для выполнения целочисленной операции и пять тактов для вещественной, тогда как вычислительному ядру МЛП необходим один такт для выполнения арифметической операции за такт, независимо от типа данных. Аппаратные затраты приведены в количестве адаптивных логических модулей (adaptive logic module ALM), необходимых для генерации устройства на базе ПЛИС Cyclone V.
Операций Intel Sandy Bridge Операций за такт AVX-256 за такт МЛП-32 8 1 4 ARM Cortex A15
NEON-128
2
0
2,2
8,3
18,9
Млн.
транзисторов
МЛП-128
4 ядра
(а)
Помимо универсальных процессоров, у МЛП существуют специализированные аналоги.
Например, модулярный нейропроцессор, разработанный в Ставропольском военном институте
связи [
Таким образом, в представленном модулярно-логарифмическом процессоре заложен потенциал параллельного счета и обеспечения отказоустойчивости на уровне архитектуры, что делает актуальным его применение для расчета задач, критичных не только к скорости, но и к надежности вычислений.
Высокая производительность достигается за счет: распараллеливания арифметических операций на уровне остатков непозиционной системы счисления; параллельно-конвейерной обработки каждого модуля в однородной вычислительной среде; замены операций умножение и деление вещественных чисел операциями сложение и вычитание соответственно, благодаря свойствам логарифмов.
Надежность вычислений обеспечивается: обнаружением и коррекцией ошибок; устойчивостью к постепенной деградации оборудования; динамической реконфигурацией числа ядер для управления разрядностью вычислений; отсутствием ошибок округления за счет применения ЛСС.
Текущая реализация в виде IP-блока софт-процессора подтверждает реализуемость архитектурных особенностей, описанных в данной статье. В перспективе такой процессор может быть создан не только в качестве дополнения системы на кристалле, но и как самостоятельное устройство. Например, в виде арифметического ускорителя, подключаемого к компьютеру с традиционной архитектурой, либо в качестве центрального процессора на базе СБИС. В любом из этих вариантов высокая производительность, масштабируемость и реконфигурируемость достигается за счет применения однородных вычислительных сред, функционирующих в базисе системы остаточных классов и логарифмической системы счисления.
Сферами применения МЛП являются: высокопроизводительные вычисления, требующие работы с большой разрядностью данных (задачи моделирования климата, исследование электромагнитного рассеяния, исследование орбитальной эволюции небесных тел и другие), где за счет распараллеливания счёта на множество независимых остатков достигается прирост производительности по сравнению с известными аналогами;
высоконадёжные вычисления, требующие постоянного контроля правильности вычислений (задачи наведения ракет, управления атомной электростанцией, функционирования космических аппаратов и подобные), где за счёт применения корректирующих свойств СОК достигается уменьшение аппаратных затрат по сравнению с аналогами. Литература 3. Coleman J.N., Chester E.I. Arithmetic on the European Logarithmic Microprocessor // IEEE
Transactions on Computers. 2000. Vol. 49, No. 7. P. 702–715. The highly reliable modular-logarithmic processor with reconfigurable architecture
I.P. Osinin The Russian Federal Nuclear Center – All-Russian Scientific Research Institute of
Experimental Physics (RFNC-VNIIEF) The article describes the organization of perspective modular-logarithmic processor. The key difference from analogues is to use non-positional number system based on homogeneous computing environments that parallelize computations until operand bits, increasing the speed of calculations, and also has introduced a number of unique properties that significantly improve the reliability of computations. Application of residual classes in conjunction with the logarithmic number system instead of the floating-point allowed us to use range of the representation the same IEEE-754 format, while refusing the slow operation of rounding and smoothing orders. The prototype of processor is implemented in the view of IP-block of soft processor based on FPGA. 3. Coleman J.N., Chester E.I. Arithmetic on the European Logarithmic Microprocessor // IEEE
Transactions on Computers. 2000. Vol. 49, No. 7. P. 702–715.