John E. Howland
Department of Computer Science
Trinity University
715 Stadium Drive
San Antonio, Texas 78212-7200
Voice: (210) 999-7364
Fax: (210) 999-7477
E-mail: jhowland@Trinity.Edu
Web: http://www.cs.trinity.edu/~jhowland/
Subject Areas: Modeling Parallel Computation J Programming Language, Parallel Computation.
Keywords: Modeling, J Programming Language Parallel Computation.
A computer is a mechanism for interpreting a language. It interprets (performs the actions specified in) sentences in a language which is known as the computer's machine language. It follows, therefore, that a study of the organization of computers is related to the study of the organization of computer languages.
Computer languages are classified in a variety of ways. Machine languages are rather directly interpreted by computers. Higher level computer languages are often somewhat independent from a particular computer and require translation (compilation) to machine language before programs may be interpreted (executed).
In computing there is an insatiable desire for speed because of the existence of problems for which practically computable solutions have not been found. Much research in the area of parallel computing has focused on the problem of designing parallel hardware. SIMD (Single Instruction Multiple Data) machines, for example, use multiple processors all executing the same instruction in synchronism on different data. MIMD (Multiple Instruction Multiple Data) machines, use multiple processors executing perhaps different instructions on different data. There exist a wide variety of other parallel computing designs such as vector machines, etc. Each parallel hardware design requires unique programming to properly utilize the parallel features of the hardware. Much research has focused on the problem of utilizing existing programs in languages such as FORTRAN or C on parallel machines, but this research has not achieved desired results unless parallel features of a particular hardware design are added to FORTRAN or C but this requires the existing programs to be re-written in order to use such features.
Other research has focused on developing new parallel languages for use on a particular type of parallel machine. This research is successful in making good use of a particular parallel machine, but requires new programming rather than using an inventory of existing programs.
This research proposal involves developing a MIMD
parallel implementation of the J programming language. J is a
very high level functional programming language which allows application of
functions to data in aggregate rather than on an element by element basis.
This fact makes J programs free from the low-level details of item by item
computation. For example, to sum and array of numbers a
, the
program +/a
is used. This program is free of details such as whether
the sum is accumulated from first to last or last to first or even whether
some parallel approach is used to complete the summation. Because J programs
do not contain such details, they do not need to be re-written in order to
achieve high performance on a parallel J machine.
The proposal involves two phases of first modeling how each J primitive function may be performed in parallel on a MIMD machine and second providing an efficient implementation of the parallel J primitive. At the heart of the research is the discovery of (if possible) MIMD parallel algorithms for each J primitive function.
The end result of this research, if successful, would be to provide a parallel implementation of an existing programming language so that the performance of already existent programs can be significantly improved without requiring any changes to the programs.
In this proposal, the term modeling is used in the context of software modeling, as in parallel models of each J primitive implemented as programs (or program fragments) in some programming language. It is proposed that the J language itself be used during the modeling phase of this project.
The J programming language [Burk 2001,Bur 2001,Hui 2001] is, perhaps, the only programming language which satisfies
the criteria of software modeling developed
by Howland in [How 2002]. J uses infix notation with primitive functions denoted by
a special symbol, such as +
or %
, or a special symbol or word followed by the suffix of .
or :
.
Each function name may be used as a monad (one argument, written to the right) or as a dyad (two
arguments, one on the left, the other on the right).
The J vocabulary of primitive (built-in) functions is shown in Figures 1 and 2. These
figures show the monadic definition of a function on the left of the *
and the dyadic
definition on the right. For example, the function symbol +:
represents the monad double
and the
dyad not-or
(nor
).
J uses a simple rule to determine the order of evaluation of functions in expressions.
The argument of a monad or the right argument of a dyad is the value of the entire expression
on the right. The value of the left argument of a dyad is the first item written
to the left of the dyad. Parentheses are used in a conventional manner as punctuation
which alters the order of evaluation. For example, the expression 3*4+5
produces
the value 27
, whereas (3*4)+5
produces the value 17
.
The evaluation of higher level functions (function producing functions) must be done (of course)
before any functions are applied. Two types of higher level functions exist; adverbs (higher level
monads) and conjunctions (higher level dyads). Figures 1 and 2
show adverbs in bold italic face and conjunctions in bold face. For example, the conjunction
bond (Curry) binds an argument of a dyad to a fixed value producing a monad function as a result
(4&*
produces a monad which multiplies by 4
).
J is a functional programming language which uses functional composition to model computational
processes. J supports a form of programming known as tacit. Tacit programs have
no reference to their arguments and often use special composition rules known as hooks
and forks. Explicit programs with traditional control structures may also be written.
Inside an explicit definition, the left argument of a dyad is always named x.
and the
argument of a monad (as well as the right argument of a dyad) is always named y.
.
J supports a powerful set of primitive data structures for lists and arrays. Data (recall that functions have first-class status in J), once created from notation for constants or function application, is never altered. Data items possess several attributes such as type (numeric or character, exact or inexact, etc.) shape (a list of the sizes of each of its axes) and rank (the number of axes). Names are an abstraction tool (not memory cells) which are assigned (or re-assigned) to data or functions.
This research project will develop a parallel implementation of the J programming language for MIMD machines. This is a very large project which may take a couple of years to complete. The research will be done in two phases:
Any parallel processing research project necessarily needs access to parallel computing facilities. The Computer Science Department has excellent facilities for this research project. No additonal funding for laboratory equipment will be needed to complete this research project.
MIMD machines contain multiple interconnected processors which are capable of simultaneous execution of separate programs on separate data. The Trinity Computer Science Department has several MIMD machines which may be used during the modeling phase of this project. SnowWhite is a 4 processor machine where the processors are interconnected by a 4GB shared memory. The 7 Dwarf machines are seven 2 processor machines where each pair of processors are interconnected by a 1GB shared memory and each of the machines is interconnected by a 100Mbit/sec Ethernet switch. The Prometheus cluster is a collection of eight 2 processor machines (each pair of processors connected by shared memory) and each of the machines are connected by a 1Gbit/sec Ethernet switch. The Xena cluster is a collection of 22 one processor machines connected by a 100Mbit/sec Ethernet switch. The Janus cluster is a collection of 22 one processor machines connected by a 100Mbit/sec Ethernet switch. All of the Computer Science Department Unix machines are networked in such a was as to allow any of the above machines or clusters to be combined to form a larger MIMD machine.
Parallel computation on a MIMD machine involves decomposing the work done in an algorithm into parts which are distributed to separate processors for simultaneous execution, then the partial results must be retrieved from the separate processors to assemble the final result. MIMD computation involves an execution-time versus transportation-time (TT) trade-off. After decomposition, there must be (in relation to transport overhead) enough speed-up from the parallel portion of the computation to warrant the extra overhead of transportation of the algorithm parts to the various MIMD processors. Transportation may be accomplished more efficiently with shared memory than with Ethernet or shared file-systems. Both types of transportation overhead will be modeled.
Figures 1 and 2 show the primitive spelling for each of the primitive functions which make up the J programming language. There are approximately 240 functions which must be considered. The problem is separable by function allowing separate models for each function. The project in total is quite large, but the separability opens the possibility for research participation by undergraduate students. It is my intention to involve as many interested undergraduate computing science students in this project as possible.
A modeling infrastructure tool set will be developed which may be used for the modeling of each primitive. Recent versions of J provide a network socket interface and protocol to provide access to a J system running on another processor on the network. This socket interface will be used in the modeling tool set which will also include execution-time and transport-time measurement tools.
Prior work in parallel algorithms will apply to some primitive functions.
For example, parallel matrix multiplication of large or sparse matrices
has been studied. Matrix multiplication is a derived function from the
conjunction .
dot product as +/ . *
. With large
matrices, the inner products of rows of the left argument and columns
of the right argument may be computed on different processors
because the inner product computation is significant in relation to
the transport time. However, the J matrix product generalizes to higher
rank arrays, so that it is not obvious that this approach will generalize
to higher rank arrays. Moreover, the parallelism may need to be
done at the conjunction (rather than derived function ) level so as to
apply to other useful products such as +./ . *.
.
J conjunctions and adverbs (verb producing verbs) must be analyzed on a case
by case basis when discovering parallel algorithms. For example, the
adverb /
(insert) simply derives a new verb as in +/
(sum)
or */
(product) and there is no need to this simple derivation
on more than one processor. However, the rank conjunction, "
derives a new verb which is applied to the cells of a specified rank
in its argument. For example, +/ "1
sums the 1 cells of its
argument while +/ "2
sums the 2 cells of its argument. These
two cases require different parallel algorithms.
Certain other primitive J functions pose a special challenge to discover
MIMD parallel algorithm. For example, the monad q:
, prime
factors, computes the prime factors of its argument. Parallel factoring a very
large number (thousands of digits) will probably require a different algorithm
than factoring of thousands of smaller numbers.
The researcher has worked in the area of application of functional languages for more than 35 years. This work includes the APL language and since 1991, the J functional language. His use of J is recognized in the US, Canada and Europe.