Most of the developers building any systems are generally stuck with the problem of implementing graph algorithms. Graph algorithms are really fundamental algorithms and are applied extensively...take the following example's
1. Circuit Partitioning: The stage where the designer had come up with a netlist and technology mapping being done. Now want to partition the circuit so that highly connected blocks stay together.....So when I talk about netlist....there it goes the HYPERGRAPH. The most fundamental netlist representation so to make systems which process these hypergraphs (netlist's) you need to write code in a very generic manner because the partioned hypergraph by the partitioning algorithms will be used by the placement algorithms and it goes on and on.......hmmmm now I recollect the network stack where pointer to the packet is passed across several layers and its done in such a way that to avoid redundancy involved in copying over the stack (process stack not network stack) they use a pointer to some heap space.......similarly in EDA tools where the netlist is taken through several stages(involves verification also) and finally realized into physical geometry, the developers especially EDA tool developers need some generic implementations like STL....its really great TEMPLATE LIBRARY lets you quickly do your tasks and modify only appropriate parts of the algorithms.....but STL has no support of hypergraphs...I mean not even graphs....you need to create your own Graph Container on the existing framework.....so now to avoid this we have got GTL a great libray.....I came across it while helping a friend in implementing KLM circuit partitioning algorithm...I feel that it would be really helpful for may other computer science domains apart from CAD....
Cheers
Vamsi
No comments:
Post a Comment