Can someone explain what ggml_backend_sched_t do?

[Zijie-Tian]

Recently, I’ve been studying ggml_backend_sched_t in ggml. I understand that sched enables compute with multi-backends. However, I’m quite confused about ggml_backend_sched_split_graph, ggml_backend_sched_alloc_splits, and ggml_backend_sched_reserve. Could someone help me clarify:

1. I understand that ggml_backend_sched_split_graph is likely dividing the computation graph based on buffer types, but in the logic of splitting, I have a hard time understanding the following code:
   

   llama.cpp/ggml/src/ggml-backend.cpp

   Lines 1184 to 1243 in a9e8a9a

   	// pass 3: upgrade nodes to higher prio backends with compatible buffer types
   	// if the tensor is already in the same buffer type (*) as another higher priority backend, we should move it there
   	// however, we also need to verify that the sources are in compatible buffer types
   	// (*) the actual requirement is more relaxed, the buffer type of the backend should be supported by all the users of this tensor further down the graph
   	// however, this is slow to verify, so we have a more strict requirement that the buffer type is the same
   	// this is not uncommon since multiple backends can use host memory, with the same buffer type (eg. BLAS and CPU)
   	// additionally, set remaining unassigned nodes to the backend with the most supported inputs
   	// only nodes that could not be assigned during expansion due to the backend not supporting the op should be unassigned at this point
   	for (int i = 0; i < graph->n_nodes; i++) {
   	struct ggml_tensor * node = graph->nodes[i];
   	if (ggml_is_view_op(node->op)) {
   	continue;
   	}
   	int * node_backend_id = &tensor_backend_id(node);
   	if (*node_backend_id == -1) {
   	// unassigned node: find the backend with the most supported inputs
   	int n_supported_best = -1;
   	for (int b = 0; b < sched->n_backends; b++) {
   	if (ggml_backend_supports_op(sched->backends[b], node)) {
   	int n_supported = 0;
   	for (int j = 0; j < GGML_MAX_SRC; j++) {
   	struct ggml_tensor * src = node->src[j];
   	if (src == NULL) {
   	continue;
   	}
   	if ((tensor_backend_id(src) != -1 || tensor_backend_id(src->view_src) != -1) && ggml_backend_sched_buffer_supported(sched, src, b)) {
   	n_supported++;
   	}
   	}
   	if (n_supported > n_supported_best) {
   	n_supported_best = n_supported;
   	*node_backend_id = b;
   	SET_CAUSE(node, "3.best");
   	}
   	}
   	}
   	} else {
   	// assigned node: upgrade to higher prio backend if possible
   	for (int b = 0; b < *node_backend_id; b++) {
   	if (sched->bufts[b] == sched->bufts[*node_backend_id] && ggml_backend_supports_op(sched->backends[b], node)) {
   	bool supported = true;
   	for (int j = 0; j < GGML_MAX_SRC; j++) {
   	struct ggml_tensor * src = node->src[j];
   	if (src == NULL) {
   	continue;
   	}
   	if (!ggml_backend_sched_buffer_supported(sched, src, b)) {
   	supported = false;
   	break;
   	}
   	}
   	if (supported) {
   	*node_backend_id = b;
   	SET_CAUSE(node, "3.upg");
   	break;
   	}
   	}
   	}
   	}
   	}

   
   What is the purpose of this code?

2. Additionally, I’m still confused by the following code:
   

   llama.cpp/ggml/src/ggml-backend.cpp

   Lines 1357 to 1400 in a9e8a9a

   	if (src->flags & GGML_TENSOR_FLAG_INPUT && sched->n_copies > 1) {
   	if (tensor_id_copy(src_id, src_backend_id, 0) == NULL) {
   	ggml_backend_t backend = sched->backends[src_backend_id];
   	for (int c = 0; c < sched->n_copies; c++) {
   	struct ggml_tensor * tensor_copy;
   	if (c == sched->cur_copy) {
   	tensor_copy = src; // use the original tensor as the current copy
   	} else {
   	tensor_copy = ggml_dup_tensor_layout(sched->ctx, src);
   	ggml_format_name(tensor_copy, "%s#%s#%d", ggml_backend_name(backend), src->name, c);
   	}
   	if (sched->n_copies > 1) {
   	ggml_set_input(tensor_copy);
   	ggml_set_output(tensor_copy); // prevent ggml-alloc from overwriting the tensor
   	}
   	tensor_id_copy(src_id, src_backend_id, c) = tensor_copy;
   	SET_CAUSE(tensor_copy, "4.cpy");
   	}
   	int n_graph_inputs = sched->n_graph_inputs++;
   	GGML_ASSERT(n_graph_inputs < GGML_SCHED_MAX_SPLIT_INPUTS);
   	sched->graph_inputs[n_graph_inputs] = src;
   	}
   	}
   	if (src_backend_id != cur_backend_id && !ggml_backend_sched_buffer_supported(sched, src, cur_backend_id)) {
   	// create a copy of the input in the split's backend
   	if (tensor_id_copy(src_id, cur_backend_id, 0) == NULL) {
   	ggml_backend_t backend = sched->backends[cur_backend_id];
   	for (int c = 0; c < sched->n_copies; c++) {
   	struct ggml_tensor * tensor_copy = ggml_dup_tensor_layout(sched->ctx, src);
   	ggml_format_name(tensor_copy, "%s#%s#%d", ggml_backend_name(backend), src->name, c);
   	if (sched->n_copies > 1) {
   	ggml_set_input(tensor_copy);
   	ggml_set_output(tensor_copy); // prevent ggml-alloc from overwriting the tensor
   	}
   	tensor_id_copy(src_id, cur_backend_id, c) = tensor_copy;
   	SET_CAUSE(tensor_copy, "4.cpy");
   	}
   	int n_inputs = split->n_inputs++;
   	GGML_ASSERT(n_inputs < GGML_SCHED_MAX_SPLIT_INPUTS);
   	split->inputs[n_inputs] = src;
   	}
   	node->src[j] = tensor_id_copy(src_id, cur_backend_id, sched->cur_copy);
   	}

   
   I know it establishes a copy between different buffers, but is this copy pre-allocated with a buffer, or is it copied at runtime?

3. What is the difference between ggml_backend_sched_reserve and ggml_backend_sched_alloc_graph? I’m confused about the purpose of each.
   

   llama.cpp/ggml/src/ggml-backend.cpp

   Lines 1727 to 1755 in a9e8a9a

   	bool ggml_backend_sched_reserve(ggml_backend_sched_t sched, struct ggml_cgraph * measure_graph) {
   	GGML_ASSERT((int)sched->hash_set.size >= measure_graph->n_nodes + measure_graph->n_leafs);
   	ggml_backend_sched_split_graph(sched, measure_graph);
   	if (!ggml_gallocr_reserve_n(sched->galloc, &sched->graph, sched->node_backend_ids, sched->leaf_backend_ids)) {
   	return false;
   	}
   	ggml_backend_sched_reset(sched);
   	ggml_backend_sched_synchronize(sched);
   	return true;
   	}
   	bool ggml_backend_sched_alloc_graph(ggml_backend_sched_t sched, struct ggml_cgraph * graph) {
   	GGML_ASSERT((int)sched->hash_set.size >= graph->n_nodes + graph->n_leafs);
   	ggml_backend_sched_split_graph(sched, graph);
   	if (!ggml_backend_sched_alloc_splits(sched)) {
   	return false;
   	}
   	sched->is_alloc = true;
   	return true;
   	}

4. I noticed that my code enters the following section and throws an error. When it enters this if branch, I’m really curious about what this part is checking? how can i solve it by modify compute graph?
   

   llama.cpp/ggml/src/ggml-backend.cpp

   Lines 1524 to 1534 in a9e8a9a

   	if (backend_ids_changed || !ggml_gallocr_alloc_graph(sched->galloc, &sched->graph)) {
   	// the re-allocation may cause the split inputs to be moved to a different address
   	ggml_backend_sched_synchronize(sched);
   	#ifndef NDEBUG
   	GGML_LOG_DEBUG("%s: failed to allocate graph, reserving (backend_ids_changed = %d)\n", __func__, backend_ids_changed);
   	#endif
   	ggml_gallocr_reserve_n(sched->galloc, &sched->graph, sched->node_backend_ids, sched->leaf_backend_ids);
   	if (!ggml_gallocr_alloc_graph(sched->galloc, &sched->graph)) {
   	GGML_LOG_ERROR("%s: failed to allocate graph\n", __func__);
   	return false;
   	}

5. What is the purpose of sched->is_alloc?
   

   llama.cpp/ggml/src/ggml-backend.cpp

   Line 1724 in a9e8a9a

   sched->is_alloc = false;

   
   

   llama.cpp/ggml/src/ggml-backend.cpp

   Line 1752 in a9e8a9a

   sched->is_alloc = true;

[slaren]

1. I am not sure that I can add much more to what is already written in the comment. If you are confused why that is necessary, keep in mind that the scheduler does not find the most optimal way to split the graph algorithmically, because that would be far too expensive. Instead, it is a bunch of heuristics that work well in the common use cases. So the answer to why the split is done the way it is, it is because it solved some specific problem that was found during development.
2. The copies are performed during ggml_backend_sched_compute_splits. The reason there may be multiple copies of each tensor is because it improves efficiency when using pipeline parallelism.
3. reserve is only intended to be used to pre-allocate the compute buffers
4. To avoid this you need to reserve the graph with the largest possible tensors (eg. with the maximum context size in a transformer), and ensure that the following graphs are topologically identical and use tensors that are equal or smaller than the graph used during reserve. Generally this is not something that you need to worry about unless you are trying to implement pipeline parallelism.
5. To keep track of whether the graph is allocated so that it can be allocated automatically in ggml_backend_sched_graph_compute if necessary

[Zijie-Tian]

Thank you for you answer! slaren!!! .

I am not sure that I can add much more to what is already written in the comment. If you are confused why that is necessary, keep in mind that the scheduler does not find the most optimal way to split the graph algorithmically, because that would be far too expensive. Instead, it is a bunch of heuristics that work well in the common use cases. So the answer to why the split is done the way it is, it is because it solved some specific problem that was found during development.

As I understand it, currently, ggml_backend_sched_compute_splits is only used to identify the positions where additional copies are needed and to promote operators to a higher-priority backend (e.g., the GPU) whenever possible. Is it right?

To avoid this you need to reserve the graph with the largest possible tensors (eg. with the maximum context size in a transformer), and ensure that the following graphs are topologically identical and use tensors that are equal or smaller than the graph used during reserve. Generally this is not something that you need to worry about unless you are trying to implement pipeline parallelism.

Additionally, I would still appreciate a detailed explanation of the cause of this error. Could you perhaps give a very simple example?

[Zijie-Tian]

The copies are performed during ggml_backend_sched_compute_splits. The reason there may be multiple copies of each tensor is because it improves efficiency when using pipeline parallelism.

Additionally, I'd like to ask if the intermediate computation results (model activations) will cause multiple memory copy (for example, Qcur in CPU and GPU?) during inference runtime?

[slaren]

As I understand it, currently, ggml_backend_sched_compute_splits is only used to identify the positions where additional copies are needed and to promote operators to a higher-priority backend (e.g., the GPU) whenever possible. Is it right?

ggml_backend_sched_split_graph does that. ggml_backend_sched_compute_splits does the computation, copying data between the graph splits as needed.

Additionally, I would still appreciate a detailed explanation of the cause of this error. Could you perhaps give a very simple example?

This is not an error, it's just a message for debugging issues. It happens when evaluating a graph that either has a different topology than the previous graph (ie. the graph nodes are different), or when the topology is the same, but some tensors are larger. This means that the memory addresses assigned to each tensor need to be recalculated, and this forces a synchronization. Generally this is not something that you need to worry about.

Additionally, I'd like to ask if the intermediate computation results (model activations) will cause multiple memory copy (for example, Qcur in CPU and GPU?) during inference runtime?

If you set the environment variable GGML_SCHED_DEBUG to 1 or 2, you will get a detailed report of how the graph was split. At the start of every split, you will see a list of inputs: these are tensors that are being copied to a different backend.

[Zijie-Tian]

Thank you!!! Slaren. I greatly appreciate your work.

[Zijie-Tian]

slaren, I found that in the ggml_backend_sched_split_graph function, there are extensive graph splitting operations internally, depending on the backend, which results in multiple splits. However, these splits may lead to unnecessary memory copies in runtime. I'm wondering if there could be cases where different backends don't actually require splitting. For example, Mac or Jetson's Unified Memory might not need these splittings.