Show where biased coloring helps make the right decisions

Reference no: EM13903735

The table below represents a register-interference graph. Nodes 1-6 are precolored (with colors 1-6), and nodes A-H are ordinary (non-precolored). Every pair of precolored nodes interferes, and each ordinary node interferes with nodes where there is an x in the table.

The following pairs of nodes are related by MOVE instructions:

( A, 3) (H, 3) (G, 3) (B, 2) (C, 1) (D, 6) (E, 4) (F, 5)

Assume that register allocation must be done for an 8-register machine.

a. Ignoring the MOVE instructions, and without using the coalesce heuristic, color this graph using simplify and spill. Record the sequence (stack) of simplify and potential-spill decisions, show which potential spills become actual spills, and show the coloring that results.

b. Color this graph using coalescing. Record the sequence of simplify, coalesce, freeze, and spill decisions. Identify each coalesce as Briggs- or George-style. Show how many MOVE instructions remain.

*c. Another coalescing heuristic is biased coloring. Instead of using a conservative coalescing heuristic during simplification, run the simplify-spill part of the algorithm as in part (a), but in the select part of the algorithm,

i. When selecting a color for node X that is move-related to node Y , when a color for Y has already been selected, use the same color if possible (to eliminate the MOVE).

ii. When selecting a color for node X that is move-related to node Y , when a color for Y has not yet been selected, use a color that is not the same as the color of any of Y 's neighbors (to increase the chance of heuristic (i) working when Y is colored).

Conservative coalescing (in the simplify phase) has been found to be more effective than biased coloring, in general; but it might not be on this particular graph. Since the two coalescing algorithms are used in different phases, they can both be used in the same register allocator.

*d. Use both conservative coalescing and biased coloring in allocating registers. Show where biased coloring helps make the right decisions.

Reference no: EM13903735

Questions Cloud

How can control over local marketing be managed in exporting : How can control over local marketing be managed in exporting? In franchising? How can Star- bucks, the specialty coffee retailer, maintain marketing control over its franchise operations in Japan?

What factors might make their behavior very similar : What behavioral differences would you expect to find between the managers in a large German multinational and in an American MNC in the same industry? What factors might make their behavior very similar?

What role is played by a strong brand : Visit an Internet interactive vehicle-buying service (such as AutoVantage) and compare the various makes offered. Discuss how the close comparisons possible online makes competitive advantages easier to identify. What role is played by a strong br..

What is probability that next subgroup average will fall : what is the probability that the next subgroup average will fall outside the control limits? On average, how many subgroups will have to be looked at in order to detect this shift?

Show where biased coloring helps make the right decisions : Use both conservative coalescing and biased coloring in allocating registers. Show where biased coloring helps make the right decisions.

What are the strengths and weaknesses of agency theory : What are the strengths and weaknesses of agency theory as a means of understanding executives' motivation and behaviour?

Does it appear that the process was in control : Assume that items produced are supposed to be normally distributed with mean 35 and standard deviation 3. To monitor this process, subgroups of size 5 are sampled.

What do firms hope to achieve by introducing profitsharing : What do firms hope to achieve by introducing profitsharing? How likely are they to get what they are after?

How scientific piece rates differ from standard piece rates : Why do piece rates have such a high propensity to cause a breach of the psychological contract and How do ‘scientific' piece rates differ from standard piece rates? Are they any better - and for whom?

User Account

All Pages