r6 - 02 Apr 2008 - 16:11:59 - XiaomingGuYou are here: TWiki >  Main Web > CS255Assign1

Assignment 1

  • Deadline: April 16. Please put your answer into Xiaoming's mailbox (tagged by X.GU) in CS department mailroom.


1. Give the distance vectors in the following two loop nests.
do i = 2, n
    do j = 1, n-1
        a[i,j] = a[i,j] + a[i-1,j+1]
    end do
end do

do i = 1, n
    do j = 2, n-1
        a[j] = (a[j] + a[j-1] + a[j+1])/3
    end do
end do

2. Write down the basic vectorization algorithm and the basic condition for a loop to be parallelizable (Hint: use direction vectors). Apply the basic vectorization for the following two loop nests. In addition, for each loop check whether it is parallelizable, that is, whether its iterations can be executed in parallel.
do i = 1, n
    do j = 2, n
        a[i,j] = a[i,j-1] + c
    end do
end do

do i = 1, n
    do j = 1, n
        a[i,j] = a[i-1,j] + a[i-1,j+1]
    end do
end do

3. Define may and must problems, flow-sensitive and flow-insensitive problems in interprocedural analysis. Define and classify the problems of MOD, USE and KILL.
4. Build the control dependence graph for the following control flow graph.
                                                          1
                                                        /   \
                                                       /     \
                                                      2       3
                                                     /  \    /  \
                                                    /    \  /    \
                                                   4       5      6
                                                    \       \    /
                                                     \       \  /
                                                      7       8
                                                        \    /
                                                         \  /
                                                          9
Edit | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r6 < r5 < r4 < r3 < r2 | More topic actions
 
URCS Wiki
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback