A Two-Level Dynamic Chrono-Scheduling Algorithm

Abstract

We propose a dynamic instruction scheduler that does not need any kind of wakeup logic, as all the instructions are “programmed” on issue stage to be executed in pre-calculated cycles. The scheduler is composed of two similar levels, each one composed of simple “stations”, where the timing information is recorded. The first level is aimed to the group of instructions whose timing information cannot be calculated at issue (for example, those instructions whose latency is not predictable). The second level contains simple “stations” for the instructions whose execution and write back cycle have been already calculated. The key idea of this scheduler is to extract and record all possible information about the future execution of an instruction during its issue, so as not to look for this information again and again during wait stages at the reservation stations. Another additional advantage is that time critical parts can be identified as instruction timing information is available, so high speed and frequency logic can be used only in these parts, while the rest of the scheduler can work at lower frequencies, therefore consuming much less power. The lack of wakeup and CAM (Content Addressable Memory) means that power consumption and latencies would be presumably reduced, frequency would probably be made higher, while CPI (clock Cycles Per Instruction) would remain approximately the same.