We introduce a domain-specific language, GRAph Parallel Actor Language, that enables parallel graph algorithms to be written in a natural, high-level form. GRAPAL is based on our GraphStep compute model, which enables a wide range of parallel graph algorithms that are high-level, deterministic, free from race conditions, and free from deadlock. Programs written in GRAPAL are easy for a compiler and runtime to map to efficient parallel field programmable gate array (FPGA) implementations. We show that the GRAPAL compiler can verify that the structure of operations conforms to the GraphStep model. We allocate many small processing elements in each FPGA that take advantage of the high on-chip memory bandwidth (5x the sequential processor) and process one graph edge per clock cycle per processing element. We show how to automatically choose parameters for the logic architecture so the high-level GRAPAL programming model is independent of the target FPGA architecture. We compare our GRAPAL applications mapped to a platform with four 65 nm Virtex-5 SX95T FPGAs to sequential programs run on a single 65 nm Xeon 5160. Our implementation achieves a total mean speedup of 8x with a maximum speedup of 28x. The speedup per chip is 2x with a maximum of 7x. The ratio of energy used by our GRAPAL implementation over the sequential implementation has a mean of 1/10 with a minimum of 1/80.
展开▼
机译：我们引入了一种特定于领域的语言GRAph Parallel Actor Language，该语言使并行图算法能够以自然的高级形式编写。 GRAPAL基于我们的GraphStep计算模型，该模型支持各种高级，确定性，无竞争条件和无死锁的并行图算法。用GRAPAL编写的程序易于编译器和运行时映射到高效的并行现场可编程门阵列（FPGA）实现。我们证明了GRAPAL编译器可以验证操作的结构是否符合GraphStep模型。我们在每个FPGA中分配许多小处理元件，以利用高片上存储器带宽（顺序处理器的5倍）并在每个处理元件的每个时钟周期处理一个图形边缘。我们展示了如何为逻辑体系结构自动选择参数，以便高级GRAPAL编程模型独立于目标FPGA体系结构。我们将映射到具有四个65纳米Virtex-5 SX95T FPGA的平台的GRAPAL应用程序与在单个65纳米Xeon 5160上运行的顺序程序进行比较。我们的实现实现了平均平均加速8倍，最大加速28倍。每个芯片的加速是2倍，最大是7倍。我们的GRAPAL实现与顺序实现所消耗的能量之比平均为1/10，最小值为1/80。
展开▼
