1 // Copyright 2012 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Parallel for algorithm.
12 // the thread's iteration space [32lsb, 32msb)
20 byte pad
[CacheLineSize
];
24 runtime_parforalloc(uint32 nthrmax
)
28 // The ParFor object is followed by CacheLineSize padding
29 // and then nthrmax ParForThread.
30 desc
= (ParFor
*)runtime_malloc(sizeof(ParFor
) + CacheLineSize
+ nthrmax
* sizeof(ParForThread
));
31 desc
->thr
= (ParForThread
*)((byte
*)(desc
+1) + CacheLineSize
);
32 desc
->nthrmax
= nthrmax
;
37 runtime_parforsetup(ParFor
*desc
, uint32 nthr
, uint32 n
, void *ctx
, bool wait
, void (*body
)(ParFor
*, uint32
))
42 if(desc
== nil
|| nthr
== 0 || nthr
> desc
->nthrmax
|| body
== nil
) {
43 runtime_printf("desc=%p nthr=%d count=%d body=%p\n", desc
, nthr
, n
, body
);
44 runtime_throw("parfor: invalid args");
59 for(i
=0; i
<nthr
; i
++) {
60 begin
= (uint64
)n
*i
/ nthr
;
61 end
= (uint64
)n
*(i
+1) / nthr
;
62 pos
= &desc
->thr
[i
].pos
;
63 if(((uintptr
)pos
& 7) != 0)
64 runtime_throw("parforsetup: pos is not aligned");
65 *pos
= (uint64
)begin
| (((uint64
)end
)<<32);
70 runtime_parfordo(ParFor
*desc
)
73 uint32 tid
, begin
, end
, begin2
, try, victim
, i
;
74 uint64
*mypos
, *victimpos
, pos
, newpos
;
75 void (*body
)(ParFor
*, uint32
);
78 // Obtain 0-based thread index.
79 tid
= runtime_xadd(&desc
->thrseq
, 1) - 1;
80 if(tid
>= desc
->nthr
) {
81 runtime_printf("tid=%d nthr=%d\n", tid
, desc
->nthr
);
82 runtime_throw("parfor: invalid tid");
85 // If single-threaded, just execute the for serially.
87 for(i
=0; i
<desc
->cnt
; i
++)
97 // While there is local work,
98 // bump low index and execute the iteration.
99 pos
= runtime_xadd64(mypos
, 1);
100 begin
= (uint32
)pos
-1;
101 end
= (uint32
)(pos
>>32);
109 // Out of work, need to steal something.
112 // If we don't see any work for long enough,
113 // increment the done counter...
114 if(try > desc
->nthr
*4 && !idle
) {
116 runtime_xadd(&desc
->done
, 1);
118 // ...if all threads have incremented the counter,
120 if(desc
->done
+ !idle
== desc
->nthr
) {
122 runtime_xadd(&desc
->done
, 1);
125 // Choose a random victim for stealing.
126 victim
= runtime_fastrand1() % (desc
->nthr
-1);
129 victimpos
= &desc
->thr
[victim
].pos
;
131 // See if it has any work.
132 pos
= runtime_atomicload64(victimpos
);
134 end
= (uint32
)(pos
>>32);
140 runtime_xadd(&desc
->done
, -1);
143 begin2
= begin
+ (end
-begin
)/2;
144 newpos
= (uint64
)begin
| (uint64
)begin2
<<32;
145 if(runtime_cas64(victimpos
, pos
, newpos
)) {
151 // Has successfully stolen some work.
153 runtime_throw("parfor: should not be idle");
154 runtime_atomicstore64(mypos
, (uint64
)begin
| (uint64
)end
<<32);
156 me
->nstealcnt
+= end
-begin
;
160 if(try < desc
->nthr
) {
162 } else if (try < 4*desc
->nthr
) {
164 runtime_procyield(20);
165 // If a caller asked not to wait for the others, exit now
166 // (assume that most work is already done at this point).
167 } else if (!desc
->wait
) {
169 runtime_xadd(&desc
->done
, 1);
171 } else if (try < 6*desc
->nthr
) {
181 runtime_xadd64(&desc
->nsteal
, me
->nsteal
);
182 runtime_xadd64(&desc
->nstealcnt
, me
->nstealcnt
);
183 runtime_xadd64(&desc
->nprocyield
, me
->nprocyield
);
184 runtime_xadd64(&desc
->nosyield
, me
->nosyield
);
185 runtime_xadd64(&desc
->nsleep
, me
->nsleep
);
193 // For testing from Go.
195 runtime_parforiters(ParFor
*desc
, uintptr tid
, uintptr
*start
, uintptr
*end
)
197 *start
= (uint32
)desc
->thr
[tid
].pos
;
198 *end
= (uint32
)(desc
->thr
[tid
].pos
>>32);