Distributed Memory Architecture for High-Level Synthesis ofEmbedded Controllers from Erlang
Kagumi Azuma
Nagisa Ishiura

Nobuaki Yoshida
Hiroyuki Kanbara

Department of Informatics
Kwansei Gakuin University
2-1 Gakuen, Sanda, Hyogo, JapanASTEM RI/KYOTO
Kyoto, Japan

Abstract

order to meet various needs for these products, higher and higher
functionalities are being required.
Especially, with the recent rapid development of the network environment and advent of new services and applications utilizing it,
networking or coordination of multiple embedded systems is being
required. Although real-time operating systems may alleviate thecomplexity of implementing such systems, high skills are required
to specify interrupt handling and to guarantee response time. It isa next challenge to establish new methodologies to model and toautomate design of such communication oriented and sophisticatedsystems.
One approach to address this issue is to use domain speci�c languages which orient event processing, concurrency speci�cation,and networking. Erlang [1] is a concurrency oriented functional
programming language which is originally developed for implementing telephony switches. While it is widely used in the areaof telecommunications, e-commerce, instant messaging, etc., there
are some attempts to use Erlang for embedded systems [2], basedon an observation that concurrent processes and message passing
will allow succinct description of event processing.
On the other hand, at the same time with higher functionality,
higher performance as well as lower power consumption is required
to the embedded systems. An embedded system is commonly implemented as a combination of hardware, processors, and software
running on them. When it is di�cult to achieve compatibility between performance and power consumption, some functionalities
originally implemented as software are migrated to hardware.
High-level synthesis [3], which automatically synthesizes hardware design from software programs, is one of the key technologies
to expedite such re-implementation. Various methodologies to automate hardware design based on high-level synthesis have been
proposed [4, 5]. If hardware is automatically derived from Erlang
speci�cation, advanced sophisticated systems would be easily implemented as e�cient devices with higher response and smaller
power consumption than processor-based systems.
In this context, Takebayashi et al. [6] proposed a way of specifying the behavior of embedded systems in a subset of Erlang and amethod of synthesizing hardware description from the speci�cation. In their framework, each Erlang process is implemented as aseparate logic circuit. Assembly codes of BEAM virtual machine obtained by compiling the input Erlang programs are translated into
CDFG (control data�ow graph, a typical intermediate data structure
for high-level synthesis), from which Verilog HDL [7] codes are
generated using the back-end of the high-level synthesizer ACAP[5]. Although, they generated Verilog HDL codes from a simple
Erlang speci�cation, they were not of practical use because it assumed a shared centralized memory; it is accessed by all the circuits
for the processes simultaneously but a memory device with such

This paper presents a distributed memory architecture for dedicated hardware automatically synthesized from Erlang programs.
Our team had developed a framework for generating embedded
systems controllers whose behavior was speci�ed by a subset ofErlang, where each process was mapped into hardware (a logic
circuit) running independently of the circuits for the other processes. However, the resulting hardware was not of practical use
because it shared a single main memory potentially accessed by
all the circuits for the processes simultaneously. To address thisissue, in this paper, the main memory is partitioned into banks
so that each process can access its own memory independentlyof the other processes. In order to keep the interconnections formessage passing to a practical size, a bus architecture is employed
where send requests are arbitrated by an arbiter (logic circuit). In
order to make the resulting hardware as small as possible, a garbage
collection circuit is shared among the circuits for the processes also
under the control of the arbiter. From a simple Erlang speci�cation,
Verilog HDL codes for necessary hardware to construct a system
has been generated.
CCS Concepts • Computer systems organization → Embedded hardware; • Hardware → Hardware-software codesign;• Software and its engineering → Functional languages;
Keywords Erlang, high-level synthesis, distributed memory architecture, embedded systems, ACAP
ACM Reference Format:
Kagumi Azuma, Nagisa Ishiura, Nobuaki Yoshida, and Hiroyuki Kanbara.
2017. Distributed Memory Architecture for High-Level Synthesis of Embedded Controllers from Erlang. In Proceedings of 16th ACM SIGPLAN International Workshop on Erlang, Oxford, UK, September 8, 2017 (Erlang’17),
7 pages.
h�ps://doi.org/10.1145/3123569.3123574

1

Introduction

Nowadays, innumerable embedded systems are implemented invarious products, such as consumer electronics, automobiles, medical appliances, industrial electronics, autonomous robots, etc. In
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor pro�t or commercial advantage and that copies bear this notice and the full citationon the �rst page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior speci�c permission and/or
a fee. Request permissions from permissions@acm.org.
Erlang’17, September 8, 2017, Oxford, UK© 2017 Association for Computing Machinery.
ACM ISBN 978-1-4503-5179-9/17/09. . . $15.00h�ps://doi.org/10.1145/3123569.3123574

13

Erlang’17, September 8, 2017, Oxford, UK
asm
gas

C

MIPS binary-32756 -32760

library info

+ lw +

optimizationL

objdump

CDFG generator

ACAP [5] is one of the high-level synthesis system, which weutilize as a base of the work in this paper. It synthesizes Verilog
HDL from C programs or MIPS binary codes. The �ow of synthesis
is shown in Figure 1. A binary code generated by GCC or GAS (theGNU assembler) is once disassembled to an assembly code, which
is analyzed and translated into a CDFG. Verilog HDL is generated
according to the standard high-level synthesis procedure.
We use ACAP as a basis of the work in this paper in two ways; weutilize the back-end of ACAP (scheduling through HDL generation)
to generate Verilog HDL from Erlang via CDFG representation, andto obtain hardware modules for complex tasks such as message
passing and garbage collection by high-level synthesis from C codesin the BEAM emulator. Any other high-level synthesizer than ACAP
may be used as long as 1) it accepts CDFGs as well as C codes as
inputs, and 2) it can compile ANSI-C programs into HDL codes.

CDFG

gcc

...
lw v1,-32756(gp)lw v0,-32764(gp)nopaddu v0,v1,v0
sll v0,v0,0x2
sw v0,-32760(gp)...

Kagumi Azuma, Nagisa Ishiura, Nobuaki Yoshida, and Hiroyuki Kanbaralw

Lschedulingbinding

+

addu

<<

sll

RTL IR-32764+S

sw

composer
Verilog
HDL

Figure 1. High-level synthesizer �ow in ACAP [5].
many ports does not exist or is not a�ordable at least to embedded
systems.
To address this issue, this paper presents a distributed memoryarchitecture for high-level synthesis of embedded systems from
Erlang. In this architecture, the stack, the heap, and the message
queue of each process are stored in its local memory, which can beaccessed independently of the other processes. The local memories
are connected with two buses, through which messages are passed
around. Send operations using the bus is arbitrated by an arbiter
circuit. We have implemented a prototype of the synthesizer on
the bases of ACAP, and from a simple Erlang speci�cation, Verilog
HDL codes for necessary hardware to construct a system has been
generated.

2

3

High-Level Synthesis from Erlang

3.1

Erlang Subset for Specifying Embedded Systems
Control

The systems we deal with in our current project [6] are relatively
small ones that control embedded systems. It consists of �xed number of processes up to 10. Furthermore, considering hardware implementation, we assume a very limited subset of Erlang in thispaper. Since the number of the processes are �xed, it is assumed that
all the processes are created at the system initialization time andthere is no dynamic creation/deletion of processes. Input/outputof the system is performed via Erlang ports, which receive/send
byte sequences. Currently, communication only within the system
is handled. Namely, communication with external processes via
TCP/IP is out of the scope of this paper. The data types handled
in this paper are limited to 28 bit signed integers, lists, and tuples.
Closures are not supported.
Figure 2 shows a small example of control description by ourErlang subset. The controller receives signals at an input port port0
from button presses indicating the directions to move. It sends out
corresponding signals to the driving device at an output port port1.
A process proc0 handles I/O and a process proc1 is in charge ofdata translation. In the Erlang code, the two ports and two processes
are created in start (lines 4–14).

High-Level Synthesis and ACAP

High-level synthesis [3] is a technology to generate dedicated hardware automatically from a behavioral speci�cation of target systems, which is often described in procedural programming languages such as C. The typical �ow of synthesis is as follows:
1. CDFG generation
A given speci�cation is compiled into an intermediate data
structure called a control data�ow graph (CDFG), which is acollection of data�ow graphs (DFGs) and transition relations
among them. A data�ow graph expresses the operations anddependencies among them in a basic block.
2. Scheduling
The clock cycle, or the time frame, to execute each operationin each DFG is determined. Typically, this is a problem ofminimizing total clock cycles to execute all the operations
in each DFG with the given numbers of execution units.
3. Binding
Each operation is assigned to a concrete instance of theexecution unit and each value is assigned to a register (ahardware unit to memorize a value, consisting of a set of�ip-�ops). This determines the topology of the resulting
hardware, so it is formulated as the problem of minimizing
the estimated size of the hardware.
4. HDL generation
The speci�cation of the hardware is generated in the formof a hardware design language (HDL), such as Verilog HDL[7] or VHDL [8].

3.2Flow of Synthesis

In the area of hardware design, a circuit to perform a certain task
is called a (hardware) module, so we will henceforth refer to thecircuit for a process as a process module. Similarly, the circuits toperform arbitration, bus functions, and garbage collection will becalled an arbiter module, a bus module, and a garbage collection
module, respectively.
In our method, each Erlang process is synthesized into a single
hardware module so that processes can run independently of eachother except for during interprocess communication. The overhead
for scheduling and management of processes are eliminated.
An Erlang process may execute multiple functions. In our method,
all the functions executed by each process, which are recognized
by static analysis, are synthesized into a single hardware module.
For example, a hardware module for process proc0 in Figure 2(b) should be able to execute functions loop0 and decode, while
the proc1 module should run functions loop1, calc, and encode.

14

Distributed Memory Architecture for High-Level Synthesis of Embedded Controllers
from Erlang(button)

port0

Erlang’17, September 8, 2017, Oxford, UK
Erlang(motor drive)

proc0

port1

proc1

(translation)

erlc
BEAM code(a) Communication among processes and ports.

CDFG generator
CDFG

01: -module(roomba).
02: -export(start/0).
03:
04: start() ->05: spawn(fun() ->06:
register(proc1, self()),
07:
loop1(0, 0)
08: end),
09: spawn(fun() ->10:
register(proc0, self()),
11:
Port0 = open_port({spawn, stdbuf -i0 -o0 -e0 od-h -w8 /dev/input/js0 | ./controller }, {packet, 2}),
12:
Port1 = open_port({spawn, ./roomba }, {packet, 2}),13:
loop0(Port0, Port1)
14: end).
15:
16: decode(Dt,Dh,Et,Eh) ->{((Dh bsl 8) bor Dt), ((Eh bsl 8) bor Et)};
17: decode(X) -> X.
18:
19: loop0(Port0, Port1) ->20: receive
21:{Port0, {data, Data}} ->22:
Data2 = decode(Data),
23:
proc1 ! {proc0, data, Data2},
24:
loop0(Port0, Port1);
25:{proc1, Data3} ->26:
Port1 ! {proc0, {command, Data3}},
27:
loop0(Port0, Port1);
28:{Port1, _} ->29:
loop0(Port0, Port1);
30:
_ ->
31:
loop0(Port0, Port1)
32: end.
33:
34: loop1(D, T) ->35: receive
36:{proc0, data, Data} ->37:{Drive, Turn} = calc(Data, D, T),38:
Cmd = encode(Drive, Turn),
39:
proc0 ! {proc1, Cmd},
40:
loop1(Drive, Turn);
41:
X ->
42:
proc0 ! X,
43:
loop1(D, T)
44: end.
45:
46: calc({Para, X}, Drive, Turn) ->47: if48:
X == 258 -> {Para, Turn};49:
X == 1026 -> {Para, Turn};
50:
X == 2-> {Drive, Para};
51:
X == 770 -> {Drive, Para};
52:
true-> {0, 0}53: end.
54:
55: encode(Drive, Turn) ->56: if
57:
Drive =< 57343, Drive >= 32768 ->
58:
if
59:
Turn =< 57343, Turn >= 32768 -> {146, 0, 127, 0, 63};
60:
Turn =< 32767, Turn >= 12288 -> {146, 0, 63, 0, 127};61:
true-> {146, 0, 127, 0, 127}
62:
end;
63:
Drive =< 32767, Drive >= 8192 ->
64:
if
65:
Turn =< 57343, Turn >= 32768 -> {146,255,127,255,63};
66:
Turn =< 32767, Turn >= 12288 -> {146,255,63,255,127};67:
true-> {146,255,127,255,127}
68:
end;
69:
true ->
70:
if
71:
Turn =< 57343, Turn >= 32768 -> {146,255,127,0,127};
72:
Turn =< 32767, Turn >= 12288 -> {146,0,127,255,127};73:
true-> {146,0,0,0,0}74:
end
75: end.

A
B

libraries (C)+Verilog HDL

ACAP

ACAP

Verilog HDL

Figure 3. Flow of hardware synthesis from Erlang via BEAM code
[6].
x[0]
x[0]

x[1]

b’1111+x[2](a) addition

b’01

4

ld

+

x[1]

ld
x[2]

(b) get_list

Figure 4. Conversion from BEAM instruction to DFG [6].
which would be di�cult to embed into the CDFG. In our framework,
these tasks are implemented as separate hardware modules, called“library modules,” which are activated from the CDFG per demand.
The library modules are synthesized from a reduced C code of the
BEAM interpreter by ACAP.
3.3

Converting BEAM Assembly to CDFG

The BEAM assembly code is analyzed to create a CDFG for eachprocess. First, the initial process to start the system is scanned to
identify all the processes present in the code. Then, all the functions
which may be called from each process are enumerated. Each function is decomposed into basic blocks based on branch instructions
and target labels. The instructions in each basic block are converted
into operations of a DFG (data�ow graph), and then a CDFG isconstructed based on the overall control �ow.
BEAM instructions are translated into DFG operations as follows.
1. Arithmetic and bit operations
Since arithmetic and bit operations in Erlang compiles to
gc_bif instructions, which execute built-in functions, they
are simply converted into operation nodes in DFGs. Since
the 28 bit integer data has b’1111 in the lower 4 bits, instructions on them are translated into operation sequences
to manipulate the upper 28 bit �elds. For example, for an
instruction{gc_bif,’+’,{f,0},0,[{x,0},{x,1}],{x,2}}.
which adds the contents of the registers x[0] and x[1] of
the BEAM VM together and puts the result into x[2], theDFG fragment in Figure 4 (a) is generated. Note that 32 bit
datapath is assumed in this paper. In the case of addition,x[0]+x[1] b’1111 results in addition of the upper 28 bits andsetting of tag b’1111 in the lower 4 bits.
2. List and tuple manipulation
Manipulation of lists and tuples is translated into a sequenceof loads and stores on the heap. For example, for an instruction{get_list,{x,0},{x,1},{x,2}}.

(b) Behavior description by Erlang [6].

Figure 2. Example of Erlang description.
When multiple processes call the same function, the code for thefunction is duplicated.
The �ow of synthesis is illustrated in Figure 3. A given Erlang
program is compiled by erlc, an Erlang compiler, into a BEAM
assembly code, from which CDFG is constructed. By feeding the
CDFG into the back-end of high-level synthesizer ACAP, a Verilog
HDL code is generated. However, some BEAM instructions involve
complex tasks such as message passing and garbage collection

15

Erlang’17, September 8, 2017, Oxford, UK

Kagumi Azuma, Nagisa Ishiura, Nobuaki Yoshida, and Hiroyuki Kanbara

which takes list x[0], whose upper 30 bits represents theaddress of the �rst element and lower 2 bits are tag b’01,
and extracts its �rst element (car) and remaining part (cdr)
into x[1] and x[2], respectively, is compiled into the DFG
fragment in Figure 4 (b) which loads data from the heap.
3. Jump and call
Jump instructions are translated into transition among DFGs.
For example,{test,is_noempty_list,{f,4},{x,0}}.
veri�es that the list pointed by x[0] is non-empty; if the test
fails, the control is transferred to the DFG corresponding to
the label f4. A call instruction{call,1,{f,2}}.
saves the return address in CP, the continuation pointer, andjumps to f2. It is translated to an operation sequence to savethe ID of the return instruction and to transfer the control.
Returning to the calling point is achieved based on the table
which maps the instruction IDs to the states.
4. Manipulation of the heap and the stack
When the instructions to secure memory cells on the heap or
the stack do not �nd enough free cells, they trigger garbage
collection (GC), which are processed by the library module
attached to the process module. Thus, these instructions areconverted into a DFG fragment to call the library module
which consists of 1) stores of arguments, 2) store to variable
to activate the library module, 3) polling to wait for thecompletion of the library module, and 4) loads of the results.
5. Message passing
Message passing also involves complex tasks such as copy ofheap data and garbage collection, which are also converted
into a DFG fragment to call the library module.
3.4

P0

L0

P1

L1

P2

L2

P3

L3

main memory
M0

M1

M2

M3

Figure 5. Previous hardware con�guration with single main memory.

arbiter

P0
L0

P1
L1

P2
L2

P3

GC

L3

Q-bus
H-bus

Q0

H0

Q1

H1

Q2

H2

Q3

H3

Figure 6. Proposed hardware con�guration with distributed memories.
Copies the current message in the queue to x[0] register andcopy any attached data into the heap. If enough free words
are not available in the heap, garbage collection is invoked.
5. remove_message
Unlinks the current message from the message queue (whena match succeeded on the message).
6. save_message
Proceeds the current message pointer by one (when all thematches on the message fail).
7. wait_timeout t
Waits for a new message. If no message arrives within t
clock cycles, quit waiting (and just returns the control to thecaller).

Library Module

Each process is provided with a library module which handles
complex tasks. The library module executes the following sevenfunctions.
1. test_heap m, n
Tests if m free words are available on the heap for the process.
If not, garbage collection is invoked. n is the number of the x
registers which must be protected from garbage collection.
2. allocate m, nExpands the stack region by m+1 words by updating SP. Lackof necessary free words triggers garbage collection.
3. sendSends the contents of x[1] register as a message to the processor the port indicated by x[0] register. If the destination isa process, it enqueues the message to the message queueof the destination process and copies the accompanying
data, if any, to the “mini heap” attached to the message. If
the message is destined to an output port, the message andthe accompanying data are serialized and put into the byte
stream bu�er of the output port. The send function may
be invoked by an input port when a new byte sequence is
detected on the input bu�er of the port. In this case, a list
data structure is assembled which are copied to the message
queue and the mini heap of the destination process.
4. receive

The library modules are controlled by process modules via control variables. Let RUN_i be the variable to control the library
module of process i. When RUN_i is 0, the library module is idle.
When the process want to activate the library module, it writes
the number (1 through 7) of the desired function into RUN_i after
writing the argument values into the memory. Then the library
module completes the execution of the function indicated by RUN_i,
it stores the result in the memory, and resets RUN_i. As soon as
RUN_i is turned o�, the process module loads the result and resumes its tasks.

4Distributed Memory Architecture

In the synthesis method proposed in [6], a centralized memoryarchitecture is assumed, as shown in Figure 5, where a single memory module is accessed by process modules and library modules
in parallel. This is obviously unrealistic, for a memory module ofas much as 10 ports is not a�ordable at least to embedded systems.
The other problem with the previous architecture is that the size ofthe hardware, especially that of library modules, is too large. This

16

Distributed Memory Architecture for High-Level Synthesis of Embedded Controllers
from Erlang
is because, each library module must include hardware for garbage
collection which is large but not used so frequently.
In order to make the synthesized hardware more practical, we
propose in this paper a distributed memory architecture, illustrated
in Figure 6, which has the following features:

Erlang’17, September 8, 2017, Oxford, UK
arbiter

local

local

P0

receive

P1

L0

L1

receive

P2
L2

P3

GC

L3

Q-bus

1. Distributed memories
Each process and library module (Pi and Li) have their own
memory, which is further partitioned into a memory forthe heap and the stack (Hi) and the one for the message
queue and the mini heap (Qi). Note that only a single port isenough for both Hi and Qi. Nevertheless, all the processes
can operate independently with each other, except for during
message passing and garbage collection.
2. Shared garbage collector
A single garbage collection module (GC) is shared with all
the processes. This contribute to signi�cant reduction on the
hardware cost, though only one process can execute GC at
the same time.
3. Two buses for global communication
Two buses, Q-bus for accessing Qis and H-bus for His are provided to carry out message passing and garbage collection.
We adopt bus architecture for message passing because apoint-to-point network needs huge amount of interconnects
and support hardware. However, with the bus architecture,message passing and GC must be processed one by one.
4. Arbitration
Message passing and GC are moderated by an arbiter module.
It receives requests for GC or message passing and permits
their execution according to prede�ned priorities.

H-bus

Q0

H0

Q1

H1

Q2

H2

Q3

H3

(a) Parallel execution of local operations.
arbiter
local

local

P0
L0

send

P1
L1

receive

P2
L2

P3

GC

L3

Q-bus
H-bus

Q0

H0

Q1

H1

Q2

H2

Q3

H3

(b) Send operation.
arbiter
local

GC

P0
L0

send

P1
L1

receive

P2
L2

P3

GC

L3

Q-bus
H-bus

4.1

Distributed Memory and Bus Modules

The distributed memory scheme works as follows.

Q0

1. Each process module Pi can access its own working memory
Hi independently of the other processes. For example, as
shown in Figure 7 (a), P0 and P1 can execute their local
computation using their working memories in parallel. Eachlibrary module Li may access message queue Qi and Hi
independently of the other processes. So receive operations
can be also executed in parallel.
2. When process Pi sends a message to Pj, it reads its own
working memory Hi and writes to the message queue Qj of
the destination process. The latter is done through the Q-bus.
In Figure 7 (b), for example, P2 is sending a message to P1,
so L2 reads H2 and writes to Q1. Meanwhile, irrelevant P0
and P3 can operate in parallel. Furthermore, P1 can executelocal computation, as long as it does not access Q1. (In thiscase, P1 cannot execute receive.)
3. When process Pi requests GC, the GC module cleans up
Hi via H-bus. In Figure 7 (c), garbage collection is being
executed on the heap of P1. The other processes can run
in parallel as long as they do not access H1. Thus, even thesend operation from P2 to P1 can be done simultaneously.

H0

Q1

H1

Q2

H2

Q3

H3

(c) Garbage collection.

Figure 7. Distributed memory architecture.

On the side of Li, read accesses to the Qi and Qj (j , i) arehandled as follows:• If the read access is from Li and the segment number (theupper 32 m bits) of the address is i, then the read request
is forwarded to Qi with the lower m bit of the address, andthe answer from Qi is returned to Li.
• If the read access is from Li and the segment number of theaddress is not i, then the read request is broadcast via Q-bus
with the full address. As soon as the resulting data appear
on the bus, they are returned to Li.
• If the read access is from the Q-bus (namely, from the otherprocesses) and the segment number of the address is equal
to i, then the read request is forwarded to Qi with the lower
m bit of the address, and the answer from Qi is put on thebus.

Accesses to the memories of other processes are handled by abus module. We assume a single address space for an entire system,
which is addressed by 32 bits. Each of Hi or Qi is assigned a segmentfrom the address space. The lower m bits of the address are used
for the local memory address and the upper 32 m bits are used
for distinguishing the segments.

Note that no two library modules try to access the Q-bus simultaneously. Furthermore, no two Li and Lj do not access Qi
simultaneously. These are guaranteed by the arbiter.
The accesses to Hi are handled in the same way as those to Qi,
except that both Li and Pi may access Hi. This, however, does not17Erlang’17, September 8, 2017, Oxford, UK

Kagumi Azuma, Nagisa Ishiura, Nobuaki Yoshida, and Hiroyuki Kanbara

make big di�erence because Li and Pi does not access Hi simultaneously.

arbiter module

P0

4.2

The arbiter module arbitrates message passing and garbage collection based on the requests from the processes. If a request arrives
while the previous one is being processed, the new one will beprocessed after the previous one. If multiple requests are waitingor multiple requests arrive simultaneously, the order is determinedaccording to the predetermined priority.
Requests for garbage collection are processed as follows.
1. Library module Li requests GC by raising its GC request
signal GC_reqi to 1.
2. On noticing GC_reqi =1, the arbiter forwards the request to
the GC module by setting GC_req=1 and GC_process=i. If
multiple requests are arriving, the arbiter chooses one ofthem according to the priority.
3. The GC module does garbage collection on Qi, and thennoti�es the completion by making GC_req=0.
4. The arbiter forwards the noti�cation to Li by setting GC_reqi =0.
5. On con�rming GC_reqi =0, Li and Pi resume their execution.
The protocol for send requests needs extra steps because thesend is not permitted while the destination process is executing a
receive operation (which manipulates the message queue).
1. Library module Li requests send to process j by setting
send_reqi =1 and send_to=j.
2. Arbiter forwards the request to process j by raising enqueue
request signal of j (enq_reqj =1). If multiple requests arearriving, the arbiter chooses one of them according to thepriority.
3. If the process j is not executing neither of receive_message,
remove_message, nor save_message, then it permits enqueueing of the new message by setting enq_readyj =1.
4. The arbiter forwards the permission to Li by setting send_reqi =1.
5. On con�rming send_reqi =1, Li starts enqueueing of the message and copy of the heap data to Qj.
6. Li noti�es the completion of the send operation by setting
send_reqi =0.
7. Arbiter forwards the completion by setting enq_reqj=0.
Note that library module Lj must be designed carefully so that it
can respond to enq_reqj = 1 while it is waiting for its send request(of the lower priority) to be processed.
4.3

I/O Modules

In order to access to the signals regarding arbitration, such as
GC_reqi and enq_readyj , in a uniform manner, we place them allin the address space. Namely, all the signals are read and written
to by memory mapped I/O. This interfacing is taken care of by I/Omodules. Figure 8 is a revised version of Figure 6.

5

P1

L0

Arbiter

Implementation

A prototype high-level synthesizer based on the proposed method
has been implemented which runs on Ubuntu Linux and Mac OS X.
The BEAM to CDFG translator ( A in Figure 3) is implemented
in Perl5. All the operations in CDFGs are based on 32 bit datapathof ACAP.
The C library programs ( B in Figure 3) are obtained by extracting
and reducing the necessary portions from the source code of the

18

P2

L1

IO module

IO module

GC

L3

IO module

bus module

local

P3

L2

send

IO module

receive

IO moduleGC

bus module

Q0

H0

Q1

Q2

H1

H2

Q3

H3

Figure 8. Proposed architecture with I/O modules.

arbiter moduleP0

iport0

L0

IO module

IO module

L1

P1

IO module

oport1

IO moduleGC

IO module

bus modulebus module

ibuffer

Q0

H0

Q1

H1

obuffer

Figure 9. Synthesized hardware con�guration of the sample program.

BEAM interpreter of Erlang OTP 18.1.3. The original codes forhandling the message queues and copy of the heap data were usedalmost without modi�cation, though unnecessary codes are deleted
and dynamic memory allocation was rewritten into static memory
allocation. While the original version of the garbage collector in the
BEAM interpreter is based on the mark-and-sweep method withtwo dynamic regions, our prototype adopted rather simple method
which alternatively use two statically allocated regions. As for thedata structure to bookkeep processes and the routines for message
passing, simple versions that met our requirements were newly
coded. Verilog HDL codes of the library modules L0, L1, iport0 andoport1 were synthesized from these C programs by ACAP.
TABLE 1 summarizes the metrics of the hardware, implemented
as circuits in an FPGA (�eld programmable gate array; a programmable
logic device), synthesized from the Erlang speci�cation in Figure
2 (with the structure in Figure 9). “LUTs”, “FFs” and “delay” arethe numbers of the LUTs (look-up tables, or the logic gates of
the FPGA) and �ip-�ops (registers), and the critical path delay,
respectively, obtained by Xilinx Vivado (2015.4) targeting Artix7 (xc7a100tcsg324-3). For the readers’ reference, the �gures for a
MIPS R3000 compatible CPU core are listed.
The bus, arbiter, and I/O modules are small enough, for they havebeen manually designed in Verilog HDL. Considering the amountof the tasks performed by the processes, the hardware may be toolarge. The sizes of the library modules are also a little too large.
This is because we have just succeeded in generating Verilog HDLfrom Erlang or C codes and have not done much optimization yet.
We have not tested the behavior of the synthesized Verilog codes,
though the behavior of the library modules were tested in the C
program level on PC (with x86 CPU), and the protocols regarding

Distributed Memory Architecture for High-Level Synthesis of Embedded Controllers
from Erlang
Table 1. Synthesis result of Erlang code in Figure 2.

bus
arbiter
I/O
P0
P1
GC
L0
L1
iport0
oport1MIPS R3000

LUTs
172
156
300
4,480
4,788
13,185
12,33812,023
10,700
496
3,166

FFs
212
51
162
806
741
1,260
1,346
1,380
1,259
162
1,773

also much room for optimization in generating CDFG from BEAM
codes.

delay [ns]
3.654
3.659
5.825
8.836
9.217
12.82813.25713.44712.652
5.625
11.698

Acknowledgments
Authors would like to express their appreciation to Prof. Hiroyuki
Tomiyama of Ritsumeikan University, and Mr. Takayuki Nakatani(formerly with Ritsumeikan University) for their discussion andvaluable comments. We would like to thank Mr. Hinata Takebayashi(formerly with Kwansei Gakuin University) who have developed
the initial version of the BEAM to CDFG compiler. We would also
like to thank to all the members of Ishiura Lab. of Kwansei Gakuin
University. This work is partly supported by JSPS KAKENHI underGrant Nos. 16K00088 and 16K01207.

Logic synthesis: Vivado 2015.4, target: Artix-7

References[1] Joe Armstrong. 2007. Programming Erlang: Software for a Concurrent World, Pragmatic Bookshelf.
[2] Brian Chamberlain. Using Erlang on the RaspberryPi to Interact with the PhysicalWorld. Retrieved February 4, 2016 from h�p://www.slideshare.net/breakpointer/using-erlang-on-the-raspberrypi.
[3] Daniel D. Gajski, Nikil D. Dutt, Allen C-H Wu, and Steve Y-L Lin. 1992. High-Level
Synthesis: Introduction to Chip and System Design. Kluwer Academic Publishers.
[4] Seiya Shibata, Shinya Honda, Hiroyuki Tomiyama, and Hiroaki Takada. 2010. Advanced SystemBuilder: A Tool Set for Multiprocessor Design Space Exploration. In
Proceedings of the International SoC Design Conference (ISOCC 2010). (November2010). 79–82.
[5] Nagisa Ishiura, Hiroyuki Kanbara, and Hiroyuki Tomiyama. ACAP: Binary Synthesizer Based on MIPS Object Codes. In Proceedings of International TechnicalConference on Circuit/Systems, Computers and Communications (ITC-CSCC 2014).
(July 2014). 725–728.
[6] Hinata Takebayashi, Nagisa Ishiura, Kagumi Azuma, Nobuaki Yoshida, and Hiroyuki Kanbara. 2016. High-Level Synthesis of Embedded Systems Controller
from Erlang. In Proceedings of the Workshop on Synthesis And System Integrationof Mixed Information Technologies (SASIMI 2016). (October 2016). 285–290.
[7] IEEE Computer Society. 2001. IEEE Standard Verilog Description Language (IEEEStandard 1364-2001), IEEE, New York, NY, USA.
[8] IEEE Computer Society. 2008. IEEE Standard VHDL Language (IEEE Standard
1076-2008), IEEE, New York, NY, USA.

arbitration of send and GC requests were tested by cycle-accurate
simulation with models written in C.

6

Erlang’17, September 8, 2017, Oxford, UK

Conclusion

This paper has presented a distributed memory architecture forhigh-level synthesis from control speci�cation of embedded systems by Erlang. A prototype synthesizer has been implemented
which has generated Verilog codes from a simple example.
Currently, the resulting hardware is still too large for practicaluse. We are now working on reduction of redundancies and various
optimization measures on process modules and library modules.
For example, a library modules is almost a �nite state machine,
except for functions to copy heap data structs and message queue
manipulation, so it can be written in Verilog HDL rather than C,
which drastically reduces the resulting hardware size. There are19