DPDK-dev Archive on lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH dpdk/26.11 v3 0/2] graph: topological bitmap scheduling
@ 2026-07-17  9:03 Robin Jarry
  2026-07-17  9:03 ` [PATCH dpdk/26.11 v3 1/2] graph: add diamond topology performance test Robin Jarry
  2026-07-17  9:03 ` [PATCH dpdk/26.11 v3 2/2] graph: replace circular buffer with topological bitmap Robin Jarry
  0 siblings, 2 replies; 3+ messages in thread
From: Robin Jarry @ 2026-07-17  9:03 UTC (permalink / raw)
  To: dev
  Cc: Christophe Fontaine, David Marchand, Jerin Jacob,
	Kiran Kumar Kokkilagadda, Konstantin Ananyev, Maxime Leroy,
	Nithin Kumar Dabilpuram, Vladimir Medvedkin, Zhirun Yan

Replace the FIFO circular buffer in rte_graph with a bitmap and a
topologically-sorted schedule table. The old circular buffer appended
nodes in enqueue order, effectively a partial DFS driven by per-node
process functions. This caused convergence nodes to be visited before
all upstream branches had run, resulting in redundant visits with
smaller batches.

Nodes are now sorted by (topo_order, node_id) using BFS depth from
source nodes, ensuring upstream nodes are always visited before
downstream ones. The diamond perf test shows a ~10% throughput
improvement (converge visited once at 256 objs/call instead of twice
at 128).

Changes v2 -> v3:
 - dropped explicit priority field (int16_t) from rte_node_register
   and struct node; topological ordering from BFS is sufficient
 - removed hiprio worker node type from diamond test; topo_order
   alone provides correct ordering without user intervention
 - updated documentation and SVG diagram accordingly

Changes v1 -> v2:
 - split diamond perf test into separate preparatory patch
 - added topological depth (topo_order) as secondary sort key to
   preserve upstream-before-downstream ordering, preventing a
   regression in the reverse tree test
 - restored idx == 0 guard on bitmap set in the enqueue path to
   avoid a ~15% throughput regression caused by touching the pending
   bitmap cache line on every enqueue call
 - added performance numbers measured before and after

Cc: Christophe Fontaine <cfontain@redhat.com>
Cc: David Marchand <david.marchand@redhat.com>
Cc: Jerin Jacob <jerinj@marvell.com>
Cc: Kiran Kumar Kokkilagadda <kirankumark@marvell.com>
Cc: Konstantin Ananyev <konstantin.ananyev@huawei.com>
Cc: Maxime Leroy <maxime@leroys.fr>
Cc: Nithin Kumar Dabilpuram <ndabilpuram@marvell.com>
Cc: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
Cc: Zhirun Yan <yanzhirun_163@163.com>

Robin Jarry (2):
  graph: add diamond topology performance test
  graph: replace circular buffer with topological bitmap

 app/test/test_graph_perf.c                    |  130 +-
 doc/guides/prog_guide/graph_lib.rst           |   29 +-
 .../prog_guide/img/graph_mem_layout.svg       | 1823 +++++++----------
 lib/graph/graph.c                             |   27 +-
 lib/graph/graph_debug.c                       |   12 +-
 lib/graph/graph_ops.c                         |   46 +
 lib/graph/graph_populate.c                    |  107 +-
 lib/graph/graph_private.h                     |   41 +-
 lib/graph/rte_graph_model_mcore_dispatch.h    |   34 +-
 lib/graph/rte_graph_model_rtc.h               |   63 +-
 lib/graph/rte_graph_worker.h                  |    2 +-
 lib/graph/rte_graph_worker_common.h           |   78 +-
 12 files changed, 1158 insertions(+), 1234 deletions(-)

-- 
2.55.0


^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2026-07-17  9:05 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-07-17  9:03 [PATCH dpdk/26.11 v3 0/2] graph: topological bitmap scheduling Robin Jarry
2026-07-17  9:03 ` [PATCH dpdk/26.11 v3 1/2] graph: add diamond topology performance test Robin Jarry
2026-07-17  9:03 ` [PATCH dpdk/26.11 v3 2/2] graph: replace circular buffer with topological bitmap Robin Jarry

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox