celerity / celerity-runtime

High-level C++ for Accelerator Clusters
https://celerity.github.io
MIT License
139 stars 18 forks source link

Add experimental task hints API, support for 2D splits #227

Closed psalz closed 9 months ago

psalz commented 9 months ago

This adds a new experimental::hint API that can be used to provide the runtime with additional information on how to process a task. The first two hints we have are experimental::hints::split_1d and experimental::hints::split_2d. As a 1D split is currently the default, the former is a no-op. For the latter this introduces a new split_2d function that attempts to produce a number of evenly sized chunks while satisfying the provided granularity constraints.

The algorithm works by trying to find two factors for num_chunks, the number of requested chunks, that are as close to sqrt(num_chunks) as possible while also producing the requested number of chunks, degrading to a 1D split in the worst case. Due to granularity constraints it is not always possible to produce the requested number of chunks however, in that case the algorithm will attempt to get as close as possible. Finding the factors requires at most O(sqrt(num_chunks)) time.

Given the two factors, the algorithm uses two heuristics to decide to which side of the domain they should be assigned:

Here's a visual representation of some of the 2D splits from the unit tests. Each split is labelled in the form <size0>x<size1> ~ <granularity0>x<granularity1> | <num chunks>. Red lines represent split constraints (i.e., individual red boxes can not be split further):

image

github-actions[bot] commented 9 months ago

Check-perf-impact results: (3b34e58e3c100f4c3541a1ed59580f72)

:question: No new benchmark data submitted. :question:
Please re-run the microbenchmarks and include the results if your commit could potentially affect performance.

fknorr commented 9 months ago

I noticed that task_manager::submit_command_group has a hints parameter, I guess that's obsolete now.

github-actions[bot] commented 9 months ago

Check-perf-impact results: (4c65f1399a47e0eb1340f63004745b17)

:question: No new benchmark data submitted. :question:
Please re-run the microbenchmarks and include the results if your commit could potentially affect performance.