/* Copyright Universite de Versailles Saint-Quentin en Yvelines 2009 AUTHORS: Sebastien Briais, Sid Touati This file is part of RS. RS is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. RS is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with RS. If not, see . */ #ifndef __RS_GREEDY_H #define __RS_GREEDY_H /** \file greedy.h \brief Register saturation (greedy-k heuristic) */ #include #include /** Compute a killing function according to Greedy-k algorithm. @param[in] dag = GDD_DAG @param[in] type = considered type @return a killing function */ SCEDA_HashMap *RS_ddag_greedy_k(GDD_DAG *dag, const char *type); /** Return an approximated set of saturating values for given type. Use Greedy-k algorithm. @param[in] dag = GDD_DAG @param[in] type = considered type @return a list of saturating values */ SCEDA_List *RS_ddag_estimate_saturating_values(GDD_DAG *dag, const char *type); /** Estimate the register saturation for given type. Use Greedy-k algorithm. @param[in] dag = GDD_DAG @param[in] type = considered type @param[in] fast = TRUE to use fast version, FALSE to use precise version @return an approximation of the register saturation */ int RS_ddag_estimate_saturation(GDD_DAG *dag, const char *type, int fast); #endif /** \page greedy Register saturation: theory & practice \section greedy_intro Introduction The register saturation of an acyclic DDG is intuitively the maximum number of registers needed simulteanously, over all the possible scheduling of the DDG instructions. It is possible to compute exactly this value. However, since this problem is NP-complete, the exact algorithm may take a very very long time in practice. Sid Touati has presented in the research article Register saturation in instruction level parallelism an efficient heuristic --called Greedy-k-- to estimate this value. The central point of the two algorithms (exact and approximated) is the potential killers graph. This graph is defined as follows. If \f$G = (V,E)\f$ is an acyclic DDG and \f$t\f$ is a register type, the potential killer graph of type \f$t\f$ is \f$\mathop{PK}^t(G) = (V,E_K)\f$, where \f$E_K = \{ (u,v) \mid u \in V_R^t \wedge v \in \mathop{pkill}_G^t(u) \}\f$. The set \f$\mathop{pkill}_G^t(u)\f$ is the set of potential killers of value \f$u\f$. It is defined by \f$\mathop{pkill}_G^t(u) = \{ v \in \mathop{Cons}^t(u) \mid \mathop{U}(v) \cap \mathop{Cons}^t(u) = \emptyset \}\f$. A killing function is a function \f$\mathop{k}: V_R^t \to V\f$ that choses for each value \f$u \in V_R^t\f$ which potential killer consumes it the latter (ie kills it). If a value is not defined in the map (and thus maps to NULL), it means that it is killed afterwards. A killing function is valid if and only if the graph associated with the killing function is acyclic. This graph is defined by \f$G^t_{\rightarrow k} = (V,E \cup E_k^t)\f$ where \f$E_k^t = \{ (v,\mathop{k}(u)) \mid u \in V_R^t, v \in \mathop{pkill}_G^t(u), v \neq \mathop{k}(u) \}\f$ with \f$\delta(e) = \delta_r^t(v) - \delta_r^t(\mathop{k}(u)) + 1\f$ for any edge \f$e = (v,\mathop{k}(u)) \in E_k^t\f$. Note that not all killing functions are valid. Any valid killing function implies a certain register need. Greedy-k heuristics constructs greedily a killing function that has in practice a register need close to the exact register saturation. The exact algorithm makes an exhaustive search amongst all valid killing functions and maximises the register need. We refer to Sid Touati's article for further details and proofs. \section greedy_api API These functions work on acyclic DDGs (GDD_DAG of DDG library). \code SCEDA_Graph *RS_ddag_pkill(GDD_DAG *dag, const char *type); \endcode Compute the "potential killers" graph for given type. \code SCEDA_List *RS_ddag_saturating_values(GDD_DAG *dag, SCEDA_HashMap *killing_map, const char *type); \endcode Compute a list of saturating values of given type in the DDG, assuming a given killing function. \code SCEDA_HashMap *RS_ddag_greedy_k(GDD_DAG *dag, SCEDA_Graph *pkg, const char *type); \endcode Compute a killing function for given type using Greedy-k algorithm. \code SCEDA_List *RS_ddag_estimate_saturating_values(GDD_DAG *dag, const char *type); \endcode Return an approximated set of saturating values for given type. \code int RS_ddag_estimate_saturation(GDD_DAG *dag, const char *type, int fast); \endcode Estimate register saturation for values of given type, with fast or precise heuristic. \code int RS_ddag_compute_saturation(GDD_DAG *dag, const char *type, double timeout, int *rs, SCEDA_HashMap **k); \endcode Compute the register saturation for values of given type. Since the execution time can be very long, the exhaustive search will stop after the execution time has exceded the timeout (in seconds). \section greedy_example Example The following program parses an XML description of an architecture and a DDG and gives an estimation of the register saturation for each types of the architecture. \include "greedy/main.c" */