In this thesis, a new branch folding technique, speculative branch folding, is proposed for low power, embedded applications. The proposed technique is applicable to the single-issue, five stage pipeline structure. An implementation for a commercial embedded processor is also introduced.
The proposed technique predicts the direction of a conditional branch and then it combines the branch instruction with the first instruction of predicted path of the branch. We proposed the folded instruction that consists of the predicted target instruction and the branch condition. Only this folded instruction enters the execution pipeline instead of the branch instruction and the predicted target instruction. Because no branch instruction enters the execution pipeline, the execution continues as if there is no branch instruction in the original sequence of instructions.
An example pipeline structure to implement the pro posed technique is introduced in this thesis. The pipeline structure is conceptually divided into two parts, the pre-fetch unit and the execution unit, and the instruction queue links these two units. The pre-fetch unit fetches instructions from memory and partially decodes the instructions to find branch instructions before storing them in the instruction queue. The execution unit received instructions from the instruction queue, and then decodes and executes them. The instruction queue finds branch instructions and predicts their direction. When a branch instruction reaches the front of the instruction queue, it combines the branch instruction with the predicted instruction and provides only this folded instruction to the execution unit.
Effectiveness of the speculative branch folding is evaluated by extensive simulation. The Simplescalar simulator is modified to show the effect of the proposed technique. We use the Mediabench benchmark suits that are ported to the Simplescalar PISA instruction set architecture. The experimental results show that the proposed technique performs better than SBB folding scheme, the previously proposed branch folding technique for low power embedded processors. Various hardware configurations are also evaluated to analyze the tradeoff of the performance, the power consumption, and the hardware overhead.
A commercial embedded processor, Calm$DSP^{TM}$, is re-designed using speculative branch folding. The hardware cost and the power consumption are measured using commercial and in-house tools used in the ASIC design flow of Samsung. The implementation result of the new processor shows that the proposed technique can be applied to commercial embedded processors. The new processor is implemented with little hardware cost overhead compared with the previous one and shows better performance.
본 논문에서는 Speculative Branch Folding이라는 새로운 Branch Folding 기법을 제안하였다. 제안된 기법은 single-issue, 5 stage pipeline 구조에 적용할 수 있다. 또한, 본 논문에서는 제안된 기법을 상용 내장형 프로세서에 적용하여 구현한 결과를 제시하였다.
제안된 기법에서는 branch의 방향을 예측하여 branch 명령어와 예측된 경로의 첫번째 명령어를 합친다. 예측된 명령어에 branch condition을 첨부함으로써 folded 명령어를 구성한다. Branch 명령어와 예측된 명령어 대신에 folded 명령어만이 실행 파이프라인에 진입한다. 실행 파이프라인 내에 branch 명령어가 존재하지 않기 때문에 실질적인 branch 명령어의 실행시간은 0 이 된다.
제안된 기법을 구현하기 위하여 간단한 파이프라인 구조의 예를 제시하였다. 파이프라인 구조는 개념적으로 Pre-fetch unit과 execution unit의 2부분으로 나뉘고, instruction queue가 이둘을 연결한다. Pre-fetch unit은 메모리에서 명령어를 인출하고, branch 명령어를 차지 위해 이 명령어를 instruction queue에 정장하기 전에 부분적으로 decode 한다. Execution unit 은 instruction queue로부터 명령어를 제공받아서 이를 decode하고 실행한다. Instruction queue는 branch명령어를 찾아서 이의 branch방향을 예측한다. Branch명령어가 instruction queue의 이 branch 명령어와 예측된 명령어를 합치고 이를 execution unit에 제공한다.
시뮬레이션을 통해 제안된 기법의 성능을 평가해 보았다. 시뮬레이터는 Simplescalar를 사용하고 benchmark은 Simplescalar PISA ISA로 porting된 mediabench를 사용하였다. 실험결과 제안된 기법은 기존에 저전력 내장형 프로세서를 대상으로 제시되었던 SBB folding 방식에 비해 나은 성능을 보였다. 또한, 다양한 하드웨어 구성에 따라 성능 및 전력소모, 하드웨어 구성에 따라 성능 및 전력소모, 하드웨어 추가비용에 대해 분석하였다.
$CalmDSP^{TM}$라는 상용 프로세서에 제안된 기법을 적용하여 다시 설계하였다. 삼성의 ASIC design flow에 사용되는 상용 및 in-house tool을 이용하여 하드웨어 비용 및 전력소모량을 측정하였다. 구현 결과 제안된 기법이 상용 내장형 프로세서에 적용될 수 있음을 알 수 있었다. 작은 하드웨어 추가비용을 이용하여 제안된 기법을 적용하기 전보다 성능을 높이고 전력의 소모를 줄일 수 있음을 확인하였다.
