1 /* 2 * This file is part of MPSolve 3.2.1 3 * 4 * Copyright (C) 2001-2020, Dipartimento di Matematica "L. Tonelli", Pisa. 5 * License: http://www.gnu.org/licenses/gpl.html GPL version 3 or higher 6 * 7 * Authors: 8 * Leonardo Robol <leonardo.robol@unipi.it> 9 */ 10 11 /** 12 * @file 13 * @brief Multithreading iterations for MPSolve. 14 */ 15 16 #include <pthread.h> 17 #include <semaphore.h> 18 #include <mps/mps.h> 19 20 MPS_BEGIN_DECLS 21 22 #ifndef MPS_THREADING_H_ 23 #define MPS_THREADING_H_ 24 25 #define MPS_THREAD_JOB_EXCEP -1 26 #define MPS_MAX_CORES 8192 27 28 #define mps_with_lock(pmutex, code) { \ 29 pthread_mutex_lock (&pmutex); \ 30 code \ 31 pthread_mutex_unlock (&pmutex); \ 32 } 33 34 /** 35 * @brief A generic routine that can be performed by a <code>mps_thread</code>. 36 */ 37 typedef void * (*mps_thread_work)(void *); 38 39 /** 40 * @brief A new job for <code>mps_thread_fsolve()</code>, 41 * <code>mps_thread_dsolve()</code> or <code>mps_thread_msolve()</code>. 42 * 43 */ 44 struct mps_thread_job { 45 /** 46 * @brief The index if the root to iterate on. 47 */ 48 int i; 49 50 /** 51 * @brief The iteration that will be performed on this root. 52 */ 53 int iter; 54 55 /** 56 * @brief cluster_item The cluster element of <code>s->clusterization 57 * that we are iterating on. 58 */ 59 mps_cluster_item * cluster_item; 60 }; 61 62 63 /** 64 * @brief Struct holding a job queue. 65 * 66 * This structure can be used to coordinate the work in the different 67 * thread during multithread computation in MPSolve. 68 * 69 * It must be allocated using <code>mps_thread_job_queue_new()</code> 70 * and freed with <code>mps_thread_job_queue_free()</code>. 71 * A new job can be requested with the routine 72 * <code>mps_thread_job_queue_next()</code>. 73 * 74 * @see mps_thread_job_queue_next() 75 */ 76 struct mps_thread_job_queue { 77 /** 78 * @brief Maximum number of iteration to perform before 79 * raising an exeption. 80 */ 81 unsigned int max_iter; 82 83 /** 84 * @brief Number of the roots of this problem (i.e. degree of 85 * the polynomial). 86 */ 87 unsigned int n_roots; 88 89 /** 90 * @brief Iterations that is being performed right now. 91 */ 92 int iter; 93 94 /** 95 * @brief Next root to iterate on. 96 */ 97 mps_root * root; 98 99 /** 100 * @brief Element of <code>s->clusterization</code> that 101 * we are iterating on. 102 */ 103 mps_cluster_item * cluster_item; 104 105 /** 106 * @brief Internal mutex of the queue used to guarantee 107 * exclusive access. 108 */ 109 pthread_mutex_t mutex; 110 }; 111 112 /** 113 * @brief Data packed to be passed to a new thread that will 114 * perform floating point, dpe or multiprecision iterations. 115 */ 116 struct mps_thread_worker_data { 117 /** 118 * @brief Pointer to the integer that holds the number of zeros 119 * computed until now. 120 */ 121 volatile int *nzeros; 122 123 /** 124 * @brief The number of well approximated roots required to stop iteration 125 * packet. 126 */ 127 int required_zeros; 128 129 /** 130 * @brief Pointer to the integer that holds the number of iterations 131 * performed until now. 132 */ 133 volatile int *it; 134 135 /** 136 * @brief The pointer to the <code>mps_context</code> struct. 137 */ 138 mps_context *s; 139 140 /** 141 * @brief The index of this thread. 142 */ 143 int thread; 144 145 /** 146 * @brief The total number of threads. 147 */ 148 int n_threads; 149 150 /** 151 * @brief Pointer to the boolean excep value. Setting this to true 152 * cause the iteration to enter exception state. 153 * 154 * If this state is reached all threads returns because no more 155 * iteration are needed / useful. 156 */ 157 volatile mps_boolean *excep; 158 159 /** 160 * @brief Array of <code>n</code> mutexes where <code>n = s->n</code>, i.e. 161 * is the total number of roots of the polynomial. 162 * 163 * The mutex in position <code>i</code> gets locked when a 164 * thread needs to read and/or write from/to 165 * the i-th root. 166 */ 167 pthread_mutex_t *aberth_mutex; 168 169 /** 170 * @brief Global aberth mutex used to coordinate all aberth 171 * computations. 172 */ 173 pthread_mutex_t *global_aberth_mutex; 174 175 /** 176 * @brief Array of <code>n</code> mutexes that gets locked when a thread 177 * start to iterate over a root. This is done to ensure that only a thread 178 * at a time is iterating over a root. 179 */ 180 pthread_mutex_t *roots_mutex; 181 182 /** 183 * @brief Global state mute used to synchronize some (hopefully not so many) 184 * global operation. 185 */ 186 pthread_mutex_t *gs_mutex; 187 188 /** 189 * @brief Pointer to the <code>mps_thread_job_queue</code> that the thread 190 * may query for other work. 191 */ 192 mps_thread_job_queue *queue; 193 }; 194 195 /** 196 * @brief A thread that is part of a thread pool. 197 */ 198 struct mps_thread { 199 /** 200 * @brief Pool of which this thread is part. 201 */ 202 mps_thread_pool * pool; 203 204 /** 205 * @brief The pthread_t assigned to the worked. 206 */ 207 pthread_t * thread; 208 209 /** 210 * @brief The next thread in the pool, or NULL if this 211 * is the last thread contained in it. 212 */ 213 mps_thread * next; 214 215 /** 216 * @brief The data assigned to this thread, that sets 217 * the worker that he has to do. 218 */ 219 mps_thread_worker_data * data; 220 221 /** 222 * @brief True if the thread is busy. 223 */ 224 mps_boolean busy; 225 226 /** 227 * @brief Busy mutex of the thread. This is locked when the thread 228 * is doing something, se we can emulate a join on it by 229 * try to lock and unlock this mutex. 230 */ 231 pthread_mutex_t busy_mutex; 232 233 /** 234 * @brief Condition that allow the thread to run. Before the thread 235 * finish the busy state (unlocking the busy mutex) or when it is 236 * created, it waits for the start condition to be true before 237 * doing anything. 238 */ 239 pthread_cond_t start_condition; 240 241 /** 242 * @brief A boolean value that is true if the thread must continue to 243 * poll, or false if it is required to exit. Since the thread 244 * may be waiting for work a call to pthread_cond_signal on 245 * start condition may be required to make it exit after setting 246 * this variable. 247 */ 248 mps_boolean alive; 249 250 /** 251 * @brief The routine that must be called when the thread starts. 252 */ 253 mps_thread_work work; 254 255 /** 256 * @brief The argument to be passed to the thread. 257 */ 258 void * args; 259 }; 260 261 /** 262 * @brief An item that can be inserted and/or extracted from 263 * a mps_thread_pool_queue. 264 */ 265 struct mps_thread_pool_queue_item { 266 /** 267 * @brief The actual job that should be performed. 268 */ 269 mps_thread_work work; 270 271 /** 272 * @brief The args that shall be passed to the work function. 273 */ 274 void * args; 275 276 /** 277 * @brief The next item in the queue. 278 */ 279 mps_thread_pool_queue_item * next; 280 }; 281 282 /** 283 * @brief A queue of work items that thread can consume. 284 */ 285 struct mps_thread_pool_queue { 286 /** 287 * @brief Pointer to the first item of the queue, or NULL if 288 * the queue is empty. 289 */ 290 mps_thread_pool_queue_item * first; 291 292 /** 293 * @brief Pointer to the last item of the queue, or NULL if 294 * the queue is empty. 295 */ 296 mps_thread_pool_queue_item * last; 297 }; 298 299 /** 300 * @brief A thread pool that contains a set of <code>mps_thread</code> 301 * and allow to manage them as a set of worker. 302 */ 303 struct mps_thread_pool { 304 /** 305 * @brief The numer of thread in the thread pool. 306 */ 307 unsigned int n; 308 309 /** 310 * @brief Limit to the maximum spawnable number 311 * of threads. This can be set to 0 that means 312 * "No limit". It is useful when less concurrency 313 * is desired without deleting and recreating threads. 314 * 315 * This variables MUST be updated using the accessor function 316 * mps_thread_pool_set_ 317 */ 318 unsigned int concurrency_limit; 319 320 /** 321 * @brief A pointer to the first thread in the thread pool. 322 */ 323 mps_thread * first; 324 325 /** 326 * @brief Queue of the work that shall be consumed by the threads. 327 */ 328 mps_thread_pool_queue * queue; 329 330 /** 331 * @brief Mutex associated to the queue_changed condition. 332 */ 333 pthread_mutex_t queue_changed_mutex; 334 335 /** 336 * @brief Condition that is notified when the queue changes. 337 */ 338 pthread_cond_t queue_changed; 339 340 pthread_mutex_t work_completed_mutex; 341 pthread_cond_t work_completed_cond; 342 int busy_counter; 343 344 /** 345 * @brief When this vaulue is set to true every call to mps_assign_job 346 * returns immediately. 347 * 348 * When it is set to false the calls to mps_thread_pool_assign() when the number 349 * of thread is set to 1 will immediately perform the work, instead 350 * of delegating it to a background thread. This is done to ensure reasonable 351 * performance for the cases where only 1 CPU is available on the PC. 352 */ 353 mps_boolean strict_async; 354 }; 355 356 /* EXPORTED ROUTINES */ 357 358 void * mps_thread_mainloop (void * thread_ptr); 359 360 void mps_thread_start_mainloop (mps_context * s, mps_thread * thread); 361 362 mps_thread * mps_thread_new (mps_context * s, mps_thread_pool * pool); 363 364 void mps_thread_free (mps_context * s, mps_thread * thread); 365 366 void mps_thread_pool_set_concurrency_limit (mps_context * s, mps_thread_pool * pool, 367 unsigned int concurrency_limit); 368 369 void mps_thread_pool_assign (mps_context * s, mps_thread_pool * pool, mps_thread_work work, void * args); 370 371 void mps_thread_pool_insert_new_thread (mps_context * s, mps_thread_pool * pool); 372 373 void mps_thread_pool_wait (mps_context * s, mps_thread_pool * pool); 374 375 mps_thread_pool * mps_thread_pool_get_system_pool (mps_context * s); 376 377 void mps_thread_pool_set_strict_async (mps_thread_pool * pool, mps_boolean strict_async); 378 379 mps_thread_pool * mps_thread_pool_new (mps_context * s, int n_threads); 380 381 void mps_thread_pool_free (mps_context * s, mps_thread_pool * pool); 382 383 mps_thread_job_queue * mps_thread_job_queue_new (mps_context * s); 384 385 void mps_thread_job_queue_free (mps_thread_job_queue * q); 386 387 mps_thread_job mps_thread_job_queue_next (mps_context * s, mps_thread_job_queue * q); 388 389 void mps_thread_fpolzer (mps_context * s, int *nit, mps_boolean * excep, int required_zeros); 390 391 void mps_thread_mpolzer (mps_context * s, int *nit, mps_boolean * excep, int required_zeros); 392 393 void mps_thread_dpolzer (mps_context * s, int *nit, mps_boolean * excep, int required_zeros); 394 395 int mps_thread_get_core_number (mps_context * s); 396 397 int mps_thread_get_id (mps_context * s, mps_thread_pool * pool); 398 399 /* MACROS */ 400 401 /** 402 * @brief Get a pointer to an array of n+2 booleans 403 * that is local to the thread. 404 */ 405 #define mps_thread_get_spar2(s, n_thread) (s->spar2 + (s->deg + 2) * (n_thread)) 406 407 /** 408 * @brief Get a pointer to an array of n+1 multiprecision 409 * that is local to the thread. 410 */ 411 #define mps_thread_get_mfpc2(s, n_thread) (s->mfpc2 + (s->deg + 1) * (n_thread)) 412 413 /** 414 * @brief Get a pointer to an array of n+2 DPE 415 * that is local to the thread. 416 */ 417 #define mps_thread_get_dap2(s, n_thread) (s->dap2 + (s->deg + 2) * (n_thread)) 418 419 MPS_END_DECLS 420 421 #endif /* MPS_THREADING_H_ */ 422