/*
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
<http://www.gnu.org/licenses/>.
*/
#ifndef __RS_GREEDY_H
#define __RS_GREEDY_H
/** \file greedy.h
\brief Register saturation (greedy-k heuristic) */
#include <GDD/dag.h>
#include <SCEDA/graph.h>
/** 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 <em>Register saturation in instruction level
parallelism</em> 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"
*/