Multi-softcore architectures and algorithms for a class of sparse computations

Restricted until 13 Feb. 2011. Field-programmable gate array (FPGA) is a representative reconfigurable computing platform. It has been used in many applications to execute computationally intensive workloads. In this work, we study architectures and algorithms on FPGA for sparse computations. These computations have unique features: 1) the ratio of input and output operations to computation is high and 2) most memory accesses are random with little or no data locality, which leads to low memory bandwidth utilization.; We propose Multiple Application Specific Softcore architecture to overcome the performance hurdles that are inherent to sparse computations. We identify the critical issues, demonstrate our solutions, and validate the proposed architecture using two case studies: large dictionary string matching and breadth-first search on a graph. Our architecture utilizes multiple application-specific processing units (softcores) to exploit the potential thread-level parallelism in these computations. To alleviate the impact of long latency from accessing external memory on system performance, a specialized memory architecture and a scheduling mechanism are devised to reduce the number of accesses to external memory and to hide the effects of the remaining accesses. By utilizing customized interconnects which are adaptive to communication demand, flexible and efficient inter-softcore data exchange and synchronization mechanism are well supported.; The two kernels in our study are among the most common sparse computation algorithms and are of practical significance on their own. String matching searches for all occurrences of a set of patterns (the dictionary) in a string of input data. It is the core function of search engines, intrusion detection systems (IDS), virus scanners, and spam and content filters. In our study on large dictionary string matching, our design achieved a throughput comparable to implementations on state-of-the-art multi-core computing systems. Breadth-first search is a fundamental building block for many graph algorithms, with applications in network analysis, image processing, and database query. Breadth-first search is a difficult kernel to parallelize on cache-based multi-core systems due to its fine-grained random data access and synchronization between threads. We demonstrate that, by using a message passing multi-core architecture with a distributed barrier design, high throughput performance can be obtained using a modest amount of logic resources on FPGA.本数据集于2011年2月13日前受限访问。现场可编程门阵列（Field-programmable gate array，FPGA）是一类典型的可重构计算平台，已被广泛应用于各类计算密集型工作负载的执行场景。本研究针对稀疏计算（sparse computations）场景，探索适用于FPGA的架构与算法方案。此类计算具备两大独特特性：其一，输入输出操作与计算量的占比偏高；其二，绝大多数内存访问为随机访问，数据局部性极弱甚至不存在，这会导致内存带宽利用率（memory bandwidth utilization）低下。 为克服稀疏计算固有的性能瓶颈，我们提出了多专用软核架构。我们明确了核心问题，验证了所提解决方案，并通过两项案例研究对所提架构进行了有效性验证：大规模字典字符串匹配，以及图上的广度优先搜索（Breadth-first search）。本架构借助多个专用处理单元（软核，softcore），以挖掘此类计算中潜藏的线程级并行性（thread-level parallelism）潜力。为缓解外部内存（external memory）访问的高延迟对系统性能造成的负面影响，我们设计了专用内存架构与调度机制，以减少外部内存访问次数，并掩盖剩余访问带来的延迟影响。通过采用适配通信需求的定制化互连结构（interconnects），本架构可实现灵活高效的软核间数据交换与同步机制。 本研究涉及的两类计算核心均为最具代表性的稀疏计算算法，本身即具备极高的实际应用价值。字符串匹配指在输入数据流中查找一组模式（即字典）的所有匹配项，其作为核心功能广泛应用于搜索引擎、入侵检测系统（Intrusion Detection Systems，IDS）、病毒扫描程序以及垃圾邮件与内容过滤器等场景。在大规模字典字符串匹配的研究中，我们的设计所实现的吞吐量，可与当前顶尖多核计算系统上的实现方案相媲美。 广度优先搜索（Breadth-first search）是众多图算法的基础构建模块，可应用于网络分析、图像处理与数据库查询等场景。由于具备细粒度随机数据访问特性且需要线程间同步，广度优先搜索是一类难以在基于缓存的多核系统上实现并行化的计算核心。我们验证了，通过采用带有分布式屏障（distributed barrier）设计的消息传递多核架构，仅需在FPGA上占用少量逻辑资源（logic resources），即可实现高性能的吞吐量。