#include "mcmgraph.h"
#include "../../base/hsdf/check.h"
#include "../../base/algo/components.h"
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <math.h>

Include dependency graph for mcmhoward.cc:

Defines
#define	MAX_NIterations 1000
#define	EPSILON -HUGE_VAL
Functions
static void	Epsilon (double a, int narcs, double epsilon)
static void	Initial_Policy ()
static void	New_Build_Inverse ()
static void	Init_Depth_First ()
static void	New_Depth_First_Label (int i)
static void	Visit_From (int initialpoint, int color)
static void	Value ()
static void	Init_Improve ()
static void	First_Order_Improvement (int *improved)
static void	Second_Order_Improvement (int *improved)
static void	Improve (int *improved)
static void	Allocate_Memory ()
static void	Free_Memory ()
static void	Check_Rows ()
static void	Security_Check ()
static void	Import_Arguments (int IJ, double A, int NNODES, int NARCS, double CHI, double V, int POLICY, int NITERATIONS, int *NCOMPONENTS)
static void	Update_Policy ()
static void	End_Message ()
static void	Howard (int IJ, double A, int NNODES, int NARCS, double CHI, double V, int POLICY, int NITERATIONS, int *NCOMPONENTS)
static void	convertMCMgraphToMatrix (MCMgraph g, int IJ, double *A)
static CFraction	mcmHoward (TimedSDFgraph *g)
CFraction	maximumCycleMeanHoward (TimedSDFgraph *g)
Variables
static int *	ij
static double *	a
static int	nnodes
static int	narcs
static double *	chi
static double *	v
static int *	pi
static int *	NIterations
static int *	NComponents
static int *	newpi = NULL
static int *	piinv_idx = NULL
static int *	piinv_succ = NULL
static int *	piinv_elem = NULL
static int *	piinv_last = NULL
static double *	c = NULL
static double *	vaux = NULL
static double *	newc = NULL
static double *	newchi = NULL
static int *	visited = NULL
static int *	component = NULL
static double	lambda = 0
static double	epsilon = 0
static int	color = 1

Define Documentation

#define EPSILON -HUGE_VAL

Referenced by Initial_Policy().

#define MAX_NIterations 1000

Referenced by End_Message(), and Howard().

Function Documentation

static void Allocate_Memory ( ) [static]

References c, component, newc, newchi, newpi, nnodes, piinv_elem, piinv_idx, piinv_last, piinv_succ, vaux, and visited.

Referenced by Howard().

static void Check_Rows ( ) [static]

References ij, narcs, and nnodes.

Referenced by Security_Check().

static void convertMCMgraphToMatrix	(	MCMgraph *	g,
		int *	IJ,
		double *	A
	)			`[static]`

convertMCMgraphToMatrix () The function converts a weighted directed graph used in the MCM algorithms to a sparse amtrix input for Howard's algorithm.

References _MCMedge::dst, MCMgraph::edges, _MCMnode::id, MCMgraph::nodes, _MCMedge::src, _MCMedge::visible, _MCMnode::visible, and _MCMedge::w.

Referenced by mcmHoward().

static void End_Message ( ) [static]

References MAX_NIterations, and NIterations.

Referenced by Howard().

static void Epsilon	(	double *	a,
		int	narcs,
		double *	epsilon
	)			`[static]`

Epsilon () The termination tests are performed up to an epsilon constant, which is fixed heuristically by the following routine.

Referenced by Howard().

static void First_Order_Improvement ( int * improved ) [static]

References a, chi, ij, narcs, newc, newchi, and newpi.

Referenced by Improve().

static void Free_Memory ( ) [static]

References c, component, newc, newchi, newpi, piinv_elem, piinv_idx, piinv_last, piinv_succ, vaux, and visited.

Referenced by Howard().

static void Howard	(	int *	IJ,
		double *	A,
		int	NNODES,
		int	NARCS,
		double *	CHI,
		double *	V,
		int *	POLICY,
		int *	NITERATIONS,
		int *	NCOMPONENTS
	)			`[static]`

Howard () Howard Policy Iteration Algorithm for Max Plus Matrices.

INPUT of Howard Algorithm: ij,A,nnodes,narcs : sparse description of a matrix.

OUTPUT: chi cycle time vector v bias pi optimal policy NIterations: Number of iterations of the algorithm NComponents: Number of connected components of the optimal policy

REQUIRES: O(nnodes) SPACE One iteration requires: O(narcs+nnodes) TIME

The following variables should be defined in the environment from which the Howard routine is called.

INPUT VARIABLES int NNODES; number of nodes of the graph int NARCS; number of arcs of the graph int *IJ; array of integers of size 2*narcs for (0 <=k <narcs), the arc numbered k goes from IJ[k][0] =(IJ[2k]) to IJ[k][1] (=IJ[2k+1]) double *A; array of double of size narcs A[k]=weight of the arc numbered k

OUTPUT VARIABLES double *V; array of double of size nnodes (the bias vector) double *CHI; array of double of size nnodes (the cycle time vector) int *POLICY; array of integer of size nnodes (an optimal policy) int NITERATIONS; the number of iterations of the algorithm int NCOMPONENTS; the number of connected components of the optimal policy which is returned.

References a, Allocate_Memory(), End_Message(), epsilon, Epsilon(), Free_Memory(), Import_Arguments(), Improve(), Initial_Policy(), MAX_NIterations, narcs, New_Build_Inverse(), NIterations, Security_Check(), Update_Policy(), and Value().

Referenced by mcmHoward().

Here is the call graph for this function:

static void Import_Arguments	(	int *	IJ,
		double *	A,
		int	NNODES,
		int	NARCS,
		double *	CHI,
		double *	V,
		int *	POLICY,
		int *	NITERATIONS,
		int *	NCOMPONENTS
	)			`[static]`

References a, chi, ij, narcs, NComponents, NIterations, nnodes, pi, and v.

Referenced by Howard().

static void Improve ( int * improved ) [static]

References First_Order_Improvement(), Init_Improve(), NComponents, and Second_Order_Improvement().

Referenced by Howard().

Here is the call graph for this function:

static void Init_Depth_First ( ) [static]

References component, nnodes, and visited.

Referenced by Value().

static void Init_Improve ( ) [static]

References c, chi, newc, newchi, newpi, nnodes, pi, v, and vaux.

Referenced by Improve().

static void Initial_Policy ( ) [static]

Initial_Policy Build an admissible policy pi and its associated cost vector c from ij and A. Reasonable greedy rule to determine the first policy. pi(node i) = arc with maximal weigth starting from i for full random matrices, this choice of initial policy seems to cut the number of iterations by a factor 1.5, by comparison with a random initial policy.

References a, c, EPSILON, ij, narcs, nnodes, pi, and vaux.

Referenced by Howard().

CFraction maximumCycleMeanHoward ( TimedSDFgraph * g )

maximumCycleMeanHoward () The function computes the maximum cycle mean of a HSDF graph using Howard's algorithm.

References isHSDFgraph(), isStronglyConnectedGraph(), and mcmHoward().

Referenced by analyzeSDFG().

Here is the call graph for this function:

static CFraction mcmHoward ( TimedSDFgraph * g ) [static]

mcmHoward () The function computes the maximum cycle mean of a HSDF graph using Howard's algorithm.

References chi, convertMCMgraphToMatrix(), Howard(), MCMgraph::nrEdges(), MCMgraph::nrNodes(), stronglyConnectedMCMgraph(), transformHSDFtoMCMgraph(), and v.

Referenced by maximumCycleMeanHoward().

Here is the call graph for this function:

static void New_Build_Inverse ( ) [static]

References nnodes, pi, piinv_elem, piinv_idx, piinv_last, and piinv_succ.

Referenced by Howard().

static void New_Depth_First_Label ( int i ) [static]

Given the value of v at initial point i, we compute v[j] for all predecessor j of i, according to the spectral equation, v[j]+ lambda = A(arc from j to i) v[i] the array visited is changed by side effect.

References a, c, chi, color, component, lambda, piinv_elem, piinv_idx, piinv_succ, v, and visited.