[1] | 1 | /* |
---|
| 2 | * kern/dqdt.h - Distributed Quad Decision Tree |
---|
[19] | 3 | * |
---|
[437] | 4 | * Author : Alain Greiner (2016,2017,2018) |
---|
[1] | 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 | |
---|
[14] | 27 | #include <kernel_config.h> |
---|
[457] | 28 | #include <hal_kernel_types.h> |
---|
[1] | 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 |
---|
[19] | 37 | * quad-tree covering this one-dimensionnal vector. If the number of clusters |
---|
[1] | 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]. |
---|
[19] | 40 | * |
---|
| 41 | * - If both Y_SIZE and Y_SIZE are larger than 1, it makes the assumption that |
---|
[437] | 42 | * the clusters topology is a 2D mesh. The [X,Y] coordinates of a cluster are |
---|
[19] | 43 | * obtained from the CXY identifier using the following rules : |
---|
[1] | 44 | * X = CXY >> Y_WIDTH / Y = CXY & ((1<<Y_WIDTH)-1) |
---|
[19] | 45 | * If the mesh X_SIZE and Y_SIZE dimensions are not equal, or are not power of 2, |
---|
[1] | 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. |
---|
[19] | 50 | * There are at most 6 DQDT nodes in a cluster |
---|
[1] | 51 | * . Level 0 nodes exist on all clusters and have no children. |
---|
[19] | 52 | * . Level 1 nodes exist when both X and Y coordinates are multiple of 2 |
---|
[1] | 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 | /**************************************************************************************** |
---|
[19] | 78 | * This local function initializes the local DQDT structures. |
---|
[1] | 79 | * The information describing the hardware platform topology and the cluster |
---|
| 80 | * indexing policy is defined by the three arguments below. |
---|
[19] | 81 | * This initialisation is done in parallel, locally in each cluster, because the DQDT |
---|
[1] | 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 | /**************************************************************************************** |
---|
[438] | 95 | * This local function updates the total number of threads in level 0 DQDT node, |
---|
| 96 | * and propagates the variation to the DQDT upper levels. |
---|
[1] | 97 | * It should be called on each thread creation or destruction. |
---|
| 98 | **************************************************************************************** |
---|
| 99 | * @ increment : increment (can be positive or negative) |
---|
| 100 | ***************************************************************************************/ |
---|
[438] | 101 | void dqdt_update_threads( int32_t increment ); |
---|
[1] | 102 | |
---|
| 103 | /**************************************************************************************** |
---|
[438] | 104 | * This local function updates the total number of pages in level 0 DQDT node, |
---|
| 105 | * and propagates the variation to the DQDT upper levels. |
---|
| 106 | * It should be called on each physical memory page allocation or release. |
---|
[1] | 107 | **************************************************************************************** |
---|
| 108 | * @ increment : increment (can be positive or negative) |
---|
| 109 | ***************************************************************************************/ |
---|
[438] | 110 | void dqdt_update_pages( int32_t increment ); |
---|
[1] | 111 | |
---|
| 112 | /**************************************************************************************** |
---|
| 113 | * This function can be called in any cluster. It traverses the DQDT tree |
---|
| 114 | * from the root to the bottom, to analyse the computing load and select the cluster |
---|
| 115 | * with the lowest number ot threads to place a new process. |
---|
| 116 | **************************************************************************************** |
---|
| 117 | * @ returns the cluster identifier with the lowest computing load. |
---|
| 118 | ***************************************************************************************/ |
---|
| 119 | cxy_t dqdt_get_cluster_for_process(); |
---|
| 120 | |
---|
| 121 | /**************************************************************************************** |
---|
| 122 | * This function can be called in any cluster. It traverses the DQDT tree |
---|
[19] | 123 | * from the root to the bottom, to analyse the memory load and select the cluster |
---|
[1] | 124 | * with the lowest memory load for dynamic memory allocation with no locality constraint. |
---|
| 125 | **************************************************************************************** |
---|
| 126 | * @ returns the cluster identifier with the lowest memory load. |
---|
| 127 | ***************************************************************************************/ |
---|
| 128 | cxy_t dqdt_get_cluster_for_memory(); |
---|
| 129 | |
---|
[437] | 130 | /**************************************************************************************** |
---|
[438] | 131 | * This function displays on kernel TXT0 the DQDT state for all nodes in the quad-tree. |
---|
| 132 | * It traverses the quadtree from root to bottom, and can be called by a thread |
---|
| 133 | * running in any cluster |
---|
[437] | 134 | ***************************************************************************************/ |
---|
[438] | 135 | void dqdt_display(); |
---|
[1] | 136 | |
---|
[437] | 137 | |
---|
[1] | 138 | #endif /* _DQDT_H_ */ |
---|