scheduler.py 86.6 KB
Newer Older
1
# SPDX-License-Identifier: Apache-2.0
2
# SPDX-FileCopyrightText: Copyright contributors to the vLLM project
3

4
import enum
5
6
import os
import random
7
import time
8
from collections import deque
9
from dataclasses import dataclass, field
10
11
12
from typing import Callable, Deque, Dict, Iterable, List, Optional
from typing import Sequence as GenericSequence
from typing import Set, Tuple, Union
Woosuk Kwon's avatar
Woosuk Kwon committed
13

14
15
from vllm.config import CacheConfig, SchedulerConfig
from vllm.config.lora import LoRAConfig
16
from vllm.core.interfaces import AllocStatus, BlockSpaceManager
Woosuk Kwon's avatar
Woosuk Kwon committed
17
from vllm.logger import init_logger
18
from vllm.lora.request import LoRARequest
Woosuk Kwon's avatar
Woosuk Kwon committed
19
from vllm.sequence import (Sequence, SequenceData, SequenceGroup,
20
21
22
                           SequenceGroupBase, SequenceGroupMetadata,
                           SequenceGroupMetadataDelta, SequenceStage,
                           SequenceStatus)
23
from vllm.utils import Device, PyObjectCache
Woosuk Kwon's avatar
Woosuk Kwon committed
24

Woosuk Kwon's avatar
Woosuk Kwon committed
25
logger = init_logger(__name__)
26

27
28
29
30
31
32
33
# Test-only. If configured, decode is preempted with
# ARTIFICIAL_PREEMPTION_PROB% probability.
ENABLE_ARTIFICIAL_PREEMPT = bool(
    os.getenv("VLLM_TEST_ENABLE_ARTIFICIAL_PREEMPT", False))  # noqa
ARTIFICIAL_PREEMPTION_PROB = 0.5
ARTIFICIAL_PREEMPTION_MAX_CNT = 500

Woosuk Kwon's avatar
Woosuk Kwon committed
34

35
36
37
38
39
40
41
42
43
class PreemptionMode(enum.Enum):
    """Preemption modes.

    1. Swapping: Swap out the blocks of the preempted sequences to CPU memory
    and swap them back in when the sequences are resumed.
    2. Recomputation: Discard the blocks of the preempted sequences and
    recompute them when the sequences are resumed, treating the sequences as
    new prompts.
    """
44

45
46
47
48
    SWAP = enum.auto()
    RECOMPUTE = enum.auto()


49
50
@dataclass
class SchedulingBudget:
51
52
53
54
55
56
57
58
59
    """The available slots for scheduling.

    TODO(sang): Right now, the budget is request_id-aware meaning it can ignore
    budget update from the same request_id. It is because in normal scheduling
    path, we update RUNNING num_seqs ahead of time, meaning it could be
    updated more than once when scheduling RUNNING requests. Since this won't
    happen if we only have chunked prefill scheduling, we can remove this
    feature from the API when chunked prefill is enabled by default.
    """
60

61
62
    token_budget: int
    max_num_seqs: int
63
64
    _request_ids_num_batched_tokens: Set[str] = field(default_factory=set)
    _request_ids_num_curr_seqs: Set[str] = field(default_factory=set)
65
66
67
    # Number of cached tokens in the batch.
    _num_cached_tokens: int = 0
    # Number of actual non-cached tokens in the batch.
68
69
    _num_batched_tokens: int = 0
    _num_curr_seqs: int = 0
70
71

    def can_schedule(self, *, num_new_tokens: int, num_new_seqs: int):
72
73
74
        # We allow num_new_tokens to be 0 when the entire sequence has
        # been cached.
        assert num_new_tokens >= 0
75
        assert num_new_seqs != 0
76
77
78
        return (self.num_batched_tokens + num_new_tokens <= self.token_budget
                and self.num_curr_seqs + num_new_seqs <= self.max_num_seqs)

79
80
81
    def remaining_token_budget(self):
        return self.token_budget - self.num_batched_tokens

82
83
84
85
    def add_num_batched_tokens(self,
                               req_id: str,
                               num_batched_tokens: int,
                               num_cached_tokens: int = 0):
86
        if req_id in self._request_ids_num_batched_tokens:
87
            return
88
89
        assert num_cached_tokens >= 0
        assert num_batched_tokens >= 0
90

91
        self._request_ids_num_batched_tokens.add(req_id)
92
        self._num_batched_tokens += num_batched_tokens
93
        self._num_cached_tokens += num_cached_tokens
94
95
96

    def subtract_num_batched_tokens(self, req_id: str,
                                    num_batched_tokens: int):
97
98
        if req_id in self._request_ids_num_batched_tokens:
            self._request_ids_num_batched_tokens.remove(req_id)
99
100
101
            self._num_batched_tokens -= num_batched_tokens

    def add_num_seqs(self, req_id: str, num_curr_seqs: int):
102
        if req_id in self._request_ids_num_curr_seqs:
103
104
            return

105
        self._request_ids_num_curr_seqs.add(req_id)
106
107
108
        self._num_curr_seqs += num_curr_seqs

    def subtract_num_seqs(self, req_id: str, num_curr_seqs: int):
109
110
        if req_id in self._request_ids_num_curr_seqs:
            self._request_ids_num_curr_seqs.remove(req_id)
111
112
113
114
115
116
117
118
119
120
            self._num_curr_seqs -= num_curr_seqs

    @property
    def num_batched_tokens(self):
        return self._num_batched_tokens

    @property
    def num_curr_seqs(self):
        return self._num_curr_seqs

121
122
123
124
    @property
    def num_cached_tokens(self):
        return self._num_cached_tokens

125

126
127
128
129
130
131
132
133
134
135
@dataclass
class ScheduledSequenceGroup:
    # A sequence group that's scheduled.
    seq_group: SequenceGroup
    # The total chunk size (number of tokens) to process for next iteration.
    # 1 for decoding. Same as prompt tokens for prefill, but if prefill is
    # chunked, it can be smaller than that.
    token_chunk_size: int


136
@dataclass
137
class SchedulerOutputs:
138
    """The scheduling decision made from a scheduler."""
139

140
    # Scheduled sequence groups.
141
    scheduled_seq_groups: GenericSequence[ScheduledSequenceGroup]
142
143
144
145
    # Number of prefill groups scheduled.
    num_prefill_groups: int
    # Total number of batched tokens.
    num_batched_tokens: int
146
147
148
149
    # Blocks to swap in. List of CPU -> GPU block number.
    blocks_to_swap_in: List[Tuple[int, int]]
    # Blocks to swap out. List of GPU -> CPU block number.
    blocks_to_swap_out: List[Tuple[int, int]]
150
151
    # Blocks to copy. Source to dest block.
    blocks_to_copy: List[Tuple[int, int]]
152
153
154
155
    # Sequence groups that are going to be ignored.
    ignored_seq_groups: List[SequenceGroup]
    # The number of slots for lookahead decoding.
    num_lookahead_slots: int
156
157
    # The number of requests in the running queue
    running_queue_size: int
158
    preempted: int
159
160

    def __post_init__(self):
161
        # Swap in and swap out should never happen at the same time.
162
        assert not (self.blocks_to_swap_in and self.blocks_to_swap_out)
163

164
        self.num_loras: int = len(self.lora_requests)
165
166
167
        if self.num_loras > 0:
            self._sort_by_lora_ids()

168
    def is_empty(self) -> bool:
Woosuk Kwon's avatar
Woosuk Kwon committed
169
170
171
        # NOTE: We do not consider the ignored sequence groups.
        return (not self.scheduled_seq_groups and not self.blocks_to_swap_in
                and not self.blocks_to_swap_out and not self.blocks_to_copy)
172

173
    def _sort_by_lora_ids(self):
174
175
176
177
178
179
180
181
182
183
184
185
        assert 0 <= self.num_prefill_groups <= len(self.scheduled_seq_groups)

        def key_fn(group: ScheduledSequenceGroup):
            key = (group.seq_group.lora_int_id, group.seq_group.request_id)
            if 0 < self.num_prefill_groups < len(self.scheduled_seq_groups):
                # Sort sequence groups so that all prefills come before all
                # decodes as required by chunked prefill.
                return (not group.seq_group.is_prefill(), *key)
            return key

        self.scheduled_seq_groups = sorted(self.scheduled_seq_groups,
                                           key=key_fn)
186
187
188

    @property
    def lora_requests(self) -> Set[LoRARequest]:
189
190
191
192
193
        return {
            g.seq_group.lora_request
            for g in self.scheduled_seq_groups
            if g.seq_group.lora_request is not None
        }
194

195

196
@dataclass
197
198
199
200
201
202
class SchedulerRunningOutputs:
    """The requests that are scheduled from a running queue.

    Could contain prefill (prefill that's chunked) or decodes. If there's not
    enough memory, it can be preempted (for recompute) or swapped out.
    """
203

204
    # Selected sequences that are running and in a decoding phase.
205
    decode_seq_groups: List[ScheduledSequenceGroup]
206
207
    # Selected sequences that are running and in a prefill phase.
    # I.e., it means the prefill has been chunked.
208
    prefill_seq_groups: List[ScheduledSequenceGroup]
209
210
211
212
213
    # The preempted sequences.
    preempted: List[SequenceGroup]
    # Sequences that are swapped out.
    swapped_out: List[SequenceGroup]
    # The blocks to swap out.
214
    blocks_to_swap_out: List[Tuple[int, int]]
215
    # The blocks to copy.
216
    blocks_to_copy: List[Tuple[int, int]]
217
    # The number of slots for lookahead decoding.
218
219
    num_lookahead_slots: int

220
221
222
223
    # Optimization for fast-access to seq_group lists
    decode_seq_groups_list: List[SequenceGroup]
    prefill_seq_groups_list: List[SequenceGroup]

224
    @classmethod
225
226
227
228
    def create_empty(cls) -> "SchedulerRunningOutputs":
        return SchedulerRunningOutputs(
            decode_seq_groups=[],
            prefill_seq_groups=[],
229
230
            preempted=[],
            swapped_out=[],
231
            blocks_to_swap_out=[],
232
            blocks_to_copy=[],
233
            num_lookahead_slots=0,
234
235
            decode_seq_groups_list=[],
            prefill_seq_groups_list=[],
236
237
238
239
240
        )


@dataclass
class SchedulerSwappedInOutputs:
241
242
243
244
    """The requests that are scheduled from a swap queue.

    Could contain prefill (prefill that's chunked) or decodes.
    """
245

246
247
    # Selected sequences that are going to be swapped in and is in a
    # decoding phase.
248
    decode_seq_groups: List[ScheduledSequenceGroup]
249
250
    # Selected sequences that are going to be swapped in and in a prefill
    # phase. I.e., it means the prefill has been chunked.
251
    prefill_seq_groups: List[ScheduledSequenceGroup]
252
    # The blocks to swap in.
253
    blocks_to_swap_in: List[Tuple[int, int]]
254
    # The blocks to copy.
255
    blocks_to_copy: List[Tuple[int, int]]
256
    # The number of slots for lookahead decoding.
257
    num_lookahead_slots: int
258
259
    # Infeasible sequence groups.
    infeasible_seq_groups: List[SequenceGroup]
260
261
262
263

    @classmethod
    def create_empty(cls) -> "SchedulerSwappedInOutputs":
        return SchedulerSwappedInOutputs(
264
265
            decode_seq_groups=[],
            prefill_seq_groups=[],
266
            blocks_to_swap_in=[],
267
            blocks_to_copy=[],
268
            num_lookahead_slots=0,
269
            infeasible_seq_groups=[],
270
271
272
273
274
        )


@dataclass
class SchedulerPrefillOutputs:
275
276
277
278
279
    """The requests that are scheduled from a waiting queue.

    Could contain a fresh prefill requests or preempted requests that need
    to be recomputed from scratch.
    """
280

281
    # Selected sequences for prefill.
282
    seq_groups: List[ScheduledSequenceGroup]
283
284
285
286
287
288
289
290
291
292
293
294
295
    # Ignored sequence groups.
    ignored_seq_groups: List[SequenceGroup]
    num_lookahead_slots: int

    @classmethod
    def create_empty(cls) -> "SchedulerPrefillOutputs":
        return SchedulerPrefillOutputs(
            seq_groups=[],
            ignored_seq_groups=[],
            num_lookahead_slots=0,
        )


296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
def seq_group_metadata_builder():
    return SequenceGroupMetadata(request_id="",
                                 is_prompt=False,
                                 seq_data={},
                                 sampling_params=None,
                                 block_tables={})


def scheduler_running_outputs_builder():
    return SchedulerRunningOutputs(decode_seq_groups=[],
                                   prefill_seq_groups=[],
                                   preempted=[],
                                   swapped_out=[],
                                   blocks_to_swap_out=[],
                                   blocks_to_copy=[],
                                   num_lookahead_slots=0,
                                   prefill_seq_groups_list=[],
                                   decode_seq_groups_list=[])


def scheduled_seq_group_builder():
317
    return ScheduledSequenceGroup(SequenceGroup.__new__(SequenceGroup),
318
319
                                  token_chunk_size=0)
    # return ScheduledSequenceGroup(seq_group=None, token_chunk_size=0)
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
@dataclass
class PartialPrefillMetadata:
    """Holds information about the partial prefills that are currently running
    during a single iteration of the Scheduler.
    When chunked prefill is enabled, we allow a certain number of seqs to be
    partially prefilled during each iteration. Having multiple partial prefills
    in flight allows us to minimize TTFT and avoid decode starvation in cases
    where a single sequence group with a very large prompt blocks the queue for
    too many iterations.
    The number of long prefill requests is limited so that smaller
    requests may jump the queue in front of them and get to the decode
    phase faster.
    """

    # A minimum bound on the total number of prefills to be scheduled during
    # this iteration
    schedulable_prefills: int

    # The number of long prefill requests currently running
    long_prefills: int

    scheduler_config: SchedulerConfig

    def can_schedule(self, seq_group: SequenceGroup) -> bool:
        """When concurrent partial prefills are enabled,
        we limit the number of long requests and only accept
        shorter requests from the queue while running them
        concurrently"""
        return not (seq_group.first_seq.get_num_new_tokens()
                    > self.scheduler_config.long_prefill_token_threshold
                    and self.long_prefills
                    >= self.scheduler_config.max_long_partial_prefills
                    and self.scheduler_config.max_num_partial_prefills > 1)

    def maybe_increment_partial_prefills(self,
                                         seq_group: SequenceGroup) -> None:
        # When a new prefill is scheduled, we need to know if it is a
        # long request
        if (seq_group.first_seq.get_num_new_tokens()
                > self.scheduler_config.long_prefill_token_threshold):
            self.long_prefills += 1

    @classmethod
    def from_queues(
        cls,
        running: Deque[SequenceGroup],
        waiting: Deque[SequenceGroup],
        scheduler_config: SchedulerConfig,
    ) -> "PartialPrefillMetadata":
        """Create a PartialPrefillMetadata object from the current state of
        the scheduler's queues.
        This accounts for the currently running prefill requests, and peeks into
        the waiting queue to see if there are more prefills to potentially be
        scheduled during this iteration."""
        prefills = 0
        long_prefills = 0

        waiting_long_prefills = 0

        for sg in running:
            if sg.first_seq.data.stage == SequenceStage.PREFILL:
                prefills += 1
                if (sg.first_seq.get_num_new_tokens()
                        > scheduler_config.long_prefill_token_threshold):
                    long_prefills += 1

        for sg in waiting:
            # Don't bother looping through the rest of the queue if we know
            # there are already at
            # least max_partial_prefills requests to fill
            if prefills >= scheduler_config.max_num_partial_prefills:
                break

            # Don't count long requests from the waiting queue if we aren't
            # going to schedule them anyway
            if (sg.first_seq.get_num_new_tokens()
                    > scheduler_config.long_prefill_token_threshold):
                if (long_prefills + waiting_long_prefills
                        >= scheduler_config.max_long_partial_prefills):
                    continue
                waiting_long_prefills += 1
            prefills += 1

        # NB: long_prefills and waiting_long_prefills are tracked separately.
        # We don't account for the waiting requests here because we need to use
        # this metadata to track how many have actually been scheduled.
        return PartialPrefillMetadata(
            schedulable_prefills=min(
                prefills, scheduler_config.max_num_partial_prefills),
            long_prefills=long_prefills,
            scheduler_config=scheduler_config,
        )


Woosuk Kwon's avatar
Woosuk Kwon committed
416
417
class Scheduler:

Woosuk Kwon's avatar
Woosuk Kwon committed
418
    def __init__(
Woosuk Kwon's avatar
Woosuk Kwon committed
419
        self,
420
421
        scheduler_config: SchedulerConfig,
        cache_config: CacheConfig,
422
        lora_config: Optional[LoRAConfig],
423
        pipeline_parallel_size: int = 1,
424
        output_proc_callback: Optional[Callable] = None,
Woosuk Kwon's avatar
Woosuk Kwon committed
425
    ) -> None:
426
427
        self.scheduler_config = scheduler_config
        self.cache_config = cache_config
428
429
430
431
        # Note for LoRA scheduling: the current policy is extremely
        # simple and NOT fair. It can lead to starvation of some
        # LoRAs. This should be improved in the future.
        self.lora_config = lora_config
Woosuk Kwon's avatar
Woosuk Kwon committed
432

433
        version = "selfattn"
434
        if (self.scheduler_config.runner_type == "pooling"
435
436
                or self.cache_config.is_attention_free):
            version = "placeholder"
437

438
        BlockSpaceManagerImpl = BlockSpaceManager.get_block_space_manager_class(
439
            version)
440

441
442
443
444
445
446
447
448
        num_gpu_blocks = cache_config.num_gpu_blocks
        if num_gpu_blocks:
            num_gpu_blocks //= pipeline_parallel_size

        num_cpu_blocks = cache_config.num_cpu_blocks
        if num_cpu_blocks:
            num_cpu_blocks //= pipeline_parallel_size

Woosuk Kwon's avatar
Woosuk Kwon committed
449
        # Create the block space manager.
450
        self.block_manager = BlockSpaceManagerImpl(
451
            block_size=self.cache_config.block_size,
452
453
            num_gpu_blocks=num_gpu_blocks,
            num_cpu_blocks=num_cpu_blocks,
454
            sliding_window=self.cache_config.sliding_window,
455
456
            enable_caching=self.cache_config.enable_prefix_caching,
        )
457

458
        # Sequence groups in the WAITING state.
459
        # Contain new prefill or preempted requests.
460
        self.waiting: Deque[SequenceGroup] = deque()
461
        # Sequence groups in the RUNNING state.
462
        # Contain decode requests.
463
        self.running: Deque[SequenceGroup] = deque()
464
        # Sequence groups in the SWAPPED state.
465
        # Contain decode requests that are swapped out.
466
        self.swapped: Deque[SequenceGroup] = deque()
Mor Zusman's avatar
Mor Zusman committed
467
468
469
        # Sequence groups finished requests ids since last step iteration.
        # It lets the model know that any state associated with these requests
        # can and must be released after the current step.
470
        # This is used to evict the finished requests from the Mamba cache.
Mor Zusman's avatar
Mor Zusman committed
471
        self._finished_requests_ids: List[str] = list()
472
473
474
475
476
477
        # Time at previous scheduling step
        self.prev_time = 0.0
        # Did we schedule a prompt at previous step?
        self.prev_prompt = False
        # Latency of the last prompt step
        self.last_prompt_latency = 0.0
478
479
        # preemption mode, RECOMPUTE or SWAP
        self.user_specified_preemption_mode = scheduler_config.preemption_mode
480

481
482
483
484
485
486
        # The following field is test-only. It is used to inject artificial
        # preemption.
        self.enable_artificial_preemption = ENABLE_ARTIFICIAL_PREEMPT
        self.artificial_preempt_cnt = (ARTIFICIAL_PREEMPTION_MAX_CNT
                                       if self.enable_artificial_preemption
                                       else 0)
487
        self.num_cumulative_preemption: int = 0
488

489
        # Used to cache python objects
490
491
492
493
494
495
496
497
        self._seq_group_metadata_cache: List[PyObjectCache] = []
        self._scheduler_running_outputs_cache: List[PyObjectCache] = []
        self._scheduled_seq_group_cache: List[PyObjectCache] = []

        # For async output processing, we need to swap cache buffers between
        # iterations. I.e. since the output processing is lagged one step,
        # we cannot reuse the cached objects immediately when the schedule()
        # is called again, but only when schedule() is called the second time.
498
499
        self.output_proc_callback = output_proc_callback
        self.use_async_output_proc = self.output_proc_callback is not None
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
        self.num_cache_iters = 2 if self.use_async_output_proc else 1

        self.cache_id = 0
        for i in range(self.num_cache_iters):
            self._seq_group_metadata_cache.append(
                PyObjectCache(seq_group_metadata_builder))
            self._scheduler_running_outputs_cache.append(
                PyObjectCache(scheduler_running_outputs_builder))
            self._scheduled_seq_group_cache.append(
                PyObjectCache(scheduled_seq_group_builder))

        # For async postprocessor, the extra decode run cannot be done
        # when the request reaches max_model_len. In this case, the request
        # will be stopped during schedule() call and added to this stop list
        # for processing and deallocation by the free_finished_seq_groups()
        self._async_stopped: List[SequenceGroup] = []

517
518
519
520
521
522
523
524
525
526
527
528
        # List with the chunk sizes to hand out to each sequence depending
        # on how many partial prefills are running. This is slightly faster than
        # running an integer division every time a prefill is scheduled.
        # This splits the budget evenly among all prefills.
        self.partial_prefill_budget_lookup_list = [0] * (
            self.scheduler_config.max_num_partial_prefills + 1)
        self.partial_prefill_budget_lookup_list[0] = (
            scheduler_config.max_num_batched_tokens)
        for i in range(1, self.scheduler_config.max_num_partial_prefills + 1):
            self.partial_prefill_budget_lookup_list[i] = (
                scheduler_config.max_num_batched_tokens // i)

529
530
531
    @property
    def next_cache_id(self):
        return (self.cache_id + 1) % self.num_cache_iters
532

533
534
535
536
    @property
    def lora_enabled(self) -> bool:
        return bool(self.lora_config)

537
538
539
540
541
    @property
    def num_decoding_tokens_per_seq(self) -> int:
        """The number of new tokens."""
        return 1

542
    def add_seq_group(self, seq_group: SequenceGroup) -> None:
543
        # Add sequence groups to the waiting queue.
544
        self.waiting.append(seq_group)
Woosuk Kwon's avatar
Woosuk Kwon committed
545

546
547
548
549
550
551
552
553
554
555
    def _add_seq_group_to_running(self, seq_group: SequenceGroup) -> None:
        # Add sequence groups to the running queue.
        # Only for testing purposes.
        self.running.append(seq_group)

    def _add_seq_group_to_swapped(self, seq_group: SequenceGroup) -> None:
        # Add sequence groups to the swapped queue.
        # Only for testing purposes.
        self.swapped.append(seq_group)

556
557
558
559
560
    def abort_seq_group(
        self,
        request_id: Union[str, Iterable[str]],
        seq_id_to_seq_group: Optional[Dict[str, SequenceGroupBase]] = None,
    ) -> None:
561
562
563
564
565
566
567
568
569
570
571
        """Aborts a sequence group with the given ID.

        Check if the sequence group with the given ID
            is present in any of the state queue.
        If present, remove the sequence group from the state queue.
            Also, if any of the sequences in the sequence group is not finished,
                free the sequence with status `FINISHED_ABORTED`.
        Otherwise, do nothing.

        Args:
            request_id: The ID(s) of the sequence group to abort.
572
            seq_id_to_seq_group: helper for groups with n>1
573
        """
Antoni Baum's avatar
Antoni Baum committed
574
575
576
        if isinstance(request_id, str):
            request_id = (request_id, )
        request_ids = set(request_id)
577
        seq_id_to_seq_group = seq_id_to_seq_group or {}
578
        for state_queue in [self.waiting, self.running, self.swapped]:
ljss's avatar
ljss committed
579
            aborted_groups: List[SequenceGroup] = []
580
            for seq_group in state_queue:
581
582
583
584
585
586
587
588
589
                # When n>1, seq_group.request_id looks like
                # foo_parallel_sample_0, while request_ids is just foo, and we
                # should resolve it as real_request_id to match.
                if seq_group.request_id in seq_id_to_seq_group:
                    real_request_id = seq_id_to_seq_group[
                        seq_group.request_id].group_id
                else:
                    real_request_id = seq_group.request_id
                if real_request_id in request_ids:
590
591
                    # Appending aborted group into pending list.
                    aborted_groups.append(seq_group)
592
593
594
                    # We can't remove real_request_id in request_ids here,
                    # because there may be other seq groups sharing the same
                    # real_request_id
595
596
597
            for aborted_group in aborted_groups:
                # Remove the sequence group from the state queue.
                state_queue.remove(aborted_group)
598
                # Remove the aborted request from the Mamba cache.
599
                self._finished_requests_ids.append(aborted_group.request_id)
ljss's avatar
ljss committed
600
                for seq in aborted_group.get_seqs():
601
602
603
604
                    if seq.is_finished():
                        continue
                    seq.status = SequenceStatus.FINISHED_ABORTED
                    self.free_seq(seq)
605
606
                if aborted_group.request_id in seq_id_to_seq_group:
                    del seq_id_to_seq_group[aborted_group.request_id]
607

608
609
610
611
612
613
614
615
616
617
618
619
620
                self._free_seq_group_cross_attn_blocks(aborted_group)

    def _free_seq_group_cross_attn_blocks(
        self,
        seq_group: SequenceGroup,
    ) -> None:
        """
        Free a sequence group from a cross-attention block table.
        Has no effect on decoder-only models.
        """
        if seq_group.is_encoder_decoder():
            self.block_manager.free_cross(seq_group)

621
    def has_unfinished_seqs(self) -> bool:
622
623
        return (len(self.waiting) != 0 or len(self.running) != 0
                or len(self.swapped) != 0)
624

625
626
627
    def get_prefix_cache_hit_rate(self, device: Device) -> float:
        return self.block_manager.get_prefix_cache_hit_rate(device)

628
629
    def reset_prefix_cache(self, device: Optional[Device] = None) -> bool:
        return self.block_manager.reset_prefix_cache(device)
630

631
632
633
    def get_num_unfinished_seq_groups(self) -> int:
        return len(self.waiting) + len(self.running) + len(self.swapped)

Mor Zusman's avatar
Mor Zusman committed
634
635
636
637
638
639
    def get_and_reset_finished_requests_ids(self) -> List[str]:
        """Flushes the list of request ids of previously finished seq_groups."""
        finished_requests_ids = self._finished_requests_ids
        self._finished_requests_ids = list()
        return finished_requests_ids

640
    def _schedule_running(
641
642
643
        self,
        budget: SchedulingBudget,
        curr_loras: Optional[Set[int]],
644
        enable_chunking: bool = False,
645
        partial_prefill_metadata: Optional[PartialPrefillMetadata] = None,
646
    ) -> SchedulerRunningOutputs:
647
        """Schedule sequence groups that are running.
648

649
        Running queue should include decode and chunked prefill requests.
Woosuk Kwon's avatar
Woosuk Kwon committed
650

651
652
653
654
655
        Args:
            budget: The scheduling budget. The argument is in-place updated
                when any decodes are preempted.
            curr_loras: Currently batched lora request ids. The argument is
                in-place updated when any decodes are preempted.
656
657
658
659
            enable_chunking: If True, seq group can be chunked and only a
                chunked number of tokens are scheduled  if
                `budget.num_batched_tokens` has not enough capacity to schedule
                all tokens.
660
            partial_prefill_metadata: information about the partial prefills
661
                that are currently running
662

663
        Returns:
664
            SchedulerRunningOutputs.
665
        """
666
667
        ret: SchedulerRunningOutputs = self._scheduler_running_outputs_cache[
            self.cache_id].get_object()
668
669
670
671
672
673
674
675
        ret.blocks_to_swap_out.clear()
        ret.blocks_to_copy.clear()
        ret.decode_seq_groups.clear()
        ret.prefill_seq_groups.clear()
        ret.preempted.clear()
        ret.swapped_out.clear()

        ret.num_lookahead_slots = self._get_num_lookahead_slots(
676
            is_prefill=False, enable_chunking=enable_chunking)
677
678
679
680

        ret.decode_seq_groups_list.clear()
        ret.prefill_seq_groups_list.clear()

681
        # Blocks that need to be swapped or copied before model execution.
682
683
        blocks_to_swap_out: List[Tuple[int, int]] = ret.blocks_to_swap_out
        blocks_to_copy: List[Tuple[int, int]] = ret.blocks_to_copy
Woosuk Kwon's avatar
Woosuk Kwon committed
684

685
686
687
688
689
        decode_seq_groups: List[ScheduledSequenceGroup] = ret.decode_seq_groups
        prefill_seq_groups: List[
            ScheduledSequenceGroup] = ret.prefill_seq_groups
        preempted: List[SequenceGroup] = ret.preempted
        swapped_out: List[SequenceGroup] = ret.swapped_out
Woosuk Kwon's avatar
Woosuk Kwon committed
690

691
692
        running_queue = self.running
        assert len(self._async_stopped) == 0
693
694
        while running_queue:
            seq_group = running_queue[0]
695
696
697
698
699
700
701
            # We discard the cached tokens info here because we don't need it
            # for running sequence:
            #   1. If a sequence is running with chunked prefill, the cached
            #      tokens info was already used for the first prefill.
            #   2. If a sequence is running with non-chunked prefill, then
            #      there it's a decoding sequence, and the cached tokens info is
            #      irrelevant.
702
            num_uncached_new_tokens, _ = \
703
                self._get_num_new_uncached_and_cached_tokens(
704
705
706
707
708
709
                seq_group,
                SequenceStatus.RUNNING,
                enable_chunking,
                budget,
                partial_prefill_metadata,
            )
710
711

            num_running_tokens = num_uncached_new_tokens
712
            if num_running_tokens == 0:
713
                # No budget => Stop
714
                break
715
716

            running_queue.popleft()
717
718
719
720
721

            # With async postprocessor, an extra decode run is done
            # to process the final tokens. The check below avoids this extra
            # decode run when the model max len is reached, in order to avoid
            # a memory overflow.
722
723
            if (self.use_async_output_proc and seq_group.seqs[0].get_len()
                    > self.scheduler_config.max_model_len):
724
725
726
                self._async_stopped.append(seq_group)
                continue

727
728
            # NOTE(woosuk): Preemption happens only when there is no available
            # slot to keep all the sequence groups in the RUNNING state.
729
            while not self._can_append_slots(seq_group, enable_chunking):
730
731
                budget.subtract_num_batched_tokens(seq_group.request_id,
                                                   num_running_tokens)
732
                num_running_seqs = seq_group.get_max_num_running_seqs()
733
734
                budget.subtract_num_seqs(seq_group.request_id,
                                         num_running_seqs)
735
736
737

                if (curr_loras is not None and seq_group.lora_int_id > 0
                        and seq_group.lora_int_id in curr_loras):
738
                    curr_loras.remove(seq_group.lora_int_id)
739

740
741
                # Determine victim sequence
                cont_loop = True
742
                if running_queue:
743
                    # Preempt the lowest-priority sequence group.
744
                    victim_seq_group = running_queue.pop()
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
                else:
                    # No other sequence group can be preempted.
                    # Preempt the current sequence group.
                    # Note: This is also where we stop this loop
                    # (since there is nothing else to preempt)
                    victim_seq_group = seq_group
                    cont_loop = False

                # With async postprocessor, before preempting a sequence
                # we need to ensure it has no pending async postprocessor
                do_preempt = True
                if self.use_async_output_proc:
                    assert self.output_proc_callback is not None
                    self.output_proc_callback(
                        request_id=victim_seq_group.request_id)

                    # It may be that the async pending "victim_seq_group"
                    # becomes finished, in which case we simply free it.
                    if victim_seq_group.is_finished():
                        self._free_finished_seq_group(victim_seq_group)
                        do_preempt = False

                # Do preemption
                if do_preempt:
769
770
771
772
773
774
                    preempted_mode = self._preempt(victim_seq_group,
                                                   blocks_to_swap_out)
                    if preempted_mode == PreemptionMode.RECOMPUTE:
                        preempted.append(victim_seq_group)
                    else:
                        swapped_out.append(victim_seq_group)
775
776

                if not cont_loop:
Woosuk Kwon's avatar
Woosuk Kwon committed
777
778
                    break
            else:
779
                self._append_slots(seq_group, blocks_to_copy, enable_chunking)
780
                is_prefill = seq_group.is_prefill()
781

782
783
784
                scheduled_seq_group: ScheduledSequenceGroup = (
                    self._scheduled_seq_group_cache[
                        self.cache_id].get_object())
785
                scheduled_seq_group.seq_group = seq_group
786
                if is_prefill:
787
788
789
                    scheduled_seq_group.token_chunk_size = num_running_tokens
                    prefill_seq_groups.append(scheduled_seq_group)
                    ret.prefill_seq_groups_list.append(seq_group)
790
                else:
791
792
793
794
                    scheduled_seq_group.token_chunk_size = 1
                    decode_seq_groups.append(scheduled_seq_group)
                    ret.decode_seq_groups_list.append(seq_group)

795
796
                budget.add_num_batched_tokens(seq_group.request_id,
                                              num_running_tokens)
797
798
799
800
801
802
803
                # OPTIMIZATION:  Note that get_max_num_running_seqs is
                # expensive. For the default scheduling chase where
                # enable_chunking is False, num_seqs are updated before running
                # this method, so we don't have to update it again here.
                if enable_chunking:
                    num_running_seqs = seq_group.get_max_num_running_seqs()
                    budget.add_num_seqs(seq_group.request_id, num_running_seqs)
804
805
806
                if curr_loras is not None and seq_group.lora_int_id > 0:
                    curr_loras.add(seq_group.lora_int_id)

807
808
        self._scheduler_running_outputs_cache[self.next_cache_id].reset()
        self._scheduled_seq_group_cache[self.next_cache_id].reset()
809
810

        return ret
811

812
813
814
815
    def _schedule_swapped(
        self,
        budget: SchedulingBudget,
        curr_loras: Optional[Set[int]],
816
        enable_chunking: bool = False,
817
    ) -> SchedulerSwappedInOutputs:
818
        """Schedule sequence groups that are swapped out.
819

820
821
822
        It schedules swapped requests as long as it fits `budget` and
        curr_loras <= max_lora from the scheduling config. The input arguments
        `budget` and `curr_loras` are updated based on scheduled seq_groups.
823

824
825
826
827
828
        Args:
            budget: The scheduling budget. The argument is in-place updated
                when any requests are swapped in.
            curr_loras: Currently batched lora request ids. The argument is
                in-place updated when any requests are swapped in.
829
830
831
832
833
            enable_chunking: If True, seq group can be chunked and only a
                chunked number of tokens are scheduled  if
                `budget.num_batched_tokens` has not enough capacity to schedule
                all tokens.

834
835
836
837
        Returns:
            SchedulerSwappedInOutputs.
        """
        # Blocks that need to be swapped or copied before model execution.
838
        blocks_to_swap_in: List[Tuple[int, int]] = []
839
        blocks_to_copy: List[Tuple[int, int]] = []
840
841
        decode_seq_groups: List[ScheduledSequenceGroup] = []
        prefill_seq_groups: List[ScheduledSequenceGroup] = []
842
        infeasible_seq_groups: List[SequenceGroup] = []
843

844
845
        swapped_queue = self.swapped

846
        leftover_swapped: Deque[SequenceGroup] = deque()
847
848
849
850
        while swapped_queue:
            seq_group = swapped_queue[0]

            # If the sequence group cannot be swapped in, stop.
851
852
            is_prefill = seq_group.is_prefill()
            alloc_status = self.block_manager.can_swap_in(
853
854
                seq_group,
                self._get_num_lookahead_slots(is_prefill, enable_chunking))
855
            if alloc_status == AllocStatus.LATER:
856
                break
857
858
859
860
            elif alloc_status == AllocStatus.NEVER:
                logger.warning(
                    "Failing the request %s because there's not enough kv "
                    "cache blocks to run the entire sequence.",
861
862
                    seq_group.request_id,
                )
863
864
865
866
867
                for seq in seq_group.get_seqs():
                    seq.status = SequenceStatus.FINISHED_IGNORED
                infeasible_seq_groups.append(seq_group)
                swapped_queue.popleft()
                continue
868
869
870
871

            lora_int_id = 0
            if self.lora_enabled:
                lora_int_id = seq_group.lora_int_id
872
873
874
                assert curr_loras is not None
                assert self.lora_config is not None
                if (lora_int_id > 0 and (lora_int_id not in curr_loras)
875
876
877
878
879
880
881
882
883
884
                        and len(curr_loras) >= self.lora_config.max_loras):
                    # We don't have a space for another LoRA, so
                    # we ignore this request for now.
                    leftover_swapped.appendleft(seq_group)
                    swapped_queue.popleft()
                    continue

            # The total number of sequences in the RUNNING state should not
            # exceed the maximum number of sequences.
            num_new_seqs = seq_group.get_max_num_running_seqs()
885
886
887
888
889
890
891
892
893
            num_new_tokens_uncached, num_new_tokens_cached = (
                self._get_num_new_uncached_and_cached_tokens(
                    seq_group, SequenceStatus.SWAPPED, enable_chunking,
                    budget))

            if num_new_tokens_uncached == 0 or not budget.can_schedule(
                    num_new_tokens=num_new_tokens_uncached,
                    num_new_seqs=num_new_seqs,
            ):
894
895
                self.remove_seq_from_computed_blocks_tracker(
                    seq_group, SequenceStatus.SWAPPED)
896
897
898
899
900
901
                break

            if lora_int_id > 0 and curr_loras is not None:
                curr_loras.add(lora_int_id)
            swapped_queue.popleft()
            self._swap_in(seq_group, blocks_to_swap_in)
902
            self._append_slots(seq_group, blocks_to_copy, enable_chunking)
903
904
            if is_prefill:
                prefill_seq_groups.append(
905
906
907
908
909
                    ScheduledSequenceGroup(
                        seq_group,
                        token_chunk_size=num_new_tokens_uncached +
                        num_new_tokens_cached,
                    ))
910
911
912
            else:
                decode_seq_groups.append(
                    ScheduledSequenceGroup(seq_group, token_chunk_size=1))
913
914
915
916
917
            budget.add_num_batched_tokens(
                seq_group.request_id,
                num_batched_tokens=num_new_tokens_uncached,
                num_cached_tokens=num_new_tokens_cached,
            )
918
            budget.add_num_seqs(seq_group.request_id, num_new_seqs)
919
920
921

        swapped_queue.extendleft(leftover_swapped)

922
        return SchedulerSwappedInOutputs(
923
924
            decode_seq_groups=decode_seq_groups,
            prefill_seq_groups=prefill_seq_groups,
925
926
            blocks_to_swap_in=blocks_to_swap_in,
            blocks_to_copy=blocks_to_copy,
927
            num_lookahead_slots=self._get_num_lookahead_slots(
928
                is_prefill=False, enable_chunking=enable_chunking),
929
930
            infeasible_seq_groups=infeasible_seq_groups,
        )
931

932
    def _get_prompt_limit(self, seq_group: SequenceGroup) -> int:
933
        if self.scheduler_config.chunked_prefill_enabled:
934
935
            prompt_limit = self.scheduler_config.max_model_len
        else:
936
937
938
939
            prompt_limit = min(
                self.scheduler_config.max_model_len,
                self.scheduler_config.max_num_batched_tokens,
            )
940
941

        # Model is fine tuned with long context. Return the fine tuned max_len.
942
        if seq_group.lora_request and seq_group.lora_request.long_lora_max_len:
943
944
945
946
947
            assert prompt_limit <= seq_group.lora_request.long_lora_max_len
            return seq_group.lora_request.long_lora_max_len
        else:
            return prompt_limit

948
949
    def _get_priority(self,
                      seq_group: SequenceGroup) -> Tuple[Optional[int], float]:
950
        """Get the priority of the sequence group.
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
        Highest preference to user-defined priority, followed by arrival time.
        Args:
            seq_group: The sequence group input.
        Returns:
            The priority of the sequence group.
        """
        return seq_group.priority, seq_group.arrival_time

    def _schedule_priority_preemption(
        self,
        budget: SchedulingBudget,
    ) -> int:
        """Sorts waiting and running queue. Also, force preempt requests
        from the running queue if their priority is lower.
        Priority-based preemption is used with the priority policy.
        Args:
            budget: The scheduling budget. The argument is in-place updated
                when any requests are scheduled.
        Returns:
            A count of priority-based preemptions.
        """

        waiting_queue = self.waiting

        running_queue = deque(sorted(self.running, key=self._get_priority))

        blocks_to_swap_out: List[Tuple[int, int]] = []
        force_preemption_count = 0

        if waiting_queue:
            seq_group = waiting_queue.popleft()
            num_new_seqs = seq_group.get_max_num_running_seqs()
983
            num_new_tokens_uncached, _ = \
984
                self._get_num_new_uncached_and_cached_tokens(
985
                seq_group, SequenceStatus.WAITING, False, budget)
986

987
            # Only preempt if priority inversion exists
988
989
            while running_queue and self._get_priority(
                    running_queue[-1]) > self._get_priority(seq_group):
990
                # Only preempt if waiting sequence cannot be allocated
991
                can_allocate = self.block_manager.can_allocate(seq_group)
992
993
994
995
996
997
                if (num_new_tokens_uncached > 0
                        and can_allocate == AllocStatus.OK
                        and budget.can_schedule(
                            num_new_tokens=num_new_tokens_uncached,
                            num_new_seqs=num_new_seqs,
                        )):
998
999
                    break

1000
                # Adjust budget to remove the victim sequence group
1001
                vseq_group = running_queue.pop()
1002
1003
1004
1005
1006
                num_running_tokens_uncached, _ = (
                    self._get_num_new_uncached_and_cached_tokens(
                        vseq_group, SequenceStatus.RUNNING, False, budget))
                budget.subtract_num_batched_tokens(
                    vseq_group.request_id, num_running_tokens_uncached)
1007
1008
1009
1010
                num_running_seqs = vseq_group.get_max_num_running_seqs()
                budget.subtract_num_seqs(vseq_group.request_id,
                                         num_running_seqs)

1011
                # Preempt out the victim sequence group
1012
                self._preempt(vseq_group, blocks_to_swap_out)
1013
1014
                waiting_queue.appendleft(vseq_group)
                force_preemption_count += 1
1015
            # Put the sequence back into the waiting queue
1016
1017
            waiting_queue.appendleft(seq_group)

1018
1019
1020
            self.remove_seq_from_computed_blocks_tracker(
                seq_group, SequenceStatus.WAITING)

1021
1022
1023
1024
1025
1026
        waiting_queue = deque(sorted(waiting_queue, key=self._get_priority))

        self.waiting = waiting_queue
        self.running = running_queue
        return force_preemption_count

1027
1028
1029
1030
    def _schedule_prefills(
        self,
        budget: SchedulingBudget,
        curr_loras: Optional[Set[int]],
1031
        enable_chunking: bool = False,
1032
        partial_prefill_metadata: Optional[PartialPrefillMetadata] = None,
1033
    ) -> SchedulerPrefillOutputs:
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
        """Schedule sequence groups that are in prefill stage.

        Note that the current scheduler treats PREEMPTED_FOR_RECOMPUTE
        as a new prefill (that starts from beginning -> most recently generated
        tokens).

        It schedules waiting requests as long as it fits `budget` and
        curr_loras <= max_lora from the scheduling config. The input arguments
        `budget` and `curr_loras` are updated based on scheduled seq_groups.

        Args:
            budget: The scheduling budget. The argument is in-place updated
                when any requests are scheduled.
            curr_loras: Currently batched lora request ids. The argument is
                in-place updated when any requests are scheduled.
1049
1050
1051
1052
            enable_chunking: If True, seq group can be chunked and only a
                chunked number of tokens are scheduled  if
                `budget.num_batched_tokens` has not enough capacity to schedule
                all tokens.
1053
1054
            partial_prefill_metadata: information about the partial prefills
                that are currently running
1055
1056

        Returns:
1057
            SchedulerPrefillOutputs.
1058
        """
1059
1060
1061
1062
1063
1064
1065
1066
        if budget.remaining_token_budget() == 0:
            # Do nothing: Can't add any more prefill anyway
            return SchedulerPrefillOutputs(
                seq_groups=[],
                ignored_seq_groups=[],
                num_lookahead_slots=self._get_num_lookahead_slots(
                    is_prefill=True, enable_chunking=enable_chunking),
            )
1067
        ignored_seq_groups: List[SequenceGroup] = []
1068
        seq_groups: List[ScheduledSequenceGroup] = []
1069
        using_prompt_embeds: bool = False
1070
1071

        waiting_queue = self.waiting
1072

1073
        leftover_waiting_sequences: Deque[SequenceGroup] = deque()
1074
1075
1076
1077
1078
1079
1080
        while self._passed_delay(time.time()) and waiting_queue:
            seq_group = waiting_queue[0]

            waiting_seqs = seq_group.get_seqs(status=SequenceStatus.WAITING)
            assert len(waiting_seqs) == 1, (
                "Waiting sequence group should have only one prompt "
                "sequence.")
1081
1082
1083
1084
1085
            if (partial_prefill_metadata is not None
                    and not partial_prefill_metadata.can_schedule(seq_group)):
                leftover_waiting_sequences.appendleft(seq_group)
                waiting_queue.popleft()
                continue
1086
1087
            num_new_tokens_uncached, num_new_tokens_cached = (
                self._get_num_new_uncached_and_cached_tokens(
1088
1089
1090
1091
1092
1093
                    seq_group,
                    SequenceStatus.WAITING,
                    enable_chunking,
                    budget,
                    partial_prefill_metadata=partial_prefill_metadata,
                ))
1094
1095
            num_new_tokens = num_new_tokens_uncached + num_new_tokens_cached

1096
1097
1098
1099
            if not enable_chunking:
                num_prompt_tokens = waiting_seqs[0].get_len()
                assert num_new_tokens == num_prompt_tokens

1100
1101
            prompt_limit = self._get_prompt_limit(seq_group)
            if num_new_tokens > prompt_limit:
1102
                logger.warning(
1103
                    "Input prompt (%d tokens) is too long"
1104
1105
1106
1107
                    " and exceeds limit of %d",
                    num_new_tokens,
                    prompt_limit,
                )
1108
1109
                for seq in waiting_seqs:
                    seq.status = SequenceStatus.FINISHED_IGNORED
1110
1111
                self.remove_seq_from_computed_blocks_tracker(
                    seq_group, SequenceStatus.FINISHED_IGNORED)
1112
1113
1114
1115
                ignored_seq_groups.append(seq_group)
                waiting_queue.popleft()
                continue

1116
1117
            num_lookahead_slots: int = 0

1118
            # If the sequence group cannot be allocated, stop.
1119
1120
            can_allocate = self.block_manager.can_allocate(
                seq_group, num_lookahead_slots=num_lookahead_slots)
1121
            if can_allocate == AllocStatus.LATER:
1122
1123
                self.remove_seq_from_computed_blocks_tracker(
                    seq_group, SequenceStatus.WAITING)
1124
1125
1126
                break
            elif can_allocate == AllocStatus.NEVER:
                logger.warning(
1127
1128
                    "Input prompt (%d tokens) + lookahead slots (%d) is "
                    "too long and exceeds the capacity of block_manager",
1129
1130
1131
                    num_new_tokens,
                    num_lookahead_slots,
                )
1132
1133
                for seq in waiting_seqs:
                    seq.status = SequenceStatus.FINISHED_IGNORED
1134
1135
                self.remove_seq_from_computed_blocks_tracker(
                    seq_group, SequenceStatus.FINISHED_IGNORED)
1136
1137
1138
1139
                ignored_seq_groups.append(seq_group)
                waiting_queue.popleft()
                continue

1140
1141
1142
1143
1144
            # We cannot mix sequence groups that use prompt embeds and
            # those that do not.
            if len(seq_groups) == 0:
                using_prompt_embeds = seq_group.uses_prompt_embeds()
            if using_prompt_embeds != seq_group.uses_prompt_embeds():
1145
1146
                self.remove_seq_from_computed_blocks_tracker(
                    seq_group, SequenceStatus.WAITING)
1147
1148
1149
1150
                leftover_waiting_sequences.appendleft(seq_group)
                waiting_queue.popleft()
                continue

1151
1152
1153
            lora_int_id = 0
            if self.lora_enabled:
                lora_int_id = seq_group.lora_int_id
1154
1155
                assert curr_loras is not None
                assert self.lora_config is not None
1156
1157
1158
1159
1160
                if (self.lora_enabled and lora_int_id > 0
                        and lora_int_id not in curr_loras
                        and len(curr_loras) >= self.lora_config.max_loras):
                    # We don't have a space for another LoRA, so
                    # we ignore this request for now.
1161
1162
                    self.remove_seq_from_computed_blocks_tracker(
                        seq_group, SequenceStatus.WAITING)
1163
1164
1165
1166
                    leftover_waiting_sequences.appendleft(seq_group)
                    waiting_queue.popleft()
                    continue

1167
1168
            if (budget.num_batched_tokens
                    >= self.scheduler_config.max_num_batched_tokens):
1169
1170
1171
                # We've reached the budget limit - since there might be
                # continuous prefills in the running queue, we should break
                # to avoid scheduling any new prefills.
1172
1173
                self.remove_seq_from_computed_blocks_tracker(
                    seq_group, SequenceStatus.WAITING)
1174
1175
                break

1176
            num_new_seqs = seq_group.get_max_num_running_seqs()
1177
1178
1179
1180
            if num_new_tokens_uncached == 0 or not budget.can_schedule(
                    num_new_tokens=num_new_tokens_uncached,
                    num_new_seqs=num_new_seqs,
            ):
1181
1182
                self.remove_seq_from_computed_blocks_tracker(
                    seq_group, SequenceStatus.WAITING)
1183
1184
1185
1186
1187
1188
                break

            # Can schedule this request.
            if curr_loras is not None and lora_int_id > 0:
                curr_loras.add(lora_int_id)
            waiting_queue.popleft()
1189
            self._allocate_and_set_running(seq_group)
1190

1191
1192
1193
1194
            if partial_prefill_metadata is not None:
                partial_prefill_metadata.maybe_increment_partial_prefills(
                    seq_group)

1195
1196
            seq_groups.append(
                ScheduledSequenceGroup(seq_group=seq_group,
1197
                                       token_chunk_size=num_new_tokens))
1198
1199
1200
1201
1202
            budget.add_num_batched_tokens(
                seq_group.request_id,
                num_batched_tokens=num_new_tokens_uncached,
                num_cached_tokens=num_new_tokens_cached,
            )
1203
            budget.add_num_seqs(seq_group.request_id, num_new_seqs)
1204
1205
1206
1207
1208
1209

        # Queue requests that couldn't be scheduled.
        waiting_queue.extendleft(leftover_waiting_sequences)
        if len(seq_groups) > 0:
            self.prev_prompt = True

1210
        return SchedulerPrefillOutputs(
1211
1212
            seq_groups=seq_groups,
            ignored_seq_groups=ignored_seq_groups,
1213
            num_lookahead_slots=self._get_num_lookahead_slots(
1214
1215
                is_prefill=True, enable_chunking=enable_chunking),
        )
1216

1217
1218
    def _schedule_default(self) -> SchedulerOutputs:
        """Schedule queued requests.
1219

1220
        The current policy is designed to optimize the throughput. First,
1221
1222
1223
1224
1225
1226
1227
1228
1229
        it batches as many prefill requests as possible. And it schedules
        decodes. If there's a pressure on GPU memory, decode requests can
        be swapped or preempted.
        """
        # Include running requests to the budget.
        budget = SchedulingBudget(
            token_budget=self.scheduler_config.max_num_batched_tokens,
            max_num_seqs=self.scheduler_config.max_num_seqs,
        )
1230
1231
1232
1233
1234
        # Make sure we include num running seqs before scheduling prefill,
        # so that we don't schedule beyond max_num_seqs for prefill.
        for seq_group in self.running:
            budget.add_num_seqs(seq_group.request_id,
                                seq_group.get_max_num_running_seqs())
1235
        curr_loras = (set(
1236
            seq_group.lora_int_id for seq_group in self.running
1237
            if seq_group.lora_int_id > 0) if self.lora_enabled else None)
1238

1239
1240
1241
        prefills = SchedulerPrefillOutputs.create_empty()
        running_scheduled = SchedulerRunningOutputs.create_empty()
        swapped_in = SchedulerSwappedInOutputs.create_empty()
1242
1243
1244

        # If any requests are swapped, prioritized swapped requests.
        if not self.swapped:
1245
1246
1247
            prefills = self._schedule_prefills(budget,
                                               curr_loras,
                                               enable_chunking=False)
1248

1249
1250
1251
1252
        if len(prefills.seq_groups
               ) == 0 and self.scheduler_config.policy == "priority":
            self._schedule_priority_preemption(budget)

1253
        # Don't schedule decodes if prefills are scheduled.
1254
1255
        # NOTE: If `_schedule_prefills` doesn't enable chunking, self.running
        # only contains decode requests, not chunked prefills.
1256
        if len(prefills.seq_groups) == 0:
1257
1258
1259
            running_scheduled = self._schedule_running(budget,
                                                       curr_loras,
                                                       enable_chunking=False)
1260

1261
1262
            # If any sequence group is preempted, do not swap in any sequence
            # group. because it means there's no slot for new running requests.
1263
1264
1265
1266
            if (len(running_scheduled.preempted) +
                    len(running_scheduled.swapped_out) == 0):
                swapped_in = \
                    self._schedule_swapped(budget, curr_loras)
1267

1268
1269
        assert (budget.num_batched_tokens
                <= self.scheduler_config.max_num_batched_tokens)
1270
1271
1272
        assert budget.num_curr_seqs <= self.scheduler_config.max_num_seqs

        # Update waiting requests.
1273
        self.waiting.extendleft(running_scheduled.preempted)
1274
        # Update new running requests.
1275
1276
1277
1278
1279
1280
1281
1282
1283
        if len(prefills.seq_groups) > 0:
            self.running.extend([s.seq_group for s in prefills.seq_groups])

        self.running.extend(running_scheduled.decode_seq_groups_list)

        if len(swapped_in.decode_seq_groups) > 0:
            self.running.extend(
                [s.seq_group for s in swapped_in.decode_seq_groups])

1284
        # Update swapped requests.
1285
        self.swapped.extend(running_scheduled.swapped_out)
1286
1287
        preempted = len(running_scheduled.preempted) + len(
            running_scheduled.swapped_out)
1288

1289
1290
1291
1292
        # There should be no prefill from running queue because this policy
        # doesn't allow chunked prefills.
        assert len(running_scheduled.prefill_seq_groups) == 0
        assert len(swapped_in.prefill_seq_groups) == 0
1293
1294
1295

        # Merge lists
        num_prefill_groups = len(prefills.seq_groups)
1296
        ignored_seq_groups_for_embeds = list[SequenceGroup]()
1297
1298
1299
        if num_prefill_groups > 0:
            scheduled_seq_groups = prefills.seq_groups
            scheduled_seq_groups.extend(running_scheduled.decode_seq_groups)
1300
            ignored_seq_groups_for_embeds.clear()
1301
1302
        else:
            scheduled_seq_groups = running_scheduled.decode_seq_groups
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
            if len(scheduled_seq_groups) > 0:
                using_prompt_embeds = scheduled_seq_groups[
                    0].seq_group.uses_prompt_embeds()
                ignored_seq_groups_for_embeds.clear()
                indices_ignored = list[int]()
                for i, schedule_seq_group in enumerate(scheduled_seq_groups):
                    if using_prompt_embeds !=\
                        schedule_seq_group.seq_group.uses_prompt_embeds():
                        ignored_seq_groups_for_embeds.append(
                            schedule_seq_group.seq_group)
                        indices_ignored.append(i)
                if len(ignored_seq_groups_for_embeds) > 0:
                    scheduled_seq_groups = [
                        group for i, group in enumerate(scheduled_seq_groups)
                        if i not in indices_ignored
                    ]
            else:
                ignored_seq_groups_for_embeds.clear()

1322
1323
1324
1325
1326
1327
        scheduled_seq_groups.extend(swapped_in.decode_seq_groups)

        blocks_to_copy = running_scheduled.blocks_to_copy
        blocks_to_copy.extend(swapped_in.blocks_to_copy)

        ignored_seq_groups = prefills.ignored_seq_groups
1328
        ignored_seq_groups.extend(ignored_seq_groups_for_embeds)
1329
1330
        ignored_seq_groups.extend(swapped_in.infeasible_seq_groups)

1331
        return SchedulerOutputs(
1332
1333
            scheduled_seq_groups=scheduled_seq_groups,
            num_prefill_groups=num_prefill_groups,
1334
1335
            num_batched_tokens=budget.num_batched_tokens +
            budget.num_cached_tokens,
1336
            blocks_to_swap_in=swapped_in.blocks_to_swap_in,
1337
            blocks_to_swap_out=running_scheduled.blocks_to_swap_out,
1338
1339
            blocks_to_copy=blocks_to_copy,
            ignored_seq_groups=ignored_seq_groups,
1340
            num_lookahead_slots=running_scheduled.num_lookahead_slots,
1341
            running_queue_size=len(self.running),
1342
            preempted=preempted,
1343
1344
        )

1345
    def _schedule_chunked_prefill(self) -> SchedulerOutputs:
1346
        """Schedule queued requests.
1347

1348
1349
1350
1351
1352
1353
1354
1355
        Chunked prefill allows to chunk prefill requests, batch them together
        with decode requests. This policy 1. schedule as many decoding requests
        as possible. 2. schedule chunked prefill requests that are not
        finished. 3. schedule swapped request. 4. schedule new prefill
        requests.

        The policy can sustain the high GPU utilization because it can put
        prefill and decodes requests to the same batch, while it improves
1356
        inter token latency because decodes requests don't need to be blocked
1357
1358
1359
1360
1361
1362
        by prefill requests.
        """
        budget = SchedulingBudget(
            token_budget=self.scheduler_config.max_num_batched_tokens,
            max_num_seqs=self.scheduler_config.max_num_seqs,
        )
1363
        curr_loras: Set[int] = set()
1364

1365
1366
        prefills = SchedulerPrefillOutputs.create_empty()
        swapped_in = SchedulerSwappedInOutputs.create_empty()
1367

1368
1369
1370
1371
1372
1373
1374
        # Create partial prefill metadata
        partial_prefill_metadata = PartialPrefillMetadata.from_queues(
            running=self.running,
            waiting=self.waiting,
            scheduler_config=self.scheduler_config,
        )

1375
        # Decoding should be always scheduled first by fcfs.
1376
1377
1378
1379
1380
1381
        running_scheduled = self._schedule_running(
            budget,
            curr_loras,
            enable_chunking=True,
            partial_prefill_metadata=partial_prefill_metadata,
        )
1382
1383
1384
1385
1386

        # Schedule swapped out requests.
        # If preemption happens, it means we don't have space for swap-in.
        if len(running_scheduled.preempted) + len(
                running_scheduled.swapped_out) == 0:
1387
            swapped_in = self._schedule_swapped(budget, curr_loras)
1388

1389
1390
1391
1392
1393
1394
        prefills = self._schedule_prefills(
            budget,
            curr_loras,
            enable_chunking=True,
            partial_prefill_metadata=partial_prefill_metadata,
        )
1395

1396
1397
        assert (budget.num_batched_tokens
                <= self.scheduler_config.max_num_batched_tokens)
1398
1399
1400
1401
        assert budget.num_curr_seqs <= self.scheduler_config.max_num_seqs

        # Update waiting requests.
        self.waiting.extendleft(running_scheduled.preempted)
1402

1403
        # Update new running requests.
1404
1405
1406
        # By default, vLLM scheduler prioritizes prefills.
        # Once chunked prefill is enabled,
        # the policy is changed to prioritize decode requests.
1407
1408
1409
1410
        self.running.extend(
            [s.seq_group for s in swapped_in.decode_seq_groups])
        self.running.extend(
            [s.seq_group for s in swapped_in.prefill_seq_groups])
1411
1412
        self.running.extend(
            [s.seq_group for s in running_scheduled.decode_seq_groups])
1413
1414
1415
1416
1417
1418
        # Because multiple prefills may be running concurrently, we need to
        # make sure that prefills which are scheduled to finish are listed
        # before those that won't. This is so that on the next scheduling
        # iteration when they have transitioned to the decode stage, they are
        # properly prioritized over sequences that are still in the prefill
        # stage.
1419
        self.running.extend(
1420
1421
            self._order_finishing_prefills_first(
                running_scheduled.prefill_seq_groups))
1422
1423
        self.running.extend([s.seq_group for s in prefills.seq_groups])

1424
1425
        # Update swapped requests.
        self.swapped.extend(running_scheduled.swapped_out)
1426
        # Put prefills first due to Attention backend ordering assumption.
1427
1428
1429
1430
1431
1432
1433
1434
        scheduled_seq_groups = (prefills.seq_groups +
                                running_scheduled.prefill_seq_groups +
                                swapped_in.prefill_seq_groups +
                                running_scheduled.decode_seq_groups +
                                swapped_in.decode_seq_groups)
        num_prefill_groups = (len(prefills.seq_groups) +
                              len(swapped_in.prefill_seq_groups) +
                              len(running_scheduled.prefill_seq_groups))
1435
        return SchedulerOutputs(
1436
1437
            scheduled_seq_groups=scheduled_seq_groups,
            num_prefill_groups=num_prefill_groups,
1438
1439
            num_batched_tokens=budget.num_batched_tokens +
            budget.num_cached_tokens,
1440
1441
            blocks_to_swap_in=swapped_in.blocks_to_swap_in,
            blocks_to_swap_out=running_scheduled.blocks_to_swap_out,
1442
1443
            blocks_to_copy=running_scheduled.blocks_to_copy +
            swapped_in.blocks_to_copy,
1444
1445
            ignored_seq_groups=prefills.ignored_seq_groups +
            swapped_in.infeasible_seq_groups,
1446
            num_lookahead_slots=0,
1447
            running_queue_size=len(self.running),
1448
1449
            preempted=(len(running_scheduled.preempted) +
                       len(running_scheduled.swapped_out)),
1450
        )
Woosuk Kwon's avatar
Woosuk Kwon committed
1451

1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
    def _order_finishing_prefills_first(
        self, scheduled_prefill_seqs: List[ScheduledSequenceGroup]
    ) -> List[SequenceGroup]:
        """Returns a list of prefilling SequenceGroups where sequences that are
        scheduled to finish prefilling are listed first"""
        finishing = [
            s.seq_group for s in scheduled_prefill_seqs
            if s.seq_group.get_num_uncomputed_tokens() == s.token_chunk_size
        ]
        not_finishing = [
            s.seq_group for s in scheduled_prefill_seqs
            if s.seq_group.get_num_uncomputed_tokens() != s.token_chunk_size
        ]
        return finishing + not_finishing

1467
1468
1469
1470
1471
1472
1473
    def _schedule(self) -> SchedulerOutputs:
        """Schedule queued requests."""
        if self.scheduler_config.chunked_prefill_enabled:
            return self._schedule_chunked_prefill()
        else:
            return self._schedule_default()

1474
1475
    def _can_append_slots(self, seq_group: SequenceGroup,
                          enable_chunking: bool) -> bool:
1476
1477
1478
        """Determine whether or not we have enough space in the KV cache to
        continue generation of the sequence group.
        """
1479
1480
1481
1482
1483
1484
1485
        # It is True only for testing case to trigger artificial preemption.
        if (self.enable_artificial_preemption
                and random.uniform(0, 1) < ARTIFICIAL_PREEMPTION_PROB
                and self.artificial_preempt_cnt > 0):
            self.artificial_preempt_cnt -= 1
            return False

1486
1487
1488
1489
        is_prefill = seq_group.is_prefill()
        num_lookahead_slots = self._get_num_lookahead_slots(
            is_prefill, enable_chunking)

1490
        return self.block_manager.can_append_slots(
1491
            seq_group=seq_group, num_lookahead_slots=num_lookahead_slots)
1492

1493
    def _allow_async_output_proc(self, seq_group: SequenceGroup) -> bool:
1494
1495
1496
        # async_output_proc is allowed only when we have a single sequence
        # in the sequence group
        no_single_seq = seq_group.sampling_params is None or (
1497
            seq_group.sampling_params.n == 1)
1498
        return no_single_seq
1499
1500
1501
1502

    def schedule(
            self
    ) -> Tuple[List[SequenceGroupMetadata], SchedulerOutputs, bool]:
1503
1504
1505
        # Schedule sequence groups.
        # This function call changes the internal states of the scheduler
        # such as self.running, self.swapped, and self.waiting.
1506
        scheduler_start_time = time.perf_counter()
1507

1508
        scheduler_outputs: SchedulerOutputs = self._schedule()
1509
        now = time.time()
1510

1511
1512
1513
        if not self.cache_config.enable_prefix_caching:
            common_computed_block_nums = []

1514
        allow_async_output_proc: bool = self.use_async_output_proc
1515

1516
        # Create input data structures.
1517
        seq_group_metadata_list: List[SequenceGroupMetadata] = []
1518
1519
        for i, scheduled_seq_group in enumerate(
                scheduler_outputs.scheduled_seq_groups):
1520
1521
            seq_group = scheduled_seq_group.seq_group
            token_chunk_size = scheduled_seq_group.token_chunk_size
1522
1523
            seq_group.maybe_set_first_scheduled_time(now)

1524
1525
1526
1527
1528
            seq_group_metadata = self._seq_group_metadata_cache[
                self.cache_id].get_object()
            seq_group_metadata.seq_data.clear()
            seq_group_metadata.block_tables.clear()

1529
            # seq_id -> SequenceData
1530
            seq_data: Dict[int, SequenceData] = {}
1531
            # seq_id -> physical block numbers
1532
            block_tables: Dict[int, List[int]] = {}
1533

1534
1535
            if seq_group.is_encoder_decoder():
                # Encoder associated with SequenceGroup
1536
1537
1538
                encoder_seq = seq_group.get_encoder_seq()
                assert encoder_seq is not None
                encoder_seq_data = encoder_seq.data
1539
1540
1541
1542
1543
1544
1545
1546
                # Block table for cross-attention
                # Also managed at SequenceGroup level
                cross_block_table = self.block_manager.get_cross_block_table(
                    seq_group)
            else:
                encoder_seq_data = None
                cross_block_table = None

1547
            for seq in seq_group.get_seqs(status=SequenceStatus.RUNNING):
1548
                seq_id = seq.seq_id
1549
                seq_data[seq_id] = seq.data
1550
                block_tables[seq_id] = self.block_manager.get_block_table(seq)
1551
                self.block_manager.access_all_blocks_in_seq(seq, now)
1552

1553
1554
1555
1556
            if self.cache_config.enable_prefix_caching:
                common_computed_block_nums = (
                    self.block_manager.get_common_computed_block_ids(
                        seq_group.get_seqs(status=SequenceStatus.RUNNING)))
1557

1558
            do_sample = True
1559
1560
1561
1562
1563
            is_prompt = seq_group.is_prefill()
            # We should send the metadata to workers when the first prefill
            # is sent. Subsequent requests could be chunked prefill or decode.
            is_first_prefill = False
            if is_prompt:
1564
1565
1566
                seqs = seq_group.get_seqs()
                # Prefill has only 1 sequence.
                assert len(seqs) == 1
1567
1568
                num_computed_tokens = seqs[0].data.get_num_computed_tokens()
                is_first_prefill = num_computed_tokens == 0
1569
1570
1571
1572
1573
                # In the next iteration, all prompt tokens are not computed.
                # It means the prefill is chunked, and we don't need sampling.
                # NOTE: We use get_len instead of get_prompt_len because when
                # a sequence is preempted, prefill includes previous generated
                # output tokens.
1574
1575
                if (token_chunk_size + num_computed_tokens
                        < seqs[0].data.get_len()):
1576
1577
                    do_sample = False

1578
1579
            # It assumes the scheduled_seq_groups is ordered by
            # prefill < decoding.
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
            if is_first_prefill or not self.scheduler_config.send_delta_data:
                seq_group_metadata = SequenceGroupMetadata(
                    request_id=seq_group.request_id,
                    is_prompt=is_prompt,
                    seq_data=seq_data,
                    sampling_params=seq_group.sampling_params,
                    block_tables=block_tables,
                    do_sample=do_sample,
                    pooling_params=seq_group.pooling_params,
                    token_chunk_size=token_chunk_size,
                    lora_request=seq_group.lora_request,
                    computed_block_nums=common_computed_block_nums,
                    encoder_seq_data=encoder_seq_data,
                    cross_block_table=cross_block_table,
                    state=seq_group.state,
                    # `multi_modal_data` will only be present for the 1st comm
                    # between engine and worker.
                    # the subsequent comms can still use delta, but
                    # `multi_modal_data` will be None.
1599
1600
1601
1602
1603
1604
                    multi_modal_data=(seq_group.multi_modal_data
                                      if scheduler_outputs.num_prefill_groups
                                      > 0 else None),
                    multi_modal_placeholders=(
                        seq_group.multi_modal_placeholders
                        if scheduler_outputs.num_prefill_groups > 0 else None),
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
                )
            else:
                # When SPMD mode is enabled, we only send delta data except for
                # the first request to reduce serialization cost.
                seq_data_delta = {}
                for id, data in seq_data.items():
                    seq_data_delta[id] = data.get_delta_and_reset()
                seq_group_metadata = SequenceGroupMetadataDelta(
                    seq_data_delta,
                    seq_group.request_id,
                    block_tables,
                    is_prompt,
                    do_sample=do_sample,
                    token_chunk_size=token_chunk_size,
                    computed_block_nums=common_computed_block_nums,
                )
1621
            seq_group_metadata_list.append(seq_group_metadata)
1622

1623
1624
1625
1626
            if allow_async_output_proc:
                allow_async_output_proc = self._allow_async_output_proc(
                    seq_group)

1627
1628
1629
1630
        # Now that the batch has been created, we can assume all blocks in the
        # batch will have been computed before the next scheduling invocation.
        # This is because the engine assumes that a failure in model execution
        # will crash the vLLM instance / will not retry.
1631
1632
        for scheduled_seq_group in scheduler_outputs.scheduled_seq_groups:
            self.block_manager.mark_blocks_as_computed(
1633
1634
                scheduled_seq_group.seq_group,
                scheduled_seq_group.token_chunk_size)
1635

1636
1637
        self._seq_group_metadata_cache[self.next_cache_id].reset()

1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
        scheduler_time = time.perf_counter() - scheduler_start_time
        # Add this to scheduler time to all the sequences that are currently
        # running. This will help estimate if the scheduler is a significant
        # component in the e2e latency.
        for seq_group in self.running:
            if seq_group is not None and seq_group.metrics is not None:
                if seq_group.metrics.scheduler_time is not None:
                    seq_group.metrics.scheduler_time += scheduler_time
                else:
                    seq_group.metrics.scheduler_time = scheduler_time

1649
1650
1651
1652
1653
1654
        # Move to next cache (if exists)
        self.cache_id = self.next_cache_id

        # Return results
        return (seq_group_metadata_list, scheduler_outputs,
                allow_async_output_proc)
1655

1656
1657
    def fork_seq(self, parent_seq: Sequence, child_seq: Sequence) -> None:
        self.block_manager.fork(parent_seq, child_seq)
Woosuk Kwon's avatar
Woosuk Kwon committed
1658

1659
    def free_seq(self, seq: Sequence) -> None:
1660
        """Free a sequence from a block table."""
1661
        self.block_manager.free(seq)
Woosuk Kwon's avatar
Woosuk Kwon committed
1662

1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
    def remove_seq_from_computed_blocks_tracker(
            self, seq_group: SequenceGroup,
            status: Optional[SequenceStatus]) -> None:
        seqs = seq_group.get_seqs(status=status)
        for seq in seqs:
            self._remove_seq_from_computed_blocks_tracker(seq)

    def _remove_seq_from_computed_blocks_tracker(self, seq: Sequence) -> None:
        """
        Free a sequence computed blocks tracker _seq_id_to_blocks_hashes
        and _seq_id_to_num_tokens_computed.
        """
        self.block_manager.remove_seq_from_computed_blocks_tracker(seq)

1677
1678
1679
1680
1681
1682
    def _free_finished_seqs(self, seq_group: SequenceGroup) -> None:
        """Free finished seqs in a sequence group."""
        for seq in seq_group.get_seqs():
            if seq.is_finished():
                self.free_seq(seq)

1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
    def _free_finished_seq_group(self, seq_group: SequenceGroup) -> None:
        if seq_group.is_finished():
            # Free cross-attention block table, if it exists
            self._free_seq_group_cross_attn_blocks(seq_group)

            # Add the finished requests to the finished requests list.
            # This list will be used to update the Mamba cache in the
            # next step.
            self._finished_requests_ids.append(seq_group.request_id)

        # Free finished seqs
        self._free_finished_seqs(seq_group)

1696
    def free_finished_seq_groups(self) -> None:
1697
1698
        remaining: Deque[SequenceGroup] = deque()
        for seq_group in self.running:
1699
1700
            self._free_finished_seq_group(seq_group)
            if not seq_group.is_finished():
1701
                remaining.append(seq_group)
1702

1703
        self.running = remaining
Woosuk Kwon's avatar
Woosuk Kwon committed
1704

1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
        # Handle async stopped sequence groups
        # (ones that reached max model len)
        if self._async_stopped:
            for seq_group in self._async_stopped:
                self._free_seq_group_cross_attn_blocks(seq_group)
                self._finished_requests_ids.append(seq_group.request_id)

                # Free finished seqs
                self._free_finished_seqs(seq_group)

            self._async_stopped.clear()

1717
    def _allocate_and_set_running(self, seq_group: SequenceGroup) -> None:
1718
        self.block_manager.allocate(seq_group)
1719
        for seq in seq_group.get_seqs(status=SequenceStatus.WAITING):
1720
1721
            seq.status = SequenceStatus.RUNNING

1722
1723
1724
1725
1726
1727
    def _append_slots(
        self,
        seq_group: SequenceGroup,
        blocks_to_copy: List[Tuple[int, int]],
        enable_chunking: bool = False,
    ) -> None:
1728
1729
1730
1731
1732
        """Appends new slots to the sequences in the given sequence group.

        Args:
            seq_group (SequenceGroup): The sequence group containing the
                sequences to append slots to.
1733
1734
1735
1736
1737
            blocks_to_copy (List[Tuple[int, int]]): A list of tuple of two
                ints, the first int is the source block index, and the second
                int is the destination block index. This list is updated with
                the new source and destination block indices for the appended
                slots.
1738
            enable_chunking (bool): True if chunked prefill is enabled.
1739
        """
1740
1741
1742
1743
1744
1745
        is_prefill: bool = seq_group.is_prefill()
        num_lookahead_slots: int = self._get_num_lookahead_slots(
            is_prefill, enable_chunking)

        seq_status: Optional[SequenceStatus] = SequenceStatus.RUNNING
        for seq in seq_group.get_seqs(status=seq_status):
1746
            cows = self.block_manager.append_slots(seq, num_lookahead_slots)
1747
1748
            if len(cows) > 0:
                blocks_to_copy.extend(cows)
1749

1750
1751
    def _preempt(self, seq_group: SequenceGroup,
                 blocks_to_swap_out: List[Tuple[int, int]]) -> PreemptionMode:
1752
1753
1754
        # If preemption mode is not specified, we determine the mode as follows:
        # We use recomputation by default since it incurs lower overhead than
        # swapping. However, when the sequence group has multiple sequences
1755
1756
        # (e.g., beam search), recomputation is not currently supported. In
        # such a case, we use swapping instead.
1757
1758
1759
1760
1761
1762
        # FIXME(woosuk): This makes our scheduling policy a bit bizarre.
        # As swapped sequences are prioritized over waiting sequences,
        # sequence groups with multiple sequences are implicitly prioritized
        # over sequence groups with a single sequence.
        # TODO(woosuk): Support recomputation for sequence groups with multiple
        # sequences. This may require a more sophisticated CUDA kernel.
1763
        if self.user_specified_preemption_mode is None:
1764
            if seq_group.get_max_num_running_seqs() == 1:
1765
1766
1767
                preemption_mode = PreemptionMode.RECOMPUTE
            else:
                preemption_mode = PreemptionMode.SWAP
1768

1769
1770
1771
1772
1773
        elif self.user_specified_preemption_mode == "swap":
            preemption_mode = PreemptionMode.SWAP
        else:
            preemption_mode = PreemptionMode.RECOMPUTE

1774
1775
1776
1777
1778
1779
        if self.num_cumulative_preemption % 50 == 0:
            logger.warning(
                "Sequence group %s is preempted by %s mode because there is "
                "not enough KV cache space. This can affect the end-to-end "
                "performance. Increase gpu_memory_utilization or "
                "tensor_parallel_size to provide more KV cache memory. "
1780
1781
1782
1783
1784
                "total_num_cumulative_preemption=%d",
                seq_group.request_id,
                preemption_mode,
                self.num_cumulative_preemption + 1,
            )
1785
1786
        self.num_cumulative_preemption += 1

1787
1788
1789
1790
1791
        if preemption_mode == PreemptionMode.RECOMPUTE:
            self._preempt_by_recompute(seq_group)
        elif preemption_mode == PreemptionMode.SWAP:
            self._preempt_by_swap(seq_group, blocks_to_swap_out)
        else:
1792
            raise AssertionError("Invalid preemption mode.")
1793
        return preemption_mode
1794
1795
1796
1797
1798
1799
1800
1801
1802

    def _preempt_by_recompute(
        self,
        seq_group: SequenceGroup,
    ) -> None:
        seqs = seq_group.get_seqs(status=SequenceStatus.RUNNING)
        assert len(seqs) == 1
        for seq in seqs:
            seq.status = SequenceStatus.WAITING
1803
1804
            self.free_seq(seq)
            seq.reset_state_for_recompute()
1805
        self._free_seq_group_cross_attn_blocks(seq_group)
1806
1807
1808
1809

    def _preempt_by_swap(
        self,
        seq_group: SequenceGroup,
1810
        blocks_to_swap_out: List[Tuple[int, int]],
1811
1812
1813
1814
1815
1816
    ) -> None:
        self._swap_out(seq_group, blocks_to_swap_out)

    def _swap_in(
        self,
        seq_group: SequenceGroup,
1817
        blocks_to_swap_in: List[Tuple[int, int]],
1818
1819
    ) -> None:
        mapping = self.block_manager.swap_in(seq_group)
1820
        blocks_to_swap_in.extend(mapping)
1821
1822
1823
1824
1825
1826
        for seq in seq_group.get_seqs(status=SequenceStatus.SWAPPED):
            seq.status = SequenceStatus.RUNNING

    def _swap_out(
        self,
        seq_group: SequenceGroup,
1827
        blocks_to_swap_out: List[Tuple[int, int]],
1828
    ) -> None:
1829
1830
1831
1832
1833
1834
        if not self.block_manager.can_swap_out(seq_group):
            # FIXME(woosuk): Abort the sequence group instead of aborting the
            # entire engine.
            raise RuntimeError(
                "Aborted due to the lack of CPU swap space. Please increase "
                "the swap space to avoid this error.")
1835
        mapping = self.block_manager.swap_out(seq_group)
1836
        blocks_to_swap_out.extend(mapping)
1837
1838
        for seq in seq_group.get_seqs(status=SequenceStatus.RUNNING):
            seq.status = SequenceStatus.SWAPPED
1839

1840
1841
1842
1843
1844
1845
1846
1847
    def _passed_delay(self, now: float) -> bool:
        if self.prev_prompt:
            self.last_prompt_latency = now - self.prev_time
        self.prev_time, self.prev_prompt = now, False
        # Delay scheduling prompts to let waiting queue fill up
        if self.scheduler_config.delay_factor > 0 and self.waiting:
            earliest_arrival_time = min(
                [e.metrics.arrival_time for e in self.waiting])
1848
1849
1850
            passed_delay = ((now - earliest_arrival_time)
                            > (self.scheduler_config.delay_factor *
                               self.last_prompt_latency) or not self.running)
1851
1852
1853
        else:
            passed_delay = True
        return passed_delay
1854

1855
1856
    def _get_num_lookahead_slots(self, is_prefill: bool,
                                 enable_chunking: bool) -> int:
1857
1858
1859
1860
        """The number of slots to allocate per sequence per step, beyond known
        token ids. Speculative decoding uses these slots to store KV activations
        of tokens which may or may not be accepted.
        """
1861
        return 0
1862

1863
1864
1865
1866
1867
1868
    def _get_num_new_uncached_and_cached_tokens(
        self,
        seq_group: SequenceGroup,
        status: SequenceStatus,
        enable_chunking: bool,
        budget: SchedulingBudget,
1869
        partial_prefill_metadata: Optional[PartialPrefillMetadata] = None,
1870
1871
1872
1873
    ) -> Tuple[int, int]:
        """
        Returns the number of new uncached and cached tokens to schedule for a
        given sequence group that's in a given `status`.
1874
1875
1876
1877
1878

        The API could chunk the number of tokens to compute based on `budget`
        if `enable_chunking` is True. If a sequence group has multiple
        sequences (e.g., running beam search), it means it is in decoding
        phase, so chunking doesn't happen.
1879

1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
        Returns (0, 0) if the new token cannot be computed due to token budget.

        The cached tokens's blocks are already computed, and the attention
        backend will reuse the cached blocks rather than recomputing them. So
        the scheduler could schedule these cached tokens "for free".

        Args:
            seq_group: The sequence group to get the number of new tokens to
                schedule.
            status: The status of the sequences to get the number of new tokens
                to schedule.
            enable_chunking: Whether to chunk the number of tokens to compute.
            budget: The budget to chunk the number of tokens to compute.
1893
1894
            partial_prefill_metadata: information about the partial prefills
                that are currently running
1895
1896
1897
1898
1899
1900


        Returns:
            A tuple of two ints. The first int is the number of new uncached
            tokens to schedule. The second int is the number of cached tokens.
            If no more new tokens can be scheduled, returns (0, 0).
1901
        """
1902
1903
1904
        num_cached_new_tokens = 0
        num_uncached_new_tokens = 0

1905
        seqs = seq_group.get_seqs(status=status)
1906
1907
        # Compute the number of new uncached and cached tokens for
        # each sequence.
1908
        for seq in seqs:
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
            if not seq.is_prefill():
                # Decode sequences should always just have 1 uncached token
                # TODO(rickyx): Actually is this still correct for multi-step?
                num_uncached_new_tokens += 1
                continue

            num_computed_tokens_seq = seq.get_num_computed_tokens()
            all_num_new_tokens_seq = seq.get_len() - num_computed_tokens_seq
            if not self.cache_config.enable_prefix_caching:
                # If prefix caching is not enabled, all new tokens are uncached.
                num_uncached_new_tokens += all_num_new_tokens_seq
                continue

            # NOTE: the cache token might be currently in a block that's in an
            # evictor meaning that it's not yet allocated. However, we don't
            # exclude such tokens in the cache count because it will be
            # guaranteed to be allocated later if the sequence can be allocated.
            num_cached_tokens_seq = self.block_manager.get_num_cached_tokens(
                seq)

            # Sanity check.
            if num_cached_tokens_seq < num_computed_tokens_seq:
                # This should only happen with chunked prefill, and
                # the seq is still in prefill. The `num_cached_tokens_seq`
                # is the value we calculated on scheduling the first prefill.
                # For subsequent continuous prefill steps, we cached the
                # number of cache tokens for the sequence so the cached token
                # count could be less than the number of computed tokens.
                # See comments on `ComputedBlocksTracker` for more details.
                assert (
                    seq.is_prefill() and seq.status == SequenceStatus.RUNNING
                    and self.scheduler_config.chunked_prefill_enabled
                ), ("Number of cached tokens should not be less than the "
                    "number of computed tokens for a sequence that's still "
                    f"in prefill. But there are {num_cached_tokens_seq} cached "
                    f"tokens and {num_computed_tokens_seq} computed tokens "
                    f"for sequence {seq.seq_id}.")

            num_cached_new_tokens_seq = max(
                0, num_cached_tokens_seq - num_computed_tokens_seq)
            num_uncached_new_tokens_seq = (all_num_new_tokens_seq -
                                           num_cached_new_tokens_seq)

            num_uncached_new_tokens += num_uncached_new_tokens_seq
            num_cached_new_tokens += num_cached_new_tokens_seq

        if num_uncached_new_tokens == 0 and num_cached_new_tokens > 0:
            # For a fully cached hit sequence, we actually need to recompute the
            # last token. So we need at least 1 uncached token to schedule.
            # See ModelRunner._compute_for_prefix_cache_hit for more details.
            num_uncached_new_tokens = 1
            num_cached_new_tokens -= 1

1962
        if enable_chunking and len(seqs) == 1:
1963
1964
1965
1966
1967
1968
1969
1970
1971
            # Chunk if a running request cannot fit in the given budget.
            # If number of seq > 1, it means it is doing beam search
            # in a decode phase. Do not chunk.
            num_uncached_new_tokens = self._chunk_new_tokens_to_schedule(
                self.scheduler_config,
                self.cache_config,
                budget,
                self._get_prompt_limit(seq_group),
                num_uncached_new_tokens,
1972
1973
                self.partial_prefill_budget_lookup_list,
                partial_prefill_metadata,
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
            )

        return num_uncached_new_tokens, num_cached_new_tokens

    @staticmethod
    def _chunk_new_tokens_to_schedule(
        scheduler_config: SchedulerConfig,
        cache_config: CacheConfig,
        budget: SchedulingBudget,
        prompt_limit: int,
        num_new_tokens: int,
1985
1986
        partial_prefill_budget_lookup_list: List[int],
        partial_prefill_metadata: Optional[PartialPrefillMetadata] = None,
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
    ) -> int:
        """
        Chunks the number of new tokens to schedule based on the budget when
        chunked prefill is enabled.

        Args:
            scheduler_config: The scheduler config.
            cache_config: The cache config.
            budget: The budget to chunk the number of tokens to compute.
            prompt_limit: The maximum number of tokens allowed in a prompt.
            num_new_tokens: The number of new tokens to schedule.

        Returns:
            The number of new tokens to schedule after chunking.
        """
        remaining_token_budget = budget.remaining_token_budget()

2004
2005
2006
2007
2008
        # Get the number of tokens to allocate to this prefill slot
        prefill_slot_budget = (
            remaining_token_budget if partial_prefill_metadata is None else
            partial_prefill_budget_lookup_list[
                partial_prefill_metadata.schedulable_prefills])
2009

2010
2011
2012
2013
        if cache_config.enable_prefix_caching:
            # When prefix caching is enabled and we're partially prefilling
            # a sequence, we always allocate a number of new tokens that is
            # divisible by the block size to avoid partial block matching.
2014
            block_size = cache_config.block_size
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
            # Don't exceed either the total budget or slot budget.
            # Take min of those and get the next lowest multiple of the
            # block size:
            remaining_token_budget = (
                min(remaining_token_budget, prefill_slot_budget) //
                block_size) * block_size
            # NB: In the case where num_new_tokens < budget, we are
            # finishing prefill for this sequence, so we do not need to
            # allocate a full block.

        num_new_tokens = min(num_new_tokens, remaining_token_budget,
                             prefill_slot_budget)
2027

2028
        return num_new_tokens