4. Hardware Architecture

This section describes the hardware architecture produced by LegUp.

4.1. Circuit Topology

Each C/C++ function corresponds to a hardware module in Verilog. For instance, if we have a software program with the following call graph:

_images/hwarch_callgraph.png

where main calls a, b, and d, each of which calls c, c, and e, respectively. Notice that function c is called by both a and b. One way to create this system in hardware is to instantiate one module within another module, in a nested hierarchy, following how the functions are called in software:

_images/circuit_arch_nested.png

This architecture is employed by some of the other HLS tools, but it can create an unnecessary replication of hardware. Notice how module c has to be created twice, since the function c is called from different parent functions. In LegUp, we instantiate all modules at the same level of hierarchy, and automatically create the necessary interconnect to connect them together.

_images/circuit_arch_flat.png

This prevents modules from being unnecessarily replicated, saving area. The hardware system may also use a functional unit (denoted as FU in the figure), such as a floating-point unit, which is also created at the same level. This architecture also allows such units, which typically consume a lot of area, to be shared between different modules.

Note

For a small function, or for a function that is only called once in software, LegUp may decide to inline the function into its parent function to improve performance. Any inlined function is included as part of its parent function, so there will not be a separate module in the Verilog for the inlined function. Thus you may not find all the software functions in the generated hardware.

4.1.1. Threaded Hardware Modules

When Pthreads are used in software, LegUp automatically compiles them to concurrently executing modules. This is synonymous to how multiple threads are compiled to execute on multiple processor cores in software. By default, each thread in software becomes an independent hardware module. For example, forking three threads of function a in software creates three concurrently executing instances of module a in hardware.

4.2. Memory Architecture

LegUp stores any arrays (local or global) and global variables in a memory. We describe below what type of memories they are, as well as where the memories are stored.

In LegUp, there exists four hierarchies of memories: 1) Local memory, 2) shared-local memory, 3) aliased memory, and 4) I/O memory. Local, shared-local, and aliased memories exist in the generated hardware. I/O memories are data that are inputs/output to/from the generated hardware. They exist outside of the generated hardware (LegUp does not instantiate memories for them), where top-level memory interfaces are created for them.

4.2.1. Local Memory

LegUp uses points-to analysis to determine which memories are used by which functions. If a memory is determined to be used by a single function, where the function is to be compiled to hardware, that array is implemented as a local memory. A local memory is created and connected directly inside the module that accesses it.

Local memories have a latency of 1 clock cycle by default. The local memory latency can be changed with the set_operation_latency Tcl parameter.

4.2.2. Shared-Local Memory

If a memory is accessed by multiple functions, where all the functions that access it are to be compiled to hardware, the memory is designated as a shared-local memory. A shared-local memory is instantiated outside the modules (at the same level of hierarchy as the modules themselves, as shown for functions and FU in the diagram above), and memory ports are created for the modules to connect to the memory. Arbitration is automatically created to handle contention for a shared-local memory. LegUp automatically optimizes the arbitration logic, so that if the modules that access the memory are executing sequentially, a simple OR gate is used for arbitration (which consumes only a small amount of area), but if the accessing modules are executing concurrently (with the use of Pthreads), a round-robin arbiter is automatically created to handle contention.

Shared-local memories have a latency of 1 clock cycle. The shared-local memory latency can be changed with the set_operation_latency Tcl parameter.

4.2.3. Aliased Memory

There can be cases where a pointer can point to multiple arrays, causing pointer aliasing. These pointers need to be resolved at runtime. We designate the memories that such a pointer can refer to as aliased memories, which are stored in a memory controller (described below). A memory controller contains all memories that can alias to each other, and allows memory accesses to be steered to the correct memory at runtime. There can be multiple memory controllers in a system, each containing a set of memories that alias to each other.

Aliased memories have a latency of 2 clock cycles. The aliased memory latency can be changed with the set_operation_latency Tcl parameter.

4.2.3.1. Memory Controller

The purpose of the memory controller is to automatically resolve pointer ambiguity at runtime. The memory controller is only created if there are aliased memories. The architecture of the memory controller is shown below:

_images/memory_controller.png

For clarity, some of the signals are combined together in the figure. Even though the figure depicts a single-ported memory, all memories are dual-ported by default, unless only a single memory access is needed per cycle, in which case it will be single-ported memory. The memory controller steers memory accesses to the correct RAM, by using a tag, which is assigned to each aliased memory by LegUp. At runtime, the tag is used to determine which memory block to enable, with all other memory blocks disabled. The same tag is used to select the correct output data between all memory blocks.

4.2.4. I/O Memory

Any memory that is accessed by both the software testbench (parent functions of the top-level function) and hardware functions (the top-level functions and its descendants) becomes an I/O memory. These are any non-constant arguments for top-level function or global variables that are accessed by both the software testbench and hardware functions. I/O memories become memory interfaces of the top-level module for the generated hardware, where no actual memories are instantiated within the generated hardware for them. For more information on interfaces, please refer to Top-Level RTL Interface.

4.2.5. Memory Implementation

By default, each local, shared-local, and aliased memories are stored in a separate dual-ported on-chip RAM, where each RAM allows two accesses per clock cycle. All local memories can be accessed in parallel. All shared-local memories can be accessed concurrently when there are no accesses to same memory in the same clock cycle. If there are concurrent accesses to the same RAM, arbitration logic handles the contention automatically and stalls the appropriate modules. All independent memory controllers can also be accessed in parallel, but aliased memories which belong to the same memory controller will be accessed sequentially.

4.2.5.1. Memory Optimizations

LegUp automatically stores each single-element global variable (non-array) in a set of registers, rather than a block RAM, to reduce memory usage and improve performance. A block RAM has a minimum read latency of 1 clock cycle, where a register can be read in the same clock cycle (0 cycle latency). For small arrays, LegUp may decide to split them up and store individual elements in separate registers. This allows all elements to be accessed at the same time. If an array is accessed in a loop, and the loop is unrolled, LegUp also may decide to split up the array.

If only up to a single memory accessed is needed per cycle for a memory, LegUp will instantiate a single-ported RAM, otherwise a dual-ported RAM will be used. If a memory is only ever read from, LegUp will convert the memory to a read-only memory (ROM), even if the corresponding array is not declared as a constant in software. If a memory is not accessed at all, LegUp will automatically optimize away the memory.

4.3. Interfaces

Please refer to the Top-Level RTL Interface section for a detailed description on the interfaces that are created by LegUp.