An Instruction Scheduling Algorithm Based on Subgraph Isomorphism

Ricardo SantosRodolfo AzevedoGuido Araujo

This paper presents an instruction scheduling algorithm based on the Subgraph Isomorphism Problem. Given a Directed Acyclic Graph (DAG) G1, our algorithm looks for a subgraph G2'' in a base graph G2, such that G2'' is isomorphic to G1. The base graph G2 represents the arrangement of the processing elements of a high performance computer architecture named 2D-VLIW and G2'' is the set of those processing elements required to execute operations in G1. We have compared this algorithm with a greedy list scheduling strategy using programs of the SPEC and MediaBench suites. In our experiments, the average Operation Per Cycle (OPC) and Operations Per Instruction (OPI) achieved by our algorithm are 1:45 and 1:40 times better than the OPC and OPI obtained by the list scheduling algorithm.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: