×

Multiple branch analyzer for prefetching cache lines

  • US 4,943,908 A
  • Filed: 12/02/1987
  • Issued: 07/24/1990
  • Est. Priority Date: 12/02/1987
  • Status: Expired due to Fees
First Claim
Patent Images

1. In a computer with a processor, a main memory, said main memory storing a plurality of lines of instructions, and a cache, said cache temporarily storing instruction lines received from said main memory, apparatus for prefetching instruction lines from said main memory to said cache, comprising:

  • a branch history table having a plurality of entries, each said entry corresponding to an instruction line in said main memory and comprising addresses of all branches predicted as taken in said corresponding line;

    means connected to said branch history table for determining from the branch history table entry for a current instruction line in use by, or in queue for use by, the processor and from an address of an entry point into said current line by the processor, a next instruction line to be used by the processor and an entry point into said next line; and

    means responsive to said determination of the next instruction line for prefetching said next line from said main memory into said cache in the event said next line is not already in said cache;

    said determining means comprising;

    entry register means for receiving and storing initially the entry point address for said current line;

    map table means receiving the current address stored in said entry register means and the taken branch addresses from the branch history table entry for said current line, and outputting(a) in the event there is no taken branch in said current line following the address stored in said entry register means, the address of the next sequential instruction line in said main memory, and(b) in the event the taken branch that follows the address stored in said entry register means has a target address in said current line, the address of the next taken branch that will be encountered in said current line after taking said taken branch which follows said stored address, or the address of the next sequential instruction line in said main memory if no other taken branches will be encountered in said current line after taking said taken branch which follows said stored address, and(c) in the event the taken branch that follows the address stored in said entry register means has a target address outside said current line, said target address; and

    means for updating the address stored in said entry register means in the event that said map table means outputs a next taken branch address.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×