ChunkLlama

vLLM is a high-throughput library designed for LLM inference and serving. It achieves high performance through several core technologies:

Performance Optimizations

• PagedAttention: Efficient management of attention key and value (KV) memory.
• Continuous Batching: Efficiently handles incoming requests by batching them continuously.
• Fast Execution: Utilizes CUDA/HIP graphs for accelerated model execution.
• Quantization Support: Supports GPTQ, AWQ, SqueezeLLM, and FP8 KV Cache.
• Optimized Kernels: Custom CUDA kernels for speed.

Flexibility and Integration

• Model Support: Seamlessly integrates with Hugging Face models, including Transformer-like (e.g., Llama), Mixture-of-Experts (e.g., Mixtral), and Multi-modal (e.g., LLaVA) architectures.
• Distributed Inference: Supports Tensor parallelism for multi-GPU setups.
• API Compatibility: Provides an OpenAI-compatible API server.
• Hardware Support: Works with NVIDIA GPUs, AMD GPUs, Intel CPUs, and Intel GPUs.
• Advanced Features: Supports streaming outputs, parallel sampling, beam search, and (experimentally) prefix caching and multi-LoRA support.

After the Value dot product, the accumulated results in accs must be reduced and written to global memory.

Workflow:

1. Intra-Warp Reduction: Threads within a warp reduce their accs values so each thread holds the accumulation for its assigned head positions across all tokens in a block.
2. Inter-Warp Reduction: A reduction is performed across all warps. This involves using shared memory (out_smem) where upper warps write to shared memory and lower warps update the accs values by reading from it.
3. Global Memory Write: The final results are written from local registers to the output global memory using a calculated out_ptr which points to the specific sequence, head, and partition assigned to the thread.

// Intra-warp reduction
for (int i = 0; i < NUM_ROWS_PER_THREAD; i++) {
   float acc = accs[i];
   for (int mask = NUM_V_VECS_PER_ROW / 2; mask >= 1; mask /= 2) {
      acc += VLLM_SHFL_XOR_SYNC(acc, mask);
   }
   accs[i] = acc;
}

// Output pointer calculation and write-out
scalar_t* out_ptr = out + seq_idx * num_heads * max_num_partitions * HEAD_SIZE
                + head_idx * max_num_partitions * HEAD_SIZE
                + partition_idx * HEAD_SIZE;

for (int i = 0; i < NUM_ROWS_PER_THREAD; i++) {
   const int row_idx = lane / NUM_V_VECS_PER_ROW + i * NUM_ROWS_PER_ITER;
   if (row_idx < HEAD_SIZE && lane % NUM_V_VECS_PER_ROW == 0) {
       from_float(*(out_ptr + row_idx), accs[i]);
   }
}

To understand the kernel implementation, you must understand these abstractions:

• Sequence: Represents a client request. In this single-query kernel, num_seqs equals the total number of tokens being processed in a batch.
• Context: The set of generated tokens in a sequence.
• Vec: A list of elements fetched/calculated together. VEC_SIZE (for Q/K) and V_VEC_SIZE (for V) are sized so thread groups/threads can fetch 16 bytes at a time.
• Thread group: A group of THREAD_GROUP_SIZE threads that fetches and calculates one query token and one key token at a time.
• Block: A unit of the KV cache storing a fixed BLOCK_SIZE of tokens for one head.
• Warp: A group of 32 threads (WARP_SIZE) that executes simultaneously. A warp processes the calculation between one query token and key tokens of one entire block (potentially across multiple blocks/iterations).
• Thread block: A group of NUM_THREADS that can access the same shared memory. In this kernel, a thread block processes the calculation for one query token against a whole context.
• Grid: The collection of thread blocks with shape (num_heads, num_seqs, max_num_partitions). Each thread block handles one head, one sequence, and one partition.

In the Paged Attention kernel, the Query-Key (QK) stage calculates the dot product between a query token and various key tokens.

Mechanism:

1. Fetch Query: The query data for one token is fetched and stored in q_vecs.
2. Iterate Keys: The kernel iterates through different k_ptrs (pointing to different tokens) and prepares k_vecs in an inner loop.
3. Dot Product: A dot multiplication is performed between q_vecs and k_vecs using Qk_dot<>::dot.

Key Detail: Although each thread only fetches a portion of the query and key data at a time, the Qk_dot<>::dot function performs a cross-thread group reduction. This ensures the returned qk value is the full dot product result for the entire query and key token data, even if HEAD_SIZE is larger than the data fetched by a single thread (e.g., if HEAD_SIZE is 128 and THREAD_GROUP_SIZE is 2, each thread handles 64 elements, but the result is the full 128-element dot product).

q_vecs = ...
for ... {
   k_ptr = ...
   for ... {
      k_vecs[i] = ...
   }
   ...
   float qk = scale * Qk_dot<scalar_t, THREAD_GROUP_SIZE>::dot(q_vecs[thread_group_offset], k_vecs);
}