Header Image - Randall Morgan

Monthly Archives

3 Articles

Designing The MiniMips – Part 4 Computer Architecture and Data Paths

by SysOps 0 Comments
This entry is part 4 of 4 in the series Designing the MiniMips

Ok, last time we completed the basic design of our ALU. I hope you took the time to build it in Logisim and play with it. It should be trivial to comfirm it works by doing simple operations on paper or a programmer’s calculator and the ALU and comparing the results. Once you have confirmed that your ALU works correctly,  it is time to save it as a sub-circuit in Logisim. We’ll take a short step back to discuss the basic operation of a CPU and support systems and then we’ll answer to question of where our ALU input values and control signals come from and where the output goes.

Computer Architecture

Computers all follow a similar architecture. At a minimum they have Input, Processing, Storage, and Output. These components can take various forms. For example, input could come from a keyboard as with the typical personal computer, or it may come from some type of sensor such as the oxigen sensor in your car. Output could be to a display screen such as the LED monitor or a relay used to control a well pump. Memory can take the form of registers, magnetic disks, solid state disks, integrated circuits, or even paper punch cards. Processing can be either analog, digital, or even quantum devices.  However, the typical computer most people think of is the PC or typical desktop or laptop machine.

Computers systems can be categorized into many categories. Here we will place them into two broad categories based on the system architecture. Systems using seperate stores for instructions and data are said to be of a Hardvard Architecture. These machine read cpu instructions from ROM (Read Only Memory) and execute them. All data is stored in the system RAM (Random Access Memory). A typical microcontroller such as the Atmel AtMega324 is an example of this architecture. Other machines store cpuinstructions and data in the same memory. This allows for programs to become dynamic, being altered or created by the running program. This type of achitecture is known as Von Nueman Architecture. The Von Nueman Architecture is a powerful because program instructions are treated just like data. It does have it’s down sides however. One such short coming is the issue of security. Since any running program can access the program instructions, it can alter not only it’s own code but the code of other programs. So a rouge program could for instance alter the program for calculating an aircraft’s altitude. This could result in personal injury or death to the passengers. Because of this short-coming a lot of work has gone into developing ways to limit programs from having complete access to all programs stored in memory. Modern Von Nueman machnes contain a large amount of circuitry to manage program access to memory so such things wont occur.

Here we will develop a system using the Hardvardarchitecture and use a seperate instruction and data memories. This will allow us to reduce a few complexities and focus on other issues. In the future I may write another article on developing a Von Nueman machine.

CPU Architecture and Data Paths

Ok, let’s talk a bit about how a digital computer system works.  The first thing that occurs in most systems when power is applied is that the major components are set to a predetermined state. This reset also occurs when a “Reset” button is pushed. If you’ve ever had to take a paper click and hold in a tiny button on your router, then you’ve used a reset button. After the system has been reset, the cpu begins to step through it’s cycles. The first cycle is the ‘Fetch’ cycle. In this cycle the CPU fetches the next instruction from the program memory. Next, the instruction decoder decodes the instruction into the appropriate control signals for the various cpu components. The next step is to ‘Execute’ the instruction. The last step is to ‘Store’ the results in memory if required by the instruction. Most cpu instructions follow this pattern. However, this cycle can be shortened or have wait states added to it for complex instructions. In simple processesors some of these instructions are combined. Usually the Fetch and decode cycles are made to occur in the same cycle. In a single cycle cpu are these steps occur in one clock cycle. This is often accomplished by multiplying the clock input to generate the needed signals. However, in some architectures such as the one we will build, these steps can occur in a single cycle without the need for clock multiplication.

Below is the logisim circuit for the SimpleComputer.  This is the basic machine we will be building.  I’ve included some 7-Segment Hex digit displays to allow use to view the the CPU operation. I also included four ports on the ALU that allow us to connect some of those displays directly to the registers in the registerfile. While the circuit looks pretty basic here, it is only because I have used logisim’s ability to can a subcircuit as a component. So in this view all the major components are actually subcircuits that vary in complexity. They are all made out of logic gates of logisim standard components. If you have not used the Subcircuit feature in logisim I recommend you break out the tutorials and learn to use them. OK, let’s describe the circuit from a 10,000 foot level. We’ll being seeing each componet in great detail as we move forward.

The machine must first be reset using the reset button in the lower left of the circuit. Then we can single step through programs by clicking the clock input. We can run programs from the simulation menu in logisim. Once reset, the PC (Program Counter) will be set to 0x00 hexidecimal (hex). This will cause the first program instruction to be placed on the data output of the ROM (Read Only Memory). The ROM instruction code is broken into various parts that control certain aspects of the CPU. For eample, bits 0-3 of the instruction contain the ALU OP code. These four bits are used directly to select the chosen ALU operation. For shift operations bits 4-7 select the shift distance. For example if bits 4 – 7 contain the value 0010b in binary, then the value on the ALU’s A input will be shifted by two bit positions. Many bits in the instruction perform multiple duties. For eaxample, although bits 0-3 and 4-7 are used for the ALUOP code and the SHIFTAMT they also do double duty as the lower order byte of an immediate address in an instruction that contains an address value.

Once the instruction code is broken into it’s constituent parts, the various signals are reouted to other parts of the circuit as needed. A portion of the instruction code defines the type of instruction being executed. This allows the proper signals to be generated to control the parts of the circuit that are not directly controled by the bits in the instruction. Next the if the instruction is a register type instruction, the two source registers and the destination register are selected. The values in those registers and posibly an immediate value are feed into the ALU A and B inputs. The ALU then produces the out for all the operations we provided hardware for. This is done in parallele so producing all output at once isn’t an issue. The ALUOP code selects the desired function results and places them on the ALU output. Depending on the instruction the ALU ouput could be routed back to the destination register selected in the RegFile or it may be stored in RAM or used as a RAM address. It could also be used to set condition flags the determine if a branch will be taken. Lastly, it can be used as the input to the PC though that portion of the circuit is not shown here.

Look over the circuit and trace through the signal paths. See if you can figure out how the various parts work to control the circuit. Next time we’ll talk about the Instruction Set and continue on about the architecture. Until then, I hope you all have a happy new year!



Designing The MiniMips – Part 3 A Basic ALU

by SysOps 0 Comments
<span class="entry-title-primary">Designing The MiniMips – Part 3</span> <span class="entry-subtitle">A Basic ALU</span>
This entry is part 3 of 4 in the series Designing the MiniMips

Ok, we left off last time discussing the issues involved in binary arithmetic. Specifically, we discussed subtraction and negative numbers. We watched a Compuphile video about the issues and the Prof. showed us how to use 2’s complement to use negative numbers and addition to complete subtraction. I had asked you to play around with your own ideas on how to implement this in hardware using Logisim to simulate your ideas. I hope you had fun doing that. Here’s my idea for implementing a binary adder that uses two’s complement to do subtraction.

Now this is only one stage of the circuit. What I’ve done is taken a typical full-adder circuit and added an XOR gate to the B input. The other leg of the XOR gate is used to control the inversion of the B input value. Additionally, I’ve also tied the Sub input control bit to an OR gate used to force a carry-in bit into the adder. This has the effect of inverting B to get the 1;s complement and then adding 1 to get the 2’s complement. Only the first bit needs the OR gate for a carry-in. However, every bit in B will need the XOR gate to invert the bit.


Ok, now that we’ve taken care of old business it is time to look at the next stage of our Microprocessor development. The core of any Microprocessor or Micro-controller is it’s Arithmetic Logic Unit. This piece of hardware is responsible for completing arithmetic and logic operations. If a basic logic or arithmetic operation is not implemented in the ALU it is much more difficult to implement that function in the systems built around the microprocessor. There are a few exceptions to that… We’ll discuss some of those later. For now, let’s look at how we might build an ALU for the MiniMips.

If you’ve followed this series so far, I assume you have the basic understanding of the primitive logic operations AND, OR, NOT, and XOR. We need to implement AND, OR, NOT, and XOR as well as Addition and Subtraction in our ALU. The simplest way to do this is to include a hardware circuit for each operation and then complete them in parallel. We can then select the desired operation from the various results. Since our hardware operates in parallel it takes no extra time to implement additional operations in our ALU this way.

So our ALU operations should look something like this:

One thing we haven’t discussed yet is Signal Bus’s. A signal buss is simply a group of conductors with a common implementation theme. For example, our ALU takes two inputs A and B. Each of these inputs contains 16 signal lines, one for each bit in the 16-bit value. We could refer to these signals as the A input Bus and B input Bus. You may have also heard of the Address bus and Data Bus in a computer system. These are just groups of Address or Data signals just like our A and B inputs. A simple way to think of a bus is just to think of them as a bundle of wires all carrying related signals.

Our simple ALU has six operations. It can Add, Subtract, NOT, AND, OR, and XOR our input values. Note that Inverting is only supported on the B input. This was a choice made for our design that helped reduce the number of logic gates needed to implement the design. This is great! We can now do multiple operations on our two input values. But how do we select the results of just a single operation? Well, that’s where multiplexer come in.


A multiplexer can be thought of as a rotary switch that selects one of many input signals:

This image show’s a two pole rotary switch. But let’s just concentrate on the top portion of the image. S1a is the first pole and the center armature or wiper simply rotates to make and break contact with the outer contact points as the user turns the rotor. To allow multiple conductors like our two input values A and B to be selected, these switches are manufactured with many sets of switches stacked on top of each other and connected to a single rotor. This way when the user turns the rotor, all the wipers rotate at the same time. With the switch shown a user can select from 1 of 6 positions. If we used rotary switches in our computer we would have to rotate these switches by hand to the proper positions and at the proper times, just to complete a single operation. Luckily there are solid state implementations of these devices called multiplexers and demultiplexers. A multiplexer simply takes many input values and switches one of them to a single output. A demultiplexer works the other way around. So a multiplexer is a many to one and demultiplexer of a one to many switch. In Logisim you’ll find multiplexers and demultiplexers under the Plexer components.

You may be asking how we tell a mux or demux (multiplexer/demultiplexer) which contacts to use or how each input to select? Well, we have to provide a selection signal. This is just a binary value. Let’s look at a simple four bit to one bit multiplex circuit.

Build the Mux and Demux circuits shown below and see that the input or output is selected buy the two select bits S0 and S1. These are simple 4-to-1 and 1-to-4 circuits that control a single bit. We will need circuits that control 16-bit inputs with as many as 16 selectable inputs.

As you can see, we’ve used a set of AND gates and wired the the selection inputs and their complements to the gates to provide activation of each gate with a specific binary value. This allows only one AND gate to be active at a time. The AND gate outputs are all then fed into a single OR gate. That gate outputs is the signal on the input to the selected AND gate.

To convert the mux into a demux, we only need to tie all the signal inputs together and remove the OR gate.  Try this in logisim. Build the two circuits above and tie the output of the mux to the input of the demux. Then tie S1 together on both circuits. Next tie S0 together on both circuits. Now you should be able to select one input on the mux and get the signal out of the same input on the demux.

Now let’s see how we can tie a mux to our ALU so that we can select a single operation from the ALU:

Ok, so here we have our ALU with a few extras. First and foremost is Mux we added to the output. I’ve labeled the select lines for the Mux as OPCODE. If you look at the miring of the mux you’ll notice that I wired the out of the adder to the first two inputs of the mux. I then created a decoder that decodes the value 1 from the four OPCODE bits. The resulting signal is used to tell the Adder/Subtractor to subtract. This allows us to select Addition as 0 and subtraction as 1. Here’s a table of OPCODE values and ALU operations:

0000 A+B
0001 A-B
0010 ~B
0011 A AND B
0100 A OR B
0101 A XOR B

Now you may have noticed that I used a mux with four select inputs. This allows up to 16 operations but I’ve only included six here. We will be adding more operations to our ALU later. Now you may be asking “Where does the values for A, B and OPCODE come from” ? Well, that all depends on our instruction set and how we implement it. We’ll be discussing that soon. For now, try and build an ALU that matches the operation of this one.

Designing The MiniMips – Part 2 Subtraction and Negative Numbers

by SysOps 0 Comments
This entry is part 2 of 4 in the series Designing the MiniMips

Last time we discussed binary addition and how we could use a few logic gates to do arithmetic. I showed you a few simple circuits and left you with a simple assignment to use the full adder circuit to build a multi-bit full adder. I told you I’d show you a solution to the exercise. So here it is:

As you can see the full adders are simply cascaded by connecting the carry-out of the previous stage to the carry-in on the next stage. This cascading can be continued until the propagation delay of the carry signal become intolerable. If that happens there are techniques for improving the circuit. Checkout the Carry Lookahead Adder circuit.

Binary subtraction

We’ve seen how binary adders can be built from simple logic gates. Now let’s look at binary subtraction. The binary subtraction rules are very simple:

0-0 = 0 1-0=1 1-1 = 1 10-1 = 1

Binary subtraction is similar to decimal subtraction with the difference that when 1 is subtracted from 0, it is necessary to borrow 1 from the next higher order bit. That bit is reduced by 1 and the remainder is 1. The one thing that confuses most people when doing a binary borrow is that when you borrow in decimal you add it as 10 to the previous column. In binary we are using powers of 2. So when we borrow we must add the borrow as two bits of half the original value:

1  1  1
1  1
1 0 0 0
0 1 0 1
0 1 1

In the above, starting from the left most bit. First we can’t subtract 1 from 0 so we try to borrow 1 from the next column to the right (the tow’s column). However, it too is 0. We can’t borrow 1 from 0 so we move on to the third column left (the fours column). Next, in the fourth column left we find a 1 in the eights column. Now this one represents an 8 in decimal. So when we move it to the fours column. We have to split that 8 into two 4s. So we place two 1’s above the fours column. Next we borrow one of them and move it to the two’s column as two 2s. Again, we borrow a two from the 2s column and move it as two ones and place them in the 1s column. Now we can subtract the 1 in the right most the two ones we placed there. This leaves a one which we bring down.  In the two’s column we can now subtract 0 from the remaining 1 and get 1. We then move left to the fours column and subtract 1 from the remaining 1 we carried over and get 0. The eights column is now 0 and being a leading 0 we don’t really need to bring it down as it adds no value to our answer. Now to check our answer we can see that our original problem was: 8-5=3. And indeed 11 in binary is 3 in decimal.

Now let’s look at the logic needed to do a single bit binary subtraction. The truth table for subtraction is:

A B Diff Barrow
0 0 0 0
1 0 1 0
1 1 0 0
0 1 1 1


Looking at the table we can see that the difference is computed using an XOR gate. The borrow out however is a slightly more complex. Borrow out is only 1 when A is 0 and B is 1. This looks like and AND gate with an inverter on B.  Let’s try it out in logisim. Build the following circuit in logisim and see if it matches the truth table above:

Now this circuit is called a half subtractor. Just as the half adder is missing a carry in, the half subtractor is missing a borrow in. However, a similar cascading trick like that used for the half adder can be used to build a full subtractor. Let’s try this out. Build the circuit below in logisim and give it a try:

Negative Numbers

Now this kind of subtractor is great if you are only working with positive numbers. But if we ever need to work with a negative value as an operand or a resulting value, we are out of luck. So how do we handle negative numbers? Well, the most typical way is to reserve the left-most bit for use as a sign bit. The sign bit is set to 1 to indicate a negative value and 0 to indicate a positive value.  So if we have 8 bits we can represent -127 through +127.  There is an issue however, To demonstrate it let’s reduce this to a bit bit signed number. So we can represent -7 to +7 with the three bits know as the magnitude and the fourth bit as the sign bit.


Value Sign 4 2 1
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
-0 1 0 0 0
-1 1 0 0 1
-2 1 0 1 0
-3 1 0 1 1
-4 1 1 0 0
-5 1 1 0 1
-6 1 1 1 0
-7 1 1 1 1

Notice anything odd about this arrangement? Look closely, there are two zero values. Zero and negative zero. Who ever heard of negative zero? Sign magnitude presents it’s own issues. A program or hardware would have to check for two values of zero if this was implemented in our microprocessor. So what can we do about this? How about flipping the bits and using one’s complements. This too has it’s own issues. The issues with negative numbers is solved by something called two’s-complement. I found a Computerphile video that I think gives one of the best explanations available. Watch the video to learn more about binary math and negative numbers:


Now I am sure you have a good grasp on the problems and solutions to binary mathematics. I’ll leave you with this: How can we modify our multi-bit adder for use in both addition and subtraction? I’ll show you my solution next time. Until then, play around with your own ideas in logisim and try to build an adder/subtractor circuit using 2’s-complement.


Newsletter Powered By : XYZScripts.com