Recursive Matrix Product

 In this program, the JICOS program dispatches a single computation: matrix product, recursively defined. The concept is simple: Given two n X n matrices, if n is small enough, we compute the matrix product directly; otherwise, we decompose the matrix product into eight n/2 X n/2 block matrix products (each constitutes a task), and sum these appropriately to produce the overall product (the composition task). We call the decomposition task class Decompose and the composition task class Compose.

If it were unclear before, the example is intended to make clear that:

The order in which the subtasks are dispatched via the compute method defines the index of the the composition task's input array. Let us refer to the composition task as compose. The 1st time the compute method is invoked, it creates a task whose returned value is assigned to compose.input[0]; The 2nd time the compute method is invoked, it creates a task whose returned value is assigned to compose.input[1], and so on.


The matrices and blocks are assumed to be square and have a dimension that is a power of 2; relaxing these constraints is straightforward, and interferes with the pedagogic value of this exercise with respect to JICOS programming.

We use Janet's input capability to succinctly designate the operand submatrices to the hosts. Each Decompose task contains only row, column, and block size information: a message of O( log n ) bits.

The classes

This program comrises 3 classes:
  • Application.java: the class whose main method creates the input matrices, dispatches the block matrix product computations, and composes the output from the resulting block products.
  • Decompose.java: the class whose execute method either:
    • computes a matrix product directly xor
    • decomposes the problem into 8 submatrix products to be added by the Compose.java class.
  • Compose.java: the class that takes eight n X n matrix products and sums them to form a 2n X 2n matrix.
  • Matrix.java: a composition class whose:
    • constructor constructs a 0 matrix
    • addSubMatrix method adds a submatrix to itself
    • static makeMatrix method returns a matrix of all 1s
    • print method prints itself.

Output

Given the value 8 from the command line, the program constructs two 8 X 8 matrices of 1s, and prints their product. Here is its output:

 row 0: 8 8 8 8 8 8 8 8 
 row 1: 8 8 8 8 8 8 8 8 
 row 2: 8 8 8 8 8 8 8 8 
 row 3: 8 8 8 8 8 8 8 8 
 row 4: 8 8 8 8 8 8 8 8 
 row 5: 8 8 8 8 8 8 8 8 
 row 6: 8 8 8 8 8 8 8 8 
 row 7: 8 8 8 8 8 8 8 8