«Энтропия, эргодический источник, многомерное пространство сообщений, биты, многосмысленность, процесс Маркова — все эти слова звучат весьма внушительно, в каком бы порядке их ни расположили. Если же расположить их в правильном порядке, они обретают определенное теоретическое содержание. И настоящий специалист порой может с их помощью найти решение повседневных практических задач.»
Джон ПИРС «Не вижу зла»
Данный пост насыщен рассуждениями о тонкой оптимизации выполнения математических операций на МК с ограниченными ресурсами, а также субъективными оценками различных аспектов разработки встроенного ПО.
Тех, кого данное предупреждение не испугало, прошу под кат.
Прежде, чем мы перейдем к описанию процедуры извлечения корня квадратного из целого числа, операции, обратной к возведению в квадрат и, соответственно, умножению, поговорим о последнем.
Предположим, что у нас есть возможность умножать 8-битное число на 8-битное, получая 16-битный результат (8*8=16), как нам на основе это операции получить реализацию операции 16*16=32. Очевидный способ заключается в представлении 16, как суммы двух 8, тогда получаем
А(16)*Б(16)=(а1(8)*256+а2(8))*б1(8)*256+б2(8)) =а1*б1*256*256+а1*б2*256+а2*б1*256+а2*б2Если в получившемся выражении заменить умножение на 256 сдвигом влево на 8 разрядов, то получается вполне рабочий алгоритм. Оценим временные затраты на реализацию — нам потребуется 4 умножения 8*8=16 и 4 сложения 4х байтных чисел 32+32=32. Для МК типа AVR получим 4*2+4*4=24 такта, но это для решения «в лоб». Попробуем улучшить полученный результат. То, что нам потребуется не 4, а 3 сложения и одно присвоение, несколько ситуацию упрощает, поскольку не потребуется начальное обнуление результата, но мы его все равно не учитывали, хотя надо было и общее время должно быть 24+4=28 тактов. Но, если мы примем во внимание наличие сдвига при первых трех слагаемых (соответственно имеем, что младший (два младших байта) равен нулю и прибавлять его к результату нет никакого смысла), то прибавлять придется не 4 байта, а три и два, что сократит время исполнения на 1*2+2=4 такта и получим 20 тактов. Далее мы можем обратить внимание на то, что первое и последнее слагаемое вообще не пересекаются, что позволит заменить обнуление старшей половины результата присвоением первого слагаемого и уменьшить время исполнения еще на 2 такта до 18. Далее, используя особенности архитектуры, а именно наличие команды пересылки регистровой пары, сэкономим еще два такта и итоговый результат — 16 тактов вместо исходных 28 — мелочь, а приятно.
Аналогичные методы оптимизации работают и для операции 32*32=32, для которой можно сократить время исполнения с ожидаемых 4*4*(2+4)+4=100 тактов до (3+5+4+3)+(5+3+3)+(4+3)+3=36 тактов, что совсем неплохо. Ну и в завершение рассмотрения различных вариантов умножения отметим, что 16*16=16 можно получить за 3+3+3=9 тактов. Отметим, что все эти рассуждения справедливы только в предположении наличия операции 8*8=16 за 2 такта, и, если ее нет на целевом МК, время выполнения всех остальных версий операции точно быстрее не станет.
Подведем итоги требуемого для выполнения умножения времени (8*8=8 2, 8*8=16 9, 16*16=16 16, 16*16=32 36) и рассмотрим теперь исходную задачу.
Нам необходимо извлечь целочисленный корень квадратный из 32 битового числа Н, то есть найти наибольшее 16 битное число н такое, что н*н<=Н. Все мы из курса средней школы знаем метод последовательного приближения к корню квадратному (н=(Н/н'+н)/2), но при его использовании нам придется делить целые числа, а это очень затратная по времени операция.
Поэтому были разработаны другие схемы вычисления, одна из которых — метод поразрядного приближения, который в псевдо-коде выглядит следующим образом:
- начальные значения -> н=0; б=0х8000;
- выполнять 16 раз -> если ((н+б)*(н+б)>=Н) н=н+б; б=б>>1;
Можно сразу оценить затраты времени на выполнение данного варианта 16(количество бит результата)*(2(организация цикла)+2(сложение)+Х(умножение)+5(сравнение и решение)+2(модификация результата)/2(в среднем половину раз)+2(сдвиг бита))=16*(12+Х). Вы спросите, а почему в формуле Х вместо числа 16, и выясняется, что нас ожидала засада, раз мы пишем на языке С, а не на ассемблере. Дело в том, что в стандартной библиотеке нет операции умножения со сменой разрядности и мы не можем применить 16*16=32, а вынуждены использовать 32*32=32, что приводит к Х=36 вместо Х=16 и итоговой цифре в 16*48=768 тактов на извлечение целого значения корня квадратного из 32-битного числа.
Конечно, это намного лучше, чем метод Ньютона, но многовато, посмотрим, что можно сделать.
Итак, очевидно, что основное время уходит на вычисление очередного результата умножения. Конечно, можно переписать на ассемблере и использовать менее затратную версию умножения, получив 16*(12+16)=448 тактов, но этот путь мы оставим на крайний случай. Рассмотрим процесс внимательнее и увидим, что мы вычисляем не умножение случайного числа на само себя, а умножение предыдущего значения с некоей прибавкой, причем квадрат предыдущего значения известен. Значит, мы можем прибегнуть к разностной схеме, опираясь на формулу (н+б)*(н+б)=н*н+2*н*б+б*б. На первый взгляд выглядит издевательством — вместо одного умножения нам потребуется выполнить четыре штуки да еще и два сложения длинных (32-битных) чисел. Но начнем разбираться: н*н у нас уже есть, б*б с учетом того, что б=б'/2 легко получить, как б'*б'/4, и аналогично 2*н*б=2*н*б'/2.
Вырисовывается следующая схема вычислений:
- начальные значения -> нн=0; н=0; б=0х8000; бб=б*б;
- повторять 16 раз -> если (нн+н+бб>=Н) {н=н+б; нн=нн+бб+н}; бб>>2; б>1;
Оценим затраты на реализацию 16*(2(организация цикла)+12(присвоение и два сложения)+5(сравнение и решение)+(2(сложение)+8(два сложения))/2(в среднем половину раз)+8(сдвиг вправо на 2)+2(сдвиг вправо)=16*34=544 такта. Уже лучше, чем с неправильным умножением 32*32, а у нас еще остались резервы.
В чем они заключаются — обратим внимание на самую затратную операцию — сложение и сравнение в общей сложности 17 тактов и переделаем основной цикл алгоритма:
2. повторять 16 раз -> Т=Н-бб-н; если (Т>=0) {Н=Т; н=н+б);}; бб>>2; б>1;
Тогда время выполнения цикла составит 16*(2(организация цикла)+12(вычисление новой разности) +1(сравнение и решение) +((4(присвоение)+2(сложение))/2(в среднем половину раз)+8+2)=16*28=448 тактов, если учесть особенности архитектуры, то можно сэкономить еще 2+2=4*16=64 такта и уложиться менее, чем в 400 тактов.
Мы получаем даже чуть лучший результат, как и при использовании правильного умножения 16*16=32, но без ассемблера, «на чистом С». Однако есть и существенный минус — если в варианте с умножением все интуитивно понятно, то вариант с разностной схемой без комментариев производит впечатление сеанса черной магии, выбирать Вам. Отметим также, что мы разменяли количество тактов на дополнительную память для промежуточных переменных, обычно так и бывает.
Необходимое замечание — мы не получили существенного (в разы) выигрыша по сравнению с умножениями, поскольку у нас есть быстрая реализация 8*8=16. Если она отсутствует в МК (а это бывает) или не столь быстра (и это тоже бывает), то разностная схема становится кратно быстрее, поскольку она использует только стандартные операции сложение и сдвиг, которые в любом МК гарантировано есть.
Казалось, лучше уже не получится, но, оказывается, есть еще резервы повышения производительности алгоритма. Попытаемся использовать другой классический метод ускорения — разделяй и властвуй. Что, если сначала извлечь корень квадратный из старшей половины аргумента, а потом уточнить его? Прежде всего покажем, что это принципиально возможно. Действительно, представим аргумент в виде Н=Н'<<16+Н'' и результат в виде н=н'<<8+н''. Поскольку н''<256, то квадрат его заведомо будет меньше, чем квадрат числа н=н'<<8+256=(н'+1)<<8. Отсюда следует, что старшая часть результата не превосходит корня квадратного из старшей части аргумента.
Реализация данного подхода к оставляю на долю пытливого читателя.
Что нам даст подобный подход, ведь общее количество итераций останется неизменным — первую половину итераций мы можем провести с числами меньшей длины, а это приводит к уменьшению временных затрат. Данный подход может быть применен и к варианту с умножением и к разностному варианту, общий выигрыш составит до четверти общего времени исполнения.
Необходимое примечание — применимость данного подхода совершенно не очевидна, при реализации для МК типа AVR действительно имеет место ускорение выполнения, но для некоторых архитектур, например для x86, совершенно неожиданно появилось замедление работы. Видимо, работа с не-нативными данными (16 битными) в этой архитектуре существенно дороже по времени, нежели с родными (32 битными). Глубокого исследования я не проводил, но факт имел место и сообщить о нем должен во избежание недопонимания.
Но и это еще не все. Раз мы уже вступили на путь разделения и властвования, то почему бы не пойти дальше — извлекать корень из битов шаг за шагом, начиная со старших (начинать с младших в нашем случае контр-продуктивно). Схема алгоритма та же — мы добавляем в текущему результату очередную порцию битов и пробуем добавить очередной бит к результату, проверяя, не вышли ли мы за значение корня. Особенность же в том, что мы можем проверять только старшие биты аргумента, до тех пор, пока не доберемся до младших.
При реализации используем еще один трюк — вместо того, чтобы двигать наши вычитаемые числа вправо, будем двигать наш уменьшаемый аргумент влево, смысл от этого не меняется, а скорость увеличивается. Увеличивается за счет двух факторов — 1) нам достаточно проводить вычитание только 16 разрядных чисел (тут есть одна особенность, и ее надо учитывать, но мы рассматриваем учебный пример, воут) и 2) нам не потребуется сдвигать квадрат очередного бит, поскольку он всегда будет равным единице. Но за все в этом мире нужно платить и у нас появится сдвиг расширенной разности (6 байтной) влево, причем на 2 бита за такт. Смотрим псевдокод
- начальные значения -> н=0; Н1=0;
- повторять 16 раз -> (Н1, Н)<<2; Т=Н1-н-1; если (Т>0) {Н1=Т; н=н+2}; н<<1;
и оцениваем время исполнения, получая 16*(12(расширенный сдвиг)+4(вычисление раности)+1(решение)+2(присваивание)+1(увеличение)+2(сдвиг))=16*22=352 такта, пожалуй, результат близок к идеальному. При реализации данного варианта есть небольшие подводные камни, оставляю это опять таки на долю пытливого читателя (ну и достается же ему работы).
Ну а в заключение раздела, что меня сподвигнуло на написание данного поста. Есть совершенно замечательная библиотека McuCpp, за авторством Антона Чижова, в которой на основе класса loki авторства Андриеску необычайно элегантно (ну, насколько можно говорить об элегантности применительно к шаблонах на С++) реализована работа с пинами<a«github.com/KonstantinChizhov/Mcucpp» Я с большим уважением отношусь к упомянутому автору (к обоим из них) и недавно в связи с обстоятельствами, о которых скажу позже, смотрел исходники данной библиотеки и в очередной раз восхищался.
Однако, среди прочих файлов увидел template_utils.h, в котором были реализованы некоторые вспомогательные подпрограммы, и среди них целочисленный корень из 32-битового числа. То, что в ней используется простейший алгоритм последовательного приближения с умножением, не страшно, поскольку данный алгоритм не так уж и сильно проигрывает в быстродействии, а в понятности дает много очков вперед и все равно выигрывает. Но вот то, что реализован он несколько неаккуратно (с точки зрения быстродействия), мне сильно не понравилось, ведь «это могут увидеть дети». Неаккуратность заключается в представлении подбираемого числа 32 битами, ведь мы твердо знаем, что корень из 32 битового числа не выйдет за пределы 16 битов, так зачем нам делать сдвиги нулевых байтов. И это как раз тот случай, когда компилятор сам ни за что не догадается провести оптимизацию и ему следует помочь.
Очевидное преобразование функции
static inline uint32_t sqrt(uint32_t value) {
uint16_t result = 0;
uint16_t add = 0x8000;
for (uint8_t i = 16; i !=0; ++i) {
uint32_t rootGuess = result | add;
uint32_t guess = rootGuess * rootGuess;
if (value >= guess) {
result = rootGuess;
}
add >>= 1;
}
return result;
}позволяет нам сэкономить 2 такта на сдвиге бита и 2 такта на создании очередного множителя на каждом цикле, а организация цикла в указанном виде еще 4 такта (я знаю, что компилятор может сделать такую оптимизацию за нас, но почему бы не помочь ему в явном виде), что совсем неплохо за чисто косметические изменения кода, нисколько не затрагивающие его понятность.
Позднее примечание — один комментарий меня навел на мысль, что правильнее будет
for (uint_fast8_t i= ...)спасибо, Олег, за подсказку.
Вишенкой на торте является расположенная чуть ниже функция извлечения целого квадратного корня из знакового числа, которая утверждает, что √-1=65635=-1.С другой стороны, а почему бы и нет, чем этот результат хуже любого другого, не исключение же нам вызывать в МК, а целый корень квадратный из отрицательного числа не существует.
Ну и заключение о том, почему я обратился к библиотеке Антона Чижова. Натолкнул меня на это недавний пост относительно отечественной РТОС для МК под названием МАКС (МультиАгентная Когерентная Система) — смотри эпиграф к посту, которую рекламируют ее создатели, и которая портирована на МК производства фирмы Миландр. Замечание — данный пост ни в коем случае не является рекламным материалом и читателям это скоро станет ясно. Из упомянутого уже mcucpp авторы ОС использовали реализацию кольцевого буфера (нисколько не умаляя достоинств библиотеки Антона, должен заявить, что эта ее часть не является эталонной, и это еще мягкая формулировка, о чем я написал в другом посте, который все никак не выложу). Поскольку я с МК производства Миландр плотно работаю, материал меня заинтересовал и я пошел по ссылке на сайт разработчиков.
Здесь начинается очередной плач Ярославны.
Еще в прошлом году, когда впервые было объявлено о создании отечественной РТОС, я скачал с этого сайта описание программного продукта, но как то руки не дошли до изучения. По роду своей деятельности мне приходится иметь дело с отечественными компонентами (понимающему достаточно ...), поэтому иметь соответствующее ПО было бы совсем неплохо. Помня, как в прошлогоднем релизе директор фирмы расказывал о миллионах рублей, потраченных на разработку и большом коллективе, трудящимся над созданием данного программного продукта, решил посмотреть пробную версию, доступную для скачивание бесплатно, вот и делюсь результатами.
Для начала, описание за полгода уменьшилось по объему почти вдвое (с 115 до 55 страниц), и, если исчезновение приложений со скриншотами с описанием процесса запуска третьих продуктов из «Описания программы» можно только приветствовать, то не появление этих материалов (на создание которых было потрачено хоть и не очень значительное, но все таки время и деньги) в документе типа «Руководство оператора» лично у меня вызывает недоумение. Далее, в первой же фразе документа мы видим откровенное отклонение от истины, поскольку сама по себе РТОС никак не предназначена для «создания программ», почему то в предыдущей версии документа подобных высказываний авторы себе не позволяли, чувствуется влияние службы маркетинга. Также доставляет, что если раньше описание лежало в папке /docs корневой директории, и это было логично, то теперь оно спряталось в /toolchain/macs/docs, ладно, как говорили в моей юности, «каждый бесится по своему», двигаемся дальше.
Начинаю смотреть описание, поглядывая в исходный код (он любезно включен в состав пробной версии) и с недоумением обнаруживаю отсутствие каких бы то ни было драйверов периферийных устройств, адаптированных для работы с данной ОС. Сначала предположил, что это особенность триала, затем на форуме в информации от разработчиков обнаруживаю, что драйверов действительно нет, но они над этим работают. Более полугода (полугода, Карл, вообще то близко к году) от момента релиза ОС для МК, а они работают на драйверами. Естественно, или как еще говорят, разумеется, что ни о каких третьих продуктах (файловая система, сетевой стек, USB стек) не может быть и речи. Забавное представление у авторов о требованиях к разработке ПО для МК, ладно, проехали еще раз.
То есть заявленная ОС, подчеркиваемой особенностью которой является организация взаимодействия внутри многоконтроллерной системы, не имеет родных средств организации этого взаимодействия. Что же мы имеем в сухом остатке — а мы имеем управление задачами, собственно шедулер, минимальную службу времени и средства синхронизации задач и все — забавно, если не сказать больше. Ладно, будем смотреть дальше, даже в таком наборе компонент возможны интересные решения, особенно если учесть, что на одном сайте (не фирмы изготовителя) по ссылке увидел «экспертизу» исходного кода данной ОС. В этом документе было сказано, что программный продукт не использует сторонних (импортных) компонент и отличается оригинальностью, надо бы удостовериться.
Первое замечание, если для портирования на конкретную архитектуру Cortex-M0 (1986ВЕ1Т) используются оригинальные файлы фирмы ARM, включенные в комплект исходных кодов, то это сильно похоже на использование сторонних (импортных) фрагментов текста — лично мне кажется, что это именно использование, но, наверное, я не все знаю. Ну а во вторых, исходный код шедулера и связанных с ним компонент управления задачами действительно оригинален и не имеет аналогов (по крайней мере, мне таковые неизвестны), но это тот вид оригинальности, когда вспоминается фраза старой шаманки из фильма «Злой дух Ямбуя» о великом охотнике: «Уши отрезал, сварил и съел — ты бы догадался?».
Попытаюсь объясниться — в проектировании ОС вообще и в ОСРВ в частности одним из сложных является вопрос об обеспечении доступа всех процессов в системе к разделяемому ресурсу — времени исполнения процессора. Дело в том, что неправильно спроектированная система (и неудачно написанная задача) может заблокировать исполнение всех задач с меньшим приоритетом, что наверняка озадачит программиста. Речь идет не об выполнении запрещенных операций типа управления прерываниями (это тема отдельного разговора и в рамках простых МК решения просто не имеет, хотя авторы рассматриваемой ОС утверждают, что решили эту задачу путем использования MPU), а о непрерывном исполнении без входа в ожидание.
Данная проблема широко известна, можно решать ее по разному, на этот счет имеется обширная литература, как правило, используется набор очередей задач с разным приоритетом и модифицированный шедулер. Это требует определенных затрат для организации очередей с временем доступа О(1) и, например, во FREE-RTOS при попытке задать более 20 возможных уровней приоритета программист получает недоуменный вопрос компилятора, а действительно ли ему нужно столько (и даже, если на этот вопрос имеется утвердительный ответ, без модификации исходного кода столько приоритетов не получить).
Поэтому я был слегка удивлен, обнаружив, что рассматриваемая ОС позволяет иметь количество приоритетов до 60 (и даже больше). Удивление рассеялось, когда я полистал исходники. Вместо отдельных очередей задач с равными приоритетами авторы используют одну очередь (есть еще и вторая очередь заблокированных задач) готовых к исполнению задач, чем достигается экономия памяти (наверное, это было целью такого решения) за счет того, что
- операция внесения задачи в очередь становится О(n) и
- это делает применение модифицированного шедулера невозможным — по моему, дороговато за 20*(3*4)=240 байт оперативной памяти. Решение необычайно оригинальное, но, с моей точки зрения, это его единственное достоинство.
В общем, я так и не понял, за что авторы собираются брать деньги (но они еще и не решили, делать ли это, судя по форуму) и какие именно решения и особенности позволяют дать программному продукту столь звонкое имя. Особенно учитывая, какой объем софта предоставляют бесплатно многочисленные поставщики МК (конечно же, импортные). При просмотре форума фирмы в попытке найти ответ я увидел отсылки к упомянутому ранее программному продукту mcucpp (авторы МАКС якобы вдохновлялись идеями Чижова — три раза ха), в котором и обнаружил описанный выше мелкий недочет.
Вывод из данного раздела — если и остальные решения по импорто-замещению в области программных средств выполняются аналогичными способами со схожими по качеству результатами, то перспективы построения отечественных встроенных систем мне представляются весьма слабо определенными.
В заключение хотелось бы обратиться к руководству (нет, не разработчика ОС, я даже не хочу упоминать ее рядом с хорошими разработчиками) фирмы-разработчика и изготовителя упомянутого МК — Миландр. Вы делаете неплохие микроконтроллеры (врать не стану, уступающие по параметрам зарубежным аналогам, но не фатально), например, в свое время (в 2013) ВЕ1Т был чуть ли не топовым среди одноклассников, но на дворе 2019 год и за это время его многие догнали и перегнали.
Но, если у выпускаемых фирмой хороших МК нет:
- нормальной (лучше бы хорошей, но я реалист) документации (я знаю, что Вы думаете, будто бы она есть, уверяю Вас, Вы заблуждаетесь),
- недорогих версий в удобных корпусах (это у Вас есть),
- недорогих и удобных в работе (малогабаритных) отладочных плат на базе пункта 2,
- набора библиотек работы с периферией типа HAL, CMSIS (кое-что есть),
- набора исчерпывающе документированных примеров использования компонент МК,
- набора адаптированных и проверенных стеков под стандартные интерфейсы,
- адаптированных и проверенных внешних компонент (3rd part), включая ОСРВ,
- большого набора готовых примеров реализации стандартных устройств,
- выверенных пакетов адаптации под популярные среды программирования,
- своей собственной среды разработки, интегрированной с перечисленными компонентами (понимаю, что я замечтался, но может все таки ..) полностью готовой к использованию «из коробки»,
- обучающих материалов, базирующихся на вышеперечисленном, включая печатную продукцию и организацию семинаров разного уровня (у Вас МИЭТ под боком, конечно, MIT был бы лучше, но «других писателей у меня для Вас нет»), то сфера возможного применения данных МК несколько сужается, не правда ли (воут?).
Конечно, все это не появится само собой и стоит денег, но мне кажется, что фирма Вашего уровня могла бы себе позволить себе работу 5 человек в течении полугода для создания всего выше перечисленного (за исключением пункта, возможно, пункта 10, хотя сейчас все значимые и многие небольшие производители МК обзавелись собственной IDE). Если это будет реализовано, то исчезнет почва для появления поделок типа ОС, описываемой в данном посте.
Хотя вполне может быть, что я чего то не знаю и на самом деле все не так просто, жаль, если это действительно так.
Заранее приношу свои извинения, если мои заметки покажутся излишне резкими, именно Вас (Миландр) я не хотел обидеть.
