Last updated on Thursday, January 09, 2025

Boids, in parallel

In this week’s callback, you will look back at the Boids lab, where you did everything without polymorphism and Scala collections, and change the computation to use Scala collections, and identify opportunities to parallelize the code.

Obtaining the lab files

Run the following commands to obtain a copy of the lab:

$ git clone https://gitlab.epfl.ch/lamp/cs-214/boids-par.git
$ cd boids-par

The provided code contains a possible solution to the previous lab. You will need to modify the BoidLogic.scala, World.scala and HowManyHoursISpentOnThisLab.scala files to complete this lab.

Step 1: Moving to a new collection

Since our homemade BoidSequence doesn’t provide a parallel interface yet, we’re going to have to switch to a different collection.

Start by replacing instances of BoidSequence with Vector[Boid]. What other changes do you have to make to the previous solution now that you have access to a polymorphic collection?

Step 2: Boids flying out in parallel

With the modified implementation, can you find opportunities for parallelization? With some careful analysis, you can gain a lot of performance by adding a .par and .seq before and after your operations.

  val isVector1: Vector[Int] = Vector(1, 2, 3).par            // ❌
  // Found:    scala.collection.parallel.immutable.ParVector[Int]
  // Required: Vector[Int]

  val isVector2: Vector[Int] = Vector(1, 2, 3).par.seq        // ✔️
  val isVector3: Vector[Int] = Vector(1, 2, 3).par.toVector   // ✔️

Before jumping into the modifications, spend some time analyzing the sequential code. Identify all the places where independent calculations are being made one after the other.

It is most efficient to start from the “top” of your computation. The larger the computation you can split up, the better! This is akin to dividing a big project into its major components first, rather than starting with the tiny details. By splitting the largest independent chunks of the computation, we can maximize the amount of work done in parallel with the least number of threads created.

Remember, not all parts of the code might be suitable for parallelization. Sometimes, the overhead of parallel execution might outweigh its benefits. Test, test, and test your code again!

Testing

As changing the representation of the data should not affect the behavior of the program, all the previous test suites should continue to pass.

You can run all suites as usual with:

$ sbt test

To allow you to test the performance of your code as you play with it, we have included two benchmarks: one calls tickWorld directly, and the other one has a copy of the sequential code, as before:

/** Class for adding JMH benchmarks */
class Benchmarks:
  @Benchmark
  def parallelBenchmark =
    tickWorld(Benchmarks.random1k, Physics.default)

  @Benchmark
  def sequentialBenchmark =
    // Warning: this sequential baseline is only valid if tickWorld is the only
    // parallel function.  If tickWorldSequential calls other functions and you
    // make those parallel, then they will be called (in parallelized form) and
    // benchmarked from here as well!
    tickWorldSequential(Benchmarks.random1k, Physics.default)

You can run it using the Jmh/run -f 1 sbt command.

JMH will report results in the following form (the results below are before parallelization):

[info] Benchmark                        Mode  Cnt    Score    Error  Units
[info] Benchmarks.parallelBenchmark    thrpt    5  125.887 ±  6.088  ops/s
[info] Benchmarks.sequentialBenchmark  thrpt    5  120.561 ± 13.984  ops/s

The ops/s number is how many times the benchmark ran per one second (higher is better). In the boids lab, this is a close proxy for frames per second in the animation, which is the metric that we care about.

Submit your patch!

Once your are done, you should submit your code on Moodle. Since we are revisiting old code, rather than writing new code, the submission is done as a patch.

1. If you forgot how to create patches, you can re-watch the online lecture, or redo the introductory exercises on patching.

2. Select files to commit using git add. Make sure to select only relevant files. In this assignment, you should be including exactly three files, src/main/scala/boids/BoidLogic.scala, src/main/scala/boids/World.scala and src/main/HowManyHoursISpentOnThisLab.scala.

3. Save your work using git add, followed by git commit, with the right parameters. Make sure that your commit message if correctly formatted. We enforce the following format:

   <Scope>: <Summary>
   
   <Description>
   

   • The scope indicates what part of the course the code relates to. In this assignment, the scope should be boids-par.
   • The summary gives a high-level overview your changes. It should start with a capital letter.
   • The description describes the changes in detail—this includes information such as why the changes were necessary, which functions were changed, or what implementation decisions were taken. Here are some examples.
   • The complete header line (scope + summary) should be at most 80 characters.
   • Note that the < and > symbols are often used to show places where you should fill in a value: do not actually write these symbols in your message!

   A plain call to git commit will open your $GIT_EDITOR, which lets you input the header line and the body line separately. If you prefer to stay on the command line, you can pass the -m option multiple times: git commit -m "<Scope>: <Summary>" -m "<Description>".

4. Create a patch from your commit, using git format-patch with the correct arguments, and rename it to lab.patch.

5. Submit your patch (named lab.patch) to Moodle.

If you need help, review the lecture about version control and the corresponding exercise set.

© 2023, 2024 EPFL. All rights reserved.