ALGORITHMS AND SCHEMES OF ADDING NUMBERS IN AN ARITHMETIC LOGIC UNIT WITH THE USE OF THE SYSTEM OF RESIDUAL CLASSES
Authors:
1.
Dagestan State Technical University
Type:
Article
Pages:
from 62
to 68
Status:
Published
Received:
05.01.2014
Accepted:
25.01.2014
Published:
25.01.2014
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.3.04
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
BBK 32.973.26-018.2
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.3.04
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
BBK 32.973.26-018.2
Language:
Russian
Keywords:
arithmetic logic unit, adder, algorithm, system of residual classes, parallel computing
Abstract (English):
The algorithm of adding two numbers in the system of residual classes taking into account the possibility of parallel computing is presented; the block diagram of a hardware implementation of the algorithm is shown. The upper bound on the number of cycles of the algorithm depending on the number of processors used and bit numbers is fixed. This estimation can be used to identify a desired number of parallel processors (cores) depending on the time constraints on the operation of addition and its related arithmetic operations.
The algorithm of adding two numbers in the system of residual classes taking into account the possibility of parallel computing is presented; the block diagram of a hardware implementation of the algorithm is shown. The upper bound on the number of cycles of the algorithm depending on the number of processors used and bit numbers is fixed. This estimation can be used to identify a desired number of parallel processors (cores) depending on the time constraints on the operation of addition and its related arithmetic operations.
Keywords:
arithmetic logic unit, adder, algorithm, system of residual classes, parallel computing
arithmetic logic unit, adder, algorithm, system of residual classes, parallel computing
Введение Одной из сфер, где наиболее эффективно проявляются возможности системы остаточных классов (СОК), являются процессоры вычислительных устройств. Это связано, в частности, с тем, что при использовании СОК многие арифметические операции могут быть табулированы и дальнейшие вычисления выполняются на основе таблиц. Отметим, что при работе с табличной информацией каждая операция выполняется приблизительно за три такта работы процессора: нахождение требуемого поля таблицы, выбор значения и пересылка его по требуемому адресу. Наиболее трудоемким из перечисленных этапов является нахождение требуемого поля таблицы. Время выполнения этой операции зависит прежде всего от размера таблицы и скорости работы процессора. Размер же таблицы для каждого конкретного основания Pi СОК определяется величиной этого основания. Одним из наиболее трудоемких этапов предлагаемого ниже алгоритма является преобразование из позиционной системы счисления (ПСС) в СОК. В рамках диссертационной работы [1] разработаны алгоритмы, позволяющие существенно повысить быстродействие данной процедуры. Однако, по нашему мнению, более эффективным может оказаться аппаратное решение данной проблемы, которое мы предполагаем выполнить в рамках исследований, отраженных в [2]. Разработка алгоритма сложения чисел Пусть имеется n-битовый процессор и используется СОК, основание , причем k делит n. Тогда, при условии, что длины всех приблизительно одинаковы, из неравенств получаем . В частности, если n = 128, k = 8, то . Отсюда выводим: каждая операция (сложение, умножение, деление и др.) по основанию может быть задана таблицей, имеющей размер порядка , что может быть приемлемым с точки зрения возможностей современных процессоров при достаточно длительном использовании данного основания . При n = 64, k = 8 и n = 32, k = 4 соответственно получаем и . Сравним предлагаемые алгоритмы с классическими с точки зрения выполнения основной арифметической операции – сложения. Как отмечалось во введении, операция сложения является одной из основных операций вычислительного устройства, на которую опираются другие вычислительные действия [1]. В частности, операции вычитания и умножения в решающей степени опираются на операцию сложения. Например, для формирования алгоритма умножения на основе алгоритма сложения может быть использовано соотношение [3]: . В настоящее время наиболее известные следующие алгоритмы сложения двух двоичных чисел следующие [4–7]. 1. Алгоритм последовательного переноса – RCA-алгоритм (ripple-carry adder). В этом алгоритме, выполняемом по классической схеме сложения двух чисел, числа складываются последовательно побитно, начиная справа налево. Если в результате сложения очередных двух битов возникает дополнительный бит, то он прибавляется к результату, получающемуся при сложении следующих (расположенных слева) битов. Таким образом, процедура сложения аналогична процедуре сложения чисел «вручную, с помощью бумаги и карандаша». Алгоритм является наиболее трудоемким из всех рассматриваемых и имеет порядок при сложении двух n-битовых чисел. 2. Алгоритм предсказуемого переноса – CLA-алгоритм (carry look-ahead adder). Это наиболее распространенный в настоящее время тип алгоритмов. Процессоры подавляющего большинства современных компьютеров работают на основе алгоритмов данного типа. Алгоритм имеет иерархическую структуру. Непосредственно сложение заданных чисел происходит по группам на нижнем уровне иерархии. На последующих уровнях обрабатываются результаты предыдущих уровней. Разнообразие алгоритмов данного класса обусловлено выбором размеров групп на каждом уровне иерархии, числа групп иерархии – параметр, тесно связанный с предыдущим, а также формой записи рекуррентных формул, используемых при выполнении расчетов и организации алгоритма. Разбиение на группы позволяет параллельно проводить вычисления в разных группах, что существенно повышает быстродействие алгоритма. Среди наиболее известных алгоритмов данного класса (учитывающими также особенности их практической реализации) – алгоритмы Брента – Канга и Когдже – Стоуна [6]. CLA-алгоритм опирается на концепцию генерации и распространения переноса. Сложение двух битов A и B генерирует бит, если при сложении этих битов получается 1 (записывается GG = 1) в качестве переноса (без учета возможного единичного бита переноса, полученного от сложения битов более низших разрядов). Из определения следует, что перенос генерируется тогда и только тогда, когда одновременно A = 1 и B = 1; поэтому событию генерирования бита сопоставим бинарный предикат , который равен 1 только в случае, когда генерируется бит. Сложение двух битов A и B распространяет бит, если при сложении этих битов, с учетом возможного дополнительного бита переноса от сложения предыдущих (более младших) разрядов, возможно возникновение бита переноса (значение обозначается PG). Из определения следует, что перенос распространяет бит тогда и только тогда, когда либо A = 1, либо B = 1 (либо оба равны единице); поэтому событию распространения бита сопоставим бинарный предикат , который равен 1 только в случае, когда распространяется бит. Как вариант можно взять), где – сложение по модулю два. Тогда нетрудно убедиться в справедливости следующих рекуррентных формул для i-го бита переноса Ci при сложении i-х разрядов и заданных двух чисел a и b (i = 0, 1, …): , , , . Из данного рекуррентного соотношения можно вывести следующее равенство: . (1) В качестве базового примера рассмотрим алгоритм сложения двух 32-битовых чисел. Алгоритм имеет 3 уровня иерархии. На нижнем (первом) уровне сформируем 8 групп по 4 бита в каждой, на втором – 2 группы, каждая из которых включает по 4 группы первого уровня. На третьем обрабатываем результаты второго уровня и формируем окончательный результат. Из последней рекуррентной формулы следует выражение, используемое для выполнения вычислений в процессорах: Окончательный результат находится по формулам : . Алгоритм является трехуровневым. При необходимости его модификации для работы со 128-битовыми и более «длинными» числами наиболее целесообразный способ модификации – это добавление новых уровней: четвертого, пятого уровня. Отметим, что скорость работы алгоритма при сложении двух n-битовых чисел для достаточно больших n имеет порядок (т. е. число шагов) не выше . 3. Алгоритм с записью переноса – CSA-алгоритм (carry-save adder). Он выдает два n-битовых числа, одно из которых является результатом побитового сложения по модулю 2 исходных чисел, а второе число является вектором из битов переноса для каждого разряда. Таким образом, в данном алгоритме формируется, отдельно от процедуры сложения, число, описывающее перенос. Общая структура алгоритма следующая. – , где сложение проводится побитно по модулю 2, при сложении переносы игнорируются. Отдельно формируется вектор (число) переноса C длины n по каждому разряду; – итеративно проводится серия следующих процедур до тех пор, пока не получим : , и на каждой итерации для последней операции сложения заново формируется новый вектор переноса C. В результате работы алгоритма в S будет получена сумма чисел a и b. Данный алгоритм в среднем (при равновероятности всех возможных входных значений) требует не более шагов [5]. Хотя средняя скорость CSA-алгоритма выше, чем у CLA-алгоритма, но для отдельных наборов чисел a и b число шагов может иметь порядок . CLA-алгоритм гарантировано (при любых значениях a и b) выполняется не более чем за , что и объясняет именно его использование в процессорах. 4. В работе предлагается следующий алгоритм сложения двух чисел. Предположим, что имеется n параллельных сумматоров и основание СОК выбрано и зафиксировано. В процессе выполнения вычислений необходимо найти сумму чисел A и B. Опишем алгоритм выполнения вычислений (рис. 1). I. Все числа преобразовываются из ПСС в модулярное представление в СОК в базисе модулей в заданном наборе модулей СОК, т. е. осуществляются операции преобразования вида , и т. д. II. Если число процессоров t меньше n, то модули основания упорядочиваются в порядке убывания: , где Запоминаются порядковые индексы чисел в исходном наборе . Если число , то этап II пропускается. III. Выполняются все требуемые вычисления. В частности, в процессе вычислений возникает необходимость сложения чисел A и B, которое выполняется следующим образом: 1. Для на i-м процессоре осуществляется операция сложения по модулю чисел и на основе CLA-алгоритма. 2. По мере освобождения каждого процессора выбираются очередные (по порядку расположения модулей ) числа и и складываются по основанию . IV. После выполнения всех вычислений выполняется обратное преобразование из СОК в ПСС. Рис. 1. Общая структурная схема сложения двух чисел в СОК при достаточном числе процессоров Если число процессоров не меньше числа модулей, то сложения по каждому модулю осуществляются параллельно и независимо от остальных вычислений (рис. 2; для упрощения блоки с текущими вычислениями опущены). Рис. 2. Общая структурная схема сложения двух чисел в СОК при недостаточном числе процессоров Приведем некоторые дополнительные пояснения по описанному алгоритму. 1. Упорядочение модулей позволяет уменьшить время сложения за счет того, что времена окончаний вычислений на различных процессорах имеют более равномерный характер (меньше флуктуируют), и это уменьшает время задержки при формировании набора . С использованием разработанного программного продукта было проведено порядка 100 компьютерных экспериментов вычислений сложения случайных чисел с упорядочением и без упорядочения модулей оснований. Было выбрано n = 4, величины модулей имели от 10 до 12 двоичных битов. Как и предполагалось, упорядочение модулей ускоряет процесс вычислений, и это увеличение составило порядка 6 %. Отметим, что выбор оптимального распределения вычислений отдельных сумм по различным процессорам сводится к задачам очередности теории расписаний [8, 9]. В общем случае задача является NP-полной, т. е. не существует достаточно эффективного (по затратам времени) метода ее решения. Именно поэтому вполне приемлемо использование предложенного метода упорядочения для повышения эффективности решения. 2. В процессе вычислений на процессоре предлагается использовать алгоритм CLA. Это связано с тем, что данный алгоритм, в отличие от алгоритма CSA, дает гарантированную оценку сложности вычислений. У алгоритма CSA, несмотря более высокую среднюю скорость его работы, возможны ситуации, когда скорость вычислений существенно выше средней, что обусловлено внутренней взаимосвязью складываемых чисел и используемого модуля основания. Задержка при одном вычислении на параллельных процессорах существенно понизит скорость вычисления суммы, поскольку для формирования выходного набора суммы необходимо наличие всех сумм по модулю . Пусть p – вероятность возникновения такой ситуации. Поскольку в процессе сложения выполняется t таких вычислений, то вероятность возникновения подобной ситуации равна . Таким образом, с увеличением числа используемых процессоров вероятность ситуации, когда возникнет задержка на одном из процессоров и это вызовет задержку в вычислении всего результата, растет линейно с ростом числа процессоров. При этом алгоритм CLA может быть реализован по одноуровневой схеме, поскольку каждый модуль как число относительно невелик и записывается относительно небольшим числом двоичных битов. Таким образом, при использовании СОК в многопроцессорных системах на каждом из процессоров может быть реализована операция сложения лишь по одному из модулей (при достаточном числе процессоров), и эта операция, в силу относительно небольшой величины модуля, может быть реализована по одноуровневой схеме, что чувствительно повысит быстродействие выполнения операции суммирования по сравнению с известной классической многоуровневой схемой. Пример схемы реализации подобного алгоритма на основе формулы (1) приведен на рис. 3. Отметим, что в этом случае в развернутом виде формула (1) записывается следующим образом: ; ; ; . Здесь – биты результата сложения двух чисел; – вектор переноса, причем соответствует случаю переполнения результата сложения исходных чисел A и B. Как видно из схемы, для реализации алгоритма достаточно четырех машинных тактов работы. Увеличение длин модулей добавит в схеме новые «столбцы», усложнив ее, но не увеличит число тактов работы. Рис. 3. Структурная схема реализации алгоритма суммирования Разработанный нами алгоритм имеет ряд важных преимуществ по сравнению с остальными. Перечислим основные из них. 1. Высокая степень готовности и приспособленности для распараллеливания вычислений. Возможность полноценно реализовывать технологию параллельных вычислений. 2. Возможность существенно чаще использовать возможности табличных вычислений. Это связано с тем, что достаточно иметь таблицы вычислений только для отдельных модулей, величины которых относительно малы. 3. Независимость вычислений по каждому модулю обеспечивает значительную гибкость проектирования кристалла, позволяя в принципе использовать различные технологии проектирования и разработки каждого вычислительного модуля. 4. Возможность наращивания числа вычислительных модулей по мере необходимости; в частности с целью параллельного дублирования вычислений, их контроля по заданным ограничениям и тем самым – повышения надежности работы сумматора. 5. Отсутствие трассировочных межмодульных соединений, что обеспечивает некоторое уменьшение потребляемой мощности и уменьшение задержек по критическим путям. 6. Отсутствие специальных требований по синхронизации между отдельными модулями (за исключением синхронизации на входе и выходе), что значительно облегчает трассировку цепей тактовых частот и тем самым повышает надежность работы сумматора. Приведённые факторы, наряду с преимуществами модулярных вычислителей в быстродействии, позволяют говорить о вычислениях в СОК как о перспективной технологии разработки высокопроизводительных вычислительных систем, функционирующих в реальном времени. Оценим быстродействие предлагаемого алгоритма. Рассмотрим наихудший случай, когда вычисления выполняются на одном процессоре. Пусть Pi есть одно из чисел, входящих в основание , и есть вероятность того, что . Для определенности предположим, что сложение двух чисел по модулю Pi производится на основе RCA-алгоритма. Тогда среднее число тактов , которые потребуются для сложения двух чисел, не превосходит величины . Для оценки воспользуемся следующим неравенством Йенсена [10]: для любой случайной величины с конечным математическим ожиданием и выпуклой вверх функции справедливо неравенство , где M – знак математического ожидания. Так как функция выпукла вверх по x, то по неравенству Йенсена имеем , где в качестве рассматривается длина основания модуля; – средняя длина основания модуля Pi. Пусть теперь вычисления выполняются в процессоре, имеющем не менее k параллельных вычислительных каналов. Тогда сложение будет выполнено не более чем за тактов. Если длины всех приблизительно одинаковы, то, как показано выше, , и сложение будет выполнено не более чем за тактов работы, что при k > 1 существенно меньше, чем при использовании CLA-алгоритма. Отметим, что данная оценка является гарантированной, т. е. выполняемой при любых входных данных. Аналогично, используя по каждому каналу CSA-алгоритм, можно показать, что среднее число тактов для сложения двух n-битовых чисел при использовании k параллельных каналов не превосходит в среднем величины , но данная оценка не является гарантированной, а выполняется в среднем при условии, что все возможные сочетания входных чисел a и b равновероятны. Заключение Сравнив все перечисленные выше алгоритмы, можно заключить: при использовании параллельных вычислений предлагаемый в работе алгоритм является наиболее эффективным алгоритмом сложения чисел. В целом процесс вычисления на основе данного алгоритма может иметь задержку, связанную с преобразованием исходных чисел в СОК. Однако при проведении серии вычислений данная величина становится несущественной, особенно если преобразование чисел осуществляется на основе таблиц.
1. Magomedov Sh. G. Algoritmy i struktury ustroystv preobrazovaniya chislovoy informacii v sistemah obrabotki dannyh / Sh. G. Magomedov: dis. … kand. tehn. nauk. Astrahan', 2011. 22 c.
2. Magomedov Sh. G. Variant arhitektury zaschischennogo mikroprocessora na osnove sistemy ostatochnyh klassov / Sh. G. Magomedov // Prikaspiyskiy zhurnal: upravlenie i vysokie tehnologii. 2013. № 4. S. 118-125.
3. Chervyakov N. I. Principy postroeniya modulyarnyh summatorov i umnozhiteley / N. I. Chervyakov, I. V. D'yachenko // Materialy Mezhdunar. nauch. konf. «Modulyarnaya arifmetika» [Elektronnyy resurs]: http://www.computer-museum.ru/histussr/sokconf0.htm.
4. Katz R. Contemporary Logic Design / R. Katz. The Benjamin/Cummings Publishing Company, 1994. P. 249-256.
5. Vahid F. Digital Design / F. Vahid. John Wiley and Sons Publishers, 2006. P. 296-316.
6. [Elektronnyy resurs]: http://en.wikipedia.org/wiki/Lookahead_Carry_Unit.
7. [Elektronnyy resurs]: http://www.aoki.ecei.tohoku.ac.jp/arith/mg/algorithm.html.
8. Shkurba V. V. Zadacha treh stankov / V. V. Shkurba. M.: Nauka, 1976. 96 s.
9. Konvey R. V. Teoriya raspisaniy / R. V. Konvey, V. L. Maksvell, D. V. Miller. M.: Nauka, 1975. 360 s.
10. Feller V. Vvedenie v teoriyu veroyatnostey i ee prilozheniya. T. 2. M.: Mir, 1984. 738 s.
