Sal

A compiler and VM for Executable Directed Acyclic Graph (EDAG)

About The Project

In this project, we are trying to compile arithmetic python codes to Executable Directed Acyclic Graph(EDAG)s and run them as EDAGs.

EDAGs are acyclic so running them in a parallel manner on multiple processors would be much easier compared to normal code. Also EDAGs are capable of being configured on FPGAs or any other partially reconfigurable hardwares.

Becuase these days common processors are based Von Neuwmann design, Running EDGAs on them will cause some efficiency problems that we are trying to solve them by partitioning algorithms and precompiling techniques.

Built With

• C++(clang)
• Python
• Cmake
• moodycamel::ConcurrentQueue

Prerequisites

• Python (>=3.8)
• Cmake (>=3.21.1)
• C++ (>=17)
• Clang (>=12)

Usage

• Compiler

  cd compiler
  python3 compiler.py path/to/python/file

  It generates a sal file named a.sal

• VM

  cd vm
  mkdir build
  cd build
  cmake ..
  cmake --build .
  ./salvm path/to/sal/file

• Input python codes

  For now, the compiler input python file should only contain simple arithmetic functions, recursion is allowed. Only integers are allowed for data types. There should be a main function that will be executed by VM. Following code is a simple accepted by compiler fibonacci code:

  def fib(n):
    ret = 1
    if n > 1:
        ret = fib(n-1) + fib(n-2)
    return ret
    
  def main(n):
      return fib(n)

Compiled Sal file structure

A Sal file is a byte-coded file which describes an EDAG. The file structure follows below grammar:

<code> = <main func id><code body>
<code body> = NULL | <code body><box desc>
<box desc> = <box length><box header><graph desc>
<box header> = <box id><number of inputs><input wires><number of outputs><number of local vars><local var wires>
<graph desc> = NULL | <gate><graph desc>
<gate> = <gate id><gate input wires><gate output wires>

Roadmap

• Add compiler
• Add vm
• Add recursion and if (after this, vm will be turing complete)
• Add List data type to compiler
• Add while to compiler
• Fix vm efficiency problems
  • Add partitioning algorithms
  • Add precompiling techniques

License

Distributed under the MIT License. See LICENSE.txt for more information.