source: trunk/kernel/kern/dqdt.c @ 286

Last change on this file since 286 was 286, checked in by max@…, 4 years ago

Fix dangerous typos.

File size: 10.7 KB
Line 
1/*
2 * dqdt.c - Distributed Quaternary Decision Tree implementation.
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-MKH 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-MKH 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-MKH; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#include <kernel_config.h>
25#include <hal_types.h>
26#include <hal_special.h>
27#include <hal_atomic.h>
28#include <hal_remote.h>
29#include <printk.h>
30#include <cluster.h>
31#include <bits.h>
32#include <dqdt.h>
33
34
35///////////////////////////////////////////
36void dqdt_local_print( dqdt_node_t * node )
37{
38        printk("DQDT node : level = %d / cluster = %x / threads = %x / pages = %x\n",
39               node->level,
40               local_cxy,
41               node->threads,
42           node->pages );
43}
44
45/////////////////////////////////////////
46void dqdt_global_print( xptr_t  node_xp )
47{
48        uint32_t i;
49    dqdt_node_t local_node;
50
51    // get root node local copy
52    hal_remote_memcpy( XPTR( local_cxy , &local_node ), node_xp , sizeof(dqdt_node_t) );
53
54    // display DQDT node content
55    dqdt_local_print( &local_node );
56
57    // recursive call on children if node is not terminal
58    if ( local_node.level > 0 )
59    {
60        for ( i = 0 ; i < 4 ; i++ )
61        {
62            if ( local_node.children[i] != XPTR_NULL ) dqdt_global_print( local_node.children[i] );
63        }
64    }
65}
66
67////////////////////////////////////
68uint32_t dqdt_init( uint32_t x_size,
69                    uint32_t y_size,
70                    uint32_t y_width )
71{
72    if( (x_size > 32) || (y_size > 32) )
73    {
74        printk("\n[PANIC] in %s : illegal mesh size for DQDT support\n",
75               __FUNCTION__ );
76        hal_core_sleep();
77    }
78
79        dqdt_node_t * node;
80    cxy_t         p_cxy;         // cluster coordinates for parent node
81    cxy_t         c_cxy;         // cluster coordinates for child node
82    uint32_t      level;         // node level in quad tree
83    uint32_t      mask;          // mask on node coordinates to compute existence condition
84    uint32_t      pmask;         // mask to compute parent coordinates from child coordinates
85    cluster_t   * cluster;       // pointer on local cluster
86
87    cluster = LOCAL_CLUSTER;
88
89    // compute level_max
90    uint32_t  x_size_ext = POW2_ROUNDUP( x_size );
91    uint32_t  y_size_ext = POW2_ROUNDUP( y_size );
92    uint32_t  size_ext   = MAX(x_size_ext , y_size_ext);
93    uint32_t  level_max  = (bits_log2(size_ext * size_ext) >> 1) + 1;
94
95    // get cluster coordinates
96    uint32_t    x       = local_cxy >> y_width;
97    uint32_t    y       = local_cxy & ((1<<y_width)-1);
98
99    // loop on local dqdt nodes (at most one node per level)
100    for( level = 0 ; level < level_max ; level++ )
101    {
102        // get pointer on the node to be initialised
103        node = &cluster->dqdt_tbl[level];
104
105        // set default values
106        node->level       = level;
107        node->arity       = 0;
108        node->threads     = 0;
109        node->pages       = 0;
110        node->parent      = XPTR_NULL;
111        node->children[0] = XPTR_NULL;
112        node->children[1] = XPTR_NULL;
113        node->children[2] = XPTR_NULL;
114        node->children[3] = XPTR_NULL;
115
116        // compute masks depending on level : 0x1, 0x3, 0x7, 0xF, 0x1F etc.
117        mask  = (1<<level)-1;
118        pmask = (1<<(level+1))-1;
119
120        // check the node  existence condition at each level
121        if( ((x & mask) == 0) && ((y & mask) == 0) )
122        {
123            // set parent extended pointer
124            p_cxy = ((x & ~pmask)<<y_width) + (y & ~pmask);
125            node->parent = XPTR( p_cxy , &cluster->dqdt_tbl[level+1] );
126
127            // set child[0] extended pointer (same [x,y] coordinates)
128            if ( level > 0 )
129            {
130                c_cxy = local_cxy;
131                node->children[0] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
132                node->arity++;
133            }
134
135            // set child[1] extended pointer (coordinates may overflow)
136            if ( (level > 0) && ((y + (1<<(level-1))) < y_size) )
137            {
138                c_cxy = local_cxy + (1<<(level-1));
139                node->children[1] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1] );
140                node->arity++;
141            }
142
143            // set child[2] extended pointer (coordinates may overflow)
144            if ( (level > 0) && ((x + (1<<(level-1))) < x_size) )
145            {
146                c_cxy = local_cxy + ((1<<(level-1))<<y_width);
147                node->children[2] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
148                node->arity++;
149            }
150
151            // set child[3] extended pointer (coordinates may overflow)
152            if ( (level > 0) && 
153                 ((x + (1<<(level-1))) < x_size) && 
154                 ((y + (1<<(level-1))) < y_size) )
155            {
156                c_cxy = local_cxy + ((1<<(level-1))<<y_width) + (1<<(level-1));
157                node->children[3] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
158                node->arity++;
159            }
160        }  // end if existence condition
161    }  // end for level
162
163    return level_max;
164
165} // end dqdt_init()
166
167
168///////////////////////////////////////////////////////////////////////////
169// This recursive function is called by the dqdt_global_update() function.
170// It traverses the quad tree from clusters to root.
171///////////////////////////////////////////////////////////////////////////
172static void dqdt_propagate( xptr_t  node,         // extended pointer on current node
173                            int32_t threads_var,  // number of threads variation
174                            int32_t pages_var )   // number of pages variation
175{
176    // get current node cluster identifier and local pointer
177    cxy_t         cxy = (cxy_t)GET_CXY( node );
178    dqdt_node_t * ptr = (dqdt_node_t *)GET_PTR( node );
179
180    // update current node threads number
181    hal_remote_atomic_add( XPTR( cxy , &ptr->threads ) , threads_var );
182
183    // update current node pages number
184    hal_remote_atomic_add( XPTR( cxy , &ptr->pages ) , pages_var );
185
186    // get extended pointer on parent node
187    xptr_t parent = (xptr_t)hal_remote_lwd( XPTR( cxy , &ptr->parent ) );
188
189    // propagate if required
190    if ( parent != XPTR_NULL )
191    {
192        dqdt_propagate( parent, threads_var, pages_var );
193    }
194}
195
196/////////////////////////
197void dqdt_global_update()
198{
199        cluster_t   * cluster = LOCAL_CLUSTER;
200    dqdt_node_t * node    = &cluster->dqdt_tbl[0];
201
202    // get variations
203    int32_t      threads_var = cluster->threads_var;
204    int32_t      pages_var   = cluster->pages_var;
205
206    // propagate this variation to DQDT upper levels
207    if( (threads_var || pages_var) && (node->parent != XPTR_NULL) )
208    {
209        dqdt_propagate( node->parent, threads_var, pages_var );
210    }
211
212    // update variations
213    hal_atomic_add( &cluster->threads_var , -threads_var );
214    hal_atomic_add( &cluster->pages_var   , -pages_var   );
215}
216
217///////////////////////////////////////////////////
218void dqdt_local_update_threads( int32_t increment )
219{
220        cluster_t * cluster = LOCAL_CLUSTER;
221
222    // register change for future propagation in DQDT
223    hal_atomic_add( &cluster->threads_var , increment );
224
225    // update DQDT node level 0
226    hal_atomic_add( &cluster->dqdt_tbl[0].threads , increment );
227}
228
229/////////////////////////////////////////////////
230void dqdt_local_update_pages( int32_t increment )
231{
232        cluster_t * cluster = LOCAL_CLUSTER;
233
234    // register change for future propagation in DQDT
235    hal_atomic_add( &cluster->pages_var , increment );
236
237    // update DQDT node level 0
238    hal_atomic_add( &cluster->dqdt_tbl[0].pages , increment );
239}
240
241////////////////////////////////////////////////////////////////////////////////
242// This recursive function is called by both the dqdt_get_cluster_for_process()
243// and by the dqdt_get_cluster_for_memory() functions to select the cluster
244// with smallest number of thread, or smallest number of allocated pages.
245// It traverses the quad tree from root to clusters.
246///////////////////////////////////////////////////////////////////////////////
247static cxy_t dqdt_select_cluster( xptr_t node,
248                                  bool_t for_memory )
249{
250    dqdt_node_t   node_copy;     // local copy of the current DQDT node
251    uint32_t      i;             // index in the loop on children
252    uint32_t      select;        // index of selected child
253    xptr_t        child;         // extended pointer on a DQDT child node
254    cxy_t         cxy;           // DQDT child node cluster identifier
255    dqdt_node_t * ptr;           // pointer on a DQDT child node
256    uint32_t      load;          // load of the child (threads or pages)
257    uint32_t      load_min;      // current value of the minimal load
258
259    // get DQDT node local copy
260    hal_remote_memcpy( XPTR( local_cxy , &node_copy ), node , sizeof(dqdt_node_t) );
261
262    // return cluster identifier for a terminal mode
263    if( node_copy.level == 0 ) return GET_CXY(node);
264
265    // analyse load for all children in non terminal node
266    load_min = 0xFFFFFFFF;
267    select   = 0;
268    for( i = 0 ; i < 4 ; i++ )
269    {
270        child = node_copy.children[i];
271        if( child != XPTR_NULL )
272        {
273            cxy  = (cxy_t)GET_CXY( child );
274            ptr  = (dqdt_node_t *)GET_PTR( child );
275            if( for_memory ) load = hal_remote_lw( XPTR( cxy , &ptr->pages ) );
276            else             load = hal_remote_lw( XPTR( cxy , &ptr->threads ) );
277            if( load < load_min )
278            {
279                load_min = load;
280                select   = i;
281            }
282        }
283    }
284
285    // select the child with the lowest load
286    return dqdt_select_cluster( node_copy.children[select], for_memory );
287}
288
289////////////////////////////////////
290cxy_t dqdt_get_cluster_for_process()
291{
292    // build extended pointer on DQDT root node
293        cluster_t * cluster = LOCAL_CLUSTER;
294    uint32_t    level   = cluster->dqdt_root_level;
295    xptr_t      root    = XPTR( 0 , &cluster->dqdt_tbl[level] );
296
297    // call recursive function
298    return dqdt_select_cluster( root , false );
299}
300
301////////////////////////////////////
302cxy_t dqdt_get_cluster_for_memory()
303{
304    // build extended pointer on DQDT root node
305        cluster_t * cluster = LOCAL_CLUSTER;
306    uint32_t    level   = cluster->dqdt_root_level;
307    xptr_t      root    = XPTR( 0 , &cluster->dqdt_tbl[level] );
308
309    // call recursive function
310    return dqdt_select_cluster( root , true );
311}
312
Note: See TracBrowser for help on using the repository browser.