Um Novo Algoritmo de Minimização de Estados
para Máquinas Assíncronas Modo-Burst
Duarte Lopes de Oliveira • Marius Strum∗∗ Wang Jiang Chau∗∗ Wagner C. Cunha••
• Departamento de Eletrônica Aplicada do Instituto Tecnológico de Aeronáutica
[email protected]
[email protected]
Praça Marechal Eduardo Gomes, 50 - CEP 12228-900 - São José dos Campos - São Paulo - Brasil
∗ Laboratório de Microeletrônica da Escola Politécnica da USP
[email protected]
[email protected]
Av. Prof. Luciano Gualberto, Trav. 3, 158 - CEP 05508-900 - São Paulo - SP - Brasil
Resumo
Diversas técnicas de síntese para máquinas assíncronas denominadas máquinas modo-burst, que
partem da especificação modo-burst, foram propostas recentemente. Nas diversas metodologias
existentes, uma importante etapa no processo de síntese é a de determinação do número de variáveis
de estado necessárias, tarefa genericamente chamada de minimização de estados. As metodologias
Uclock e G-MHM que geram respectivamente máquinas de Huffman e de Huffman modificadas,
podem levar à redução efetiva do número de estados. Os algoritmos de minimização usados nas
máquinas modo-burst partem de tabelas cujo tamanho é exponencial ao número de sinais; isto
inviabiliza estas técnicas para problemas com um grande número de sinais. Este artigo propõem um
novo algoritmo para minimização de estados que pode ser aplicado em todas as máquinas modoburst (Huffman, Huffman estendida e Huffman modificada). A grande vantagem do algoritmo
proposto é que ele representa a especificação modo-burst numa eficiente tabela de cubos que permite
manipular problemas com um grande número de sinais. O nosso algoritmo obtém os mesmos
resultados de minimização obtidos com os algoritmos de metodologias anteriores a um custo de
armazenamento menor.
Abstract
Several synthesis techniques for asynchronous machines denominated as burst-mode machines,
which start from the burst-mode specification, have been proposed recently. In such methodologies, an
important stage in the synthesis process is to determine the number of need state variables, task which
is generically called state minimization. The Uclock and G-MHM methodologies which generate,
respectively, Huffmana and modified Huffman machines, may reduce the number of states. The
minimization algorithms used for burst mode machines start from of tables whose size is exponential
to the number of signals, whats makes unfeasible to adopt these techniques for problems with great
number of signals. This article proposes a new state minimization algorithm which can be applied for
all burst-mode machines (Huffman, extended Huffman and modified Huffman machines).The great
advantage of our algorithm is that it represents the burst-mode specification in an efficient table of
cubes which allows the manipulation of problems with a great number of signals. Our algorithm
obtains the same minimization results as in previous methodologies with a reduced consumption of
storage space.
1. Introdução
Existe um renovado interesse em circuitos
assíncronos devido ao aumento do desempenho dos
sistemas digitais implementados desta forma [1].
Circuitos assíncronos apresentam várias vantagens
em relação aos circuitos síncronos: eles tendem a ser
mais rápidos e menores, dissipam menos potência,
não apresentam problemas de clock-skew e são mais
robustos contra variações de temperatura e
interações eletromagnéticas [2]. Porém não é fácil
projetar circuitos assíncronos livre de risco (hazard)
e corridas críticas [3,4].
Circuitos
assíncronos
podem
ser
classificados de acordo com o modo de comunicação
com o ambiente: 1) modo fundamental, MF, no qual
um novo sinal de entrada (um sinal por vez) é aceito
depois que o circuito inteiro estiver estável
(nenhuma atividade nas portas e linhas), 2) modo
fundamental generalizado, MFG, no qual um novo
conjunto de entradas (múltiplas mudanças de
entradas) é aceito depois que o circuito inteiro
estiver estável (nenhuma atividade nas portas e
linhas), 3) modo de Entrada/Saída, E/S, no qual um
novo sinal de entrada é aceito assim que houver uma
transição de saída e, 4) modo Entrada Burst, Saída
Burst, Eb/Ob, , no qual uma nova entrada burst é
imediatamente aceita, quando toda a saída burst for
ativada.
Circuitos assíncronos também podem ser
classificados de acordo com diferentes modelos de
atraso. Os principais são: 1) bounded gate and wire
delays, BGW, [5,13,14,15,16,17,18,19,20], 2)
unbounded gate and zero wire delays [8,9,10]
também conhecidos como circuitos speed
independent (SI) e 3) unbounded gate and wire
delays também conhecidos como circuitos delay
insensitive (DI) [6,7]. A tabela 1 mostra as
diferentes metodologias de síntese de circuitos
assíncronos para estes modos de operação e modelos
de atraso com as respectivas arquiteturas alvo. As
arquiteturas SOP + R (2R) referem-se a máquinas de
Huffman com realimentação das variáveis de estado
(estado e saída). As máquinas que operam nos
modos Eb/Sb ou MFG são denominadas máquinas
modo burst.
Nas
máquinas
das
metodologias
de
Huffman(H), UCLOCK e G-MHM, um estado é
identificado exclusivamente através de variáveis de
estado. Nas máquinas das metodologias 3D e G-3D
um estado é identificado pelo conjunto de variáveis
de saída e de estado (estas últimas podendo não
existir).
Máquinas
burst
assíncronas
são
caracterizadas pelo fato de transições de estado
poderem ser ativadas por uma ou múltiplas
mudanças de sinais de entrada [12,15,18]. Os sinais
de um burst são ativados em uma ordem e tempo
arbitrários.
Modelos
de
Atraso
Modos de Comunicação
E/S
Eb/ Sb MF
G-MHM
[14]
BGW
MFG
MH Uclock
[5] [16 ]
3D [18]
G-3D[13]
SI
DI
PET [8]
ASS [9]
SYN [10]
Martin
[6]
Arquitetura
SOP+1R
SOP+2R
Standard
C [10 ]
Macro
módulos
Tabela 1 Taxinomia das máquinas assíncronas
Nowick [15], propôs uma metodologia de
síntese (UCLOCK) que parte da especificação
modo-burst e gera máquinas de Huffman [16].
Kenneth [18,19,20], com a metodologia 3-D,
melhorou este resultado partindo da especificação
modo-burst estendida que permite descrever sinais
sensíveis a nível e sinais don’t-care direcionados,
gerando máquinas de Huffman estendidas (veja a
figura 1). Em [13,14] os autores propuseram duas
metodologias de síntese que partem de uma
especificação denominada de grafo multi-burst [12].
Esta especificação apresenta operadores burst que
permitem descrever relações entre pares de entradas
bursts. Uma metodologia (G-3D) gera máquinas de
Huffman estendidas [13], e a outra metodologia (GMHM) gera máquinas de Huffman modificadas,
MHM, [14] (veja figura 2).
Entradas
Saidas
Circuitos
Combinatórios
Estados
Figura 1 Máquinas de Huffman Estendidas
Máquinas modo burst não requerem o uso de
portas complexas e são extensamente usadas para
projetar controladores assíncronos. Entretanto tais
máquinas apresentam problemas de temporização e
de interface [11].
Nas diversas metodologias
existentes, uma importante etapa no processo de
síntese é a de determinação do número de variáveis
de estado necessárias, tarefa que, neste artigo, é
chamada genericamente de minimização de estados.
O problema de minimização de estados não se aplica
aos circuitos baseados nos modelos de atraso SI e DI
porque, nos primeiros, a especificação já determina
uma forma minimizada e, nos últimos, o processo
de síntese é realizado por tradução [7]. Portanto
estes não serão considerados mais neste artigo.
Os métodos clássicos [4] para minimização de
estados não podem ser usados para máquinas burst
assíncronas porque eles não permitem múltiplas
mudanças de entrada. A razão é que a fusão de
estados pode gerar riscos lógicos [15].
Existem diversos métodos de minimização de
estados para as máquinas burst, dentro das
metodologias de síntese apresentadas. Os algoritmos
de minimização de estados da metodologia
Uclock[16,17] partem de uma tabela primitiva de
estados, de tamanho (2Ni * Ns), onde Ni é o número
de entradas e Ns o número de estados. O algoritmo
da metodologia 3-D [18] parte dos mapas
denominados de mapas 3D, de tamanho de (2Nsinal *
Nc) onde Nsinal é o número de sinais de (entrada +
saída) e Nc o número de conflitos. Os algoritmos das
metodologias G-3D [13] e G-MHM [14] partem de
um conjunto de mapas de transição de sinais. Cada
transição de estado da especificação modo-burst,
gera um mapa de transição de sinais de tamanho
(2Nsinais-ativos), onde Nsinais-ativos é o número de sinais
de entrada [14] ou o número de sinais de (entrada +
saída) [13] que atuam na transição de estado. Na
realidade, as metodologias 3D e G-3D não tratam
da minimização de estados, cujo número permanece
inalterado - a minimização do número de mapas 3D
permite, no entanto, que o número de variáveis de
estado seja reduzido.
Todos estes algoritmos estão limitados a
aplicações que envolvem um pequeno número de
sinais, porque o tamanho das suas representações é
exponencial com o número de sinais.
Neste artigo nós apresentamos um novo
algoritmo de minimização de estados de máquinas
burst assíncronas, denominado MBG-min, para
máquinas de Huffman e MHM. Este método é
baseado na minimização de mapas, cujo tamanho é
proporcional ao número de arcos da especificação. O
nosso algoritmo parte de qualquer especificação
burst e não requer a geração da tabela primitiva de
estados ou de mapas 3D. Nosso método atua
diretamente da especificação de entrada extraindo
cubos especiais para cada transição estado,
denominados de Cubos de Transição Sinais, STC.
Este método pode ser aplicado também para as
máquinas de Huffman estendidas (3D e G-3D) para
a minimização de mapas e de número de variáveis
de estado, através de Cubos de Transição Total de
Sinais, STTC.
O nosso algoritmo usa STCs ou STTCs para
verificar a compatibilidade entre quaisquer pares de
transições de estado. O tamanho de um STC é
proporcional ao número de sinais de entrada. O
STTC é proporcional ao número de sinais de
(entrada + saída). Nosso algoritmo apresenta as
seguintes vantagens em relação aos algoritmos
propostos anteriormente: 1) minimiza máquinas que
contém um grande número de sinais; 2) o algoritmo
serve para qualquer máquina burst; 3) suporta
qualquer especificação burst (modo burst, modo
burst estendido e grafo multi-burts).
Na seção 2 descrevemos as diversas
especificações
modo-burst.
Na
seção
3
apresentamos o algoritmo de minimização de
estados para máquinas burst. Na seção 4 mostramos
exemplos de minimização. Na seção 5 comparamos
o desempenho de nosso método com os métodos
alternativos. Finalmente, apresentamos nossas
conclusões na seção 6.
Entrada
burst.
Variáveis
de estado
Circuitos
Combinatorios
Ar1
Saída
burst
Ar2
Circuitos
Combinatórios
f( Sb)= Eb and Vs
As
Figura 2 Máquina de Huffman Modificada
2. Especificações modo burst
A especificação modo-burst é representada por
um grafo na qual vértices representam estados
estáveis enquanto arcos representam transições de
estados. Um estado inicial tem que existir.
Transições podem acontecer quando uma ou
múltiplas entradas/saídas (burst) mudam o seu nível
lógico, 0 1, ou 1 0 (sinais sensíveis a transição).
Quando nenhuma mudança de entrada ocorre, a
máquina permanece em seu estado estável. Os bursts
de entrada/saída devem ser monotonica, i.e., eles só
podem mudar uma vez durante cada transição. Três
restrições devem ser obedecidas pelas especificações
modo-burst, como condição de entrada única, de
subconjunto e de consistência [15]. Kenneth propôs
a especificação modo-burst estendida, ( do inglês
extended burst-mode, EBM), que soma duas
características: sinais don’t-care direcionado (que
permite
um
sinal
de
entrada
mudar
concorrentemente com sinais de saída) e sinais
sensíveis a nível ( a decisão depende do nível do
sinal) [18,19,20].
Figure 3 ilustra uma especificação modo-burst
estendida com 4 entradas (a,b,c,d), 2 saídas (x,y) e o
estado inicial A. A notação c+ (c-) significa a
transição de subida (descida) do sinal (c). A barra
(/) é usado para delimitar cada entrada burst. A
descrição b- d- /y- na transição 6 significa que a
saída (y: 1 0) seguirá a entrada burst (b: 1 0
AND d: 1 0). O sinal sensível nível a é usado para
descrever a mútua exclusão entre as transições 2 e
3. Ele pode mudar o seu valor livremente em
qualquer transição de estado. O sinal don’t-care
direcionado b* nas transições 4 e 5 significa que b
pode mudar o seu valor ou permanecer com o seu
ultimo valor. Novas restrições na especificação
modo-burst estendida são inseridas[18].
b- / y-
c- / y+
b- d- / y-
A
6
8
D
1
G
c+ / x+
5
7
C
2
B
<a->
b+ /x-
3
<a+>
b+ /y+
E
4
b* d+ / x- y+
F
b* c- / y-
Figura 3 Especificação modo-burst estendida
A especificação grafo multi-burst (do inglês MultiBurst Graph, MBG) captura o comportamento de
um controlador assíncrono como um diagrama de
transição de estado na qual uma transição ou pode
depender de uma entrada burst (como em qualquer
máquina modo-burst) ou de um par de entradas
bursts e/ou saídas bursts. No caso posterior uma
transição é especificada por uma expressão burst
composta de um par de bursts (entradas e/ou saídas)
conectadas por um operador burst, BO. Foram
definidos quatro operadores burst em[12],
permitindo a descrição das seguintes relações: ORcausalidade, OR (?); XOR-causalidade, XOR (%);
concorrência, CO (!); e seqüência, SEQ (>). O uso
destes operadores burst permitem a descrição de
concorrência entre pares de transição de estados
[13]. Além do 4 operadores, a especificação de
MBG herda todas as características da EBM [18]. O
uso de operadores burst tem que obedecer as
seguintes regras:
• Sinais de entrada e de saída seguem uma
transição única nas expressões burst (transição
monotonica).
• estado inicial de uma expressão burst deve ser
estável.
• Os operadores OR e XOR só podem ser usados
sozinhos, enquanto os outros podem ser
combinados em cada transição estado.
• valor de um sinal sensível a nível tem que
permanecer constante durante transições
ativadas por expressões burst
• Expressões burst não devem conter sinais
don’t-care direcionado.
Figura 4 ilustra a especificação de MBG do circuito
com as entradas [a,b,c,d] saídas [x,y,] e dois
operadores OR (?,?^) e XOR (%, %^); e o estado
inicial A. As 9 transições restantes são de tipo AND.
O sinal de entrada (d) é um sinal sensível a nível e
os outros são sinais sensíveis a transição. Alguns
operadores geram super-estados (estado cheio na
figura 4). No arco 2 age o operador OR, com a
sintaxe: Ib1? Ib2 / Ob (dois burst de entrada e um
burst de saída). No arco 3 a entrada burst, Ib(d– b−
c− ), o sinal (a−) é um sinal determinante. Todos os
sinais de entrada em uma transição de estado que
contém o operador OR, deve ser ativo na transição
de estado imediatamente seguinte, ou como um sinal
de transição ou como um sinal de valor
desconhecido (equivalente ao sinal dont-care
direcionado) [12]. Um sinal em uma transição de
estado, é denominado determinante, se não é
imediatamente ativo em qualquer transição de estado
anterior. Toda a transição de estado posterior a uma
transição de estado que envolve o operador OR tem
que ter um pelo menos um sinal determinante. Um
super-estado pode ter dois (XOR) ou três (OR)
estados internos. Estes estados internos podem ser
visíveis ou não, a critério do projetista; por exemplo
na figura 4, o super-estado G é do tipo XOR visível
(G1 e G2), enquanto que o super-estado H é do tipo
XOR não visível. Os super-estados E e I são do tipo
OR visível e OR não visível respectivamente.
Sintetizar circuitos como máquinas de Huffman
operando no MFG, a partir da especificação MBG, o
seguinte conjunto de restrições deve ser satisfeito:
• Uma entrada burst Ib que ativa uma transição
que sucede outra transição de estado que foi
ativada por Ib1 ! Ib2 ou Ib1 > Ib2 têm que
obedecer
a
condição
seguinte:
(Ib1∪Ib2)∩Ib=∅. Por exemplo, na figura 5 os
sinais b e c, relacionados pelo operador
concorrência no arco 6, não são ativos no arco
7.
•
Uma entrada burst Ib que ativa uma transição
que sucede outra transição de estado que foi
ativada por Ib1 ? Ib2 ou Ib1 % Ib2 têm que
obedecer a condição seguinte: (Ib1∪Ib2)⊄Ib
Por exemplo, na figura 4 os sinais b e c,
relacionados pelo operador XOR no arco 6, e
no arco posterior 4 temos (b,c) ⊄ (a,b,c)
c- b- / y13
000200
A
1
# d+ a+ / y+
# d- a+ /x+ c+ b- /
a- b- c- /x- y3
4
I
5
2 100101
100010 7
B
b+ ? C
a- ?^
c+ /
b- a- c- / y- b+ /
x+
y+
H
6
G2
001211 11
D
12
a+ %^
G1
E2 b- / b+ /x9
E1 8 100211
10
E3
a+ /
F
c- /y+ x+
c+ % b+ / x-
Figure 4 Especificação MBG com os operadores
OR e XOR
3. Procedimento de Minimização de
Estados
O nosso algoritmo trata a minimização das
máquinas burst como a minimização de mapas, isto
é, procura o menor número de mapas de
compatibilidade que cobrem todas as transições de
estado da especificação. O tipo de máquina define
qual é o procedimento que será tomado nos passos 1
e 2 do nosso algoritmo. Estes passos correspondem a
extração dos cubos e verificar a compatibilidade das
transições de estados usando tais cubos. O nosso
algoritmo parte da especificações burst, mas como
MBG ⊃ EBM ⊃ BM, podemos dizer que o nosso
algoritmo parte do MBG.
O procedimento de minimização consiste de 5
passos :
1 Tipo de Máquina: Se a máquina é de Huffman ou
Huffman modificada, ir para 1.1. Se a máquina é de
Huffman estendida, ir para 1.2.
1.1 Gerar o STC para cada transição de estado
do MBG: Seguindo as cinco regras STC. O
conjunto de STCs é arranjado numa tabela de cubos
(ver a seção 3.1).
1.2Gerar o STTC para cada transição de estado
do MBG: Seguindo as cinco regras STTCs. O
conjunto de STTCs é arranjado numa tabela de
cubos (ver a seção 3.2).
2. Gerar a tabela de pares de arcos compatíveis
(TAC): para todo o par de transições de estado do
MBG, representado ou pelos STCs ou pelos
STTCs deve obedecer as duas condições de
compatibilidade.
3. Gerar o conjunto máximo de arcos compatíveis
(CMAC): Partindo do TAC, aplicar o algoritmo
apresentado em [13] obtemos o CMAC.
4. Gerar a cobertura mínima: Aplicando uma
variação do método Patrick [21] (no lugar do estado
temos a transição do estado), obtemos a cobertura
mínima.
5. Gerar a tabela reduzida multi-burst do MBG e
do mapa de compatibilidade. Para as máquinas
Huffman e MHM, obtemos TR_MB e para as
máquinas de Huffman estendida, obtemos
TR_MB_3D.
STCs e STTCs se diferenciam pelo fato de os
primeiros serem gerados pela análise de sinais de
entrada enquanto que os últimos são gerados através
de análise de sinais de entrada e saída. Um par de
transições de estado do MBG é compatível se a
interseção de STCs ou STTCs for vazia, i e, eles não
apresentam o mesmo código para os estados iniciais,
intermediários e finais. Se um par de STCs ou
STTCs
cobre
o
mesmo
estado,
uma
incompatibilidade existe se uma das seguintes
condições for satisfeitas:
•
•
STCs ou STTCs têm diferente valores para as
suas saídas.
A propriedade de cobertura lógica é violada
para a transição do sinal de saída 1 0 [19,20].
É importante observar que cada STC ou STTC
representa todo o possível assinalamento de código
para cada sinal de uma transição de estado, portanto
cobrindo um conjunto de estados intermediários.
Para extrairmos STCs ou STTCs um conjunto de
regras são aplicadas, onde Ib, Ib1, Ib2, Ob, Ob1 e Ob2
representam entradas e saídas burst Os sinais Sn e Id
significam respectivamente sinal sensível a nível e
sinal don’t-care direcionado. Os símbolos vd, vi e vf
significam, valores don’t-care, inicial e final,
respectivamente
3.1 Extração de STC
Os STCs são extraídos do MBG aplicando as
seguintes regras.
Regras para Cubos de Transição de Sinal STC:
1: Sem operador: Ib/Ob
STC=[Ib-vd ∪Sn-vd −[Ib-vf ∪Sn-vd∪Id-vd ]/Ob-vf]/Ob-vi.
2: Com o operador CO: Ib1/Ob1 ! Ib2/Ob2
STC=[Ib1-vd ∪Ib2-vd ] −Ts1 − Ts2]/Ob1-vi ∪Ob2-vi.
onde
Ts1={Ib1-vd ∪ Ib2-vf −[Ib1-vf ∪ Ib2-vf /Ob1-vf ∪ Ob2vf]}/ Ob1-vi ∪ Ob2-vf
Ts2={Ib1-vf ∪ Ib2-vd −[Ib1-vf ∪ Ib2-vf / Ob1-vf ∪ Ob2vf]}/ Ob1-vf ∪ Ob2-vi
3: Com o operador XOR: Ib1 % Ib2/Ob
STC={[Ib1-vd − Ib1-vf / Ob-vf]∪[ Ib2-vd −Ib2-vf/Ob-vf]}/ Ob-
STTC(5)=[220210]+[220122] e
STTC(6)=[220201]+[200002]
4. Exemplos
Ilustraremos nosso método ao grafo MBG
da figura 5 que contém o operador CO.
vi
4: Com o operador OR: Ib1 ? Ib2 /Ob
STC=[Ib1-vd∪Ib2-vd]/Ob-vi −Ts1 −Ts2
onde
Ts1=[Ib1-vd∪Ib2-vf]/Ob-vd
Ts2=[Ib1-vf ∪Ib2-vd]/Ob-vd
5: Com o operador SEQ: Ib1/Ob1> Ib2 /Ob2
STC=[Ib1-vd∪Ib2-vi]/ Ob1-vi∪Ob2-vi −Ts1−Ts2
Onde
Ts1=[Ib1-vf∪Ib2-vi]/Ob1-vf∪Ob2-vi
Ts2=[Ib2-vf∪Ib1-vi]/Ob2-vf∪Ob1-vi
Como ilustração, vamos extrair os STCs das
transições de estado de número 5 e 6 da figura 3. Os
estados F(abcdxy)=220010 e G(abcdxy)=220101:
STC(5)=[2202−2201/01]/10 e
STC(6)=[2202−2000/00]/01
(2 significa valor irrelevante (don’t-care))
3.2 Extração de STTC
Os STTCs são extraídos do MBG aplicando as
seguintes regras:
Regras para os Cubos de Transição Total de
Sinais STTC:
1: Sem operador: Ib/Ob
STTC=[Ib-vd∪Ob-vi∪Sn-vd]+[Ib-vf ∪Ob-vd∪Id-vd∪Sn-vd]
2: Com o operador CO: Ib1/Ob1 ! Ib2 /Ob2
STTC=[Ib1-vd∪Ib2-vd∪Ob1-vi∪Ob2-vi]+Ts1+Ts2+ Ts3
onde
Ts1=Ib1-vd∪Ib2-vf ∪ Ob1-vi ∪Ov2-vd
Ts2=Ib1-vf ∪Ib2-vd∪Ob1-vd ∪ Ob2-vi
Ts3=Ib1-vf ∪Ib2-vf ∪ Ob1-vd∪Ob2-vd
3: Com o operador XOR: Ib1 % Ib2/Ob
STTC=[Ib1-vd ∪ Ob-vi]+[Ib1-vf ∪Ob-vd]+
[Ib2-vd ∪ Ob-vi]+[Ib2-vf ∪Ob-vd]
4: Com o operador OR: Ib1 ? Ib2 /Ob
STTC=[Ib1-vd∪Ib2-vd∪Ob-vi]+Ts1+Ts2
onde
Ts1=Ib1-vd∪Ib2-vf ∪ Ob-vd
Ts2=Ib1-vf ∪Ib2-vd∪Ob-vd
5: Com o operador SEQ: Ib1/Ob1> Ib2 /Ob2
STTC=[Ib1-vd∪Ib2-vi∪Ob1-vi∪Ob2-vi ]+
[Ib1-vf∪Ib2-vd∪Ob1-vd∪Ob2-vd]
Como ilustração, vamos extrair os STTCs das
transições de estado de número 5 e 6 da figura 3. Os
estados F(abcdxy)=220010 e G(abcdxy)=220101:
abcdxy
d- b- /y4
1
210101
D
c- /
x-
3
011111
C
200000
A
2
d- /x- y7
d+ c+/x+
201110
5
B
#a#a+
b+ /y+
b+ /x-
100111
F
6 c- /y+ !
b- /X+
111000
E
Figure 5 Especificação MBG contendo o
operador CO
4.1 Máquinas de Huffman e MHMs
A figura 6 mostra a tabela de STCs (passo
1.1) na qual cada arco foi extraído seguindo as
regras 1 e 2. A figura 7 mostra a tabela de
compatibilidade (passo 2). Por exemplo, os cubos
relativos aos arcos 3 e 5 são:
STC(3)=[2121 – 2101/01]/11 e
STC(5)=[1211 – 1111/00]/10
A interseção das entradas é:
2121
1211
1111 Há uma interseção entre os cubos.
Como a interseção 1111 tem dois diferentes valores
de saída (11 e 00) então existe um conflito entre os
arcos 3 e 5. Na tabela de compatibilidade este
conflito é marcado com X.
Os cubos relativos aos arcos 1 e 3 são:
STC(1)=[2022 – 2011/10]/00 e
STC(3)=[2121 – 1111/00]/10
A interseção das entradas é:
2022
2121
2321
O valor 3 representa interseção vazia, o
que significa nenhum conflito entre os arcos 1 e 3.
Na tabela de compatibilidade a ausência de conflito
é marcado com V.
A figura 8 mostra o conjunto máximo de
arcos compatíveis obtido pelo algoritmo descrito em
[13], que representa o passo 3 do nosso método. A
figura 9 mostra a cobertura mínima descrita num
mapa de compatibilidade, obtida pelo método
Patrick [21] (passo 4). O passo 5 gera o
correspondente TR_MB (figura 10).
Arco
Cubo de Transição de Sinais
1
[2022 - 2011/10] / 00
2
[0211 - 0111/11] /10
3
[2121 - 2101/01] / 11
4
[2202 - 2000/00] / 01
5
[1211 - 1111/00] / 10
6
[1221 - Ts1- Ts2] /00
Ts1=[1021 - 1001/11] /10
Ts2=[1201 - 1001/11] /01
7
K
1
A
B
1
EI
EF
W
EI
EF
1
Z
2
B
3
4
5
B
6
7
2
4
D
A
5
6
7
C
3
C
D
2
3
4
5
6
E
F
7
F
A
EI
EF
[2002 - 2000/00] / 11
E
Figura 6 Tabela de cubos (STC)
Figura 9 Geração do mapa de compatibilidade
2
V
3
V
V
4
X
V
V
5
V
V
X
6
X
V
7
Aplicando neste exemplo o algoritmo de
assinalamento de estados livre de corrida [4],
verificamos a necessidade de dois sinais de estado.
X
V
X
Próx. Est. / Transição de Estado
X
X
V
V
X
V
V
1
2
3
4
5
6
Estado
Atual
[K] / d+ c+ / x+
K
[Z] / # a+ b+ / x-
Figure 7 Tabela de Compatibilidade
W
Arco
Arcos Compatíveis
Conjunto Máximo Compatível
6
5
7
(67)
7
(67) (57)
4
5
(67) (57) (45)
3
47
(67) (57) (45) (34) (37)
2
34567
(267) (257) (245) (234) (237)
1
235
(123) (125) (267) (257) (245)
(234) (237)
Figura 8 Conjunto máximo compatível
[W] / # a- b+ / y+
Z
[W / c- / x[K] / d- b- / y[Z] /c- / y+ ! b- / x+
[K] / d- / x- y-
Figura 10 Tabela reduzida multi-burst (TR_MB)
4.2 Máquinas de Huffman Estendidas
A figura 11 mostra a tabela de STTCs
(passo 1) na qual cada arco do MBG está
representado pelo seu STTC. Os cubos foram
extraídos seguindo as regras 1 e 2. A figura 12
mostra a tabela de compatibilidade (passo 2). Por
exemplo, os cubos relativos aos arcos 1 e 6 são:
STTC(1)=[202200 + 201120] e
STTC(6)=[122100 + 102120 + 120102 + 100122]
A interseção é:
202200 202200 202200 202200
122100 102120 120102 100122
102100
201120
122100
101100
102100
201120
102120
101120
100100
201120
120102
103100
100100
201120
100122
103120
A figura 13 mostra o conjunto máximo compatível
obtido no passo 3 do nosso método. A cobertura
mínima obtida no passo 4 está representada pelo
mapa de compatibilidade (veja a figura 14).
Portanto há interseções entre os cubos. Os cubos
STTC(1)=100100 e STTC(6)=100122 violam a
condição de estados com saídas diferentes, portanto
temos um conflito entre os arcos 1 e 6.
Arco
6
5
7
(67)
7
(67) (57)
Os cubos relativos aos arcos 1 e 5 são:
STTC(1)=[202200 + 201120] e
STTC(5)=[121110 + 111120]
A interseção é:
202200 202200 201120 201120
121110 111120 121110 111120
101130 131100 101110 131120
O valor 3 representa interseção vazia. O cubo
101110 é o estado estável B, o que significa que não
há conflito entre esses arcos.
4
57
(67) (457)
3
457
(67) (3457)
2
34567
(267) (23457)
1
23457
(123457) (127) (267)
Arcos Compatíveis
Conjunto Máximo Compatível
Figura 13 Conjunto máximo compatível
Arco Cubo de Transição Total de Sinais
1
K
202200 + 201120
2
021110 + 011112
3
212111 + 210121
EI
EF
W
2
B
C
2
3
C
D
3
EI
EF
4
220201 + 200002
5
121110 + 111120
6
122100 + Ts1 + Ts2 + Ts3
4
D
A
4
5
B
6
7
5
6
E
E
F
7
F
A
Figura 14 Geração do mapa de compatibilidade
Ts1=102120 Ts2=121102
No passo 5 o correspondente TR_MB_3D (figura
15) é finalmente gerado.
Ts3=101122
7
1
A
B
1
200211 + 200022
Figura 11 Tabela de cubos (STTC)
Estado
Atual
2
V
3
V
V
4
V
V
V
5
V
V
V
V
6
X
V
X
X
X
7
V
V
V
V
V
V
1
2
3
4
5
6
X Y K
Prox. Est. /Transição de Estado
[10k] /d+ c+ /x+
[11k] / # a- b+ /y+
[00w] / # a+ b+ /x[01k] /c- /x[00k] / d- b- /y-
Figura 12 Tabela de compatibilidade
X Y W
[11w] / c- / y+ ! b- / x+
[00k] / d- /x- y-
Figura 15 Tabela
TR_MB_3D.
reduzida
multi-burst
Aplicando neste exemplo o algoritmo de
assinalamento de estados livre de corrida [4],
verificamos a necessidade de apenas um sinal de
estado.
é MHM, U é a máquina da metodologia Uclock e
Nro-Est é o número inicial de estados.
Sinais
5. Discussão
Nesta seção vamos comparar o número de
variáveis de estado obtidas pelo nosso método com
os algoritmos de minimização das metodologias 3D
(A1)[18] e Uclock (A2)[16]. Nas máquinas de
Huffman estendidas (3D e G-3D), os estados são
representados pelas variáveis de saída e de estado
(estas últimas podendo não existir). Isto não é
permitido nas máquinas de Huffman (Uclock e
MHM ), onde estados
são exclusivamente
representados por variáveis de estado. Neste caso a
lógica de próximo estado é sempre maior. A
vantagem das máquinas de Huffman em relação às
máquinas de Huffman estendidas está no tempo de
ciclo [14].
5.1 Máquinas de Huffman Estendidas
O nosso algoritmo (M1) foi aplicado nos
benchmarks de [18], como mostra a tabela 2. O
nosso algoritmo obteve os mesmos resultados que o
algoritmo A1.
Pe-Rvc-Ifc
Selmerg
Alloc-outbound
Rev-Setup
Nak-Pa
Sbuf-Send-Core
Mp-Forward-Pkt
Scsi-Init-Send
Mul2
Dme-Fast
Sbuf-Send-Ctl
Biu-Fifo2-Dma
Sinais
E/S
4/4
3/2
4/3
3/2
4/5
3/2
4/4
4/2
2/2
3/3
3/3
4/2
Sinais de
Estados
M1 A1
2
2
3
3
2
2
0
0
1
1
1
1
0
0
2
2
0
0
2
2
2
2
2
2
Sinais
de
Nível
não
sim
não
não
não
sim
não
sim
não
não
não
sim
Tabela 2 Comparação do número de variáveis de
estado.
5.2 Máquinas de Huffman e MHM
O nosso algoritmo (M2) foi aplicado nos seguintes
benchmarks: pe-send-ife, dme-fast-e e chu-ad-opt
[16]. A tabela 3 mostra que o nosso método obteve
os mesmos resultados que o algoritmo A2, onde M
Minimização
Variáveis
de
Nro-Est
de Estado
Estados
E/S
pe-send-ifc 5/3
M2
11
5
A2
U
M
5
3
3
3/3
8
5
5
3
2
c h u - a d - o p t 3/3
4
2
2
1
1
dme-fast-e
Tabela 3 Comparação do número de estados e
variáveis de estado.
5.3 Análise das estruturas de especificação
Nesta seção mostraremos a eficiência da tabela
de cubos do nosso algoritmo, quando aplicado em
problemas que manipulam muitos sinais.
A tabela 4 mostra a quantidade de bytes que as 3
representações (tabela primitiva de estados, mapa
3D e a tabela de cubos) necessitam para armazenar
3 exemplos fictícios (Ex1, Ex2 e Ex3). Os três
exemplos possuem cada um 10 estados e 15
transições de estados e não há operadores. Estes
exemplos manipulam 35, 65 e 130 sinais
respectivamente. Para o exemplo Ex3, considerando
um byte para cada sinal e dois cubos para cada
transição de estado, o MBG-min necessitou de
apenas 3900 bytes para armazenar a tabela de cubos,
seja STCs ou STTCs. Para este mesmo exemplo,
adotando um byte para cada célula, o Uclock
necessitou de aproximadamente 127x1029 bytes e o
3D necessitou de aproximadamente de 136x1037
bytes. Exemplos como este mostram a total
inviabilidade dos métodos Uclock e 3D quando
envolve muitos sinais.
Exemplos
Número
de
Sinais
Número de bytes
MBG-min
Uclock
E/S
6
EX1
25/10
336x10
EX2
50/15
113x10
EX3
100/30
127x10
14
29
3D
G-3D
MHM
1050
1050
1950
1950
3900
3900
8
344x10
17
369x10
37
136x10
Tabela 4 Comparação dos tipos de representação
6. Conclusão
Neste artigo, propusemos um novo algoritmo de
minimização de estados para máquinas assíncronas
modo burst que são caracterizadas como máquinas
que permitem múltiplas mudanças de entrada. Os
métodos de minimização de estados existentes
manipulam
representações, como a tabela de
estados primitiva e o mapa 3D, que tem crescimento
exponencial.
A grande vantagem do nosso
algoritmo é a tabela de cubos, que
é uma
representação proporcional ao número de sinais e
ao número de arcos. Mostramos resumidamente a
sintaxe das especificações burst (modo-burst, modoburst estendido e grafo multi-burst). O nosso
algoritmo MBG-min suporta qualquer especificação
burst. O MBG-min se baseia em uma série de regras
para gerar a tabela de cubos. Um exemplo foi dado
para ilustrar o nosso algoritmo nos diversos tipos de
máquinas. O nosso algoritmo foi testado com alguns
benchmarks e apresentou os mesmos resultados que
os obtidos com as metodologias Uclock e o 3D.
Uma breve análise mostrou que a tabela primitiva de
estados e o mapa 3D são inviáveis para aplicações
com um grande número de sinais, e que a nossa
tabela de cubos resolve eficientemente este
problema.
Referencias
[1] S. B. Furber, “Breaking Step the Return of
Asynchronous Logic”, IEE Review, July 1993,
pp.159-162.
S.
Hauck,
“Asynchronous
Design
[2]
Methodologies: An Overview”, Proc. of the IEEE,
January 1995, Vol. 83:1 pp.69-93.
[3] S. H. Unger, “Hazards, Critical Races, and
Metastability”, IEEE Transaction on Computer, June
1995, Vol. 44:6, pp. 754-768.
[4]. S. H. Unger, “Asynchronous Sequential
Switching Circuits,” John Wiley & Sons Inc, 1969.
[5]. D. H. Huffman, “The Synthesis of Sequential
Switching Circuits,” J. Franklin Ins., Vol. .257, pp.
161-190, March 1954 and pp. 275-303, April 1954.
[6]. A. J. Martin, “Compiling Communicating
Process into Delay-Insensitive VLSI Circuits,”
Distributed Computer Vol.1, no.3, pp.226-234,
1986.
[7]. E. Brunvand and R. F. Sproull, “Translating
Concurrent Programs into Delay-Insensitive
Circuits,” Proc. ICCD, pp.262-265, 1989.
[8]. J. Cortadella, M. Kishinevsky, L. Lavagno and
A.
Yakovlev, “Petrify: a Toll for Manipulating
Concurrent Specifications and Synthesis of
Asynchronous Controllers,” IEICE Transitions on
Information on Systems, vol. E80-D, no. 3, pp. 315325, March 1997.
[9]. C. Ykman-Couvreur, B. Lin and H. de Man,
“Assassin: A Synthesis System for Asynchronous
Control Circuits,” Tech. Rep., IMEC, September
1994, User and Tutorial manual
[10]. P. Beerel, Chris J. Myers and Teresa H. Meng,
“ Covering Conditions and Algorithms for the
Synthesis of Speed-Independent Circuits,” IEEE
Transitions on CAD of Integrated Circuits and
Systems, vol. 17, no 3, March 1998.
[11]. Tam-Anh Chu, “On the Models for Designing
VLSI
Digital
Asynchronous
Systems,”
INTEGRATION, the VLSI Journal 4, pp.99-113,
1986
[12] D. L. Oliveira, M. Strum and W. C. Cunha,
“Grafo Multi-Burst: Uma Especificação para
Máquinas de Estado Assíncronas,” Proc. do VI
Workshop Iberchip, Março 2000, pp. 371-380.
[13]. D. L. Oliveira, M. Strum and W. C. Cunha,
“GMB-direto: Um Novo Método de Síntese de
Máquinas de Estado Assíncronas,”, Proc. do VI
Workshop Iberchip, Março 2000, pp. 381-390.
[14]. D. L. Oliveira, M. Strum, W. J. Chau and W.
C. Cunha, “Synthesis of Multi-Burst Controller as
Modified Huffman Machines,”, Submetido Proc.
Int. Conf. On Application of Concurrency to System
Design, ICACSD 2001, Newcastle, U.K.
[15]. S. M. Nowick, “Automatic Synthesis of BurstMode Asynchronous Controllers,” Ph.D thesis,
Stanford University, 1993.
[16]. S. M. Nowick and Bill Coates, “UCLOCK:
Automatic Design of High-performance Unclocked
State Machines, ‘ Proc. ICCD, pp. 434-441, 1994.
[17]. R. M. Fuhrer, et. al, “MINIMALIST: An
Environment for the Synthesis and Verification of
Burst-Mode Asynchronous Machines,” in Proc.
IEEE/ACM Int. Workshop Logic Synthesis , 1998
[18]. Kenneth Y. Yun, “Synthesis of Asynchronous
Controllers for Heterogeneous Systems”, Ph.D.
thesis, Stanford University, 1994.
[19]. K. Y. Yun and D. L. Dill, “Automatic
Synthesis of Extended Burst-Mode Circuits: Part I
(Specification and Hazard-Free Implementation),”
IEEE Trans. on CAD of Integrated Circuit and
Systems, Vol. 18:2, February 1999, pp. 101-117.
[20]. K. Y. Yun and D. L. Dill, “Automatic
Synthesis of Extended Burst-Mode Circuits: Part II
(Automatic Synthesis),” IEEE Trans. on CAD of
Integrated Circuit and Systems, Vol. 18:2, February
1999, pp. 118-132.
[21]. S. R. Patrick, “A direct determination of the
irredundant forms of a boolean function from the set
of prime implicants,” AFCRC-TR-56-110 Air Force
Cambridge Research Center, April 1956.