没有合适的资源?快使用搜索试试~ 我知道了~
LogGP Analysis of Parallel Sorting Algorithms 并行排序算法的LogGP分析.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 109 浏览量
2024-04-02
14:31:52
上传
评论
收藏 822KB DOC 举报
温馨提示
试读
10页
LogGP Analysis of Parallel Sorting Algorithms 并行排序算法的LogGP分析.doc
资源推荐
资源详情
资源评论
LogGP Analysis of Parallel Sorting
Algorithms
Greg Tracy, University of Wisconsin, Madison
Abstract
The need for solutions to large, complex computations has grown considerably. As a
result, so has the need for models that can accurately predict the performance of parallel
systems without constructing the algorithms themselves. Parallel software developers
have a need for analyzing design changes in a quick and efficient manner. The LogGP
model was developed to help answer this problem. In this paper, I apply the LogGP
model to the analysis of parallel sorting algorithms. This paper outlines equations used
to model the performance of parallel sorting and compares the results to models built
using the LogP model as well as comparisons with actual measurements made on the
target hardware.
1 Introduction
This paper investigates the use of the parallel computation model, LogGP [AISS95] in
the analysis of parallel sorting algorithms in a network of workstations (NOW). Although
parallel sorting algorithms are fairly well developed, an accurate model provides some
insight into performance characteristics of the sort as well a quick and efficient means for
testing improvements to the algorithm. The work done in this research is the foundation
for models of more advanced parallel applications. The problems researched in parallel
sorting apply to lots of other parallel applications. The duality of computation and
communication is a common attribute for lots of interesting distributed applications.
In previous work [DCMS96], the LogP [CKPS93] model was applied to a set of sorting
algorithms running on the Thinking Machines CM-5. Those models were accurate to
within 12% of the measured results on the CM-5 and provided compeling evidence that
the LogP model provided the necessary accuracy for parallel sorts. This research
investigates and produces results which indicate that the use of the LogGP model will
result in more accurate models for parallel sorting algorithms due to the size of messages
which are transmitted between nodes. The LogP model assumes “small”, fixed sized
messages being passed between nodes, and therefore does not account for the true
behavior of the NOW sorting algorithm.
This paper will outline the LogGP model created to measure the expected performance of
sorting in a NOW environment. I will present results for a wide range of node
configurations and compare the results of the LogGP model to a LogP model of the same
problem. I will also present data for a series of model variations in an attempt to more
accurately model the current NOW-Sort implementation. This is followed up with an
资源评论
百态老人
- 粉丝: 1592
- 资源: 2万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功