TASP: Topology-aware Sequence Parallelism

Yida Wang, Ke Hong, Xiuhong Li, Yuanchao Xu, Wenxun Wang, Guohao Dai, Yu Wang [email protected], [email protected] · 2025

Read TASP: Topology-aware Sequence Parallelism by Yida Wang, Ke Hong, Xiuhong Li, Yuanchao Xu, Wenxun Wang, Guohao Dai, Yu Wang [email protected], [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-26541.txt.

Introduction

Yida Wang and six co-authors present a study from twenty twenty-five on speeding up long text work in large language models. These models slow down fast as text grows, since each word must check all words before it. A known method splits the work across chips, but its data flow wastes the links in new chip layouts.

Their method, named TASP, reshapes both the chip layout and the data flow into rings that can run side by side. Tests ran on NVIDIA and AMD chips, in one box and across boxes. TASP moved data more fast than the old ring method and its zigzag form. Speed gains reached more than three fold. The team shares its code in a public file store.

Catalog record

CREATORYida Wang, Ke Hong, Xiuhong Li, Yuanchao Xu, Wenxun Wang, Guohao Dai, Yu Wang [email protected], [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-26541

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

TASP: Topology-aware Sequence Parallelism Yida Wang, Ke Hong, Xiuhong Li, Yuanchao Xu, Wenxun Wang, Guohao Dai, Yu Wang [email protected], [email protected] Abstract Long-context large language models (LLMs) face constraints due to the quadratic complexity of the self-attention mechanism. The mainstream sequence parallelism (SP) method, Ring Attention, attempts to solve this by distributing the query into multiple query chunks across accelerators and enable each Q tensor to access all KV tensors from other accelerators via the Ring AllGather communication primitive. However, it exhibits low communication efficiency, restricting its practical applicability. This inefficiency stems from the mismatch between the Ring AllGather communication primitive it adopts and the AlltoAll topology of modern accelerators. A Ring AllGather primitive is composed of iterations of ring-styled data transfer, which can only utilize a very limited fraction of an AlltoAll topology. Inspired by the Hamiltonian decomposition of complete directed graphs, we identify that modern accelerator topology can be decomposed into multiple orthogonal ring datapaths which can concurrently transfer data without interference. Based on this, we further observe that the Ring AllGather primitive can also be decomposed into the same number of concurrent ring-styled data transfer at every iteration. Based on these insights illustrated in Figure 1 , we propose TASP , a topology-aware SP method for long-context LLMs that fully utilizes the communication capacity of modern accelerators via topology decomposition and primitive decomposition . Experimental results on both single-node and multi-node NVIDIA H100 systems and a single-node AMD MI300X system demonstrate that TASP achieves higher communication efficiency than Ring Attention on these modern accelerator topologies and achieves up to 3.58 × \times speedup than Ring Attention and its variant Zigzag-Ring Attention. The code is available at https://github.com/infinigence/HamiltonAttention . ${}^{1}$ ${}^{1}$ footnotetext: Capital Normal University ${}^{2}$ ${}^{2}$ footnotetext: Tsinghua University ${}^{3}$ ${}^{3}$ footnotetext: Infinigence-AI ${}^{4}$ ${}^{4}$ footnotetext: Shanghai Jiao Tong University \faIconFromMacro{faEnvelope} \faIconFromMacro{faEnvelope} footnotetext: Corresponding authors: Yuanchao Xu, Yu Wang Figure 1: The mismatch between the ring-style data transfer of Ring AllGather and the fully-connected communication links of modern accelerators. 1 Introduction The rapid advancement of large language models (LLMs) has ushered in a new era of long-context capabilities, with modern systems now supporting context windows extending to several million tokens [ 1 , 2 ] . This breakthrough is critical for complex tasks that require reasoning over massive datasets, such as processing lengthy legal documents, performing whole-codebase analysis, or engaging in extended multi-modal dialogues. However, the core architecture of the popular Transformer model presents a fundamental scalability bottleneck: the quadratic computational complexity of the self-attention mechanism [ 3 ] . This poses a significant challenge for inference on these long queries, as the resource demands for computation and key-value (KV) tensor storage quickly become prohibitively expensive on a single accelerator. To address these constraints, Sequence Parallelism (SP) methods [ 4 , 5 , 6 , 7 , 8 ] have emerged as a key technique for long-context training and inference. Through distributing the prolonged sequence dimension of long-context queries across a cluster of accelerators, they effectively shard the computational load and reduce the memory footprint on each accelerator, making long-context processing more feasible. However, these approaches suffer from notable limitations: Ulysses [ 5 ] ties the degree of parallelism to the number of Attention KV heads, which can not scale well. The other mainstream works, Ring Attention and its variants [ 4 , 6 , 7 , 8 ] , have no scalability constraint but have communication efficiency issues. These works first chunk the query into query chunks and distribute the these chunks to multiple accelerators, and then each accelerator computes the corresponding Q chunk and KV Chunk. Since each Q chunk requires all of the KV Chunks, an AllGather of these KV chunks must be performed. Unfortunately, the standard AllGather primitive has a constraint that each accelerator needs to store all the KV Chunks aggregated from other accelerators, failing to reduce the memory consumption. Thus, Ring Attention decomposes the AllGather on n accelerators into n-1 iterations of the ring-style data transfer (as shown in Figure 4 ). In fact, this ring-style implementation of the AllGather primitive (denoted in this paper as Ring AllGather) is one of the oldest MPICH implementations of the AllGather primitive [ 9 ] . The benefits of Ring AllGather are two-fold: (1) it incurs no data duplication at each iteration of communication and computation; and (2) the communication can be fully overlapped by computation in each iteration if the compute-to-communication ratio (CCR) is above 1.0 . Unfortunately, Ring AllGather suffers from the problem of low communication efficiency since each iteration of its ring-style data transfer can only utilize a small portion of communication links within the AlltoAll accelerator topology. As shown in Figure 1 , the utilization of full communication capacity is 1/(n-1) , which is approximately 14.3% when n=8 . This inefficiency in communication results in a low CCR of Ring Attention on modern accelerator systems, as shown in Table 1 . Consequently, the communication overhead of Ring Attention fails to be overlapped with computation, thus becoming the primary bottleneck that limits its overall performance. To this end, we propose TASP , a novel sequence parallelism methodology designed to overcome the communication bottleneck of Ring Attention by fully leveraging all the communication capacity in modern accelerator clusters. Our key insight is that the mismatch between the ring-style data transfer of Ring AllGather and the fully-connected communication links in modern accelerator clusters can be solved by topology decomposition and primitive decomposition , as shown in Figure 1 . In terms of the topology decomposition, inspired by the Hamiltonian decomposition of complete directed graphs, we identify that the modern accelerator topology can be decomposed into multiple orthogonal ring datapaths that can concurrently transfer data in a ring-style without mutual interference. We first analyze the decomposition of the AlltoAll topology of a single-node into n-1 edge-disjoint Hamiltonian cycles, where vertices represent accelerators and edges represent peer-to-peer communication links. The detailed decomposition scheme is illustrated in Figure 2 , and the formulation of this scheme is presented in Section 3.1 . Apart from the single-node scenario, Hamiltonian decomposition schemes also exist for multi-node topologies based on IB/RoCE network switches which are commonly adopted in modern AI data-centers. Table 1: Evaluation of CCR and speedup of TASP over Ring Attention, measured with a batch size of 48 on 8 AMD-MI300X across different sequence lengths. SeqLen 10K 20K 40K 50K 100K CCR 0.39 0.65 0.80 0.98 1.17 Speedup 2.4 1.8 1.5 1.3 1.1 Building upon the topology decomposition, we need to accordingly decompose the ring-style data transfer in each iteration of Ring AllGather into multiple orthogonal ring-style data transfer (We denote them all-together as Multi-Ring AllGather in this paper). In this way, we can achieve perfect mapping between these orthogonal ring-style data transfer and the orthogonal ring datapaths obtained from topology decomposition, as shown in Figure 1 . We prove that Multi-Ring AllGather is equivalent to Ring AllGather in terms of distributed Attention computation through a comprehensive analysis of Ring AllGather’s characteristics in accessibility and zero-copy. Moreover, considering the widely-adopted causal mask in LLMs, we present a query chunk placement strategy to further improve the workload balance between accelerators. Through extensive experiments, we demonstrate that TASP provides a

Read the complete text