Title: Automatic Support for Irregular Computations in a High-Level Language
Introduction and problem statement
Titanium is a parallel language which tries to abstract away some complexity of parallel algorithms especially for high performance scientific computing applications. The idea of designing this language goes back to early 90s in a research group in Berkeley computer science department.
The main characteristics of this language are:
- A dialect of Java
- Single program multiple data scheme
- Data types for multi-dimensional arrays (Java does not have this support)
- Unordered “for each” loop constructs which is suitable for parallelization and optimizations
- Explicitly partitioned Global addressing
Java was selected as the base language probably because it was the state of the art language at the time of designing Titanium and has runtime environment. Although the parallel constructs can be abstracted using libraries supporting them in the language directly make the programming environment composable and cross optimizations possible. Titanium translates the code to C language which consequently will be compiled to executable binaries.
There are two other popular languages with the same objectives which are Fortran Co-array, and UPC (Unified Parallel C). Although the Titanium has nicest feature set the UPC has more popularity. There are other parallel languages based on Java like Fortress and X10.
Intended users The main users of Titanium are high performance scientific application users.
What is unique about the suggested solution?
- Using the inspector/executor model to select the best communication model at run time.
- Compiler directed (transparent to the user) communication mode selection.
- Using analytical performance model to choose the right communication method.
- Using three different communication modes (Packed, Bounded, Bulk).
Language evaluation
Because of the lack of measurable programmability metrics evaluating a programming language is not a straight forward process. Some simple metrics could be the number of program lines or number of program symbols for a given algorithm. A part of a study named HPCS (High Productivity Computing Systems) showed that these simple metrics have a good correlation with more sophisticated yet hard to measure evaluation metrics. The problem for evaluating the parallel languages is harder because of the limited number of users for such languages. A paper published in 2006 compared the programmability of OpenMP with MPI and surprisingly found MPI a little bit more programmable.
PGAS(Partitioned Global Address Space)
PGAS is the Titanium memory space organization. The baseline for this memory organization is distributed memory. Specifically in a distributed memory environment like MPI a global name is a pair of (Node id, Local address in node) however in PGAS a global name is accessed through an array index which will be translated to node id and local index number. The translation rule is specified mostly static by programmer (and compiler). Programs have local portion of memory which is only accessible just by them as well as global portion which is shared between all nodes. The consistency model of shared data is preserved only across synchronization events. Unlike MPI which is only supporting two-way communication Titanium supports one-way communication too.
Inspector/Executor model
Running programs in Inspector/Executor model consists of two phases which are inspection, and execution. This model is a powerful tool especially for performance optimization of scientific applications. Consider the following code:
for(i=1..N)
f(A[B[i]]);
It can be reformed as:
for(i=1..N)
C[i] = A[B[i]];
for(i=1..N)
f(C[i]) ;
Since the address of array elements are not determined before executing the loop, optimizations like pre-fetching the A elements and/or selecting the best communication method (packed, bounded, and bulk) are not possible in the first code. By separating the communication part from computation these optimizations are possible enabling the runtime system to do the inspection phase before real execution. In the proposed technique in the paper this transformation will be done automatically by the compiler.
The programming model in Titanium is very similar to stream processors in which optimizations by programmer for data movements in order to hide the communication cost is possible.
Communication cost model
In the proposed method in the paper the communication cost are predicted using an analytical model for each of the three communication methods. Based on estimated costs the method with lowest cost will be selected.
Evaluation
The compiler platform and runtime environment are evaluated using sparse matrix multiplication on three different machine platforms for different types of sparse matrixes. The machine platforms are:
- RTC-Linux Cluster
- Seaborg-IBM
- Lemieux-Compaq
One experiment has run using garon2 matrix to show the difference between the optimization policies Titanium can do which are:
- Pull
- Push bound
- Push pack
- Push model
- Push model/overlap
This experiment shows the importance of push and overlap policies which are static strategies and also model based decision between bound and pack strategies. Another experiment ran to compare the Titanium generated matrix multiplication kernel with a MPI based hand tuned one named Aztec. They ran this experiment for 22 different matrixes with 1 to 16 CPUs configurations and reported the maximum and average speedup. In some cases the Titanium is 2 times faster than Aztec and in average it is 1.2 times faster. It is important to note that sparse matrix – dense vector multiplication is very similar to the communication pattern the paper is targeting in which array indexes are presented by another array elements.
Was evaluation convincing?
The data presented in figure 8 is comparing several optimizations with each other. Although it seems that the major performance gain coming from overlap and push techniques paper did not presented the performance results just for these two techniques but it has given the performance using these techniques in combination with other techniques like pack, bounded and model communications.
Also in figure 11, paper presented the speedup results for the same operation using Titanium and Aztec. Although the average and maximum speedup is presented for different matrix benchmarks and on different hardware platforms however the speedup trend from 1 to 16 CPU is not presented.
Sparse matrix- dense vector multiplication algorithm
One of the famous sparse matrix representation data structures is CSR(compressed sparse row) format. In CSR each sparse matrix represented by three arrays which are:
- Values array: which stores non-zero elements of the matrix
- Columns array: which stores the column of the corresponding value with the same index
- Row array: contains the index of the first column for the next row.
The inner loop of the sparse matrix/dense vector multiplication algorithm can simply use the suggested technique in this paper. Since the vector is scattered in global address space each node needs to collect the part of the vector which has corresponding non-zero columns in its own portion of sparse matrix. Therefore it is reasonable to adapt to the appropriate communication method whether it is packed, bounded, or bulk.
