2.1 CNN Accelerators and Processing Elements

Having millions of multiplication-accumulate (MAC) operations, a convolutional (CONV) layer can be expressed by six or seven nested loops ^[10]. On the other hand, a CONV layer can be transformed into a general matrix-matrix or matrix-vector multiplication using the im2col transform ^[11]. As a result, two typical PE designs for generic CNN accelerators are the systolic arrays ^[12,13] and inner-product multipliers with an adder tree ^[14,15]. ShorcutFusion ^[1] consists of $T_{o}$ CONV kernels. Each CONV kernel consists of $T_{i}$ multipliers and an adder tree. In particular, $T_{i}$ and $T_{o}$ were set to 64, resulting in 4096 multipliers in total.

Assume that $C_{i}$ and $C_{o}$ are the number of input feature channels and output filters, respectively, for a given CONV layer. The number of computing cycles is as follows:

where K is the filter size, and H and W are the height and width of the output feature maps, respectively.

2.2 ShortcutFusion

Fig. 1 shows the architecture of the CNN accelerator in ^[1]. In particular, it consists of a controller, two DMA modules for loading the weights and the input feature maps (IFMs) of the model, and one DMA module for writing the output feature maps (OFMs). The controller selects either a row-based weight reuse scheme or a frame-based weight reuse scheme. Notably, although there are many loop interchange or tiling options for six nested loops, ShorcutFusion utilizes only two weight reuse schemes by observing that a CONV layer may have (1) large IFMs with a small number of weights or (2) small IFMs with a large number of weights.

The two reuse schemes are described in Fig. 2. The frame-based reuse scheme is utilized when the IFMs are small enough to be stored in an on-chip buffer. In particular, it reuses the weight blocks (i.e., $K\times K\times T_{i}$ pixels) while the input sliding cube (i.e., $K\times K\times T_{i}$ pixels) passes through a single frame of the IFM, as shown in Fig. 2(a). The input data in the sliding cube are convolved with $To$ weight blocks, generating the partial sum of the OFM (i.e., $H\times W\times T_{o}$ pixels). When the input sliding cube hits the end of the frame, it moves towards the channel direction to generate the next partial sum, which is accumulated to the previous result.

The row-based weight reuse scheme is utilized when the IFMs are relatively large, and the number of weights is small. In particular, weights are preloaded and reused while the input sliding cube passes through a single row, as shown in Fig. 2(b). This generates the partial sum of the OFM (i.e., $1\times W\times T_{o}$ pixels). When the sliding cube hits the end of the row, it moves towards the channel direction, remaining in the same row. By remaining in the same row, the generated output can be accumulated to the previous output, which becomes the final output if the input sliding cube hits the end of the channel.

The main controller selects either a frame-based dataflow or a row-based dataflow depending on the weight reuse scheme. In frame-based dataflow (red arrow in Fig. 1), the IFMs are fetched from the on-chip buffer and go through the line buffer and the CONV window module. When the CONV kernel generates the OFMs, it writes the OFMs to the on-chip buffer. In the row-based dataflow (blue arrow in Fig. 1), however, the IFMs are fetched from the off-chip memory. The input loader module loads the IFMs from the off-chip memory using DMA. When the CONV kernel generates the OFMs, it writes the OFMs to the output buffer. The output writer module also stores the OFMs to off-chip memory using DMA.

Fig. 1. Block diagram of CNN accelerator in[1].

Fig. 2. Weight reuse scheme in Shortcut-Fusion: (a) Frame-based weight reuse; (b) Row-based weight reuse. Borrowed from Fig. 3. in[1].

2.3 Motivations

YOLO-v3 ^[5] is a well-known object detector that has achieved a good tradeoff between model accuracy and real-time execution. In particular, the number of input and output channels $C_{i}$ and $C_{o}$ in YOLO-v3 are 64, 128, 256, 512, and 1024. Therefore, it is likely for the PEs of ShortcutFusion to be fully utilized according to Eq. (1). Unfortunately, as reported in ^[1], ShortcutFusion only achieves a utilization of 68.42% for YOLO-v3. This phenomenon prompted this study to determine the sources of underutilization in which PEs are forced to IDLE during data movement.

3.1 Under-utilization of PEs

This subsection specifically quantifies the layer-wise PE utilization for YOLO-v3 using ShortcutFusion. Although the frame-based weight reuse scheme generally achieves higher utilization than the row-based one, it may require a huge on-chip buffer to store IFMs. Therefore, following ^[1], the cutpoint is set to 9 to meet a constraint of on-chip buffer size. As a result, a row-based weight reuse scheme was applied for CONV layers 0-8, while a frame-based weight reuse scheme was applied for the remaining CONV layers 9-76. Table 1 lists the profiling results. As shown in the third row, the ‘Frame-based’ category (i.e., layer with the frame-based dataflow) shows a relatively high PE utilization of 81.15%. The ‘Row-based’ category (i.e., layer with the row-based dataflow) shows poor PE utilization of 33.89%. Specifically, the ‘Stride = 2’ category (i.e., layers 1, 4, 9, 26, and 43 with stride = 2) suffers from severe under-utilization with a PE utilization of 34.01%. The phenomenon occurs for both the row-based scheme (e.g., layers 1 and 4) and the frame-based scheme (e.g., layers 9, 26, and 43). Because those ``stride=2'' layers account for 24.35% of the overall execution time, their low utilization causes a utilization drop for the entire network.

The following subsections analyze the source of low utilization on those layers and propose methods to enhance the utilization.

3.2 Optimization on Stride = 2 Convolution

Fig. 3 shows the dataflow during the 3${\times}$3 convolution. CONV kernel needs nine cycles to consume one window data (i.e., $3\times 3\times \mathrm{T}_{\mathrm{i}}$ pixels). Therefore, to synchronize with the CONV kernel, the controller must fetch one window data for every nine cycles.

In the case of stride = 1 convolution, however, 2-column data (i.e., $3\times 2\times \mathrm{T}_{\mathrm{i}}$ pixels) can be reused from the previous window data, as shown in Fig. 3(a). As a result, only one column of data (i.e., $3\times 1\times \mathrm{T}_{\mathrm{i}}$ pixels) needs to be fetched from the controller every nine cycles.

Fig. 3(b) shows the dataflow during stride = 2 convolution. In the case of stride = 2 convolution, only one column of data can be reused from previous window data. Therefore, two-column data must be fetched from the controller every nine cycles. On the other hand, it takes 18 cycles to fetch 2-column data because the fetching speed of the original accelerator is fixed. This makes the CONV kernel idle for nine cycles, which abruptly decreases the PE utilization.

A flexible prefetching scheme was proposed to resolve this issue (Fig. 3(c)). When conducting stride = 2 convolutions, the controller increases the data fetching speed, thus fetching 2-column data every nine cycles. As a result, the window data can be ready for every nine cycles, and the CONV kernel does not need to wait for the next window data, which avoids unnecessary stall cycles.

One more optimization point exists to increase PE utilization during stride = 2 convolution. The controller requires three-row data (i.e., $3\times \mathrm{W}\times \mathrm{T}_{\mathrm{i}}$ pixels) to fetch the column data. Therefore, three-row data should be prefetched to the line buffer before the computation starts. On the other hand, after prefetching the first three-row data, the amount of data that needs to be prefetched is smaller because the dataflow can reuse the row data from the line buffer.

In the case of stride = 1 convolution, with only a single row of data (i.e., $1\times \mathrm{W}\times \mathrm{T}_{\mathrm{i}}$ pixels) prefetch, all three-row data are ready because two can be reused from the line buffer. For the stride = 2 convolution, however, it requires two-row data because only one can be reused. The original accelerator always prefetches the same amount of row data (i.e., single row data) regardless of the layer type. Therefore, it suffers from under-utilization during the stride = 2 convolution because of insufficient prefetching.

This can also be resolved by applying a flexible prefetching scheme, which flexibly chooses the amount of prefetching. Using the proposed method, the amount of prefetched data is increased. Hence there is no under-utilization.

Fig. 3. Dataflow during a 3x3 convolution: (a) stride = 1; (b) stride = 2; (c) stride = 2 with optimization method.

3.3 Optimization on Row-based Dataflow

This subsection analyzes the source of under-utilization in row-based dataflow and presents an optimization method to increase PE utilization in the row-based dataflow.

During the row-based dataflow, the results showed lower PE utilization than frame-based dataflow. This is because the location of the feature map is different. In frame-based dataflow, the accelerator reads the IFMs from the on-chip buffer and writes the OFMs to the on-chip buffer. Using the on-chip buffer, the data bandwidth is very high, which supports the rapid movement of input and output data. This makes it easy to pipeline the whole computation, which can easily utilize the PEs.

In row-based dataflow, however, the accelerator reads the IFMs from off-chip memory and writes the OFMs back to off-chip memory. Because the data movement of input and output data is slow, it is difficult to pipeline the computation fully in row-based dataflow. Thus, PE utilization is lower than frame-based dataflow.

Fig. 4. shows a timing diagram of the CONV operation and DMA operation in the row-based dataflow. As shown in Fig. 4(a), the CONV and DMA operations are not pipelined, leading to low PE utilization. Both operations cannot be pipelined because of the data hazard caused by concurrent access to the output buffer. During the CONV operation, the CONV kernel writes the OFM to the output buffer. During the DMA process, however, the output writer reads OFM and transfers the data to off-chip memory. If both operations are pipelined, the OFM data can be overwritten by the next CONV kernel before the DMA. Although the next CONV operation starts later than the DMA, a data hazard can occur due to the low bandwidth of off-chip memory.

The output buffer is reconstructed in the proposed method to enable the pipeline between two operations. The reconstructed output buffer consists of two separate buffers. Using two separate buffers, both operation switch between two buffers (Fig. 4(b)). When the output writer reads the OFM data from one buffer, the CONV kernel writes the following OFM data to the other buffer. Because of this, the data hazard is removed, and both operations can be well-pipelined.

Fig. 4. Timing diagram of CONV operation and DMA operation in row-based dataflow: (a) Before optimization, both operations are not pipelined; (b) After optimization, the operations are well-pipelined.

4.1 Evaluation Method

This subsection presents the evaluation method for PE utilization. The PE utilization can be measured by the total operation count divided by the maximum number of operations with a given number of PEs. Since each PE can execute two operations (i.e., 1 multiplication + 1 addition) for every single cycle, the maximum number of operations is $2\times \left(PE\,\,count\right)\times \left(cycle\,\,count\right)\,.$ Therefore, PE utilization can be formulated as follows:

where $OP_{MUL}$ is the number of multiplications; $OP_{ADD}$ is the number of additions; $cycle$ is the number of cycles.

In addition, $OP_{MUL}$ and $OP_{ADD}$ are formulated as follows:

where $K$ is the width of the convolution kernel; $C_{i}$ is the number of input feature channels; $C_{o}$ is the number of output filters; $H$ is the height of OFMs; $W$ is the width of the OFMs.

The number of cycles can be obtained from RTL simulation. Therefore, PE utilization can be measured using this equation.

4.2 Evaluation Result

This section shows the results of two optimization methods compared to the original CNN accelerator ^[1]. All results are based on the YOLO-v3 network. As shown in Table 2, with the stride = 2 convolution optimization method, the average PE utilization in stride = 2 convolution achieves 67.21%, which is improved by 33.20% from the baseline. This is because the proposed flexible data prefetching scheme removes the unnecessary stall cycles. In addition, with the row-based dataflow optimization method, it achieved a PE utilization of 52.53%, which is improved by 19.1%. This shows that the reconstructed output buffer successfully increased the PE utilization by pipelining the PE operation and writing OFMs.

Fig. 5. shows the layer-wise PE utilization of the three different optimization steps. For layers 1, 4, 9, 26, and 43, stride = 2 convolutions were performed, so the stride = 2 convolution optimization (yellow in Fig. 5) shows the improvement. During the layer from 0 to 8, the accelerator used row-based dataflow, so the row-based dataflow optimization (blue in Fig. 5) shows improvement.

Table 3 lists the overall PE utilization by applying optimizations. The results indicated that ShortcutFusion++ achieved a PE utilization of 80.95%, showing 12.53% improvement from the baseline.

Fig. 5. Layer-wise PE utilization with the optimization method.