| dc.description.abstract | Tilstandsmaskiner (FSM-er) blir utstrakt brukt i digital maskinvaredesign. Ettersom markedet for integrerte kretser og brikke-systemer er økende m ̊a designene følge etter. FSM-er blir ofte spesiallaget og hardkodet for hver enkelt implementasjon. Følgende kan ikke oppførselen endres etter at brikken er produsert. I tillegg tar det tid å designe hver FSM. Denne oppgaven undersøker en Universell Programmerbar FSM (UPFSM) som kan erstatte eksisterende FSM-er.
En FSM har et sett med tilstander, et antall inn- og utganger, en overgangs- og en utgangsfunksjon. Overgangsfunksjonen returnerer neste tilstand basert på nå-tilstanden og inngangsverdiene. Utgangsfunksjonen returnerer utgangsverdiene. For en Moore-maskin er denne kun avhengig av nåtilstanden, mens en Mealy-maskin i tillegg er avhengig av inngangsverdiene.
To løsninger for en UPFSM er blitt prototypet og undersøkt:
LFSM-en er basert på en oppslagstabell (LUT), og minner om mikroprogrammert kontroll. Den holder neste-tilstanden og utgangsverdiene i en oppslagstabell som blir indeksert av nåtilstanden og inngangsverdiene. LFSM-en er koblet til en buss, slik at en mikroprosessor kan skrive et nytt program til oppslagsen.
SWFSM-en er basert på programvare. Inn- og utgangssignalene til FSM-en er forlenget til registre som kan leses og skrives til av en mikroprosessor. Mikroprosessoren kjører et program som leser inngangsverdiene, regner ut neste tilstand og skriver utgangsverdiene til registerne.
Begge disse løsningene er brukt til å erstatte en eksisterende FSM i TD, et eksisterende test-design. TD er en del av en større test-brikke, TC, som har en mikroprosessor.
Den originale hardkodede FSM-en, LFSM-en og SWFSM-en er sammenlignet. Den originale FSM-en er ikke programmerbar, men er lett å bruke, krever lite areal og genererer utgangsverdier hver klokkesykel. LFSM-en er like rask, men er vanskelig å programmere og krever mye areal. For FSM-en i TD, bruker LFSM-en 3.71 ganger (Moore) eller 5.6 ganger (Mealy) mer areal enn den originale FSM-en. Arealet øker eksponensielt med størrelsen til FSM-en. En Moore LFSM med ”666” {#inngangssignaler, #tilstandsbits, #utgangssignaler} er 441 ganger større enn en ”222” Moore LFSM. SWFSM-en bruker mindre areal (sett bort i fra mikroprosessoren), er er enklere å programmere, men den er veldig treg siden den bruker 992 klokkesykler til å lese inngangen og skrive til utgangen.
En UPFSM vil alltid være et kompromiss mellom areal, ytelse, brukervennlighet og kompleksitet. Men, programmerbarhet kan i visse design være veldg nyttig, og denne oppgaven har vist noen mulige måter implementere dette på. | |
| dc.description.abstract | FSMs are used extensively in digital hardware designs. As the market for ICs and SoCs is increasing rapidly, the designs must follow. FSMs are often custom made and hardwired for each implementation. Thus, their behavior cannot be changed after manufacturing, and it takes time to design each FSM. This thesis investigates a Universal Programmable FSM (UPFSM), which can replace existing FSMs.
An FSM has a state set, a number of inputs and outputs, a state transition function, and an output function. The state transition function finds the next state based on the current state and the input signals. A Moore machine FSM calculates the output based on the current state, while a Mealy machine FSM also uses the input signals.
Two solutions for the UPFSM has been prototyped and investigated:
The LFSM is a LUT based solution which is similar to microprogrammed control. It stores the next state and the output in a LUT which is indexed using the current state and the inputs. The LUT is connected to a bus, allowing a microprocessor to write a new program to LFSM.
The SWFSM is a software-based solution. The input and output signals for the ”FSM” are routed to registers accessible by a microprocessor. The microprocessor runs a program in software that read the input register, computes the next state and outputs, and write to the output register.
Both these solutions are used to replace an existing FSM in TD, an existing test-design. TD is part of a larger test-chip, TC, which has a microprocessor.
A comparison between the original hardwired FSM, the LFSM, and the SWFSM has been carried out. The original hardwired FSM is not programmable, but easy to use, has a small area, and provide an output every clock cycle. The LFSM is equally fast as the hardwired FSM but not easy to program and require more area. For the FSM in TD, the LFSM is 3.71 times (Moore) or 5.6 times (Mealy) larger than the original hardwired FSM in area. The LFSM area increases exponentially with FSM size. A ”666” {#input bits, #state bits, #output bits} Moore LFSM is 441 times larger than a ”222” Moore LFSM. The SWFSM require little area when the microprocessor is not considered, and it is easier to program. It is, however, very slow compared to the others, using 992 microprocessor clock cycles to read the input and write the output.
A UPFSM will always be a compromise between area, speed, ease of use, and complexity. However, the programmability can be very useful in certain designs, and this thesis has shown some possible ways to implement it. | |
