Wow, this is a tough set of questions! Some initial thoughts:
> How does Legion differ from languages like Halide which separate scheduling from the algorithm?
Yes, that's one of the similarities. Legion, Sequoia, and Halide all share a separation between the specification of the algorithm from the mapping to any particular architecture.
The biggest difference between Legion and Halide, aside from the fact that Halide is much more domain-specific to image processing, is that Legion (being a dynamic runtime system) focuses more on higher-level orchestration of tasks executing in a distributed system.
> How much of this could get handled by PGO (profile guided optimization) to observe locality and access patterns?
Yes, this is called the Inspector/Executor technique. While it's an old technique, the most recent general-purpose implementation that I know of is this paper: [Code Generation for Parallel Execution of a Class
of Irregular Loops on Distributed Memory Systems](http://web.cse.ohio-state.edu/~rountev.1/presto/pubs/sc12.pd...).
The main place where it struggles is memory capacity. It turns out that the profiles, when you're running on large distributed systems, can become very, very large. Keep in mind that modestly sized simulations these days run on hundreds to thousands of machines, and the largest run on tens of thousands of machines. So it's not hard to see why this can be problematic.
> Do you think AI has a place in directing scheduling given enough semantic information so that "bad hypothesis" can get pruned?
Yes. One nice property of Legion's approach to mapping is that no matter what mapping is chosen, the system will guarantee that the computation is still executed correctly. So the worst you can do is make yourself slower.
I think mapping, especially in the distributed setting, is one of the big unsolved problems. For domain-specific settings we have some preliminary answers. E.g. see this paper for how it applies MCMC search to find optimal mapping strategies for DNN execution: [Beyond Data and Model Parallelism for Deep Neural Networks](https://arxiv.org/pdf/1807.05358.pdf)
> Does it rely on a static description of machine (latencies and bandwidth) or does it evolve over time? Can it handle things that are dynamic but are thought of as static like memory bandwidth in a cloud environment?
Legion's model of the machine happens to be static at the moment, because that's the most expedient to implement, but explicitly designed with dynamic behavior in mind. One of the biggest cases is where you lose a machine completely (e.g. because it dies, or your spot reservation gets revoked). I'm not sure if more fine-grained behavior can be exploited in a useful way, e.g. temperature fluctuations in a CPU might very well influence performance, but unless you can predict them I don't see what you can necessarily do about that. For many of these problems, being more asynchronous helps, because at least you can turn latency-limited problems into throughput-limited ones.
> How does Legion compare to cache oblivious techniques?
I'd say that cache oblivious techniques are particular algorithms (or perhaps mapping strategies) that you could implement in Legion, but which Legion is agnostic to. Legion provides mechanism but tries to avoid hard-coding any particular policy.
> Are there changes at the processor level that could fuse operations given the existence of data in the cache, much like hyperthreading can do a context switch on a cache miss.
We don't do this on quite such a low level, but we can do it at higher levels. Mappers can select the ordering of tasks on a processor, as well as the placement and layout of data, which is in theory sufficient to play with this. In the past Legion's overheads were too high to really think about this, but we've made some significant improvements in overhead recently which could allow us to start to think about things at this granularity.
> Do we need to modify what constitutes a Basic Block? Is modern hardware too low level?
I'm not one of them, but I know there are people thinking about this. Can't recall any references at the moment.
In general, I think systems like Legion make us much less dependent on caches. If the system manages data movement in and out of explicitly managed memories, that gives us a lot more freedom to play with the architectures. And increasingly I think we'll need this flexibility if we're going to keep driving performance improvements. As one of my friends once said, "x86 is a platform for making shitty code run fast", but perhaps we don't have that luxury any more.
> Have you read the "Collapsing Towers of Interpreters" paper and do you think it applies to your work?
Haven't read it yet, but it sounds like it shares some ideas with [Terra](http://terralang.org/), which we do use heavily. In fact, the Regent language is built entirely in Terra. In general, these sorts of techniques make it much faster to build new languages, while it's not really in my direct line of research I am very grateful people are working on these things.