Wong and research team receive best paper award

ECE Professor Martin D F Wong and graduate students Lijuan Luo, Tan Yan, and Qiang Ma received the Best Paper Award at the 2010 ACM International Symposium on Physical Design (ISPD). Senior researcher Toshiyuki Shibuya of Fujitsu Lab of America was also a co-author on the paper, “B-Escape: A Simultaneous Escape Routing Algorithm Based on Boundary Routing.”

In today’s complex electronic system design, layout design of the printed circuit board (PCB), particularly the wiring process, creates a bottleneck in the overall design time. The PCB routing problem has become so difficult that no commercial design tools (auto-routers) can adequately solve it. As a result, designers often have to spend weeks or months hand-routing the board. 

Wong’s research group is actively working on this problem, aiming to develop a complete routing system that can automatically route a circuit board in hours.

The paper presents their recent work on escape routing—a key component of the routing system being developed. In modern electronics, many complex components are wired on a PCB, and the wires on every layer of the board should not cross each other.

“One key problem is to find a way to route all the pins within each component to the outside world,” Wong said. “It’s like you have a bunch of things inside a maze, and they have to simultaneously escape. You have to make sure they escape without crossing.”

Traditionally, the approach to solve this type of wiring problem is to make one pair connection at a time, routing each with a path that is as short as possible.

“We take a pair, and we try to route it as long as possible,” Wong said. “People don’t want to make a long route because it blocks other connections.”

But with their approach, carefully generated long routes leave more room for others to connect. “That’s a very counter-intuitive approach that seems to be paying off,” Wong said.

Wong and his research team work closely with industry, including IBM and Fujitsu.

“We were approached by industry saying that there are no tools, no software that can help us solve this problem,” Wong said.

They found that their result is better than existing commercial software. “We compared, and we found that there was a set of difficult escape routing problems—14 of them—we were able to completely solve all of them,” Wong said. “The leading commercial software can only solve half.”

“The PCB routing problem is far from solved,” Wong said. “We are hoping that within the next few years, we will be able to produce a software system that can completely solve this problem.”  

Luo, the first author of the paper, attributes its success to the group that worked on it.

“It was really a team work,” she said. “There were five authors, and we cooperated in every step of the project. We could see that we had some good theory in the paper, strong experimental results, and the best people writing the sections of the paper.”