数学建模社区-数学中国

标题: A题 答疑： 串行算法的并行化处理 [打印本页]
作者: huashi3483    时间: 2009-4-24 09:04
标题: A题 答疑： 串行算法的并行化处理
本答疑专家只会负责文字面上解释，不涵盖解题内容及思路，选择本题者有疑问者请回帖，专家组会选择其问题的合理性负责答疑，其答疑结果将在主帖内公布！
作者: yujun198906    时间: 2009-4-24 09:42
网络方面的，好像不行。我们没有学C语言
作者: madio    时间: 2009-4-24 09:47
学过VB也行，不影响，不需要编程，稍微了解一点相关知识就可以了！
作者: 瀚海桑田    时间: 2009-4-24 10:38
大家怎么样了  还没有头绪
作者: 瀚海桑田    时间: 2009-4-24 10:41
请问是在别人原有的算法上进行改进吗
作者: madio    时间: 2009-4-24 10:59
是对一些别人的算法结构进行处理，使得便于发挥多核的优势！ 5# 瀚海桑田
作者: pkucs    时间: 2009-4-24 11:06
明白了，加油
作者: hufeng    时间: 2009-4-24 11:09
大家做A题的有头绪没啊？。。。。。。。。。。。。。。。
作者: zhouzhihua    时间: 2009-4-24 11:09
我学C语言但是还没有头绪有点难
作者: zhouzhihua    时间: 2009-4-24 11:10
我学C语言但是还没有头绪有点难
作者: zhouzhihua    时间: 2009-4-24 11:11
我学C语言但是还没有头绪有点难
作者: 811083579    时间: 2009-4-24 11:18
讲点思路啊！怎么搞！
作者: 811083579    时间: 2009-4-24 11:19
A题啊？用什么写啊
作者: 811083579    时间: 2009-4-24 11:21
怎么不给点数据啊
作者: p31415    时间: 2009-4-24 11:31
建议管理员搞一个网上投票，看下有多少人选那些题目
作者: p31415    时间: 2009-4-24 11:32
A题我觉得有给一个简单的例子，帮助一下理解题目。
作者: p31415    时间: 2009-4-24 11:53
毫无头绪
作者: moyemuliao    时间: 2009-4-24 11:58
大家做A题的人多吗？
作者: 591822384    时间: 2009-4-24 12:00
顺序执行，分支，循环可以互相包含吗
作者: madio    时间: 2009-4-24 12:07
不要一开始考虑得太复杂，首先看看能不能处理一些易并行的程序，比如说题目中提到的数组求和程序，再深入一些比如处理一下求最短路的动态规划程序，把它做分枝并行，看看在一个程序中如何识别出一些易并行的部分，当然有时间还可以继续深入比如考虑一下如何将循环和分支的混合结构拆开等！慢慢来！ 17# p31415
作者: madio    时间: 2009-4-24 12:08
题目中的要求没有限定不相互包含，也就是说会有这样的情况，但是也可以逐步深入！ 19# 591822384
作者: aqua2001    时间: 2009-4-24 13:36
本帖最后由 aqua2001 于 2009-4-24 13:39 编辑
. K3 C$ F. t+ ]/ x7 w
1 B" |; u, }; ]' r: L依我看，第一步就是易并行的部分和没法并行化的部分怎么才能区分开来。数组求和的程序，确实是可以分成两部分并行运行的。但是如果是别的呢？举个例子，3x+1问题：- r1 W: @: g$ T: U+ b' J# G
int a=15;2 `2 P3 u' ^& p  d
while(a>1){
/ g# ~0 Y  A+ W: ^1 \6 F; V' K    if(a%2==0)
3 Z# R% c& ~" G4 D4 ?        a=a/2;1 D5 @$ S" t* S, v) V
    else8 |/ @7 x% w4 F. `
        a=3*a+1;7 X! R% l% r0 t: I: k
}
. ]; y& U" V0 }" F- N- K- y这个意思是如果a是偶数，则除以2。如果a是奇数，则乘以3再加1。反复操作。这个过程，从一切初始值出发，最后都会变成1的（这个未经证明，称为3x+1问题，又称角谷猜想）。1 g7 b2 N$ T0 S( {

; j4 ?+ `3 p; C. T0 e9 h这段算法从意思上看，应该说，很难把它拆分成两部分并行处理，并加快运行速度。这个和数组求和的区别到底是什么，第一步就是区分这个。
. L% ~6 @7 h0 n! ^* P' H( n4 j' I7 c6 j" g% y
先考虑简单的算法，再考虑复杂的。如果循环和条件之类的东西彻底嵌套在一起，人通过理解算法的含义，大概还是能分析得比较清楚的。但是使用模型来做一个确定的方法，就肯定困难一些了。
作者: linkindan    时间: 2009-4-24 13:45
http://www.spsschina.cn/?fromuser=linkindan
6 }8 @* E8 L* u5 J/ e下载年鉴的好地方
作者: xiehongye    时间: 2009-4-24 16:17
串行算法并行化基础  大家有这本书吗？
作者: xiehongye    时间: 2009-4-24 16:20
A题让人不知所措，看似专业但又不专业，无从下手，不知道需要写成什么样。
作者: e622261    时间: 2009-4-24 16:27
串行算法并行化基础 这本书有，下了题目后才到图书馆借来的。。。正在研究中
作者: moyemuliao    时间: 2009-4-24 17:34
26# e622261 $ h1 d- k2 |+ u: [- ]5 l: K

- ?& b7 S& N- w& V
, f1 W* C$ m- w* X0 f- [书名对吗？我怎么找不到啊？
作者: e622261    时间: 2009-4-24 18:13
对的，是这本书，很薄的一本书
作者: xiehongye    时间: 2009-4-24 19:15
28# e622261 % ]5 d$ Z* o+ |$ P' {
你们有啊，真好。我们图书馆没有。
作者: gdufs0    时间: 2009-4-24 22:21
今年的题目看上去很难 都没点头绪
作者: aqua2001    时间: 2009-4-24 23:51
据出题人所述，本题的思路是希望对“算法能否分解成独立运行的若干部分”这件事情建立模型。虽然这个问题本身有很深的专业背景，但不希望建模的时候在专业的细节方面花费过多的精力。更多地需要对算法“流程”的“前后相关性”的理解。所以本题的重点不是并行计算的技术细节如何实现（在典型的并行计算的书上可以看到大量细节内容，包括如何设计一些特定变量使两个进程保持同步运行，两个进程使用同一个变量时需要互斥机制，等等），而是对算法流程在“逻辑上”或者“概念上”的分析和处理。写论文的时候也要注意不要在技术细节上花费太多精力。
5 ]- i- b. r9 ?) i7 C
% Q, w. ?. ?, e另据参与出题的专家所述，本题中，虽然算法例是由C语言写就的，但也完全可以表示成伪代码，或者表示成流程图。所以对具体技术细节该如何处理将不是需要解决的重点，重点是如何对“流程的理解”做出模型化的处理。
作者: moyemuliao    时间: 2009-4-25 01:04
反对，影响别人做题思路，有不公平的因素在里面！！！！！不是说不给解题内容和思路吗！！！
作者: chenling    时间: 2009-4-25 01:13
请问如何复制B题的数据的内容？
作者: aqua2001    时间: 2009-4-25 01:16
这只是对题目要求的补充说明。否则做出来的内容可能和题目要求严重不一致。这些意见在题目的正文中都已提到，这里只是详述。不属于对思路的提示或者限制。
作者: moyemuliao    时间: 2009-4-25 02:18
只是略微发点牢骚，因为白天有课没能按时接题比大家的时间少，觉得容易让一堆人想偏的地方又被指出来了，心里只是略微有些不爽。版主能给予重视真的有点受宠若惊，支持数学中国！支持比赛！
作者: liushuxia    时间: 2009-4-25 03:58
能不能从相关性入手
作者: yujun198906    时间: 2009-4-25 07:52
睡了一觉，早上一醒来就想到了学的网络技术，不知道思路对不对，本题最终答案只是单纯的数学题吗？不包含编程吗？
作者: Kind    时间: 2009-4-25 08:59
是否考虑给定任意程序的程序段？？？？？？？？？？？？？
作者: hufeng    时间: 2009-4-25 09:05
37# yujun198906

串行算法并行化.rar

1.06 MB, 下载次数: 97, 下载积分: 体力 -2 点
作者: hufeng    时间: 2009-4-25 09:05
大家看看有用没。。。。。。。。。。。。。。
作者: hufeng    时间: 2009-4-25 09:54
38# Kind . M1 |, V2 |$ b5 n9 {% v6 e
我想是可以的。。。。。。。。。。
作者: Kind    时间: 2009-4-25 10:07
说实话，有点过时！！！！！！！
作者: 0602051104    时间: 2009-4-25 14:15
做A题的哥们有多少啊
作者: x2_nudt    时间: 2009-4-25 17:27
ddddddddddddddddddddddddddd
作者: wumingbo    时间: 2009-4-25 20:26
“分析代码，从总的计算任务中，尽量识别出可独立运算的部分，并估计每部分的计算量”，是对原代码进行分解吗，即给你一段代码，更具模型就能把其中并行的部分区分出来吗
作者: madio    时间: 2009-4-25 22:01
分解代码是专业化的事情，注意这里是要考虑对于算法的处理，就是找出一些算法中易并行的部分！ 45# wumingbo
作者: empty8832    时间: 2009-4-25 23:38
楼上提供的资源确实不错。。
作者: 甩尾儿boy-g    时间: 2009-4-25 23:57
算法的空间与时间的复杂度.rar (287.14 KB, 下载次数: 35)
作者: 甩尾儿boy-g    时间: 2009-4-25 23:59
每个算法建立一个模型，还是综合所有建立一个整体的模型？
作者: Kind    时间: 2009-4-26 01:22
我们对while语句以及其嵌套语句如何拆分？，一点思路都没有了。是不是要对它归类？然后分类讨论。那if语句呢？？
作者: Kind    时间: 2009-4-26 01:27
再说，while语句有类可分么？？？？？？？？对其简单的代数运算可行么？$ E( ?% A5 n9 ?' J* l
那if语句又该如何 理解？？？if语句能分么？？？？他的值可依赖于赋定值！是真就进行，是假就退出。我头都大了。
作者: Kind    时间: 2009-4-26 01:29
以前是为建摸工作熬夜，现在是为建模试题熬夜，总之是为建模熬夜，真的与建模结下了不解之缘。。。。。。。。。哈哈哈哈。。。。。。。
作者: 0602051104    时间: 2009-4-26 03:00
夜已经深了,人也快要沉睡.在这昏迷又似清醒的状态中,我想谈下现在形成的对数模新的看法.# E, i3 F/ j5 S8 j. a( p. u" j7 H
最早时,以为数模体现和发展数学的运用能力，现在看来与其说是建模或计算机能力的考验,不如说是比"查看论文,摘草他人以及杂交前人劳动成果的能力".6 G" N2 g# r6 w! d8 f
      我已经疲倦不堪,我厌恶数学在这里所处的状态,它被侮辱了.数模应是培养个人小组发掘创新能力的快乐天地.然而,我现在很难理直气壮地说:"我真的在这里学了好多知识啊."9 K: z, R4 C/ U3 p& x/ z9 X) Y
      说实话,呆在机房三天时间,对着电脑查看论文,寻找目标.理解别人的论文,摘下有用的句子.这实在是与数学无关,与创新无关,与"当初数学建模的初衷"相违背.难道,这就是中国的数模,"集体大范围抄袭"的数模.
) R8 K3 m5 y" K$ d9 U1 U7 f      我无意批评创办数模和支持数模的人,相反我感谢他们的好心,他们对我们青年一代的热情,是值得我们回报的.但是,想想吧,我们忽略了什么……成绩不是重要的啊,主要是我们要从中找到"真正的需求".
: ]0 H7 h" ]8 V. z2 L8 s* U0 V      一个民族,如果没有一个人愿意去思考;如果每个人只是想应付环境,而不想着去改造它,那么它终究是没有希望的.它无限的潜能,它活动的生机,都将由于我们民族理性的缺乏而暗淡.8 e% C) i, y- F: l
      科学是国家发展的灵魂,数学是一切科学的灵魂:只有一门学科真正用上了数学才能称之为科学.如果数学的建设和培养都不足以使国家,教育委员会重视的话,那么一切一切,这个民族将失去它的灵魂,有肉体而没有灵魂将是可怕的,虽然衣食无忧的活着,但是没有"希望".
7 J, y: E* V& g6 ~9 O  b% {( _7 p      我爱我的国家,我爱它的科学,我爱数模.正是因此我无法忍受对于数学的严重侮辱.好好想想我们青年的未来,好好设计我们的未来,因为"现代的教育将决定着未来的走向".  别让这美好的东西在你们手里变质,让它们放出灿烂的宇宙弧光吧.  g7 M2 W  P+ J# X; ]% B" x
      你们在设计着数模的题,你们在设计我们思想的走向,你们在设计我们国家的蓝图.你们的职业是可骄傲的,"挑战"吧,带我们这些青年(你也可以称为国家的精英)体验真正的成长,带我们穿梭一个个迷团而不是产生更多新的迷惑.- a  S3 \8 m% z
      你们辛苦了, 出题的专家;辛苦了,资助数模的热心集团;辛苦了,广大参赛的高中大学研究生;辛苦了,以任何形式关注数模举办的观众.* D! n& g$ ~: \- H
      让我们为数模喝彩,为共同的事业举杯--敬梦想,敬祖国,敬可亲可爱的国人!
! h% c& F1 L+ r% ?) ^! G# h: }7 ~(我要请求原谅,为了此刻昏迷却依然过于冲动的话语)
作者: wwz    时间: 2009-4-26 04:15
#53 A题肯定是做的崩溃了~
作者: Kind    时间: 2009-4-26 05:54
好东西还是值得大家去肯定的。数学本来就是一门高深的科学，我们可以用它来理解生活，也可以误解生活。我们能在这个领域内走多远就走多远，既然选择，就勇敢面对。刚被蚊子叮醒了，又看到上面的话。其实有时候也怀疑过数模，但他毕竟是到目前为止，数学领域的一个 应用。大家努力。
作者: Kind    时间: 2009-4-26 05:55
我还想问一下，if-else语句是否可并行 ？？？？？？？？？？？？？
作者: madio    时间: 2009-4-26 08:27
我想还是可并行的，比如说求解整数规划的分枝定界算法就是一个易并行算法，它就是可以利用if-else实现的呀。while循环也是可以并行的呀，比如说从1加到100，可以拆成两个while循环再最后把结果相加，这样不就可以让两个核同时做求和循环吗？ 56# Kind
作者: hufeng    时间: 2009-4-26 08:41
有时候感觉现在的数模题也过于的前沿化了一点................
+ P! a5 m8 V7 ^1 S8 I$ w5 z9 K  {7 L毕竟我们还只是本科,像上次08数模A题的数码相机定位,还勉强说得过去,
9 ^7 A/ U2 D6 R2 ?" T* \4 ?, Z* b但这次的并行计算也未必太前沿了.......
9 w0 e0 l( B8 y8 w  M; x个人觉得,数模题应是基础与前沿科学的结合,1 p% l' D- Q( N" j
而这题,时在是找不到这种突破口............
4 P4 \8 T- E4 \1 p衷心希望数模能有好的发展.........人人可做.......
2 g8 {- p9 |4 \' T0 T# m而不仅仅在于查些资料......
作者: Kind    时间: 2009-4-26 09:46
whlie 循环语句可以分成多个子循环来实现并行，但这种方法有点古老，但确实可用。。还有没有新创新的方法要比他更简单易行呢！这是一大卖点。% t9 \5 [- d5 i% M9 S
对于if-else语句，又没有规律可循呢？分枝定界算法确实易并行，能用这种算法的简单程序都能并行。那不用这种算法的呢？这又是一大卖点。确实有点超时代，不过这就是数学建模嘛，可是时间太少了。三天根本不能把这些问题全部彻底解决 。不过，我们尽力吧，还有第二间段呢。哈哈。。。总有人才的……
作者: 刹那.F.精英    时间: 2009-4-26 10:13
我刚刚才注册的+ U0 O6 c9 ^: N- m) _* O. H
   还没有什么矩阵币也~9 E" _. ]3 ]5 p& e: G
买不起
作者: aqua2001    时间: 2009-4-26 10:27
现在的论文里针对这个问题并没有什么非常有效的方法。不要只看别人，自己的想法才是主要的。
作者: sbfj_87    时间: 2009-4-26 12:50
SIMD模型可能有帮助。。。
作者: sbfj_87    时间: 2009-4-26 12:51
39# hufeng
作者: sbfj_87    时间: 2009-4-26 12:51
我怎么下载不了那个串行算法，，并行化的资料哦
作者: lyao    时间: 2009-4-26 13:39
这模型的检验是要用具体的程序咯？那是应该自己写还是去找一段比较好？
作者: madio    时间: 2009-4-26 14:07
本问题必不涉及具体程序的处理，处理的使一些算法结构，写点伪代码就可以了！ 65# lyao
作者: storm    时间: 2009-4-26 14:36
是啊！好难啊！一点头绪都没有！
作者: x2_nudt    时间: 2009-4-26 14:48
都要交论文了，你怎么还没有头绪？？？？？
作者: hufeng    时间: 2009-4-26 15:23
大家加油啊...........
作者: 数学学习者    时间: 2009-4-26 16:30
谢谢哈，至少对于向我们这样完全没有思路的有很大帮助。
作者: moyemuliao    时间: 2009-4-26 16:37
完成了。嘻嘻~~~今晚可以睡觉了。版主啊，做A题的人多吗？还有啊，那个获奖比例是所有还是分题啊？
作者: 挑战建模！！！    时间: 2009-4-26 16:39
做A题的谁有想法了？
作者: 数学学习者    时间: 2009-4-26 16:40
应该是所有的综合建立一个模型吧，每个算法建立一个模型好像不太容易实现。
作者: 数学学习者    时间: 2009-4-26 16:45
就当是了解新的东西，培养新的思维方法的同时多了解一些。
作者: wumingbo    时间: 2009-4-26 16:47
57# madio 我一个人做，3天能做很好吗
作者: aqua2001    时间: 2009-4-26 17:59
算法多种多样，很难讲在这里面有多复杂的问题。所以不要想做得非常彻底。可以考虑先处理较简单的算法，再逐步改进。效果也是，很难知道效率最高的分解方法是什么，所以也需要慢慢来。
作者: Kind    时间: 2009-4-27 02:52
我们的论文也要写完了，使用tex写的，好麻烦，真希望网站能给我们提供一个统一的模板，这样大家就不用再去编程序了。能节省好多时间来解决问题。
作者: Kind    时间: 2009-4-27 03:02
早上就要交卷了，好累，整整在机房呆了两夜三天，早上还有四节专业课，我，一个这么喜欢文字的女孩，不知道怎么就读了数学系，还进了数学建模协会。真的好笑。然后认识一大堆喜欢建模的同志，然后喜欢上了建模，是我选择了建模，还是建模选择了我。也许，我应该走了……无论是谁，请不要挽留……我的心真的承受不住这么大的痛了……但我还爱这篇乐园，依偎在你笔下，我死也无悔……
作者: hufeng    时间: 2009-4-27 03:07
和楼上的，同有同感啊.......
2 ^9 f$ M* O! H5 U$ t* A5 H这次可能是自己的最后一次参加建模比赛了,以后都不会有时间了......% ]: ]9 J! H* H4 P
但我依然关注这片乐地，关注我所喜爱的数模.....
作者: Kind    时间: 2009-4-27 03:20
我能不能再问一下，对于很多个if-else嵌套的语句，我用两个子程序（分别在A、B两个处理器中）来处理初始的数据，这些数据根据子程序的不同尽可能的“按需分配”，然后将子程序在处理过程中得出的数据发送到主程序上……这样A、B实现了串行算法并行化。即A、B进行了一个淘汰法则，对主程序不需要的数据进行了过滤选择。则主程序就不需要尽心选择了，就节省了时间。。。。这种算法是不是偏题了？是不是他不具有可操作性？至少在if-else语句里，不能执行，可是它的确是选择性语句。或则可操作性极小？，不知道大家理解我没有，我的队友不理解我这种想法。我困惑了？？？？
作者: Kind    时间: 2009-4-27 03:33
kind在德语中是小孩子的意思，汉音过来就是“客音特”，也就是用永远也不要长大，我也希望我能在数学中国里永远也不长大，永远留在这块神洁的领域。这夜，静得出奇，但是我喜欢。数学中国，加油。
作者: Kind    时间: 2009-4-27 03:54
我们的论文马上要结束了，但是我没动手写一个字。有点遗憾。不过三天的“争吵”已使我疲惫不堪。我的手指不想动了。晚安，我的宝贝们……英文的摘要就算了，写不好怕大家笑……嘿嘿……小女子喜欢语文，却不喜欢英语，大家！！！！！！！！！！安！！！！！！！！！！
作者: Kind    时间: 2009-4-27 06:40
我们的答卷要交到ceo@madio.cn是吧？？？？？？？？？？？？？
作者: Kind    时间: 2009-4-27 06:52
我知道了》就是懒得查啊！！！！！！！！！！！！
作者: nihao_345    时间: 2009-4-27 07:54
我们要交卷了！
4 S, P, M& W$ h- B9 s4 }/ p! E/ r好累，好爽，又好饿！% t& v& o5 i$ E
痛并快乐！- v9 n! r0 v! |) q+ {4 k
大家一起学习吧！
- }1 [" @% T# Y4 i: `我们的qq1:836777327
5 o( T# y( u  y" ~, y5 l& ^  s         qq2:40092026
( N5 I0 l$ s! w         qq3:2872558351 j, T) t  U1 ~2 q) W
祝大家好运！
作者: zhanfei    时间: 2009-4-27 08:29
要用matlab做出图形模拟吗？2 \/ N5 \6 V5 J) d3 p
编程后求出结果算不算模拟啊？
作者: aqua2001    时间: 2009-4-27 09:35
模拟不一定需要图形结果。
作者: pkucs    时间: 2009-4-27 10:00
太好了,大家都做完了啊
作者: weichuanjiao    时间: 2009-4-27 17:49
Kind，你是西大的啊，天啊，太好了，我也是啊。终于找到校友了，不容易啊，能留个联系方式吗？我的QQ:270209583;TEL:15123337658。我是计算机与信息科学学院的，大一新生哈，请多多指教啊。
作者: pengxiangda    时间: 2009-4-27 22:12
论文何时公布，急切想看到别人的思路！
作者: 龙啸九重天    时间: 2009-5-1 21:00
嘿嘿，没想到这里看到一个同门师姐和师弟~~~我也西大的，计信院的，(*^__^*) 嘻嘻
作者: heihei12    时间: 2009-5-2 02:00
哈哈。我也是西大的呢
作者: snpghnui112    时间: 2009-5-14 16:54
谁能告诉我，成绩什么时候出来啊？？？
作者: chens    时间: 2009-5-14 20:08
没头绪～～～～
作者: hufeng    时间: 2009-5-15 00:36
快了。。。。。。。。。。。
作者: Kind    时间: 2009-5-15 11:41
这么多西大的人。这么多建模的爱好者。
* j+ m1 H# m0 L! I2 v4 a联系方式就免了，我有一点忙嘿。只要你爱好数学建模，又在西大，你一定有机会见到我的。  |+ d! M7 w3 J; X0 F
上面的楼主是不是西大的？后面的江是不是长江？人满帅的。哈哈哈哈哈。成绩20号就出来了吧。前天在上面看到的。大家关注。支持数学中国。
作者: madong    时间: 2009-5-25 14:55
学习中!!!!!!!!!!!
作者: xjl943    时间: 2009-5-29 10:53
怎么不给点数据啊
作者: 紫析    时间: 2009-5-29 17:43
与c语言没太大问题吧~主要是怎么开动思维吧~
作者: hufeng    时间: 2009-6-30 14:42
呵呵,我不是西南大学的.......后面的长江不错!很高兴认识你哟.... 96# Kind



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5