Applications in Compiler Construction next up previous
Next: Related Approaches Up: Force and Energy Controlled Previous: Temperature Schemes

Applications in Compiler Construction

Although magnetic fields can be used to influence orientations of directed edges, force-directed and energy-controlled placement is mainly used for sparse, undirected graphs, e.g. symmetric relations. A typical example is the visualization of register collision graphs in compiler construction. If a compiler translates a program into machine code, it uses an infinite set of virtual processor registers at first. This is for simplicity of the code generation. Afterwards the virtual registers must be mapped to the limited number of real CPU registers. Here, the so called register collision graph helps: The nodes of this graph are the virtual registers. There is an (undirected) edge between two nodes if the life times of both virtual registers are overlapping. Register allocation is now done by coloring the graph with n colors representing n real CPU registers with the restraint that adjacent nodes must never get the same color. The problem of minimizing the number of colors (or the number of real CPU registers, resp.) is tex2html_wrap_inline2478 -complete, but there are good heuristics to solve this problem [WiMa95].

   figure481
Figure 12: Register Collision Graph

myexample489

   figure502
Figure 13: Network Topologies

Simulations of parallel programs often require the visualization of the parallel computer architecture. Because spring embedders often display symmetries, they are in particularly suitable for that. Fig. 13 shows some of these networks (see [AlGo89, Br93] for a description of these network topologies).



Georg Sander
Thu Aug 1 15:27:34 PDT 1996