109 urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891 JUCS - Journal of Universal Computer Science jucs 0948-695X 0948-6968 Journal of Universal Computer Science 10.3217/jucs-014-21-3465 29260 Research Article C.1.3 - Other Architecture Styles D.3.m - Miscellaneous I.2.5 - Programming Languages and Software Instruction Scheduling Based on Subgraph Isomorphism for a High Performance Computer Processor Santos Ricardo ricr.santos@ucdb.br 1 Azevedo Rodolfo 2 Araujo Guido 2 Dom Bosco Catholic University, Campo Grande, Brazil Dom Bosco Catholic University Campo Grande Brazil State University of Campina, Campinas, Brazil State University of Campina Campinas Brazil

Corresponding author: Ricardo Santos (ricr.santos@ucdb.br).

Academic editor:

2008 01 12 2008 14 21 3465 3480 9B009DFA-FAE0-503F-8931-AC6540337965 7000571 Ricardo Santos, Rodolfo Azevedo, Guido Araujo This article is freely available under the J.UCS Open Content License.

This paper1 presents an instruction scheduling algorithm based on the Subgraph Isomorphism Problem. Given a Directed Acyclic Graph (DAG) G1, our algorithm looks for a subgraph G02 in a base graph G2, such that G02 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 G02 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.