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

[Robert Pearson]

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);
+
+			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);