Оптимизация алгоритма центра тяжести осуществляется под RISC-архитектуру микроконтроллера IP2022 фирмы Ubicom. Выбор 8-ми разрядного микроконтроллера для данной задачи обусловлен простотой его архитектуры, что дает возможность эффективно разрабатывать программное обеспечение на языке ассемблера. Использование же, например, 32-х битных микроконтроллеров ARM (Advanced RISC Machine) с программной основой – языком С, не дает ожидаемого значительного увеличения скорости вычислений в силу ограничений компилятора.
Принцип оптимизации основан на учете особенностей входящих в вычисления операндов и очередность арифметических действий. В математической записи центр тяжести представляется как
,
где s = {s[j]} – массив входных данных длиной N.
Оптимизация алгоритма иллюстрируется на примере N = 1024 при µ = 8 разрядном квантовании отсчетов s. Обозначим числитель и знаменатель выражения центра тяжести как P и S соответственно:
, .
Каждое слагаемое вида (j×s[j]) входящее в P, имеет разрядность h = log2 N + µ = 18 бит. Максимальная величина P при этом представляется log2 N + h = 28 битами. Т.е. при 8-ми битной разрядной архитектуре числитель представляется 4 байтами P0…P3. Аналогичные рассуждения приводят к разрядности log2 N + µ = 18 бит величины S, т.е. числитель представляется тремя байтами S0…S2.
В архитектуру микроконтроллера IP2022 входит аппаратный умножитель 8´8. Именно это обстоятельство позволяет произвести оптимизацию алгоритма, которая недоступна компилятору языка C работающего с фиксированным (определенным заранее) типом переменных, т.е. в данном случае с целыми 32-х битными числами с программной реализацией умножения.
Множитель s[j], входящий в выражение числителя, имеет разрядность 8 бит, поэтому требуется привести к этой сетке множитель j. Представим j в виде
,
где i = 0…255, k = 0…3. Т.е. весь массив данных разбивается на четыре группы по 256 отсчетов, и при этом получается внутренний 8-ми битный указатель i = 0…255.
Вычисления в пределах первой группы реализуются в явном виде, т.е.
P = P + i × s[i].
Слагаемое (i × s[i]) имеет разрядность 16 бит и оно прибавляется к младшим байтам P0 и P1, а к байту P2 прибавляется ноль с учетом флага переноса.
Во второй группе (k = 1) указатель i оказывается в 256 раз меньше, что учитывается дополнительным слагаемым s[j], смещенным влево на 8 бит:
P = P + i × s[j] + (s[j] << 8),
где знак «<<» означает сдвиг операнда влево на указанное число бит. Фактическая реализация сдвига не требуется т.к. s[j] прибавляется к байтам P1…P3 с пропуском младшего байта P0.
В качестве указателя i используется младший байт номера j отсчета, что позволяет обойтись без дополнительного указателя на 256 отсчетов и соответственно без вычислительных затрат на операции с ним.
Третья и четвертая группы реализуются аналогично второй, но дополнительное слагаемое предварительно умножается на 2 и 3 соответственно, т.к. указатель i оказывается меньше в 512/256 = 2 и 768/256 = 3 раз. Некоторый выигрыш можно получить заменой умножения на 2 смещением s[i] влево на 1 бит через флаг переноса.
Накопление знаменателя практически не может быть оптимизировано, а деление производится один раз, т.е. наиболее трудоемкая в вычислительном отношении процедура накопления числителя является достаточной. Программная реализация оптимизированного алгоритма (накопление числителя и знаменателя) приведена в Приложении; язык программирования ассемблер.
Использование оптимизированного алгоритма, совмещенного по времени с выполнением синхронизации периферии, дал возможность обрабатывать до 6000 массивов по 1024 отсчета каждый в секунду. Сравнительный анализ вычислительной эффективности показал более чем двадцатикратный выигрыш по сравнению с алгоритмом реализованным на языке С при оптимизации компилятора по скорости.
Дополнительное сравнение было произведено с 32-х битным микроконтроллером на ядре ARM7, также при написании программы на языке С. Выигрыш оптимизированного алгоритма на более слабом микроконтроллере IP2022 при равных тактовых частотах составил более чем пять раз.
; инициализация указателя на массив данных
mov W,#0
mov IPL,W
mov W,#0 ; старший байт указателя на начало массива
mov IPH,W
mov W,#0
; обнуляем накапливающий сумматор знаменателя (24 бита)
mov s0,W
mov s1,W
mov s2,W
; обнуляем накапливающий сумматор числителя (32 бита)
mov p0,W
mov p1,W
mov p2,W
mov p3,W
; -------------------------
; ----- первая группа -----
mov W,#0 ; 256 отсчетов
mov count0,W
a0: mov W,(IP)
; накопление знаменателя (16 бит)
add s0,W
mov W,#0
addc s1,W
; накопление числителя (24 бита)
mov W,(IP)
mulu W,IPL
add p0,W
mov W,MULH
addc p1,w
mov w,#0
addc p2,W
inc IP
decsnz count0
jmp a0
; -------------------------
; ----- вторая группа -----
mov W,#0 ; 256 отсчетов
mov count0,W
a1: mov W,(IP)
; накопление знаменателя (24 бита)
add s0,W
mov W,#0
addc s1,W
addc s2,W
; накопление числителя (32 бита)
mov W,(IP)
mulu W,IPL
add p0,W
mov W,MULH
addc p1,w
mov w,#0
addc p2,W
addc p3,W
mov W,(IP) ; сдвиг на 8 бит
add p1,W
mov W,#0
addc p2,W
addc p3,W
inc IP
decsnz count0
jmp a1
; -------------------------
; ----- третья группа -----
mov W,#0 ; 256 отсчетов
mov count0,W
a2: mov W,(IP)
; накопление знаменателя (24 бита)
add s0,W
mov W,#0
addc s1,W
addc s2,W
; накопление числителя (32 бита)
mov W,(IP)
mulu W,IPL
add p0,W
mov W,MULH
addc p1,w
mov w,#0
addc p2,W
addc p3,W
mov W,(IP) ; сдвиг на 9 бит
rlf W,0 ; сдвиг влево через флаг переноса
addc p1,W
mov W,#0
addc p2,W
addc p3,W
inc IP
decsnz count0
jmp a2
; ----------------------------
; ----- четвертая группа -----
mov W,#0 ; 256 отсчетов
mov count0,W
a3: mov W,(IP)
; накопление знаменателя (24 бита)
add s0,W
mov W,#0
addc s1,W
addc s2,W
; накопление числителя (32 бита)
mov W,(IP)
mulu W,IPL
add p0,W
mov W,MULH
addc p1,w
mov w,#0
addc p2,W
addc p3,W
mov W,(IP) ; сдвиг на 8 бит с умножением на 3
mulu W,#3
add p1,W
addc p2,MULH
mov W,#0
addc p3,W
inc IP
decsnz count0
jmp a3
; месторасположение процедуры деления P / S (32 / 24 бит)
[\pre]
