一句话:以函数式珍珠形式深入剖析比较网络理论,揭示 Batcher 奇偶归并网络的结构。
本文是一篇函数式珍珠(functional pearl),关注并行排序算法中的比较网络。比较网络以硬连线方式可视化并行过程,无需编程语法或并发语义的复杂性即可理解,看似简单却具有出人意料地丰富的结构。作者以 Batcher 的奇偶归并网络为切入点,深入其理论,通过推导与结构化分析揭示该网络的构造原理。文中不依赖复杂并发机制,而是从比较网络的基本理论出发,展示其内在规律。作为珍珠论文,评估以理论阐述和推导为主,不涉及实验评测。
Comparison networks offer an attractive framework for studying parallel sorting algorithms. The visual presentation of such hard-wired networks makes processes easy to conceptualize without the overhead of programming syntax or the semantic complications of concurrency. Though simple in appearance they have a surprisingly rich structure. In this pearl we delve a little into their theory.