Novel Pin Assignment Algorithms for Components with Very High Pin Counts

The wiring effort and thus, the routability of electronic designs such as printed circuit boards, multi chip modules and single chip modules largely depends on the assignment of signals to component pins. For modern components that have as many as several thousand pins, this pin assignment cannot be optimized manually. This paper presents four novel pin assignment algorithms that automatically create optimized pin assignments for wiring substrate designs with components that have very high pin counts. We also present and evaluate quality estimation metrics that enable fast assessment of the pin assignment results. The efficiency of our algorithms allows the creation of optimized pin assignments using only minutes of computation time. We show the applicability of all four algorithms, including their strengths and weaknesses, in specific design applications.