Discrete Mathematics

Report: Two

Writing Prompt

Register allocation is the process of assigning values to a limited number of processor registers

where a register is a type of quickly accessible memory available to a computer's processor. The

register allocation problem is one central to compiler optimization.

The variables a and b are passed as input to the following sequence of tasks in a program shown in

Table 1:

1. Explain why the values of c and d need to be stored in different registers.

2. Explain why the values of f and h can use the same register.

3. Model the problem of determining the smallest number of registers as a graph coloring problem. In your model description, make sure to address:

(a) What do the vertices represent?

(b) Under what conditions should there be an edge between two vertices?

(c) How would a valid coloring for the graph yield a solution to the register allocation compiler optimization problem?

4. Produce a visualization of your graph model based on the presented sequence of Tasks. Do not provide a hand-drawn visualization. Use LaTeX's TikZ package or some point-and-click software like Lucid Chart.

5. Color your graph using as few colors as you can. In your response, make sure to address:

(a) Provide an updated visualization to show a valid coloring of your graph.

(b) Walk us through the steps of your coloring method/algorithm used to create the coloring.

(c) Provide a valid argument as to why the number of colors used in your coloring is the minimum number of colors to produce a valid coloring.

6. What is the minimum number of registers needed to complete this sequence of tasks as specified? Make sure to connect your answer back to the theory of graph coloring.

7. Show an assignment of variables to the registers R1, R1, etc.