Experimental: Synchronization
Calyx's default semantics do not admit any predictable form of language-level synchronization in presence of parallelism. We're currently experimenting with a suite of new primitives that add synchronization to the language.
std_sync_reg
The std_sync_reg
primitive defined by primitives/sync.futil
provides a synchronizing
register that acts as an M-structure which provides the following interface:
On the reader side:
- If the register is "empty", block the read till the register is written into.
- If the register is "full", provide the value to the reader, provide a
done
signal, and mark it as "empty".
On the writer side:
- If the register is "empty", write the value in the register, mark it as "full", and provide a
done
signal. - If the register is "full", block the write till the register is read from.
One way to think of this interface is as a size-1 concurrent FIFO.
Using std_sync_reg
The following example is a part of the Calyx compiler test suite and can be executed using:
runt -i examples/sync
The synchronizing register interface is non-standard: it provides two go signals and two done signals to initiate parallel reads and writes.
primitive std_sync_reg[WIDTH](
@write_together(1) in: WIDTH,
read_en: 1,
@write_together(1) write_en: 1,
@clk clk: 1,
@reset reset: 1
) -> (
out: WIDTH,
write_done: 1,
read_done: 1,
blocked: 1
);
The signal read_en
is used by a program to initiate a read operation while
the write_en
signal initiates a write operation.
We need to explicitly initiate a read operation because reading a value marks
the register as "empty" which causes any future reads to block.
Similarly, the output interface specifies the read_done
and write_done
signals
which the user program needs to read to know when the operations are completed.
The read_done
signal is similar to a valid
signal while the write_done
is
similar to a write_done
signal.
The following group initiates a write operation into the synchronizing register imm
from the memory in
:
// Write value from `in[idx]` to sync intermediate.
group write_imm {
imm.write_en = 1'd1;
imm.in = in.read_data;
in.addr0 = idx.out;
write_imm[done] = imm.write_done;
}
The group waits for the imm.write_done
signal to be high before continuing
execution.
If the synchronizing register was "full" in this cycle, the execution would
stall and cause the group to take another cycle.
The following group initiates a read the synchronizing register imm
and saves
the value into the out
memory:
// Read value from sync intermediate and write to temp.
group read_imm {
imm.read_en = 1'd1;
out.write_en = imm.read_done;
out.addr0 = idx.out;
out.write_data = imm.out;
read_imm[done] = out.done;
}
The group waits till the imm.read_done
signal is high to write the value into
the memory.
Note that in case the register is empty, imm.read_done
will be low and cause
the group to another cycle.
Finally, we can describe the control program as:
while lt.out with cmp {
seq {
par {
read_imm;
write_imm;
}
incr_idx;
}
}
Note that the two groups execute in parallel which means there is no guarantee to their order of execution. However, the synchronization ensures that the reads see a consistent set of writes in the order we expect.
Limitations
The example above implements a standard producer-consumer.
However, as implemented, the std_sync_reg
primitive does not support multiple
producers or consumers.
To do so, it would need to provide an interface that allows several read and
write ports and ensure that only one read or write operation succeeds.
This capability would be useful in implementing synchronizing barriers in Calyx.