«Случай — это псевдоним Бога, когда Он не хочет подписываться своим собственным именем.» А. Франс

Пример взаимодействующих автоматов — различия между версиями

Материал из Wiki
Перейти к: навигация, поиск
м
м (→‎NEW)
 
(не показаны 22 промежуточные версии 1 участника)
Строка 1: Строка 1:
 
<graphviz>
 
<graphviz>
 
digraph G {
 
digraph G {
 +
 +
RST  [shape=none label=""]
 +
 
Free -> Wait [label="req = 1"]
 
Free -> Wait [label="req = 1"]
−
Free -> Free  
+
Free -> Free [label="req = 0"]
−
Wait -> Work [label="cal_ready = 1"]
+
Wait -> Work [label="cal_ready = 0"]
−
Wait -> Wait  
+
Wait -> Wait [label="cal_ready = 1"]
−
Work -> Free [label="cal_ready = 0"]
+
Work -> Free [label="cal_ready = 1"]
−
Work -> Work  
+
Work -> Work [label="cal_ready = 0"]
 +
RST -> Free [label="reset"]
  
−
Wait [label="Wait: 01\n cal_req <= '1'\n ready <= '0'"]
+
Wait [label="Thread[0|1]Wait: 01\n cal_req <= '1'\n ready <= '0'" ]
−
Work [label="Work: 10\n cal_req <= '1'\n ready <= '0'"]
+
Work [label="Thread[0|1]Work: 10\n cal_req <= '1'\n ready <= '0'"]
−
Free [label="Free: 00\n cal_req <= '0'\n ready <= '1'"]
+
Free [label="Thread[0|1]Free: 00\n cal_req <= '0'\n ready <= '1'" style=bold]
  
−
Cal_Work3 [label="CalWork: 1000\n cal_ready = 01|10"]
+
Cal_Free [label="CalFree: 0001\n cal_ready = 11" style=bold]
−
Cal_Work2 [label="CalWork: 0100\n cal_ready = 01|10"]
+
Cal_RST [shape=none label=""]
−
Cal_Work1 [label="CalWork: 0010\n cal_ready = 01|10"]
+
Cal_Work3 [label="CalWork_3: 1000\n cal_ready = 01|10"]
−
Cal_Free [label="CalFree: 0001\n cal_ready = 11"]
+
Cal_Work2 [label="CalWork_2: 0100\n cal_ready = 01|10"]
 +
Cal_Work1 [label="CalWork_1: 0010\n cal_ready = 01|10"]
  
−
Cal_Free -> Cal_Work1 [label="cal_req = 01|10|11"]
+
Cal_RST -> Cal_Free [label="reset"]
 +
 
 +
Cal_Free -> Cal_Work1 [label="cal_req = 01|10|11\nlast_thread = 0|1"]
 
Cal_Work1 -> Cal_Work2
 
Cal_Work1 -> Cal_Work2
 
Cal_Work2 -> Cal_Work3
 
Cal_Work2 -> Cal_Work3
−
Cal_Work3 -> Cal_Free  
+
Cal_Work3 -> Cal_Free [label="cal_req = 00"]
−
Cal_Free -> Cal_Free  
+
Cal_Free -> Cal_Free [label="cal_req = 00"]
 +
Cal_Work3 -> Cal_Work1 [label="cal_req = 11\nlast_thread = 0|1"]
 +
 
 +
last_thread_RST [shape=none label=""]
 +
last_thread1 [label="last_thread: 1" style=bold]
 +
last_thread0 [label="last_thread: 0"]
 +
 
 +
 
 +
last_thread_RST -> last_thread1 [label="reset"]
 +
 
 +
last_thread0 -> last_thread0 [label="cal_req = 01|00"]
 +
last_thread0 -> last_thread1 [label="cal_req = 11"]
 +
last_thread1 -> last_thread0 [label="cal_req = 11"]
 +
last_thread1 -> last_thread1  [label="cal_req = 10|00"]
 +
 
 
}
 
}
 
</graphviz>
 
</graphviz>
 +
 +
== Расширенный вариант графа переходов ==
 +
 +
<graphviz>
 +
digraph G {
 +
ratio = "auto" ;
 +
Cal_Free [label="CalFree: 0001\n cal_ready = 11\n last_thread = 1|0" style=bold]
 +
Cal_RST [shape=none label=""]
 +
{ rank=same
 +
Cal_Work11 [label="CalWork_11: 0010\n cal_ready = 10\n last_thread = 0"]
 +
Cal_Work12 [label="CalWork_12: 0010\n cal_ready = 01\n last_thread = 1"]
 +
}
 +
Cal_Work2 [label="CalWork_2: 0100\n cal_ready = 01|10\n last_thread = 1|0"]
 +
Cal_Work3 [label="CalWork_3: 1000\n cal_ready = 01|10\n last_thread = 1|0"]
 +
 +
Cal_RST -> Cal_Free [label="reset"]
 +
 +
Cal_Free -> Cal_Work11 [label="cal_req = 11\nlast_thread = 1"]
 +
Cal_Free -> Cal_Work12 [label="cal_req = 11\nlast_thread = 0"]
 +
Cal_Free -> Cal_Work12 [label="cal_req = 10\nlast_thread = 0|1"]
 +
Cal_Free -> Cal_Work11 [label="cal_req = 01\nlast_thread = 0|1"]
 +
 +
Cal_Work11 -> Cal_Work2
 +
Cal_Work12 -> Cal_Work2
 +
 +
Cal_Work2 -> Cal_Work3
 +
 +
Cal_Work3 -> Cal_Free [label="cal_req = 00"]
 +
Cal_Free -> Cal_Free [label="cal_req = 00"]
 +
Cal_Work3 -> Cal_Work12 [label="cal_req = 11\nlast_thread = 0"]
 +
Cal_Work3 -> Cal_Work11 [label="cal_req = 11\nlast_thread = 1"]
 +
 +
last_thread_RST [shape=none label=""]
 +
last_thread1 [label="last_thread: 1" style=bold]
 +
last_thread0 [label="last_thread: 0"]
 +
 +
last_thread_RST -> last_thread1 [label="reset"]
 +
 +
last_thread0 -> last_thread0 [label="cal_req = 01|00"]
 +
last_thread0 -> last_thread1 [label="cal_req = 11"]
 +
last_thread1 -> last_thread0 [label="cal_req = 11"]
 +
last_thread1 -> last_thread1  [label="cal_req = 10|00"]
 +
 +
}
 +
</graphviz>
 +
 +
== Очень Расширенный вариант графа переходов ==
 +
 +
<graphviz>
 +
digraph G {
 +
ratio = "auto" ;
 +
Cal_Free [label="CalFree: 0001\n cal_ready = 11\n last_thread = 1|0" style=bold]
 +
Cal_RST [shape=none label=""]
 +
{ rank=same
 +
Cal_Work11 [label="CalWork_11: 0010\n cal_ready = 10\n last_thread = 0"]
 +
Cal_Work12 [label="CalWork_12: 0010\n cal_ready = 01\n last_thread = 1"]
 +
}
 +
{ rank=same
 +
Cal_Work21 [label="CalWork_21: 0100\n cal_ready = 01\n last_thread = 1"]
 +
Cal_Work22 [label="CalWork_22: 0100\n cal_ready = 10\n last_thread = 0"]
 +
}
 +
{ rank=same
 +
Cal_Work31 [label="CalWork_31: 1000\n cal_ready = 01\n last_thread = 1"]
 +
Cal_Work32 [label="CalWork_32: 1000\n cal_ready = 10\n last_thread = 0"]
 +
}
 +
Cal_RST -> Cal_Free [label="reset"]
 +
 +
Cal_Free -> Cal_Work11 [label="cal_req = 11\nlast_thread = 1"]
 +
Cal_Free -> Cal_Work12 [label="cal_req = 11\nlast_thread = 0"]
 +
Cal_Free -> Cal_Work12 [label="cal_req = 10\nlast_thread = 0|1"]
 +
Cal_Free -> Cal_Work11 [label="cal_req = 01\nlast_thread = 0|1"]
 +
 +
Cal_Work11 -> Cal_Work22
 +
Cal_Work12 -> Cal_Work21
 +
 +
Cal_Work21 -> Cal_Work31
 +
Cal_Work22 -> Cal_Work32
 +
 +
Cal_Work31 -> Cal_Free [label="cal_req = 00|10"]
 +
Cal_Work32 -> Cal_Free [label="cal_req = 00|01"]
 +
 +
Cal_Free -> Cal_Free [label="cal_req = 00"]
 +
Cal_Work32 -> Cal_Work12 [label="cal_req = 11\nlast_thread = 0"]
 +
Cal_Work31 -> Cal_Work11 [label="cal_req = 11\nlast_thread = 1"]
 +
 +
last_thread_RST [shape=none label=""]
 +
last_thread1 [label="last_thread: 1" style=bold]
 +
last_thread0 [label="last_thread: 0"]
 +
 +
last_thread_RST -> last_thread1 [label="reset"]
 +
 +
last_thread0 -> last_thread0 [label="cal_req = 01|00"]
 +
last_thread0 -> last_thread1 [label="cal_req = 11"]
 +
last_thread1 -> last_thread0 [label="cal_req = 11"]
 +
last_thread1 -> last_thread1  [label="cal_req = 10|00"]
 +
 +
}
 +
</graphviz>
 +
 +
== Pictures ==
 +
 +
<html><img src="https://docs.google.com/drawings/d/e/2PACX-1vR7fH_f2YfJ_fI3I0uqt4fh2ZQjTCV7FeFkaOcrXAnP9BGb5ZUxoQWo1wk7og2Qx24aCqdqJg8MnG5B/pub?w=583&amp;h=325"></html>
 +
 +
<html><img src="https://docs.google.com/drawings/d/e/2PACX-1vTdDmWimp7Jwyes-a-bw9NYnhEyR7Qb7OOFl5HTGrAqdvBowHSnDn1REGeE7zkKkBkdSUPf8LvWEswW/pub?w=900"></html>
 +
 +
== Граф переходов для 3 потоков ==
 +
 +
<graphviz>
 +
digraph G {
 +
ratio = "auto" ;
 +
Cal_Free [label="CalFree: 0001\n cal_ready = 111\n last_thread = 2|1|0" style=bold]
 +
Cal_RST [shape=none label=""]
 +
{ rank=same
 +
  Cal_Work11 [label="CalWork_10: 0010\n cal_ready = *10\n last_thread = 0"]
 +
  Cal_Work12 [label="CalWork_11: 0010\n cal_ready = *01\n last_thread = 1"]
 +
  Cal_Work13 [label="CalWork_12: 0010\n cal_ready = *01\n last_thread = 2"]
 +
}
 +
Cal_Work2 [label="CalWork_2: 0100\n cal_ready = 001|010|100\n last_thread = 2|1|0"]
 +
Cal_Work3 [label="CalWork_3: 1000\n cal_ready = 001|010|100\n last_thread = 2|1|0"]
 +
 +
Cal_RST -> Cal_Free [label="reset"]
 +
 +
Cal_Free -> Cal_Work11 [label="cal_req = 001\nlast_thread = 0|1|2"]
 +
Cal_Free -> Cal_Work11 [label="cal_req = 011\nlast_thread = 1"]
 +
Cal_Free -> Cal_Work11 [label="cal_req = --1\nlast_thread = 2"]
 +
 +
Cal_Free -> Cal_Work12 [label="cal_req = 010\nlast_thread = 0|1|2"]
 +
Cal_Free -> Cal_Work12 [label="cal_req = 110\nlast_thread = 2"]
 +
Cal_Free -> Cal_Work12 [label="cal_req = -1-\nlast_thread = 0"]
 +
 +
Cal_Free -> Cal_Work13 [label="cal_req = 100\nlast_thread = 0|1|2"]
 +
Cal_Free -> Cal_Work13 [label="cal_req = 101\nlast_thread = 0"]
 +
Cal_Free -> Cal_Work13 [label="cal_req = 1--\nlast_thread = 1"]
 +
 +
Cal_Work11 -> Cal_Work2
 +
Cal_Work12 -> Cal_Work2
 +
Cal_Work13 -> Cal_Work2
 +
 +
Cal_Work2 -> Cal_Work3
 +
 +
Cal_Work3 -> Cal_Free [label="cal_req = 000"]
 +
Cal_Free  -> Cal_Free [label="cal_req = 000"]
 +
Cal_Work3 -> Cal_Work12 [label="cal_req = 11?\nlast_thread = 0"]
 +
Cal_Work3 -> Cal_Work11 [label="cal_req = 11?\nlast_thread = 1"]
 +
Cal_Work3 -> Cal_Work13 [label="cal_req = 11?\nlast_thread = 2"]
 +
 +
}
 +
</graphviz>
 +
 +
=== Подграф для LastThread ===
 +
 +
<graphviz>
 +
digraph G {
 +
ratio = "auto" ;
 +
 +
last_thread_RST [shape=none label=""]
 +
last_thread2 [label="last_thread: 2" style=bold]
 +
last_thread1 [label="last_thread: 1"]
 +
last_thread0 [label="last_thread: 0"]
 +
 +
last_thread_RST -> last_thread2 [label="reset"]
 +
 +
last_thread0 -> last_thread0 [label="cal_req = 001|000"]
 +
last_thread0 -> last_thread1 [label="cal_req = -1-"]
 +
last_thread0 -> last_thread2 [label="cal_req = 10-"]
 +
 +
last_thread1 -> last_thread0 [label="cal_req = 0-1"]
 +
last_thread1 -> last_thread1  [label="cal_req = 010|000"]
 +
last_thread1 -> last_thread2  [label="cal_req = 1--"]
 +
 +
last_thread2 -> last_thread0 [label="cal_req = --1"]
 +
last_thread2 -> last_thread1 [label="cal_req = -10"]
 +
last_thread2 -> last_thread2 [label="cal_req = 100|000"]
 +
 +
}
 +
</graphviz>
 +
 +
<!-- == Описание примера взаимодействующих автоматов ==
 +
 +
Пусть имеется '''multi_fsm'''  - синхронное  цифровое устройство, состоящее из нескольких (N) автоматов (запросов) W0, W1,…, WN-1, которые хотят получить доступ к одному и тому автомату (ресурсу) cal_unit. Примером содержательной постановки является доступ к АЛУ от нескольких устройств.
 +
 +
Автоматы-запросы W<sub>J</sub> (J=0,…,N-1) не взаимодействуют друг с другом. Каждый из автоматов-запросов WJ  связан только с cal_unit. Каждый автомат-запрос имеет вход req  и выход ready.
 +
 +
<source lang="vhdl">entity fsm_multi is
 +
  generic (
 +
    THREAD_NUMBER : natural := 2;
 +
    REPLY_DELAY  : natural := 3;
 +
    BUS_WIDTH    : natural := 8);
 +
  port (
 +
    req  : in  std_logic_vector(THREAD_NUMBER-1 downto 0);
 +
    ready : out std_logic_vector(THREAD_NUMBER-1 downto 0);
 +
    clk  : in  std_logic;
 +
    rst  : in  std_logic);
 +
 +
end fsm_multi;</source>
 +
 +
Будем рассматривать два автомата-запроса W0, W1.
 +
 +
Поведение multi_fsm следующее.
 +
 +
На вход req  автомата-запроса WJ поступает сигнал (1) о том, что данный автомат хочет занять ресурс. Если ресурс свободен, то автомат WJ  занимает ресурс. Ресурс обрабатывает любой из запросов 3 такта. В этих трех тактах другой автомат-запрос, ждет обработки своего запроса. Если ресурс обработал запрос от одного автомата, то он обрабатывает запрос другого автомата если такой имеется. В начале обработки запрос W0 имеет приоритет – обрабатывается первым, если выставлены два запроса.
 +
 +
Порядок обработки запросов для более, чем 2 автомата ?
 +
 +
Ограничение на подачу запросов. Для любого из каналов запроса: запрос может повториться через 4 ( и более тактов). С каждым из запросов могут быть связаны соответствующие операнды, которые должен обработать ресурс. Следующий запрос не должен повториться, пока не будет обработан поступивший запрос. Таким образом, подача запросов во времени должна быть «осмысленной».
 +
Вся цифровая система представляет собой три взаимодействующих конечных автомата. При этом ресурс представляет собой иерархический автомат. В каждом из его внутренних состояний происходит проверка состояния – а именно, какой из автоматов-запросов занимает ресурс.-->
 +
 +
== Описание ПРАЛУ ==
 +
 +
<source lang="text">TITLE fsm_multi
 +
FORMAT  PRL
 +
AUTHOR Bibilo
 +
DATE 18/01/05
 +
PROJECT LOCON_VHDL
 +
DCL_PIN
 +
EXT
 +
INP
 +
req0 req1 req2
 +
OUT
 +
ready0 ready1 ready2
 +
INTER
 +
cal_req0 cal_req1 cal_req2
 +
cal_ready0 cal_ready1 cal_ready2
 +
last_thread
 +
END_PIN
 +
BLOCK pott1main
 +
 +
1: >
 +
    ready0 *  ready1 * ready2
 +
   
 +
  > Thread0_00.Thread1_00.Thread2_00.CU_0001.last_thread1
 +
 +
Thread0_00: -req0          >  ^ready0 > Thread0_01
 +
Thread0_01: -^cal_ready0    >  ^ready0 > Thread0_10
 +
Thread0_10: -cal_ready0    >  ready0 > Thread0_00
 +
 +
Thread1_00: -req1          >  cal_req1 * ^ready1 > Thread1_01
 +
Thread1_01: -^cal_ready1    >  cal_req1 * ^ready1 > Thread1_10
 +
Thread1_10: -cal_ready1    > ^cal_req1 *  ready1 > Thread1_00
 +
 +
Thread2_00: - req2          >  cal_req2 * ^ready2 > Thread2_01
 +
Thread2_01: -^cal_ready2    >  cal_req2 * ^ready2 > Thread2_10
 +
Thread2_10: - cal_ready2    > ^cal_req2 *  ready2 > Thread2_00
 +
 +
Thread0_01.Thread1_00.Thread2_00 : - > > Thread0_10.Thread1_00.Thread2_00.CU_0010
 +
last_thread1.Thread0_01.Thread1_01.Thread2_00 : - > > Thread0_10.Thread1_00.Thread2_00.CU_0010
 +
last_thread2.Thread0_01 : - > > Thread0_10.Thread1_00.Thread2_00.CU_0010
 +
 +
Thread0_00.Thread1_01.Thread2_00 : - > > Thread0_00.Thread1_01.Thread2_00.CU_0010
 +
last_thread2.Thread0_00.Thread1_01.Thread2_01 : - > > Thread0_00.Thread1_01.Thread2_00.CU_0010
 +
last_thread0.Thread1_01 : - > > Thread0_00.Thread1_01.Thread2_00.CU_0010
 +
 +
 +
Thread0_00.Thread1_00.Thread2_01 : - > > Thread0_00.Thread1_00.Thread2_01.CU_0010
 +
last_thread0.Thread0_01.Thread1_00.Thread2_01 : - > > Thread0_00.Thread1_00.Thread2_01.CU_0010
 +
last_thread1.Thread2_01  : - > > Thread0_00.Thread1_00.Thread2_01.CU_0010
 +
 
 +
CU_0001: -
 +
Thread0_00 * ^cal_req1 * ^cal_req2 +
 +
last_thread=1 * cal_req0 * cal_req1 * ^cal_req2 +
 +
          last_thread=2 * cal_req0
 +
              > ^cal_ready0 *  cal_ready1 *  cal_ready2 > CU_0010
 +
- ^cal_req0 * cal_req1 * ^cal_req2 +
 +
          last_thread=2 * ^cal_req0 * cal_req1 * cal_req2 +
 +
          last_thread=0 * cal_req1         
 +
            >  cal_ready0 * ^cal_ready1 *  cal_ready2 > CU_0010
 +
        - ^cal_req0 * ^cal_req1 * cal_req2 +
 +
          last_thread=0 * cal_req0 * ^cal_req1 * cal_req2 +
 +
          last_thread=1 * cal_req2
 +
            >  cal_ready0 *  cal_ready1 * ^cal_ready2 > CU_0010
 +
CU_0010: CU_0100
 +
CU_0100: CU_1000
 +
CU_1000: - ^cal_req0 * ^cal_req1 * ^cal_req2
 +
            > cal_ready0 *  cal_ready1 * cal_ready2 > CU_0001
 +
 +
last_thread0:
 +
last_thread1:
 +
last_thread2:
 +
 +
END_BLOCK pott1main
 +
END_pott1
 +
</source>
 +
 +
== NEW ==

Текущая версия на 10:07, 12 декабря 2017

[svg]

Содержание

Расширенный вариант графа переходов

[svg]

Очень Расширенный вариант графа переходов

[svg]

Pictures

Граф переходов для 3 потоков

[svg]

Подграф для LastThread

[svg]


Описание ПРАЛУ 

TITLE fsm_multi
FORMAT  PRL
AUTHOR Bibilo
DATE 18/01/05
PROJECT LOCON_VHDL
DCL_PIN 
EXT
INP
req0 req1 req2 
OUT
ready0 ready1 ready2
INTER
cal_req0 cal_req1 cal_req2
cal_ready0 cal_ready1 cal_ready2
last_thread
END_PIN
BLOCK pott1main
 
1: > 
    ready0 *  ready1 * ready2
 
   > Thread0_00.Thread1_00.Thread2_00.CU_0001.last_thread1
 
Thread0_00: -req0           >  ^ready0 > Thread0_01
Thread0_01: -^cal_ready0    >  ^ready0 > Thread0_10
Thread0_10: -cal_ready0     >   ready0 > Thread0_00
 
Thread1_00: -req1           >  cal_req1 * ^ready1 > Thread1_01
Thread1_01: -^cal_ready1    >  cal_req1 * ^ready1 > Thread1_10
Thread1_10: -cal_ready1     > ^cal_req1 *  ready1 > Thread1_00
 
Thread2_00: - req2          >  cal_req2 * ^ready2 > Thread2_01
Thread2_01: -^cal_ready2    >  cal_req2 * ^ready2 > Thread2_10
Thread2_10: - cal_ready2    > ^cal_req2 *  ready2 > Thread2_00
 
Thread0_01.Thread1_00.Thread2_00 : - > > Thread0_10.Thread1_00.Thread2_00.CU_0010
last_thread1.Thread0_01.Thread1_01.Thread2_00 : - > > Thread0_10.Thread1_00.Thread2_00.CU_0010
last_thread2.Thread0_01 : - > > Thread0_10.Thread1_00.Thread2_00.CU_0010
 
Thread0_00.Thread1_01.Thread2_00 : - > > Thread0_00.Thread1_01.Thread2_00.CU_0010
last_thread2.Thread0_00.Thread1_01.Thread2_01 : - > > Thread0_00.Thread1_01.Thread2_00.CU_0010
last_thread0.Thread1_01 : - > > Thread0_00.Thread1_01.Thread2_00.CU_0010
 
 
Thread0_00.Thread1_00.Thread2_01 : - > > Thread0_00.Thread1_00.Thread2_01.CU_0010
last_thread0.Thread0_01.Thread1_00.Thread2_01 : - > > Thread0_00.Thread1_00.Thread2_01.CU_0010
last_thread1.Thread2_01  : - > > Thread0_00.Thread1_00.Thread2_01.CU_0010
 
CU_0001: - 
Thread0_00 * ^cal_req1 * ^cal_req2 +
last_thread=1 * cal_req0 * cal_req1 * ^cal_req2 +
           last_thread=2 * cal_req0
              > ^cal_ready0 *  cal_ready1 *  cal_ready2 > CU_0010
- ^cal_req0 * cal_req1 * ^cal_req2 +
           last_thread=2 * ^cal_req0 * cal_req1 * cal_req2 +
           last_thread=0 * cal_req1           
            >  cal_ready0 * ^cal_ready1 *  cal_ready2 > CU_0010
         - ^cal_req0 * ^cal_req1 * cal_req2 +
           last_thread=0 * cal_req0 * ^cal_req1 * cal_req2 +
           last_thread=1 * cal_req2 
            >  cal_ready0 *  cal_ready1 * ^cal_ready2 > CU_0010
CU_0010: CU_0100
CU_0100: CU_1000
CU_1000: - ^cal_req0 * ^cal_req1 * ^cal_req2 
            > cal_ready0 *  cal_ready1 * cal_ready2 > CU_0001
 
last_thread0:
last_thread1:
last_thread2:
 
END_BLOCK pott1main
END_pott1

NEW

Источник — «http://simhard.com/wiki/index.php?title=Пример_взаимодействующих_автоматов&oldid=5777»