Lecture 2 (8/31/2009) — Locality Mechanisms

Lecture 2 Slides

Lecture 2 Discussion

()

Review of what a computer looks like

The relevant components of a computer are:

  • ALU
  • Register File
  • Load Store Unit (LSU)
  • Hierarchy of memories - To a programmer the memory hierarchy is invisible.The purpose of having this hierarchy in place is to give the programmer the illusion of a large, low latency storage.

What happens when a memory access is made in a program?

  • The LSU gets the Virtual Address(V.A.) from the program. To get the physical address (P.A.) translation, normally a look up of the Page Table would have to be done. Since the Page Table sits in the main memory, it costs to access it and it usually takes multiple accesses to the Page Table to get the complete translation. Therefore, a few translations(in the form of Page Table Entries(PTE’s) ) are cached in the Translation Look-aside Buffer (TLB), located inside the LSU.
  • If the VA in question causes a hit in the TLB, we get the corresponding PTE. The PTE is further checked for access permissions and in the event of positive permissions, we progress to the step of accessing the first level of the memory hierarchy. If permission is not granted, a protection fault results.
  • With the physical address in hand, the L1 cache is accessed. If there is a miss, the access request passes on to the next lower level, the L2 cache, and so on until there is a hit. This does mean though that the indexing, tag matching and permission checking on the L1 cache cannot start until the V.A. to P.A. translation is complete, adding on latency to the memory access. An alternative is to have a virtual cache, which can be indexed using the V.A. itself. This introduces the problem of guaranteeing uniqueness, wherein the same V.A. might translate to two different physical locations in two different processes. The simplest workaround of flushing the caches when a process is switched out has the obvious disadvantage of a performance hit. Another problem is that different processes might use different V.A.’s to refer to the same memory location. This would lead to duplication in a virtual cache, which would not only mean wastage but also a lack of coherence amongst different processes. A more elegant solution is to have a virtually addresses, physically tagged cache. This utilises the fact that the page offset part of the V.A. doesn’t need to be translated to get the P.A. Therefore, the cache index and offset bits can be formed from these untranslated bits.
  • The least significant bits of the address indicate the byte offset within the cache line/way. This helps in exploiting spatial locality, which is present to a fair degree in most programs. Spatial locality means that when a memory location is accessed, it is likely that locations close by will be accessed too (and soon ??). However, there might be certain access patterns which would benefit from having the “offset” bits designated differently in the address.
  • If the V.A.’s translation is not present in the TLB, a Page Table walk is done, either by the software (OS) or the hardware. If the corresponding translation is not present in the Page Table, a page fault exception is raised and a page is allocated.

Where does I/O sit?

In modern computers, I/O’s are generally memory mapped. The gigantic I/O space is mapped to a small region of memory, through virtual addressing.

Locality through Reservation Station, Bypass Network, Caches and Registers

While it is clear that registers and caches help in keeping things “local”, why do the Reservation Station or the Bypass Network matter? Both the Reservation Station and Bypass network try to re-use a computed value instead of writing it back to the register file. The Reservation Station also keeps recent instructions in it so that it does not have to go to the instruction cache to fetch the instruction again when the instruction is ready to go.

The Advantages of being “Local”

Locality improves Latency The widening processor-memory latency gap means that the cost of accessing memory can range from a few to hundreds of cycles. Registers can generally be accessed in a single cycle. ( But isn’t that due to the physical properties of memory, making the access slow, rather than locality itself? I guess my question is that how is locality the reason registers are faster to access).

Locality improves Power A 64bit floating point operation is very computation and power intensive. But transmitting the result of the operation consumes much more power. So it makes sense to compute and consume the result locally. The problem is exacerbated if power hungry repeaters are used to reduce the latency of the communication link.

Locality improves Bandwidth If things are not kept “local”, it means that global wires need to be used for communication. Such wires are necessarily thicker so that their huge length doesn’t result in high resistance and hence high latency. This increases their minimum pitch and hence a given area can fit a lesser number of wires. A decrease in bandwidth is a direct result of the increased pitch.

Register versus Memory(SRAM/DRAM)(How does this tie in with the concept of locality?)

The fundamental difference between registers and memory is their technology. Registers are made out of regular logic gates while SRAM/DRAM is constructed from cells consisting of a special configuration of transistors. Registers are faster (and more reliable? Less prone to bit flips?) but cost more in terms of area and power. Memory on the other hand is slower(specifically talking about DRAM??) but costs less in terms of area. That said, a lot of the registers in today’s processors are really SRAM.

Cache Aware Programming

Started discussing matrix multiplication and how the plain vanilla 3-loop algorithm can be modified to take advantage of locality. More details in Lecture 3.