Automating the Design of Programmable Interconnect for Reconfigurable Architectures

With Moore's law coming to an end, increasingly more hope is being put in specialized hardware implemented on reconfigurable architectures such as Field-Programmable Gate Arrays (FPGAs). Yet, it is often neglected that these architectures themselves experience problems caused by technology scaling. In fact, due to their lower logic density and the need to provide interconnect programmability, rising wire resistance impacts the performance of FPGAs particularly negatively. This is further complicated by the traditional problem of reconfigurable architecture design: exact critical paths are not known at fabrication time.For FPGAs to deliver what is expected from them, they must continue to adapt to new technological and application realities. Local optimization of programmable interconnect around a known prior solution, which, for the past two decades, has been ensuring that performance increase of moving to the next technology node is achieved on time, no longer yields the expected results. Since technology scaling has moved away from a predictable trajectory driven by geometric shrinking, into the realm of an ever-increasing number of one-off scaling boosters, it is now harder than ever to develop a lasting intuition about how to escape these local optima. Coupling this with an ever-increasing number of different applications that require FPGA acceleration in a variety of different device integration and use contexts, we believe that the only real solution to this issue is to use design automation to seek new local optima. The problem with this, however, is that design automation algorithms comparable to those that exist in a standard Application-Specific Integrated Circui} (ASIC) flow have so far not been developed---riding the wave of Moore's law in the past decades made tackling the hard combinatorial optimization problems that arise in designing programmable interconnect unattractive. Where ASIC CAD algorithms, once developed, could be used to produce thousands of different circuits, basic economy behind FPGA's success meant that in every generation, only a handful of device families with shared programmable fabric architecture were produced. As a result, a large number of algorithms exist for transforming an ASIC described at a high level of abstraction using a hardware description language into a highly optimized netlist of gates, while programmable interconnect architectures still have to be described entirely by specifying every single wire and switch that comprise them---this would be equivalent to specifying an ASIC design by listing every single logic gate and all connections between them. Well, if such a specification has to be made only once per FPGA generation---or better yet, only once for a number of generations, as has largely been the case over the past two decades---maybe the effort of developing a set of algorithms that could do this automatically is not easily justified. The problem today, as we already mentioned, is that scaling time-tested designs with only minor modifications no longer yields the required results, while manually specifying a new design at this level of abstraction is hardly feasible after the stark increase in the number of variables that have to be taken into account due to technological and application changes.In this thesis, we address the issue by developing new algorithms for automated design of several important aspects of programmable interconnect.