You may have heard the term “memory” used when referring to your computer. You also may have wondered what exactly it means. In this class, you are going to be building memory that you will use in your computer. The focus of this reading is to detail the abstraction of what memory is, and in class, we will dive deeper into the details of how to implement it. Think of this reading as providing details for the client's or user's view of memory, and what we will do in class and in the projects is focus on the implementator's view.
In this course, we will be talking about a specific type of memory known as Random Access Memory or RAM. RAM is used for data storage for programs and is constantly being read from and written to by the Central Processing Unit (CPU). RAM is different from but related to other types of storage, such as caches, disks, SSDs, etc. You don't need to worry how RAM is different from these other storage mechanisms. We just point it out so that you know in the future, when you hear the term RAM, you've actually spent some time learning about and implementing it.
The way we interact with memory is almost exactly the same as the way we interact with an array. There are several sequential slots for storing data at different indices, or addresses, and we can read or write data to them in any order. The fact that we can access the slots in any order is why it is called random access memory.
Addresses are the name we give to the indices of memory. That is, we specify a slot in memory to interact with by providing an address to the memory chip. This address is a fixed width and only refers to one slot in memory
In most computers, the length of the addresses is one byte, equivalent to eight bits. In our computer, we will be interacting with memory that uses sixteen bits in each slot. This is because it simplifies the memory functionality we have to implement.
Just like everything in hardware, there is a limit to how much memory we can store in our computer. The theoretical limit of how much memory we can have is determined by the address width. Since each address is unique, the number of addresses we can represent with our width is the maximum number of slots we can have for data (since each slot will need its own address).
Remember the formula used to determine how many different values a binary number with N bits has? The same idea is relevant here. For an address width of N bits, we can have 2N slots in our memory. Note that this is the theoretical limit—that is, we can have up to 2N slots in memory. In many computers, the number of possible addresses is often far larger than the size of memory we would use, but we will not worry about those details in this course.
Note that the address width is not the same as the slot width. That is, we could have an address width of two bits (four addresses), and a slot width of sixteen bits. The address width determines the number of slots we have, but it doesn't impose limitations on how many bits are used to store the data in each of those slots.
Let's walk through an example of what memory looks like to make some of the concepts we've mentioned more concrete. For our example, addresses will be three bits wide, and the data stored at each address will be four bits wide. If our address is three bits wide, that means we have 23 = 8 different address slots for data in our memory example. Remember these parameters are not the same as the ones we are using in the computer we are building.
Let's say our memory starts out looking like the following:
| Address | Value in Memory |
|---|---|
0b000 |
0b1000 |
0b001 |
0b0110 |
0b010 |
0b0000 |
0b011 |
0b1101 |
0b100 |
0b0001 |
0b101 |
0b0110 |
0b110 |
0b1010 |
0b111 |
0b1100 |
If we access the value memory[3], we are asking for the value that is stored in memory at address 3 (0b011). This would correspond to the value 0b1101.
We might also want to update a value in memory. If we perform the update memory[6] = 9, then our updated memory would look as follows:
| Address | Value in Memory |
|---|---|
0b000 |
0b1000 |
0b001 |
0b0110 |
0b010 |
0b0000 |
0b011 |
0b1101 |
0b100 |
0b0001 |
0b101 |
0b0110 |
0b110 |
0b1001 (Changed here) |
0b111 |
0b1100 |
The takeaway here is that an abstraction of memory works just like an array. The difference is that we use addresses to refer to the slots in memory, which have a fixed width.
The last thing we will explore is this notion of blocks within memory. Oftentimes, it helps to think of memory in different “chunks”, or what we will refer to as blocks. We will use this notion of blocks to help us build our memory chip.
For our purposes, when we divide memory into blocks, they will always be the same size, and that size must be a power of 2. The reason they need to be a power of 2 is that our overall memory size is going to be a power of 2 (remember that for N width addresses, the size of our memory is 2N). If our block size is also a power of 2, it means we can evenly divide up memory into blocks without overlaps or extra space.
For example, suppose our address width is eight, which means our memory size is 28 = 256 slots. Let's say we choose a block size of 64 slots. That means we have 256 รท 64 = 4 blocks, broken down as follows:
| Block Number | Address Range |
|---|---|
0 |
0-63 |
1 |
64-127 |
2 |
128-191 |
3 |
192-255 |
Given any address, we can easily find its block number and its index within a block. Let's look at the above table again, but this time using binary instead of decimal:
| Block Number | Address range |
|---|---|
0b00 |
0b00000000-00111111 |
0b01 |
0b01000000-01111111 |
0b10 |
0b10000000-10111111 |
0b11 |
0b11000000-11111111 |
Notice how the address ranges in binary look quite similar. For each block, the lower address and the upper address are the same except for the two most significant bits. Also, notice how the two most significant bits correspond to the block number. The rest of the bits tell us which of the 64 slots we are referring to within that block.
This can be generally broken down as follows: Given an address width of N and a block size of B, the N - log2(B) most significant bits correspond to the block number, and the log2(B) least significant bits of the address (or the rest of the bits) indicate which of the B slots we are referring to within that block.
In our example, N = 8 and B = 64. log2(B) = log2(64) = 6. This means the N - B = 8 - 6 = 2 most significant bits correspond to the block number, and the log2(B) = 6 least significant bits indicate which slot within the block we are referring to. This is exactly what we observed in the table above.
In lecture, we will begin to talk about how we will implement memory in our computer, which will rely heavily on blocking to make the task more manageable. Once we have memory built, we will start to tie everything we've done so far together by implementing the CPU.