1# Copyright 2026 Huawei Technologies Co., Ltd
2#
3# Licensed under the Apache License, Version 2.0 (the "License");
4# you may not use this file except in compliance with the License.
5# You may obtain a copy of the License at
6#
7# http://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS,
11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12# See the License for the specific language governing permissions and
13# limitations under the License.
14# ============================================================================
15# Copyright (c) 2023-2025, Songlin Yang, Yu Zhang
16# Copyright (c) 2023-2025, By Triton_Ascend & sglang_ascend
17# Copyright (c) 2026, Huawei Technologies Co., Ltd. All rights reserved.
18
19# pylint: disable=missing-public-type-hints,missing-public-docstring,invalid-name
20# pylint: disable=import-outside-toplevel,unused-argument,unused-import
21# pylint: disable=missing-module-docstring,missing-function-docstring
22
23import os
24from typing import Optional
25
26import torch
27import triton
28import triton.language as tl
29
30from .utils import prepare_chunk_indices, make_tensor_descriptor, input_guard
31
32
33def _ensure_slice_ops() -> bool:
34 """Probe and attach tl.extract_slice / insert_slice if missing; return success."""
35 if hasattr(tl, "extract_slice") and hasattr(tl, "insert_slice"):
36 return True
37 try:
38 from triton.language.extra.cann.extension import extract_slice, insert_slice
39 tl.extract_slice = extract_slice
40 tl.insert_slice = insert_slice
41 return True
42 except ImportError:
43 return False
44
45_TRITON_SLICE_AVAILABLE: bool = _ensure_slice_ops()
46FLA_TRIL_PRECISION = os.environ.get('FLA_TRIL_PRECISION', 'ieee')
47
48
49@triton.heuristics({"IS_VARLEN": lambda args: args["cu_seqlens"] is not None})
50@triton.jit(do_not_specialize=["T"])
51def solve_tril_16x16_loop_kernel_paral_v3(
52 A_ptr,
53 Ad_ptr,
54 cu_seqlens,
55 chunk_indices,
56 T,
57 H: tl.constexpr,
58 BT: tl.constexpr,
59 IS_VARLEN: tl.constexpr,
60 LARGE_BLOCK_T: tl.constexpr,
61 NT: tl.constexpr,
62 BH: tl.constexpr,
63):
64 worker_id = tl.program_id(0)
65 total_tasks = NT * BH
66 num_tasks = total_tasks // 48
67 remainder = total_tasks - num_tasks * 48
68 upper_bound = min(total_tasks, num_tasks * (worker_id + 1) + min(worker_id + 1, remainder))
69 lower_bound = num_tasks * worker_id + min(worker_id, remainder)
70 for task_id in range(lower_bound, upper_bound):
71 i_t = task_id // BH
72 i_bh = task_id % BH
73 i_b, i_h = i_bh // H, i_bh % H
74 if IS_VARLEN:
75 i_n, i_t = tl.load(chunk_indices + i_t * 2).to(tl.int32), tl.load(
76 chunk_indices + i_t * 2 + 1
77 ).to(tl.int32)
78 bos, eos = tl.load(cu_seqlens + i_n).to(tl.int32), tl.load(
79 cu_seqlens + i_n + 1
80 ).to(tl.int32)
81 T = eos - bos
82 else:
83 bos, eos = i_b * T, i_b * T + T
84
85 A = A_ptr + (bos * H + i_h) * BT
86 Ad = Ad_ptr + (bos * H + i_h) * 16
87
88 base_t = i_t * LARGE_BLOCK_T
89
90 NTASKS: tl.constexpr = 2
91 N_BLOCKS: tl.constexpr = LARGE_BLOCK_T // 16 // NTASKS
92
93 for taskid in range(0, NTASKS):
94 base_t += taskid * (LARGE_BLOCK_T // NTASKS)
95
96 b_A = tl.zeros((N_BLOCKS, 16, 16), dtype=tl.float32) # (N_BLOCKS, 16, 16)
97 for blkid in range(0, N_BLOCKS):
98 row_start_o = base_t + blkid * 16
99 col_start_o = row_start_o % BT
100 # using ptr with mask instead of tl.load(block_ptr)
101 offs_rows_in_block = tl.arange(0, 16)
102 offs_cols_in_block = tl.arange(0, 16)
103 ptr_A_subrec16 = (
104 A
105 + row_start_o * H * BT
106 + col_start_o
107 + offs_rows_in_block[:, None] * H * BT
108 + offs_cols_in_block[None, :]
109 )
110 global_rows = row_start_o + offs_rows_in_block[:, None]
111 global_cols = col_start_o + offs_cols_in_block[None, :]
112 load_mask = (global_rows < T) & (global_cols < BT)
113 b_A_subrec16 = tl.load(ptr_A_subrec16, mask=load_mask, other=0.0).to(
114 tl.float32
115 )
116 b_A = tl.insert_slice(
117 ful=b_A,
118 sub=b_A_subrec16[None, :, :], # (1, 16, 16)
119 offsets=[blkid, 0, 0],
120 sizes=[1, 16, 16],
121 strides=[1, 1, 1],
122 )
123
124 # load multi 16x16
125 local_ori_A = tl.trans(b_A, (1, 0, 2))
126 local_ori_A = tl.reshape(local_ori_A, (16, 16 * N_BLOCKS)) # (16, N_BLOCKS*16)
127
128 # change mask into matrix elementwise action
129 tmp = tl.arange(0, 16).to(tl.float32)
130 rows = tmp[:, None]
131 cols = tmp[None, :]
132 is_lower = (rows > cols).to(b_A.dtype)
133 b_A = -b_A * is_lower
134
135 for i in range(1, 16):
136 nblks_vec16 = -tl.extract_slice(
137 local_ori_A, (i, 0), (1, 16 * N_BLOCKS), (16 * N_BLOCKS, 1)
138 )
139 b_a = tl.reshape(nblks_vec16, (N_BLOCKS, 16))
140
141 dot_tmp = tl.trans(b_a[:, :, None] * b_A, (1, 0, 2))
142 dot_product = tl.sum(dot_tmp, 0)
143 b_a = b_a + dot_product # (N_BLOCKS, 16)
144
145 b_a_new_expanded = b_a[:, None, :] # (N_BLOCKS, 1, 16)
146 b_A = tl.insert_slice(
147 ful=b_A,
148 sub=b_a_new_expanded,
149 offsets=[0, i, 0],
150 sizes=[N_BLOCKS, 1, 16],
151 strides=[1, 1, 1],
152 )
153
154 on_diagonal = rows == cols
155 b_A = tl.where(on_diagonal, b_A + 1.0, b_A)
156
157 b_A = tl.reshape(b_A, (N_BLOCKS * 16, 16))
158 # using ptr with mask instead of tl.load(block_ptr)
159 offs_rows_to_store = tl.arange(0, N_BLOCKS * 16)
160 offs_cols_to_store = tl.arange(0, 16)
161 p_Ai = (
162 Ad
163 + base_t * H * 16
164 + 0
165 + offs_rows_to_store[:, None] * H * 16
166 + offs_cols_to_store[None, :]
167 )
168 global_store_rows = base_t + offs_rows_to_store[:, None]
169 store_mask = global_store_rows < T
170 tl.store(
171 p_Ai,
172 b_A.to(p_Ai.dtype.element_ty, fp_downcast_rounding="rtne"),
173 mask=store_mask,
174 )
175
176
177@triton.heuristics({"IS_VARLEN": lambda args: args["cu_seqlens"] is not None})
178@triton.jit(do_not_specialize=["T", "NT"])
179def merge_16x16_to_32x32_loop_inverse_kernel(
180 A,
181 Ad,
182 Ai,
183 cu_seqlens,
184 chunk_indices,
185 T,
186 NT,
187 H: tl.constexpr,
188 BT: tl.constexpr,
189 IS_VARLEN: tl.constexpr,
190 BH: tl.constexpr,
191):
192 worker_id = tl.program_id(0)
193 total_tasks = NT * BH
194 num_tasks = total_tasks // 24
195 remainder = total_tasks - num_tasks * 24
196 upper_bound = min(total_tasks, num_tasks * (worker_id + 1) + min(worker_id + 1, remainder))
197 lower_bound = num_tasks * worker_id + min(worker_id, remainder)
198 for task_id in range(lower_bound, upper_bound):
199 i_tt = task_id // BH
200 i_bh = task_id % BH
201 i_b, i_h = i_bh // H, i_bh % H
202 if IS_VARLEN:
203 i_n, i_t = tl.load(chunk_indices + i_tt * 2).to(tl.int32), tl.load(
204 chunk_indices + i_tt * 2 + 1
205 ).to(tl.int32)
206 bos, eos = tl.load(cu_seqlens + i_n).to(tl.int32), tl.load(
207 cu_seqlens + i_n + 1
208 ).to(tl.int32)
209 T = eos - bos
210 else:
211 bos, eos = i_b * T, i_b * T + T
212 i_t = i_tt
213
214 A_ptr = A + (bos * H + i_h) * BT
215 Ad_ptr = Ad + (bos * H + i_h) * 16
216 Ai_ptr = Ai + (bos * H + i_h) * 32
217
218 p_A_21 = tl.make_block_ptr(
219 A_ptr, (T, BT), (H * BT, 1), (i_t * 32 + 16, 0 + i_t % (BT // 32) * 32), (16, 16), (1, 0)
220 )
221 p_Ad_11 = tl.make_block_ptr(
222 Ad_ptr, (T, 16), (H * 16, 1), (i_t * 32, 0), (16, 16), (1, 0)
223 )
224 p_Ad_22 = tl.make_block_ptr(
225 Ad_ptr, (T, 16), (H * 16, 1), (i_t * 32 + 16, 0), (16, 16), (1, 0)
226 )
227 p_Ai_11 = tl.make_block_ptr(
228 Ai_ptr, (T, 32), (H * 32, 1), (i_t * 32, 0), (16, 16), (1, 0)
229 )
230 p_Ai_22 = tl.make_block_ptr(
231 Ai_ptr, (T, 32), (H * 32, 1), (i_t * 32 + 16, 16), (16, 16), (1, 0)
232 )
233 p_Ai_21 = tl.make_block_ptr(
234 Ai_ptr, (T, 32), (H * 32, 1), (i_t * 32 + 16, 0), (16, 16), (1, 0)
235 )
236
237 A_21 = tl.load(p_A_21, boundary_check=(0, 1)).to(tl.float32)
238 Ai_11 = tl.load(p_Ad_11, boundary_check=(0, 1)).to(tl.float32)
239 Ai_22 = tl.load(p_Ad_22, boundary_check=(0, 1)).to(tl.float32)
240 Ai_21 = -tl.dot(
241 tl.dot(Ai_22, A_21, input_precision="ieee"), Ai_11, input_precision="ieee"
242 )
243 tl.store(
244 p_Ai_11,
245 Ai_11.to(p_Ai_11.dtype.element_ty, fp_downcast_rounding="rtne"),
246 boundary_check=(0, 1),
247 )
248 tl.store(
249 p_Ai_22,
250 Ai_22.to(p_Ai_22.dtype.element_ty, fp_downcast_rounding="rtne"),
251 boundary_check=(0, 1),
252 )
253 tl.store(
254 p_Ai_21,
255 Ai_21.to(p_Ai_21.dtype.element_ty, fp_downcast_rounding="rtne"),
256 boundary_check=(0, 1),
257 )
258
259
260@triton.heuristics(
261 {
262 "IS_VARLEN": lambda args: args["cu_seqlens"] is not None,
263 }
264)
265@triton.jit(do_not_specialize=["T", "NT"])
266def merge_32x32_to_64x64_loop_inverse_kernel(
267 A,
268 Ad,
269 Ai,
270 cu_seqlens,
271 chunk_indices,
272 T,
273 NT,
274 H: tl.constexpr,
275 BT: tl.constexpr,
276 IS_VARLEN: tl.constexpr,
277 BH: tl.constexpr,
278):
279 worker_id = tl.program_id(0)
280 total_tasks = NT * BH
281 num_tasks = total_tasks // 24
282 remainder = total_tasks - num_tasks * 24
283 upper_bound = min(total_tasks, num_tasks * (worker_id + 1) + min(worker_id + 1, remainder))
284 lower_bound = num_tasks * worker_id + min(worker_id, remainder)
285 for task_id in range(lower_bound, upper_bound):
286 i_tt = task_id // BH
287 i_bh = task_id % BH
288 i_b, i_h = i_bh // H, i_bh % H
289 if IS_VARLEN:
290 i_n, i_t = tl.load(chunk_indices + i_tt * 2).to(tl.int32), tl.load(
291 chunk_indices + i_tt * 2 + 1
292 ).to(tl.int32)
293 bos, eos = tl.load(cu_seqlens + i_n).to(tl.int32), tl.load(
294 cu_seqlens + i_n + 1
295 ).to(tl.int32)
296 T = eos - bos
297 else:
298 bos, eos = i_b * T, i_b * T + T
299 i_t = i_tt
300
301 A_ptr = A + (bos * H + i_h) * BT
302 Ad_ptr = Ad + (bos * H + i_h) * 32
303 Ai_ptr = Ai + (bos * H + i_h) * 64
304
305 p_A_21 = tl.make_block_ptr(
306 A_ptr, (T, BT), (H * BT, 1), (i_t * 64 + 32, 0 + i_t % (BT // 64) * 64), (32, 32), (1, 0)
307 )
308
309 p_Ad_11 = tl.make_block_ptr(
310 Ad_ptr, (T, 32), (H * 32, 1), (i_t * 64, 0), (32, 32), (1, 0)
311 )
312 p_Ad_22 = tl.make_block_ptr(
313 Ad_ptr, (T, 32), (H * 32, 1), (i_t * 64 + 32, 0), (32, 32), (1, 0)
314 )
315
316 p_Ai_11 = tl.make_block_ptr(
317 Ai_ptr, (T, 64), (H * 64, 1), (i_t * 64, 0), (32, 32), (1, 0)
318 )
319 p_Ai_22 = tl.make_block_ptr(
320 Ai_ptr, (T, 64), (H * 64, 1), (i_t * 64 + 32, 32), (32, 32), (1, 0)
321 )
322 p_Ai_21 = tl.make_block_ptr(
323 Ai_ptr, (T, 64), (H * 64, 1), (i_t * 64 + 32, 0), (32, 32), (1, 0)
324 )
325
326 A_21 = tl.load(p_A_21, boundary_check=(0, 1)).to(tl.float32)
327 Ai_11 = tl.load(p_Ad_11, boundary_check=(0, 1)).to(tl.float32)
328 Ai_22 = tl.load(p_Ad_22, boundary_check=(0, 1)).to(tl.float32)
329 Ai_21 = -tl.dot(
330 tl.dot(Ai_22, A_21, input_precision="ieee"), Ai_11, input_precision="ieee"
331 )
332 tl.store(
333 p_Ai_11,
334 Ai_11.to(p_Ai_11.dtype.element_ty, fp_downcast_rounding="rtne"),
335 boundary_check=(0, 1),
336 )
337 tl.store(
338 p_Ai_22,
339 Ai_22.to(p_Ai_22.dtype.element_ty, fp_downcast_rounding="rtne"),
340 boundary_check=(0, 1),
341 )
342 tl.store(
343 p_Ai_21,
344 Ai_21.to(p_Ai_21.dtype.element_ty, fp_downcast_rounding="rtne"),
345 boundary_check=(0, 1),
346 )
347
348
349@triton.heuristics({"IS_VARLEN": lambda args: args["cu_seqlens"] is not None})
350@triton.jit(do_not_specialize=['T'])
351def solve_tril_64x64_kernel(
352 A,
353 Ai,
354 cu_seqlens,
355 chunk_indices,
356 T,
357 H: tl.constexpr,
358 BT: tl.constexpr,
359 USE_TMA: tl.constexpr,
360 IS_VARLEN: tl.constexpr,
361 DOT_PRECISION: tl.constexpr
362):
363 i_t, i_bh = tl.program_id(0), tl.program_id(1)
364 i_b, i_h = i_bh // H, i_bh % H
365 if IS_VARLEN:
366 i_n, i_t = tl.load(chunk_indices + i_t * 2).to(tl.int32), tl.load(chunk_indices + i_t * 2 + 1).to(tl.int32)
367 bos, eos = tl.load(cu_seqlens + i_n).to(tl.int32), tl.load(cu_seqlens + i_n + 1).to(tl.int32)
368 T = eos - bos
369 else:
370 bos, eos = i_b * T, i_b * T + T
371 o_i = tl.arange(0, 64)
372 m_I = o_i[:, None] == o_i[None, :]
373
374 A = A + (bos * H + i_h) * BT
375 Ai = Ai + (bos * H + i_h) * 64
376
377 offset = (i_t * 64) % BT
378 if not USE_TMA:
379 p_A = tl.make_block_ptr(A, (T, BT), (H * BT, 1), (i_t * 64, offset), (64, 64), (1, 0))
380 b_A = -tl.load(p_A, boundary_check=(0, 1)).to(tl.float32)
381 else:
382 desc = make_tensor_descriptor(A, [T, BT], [H * BT, 1], [64, 64])
383 desc_o = make_tensor_descriptor(Ai, [T, 64], [H * 64, 1], [64, 64])
384 b_A = -desc.load([i_t * 64, offset]).to(tl.float32)
385
386 for i in range(2, min(64, T - i_t * 64)):
387 b_a = -tl.load(A + (i_t * 64 + i) * H * BT + o_i + offset)
388 b_a = b_a + tl.sum(b_a[:, None] * b_A, 0)
389 b_A = tl.where((o_i == i)[:, None], b_a, b_A)
390 b_A += m_I
391 if not USE_TMA:
392 p_Ai = tl.make_block_ptr(Ai, (T, 64), (H * 64, 1), (i_t * 64, 0), (64, 64), (1, 0))
393 tl.store(p_Ai, b_A.to(p_Ai.dtype.element_ty, fp_downcast_rounding="rtne"), boundary_check=(0, 1))
394 else:
395 desc_o.store([i_t * 64, 0], b_A.to(desc_o.dtype, fp_downcast_rounding="rtne"))
396
397
398def solve_tril_64(
399 A: torch.Tensor,
400 cu_seqlens: Optional[torch.Tensor] = None,
401 output_dtype: torch.dtype = torch.float,
402 ):
403 B, T, H, BT = A.shape
404 chunk_indices = prepare_chunk_indices(cu_seqlens, BT) if cu_seqlens is not None else None
405 NT = len(chunk_indices) if cu_seqlens is not None else triton.cdiv(T, BT)
406
407 Ai = torch.zeros_like(A, dtype=output_dtype)
408 solve_tril_64x64_kernel[NT, B * H](
409 A=A,
410 Ai=Ai,
411 cu_seqlens=cu_seqlens,
412 chunk_indices=chunk_indices,
413 T=T,
414 H=H,
415 BT=BT,
416 USE_TMA=False,
417 DOT_PRECISION=FLA_TRIL_PRECISION,
418 )
419 return Ai
420
421
422@input_guard
423def solve_tril(
424 A: torch.Tensor,
425 cu_seqlens: Optional[torch.Tensor] = None,
426 output_dtype: torch.dtype = torch.float
427) -> torch.Tensor:
428 """
429 Compute the inverse of the matrix I + A
430 A should be strictly lower triangular, i.e., A.triu() == 0.
431
432 Args:
433 A (torch.Tensor):
434 [B, T, H, BT], where BT should only be 16, 32, or 64.
435 cu_seqlens (torch.Tensor):
436 The cumulative sequence lengths of the input tensor. Default: `None`.
437 output_dtype (torch.dtype):
438 The dtype of the output tensor. Default: `torch.float`.
439 If `None`, the output dtype will be the same as the input dtype.
440
441 Returns:
442 (I + A)^-1 with the same shape as A
443 """
444 output_dtype = A.dtype if output_dtype is None else output_dtype
445 if not _TRITON_SLICE_AVAILABLE:
446 if A.shape[-1] not in [64]:
447 raise ValueError(
448 f"A shape BT should in [64], but current is {A.shape[-1]}"
449 )
450 return solve_tril_64(A, cu_seqlens, output_dtype)
451 if A.shape[-1] not in [16, 32, 64]:
452 raise ValueError(
453 f"A shape BT should in [16, 32, 64], but current is {A.shape[-1]}"
454 )
455
456 B, T, H, BT = A.shape
457 # If BT matches the current processing level (final step), use output_dtype
458 # (e.g. BF16) so the kernel can downcast internally, avoiding an extra
459 # external cast that hurts performance. Otherwise, keep FP32 to preserve
460 # precision for subsequent computation stages.
461 Ad = torch.empty(
462 B, T, H, 16, device=A.device, dtype=torch.float if BT != 16 else output_dtype
463 )
464
465 LARGE_BLOCK_T = 608 * 2
466
467 chunk_indices = (
468 prepare_chunk_indices(cu_seqlens, LARGE_BLOCK_T)
469 if cu_seqlens is not None
470 else None
471 )
472 NT = len(chunk_indices) if cu_seqlens is not None else triton.cdiv(T, LARGE_BLOCK_T)
473 solve_tril_16x16_loop_kernel_paral_v3[(48,)](
474 A,
475 Ad,
476 cu_seqlens=cu_seqlens,
477 chunk_indices=chunk_indices,
478 T=T,
479 H=H,
480 BT=BT,
481 LARGE_BLOCK_T=LARGE_BLOCK_T,
482 NT=NT,
483 BH=B * H,
484 )
485
486 if BT == 16:
487 return Ad
488
489 # Same dtype logic as above: output_dtype for the final step, FP32 otherwise.
490 Ai = torch.zeros(
491 B, T, H, 32, device=A.device, dtype=torch.float if BT != 32 else output_dtype
492 )
493
494 chunk_indices = (
495 prepare_chunk_indices(cu_seqlens, 32) if cu_seqlens is not None else None
496 )
497 NT = len(chunk_indices) if cu_seqlens is not None else triton.cdiv(T, 32)
498 merge_16x16_to_32x32_loop_inverse_kernel[(24,)](
499 A=A,
500 Ad=Ad,
501 Ai=Ai,
502 cu_seqlens=cu_seqlens,
503 chunk_indices=chunk_indices,
504 T=T,
505 H=H,
506 BT=BT,
507 NT=NT,
508 BH=B * H,
509 )
510 if BT == 32:
511 return Ai
512
513 Ad = Ai
514 # Same dtype logic as above: output_dtype for the final step, FP32 otherwise.
515 Ai = torch.zeros(
516 B, T, H, 64, device=A.device, dtype=torch.float if BT != 64 else output_dtype
517 )
518 chunk_indices = (
519 prepare_chunk_indices(cu_seqlens, 64) if cu_seqlens is not None else None
520 )
521 NT = len(chunk_indices) if cu_seqlens is not None else triton.cdiv(T, 64)
522 merge_32x32_to_64x64_loop_inverse_kernel[(24,)](
523 A=A,
524 Ad=Ad,
525 Ai=Ai,
526 cu_seqlens=cu_seqlens,
527 chunk_indices=chunk_indices,
528 T=T,
529 H=H,
530 BT=BT,
531 NT=NT,
532 BH=B * H,
533 )
534 if BT == 64:
535 return Ai
536 return Ai