Aiur – ZelluX 的技术博客

做一回标题党，因为这个lab太简单了 =,=

记得要在真机上做，虚拟机里测出来的结果偏差很大。

第一个问题就是unrolling/splitting一下，然后看看哪种情况下跑得最快

第二个问题貌似更简单，换下循环顺序就差不多满分了，我一开始还以为要根据cachesize分下block然后拆开来做，囧

酱紫，over

算法导论第27章，在并行处理的条件下效率很高的排序算法。

介绍
如下面左图所示，每条横线(wire)代表一个待 比较的数值，竖线(comparator)表示连接的两条横线要做一次比较，并将较小的值放在输出横线的上方，较大的放在下面。排序过程就是从左往右依次 调用各个comparator（在同一位置上的comparator可以同时做）
有图表示了四个数字3, 2, 4, 1在经过这个Sorting Network时的行为。（由于背景为深色，建议点击图片查看）

下图是一个冒泡排序的Sorting Network表示

可以看到所有的比较都没有并行，效率很低。接下来先介绍一个0-1原理，然后利用它来构造一些比较高效的网络。

性质
首先是引理27.1：
对 于输入数据A = <a_1, a_2, .., a_n>，如果某个比较网络(comparison network)的输出是B = <b_1, b_2, …, b_n>，那么对于任一单调递增的函数f，这个网络能把输入数据f(A) = <f(a_1), f(a_2), …, f(a_n)>变为f(B) = <f(b_1), f(b_2), …f(b_3)>

这个引理的证明很简单，关键在于min(f(x), f(y)) = f(min(x,y))

接下来就是0-1原理：
一个有n个输入数据的比较网络，如果它能将仅由0和1组成的序列正确的排序（这种输入共有2^n种可能），那么它也能正确的将任意数字组成的序列排序。
证明也不难，利用前面的引理反正即可得到这个定理。

双调排序
接 下来先考虑双调序列(bitonic sequence)这种特殊情况，所谓双调序列就是先单调递增，后单调递减，或者可以通过环形旋转变化出上述特性的序列，比如<1, 4, 6, 8, 3, 2>和<6, 9, 4, 2, 3, 5>都满足条件（对于后面一种序列，只要把最后的3, 5移到序列开头就行了）。
双调排序(bitonic sorter)有若干步骤，其中有一步叫做half-cleaner，每一次half-cleaner讲数据放到一个深度为1的排序网络中，第i行和第i+n/2行比较(i=1,2,..,n/2)

引理27.3：
做完上述的half-cleaner后，输出的上半部分和下半部分都保持双调的特点，而且上半部分的每个元素都不大于下半部分的任一元素。
分四种情况讨论即可。

通过递归调用half-cleaner即可完成双调队列的排序。要对n个元素进行双调排序Bitonic-Sorter(n)，首先调用Half-Cleaner(n)，将元素分成上下两部分，接着依次对这两部分执行Bitonic-Sorter(n/2)即可。
调用的深度D(n) = lgn

归并网络
书上只给出了对0-1序列排序的算法，任意数字的排序算法留作了习题。
合并网络基于这样一个事实：对于两个已经排序了的序列X = 00000111，Y = 00001111，将Y倒过来后和X拼接的结果是一个双调序列。对这个双调序列再做一次Bitonic-Sorter就能有序。
通 过修改Bitonic-Sorter方法的第一步就能实现Merger，关键在于隐式的反转输入的下半部分。Half-Cleaner方法中比较了第i和 第i+n/2两个元素，如果下半部分反转的话就相当于比较第i和第n-i+1个元素。直接继续执行Bitonic-Sorter方法即可，如下图所示。

排序网络
我们已经有了构造一个排序网络所需的工具，接下来介绍一种利用归并网络进行排序的并行版本。
大致方法和传统的归并排序类似，从最小的颗粒开始二分增长，直到整个序列有序。
这样，一共需要lg(n)次Merger，每次归并中需要做lg(i)次Sorter，排序的总深度
D(n) =
0               (n = 1)
D(n/2) + lg(n)  (n = 2^k且 k>=1)
由Master Method可推出D(n) = big-omega(lg^2(n))
也就是说理想的并行环境中，n个数可以在O(lg^2(n))时间内完成排序。

Bitonic Sorter http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm

图片来自于Wikipedia以及算法导论附图

Streamware: Programming General-Purpose Multicore Processors Using Streams

Jayanth Gummaraju, Joel Coburn, Yoshio Turner, Mendel Rosenblum

ASPLOS 08上的文章  http://portal.acm.org/citation.cfm?id=1353534.1346319

提出了一个通用的多核平台，支持Cell CUDA Brook等多种体系结构，用户只需使用这个平台统一提供的API。

另外还加入了cache hierarchy的管理，能很好的安排各级cache保存的内容，以至于某个测试结果中单核的情况下用了Streamware的程序比不用的程序跑得还快。

问题很简单，求二进制中1的个数。对于一个字节（8bit）的变量，求其二进制表示中”1″的个数，要求算法的执行效率尽可能的高。 先来看看样章上给出的几个算法：

解法一，每次除二，看是否为奇数，是的话就累计加一，最后这个结果就是二进制表示中1的个数。

解法二，同样用到一个循环，只是里面的操作用位移操作简化了。

int Count(int v)
{
    int num = 0;
    while (v) {
        num += v  & 0x01;
        v >>= 1;
    }
    return num;
}

解法三，用到一个巧妙的与操作，v & (v -1 )每次能消去二进制表示中最后一位1，利用这个技巧可以减少一定的循环次数。

解法四，查表法，因为只有数据8bit，直接建一张表，包含各个数中1的个数，然后查表就行。复杂度O(1)。

int countTable[256] = { 0, 1, 1, 2, 1, ...,  7, 7, 8 };

int Count(int v) {
    return countTable[v];
}

好了，这就是样章上给出的四种方案，下面谈谈我的看法。 首先是对算法的衡量上，复杂度真的是唯一的标准吗？尤其对于这种数据规模给定，而且很小的情况下，复杂度其实是个比较次要的因素。 查表法的复杂度为O(1)，我用解法一，循环八次固定，复杂度也是O(1)。至于数据规模变大，变成32位整型，那查表法自然也不合适了。 其次，我觉得既然是这样一个很小的操作，衡量的尺度也必然要小，CPU时钟周期可以作为一个参考。 解法一里有若干次整数加法，若干次整数除法（一般的编译器都能把它优化成位移），还有几个循环分支判断，几个奇偶性判断（这个比较耗时间，根据CSAPP上的数据，一般一个branch penalty得耗掉14个左右的cycle），加起来大概几十个cycle吧。 再看解法四，查表法看似一次地址计算就能解决，但实际上这里用到一个访存操作，而且第一次访存的时候很有可能那个数组不在cache里，这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle（因为要访问内存）。所以对于这种“小操作”，这个算法的性能其实是很差的。 这里我再推荐几个解决这个问题的算法，以32位无符号整型为例。

int Count(unsigned x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。 还有一个更巧妙的HAKMEM算法

int Count(unsigned x) {
   unsigned n;

   n = (x >> 1) & 033333333333;
   x = x - n;
   n = (n >> 1) & 033333333333;
   x = x - n;
   x = (x + (x >> 3)) & 030707070707;
   x = x % 63;
   return x;
}

首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。 因为2⁶ = 64，也就是说 x₀ + x₁ * 64 + x₂ * 64 * 64 = x₀ + x₁ + x₂ (mod 63)，这里的等号表示同余。 这个程序只需要十条左右指令，而且不访存，速度很快。 由此可见，衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。 关于后面的两道扩展问题，问题一是问32位整型如何处理，这个上面已经讲了。 问题二是给定两个整数A和B，问A和B有多少位是不同的。 这个问题其实就是数1问题多了一个步骤，只要先算出A和B的异或结果，然后求这个值中1的个数就行了。