Does llama-parallel executes the llama_decode in serial for np=2 or more?

[abhishek-rn]

Hi,
I tried running parallel execution as below:
llama-parallel -m ggml-model-q8_0.gguf -c 8192 -np 2 -n 2 -ns 4 -t 1
It should ideally execute llama_decode 2 times but it gets executed 4 times.
Does this mean even for 2 parallel executions, the compute of next token for each sequence happens serially i.e. Sequence 1 token generation followed by Sequence 2 token generation (till we reach end of tokens for each sequence) before moving on to the next sequences?
Below is a debug line printf("\nLlama_decode"); added inside llama_decode function:

int32_t llama_decode(
        struct llama_context * ctx,
          struct llama_batch   batch) {
    printf("\nLlama_decode");
    const int ret = llama_decode_internal(*ctx, batch);
    if (ret < 0) {
        LLAMA_LOG_ERROR("%s: failed to decode, ret = %d\n", __func__, ret);
    }

    return ret;
}

The output returns:

No new questions so proceed with build-in defaults.


main: Simulating parallel requests from clients:
main: n_parallel = 2, n_sequences = 4, cont_batching = 1, system tokens = 305
Llama_decode

main: Evaluating the system prompt ...

Processing requests ...

main: clearing the KV cache
Client   0, seq    0, started decoding ...
Llama_decode
Client   1, seq    1, started decoding ...
Llama_decode
Llama_decode
Llama_decode
Client   0, seq   0/  4, prompt   11 t, response    3 t, time 18.95 s, speed  0.74 t/s, cache miss 0  

Input:    What is the meaning of life?
Response: The meaning of life

Client   1, seq   1/  4, prompt   15 t, response    3 t, time 18.95 s, speed  0.95 t/s, cache miss 0  

Input:    What is the best way to cook a steak?
Response: The best way to

main: clearing the KV cache
Client   0, seq    2, started decoding ...
Client   1, seq    3, started decoding ...
Llama_decode
Llama_decode
Llama_decode
Llama_decode
Client   0, seq   2/  4, prompt   11 t, response    3 t, time 23.07 s, speed  0.61 t/s, cache miss 0  

Input:    What is the meaning of life?
Response: The meaning of life

Client   1, seq   3/  4, prompt   22 t, response    3 t, time 23.07 s, speed  1.08 t/s, cache miss 0  

Input:    Are you familiar with the Special Theory of Relativity and can you explain it to me?
Response: The Special Theory of

main: clearing the KV cache

run parameters as of 2024-10-23 19:07:22

main: n_parallel = 2, n_sequences = 4, cont_batching = 1, system tokens = 305
External prompt file: used built-in defaults
Model and path used:  /home/abhishekn/workspace/LLMcode/llama.cpp/models/7B/ggml-model-q8_0.gguf

Total prompt tokens:     59, speed:  0.27 t/s
Total gen tokens:        12, speed:  0.06 t/s
Total speed (AVG):           speed:  0.33 t/s
Cache misses:             0

llama_perf_context_print:        load time =    2834.65 ms
llama_perf_context_print: prompt eval time =  214735.09 ms /   376 tokens (  571.10 ms per token,     1.75 tokens per second)
llama_perf_context_print:        eval time =       0.00 ms /     1 runs   (    0.00 ms per token,      inf tokens per second)
llama_perf_context_print:       total time =  214738.54 ms /   377 tokens
Llama_decode

[ggerganov]

Parallel sequences are stacked into the same batch (as long as they fit in it) so a single llama_decode can process arbitrary number of parallel sequences.

The printf is displayed out of order, because all other logs are printed asynchronously in a different thread, so it is difficult to analyze the output. Change the printf to LLAMA_LOG function for correct output.

[abhishek-rn]

Thank you for the response.
It makes complete sense.
I was just trying to understand how the "ggml_graph_compute" executes without knowing which seq_id the data belongs to.
I see the graph and data gets executed without any reference to the requests being executed.
I am assuming there would be some kind of masking at the KV cache to differentiate which request the particular data belongs to.
Can you please enlighten on this.

[ggerganov]

Lets say we have a batch of 3 sequences:

batch:
  tokens: a b c d e f g h a b c d a b c d e f
  pos   : 0 1 2 3 4 5 6 7 0 1 2 3 0 1 2 3 4 5
  seq_id: 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2
  logits: 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1

Assume that we have evaluated this batch already and the data is stored in the KV cache.

We now sample 3 tokens (A0, A1, A2) - 1 from each sequence and construct a new batch to evaluate them:

batch:
  tokens: A0 A1 A2
  pos   : 8  4  6
  seq_id: 0  1  2

While evaluating this batch, we construct the following KQ mask, based on the tokens positions and sequence ids:

mask 3 x 21:
          0 0 0 0 0 0 0 0 x x x x x x x x x x  0  x  x
          x x x x x x x x 0 0 0 0 x x x x x x  x  0  x
          x x x x x x x x x x x x 0 0 0 0 0 0  x  x  0

The x corresponds to -INF:

https://github.com/ggerganov/llama.cpp/blob/8f275a7c4593aa34147595a90282cf950a853690/src/llama.cpp#L16686-L16738

We use this mask during the attention to filter which tokens attend to which:

https://github.com/ggerganov/llama.cpp/blob/8f275a7c4593aa34147595a90282cf950a853690/src/llama.cpp#L9648-L9651

[abhishek-rn]

Thank you.
This was a much detailed answer.
Appreciate your efforts in not just building a software like this but also explaining the parts of this code in a lucid way.