ГУАП КАФЕДРА № 52 ПРЕПОДАВАТЕЛЬ доцент Белоголовый В. Г. должность, уч. степень, звание подпись, дата инициалы, фамилия Курсовая работаНа тему: “Работа в системе остаточных классов” По дисциплине: Инженерно-техническая защита информации ^ РАБОТУ ВЫПОЛНИЛ СТУДЕНТ ГР. 5821 Качанов С. С. дата инициалы, фамилия Санкт-Петербург2011В данной работе система остаточных классов и модулярная арифметика рассматриваются как средства повышения производительности и надёжности вычислений. Обладая возможностью распараллеливания, модулярные вычисления для повышения эффективности требуют разработки специализированных схем выполнения арифметических операций в модулярных каналах. Рассмотрены базовые принципы и преимущества вычислений в системе остаточных классов, обозреваются основные результаты, полученные в этом перспективном направлении. Задачу повышения скорости и надёжности вычислений можно рассматривать с двух сторон. С одной стороны это аппаратный уровень, фундаментальными ограничениями на котором являются технические возможности создания элементной базы – уменьшение размеров кристаллов, увеличение частоты синхронизации (тактовой частоты), решение проблем теплоотвода и др. Во многом этот уровень определяется современным состоянием фундаментальных наук, прежде всего, физики. С другой стороны это – математико-алгоритмический уровень вычислений, и фундаментальными ограничивающими факторами здесь выступают, в числе прочих, необходимость последовательного вычисления, когда следующий этап (шаг) частично или полностью зависит от предыдущих шагов. Даже простейшие арифметические операции сложения и умножения (не говоря уже о делении) при реализации их вычислителями с архитектурой фон-Неймана осуществляются побитого /КААК??/, и вычисление каждого последующего бита зависит от результата операции над предыдущими битами (в данном случае это знак переноса – carry sign). Существуют и другие вычислительные архитектуры, в которых акцент сделан на параллельность и массовость вычислений. Большую популярность сейчас имеют нейронные сети, которые, обладая алгоритмической универсальностью машины Тьюринга, уже доказали своё преимущество в слабо формализованных задачах, связанных с необходимостью обучения. Использование системы остаточных классов (СОК) и модулярных вычислений позволяет существенно увеличить скорость арифметических вычислений за счёт параллельного выполнения операций над остатками. Современная аппаратная база позволяет также заменять арифметические операции над остатками однотактными табличными выборками. Разработан вычислительный объект «нейронная сеть конечного кольца», сочетающий преимущества модулярного представления информации, и параллельность и помехоустойчивость нейронных сетей. Долгое время модулярная арифметика рассматривалась как интересный сугубо теоретический вопрос из-за сложности производства вычислительных структур для её реализации. Современное развитие технологии интегральных схем сделало возможным использование модулярной арифметики для многих областей цифровой обработки сигналов, распознавания образов и других задач, требующих интенсивных вычислений.^ Система остаточных классов – непозиционнаясистема счисления Пусть заданы взаимно простые положительные числа m1, m2,..., mL, которые называют основаниями или модулями системы (НОД(mi, mj) = 1 для i≠j). Число , называют вычислительным диапазоном получившейся числовой системы. Любое число X из кольца целых чисел по модулю M, XZ(M), имеет уникальное представление в заданной СОК /при первом использовании сокращения – дать расшифровку!/. (1) СОК могут быть также представлены и отрицательные числа из диапазона {-(M - 1) / 2,…, -1, 0, 1,…, (M - 1) / 2} для нечётного M и {- M/2,…,-1, 0, 1, (M/2) - 1} для чётного M . При этом, если X (2) Основным достоинством СОК является то, что арифметические операции производятся в ней независимо по каждому из модулей, следовательно, они могут выполняться параллельно по L вычислительным каналам:(3) Малоразрядность обрабатываемых остатков позволяет для повышения быстродействия арифметических операций в вычислительных каналах применять методы табличной подстановки (LUT). Более подробно модулярная арифметика в вычислительных каналах будет рассмотрена ниже, а пока же обратим внимание на следующее фундаментальное положение, лежащее в основе модулярных вычислений.^ Китайская теорема об остатках (КТО). Пусть даны попарно взаимно простые модули , и число X Z (M), СОК-представление которого определяется выражением: (4) Тогда: (5) Иными словами, кольцо целых чисел по модулю M, Z (M), изоморфно прямой сумме колец целых чисел по модулям , и существует единственное X Z (M), , восстанавливаемое по остаткам из выражения (4) по формуле: (6) где = и - обратный по умножению в кольце Z(mi) элемент для mi: Конечно, в Древнем Китае эта закономерность была сформулирована не в таком виде, а, вероятнее всего, в виде алгоритма решения математических загадок типа «необходимо определить число, имеющее остатками 2, 3, 2, соответственно, при делении на 3, 5, 7» (речь идёт о числе 23) В XVIII веке Эйлер продемонстрировал одно из возможных применений КТО для модулярных вычислений в СОК, а в XIX веке К.Ф.Гаусс доказал эту теорему, заложив основы современной теории СОК. Таким образом, КТО предоставляет фундаментальный метод для замены операций в кольце Z (M) на операции в нескольких независимых кольцах Z(mi), осуществляемые параллельно (5).^ Модулярные вычисленияКак было отмечено выше (3), операции сложения и умножения в СОК осуществляются параллельно по L вычислительным каналам. Обобщенная структура устройств цифровой обработки сигналов в модулярной арифметике представлена на рис. 1. Число X на входе преобразовываются из позиционной системы счисления (ПСС) в модулярное представление в СОК в базисе модулей после чего выполняются независимые вычисления для каждого модуля mi. На выходе происходит обратное преобразование из СОК в ПСС. Рис. 1. Общая структура устройств цифровой обработки сигналов в СОК. Cтруктура, изображённая на рис. 1, имеет ряд неоспоримых преимуществ при её реализации на интегральных схемах: 1. Независимость каждого канала по отдельному модулю обеспечивает значительную гибкость при планировке и топологическом проектировании кристалла. 2. Реализация таких устройств на основе ПЛИС, обладающих меньшими вентильными ресурсами, может быть легко перепланирована и размещена в несколько кристаллов. 3. Трассировочные межсоединения распространяются только внутри отдельного вычислительного канала, что исключает наличие длинных трасс и, как следствие, обеспечивает некоторое уменьшение потребляемой мощности и уменьшение задержек по критическим путям. 4. Отсутствие специальных требований по синхронизации между отдельными каналами (за исключением синхронизации на входе и выходе) значительно облегчает трассировку цепей тактовых частот, которые будут иметь меньшую расфазировку. Это, в свою очередь, приводит к уменьшению пиковых выбросов по цепям синхронизации. 5. При необходимости введение дополнительных избыточных каналов обеспечивает возможность построения отказоустойчивых систем.Приведённые факторы, наряду с преимуществами модулярных вычислителей в быстродействии и занимаемой площади, позволяют говорить о вычислениях в СОК как о перспективной технологии разработки высокопроизводительных систем, функционирующих в реальном времени. Поскольку в СОК используются модулярные операции, для высокой эффективности необходимо использовать специально спроектированные для СОК сумматоры и умножители. Существует достаточно большое количество подходов к реализации сумматоров по модулю m. Далее будут рассмотрены наиболее типичные и простые схемы модулярного суммирования (рис. 2). Первая из них вычисляет модульную сумму с помощью таблицы размером Для двух соответствующих элементов просто выбирается ответ из большой таблицы. Это решение очень хорошо подходит для случаев, когда длина слова мала, например, n 4 . Для больших модулей, память LUT была бы значительного размера и другие схемы для суммирования оказываются в этом случае более предпочтительными. Следующее предложение основывается на обычном суммировании x + y и одной таблицы, содержащей все возможные значения для . При этом существенно сокращается размер подстановочной таблицы с до что даёт возможность расширять набор модулей в случае необходимости большего динамического диапазона или избыточных модульных каналов для коррекции ошибок. Третья схема суммирования является самой распространённой и наиболее предпочтительной в большинстве случаев. В этой схеме используется два сумматора и мультиплексор для выбора результата в соответствии с выражением: (9) Умножители на основе закона квадратов (рис. 3) вычисляют модулярное произведение с помощью следующего равенства (закон квадратов): (10), где 0 x, y , , (11) и произведение (12) Существование операции деления на 2 ставит под угрозу целочисленность промежуточных вычислений и, соответственно, правильность результата после использования таблиц подстановок. Более того, существование обратного по умножению по модулю m для 2 элемента, , гарантируется только в случае, если 2 не делит m (т.е. m – нечётно). Тэйлор в своей работе привёл доказательство теоремы, показав, что даже если при вычислении (11) будут промежуточные дроби, они взаимно уничтожатся. Умножители, основанный на арифметике указателей является сравнимой альтернативой по сложности и скорости умножителям, основанным на законе квадратов. Их использование ограничено простыми модулями и основывается на осуществлении преобразования в степенную форму (так называемое степенное исчисление), в котором умножение может более быстро осуществляться посредством операции суммирования. Метод работы этого умножителя связан с математическими свойствами полей Галуа обозначаемых GF(p), где p – простое число. Все ненулевые элементы поля Галуа могут быть получены путём многократного возведения в степень примитивного элемента – порождающёго /?/ поле GF(p) элемента g. Это свойство полей Галуа можно использовать для умножения в GF(m) благодаря использованию изоморфизма между мультипликативной по модулю m группой Q = {1, 2,…, m -1}, и аддитивной по модулю (m- 1) группой I = {0, 1,…, m - 2}. Этот изоморфизм может быть установлен следующим образом: : (13) и умножение над полем GF(m) может производиться по формуле: (14). Таким образом, умножение двух чисел qи q можно производить, вычисляя модулярную сумму соответствующих указателей i и i а затем проводя обратное преобразование из степенного пространства в исходный вид. Необходимо специально обрабатывать случаи, когда один из операндов на входе умножителя равен нулю и в этом случае назначать нулевой результат произведения. Это происходит потому, что не определён элемент в степенном пространстве, соответствующий нулевому элементу группы Q. Степени i и i для qи q, соответственно, могут быть заранее вычислены и помещены в LUT. Сложение степеней выполняет сумматор по модулю m - 1. Обратное преобразование из степенного представления i и i в исходное qи q, также может быть выполнено с помощью предварительно вычисленных LUT. Рассмотрим в качестве примера работу этого умножителя на примере умножения двух чисел 14 и 28 по модулю 31. Так как 31 – простое число, существует порождающий элемент g, дающий возможность ассоциировать каждый элемент мультипликативной группы Q = {1, 2,…, 31} с элементом аддитивной группы I = {0, 1,…, 30} . Соответствие задаётся выражением , где , и , . Эта таблица в сущности и представляет собой содержание LUT размером прямого и обратного преобразования в умножителе, изображенном на рис. 4. Рассмотрим работу умножителя Галуа (рис. 4, рис. 5, табл. 1) на примере умножения . Итак, и , а произведение получается посредством суммирования соответствующих им элементов i и i, выбранных из табл. 1. Таким образом, указатели оказываются i= 22 и i = 16 и = 8. Элементу в табл. 1 соответствуют , следовательно Таблица 1. Содержание LUT-таблицы для умножителя Галуа по модулю 31 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 24 1 18 20 25 28 12 2 14 23 19 11 22 21 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 6 7 26 4 8 29 17 27 13 10 5 3 16 9 15 На рис. 5 показано, каким образом происходит умножение чисел 14 и 28 по модулю 31 по схеме, изображённой на рис. 4. Для простоты две таблицы LUT1 и LUT2 объединены в одну и представляют собой таблицы, переводящие умножаемые числа в степенное представление по табл. 1, а в качестве сумматора выступает простой модулярный сумматор, изображённый на рис. 2(а). LUT3 выполняет сложение по модулю 30, а LUT4 переводит результат из степенного представления обратно в первоначальный. LUT4 представляет собой табл. 1, только отсортированную по . На рис. 5 ADDR на входе таблицы и [ADDR] на выходе показывают, что значение, поступившее на вход таблицы, рассматривается в качестве линейного адреса элемента, который будет выдан на выход таблицы, т.е. [ADDR] – это содержимое ячейки таблицы по адресу ADDR.Список литературы: 1. Neto J. P., Siegelmann H. T., Costa J. F., Araujo C. P. S. Turing Universality of Neural Nets (revisited). // Lecture Notes in Computer Science – 1333, Springer-Verlag, 1997. pp. 361-366. 2. Червяков Н. И., Сахнюк П. А., Шапошников А. В., Ряднов С. А. Модулярные параллельные вычислительные структуры нейропроцессорных систем / Под ред. Н. И. Червякова. –М.: Физматлит, 2003. – 288 с. 3. Червяков Н. И., Сахнюк П. А., Шапошников А. В. Макоха А.Н. Нейрокомпьютеры в остаточных классах. Учебное пособие для вузов (научная серия «Нейрокомпьютеры и их применение, ред. А. И. Галушкин, кн. 11). –М.: Радиотехника, 2003. – 272 с. 4. Акушский И. Я., Юдицкий Д. И. Машинная арифметика в остаточных классах. –М.: Советское радио, 1968. 5. Ноден. П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями): Пер. с франц. – М.: Мир, 1999. – 720 с. 6. Gauss C. F. Disquisitiones Arithmeticae. Yale University Press, New Haven, 1966. 7. Стемпковский А. Л., Корнилов А. И., Семёнов М.Ю. Особенности реализации устройств цифровой обработки сигналов в интегральном исполнении с применением модулярной арифметики. // Информационные технологии, №2, 2004. С. 2–9. 8. Bayoumi M. A., Jullien G. A., Miller W. C. A VLSI Implementation of Residue Adders, // IEEE Transactions on Circuits and Systems, vol. CAS-34, # 3, 1987. 9. Lakhani G. Some Fast Residual Arithmetic Adders, //International Journal of Electronics, vol. 77, #2, 1994. pp. 225–240. 10. Dugdale M. VLSI Implementation of Residue Adders Based on Binary adders, // IEEE Trans. on Circuits and Systems II, vol. 39, #5, 1992. pp. 325–329. 11. Taylor F. Large Moduli Multipliers for Signal Processing, //IEEE Transactions on Circuits and Systems, vol. CAS-28, #7, 1981. pp. 731–736. 12. Jullien G. A. Implementation of Multiplication, Modulo a Prime Number, with Applications to Number Theoretic Transforms, // IEEE Transactions on Computer, vol. C-29, #10, 1980. pp. 899–905. 13. Radhakrishman D., Yuan Y. Fast and Highly Compact RNS Multipliers, // International Journal of Electronics, vol. 70, #2, 1991. pp. 281–293. 14. Krishna H., Krishna B., Lin K.Y., Sun J.D. Computational Number Theory and Digital Signal Processing. Fast Algorithms and Error Control Techniques. – CRC Press, 1994. 15. Krishna H. Digital Signal Processing Algorithms, Number Theory, Convolution, Fast Fourier Transforms, and Applications. – CRC Press, 1998.1. По тексту указать – что откуда [1] [2] и т.д. 2. и – самое интересное: -СОК – не самоцель, в какой мере подходит она для поиска решения поставленной задачи (нахождение простых чисел, если не ошибаюсь – тем более, что модули СОК – простые числа))? Можно ли эту задачу распараллелить для СОК? -какой подвиг надо совершить, чтобы реализовать многоядерность процессоров для решения ОДНОЙ задачи? Ибо существуют понятие Искусственный параллелизм, и одно из его проявлений – разложение большой задачи на параллельно выполняемые СОК-элементарные подзадачи 3. и – возможно, весьма неприятное – не уйдет ли все быстродействие в свисток при преобразованиях ПСС-СОК и обратно...4. Интересный сайт я тут нашел http://oeis.org/Seis.html и пока просто не успел изучить до конца - нет ли там последовательности простых чисел?