1 #ifndef __TREEMATCH_H__
2 #define __TREEMATCH_H__
3
4 /* size_t definition */
5 #include <stddef.h>
6 #include "tm_verbose.h"
7
8 /********* TreeMatch Public Enum **********/
9
10 /*type of topology files that can be read*/
11 typedef enum{
12 TM_FILE_TYPE_UNDEF,
13 TM_FILE_TYPE_XML,
14 TM_FILE_TYPE_TGT
15 } tm_file_type_t;
16
17 /* different metrics to evaluate the solution */
18 typedef enum{
19 TM_METRIC_SUM_COM = 1,
20 TM_METRIC_MAX_COM = 2,
21 TM_METRIC_HOP_BYTE = 3
22 } tm_metric_t;
23
24 /* numbering */
25 typedef enum{
26 TM_NUMBERING_LOGICAL = 0,
27 TM_NUMBERING_PHYSICAL = 1
28 } tm_numbering_t;
29
30 /********* TreeMatch Public Structures **********/
31
32 typedef struct _job_info_t{
33 int submit_date;
34 int job_id;
35 int finish_date;
36 } tm_job_info_t;
37
38 typedef struct _tm_tree_t{
39 int constraint; /* tells if the tree has been constructed with constraints on the nodes or not.
40 Usefull for freeing it. needs to be set on the root only*/
41 struct _tm_tree_t **child;
42 struct _tm_tree_t *parent;
43 struct _tm_tree_t *tab_child; /* The pointer to be freed */
44 double val;
45 int arity;
46 int depth;
47 int id; /* id of the node or the leaf. Ids are different onmly on a given level */
48 int uniq; /* uniq id in the whole tree */
49 int dumb; /* 1 if the node belongs to a dumb tree: hence has to be freed separately */
50 tm_job_info_t *job_info;
51 int nb_processes; /* number of grouped processes (i.e. the order of the affinity matrix). Set at the root only */
52 }tm_tree_t; /* FT : changer le nom : tm_grouap_hierachy_t ? */
53
54 /* Maximum number of levels in the tree*/
55 #define TM_MAX_LEVELS 100
56
57 typedef struct {
58 int *arity; /* Arity of the nodes of each level*/
59 int nb_levels; /* Number of levels of the tree. Levels are numbered from top to bottom starting at 0*/
60 size_t *nb_nodes; /* Number of nodes of each level*/
61 int physical_num; /* Flag set to !=0 if se use physical numberig and set to 0 is we use logical numbering */
62 int *node_id; /* ID of the nodes of the tree of the last level*/
63 int *node_rank ; /* Rank of the nodes of the tree for the last level given its ID: this is the inverse tab of node_id*/
64
65 size_t *nb_free_nodes; /* Nb of available nodes of each level*/
66 int **free_nodes; /* array of node that are free: useful to simulate batch scheduler*/
67 double *cost; /* Cost of the communication depending on the distance:
68 cost[i] is the cost for communicating at distance nb_levels-i*/
69
70 int *constraints; /* Array of constraints: id of the nodes where it is possible to map processes */
71 int nb_constraints; /* Size of the above array */
72 int oversub_fact; /* Maximum number of processes to be mapped on a given node */
73 int nb_proc_units; /* The real number of units used for computation */
74 }tm_topology_t;
75
76
77 typedef struct {
78 double ** mat;
79 double * sum_row;
80 int order;
81 long int nnz; /* number of non zero entries */
82 } tm_affinity_mat_t;
83
84 /*
85 sigma[i] is such that process i is mapped on core sigma[i]
86 k[i][j] is such that core i executes process k[i][j] (0<=j<<=oversubscribing factor - 1)
87
88 size of sigma is the number of processes (nb_objs)
89 size of k is the number of cores/nodes (nb_compute_units)
90 size of k[i] is the number of process we can execute per nodes (1 if no oversubscribing)
91
92 We must have number of process<=number of cores
93
94 k[i] == NULL if no process is mapped on core i
95 */
96
97 typedef struct {
98 int *sigma;
99 size_t sigma_length;
100 int **k;
101 size_t k_length;
102 int oversub_fact;
103 }tm_solution_t;
104
105
106 /************ TreeMatch Public API ************/
107 /* construct topology from local one using hwloc */
108 tm_topology_t* tm_get_local_topology_with_hwloc(void);
109
110 /* Aletrnatively, load XML or TGT topology */
111 tm_topology_t *tm_load_topology(char *arch_filename, tm_file_type_t arch_file_type);
112 /*
113 Alternatively, build a synthetic balanced topology.
114
115 nb_levels : number of levels of the topology +1 (the last level must be of cost 0 and arity 0).
116 arity : array of arity of the first nb_level (of size nb_levels)
117 cost : array of costs between the levels (of size nb_levels)
118 core_numbering: numbering of the core by the system. Array of size nb_core_per_node
119
120 nb_core_per_nodes: number of cores of a given node. Size of the array core_numbering
121
122 both arity and cost are copied inside tm_build_synthetic_topology
123
124 The numbering of the cores is done in round robin fashion after a width traversal of the topology.
125 for example:
126 {0,1,2,3} becomes 0,1,2,3,4,5,6,7...
127 and
128 {0,2,1,3} becomes 0,2,1,3,4,6,5,7,...
129
130 Example of call to build the 128.tgt file: tleaf 4 16 500 2 100 2 50 2 10
131
132 double cost[5] = {500,100,50,10,0};
133 int arity[5] = {16,2,2,2,0};
134 int cn[2]={0,1};
135
136 topology = tm_build_synthetic_topology(arity,cost,5,cn,2);
137
138 */
139 tm_topology_t *tm_build_synthetic_topology(int *arity, double *cost, int nb_levels, int *core_numbering, int nb_core_per_nodes);
140 /* load affinity matrix */
141 tm_affinity_mat_t *tm_load_aff_mat(char *com_filename);
142 /*
143 Alternativelly, build the affinity matrix from a array of array of matrix of size order by order
144 For performance reason mat is not copied.
145 */
146 tm_affinity_mat_t * tm_build_affinity_mat(double **mat, int order);
147 /* Add constraints to toplogy
148 Return 1 on success and 0 if the constari,ts id are not compatible withe nodes id */
149 int tm_topology_add_binding_constraints(char *bind_filename, tm_topology_t *topology);
150 /* Alternatively, set the constraints from an array.
151 Return 1 on success and 0 if the constari,ts id are not compatible withe nodes id
152
153 The array constraints is copied inside tm_topology_set_binding_constraints
154
155 */
156 int tm_topology_set_binding_constraints(int *constraints, int nb_constraints, tm_topology_t *topology);
157 /* display arity of the topology */
158 void tm_display_arity(tm_topology_t *topology);
159 /* display the full topology */
160 void tm_display_topology(tm_topology_t *topology);
161 /* Optimize the topology by decomposing arities */
162 void tm_optimize_topology(tm_topology_t **topology);
163 /* Manage oversubscribing */
164 void tm_enable_oversubscribing(tm_topology_t *topology, unsigned int oversub_fact);
165 /* core of the treematch: compute the solution tree */
166 tm_tree_t *tm_build_tree_from_topology(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, double *obj_weight, double *com_speed);
167 /* compute the mapping according to the tree and the core numbering*/
168 tm_solution_t *tm_compute_mapping(tm_topology_t *topology, tm_tree_t *comm_tree);
169 /* display the solution*/
170 double tm_display_solution(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_solution_t *sol, tm_metric_t metric);
171 /* display RR, packed, MPIPP*/
172 void tm_display_other_heuristics(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_metric_t metric);
173 /* free TM strutures*/
174 void tm_free_topology(tm_topology_t *topology);
175 void tm_free_tree(tm_tree_t *comm_tree);
176 void tm_free_solution(tm_solution_t *sol);
177 void tm_free_affinity_mat(tm_affinity_mat_t *aff_mat);
178 /* manage verbosity of TM*/
179 void tm_set_verbose_level(unsigned int level);
180 unsigned int tm_get_verbose_level(void);
181 /* finalize treematch :check memory if necessary, and free internal variables (thread pool)*/
182 void tm_finalize(void);
183
184 /*
185 Ask for exhaustive search: may be very long
186 new_val == 0 : no exhuative search
187 new_val != 0 : exhuative search
188 */
189 void tm_set_exhaustive_search_flag(int new_val);
190 int tm_get_exhaustive_search_flag(void);
191
192 /*
193 Ask for greedy k-partitionning even if scotch is available
194 new_val == 0 : no greedy k-partitionning
195 new_val != 0 : greedy k-partitionning
196 */
197 void tm_set_greedy_flag(int new_val);
198 int tm_get_greedy_flag(void);
199
200
201 /* Setting the maximum number of threads you want to use in parallel parts of TreeMatch */
202 void tm_set_max_nb_threads(unsigned int val);
203
204 /* managing the usage of physical vs. logical core numbering when using hwloc/xml files */
205 void tm_set_numbering(tm_numbering_t new_val); /* TM_NUMBERING_LOGICAL or TM_NUMBERING_PHYSICAL */
206 tm_numbering_t tm_get_numbering(void); /* TM_NUMBERING_LOGICAL or TM_NUMBERING_PHYSICAL */
207
208 #include "tm_malloc.h"
209
210 #endif