Overview: How the execution scheduler prioritizes critical slice instructions to launch memory requests earlier, why naive priority causes CPU deadlocks, and how the ROB-head liveness rule guarantees forward progress.
| Scheduling Step | Where It Runs | Selection Rule | Why It Is Critical |
|---|---|---|---|
| Step 1: ROB-Head Progress | execute_instruction() |
If the instruction at the head of the ROB is ready, issue it first unconditionally. | Eliminates pipeline deadlock: guarantees the ROB head can retire so the window never freezes. |
| Step 2: Critical Priority Issue | execute_instruction() |
Issues ready instructions with is_critical == true up to remaining execution width. |
Calculates delinquent load addresses as early as possible. |
| Step 3: Non-Critical Issue | execute_instruction() |
Fills any remaining issue slots with non-critical instructions in program order. | Maximizes execution bandwidth and instruction-level parallelism. |
"The actual performance gain in CRISP happens in the execution stage (execute_instruction()), where the out-of-order core decides which ready instructions to issue to execution units.
In standard ChampSim, the scheduler simply issues the oldest ready instructions in program order. In CRISP, we separate ready instructions into two groups: ready critical instructions and ready non-critical instructions.
However, simply prioritizing critical instructions creates a dangerous correctness bug: pipeline deadlock. Because out-of-order processors must commit instructions in strict program order from the head of the Reorder Buffer, if the instruction at the head of the ROB is not marked critical, and the CPU keeps choosing critical instructions behind it, the ROB head will starve. It will never execute, it will never retire, the ROB will fill to capacity, and the processor hangs permanently.
To eliminate this deadlock, I implemented a strict three-step scheduling policy:
First, we check the instruction at the head of the ROB. If it is ready to execute, we unconditionally issue it first. This guarantees forward progress under all conditions.
Second, we issue all ready critical instructions up to the remaining execution width.
Third, any remaining execution slots in that cycle are filled by non-critical instructions.
This policy gives critical address calculations priority while ensuring the core never starves or locks up."
Understanding why an out-of-order scheduler can deadlock is one of the most critical concepts in microarchitecture:
Scenario without Step 1 Guarantee (BROKEN):
ROB Head: Ordinary Instruction (Ready, but non-critical)
ROB Slot 5: Critical Instruction (Ready)
ROB Slot 6: Critical Instruction (Ready)
Cycle 1: Scheduler picks Slot 5 & 6 (Criticals prioritized)
Cycle 2: More critical instructions become ready -> Scheduler picks them!
...
ROB Head NEVER gets issued!
ROB Head cannot retire -> ROB fills to 256 entries -> Dispatch stops -> DEADLOCK!
CRISP's three-step policy prevents this scenario entirely:
Each Execution Cycle:
│
▼
STEP 1: Check ROB Head
Is instruction at ROB.front() ready?
├── YES ──► Issue ROB Head immediately (Slot consumed)
└── NO ──► Continue to Step 2
│
▼
STEP 2: Issue Ready Criticals
Collect instructions where is_critical == true and ready
Issue up to remaining EXEC_WIDTH slots
│
▼
STEP 3: Fill Remaining Bandwidth
If execution slots remain:
Issue ready non-critical instructions in program order
│
▼
Cycle Complete (All issued instructions dispatched to functional units)
In a 6-way execution core (which can issue up to 6 instructions per cycle):
Answer: "The ROB head guarantee consumes at most 1 issue slot out of the CPU's total execution width (e.g., 6 instructions per cycle in our core). That leaves 5 full execution slots each cycle exclusively for critical instructions. Issuing the ROB head as soon as it is ready actually clears the front of the buffer faster, which prevents dispatch from stalling and creates more space for critical instructions to enter the pipeline."
Answer: "If multiple critical instructions are ready, they are selected in program order (oldest first). This ensures that earlier steps in the address calculation chain complete before dependent downstream instructions."
Answer: "No. CRISP does not inject speculative instructions, helper threads, or redundant computations. The total number of instructions executed is identical to the baseline processor. All performance gains come entirely from reordering when instructions execute so that memory loads begin earlier."