Reliable branch predictions for real-time applications

Details Reliable branch predictions for real-time applications Reliable branch predictions for real-time applications

1998-09-11

2002-08-06

Maung, Zarni (Department: 2154)

Electrical computers and digital processing systems: processing

Processing control

Branching

C712S233000, C712S235000

Reexamination Certificate

active

06430682

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to computer systems, and more particularly to branch prediction in instruction processing.
BACKGROUND OF THE INVENTION
In computer design, engineers are constantly looking for new approaches to increase the effective rate at which the processor unit executes instructions. One method of increasing the effective rate of processor execution is by prefetching. Prefetching can be used to bring in information from the memory into an instruction cache before the processor needs the information.
Primarily, there are two different types of prefetching, instruction prefetching and data prefetching. Prefetching instruction lines from memory to cache reduces the number of instruction cache misses. Data prefetching reduces data cache misses by exploiting the program access pattern for data.
There has been considerable research done in the area of data-prefetching, in part because this kind of prefetching is in high demand and usually fairly simple to implement. However, the idea of prefetching instructions has not been as extensively researched, due to its complexity. With the advent of superscalar machines, this type of prefetching is needed.
In designing a processor which utilizes prefetching, the designer has to take into consideration several issues. It is possible for data or instructions to be prefetched into the cache that will never be used by the processor. If the processor accesses memory in a sequential manner, this problem will not occur. However, if branches, jumps, and function calls are taken into consideration, prefetched data/instructions may not be used if the program execution path is different from the instruction prefetch path. If the data is prefetched too early, it can become stale before it is referenced, requiring refetching of the data, thus, increasing memory traffic.
In next line prefetching, the cache line that is next to the current cache line is prefetched automatically if it is not already in the cache. This method is simple to implement, in that a lot of additional logic is not required. Performance is fairly good if branches frequently execute the fallthrough path. However, this method is not very useful in the case where a branch is taken. In unconditional jumps and procedure calls, next line prefetching causes an increase in memory traffic and is not likely to prefetch the cache lines that are going to be used. However, because of the ease of implementation and small cost, the next line prefetching scheme can be found in many microprocessors.
SUMMARY OF THE INVENTION
The invention provides branch execution mechanisms that efficiently manage processing and hardware resources for computer processing. The invention presents methods that increase processor performance and improve the worst-case time bounds of tasks on computer processors with branch execution.
In one embodiment, a branch execution method is disclosed for reducing the execution time of certain conditional branches effectively converting them into jump instructions. A conditional branch instruction suitable for this embodiment is divided into conditional-test and execute-branch steps in which the conditional branch instruction is pre-conditioned to take or not-take the branch according to the results of the conditional test step.
Advantageously, the branch execution method minimizes overhead through the use of a one bit entry for each conditional branch instruction wherein entries are indexed by the addresses of active pre-conditioned branch instructions.
In an another embodiment, the branch execution minimizes overhead through the use of a one bit entry for each conditional branch instruction wherein entries are a fixed part of the architecture and are indexed by the location of each entry in a register.


REFERENCES:
patent: 4991080 (1991-02-01), Emma et al.
patent: 5210831 (1993-05-01), Emma et al.
patent: 5247627 (1993-09-01), Murakami et al.
patent: 5371862 (1994-12-01), Suzuki et al.
patent: 5408620 (1995-04-01), Asakawa et al.
patent: 5418917 (1995-05-01), Hiraoka et al.
patent: 5664135 (1997-09-01), Schlansker et al.
patent: 5748936 (1998-05-01), Karp et al.
patent: 5815695 (1998-09-01), James et al.
patent: 5907714 (1999-05-01), Doutaud et al.
patent: 5949995 (1999-09-01), Freeman et al.
Tom R. Halfhill, “Beyond Pentium II”, BYTE, pp. 80-83, 86, Dec., 1997.

Affiliated with

Also associated with

Rating

Reliable branch predictions for real-time applications does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reliable branch predictions for real-time applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reliable branch predictions for real-time applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2966417