On Fast Iterative Mapping Algorithms for Stripe-based Reconfigurable Architectures

Abstract

Reconfigurable devices have potential for great flexibility/efficiency, but mapping algorithms onto these architectures is a long-standing challenge. This paper addresses this challenge for stripe based coarse-grained reconfigurable architectures (CGRAs) by drawing on insights from graph drawing. We adapt fast, iterative algorithms from hierarchical graph drawing to the problem of mapping to stripe based architectures. We find that global sifting is 98 times as fast as simulated annealing and produces very compact designs with 17% less area on average, at a cost of 5% greater wire length. Interleaving iterations of Sugiyama and global sifting is 40 times as fast as simulated annealing and achieves somewhat more compact designs with 1.8% less area on average, at a cost of only 1% greater wire length. These solutions can enable fast design space exploration, rapid performance testing, and flexible programming of CGRAs “in the field.”