Anais do XVI Encontro de Iniciação Científica e Pós-Graduação do ITA – XVI ENCITA / 2010
Instituto Tecnológico de Aeronáutica, São José dos Campos, SP, Brasil, 20 de outubro de 2010
MINIMIZAÇÃO DE ESTADOS PARA MÁQUINAS DE
ESTADO FINITO ASSÍNCRONO
Rômulo Magalhães Brasil
Divisão de Eletrônica Aplicada do Instituto Tecnológico de Aeronáutica – I TA – IEEA
Praça Marechal Eduardo Gomes, 50 – CEP 12228-900 – São José dos Campos – SP – Brasil
Bolsista PIBIC-CNPq
Email: Rô[email protected]
Duarte Lopes de Oliveira
Divisão de Eletrônica Aplicada do Instituto Tecnológico de Aeronáutica – I TA – IEEA
Praça Marechal Eduardo Gomes, 50 – CEP 12228-900 – São José dos Campos – SP – Brasil
Email: [email protected]
Resumo. Projeto de sistemas digitais síncronos VLSI (Very Large Scale Integration) na tecnologia DSM (Deep-
SubMicron) que permite 109 transistores tem no sinal de relógio o seu maior problema. Uma interessante alternativa
para o projeto VLSI_DSM é o paradigma assíncrono. Eles operam por eventos, portanto não necessitam de um sinal
de relógio. Máquinas de estado finito assíncrono (MEFA) é um importante componente dos sistemas digitais
assíncronos. Uma interessante MEFA é as máquinas modo rajada estendido (MEFA_MRE) (extended burst-mode
machine). Ela é implementada na arquitetura de Huffman estendida (saída realimentada), usando a ferramenta 3D.
Uma etapa na síntese lógica das MEFA_MRE é a minimização de estados. Este artigo mostra que a álgebra das
partições pode ser usada para minimizar as MEFA_MRE, na arquitetura clássica de Huffman.
Palavras chave: lógica assíncrona, risco, especificação modo rajada, máquinas de estado finito, minimização de estados
1. Introdução
Circuitos assíncronos são circuitos seqüenciais que não necessitam de sinal externo de relógio (Clock) para
coordenar suas operações internas (Myers, 2001). Circuitos assíncronos foram usados nos primeiros computadores, e os
estudos nessa área tiveram grande crescimento na década de 60. No entanto, na década de 70 o interesse nesse circuito
caiu devido, principalmente, a popularidade dos circuitos síncronos, que precisam de um sinal de clock para gerenciar
suas atividades (McCluskey, 1986; Sparso, et al., 2001). A popularidade dos circuitos síncronos tem como principal
razão a facilidade com que os mesmos podem ser projetados, quando comparados com os circuitos assíncronos. A
única regra que os projetistas tinham de seguir era garantir a estabilidade do circuito, dado certo intervalo de tempo,
antes e depois da mudança no sinal de clock (tempos de set-up e hold).
Todavia, com a evolução da tecnologia VLSI (deep-submicron – DSM – 109 transistores), as deficiências dos
circuitos síncronos começaram a emergir. Os problemas mais importantes são defasagem de clock (clock skew),
dissipação de potência, rede de distribuição do clock e interação com o ambiente (Sparso, et al., 2001). Devido aos
problemas crescentes da síntese síncrona, em meados dos anos 80 voltou o interesse por circuitos assíncronos,
inicialmente no meio academico e posteriormente no meio industrial.
Projetistas de circuitos síncronos tinham de lidar com problemas de defasagem de clock: a diferença no instante de
chegada dos sinais de clock em várias partes do chip ou um sistema que reduz efetivamente o tempo alocado para
processos computacionais úteis. Na medida em que os chips VLSI diminuíam de tamanho, os transistores tornavam-se
mais rápidos. No entanto, a distância que os elétrons tinham de viajar para entregar os níveis do sinal de clock
permaneciam as mesmas. Mais ainda, a largura dos fios diminuía, mas o mesmo não acontecia com sua largura vertical.
Portanto os elétrons demoravam ainda mais tempo para percorrerem a mesma distância. Dessa maneira, a evolução da
tecnologia VLSI agravou ainda mais os problemas com defasagem de clock. Para minimizar esses efeitos, uma área
cada vez maior dos chips VLSI é designada para distribuição dos sinais de clock.
Além do exposto acima, com o aumento do número de transistores inseridos em um único chip, os projetistas
começaram a enfrentar reais problemas com a dissipação de potência. Em chips síncronos com sinais de clock globais,
até mesmo as partes inativas do chip dissipam calor (Sutherland, et al., 2002; Hauck, 1995).
Por fim, a maioria dos chips VLSI e, conseqüentemente, todos os sistemas digitais têm de interagir com sinais
assíncronos. É dificil imaginar dois sistemas digitais conectados por uma rede sincronizada com um clock global terem
um alto desempenho. Um chip síncrono que se comunica com um ambiente que não compartilha do mesmo sinal de
clock deve sincronizar entradas externas assíncronas com o próprio clock interno. Isso apresenta um risco inerente de
falha de sincronização. Quando circuitos digitais operavam em velocidade relativamente baixa, o risco de falha de
sincronização era extremamente baixo. No entanto, quando as freqüências dos sinais de clock chegaram na faixa de
centenas de MHz, a probabilidade de falha se tornou significativa. Isso incentivou as buscas por novas soluções.
Anais do XVI ENCITA, ITA,20 de outubro de 2010
,
1.1. Sistemas digitais assíncronos: uma alternativa
Existem vários benefícios que circuitos assíncronos trazem para o projeto de sistemas digitais. Considera-se a
necessidade de circuitos assíncronos no contexto dos sistemas (Myers, 2001; Fuhrer, 1999):
•
•
•
•
Várias interfaces de sinalização de protocolos, como a SCSI bus data transfer protocol, são assíncronas.
Projeto de controles síncronos requereria sincronização de sinais assíncronos para uma alta velocidade do
clock interno, dificultando o projeto e potencialmente prejudicando o desempenho.
Circuitos assíncronos são ideais para a construção de componentes modulares. Modularidade é uma
propriedade atrativa em qualquer sistema, pois faz com que a verificação temporal global seja desnecessária.
Circuitos assíncronos projetados para alto desempenho também funcionam quando a velocidade do sistema é
diminuída.
Circuitos assíncronos tendem a dissipar menos energia que os síncronos em algumas aplicações que utilizam
tecnologia CMOS. Circuitos assíncronos não apresentam dissipação de potência devido a transições de clock e
glitches, pois circuitos CMOS dissipam potência apenas durante as transições. Além disso, a natureza dos
circuitos assíncronos é ideal para aplicações de baixa potência que necessitam de rápidas transições entre os
estados standby e ativo, pois as partes inativas dos circuitos assíncronos estão em modo standby sem
dissipação alguma de potência. Com a crescente ênfase em componentes eletrônicos portáteis e aplicações sem
fio, baixa dissipação de potência deve se tornar um requerimento importante para designs de chips VLSI.
Circuitos assíncronos têm baixa latência de saída, pois os sinais de saídas são gerados imediatamente após o
recebimento dos sinais de entrada, sem a necessidade de se esperar o próximo sinal de clock. Essa
característica é importante em controladores de memória e em circuitos de alto desempenho.
1.2. Sistemas digitais assíncronos: problemas
Mesmo tendo levantado vários argumentos a favor do uso de assíncrono na última seção, existem alguns problemas
com o projeto de assíncronos em seu estado atual. Circuitos assíncronos são difíceis de projetar manualmente,
principalmente devido ao fenômeno chamado hazard, que são glitches potenciais, ou pulsos indesejados no circuito.
Nos circuitos síncronos, glitches não causam problemas contanto que os mesmos se estabilizem antes do próximo sinal
de clock. No entanto, em circuitos assíncronos, glitches não podem ser tolerados pois os circuitos são sensíveis a toda e
qualquer mudança nos sinais de entrada. Portanto, os projetistas precisam estar bem atentos a cada passo durante a
síntese para evitar esses problemas no projeto final (Myers, 2001; Yuan, et al., 2004).
Um problema ainda maior no projeto de assíncronos é a falta de ferramentas para síntese automática, como também,
para verificação e testabilidade. As poucas ferramentas existentes carecem de eficiencia, quando aplicadas em grandes
sistemas digitais. Ainda mais importante, é fácil prever que para o futuro, praticamente todos os projetos assíncronos
deverão interagir com os projetos síncronos já existentes. As metodologias atuais para o projeto de circuitos assíncronos
não estão adequadas para serem aplicadas em circuitos heterogêneos, os quais consistem de componentes síncronos e
assíncronos.
1.3. Projeto digital assíncrono: estilos
Uma maneira convencional de classificar circuitos assíncronos é pela robustez de cada classe de circuitos com
respeito às variações no atraso dos componentes de sistema físico. Cada classe de circuitos faz algumas hipóteses sobre
atrasos. Essas hipóteses diretamente afetam a validade dos métodos de síntese. Por exemplo, um modelo que assume
que as portas possuem atrasos arbitrários não seria aplicável para circuitos síncronos, pois nesse modelo não existe
garantia de que as mudanças nas saídas das portas irão se estabilizar dentro de um período de clock (Hauck, 1995).
Um circuito insensível a atrasos (delay-insensitive – DI) são circuitos assíncronos que funcionam corretamente
independentemente das variações de atraso dos fios e das portas que o compõem. Em outras palavras, esta classe de
circuitos é modelada como tendo atrasos arbitrários e finitos tanto em suas portas quanto em seus fios. Esses circuitos
consistem de macromódulos e de fios que os conectam. Cada macromódulo deve ser projetado de modo a garantir que
as variações de atrasos nos fios não causem mau funcionamento do circuito. O projeto interno dos macromódulos prevê
certos valores temporais. Por isso os mesmos não são insensíveis a atrasos, embora as comunicações entre eles o sejam.
Uma outra classe robusta (equivalente ao DI) mas com alguma consideração temporal é quase insensível a atraso (quasi
delay insensitive – QDI), onde os fios com fan-out >1 (isochronic fork) devem ter atrasos iguais (Myers, 2001; Sparso,
Anais do XVI ENCITA, ITA,20 de outubro de 2010
,
et al., 2001). A classe de circuitos independentes de velocidade (speed-independent – SI) opera corretamente
independentemente das variações no atraso das portas, e os atrasos nos fios são desprezíveis (Hauck, 2001). A hipótese
SI era viável nos primeiros tempos do VLSI, quando os atrasos nos fios eram desprezíveis comparados aos das portas.
No entanto, nas novas gerações de VLSI os atrasos dos fios não são mais insignificantes. Portanto, ao projetar-se
circuitos com a hipótese SI deve-se ter extremo cuidado para que a suposição de fios com atrasos constante (diferença
desprezível) não seja violada. A classe de circuitos assíncronos que mais se aproximam dos circuitos síncronos, opera
corretamente no modelo onde os atrasos nas portas e linhas são conhecidos e possuem limite inferior e superior
(bounded gate and wire delay – BGWD).
Existem diferentes estilos de projeto assíncrono. Cada estilo está relacionado com a classe do circuito, arquitetura e
metodologia. Um interessante estilo de projeto de sistemas assíncronos é o de decomposição. Este estilo decompõe o
sistema em controlador + datapath. Um estilo bastante popular para síntese do controlador é as máquinas de estado
finito assíncrona modo rajada estendido (MEFA_MRE) (extended burst-mode machine) (Yun, 1999). As MEFA_MRE
são máquinas modelo Mealy que na maoria dos casos é especificada incompletamente (MEFA_MRE_EI), e obedecem
ao modelo BGWD. A interação com o ambiente acontece no modo fundamental (Yun, 1999). A ferramenta 3D
proposta por Yun no seu doutorado sintetiza as MEFA_MRE na arquitetura de Huffman estendida (ver figura 1b). Esta
arquitetura usa as variáveis de saída como estado, que possibilita circuitos menores, mas há o potêncial de aumento do
tempo de latência. A minimização de estados é uma importante tarefa na síntese de MEFA_MRE_EI, mas os
algoritmos propostos que realizam minimização exata exigem um alto esforço computacional, inviabilizando a tarefa
para máquinas grandes. Os motivos são: a explosão na geração das classes de compatibilidade e a etapa de cobertura
mínima é um problema NP-completo (McCluskey, 1986).
Neste artigo propomos um algorimo de minimização de estados para MEFA_MRE_EI, que é uma adaptação do
algoritmo classico de minimização de estados para MEF especificadas completamente (MEF_EC), que é baseado na
álgebra das partições. A nosso algoritmo está voltado para a arquitetura de Huffman (ver figura 1a) (Huffman, 1954),
onde os estados são identificados por variáveis de estado, portanto baixo tempo de latência. A tarefa de minimização de
estados para MEF_EC exigem um baixo esforço computacional. As classes geradas são drasticamente reduzidas e o
algoritmo de partições tem complexidade linear (McCluskey, 1986). Para obtermos um baixo esforço computacional na
máqunas EI o nosso algoritmo incorpora uma nova operação que é a fusão de partições. O algoritmo proposto obtém
resultados bastante satisfatórios, no caso sub-ótimo.
Este artigo está estruturado como segue: seção 2 apresenta a especificação MEFA_MRE; seção 3 mostra conceitos
de minimização de estados e o algoritmo de particionamento; seção 4 ilustra duas aplicações do algoritmo; seção 5
apresenta uma discussão e resultados; seção 6 finalmente as nossas conclusões e trabalho futuro.
E ntradas
Saidas
E ntradas
S aidas
E stados
E stados
(a)
(b)
Figura 1. Arquitetura alvo: a) máquina de Huffman; b) máquina de Huffman estendida (saída realimentada).
2. Especificação de MEFA_MRE
O modo rajada estendido é uma interface poderosa para especificar uma grande classe de controladores. Sua
intenção é projetar máquinas de estados assíncronas e máquinas que caiam na área intermediária, entre síncronos e
assíncronos, mesmo assim é teoricamente possível fazer a especificação de qualquer máquina síncrona Moore e
praticamente possível de fazer o projeto de pequenas e médias máquinas síncronas de Moore. É particularmente útil
para controladores que operam com sistemas heterogêneos, isto é, com sistemas com uma mistura de componentes
Anais do XVI ENCITA, ITA,20 de outubro de 2010
,
síncronos e assíncronos. É importante notar que toda especificação legal do modo rajada estendido é possível de se
implementar.
Figura 2 mostra um exemplo de especificação do modo rajada estendido (benchmark biu-dma2fifo). Sinais que não
estão cercados por desigualdades (< >) e terminam com + ou – são sinais terminais. Esses são sinais de transição.
Sinais cercados pelas desigualdades (<>) são condicionais, que são sinais cujos valores são amostrados quando todas as
transições terminais associadas a eles tenham ocorrido. O condicional <a+> pode ser lido como “se a estiver alto” e <a> pode ser lido como “se a estiver baixo”. Uma transição de estado ocorre se todas as condições são satisfeitas e todas
as transições têm aparecido. Um sinal terminado com asterisco é um direct don’t care. Se “a” é um direct don’t care
deve haver uma seqüência de transições de estados na máquina rotulada com a*. Se uma transição de estado é rotulada
com a*, as seguintes transições de estado na máquina devem ser rotuladas com a* ou com a+ ou com a- (as transições
terminais para o direct don’t care). A figura 2 descreve uma máquina de estados, tendo uma entrada condicional
(cntgt1), três entradas de transição (ok,frin,dackn) e duas saídas (dreq,faout). Consideremos a transição de estado 4→5.
Nesse ponto, o comportamento da máquina é: “Se cntgt1 está baixo quando dackn abaixar, vá para o estado 2 e abaixe a
saída dreq”.
Figura 2. Especificação modo rajada estendido: biu-dma2fifo.
Um sinal direct don’t care deve mudar no máximo uma vez durante a seqüência de transições de estados que rotula,
isto é, direct don’t care são sinais monotônicos, e, se não mudam nessa seqüência, deve mudar durante a transição de
estado que esse terminal de transição rotula. Um terminal de transição que não é imediatamente precedido por um direct
don’t care é chamado compulsório, desde que deve aparecer na transição de estado que rotula. Na figura 2, frin está em
nível baixo quando a especificação está no estado 4. Essa variável pode assumir nível alto em qualquer instante com o
“deslocamento” da máquina entre os estados 5 e 6 ou para o estado 2, dependendo do nível de cntgt1, e deve ter subido
no instante em que a máquina vai para o estado 6 ou 2, pois a terminação de transição frin+ aparece entre os estados 5 e
6 e também entre os estados 4 e 2.
Os sinais de entrada são globalmente particionados em sinais de nível (condicionais), os quais nunca podem ser
usados como sinais de transição, e sinais de transição (terminais ou direct don’t care), os quais nunca podem ser usados
como sinais de nível. Se um sinal de nível não é mencionado em uma particular transição de estados, ele pode mudar
livremente. Se um sinal de transição não é mencionado, esse não pode mudar livremente. Mais genericamente, uma
máquina assíncrona de estados finitos modo rajada estendido é especificada por um diagrama de estados que consiste
de um número finito de estados, um conjunto de transições rotuladas conectando pares de estados, e um estado inicial.
Cada transição de estado é rotulada com um conjunto de sinais de nível e dois conjuntos de sinais de transição: uma
rajada de entrada e outra de saída. Uma rajada de saída é um conjunto de saída de transição, e uma rajada de entrada é
Anais do XVI ENCITA, ITA,20 de outubro de 2010
,
um conjunto não-vazio de entradas de transição (terminais ou direct don’t care), pelo menos um dos quais deve ser
compulsório.
Em um dado estado, quando todos os sinais condicionais especificados têm valores corretos e quando todos os
terminais de transição especificados na rajada de entrada têm aparecido, a máquina gera a correspondente rajada de
saída e vai para o próximo estado. Sinais de transição especificados na rajada de entrada podem aparecer em uma
ordem temporal arbitrária. Contudo, os sinais condicionais devem estabilizar em níveis corretos antes de qualquer sinal
compulsório na rajada de entrada apareça e devem manter seus valores até que todas as terminações de transição
apareçam. O atraso mínimo da estabilização condicional para a primeira transição compulsória é chamado tempo de
setup. Analogamente, o mínimo atraso do último sinal terminal até a mudança na condicional é chamado tempo de hold.
Valores atuais de tempo de setup e hold de sinais condicionais com respeito ao primeiro pico compulsório e o último
pico terminal dependem da implementação. O período entre o especificado tempo de setup antes do primeiro pico
compulsório e terminando no especificado tempo de hold depois do último pico terminal é chamado tempo de
amostragem. Níveis de sinais condicionais não precisam ser estáveis fora dos especificados períodos de amostragem.
Cada sinal especificado com um direct don’t care pode modificar seu valor monotonicamente a qualquer instante
incluindo durante as rajadas de saída, a menos que já esteja no nível especificado no próximo pico terminal. As saídas
podem ser geradas em qualquer ordem, mas o próximo conjunto de picos compulsórios da próxima rajada de entrada
não deve aparecer até que a máquina esteja estabilizada. Diferentes ferramentas foram propostas para síntese de
máquinas de estado modo-rajada e extensões (Yun, 1999; Fuhrer, 1999; Oliveira, 2004).
Seguem alguns exemplos de rótulos de transições de estados:
•
•
<c1+><c2->x+/z1+z2- significa: se c1=1 e c2=0, quando x “subir”, a máquina deve “levantar” z1 e
“abaixar” z2.
x1+x2-/z+
significa: quando x1 “subir” e x2 “abaixar” a máquina deve “levantar” z
3. Minimização de estados para MEFA_MRE_EI
Aplicaremos o nosso algoritmo no benchmak biu-dma2fifo (figura 2) (Yun, 1999). Ele descreve um controlador
para uma unidade de interface de barramento (Bus Interface Unit), cuja função é controlar o barramento de dados entre
o DMA (Direct Memory Access) e a FIFO (first-in first-out). Este controlador faz parte da interface SCSI (Small
Computer Systems Interface). Para facilitar a exposição do algoritmo de minimização de estados, a especificação MRE
será descrita na representação equivalente que é a tabela de fluxo MRE, que já está voltada para a arquitetura de
Huffman. Figura 3 mostra o benchmark biu-dma2fifo descrito na tabela de fluxo MRE, onde os sinais de entrada O,F e
D são respectivamente ok, frin e dackn.
Figura 3. Tabela de fluxo MRE: biu-dma2fifo.
Anais do XVI ENCITA, ITA,20 de outubro de 2010
,
Os algoritmos propostos para minimização de estados das MEFA_MRE_EI podem gerar até 2N classes
compatíveis, onde N é o número de estados. O motivo deste número elevado de classes é que a propriedade transitiva
nas MEFA_MRE_EI não é obedecida, portanto um estado pode aparecer em várias classes. Isto ocorre porque um
estado don’t-care pode assumir vários estados, para permitir a compatibilidade. Para reduzir drasticamente o esforço
computacional do algoritmo de minimização de estados, propomos uma nova operação que é a fusão de partições.
Neste modelo o estado don’t-care na fusão assumirá um único estado. A escolha do estado atribuído ao estado
originalmente don’t-care segue a heurística da ordem dos estados da tabela de fluxo. Os algoritmos de minimização de
estados para MEF_EI usam o conceito de par de estados compatíveis. Este conceito continua valendo no nosso
algoritmo.
Definição 3.1 (Unger, 1969) Dois estados A e B da tabela de fluxo T que opera no modo fundamental são compatíveis
se e somente se:
(a)
Se forem especificados, as saídas são idênticas, e
(b)
Se forem especificados, os seus próximos estados também são compatíveis
Se um par de estados é compatível, então eles podem ser fundidos. A fusão de estados pode inviabilizar a etapa de
minimização lógica livre de risco lógico nas MEFA_MRE. A cobertura de implicantes obedece a um conjunto de
regras, onde a fusão de estados pode inviabilizar estas regras. A inviabilidade é porque a definição 3.1 não satisfaz a
cobertura de implicantes livre de risco. Para solucionar este problema, há uma extensão desta definição.
Definição 3.2 (Nowick, 1995) Dois estados A e B da tabela de fluxo MRE_EI T são compatíveis livre de risco se e
somente se:
(a) Se forem especificados, as saídas são idênticas, e
(b) Se forem especificados, os seus próximos estados também são compatíveis, e
(c) Regras de cobertura lógica livre de risco são viabilizadas.
A definição 3.2 permite gerar classes de compatibilidade em que um estado pode fazer parte de diferentes classes,
portanto pode levar a uma explosão de classes. Nas máquinas especificadas completamente um estado faz parte
somente de uma única classe, portanto gera-se uma partição. Para ilustrar o modelo de estado único, apliquemos no
benchmark da figura 3. A primeira etapa de um algoritmo de minimização de estados para máquinas EI é a geração de
todos os pares de estados compatíveis, que é obtido na aplicação da definição 3.2. Por exemplo, o estado 0 é comparado
com os estados (1,2,..6) e gera os pares de estados compatíveis (0,1)e (0,4). O estado 1 é comparado com os estados
(2,3,...,6) e gera o par (1,4), e assim por diante. Como houve a geração dos três pares de estados compatíveis (0,1), (0,4)
e (1,4), então temos a classe (0,1,4), porque temos as três combinações de pares compatíveis possíveis. Nas máquinas
EI faz-se a geração de todos os pares possíveis. Nas nossas máquinas a geração de um par compatível, imediatamente
usa-se este par para comparar com outros estados. Para as nossas máquinas o estado 0 é comparado com o estado 1,
como são compatíveis temos a classe (0,1). A seguir a classe (0,1) é comparada com os estados que segue (2,3,4).
Como há compatibilidade entre a classe (0,1) e o estado 4, então gera a classe (0,1,4).
3.1. Método K-partição
Neste artigo apresentamos uma extensão do algoritmo K-partição. Diferente do algoritmo clássico, onde somente
há reparticionamento, no nosso algoritmo também há fusão de partições. Ele é processado em seis passos e é aplicado
nas MEFA_MRE_EI, portanto toda partição final satisfaz a definição 3.2:
1: Todos os estados da MEFA_MRE_EI estão em uma única partição.
2: Particione os estados separando os de saída diferentes
3: Reparticione os estados criando partições separadas para os estados de uma mesma partição, mas que os seus
próximos estados estejam em partições diferentes.
4: Repita o passo 3 até que a nova partição gerada seja igual a anterior.
5: Seja C o conjunto de K partições finais, {P1,P2,...,PK}; compare Pi de C, onde 1≤i≤K com Pj de C tal que i≠j.
Se Pi e Pj forem compatíveis, então gerar a partição Pij.
6: Repita o passo 6 até que a nova fusão de partições gerada seja igual a anterior.
Anais do XVI ENCITA, ITA,20 de outubro de 2010
,
A ferramenta de minimização de estados aceita a descrição textual das MEFA_MRE, no caso o benchmark biudma2fifo (ver figura 4).
input ok
input frin
input dackn
input cntgt1
output
output
01
12
15
23
34
45
42
56
60
0
0
1
0
dreq
faout
ok+ frin*
[cntgt1+] frin* dackn[cntgt1-] frin* dacknfrin+ dackn+
frin+
[cntgt1-] frin* dackn[cntgt1+] frin* dacknok* fain+ dackn+
ok- frin-
0
0
| dreq+
| dreq| dreq| faout+
| dreq+ faout| dreq| dreq| faout+
| faout-
Figura 4. Descrição textual (arquivo de entrada) do biu-dma2fifo para a ferramenta de minimização.
4. Exemplos
Para ilustrar o nosso método de minimização de estados, aplicaremos em dois benchmarks
4.1. Benchmark biu-dma2fifo
A arvore descrita na figura 5 mostra o procedimento do nosso algoritmo de partição. Cada vértice descreve uma
partição e as arestas indicam o reparticionamento ou fusão de partições. A raiz é o passo 1 do nosso algoritmo. O passo
2 corresponde ao nível 2 da arvore. Os passos 3 e 4 correspondem ao nível 3 da arvore. Os passos 5 e 6 correspondem
ao nível 4 da arvore. No ultimo nível da arvore aparecem ás partições finais, que definem os estados fundidos. Neste
exemplo houve a fusão das partições ((0),(1,4)) que gerou a fusão dos estados (0,1,4). Figura 6 mostra a tabela de fluxo
MRE reduzida.
Figura 5 Arvore de particionamento: biu-dma2fifo
Anais do XVI ENCITA, ITA,20 de outubro de 2010
,
Figura 6 Tabela de fluxo MRE_EI reduzida: biu-dma2fifo.
4. 2. Benchmark Hp-ir
As figuras 7 e 8 mostram respectivamente benchmark Hp-ir descrito na forma de diagrama e de tabela de fluxo. A
figura 9 mostra a arvore de particionamento, onde obtivemos as fusões dos estados (1,2,7), (0,5), (3,4) mostrados no
ultimo nível da arvore. Neste exemplo, as partições ((3),(4)) e ((0),(5)) foram fundidas A figura 10 mostra a tabela de
fluxo MRE reduzida.
Figura 7. Especificação modo rajada: Hp-ir
Anais do XVI ENCITA, ITA,20 de outubro de 2010
,
Figura 8. Tabela de fluxo modo rajada Hp-ir
Figura 9 Arvore de particinamento: Hp-ir
Figura 10. Tabela de fluxo MR_EI reduzida: Hp-ir
Anais do XVI ENCITA, ITA,20 de outubro de 2010
,
5. Discussão e Resultados
O algoritmo proposto usa como estrutura intermediária uma arvore, que facilita o reparticionamento e as fusões de
partições. Em cada nível da arvore o número de vértices não ultrapassa o número de estados. O número de níveis é no
máximo de quatro. Toda partição que está contida em outra partição é eliminada. O algoritmo proposto foi testado
manualmente em vários benchmarks. Os dois benchmarks ilustrados obtiveram a minimização exata.
6. Conclusão
Trata-se de um trabalho inovador na literatura, que procura diminuir o esforço computacional requerido no
processo de minimização de MEFA_MRE. O processo de minimização de estados é um problema NP-completo e por
isso torna-se inviável para máquinas de grande porte. Com essa motivação, foi proposto um algoritmo que é uma
expansão do algoritmo de particionamento que visa viabilizar uma minimização para máquinas como as mencionadas
acima, mesmo que tal procedimento não garanta uma redução máxima do número de estados. O algoritmo proposto foi
detalhado e um software computacional que o implementa está sendo desenvolvido na linguagem C++ no ambiente PCwindows.
7. Agradecimentos
Agradeço a Deus e minha família pelo apoio dado em momentos difíceis e também ao CNPQ pelo auxílio
financeiro de grande valia.
8. Referências
Myers, C. J., 2001, “Asynchronous circuit design,” John Wiley & Sons
Spars_, J and Furber, S (eds.), 2001, “Principles of asynchronous circuit design - A systems perspective,” Kluwer
Academic Publishers.
McCluskey, E. J., 1986, “Logic Design Principles with Emphasis on Testable Semicustom Circuits”, Prentice-Hall.
Yuan, J. S. and Kuang, W. 2004, “Teaching Asynchronous Design in Digital Integrated Circuits,” IEEE Trans on
Education, vol.47, no. 3, pp. 397-404.
Sutherland, E. and Ebergen, J., 2002, “Computers without clocks,” Sci. Amer., pp. 62-69.
S. Hauck, S., 1995, “Asynchronous Design Methodologies: An Overview”, Proc. of the IEEE, Vol. 83:1 pp.69-93.
Huffman, H., 1954, “The Synthesis of Sequential Switching Circuits,” J. Franklin Ins., Vol. 257, pp. 161-190, March e
pp.275-303, April.
Nowick, S. M., 1995, “Automatic Synthesis of Burst-Mode Asynchronous Controllers,” Ph.D. thesis, Stanford
University.
Yun, K. Y. and Dill, D. L., 1999, "Automatic Synthesis of Extended Burst-Mode Circuits: Part I (Specification and
Hazard-.Free Implementation) and Part II (Automatic Synthesis)," IEEE Trans. on CAD of Integrated Circuit and
Systems, Vol. 18:2, pp. 101-132.
Fuhrer, R. M., 1999, “Sequential Optimization of Asynchronous and Synchronous Finite-State Machine”, Ph.D. thesis,
Department of Computer Science, Columbia University.
Oliveira, D. L., 2004, “Miriã: Uma ferramenta para síntese de controladores assíncronos multi-rajada,” tese de
doutorado, EPUSP.