Bjorn Lisper wrote:
A guess is that the first generation will support a shared memory model much like SMP:s of today (shared main memory with on-chip cache(s), or some other kind of local memory (-ies)). Here, I think implicit parallelism in functional languages can be a win in some situations. This is provided spawning of parallel threads is cheap and local memory can be efficiently utilized (so control of granularity is no problem, and dynamic parallelism is cheap). Cheap threads is likely to be true, efficient use of local memory is a question mark.
You only need one thread per CPU-core, so the spawning threads cost is a red-herring. Just like GHC schedules haskell-threads from a single OS-thread.
However, some obstacles:
Laziness, if used strictly (sorry) gets in the way for parallelism. Waiting to spawn a parallel thread until we surely know it's result is needed, if it is anyway needed 99% of the time, is not an optimal strategy. I think optimistic evaluation strategies a la Robert Ennals can be helpful here. But designing them to work for new parallel architectures may be non-trivial. I think there can be material for PhD theses here.
I suggest speculative execution, as used by current CPUs to take advantage of multiple microcode execution units. If the a CPU has spare capacity, functions whose results might be needed are run. As soon as you know a result is not needed the thread can be killed, and the time used for something else. A lot of work has already been done on hardware superscalar-architectures, and a lot of this should be applicable to the software case.
If the program implements an inherently sequential algorithm then parallelism won't help anyway. The use of lists often leads to sequential algorithms: a prime example is list folds, which all translate the linear spine structure of a list into a sequential dependence graph of the resulting computation. Folds over tree-like structures are better in this regard. The FP community will have a problem with legacy code using inherently sequential computations over lists. There has been quite some research on how to parallellize list computations (skeletons, program transformations using BMF,...). However, they typically rely on knowing the length of the list. In a lazy language it is common that lists are evaluated dynamically, and then it's hard to use these techniques efficiently. Again, speculation may help.
But in the worst case its just a sequential computation, so any gain from parallelism is still a gain... also the dependant part of a loop is often separate from an independant part... For example consider a list of strings, and taking the length of each string. The next iteration does not have to wait for the length to be computed, it can start the next length computation as soon as the pointer for the next list cell has been dereferenced.
In the long run, as hardware dimensions shrink even more and communication becomes relatively even more expensive, it is likely that we will have some kind of on-chip massively parallel, mesh-connected distributed memory machine. This will most likely favor static parallelization techniques, which means only for certain classes of functional programs an automatic approach with implicit parallelism will work well.
The next generation of CPUs seem to be using a shared cache architecture, so overheads are extreemely small... Erm, by static I assume you mean programmer specified parallelism. I would tend to think of static parallelization as something that takes place at compile time (and would still count as implicit). Keean.