Assignment 8 — Matrices in parallel

The Matrix from Class 15, multiplied by several threads at once: in two halves, in bands, and a row at a time from a dispenser the threads share. Then a clock on all of it.

Due Oct 27, 2026

This one has its own repo. Accept it the same way you accepted A7, clone it, open the folder in IntelliJ and let it finish loading. It is laid out as A7 was: the code under src/main/java, the tests under src/test/java, and a pom.xml that tells IntelliJ what the project needs, this time Apache Commons Numbers as well as JUnit. Run MatrixTest from the arrow beside its name. The red tests are the methods you are about to write, and a task is done when its tests are green, yours included.

Matrix is the one from Class 15, finished: Fraction is an Addition<Fraction> and a Multiplication<Fraction>, and add and multiply are written. multiply makes the rows of the product one after another, in the thread that calls it. But each row is a piece of work of its own: row 3 of the product needs row 3 of this matrix and all of that one, and nothing from row 2. So several threads can make rows at the same time, as long as no two of them write in the same place. This assignment shares the rows out three ways, and then times them.

Three things in Matrix are there for you to use:

Each task ends with a test of your own: a case the given tests do not try, checked with assertEquals against what multiply gives in one thread, or against values worked out by hand. It is done when it is green, and it goes red when you change the value it expects (then put it back).

Task 4 is the one to start early if you can. It asks you to break a class on purpose and watch a test fail, and the failures come and go: it needs several runs and a clear head, not the last hour before the deadline.

Part 1 — rows in bands

  1. Write Band, then multiplyInHalves. Band is a new file, src/main/java/Band.java, and its header is

    public class Band<T extends Addition<T> & Multiplication<T>> implements Runnable

    with the same bound as Matrix, because a band holds two matrices of T. It has five final fields: the two matrices, left and right; the first row of its band, from; the row after its last, to; and result, the list of places every band shares. A constructor takes all five. run makes each of its rows with left.productRow(r, right) and puts it in its place with result.set(r, ...). It needs three imports: java.util.List, and Addition and Multiplication from org.apache.commons.numbers.core, as Matrix has them.

    run is what a thread runs. new Thread(band).start() runs it in a new thread while this one carries on; band.run() would be an ordinary call, in this thread.

    Then in Matrix, multiplyInHalves(that): check the shapes with checkMultiply, as multiply does; take emptyRows(); make two bands, the rows from 0 up to rows / 2 and from rows / 2 up to rows, and a Thread for each. Start both, then join both, then make the matrix. join waits until that thread has finished. Without it the matrix is made from a list whose places may still be empty.

    Your test: a matrix of one row, where rows / 2 is 0, so the top band has no rows at all. Its product in halves is what multiply gives.

    Done when halvesGiveWhatOneThreadGives, halvesOfAnOddNumberOfRows and your test are green.

  2. Write multiplyInBands(that, threads). Any number of bands: thread i makes the rows from i * rows / threads up to (i + 1) * rows / threads. For 7 rows and 3 threads that is rows 0 and 1, rows 2 and 3, and rows 4, 5 and 6:

    thread i from i * 7 / 3 up to (i + 1) * 7 / 3
    0 0 2
    1 2 4
    2 4 7

    Start every thread first, keeping each in a List<Thread>, and only then join them all. A join straight after each start waits for that band before the next one starts, which is one thread at a time again. Fewer than one thread is an IllegalArgumentException.

    Your test: more threads than rows: 3 rows and 8 threads, where five of the bands are empty.

    Done when the three bands tests and yours are green.

Part 2 — rows on demand

Bands share the rows out before any thread starts. If some rows take longer than others, one thread finishes early and waits while another is still on a long band. The other way to share is on demand: no thread owns a band; each takes the next row nobody has taken yet, makes it, and comes back for another, until there is none left. A thread that gets quick rows simply takes more of them.

The rows are handed out by one object that all the threads share, and it is the one thing in this assignment that changes while they run.

  1. Write RowDispenser. A new file, src/main/java/RowDispenser.java, with a constructor RowDispenser(int rows) and one method, next(), which returns 0 the first time it is called, then 1, then 2, and -1 once every row has been handed out, and -1 every time after that. Two fields: how many rows there are, and the next one to hand out. Mark next synchronized: two threads that ask at the same moment must not get the same row. Write the end test as next >= rows, not ==, for a reason task 4 shows.

    Your test: a new file, src/test/java/RowDispenserTest.java, shaped like MatrixTest: a dispenser of 3 hands out 0, 1 and 2, then -1, and -1 again.

  2. Watch the race, then keep it out. A second test in RowDispenserTest: four threads share one dispenser of 100,000 rows, and every row from 0 to 99,999 is handed out exactly once.

    Inside the test file, a small class Taker implements Runnable, with the dispenser and a List<Integer> got as fields; its run asks for rows until -1 and adds each one to got. The test makes four takers on one dispenser and a thread for each, starts all four, joins all four, and then checks. A boolean[] seen of 100,000 places: for every row in every taker’s got, the test fails if that row is outside 0 to 99,999 or already seen, and otherwise marks it seen. Last, every place must be true. fail("row " + r + " handed out twice") is the line to fail with, so the message says which row.

    Then take synchronized off next and run this test five times. In a comment above the test, write how many of the five runs failed and what one of the messages said. Then put synchronized back, and the test is green again. (This is what >= was for: without synchronized, two threads can push the next row past the end, and an == would never be true again.)

    Done when both of your RowDispenserTest tests are green, with the comment above the second.

  3. Write RowTaker, then multiplyOnDemand(that, threads). RowTaker is a new file, a Runnable with Band’s header and four fields: the two matrices, the shared dispenser and the shared result. Its run asks the dispenser for a row, makes it and puts it in its place, and asks again, until the dispenser says -1. A for loop says it in one line:

    for (int r = dispenser.next(); r != -1; r = dispenser.next()) {

    multiplyOnDemand makes one RowDispenser for all the rows, then threads takers that share it and result, starts them all, joins them all, and makes the matrix. result.set needs no synchronized: the dispenser never gives one row to two threads, so two threads never set the same place. Fewer than one thread is an IllegalArgumentException.

    Your test: more takers than rows: 3 rows and 8 threads, where most takers get -1 at their first question.

    Done when onDemandGivesWhatOneThreadGives and your test are green.

Part 3 — a clock

  1. Write Timing. A new file, src/main/java/Timing.java, whose main multiplies two 300 by 300 matrices of Real, which is in the project: one double that can be added and multiplied. Fill them from new Random(1).nextDouble() and new Random(2).nextDouble(), so every run multiplies the same two.

    Multiply once without timing anything first: the first run of any Java code is slower while it gets compiled. Then time multiply, and multiplyInBands and multiplyOnDemand with 2 threads and with 4. For each, long start = System.nanoTime(); before and (System.nanoTime() - start) / 1_000_000 after is the time in milliseconds; print one line each. Print Runtime.getRuntime().availableProcessors() too: how many threads the computer can run at the same moment.

    Run it three times, and paste the three runs into a comment at the top of Timing.java, with a line or two on what they show: how much faster four threads are than one, and whether that is what the number of processors leads you to expect.

    Done when Timing runs, and its comment holds three runs and your lines on them.

Optional — the Game of Life, in parallel

A bigger one, in new files of its own. Conway’s Game of Life is a board of cells, each alive or dead, that changes a generation at a time, every cell at once, by one rule about its eight neighbours:

  • a live cell with two or three live neighbours stays alive;
  • a dead cell with exactly three live neighbours comes alive;
  • every other cell is dead in the next generation.

Off the edge of the board counts as dead. Three cells in a row turn into three in a column and back again for ever, a blinker:

.....      .....
.....      ..#..
.###.  ->  ..#..
.....      ..#..
.....      .....

The middle cell has two live neighbours and stays; the two ends have one each and die; the cells above and below the middle have three each and come alive.

Each new generation is made from the old one alone, so its rows can be made by several threads at once, the way the product’s were. Build it in this order:

  • Board, in src/main/java/Board.java, which never changes once made: a boolean[][] field, true for alive; a constructor taking the rows as strings, '#' for alive and '.' for dead, as the picture above; isAlive(r, c); and toString, the rows in the same characters, one per line.

  • neighbours(r, c): how many of the eight cells around this one are alive. Two loops over dr and dc from -1 to 1, skipping the cell itself (dr and dc both 0) and any place off the board.

  • next(): a new boolean[][], each place set by the rule from neighbours, and a new Board made from it. Read only the old board while you fill the new one: a cell changed early would give its neighbours the wrong count.

  • next(threads): the same, in bands of rows, as in task 2. Each thread writes only its own rows of the new array.

  • equals and hashCode: Arrays.deepEquals and Arrays.deepHashCode compare and hash an array of arrays cell by cell, which == and equals on arrays do not.

  • BoardTest: the blinker turns and turns back; a glider moves one row down and one column right in four generations; and next(threads) gives what next() gives on a board of your own, for 1 to 5 threads. The glider, and where it is four generations later:

    .#....      ......
    ..#...      ..#...
    ###...  ->  ...#..
    ......      .###..
    ......      ......
    ......      ......

Then a main that prints a glider crossing a larger board, a generation at a time.

Handing in

Commit and push. The last commit before the deadline is what gets marked.

Every push is graded, one check at a time, and the result lands on your feedback pull request, so push early and read what failed rather than saving it all for the last night. The checks are MatrixTest again, with a few of their own, among them whether more than one thread really did the work; a green test on your machine is a green check there.

A student presents this one in class on Wednesday, October 28.