From e173d6b1b13b24860d5948c386f629aaaf53f862 Mon Sep 17 00:00:00 2001 From: Alyssa Rosenzweig Date: Fri, 12 Jul 2019 14:48:34 -0700 Subject: [PATCH] panfrost: Precompute scoreboard dependents Mali job dependency graphs, at least for GLES3.0, have the special property that a given node will only have at most a single dependent. This allows us to efficiently precompute the dependent array and replace an inner loop's O(N) search with an O(1) lookup, bringing the algorithmic complexity of scoreboarding from O(N^2) to O(N). Signed-off-by: Alyssa Rosenzweig --- src/gallium/drivers/panfrost/pan_scoreboard.c | 58 +++++++++++++++++-- 1 file changed, 54 insertions(+), 4 deletions(-) diff --git a/src/gallium/drivers/panfrost/pan_scoreboard.c b/src/gallium/drivers/panfrost/pan_scoreboard.c index ed3f42271d4..63463daf0b4 100644 --- a/src/gallium/drivers/panfrost/pan_scoreboard.c +++ b/src/gallium/drivers/panfrost/pan_scoreboard.c @@ -366,7 +366,40 @@ panfrost_scoreboard_link_batch(struct panfrost_job *batch) BITSET_WORD *edge_removal_1 = calloc(sz, 1); BITSET_WORD *edge_removal_2 = calloc(sz, 1); - /* We compute no_incoming by traversing the batch. */ + /* We compute no_incoming by traversing the batch. Simultaneously, we + * would like to keep track of a parity-reversed version of the + * dependency graph. Dependency indices are 16-bit and in practice (for + * ES3.0, at least), we can guarantee a given node will be depended on + * by no more than one other nodes. P.f: + * + * Proposition: Given a node N of type T, no more than one other node + * depends on N. + * + * If type is SET_VALUE: The only dependency added against us is from + * the first tiler job, so there is 1 dependent. + * + * If type is VERTEX: If there is a tiler node, that tiler node depends + * on us; if there is not (transform feedback), nothing depends on us. + * Therefore there is at most 1 dependent. + * + * If type is TILER: If there is another TILER job in succession, that + * node depends on us. No other job type depends on us. Therefore there + * is at most 1 dependent. + * + * If type is FRAGMENT: This type cannot be in a primary chain, so it + * is irrelevant. Just for kicks, nobody would depend on us, so there + * are zero dependents, so it holds anyway. + * + * TODO: Revise this logic for ES3.1 and above. This result may not + * hold for COMPUTE/FUSED/GEOMETRY jobs; we might need to special case + * those. Can FBO dependencies be expressed within a chain? + * --- + * + * Point is, we only need to hold a single dependent, which is a pretty + * helpful result. + */ + + unsigned *dependents = calloc(node_count, sizeof(unsigned)); for (unsigned i = 0; i < node_count; ++i) { struct mali_job_descriptor_header *node = DESCRIPTOR_FOR_NODE(i); @@ -374,8 +407,23 @@ panfrost_scoreboard_link_batch(struct panfrost_job *batch) unsigned dep_1 = node->job_dependency_index_1; unsigned dep_2 = node->job_dependency_index_2; + /* Record no_incoming info for this node */ + if (!(dep_1 || dep_2)) BITSET_SET(no_incoming, i); + + /* Record this node as the dependent of each of its + * dependencies */ + + if (dep_1) { + assert(!dependents[dep_1 - 1]); + dependents[dep_1 - 1] = i; + } + + if (dep_2) { + assert(!dependents[dep_2 - 1]); + dependents[dep_2 - 1] = i; + } } /* No next_job fields are set at the beginning, so L is implciitly the @@ -415,8 +463,10 @@ panfrost_scoreboard_link_batch(struct panfrost_job *batch) tail = n; - /* Scan dependencies */ - for (unsigned node_m = 0; node_m < node_count; ++node_m) { + /* Grab the dependent, if there is one */ + unsigned node_m = dependents[node_n]; + + if (node_m) { struct mali_job_descriptor_header *m = DESCRIPTOR_FOR_NODE(node_m); @@ -439,7 +489,7 @@ panfrost_scoreboard_link_batch(struct panfrost_job *batch) dep_2 = 0; } else { /* This node has no relevant dependencies */ - continue; + assert(0); } /* Are there edges left? If not, add us to S */ -- 2.30.2