Context Navigation

source: soft/giet_vm/giet_libs/user_barrier.c @ 538

Last change on this file since 538 was 508, checked in by alain, 10 years ago
Cosmetic.
File size: 13.2 KB

Line
1	//////////////////////////////////////////////////////////////////////////////////
2	// File : user_barrier.c
3	// Date : 01/04/2012
4	// Author : alain greiner
5	// Copyright (c) UPMC-LIP6
6	///////////////////////////////////////////////////////////////////////////////////
7
8	#include "user_barrier.h"
9	#include "malloc.h"
10	#include "stdio.h"
11	#include "giet_config.h"
12
13	///////////////////////////////////////////////////////////////////////////////////
14	// Simple barrier access functions
15	///////////////////////////////////////////////////////////////////////////////////
16
17	///////////////////////////////////////////
18	void barrier_init( giet_barrier_t* barrier,
19	unsigned int ntasks )
20	{
21	barrier->arity = ntasks;
22	barrier->count = ntasks;
23	barrier->sense = 0;
24
25	asm volatile ("sync" ::: "memory");
26	}
27
28	////////////////////////////////////////////
29	void barrier_wait( giet_barrier_t* barrier )
30	{
31
32	#if GIET_DEBUG_USER_BARRIER
33	unsigned int x;
34	unsigned int y;
35	unsigned int p;
36	giet_proc_xyp( &x, &y, &p );
37	giet_shr_printf("[DEBUG USER BARRIER] proc[%d,%d,%d] enters barrier_wait()\n",
38	x, y, p );
39	#endif
40
41	// compute expected sense value
42	unsigned int expected;
43	if ( barrier->sense == 0 ) expected = 1;
44	else expected = 0;
45
46	// parallel decrement barrier counter using atomic instructions LL/SC
47	// - input : pointer on the barrier counter (pcount)
48	// - output : counter value (count)
49	volatile unsigned int* pcount = (unsigned int *)&barrier->count;
50	volatile unsigned int count = 0; // avoid a warning
51
52	asm volatile( "addu $2, %1, $0 \n"
53	"barrier_llsc: \n"
54	"ll $8, 0($2) \n"
55	"addi $9, $8, -1 \n"
56	"sc $9, 0($2) \n"
57	"beqz $9, barrier_llsc \n"
58	"addu %0, $8, $0 \n"
59	: "=r" (count)
60	: "r" (pcount)
61	: "$2", "$8", "$9", "memory" );
62
63	// the last task re-initializes count and toggle sense,
64	// waking up all other waiting tasks
65	if (count == 1) // last task
66	{
67	barrier->count = barrier->arity;
68	barrier->sense = expected;
69	}
70	else // other tasks busy waiting the sense flag
71	{
72	// polling sense flag
73	// input: pointer on the sens flag (psense)
74	// input: expected sense value (expected)
75	unsigned int* psense = (unsigned int *)&barrier->sense;
76	asm volatile ( "barrier_sense: \n"
77	"lw $3, 0(%0) \n"
78	"bne $3, %1, barrier_sense \n"
79	:
80	: "r"(psense), "r"(expected)
81	: "$3" );
82	}
83
84	asm volatile ("sync" ::: "memory");
85
86	#if GIET_DEBUG_USER_BARRIER
87	giet_shr_printf("[DEBUG USER BARRIER] proc[%d,%d,%d] exit barrier_wait()\n",
88	x, y, p );
89	#endif
90
91	}
92
93	///////////////////////////////////////////////////////////////////////////////////
94	// SQT barrier access functions
95	///////////////////////////////////////////////////////////////////////////////////
96
97	///////////////////////////////////////////////////
98	static
99	void sqt_barrier_build( giet_sqt_barrier_t* barrier,
100	unsigned int x,
101	unsigned int y,
102	unsigned int level,
103	sqt_node_t* parent,
104	unsigned int x_size,
105	unsigned int y_size,
106	unsigned int ntasks )
107	{
108	// This recursive function initializes the SQT nodes
109	// traversing the SQT from root to bottom
110
111	// get target node address
112	sqt_node_t* node = barrier->node[x][y][level];
113
114	if (level == 0 ) // terminal case
115	{
116	// initializes target node
117	node->arity = ntasks;
118	node->count = ntasks;
119	node->sense = 0;
120	node->level = 0;
121	node->parent = parent;
122	node->child[0] = NULL;
123	node->child[1] = NULL;
124	node->child[2] = NULL;
125	node->child[3] = NULL;
126
127	#if GIET_DEBUG_USER_BARRIER
128	giet_shr_printf("[DEBUG USER BARRIER] initialize sqt_node[%d][%d][%d] : arity = %d\n"
129	" parent = %x / child0 = %x / child1 = %x / child2 = %x / child3 = %x\n",
130	x, y, level, node->arity,
131	(unsigned int)node->parent,
132	(unsigned int)node->child[0],
133	(unsigned int)node->child[1],
134	(unsigned int)node->child[2],
135	(unsigned int)node->child[3] );
136	#endif
137
138	}
139	else // non terminal case
140	{
141	unsigned int cx[4]; // x coordinate for children
142	unsigned int cy[4]; // y coordinate for children
143	unsigned int arity = 0;
144	unsigned int i;
145
146	// the child0 coordinates are equal to the parent coordinates
147	// other children coordinates are incremented depending on the level value
148	cx[0] = x;
149	cy[0] = y;
150
151	cx[1] = x + (1 << (level-1));
152	cy[1] = y;
153
154	cx[2] = x;
155	cy[2] = y + (1 << (level-1));
156
157	cx[3] = x + (1 << (level-1));
158	cy[3] = y + (1 << (level-1));
159
160	// initializes target node
161	for ( i = 0 ; i < 4 ; i++ )
162	{
163	if ( (cx[i] < x_size) && (cy[i] < y_size) )
164	{
165	node->child[i] = barrier->node[cx[i]][cy[i]][level-1];
166	arity++;
167	}
168	else node->child[i] = NULL;
169	}
170	node->arity = arity;
171	node->count = arity;
172	node->sense = 0;
173	node->level = level;
174	node->parent = parent;
175
176	#if GIET_DEBUG_USER_BARRIER
177	giet_shr_printf("[DEBUG USER BARRIER] initialize sqt_node[%d][%d][%d] : arity = %d\n"
178	" parent = %x / child0 = %x / child1 = %x / child0 = %x / child1 = %x\n",
179	x, y, level, node->arity,
180	(unsigned int)node->parent,
181	(unsigned int)node->child[0],
182	(unsigned int)node->child[1],
183	(unsigned int)node->child[2],
184	(unsigned int)node->child[3] );
185	#endif
186
187	// recursive calls for children nodes
188	for ( i = 0 ; i < 4 ; i++ )
189	{
190	if ( (cx[i] < x_size) && (cy[i] < y_size) )
191	sqt_barrier_build( barrier,
192	cx[i],
193	cy[i],
194	level-1,
195	node,
196	x_size,
197	y_size,
198	ntasks );
199	}
200	}
201	} // end sqt_barrier_build()
202
203	////////////////////////////////////////////////////
204	void sqt_barrier_init( giet_sqt_barrier_t* barrier,
205	unsigned int x_size, // number of clusters in a row
206	unsigned int y_size, // number of clusters in a col
207	unsigned int ntasks ) // tasks per clusters
208	{
209	// check parameters
210	if ( x_size > 16 ) giet_exit("SQT BARRIER ERROR : x_size too large");
211	if ( y_size > 16 ) giet_exit("SQT BARRIER ERROR : y_size too large");
212	if ( ntasks > 8 ) giet_exit("SQT BARRIER ERROR : ntasks too large");
213
214	// compute SQT levels
215	unsigned int levels;
216	unsigned int side;
217	unsigned int z = (x_size > y_size) ? x_size : y_size;
218	levels = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 3 : (z < 9) ? 4 : 5;
219	side = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 4 : (z < 9) ? 8 : 16;
220
221	#if GIET_DEBUG_USER_BARRIER
222	giet_shr_printf("\n[DEBUG USER BARRIER] sqt_nodes allocation\n"
223	" x_size = %d / y_size = %d / levels = %d / side = %d\n",
224	x_size , y_size , levels , side );
225	#endif
226
227	// allocates memory for the SQT nodes and initializes SQT nodes pointers array
228	// the number of SQT nodes in a cluster(x,y) depends on (x,y):
229	// At least 1 node / at most 5 nodes
230	unsigned int x; // x coordinate for one SQT node
231	unsigned int y; // y coordinate for one SQT node
232	unsigned int l; // level for one SQT node
233	for ( x = 0 ; x < x_size ; x++ )
234	{
235	for ( y = 0 ; y < y_size ; y++ )
236	{
237	for ( l = 0 ; l < levels ; l++ )
238	{
239
240	if ( ( (l == 0) && ((x&0x00) == 0) && ((y&0x00) == 0) ) \|\|
241	( (l == 1) && ((x&0x01) == 0) && ((y&0x01) == 0) ) \|\|
242	( (l == 2) && ((x&0x03) == 0) && ((y&0x03) == 0) ) \|\|
243	( (l == 3) && ((x&0x07) == 0) && ((y&0x07) == 0) ) \|\|
244	( (l == 4) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) )
245	{
246	barrier->node[x][y][l] = remote_malloc( sizeof(sqt_node_t),
247	x, y );
248
249	#if GIET_DEBUG_USER_BARRIER
250	giet_shr_printf("[DEBUG USER BARRIER] SQT node[%d][%d][%d] : vaddr = %x\n",
251	x, y, l, (unsigned int)barrier->node[x][y][l] );
252	#endif
253	}
254	}
255	}
256	}
257
258	// recursively initialize all SQT nodes from root to bottom
259	sqt_barrier_build( barrier,
260	0,
261	0,
262	levels-1,
263	NULL,
264	x_size,
265	y_size,
266	ntasks );
267
268	asm volatile ("sync" ::: "memory");
269
270	} // end sqt_barrier_init
271
272
273
274	///////////////////////////////////////
275	static
276	void sqt_barrier_decrement( sqt_node_t* node )
277	{
278	// This recursive function decrements the distributed "count" variables,
279	// traversing the SQT from bottom to root.
280	// The last arrived task reset the local node before returning.
281
282	#if GIET_DEBUG_USER_BARRIER
283	unsigned int px;
284	unsigned int py;
285	unsigned int pl;
286	giet_proc_xyp( &px, &py, &pl );
287	giet_shr_printf("\n[DEBUG USER BARRIER] P[%d,%d,%d] decrement SQT barrier node %x :\n"
288	" level = %d / arity = %d / sense = %d / count = %d\n",
289	px , py , pl , (unsigned int)node ,
290	node->level , node->arity , node->sense , node->count );
291	#endif
292
293	// compute expected sense value
294	unsigned int expected;
295	if ( node->sense == 0) expected = 1;
296	else expected = 0;
297
298	// atomic decrement
299	// - input : count address (pcount)
300	// - output : modified counter value (count)
301	unsigned int* pcount = (unsigned int*)&node->count;
302	unsigned int count = 0; // avoid a warning
303
304	asm volatile( "addu $2, %1, $0 \n"
305	"sqt_llsc: \n"
306	"ll $8, 0($2) \n"
307	"addi $9, $8, -1 \n"
308	"sc $9, 0($2) \n"
309	"beqz $9, sqt_llsc \n"
310	"addu %0, $8, $0 \n"
311	: "=r" (count)
312	: "r" (pcount)
313	: "$2", "$8", "$9", "memory" );
314
315	if ( count == 1 ) // last task
316	{
317	// decrement the parent node if the current node is not the root
318	if ( node->parent != NULL )
319	sqt_barrier_decrement( node->parent );
320
321	// reset the current node
322	node->sense = expected;
323	node->count = node->arity;
324
325	#if GIET_DEBUG_USER_BARRIER
326	giet_shr_printf("\n[DEBUG USER BARRIER] P[%d,%d,%d] reset SQT barrier node %x :\n"
327	" level = %d / arity = %d / sense = %d / count = %d\n",
328	px , py , pl , (unsigned int)node ,
329	node->level , node->arity , node->sense , node->count );
330	#endif
331	return;
332	}
333	else // not the last task
334	{
335	// poll sense flag
336	// input: pointer on the sens flag (psense)
337	// input: expected sense value (expected)
338	unsigned int* psense = (unsigned int *)&node->sense;
339	asm volatile ( "sqt_sense: \n"
340	"lw $3, 0(%0) \n"
341	"bne $3, %1, sqt_sense \n"
342	:
343	: "r"(psense), "r"(expected)
344	: "$3" );
345	return;
346	}
347	} // end sqt_decrement()
348
349	////////////////////////////////////////////////////
350	void sqt_barrier_wait( giet_sqt_barrier_t* barrier )
351	{
352	// compute cluster coordinates for the calling task
353	unsigned int x;
354	unsigned int y;
355	unsigned int lpid;
356	giet_proc_xyp( &x, &y, &lpid );
357
358	// recursively decrement count from bottom to root
359	sqt_barrier_decrement( barrier->node[x][y][0] );
360
361	asm volatile ("sync" ::: "memory");
362
363	} // end sqt_barrier_wait()
364
365
366	// Local Variables:
367	// tab-width: 4
368	// c-basic-offset: 4
369	// c-file-offsets:((innamespace . 0)(inline-open . 0))
370	// indent-tabs-mode: nil
371	// End:
372	// vim: filetype=c:expandtab:shiftwidth=4:tabsroot=4:softtabsroot=4
373
374	// Local Variables:
375	// tab-width: 4
376	// c-basic-offset: 4
377	// c-file-offsets:((innamespace . 0)(inline-open . 0))
378	// indent-tabs-mode: nil
379	// End:
380	// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
381

Note: See TracBrowser for help on using the repository browser.

Download in other formats: