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 <[EMAIL PROTECTED]>
> ----
> 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);
>
>
_______________________________________________
general mailing list
[email protected]
http://lists.openfabrics.org/cgi-bin/mailman/listinfo/general
To unsubscribe, please visit http://openib.org/mailman/listinfo/openib-general
