Intel® OpenMP* Runtime Library
 All Classes Functions Variables Typedefs Enumerations Enumerator Groups Pages
kmp_sched.cpp
1 /*
2  * kmp_sched.c -- static scheduling -- iteration initialization
3  * $Revision: 42358 $
4  * $Date: 2013-05-07 13:43:26 -0500 (Tue, 07 May 2013) $
5  */
6 
7 /* <copyright>
8  Copyright (c) 1997-2013 Intel Corporation. All Rights Reserved.
9 
10  Redistribution and use in source and binary forms, with or without
11  modification, are permitted provided that the following conditions
12  are met:
13 
14  * Redistributions of source code must retain the above copyright
15  notice, this list of conditions and the following disclaimer.
16  * Redistributions in binary form must reproduce the above copyright
17  notice, this list of conditions and the following disclaimer in the
18  documentation and/or other materials provided with the distribution.
19  * Neither the name of Intel Corporation nor the names of its
20  contributors may be used to endorse or promote products derived
21  from this software without specific prior written permission.
22 
23  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27  HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 
35 </copyright> */
36 
37 /*
38  * Static scheduling initialization.
39  *
40  * NOTE: team->t.t_nproc is a constant inside of any dispatch loop, however
41  * it may change values between parallel regions. __kmp_max_nth
42  * is the largest value __kmp_nth may take, 1 is the smallest.
43  *
44  */
45 
46 #include "kmp.h"
47 #include "kmp_i18n.h"
48 #include "kmp_str.h"
49 #include "kmp_error.h"
50 
51 // template for type limits
52 template< typename T >
53 struct i_maxmin {
54  static const T mx;
55  static const T mn;
56 };
57 template<>
58 struct i_maxmin< int > {
59  static const int mx = 0x7fffffff;
60  static const int mn = 0x80000000;
61 };
62 template<>
63 struct i_maxmin< unsigned int > {
64  static const unsigned int mx = 0xffffffff;
65  static const unsigned int mn = 0x00000000;
66 };
67 template<>
68 struct i_maxmin< long long > {
69  static const long long mx = 0x7fffffffffffffffLL;
70  static const long long mn = 0x8000000000000000LL;
71 };
72 template<>
73 struct i_maxmin< unsigned long long > {
74  static const unsigned long long mx = 0xffffffffffffffffLL;
75  static const unsigned long long mn = 0x0000000000000000LL;
76 };
77 //-------------------------------------------------------------------------
78 #ifdef KMP_DEBUG
79 //-------------------------------------------------------------------------
80 // template for debug prints specification ( d, u, lld, llu )
81  char const * traits_t< int >::spec = "d";
82  char const * traits_t< unsigned int >::spec = "u";
83  char const * traits_t< long long >::spec = "lld";
84  char const * traits_t< unsigned long long >::spec = "llu";
85 //-------------------------------------------------------------------------
86 #endif
87 
88 template< typename T >
89 static void
90 __kmp_for_static_init(
91  ident_t *loc,
92  kmp_int32 global_tid,
93  kmp_int32 schedtype,
94  kmp_int32 *plastiter,
95  T *plower,
96  T *pupper,
97  typename traits_t< T >::signed_t *pstride,
98  typename traits_t< T >::signed_t incr,
99  typename traits_t< T >::signed_t chunk
100 ) {
101  typedef typename traits_t< T >::unsigned_t UT;
102  typedef typename traits_t< T >::signed_t ST;
103  /* this all has to be changed back to TID and such.. */
104  register kmp_int32 gtid = global_tid;
105  register kmp_uint32 tid;
106  register kmp_uint32 nth;
107  register UT trip_count;
108  register kmp_team_t *team;
109 
110  KE_TRACE( 10, ("__kmpc_for_static_init called (%d)\n", global_tid));
111  #ifdef KMP_DEBUG
112  {
113  const char * buff;
114  // create format specifiers before the debug output
115  buff = __kmp_str_format(
116  "__kmpc_for_static_init: T#%%d sched=%%d liter=%%d iter=(%%%s," \
117  " %%%s, %%%s) incr=%%%s chunk=%%%s signed?<%s>\n",
118  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec,
119  traits_t< ST >::spec, traits_t< ST >::spec, traits_t< T >::spec );
120  KD_TRACE(100, ( buff, global_tid, schedtype, *plastiter,
121  *plower, *pupper, *pstride, incr, chunk ) );
122  __kmp_str_free( &buff );
123  }
124  #endif
125 
126  if ( __kmp_env_consistency_check ) {
127  __kmp_push_workshare( global_tid, ct_pdo, loc );
128  if ( incr == 0 ) {
129  __kmp_error_construct( kmp_i18n_msg_CnsLoopIncrZeroProhibited, ct_pdo, loc );
130 
131  }
132  }
133  /* special handling for zero-trip loops */
134  if ( incr > 0 ? (*pupper < *plower) : (*plower < *pupper) ) {
135  *plastiter = FALSE;
136  /* leave pupper and plower set to entire iteration space */
137  *pstride = incr; /* value should never be used */
138  // *plower = *pupper - incr; // let compiler bypass the illegal loop (like for(i=1;i<10;i--)) THIS LINE CAUSED shape2F/h_tests_1.f TO HAVE A FAILURE ON A ZERO-TRIP LOOP (lower=1,\
139  upper=0,stride=1) - JPH June 23, 2009.
140  #ifdef KMP_DEBUG
141  {
142  const char * buff;
143  // create format specifiers before the debug output
144  buff = __kmp_str_format(
145  "__kmpc_for_static_init:(ZERO TRIP) liter=%%d lower=%%%s upper=%%%s stride = %%%s signed?<%s>, loc = %%s\n",
146  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec, traits_t< T >::spec );
147  KD_TRACE(100, ( buff, *plastiter, *plower, *pupper, *pstride, loc->psource ) );
148  __kmp_str_free( &buff );
149  }
150  #endif
151  KE_TRACE( 10, ("__kmpc_for_static_init: T#%d return\n", global_tid ) );
152  return;
153  }
154 
155  #if OMP_40_ENABLED
156  if ( schedtype > kmp_ord_upper ) {
157  // we are in DISTRIBUTE construct
158  schedtype += kmp_sch_static - kmp_distribute_static; // AC: convert to usual schedule type
159  tid = __kmp_threads[ gtid ]->th.th_team->t.t_master_tid;
160  team = __kmp_threads[ gtid ]->th.th_team->t.t_parent;
161  } else
162  #endif
163  {
164  tid = __kmp_tid_from_gtid( global_tid );
165  team = __kmp_threads[ gtid ]->th.th_team;
166  }
167 
168  /* determine if "for" loop is an active worksharing construct */
169  if ( team -> t.t_serialized ) {
170  /* serialized parallel, each thread executes whole iteration space */
171  *plastiter = TRUE;
172  /* leave pupper and plower set to entire iteration space */
173  *pstride = (incr > 0) ? (*pupper - *plower + 1) : (-(*plower - *pupper + 1));
174 
175  #ifdef KMP_DEBUG
176  {
177  const char * buff;
178  // create format specifiers before the debug output
179  buff = __kmp_str_format(
180  "__kmpc_for_static_init: (serial) liter=%%d lower=%%%s upper=%%%s stride = %%%s\n",
181  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec );
182  KD_TRACE(100, ( buff, *plastiter, *plower, *pupper, *pstride ) );
183  __kmp_str_free( &buff );
184  }
185  #endif
186  KE_TRACE( 10, ("__kmpc_for_static_init: T#%d return\n", global_tid ) );
187  return;
188  }
189  nth = team->t.t_nproc;
190  if ( nth == 1 ) {
191  *plastiter = TRUE;
192 
193  #ifdef KMP_DEBUG
194  {
195  const char * buff;
196  // create format specifiers before the debug output
197  buff = __kmp_str_format(
198  "__kmpc_for_static_init: (serial) liter=%%d lower=%%%s upper=%%%s stride = %%%s\n",
199  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec );
200  KD_TRACE(100, ( buff, *plastiter, *plower, *pupper, *pstride ) );
201  __kmp_str_free( &buff );
202  }
203  #endif
204  KE_TRACE( 10, ("__kmpc_for_static_init: T#%d return\n", global_tid ) );
205  return;
206  }
207 
208  /* compute trip count */
209  if ( incr == 1 ) {
210  trip_count = *pupper - *plower + 1;
211  } else if (incr == -1) {
212  trip_count = *plower - *pupper + 1;
213  } else {
214  if ( incr > 1 ) {
215  trip_count = (*pupper - *plower) / incr + 1;
216  } else {
217  trip_count = (*plower - *pupper) / ( -incr ) + 1;
218  }
219  }
220  if ( __kmp_env_consistency_check ) {
221  /* tripcount overflow? */
222  if ( trip_count == 0 && *pupper != *plower ) {
223  __kmp_error_construct( kmp_i18n_msg_CnsIterationRangeTooLarge, ct_pdo, loc );
224  }
225  }
226 
227  /* compute remaining parameters */
228  switch ( schedtype ) {
229  case kmp_sch_static:
230  {
231  if ( trip_count < nth ) {
232  KMP_DEBUG_ASSERT(
233  __kmp_static == kmp_sch_static_greedy || \
234  __kmp_static == kmp_sch_static_balanced
235  ); // Unknown static scheduling type.
236  if ( tid < trip_count ) {
237  *pupper = *plower = *plower + tid * incr;
238  } else {
239  *plower = *pupper + incr;
240  }
241  *plastiter = ( tid == trip_count - 1 );
242  } else {
243  if ( __kmp_static == kmp_sch_static_balanced ) {
244  register UT small_chunk = trip_count / nth;
245  register UT extras = trip_count % nth;
246  *plower += incr * ( tid * small_chunk + ( tid < extras ? tid : extras ) );
247  *pupper = *plower + small_chunk * incr - ( tid < extras ? 0 : incr );
248  *plastiter = ( tid == nth - 1 );
249  } else {
250  register T big_chunk_inc_count = ( trip_count/nth +
251  ( ( trip_count % nth ) ? 1 : 0) ) * incr;
252  register T old_upper = *pupper;
253 
254  KMP_DEBUG_ASSERT( __kmp_static == kmp_sch_static_greedy );
255  // Unknown static scheduling type.
256 
257  *plower += tid * big_chunk_inc_count;
258  *pupper = *plower + big_chunk_inc_count - incr;
259  if ( incr > 0 ) {
260  if ( *pupper < *plower ) {
261  *pupper = i_maxmin< T >::mx;
262  }
263  *plastiter = *plower <= old_upper && *pupper > old_upper - incr;
264  if ( *pupper > old_upper ) *pupper = old_upper; // tracker C73258
265  } else {
266  if ( *pupper > *plower ) {
267  *pupper = i_maxmin< T >::mn;
268  }
269  *plastiter = *plower >= old_upper && *pupper < old_upper - incr;
270  if ( *pupper < old_upper ) *pupper = old_upper; // tracker C73258
271  }
272  }
273  }
274  break;
275  }
276  case kmp_sch_static_chunked:
277  {
278  register T span;
279  if ( chunk < 1 ) {
280  chunk = 1;
281  }
282  span = chunk * incr;
283  *pstride = span * nth;
284  *plower = *plower + (span * tid);
285  *pupper = *plower + span - incr;
286  /* TODO: is the following line a bug? Shouldn't it be plastiter instead of *plastiter ? */
287  if (*plastiter) { /* only calculate this if it was requested */
288  kmp_int32 lasttid = ((trip_count - 1) / ( UT )chunk) % nth;
289  *plastiter = (tid == lasttid);
290  }
291  break;
292  }
293  default:
294  KMP_ASSERT2( 0, "__kmpc_for_static_init: unknown scheduling type" );
295  break;
296  }
297 
298  #ifdef KMP_DEBUG
299  {
300  const char * buff;
301  // create format specifiers before the debug output
302  buff = __kmp_str_format(
303  "__kmpc_for_static_init: liter=%%d lower=%%%s upper=%%%s stride = %%%s signed?<%s>\n",
304  traits_t< T >::spec, traits_t< T >::spec, traits_t< ST >::spec, traits_t< T >::spec );
305  KD_TRACE(100, ( buff, *plastiter, *plower, *pupper, *pstride ) );
306  __kmp_str_free( &buff );
307  }
308  #endif
309  KE_TRACE( 10, ("__kmpc_for_static_init: T#%d return\n", global_tid ) );
310  return;
311 }
312 
313 //--------------------------------------------------------------------------------------
314 extern "C" {
315 
336 void
337 __kmpc_for_static_init_4( ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter,
338  kmp_int32 *plower, kmp_int32 *pupper,
339  kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk )
340 {
341  __kmp_for_static_init< kmp_int32 >(
342  loc, gtid, schedtype, plastiter, plower, pupper, pstride, incr, chunk );
343 }
344 
348 void
349 __kmpc_for_static_init_4u( ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter,
350  kmp_uint32 *plower, kmp_uint32 *pupper,
351  kmp_int32 *pstride, kmp_int32 incr, kmp_int32 chunk )
352 {
353  __kmp_for_static_init< kmp_uint32 >(
354  loc, gtid, schedtype, plastiter, plower, pupper, pstride, incr, chunk );
355 }
356 
360 void
361 __kmpc_for_static_init_8( ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter,
362  kmp_int64 *plower, kmp_int64 *pupper,
363  kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk )
364 {
365  __kmp_for_static_init< kmp_int64 >(
366  loc, gtid, schedtype, plastiter, plower, pupper, pstride, incr, chunk );
367 }
368 
372 void
373 __kmpc_for_static_init_8u( ident_t *loc, kmp_int32 gtid, kmp_int32 schedtype, kmp_int32 *plastiter,
374  kmp_uint64 *plower, kmp_uint64 *pupper,
375  kmp_int64 *pstride, kmp_int64 incr, kmp_int64 chunk )
376 {
377  __kmp_for_static_init< kmp_uint64 >(
378  loc, gtid, schedtype, plastiter, plower, pupper, pstride, incr, chunk );
379 }
384 } // extern "C"
385