15-418/618 Fall 2018 Project

Mutex Implementation with User Level Interrupt (ULI) Framework

Project Proposal


Checkpoint Report


Final Report


Progress Report

Week 1 (Nov. 4 - 10)

    • Read research papers on Active Messages and met with Prof. Goldstein to discuss our understanding
      • Thorsten von Eicken, David E. Culler, Seth Copen Goldstein, and Klaus Erik Schauser. 1992. Active messages: a mechanism for integrated communication and computation. SIGARCH Comput. Archit. News 20, 2 (April 1992), 256-266. DOI: https://doi.org/10.1145/146628.140382
      • Jeremiah James Willcock, Torsten Hoefler, Nicholas Gerard Edmonds, and Andrew Lumsdaine. 2010. AM++: a generalized active message framework. In Proceedings of the 19th international conference on Parallel architectures and compilation techniques (PACT '10). ACM, New York, NY, USA, 401-410. DOI: https://doi.org/10.1145/1854273.1854323
    • Got guidance from Prof. Goldstein on how to set up our workbench
      • We will be running our programs in our containerised environment
      • There are two possible environments
        • Simulation: This will compile the programs and the library to run the programs on the underlying architecture
        • Native: This will compile our code to run on GEM5 simulator. The compiler compiles each of the messaging primitives like SEND and RECV as if each of them were a part of the CPU instruction set.

Week 2 (Nov. 11 - 17)

    • We got the container running and ran simple message passing programs like Ping Pong (sample programs from ULI repository) in the container.
    • We explored the existing ULI code base to understand basic ULI primitives which we would later use to write our own programs.
    • We are currently using gcc compiler but we have to shift to clang which inserts some of the boilerplate for using ULI library and makes code much cleaner. We will be taking this up in Week 3.
    • We implemented a very primitive mutex using ULI
      • The ULI mutex implementation is that, one thread serves as the central thread, who controls the acquirement and release of a global lock to the contending threads. In order to require lock, a thread needs to send a message to the central thread with a designated handler. Upon the reception of the message, the central thread executes the handler to perform the task at critical section, then executes an acknowledgement handler to do housekeeping work. If after sending a message, the message isn’t immediately received by the central thread, the contending thread spins until its message is received. This simple program with ULI mutex was compiled with gcc and ran correctly.
    • We have also implemented microbenchmarks using Test&Set and Test&Set with Backoff but are waiting for clang compiler to be ready for GEM5 simulation. We hope to get it by the beginning of Week 3. Then we can proceed with microbenchmarking.

Checkpoint Status

    • As per our proposed schedule in the project proposal, we are ahead.

Week 3 (Nov. 18 - 25)