Clustering Algorithms for Component Placement in Printed Circuit Boards

Abstract

In 2024, approximately 12 billion printed circuit boards (PCBs) were manufactured globally [1], with the trend increasing gradually, and the majority of PCB layouts still being completed manually. The manual design process amounts to millions of hours of tedium that can be eased with automation. One of the biggest challenges is that the complex Printed Circuit Board designs typically have hundreds, sometimes thousands of components and even more net connections between them. This makes both manual and automated placement very time-consuming. As a way to improve placement performance, in this thesis, we constructed a custom weighted undirected graph representation of components and nets for any board that would encode physical and electrical constraints. Additionally, we integrated the Louvain and Leiden clustering algorithms for component clustering in PCB placement. We also showed comparative metrics with the spectral clustering algorithm applied to unweighted graph representations, which is the prior state of this project, but it has no knowledge of electrical and physical constraints associated with PCB designs and would thus produce results that require more manual correction. This new clustering approach was able to generate more optimal clustering and reduced average runtime by 51.05%, decreased estimated length of routing by 7.72%, and improved component association score by 12.8%.