A Framework for Maximizing Performance of Self-scheduling Algorithms 461
Fig. 1. LASS operations
iterations are available in the batch B
i
, T
i
can help other Workers completing
their batches. In this case, multiple Workers will contend the access to the same
batch of iterations, hence synchronization is required. This is the only scenario
in which LASS requires synchronization. Indeed, with the exception of the last
case mentioned above, a Worker can fetch C
j
iterations from C without explicitly
gain exclusive access to the queue of iterations. Once a Worker fetches a chunk
size number from C, it moves the index of C to the next position. Because the
index of C is shared by all the Workers, two or more Workers can access the
same chunk size sometimes. Even if this happens, the algorithm can still run
correctly because the termination of the loop is not detected by checking C and
C just provides chunk sizes but not real chunks.
For clarity, we present the example in Figure 1. Let us assume the iterations
space being composed of 1000 iterations, that is Γ = {I
1
,I
2
, ···,I
1000
},andthat
these iterations need to be scheduled to run on P = 4 cores. The iteration space
is partitioned in four batches composed of 250 iterations, Γ = Γ
1
∪ Γ
2
∪ Γ
3
∪ Γ
4
.
Four Workers are spawn, T
1
, T
2
, T
3
and T
4
. Each Worker is assigned to a different
core, so that any time the Worker T
j
processes a chunk, it will always run on
the core P
j
.
The Worker T
j
is the owner of the batch Γ
j
. When the parallel execution
starts, the Worker T
j
has exclusive access to its own batch. Before the Workers
start, a self-scheduling algorithms is used to create a list of chunks, named C.
Iterations are scheduled in chunks as indicated in C.Letn
i
be the iterations
index in Γ
i
. At a scheduling step in Figure 1, n
1
= 100, n
2
= 450, and the upper
bound for Γ
3
is n
3
= 750. There are three distinct possible scenarios:
– The Worker T
1
attempts to fetch C
j
iterations from Γ
1
.Ifn
1
+ C
j
<u
1
, C
j
consecutive iterations can be fetched from Γ
1
. Next, the Worker T
1
fetches
C
j
consecutive iterations from Γ
1
starting from n
1
and executes them.
– The Worker T
2
attempts to fetch C
j
from Γ
2
.Ifn
2
+ C
j
>u
2
,onlyu
2
− n
2
are fetched from Γ
2
,andC
= C
j
− (u
2
− n
2
) is a new chunk size which is
appended to the list of chunk sizes.
– The Worker T
3
attempts to fetch C
j
from Γ
3
.Ifn
3
+C
j
= u
3
, all iterations in
Γ
3
have already been processed. In this case, n
3
points to n
4
. If the iterations
in Γ
4
have also been consumed, both n
3
and n
4
point to n
1
.
剩余11页未读，继续阅读
weixin_38616139
- 粉丝: 3
- 资源: 908
我的内容管理
展开
最新资源
- JSP+SSM科研管理系统响应式网站设计案例
- 推荐一款超级好用的嵌入式串口调试工具
- PHP域名多维查询平台：高效精准的域名搜索工具
- Citypersons目标检测数据集：Yolo格式下载指南
- 掌握MySQL面试必备：程序员面试题解析集锦
- C++软件开发培训：核心技术资料深度解读
- SmartSoftHelp二维码工具：生成与解析条形码
- Android Spinner控件自定义字体大小的方法
- Ubuntu Server on Orangepi3 LTS 官方镜像发布
- CP2102 USB驱动程序的安装与更新指南
- ST-link固件升级指南：轻松更新程序步骤
- Java实现的质量管理系统Demo功能分析与操作
- Everything高效文件搜索工具：快速精确定位文件
- 基于B/S架构的酒店预订系统开发实践
- RF_Setting(E22-E90(SL)) V1.0中性版功能解析
- 高效转换M3U8到MP4：免费下载工具发布
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
