Project

General

Profile

EFSM Building (Related Work) » History » Version 37

Sergey Smolov, 03/31/2017 11:50 AM

1 1 Sergey Smolov
h1. EFSM Building (Related Work)
2
3 22 Sergey Smolov
Алгоритмы извлечения EFSM-моделей из исходного кода HDL-описаний. Все перечисленные методы строят по одному EFSM на каждый процесс целевого HDL-описания.
4 1 Sergey Smolov
5 22 Sergey Smolov
{{toc}}
6
7 17 Sergey Smolov
h2. Giomi J.-C. 1995 Finite State Machine Extraction From Hardware Description Languages
8 16 Sergey Smolov
9 25 Sergey Smolov
Алгоритм строит FSM-модели - частный случай EFSM-моделей - по HDL-описанию. Метод применим только к описаниям, которые синхронизируются единственным clock. Кроме того, все wait-выражения в исходном коде также синхронизируются единственным clock.
10 26 Sergey Smolov
Построенные FSM-модели предполагается использовать для синтеза netlist.
11 1 Sergey Smolov
12
*Шаг 1*
13 30 Sergey Smolov
HDL-описание подается на вход парсеру, который выполняет лексический и синтаксический анализ и строит _граф потока управления_ (Control Flow Graph, CFG). Выражения парсер представляет в виде ориентированных ациклических графов, внутренние вершины которых помечены операциями, а конечные вершины - переменными или значениями. Вершины CFG принадлежат к следующим типам: начало (source), конец (sink), условный оператор (switch), ветвь условного оператора (case), ожидание (wait), порождение процессов (fork), завершение процессов (join), присваивание (assignment) и цикл (loop). Вызовы функций и процедур разворачиваются при трансляции в подграфы CFG. Для loop с фиксированным числом итераций предполагается использовать процедуру _развертывания_ (unrolling).
14 22 Sergey Smolov
15
*Шаг 2*
16 34 Sergey Smolov
По CFG осуществляется поиск в ширину (bredth-first search). Фактически, в время выполнения поиска в ширину осуществляется и Шаг 3.
17 32 Sergey Smolov
Каждой вершине CFG сопоставляется синтаксическое выражение, называемое _условием активации_ (activation node). Для вершин типа wait и source оно равно 1. Для прочих вершин оно вычисляется как сумма произведений условий активации родительских (parent) вершин на условия активации исходящих из них ребер. Условие активации ребра равно 1 для всех ребер, которые НЕ исходят из вершин fork, wait, switch и source. Для ребер, исходящих из вершин типа source и fork, условия активации имеют вид равенства @ISR == val_w@, где ISR - неявная переменная состояния (Implicit State Register). Для ребра, исходящего из вершины типа fork условие активации формулируется как предикат, равный 1 для текущей ветви и 0 для всех остальных ветвей, исходящих из той же вершины. Для ребра, исходящего из вершины типа switch условие строится в виде равенства @cond == val@, где cond - условие в узле switch, val - значение в узле case. Путь в CFG называется _активируемым_ (activated path), если для каждого его ребра условие активации не принимает значение 0.
18 29 Sergey Smolov
19 1 Sergey Smolov
*Шаг 3*
20 33 Sergey Smolov
Для каждой вершины CFG вычисляется набор _выражений над данными_ (data expression) для всех переменных CFG. Выражения над данными имеют вид @de_node(v) = val(v)@, где @de_node(v)@ - обозначение для выражения для вершины @node@ и переменнной @v@, @val(v)@ - значение, определяемое типом вершины. В вершине source @val(v)@ есть начальное значение @v@, в вершине wait - предыдущее значение @v@, в assignment - выражение, присваиваемое переменной, в прочих случаях - сумма выражений над данными для указанной переменной и всех родительских вершин, умноженных на условия активации родительских вершин.
21 30 Sergey Smolov
22
*Шаг 4*
23 1 Sergey Smolov
На данном шаге выполняется оптимизация выражений над данными, построенных на предыдущем шаге. Целью оптимизации является устранение ненужных условий.
24 34 Sergey Smolov
По CFG осуществляется поиск в глубину (depth-first search).
25 1 Sergey Smolov
Для заданной вершины @n@ CFG-модели определяется множество _неявных предыдущих состояний_ (Implicit Previous State, IPS) - множество wait-вершин, которые являются ближайшими к вершины @n@ в направлении, противоположном потоку выполнения. Вершина @s@ принадлежит @IPS(n)@, если она принадлежит классу wait или source и между ней и @n@ существует хотя бы один активируемый путь, не содержащих других вершин класса wait.
26 34 Sergey Smolov
Вводится понятие _максимального множества расширенного уровня_ (Extended Level Maximal Set, ELMS). Пусть необходимо оптимизировать выражение над данными для переменной @v@ в вершине @n@. Тогда @ELMS(n.v)@ - это множество наиболее отдаленных предков вершины @n@, таких, что каждый путь от них до @n@ является активируемым и не содержит вершин wait и присваиваний @v@. В таком случае выражение над данными @de_n(v)@ можно представить в виде суммы произведений (см. Шаг 3) для всех вершин из @ELMS(n,v)@.
27
Для каждого неявного состояния, сопоставленного вершине wait, вычисляются условия на переходы и выходные значения. Так, условие на переход по wait-вершине @i@ из @IPS(w)@ в wait-вершину @w@ вычисляется как сумма произведений условий активации вершин на условия активации исходящих из них ребер, соединяющих эти вершины с @w@ для всех родительских вершин для вершины @w@. Выходное значение для переменной @v@ вычисляется как сумма произведений условий активации вершин на выражения над данными для переменной @v@ в этих вершинах, для всех вершин из множества @ELMS(w, v)@.
28 31 Sergey Smolov
29 1 Sergey Smolov
*Шаг 5* 
30
Определение начального состояния FSM. Одним из относительно простых способов является поиск кода (и состояния), который выполняется (и достигается) по reset. Сигнал reset задается пользователем.
31 34 Sergey Smolov
32
*Шаг 6*
33
Неявные переменные состояния заменяются на _явные переменные состояния_ (Explicit State Register, ESR). Для каждой пары явных состояний определяются условия на переходы и выражения над данными для выходных переменных.
34 19 Sergey Smolov
35 21 Sergey Smolov
h2. Cheng K., Krishnakumar A. 1996 Automatic generation of functional vectors using the extended finite state machine model
36 10 Sergey Smolov
37 27 Sergey Smolov
На вход алгоритму подается описание на языках VHDL или C (BESTMAP-C - см. Jou, J-Y., Rothweiler, S., Ernst, R., Sutarwala, S., and Prabhu, A. 1989. BESTMAP: Behavioral Synthesis from C. In International Workshop on Logic Synthesis (Research Triangle Park, NC, May).). Построенную EFSM-модель предполагается использовать для генерации по ней тестов.
38 4 Sergey Smolov
39
*Шаг 1*
40 8 Sergey Smolov
Промежуточное представление кода строится с помощью Bridge AT & T Behaviour Synthesis System. По синхронной части кода (synchronous section) строится _дерево операторов_ (statement tree) _T_. Листовыми вершинами дерева являются базовые блоки (последовательности присваиваний). Ветви дерева снабжены атрибутами. Атрибуты - это выражения булева типа, соответствующие ветвям условных операторов в исходном коде. Не указано, каким образом выбираются переменные состояния (state variables), однако на *Шаге 3* они считаются уже определенными.
41 5 Sergey Smolov
42
*Шаг 2*
43 7 Sergey Smolov
Строится список всех возможных комбинаций условий на входные сигналы. Условия извлекаются из дерева операторов. Извлеченные комбинации проходят процедуру _ортогонализации_, такую, что каждая исходная комбинация оказывается представимой в виде суперпозиции нескольких ортогональных условий. В результате строится множество ортогонализованных условий _I_.
44 1 Sergey Smolov
45
*Шаг 3*
46 7 Sergey Smolov
Предыдущий шаг повторяется для всех условий, содержащих переменные состояния. В результате строится множество ортогонализованных условий _C_.
47
48
*Шаг 4*
49 11 Sergey Smolov
Собственно, построение EFSM по дереву T, и множествам C и I. Данный шаг в статье написан в весьма общем виде, псевдокод отсутствует. Результатом данного шага является _граф переходов между блоками_ (block transition graph), формальное определение которого в статье не приводится.
50 7 Sergey Smolov
51
*Шаг 5*
52 1 Sergey Smolov
Стабилизация графа переходов между блоками. Алгоритм стабилизации приводится в статье с использованием псевдокода. Идея алгоритма состоит в расщеплении слишком общих условий на более частные и не пересекающиеся, что позволяет исключить недетерминированные переходы в модели (Lee, D., Yannakakis, M. 1992. Online minimization of transition systems). Однако допускаются так называемые _частично стабильные переходы_ (semi-stable transitions). В таких переходах 1) действия (update functions) имеют вид x := x + c, где c - константа, а x - переменная состояния; 2) мощность множества конечных вершин равна 2; 3) одной из конечных вершин является начальная вершина, т.е. имеется цикл. В статье показывается, что для таких вершин в процессе обхода можно вычислить количество итераций, которое потребуется, чтобы выйти из цикла. Утверждается, что это допущение сокращает потребление вычислительных ресурсов (времени и памяти), по сравнению с алгоритмом _стабилизации_.
53 10 Sergey Smolov
54 21 Sergey Smolov
h2. Guglielmo G.D., Guglielmo L.D., Fummi F., Pravadelli G. 2011 Efficient Generation of Stimuli for Functional Verification by Backjumping Across Extended FSMs
55 12 Sergey Smolov
56
Целью метода является построение EFSM-моделей, которые легко обходить (easy-to-traverse). Обход EFSM-модели является основной техникой для генерации тестов.
57 13 Sergey Smolov
58
*Шаг 1*
59
Построение "эталонной" EFSM-модели (Reference EFSM, REFSM).
60 16 Sergey Smolov
На вход алгоритму подается HDL-описание в виде _конечного автомата с потоком данных_ (FSM with Datapath, FSMD). FSMD-модель - это комбинация FSM (control path) и _конвейера данных_ (data path). Как правило, FSM-компонент осуществляет прием входных сигналов, чтение переменных состояния и формирование запроса на обработку данных. Запрос передается конвейеру, который его выполняет и возвращает результат FSM-компоненту. FSMD-модель строится методом Giomi ( Giomi J. 1995 Finite state machine extraction from hardware description languages).
61 13 Sergey Smolov
62 35 Sergey Smolov
ВАЖНО: в статье Giomi термин FSMD в явном виде не присутствует и не совсем понятно, что он делает здесь. HDL-описание, обрабатываемое методом Giomi, имеет некоторые синтаксические ограничения, но они напрямую не связаны с FSMD-представлением.
63
64 1 Sergey Smolov
*Шаг 2*
65 14 Sergey Smolov
Построение "наибольшей" EFSM-модели (Largest EFSM, LEFSM). На данном шаге выполняется преобразование переходов REFSM, содержащих условные операторы, в переходы LEFSM, не содержащие таковых. Процесс завершается построением LEFSM, количество состояний в которой является наибольшим среди всех шагов алгоритма.
66 36 Sergey Smolov
Алгоритм построения LEFSM является линейным по количеству условных операторов в коде HDL-описания. Выполняется перебор всех переходов REFSM-модели. Если переход не содержит условных операторов, он остается неизменным. Если переход содержит условные операторы, то
67
рекурсивным образом выполняется расщепление на переходы, не содержащие условных операторов. Расщепление сопровождается созданием новых символических состояний LEFSM-модели. Часть перехода, являющаяся условным оператором, расщепляется на количество переходов, равное количеству ветвей в условном операторе. Для каждого "нового" перехода создается новое конечное состояние.
68 14 Sergey Smolov
69
*Шаг 3*
70 1 Sergey Smolov
Построение "наименьшей" EFSM-модели (Smallest EFSM, SEFSM). На данном шаге выполняется группировка совместимых переходов LEFSM. Процесс завершается построением SEFSM, количество состояний в которой является наименьшим среди всех шагов алгоритма.
71 37 Sergey Smolov
Основная цель данного шага - обеспечить построение модели, которая была бы эквивалентна исходному HDL-описанию в смысле исполнения тестов. По-видимому, неявно предполагается, что за один такт EFSM-модель исполняет ровно один переход.
72 36 Sergey Smolov
Шаг 3 включает в себя следующие операции:
73
# композиция совместимых переходов;
74
# устранение несовместимости переходов;
75
76
Пусть @tij@ из состояния @Si@ в состояние @Sj@ с охранным условием @eij@ и действием @uij@, а переход @tjk@ из состояния @Sj@ в @Sk@ с охранным условием @ejk@ и действием @ujk@. Говорят, что @tij@ _совместим_ с @tjk@, если @eij@ и @ejk@ могут быть истинны одновременно, и @uij@ не содержит присваиваний переменным, используемым в @ejk@. В таком случае переход @tij@ объединяют с переходом @tjk@: последний получает охранное условие @eij AND ejk@ и действие @uij OR ujk@.
77 1 Sergey Smolov
78 37 Sergey Smolov
Если переходы @tij@ и @tjk@ не являются совместимыми, то это может произойти по двум причинам:
79
* Если их охранные условия не могут быть одновременно истинными - в случае, если переходы являются вложенными (nested, соответствуют вложенным условным операторам), то это сигнализирует об ошибке в HDL-описании; если нет, то должна проводиться композиция с другими переходами, являющимися совместимыми;
80
* Если действие перехода @tij@ определяет переменную(ые), которые используются в охранному условии @tjk@ - в таком случае предлагается модифицировать код HDL-описания таким образом, чтобы для каждой переменной @v@ её значение менялось после проверок этого значения.
81 1 Sergey Smolov
82 14 Sergey Smolov
*Шаг 4*
83 37 Sergey Smolov
Дополнительные оптимизации, приводящие к построению "полу-стабилизированной" EFSM (Semi-Stabilized EFSM, (S^2)EFSM). Оптимизация нацелена на восстановление оригинальных состояний EFSM-модели.
84
Восстановление оригинальных состояний делается методом _стабилизации_ Cheng, Krishnakumar. Стабилизация проводится по некоторым переменным (не всем), чтобы избежать комбинаторного взрыва состояний и одновременно удалить часть условий, зависящих от внутренних переменных, из охранных условий переходов. Можно предположить, что, в первую очередь, стабилизация нацеливается на такие переменные, которые используются во всех охранных условиях  и всех действиях переходов SEFSM.