Master Thesis

- In the appendix a library of MoPL-3 programs is shown. The library is not intended to be complete, and should be only an overview of the possibilitys if the language.
- A.1 Vector Vector Multiplication

- A.1 Vector Vector Multiplication

FUNCTION VectorVectorMultiplication (SizeXY) /* Vector-Vector Multiplication */ /* SizeXY x 1 with 1 x SizeXY giving 1x1 matrix */ /* Set memory areas for VectorP, VectorQ and Result containing integers */ array VectorP [1:SizeXY, 1:1] of int; VectorQ [1:1, 1:SizeXY] of int; Result [1:1, 1:1] of int; /* Set scan pattern for SW_P and SW_Q according to the algorithm */ scanPattern RowScan is SizeXY-1 steps [1,0]; ColScan is SizeXY-1 steps [0,1]; /* Set all scan windows to the size of 1x1 of integers */ window ProductW is SW_P, SW_Q, SW_R [1:1, 1:1] of int; /* rALU Product adds the content of SW_P multiplied by SW_Q to SW_R */ rALUsubnet Product of ProductW is SW_R [1,1] = SW_R [1,1] + SW_P [1,1] * SW_Q [1,1]; /* Activation part for the vector-vector multiplication */ begin /* Specify the scan window group ProductW */ with ProductW do begin /* Activate the rALU configuration Product */ activate Product; /* Move the scan windows to their starting positions on their arrays */ move SW_P to VectorP [1,1]; move SW_Q to VectorQ [1,1]; move SW_R to Result [1,1]; /* Start the scan with RowScan and ColScan for SW_P and SW_Q respectively */ /* that run parallel */ parbegin RowScan[SW_P]; ColScan[SW_Q]; parend; end; /* of with ProductW do begin */ end; /* of activation part */

- A.2 Vector Matrix Multiplication

FUNCTION VectorMatrixMultiplication (Width, Height) /* Vector-Matrix Multiplication */ /* Height x 1 with Width x Heigth giving Width x 1 matrix */ /* Set memory areas for VectorP, MatrixQ and Result containing integers */ array VectorP [1:Height, 1:1] of int; MatrixQ [1:Width, 1:Height] of int; Result [1:Width, 1:1] of int; /* Set scan pattern for SW_P, SW_Q and SW_R according to the algorithm */ scanPattern RowScan is Width-1 steps [1,0]; ColScan is Width-1 steps [0,1]; ORScan is Height-1 steps [1,0]; /* Set all scan windows to the size of 1x1 of integers */ window ProductW is SW_P, SW_Q, SW_R [1:1, 1:1] of int; /* rALU Product adds the content of SW_P multiplied by SW_Q to SW_R */ rALUsubnet Product of ProductW is SW_R [1,1] = SW_R [1,1] + SW_P [1,1] * SW_Q [1,1]; /* Activation part for the vector-vector multiplication */ begin /* Specify the scan window group ProductW */ with ProductW do begin /* Activate the rALU configuration Product */ activate Product; /* Move the scan windows to their starting positions on their arrays */ move SW_P to VectorP [1,1]; move SW_Q to MatrixQ [1,1]; move SW_R to Result [1,1]; /* Start the scan with RowScan and ColScan for SW_P and SW_Q respectively */ /* in parallel nested with ORScan for SW_Q and SW_R*/ ORScan(parbegin RowScan[SW_P]; ColScan[SW_Q]; parend;)[SW_Q, SW_R]; end; /* of with ProductW do begin */ end; /* of activation part */

- A.3 Matrix Matrix Multiplication

FUNCTION MatrixMatrixMultiplication (SizePxQy, SizePyRy, SizeQxRx) /* Matrix-Matrix Multiplication */ /* SizePxQy x SizePyRy with SizeQxRx x SizePxQy giving SizeQxRx x SizePyRy matrix) */ /* Set memory areas for MatrixP, MatrixQ and Result containing integers */ array MatrixP [1:SizePxQy, 1:SizePyRy] of int; MatrixQ [1:SizeQxRx, 1:SizePxQy] of int; Result [1:SizeQxRx, 1:SizePyRy] of int; /* Set scan pattern for SW_P, SW_Q and SW_R according to the algorithm */ scanPattern RowScan is SizePxQy-1 steps [1,0]; ColScan is SizePxQy-1 steps [0,1]; ORScan is SizeQxRx-1 steps [1,0]; /* Outer Row Scan */ OCScan is SizeQxRx-1 steps [1,0]; /* Outer Col Scan */ /* Set all scan windows to the size of 1x1 of integers */ window ProductW is SW_P, SW_Q, SW_R [1:1, 1:1] of int; /* rALU Product adds the content of SW_P multiplied by SW_Q to SW_R */ rALUsubnet Product of ProductW is SW_R [1,1] = SW_R [1,1] + SW_P [1,1] * SW_R [1,1]; /* Activation part for the vector-vector multiplication */ begin /* Specify the scan window group ProductW */ with ProductW do begin /* Activate the rALU configuration Product */ activate Product; /* Move the scan windows to their starting positions on their arrays */ move SW1 to MatrixP [1,1]; move SW2 to MatrixQ [1,1]; move SW3 to Result [1,1]; /* Start the scan with RowScan and ColScan for SW_P and SW_Q respectively */ /* in parallel nested with ORScan for SW_Q and SW_R and finally OCScan */ /* for SW_R and SW_P */ OCScan(ORScan(parbegin RowScan[SW_P]; ColScan[SW_Q]; parend;)[SW_R, SW_Q];)[SW_R, SW_P]; end; /* of with ProductW do begin */ end; /* of activation part */

- A.4 Gauß Algorithm

FUNCTION GaussAlgorithm4() /* Example Gauß elimination algorithm */ /* Input : Matrix of the shape [A|B] with A 4x4 matrix and B 4x1 vector */ /* Output: Matrix of the shape [U|R] with U unknown and R resulting vector*/ /* Due to a lack in hardware flexibility and limitations in MoPL-3 there */ /* is no other way to describe the algorithm more flexible. With the */ /* modifications to the software and the hardware as described in chapter */ /* 8 this algorithm can be implemented flexible in size. */ /* Set memory area for the Data containing integers with the size of 5 by 4*/ array Data [1:5, 1:4] of int; /* Set scan pattern for the Gauss algorithm */ scanPattern DiagScan is 3 steps [ 1, 1]; /* for Pivotelement */ DiagUpScan is 3 steps [-1,-1]; BackScan is 5 steps [-1, 0]; DownScan is 4 steps [ 1, 0]; UpScan is 4 steps [ 0,-1]; /* Set all scan windows to the size of 1x1 of integers */ window EliminateW is Pivot, Referenz, Dest, Src [1:1, 1:1] handle [1,1] of int; /* rALU ToOne divides the content in scan window Dest by that of Pivot */ /* This results in a one in the pivot element */ rALUsubnet ToOne of EliminateW is Dest[1,1] = Dest[1,1] / Pivot[1,1]; /* rALU Eliminate performes the substraction of two rows for each element */ /* This results in a zero in all the elements in the current povit row */ rALUsubnet Eliminate of EliminateW is Dest[1,1] = (Dest[1,1] - Referenz[1,1] * Src[1,1]) / Pivot [1,1]; resident; /* Activation part for the vector-vector multiplication */ /* Specify the scan window group ProductW */ begin with EliminateW do begin activate Eliminate; /* create upper triangle matrix */ move Pivot to Data [1,1]; move Referenz to Data [1,2]; move Dest to Data [5,2]; move Src to Data [5,1]; DownScan(BackScan[Src, Dest];) [Dest, Src]; move Pivot to Data [2,2]; move Referenz to Data [2,3]; move Dest to Data [5,3]; move Src to Data [5,2]; DownScan(BackScan[Src, Dest];) [Dest, Src]; move Pivot to Data [3,3]; move Referenz to Data [3,4]; move Dest to Data [5,4]; move Src to Data [5,3]; DownScan(BackScan[Src, Dest];) [Dest, Src]; passivate Eliminate; activate ToOne; /* make the diagonal to 1 */ move Pivot to Data [1,1]; move Dest to Data [5,1]; DownScan(BackScan[Dest];) [Dest]; move Pivot to Data [2,2]; move Dest to Data [5,2]; DownScan(BackScan[Dest];) [Dest]; move Pivot to Data [3,3]; move Dest to Data [5,3]; DownScan(BackScan[Dest];) [Dest]; move Pivot to Data [4,4]; move Dest to Data [5,4]; DownScan(BackScan[Dest];) [Dest]; remove ToOne; activate Eliminate; /* generate unity matrix*/ move Pivot to Data [4,4]; move Src to Data [5,4]; move Referenz to Data [4,3]; move Dest to Data [5,3]; UpScan[Referenz, Dest]; move Pivot to Data [3,3]; move Src to Data [5,3]; move Referenz to Data [3,2]; move Dest to Data [5,2]; UpScan[Referenz, Dest]; move Pivot to Data [2,2]; move Src to Data [5,2]; move Referenz to Data [2,1]; move Dest to Data [5,1]; UpScan[Referenz, Dest]; end; /* of with ProductW do begin */ end; /* of activation part */

- A.5 Spline Interpolation

FUNCTION SplineInterpolation (NrElements) /* Example for a spline interpolation */ /* Input : Set of points with X, Y coordinates */ /* P[1,1] and P[NrElements+1,1] must be equal to zero ! */ /* Output: U, P to calculate the function */ /* Set memory areas for the data containing floating numbers */ array X [0:NrElements+1, 1:1] of float; Y [0:NrElements+1, 1:1] of float; D [0:NrElements+1, 1:1] of float; U [0:NrElements+1, 1:1] of float; W [0:NrElements+1, 1:1] of float; P [0:NrElements+1, 1:1] of float; /* Set scan patterns for scans in both directions */ scanPattern DownScan is NrElements-1 steps [1,0]; UpScan is NrElements-1 steps [-1,0]; /* Set all scan windows to the size of 3x1 of integers */ /* for the center element and the two neighboured elements */ window XW is SW_X [1:3, 1:1] of float; SW_Y [1:3, 1:1] of float; SW_D [1:3, 1:1] of float; SW_U [1:3, 1:1] of float; SW_W [1:3, 1:1] of float; SW_P [1:3, 1:1] of float; /* rALU Load_DW calculates the initial values for D and W */ rALUsubnet Load_DW of XW is SW_D[2,1] = 2.0 * (SW_X[3,1] - SW_X[1,1]); SW_W[2,1] = 6.0 * ((SW_Y[3,1]-SW_Y[2,1])/SW_U[2,1] -(SW_Y[2,1]-SW_Y[1,1])/SW_U[1,1]); /* rALU Load_U calculates the initial values for U */ rALUsubnet Load_U of XW is SW_U[2,1] = SW_X[3,1] - SW_X[2,1]; /* rALU Calc_DW calculates the appropriate datas for D and W */ rALUsubnet Calc_DW of XW is SW_W[2,1] = SW_W[2,1]-SW_W[3,1]*SW_U[2,1]/SW_D[2,1]; SW_D[2,1] = SW_D[2,1]-SW_U[3,1]*SW_U[2,1]/SW_D[2,1]; /* rALU Calc_P calculates the appropriate datas for P */ rALUsubnet Calc_P of XW is SW_P[2,1] = SW_W[2,1]-SW_U[2,1]*SW_P[3,1]/SW_D[2,1]; /* Activation part for the vector-vector multiplication */ begin /* Specify the scan window group XW */ with XW do begin /* Activate the rALU configuration Load_U, move the scan windows to their */ /* starting positions and start the scan with the windows SW_U and SW_X */ activate Load_U; move SW_X to X [1,1]; move SW_U to U [1,1]; DownScan[SW_U, SW_X]; /* Activate the rALU configuration Load_DW, move the scan windows to their*/ /* starting positions and start the scan with the windows U, X, D, and W */ activate Load_DW; move SW_W to W [1,1]; move SW_D to D [1,1]; move SW_X to X [1,1]; move SW_U to U [1,1]; DownScan[SW_U, SW_X, SW_D, SW_W]; /* Activate the rALU configuration Calc_DW, move the scan windows to their*/ /* starting positions and start the scan with the windows U, D, and W */ activate Calc_DW; move SW_W to W [1,1]; move SW_D to D [1,1]; move SW_U to U [1,1]; DownScan[SW_U, SW_D, SW_W]; /* Activate the rALU configuration Calc_P, move the scan windows to their */ /* starting positions and start the scan with the windows U, D and W */ activate Calc_P; move SW_P to P [NrElements-1,1]; move SW_W to W [NrElements-1,1]; move SW_D to D [NrElements-1,1]; move SW_U to U [NrElements-1,1]; UpScan[SW_U, SW_D, SW_W]; end; /* of with ProductW do begin */ end; /* of activation part */

- A.6 Sharpen Algorithm

FUNCTION Sharpen (ImgWidth, ImgHeight) /* Set memory areas for image and coeffitient matrix containing integers */ array ImgData [1:ImgWidth, 1:ImgHeight] of int; CoefData [1:3, 1:3] of int; /* Set scan pattern for RowScan and ColScan according to the algorithm */ scanPattern RowScan is ImgWidth - 2 steps [1,0]; ColScan is ImgHeight - 2 steps [0,1]; /* Set the two scan windows Img and Coef to the size of 3x3 of integers */ window SharpenW is Img, Coef [1:3, 1:3] of int; /* rALU Sharpen sums up the content of every element of Img multiplied by */ /* the corresponding element of Coef to the center element of Img */ rALUsubnet Sharpen of SharpenW is Img [2,2] = Img [1,1] * Coef [1,1] + Img [2,1] * Coef [2,1] + Img [3,1] * Coef [3,1] + Img [1,2] * Coef [1,2] + Img [2,2] * Coef [2,2] + Img [3,2] * Coef [3,2] + Img [1,3] * Coef [1,3] + Img [2,3] * Coef [2,3] + Img [3,3] * Coef [3,3]; /* Activation part for the sharpen algorithm */ begin /* Specify the scan window group SharpenW */ with SharpenW do begin /* Activate the rALU configuration Sharpen */ activate Sharpen; /* Move the scan windows to their initial positions on Img- and CoefData */ move Img to ImgData [1,1]; move Coef to CoefData [1,1]; /* Start the nested scan for Img with RowScan and ColScan */ RowScan(ColScan[Img];)[Img]; end; /* of with ProductW do begin */

- end; /* of activation part */
- A.7 Shuffle Exchange

- A.7 Shuffle Exchange

FUNCTION ShuffleExchange(DataSize, DestWidth) /* Move the data from DataMap1 to DataMap2 according to the shuffle alg */ /* Set the arrays for source (DataMap1) and destination (DataMap2) */ /* to 1xDataSize each */ array DataMap1 [1:DataSize, 1:1] of int; DataMap2 [1:DataSize, 1:1] of int; /* Set scan pattern for Down1Scan (move down by one position) for source, */ /* Down3Scan (move down by three positions) and UpScan (move fife */ /* positions back upwards) for the destination data */ scanPattern Down1Scan is DataSize-1 steps [ 1, 0]; OuterDown1Scan is DestWidth-1 steps [ 1, 0]; DownNScan is DestWidth-1 steps [ DestWidth, 0]; /* Set ShuffleScan to iterate Down3Scan and UpScan until the final */ /* position at [1,DataSize] is reached */ ShuffleScan is begin while @[,<=DataSize] begin Down3Scan; UpScan; end; end; /* The scan windows SW1 and SW2 for source and destination have the size */ /* of 1x1 containing integers */ window ShuffleW is SW1, SW2 [1:1, 1:1] of int; /* The rALU configuration has to move the data from source to destination */ rALUsubnet Exchange of ShuffleW is SW2[1,1] = SW1[1,1]; /* Activation part for the shuffle exchange */ begin /* Specify the scan window group ShuffleW */ with ShuffleW do begin /* Activate the rALU configuration Exchange */ activate Exchange; /* Move the scan windows to their initial positions on DataMap1 and 2 */ move SW1 to DataMap1 [1,1]; move SW2 to DataMap2 [1,1]; /* Start the scans for source and destination parallel */ parbegin Down1Scan[SW1]; ShuffleScan[SW2]; parend; end; /* of with ProductW do begin */ end; /* of activation part */

- A.8 Fast Fourier Transformation

FUNCTION FFT (DataWidth, DataHeight) /* Example for the FFT algorithm */ /* Set array CGFFT to the size of */ /* DataWidth*DataWidth by DataHeight*2 of floating numbers */ array CGFFT [1:DataWidth*DataWidth, 1:DataHeight*2] of float; /* Specify scan pattern for scan windows SW1 (HLScan, SP1), */ /* SW2 and SW3 (HLScan, SP23) according to figure 5.5 */ scanPattern SP1 is DataHeight-1 steps [0,2]; SP23 is DataHeight-1 steps [0,1]; HLScan is DataWidth-1 steps [2,0]; /* Set scan window group ThreeW consisting of one 2x2 window and */ /* two 1x1 windows of floating numbers */ window ThreeW is SW1 [1:2, 1:2] handle [1,1] of float; SW2, SW3 [1:1, 1:1] of float; /* Set Data in SW2 and SW3 to appropriate values for FFT */ /* SW1, SW2 and SW3 are grouped togethter in scan window group ThreeW */ rALUsubnet FFT of ThreeW is SW2 [1,1] = SW1[1,1] + SW1[2,1] * SW1[1,2]; SW3 [1,1] = SW1[1,1] - SW1[2,1] * SW1[1,2]; /* Activation part for the FFT */ begin /* Specify the scan window group ThreeW */ with ThreeW do begin /* Activate the rALU configuration FFT */ activate FFT; /* Move the scan windows to their starting positions on the array CGFFT */ move SW1 to CGFFT [0,0]; move SW2 to CGFFT [2,0]; move SW3 to CGFFT [2,DataHeight]; /* Start the scan with SP1 and SP23 as the innermost scan for SW1 */ /* SW2 and SW3 that run in parallel */ /* HLScan is the outer scan that moves all three scan windows */ HLScan (parbegin SP1[SW1]; SP23[SW2]; SP23[SW3]; parend;) [SW1, SW2, SW3]; end; /* of with ThreeW do begin */ end; /* of activation part */

- A.9 n-Body Algorithm

FUNCTION nBodyAlgorithm (NrElements) /* nBody Algorithm with NrElements */ #define G 9.81 #define x0 SW1[1,1] #define y0 SW1[2,1] #define z0 SW1[3,1] #define vx0 SW1[1,2] #define vy0 SW1[2,2] #define vz0 SW1[2,3] #define m0 SW1[1,3] #define pos0 SW1[2,3] #define ax0 SW1[1,4] #define ay0 SW1[2,4] #define az0 SW1[3,4] #define aax0 SW1[1,5] #define aay0 SW1[2,5] #define aaz0 SW1[3,5] #define x1 SW2[1,1] #define y1 SW2[2,1] #define z1 SW2[3,1] #define vx1 SW2[1,2] #define vy1 SW2[2,2] #define vz1 SW2[2,3] #define m1 SW2[1,3] #define pos1 SW2[2,3] #define ax1 SW2[1,4] #define ay1 SW2[2,4] #define az1 SW2[3,4] #define aax1 SW2[1,5] #define aay1 SW2[2,5] #define aaz1 SW2[3,5] #define r sqrt ((x0-x1)*(x0-x1) + (y0-y1)*(y0-y1) + (z0-z1)*(z0-z1)) #define r3 r * r * r #define r5 r * r * r * r * r /* Set the array for NrElements objects of the size of 5x3 */ array Data [1:3, 1:NrElements*5] of float; /* Set the scan pattern to NrElements-1 steps to the right for both inner */ /* and outer scan. */ scanPattern InnerScan is NrElements-1 steps [5,0]; OuterScan is NrElements-1 steps [5,0]; /* The scan windows SW1 and SW2 have the size of 5x3 containing floats */ window nBodyW is SW1, SW2 [1:3, 1:5] of float; /* Set the rALU configuration for the nBody problem */ /* according to figure 5.11 */ rALUsubnet nBody of nBodyW is begin if (pos1 != pos0) then begin ax1 = ax1 + G * (m1 / r3) * (x0 - x1); ay1 = ay1 + G * (m1 / r3) * (y0 - y1); az1 = az1 + G * (m1 / r3) * (z0 - z1); aax1 = aax1 + G * m1 * ((vx0 - vx1) / (r3)) - (3.0 * (vx0 - vx1) * (x0 - x1) * (x0 - x1) / (r5)); aay1 = aay1 + G * m1 * ((vy0 - vy1) / (r3)) - (3.0 * (vy0 - vy1) * (y0 - y1) * (y0 - y1) / (r5)); aaz1 = aaz1 + G * m1 * ((vz0 - vz1) / (r3)) - (3.0 * (vz0 - vz1) * (z0 - z1) * (z0 - z1) / (r5)); end; end; /* Activation part for the nBody algorithm */ begin /* Specify the scan window group nBodyW */ with nBodyW do begin /* Activate the rALU configuration nBody */ activate nBody; /* Move the scan windows SW1 and SW2 to their starting positions on Data */ move SW1 to Data [1,1]; move SW2 to Data [1,1]; /* Start the nested scan OuterScan(InnerScan) for SW2 and SW1 */ OuterScan (InnerScan [SW2];) [SW1]; end; /* of with nBodyW do begin */ end; /* of activation part */

Master Thesis - 13 JAN 1997 [Next] [Previous] [Top] [Contents] [Index]

Generated with Harlequin WebMaker