How many squares fit in a circle?
Andrew Mclaughlin 
I am reading a book on computer architecture. The author discusses how processor chips are made from wafers. Dies (the heart of the chip, that does calculations) are cut from circular wafer plates.
Because dies are square (or rectangular I should say), and the wafer is a circle, not all of the area of the wafer is used for dies.
To calculate how many dies can go into a single wafer, the author uses this equation: $$\text{Dies per wafer}=\frac{\pi\times(\text{Wafer diameter}/2)^2}{\text{Die area}}-\frac{\pi\times\text{Wafer diameter}}{\sqrt{2\times\text{Die area}}}.$$
The second part of the equation compensates for the problem of squares in a circle. I am interested in the derivation of the second part. Can you help me out?
$\endgroup$ 12 Answers
$\begingroup$$$\text{Dies per wafer} = \frac{ \pi \times (\text{Wafer diameter} / 2)^2}{\text{Die area}} - \frac{\pi \times (\text{Wafer diameter})}{\sqrt{2 \times \text{Die area}}}$$Because $\text{Wafer diameter} / 2 = \text{Wafer radius}$, $\pi \times \text{Wafer diameter} = \text{Wafer circumference}$, and $\sqrt{\text{Die area}} = \text{Square die edge length}$, the above is equivalent to$$\text{Dies per wafer} = \frac{\text{Wafer area}}{\text{Die area}} - \sqrt{\frac{1}{2}} \frac{\text{Wafer circumference}}{\text{Square die edge length}}$$The left side is the number of dies you could get, if the wafer had a shape that could be exactly packed with dies. The right side is the estimated number of dies "lost" because of the disc shape.
The way you can derive this estimate is simple. Let's assume $r$ is the wafer radius, and $L$ is the edge length for each square die, and that the area unusable for dies corresponds to the area within $L/\sqrt{2}$ of the perimeter; within half the diagonal of each die. That gives us the estimate on the number of dies $N$ we can fit on the wafer as$$\begin{aligned} N(r, L) &\approx \frac{\pi (r - \sqrt{1/2}L)^2}{L^2} \\ \; &= \frac{\pi r^2}{L^2} - \frac{2 \pi \sqrt{1/2} r L}{L^2} + \frac{\pi L^2}{2 L^2} \\ \; &= \pi \left(\frac{r}{L}\right)^2 - \frac{2 \pi r}{\sqrt{2} L} + \frac{\pi}{2} \\ \end{aligned}$$The third term $\pi/2 \approx 1.57$, and is obviously insignificant for the estimate, so we can drop it. Our estimate then becomes$$N(r, L) = \frac{\pi r^2}{L^2} - \frac{2 \pi r}{\sqrt{2} L}$$If we write $r$ as $\text{Wafer diameter} / 2$, and $L^2$ as $\text{Die area}$, it becomes$$\text{Dies per wafer} = \frac{\pi \times (\text{Wafer diameter} / 2)^2}{\text{Die area}} - \frac{\pi \times (\text{Wafer diameter})}{\sqrt{2 \times (\text{Die area})}}$$which is exactly the estimate at hand.
Of course, we don't know if the original authors derived it this way, but this is definitely a sensible way one can derive the estimate.
Comparing to bounds estimates shown here, $\lambda = \text{Wafer radius} / \text{Square die edge length}$. The above estimate of the number of dies then equates to$$N(\lambda) = \pi \lambda^2 - \sqrt{\frac{1}{2}} 2 \pi \lambda = \pi \lambda \left ( \lambda - \sqrt{2} \right )$$which is smaller than the upper bounds derived in that other answer. In other words, the $\text{Dies per wafer}$ estimate is quite conservative.
$\endgroup$ 5 $\begingroup$The first part of the equation gives us the number of squares (including all the squares we had to chop at the circles edge). The second part is an estimate of square dies on the edge of the circle. This is estimated by counting number of squares that can be layed along the edge of circle so that diagonal of square overlaps with edge of circle.
This esitmate should work alright only if the square is significantly smaller than the circle. If you were for example fitting a square which was of edges $1$ unit long on a circle $\sqrt{2}$ unit in diameter, The equation gives us $- \frac{1}{2} \pi$ as the number of squares.
$\endgroup$
