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"""Cached eager recursive doubling using public batched point-to-point transport."""
16from __future__ import annotations
17
18
19from dataclasses import dataclass
20from functools import lru_cache
21import importlib
22from typing import Any
23
24import torch
25import torch.distributed as dist
26
27from hyper_parallel.distributed.context_parallel.kimi_delta_attention_rd_plan import (
28 RDResetPlan, build_reset_plan, build_scan_rounds,
29)
30
31
32_RD_EPILOGUE_BLOCK_ROWS = 64
33
34
35@lru_cache(maxsize=1)
36def _rd_kernels() -> Any:
37 """Load optional Ascend kernels only when an NPU epilogue is executed."""
38 return importlib.import_module(
39 "hyper_parallel.components.functional._triton.kimi_delta_attention.rd_pointwise"
40 )
41
42
43def _finish_round(product: torch.Tensor, previous: torch.Tensor, save_m: bool = True) -> torch.Tensor | None:
44 """Add the previous S and copy the next M in one launch, without fusing GEMM.
45
46 Inputs must be distinct contiguous FP32 [B,H,128,256] buffers. Only the
47 newly computed product's S half is modified; input summaries are immutable.
48 The validated scan inputs and fresh matrix product establish this layout.
49
50 Args:
51 product: Fresh contiguous FP32 packed matrix product [B, H, 128, 256].
52 previous: Previous immutable packed S/M tensor with the same layout.
53 save_m: Whether a future round consumes the new contiguous M.
54 """
55 state_width, packed_width = product.shape[-2:]
56 matrix = (torch.empty((*product.shape[:-1], state_width), dtype=product.dtype, device=product.device)
57 if save_m else None)
58 kernels = _rd_kernels()
59
60 rows = product.numel() // packed_width
61 block_rows = _RD_EPILOGUE_BLOCK_ROWS
62 kernels.kda_rd_finish_round_kernel[((rows + block_rows - 1) // block_rows,)](
63 product, previous, matrix if save_m else product,
64 row_count=rows, state_width=state_width, packed_width=packed_width,
65 block_rows=block_rows, save_matrix=save_m, num_warps=4)
66 return matrix
67
68
69def _finish_to_state(
70 product: torch.Tensor, previous: torch.Tensor, save_m: bool,
71) -> tuple[torch.Tensor | None, torch.Tensor]:
72 """Emit contiguous final-stage S alongside the unchanged packed epilogue.
73
74 Args:
75 product: Fresh contiguous FP32 packed matrix product [B, H, 128, 256].
76 previous: Previous immutable packed S/M tensor with the same layout.
77 save_m: Whether a future round consumes the new contiguous M.
78 """
79 state_width, packed_width = product.shape[-2:]
80 state = torch.empty((*product.shape[:-1], state_width), dtype=product.dtype, device=product.device)
81 matrix = torch.empty_like(state) if save_m else None
82 kernels = _rd_kernels()
83
84 rows = product.numel() // packed_width
85 block_rows = _RD_EPILOGUE_BLOCK_ROWS
86 kernels.kda_rd_finish_to_state_kernel[((rows + block_rows - 1) // block_rows,)](
87 product, previous, matrix if save_m else product, state,
88 row_count=rows, state_width=state_width, packed_width=packed_width,
89 block_rows=block_rows, save_matrix=save_m, num_warps=4)
90 return matrix, state
91
92
93class RoundExchange:
94 """Keep immutable payload alive until send completion; outputs belong to the call."""
95
96 def __init__(self, group: Any, rank: int, ranks: tuple[int, ...]) -> None:
97 """Resolve ordered peers and the process group's protocol device."""
98 if not ranks or len(set(ranks)) != len(ranks) or not 0 <= rank < len(ranks):
99 raise ValueError("RD requires unique global peers and a valid local rank")
100 if tuple(dist.get_process_group_ranks(group)) != ranks:
101 raise ValueError("RD mesh sequence order must match its communication group order")
102 self.group, self.rank, self.size, self.peers = group, rank, len(ranks), ranks
103 if dist.get_backend(group) != "hccl":
104 raise ValueError("KDA recursive doubling requires an HCCL process group")
105 # Receive-only TND ranks have no local summary to infer a device from.
106 # Load the optional extension here and bind buffers to the caller's NPU.
107 torch_npu = importlib.import_module("torch_npu")
108 self.device = torch.device("npu", torch_npu.npu.current_device())
109
110 def __call__(
111 self, payload: torch.Tensor | None, destination: int | None, source: int | None,
112 receive_shape: tuple[int, ...] | None = None,
113 ) -> torch.Tensor | None:
114 """Exchange peers, allocating only a live receive independently of the send.
115
116 Args:
117 payload: Immutable send tensor; may be absent when there is no destination.
118 destination: Group-local send peer, or None.
119 source: Group-local receive peer, or None.
120 receive_shape: Explicit receive shape, required for a receive without a payload.
121 """
122 output = self._prepare_receive(payload, destination, source, receive_shape)
123 if source is None and destination is None:
124 return output
125 operations = []
126 if source is not None:
127 operations.append(dist.P2POp(dist.irecv, output, self.peers[source], self.group))
128 if destination is not None:
129 operations.append(dist.P2POp(dist.isend, payload, self.peers[destination], self.group))
130 for handle in dist.batch_isend_irecv(operations):
131 handle.wait()
132 return output
133
134 def _prepare_receive(
135 self, payload: torch.Tensor | None, destination: int | None, source: int | None,
136 receive_shape: tuple[int, ...] | None,
137 ) -> torch.Tensor | None:
138 """Validate one exchange and allocate only its live receive buffer."""
139 if payload is None:
140 if destination is not None:
141 raise ValueError('RD send requires a payload')
142 if source is not None and receive_shape is None:
143 raise ValueError('RD receive without a payload requires a shape')
144 elif payload.device != self.device or not payload.is_contiguous():
145 raise ValueError('RD payload must be contiguous on the protocol device')
146 if any(peer is not None and not 0 <= peer < self.size for peer in (source, destination)):
147 raise ValueError('RD peer is outside the process group')
148 output = None
149 if source is not None:
150 output = (torch.empty_like(payload) if receive_shape is None else torch.empty(
151 receive_shape, dtype=torch.float32 if payload is None else payload.dtype, device=self.device))
152 return output
153
154
155def _validate_summary(
156 tensor: torch.Tensor, device: torch.device, state_shape: tuple[int, ...] | None = None,
157) -> None:
158 """Validate caller-owned S/M/G and cached transfers before any peer exchange."""
159 if (not isinstance(tensor, torch.Tensor) or tensor.ndim != 4
160 or tensor.shape[-2:] != (128, 128) or tensor.dtype != torch.float32
161 or tensor.device != device or not tensor.is_contiguous()):
162 raise ValueError("RD requires contiguous FP32 B/H/K128/V128 summaries on the protocol device")
163 if state_shape is not None and tensor.shape != state_shape:
164 raise ValueError("RD summary shape differs from the invocation")
165
166
167def _validate_backward_summary(
168 gradient: torch.Tensor | None, cache: tuple, expected: int,
169 device: torch.device, state_shape: tuple[int, ...] | None = None,
170) -> None:
171 """Reject incompatible invocation cache layouts before any peer exchange."""
172 if gradient is None:
173 if state_shape is None:
174 raise ValueError("RD gradient may be absent only with invocation shape metadata")
175 else:
176 _validate_summary(gradient, device, state_shape)
177 state_shape = gradient.shape
178 if not isinstance(cache, tuple) or len(cache) != expected:
179 raise ValueError("RD received an incompatible invocation cache")
180 for matrix in cache:
181 _validate_summary(matrix, device, state_shape)
182
183
184def _compact_transfer(matrix: torch.Tensor) -> torch.Tensor:
185 """Keep a contiguous M view from retaining a larger producer allocation."""
186 if matrix.untyped_storage().nbytes() != matrix.numel() * matrix.element_size():
187 return matrix.clone()
188 return matrix
189
190
191class KDAStateRecursiveDoubling:
192 """Exclusive forward scan and its cached adjoint, preserving the established rounding.
193
194 Caller creates/warm-ups the HCCL group collectively. Inputs are immutable,
195 contiguous FP32 B/H/K128/V128 summaries. Keep the returned invocation cache
196 with its own autograd context. No shared graph buffers or mutable layer state.
197 """
198
199 requires_contiguous_summaries = True
200
201 def __init__(self, group: Any, rank: int, ranks: tuple[int, ...]) -> None:
202 """Prepare communication metadata and logarithmic scan distances."""
203 self.exchange = RoundExchange(group, rank, ranks)
204 self.rank, self.size = self.exchange.rank, self.exchange.size
205 self.device = self.exchange.device
206 self.distances = tuple(1 << level for level in range((self.size - 1).bit_length()))
207 self.rounds = build_scan_rounds(self.rank, self.size, self.distances)
208
209 def bind_sequence(
210 self, sequence_info: Any, state_shape: tuple[int, ...] | None = None,
211 ) -> _ResetRDInvocation:
212 """Bind immutable packed metadata, optionally allowing absent dead summaries.
213
214 Args:
215 sequence_info: This call's packed document offsets and local interval.
216 state_shape: B/H/K/V dimensions, without retaining a tensor allocation.
217 """
218 if sequence_info.start != self.rank * sequence_info.length:
219 raise ValueError("RD packed interval must follow the state process-group order")
220 if state_shape is not None:
221 state_shape = tuple(state_shape)
222 if (len(state_shape) != 4 or state_shape[-2:] != (128, 128)
223 or any(not isinstance(dim, int) or dim < 1 for dim in state_shape)):
224 raise ValueError("RD invocation shape requires positive B/H and K=V128")
225 plan = build_reset_plan(sequence_info.documents, sequence_info.length, self.size, self.rank)
226 return _ResetRDInvocation(self, plan, state_shape)
227
228 def directional_plan(self, sequence_info: Any, local_length: int, reverse: bool = False) -> RDResetPlan:
229 """Reuse reset planning for independent forward or reverse affine maps.
230
231 Args:
232 sequence_info: Packed metadata, or None for one continuous document.
233 local_length: Equal token interval length in this state group.
234 reverse: Whether to scan fresh G/N in reverse chronological order.
235 """
236 if sequence_info is not None and sequence_info.start != self.rank * local_length:
237 raise ValueError("RD packed interval must follow the state process-group order")
238 documents = (0, self.size * local_length) if sequence_info is None else sequence_info.documents
239 return build_reset_plan(documents, local_length, self.size, self.rank, reverse=reverse)
240
241 def scan_affine(
242 self, packed: torch.Tensor | None, plan: RDResetPlan,
243 state_shape: tuple[int, ...], reverse: bool = False,
244 ) -> torch.Tensor | None:
245 """Scan independently supplied affine maps without a forward-adjoint cache.
246
247 Args:
248 packed: Immutable FP32 [B,H,128,256] S/M or G/N; absent for a dead tail.
249 plan: Directional reset plan from this invocation's metadata.
250 state_shape: B/H/K/V dimensions for receive-only fragments.
251 reverse: Map mirrored logical ranks onto the original process group.
252
253 Returns:
254 Exclusive input state, or None at a real document boundary.
255 N is already a reverse transfer and is never transposed here.
256 """
257 rank = self.size - self.rank - 1 if reverse else self.rank
258 if plan.size != self.size or plan.local_rank != rank:
259 raise ValueError("RD affine scan received another rank's directional plan")
260 rounds = plan.execution_rounds(rank)
261 destination, source = plan.shift_peers(rank)
262 if packed is None:
263 if rounds or destination is not None:
264 raise ValueError("RD affine map may be absent only without an exit consumer")
265 state = None
266 else:
267 if (packed.shape != (*state_shape[:-1], 256) or packed.dtype != torch.float32
268 or packed.device != self.device or not packed.is_contiguous()):
269 raise ValueError("RD affine maps must be contiguous FP32 [B,H,128,256] on the protocol device")
270 with torch.autocast(device_type=packed.device.type, enabled=False):
271 state = self._scan_independent_maps(packed, plan, rounds, reverse)
272 return self._exchange_direction(state, destination, source, reverse, state_shape)
273
274 def _exchange_direction(self, payload, destination, source, reverse, receive_shape=None):
275 """Reverse only logical peers; retain the original communicator and global ranks."""
276 if reverse:
277 destination = None if destination is None else self.size - destination - 1
278 source = None if source is None else self.size - source - 1
279 return self.exchange(payload, destination, source, receive_shape=receive_shape)
280
281 def _scan_independent_maps(self, packed, plan, rounds, reverse):
282 """Use FP32 Torch GEMM/add while sharing RD transport and pruning plans."""
283 state = packed[..., :128]
284 matrix = packed[..., 128:].contiguous() if rounds else None
285 for step in rounds:
286 final = step.stage == len(plan.distances) - 1
287 payload = state.contiguous() if final else packed
288 received = self._exchange_direction(payload, step.destination, step.source, reverse)
289 if received is None:
290 continue
291 if final:
292 state = matrix @ received + state
293 else:
294 updated = matrix @ received
295 updated[..., :128].add_(state)
296 packed, state = updated, updated[..., :128]
297 matrix = updated[..., 128:].contiguous() if step.save_matrix else None
298 return state.contiguous()
299
300 def _shift_peers(self, plan: RDResetPlan | None) -> tuple[int | None, int | None]:
301 """Only continued documents consume the preceding rank's exit."""
302 if plan is not None:
303 return plan.shift_peers(self.rank)
304 return (self.rank + 1 if self.rank + 1 < self.size else None,
305 self.rank - 1 if self.rank else None)
306
307 def _compose_packed_round(self, step, matrix, received, previous):
308 """Keep packed arithmetic, materializing a transfer only for a later receive."""
309 aggregate = matrix @ received
310 if 2 * self.distances[step.stage] == self.distances[-1]:
311 next_matrix, state = _finish_to_state(aggregate, previous, step.save_matrix)
312 else:
313 next_matrix = _finish_round(aggregate, previous, save_m=step.save_matrix)
314 state = None
315 return aggregate, next_matrix, state
316
317 def forward(
318 self, state: torch.Tensor | None, matrix: torch.Tensor | None,
319 plan: RDResetPlan | None = None, state_shape: tuple[int, ...] | None = None,
320 ) -> tuple[torch.Tensor | None, tuple[torch.Tensor, ...]]:
321 """Return the exclusive incoming state and immutable pre-round transfer cache.
322
323 Args:
324 state: Local summary S tensor or kernel output.
325 matrix: Contiguous FP32 local transfer M.
326 plan: Internal immutable plan supplied by the packed invocation wrapper.
327 state_shape: Optional per-call dimensions enabling absent dead summaries.
328 """
329 rounds = self.rounds if plan is None else plan.execution_rounds(self.rank)
330 destination, source = self._shift_peers(plan)
331 if state_shape is not None and plan is None:
332 raise ValueError("RD optional summaries require a packed invocation plan")
333 if state is None:
334 if state_shape is None or matrix is not None or rounds or destination is not None:
335 raise ValueError("RD state may be absent only when no exit-state consumer exists")
336 return self.exchange(None, None, source, receive_shape=state_shape), ()
337 _validate_summary(state, self.device, state_shape)
338 _validate_summary(matrix, self.device, state.shape)
339 narrow_state, cache = self._scan_forward(state, matrix, rounds)
340 received = self.exchange(narrow_state, destination, source)
341 if received is None and state_shape is None:
342 received = torch.zeros_like(state)
343 return received, cache
344
345 def _scan_forward(
346 self, state: torch.Tensor, matrix: torch.Tensor, rounds: tuple,
347 ) -> tuple[torch.Tensor, tuple[torch.Tensor, ...]]:
348 """Compose live inclusive-scan rounds, preserving per-round adjoint inputs."""
349 matrix = _compact_transfer(matrix) if rounds else matrix
350 # Reset-only shifts never consume a packed S/M payload.
351 packed = (torch.cat((state, matrix), dim=-1)
352 if any(step.stage < len(self.distances) - 1 for step in rounds) else None)
353 before_m, narrow_state = matrix, state
354 cache = []
355 for step in rounds:
356 final = step.stage == len(self.distances) - 1
357 if final and narrow_state is None:
358 narrow_state = packed[..., :128].contiguous()
359 destination, source = step.destination, step.source
360 received = self.exchange(narrow_state if final else packed, destination, source)
361 if source is not None:
362 cache.append(before_m)
363 if final:
364 narrow_state = before_m @ received + narrow_state
365 else:
366 packed, before_m, narrow_state = self._compose_packed_round(
367 step, before_m, received, packed)
368 if narrow_state is None:
369 narrow_state = packed[..., :128].contiguous()
370 return narrow_state, tuple(cache)
371
372 def backward(
373 self, gradient: torch.Tensor | None, cache: tuple[torch.Tensor, ...],
374 plan: RDResetPlan | None = None, state_shape: tuple[int, ...] | None = None,
375 ) -> torch.Tensor | None:
376 """Transpose the exact recorded forward composition order.
377
378 Args:
379 gradient: Contiguous FP32 local state-gradient summary G.
380 cache: Invocation-owned transfers returned by this protocol forward.
381 plan: The same internal plan used by this invocation's forward.
382 state_shape: The same optional per-call shape used by forward.
383 """
384 expected = (sum(self.rank >= distance for distance in self.distances)
385 if plan is None else plan.cache_count(self.rank))
386 source, destination = self._shift_peers(plan)
387 if state_shape is not None and plan is None:
388 raise ValueError("RD optional summaries require a packed invocation plan")
389 if gradient is None and destination is not None:
390 raise ValueError("RD gradient may be absent only when no head-gradient consumer exists")
391 _validate_backward_summary(gradient, cache, expected, self.device, state_shape)
392 received = (self.exchange(gradient, destination, source) if gradient is not None
393 else self.exchange(None, destination, source, receive_shape=state_shape))
394 if received is None and state_shape is not None:
395 # A tail without a consumer has no live scan rounds in a reset plan.
396 return None
397 adjoint = torch.zeros_like(gradient) if received is None else received
398 index = len(cache)
399 rounds = self.rounds if plan is None else plan.execution_rounds(self.rank)
400 for step in reversed(rounds):
401 source, destination = step.destination, step.source
402 payload = adjoint
403 if destination is not None:
404 index -= 1
405 payload = cache[index].transpose(-2, -1) @ adjoint
406 received = self.exchange(payload, destination, source)
407 if received is not None:
408 # Adjoint is invocation-owned and every send has completed.
409 adjoint.add_(received)
410 return adjoint
411
412
413@dataclass(frozen=True)
414class _ResetRDInvocation:
415 """Share static transport while keeping the exact plan with one autograd call."""
416
417 requires_contiguous_summaries = True
418
419 protocol: KDAStateRecursiveDoubling
420 plan: RDResetPlan
421 state_shape: tuple[int, ...] | None = None
422
423 @property
424 def allows_absent_summaries(self) -> bool:
425 """Whether shape metadata replaces unused full-size placeholders."""
426 return self.state_shape is not None
427
428 @property
429 def needs_state_summary(self) -> bool:
430 """Only a continuing tail document has an exit-state consumer."""
431 return self.plan.shift_peers(self.protocol.rank)[0] is not None
432
433 @property
434 def needs_transition_summary(self) -> bool:
435 """Produce M only when a consumed exit depends on this rank's entry."""
436 return self.needs_state_summary and self.plan.is_transfer_active(self.protocol.rank)
437
438 def forward(
439 self, state: torch.Tensor | None, matrix: torch.Tensor | None,
440 ) -> tuple[torch.Tensor | None, tuple[torch.Tensor, ...]]:
441 """Execute the pruned graph and return its tensor-only cache."""
442 return self.protocol.forward(state, matrix, self.plan, self.state_shape)
443
444 def backward(self, gradient: torch.Tensor | None, cache: tuple[torch.Tensor, ...]) -> torch.Tensor | None:
445 """Transpose this invocation's graph, independent of later forwards."""
446 return self.protocol.backward(gradient, cache, self.plan, self.state_shape)