Deterministic Multi-Core Parallel Routing for FPGAs

Marcel Gort and Jason Anderson

University of Toronto

November, 2010

The run-time of field-programmable gate array (FPGA) CAD tools is a major concern for FPGA vendors and their customers. Two factors are at play in worsening run-times for the largest designs. First, uniprocessor performance improvements have largely given way to increases in the number of cores on a chip. Second, chips continue to double in size every two years. There is, consequently, a widening gap between the size of chips, and the ability of CAD tools running on a single core to handle them, resulting in a demand for parallel CAD tools.

This talk will present our recent work in coarse and fine-grained techniques for parallel FPGA routing on modern multi-core processors. In the coarse-grained approach, sets of design signals are assigned to different processor cores and routed concurrently. Communication between cores is through the MPI (message passing interface) communications protocol. In the fine-grained approach, the task of routing an individual load pin on a signal is parallelized using threads. The proposed techniques provide deterministic/repeatable results.  Moreover, the coarse and fine-grained approaches are not mutually exclusive and can be used in tandem. Results show that on a 4-core processor, the techniques improve router run-time by ~2.1x, on average, with no significant impact on circuit speed performance or interconnect resource usage.