Apparatus and method for instruction fetching using a multi-port instruction cache directory

• US 5,918,044 A
• Filed: 10/31/1996
• Issued: 06/29/1999
• Est. Priority Date: 10/31/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Levitan, David Stephen, Muhich, John Stephen
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): TZENG, FRED
• Application Number:
  US08/741,465
• Time in Patent Office: 971 Days
• Field of Search: 711/125, 711/128, 395/382, 395/581, 395/585, 395/586, 395/800.23, 395/587, 395/376, 395/582, 395/383, 364/261.7, 364/938
• US Class Current: 712/235
• CPC Class Codes: G06F 12/0853 Cache with multiport tag or data arrays
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/1054 the data cache being concurrently physically addressed
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

In an instruction fetch unit for an information handling system which decodes instructions, calculates target addresses of multiple branch instructions, and resolves multiple branch instructions in parallel instead of sequentially, the critical path through a multiple way set associative instruction cache is through a directory and compare circuit which selects which way instructions will be retrieved. This patch is known as the late select path. A multi-ported effective address (EA) directory is provided and is accessed prior to selection of a fetch address which fetches the next set of instructions from the cache. In this manner, the time required for the late select path can be reduced.

Claims

1. In an information handling system, an apparatus for fetching instructions comprising:

a cache for storing first and second sets of addressable instructions;

instruction queues operably coupled to said cache for storing a set of fetched instructions;

fetch address selector operably coupled to said cache for selecting a fetch address and for providing said fetch address to said cache to fetch a new set of instructions;

at least one branch target calculator operably coupled to said instruction queues and to said fetch address selector for determining, in parallel, if instructions in said instruction queues are branch instructions and for providing, in parallel, target addresses of the branch instructions to said fetch address selector so that said fetch address selector can provide said cache with one of a plurality of target addresses as said fetch address; and

a directory operatively associated with said cache for selecting one of said sets from which said instructions are fetched, said directory including a plurality of input ports coupled to said branch target calculator for inputting said plurality of target addresses in parallel with said fetch address selector such that said directory is accessed prior to said fetch address selector selecting said fetch address.

2. The apparatus, as recited in claim 1, further comprising branch resolution logic operably coupled to said fetch address selector for resolving or predicting said branch instructions.

3. The apparatus, as recited in claim 2, wherein said branch target calculator determines if an instruction in said instruction queue is a branch instruction and provides a target address before or during the time in which said branch resolution logic resolves said branch instructions such that said branch resolution logic resolves a plurality of said branch instructions in parallel.

4. The apparatus, as recited in claim 2, wherein said branch resolution logic includes prediction means for predicting the outcomes of said branch instructions.

5. The apparatus, as recited in claim 4, wherein said prediction means includes a branch history table including BHT entries.

6. The apparatus, as recited in claim 5, wherein said branch history table is operably coupled to said instruction queues for providing said instruction queues with said BHT entries at the same time that said set of fetched instructions are stored in said instruction queues.

7. The apparatus, as recited in claim 2, further comprising a branch queue operably coupled to said branch target calculator for receiving said target addresses, operably coupled to said instruction queues for receiving the addresses of said set of fetched instructions stored in said instruction queues, and operably coupled to said fetch address selector for providing said fetch address selector and said directory with at least one resolved address.

8. The apparatus, as recited in claim 7, further comprising a sequential address calculator for providing a sequential address to said fetch address selector and to said directory.

9. The apparatus, as recited in claim 8, wherein each of said instruction queues store an address for said instruction stored in said instruction queue.

10. The apparatus, as recited in claim 9, wherein said sequential address calculator is operably coupled to said instruction queues for providing the addresses of said instructions stored in said instruction queues.

11. The apparatus, as recited in claim 8, further comprising an interrupt address generator for providing an interrupt address to said fetch address selector and to said directory.

12. The apparatus, as recited in claim 11, wherein said branch resolution logic includes means for prioritizing said target addresses, each said resolved address, said sequential address, and said interrupt address provided to said fetch address selector from a highest priority address to a lowest priority address such that said fetch address selector selects said highest priority address as said fetch address.

13. The apparatus, as recited in claim 1, wherein said fetch address selector comprises a multiplexor.

14. The apparatus, as recited in claim 1, wherein said cache is a set associative cache.

15. The apparatus, as recited in claim 1, wherein said directory is an effective address directory.

16. A method for fetching instructions in an information handling system including a cache for storing first and second sets of addressable instructions, a directory operatively associated with the cache for selecting one of the sets from which the instructions are fetched, instruction queues operatively coupled to the cache for storing a set of fetched instructions, at least one branch target calculator operatively coupled to the instruction queues and a fetch address selector, said method comprising the steps of:

determining in parallel, in the branch target calculator, if the instructions in the instruction queues are branch instructions;

calculating in parallel, in the branch target calculator, target addresses of the branch instructions;

selecting, in the fetch address selector, a fetch address for fetching a new set of instructions from the cache; and

accessing the directory with the target addresses prior to the fetch address selector selecting the fetch address.

17. The method, as recited in claim 16, further comprising the steps of:

providing branch resolution logic operably coupled to the fetch address selector; and

resolving, in the branch resolution logic, the branch instructions.

18. The method, as recited in claim 17, wherein said determining and calculating steps are performed either before or during the time in which said resolving step is performed.

19. The method, as recited in claim 17, wherein said resolving step further includes the step of predicting the outcomes of the branch instructions.

20. The method, as recited in claim 19, wherein said predicting step includes the step of providing a branch history table including BHT entries.

21. The method, as recited in claim 20, wherein said step of providing a branch history table further includes the step of storing said BHT entries in the instruction queues at the same time that the set of fetched instructions are stored in the instruction queues.

22. The method, as recited in claim 17, further comprising the step of providing a branch queue coupled to each branch target calculator, the instruction queues, and the fetch address selector.

23. The method, as recited in claim 22, further comprising the step of receiving, in the branch queue, the target addresses and the addresses of the set of instructions stored in the instruction queues.

24. The method, as recited in claim 23, further comprising the steps of:

saving, in the branch queue for each predicted branch outcome, the target address of the set of fetched instructions stored in the instruction queues if the predicted branch outcome is taken; and

providing, in the case of a misprediction of a branch outcome, at least one resolved branch address to the fetch address selector wherein each of said resolved branch addresses are said addresses saved in the branch queue.

25. The method, as recited in claim 24, further comprising the step of providing a sequential address to the fetch address selector and the directory.

26. The method, as recited in claim 25, further comprising the step of providing an interrupt address to the fetch address selector and the directory.

27. The method, as recited in claim 26, further comprising the step of prioritizing, in the branch resolution logic, the target addresses, each resolved address, the sequential address and the interrupt address from a highest priority address to a lowest priority address.

28. The method, as recited in claim 27, wherein said selecting step further includes the step of selecting the highest priority address as the fetch address.

29. The method, as recited in claim 16, wherein the cache is a set associative cache.

30. The method, as recited in claim 16, wherein the directory is an effective address directory.

31. A method for fetching a new instruction from a cache for storing first and second sets of instructions to be fetched in an information handling system operating at predetermined number of cycles per second and including a directory operatively associated with the cache for selecting one of the sets from which the instructions are fetched, said method comprising the steps of:

performing the following steps in a first portion of the cycle to determine a fetch address;

a) decoding a current instruction to determine if the current instruction is a branch instruction;

b) if the current instruction is a branch instruction, performing the following steps in parallel;

i) calculating the target address of the branch instruction, and

ii) resolving the branch instruction;

c) selecting a fetch address for fetching a new instruction from the cache; and

d) accessing the directory with the target address prior to completing the resolution of the branch instruction and selecting a fetch address; and

fetching, using the fetch address, the new instruction from the cache during a second portion of the cycle.

32. In an information handling system, an apparatus for fetching instructions comprising:

(a) a cache for storing first and second sets of addressable instructions, such an instruction having a fetch address for fetching the instruction from the cache;

(b) first and second instruction queues ("IQs") operably coupled to the cache for storing fetched instructions;

(c) first and second branch target calculators ("BTCs") operably coupled to a corresponding one of the IQs, for calculating respective first and second branch instruction target addresses;

(d) a fetch address selector ("FAS"), operably coupled to the cache and the BTCs, for providing to the cache a selected fetch address in response to the branch instruction target addresses; and

(e) a directory operatively associated with said cache for selecting one of said sets from which instructions are fetched, said directory including a plurality of input ports coupled to said first and second BTCs for inputting said first and second branch instruction target addresses in parallel with said FAS such that said directory is accessed prior to said FAS selecting said fetch address.

33. The system of claim 32, wherein the BTCs calculate the target addresses and the FAS provides the fetch address during a single processing cycle of the system.

34. The system of claim 32, wherein said cache is a set associative cache.

35. The system of claim 32, wherein said directory is an effective address directory.

36. In an information handling system, an apparatus for fetching instructions comprising:

(a) a cache for storing first and second sets of addressable instructions, such an instruction having a fetch address for fetching the instruction from the cache;

(b) a fetch address selector ("FAS"), operably coupled to the cache, for providing to the cache a selected fetch address from a plurality of potential fetch addresses; and

(c) a directory operatively associated with said cache for selecting one of said sets from which instructions are fetched, said directory including a plurality of input ports for inputting said plurality of potential fetch addresses such that said directory is accessed prior to said FAS selecting said fetch address.

37. The system of claim 36, further including first and second branch target calculators ("BTCs") for calculating respective first and second branch target addresses for fetched instructions wherein said potential fetch addresses include said first and second branch target addresses.

38. The system of claim 37, wherein the BTCs calculate the target addresses and the FAS provides the fetch address during a single processing cycle of the system.

39. The system of claim 36, wherein said cache is a set associative cache.

40. The system of claim 36, wherein said directory is an effective address directory.

41. A method for fetching instructions in an information handling system, said method comprising the steps of:

storing first and second sets of addressable instructions in a cache wherein such an instruction has a fetch address for fetching the instruction from a cache;

providing to the cache a selected fetch address from a plurality of potential fetch addresses; and

inputting the plurality of potential fetch addresses into a directory for selecting one of the sets from which instructions are fetched such that the directory is accessed prior to providing the cache a selected fetch address.