Ideas for multithreaded rendering

[rovinski]

I saw the conversation in #3330, #3342, #3348, etc. and started thinking about how the rendering time might be improved aside from not drawing objects that aren't useful.

It seems that the rendering, for the most part, is embarrassingly parallel. In LayoutViewer::drawInstanceOutlines() for example (the most expensive layer measured in #3348), a function is applied to every instance in a vector to determine how / if it gets drawn, and then it makes a draw call.

OpenROAD/src/gui/src/layoutViewer.cpp

Lines 2041 to 2091 in 6920ac5

	// Draw the instances bounds
	void LayoutViewer::drawInstanceOutlines(QPainter* painter,
	const std::vector<odb::dbInst*>& insts)
	{
	int minimum_height_for_tag = nominalViewableResolution();
	int minimum_size = fineViewableResolution();
	const QTransform initial_xfm = painter->transform();
	painter->setPen(QPen(Qt::gray, 0));
	painter->setBrush(QBrush());
	for (auto inst : insts) {
	dbMaster* master = inst->getMaster();
	if (minimum_size > master->getWidth()
	&& minimum_size > master->getHeight()) {
	painter->setTransform(initial_xfm);
	int x;
	int y;
	inst->getOrigin(x, y);
	painter->drawPoint(x, y);
	} else {
	// setup the instance's transform
	QTransform xfm = initial_xfm;
	dbTransform inst_xfm;
	inst->getTransform(inst_xfm);
	addInstTransform(xfm, inst_xfm);
	painter->setTransform(xfm);
	// draw bbox
	Rect master_box;
	master->getPlacementBoundary(master_box);
	painter->drawRect(master_box.xMin(),
	master_box.yMin(),
	master_box.dx(),
	master_box.dy());
	// Draw an orientation tag in corner if useful in size
	qreal master_h = master->getHeight();
	if (master_h >= minimum_height_for_tag) {
	qreal master_w = master->getWidth();
	qreal tag_width = std::min(0.25 * master_w, 0.125 * master_h);
	qreal tag_x = master_box.xMin() + tag_width;
	qreal tag_y = master_box.yMin() + tag_width * 2;
	painter->drawLine(QPointF(tag_x, master_box.yMin()),
	QPointF(master_box.xMin(), tag_y));
	}
	}
	}
	painter->setTransform(initial_xfm);
	}

This is essentially a map reduce paradigm which should be extremely parallel, except that Qt painter objects aren't thread safe. There was discussion in #3279 that the database is not "thread safe", but I think that was in the context of read/write operations and not read-only operations.

Beyond that, each layer is independently but sequentially rendered:

OpenROAD/src/gui/src/layoutViewer.cpp

Lines 2555 to 2599 in 6920ac5

	utl::Timer insts_outline;
	drawInstanceOutlines(painter, insts);
	debugPrint(logger_, GUI, "draw", 1, "inst outline render {}", insts_outline);
	// draw blockages
	utl::Timer inst_blockages;
	drawBlockages(painter, block, bounds);
	debugPrint(logger_, GUI, "draw", 1, "blockages {}", inst_blockages);
	dbTech* tech = block->getDataBase()->getTech();
	for (dbTechLayer* layer : tech->getLayers()) {
	drawLayer(painter, block, layer, insts, bounds, gui_painter);
	}
	utl::Timer inst_names;
	drawInstanceNames(painter, insts);
	debugPrint(logger_, GUI, "draw", 1, "instance names {}", inst_names);
	utl::Timer inst_rows;
	drawRows(painter, block, bounds);
	debugPrint(logger_, GUI, "draw", 1, "rows {}", inst_rows);
	utl::Timer inst_access_points;
	if (options_->areAccessPointsVisible()) {
	drawAccessPoints(gui_painter, insts);
	}
	debugPrint(logger_, GUI, "draw", 1, "access points {}", inst_access_points);
	utl::Timer inst_module_view;
	drawModuleView(painter, insts);
	debugPrint(logger_, GUI, "draw", 1, "module view {}", inst_module_view);
	utl::Timer inst_regions;
	drawRegions(painter, block);
	debugPrint(logger_, GUI, "draw", 1, "regions {}", inst_regions);
	utl::Timer inst_pin_markers;
	if (options_->arePinMarkersVisible()) {
	drawPinMarkers(gui_painter, block, bounds);
	}
	debugPrint(logger_, GUI, "draw", 1, "pin markers {}", inst_pin_markers);
	utl::Timer inst_cell_grid;
	drawGCellGrid(painter, bounds);
	debugPrint(logger_, GUI, "draw", 1, "save cell grid {}", inst_cell_grid);

There may or may not be ordering required on draw calls to these layers, I'm not sure.

I looked at a few Qt guides and they all recommend separating computation from rendering in separate threads for better performance (and interactivity).

I think some of these things were mentioned by @QuantamHD in #1930 but the PR itself seems to be unrelated (and abandoned).

I have some interest in looking into this, but I wonder what the best approach would be for this? Qt has QThread and QThreadPool for this exact purpose. There's also QtConcurrent which may have some uses.

In an ideal world, it seems like there should be a thread pool with getThreadCount()-1 threads and the main thread. The main thread has a render queue which atomically pops the queue for draw calls and does nothing else until all worker threads yield. The worker threads can parallelize at the granularity of layer or instance/shape depending on what's optimal. But this could take a lot of refactoring, possibly be overkill, or possibly be difficult to tune the amount of threading correctly.

An intermediate step could be to simply parallelize some of the heavy-weight tasks that block the GUI thread, such as using std::transform(std::execution::par) or std::for_each(std::execution::par) and separating the draw calls from the filtering. But also these functions don't seem to be well supported on old versions of GCC/Clang (it requires Intel libtbb and may error or just use a serial version if it isn't linked, but I think it also think it doesn't work on Apple silicon). Maybe using OpenMP would work?

Any thoughts or opinions?
@gadfort @maliberty @oharboe @QuantamHD

[oharboe]

After the recent performance improvement, the biggest performance problem currently for us, is that all intermediate zoom levels are rendered #3278

So if that could be fixed FIRST... :-)

Afterwards, the suggestions that you propose sound wicked!

It is true that Qt nor the database is thread safe, then on the other hand, this means that the GUI is single threaded, so I suppose that you are right that you can use as many or few threads as you like as long as Qt nor the database functions are non-the-wiser. Rendering should be especially amenable to this since it is a read only operation...

Also, rendering doesn't have to be perfect. I have been thinking that a draft could be rendered while zooming and then when the user stops giving input, more detail can be rendered.

[rovinski]

I think there's a couple ways to enhance interactivity orthogonally to sheer render performance.

One is to use a cached copy of a render and apply zoom transformations to it. I think this could be as simple as using QPixMap::scaled() to generate intermediate frames while the new zoom level is rendered.

The other is to update the view while the render is still working. This would mean that the display doesn't "hang" until the new zoom level is fully rendered, but instead shows instances, metals, etc. popping in "slowly" when they are rendered.

If these two techniques are both used, you could get something similar to Google Maps where updates pop in as they are ready but the interface stays responsive the whole time.

That would be really cool, but also possibly more than I could handle right now :). I think setting up some kind of threaded infrastructure would be a good stepping stone.

Re: #3278 I wonder if the issue is that the update isn't checked during the render. As Matt mentioned I think the scroll events should get collapsed, but that might still mean that the first render only works off of the first scroll event and then the second render works on all the collapsed events.

[oharboe]

W.r.t. performance, I would be delighted if #3278 is fixed. It is really the last practical obstacle w.r.t. performance, the rest is gravvy.

I always say that there are two universally loved features, get them right and you will have undying loyalty from your users: quality(no bugs) and performance. If it is fast and it works, it is going to be VERY hard to convince users to switch :-)

[maliberty]

@rovinski I've considered all these ideas but lack the time to implement them all. Right now I'm looking at moving the rendering to a separate thread and making it interruptible. The main challenge is figuring out how to trigger the right events at the right time to make Qt happy. It is very particular that you can only paint in paintEvent.

Assuming I can land this then it is more straightforward to split that worker thread into multiple threads. KLayout works in a similar fashion where they render per layer in each thread and composite in the main thread.

[maliberty]

Ideally that's why I'm trying it. Qt is fighting me though...

[oharboe]

But it will be worth the struggle and wait, I think. It is an elegant and generic solution that avoids cruft elsewhere, even if it requires wrestling with Qt and possibly some tricky code.

[rovinski]

I think there are opportunities within a layer as well. There probably needs to be some kind of work stealing to ensure that there isn't one thread bottlenecking the render.

If there's something in particular you want me to look into, I'd be happy to.

[Iyury1]

I also wouldnt mind helping out to implement some of these other ideas now that the renderThread is up and working.

[maliberty]

That would be great. I would start by having each thread render one layer in its own buffer and then composite them in the main thread in order. You'll have to keep the interrupt / restart working across the whole thread group.