本文为摘录，原文为： attachments/pdf/c/p259-arman.pdf

1 ABSTRACT

Mergesort 优点：

  • 不受数据倾斜影响
  • 适于通过向量化执行来进行并行处理
  • 适于多线程操作操作

Origami:

  • 内存归并排序算法框架
  • 对每个向量化指令集，提供寄存器内排序算子 （in-register sorter），小数据量性能提供 8 倍
  • branchless streaming merge 1.5 倍提升

2 INTRODUCTION

MergeSort 的优点：

  • 对数据分布不敏感 (distribution insensitivity): constant time on all inputs
  • 支持流式操作 (streaming operation) ， 适用于外存数据，或者分布式数据
  • 适用于多核并行计算

3 PIPELINE OVERVIEW

3.1 notation

  • N ： 待排序的元素数量
  • C ： 能够装进 L2 Cache 的数量 （约 2^16 ~ 2^18 ）
  • T ： 线程数量，常为 CPU 核数的二倍
  • W ： 每个 SIMD 寄存器可以装下的元素数量 （约 4 ~ 16 ）
  • R ： 每个 CPU 核上 SIMD 寄存器的个数 （通常 16 or 32 ）
  • B ： 每个元素的 bits 数 （ 32, 64, or 128 ）

3.2 better cache utilization,

  • L2 Cache

    • 为更好的利用 CPU Cache ， 通常将输入划分成大小为 C 的块 （block） ，然后在 Cache 对其排序，

    从而生成 N/C 个有序列表。

    • 然后使用 k 路合并 （ k>=2 ） ，生成最终的有序列表

3.3 4 Phases

MergeSort 可以分解为四个阶段，标记为 P_1 ~ P_4

3.3.1 (P1) Tiny sorters

  • 将整个输入转换成有序的子列的过程
  • 子列长度为 m ， ( m>=2= ):
    • 子列内容为 [im, (i+1)m)
    • i = 10,1,...,C/m-1
  • MergeSort 对 P1 阶段效率不高 （长度小于 128 时）
    • 可使用其他排序算法
      • insert sort
      • SIMD generalizations

3.3.2 (P2) In-cache merge

  • P1 结束后，每个子队列都是有序的
  • P2 由 \(log_2(C/m)\) 个二元合并 (binary merge) 构成

3.3.3 (P3) Out-of-cache independent merge