DeepSpeed sequence parallelism (aka Ulysses) integration with HF transformer
Author: samadejacobs
Pull request: yes
Labels: name: DeepSpeed

# What does this PR do?
This PR enhances capabilities of [DeepSpeed long sequence (context) parallelism (aka DS Ulysses)](https://dl.acm.org/doi/10.1145/3662158.3662806) with support for HF models. Support is currently enabled when both DeepSpeed and flash attn are enabled. Future support would be extended to SPDA.  All current and future HF models (such as Llama, opt etc) using refactored flash_attention_utils are supported.

<!--
Congratulations! You've made it this far! You're not quite done yet though.

Once merged, your PR is going to appear in the release notes with the title you set, so make sure it's a great title that fully reflects the extent of your awesome contribution.

Then, please replace this with a description of the change and which issue is fixed (if applicable). Please also include relevant motivation and context. List any dependencies (if any) that are required for this change.

Once you're done, someone will review your PR shortly (see the section "Who can review?" below to tag some potential reviewers). They may suggest changes to make the code even better. If no one reviewed your PR after a week has passed, don't hesitate to post a new comment @-mentioning the same persons---sometimes notifications get lost.
-->

<!-- Remove if not applicable -->

Fixes # (issue)


## Before submitting
- [ ] This PR fixes a typo or improves the docs (you can dismiss the other checks if that's the case).
- [x] Did you read the [contributor guideline](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md#create-a-pull-request),
      Pull Request section?
- [x] Was this discussed/approved via a Github issue or the [forum](https://discuss.huggingface.co/)? Please add a link
      to it if that's the case.
- [x] Did you make sure to update the documentation with your changes? Here are the
      [documentation guidelines](https://github.com/huggingface/transformers/tree/main/docs), and
      [here are tips on formatting docstrings](https://github.com/huggingface/transformers/tree/main/docs#writing-source-documentation).
- [x] Did you write any new necessary tests?


## Who can review?

Anyone in the community is free to review the PR once the tests have passed. Feel free to tag
members/contributors who may be interested in your PR.

<!-- Your PR will be replied to more quickly if you can figure out the right person to tag with @

 If you know how to use git blame, that is the easiest way, otherwise, here is a rough guide of **who to tag**.
 Please tag fewer than 3 people.

Models:

- text models: @ArthurZucker
- vision models: @amyeroberts
- speech models: @sanchit-gandhi
- graph models: @clefourrier

Library:

- flax: @sanchit-gandhi
- generate: @zucchini-nlp (visual-language models) or @gante (all others)
- pipelines: @Narsil
- tensorflow: @gante and @Rocketknight1
- tokenizers: @ArthurZucker
- trainer: @muellerzr and @SunMarc

Integrations:

- deepspeed: HF Trainer/Accelerate: @muellerzr
- ray/raytune: @richardliaw, @amogkam
- Big Model Inference: @SunMarc
- quantization (bitsandbytes, autogpt): @SunMarc

Documentation: @stevhliu

HF projects:

- accelerate: [different repo](https://github.com/huggingface/accelerate)
- datasets: [different repo](https://github.com/huggingface/datasets)
- diffusers: [different repo](https://github.com/huggingface/diffusers)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Maintained examples (not research project or legacy):

- Flax: @sanchit-gandhi
- PyTorch: See Models above and tag the person corresponding to the modality of the example.
- TensorFlow: @Rocketknight1

 -->
@muellerzr 

Comments:
cc @SunMarc 

The docs for this PR live [here](https://moon-ci-docs.huggingface.co/docs/transformers/pr_32305). All of your documentation changes will be reflected on that endpoint. The docs are available until 30 days after the last update.

@samadejacobs  I'm glad to see this pr will be merged soon. When are you going to support sdpa in the future? It's useful for me.

> @samadejacobs I'm glad to see this pr will be merged soon. When are you going to support sdpa in the future? It's useful for me.

Yes, but I want to run it on the npu, but it doesn't support flash2, but sdpa.

@samadejacobs anything I can do to help get this merged? 

> @samadejacobs I'm glad to see this pr will be merged soon. When are you going to support sdpa in the future? It's useful for me.

@glowwormX, future support would be extended to SPDA.

> @samadejacobs anything I can do to help get this merged?

@ArthurZucker, many thanks, please see my earlier response.

Hey @samadejacobs ! 
Ah, I am not sure I have bandwidth right now for https://github.com/huggingface/transformers/pull/32305#discussion_r1769601049, but if you can't do it will see if I can ping someone or do it! 

Hi, do I understand correctly that this PR deals only with attention support? 
As far as I understand, sequence parallelism requires that two or more workers are given the same data, and this requires adjustments in trainers and dataloaders.

@samadejacobs so how is this going now? 

I have been working on this for my team in Bloomberg. I think I may have a PR that merges changes from everybody that works. Will share shortly and hopefully we can get this feature in.

cc @XuehaiPan

Hi, I'd like to know about plan to merge it and I would be happy to help with it.

I have recently [implemented](https://github.com/turbo-llm/turbo-alignment/pull/67) Ulyssys attention in our turbo-alignment library, which is built on Transformers library and heavily uses both Transformers models and Trainer. 
Despite not being merged, that PR is quite well tested and we have sucesfully trained several models with large context with this code.

From this experience I have learnt, that to achieve  this, we need to take several steps.

1. Add or patch existing attention modules. Like in this PR, this could be done with a decorator. The problem is eager attention module, which is repeated across many models, [Gemma](https://github.com/huggingface/transformers/blob/main/src/transformers/models/gemma2/modular_gemma2.py#L216) and [Llama](https://github.com/huggingface/transformers/blob/main/src/transformers/models/llama/modeling_llama.py#L171) for example. It can be questioned whether one, who would like to use context parallelism, will use eager implementation, so IMHO, eager attention can be left for later.

2. Adjust all computations which use world size. For example, number of training steps in the Trainer [code](https://github.com/huggingface/transformers/blob/main/src/transformers/trainer.py#L2277), and in some places in the Accelerate, for example in data loader [preparing](https://github.com/huggingface/accelerate/blob/main/src/accelerate/accelerator.py#L2339). This is important for right datasets sharding across workers.

3. Perfectly synchronize all the random generators inside one sequence parallel group, since otherwise, one can get different permutations 

4. Deal with position numbering and KV caches. As of today, in the absence of cache, positions_ids will be assigned to numbers from 0 to `seq_length - 1` and this has to be adjusted to reflect that i-th worker in the sequence parallel group see only subset of tokens (see Gemma 2 [code](https://github.com/huggingface/transformers/blob/main/src/transformers/models/gemma2/modular_gemma2.py#L413-L420) for example. This is not hard to do. But I don't know how to deal with caches, in our implementation we explicitly disable them. 

5. Attention masks. It seem right, that each worker inside sequence parallel group sees all the attention mask (worker needs it to compute the attention), so some around computing lengths and cache positions should be adjusted. 

6. Generation. The generation process requires that we at each step regroup the whole sentence. Also, at each step we have to deal with KV caches

7. Workers discovery. As far as I know, there are two approaches: model parallel unit and torch device mesh.

8. Loss computation. We have taken a Deepspeed approach to compute the cross-entropy. But all other losses, like for sequence classification, should be adjusted as well.


I would love to discuss this issuses and help to deal with them.

I am also aware of [another](https://github.com/huggingface/transformers/issues/35983) context parallel approach, but seems like this great library can have both, right?

We will soon have a new PR from deepspeed team ! I will close this one once they open it. Sorry that this one didn't get merged. 

> We will soon have a new PR from deepspeed team ! I will close this one once they open it. Sorry that this one didn't get merged.

Hi @SunMarc, is there any update on this topic? Any expected timeline? Thanks :)

cc @stas00 do you know when you are planning to land this ? 

@SunMarc, please kindly sync with @S1ro1 - we are waiting for him to complete the redesign of the parallelism in HF Accelerate. https://github.com/huggingface/accelerate/pull/3673

@stas00 I think given my limited availability recently and the time I'll be able to get to doing it in DeepSpeed, you can probably just integrate it with DeepSpeed as is and we'll do the refactor separately, else I don't think its entirely realistic to get it merged soon enough.

> you can probably just integrate it with DeepSpeed

I'm not sure what you mean, Matej. It's already in Deepspeed. Unless you mean in the Deepspeed plugin of HF Accelerate?

What's the rough new ETA for your work?