An efficient router for 2-D field programmable gate array

TitleAn efficient router for 2-D field programmable gate array
Publication TypeConference Paper
Year of Publication1994
AuthorsWu, Y-L, Marek-Sadowska, M
Conference NameEuropean Design and Test Conference, 1994. EDAC, The European Conference on Design Automation. ETC European Test Conference. EUROASIC, The European Event in ASIC Design, Proceedings.
Date Publishedfeb-3 mar
Keywords2D FPGA, bin-packing heuristic, circuit layout CAD, field programmable gate array, greedy 2-D router, logic arrays, logic CAD, network routing, one-step router, routing length, VLSI
AbstractIn this paper, we analyze the traditional 2-step global/detailed routing scheme. We propose a bin-packing heuristic based greedy 2-D router that can effectively and stably produce good results in both minimizing routing length and number of tracks needed to complete routing. On the tested MCNC benchmarks, our router resulted 17% less total tracks compared to the best known results of 2-step routers. Our one-step router is linear in both CPU time and run-time memory which suggests its particular suitability for very large circuits