Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
cannonAsync.c
Go to the documentation of this file.
1 /*
2 * cannonAsync.c
3 * Hitmap example
4 * Cannon's algorithm for Matrix Multiplication
5 *
6 * Asynchronous communications
7 *
8 * v1.1
9 * (c) 2007-2010, Arturo Gonzalez-Escribano
10 */
11 
12 /*
13  * <license>
14  *
15  * Hitmap v1.2
16  *
17  * This software is provided to enhance knowledge and encourage progress in the scientific
18  * community. It should be used only for research and educational purposes. Any reproduction
19  * or use for commercial purpose, public redistribution, in source or binary forms, with or
20  * without modifications, is NOT ALLOWED without the previous authorization of the copyright
21  * holder. The origin of this software must not be misrepresented; you must not claim that you
22  * wrote the original software. If you use this software for any purpose (e.g. publication),
23  * a reference to the software package and the authors must be included.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS "AS IS" AND ANY
26  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
27  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
28  * THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
29  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34  *
35  * Copyright (c) 2007-2015, Trasgo Group, Universidad de Valladolid.
36  * All rights reserved.
37  *
38  * More information on http://trasgo.infor.uva.es/
39  *
40  * </license>
41 */
42 
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <hitmap.h>
46 
47 #define max(a,b) ((a)>(b)) ? (b):(a)
48 
49 hit_tileNewType( double );
50 
51 #define MATRIX_AROWS 10
52 #define MATRIX_ACOLUMNS 20
53 #define MATRIX_BCOLUMNS 10
54 
57 
58 void cannonsMM( int n, int m, int p );
59 
60 
61 /* A. MAIN: INVOCATION OF CANNON'S ALGORITHM */
62 int main(int argc, char *argv[]){
63  hit_comInit( &argc, &argv );
64 
66 
68  return 0;
69 }
70 
71 
72 /* B. FUNCTION TO COMPUTE THE PRODUCT OF TWO LOCAL SUBMATRICES */
73 void matrixBlockProduct( HitTile_double A, HitTile_double B, HitTile_double C ) {
74  int i,j,k;
75 #ifdef OPTIMIZE_PRODUCT
76  double *datas[3] = { C.data, A.data, B.data };
77  int rowSizes[3] ={ C.origAcumCard[1],A.origAcumCard[1],B.origAcumCard[1] };
78 # ifdef OPTIMIZE_LOOPS
79  int loopLimits[3] = { hit_tileDimCard(C,0), hit_tileDimCard(C,1), hit_tileDimCard(A,1) };
80  for (i=0; i<loopLimits[0]; i++) {
81  for (j=0; j<loopLimits[1]; j++) {
82  for (k=0; k<loopLimits[2]; k++) {
83 # else
84  for (i=0; i<hit_tileDimCard(C,0); i++) {
85  for (j=0; j<hit_tileDimCard(C,1); j++) {
86  for (k=0; k<hit_tileDimCard(A,1); k++) {
87 # endif
88 #else
89  for (i=0; i<hit_tileDimCard(C,0); i++) {
90  for (j=0; j<hit_tileDimCard(C,1); j++) {
91  for (k=0; k<hit_tileDimCard(A,1); k++) {
92 #endif
93 
94 #ifdef OPTIMIZE_PRODUCT
95  datas[0][i*rowSizes[0]+j] =
96  datas[0][i*rowSizes[0]+j] + datas[1][i*rowSizes[1]+k] * datas[2][k*rowSizes[2]+j] ;
97 #else
98  hit_tileElemAtNoStride(C,2,i,j) =
99  hit_tileElemAtNoStride(C,2,i,j)
100  + hit_tileElemAtNoStride(A,2,i,k) * hit_tileElemAtNoStride(B,2,k,j);
101 #endif
102  }
103  }
104  }
105 }
106 
107 
108 /* C. INITIALIZE MATRICES */
109 void initMatrices( int m, int p,
110  HitTile_double tileA, HitTile_double tileB, HitTile_double tileC,
111  HitLayout layA, HitLayout layB ) {
112  /* 1. INIT C = 0 */
113  double zero=0;
114  hit_tileFill( &tileA, &zero );
115  hit_tileFill( &tileB, &zero );
116  hit_tileFill( &tileC, &zero );
117 
118 #if defined(READ_AB) || defined(WRITE_AB)
119  HitTile_double realTileA, realTileB;
120  hit_tileSelectArrayCoords( &realTileA, &tileA, hit_layShape( layA ) );
121  hit_tileSelectArrayCoords( &realTileB, &tileB, hit_layShape( layB ) );
122 #endif
123 
124 #ifdef READ_AB
125 #ifdef READ_BIN
126  hit_tileFileRead( &realTileA, "A.in", HIT_FILE_ARRAY );
127  hit_tileFileRead( &realTileB, "B.in", HIT_FILE_ARRAY );
128 #else
129  hit_tileTextFileRead( &realTileA, "A.in.dtxt", HIT_FILE_ARRAY, HIT_FILE_DOUBLE, 14, 4 );
130  hit_tileTextFileRead( &realTileB, "B.in.dtxt", HIT_FILE_ARRAY, HIT_FILE_DOUBLE, 14, 4 );
131 #endif
132 #else
133  int i,j;
134 
135  /* 2. INIT A(i,j) = ( i*numCol + j ) % 1000 */
136  hit_layForDimDomain( layA, 0, i )
137  hit_layForDimDomain( layA, 1, j )
138  hit_tileElemAtArrayCoords( tileA, 2, i,j ) = ( i * m + j ) % 1000;
139 
140  /* 3. INIT B: DIFFERENT COMPILE-TIME OPTIONS */
141 #ifdef B_IDENTITY
142  /* 3.a. INIT B = Identity */
143  hit_layForDimDomain( layB, 0, i )
144  hit_layForDimDomain( layB, 1, j )
145  hit_tileElemAtArrayCoords( tileB, 2, i,j ) = (i==j) ? 1.0 : 0.0;
146 #else
147  /* 3.b. INIT B = Random with seed */
148  srand48( 364543 );
149  for (i=0; i<m; i++) {
150  for (j=0; j<p; j++) {
151  if ( i>=hit_layDimBegin(layB,0) && i<=hit_layDimEnd(layB,0) && j>=hit_layDimBegin(layB,1) && j<=hit_layDimEnd(layB,1) )
152  hit_tileElemAtArrayCoords( tileB, 2, i,j ) = drand48();
153  else drand48();
154  }
155  }
156 #endif
157 #endif
158 #ifdef WRITE_AB
159  /* 4. WRITE A,B ON FILES */
160 #ifdef WRITE_BIN
161  hit_tileFileWrite( &realTileA, "A.out", HIT_FILE_ARRAY );
162  hit_tileFileWrite( &realTileB, "B.out", HIT_FILE_ARRAY );
163 #else
164 #ifdef WRITE_TILE_FILES
165  char name[8];
166  sprintf(name, "A.%d", hit_Rank );
167  hit_tileTextFileWrite( &realTileA, name, HIT_FILE_TILE, HIT_FILE_DOUBLE, 14, 4 );
168  sprintf(name, "B.%d", hit_Rank );
169  hit_tileTextFileWrite( &realTileB, name, HIT_FILE_TILE, HIT_FILE_DOUBLE, 14, 4 );
170 #endif
171  hit_tileTextFileWrite( &realTileA, "A.out.dtxt", HIT_FILE_ARRAY, HIT_FILE_DOUBLE, 14, 4 );
172  hit_tileTextFileWrite( &realTileB, "B.out.dtxt", HIT_FILE_ARRAY, HIT_FILE_DOUBLE, 14, 4 );
173 #endif
174 #endif
175 }
176 
177 
178 /* D. PARALLEL CANNON'S ALGORITHM FOR MATRIX MULTIPLICATION */
179 void cannonsMM( int n, int m, int p ) {
180  /* 0. INIT CLOCKS */
182  hit_clockStart( mainClock );
183  hit_clockReset( productClock );
184 
185  /* 1. CREATE VIRTUAL TOPOLOGY */
186  HitTopology topo = hit_topology( plug_topSquare );
187 
188  /* 2. DECLARE FULL MATRICES WITHOUT MEMORY */
189  HitTile_double A, B, C;
190  hit_tileDomain( &A, double, 2, n, m );
191  hit_tileDomain( &B, double, 2, m, p );
192  hit_tileDomain( &C, double, 2, n, p );
193 
194  /* 3. COMPUTE PARTITIONS */
195 #define LAYOUT_BALANCED
196 #ifdef LAYOUT_BALANCED
197  HitLayout layA = hit_layout(plug_layBlocksBalance, topo, hit_tileShape( A ), 0, 0.8f );
198  HitLayout layC = hit_layout(plug_layBlocksBalance, topo, hit_tileShape( C ), 0, 0.8f );
199 #else
200  HitLayout layA = hit_layout(plug_layBlocks, topo, hit_tileShape( A ) );
201  HitLayout layC = hit_layout(plug_layBlocks, topo, hit_tileShape( C ) );
202 #endif
203  HitLayout layB = hit_layout(plug_layBlocks, topo, hit_tileShape( B ) );
204 
205  hit_layWrapNeighbors( &layA );
206  hit_layWrapNeighbors( &layB );
207 
208  /* 4. CREATE AND ALLOCATE TILES */
209  HitTile_double tileA, tileB, tileC, copyTileA, copyTileB;
210  hit_tileSelectNoBoundary( &tileA, &A, hit_layMaxShape(layA));
211  hit_tileSelectNoBoundary( &tileB, &B, hit_layMaxShape(layB) );
212  hit_tileSelect( &tileC, &C, hit_layShape(layC) );
213  hit_tileAlloc( &tileA ); hit_tileAlloc( &tileB ); hit_tileAlloc( &tileC );
214  hit_tileClone( &copyTileA, &tileA ); hit_tileClone( &copyTileB, &tileB );
215 
216  /* 5. INITIALIZE MATRICES */
217  initMatrices( m, p, tileA, tileB, tileC, layA, layB );
218 
219  /* 6. INITIAL ALIGNMENT PHASE */
220  HitCom commRow, commColumn;
221  commRow = hit_comShiftDim( layA, 1, -hit_laySelfRanksDim(layA,0), &tileA, HIT_DOUBLE );
222  commColumn = hit_comShiftDim( layB, 0, -hit_laySelfRanksDim(layB,1), &tileB, HIT_DOUBLE );
223 
224  hit_comDo( &commRow );
225  hit_comDo( &commColumn );
226  hit_comFree( commRow );
227  hit_comFree( commColumn );
228 
229  /* 7. REPEATED COMM PATTERN */
230  HitPattern shift = hit_pattern( HIT_PAT_UNORDERED );
231  hit_comTagSet( TAG_A, TAG_B );
232  hit_patternAdd( &shift, hit_comShiftDimAsync(layA, 1, 1, &tileA, &copyTileA, HIT_DOUBLE, TAG_A));
233  hit_patternAdd( &shift, hit_comShiftDimAsync(layB, 0, 1, &tileB, &copyTileB, HIT_DOUBLE, TAG_B));
234 
235  /* 8. DO COMPUTATION */
236  int loopIndex;
237  int loopLimit = max( layA.numActives[0], layA.numActives[1] );
238  for (loopIndex = 0; loopIndex < loopLimit-1; loopIndex++) {
239  /* 8.1. START COMMUNICATIONS FROM TILES TO REMOTE TILE BUFFERS */
240  hit_patternStartAsync( shift );
241 
242  /* 8.2. CLOCK TO MEASURE SECUENTIAL TIME OF THE PRODUCT */
243  hit_clockContinue( productClock );
244  matrixBlockProduct( tileA, tileB, tileC );
245  hit_clockStop( productClock );
246 
247  /* 8.3. END COMMUNICATIONS, MOVE DATA FROM TILE BUFFERS */
248  hit_patternEndAsync( shift );
249  hit_tileUpdateToAncestor( &copyTileA );
250  hit_tileUpdateToAncestor( &copyTileB );
251  }
252  /* 9. LAST ITERATION MULTIPLICATION: NO COMMUNICATION AFTER */
253  hit_clockContinue( productClock );
254  matrixBlockProduct( tileA, tileB, tileC );
255  hit_clockStop( productClock );
256 
257  /* 10. CLOCK RESULTS */
258  hit_clockStop( mainClock );
259  hit_clockReduce( layC, mainClock );
260  hit_clockReduce( layC, productClock );
261  hit_clockPrintMax( mainClock );
262  hit_clockPrintMax( productClock );
263 
264  /* 11. WRITE RESULT MATRIX */
265 #ifdef WRITE_RESULT
266 #ifdef WRITE_BIN
267  hit_tileFileWrite( &tileC, "C.out", HIT_FILE_ARRAY );
268 #else
269  hit_tileTextFileWrite( &tileC, "C.dtxt", HIT_FILE_ARRAY, HIT_FILE_DOUBLE, 14, 4 );
270 #endif
271 #endif
272 
273  /* 12. FREE RESOURCES */
274  hit_tileFree( tileA ); hit_tileFree( tileB ); hit_tileFree( tileC );
275  hit_tileFree( copyTileA ); hit_tileFree( copyTileB );
276  hit_patternFree( &shift );
277  hit_layFree( layA ); hit_layFree( layB ); hit_layFree( layC );
278  hit_topFree( topo );
279 }
280 
void hit_patternEndAsync(HitPattern pattern)
Definition: hit_pattern.c:200
#define hit_layShape(lay)
Definition: hit_layout.h:650
#define hit_comTagSet(...)
Definition: hit_com.h:909
#define hit_tileNewType(baseType)
Definition: hit_tile.h:163
HitClock productClock
Definition: cannonAsync.c:56
#define A
Definition: mg.c:64
#define hit_tileFileWrite(var, file, coord)
Definition: hit_tile.h:947
#define hit_clockSynchronizeAll()
Definition: hit_utils.h:55
#define hit_tileFill(var, value)
Definition: hit_tile.h:390
void initMatrices(int m, int p, HitTile_double tileA, HitTile_double tileB, HitTile_double tileC, HitLayout layA, HitLayout layB)
Definition: cannonAsync.c:109
#define hit_Rank
Definition: hit_com.h:140
void srand48(long)
#define MATRIX_ACOLUMNS
Definition: cannonAsync.c:52
#define B
Definition: mg.c:65
void hit_comFree(HitCom issue)
Definition: hit_com.c:1995
void hit_comDo(HitCom *issue)
Definition: hit_com.c:2408
#define MATRIX_BCOLUMNS
Definition: cannonAsync.c:53
HitShape hit_layMaxShape(HitLayout lay)
Definition: hit_layout.c:1623
#define hit_clockContinue(c)
Definition: hit_utils.h:121
#define MATRIX_AROWS
Definition: cannonAsync.c:51
#define hit_tileAlloc(var)
Definition: hit_tile.h:319
#define hit_topology(name,...)
Definition: hit_topology.h:308
#define HIT_FILE_DOUBLE
Definition: hit_tile.h:189
HitClock mainClock
Definition: cannonAsync.c:55
#define hit_laySelfRanksDim(lay, dim)
Definition: hit_layout.h:857
#define hit_tileSelect(newVar, oldVar, shape)
Definition: hit_tile.h:453
#define HIT_PAT_UNORDERED
Definition: hit_pattern.h:81
void hit_patternAdd(HitPattern *pattern, HitCom comm)
Definition: hit_pattern.c:61
#define hit_clockPrintMax(c)
Definition: hit_utils.h:175
#define hit_tileDimCard(var, dim)
Definition: hit_tile.h:750
#define hit_tileFileRead(var, file, coord)
Definition: hit_tile.h:974
#define hit_clockReset(c)
Definition: hit_utils.h:78
#define hit_tileClone(newVar, oldVar)
Definition: hit_tile.h:404
#define hit_tileTextFileWrite(var, file, coord, datatype, s1, s2)
Definition: hit_tile.h:1011
void hit_topFree(HitTopology topo)
Definition: hit_topology.c:129
void hit_layWrapNeighbors(HitLayout *lay)
Definition: hit_layout.c:1593
void hit_patternFree(HitPattern *pattern)
Definition: hit_pattern.c:94
void hit_comInit(int *pargc, char **pargv[])
Definition: hit_com.c:111
#define hit_tileTextFileRead(var, file, coord, datatype, s1, s2)
Definition: hit_tile.h:1045
void cannonsMM(int n, int m, int p)
Definition: cannonAsync.c:179
#define hit_comShiftDim(lay, dim, shift, tileP, baseType)
Definition: hit_com.h:646
#define hit_tileDomain(newVarP, baseType, numDims,...)
Definition: hit_tile.h:286
#define HIT_FILE_TILE
Definition: hit_tile.h:196
#define hit_tileElemAtNoStride(var, ndims,...)
Definition: hit_tile.h:558
void hit_layFree(HitLayout lay)
Definition: hit_layout.c:2251
#define hit_clockStop(c)
Definition: hit_utils.h:109
#define HIT_FILE_ARRAY
Definition: hit_tile.h:201
int main(int argc, char *argv[])
Definition: cannonAsync.c:62
#define m(a, b, c)
#define hit_layDimEnd(lay, dim)
Definition: hit_layout.h:700
#define hit_tileSelectArrayCoords(newVar, oldVar, shape)
Definition: hit_tile.h:494
void matrixBlockProduct(HitTile_double A, HitTile_double B, HitTile_double C)
Definition: cannonAsync.c:73
#define hit_tileElemAtArrayCoords(var, ndims,...)
Definition: hit_tile.h:534
#define hit_tileUpdateToAncestor(shadow)
Definition: hit_tile.h:613
#define hit_layDimBegin(lay, dim)
Definition: hit_layout.h:695
#define hit_comShiftDimAsync(lay, dim, shift, tileSend, tileRecv, baseType, tag)
Definition: hit_com.h:661
#define hit_tileSelectNoBoundary(newVar, oldVar, shape)
Definition: hit_tile.h:434
void hit_patternStartAsync(HitPattern pattern)
Definition: hit_pattern.c:187
#define hit_layout(name, topo,...)
Definition: hit_layout.h:415
#define hit_layForDimDomain(lay, dim, index)
Definition: hit_layout.h:837
int numActives[HIT_MAXDIMS]
Definition: hit_layout.h:257
#define C
Definition: mg.c:66
#define hit_tileFree(var)
Definition: hit_tile.h:369
#define max(a, b)
Definition: cannonAsync.c:47
#define HIT_DOUBLE
Definition: hit_com.h:78
double drand48()
#define hit_tileShape(var)
Definition: hit_tile.h:723
void hit_comFinalize()
Definition: hit_com.c:159
#define hit_clockReduce(lay, c)
Definition: hit_utils.h:139
#define hit_clockStart(c)
Definition: hit_utils.h:87