A Binding Algorithm for Retargetable Compilation to Non-orthogonal DSP Architectures

Masayuki YAMAGUCHI  Nagisa ISHIURA  Takashi KAMBE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.12   pp.2630-2639
Publication Date: 1998/12/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Compiler
retargetable compiler,  binding,  non-orthogonal architecture,  DSP,  binary decision diagram,  

Full Text: PDF>>
Buy this Article

This paper presents a new binding algorithm for a retargetable compiler which can deal with diverse architectures of application specific embedded processors. The architectural diversity includes a "non-orthogonal" datapath configuration where all the registers are not equally accessible by all the functional units. Under this assumption, binding becomes a hard task because inadvertent assignment of an operation to a functional unit may rule out possible assignment of other operations due to unreachability among datapath resources. We propose a new BDD-based algorithm to solve this problem. While most of the conventional methods are based on the covering of expression trees obtained by decomposing DFGs, our algorithm works directly on the DFGs so as to avoid infeasible bindings. In the experiments, a feasible binding which satisfies the reachability is found or the deficiency of datapath is detected within a few seconds.