Deterministic VLSI Block Placement Algorithm Using Less Flexibility First Principle

In this paper, a simple whileeffective deterministic algorithm for solving the VLSI block placementproblem is proposed considering the packing area and interconnect wiringsimultaneously. The algorithm is based on a principle inspired byobservations of ancient professionals in solving their similar problems.Using the so-called Less Flexibility First principle, it is tried topack blocks with the least packing flexibility on its shape andinterconnect requirement to the empty space with the least packingflexibility in a greedy manner. Experimental results demonstrate thatthe algorithm, though simple, is quite effective in solving the problem.The same philosophy could also be used in designing efficient heuristicsfor other hard problems, such as placement with preplaced modules,placement with L/T shape modules, etc.