1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
|
// swarm/integ_attn: merged attention kernel = live attn.cu +
// attn_softmax padded smem (row stride 84 halves), fwd software pipelining (double-buffered K,
// next QK^T overlapping softmax), unrolled full-tile dQ atomic loop;
// bwd ILP kept as a knob, default off (see BWD_ILP) (polynomial exp NOT included)
// attn_long 1-D grid, heads interleaved in the global longest-first launch order
// attn_bwd mode 6: next query tile's Q, dO, lse, D prefetched into registers (BWD_PF)
// o, lse, dk, dv bitwise identical to the live kernel; dq differs only by fp32 atomic order.
// Varlen causal FlashAttention for sm_70 (V100), head_dim 64, fp16 in/out.
//
// Why this exists: PyTorch's only SDPA backend that trains on sm_70 is the
// CUTLASS memory-efficient kernel, whose backward measured ~4x its own forward
// on Boris-2's shapes (FlashAttention-2 does ~2.5x). Triton cannot help here:
// on sm_70 tl.dot lowers to plain FMA (no tensor cores), so this is CUDA with
// raw mma.sync.m8n8k4 -- the same HMMA.884 instruction CUTLASS's sm70 path uses.
//
// Precision is the memory-efficient kernel's precision class, deliberately:
// * every GEMM takes fp16 operands and accumulates in fp32
// * softmax statistics (max, sum, logsumexp) are fp32
// * P and dS are rounded to fp16 only as GEMM operands, as in any fp16 kernel
// * dQ is accumulated in an fp32 buffer across key tiles and rounded once
//
// Fragment layouts of m8n8k4 (verified empirically on this card, see
// volta_kernels/README.md). j = lane%4, hi = lane>=16, quad-pair qp = (lane>>2)&3:
// A.row : row = j + 4hi, k = 0..3 A.col : k = j, row = 4hi + 0..3
// B.col : n = j + 4hi, k = 0..3 B.row : k = j, n = 4hi + 0..3
// D f32 : row = (lane&1) + (i&2) + 4hi, col = (i&4) + (lane&2) + (i&1)
// Each quad-pair computes its own 8x8 tile; the four are arranged 2x2 into a
// 16x16 warp tile: m offset 8*(qp&1), n offset 8*(qp>>1).
#include <torch/extension.h>
#include <ATen/cuda/CUDAContext.h>
#include <cuda_fp16.h>
#include <stdint.h>
namespace {
constexpr int HD = 64; // head dim
constexpr int TL = 64; // tile edge (queries or keys)
constexpr int NT = 128; // 4 warps, 16 tile rows each
// 64x64 fp16 tiles live unpadded in shared memory with the 8-byte segments of
// each row XOR-swizzled. The mapping makes every fragment access pattern used
// below (A.row, B.col: 8 rows x one segment; B.row, A.col: 4 rows x two
// segments) hit distinct banks within each half-warp.
__device__ __forceinline__ int swz(int r) { return ((r & 3) << 2) | ((r >> 2) & 3); }
__device__ __forceinline__ int so(int r, int c) {
return r * 64 + ((((c >> 2) ^ swz(r))) << 2) + (c & 3);
}
// Compile-time knobs (defaults = the adopted combination).
// BWD_ILP (attn_softmax) and BWD_PF (attn_bwd mode 6) combine without spills (255 regs, 2 CTAs/SM),
// but with the prefetch on, ILP adds nothing measurable (bwd vs live: PF only 0.944/0.945 at
// 16x2048, 0.900 at 4x8192; PF+ILP 0.946/0.947 and 0.897). PF alone wins at stage 1 and leaves
// 17 registers of headroom (238), so ILP is off by default; set -DBWD_ILP=1 to re-test.
#ifndef BWD_ILP
#define BWD_ILP 0 // bwd: S^T MMAs first, then exp(S^T) and the dP^T MMAs in one basic block
#endif
#ifndef BWD_PF
#define BWD_PF 1 // bwd: next query tile's Q/dO/lse/D prefetched into registers
#endif
// Padded layout: row stride 84 halves = 42 words. Every fragment pattern used
// here (8 rows {0..3,8..11} x 8B; 4 rows x 2 segments 16B apart; P's 32-bit
// stores; commit's 2 rows x 8 segments) hits distinct banks per half-warp, and
// all per-ks / per-nb offsets become compile-time immediates.
constexpr int LDP = 84;
template <bool P> __device__ __forceinline__ int lo(int r, int c) {
if constexpr (P) return r * LDP + c; else return so(r, c);
}
__device__ __forceinline__ uint2 lds2(const half* t, int off) {
return *reinterpret_cast<const uint2*>(t + off);
}
#define DEF_MMA(LA, LB) \
__device__ __forceinline__ void mma_##LA##_##LB(float* d, uint2 a, uint2 b) { \
asm("mma.sync.aligned.m8n8k4." #LA "." #LB ".f32.f16.f16.f32 " \
"{%0,%1,%2,%3,%4,%5,%6,%7}, {%8,%9}, {%10,%11}, {%0,%1,%2,%3,%4,%5,%6,%7};" \
: "+f"(d[0]), "+f"(d[1]), "+f"(d[2]), "+f"(d[3]), \
"+f"(d[4]), "+f"(d[5]), "+f"(d[6]), "+f"(d[7]) \
: "r"(a.x), "r"(a.y), "r"(b.x), "r"(b.y)); \
}
DEF_MMA(row, col)
DEF_MMA(row, row)
DEF_MMA(col, row)
__device__ __forceinline__ float ex2(float x) {
float y;
asm("ex2.approx.ftz.f32 %0, %1;" : "=f"(y) : "f"(x));
return y;
}
__device__ __forceinline__ unsigned pack_h2(float a, float b) {
__half2 h = __floats2half2_rn(a, b);
return *reinterpret_cast<unsigned*>(&h);
}
// Copy rows [row0, row0+64) of one head (64 contiguous halves at token stride
// `ts`) into a swizzled tile. Rows at or past `nrows` are zero-filled.
template <bool PD = false>
__device__ __forceinline__ void load_tile(half* t, const half* g, int ts, int row0,
int nrows, int tid) {
#pragma unroll
for (int it = 0; it < (TL * 8) / NT; ++it) {
int idx = tid + it * NT;
int r = idx >> 3, c = (idx & 7) * 8;
uint4 v = make_uint4(0, 0, 0, 0);
if (row0 + r < nrows)
v = *reinterpret_cast<const uint4*>(g + (long)(row0 + r) * ts + c);
*reinterpret_cast<uint2*>(t + lo<PD>(r, c)) = make_uint2(v.x, v.y);
*reinterpret_cast<uint2*>(t + lo<PD>(r, c + 4)) = make_uint2(v.z, v.w);
}
}
// Register-staged copy of one 64x64 tile: global loads issued early, the
// swizzled shared-memory stores later, so the load latency overlaps compute.
struct TileRegs { uint4 v[(TL * 8) / NT]; };
__device__ __forceinline__ void fetch_tile(TileRegs& R, const half* g, int ts, int row0, int nrows, int tid) {
#pragma unroll
for (int it = 0; it < (TL * 8) / NT; ++it) {
int idx = tid + it * NT, r = idx >> 3, c = (idx & 7) * 8;
R.v[it] = (row0 + r < nrows) ? *reinterpret_cast<const uint4*>(g + (long)(row0 + r) * ts + c)
: make_uint4(0, 0, 0, 0);
}
}
template <bool PD = false>
__device__ __forceinline__ void commit_tile(half* t, const TileRegs& R, int tid) {
#pragma unroll
for (int it = 0; it < (TL * 8) / NT; ++it) {
int idx = tid + it * NT, r = idx >> 3, c = (idx & 7) * 8;
*reinterpret_cast<uint2*>(t + lo<PD>(r, c)) = make_uint2(R.v[it].x, R.v[it].y);
*reinterpret_cast<uint2*>(t + lo<PD>(r, c + 4)) = make_uint2(R.v[it].z, R.v[it].w);
}
}
// Map a flat block index onto (document, tile). tcum[d] is the number of tiles
// in documents before d; tcum[ndocs] the total.
__device__ __forceinline__ bool find_tile(const int* tcum, const int* perm, int ndocs, int b,
int& doc, int& local, int& ntiles) {
if (b >= tcum[ndocs]) return false;
int lo = 0, hi = ndocs - 1;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (tcum[mid] <= b) lo = mid; else hi = mid - 1;
}
doc = perm[lo]; // tcum is over documents sorted longest-first
local = b - tcum[lo];
ntiles = tcum[lo + 1] - tcum[lo];
return true;
}
// --------------------------------------------------------------------------
// Forward. One CTA = one 64-query tile of one document, one head.
// --------------------------------------------------------------------------
__global__ void __launch_bounds__(NT) fwd_kernel(
const half* __restrict__ Q, const half* __restrict__ K, const half* __restrict__ V,
half* __restrict__ O, float* __restrict__ LSE, const int* __restrict__ cu,
const int* __restrict__ tcum, const int* __restrict__ perm, int ndocs, int N, int H,
int sq, int sk, int sv, int s_o, float scale_log2) {
// Padded tiles (row stride LDP); K double-buffered for the software pipeline.
__shared__ __align__(16) half Ks2[2][TL * LDP];
__shared__ __align__(16) half Vs[TL * LDP];
__shared__ __align__(16) half Ps[4][16 * LDP];
// 1-D grid, heads interleaved: the longest-first order holds across heads.
const int h = blockIdx.x % H;
int doc, local, ntiles;
if (!find_tile(tcum, perm, ndocs, blockIdx.x / H, doc, local, ntiles)) return;
const int t = ntiles - 1 - local; // longest-running tiles launch first
const int s0 = cu[doc], L = cu[doc + 1] - s0;
const int tid = threadIdx.x, w = tid >> 5, lane = tid & 31;
const int j = lane & 3, hi = lane >> 4, qp = (lane >> 2) & 3;
const int mo = 8 * (qp & 1), no = 8 * (qp >> 1);
uint2 qf[16];
{
int qrow = t * TL + 16 * w + mo + j + 4 * hi;
const half* g = Q + (long)(s0 + qrow) * sq + h * HD;
#pragma unroll
for (int ks = 0; ks < 16; ++ks)
qf[ks] = qrow < L ? *reinterpret_cast<const uint2*>(g + 4 * ks) : make_uint2(0, 0);
}
const int qr0 = t * TL + 16 * w + mo + (lane & 1) + 4 * hi; // i&2 == 0
float m[2] = {-INFINITY, -INFINITY}, l[2] = {0.f, 0.f};
float o[4][8];
#pragma unroll
for (int a = 0; a < 4; ++a)
#pragma unroll
for (int i = 0; i < 8; ++i) o[a][i] = 0.f;
half* P = Ps[w];
const half* Kg = K + (long)s0 * sk + h * HD;
const half* Vg = V + (long)s0 * sv + h * HD;
float s[4][8];
TileRegs kr, vr;
// Prologue: K_0 committed, S_0 computed; the loop body computes S_{kt+1}
// while doing softmax(S_kt). Ks2[kt&1] holds K_kt.
fetch_tile(kr, Kg, sk, 0, L, tid);
fetch_tile(vr, Vg, sv, 0, L, tid);
commit_tile<true>(Ks2[0], kr, tid);
if (t > 0) fetch_tile(kr, Kg, sk, TL, L, tid);
__syncthreads();
#pragma unroll
for (int a = 0; a < 4; ++a)
#pragma unroll
for (int i = 0; i < 8; ++i) s[a][i] = 0.f;
#pragma unroll
for (int ks = 0; ks < 16; ++ks)
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
mma_row_col(s[nb], qf[ks], lds2(Ks2[0], lo<true>(nb * 16 + no + j + 4 * hi, 4 * ks)));
for (int kt = 0; kt <= t; ++kt) {
__syncthreads(); // everyone done with Vs (PV of kt-1) and Ks2[(kt+1)&1] (S_kt's MMAs)
commit_tile<true>(Vs, vr, tid);
if (kt < t) commit_tile<true>(Ks2[(kt + 1) & 1], kr, tid);
if (kt < t) {
fetch_tile(vr, Vg, sv, (kt + 1) * TL, L, tid);
if (kt + 1 < t) fetch_tile(kr, Kg, sk, (kt + 2) * TL, L, tid);
}
__syncthreads();
const bool diag = (kt == t);
const bool masked = diag || kt * TL + TL > L;
float mx[2] = {m[0], m[1]};
// Mask by select only; the max, the next tile's MMAs and the exp share one
// basic block so ptxas can interleave HMMA with the softmax FP work.
if (masked) {
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 0; i < 8; ++i) {
int key = kt * TL + nb * 16 + no + (i & 4) + (lane & 2) + (i & 1);
int qr = qr0 + (i & 2);
bool ok = key < L && (!diag || key <= qr);
s[nb][i] = ok ? s[nb][i] : -INFINITY;
}
}
float sn[4][8];
{
const half* Kn = Ks2[(kt + 1) & 1]; // stale on the last tile; result unused
#pragma unroll
for (int a = 0; a < 4; ++a)
#pragma unroll
for (int i = 0; i < 8; ++i) sn[a][i] = 0.f;
#pragma unroll
for (int ks = 0; ks < 16; ++ks)
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
mma_row_col(sn[nb], qf[ks], lds2(Kn, lo<true>(nb * 16 + no + j + 4 * hi, 4 * ks)));
}
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 0; i < 8; ++i) mx[(i >> 1) & 1] = fmaxf(mx[(i >> 1) & 1], s[nb][i]);
#pragma unroll
for (int r = 0; r < 2; ++r) {
mx[r] = fmaxf(mx[r], __shfl_xor_sync(0xffffffff, mx[r], 2));
mx[r] = fmaxf(mx[r], __shfl_xor_sync(0xffffffff, mx[r], 8));
}
float alpha[2];
#pragma unroll
for (int r = 0; r < 2; ++r) {
alpha[r] = ex2((m[r] - mx[r]) * scale_log2); // exp2(-inf) = 0 on the first tile
m[r] = mx[r];
l[r] *= alpha[r];
}
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 0; i < 8; ++i) {
int r = (i >> 1) & 1;
float p = ex2(fmaf(s[nb][i], scale_log2, -m[r] * scale_log2));
s[nb][i] = p;
l[r] += p;
o[nb][i] *= alpha[r];
}
__syncwarp();
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 0; i < 8; i += 2) {
int row = mo + (lane & 1) + (i & 2) + 4 * hi;
int col = nb * 16 + no + (i & 4) + (lane & 2);
*reinterpret_cast<unsigned*>(P + lo<true>(row, col)) = pack_h2(s[nb][i], s[nb][i + 1]);
}
__syncwarp();
#pragma unroll
for (int ks = 0; ks < 16; ++ks) {
uint2 a = lds2(P, lo<true>(mo + j + 4 * hi, 4 * ks));
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
mma_row_row(o[nb], a, lds2(Vs, lo<true>(4 * ks + j, nb * 16 + no + 4 * hi)));
}
#pragma unroll
for (int a = 0; a < 4; ++a)
#pragma unroll
for (int i = 0; i < 8; ++i) s[a][i] = sn[a][i];
}
#pragma unroll
for (int r = 0; r < 2; ++r) {
l[r] += __shfl_xor_sync(0xffffffff, l[r], 2);
l[r] += __shfl_xor_sync(0xffffffff, l[r], 8);
}
#pragma unroll
for (int r = 0; r < 2; ++r) {
int qr = qr0 + 2 * r;
if (qr >= L) continue;
float inv = 1.f / l[r];
half* og = O + (long)(s0 + qr) * s_o + h * HD;
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 2 * r; i < 8; i += 4) {
int col = nb * 16 + no + (i & 4) + (lane & 2);
*reinterpret_cast<unsigned*>(og + col) = pack_h2(o[nb][i] * inv, o[nb][i + 1] * inv);
}
if ((lane & 2) == 0 && no == 0) LSE[(long)h * N + s0 + qr] = m[r] * scale_log2 + __log2f(l[r]);
}
}
// --------------------------------------------------------------------------
// Backward. One CTA = one 64-key tile of one document, one head; it walks the
// query tiles at and after it. dK/dV stay in registers; dQ is accumulated in
// an fp32 buffer with atomics (same as FlashAttention-2).
// --------------------------------------------------------------------------
__global__ void __launch_bounds__(NT) bwd_kernel(
const half* __restrict__ Q, const half* __restrict__ K, const half* __restrict__ V,
const half* __restrict__ dO, const float* __restrict__ LSE,
const float* __restrict__ Dv, float* __restrict__ dQacc, half* __restrict__ dK,
half* __restrict__ dV, const int* __restrict__ cu, const int* __restrict__ tcum,
const int* __restrict__ perm,
int ndocs, int N, int H, int sq, int sk, int sv, int sdo, int sdk, int sdv,
float scale_log2, float scale) {
__shared__ __align__(16) half Ks[TL * HD];
__shared__ __align__(16) half Vs[TL * HD];
// Q and dO for the current query tile (padded, row stride LDP). Once dK/dV
// are done with them they are dead for the iteration, and the same bytes
// stage dQ in fp32.
__shared__ __align__(16) half QdOs[2 * TL * LDP];
half* Qs = QdOs;
half* dOs = QdOs + TL * LDP;
float* dQs = reinterpret_cast<float*>(QdOs);
__shared__ __align__(16) half St[TL * TL]; // P^T, then dS^T (key rows, query cols)
__shared__ float lse_s[TL], d_s[TL];
// 1-D grid, heads interleaved: the longest-first order holds across heads.
const int h = blockIdx.x % H;
int doc, kt, ntiles;
if (!find_tile(tcum, perm, ndocs, blockIdx.x / H, doc, kt, ntiles)) return;
const int s0 = cu[doc], L = cu[doc + 1] - s0;
const int tid = threadIdx.x, w = tid >> 5, lane = tid & 31;
const int j = lane & 3, hi = lane >> 4, qp = (lane >> 2) & 3;
const int mo = 8 * (qp & 1), no = 8 * (qp >> 1);
load_tile(Ks, K + (long)s0 * sk + h * HD, sk, kt * TL, L, tid);
load_tile(Vs, V + (long)s0 * sv + h * HD, sv, kt * TL, L, tid);
float dk[4][8], dv[4][8];
#pragma unroll
for (int a = 0; a < 4; ++a)
#pragma unroll
for (int i = 0; i < 8; ++i) dk[a][i] = dv[a][i] = 0.f;
const int kr0 = kt * TL + 16 * w + mo + (lane & 1) + 4 * hi; // this lane's key rows (i&2==0)
half* Sw = St + 16 * w * 64; // this warp's 16 key rows
const half* Qg = Q + (long)s0 * sq + h * HD;
const half* dOg = dO + (long)s0 * sdo + h * HD;
#if BWD_PF
// The next query tile's Q/dO (and lse/D) are fetched into registers while
// the current tile computes, like the forward's K/V prefetch.
TileRegs qreg, dreg;
float lse_n = 0.f, d_n = 0.f;
fetch_tile(qreg, Qg, sq, kt * TL, L, tid);
fetch_tile(dreg, dOg, sdo, kt * TL, L, tid);
if (tid < TL) {
int qr = kt * TL + tid;
if (qr < L) { lse_n = LSE[(long)h * N + s0 + qr]; d_n = Dv[(long)h * N + s0 + qr]; }
}
#endif
for (int qt = kt; qt < ntiles; ++qt) {
__syncthreads();
#if BWD_PF
commit_tile<true>(Qs, qreg, tid);
commit_tile<true>(dOs, dreg, tid);
if (tid < TL) { lse_s[tid] = lse_n; d_s[tid] = d_n; }
if (qt + 1 < ntiles) {
fetch_tile(qreg, Qg, sq, (qt + 1) * TL, L, tid);
fetch_tile(dreg, dOg, sdo, (qt + 1) * TL, L, tid);
if (tid < TL) {
int qr = (qt + 1) * TL + tid;
bool ok = qr < L;
lse_n = ok ? LSE[(long)h * N + s0 + qr] : 0.f;
d_n = ok ? Dv[(long)h * N + s0 + qr] : 0.f;
}
}
#else
load_tile<true>(Qs, Qg, sq, qt * TL, L, tid);
load_tile<true>(dOs, dOg, sdo, qt * TL, L, tid);
if (tid < TL) {
int qr = qt * TL + tid;
bool ok = qr < L;
lse_s[tid] = ok ? LSE[(long)h * N + s0 + qr] : 0.f;
d_s[tid] = ok ? Dv[(long)h * N + s0 + qr] : 0.f;
}
#endif
__syncthreads();
// S^T = K_w Q^T and dP^T = V_w dO^T, both (16 keys x 64 queries).
float st[4][8], dp[4][8];
#pragma unroll
for (int a = 0; a < 4; ++a)
#pragma unroll
for (int i = 0; i < 8; ++i) st[a][i] = dp[a][i] = 0.f;
#if BWD_ILP
// S^T first; the dP^T MMAs are issued in the same basic block as exp(S^T)
// so ptxas interleaves HMMA with the MUFU/FFMA work.
#pragma unroll
for (int ks = 0; ks < 16; ++ks) {
uint2 ak = lds2(Ks, so(16 * w + mo + j + 4 * hi, 4 * ks));
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
mma_row_col(st[nb], ak, lds2(Qs, lo<true>(nb * 16 + no + j + 4 * hi, 4 * ks)));
}
#define DP_MMAS \
_Pragma("unroll") for (int ks = 0; ks < 16; ++ks) { \
uint2 av = lds2(Vs, so(16 * w + mo + j + 4 * hi, 4 * ks)); \
_Pragma("unroll") for (int nb = 0; nb < 4; ++nb) \
mma_row_col(dp[nb], av, lds2(dOs, lo<true>(nb * 16 + no + j + 4 * hi, 4 * ks))); \
}
#define DS_FROM_P \
_Pragma("unroll") for (int nb = 0; nb < 4; ++nb) \
_Pragma("unroll") for (int i = 0; i < 8; ++i) { \
int c = nb * 16 + no + (i & 4) + (lane & 2) + (i & 1); \
dp[nb][i] = st[nb][i] * (dp[nb][i] - d_s[c]); \
}
#else
#pragma unroll
for (int ks = 0; ks < 16; ++ks) {
uint2 ak = lds2(Ks, so(16 * w + mo + j + 4 * hi, 4 * ks));
uint2 av = lds2(Vs, so(16 * w + mo + j + 4 * hi, 4 * ks));
#pragma unroll
for (int nb = 0; nb < 4; ++nb) {
int n = nb * 16 + no + j + 4 * hi;
mma_row_col(st[nb], ak, lds2(Qs, lo<true>(n, 4 * ks)));
mma_row_col(dp[nb], av, lds2(dOs, lo<true>(n, 4 * ks)));
}
}
#endif
const bool diag = (qt == kt);
// Masks are needed only on the diagonal tile and a document's last query
// tile (a partial key tile is always diagonal); uniform across the CTA.
if (diag || qt * TL + TL > L) {
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 0; i < 8; ++i) {
int c = nb * 16 + no + (i & 4) + (lane & 2) + (i & 1);
int qr = qt * TL + c;
int kr = kr0 + (i & 2);
bool ok = qr < L && kr < L && (!diag || kr <= qr);
float p = ok ? ex2(fmaf(st[nb][i], scale_log2, -lse_s[c])) : 0.f;
st[nb][i] = p;
#if !BWD_ILP
dp[nb][i] = p * (dp[nb][i] - d_s[c]);
#endif
}
#if BWD_ILP
DP_MMAS
DS_FROM_P
#endif
} else {
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 0; i < 8; ++i) {
int c = nb * 16 + no + (i & 4) + (lane & 2) + (i & 1);
float p = ex2(fmaf(st[nb][i], scale_log2, -lse_s[c]));
st[nb][i] = p;
#if !BWD_ILP
dp[nb][i] = p * (dp[nb][i] - d_s[c]);
#endif
}
#if BWD_ILP
DP_MMAS
DS_FROM_P
#endif
}
#undef DP_MMAS
#undef DS_FROM_P
// dV_w += P^T_w dO
__syncwarp();
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 0; i < 8; i += 2) {
int row = mo + (lane & 1) + (i & 2) + 4 * hi;
int col = nb * 16 + no + (i & 4) + (lane & 2);
*reinterpret_cast<unsigned*>(Sw + so(row, col)) = pack_h2(st[nb][i], st[nb][i + 1]);
}
__syncwarp();
#pragma unroll
for (int ks = 0; ks < 16; ++ks) {
uint2 a = lds2(Sw, so(mo + j + 4 * hi, 4 * ks));
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
mma_row_row(dv[nb], a, lds2(dOs, lo<true>(4 * ks + j, nb * 16 + no + 4 * hi)));
}
// dK_w += dS^T_w Q
__syncwarp();
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 0; i < 8; i += 2) {
int row = mo + (lane & 1) + (i & 2) + 4 * hi;
int col = nb * 16 + no + (i & 4) + (lane & 2);
*reinterpret_cast<unsigned*>(Sw + so(row, col)) = pack_h2(dp[nb][i], dp[nb][i + 1]);
}
__syncwarp();
#pragma unroll
for (int ks = 0; ks < 16; ++ks) {
uint2 a = lds2(Sw, so(mo + j + 4 * hi, 4 * ks));
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
mma_row_row(dk[nb], a, lds2(Qs, lo<true>(4 * ks + j, nb * 16 + no + 4 * hi)));
}
// dQ (64 queries x 64 dims) += dS K; warp w takes queries 16w..16w+15.
// Its A operand is dS = (dS^T)^T, read straight from St as A.col.
__syncthreads();
float dq[4][8];
#pragma unroll
for (int a = 0; a < 4; ++a)
#pragma unroll
for (int i = 0; i < 8; ++i) dq[a][i] = 0.f;
#pragma unroll
for (int ks = 0; ks < 16; ++ks) {
uint2 a = lds2(St, so(4 * ks + j, 16 * w + mo + 4 * hi));
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
mma_col_row(dq[nb], a, lds2(Ks, so(4 * ks + j, nb * 16 + no + 4 * hi)));
}
// Stage the warp's 16x64 dQ slice in shared memory and issue the atomics
// row-contiguous: each warp-wide RED then covers 128 consecutive bytes
// (4 sectors) instead of scattering over 8 rows 2KB apart. Row stride is
// 64 floats; float2 slots are XOR-swizzled by row so both the fragment-
// layout writes and the row reads are bank-conflict free.
float* dQw = dQs + 16 * w * 64;
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 0; i < 8; i += 2) {
int row = mo + (lane & 1) + (i & 2) + 4 * hi;
int c2 = (nb * 16 + no + (i & 4) + (lane & 2)) >> 1;
int f = ((row & 1) << 1) | (row & 8);
*reinterpret_cast<float2*>(dQw + row * 64 + 2 * (c2 ^ f)) =
make_float2(dq[nb][i], dq[nb][i + 1]);
}
__syncwarp();
{
const int qbase = qt * TL + 16 * w;
const int nrow = min(16, L - qbase);
if (nrow == 16) {
// full 16-row slice: unrolled, smem offsets are 4 lane bases + immediates,
// global offsets one 64-bit pointer + row * (H*HD) increments.
float* gp = dQacc + ((long)(s0 + qbase) * H + h) * HD + lane;
const long rs = (long)H * HD;
const int x0 = lane >> 1, b0 = lane & 1;
#pragma unroll
for (int row = 0; row < 16; ++row) {
const int f = ((row & 1) << 1) | (row & 8);
const float* sr = dQw + row * 64 + 2 * (x0 ^ f) + b0;
atomicAdd(gp, sr[0]);
atomicAdd(gp + 32, sr[32]);
gp += rs;
}
} else
for (int it = 0; it < 2 * nrow; ++it) {
int row = it >> 1, col = (it & 1) * 32 + lane;
int f = ((row & 1) << 1) | (row & 8);
float v = dQw[row * 64 + 2 * ((col >> 1) ^ f) + (col & 1)];
atomicAdd(dQacc + ((long)(s0 + qbase + row) * H + h) * HD + col, v);
}
}
}
#pragma unroll
for (int r = 0; r < 2; ++r) {
int kr = kr0 + 2 * r;
if (kr >= L) continue;
half* gk = dK + (long)(s0 + kr) * sdk + h * HD;
half* gv = dV + (long)(s0 + kr) * sdv + h * HD;
#pragma unroll
for (int nb = 0; nb < 4; ++nb)
#pragma unroll
for (int i = 2 * r; i < 8; i += 4) {
int col = nb * 16 + no + (i & 4) + (lane & 2);
*reinterpret_cast<unsigned*>(gk + col) = pack_h2(dk[nb][i] * scale, dk[nb][i + 1] * scale);
*reinterpret_cast<unsigned*>(gv + col) = pack_h2(dv[nb][i], dv[nb][i + 1]);
}
}
}
// D[h][n] = sum_d dO[n,h,d] * O[n,h,d] in fp32. One warp per (n, h) row pair.
__global__ void bwd_pre_kernel(const half* __restrict__ dO, const half* __restrict__ O,
float* __restrict__ Dv, int N, int H, int sdo, int s_o) {
int gw = (blockIdx.x * blockDim.x + threadIdx.x) >> 5, lane = threadIdx.x & 31;
if (gw >= N * H) return;
int n = gw / H, h = gw % H;
__half2 a = reinterpret_cast<const __half2*>(dO + (long)n * sdo + h * HD)[lane];
__half2 b = reinterpret_cast<const __half2*>(O + (long)n * s_o + h * HD)[lane];
float2 fa = __half22float2(a), fb = __half22float2(b);
float acc = fa.x * fb.x + fa.y * fb.y;
#pragma unroll
for (int o = 16; o; o >>= 1) acc += __shfl_xor_sync(0xffffffff, acc, o);
if (lane == 0) Dv[(long)h * N + n] = acc;
}
// dq = fp16(dQacc * scale), four elements per thread.
__global__ void bwd_post_kernel(const float4* __restrict__ acc, uint2* __restrict__ dq,
long n4, float scale) {
long i = blockIdx.x * (long)blockDim.x + threadIdx.x;
if (i >= n4) return;
float4 v = acc[i];
dq[i] = make_uint2(pack_h2(v.x * scale, v.y * scale), pack_h2(v.z * scale, v.w * scale));
}
void check_qkv(const torch::Tensor& t, const char* name) {
TORCH_CHECK(t.is_cuda() && t.scalar_type() == at::kHalf, name, " must be cuda fp16");
TORCH_CHECK(t.dim() == 3 && t.size(2) == HD && t.stride(2) == 1 && t.stride(1) == HD,
name, " must be (N, H, 64) with contiguous heads");
TORCH_CHECK(t.stride(0) % 8 == 0, name, " token stride must be a multiple of 8");
}
void check_meta(const torch::Tensor& q, const torch::Tensor& k, const torch::Tensor& v,
const torch::Tensor& cu, const torch::Tensor& tcum) {
TORCH_CHECK(k.sizes() == q.sizes() && v.sizes() == q.sizes(),
"q, k, v must have the same (N, H, 64) shape");
TORCH_CHECK(k.device() == q.device() && v.device() == q.device() &&
cu.device() == q.device() && tcum.device() == q.device(),
"q, k, v, cu, tcum must be on one device");
TORCH_CHECK(cu.scalar_type() == at::kInt && tcum.scalar_type() == at::kInt &&
cu.dim() == 1 && tcum.dim() == 1 && cu.is_contiguous() && tcum.is_contiguous(),
"cu and tcum must be contiguous 1-D int32");
TORCH_CHECK(cu.numel() >= 2 && tcum.numel() == cu.numel(),
"cu and tcum must both have ndocs+1 entries");
}
} // namespace
// q, k, v: (N, H, 64) fp16. cu: (ndocs+1,) int32 offsets. tcum: (ndocs+1,) int32
// cumulative 64-tile counts. Returns (o, lse) with lse (H, N) fp32 in log2 units.
std::vector<torch::Tensor> fwd(torch::Tensor q, torch::Tensor k, torch::Tensor v,
torch::Tensor cu, torch::Tensor tcum, torch::Tensor perm, double scale) {
check_qkv(q, "q"); check_qkv(k, "k"); check_qkv(v, "v");
check_meta(q, k, v, cu, tcum);
const int N = q.size(0), H = q.size(1), ndocs = cu.numel() - 1;
auto o = torch::empty({N, H, HD}, q.options());
auto lse = torch::empty({H, N}, q.options().dtype(torch::kFloat));
// 1-D grid, heads interleaved (b = blockIdx.x / H); >= H * sum of ceil(len/64)
dim3 grid(((N + TL - 1) / TL + ndocs) * H);
fwd_kernel<<<grid, NT, 0, at::cuda::getCurrentCUDAStream()>>>(
(const half*)q.data_ptr(), (const half*)k.data_ptr(), (const half*)v.data_ptr(),
(half*)o.data_ptr(), lse.data_ptr<float>(), cu.data_ptr<int>(), tcum.data_ptr<int>(), perm.data_ptr<int>(),
ndocs, N, H, q.stride(0), k.stride(0), v.stride(0), o.stride(0),
(float)(scale * 1.4426950408889634));
C10_CUDA_KERNEL_LAUNCH_CHECK();
return {o, lse};
}
// Returns (dq, dk, dv), each (N, H, 64) fp16.
std::vector<torch::Tensor> bwd_raw(torch::Tensor dout, torch::Tensor q, torch::Tensor k,
torch::Tensor v, torch::Tensor o, torch::Tensor lse,
torch::Tensor cu, torch::Tensor tcum, torch::Tensor perm, double scale) {
check_qkv(q, "q"); check_qkv(k, "k"); check_qkv(v, "v");
check_meta(q, k, v, cu, tcum);
dout = dout.contiguous();
check_qkv(dout, "dout");
TORCH_CHECK(dout.sizes() == q.sizes() && o.sizes() == q.sizes() && o.stride(2) == 1 &&
o.stride(1) == HD && dout.device() == q.device() && o.device() == q.device(),
"dout and o must match q");
TORCH_CHECK(lse.scalar_type() == at::kFloat && lse.is_contiguous() && lse.dim() == 2 &&
lse.size(0) == q.size(1) && lse.size(1) == q.size(0), "lse must be (H, N) fp32");
const int N = q.size(0), H = q.size(1), ndocs = cu.numel() - 1;
// D_i = rowsum(dO * O), fp32, laid out (H, N) like lse.
auto stream = at::cuda::getCurrentCUDAStream();
auto Dv = torch::empty({H, N}, q.options().dtype(torch::kFloat));
bwd_pre_kernel<<<(N * H * 32 + 255) / 256, 256, 0, stream>>>(
(const half*)dout.data_ptr(), (const half*)o.data_ptr(), Dv.data_ptr<float>(), N, H,
dout.stride(0), o.stride(0));
auto dqacc = torch::zeros({N, H, HD}, q.options().dtype(torch::kFloat));
auto dk = torch::empty({N, H, HD}, q.options());
auto dv = torch::empty({N, H, HD}, q.options());
// 1-D grid, heads interleaved (b = blockIdx.x / H); >= H * sum of ceil(len/64)
dim3 grid(((N + TL - 1) / TL + ndocs) * H);
bwd_kernel<<<grid, NT, 0, stream>>>(
(const half*)q.data_ptr(), (const half*)k.data_ptr(), (const half*)v.data_ptr(),
(const half*)dout.data_ptr(), lse.data_ptr<float>(), Dv.data_ptr<float>(),
dqacc.data_ptr<float>(), (half*)dk.data_ptr(), (half*)dv.data_ptr(),
cu.data_ptr<int>(), tcum.data_ptr<int>(), perm.data_ptr<int>(), ndocs, N, H, q.stride(0), k.stride(0),
v.stride(0), dout.stride(0), dk.stride(0), dv.stride(0),
(float)(scale * 1.4426950408889634), (float)scale);
C10_CUDA_KERNEL_LAUNCH_CHECK();
// raw fp32 dQ accumulator, NOT yet multiplied by the softmax scale
return {dqacc, dk, dv};
}
std::vector<torch::Tensor> bwd(torch::Tensor dout, torch::Tensor q, torch::Tensor k,
torch::Tensor v, torch::Tensor o, torch::Tensor lse,
torch::Tensor cu, torch::Tensor tcum, torch::Tensor perm, double scale) {
check_qkv(q, "q"); check_qkv(k, "k"); check_qkv(v, "v");
check_meta(q, k, v, cu, tcum);
dout = dout.contiguous();
check_qkv(dout, "dout");
TORCH_CHECK(dout.sizes() == q.sizes() && o.sizes() == q.sizes() && o.stride(2) == 1 &&
o.stride(1) == HD && dout.device() == q.device() && o.device() == q.device(),
"dout and o must match q");
TORCH_CHECK(lse.scalar_type() == at::kFloat && lse.is_contiguous() && lse.dim() == 2 &&
lse.size(0) == q.size(1) && lse.size(1) == q.size(0), "lse must be (H, N) fp32");
const int N = q.size(0), H = q.size(1), ndocs = cu.numel() - 1;
// D_i = rowsum(dO * O), fp32, laid out (H, N) like lse.
auto stream = at::cuda::getCurrentCUDAStream();
auto Dv = torch::empty({H, N}, q.options().dtype(torch::kFloat));
bwd_pre_kernel<<<(N * H * 32 + 255) / 256, 256, 0, stream>>>(
(const half*)dout.data_ptr(), (const half*)o.data_ptr(), Dv.data_ptr<float>(), N, H,
dout.stride(0), o.stride(0));
auto dqacc = torch::zeros({N, H, HD}, q.options().dtype(torch::kFloat));
auto dk = torch::empty({N, H, HD}, q.options());
auto dv = torch::empty({N, H, HD}, q.options());
// 1-D grid, heads interleaved (b = blockIdx.x / H); >= H * sum of ceil(len/64)
dim3 grid(((N + TL - 1) / TL + ndocs) * H);
bwd_kernel<<<grid, NT, 0, stream>>>(
(const half*)q.data_ptr(), (const half*)k.data_ptr(), (const half*)v.data_ptr(),
(const half*)dout.data_ptr(), lse.data_ptr<float>(), Dv.data_ptr<float>(),
dqacc.data_ptr<float>(), (half*)dk.data_ptr(), (half*)dv.data_ptr(),
cu.data_ptr<int>(), tcum.data_ptr<int>(), perm.data_ptr<int>(), ndocs, N, H, q.stride(0), k.stride(0),
v.stride(0), dout.stride(0), dk.stride(0), dv.stride(0),
(float)(scale * 1.4426950408889634), (float)scale);
C10_CUDA_KERNEL_LAUNCH_CHECK();
auto dq = torch::empty({N, H, HD}, q.options());
long n4 = (long)N * H * HD / 4;
bwd_post_kernel<<<(n4 + 255) / 256, 256, 0, stream>>>(
reinterpret_cast<const float4*>(dqacc.data_ptr<float>()),
reinterpret_cast<uint2*>(dq.data_ptr()), n4, (float)scale);
C10_CUDA_KERNEL_LAUNCH_CHECK();
return {dq, dk, dv};
}
PYBIND11_MODULE(TORCH_EXTENSION_NAME, m) {
m.def("fwd", &fwd);
m.def("bwd", &bwd);
m.def("bwd_raw", &bwd_raw);
}
|