A LEGAL algorithm following global routing

This papers presents an implementation of a LEGAL algorithm following a previous established global routing. LEGAL algorithms were first proposed by Johann in 1994, where the ideas from the most efficient channel routing algorithms were combined and used to process detailed routing of large areas in almost linear time. Other implementations produced good detailed results but had no means of making a global routing distribution in bigger circuits, which is a task for global routing. Now we present the first implementation of a detailed LEGAL routing that can obey global paths previously chosen for each net. The mechanisms developed to isolate global and local decisions and still keep LEGAL routing being made over the whole area are the focus of this paper. The implementation should be tested and refined further to allow optimizations and become competitive to other approaches in practice.