JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

1 of 8

ICCAD 2018 CAD Contest Problem B

Obstacle-Aware On-Track Bus Routing

About Liao, Hua-Yu Chang, Owen Chi, and Jang Wang

Nov 5^th, 2018

2 of 8

Introduction

Bus routing in advanced technology nodes is challenging

Non-uniform and complex routing track configuration
Routing in-between small obstacles while maintaining same routing topology

Routing Tracks

Width constraint

Routing In-Between Small Obstacles

3 of 8

Problem Formulation

Input

A set of routing layers L = {L₁, L₂, ..., L_k}

With preferred direction for each layer
With min spacing constraint for each layer
With min width constraint for each layer

A set of obstacles O = {O₁, O₂, ..., O_m}
A set of routing tracks T = {T₁, T₂, ..., T_n}

With width constraint for each track

A set of buses B = {B₁, B₂, ..., B_r}

With width constraint for each layer for each bus
With pin shapes for each bit in a bus

Design boundary BD

L₂

L₁

4 of 8

Problem Formulation (Cont’d)

Output

A set of on-track wires and vias that connect pins for all buses

L₂

L₁

5 of 8

Evaluation Rule

Better

Worse

Better

Worse

6 of 8

Evaluation Rule (Cont’d)

C_P = spacing_violation P_s + routing_failure_penalty P_f
P_s = #spacing_violations * δ

Each path check with paths of different net, obstacles, and design boundary (include shorts)

P_f = #failed_buses * ε

ε is large so that the penalty of a failed bus is higher than the cost of a reasonably routed bus

Different topology

Path off-track

Track width violation

Bit open

Bit order inconsistency

p₁

p₂

L₁

S₁

O₁

Spacing Violation

Route Fail

7 of 8

Test Cases

Eight cases used in final test

Certain advanced node rules
A portion of real design was used with some details removed
Simplified tracks
Simplified power structure
Some cases have power structure removed
Limit routing to 3-4 layers

	beta_1	beta_2	beta_3	beta_4	beta_5	final_1	final_2	final_3
#nets	1260	1262	665	698	1964	1032	1285	852
#buses	34	26	60	62	6	18	70	47
#tracks	49209	49209	22732	22732	54150	81226	14209	21379

8 of 8

Evaluation Results

16 teams submitted their programs for final test
12 teams can run through at least half of the tests
Top five teams

Ranking	1	2	3	4	5
Team	cada112	cada016	cada129	cada012	cada057