ࡱ> CEB{M Z?bjbj== CrWW3l  $Pn<\3B(-/2222222$5 "730'(0030B30000ppB20020 01:g2,2B XV 02 24,30\32 70720Parallel Solution of Unstructured Sparse Matrix Equations on a Network of Workstations Using PVM* AUSIF MAHMOOD1, GEDIMINAS KERAS1, JULIUS DICHTER1 1Computer Science and Engineering, University of Bridgeport, Bridgeport, CT 06601 ABSTRACT Parallelization of the unstructured sparse matrix solution is considered to be a challenging problem and previous studies have not yielded any speedup for circuit simulation under a coarse-grain distributed environment. This paper develops a parallel block-partitionable sparse matrix solution algorithm and implements it on a network of workstations using Parallel Virtual Machine (PVM). In our scheme, the sparse matrix is divided into equal size blocks, and different blocks are assigned to workstations according to the fill-in expected such that a good load balance is achieved in parallel execution. The algorithm developed in this work exploits sparsity at the block level as well as within a non-zero block. An efficient mapping scheme to assign different matrix blocks to workstations is developed which maximizes concurrency and minimizes communication between processors. Associated reordering and efficient sparse storage schemes are also developed. The sparse matrix solver is tested on several benchmark matrices. Speedup is obtained for all benchmark matrices tested in this work. It is expected that as the network latency and throughput improve by employing newer technologies such as ATM or gigabit eithernet, the speedup obtained here will correspondingly improve. KEY WORds Sparse matrix solution, PVM, parallel circuit simulation, distributed computing, LU decomposition. IntROduction Sparse matrix solution is encountered in many modelling and simulation problems such as ODE solvers [1], finite element analysis [2] and circuit simulation [3; 4]. These programs often use implicit methods for numerically solving systems of differential equations which transform the problem into a system of nonlinear equations. The non-linear equations are further converted to a system of linear equations by employing a Newton-type process in which the Jacobian of the derivative function determines the structure of the matrices for these linear systems. Since it often occurs that the components of the derivative function only depend on a small number of variables, the system can be considerably sparse, especially for large problems. Hence, significant computation time can be saved by using a sparse matrix solver instead of using a dense solution. Sparse matrix solution is extremely time consuming for large problems and so its parallelization is desirable to improve its execution time. Unsymmetric and unstructured nature of the sparse matrices under consideration makes it very difficult to achieve efficient parallelization [6-8]. This paper develops a parallel sparse matrix solver for use with a detailed circuit simulation program such as SPICE. Although we focus on circuit simulation, the sparse matrix solver developed here is useful for any problem involving direct solution of sparse and unstructured matrices. PREvious work Quite a few attempts have been made at parallelizing circuit simulation in the last decade [5-13]. Of these, most success has been reported in a theoretical study on systolic arrays [1], while the past work in coarse-grained implementation on a network of workstations using PVM did not produce any speedups [13]. Implementations on general purpose parallel machines have reported some success [6-9]. However, the high cost of general purpose parallel computers makes distributed computing based on an existing network of workstations more popular, despite lower communication performance (bandwidth < 10 Mbits/s and latencies 1-10ms for standard Ethernet). Although in this work we use workstations connected by standard Ethernet, parallelization techniques developed here are scalable to yield better results from the improvements in the network medium. Sparse LU Decomposition Algorithm Hwang and Cheng [14] have determined the optimal parallelism in the block-partitioned LU decomposition algorithm for a dense matrix. We have modified this algorithm to an efficient sparse form. We have devised a two-level sparse algorithm which exploits sparsity at the block level as well as with in a block. This results in a much nicer exploitation of the sparsity in the matrix with better load balancing, and detection of the fill-in band. Our Sparse LU Decomposition algorithm is shown below. The novelty of our algorithm is based on three techniques: two-level sparse storage scheme, initial reordering scheme, and sparse computations for diagonal blocks. We further describe these techniques below. Sparse Storage SCHEME We have developed a new storage scheme for our two-level sparse matrix solver. In order to conserve memory, a dynamically allocated storage for nonzero blocks is carried out. A 2-D pointer array is maintained in which a pointer either points to the nonzero block or NULL if the block is zero. This way, a fast access to nonzero blocks can be readily obtained. Implementation is as follows (fig. 2) 1) Divide the Matrix into equal size blocks according to granularity required. 2) Check each block. If it is nonzero, then dynamically allocate block storage for it and connect it to the 2-D pointer array. If the block is zero, the 2-D pointer array is initialized to NULL and no storage for the block is allocated. The above storage scheme not only conserves memory but provides a very fast access to elements of a nonzero block. Since the block-level sparisty is found to be very high (>90%) for block sizes <= 10x10 for large problems, the memory saving properties of this scheme are very good. Note that the nonzero blocks are stored in noncompact form for fast access during the block-level sparse matrix solution. However, this noncompact form is changed to compact form (Compressed Sparse Row/Column) to utilize sparsity within a block during execution. The scheme described here is also recursive in nature. i.e., the 2-D pointer array can be made to point to a large block which in turn is stored in terms of another pointer array and dynamically allocated smaller nonzero blocks. Such an indirect scheme may be needed in solution of highly sparse very large size matrices.  Reordering To Minimize Fill-in To speedup LU decomposition we can skip those computations which result in zero blocks. Fill-in is therefore an important factor in the execution time. Matrix reordering, (relabeling the nodes) can be carried out to reduce the fill-in and execution time. We devised a block-level reordering algorithm based on a modification of the Markowitzs algorithm. Our algorithm always selects the next pivot to be a diagonal block whose row-column nonzero product is the smallest. The nonzero block count for a row or column is determined from the entire matrix and not just the active submatrix as is usually done in the Markowitz algorithm at the element level. This improved reordering algorithm resulted in reduction of over 50% for some of the benchmarks that we implemented. diagonal block computations Parallel LU decomposition algorithm contains a sequence of steps. Each step involves calculating L and U inverses of the nth diagonal block (sequential part), then L blocks for nth column and U blocks for nth row (parallel part). Minimizing the time spent in sequential part of each step is crucial in achieving speedup (Amdahl's law). Calculating L and U inverses of the diagonal block involves decomposing the block into L and U parts, and finding the inverse of each. To LU decompose diagonal block, Sparse Gaussian elimination [14] was used in previous work [13]. We chose to use the block level decomposition algorithm to decompose a single block. We form "stripes" of single elements and perform calculations sequentially. This method exploits sparsity of the block the same way as the Sparse Gaussian Elimination does, and the complexity of the two algorithms is the same, only our approach does not require extra step of conversion because it does not need the input to be in sparse format. We have also introduced a sparse inverse calculation algorithm for L and U parts of the diagonal block. In the previous work [13], inverse calculation algorithm by Hwang and Cheng was used. This algorithm did not use element level sparsity of the block. Our inverse calculation algorithm exploits the sparsity of the block, decreasing the inverse computation time. The algorithm also produces CSR and CSC representations of L and U inverses of the block at no additional cost, so we again eliminate conversion step. Let's examine L block inverse first. By definition, AXA-1=I. Consider 5X5 matrix (fig. 3) - calculating i41 is highlighted. For each value of ikt we need to scan a row of as, and add antikn to the result. Recall that we already have input matrix L in CSR format. We may thus avoid scanning the full row of as and get nonzero as directly from the CSR representation. This way algorithm complexity would be determined by the number of nonzero elements rather than by the size of the block. It is easy to see that Also, to calculate each ikx, only the values of is from the rows above kth are used. Therefore the calculations should be performed from top row down, left to right as follows (Fig. 4):  Order of Calculations for the L Inverse Similarly, sparse U inverse is calculated for the U component of the diagonal block. Results We tested several benchark circuits to verify the performance of the algorithm and also examined the effect of various improvements individually, such as block size, reordering, fill-in envelop detection and skipping computations in those blocks which will not get filled-in, load balancing scheme (assignment of matrix blocks to different processors). As an example, the performance results on a PVM implementation for the SIMM1904 (1904x1904) matrix are shown in Figure 5: Speedup for SIMM1904 benchmark matrix for a block size of 100x100 Block size impact on the speed of decomposition is shown in Fig. 6. Optimum block level size is around 100X100. Performance improvement over the previous coarse-grained algorithm [13] is more than twice for certain block sizes. Overall Algorithm Performance for Different Block Sizes CONCLSIONS LU decomposition of sparse unsymmetric matrices may be successfully paralellized over the network of LAN-connected workstations. An algorithm based on Hwang and Cheng [14] LU decomposition algorithm may be used for sparse matrix computations on distributed system. The key elements of making the distributed solution efficient is sparse storage of large matrices, reordering that minimizes fill-in, and optimized computations of the diagonal block. Significant part of execution time is spent in communication, therefore using newer technologies such as ATM or gigabit eithernet our algorithm should yeld even higher speed-ups. REFERENCES [1] De Swart, J. J. B.; Blom, J. G., Experiences with Sparse Matrix Solvers in Parallel ODE Software,| Computers & Mathematics with Applications, vol. 31, no. 9, pp. 43-55. [2] Kapadia, N.; Lichtenberg, B.; Fortes, J. A. B.; Gray, J. L.; Siegel, H. J.; Webb, K. J., Parallel Solution of Unstructured Sparse Finite Element Equations, IEEE Antennas and Propagation Society International Symposium, 1995. [3] Jacob K. White, Alberto Sangiovanni-Vincentelli, "Relaxation Techniques for the Simulation of VLSI Circuits," Kluwer Academic Publishers, 1987. [4] Nagel, L. W., "SPICE2: A Computer Program to Simulate Semiconductor Circuits," Memo. no. ERL-M520, Electronics Research Laboratory, U.C. Berkeley, May 1975. [5] Trotter, J. A., and P. Agrawal, "Circuit Simulation Algorithms on a Distributed Memory Multiprocessor System," Proc. of the ICCAD-90, pp. 438-441, 1990. [6] Cox, P., R. Burch, et al., "Direct Circuit Simulation Algorithms for Parallel Processing," IEEE Trans. on CAD of ISCAS, vol. 10, no. 6, June 1991, pp. 714-725. [7] Sadayappan, P., and V. Visvanathan, "Circuit Simulation on Shared Memory Multiprocessors," IEEE Trans. on Computers, vol. 37 no. 12, pp. 1634-1642. [8] Yang, G. C., "PARASPICE: A Parallel Circuit Simulator for Shared-Memory Multiprocessors," Proc. of the 27th Design Automation Conf., 1990, pp. 400-405. [9] Mahmood, A., S. Sparks and W. I. Baker, "Systolic Algorithms for Solving a Sparse System of Linear Equations in Circuit Simulation," Integration: The VLSI journal, vol. 19.1, 1995, pp. 83-107. [10] Sadayappan, P., "Efficient Sparse Matrix Factorization for Circuit Simulation on Vector Supercomputers," Proc. of the 26th Design Autom. Conf., 1989, pp. 13-18. [11] Vladimirescu, A., and D. O. Pederson, "Circuit Simulation on Vector Processors," Proc. of the IEEE ICCC, 1982, pp. 172-175. [12] Greer, B., "Converting SPICE to Vector Code," VLSI Sys Design, vol. VII, Jan. 1986. [13] Chilakpati, U., Parallel SOLVE for SPICE on a Network of Workstations, M.S. Project Report, Washington State University, 1995. [14] Vipin Kumar, A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing, Design and Analysis of Algorithms, The Benjamin/Cummings Publishing Company, Inc., 1994. * This research was funded in part by a grant from the National Science Foundation Center for the Design of Analog and Digital Integrated Circuits under grant # CDADIC 92-4. read_input_matrix(A) /* read and store matrix in block sparse form */ reorder_markov(A) /* reorder blocks using modified Markovitz alg. */ For i=1 to B /* B = total number of blocks in a row or column */ For k=i+1 to B send Ak,i blocks to machines that will calculate Uk,i blocks send Ai,k blocks to machines that will calculate Li,k blocks For i=1 to B /* B = total number of blocks in a row or column */ /* sequential step */ if (i > 1) compute A'i,i = Ai,i - Li,1:i-1 X U1:i-1,i /* multiply stripes */ compute Li,i and Ui,i from A'i,i /* LU decompose Ai,i */ if (i < B) compute L-1i,i from Li,i /* compute L-1i,i in CSR format */ compute U-1i,i from Ui,i /* compute U-1i,i in CSC format */ multicast Li,1:i-1 and L-1i,i to machines computing U blocks multicast U1:i-1,i and U-1i,i to machines computing L blocks /* on machines computing U blocks */ For k=i+1 to B compute Ui,k from L1:i-1,i, Uk,1:i-1, Ai,k, and L-1i,i /* on machines computing L blocks */ For k=i+1 to B compute Lk,i from Lk,1:i-1, Uk,1:i-1, Ak,i, and U-1i,i /* sequential step */ gather L and U results of ith step Two Level Sparse Partitioned LU Decomposition Algorithm Original Matrix (block size 2x2) Stored as (partial view)  EMBED Excel.Sheet.8  9 3 0 0 0 0 0 0 9 5 0 5 0 0 0 0 0 0 6 0 0 0 8 0 0 0 1 2 0 0 0 0 3 4 0 0 0 6 0 0 0 0 0 7 5 1 0 0 0 0 0 0 6 2 0 2 3 2 0 0 2 1 0 0 0 0 6 1 0 0 6 2 0 0 0 0 3 5 0 0 4 0 0 0 0 0 0 0 9 2 5 8 0 0 0 0 0 0 2 8 Storage of a Matrix for Two-Level Sparse Execution  EMBED Mathcad  Calculating L Inverse  EMBED Mathcad   EMBED Mathcad  EMBED Excel.Sheet.8  EMBED Excel.Sheet.8  `acqrVW_ a & &:&<&_&`&b&|&}&&&&&&'''''''''( (!(#(((++B+C+(,),`,l,..V//?0|0001l1~1.2C222\3 6OJQJOJQJ mHnHu6H*6H*jUmHnHuCJ5H* 0J5CJ5CJP:cd  g h u wV]sP= & F$a$$da$7d8g8Y?=!#%'''''(((((((((((dhx](())$)+C+D+(,a,l,,-..../011X22314456 v>^`> >^`>\3t33464444e555 6Q6`6667|7777777b8P9S9|9999999:<:@:C:G:N:R:Y:{:~:::::::::::::::;; ;;;#;%;(;H;O;U;W;Z;;;;;;;<<<<<<<&<(<+<q<t<{<<<<H*H*OJQJ0J6OJQJ 6OJQJ[6w6678c8d8e8f8g888889H9999 :!:-:q::::h]h d` >^`> >^`>:::;;;z;;;;;,<-<T<e<<<<<<===(=9=:=D=S=T=o=p==<<<<<<=9=:=S=T=U=k=l=n=p=>>>>>>>>>>? ? ? ? ???? ?!?#?$?7?8?9?:?>;>X>u>>>>>>>>>>>> ? ?"?#?;?^`>$&PP/ =!"#$%+ 0&PP/ =!"#$% P`!L1HȾ-5O'W? >8f(xYkU?wfw&55ieHM%lC[_,&lȇi4*,|?@#,''j0 |XL`=ܙ3wM0av͝ss0Z_aQ!h! ftO(uwO:Esp4K-8uqe\JV`fr6W9[].ީ/LuB7 fr5:EplDLuyᜲw6,ഐ+NS5kkt'll5Ʀfc`lƤcu6} {Yq MŻZ#i  ,3ygɯ[?u%-&fࢡ;dd9>rYG#q|d9>rYլkyelkXc*U2Velt{=lAO>q~ly;v5gi'!w04W]Ĉ{]7ʓx`!eee{Gv W/T/P:܁7`'l(:*mt-F`edOx@^3'5¼\Ĝb@6*+e¨x汏<ΣYݩWwÿC}@?ս+J֫W}ia}la6na/kب he {Eú,l!;-Q[!~F h j!¦դ*? WyV5|nWb§dtcRzn*}g|y\+ηH|HگzҒq:bt=t=|m%x w\7-vxNs-'Mofޱ\K:]E.Ob մ{nX^4r^ K"?ld*z9طUʓOЯO"[t{413'O>k-o5"$Nä%ߛ}3GkQӿym>${`!o+, āR*=2HxT=KA}@$b4`D kAH!!'ZXYoQB4n{3;7 YyqAL4mH/E+) =<,>M>s-fUq=荅hDJYqzP/O(<]Yoo环.{T%ְ$#k_tco0ޡeT&-_SGvȉvN 'v W!]NUtsXuȥ’AƖelbg$`۝M1<|j9szZR Q`!)+/ { v*[ tdxJ@Ld!Z1$ا bq[ *HG -Dst !3~{9G҄d\~Bgl{ҋYǡs$z׮$~-.z +|q{`_߲a* Yb9;l"VUȶm'hA;Ͽ֞ז%6F0#*aF2t\Œ dq {cuge0#*aF2tRŒ dI=0 90<aF2*aF2RU <#q w7ǺKQT5[ tDܫ Wi [7`!UJDK)Pf)l)h xZ]hGvOF#^[ b`Iڔ>Jjڴmzbb,"%U)|>YhP-ЂA+gfg;d4a~ww~fZD c_4[K%)j͔e_*?!iėX5CjrpW;JS2jb,ĝERR/2@WRzFZ#\g ?(4b]YLyܥ+cE[d,\a*1^=szdmHE-˳ei46/ղ\{'AyD+A}fYNV;Akdƪf1Rus3_I\.GwH+1k<>GYMCkK)Zѕ8/trmYsAc2X#c 50VX5cU2zs&kcn3e$c';9Ʈ0vdcw{#ƼYWaNlg˼\l{Q;3:#S7jls ʀ@wj3tUֆq/$VyʢEnbT\4~bq\iF4(S mjft|s{r8҆* Jtup3ZkQZM5f)O6?sB?}&3`8]9I .4B\Z[gl= {Ճ(5UH9,O<Ո1\\ $Vď=(I%뒥Ngf}C1ګ8yܵb?|_ ^:Ll#}3ns_?_3)E%˩SozE\)|U?)C+m2TÉQ<ղKy~Y//s@zvu';U뒙w۠7Ӧ2ROO+WoHbCyV!_ϙo~8B, E'\ijB)V Y$4?9z!eײ5>wګN=5GbMi,fè`!tbyَt..cbxZQoGsB1hQM!؄(iȅ H iKTUQ(=QC>乿?"/URɝݛ>g2mfٹ@.Cs?r7+va [G9+p aۧnwU+$b3>؊mlE61B-zJs<~;zqJ#ga,ɉMKڈKzxD2"]/tLZ~&0Lc8~[<Ǣ->$zΎ: _j)-W-kJƖdΩ5nj"wT]~ϐO鷝h~'Z6*VyNi,Zw{J #,ˑ-eeee ֆgK}KAm%|75#>HOF`8x23rf_~f |kw#FGܣz.#lޑ3YӢ}xB뎇{i[|ΣqYѲ!ɏҳc(z*+ަ ¾ٚ [,*@s֓%ՓZ( fkP0S"EFHmqָ*|*`F~lR+;C(J~q(*ڰpE6Y[F"_&aRpʊ[BN* *,f 5ˢfTPUUMJVf:,I|>&fD-k+JDڰA&CTZ%Q6G TH ml6lC{J͇¯taSf63&E٬lRTQ kl kbXhh EFѨѨ)ѰIZ͟n DE=m~wsާxsrIQz\EQ.ijC̜/xt)޾:jlnu3峊 )'m6|C{O+ + CSmZR4iU3ڦEbeh<mS2@2@=sh*wm-FFKFVe=sh:sh;ZUe'Na*JyޥڦÞoJmRma7\qR۸Tt Wmڤ iI*6)U@mP@|ˠ3 6BXTAA UdQETAD'P6TP5USP(:,j(yOO(E E3e {Vg8~fЉ0+z?O~E0_۟;}/^/ptJė͍#G1u×ON;A@xbe%(+ʧ}Qh=2Spކ+ c2Rwyh8{gT Z iϰ4 Ѿѓݻ1fDFVOv39} .QIv73}}`dw+3nvn{.nCgdu'%xB5.۪XcU,cVEqu-|ӓ98?o6v߃ȇa.{ғY O2[ 2~{g45)~8`P5mxgݘsy]ݳ8cIIv,:DSq\Z4O~3[ 1;xHFLc-ڟm3ە>2 f9llܽwTFU+(/`!^}fC)a9?nI/,xKkQsTUcE,xԆ9sYHE ZBB kAn/ŵL&P:oH4=tfJ F>3%:~3XRr.v5~ML6uVG:#蜍}g]f%~:qs,7^!#?љ[mXi=y]^V'hxO}Gkw*+7[YuҾ0rCBZ!yTyxEAQQrZ}`7{4M7+q# Yw^w9Rs6pاbu;Cc_bְM'ld8D; 5J: QZz:FAȊ%2ҫ莜“莜Bc9M-Ytkݏk#-Yw^7))31E:lchp2(הhGtx;.g n ñiGtvvHg7cGwoșO5=W乿?"/URɝݛ>g2mfٹ@.Cs?r7+va [G9+p aۧnwU+$b3>؊mlE61B-zJs<~;zqJ#ga,ɉMKڈKzxD2"]/tLZ~&0Lc8~[<Ǣ->$zΎ: _j)-W-kJƖdΩ5nj"wT]~ϐO鷝h~'Z6*VyNi,Zw{J #,ˑ-eeee ֆgK}KAm%|75#>HOF`8x23rf_~f |kw#FGܣz.#lޑ3YӢ}xB뎇{i[|ΣqYѲ!ɏҳc(z*+ަ ¾ٚ [,*@s֓%ՓZ( fkP0S"EFHmqָ*|*`F~lR+;C(J~q(*ڰpE6Y[F"_&aRpʊ[BN* *,f 5ˢfTPUUMJVf:,I|>&fD-k+JDڰA&CTZ%Q6G TH ml6lC{J͇¯taSf63&E٬lRTQ kl kbXhh EFѨѨ)ѰIZ͟n DE=m~wsާxsrIQz\EQ.ijC̜/xt)޾:jlnu3峊 )'m6|C{O+ + CSmZR4iU3ڦEbeh<mS2@2@=sh*wm-FFKFVe=sh:sh;ZUe'Na*JyޥڦÞoJmRma7\qR۸Tt Wmڤ iI*6)U@mP@|ˠ3 6BXTAA UdQETAD'P6TP5USP(:,j(yOO(E E3e {Vg8~fЉ0+z?O~E0_۟;}/^/ptJė͍#G1u×ON;A@xbe%(+ʧ}Qh=2Spކ+ c2Rwyh8{gT Z iϰ4 Ѿѓݻ1fDFVOv39} .QIv73}}`dw+3nvn{.nCgdu'%xB5.۪XcU,cVEqu-|ӓ98?o6v߃ȇa.{ғY O2[ 2~{g45)~8`P5mxgݘsy]ݳ8cIIv,:DSq\Z4O~3[ 1;xHFLc-ڟm3ە>2 f9llܽwTFU+(/DdG<  C A? 2}fC)a9?nfD`!^}fC)a9?nI/,xKkQsTUcE,xԆ9sYHE ZBB kAn/ŵL&P:oH4=tfJ F>3%:~3XRr.v5~ML6uVG:#蜍}g]f%~:qs,7^!#?љ[mXi=y]^V'hxO}Gkw*+7[YuҾ0rCBZ!yTyxEAQQrZ}`7{4M7+q# Yw^w9Rs6pاbu;Cc_bְM'ld8D; 5J: QZz:FAȊ%2ҫ莜“莜Bc9M-Ytkݏk#-Yw^7))31E:lchp2(הhGtx;.g n ñiGtvvHg7cGwoșO5=WM>s-fUq=荅hDJYqzP/O(<]Yoo环.{T%ְ$#k_tco0ޡeT&-_SGvȉvN 'v W!]NUtsXuȥ’AƖelbg$`۝M1<|j9szZR QRDd<  C A?   !"#$%&'()*+,-./0123456789;<=>?@A DXzgHIJKLMNOPQRSTUVWhZ[\]^_`abcdefijkplmnoqwrstuvxy|}~Root Entry/ FP XF@8Data : WordDocument.CrObjectPool1 XP X_978723013 FXPXOle PRINTG!CompObjf  !"#$%&'()*+,-./0123456789:;?BCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmqtuvwxyz{|}~ FMicrosoft Excel WorksheetBiff8Excel.Sheet.89qOh+'08@Xp Authorized UserAuthorized UserMicrosoft Excel@hG ~  -   2''  ' 1' 1 Arial-  2 9 2 !3 2 9 2 5 "Systemn-'- 7  2 0 2 !5 2 6 2 0 -'- 1  2 Mb0 2 M0 2 M0 2 n2 2 n!1 2 nD0 2 n0 2 n0 2 6 2 !2 2 D0 2 0 2 0 2 0 2 b0 2 0 2 0 2 4 2 !0 2 9 2 2 2 5 2 !8 2 2 2 8 -'- 2-  "-4 "- !2-4- !2-774- !27-9- !9-9- !7-9- !9-9- !7-292- !72-gg4- !2g-4- !2-4- !2-g- !Dg-i- !Bi-i22- !Bi2-4- !2-H- !H-H- !H-9- !7-4- !2-004- !20-2- !:-2- !8-222- !82-2- !:-2- !8-2- !8-F77- !F7-HUU- !HU-Hss- !Hs-H- !H-- !2-- !2-77- !27-F9F- !F9-g9g- !g9-9- !9-9- !9-9- !9-9- !9-- !2-- !2-00- !20--'- 1-'- * -4&;PUh "--%>cC^ "-- $EeRR=[--&&Zmv "--%\e|-- $hso_z--&&Zx "--%\g-- $jua--&&x "--%z-- $--&& "--%-- $--&& "--%-- $--&&k "--%{-- $mx--&&:] "--%<K-- $MZE--&&:U "--%<E-- $HR?--&&Ng "--%c^-- $eP\--&& "--%-- $--&&O--$$$ $"!"####"$%%%&&'&%$((())*)($+++,,-,+$/./0000/$21233332$54566665$87899998$;;;<<=<;$>>>??@?>$AAABBCBA$EDEFFFFE$HGHIIIIH$KJKLLLLK--&&Q--$!  !!$$####$%$$(''''()($,++++,-,$0////010$43333454$87777898$<;;;;<=<$@????@A@$DCCCCDED$HGGGGHIH$LKKKKLML--&&2"QW--$5#4#3$4%4%4%5$5#$6'5'5(5)5)6)7(6'$8*7*7+7,7,8,9+8*$:.9.9/9090:0;/:.$<1;1;2;3;3<3=2<1$>5=5=6=7=7>7?6>5$@8?8>9?:?:@:@9@8$B<A<@=A>A>B>B=B<$D?C?B@CACADAD@D?$FCECDDEEEEFEFDFC$HFGFFGGHGHHHHGHF$IJHJHKHLHLILJKIJ$KMJMJNJOJOKOLNKM$MQLQLRLSLSMSNRMQ--&&5W--$TUUTTSST$PQQPPOOP$MNNMMLLM$IJJIIHHI$EFFEEDDE$BCCBBAAB$>??>>==>$:;;::99:--&&--$$$$$$$$$$--&&X{ "--%Zi-- $kxc--& -'ObjInfo WorkbookYSummaryInformation( DocumentSummaryInformation8 A\pAuthorized User Ba= =--% <X@"1Arial1Arial1Arial1Arial1Arial"$"#,##0_);\("$"#,##0\)!"$"#,##0_);[Red]\("$"#,##0\)""$"#,##0.00_);\("$"#,##0.00\)'""$"#,##0.00_);[Red]\("$"#,##0.00\)7*2_("$"* #,##0_);_("$"* \(#,##0\);_("$"* "-"_);_(@_).))_(* #,##0_);_(* \(#,##0\);_(* "-"_);_(@_)?,:_("$"* #,##0.00_);_("$"* \(#,##0.00\);_("$"* "-"??_);_(@_)6+1_(* #,##0.00_);_(* \(#,##0.00\);_(* "-"??_);_(@_)                + ) , *   (@ @  (   `& Sheet1ZR3  @@  T0Bbb00sT00sT0bbbO{0]bb:0hbb .b|A0b'ǀ0AT00bTbTb@z0(Н0bbXz0blVbfO ]fwBwBB ]bazp0.bb.0sT0b0sT0\bT ], (.S0Hbt00,b@     ՜.+,D՜.+, PXp x my organizationj Sheet1  Worksheets 6> _PID_GUIDAN{4FF87F65-B3AF-11D2-B8F2-EC9232E62A75}_958424830F VX-XXOle CompObj TObjInfo F Mathcad 5.0MathcadMathcad9q 8 3 337 133 251 72 .MCAD 303010000 1 74 10 0 .CMD FORMAT rd=d ct=10 im=i et=3 zt=15 pr=3 mass length time charge temperature tr=0 vm=0 .CMD SET ORIGIN 0 .CMD SET TOL 0.001000000000000 .CMD SET PRNCOLWIDTH 8 .CMD SET PRNPRECISION 4 .CMD PRINT_SETUP 1.200000 0.718750 1.200000 1.200000 0 .CMD HEADER_FOOTER 1 Ole10Native Ole10ItemName<_958343323F@H^X_XOle =1 *empty* *empty* *empty* 0 1 *empty* *empty* *empty* .CMD HEADER_FOOTER_FONT fontID=14 family=Arial points=10 bold=0 italic=0 underline=0 .CMD HEADER_FOOTER_FONT fontID=15 family=Arial points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE_NAME fontID=0 name=Variables .CMD DEFINE_FONTSTYLE_NAME fontID=1 name=Constants .CMD DEFINE_FONTSTYLE_NAME fontID=2 name=Text .CMD DEFINE_FONTSTYLE_NAME fontID=4 name=User^1 .CMD DEFINE_FONTSTYLE_NAME fontID=5 name=User^2 .CMD DEFINE_FONTSTYLE_NAME fontID=6 name=User^3 .CMD DEFINE_FONTSTYLE_NAME fontID=7 name=User^4 .CMD DEFINE_FONTSTYLE_NAME fontID=8 name=User^5 .CMD DEFINE_FONTSTYLE_NAME fontID=9 name=User^6 .CMD DEFINE_FONTSTYLE_NAME fontID=10 name=User^7 .CMD DEFINE_FONTSTYLE fontID=0 family=Times^New^Roman points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=1 family=Times^New^Roman points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=2 family=Arial points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=4 family=Arial points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=5 family=Courier^New points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=6 family=System points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=7 family=Script points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=8 family=Roman points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=9 family=Modern points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=10 family=Times^New^Roman points=10 bold=0 italic=0 underline=0 .CMD UNITS U=1 .CMD DIMENSIONS_ANALYSIS 0 0 .EQN 9 1 4 0 ({5,5}10..0({0:a}NAME)[(54)10..({0:a}NAME)[(53)({0:a}NAME)[(43)10.({0:a}NAME)[(52)({0:a}NAME)[(42)({0:a}NAME)[(32)10({0:a}NAME)[(51)({0:a}NAME)[(41)({0:a}NAME)[(31)({0:a}NAME)[(21)1)*({5,5}({0:i}NAME)[(55)0..0({0:i}NAME)[(54 )({0:i}NAME)[(44)0..({0:i}NAME)[(53)({0:i}NAME)[(43)({0:i}NAME)[(33)0.({0:i}NAME)[(52)({0:i}NAME)[(42)({0:i}NAME)[(32)({0:i}NAME)[(22)0({0:i}NAME)[(51)({0:i}NAME)[(41)({0:i}NAME)[(31)({0:i}NAME)[(21)({0:i}NAME)[(11))({5,5}10..00 10...010...0100..01) 8 3 362 133 251 72 FMathcadMathcadMathcad9qCompObj>PObjInfo@Ole10NativeA Ole10ItemNamen 48 158 187 219 63 192 .MCAD 303010000 1 74 23 0 .CMD FORMAT rd=d ct=10 im=i et=3 zt=15 pr=3 mass length time charge temperature tr=0 vm=0 .CMD SET ORIGIN 0 .CMD SET TOL 0.001000000000000 .CMD SET PRNCOLWIDTH 8 .CMD SET PRNPRECISION 4 .CMD PRINT_SETUP 1.200000 -1.000000 1.200000 1.200000 0 .CMD HEADER_FOOTER 1 1 *empty* *empty* *empty* 0 1 *empty* *empty* *empty* .CMD HEADER_FOOTER_FONT fontID=14 family=Arial points=10 bold=0 italic=0 underline=0 .CMD HEADER_FOOTER_FONT fontID=15 family=Arial points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE_NAME fontID=0 name=Variables .CMD DEFINE_FONTSTYLE_NAME fontID=1 name=Constants .CMD DEFINE_FONTSTYLE_NAME fontID=2 name=Text .CMD DEFINE_FONTSTYLE_NAME fontID=4 name=User^1 .CMD DEFINE_FONTSTYLE_NAME fontID=5 name=User^2 .CMD DEFINE_FONTSTYLE_NAME fontID=6 name=User^3 .CMD DEFINE_FONTSTYLE_NAME fontID=7 name=User^4 .CMD DEFINE_FONTSTYLE_NAME fontID=8 name=User^5 .CMD DEFINE_FONTSTYLE_NAME fontID=9 name=User^6 .CMD DEFINE_FONTSTYLE_NAME fontID=10 name=User^7 .CMD DEFINE_FONTSTYLE fontID=0 family=Times^New^Roman points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=1 family=Times^New^Roman points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=2 family=Arial points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=4 family=Arial points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=5 family=Courier^New points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=6 family=System points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=7 family=Script points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=8 family=Roman points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=9 family=Modern points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=10 family=Times^New^Roman points=10 bold=0 italic=0 underline=0 .CMD UNITS U=1 .CMD DIMENSIONS_ANALYSIS 0 0 .EQN 9 1 4 0 ({5,5}10..0({0:a}NAME)[(54)10_n_u_l_l_.({0:a}NAME)[(53)({0:a}NAME)[(43)10.({0:a}NAME)[(52)({0:a}NAME)[(42)({0:a}NAME)[(32)10({0:a}NAME)[(51)({0:a}NAME)[(41)({0:a}NAME)[(31)({0:a}NAME)[(21)(1)[(_n_u_l_l_))*({5,5}({0:i}NAME)[(55)0 ..0({0:i}NAME)[(54)({0:i}NAME)[(44)0_n_u_l_l_.({0:i}NAME)[(53)({0:i}NAME)[(43)({0:i}NAME)[(33)0.({0:i}NAME)[(52)({0:i}NAME)[(42)({0:i}NAME)[(32)({0:i}NAME)[(22)0({0:i}NAME)[(51)({0:i}NAME)[(41)({0:i}NAME)[(31)({0:i}NAME)[(21)( {0:i}NAME)[(11))({5,5}(1)[(_n_u_l_l_)0..00(1)[(_n_u_l_l_)0_n_u_l_l_..0(1)[(_n_u_l_l_)0.._n_u_l_l_0(1)[(_n_u_l_l_)00..0(1)[(_n_u_l_l_)) .EQN 15 5 19 0 ({0:i}NAME)[({0:kt}NAME)(({0:t}NAME+1,{0:n}NAME<{0:k}NAME,{0:n}NAME,({0:a}NAME)[({0:nt}NAME)*({0:i}NAME)[({0:kn}NAME)){64})-({0:a}NAME)[({0:kt}NAME) ?L48 158 187 219 63 192_958424726FpgX_xXOle oCompObjpTObjInfor F Mathcad 5.0MathcadMathcad9q32 243 148 373 89 312 .MCAD 303010000 1 74 28 0 .CMD FORMAT rd=d ct=10 im=i et=3 zt=15 pr=3 mass length time charge temperature tr=0 vm=0 .CMD SET ORIGIN 0 .CMD SET TOL 0.001000000000000 .CMD SET PRNCOLWIDTH 8 .CMD SET PRNPRECISION 4 .CMD PRINT_SETUP 1.200000 0.718750 1.200000 1.200000 0 .CMD HEADER_FOOTEROle10NativesOle10ItemName_978726261& FX,XOle  1 1 *empty* *empty* *empty* 0 1 *empty* *empty* *empty* .CMD HEADER_FOOTER_FONT fontID=14 family=Arial points=10 bold=0 italic=0 underline=0 .CMD HEADER_FOOTER_FONT fontID=15 family=Arial points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE_NAME fontID=0 name=Variables .CMD DEFINE_FONTSTYLE_NAME fontID=1 name=Constants .CMD DEFINE_FONTSTYLE_NAME fontID=2 name=Text .CMD DEFINE_FONTSTYLE_NAME fontID=4 name=User^1 .CMD DEFINE_FONTSTYLE_NAME fontID=5 name=User^2 .CMD DEFINE_FONTSTYLE_NAME fontID=6 name=User^3 .CMD DEFINE_FONTSTYLE_NAME fontID=7 name=User^4 .CMD DEFINE_FONTSTYLE_NAME fontID=8 name=User^5 .CMD DEFINE_FONTSTYLE_NAME fontID=9 name=User^6 .CMD DEFINE_FONTSTYLE_NAME fontID=10 name=User^7 .CMD DEFINE_FONTSTYLE fontID=0 family=Times^New^Roman points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=1 family=Times^New^Roman points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=2 family=Arial points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=4 family=Arial points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=5 family=Courier^New points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=6 family=System points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=7 family=Script points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=8 family=Roman points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=9 family=Modern points=10 bold=0 italic=0 underline=0 .CMD DEFINE_FONTSTYLE fontID=10 family=Times^New^Roman points=10 bold=0 italic=0 underline=0 .CMD UNITS U=1 .CMD DIMENSIONS_ANALYSIS 0 0 .EQN 9 1 4 0 ({5,5}10..0({0:a}NAME)[(54)10_n_u_l_l_.({0:a}NAME)[(53)({0:a}NAME)[(43)10.({0:a}NAME)[(52)({0:a}NAME)[(42)({0:a}NAME)[(32)10({0:a}NAME)[(51)({0:a}NAME)[(41)({0:a}NAME)[(31)({0:a}NAME)[(21)(1)[(_n_u_l_l_))*({5,5}({0:i}NAME)[(55)0 ..0({0:i}NAME)[(54)({0:i}NAME)[(44)0_n_u_l_l_.({0:i}NAME)[(53)({0:i}NAME)[(43)({0:i}NAME)[(33)0.({0:i}NAME)[(52)({0:i}NAME)[(42)({0:i}NAME)[(32)({0:i}NAME)[(22)0({0:i}NAME)[(51)({0:i}NAME)[(41)({0:i}NAME)[(31)({0:i}NAME)[(21)( {0:i}NAME)[(11))({5,5}(1)[(_n_u_l_l_)0..00(1)[(_n_u_l_l_)0_n_u_l_l_..0(1)[(_n_u_l_l_)0.._n_u_l_l_0(1)[(_n_u_l_l_)00..0(1)[(_n_u_l_l_)) .EQN 15 5 19 0 ({0:i}NAME)[({0:kt}NAME)(({0:t}NAME+1,{0:n}NAME<{0:k}NAME,{0:n}NAME,({0:a}NAME)[({0:nt}NAME)*({0:i}NAME)[({0:kn}NAME)-({0:a}NAME)[({0:kt}NAME)){64}) .EQN 15 -2 28 0 ({5,5}({0:i}NAME)[(55)0..0({0:i}NAME)[(54)({0:i}NAME)[(44)0..({0:i}NAME)[(53)({0:i}NAME)[(43)({0:i}NAME)[(33)0.({0:i}NAME)[(52)({0:i}NAME)[(42)({0:i}NAME)[(32)({0:i}NAME)[(22)0({0:i}NAME)[(51)({0:i}NAME)[(41)({0:i}NAME)[(31)( {0:i}NAME)[(21)({0:i}NAME)[(11)) .EQN 19 0 25 0 ({5,5}10..0({0:a}NAME)[(54)10_n_u_l_l_.({0:a}NAME)[(53)({0:a}NAME)[(43)10.({0:a}NAME)[(52)({0:a}NAME)[(42)({0:a}NAME)[(32)10({0:a}NAME)[(51)({0:a}NAME)[(41)({0:a}NAME)[(31)({0:a}NAME)[(21)(1)[(_n_u_l_l_))*({5,5}({0:i}NAME)[(55)0 ..0({0:i}NAME)[(54)({0:i}NAME)[(44)0_n_u_l_l_.({0:i}NAME)[(53)({0:i}NAME)[(43)({0:i}NAME)[(33)0.({0:i}NAME)[(52)({0:i}NAME)[(42)({0:i}NAME)[(32)({0:i}NAME)[(22)0({0:i}NAME)[(51)({0:i}NAME)[(41)({0:i}NAME)[(31)({0:i}NAME)[(21)( {0:i}NAME)[(11))({5,5}(1)[(_n_u_l_l_)0..00(1)[(_n_u_l_l_)0_n_u_l_l_..0(1)[(_n_u_l_l_)0.._n_u_l_l_0(1)[(_n_u_l_l_)00..0(1)[(_n_u_l_l_)) 32 243 148 373 89 312 FMicrosoft Excel WorksheetBiff8Excel.Sheet.89qOh+'08@Xp Ausif MahmoodxAuthorized UserMicrosoft Excel@1PRINT"CompObjfObjInfo!$Workbook#' U (   86''  Arials-Arial ------------"Systemn-'- 86 "- - .+ "---'--- 86- "- $555 "----'--- -X$Ct t??  jj55---'--- 86X$C "-5 55---'--- 86 "-5 -tt??  jj55++yy---'--- -+ ---'--- !.---'--- . - "- %uu %uu+u%+uyu %yuuu%uu "-%%+%+?Rey%y %u- "-$nu|un---'--- .u $nu|un---'--- .u+ $+n2u+|$u+n---'--- .uy $ynuy|ruyn---'--- .u $nu|un---'--- .u $nu|un---'--- .- "- x---'--- . ---'--- .+ 2$---'--- .y r---'--- . ---'--- . ---'--- .---'--- !.---'--- 86---'--- 86---'--- 86  2 ffw02 dUUdw102 /UU/wO202 UUw302 UUw402 UUw502 ZUUZwz602 %UU%wE70---'--- 86---'--- 86  2 3 2 5 2 ##47 2 qq92 112 '13---'--- 86------'---   2 (2 Number of Workstations     ----'--- 86-----'--- P7   2 &<JArial-2 &Execution Time (Seconds)-----'--- 86- "-- Y$C---'--- W#D---'--- W#D "-L h-$hohah 2 Best2  Sequential2  Algorithm ---'--- W#D---'--- W#D "-L h- oa2 Parallel 2  Algorithm ---'--- W#D---'--- 86---'--- 86 "-- .+ - -' 86 '  ' A\pAuthorized User Ba==<X@"11Arial11Arial11Arial11Arial11Arial11Arial11Arial11Arial11Arial11Arial"$"#,##0_);\("$"#,##0\)!"$"#,##0_);[Red]\("$"#,##0\)""$"#,##0.00_);\("$"#,##0.00\)'""$"#,##0.00_);[Red]\("$"#,##0.00\)7*2_("$"* #,##0_);_("$"* \(#,##0\);_("$"* "-"_);_(@_).))_(* #,##0_);_(* \(#,##0\);_(* "-"_);_(@_)?,:_("$"* #,##0.00_);_("$"* \(#,##0.00\);_("$"* "-"??_);_(@_)6+1_(* #,##0.00_);_(* \(#,##0.00\);_(* "-"??_);_(@_)                + ) , *  ` Chart1,Sheet1!Sheet2"Sheet3bZ  3  @@  RNumber of WorkstationsParallel AlgorithmBest Sequential Algorithm xI 5v6020Z 5w+pT 5x/e 5y2. : 7 *bJ28 6bb+0740P40P4(Н0LbP<6740 b< bfOw[bazp0*bb*y$0$0%.S0Hbt001.0  A  dMbP?_*+%"0??4UT0bbT0   @M@L@@M@E@@M@A@"@M@@@&@M@A@*@M@A@^x*(  p  6O?%i]W  A"W??3` m ` m ` m PH 0(  ?3d23 O 4 3Q: 6Best Sequential AlgorithmQ ;Q ;Q3_4E4 3Q: (Parallel AlgorithmQ ;Q ;Q3_4E4D $% M 3O&Q4$% M 3O&Q4FA4 3O 3*@*@@#M43*#M! M4%  KQM3O&Q 0Number of Workstations'4%  MZ3O&Q 4Execution Time (Seconds)'4523  43d"  ~3O ~% M3OQ423 M  443_ M NM ] MM<4444eee >@  A  dMbP?_*+%" ?? U>@ A  dMbP?_*+%"?? U>@ SummaryInformation(#%DocumentSummaryInformation8_978732467( F`GXpXOle g՜.+,D՜.+,X PX|  University of BridgeportDj Sheet1Sheet2Sheet3Chart1  WorksheetsCharts 6> _PID_GUIDAN{9992ABEA-D391-11D1-A627-C812510E4726} FMicrosoft Excel WorksheetBiff8Excel.Sheet.89qOh+'08@Xp Authorized UserAuthorized UserMicrosoft Excel@¿PRINT'*@CompObjfObjInfo),Workbooky M    ^''   Arial-----------------------------------------------------------------------------------------"Systemn-'- ^ "- - S "---'--- ^- "- $>> "----'--- >K >>>pp>GG>>---'--- ^K "- >>---'--- ^ "- ppGG>AAee>>---'--- S ---'--- F---'--- F - "-   //SSwwpp,, 3f"-  //SSww,- "----'--- F ---'--- F ---'--- F  ---'--- F/ 6(---'--- FS ZL---'--- Fw ~p---'--- F ---'--- F ---'--- F ---'--- Fp wi---'--- F,, 33%%---'--- F3f - 3f"-  $---'--- F  $---'--- F  $---'--- F   $  ---'--- F/  $/6(/---'--- FS  $SZLS---'--- Fw  $w~pw---'--- F  $---'--- F  $---'--- F  $---'--- F  $---'--- F,  $,3%,---'--- F---'--- F---'--- ^---'--- ^---'--- ^  2 mmz!0 2 ``z20 2 ``z40 2 ``z60 2 c``cz|80 2 :SS:zS100 2 SSz*120 ---'--- ^---'--- ^-----'--- R#o -- "- $s;);M-- :C$$$$)s(%%0 -----'--- ^-----'--- R# -- "- $;);M-- :C$$$$)(%%0 -----'--- ^-----'--- R/# -- "- $;)(;M-- :C$$$$)(%%0 -----'--- ^-----'--- Rw#H -- "- $L;^)p;^M-- :C$$$$)L(%%0 -----'--- ^-----'--- R# -- "- $;);M-- :C$$$$)(%%0 -----'--- ^-----'--- \# -- "- $E+=W--  C,.,.+(/-P -----'--- ^---'--- ^-----'--- \-  2 1a}2 b1 Block Size  ----'--- ^-----'--- O,(  2 -0J Arial-2 -Execution Time (sec.)-----'--- ^ "-- K---'--- L---'--- L "- -2  PREVIOUS WORK---'--- L---'--- L 3f"- 3f - $2 OUR WORK---'--- L---'--- ^---'--- ^ "-- S --' ^ '  '    0 !"#$%&'()*+,-./ A\pAuthorized User Ba= => N <X@"1Arial1Arial1Arial1Arial1Arial1Arial1Arial"$"#,##0_);\("$"#,##0\)!"$"#,##0_);[Red]\("$"#,##0\)""$"#,##0.00_);\("$"#,##0.00\)'""$"#,##0.00_);[Red]\("$"#,##0.00\)7*2_("$"* #,##0_);_("$"* \(#,##0\);_("$"* "-"_);_(@_).))_(* #,##0_);_(* \(#,##0\);_(* "-"_);_(@_)?,:_("$"* #,##0.00_);_("$"* \(#,##0.00\);_("$"* "-"??_);_(@_)6+1_(* #,##0.00_);_(* \(#,##0.00\);_(* "-"??_);_(@_)                + ) , *  ` Chart1DSheet10 block size PREVIOUS WORKOUR WORK t0T0bb@ bbb  (Н0T0 bfOp\fwBwBBp\bazp0bbp\fwBwBBp\bDS0Hbt000be0sT0 ) 3 b#M-43*#M! M4% / 0yM3O)Q  Block Size'4% .#MZ3OQQ .Execution Time (sec.)'4523   43"  J 3O % M3O&Q423 M NM44444 e7@7@8@8@9@9@@@@@A@A@B@B@F@F@I@I@@P@@P@ Y@ Y@ [@ [@ f@ f@eF@<@B@:@E@<@=@:@@@6@>@9@A@5@E@5@L@<@ F@ .@ T@ ;@ @\@ K@e>  A  dMbP?_*+%MWinFax@f@MSUD WinFaxd"d??U T0bb@bb   T0    7@F@<@8@B@:@9@E@<@@@=@:@A@@@6@B@>@9@F@A@5@I@E@5@ @P@L@<@ Y@F@.@ [@T@;@ f@@\@K@~*>@ SummaryInformation(+-DocumentSummaryInformation81Table7SummaryInformation(0!H՜.+,D՜.+,4 PXp x my organizationj Sheet1Chart1  WorksheetsCharts 6> _PID_GUIDAN{EC786CC6-B3EA-11D2-B8F2-EC9232E62A75}Oh+'0 (4 P \ ht|:Parallel Solution of Unstructured Sparse Matrix Equations araAuthorized Useruth Normal.dotUJulek.d2leMicrosoft Word 9.0f@Ik@X@Xz*2)+/ { v*[`!)+/ { v*[ tdxJ@Ld!Z1$ا bq[ *HG -Dst !3~{9G҄d\~Bgl{ҋYǡs$z׮$~-.z +|q{`_߲a* Yb9;l"VUȶm'hA;Ͽ֞ז%6F0#*aF2t\Œ dq {cuge0#*aF2tRŒ dI=0 90<aF2*aF2RU <#q w7ǺKQT5[ tDܫ Wi [7빨DdM  <  C A? 2L1HȾ-5O'W?n`!L1HȾ-5O'W? >8f(xYkU?wfw&55ieHM%lC[_,&lȇi4*,|?@#,''j0 |XL`=ܙ3wM0av͝ss0Z_aQ!h! ftO(uwO:Esp4K-8uqe\JV`fr6W9[].ީ/LuB7 fr5:EplDLuyᜲw6,ഐ+NS5kkt'll5Ʀfc`lƤcu6} {Yq MŻZ#i  ,3ygɯ[?u%-&fࢡ;dd9>rYG#q|d9>rYլkyelkXc*U2Velt{=lAO>q~ly;v5gi'!w04W]Ĉ{]7ʓx`!eee{Gv W/T/P:܁7`'l(:*mt-F`edOx@^3'5¼\Ĝb@6*+e¨x汏<ΣYݩWwÿC}@?ս+J֫W}ia}la6na/kب he {Eú,l!;-Q[!~F h j!¦դ*? WyV5|nWb§dtcRzn*}g|y\+ηH|HگzҒq:bt=t=|m%x w\7-vxNs-'Mofޱ\K:]E.Ob մ{nX^4r^ K"?ld*z9طUʓOЯO"[t{413'O>k-o5"$Nä%ߛ}3GkQӿym>${Dd *<  C A? 2UJDK)Pfn`!UJDK)Pf)l)h xZ]hGvOF#^[ b`Iڔ>Jjڴmzbb,"%U)|>YhP-ЂA+gfg;d4a~ww~fZD c_4[K%)j͔e_*?!iėX5CjrpW;JS2jb,ĝERR/2@WRzFZ#\g ?(4b]YLyܥ+cE[d,\a*1^=szdmHE-˳ei46/ղ\{'AyD+A}fYNV;Akdƪf1Rus3_I\.GwH+1k<>GYMCkK)Zѕ8/trmYsAc2X#c 50VX5cU2zs&kcn3e$c';9Ʈ0vdcw{#ƼYWaNlg˼\l{Q;3:#S7jls ʀ@wj3tUֆq/$VyʢEnbT\4~bq\iF4(S mjft|s{r8҆* Jtup3ZkQZM5f)O6?sB?}&3`8]9I .4B\Z[gl= {Ճ(5UH9,O<Ո1\\ $Vď=(I%뒥Ngf}C1ګ8yܵb?|_ ^:Ll#}3ns_?_3)E%˩SozE\)|U?)C+m2TÉQ<ղKy~Y//s@zvu';U뒙w۠7Ӧ2ROO+WoHbCyV!_ϙo~8B, E'\ijB)V Y$4?9z!eײ5>wګN=5GbMi,fè՜.+,0, hp  my organizationZX4 :Parallel Solution of Unstructured Sparse Matrix Equations Title  FMicrosoft Word Document MSWoDocumentSummaryInformation8\CompObjj i0@0 Normal_HmH sH tH N@N Heading 1$$ & Fd @&a$ 5;tH u<A@< Default Paragraph Font<O< Figure$ & Fxa$ 5tH u<&@< Footnote ReferenceCJEHBB@B Body Text$hd `ha$tH uV@"V Footnote Text$@dx`@a$OJQJtH uB @2B Footer$ !h`ha$tH uBOBB Normal_noident$a$ CJOJQJ`Z;w -bxZ;  !%, w -bx    Z;V&V:cdghu   wV]sP=!#####$$$$$$$$$$$$%%$%'C'D'((a(l((-****+,--X../10012w22d4e4g444485H5555 6!6-6q66666:7;7z77777,8-8T8e888888999(999:9D9S9T9o9p99999::;:X:u:::::::::::: ; ;";#;;;<;[;` hh   www ]]]]]]]    % %%% % a(a(a( 0   \3<Z? %(=(6:=Y?Z?!#$&')*Y?"bsu::::::H,-o2$L1HȾ-5O'W?SV)2$o+, āRG\)2$)+/ { v*[E^)2$UJDK)Pf_)2$tbyَt.f)2$}fC)a9?nfn)@L,,( H($dpn \  S A  ?"\  S A  ?"~h (   3"Z  S A  ?( ` %  # I   B0CDEFT77* :"IWGzEa(;*[,{7U<ad(79;;EJ&O,;0^"DS+-<1g*#$'(@                   lB  0D % \   S  A  ?".h l d(    3"T   # l d(d Z   3 @ %  Vh " +X/   3"|Z )*4  z"`*C-2` -< # Zw2(4`  C / < Z  3 -: ` e |- # )*2Z  S A ?e |-`  *n2 #  cr  s * *f1 vZ  * 2   * 2TB  C D * 2TB  C D 2 2TB  C D * *vZ *m*n1  **n2TB  C Dnu*n1TB  C D+m*gm*TB  C D*1f1 ` < #  TB  C D<TB   C D<Z ! 3 (- +X/ lh R+ " 3"Z w <  # R+ 42 $ 5<Z % S %A ?w < >`    &# 5g5`B ' c $D " fB ( s *D"  >`  p p )# Z `B * c $D p pfB + s *D p p` , C  ,l (  B S  ?V#$'((Z; 0#F4  4"d$' 4 4v ]t](g 4 ]o 4; _Ref441425000 _978702821 _978702939 _978703369 _978703449 _978703508 _978703537 _978714584 _978714616 _978714702 _978714791 _978714835 _978714905 _978719157 _978719676 _978719748 _978719957 _978720132 _978720153 _978720269 _978720313 _978720383 _978720614 _978721043 _978721064 _978721479 _978721542 _978721604 _978721662 _978721794 _978722049 _978722081 _978722102 _978722135 _978722221 _978722286 _978722348 _978722377 _978722447 _978722801 _978722816 _978722841 _978723013 _978118110 _978726045 _978726061 _978726150 _978726174 _978726227 _978728422 _978728488 _978728509 _978728570 _978728672 _978729030 _978729045 _978731959 _978732467 OLE_LINK1k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k97;7;7;7;7;7;S;S;S;S;S;S;S;S;S;T;[;@@@@@@@@ @ @ @ @ @@@@@@@@@@@@@@@@@@@ @!@"@#@$@%@&@'@(@)@*@+@,@-@.@/@0@1@2@3@4@5@6@7@8@9@:k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k9k97;7;7;7;7;7;S;S;S;S;S;S;S;S;S;U;[;Authorized User(C:\Gedas\pap\austria_conf\keraspap21.docausifD:\word\keraspap2.docJulek&C:\Julek\papers\Iasted99\keraspap2.doc;^Q&zhh^h`.h^h`Fig. .;^Q&3c4d4f4g4[;@tZ;`@UnknownGz Times New Roman5Symbol3& z Arial3z Times[TimesLTBookman Old Style_5  CourierLTBookman Old Style"1hBaFBaFz*ZY0X4*29Parallel Solution of Unstructured Sparse Matrix EquationsAuthorized UserJulekrdDocWord.Document.89q