Research Article
Quantifying ILP by means of Graph Theory
@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
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.