Programming From The Ground Up Chapter 2

Chapter 2:

Know The Concepts

1) Describe the fetch-execute cycle.

Also known as an instruction cycle or fetch-decode-execute cycle is the basic operational process of a computer. The process consists of the computer retrieving a program instruction from its memory; it then determines what actions the instruction contains. Lastly, it will execute the cycle. The name “fetch-decode-execute” is the easiest naming to understand as it is literally fetching the instruction, decoding what the instruction holds and then executing the instruction.

https://en.wikipedia.org/wiki/Instruction_cycle

2) What is a register? How would computation be more difficult without registers?

A register is special, high-speed memory locations in the processor itself; the two kinds of registers are general registers and special-purpose registers. General-purpose registers contain the main actions such as addition, subtraction, multiplication, comparison, and other operations. There are very few of these general-purpose registers because when an action is complete the information will transport itself back to memory. Special-purpose registers have very specific purposes.

Computation would be much more difficult without the use of registers because the CPU would be required to strictly use memory to run actions. This creates the problem of the CPU having to check the memory space for data which reduces performance due to many more actions taking place constantly.

3) How do you represent numbers larger than 255?

By simply using a combination of bytes to represent larger numbers we can represent numbers larger than 255. Two bytes can represent 0-65536, four bytes 0-4294967295. Computers will stick bytes together for us for numbers up to 4 bytes long and 4 bytes is the default for the scenarios from the book.

4) How big are the registers on the machines we will be using?

The registers on the machine are each 4 bytes long. The x86 processors have four-byte words so it is most natural for computers with this processor to do computations four bytes at a time.
*The size of a typical register is called a computer’s word size

5) How does a computer know how to interpret a given byte or set of bytes of memory?

The Computer can’t tell the difference between a value that is an address, number, ASCII code, or a any other value purpose. A number becomes the intended or unintended purpose when it is displayed or there is an attempt to display it. For example an ASCII code value is nothing but a value until we tell it to display the given value as ASCII. Another example is that a value only becomes an address (also called a pointer) when you try to look up the byte it points to. Instructions are in the same boat, the computer doesn’t even know the difference between an instruction and data since they are both stored in memory. The computer only knows the difference if the instruction pointer (a special-purpose register) points to the instruction at one point or another. So a value is only declared an instruction once the instruction pointer has pointed to it.

6) What are the addressing modes and what are they used for?

Immediate mode – the data to access is embedded in the instruction itself. So if we wanted to initialize a register to 0 we would specify immediate mode and give it the number 0. This would prevent the need to give the computer an address to read the 0 from.

Register addressing mode – The instruction contains the memory address to access instead of a memory location.

Direct addressing mode – The instruction contains the memory address to access. You would include in the instruction to load a certain register with the data at a specific address. The computer will go to that specific address and copy the contents into the chosen register.

Indexed addressing mode – The instruction contains a memory address to access, while also specifying an index register to offset that address. An example of this would be specifying address 2002 and an index register. Depending on the index register determines the offset of the address; if the index register contains the number 4, the actual address the data is loaded from would be 2006. This is beneficial because now if you have a set of numbers starting at location 2002, you can cycle between each of the numbers using an index register. This can also be accompanied by a multiplier on x86 processors. This allows you to access memory a byte at a time or a word at a time (4 bytes). If you wanted to access an entire word, your index would need to be multiplied by 4.

Indirect addressing mode – The instruction contains a register that contains a pointer to where the data should be accessed. So if we specified the %eax register and the %eax register contained the value 4, whatever value was at at memory location 4 would be used. This is similar to direct addressing except instead of using the value found in the memory we are using it to tell us where the desired value is located.

Base pointer addressing mode – Similar to indirect addressing, but you also include a number called the offset to add to the register’s value before using the final value for lookup.

7) What does the instruction pointer do?

The instruction pointer (IP) has quite a bit of different names that are commonly used such as, program counter (PC) and instruction address register (IAR). The instruction pointer does exactly what it sounds like, points to the next instruction to be executed by the processor. This register is changed by the processor while the program is executed.

Use The Concepts

1) What data would you use in an employee record? How would you lay it out in memory?

I’d create an employee record consisting of employee name, address, age, title, id number

Start of Record:

Employee’s name pointer (1 word) – start of record

Employee’s address pointer (1 word) – start of record + 4

Employee’s age (1 word) – start of record + 8

Employee’s title (1 word) – start of record + 12

Employee’s id number (1 word) – start of record + 16

2) If I had the pointer at the beginning of the employee record above, and wanted

to access a particular piece of data inside of it, what addressing mode would I

use?

I would use the indexed addressing mode with a multiplier of 4. This would allow me to use an index of 1 for +4 or 2 for +8 and so on.

3) In base pointer addressing mode, if you have a register holding the value 3122,

and an offset of 20, what address would you be trying to access?

For base pointer addressing mode we take the value and then add the offset. The end result is the address we want to access. Therefore, 3122 + 20 = 3142

4) In indexed addressing mode, if the base address is 6512, the index register has a

5, and the multiplier is 4, what address would you be trying to access?

The multiplier effects the index therefore 6512 + (5 * 4) = 6532

5) In indexed addressing mode, if the base address is 123472, the index register

has a 0, and the multiplier is 4, what address would you be trying to access?

With an index of 0 the base address is unaffected. Therefore the answer is 123472

6) In indexed addressing mode, if the base address is 9123478, the index register

has a 20, and the multiplier is 1, what address would you be trying to access?

9123478 + (20 * 1) = 9123498

Going Further

1) What are the minimum number of addressing modes needed for computation?

According to this stack-overflow comment by ElderBug the only addressing mode required is register indirect addressing. With this you can access memory, calculate any address in a register, and use it to do the accessing. It can also replace direct register operands by simply using memory instead. As well as immediate operands by constructing values with arithmetic.

https://stackoverflow.com/questions/35221379/what-is-the-minimum-number-of-addressing-modes-necessary-for-computation

2) Why include addressing modes that aren’t strictly needed?

Although they may not be needed all addressing modes have a significant use. Our person from stackoverflow ElderBug also gave us a pretty sweet rundown of each of the addressing modes. Using slightly different naming than mentioned previously but it should be obvious which is which.

  • Immediate addressing saves you a register if you just have to access a fixed variable in memory.
  • Base + offset is really useful for accessing object members : you can keep the base address in a register and access individual members with a fixed offset. No need for intermediate calculations or register to hold the member address.
  • Similarly, indexed addressing is used for accessing arrays : you can just change an index register to access any value in the array.
  • With a scale you can access multi-bytes variable (ex: int) arrays with no additional registers or calculations.
  • A combination of everything can be used to access an array member in an object, still preserving the base pointer for potential access to other members in the object.

https://stackoverflow.com/questions/35221379/what-is-the-minimum-number-of-addressing-modes-necessary-for-computation

3) Research and then describe how pipelining (or one of the other complicating factors) affects the fetch-execute cycle.

If you are familiar with linux you probably have an idea of what piping may entail. Wiki defined the term pretty great so I’ll save myself the trouble of trying.

“in computing, a pipeline, also known as a data pipeline, is a set of data processing elements connected in series, where the output of one element is the input of the next one. The elements of a pipeline are often executed in parallel or in time-sliced fashion. Some amount of buffer storage is often inserted between elements” https://en.wikipedia.org/wiki/Pipeline_(computing)

The biggest difference of a device with data pipeline capabilities and one without the ability would be the hardware. The fetch is performed while the execute is being processed and this is possible because they each use separate hardware elements. Instruction execution can also be overlapped in a pipeline which allows for CPI (cycles per instruction) of 1. Using overlap with instruction execution leads to data and branch hazards or instructions which influence later instructions in the pipeline. This leads to a much more complex system. https://cs.nyu.edu/courses/fall08/V22.0436-001/lecture18.html

4) Research and then describe the tradeoffs between fixed-length instructions and variable-length instructions.

Fixed-length instructions with a relatively uniform formatting allows for substantially simpler fetching and parsing of the instructions. Fixed-length instructions compared to typical variable length encodings tend to use fewer bits. The negatives of fixed-length instructions is likely obvious but the main idea is that you are very limited. There are many limitations such as an attempt to extend an instruction set or have a larger than possible constant.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: