Домашка по арифметике28.01.2020 10:08

Лёшенька, Лёшенька, сделай одолжение!
Выучи Алёшенька таблицу умножения !
Агния Барто

Сначала задачка для первоклассника. Дано некоторое положительное число. Нужно умножить на него другое число, заранее неизвестное. Вопрос, как посоветуют это сделать благородные доны ??? Бывалый разраб наверняка скажет, мол мужик, ставь умножитель и не парь мне мОзги. И возможно будет в корне неправ! Ибо кроме монстров от Alterra и Xilinx существует ещё и такое замечательное семейство как iCE-40 от Lattice. Ультрамикропотребляющее. Очень дешевое. Да вот беда, больно мелкие они, и увы, умножителей там нет. Я столкнулся с этим года 4 назад, когда портировал некий ADPCM-кодек с ассемблера adsp-2185 на такой кристалл.
Нет, без умножителя общего назначения (для двух переменных) там разумеется не обошлось. Пришлось сделать его ручками и он занял половину кристалла. Беда в том, что молотил он у меня в каждом такте, т.е. вообще без свободных окон. А кроме умножений переменных в алгоритме были фиксированные коэффициенты, на которые тоже надо было умножать. И использовать для этого умножитель не было никакой возможности, просто не оставалось свободного окна. А поскольку борьба в проекте шла за каждую ячейку, разумеется меня очень интересовало, как бы извернуться, и используя свойства этих коэффициентов сделать оптимальную схему умножения на них (не умножитель общего назначения, а устройство умножения на заданное число !). Ну и как полная сбыча мечт — чтобы схемы умножения на разные коэффициенты максимально использовали какие-то общие ресурсы кристалла.

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

Вспомним немного, как мы вообще умножаем число А на В.

1. Для начала положим результат равным нулю.
2. Пробежимся по разрядам A.
3. Если в разряде 0, ничего не делаем.
4. Если в разряде 1, сдвигаем B на соответствующее число разрядов и прибавляем к результату.

Итого, чем меньше в разрядах А единиц, тем проще на него умножать. Умножить на 2, 4 или 8 совсем легко. Нужен только сдвиг. Немного труднее умножить на 3, 5 или 10. Потребуются одно сложение. Ещё труднее умножить на 11. Чем больше единиц, тем труднее.

Ну, а как насчёт умножения на 255? Целых 8 единиц, кошмарная задача, правда? А вот и фигушки! Сделаем хитрый финт ушами. Умножим наше В на 256 (т.е. сдвинем на 8 разрядов) и вычтем его же из результата. Получается несмотря на грозный вид, умножить на 255 столь же легко, как и на 10. Столь же легко умножать и на 254, и на 240, и на 224 (если хотите, проверьте!).

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

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

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

Придадим нашим рассуждениям более регулярный вид. Для начала пусть у нас уже есть какая-то схема умножения на А. Возьмём в качестве В единицу. Тогда все слагаемые сдвинутся, сложатся и вычтутся таким образом, что в результате получится то же самое А. Итого, наша схема умножения на A есть ни что иное, как представление числа A в виде суммы степеней двойки, в котором слагаемые могут быть и со знаком + и со знаком -. А можно сгруппировать вместе положительные и отрицательные слагаемые, и сказать что схема описывается разностью неких чисел A+ и A-, равной A. Это плохо… Члены разности могут быть как угодно велики. Подумаем, есть ли какие-то соображения, позволяющие их ограничить?
Заметим прежде всего, что каждая степень двойки может входить в схему только один раз. В самом деле, если она входит дважды с одним знаком, это можно заменить степенью двойки на единицу бОльшей. Если она входит дважды с разными знаками, они взаимно вычитаются. Итого, схема очень напоминает обычное двоичное представление A. С той лишь разницей, что его «биты»(в дальнейшем будем называть их триты), могут принимать не два, а три значения: 1, 0 и -1.
Итого. Если A есть n-разрядное двоичное число, схема умножения на него описывается суммой:

где  — триты, принимающие значения 1, 0 и -1, а m некое пока неизвестное число.

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

Попытаемся найти m. Как видно из примера с умножением на 255, m никак не меньше n. Посмотрим, может ли оно быть равно n+1.
Пускай A как и прежде, положительное n-разрядное число. Тогда схема умножения задаётся как:

Вспомним, что 
Поэтому старший трит никак не может быть равен -1. Ведь даже если все остальные будут 1, сумма всё равно будет равна -1. А по условию A положительно. Пусть теперь старший трит равен 1. Но в этом случае следующий трит должен быть равен -1. Иначе сумма получится слишком большой. В самом деле, если следующий трит равен 0, сумма получится не меньше чем
В то время как n-разрядное A не больше . Но если старший трит равен 1, а следующий -1, то сумма двух старших членов равна . А значит старший трит равен 0.

Таким образом доказано важное утверждение: m=n.
Иными словами для представления любой схемы умножения на n-разрядное A достаточно n+1 степеней двойки — от 0 до n(на одну больше, чем для двоичного представления), что сразу избавляет нас от бесконечности.

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

Писать будем на питоне. Не потому что я такой его фанат, а потому что с ним крайне удобно работать в блокнотах jupyter. Для начала напишем класс TriScheme, работающий с введёнными выше троичными схемами, функцию allSchemes, вычисляющую с его помощью все схемы для чисел заданной разрядности простым перебором, и функцию printSchemes, распечатывающую результат:

class TriScheme():     
    def __init__(self, buf:list): # создает из массива
        self.buf=[]
        for i in range(0, len(buf)):
            s=0
            if (type(buf[i]) == int) or (type(buf[i]) == float):
                if buf[i]   > 0: s=1
                elif buf[i] < 0: s=-1
            self.buf.append(s)
            
    def zero(self): # обнуляет
        self.buf=[0]*len(self.buf)
        
    def __repr__(self): # представление в виде строки
        s=""
        for i in range(1, len(self.buf)+1):            
            if   self.buf[-i]==1:  s=s+"+"
            elif self.buf[-i]==0:  s=s+"0"
            elif self.buf[-i]==-1: s=s+"-"
        return s
            
    def inc(self):  # инкремент (переход к следующей)
        for i in range(0, len(self.buf)):
            if (self.buf[i]+1) < 2:
                self.buf[i]+=1
                break
            for j in range(0, i+1):
                self.buf[i]=-1
                
    def __int__(self):  # выдаёт значение
        m=1
        s=0
        for i in range(0, len(self.buf)):
            s+=self.buf[i]*m
            m=m*2
        return s
    
    def isMax(self): # проверяет что схема максимальна
        s=0
        for i in range(0, len(self.buf)):
            s+=self.buf[i]
        return (s == len(self.buf))
    
    def isMaxDig(self): # проверяет, что схема максимальная, соответствующая n-разрядному числу
        s=[0]*len(self.buf)
        s[0]=-1
        s[-1]=1
        return (self.buf == s)
        
    def ones(self): # выдает число ненулевых элементов (трудность схемы)
        s=0
        for i in range(0, len(self.buf)):
            if self.buf[i] != 0:
                s+=1
        return s
    
    def minPos(self):  # выдаёт номер минимальной ненулевой позиции
        for i in range(0, len(self.buf)):
            if self.buf[i] != 0:
                return i
                         
def allSchemes(dig): # считает все схемы для всех чисел разрядности dig
    sch=[]
    for i in range(0, 2**dig): sch.append([])
    ts=TriScheme([0]*(dig+1))    
    while True:
        sch[int(ts)].append(TriScheme(ts.buf))
        if ts.isMaxDig():
            break
        ts.inc()
    return sch

def printSchemes(sch):  # печатает список схем в формате число трудность количество_схем список_схем
    for i in range(0, len(sch)):
        s=sch[i]
        a=[]
        for j in range(0, len(s)): 
            a.append(s[j].ones())
        m=min(a)
        print(i, m, len(s), s)

# Вычисляем схемы для всех 4-разрядных чисел        
sch4=allSchemes(4)
printSchemes(sch4)

Вычислим схемы для всех 4-разрядных чисел:
0 0 1 [00000]
1 1 5 [0000+, 000±, 00±-, 0±--, ±---]
2 1 4 [000+0, 00±0, 0±-0, ±--0]
3 2 7 [000++, 00±+, 00+0-, 0±-+, 0±0-, ±--+, ±-0-]
4 1 3 [00+00, 0±00, ±-00]
5 2 8 [00+0+, 00++-, 0±0+, 0±+-, 0+0--, ±-0+, ±-±, ±0--]
6 2 5 [00++0, 0±+0, 0+0–0, ±-+0, ±0–0]
7 2 7 [00+++, 0±++, 0+0-+, 0+00-, ±-++, ±0-+, ±00-]
8 1 2 [0+000, ±000]
9 2 7 [0+00+, 0+0±, 0++--, ±00+, ±0±, ±+--, +0---]
10 2 5 [0+0+0, 0++-0, ±0+0, ±+-0, +0--0]
11 3 8 [0+0++, 0++-+, 0++0-, ±0++, ±+-+, ±+0-, +0--+, +0–0-]
12 2 3 [0++00, ±+00, +0–00]
13 3 7 [0++0+, 0+++-, ±+0+, ±++-, +0–0+, +0-±, +00--]
14 2 4 [0+++0, ±++0, +0-+0, +00–0]
15 2 5 [0++++, ±+++, +0-++, +00-+, +000-]

Здесь в начале строки число, за ним его трудность (минимальное количество ненулевых элементов в схеме), затем число схем, и наконец список схем.
В схеме + обозначает 1, 0 — 0, и - — -1. Старший трит слева (как при обычном написании чисел).

Из таблицы видно во-первых, что только числа 13 и 11 имеют трудность 3 (максимальную для 4-разрядных чисел, как доказано выше). И во-вторых, что число различных схем для каждого числа довольно велико. Это говорит во-первых о том, что умножение чаще всего операция сильно более простая чем нас учили в школе. И во-вторых о том, что для реализации устройств умножения на несколько констант с использованием общих ресурсов кристалла, выбор схем достаточно велик. Ещё интереснее выглядят данные по более длинным числам. Так для 14-разрядных чисел максимальная трудность получается равной 8. А максимальное число схем — 937.

Всё бы хорошо, но приведённый выше алгоритм слишком затратен. Его сложность растёт как  в зависимости от разрядности чисел n. Для 8 разрядов считается мгновенно. Для 14 — минуты. Для 16 — часы. Если нужно считать схемы ДЛЯ ВСЕХ n-разрядных чисел, увы, больше ничего сделать нельзя, кроме как переписать его на С и взять компьютер помощнее. Впрочем алгоритм прекрасно распараллеливается и наверняка может быть запущен на GPU или на кластере.

Для проектирования конкретных железок как правило требуются списки схем для конкретных чисел. Причём желательно ВСЕ, а не только оптимальные. Ибо какую выбрать, может зависеть от обстоятельств (например устройство умножения на несколько констант). И вот тут можно предложить алгоритм гораздо более гуманный. Ещё раз вспомним замечательное равенство: .
В контексте задачи это означает следующее. Пусть известны несколько старших тритов схемы. Все младшие триты, начиная с позиции k неизвестны и предварительно считаются равными нулю. Тогда изменяя каким угодно образом неизвестные триты, мы изменим значение схемы не более чем на плюс/минус . Причем с продвижением к младшим тритам величина этой неопределённости уменьшается. Это позволяет искать схемы методом последовательных приближений, трит за тритом.

Пусть дано положительное число A. Надо найти все схемы для него среди n-разрядных чисел. Абсолютную величину разности между A и значением некоторой схемы, назовём погрешностью схемы. Возьмем для начала n+1-разрядную схему, описывающую n-разрядные числа, все триты которой неизвестны, и изначально положены равными нулю. И начнём определять триты, один за другим, начиная со старшего. В k-й позиции схема может породить три новых схемы — со значениями k-го трита 1, 0 и -1. Оставим в списке схем для продолжения только те из них, погрешность которых не превышает . С получившимся списком схем перейдём к шагу в позиции k-1. Таким образом, в результирующем списке (в позиции 0) будут ВСЕ возможные схемы, значение которых равно A. Давайте напишем такую функцию calcSchemes.

def calcSchemes(a, n=-1):
    m=1
    nn=1
    while m < a:
        nn+=1
        m=m*2
    if n < nn:
        n=nn
    sch=[TriScheme([0]*n)]
    for i in range(0, n):
        tmp=[]
        pos=n-i-1
        for j in range(0, len(sch)):
            for k in range(-1, 2):
                ts=sch[j]
                ts.buf[pos]=k
                d=abs(a - int(ts))
                if d <= (2**pos - 1):
                    tmp.append(TriScheme(ts.buf))
        sch=tmp   
    return sch 

Ну и наконец обещанная сбыча мечт.
В том проекте было два коэффициента, на которые требовалось умножать: 16351 и 16318. Используя calcSchemes найдём схемы для этих коэффициентов:

Нам повезло! Оба коэффициента имеют трудность 3. Выбираем для обоих оптимальные схемы:
Для 16318 +0000000–0000–0 и для 16351 — +00000000–0000-. Нам ещё раз повезло! Обратите внимание на хвосты схем. Они для 16318 и 16351 отличаются только сдвигом влево на одну позицию. А значит устройство умножения на 16318 и 16351, включает только один добавочный мультиплексор, переключающий сдвинутый и не сдвинутый операнд на входе сумматора.
Давайте посмотрим результат. Напишем на верилоге три варианта устройства умножения на 16318 и 16351:

1. «Школьный» вариант (только сложения и сдвиги)
2. Оптимальная схема
3. Оптимальная схема, использующая общие ресурсы

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

Все три варианта работают правильно, умножая при 0 на входе s на 16318, а при 1 — на 16351. При этом yosys даёт для школьного варианта 488 ячеек, для оптимального — 206, и для варианта с общими ресурсами 202. Наверно он сам тоже что-то оптимизирует, хотя разница в 4 ячейки всё-таки есть. Как видим, разница со школьным вариантом очень приличная.

Ну и наконец. Возможно кому-то покажется излишним городить такой огород, только для того, чтобы элементарно сообразить, что 16318=16384–64–2, а 16351=16384–32–1. Однако во-первых числа могут быть и посложнее. Во-вторых, если устройство должно умножать несколько чисел, далеко не очевидно, что следует брать оптимальные схемы. Мне в том проекте просто повезло. В общем случае программа поиска схем может сильно помочь. Надеюсь статья кому-то оказалось полезной. И тот кто её прочитал, надеюсь не будет паниковать, если надо умножать, а умножителя нет.

© Habrahabr.ru