1 | /* |
---|
2 | * kern/dqdt.h - Distributed Quad Decision Tree |
---|
3 | * |
---|
4 | * Author : Alain Greiner (2016,2017,2018) |
---|
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 <kernel_config.h> |
---|
28 | #include <hal_kernel_types.h> |
---|
29 | #include <hal_atomic.h> |
---|
30 | |
---|
31 | /**************************************************************************************** |
---|
32 | * This DQDT infrastructure maintains a topological description of ressources usage |
---|
33 | * in each cluster: number of threads, and number of physical pages allocated. |
---|
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 | * |
---|
40 | * TODO : the mapping for the one dimensionnal topology is not implemented yet [AG]. |
---|
41 | * |
---|
42 | * - If both Y_SIZE and Y_SIZE are larger than 1, it makes the assumption that |
---|
43 | * the clusters topology is a 2D mesh. The [X,Y] coordinates of a cluster are |
---|
44 | * obtained from the CXY identifier using the Rrelevant macros. |
---|
45 | * X = CXY >> Y_WIDTH / Y = CXY & ((1<<Y_WIDTH)-1) |
---|
46 | * - If the mesh X_SIZE and Y_SIZE dimensions are not equal, or are not power of 2, |
---|
47 | * or the mesh contains "holes" reported in the cluster_info[x][y] array, |
---|
48 | * we build the smallest two dimensionnal quad-tree covering all clusters, |
---|
49 | * and this tree is truncated as required. |
---|
50 | * - The mesh size is supposed to contain at most 32 * 32 clusters. |
---|
51 | * Therefore, it can exist at most 6 DQDT nodes in a given cluster: |
---|
52 | * . Level 0 nodes exist on all clusters and have no children. |
---|
53 | * . Level 1 nodes exist when both X and Y coordinates are multiple of 2 |
---|
54 | * . Level 2 nodes exist when both X and Y coordinates are multiple of 4 |
---|
55 | * . Level 3 nodes exist when both X and Y coordinates are multiple of 8 |
---|
56 | * . Level 4 nodes exist when both X and Y coordinates are multiple of 16 |
---|
57 | * . Level 5 nodes exist when both X and Y coordinates are multiple of 32 |
---|
58 | * - For nodes other than level 0, the placement is defined as follow: |
---|
59 | * . The root node is placed in the cluster containing the core executing |
---|
60 | * the dqdt_init() function. |
---|
61 | * . An intermediate node (representing a given sub-tree) is placed in one |
---|
62 | * cluster covered by the subtree, pseudo-randomly selected. |
---|
63 | ***************************************************************************************/ |
---|
64 | |
---|
65 | /**************************************************************************************** |
---|
66 | * This structure describes a node of the DQDT. |
---|
67 | * The max number of children is 4, but it can be smaller for some nodes. |
---|
68 | * Level 0 nodes are the clusters, and have no children. |
---|
69 | * The root node has no parent. |
---|
70 | ***************************************************************************************/ |
---|
71 | |
---|
72 | typedef struct dqdt_node_s |
---|
73 | { |
---|
74 | uint32_t level; // node level |
---|
75 | uint32_t arity; // actual children number in this node |
---|
76 | uint32_t threads; // current number of threads in subtree |
---|
77 | uint32_t pages; // current number of pages in subtree |
---|
78 | xptr_t parent; // extended pointer on parent node |
---|
79 | xptr_t children[2][2]; // extended pointers on children nodes |
---|
80 | } |
---|
81 | dqdt_node_t; |
---|
82 | |
---|
83 | |
---|
84 | /**************************************************************************************** |
---|
85 | * This function recursively initializes the DQDT structure from informations |
---|
86 | * stored in cluster manager (x_size, y_size and cluster_info[x][y]. |
---|
87 | * It is executed in all clusters by the local CP0, to compute level_max and register |
---|
88 | * the DQDT root node in each cluster manager, but only CPO in cluster 0 build actually |
---|
89 | * the quad-tree covering all active clusters. |
---|
90 | * This initialisation can use remote_accesses, because the DQDT nodes are |
---|
91 | * allocated as global variables in the cluster_manager, and the local addresses |
---|
92 | * are identical in all clusters. |
---|
93 | ***************************************************************************************/ |
---|
94 | void dqdt_init( void ); |
---|
95 | |
---|
96 | /**************************************************************************************** |
---|
97 | * This local function updates the total number of threads in level 0 DQDT node, |
---|
98 | * and propagates the variation to the DQDT upper levels. |
---|
99 | * It should be called on each thread creation or destruction. |
---|
100 | **************************************************************************************** |
---|
101 | * @ increment : increment (can be positive or negative) |
---|
102 | ***************************************************************************************/ |
---|
103 | void dqdt_update_threads( int32_t increment ); |
---|
104 | |
---|
105 | /**************************************************************************************** |
---|
106 | * This local function updates the total number of pages in level 0 DQDT node, |
---|
107 | * and propagates the variation to the DQDT upper levels. |
---|
108 | * It should be called on each physical memory page allocation or release. |
---|
109 | **************************************************************************************** |
---|
110 | * @ increment : increment (can be positive or negative) |
---|
111 | ***************************************************************************************/ |
---|
112 | void dqdt_update_pages( int32_t increment ); |
---|
113 | |
---|
114 | /**************************************************************************************** |
---|
115 | * This function can be called in any cluster. It traverses the DQDT tree |
---|
116 | * from the root to the bottom, to analyse the computing load and select the cluster |
---|
117 | * with the lowest number ot threads to place a new process. |
---|
118 | **************************************************************************************** |
---|
119 | * @ returns the cluster identifier with the lowest computing load. |
---|
120 | ***************************************************************************************/ |
---|
121 | cxy_t dqdt_get_cluster_for_process( void ); |
---|
122 | |
---|
123 | /**************************************************************************************** |
---|
124 | * This function can be called in any cluster. It traverses the DQDT tree |
---|
125 | * from the root to the bottom, to analyse the memory load and select the cluster |
---|
126 | * with the lowest memory load for dynamic memory allocation with no locality constraint. |
---|
127 | **************************************************************************************** |
---|
128 | * @ returns the cluster identifier with the lowest memory load. |
---|
129 | ***************************************************************************************/ |
---|
130 | cxy_t dqdt_get_cluster_for_memory( void ); |
---|
131 | |
---|
132 | /**************************************************************************************** |
---|
133 | * This function displays on kernel TXT0 the DQDT state for all nodes in the quad-tree. |
---|
134 | * It traverses the quadtree from root to bottom, and can be called by a thread |
---|
135 | * running in any cluster |
---|
136 | ***************************************************************************************/ |
---|
137 | void dqdt_display( void ); |
---|
138 | |
---|
139 | |
---|
140 | #endif /* _DQDT_H_ */ |
---|