Normal 0 false false false EN-US X-NONE X-NONE /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes;

Normal 0 false false false EN-US X-NONE X-NONE /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; mso-padding-alt:0in 5.4pt 0in 5.4pt; mso-para-margin-top:0in; mso-para-margin-right:0in; mso-para-margin-bottom:8.0pt; mso-para-margin-left:0in; line-height:107%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri",sans-serif; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;}

6.15. A common problem in MPI programs is converting global array indexes to

local array indexes and vice-versa.

a. Find a formula for determining a global index from a local index if the

array has a block distribution.

b. Find a formula for determining a local index from a global index if the

array has a block distribution.

c. Find a formula for determining a global index from a local index if the

array has a cyclic distribution.

d. Find a formula for determining a local index from a global index if the

array has cyclic distribution.

You can assume that the number of processes evenly divides the number of

elements in the global array. Your solutions should only use basic arithmetic

operators (+,-,*,/). They shouldn’t use any loops or branches.

6.17. a. Use Figure 6.10 to determine the maximum number of records that would

be on the stack at any one time in solving a four-city TSP. (Hint: Look at

the stack after branching as far as possible to the left).

b. Draw the tree structure that would be generated in solving a five-city TSP.

c. Determine the maximum number of records that would be on the stack at

any one time during a search of this tree.

d. Use your answers to the preceding parts to determine a formula for the

maximum number of records that would be on the stack at any one time in

solving an n-city TSP.

6.18. Breadth-first search can be implemented as an iterative algorithm using a

queue. Recall that a queue is a “first-in first-out” list data structure, in which

objects are removed, or dequeued, in the same order in which they’re added,

or enqueued. We can use a queue to solve TSP and implement breadth-first

search as follows:

queue = Init queue(); /_ Create empty queue _/

tour = Init tour(); /_ Create partial tour that visits

hometown _/

Enqueue(queue, tour);

while (!Empty(queue)) f

tour = Dequeue(queue);

if (City count(tour) == n) f

if (Best tour(tour))

Update best tour(tour);

g else f

for each neighboring city

if (Feasible(tour, city)) f

Add city(tour, city);

Enqueue(tour);

Remove last city(tour);

g

g

Free tour(tour);

g /_ while !Empty _/

This algorithm, although correct, will have serious difficulty if it’s used on a

problem with more than 10 or so cities. Why?

In the shared-memory implementations of our solutions to TSP, we use

breadth-first search to create an initial list of tours that can be divided among

the threads.

a. Modify this code so that it can be used by thread 0 to generate a queue of

at least thread count tours.

b. Once the queue has been generated by thread 0, write pseudocode that

shows how the threads can initialize their stacks with a block of tours

stored in the queue.

6.20. Suppose the stack on process/thread A contains k tours.

a. Perhaps the simplest strategy for implementing stack splitting in TSP is to

pop k=2 tours from A’s existing stack and push them onto the new stack.

Explain why this is unlikely to be a good strategy.

b. Another simple strategy is to split the stack on the basis of the cost of the

partial tours on the stack. The least-cost partial tour goes to A. The second

cheapest tour goes to new stack. The third cheapest goes to A, and so on.

Is this likely to be a good strategy? Explain your answer.

c. A variation on the strategy outlined in the preceding problem is to use

average cost per edge. In average cost per edge, the partial tours on A’s

stack are ordered according to their cost divided by the number of edges in

the partial tour. Then the tours are assigned in round-robin fashion to the

stacks, that is, the cheapest cost per edge to A, the next cheapest cost per

edge to new stack, and so on. Is this likely to be a good strategy? Explain

your answer.

Implement the three strategies outlined here in one of the dynamic loadbalancing

codes. How do these strategies compare to each other and the

strategy outlined in the text? How did you collect your data?