D D Santambrogio
email: marco.santambrogio@polimi.it

C B Sciuto

G Ciobanu
email: c.b.ciobanu@uva.nl

A L Stramondo

Varbanescu

L Stornaiuolo
email: luca.stornaiuolo@polimi.it

M Rabozzi
email: marco.rabozzi@polimi.it

M. D Santambrogio

D Sciuto

C B Ciobanu
email: c.b.ciobanu@tudelft.nl

G Stramondo
email: g.stramondo@uva.nl

A L Varbanescu
email: a.l.varbanescu@uva.nl

Building High-Performance, Easy-to-Use Polymorphic Parallel Memories with HLS

Keywords: Polymorphic Parallel Memory, High Level Synthesis, FPGA

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The success of High-Level Languages (HLLs) for non-traditional computing systems, like Field Programmable Gate Arrays (FPGAs), has accelerated the adop-tion of these platforms for general purpose computing. In particular, the main hardware vendors released tools and frameworks to support their products by allowing the design of optimized kernels using HLLs. This is the case, for example, for Xilinx, which allows using C++ or OpenCL within the Vivado Design Suite (1) to target FPGAs. Moreover, FPGAs are increasingly used for dataintensive applications, because they enable users to create custom hardware accelerators, and achieve high-performance implementations with low power consumption. Combining this trend with the fast-paced development of HLLs, more and more users and applications aim to experiment with FPGA accelerators.

In the effort of providing HLL tools for FPGA design, some of the features used by hardware design experts are difficult to transparently integrate. One such feature is the efficient use of BRAMs, the FPGA distributed, high-bandwidth, on-chip memories [START_REF] Weinhardt | Memory access optimisation for reconfigurable systems[END_REF]. BRAMs can provide memory-system parallelism, but their use remains challenging due to the many different ways in which data can be partitioned in order to achieve efficient parallel data accesses. Typical HLL solutions allow easy-to-use mechanisms for basic data partitioning. These mechanisms work well for simple data access patterns, but can significantly limit the patterns for which parallelism (and thus, increased performance) can be achieved. Changing data access patterns on the application side is the current state-of-the-art approach: by matching the application patterns with the simplistic partitioning models of the HLL, one can achieve parallel operations and reduce the kernel execution time. However, if at all possible, this transformation also requires extensive modification of the application code, which is cumbersome and error-prone to the point of canceling the productivity benefits of HLLs.

To address the challenges related to the design and practical use of parallel memory systems for FPGA-based applications, PolyMem, a Polymorphic Parallel Memory, was proposed [START_REF] Ciobanu | Maxpolymem: High-bandwidth polymorphic parallel memories for dfes[END_REF]. PolyMem is envisioned as a high-bandwidth, twodimensional (2D) memory used to cache performance-critical data on the FPGA chip, making use of the distributed memory banks (the BRAMs). PolyMem is inspired by the Polymorphic Register File (PRF) (4), a runtime customizable register file for Single Instruction, Multiple Data (SIMD) co-processors. Poly-Mem is suitable for FPGA accelerators requiring high bandwidth, even if they do not implement full-blown SIMD co-processors on the reconfigurable fabric.

The first hardware implementation of the Polymorphic Register File was designed in System Verilog [START_REF] Ciobanu | Scalability Study of Polymorphic Register Files[END_REF]. MAX-PolyMem is the first prototype of Poly-Mem written entirely in MaxJ, and targeted at Maxeler Data Flow Engines (DFEs) (3; 6). Our new HLS PolyMem is an alternative HLL solution, proven to be easily integrated with the Xilinx toolchains. The current work is an extension of our previous implementation presented in [START_REF] Stornaiuolo | Hls support for polymorphic parallel memories[END_REF].

Figure 1 depicts the architecture of a system using (HLS-)PolyMem. The FPGA board (with a high-capacity DRAM memory), is connected to the host CPU through a PCI Express link. PolyMem acts as a high-bandwidth, 2D parallel software cache, able to feed an on-chip application kernel with multiple data elements every clock cycle. The focus of this work is to provide an efficient implementation of PolyMem in Vivado HLS, and employ it to maximize memory-accesses parallelism by exploiting BRAMs; we empirically demonstrate the gains we get from PolyMem by comparison against the partitioning of BRAMs, as provided by Xilinx tools, for three case-studies. In this work, we provide empirical evidence that HLS-PolyMem provides significant improvements in terms of both performance and usability when compared with the current memory partitioning approach present in Vivado HLS. To this end, we highlight the following novel aspects of this work:

• We provide a new, complete, open-source implementation 4 of PolyMem for Vivado HLS. This new implementation contains all the memory access schemes supported by the original PRF, as well as its multiview feature. Our implementation can be easily integrated within the Xilinx Hardware-Software Co-Design Workflow; • We present a basic, high-level PolyMem interface (i.e., a rudimentary API for using PolyMem). The API includes basic parallel read and write operations. Furthermore, our API was further extended to support masked writes, avoiding overwrites and further reduce latency. For example, when PolyMem supports wide parallel access (e.g., 8 elements), but the user requires less data to be stored (e.g., 5 elements), and wants to avoid overwriting existing data (e.g., the remaining 3 elements). We demonstrate the use of the API in all the applications discussed in this paper (synthetic and real-life examples alike); • We design and prototype a synthetic, parameterized microbenchmarking framework to thoroughly evaluate the performance of HLS-PolyMem. Our microbenchmarking strategy is based on chains of operations using one or several parallel access patterns, thus stressing both the performance and flexibility of the proposed parallel memory. The framework is extended to enable the comparison against existing HLS memory partitioning schemes. Finally, we show how to use these microbenchmarks to provide an extensive analysis of HLS-PolyMem's performance. • We design, implement, and analyze in detail two case-study applications which demonstrate the ability of our HLS-PolyMem to cope with real applications and data, multiple memory access patterns, and tiling. Our experiments for these case-studies focus on performance, resource-utilization, and productivity, and contrast our HLS PolyMem with standard memory partitioning techniques.

Our results, collected for both synthetic and real-life case-studies, thoroughly demonstrate that HLS PolyMem outperforms traditional HLS partitioning schemes in performance and usability. We therefore conclude that our HLS-PolyMem is the first approach that enables HLS programmers to use BRAMs to construct flexible, multiview parallel memories, which can still be easily embedded in the traditional HLS modus operandi.

The remainder of this paper is organized as follows. Section 2 provides an introduction to parallel memories, and discusses the two alternative implementations presented in this work: the PRF-inspired PolyMem and the HLS partitioning schemes. Section 3 presents the HLS PolyMem class for Vivado, together with the proposed optimizations. In Section 4 we present our microbenchmarking framework, as well as the our in-depth evaluation using this synthetic workload. Section 5 describes our experience with designing, implementing, and evaluating the two case studies. Section 6 highlights relevant related work and, finally, our conclusion and future work directions are discussed in Section 7.

2 Parallel Memories: Challenges and Solutions A parallel memory can be realized by combining a set of independent memories, referred to as banks or lanes. The width of the parallel memory, i.e., the number of banks used in the implementation, represents the maximum number of elements that can be read in parallel. The capacity of the parallel memory refers to the amount of data that it can store. A specific element contained in a PM is identified by its location, a combination of a memory module identifier (to specify which one of the sequential memories hosts the data) and an in-memory address (to specify where within that memory the element is stored).

Depending on how the information is stored and/or retrieved from the memory, we distinguish three types of parallel memories: redundant, non-redundant, and hybrid.

Redundant PMs. The simplest implementation of a PM is a fully redundant one, where all M sequential memory blocks contain fully replicated information. The benefit of such a memory is that it allows an application to access any combination of M data elements in parallel. However, such a solution has two major drawbacks: first, the total capacity of a redundant PM is M times lower than the combined capacities of all its banks, and, second, parallel writes are very expensive in order to maintain information consistency.

To use such a memory, the application requires minimal changes, and the architecture is relatively simple to manage.

Non-Redundant PMs. Non-redundant PMs completely avoid data duplication: each data item is stored in only one of the M banks. The one-to-one mapping between the coordinate of an element in the application space and a memory location is part of the memory configuration. These memories can use the full capacity of all the memory resources available, and data consistency is guaranteed by avoiding data replication, making parallel writes feasible as well. The main drawback of non-redundant parallel memories is that they require additional logic -compared to redundant memories -to perform the mapping, and they restrict the possible parallel accesses: if two elements are stored in the same bank, they cannot be accessed in parallel. There are two major approaches used to implement non-redundant PM: (1) use a set of predefined mapping functions that enable parallel accesses in a set of predefined shapes (4; 8; 9; 10), or, (2) derive an application-specific mapping function (11; 12). For the first approach, the application requires additional analysis and potential changes, while the architecture is relatively fixed. For the second approach, however, a new memory architecture needs to be implemented for every application, potentially a more challenging task when the parallel memory is to be implemented in hardware.

Hybrid PMs. Besides the two extremes discussed above, there are also hybrid implementations of parallel memories, which combine the advantages of the two previous approaches by using partial data redundancy [START_REF] Scheideler | Exploiting storage redundancy to speed up randomized shared memory simulations[END_REF]. Of course, in this case, the challenge is to determine which data should be replicated and where. In turn, this solution requires both application and architecture customization.

The Polymorphic Register File and PolyMem

A PRF is a parameterizable register file, which can be logically reorganized by the programmer or a runtime system to support multiple register dimensions and sizes simultaneously (4). The simultaneous support for multiple conflict-free access patterns, called multiview, is crucial, providing flexibility and improved performance for target applications. The polymorphism aspect refers to the support for adjusting the sizes and shapes of the registers at runtime. Table 1 presents the PRF multiview schemes (ReRo, ReCo, RoCo and ReTr), each supporting a combination of at least two conflict-free access patterns. A scheme is used to store data within the memory banks of the PRF, such that it allows different parallel access types. The different access types refer to the actual data elements that can be accessed in parallel. PolyMem reuses the PRF conflict-free parallel storage techniques and patterns, as well as the polymorphism idea. Figure 2(a) illustrates the access patterns supported by the PRF and PolyMem. In this example, a 2D logical address space of 8 × 9 elements contains 10 memory Regions (R), each with different size and location: matrix, transposed matrix, row, column, main and secondary diagonals. In a hardware implementation with eight memory banks, each of these regions can be read using one (R1-R9) or several (R0) parallel accesses. c i , c j (i, j, Access Type) &A(c i , c 4) design. The inputs are the matrix indexes (i, j) pointing to the first cell of the block of data the user wants to read/write in parallel, and the AccessType to select the shape of the parallel access. By design, the PRF optimizes the memory throughput for a set of predefined memory access patterns. For PolyMem, we consider p × q memory modules and the five parallel access schemes presented in Table 1. Each scheme supports dense, conflict-free access to p • q elements. When implemented in reconfigurable technology, PolyMem allows application-driven customization: its capacity, number of read/write ports, and the number of lanes can be configured to best support the application needs.

The block diagram in Figure 2(b) shows, at high level, the PRF architecture. The multi-bank memory is composed of a bi-dimensional matrix containing p×q memory modules. This enables parallel access to p•q elements in one memory operation. The inputs of the PRF are shown at the top of the diagram. AccessType represents the parallel access pattern. (i, j) are the top-left coordinates of the parallel accesse. The list of elements to access is generated by the AGU module and is sent to the A and m modules: the A module generates one in-memory address for each memory bank in the PRF, while the m module applies the mapping function of the selected scheme and computes, for each accessed element, the memory bank where it is stored. The Data Shuffle block reorders the Data In/Out, ensuring the PEF user obtains the accessed data in their original order.

Matrix storage in a parallel memory

Figure 3 compares two ways for a 6×6 matrix to be mapped in BRAMs to enable parallel accesses. Thus, the default Vivado HLS partitioning techniques with a factor of 3 is compared against a PolyMem with 3 memory banks, organized exploiting the PolyMem RoCo scheme. The memory banks, in this case, are organized in a 1 × 3 structure, allowing parallel access to rows and columns of three, eventually unaligned, elements. The left side of Figure 3 shows an example of a matrix to be stored in the partitioned BRAMs, aiming to achieve read/write parallelism. The right side illustrates three techniques used to partition the matrix, using two unaligned, parallel accesses of 3 elements (gray and black in the figure), starting respectively from the cells containing elements 8 and 23. The HLS Array Partitioning techniques enable either the black or the gray access to be performed in parallel (for Block and Cyclic, respectively). Using PolyMem with a RoCo scheme, each element of each access is mapped on a different memory bank; in turn, this organization enables both the gray and the black access to happen in a single (parallel) operation 5 . This section describes the main components of our PolyMem implementation for Vivado HLS. The goal of integrating PolyMem in the Xilinx workflow is to provide users with an easy-to-use solution to exploit parallelism when accessing data stored on the on-chip memory with different access patterns.

Our Vivado HLS PolyMem implementation exploits all the presented five schemes (ReO, ReRo, ReCo, RoCo, ReTr) to store on the FPGA BRAMs the data required to perform the application operations. Compared to the default Vivado memory partitioning techniques, which allow hardware parallelism with a single access pattern, a PolyMem employing a multiview scheme allows multiple types of access simultaneously for unaligned data with conservative hardware resources usage.

We implemented a template-based class polymem that exploits loop unrolling to parallelize memory accesses. When HLS PolyMem is instantiated within the user application code, it is possible to specify DATA T, i.e., the type of data to be stored, the (p × q) number of internal banks of memory (i.e.,the level of parallelism), the (N × M ) dimension of the matrix to be stored (also used to compute the depth of each bank of data), and the scheme to organize data within the different banks of memory. Listing 1.1 presents the interfaces of methods that allow accesses to data stored within PolyMem. Simple read and write methods use the m and A modules (described in Section 2.2) to compute, respectively, the address and the depth of the bank of memory in which the required data is stored or needs to be saved. On the other hand, the read block and the write block exploit optimized versions of m and A to read/write (q • p) elements in parallel, while limiting the hardware resources used to reorder data. Finally, we optimized the memory access operations by implementing a write block masked method to specify which data in the block has to be overwritten within PolyMem. As an example, this method is useful when PolyMem supports a wide parallel access (e.g., 8 elements), but the user requires less data to be stored (e.g., 5 elements), and wants avoid overwriting existing data (e.g., the remaining 3 elements). In this Section, we focus on the evaluation of HLS PolyMem. The evaluation is based on a synthetic benchmark, where we demonstrate that PolyMem offers a high-performance, high-productivity alternative to partitioned memories in HLS.

Experimental setup

We present the design and implementation of our microbenchmarking suite, and detail the way all our measurements are performed. All the experiments in this section are validated and executed on a Xilinx Virtex-7 VC707 board (part xc7vx485tffg1761-2), with the following hardware resources: 303600 LUTs, 607200 FFs, 1030 BRAMs, and 2800 DSPs. We instantiate a Microblaze processor on the FPGA to control the DMA that transfers data between the FPGA board DRAM memory and the on-chip BRAMs where the computational kernel performs memory accesses. The Microblaze also starts and stops an AXI Timer to measure the execution time of each experiment. The data transfers to and from the computational kernel employ the AXI Stream technology.

Microbenchmark design. To provide an in-depth evaluation of our Polymorphic memory, we designed a specific microbenchmark which tests the performance of PolyMem together with its flexibility -i.e., its ability to cope with applications that require different parallel access types to the same data structure. Moreover, we compare the results of the Polymem-augmented design with the ones achievable by partitioning the memory with the default techniques available in Vivado HLS. To ensure a fair comparison, we utilize a Vivado HLS Cyclic array partition with a factor equal to the number of PolyMem lanes (both designs can access at most p • q data elements in parallel from the BRAMs).

The requirements we state for such a microbenchmark are:

1. Focus on the reading performance of the memory, in terms of bandwidth; 2. Support all access types presented in Section 2.2; 3. Test a combination of more access types, to further demonstrate the flexibility of polymorphism; 4. Measure the overall bandwidth achieved by these memory transfers.

To achieve these requirements, we designed different computational kernels (IP Cores) that perform a (configurable) number of parallel memory reads, from various locations inside the memory, using different parallel access patterns. Each combination of parallel reads is performed in two different scenarios. The accessed on-chip FPGA memory (BRAMs) M, where the input data are stored, is partitioned by using (1) the default techniques available in Vivado HLS, and (2) the HLS PolyMem technology.

A high-level description of the operations executed by the computational kernels and measured by the timer is presented in Listing 1.2. Memory M is used to store the input data and it is physically implemented in partitioned BRAMs. The kernel receives the data to fill the memory M and N READS matrix coordinates to perform parallel accesses with different access types -i.e., given an access type and the matrix coordinates (i, j), the computational kernel reads a block of data starting from (i, j) and following the access type. When the memory reads are done, the kernel sends sampled results on the output stream. By comparing the performance results of HLS-partitioning and PolyMem, we are able to assess which scheme provides both performance and flexibility, and, moreover, provide a quantitative analysis of the performance gap between the two. We provide more details on how the measurements are performed in the following paragraphs.

The complete code used for all the experiments described in this section is available in our code repository 6 .

Measurement setup

In order to measure the performance of the two different parallel memory microbenchmaks, we propose a setup as presented in Figure 4. Specifically, in this diagram, "Memory" is either an HLS-partitioned memory, or an instance of PolyMem (as described in the previous paragraph). In order to measure the performance of the two memories, we propose an approach based on the following steps.

1. Measure, on the Microblaze processor, the overhead of phases 1 and 3. We note that phases 1 and 3 are implemented using the basic streaming constructs provided by the AXI Stream technology. We achieve this by a onetime measurement where no memory reads or only one memory read are performed. 2. Measure, on the Microblaze processor, the execution time of the complete setup, from the beginning of phase 1 to the end of phase 3. Due to the explicit synchronization between phases 1, 2, and 3, we can guarantee that no overlap happens between them. 3. Determine, by subtraction, the absolute execution time of phase 2 alone, which is a measure of the parallel memory's reading performance. 4. Present the absolute performance of the two memories in terms of achieved bandwidth. For the case of PolyMem, we can also assess the efficiency of the implementation by comparing the achieved bandwidth with that predicted by the theoretical performance model ( 14). 5. Present the relative performance of the two parallel memories as speedup.

We calculate speedup as the ratio of the execution time of of HLS-based partitioning solution over the execution of the PolyMem-based solution. We chose to use the entire execution time, including the copy overhead, as an estimate of a realistic benchmark when the same architecture is used for real-life applications. We note that this choice is pessimistic, as the overhead of phases 1 and 3 can be quite large.

Results

All the results presented in this section are from experiments performed using the settings in Table 2. The input data stream employs double precision (64-bit) numbers, and the computational kernel receives an amount of data (equal for all the experiments), that includes the input matrix and the list of coordinates (i, j):

N IN DATA = (DIM • DIM) + (N READS • 2) = 15360 64-bit elements
The number of data that the computational kernel reads from the memory is computed as follow:

N READ DATA = (N READS • BLOCK SIZE) = 49152 64-bit elements
The output data stream employs double precision 64-bit numbers, and the computational kernel sends back to the microblaze a sample of the results (data read), equal for all the experiments, amounting to:

N OUT DATA = (N RESULTS BLOCKS•BLOCK SIZE) = 800 64-bit elements
To measure the overheads introduced by the data transfers in terms of hardware resources utilization and execution time, we implemented two computational kernels: the first one does not perform any memory accesses (the BRAMs are not even partitioned) and the second one performs only one memory access (the added execution time of this one access is negligible). The second kernel was executed for both memory configurations (HLS Cyclic and PolyMem). The results are shown in Table 3. The consistent execution time indicates that the overhead is systematic and constant. Given the data transfers execution time overhead equal to 265 ns, we can compute the bandwidth (BW) in GB/s for each new experiment with the following formula:

BW [B/s] = N READS * BLOCK SIZE * 8 (Exec. time -overhead)
In Table 4, we report the detailed results of our microbenchmarking experiments, in terms of hardware resource utilization, execution time, and bandwidth. We provide results for the two different memory configurations and all PolyMem access schemes. As shown in Listing 1.2, the memory accesses are equally divided among the access patterns supported by the selected scheme. We further note that, for all the schemes, the speedup of the end-to-end computation (i.e., phases 1, 2 and 3 from Figure 4) is 1.78x. For the actual computation, using the parallel memory (i.e., without the data transfer overhead), the PolyMem outperforms HLS partitining by as much as 13.22x times. Moreover, in terms of hardware resources, (1) the BRAM utilization is similar for both parallel memories, which indicates no overhead for PolyMem, (2) PolyMem is more economical in terms of "consumed" LUT and FF (up to 20% less), and (3) HLS partitioning makes use of DSPs, while PolyMem does not. The following paragraph contains an evaluation of these results. Unaligned accesses and final evaluation The results suggest that the Vivado HLS default partitioning techniques are not able to exploit parallel reads for the described access patterns. This is due to the fact that, even if the data are correctly distributed among the BRAMs to perform at least one access type, parallel accesses unaligned with respect to the partitioning factor are not supported. To prove that, we perform experiments where the memory reads are forced to be aligned with respect to the partitioning factor, for one of the access type -e.g. having a cyclic partitioned factor of 4 on the Ro access, it is possible to read 4 data in parallel at the coordinates {(i, j), (i, j+1), (i, j+2), (i, j+3)}, only if j is a multiple of 4. This is possible, at compile time, by using the integer division on the reading coordinates (i, j) as follows:

aligned j = j BLOCK SIZE * BLOCK SIZE
This ensures that aligned j is a multiple of the number of memory banksi.e. BLOCK SIZE. Using aligned j for the data access allows the HLS compiler to perform more aggressive optimizations parallelizing the access to the partitioned memory. Table 5 shows the results for the RoCo scheme with different combinations of access types, where forced aligned accesses are performed or not. The cases where the memory reads are aligned with respect to the partitioning factor are the only ones where the default Vivado HLS partitioning is able to achieve the same performance of PolyMem, while using fewer hardware resources. However, even in this cases, the default Vivado HLS partitioning is not able to perform all the memory accesses with the right amount of parallelism if the application requires multiple access patterns. Practical examples showing the advantages of using PolyMem are provided in the following section.

Application case-studies

In this Section, we analyze two case-study applications, i.e., matrix multiplication and Markov chain, that exploit our HLS PolyMem to parallelize accesses to matrix data. Each application demonstrates different HLS PolyMem features. In the matrix multiplication case-study, we show how our approach outperforms implementations that use the default partitioning of Vivado HLS. For the Markov Chain application, we show how HLS PolyMem enables performance gains with minimal changes to the original software code.

Matrix multiplication (MM)

With this case study, we aim to demonstrate the usefulness of the multiview property of HLS-PolyMem. Specifically, we investigate, in the context of a real application, two aspects: (1) if there is any performance loss or overhead between the two parallel memories for a single matrix multiplication, and ( 2) what is the performance gap between the two types of parallel memories in the case where multiple parallel access shapes are needed, on the same data structure, in the same application.

Single matrix multiplication. For our first experiment, the application performs one multiplication of two square matrices, B and C, of size DIM , that are stored by using either the default HLS array partitioning techniques or the HLS PolyMem implementation. Since the multiplication B × C is performed by accessing the rows of B and multiply-accumulating the data with the columns of C, it is convenient, when using HLS default partitioning, to partition B on the second dimension and C on the first one. Indeed, this allows to achieve parallel accesses to the rows of B and columns of C in the innermost loop of the computation.

On the other hand, for the HLS PolyMem implementation, we store both B and C in the HLS PolyMem , configured with a RoCo scheme, because it allows parallel accesses to both rows and columns.

Listings 1.3 and 1.4 show the declaration of the matrices and their partitioning using the HLS default partitioning and the HLS PolyMem, respectively. Both parallel memories use 16 lanes (i.e., data is partitioned onto 16 memory banks): the HLS partitioned scheme uses a parallel factor of 16, while the B and C HLS PolyMem instances are initialized with p = 4 and q = 4.

Double (mirrored) matrix multiplication

Even though both approaches achieve the goal of computing the matrix multiplication by accessing 16 matrix elements in parallel, the HLS PolyMem solution provides more flexibility when additional data access patterns are required, which is often the case for larger kernels. In order to highlight this aspect, we also consider a second kernel function, in which both the B × C and the C × B products need to be computed. This effectively means that the new kernel can only enable 16 parallel accesses for both multiplications if the matrices allow parallel reads in using both rowand column-patterns. 6 reports the latency and resource utilization estimated by Vivado HLS when computing the single matrix multiplication kernel (1MM), B × C (rows 1,2), and when computing the double multiplication (2MM's), B × C followed by C × B (rows 3,4 and 5,6) for the two parallel memories under consideration. As expected, when using the default Vivado HLS partitioning techniques, the second multiplication (C × B) cannot be computed efficiently due to the way in which the matrix data is partitioned into the memory banks, as described in Section 2. Indeed, C can only be accessed in parallel by rows and B by columns. On the other hand, the implementation based on HLS PolyMem is perfectly capable of performing both matrix products (B × C and C × B) efficiently. The performance data reflects this very well: the estimated latency reported in Table 6 is the same for both products in the PolyMem case, and drastically different in the case of HLS partitioning.

Results and analysis Table

It is also worth noting that for a matrix size of 32 × 32, the two approaches have similar resource consumption, while for matrices with larger dimensions and a parallel factor of 16, the HLS PolyMem has a resource consumption overhead in terms of FF and LUT of at most 8.5% compared to the HLS default partitioning schemes. Finally, in order to empirically validate the designs, we implemented the kernel module performing both B × C and C × B with matrix size of 96 and a parallel factor of 16 on a Xilinx Virtex-7 VC707 with a target frequency of 100MHz. The benchmarking system is similar to that presented in Section 4: a soft Microblaze core is used to manage the experiment, the input/output data (matrices B and C, and the result) are streamed into parallel memory, and the actual multiplication operations are performed using the parallel memory. For the kernel with a single multiplication, the performance of the two solutions is the same. However, for the kernel with the double multiplication, the HLS PolyMem version achieves an overall speedup of 5x compared to the implementation based on HLS memory partitioning.

Markov Chain and the Matrix power operation

With this case study, which has at its core the matrix power operation, we aim to reinforce the need for multiview accesses to the same data structure, and furtehr demonstrate how tiling can be easily achieved and used in conjuction with HLS-PolyMem, to further alleviate its resource overhead.

A Markov Chain is a stochastic model used to describe real-world processes. Some of its most relevant applications are found in queuing theory, the study of population growths [START_REF] Arsanjani | Integration of logistic regression, markov chain and cellular automata models to simulate urban expansion[END_REF], and in stochastic simulation methods such as Gibbs sampling [START_REF] Smith | Bayesian computation via the gibbs sampler and related markov chain monte carlo methods[END_REF] and Markov Chain Monte Carlo [START_REF] Gilks | Markov chain Monte Carlo in practice[END_REF]. Moreover, Page Rank ( 18), an algorithm used to rank websites by search engines, leverages a time-continuous variant of this model. A Markov Chain can also describe a system composed of multiple discrete states, where the probability of being in a state depends only on the previous state of the system.

A Markov Transition Matrix A, which is a variant of an adjacency matrix, can be used to represent a Markov Chain. In this matrix, each row contains the probability to move from the current state to any other state of the system. More specifically, given two states i and j, the probability to transition from i to j is a i,j , where a i,j is the element at row i and column j of the transition matrix A.

Computing the h-th power of the Markov Transition Matrix is a way to determine what is the probability to transition from an initial state to a final state in h steps. Furthermore, when the number of steps h tends to infinity, the result of A h can be used to recover the stationary distribution of the Markov Chain, if it exists.

From a computational perspective, an approximate value for the result of lim x→∞ A x is obtained for large enough values of x. In our implementation, matrix A is stored in a HLS PolyMem, so that both rows and columns can be accessed in parallel. We then compute A 2 and save the result into a support matrix A temp, partitioned on the second dimension. After A 2 is computed, we can easily compute A 2 h by copying back results to the HLS PolyMem and iterating the overall computation h times.

Listing 1.7 shows an HLS PolyMem-based algorithm that can be used to compute A 2 h . The implementation consists of an outermost loop repeated h times in which we compute the product A × A whose result is stored in A t emp and copied back to the PolyMem for A before the next iteration.

Implementing the same algorithm by using the HLS partitioning techniques, as presented in the previous case study, results in poor exploitation of the available parallelism, or in duplicated data, since A needs to be accessed both by rows and columns. The HLS PolyMem enables parallel accesses to matrix A for both rows and columns, but adds some overhead in terms of hardware resources and complexity of the logic to shuffle data within the right memory banks. The resources overhead has a quadratic growth with respect to the number p • q of parallel memories used to store data [START_REF] Ciobanu | Customizable Register Files for Multidimensional SIMD Architectures[END_REF].

A possible solution to this problem is a simple form of tiling, were we reduce the dimension of PolyMem by dividing the input matrix A and storing its values in a grid of multiple PolyMems. If A has DIM × DIM elements, it is possible to organize the on-chip memory to store data in a grid of b × b square blocks, each having size DIM b × DIM b . In order to preserve the same level of parallelism, we can re-engineer the original computation to work in parallel on the data stored in each memory within the grid. Instead of computing a single vectorized row-column product, it is possible to perform the computation on multiple rowcolumn products in parallel and reduce the final results.

Figure 5 shows how the input matrix is divided in multiple memories according to the choice of the parameters p, q and b. Moreover, the figure also shows which is the data accessed concurrently at each step of the computation. As an example, for the case p = q = b = 2 there are 4 row-column products performed in parallel (b 2 ) and for each of them 4 values are processed in parallel (p • q).

It is important to notice that when p = q = 1 the PolyMemreduces to memories in which a single element is accessed in parallel. In this case, each PolyMem can be removed and substituted by a single memory bank. components implemented by PolyMem with a level of parallelism of p × q. When both p and q are set to 1, it is possible to remove the HLS PolyMem logic.

In Table 7 we report the latency and the resource utilization estimated by Vivado HLS together with the number of lines of code (LOC) for different configurations of the parameters p, q and b on 8 iterations of the power operation for a 384x384 matrix. The numbers demonstrate that by re-engineering the code and the access patterns (b > 1), it is possible to achieve a smaller overall latency. However, this comes at the cost of a more convoluted code which is approximately twice as long, in terms of lines of code, as the original version. On the contrary, by using a single PolyMem (b = 1) we can still obtain higher performance than using the default HLS array partitioning techniques, with a much smaller and simpler code base. Indeed, PolyMem allows to reduce the time to develop an optimized FPGA-based implementation of the algorithm with minor modifications to the original software code. Thanks to HLS PolyMem we raise the level of abstraction of parallel memory accesses, thus enhancing the overall design experience and productivity. Finally, to validate the flexibility the HLS PolyMem library, we implemented and tested the application by using Xilinx SDx tool, that enables OpenCL integration and automatically generates the PCIe drivers for communication. In this case, the benchmarking follows a similar method as the one presented in Section 4.1 and Figure 4, with two ammendments: (1) instead of using the Microblaze softcore, we manage the experiment directly from the CPU of the host system where the FPGA board acts as an accelerator, and (2) the transfers from stages (1) and ( 3) are performed in blocks over the PCIe bus. We synthesized a design for a matrix size of 256 and parameters p = q = b = 2 at 200MHz, and we benchmarked its performance on the Xilinx Kintex Ultrascale ADM-PCIE-KU3 platform. The obtained throughput is 1.6GB/s. We note that this number is significantly lower than the expected performance of the HLS-PolyMem itself because it also includes the PCIe overhead. Without this overhead, the performance of the computation using the parallel memory alone is expected to be similar to the performance of a single PolyMem block with p × q lanes, running at 200MHz, which should be in the same order as that presented in Table 1 (i.e., 21 GB/s for a 16-lane HLS-PolyMem). In the 90s, more work has been devoted to investigating various addressing schemes and their implementation. For example, (9) investigates schemes based on linear addressing transformation (i.e., XOR schemes), and the use of these schemes for accessing memory in conflict-free manner using multiple strides, blocks, and FFT access patterns. In (21), another memory system design, enabling different parallel accesses to a 2D parallel memory is presented; their design is different in that it focuses on 2D memories to be accessed by arrays of 2D processing units, and thus their mapping and addressing functions are specialized.

SIMD processors have fueled more research in building and using parallel memories efficiently. For example, the use of memory systems that leverage a prime number of memory modules to provide parallel accesses for rectangles, rows, columns, and diagonals is investigated in [START_REF] Park | Multiaccess Memory System for Attached SIMD Computer[END_REF]; the authors prove the advantages in building fast mapping/addressing functions for such particular memories, an idea already envisioned and analyzed in [START_REF] Lawrie | The prime memory system for array access[END_REF]. In the same work [START_REF] Park | Multiaccess Memory System for Attached SIMD Computer[END_REF], Park also introduces a Multi Access Memory System, which provides access to multiple sub-array types, although it uses memory modules in a redundant manner. Research proposing an addressing function for 2D rectangular accesses, suitable for multimedia applications, is presented in [START_REF] Kuzmanov | Multimedia rectangularly addressable memory[END_REF]; the aim of this work is to minimize the number of required memory modules for efficient (i.e., full utilization) parallel accesses. The work in ( 24) also aims at the full utilization of the memory modules, introducing a memory system based on linear skewing (the same idea from 1971 [START_REF] Budnik | The Organization and Use of Parallel Memories[END_REF]) that support accesses to block and diagonal conflict-free accesses in a 2D space. ( 25) proposes a memory system with power of 2 memory modules able to perform strided access with a power of two interval in horizontal and vertical directions. The analysis of parallel memories is also refined -for example, the effect of using a parallel memory to the dynamic instruction count of an application is explored in [START_REF] Gou | Sams multi-layout memory: providing multiple views of data to boost simd performance[END_REF].

The PRF multiview access schemes -which are fundamental for this workare explained in detail in (4), together with the hardware design and implementation requirements. This work introduces an efficient HLS implementation of the PRF addressing schemes, greatly simplifying the deployment of PolyMem on FPGAs. Alternative schemes also exist. For example, the Linear-Transformation-Based (LTB) algorithm for automatic generation of memory partitions of multidimensional arrays, which is suitable for being used during FPGA HLS loop pipelining, is described in [START_REF] Wang | Memory partitioning for multidimensional arrays in high-level synthesis[END_REF]. The Local Binary Pattern (LBP) algorithm from [START_REF] Yin | Multibank memory optimization for parallel data access in multiple data arrays[END_REF] considers the case of multi-pattern and multi-array memory partitioning. [START_REF] Yang | Automatic Construction of Program-Optimized FPGA Memory Networks[END_REF] discusses the advantages of a hierarchical memory structures generated on tree-based network, as well as different methods for their automatic generation.

Building a memory hierarchy for FPGA kernels is recognized as a difficult, error-prone task (27; 28). For example, (28; 29; 30; 31; 32) focus on the design of generic, traditional caches. Moreover, the recently released High-Level Synthesis (HLS) tools for FPGAs [START_REF] Cong | Highlevel synthesis for fpgas: From prototyping to deployment[END_REF] provide a simple set of parallel access patterns to onchip memory starting from high-level languages implementations. More recently, work has been done on using the Polyhedral Model to automatically determine the module assignment and addressing funtions [START_REF] Wang | Theory and algorithm for generalized memory partitioning in high-level synthesis[END_REF]. By comparison, our work proposes a parallel, polymorphic memory which can be exploited from HLS tools and acts as a caching mechanism between the DRAM and the processing logic; instead of supporting placement and replacement policies, our memory is configured for the application at hand, and it is directly accessible for reading and writing. Moreover, PolyMem includes a multiView feature, enabling multiple conflict-free access types, a capability not present in other approaches [START_REF] Wang | Theory and algorithm for generalized memory partitioning in high-level synthesis[END_REF].

Application-specific caches have also been investigated for FPGAs (26; 35; 29), though none of these are polymorphic or parallel. For example, in [START_REF] Nalabalapu | Bandwidth management with a reconfigurable data cache[END_REF], the authors demonstrate why and how different caches can be instantiated for specific data structures with different access patterns. PolyMem starts from a similar idea, but, benefiting from its multi-view, polymorphic design, it improves on it by using a single large memory for all these data structures. Many of PolyMem's advantages arise from its PRF-based design (4), which is more flexible and performs better than alternative memory systems (37; 38; 39; 40); its high performance in scientific applications has also been proven for practical applications (41; 42; 43). As stated before, the first hardware implementation of the Polymorphic Register File was designed in System Verilog [START_REF] Ciobanu | Scalability Study of Polymorphic Register Files[END_REF]. MAX-PolyMem was the first prototype of PolyMem written entirely in MaxJ, and targeted at Maxeler DFEs (3; 6). Our new HLS PolyMem is an alternative HLL solution, proven to be easily integrated with the Xilinx toolchains.

In summary, compared to previous work on enabling easy-to-use memory hierarchies and/or caching mechanisms for FPGAs, PolyMem proposes a PRFbased design that supports polymorphic parallel accesses through a single, multiview, application-specific software cache. The previous HLS implementation (3) has demonstrated good performance, but was specifically designed to be used on Maxeler-based systems. Our current HLS-PolyMem is the most generic implementation to date, it preserves the advantages of the previous incarnations of the system in terms of performance and flexibility, and adds the ease-of-use of an HLS library that can be easily integrated in the design flow of modern tools like Vivado HLx and Vivado SDx.

Conclusion and Future Work

In this paper, we presented a C++ implementation of PolyMem optimized for Vivado HLS, ready-to-use as a library for applications requiring parallel memories. Compared to the naive optimizations using HLS array partitioning techniques, the HLS PolyMem implementation is better in terms of performance, provdides high flexibility in terms of supported parallel access patterns, and requires virtually zero implementation effort in terms of code re-engineering. Our design exposes an easy-to-use interface to enhance design productivity for FGPA-based applications. This interface provides methods for both the basic parallel read/write operations, and it is extended with to support masked onchip parallel accesses. Furthermore, we provide a full, open-source implementation of HLS-PolyMem, supporting all the original PolyMem schemes7 . Our evaluation, based on comprehensive microbenchmarking, demonstrates sustained high-performance for all these schemes. Our results demonstrate HLS-PolyMem achieves the same level of performance as HLS-partitioning for simple access patterns (i.e., rows and columns), and significant performance benefits compared with HLS-partitioning for more complex access patterns. We observe bandwidth improvement as high as 13x for complex access patterns combinations, which HLS partitioning simply cannot support.

We also proved the flexibility of the library among the Xilinx Design Tools, by implementing the kernels for both the Vivado workflow with a Virtex-7 VC707 and the SDx workflow with a Kintex Ultrascale 3 ADM-PCIE. Our empirical analysis of our library on two case studies (Matrix multiplication and Markov Chains) demonstrated competitive results in terms of latency, low code complexity, but also a small overhead in terms of hardware resource utilization.

Our future work focuses on three different directions. First, we aim to provide the usability of HLS for more case-studies, and further develop the API to better support end-users. Second, we aim to further improve the implementation of the HLS-PolyMem backend. For example, we consider improving the HLS Poly-Mem shuffle module by exploiting a Butterfly Network [START_REF] Avior | A tight layout of the butterfly network[END_REF] for the memory banks connections, and enhance our HLS implementation to support both standard and customized addressing. Third, we envision a wizard-like framework to automatically analyze the user application code, estimate the potential benefits of using HLS-PolyMem, and suggest how to actually embed the parallel memory in the code to reach the best possible performance.

Fig. 1 .

 1 Fig. 1. System organization using PolyMem as a parallel cache.

2. 1

 1 Parallel Memories Definition 1 (Parallel Memory). A Parallel Memory (PM) is a memory that enables the access to multiple data elements in parallel.

Fig. 2 .

 2 Fig.2. PRF (4) design. The inputs are the matrix indexes (i, j) pointing to the first cell of the block of data the user wants to read/write in parallel, and the AccessType to select the shape of the parallel access.

Fig. 3 .

 3 Fig.3. Comparison between different partitioning techniques offered by Vivado HLS (factor = 3) and the RoCo scheme of PolyMem, with 3 memory banks, for data stored in a 6 × 6 matrix. PolyMem allows 3 parallel data reads/writes, from the rows and the columns of the original matrix. Unaligned blocks are also supported.

Listing 1 . 2 .

 12 The structure of the proposed microbenchmark stream in data to fill memory M stream in N_READS r e a d _ co o r d i n a t e s synchronize // wait for s t r e a m i n g to c o m p l e t e // process reads foreach ACCESS_TYPE in P O L Y M E M _ S C H E M E _ S U P P O R T E D _ A C C E S S _ T Y P E S : chunk_size = N_READS / N _ S U P P O R T E D _ A C C E S S _ T Y P E S foreach (i , j ) in c h u n k _ o f _ r e a d _ c o o r d i n a t e s : c u r r e n t _ r e s u l t s _ b l o c k = M . read_block (i , j , ACCESS_TYPE ) // done p r o c e s s i n g reads foreach k in range ( N _ R E S U L T S _ B L O C K S ): stream out the k ^th results_block synchronize // wait for s t r e a m i n g to c o m p l e t e

Fig. 4 .

 4 Fig. 4. The measurement setup used for microbenchmarks. The measured bandwidth corresponds to phase 2, where reading the data from the parallel memory happens.

Listing 1 . 3 .Listing 1 . 4 .Listing 1 . 6 .

 131416 Declaration and partitioning of matrices to parallelize accesses to rows (dim=2) of B and to columns (dim=1) of C with a parallel factor of 16. float B [ DIM ][ DIM ]; # pragma HLS ar ra y _p ar ti t io n variable = B block factor =16 dim =2 float C [ DIM ][ DIM ]; # pragma HLS ar ra y _p ar ti t io n variable = C block factor =16 dim =1 Declaration of the matrices stored by using the HLS PolyMem with the RoCo scheme with a parallel factor of 4 • 4 = 16. # include " hls_prf . h " hls :: prf < float , 4 , 4 , DIM , DIM , SCHEME_RoCo > B ; hls :: prf < float , 4 , 4 , DIM , DIM , SCHEME_RoCo > C ; Listings 1.5 and 1.6 show the matrix multiplication code when using the HLS default partitioning and the HLS PolyMem, respectively. Listing 1.5. Matrix multiplication code that leverages default HLS partitioning to perform parallel accesses. // B * C matrix m u l t i p l i c a t i o n for ( int i = 0; i < DIM ; ++ i ) for ( int j = 0; j < DIM ; ++ j ) { # pragma HLS PIPELINE II =1 float sum = 0; for ( int k = 0; k < DIM ; ++ k ) sum += B [ i ][ k ] * C [ k ][ j ]; OUT [ i ][ j ] = sum ; } Matrix multiplication code that exploits the HLS PolyMem with RoCo scheme to perform parallel accesses.

Fig. 5 .

 5 Fig.5. Comparison between different partitioning of the input matrix in a grid of b 2 components implemented by PolyMem with a level of parallelism of p × q. When both p and q are set to 1, it is possible to remove the HLS PolyMem logic.

Table 1 .

 1 The PRF memory access schemes

	PRF Schemes Available Access Types
	ReO	Rectangle
	ReRo	Rectangle, Row, Main/Secondary Diagonals
	ReCo	Rectangle, Column, Main/Secondary Diagonals
	RoCo	Row, Column, Rectangle
	ReTr	Rectangle, Transposed Rectangle

  Listing 1.1. List of the methods interfaces to allow user read/write data by used sequential or parallel accesses

	DATA_T read ( int i , int j );
	void write ( DATA_T data , int i , int j );
	void read_block ( int i , int j , DATA_T out [ p * q ] ,
	int P RF _A C CE SS _T Y PE );
	void write_block ( DATA_T in [ p * q ] , int i , int j ,
	int P RF _A C CE SS _T Y PE );
	void w r i t e _ b l o c k _ m a s k e d ( DATA_T in [ p * q ] ,
	ap_uint < p * q > mask ,
	int i , int j ,
	int P RF _A CC E SS _T YP E );

Table 2 .

 2 Microbenchmark settings

	Clock Frequency (ClkFr):	200 MHz
	Data type (DType):	64-bit double
	Input matrix size (DIM × DIM ):	96 × 96
	HLS partitioning factor (FACTOR):	16
	PolyMem lanes (p × q):	16 (2 × 8)
	Number of passed coordinates (i, j) (N READS):	3072
	Size of each read block (BLOCK SIZE):	16
	Number of output blocks (N RESULTS BLOCKS):	50

Table 3 .

 3 Hardware resources utilization and execution time spent in phases 1 and 3 of the proposed architecture

	Memory	Access	LUT	FF	BRAM	DSP	Runtime [µs]
	-	-	41400	34064	21	0	265
	HLS Cyclic	Row	43194	35302	172	0	265
	PolyMem	Row	46375	36444	172	0	265

Table 4 .

 4 Hardware resources utilizations, execution times and bandwidths for microbenchmark experiments with different memory configurations and access schemes

	Memory Scheme LUT	FF BRAM DSP Runtime[µs] BW[GB/s]
	HLS Cyclic ReO 45800 36121	172	0	503	1.54
	PolyMem	ReO 45590 36364	172	0	283	20.35
	HLS Cyclic ReRo 90197 65993	174 224	503	1.54
	PolyMem	ReRo 59082 40661	172	0	283	20.35
	HLS Cyclic ReCo 85055 64679	174 164	503	1.54
	PolyMem	ReCo 62549 40434	172	0	283	20.35
	HLS Cyclic RoCo 67066 54217	174 100	503	1.54
	PolyMem RoCo 55025 38944	172	0	283	20.35
	HLS Cyclic ReTr 62259 54244	174	40	503	1.54
	PolyMem	ReTr 51282 37744	172	0	283	20.35

Table 5 .

 5 Hardware resources utilizations, execution times and bandwidths for the RoCo scheme with different combinations of access types with and without forced aligned accesses (FA)

	Memory	Access Types	LUT	FF BRAM DSP Runtime[µs] BW[GB/s]
	HLS Cyclic	Ro	60127 52552	174	64	503	1.54
	PolyMem	Ro	45641 36432	172	0	283	20.35
	HLS Cyclic	FA Ro	43048 35316	173	0	283	20.35
	PolyMem	FA Ro	45175 36391	173	0	283	20.35
	HLS Cyclic	Ro, Co, Re	67066 54217	174 100	503	1.54
	PolyMem	Ro, Co, Re	55025 38944	172	0	283	20.35
	HLS Cyclic Ro, Co, FA Re 47812 38003	173	0	429	2.23
	PolyMem Ro, Co, FA Re 55328 38975	173	0	283	20.35

Table 6 .

 6 Latency and hardware resources for matrix multiplication with different memory configurations and matrix dimensions

	Memory	Latency factor 1 MM 2 MM's BRAM DSP Hardware resources Matrix Parallel size FF LUT
	HLS	32	4	4227	n.a.	18 40 6162 6485
	PolyMem	32	4 (2 × 2) 4227	n.a.	18 40 6153 6018
	HLS	32	4	4227 16503	18 40 7444 9197
	PolyMem	32	4 (2 × 2) 4227	4227	18 40 7367 7364
	HLS	96	16	28033 442722	96 164 28554 40474
	PolyMem	96 16 (4 × 4) 28033 28033	96 160 30969 43636

  Listing 1.7. HLS PolyMem implementation of A 2 h

	hls :: prf < float , p , q , DIM , DIM , SCHEME_RoCo > A ;
	for ( int iter =0; iter < h ; iter ++){
	// A * A matrix m u l t i p l i c a t i o n
	for ( int i = 0; i < DIM ; ++ i ){
	for ( int j = 0; j < DIM ; ++ j ) {
	# pragma HLS PIPELINE II =1
	float sum = 0;
	for ( int k = 0; k < DIM ; k += p * q ) {
	A . read_block (i , k , temp_row , ACCESS_Ro );
	A . read_block (k , j , temp_col , ACCESS_Co );
	for ( int t = 0; t < p * q ; t ++)
	sum += temp_row [ t ] * temp_col [ t ];
	}
	A_temp [ i ][ j ] = sum ;
	}
	}
	// Copy back results to PolyMem
	for ( int i = 0; i < DIM ; ++ i ){
	for ( int t = 0; t < DIM ; t += p * q ) {
	# pragma HLS II =1
	A . write_block (& A_temp [ i ][ t ] , i , t , ACCESS_Ro );
	}
	}
	}

Table 7 .

 7 Latency, hardware resources and lines of code, for 8 iterations of the matrix power operation with different memory configurations and a matrix size of 384

				Hardware resources
	Memory	p q b	Latency	BRAM DSP	FF	LUT	LOC
	PolyMem	2 2 1 1557835871	1036	14	9936 11071	98
	PolyMem	2 4 1	840333407	1044	17 19678 28855	98
	PolyMem	4 4 1	488632423	1060	31 36138 53621	98
	multi PolyMem 1 1 2	758085955	1036	14	6967	5572	188
	multi PolyMem 1 2 2	394149976	1044	28 14709 12934	188
	multi PolyMem 2 2 2	214032480	1060	45 24845 22418	188
	NO PolyMem	1 1 4	101848419	1124	76 32852 13706

https://github.com/storna/hls polymem

This small-scale example is included for visualization purposes only. Realapplications are likely to use more memory banks, allowing parallel accesses to larger data blocks.

https://github.com/storna/hls polymem

Related WorkThe concept of parallel memory is fairly old, and has been widely discussed in scientific literature. As early as 1971, Kuck et al. discuss the advantages and disadvantages of using memory systems with power of two memory banks[START_REF] Budnik | The Organization and Use of Parallel Memories[END_REF], based on results collected from a study on performed on the Illiac IV machine.One of the earliest design methodologies and general designs of a parallel memory system suitable, dedicated to image processing applications, are presented in[START_REF] Voorhis | Memory Systems for Image Processing[END_REF]. The memory space is already organized as a 2D structure, while the parameters p, q are the parameters of the parallel region to be accessed; the authors discuss three different mapping functions, and ultimately demonstrate the benefits parallel accesses bring to image processing.

https://github.com/storna/hls polymem


Naoki Ojima
email: ojima@silicon.u-tokyo.ac.jp

Toru Nakura

Tetsuya Iizuka

Kunihiro Asada

A 65 nm CMOS Synthesizable Digital Low-Dropout Regulator Based on Voltage-to-Time Conversion with 99.6% Current Efficiency at 10-mA Load

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Along with the exponential advancement of process technologies, performance of LSI circuits rapidly improves and many functional building blocks such as analog, logic, RF, memory block, etc. can be integrated on a chip, which have brought system-on-a-chip (SoC) era. Meanwhile, in order to reduce power consumption as indicated by the scaling law, power supply voltages have been lowered. In addition, it is desirable that a power supply of each functional block is independently tuned according to the changing operating condition so as to have the optimal power efficiency. The on-chip voltage regulation is essential for this purpose, because off-chip voltage regulators require large PCB area, which leads to increase in cost. For those reasons, efficient, tunable, fast-transient and on-chip power sources are in great demand for SoC, hence low-dropout (LDO) regulators are now widely used. As shown in Fig. 1 driver amplifier and an analog pass transistor to provide voltage regulation with negative feedback. When the supply voltage is high enough, they exhibit high current efficiency, fast transient response, high power supply rejection and small output ripple [START_REF] Hazucha | Area-efficient linear regulator with ultra-fast load regulation[END_REF][START_REF] Lam | A 0.9 V 0.35 µm Adaptively Biased CMOS LDO Regulator with Fast Transient Response[END_REF][START_REF] Milliken | Full On-Chip CMOS Low-Dropout Voltage Regulator[END_REF][START_REF] El-Nozahi | High PSR Low Drop-Out Regulator With Feed-Forward Ripple Cancellation Technique[END_REF]. In addition, their area occupation could be smaller than other power management circuits such as switching regulators, because they do not require large inductors. However, they have difficulty in operating at low supply voltage, since amplifiers cannot sustain their dynamic range and high gain under such a situation. To solve this issue, the digital implementations of LDOs shown in Fig. 1(b) has been proposed [5][START_REF] Gangopadhyay | A 32 nm Embedded, Fully-Digital, Phase-Locked Low Dropout Regulator for Fine Grained Power Management in Digital Circuits[END_REF][START_REF] Otsuga | An on-chip 250 mA 40 nm CMOS digital LDO using dynamic sampling clock frequency scaling with offset-free TDC-based voltage sensor[END_REF][START_REF] Oh | A 110-nm CMOS 0.7-V Input Transient-Enhanced Digital Low-Dropout Regulator With 99.98% Current Efficiency at 80-mA Load[END_REF][START_REF] Nasir | All-Digital Low-Dropout Regulator With Adaptive Control and Reduced Dynamic Stability for Digital Load Circuits[END_REF][START_REF] Kim | A Fully Integrated Digital Low-Dropout Regulator Based on Event-Driven Explicit Time-Coding Architecture[END_REF][START_REF] Salem | A Successive Approximation Recursive Digital Low-Dropout Voltage Regulator With PD Compensation and Sub-LSB Duty Control[END_REF][START_REF] Kim | A 67.1-ps FOM[END_REF][START_REF] Akram | Fast Transient Fully Standard-Cell-Based All Digital Low-Dropout Regulator With 99.97% Current Efficiency[END_REF][START_REF] Zhao | A Digital LDO With Co-SA Logics and TSPC Dynamic Latches for Fast Transient Response[END_REF][START_REF] Liu | A fully-synthesizable 0.6V digital LDO with dual-loop control using digital standard cells[END_REF]. A typical digital LDO has a digital controller made of logic gates that controls the number of turned-on PMOS switches at output stage, and employs an analog voltage comparator to detect the difference between reference and feedback voltages. Thus digital LDOs can eliminate amplifiers and operate under a low supply voltage. Moreover, since they are constucted mainly from digital logic gates, their performance can be easily improved by process downscaling and clock boosting.

A voltage comparator, however, often requires careful manual design so as to minimize the voltage offset between two inputs. Thus even digital LDOs also require sophisticated analog design flows, which is often time-consuming. A digital design flow, on the other hand, requires much less design effort, because its layout design is automated. Since circuit implementation in digital design flows is based on RTL source codes, the circuits that have the similar specification can be made easily even when the used process technologies are updated. Thus recently many analog circuits such as analog-to-digital converters (ADC) [START_REF] Weaver | Digitally Synthesized Stochastic Flash ADC Using Only Standard Digital Cells[END_REF] or phase-locked loops (PLL) [START_REF] Deng | A Fully Synthesizable All-Digital PLL With Interpolative Phase Coupled Oscillator, Current-Output DAC, and Fine-Resolution Digital Varactor Using Gated Edge Injection Technique[END_REF] are designed through digital automated flow, in order to take advantage of the relaxed design burden and process portability. Hence we have been motivated to implement LDOs, one of the indispensable blocks for SoCs, in digital design flows.

In order to relax the burden of manual analog designs, this paper proposes a synthesizable digital LDO, whose preliminary results have been presented in [START_REF] Ojima | A Synthesizable Digital Low-Dropout Regulator Based on Voltage-to-Time Conversion[END_REF]. By utilizing voltage-to-time conversion, the proposed LDO has a suitable architecture for standard-cell-based automatic place and route (P&R).

2 Proposed Synthesizable LDO

Architecture

One of the design issues in constructing an LDO with standard cells is an implementation of a voltage comparison unit. Reference [START_REF] Weaver | Digitally Synthesized Stochastic Flash ADC Using Only Standard Digital Cells[END_REF] reported that an analog voltage comparator can be implemented with 3-input NAND gates. Such comparators can be easily designed, but they suffer from the random systemtic offset owing to the randomness of the automatic P&R. Thus the single comparator made of NAND gates is not suitable for precise voltage comparison. The PLL-like LDO in [START_REF] Gangopadhyay | A 32 nm Embedded, Fully-Digital, Phase-Locked Low Dropout Regulator for Fine Grained Power Management in Digital Circuits[END_REF] employs voltage-controlled ring oscillators in order to convert the voltage difference into the phase difference. However, this architecture is not preferable because a voltage-controlled ring oscillator has an integral characteristic that adds a pole to the system, which deteriorates the stability of the loop. Moreover, voltage-controlled ring oscillators might be a cause to increase the current consumption of the voltage comparison unit. Some digital LDOs utilize voltage-to-time converters (VTC) and time-to-digital converters (TDC) [START_REF] Otsuga | An on-chip 250 mA 40 nm CMOS digital LDO using dynamic sampling clock frequency scaling with offset-free TDC-based voltage sensor[END_REF][START_REF] Oh | A 110-nm CMOS 0.7-V Input Transient-Enhanced Digital Low-Dropout Regulator With 99.98% Current Efficiency at 80-mA Load[END_REF], so that they exclude analog voltage comparators. Although a TDC can be composed of digital logic cells, its layout implementation actually requires manual design because its linearity is very sensitive to the parasitic capacitance of its layout pattern. Hence we propose to use a simple bang-bang detector, in order to relax the complexity of the layout and eliminate the systematic offset even when the layout is automatically placed and routed.

Our proposed LDO shown in Fig. 2 employs voltage-controlled delay lines (VCDL), and the difference between the reference and the output voltages are converted into the time-domain. The proposed LDO consists of two inverter chains, a bang-bang phase detector, a digital controller, a PMOS switch array, and an output capacitor. Though for this prototype a dedicated ring oscillator is used as an internal clock source and a pulse generator, these clock and pulse signals can be replaced by a clock for other blocks on the SoC. The digital controller generates 128-bit-width thermometer code from 1-bit output from the bang-bang phase detector to control the switches. The PMOS switch array has parallelly-aligned 128 PMOS transistors, all of which have the same size. Each gate of the switch is connected to each bit of the thermometer code from the digital controller. The two inverter chains have the same structure, which has a series connection of 128 inverters. As shown in Fig. 3, the bang-bang phase detector is simply composed of a D-FF and a buffer. The buffer is connected to the clock input of the D-FF to compensate the setup time of the D-FF. As shown in Fig. 4, the internal clock and pulse generator is composed of inverters, D-FFs, and multiplexers for frequency tuning. The output capacitor is assembled off-chip. Once the switch PMOS transistor cell is added to a standard-cell library, all cells needed to compose the proposed LDO are included in the library and the LDO can be generated from Verilog gate-level netlists and synthesized with a P&R tool.

The layout of the PMOS switch has to follow the design rules for standard cells so that it can be placed and routed by the P&R tool. Fig. 5 shows an outline of the PMOS switch cell layout. It is designed just by removing the NMOS transistor from the inverter cell for ease of the additional cell layout. Thus, the size of the PMOS switch cell is equal to that of the inverter cell. The operation of the proposed LDO is described as follows. As shown in Fig. 2, the two inverter chains are powered by V re f and V out , respectively. An identical pulse train from the internal pulse generator enters into them at the same time. The inverter chains work as VCDLs. In other words, the inverter chains convert the voltage difference between V re f and V out into the delay difference that is compared by the phase detector. Based on the phase detector output, the digital controller changes the number of turned-on PMOS switches.

V ref V out V in C out I load
K p K i z -1 Input[n] Output[n] Intg[n]
Fig. 6. Signal flow graph of the digital controller that includes proportional and integral paths.

Fig. 6 shows the signal flow graph of the digital controller. The operation of the digital controller is expressed by the following discrete-time difference equations.

Intg[n] = Intg[n -1] + K i × Input[n] (1) Output[n] = Intg[n] + K p × Input[n] (2)
The digital controller includes proportional and integral paths. Output[n] is 7-bit binary.

Then the binary output is decoded into thermometer code so that the number of turned-on PMOS switches can be controlled one by one. When V out is higher than V re f , the phase detector output becomes HIGH and the digital controller decreases the number of turned-on switches. On the contrary, when V out is lower than V re f , the phase detector output becomes LOW and the digital controller increases the number of turned-on switches. In this way V out approaches to V re f . As the divider and the multiplexer is attached to the internal clock and pulse generator, in this prototype the clock frequency can be easily tuned by the multiplexer for test purpose. The components other than the inverter chains are powered by V in . The HIGH-level voltage of the pulse trains which travel through the inverter chains are equal to their power source voltage, V re f or V out . Therefore, if V re f is lower than the logic threshold voltage of the phase detector powered by V in , the phase detector cannot be driven by the pulse from the inverter chain powered by V re f . Thus, the lower limit of V re f is determined by the logic threshold voltage of the standard cells powered by V in .

Transfer Function of the Control Loop

Fig. 7 shows the signal flow graph of the proposed LDO. The comparison unit composed of inverter chains and a D-FF generates an error sample. Since the comparison is done based on the pulse train which is the same signal as the clock, one clock delay occurs here at every sample. As previously described, the digital controller has proportional and integral paths. In order to investigate the loop stability in continuous-time domain, the approximation below is applied:

z ≈ 1 + sT s , (3)
where T s represents the sampling period. The transfer function of the digital controller is thus approximated as follows:

H ctrl = K p + 1 1 -z -1 K i ( 4
)
≈ K p + 1 + sT s sT s K i . (5)
The output stage is composed of the switch array, the output capacitor, and the effective resistance. I pmos is the current through a single PMOS switch. According to [START_REF] Nasir | All-Digital Low-Dropout Regulator With Adaptive Control and Reduced Dynamic Stability for Digital Load Circuits[END_REF], the effective resistance R l can be approximated as V out /I load . Using (3) and ( 5), the continuous-time open-loop transfer function G(s) is given by

G(s) = ( K p 1 + sT S + K i sT s ) • I pmos R -1 l + sC out . (6)
When I load is small, R l becomes big so that R -1 l ≪ sC out . Then, G(s) approximates

G(s) ≈ ( K p 1 + sT S + K i sT s ) • I pmos sC out . (7)
If K p = 0, the poles of the closed-loop transfer function are close to the imaginary axis, and thus the system tends to be unstable. To avoid oscillation, we add the proportional gain K p to the digital controller. Fig. 8 shows the bode plots of the open loop transfer function with small I load of 100 µA for K P = 0 and K p = 1, respectively. When K p = 0, the phase margin is 17 • , whereas it is 27 • when K p = 1, which suppresses the abrupt phase change around 1 MHz.

Design Procedure of the Proposed LDO

This section explains the design procedure of the proposed LDO. Fig. 9 shows the design flow diagram. The explanation follows the step numbers shown in Fig. 9. 0)

The PMOS switch cell is designed in advance and added to the standard-cell library.

1) The specification of the circuit, such as maximum load current or reference voltage, is set. Based on this specification, the number of the PMOS switches in the switch array and the output bit width of the digital controller are determined.

2) The RTL Verilog code of the digital controller is prepared, then logically synthesized to have the gate-level Verilog netlist. 3) The gate-level Verilog netlists of other components, such as the inverter chain, the phase detector, the switch array, and the internal clock and pulse generator are generated by a dedicated script. Examples of the gate-level Verilog description is shown in Fig. 10. Since each building block has simple standard-cell-based structure, the gate-level netlist generation is simply implemented. For example, the switch array is constructed only by the parallel PMOS switch cells, and thus its gate-level netlist is generated easily by the script according to the specification. 4) The layout of each building block is individually placed and routed by a P&R tool. This is because they have different power supplies; the two inverter chains are powered by V out or V re f respectively, and the other blocks are powered by V in . We use the same layout for both of the two inverter chains, so that there is little systematic offset in the voltage comparison unit. 5) All the layouts are connected together. It takes few hours to generate the whole layout of the proposed LDO from scratch, which is much less time than that in the case for the conventional LDO design with analog flows.

V out V ref K p K i I pmos R l -1 +sC out Output Stage z -1

Prototype Implementation and Measurement Results

Based on the architecture described in the previous section, the prototype of the proposed LDO is fabricated in a 65 nm standard CMOS technology. Fig. 11 shows the chip photo. The active area of the proposed LDO is 0.015 µm 2 . Fig. 12 shows the measured tracking response of V out with 10.4 MHz clock when V re f , which is externally supplied in this measurement, switches between 600 mV and 800 mV. Here, I load and C out is 10 mA and 220 pF, respectively. When V re f changes from 600 mV to 800 mV, the settling time is 4.5 µs, whereas it is 4.4 µs when V re f changes from 800 mV to 600 mV. Fig. 13 shows the measured transient response of V out with 10.4 MHz clock when I load changes between 5 mA and 10 mA. V re f of 800 mV and C out of 220 pF are used in this experiment. When I load changes from 5 mA to 10 mA, the settling time is 6.6 µs and the undershoot is 303 mV. When I load changes from 10 mA to 5 mA, the settling time is 6.0 µs and the overshoot is 126 mV. Since the operation region of PMOS temporarily enters into saturation region when the undershoot occurs while it does not for the case of overshoot, the waveforms of V out transient become different in these two cases.

The overall current consumption with 10.4 MHz clock and I load of 10 mA is 282 µA including the current consumed at the internal clock and pulse generator, which is not essential in the actual use because it can be substituted by an internal clock for other functional blocks on the SoC. Based on the circuit simulation result, the LDO core consumes 12.5 % of the total current as shown in Fig. 14. Thus, the quiescent current of the LDO core is assumed to be 35.2 µA, which leads to 99.6 % current efficiency.

In the proposed architecture, V re f is used as a power source of a VCDL. Hence, V re f is required to supply current to drive the VCDL for voltage comparison. Fig. 15 shows the current consumption from V re f versus the frequency of the pulse train, which is equal to CLK, with V re f of 800 mV and I load of 10 mA. The pulse is sent from the internal oscillator, and its frequency is tuned by the multiplexer. Typically, when the pulse frequency is 10.4 MHz, the current consumption from V re f is 10.6 µA. According to Fig. 15, the current consumption of V re f is proportional to the pulse frequency. When the pulse frequency is set high in order to have the fast transient response, V re f is required to supply more current.

Table 1 shows performance comparison to prior digital LDOs. This work realizes a competitive current efficiency and FOM T with synthesizable architecture, while others cannot be fully synthesizable and need manual designs. Owing to the automated design flow of this work, if needed the maximum load current I load,max can be easily increased by adding more PMOS switches, at the expense of the increase in the area and the quiescent current.

Conclusion

This paper proposes a synthesizable digital LDO that is designed by a P&R tool. In the proposed LDO, by using inverter chains as VCDLs, the difference between the output and the reference voltages is converted into the delay difference that can be compared by a phase detector. The voltage control loop is all composed of standard cells and synthesizable, which drastically relaxes the design burden. The prototype is fabricated in a 65 nm standard CMOS technology with 0.015 mm 2 area occupation. According to the measurement results of the prototype, with 10.4 MHz clock and C out of 220 pF the tracking response time when V re f switches between 600 mV and 800 mV is ∼4.5 µs with I load of 10 mA, and the transient response time when I load changes between 5 mA and 10 mA is ∼6.6 µs with V re f of 800 mV. The quiescent current consumed by the LDO core is as low as 35.2 µA at 10 mA load current, which leads to 99.6 % current efficiency. In our prototype, V re f needs to supply 10.6 µA current when the pulse frequency is 10.4 MHz.

In this paper, we used a PMOS switch cell made from an inverter cell. However, this customized PMOS switch cell can be substituted by a tri-state inverter cell [START_REF] Liu | A fully-synthesizable 0.6V digital LDO with dual-loop control using digital standard cells[END_REF] or a tri-state buffer cell. If the inputs of these cells are tied to LOW (in the case of tri-state inverters) or HIGH (in the case of tri-state buffers), the output PMOS transistors can be controlled by the tri-state control inputs. Thus, if these cells are included in the standard cell library, a fully standard-cell based synthesizble LDO can be realized and the design burden would be more relaxed.

Fig. 1 .

 1 Fig. 1. LDO architectures. (a) Conventional analog LDO has a simple architecture, and includes an error amplifier, a driver amplifier and an analog pass transistor. (b) Digital LDO includes a comparator, a digital controller made of logic gates, and parallel pass transistors.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Phase detector composed of standard cells.

Fig. 5 .

 5 Fig. 5. (a) An inverter cell and (b) an additional PMOS transistor cell for the switch array.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Signal flow graph of the proposed LDO.

Fig. 10 .

 10 Fig. 10. Examples of the gate-level Verilog description: (a) inverter chain, (b) phase detector, (c) switch array, and (d) internal clock and pulse generator.

Fig. 12 .

 12 Fig. 12. Measured tracking response of V out when V re f switches between 600 mV and 800 mV with 10.4 MHz-clock, I load of 10 mA and C out of 220 pF.

Fig. 13 .Fig. 14 .

 1314 Fig. 13. Measured transient response of V out when I load changes between 5 mA and 10 mA with 10.4 MHz-clock, V re f of 800 mV and C out of 220 pF.

Fig. 15 .

 15 Fig. 15. Current consumption from V re f versus the frequency of the pulse train.

  Design flow of the proposed circuit.

			2
	1 Specification Set	RTL (Digital Controller)	3	Logic Synthesis	Gate Level Verilog Netlist	5	Connect Modules	Whole Layout
		Dedicated Script	Netlist Generation	4	Automatic		Each
						P&R		Layout
		0
		Design	Standard Cell
		PMOS cell		Library
	module inverterChain(IN, OUT); input IN; output OUT; wire node0, node1, ..., node(K-1); inv U0 (.A(IN), .Y(node0)); inv U1 (.A(node0), .Y(node1)); ... inv UK (.A(node(K-1)), .Y(OUT)); endmodule wire node0; buf U0 (.A(INN), .Y(node0)); dff U1 (.D(INP), .C(node0), .Q(OUT)); endmodule Fig. 9. module switchArray(IN, OUT); module phaseDetector(INP, INN, OUT); input INP, INN; output OUT;	module clockAndPulseGenerator(SELECT, OUT); input [1:0] SELECT; output OUT; wire node0, node1, node2, q0, q1, q2, q3, xq0, xq1, xq2, xq3; // ring oscillator inv U0 (.A(node2), .Y(node0)); inv U1 (.A(node0), .Y(node1)); inv U2 (.A(node1), .Y(node2)); // divider dff U3 (.D(xq0), .C(node2), .
	input [N-1:0] IN;
	output OUT;
	pmos U0 (.A(IN[0]), .Y(OUT));
	pmos U1 (.A(IN[1]), .Y(OUT));
	...
	pmos U(N-1) (.A(IN[N-1]), .Y(OUT));
	endmodule

Table 1 .

 1 Comparison to prior arts of Performance FOM T = (C out ×∆V out ×I q )/∆I 2 load[START_REF] Hazucha | Area-efficient linear regulator with ultra-fast load regulation[END_REF]

		This work	[5] CICC 2010	[6] JSSC 2014	[10] JSSC 2017	[11] JSSC 2018	[12] SSC-L 2018	[13] TPE 2018	[14] SSC-L 2018
	Process	65 nm	65 nm	32 nm	65 nm	65 nm	65 nm	65 nm	28 nm
	Active area [mm 2 ]	0.015	0.042	0.008	0.029	0.0023	0.012	0.014	0.019
	V in [V]	1.0	0.5	0.7-1.0	0.5-1.0	0.5-1.0	0.5-1.0	0.7-1.2	0.6-0.65
	V out [V]	0.8	0.45	0.5-0.9	0.45-0.95	0.3-0.45	0.35-0.95	0.6-1.1	0.55-0.6
	I load,max [mA]	10	0.2	5	3.5	2	2.8	25	25
	C out [pF]	220	100000	100	400	400	100	1000	150
	Quiescent I q [µA]	35.2	2.7	92	12.5	14	45.2	6	28
	Current efficiency [%] 99.6	98.7	98.2	96.3	99.8	98.4	99.97	99.96
	Transient ∆V out	300 mV	40 mV	150 mV	40 mV	40 mV	46 mV	200 mV	56 mV
	@ load step ∆I load	@ 5 mA	@ 0.2 mA	@ 0.8 mA	@ 0.4 mA	@ 1.06 mA	@ 1.76 mA	@ 23.5 mA	@ 20 mA
	FOM T [ps] *	93	270000	1150	1250	199	67.1	2.17	0.59

*

Acknowledgment

This work is partly supported by JSPS KAKENHI Grant Number 17H03244, and is supported by VLSI Design and Education Center (VDEC), the University of Tokyo in collaboration with Synopsys, Inc., Cadence Design Systems, Inc., and Mentor Graphics, Inc.