source: trunk/kernel/kern/dqdt.h @ 8

Last change on this file since 8 was 1, checked in by alain, 8 years ago

First import
File size: 8.6 KB
Line 
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 ***************************************************************************************/
65typedef 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}
74dqdt_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 ***************************************************************************************/
90uint32_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 ***************************************************************************************/
100void 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 ***************************************************************************************/
107void 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 ***************************************************************************************/
115void 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 ***************************************************************************************/
125void 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 ***************************************************************************************/
135void 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 ***************************************************************************************/
144cxy_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 ***************************************************************************************/
153cxy_t dqdt_get_cluster_for_memory();
154
155
156#endif  /* _DQDT_H_ */
Note: See TracBrowser for help on using the repository browser.