Жуков-Емельянов О.Д. Информационные технологии на основе модулярной алгебры

Оглавление

Информационные технологии и модулярные вычисления

Введение. Модулярные числовые системы

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

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

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

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

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

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

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

– отсутствие межразрядных переносов, полный параллелизм обработки разрядов и, как следствие, высокий темп выполнения модулярных операций, недостижимый для операций в двоичных системах;

– малая величина (длина в битах) участвующих в модулярных операциях цифр (вычетов) и, с учетом этого, возможность широкого использования табличных методов выполнения операций и функций;

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

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

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

В основе СВ лежит Китайская теорема о вычетах, в соответствии с которой число, находящееся в диапазоне, равном произведению всех модулей СВ, может быть уникально представлено совокупностью вычетов по этим модулям. Теоретической базой СВ является теория сравнений [1].

Впервые идею использования СВ в рамках компьютерных технологий высказали чешские ученые М.Валах и А.Свобода [2]. После этого как в СССР, так и в США появляется целый ряд работ, посвященных СВ.

Определяющая роль в становлении и развертывании данного направления в нашей стране принадлежит И.Я.Акушскому, который не только внес значительный вклад в математическую теорию вычислений структур на основе СВ, но также осуществлял научное руководство разработкой первой отечественной ЭВМ, использующей эту систему. Дальнейшее развитие теории в этом направлении нашло свое отражение в многочисленных зарубежных и отечественных исследованиях.

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

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

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

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

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

Данные системы определяются в работе как дуальные смешанные системы (ДСС) включающие пару, которая состоит из позиционной системы и изоморфной по отношению к ней модулярной системы. Если первая система представляет собой обычную d-разрядную позиционную систему с основанием m, то во второй системе числа представляются совокупностью d вычетов по модулю т. Преобразование из одной системы в другую осуществляется с помощью соответствующих конгруэнции.

Дуальным системам ДСС присущи все достоинства СВ, связанные с модулярной структурой чисел и независимой, параллельной обработкой всех вычетов. Но, в отличие от СВ, эта система является не только модулярной, но и структурно истинно модульной, так как все вычеты чисел в ней представляются и обрабатываются по единому модулю т. Следовательно, ДСС более, чем СВ, технологична с точки зрения ее реализации. Кроме того, благодаря изоморфизму между СС и ИСС пара СС/ИСС обладает всеми достоинствами позиционных систем с точки зрения возможности естественного представления целых, вещественных и рациональных чисел, включая форматы с фиксированной и плавающей точкой. Но в отличие от позиционных систем скорость выполнения модулярных операций в изоморфной системе не зависит от ее разрядности, изменяемой в пределах до максимально возможного числа разрядов для выбранного модуля. В то же время, расширение разрядности СВ осуществляется за счет введения новых модулей большей величины. А поскольку быстродействие для СВ определяется скоростью операций по максимальному модулю, поэтому, все-таки, существует некоторая зависимость производительности от разрядности. Кроме того, изНза неоднородности СВ "неудобна" для представления и обработки текстовой информации и логических переменных.

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

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

В то же время, если в изоморфной системе в качестве модуля т вместо простого числа выбрано составное число, равное в общем случае произведению n простых чисел (модулей m_i; i = 1,..., n), тогда все результаты исследований в части СВ, полученные ранее и в данной работе, могут быть применены в рамках дуальной системы для процедур обработки вычетов, представляемых в СВ с системой модулей m_i.

Отметим еще одну проблему, общую в целом для компьютерных технологий. Одной из фундаментальных задач компьютерной алгебры является представление математических объектов в виде информации, числовых данных произвольной (теоретически неограниченной) длины. В современных двоичных компьютерах и системах микропроцессоры и процессорные элементы имеют ограниченную длину разрядной сетки до 64,128 бит. Поэтому, если информационная емкость объекта равна V бит и превышает возможности разрядной сетки, то он представляется уже q машинными словами длиной w бит, где V = qw. При этом обработка таких объектов выполняется более медленным по сравнению с отдельной машинной командой программным способом. В данном контексте как символы, так и объекты-это "слова", которыми оперируют вычислительные машины, их отличие – лишь в размерности. В тех случаях, когда информационная емкость объекта многократно или на многие порядки превосходит число бит, соответствующее машинным словам, это чисто количественное различие имеет далеко идущие качественные последствия в силу экспоненциального быстрого возрастания сложности обработки двоичных данных с ростом их длины.

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

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

Таким образом, новая система должна отличаться от дуальной лишь одним свойством: она должна обеспечить возможность представления и обработки информации произвольной длины при неизменной величине основания (модуля). Актуальность и достоинства подобного класса числовых систем очевидны. Сразу оговоримся, что в результате проведенных исследований была разработана такая система, которая определена как многоуровневая дуальная смешанная система (МДСС).

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

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

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

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

Одной из центральных проблем современной теории и практики вычислений является верификация их достоверности. Эта задача относится к интервальной математике, которая требует, по крайней мере, двойного счета при решении одной задачи [106]. Более высокие по сравнению с двоичными системами производительность и точность модулярных вычислений обеспечивают и более высокую эффективность автоматической верификации результатов этих вычислений.

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

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

Актуальность данного направления исследований подтверждается, например, введением в архитектуру последних моделей двоичных микропроцессоров ведущих производителей новых инструкций для SIMD и других видов параллельной обработки. Однако, вследствие того, что двоичные микропроцессоры имеют фиксированные форматы машинных слов (64,128 бит) и весьма малый объем регистровой памяти, введенный режим SIMD весьма ограничен возможностью параллельной обработки лишь одного вектора, включающего 4–8 элементов длиной 8–16 бит.

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

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

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

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

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

Краткое содержание

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

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

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

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

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

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

Другой пример применения СВ приведен в седьмой главе, в которой демонстрируется бесконфликтная система памяти на основе КТ. Система обеспечивает также обнаружение и коррекцию ошибок в процессе адресной трансляции.

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

В девятой главе демонстрируется метод экспоненциальных вычислений на основе СВ для криптографии. Основное его отличие от известных методов состоит в том, что вычет степени числа по модулю Р конструируется из двух вычетов по модулям Р + 1 и Р + 2. Если Р – простое, то Р + 1 и Р + 2 суть составные числа, что позволяет вести вычисления не по названным модулям, а по модулям, равным их факторам разложения.

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

На примере умножения полиномов с использованием теории конечных полей и колец в десятой главе рассматривается возможность введения дуальных смешанных систем, для которых вычислительная сложность этой операции определяется как O(d), а не O(d2), как для классической схемы умножения двух полиномов степени d – 1.

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

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

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

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

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

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

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

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

Об авторе

Кандидат физико-математических наук. Область научных интересов – параллельные вычисления и системы. В настоящее время основное внимание уделяет проблемам параллелизма на уровне вычислительных методов и данных на базе модулярной алгебры. Имеет несколько десятков публикаций в указанной области. Дважды получал международные исследовательские гранты.