supercomp91 (1158319), страница 5
Текст из файла (страница 5)
(All times in this section are in seconds.) Observe that if the Distributionis [Block,Block], the number of processors must be asquare for small values of M. Also, if when N = 128the problem was too big to run on 1 processor, so aspeed-up of 4 was assumed on 4 processors. Clearlyfrom this table we see that a block size of 64 is sucient to get most of the performance out of this program.5.3 A Fast Poisson SolverAn important special case in the numerical solutionof PDEs is the solution to the Poisson equation@ 2 u + @ 2 u = f:@x2 @y2The fast Poisson solver operates by exploiting thealgebraic structure of the nite dierence operator Aassociated with the dierential operator.
A is just the5-point stencil described above. Assume a computational grid of size n by n where n = 2k + 1 for someinteger k. The basic idea is to observe that A can befactored asA= QT Qwhere Q is an block orthogonal matrix and T is blocktridiagonal. It turns out that each block of Q corresponds to a sine transform along the columns ofthe grid and the tridiagonal system that compose theblocks of T are oriented along the rows of the grid.Solving the equation A U = F becomesU = Q T 1 Q F:Our strategy for programming this example is as follows.
We will represent the grid arrays U and F eachas a linear array of vectors. A vector will be a special class with a number of builtin functions includingFFTs and sine transforms, and the linear array will be10ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooBlocked grid with local subgrids andedge vectors for neighbor communicationPartitioned GridFigure 3: Blocked Subgrid Structures for the Grid CollectionM=16,N=16, Block,WholeTimeSpeed-UpM=4,N=64, Block,BlockTimeSpeed-UpM=4,N=128, Block,BlockTimeSpeed-Upp=183.151.0p=180.131.0p=1****1.0p=242.681.94p=2||p=2||-p=421.853.80p=420.53.9p=485.064.0*p=811.697.11p=8||p=8||-p = 168.1410.21p = 166.9911.46p = 1628.6711.9Table 5: 20 CG Iterations on Grid of Size 256 by 256 on the BBN GP1000.a collection with a built in function to solve a tridiagonal system in parallel across the collection.
We willassociate the columns of the grid with the vectors andthe row dimension will go across the collection. Morespecically we dene our collection asint i, s;ElementType *a, *b, c;a = new ElementType[log2(n)];b = new ElementType[log2(n)];a[0] = x; b[0] = y;// forward eliminationfor(s = 1; s < n/2; s = 2*s){c = b[s]/a[s]; b[s+1] = -c*b[s];a[s+1] = a[s] +2*b[s+1];Y.DoSubset(i, [2*s: n-1: 2*s],(*this)(i)+=-c*((*this)(i-s))+ (*this)(i+s));}// backsolvefor(s = n/2; s >= 1; s = s/2)Y.DoSubset(i,[s: n-1: 2*s],(*this)(i)+=-b[s]*(*this)(i-s)+(*this)(i+s))/a[s]);}Collection LinearArray: DistributedArray{...public:CyclicReduction(ElementType a,ElementType b);};where the method CyclicReduction(a,b) solves asystem of tridiagonal equations of the formb xi 1 + a xi + b xi+1 = yifor i = 1; n, where the values yi are the initial elementsof the collection which are overwritten by the resultsxi .The exact code for this O(log(n)) parallel tridiagonal system solver isIn this case, the DoSubset operator evaluates theexpression argument for each instance of the variablei in the given range.
(This version of the DoSubsetoperator is not yet implemented, so the in the actualcode a more messy, but functionally identical form isused.) Notice that we have left the element type unspecied. In order for this algorithm to work properlyvoid LinearArray::CyclicReduction(ElementType x,ElementType y){11M=12,N=32, Block,Whole p = 1 p = 2 p = 3 p = 4 p = 6 p = 12Time31.1 16.69 11.52 8.94 6.35 3.63Speed-Up1.01.86 2.69 3.47 4.89 8.56Table 6: 384 CG Iterations on Grid of size 384 by 384 on the Fx2800.all we need is an element with the basic arithmeticoperators \*", \+", \/" and \+=". Because we wanteach element to represent one column of the array wecan uselocality has been preserved for each sine transform,because we have parallelized that as a set of independent transforms each done with a single processor.We have executed this code on both the alliantFx2800 and the BBN GP1000 and the results areshown in Table 7.class vector ElementTypeOf LinearArray{int n;// size of vector.float *vals; // the actual data.public:vector();vector(int size);float &operator [](int i){ return vals[i]; }vector &operator =(vector);vector operator *(vector);vector operator +(vector);friend vector operator *(float, vector);void SinTransform(vector *result);};5.4 0/1 Knapsack ProblemThe complete code for the Fast Poisson Solver nowtakes the form shown below.
We declare three lineararrays of vectors: one for the \right hand side" F , onefor the solution U, and one for a temporary Temp. Werst initialize a pair of vectors of special coecients aand b. Next we do a sine transform on each component of F leaving the results in Temp. Next we applythe cyclic reduction operator to solve the tridiagonalsystems dened by the rows of the matrix. Finally, weapply the sine transforms again to each column.LinearArray<vector> F([MAXPROC],[n+1],[Block]);LinearArray<vector> Temp([MAXPROC],[n+1],[Block]);LinearArray<vector> U([MAXPROC],[n+1],[Block]);poisson(int n){vector a(n+1);vector b(n+1);for(i = 1; i < n; i++){a[i] = 4-2 *cos(i*pi/n);b[i] = -1;}F.SinTransform(Temp);Temp.CyclicReduction(a,b);Temp.SinTransform(U);}Notice that the cyclic reduction operation solvedthe tridiagonal equations as a \vector" of tridiagonalequations parallelized across processors, i.e.
each processor participates in the solution of each equation.Furthermore it is at this stage where we do most of theinter processor communication. On the other hand,In this section we show an implementation of0/1 knapsack problems by using distributed arraycollections based on the algorithm developped bySahni[11]. The one-dimensional 0/1 knapsack problem Knap(G; C) can be dened as follows: Given aset of m dierent objects and a knapsack, each objecti has a weight wi and a prot pi, and the knapsackhas a capacity C.
C, wi, and pi are all positive integers. The problem is to nd a combination of objectsinclude in the knapsack such thatPT otalP rofit = mi=1 pizi is maximizedPsubject to mi=1 wizi Cobject i is includedwhere zi = 10 ifotherwiseThe algorithm we show here is to decompose the original problem into subproblems of smaller size, to solveall subproblems in parallel and nally combine all partial solutions into the original solution. Our algorithms will only nd out the solution of TotalProtbut not the solution vector zi . The solution vector zican be found without changing the idea of the algorithm by saving all the history of prot vectors andbacktracking from TotalProt[11].The algorithm can be divided into three phases.
Inthe rst phase of the computation, we will set up a distributed array of m dierent objects and a distributedarray of #proc prot vectors.This can be done by the followings.classint};class12object ElementTypeOf Darray{weight,profit;ProfitVect ElementTypeOf Darray {Fx2800,TimeSpeed-UpGP1000,TimeSpeed-Upp=17.511.0p=170.481.0p=23.851.95p=235.661.97p=32.632.86p=324.032.94p=61.405.36p=612.655.57p = 120.72310.38p = 12 p = 247.486.369.4211.08Table 7: Fast Poisson Solver on a 256 by 256 grid.int v[C+1];combine(int stride);};Darray<object>G([MAXPROC],[m],[Block]);Darray<ProfitVect> S([MAXPROC],[MAXPROC],[Block]);Next, we have each processor representative in thedistributed collection G perform dynamic programming on its local collection Knap(Gi ; C).
This can bedone by employing the DOALL operator. A DOALLoperator will send a message dynamic knapsack() toeach processor representative in the collection G andhave the set of processor representatives in G executethe message simultaneously. Therefore each processorrepresentative i of collection G will solve Knap(Gi ; C)by applying dynamic programming and get a protvector stored in the ith prot vector of S respectively.The prot vector of size C + 1 stands for the currentbest TotalProt under the capacity from 0 to C.The nal stage is the combining stage. The combining process combines the resulting prot vectors.Let b,d be two prot vectors for Knap(B; C) andKnap(D; C) such that B \ D = , Then prot vectore of G(B [ D; C) can be obtained in the following way:the main program which includes the dynamic programming stage and the combining stage below.
TheDoSubset operator in the program is used to send themessage combine() to an index set of ProtVector elements in the collection. The experimental result withm=16*1024, C=400 is also shown in the Table 8.main() {int stride,i,p;G.DOALL(dynamic_knapsack);p = S.max_elements();for (stride=i=p/2;i>=1;i=i/2,stride=stride/2)S.DoSubSet([0:i-1:1],S.combine,stride);}5.5 Traveling Salesman ProblemIn this section, we will discuss the traveling salesman problem as a representative example for parallelbranch and bound.
The traveling salesman problemcan be stated as follows: Given a set of cities andinner-city distances, nd a shortest tour that visits every city exactly once and returns to the starting city.The problem can be solved using branch and boundalgorithm. The program studied here will be basedon LMSK algorithm[8][10]. Our PC++ program usesthe collection called DistributedPriorityQueue fromPC++ collection libraries to manage the searchingstate space.
The experiments are conducted both onAlliant/FX-2800 and BBN GP 1000 machines.The LMSK algorithm works by partitioning the setof all possible tours into progressively smaller subsetswhich are represented on the nodes of a state-spacetree and then expanding the state space tree incrementally toward the goal node using heuristic to guide thesearch. A reduce matrix is used to calculate the lowerbounds for each subset of tours. The bound guidesthe partitioning of subsets and eventually identify anoptimal tour { when a subset is found that contains asingle tour whose cost is less than or equal to the lowerbounds for all other subsets, that the tour is optimal.Our algorithm will use DistributedPriorityQueuecollections to manage the creation and removementof state nodes in the searching space. Every elemente = combine(b; d)where ei = max0j i fbj + di j g; for i = 0; 1; :::; CThe method combine is built as a method of the ProfitVector.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
