Trong thiết kế vi mạch tích hợp quy mô siêu lớn (VLSI), kiến trúc máy tính và thiết kế giao diện tự động (Auto-Layout), bài toán quy hoạch mặt bằng (floor planning) đóng vai trò quyết định hiệu năng của toàn bộ hệ thống. Nhiệm vụ là sắp xếp $N$ khối chức năng hình chữ nhật (các lõi xử lý, bộ nhớ đệm, khối tính toán đồ họa) vào một bề mặt chip phẳng sao cho không có hai khối nào đè lên nhau, đồng thời tối thiểu hóa tổng diện tích chip hoặc chiều dài dây dẫn kết nối.

Nhìn từ góc độ tối ưu hóa, bài toán floor planning tổng quát là một bài toán tối ưu tổ hợp NP-khó vì vị trí tương đối giữa các khối (khối này nằm bên trái hay bên phải, bên trên hay bên dưới khối kia) là các quyết định rời rạc. Tuy nhiên, một khi cấu trúc hình học tương đối được ấn định thông qua một cây phân cắt (slicing tree), toàn bộ bài toán chọn kích thước, tỷ lệ khung hình và tọa độ các khối chuyển hóa một cách tự nhiên thành một Quy hoạch hình học (GP) hoặc Quy hoạch tuyến tính (LP) khả giải tối ưu toàn cục.

1. Mô hình hóa bài toán Floor Planning

Giả sử ta cần bố trí $N$ khối hình chữ nhật được đánh số từ $1$ đến $N$. Mỗi khối $i$ được mô tả bởi các biến quyết định:

• Tọa độ góc trái dưới: $(x_i,y_i)\in {\mathbb{R}}^2$.
• Chiều rộng: $w_i>0$.
• Chiều cao: $h_i>0$.

Do đó, khối thứ $i$ chiếm dụng miền không gian kín:

$${\mathcal{R}}_i=[x_i,x_i+w_i]\times [y_i,y_i+h_i].$$

Toàn bộ $N$ khối phải nằm trọn trong một khung bao hình chữ nhật chung có kích thước chiều rộng $W$ và chiều cao $H$, đặt tại gốc tọa độ:

$$x_i\ge 0,y_i\ge 0,x_i+w_i\le W,y_i+h_i\le H,\mathrm{\forall }i=1,\dots ,N.$$

Ràng buộc về kích thước và hình dạng của từng khối

Các khối phần cứng thường có tính co dãn linh hoạt trong giới hạn công nghệ:

1. Diện tích tối thiểu: Mỗi khối phải có diện tích không nhỏ hơn một ngưỡng thiết kế $S_i>0$:
   $$w_i{h}_i\ge S_i.$$
2. Tỷ lệ khung hình (Aspect Ratio): Để tránh các khối quá mỏng hoặc dài ngoằng gây khó khăn khi chế tạo, tỷ số giữa chiều cao và chiều rộng bị kẹp trong một khoảng cho phép:
   $${\alpha }_i\le \frac{h_i}{w_i}\le {\beta }_i,0<{\alpha }_i\le {\beta }_i.$$

2. Ràng buộc không chồng lấn và Cây phân cắt (Slicing Floorplans)

Hai khối $i$ và $j$ ($i\ne j$) không đè lên nhau ($\mathrm{int}({\mathcal{R}}_i)\cap \mathrm{int}({\mathcal{R}}_j)=\mathrm{\varnothing }$) khi và chỉ khi thỏa mãn ít nhất một trong bốn quan hệ hình học sau:

1. Khối $i$ nằm hoàn toàn bên trái khối $j$: $x_i+w_i\le x_j$.
2. Khối $i$ nằm hoàn toàn bên phải khối $j$: $x_j+w_j\le x_i$.
3. Khối $i$ nằm hoàn toàn bên dưới khối $j$: $y_i+h_i\le y_j$.
4. Khối $i$ nằm hoàn toàn bên trên khối $j$: $y_j+h_j\le y_i$.

Phép tuyển "hoặc" giữa bốn điều kiện này tạo nên tính phi lồi tổ hợp. Để giải quyết, người ta cố định trước quan hệ thứ tự tương đối bằng cách sử dụng mô hình mặt bằng phân cắt (Slicing Floorplan).

Một mặt bằng phân cắt được tạo thành bằng cách đệ quy chia đôi một hình chữ nhật lớn thành hai hình chữ nhật con bằng một lát cắt ngang (H) hoặc lát cắt dọc (V). Cấu trúc này được biểu diễn bằng một cây nhị phân (Slicing Tree), trong đó các lá là các khối chức năng và các nút nội bộ là các lát cắt.

Khi cây phân cắt đã cố định, với mỗi cặp khối $(i,j)$, ta luôn xác định được một quan hệ duy nhất có dạng:

• Lát cắt dọc: $x_i+w_i\le x_j$ (khối $i$ ở nhánh trái, khối $j$ ở nhánh phải).
• Lát cắt ngang: $y_i+h_i\le y_j$ (khối $i$ ở nhánh dưới, khối $j$ ở nhánh trên).

Khi đó, toàn bộ các ràng buộc vị trí không chồng lấn trở thành các bất đẳng thức tuyến tính chuẩn đối với các biến tọa độ và kích thước.

3. Cải dạng Quy hoạch hình học (GP) cho bài toán chọn kích thước

Khi cấu trúc cây phân cắt đã ấn định, ta muốn xác định kích thước $(w_i,h_i)$ và kích thước khung bao $(W,H)$ sao cho tổng diện tích bao quanh $WH$ là nhỏ nhất.

Bài toán có dạng:

$$\begin{array}{rl}& \text{minimize}WH\\ & \text{subject to}{w}_i{h}_i\ge S_i,i=1,\dots ,N,\\ & \phantom{\text{subject to}}{\alpha }_i\le h_i{w}_i^{-1}\le {\beta }_i,i=1,\dots ,N,\\ & \phantom{\text{subject to}}\text{slicing constraints.}\end{array}$$

Trong cấu trúc slicing tree, chiều rộng và chiều cao của khung bao có thể được biểu diễn như các posynomial của các biến kích thước khối. Cụ thể, nếu hai khối $i$ và $j$ ghép dọc thì chiều rộng tổng là $w_i+w_j$, trong khi nếu ghép ngang thì chiều rộng tổng là $max(w_i,w_j)$.

Ràng buộc diện tích viết lại thành: Biểu thức $S_i{w}_i^{-1}{h}_i^{-1}\le 1$ (một ràng buộc posynomial). Ràng buộc tỷ lệ khung hình viết lại thành: Biểu thức ${\alpha }_i{w}_i{h}_i^{-1}\le 1$ và ${\beta }_i^{-1}{h}_i{w}_i^{-1}\le 1$ (các ràng buộc posynomial).

Do đó, toàn bộ bài toán là một Quy hoạch hình học (GP) chuẩn tắc trên các biến dương $(w_i,h_i,W,H)$. Sau phép đổi biến logarit $u=\log w,v=\log h$, bài toán trở thành một bài toán tối ưu lồi với hàm mục tiêu lồi và các ràng buộc affine, giải được với hiệu năng số học cao.

4. Tối ưu hóa độ dài dây dẫn (Wirelength Optimization)

Bên cạnh mục tiêu diện tích, trong thiết kế mạch tích hợp, nhiệt độ và độ trễ tín hiệu phụ thuộc trực tiếp vào tổng độ dài dây nối giữa các khối.

Giả sử tâm của khối $i$ có tọa độ:

$$c_i=(x_i+\frac{1}{2}{w}_i,y_i+\frac{1}{2}{h}_i).$$

Độ dài dây nối Manhattan ($L_1$) giữa hai khối $i$ và $j$ với trọng số kết nối $C_{ij}\ge 0$ (đo lường số lượng đường truyền song song) là:

$${\text{Wirelength}}_{ij}=C_{ij}(|c_i^{(x)}-c_j^{(x)}|+|c_i^{(y)}-c_j^{(y)}|).$$

Tổng chiều dài dây nối toàn mạch là:

$${\mathrm{\Phi }}_{\text{wire}}=\sum _{1\le i<j\le N}{C}_{ij}(|c_i^{(x)}-c_j^{(x)}|+|c_i^{(y)}-c_j^{(y)}|).$$

Khi kích thước các khối $(w_i,h_i)$ đã được ấn định, hàm mục tiêu ${\mathrm{\Phi }}_{\text{wire}}$ là tổng của các dạng trị tuyệt đối. Bằng cách đưa vào các biến phụ $u_{ij},v_{ij}\ge 0$ thỏa mãn:

$$-u_{ij}\le c_i^{(x)}-c_j^{(x)}\le u_{ij},-v_{ij}\le c_i^{(y)}-c_j^{(y)}\le v_{ij},$$

bài toán tối thiểu hóa chiều dài dây nối đưa thẳng về một bài toán Quy hoạch tuyến tính (LP):

$$\begin{array}{rl}& \text{minimize}\sum _{i<j}{C}_{ij}(u_{ij}+v_{ij})\\ & \text{subject to}-u_{ij}\le x_i-x_j+\frac{w_i-w_j}{2}\le u_{ij},\\ & \phantom{\text{subject to}}-v_{ij}\le y_i-y_j+\frac{h_i-h_j}{2}\le v_{ij},\\ & \phantom{\text{subject to}}\text{affine non-overlapping constraints on }(x_i,y_i).\end{array}$$

5. Bài tập tự luyện

Bài tập 1: Quy hoạch hình học cho mặt bằng phân cắt hai khối

Xét hai khối chức năng được ghép cạnh nhau theo phương ngang (lát cắt dọc $V$): Khối 1 nằm bên trái, khối 2 nằm bên phải. Kích thước khung bao là $W=w_1+w_2$ và $H=max\{h_1,h_2\}$. Yêu cầu thiết kế:

• Diện tích tối thiểu: Thỏa mãn $w_1{h}_1\ge 4$ và $w_2{h}_2\ge 8$.
• Tỷ lệ khung hình vuông vắn: Thỏa mãn $0,5\le h_1/w_1\le 2$ và $0,5\le h_2/w_2\le 2$.

1. Thiết lập bài toán tối thiểu hóa diện tích khung bao $WH$ dưới dạng Quy hoạch hình học (GP).
2. Chuyển bài toán sang dạng lồi bằng phép đổi biến logarit.
3. Tìm kích thước tối ưu của hai khối khi giả định $h_1=h_2=H$.

Lời giải

1. Thiết lập dạng GP: Vì $H=max\{h_1,h_2\}$, ta đặt biến phụ $H$ với $h_1\le H$ và $h_2\le H$, tức $h_1{H}^{-1}\le 1$ và $h_2{H}^{-1}\le 1$. Khung bao chiều rộng: $W=w_1+w_2$. Hàm mục tiêu: $WH=(w_1+w_2)H=w_{1}H+w_{2}H$ (một posynomial). Bài toán GP dạng chuẩn:

   $$\begin{array}{rl}& \text{minimize}{w}_{1}H+w_{2}H\\ & \text{subject to}4w_1^{-1}{h}_1^{-1}\le 1,\\ & \phantom{\text{subject to}}8w_2^{-1}{h}_2^{-1}\le 1,\\ & \phantom{\text{subject to}}{h}_1{H}^{-1}\le 1,h_2{H}^{-1}\le 1,\\ & \phantom{\text{subject to}}0,5w_1{h}_1^{-1}\le 1,0,5h_1{w}_1^{-1}\le 1,\\ & \phantom{\text{subject to}}0,5w_2{h}_2^{-1}\le 1,0,5h_2{w}_2^{-1}\le 1.\end{array}$$

2. Dạng lồi qua thang logarit: Đặt ${\tilde{w}}_i=\log w_i,{\tilde{h}}_i=\log h_i,\tilde{H}=\log H$. Hàm mục tiêu chuyển thành hàm log-sum-exp:

   $$f_0=\log (e^{{\tilde{w}}_1+\tilde{H}}+e^{{\tilde{w}}_2+\tilde{H}})=\tilde{H}+\log (e^{{\tilde{w}}_1}+e^{{\tilde{w}}_2}).$$

   Các ràng buộc trở thành affine:

   $$$$

\tilde{w}_1 + \tilde{h}_1 &\ge \log 4, \ \tilde{w}_2 + \tilde{h}_2 &\ge \log 8, \ \tilde{h}_1 &\le \tilde{H}, \quad \tilde{h}_2 \le \tilde{H}, \ -\log 2 &\le \tilde{h}_1 - \tilde{w}_1 \le \log 2, \quad -\log 2 \le \tilde{h}_2 - \tilde{w}_2 \le \log 2. \end

$$3.\ast \ast Tìmnghiệmtốiưukhi\$h_1=h_2=H\$\ast \ast :Đểdiệntíchkhungbao\$WH=(w_1+w_2)H=w_{1}H+w_{2}H\$nhỏnhất,cácràngbuộcdiệntíchphảiđạtchặt:$$

w_1 = \frac{4}{H}, \qquad w_2 = \frac{8}{H}.

$$Khiđóchiềurộngtổng:\$W=w_1+w_2=\frac{12}{H}\$.Tổngdiệntíchkhungbaolà\$WH=\frac{12}{H}\cdot H=12\$hằngsố!Đểthỏamãntỷlệkhunghìnhchocảhaikhối:-Vớikhối1:Tỷlệ\$0,5\le H^2/4\le 2\$,suyra\$\sqrt{2}\le H\le 2\sqrt{2}\$.-Vớikhối2:Tỷlệ\$0,5\le H^2/8\le 2\$,suyra\$2\le H\le 4\$.Giaohaimiềnnghiệmcho:$$

2 \le H \le 2\sqrt{2} \approx 2{,}828.

$$Chọnnghiệmđốixứngtiệnlợi\$H=2\$:-Khối1:\$h_1=2,w_1=2\$(tỷlệ\$h_1/w_1=1\$,hìnhvuông).-Khối2:\$h_2=2,w_2=4\$(tỷlệ\$h_2/w_2=0,5\$,nằmtrongkhoảng\$[0,5;2]\$).-Khungbao:\$W=6,H=2\$,tổngdiệntíchtốiưu\$S_{min}=12\$.Khôngcódiệntíchchết(deadspace=0$$

Bài tập 2: Cân bằng dây dẫn bằng Quy hoạch tuyến tính

Cho ba khối chức năng $A,B,C$ có kích thước cố định $1\times 1$. Khối $A$ được gắn chặt tại tọa độ $(0,0)$, khối $B$ được gắn chặt tại $(4,0)$. Khối $C$ là một lõi xử lý trung gian có tọa độ $(x,y)$ cần tìm trong vùng $0\le x\le 4,0\le y\le 3$. Trọng số kết nối dây dẫn là $C_{AC}=2$ và $C_{BC}=3$.

1. Viết biểu thức tổng độ dài dây nối Manhattan từ khối $C$ tới hai khối $A$ và $B$.
2. Tìm tọa độ $(x^{\ast },y^{\ast })$ tối ưu giải tích.
3. Thêm một khối cố định $D$ tại $(2,3)$ với trọng số $C_{CD}=4$. Tìm vị trí tối ưu mới của khối $C$.

Lời giải

1. Biểu thức tổng độ dài dây dẫn: Tọa độ tâm các khối: $c_A=(0,5,0,5)$, $c_B=(4,5,0,5)$, và $c_C=(x+0,5,y+0,5)$. Đặt biến dịch chuyển tương đối $x\in [0,4]$ và $y\in [0,3]$: Khoảng cách Manhattan:

   • Từ $A$ đến $C$: $|x-0|+|y-0|=x+y$ (vì $x,y\ge 0$).
   • Từ $B$ đến $C$: $|x-4|+|y-0|=(4-x)+y$ (vì $0\le x\le 4,y\ge 0$). Tổng chiều dài có trọng số:
   $$f(x,y)=2(x+y)+3((4-x)+y)=2x+2y+12-3x+3y=12-x+5y.$$

2. Tìm tọa độ tối ưu: Hàm mục tiêu tuyến tính phân rã theo hai biến độc lập:

   $$\underset{0\le x\le 4,0\le y\le 3}{min}(12-x+5y).$$
   • Với biến $y$: Hệ số $+5>0$, hàm đồng biến theo $y$. Để cực tiểu, ta chọn $y^{\ast }=0$.
   • Với biến $x$: Hệ số $-1<0$, hàm nghịch biến theo $x$. Để cực tiểu, ta chọn $x^{\ast }=4$. Vậy vị trí tối ưu là $(x^{\ast },y^{\ast })=(4,0)$. Khối $C$ đặt sát cạnh khối $B$ do trọng số kết nối $C_{BC}=3$ lớn hơn $C_{AC}=2$. Giá trị mục tiêu tối ưu: $f(4,0)=12-4+0=8$.

3. Khi bổ sung khối $D$ tại $(2,3)$ với $C_{CD}=4$: Khoảng cách từ $C$ đến $D$: $|x-2|+|y-3|=|x-2|+(3-y)$ (vì $y\le 3$). Hàm mục tiêu mới:

   $$$$

g(x, y) &= 12 - x + 5y + 4\big(|x - 2| + 3 - y\big) \ &= 12 - x + 5y + 4|x - 2| + 12 - 4y \ &= 24 - x + y + 4|x - 2|. \end

$$-Theophương\$y\$:Hàmmụctiêutăngtheo\$y\$(hệsố\$+1\$),dođónghiệmtốiưutiếptụclà\$y^{\ast }=0\$.-Theophương\$x\$:Xéthàm\$h(x)=-x+4|x-2|\$trênđoạn\$[0,4]\$:-Khi\$x\in [0,2]\$:\$h(x)=-x+4(2-x)=8-5x\$,nghịchbiến,đạtcựctiểutại\$x=2\$vớigiátrị\$h(2)=8-10=-2\$.-Khi\$x\in [2,4]\$:\$h(x)=-x+4(x-2)=3x-8\$,đồngbiến,đạtcựctiểutại\$x=2\$vớigiátrị\$h(2)=6-8=-2\$.Nhưvậy,vịtrítốiưuduynhấtmớilà:$$

(x^, y^) = (2, 0).

$$Giátrịhàmmụctiêutốiưu:\$g(2,0)=24-2+0+4(0)=22\$.Trọngsốkếtnốilớncủakhối\$D\$(\$C_{CD}=4\$)đãkéotọađộ\$x\$vềngaytrungvị\$x=2\$.$$

Bài tập 3: Nới lỏng lồi cho ràng buộc không chồng lấn

Cho hai khối hình vuông kích thước $2\times 2$. Ràng buộc không chồng lấn là: Biểu thức $|x_1-x_2|\ge 2$ hoặc $|y_1-y_2|\ge 2$.

1. Giải thích vì sao của cặp tọa độ $(x_1,y_1)$ và $(x_2,y_2)$ không phải là .
2. Nêu kỹ thuật biến đổi sử dụng biến nhị phân (Big-M method) để mô hình hóa ràng buộc này trong Quy hoạch hỗn hợp số nguyên (MILP).
3. Trong phương pháp lồi (Convex Relaxation), nếu bỏ qua tính rời rạc của biến nhị phân, điều gì xảy ra với hai khối?

Lời giải

1. Tính phi lồi của : Miền không chồng lấn là phần bù của một hình vuông mở:

   $$\mathcal{F}=\{(\mathrm{\Delta }x,\mathrm{\Delta }y)\in {\mathbb{R}}^2\mid max\{|\mathrm{\Delta }x|,|\mathrm{\Delta }y|\}\ge 2\},$$

   trong đó $\mathrm{\Delta }x=x_1-x_2$ và $\mathrm{\Delta }y=y_1-y_2$. Lấy hai :

   • Điểm $A=(2,0)\in \mathcal{F}$ (khối 1 ở bên phải khối 2 khoảng cách 2).
   • Điểm $B=(-2,0)\in \mathcal{F}$ (khối 1 ở bên trái khối 2 khoảng cách 2). Trung điểm của đoạn $AB$ là $M=\frac{1}{2}A+\frac{1}{2}B=(0,0)$. Tại $M$, $\mathrm{\Delta }x=0$ và $\mathrm{\Delta }y=0$, suy ra hai khối đè khít lên nhau, $M\notin \mathcal{F}$. Vì đoạn nối giữa hai chứa điểm không khả thi, miền khả thi hoàn toàn không lồi.

2. Kỹ thuật Big-M trong MILP: Để chọn một trong bốn điều kiện, ta đưa vào bốn biến nhị phân $b_1,b_2,b_3,b_4\in \{0,1\}$ và một hằng số đủ lớn $M>0$:

   $$$$

x_1 - x_2 + 2 &\le M(1 - b_1), \ x_2 - x_1 + 2 &\le M(1 - b_2), \ y_1 - y_2 + 2 &\le M(1 - b_3), \ y_2 - y_1 + 2 &\le M(1 - b_4), \ b_1 + b_2 + b_3 + b_4 &\ge 1. \end

$$Khibiếnnhịphân\$b_1=1\$,vếphảibằng0vàràngbuộc\$x_1+2\le x_2\$cóhiệulực.Cácràngbuộccó\$b_k=0\$cóvếphảibằng\$M\$,hoàntoànbịvôhiệuhóa.3.\ast \ast Hiệntượngkhinớilỏnglồi\ast \ast :Khinớilỏngcácbiếnnhịphânsangkhoảngliêntục\$b_k\in [0,1]\$,bộgiảitốiưusẽchọn\$b_1=b_2=b_3=b_4=0,25\$vớitổngbằng1.Khiđómỗiràngbuộcđềubịnớilỏngmộtkhoảng\$0,75M\$.Kếtquảlàhaikhốicóthểtựdoxuyênthấuvàchồnglấnlênnhauđểgiảmthiểutốiđađộdàidâynối.Đểgiảiquyết,ngườitakếthợpnớilỏnglồivớithuậttoánphânnhánhchặn(Branch-and-Bound)hoặcthuậttoánditruyềnđểcốđịnhcâyphâncắttrước.$$

Tóm tắt

Quy hoạch mặt bằng (Floor Planning) là minh chứng điển hình cho sự kết hợp khéo léo giữa cấu trúc hình học rời rạc và tối ưu hóa lồi liên tục. Mặc dù bài toán vị trí tương đối mang bản chất tổ hợp phi lồi, việc cố định quan hệ thứ tự qua cây phân cắt slicing tree mở đường cho việc áp dụng Quy hoạch hình học (GP) để tìm kích thước và tỷ lệ khung hình tối ưu toàn cục.

Bên cạnh đó, bài toán tối thiểu hóa độ dài dây dẫn kết nối theo chuẩn Manhattan đưa trực tiếp về Quy hoạch tuyến tính (LP), cung cấp các thuật toán giải quyết nhanh chóng và chuẩn xác cho các bài toán phân bổ không gian và bố trí linh kiện quy mô lớn trong công nghiệp bán dẫn và trí tuệ nhân tạo.

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press, Chapter 8: Geometric Problems (§8.8).