We tossed this back and forth among ourselves probably longer than we should have....
> Dear Fortress Development Team,
>
> I have been working recently on surveying some of the challenges facing new programming languages for large (petascale->exascale) systems and I was hoping to get some feedback from the Fortress team on some of the challenges Fortress will face at this scale. I appreciate the team are very busy but I would be most grateful if you could spare a few minutes to provide some insight into some of these challenges. I hope to compare various programming languages and models to see where they are heading with respect to HPC and upcoming architectures over the coming decade.
> For this discussion I am assuming that the next-generation systems will comprise many distributed nodes where each node is represented by a single address space (at least that is the trend I tend to hear most often).
Thanks for your inquiry.
At present, Fortress is not currently focused on high-end, distributed-memory computing. Fortress started within Sun's HPCS activities and operated in conjunction with teams looking at hardware design. Sun's eventual proposal was for a petascale supercomputer that would in fact support a single petascale address space (that is, at least 50 address bits) in hardware. We believed as a matter of philosophy, and still believe, that the single-address-space model makes application programmers more productive overall. We did not, and do not, believe that complete hardware support for a single address space is an absolute requirement, but only an engineering trade-off; if this model is not provided by hardware, then it can be simulated by software, perhaps with hardware assistance. MPI or something like it might well play a role in some implementations of this lower-level infrastructure.
At present, however, the focus of the Fortress project has shifted more towards "volume" computing. There is no novel, petascale system that we are targeting right now. While many of the design features of Fortress may indeed eventually prove useful at large scales, we are exploring whether these same features might make programmers more productive on multicore computers and multicore clusters. Out current compiler effort is targeted to a single JVM instance; to the extent that any given single JVM implementation makes multithreading available, our Fortress implementation will endeavor to exploit it. We hope someday to explore the utility of our original design for (semi-)automatic management of data distribution within this framework to address the issue of non-uniform memory access times.
Fortress does have some important, high-level design philosophies that are immediately relevant to your inquiry:
*) Fortress is designed to encourage programmers to expose and exploit concurrency.
*) The language is designed to be growable, and we anticipate much functionality to be supplied by add-ons writen as Fortress source code.
> 1. Do you expect that Fortress is sufficient to develop complete applications when scaling to these large system sizes (for instance 10^5-10^6 cores, with 10-100 threads per core) or do you envisage it being coupled with some message passing technology (e.g. MPI) to pass data between nodes? If you believe MPI will be required, has there been any progress towards interfacing Fortress with MPI and what sort of further challenges does this pose?
Our goal is to do for multithreading what garbage-collection technology has largely done for data allocation except at the very largest scales: to relieve the programmer of the burden of explicitly mapping parts of the program onto specific hardware resources. The problem with MPI is that its very model requires the programmer to be aware of, and to manage, this mapping. Such explicit management is appropriate and necessary when a phase of technology is in its early stages, or when absolute maximum performance is demanded, despite the tremendous cost in programmer effort.
When the C language, and its implementation technology, was in its infancy, it was necessary to have "register" declarations so that programmers could control the mapping of local variables to specific hardware resources. Five to ten years later, we reached a stage where only "mediocre" compilers obeyed these directives: low-end compilers didn't even know what to do with them, and the best compilers nearly always did a better job of register allocation than most programmer could using the directives. Nowadays the C "register" directive is all but forgotten.
We believe that programmers will be more productive when we reach the point that compilers nearly always do a better job of mapping program segments to processors/cores/threads (and data structures to memory regions) than most programmers could. The reason we think this day will come is that the strategies for improved resource management are becoming ever more complicated, to the point that understanding them and using them effectively will be beyond the reach of all but the most expert programmers in this speciality; most programmers will be more productive in letting a compiler and runtime system manage these resources automatically, even if the result is somewhat less than the theoretically achievable optimum, because it will free up their time and expertise to focus on other (application-related) difficulties. Back in the day when the algorithms of interest were applied to a small number of uniform, dense, contiguous, multidimensional arrays, and the optimization strategies consisted primarily deciding (a) which dimensions to decompose for parallel processing, (b) whether to do so in block, cyclic, or block-cyclic fashion, and (c) whether to use shadow borders as a strategy for managing interprocessor communication, then this design space was (barely) manageable by application programmers. As we are increasingly relying on multiple heterogeneous, sparse, irregular data representations with dynamically changing processing orders and communication relationships, the optimal strategies will be too complex to be worth managing "by hand" in all but the most critical cases.
> 2. To exploit parallelism at such scales, applications will need to uncover large amounts of concurrency. Which features of Fortress will allow programmers to do this naturally?
Parallelism almost by default. The default behavior of "for loops" is parallel, depending on the data structures that are "iterated" over. The defined behavior of parameter lists and operand parameters is parallel-evaluation-allowed. There are several constructions that process data aggregates elementwise. We believe in data parallelism as a programming strategy, with the understanding that (1) control parallelism lies underneath and is available; (2) data parallelism and control parallelism can be freely nested, both separately and with each other; (3) atomic blocks (implemented through optimistic transactional memory mechanisms) are available for managing concurrent update, and may also be freely nested; and (4) load balancing of work among hardware threads is performed automatically.
Example: let x be an array of many data items. The Fortress expression `SUM[a <- x] (if a > 0 then f(a, b) else g(a, c) + h(a, d))` specifies that (i) the items of x may be processed concurrently (data parallelism); (ii) for each item, we can choose one of two computations, and it is if not necessary to wait for executions of f to complete before computations of g and h can begin (data parallelism need not be SIMD); (iii) if we should choose to execute g(a, c) + h(a, d) for some item, then it is permitted to execute g(a, c) and h(a, d) in parallel, which may be useful if additional hardware parallelism is available; (iv) f, g, and h may further specify and exploit data parallelism, control parallelism, or both, and may use atomic blocks to manage concurrent access (for example, they might all concurrently access a shared hashtable containing memoized computations); (v) if one or more of these subcomputations produces an exception, then a single exception is delivered from the entire construct after automatically reining in all outstanding concurrent subcomputations that were spawned for the overall expression; and (vi) the results of all subcomputations are automatically added up and the sum is delivered as the final result of the expression, assuming no exception has occurred.
Note that the SUM operator is not built into the language. A programmer may define any binary combining operation and use it in this syntactic construction, and such an operation may combine arbitrarily complicated data structures, not just numbers. Provided that the operation is declared to be associative, then parallelization strategies automatically come into play to perform the combining step treewise rather than in sequential order.
The standard Fortress library provides support not only for arrays but for trees, lists, sets, multisets, and maps. All support multiple standard strategies for parallel processing. Policies such as whether there should be a minimum data chunk size, beneath which you are better off processing sequentially rather than spawning further threads, are explicitly under the control of the library code, which is to say, that it can be modified by rewriting Fortress source code---such policies are not buried in the compiler or the runtime system.
> 3. Movement of data will become even more expensive due to power concerns. Which features of Fortress allow programmers to manage data locality within complex memory hierarchies? How does Fortress plan to overcome the challenges of co-locating and distributing tasks and data at large scales (with many co-operating tasks)? What are there challenges in providing address translation (global to local mappings) and/or managing synchronization at such large scales?
The design of Fortress, dating from its DARPA HPCS days, includes a data structure that serves as an abstract hierarchical description of processor and memory resources. Data structures and threads can be explicitly mapped onto hardware resources by writing code to perform this mapping. In this way Fortress goes beyond HPF, which provided only a fixed, nonextensible set of data distribution strategies. On the other hand, it is our hope that this mechanism will serve only as a temporary platform for research and exploration, and that someday it will become as outmoded as C "register" declarations.
> 4. Are there plans to support possible heterogeneity within nodes in Fortress? If so, which features of Fortress can be used drive accelerator devices such as GPGPUs for instance?
No particular plans either for or against heterogeneity. This is more of an implementation issue than a language issue. We do understand that the availability of specialized computational hardware such as GPUs makes the problem of mapping computations to hardware resources substantially more difficult. We have not put in much effort on this problem. We do believe, however, that the hardware-description data structure described in our answer to the previous question can provide a framework for exploring these questions in an extensible, user-programmable manner.
> 5. If a new OS is required to support applications on novel Exascale systems would there be much effort required to adapt Fortress?
As the record of our proposals under the DRPA HPCS program will show, we believe strongly in virtual machines with dynamic runtime compilation. This gains a measure of independence from hardware and operating systems while allowing code to be optimized in response to actual runtime behavior rather than just compile-time predictions of behavior.
Right now we are targeting our first Fortress compiler to the Java Virtual Machine. We have some ideas about how an improved virtual machine might better support the Fortress type system and thread model.
> 6. Will Fortress provide features for (1) application fault-tolerance and (2) adaptive load-balancing at runtime?
We have not thought very hard about application fault-tolerance, except to note that operations like incremental checkpointing have a lot in common with the implementation of both garbage collection and transactions -- and that given Fortress's laissez-faire approach to parallelism, and support for transactions in access to shared memory, that fault-tolerance would not be a bad fit. Adaptive load-balancing has been a central part of our implementation strategy from the beginning. The Fortress interpreter has been using adaptive work-stealing for years, and the compiler, though not yet finished, has been demonstrated to use this same work-stealing framework (which, however, has not yet been tuned to better serve compiled code).
> 7. Will support of parallel I/O be a core part of the Fortress language?
Fortress has no core parts :-). It's all in the library, and parallel I/O would fit perfectly there. At present, all I/O is implemented through call-outs to Java code through a foreign function interface.
> 8. How will Fortress propose to interoperate with other languages/models? Does it make sense to be able to mix Fortress with UPC/CAF/Chapel/X10 for instance?
We think interoperation is very important, but it's potentially very hard depending on how the languages match semantically. The language-level problems that we worry about are differences in the threading model (work-stealing, for example), differences in the memory model (single address space, or not? transactional, or not?), and differences in data structures (what's an "array"?) We have not yet spent much effort studying interoperability with UPC/CAF/Chapel/X10. We have spent a great deal of effort working out interoperability with Java.
--
And to add a minor bit of context, that we probably take for granted; we think that dynamic compilation, in the style of HotSpot, is the way to get good performance. Cross-module inlining is taken for granted; specialization of generics is expected, that sort of thing. Dynamic compilation is not required to get this -- it can be done in a static compiler -- but it leads to tools that are generally more usable (some of us have worked on systems that compiled Java bytecodes ahead-of-time that attempted to inline as aggressively as HotSpot, and it makes for long compilations, and requires automated optimizer-dependence-checking infrastructure).
In addition, when we say "in the library", we are not just referring to packages of subroutines. It's our goal to encode properties like Associative, Commutative, HasIdentity in the type system, and to transform code, either in the optimizer, or through overloading-driven code selection, to take advantage of this. An optimizer that only understands machine instructions and registers is not going to make much of a dent in domain-specific languages; ideally, we want to be able to express (in the library) things like "matrix multiplication is associative but not commutative" and "the distributive law holds for regular expressions" (that is, e1e2|e1e3 = e1(e2|e3) ).
This is pretty much what we are working on right now -- we have tested these ideas in the interpreter, and now we are trying to implement them decently enough (for a first compiler) in the compiler.