Even if some scientists want to replace silicon by carbon to create faster computer chips, other researchers are developing faster integrated circuits from silicon by simply using computer-aided design (CAD) software based on better mathematical algorithms than commercial software. A UCLA team has shown that it is possible to reduce the wire length of current circuits by 30% by designing a more optimal chip layout. This is the equivalent of one technology generation. Moreover, the faster and smaller circuits developed with this software don't need any modification in the manufacturing process. So when will we see these faster chips? Time will tell.
The figure above shows the placement solutions offered by the UCLA's Multilevel Global Placement Tool (mPL) after different runs. You can see that cells are distributed more evenly from level to level. (Credit: UCLA VLSI CAD lab)
This research work on better circuit placement has been led by Jason Cong, UCLA professor, chair of computer science and director of the UCLA VLSI CAD lab, who collaborated with Tony Chan, UCLA professor of mathematics. Both were helped by graduate student Eric Radke.
Here are more details picked from the UCLA news release. "Integrated circuits have a series of interconnected, nanosize nodes; the locations of the nodes on the chip's surface are very important because they can minimize the wire length on which the signal travels. Nodes include tiny 'logic gates,' as well as much larger memory blocks and other functional blocks. There are tens of millions of nodes on a chip. 'We have found there is a huge amount of room for improvement in the physical design of the chip itself, including where nodes are placed,' said UCLA mathematics graduate student Eric Radke, who works with Chan and Cong. 'We want to minimize the wire length in each node.'"
And this is not an easy task according to Cong. "How do you place the nodes on a two-dimensional surface with big pieces and small pieces that are all connected to one another. It's like a jigsaw puzzle with millions of pieces. How do you place them to minimize the total interconnections (wires) among them?"
But good mathematicians and powerful computers can help. "'It's fairly easy to model this problem mathematically,' Radke said. 'You can think of the nodes as points on a giant graph, and you can think of the interconnects as hyper-edges that connect more than two nodes. We can use mathematics to determine how the placement problem should be solved. We use a mathematical technique called multiscale methods, in which we group nodes together until we get a mathematical problem that is small enough to solve.'"
For more information about the software tools used by the researchers, you can read "Multilevel Generalized Force-directed Method for Circuit Placement" (PDF format, 8 pages, 625 KB). This article obtained the Best Paper Award at the International Symposium on Physical Design (ISPD) held in San Francisco in April 2005. The above picture was extracted from this paper.
Incidentally, I was surprised by the web address of ISPD which is http://www.ispd.cc. Why did this organization choose a domain owned by Cocos (Keeling) Islands, a territory of Australia?
Anyway, Cong and Chan have already upgraded their software from mPL5 to mPL6. Please read "mPL6: Enhanced Multilevel MixedSize Placement" (PDF format, 3 pages, 114 KB), which was presented at ISPD 2006 in San Jose, for more details.
Sources: UCLA news release, December 19, 2007; and various websites
You'll find related stories by following the links below.