1 of 33

CAL Implementation in GraalVM

Lakshya A Agrawal

Advisor: Dr. Endri Bezati

Supervisor: Prof. James Larus

2 of 33

CAL Implementation in GraalVM

CAL

Dataflow Programming Language

Actor Model of Computation

GraalVM

Universal Virtual Machine

Support for Polyglot and Native image

3 of 33

Problem

Decrease in performance gains for general purpose processors

Potential Solution

Explore use of FPGAs as reconfigurable accelerators

Challenge!

Determine division of work between processor and FPGA

Context of the problem

3

4 of 33

Experiments on different system configurations
Require rewrite of parts of systems

A single language system
Targets both CPUs and FPGAs
Simplifies division of labor exploration to a simple recompile
This is addressed by Tycho

4

Context of the problem

Finding Division of Labour

StreamBlocks

Solution

5 of 33

Aim of the project

Extend StreamBlocks with a development environment

Debugger support

Polyglot support

CAL implementation over GraalVM

Truffle Framework

Faster language extension experiments

Native Image Compilation

5

6 of 33

Philosophy: Writing AST Interpreter is easy

Profiling info from interpreter used for optimized partial evaluations

Implementations of languages like TruffleRuby have faster than native performance

Compiles to native image

Saves the warming up time of the JVM

Uses AST metadata to power development tools

Debugger using Chrome Dev Tools and Debugger Adapter Protocol

IDE support through Language Server Protocol

Background

Truffle Programming Language Implementation Framework

6

7 of 33

Background

CAL Programming Language

The Actor Model

A Program consists of different Actors

Actors have point to point connections with each other through data-pipes

Communicate discrete data packets (tokens)

7

8 of 33

Background

CAL Programming Language

Individual Actors consist of

A series of input ports and output ports

8

9 of 33

Background

CAL Programming Language

Individual Actors consist of

An internal State (variable bindings)

9

10 of 33

Background

CAL Programming Language

Individual Actors consist of

Set of optionally tagged actions, which perform the actual "computation"

10

11 of 33

Background

CAL Programming Language

In each firing, one action may execute, which can:

Consume tokens from Actor's input ports

Modify the Actors' internal state

Produce tokens at its output ports

Rules can be specified to determine when an action is fired

Actors perform their computation in a sequence of steps called firings

11

12 of 33

How does an Actor execute?

Action Selection

Action Execution

12

13 of 33

Action Selection

Which Action to execute next?

What if data arrives at both the ports?

Scenario

13

14 of 33

Action Selection

Which Action to execute next?

Actors can have multiple actions

The order of action execution can affect the results of the computation

CAL Provides a powerful set of Action-Selection constructs

What is the need?

14

15 of 33

Each action can be provided a tag in the form of X.Y.Z

The action can then be referred to by any of its tag prefixes

An action tagged X.Y.Z can be referred by X, X.Y and X.Y.Z

Action Selection

Which Action to execute next?

Naming Actions

15

16 of 33

Action Selection Primitives

Input port constraints

Enough tokens available in port for action binding

Guards

Boolean pre-condition to execution

Schedules

Ordering over action-tags as a REGULAR language
Specified as FSM or Regex

Priorities

Prioritize certain actions over others

Action selection can be very complex

…but it is driven by relatively few simple “atomic” conditions

16

17 of 33

Action Selection Primitives

Action selection can be very complex

…but it is driven by relatively few simple “atomic” conditions

Input port constraints

Enough tokens available in port for action binding

17

18 of 33

Action Selection Primitives

Action selection can be very complex

…but it is driven by relatively few simple “atomic” conditions

Input port constraints

Enough tokens available in port for action binding

Guards

Boolean pre-condition to execution

18

19 of 33

Action Selection Primitives

Action selection can be very complex

…but it is driven by relatively few simple “atomic” conditions

Input port constraints

Enough tokens available in port for action binding

Guards

Boolean pre-condition to execution

Schedules

Ordering over action-tags as a REGULAR language
Specified as FSM or Regex

19

20 of 33

Action Selection Primitives

Input port constraints

Enough tokens available in port for action binding

Guards

Boolean pre-condition to execution

Schedules

Ordering over action-tags as a REGULAR language
Specified as FSM or Regex

Priorities

Prioritize certain actions over others

Action selection can be very complex

…but it is driven by relatively few simple “atomic” conditions

20

21 of 33

Action Selection Primitives – Language Specification

An Action may execute if it satisfies the following:

2. All input patterns are satisfied

3. Guard conditions satisfied

4. No higher-priority action is enabled

1. The Action Tag may follow from the Action Schedule

actor Add () A, B ==> X:

action A:[a], B:[b] ==> X:[a+b] end

end

actor Split() A ==> P, N:

action A:[a] ==> P:[a]

guard a >= 0 end

action A:[a] ==> N:[a]

guard a < 0 end

end

actor BiasedMerge() A, B ==> X:

CopyA: action A:[a] ==> X:[a] end

CopyB: action B:[b] ==> X:[b] end

priority CopyA > CopyB; end

end

actor AlmostFairMerge () Input1, Input2 ==> Output:

A: action Input1: [x] ==> [x] end

B: action Input2: [x] ==> [x] end

schedule fsm s1:

s1 (A) --> s2;

s2 (B) --> s1;

end

21

22 of 33

Action Selection Implementation

Priorities and Schedules

Priorities induce a partial order on the set of actions

Implementation:

DAG generated from partial order induced by priority relations

Topological sorting of the DAG using DFS

This ordering is used to execute actions sequentially for firing

Schedules

Implementation:

Regex converted to FSMs

FSM transitions stored in AST nodes

Actions checked before execution

State change after action execution

22

23 of 33

Fanout of tokens from FIFOs

Same port of an Actor can have multiple outgoing connections

Implementation

Fanout Node for every output port

References to all outgoing buffers stored

On token push to fanout, tokens are pushed to all references

23

24 of 33

Initializer Actions

Special Actions which only execute once at the beginning

Implementation

Initializers follow all action scheduling rules

ActorInitializer calls action-selection for initializers

24

25 of 33

List Comprehensions

List Comprehension Expressions, which can bind variables from generators, filter bindings by boolean expressions and collect values generated by expression evaluation

Implementation

Each Generator introduces a Lexical Scope

Currently RootNodes are used to create lexical scope

Inefficient Implementation�Will be improved with better support for lexical scoping

25

26 of 33

Action input and output expressions

Support for reading(or writing) multiple tokens from a port during one firing of the action

Implementation

Repeat expressions are created as for-loops in the AST

Multiple expressions are created as enumerated AST nodes

26

27 of 33

CAL Runtime: Running actors to conclusion

The Root entity can be executed user input number of times

Or can be specified to be run till conclusion

Run the root entity till conclusion

Each entity reports if any action executed

Invoke root entity till it returns true

27

28 of 33

Current State of Implementation

What works?

CAL Programs based on Language Spec

59 in total
Each testing a different language feature
CI Pipeline ensures stability across commits

Working JPEG Decoder Program

A movie JPEG decoder description in CAL

Experimental Debugger support with code stepping

Over Chrome Dev Tools
Support for breakpoints

Native Image Compilation Support

CI Pipeline in GitHub
Latest build can be directly downloaded

28

29 of 33

Working Chrome Dev Tools based Debugger

29

30 of 33

Work achieved over Summer

Action Priorities

Guards over bound tokens

Action Schedule FSM

Action Schedule Regex

List Comprehensions

Native Image Compilation

Initializer Actions

Basic Type System

Multiple Input ports in Actors

Fanout of tokens

List size operator

Execution of entities to conclusion

Import all and Namespaces

Complex input and output expressions

While loops

Procedures

Invariant port ordering in Actors

GitHub Actions CI for release and testing

30

31 of 33

Non-preemptive Actor Scheduling

Network Language

Polyglot

Partition of actors into multiple cores

Network Visuali-�zation

Proper Lexical Scoping

Compiler Support

Working language server protocol

Lots of Exciting Development going as Open Source on GitHub

Work in Progress

32

32 of 33

CAL Implementation in GraalVM

Acknowledgements:

Tibor Vaughan, Initial Contributor

Petar Dekanovic, Antlr Parser

Thank You!

33 of 33

Gaps in current implementation

Performance

JPEG Decoder 1000x slower, as compared to native execution
Round Robin Scheduling of Actors
To be improved with working GraalVM Compilation

Partial support for Lexical Scoping

Namespace collision between port names and variable names

Partial support for Types

Currently supported types are int, uint, string and List<Type>

31

With all of the working features outlined in the previous slides, we also have certain gaps in our current implementation, which are all being currently addressed and actively worked upon.

The JPEG decoder program is currently about 1000x slower as compared to the native execution. The 2 major reasons for this are the current use of round robin scheduling under which each actor is executed for exactly one firing after which the next actor is executed. This will be improved with pre-emptive actor scheduling under which each actor will be executed till conclusion before moving on to the next actor.

The other work-in-progress is to add profiling information for the AST to aid the GraalVM system to provide efficient compilation.

Our current implementation provides partial support for Lexical Scoping, for example, there is currently a namespace collision between port names and variable names which will be improved in the future with better lexical scoping.