Chips-Chips
The challenge
The goal of this challenge was to minimize the average length of chains that connected pins in a chip, while also trying to minimize the standard deviation of the lengths of the different chains. This was a problem set by Qualcomm for the FME Datathon 2022 which had the aim of minimizing the power loss across a chip.
Our approach
Together with Paula, Ruth, Àlex and I, we decided to approach the problem by modelling it by considering a graph where the nodes are pins and the edges cables. We implemented 2 strategies:
The first strategy was implemented to minimize the sum of the lengths of the chain. In each iteration the algorithm connects a node to the path by removing one edge and and adding 2 edges from the disconnected nodes to the new node, which is choosen to minimize the length. However even though this works well, because the algorithm takes O(n³) it takes too long for large cases (>1000 nodes).
Our second stratregy is less accurate but has a time complecity of O(log(n)). It takes all the pins (nodes) and divides them into 32 different intervals depending on the Y-axis, then every pin on the interval is connected with the same cable from left to right and the n-th interval is connected with the n+16-th internval so we connect the input with the output driver.
One of our solutions.