By Richard Goering
Spurred by prize money intended to facilitate academic research, developers of three award-winning IC global routers released their code as open source this month (Nov. 2007). The move will ultimately help improve commercial IC placement and routing systems, the developers say.
The three routers are Fairly Good Router (FGR) from the University of Michigan, MaizeRouter from the University of Michigan, and BoxRouter from the University of Texas (Austin). These were the top three winning routers in a contest held at the International Symposium on Physical Design (ISPD) last spring. The IEEE Council on Design Automation (CEDA) offered to award prize money to the winning teams on the condition that their code be made available as open source by Nov. 15.
Global routing, an essential phase of the IC physical design process, defines interconnect paths between major blocks. To spark some research in this area, the Association for Computing Machinery (ACM) Special Interest Group on Design Automation (SIGDA), CEDA, and the Semiconductor Research Corp. (SRC) sponsored a contest at ISPD that drew 11 teams from universities and research institutes. In the 3D (multilayer) category, MaizeRouter took first place, BoxRouter second place, and FGR third place.
CEDA decided to “piggyback” on top of this contest and award cash prizes to the top three global routers, with the requirement that the code be available as open source, said Lou Scheffer, academic infrastructure chair of CEDA’s technical activities committee and Cadence fellow. “We want to lower the barrier to entry in academic research,” he said. With the code available, he said, other research groups can develop placers and detailed routers without having to write their own global routers.
The open-source code will help improve commercial routers by making benchmarks available, and by giving developers the ability to compare different algorithms, Scheffer said. “Industrial people tend to pick one [algorithm] and run with it because they don’t have time to write more than one,” he said. With open-source availability, he said, “you get a free comparison of techniques and you get some ideas.”
In the long run, Scheffer said, CEDA would like to see a complete open-source flow from RTL to GDSII for academic research. Two pieces were previously missing – global routing and detailed routing. With global routing now available, the challenge turns to detailed routing to round out the open-source flow.
Open-source availability of academic global routers will “absolutely” improve commercial tools in the long run, said Igor Markov, FGR co-author and associate professor of electrical engineering and computer science and the University of Michigan. “We realized the results produced by [commercial] global routers are not that strong,” he said. “They [EDA vendors] have much stronger detailed routers that compensate for the poor results of global routers. We think there’s a lot of room to improve industry global routers, and our tools will allow them to do that.”
The open-source routers will help improve academic research, Markov said, because other groups will be able to examine data structures that are too low-level to describe in papers. As with the other two routers, the current open-source license for FGR is for academic use only, and it requires that derivative works be released as open source. But the university will consider individual requests from commercial providers to license the software, he said.
“There really has been no complete global routing package out there on the web with full source,” said Michael Moffitt, MaizeRouter author and currently a postdoctoral fellow at IBM’s Austin Research Lab. With open-source availability, he said, “people can look at the details, look at how data structures work, and understand how routing algorithms differ. The other impact is that people can use this router in their place and route flows.”
Open source availability will “stimulate research for the entire global routing research community,” said David Pan, BoxRouter co-developer and professor of electrical and computer engineering at the University of Texas at Austin. “A lot of times when you read a paper and try to implement it, you cannot reproduce the results. In open source there is nothing to hide. You see everything.”
Importance of global routing
There wasn’t much research happening in global routing before BoxRouter 1.0 was presented at the Design Automation Conference in 2006, Pan said. “We improved results significantly compared to the state of the art, and that sparked a lot of research, as you can see from the ISPD routing contest,” he said. An improved version of BoxRouter was used for the ISPD contest.
Global routing is becoming more and more important, Pan said. As well as routability, he said, global routing impacts manufacturability concerns such as chemical mechanical polishing (CMP), lithography, and critical area analysis. Moffitt noted that global routing could potentially be used to guide placement engines.
“Global routing controls the success of detailed routing,” Markov said. “If the global routing is bad, the detailed routing has few chances to succeed.” In the commercial world, he noted, global routing is bundled with detailed routing, making it difficult to evaluate separately. With the lack of benchmarking for global routing, EDA providers don’t even realize they’re getting poor results, he noted.
“Up until this year, the state of global routing research was fairly poor,” said Moffitt. “I think up until this point people really hadn’t figured out global routing. It was still a mystery until this [ISPD] contest. That’s one reason I think these contests are critical for the advancement of CAD.”
Global routing is receiving more attention these days. A session at the recent ICCAD addressed global routing, and it included presentations on FGR and BoxRouter. It also included a presentation of Archer, a global router from the University of Illinois that was not included in the ISPD contest. Archer has “competitive” results compared to FGR and BoxRouter, Markov said.
An intelligent router
If it wasn’t for the ISPD contest, Moffitt wouldn’t have written MaizeRouter, he said. Moffitt wasn’t even a CAD researcher – he was completing his PhD in artificial intelligence (AI) at the University of Michigan at the time. “I didn’t know anything about global routing,” he said. “I hadn’t read any papers on routing. I did it just for fun. I was actually quite shocked when I won the 3D contest.”
Moffitt said he wrote most of the code for MaizeRouter, which has only around 1,500 lines of code, in a weekend. His AI background helped. “In AI, we do searches dealing with constraints, which in some sense is what you do in CAD,” he said. “There are some inspirations from AI, for instance the A* search algorithm, but I wouldn’t call it an AI router.”
MaizeRouter uses two fundamental techniques. One is “extreme edge shifting,” aimed primarily at the efficient reduction of routing congestion, and the other is “edge retraction,” a counterpart that serves to reduce unnecessary wire length. A garbage collection technique eliminates leftover routing segments produced by these edge-based operations.
Even though BoxRouter routed more circuits, and FGR had better wire length, MaizeRouter took first place in the ISPD 3D routing contest. That’s because MaizeRouter had fewer “overflows” caused by attempts to route too many nets in a grid cell, Moffitt said. “There was some controversy over whether the criteria for the contest were correct,” he noted.
FGR was written primarily by Jarrod Roy, graduate student at the University of Michigan. Compared to MaizeRouter, Markov said, FGR “is more conventional. It is much closer to what industry routers do.” FGR uses a mathematical construct called Lagrange multipliers, also used by industry routers, but claims to do so with greater mathematical rigor and performance.
FGR, which took first place in the ISPD 2D routing contest and third place in the 3D contest, claims 10.6 percent better wire length than BoxRouter and 9.1 percent better wire length than MaizeRouter.
What’s unique about BoxRouter, Pan said, is that it has a “box expansion” approach. It does pre-routing on congested areas, and then gradually expands the congested box. It also uses a formulation called integer linear programming. “People think that’s slow, but we have a very fast way to do the box expansion, so the problem size is manageable,” he said. BoxRouter’s primary author is student Minsik Cho.
The ISPD contest used an ISPD 1998 benchmark suite, along with updated ISPD 2007 benchmarks representing much larger circuits. At ICCAD, Pan noted, the BoxRouter presentation included some “mission impossible type benchmarks” derived by taking circuits from the ISPD 1998 suite and making them “barely routable.”
Markov said that the release of the open-source routers helps fulfill a 2005 IEEE Computer-Aided Network Design (CANDE) prediction that an open-source RTL-to-GDSII design suite will exist by 2010. But detailed routing is still needed, and that will be a harder problem to solve, he said.
Pan said that an open-source RTL-to-GDSII system would be good for academic research, but he’s unsure of its long term impact on the EDA industry. “Will open-source grow the entire EDA pie? I am not sure,” he said. Pan also agreed that detailed routing is a tough problem. “The industry is mostly trying to satisfy hundreds of complicated rules from fabs, and we don’t have access to those rules in academia,” he said. “My dream router is one with simple rules with good fidelity, and fast models at different levels of abstraction.”