4
$\begingroup$

Wikipedia says graph theory is used in computer chip design.

... travel, biology, computer chip design, and many other fields. ...

Is there a good reference for that? I can imagine optimal way to draw cpu to chip is to draw shortest hamiltonian cycle in it.

$\endgroup$
2
$\begingroup$

You might find this article of use: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.2278

$\endgroup$
2
$\begingroup$

I'm not sure what would constitute a good reference given the breadth of applications of graph theory in integrated circuit design.

You could glance at the floorplanning, placement and routing chapters of Smith's "Application specific integrated circuits" to get a feel for what is involved. It is an old book (1997) but gives a decent, fairly concise overview.

However, the term 'optimal' is hard to characterize in terms of cpu design, there are many conflicting objectives that need to be addressed. The old adage was "power, speed, area - pick two". Design (in the broad sense) has become considerably more complicated since those relatively simple days.

$\endgroup$
  • $\begingroup$ Should "breath" be "breadth"? $\endgroup$ – Code-Guru Mar 3 '13 at 0:13
  • $\begingroup$ Indeed it should, thanks... $\endgroup$ – copper.hat Mar 3 '13 at 2:54
1
$\begingroup$

I don't know about a reference. However, the intuition is that an electrical circuit in a computer chip design is etched into a flat surface. This implies that the graph model of this circuit must be a planar graph. So the theory behind planar graphs is very important in designing such circuits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.