并行算法的一般设计过程

1. PCAM设计方法学

设计并行算法的四个阶段:

划分(Partitioning):分解成小的任务,开拓并发性

通讯(Communication):确定诸任务间的数据交换,监测划分的合理性;

组合(Agglomeration):依据任务的局部性,组合成更大的任务;

映射(Mapping):将每个任务分配到处理器上,提高算法的性能。

2. 划分

充分开拓算法的并发性和可扩放性;

先进行数据分解(称域分解),再进行计算功能的分解(称功能分解);

使数据集和计算集互不相交;

划分阶段忽略处理器数目和目标机器的体系结构;

主要分为两类划分:

Ø  域分解(domaindecomposition)

Ø  功能分解(functionaldecomposition)

域分解:

划分的对象是数据,可以是算法的输入数据、中间处理数据和输出数据;

将数据分解成大致相等的小数据片;

划分时考虑数据上的相应操作;

如果一个任务需要别的任务中的数据,则会产生任务间的通讯;

 

功能分解:

划分的对象是计算,将计算划分为不同的任务,其出发点不同于域分解;

划分后,研究不同任务所需的数据。如果这些数据不相交的,则划分是成功的;如果数据有相当的重叠,意味着要重新进行域分解和功能分解;

功能分解是一种更深层次的分解。

划分依据:

划分是否具有灵活性?

划分是否避免了冗余计算和存储?

划分任务尺寸是否大致相当?

任务数与问题尺寸是否成比例?

功能分解是一种更深层次的分解,是否合理?

3. 通讯

通讯是PCAM设计过程的重要阶段;

划分产生的诸任务,一般不能完全独立执行,需要在任务间进行数据交流;从而产生了通讯;

功能分解确定了诸任务之间的数据流;

诸任务是并发执行的,通讯则限制了这种并发性;

局部/全局通讯

 

结构化/非结构化通讯

结构化通讯:存在一个相同的通讯模式

非结构化通讯:不存在一个相同的通讯模式

静态/动态通讯

同步/异步通讯

通讯判据:

所有任务是否执行大致相当的通讯?

是否尽可能的局部通讯?

通讯操作是否能并行执行?

同步任务的计算能否并行执行?

4. 组合

组合是由抽象到具体的过程,是将组合的任务能在一类并行机上有效的执行;

合并小尺寸任务,减少任务数。如果任务数恰好等于处理器数,则也完成了映射过程;

通过增加任务的粒度和重复计算,可以减少通讯成本;

保持映射和扩展的灵活性,降低软件工程成本;

表面容积效应:

通讯量与任务子集的表面成正比,计算量与任务子集的体积成正比;

增加重复计算有可能减少通讯量;

重复计算:

重复计算减少通讯量,但增加了计算量,应保持恰当的平衡;

重复计算的目标应减少算法的总运算时间;

组合判据:

增加粒度是否减少了通讯成本?

重复计算是否已权衡了其得益?

是否保持了灵活性和可扩放性?

组合的任务数是否与问题尺寸成比例?

是否保持了类似的计算和通讯?

有没有减少并行执行的机会?

5. 映射

每个任务要映射到具体的处理器,定位到运行机器上;

任务数大于处理器数时,存在负载平衡和任务调度问题;

映射的目标:减少算法的执行时间

并发的任务à 不同的处理器

任务之间存在高通讯的à 同一处理器

映射实际是一种权衡,属于NP完全问题;

负载平衡算法:

静态的:事先确定;

概率的:随机确定;

动态的:执行期间动态负载;

基于域分解的:

Ø  递归对剖

Ø  局部算法

Ø  概率方法

Ø  循环映射

 

任务调度算法:

任务放在集中的或分散的任务池中,使用任务调度算法将池中的任务分配给特定的处理器。下面是两种常用调度模式:

经理/雇员模式

非集中模式

映射判据:

采用集中式负载平衡方案,是否存在通讯瓶颈?

采用动态负载平衡方案,调度策略的成本如何?

 

时间: 2012-12-02

并行算法的一般设计过程的相关文章

网页设计过程中应该注意的十个问题

1.不要滥用Flash Adobe公司的这项动画技术让互联网变得更为强大,从Nike公司非常夸张的首页动画到众多广告商使用的网页Banner.但是这项技术非常容易被滥用,过多的动画不仅没有实用性而且还会拖慢用户的网页浏览器. 2.不要让广告遮挡了网站内容 的确,广告对网站的生存来说是至关重要的,但研究表明,弹出广告和整页的广告一旦遮挡了网站内容,那它们的效用会大打折扣,同时也会影响读者是否会再来光顾.一个能够根据读者的要求进行伸缩的广告会更合适一些. 3.不要让网页看起来杂乱无章 网页是一个大杂

交互设计经验:设计过程中存在太多的矛盾

文章描述:交互设计经验:设计过程中存在太多的矛盾. 在产品团队中经常听到有人表态:"我们要做简洁的用户界面",同时又有另外一种声音传来:"我们要做功能强大的产品".乍一听,简洁意味着用户界面控件精炼,然而少数的交互方式如何表达各类强大的功能?反之,强大意味着功能丰富强劲,必然拥有错综复杂的联系,如何让其界面保持简洁?两者似乎无法共存,这让我突然想到自相矛盾的故事,楚国商人夸耀自己的矛锐利万分,同时自己的盾又坚固无比, "以子之矛,陷子之盾,何如?"

图标设计过程中需要注意的问题

文章描述:那么怎么样才能做出一套好的图标?在图标设计过程中需要注意哪些问题? 图标在生活中运用是显而可见的.例如:男女厕所标志和各种交通标志等.在计算机系统或软件方面的应用也是很广泛.例如:程序标识.数据标识.命令选择.模式信号或切换开关.状态指示等.下面的例子更形象的说明这个问题. (图片来源:九铭)外国人A与中国人B,两人在语言上存在差异对文字的认识是不同的,用图标来表示,会缩短语言描述的距离.所以图标更具有快捷传达信息.便于记忆的特性.那么图标被广泛使用的时候,什么样的图标才是好图标呢?好

设计案例分享:腾讯手机令牌的设计过程

文章描述:QQ安全我做主-手机令牌2.0设计分享. 一款小小的工具软件,如何赢得  iPhone app store4星级+评价:Android 电子市场4.5星评价,让我与您一起分享手机令牌的设计过程 什么是手机令牌? 手机令牌是通过6位动态密码保护QQ帐号.Q币和游戏装备等虚拟财产安全的手机软件.手机令牌每30S更换一次动态密码,用户在敏感操作的时候验证动态密码,以此保障自己的帐号安全.简单的说:手机令牌是一个动态密码的生成软件.是我们专为保护用户QQ帐号安全设计的手机APP. 设计工作主要

数据库设计过程中一些命名规范

规范|过程|设计|数据|数据库|数据库设计 数据库设计过程中命名规范很是重要,命名规范合理的设计能够省去开发人员很多时间去区别数据库实体. 数据库物理设计包括:表设计,视图设计,存储过程设计,用户自定义函数设计等等. 1.  表设计命名规范:表使用t开头最好能将表根据属性分类并作好编号. 如:编码表可写为tBM001Something  t为表开头,BM为业务类型,001为该类别中的第几个表something是表的名称注释. 2. 视图设计命名规范:视图设计过程中使用v开头,视图命名以制作视图的

网页设计师页面设计过程中也要注意页面性能

一名网页设计师在做具体设计的时候应该考虑的问题有哪些?业务,产品,信息结构,交互,视觉--别忘了还有页面性能.我所崇尚的其实一直都是小作坊似的创业团队协作开发模式,大伙儿能快速沟通,就算设计师没关注到页面性能这一点,前端同学也能迅速提醒他,因为他俩就无时无刻不在一起.而现在在标准项目流程中,大家的沟通成本成倍增加了,除非是与世隔绝的闭关(就算是闭关,前端同学多半也在陪着开发),前端同学很难在页面设计过程中就和设计师沟通页面性能的问题. 页面性能不仅仅是前端同学的问题 页面性能的重要性不再赘述,就

用户体验设计:Nearby Tweets改版的完整设计过程

UX Case Study: Designing a user-focused web appBrian Cray版权所有作者:Brian Cray译者:UCD翻译小组,波希米亚原文地址: http://briancray.com/2010/01/26/ux-case-study-designing-user-focused-web-app/ 这篇文章记录了Nearby Tweets改版的完整设计过程.Web开发者和商家期望借此获取些灵感.用户则更有兴趣找寻这些设计中所蕴藏的东西.当然,我希望能

符合用户情感设计 QQ2010个性皮肤设计过程

09年的电影缓缓的落下帷幕,以及新年伊始,轰轰烈烈催人癫狂的<阿凡达>.整年里,最让人我记忆深刻的还是<飞屋历险记>. Carl与Ellie被南美的那个名叫"paradisefall"的瀑布魂牵梦萦,于是他们决定一天天的往容器里存钱,积攒旅费以完成童年的梦想.可是,生活毕竟不是天天祥和与顺心,总是充满着未知和意外,车子爆胎,骨折住院,被大树压垮房子,面对种种突如而来的变故,容器只能一次次的被打碎挪为他用重头再来.可即便如此,又能怎样,每一个硬币投入锃亮的容器,都

Anders Hejlsberg 谈C#设计过程

过程|设计 一 1.C#设计过程 ? Bruce Eckel:我听说C#是一个工程师小组在一个屋子里设计出来的? Anders Hejlsberg:是的.4年来,我们一直呆在这个屋子里.现在,每周一.三.五,我们仍然在这里会面. Bruce Eckel:我很想了解一些关于C#设计过程的情况.我直接或间接参与过几种语言的设计工作,如Python.在Python设计过程中,Guido van Rossum被我们戏称为"仁慈的独裁者". Anders Hejlsberg:哦,Guido va