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

Last change on this file since 636 was 632, checked in by alain, 6 years ago

This version replace the RPC by direct remote memory access
for physical pages allacation/release.
It is commited before being tested.
File size: 8.0 KB
Line 
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
72typedef 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 macro-cluster     */
77    uint32_t      pages;            /*! current number of pages in macro-cluster       */
78    uint32_t      cores;            /*! number of active cores in macro cluster        */
79    uint32_t      clusters;         /*! number of active cluster in macro cluster      */ 
80        xptr_t        parent;           /*! extended pointer on parent node                */
81        xptr_t        children[2][2];   /*! extended pointers on children nodes            */
82}
83dqdt_node_t;
84
85
86/****************************************************************************************
87 * This function recursively initializes the DQDT structure from informations
88 * stored in cluster manager (x_size, y_size and cluster_info[x][y].
89 * It is executed in all clusters by the local CP0, to compute level_max and register
90 * the DQDT root node in each cluster manager, but only CPO in cluster 0 build actually
91 * the quad-tree covering all active clusters.
92 * This initialisation can use remote_accesses, because the DQDT nodes are
93 * allocated as global variables in the cluster_manager, and the local addresses
94 * are identical in all clusters.
95 ***************************************************************************************/
96void dqdt_init( void );
97
98/****************************************************************************************
99 * These local function update the total number of threads in level 0 DQDT node,
100 * and immediately propagates the variation to the DQDT upper levels.
101 * They are called on each thread creation or destruction.
102 ***************************************************************************************/
103void dqdt_increment_threads( void );
104void dqdt_decrement_threads( void );
105
106/****************************************************************************************
107 * These two functions can be called by any thread running in any cluster.
108 * They increment/decrement the total number of 4 Kbytes pages allocated in a cluster
109 * identified by the <cxy> argument, as specified by the <order> argument. The level 0
110 * DQDT node is udated, and this change is immediately propagated to upper levels.
111 * They are called by PPM on each physical memory page allocation or release.
112 ****************************************************************************************
113 * @ cxy     : target cluster identifier.
114 * @ order   : ln2( number of 4 Kbytes pages )
115 ***************************************************************************************/
116void dqdt_increment_pages( cxy_t    cxy , 
117                           uint32_t order );
118
119void dqdt_decrement_pages( cxy_t    cxy,
120                           uint32_t order );
121
122/****************************************************************************************
123 * This function can be called in any cluster. It traverses the DQDT tree
124 * from the root to the bottom, to analyse the computing load and select the cluster
125 * with the lowest number ot threads to place a new process.
126 ****************************************************************************************
127 * @ returns the cluster identifier with the lowest computing load.
128 ***************************************************************************************/
129cxy_t dqdt_get_cluster_for_process( void );
130
131/****************************************************************************************
132 * This function can be called in any cluster. It traverses the DQDT tree
133 * from the root to the bottom, to analyse the memory load and select the cluster
134 * with the lowest memory load for dynamic memory allocation with no locality constraint.
135 ****************************************************************************************
136 * @ returns the cluster identifier with the lowest memory load.
137 ***************************************************************************************/
138cxy_t dqdt_get_cluster_for_memory( void );
139
140/****************************************************************************************
141 * This function displays on kernel TXT0 the DQDT state for all nodes in the quad-tree.
142 * It traverses the quadtree from root to bottom, and can be called by a thread
143 * running in any cluster
144 ***************************************************************************************/
145void dqdt_display( void );
146
147
148#endif  /* _DQDT_H_ */
Note: See TracBrowser for help on using the repository browser.