|
|
|
BC/NW 2007, №1, (10) :16.2 Расширенные
табличные модели для представления временнЫх зависимостей О.В. Виноградов, А.П.
Еремеев (Москва, Московский энергетический институт (технический университет), Россия) Табличные модели принятия решений известны и широко
применяются, начиная с последней трети XX века (см. напр. [1, 2]). При этом всегда существовали
различные модификации языка таблиц решений (ТР), отличающиеся как
синтаксическими аспектами, так и семантикой принятия решения по таким моделям.
В последние годы в литературе получил распространение ещё один вид табличных
моделей, называемых хронометрированными таблицами решений (timed decision tables, ХТР).
Такие модели традиционно применяются при разработке и оптимизации
схемотехнических решений с использованием языка HDL, позволяя описывать логику функционирования
устройства в компактной форме и с учётом реальной инерционности элементов схемы
(см. [3, 4]). В описании ХТР будем следовать [3]. Каждая ХТР может
быть представлена в виде совокупности трёх таблиц: таблицы потока управления (control flow table), таблицы зависимостей (dependency table) и
таблицы задержек (delay table). Таблица потока управления представляет собой
классическую ТР, состоящую из четырёх квадрантов: указателя условий, указателя
действий, матрицы условий и матрицы действий. Эта таблица является ядром ХТР, в
ней кодируется логика принятия решений. Таблица зависимостей описывает
зависимости между действиями, содержащимися в таблице потока управления.
Входами этой таблицы могут являться символы s, ŝ, c и m, соответствующие понятиям «порядковое
предшествование» (serial predecessor), «порядковое следование» (serial successor),
«параллельное выполнение» (concurrent) и
«взаимное исключение» (mutually exclusive)
соответственно. Таблица зависимостей является квадратной, в силу необходимости
задания зависимостей между каждой парой действий. При этом из-за симметричности
понятий «параллельное выполнение» и «взаимное исключение» таблица зависимостей
является симметричной с точностью до взаимной замены символов s и ŝ. Таблица задержек применяется для
моделирования длительности выполнения действий, сопоставляя каждому действию
предполагаемую задержку, связанную с его выполнением. Покажем сводимость ХТР к общей модели ТР, приведённой
в [1]: DT = <(C, A, C', A'), B>. Четыре квадранта таблицы
потока управления непосредственно соответствуют компонентам C, A, C' и A' в
[1]. Информация из таблицы зависимостей может быть также перенесена в компонент
A' = |arj|, при условии, что входы arj задаются натуральными числами и имеют семантику
приоритета выполнения действий, а действия с равным приоритетом могут быть
выполнены параллельно. Таблицу задержек можно тогда рассматривать как одну из
формализаций компонента B, наряду с
частотными коэффициентами применимости продукций, сложностью проверки условий и
зависимостями между условиями в ТР. Литература 1.
Еремеев А.П. О корректности продукционной модели принятия решений на основе
таблиц решений // Автоматика и Телемеханика,
2001, №10, с. 78-90. 2.
Хамби Э. Программирование таблиц решений. М.: Мир, 1976, – 86 с. 3. Gupta S., Gupta R. Software
Synthesis using Timed Decision Tables. Tech. Rep. #99-01, UCI/ICS, Jan. 1999 //
http://mesl.ucsd.edu/pubs/swSynthTR99-01.pdf,
– 18 с. 4. Rath K., Li J. Synthesizing
Reconfigurable Sequential Machines Using Tabular Models // Proc. of 5th Reconfigurable
Architectures Workshop RAW-98, |