FIFO Pipeline IPC with Stalls
Problem statement
Model two pipeline modules. A has a FIFO capacity of 10 instructions; B has capacity 1. Both start empty. There is one offered instruction per cycle. An instruction cannot bypass either queue.
stalled[t] is 1 when B cannot consume during cycle t and 0 otherwise. Perform these events in this exact order in each cycle:
- If B contains an instruction and is not stalled, consume it and increase the completed count.
- If B is now empty and A is not empty, move exactly one oldest instruction from A to B.
- If A now has room, admit the offered instruction into A. Otherwise reject that cycle's offer; rejected offers are not retried.
Let T be the number of cycles. Define A's IPC as admitted/T and B's IPC as completed/T. Return the exact fractions as four integers [admitted, T, completed, T], without reducing them. Do not drain the queues after the last cycle.
Function
pipelineIpc(stalled: int[]) → int[]Examples
Example 1
stalled = [0,0,0]return = [3,3,1,3]Cycle 1 admits the first instruction into A. Cycle 2 moves it to B and admits another. Cycle 3 consumes the first instruction, then transfers and admits again. A admits 3 instructions and B completes 1 in 3 cycles.
Example 2
stalled = [1,1,1,1,1,1,1,1,1,1,1,1]return = [11,12,0,12]B fills on cycle 2 and never consumes. A fills its 10 slots by cycle 11; the offer in cycle 12 is rejected. In total 11 instructions are admitted and none completes.
Example 3
stalled = [0,0,1,0]return = [4,4,1,4]The stall in cycle 3 keeps B occupied, while A still has room to accept. B consumes once in cycle 4. All four offers fit in A over the window.
Constraints
1 <= stalled.length <= 10000.- Every entry of stalled is 0 or 1.