Модулярные процессоры – оценки, история борьбы и победы над бивалентным дефектом
Инютин С. А.
Известен способ представления числовых величин в векторной форме с независимыми компонентами – наименьшими неотрицательными вычетами по модулям из множества взаимно-простых чисел, называемых основаниями модулярной арифметики.
Модулярная арифметика имеет несомненные достоинства: независимость выполнения аддитивных и мультипликативных операций по всем компонентам векторных представлений, а также уникальную возможность построения арифметических помехозащитных кодов, позволяющих контролировать выполнение операций обработки данных в таких компьютерных форматах, называемых модулярными. Однако, имеется недостаток – естественная избыточность представления компонент модулярных форматов данных в двоичных цифровых регистрах. Проанализируем возникающие при этом проблемы.
При создании технических устройств: специализированных процессоров, контролеров, цифровых фильтров, работающих на основе модулярной арифметики (отечественное название – система остаточных классов), первым и важнейшим этапом является выбор модулей – простых (взаимно-простых) чисел. Эти числа называются основаниями модулярной арифметики. Результаты большинства операции в этой арифметике являются наименьшими неотрицательными вычетами по модулю, а обрабатываемые числовые данные в модулярных форматах данных являются векторами с компонентами – вычетами по модулю. Учитывая, что проектирование большинства современных устройств ориентировано на двоичную элементную базу, компоненты модулярных векторов отображаются в двоичных регистрах. Причем не все возможные двоичные комбинации регистра используются для представления вычетов по простым модулям, следовательно, возникает избыточность двоичного регистрового представления, получившая название бивалентного дефекта.
Числовая величина A в модулярном формате данных представлена вектором:
где αi – наименьший неотрицательный вычет по модулю modpi,
– вычислительный диапазон модулярной арифметики.
Введем понятие бивалентного дефекта для одиночного основания δi и полного вычислительного диапазона ∆n для n-регистровой бинарной разрядной сетки модулярного процессора:
Бивалентный дефект дает основу для расчета информационной избыточности (информационного дефекта) регистра 2ni – pi, а также относительного информационного дефекта .
Представление числовой величины в модулярном формате данных можно рассматривать в качестве кодового n-компонентного вектора, компоненты которого отображены в n-бинарных регистрах длиной . При этом суммарная длина разрядной сетки модулярного процессора равна .
Определим информационную избыточность разрядной сетки модулярного процессора и относительную информационную избыточность разрядной сетки . Отметим, что нулевой бивалентный дефект даёт нулевую информационную избыточность разрядной сетки процессора.
Определим приведенную информационную избыточность разрядной сетки модулярного процессора и относительную приведенную информационную избыточность разрядной сетки .
Известными и применяемыми до настоящего времени методами уменьшения избыточности от бивалентного дефекта являются:
- выбор простых оснований модулярной арифметики с минимальным бивалентным дефектом,
- выбор отдельных взаимно-простых оснований с минимальным бивалентным дефектом,
- применение многоуровневой модулярной арифметики.
Проанализируем с позиции бивалентного дефекта и информационной избыточности разрядные сетки известных ЦВМ с модулярными процессорами Т340А, К340А, Алмаз, 5Э53, а также проект 41-50 «Лидер», разработанные в разные годы в Специализированном вычислительном центре Зеленоградского научного центра микроэлектроники Министерства электронной промышленности СССР [1].
В 60-х годах прошлого века в НИИ-37 начались работы по созданию ЦВМ на основе модулярной арифметики. В 1962-63 гг. был разработан первый, экспериментальный образец модулярной ЦВМ Т340А (главный конструктор Д.И. Юдицкий, научный руководитель И.Я Акушский). В 1963 г. была создана существенно модифицированная ЦВМ К340А, которая выпускалась серийно до середины 70-х годов (главный конструктор Д.И. Юдицкий, научный руководитель И.Я Акушский). В дальнейшем работы на разработанной базе по созданию специализированной модулярной ЦВМ и её применению для оборонных задач продолжил Л.В. Васильев, удостоенный Госпремии СССР за серийный образец спецЦВМ. В 1968 г. создана модулярная ЦВМ проекта «Алмаз (главный конструктор Д.И. Юдицкий, научный руководитель И.Я Акушский). Все эти машины имели бинарную 45-разрядную сетку модулярного процессора. Количественные и информационные параметры разрядной сетки приведем в таблицах 1-4.
Таблица 1.
Разряды процессора |
1 |
2-4 |
5-9 |
10-15 |
16-20 |
21-25 |
26-30 |
31-34 |
35-39 |
40-45 |
Основания модулярные |
2 |
5 |
23 |
63 |
17 |
19 |
29 |
13 |
31 |
61 |
Разрядность регистров |
1 |
3 |
5 |
6 |
5 |
5 |
5 |
4 |
5 |
6 |
Бивалентный дефект |
0 |
0,678 |
0,476 |
0,023 |
0,913 |
0,752 |
0,142 |
0,300 |
0,046 |
0,069 |
Избыточность |
0 |
0,375 |
0,281 |
0,016 |
0,469 |
0,406 |
0,094 |
0,188 |
0,031 |
0,047 |
% избыточности |
0 |
37,50 |
28,13 |
1,56 |
46,88 |
40,63 |
9,38 |
18,75 |
3,13 |
4,69 |
Таблица 2.
Диапазон вычислительный |
3336597244890 |
Разрядность реальная |
45 |
Бивалентный дефект |
3,398 |
Избыточность информационная |
0,905 |
Избыточность приведенная |
0,784 |
% избыточности приведенной |
78,4 |
Для указанного вычислительного диапазона требуется бинарная разрядность 42 бит.
Таблица 3.
Диапазон вычислительный |
3336597244890 |
Разрядность необходимая |
42 |
Бивалентный дефект |
0,398 |
Избыточность информационная |
0,241 |
% избыточности информац. |
24,13 |
Для указанной разрядности модулярного процессора ЦВМ вычислим численное значение информационной избыточности 2k – P разрядной сетки процессора.
Таблица 4.
Разрядность процессора |
45 |
Избыточность диапазона |
35184372088801 |
Из приведенных данных видно, что модулярный процессор имел большой, 78,4 процент избыточности.
В 70-х годах прошлого века в Специализированном вычислительном центре (Зеленоград) были разработаны ЦВМ 5Э53 (1971), специализированная модулярная ЦВМ для проекта 41-50 «Лидер» (1973) с 40-разрядной сеткой модулярного процессора (главный конструктор Д.И. Юдицкий, научный руководитель И.Я Акушский). Количественные и информационные параметры разрядной сетки приведем в таблицах 5-8.
Таблица 5.
Разряды процессора |
1- 5 |
6- 10 |
11- 15 |
16- 20 |
21- 25 |
25- 30 |
31- 35 |
36-40 |
Основания модулярные |
17 |
19 |
26 |
31 |
23 |
25 |
27 |
29 |
Разрядность регистров |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
Бивалентный дефект |
0,913 |
0,752 |
0,300 |
0,046 |
0,476 |
0,356 |
0,245 |
0,142 |
Избыточность |
0,469 |
0,406 |
0,188 |
0,031 |
0,281 |
0,219 |
0,156 |
0,094 |
% избыточности |
46,88 |
40,63 |
18,75 |
3,13 |
28,13 |
21,88 |
15,63 |
9,38 |
Таблица 6.
Диапазон вычислительный |
117210676050 |
Разрядность реальная |
40 |
Бивалентный дефект |
3,230 |
Избыточность информац. |
0,893 |
Избыточность приведённая |
0,758 |
% избыточности приведён. |
75,8 |
Для указанного вычислительного диапазона требуется бинарная разрядность 37 бит.
Таблица 7.
Диапазон вычислительный |
117210676050 |
Разрядность необходимая |
37 |
Бивалентный дефект |
0,230 |
Избыточность информационная |
0,147 |
% избыточности информацион. |
14,72 |
Для указанной разрядности модулярного процессора ЦВМ вычислим численное значение информационной избыточности 2k – P разрядной сетки процессора.
Таблица 8.
Разрядность процессора |
40 |
Избыточность диапазона |
982300951726 |
Из приведенных данных видно, что модулярный процессор имел большой процент избыточности, равный 75,8. Делались попытки естественную избыточность модулярной арифметики использовать для дополнительного повышения надежности передачи данных в комплексе специализированных ЦВМ, но существенных результатов не было достигнуто
В 2000-х годах в Институте проблем проектирования в микроэлектронике РАН для ряда проектов под научным руководством академиков А.Л. Стемпковского и В.М. Амербаева были разработаны специализированные модулярные микропроцессоры с 22- и 43-разрядной двоичной сеткой для цифровой обработки сигналов, ориентированные на использование многоуровневой модулярной арифметики [2]. Отметим, что с увеличением количества уровней избыточность пропорционально увеличивается. Приведем параметры двух вариантов микропроцессоров, использующих модулярную арифметику. Количественные и информационные параметры разрядной сетки приведем в таблицах 9-14.
Таблица 9. Первый вариант
Разряды процессора |
1 |
2-3 |
4-6 |
7-9 |
10-13 |
14-17 |
18-22 |
Основания модулярные |
2 |
3 |
5 |
7 |
11 |
13 |
17 |
Разрядность регистров |
1 |
2 |
3 |
3 |
4 |
4 |
5 |
Бивалентный дефект |
0,000 |
0,415 |
0,678 |
0,193 |
0,541 |
0,300 |
0,913 |
Избыточность |
0,000 |
0,250 |
0,375 |
0,125 |
0,313 |
0,188 |
0,469 |
% избыточности |
0,00 |
25,00 |
37,50 |
12,50 |
31,25 |
18,75 |
46,88 |
Таблица 10.
Параметры |
Реально |
Необходимо |
Диапазон вычислительный |
510510 |
510510 |
Разрядность необходимая |
22 |
19 |
Бивалентный дефект |
3,038 |
0,038 |
Избыточность информационная |
0,878 |
0,026 |
Избыточность приведенная |
0,784 |
0 |
% избыточности приведенной |
78,4 |
0 |
Для указанной разрядности модулярного микропроцессора первого варианта вычислим численное значение информационной избыточности 2k – P разрядной сетки процессора.
Таблица 11.
Разрядность процессора |
22 |
Избыточность диапазона |
3683794 |
Таблица 12. Второй вариант.
Разряды процессора |
1-5 |
6-10 |
11-15 |
16-20 |
21-25 |
26-31 |
32-37 |
38-43 |
Основания модулярные |
19 |
21 |
23 |
29 |
31 |
37 |
41 |
43 |
Разрядность регистров |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
Бивалентный дефект |
0,752 |
0,608 |
0,476 |
0,142 |
0,046 |
0,791 |
0,642 |
0,574 |
Избыточность |
0,406 |
0,344 |
0,281 |
0,094 |
0,031 |
0,422 |
0,359 |
0,328 |
% избыточности |
40,63 |
34,38 |
28,13 |
9,38 |
3,13 |
42,19 |
35,94 |
32,81 |
Таблица 13.
Параметры |
Реально |
Необходимо |
Диапазон вычислительный |
538163773413 |
538163773413 |
Разрядность |
43 |
39 |
Бивалентный дефект |
4,031 |
0,031 |
Избыточность информационная |
0,939 |
0,021 |
Избыточность приведенная |
0,914 |
0 |
% избыточности приведенной |
91,4 |
0 |
Для указанной разрядности модулярного микропроцессора второго варианта вычислим численное значение информационной избыточности 2k – P разрядной сетки процессора.
Таблица 14.
Разрядность процессора |
43 |
Избыточность диапазона |
8796093022208 |
Из приведенных данных видно, что модулярный микропроцессор в первом варианте имел избыточность 78,4% и во втором варианте 91,4%.
В 2015 г. был разработан новый метод борьбы с бивалентным дефектом или способ перераспределения избыточности симметричных модулярных оснований, позволивший одержать победу над этим явлением.
Способ основан на выборе взаимно-простых оснований модулярной арифметики симметричных относительно числа, являющего некоторой степенью двух, и использовании избыточности одних оснований для отображения числовых значений вычетов симметричных им, превышающих регистровую емкость.
Для иллюстрации способа, ориентируясь на стандартный двоичный размер байта, выберем взаимно-простые модули – основания модулярной арифметики: {p1, p2, p3, p4, p5} = {253,255, 256, 257, 259}. Для них выполняются следующее: модуль 257 – простой; для четырех модулей мультипликативные канонические разложения имеют вид: 253 = 11.23; 255 = 3.5.17; 259 = 7.37; 256 = 28. Это позволяет сформировать две пары (p1,p5), (p2,p4) взаимно-простых модулей, равноотстоящих от константы 28. Для модулей выполняются соотношения: p = p3 = 28 = 256; n = log2 p = log228 = 8 –длина блока (двоичного регистра);
первая пара оснований p1 = p – γ ̃1 = 253 =28 – 3; p5 = p + γ1 = 259 =28 +3; γ ̃1 = γ1 = 3 – разности между константой 28 и модулями первой пары (количеством бинарных комбинаций;
вторая пара модулей p2 = p – γ ̃2 = 255 = 28 – 1; p4 = p + γ2 = 28 + 1 = 257; γ ̃2 = γ2 = 1 – разности между константой 28 и модулями второй пары.
Выполнение соотношений для модулей – оснований модулярной системы позволяет заявленным способом размещать двоичные значения вычетов по пяти взаимно-простым модулям в пяти однородных 8-битовых блоках выходного регистра (бинарной 40-разрядной сетке модулярной ЦВМ).
Пусть из блока входного регистра получен вычет α4 = 28 = p по модулю 257, который не может быть размещен в 8-битовом блоке. Вычисляют число α ̃2 = α4 – (p – p2) = α4 – δi = α4 – 1 < p, которое размещают в 8-битовом блоке, предназначенном для размещения вычета по модулю p2, который размещают в 8-битовом блоке, предназначенном для размещения вычета по модулю p4.
Модулярная арифметика с множеством оснований
{p1, p2, p3, p4, p5} = {253,255, 256, 257, 259}
имеет суммарный бивалентный дефект и информационную избыточность, равные нулю.
Специальный способ выбора оснований модулярной арифметики и соответствующее устройство детально раскрыты в описании к патенту [3].
Способ и соответствующее техническое решение относится к области специализированной цифровой вычислительной техники, может быть использовано в системах связи и управления сложными объектами, предназначено для компактного размещения в цифровом регистре групп чисел или данных, представленных в модулярных форматах. Результатом технического решения является уменьшение информационной избыточности размещения групп чисел в однородных, равной длины блоках цифрового регистра, что повышает эффективность размещения данных, экономичность функционирования, технологичность схемотехнического проектирования однородного блокового регистра (разрядной сетки ЦВМ).
Новый способ уменьшения избыточности содержит задание первой константы, разделение на пары вычетов по модулю из блоков входного регистра, вычисление второй константы, выбор пары оснований модулярной системы, симметричных относительно первой константы, преобразование вычета по одному из оснований с использованием второй константы, размещение после преобразования пары чисел в однородных блоках выходного регистра. Устройство, реализующее способ, содержит однородный выходной блоковый регистр и неоднородный входной блоковый регистр, в котором для каждой пары блоков содержатся блоки сравнения, вычитания, передачи в параллельном бинарном коде информационных данных в однородный выходной регистр, проводники передачи управляющих сигналов. При передаче каждой пары чисел из блоков входного регистра в блоке сравнения одно из чисел сравнивают с заданной первой константой, если число меньше, то по первому управляющему сигналу пару чисел без изменений передают в соответствующую пару блоков выходного регистра, в противном случае по второму управляющему сигналу в блоке вычитания от сравниваемого числа вычитают расчетную вторую константу и размещают после ротации числа в паре однородных блоков выходного регистра.
В результате специальным выбором оснований модулярной арифметики описанный способ позволяет на порядок уменьшить информационную избыточность, а в отдельных случаях получить бивалентный дефект и информационную избыточность, равные нулю.
Литература
- Малашевич Б.М. Неизвестные модулярные суперЭВМ // PC Week/RE. 2005. № 9. С. 44-45; № 10. С. 52-54.
- Амербаев В.М., Тельпухов Д.В., Константинов А.В. Бивалентный эффект модулярных кодов // Проблемы разработки перспективных микро- и наноэлектронных систем. Сборник трудов ИППМ РАН. Под общей ред. А.Л. Стемпковского. М.: ИППМ-МЕС, 2008. С. 492-496.
- Инютин С.А. Способ и устройство размещения групп чисел в однородных блоках цифрового регистра. Патент на изобретение РФ № 2591009 зарегистрирован 17.06.2016, приоритет заявки № 2015109196 от 17.03.2015
Об авторе: д.т.н., профессор
Московский авиационный институт (национальный исследовательский университет)
Москва, Россия
Материалы международной конференции Sorucom 2017
Помещена в музей с разрешения автора
16 января 2019