3
\$\begingroup\$

A processor is working at 100 MHz. The program memory interfaced to it can work only at 25 MHz maximum. Is there anyway we can fetch an instruction from it in one clock cycle of the processor ? I read that instruction cache can be used for this purpose. How instruction cache actually makes instruction fetch faster, while we cannot increase the speed of the slow memory ?

\$\endgroup\$
  • 1
    \$\begingroup\$ a cache is only part of it, the prefetch and prefetch buffer is a factor. cache simply makes some of the information faster for repetitive or linear accesses. but your processor still stalls if you only fetch one instruction at at time even with a cache (depending on where the cache is, busses, etc). \$\endgroup\$ – old_timer Dec 13 '17 at 19:32
1
\$\begingroup\$

Processors have a fetch/execute pipeline which fetches, decodes and executes instructions. Different processors have different number of pipeline levels. A three stage pipe line is shown. Each instruction takes three clock cycles to execute, but because the stages can be paralleled, the net execution is 1 clock/instruction for the processor.

Fetch/Execute Pipeline

Ideally, we’d like to have programs execute as fast as possible. But this is not cost effective. A typical memory hierarchy is shown.

Memory Hierarchy

Fastest memory is registers. If you have many general purpose registers, the program can run from the registers.

Locality means most instruction fetches will be sequential. Only time it is not is when a branch is encountered. The present contents of the 3-stage pipeline must be trashed, so the new instructions can be loaded. If the branch is small, contents may be in registers. We loose 3 clock cycles, while the new instruction is fetched from the registers. The processor stalls until there is a new instruction to execute. Additional clock cycles are inserted.

If it is not in the registers, the address is sent to the cache. On-chip cache is a small amount of high speed memory. If it is a hit. On-chip cache is 1 or 2 clock cycles to access the next instruction. Still 1'ish clock cycles/instruction.

We skip multiple levels of cache. Just another level of buffering. No real point at 100MHz. L2 caches are just small amounts of fast SRAM.

If it is a miss, cache must request instruction from main memory. Main memory is a large amount of cheap memory. At 25MHz, each instruction would require 4 clock cycles to fetch. Instruction is read into cache and processor. 4 clocks to fetch and 3 to execute.

Locality means that the processor will also need the next instruction. The memory controller is set up to read a full block of adjacent locations from DRAM to the cache. The processor program counter will request the next location, cache miss, but the memory controller is already fetching this 2nd location from main memory, so overall delay is lower.

Finally, if program is not in main memory, it must be loaded into DRAM from storage. Big performance hit, as storage is sloooooow...

Ultimately, 1 clock cycle / instruction depends on the program and compiler / programmer.


Edit...

Cache has to be loaded. Typically, DRAM controllers have burst capacity, where first read takes 4 cycles, but the initial DRAM address is already supplied and subsequent reads take less than 4, say 2 cycles. A three-stage pipeline processor has to wait 7 clock cycles to get the first instruction (worse case scenario - branch, trash pipeline - cache miss, fetch from DRAM), but 2 or 3 for the next instruction that is already on the way to the cache.

A lot of programs are not sequential but loops or reused subroutines, where cache (and levels of cache) can improve performance. If a program was sequential, then cache would have no purpose. Processor would run at speed of DRAM read access.

No pipelining, sequential code, no burst capability, then your processor runs at 25MHz, with 3 wait states inserted into each instruction. Pipelining, loopey code (that fits in 100MHz registers or 100MHz cache) and burst DRAM read capability means the processor runs at 100MHz and 1 clock cycle/instruction.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ So if cache is working at 100 MHz or so, processor can fetch instructions in one cycle from it ? It means that the cache has already stored more than one instructions in it, from memory at 4 cycles/instruction, before the processor even starts fetching instructions ? \$\endgroup\$ – Meenie Leis Dec 13 '17 at 13:03
  • \$\begingroup\$ But if cache also needs 4 cycles to fetch one instruction from memory, how is it useful in the end? If there are 4 instructions, It will take 16 cycles to copy to cache, eventhough processor can fetch one instruction in one cycle from the cache. \$\endgroup\$ – Meenie Leis Dec 13 '17 at 13:08
  • 2
    \$\begingroup\$ Correct. The benefit applies next time you execute the same instructions when they are still in the cache and can be fetched in one cycle. There are also some types of memory where it takes (e.g.) 4 cycles to fetch - but you get 4 or more instructions back at once. Which can be added to the cache. \$\endgroup\$ – pjc50 Dec 13 '17 at 15:46
  • \$\begingroup\$ "but you get 4 or more instructions back at once" - Is that called burst mode or something ? :-) @pjc50 \$\endgroup\$ – Meenie Leis Dec 13 '17 at 17:58
  • 1
    \$\begingroup\$ Yes, exactly that - DRAM burst mode. \$\endgroup\$ – pjc50 Dec 13 '17 at 18:02
1
\$\begingroup\$

In the words of Father Ted, the instruction cache is small but the memory is far away.

The 25Mhz memory will take at least four of the 100MHz processor's cycles. The instruction cache does not actually make the access to main memory faster, but it will return values immediately rather than after a delay. The advantage of this is on the second and subsequent time the processor attempts to access a particular address. Such as when executing a loop.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ So if it is a program without any loop ? If the program is just executing sequentially from top to bottom straightaway. No advantage will be there by using cache ? \$\endgroup\$ – Meenie Leis Dec 12 '17 at 19:17
  • 3
    \$\begingroup\$ @MeenieLeis correct, but in practice how many programs simply execute sequentially with no branching or loops? Very few that do anything useful. \$\endgroup\$ – Tom Carpenter Dec 12 '17 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.