Interval() and tile_evenly() are bugged when the size of the interval is less than the number of tiles.

[alobb]

When running the following program,

#include <agency/agency.hpp>
#include <agency/experimental.hpp>
#include <iostream>

int main() {
    const int NUM_TILES = 12;
    auto tiles = agency::experimental::tile_evenly(agency::experimental::interval(0, 9), NUM_TILES);

    agency::bulk_invoke(agency::seq(NUM_TILES), [=](agency::sequenced_agent& self)
    {
        auto this_tile = tiles[self.index()];
        std::cout << *this_tile.begin() << std::endl;
    });
}

the output will be:

256 % ./a.out
0
1
2
3
4
5
6
7
8
9
10
11

Arguably, the code could be seen as broken because some tiles will have no values in them, but it seems like Agency should still be able to gracefully handle this.

Meta:

258 % clang --version
clang version 3.7.1 (tags/RELEASE_371/final)
Target: x86_64-pc-linux-gnu
Thread model: posix

264 % git --no-pager log -1
commit aef3063918e3ee7a8fab0b72b1cb32daf716cf98
Merge: 66436cd 5094314
Author: Jared Hoberock <jaredhoberock@gmail.com>
Date:   Wed Jan 25 14:20:23 2017 -0600

    Merge pull request #337 from jaredhoberock/issue-336

    Use public links to repositories for submodules

clang++ -g -std=c++11 -I./agency/ main.cpp

[jaredhoberock]

Thanks for the report.

What do you expect to happen when more tiles are requested than there are elements to begin with?

[alobb]

I would expect that, if we have x tiles and a length y interval, the first y tiles each contain 1 point in the interval, and the last x - y tiles are empty. However, this is certainly not what is expected by tiling where you would normally have a bigger interval than number of tiles. I would understand not coding it this way, but in that case, it would be helpful for Agency to check that the number of tiles and size of interval is valid.

[jaredhoberock]

Thanks for the explanation. I agree that introducing empty tiles would be one way to produce a result, but one problem with that solution is that the result is no longer tiled "evenly" -- some portions of the result have elements, and other portions are empty. Another problem is that it's not immediately clear to me whether there is a way to implement that result that would be as efficient as the current solution, which takes advantage of the assumption that all tiles have the same size, except for possibly the last tile of the result.

Also, if one is creating execution based on the tiling as you are, one might prefer not to create agents (a potentially expensive operation) for empty tiles.

For what it's worth, tile_evenly(range, num_tiles) is essentially intended to be shorthand for tile(range, (range.size() + num_tiles - 1) / num_tiles). When the denominator of this division is too big, the behavior is essentially undefined.

Do you think it would be reasonable for tile_evenly() to check its parameters and throw an exception if the choice of parameters cannot produce a tiling?

[alobb]

That seems like a reasonable thing to do, but I thought of another possible solution: you could change the number of tiles to be the size of the range if the range is smaller than the number of tiles given by the user. Although this implicitly hides the configuration of tiles from the user, this should be an exceptional case. Additionally, this avoids creating redundant agents.

[jaredhoberock]

Thanks for the suggestion. I agree that producing a valid tiling in this case is a better option, and should be just as easy to implement. I've filed #339 to track this issue separately.