← Back

15-418 Milestone Report

By Joshua Nichols (joshuani) and Lucca Rodrigues (luccar)

Progress Summary

We have fully implemented a compiler for C0 in Rust with several new language features. The compiler targets LLVM using the inkwell bindings package to convert the LLVM intermediate representation (IR) into machine code. The new language features that we have added include the following:

We are able to call the native OS's pthread_create and pthread_join to allow users to write parallel C0 code. Implementing parallel map and reduce in C0 showed an approximately 7x speedup on 8 processors.

Goals and Deliverables Progress

Deliverables

The three main deliverables we specified in the project proposal are:

  1. Implement code generation to target LLVM backend.
  2. Add foreign function interface (FFI) to support native system calls.
  3. Develop standard library for spawning and joining threads.

We have successfully achieved all our deliverables:

  1. We implemented LLVM code generation through a series of IR lowerings. First, the source code is parsed into an AST which is defined as a recursive data structure. Next, we lower the AST to an IR which stores expressions and statements in an arena allocator and desugars symbol names. Typechecking and semantic analysis are performed on this IR. Finally, we lower the higher-level IR to a three-address assembly IR which we can directly lower to the LLVM representation.

  2. We added the extern keyword to specify externally defined functions for the FFI. The compiler tells LLVM to trust those functions exist without being explicitly defined, and they are only later added during the linking phase.

  3. We added user defined functions to call into the system's native threads:

extern fn pthread_create(thread: void*, attr: void*, start_routine: fn(void*) -> void*, arg: void*) -> int;
extern fn pthread_join(thread: void*, retval: void*) -> int;

Note this required functions as values (function pointers) which was initially included in the nice to haves.

Nice to Haves

The nice to haves we specified in the project proposal are:

  1. Implement support for functions as first-class values.
  2. Develop standard library with common algorithms implemented using parallelism.
  3. Add shared thread pool to reduce overhead of spawning and joining threads.
  4. Add dynamic task queue to balance workload in standard library algorithms.

We successfully added support for functions as first-class values, have made significant progress in adding a parallel standard library, and have not started on the last two items.

We implemented functions as first-class values using function pointers by adding a function type, e.g. fn(int) -> int, which is represented as a pointer underneath the hood. To support generic functions and structs, we added the void* type and type casting, e.g. x as void*.

Updated Deliverables

The remaining deliverables we want to accomplish before the poster session are:

  1. Finish standard library with parallel filter and scan algorithms.
  2. Implement shared thread pool to reduce thread spawning/joining overhead.
  3. Implement dynamic task queue to support workload balancing.

Poster Demo

During the poster session, we would like to showcase speedup graphs of several examples of common parallel algorithms in C0 implemented using our parallel DSL and compiler. We plan to focus on our performance debugging, data collection and analysis journey rather than elaborate demos.

Preliminary Results

To test our DSL, we implemented a simple example in C0: a hand-written, parallel map-reduce over an array of integers. At a high-level, it does the following:

  1. Creates an array A of length 40.
  2. Fills every entry with 40.
  3. In parallel, replaces each entry with fib(40) (parallel map).
  4. In parallel, sums all those results together (parallel reduce).
  5. Returns the final sum.

So mathematically, the result is:

40×fib(40)40 \times \text{fib}(40)

because there are 40 elements, and each one becomes fib(40). The Fibonacci function is a classic recursive implementation, and intentionally expensive, serving as a good benchmark for parallelization of work.

It is worth noting that this algorithm is embarrassingly parallel. As shown by the results below, our program's speedup scaled almost perfectly linear with the number of processors. But this is by design: our main goal here was to implement a proof of concept for our parallelization primitives and establish a performance baseline. If we had somehow gotten less than 5x for 8 processors, we would have instead turned our attention to identifying bottlenecks with the actual language implementation. But with this baseline now in place, we're confident that our compilation pipeline delivers expected speedup trends on par with a common multi-threading implementation in general-purpose systems languages (e.g. C/C++ with POSIX threads).

Number of threadsComputation time (s)Speedup
15.621.00
22.792.01
41.413.99
80.7197.81

Table 1: Benchmark which computes and sums Fibonacci numbers

Issues and Concerns

One issue that we have noticed is that, due to the fact that the function signature for pthread_create and pthread_join take in arguments in the form of void pointers as opposed to typed generics, we inevitably have to define and cast a new data type every time we want to call the multi-threading API functions.

We believe that stronger type checker features/ergonomics could solve this (e.g. C++ templates/STL, Rust traits, closures/lambdas). But we are also aware that this project is quite time-sensitive, and we want to focus on implementing and benchmarking parallelization, as opposed to just implementing a new programming language from scratch.

Updated Schedule