Instruction scheduling with k-successor tree for clustered VLIW processors

Clustering is a well-known technique for improving the scalability of classical VLIW (Very Long Instruction Word) processors. A clustered VLIW processor consists of multiple clusters. Each cluster has a local register file and a set of functional units. This paper proposes a novel phase coupled, priority-based heuristic for scheduling a set of operations in a basic block on a clustered VLIW processor. Our heuristic converts the instruction scheduling problem to the problem of scheduling a set of operations with a common deadline. The priority of each operation v _i is the l _max (v _i )-successor-tree-consistent deadline. This deadline is the upper bound on the latest completion time of v _i in any feasible schedule for a relaxed problem where the precedence-latency constraints only between v _i and all its successors are considered. We have simulated our heuristic and the Integrated heuristic on the 808 basic blocks taken from the MediaBench II benchmark suite using three processor models. On average, for the three processor models, our heuristic improves over the Integrated heuristic by 13 %, 18 %, 16 %, respectively.