Parallel Algorithms for J Programming Language Primitives

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/

Abstract:

A two phase research project is proposed involving the modeling and implementation of parallel algorithms for the primitive operations which constitute the J programming language.

Subject Areas: Modeling Parallel Computation J Programming Language, Parallel Computation.

Keywords: Modeling, J Programming Language Parallel Computation.

1 Introduction

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.

1.1 Modeling

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.

1.1.1 J as a Modeling Notation

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).

Figure 1: J Vocabulary, Part 1
\includegraphics[width=5in]{vocab1.aw.eps}

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.

Figure 2: J Vocabulary, Part 2
\includegraphics[width=5in]{vocab2.aw.eps}

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.

2 The Research Project

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:

  1. Construct parallel models of each J primitive. These models will be written in J. This phase of the project will be completed during the proposed academic leave, Spring semester, 2003-2004.

  2. Construct a portable C implementation of each of the modeled parallel J primitive functions. This phase will begin after the completion of the first phase and requires access to the source code for a recent J release (which I have).

2.1 Computer Science MIMD Machines

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.

2.2 Modeling Methodology

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.

3 Research Qualifications

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.

Bibliography

Burk 2001
Burke, Chris, J User Manual, J Software, Toronto, Canada, May 2001.

Bur 2001
Burke, Chris, Hui, Roger K. W., Iverson, Kenneth E., McDonnell, Eugene, E., McIntyre, Donald B., J Phrases, J Software, Toronto, Canada, March 2001.

How 1998
Howland, John E.,``Recursion, Iteration and Functional Languages'', Journal for Computing in Small Colleges, Volume 13, Number 4, April, 1998.

How 2002
Howland, John E., ``Building Models: A Direct but Neglected Approach to Teaching Computer Science'', Journal for Computing in Small Colleges, Volume 17, Number 5, April, 2002.

Hui 2001
Hui, Roger K. W., Iverson, Kenneth E., J Dictionary, J Software, Toronto, Canada, May 2001.



2002-10-22