Модулярные процессоры – история и оценки тривалентного эффекта

Инютин Сергей Арнольдович

Аннотация

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

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

I. Введение

Известно утверждение, впервые сформулированное профессором МГУ С.В. Фоминым, об оптимальном основании позиционной системы счисления, позволяющим записать наибольшее количество информации конечным словом в позиционной записи числа, при ограничении на количество используемых символов. Оптимальным основанием позиционной системы счисления является основание натурального логарифма – e . Очевидно, выполняется неравенство |3- e|< |2 – e|. Из утверждения следует важный вывод: троичная система счисления позволяет достичь большей информационной ёмкости при отображении дискретных данных в троичном регистре, по сравнению с двоичным вариантом регистром. Этот факт всегда вызывал интерес к троичной системе счисления среди разработчиков перспективных образцов вычислительных систем. К недостаткам вычислительных систем, оперирующих со специальными форматами данных, ориентированными на троичное представление, относятся большие аппаратурные затраты, по сравнению с двоичными вычислительными устройствами и меньшая надёжность обработки трёх состояний в элементарной ячейке троичной разрядной сетки. Элементная база вычислительных устройств постоянно совершенствуется, поэтому работы в направлении применения троичной системы счисления проводились и продолжают проводиться.

II. История создания

Условно этот период помещается между выходом Яндекса на безубыточность и появлением смартфонов, как средства доступа к Рунету. Именно в это время государство обратило серьезное внимание на Рунет как новый сектор рынка, и выступило с целым рядом инициатив, объявив программу Электронная Россия. В Рунете начали работать первые венчурные фонды. Количество сайтов Рунета перевалило за 15 миллионов. Интернет пришел в публичные пространства, учебные заведения.

Прогнозирование в это время получило сильный импульс в связи с созданием аналитических подразделений и самостоятельных агентств. Среди них, например, RBC.ru и J’son and Partners (российская компания – с 2002 г.). Впервые отдельные метрики Рунета стали определяться международными компаниями (GFK и другие). Отличием от предыдущего периода стал спрос на прогнозирование денежных потоков, необходимое в венчурной отрасли и при совершении сделок слияния и поглощения. Появились исключительно онлайновые СМИ. Вошли в практику счетчики посещений и рейтинги популярности. Появилась публичная Премия Рунета.

Компании-игроки Рунета начали рассматриваться, как бизнесы, способные генерировать доход. Именно данный тип прогнозов позволил обосновать целый ряд решений о покупке компаний, заложил основу оценки справедливой рыночной стоимости. Пример - консолидация активов поисковика АПОРТ и каталога Ау!, выполненная для продажи Golden Telecom (меньше $500 тыс., 2000 год) и последующее поглощение самого Golden Telecom ($10 млн, 2008 год).

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

III. 2010-2020 рунет для всех и повсюду – новый фактор развития

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

• бивалентный эффект, возникающий при отображении компонент вектора модулярного представления в бинарных регистрах типовой элементной базы [3];

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

По меткому замечанию академика В.М. Амербаева термин «системы в остаточных классах» следовало бы изменить на «системы классов вычетов или остатков по модулю». В дальнейшем эта область научных знаний получила название модулярной арифметики, под которым система остаточных классов известна за рубежом.

В середине 70-х годов произошло фактическое перемещение в Алма-Ату центра теоретических разработок процессоров на основе системы остаточных классов (модулярной арифметики), использующих специальные форматы данных и предназначенных для работы с комплексными числами. В эти годы вёлся интенсивный поиск новых областей приложения модулярной арифметики. В НПО «Алмаз» и «Астрофизика» (Москва), совместно с Институтом математики и механики АН Казахской ССР (ИММ АН КазССР) выполнялся ряд научных проектов, в которых для описания движения летательных объектов применялись комплексные числа и кватернионы, а расчёты выполнялись с использованием арифметики системы остаточных классов [1]. Со стороны АН Казахской ССР научные проекты возглавляли академик Амербаев В.М. и член-корреспондент Акушский И.Я., руководили исследованиями заведующие отделами профессора Пак И.Т. и Казангапов А.Н. В выполнении научных проектов участвовали группа старших и младших научных сотрудников отделов Параллельных вычислительных процессов и Анализа и синтеза цифровых данных указанного института [2]. В эти годы академик Амербаев В.М. имел тесные контакты с ведущим вузом страны – МГУ им. М.В. Ломоносова. По совету коллег из МГУ, создателей ЭВМ «Сетунь» и «Сетунь-70», в которых данные в соответствующих форматах обрабатывались в троичной системе счисления, внимание разработчиков проектов из АН Казахской ССР привлекла идея объединения троичной системы счисления с системой остаточных классов. В дальнейшем выяснилось, что это также уменьшает информационную избыточность модулярного представления цифровых данных. 

III. Применение

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

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

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

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

Числовая величина A в модулярном формате данных представлена вектором:

A(mod P) ↔ (α₁ mod p₁… α_n mod p_n),

где α_i - наименьший неотрицательный вычет по модулю mod p_i,

{ p₁,...p_n }  -множество простых или взаимно-простых целых чисел, называемых основания модулярной арифметики;

P = Π P_i, i=1, n - верхняя грань числового значения вычислительного диапазона модулярной арифметики.

Учитывая использование троичной элементной базы, введем для модулярного процессора понятие тривалентногоэффекта для одиночного основания δ_i и полного вычислительного диапазона ∆_n для n- регистровой троичной разрядной сетки модулярного процессора:

δ_i = [log₃p_i] - log₃p_i = n_{i -} log₃p_i ≥ 0,

 ∆_n =∑δ_i, i=1, n

где квадратными скобками n_i = [log₃p_i] обозначена целая не меньшая часть, равная троичной разрядности регистра для отображения одного вычета по соответствующему модулю.

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

Для иллюстрации способа выберем взаимно-простые модули – основания троичной модулярной арифметики, близкие по величине к двоичному значению бинарного стандартного байта 256 = 2⁸.

Для троичной регистровой базы выберем шесть тритовых модулярных основания: {p₁, p₂, p₃, p₄, p₅, p₆}  ={229,233,239, 241,242, 243 = 3⁵}. При таком выборе оснований разрядная сетка специализированного вычислительного устройства имеет длину 30 трит, а особенности такого выбора тритовых модулярных оснований приведены в Таблице 1. Значение модулярного вычислительного диапазона равно P = ΠP_i, i=1, 6 = 180729058527458, что превышает 8630377364883 = 3²⁹. Для отображения числового значения модулярного вычислительного диапазона в бинарной разрядной сетке требуется 48 бит.

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

Таблица 1

Модулярные основания для троичного варианта

Для рассмотренного варианта избыточность равна (205891132094649 - 180729058627458) / 205891132094649 = (3³⁰- P)/3³⁰=12,22%, значительно меньшая по сравнению с вариантами выбора оснований модулярной арифметики, дающих близкую длину разрядной сетки в разработанных специализированных двоичных ЦВМ.

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

Тривалентный эффект дает основу для расчета информационной избыточности отдельного регистра 3^n_i – p_i, а также относительного информационного эффекта (3^n_i – p_i)/ 3^n_i. Определим информационную избыточность разрядной сетки модулярного процессора 3^k – P и относительную информационную избыточность разрядной сетки (3^k – P)/3^k = 1 - P/3^k. Отметим, что нулевой тривалентный эффект приводит к нулевой информационной избыточности троичной разрядной сетки процессора.

Представление числовой величины в модулярном формате данных можно рассматривать в качестве кодового n-компонентного вектора, компоненты которого отображены вn–троичных регистрах, длиной n_i = [log₃p_i]. Суммарная длина разрядной сетки модулярного процессора равна k=∑n_i, i=1, n. 

Определим приведенную информационную избыточность разрядной сетки модулярного процессора 3^k - 3^[log₃P] и относительную приведенную информационную избыточность разрядной сетки (3^k - 3^[log₃P]) / 3^k= 1 - 3^{[log₃P] - k}.

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

• выбор простых оснований или отдельных взаимно-простых оснований модулярной арифметики с минимальными эффектами отображения;

• применение многоуровневой модулярной арифметики.

Для вычислительного диапазона, заданного произведением выбранных модулярных оснований, требуется двоичная разрядность 42 бит. Для указанной разрядности модулярного процессора ЦВМ вычисленное численное значение информационной избыточности 2^k - P разрядной сетки процессора приведено в таблице 3.

Таблица 3

Вычислительные диапазоны модулярных ЦВМ для двоичного варианта

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

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

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

Для иллюстрации способа уменьшения регистрового эффекта для двоичной арифметики, ориентируясь на стандартный двоичный размер байта, выберем взаимно-простые основания (модули) модулярной арифметики {p₁, p₂, p₃, p₄, p₅}  ={253,255, 256, 257, 259}. Модуль 257 –простой; для четырех модулей мультипликативные канонические разложения имеют вид: 253=11∙23; 255=3∙5∙17; 259=7∙37; 256=2⁸. Способ позволяет сформировать две пары взаимно-простых модулей (p₁, p₅), (p₂, p₄), равноотстоящих от константы 2⁸. Для модулей выполняются соотношения: p = p₃ = 2⁸ = 256; n = log₂p = log₂2⁸ = 8 – длина блока (двоичного регистра). Первая пара оснований связана соотношениями p₁ = p - Ῡ₁ = 253 = 2⁸-3; p₅ = p + Υ₁ = 259 = 2⁸+3; Ῡ₁ = Υ₁ = 3 - разность между константой 2⁸ и модулями первой пары (количеством троичных комбинаций). Вторая пара модулей связана соотношениями p₂ = p - Ῡ₂ = 255 = 2⁸-1; p₄ = p + Ῡ₂ = 2⁸+1 = 257; Ῡ₂ = Υ₂ = 1 - разность между константой 2⁸ и модулями второй пары. 

Выполнение соотношений для модулей – оснований модулярной системы позволяет заявленным способом размещать двоичные значения вычетов по пяти взаимно-простым модулям в пяти однородных 8-битовых блоках выходного регистра (двоичной 40 -разрядной сетке модулярной ЦВМ). Например, из блока входного регистра получен вычет α₄ = 2⁸ = p по модулю 257 257, который не может быть размещен в 8-битовом блоке. Вычисляют число ᾶ₂ = α₄ - (p - p₂) = α₄ - δ_i = α₄ - 1 < p , которое размещают в 8-битовом блоке, предназначенном для размещения вычета по модулю p₂, который размещают в 8-битовом блоке, предназначенном для размещения вычета по модулю p₄.

Модулярные основания {p₁, p₂, p₃, p₄, p₅}  ={253,255, 256, 257, 259} при использовании указанного способа позволяют получить нулевые суммарный бивалентный эффект и информационную избыточность.

Способ выбора оснований модулярной арифметики и соответствующее устройство приведены в описании к патенту РФ [5].

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

IV. Выводы и заключение

Результатом технического решения, приведенного в упомянутом патенте, является уменьшение информационной избыточности размещения групп чисел в однородных, равной длины блоках цифрового регистра. Это повышает эффективность размещения данных, экономичность функционирования, технологичность схемотехнического проектирования однородного блокового регистра (разрядной сетки ЦВМ).

Приведём варианты выбора взаимно-простых модулярных оснований для троичных разрядных сеток специализированных модулярных процессоров с минимальным тривалентным эффектом, используя способ, описанный в патенте РФ [5].

{p₁, p₂, p₃, p₄, p₅}  ={233, 241, 242=2∙11², 243=3⁵, 257}

Для 25 разрядной троичной сетки процессора модулярный вычислительный диапазон 848648262726 ≈ 3²⁵.

{p₁, p₂, p₃, p₄, p₅, p₆}  ={233, 241, 242=2∙11², 243=3⁵, 245 = 242=5∙53, 257}

Для 30 разрядной троичной сетки модулярный вычислительный диапазон 207918824367870 ≈ 3³⁰.

В заключение следует также привести диалог между членом-корреспондентом И.Я. Акушским и известным специалистом в области помехозащитного кодирования профессором М.С. Пинскером, состоявшийся в Алма-Ате на конференции по высокопроизводительным вычислениям, проводимой в 1979 году Институтом математики и механики АН Казахской ССР на Медео. Марк Семёнович на круглом столе – при свободном обмене мнениями в содержательной беседе (я был свидетелем этого разговора), обращаясь к И.Я. Акушскому, сказал: «даже в троичной системе остаточных классов хозяйки в магазине и на рынке не будут выполнять расчёты». На это Израиль Яковлевич, известный своим остроумием, заметил «конечно, они будут считать, используя исключительно коды Боуза-Чоудхури-Хоквингема (БЧХ)». Как известно, М.С. Пинскер работал в Институте проблем передачи информации АН ССР и был известным специалистом в этой области помехозащитного кодирования дискретной информации.

Список литературы

1. Акушский И.Я., Амербаев В.М., Пак И.Т. Основы машинной арифметики комплексных чисел. Алма-Ата: Наука, 1970. 210с.

2. Амербаев В.М., Пак И.Т. Параллельные вычисления в комплексной области. Алма-Ата: Наука, 1984. 183с.

3. Амербаев В.М., Тельпухов Д.В., Константинов А.В. Бивалентный эффект модулярных кодов. //Проблемы разработки перспективных микро- и наноэлектронных систем. Сборник трудов ИППМ РАН/ под общей ред. А.Л. Стемпковского. М: ИППМ-МЕС, 2008. с.492-466.

4. Малашевич Б.М. Неизвестные модулярные суперЭВМ. PCWeek/RE, М., 2005, № 9, с. 44-45; № 10, с. 52-54.

5. Инютин С.А. Способ и устройство размещения групп чисел в однородных блоках цифрового регистра. Патент на изобретение РФ № 2591009 зарегистрирован 17.06.2016, приоритет заявки № 2015109196 от 17.03.2015.

Об авторе: НИУ «Московский авиационный институт (МАИ)», Москва, Россия,
Inyutin_sa@mail.ru
Материалы международной конференции Sorucom 2020
Помещена в музей с разрешения автора 16 ноября 2021