📦 Packing and Re-packing

---

# 📦 Packing and Re-packing
### FPGA block packing algorithms

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**Part 1: FPGA Design Flow** 🏭
- Logic synthesis → packing 📋
- Role of packing in the flow 🔄

**Part 2: Packing Problems** 🧩
- Toy Problem (1): one L + one F 🤝
- Weighted bipartite matching 📐
- Toy Problem (2): L + F + Q
- Toy Problem (3): two L's + one F

]
.pull-right[

**Part 3: Extensions** 🔍
- Specialized cell types 🏭
- Set cover connection 🎯

]

---

## Part 1: FPGA Design Flow 🏭

---

### 🏭 Design flow of FPGA

.mermaid[
<pre>
flowchart TD
    LS[Logic Synthesis] --> TM[Technology Mapping]
    TM --> PK[Packing]
    PK --> PL[Placement]
    PL --> RT[Routing]

style LS fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style TM fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440
    style PK fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440
    style PL fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px,color:#2e3440
    style RT fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440
</pre>
]

---

## Part 2: Packing Problems 🧩

---

### 🧩 Toy Problem (1)

.mermaid[
<pre>
graph TD
    subgraph "Cells C"
        C1((C1))
        C2((C2))
        C3((C3))
    end
    subgraph "L Elements"
        L1[L1]
        L2[L2]
        L3[L3]
    end
    subgraph "F Elements"
        F1[F1]
        F2[F2]
        F3[F3]
    end
    C1 --> L1
    C1 --> F1
    C2 --> L2
    C2 --> F2
    C3 --> L3
    C3 --> F3

style C1 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440
    style C2 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440
    style C3 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440
    style L1 fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440
    style L2 fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440
    style L3 fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440
    style F1 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style F2 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style F3 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
</pre>
]

Given:

- A netlist contains ${\color{blue} n}$ L's and ${\color{orange} m}$ F's.
- A grid of C's, each of them can pick exactly one L and one F.

---

### 📝 Problem Formulation

- Weighted bipartite matching
- Edge-weight models the importance, e.g.
- connectivity
- physical distance (repacking)

Choices:

- Exact solution using a network flow algorithm
- Approximate solution using greedy or primal-dual algorithm

---

### 📚 Example

```text
  F  F  F  F  F  F  o  o  o  o  o  o  o  o  o  o

L  L  L  L  L  L  L  L  L  L  L  L  L  L  o  o
```

---

### 🧩 Toy Problem (2)

- A netlist contains ${\color{blue} n}$ L's, ${\color{orange} m}$ F's, and ${\color{green} p}$ Q's.
- A grid of C's, each of them can pick exactly one L, one F, and one Q.

Possible solution:

- Two-stage approach: pack_toy1(Q, F) pack_toy1(QF, L)
]
.pull-right[
.mermaid[
<pre>
graph LR
    subgraph "Stage 1"
        Q1[Q] --> QF1[QF]
        F1[F] --> QF1
        Q2[Q] --> QF2[QF]
        F2[F] --> QF2
    end
    subgraph "Stage 2"
        QF1 --> C1[Cell]
        L1[L] --> C1
        QF2 --> C2[Cell]
        L2[L] --> C2
    end

style Q1 fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440
    style Q2 fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440
    style F1 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style F2 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style L1 fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px,color:#2e3440
    style L2 fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px,color:#2e3440
    style QF1 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440
    style QF2 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440
    style C1 fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440
    style C2 fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440
</pre>
]
]

---

### 🧩 Toy Problem (3)

Given:

- A netlist contains ${\color{blue} n}$ L's and ${\color{orange} m}$ F's.
- A grid of C's, each of them can pick exactly **two** L's and one F.

Possible solution:

- Two-stage approach: pack_toy1(F, L) pack_toy1(L, FL)

---

### 📚 Example

Step 1

```text
  F  F  F  F  F  F

L  L  L  L  L  L  L  L  L  L  L  L  L  L
```

Step 2

```text
  FL  FL  FL  FL  FL  FL  o   o

L   L   L   L   L   L   L   L
```

---

## Part 3: Extensions 🔍

---

### 🏭 Specialized C?

.mermaid[
<pre>
graph LR
    subgraph "Cell Types"
        C1["Cell Type 1\n L1 + F"]
        C2["Cell Type 2\n L2 + F"]
    end
    subgraph "Elements"
        L1[L1]
        L2[L2]
        F[F]
    end
    C1 --> L1
    C1 --> F
    C2 --> L2
    C2 --> F

style C1 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440
    style C2 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style L1 fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440
    style L2 fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px,color:#2e3440
    style F fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440
</pre>
]

- What if there are two kinds of C's

- e.g. C1 = [L1, F], C2 = [L2, F]

- Set Cover problem?

---

# 🙋 Q&A

### Questions? Discussion? 💬

---

# 👏 Thank You

Slides built with Remark.js 🎉 | KaTeX 📐 | Mermaid 🧩 | Nord Theme 🌙