Fast-OverlaPIM: A Fast Overlap-driven Mapping Framework for Processing In-Memory Neural Network Acceleration

PIM has been widely used for memory-intensive and compute-intensive applications because of its extensive bandwidth for computing and ability to minimize data movement. Various PIM-based architectures have been introduced to support parallel operations inside memory with different memory technologies, such as SRAM[31], DRAM[32, 33, 34, 35], ReRAM[36, 10, 37], spintronics-based magnetic memories [38]. This work focuses on the digital PIM paradigm, which stores the conventional digital representation (i.e., one binary bit per cell) in memory. A common underlying foundation for digital PIM is row-parallel bit-serial operations [35], which make use of the common bit-line circuits shared in memory blocks to process all columns in selected operand rows in a single step. Supported with universal bit-wise operations (e.g. AND, NOR, majority operation, etc.), PIM memory enables general computations for DNN [39, 40, 33]. Our baseline system is the bit-serial row-parallel PIM architecture [34] based on HBM2 DRAM [41], which supports universal bit-wise operations in the DRAM banks with activate-activate-precharge [33] and performs majority-based addition (MAJ) [35].

In addition to the baseline DRAM system, Fast-OverlaPIM can be aligned with other digital PIM-based architectures through minimal modifications for the performance model and customized architecture configurations as inputs. In Section IV-B and Section IV-C, we will furtherdiscuss the possibility of extending Fast-OverlaPIM to support analog PIM, which represents fixed operands (i.e., neural network weights) in memory cells and process computation by applying analog signals (i.e., current) as other operands and sensing the result signals [42, 43].

Floating-point matrix operations, such as additions and multiplications, are the bottleneck for DNNs. For each layer, weights and inputs are loaded into memory spaces for computation. After execution, outputs are reallocated to the input memory space for the next layer without transferring between memory and processing units. As shown in Figure 1, we allocate memory rows to different bits of operand and result vectors to support an in-memory computation for each addition and multiplication operation. The example only shows single-bit values for input, filter, and output. In practice, each data may take multiple rows. Once the operand and result vectors are aligned, the memory issues a sequence of universal bit-wise operations to generate the result vector. Such bit-serial operations achieve extensive parallelism because we can simultaneously process all columns in memory rows in different memory blocks (e.g. Bank and Channel).

Figure 2 shows an example of high-level PIM architecture for DNN acceleration. The memory is organized into multiple channels, each containing several banks. Each bank is a 2D memory array, which is the basic unit of PIM computing. We note that this spatial layout is general to support various technologies, such as digital bit-serial computing or analog computing. To accelerate NN, each layer may be pre-allocated with several memory banks spatially to exploit parallelism. For networks with larger depths, fully completed layers will be replaced by new subsequent layers. Thus, through pre-allocating memory resources for different layers given memory constraints, the PIM-based accelerators can accommodate the whole DNN network, different from ASIC-based accelerators that usually process one layer at a time [16]. The whole network execution avoids costly off-chip data communication.

Achieving optimized performance PIM acceleration on NN requires sophisticated design choices on software-to-hardware mapping, which determines the operation scheduling and data allocation of a specific DNN across the hardware resources [16]. Each mapping has a direct relation to a specific data allocation and operation schedule on the given hardware, which has hierarchical storage. The per-layer optimization (i.e. process one layer at a time) for customized accelerators may lead to sub-optimal performance for PIM architectures with sufficient resources to process many layers simultaneously.

Figure 1 shows an example of two different mappings in PIM architecture. The mappings are described using the syntax of Timeloop [16]. Mapping1 parallelizes computations of all 4 outputs by exploiting memory resources and spreading data in different memory columns for each layer; Mapping2 parallelizes two output tiles where each tile sequentially processes 2 outputs by dividing memory into two consecutive NN layers. Mapping1 and Mapping2 have different data layouts, which affects both the latency for processing the layer and the order of producing outputs and consuming inputs through different allocations. Given the layer-wise data dependencies, the order of generating outputs and utilizing inputs significantly affects the ability for computational overlap optimization.

Figure 3(a) and Figure 3(b) demonstrate overlap optimization through the comparison of execution times and memory allocation between sequential execution and paralleled spatially execution based on the different mapping choices of two consecutive layers. We divide the computation of each layer into multiple time steps, where each time step processes several operation spaces in parallel (spatially processed in different memory blocks). In Figure 3(a), larger PIM-based memory is allocated for each layer so that Layer1 achieves full completion at time step1. However, Layer2 needs to wait until after time step1 to start execution and the whole processing for the two layers will be finished at step3. But in Figure 3(b), smaller memory is allocated for each individual in order to trade for parallelism between Layer1 and Layer2 so that Layer1 can only be fully completed at time step1.5 due to limited memory allocation and computation resources. However, Layer2 can overlap the computation of its output0 with Layer1 at time step , where Laye 1 completes the computation of operation spaces output0 and output1 (input0 and input1 in Layer2). Output1 of Layer2 can also be overlapped. Layer2 can finish execution before time step3 and gain the improvement from overlap optimization. Such overlap optimization can bring better performance than the performance considered by the existing framework considering the increasing per-layer size of modern DNNs.

To harness the overlap optimization introduced in III-C, we initially explored the potential for overlapping in mappings generated with conventional DNN frameworks. In Figure 4, we display the experimental result of PIM acceleration for ResNet-18 and VGG-16 where we use the state-of-the-art open source frameworks, Timeloop [16], to search for the best mapping (mapping with the lowest latency) layer by layer. We added the analysis of the computation overlapping of consecutive layers on the top of Timeloop and reduced the overlapped computations from the original latency if and only if the input for all operation spaces of the following layer becomes ready in a specific time step. Therefore, not all overlapped data spaces lead to a latency reduction. This figure is produced by calculating the normalized latency of the overlapped computation in the experiment, where a higher value indicates better performance with more overlapped computations. If we naively search for the best non-overlap performance mapping for each layer, the overlapped latency varies significantly from layer to layer for both workloads. For ResNet-18, 10 out of 20 layers only have very limited overlapping ($\leq 30\%$) while other layers can overlap a significant portion of their computations (31% to 68%). And for VGG-16, 5 out of 13 layers cannot gain latency improvement at all and 4 out of 13 layers only have trivial overlapping ($\leq 10\%$) while the rest layers have some overlapping (11 % to 37 %). Therefore, there exists great potential to optimize the performance by optimizing the DNN mapping on PIM based on overlaps of computations between consecutive layers.

Figure 5 shows the key components of Fast-OverlaPIM to enable overlap-based optimization. First, we design a new interface to configure the hardware and optimization procedure of the whole network. Second, we add a PIM performance model to support the accurate evaluation of mapping on PIM architectures. Third, we develop a lightweight fine-grained data space generation algorithm. This process generates detailed data spaces over time on various memory components, facilitating efficient preparation for overlap analysis and optimization within a relatively short runtime. Then, we propose a fast analytical computational overall analysis algorithm to resolve the output-input data dependencies between the consecutive layers to determine the overlapping performance. We propose a transformation algorithm that can significantly increase the search capability of whole DNN optimization with trivial overhead. Moreover, we introduce novel search strategy alternatives with the capability of starting from layers other than the numeric first layer to explore larger design spaces and to improve the performance of searched mappings.

To develop a user-friendly framework for the whole network mapping, we implemented the DNN interface that takes the whole DNN model as input and gives the whole-network layer information as outputs to serve as configurations for Fast-OverlaPIM. Fast-OverlaPIM interface extracts the size parameters of the input, filter, and output for each NN layer. The extraction results are in Fast-OverlaPIM readable format and processed by Fast-OverlaPIM in sequential order as a whole-network description. These interfaces will allow the users to configure the whole network for the overlap analysis between consecutive layers as a global mapper without much manual effort. We also enable the new interface to take the description of per-layer mapping constraints as inputs to assist with the mapping search. User-defined mapping constraints provide additional information for tiling and allocating matrix workloads onto hardware components.

For the hardware configuration, the interface takes the user-customized PIM model as input. For each memory level, we can configure the number of parallel instances and word bits to represent the operation throughput; the read bandwidth and write bandwidth can be specified to model different intra-memory links for data movement. Figure 6 shows an example of DRAM-based PIM architecture configuration. The configuration is constructed following the hierarchical tree structure of storage elements. The read/write bandwidth of each channel is 16 bytes. If a level does not have read/write bandwidth (e.g., Column in the example), the upper level (i.e., Bank) handles the data movement. We can specify the supported PIM operations at each level to emulate different PIM structures. The example shows the configuration to support bit-serial row-parallel operations, where all column instances can compute 1-bit addition or multiplication simultaneously. In Section IV-D, we illustrate how to exploit Fast-OverlaPIM as a general-purpose PIM-based mapping optimization framework that can support various PIM-based architectures.

We implemented a new PIM performance for latency performance evaluation because the Timeloop [16] performance model only considers the compute, read, and write latency. These statistics are insufficient for PIM performance evaluation which requires data movement. In the context of the PIM architecture the PIM architecture for Fast-OverlaPIM, we focus on spatially distributed PIM acceleration for our network optimization based on bit-serial row-parallel processing [34], as introduced in Section III-A and Section III-B. We allocate a fixed amount of memory for each individual DNN layer, and the framework determines the data layout based on the mapping. We allocated a fixed amount of memory for each DNN layer, and the framework optimizes the data layout. Based on the mapping, we place the filter of all layers and input data for the first layer. After the completion of the execution for each layer, we move its output to the corresponding memory locations of the input for the next layer. Our PIM performance model estimates the performance of such processing flow.

To represent the computation latency of PIM, we replace the read/write operations in [16] with the data movements required by PIM executions. Data movements include the output-input inter-layer data transfer and the data movements for reductions of partial sums located in different columns. Specifically, for each MAC operation in a memory bank, we model the operation using three steps: 1) the element-wise multiplications for partial products, 2) memory read/write for transposition, and 3) serial additions for reduction. The latency and energy of read/write are similar to the normal DRAM operation, with activation, precharging, and read/write DRAM commands. Each full addition requires $4n+1$ activate-activate-precharge (AAP) operations, where n is the number of bits per value (16-bit in our experiments). Each multiplication consists of sequential full additions.

Our overlap-based analysis and optimization are applicable to other spatial DNN accelerations, including PIM architectures with different technologies or ASIC-based spatial accelerators. For instance, Figure 7 illustrates the support for FloatPIM, a ReRAM-based digital PIM architecture that exploits bit-serial row-parallel computations for DNN training and inference[10]. FloatPIM is compatible with any bipolar resistive technology, which is the most commonly used in existing non-volatile memories (NVMs). By adjusting the memory hierarchy level and the corresponding number of instances in the user-defined configuration, the FloatPIM architecture can be represented in Fast-OverlaPIM. Adjusting the add and multiply latency ensures the corresponding cycle-latency measurement for the ReRAM-based PIM. Furthermore, we can adjust the read and write bandwidth in the memory level to represent the customized intra-tile links in FloatPIM. These configuration adjustments are similarly generalizable to other PIM-based architectures.

While the current implementation of Fast-OverlaPIM focuses on digital-based PIM architectures, which allocate all data in the conventional digital memory, we can extend it to support analog PIM by configuring architectural configuration input and performance model. In analog PIM[42][43], only the filter is allocated directly in memory, and input will be loaded as the analog signal to the memory for computation. However, the output is still generated in the temporally sequential order for each spatially distributed PE. Thus, the partial input for the succeeding layer can still be finished and loaded to the next filter before the proceeding layer is fully completed. Therefore, we can modify the architecture configuration to model the analog PIM memory and implement a new performance model to consider the analog-specific operations (e.g., ADC, DAC, etc.).

DNN mappings describe the way in which inputs, outputs, and weight are split into data spaces at each level of the memory hierarchy and at each time step. We utilize a consistent representation of data spaces and loop decomposition to facilitate mapping generation, fine-grained data space generation, and computational overlap analysis.

Fast-OverlaPIM exploits the conventional 7D-loop representation for the DNN layer. We use the convolution layer as the example, where $R$ and $S$ are the height and width of weight, $P$ and $Q$ are the height and weight of output, $C$ is the number of input channels, $K$ is the number of output channels, and the number of inputs or batch size is represented by $N$. With this parameterized representation, we define the output data space as a 4-D tensor $[N,K,P,Q]$ and the input data space as $[N,C,P+R-1,Q+S-1]$ for further input/output overlapping analysis on different mappings. This can represent the whole DNN model because CONV and FC (Fully-Connected) layers dominate the computations and data movement. Figure 8 shows an example of data spaces for the mapping on a two-level memory. For simplicity, we ignore the dimension of $N$ in the later discussion.

In Figure 8 (a), each mapping, with a specific loop decomposition and permutation, can be translated into data spaces that are spatially and temporarily distributed. Specifically, the spatial distribution (i.e., $parallel\_for$) means data spaces are split and allocated to different hardware instances. The temporal distribution (i.e., $for$) happens when a data space of a hardware instance is further decomposed into smaller data spaces. These smaller data spaces are sequentially processed by the corresponding hardware component in multiple temporal steps, where the instance processes a temporal data space in each step. In Figure 8, the whole output data space is spatially decomposed into two channel-level spaces, each of which is further decomposed into two temporal steps. Similarly, each channel-level temporal step is decomposed into 2 bank-level spaces, where each consists of $P*Q$ temporal steps. In total, each bank in this example consists of $2*P*Q$ temporal steps.

Analysis of the overlap between layers requires the comparison of the detailed output/input data spaces for each memory hierarchy level across DNN layers. However, previous works avoid generating fine-grained data spaces due to runtime limitations. Timeloop [16] only collects a small portion of data spaces for size measurement. Since Timeloop generates data spaces from recursive function calls, collecting all data spaces is unacceptably expensive for both runtime efficiency and memory consumption and makes overlap analysis impossible.

To reduce the complexity, we propose a lightweight fine-grained generation algorithm to infer all spatial and temporal data spaces through analytical observation and formulation. In Figure  8(b)(c), Timeloop [16] generates partial data spaces in the light green and yellow. Our analytical algorithm utilizes these data spaces as reference points to generate fine-grained data spaces. In order words, we identify and generate the $4\times(PQ-2)$ number of previously un-generated data space, as highlighted within the blue rectangle.

We propose a lightweight data space analysis based on the observation that the size of data spaces remains the same at each hardware level. The dimension value of data spaces changes periodically corresponding to the inner loop iteration, where each loop level increments one data space dimension. Since these increments are well-patterned with the fixed total number of data spaces and stable size of each individual data space, we conclude a lemma to define the relationship between the index increment of the specific loop level $n$ and its corresponding time step increment:

where $num_{j}$ is the number of iterations in the $j^{th}$ temporal loop, and $q$ is the lower bound of loops in the target hardware level where the current loop iteration belongs.

Then, our analysis algorithm runs in two steps. First, we analyze the nested loop of the mapping to split the whole data space into small data spaces until the target level (i.e., bank-level). The loop analysis runs in an up-down loop order to generate small data spaces by splitting data spaces from the upper loop level. Second, we map the generated data spaces into the correct temporal and spatial locations. The spatial index for each data space can be computed straightforwardly by tracking all spatial loops (i.e., $parallel\_for$).

For the temporal index, we deduce a formula to translate the indices of loop iterations into the temporal steps at each hardware level. Assuming $k$ is the index of the $n^{th}$ temporal loop iteration and $i$ is the global index of $0-(n-1)$ temporal loops, the temporal index of data spaces in the $n^{th}$ loop can be found by:

where $G(n)$ could be found by utilizing Equation 1. We compare them with original data spaces generated from Timeloop [16] using data space generation with no extrapolating to verify our analytical data spaces.

Compared to the strategy in Timeloop’s, which depends on recursive function calls, our method more efficiently compute all data spaces in $O(n)$ time complexity, where $n$ is the total number of data spaces. If we implement the data space generation in the Timeloop’s recursive function calls, the analysis for one mapping takes around 600 seconds. Our proposed analytical calculation only takes less than 60 seconds.

In this section, we clearly define the condition of overlap to prepare for overlap analysis. With the fine-grained data spaces for two consecutive layers, Layer $n$ and $n+1$, we analyze the overlap and estimate the overlapped performance. We denote $O_{t}^{i}$ and $I_{t}^{i}$ as the whole output and input operation spaces in $t^{th}$ temporal step of all hardware instances for Layer $i$. We first find the ready time of $I_{t}^{n+1}$, which is the time when all data in $I_{t}^{n+1}$ are finished by the previous layer (Layer $n$). For each $I_{t_{i}}^{n+1}$, we need to check all $O_{t}^{n}$ and find the latest time step $t_{o}$ that $O_{t_{o}}^{n}$ has an overlap with $I_{t_{i}}^{n+1}$. If $t_{o}$ is earlier than the end time of Layer $n$, we can compute $O_{t_{i}}^{n+1}$ right after $t_{o}$ because the whole $I_{t_{i}}^{n+1}$ has been calculated. The computation of $O_{t_{i}}^{n+1}$ is overlapped with computations in Layer $n$ after $t_{o}$.

Then, with available instances, the process starts earlier with partial input to exploit overlapping execution between two layers. The ready timestamps $T_{t}$ for input data spaces at $t_{n+1}$ are determined by finding the latest output data space of Layer $n$ which intersects (unions) with any input data spaces of Layer $n+1$ for any instances at time step $t_{n+1}$. Our new evaluation considers the overlapped data spaces (computations) based on the hardware constraints to determine the overlapped performance as the new optimization metric.

The extensive parallelism exploited through computational overlap gains great performance improvement. To benefit from this advantage, Fast-OverlaPIM develops the overlap analysis algorithm to determine the accurate overlap time step results for evaluating the overlapped performance. In the PIM architecture, we conduct the overlap analysis at the bank level because the analysis at an upper (e.g., channel) produces too coarse-grained data spaces while a lower level (e.g., column) has too many instances that will make the analysis intractable.

Our previous work, OverlaPIM [29], utilizes the naive approach to determine the computational overlap by traversing through all data spaces at a target storage level and finding the ready timestamps. However, this analysis requires $Q(N*M)$ time complexity with overheads, where $N$ and $M$ represent the number of data spaces for Layer $k$ and Layer $k+1$ separately. Given the massive number of data spaces in PIM DNN acceleration, over $10^{7}$ in Bank level for some cases, this approach becomes unacceptably expensive and will strongly limit the search space for the framework due to the unsupportable large computation requirement during the runtime.

To develop an applicable framework, we proposed a fast analytical computational overlap analysis algorithm to implement Fast-OverlaPIM. First, as we mentioned in Section IV-F, we utilize Equation 1 to calculate the index incremental size for each loop level for the Layer $N$, in order words, the preceding layer. Then, for conducting the overlap analysis at the bank level, we traverse through the loops of Layer $N$ in an up-down order from DRAM to Bank level to get the finishing time step for the input data spaces of Layer $N+1$:

which is the output from Layer $N$.

During the traversal, we first propose an equation to determine the relationship between the loop and the increment of the lower bound for the data spaces:

where $n$ represents the $n^{th}$ in a down-up order loop, $D(k,p,q)^{n}$ is a list that stores the size for each $K$, $P$, $Q$ tensor element, and we denote $L(n)\subseteq K/P/Q$ when $L(n)$ decomposes the corresponding tensor.

Since each loop decomposes one dimension among $P$, $Q$, and $K$, in the following discussion, for simplicity, for each loop level, we utilize a single variable $d$ to represent the decomposed $K_{min}^{m},P_{min}^{m},Q_{min}^{m}$ dimension and ignore the rest. We define the $S(d)$ to store the lower bound of the decomposed data space and assign the initial value to $d$:

which will be updated during the up-down loop traverse.

We apply the following functions on each loop level $i$ to find the time step and the spatial element index of the output/input of Layer $N$/Layer $N+1$.

If $L(i)$ is a spatial loop, then

If $L(i)$ is a temporal loop, then

where $G(i)$ is found using Equation 1, $S$ denotes the lower bound for the spatial index of the input data space (i.e., the ID for the spatial element that generates the corresponding output from Layer $N$), $T$ denotes the lower bound for the temporal index of the input data space, which is the time step we referred to, and $D(x)$ represents the largest data space to awaiting for decomposing. The unmentioned dimensions remain unchanged in the equations. The calculation of $T$ is similar to Equation 2. To take the time steps required for filter multiplication for each decomposed data space into account, we also specifically trace the loop sizes for loop levels that decompose the weights (i.e. $R$ and $S$). The total sizes will be added to the temporal index for the finalized time step.

Although computational overlap enhances performance, the overhead for the analysis is non-trivial even with our lightweight algorithms. Therefore, it is critical to find a new method to search for more mappings in each overlap analysis. If we can generate the analysis statistics for different mappings in trivial time, we can significantly enlarge the search space, hence improving the search result.

We propose an overlap-based mapping transformation that can directly generate the evaluation results for different mappings based on the mapping that is analyzed in detail. Figure 9 shows an example of mapping transformation, where we mark the ready time for the input of each data space ($t_{x}$). The left part shows the original mapping, where no overlap is available because the latest ready time of all data spaces in a time step is the end time of the previous layer (i.e., $t_{3}$). For transformation, we reorganize the data spaces and reschedule data spaces at the same ready time, as shown in the right part, significantly decreasing the end time of the layer.

The transformation runs in two steps. First, it sorts the data spaces in the ascending order of ready time of input. After sorting, the algorithm allocates the memory resources for each data space based on the ready time. In practice, the number of data spaces with the same ready time can be larger than the number of memory resources. Therefore, a round-robin manner is used to schedule the data space with the same ready time to the same memory location. We should note that the transformation is not overhead-free because it might change the locations of partial sums that require data movements for reduction. Since the transformation does not require re-analysis of the data space and the complexity of the algorithm is $O(logN)$ bounded by the search, the transformation only introduces trivial runtime overhead during the process.

Fast-OverlaPIM supports the mapping search for all layers in the entire DNN model. To evaluate the whole network, we require descriptions of all layers and their corresponding mapping constraints and architecture configurations as inputs. These inputs can be generated automatically through our self-designed toolkit by providing information on architecture design and constraints. The workload parameters for each layer will be auto-generated and processed by Fast-OverlaPIM following the sequential order for analysis.

During the execution time, the optimization mapper generates candidate mappings based on the configurations, including both the architecture configuration and the mapping constraints. For each mapping, it generates the fine-grained temporal and spatial data spaces, as well as the PIM performance evaluation. Then, the framework calculates the overlap of consecutive layers based on their fine-grained data spaces and recalculates the performance considering the overlapped computations. Based on the overlapped result (i.e. the time step for ready output), Fast-OverlaPIM also transforms the current mapping into overlap-friendly mappings to increase the search space and improve the performance on latency reduction. The framework continues to update the best mapping based on the overlap-based performance until meeting the termination requirements (similar to Timeloop [16]), which is set to a fixed number of valid mappings in our framework.

Given that overlapping performance depends on both Layer $n$ and Layer $n+1$, finding the best performance mappings for all layers through searching and comparing mappings would be prohibitively expensive. For example, if we search for $k$ mappings in each layer, the total possible combination of mappings for all $N$ layers would be $k^{N}$. The exhaustive search for optimal mappings would be unacceptably expensive in this case. Thus, for each Layer $n+1$, the overlapping optimization search is done based on the best mapping found for Layer $n$. Our evaluation shows that such a linear method can produce high-performance mappings. We leave a more in-depth investigation of global optimization for future work.

We notice that the skip connections in ResNet models can also affect the whole network mapping optimization. However, the skip layers can be executed in parallel with other layers ($\geq 2$) from the same block, with careful mapping optimization, the skip layer will be completed during the execution time of other layers. Thus, its mapping will not affect the total latency optimization for the whole DNN network.

To better diminish the search space limitation for the whole DNN optimization and provide a more balanced priority for each layer in the optimization process, as mentioned in Section IV-A, we proposed our novel search strategies. Conventional whole network mapping optimization always analyzes layers starting from the first layer and forwarding to the next following the temporal order[29, 17, 15]. However, considering the interdependent relationship for performance between Layer $N$ and Layer $N+1$, searching from the beginning tends to optimize earlier layers better than later layers. With the restricted number of mappings being searched, searching mappings for Layer $N+1$ based on fixed mapping of Layer $N$ creates biased results. To address this, we introduced an interface that enables mapping exploration based on the fixed mapping of Layer $N+1$ for Layer $N$. This approach offers more mapping search flexibility and reduces timely bias during whole DNN mapping exploration.

More specifically, all succeeding layers are restricted to determine the overlap mapping based on the fixed mapping from the proceeding layer to reduce the search workloads from $k^{N}$ to $N\times k$. However, there exists the possibility that the succeeding layers can generate better overlap mappings based on the sub-optimal mappings of the proceeding layers and provide better throughput among all layers. The cycle performances of NN layers are dominated by data point accesses and data transfer, which will scale with the total number of parameters for each layer. Layers with larger output height and weight ($P$ and $Q$) and a larger number of input and output channels ($C$ and $K$) are more likely to become the performance bottleneck of the whole network optimization. We break the convention of starting generating the optimal mapping for Layer $1$. Our novel search interface allows users to select a middle layer as the starting point for the whole network optimization based on the size of input, output, and weight parameters. Thus, Fast-OverlaPIM can provide more insights into the whole network optimization within a linear time runtime increment.

In conclusion, we proposed 3 search methods to enlarge our search space. The “Forward” method is the conventional method that searches starting from the first layer following the temporal order. The “Backward” method starts mapping exploration from the last layer and finds mappings for previous layers based on the fixed mappings for its succeeding layer following the reverse temporal order. The “Middle” method triggers the whole network mapping search beginning at an intermediate layer. For our Fast-OverlaPIM framework, we explore the “Middle” method based on the layer with the largest output size (i.e. $P\times Q\times K$) and with the largest overall size (i.e. $P\times Q\times C\times K$). The “Forward” and “Backward” searches are conducted separately from the chosen layer.

Figure 10 shows the overall results of different mapping optimization algorithms. For ResNet-18, the overlapped latency of the best overlapping mapping (Best Overlap) is $1.6\times$ faster than the end-to-end latency without overlapping (Best Original). If we adopt the transformation in the search process, the best mapping (”Best Transform”) further improves the performance of “Best Overlap” by $2.9\times$. For VGG-16, “Best Overlap” provides $1.17\times$ speedup over “Best Original”, and ”Best Transform” provides $5.0\times$ speedup over “Best Original”. On a larger workload, ResNet-50, Fast-OverlaPIM demonstrates even better performance. “Best Overlap” generates $1.3\times$ faster mapping than “Best Original” and “Best Transform” is $18.1\times$ better than “Best Original”.

For comparison based on the same mapping with different algorithms, “Overlap Transform” and “Best Transform” achieve $1.4\times$ and $6.5\times$ speedup over “Original Transform” separately in ResNet-18. Fast-OverlaPIM gives a better improvement in VGG-16 based on this condition. “Overlap Transform” provides $2.0\times$ speedup over “Original Transform”. The overlap-based optimization with transformation (”Best Transform”) produces significantly better mappings, which is $22.0\times$ faster than “Original Transform”. $24.5\times$ speedup is gained by “Best Transform” over “Original Transform” on workload ResNet-50.

Figure 11 displays a performance comparison between our proposed Fast-OverlaPIM and OverlaPIM [29]. For a fair comparison, we run two tools in the same amount of runtime. For ResNet-18 and VGG-16, Fast-OverlaPIM achieves $7.6\times$ and $15.1\times$ better performance on the original cycles (“Best Original” over “OverlaPIM Original”). This improvement stems from the search space enlargement given the advancement of the runtime performance. With the transformation mechanism, Fast-OverlaPIM achieves $49.3\times$ to $76.1\times$ speedup over OverlaPIM (“Best Transform” over “OverlaPIM Original”). The relative speedup of $4.6\times$ and $18.1\times$ for the transform cycle compared to the original cycles from Fast-OverlaPIM also overcomes previous results of $2.1\times$ to $4.1\times$ performance improvement. The primary factor for this enhancement is that with analytical overlap analysis, Fast-OverlaPIM supports more detailed and accurate finish time step generation, which benefits transformation. Furthermore, it is important to note that our new framework is now able to handle larger workloads, such as ResNet-50, due to the significantly faster runtime (Section V-F).

Figure 12 shows the per-layer performance comparison over different mapping optimization algorithms. The figures are produced over a logarithm scale as some layers achieve very significant performance benefits. Figure 12 (a) displays the results on ResNet-50. As we observe, “Best Overlap” improves the performance largely (more than $2\times$ speedup) for only 10 out of 49 layers. On the other hand, “Best Transform” improves the performance from $4.8\times$ to $369.2\times$. Figure 12 (b) is the per-layer performance breakdown for ResNet-18. As shown in the figure, the overlap-based algorithms, both “Best Overlap” and “Best Transform”, find better mappings than the original method (”Best Original”). “Best Transform” gives at least $2.3\times$ and at up to $474.3\times$ speedup among Layer $2$ to Layer $20$. The proposed optimization achieves small performance improvements when the existing mapping algorithm (without overlap consideration) coincidentally produces mappings with a high overlap ratio, as shown in Figure 4. Figure 12(c) is the per-layer performance comparison on VGG-16. Even though 4 out of 13 layers fail to find better mappings with “Best Overlap” compared to “Best Original”. The mapping with transformation still shows a significant benefit of transformation, which is $3.8\times$ to $74.7\times$ speedup over the original method.

However, we can also observe that for “Original Transform” and “Overlap Transform”, all 3 workloads generate mapping with worse performance compared to “Best Original”. This observation also supports our motivation that the best mapping explored by Timeloop may not necessarily be the best mapping with overlapped computation.

We adopt Fast-OverlaPIM on various architecture settings where we allocate different amounts of memory resources for each layer. We compare the performance of different optimization algorithms in various architecture settings, as shown in Figure 13. For the sake of clarity and simplicity, we compared our search methods based on “Original Transform”, “Overlap Transform”, and “Best Transform” as they resulted from the same series of mappings.

The results show that, in ResNet-18, “Best Transform” is 6.5 $\times$ and 1.6$\times$ faster than “Original Transform”, and “Overlap Transform” for the 4-channel setting, similar but slightly better than the results shown in Figure 10 (the default 2-channel setting). The performance improvements on the 1-channel setting appear to be beneficial for the “Best Transform” algorithm. It achieves 1.6$\times$ and 22.8$\times$ speedup over the baseline. Across different settings, we observe similar performance on VGG-16. Fast-OverlaPIM also shows its memory sensitivity on our larger workload, ResNet-50. As shown in Figure 13, the whole network ResNet50 demonstrates the best speedup for “Overlap Transform” and “Best Transform”, where 2-channel and 4-channel settings have similar performance improvement on “Best Transform”, $31.0\times$ and $29.9\times$, separately. The speedup for the 1-channel setting for “Best Transform” in ResNet-50 is $14.6\times$. The performance improvements with “Overlap Transform” are $1.3\times$, $1.5\times$, and $2.2\times$ for each architecture setting. Such results prove that Fast-OverlaPIM is scalable and general for DNN mapping on PIM architectures.

As mentioned in Section IV-H, previous work [29] conducts overlap analysis by exhaustively comparing all data spaces of Layer $N$ and Layer $N+1$, which makes the analysis unacceptably expensive. Our Analytical Computational Overlap Analysis greatly improves the runtime efficiency. Figure 14 shows that the algorithm from Fast-OverlaPIM achieves $3.4\times$ to $323.1\times$ runtime speedup. As the number of data spaces gets larger, the speedup increases more than quadratically.

We experimented with our 3 search methods proposed in Section IV-K on ResNet-18, VGG-16, and ResNet-50. Again, similarly to Section V-E, for the sake of clarity and simplicity, we compared our search methods based on “Original Transform”, “Overlap Transform”, and “Best Transform”.

As shown in Figure 15, although the “Backward” method performs worst without transformation (“Best Original” and “Best Overlap”), on both ResNet-18 and VGG-16, “Best Transformation” with “Backward” method gains $1.1\times$ and $2.3\times$ better performance than with “Forward” method separately. The performance for different search methods on ResNet-50 is different from ResNet-18 and VGG-16. The “Middle” method achieves up to $1.2\times$ better performance than “Forward” with transformation, whereas “Forward” has $2.9\times$ better performance compared to “Backward”. However, for “Best Overlap”, “Forward” is $2.2\times$ better than the “Middle”.

Specifically, we explored the “Middle” with two heuristics as mentioned in Section IV-K, the choice of the intermediate layer to start the mapping search process is determined based on the layer with the largest output size (i.e. $P\times Q\times K=mid$) and with the largest overall input/output size i.e. $P\times Q\times C\times K=mid2$). The chosen starting layers are Layer$4$ and Layer$18$, Layer$2$ and Layer$9$, and Layer$10$ and Layer$41$ for ResnNet-18, VGG-16, and ResNet-50 respectively. We observed that the performance between two heuristic reaches is up to $41.9\times$. These results are very intriguing, which further supports our claim that the optimal mappings from conventional frameworks may not be the best mappings under PIM architecture with overlapping.

During our experiments, we also observed an insight that with different search methods, the same layers from the same NN model can have very different performances. For ResNet-18, 16 out of 20 layers generate different mappings with different search methods. And for VGG-16, 12 out of 13 layers produce different mappings.

As mentioned in Section IV-B and Section IV-D, Fast-OverlaPIM is a versatile PIM-based mapping optimization that can accommodate various PIM-based architectures. Figure 16 presents the per-layer performance comparison of the ReRAM-based PIM architecture on ResNet-18. ReRAM-based PIM Fast-OverlaPIM achieves $1.16\times$ overall speedup for “Best Overlap” and $2.42\times$ overall speedup for “Best Transform”, which demonstrates that Fast-OverlaPIM can support PIM architectures other than DRAM-based PIM.