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:
productRow(r, that)returns rowrof this times that, as a list.emptyRows()returns a list with one empty place for each row of the product. A thread fills placerwithset(r, row).new Matrix<>(rows), the private constructor, makes the product from that list once every place is filled.
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
Write
Band, thenmultiplyInHalves.Bandis a new file,src/main/java/Band.java, and its header iswith the same bound as
Matrix, because a band holds two matrices ofT. It has fivefinalfields: the two matrices,leftandright; the first row of its band,from; the row after its last,to; andresult, the list of places every band shares. A constructor takes all five.runmakes each of its rows withleft.productRow(r, right)and puts it in its place withresult.set(r, ...). It needs three imports:java.util.List, andAdditionandMultiplicationfromorg.apache.commons.numbers.core, asMatrixhas them.runis 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 withcheckMultiply, asmultiplydoes; takeemptyRows(); make two bands, the rows from 0 up torows / 2and fromrows / 2up torows, and aThreadfor each. Start both, thenjoinboth, then make the matrix.joinwaits 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 / 2is 0, so the top band has no rows at all. Its product in halves is whatmultiplygives.Done when
halvesGiveWhatOneThreadGives,halvesOfAnOddNumberOfRowsand your test are green.Write
multiplyInBands(that, threads). Any number of bands: threadimakes the rows fromi * rows / threadsup 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 ifrom i * 7 / 3up to (i + 1) * 7 / 30 0 2 1 2 4 2 4 7 Start every thread first, keeping each in a
List<Thread>, and only then join them all. Ajoinstraight after eachstartwaits for that band before the next one starts, which is one thread at a time again. Fewer than one thread is anIllegalArgumentException.Your test: more threads than rows: 3 rows and 8 threads, where five of the bands are empty.
Done when the three
bandstests 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.
Write
RowDispenser. A new file,src/main/java/RowDispenser.java, with a constructorRowDispenser(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. Marknextsynchronized: two threads that ask at the same moment must not get the same row. Write the end test asnext >= rows, not==, for a reason task 4 shows.Your test: a new file,
src/test/java/RowDispenserTest.java, shaped likeMatrixTest: a dispenser of 3 hands out 0, 1 and 2, then -1, and -1 again.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 aList<Integer> gotas fields; itsrunasks for rows until -1 and adds each one togot. The test makes four takers on one dispenser and a thread for each, starts all four, joins all four, and then checks. Aboolean[] seenof 100,000 places: for every row in every taker’sgot, the test fails if that row is outside 0 to 99,999 or already seen, and otherwise marks it seen. Last, every place must betrue.fail("row " + r + " handed out twice")is the line to fail with, so the message says which row.Then take
synchronizedoffnextand 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 putsynchronizedback, and the test is green again. (This is what>=was for: withoutsynchronized, two threads can push the next row past the end, and an==would never be true again.)Done when both of your
RowDispenserTesttests are green, with the comment above the second.Write
RowTaker, thenmultiplyOnDemand(that, threads).RowTakeris a new file, aRunnablewithBand’s header and four fields: the two matrices, the shared dispenser and the sharedresult. Itsrunasks the dispenser for a row, makes it and puts it in its place, and asks again, until the dispenser says -1. Aforloop says it in one line:multiplyOnDemandmakes oneRowDispenserfor all the rows, thenthreadstakers that share it andresult, starts them all, joins them all, and makes the matrix.result.setneeds nosynchronized: the dispenser never gives one row to two threads, so two threads never set the same place. Fewer than one thread is anIllegalArgumentException.Your test: more takers than rows: 3 rows and 8 threads, where most takers get -1 at their first question.
Done when
onDemandGivesWhatOneThreadGivesand your test are green.
Part 3 — a clock
Write
Timing. A new file,src/main/java/Timing.java, whosemainmultiplies two 300 by 300 matrices ofReal, which is in the project: onedoublethat can be added and multiplied. Fill them fromnew Random(1).nextDouble()andnew 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, andmultiplyInBandsandmultiplyOnDemandwith 2 threads and with 4. For each,long start = System.nanoTime();before and(System.nanoTime() - start) / 1_000_000after is the time in milliseconds; print one line each. PrintRuntime.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
Timingruns, 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, insrc/main/java/Board.java, which never changes once made: aboolean[][]field,truefor alive; a constructor taking the rows as strings,'#'for alive and'.'for dead, as the picture above;isAlive(r, c); andtoString, 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 overdranddcfrom -1 to 1, skipping the cell itself (dranddcboth 0) and any place off the board.next(): a newboolean[][], each place set by the rule fromneighbours, and a newBoardmade 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.equalsandhashCode:Arrays.deepEqualsandArrays.deepHashCodecompare and hash an array of arrays cell by cell, which==andequalson arrays do not.BoardTest: the blinker turns and turns back; a glider moves one row down and one column right in four generations; andnext(threads)gives whatnext()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.