[ofa-general] Re: [PATCH][5] opensm: compute local geometry

[Sasha Khapyorsky]

On 10:59 Tue 11 Nov     , Robert Pearson wrote:
> Sasha,
> 
> Here is the fifth patch implementing the mesh analysis algorithm.
> 
> This patch implements
>       - routine to compute characteristics polynomial of a matrix
>       - routine to compute the local 'metric' around each switch
>       - routine to classify switches into a histogram of local geometry
> classes
> 
> Regards,
> 
> Bob Pearson
> 
> Signed-off-by: Bob Pearson <rpearson at systemfabricworks.com>
> ----
> diff --git a/opensm/opensm/osm_mesh.c b/opensm/opensm/osm_mesh.c
> index 7434fee..9254de3 100644
> --- a/opensm/opensm/osm_mesh.c
> +++ b/opensm/opensm/osm_mesh.c
> @@ -338,6 +338,172 @@ static int determinant(lash_t *p_lash, int deg, int
> rank, int ***m, int *p)
>  }
>  
>  /*
> + * char_poly
> + *
> + * compute the characteristic polynomial of matrix of rank
> + * by computing the determinant of m-x*I and return in poly
> + * as an array. caller must free poly
> + */
> +static int char_poly(lash_t *p_lash, int rank, int **matrix, int **poly)
> +{
> +	int ret = -1;
> +	int i, j;
> +	int ***m = NULL;
> +	int *p = NULL;
> +	int deg = rank;
> +
> +	do {
> +		if (!(p = poly_alloc(p_lash, deg))) {
> +			break;
> +		}
> +
> +		if (!(m = pm_alloc(p_lash, rank, deg))) {
> +			free(p);
> +			p = NULL;
> +			break;
> +		}
> +
> +		for (i = 0; i < rank; i++) {
> +			for (j = 0; j < rank; j++) {
> +				m[i][j][0] = matrix[i][j];
> +			}
> +			m[i][i][1] = -1;
> +		}
> +
> +		if (determinant(p_lash, deg, rank, m, p)) {
> +			free(p);
> +			p = NULL;
> +			break;
> +		}
> +
> +		ret = 0;
> +	} while(0);
> +
> +	pm_free(m, rank);
> +	*poly = p;
> +	return ret;
> +}
> +
> +/*
> + * get_switch_metric
> + *
> + * compute the matrix of minimum distances between each of
> + * the adjacent switch nodes to sw along paths
> + * that do not go through sw. do calculation by
> + * relaxation method
> + * allocate space for the matrix and save in node_t structure
> + */
> +static int get_switch_metric(lash_t *p_lash, int sw)
> +{
> +	int ret = -1;
> +	int i, j, change;
> +	int sw1, sw2, sw3;
> +	switch_t *s = p_lash->switches[sw];
> +	switch_t *s1, *s2, *s3;
> +	int **m;
> +	mesh_node_t *node = s->node;
> +	int num_links = node->num_links;
> +
> +	do {
> +		if (!(m = m_alloc(p_lash, num_links)))
> +			break;
> +
> +		for (i = 0; i < num_links; i++) {
> +			sw1 = node->links[i]->switch_id;
> +			s1 = p_lash->switches[sw1];
> +
> +			/* make all distances big except s1 to itself */
> +			for (sw2 = 0; sw2 < p_lash->num_switches; sw2++)
> +				p_lash->switches[sw2]->node->temp =
> 0x7fffffff;
> +
> +			s1->node->temp = 0;
> +
> +			do {
> +				change = 0;
> +
> +				for (sw2 = 0; sw2 < p_lash->num_switches;
> sw2++) {
> +					s2 = p_lash->switches[sw2];
> +					if (s2->node->temp == 0x7fffffff)
> +						continue;
> +					for (j = 0; j < s2->node->num_links;
> j++) {
> +						sw3 =
> s2->node->links[j]->switch_id;
> +						s3 = p_lash->switches[sw3];
> +
> +						if (sw3 == sw)
> +							continue;
> +
> +						if ((s2->node->temp + 1) <
> s3->node->temp) {
> +							s3->node->temp =
> s2->node->temp + 1;
> +							change++;
> +						}
> +					}
> +				}
> +			} while(change);

As far as I can understand it is minimal hops calculation.

We already have this information in OpenSM switches lmx mtrices. Using
this matrix 'm' could be created as:

	for (i = 0; i < num_links; i++) {
		sw1 = node->links[i]->switch_id;
		s1 = p_lash->switches[sw1];

		for (i = 0; i < num_links; i++) {
			unsigned lid;
			sw2 = node->links[i]->switch_id;
			s2 = p_lash->switches[sw2];
			lid = cl_ntoh16(osm_node_get_base_lid(s2->p_sw->p_node, 0));

			m[i][j] = osm_switch_get_least_hops(s1->p_sw, lid);
		}
	}

> +
> +			for (j = 0; j < num_links; j++) {
> +				sw2 = node->links[j]->switch_id;
> +				s2 = p_lash->switches[sw2];
> +				m[i][j] = s2->node->temp;
> +			}
> +		}
> +
> +		if (char_poly(p_lash, num_links, m, &node->poly)) {
> +			m_free(m, num_links);
> +			m = NULL;
> +			break;
> +		}
> +
> +		ret = 0;
> +	} while(0);
> +
> +	node->matrix = m;
> +	return ret;
> +}
> +
> +/*
> + * classify_switch
> + *
> + * add switch to histogram of switch types
> + */
> +static void classify_switch(lash_t *p_lash, int sw)
> +{
> +	int i;
> +	switch_t *s = p_lash->switches[sw];
> +	switch_t *s1;
> +	mesh_t *mesh = p_lash->mesh;
> +
> +	for (i = 0; i < mesh->num_class; i++) {
> +		s1 = p_lash->switches[mesh->class_type[i]];
> +	
> +		if (poly_diff(s->node->num_links, s->node->poly, s1))
> +			continue;
> +
> +		mesh->class_count[i]++;
> +		return;
> +	}
> +
> +	mesh->class_type[mesh->num_class] = sw;
> +	mesh->class_count[mesh->num_class] = 1;
> +	mesh->num_class++;
> +	return;
> +}
> +
> +/*
> + * get_local_geometry
> + *
> + * analyze the local geometry around each switch
> + */
> +static void get_local_geometry(lash_t *p_lash)
> +{
> +	int sw;
> +
> +	for (sw = 0; sw < p_lash->num_switches; sw++) {
> +		get_switch_metric(p_lash, sw);
> +		classify_switch(p_lash, sw);
> +	}
> +}
> +
> +/*
>   * osm_mesh_cleanup - free per mesh resources
>   */
>  void osm_mesh_cleanup(lash_t *p_lash)
> @@ -404,6 +570,12 @@ int osm_do_mesh_analysis(lash_t *p_lash)
>  		return -1;
>  	}
>  
> +	/*
> +	 * get local metric and invariant for each switch
> +	 * also classify each switch
> +	 */
> +	get_local_geometry(p_lash);
> +
>  	printf("lash: do_mesh_analysis stub called\n");
>  
>  	OSM_LOG_EXIT(p_log);
> 
>