Debian Codegraph @

bwa-apache2/kthread.c

raw
1 #include <pthread.h>
2 #include <stdint.h>
3 #include <stdlib.h>
4 #include <limits.h>
5
6 /************
7 * kt_for() *
8 ************/
9
10 struct kt_for_t;
11
12 typedef struct {
13 struct kt_for_t *t;
14 long i;
15 } ktf_worker_t;
16
17 typedef struct kt_for_t {
18 int n_threads;
19 long n;
20 ktf_worker_t *w;
21 void (*func)(void*,long,int);
22 void *data;
23 } kt_for_t;
24
25 static inline long steal_work(kt_for_t *t)
26 {
27 int i, min_i = -1;
28 long k, min = LONG_MAX;
29 for (i = 0; i < t->n_threads; ++i)
30 if (min > t->w[i].i) min = t->w[i].i, min_i = i;
31 k = __sync_fetch_and_add(&t->w[min_i].i, t->n_threads);
32 return k >= t->n? -1 : k;
33 }
34
35 static void *ktf_worker(void *data)
36 {
37 ktf_worker_t *w = (ktf_worker_t*)data;
38 long i;
39 for (;;) {
40 i = __sync_fetch_and_add(&w->i, w->t->n_threads);
41 if (i >= w->t->n) break;
42 w->t->func(w->t->data, i, w - w->t->w);
43 }
44 while ((i = steal_work(w->t)) >= 0)
45 w->t->func(w->t->data, i, w - w->t->w);
46 pthread_exit(0);
47 }
48
49 void kt_for(int n_threads, void (*func)(void*,long,int), void *data, long n)
50 {
51 int i;
52 kt_for_t t;
53 pthread_t *tid;
54 t.func = func, t.data = data, t.n_threads = n_threads, t.n = n;
55 t.w = (ktf_worker_t*)alloca(n_threads * sizeof(ktf_worker_t));
56 tid = (pthread_t*)alloca(n_threads * sizeof(pthread_t));
57 for (i = 0; i < n_threads; ++i)
58 t.w[i].t = &t, t.w[i].i = i;
59 for (i = 0; i < n_threads; ++i) pthread_create(&tid[i], 0, ktf_worker, &t.w[i]);
60 for (i = 0; i < n_threads; ++i) pthread_join(tid[i], 0);
61 }
62
63 /*****************
64 * kt_pipeline() *
65 *****************/
66
67 struct ktp_t;
68
69 typedef struct {
70 struct ktp_t *pl;
71 int64_t index;
72 int step;
73 void *data;
74 } ktp_worker_t;
75
76 typedef struct ktp_t {
77 void *shared;
78 void *(*func)(void*, int, void*);
79 int64_t index;
80 int n_workers, n_steps;
81 ktp_worker_t *workers;
82 pthread_mutex_t mutex;
83 pthread_cond_t cv;
84 } ktp_t;
85
86 static void *ktp_worker(void *data)
87 {
88 ktp_worker_t *w = (ktp_worker_t*)data;
89 ktp_t *p = w->pl;
90 while (w->step < p->n_steps) {
91 // test whether we can kick off the job with this worker
92 pthread_mutex_lock(&p->mutex);
93 for (;;) {
94 int i;
95 // test whether another worker is doing the same step
96 for (i = 0; i < p->n_workers; ++i) {
97 if (w == &p->workers[i]) continue; // ignore itself
98 if (p->workers[i].step <= w->step && p->workers[i].index < w->index)
99 break;
100 }
101 if (i == p->n_workers) break; // no workers with smaller indices are doing w->step or the previous steps
102 pthread_cond_wait(&p->cv, &p->mutex);
103 }
104 pthread_mutex_unlock(&p->mutex);
105
106 // working on w->step
107 w->data = p->func(p->shared, w->step, w->step? w->data : 0); // for the first step, input is NULL
108
109 // update step and let other workers know
110 pthread_mutex_lock(&p->mutex);
111 w->step = w->step == p->n_steps - 1 || w->data? (w->step + 1) % p->n_steps : p->n_steps;
112 if (w->step == 0) w->index = p->index++;
113 pthread_cond_broadcast(&p->cv);
114 pthread_mutex_unlock(&p->mutex);
115 }
116 pthread_exit(0);
117 }
118
119 void kt_pipeline(int n_threads, void *(*func)(void*, int, void*), void *shared_data, int n_steps)
120 {
121 ktp_t aux;
122 pthread_t *tid;
123 int i;
124
125 if (n_threads < 1) n_threads = 1;
126 aux.n_workers = n_threads;
127 aux.n_steps = n_steps;
128 aux.func = func;
129 aux.shared = shared_data;
130 aux.index = 0;
131 pthread_mutex_init(&aux.mutex, 0);
132 pthread_cond_init(&aux.cv, 0);
133
134 aux.workers = (ktp_worker_t*)alloca(n_threads * sizeof(ktp_worker_t));
135 for (i = 0; i < n_threads; ++i) {
136 ktp_worker_t *w = &aux.workers[i];
137 w->step = 0; w->pl = &aux; w->data = 0;
138 w->index = aux.index++;
139 }
140
141 tid = (pthread_t*)alloca(n_threads * sizeof(pthread_t));
142 for (i = 0; i < n_threads; ++i) pthread_create(&tid[i], 0, ktp_worker, &aux.workers[i]);
143 for (i = 0; i < n_threads; ++i) pthread_join(tid[i], 0);
144
145 pthread_mutex_destroy(&aux.mutex);
146 pthread_cond_destroy(&aux.cv);
147 }