Enumeration of Gate Pairs in a 3-D IC

The starting gates N_start used in the derivation of the interconnect length distribution for three-dimensional (3-D) circuits in [291] are described in this appendix. The starting gates are those gates that form manhattan hemispheres of radius l, where l is the interconnect length connecting two gates. For a 3-D circuit consisting of n tiers and including N_n = N/n gates per tier and those gates located close to the periphery of each tier, only partial manhattan hemispheres are formed. Consequently, the number of gates encircled by these partial manhattan hemispheres varies with the interconnect length:

Region I: l = 0

$N_{\mathrm{start}}=N_{n}n$ (A-1)

(A-1)

Region II: $0<l\le (n-1)d_v$

$N_{\mathrm{start}}=n\left(N_n-l\right)$ (A-2)

(A-2)

Region III: $\left(n-1\right)d_v<l\le \frac{\sqrt{N_n}}{2}+1$

$N_{\mathrm{start}}=nN-l$ (A-3)

(A-3)

Region IV: $\frac{\sqrt{N_n}}{2}+1<l\le \sqrt{N_n}$

$N_{\mathrm{start}}=n{N}_n-l-\left(l-\frac{\sqrt{N_n}}{2}-1\right)\left(l-\frac{\sqrt{N_n}}{2}\right)$ (A-4)

(A-4)

Region V: $\sqrt{N_n}<l\le \sqrt{N_n}+(n-1)d_v$

$N_{\mathrm{start}}=\frac{7N_n}{4}-\frac{\sqrt{N_n}}{2}-\sqrt{N_n}l-f\left[l,g\left[l-\sqrt{N_n}-1\right],1\right]$ (A-5)

(A-5)

Region VI: $\sqrt{N_n}+(n-1)d_v<l\le \frac{3\sqrt{N_n}}{2}$

$N_{\mathrm{start}}=\frac{7N_n}{4}-\frac{\sqrt{N_n}}{2}-\sqrt{N_n}l+f\left[l,n-1,2\right]-2f\left[l,n-1,\frac{3}{2}\right]$ (A-6)

(A-6)

Region VII: $\frac{3\sqrt{N_n}}{2}<l\le \frac{3\sqrt{N_n}}{2}+\left(n-1\right)d_v$

$N_{\mathrm{start}}=\left\{\begin{array}{l}\left(2\sqrt{N_n}-l\right)\left(2\sqrt{N_n}-l-1\right)+f\left[l,n-1,2\right]-2f\left[l,n-1,\frac{3}{2}\right]\\ +2f\left[l,g\left[l-\frac{3}{2}\sqrt{N_n}-1,d_v\right],\frac{3}{2}\right]\end{array}\right\}$ (A-7)

(A-7)

Region VIII: $\frac{3\sqrt{N_n}}{2}+\left(n-1\right)d_v<l\le 2\sqrt{N_n}$

$N_{\mathrm{start}}=\left(2\sqrt{N_n}-l\right)\left(2\sqrt{N_n}-l-1\right)+f\left[l,n-1,2\right]$ (A-8)

(A-8)

Region IX: $2\sqrt{N_n}<l\le 2\sqrt{N_n}+\left(n-1\right)d_v$

$N_{\mathrm{start}}=f\left[l,n-1,2\right]-f\left[l,g\left[l-2\sqrt{N_n}-1,d_v\right],2\right]$ (A-9)

(A-9)

The function g[x,y] is the discrete quotient function while function f[x,y,z] is

$f\left[l,y,z\right]=2\left\{\begin{array}{l}\frac{d_v^{2}y}{6}\left(2y^2+3y+1\right)+\frac{y}{2}\left(2z\sqrt{N_n}{d}_v-2d_{v}l-d_v\right)\left(y+1\right)\\ +4y\left(9N_n-3\sqrt{N_n}l-\frac{3}{2}\sqrt{N_n}+l+l^2\right)\end{array}\right\}$ (A-10)

(A-10)

d_v denotes the intertier distance between two adjacent tiers within a 3-D system.