Home         Software: Requirements Download         Ongoing Projects            Publications

Coyote Project Malardalens Hogskola
Nerina Bermudo & Xavier Vera & WCET group

 

 
Notice

This project is finished. The web pages provide documentation but are not maintained. Some of them might not be up-to-date. Software for downloading is provided as is (see the license): it is neither maintained nor supported, and we assume no responsibility of any sort for any consequences that might arise from its use.

Questions might be answered by Xavier Vera, but he is not affiliated with us anymore and there are no guarantees that he will answer.

 

Can I catch all the misses ?Objective
Data caches are a key component of current microprocessors in order to reduce the memory latency. The effectiveness of a cache memory depends not only on the hardware structure, but also on the code generated by the compiler. Common compiler techniques require some knowledge of the behavior of the program in order to be applied. Unfortunately, so far this information can not be obtained in a fast and accurate way at the same time. We present a tool that fills this gap. It allows analyzing the cache memory behavior accurately in few seconds.


 
Description of the Coyote Project

Cache Miss Equations (CMEs) is a method, developed at Princeton University by Somnath Gosh, which accurately describes the cache behavior. Unfortunately, a direct solution of the CMEs is computationally intractable. Even though the computation cost of generating CMEs is a linear function of the number of references, to solve them is a NP-Hard problem and thus trying to study a whole program may be infeasible.

We have followed the ideas presented by Vera et al at the Computer Architecture Department (DAC) at Universitat Politècnica de Catalunya in the following papers:

The implementation consists of 20,000 lines of C++ code. A basic infrastructure provides a hierarchy of C++ classes, which can be used by the developers for analyzing the input program. 
 
The Tool Suite
The software is divided in different modules:

  • Internal Representation: set of classes that describes the program that is going to be analyzed. It basically contains:

    • Classes to represent different memory accesses.

    • Classes to compute its locality by means of reuse vectors.

    • Classes to generate the equations that describe the cache behavior.

    • Set of functions and classes to solve those equations and store the information about the misses.

    • Set of functionalities that allows analyzing only the cache behavior of a subset of the references: perfect for partitioned caches.

Then, we have the different applications. We do not plan only to compute miss ratios for perfectly nested loops. Check out our ongoing projects!

Before summer 2002, we plan to distribute:

  • Genetic Algorithm: set of classes that allows designing and solving a genetic algorithm on the IR. (not available yet )

  • Compiler Optimizations: some compiler optimizations that make use of our IR to improve cache memory behavior. (not available yet)

Add-ons (this software is not maintained and is provided only for convenience purposes):

  • Parser: there is currently a Fortran parser based on Polaris and the Ictineo Library. In order to compile it, you need to apply for their free licenses (Ictineo License). This parser generates the information needed by the IR.
 
How to get a copy

Go to our download page.

This page was last updated Sept. 25th, 2006