Intel过去几年举办过好几次线程技术大赛
包括和topcoder合作
些竞赛质量都不错
题目难度适中而且具有启发性对多核编程感兴趣C/C
员应该关注下其实参和这样活动置身于竞赛气氛当中无论是否获奖都可以在短时间内大幅度地提高对多线程编程理解这次比赛比较有特色为期长达几个月的久而且每个月都有轮竞赛每月评选轮优胜奖奖品也很诱人是颗4核酷睿2CPU ;-) 本月(2008年1月)
题目是个经典问题“生命游戏”这是英国数学家John Conway发明个有趣游戏不过这个游戏的所以名声大噪还得归功于著名科普作家马丁•伽德纳他在1970年10月号
科学美国人
杂志“数学游戏”专栏介绍了生命游戏不但让大众迷上这个游戏也令多专业数学家产生了研究兴趣甚至产生了个新数学研究领域cellular automata(细胞自动机？)听说这个领域还对模拟类游戏产生了影响不知是否确有其事 大致来说
生命游戏是这样玩在个由正方形小格子组成 2维网格(就像国际象棋棋盘那样)里生活着群细胞每个细胞占据个小格子它 4邻左右(最多)有8个格子如果那些格子里也生活着细胞那么这些细胞就成为“邻居” 细胞对生存环境要求苛刻
太孤独话会死但是食物有限所以太拥挤也会死细胞还需要繁衍生息如果邻居数量合适就可以在空格子里分裂出新细胞数学家们研究话题是怎样制定规则才能让细胞群繁衍发展呈现某种特定模式比如说能够稳定持续地发展下去或者逐渐消亡或者恒定不变或者最有趣是在几个状态的内反复循环要想“生生不息”这些条件即不能太严苛也不能太宽松总的Conway对于生命游戏制定规则如下: 1. 如果
个细胞只有0或1个邻居它将
孤独而死； 2. 如果
个细胞有4到8个邻居它将拥挤而死； 3. 如果
个细胞恰有2或者3个邻居它将继续生存下去； 4. 如果
个空格子恰有3个邻居将“生”出个新细胞； 5. 其他
空格子继续维持原状 这个问题出现在
员面前时候大多数是要求开发个来对这个游戏进行模拟我以前学习数据结构和算法时候曾经接触过但是没有深入研究其实这个问题很有趣算法上可以有些变化但主要是数据结构设计可以有几种区别考虑比如可以从网格角度出发设计个(可能是稀疏)矩阵用0或1表示细胞生死每过代就对矩阵进行次全局扫描决定细胞生死也可以从细胞出发把每个细胞 2维坐标位置记下然后个细胞个细胞地考察没考察个细胞就把它可能影响到其他细胞或者空格纳入视线等到全部细胞考察完毕也就可以次性决定下代格局后面这种算法减少了需要考虑情况数量当网格很大而细胞比较稀疏时就节省了时间 不过这次Intel
竞赛并不想让参赛者在算法上动脑筋而是已经把串行实现了要求参赛者在其基础上改成并行多线程可以从竞赛站点上分别下载Linux和Windows版串行实现其中算法基本上是上述第 2种即从细胞出发算法当中自制了个超级简单链表数据结构然后用 4个链表
live, die, maylive, maydie分别表示新生刚死可能出生和可能死掉细胞然后用TraverseList
遍历链表并对链表中每个元素施加相应操作最后把结果口气写在个5002x5002网格中实际上这个网格有效尺度是5000x5000多出来那两行和两列是为了方便边界条件处理整个算法还是很直白建议有兴趣人直接下载来阅读理解 [Page]我大致研究了
下实际上这个题目还是属于个数据并行算法关键在和把链表访问并行化包括ClearListTraverseListCopyList如果能够充分并行化则可以利用多核CPU多个硬件线程加速执行如果是为了这个目标简单单链表就似乎不是最好数据结构而类似STL中std::vector那样动态
就比较适合可以很有效分段我大致想法如下: 用std::vector取代List作为基本数据结构
设定个合适grain size也就是说个线程处理细胞数量般来说这个数量大小大致以需要消耗10,000条机器指令为好我估计在这个例子中100是个合理数值然后根据现有细胞数量确定线程数N主线程创建N个线程后
join阻塞自己等待那N个线程分别在List区别片段上执行相同操作当所有线程执行完毕的后就可以得到所需结果这里还应该用线程池来避免频繁地创建线程至于算法直接用中提供即可这个题目主要还是考察线程操作 这里
难点还是在那些底层线程API我不太熟悉pthread对Windows线程还是比较熟悉尽管如此让我去写个小线程池然后再把每个片段任务分配给线程来执行再处理同步什么还是有点麻烦直接使用OpenMP或者Intel Threading Building Blocks就会方便很多我倾向于使用后者不过还需要学习
最新评论