共 1,303 篇文章

共 6,316 篇文章及评论

Archives

帖子来自 Zhouweiming 周伟明 

OpenMP编程的数据竞争问题

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 28, 2009 在 11:09 上午
评论 (2)

OpenMP编程的数据竞争问题 使用OpenMP编程时，通常都是将函数内的某段代码并行化执行，但是，对于在函数内声明的变量，很容易被多个线程同时读写访问，这将导致数据竞争问题。 不妨先看一个代码例子： 找出下面代码中的问题 template <class T> void Parallel_Matrix_Sub(T *a, int row_a, int ...

继续 ›

分类: 博客征文专栏, 并行计算

多核程序调试与测试(1)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 28, 2009 在 11:08 上午
评论 (2)

多核程序调试与测试 注：本文主要根据今年到某企业讲课的胶片整理而成，因为是胶片，内容会显得比较精简，不到之处还请海涵。 多核程序的调试与测试历来是世界性难题，岂止为止没有发现能够对付它的银弹。这是因为多核程序与单核程序有着很大的不同，单核程序通常是一些内存访问、资源泄漏、计算错误（如差1）等。多核程序中，不仅会遇到单核程序中所遇到的所有问题，还会遇到许多新的问题和陷阱。 多核程序常见问题与陷阱 多核常见问题和陷阱如下： 1）数据竞争 2）死锁 3）数据操作时序 4）活锁 5）原子操作 6）资源回收 7）优先级翻转 8）线程挂起或死亡 9）线程重启 下面就来探讨一下这些问题和陷阱 数据竞争 常见的数据竞争问题有以下几种： 1）OpenMP中的数据竞争 2）原子操作中的数据竞争 3）通常多线程环境中的数据竞争 一般来说，数据竞争是一种非常难以发现和调试的问题，因为多个线程同时操作某个变量的频率本来就非常低，这使得问题需要重复非常多次才能出现一次，给测试带来了难度。 同时，如果要对数据竞争问题进行定位，难度就更大了，如果进行单步执行，问题很可能根本就不会出现。 对付数据竞争最有效的方法就是使用人工进行代码静态审查，找一些对多线程编程富有经验的人，对含有共享数据操作的模块进行代码检视。 另外一个方法就是借助工具，有一些专门的工具可以用来检查某些类型的数据竞争问题，比如Intel线程检测器工具可以识别数据竞争、死锁、等问题。

继续 ›

分类: 博客征文专栏, 并行计算

多核程序调试与测试(3)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 28, 2009 在 11:07 上午
评论 (1)

多核程序的测试 测试方法和步骤 1）先将程序编译成串行版本 2）对串行版本进行详尽的测试，确保没有问题 3）再编译成并行版本 4）对并行版本进行测试 死锁测试 死锁问题一般可以通过设计消除 – 将Lock() Unlock()操作改成 CScopedLock类调用 –  避免嵌套锁 – 检查是否有活锁问题 – 采用类似内存测试的方法进行测试 数据竞争测试 在核数较多的机器上进行测试 代码中不要插入测试和调试代码 如果用了sleep等延时操作，可以将其注释掉进行测试 代码静态检查 人工进行代码静态检查是必须的 重点检查数据竞争和数据操作时序 测试用例设计 基于阻塞情况而设计用例 – 比如在数据为空或为满情况下是否会出现阻塞现象 基于数据状态而设计用例 – ...

继续 ›

分类: 博客征文专栏, 并行计算

多核程序调试与测试(2)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 19, 2009 在 9:39 下午
评论 (1)

死锁 导致死锁的因素通常有以下几种： 1）忘记解锁 2）嵌套锁顺序错误 3）递归锁 死锁的问题很容易解决，忘记死锁可以通过使用CScopedLock类，利用类的析构函数自动释放锁，程序中尽量避免使用嵌套锁等，一般来说，嵌套锁都可以改写成非嵌套的锁。 数据操作时序 数据操作时序和数据竞争不一样，它发生于两次加锁解锁之间进行了任务切换。如果第2次加锁解锁的共享变量依赖于第1次加锁解锁的共享变量，两次之间切换任务时，修改了第1次的共享变量的值，将导致第2次访问的共享变量的值的变化，从而产生一些不可预知的问题。 数据操作时序问题的出现是随机性的，有些问题出现概率很小，很难定位 一般使用代码静态分析方法来发现这类问题 使用原子操作时最容易犯这个问题，这也是无锁编程的困难所在 活锁 多个线程A、B、C都在等待某一个锁，线程A释放锁，线程B获得锁，这时线程A又重新等待锁，线程B释放后，线程A又获得锁，如此循环下去，将导致线程C永远得不到锁。 这种锁一直被某几个线程持有，使得某个线程一直等不到锁的情况叫做“活锁”。 活锁问题通常与操作系统的线程调度策略有关，对于现代操作系统来说，同优先级线程通常采用轮循调度，一般不会发生活锁问题，但是对于不同优先级的线程，通常采用抢占式调度，则有可能发生活锁问题。 原子操作 现在的多核机器通常都支持原子操作，原子操作通常比锁的效率高（注：也有用原子操作实现的锁），原子操作一个最大的优势就是不会出现死锁，另外使用原子操作操作的变量，读取该变量时和读取普通变量是一样的，即使锁做得和原子操作一样快，原子操作也可以省去一半的操作开销。 原子操作使用的难度要比锁高，因此有以下注意事项： 1）原子操作极易引起数据竞争和数据操作时序问题 2）通过返回值获取变量修改后的值 3）不要轻易对指针使用原子操作 资源回收 多线程环境中的资源回收和单线程环境不同，单线程环境的回收资源通常是指资源泄漏问题，多线程环境的资源回收是指在回收了某个资源后，还有一些没有退出的常驻线程会继续访问这些已被释放了的资源。 保证安全回收资源的两点建议： 1）  确保资源回收前，其他线程都不会再访问这个资源 2）使用多线程退出算法来保证资源被回收前，让需要访问这个资源的线程全部退出。 线程挂起或死亡 在使用了锁的线程中，线程挂起通常是非常危险的问题，因为它有可能导致线程持有的锁没有释放，从而让其他线程等不到锁，一直等待下去。 线程重启 有些应用中，需要在不退出进程的情况下将线程重启，将线程重启也是一种难度较高的动作，因为首先需要将原线程退出，再将线程运行起来，线程重启时，如何确保资源被安全释放或安全保存，如何保证重启时，程序数据的安全？对于大型软件来说，这些问题都是比较棘手的问题。因此，除非有特殊需要，一般不要设计线程可以重启的应用。 要做到让线程重启的安全，以下几点供参考： 1）使用多线程退出算法让线程自然退出 2）释放线程私有资源 3）释放线程持有的锁 至此，将多线程编程常见问题和陷阱简要地过了一遍，下面接着谈谈多核程序测试方面。

继续 ›

分类: 博客征文专栏, 并行计算

多核动态任务调度的进一步探索(6)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 8, 2009 在 10:14 上午
评论 (1)

// 下面是CWaitTaskScheduler.cpp文件内容 /*  * Copyright (c) 2006-2008  * Author: Weiming Zhou  *  * Permission to ...

继续 ›

分类: 博客征文专栏, 并行计算, 开放源代码

多核动态任务调度的进一步探索(5)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 8, 2009 在 10:14 上午
评论 (1)

完整的代码存放在开源项目MCAPI(原CAPI项目，迁移到Sourceforge后改名为MCAPI)中，由于这部分代码暂未发布，因此我会把完整的代码贴在后面，当然，需要的话，你也可以直接到sourceforge的svn库中去将代码取下来，取代码的地址为https://mcapi.svn.sourceforge.net/svnroot/mcapi （需要用svn客户端去取，在Linux下，可以使用命令svn co https:// mcapi.svn.sourceforge.net/svnroot/mcapi mcapi来获取代码） 由于有依赖关系的调度其他部分和前面列出的几篇文中中讲的动态任务调度类似，因此就不再详述了，下面列出它的完整代码。 // 下面是CWaitTaskScheduler.h头文件内容 class CWaitTask { public:     THREADFUNC      ...

继续 ›

分类: 其他, 博客征文专栏, 并行计算, 开放源代码

多核动态任务调度的进一步探索(4)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 8, 2009 在 10:13 上午
评论 (3)

首先，我们要等待一组任务，可以设计一个计数变量，每完成一个任务，让计数减1，计数为0时表示所有的任务都完成了，这时可以往下继续执行了，只要计数不为0，那么程序就不能往下执行。下图是任务计数的一个示意。         当任务计数不为0时，必须等待其他任务完成，在通常的做法中，都是要用一个栅障来进行等待，实际上，判断计数不为0时，线程可以不进行等待，去偷取其他线程的任务执行，这样线程就不用空等，同时因为在执行其他线程的任务，也不会往下执行，保证了任务的执行时序和依赖关系。          下面给出关键部分的实现代码：  void CWaitTaskScheduler::SpawnTaskArrayAndWait(CTaskArray *pTaskArray) {     int i;     for (i = ...

继续 ›

分类: 博客征文专栏, 并行计算, 开放源代码

多核动态任务调度的进一步探索(2)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 8, 2009 在 10:13 上午
评论 (14)

对于矩阵乘法  C =  A × B，通常的做法是将矩阵进行分块相乘，如下图所示：       从上图可以看出这种分块相乘总共用了8次乘法，当然对于子矩阵相乘（如A0×B0），还可以继续递归使用分块相乘。对于中小矩阵来说，很适合使用这种分块乘法，但是对于大矩阵来说，递归的次数较多，如果能减少每次分块乘法的次数，那么性能将可以得到很好的提高。 Strassen矩阵乘法就是采用了一个简单的运算技巧，将上面的8次矩阵相乘变成了7次乘法，看别小看这减少的1次乘法，因为每递归1次，性能就提高了1/8，比如对于1024*1024的矩阵，第1次先分解成7次512*512的矩阵相乘，对于512*512的矩阵，又可以继续递归分解成256*256的矩阵相乘，…，一直递归下去，假设分解到64*64的矩阵大小后就不再递归，那么所花的时间将是分块矩阵乘法的(7/8) * (7/8) * (7/8) ...

继续 ›

分类: 博客征文专栏, 并行计算, 开放源代码

多核动态任务调度的进一步探索(3)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 8, 2009 在 10:13 上午
评论 (2)

如果使用动态任务调度来实现上面的Strassen矩阵乘法，通常的做法是将7次矩阵乘法变成7个任务来执行，但是，由于计算C0，C1，C2，C3时，必须先将M1,M2,M3,M4,M5,M6,M7计算好，因此生成了7个矩阵乘法任务后，必须在计算C0前，等待这7个任务全部完成。 下面给出动态任务调度实现Strassen矩阵相乘的伪代码。   Parallel_StrassenMultiply(A, B, C)  {     T1 = A0 + A3;     T2 ...

继续 ›

分类: 博客征文专栏, 并行计算, 开放源代码

多核动态任务调度的进一步探索(1)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十二月 8, 2009 在 10:12 上午
评论 (4)

多核动态任务调度的进一步探索   多核中的动态任务调度算法可以说是多核三大算法之首，因为它可以将一些串行程序变成并行执行的。程序员只要按照一定接口规范写串行算法，就可以用动态任务调度器将其并行运行。Intel TBB库中就实现了一个动态任务调度算法，不过TBB库中的实现代码量较大（大约有4000多行代码），估计没有多少人能完全看得明白，我在开源MCAPI(原CAPI项目，迁移到Sourceforge后改名为MCAPI)库(地址：http://sourceforge.net/projects/mcapi)中也实现了几种不同类型的动态任务调度算法，这些实现中的任何一种都只用了两百行代码左右，其中有部分实现方法在今年5~6月份时已撰文介绍了，文章链接如下： 多核中的动态任务调度(1) 多核中的动态任务调度(2) 多核中的动态任务调度(3) 多核中的动态任务调度(4)   用动态任务调度器实现Parallel_For （1） 用动态任务调度器实现Parallel_For （2）   用Parallel_For进行并行快速排序 用Parallel_For进行并行快速排序 用Parallel_For进行并行快速排序     上面这些文章中介绍的动态任务调度算法，也能实现将一些串行算法自动变成并行执行，不过这个算法的功能相比TBB中的动态任务调度算法功能上要差一些，因为它只能实现一些简单的无依赖关系的动态任务调度，当任务间存在依赖关系时，必须等待依赖的任务完成后，才能继续执行下面的任务。为了弥补上述动态任务调度功能上的不足，我在今年年初时设计了一个新的动态任务调度算法，可以实现有依赖关系的动态任务调度。 下面就是一种典型的有依赖关系的任务调度 l  将一个大的任务被拆分成多个小任务 l  需要等这多个小任务全部处理完，然后才能对多个小任务处理结果进行合并 l  拆分任务和对任务结果进行合并间需要进行等待   为了进一步说明问题，下面以并行Strassen矩阵乘法来说明这种有依赖关系的任务调度问题。

继续 ›

分类: 博客征文专栏, 并行计算, 开放源代码

用Parallel_For进行并行快速排序

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 五月 31, 2009 在 10:43 上午
评论 (10)

用Parallel_For进行并行快速排序       注：本文主要内容摘自笔者所著的《多核计算与程序设计》一书，略有修改，后续还会继续发布系列文章，如有需要，可以考虑将一下地址加入到您的浏览器收藏夹中：http://software.intel.com/zh-cn/blogs/category/multicore/。 上一篇文章 用动态任务调度器实现Parallel_For  中，实现了Parallel_For()功能， Parallel_For()可以实现许多的并行区间处理功能，下面以并行快速排序为例来讲解如何使用Parallel_For()的功能。 要用Parallel_For()来进行并行快速排序，需要先继承CRange类来实现一个CQuickSortRange类，然后就可以将CQuickSortRange类的实例作为参数传给Parallel_For()进行并行快速排序。 CQuickSortRange类的定义如下： template <class T> class CQuickSortRange : public ...

继续 ›

分类: 博客征文专栏, 并行计算

用动态任务调度器实现Parallel_For （2）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 五月 31, 2009 在 10:30 上午
评论 (0)

上一篇文章：  用动态任务调度器实现Parallel_For (1)   上面的处理过程可以用C++代码实现如下： /**   CRange的任务处理入口函数            @param  void *pArg - 实际为一个CRange指针          @return  ...

继续 ›

分类: 博客征文专栏, 并行计算

用动态任务调度器实现Parallel_For （1）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 五月 31, 2009 在 10:22 上午
评论 (0)

用动态任务调度器实现Parallel_For     注：本文主要内容摘自笔者所著的《多核计算与程序设计》一书，略有修改，后续还会继续发布系列文章，如有需要，可以考虑将一下地址加入到您的浏览器收藏夹中：http://software.intel.com/zh-cn/blogs/category/multicore/。 上一篇文章：   1、多核中的动态任务调度(1) 2、多核中的动态任务调度(2) 3、多核中的动态任务调度(3) 4、多核中的动态任务调度(4)   用动态任务调度器实现Parallel_For 从前面的CNestTaskScheduler的使用方法中可以发现，采用嵌套任务调度，可以很方便地将一个大区间拆分成更多的小区间，将各个拆分后的区间放入分布式队列中，然后各个线程再从分布式队列中取出相应的区间进行处理。 对于一个for循环来说，通常处理的都是一个区间，因此也可以使用任务调度的方式将其拆分成更小的区间进行并行化执行。下面就利用嵌套任务调度的方法来实现一个Parall_For功能。 1.        区间的描述：CRange类 要实现对区间的分拆功能，使用一个类CRange来描述区间。在实际情况中，区间通常可以由两个整数表示区间开始和结束位置，也可以由两个迭代器变量来表示区间开始和结束位置。不过CRange是一个抽象接口类，它并不定义区间的开始和结束位置，区间的开始和结束位置由继承它的类去定义。CRange类用C++定义如下： class CRange { protected:     CNestTaskScheduler  *m_pTaskScheduler; public:     CRange(){};     CRange(CNestTaskScheduler *p);     void ...

继续 ›

分类: 博客征文专栏, 并行计算

多核中的动态任务调度(3)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 五月 30, 2009 在 2:26 下午
评论 (0)

上一篇文章： 1）多核中的动态任务调度(1) 2）多核中的动态任务调度(2) 3) 线程池入口函数处理流程 线程池入口函数的处理在一个循环中进行，每次循环中，从分布式队列中获取任务，然后执行任务的启动入口函数，如果从分布式队列中获取任务失败，则认为所有任务被处理完，此时需要判断是否还有挂起的线程，有则需要将挂起线程执行起来让其退出，然后退出循环并结束当前线程。    图3  线程池入口函数处理流程图   /**   嵌套任务调度的获取任务函数            @param  TASK &Task - 接收从分布式队列中获取的任务          ...

继续 ›

分类: 博客征文专栏, 并行计算

多核中的动态任务调度(4)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 五月 30, 2009 在 2:26 下午
评论 (1)

上一篇文章： 多核中的动态任务调度(1) 多核中的动态任务调度(2) 多核中的动态任务调度(3)   3、CNestTaskScheduler使用方法 注：完整的CNestTaskScheduler的源代码，请到CAPI开源项目进行下载，下载地址为：https://sourceforge.net/projects/mcapi/ 下面以一个区间递归分拆为例讲解如何使用CNestTaskScheduler。首先需要写一个任务处理入口函数，代码如下： struct RANGE {     int begin;     int end; };   CNestTaskScheduler  *pTaskSched = NULL;   /**   ...

继续 ›

分类: 博客征文专栏, 并行计算

多核中的动态任务调度(2)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 五月 30, 2009 在 2:13 下午
评论 (0)

  上一篇文章：多核中的动态任务调度(1) 1) BeginRootTask()的处理流程 BeginRootTask()的处理流程较简单，它先创建线程池，接着将一个原始任务放入到第0个线程的本地队列中，然后执行第0个线程，最后等待所有线程执行完。处理流程如下图所示：      图1 嵌套型任务BeginRootTask()处理流程图 BeginRootTask()的代码如下： /**   嵌套任务调度的开始根线程函数            @param  TASK &Task - 要执行的最初任务          ...

继续 ›

分类: 博客征文专栏, 并行计算

多核中的动态任务调度(1)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 五月 30, 2009 在 2:03 下午
评论 (1)

  多核中的动态任务调度 注：本文主要内容摘自笔者所著的《多核计算与程序设计》一书，略有修改，后续还会继续发布系列文章，如有需要，可以考虑将一下地址加入到您的浏览器收藏夹中：http://software.intel.com/zh-cn/blogs/category/multicore/。 1、基本思想 动态任务调度可以将一系列分解好的任务进行并行运行，并取得一定程度的负载均衡。动态任务调度的最大作用就是用它来做并行计算。动态任务调度有多种方法，一般可以使用分布式队列【1】来实现，下面讲解一种最简单的嵌套型任务调度的实现方法。 对于嵌套型任务，通常都有一个或多个开始任务，其他任务的产生都源于这些开始任务。 调度的方法为，每个线程由一个本地队列，另外由一个所有线程共享的队列。当每个线程产生n个新任务后，先检查本地队列是否为空，如果为空，则放入一个任务到本地队列中。然后检查共享队列是否满，如果未满则将其他任务放入共享队列中，否则放入到本地队列中。 上面这个调度方法实际上和CDistributeQueue【1】中的进队操作方法是一样的，因此可以使用CDistributeQueue来实现嵌套型动态任务的调度。 一般来说，嵌套型动态任务调度会遇到以下一些问题： 1、 初始时可能只有一个任务运行，此种情况下只能有一个线程运行，其他线程必须挂起。当动态任务产生后，需要唤醒挂起的线程进行执行。 2、 由于每个任务中会产生新的任务，因此每个任务既是消费者，同时也是生产者。在操作本地队列时，比非嵌套型任务调度更加方便，如何将本地队列的操作最大化是首要考虑的问题。 根据上面的思想，下面设计一个CNestTaskScheduler类来实现对嵌套型动态任务的调度。 2、CNestTaskScheduler类的设计和实现 CNestTaskScheduler类的定义如下： class CNestTaskScheduler { private:     CThreadPool     m_ThreadPool;//(TaskScheduler_StartFunc, NULL, 0);     CDistributedQueue<TASK, ...

继续 ›

分类: 博客征文专栏, 并行计算

OpenMP编程指南

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 四月 20, 2009 在 10:43 上午
评论 (5)

OpenMP编程指南 进入多核时代后，必须使用多线程编写程序才能让各个CPU核得到利用。在单核时代，通常使用操作系统提供的API来创建线程，然而，在多核系统中，情况发生了很大的变化， 如果仍然使用操作系统API来创建线程会遇到一些问题。具体来说，有以下三个问题： 1）CPU核数扩展性问题 多核编程需要考虑程序性能随CPU核数的扩展性，即硬件升级到更多核后，能够不修改程序就让程序性能增长，这要求程序中创建的线程数量需要随CPU核数变化，不能创建固定数量的线程，否则在CPU核数超过线程数量上的机器上运行，将无法完全利用机器性能。虽然通过一定方法可以使用操作系统API创建可变化数量的线程，但是比较麻烦，不如OpenMP方便。 2）方便性问题 在多核编程时，要求计算均摊到各个CPU核上去，所有的程序都需要并行化执行，对计算的负载均衡有很高要求。这就要求在同一个函数内或同一个循环中，可能也需要将计算分摊到各个CPU核上，需要创建多个线程。操作系统API创建线程时，需要线程入口函数，很难满足这个需求，除非将一个函数内的代码手工拆成多个线程入口函数，这将大大增加程序员的工作量。使用OpenMP创建线程则不需要入口函数，非常方便，可以将同一函数内的代码分解成多个线程执行，也可以将一个for循环分解成多个线程执行。 3）可移植性问题 目前各个主流操作系统的线程API互不兼容，缺乏事实上的统一规范，要满足可移植性得自己写一些代码，将各种不同操作系统的api封装成一套统一的接口。OpenMP是标准规范，所有支持它的编译器都是执行同一套标准，不存在可移植性问题。 综上所述，在多核编程中，使用OpenMP就很有必要，下面列出以前发表在我的CSDN博客中的OpenMP文章，供大家参考。 1、OpenMP并行程序设计（一） 介绍OpenMP程序在并行计算时的效率，在双核CPU上效率增加了整整一倍。 阅读全文 2、OpenMP并行程序设计（二） 1、fork/join并行执行模式的概念 2、OpenMP指令和库函数介绍 3、parallel 指令的用法 4、for指令的使用方法 ...

继续 ›

分类: 博客征文专栏, 并行计算

并行顺序搜索及终止检测（1）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 四月 3, 2009 在 1:57 下午
评论 (0)

并行顺序搜索及终止检测 注：本文主要内容摘自笔者所著的《多核计算与程序设计》一书，略有修改，后续还会继续发布系列文章，如有需要，可以考虑将一下地址加入到您的浏览器收藏夹中：http://software.intel.com/zh-cn/blogs/category/multicore/。 在一个有序表里进行搜索时，可以使用二分查找一类的高效算法，计算量非常低，通常达不到最小线程粒度的要求，因此这种顺序表的查找在实际情况中不需要分解成多个任务来执行。但是当对一个无序的表进行搜索时，通常需要对整个无序表进行遍历，如果表的规模大于最小线程粒度的大小，那么将其分解成多个任务来执行就很有必要了。 对一个无序的顺序表的并行搜索非常简单，将表分成相等的几块，每个线程搜索一块，如果找到了要查找的目标数据，那么中止搜索。 下面来看两个并行搜索的实例： 1、         并行搜索指定数据 在一段无序的数据中，如果要查找指定数据，只要将其划分成若干段，每个线程搜索其中一段，就可以搜索到指定的数据位置。下面的代码实现了在数组里并行搜索指定数据，最终返回指定数据在数组中的下标位置。 int Parallel_SearchData(void **ppData, int nLen, void *pData,                                            COMPAREFUNC ...

继续 ›

分类: 博客征文专栏, 并行计算

并行顺序搜索及终止检测（3）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 四月 3, 2009 在 1:52 下午
评论 (0)

上两篇文章请看： 1）并行顺序搜索及终止检测（1） 2）并行顺序搜索及终止检测（2） 5、         源代码实现 下面是带有终止检测算法的并行顺序搜索源代码： LONG volatile g_SearchFlag = 0; static int g_SearchPos = -1;   void ...

继续 ›

分类: 博客征文专栏, 并行计算

并行顺序搜索及终止检测(2)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 四月 3, 2009 在 1:51 下午
评论 (0)

上一篇文章请看：并行顺序搜索及终止检测（1） 3、         伪共享问题的解决 首先需要给pnMax分配一个更大的空间，如下面的代码所示： #define CACHE_LINE_LEN  64        int *pnMax = (int *)malloc(nCore * ...

继续 ›

分类: 其他, 博客征文专栏, 并行计算

用原子操作解决多线程退出问题(1)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 三月 31, 2009 在 1:24 下午
评论 (3)

用原子操作解决多线程退出问题 注：本文主要内容摘自笔者所著的《多核计算与程序设计》一书，略有修改，后续还会继续发布系列文章，如有需要，可以考虑将一下地址加入到您的浏览器收藏夹中：http://software.intel.com/zh-cn/blogs/category/multicore/。 单个子线程退出算法 在使用多线程编程时，当存在一些常驻的线程访问的共享数据时，退出时必须要先结束这些常驻的线程才能对共享资源进行释放操作，否则如果没有先让常驻线程退出就进行释放的话，释放完共享资源后，常驻线程将访问已经释放了的共享资源，导致程序出现异常。 例如，在多线程环境中，有一个子线程一直在对链表循环地进行遍历操作，这时候想退出主线程，如何将这条链表释放呢？如果在主线程中退出时简单地将链表释放，释放后到程序完全退出前还有一段时间，如果这时发生线程切换，切换到那个进行遍历操作的子线程上，这个子线程还会继续对链表进行遍历操作，但是主线程已经将链表释放了，这会导致子线程访问已经释放的内存而产生异常。 下图是一个不安全的多线程退出时的场景示意图：     图1：不安全的多线程退出场景示意图 有必要设计一个算法来避免上图所示的问题，分析上述例子可以发现，要使程序安全地退出，必须在释放链表前让所有对链表有操作的线程退出，这样在释放链表后就不会再有线程访问已经释放的链表了。但怎样能在释放链表前让其他对链表有操作的线程安全地退出呢？有操作系统基础的读者应该知道线程如果不是正常退出会导致资源泄漏，因此不能使用线程退出函数如TerminateThread()等强制那些线程退出，最好的方法是让那些线程自己主动退出。 要将对链表进行操作的线程在链表释放前退出，必须让这些线程知道要进行释放操作了，可以使用一个退出标志来实现这一点，也就是在进行释放操作前先设置一个退出标志。子线程中要定期检测这个标志，如果标志表示可以退出时即退出线程。在退出线程时，要让进行释放操作的线程知道进行遍历操作的子线程已经退出了，通常可以让子线程在退出前发送一个事件通知——释放线程可以进行释放操作了。     图2：单个常驻线程情况下的安全退出过程示意图 下面再来看多个线程访问共享资源时的退出情况，详情请看： 用原子操作解决多线程退出问题(2)  

继续 ›

分类: 博客征文专栏, 并行计算

用原子操作解决多线程退出问题(2)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 三月 31, 2009 在 1:15 下午
评论 (7)

多个线程访问共享资源时的退出 上面讨论的是单个常驻子线程访问共享资源的情况，实际上可能有多个子线程在对链表进行操作，如果每个子线程都在退出前发送一个事件通知给释放操作的线程，可能第一个子线程已经发送了事件通知，第二个子线程还在运行，但释放操作的线程已经收到事件通知、进行了释放操作；由于第二个线程还在运行，如果这时线程切换到第二个子线程上，则会导致第二个子线程访问已经释放的链表。要解决这个问题，必须保证让进行释放操作的线程在所有访问共享资源的子线程都退出后才能释放链表，这样又引入一个问题，如何让释放操作的线程知道所有子线程都已经退出了呢？ 最简单的方法就是用一个计数变量来实现，计数变量初始为0，每创建一个对链表操作的线程，计数加1；每退出一个操作线程，计数减1，因此在对链表操作的线程中，只要判断计数是否为0，若为0，就发送一个事件通知给释放操作的线程表示可以释放即可。   图3：多个常驻线程情况下的安全退出过程示意图 经过上面的分析，下面就来使用原子操作实现多线程退出算法。 无锁的退出算法 多线程退出算法本身的共享变量主要是计数和退出标志，都是简单的共享变量，并且访问最频繁的操作是对标志变量的读取操作，每循环一次便要读取一次，其他操作都是一次性的写操作，属于写操作稀少，读操作频繁的情况，可以使用多核编程中的条件同步模式一文中讲过的条件同步模式高效地实现。 用原子操作来实现时，最大的好处是读操作和访问非共享变量一样不需要任何保护，也不需要原子操作，只有在写时才使用原子操作。 无锁的编码用C/C++实现如下： class CMTask { private:     EVENT m_ExitEvent;            // 退出事件     LONG volatile ...

继续 ›

分类: 博客征文专栏, 并行计算

用原子操作解决多线程退出问题(3)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 三月 31, 2009 在 1:07 下午
评论 (0)

前两篇文章请看： 1）用原子操作解决多线程退出问题(1) 2）用原子操作解决多线程退出问题(2) 多线程退出算法的使用 在使用了共享资源的常驻子线程中，一般采用以下伪代码所示的结构来构造线程的入口处理函数。 CMTask  *g_pMtask = new CMTask; ThreadFunc() {        g_pMtask->EnterTask();        for(;;)        {               if ( ...

继续 ›

分类: 博客征文专栏, 并行计算

原子操作在多核编程中的使用（1）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 三月 31, 2009 在 11:17 上午
评论 (10)

原子操作在多核编程中的使用 注：本文主要内容摘自笔者所著的《多核计算与程序设计》一书，略有修改，后续还会继续发布系列文章，如有需要，可以考虑将一下地址加入到您的浏览器收藏夹中：http://software.intel.com/zh-cn/blogs/category/multicore/。 现代操作系统中，一般都提供了原子操作来实现一些同步操作，所谓原子操作，也就是一个独立而不可分割的操作。在单核环境中，一般的意义下原子操作中线程不会被切换，线程切换要么在原子操作之前，要么在原子操作完成之后。更广泛的意义下原子操作是指一系列必须整体完成的操作步骤，如果任何一步操作没有完成，那么所有完成的步骤都必须回滚，这样就可以保证要么所有操作步骤都未完成，要么所有操作步骤都被完成。 例如在单核系统里，单个的机器指令可以看成是原子操作（如果有编译器优化、乱序执行等情况除外）；在多核系统中，单个的机器指令就不是原子操作，因为多核系统里是多指令流并行运行的，一个核在执行一个指令时，其他核同时执行的指令有可能操作同一块内存区域，从而出现数据竞争现象。多核系统中的原子操作通常使用内存栅障（memory barrier）来实现，即一个CPU核在执行原子操作时，其他CPU核必须停止对内存操作或者不对指定的内存进行操作，这样才能避免数据竞争问题。 Win32 API中常用的原子操作主要有三类，一种是加1减1操作，一种是比较交换操作，另外一种是赋值（写）操作。 1.        原子加1减1操作 原子加减操作主要是对指定的变量进行加1或减1操作，原子加1操作API如下： LONG InterlockedIncrement( LONG volatile* Addend); 执行原子加1操作，Addend的值会被加1，返回值为原始Addend加1后的值。需要注意的是，当操作结束后，如果再读取Addend的值不一定等于原始Addend加1后的值，因为这时有可能其他线程会修改Addend的值。 原子减1操作的API如下： LONG InterlockedDecrement( LONG ...

继续 ›

分类: 博客征文专栏, 并行计算

原子操作在多核编程中的使用（2）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 三月 31, 2009 在 11:09 上午
评论 (0)

前一篇文章请看： 原子操作在多核编程中的使用（1） 3.        原子写操作 原子写操作的作用是对共享变量进行写操作，在微软的API中，原子写操作的对应函数为： LONG InterlockedExchange( LONG volatile* Target, LONG Value); InterlockedExchange的作用为将Value的值赋给Target指向的变量，返回Target指向变量未被赋值前的值。 下面用AtomicWrite()来表示原子赋值操作， #define AtomicWrite(x, y)  ...

继续 ›

分类: 博客征文专栏, 并行计算

多核编程伪共享问题及其对策

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 三月 26, 2009 在 10:26 上午
评论 (0)

多核编程中的伪共享问题及其对策 注：本文主要内容摘自笔者所著的《多核计算与程序设计》一书，略有修改，后续还会继续发布系列文章，如有需要，可以考虑将一下地址加入到您的浏览器收藏夹中：http://software.intel.com/zh-cn/blogs/category/multicore/。 前一篇文章 “多核编程锁竞争问题及其对策”中，提到了多核编程所遇到的各种问题，本文就来讲述一种的一个问题，伪共享问题及其对策。 伪共享问题在《多核程序设计技术－通过软件多线程提升性能》一书中有详细讲解，它是由于CPU cache机制造成的，CPU读取Cache时是以行为单位读取的，如果两个硬件线程的两块不同内存位于同一Cache行里，那么当两个硬件线程同时在对各自的内存进行写操作时，将会造成两个硬件线程写同一Cache行的问题，它会引起竞争，就像在乒乓球比赛一样，效率将成百倍的下降。 在单核系统中，伪共享问题是不存在的，因为同一时刻只有一个硬件线程在执行，不存在同时写同一Cache行的问题。 伪共享问题在实际情况中是经常可以碰到的，比如两个线程同时写一个数组的相邻部分，或者写两块相邻的内存，这些都有可能造成伪共享问题。 对于分配的内存，可以采取一定的内存分配算法使各块内存不在同一Cache行里，但对于数组或变量的访问，就必须要由程序员在设计时进行避免伪共享问题。 要解决伪共享问题，首先必须知道给定的内存中，那块区域会处于同一Cache行内，Intel的系统中，有一个简单的算法可以得到一块内存中对应的Cache行首地址，即每个Cache行首地址都是Cache行大小的整数倍。 比如一块内存大小为60字节，首地址为0x0012ff52，由于0x0012ff52除以64以后余数为0x12，因此这个地址不是Cache行的首地址。在这个地址之前的Cache行首地址为0x0012ff40，在这个地址之后的Cache行首地址为0x0012ff80。对应的内存位于两块不同的Cache中。如下图所示：   图1：Cache行对齐示意图 根据上面所说的Cache行首地址为Cache行大小的整数倍的特点，可以设计一个函数来取出给定地址之后的第0个Cache行首地址。代码如下： /**  计算给定地址之后的第0个Cache行首地址     如果给定地址刚好为一个Cache行首地址，那么计算结果等于它自身     @param    void *pAddr - 给定的地址    ...

继续 ›

分类: 博客征文专栏, 并行计算

多核编程锁竞争问题及其对策

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 三月 26, 2009 在 10:08 上午
评论 (10)

多核编程锁竞争问题及其对策 注：本文主要内容摘自笔者所著的《多核计算与程序设计》一书，略有修改，后续还会继续发布系列文章，如有需要，可以考虑将一下地址加入到您的浏览器收藏夹中：http://software.intel.com/zh-cn/blogs/category/multicore/。 在多核系统中编程，主要是使用多线程技术让程序并发执行。不过与单核系统编程的多线程编程有了很大的不同，具体来讲，有以下几个方面的区别： 1）锁竞争导致的串行化的区别 2）线程分解与执行的区别 3）CPU核负载平衡的区别 4）任务调度策略的区别 5）CPU Cache存取的区别（伪共享问题） 6）任务优先级抢占的区别 7）串行计算与并行及分布式计算的区别 本文先讲解其中的锁竞争问题及其对策。 锁竞争导致的串行化的区别 在单核系统中，如果某个线程获取了锁，那么这个线程将获取CPU的运行时间，其他等待获取锁的线程将被阻塞住，并得不到CPU的运行时间。因此单核系统中，即使使用了锁，影响计算时间的只是加锁、解锁操作本身耗费的时间，CPU还是一直处于运行状态的，并不会因为锁的问题出现CPU空闲现象，除非程序有BUG，出现死锁现象。 而在多核系统中，比如在双核系统中有两个线程A、B要使用同一把锁，那么当线程A获取锁后，在A未解锁前线程B将处于阻塞状态，这是只有线程A在运行，两个CPU核只有一个得到利用，另外一个CPU核处于空闲状态。 上面说的是两个线程的情况，实际上即使有更多线程，如果线程都处于等待同一把锁状态时，会导致只有一个线程在运行的情况，这样多个线程受锁竞争的影响出现串行化执行现象。 锁竞争导致的串行化现象对加速比指标有非常重大的影响，不论CPU核有多少，最终只有一个核在运行，加速比只有1，多核的性能只相当于单核的性能。 锁竞争的解决策略 锁竞争的解决方法有许多种，一种最简单的方法就是将竞争一把锁改为竞争多把锁，这样将可以使得同时有多个线程在运行，避免了同时只有一个线程在执行的情况。 竞争多把锁又叫分布式锁竞争，相关的设计模式有线程分组竞争模式和线程随机竞争模式，相关的材料可以参考以下两篇文章： 1、多核编程中的线程分组竞争模式 讨论了使用线程分组锁竞争方式来消除锁竞争导致的CPU饥饿现象，队列池就是线程分组竞争的一个非常好的实践，线程分组竞争模式相对于无锁编程具有更好的优势。 阅读全文 2、多核编程中的任务随机竞争模式的概率分析 本文主要分析了多个线程在随机分布式锁竞争的情况下，有不少于CPU核数个数的线程在运行的概率。然后将随机竞争和无锁编程的性能进行了理论上的比较。阅读全文 除了上面两种模式外，某些情况下还有一些更高效的方法来消除锁竞争问题，其基本思想就是减少锁的使用，多核编程中的条件同步模式这篇文章中讲解了一种减少锁的使用的方法。另外一种减少锁的方法是批量处理模式，以链表遍历为例，将每迭代一个节点就进行一次加锁解锁改为迭代多个节点进行一次加锁解锁，可以有效地减少锁的使用。 要彻底消除锁竞争，最理想的境界就是不使用锁，这就要用到老子是伟大的多核计算科学家一文中所说的自私的方法，有关如何在程序中实现自私，可以参考以下几篇文章。 多核分布式队列的实现：偷与自私的运用（1） 多核分布式队列的实现：偷与自私的运用（2） 多核分布式队列的实现：偷与自私的运用（3） 多核分布式队列的实现：偷与自私的运用（4） 这篇文章暂时先讲到这里，下一篇文章将讲解多核编程的伪共享问题。  详情请看：多核编程伪共享问题及其对策 更多的多核相关的资源，可以访问： 1）Intel软件社区多核论坛：http://forum.csdn.net/Intel/IntelMulti-core/ ...

继续 ›

分类: 其他, 博客征文专栏, 并行计算

程序员的十层楼 11层(上帝)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 二月 9, 2009 在 9:58 上午
评论 (202)

  第1～3层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1071/ 第4～5层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1073/ 第6～7层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1077/ 第8～9层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1081/ 第10层(上) 看这里：http://software.intel.com/zh-cn/blogs/2009/02/09/1084/ 第10层(下) ...

继续 ›

分类: 其他

程序员的十层楼 10层(下)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 二月 9, 2009 在 9:51 上午
评论 (79)

  第1～3层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1071/ 第4～5层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1073/ 第6～7层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1077/ 第8～9层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1081/ 第10层(上) 看这里：http://software.intel.com/zh-cn/blogs/2009/02/09/1084/ 3、海森堡 ...

继续 ›

分类: 其他

程序员的十层楼 10层(上)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 二月 9, 2009 在 9:46 上午
评论 (37)

  第1～3层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1071/ 第4～5层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1073/ 第6～7层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1077/ 第8～9层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1081/ 第10层 大哲 看了这层楼的名字“大哲”，可能不少人已经猜到了这层楼的秘密，那就是你的成果必须要上升到哲学的高度，你才有机会能进到这层来。 当然，上升到哲学高度只是一个必要条件，牛顿的万有引力似乎也上升到了哲学的高度，因为不知道引力到底是怎么来的，但是牛顿没有被划到这一层，因为进到这层还有另外的条件，那就是你的成果必须引起了哲学上的深度思考，并能让人们的世界观向前跨进一大步。窃以为牛顿、爱因斯坦等人的成就还达不到让人们世界观向前跨进一大步的程度。 所以，这层楼中的人的成就对我们普通人认识世界非常重要，你可以不学相对论，但是你不可以不对这层楼的人所作出的成就不了解，否则你的世界观就是极其不完整的，会犯许多认识上的错误。不幸的是，中国的科普知识普及还不够到位，知道这层楼成就的人好像并不多，程序员中恐怕更少。下面就来看看这些用一只手的手指数得清的大哲们，到底有什么成就，能比万有引力定律和相对论还重要。 1、希尔伯特 (1862～1943) 第1位进到此楼层是一位名叫“希尔伯特”的大数学家，如果你学过《泛函分析》，那么你在学习希尔伯特空间时可能已经对这位大数学家有所了解；如果你不是学数学出身的，又对数学史不感兴趣的话，恐怕你从来没有听说过这个名字。不过如果我问一下，知不知道二次世界大战前世界数学中心在那里，你肯定会有兴趣想知道。 不妨说一下，二战前整个世界的数学中心就在德国的哥廷根，而我们这位大数学家希尔伯特便是它的统帅和灵魂人物。即使在二战期间，希特勒和丘吉尔也有协定，德国不轰炸牛津和剑桥，作为回报，英国不轰炸海德堡和哥廷根。 整个二十世纪上半期的超一流数学家，几乎都出自其门下。这里不妨举几个我们熟悉的人物，例如冯·诺伊曼就曾受到他和他的学生施密特和外尔的思想影响，还到哥廷根大学任过希尔伯特的助手，钱学森的老师冯·卡门是在哥廷根取得博士学位的。顺便提一下，这位大数学家发现当时物理学上出了很多大的成果如相对论和量子力学，但是这些物理学家的数学功力明显不足，因此有一段时间带领他的学生们研究过物理学，并独立发现了广义相对论，只是不好意思和物理学家争功劳，将广义相对论的功劳全部让给了爱因斯坦。 广义相对论相对于这位大数学家在数学上的贡献，其实是算不了什么的，只是由此可看出这位大数学家品格的高尚之处。如果再去看看牛顿之流的人物的品行，整天和莱布尼茨、虎克等人争功劳，利用自己的优势地位打压他人，甚至闹得上法庭，和这位希尔伯特先生比起来，简直就是个小丑。 说到这里，你可能对这位大数学家“希尔伯特”有了一些初步映象，感觉到了他的重要性，不过他在数学上的主要成就可不是几句话说得清楚的。首先，他是一位集大成者，精通当时数学所有分支领域，在数学的各个领域都有较大的贡献，当然这些成就只能让他成为一个大科学家，不能带他进入这层楼。事实上这位“希尔伯特”解决的任何一个数学问题都够不到这层楼的高度，那么他怎么混到这层楼来了呢？ 话得从1900年说起，当时还很年轻的希尔伯特在当时的世界数学大会上做了一个报告，高屋建瓯地提出了著名的23个未解决的数学问题，然后整个二十世纪上半期，全世界的数学家们都在这23个问题的指导下展开研究，直到现在仍然有许多数学家受这23个问题的指导在进行研究。例如我们熟知的哥德巴赫猜想，就属于其中第8个问题素数分布的一个子问题。 如果用“高瞻远瞩”来形容这位大数学家的话，那么这个世界上恐怕没有第二个人再配得上“高瞻远瞩”这四个字，不论是欧拉、高斯、牛顿、爱因斯坦还是被誉为最有才华的数学家伽罗华，概不例外。 虽然那23个问题是归纳总结出来的，并不全是原创，但是其中有不少问题是可以上升到哲学的高度，引起深度思考的。可能大多数人都会觉得希尔伯特是进不到这层楼的，我们知道提出问题的人和解决问题的人是一样伟大的，何况他提出的问题是如此之多，基于这点，个人觉得应该让希尔伯特跨进这层楼的门槛里。 看完这位希尔伯特的成就，你可能会觉得对你的世界观并没有产生任何影响。确实如此，他提出的问题不是用来影响你的，而是用来影响其他大科学家和大哲的，下面再来说说另一位对他提出的23个问题中的第2个问题有杰出贡献的大哲，你就会感觉到大哲们的成果的威力了。 2、哥德尔 ...

继续 ›

分类: 其他

程序员的十层楼(8~9层）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 二月 4, 2009 在 3:05 下午
评论 (38)

第1～3层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1071/ 第4～5层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1073/ 第6～7层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1077/ 第8层 科学家 科学家向来都是一个神圣的称号，因此我把他放在了“大师”之上。要成为科学家，你的贡献必须超越大师，不妨随便举一些例子。 如果你象Dijkstra一样设计了ALGOL语言，提出了程序设计的三种基本结构：顺序、选择、循环，那么你可以爬到第8层楼来。顺便说一下，即使抛开这个成果，Dijkstra凭他的PV操作和信号量概念的提出，同样可以进到这层楼。 如果你象Don Knuth一样，是数据结构与算法这门学科的重要奠基者，你也可以进到这层楼来。当然，数据结构和算法这门学科不是某个人开创的，是许多大师和科学家集体开创的。 如果你象巴科斯一样发明了Fortran语言，并提出了巴科斯范式，对高级程序语言的发展起了重要作用，你也可以进到这层楼来。 或者你象Ken Thompson、Dennis Ritchie一样发明了Unix操作系统和功能强大、高效、灵活、表达力强的C语言，对操作系统理论和高级编程语言均作出重大贡献，那么你也可以进到这层楼来。 或者你有Frederick ...

继续 ›

分类: 其他

程序员的十层楼（6～7层）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 二月 4, 2009 在 2:58 下午
评论 (51)

  第1～3层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1071/ 第4～5层 看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1073/ 第6层 学者 当"专家"们想继续往上一层楼爬时，他们几乎一眼就可以看到楼梯的入口，不过令他们吃惊的是，楼梯入口处竖了一道高高的门槛，上面写着"创新"二字。不幸的是，大多数人在爬到第5层楼时已经体能消耗过度，无力翻过这道门槛。 有少数体能充足者，可以轻易翻越这道门槛，但是并不意味着体力消耗过度者就无法翻越，因为你只是暂时还没有掌握恢复体能的方法而已，当掌握了恢复体能的方法，将体能恢复后，你就可以轻易地翻越这道门槛了。 怎么才能将体能恢复呢？我们的老祖宗"孔子"早就教导过我们"温故而知新"，在英文里，研究的单词是"research"，其前缀"re"和"search"分别是什么意思不用我解释吧。或许有些人觉得"温故而知新"和"research"有些抽象，不好理解，我再给打个简单的比方，比如你在爬一座高山，爬了半天，中途体力不支，怎么恢复体力呢？自然是休息一下，重新进食一些食物，体力很快就可以得到恢复。 由此可知，对体能消耗过度者，休息＋重新进食通常是恢复体能的最佳选择。可惜的是，国内的老板们并不懂得这点，他们的公司里不仅连正常国家规定的休息时间都不给足，有些公司甚至有员工"过劳死"出现。所以国内能翻越"创新"这道门槛的人是"少之又少"，和西方比起来估计是数量级的差别。 再说说重新进食的问题，这个重新进食是有讲究的，需要进食一些基础性易消化的简单食物，不能进食山珍海味级的复杂食物，否则很难快速吸收。以查找为例，并不是去天天盯着那些复杂的查找结构和算法进行研究，你需要做的是将二分查找、哈希查找、普通二叉树查找等基础性的知识好好地复习几遍。 以哈希查找为例，首先你需要去将各种冲突解决方法如链式结构、二次哈希等编写一遍，再试试不同种类的哈希函数，然后还需要试试在硬盘中如何实现哈希查找，并考虑数据从硬盘读到内存后，如何组织硬盘中的数据才能快速地在内存中构建出哈希表来，...，这样你可能需要将一个哈希表写上十几个不同的版本，并比较各个版本的性能、功能方面的区别和适用范围。 总之，对任何一种简单的东西，你需要考虑各种各样的需求，以需求来驱动研究。最后你将各种最基础性的查找结构和算法都了然于胸后，或许某天你再看其他更复杂的查找算法，或者你在散步时，脑袋里灵光一现，突然间就发现了更好的方法，也就从专家晋升为"学者"了。 学者所做的事情，通常都是在前人的基础上，进行一些小的优化和改进，例如别人发明了链式基数排序的方法，你第1个发现使用一定的方法，可以用数组替代链表进行基数排序，性能还能得到进一步提高。 由于学者需要的只是一些小的优化改进，因此中国还是有一定数量的学者。不过和国外的数量比起来，估计少了一个数量级而已。 也许有人会觉得现在中国许多公司申请专利的数量达到甚至超过西方发达国家了，我们的学者数量应该不会比他们少多少。因此，有必要把专利和这里说的创新的区别解释一下。 所谓专利者，只要是以前没有的，新的东西，都可以申请专利；甚至是以前有的东西，你把他用到了一个新的领域的产品里去，也可以申请专利。比如你在房子里造一个水泥柱子，只要以前没有人就这件事申请专利，那么你就可以申请专利，并且下次你把水泥柱子挪一个位置，又可以申请一个新的专利；或者你在一个柜子上打上几个孔，下次又把孔的位置改一改，...，均可申请专利。 这层楼里所说的创新，是指学术层面的创新，是基础研究方面的创新，和专利的概念是完全不同的，难度也是完全不同的。你即使申请了一万个象那种打孔一类的专利，加起来也够不到这层楼里的一个创新。 当你爬到第6层楼时，你也许会有一种突破极限的快感，因为你终于把那道高高的写着"创新"二字的门槛给翻过去了，实现了"0"的突破。这时，你也许有一种"独上高楼，欲望尽天涯路"的感觉，但是很快你会发现看到的都是比较近的路，远处的路根本看不清楚。如果你还有足够的体力的话，你会想爬到更高一层的楼层去。 第7层 大师 从第6层楼爬到第7层楼，并没有多少捷径可走，主要看你有没有足够的能量。你如果能象Hoare一样设计出一个快速排序的算法；或者象Eugene W. Myers一样设计出了一个用编辑图的最短路径模型来解决diff问题的算法；或者象M.J.D. Powell一样提出了一个能够处理非线性规划问题的SQP方法；或者你发现基于比较的排序算法，它的复杂度下界为O(NLogN)；或者你发现用栈可以将递归的算法变成非递归的；或者你设计出一个红黑树或者AVL树之类的查找结构；或者你设计出一个象C++或Java一样的语言；或者你发明了UML；...，你就爬到了第7层，晋升为"大师"了。 上面举的这些例子中，其中有些人站的楼层比这层高，这里只是为了形象说明而举例他们的某个成就。从上面列出的一些大师的贡献可以看出，成为大师必须要有较大的贡献。首先解决问题必须是比较重要的，其次你要比前辈们在某方面有一个较大的提高，或者你解决的是一个全新的以前没有解决过的问题；最重要的是，主要的思路和方法必须是你自己提供的，不再是在别人的思路基础上进行的优化和改进。 看了上面这些要求，如果能量不够的话，你也许会觉得有些困难，所以不是每个人都能成为"大师"的。中国软件业里能称得上是"大师"的人，用屈指可数来形容，估计是绰绰有余。值得一提得是，国外的"大师"就象我们的"大牛"一样满天飞的多。 我把我猜测本国有可能进到这层楼的大师列一下，以起个抛砖引玉的作用。汉王的"手写识别"技术由于是完全保密的，不知道它里面用了什么思想，原创思想占的比重有多少，因此不知道该把它划到这层楼还是更高一层楼去。原山东大学王小云教授破解DES和MD5算法时，用到的方法不知道是不是完全原创的，如果是的话也可进到这层楼来。 陈景润虽然没有彻底解决哥德巴赫猜想，但他在解决问题时所用的方法是创新的，因此也可以进到这层楼来。当然，如果能彻底解决哥德巴赫猜想，那么可以算到更高的楼层去。 求伯君和王志东等大牛们，他们在做WPS和表格处理之类的软件时，不知是否有较大的原创算法在里面，如果有的话就算我错把他们划到了大牛层。由于所学有限，不知道国内还有那些人能够得上"大师"的级别，或许有少量做研究的教授、院士们，可以达到这个级别，有知道的不妨回个帖子晾一晾。 鉴于"大师"这个称号的光环效应，相信有不少人梦想着成为"大师"。或许你看了前面举的一些大师的例子，你会觉得要成为大师非常困难。不妨说一下，现在有一条通往"大师"之路的捷径打开了，那就是多核计算领域，有大量的处女地等待大家去挖掘。 以前在单核时代开发的各种算法，现在都需要改写成并行的。数据结构与算法、图像处理、数值计算、操作系统、编译器、测试调试等各个领域，都存在大量的机会，可以让你进到这层楼来，甚至有可能让你进到更高一层楼去。 下一篇文章请看：程序员的十层楼(8~9层）

继续 ›

分类: 其他

程序员的十层楼（4~5层）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 二月 4, 2009 在 2:38 下午
评论 (33)

第1～3层，请看这里：http://software.intel.com/zh-cn/blogs/2009/02/04/1071/ 第4层 大牛 从第3层爬到第4层可不像上面说过的那几层一样容易，要成为大牛的话，你必须要能做牛人们做不了的事情，解决牛人们解决不了问题。比如牛人们通常都不懂写操作系统，不会写编译器，不懂得TCP/IP协议的底层实现，如果你有能力将其中的任何一个实现得象模象样的话，那么你就从牛人升级为"大牛"了。 当然，由于各个专业领域的差别，这里举操作系统、编译器、TCP/IP协议只是作为例子，并不代表成为"大牛"一定需要掌握这些知识，以时下热门的多核编程来说，如果你能比牛人们更深入地掌握其中的各种思想原理，能更加自如的运用，并有能力去实现一个象开源项目TBB库一样的东西，也可以成为"大牛"，又或者你能写出一个类似Apache一样的服务器，或者写出一个数据库，都可以成为"大牛"。 要成为"大牛"并不是一件简单的事情，需要付出比牛人们多得多的努力，一般来说，至少要看过200~400本左右的专业书籍并好好掌握它，除此之外，还得经常关注网络和期刊杂志上的各种最新信息。 当"牛人"晋升为"大牛"，让"牛人们"发现有比他们更牛的人时，对"牛人"们的心灵的震撼是可想而知的。由于牛人们的数量庞大，并且牛人对大虾和菜鸟阶层有言传身教的影响，所以大牛们通常能获得非常高的社会知名度，几乎可以用"引无数菜鸟、大虾、牛人竞折腰"来形容，看看前面提过的Linus Torvalds等大牛，应该知道此言不虚。 虽然成为"大牛"的条件看起来似乎很高似的，但是这层楼并不是很难爬的一层，只要通过一定的努力，素质不是很差，还是有许多"牛人"可以爬到这一层的。由此可知，"大牛"这个楼层的人数其实并不像想像的那么少，例如比尔·盖茨之类的人好像也是属于这一层的。 由于"大牛"这层的人数不少，所以也很难统计除到底是中国的"大牛"数量多还是西方的大牛数量多？我估计应该是个旗鼓相当的数量，或者中国的"大牛"们会更多一些。 看到这里，可能会有很多人会以为我在这里说瞎话，Linus Torvalds写出了著名的Linux操作系统，我国并没有人写出过类似的东西啊，我国的"大牛"怎么能和西方的比呢? 不知大家注意到没有，Linus Torvalds只是写出了一个"象模象样"的操作系统雏形，Linux后来真正发展成闻名全球的开源操作系统期间，完全是因为许多支持开源的商业公司如IBM等，派出了许多比Linus Torvalds更高楼层的幕后英雄在里面把它开发出来的。 可能有些菜鸟认为Linus Torvalds是程序员中的上帝，不妨说个小故事： Linus，Richard Stallman和Don Knuth（高德纳）一同参加一个会议。 Linus ...

继续 ›

分类: 其他

程序员的十层楼(1~3层)

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 二月 4, 2009 在 2:25 下午
评论 (95)

程序员的十层楼 自西方文艺复兴以来，中国在自然科学方面落后西方很多，软件领域也不例外。当然现在中国的许多程序员们对此可能有许多不同的意见，有些人认为中国的程序员水平远落后于西方，有些则认为中国的程序员个人能力并不比西方的程序员差，只是整个软件产业落后而已。 那么，到底中国的程序员水平比西方程序员水平差，还是中国有许多优秀的程序员达到或超过了西方程序员同等水平呢？要解决这个问题，必须先知道程序员有多少种技术层级，每个层级需要什么样的技术水平，然后再比较中国和西方在各个技术层级的人数，就可以知道到底有没有差距，差距有多大。 当然，对于如何划分程序员的技术层级，不同公司或不同人会有不同的划分标准，下面的划分仅代表个人的观点，如有不当之处，还请砸板砖予以纠正。 第1层  菜鸟 第1层楼属于地板层，迈进这层楼的门槛是很低的。基本上懂计算机的基本操作，了解计算机专业的一些基础知识，掌握一门基本的编程语言如C/C++，或者Java，或者JavaScript，...，均可入门迈进这层。 在这层上，中国有着绝对的优势，除了从计算机专业毕业的众多人数外，还有大量的通信、自动化、数学等相关专业的人士进入这一行，此外还有众多的其他专业转行的人士，人数绝对比西方多出甚多。并且还有一个优势就是我们这层人员的平均智商比西方肯定高。 没有多少人愿意一辈子做菜鸟，因为做"菜鸟"的滋味实在是不咋的，整天被老大们吆喝着去装装机器，搭建一下测试环境，或者对照着别人写好的测试用例做一些黑盒测试，好一点的可以被安排去写一点测试代码。当然如果运气"好"的话，碰到了国内的一些作坊式的公司，也有机会去写一些正式的代码。 所以，菜鸟们总是在努力学习，希望爬更高的一层楼去。 第2层 大虾 从第1层爬到第2层相对容易一些，以C/C++程序员为例，只要熟练掌握C/C++编程语言，掌握C标准库和常用的各种数据结构算法，掌握STL的基本实现和使用方法，掌握多线程编程基础知识，掌握一种开发环境，再对各种操作系统的API都去使用一下，搞网络编程的当然对socket编程要好好掌握一下，然后再学习一些面向对象的设计知识和设计模式等，学习一些测试、软件工程和质量控制的基本知识，大部分人经过2～3年的努力，都可以爬到第2层，晋升为"大虾"。 中国的"大虾"数量和"菜鸟"数量估计不会少多少，所以这层上仍然远领先于西方。 大虾们通常还是有些自知之明，知道自己只能实现一些简单的功能，做不了大的东西，有时候还会遇到一些疑难问题给卡住，所以他们对那些大牛级的人物通常是非常崇拜的，国外的如Robert C. Martin、Linus Torvalds，国内的如求伯君、王志东等通常是他们崇拜的对象。其中的有些人希望有一天也能达到这些大牛级人物的水平，所以他们继续往楼上爬去。 第3层 牛人 由于"大虾"们经常被一些疑难问题给卡住，所以有了"大虾"们只好继续学习，他们需要将原来所学的知识进一步熟练掌握，比如以熟练掌握C++编程语言为例，除了学一些基础性的C++书籍如《C++ Primer》，《Effective C++》，《Think in ...

继续 ›

分类: 其他

多核分布式队列的实现：“偷”与“自私”的运用（1）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 一月 23, 2009 在 11:15 上午
评论 (8)

多核分布式队列的实现："偷"与"自私"的运用 在讨论本文的正题前，不得不先说一些闲话，嫌哆嗦者可以跳过"前言"部分不读。 1. 前言 在发表了"老子是伟大的多核计算科学家" （链接：http://blog.csdn.net/drzhouweiming/archive/2008/11/07/3246254.aspx，为叙述方便，后面将这篇文章简称为"老子"）一文后，褒扬者有许多，但是也引来了许多板砖。当然大部分板砖都只是泛泛的批评，没有任何内容。不过有些人觉得似乎有些牵强附会，倒是引起了我的注意，确实这类文章可能确实容易给人牵强附会的感觉。 需要说明的是，本人并没有觉得它是牵强附会的。首先申明一下，我并不是研究哲学的，也没有详细研究过老子的《道德经》，但是我在设计多核算法时，确实受到了《道德经》中的思想启发。举两个例子如下： 第一个例子是在设计多核查找算法（链接：http://blog.csdn.net/drzhouweiming/archive/2008/10/27/3159501.aspx）时，最初我是用AVL树作为多级查找结构的子查找结构的，当时觉得AVL树肯定会比数组更好，因为对稍微大一点的数组进行插入删除的效率非常低，只能用在很少数据的表上，不能对大量数据的表进行管理。记得有一天看电视时，凑巧看到在讲老子的小国寡民思想，谈到了结绳而治的问题，受此启发，对AVL树比数组更好的想法产生了怀疑，于是试着将查找子结构改为用最原始的数组来实现，结果发现即使对上百万个规模的数据的表进行处理，综合性能也比用AVL树更好。 第二个例子是在设计多核分布式内存管理算法时，采用了"抢"的方法，使得分配和释放内存不需要使用锁。这也是受《道德经》中的"无为"及"大道自然"的思想影响，因为之前已经发现"贪心"、"自私"、"偷"这几种人性的本能在算法中得到广泛使用，既然连"偷"都在多核算法中得到使用，那么它的孪生兄弟"抢"应该也可以在多核算法中得到使用，本着此思想，后来终于发现可以将"抢"的思想用在多核分布式内存管理算法中，大大提高共享内存分配和释放的效率。 对老子《道德经》的解释，历来有各种不同的解释。既然有些人只是在理论层面都可以进行解释，我现在把它的部分思想用到了具体的多核算法中，变成了在计算机里可以实际运行的程序，对它解释一下就变成了牵强附会的话，那么这种牵强附会我想越多越好。 闲话少叙，言归正传，下面就来谈一个使用"偷"与"自私"的方法实现的多核分布式队列的详细实例，以看看如何将看似泛泛而谈的思想变成可以运行的程序的。 2. 分布式队列的基本概念 在"多核编程中的条件同步模式"（链接： http://software.intel.com/zh-cn/blogs/2009/01/14/845/）这篇文章中，讲到了如何减少共享队列中的锁的使用次数的具体方法，在它的基础上，可以构造出一个高效的队列池。 如果采用线程分组竞争模式（参见"多核编程中的线程分组竞争模式，链接：http://blog.csdn.net/drzhouweiming/archive/2007/07/10/1684753.aspx）来实现队列池，那么每组线程对应于队列池中的一个子队列，当某个线程在操作自己所属的子队列时，如果子队列为空却进行出队操作，那么此时可以从其他组线程所属的子队列中进行出队操作，这也就是"老子"一文中所说的"偷"的方法的使用。 有没有更好的方法进一步减少同步或者锁的使用呢？答案是有的。偷别人的东西总不如掏自己口袋里的东西来得方便，之所以需要"偷"，乃是因为自己口袋里空空。如果大家都富裕了，口袋都鼓鼓的了，自然不需要去"偷"别人的了。 当然在计算机中，"富裕"的办法就是给每个线程赋予一个私有队列，这样每个线程可以大部分时间都操作自己私有队列，不需要同步操作，大大提高效率，这也就是"老子"一文中所说的"自私"方法的使用。 基于"偷"和"自私"两种方法，就可以设计出一个适应多核环境的分布式队列。在分布式队列中，每个操作队列的线程都有一个私有队列，另外为了解决私有队列间的负载均衡问题，还需要一个队列池来维护数据的负载均衡。 分布式队列的数据结构示意图如下：   图1：分布式队列数据结构示意图 有了上面的数据结构图，具体来实现就可以分为两个步骤： 1、 实现一个队列池 2、 给每个线程赋予一个私有队列 队列池的实现可以采用前面讲过方法实现，这里就不详述了，下面主要谈谈如何给每个线程赋予一个私有队列（也称作本地化队列）的详细实现方法。 下一篇文章请看：多核分布式队列的实现：“偷”与“自私”的运用（2）

继续 ›

分类: 其他, 博客征文专栏, 并行计算

多核分布式队列的实现：“偷”与“自私”的运用（2）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 一月 23, 2009 在 11:14 上午
评论 (0)

多核分布式队列的实现："偷"与"自私"的运用  上一篇文章请看：多核分布式队列的实现：“偷”与“自私”的运用（1） 3. 本地化队列的实现思路 要给线程指定一个本地化队列，通常的做法是先将创建好的队列放入一个数组中，然后给线程编号，从0开始进行编号，编号为0的线程对应于数组下标为0位置上存放的队列，编号为1的线程对应于数组下标为1位置上存放的队列，...。 每个线程要获取自己的本地化队列时，只需要先获取线程编号，然后就可以通过线程编号去访问对应的队列，由于每个线程的编号都不相同，因此每个线程访问的队列都不相同，即每个队列只有一个线程访问它，这样就可以实现每个线程的本地化队列。 那么如何给线程编号从0开始编号呢，操作系统并没有直接提供这种功能。即使操作系统提供了线程从0开始编号的功能也没有用，因为并不一定所有的线程都会访问分布式队列。例如有8个线程，其中编号为0，3，5，7的线程会访问分布式队列，那么在创建分布式队列时，就需要创建8个本地队列，否则线程编号将无法和存放队列的数组下标对应起来。 看到这里，目标已经很明确了，那就是要给所有访问分布式队列的线程从0开始依次编号。比如有N个线程要访问分布式队列，那么需要给这N个线程依次编号为0，1，...N-1。下面就来讨论如何给线程编号的问题。 4. 给线程编号的方法 在操作系统中，通常提供了线程本地存储的API，通过API可以给每个线程设定一个数据（可以是指针，也可以是一个整数），同时也可以通过API来取出当前线程设置的那个数据。比如给一个线程A设定一个整数0，那么线程A执行的任何地方都可以调用相应的API获取到整数0，这样就可以在程序的任何地获取到线程A的编号为0。 在Windows系列操作系统中，提供了Tls_Alloc()，Tls_SetValue()，Tls_GetValue()，Tls_Free()这几个函数来实现线程本地存储操作。 pthread中，可以通过pthread_key_create(), pthread_setspecific(), pthread_getspecific()等函数来实现线程本地存储操作，其中pthread_create_key()和Tls_Alloc()功能相同，只是参数有所不同，Tls_SetValue()和pthread_setspecific()功能等价，Tls_GetValue()和pthread_getspecific()功能等价。 下面演示一下TlsAlloc()，Tls_SetValue()，Tls_GetValue()，Tls_Free()这几个函数的基本用法。 DWORD g_dwTlsIndex; LONG volatile g_dwThreadId = 0;   int ...

继续 ›

分类: 其他, 博客征文专栏, 并行计算

多核分布式队列的实现：“偷”与“自私”的运用（3）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 一月 23, 2009 在 11:14 上午
评论 (0)

前两篇文章请看： 1）多核分布式队列的实现：“偷”与“自私”的运用（1） 2）多核分布式队列的实现：“偷”与“自私”的运用（2）   5. 进队出队操作 分布式队列的进队出队操作根据不同应用类型具有不同的操作策略，但是不论何种类型的操作，其基本思想必须以本地队列操作最大化作为前提条件。下面给出分布式队列中常用的进队出队操作类型。 1)        出队操作 出队操作比较简单，通常都是先从本地队列中获取数据，如果本地队列为空，那么再从共享队列池中获取数据。 由于先从本地队列中获取数据，因此有助于实现本地队列操作的最大化。 出队操作的流程图如下：   图2：分布式队列的出队操作流程图 2)        进队操作 进队操作相比于出队操作要复杂一些，常用的操作策略有以下两种： 策略1：先判断本地队列是否为空，如果为空则将数据放入本地队列中；然后判断共享队列池中是否满，如果满则将数据放入本地队列中，否则放入共享队列中。 在这种策略的进队操作中，首先考虑的是本地队列的操作问题，本地队列至少要有一个数据，然后考虑的问题是负载平衡问题，共享队列池中的数据主要用于各线程间数据的负载均衡。共享队列池的大小必须做出限制，否则数据全部都进到共享队列池中去了，本地队列未得到有效使用。 共享队列池到底设定多大，才能使得本地队列操作最大化与负载平衡问题之间取得一个好的均衡，是在实际情况中需要考虑的问题，最好通过测试程序性能去获取一个合适的值。 进队操作策略1的操作流程图如下：   图3：分布式队列的进队操作策略1的流程图 策略2：当有多个数据需要进队时，先放入一些数据到本地队列中，然后剩下的数据再放入共享队列池中，如果队列池满的话，则仍然放入本地队列中。 本策略中，通常是进队的线程马上自己要从队列中获取数据，因此要先放入一些数据到自己的本地队列中，保证下次从队列中取数据一定是从本地队列中获取，可以大大提高本地化队列操作的频率，有效降低共享队列池的操作，大大减少了同步操作。 进队操作策略2的操作流程图如下：   图4：分布式队列的进队操作策略2的流程图 有了进队操作和出队操作的详细流程后，实现分布式队列的具体代码就容易多了。下面就来实现CDistributedQueue类的各个操作的详细源代码。   下一篇文章请看：多核分布式队列的实现：“偷”与“自私”的运用（4）

继续 ›

分类: 其他, 博客征文专栏, 并行计算

多核分布式队列的实现：“偷”与“自私”的运用（4）

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 一月 23, 2009 在 11:14 上午
评论 (2)

前三篇文章请看： 1）多核分布式队列的实现：“偷”与“自私”的运用（1） 2）多核分布式队列的实现：“偷”与“自私”的运用（2） 3）多核分布式队列的实现：“偷”与“自私”的运用（3） 6. CDistributedQueue 源代码 在设计CDistributeQueue类时，通常有两种方案值得考虑： 1、 本地队列预先创建好，当有线程访问时就可以直接根据线程编号去访问对应的本地队列。 2、 不预先创建本地队列，当线程第一次访问分布式队列时，由于获取不到线程编号，由此可以断定本线程是第1次访问分布式队列，此时才创建本地队列。 方案1和方案2可以说各有优缺点。方案1中，在事先不知道有多少线程会访问分布式队列的情况下，预先创建好本地队列会造成程序初始化时间过长，并且可能有一些创建好的队列得不到使用。 方案2中，采用线程访问分布式队列时才创建本地队列，初始化时比较简单，并且不会造成多创建了本地队列的情况。缺点是编程时，队列的操作代码会变复杂一些，效率会有所降低。 下面的代码中，给出的是方案2的实现。 1) 类的原型定义和成员函数 //获取线程Id回调函数定义 typedef int (*GetThreadIdFunc)(void *pArg);   template <class ...

继续 ›

分类: 其他, 博客征文专栏, 并行计算

多核编程中的条件同步模式

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 一月 14, 2009 在 2:00 下午
评论 (39)

多核编程中的条件同步模式   在多线程编程中，当对共享资源进行操作时，需要使用同步（通常是锁或原子操作）来进行保护，以避免数据竞争问题。不幸的是，同步操作的开销非常大，比如对一个整数变量进行加法操作，那么同步操作的开销是加法操作的上百倍以上。 有没有办法可以减少这种同步操作的开销呢？如果能设计出更快的锁或更快的原子操作来，那么这种开销自然就减少了。以目前的技术来看，最快速的原子操作耗时也是普通加法操作的上百倍，所以从这方面着手是非常困难的。 那么能不能从软件算法的角度来减少同步操作的开销呢？答案是当然可以，基本思想是减少使用同步的次数，比如原来要使用同步1000次，现在改为在满足一定条件下才使用同步，只需要10次，那么同步的开销平摊下来就被减少了100倍，效率大大提高了。下面先来看一个共享队列例子。 一个普通的共享队列通常都是使用锁来实现，当然也有用CAS原子操作来实现的，这里只讨论用锁来实现的共享队列。 在有锁保护的共享队列中，在队列的进队和出队操作时，通常都是使用锁来进行保护的，一个典型的使用锁保护的出队操作伪代码如下：        template class <T>        Locked_DeQueue(T &data)        {               Lock();               DeQueue(data);  //调用串行的出队操作               ...

继续 ›

分类: 其他, 博客征文专栏, 并行计算

多核编程的四层境界

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 一月 14, 2009 在 1:58 下午
评论 (22)

多核编程的四层境界   版权申明：这篇文章可以被自由转载，如果修改其中的内容需征得作者同意。   自发表“老子是伟大的多核计算科学家”（欲看此文，请点这里）一文来，收到许多网友的强烈反响，褒扬者有之，砸板砖者亦有之。不过板砖数量倒是在我的意料之中，凡是跟哲学或者说是玄学的东西沾上边的，总会招来一阵口舌之争。虽然砸板砖者也没有说出任何反驳的道理来，但是并不代表那篇文章就很完美，没有不足的地方。实际上那篇文章中只涉及了多核编程的一个层面的思想，还有另外三层思想没有被提及，这也许可以算作是那篇文章的不足之处吧。为弥补其不足之处，下面从四个层面来阐述多核编程的基本思想。 第一层  先天·方法·策略层 第一层的基本思想就是“老子是伟大的多核计算科学家”一文中所提及的几个基本思想：“贪心”、“自私”、“偷”等。这些东西是先天存在的，是人类的一种本能，它又可以看作是方法、策略，因此把这层叫作“先天·方法·策略层”。 先天的方法策略并不限于“贪心”、“自私”、“偷”这三种，去年的SD大会上，我讲过一个基于抢夺的分布式内存管理算法，说明“抢”也是一种先天的方法策略。所谓： “人之初，性本贪，性自私，性喜偷，性喜抢。” 为避免误解，这里先说明一下，这里所说的“偷”、“抢”和通常意义的偷、抢并不完全相同。“偷”和道家意义上的偷是同一个含义，即“不与取”之意；“抢”则是取“不归还”之意。 昔范蠡云：“且夫天舆弗取，反受其咎”。既然上天给了我们这么多好的方法策略，不用它的话显然是一种糟蹋。在多核编程中如何使用这些策略来进行编程，开源项目TBB中可以找到详细的代码例子。 第二层  目标·需求·评价层 先天的方法策略，虽然看似简单，但要用好它并不是一件容易的事情。自私、贪心、偷、抢等先天方法既可以用来做好事，也可以用来做坏事。这就牵涉到如何评价是否用好了这些先天方法策略的问题，也就是第二层目标·需求·评价层所需要解决的问题。 并不能为了使用先天方法策略而使用它，而是用它来满足我们的需求，到达一定的目标。那么这个需求和目标是什么呢？ 在这里不想对一般的需求进行分析，只分析优化方面的需求。要达到优化，可以理解为各种资源的有效利用，可能有很多人已经有这方面的理解【1】。这些资源可以分为以下几个方面： 1）时间资源， 时间资源指的就是时间，比如一段程序或算法需要运行多长时间。 2）空间资源，如内存、硬盘、网络、各种IO设备资源等均属于空间资源。 3）计算资源，如CPU、GPU、各种板卡上的处理器等均属于计算资源。 4）能源资源，通常指的是电能的消耗量，由于全球变软，环保问题的日益重要，这个在以往被忽视的资源也变得重要起来。 如何有效利用上述资源，并在各种资源利用间取得均衡，是制定目标和需求的基础，也是评价程序或算法优化程度的基础。 第三层  本质·根源·保障层 资源的有效利用，可不是一件简单的事情。在单核时代，许多程序员已有时间资源和空间资源的利用及均衡方面的丰富经验，那时几乎不用考虑计算资源的利用问题，因为处理器只有一个。 然而，在多核系统中，计算资源的利用成了头号问题，多个处理器的使用，使得程序员必须考虑如何将程序在各个处理器上并行地执行，这就牵涉到一个负载均衡问题。 负载均衡问题历来属于难题，由于客观上存在大量的共享资源，各种不同的共享资源情况复杂，并不能简单地将负载平均一下就摊到各个CPU核上去执行。那么用什么来保障负载平衡呢？如何去达到资源有效利用的终极目标需求呢？ 要保障目标需求的实现，其核心就是公平、正义问题。当然，对公平、正义这两个词的理解，现实情况中存在多种解释，这里采用更广义的解释，凡是可从正确的前提通过逻辑推导出来的定义，均视做正义，例如自然科学中的所有公理、定理及推论，均属于正义。在人类社会中，一些公认的道德标准、法律条文，也属于正义。 以动态偷取的调度算法为例，一般都是设计成每个线程一次偷取一个任务，实际上已经隐含地使用公平正义对偷取的数量做了限制，倘若不如此，任由一个线程一次将队列中所有任务都偷走，那么其他线程就偷不到任务了，这样就会出现负载不均衡，无法有效地利用多个处理器的计算资源。 再比如基于抢夺的内存分配算法，每个线程使用了共享内存后，它并不返回给它的属主线程，而是据为己有，这样时间一长，必然有某些线程占有了过多的内存资源。为了解决这个问题，解决方法就是每次抢完后，都需要判断一下自己占有的内存数量是否过多，过多的话则主动将一部分内存归返给公共内存池，从而实现负载均衡。可以看出基于抢夺的内存分配算法中也使用了公平、正义以确保负载均衡。 公平、正义问题可以说是算法之本，全局效率之源。为什么这么说呢？不妨看看现在美国发生的次贷危机，其根本原因是由于银行将贷款发放给无偿返能力的客户所造成的。从公平、正义的角度看，实质上是银行为了自身的贪心、自私，违反了基本的公平、正义问题。次贷危机的后果，无需我多言，大家均已看到。可见，没有公平正义，贪心、自私等先天方法策略必然会被滥用，其结果必然导致全局的不优。 由此可见，公平、正义是保障贪心、自私、偷、抢等先天方法策略得以正确使用的前提条件。本层名称中的本质、根源、保障，说的就是公平、正义。 需要提及的是，在人类社会的现实中，由于人是有情感的，公平正义在执行中总会存在偏差，这时就需要仁爱来弥补其不足，这也许是儒家思想能够流传两千多年而不灭的根本原因。当然，如果把仁爱思想也看作是道德标准的一部分的话，按照前面给出的正义的定义，其实仁爱也属于正义的范畴。 第四层  算法·实现·执行层 通过上面三个层面的阐述，可以知道先天的方法策略是实现优化的基本手段，资源有效利用则是实现优化的目标需求及评价条件，公平、正义则是保障先天的方法策略合理使用的前提条件。是不是有了这几样东西就可以做到达成优化的最终结果呢？ 答案是“非也”。如果上面那几个东西就可以达成优化的结果，那么从街上随便抓个人恐怕都可以写出很好的多核程序来了，还要程序员干嘛，还要去学习多核编程的各种模式、技巧及算法干嘛？ 就像学了牛顿力学一样，有些人可以设计出摩天大厦，造出各种机械，有些人却啥也做不了。何也？运用好坏之不同也。要写出好的多核程序，同样牵涉导如何运用上面三层中的基本原理思想方法的问题，而要用好这些基本原理思想，更多的还是要靠程序员自身的知识及能力，最终依赖于算法或程序的具体实现。就像有了道家，儒家，却仍然少不了法家、农家、医家等各个领域的诸子百家。 怎样写出好的多核算法或程序来？ “好好学习、天天向上”是也【2】。     备注： 【1】 08年深秋，与孟岩先生在上海相聚，一起聊到对多核计算的理解时，他谈起了各种资源如CPU资源的有效利用问题。 【2】 关于学习写多核程序，提供一些学习材料给大家参考如下。 1）  TBB开源项目： ...

继续 ›

分类: 其他, 博客征文专栏, 并行计算

“老子”是伟大的多核计算科学家

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 十一月 10, 2008 在 12:26 下午
评论 (91)

“老子”是伟大的多核计算科学家   道家的思想可谓博大精深，“老子”的《道德经》成为翻译为外国文字最多的中国书籍，同时也是世界上翻译成外国文字第二多的书籍，仅次于圣经。要知道，《圣经》子所以成为翻译成外国文字第一多的书籍，是因为有10多亿的基督教徒。不要说在国外，即使在中国国内，现在也没有多少道教徒，道家的思想却能在世界上流传如此之广，实在让人觉得是“玄之又玄”。   也许有人会纳闷，“老子”为道家思想的创始人，生活于春秋末期，那时不要说计算机，连能用来进行手工计算的草稿纸都没有发明，怎么会成为了伟大的多核计算科学家呢？这该不会是瞎忽悠人吧。   我要说的是，这决不是瞎忽悠人。虽然“老子”所处的时代没有计算机，但是它提出的道家思想中，蕴含了现代多核计算的一些基本原理和思想在内。从这个角度讲，“老子”确实是一位伟大的多核计算科学家。   道家的思想中，无非就是“无为”、“小国寡民”、“大智若愚”、“大巧若拙”、“大音希声”、信言不美、美言不信、…等各种思想。这些思想普遍都认为是一些哲学思想，这和作为科学的多核计算看上去好像是风牛马不及的事啊！老子又怎么能成为科学家呢？难道道家思想里真的蕴含了我们所不知道的多核计算原理和思想在里面？   没错，道家思想里确实蕴含了现代多核计算的原理和思想在内。当然，这不是说白话，得拿出实际证据来证明它才行。下面就以一些多核计算方面的实例来论证道家思想中蕴含的深刻思想，从中也许可以窥见它的“众妙之门”中的冰山一角。   小国寡民与多核计算 不妨先从“小国寡民”思想说起，“小国寡民”历来被看成是近似乌托帮式的无法实现的理想，在人类社会史中，好像还没有见过那朝那代实现过这个理想。更有人认为这是一个不切实际的想法，甚至认为是错误的思想。可喜的是，这个理想不仅非常正确，而且现在在多核计算中变成了现实，也就是说它得到了科学的证实。下面以多核中查找设计思想和“小国寡民”思想来作一番比较，以窥其中的奥妙。   “多核查找－顺序查找也疯狂”一文介绍了多核查找设计的基本思想，其基本思路是为了避免其中式锁竞争导致的串行化执行，必须将一个大的查找数据结构拆分成多个独立的小的子数据结构，然后给每个小的子数据结构加一把锁，这个当多个线程访问不同的子数据结构时，就不会出现锁竞争现象。“小国寡民”思想是在一个大国中，许多分解成许多独立的小国，这可以说和多核中查找设计的思路是一模一样的。   不妨再回顾一下《道德经》中第八十章中关于小国寡民的原文描述：   “小国寡民；使有什伯之器，而不用；使民重死，而不远徙；虽有舟舆，无所乘之；虽有甲兵，无所陈之；使民复结绳，而用之。至治之极民各甘其食，美其服，安其俗，乐其业。邻国相望，鸡犬之声相闻，民至老死，不相往来。”   先看最后一句，“邻国相望，鸡犬之声相闻，民至老死，不相往来。”，这也就是说各个小国都是独立的，并且由于不能相往来，相当于每个小国都有一把“锁”，这和多核查找中的各个子数据结构都加了一把锁的场景是一样的。   再看第一句“小国寡民；使有什伯之器，而不用；使民重死，而不远徙；虽有舟舆，无所乘之；虽有甲兵，无所陈之；使民复结绳，而用之。”，这是最容易被人产生误解的一句话，许多人认为老子想把人民倒退回结绳而治的原始状态，是一种愚民思想。事实上这些人根本没有理解透这句话中包含的深刻思想。普通老百姓都知道有先进的工具和技术却不使用，却要倒退回结绳而治的状态是一种倒退，除非发了疯才会这么做。   “老子”是不是疯子？当然不是，不仅不是，而且老子比他同时代的人要聪明得多。正所谓“大智若愚”，老子一生中遇到过许多聪明人，包括儒家创始人孔子也曾向老子请教过，然而老子却发现没有一个人能理解他的思想，最后只好“骑青牛，出函关”。   没有人能理解是很正常的，要是那个时代就有人能理解老子的思想的话，那么本文的标题只能改为“老子是一位多核计算学科学家”，万万不敢将“伟大”二字贯在前面的。之所以没有人能理解老子的思想，正是因为其中蕴含了深刻的多核计算思想在内。这句话如果和多核的查找对照起来进行解释，我们就能发现“老子”的真正伟大之处。下面就来看看“老子”到底伟大在什么地方。   让“小国寡民”倒退回结绳而治的原始状态，反映到多核查找中就是让小的子数据结构采用最原始、最简单的数据结构和算法。最原始的数据结构是什么？当然是数组。那么在数组中如何进行查找呢？我们都知道在有序数组采用二分查找是很快速的，然而二分查找并不是最原始的查找方法，最原始的查找方法是顺序查找。也就是说在数组中不要用二分查找，只能用顺序查找。写到这里，可能就会有人有疑问了，不用高效的二分查找，却去用原始落后的顺序查找，不会有病吧，这也能体现出“老子”的伟大来？   我要说的是，用看似原始落后的东西来替代貌似先进的东西正是老子的伟大之处。为什么这样说呢？首先我们看看前提条件：“小国”，反映到多核查找中就是数组要足够小。在一个很小的数组中进行查找，比如只有少数几个数据的数组中进行查找，用顺序查找更好还是用二分查找更好呢？显然稍有编程常识的人都知道，二分查找时虽然比较次数少一些，但是由于它要计算中间数据的下标位置，需要进行加法和除以2的计算，存在计算开销，计算速度可能会比顺序查找更慢。从软件的稳定性方面来讲，编写一个顺序查找程序非常简单，不易出错，而编写一个二分查找程序就没有那么容易了。不妨看看“90％程序员写不出无BUG的二分查找程序？”这篇文章，就知道写一个二分查找程序的难度了，这么难写的程序能保证软件的稳定性吗？要知道，道家思想中还蕴含了软件中的稳定可靠性思想，有兴趣的不妨看这篇文章：“道家·老子的算法思想分析”。再者写一个复杂度高的程序，开发和测试工作量增加了多少啊。   写到这里，相信许多人已经窥破了“小国寡民”的妙处，不会再简单的认为它是一种愚民思想。我们也不得不由衷地钦佩和敬仰生活比我们早2500多年的“老子”，在那么原始的年代，“老子”就窥破了“众妙之门”，道家思想之高深，由此可见一斑。由于实在找不到什么好的用词来形容道家思想的高深和玄妙，只能慨叹一声：“道、可道，非常道”。   “无为”与多核计算   前面的“小国寡民”思想的分析，只是道家思想的冰山一角。不妨再将道家的“无为”思想和多核计算方面的实例联系起来进行分析，看看它们之间是否有什么相似之处。   道家的“无为”，追求的是一种顺应自然的思想，这种思想的详细阐述无须我多言，网上可以找出一大堆历史典籍。所谓“大道自然”，即做事需要使用自然的力量，不要去强求使用一些人为的力量。   自然赋给了我们人类什么力量呢？“贪心”、“自私”、“偷窃”等都是自然赋给人类的自然力量，当然自然还赋给了人类很多自然力量，本文只讨论“贪心”、“自私”、“偷窃”这三种自然力量。把道家的“无为”思想应用到多核计算上，也就是说要用自然的力量来设计多核算法，令人惊讶的是，“贪心”、“自私”、“偷窃”正是用来设计多核算法的最有效的自然力量。下面以一些实例来说明它。   先说说“贪心”，儒家认为“人之初，性本善”，西方观点则认为“人之初，性本恶”。其实，人之初是没有所谓善恶的，善恶是人类后天形成的东西，自然界给予人类的自然力量是没有所谓的善恶之分的。所谓善恶皆因贪，也许说成“人之初，性本贪”更恰当。所以可以认为“贪心”是自然赋给人的一种自然力量。   有过算法经验的人都知道，单核时代，“贪心”就是算法设计的一种普遍性的最优策略，特别是对于一些NP难题，往往可以用贪心策略设计出一些复杂度为O(N)的算法。当然在多核算法中，贪心策略也是必不可少，比如任务图分解与调度问题，它就是一个NP难题，处理这类问题贪心策略往往是最有效的方法。   再看看“自私”，试问有那个人能一点都不“自私”。如果去观察一下小孩子的行为，很容易得出“人之初，性自私”的结论。“自私”也是大自然赋给人类的一种自然力量。   “自私”也能用来设计多核算法吗？答案是不仅可以，而且“自私”还是一种最有效的设计多核算法的优化策略之一。这里举个简单的例子，比如多核中的内存管理，如果每个线程都带有一个私有的内存管理器的话，那么分配内存时就只要从私有的内存管理器里进行分配就可以了，不需要进行加锁解锁操作，效率能提高多少可想而知。有兴趣者不妨去试试Intel开源项目TBB中的内存管理算法，就知道使用“自私”这种自然力量来设计多核算法有多大的好处了。   最后再看看“偷窃”，这可能会让大多数人产生怀疑，“偷窃”在人类社会中历来都是被看成是非法行为，这难道也是大自然赋给人类的自然力量？试看看自人类有史以来，有那个朝代和那个时期能够根绝“偷窃”这种现象，偷窃路人之物者有之，偷窃公家财物者有之，偷情者有之，甚至窃国者亦有之，…。不难发现，这个世界中充满了“偷窃”现象。再看看小孩子的行为，当小孩子看到自己想要的东西时，马上就会去把它拿到自己手中，可以说，“人之初，性喜偷”。所以“偷窃”也是一种大自然赋给人类的自然力量。   也许有人要问了，我就姑且先承认“偷窃”是一种自然力量吧，难道“偷窃”也可以用来设计多核算法不成？这可问到点子上了，“偷窃”这种自然力量还真的在多核算法中得到了使用，在多核的动态任务调度算法中，就用到了“偷窃”的思想，有兴趣的不妨去看看Intel的开源项目TBB中的任务调度算法，里面就用到了“偷窃”的思想，当然这个任务调度算法也使用“自私”的思想。   值得一提的是，动态任务调度算法可不是一个普通的算法，这可是多核中最酷的三大算法之一（另外两个就是前面提到的多核查找和多核内存管理算法）。许多的并行算法都可以通过这个算法来实现，并且你只要写一个串行的算法，那么就可以动态任务调度的方式自动将它变成并行算法，用它可以实现并行排序，并行数值计算，并行搜索等各种并行算法。这意味着程序员不需要学习并行计算的知识就可以复用以前单核时代的串行算法，由动态任务调度器自动将其变成并行算法，酷毙了吧！同时这也意味着多核程序中，大量的并行计算都在调用动态任务调度算法，都在进行“偷窃”动作。可见多核程序中也将充满“偷窃”现象。在南怀瑾的《老子他说》一书中p90页最后一行写道，“照道家的看法，这个世界本来就是一个相互偷盗的世界，彼此相偷，互相混水摸鱼”，这和多核程序中的相互偷盗可谓不谋而合。   看了上面这些内容，可以发现，道家的“无为”思想在多核计算中已经得到了充分的实践，道家思想中确实蕴含了深刻的多核计算原理和思想。虽然如此，但是也许有人要不高兴了，上面说的这些自然力量怎么尽是一些“贪心”、“自私”、“偷窃”，看起来像是人类阴暗面的东西。难道要让每个人都去尽情地“贪心”、“自私”、“偷窃”，才算符合道家的顺其自然之理，这不是要让人学坏吗？如果这样理解的话，我想就从根本上误会了道家的“无为”思想。   道家之所以提倡“无为”的顺其自然之理，在于它认为最优的东西必然是使用自然力量才能达到，并不等于使用了自然力量就一定可以达到最优。如果“老子”说使用了自然的力量就一定最优，那么我不仅不会说“老子”伟大，而且会认为他是一个浑蛋。世界上的任何东西都有它的使用范围，即需要合理使用它。当“贪心”变成“贪婪”，“自私”变成“损人利己”的时候，自然就超越了这些自然力量的使用范围，当然没有人会认同这种现象的发生。   话要说回来，世界是复杂的，有圣人就有浑蛋，“圣人不死，大盗不已”，总会有人做“贪婪”、“损人利己”的事情而不自知，而且他们偏偏认为这是最优的。所谓“有无相生”，滥用自然力量的人，最终逃脱不了自然的惩罚。看看最近华尔街的金融海啸，也许可以有所启示。   多核编程相关文章： 1）用原子操作解决多线程退出问题 2）原子操作在多核编程中的使用 3）多核编程伪共享问题及其对策 4）多核编程锁竞争问题及其对策 5）多核分布式队列的实现：“偷”与“自私”的运用 6）多核编程中的条件同步模式 7）多核编程的四层境界 8）程序员的十层楼(1~3层) 9）多核编程文章汇总    

继续 ›

分类: 并行计算