#include "llama-memory-hybrid-idx.h"
#include "llama-impl.h"
#include "llama-batch.h"
#include "llama-io.h"
#include "llama-model.h"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iterator>
#include <stdexcept>
llama_memory_hybrid_idx::llama_memory_hybrid_idx(
const llama_model & model,
ggml_type type_k,
ggml_type type_v,
bool v_trans,
uint32_t kv_size,
uint32_t n_pad,
uint32_t n_swa,
llama_swa_type swa_type,
ggml_type type_r,
ggml_type type_s,
uint32_t rs_size,
uint32_t n_seq_max,
uint32_t n_rs_seq,
bool offload,
bool unified,
const layer_filter_cb & filter_attn,
const layer_filter_cb & filter_recr,
const layer_filter_cb & filter_idx) :
llama_memory_hybrid(
model,
type_k, type_v, v_trans, kv_size, n_pad, n_swa, swa_type,
type_r, type_s, rs_size,
n_seq_max, n_rs_seq, offload, unified,
filter_attn, filter_recr),
hparams_idx(model.hparams),
mem_idx(filter_idx == nullptr ? nullptr : [&] {
std::fill(hparams_idx.n_head_kv_arr.begin(), hparams_idx.n_head_kv_arr.end(), 1);
hparams_idx.n_embd_head_k_full = model.hparams.indexer_head_size;
hparams_idx.rope_type = LLAMA_ROPE_TYPE_NONE;
LLAMA_LOG_INFO("%s: creating indexer KV cache, size = %u cells\n", __func__, kv_size);
return new llama_kv_cache(
model, hparams_idx, type_k, type_v, v_trans, offload, unified,
kv_size, n_seq_max, n_pad, n_swa, swa_type,
nullptr, filter_idx, nullptr, nullptr, "idx_");
}()) {}
llama_memory_context_ptr llama_memory_hybrid_idx::init_batch(llama_batch_allocr & balloc, uint32_t n_ubatch, bool embd_all) {
do {
balloc.split_reset();
std::vector<llama_ubatch> ubatches;
while (true) {
llama_ubatch ubatch;
if (embd_all) {
ubatch = balloc.split_seq(n_ubatch);
} else {
const bool unified = (get_mem_attn()->get_n_stream() == 1);
const uint32_t n_rs_seq = get_mem_recr()->n_rs_seq;
ubatch = balloc.split_equal(n_ubatch, !unified, n_rs_seq > 0 ? n_rs_seq + 1 : 0);
}
if (ubatch.n_tokens == 0) {
break;
}
ubatches.push_back(std::move(ubatch)); }
if (balloc.get_n_used() < balloc.get_n_tokens()) {
break;
}
if (!get_mem_recr()->prepare(ubatches)) {
LLAMA_LOG_ERROR("%s: failed to prepare recurrent ubatches\n", __func__);
return std::make_unique<llama_memory_hybrid_idx_context>(LLAMA_MEMORY_STATUS_FAILED_PREPARE);
}
auto heads_attn = get_mem_attn()->prepare(ubatches);
if (heads_attn.empty()) {
LLAMA_LOG_ERROR("%s: failed to prepare attention ubatches\n", __func__);
return std::make_unique<llama_memory_hybrid_idx_context>(LLAMA_MEMORY_STATUS_FAILED_PREPARE);
}
llama_kv_cache::slot_info_vec_t heads_idx;
if (mem_idx) {
heads_idx = heads_attn;
}
return std::make_unique<llama_memory_hybrid_idx_context>(
this, std::move(heads_attn), std::move(heads_idx), std::move(ubatches));
} while(false);
return std::make_unique<llama_memory_hybrid_idx_context>(LLAMA_MEMORY_STATUS_FAILED_PREPARE);
}
llama_memory_context_ptr llama_memory_hybrid_idx::init_full() {
return std::make_unique<llama_memory_hybrid_idx_context>(this);
}
llama_memory_context_ptr llama_memory_hybrid_idx::init_update(llama_context * lctx, bool optimize) {
return std::make_unique<llama_memory_hybrid_idx_context>(this, lctx, optimize);
}
void llama_memory_hybrid_idx::clear(bool data) {
llama_memory_hybrid::clear(data);
if (mem_idx) {
mem_idx->clear(data);
}
}
bool llama_memory_hybrid_idx::seq_rm(llama_seq_id seq_id, llama_pos p0, llama_pos p1) {
if (!get_mem_recr()->seq_rm(seq_id, p0, p1)) {
return false;
}
if (mem_idx) {
mem_idx->seq_rm(seq_id, p0, p1);
}
return get_mem_attn()->seq_rm(seq_id, p0, p1);
}
void llama_memory_hybrid_idx::seq_cp(llama_seq_id seq_id_src, llama_seq_id seq_id_dst, llama_pos p0, llama_pos p1) {
llama_memory_hybrid::seq_cp(seq_id_src, seq_id_dst, p0, p1);
if (mem_idx) {
mem_idx->seq_cp(seq_id_src, seq_id_dst, p0, p1);
}
}
void llama_memory_hybrid_idx::seq_keep(llama_seq_id seq_id) {
llama_memory_hybrid::seq_keep(seq_id);
if (mem_idx) {
mem_idx->seq_keep(seq_id);
}
}
void llama_memory_hybrid_idx::seq_add(llama_seq_id seq_id, llama_pos p0, llama_pos p1, llama_pos shift) {
llama_memory_hybrid::seq_add(seq_id, p0, p1, shift);
if (mem_idx) {
mem_idx->seq_add(seq_id, p0, p1, shift);
}
}
void llama_memory_hybrid_idx::seq_div(llama_seq_id seq_id, llama_pos p0, llama_pos p1, int d) {
llama_memory_hybrid::seq_div(seq_id, p0, p1, d);
if (mem_idx) {
mem_idx->seq_div(seq_id, p0, p1, d);
}
}
std::map<ggml_backend_buffer_type_t, size_t> llama_memory_hybrid_idx::memory_breakdown() const {
std::map<ggml_backend_buffer_type_t, size_t> mb = llama_memory_hybrid::memory_breakdown();
if (mem_idx) {
for (const auto & buft_size : mem_idx->memory_breakdown()) {
mb[buft_size.first] += buft_size.second;
}
}
return mb;
}
void llama_memory_hybrid_idx::state_write(llama_io_write_i & io, llama_seq_id seq_id, llama_state_seq_flags flags) const {
llama_memory_hybrid::state_write(io, seq_id, flags);
if ((flags & LLAMA_STATE_SEQ_FLAGS_PARTIAL_ONLY) == 0) {
if (mem_idx) {
mem_idx->state_write(io, seq_id, flags);
}
}
}
void llama_memory_hybrid_idx::state_read(llama_io_read_i & io, llama_seq_id seq_id, llama_state_seq_flags flags) {
llama_kv_cache::slot_info_vec_t sinfos_attn;
try {
if ((flags & LLAMA_STATE_SEQ_FLAGS_PARTIAL_ONLY) == 0) {
get_mem_attn()->state_read_sinfo(io, seq_id, flags, mem_idx ? &sinfos_attn : nullptr, nullptr);
}
get_mem_recr()->state_read(io, seq_id, flags);
if ((flags & LLAMA_STATE_SEQ_FLAGS_PARTIAL_ONLY) == 0) {
if (mem_idx) {
mem_idx->state_read_sinfo(io, seq_id, flags, nullptr, &sinfos_attn);
}
}
} catch (...) {
state_drop(seq_id);
throw;
}
}
void llama_memory_hybrid_idx::state_drop(llama_seq_id seq_id) {
if (seq_id < 0) {
clear(true);
return;
}
get_mem_attn()->seq_rm(seq_id, -1, -1);
get_mem_recr()->seq_rm(seq_id, -1, -1);
if (mem_idx) {
mem_idx->seq_rm(seq_id, -1, -1);
}
}
llama_kv_cache * llama_memory_hybrid_idx::get_mem_idx() const {
return mem_idx.get();
}
void llama_memory_hybrid_idx::set_input_qsa(
ggml_tensor * cell_blk,
ggml_tensor * blk_cells,
ggml_tensor * blk_pos,
ggml_tensor * bias,
const llama_ubatch * ubatch,
uint32_t ratio,
bool blk_bias) const {
GGML_ASSERT(ratio > 0);
GGML_ASSERT(get_mem_idx() != nullptr);
GGML_ASSERT(ggml_backend_buffer_is_host(cell_blk->buffer));
const int64_t n_kv = cell_blk->ne[0];
const int64_t n_ns = cell_blk->ne[1]; const int64_t n_blocks = blk_pos->ne[0]/(4*n_ns);
const int64_t n_tokens = ubatch->n_tokens;
const int64_t r = ratio;
GGML_ASSERT(n_tokens % n_ns == 0);
const int64_t n_tps = n_tokens/n_ns;
int32_t * dst_cell_blk = (int32_t *) cell_blk->data;
int32_t * dst_blk_cells = (int32_t *) blk_cells->data;
int32_t * dst_blk_pos = (int32_t *) blk_pos->data;
float * dst_bias = (float *) bias->data;
GGML_ASSERT(r <= 64);
const uint64_t slots_full = r == 64 ? ~uint64_t(0) : ((uint64_t(1) << r) - 1);
std::vector<int32_t> blk_of(n_kv);
std::vector<int32_t> cell_grp(n_kv);
std::vector<int32_t> grp_head(n_blocks);
std::vector<int32_t> grp_next;
std::vector<int32_t> grp_first;
std::vector<int32_t> grp_slot0;
std::vector<uint64_t> grp_slots;
std::vector<int32_t> grp_bid;
std::vector<int32_t> bid_idx;
std::vector<int32_t> bid_cell;
std::vector<int32_t> bid_slot0;
std::vector<int32_t> order;
std::vector<int32_t> rank;
std::fill(dst_blk_pos, dst_blk_pos + 4*n_blocks*n_ns, 0);
for (int64_t s = 0; s < n_ns; ++s) {
const llama_seq_id seq_of_stream = ubatch->seq_id[s*n_tps][0];
const auto & cells = get_mem_idx()->get_cells(seq_of_stream);
int32_t * cur_cell_blk = dst_cell_blk + s*n_kv;
int32_t * cur_blk_cells = dst_blk_cells + s*(r*n_blocks);
std::fill(cur_blk_cells, cur_blk_cells + r*n_blocks, 0);
bid_idx .clear();
bid_cell .clear();
bid_slot0.clear();
int n_seq_present = 0;
for (int sq = 0; sq < LLAMA_MAX_SEQ && n_seq_present < 2; ++sq) {
if (cells.seq_pos_min(sq) >= 0) {
n_seq_present++;
}
}
const bool one_seq = n_seq_present <= 1;
bool oor = false;
bool dup = false;
bool ranked = false;
auto group_cells = [&]() {
std::fill(blk_of.begin(), blk_of.end(), -1);
std::fill(cell_grp.begin(), cell_grp.end(), -1);
std::fill(grp_head.begin(), grp_head.end(), -1);
grp_next .clear();
grp_first.clear();
grp_slot0.clear();
grp_slots.clear();
grp_bid .clear();
oor = false;
dup = false;
for (int64_t j = 0; j < n_kv; ++j) {
if (cells.is_empty(j)) {
continue;
}
const int64_t idx = ranked ? rank[j] : cells.pos_get(j);
const int64_t pb = idx/r;
if (pb >= n_blocks) {
oor = true;
continue;
}
int32_t g = -1;
for (int32_t c = grp_head[pb]; c >= 0; c = grp_next[c]) {
if (one_seq || cells.seq_get_all((uint32_t) grp_first[c]) == cells.seq_get_all((uint32_t) j)) {
g = c;
break;
}
}
if (g < 0) {
g = (int32_t) grp_first.size();
grp_next .push_back(grp_head[pb]);
grp_first.push_back((int32_t) j);
grp_slot0.push_back(-1);
grp_slots.push_back(0);
grp_bid .push_back(-1);
grp_head[pb] = g;
}
const uint64_t bit = uint64_t(1) << (idx%r);
dup |= (grp_slots[g] & bit) != 0;
cell_grp[j] = g;
grp_slots[g] |= bit;
if (idx%r == 0) {
grp_slot0[g] = (int32_t) j;
}
}
};
group_cells();
if (dup && ubatch->is_pos_2d() && one_seq) {
order.clear();
order.reserve(n_kv);
for (int64_t j = 0; j < n_kv; ++j) {
if (!cells.is_empty(j)) {
order.push_back((int32_t) j);
}
}
std::sort(order.begin(), order.end(), [&cells](int32_t a, int32_t b) {
const llama_pos pa = cells.pos_get(a);
const llama_pos pb = cells.pos_get(b);
if (pa != pb) {
return pa < pb;
}
const auto & ea = cells.ext_get(a);
return cells.ext_get(b).is_2d_gt(ea.x, ea.y);
});
rank.assign(n_kv, -1);
for (int64_t k = 0; k < (int64_t) order.size(); ++k) {
rank[order[k]] = (int32_t) k;
}
ranked = true;
group_cells();
}
GGML_ASSERT((!blk_bias || !oor) && "qsa: cell position runs past the cell window");
int32_t n_bid = 0;
for (int64_t pb = 0; pb < n_blocks; ++pb) {
for (int32_t g = grp_head[pb]; g >= 0; g = grp_next[g]) {
if (grp_slots[g] != slots_full) {
continue;
}
grp_bid[g] = n_bid++;
bid_idx .push_back((int32_t) (pb*r));
bid_cell .push_back(grp_first[g]);
bid_slot0.push_back(grp_slot0[g]);
}
}
GGML_ASSERT(n_bid <= n_blocks);
for (int32_t b = 0; b < n_bid; ++b) {
int32_t sec_pos[4] = { bid_idx[b], bid_idx[b], bid_idx[b], bid_idx[b] };
if (ranked) {
const int32_t c = bid_slot0[b];
const llama_pos p = cells.pos_get(c);
const auto & e = cells.ext_get(c);
sec_pos[0] = p;
sec_pos[1] = e.y;
sec_pos[2] = e.x;
sec_pos[3] = p;
}
for (int64_t sec = 0; sec < 4; ++sec) {
dst_blk_pos[sec*(n_blocks*n_ns) + s*n_blocks + b] = sec_pos[sec];
}
}
const bool have_dead = n_bid < n_blocks;
const int32_t dead_bid = have_dead ? n_bid : n_blocks - 1;
for (int64_t j = 0; j < n_kv; ++j) {
const int32_t g = cell_grp[j];
blk_of[j] = g < 0 ? -1 : grp_bid[g];
if (blk_of[j] >= 0) {
const int64_t idx = ranked ? rank[j] : cells.pos_get(j);
cur_blk_cells[blk_of[j]*r + (idx%r)] = (int32_t) j;
}
cur_cell_blk[j] = blk_of[j] < 0 ? dead_bid : blk_of[j];
}
for (int64_t ii = 0; ii < n_tps; ++ii) {
const int64_t i = s*n_tps + ii;
const llama_seq_id seq_id = ubatch->seq_id[i][0];
int64_t q = ubatch->pos[i];
if (ranked) {
const llama_pos qt = ubatch->pos[i];
const llama_pos qy = ubatch->pos[i + n_tokens];
const llama_pos qx = ubatch->pos[i + n_tokens*2];
int64_t lo = 0;
int64_t hi = (int64_t) order.size();
while (lo < hi) {
const int64_t mid = (lo + hi)/2;
const int32_t c = order[mid];
const llama_pos pc = cells.pos_get(c);
if (pc < qt || (pc == qt && !cells.ext_get(c).is_2d_gt(qx, qy))) {
lo = mid + 1;
} else {
hi = mid;
}
}
q = lo - 1;
}
const int64_t tail_start = (q + 1)/r*r;
if (blk_bias) {
float * cur_blk_bias = dst_bias + i*n_blocks;
for (int64_t b = 0; b < n_blocks; ++b) {
if (b >= n_bid || !cells.seq_has((uint32_t) bid_cell[b], seq_id)) {
cur_blk_bias[b] = -INFINITY;
continue;
}
cur_blk_bias[b] = bid_idx[b] >= tail_start ? 1e9f : 0.0f;
}
if (have_dead) {
cur_blk_bias[dead_bid] = 1e9f;
}
continue;
}
float * cur_bias = dst_bias + i*n_kv;
for (int64_t j = 0; j < n_kv; ++j) {
float v = -INFINITY;
if (!cells.is_empty(j) && cells.seq_has(j, seq_id)) {
const int64_t idx = ranked ? rank[j] : cells.pos_get(j);
if (idx <= q) {
v = idx >= tail_start ? 1e9f : (blk_of[j] < 0 ? -INFINITY : 0.0f);
}
}
cur_bias[j] = v;
}
}
}
}
static std::vector<uint32_t> llama_memory_hybrid_idx_ns(const llama_kv_cache::slot_info_vec_t & sinfos) {
std::vector<uint32_t> res;
res.reserve(sinfos.size());
for (const auto & sinfo : sinfos) {
res.push_back(sinfo.s1 - sinfo.s0 + 1);
}
return res;
}
llama_memory_hybrid_idx_context::llama_memory_hybrid_idx_context(llama_memory_status status) :
llama_memory_hybrid_context(status) {}
llama_memory_hybrid_idx_context::llama_memory_hybrid_idx_context(llama_memory_hybrid_idx * mem) :
llama_memory_hybrid_context(mem),
mem(mem),
ns_ubatch(mem->get_mem_idx() == nullptr ?
std::vector<uint32_t>() : std::vector<uint32_t>{ mem->get_mem_idx()->get_n_stream() }),
ctx_idx(mem->get_mem_idx() == nullptr ? nullptr :
new llama_kv_cache_context(mem->get_mem_idx())) {}
llama_memory_hybrid_idx_context::llama_memory_hybrid_idx_context(
llama_memory_hybrid_idx * mem,
llama_context * lctx,
bool optimize) :
llama_memory_hybrid_context(mem, lctx, optimize),
mem(mem),
ctx_idx(mem->get_mem_idx() == nullptr ? nullptr :
mem->get_mem_idx()->init_update(lctx, optimize)) {}
llama_memory_hybrid_idx_context::llama_memory_hybrid_idx_context(
llama_memory_hybrid_idx * mem,
slot_info_vec_t sinfos_attn,
slot_info_vec_t sinfos_idx,
std::vector<llama_ubatch> ubatches) :
llama_memory_hybrid_context(mem, std::move(sinfos_attn), ubatches),
mem(mem),
ns_ubatch(llama_memory_hybrid_idx_ns(sinfos_idx)),
ctx_idx(mem->get_mem_idx() == nullptr ? nullptr :
new llama_kv_cache_context(mem->get_mem_idx(), std::move(sinfos_idx), ubatches)) {}
bool llama_memory_hybrid_idx_context::next() {
if (ctx_idx) {
ctx_idx->next();
}
++i_cur;
return llama_memory_hybrid_context::next();
}
bool llama_memory_hybrid_idx_context::apply() {
bool res = llama_memory_hybrid_context::apply();
if (ctx_idx) {
res = res & ctx_idx->apply();
}
return res;
}
const llama_kv_cache_context * llama_memory_hybrid_idx_context::get_idx() const {
return static_cast<const llama_kv_cache_context *>(ctx_idx.get());
}
uint32_t llama_memory_hybrid_idx_context::get_n_stream() const {
GGML_ASSERT(i_cur < ns_ubatch.size());
return ns_ubatch[i_cur];
}
void llama_memory_hybrid_idx_context::set_input_qsa(
ggml_tensor * cell_blk,
ggml_tensor * blk_cells,
ggml_tensor * blk_pos,
ggml_tensor * bias,
const llama_ubatch * ubatch,
uint32_t ratio,
bool blk_bias) const {
GGML_ASSERT(mem != nullptr);
mem->set_input_qsa(cell_blk, blk_cells, blk_pos, bias, ubatch, ratio, blk_bias);
}