并行

上图是寻址逻辑电路，输出端 A、B 独特组成 2 bit 的地址线，2 bit 的地址线能够示意 00、01、10、11 这 4 个地址，它们别离位于输入端 Z、Y、X、W，通过地址线示意的二进制数就能够找到输入端中的不同地址（当前就能够对其进行读写操作了） 也能够这样了解：输出端 A、B 相当于两个开关，输入端 Z、Y、X、W 相当于 4 个灯泡，两个开关的不同状态的组合就能够管制其中 1 个灯泡中的亮灭。接下来剖析繁多输出端：当输出端A 为 1 时，会选出输入端X、输入端W； 当输出端A 为 0 时（通过非门会变成 1），会选出输入端Z、输入端Y； 论断：不论输出端A 是 0 还是 1，都会选出一半当输出端B 为 1 时，会选出输入端W、输入端Y； 当输出端B 为 0 时（通过非门会变成 1），会选出输入端X、输入端Z； 论断：不论输出端 B 是 0 还是 1，都会选出一半因为只有当与门同时为 1 时，输入端才会输入 1。 当初，当输出端A和输出端B别离为 0、1 时，输入端Y就是输出端A、B 独特选出的地址。 上图的红线为 1（输出端A 的 0 通过非门会将其之后的线路置为 1）那它的工夫复杂度是怎么样的呢？ 因为输出端A、输出端B（比方地址 01）是同时输出的，所以电路会进行并行的二分查找，一个输出端的一次二分查找是 O(1)，所有的输出端并行，进行一次二分查找同样是 O(1)。 以上是 2 bit 寻址，更多 bit 的寻址同样是并行进行的，所以工夫复杂度同样是 O(1)。 ...

作者｜Yossi.Kreinin起源｜OSChina网站翻译｜Andy、袁不语、YuanyuanL、姜鹏飞校对｜胡燕君（OneFlow） 依据字面词义，并发（concurrent）是指竞争或反抗，而并行（parallelism）指两条直线永不相交的状态。在计算机中的并行和并发问题上，我与Joe Armstrong（译注：Erlang语言发明者）和Rob Pike（译注：Go语言发明者）这俩人的认识并不统一。 上面我以自动售货机和分礼物为例来阐明我的观点。 首先，并行和并发都是十分风行的概念，很多编程语言和工具通常都会重点宣传本人“兼具高度并行性和高度并发性”。但我却认为，并行和并发须要的是不同的工具，而对单个工具来说，并行和并发不可兼得。例如： Erlang、Rust、Go和STM Haskell善于并发解决Flow、Cilk、checkedthreads和Haskell偏重并行处理也有像Haskell这样的语言或零碎，既能解决并行，也能解决并发，但在Haskell外部，并行和并发分属两套不同的工具集。而且Haskell的官网wiki（http://www.haskell.org/haskel...）也解释了两者的应用准则，如果谋求并行，那么不应该应用并发工具： 经验总结：优先应用纯并行，而后再思考并发。Haskell早就意识到一个工具难以同时解决这两个问题。专门针对并行环境设计的新编程语言ParaSail，也面临同样的难处，尽管它也兼备针对并行和并发的工具集，但它也倡议在并行、非并发程序中尽量不要应用并发性能。 这就与很多人的观点天壤之别了，尤其是一些并发性能的铁粉，他们认为本人的并发工具解决起并行任务时也能熟能生巧。Rob Pike就说，因为Go是一种并发性语言，所以它也很适宜并行（http://talks.golang.org/2012/...）。 并发使得并行变得更容易（进步可扩展性等）。同样，Joe Armstrong也是这么说Erlang语言的。他甚至还说：当初还想用非并发的思维去解决并行的问题是缘木求鱼。 到底是什么起因导致这种一致，为什么Haskell和ParaSail的开发者认为并发和并行要用不同的工具，而Go和Erlang的开发者却认为并行语言也能解决并发呢？ 我感觉这是因为大家要解决的问题不同，对并行和并发的区别有不同了解，才导致最终论断不同。Joe Armstrong已经画过一张图来解释两者的区别，经自己的灵魂画手还原如下： 尽管并发在很多时候只波及繁多队列，但我还是依照Joe Armstrong的原图画了2个队列。从图中咱们能够看出： “并行”意味着可乐散发速度更快；从部分来看，“并行”实质上还是并发问题 ；先排队者先失去可乐；谁先拿到可乐都没关系，反正最终每个人都会拿到；当然，如果自动售货机里的可乐中途卖完了，前面的人就会拿不到——那也是没有方法，人生就是这样。以上是用自动售货机举例，如果换一个比喻，假如是给一群孩子散发礼物呢，这两种类比之间有实质性区别吗？ 有区别。自动售货机是一个事件处理零碎：人们不定时地到来，并且从机器中取不定数量的可乐。而分礼物是一个计算零碎：你晓得每个孩子想要什么，你晓得你买了什么礼物，并且你要决定哪个礼物分给哪个孩子。 在分礼物的场景中，“并发”与“并行”有不同的意义： 从下面的例子中，能够看出“并行”和“并发”有如下区别： 和自动售货机一样，“并发”也遵循“先到先得”的规定；“并行”则不一样：礼物已有标签，每个孩子拿到什么都是确定的；“并发”必须靠队列来维持秩序，防止两个孩子同时抢一个礼物——就像零碎要避免多个工作争先访问共享的数据，防止零碎瘫痪一样；“并行”模式下，就不须要队列了，不论谁先谁后，每个人都会拿到属于本人的礼物。在俄语中，“concurrent（并发，读作kon-koo-rent）”和“competitor（竞争对手）”是同义词。这种含意正好符合了分礼物中的“并发”情景的竞争属性：每个人都心愿本人最早到，这样就能挑到最好的礼物。 但“并行”场景则不同，每个礼物盒都写上了对应小朋友的名字。在逻辑上，孩子和礼物之间一一对应，互不穿插，互不烦扰。（但为什么我在图中画的连线却相交呢？一会儿我会解释这个问题。咱们能够先这么想：每个孩子奔向本人的礼物时路线会有相交，就像不同处理器寻找本人想要的数据时门路会相撞，但这并不影响到谁最终拿到什么礼物。） 1 计算和事件处理咱们能够联想电话客服、Web服务器、银行柜台等利用场景，它们和自动售货机是相似的事件处理零碎，都要解决并发工作，都必须解决不可预知的申请带来的不可避免的抵触。并行设计能够在肯定水平上进步处理速度，但其问题的本源还是在于并发中的抵触。 而在计算零碎中，例如分礼物、图形处理、计算机视觉、科学计算等中，则不会呈现并发抵触。输出是确定的，只需依据输出进行计算，而后输入，不会有意外烦扰。这时，并行的办法能够进步计算速度，但也容易呈现bug。 接下来咱们将持续探讨计算零碎和事件处理零碎的差异。 2 确定性：现实VS妄想在计算零碎中，咱们须要更多的确定性，因为这能够使编程人员轻松很多----如果程序的输入后果是可确定的，那咱们就能够释怀地去测试优化或者重构代码，只有输入后果没变，就阐明咱们没做错。 而且这种确定性要求的只是一种大略的确定，并不需要100%雷同----例如，在计算机视觉训练中，你并不要求机器每次找到的100张图片都是同一组，只有下面都有小猫就行；你也不要求机器每次都求出截然不同的圆周率近似值，只有它是在3和4之间就能够了。 在计算零碎中，领有确定性是现实状况，而且是能够达到的。 然而在事件处理零碎中，一切都是不确定的。如果事件产生程序不同，产生的后果也不同。譬如，如果我比你来得早，那罐仅剩的可乐就是我的；如果咱俩的银行联名账户只剩一块钱，而我的取款操作比你晚了0.001秒，钱就会打给你。 但如果再给我一次机会，那么钱属谁手就不肯定了。这就是事件处理零碎的不确定性。同样的程序运行屡次，后果能够背道而驰。而所有可能的后果数将随抵触的数量指数式增长。还有比这更让人头疼的事吗？ 3 如何判断并行平安：确定性VS正确性当程序以不同的程序处理事件时，你怎么确定其中没有bug？ 在计算零碎中，只有你每次运行程序都能失去雷同的后果，即便是谬误的后果，你也能够根本判定程序是并行平安的。就像运行一个搜寻小猫的程序，你每次都搜出了同一种类的小狗，那阐明你的程序有问题，然而不存在并行方面的问题。 然而在事件处理零碎中，状况就简单了一些，只有当零碎每次都能失去正确的后果，你能力确定零碎是并行平安的。 比方程序要模仿两个人同时取钱，不可能要求每次都是同一个人取到最初的一块钱，那如何判断这个程序没有bug？咱们只能从侧面来看，例如账户有没有呈现的负余额，会不会间断两次取空一个账户，会不会凭空减少账户金额等等。如果上述这些异常情况都没有产生，你就能够认为你的模拟程序没有问题。 对电话服务来说也是这样，你须要先定义出一系列“正确的后果”，而后用这些“正确的后果”验证你的电话服务是否失常。 但很遗憾，如果一个零碎的后果不能体现时序相干的问题，那你就无奈晓得零碎的时序有没有bug。这也是个头疼的问题。 4 并行谬误：易定位VS难定义对于标好名字的礼物来说，如果呈现并行谬误，是很容易发现的--即便礼物上的名字是用外语写的，孩子看不懂，这都没关系，为什么？请看下图： 所以对并行零碎来说，零碎不意识这些“标记”没关系，只有有标记就行。如果发现两个孩子抢夺同一份礼物，就能够找意识标记的人来解决抵触。 这就如同一个自动化的测试工具，不须要晓得哪个工作别离拜访什么数据，只有晓得一个工作不能拜访被别的工作批改过的数据就行了。如果产生了这种抵触拜访，那就当做bug报告给程序员来解决。 这样的工具当初曾经有很多了，Cilk语言有，Checkedthreads也带有一个基于Valgrind的相似工具。(注：Checkedthreads，一个C++并行框架https://github.com/yosefk/che...；Valgrind，一套反对动态分析的工具http://valgrind.org） 但Haskell不必这么干，因为首先它不存在副作用（side effect），这就保障了并行处理不会呈现抵触。但即使没有这种动态保障，Haskell的动静冲突检测机制也能防止抵触。 造成的意外后果就是，在计算零碎中，你不须要精确标记出bug所在，也不须要指出bug导致的问题是什么。 而在事件处理零碎中，必须有一个常识丰盛、责任感强的“小孩儿”来掌控全局，维持秩序。 此外，事件处理零碎还隐含了一个通用的规定：他人正在解决的过程，你就不能插手了，必须乖乖地在队列里等待。在“分礼物”场景中，“小孩儿”的存在能够保障这条规定失去恪守，让分礼物的工作更顺利，但还是难以避免其余可能的抵触。 在上图中，小孩A中途来到，回来后没有通过排队就接触礼物，违反规定，于是被零碎检测为bug，小孩儿呈现，重整秩序。 但纵观全程，小孩A先拆开了礼物，但又中途来到队列，回来后发现礼物被前面的小孩B领了——这种后果合乎零碎的要求吗？一方面，小孩B没有插队，也没有阻挡小孩A领礼物，并未违反零碎规定；但另一方面，小孩B领到本属于小孩A的礼物，这并不合乎零碎的预设。 上述情况体现在具体代码中是这样的：以下是一个谬误的汇款操作，能够轻易被主动调试工具检测出“有bug”： src.balance -= amountdst.balance += amount此处没有任何同步操作。src.balance可能被两个过程同时批改，导致其中的一次批改是有效的。好在，Helgrind等数据争用检测工具能够通过监控内存拜访发现这样的同步问题，Cilk和checkedthreads外部也有类似的工具。 但下列代码中的bug，上述工具可能就检测不进去了： atomic { src.balance -= amount } atomic { dst.balance += amount }下面代码中的“atomic”示意原子操作，意思是对账户余额的批改必须顺次进行。这样一来，检测工具就能够少操些心了——但这样就意味着没有bug了？ ...

归并排序归并排序能够简略得扩大为并行模式，每个合并操作互相独立，因而咱们以归并排序为例实现一下多线程排序。 自下而上归并排序根本示意图如下，假如 N % 2 == 0，归并排序共 log2(N) 层，共 n-1 次合并操作 代码如下，自底向上逐层合并， grpSize 为以后层的块大小，相邻块进行合并。repo1 和 repo2 别离指向输出数据和长期空间，每次合并之后进行替换secondGrpSize 确保了遇到数组开端时，第二个块大小的正确性secondGrpSize == 0 第二个块大小为零时，无需排序，间接拷贝输出数据到新空间即可mergeList 参数为： 块1起始地位，块2起始地位，块1长度，块2长度，指标数组template <class T> void mergesort(T *data, int N) { T *temp = new T[N]; T *repo1, *repo2, *aux; repo1 = data; repo2 = temp; for (int grpSize = 1; grpSize < N; grpSize <<= 1) {#pragma omp parallel for for (int stIdx = 0; stIdx < N; stIdx += 2 * grpSize) { int nextIdx = stIdx + grpSize; int secondGrpSize = min(max(0, N - nextIdx), grpSize); if (secondGrpSize == 0) { for (int i = 0; i < N - stIdx; i++) repo2[stIdx + i] = repo1[stIdx + i]; } else mergeList(repo1 + stIdx, repo1 + nextIdx, grpSize, secondGrpSize, repo2 + stIdx); } aux = repo1; repo1 = repo2; repo2 = aux; } if (repo1 != data) memcpy(data, temp, sizeof(T) * N); delete[] temp;}template <class T>void mergeList(T *src1, T *src2, int len1, int len2, T *dest) { int idx1 = 0, idx2 = 0; int loc = 0; while (idx1 < len1 && idx2 < len2) { if (src1[idx1] <= src2[idx2]) { dest[loc] = src1[idx1]; idx1++; } else { dest[loc] = src2[idx2]; idx2++; } loc++; } for (int i = idx1; i < len1; i++) dest[loc++] = src1[i]; for (int i = idx2; i < len2; i++) dest[loc++] = src2[i];}测试：16 线程下 ...