Debian Codegraph @

3rdparty/mshmet/src/sourceslib/lplib3.c

raw
1
2
3 /*----------------------------------------------------------*/
4 /* */
5 /* LPLIB V3.02 */
6 /* */
7 /*----------------------------------------------------------*/
8 /* */
9 /* Description: Handles threads, scheduling */
10 /* & dependencies */
11 /* Author: Loic MARECHAL */
12 /* Creation date: feb 25 2008 */
13 /* Last modification: feb 15 2011 */
14 /* */
15 /*----------------------------------------------------------*/
16
17
18 #ifndef SERIAL
19
20 /*----------------------------------------------------------*/
21 /* Includes */
22 /*----------------------------------------------------------*/
23
24 #include <pthread.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <math.h>
29 #include <stdbool.h>
30 #include <assert.h>
31 #include <errno.h>
32 #include "lplib3.h"
33 #ifdef __FreeBSD__
34 #include <sys/types.h>
35 #include <pmc.h>
36 #endif
37
38 /*----------------------------------------------------------*/
39 /* Defines */
40 /*----------------------------------------------------------*/
41
42 #define MaxLibPar 10
43 #define MaxPth 128
44 #define MaxTyp 100
45 #define DefNmbSmlBlk 64
46 #define DefNmbDepBlk 256
47 #define MaxTotPip 65536
48 #define MaxPipDep 100
49 #define MaxHsh 10
50
51 enum ParCmd {RunBigWrk, RunSmlWrk, ClrMem, EndPth};
52
53
54 /*----------------------------------------------------------*/
55 /* Structures' prototypes */
56 /*----------------------------------------------------------*/
57
58 typedef struct WrkSct
59 {
60 int BegIdx, EndIdx, NmbDep, *DepWrdTab;
61 int *DepIdxTab;
62 struct WrkSct *pre, *nex;
63 }WrkSct;
64
65 typedef struct
66 {
67 int NmbLin, NmbSmlWrk, NmbBigWrk, SmlWrkSiz, BigWrkSiz, DepWrkSiz, NmbDepWrd, *DepWrdMat, *DepIdxMat;
68 char *RunDepTab;
69 WrkSct *SmlWrkTab, *BigWrkTab;
70 }TypSct;
71
72 typedef struct
73 {
74 int idx;
75 char *ClrAdr;
76 WrkSct *wrk;
77 pthread_mutex_t mtx;
78 pthread_cond_t cnd;
79 pthread_t pth;
80 struct ParSct *par;
81 }PthSct;
82
83 typedef struct PipSct
84 {
85 int idx, NmbDep, DepTab[ MaxPipDep ];
86 void *prc, *arg;
87 pthread_t pth;
88 struct ParSct *par;
89 }PipSct;
90
91 typedef struct BucSct
92 {
93 int idx[3];
94 long long int dat;
95 struct BucSct *nex;
96 }BucSct;
97
98 typedef struct
99 {
100 int mul[3], NmbOvf[ MaxPth ];
101 TypSct *typ1, *typ2;
102 BucSct *buc, *ovf[ MaxPth ];
103 }HshSct;
104
105 typedef struct ParSct
106 {
107 int NmbCpu, WrkCpt, NmbPip, PenPip, RunPip, NmbTyp, BufMax, BufCpt, req, cmd, ClrLinSiz, *PipWrd;
108 double sta[2];
109 void (*prc)(int, int, int, void *), *arg;
110 pthread_cond_t ParCnd, PipCnd;
111 pthread_mutex_t ParMtx, PipMtx;
112 pthread_t PipPth;
113 PthSct *PthTab;
114 TypSct *TypTab, *CurTyp, *DepTyp, *typ1, *typ2;
115 WrkSct *NexWrk, *BufWrk[ MaxPth / 4 ];
116 HshSct HshTab[ MaxHsh ];
117 }ParSct;
118
119 typedef struct
120 {
121 unsigned long long (*idx)[2];
122 double box[6], (*crd)[3], (*crd2)[2];
123 }ArgSct;
124
125
126 /*----------------------------------------------------------*/
127 /* Private procedures' prototypes */
128 /*----------------------------------------------------------*/
129
130 static int SetBit(int *, int);
131 static int GetBit(int *, int);
132 static int AndWrd(WrkSct *, char *);
133 static void SetWrd(WrkSct *, char *);
134 static void ClrWrd(WrkSct *, char *);
135 int CmpWrk(const void *, const void *);
136 static void *PipHdl(void *);
137 static void *PthHdl(void *);
138 static WrkSct *NexWrk(ParSct *, int);
139
140
141 /*----------------------------------------------------------*/
142 /* Global variables */
143 /*----------------------------------------------------------*/
144
145 ParSct *ParTab[ MaxLibPar+1 ];
146 int IniLibPar = 0;
147
148
149 /*----------------------------------------------------------*/
150 /* Init structures, scheduler and launch threads */
151 /*----------------------------------------------------------*/
152
153 int InitParallel(int NmbCpu)
154 {
155 int i, ParIdx;
156 ParSct *par = NULL;
157 PthSct *pth;
158
159 /* Check the number of requested cpu and clear the main par table at first call */
160
161 if(NmbCpu > MaxPth)
162 return(0);
163
164 if(!IniLibPar)
165 {
166 IniLibPar = 1;
167
168 for(i=1;i<=MaxLibPar;i++)
169 ParTab[i] = NULL;
170 }
171
172 /* Allocate and build main parallel structure */
173
174 for(ParIdx=1; ParIdx<=MaxLibPar; ParIdx++)
175 if(!ParTab[ ParIdx ])
176 {
177 par = ParTab[ ParIdx ] = calloc(1, sizeof(ParSct));
178 break;
179 }
180
181 if(!par)
182 return(0);
183
184 if(!(par->PthTab = calloc(NmbCpu, sizeof(PthSct))))
185 return(0);
186
187 if(!(par->TypTab = calloc((MaxTyp + 1), sizeof(TypSct))))
188 return(0);
189
190 if(!(par->PipWrd = calloc(MaxTotPip/32, sizeof(int))))
191 return(0);
192
193 par->NmbCpu = NmbCpu;
194 par->WrkCpt = par->NmbPip = par->PenPip = par->RunPip = 0;
195
196 /* Set the size of WP buffer */
197
198 if(NmbCpu >= 4)
199 par->BufMax = NmbCpu / 4;
200 else
201 par->BufMax = 1;
202
203 pthread_mutex_init(&par->ParMtx, NULL);
204 pthread_mutex_init(&par->PipMtx, NULL);
205 pthread_cond_init(&par->ParCnd, NULL);
206 pthread_cond_init(&par->PipCnd, NULL);
207
208 /* Launch pthreads */
209
210 for(i=0;i<par->NmbCpu;i++)
211 {
212 pth = &par->PthTab[i];
213 pth->idx = i;
214 pth->par = par;
215 pthread_mutex_init(&pth->mtx, NULL);
216 pthread_cond_init(&pth->cnd, NULL);
217 pthread_create(&pth->pth, NULL, PthHdl, (void *)pth);
218 }
219
220 /* Wait for all threads to be up and wainting */
221
222 pthread_mutex_lock(&par->ParMtx);
223
224 while(par->WrkCpt < par->NmbCpu)
225 pthread_cond_wait(&par->ParCnd, &par->ParMtx);
226
227 pthread_mutex_unlock(&par->ParMtx);
228
229 return(ParIdx);
230 }
231
232
233 /*----------------------------------------------------------*/
234 /* Stop all threads and free memories */
235 /*----------------------------------------------------------*/
236
237 void StopParallel(int ParIdx)
238 {
239 int i;
240 PthSct *pth;
241 ParSct *par;
242
243 /* Get and check lib parallel instance */
244
245 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
246 return;
247
248 /* Send stop to all threads */
249
250 pthread_mutex_lock(&par->ParMtx);
251 par->cmd = EndPth;
252 pthread_mutex_unlock(&par->ParMtx);
253
254 /* Wait for all threads to complete */
255
256 for(i=0;i<par->NmbCpu;i++)
257 {
258 pth = &par->PthTab[i];
259 pthread_mutex_lock(&pth->mtx);
260 pthread_cond_signal(&pth->cnd);
261 pthread_mutex_unlock(&pth->mtx);
262 pthread_join(pth->pth, NULL);
263 }
264
265 pthread_mutex_destroy(&par->ParMtx);
266 pthread_cond_destroy(&par->ParCnd);
267
268 WaitPipeline(ParIdx);
269
270 pthread_mutex_destroy(&par->PipMtx);
271 pthread_cond_destroy(&par->PipCnd);
272
273 /* Free memories */
274
275 for(i=1;i<=MaxTyp;i++)
276 if(par->TypTab[i].NmbLin)
277 FreeType(ParIdx, i);
278
279 free(par->PthTab);
280 free(par->TypTab);
281 free(par->PipWrd);
282 free(par);
283
284 ParTab[ ParIdx ] = NULL;
285 }
286
287
288 /*----------------------------------------------------------*/
289 /* Launch the loop prc on typ1 element depending on typ2 */
290 /*----------------------------------------------------------*/
291
292 float LaunchParallel(int ParIdx, int TypIdx1, int TypIdx2, void *prc, void *PtrArg)
293 {
294 int i;
295 PthSct *pth;
296 ParSct *par;
297 TypSct *typ1, *typ2 = NULL;
298
299 /* Get and check lib parallel instance */
300
301 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
302 return(-1.);
303
304 /* Check bounds */
305
306 if( (TypIdx1 < 1) || (TypIdx1 > MaxTyp) || (TypIdx2 < 0) || (TypIdx2 > MaxTyp) || (TypIdx1 == TypIdx2) )
307 return(-1.);
308
309 typ1 = &par->TypTab[ TypIdx1 ];
310
311 if(TypIdx2)
312 {
313 /* Lock acces to global parameters */
314
315 pthread_mutex_lock(&par->ParMtx);
316
317 par->cmd = RunSmlWrk;
318 par->prc = (void (*)(int, int, int, void *))prc;
319 par->arg = PtrArg;
320 par->typ1 = typ1;
321 par->typ2 = typ2 = &par->TypTab[ TypIdx2 ];
322 par->NexWrk = typ1->SmlWrkTab;
323 par->BufCpt = 0;
324 par->WrkCpt = 0;
325 par->sta[0] = par->sta[1] = 0.;
326 par->req = 0;
327
328 /* Clear running wp */
329
330 for(i=0;i<par->NmbCpu;i++)
331 par->PthTab[i].wrk = NULL;
332
333 memset(typ1->RunDepTab, 0, typ1->NmbDepWrd * 32 * sizeof(char));
334
335 /* Build a linked list of wp */
336
337 for(i=0;i<par->typ1->NmbSmlWrk;i++)
338 {
339 typ1->SmlWrkTab[i].pre = &typ1->SmlWrkTab[ i-1 ];
340 typ1->SmlWrkTab[i].nex = &typ1->SmlWrkTab[ i+1 ];
341 }
342
343 typ1->SmlWrkTab[0].pre = typ1->SmlWrkTab[ typ1->NmbSmlWrk - 1 ].nex = NULL;
344
345 /* Start main loop : wake up threads and wait for completion or blocked threads */
346
347 do
348 {
349 /* Search for some idle threads */
350
351 par->req = 0;
352
353 for(i=0;i<par->NmbCpu;i++)
354 {
355 pth = &par->PthTab[i];
356
357 if(pth->wrk)
358 continue;
359
360 if(!(pth->wrk = NexWrk(par, i)))
361 {
362 par->req = 1;
363 break;
364 }
365
366 /* Wake up the thread and provide it with a WP list */
367
368 pthread_mutex_lock(&pth->mtx);
369 pthread_cond_signal(&pth->cnd);
370 pthread_mutex_unlock(&pth->mtx);
371 }
372
373 /* If every WP are done : exit the parallel loop */
374
375 if(par->WrkCpt == typ1->NmbSmlWrk)
376 break;
377
378 /* Otherwise, wait for a blocked thread */
379
380 pthread_cond_wait(&par->ParCnd, &par->ParMtx);
381 }while(1);
382
383 pthread_mutex_unlock(&par->ParMtx);
384
385 /* Return the average speedup */
386
387 return(par->sta[1] / par->sta[0]);
388 }
389 else
390 {
391 /* Lock acces to global parameters */
392
393 pthread_mutex_lock(&par->ParMtx);
394
395 par->cmd = RunBigWrk;
396 par->prc = (void (*)(int, int, int, void *))prc;
397 par->arg = PtrArg;
398 par->typ1 = typ1;
399 par->typ2 = NULL;
400 par->WrkCpt = 0;
401
402 for(i=0;i<typ1->NmbBigWrk;i++)
403 {
404 pth = &par->PthTab[i];
405 pth->wrk = &typ1->BigWrkTab[i];
406 }
407
408 for(i=0;i<typ1->NmbBigWrk;i++)
409 {
410 pth = &par->PthTab[i];
411 pthread_mutex_lock(&pth->mtx);
412 pthread_cond_signal(&pth->cnd);
413 pthread_mutex_unlock(&pth->mtx);
414 }
415
416 pthread_cond_wait(&par->ParCnd, &par->ParMtx);
417
418 pthread_mutex_unlock(&par->ParMtx);
419
420 /* Return the average speedup */
421
422 return(par->NmbCpu);
423 }
424 }
425
426
427 /*----------------------------------------------------------*/
428 /* Pthread handler, waits for job, does it, then signal end */
429 /*----------------------------------------------------------*/
430
431 static void *PthHdl(void *ptr)
432 {
433 PthSct *pth = (PthSct *)ptr;
434 ParSct *par = pth->par;
435
436 /* Tell the scheduler if all threads are ready */
437
438 pthread_mutex_lock(&par->ParMtx);
439 par->WrkCpt++;
440 pthread_cond_signal(&par->ParCnd);
441 pthread_mutex_lock(&pth->mtx);
442 pthread_mutex_unlock(&par->ParMtx);
443
444 /* Enter main loop until StopParallel is send */
445
446 do
447 {
448 /* Wait for a wake-up signal from the main loop */
449
450 pthread_cond_wait(&pth->cnd, &pth->mtx);
451
452 switch(par->cmd)
453 {
454 case RunBigWrk :
455 {
456 /* Launch a single big wp and signal completion to the scheduler */
457
458 par->prc(pth->wrk->BegIdx, pth->wrk->EndIdx, pth->idx, par->arg);
459
460 pthread_mutex_lock(&par->ParMtx);
461 par->WrkCpt++;
462
463 if(par->WrkCpt >= par->typ1->NmbBigWrk)
464 pthread_cond_signal(&par->ParCnd);
465
466 pthread_mutex_unlock(&par->ParMtx);
467 }break;
468
469 case RunSmlWrk :
470 {
471 do
472 {
473 /* Run the WP */
474
475 par->prc(pth->wrk->BegIdx, pth->wrk->EndIdx, pth->idx, par->arg);
476
477 /* Locked acces to global parameters : update WP count, tag WP done and signal the main loop */
478
479 pthread_mutex_lock(&par->ParMtx);
480
481 par->WrkCpt++;
482
483 if(!(pth->wrk = NexWrk(par, pth->idx)))
484 {
485 par->req = 1;
486 pthread_cond_signal(&par->ParCnd);
487 pthread_mutex_unlock(&par->ParMtx);
488 break;
489 }
490
491 if(par->req)
492 pthread_cond_signal(&par->ParCnd);
493
494 pthread_mutex_unlock(&par->ParMtx);
495 }while(1);
496 }break;
497
498 case ClrMem :
499 {
500 /* Clear memory and signal completion to the scheduler */
501
502 memset(pth->ClrAdr, 0, par->ClrLinSiz);
503
504 pthread_mutex_lock(&par->ParMtx);
505 par->WrkCpt++;
506 pthread_cond_signal(&par->ParCnd);
507 pthread_mutex_unlock(&par->ParMtx);
508 }break;
509
510 case EndPth :
511 {
512 /* Destroy the thread mutex and condition and call for join */
513
514 pthread_mutex_unlock(&pth->mtx);
515 pthread_mutex_destroy(&pth->mtx);
516 pthread_cond_destroy(&pth->cnd);
517 return(NULL);
518 }break;
519 }
520 }while(1);
521
522 return(NULL);
523 }
524
525
526 /*----------------------------------------------------------*/
527 /* Get the next WP to be computed */
528 /*----------------------------------------------------------*/
529
530 static WrkSct *NexWrk(ParSct *par, int PthIdx)
531 {
532 int i;
533 PthSct *pth = &par->PthTab[ PthIdx ];
534 WrkSct *wrk;
535
536 /* Update stats */
537
538 par->sta[0]++;
539
540 for(i=0;i<par->NmbCpu;i++)
541 if(par->PthTab[i].wrk)
542 par->sta[1]++;
543
544 /* Remove previous work's tags */
545
546 if(pth->wrk)
547 ClrWrd(pth->wrk, par->typ1->RunDepTab);
548
549 /* If the wp's buffer is empty search for some new compatible wp to fill in */
550
551 if(!par->BufCpt)
552 {
553 wrk = par->NexWrk;
554
555 while(wrk)
556 {
557 /* Check for dependencies */
558
559 if(!AndWrd(wrk, par->typ1->RunDepTab))
560 {
561 par->BufWrk[ par->BufCpt++ ] = wrk;
562
563 /* Unlink wp */
564
565 if(wrk->pre)
566 wrk->pre->nex = wrk->nex;
567 else
568 par->NexWrk = wrk->nex;
569
570 if(wrk->nex)
571 wrk->nex->pre = wrk->pre;
572
573 /* Add new work's tags */
574
575 SetWrd(wrk, par->typ1->RunDepTab);
576
577 if(par->BufCpt == par->BufMax)
578 break;
579 }
580
581 wrk = wrk->nex;
582 }
583 }
584
585 /* Return the next available wp in buffer and unlink it from the todo list */
586
587 if(par->BufCpt)
588 return(par->BufWrk[ --par->BufCpt ]);
589 else
590 return(NULL);
591 }
592
593
594 /*----------------------------------------------------------*/
595 /* Allocate a new kind of elements and set work-packages */
596 /*----------------------------------------------------------*/
597
598 int NewType(int ParIdx, int NmbLin)
599 {
600 int i, TypIdx=0, idx;
601 TypSct *typ;
602 ParSct *par;
603
604 /* Get and check lib parallel instance */
605
606 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
607 return(0);
608
609 if(NmbLin < par->NmbCpu)
610 return(0);
611
612 /* Search for a free type structure */
613
614 for(i=1;i<=MaxTyp;i++)
615 if(!par->TypTab[i].NmbLin)
616 {
617 TypIdx = i;
618 break;
619 }
620
621 if(!TypIdx)
622 return(0);
623
624 typ = &par->TypTab[ TypIdx ];
625 typ->NmbLin = NmbLin;
626
627 /* Compute the size of small work-packages */
628
629 if(NmbLin >= DefNmbSmlBlk * par->NmbCpu)
630 typ->SmlWrkSiz = NmbLin / (DefNmbSmlBlk * par->NmbCpu);
631 else
632 typ->SmlWrkSiz = NmbLin / par->NmbCpu;
633
634 typ->NmbSmlWrk = NmbLin / typ->SmlWrkSiz;
635
636 if(NmbLin != typ->NmbSmlWrk * typ->SmlWrkSiz)
637 typ->NmbSmlWrk++;
638
639 if(!(typ->SmlWrkTab = calloc(typ->NmbSmlWrk , sizeof(WrkSct))))
640 return(0);
641
642 /* Set small work-packages */
643
644 idx = 0;
645
646 for(i=0;i<typ->NmbSmlWrk;i++)
647 {
648 typ->SmlWrkTab[i].BegIdx = idx + 1;
649 typ->SmlWrkTab[i].EndIdx = idx + typ->SmlWrkSiz;
650 idx += typ->SmlWrkSiz;
651 }
652
653 typ->SmlWrkTab[ typ->NmbSmlWrk - 1 ].EndIdx = NmbLin;
654
655 /* Compute the size of big work-packages */
656
657 typ->BigWrkSiz = NmbLin / par->NmbCpu;
658 typ->NmbBigWrk = par->NmbCpu;
659
660 if(!(typ->BigWrkTab = calloc(typ->NmbBigWrk , sizeof(WrkSct))))
661 return(0);
662
663 /* Set big work-packages */
664
665 idx = 0;
666
667 for(i=0;i<typ->NmbBigWrk;i++)
668 {
669 typ->BigWrkTab[i].BegIdx = idx + 1;
670 typ->BigWrkTab[i].EndIdx = idx + typ->BigWrkSiz;
671 idx += typ->BigWrkSiz;
672 }
673
674 typ->BigWrkTab[ typ->NmbBigWrk - 1 ].EndIdx = NmbLin;
675
676 return(TypIdx);
677 }
678
679
680 /*----------------------------------------------------------*/
681 /* Add this kind of element to the free-list */
682 /*----------------------------------------------------------*/
683
684 void FreeType(int ParIdx, int TypIdx)
685 {
686 TypSct *typ;
687 ParSct *par;
688
689 /* Get and check lib parallel instance */
690
691 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
692 return;
693
694 /* Check bounds and free mem */
695
696 if( (TypIdx < 1) || (TypIdx > MaxTyp) )
697 return;
698
699 typ = &par->TypTab[ TypIdx ];
700
701 if(typ->SmlWrkTab)
702 free(typ->SmlWrkTab);
703
704 if(typ->BigWrkTab)
705 free(typ->BigWrkTab);
706
707 if(typ->DepIdxMat)
708 free(typ->DepIdxMat);
709
710 if(typ->RunDepTab)
711 free(typ->RunDepTab);
712
713 if(typ->DepWrdMat)
714 free(typ->DepWrdMat);
715
716 memset(typ, 0, sizeof(TypSct));
717 }
718
719
720 /*----------------------------------------------------------*/
721 /* Allocate a dependency matrix linking both types */
722 /*----------------------------------------------------------*/
723
724 int BeginDependency(int ParIdx, int TypIdx1, int TypIdx2)
725 {
726 int i;
727 ParSct *par;
728 TypSct *typ1, *typ2;
729
730 /* Get and check lib parallel instance */
731
732 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
733 return(0);
734
735 /* Check bounds */
736
737 par->CurTyp = typ1 = &par->TypTab[ TypIdx1 ];
738 par->DepTyp = typ2 = &par->TypTab[ TypIdx2 ];
739
740 if( (TypIdx1 < 1) || (TypIdx1 > MaxTyp) || (TypIdx2 < 1) || (TypIdx2 > MaxTyp) || (typ1 == typ2) \
741 || !typ1->NmbLin || !typ2->NmbLin)
742 {
743 return(0);
744 }
745
746 /* Compute dependency table's size */
747
748 if(typ2->NmbLin >= DefNmbDepBlk * par->NmbCpu)
749 typ1->DepWrkSiz = typ2->NmbLin / (DefNmbDepBlk * par->NmbCpu);
750 else
751 typ1->DepWrkSiz = typ2->NmbLin / par->NmbCpu;
752
753 typ1->NmbDepWrd = typ2->NmbLin / (typ1->DepWrkSiz * 32);
754
755 if(typ2->NmbLin != typ1->NmbDepWrd * typ1->DepWrkSiz * 32)
756 typ1->NmbDepWrd++;
757
758 /* Allocate a global dependency table */
759
760 if(!(typ1->DepWrdMat = calloc(typ1->NmbSmlWrk * typ1->NmbDepWrd, sizeof(int))))
761 return(0);
762
763 /* Then spread sub-tables among WP */
764
765 for(i=0;i<typ1->NmbSmlWrk;i++)
766 {
767 typ1->SmlWrkTab[i].NmbDep = 0;
768 typ1->SmlWrkTab[i].DepWrdTab = &typ1->DepWrdMat[ i * typ1->NmbDepWrd ];
769 }
770
771 /* Allocate a running tags table */
772
773 if(!(typ1->RunDepTab = calloc(typ1->NmbDepWrd * 32, sizeof(char))))
774 return(0);
775
776 return(1);
777 }
778
779
780 /*----------------------------------------------------------*/
781 /* Type1 element idx1 depends on type2 element idx2 */
782 /*----------------------------------------------------------*/
783
784 void AddDependency(int ParIdx, int idx1, int idx2)
785 {
786 WrkSct *wrk;
787 ParSct *par;
788
789 /* Get and check lib parallel instance */
790
791 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
792 return;
793
794 /* Set and count dependency bit */
795
796 wrk = &par->CurTyp->SmlWrkTab[ (idx1-1) / par->CurTyp->SmlWrkSiz ];
797
798 if(!SetBit(wrk->DepWrdTab, (idx2-1) / par->CurTyp->DepWrkSiz ))
799 wrk->NmbDep++;
800 }
801
802
803 /*----------------------------------------------------------*/
804 /* Sort wp depending on their number of dependencies */
805 /*----------------------------------------------------------*/
806
807 void EndDependency(int ParIdx, float DepSta[2])
808 {
809 int i, j, idx=0, NmbDep, NmbDepBit, TotNmbDep = 0;
810 ParSct *par;
811 TypSct *typ1, *typ2;
812 WrkSct *wrk;
813
814 /* Get and check lib parallel instance */
815
816 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
817 return;
818
819 /* Compute average number of collisions */
820
821 DepSta[1] = 0.;
822 typ1 = par->CurTyp;
823 typ2 = par->DepTyp;
824
825 for(i=0;i<typ1->NmbSmlWrk;i++)
826 {
827 TotNmbDep += typ1->SmlWrkTab[i].NmbDep;
828
829 if(typ1->SmlWrkTab[i].NmbDep > DepSta[1])
830 DepSta[1] = typ1->SmlWrkTab[i].NmbDep;
831 }
832
833 DepSta[0] = TotNmbDep;
834
835 /* Allocate a global dependency index table */
836
837 if(!(typ1->DepIdxMat = calloc(TotNmbDep, sizeof(int))))
838 return;
839
840 /* Then spread and fill the sub-tables among WP */
841
842 NmbDep = typ1->NmbDepWrd * 32;
843
844 for(i=0;i<typ1->NmbSmlWrk;i++)
845 {
846 wrk = &typ1->SmlWrkTab[i];
847 wrk->DepIdxTab = &typ1->DepIdxMat[ idx ];
848 idx += wrk->NmbDep;
849 wrk->NmbDep = 0;
850
851 for(j=0;j<NmbDep;j++)
852 if(GetBit(wrk->DepWrdTab, j))
853 wrk->DepIdxTab[ wrk->NmbDep++ ] = j;
854 }
855
856 /* Compute stats */
857
858 NmbDepBit = typ2->NmbLin / typ1->DepWrkSiz;
859
860 if(typ2->NmbLin - NmbDepBit * typ1->DepWrkSiz)
861 NmbDepBit++;
862
863 DepSta[0] = 100 * DepSta[0] / (typ1->NmbSmlWrk * NmbDepBit);
864 DepSta[1] = 100 * DepSta[1] / NmbDepBit;
865
866 /* Sort WP from highest collision number to the lowest */
867
868 qsort(typ1->SmlWrkTab, typ1->NmbSmlWrk, sizeof(WrkSct), CmpWrk);
869
870 par->CurTyp = NULL;
871 }
872
873
874 /*----------------------------------------------------------*/
875 /* Test and set a bit in a multibyte number */
876 /*----------------------------------------------------------*/
877
878 static int SetBit(int *tab, int idx)
879 {
880 int res = ( tab[ idx >> 5 ] & (1 << (idx & 31)) );
881 tab[ idx >> 5 ] |= 1 << (idx & 31);
882 return(res);
883 }
884
885
886 /*----------------------------------------------------------*/
887 /* Test a bit in a multibyte number */
888 /*----------------------------------------------------------*/
889
890 static int GetBit(int *tab, int idx)
891 {
892 return( tab[ idx >> 5 ] & (1 << (idx & 31)) );
893 }
894
895
896 /*----------------------------------------------------------*/
897 /* Check wether two WP share common resources -> locked */
898 /*----------------------------------------------------------*/
899
900 static int AndWrd(WrkSct *wrk, char *wrd)
901 {
902 int i;
903
904 for(i=0;i<wrk->NmbDep;i++)
905 if(wrd[ wrk->DepIdxTab[i] ])
906 return(1);
907
908 return(0);
909 }
910
911 static void SetWrd(WrkSct *wrk, char *wrd)
912 {
913 int i;
914
915 for(i=0;i<wrk->NmbDep;i++)
916 wrd[ wrk->DepIdxTab[i] ] = 1;
917 }
918
919 static void ClrWrd(WrkSct *wrk, char *wrd)
920 {
921 int i;
922
923 for(i=0;i<wrk->NmbDep;i++)
924 wrd[ wrk->DepIdxTab[i] ] = 0;
925 }
926
927
928 /*----------------------------------------------------------*/
929 /* Compare two workpackages number of bits */
930 /*----------------------------------------------------------*/
931
932 int CmpWrk(const void *ptr1, const void *ptr2)
933 {
934 WrkSct *w1, *w2;
935
936 w1 = (WrkSct *)ptr1;
937 w2 = (WrkSct *)ptr2;
938
939 if(w1->NmbDep > w2->NmbDep)
940 return(-1);
941 else if(w1->NmbDep < w2->NmbDep)
942 return(1);
943 else
944 return(0);
945 }
946
947
948 /*----------------------------------------------------------*/
949 /* Launch the loop prc on typ1 element depending on typ2 */
950 /*----------------------------------------------------------*/
951
952 int ParallelMemClear(int ParIdx, void *PtrArg, long siz)
953 {
954 char *tab = (char *)PtrArg;
955 int i;
956 PthSct *pth;
957 ParSct *par;
958
959 /* Get and check lib parallel instance, adresse and size */
960
961 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) || !tab || (siz < par->NmbCpu) )
962 return(0);
963
964 /* Lock acces to global parameters */
965
966 pthread_mutex_lock(&par->ParMtx);
967
968 par->cmd = ClrMem;
969 par->ClrLinSiz = siz / par->NmbCpu;
970 par->WrkCpt = 0;
971
972 /* Spread the buffer among each thread and wake then up */
973
974 for(i=0;i<par->NmbCpu;i++)
975 {
976 pth = &par->PthTab[i];
977 pth->ClrAdr = &tab[ i * par->ClrLinSiz ];
978
979 pthread_mutex_lock(&pth->mtx);
980 pthread_cond_signal(&pth->cnd);
981 pthread_mutex_unlock(&pth->mtx);
982 }
983
984 /* Wait for each thread to complete */
985
986 while(par->WrkCpt < par->NmbCpu)
987 pthread_cond_wait(&par->ParCnd, &par->ParMtx);
988
989 pthread_mutex_unlock(&par->ParMtx);
990
991 return(1);
992 }
993
994
995 /*----------------------------------------------------------*/
996 /* Wait for a condition, launch and detach a user procedure */
997 /*----------------------------------------------------------*/
998
999 int LaunchPipeline(int ParIdx, void *prc, void *PtrArg, int NmbDep, int *DepTab)
1000 {
1001 int i;
1002 PipSct *NewPip=NULL;
1003 ParSct *par;
1004
1005 /* Get and check lib parallel instance and the number of pipes and dependencies */
1006
1007 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) \
1008 || (NmbDep > MaxPipDep) || (par->NmbPip >= MaxTotPip) )
1009 {
1010 return(0);
1011 }
1012
1013 /* Allocate and setup a new pipe */
1014
1015 if(!(NewPip = malloc(sizeof(PipSct))))
1016 return(0);
1017
1018 NewPip->prc = prc;
1019 NewPip->arg = PtrArg;
1020 NewPip->par = par;
1021 NewPip->NmbDep = NmbDep;
1022
1023 for(i=0;i<NmbDep;i++)
1024 NewPip->DepTab[i] = DepTab[i];
1025
1026 /* Lock pipe mutex, increment pipe counter and launch the pipe regardless dependencies */
1027
1028 pthread_mutex_lock(&par->PipMtx);
1029 NewPip->idx = ++par->NmbPip;
1030 par->PenPip++;
1031 pthread_create(&NewPip->pth, NULL, PipHdl, (void *)NewPip);
1032 pthread_mutex_unlock(&par->PipMtx);
1033
1034 return(NewPip->idx);
1035 }
1036
1037
1038 /*----------------------------------------------------------*/
1039 /* Thread handler launching and waitint for user's procedure*/
1040 /*----------------------------------------------------------*/
1041
1042 static void *PipHdl(void *ptr)
1043 {
1044 int RunFlg, i;
1045 PipSct *pip = (PipSct *)ptr;
1046 ParSct *par = pip->par;
1047 void (*prc)(void *);
1048
1049 /* Wait for conditions to be met */
1050
1051 do
1052 {
1053 pthread_mutex_lock(&par->PipMtx);
1054
1055 if(par->RunPip < par->NmbCpu)
1056 {
1057 RunFlg = 1;
1058
1059 for(i=0;i<pip->NmbDep;i++)
1060 if(!GetBit(par->PipWrd, pip->DepTab[i]))
1061 {
1062 RunFlg = 0;
1063 break;
1064 }
1065 }
1066
1067 if(!RunFlg)
1068 {
1069 pthread_mutex_unlock(&par->PipMtx);
1070 usleep(1000);
1071 }
1072 }while(!RunFlg);
1073
1074 /* Execute the user's procedure and set the flag to 2 (done) */
1075
1076 prc = (void (*)(void *))pip->prc;
1077 par->RunPip++;
1078
1079 pthread_mutex_unlock(&par->PipMtx);
1080
1081 prc(pip->arg);
1082
1083 pthread_mutex_lock(&par->PipMtx);
1084 SetBit(par->PipWrd, pip->idx);
1085 par->PenPip--;
1086 par->RunPip--;
1087 free(pip);
1088 pthread_mutex_unlock(&par->PipMtx);
1089
1090 return(NULL);
1091 }
1092
1093
1094 /*----------------------------------------------------------*/
1095 /* Wait for all pipelined procedures to complete */
1096 /*----------------------------------------------------------*/
1097
1098 void WaitPipeline(int ParIdx)
1099 {
1100 int PenPip;
1101 ParSct *par;
1102
1103 /* Get and check lib parallel instance */
1104
1105 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
1106 return;
1107
1108 do
1109 {
1110 pthread_mutex_lock(&par->PipMtx);
1111 PenPip = par->PenPip;
1112 pthread_mutex_unlock(&par->PipMtx);
1113 usleep(1000);
1114 }while(PenPip);
1115 }
1116
1117
1118 /*-
1119 * Copyright (c) 1992, 1993
1120 * The Regents of the University of California. All rights reserved.
1121 * Multithread implementation Copyright (c) 2006, 2007 Diomidis Spinellis.
1122 *
1123 * Redistribution and use in source and binary forms, with or without
1124 * modification, are permitted provided that the following conditions
1125 * are met:
1126 * 1. Redistributions of source code must retain the above copyright
1127 * notice, this list of conditions and the following disclaimer.
1128 * 2. Redistributions in binary form must reproduce the above copyright
1129 * notice, this list of conditions and the following disclaimer in the
1130 * documentation and/or other materials provided with the distribution.
1131 * 4. Neither the name of the University nor the names of its contributors
1132 * may be used to endorse or promote products derived from this software
1133 * without specific prior written permission.
1134 *
1135 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
1136 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1137 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1138 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
1139 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1140 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1141 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1142 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1143 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1144 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1145 * SUCH DAMAGE.
1146 */
1147
1148 #define verify(x) (x)
1149 #define DLOG(...)
1150 #define min(a, b) (a) < (b) ? a : b
1151
1152 typedef int cmp_t(const void *, const void *);
1153 static inline char *med3(char *, char *, char *, cmp_t *, void *);
1154 static inline void swapfunc(char *, char *, int, int);
1155
1156 /*
1157 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
1158 */
1159 #define swapcode(TYPE, parmi, parmj, n) { \
1160 long i = (n) / sizeof (TYPE); \
1161 TYPE *pi = (TYPE *) (parmi); \
1162 TYPE *pj = (TYPE *) (parmj); \
1163 do { \
1164 TYPE t = *pi; \
1165 *pi++ = *pj; \
1166 *pj++ = t; \
1167 } while (--i > 0); \
1168 }
1169
1170
1171 static inline void swapfunc(char *a, char *b, int n, int swaptype)
1172 {
1173 if(swaptype <= 1)
1174 swapcode(long, a, b, n)
1175 else
1176 swapcode(char, a, b, n)
1177 }
1178
1179 #define swap(a, b) \
1180 if (swaptype == 0) { \
1181 long t = *(long *)(a); \
1182 *(long *)(a) = *(long *)(b); \
1183 *(long *)(b) = t; \
1184 } else \
1185 swapfunc(a, b, es, swaptype)
1186
1187 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
1188
1189 #define CMP(t, x, y) (cmp((x), (y)))
1190
1191 static inline char *med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk)
1192 {
1193 return CMP(thunk, a, b) < 0 ?
1194 (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
1195 :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
1196 }
1197
1198 /*
1199 * We use some elaborate condition variables and signalling
1200 * to ensure a bound of the number of active threads at
1201 * 2 * maxthreads and the size of the thread data structure
1202 * to maxthreads.
1203 */
1204
1205 /* Condition of starting a new thread. */
1206 enum thread_state {
1207 ts_idle, /* Idle, waiting for instructions. */
1208 ts_work, /* Has work to do. */
1209 ts_term /* Asked to terminate. */
1210 };
1211
1212 /* Variant part passed to qsort invocations. */
1213 struct qsort {
1214 enum thread_state st; /* For coordinating work. */
1215 struct common *common; /* Common shared elements. */
1216 void *a; /* Array base. */
1217 size_t n; /* Number of elements. */
1218 pthread_t id; /* Thread id. */
1219 pthread_mutex_t mtx_st; /* For signalling state change. */
1220 pthread_cond_t cond_st; /* For signalling state change. */
1221 };
1222
1223 /* Invariant common part, shared across invocations. */
1224 struct common {
1225 int swaptype; /* Code to use for swapping */
1226 size_t es; /* Element size. */
1227 void *thunk; /* Thunk for qsort_r */
1228 cmp_t *cmp; /* Comparison function */
1229 int nthreads; /* Total number of pool threads. */
1230 int idlethreads; /* Number of idle threads in pool. */
1231 int forkelem; /* Minimum number of elements for a new thread. */
1232 struct qsort *pool; /* Fixed pool of threads. */
1233 pthread_mutex_t mtx_al; /* For allocating threads in the pool. */
1234 };
1235
1236 static void *qsort_thread(void *p);
1237
1238 /* The multithreaded qsort public interface */
1239 void qsort_mt(void *a, size_t n, size_t es, cmp_t *cmp, int maxthreads, int forkelem)
1240 {
1241 struct qsort *qs;
1242 struct common c;
1243 int i, islot;
1244 bool bailout = true;
1245
1246 if (n < forkelem)
1247 goto f1;
1248 errno = 0;
1249 #ifdef __FreeBSD__
1250 if (maxthreads == 0) {
1251 /*
1252 * Other candidates:
1253 * NPROC environment variable (BSD/OS, CrayOS)
1254 * sysctl hw.ncpu or kern.smp.cpus
1255 */
1256 int ncpu;
1257 if (pmc_init() == 0 && (ncpu = pmc_ncpu()) != -1)
1258 maxthreads = ncpu;
1259 else
1260 maxthreads = 2;
1261 }
1262 #endif
1263 /* XXX temporarily disabled for stress and performance testing.
1264 if (maxthreads == 1)
1265 goto f1;
1266 */
1267 /* Try to initialize the resources we need. */
1268 if (pthread_mutex_init(&c.mtx_al, NULL) != 0)
1269 goto f1;
1270 if ((c.pool = (struct qsort *)calloc(maxthreads, sizeof(struct qsort))) ==NULL)
1271 goto f2;
1272 for (islot = 0; islot < maxthreads; islot++) {
1273 qs = &c.pool[islot];
1274 if (pthread_mutex_init(&qs->mtx_st, NULL) != 0)
1275 goto f3;
1276 if (pthread_cond_init(&qs->cond_st, NULL) != 0) {
1277 verify(pthread_mutex_destroy(&qs->mtx_st));
1278 goto f3;
1279 }
1280 qs->st = ts_idle;
1281 qs->common = &c;
1282 if (pthread_create(&qs->id, NULL, qsort_thread, qs) != 0) {
1283 verify(pthread_mutex_destroy(&qs->mtx_st));
1284 verify(pthread_cond_destroy(&qs->cond_st));
1285 goto f3;
1286 }
1287 }
1288
1289 /* All systems go. */
1290 bailout = false;
1291
1292 /* Initialize common elements. */
1293 c.swaptype = ((char *)a - (char *)0) % sizeof(long) || \
1294 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
1295 c.es = es;
1296 c.cmp = cmp;
1297 c.forkelem = forkelem;
1298 c.idlethreads = c.nthreads = maxthreads;
1299
1300 /* Hand out the first work batch. */
1301 qs = &c.pool[0];
1302 verify(pthread_mutex_lock(&qs->mtx_st));
1303 qs->a = a;
1304 qs->n = n;
1305 qs->st = ts_work;
1306 c.idlethreads--;
1307 verify(pthread_cond_signal(&qs->cond_st));
1308 verify(pthread_mutex_unlock(&qs->mtx_st));
1309
1310 /*
1311 * Wait for all threads to finish, and
1312 * free acquired resources.
1313 */
1314 f3: for (i = 0; i < islot; i++) {
1315 qs = &c.pool[i];
1316 if (bailout) {
1317 verify(pthread_mutex_lock(&qs->mtx_st));
1318 qs->st = ts_term;
1319 verify(pthread_cond_signal(&qs->cond_st));
1320 verify(pthread_mutex_unlock(&qs->mtx_st));
1321 }
1322 verify(pthread_join(qs->id, NULL));
1323 verify(pthread_mutex_destroy(&qs->mtx_st));
1324 verify(pthread_cond_destroy(&qs->cond_st));
1325 }
1326 free(c.pool);
1327 f2: verify(pthread_mutex_destroy(&c.mtx_al));
1328 if (bailout) {
1329 DLOG("Resource initialization failed; bailing out.\n");
1330 /* XXX should include a syslog call here */
1331 fprintf(stderr, "Resource initialization failed; bailing out.\n");
1332 f1: qsort(a, n, es, cmp);
1333 }
1334 }
1335
1336 #define thunk NULL
1337
1338 /*
1339 * Allocate an idle thread from the pool, lock its
1340 * mutex, change its state to work, decrease the number
1341 * of idle threads, and return a
1342 * pointer to its data area.
1343 * Return NULL, if no thread is available.
1344 */
1345 static struct qsort *allocate_thread(struct common *c)
1346 {
1347 int i;
1348
1349 verify(pthread_mutex_lock(&c->mtx_al));
1350 for (i = 0; i < c->nthreads; i++)
1351 if (c->pool[i].st == ts_idle) {
1352 c->idlethreads--;
1353 c->pool[i].st = ts_work;
1354 verify(pthread_mutex_lock(&c->pool[i].mtx_st));
1355 verify(pthread_mutex_unlock(&c->mtx_al));
1356 return (&c->pool[i]);
1357 }
1358 verify(pthread_mutex_unlock(&c->mtx_al));
1359 return (NULL);
1360 }
1361
1362 /* Thread-callable quicksort. */
1363 static void qsort_algo(struct qsort *qs)
1364 {
1365 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
1366 int d, r, swaptype, swap_cnt;
1367 void *a; /* Array of elements. */
1368 size_t n, es; /* Number of elements; size. */
1369 cmp_t *cmp;
1370 int nl, nr;
1371 struct common *c;
1372 struct qsort *qs2;
1373 pthread_t id;
1374
1375 /* Initialize qsort arguments. */
1376 id = qs->id;
1377 c = qs->common;
1378 es = c->es;
1379 cmp = c->cmp;
1380 swaptype = c->swaptype;
1381 a = qs->a;
1382 n = qs->n;
1383 top:
1384 DLOG("%10x n=%-10d Sort starting.\n", id, n);
1385
1386 /* From here on qsort(3) business as usual. */
1387 swap_cnt = 0;
1388 if (n < 7) {
1389 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
1390 for (pl = pm;
1391 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
1392 pl -= es)
1393 swap(pl, pl - es);
1394 return;
1395 }
1396 pm = (char *)a + (n / 2) * es;
1397 if (n > 7) {
1398 pl = a;
1399 pn = (char *)a + (n - 1) * es;
1400 if (n > 40) {
1401 d = (n / 8) * es;
1402 pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
1403 pm = med3(pm - d, pm, pm + d, cmp, thunk);
1404 pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
1405 }
1406 pm = med3(pl, pm, pn, cmp, thunk);
1407 }
1408 swap(a, pm);
1409 pa = pb = (char *)a + es;
1410
1411 pc = pd = (char *)a + (n - 1) * es;
1412 for (;;) {
1413 while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
1414 if (r == 0) {
1415 swap_cnt = 1;
1416 swap(pa, pb);
1417 pa += es;
1418 }
1419 pb += es;
1420 }
1421 while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
1422 if (r == 0) {
1423 swap_cnt = 1;
1424 swap(pc, pd);
1425 pd -= es;
1426 }
1427 pc -= es;
1428 }
1429 if (pb > pc)
1430 break;
1431 swap(pb, pc);
1432 swap_cnt = 1;
1433 pb += es;
1434 pc -= es;
1435 }
1436 if (swap_cnt == 0) { /* Switch to insertion sort */
1437 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
1438 for (pl = pm;
1439 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
1440 pl -= es)
1441 swap(pl, pl - es);
1442 return;
1443 }
1444
1445 pn = (char *)a + n * es;
1446 r = min(pa - (char *)a, pb - pa);
1447 vecswap(a, pb - r, r);
1448 r = min(pd - pc, pn - pd - es);
1449 vecswap(pb, pn - r, r);
1450
1451 nl = (pb - pa) / es;
1452 nr = (pd - pc) / es;
1453 DLOG("%10x n=%-10d Partitioning finished ln=%d rn=%d.\n", id, n, nl, nr);
1454
1455 /* Now try to launch subthreads. */
1456 if (nl > c->forkelem && nr > c->forkelem &&
1457 (qs2 = allocate_thread(c)) != NULL) {
1458 DLOG("%10x n=%-10d Left farmed out to %x.\n", id, n, qs2->id);
1459 qs2->a = a;
1460 qs2->n = nl;
1461 verify(pthread_cond_signal(&qs2->cond_st));
1462 verify(pthread_mutex_unlock(&qs2->mtx_st));
1463 } else if (nl > 0) {
1464 DLOG("%10x n=%-10d Left will be done in-house.\n", id, n);
1465 qs->a = a;
1466 qs->n = nl;
1467 qsort_algo(qs);
1468 }
1469 if (nr > 0) {
1470 DLOG("%10x n=%-10d Right will be done in-house.\n", id, n);
1471 a = pn - nr * es;
1472 n = nr;
1473 goto top;
1474 }
1475 }
1476
1477 /* Thread-callable quicksort. */
1478 static void *qsort_thread(void *p)
1479 {
1480 struct qsort *qs, *qs2;
1481 int i;
1482 struct common *c;
1483 pthread_t id;
1484
1485 qs = p;
1486 id = qs->id;
1487 c = qs->common;
1488 again:
1489 /* Wait for work to be allocated. */
1490 DLOG("%10x n=%-10d Thread waiting for work.\n", id, 0);
1491 verify(pthread_mutex_lock(&qs->mtx_st));
1492 while (qs->st == ts_idle)
1493 verify(pthread_cond_wait(&qs->cond_st, &qs->mtx_st));
1494 verify(pthread_mutex_unlock(&qs->mtx_st));
1495 if (qs->st == ts_term) {
1496 DLOG("%10x n=%-10d Thread signalled to exit.\n", id, 0);
1497 return(NULL);
1498 }
1499 assert(qs->st == ts_work);
1500
1501 qsort_algo(qs);
1502
1503 verify(pthread_mutex_lock(&c->mtx_al));
1504 qs->st = ts_idle;
1505 c->idlethreads++;
1506 DLOG("%10x n=%-10d Finished idlethreads=%d.\n", id, 0, c->idlethreads);
1507 if (c->idlethreads == c->nthreads) {
1508 DLOG("%10x n=%-10d All threads idle, signalling shutdown.\n", id, 0);
1509 for (i = 0; i < c->nthreads; i++) {
1510 qs2 = &c->pool[i];
1511 if (qs2 == qs)
1512 continue;
1513 verify(pthread_mutex_lock(&qs2->mtx_st));
1514 qs2->st = ts_term;
1515 verify(pthread_cond_signal(&qs2->cond_st));
1516 verify(pthread_mutex_unlock(&qs2->mtx_st));
1517 }
1518 DLOG("%10x n=%-10d Shutdown signalling complete.\n", id, 0);
1519 verify(pthread_mutex_unlock(&c->mtx_al));
1520 return(NULL);
1521 }
1522 verify(pthread_mutex_unlock(&c->mtx_al));
1523 goto again;
1524 }
1525
1526
1527 /*----------------------------------------------------------*/
1528 /* Lplib qsort_mt encapsulation */
1529 /*----------------------------------------------------------*/
1530
1531 void ParallelQsort(int ParIdx, void *base, size_t nel, size_t width, int (*compar)(const void *, const void *))
1532 {
1533 ParSct *par;
1534
1535 /* Get and check lib parallel instance */
1536
1537 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
1538 return;
1539
1540 qsort_mt(base, nel, width, compar, par->NmbCpu, 10000);
1541 }
1542
1543
1544 /*----------------------------------------------------------*/
1545 /* Compute the hilbert code from 3d coordinates */
1546 /*----------------------------------------------------------*/
1547
1548 static void RenPrc(int BegIdx, int EndIdx, int PthIdx, ArgSct *arg)
1549 {
1550 unsigned long long IntCrd[3], m=1LL<<63, cod;
1551 int i, j, b, GeoWrd, NewWrd, BitTab[3] = {1,2,4};
1552 double dbl;
1553 int rot[8], GeoCod[8]={0,3,7,4,1,2,6,5}; /* Z curve = {5,4,7,6,1,0,3,2} */
1554 int HilCod[8][8] = {{0,7,6,1,2,5,4,3}, {0,3,4,7,6,5,2,1}, {0,3,4,7,6,5,2,1}, {2,3,0,1,6,7,4,5},\
1555 {2,3,0,1,6,7,4,5}, {6,5,2,1,0,3,4,7}, {6,5,2,1,0,3,4,7}, {4,3,2,5,6,1,0,7}};
1556
1557 for(i=BegIdx; i<=EndIdx; i++)
1558 {
1559 /* Convert double precision coordinates to integers */
1560
1561 for(j=0;j<3;j++)
1562 {
1563 dbl = (arg->crd[i][j] - arg->box[j]) * arg->box[j+3];
1564 IntCrd[j] = dbl;
1565 }
1566
1567 /* Binary hilbert renumbering loop */
1568
1569 cod = 0;
1570
1571 for(j=0;j<8;j++)
1572 rot[j] = GeoCod[j];
1573
1574 for(b=0;b<21;b++)
1575 {
1576 GeoWrd = 0;
1577
1578 for(j=0;j<3;j++)
1579 {
1580 if(IntCrd[j] & m)
1581 GeoWrd |= BitTab[j];
1582
1583 IntCrd[j] = IntCrd[j]<<1;
1584 }
1585
1586 NewWrd = rot[ GeoWrd ];
1587 cod = cod<<3 | NewWrd;
1588
1589 for(j=0;j<8;j++)
1590 rot[j] = HilCod[ NewWrd ][ rot[j] ];
1591 }
1592
1593 arg->idx[i][0] = cod;
1594 arg->idx[i][1] = i;
1595 }
1596 }
1597
1598
1599 /*----------------------------------------------------------*/
1600 /* Comparison of two items for the qsort */
1601 /*----------------------------------------------------------*/
1602
1603 int CmpPrc(const void *a, const void *b)
1604 {
1605 unsigned long long *pa = (unsigned long long *)a, *pb = (unsigned long long *)b;
1606
1607 if(*pa > *pb)
1608 return(1);
1609 else
1610 return(-1);
1611 }
1612
1613
1614 /*----------------------------------------------------------*/
1615 /* Renumber a set of coordinates through a Hilbert SFC */
1616 /*----------------------------------------------------------*/
1617
1618 void HilbertRenumbering(int ParIdx, int NmbLin, double box[6], double (*crd)[3], unsigned long long (*idx)[2])
1619 {
1620 int i, NewTyp;
1621 double len = pow(2,64);
1622 ParSct *par;
1623 ArgSct arg;
1624
1625 /* Get and check lib parallel instance */
1626
1627 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
1628 return;
1629
1630 NewTyp = NewType(ParIdx, NmbLin);
1631 arg.crd = crd;
1632 arg.idx = idx;
1633 arg.box[0] = box[0];
1634 arg.box[1] = box[1];
1635 arg.box[2] = box[2];
1636 arg.box[3] = len / (box[3] - box[0]);
1637 arg.box[4] = len / (box[4] - box[1]);
1638 arg.box[5] = len / (box[5] - box[2]);
1639
1640 LaunchParallel(ParIdx, NewTyp, 0, (void *)RenPrc, (void *)&arg);
1641 ParallelQsort(ParIdx, &idx[1][0], NmbLin, 2 * sizeof(long long), CmpPrc);
1642
1643 for(i=1;i<=NmbLin;i++)
1644 idx[ idx[i][1] ][0] = i;
1645 }
1646
1647
1648 /*----------------------------------------------------------*/
1649 /* Compute the hilbert code from 2d coordinates */
1650 /*----------------------------------------------------------*/
1651
1652 static void RenPrc2D(int BegIdx, int EndIdx, int PthIdx, ArgSct *arg)
1653 {
1654 unsigned long long IntCrd[2], m=1LL<<62, cod;
1655 int i, j, b, GeoWrd, NewWrd, BitTab[2] = {1,2};
1656 double dbl;
1657 int rot[4], GeoCod[4]={1,2,0,3};
1658 int HilCod[4][4] = {{0,3,2,1}, {0,1,2,3}, {0,1,2,3}, {2,1,0,3}};
1659
1660 for(i=BegIdx; i<=EndIdx; i++)
1661 {
1662 /* Convert double precision coordinates to integers */
1663
1664 for(j=0;j<2;j++)
1665 {
1666 dbl = (arg->crd2[i][j] - arg->box[j]) * arg->box[j+2];
1667 IntCrd[j] = dbl;
1668 }
1669
1670 /* Binary hilbert renumbering loop */
1671
1672 cod = 0;
1673
1674 for(j=0;j<4;j++)
1675 rot[j] = GeoCod[j];
1676
1677 for(b=0;b<31;b++)
1678 {
1679 GeoWrd = 0;
1680
1681 for(j=0;j<2;j++)
1682 {
1683 if(IntCrd[j] & m)
1684 GeoWrd |= BitTab[j];
1685
1686 IntCrd[j] = IntCrd[j]<<1;
1687 }
1688
1689 NewWrd = rot[ GeoWrd ];
1690 cod = cod<<2 | NewWrd;
1691
1692 for(j=0;j<4;j++)
1693 rot[j] = HilCod[ NewWrd ][ rot[j] ];
1694 }
1695
1696 arg->idx[i][0] = cod;
1697 arg->idx[i][1] = i;
1698 }
1699 }
1700
1701
1702 /*----------------------------------------------------------*/
1703 /* Renumber a set of 2D coordinates through a Hilbert SFC */
1704 /*----------------------------------------------------------*/
1705
1706 void HilbertRenumbering2D(int ParIdx, int NmbLin, double box[4], double (*crd)[2], unsigned long long (*idx)[2])
1707 {
1708 int i, NewTyp;
1709 double len = pow(2,62);
1710 ParSct *par;
1711 ArgSct arg;
1712
1713 /* Get and check lib parallel instance */
1714
1715 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
1716 return;
1717
1718 NewTyp = NewType(ParIdx, NmbLin);
1719 arg.crd2 = crd;
1720 arg.idx = idx;
1721 arg.box[0] = box[0];
1722 arg.box[1] = box[1];
1723 arg.box[2] = len / (box[2] - box[0]);
1724 arg.box[3] = len / (box[3] - box[1]);
1725
1726 LaunchParallel(ParIdx, NewTyp, 0, (void *)RenPrc2D, (void *)&arg);
1727 ParallelQsort(ParIdx, &idx[1][0], NmbLin, 2 * sizeof(long long), CmpPrc);
1728
1729 for(i=1;i<=NmbLin;i++)
1730 idx[ idx[i][1] ][0] = i;
1731 }
1732
1733
1734 /*----------------------------------------------------------*/
1735 /* Setup a parallel hash table and return its index */
1736 /*----------------------------------------------------------*/
1737
1738 int AllocHash(int ParIdx, int BasTyp, int DepTyp)
1739 {
1740 int HshIdx, mul, i;
1741 ParSct *par;
1742 HshSct *hsh;
1743 TypSct *typ1, *typ2;
1744
1745 /* Get and check lib parallel instance */
1746
1747 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) || !BasTyp || !DepTyp)
1748 return(0);
1749
1750 typ1 = &par->TypTab[ BasTyp ];
1751 typ2 = &par->TypTab[ DepTyp ];
1752
1753 for(HshIdx=1; HshIdx< MaxHsh; HshIdx++)
1754 if(!par->HshTab[ HshIdx ].typ1)
1755 break;
1756
1757 if( (HshIdx == MaxHsh) || !typ1->NmbLin || !typ2->NmbLin )
1758 return(0);
1759
1760 hsh = &par->HshTab[ HshIdx ];
1761 hsh->typ1 = typ1;
1762 hsh->typ2 = typ2;
1763 mul = pow(typ1->NmbLin, 1./3.) - 1;
1764 hsh->mul[0] = mul;
1765 hsh->mul[1] = mul * mul;
1766 hsh->mul[2] = mul * mul * mul;
1767 hsh->buc = calloc(typ1->NmbLin, sizeof(BucSct));
1768
1769 printf("hash mul = %d %d %d\n",hsh->mul[2],hsh->mul[1],hsh->mul[0]);
1770 printf("hash size = %d, adr = %p\n",typ1->NmbLin,hsh->buc);
1771
1772 for(i=0;i<par->NmbCpu;i++)
1773 {
1774 hsh->ovf[i] = calloc(typ1->NmbLin / par->NmbCpu, sizeof(BucSct));
1775 hsh->NmbOvf[i] = 0;
1776 }
1777
1778 return(HshIdx);
1779 }
1780
1781
1782 /*----------------------------------------------------------*/
1783 /* Release a hash table */
1784 /*----------------------------------------------------------*/
1785
1786 void FreeHash(int ParIdx, int HshIdx)
1787 {
1788 int i;
1789 ParSct *par;
1790
1791 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]))
1792 return;
1793
1794 if( (HshIdx < 1) || (HshIdx > MaxHsh) )
1795 return;
1796
1797 if(par->HshTab[ HshIdx ].buc)
1798 free(par->HshTab[ HshIdx ].buc);
1799
1800 for(i=0;i<par->NmbCpu;i++)
1801 if(par->HshTab[ HshIdx ].ovf[i])
1802 free(par->HshTab[ HshIdx ].ovf[i]);
1803
1804 memset(&par->HshTab[ HshIdx ], 0, sizeof(HshSct));
1805 }
1806
1807
1808 /*----------------------------------------------------------*/
1809 /* Multithread compatible hash insertertion */
1810 /*----------------------------------------------------------*/
1811
1812 long long int AddHash(int ParIdx, int PthIdx, int HshIdx, int a, int b, int c, long long int dat)
1813 {
1814 int i;
1815 long long int key, idx[3];
1816 ParSct *par;
1817 HshSct *hsh;
1818 BucSct *buc, *ovf;
1819
1820 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]))
1821 return(0);
1822
1823 if( (HshIdx < 1) || (HshIdx > MaxHsh) )
1824 return(0);
1825
1826 hsh = &par->HshTab[ HshIdx ];
1827
1828 if(a < b)
1829 {
1830 if(b < c)
1831 {
1832 idx[0] = a;
1833 idx[1] = b;
1834 idx[2] = c;
1835 }
1836 else if(a < c)
1837 {
1838 idx[0] = a;
1839 idx[1] = c;
1840 idx[2] = b;
1841 }
1842 else
1843 {
1844 idx[0] = c;
1845 idx[1] = a;
1846 idx[2] = b;
1847 }
1848 }
1849 else
1850 {
1851 if(a < c)
1852 {
1853 idx[0] = b;
1854 idx[1] = a;
1855 idx[2] = c;
1856 }
1857 else if(b < c)
1858 {
1859 idx[0] = b;
1860 idx[1] = c;
1861 idx[2] = a;
1862 }
1863 else
1864 {
1865 idx[0] = c;
1866 idx[1] = b;
1867 idx[2] = a;
1868 }
1869 }
1870
1871 key = (hsh->mul[2] * idx[2] + hsh->mul[1] * idx[1] + hsh->mul[0] * idx[0]) / hsh->typ2->NmbLin;
1872 buc = &hsh->buc[ key ];
1873
1874 /* printf("pth %d, hash %d / %p, tab = %p, ovf = %p, indices = %lld %lld %lld, key %lld, buc = %p\n",\
1875 PthIdx, HshIdx, hsh, hsh->buc, hsh->ovf[ PthIdx ], idx[2], idx[1], idx[0], key, buc);
1876 */
1877 if(!buc->idx[2])
1878 {
1879 for(i=0;i<3;i++)
1880 buc->idx[i] = idx[i];
1881
1882 buc->dat = dat;
1883 return(0);
1884 }
1885 else
1886 do
1887 {
1888 if( (buc->idx[0] == idx[0]) && (buc->idx[1] == idx[1]) && (buc->idx[2] == idx[2]) )
1889 return(buc->dat);
1890 else if(!buc->nex)
1891 {
1892 if(hsh->NmbOvf[ PthIdx ] >= hsh->typ1->NmbLin / par->NmbCpu)
1893 {
1894 hsh->ovf[ PthIdx ] = calloc(hsh->typ1->NmbLin / par->NmbCpu, sizeof(BucSct));
1895 hsh->NmbOvf[ PthIdx ] = 0;
1896 puts("realloc");
1897 }
1898
1899 ovf = &hsh->ovf[ PthIdx ][ hsh->NmbOvf[ PthIdx ]++ ];
1900 ovf->nex = hsh->buc[ key ].nex;
1901 hsh->buc[ key ].nex = ovf;
1902 ovf->dat = dat;
1903
1904 for(i=0;i<3;i++)
1905 ovf->idx[i] = idx[i];
1906
1907 return(0);
1908 }
1909 }while(buc = buc->nex);
1910
1911 return(0);
1912 }
1913
1914
1915 #else
1916
1917
1918 #include <stdio.h>
1919 #include <stdlib.h>
1920 #include <string.h>
1921 #include "lplib3.h"
1922
1923 #define MaxLibPar 10
1924 #define MaxPth 128
1925 #define MaxTyp 100
1926
1927 typedef struct
1928 {
1929 int NmbLin;
1930 }TypSct;
1931
1932 typedef struct ParSct
1933 {
1934 int NmbTyp;
1935 float sta[2];
1936 void (*prc)(int, int, int, void *), *arg;
1937 TypSct TypTab[ MaxTyp+1 ];
1938 }ParSct;
1939
1940 ParSct *ParTab[ MaxLibPar+1 ];
1941 int IniLibPar = 0;
1942
1943
1944 int InitParallel(int NmbCpu)
1945 {
1946 int i, ParIdx;
1947 ParSct *par = NULL;
1948
1949 if(NmbCpu > MaxPth)
1950 return(0);
1951
1952 if(!IniLibPar)
1953 {
1954 IniLibPar = 1;
1955
1956 for(i=1;i<=MaxLibPar;i++)
1957 ParTab[i] = NULL;
1958 }
1959
1960 /* Allocate and build main parallel structure */
1961
1962 for(ParIdx=1; ParIdx<=MaxLibPar; ParIdx++)
1963 if(!ParTab[ ParIdx ])
1964 {
1965 par = ParTab[ ParIdx ] = calloc(1, sizeof(ParSct));
1966 break;
1967 }
1968
1969 if(!par)
1970 return(0);
1971
1972 return(ParIdx);
1973 }
1974
1975
1976 void StopParallel(int ParIdx)
1977 {
1978 int i;
1979 ParSct *par;
1980
1981 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
1982 return;
1983
1984 for(i=1;i<=MaxTyp;i++)
1985 FreeType(ParIdx, i);
1986
1987 free(par);
1988 ParTab[ ParIdx ] = NULL;
1989 }
1990
1991
1992 int NewType(int ParIdx, int NmbLin)
1993 {
1994 int i, TypIdx=0;
1995 TypSct *typ;
1996 ParSct *par;
1997
1998 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
1999 return(0);
2000
2001 if(NmbLin <= 0)
2002 return(0);
2003
2004 for(i=1;i<=MaxTyp;i++)
2005 if(!par->TypTab[i].NmbLin)
2006 {
2007 TypIdx = i;
2008 break;
2009 }
2010
2011 if(!TypIdx)
2012 return(0);
2013
2014 typ = &par->TypTab[ TypIdx ];
2015 typ->NmbLin = NmbLin;
2016
2017 return(TypIdx);
2018 }
2019
2020
2021 void FreeType(int ParIdx, int TypIdx)
2022 {
2023 }
2024
2025
2026 int BeginDependency(int ParIdx, int TypIdx1, int TypIdx2)
2027 {
2028 return(0);
2029 }
2030
2031
2032 void AddDependency(int ParIdx, int idx1, int idx2)
2033 {
2034 }
2035
2036
2037 void EndDependency(int ParIdx, float DepSta[2])
2038 {
2039 }
2040
2041
2042 float LaunchParallel(int ParIdx, int typ1, int typ2, void *prc, void *PtrArg)
2043 {
2044 ParSct *par;
2045 void (*UsrPrc)(int, int, int, void *) = (void (*)(int, int, int, void *))prc;
2046
2047 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
2048 return(-1.);
2049
2050 if( (typ1 < 1) || (typ1 > MaxTyp) || (typ2 < 0) || (typ2 > MaxTyp) || (typ1 == typ2) )
2051 return(-1.);
2052
2053 UsrPrc(1, par->TypTab[ typ1 ].NmbLin, 0, PtrArg);
2054
2055 return(1.);
2056 }
2057
2058
2059 int ParallelMemClear(int ParIdx, void *PtrArg, long siz)
2060 {
2061 memset(PtrArg, 0, siz);
2062 return(1);
2063 }
2064
2065 void ParallelQsort(int ParIdx, void *base, size_t nel, size_t width, int (*compar)(const void *, const void *))
2066 {
2067 ParSct *par;
2068
2069 /* Get and check lib parallel instance */
2070
2071 if( (ParIdx < 1) || (ParIdx > MaxLibPar) || !(par = ParTab[ ParIdx ]) )
2072 return;
2073
2074 qsort(base, nel, width, compar);
2075 }
2076
2077 #endif