L7.1. Sequential implementation of algorithms

Loading...

Del curso dictado por Universitat Autònoma de Barcelona

Digital Systems: From Logic Gates to Processors

176 calificaciones

Universitat Autònoma de Barcelona

Digital Systems: From Logic Gates to Processors

176 calificaciones

This course gives you a complete insight into the modern design of digital systems fundamentals from an eminently practical point of view. Unlike other more "classic" digital circuits courses, our interest focuses more on the system than on the electronics that support it. This approach will allow us to lay the foundation for the design of complex digital systems. You will learn a set of design methodologies and will use a set of (educational-oriented) computer-aided-design tools (CAD) that will allow you not only to design small and medium size circuits, but also to access to higher level courses covering so exciting topics as application specific integrated circuits (ASICs) design or computer architecture, to give just two examples. Course topics are complemented with the design of a simple processor, introduced as a transversal example of a complex digital system. This example will let you understand and feel comfortable with some fundamental computer architecture terms as the instruction set, microprograms and microinstructions. After completing this course you will be able to: * Design medium complexity digital systems. * Understand the description of digital systems using high-level languages such as VHDL. * Understand how computers operate at their most basic level (machine language).

De la lección

Sequential circuits III and Finite State Machines

<b><font size=4 color=#B22222><b>Click on "v More" to read the purpose of this module</b></font> </b><br/><br/>This module deals with two topics: <ol><li>In previous lessons, the relation between algorithms (programming language structures) and combinational circuits has been commented. This relation also exists between algorithms and sequential circuits. We will explore this relation in the current module.</li><li>The second topic we will see is the definition and VHDL modelling of Finite State Machines.</li></ol>

L7.1. Sequential implementation of algorithms14:46

Conoce a los instructores

Elena Valderrama
Professor
Departamento de Microelectrónica y Sistemas Electrónicos. UAB.
Jean-Pierre Deschamps
Professor
Lluis Terés
Professor
Centro Nacional de Microelectrónica del CSIC
Merce Rullan
ProfesoraTitular
Departamento de Microelectrónica y Sistemas Electrónicos. UAB.
Joaquín Saiz Alcaine
Ingeniero Informático
Departamento de Microelectrónica y Sistemas Electrónicos. UAB.
David Bañeres
Profesor Agregado
Estudios de Informática, Multimedia y Telecomunicación. UOC.
Juan Antonio Martínez
Collaborator
APSI - UAB

[MUSIC]

In our preceding lesson we have commented

the relation between algorithms and combinational circuits.

Such a relation also exists between algorithms and sequential circuits.

The relation between algorithms and digital circuits

is one of the bases of this course.

Actually, some systems are sequential by nature, which is the case of systems

including an explicit or an implicit reference to successive time intervals,

and several examples have been seen before:

for example, circuits that generate sequences, or circuits that detect

some specific sequences, or circuits that control sequences of events.

But algorithms without any time reference

can also be implemented by sequential circuits.

Let us see a first example. We are going

to specify the working of a circuit that computes

the integer square root of a natural number X using

for that what we could call the "naive algorithm".

It consists of computing all pair (R, S)

such that S is the square of R+1.

For that we can use this relation. Thus, given R

and S such that S is equal to the square of R+1 (for example

if R = 2, R+1 is 3, and the square of

R+1 is 9), then in function of R and S we compute the next value of R,

that is R+1, and the next value of S, that is to say

R + 2 square, and then the corresponding algorithm is this one.

This computation is the body of a loop, loop controlled by this condition

that means that as long as S is smaller

than or equal to X, then we execute this loop.

As an example assume that X = 47.

Then the execution of this loop generates uccessively

number R equal to 0, S to 1, R equal to 1,

S equal to 4, and so on, up to the time when

for the first time the condition does not hold true

because 49 is greater than 47.

And the conclusion is that the square root (the

integer square root) of 47 is equal to 6.

A fiirst comment: this is obviously not a good

algorithm as the number of steps is equal to

the square root itself.

That means that for great values of X, X of the order of 2**n, the number of

steps is of the order of the square root of

2**n. It is used just for didactic purposes.

Then, if we have this algorithm, with a loop,

the first idea is an iterative combinational circuit.

For that, as we don't know in advance how many times the loop will be executed,

we modified the algorithm and say that once the condition

stops holding true, the value of S and R won't change any more.

So, if the condition holds true, then we execute

the two operations that we have seen before, but if the condition doesn't

hold true then the new value of S is the current value

of S, and the same for R. Then the component, this component,

executes this loop body

and the connections between components correspond to this instruction,

that is to say, the next value of S,

the output of this circuit, is the current value

of S, that is to say, the input of

the next circuit, and the same for the other input.

Then, with this configuration, the first output of the circuit computes

either number i (if the component is component number i) or the square root.

Now,

what is the number of components in this

iIterative circuit?

We know that the number of step is equal to the square root of X.

Then as X is smaller than 2**n, and its

square root is smaller than the square root of 2**n,

the number of steps is of the order (the maximum number

of steps) is the square root of 2**n.

That means that (an example)

if we are computing the square root of numbers with 32 bits, the

number of steps could be as large as 2 to the power 16,

that is a number greater than 65,000 components.

So, this circuit in this case would have more

than 65,000 components, obviously a too large number of components.

A better idea is Sequential Implementation.

We know that combinational circuits implement functions. Sequential circuits

include a combinational circuit so they also implement functions.

But what else does implement a sequential system?

Basically two things.

Memory and time partition thanks to the synchronization external signal.

Then we could associate the memory elements to variable

R And S, and partition the time into intervals,

and assign the time intervals to each operation, or to each group of operations.

For example, during the first time interval, we

could initialize the values of variables R and S.

Then during the second time interval, the third time interval, and

so on, we could execute those operations.

Then we could also add a new variable END used here and here.

And, in this way, we get the following algorithm,

that is to say: we initialize the variables R and S;

as long as condition S lower than or equal to X, we execute this set of

operation, and the END variable is equal to "false";

once the condition doesn't hold any more, then the values of

S and R wouldn't change any more, and the variable END will be equal to "true".

The synchronization input is used (here or here) to modify

the values of R and S, replacing the value of

S by the next value of S and the value of R by the next value of

R, as they are computed by the algorithm and thus by the combinational circuit.

So, we get the following sequential circuit that

consists of a combinational circuit and the memory.

The memory stores variables R and S, and the

combinational circuit computes the next values of R and S.

So it's a sequential circuit whose internal state

is constituted by the values of R and S.

Observe that the corresponding state transition graph of this sequential

circuit would include as many vertices as pairs (R, S),

and for every vertex as many edges as values of X.

That means a huge number of vertices and a huge number of edges.

Obviously not a good way to specify the circuit.

Now, some comments about algorithm implementation,

either by means of a combinational circuit

or by means of a sequential circuit.

Our first comment: conceptually, any algorithm without time

references, can be implemented by a combinational circuit.

For that, you could execute the algorithm for all input

variable values, and store the corresponding output values in a table.

Then once you have a table that defines

the circuit, you can generate the corresponding combinational circuit.

But obviously in many cases, this table enormous.

So that this method makes sense if you

have an unbounded space to implement the algorithm,

for example, unbounded silicon area,

and (furthermore) if you have a lot of

time to dedicate to the development of the circuit.

Then a better method is to directly translate algorithm instructions

into circuits.

We have seen examples before: how we can translate an

"if then else" instruction into a circuit with a multiplexer, or

the same with the "case" instructions, with the "loops", and so on.

But even with these methods, the results might be a too-large circuit,

and we have seen an example with the "naive" square root algorithm.

Now, what about sequential circuit?

Sequential circuits compute functions, like combinational

circuits, because they include a combinational circuit.

But, furthermore,

they are able to store data and

to assign different time intervals to different operations

thanks to the synchronization external signal.

The result is that, in the case of loops, memory elements allow to substitute N

identical components by one component that iteratively executes the loop body.

So we could say that space, that generally means silicon area,

has been replaced by time.

Furthermore, this method is not restricted to the case of iterations.

Let us see an example.

Consider this 4-instruction algorithm:

First instruction: compute X1 equal to some function F1 of the input X.

After that, compute X2 equal to some function F2 of

the first result obtained before X1, and so on,

X3 is a function of X2, and the output R is a function of X3.

To this algorithm corresponds this simple combinational

circuit with four components, one that implements function F1,

the second one function F2, function F3 and function F4.

But it could also be implemented by a sequential circuit.

First we slightly modify the algorithm with a new variable STEP

initially equal to FIRST.

Then we define the loop body: it's a "case"

instruction; in the case where STEP is equal to FIRST, then

R (variable R) is equal to F1 of the input X,

and the next STEP will be SECOND.

When STEP is equal to SECOND, R is equal to

F2(R) and the new step will be THIRD.

When STEP is equal to THIRD, we compute F3(R),

and now STEP will be equal to FOURTH,

and when STEP is equal to FOURTH, the new value of R will

be F4(R), STEP will be equal to some value FINAL,

and when STEP is equal to FINAL, STEP remains equal to this value FINAL.

So that the circuit we obtain is this one, this sequential circuit,

in which the combinational circuit executes the "case" instruction,

and the memory stores both R and STEP.

Conclusion:

algorithms can be implemented by sequential circuits.

For that, we use memory elements to store the variables;

we assign time intervals to the different operations of the algorithm,

and the operations are executed by the combinational part of the circuit.

In this way we get this architecture, that is

to say, the well known structure of sequential circuit.

We have compared sequential

and combinational implementation of algorithms

and have given two examples of sequential implementations.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play