Speed Optimization -Introduction- (Michael Kunstelj / Lorenzo Micheletto)
(Note from Betov: I include this paper without the Authors agreement, because I have not been able to get in touch with them. Betov@free.fr)
Brief intro about how a CPU works
Now a brief intro on the innards Intel CPUs.
Most processors these days have within in them a system termed a ''''pipeline''''. The 486 / 586 are certainly within this category. However, most people aren''t quite sure what exactly a pipeline is, here follows a complete explanation:
The execution of a machine code instruction can be roughtly split in five stages: [n.b. this is a generic pipeline]
1) FETCH instruction opcode and immediate data
2) DECODE opcode and align immediata data into temporary registers
3) CALCULATE ADDRESS OF OPERANDS and load ''em into memory.
(calculate the address of memory locations to access
and select the register operands to use)
(sometimes called DECODE 2)
4) EXECUTE instruction (loading memory operands if needed)
& write results to INTERNAL registers
5) WRITEBACK memory-operand results to memory
Every stage takes ONE OR MORE cpu cycles to be completed, but usually a modern cpu needs just one cpu cycle for every execution stage (excluding stages 1 and 5 that have to deal with memory/cache access
and stage 4 when ''''complex'''' microcoded instructions are executed).
A cpu-core ( the ''''real'''' cpu, not cache support nor the other things that are usually integrated into a modern cpu) has five ''''specialized'''' units, one for every stage of instruction execution, plus a ''''register file''''
(and ultra-fast on-chip memory where internal register values are stored) and a CONTROL UNIT.
The control unit ''''coordinates'''' the action of all the other units so they can work together.
Here follows an extended ascii drawing of ONE on the many ways these units can be connected:
MEMORY INPUT (''''memory load'''' unit)
¦ +------------+
+------->+------------+<-------->¦ ¦
+++ ¦ FETCH ¦ ¦ ¦
+---------------------+¦+>+---------------+ ¦ ¦
¦ (instruction pointer)¦ ¦ ¦ ¦
¦ ¦ +------------+<-+ ¦ ¦
¦ ¦ ¦ DECODE ¦<-------->¦ ¦
¦ ¦ +---------------+ ¦ ¦
¦ ¦ ¦ ¦ ¦
¦ ¦ +------------+<-+ ¦ CONTROL ¦
¦ ++ ¦ ADDRESS C. ¦<-------->¦ ¦
¦ +----+-->+---------------+ ¦ UNIT ¦
¦ ¦ ++ ¦ ¦ ¦
+------------------------+ +->+------------+<-+ ¦ ¦
¦ REGISTER FILE +----->¦ EXECUTE ¦<-------->¦ ¦
+------------------------+<---------------------+ ¦ ¦
¦ ¦ ¦
+------------+<-+ ¦ ¦
¦ WRITEBACK ¦<-------->¦ ¦
+---------------+ ¦ ¦
¦ +------------+
MEMORY OUTPUT <---+
(''''memory store'''' unit)
If you look the drawing, the control unit needs to communicate with all the other units to make ''em work together.
Usually the ''''control unit'''' is scattered in little units that coordinates intruction and data flow between adiacent units, but you can think at it as a single indipendent unit.
The five execution units are what gives the ''''raw'''' cpu power but the control unit is what lets you fully utilize ''em.
Let''s suppose every unit performs one operation in one step.
With a ''''cheap'''' control unit, to execute a complete machine language instruction you first enable FETCH, then you enable DECODE and so on until WRITEBACK is completed and the control unit enables FETCH again to execute the next instruction.
This is what happens into an ''''absolutely not pipelined'''' cpu with ''''one cycle'''' stages, the fastest instructions takes 5 cycles but the control unit is very simple (just a circular shift register that enables one unit at a time).
Of course this is the worst case, nobody is so jerk to build a cpu like that.
Every cpu stage-execution unit is a stand alone thing, it has its hardware and its ''''temporary registers'''' so it is capable to operate ''''alone''''.
So, IF THE CONTROL UNIT can SINCHRONIZE the operations of all the stage-execution units, it can make ''em WORK IN PIPELINE (like in a factory, where every worker/robot in a production line a) receives a partially refined product from the previous worker in line b) performs some simple operations to refine the product a little more c) pass the result to the next worker in line). A cpu with such a control unit is called a pipelined CPU.
If you have to execute in sequence instructions A,B,C,D,E on a pipelined processor ....
While the WRITEBACK unit is performing stage 5 of A
the EXECUTION unit can perform stage 4 of B
the ADDRESS CALCULATE unit can perform stage 3 of C
the DECODE unit can perform stage 2 of D
and the FETCH unit can perform stage 1 of E
So if you start the cpu at instruction A it looks like that instruction A takes 5 cycles while instructions B,C,D,E (immediately one stage behind) looks like they take JUST ONE CYCLE!!!
So if you execute a SEQUENCE of 8 instructions on a ''''not pipelined'''' processor with a five stage ''''pipe'''' it takes 40 steps to execute the sequence while on a pipelined processor this takes 5+7=12 steps!!! ( 5 steps for the first instruction to get thru the pipeline then 7 steps for the other instructions immediately ''''one step'''' behind) And the more instructions are executed in sequence, the more it looks like every instruction takes ''''just'''' one cycle to execute.
This is of course the optimal situation, when the processor pipeline is filled and WHEN EVERY INSTRUCTION DOES NOT USE MEMORY/REGISTER OPERANDS ''''still under processing'''' IN SUCCESSIVE EXECUTION-STAGES!!!!!!
THINGS A CPU MUST CHECK TO MAKE A PIPELINE WORK CORRECTLY
A pipelined processor control-unit must ''''check'''' :
A) at stage 1 (FETCH)
IF in stage 2..4 there are JUMP instructions [ they change the program counter (the same register used by the fetch unit)]
THEN stage 1 must ''''wait'''' until the jump is completed and then ''''restarts'''', loading the memory location pointed by the new program counter value.
Because the jump opcode must pass thru the decode stage ...if the DECODE unit ''detects'' a jump opcode, it makes the FETCH unit ''stops'' AT LEAST for two cycles until the jump is performed.This of course means the processor pipeline ''wastes'' some cpu cycles.
A 486 handles jumps in a smarter way, when the FETCH unit loads a jump instruction, it goes on assuming the jump WON''T BE TAKEN (it read the instructions following the jump). If the jump is taken, the values in the DECODE 1 and DECODE 2 units are ''discarded'' and the FETCH unit starts loading from the new
program counter value. This explains why on 486 relative jumps (the fastest jumps) takes 3 cycles if taken (two cycles ''lost'') 1 cycle if not taken (no cycles lost)
A ''smarter'' control unit can recognize in advance unconditional jumps and start immediately loading opcodes from the new program counter location AND/OR try to ''predict'' the jump destination of conditional jumps (like the Pentium does).
B) at step 3 (ADDRESS CALCULATION)
IF in stage 3 a register needed for address calculation is under processing in stage 4 (EXECUTE)
THEN the stage 3 unit generates a ''do nothing'' control sequence for one cpu cycle.
C) memory access conflicts
These can be caused by lots of different things, they are usually resolved by the memory load/store units.
Told in a short way, in a fully pipelined processor when the pipeline is ''working on a sequence'' the first instruction in the sequence takes the full execution time while the other instructions takes a shorter time (usually one cycle) because they are immediately behind, this means they ''look faster'' (and in fact they are, because the pipeline fully utilizes all the functional units it has).
If some instructions ''modify'' values needed in the previous cpu stages the control unit stops the unit needing those values (and the others behind it) and inserts ''do nothing'' codes into the successive units in the processor pipe to make things work as expected (this is called a PIPELINE STALL or a PIPELINE FLUSH)
This explains why usually a taken jump takes more time than one that''s not taken (when a jump is performed you must flush the pipeline).
The newer processors includes JUMP PREDICTION UNITS that handles jump faster, but the less you jump, the better.