Heuristic Instruction Scheduling Algorithm Using Available Distance for Partial Forwarding Processor

Takuji HIEDA  Hiroaki TANAKA  Keishi SAKANUSHI  Yoshinori TAKEUCHI  Masaharu IMAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.12   pp.3258-3267
Publication Date: 2009/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.3258
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Embedded, Real-Time and Reconfigurable Systems
partial forwarding,  instruction scheduling,  compiler,  design space exploration,  

Full Text: PDF>>
Buy this Article

Partial forwarding is a design method to place forwarding paths on a part of processor pipeline. Hardware cost of processor can be reduced without performance loss by partial forwarding. However, compiler with the instruction scheduler which considers partial forwarding structure of the target processor is required since conventional scheduling algorithm cannot make the most of partial forwarding structure. In this paper, we propose a heuristic instruction scheduling method for processors with partial forwarding structure. The proposed algorithm uses available distance to schedule instructions which are suitable for the target partial forwarding processor. Experimental results show that the proposed method generates near-optimal solutions in practical time and some of the optimized codes for partial forwarding processor run in the shortest time among the target processors. It also shows that the proposed method is superior to hazard detection unit.