Aplicación de la Teoría de Grafos al Análisis del Paralelismo a Nivel de Instrucción (On Applying Graph Theory to ILP Analysis)

Raúl Durán (raul.duran@uah.es), Rafael Rico (rafael.rico@uah.es)


Departamento de Automática, Universidad de Alcalá, Spain
This paper appears in: Revista IEEE América Latina

Publication Date: June 2006
Volume: 4,   Issue: 4 
ISSN: 1548-0992


Abstract:
The evaluation of computer architectures requires new tools that complement the customary simulations. Graph theory can help to create a new frame of fine grain parallelism analysis. The differences found between the superscalar performance in x86 and non-x86 processors and the peculiar characteristics of the x86 instruction set architecture recommend to carry out a thorough study of the available parallelism at the machine language layer. Starting off from graph theory foundations, new concepts are introduced, from reduced valence to data dependence matrix D, the latter characterizing a code sequence in a mathematical manner. This matrix satisfies a series of properties and restrictions and provides information about the ability of the code to be processed concurrently. The different sources of data dependencies can be composed, facilitating a way to analyze their final influence on the degree of parallelism.

Index Terms:
Computer architecture evaluation, instruction level parallelism, instructions set architecture, graph theory   


Documents that cite this document
This function is not implemented yet.


[PDF Full-Text (154)]