八条设计多线程程序的简单规则

更新:
[2010.3.6] Scalability翻译从”可扩展性“改成”可伸缩性“.

前言:最近在看该作者的《The Art of Concurrency》,里面第四章就是上面这篇文章,觉得很实用而且很有共鸣。作者基于在并行编程领域的20多年工作经验总结成下面八条简单的原则,一下子帮我把之前并行编程时的一些认识给理清了,量化了,实在是“居家旅行,并行编程,必备良药”。花了几天时间把它翻译了一下,不知道各位在看了之后是否有些共鸣呢?


作者:Clay Breshears
译者:并行实验室 Parallel Labs

在Intel,并行化技术主要有四个步骤:分析,设计与实现,调试以及性能调优。这些步骤用来对一段串行代码进行并行化。尽管这四个步骤中的第一、三、四步都已经有了很多相关文档,但是关于怎样进行设计与实现的却不多。

并行编程更像是一门艺术,而不是一门科学。这里将会给出八条设计多线程程序的简单规则,你可以把他们一一放进你的多线程程序设计百宝箱中。通过参考这些规则,你能写出高质量、高效率的多线程程序。我努力试着将这些规则按照(半)时间顺序组织起来,但是它们之间并没有硬性的先后顺序。就像“别在泳池边奔跑”和“别在浅水区跳水”一样,两个都是好主意,但是后者也能放在前者的前面,反之亦然。

规则一:找到真正不相关的计算任务
如果你将要执行的运算任务相互之间不独立的话,你是不可能将它们并行化的。我可以很容易的举出一些真实世界中相互独立的任务如何为了达成同一个目的而工作的例子。比如说一个DVD出租店,它先把收到的求租电影的订单分给员工们,员工再从存放电影DVD的地方根据订单找到影片拷贝。当一个员工取出一张古典音乐喜剧的拷贝时,他并不影响另一个寻找最近科幻电影大作的员工,也不影响另一个寻找某热门犯罪连续剧第二季花絮的员工(我假设所有不能被满足的订单在递交给DVD出租店之前就已经被处理过了)。同样的,每个订单的打包和邮递工作也不会影响其他订单的查找、运送和处理工作。

你也可能会遇到某些不能被并行化的而只能串行执行的计算任务,它们大多数是因为循环之间或者计算步骤之间有依赖关系从而导致它们只能按照特定的顺序串行执行。一个很好的例子是驯鹿怀孕的过程。通常驯鹿需要八个月来生小驯鹿,你不可能为了早点生个小驯鹿就让八个驯鹿来一起来生,想一个月就生出一个来。但是,如果圣诞老人希望尽快的扩充雪橇队伍,他可以让八只驯鹿一起生,这样八个月后就能有八只小驯鹿了(注:可以理解为尽管单个任务的执行时间没缩短,但是吞吐量却大了)。

规则二:尽可能地在最高层进行并行化
在对一段串行代码进行并行化时我们有两种方法可以选择,一个是自底向上,另一个是自顶向下。在对我们的代码进行分析的过程中,我们先找到花费了最多执行时间的程序热点(hotspots)。对这些代码段进行并行化是使我们获得最大的性能提升的最好办法。

在自底向上的方法中,你可以考虑先直接对那些程序热点进行并行化。如果这不太可能实现的话,我们可以顺着它的调用栈(call stack)向上查找,看看能不能找到其他的可以并行化的程序热点。假如你的程序热点在一个嵌套循环的最里层,我们可以从内向外的逐一检查每一层循环,看看某一层是否能被并行执行。即使我们能一开始就很顺利的把程序热点并行化了,我们仍然应该去检查一下是否可能在调用栈中更高的某一层上实现并行化。这样做能提高每个线程所执行的任务的粒度。(注:每个线程所执行的任务的粒度可以理解为成功并行化了的部分在整个程序中所占的比例,根据Amdahl定律,并行化的部分越多,程序的整体性能越高)

为了更清楚的描述这条规则,让我们举一个对视频编码程序进行并行化的例子。如果你的程序热点是针对每个像素的计算,你可以先找到对一帧视频中的每个像素进行计算的循环,并考虑对它进行并行化。以此为基础向“上”找,你可能会发现对每一帧进行处理的循环也是可以被并行化的,这意味着每个线程都可以以帧为单位对一组数据进行独立的处理。如果这个视频编码程序同时要对好几个视频进行处理,那么让每个线程单独处理一个视频流将会是最高层的并行化。

在另一种自顶向下的并行化方法中,我们可以先对整个程序以及计算的流程(为了完成计算任务而依序组合起来的各个程序模块)进行分析。如果并行化的机会不是很明显,我们可以挑出那些包含了程序热点的模块并对他们进行分析,如果不行就再分析更小的程序热点模块,直到能找到独立的计算任务为止。

对视频编码程序的例子来说,如果你的程序热点是针对单个像素的计算,采用自顶向下的方法时就可以首先考虑该程序对多个不同的视频流进行编码的情况(每个编码任务都包含了像素计算的任务)。如果你能在这一层成功进行并行化,那么你已经得到了最高层的并行。如果没能成功,那我们可以向“下”找,看看每个视频流的不同帧的计算是否能被并行处理,最后看看每个帧的不同像素的计算是否能被并行处理。

并行任务的粒度可以理解成在进行同步之前所需要完成的计算量。同步之间运行的时间越长,粒度越大。细粒度的并行存在的隐患就是给每个线程分配的任务可能不够多,以至于都不够弥补使用多线程所带来的开销。此时,在计算量不变的情况下使用更多的线程只会让情况变得更加糟糕。粗粒度的并行化拥有相对来说更少的线程开销,并且更可能在线程增多的情况下仍然有很好的可扩展性。尽可能的在最高层对程序热点实现并行化是实现对多线程的粗粒度任务划分的主要方法之一。

规则三:尽早针对众核趋势做好可伸缩性的规划
当我写这本书的时候,四核处理器已经成为了主流。未来处理器的核心数量只会越来越多。所以你应该在你的软件中为这个发展趋势做好规划。可伸缩性(scalability)被用来用来衡量一个程序应对变化的能力,典型的变化有系统资源(例如核心数量,内存大小,总线速度)或数据集大小的增加等。在面对越来越多的可用核心时,你必须写出能灵活高效的利用不同数量的核心的代码。

C. Northcote Parkinson说过,“数据的增长是为了适应处理能力的增加”。这意味着随着计算能力的增长加(核心数量的增加),很有可能我们会有更多的数据需要处理。我们永远会有更多的计算任务需要完成。不管是增加科学模拟中的建模精度,还是处理更清晰的高清视频,又或者搜索许多更大的数据库,如果你拥有了更多的计算资源,总会有人想要处理更多的数据。

用数据分解(data decomposition)的方法来设计和实现并行化能给你提供更多的高可扩展性的解决方案。任务分解(task decomposition)的方法可能会面临程序中可独立运行的函数或者代码段数量有限或者数量固定的问题。等到每一个独立的任务已经在单独的线程和核心上运行的时候,再想通过增加线程的数量来利用空闲的多余核心的方法就提高不了程序的性能了。因为在一个程序中数据的大小比独立的计算任务的数量更有可能增加,所以基于数据分解的设计将更有可能获得很好的可伸缩性。

即使有的程序已经基于任务分解的模式给每个线程分配了不同的计算任务,我们仍然可以在需要处理的数据增加的时候利用更多的线程来完成工作。例如我们需要修建一个杂货店,这项工程由一些不同的任务组成。如果开发商又买了一块相邻的地皮,并且商店要盖的楼层数翻倍了,我们可以雇佣更多的工人去完成这些的任务,比如说更多的油漆工,更多的盖顶工,更多的电工。因此,我们应该注意是否能对增加了的数据进行数据分解,以便利用空闲核心上的可用线程来完成这个工作,哪怕是在我们已经采用了任务分解的方式的程序中。

规则四:尽可能利用已有的线程安全库
如果你的程序热点的计算任务能通过库函数调用来完成,强烈建议你考虑使用同等功能的库函数,而不是调用自己手写的代码。即使是串行程序,“重新造轮子”来完成已经被高度优化的库函数实现了的功能仍不是一个好主意。许多的库,例如Intel Math Kernel Library(Intel MKL)和Intel Integrated Performance Primitives (Intel IPP),提供了能更好的利用多核处理器的并行版本的函数。

比使用并行版本的函数库更重要的一点是:我们需要确保所有的库函数调用都是线程安全的(thread-safe)。如果你已经把你串行代码中的程序热点替换成了一个库函数调用,你仍有可能在调用树(call tree)的更高层上发现能把程序分解成独立的计算任务的代码段。当你有好几个并行的计算任务,并且它们都同时调用了库函数(特别是第三方函数库),那么函数库中引用并更新共享变量的函数可能会造成数据竞争(data race)。记得好好检查你在并行编程中所调用的函数库的文档中关于线程安全性的描述。当你在设计和编写自己的用于并行执行的函数库时,请务必确保函数是可重入(reentrant)的。如果不能确保的话,你应该给共享的资源加上同步机制。

规则五:使用合适的多线程模型
如果并行版的函数库不足以完成程序的并行化,而你又想使用可以自己控制的线程,在隐式的多线程模型能满足你的功能需求的前提下请尽量使用该模型(例如OpenMP或者Intel Thread Building Block)而不是显式的多线程模型(例如Pthread)。显式的多线程模型确实能提供对线程的更精确的控制。但是,如果你仅仅是想把你的计算密集型循环给并行化,或者你不需要显式多线程模型提供的诸多特性,那么我们最好还是能满足需要就好。实现的复杂度越高,犯错误的几率就越大,以后代码的维护难度也会越大。

OpenMP采用的是数据分解的方法,它尤其适合并行化那些需要处理大量数据的循环。尽管这种类型的并行化可能是唯一一种你能引入的并行模式,但是可能还会有其他的要求(例如由你的雇主或者管理层所决定的工程方案)让你不能使用OpenMP。如果是那样的话,我建议你先使用OpenMP来快速开发出并行化后的模型,估算一下可能的性能提升、可扩展性以及大概需要多少时间才能把这些串行代码用显式多线程库给并行化。

规则六:永远不要假设具体的执行顺序
在串行程序中我们可以非常容易地预测某个程序的当前状态结束之后它会变成什么状态。然而,多个线程的执行顺序却是不确定的,它是由操作系统的调度器(scheduler)决定的。这意味着我们不可能准确的预测两个执行状态之间多个线程的执行顺序,甚至连预测哪个线程会在下一步被调度执行也不能。这样的机制主要是为了隐藏程序运行时的延迟,特别是当运行的线程的数量多于核心的数量时。例如,如果一个线程因为要访问不在cache中的地址,或者需要处理一个I/O请求而被阻塞了(blocked),那么操作系统的调度器就会把该线程调度到等待队列里,同时把另一个等待执行的线程调度进来并执行它。

数据竞争(data race)就是由这种调度的不确定性造成的。如果你假设一个线程对共享变量的写操作会在另一个线程对该共享变量的读操作之前完成,你的预测可能会一直正确,有可能有些时候会正确,也有可能从来都不会正确。如果你足够幸运的话,有时候在一个特定平台上每次你运行这个程序时线程的执行顺序都不会改变。但是系统间的每个不同(例如数据在磁盘上存储的位置,内存的速度或者插座中的交流电源)都有可能影响线程的调度。对一段需要特定的线程执行顺序的代码来说,如果仅仅依靠乐观的估计而不采取任何实质性的措施的话,很有可能会受到数据竞争,死锁等问题的困扰。

从性能的角度来讲,最好的情形当然是让所有的线程尽可能没有约束的运行,就像比赛中的赛马或猎犬的一样。除非必要的话,尽可能不要规定一个特定的执行顺序。你需要找到那些确实需要规定执行顺序的地方,并且实现一些必要的同步方法来调整线程间的执行顺序。

拿接力赛跑来说,第一棒的选手会竭尽全力的奔跑。但是为了成功的完成接力赛,第二个,第三个和最后一棒都需要先等到拿到接力棒之后才能开始跑他们的赛段。接力棒的交接就是他们的同步机制,这样就确保了接力过程中的“执行”顺序。

规则七:尽可能使用线程本地存储或者对特定的数据加锁
同步(Synchronization)本身并不属于计算任务,它只是为了确保程序的并行执行能得到正确的结果所产生的额外开销。虽然它产生了额外的开销但是又不可或缺。因此我们还是要尽可能的把同步所产生的开销降低到最低。你可以使用线程私有的存储空间或者独占的内存地址(例如一个用线程ID来进行索引的数组)来达到这个目的。

那些很少需要在线程间共享的临时变量可以被每个线程单独地在本地进行声明或分配。那些存储着每个线程的部分结果(partial result)的变量也应该是线程私有的。但是在把每个线程的部分结果保存到一个共享的变量的时候就需要采取一些适当的同步措施了。如果我们能确保这样的共享更新操作能尽可能少的进行,我们就可以把同步的额外开销降到最低了。如果我们使用显式的线程编程模型的话,我们可以使用那些线程本地存储(Thread Local Storage)的API来保证线程私有变量在多个并行区域的执行过程中,或者在一个并行函数的多次调用的过程中的一致性。

如果线程本地存储不可行,而且你必须用同步的对象(例如锁)来协调对共享资源的访问的话,请确保对数据进行了适当的锁操作。最简单的方法就是对锁和数据对象采取一一对应的分配策略。如果对变量的内存地址的访问都是在同一个临界区进行的话,我们就可以使用一把锁来对多个数据进行保护。

如果你有大量的数据需要保护,例如由一万个数据的数组,我们该怎么办呢?如果我们对整个数组只用一个锁来进行保护的话,很可能会造成严重的锁竞争从而导致性能瓶颈。那么我们是不是可以给每个数组元素创建一个锁呢?然而即使是有32个或者64个线程在同时访问这个数组,这样做看起来也浪费了很多的内存空间来保护那些只有百分之一不到的发生概率的访问冲突。不过有一种折中的解决方案,叫做“取模锁”(modulo lock)。取模锁是用来保护数据集合中的所有的第N个元素,其中N是锁的数量。例如,有两个锁,一个保护所有的奇数个的元素,另一个保护所有的偶数个元素。当需要访问一个被保护的变量时,线程需要先对要访问的地址进行取模操作,然后再去获得对应的取模锁。使用的锁的数量应该是基于线程的数量以及两个线程同时访问相同元素的可能性来决定。

但是,当你决定用锁来对数据进行保护时,请一定不要用多于一个的锁来给一个单独的元素进行加锁。西格尔定律告诉我们“一个人看着一个表能知道现在几点了,但是他要是有两个表那么他就确定不了时间了”。如果两个不同的锁都对同一个变量进行了保护,那么可能出现代码中的某一部分通过第一个锁来进行访问的同时,代码中的另一部分通过第二个锁也进行了访问。正在执行这两个代码段的多个线程就可能发生数据竞争,因为它们都以为它们对这个被保护的变量有独占的访问权限。

规则八:敢于更换更易并行化的算法
当比较串行或者并行程序的性能的时候,运行时间就是衡量的首要标准。程序员会根据算法的时间复杂度来进行选择。时间复杂度和一个程序的性能是息息相关的。它的含义就是,当其他的一切条件都一样时,完成同样功能的时间复杂度为O(NlogN)的算法(例如快速排序)要比O(n^2)的算法(例如选择排序)要快。

在并行程序中,拥有更好的时间复杂度的算法也会更快一些。然而,有些时候时间复杂度更好的算法却不是很容易被并行化。如果算法的热点不太容易被并行化的话(而且在调用栈的更高层中你又找不到能很容易被并行化的热点),那么你可以尝试换一个稍微慢一点但是却更容易被并行化的算法。当然,还有可能一些其他的改动措施也能让你比较轻松的把某一段代码给并行化了。

这里我们可以给出一个线性代数中两个矩阵相乘的例子。Strassen的算法拥有最好的时间复杂度:O(n^2.81)。这当然比传统的三重循环的O(n^3)的算法要好。Strassen的算法把每个分成四部分,然后进行七次递归调用来对n/2 x n/2的子矩阵进行乘运算。如果想把这七次递归调用并行化的话,我们可以在每次的递归调用的时候创建一个新线程来进行运算,直到子矩阵到达一个预设的大小为止。这样的话线程的数量就会指数级的成倍增长。随着子矩阵越来越小,给新创建的线程分配的计算任务就会越来越少。还有另一种方法,就是先创建一个有七个线程的线程池。七次子矩阵相乘的运算任务可以分别分配给这七个线程以完成并行化。这样的话线程池就会跟串行版本的程序一样递归调用Strassen算法来对子矩阵进行乘运算。然而,这种方法的缺点就在于对一个拥有大于八个核的系统来说,永远只有七个核在工作,其他的资源都被浪费了。

另一个更容易被并行化的矩阵乘法就是三重循环的算法了。我们可以有很多方法来对矩阵进行数据分解(按行分解,按列分解或者按块分解)然后再把它们分配给不同的线程。通过用OpenMP在某一层循环中加上编译指示,或者用显式线程模型实现矩阵分割,我们很容易的就能完成并行化。只需要更少的代码改动就可以对这个简单的串行算法完成并行化,并且代码的整体结构改动也会比Strassen算法要少很多。

总结
我们已经列出了八条简单的规则,在把串行程序并行化的过程中你应该时刻记住它们。通过遵循这些规则以及一些实际的编程规则,你应该可以更容易的创造更健壮的并行化解决方案,同时能包含更少的并行化时的问题,以及在更短的时间里得到最好的性能。

原文链接:8 Simple Rules for Designing Threaded Applications

瑞典Ericsson总部Master Thesis面试回忆录

前言:去年4月份我申请过一些6月份开始的毕业设计和暑假实习,最终拿到了Ericsson的master thesis offer和另一个哥德堡小公司的summer intern,Volvo在我拿到summer intern后也给了interview。现在应该已经有不少一年级的同学要开始找暑假实习了,我觉得你们可以考虑申请6月份开始的毕设(等毕设结束后再回学校把剩下的课程修完)。下面是我去位于Kista的Ericsson总部面试的经历,希望对大家有用。Summer Intern总体上来讲难度比thesis大很多,因为很多瑞典人也要竞争这种职位,而且那些提供summer intern的小公司也不太喜欢招foreigner。

2009 May 5th:

晚上刚从超市回来就发现Gtalk弹出新邮件的消息,第一眼就看见标题中Interview的字眼,立刻欣喜若狂,急急忙忙打开仔细一看,竟然是我最早申请的职位的Interview!我是April 24th投的这个职位(Master Thesis),另外还投了若干Summer Job(其中就包括我当天刚刚投完的Nema Labs的Summer job,后面会详叙),Volvo的Master Thesis以及其他几个Ericsson的Thesis Position。

因为这个是我投出去的第一份申请,当时完全没有任何经验,而且Cover Letter和CV都不是最好,现在回想之所以能够拿到这个Interview,主要因为以下几点原因:

1. 专业对口,GPA够。职位是做Sensor Network的,我的专业是Networks and Distributed Systems,正好对口,而且我在刚刚结束的课程Project中正好做过Sensor Network的一个项目,可谓牛头对上了马嘴,不亦乐乎。另外GPA也是Ericsson非常看重的,很多职位写明必须4.0(满分5.0)以上,个人觉得4.3以上比较保险。

2. 简历虽然有些小纰漏,但是因为当时也有针对职位的要求进行修改,所以还是能给人第一眼的好印象的。

3. Cover Letter写得也还凑合。除了常规介绍外还重点说了说自己对那个Thesis的看法,扯了扯自己的本科毕设。

发信人是后来面试我的Dr. V.,我一查竟然是UCxx的出身,心想又是UCxx啊!不禁由衷的仰慕,立刻对之后的Interview十分的向往。事后证明Dr. V.人真的非常的nice,虽然有些许龅牙,但是至少英语听起来比较舒服啊!

之后的信件往来就是确定面试时间之类,定下下下周五之后立刻跟身在Kista的yoan师兄联系商量借住事宜(在此对师兄的热情相助表示深深感谢!是你让我在Kista感受到家的温暖啊!还顺带连累你熬了个通宵 囧),然后就是买往返的火车票之类。一切定好后剩下的两个礼拜就开始拼命准备,囫囵吞枣扫了些论文,再跟着看了些英文面试的资料,甚至还去了Career Office做了一次咨询。

这其中发生了一件比较逗的事情。因为哥德堡到斯德的来回火车票加起来600多SEK,我心想这一趟下去怎么的也得1000块了,要不问问看他们能不能给报销?再加上外国公司以往报销路费的事听了不少,我就借着发信问问题的机会顺带来了句:“I am wondering whether you will undertake my travel fee for this interview?” 猜猜人家怎么回的?

“it’s not possible to 报销路费, so我们只能电话Interview了”,我心想,大哥我这菜鸟要电话面试不就相当于直接管你要据信么,再说我票都定了大不了当去旅游好了,于是连忙给他发信解释说没关系云云。

2009 May 14th

早上6点的火车去Stockholm,4点半起的,等5点的第一班tram去Central Station。顺利等到4路电车,心想时间肯定来得及,耽误不了。但是不幸恰恰在心情放松麻痹大意的情况下发生了。我在离火车站还有两站路的时候突发奇想拿出口语书开始模拟英语面试,自己边模拟面试官边想着怎么回答,简直就是左右互搏,天人合一,不亦乐乎,十分忘我。练了5,6分钟后我发现不对了:怎么窗外还能看见火车啊?我仔细一看,我靠!还真是Central Station的火车,其中就有我要坐的x2000!我心中大叫不好,刚刚停的那站就是火车站,我给错过了!!我赶紧收拾东西站在门口准备在下站下车赶紧再坐回去,结果老天真给我开了个大玩笑:过了上一站之后Tram就进入郊区了,开了至少5分钟才到下一站!那5分钟简直就是我人生最漫长的一段时间之一,脑子100%运转,不停看表计算时间,同时储备体力随时准备狂奔。

5分钟后终于到达下一站了,赶紧下车,到对面站台看反方向的车几点到:5分钟以后!这意味着我到火车站后离发车只剩10分钟不到!!!而且我还从来没去过火车站都不知道火车在哪!天无绝人之路,我发现旁边竟然还有一个车站!赶紧对了下时间,Tram7马上就到,又多出了5分钟!老天保佑,我心急如焚的等着不紧不慢的7路小电车,来了!上车!走!到!门开的一霎那,我真是卯足了劲往站台冲啊!事后回想我大概只用了1分钟不到就找到了X2000的站台。这还多亏瑞典的火车站不像国内的那么大,还要进候车厅再排队检票上下楼梯什么的,站台离车站正门也就2-3分钟的路,而且上车后再检票。我悬着的心终于放下来了,事后回想就算当天没赶上我也可以再买下一班的,大不了先上车后补票,还好是我之前订的就是周四走周五面试。虽然我这不叫大难不死,但也算是必有后福啊!

顺利到达Stockholm。斯京的火车站和地铁站是连在一起的,下火车后直接就去地铁售票处买了张24h的通票(100SEK),直奔Kista。话说这个Kista号称瑞典最大的科技园区,里面不仅有Ericsson全球总部,华为瑞典分舵等众多IT公司,KTH也有一个分校区在那边。出了Kista地铁站直接就是一个大型Shopping Mall,在把正补觉的师兄吵醒之后顺利放下行李。中午吃了师兄做的红烧肉拌面,话说那个红烧肉确实很够味,真是赞!

下午就出去Kista园区去寻我明天面试的地点去了。来了Kista我最大的感受就是,整个Kista到处都是Ericsson的人。不管是在Shopping Mall里的Restaurant还是在工业园区的大街上,到处都是挂着蓝色Ericsson牌子的人,简直就是Ericsson大山寨。后来听到一个说法,Ericsson这样的国民企业其实更应该被看做一个Community,在Kista的shopping mall里面甚至有专门的Ericsson员工价,由此可见一般。顺便说一句,上次回国刚下飞机在机场大巴上,坐我旁边的竟然是个瑞典小哥,仔细一聊竟然也是学CS的,从Stockholm来中国找他中国女朋友,于是我就问“你是不是给Ericsson工作”,结果竟然猜对了。由此可见爱立信有多庞大。

事实也确实如此。一开始我找到的最显眼的是一栋白色的大型Ericsson办公楼,整个楼占了一个广场的大小,气势直逼瑞典皇宫了(当然更现代点),真不愧是世界级大公司的全球总部啊。于是我就去reception问我的面试官是不是在这栋楼办公,结果人家告诉我:“不好意思,你找的人在对面那栋楼办公,出门后直走就到了”。等我出去仔细一看,原来Ericsson Research是另一栋大红楼。我猜可能那栋大白楼里面应该都是Ericsson负责工业产品的部门吧。踩点完毕后就回家继续做准备去了。Tips:对面试要提前踩点,特别是去不熟悉的地方更要多做准备,因为瑞典人很忌讳迟到(瑞典交通发达,地铁非常准时,也没什么堵车,所以没有迟到的理由)。

虽然最后我拿到了这个Offer,但是说实话在面试之前我还是非常紧张的。这可是我第一次英文面试,两个面试官都是顶尖大学的PHD,还顶着Ericsson总部的光环。我做的主要准备如下:

1)根据Position Description看了几篇该领域的综述型Paper,以到达快速入门的目的;

2)仔细研究该Position的Requirement,结合自己的CV自己进行了若干次模拟面试

3)准备了自己本科毕设的资料(一页A4插图,直观明了)和,因为这个跟该Thesis有点相关

4)给面试专门准备了一份CV,突出了自己项目经验跟该position的相关性

面试的流程大致如下:

跟两份面试官打过招呼后直接把CV和Transcript递上(省了人家自己打印的功夫,而且给你第一印象就是你准备的很充分。“我把简历都给你带过来了,上面的都是你们需要的”)。Dr.V.人非常好的先给我介绍了一下该Thesis的大致背景,很好的帮助我消除了紧张情绪并帮助我快速进入状态。在了解到项目的大致框架后我适时的接过话题(适时把握话题的主动性,不是被人牵着鼻子走。“我对这个很熟,请听听我的想法”),抛出了我对这个项目的具体实现的想法(虽然有些当时我的想法有些许错误,但是很好的表现出自己对这个项目的兴趣,就像是说:“你看,我自己脑子里已经有一个实现了,我很有可能能把这个项目完成的很好”)。

再聊了一些项目的话题后面试官就开始问我的简历上的项目经验了。我就一个一个跟他们解释(“我做过的东西跟这个Thesis都很相关,我很有竞争力”),其中有几个他们比较熟悉的项目他们就会问你一些技术问题或者算法问题。不过只要自己对项目的背景知识和本身的实现比较熟悉基本没什么问题,而且就算真的不会直接说不会也没关系。我其中就有2个问题直接说了不会,很可能他们因为看重我其他的背景和我的学习能力所以没影响我拿offer。

我感觉我整个面试过程中最出彩的地方在介绍我的本科毕设部分。回想当年在白混了3年之后,心想最后一个毕设怎么的也得拿个A做出点像样的东西来,要不大学白过了,于是狠命搞了半年终于如愿以偿。正好毕设跟这个Thesis很相关,当我拿出我做的prototype的照片并向他们介绍它的功能的时候,我分明的感觉到两位Ericsson Researcher都被我打动了(“给我Offer吧!本科毕设我都拿A了,你们这个Thesis我肯定不会让你们失望的!”)。

最后Dr. V.非常Nice的送我下楼,我在电梯里又跟他聊起不能报销差旅费的事情,最后我对他说了我生平最有打动人的效果的一句英语:“I just want to let you know my serious and positive attitude for this position.”结果Dr.V.非常配合的笑着对我说:“Yes!You have!”

The End:May 19th下午正准备跟妞妞mixi,突然接到一个010开头的电话,我还奇怪难道是北京打来的?后来才知道在瑞典Stockholm的区号也是010。也许大家都猜到了,其实就是另一位面试官打来的Offer电话。

P.S. 虽然因为种种原因没去Ericsson,但是我仍然深深的被Ericsson HQ的魅力所吸引,它向我展现了一个世界电信巨头的风采。而Stockholm,它的美丽更是让我留恋。希望下一次妞妞能跟我再一次同游斯德。

P.S.S. 猜猜Kista最大的中国人群体里在哪?不错,就是华为!华为真是牛逼,我问过好几个瑞典人了,华为真的是一个爱立信强有力对手的存在,直接把分舵开到Ericsson老家,有点新东方把分舵开始ETS总部的意思。在此祝华为越来越牛逼!早日出台Kista华为员工价!

Pthreads并行编程之spin lock与mutex性能对比分析

POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段,其中最典型的应用就是用Pthreads提供的锁机制(lock)来对多个线程之间共 享的临界区(Critical Section)进行保护(另一种常用的同步机制是barrier)。

Pthreads提供了多种锁机制:
(1) Mutex(互斥量):pthread_mutex_***
(2) Spin lock(自旋锁):pthread_spin_***
(3) Condition Variable(条件变量):pthread_con_***
(4) Read/Write lock(读写锁):pthread_rwlock_***

Pthreads提供的Mutex锁操作相关的API主要有:
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的与Spin Lock锁操作相关的API主要有:
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

从实现原理上来讲,Mutex属于sleep-waiting类型的锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。假设线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁,而此时这个锁正被线程B所持有,那么线程A就会被阻塞(blocking),Core0 会在此时进行上下文切换(Context Switch)将线程A置于等待队列中,此时Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。

如果大家去查阅Linux glibc中对pthreads API的实现NPTL(Native POSIX Thread Library) 的源码的话(使用”getconf GNU_LIBPTHREAD_VERSION”命令可以得到我们系统中NPTL的版本号),就会发现pthread_mutex_lock()操作如果没有锁成功的话就会调用system_wait()的系统调用(现在NPTL的实现采用了用户空间的futex,不需要频繁进行系统调用,性能已经大有改善),并将当前线程加入该mutex的等待队列里。而spin lock则可以理解为在一个while(1)循环中用内嵌的汇编代码实现的锁操作(印象中看过一篇论文介绍说在linux内核中spin lock操作只需要两条CPU指令,解锁操作只用一条指令就可以完成)。有兴趣的朋友可以参考另一个名为sanos的微内核中pthreds API的实现:mutex.c spinlock.c,尽管与NPTL中的代码实现不尽相同,但是因为它的实现非常简单易懂,对我们理解spin lock和mutex的特性还是很有帮助的。

那么在实际编程中mutex和spin lcok哪个的性能更好呢?我们知道spin lock在Linux内核中有非常广泛的利用,那么这是不是说明spin lock的性能更好呢?下面让我们来用实际的代码测试一下(请确保你的系统中已经安装了最近的g++)。

// Name: spinlockvsmutex1.cc
// Source: http://www.alexonlinux.com/pthread-mutex-vs-pthread-spinlock
// Compiler(spin lock version): g++ -o spin_version -DUSE_SPINLOCK spinlockvsmutex1.cc -lpthread
// Compiler(mutex version): g++ -o mutex_version spinlockvsmutex1.cc -lpthread
#include <stdio.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <errno.h>
#include <sys/time.h>
#include <list>
#include <pthread.h>

#define LOOPS 50000000

using namespace std;

list<int> the_list;

#ifdef USE_SPINLOCK
pthread_spinlock_t spinlock;
#else
pthread_mutex_t mutex;
#endif

//Get the thread id
pid_t gettid() { return syscall( __NR_gettid ); }

void *consumer(void *ptr)
{
    int i;

    printf("Consumer TID %lun", (unsigned long)gettid());

    while (1)
    {
#ifdef USE_SPINLOCK
        pthread_spin_lock(&spinlock);
#else
        pthread_mutex_lock(&mutex);
#endif

        if (the_list.empty())
        {
#ifdef USE_SPINLOCK
            pthread_spin_unlock(&spinlock);
#else
            pthread_mutex_unlock(&mutex);
#endif
            break;
        }

        i = the_list.front();
        the_list.pop_front();

#ifdef USE_SPINLOCK
        pthread_spin_unlock(&spinlock);
#else
        pthread_mutex_unlock(&mutex);
#endif
    }

    return NULL;
}

int main()
{
    int i;
    pthread_t thr1, thr2;
    struct timeval tv1, tv2;

#ifdef USE_SPINLOCK
    pthread_spin_init(&spinlock, 0);
#else
    pthread_mutex_init(&mutex, NULL);
#endif

    // Creating the list content...
    for (i = 0; i < LOOPS; i++)
        the_list.push_back(i);

    // Measuring time before starting the threads...
    gettimeofday(&tv1, NULL);

    pthread_create(&thr1, NULL, consumer, NULL);
    pthread_create(&thr2, NULL, consumer, NULL);

    pthread_join(thr1, NULL);
    pthread_join(thr2, NULL);

    // Measuring time after threads finished...
    gettimeofday(&tv2, NULL);

    if (tv1.tv_usec > tv2.tv_usec)
    {
        tv2.tv_sec--;
        tv2.tv_usec += 1000000;
    }

    printf("Result - %ld.%ldn", tv2.tv_sec - tv1.tv_sec,
        tv2.tv_usec - tv1.tv_usec);

#ifdef USE_SPINLOCK
    pthread_spin_destroy(&spinlock);
#else
    pthread_mutex_destroy(&mutex);
#endif

    return 0;
}

该程序运行过程如下:主线程先初始化一个list结构,并根据LOOPS的值将对应数量的entry插入该list,之后创建两个新线程,它们都执行consumer()这个任务。两个被创建的新线程同时对这个list进行pop操作。主线程会计算从创建两个新线程到两个新线程结束之间所用的时间,输出为下文中的”Result “。

测试机器参数:
Ubuntu 9.04 X86_64
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz
4.0 GB Memory

从下面是测试结果:

gchen@gchen-desktop:~/Workspace/mutex$ g++ -o spin_version -DUSE_SPINLOCK spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ g++ -o mutex_version spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ time ./spin_version
Consumer TID 5520
Consumer TID 5521
Result - 5.888750

real    0m10.918s
user    0m15.601s
sys    0m0.804s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex_version
Consumer TID 5691
Consumer TID 5692
Result - 9.116376

real    0m14.031s
user    0m12.245s
sys    0m4.368s

可以看见spin lock的版本在该程序中表现出来的性能更好。另外值得注意的是sys时间,mutex版本花费了更多的系统调用时间,这就是因为mutex会在锁冲突时调用system wait造成的。

但是,是不是说spin lock就一定更好了呢?让我们再来看一个锁冲突程度非常剧烈的实例程序:

//Name: svm2.c
//Source: http://www.solarisinternals.com/wiki/index.php/DTrace_Topics_Locks
//Compile(spin lock version): gcc -o spin -DUSE_SPINLOCK svm2.c -lpthread
//Compile(mutex version): gcc -o mutex svm2.c -lpthread
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/syscall.h>

#define        THREAD_NUM     2

pthread_t g_thread[THREAD_NUM];
#ifdef USE_SPINLOCK
pthread_spinlock_t g_spin;
#else
pthread_mutex_t g_mutex;
#endif
__uint64_t g_count;

pid_t gettid()
{
    return syscall(SYS_gettid);
}

void *run_amuck(void *arg)
{
       int i, j;

       printf("Thread %lu started.n", (unsigned long)gettid());

       for (i = 0; i < 10000; i++) {
#ifdef USE_SPINLOCK
           pthread_spin_lock(&g_spin);
#else
               pthread_mutex_lock(&g_mutex);
#endif
               for (j = 0; j < 100000; j++) {
                       if (g_count++ == 123456789)
                               printf("Thread %lu wins!n", (unsigned long)gettid());
               }
#ifdef USE_SPINLOCK
           pthread_spin_unlock(&g_spin);
#else
               pthread_mutex_unlock(&g_mutex);
#endif
       }
       
       printf("Thread %lu finished!n", (unsigned long)gettid());

       return (NULL);
}

int main(int argc, char *argv[])
{
       int i, threads = THREAD_NUM;

       printf("Creating %d threads...n", threads);
#ifdef USE_SPINLOCK
       pthread_spin_init(&g_spin, 0);
#else
       pthread_mutex_init(&g_mutex, NULL);
#endif
       for (i = 0; i < threads; i++)
               pthread_create(&g_thread[i], NULL, run_amuck, (void *) i);

       for (i = 0; i < threads; i++)
               pthread_join(g_thread[i], NULL);

       printf("Done.n");

       return (0);
}

这个程序的特征就是临界区非常大,这样两个线程的锁竞争会非常的剧烈。当然这个是一个极端情况,实际应用程序中临界区不会如此大,锁竞争也不会如此激烈。测试结果显示mutex版本性能更好:

gchen@gchen-desktop:~/Workspace/mutex$ time ./spin
Creating 2 threads...
Thread 31796 started.
Thread 31797 started.
Thread 31797 wins!
Thread 31797 finished!
Thread 31796 finished!
Done.

real    0m5.748s
user    0m10.257s
sys    0m0.004s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex
Creating 2 threads...
Thread 31801 started.
Thread 31802 started.
Thread 31802 wins!
Thread 31802 finished!
Thread 31801 finished!
Done.

real    0m4.823s
user    0m4.772s
sys    0m0.032s

另外一个值得注意的细节是spin lock耗费了更多的user time。这就是因为两个线程分别运行在两个核上,大部分时间只有一个线程能拿到锁,所以另一个线程就一直在它运行的core上进行忙等待,CPU占用率一直是100%;而mutex则不同,当对锁的请求失败后上下文切换就会发生,这样就能空出一个核来进行别的运算任务了。(其实这种上下文切换对已经拿着锁的那个线程性能也是有影响的,因为当该线程释放该锁时它需要通知操作系统去唤醒那些被阻塞的线程,这也是额外的开销)

总结
(1)Mutex适合对锁操作非常频繁的场景,并且具有更好的适应性。尽管相比spin lock它会花费更多的开销(主要是上下文切换),但是它能适合实际开发中复杂的应用场景,在保证一定性能的前提下提供更大的灵活度。

(2)spin lock的lock/unlock性能更好(花费更少的cpu指令),但是它只适应用于临界区运行时间很短的场景。而在实际软件开发中,除非程序员对自己的程序的锁操作行为非常的了解,否则使用spin lock不是一个好主意(通常一个多线程程序中对锁的操作有数以万次,如果失败的锁操作(contended lock requests)过多的话就会浪费很多的时间进行空等待)。

(3)更保险的方法或许是先(保守的)使用 Mutex,然后如果对性能还有进一步的需求,可以尝试使用spin lock进行调优。毕竟我们的程序不像Linux kernel那样对性能需求那么高(Linux Kernel最常用的锁操作是spin lock和rw lock)。

2010年3月3日补记:这个观点在Oracle的文档中得到了支持:

During configuration, Berkeley DB selects a mutex implementation for the architecture. Berkeley DB normally prefers blocking-mutex implementations over non-blocking ones. For example, Berkeley DB will select POSIX pthread mutex interfaces rather than assembly-code test-and-set spin mutexes because pthread mutexes are usually more efficient and less likely to waste CPU cycles spinning without getting any work accomplished.

p.s.调用syscall(SYS_gettid)和syscall( __NR_gettid )都可以得到当前线程的id:)

转载请注明来自: www.parallellabs.com

How to do performance analysis on your parallelized program efficiently?

Be a scientist: Gather data. Analyze it. Especially when it comes to parallelism and scalability, there’s just no substitute for the advice to measure, measure, measure, and understand what the results mean. Putting together test harnesses and generating and analyzing numbers is work, but the work will reward you with a priceless understanding of how your code actually runs, especially on parallel hardware—an understanding you will never gain from just reading the code or in any other way. And then, at the end, you will ship high-quality parallel code not because you think it’s fast enough, but because you know under what circumstances it is and isn’t (there will always be an “isn’t”), and why.

Herb Sutter

doubanclaim5959b1bcd330f270

09年感悟

上半年顺风顺水,有付出也有收获,良好的状态持续到暑假实习结束。下半年压力陡增,主要包括就业压力和毕设压力。一个是因为国内就业竞争的激烈,另一个是因为十分具有挑战性的毕设课题。

压力。有压力是好事,在恰当的时候它能转换为我的动力,督促我的行为,间接促进我的进步。但是对待压力也要心态平和,不要过于焦虑、消沉,否则会陷入非常被动的局面。看过一句话,压力大就是因为自信心不足。自信心是建立在刻苦的努力之上的。所以最好的状态还是Take it easy,找准最需要下功夫的地方,多勤奋一点,多努力一点,付出的比别人多自然就有丰厚的回报,而且随着一点一滴的积累,自信心自然也就来了。

定位。首先是找到并持续的激发自己的兴趣点,从事自己真正发自内心喜欢并且觉得有意义的事情,这往往是成功的第一步。不要被所谓的“热潮”牵着鼻子走,分散了自己的注意力不说,这些不是自己最感兴趣的事情往往也不太适合自己。最好的学习和工作状态是每天早晨睁开眼就很兴奋很期待今天要做的事情,不管是它能给他人带来很积极的影响,或是能提升自己的专业技能,都能给自己带来满足感、成就感。最怕的就是对事情只有三分钟热情,当几天过去热情不在,或是碰到困难后就放弃,这样往往最后就是竹篮打水一场空。其次就是对症下药,先找自己最薄弱的环节并积极去弥补它。不要左一下右一下,结果等到面对问题的时候那些最需要的技能还没准备好那就完了。这里引出了另一个话题,专注。

专注。提高学习效率最有效的办法就是专注。首先从生活习惯上改善,每天划出几大块完整的学习时间段有助于保持专注。把学习的精力集中在能提升自己核心竞争力的技能上,而不是“花拳绣腿”,看上去新鲜实际上没啥用处。其次,注意任务切换(Context Switch)是要花费时间和精力的。这体现在学习的过程中,例如你学着学着突然想上下网,结果这一上就是十几二十分钟,等你再切回学习这个进程,你得先花十几分钟找回刚刚学习的感觉,才能继续开始,这样宝贵的三十分钟就没了。解决办法就是尽量减少Context Switch的次数。

计划。短期来看,给事情安排好优先级,给每天的工作都制定好计划;长期来看,给职业生涯做好规划。这样能有效的减少学习时的无所事事的(idle)时间(参考暗时间一文),有效的提升productivity。以前我不相信我可以同时做好两三件大事,但是2010年我想挑战一下自己,从每天的时间安排做起,争取高效率快节奏的同时把两到三件事情给同时做好,因为我导师就是这么干的。我问过我导师你这么忙胆识还能把事情安排的井井有条(又是搞研究开会又是开公司)是不是因为你已经成功的把自己并行化了,他笑说他希望他有One million cores,这样他就能把所有的事情都处理的来。当然了,其实我发现一个重要原因是因为他有严格的时间管理方法,以小时为单位来详细安排自己每天的行程。

思考。如果每天只是忙忙碌碌但是不进行足够深入的思考并总结自己得到的经验教训,所能得到的进步就会不够多。每天起床吃饭学习然后睡觉,但是不思考,就会停滞在一个思维水平上,往往不能得到大突破。刘未鹏的博客有很多关于“思考”的好文,今年我的目标就是多思考,多总结,从而多进步。

宠辱不惊。心智的成熟体现在“不以物喜,不以己悲”,抗压能力,调整能力等等上。我现在这个阶段,开始从校园走向社会,各方面的压力会迎面而来。这个时候更需要自己有良好的心态,积极的调整自己,善于化解压力,善于自我激励,时刻把握住自己的目标,不迷失自己的方向。

眼光。眼光放长远些,明年的目标只是第一步,五年乃至十年的目标才是更值得关注的。当然,第一步的起点如果够高会很有帮助。

09年大事记:

09 Jan – 09 Mar

TDA297 Distributed Systems II, EDA281 Parallel Computer Organization and Design

09 Mar – 09 May

TIN092 Algorithm, EDA203 Unix Internal, Internship Applications & Interviews

09 Jun – 09 Jul

Summer Intern at Nema Labs

09 Aug

Summer vacation in China

09 Sep – 09 Oct

TDA381 Concurrent Programming (pending), DAT145 Advanced topic in NDS

09 Oct – 09 Dec

DAT105 Computer Architecture, Master Thesis

10年计划:

09 Jan – 09 Mar

TDA231 – Algorithms for machine learning and inference

09 Jan – 09 Sep

Master Thesis

09 Jun – 09 Aug

Summer Internship

09 Fall

To be continued.

Proposal for the “Search and sort” competition of Findwise

In this April I took part in a competition hold by Findwise and Mriday which is about search technology.

Search and Sort | Findwise

Current, Search and Sort | Findwise April 25th, 2009

We are constantly acquiring innovative ideas and solutions in the field of search technology. Therefore we have created the following contest to discover people who are interested in joining Findwise and build next generation’s search technology.

Project overview

The name of this contest is called Search and Sort. We can start by looking at an example which everybody is familiar with, Google. The Google search engine is the most used search engine on the Web. The search results generated from it includes webpages, PDF, Word documents, Excel spreadsheets, Flash, videos etc. For any query, up to the first 1000 results can be shown with a maximum of 100 displayed per page.

Despite all this power, it is still sometimes time consuming to find the exact piece of information you are looking for. This is because although the different results are ranked, they are not well organized. For the average user, wouldn’t it be neat if different types of search results are categorized and displayed in different
groups?

Submission

Your submission for this contest should contain two parts

Think of a search engine based on the concept of Search and Sort. Come up with a user interface design including two pages. One welcome page with the search box (and whatever else you think is suitable), and one page with the different types of results categorized, sorted, and presented in a userfriendly fashion. There is no strict requirements on exactly how the results will be categorized. It is entirely up to you to decide the types of categories. In fact, this will be a key deciding factor when your contest submission is being reviewed.

The second part of the contest is to discuss the framework behind your graphical user interface. What programming language and platform do you suggest for building the system? How would you extract information from different types of results and use that information to categorize them? Describe the plan to develop and implement it. The key for this part is to show a good understanding of the basics of a search engine, and a passion to innovate new ideas.

Searching has become the standard way for Internet users to find information. This contest gives you the chance to take Searching to the next level. If you are interested in search technology and would like to join the leading vendor independent company within this segment in Sweden, then send us your ideas. We will carefully review your submission and provide feedback. Your submission should be in PDF or DOC format.

The deadline for submission is 2009-04-30

Reward

The top 5 submissions will be invited to Findwise and receive a learning session about the company and the future of search technology. The most outstanding submission will receive a monetary reward of 10 000 SEK. Job offers will be presented to qualified individuals if requirements are met.

I spent a whole Sunday to write down a proposal for this topic. That’s the first time for me to write down something on “search technology” which is a very interesting and hot area nowdays. Even though this paper looks a lit bit naive now, I still like it since I enjoy the feeling of writing down something interesting very much.

You can find and download my proposal from the link below:

Search and sort.pdf

在瑞典打甲流疫苗

如果在哥德堡想打甲流H1N1疫苗的话可以参考这里

在页面左侧栏列出了哥德堡不同的地区的Vårdcentraler,离Chalmers最近的Vårdcentraler是属于Centrum地区。我去的是Vårdcentralen Gibraltargatan,就在图书馆旁边。打开Vårdcentralen Gibraltargatan的页面后有专门的接种时间等信息:

Våra vaccinationstider

För information om influensan och vaccineringen

一般他们都是8点开门,但是疫苗现在还是比较抢手,昨天11点到的时候已经没有了,所以今天我是早上8点到的,排到了24号,等了半个多小时轮到了我。等待时填了个人信息表,然后进去打针,打完后医生会给你写好一个小卡片让你留底。但是个人信息表是瑞典语的,以下是粗略翻译(仅供参考):

underlag för pandemivaccination (pandemrix)

för patienten

inför vaccinationen mot den pandemiska influensan ber vi dig svara på följande frågor

1. har du tidigare fatt nagon allvarlig reaktion (som yrsel, svimning, andnod eller utslag)

ja/nej/vet ej

2. ar du allergisk mot agg

3. medicinerar du med nagon blodfortunnande medicin, t.ex. waran eller fragmin? (galler ej trombyl)

4. har du nagon sjukdom eller medicin som påverkar ditt immunforsvar

5. har du nyligen (inom 1 manad) fatt nagot annat vaccin

6. tillhor du nagon medicinsk riskgrupp for den pandemiska flu

———————————

basis for pandemic vaccination (Pandemrix)
the patient

for vaccination against pandemic influenza, please answer the following questions
1. have you ever had any severe reaction (such as dizziness, fainting, shortness of breath or a rash)
yes/no/do not know
2nd Are you allergic to eggs
3rd medication you with any blood-thinning medicine, such as warfarin or Fragmin? (Not Trombyl)
4th you have an illness or medication that affects your immune system
5th have you recently (within 1 month) received any other vaccine
6th you belong to any medical risk groups for pandemic flu

An interesting algorithm problem: the longest plateau

Recently I met an interesting algorithm problem:

Problem:

Given an array, try to develop an efficient algorithm which can compute the length of the longest plateau. A plateau is a consecutive segment of an array with equal contents. For example, if x[] = {1, 2, 3, 4, 4, 4, 5, 5, 6}, then we have six plateaus which are 1, 2, 3, 4-4-4, 5-5 and 6. And obviously the length of the longest plateaus is 3.

Analysis:

Well, a straightforward idea is try to firstly compute all the length of different plateaus from left to right and then select the longest length. The pseudo-code is like this:

for each element in the array a[]
     if a[i] is equal to a[i-1]
          add 1 to the length for the current plateau
          check whether the current length is the longest one so far
     else
          reset length to 1 // plateau length is at least 1

Whether we need line 5&6 depends on whether we need to store the length of every plateau. If we just want to calculate the longest length then we can keep the code and use the “length” as a temp variable which is only used inside the loop. On the other hand, if we need to keep track of the length of all plateaus, we need to use an array of “length[]” to store the needed information.

/*
 * input: an array a[], the length of the array n
 * output: the length of the longest plateau
 */
int longestPlateau (int a[], int n)
{
	if (n == 0)
 		return 0;

	int length = 1;
	int longestLength = 1;

	for (int i = 1; i<n; i++)
 	{
		if (a[i] == a[i-1])
 		{
 			length++;
			longestLength = max(longestLength, length);
 		}
 		else
 			length = 1;
	}
	return longestLength;
}

Some more:

What if the given array is sorted (in the increasing order) already?

Actually if the array is sorted, the algorithm can be much simpler:

assume the longest length now is L, then we just need to compare a[i] and a[i-L], if they are equal then all the elements between them are also equal (since this is a sorted array!), and we can add 1 to the current longest length. The code looks like this:

/*
 * input: an sorted array a[] (increasing order), the length of the array n
 * output: the length of the longest plateau
 */
int longestPlateau (int a[], int n)
{
	if (n == 0)
 		return 0;

	int length = 1;
	for (int i = 1; i<n; i++)
 	{
		if (a[i] == a[i-length])
 			length++;
	}
	return length;
}

Launched my master thesis finally

Today I talked with my supervisor again and finally and officially launched my Master Thesis!

The next coming 12 months I will focus on developing a methodology on analyzing the performance bottleneck of large-scale multi-threaded software. I am really excited in the challenging problem about how to find the performance bottleneck when we are moving to many-core systems with hundreds of threads running concurrently. There will be a lot of fun and I believe I can learn a lot from it.

Another fun thing is, in the project plan written by my supervisor, the total budget is written as “81 000 KSEK” incorrectly, I hope Ericsson will not notice that mistake and if so, they have to pay a lot of  money to us since they have approved this project:)