The problem of mapping a data flow graph onto a reconfigurable architecture has been difficult to solve quickly and optimally. Anytime algorithms have the potential to meet both goals by generating a good solution quickly and improving that solution over time, but they have not been shown to be practical for mapping. The key insight into this paper is that mapping algorithms based on search trees can be accelerated using a database of examples of high quality mappings. The depth of the search tree is reduced by placing patterns of nodes rather than single nodes at each level. The branching factor is reduced by placing patterns only in arrangements present in a dictionary constructed from examples. We present two anytime algorithms that make use of patterns and dictionaries: Anytime A*and Anytime Multiline Tree Rollup. We compare these algorithms to simulated annealing and to results from human mappers playing the online game UNTANGLED. The anytime algorithms outperform simulated annealing and the best game players in the majority of cases, and the combined results from all algorithms provide an informative comparison between architecture choices.

The problem of creating efficient mappings of dataflow graphs onto specific architectures (i.e., solving theplace and routeproblem) is incredibly challenging. The difficulty is especially acute in the area of Coarse-Grained Reconfigurable Architectures (CGRAs) to the extent that solving the mapping problem may remove a significant bottleneck to adoption. We believe that the next generation of mapping algorithms will exhibit pattern recognition, the ability to learn from experience, and identification of creative solutions, all of which are human characteristics. This manuscript describes our game UNTANGLED, developed and fine-tuned over the course of a year to allow us to capture and analyze human mapping strategies. It also describes our results to date. We find that the mapping problem can be crowdsourced very effectively, that players can outperform existing algorithms, and that successful player strategies share many elements in common. Based on our observations and analysis, we make concrete recommendations for future research directions for mapping onto CGRAs.