Data communication estimation and reduction for reconfigurable systems

Widespread adoption of reconfigurable devices requires system level synthesis techniques to take an application written in a high level language and map it to the reconfigurable device. This paper describes methods for synthesizing the internal representation of a compiler into a hardware description language in order to program reconfigurable hardware devices. We demonstrate the usefulness of static single assignment (SSA) in reducing the amount of data communication in the hardware. However, the placement of Φ-nodes by current SSA algorithms is not optimal in terms of minimizing data communication. We propose a new algorithm which optimally places Φ-nodes, further decreasing area and communication latency. Our algorithm reduces the data communication (measured as total edge weight in a control data flow graph) by as much as 20% for some applications as compared to the best-known SSA algorithm - the pruned algorithm. We also describe future modifications to our model that should increase the effectiveness of our methods.