FIDIL(ID:1396/fid001)Array based language with domains and regions as first class elementsfor FInite DIfference Language Array variant of fortran with first class regionsLawrence Livermore Labs Based on "maps", generalized arrays whose index sets ("domains") are arbitrary d-dimensional sets. Domains are first-class objects and may be constructed by union, intersection, etc. Maps in turn based on Hilfinger's array/map extensions to Ada under the supervision of Shaw at CMU, and leading in turn to the Titanium Java array/map extensions Places People: Structures: Related languages
References: in Grossman, Robert (ed) Symbolic Computation: Applications to Scientific Computing, SIAM, 1989 view details Extract: Overview of the FIDIL Language Overview of the FIDIL Language The FIDIL language is one response to the programming difficulties caused by the increasing complexity of modern algorithms in computational fluid dynamics (CFD), and by the subtleties of achieving high performance from a diverse set of modern supercomputer architectures. When, for example, a modern two-dimensional adaptive mesh-refinement scheme, describable in a few pages of mathematics, becomes 10000 lines of FORTRAN, it becomes difficult to experiment with simple variations on the method, and nearly impossible to consider moving to three dimensions. These problems multiply if one wants to maintain such a program over a variety of architectures. To address these problems, the FIDEL language provides two extensions over languages currently popular for scientific computation. First, it incorporates modern capabilities for defining operators and for performing "higher-order" operations upon functions. Second, it extends the usual notion of array types to provide arrays with more general index sets. The result, we think, is well-suited to the needs of scientific programmers who work with linite-difference and particle methods. Furthermore, because FIDIL programs are explicitly formulated in terms of operations upon entire arrays, we believe lhat it will be feasible to compile FIDEL for disparate architectures with little source-code modification required. In this paper, we will concentrate on implementation issues in the implementation of the array data structures in FIDIL. Section 2 gives a very brief overview of FIDIL's array-related features. The language is described in more detail elsewhere [6, 5]. The rest of the paper is devoted to implementation. Extract: Relevant Language Features Relevant Language Features In most ways, FIDIL is just another strongly-typed language in the Algol Inniily. I'or the purposes of this paper, the essential differences arise in its liviilment of arrays. In conventional procedural languages, arrays have index sets dial are fixed no later than the time of their creation and that consist of rectangular sets of integer tuples. FIDEL arrays are generalized into what we call maps. At any time, an n-dimensional map has an index set (called a domain) that is an arbitrary set of ra-tuples of integers. Domains are themselves legitimate data values; they (and thus the index sets of maps) may be data-dependent, computable only on execution of the program. A map variable may be flexible, in which case its index set may change dynamically. The notation "[D] T" (used in variable or parameter declarations) denotes a map type with domain D and codomain (element type) T. Thus, [ 1 .. 10, 1 . . 10 ] real U indicates that the variable U is a 10 x 10 array of reals. The notation " [*n] '/'" in a parameter declaration indicates a map with any n-dimensional domain and codomain T (' [*1]' may be abbreviated '[]')? The modifier "flex" in front of an array type indicates that the domains of instances of that type may vary. Maps and domains may be stored in variables, passed as parameters, returned as values, or stored as fields of structures. The language contains a rich set of generic operations upon maps and domains, some of which are summarized in tables 1 and 2. For computational purposes, one of the most significant operations is the functional operator ' @'. If F is a function on reals that produces real values, for example, then F @ denotes a function operating on maps of reals and producing maps of reals, defined by extending F to apply pointwise to the elements of a map. Technically, F @ is overloaded to denote a family of such functions, one for each possible arity of the map arguments. If G takes two arguments, then G'@ takes two maps and returns a map. To resolve the issue of what to do when the domains of the two arguments to G@ differ, FIDIL defines G@ (X, Y) to 159 produce a map whose domain is the intersection of those of X and Y. We have found this to be the most convenient definition in practice. The standard arithmetic operators are all overloaded with instances that behave as if '@' had been applied. Thus, given the variables [ 1. .10, 1. .100 ] real A; [ 1. .100, 1. .10 ] real B; the expression A+B produces a 10 x 10 map value containing the sums of corresponding elements of A and B whose indices are between 1 and 10. As a further convenience, the arithmetic operators will also take a mixture of scalar and map arguments, with the obvious meaning. The array features of FIDIL are similar to those of several other languages that have been proposed for scientific computation. APL is perhaps the best-known example of a language that allows the direct manipulation of arrays as complete entities, and provides functional operators that can in principle be applied simultaneously over all elements of an array. FORTRAN 8X [1] and Actus [7] are two languages that also provide for concise descriptions of operations over entire arrays. Both of them, like standard APL, concentrate on rectangular data structures. Connection Machine Lisp [8] has an even more general array structure than ours (the index sets may be arbitrary sets of Lisp objects). It is not clear, however, what effect this generality will have on performance. For CFD algorithms, at least, it is reasonable to restrict ourselves to uniform sets of integer tuples. Extract: Elementwise Operations on Maps Elementwise Operations on Maps The implementation of maps, and elementwise operations on them, must obey two constraints: good vectorization and efficient use of memory. The typical application that FIDIL targets runs for a long time on supercomputers, spends most of its time doing vector floating point computation, and it does a lot of dynamic allocation of large data structures. To make it easier to optimize the use of memory, a sequence (the part of a map that contains its data) is not stored sequentially in memory, but it is broken in chunks with a fixed maximum size. The technique we use to implement elementwise statements is called chunk-by-chunk evaluation. The compiler identifies groups of consecutive elementwise statements with the same execution domain1, and it translates them into two nested loops: an outer loop that iterates over chunks, and a vectorizable inner loop that iterates over all elements of a chunk. In the general case (e.g. the operands have domains with different shapes), the outer loop aligns the operands' elements by copying them into temporary chunks with calls to run-time library routines. The run-time system recognizes several opportunities for optimizing this scheme by eliminating the extra copy: for instance when the operands have the same domain as the statement domain of execution; or when they have simple shapes, and the alignment can be achieved by fiddling with the iteration bounds. We are considering a future improvement to this scheme that would handle several reshaping operators better, such as the scaling operators contract and expand. The improvement consists in combining the chunk-by-chunk evaluation with delayed evaluation techniques proposed for the compilation of APL programs [4, 2]. We call the resulting combination lazy chunk-by-chunk evaluation. in Restifo Mullin, Lenore M. et. al., (eds) "Arrays, functional languages and parallel systems" Kluwer Academic Publishers, Boston, MA, 1991 view details |