Автоматное программирование. Часть 4. Эффективность автоматно-спроектированных программ

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

    Я бы сформулировал вопрос иначе: насколько эффективны автоматно-спроектированные программы? Такая формулировка вопроса намекает, что автоматное проектирование — источник высокой эффективности программ. Я ещё практически не касался столь важной темы как эффективность, и пример «Дисплей» идеально подходит для иллюстрации эффективности автоматного проектирования. В первой статье я познакомил читателей с «лабораторной» версией этого модуля, но тестировать я буду «боевой» вариант, процесс проектирования которого я приведу в следующей статье. Исследование эффективности будет выполнено для платформ msp430 и CortexM3.

    Чтобы не быть субъективным, оценивая эффективность, нужно с чем-то сравнивать результаты. Поэтому я проведу тот же комплекс испытаний для неавтоматной реализации примера «Дисплей» любезно предоставленной michael_vostrikov, за что ему огромная благодарность и плюсы в карму.


    Оглавление.

    Предыдущая статья

    Автоматную реализацию я условно назову А1, не автоматную — A2. Оригинальная А2 написана на JavaScript, но чтобы можно было исследовать эти реализации в равных условиях я перекатал вариант A2 на С++ . С него и начнём.

    (FSM || !FSM)?


    Как и в случае с реализацией А1, вариант A2 делится на: модуль разбиения текста на блоки и модуль отображения текстовых блоков.

    image

    Рисунок 1. Крупномасштабная структура модуля «А2:: Дисплей»

    Автомат разбиения на блоки представлен функцией A2::tDisplay::Out_text. Из её анализа видно, что вариант A2, условно названный мной «неавтоматный», реализуется типичным автоматом, который описывается диаграммой состояний:

    image

    Рисунок 2. Вариант А2. Автомат разбиения текста на блоки. Диаграмма состояний

    Для того, чтобы подчеркнуть состояния в исходнике, я выделю их цветом.

    image

    Рисунок 3. Вариант А2. Автомат разбиения текста на блоки. Исходный код программы с «подцвеченными» состояниями

    Автомат A2::tDisplay::Out_text это ещё один пример реализации автоматов вдогон примерам из прошлой статьи. Имеется два явным образом выделенных состояния и переменная (esc_mode), которая определяет текущее Внутреннее состояние. То, что эта переменная имеет тип bool, нисколько не умаляет её в этом качестве.

    Рассмотрим аналогичный автомат для варианта А1, который я привожу здесь для удобства

    image

    Рисунок 4. Вариант А1. Автомат разбиения текста на блоки. Диаграмма состояний

    Исходный код.Вариант А1. Автомат разбиения текста на блоки.
    image


    Это тоже автомат, у него есть три однозначно выделенных состояния и явно прописаны переходы между ними, и хотя здесь нет специальной переменной описывающей внутреннее состояние, структура программы такова, что программный счётчик является этой переменной. Когда:

    Таблица 1. Соответствие значения программного счётчика и текущего внутреннего состояния программы

    значение программного счётчика в диапазоне

    это соответствует состоянию

    state__inside_text_block

    state__out_text_block

    режим текста

    state__out_text_block

    state__control_processing

    вывод блока

    state__control_processing

    до конца цикла

    обработка управляющей

    последовательности


    В случае A2 в роли переменной Внутреннее состояние выступает переменная тип bool, в случае A1 — программный счётчик, и тем не менее это ярко выраженные автоматно-реализованные алгоритмы. Напомню, что вариант А2 это автомат Мили. В отличии от автомата Мура (вариант А1) выходные сигналы (или действия) здесь пишутся не в овале, а над стрелкой перехода, через слеш после условия перехода.

    A2::OA.


    Продолжим анализ варианта А2:: Дисплей, перейдя к автомату вывода текстового блока. Этот автомат сильно отличается от аналогичного автомата варианта А1.

    Исходник этого автомата
    struct tFont_item{
    
            u1x Width;
      const u1x * Image;
    
    }; 
    
    union
    {
    
        u2x Data;
        u1x Array[2];
    
     }Symbol_buffer;
    
    ////////////////////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////////////////////
    void printToBuffer( int lineStartX, int lineStartY, const tFont_item * symbolInfo, int minX, int maxX)
        {
    
          u1x bytes_Width  = (symbolInfo->Width + 7) >> 3;
    
          for (int y = 0; y < Font_height; y++)
          {
    
           if(bytes_Width == 1)
          
             Symbol_buffer.Array[1] = *((u1x*)(symbolInfo->Image + bytes_Width * y));
    
           else
             
             Symbol_buffer.Data = *((u2x*)(symbolInfo->Image + bytes_Width * y));
    
            u2x bit_mask = 0x8000;
           
            for (int x = 0; x < symbolInfo->Width; x++)
            {
    
              bool bit = Symbol_buffer.Data & bit_mask;
    
              bit_mask = bit_mask >> 1;
    
              int lineX = lineStartX + x;
    
              int lineY = lineStartY + y;
    
              if (lineX >= minX && lineX <= maxX)
              {
                setPixelInBuffer(lineX, lineY, bit);
              }
    
            }//for (int x = 0; x < symbolInfo->Width; x++)
    
          }//for (int y = 0; y < Font_height; y++)
    
        };//void printToBuffer(  int lineStartX, int lineStartY, tFont_item * symbolInfo, int minX, int maxX )
    
                               
    ////////////////////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////////////////////
    ////////////////////////////////////////////////////////////////////////////////////////
    void setPixelInBuffer(int x, int y, bool bit)
        {
    
          int bitNumber = (x & 7);
          int byteNumber = x >> 3;
    
          if (bit)
          {
    
            Line_buffer[y][byteNumber] |= (0x80 >> bitNumber);
    
          }
    
        };//void setPixelInBuffer(int x, int y, bool bit)
    


    В этой реализации не производится классификация символов, поэтому работа УА для Автомата вывода текстового блока сводится к прямому вызову операционного автомата отображения символа для каждого отображаемого символа.

    image

    Рисунок 5. Автомат вывода текстового блока, управляющий автомат

    Но откуда в неавтоматной реализации операционный автомат? Несмотря на то, что реализация А2 была мной условно названа неавтоматной, в её основе тоже лежит операционный автомат. Это простейший автомат произвольного побитового переноса.

    image

    Рисунок 6. Операционный автомат примера А2

    Как было сказано ранее, операционный автомат – полуфабрикат, который может выполнять некоторое действие с любыми допустимыми параметрами. Он может быть вырожденным в комбинационную схему. Главные требования к нему: максимальная простота, максимальная эффективность. Эти требования, как будет показано, вступают в противоречие.

    С точки зрения простоты алгоритма операционный автомат произвольного побитового переноса великолепен. Он универсален, может произвести копирование любого пикселя знакогенератора в произвольный пиксель строчного буфера. Параметризация ОА в данном случае осуществляется простейшим управляющим автоматом.

    image

    Рисунок 7. Управляющий автомат вывода

    Этот пример показывает, что большинство программ с простой логикой управления – автоматно-реализованные сами по себе, неавтоматность появляется, когда происходит последовательное усложнение логики управления. Если вы не занимаетесь проектированием алгоритма как явного автомата, то, при последовательном усложнении программы, после добавления очередной фишки, очередного «костыля» может произойти «структурный переход» — автоматность реализации исчезнет и вы получите нечто типа неавтоматного примера из статей 2 и 3.

    image

    Рисунок 8. Неавтоматный алгоритм

    Итак, мы имели возможность убедиться, что реализация А2 в чистом виде автоматная, но насколько она эффективна?

    A1 vs A2


    Единственный способ сравнить эффективность рассматриваемых реализаций – провести испытания. Для тестирования я использую среду разработки IAR.

    Первый тестовый пример – строка символов во весь экран, выводится в виде бегущей справа налево строки, до тех пор, пока вся строка не исчезнет с экрана. Физический вывод эмулируется выводом данных в порт I/O, что в первом приближении соответствует действительности.
    Шрифт 6x9, дисплей 256х64. Оптимизация – максимальная по скорости.

    char Test_text[43];
    
    int main( void )
    {
      for(int i = 0; i < 42; i++)
        
        Test_text[i] = 'A' + i;
      
      Display = new tDisplay(256,64,16);
        
      for( int i = 0; i > -270 ; i-- )
      {
     
        Display->Out_text(0,0,256,64,i,0, (uchar*)Test_text);
    
      }
    
    }
    

    Если вы пишите на IAR, возможно вам будет полезно прочитать о методике измерения.
    Для измерения длительности работы (в циклах контроллера) используется симулятор IAR C-SPY. Циклы контроллера считают 2 специальных счётчика – CTIMER1 и CTIMER2. Это переменные отладчика IAR C-SPY, которые можно найти в режиме отладки на вкладке View->Register. Для того чтобы не снимать каждый результат вручную, результаты автоматически скидываются в файл с помощью макрофункций отладчика.

    Для этого, прямо в IAR редакторе я создал файл и сохранил его под именем cspy_1.mac. В файл поместил текст с макрофункциями

    __var filehandle; 
    
    ////////////////////////////////////////////////
    setup()
    {
      filehandle = __openFile("filelog1.txt", "w");
    }
    
    
    ////////////////////////////////////////////////
    clear()
    {
      #CCTIMER1 = 0;
    }
    
    
    ////////////////////////////////////////////////
    out_data()
    {
      __fmessage filehandle , #CCTIMER1, "\n";
     
      #CCTIMER1 = 0;
    }
    
    
    ////////////////////////////////////////////////
    close()
    {
      __closeFile(filehandle);
    }
    

    Это Си подобный язык, но не Си, очень простой и в справке по IAR описан довольно подробно. Затем я подключил этот файл к проекту. Для этого, я выбрал пункт Debugger через Project->Options, отметил чекбокс Use macro file и выбрал файл cspy_1.mac.

    image

    Рисунок сп.1. Подключение к проекту файла с макрофункциями

    Описанные в cspy_1.mac макрофункции подключаются к точкам останова показанным на рис. сп.2.

    image

    Рисунок сп.2. Подключение точек останова

    Для этого в интересующие позиции ставятся точки останова. Точки останова ставятся и убираются двойным щелком по серой полосе слева от текста. После того как все точки поставлены, нужно открыть вкладку View->Breakpoints

    image

    Рисунок сп.3. Настройка

    Щёлкнув правой кнопкой по интересующей точке, выбрать Edit, появляется окно Edit breakpoint

    image

    Рисунок сп.4. Настройка

    В появившемся окошке прописывается имя требуемой функции. Если прописать его в поле помеченном 1, то указанная функция будет вызвана только когда произойдёт останов. Чтобы указанная функция вызывалась, но без останова программы, её имя следует прописать в поле 2, что приведёт к вызову этой функции до останова, с целью определить нужно остановить программу или нет. Если соответствующая макрофункция вернёт 1, будет произведён останов, если функция вернёт 0 или ничего не вернёт, останова не будет. Указанная макрофункция выполнится до выполнения соответствующего выражения Си-программы в точке останова.

    Результаты исследования приведены на графике.

    image

    Рисунок 9. Результаты первого теста

    Хорошо заметно, что для варианта А2, когда строка фактически выходит за край окна вывода значительное количество циклов тратится на то, чтобы в результате ничего не показать. Возможен вариант проверки, но он ещё сильнее замедлит работу алгоритма для тех случаев, когда есть что выводить. Для варианта А1, при выходе строки за границы окна циклопотребление падает до величины порядка 3000 циклов. Такое поведение изначально встроено в саму структуру алгоритма путём выбора соответствующих состояний автомата(в следующей статье я опишу процесс автоматной разработки на примере А1), оно не требует дополнительных проверок.

    Первый пример даёт общее представление о том, как работают эти два алгоритма в режиме бегущей строки, но основное применение модуля «Дисплей» — обычный вывод текста, полностью помещающегося на экране, в любую позицию экрана. Для исследования работы модуля в основном режиме я воспользуюсь тестовым примером:

    char Test_text[32];
    
    int main( void )
    {
      
      for(int i = 0; i< 31; i++)
    
        Test_text[i] = 'A' + i;
      
      Display = new tDisplay(256,64,24);
        
      for( int j = 0; j < 31; j++)
      {
    
        for( int i = 0; i < 8; i++)
        {
     
        
           Display->Out_text(0,0,256,64,i,0, (uchar*)&Test_text[31-j]);
           
        }
    
      }
    
    }
    

    Тестовый пример выводит строки разной длины от 0 до 31 символа, шрифт 6х9. Каждая строка выводится сначала без cдвига, потом со сдвигом на 1 пиксель вправо, потом на 2 и т.д. до 8 пикселей. Это имитирует вывод текста, в разные позиции экрана (к чему чувствительны оба алгоритма).

    image

    Рисунок 10. Влияние начального сдвига окна вывода от границы байта на циклопотребление

    Полученные результаты усредняются по сдвигам, в результате получается значение, не зависящее от начального положения строки на экране.

    image

    Рисунок 11. Вывод текстовой строки шрифтом 6x9

    Как и следовало ожидать, величина циклопотребления растёт линейно с увеличением количества символов в строке. Для варианта А1 удельное циклопотребление (циклов на символ) составляет 1200 циклов на символ, для варианта A2 5913 цикла (оптимизация, напомню, максимальная по скорости).

    image

    Рисунок 12. Пояснение терминов общие накладные расходы, удельное циклопотребление и циклопотребление холостого хода

    Общие накладные расходы составляют 3431 (А1) и 16433 (А2). Стоит обратить внимание на циклопотребление холостого хода, то есть когда на вход подана строка длиной 0 символов – 118 (А1) и 13548 (А2) циклов. Такая гигантская разница связана с чисткой строчного буфера в варианте А2. При помощи дополнительной проверки исходной строки на символ ‘\0’ можно исключить чистку строчного буфера для пустой строки и свести циклопотребление холостого хода до сопоставимой с А1 величины. Я не стал этого делать намеренно, чтобы иметь хороший повод подробнее рассмотреть вопрос о строчном буфер. Работа со строчным буфером – главная составляющая больших накладных расходов. Во первых, можно исключить операцию чистки строчного буфера, если переписать функцию setPixelInBuffer

    void setPixelInBuffer(int x, int y, bool bit)
        {
    
          int bitNumber = (x & 7);
          int byteNumber = x >> 3;
    
          if (bit)
          {
            Line_buffer[y][byteNumber] |= (0x80 >> bitNumber);
          }
          else
          {
            Line_buffer[y][byteNumber] &= ~(0x80 >> bitNumber);
          }
    
        };//void setPixelInBuffer(int x, int y, bool bit)

    но в этом случае получается не ускорение, а замедление работы алгоритма примерно в 1.5 раза (для шрифта 6x9) на символ, поскольку при очистке строчного буфера, выводятся все «белые» пиксели разом, а в этом варианте каждый «белый» пиксель выводится отдельно. График рис. показывают картину, которая получится в этом случае.

    image

    Рисунок 13. Различие между реализациями с чисткой строчного буфера и без

    Вторая проблема относящаяся к строчному буферу связана не с необходимостью чистки строчного буфера, а в самом его наличии. Для дисплея 256 точек шириной и максимальной высотой шрифта 24 пикселя размер строчного буфера составляет 768 байтов. Для «маленьких» микроконтроллеров в целом и msp430 в частности характерна проблема дефицита оперативной памяти. Вариант со строчным буфером требует:

    $ (32х24)_\text{строчный буфер} + 28_\text{ сам обьект класса tDisplay} + 59 _\text{ переменные в стеке} ≈ 850 байт. $


    Это оказывается очень расточительным для микроконтроллеров с объёмом ОЗУ 2-4 кб. И это при том, что тот же самый контроллер содержит ПЗУ объёмом 60 кб и программный код модуля tDisplay занимает те же 2 кб кода – 3.2%. 3.2% для базовой функции ввода-вывода (которая уже содержит эффективную реализацию бегущей строки и виртуальных окон вывода) очень даже приемлемо, в то время как 41.5% ОЗУ на одну операцию вывода текста – серьёзные расходы. Даже если взять более солидный msp430f2616 с 4 кб ОЗУ то 20% всё равно не мало.

    Раз уж речь зашла об msp, не лишним будет сказать об энергосбережении. Это один из самых скромных по питанию микроконтроллеров, который хорошо подходит для работы в приборах, питающихся от батарейки. Обращаю внимание на, возможно, не самый очевидный аспект: многократное повышение быстродействия программы не просто ускоряет работу в целом (быстродействие бывает не всегда критично), но прямо экономит электроэнергию аккумуляторов, позволяя микроконтроллеру находится в режиме сна бόльшую часть времени, и растягивать время работы на одной зарядке многократно.

    Вариант А1 спроектирован по схеме без строчного буфера. То есть, этот модуль не только в разы быстрее, но и требует в десятки раз меньше ОЗУ. Автомат, применённый в А1, имеет две подреализации: скоростную и экономную. Экономная требует для работы всего порядка 60 байтов ОЗУ. Естественно напрашивается вопрос: вероятно вариант А1, проигрывает варианту А2 в размере кода? Действительно, при полной оптимизации по скорости (при которой, однако производится некоторая оптимизация по размеру) получаем следующую картину по характеристикам.

    Таблица 2. Сравнительные характеристики программных модулей

    пзу

    озу

    производительность

    а2

    1122

    796+58 стек

    1

    а1.скоростной

    2088

    240 + 26 стек

    4.6 – 7.9

    а1.экономный

    2490

    62 + 18 стек

    3.5 – 6


    Для сравнения, размер знакогенератора у которого определены глифы всех 256 символов, для шрифта 6x9 составляет 3344 байт.

    Проанализируем, как растёт удельное циклопотребление с увеличением размера шрифта. На рис. 14 показан график зависимости удельного циклопотребления для шрифтов 6х9, 8х16 и 16х24, на котором видно что, величина УЦ для варианта А2 пропорциональна площади, а для варианта А1 пропорциональна высоте символов. Чтобы подчеркнуть это, по оси х показана для варианта А2 площадь символов, а для А1 высота символа в линиях.


    image

    Рисунок 14. Зависимость удельного циклопотребления от размера шрифта

    Удельное циклопотребление варианта А1 (далее все цифры для скоростного) по сравнению с А2 выше в 4.9 для шрифта 6х9, в 6.4 раза для шрифта 8x16 и в 9.2 раза для 16х24, а в среднем для строки длиной 0..31 символ вариант А1 показывает большее быстродействие в 4.6 раза для шрифта 6х9, в 5.8 раз для 8x16 и в 7.9 раз для 16х24.

    Взгляд в будущее.


    Позвольте предложить к рассмотрению важный вопрос, уходящий далеко за рамки этого цикла статей. Участвующие в испытаниях модули имели максимальную оптимизацию по скорости. Хотелось бы узнать, насколько эти реализации поддаются оптимизации. На рис. 15 изображён коэффициент оптимизации (отношение неоптимизированного к оптимизированному) в зависимости от длины строки, для разных шрифтов, для обоих вариантов.

    image

    Рисунок 15. Степень оптимизации программы

    Видно, что степень «обжатия» в обоих вариантах невелика, что говорит о том, что речь не идёт о хорошей и плохой реализации, оба варианта реализованы эффективно для своей схемы, т.е. ОА+УА. Но обратите внимание, что даже обжатый в 1.4 раза вариант А2 в 5-8 раз медленней обжатого всего в 1.15 раза варианта А1. И это не удивительно, основные инструменты оптимизатора: inline вставка функций, оптимизация циклов, разворачивание коротких циклов и всё такое. Т.е. он оптимизирует стандартные структурные конструкции программирования. Но оптимизация алгоритма, как оптимизация автомата(рис.16), лежащего в основе программы, даёт существенный прирост производительности, и это лейтмотив сегодняшней статьи.

    image

    Рисунок 16. Оптимизация алгоритма путём оптимизации соответствующих автоматов

    Отсюда можно сделать далеко идущий вывод: один из путей эволюции оптимизаторов кода связан с преобразованием алгоритма в автомат, и оптимизацией полученного автомата. Однако в примере А2 настолько примитивные автоматы, что дальше их уже некуда оптимизировать. Значительная эффективность алгоритма А1 по сравнению с А2 обусловлена применением принципиально иной схемы построения его операционного автомата. Следовательно, чтобы повысить эффективность варианта А2, нужно взять для него ОА от А1, а не оптимизировать структурные конструкции варианта А2. «Автоматная» оптимизация кода, по всей видимости, будет включать:

    1. Автоматическое разбиение исходного кода на ОАисх и УАисх. Вероятнее всего это будет анализ поведения, поиск паттернов. Автомат в этом случае получается не любой, а тот который есть в базе, и который, соответственно, может быть классифицирован. Соответственно, требуется какой-то стандарт для описания поведения ОА. Замечу, что диаграмма состояний и переходов в принципе описывает как раз таки поведение, однако интуиция подсказывает, что одной диаграммы состояний и переходов будет маловато.

    image

    Рисунок 17. Получение автомата из программного кода на любом языке программирования

    Автоматическое распознавание и классификацию операционных автоматов в исходном коде реализовать сложнее, чем сгенерировать код автомата по диаграмме состояний (что, например, делает IAR visualState), поэтому можно предположить, что схемам полностью автоматической оптимизации любого исходного кода будут предшествовать такие инструменты разработки, в которых пункт 1 будет исключён и разработка будет вестись, начиная со 2 пункта.

    2. Поиск наиболее эффективного ОА из множества ОА имеющихся в базе данных будет производиться поисковой системой, возможно на основе нейросетки, обученной на автоматы. Т.е. это будет выбор наиболее подходящего решения из множества уже готовых, имеющихся в базе данных. Предполагается, что готовые решения в базе данных будут разработаны в эпоху «первоначального накопления» программистами, либо специально обученными программами, которые будут «майнить» операционные автоматы, например при помощи генетических алгоритмов.

    image

    Рисунок 18. Поиск эффективного решения

    3. Настройка управляющего автомата, соответствующего выбранному ОА. Преобразование автоматов в код.

    image

    Рисунок 19. Оптимизированная реализация

    После описанных выше действий может быть выполнена добавочная оптимизация кода (то же самое, что и сегодня называют оптимизацией).

    Сказанное подразумевает, что требуется стандарт описания операционного автомата. Описания не в смысле его логической схемы (VHDL), потому что он и так хранится в виде кода, а в смысле набора метаинформации о том, что он умеет делать и о границах его применимости (описание поведения), метаинформации, делающей возможным автоматизированный поиск автомата-партнёра, например то, с какими УА может стыковаться этот ОА. Диаграмма состояний и переходов, несомненно, один из элементов такого описания.

    Как было сказано выше, подразумевается некая библиотека стандартных, ранее разработанных ОА, классифицированных по семействам и снабжённых упомянутым описанием. Операционные автоматы в этой библиотеке будут в готовом виде, например, на Си или на ассемблере. Каждому ОА будет соответствовать подходящий управляющий автомат, который будет храниться в виде диаграммы состояний.

    Такая схема (т.е. ОА в виде кода и УА в виде диаграммы) предпочтительна потому, что операционный автомат – высокоэффективное решение, заточенное под определённую задачу и платформу. С другой стороны, характеристики этого ОА могут варьироваться при помощи внешних параметров (в строго оговорённых для него пределах), которые задаются как раз таки управляющим автоматом.

    Управляющий автомат по своей сути это модель, описывающая работу петли обратной связи. Схемотехники хорошо знают, задавая определённую обратную связь в усилителе можно добиться изменения параметров, не вмешиваясь в конструкцию самого усиливающего элемента. Аналогично и с автоматами, регулируя УА — обратную связь операционного автомата (в строго оговорённых для каждого ОА пределах), можно добиться изменения свойств автомата в целом, не меняя его операционную часть.

    Соответственно, управляющий автомат хранящийся в библиотеке, это ещё не готовый модуль, он может настраиваться для получения требуемого поведения, и один тип УА подходит разным модификациям ОА, подобно тому, как цепочка обратной связи из соответственно соединённых резистора и конденсатора делает из операционного усилителя интегратор вне зависимости от разброса характеристик операционника. Учитывая это, лучше хранить УА в виде диаграмм состояний и генерировать по ним код в момент сборки результирующего автомата.

    Семейства автоматов буду представлять собой нечто подобное:

    image

    Рисунок 20. Семейства автоматов

    Семейству близкородственных ОА соответствует семейство УА партнёров с разными параметрами. При этом не обязательно, что каждому ОА семейства подойдёт любой УА.

    Рассказанное является достаточно прагматическим, поскольку указывает конструктивные пути эволюции средств разработки ПО. Я перечислил перспективы разной степени удалённости. Одни из них могут быть воплощены уже практически завтра, другие в отдалённом будущем. К сказанному остаётся добавить, что разработка собственно операционного автомата это некая разновидность профессионального мастерства, однако, в ней нет ничего сложного. Есть некий ход рассуждений, который я попытаюсь привести, позволяющий производить разработку эффективных автоматов. Поскольку эта часть уже достигла солидного объёма, продолжим разговор о проектировании ОА в следующей части, а напоследок рассмотрим работу тех же алгоритмов на платформе CortexM3

    CortexM3


    Как и следовало ожидать, скомпилированные под эту платформу примеры показывают более высокое быстродействие. В скобках указано сокращение соответствующей величины по сравнению с платформой msp 430.

    Таблица 3. Итоговое сравнение характеристик

    6х9

    8х16

    16х24

    общие накладные расходы

    удельное циклопотребление

    общие накладные расходы

    удельное циклопотребление

    общие накладные расходы

    удельное циклопотребление

    msp430.a1

    3431

    1202

    6122

    2299

    7764

    4052

    msp430.a2

    15938

    5716

    28910

    14318

    42402

    35748

    cortex m3.a1

    1831(1.9)

    715(1.7)

    3237(1.9)

    1370 (1.7)

    4795(1.6)

    2238(1.8)

    cortexm3.a2

    6182(2.6)

    2131(2.7)

    11347 (2.5)

    5236(2.7)

    16440(2.6)

    13282(2.7)



    Вкратце прокомментирую результаты. Ускорение работы алгоритма связано с более эффективным выполнением инструкций ядром Cortex M3. Большинство инструкций выполняются за 1-2 цикла, в то время как ядро msp430 выполняет инструкции (кроме регистр-регистр) за 2-3 цикла. Вторая причина высокого быстродействия – более эффективная работа операций сдвига. Cortex M3 способен сдвигать слово шириной 32 бита на величину до 32х позиций за раз, в то время, в то время как msp430 выполняет сдвиг 16 бит на 1 позицию за раз.

    При этом размер кода оказывается даже ниже чем соответствующий размер кода для msp430: 1043 против 1122 байт вариант А2 и 1914 против 2088 байт вариант А1.скоростной. Экономия 200 байтов ОЗУ для этого типа контроллеров неактуальна, поэтому вариант А1.экономный не рассматривается.

    Эта статья завершает вводный цикл – первоначальное ознакомление с аспектами автоматного программирования. Следующая статья — практикум. На примере разработки дисплея А1 я постараюсь наглядно продемонстрирую автоматный стиль мышления, в процессе автоматной разработки.

    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 11
    • 0
      «но чтобы можно было исследовать эти реализации в равных условиях я перекатал вариант A2 на С. „
      Выглядит как С++, а не С.
      • 0
        верно. На самом деле минимум ООП максимум обычного С. Это же для микроконтроллеров, а там С предпочтительней. но чтобы не вводить в заблуждение поправил
      • 0

        Было бы неплохо данные автоматы промоделировать в Stateflow и сгенерить из них Си-код. Я уверен, что там можно получить код и пооптимизированей.

        • 0
          Я уверен, что там можно получить код и пооптимизированей.

          но на чём основана эта уверенность? было бы неплохо хотя бы общие соображения.
          • 0

            Основана на использовании.
            Из общих соображений — генератор кода не ограничен какими либо парадигмами программирования, как программист. Например, читаемостью кода. Поэтому он может не меняя исходного представления автомата состояния, его читаемости и функционирования провести множество оптимизаций. Как примеры:


            • Заменить if, then, else — switch case и наоборот, где это приведет к уменьшению размера кода или изменению его эффективности
            • Убрать из кода состояния и переходы, которые не могут произойти по определению. Компилятор на такое не способен.
            • Убрать условия, которые не будут проверяться или всегда истинны/ложны
            • Заменить простые автоматы состояний, функции и переходы таблицами истинности.
            • Применить, в зависимости от заданных критериев, inline функции — т.е. заменить вызов функции ее полным кодом или наоборот. Применить макросы, где это эффективно.
            • выбрать соответствующие типы переменных, которые наилучшим образом отвечают критериям оптимизации для конкретной процессорной архитектуры (т.к x86, ARM, TMS320 и 8051 немного по-разному переваривают char, unsigned long и пр.)
            • развернуть или нет циклы for в зависимости от критериев.
            • и кучу других оптимизаций
            • 0
              Например, читаемостью кода.

              Читаемость кода как таковая не влияет на быстродействие — оптимизируется не исходный код, а программные структуры.
              — Если вы читали внимательно, на рис 15 я показал насколько алгоритмы поддаются всему, что вы описали. коэффициент оптимизации получился 1.15, то есть, проделав все описанные вами пункты, оптимизатор смог улучшить результат всего на 15%.
              — я embedder с большим стажем, и долгое время писал проги, и обязательно изучал во что они превращаются после компиляции. Я как супернейросетка выработал такое профессиональное чутьё, что можете положиться на моё слово — я могу построить по диаграмме состояний на самом деле высокоэффективный код, при этом вполне осознавая, какой исполняемый код получится. Это не хвастовство, я просто хочу сказать, что вы можете вполне доверять тому что я пишу
              • 0
                — Если вы читали внимательно, на рис 15 я показал насколько алгоритмы поддаются всему, что вы описали. коэффициент оптимизации получился 1.15, то есть, проделав все описанные вами пункты, оптимизатор смог улучшить результат всего на 15%.

                Я так понимаю, что вы использовали компиляторные оптимизации o1, o2, o3, наверное. Это немножко не то, так как применимость данных оптимизаций ограничена исходным кодом, который им вскормлен. Оптимизации, же, которые делает генератор кода, работают на один уровень выше — на этапе генерации самого кода. Поэтому тут совсем другой уровень и результат.
                Я сам применял компиляторные оптимизации и к сгенерированному коду и к ручному и говно-коду и получал те же самые 15% во всех случаях, поэтому могу констатировать, что прирост производительности благодаря им мало зависит от исходного кода.


                я embedder с большим стажем, и долгое время писал проги, и обязательно изучал во что они превращаются после компиляции. Я как супернейросетка выработал такое профессиональное чутьё, что можете положиться на моё слово — я могу построить по диаграмме состояний на самом деле высокоэффективный код, при этом вполне осознавая, какой исполняемый код получится. Это не хвастовство, я просто хочу сказать, что вы можете вполне доверять тому что я пишу

                Ничуть не пытаюсь приуменьшить вашу квалификацию. Просто по моим наблюдениям качество автоматически сгенерированного кода из автоматов на сегодня настолько высоко, что позволяет состязаться с ембеддерами с большим стажем. Причем, чтобы нарисовать такой автомат, необязательно иметь опыт ембеддерщика вообще, а достаточно иметь базовое понимание, как работают автоматы вообще.

                • 0
                  Я сам применял компиляторные оптимизации и к сгенерированному коду и к ручному и говно-коду и получал те же самые 15% во всех случаях, поэтому могу констатировать, что прирост производительности благодаря им мало зависит от исходного кода.

                  не соглашусь. В следующей статье я последовательно пишу исходник и делаю комиты по шагам. Там в первом, «лабораторном», неоптимальном варианте, оптимизация 10 кратная.
                  Это немножко не то, так как применимость данных оптимизаций ограничена исходным кодом, который им вскормлен. Оптимизации, же, которые делает генератор кода, работают на один уровень выше — на этапе генерации самого кода. Поэтому тут совсем другой уровень и результат.

                  генерил в IAR visualSTATE их простые примеры. По крайне мере там, ничего не говорит даже о приблизительной оптимальности по сравнению с ручным. Просто совершенно другой уровень. Я не делал там свой пример, но речь может идти о в десятки раз менее эффективном коде. Там сама схема реализации автомата такая, что можно не генеря давать прогнозы.
                  • 0
                    Кстати, раз уж зашла речь о генераторах кода по диаграмме, я буду благодарен если вы поделитесь со мной своим опытом по сгенереному коду, потому что я сталкивался со схемами реализации автоматов 1 и 3 из предыдущей статьи, и даже не знаю генерят ли какие-нибудь программы что-нибудь ещё
          • 0

            Ну и вообще мое ИМХО насчет эволюции разработки программных автоматов для встраиваемых систем — это графическое моделирование и автоматическая генерация кода. Рисуете Вашу блок-схему с переходами и состояниями так, как она должна работать. Моделируете с внешними воздействиями и отлаживаете у себя на компьютере. Потом нажимаете на кнопку и генерируете либо Си-код для микроконтроллера, либо VHD/Verilog для ПЛИС, если автомат должен реагировать за наносекунды. Компилируете и получаете рабочий автомат с первого раза. Если надо, выбираете галочки и оптимизируете автомат по скорости, занимаемому месту и требуемой памяти.

            • 0
              Рисуете Вашу блок-схему с переходами и состояниями так, как она должна работать.

              тут вопрос в степени детализации блок-схемы и в том руководствуясь чем, собственно, вы будете её рисовать. автоматное программирование — не столько способ реализации, потому что, как я показал в этой статье — автоматная реализация — дело нехитрое, а вопрос проектирования и я это постараюсь показать в следующем цикле — практикуме
              Ну и вообще мое ИМХО насчет эволюции разработки программных автоматов для встраиваемых систем — это графическое моделирование и автоматическая генерация кода.

              если вам будет так удобней, то пожалуйста, автоматное программирование в моём представлении весьма демократично. В предыдущей статье есть глава «Артефакты автоматной схемотехники» и там показано, что бывает удобней просто написать функцию в «естесственном» программистком стиле, она останется автоматно реализованной.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.