Efficient Search Algorithms for Tiled Architectures in the Billion Transistor Era

摘要

Over the next decade the underlying architectural assumptions used in the design of parallel algorithms will change significantly, likely impacting on the efficiency of many well-known parallel algorithms. Several single-chip parallel architectures have been proposed to exploit these chip-level resources, and to overcome the wire-delay bottleneck apparent in current superscalar designs, designs that do not scale to billion transistor large silicon areas. One of the promising proposed architectures are tiled architectures, based on replicated processing tiles interconnected with high-bandwidth, low-overhead communication links. With the arrival of such fine-grained, highly-parallel architectures, that possibly provide thousands of simple processing elements connected with fast links, we need to have another look at the efficiency of many well-known parallel algorithms. This paper presents an efficient new search algorithm for tiled architectures and highlights some of the main issues when designing algorithms for such systems. Our simulation results show that as the number of tiles increases in a tiled processor, the work distribution in the proposed algorithm becomes significantly better than in a traditional depth-first search (DFS) algorithm, and the minimum utilization of any tile is an order of magnitude higher than in a traditional parallel DFS.