9
9
4
5
5
6
3 1
(a)
9
8
4
5
5
4
6
2
9
7
4
5
5
6 1
(b)
(c)
9
6
4
5
5
5
(d)
9 5
4
5
5
4
6
9
8 4
4
5
5
3
(e)
(f)
H
T
H
T
H
T
H
T
H
T
H
T
1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4
71
7
2
7
3
7
7
12
Figure 1. Work Stealing: An Illustration
tion strategy known as fast/slow clones, and a distinct solu-
tion for locking [16]. Both are out of the scope of this paper.
Deque Management One natural consequence of placing
continuations onto the deque is that the order of tasks on
the deque reflects the immediacy of processing these items
as defined by the work-first principle: the earlier the item is
placed, the less immediate it is. For example, if the control
flow of a worker reaches L10, two tasks are placed on the
deque, the program counter for L3 (when the spawn in L2 is
executed) and the program counter for L7 (when the spawn
in L6 is executed). In a serial execution, L3 will only be
encountered after L7.
With this observation, deque is designed as a data struc-
ture that can be manipulated on both ends. Let us call the
head of the deque as the earliest item placed on the deque by
the worker, whereas the tail of the deque as the latest. When
a worker becomes idle, it always retrieves from the tail of
Algorithm 2.1 Worker
w : WORKER
procedure SCHEDULE(w)
loop
t ← POP(w)
if t==null then
v = SELECT()
t ← STEAL(v)
if t==null then
YIELD(w)
else
WORK(w, t)
end if
else
WORK(w, t)
end if
end loop
end procedure
Structures
structure WORKER
DQ // deque (array)
H // head index
T // tail index
end structure
structure TASK
... // program counter, etc
end structure
Other Definitions
procedure WORK(w, t)
// worker w runs task t
procedure SELECT()
// select and return a victim
procedure YIELD(w)
// yield worker w
procedure LOCK(w)
procedure UNLOCK(w)
// lock/unlock w
Algorithm 2.2 Push
w : WORKER
t : TASK
procedure PUSH(w,t)
w.T++
w.DQ[w.T] ← t
end procedure
Algorithm 2.3 Pop
w : WORKER
procedure POP(w)
w.T– –
if w.H > w.T then
w.T++
LOCK(w)
w.T−−
if w.H > w.T then
w.T++
UNLOCK(w)
return null
end if
end if
UNLOCK(w)
return w.DQ[w.T]
end procedure
Algorithm 2.4 Steal
v : WORKER // victim
procedure STEAL(v)
LOCK(v)
v.H++
if v.H > v.T then
v.H– –
UNLOCK(v)
return null
end if
UNLOCK(v)
return v.DQ[v.H]
end procedure
Figure 2. Work Stealing Algorithm
its own deque, i.e., the most immediate task. On the other
hand, when a thief attempts to steal from a worker, it always
retrieves from the head of that worker’s deque, i.e., the least
immediate task. From now on, we call the worker placing a
task to its own deque a push, while removing a task from its
own deque a pop. We continue to use term steal to refer to a
worker removing a task from another worker’s deque.
515
剩余14页未读，继续阅读
xiaochaoyxc
- 粉丝: 0
- 资源: 7
我的内容管理
展开
最新资源
- 构建Cadence PSpice仿真模型库教程
- VMware 10.0安装指南：步骤详解与网络、文件共享解决方案
- 中国互联网20周年必读：影响行业的100本经典书籍
- SQL Server 2000 Analysis Services的经典MDX查询示例
- VC6.0 MFC操作Excel教程：亲测Win7下的应用与保存技巧
- 使用Python NetworkX处理网络图
- 科技驱动：计算机控制技术的革新与应用
- MF-1型机器人硬件与robobasic编程详解
- ADC性能指标解析：超越位数、SNR和谐波
- 通用示波器改造为逻辑分析仪：0-1字符显示与电路设计
- C++实现TCP控制台客户端
- SOA架构下ESB在卷烟厂的信息整合与决策支持
- 三维人脸识别：技术进展与应用解析
- 单张人脸图像的眼镜边框自动去除方法
- C语言绘制图形：余弦曲线与正弦函数示例
- Matlab 文件操作入门：fopen、fclose、fprintf、fscanf 等函数使用详解
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
