Combined run-time area allocation and long line re-routing for reconfigurable computing

On-line (run time) algorithms for allocation of area and routing resources are a requirement if field programmable logic applications are to be loaded to the FPGA at the arbitrary request of users. Long lines are the preferred interconnect for such applications on dense FPGAs as they provide low delay channels. In this paper we investigate the combination of an area allocation algorithm based on the Minkowski sum with run time routing based on line probing for applications that are linked only by long lines. We show by construction that allocation and routing are feasible at run time using these algorithms. The paper then introduces a new metric to measure the performance of dynamic run time resource allocation on FPGAs. The new metric measures fragmentation of resources in an environment where applications selected from statistical distributions of area and execution time are continuously queued for placement on the FPGA. It is argued that this metric is more realistic compared to other measures which are based on static model of allocation. A simulation of this dynamic FPGA environment has revealed new behaviours related to run time reconfiguration. Firstly, to maintain full utilisation of the area resources of the FPGA, it will be necessary to queue tasks prior to execution. The queuing time of these tasks is an added overhead not previously reported. Secondly, small area applications may block other applications due to the exhaustion of long line routing resources. This adds to the other already observed blocking behaviour where large area cores may so dominate the FPGA area that further allocation is prevented. A new operation for the aggregation of small cores is proposed in this paper to overcome blocking associated with routing.