magnatelee
commented
4 years ago To make the discussion concrete, let me describe a typical scenario that could be greatly simplified with deferred binding of bounds to regions:
Launching Legion tasks that potentially produce outputs of different sizes involves the following steps:
- Computing (or estimating the upper bound of) the size of the output for each parallel task. We often need to launch another set of tasks to do this counting if the counting needs to access data. (e.g., filtering values with a predicate)
- Determining bounds of output subregions. This requires a prefix sum of the result from (1)
- Creating an output partition using the bounds from (2)
- Launching computation tasks in parallel using the partition from (3)
The first three steps are just to set up the output partition and the amount of computation involved is often very light. Furthermore, there can be duplication of work in steps (1) and (4) because counting in (3) often cannot be done without performing some or even all computation in (4).
With proper runtime support, steps (1)-(4) can be simplified to the following two:
a. Launching computation tasks that take subregions with unspecified bounds. Each task allocates elements incrementally in its output subregion. When the tasks are done, each subregion is only locally consistent, i.e., has 0 for its lower bound. b. Shuffling subregion bounds across all tasks to recover global indexing. This is a prefix sum as in step (2) but performed inside the runtime.
This simpler strategy requires more than just deferred binding of bounds. Here are relevant runtime mechanisms:
i. Deferred binding of bounds to index spaces (this issue) ii. Regions that have index spaces with unspecified bounds. These regions are mapped to a special kind of Realm instances in (iii) and provide allocators (similar to those that we used to have for unstructured regions a long time ago). iii. Realm instances providing malloc-like allocators. Region allocators in (ii) will be backed by these Realm allocators. iv. Pending partitions of index spaces having unspecified bounds. Subspaces of this pending partition also have unspecified bounds. v. A prefix sum or something to that effect to recover global indexing as in (b). This is necessary only when there are parallel tasks producing outputs with the pending partition in (iv).
One of the things to be discussed is when we should recover global indexing (step (b)). One way would be to simply let the user initiate the recovery. Another option would be to couple it with the task life cycle, for which we need these simplifying assumptions:
- Every pending partition of an index space with unspecified bounds must be complete. This is to guarantee that the tasks that allocate indices using this partition can solely determine the bounds of the subspaces and also of the parent index space.
- An index task taking such a pending partition must be complete as well, i.e., has the color space of the pending partition as its launch domain.
- No single task can take a subregion of a partition whose parent region has bounds that is yet to be determined. Single tasks that are dominated by some preceding index task determining the bounds are acceptable.
Obviously, I left out a lot of details here, so any comments or questions are welcome.
lightsighter
In order to deal with tasks that produce unknown sized output, it would be nice if we could create the names for index spaces and logical regions without having to specify their size up front and then later bind the size as part of a task when it is mapped either inline or as a sub-task. The idea would be that index spaces and their associate regions do not actually need bounds until they are mapped for the first time. Doing this could potentially create cycles and therefore is not something that we should take lightly. Assigning @alexaiken to think through an initial design.