API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 24th, 2014
186
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.20 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. * Himawan Go
  3. * 4943425
  4. * Section 006
  5. *
  6. * trans.c - Matrix transpose B = A^T
  7. *
  8. * Each transpose function must have a prototype of the form:
  9. * void trans(int M, int N, int A[N][M], int B[M][N]);
  10. *
  11. * A transpose function is evaluated by counting the number of misses
  12. * on a 1KB direct mapped cache with a block size of 32 bytes.
  13. */
  14. #include <stdio.h>
  15. #include "cachelab.h"
  16.  
  17. int is_transpose(int M, int N, int A[N][M], int B[M][N]);
  18.  
  19. /*
  20. * transpose_submit - This is the solution transpose function that you
  21. * will be graded on for Part B of the assignment. Do not change
  22. * the description string "Transpose submission", as the driver
  23. * searches for that string to identify the transpose function to
  24. * be graded.
  25. */
  26. char transpose_submit_desc[] = "Transpose submission";
  27. void transpose_submit(int M, int N, int A[N][M], int B[M][N])
  28. {
  29. // Temporary variables
  30. int temp1, temp2, temp3, temp4, temp5, temp6, temp7, temp8;
  31.  
  32. // Variables for iterations
  33. int row, column, i, j;
  34.  
  35. // For 64 x 64 matrix
  36. if(M == 64 && N == 64){
  37. // Block size of 8
  38. for (row = 0; row < 64; row += 8) {
  39. for (column = 0; column < 64; column += 8) {
  40. // In case of diagonal
  41. if (row == column) {
  42. // Block size of 4
  43. for (i = 0; i < 8; i += 4) {
  44. for (j = 0; j < 8; j += 4) {
  45. // Save values of upper half of the block
  46. temp1 = A[row + i][column + j];
  47. temp2 = A[row + i][column + j + 1];
  48. temp3 = A[row + i][column + j + 2];
  49. temp4 = A[row + i][column + j + 3];
  50. temp5 = A[row + i + 1][column + j];
  51. temp6 = A[row + i + 1][column + j + 1];
  52. temp7 = A[row + i + 1][column + j + 2];
  53. temp8 = A[row + i + 1][column + j + 3];
  54.  
  55. // Transposing upper half of the block
  56. B[column + j][row + i] = temp1;
  57. B[column + j][row + i + 1] = temp5;
  58. B[column + j + 1][row + i] = temp2;
  59. B[column + j + 1][row + i + 1] = temp6;
  60. B[column + j + 2][row + i] = temp3;
  61. B[column + j + 2][row + i + 1] = temp7;
  62. B[column + j + 3][row + i] = temp4;
  63. B[column + j + 3][row + i + 1] = temp8;
  64.  
  65. // Save values of bottom half of the block
  66. temp1 = A[row + i + 2][column + j ];
  67. temp2 = A[row + i + 2][column + j + 1];
  68. temp3 = A[row + i + 2][column + j + 2];
  69. temp4 = A[row + i + 2][column + j + 3];
  70. temp5 = A[row + i + 3][column + j];
  71. temp6 = A[row + i + 3][column + j + 1];
  72. temp7 = A[row + i + 3][column + j + 2];
  73. temp8 = A[row + i + 3][column + j + 3];
  74.  
  75. // Transposing bottom half of the block
  76. B[column + j][row + i + 2] = temp1;
  77. B[column + j][row + i + 3] = temp5;
  78. B[column + j + 1][row + i + 2] = temp2;
  79. B[column + j + 1][row + i + 3] = temp6;
  80. B[column + j + 2][row + i + 2] = temp3;
  81. B[column + j + 2][row + i + 3] = temp7;
  82. B[column + j + 3][row + i + 2] = temp4;
  83. B[column + j + 3][row + i + 3] = temp8;
  84. }
  85. }
  86. }
  87. else {
  88. // Transposing Row 1 Column 1 to Row 4 Column 4
  89. for (i = 0; i < 4; i++){
  90. for (j = 0; j < 4; j++){
  91. B[column + j][row + i] = A[row + i][column + j];
  92. }
  93. }
  94.  
  95. // Save values of Row 1 Column 5 to Row 2 Column 8
  96. temp1 = A[row][column + 4];
  97. temp2 = A[row][column + 5];
  98. temp3 = A[row][column + 6];
  99. temp4 = A[row][column + 7];
  100. temp5 = A[row + 1][column + 4];
  101. temp6 = A[row + 1][column + 5];
  102. temp7 = A[row + 1][column + 6];
  103. temp8 = A[row + 1][column + 7];
  104.  
  105. // Transposing Row 5 Column 1 to Row 8 Column 4
  106. for (i = 4; i < 8; i++){
  107. for (j = 0; j < 4; j++){
  108. B[column + j][row + i] = A[row + i][column + j];
  109. }
  110. }
  111.  
  112. // Transposing Row 5 Column 5 to Row 8 Column 8
  113. for (i = 4; i < 8; i++){
  114. for (j = 4; j < 8; j++){
  115. B[column + j][row + i] = A[row + i][column + j];
  116. }
  117. }
  118.  
  119. // Transposing Row 1 Column 5 to Row 2 Column 8
  120. B[column + 4][row] = temp1;
  121. B[column + 5][row] = temp2;
  122. B[column + 6][row] = temp3;
  123. B[column + 7][row] = temp4;
  124. B[column + 4][row + 1] = temp5;
  125. B[column + 5][row + 1] = temp6;
  126. B[column + 6][row + 1] = temp7;
  127. B[column + 7][row + 1] = temp8;
  128.  
  129. // Transposing Row 3 Column 5 to Row 4 Column 8
  130. for (i = 2; i < 4; i++){
  131. for (j = 4; j < 8; j++){
  132. B[column + j][row + i] = A[row + i][column + j];
  133. }
  134. }
  135. }
  136. }
  137. }
  138. }
  139. // For 61 x 67 matrix
  140. else if(M == 61 && N == 67){
  141. // Block size of 14
  142. for(column = 0; column < N ; column += 14){
  143. for(row = 0; row < M; row += 14){
  144. for(i = column; i < column + 14; i++){
  145. for(j = row; j < row + 14; j++){
  146. // Limit operation to the size of matrix
  147. if(i < 67 && j < 61){
  148. B[j][i] = A[i][j];
  149. }
  150. }
  151. }
  152. }
  153. }
  154. }
  155. }
  156.  
  157. /*
  158. * You can define additional transpose functions below. We've defined
  159. * a simple one below to help you get started.
  160. */
  161.  
  162. /*
  163. * trans - A simple baseline transpose function, not optimized for the cache.
  164. */
  165. char trans_desc[] = "Simple row-wise scan transpose";
  166. void trans(int M, int N, int A[N][M], int B[M][N])
  167. {
  168. int i, j, tmp;
  169.  
  170. for (i = 0; i < N; i++) {
  171. for (j = 0; j < M; j++) {
  172. tmp = A[i][j];
  173. B[j][i] = tmp;
  174. }
  175. }
  176.  
  177. }
  178.  
  179. /*
  180. * registerFunctions - This function registers your transpose
  181. * functions with the driver. At runtime, the driver will
  182. * evaluate each of the registered functions and summarize their
  183. * performance. This is a handy way to experiment with different
  184. * transpose strategies.
  185. */
  186. void registerFunctions()
  187. {
  188. /* Register your solution function */
  189. registerTransFunction(transpose_submit, transpose_submit_desc);
  190.  
  191. /* Register any additional transpose functions */
  192. registerTransFunction(trans, trans_desc);
  193.  
  194. }
  195.  
  196. /*
  197. * is_transpose - This helper function checks if B is the transpose of
  198. * A. You can check the correctness of your transpose by calling
  199. * it before returning from the transpose function.
  200. */
  201. int is_transpose(int M, int N, int A[N][M], int B[M][N])
  202. {
  203. int i, j;
  204.  
  205. for (i = 0; i < N; i++) {
  206. for (j = 0; j < M; ++j) {
  207. if (A[i][j] != B[j][i]) {
  208. return 0;
  209. }
  210. }
  211. }
  212. return 1;
  213. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!