Index: ft/giet_vm/giet_libs/barrier.c =================================================================== --- /soft/giet_vm/giet_libs/barrier.c (revision 500) +++ (revision ) @@ -1,409 +1,0 @@ -////////////////////////////////////////////////////////////////////////////////// -// File : barrier.c -// Date : 01/04/2012 -// Author : alain greiner -// Copyright (c) UPMC-LIP6 -/////////////////////////////////////////////////////////////////////////////////// - -#include "barrier.h" -#include "malloc.h" -#include "stdio.h" -#include "giet_config.h" - -/////////////////////////////////////////////////////////////////////////////////// -// Simple barrier access functions -/////////////////////////////////////////////////////////////////////////////////// - -/////////////////////////////////////////// -void barrier_init( giet_barrier_t* barrier, - unsigned int ntasks ) -{ - barrier->ntasks = ntasks; - barrier->count = ntasks; - barrier->sense = 0; - - asm volatile ("sync" ::: "memory"); -} - -//////////////////////////////////////////// -void barrier_wait( giet_barrier_t* barrier ) -{ - -#if GIET_DEBUG_USER_BARRIER -unsigned int x; -unsigned int y; -unsigned int p; -giet_proc_xyp( &x, &y, &p ); -giet_shr_printf("[DEBUG BARRIER] proc[%d,%d,%d] enters barrier_wait()\n", x, y, p ); -#endif - - // compute expected sense value - unsigned int expected; - if ( barrier->sense == 0 ) expected = 1; - else expected = 0; - - // parallel decrement barrier counter using atomic instructions LL/SC - // - input : pointer on the barrier counter (pcount) - // - output : counter value (count) - volatile unsigned int* pcount = (unsigned int *)&barrier->count; - volatile unsigned int count = 0; // avoid a warning - - asm volatile( "addu $2, %1, $0 \n" - "barrier_llsc: \n" - "ll $8, 0($2) \n" - "addi $9, $8, -1 \n" - "sc $9, 0($2) \n" - "beqz $9, barrier_llsc \n" - "addu %0, $8, $0 \n" - : "=r" (count) - : "r" (pcount) - : "$2", "$8", "$9", "memory" ); - - // the last task re-initializes count and toggle sense, - // waking up all other waiting tasks - if (count == 1) // last task - { - barrier->count = barrier->ntasks; - barrier->sense = expected; - } - else // other tasks busy waiting the sense flag - { - // polling sense flag - // input: pointer on the sens flag (psense) - // input: expected sense value (expected) - volatile unsigned int* psense = (unsigned int *)&barrier->sense; - asm volatile ( "barrier_sense: \n" - "lw $3, 0(%0) \n" - "bne $3, %1, barrier_sense \n" - : - : "r"(psense), "r"(expected) - : "$3" ); - } - - asm volatile ("sync" ::: "memory"); - -#if GIET_DEBUG_USER_BARRIER -giet_shr_printf("[DEBUG BARRIER] proc[%d,%d,%d] exit barrier_wait()\n", x, y, p ); -#endif - -} - -/////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////// -// SBT barrier access functions -/////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////// - - -//////////////////////////////////////////////////// -void sbt_barrier_init( giet_sbt_barrier_t* barrier, - unsigned int nclusters, // number of clusters - unsigned int ntasks ) // tasks per clusters -{ - unsigned int x; // x coordinate for one SBT node - unsigned int y; // y coordinate for one SBT node - unsigned int l; // level for one SBT node - unsigned int x_size; // max number of clusters in a row for the SBT - unsigned int y_size; // max number of clusters in a column for the SBT - unsigned int levels; // depth of the SBT (number of levels) - - // compute SBT characteristics - if ( nclusters == 1 ) // mesh 1*1 - { - x_size = 1; - y_size = 1; - levels = 1; - } - else if ( nclusters == 2 ) // mesh 2*1 - { - x_size = 2; - y_size = 1; - levels = 2; - } - else if ( nclusters == 4 ) // mesh 2*2 - { - x_size = 2; - y_size = 2; - levels = 3; - } - else if ( nclusters == 8 ) // mesh 4*2 - { - x_size = 4; - y_size = 2; - levels = 4; - } - else if ( nclusters == 16 ) // mesh 4*4 - { - x_size = 4; - y_size = 4; - levels = 5; - } - else if ( nclusters == 32 ) // mesh 8*4 - { - x_size = 8; - y_size = 4; - levels = 6; - } - else if ( nclusters == 64 ) // mesh 8*8 - { - x_size = 8; - y_size = 8; - levels = 7; - } - else if ( nclusters == 128 ) // mesh 16*8 - { - x_size = 16; - y_size = 8; - levels = 8; - } - else if ( nclusters == 256 ) // mesh 16*16 - { - x_size = 16; - y_size = 16; - levels = 9; - } - else - { - x_size = 0; // avoid warning - y_size = 0; - levels = 0; - giet_exit("error in tree_barrier_init() : nclusters must be power of 2\n"); - } - - // ntasks initialisation - barrier->ntasks = ntasks * nclusters; - -#if GIET_DEBUG_USER_BARRIER -giet_shr_printf("\n[DEBUG BARRIER] sbt_nodes allocation / ntasks = %d\n", ntasks ); -#endif - - // allocates memory for the SBT nodes and initializes SBT nodes pointers array - // the number of SBT nodes in a cluster(x,y) depends on (x,y). - // At least 1 node / at most 9 nodes - for ( x = 0 ; x < x_size ; x++ ) - { - for ( y = 0 ; y < y_size ; y++ ) - { - for ( l = 0 ; l < levels ; l++ ) // level 0 nodes - { - - if ( ( (l == 0) && ((x&0x00) == 0) && ((y&0x00) == 0) ) || - ( (l == 1) && ((x&0x01) == 0) && ((y&0x00) == 0) ) || - ( (l == 2) && ((x&0x01) == 0) && ((y&0x01) == 0) ) || - ( (l == 3) && ((x&0x03) == 0) && ((y&0x01) == 0) ) || - ( (l == 4) && ((x&0x03) == 0) && ((y&0x03) == 0) ) || - ( (l == 5) && ((x&0x07) == 0) && ((y&0x03) == 0) ) || - ( (l == 6) && ((x&0x07) == 0) && ((y&0x07) == 0) ) || - ( (l == 7) && ((x&0x0F) == 0) && ((y&0x07) == 0) ) || - ( (l == 8) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) ) - { - barrier->node[x][y][l] = remote_malloc( sizeof(sbt_node_t), x, y ); - -#if GIET_DEBUG_USER_BARRIER -giet_shr_printf("[DEBUG SBT] node[%d][%d][%d] : vaddr = %x\n", - x, y, l, (unsigned int)barrier->node[x][y][l] ); -#endif - } - } - } - } - -#if GIET_DEBUG_USER_BARRIER -giet_shr_printf("\n[DEBUG SBT] SBT nodes initialisation\n"); -#endif - - // recursively initialize all SBT nodes from root to bottom - sbt_build( barrier, 0, 0, levels-1, NULL, ntasks ); - - asm volatile ("sync" ::: "memory"); -} - -//////////////////////////////////////////////////// -void sbt_barrier_wait( giet_sbt_barrier_t* barrier ) -{ - // compute cluster coordinates for the calling task - unsigned int x; - unsigned int y; - unsigned int lpid; - giet_proc_xyp( &x, &y, &lpid ); - - // recursively decrement count from bottom to root - sbt_decrement( barrier->node[x][y][0] ); - - asm volatile ("sync" ::: "memory"); -} - - -///////////////////////////////////////////// -void sbt_build( giet_sbt_barrier_t* barrier, - unsigned int x, - unsigned int y, - unsigned int level, - sbt_node_t* parent, - unsigned int ntasks ) -{ - // This recursive function initializes the SBT notes - // traversing the SBT from root to bottom - - // get target node address - sbt_node_t* node = barrier->node[x][y][level]; - - if (level == 0 ) // terminal case - { - // initializes target node - node->arity = ntasks; - node->count = ntasks; - node->sense = 0; - node->level = 0; - node->parent = parent; - node->child0 = NULL; - node->child1 = NULL; - -#if GIET_DEBUG_USER_BARRIER -giet_shr_printf("[DEBUG BARRIER] initialize sbt_node[%d][%d][%d] :" - " arity = %d / child0 = %x / child1 = %x\n", - x, y, level, - node->arity, node->child0, node->child1 ); -#endif - - } - else // non terminal case - { - unsigned int x0; // x coordinate for child0 - unsigned int y0; // y coordinate for child0; - unsigned int x1; // x coordinate for child1; - unsigned int y1; // y coordinate for child1; - - // the child0 coordinates are equal to the parent coordinates - // the child1 coordinates are incremented depending on the level value - if ( level & 0x1 ) // odd level => X binary tree - { - x0 = x; - y0 = y; - x1 = x + (1 << ((level-1)>>1)); - y1 = y; - } - else // even level => Y binary tree - { - x0 = x; - y0 = y; - x1 = x; - y1 = y + (1 << ((level-1)>>1)); - } - - // initializes target node - node->arity = 2; - node->count = 2; - node->sense = 0; - node->level = level; - node->parent = parent; - node->child0 = barrier->node[x0][y0][level-1]; - node->child1 = barrier->node[x1][y1][level-1]; - -#if GIET_DEBUG_USER_BARRIER -giet_shr_printf("[DEBUG BARRIER] initialize sbt_node[%d][%d][%d] :" - " arity = %d / child0 = %x / child1 = %x\n", - x, y, level, - node->arity, node->child0, node->child1 ); -#endif - - // recursive calls for children nodes - sbt_build( barrier , x0 , y0 , level-1 , node , ntasks ); - sbt_build( barrier , x1 , y1 , level-1 , node , ntasks ); - } - -} // end sbt_build() - - -/////////////////////////////////////// -void sbt_decrement( sbt_node_t* node ) -{ - // This recursive function decrements the distributed "count" variables, - // traversing the SBT from bottom to root. - - // compute expected sense value (toggle) - unsigned int expected; - if ( node->sense == 0) expected = 1; - else expected = 0; - - // atomic decrement - // - input : count address (pcount) - // - output : modified counter value (count) - unsigned int* pcount = (unsigned int*)&node->count; - unsigned int count = 0; // avoid a warning - - asm volatile( "addu $2, %1, $0 \n" - "sbt_llsc: \n" - "ll $8, 0($2) \n" - "addi $9, $8, -1 \n" - "sc $9, 0($2) \n" - "beqz $9, sbt_llsc \n" - "addu %0, $8, $0 \n" - : "=r" (count) - : "r" (pcount) - : "$2", "$8", "$9", "memory" ); - - if ( count == 1 ) // last task for this level - { - if ( node->parent == NULL ) // root node : call sbt_release() - { - sbt_release( node, expected ); - } - else // call sbt_decrement() for parent - { - sbt_decrement( node->parent ); - } - } - else // not the last: busy waiting on current "sense" flag - { - // polling sense flag - // input: pointer on the sens flag (psense) - // input: expected sense value (expected) - volatile unsigned int* psense = (unsigned int *)&node->sense; - asm volatile ( "sbt_sense: \n" - "lw $3, 0(%0) \n" - "bne $3, %1, sbt_sense \n" - : - : "r"(psense), "r"(expected) - : "$3" ); - } -} // end sbt_decrement() - - -/////////////////////////////////// -void sbt_release( sbt_node_t* node, - unsigned int expected ) -{ - // This recursive function reset all sense and count variables - // traversing the SBT from root to bottom - - // toggle sense flag for the target node - node->sense = expected; - - // re-initialise count for the target node - node->count = node->arity; - - // call recursively sbt_release() for children if not terminal - if ( node->level > 0 ) - { - sbt_release( node->child0, expected ); - sbt_release( node->child1, expected ); - } -} // end sbt_release() - -// Local Variables: -// tab-width: 4 -// c-basic-offset: 4 -// c-file-offsets:((innamespace . 0)(inline-open . 0)) -// indent-tabs-mode: nil -// End: -// vim: filetype=c:expandtab:shiftwidth=4:tabsroot=4:softtabsroot=4 - -// Local Variables: -// tab-width: 4 -// c-basic-offset: 4 -// c-file-offsets:((innamespace . 0)(inline-open . 0)) -// indent-tabs-mode: nil -// End: -// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 - Index: ft/giet_vm/giet_libs/barrier.h =================================================================== --- /soft/giet_vm/giet_libs/barrier.h (revision 500) +++ (revision ) @@ -1,115 +1,0 @@ -////////////////////////////////////////////////////////////////////////////////// -// File : barrier.h -// Date : 01/04/2012 -// Author : alain greiner -// Copyright (c) UPMC-LIP6 -/////////////////////////////////////////////////////////////////////////////////// -// The barrier.c and barrier.h files are part of the GIET-VM nano-kernel. -// This user-level library provides a synchronisation service between several -// tasks sharing the same address space in a parallel multi-tasks application. -// -// There is actually two types of barriers: -// 1) The "giet_barrier_t" is a simple sense-reversing barrier. -// It can be safely used several times (in a loop for example), -// but it does not scale, and should not be used when the number -// of tasks is larger than few tens. -// -// 2) The giet_sbt_barrier_t" can be used in multi-clusters architectures, -// and is implemented as a physically distributed Sliced-Binary-Tree (SBT). -// WARNING: The following placement constraints must be respected: -// - The number of involved clusters must be a power of 2. -// - The number of involved tasks in a cluster is the same in all clusters. -// - The involved clusters form a mesh[N][N] or a mesh[N][N/2] -// - The lower left involved cluster is cluster(0,0) -// -// Neither the barrier_init(), nor the barrier_wait() function require a syscall. -// For both types of barriers, the barrier initialisation should be done by -// one single task. -/////////////////////////////////////////////////////////////////////////////////// - -#ifndef _BARRIER_H_ -#define _BARRIER_H_ - -#include "hard_config.h" - -/////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////// -// simple barrier structure and access functions -/////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////// - -typedef struct giet_barrier_s -{ - char name[32]; // barrier name - unsigned int sense; // barrier state (toggle) - unsigned int ntasks; // total number of expected tasks - unsigned int count; // number of not arrived tasks -} giet_barrier_t; - -/////////////////////////////////////////////////// -extern void barrier_init( giet_barrier_t* barrier, - unsigned int ntasks ); - -//////////////////////////////////////////////////// -extern void barrier_wait( giet_barrier_t* barrier ); - -/////////////////////////////////////////////////////////////////////////////////// -////////////////////////////////////////////////////////////////////////////////// -// SBT barrier structures and access functions -////////////////////////////////////////////////////////////////////////////////// -////////////////////////////////////////////////////////////////////////////////// - -typedef struct sbt_node_s -{ - unsigned int arity; // number of children (must be 2 or 4) - unsigned int count; // number of not arrived children - unsigned int sense; // barrier state (toggle) - unsigned int level; // hierarchical level (0 is bottom) - struct sbt_node_s* parent; // pointer on parent node (NULL for root) - struct sbt_node_s* child0; // pointer on children node - struct sbt_node_s* child1; // pointer on children node - unsigned int padding; // for 32 bytes alignment -} sbt_node_t; - -typedef struct giet_sbt_barrier_s -{ - char name[32]; // barrier name - unsigned int ntasks; // total number of expected tasks - sbt_node_t* node[X_SIZE][Y_SIZE][9]; // array of pointers on SBT nodes -} giet_sbt_barrier_t; - -/////////////////////////////////////////////////////////// -extern void sbt_barrier_init( giet_sbt_barrier_t* barrier, - unsigned int nclusters, - unsigned int ntasks ); - -///////////////////////////////////////////////////////////// -extern void sbt_barrier_wait( giet_sbt_barrier_t* barrier ); - -///////////////////////////////////////////// -void sbt_build( giet_sbt_barrier_t* barrier, - unsigned int x, - unsigned int y, - unsigned int level, - sbt_node_t* parent, - unsigned int ntasks ); - -/////////////////////////////////////// -void sbt_decrement( sbt_node_t* node ); - -/////////////////////////////////// -void sbt_release( sbt_node_t* node, - unsigned int expected ); - - - -#endif - -// Local Variables: -// tab-width: 4 -// c-basic-offset: 4 -// c-file-offsets:((innamespace . 0)(inline-open . 0)) -// indent-tabs-mode: nil -// End: -// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 - Index: /soft/giet_vm/giet_libs/stdio.c =================================================================== --- /soft/giet_vm/giet_libs/stdio.c (revision 500) +++ /soft/giet_vm/giet_libs/stdio.c (revision 501) @@ -253,18 +253,17 @@ { va_list args; - const int channel = 0; volatile unsigned int sr_save; sys_call( SYSCALL_TTY_GET_LOCK, - channel, + 0, (unsigned int)&sr_save, 0, 0 ); va_start( args, format ); - int ret = __printf(format, channel, &args); + int ret = __printf(format, 0, &args); va_end( args ); sys_call( SYSCALL_TTY_RELEASE_LOCK, - channel, + 0, (unsigned int)&sr_save, 0, 0 ); @@ -541,10 +540,13 @@ ////////////////////////////////////////////////////////////////////////////////// -//////////////////////////////// -unsigned int giet_nic_rx_alloc() +//////////////////////////////////////////////////// +unsigned int giet_nic_rx_alloc( unsigned int xmax, + unsigned int ymax ) { int channel = sys_call( SYSCALL_NIC_ALLOC, 1, - 0, 0, 0 ); + xmax, + ymax, + 0 ); if ( channel < 0 ) giet_exit("error in giet_nic_rx_alloc()"); @@ -552,10 +554,13 @@ } -//////////////////////////////// -unsigned int giet_nic_tx_alloc() +//////////////////////////////////////////////////// +unsigned int giet_nic_tx_alloc( unsigned int xmax, + unsigned int ymax ) { int channel = sys_call( SYSCALL_NIC_ALLOC, - 0, - 0, 0, 0 ); + 0, + xmax, + ymax, + 0 ); if ( channel < 0 ) giet_exit("error in giet_nic_tx_alloc()"); @@ -772,12 +777,14 @@ } -/////////////////////////////////////////////// -void giet_proc_number( unsigned int cluster_id, - unsigned int* buffer ) -{ - if ( sys_call( SYSCALL_PROC_NUMBER, - cluster_id, - (unsigned int) buffer, - 0, 0) ) giet_exit("ERROR in giet_proc_number()"); +///////////////////////////////////////////////// +void giet_procs_number( unsigned int* x_size, + unsigned int* y_size, + unsigned int* nprocs ) +{ + if ( sys_call( SYSCALL_PROCS_NUMBER, + (unsigned int)x_size, + (unsigned int)y_size, + (unsigned int)nprocs, + 0 ) ) giet_exit("ERROR in giet_procs_number()"); } Index: /soft/giet_vm/giet_libs/stdio.h =================================================================== --- /soft/giet_vm/giet_libs/stdio.h (revision 500) +++ /soft/giet_vm/giet_libs/stdio.h (revision 501) @@ -31,5 +31,5 @@ #define SYSCALL_FBF_CMA_STOP 0x0D #define SYSCALL_EXIT 0x0E -#define SYSCALL_PROC_NUMBER 0x0F +#define SYSCALL_PROCS_NUMBER 0x0F #define SYSCALL_FBF_SYNC_WRITE 0x10 @@ -212,7 +212,7 @@ ////////////////////////////////////////////////////////////////////////// -extern unsigned int giet_nic_rx_alloc(); - -extern unsigned int giet_nic_tx_alloc(); +extern unsigned int giet_nic_rx_alloc( unsigned int xmax, unsigned int ymax ); + +extern unsigned int giet_nic_tx_alloc( unsigned int xmax, unsigned int ymax ); extern void giet_nic_rx_start( unsigned int channel ); @@ -272,6 +272,7 @@ extern void giet_context_switch(); -extern void giet_procnumber( unsigned int cluster_xy, - unsigned int buffer ); +extern void giet_procs_number( unsigned int* x_size, + unsigned int* y_size, + unsigned int* nprocs ); extern void giet_vobj_get_vbase( char* vspace_name, Index: /soft/giet_vm/giet_libs/user_barrier.c =================================================================== --- /soft/giet_vm/giet_libs/user_barrier.c (revision 501) +++ /soft/giet_vm/giet_libs/user_barrier.c (revision 501) @@ -0,0 +1,381 @@ +////////////////////////////////////////////////////////////////////////////////// +// File : user_barrier.c +// Date : 01/04/2012 +// Author : alain greiner +// Copyright (c) UPMC-LIP6 +/////////////////////////////////////////////////////////////////////////////////// + +#include "user_barrier.h" +#include "malloc.h" +#include "stdio.h" +#include "giet_config.h" + +/////////////////////////////////////////////////////////////////////////////////// +// Simple barrier access functions +/////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////// +void barrier_init( giet_barrier_t* barrier, + unsigned int ntasks ) +{ + barrier->arity = ntasks; + barrier->count = ntasks; + barrier->sense = 0; + + asm volatile ("sync" ::: "memory"); +} + +//////////////////////////////////////////// +void barrier_wait( giet_barrier_t* barrier ) +{ + +#if GIET_DEBUG_USER_BARRIER +unsigned int x; +unsigned int y; +unsigned int p; +giet_proc_xyp( &x, &y, &p ); +giet_shr_printf("[DEBUG USER BARRIER] proc[%d,%d,%d] enters barrier_wait()\n", + x, y, p ); +#endif + + // compute expected sense value + unsigned int expected; + if ( barrier->sense == 0 ) expected = 1; + else expected = 0; + + // parallel decrement barrier counter using atomic instructions LL/SC + // - input : pointer on the barrier counter (pcount) + // - output : counter value (count) + volatile unsigned int* pcount = (unsigned int *)&barrier->count; + volatile unsigned int count = 0; // avoid a warning + + asm volatile( "addu $2, %1, $0 \n" + "barrier_llsc: \n" + "ll $8, 0($2) \n" + "addi $9, $8, -1 \n" + "sc $9, 0($2) \n" + "beqz $9, barrier_llsc \n" + "addu %0, $8, $0 \n" + : "=r" (count) + : "r" (pcount) + : "$2", "$8", "$9", "memory" ); + + // the last task re-initializes count and toggle sense, + // waking up all other waiting tasks + if (count == 1) // last task + { + barrier->count = barrier->arity; + barrier->sense = expected; + } + else // other tasks busy waiting the sense flag + { + // polling sense flag + // input: pointer on the sens flag (psense) + // input: expected sense value (expected) + unsigned int* psense = (unsigned int *)&barrier->sense; + asm volatile ( "barrier_sense: \n" + "lw $3, 0(%0) \n" + "bne $3, %1, barrier_sense \n" + : + : "r"(psense), "r"(expected) + : "$3" ); + } + + asm volatile ("sync" ::: "memory"); + +#if GIET_DEBUG_USER_BARRIER +giet_shr_printf("[DEBUG USER BARRIER] proc[%d,%d,%d] exit barrier_wait()\n", + x, y, p ); +#endif + +} + +/////////////////////////////////////////////////////////////////////////////////// +// SQT barrier access functions +/////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////// +static +void sqt_barrier_build( giet_sqt_barrier_t* barrier, + unsigned int x, + unsigned int y, + unsigned int level, + sqt_node_t* parent, + unsigned int x_size, + unsigned int y_size, + unsigned int ntasks ) +{ + // This recursive function initializes the SQT nodes + // traversing the SQT from root to bottom + + // get target node address + sqt_node_t* node = barrier->node[x][y][level]; + + if (level == 0 ) // terminal case + { + // initializes target node + node->arity = ntasks; + node->count = ntasks; + node->sense = 0; + node->level = 0; + node->parent = parent; + node->child[0] = NULL; + node->child[1] = NULL; + node->child[2] = NULL; + node->child[3] = NULL; + +#if GIET_DEBUG_USER_BARRIER +giet_shr_printf("[DEBUG USER BARRIER] initialize sqt_node[%d][%d][%d] : arity = %d\n" + " parent = %x / child0 = %x / child1 = %x / child0 = %x / child1 = %x\n", + x, y, level, node->arity, + (unsigned int)node->parent, + (unsigned int)node->child[0], + (unsigned int)node->child[1], + (unsigned int)node->child[2], + (unsigned int)node->child[3] ); +#endif + + } + else // non terminal case + { + unsigned int cx[4]; // x coordinate for children + unsigned int cy[4]; // y coordinate for children + unsigned int arity = 0; + unsigned int i; + + // the child0 coordinates are equal to the parent coordinates + // other children coordinates are incremented depending on the level value + cx[0] = x; + cy[0] = y; + + cx[1] = x + (1 << (level-1)); + cy[1] = y; + + cx[2] = x; + cy[2] = y + (1 << (level-1)); + + cx[3] = x + (1 << (level-1)); + cy[3] = y + (1 << (level-1)); + + // initializes target node + for ( i = 0 ; i < 4 ; i++ ) + { + if ( (cx[i] < x_size) && (cy[i] < y_size) ) + { + node->child[i] = barrier->node[cx[i]][cy[i]][level-1]; + arity++; + } + else node->child[i] = NULL; + } + node->arity = arity; + node->count = arity; + node->sense = 0; + node->level = level; + node->parent = parent; + +#if GIET_DEBUG_USER_BARRIER +giet_shr_printf("[DEBUG USER BARRIER] initialize sqt_node[%d][%d][%d] : arity = %d\n" + " parent = %x / child0 = %x / child1 = %x / child0 = %x / child1 = %x\n", + x, y, level, node->arity, + (unsigned int)node->parent, + (unsigned int)node->child[0], + (unsigned int)node->child[1], + (unsigned int)node->child[2], + (unsigned int)node->child[3] ); +#endif + + // recursive calls for children nodes + for ( i = 0 ; i < 4 ; i++ ) + { + if ( (cx[i] < x_size) && (cy[i] < y_size) ) + sqt_barrier_build( barrier, + cx[i], + cy[i], + level-1, + node, + x_size, + y_size, + ntasks ); + } + } +} // end sqt_barrier_build() + +//////////////////////////////////////////////////// +void sqt_barrier_init( giet_sqt_barrier_t* barrier, + unsigned int x_size, // number of clusters in a row + unsigned int y_size, // number of clusters in a col + unsigned int ntasks ) // tasks per clusters +{ + // check parameters + if ( x_size > 16 ) giet_exit("SQT BARRIER ERROR : x_size too large"); + if ( y_size > 16 ) giet_exit("SQT BARRIER ERROR : y_size too large"); + if ( ntasks > 8 ) giet_exit("SQT BARRIER ERROR : ntasks too large"); + + // compute SQT levels + unsigned int levels; + unsigned int side; + unsigned int z = (x_size > y_size) ? x_size : y_size; + levels = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 3 : (z < 9) ? 4 : 5; + side = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 4 : (z < 9) ? 8 : 16; + +#if GIET_DEBUG_USER_BARRIER +giet_shr_printf("\n[DEBUG USER BARRIER] sqt_nodes allocation\n" + " x_size = %d / y_size = %d / levels = %d / side = %d\n", + x_size , y_size , levels , side ); +#endif + + // allocates memory for the SQT nodes and initializes SQT nodes pointers array + // the number of SQT nodes in a cluster(x,y) depends on (x,y): + // At least 1 node / at most 5 nodes + unsigned int x; // x coordinate for one SQT node + unsigned int y; // y coordinate for one SQT node + unsigned int l; // level for one SQT node + for ( x = 0 ; x < x_size ; x++ ) + { + for ( y = 0 ; y < y_size ; y++ ) + { + for ( l = 0 ; l < levels ; l++ ) + { + + if ( ( (l == 0) && ((x&0x00) == 0) && ((y&0x00) == 0) ) || + ( (l == 1) && ((x&0x01) == 0) && ((y&0x01) == 0) ) || + ( (l == 2) && ((x&0x03) == 0) && ((y&0x03) == 0) ) || + ( (l == 3) && ((x&0x07) == 0) && ((y&0x07) == 0) ) || + ( (l == 4) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) ) + { + barrier->node[x][y][l] = remote_malloc( sizeof(sqt_node_t), + x, y ); + +#if GIET_DEBUG_USER_BARRIER +giet_shr_printf("[DEBUG USER BARRIER] SQT node[%d][%d][%d] : vaddr = %x\n", + x, y, l, (unsigned int)barrier->node[x][y][l] ); +#endif + } + } + } + } + + // recursively initialize all SQT nodes from root to bottom + sqt_barrier_build( barrier, + 0, + 0, + levels-1, + NULL, + x_size, + y_size, + ntasks ); + + asm volatile ("sync" ::: "memory"); + +} // end sqt_barrier_init + + + +/////////////////////////////////////// +static +void sqt_barrier_decrement( sqt_node_t* node ) +{ + // This recursive function decrements the distributed "count" variables, + // traversing the SQT from bottom to root. + // The last arrived task reset the local node before returning. + +#if GIET_DEBUG_USER_BARRIER +unsigned int px; +unsigned int py; +unsigned int pl; +giet_proc_xyp( &px, &py, &pl ); +giet_shr_printf("\n[DEBUG USER BARRIER] P[%d,%d,%d] decrement SQT barrier node %x :\n" + " level = %d / arity = %d / sense = %d / count = %d\n", + px , py , pl , (unsigned int)node , + node->level , node->arity , node->sense , node->count ); +#endif + + // compute expected sense value + unsigned int expected; + if ( node->sense == 0) expected = 1; + else expected = 0; + + // atomic decrement + // - input : count address (pcount) + // - output : modified counter value (count) + unsigned int* pcount = (unsigned int*)&node->count; + unsigned int count = 0; // avoid a warning + + asm volatile( "addu $2, %1, $0 \n" + "sqt_llsc: \n" + "ll $8, 0($2) \n" + "addi $9, $8, -1 \n" + "sc $9, 0($2) \n" + "beqz $9, sqt_llsc \n" + "addu %0, $8, $0 \n" + : "=r" (count) + : "r" (pcount) + : "$2", "$8", "$9", "memory" ); + + if ( count == 1 ) // last task + { + // decrement the parent node if the current node is not the root + if ( node->parent != NULL ) + sqt_barrier_decrement( node->parent ); + + // reset the current node + node->sense = expected; + node->count = node->arity; + +#if GIET_DEBUG_USER_BARRIER +giet_shr_printf("\n[DEBUG USER BARRIER] P[%d,%d,%d] reset SQT barrier node %x :\n" + " level = %d / arity = %d / sense = %d / count = %d\n", + px , py , pl , (unsigned int)node , + node->level , node->arity , node->sense , node->count ); +#endif + return; + } + else // not the last task + { + // poll sense flag + // input: pointer on the sens flag (psense) + // input: expected sense value (expected) + unsigned int* psense = (unsigned int *)&node->sense; + asm volatile ( "sqt_sense: \n" + "lw $3, 0(%0) \n" + "bne $3, %1, sqt_sense \n" + : + : "r"(psense), "r"(expected) + : "$3" ); + return; + } +} // end sqt_decrement() + +//////////////////////////////////////////////////// +void sqt_barrier_wait( giet_sqt_barrier_t* barrier ) +{ + // compute cluster coordinates for the calling task + unsigned int x; + unsigned int y; + unsigned int lpid; + giet_proc_xyp( &x, &y, &lpid ); + + // recursively decrement count from bottom to root + sqt_barrier_decrement( barrier->node[x][y][0] ); + + asm volatile ("sync" ::: "memory"); + +} // end sqt_barrier_wait() + + +// Local Variables: +// tab-width: 4 +// c-basic-offset: 4 +// c-file-offsets:((innamespace . 0)(inline-open . 0)) +// indent-tabs-mode: nil +// End: +// vim: filetype=c:expandtab:shiftwidth=4:tabsroot=4:softtabsroot=4 + +// Local Variables: +// tab-width: 4 +// c-basic-offset: 4 +// c-file-offsets:((innamespace . 0)(inline-open . 0)) +// indent-tabs-mode: nil +// End: +// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 + Index: /soft/giet_vm/giet_libs/user_barrier.h =================================================================== --- /soft/giet_vm/giet_libs/user_barrier.h (revision 501) +++ /soft/giet_vm/giet_libs/user_barrier.h (revision 501) @@ -0,0 +1,89 @@ +////////////////////////////////////////////////////////////////////////////////// +// File : user_barrier.h +// Date : 01/04/2012 +// Author : alain greiner +// Copyright (c) UPMC-LIP6 +/////////////////////////////////////////////////////////////////////////////////// +// The barrier.c and barrier.h files are part of the GIET-VM nano-kernel. +// This user-level library provides a synchronisation service between several +// tasks sharing the same address space in a parallel multi-tasks application. +// +// There is actually two types of barriers: +// 1) The "giet_barrier_t" is a simple sense-reversing barrier. +// It can be safely used several times (in a loop for example), +// but it does not scale, and should not be used when the number +// of tasks is larger than few tens. +// +// 2) The giet_sqt_barrier_t" can be used in multi-clusters architectures, +// and is implemented as a physically distributed Synchro-Quad-Tree (SQT). +// WARNING: The following placement constraints must be respected: +// - The number of involved tasks in a cluster is the same in all clusters. +// - The involved clusters form a mesh[x_size * y_size] +// - The lower left involved cluster is cluster(0,0) +// +// Neither the barrier_init(), nor the barrier_wait() function require a syscall. +// For both types of barriers, the barrier initialisation should be done by +// one single task. +/////////////////////////////////////////////////////////////////////////////////// + +#ifndef USER_BARRIER_H_ +#define USER_BARRIER_H_ + +/////////////////////////////////////////////////////////////////////////////////// +// simple barrier structure and access functions +/////////////////////////////////////////////////////////////////////////////////// + +typedef struct giet_barrier_s +{ + unsigned int sense; // barrier state (toggle) + unsigned int arity; // total number of expected tasks + unsigned int count; // number of not arrived tasks +} giet_barrier_t; + +/////////////////////////////////////////////////// +extern void barrier_init( giet_barrier_t* barrier, + unsigned int ntasks ); + +//////////////////////////////////////////////////// +extern void barrier_wait( giet_barrier_t* barrier ); + +////////////////////////////////////////////////////////////////////////////////// +// SQT barrier structures and access functions +////////////////////////////////////////////////////////////////////////////////// + +typedef struct sqt_node_s +{ + unsigned int arity; // number of expected tasks + unsigned int count; // number of not arrived tasks + unsigned int sense; // barrier state (toggle) + unsigned int level; // hierarchical level (0 is bottom) + struct sqt_node_s* parent; // pointer on parent node (NULL for root) + struct sqt_node_s* child[4]; // pointer on children node (NULL for bottom) + unsigned int padding[7]; // for 64 bytes alignment +} sqt_node_t; + +typedef struct giet_sqt_barrier_s +{ + sqt_node_t* node[16][16][5]; // array of pointers on SBT nodes +} giet_sqt_barrier_t; + +/////////////////////////////////////////////////////////// +extern void sqt_barrier_init( giet_sqt_barrier_t* barrier, + unsigned int x_size, + unsigned int y_size, + unsigned int ntasks ); + +///////////////////////////////////////////////////////////// +extern void sqt_barrier_wait( giet_sqt_barrier_t* barrier ); + + +#endif + +// Local Variables: +// tab-width: 4 +// c-basic-offset: 4 +// c-file-offsets:((innamespace . 0)(inline-open . 0)) +// indent-tabs-mode: nil +// End: +// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 + Index: /soft/giet_vm/giet_libs/user_lock.c =================================================================== --- /soft/giet_vm/giet_libs/user_lock.c (revision 500) +++ /soft/giet_vm/giet_libs/user_lock.c (revision 501) @@ -78,8 +78,7 @@ void lock_release( user_lock_t* lock ) { - unsigned int current = lock->current; + asm volatile( "sync" ); - if ( current == (GIET_LOCK_MAX_TICKET - 1) ) lock->current = 0; - else lock->current = current + 1; + lock->current = lock->current + 1; #if GIET_DEBUG_USER_LOCK