1 of 16

2021 ICCAD CAD Contest Problem B: Routing with Cell Movement Advanced

Problem Description, Benchmarks, and Results

Kai-Shun Hu, Tao-Chun Yu, Ming-Jen Yang, and Chin-Fang Cindy Shen

November 2021

© 2021 Synopsys, Inc.

1

2 of 16

Outline

  • Problem Description
  • Benchmarks
  • Results

​

© 2021 Synopsys, Inc.

2

3 of 16

Outline

  • Problem Description
  • Benchmarks
  • Results

​

© 2021 Synopsys, Inc.

3

4 of 16

Problem Description

  • This Contest Problem is an extended problem from 2020 ICCAD CAD Contest Problem B

​

  • Objective
    • Placement and Routing divide-and-conquer approach would introduce
      • conservative margin reservation and mis-correlation between stages

​

  • Develop a global route routing engine
    • Honor all given constraints
    • Can move cells from one gGrid to another gGrid
    • Max number of cell moves would be given
    • Optimize the given score metric

​

© 2021 Synopsys, Inc.

4

5 of 16

Outline

  • Problem Description
  • Benchmarks
  • Results

​

© 2021 Synopsys, Inc.

5

6 of 16

Benchmarks

  • Public cases

​

​

​

​

​

​

  • Hidden cases

​

case1

case2

case3

Case4

case5

case6

#gGrids

5x5

4x4

27x33

104x103

277x277

237x236

#Layers

3

3

7

16

12

16

#CellInsts

8

6

2,735

96,689

204,206

352,234

#Nets

6

6

2,644

92,559

179,996

332,063

initial #routes

42

20

25,051

1,336,847

2,898,482

4,454,757

initial total weighted score

101

38.58

29,706.6

1,590,850

3,671,190

5,602,310

​

case3B

case4B

case5B

case6B

#gGrids

27x33

104x103

277x277

237x236

#Layers

7

16

12

16

#CellInsts

2,738

96,690

204,206

352,302

#Nets

2,644

92,566

179,996

332,118

initial #routes

25,325

1,333,966

2,892,456

4,416,213

initial total weighted score

30,073.8

1,529,270

3,665,610

5,554,350

© 2021 Synopsys, Inc.

6

7 of 16

Outline

  • Problem Description
  • Benchmarks
  • Results

​

© 2021 Synopsys, Inc.

7

8 of 16

Results – Top X

  • Alpha

​

​

​

​

​

  • Beta

Alpha to Beta

Rank

case1

case2

case3

Case4

case5

case6

case3B

case4B

case5B

case6B

1

53.60

13.34

9,271.2

568,290

n/a

n/a

n/a

n/a

n/a

n/a

2

53.60

13.34

4,862.2

0

n/a

n/a

n/a

n/a

n/a

n/a

3

53.60

13.34

4,351.8

0

n/a

n/a

n/a

n/a

n/a

n/a

4

53.60

13.10

4,351.8

0

n/a

n/a

n/a

n/a

n/a

n/a

5

52.10

13.10

0

0

n/a

n/a

n/a

n/a

n/a

n/a

Rank

case1

case2

case3

case4

case5

case6

case3B

case4B

case5B

case6B

1

53.60

13.34

9,570.2

588,980

1,222,250

1,125,340

9,723.2

565,063

1,222,530

1,102,420

2

53.60

13.34

9,312.8

584,383

1,201,020

1,116,300

9,572.0

558,761

1,200,450

1,099,750

3

53.60

13.34

9,303.8

568,198

1,097,340

839,992

9,559.0

544,283

1,073,710

847,020

4

52.10

13.34

9,280.6

555,857

1,076,410

751,291

9,494.2

533,748

1,029,790

738,094

5

52.10

13.34

9,275.8

486,848

1,032,290

723,704

9,420.2

488,702

806,574

651,165

© 2021 Synopsys, Inc.

8

9 of 16

Results – Top X

  • Beta

​

​

​

​

​

  • Final

Beta to Final

Rank

case1

case2

case3

case4

case5

case6

case3B

case4B

case5B

case6B

1

53.60

13.34

9,570.2

588,980

1,222,250

1,125,340

9,723.2

565,063

1,222,530

1,102,420

2

53.60

13.34

9,312.8

584,383

1,201,020

1,116,300

9,572.0

558,761

1,200,450

1,099,750

3

53.60

13.34

9,303.8

568,198

1,097,340

839,992

9,559.0

544,283

1,073,710

847,020

4

52.10

13.34

9,280.6

555,857

1,076,410

751,291

9,494.2

533,748

1,029,790

738,094

5

52.10

13.34

9,275.8

486,848

1,032,290

723,704

9,420.2

488,702

806,574

651,165

Rank

case1

case2

case3

case4

case5

case6

case3B

case4B

case5B

case6B

1

53.60

13.34

9,900.6

610,719

1,252,540

1,207,500

10,123.6

584,771

1,252,670

1,186,130

2

53.60

13.34

9,590.4

606,053

1,245,000

1,204,010

9,825.8

579,469

1,243,930

1,184,140

3

53.60

13.34

9,576.6

600,378

1,236,580

1,162,360

9,812.6

574,495

1,235,660

1,143,930

4

53.60

13.34

9,572.8

597,955

1,234,230

1,154,400

9,812.2

571,747

1,234,840

1,141,010

5

53.60

13.34

9,569.0

593,155

1,224,610

1,151,710

9,754.8

568,685

1,224,000

1,132,740

© 2021 Synopsys, Inc.

9

10 of 16

Results – Changing % of the max cell moves

case4

%

cada0136

cada0095

cada0129

​

0

n/a

n/a

348,327

10

496,164

481,347

490,824

30

610,719

606,053

597,955

100

634,609

637,326

618,296

case5

%

cada0136

cada0095

cada0129

​

0

n/a

n/a

802,897

10

1,044,210

1,023,310

1,033,710

30

1,252,540

1,245,000

1,234,230

100

1,339,820

1,310,660

1,324,520

case6

%

cada0136

cada0095

cada0129

​

0

n/a

n/a

633,002

10

987,205

969,231

953,806

30

1,207,500

1,204,010

1,162,360

100

1,257,070

1,255,220

1,186,170

case4B

%

cada0136

cada0095

cada0129

​

0

n/a

n/a

339,213

10

475,642

461,700

470,804

30

584,771

579,469

571,747

100

606,256

608,516

591,236

case5B

%

cada0136

cada0095

cada0129

​

0

n/a

n/a

800,942

10

1,045,680

1,025,280

1,034,720

30

1,252,670

1,243,930

1,234,840

100

1,338,820

1,308,670

1,324,260

case6B

%

cada0136

cada0095

cada0129

​

0

n/a

n/a

655,131

10

985,007

971,761

953,967

30

1,186,130

1,184,140

1,143,930

100

1,223,050

1,222,250

1,154,820

© 2021 Synopsys, Inc.

10

11 of 16

Results – Runtime

  • Elapsed time (mm:ss)

​

case3

case4

case5

case6

case3B

case4B

case5B

case6B

cada0136

34:20

58:46

59:06

59:24

35:41

58:47

59:03

59:24

cada0095

00:06

07:54

25:46

52:33

00:06

07:59

24:45

48:43

cada0129

00:06

12:06

25:15

37:51

00:06

12:40

25:31

38:07

© 2021 Synopsys, Inc.

11

12 of 16

Results – Layer Power Factor

Changing power factor to 1.0 for all layers – case6 example

Util% 

 

cada0136

cada0095

cada0129

 

case6.in

contest

1.0 factor

contest

1.0 factor

contest

1.0 factor

M1

86.93%

6.96%

23.12%

1.67%

13.67%

64.83%

67.95%

M2

79.62%

67.10%

71.33%

68.93%

73.27%

69.13%

73.45%

M3

68.00%

50.60%

64.84%

51.37%

65.69%

49.31%

64.71%

M4

31.01%

8.57%

33.34%

6.97%

29.74%

7.01%

29.25%

M5

30.55%

21.35%

32.74%

22.62%

31.24%

25.83%

28.44%

M6

20.41%

30.50%

26.26%

31.16%

26.51%

36.17%

29.97%

M7

21.71%

12.23%

17.93%

12.03%

17.04%

11.66%

18.74%

M8

13.83%

8.11%

2.22%

7.87%

2.25%

7.84%

2.37%

M9

13.04%

63.24%

2.16%

61.00%

1.96%

59.20%

2.45%

M10

28.86%

74.58%

17.25%

71.35%

18.71%

68.12%

17.57%

M11

26.56%

46.40%

10.77%

44.46%

11.70%

38.09%

11.06%

M12

28.72%

36.30%

1.16%

35.28%

0.60%

31.46%

0.70%

M13

24.38%

8.41%

0.35%

5.31%

0.47%

8.62%

0.47%

M14

0.01%

7.36%

0.00%

3.96%

0.00%

7.63%

0.00%

M15

0.76%

3.43%

0.00%

1.71%

0.04%

2.89%

0.00%

M16

0.00%

1.41%

0.00%

0.68%

0.00%

2.02%

0.00%

© 2021 Synopsys, Inc.

12

13 of 16

Winners

© 2021 Synopsys, Inc.

13

14 of 16

Winners

First Place of Problem B

Canhui Luo, Jinghu Liang, Zhenxuan Xie

Advisor: Dr. Zhouxing Su, Prof. Zhipeng Lü

Team ID: cada0136

​

Second Place of Problem B

Xinshi Zang, Fangzhou Wang, Jinwei Liu,

Advisor: Prof. Evangeline F.Y. Young, Prof. Martin D.F. Wong

Team ID: cada0095

​

Third Place of Problem B

Peng Zou

Advisor: Prof. Jianli Chen, Prof. Jun Yu

Team ID: cada0129

​

Honorable Mention of Problem B

Fuheng Shen, Yangjie Mei

Advisor: Prof. Ziran Zhu, Prof. Jun Yang

Team ID: cada0006

© 2021 Synopsys, Inc.

14

15 of 16

Thank You

© 2021 Synopsys, Inc.

15

16 of 16

2021 ICCAD CAD Contest Problem B: Routing with Cell Movement Advanced

Problem Description, Benchmarks, and Results

Kai-Shun Hu, Tao-Chun Yu, Ming-Jen Yang, and Chin-Fang Cindy Shen

November 2021

© 2021 Synopsys, Inc.

16