2nd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Quantifying ILP by means of Graph Theory

Download746 downloads
  • @INPROCEEDINGS{10.4108/valuetools.2007.1797,
        author={Virginia Escuder and Ra\^{u}l Dur\^{a}n and Rafael Rico},
        title={Quantifying ILP by means of Graph Theory},
        proceedings={2nd International ICST Conference on Performance Evaluation Methodologies and Tools},
        proceedings_a={VALUETOOLS},
        year={2010},
        month={5},
        keywords={Instruction level parallelism Graph theory.},
        doi={10.4108/valuetools.2007.1797}
    }
    
  • Virginia Escuder
    Raúl Durán
    Rafael Rico
    Year: 2010
    Quantifying ILP by means of Graph Theory
    VALUETOOLS
    ICST
    DOI: 10.4108/valuetools.2007.1797
Virginia Escuder1,*, Raúl Durán1,*, Rafael Rico1,*
  • 1: Department of Computer Engineering Universidad de Alcalá 28871 Alcalá de Henares (Spain) +34 91 885 66 15
*Contact email: virginia.escuder@uah.es, raul.duran@uah.es, rafael.rico@uah.es

Abstract

Computer architecture evaluation requires new tools that complement the customary simulations and, in this sense, the traditional Graph Theory can help to create a new frame for finegrain parallelism analysis of execution performance, a step beyond the classical static analysis performed by compilers. Starting off from Graph Theory basic foundations, this paper introduces the data dependence matrix D supported by the novel concept of the reduced valence. The matrix D characterizes a code sequence in a mathematical manner, is endowed with a number of properties and restrictions, and provides information about the ability of the code to be processed concurrently. Among other details, some low complexity techniques to calculate parallelism degree from the matrix D are presented.