1 | /* |
---|
2 | * kern/dqdt.h - Distributed Quad Decision Tree |
---|
3 | * |
---|
4 | * Author : Alain Greiner (2016) |
---|
5 | * |
---|
6 | * Copyright (c) UPMC Sorbonne Universites |
---|
7 | * |
---|
8 | * This file is part of ALMOS-MKH |
---|
9 | * |
---|
10 | * ALMOS-kernel is free software; you can redistribute it and/or modify it |
---|
11 | * under the terms of the GNU General Public License as published by |
---|
12 | * the Free Software Foundation; version 2.0 of the License. |
---|
13 | * |
---|
14 | * ALMOS-kernel is distributed in the hope that it will be useful, but |
---|
15 | * WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
17 | * General Public License for more details. |
---|
18 | * |
---|
19 | * You should have received a copy of the GNU General Public License |
---|
20 | * along with ALMOS-kernel; if not, write to the Free Software Foundation, |
---|
21 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
---|
22 | */ |
---|
23 | |
---|
24 | #ifndef _DQDT_H_ |
---|
25 | #define _DQDT_H_ |
---|
26 | |
---|
27 | #include <almos_config.h> |
---|
28 | #include <hal_types.h> |
---|
29 | #include <hal_atomic.h> |
---|
30 | |
---|
31 | /**************************************************************************************** |
---|
32 | * This DQDT infrastructure maintains a topological description of ressources usage |
---|
33 | * (number of threads, and number of physical pages allocated) in each cluster. |
---|
34 | * |
---|
35 | * - If X_SIZE or Y_SIZE are equal to 1, it makes the assumption that the cluster |
---|
36 | * topology is a one dimensionnal vector, an build the smallest one-dimensionnal |
---|
37 | * quad-tree covering this one-dimensionnal vector. If the number of clusters |
---|
38 | * is not a power of 4, the tree is truncated as required. |
---|
39 | * TODO : the mapping for the one dimensionnal topology is not implemented yet [AG]. |
---|
40 | * |
---|
41 | * - If both Y_SIZE and Y_SIZE are larger than 1, it makes the assumption that |
---|
42 | * the cluster topology is a 2D mesh. The [X,Y] coordinates of a cluster are |
---|
43 | * obtained from the CXY identifier using the following rules : |
---|
44 | * X = CXY >> Y_WIDTH / Y = CXY & ((1<<Y_WIDTH)-1) |
---|
45 | * If the mesh X_SIZE and Y_SIZE dimensions are not equal, or are not power of 2, |
---|
46 | * we build the smallest two dimensionnal quad-tree covering all clusters, |
---|
47 | * and this tree is truncated as required. |
---|
48 | * The root node is always implemented in cluster [0,0] |
---|
49 | * The mesh size is supposed to contain at most 32 * 32 clusters. |
---|
50 | * There are at most 6 DQDT nodes in a cluster |
---|
51 | * . Level 0 nodes exist on all clusters and have no children. |
---|
52 | * . Level 1 nodes exist when both X and Y coordinates are multiple of 2 |
---|
53 | * . Level 2 nodes exist when both X and Y coordinates are multiple of 4 |
---|
54 | * . Level 3 nodes exist when both X and Y coordinates are multiple of 8 |
---|
55 | * . Level 4 nodes exist when both X and Y coordinates are multiple of 16 |
---|
56 | * . Level 5 nodes exist when both X and Y coordinates are multiple of 32 |
---|
57 | ***************************************************************************************/ |
---|
58 | |
---|
59 | /**************************************************************************************** |
---|
60 | * This structure describes a node of the DQDT. |
---|
61 | * The max number of children is 4, but it can be smaller for some nodes. |
---|
62 | * Level 0 nodes are the clusters, and have no children. |
---|
63 | * The root node has no parent, and is always stored in cluster[0,0]. |
---|
64 | ***************************************************************************************/ |
---|
65 | typedef struct dqdt_node_s |
---|
66 | { |
---|
67 | uint32_t level; // node level |
---|
68 | uint32_t arity; // actual children number in this node |
---|
69 | uint32_t threads; // current number of threads in subtree |
---|
70 | uint32_t pages; // current number of pages in subtree |
---|
71 | xptr_t parent; // extended pointer on parent node |
---|
72 | xptr_t children[4]; // extended pointers on children nodes |
---|
73 | } |
---|
74 | dqdt_node_t; |
---|
75 | |
---|
76 | |
---|
77 | /**************************************************************************************** |
---|
78 | * This local function initializes the local DQDT structures. |
---|
79 | * The information describing the hardware platform topology and the cluster |
---|
80 | * indexing policy is defined by the three arguments below. |
---|
81 | * This initialisation is done in parallel, locally in each cluster, because the DQDT |
---|
82 | * is allocated as a global variable in the cluster_manager, and the local addresses |
---|
83 | * are identical in all clusters. |
---|
84 | **************************************************************************************** |
---|
85 | * @ x_size : number of clusters (containing memory and CPUs) in a row |
---|
86 | * @ y_size : number of clusters (containing memory and CPUs) in a column |
---|
87 | * @ y_width : number of LSB used to code the Y value in CXY |
---|
88 | * @ return the number of levels in quad-tree. |
---|
89 | ***************************************************************************************/ |
---|
90 | uint32_t dqdt_init( uint32_t x_size, |
---|
91 | uint32_t y_size, |
---|
92 | uint32_t y_width ); |
---|
93 | |
---|
94 | /**************************************************************************************** |
---|
95 | * This recursive function displays usage information for all DQDT nodes in the subtree |
---|
96 | * defined by the node argument. It traverses the quadtree from root to bottom. |
---|
97 | **************************************************************************************** |
---|
98 | * @ node_xp : extended pointer on a DQDT node. |
---|
99 | ***************************************************************************************/ |
---|
100 | void dqdt_global_print( xptr_t node_xp ); |
---|
101 | |
---|
102 | /**************************************************************************************** |
---|
103 | * This function displays summary usage information in a given DQDT local node. |
---|
104 | **************************************************************************************** |
---|
105 | * @ node : local pointer on a DQDT node. |
---|
106 | ***************************************************************************************/ |
---|
107 | void dqdt_local_print( dqdt_node_t * node ); |
---|
108 | |
---|
109 | /**************************************************************************************** |
---|
110 | * This recursive function traverses the DQDT quad-tree from bottom to root, to propagate |
---|
111 | * the change in the threads number and allocated pages number in a leaf cluster, |
---|
112 | * toward the upper levels of the DQDT quad-tree. |
---|
113 | * It should be called periodically by each instance of the kernel. |
---|
114 | ***************************************************************************************/ |
---|
115 | void dqdt_global_update(); |
---|
116 | |
---|
117 | /**************************************************************************************** |
---|
118 | * This local function updates both the total number of threads, |
---|
119 | * in the level 0 DQDT node, and the variation of the number of threads |
---|
120 | * for future propagation to the DQDT upper levels. |
---|
121 | * It should be called on each thread creation or destruction. |
---|
122 | **************************************************************************************** |
---|
123 | * @ increment : increment (can be positive or negative) |
---|
124 | ***************************************************************************************/ |
---|
125 | void dqdt_local_update_threads( int32_t increment ); |
---|
126 | |
---|
127 | /**************************************************************************************** |
---|
128 | * This local function updates both the total number of allocated pages, |
---|
129 | * in the level 0 DQDT node, and the variation of the number of pages |
---|
130 | * for future propagation to the DQDT upper levels. |
---|
131 | * It should be called on each memory allocation or release. |
---|
132 | **************************************************************************************** |
---|
133 | * @ increment : increment (can be positive or negative) |
---|
134 | ***************************************************************************************/ |
---|
135 | void dqdt_local_update_pages( int32_t increment ); |
---|
136 | |
---|
137 | /**************************************************************************************** |
---|
138 | * This function can be called in any cluster. It traverses the DQDT tree |
---|
139 | * from the root to the bottom, to analyse the computing load and select the cluster |
---|
140 | * with the lowest number ot threads to place a new process. |
---|
141 | **************************************************************************************** |
---|
142 | * @ returns the cluster identifier with the lowest computing load. |
---|
143 | ***************************************************************************************/ |
---|
144 | cxy_t dqdt_get_cluster_for_process(); |
---|
145 | |
---|
146 | /**************************************************************************************** |
---|
147 | * This function can be called in any cluster. It traverses the DQDT tree |
---|
148 | * from the root to the bottom, to analyse the memory load and select the cluster |
---|
149 | * with the lowest memory load for dynamic memory allocation with no locality constraint. |
---|
150 | **************************************************************************************** |
---|
151 | * @ returns the cluster identifier with the lowest memory load. |
---|
152 | ***************************************************************************************/ |
---|
153 | cxy_t dqdt_get_cluster_for_memory(); |
---|
154 | |
---|
155 | |
---|
156 | #endif /* _DQDT_H_ */ |
---|