Consider the problem of assigning registers on a central processing unit (CPU) to the variables in...

 

Transcribed Image Text:

Consider the problem of assigning registers on a central processing unit (CPU) to the variables in a program. Since a program may have many variables and there are a limited number of registers on the CPU, assigning registers to variables is an important problem. Since only certain variables are in use at different times during the execution of the program (variables that are being used at a particular time are called alive), the real task is merely to figure out which alive variables to assign to the limited number of registers. This is a classic graph-colouring problem. For a certain program the following holds: 1. There are seven variables in use in the program. 2. Program variables A,B, and D are alive together. Program variables C,D,E, and F are alive together, and program variables A,E, and G are alive together. 3. There are four registers available for assignment to program variables. (6.1) Define the variables for this CSP. (9) (6.2) Define the domain for each variable in the CSP. (4) (6.3) Define the constraints for the variables in the CSP. (11) (6.4) Provide the constraint graph for this problem. Does a solution exist? If no solution exists, explain what parameters from the problem would have to change in order to get to a solution. (5) Consider the problem of assigning registers on a central processing unit (CPU) to the variables in a program. Since a program may have many variables and there are a limited number of registers on the CPU, assigning registers to variables is an important problem. Since only certain variables are in use at different times during the execution of the program (variables that are being used at a particular time are called alive), the real task is merely to figure out which alive variables to assign to the limited number of registers. This is a classic graph-colouring problem. For a certain program the following holds: 1. There are seven variables in use in the program. 2. Program variables A,B, and D are alive together. Program variables C,D,E, and F are alive together, and program variables A,E, and G are alive together. 3. There are four registers available for assignment to program variables. (6.1) Define the variables for this CSP. (9) (6.2) Define the domain for each variable in the CSP. (4) (6.3) Define the constraints for the variables in the CSP. (11) (6.4) Provide the constraint graph for this problem. Does a solution exist? If no solution exists, explain what parameters from the problem would have to change in order to get to a solution. (5)

Answer rating: 100% (QA)

61 Define the variables for this CSP A B C D E F G 62 Define the domain for each variable in the CSP ... View the full answer