Evaluation of Circuits on the Reconfigurable Mesh

The Reconfigurable Mesh (RM) is a grid of Processing Elements (PEs) that use dynamic reconfigurations to create varying bus-segments between its PEs. This allows the RM to perform computations such as sorting or counting in a constant number of steps. It has long been speculated that the RM's dynamic reconfiguration should replace the static reconfiguration architecture of the FPGA. In this work, we show that the RM can be used not only to accelerate specific computations such as sorting or summing but also for speeding up the main function of the FPGA, namely evaluation of Boolean Circuits (BCs). We propose an RM algorithm to evaluate BCs and show that it can be done without size blow-up. Moreover, like in the FPGA, it can be done using a grid of tri-state switching elements, rather than a grid of PEs as is the case with the regular RM. This model is called FPRM, and preliminary ASIC synthesis results illustrate that the FPRM architecture is about 2X faster and also more efficient in power/area than the FPGA routing infrastructure.