An Algebra of Scans
An Algebra of Scans
复制标题
扫描代数
DOI：
10.1007/978-3-540-27764-4_11
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
R. Hinze
中科院分区：
文献类型：
--
作者：
R. Hinze
并行前缀电路采用n输入x 1，x 2，...，x n，并产生n输出x 1，x 1∘x 2，...，x 1 x1∘x 2 x 2∘x x x n，where''∘'是一个任意的关联二进制操作。通过各种方式来考虑大小，深度或风扇的约束，通过图形方式定义了实现，或者通过列举这两个方法都有其优点。扫描的递归结构，但不适合形式的形式，而严格却掩盖了扫描的结构，并且在本文中也很难操纵我们表明，平行前缀电路只使用两个基本的构建块和四个组合器，所有标准设计都可以简洁地描述。系统的方式。
A parallel prefix circuit takes n inputs x 1, x 2, ..., x n and produces the n outputs x 1, x 1 ∘ x 2, ..., x 1 ∘ x 2 ∘ ⋯ ∘ x n , where’∘’ is an arbitrary associative binary operation. Parallel prefix circuits and their counterparts in software, parallel prefix computations or scans, have numerous applications ranging from fast integer addition over parallel sorting to convex hull problems. A parallel prefix circuit can be implemented in a variety of ways taking into account constraints on size, depth, or fan-out. Traditionally, implementations are either defined graphically or by enumerating the underlying graph. Both approaches have their pros and cons. A figure if well drawn conveys the possibly recursive structure of the scan but it is not amenable to formal manipulation. A description in form of a graph while rigorous obscures the structure of a scan and is equally hard to manipulate. In this paper we show that parallel prefix circuits enjoy a very pleasant algebra. Using only two basic building blocks and four combinators all standard designs can be described succinctly and rigorously. The rules of the algebra allow us to prove the circuits correct and to derive circuit designs in a systematic manner.