| 1 |
// Start of copy.h |
| 2 |
|
| 3 |
// Cache-oblivious map-transpose function. |
| 4 |
#define GEN_MAP_TRANSPOSE(NAME, ELEM_TYPE) \ |
| 5 |
static void map_transpose_##NAME \ |
| 6 |
(ELEM_TYPE* dst, ELEM_TYPE* src, \ |
| 7 |
int64_t k, int64_t m, int64_t n, \ |
| 8 |
int64_t cb, int64_t ce, int64_t rb, int64_t re) \ |
| 9 |
{ \ |
| 10 |
int32_t r = re - rb; \ |
| 11 |
int32_t c = ce - cb; \ |
| 12 |
if (k == 1) { \ |
| 13 |
if (r <= 64 && c <= 64) { \ |
| 14 |
for (int64_t j = 0; j < c; j++) { \ |
| 15 |
for (int64_t i = 0; i < r; i++) { \ |
| 16 |
dst[(j + cb) * n + (i + rb)] = src[(i + rb) * m + (j + cb)]; \ |
| 17 |
} \ |
| 18 |
} \ |
| 19 |
} else if (c <= r) { \ |
| 20 |
map_transpose_##NAME(dst, src, k, m, n, cb, ce, rb, rb + r/2); \ |
| 21 |
map_transpose_##NAME(dst, src, k, m, n, cb, ce, rb + r/2, re); \ |
| 22 |
} else { \ |
| 23 |
map_transpose_##NAME(dst, src, k, m, n, cb, cb + c/2, rb, re); \ |
| 24 |
map_transpose_##NAME(dst, src, k, m, n, cb + c/2, ce, rb, re); \ |
| 25 |
} \ |
| 26 |
} else { \ |
| 27 |
for (int64_t i = 0; i < k; i++) { \ |
| 28 |
map_transpose_##NAME(dst + i * m * n, src + i * m * n, 1, m, n, cb, ce, rb, re); \ |
| 29 |
}\ |
| 30 |
} \ |
| 31 |
} |
| 32 |
|
| 33 |
// Straightforward LMAD copy function. |
| 34 |
#define GEN_LMAD_COPY_ELEMENTS(NAME, ELEM_TYPE) \ |
| 35 |
static void lmad_copy_elements_##NAME(int r, \ |
| 36 |
ELEM_TYPE* dst, int64_t dst_strides[r], \ |
| 37 |
ELEM_TYPE *src, int64_t src_strides[r], \ |
| 38 |
int64_t shape[r]) { \ |
| 39 |
if (r == 1) { \ |
| 40 |
for (int i = 0; i < shape[0]; i++) { \ |
| 41 |
dst[i*dst_strides[0]] = src[i*src_strides[0]]; \ |
| 42 |
} \ |
| 43 |
} else if (r > 1) { \ |
| 44 |
for (int i = 0; i < shape[0]; i++) { \ |
| 45 |
lmad_copy_elements_##NAME(r-1, \ |
| 46 |
dst+i*dst_strides[0], dst_strides+1, \ |
| 47 |
src+i*src_strides[0], src_strides+1, \ |
| 48 |
shape+1); \ |
| 49 |
} \ |
| 50 |
} \ |
| 51 |
} \ |
| 52 |
|
| 53 |
// Check whether this LMAD can be seen as a transposed 2D array. This |
| 54 |
// is done by checking every possible splitting point. |
| 55 |
static bool lmad_is_tr(int64_t *n_out, int64_t *m_out, |
| 56 |
int r, |
| 57 |
const int64_t strides[r], |
| 58 |
const int64_t shape[r]) { |
| 59 |
for (int i = 1; i < r; i++) { |
| 60 |
int n = 1, m = 1; |
| 61 |
bool ok = true; |
| 62 |
int64_t expected = 1; |
| 63 |
// Check strides before 'i'. |
| 64 |
for (int j = i-1; j >= 0; j--) { |
| 65 |
ok = ok && strides[j] == expected; |
| 66 |
expected *= shape[j]; |
| 67 |
n *= shape[j]; |
| 68 |
} |
| 69 |
// Check strides after 'i'. |
| 70 |
for (int j = r-1; j >= i; j--) { |
| 71 |
ok = ok && strides[j] == expected; |
| 72 |
expected *= shape[j]; |
| 73 |
m *= shape[j]; |
| 74 |
} |
| 75 |
if (ok) { |
| 76 |
*n_out = n; |
| 77 |
*m_out = m; |
| 78 |
return true; |
| 79 |
} |
| 80 |
} |
| 81 |
return false; |
| 82 |
} |
| 83 |
|
| 84 |
// This function determines whether the a 'dst' LMAD is row-major and |
| 85 |
// 'src' LMAD is column-major. Both LMADs are for arrays of the same |
| 86 |
// shape. Both LMADs are allowed to have additional dimensions "on |
| 87 |
// top". Essentially, this function determines whether a copy from |
| 88 |
// 'src' to 'dst' is a "map(transpose)" that we know how to implement |
| 89 |
// efficiently. The LMADs can have arbitrary rank, and the main |
| 90 |
// challenge here is checking whether the src LMAD actually |
| 91 |
// corresponds to a 2D column-major layout by morally collapsing |
| 92 |
// dimensions. There is a lot of looping here, but the actual trip |
| 93 |
// count is going to be very low in practice. |
| 94 |
// |
| 95 |
// Returns true if this is indeed a map(transpose), and writes the |
| 96 |
// number of arrays, and moral array size to appropriate output |
| 97 |
// parameters. |
| 98 |
static bool lmad_map_tr(int64_t *num_arrays_out, int64_t *n_out, int64_t *m_out, |
| 99 |
int r, |
| 100 |
const int64_t dst_strides[r], |
| 101 |
const int64_t src_strides[r], |
| 102 |
const int64_t shape[r]) { |
| 103 |
int64_t rowmajor_strides[r]; |
| 104 |
rowmajor_strides[r-1] = 1; |
| 105 |
|
| 106 |
for (int i = r-2; i >= 0; i--) { |
| 107 |
rowmajor_strides[i] = rowmajor_strides[i+1] * shape[i+1]; |
| 108 |
} |
| 109 |
|
| 110 |
// map_r will be the number of mapped dimensions on top. |
| 111 |
int map_r = 0; |
| 112 |
int64_t num_arrays = 1; |
| 113 |
for (int i = 0; i < r; i++) { |
| 114 |
if (dst_strides[i] != rowmajor_strides[i] || |
| 115 |
src_strides[i] != rowmajor_strides[i]) { |
| 116 |
break; |
| 117 |
} else { |
| 118 |
num_arrays *= shape[i]; |
| 119 |
map_r++; |
| 120 |
} |
| 121 |
} |
| 122 |
|
| 123 |
*num_arrays_out = num_arrays; |
| 124 |
|
| 125 |
if (r==map_r) { |
| 126 |
return false; |
| 127 |
} |
| 128 |
|
| 129 |
if (memcmp(&rowmajor_strides[map_r], |
| 130 |
&dst_strides[map_r], |
| 131 |
sizeof(int64_t)*(r-map_r)) == 0) { |
| 132 |
return lmad_is_tr(n_out, m_out, r-map_r, src_strides+map_r, shape+map_r); |
| 133 |
} else if (memcmp(&rowmajor_strides[map_r], |
| 134 |
&src_strides[map_r], |
| 135 |
sizeof(int64_t)*(r-map_r)) == 0) { |
| 136 |
return lmad_is_tr(m_out, n_out, r-map_r, dst_strides+map_r, shape+map_r); |
| 137 |
} |
| 138 |
return false; |
| 139 |
} |
| 140 |
|
| 141 |
// Check if the strides correspond to row-major strides of *any* |
| 142 |
// permutation of the shape. This is done by recursive search with |
| 143 |
// backtracking. This is worst-case exponential, but hopefully the |
| 144 |
// arrays we encounter do not have that many dimensions. |
| 145 |
static bool lmad_contiguous_search(int checked, int64_t expected, |
| 146 |
int r, |
| 147 |
int64_t strides[r], int64_t shape[r], bool used[r]) { |
| 148 |
for (int i = 0; i < r; i++) { |
| 149 |
for (int j = 0; j < r; j++) { |
| 150 |
if (!used[j] && strides[j] == expected && strides[j] >= 0) { |
| 151 |
used[j] = true; |
| 152 |
if (checked+1 == r || |
| 153 |
lmad_contiguous_search(checked+1, expected * shape[j], r, strides, shape, used)) { |
| 154 |
return true; |
| 155 |
} |
| 156 |
used[j] = false; |
| 157 |
} |
| 158 |
} |
| 159 |
} |
| 160 |
return false; |
| 161 |
} |
| 162 |
|
| 163 |
// Does this LMAD correspond to an array with positive strides and no |
| 164 |
// holes? |
| 165 |
static bool lmad_contiguous(int r, int64_t strides[r], int64_t shape[r]) { |
| 166 |
bool used[r]; |
| 167 |
for (int i = 0; i < r; i++) { |
| 168 |
used[i] = false; |
| 169 |
} |
| 170 |
return lmad_contiguous_search(0, 1, r, strides, shape, used); |
| 171 |
} |
| 172 |
|
| 173 |
// Does this copy correspond to something that could be done with a |
| 174 |
// memcpy()-like operation? I.e. do the LMADs actually represent the |
| 175 |
// same in-memory layout and are they contiguous? |
| 176 |
static bool lmad_memcpyable(int r, |
| 177 |
int64_t dst_strides[r], int64_t src_strides[r], int64_t shape[r]) { |
| 178 |
if (!lmad_contiguous(r, dst_strides, shape)) { |
| 179 |
return false; |
| 180 |
} |
| 181 |
for (int i = 0; i < r; i++) { |
| 182 |
if (dst_strides[i] != src_strides[i] && shape[i] != 1) { |
| 183 |
return false; |
| 184 |
} |
| 185 |
} |
| 186 |
return true; |
| 187 |
} |
| 188 |
|
| 189 |
|
| 190 |
static void log_copy(struct futhark_context* ctx, |
| 191 |
const char *kind, const char *provenance, |
| 192 |
int r, |
| 193 |
int64_t dst_offset, int64_t dst_strides[r], |
| 194 |
int64_t src_offset, int64_t src_strides[r], |
| 195 |
int64_t shape[r]) { |
| 196 |
if (ctx->logging) { |
| 197 |
fprintf(ctx->log, "\n# Copy %s\n", kind); |
| 198 |
if (provenance) { fprintf(ctx->log, "At: %s\n", provenance); } |
| 199 |
fprintf(ctx->log, "Shape: "); |
| 200 |
for (int i = 0; i < r; i++) { fprintf(ctx->log, "[%ld]", (long int)shape[i]); } |
| 201 |
fprintf(ctx->log, "\n"); |
| 202 |
fprintf(ctx->log, "Dst offset: %ld\n", (long int)dst_offset); |
| 203 |
fprintf(ctx->log, "Dst strides:"); |
| 204 |
for (int i = 0; i < r; i++) { fprintf(ctx->log, " %ld", (long int)dst_strides[i]); } |
| 205 |
fprintf(ctx->log, "\n"); |
| 206 |
fprintf(ctx->log, "Src offset: %ld\n", (long int)src_offset); |
| 207 |
fprintf(ctx->log, "Src strides:"); |
| 208 |
for (int i = 0; i < r; i++) { fprintf(ctx->log, " %ld", (long int)src_strides[i]); } |
| 209 |
fprintf(ctx->log, "\n"); |
| 210 |
} |
| 211 |
} |
| 212 |
|
| 213 |
static void log_transpose(struct futhark_context* ctx, |
| 214 |
int64_t k, int64_t n, int64_t m) { |
| 215 |
if (ctx->logging) { |
| 216 |
fprintf(ctx->log, "## Transpose\n"); |
| 217 |
fprintf(ctx->log, "Arrays : %ld\n", (long int)k); |
| 218 |
fprintf(ctx->log, "X elements : %ld\n", (long int)m); |
| 219 |
fprintf(ctx->log, "Y elements : %ld\n", (long int)n); |
| 220 |
fprintf(ctx->log, "\n"); |
| 221 |
} |
| 222 |
} |
| 223 |
|
| 224 |
#define GEN_LMAD_COPY(NAME, ELEM_TYPE) \ |
| 225 |
static void lmad_copy_##NAME \ |
| 226 |
(struct futhark_context *ctx, int r, \ |
| 227 |
ELEM_TYPE* dst, int64_t dst_offset, int64_t dst_strides[r], \ |
| 228 |
ELEM_TYPE *src, int64_t src_offset, int64_t src_strides[r], \ |
| 229 |
int64_t shape[r]) { \ |
| 230 |
log_copy(ctx, "CPU to CPU", NULL, r, dst_offset, dst_strides, \ |
| 231 |
src_offset, src_strides, shape); \ |
| 232 |
int64_t size = 1; \ |
| 233 |
for (int i = 0; i < r; i++) { size *= shape[i]; } \ |
| 234 |
if (size == 0) { return; } \ |
| 235 |
int64_t k, n, m; \ |
| 236 |
if (lmad_map_tr(&k, &n, &m, \ |
| 237 |
r, dst_strides, src_strides, shape)) { \ |
| 238 |
log_transpose(ctx, k, n, m); \ |
| 239 |
map_transpose_##NAME \ |
| 240 |
(dst+dst_offset, src+src_offset, k, n, m, 0, n, 0, m); \ |
| 241 |
} else if (lmad_memcpyable(r, dst_strides, src_strides, shape)) { \ |
| 242 |
if (ctx->logging) {fprintf(ctx->log, "## Flat copy\n\n");} \ |
| 243 |
memcpy(dst+dst_offset, src+src_offset, size*sizeof(*dst)); \ |
| 244 |
} else { \ |
| 245 |
if (ctx->logging) {fprintf(ctx->log, "## General copy\n\n");} \ |
| 246 |
lmad_copy_elements_##NAME \ |
| 247 |
(r, \ |
| 248 |
dst+dst_offset, dst_strides, \ |
| 249 |
src+src_offset, src_strides, shape); \ |
| 250 |
} \ |
| 251 |
} |
| 252 |
|
| 253 |
GEN_MAP_TRANSPOSE(1b, uint8_t) |
| 254 |
GEN_MAP_TRANSPOSE(2b, uint16_t) |
| 255 |
GEN_MAP_TRANSPOSE(4b, uint32_t) |
| 256 |
GEN_MAP_TRANSPOSE(8b, uint64_t) |
| 257 |
|
| 258 |
GEN_LMAD_COPY_ELEMENTS(1b, uint8_t) |
| 259 |
GEN_LMAD_COPY_ELEMENTS(2b, uint16_t) |
| 260 |
GEN_LMAD_COPY_ELEMENTS(4b, uint32_t) |
| 261 |
GEN_LMAD_COPY_ELEMENTS(8b, uint64_t) |
| 262 |
|
| 263 |
GEN_LMAD_COPY(1b, uint8_t) |
| 264 |
GEN_LMAD_COPY(2b, uint16_t) |
| 265 |
GEN_LMAD_COPY(4b, uint32_t) |
| 266 |
GEN_LMAD_COPY(8b, uint64_t) |
| 267 |
|
| 268 |
// End of copy.h |