Runtime Design Space Exploration and Mapping of DCNNs for the Ultra-Low-Power Orlando SoC Runtime Design Space Exploration and Mapping of DCNNs

These parameters are the number of CAs, on-chip memory ($MEM_{SIZE}$), and external memory bandwidth ($EXT_{BW}$) available to a DCNN workload. They are used to simulate on-chip resource sharing in the context of multiple simultaneous workloads running. Therefore, we limit the availability of each resource to achieve Orlando model configuration. The range of values for $MEM_{SIZE}$ is 128 KB to 4 MB, which is the total amount of on-chip memory. The values for $N_{CA}$ range from 1 to 8 with even values, because with odd numbers of accelerators, it is hard to take advantage of chaining and parallel accelerators. The $EXT_{BW}$ parameter has a range from 200 MB/s to 3 GB/s.

In principle, DVFS is a runtime feature of the platform. In our exploration, it is considered fixed for all layers of a given CNN. This is due to the latency required to adjust to the new DVFS configuration that is usually significantly greater than a single inference latency of a CNN topology. This parameter allows us to run the inference of the networks at different energy-efficiency points and allows the system to adapt to the needs of the application. The available values of DVFS configuration are listed in Table 1.

The convolutional layer mapping parameters are also shown in Table 1. These are mainly related to the configurable parameters of the stream switch and CAs, shown in the coprocessor subsystem in Figure 3. The stream switch enables different numbers and combinations of CAs to run either in parallel or in chain with the help of the DMA engines available on the platform. These different modes affect the execution performance and data reuse patterns, hence directly influencing the external bandwidth usage of the system. The adjustable runtime parameters of the CAs basically allow the CAs to adapt the characteristics of the specific workloads of a convolutional layer. The $N_{CA\_chain}$ and $N_{CA\_parallel}$ parameters (also indicated as M and N in Figure 4(b) (Parallel/Chained Execution)) are related to how a set of (total of $N_{CA}$) accelerators are configured in the stream switch, where $N_{CA\_chain}$ is the number of chained accelerators and $N_{CA\_parallel}$ is the number of parallel accelerator chains. Since the total number of CAs available to the given workload is limited, this constraint on $N_{CA\_chain}$ and $N_{CA\_parallel}$ is expressed by Equation (1), where $L$ is the set of convolutional layers for a given network.

Fig. 3. Orlando SoC top-level block diagram [Desoli et al. 2017].

Fig. 4. Convolution layer mapping and configuration of multiple accelerators.

Fig. 5. The overall DCNN system stack for the Orlando SoC.

Fig. 6. Overview of the runtime DSE and mapping flow.

The parameters $N_{PAR\_KERNEL}$ and $BATCH_{SIZE}$ are the number of parallel kernels and the number of feature channels (a.k.a. feature batches) that have to be processed by a single CA, respectively. The physical limitation on these parameters comes from the design of the CAs (see Section 2). The last two parameters, $STRIPE_{SEQ}$ and $N_{STRIPES}$, relate to how the data is partitioned in the situation that data needed for a single layer cannot fit into the on-chip memory resources allocated to the network. Therefore, the feature map is partitioned into $N_{STRIPES}$, and only one stripe and filters related to those stripes are copied to the memory, and all convolution operations are performed in a sliding window manner on that chunk of data that resides in the on-chip memory. The $STRIPE_{SEQ}$ parameter determines the way the stripes are formed. It can be either depth-first or vertical-first as represented in Figure 7. In the depth-first case, the feature data is partitioned from the horizontal dimension so that CAs can process the input feature data in the depth-first order (Figure 7(b)). In the vertical-first case, they are partitioned from the channel dimensions, and CAs process the data in the vertical stripe first before moving on to the next stripe (Figure 7(c)). The two different ways of striping exist because different layers might have different memory access patterns as shown in Figure 2.

Fig. 7. Feature map striping.

These parameters implicitly allow different kinds of data reuse available naturally in the convolutional layer. The depth-first approach allows more data reuse of output feature maps by accumulating in smaller feature map regions. In contrast, the vertical-first approach takes advantage of reuse of kernel weights, as each sliding window instance shares kernel parameters. There is also the possibility of including the horizontal-first approach. It would have had similar trade-offs to the vertical-first approach; however, the CAs in the Orlando architecture can take advantage of larger width feature maps. For that reason, we did not consider the horizontal-first approach in our methodology.

To simulate the situations in which the data fits into the allocated on-chip memory, we prune the configuration points with total memory requirement (Equation (2)) that exceeds the $MEM_{SIZE}$. The details of how the memory footprint is calculated are explained in Section 5.3.

Considering the design of experiments selected in Table 1, the cardinality of the design space is composed of 1,080 configuration points. Since the second exploration phase depends partially on the configuration point selected in the first phase, it is much harder to analytically formulate or indicate the cardinality of a combined design space.

To calculate the execution time for each layer in the network, we compute the number of clock cycles necessary for the accelerators to finish computation of the layer and the time required for the data transfers between the on-chip memory and the external memory. Let us assume that the data needed for the layers like filter weights or the previous feature map reside in the external memory.

Given that the presence of DMA engines (Figure 3) in the Orlando architecture enable asynchronous memory transfers, we assume that memory transfers and CA executions overlap (Equation (3)).

Total accelerator execution time is calculated by using Equation (4). The $T_{clk}$ is the clock period given by the DVFS configuration of the Orlando platform, and $CA_{work}$ is the number of cycles of work for a CA to finish a batch of the feature map. The cycle count depends on $IFM_W$ and $IFM_H$, which respectively represent the width and height of the 3D input feature map ($IFM$) from a specific layer in the CNN topology. How many cycles are spent actually toward the layer computation is represented by the $CA_{utilization}$ coefficient. The $CA_{utilization}$ coefficient in the equation is calculated per layer according to Section 5.2, and it takes values ranging from 0% to 100% (in the ideal case). The term $R_{CA}$ (Equation (6)) represents how many times (a.k.a. rounds) the CAs need to run to compute a single set of feature activations. The term of $R_{CA}$ is affected not only by the convolutional layer parameters $IFM_D$ and $N_{KERNELS}$ in a layer but also by the runtime parameters as described in Equations (7) and (8).

Equation (7) describes how many times an accelerator chain needs to run to consume all input feature channels ($IFM_D$). The whole chain of CAs is configured with the same $BATCH_{SIZE}$ parameter; therefore, in one full execution of spatial dimensions ($IFM_W$ and $IFM_H$) of the feature map, a chain of CAs can process $BATCH_{SIZE} \times N_{CA\_chain}$ of channels. Similarly, the number of rounds needed to run for using all of the kernels is shown in Equation (8). The total number of kernels finished can also be calculated using $N_{PAR\_KERNEL} \times N_{CA\_parallel}$ since parallel CAs are loaded with different sets of kernel filters and $N_{PAR\_KERNEL}$ defines the number of kernels loaded in each CA.

As shown in Equation (9), $T_{mem\_access}$ depends on the bandwidth requirements of features, kernels, and output values for the layers and the external bandwidth of the system. The way memory access and the footprint are calculated is detailed in Section 5.3.

The term $T_{clk}$ used in the models comes from the clock frequency given by the selected DVFS configuration.

The utilization model is introduced to estimate the wasted cycles per layer for CAs. The main reason there are cycles not utilized is that CAs need at least ($K_H-1$) lines of feature maps and $K_W$ amount of pixels to start producing an output. The delay in units of cycles is expressed by Equations (11) and (12).

The main factors that play roles in underutilization are the feature map and filter kernel dimensions. Therefore, the characteristics of a layer and its workload are essential to attain accurate utilization that leads to a more precise model. The delay values $D_{lstartup}$ and $D_{fstartup}$ are wasted cycles due to the line start-up and frame start-up. By using these wasted cycles along with cycles that actually produce an output, $CA_{utilization}$ is calculated (Equation (10)).

Figure 8 shows the progression of a CA through one frame of a feature map. The red lines signify data already loaded into the CA buffers, whereas yellow lines indicate data that need to be loaded that stall the CAs. The blue rectangle shows the kernel window. When a dashed line is shown, it means that it is stalled and waiting for data. Although Figure 8 shows 2D data, there is also a batch of feature map channels that is characterized by $BATCH_{SIZE}$ in Equations (11) and (12). In Figure 8(a), at the beginning of the frame $K_H-1$ lines must be loaded (yellow lines). This frame start-up cost is also formulated in Equation (12). In Figure 8(b), after the (red) lines are loaded, the CA waits for $K_W$ pixels for the one line (shown by a partial yellow line). After it is loaded, the CA starts to execute in a sliding window fashion, whereas the DMA engines load the necessary data for the next pixels of the feature map, as shown in Figure 8(c). When the CA engine reaches the end of a line (Figure 8(d)), it needs to move on to the next line. However, it requires $K_W$ amount of pixels of the next line to produce an output and to begin a sliding window (Figure 8(e)).

Fig. 8. CA execution progression with data stalls.

Besides the aforementioned underutilization, there is also the time to configure the whole acceleration framework to get the dataflow. However, we decided not to include this cost in the model because it corresponds to 20 to 40 register file accesses per layer, and this is negligible with respect to the time required to run a layer.

The memory usage model estimates the memory footprint of the input feature map, weight filters, and output feature map. In the case of input feature maps, due to the striping, the size of stripes are considered. In this way, it is possible to utilize the on-chip memory by taking advantage of spatial locality. The striping is explained in Section 4.3.

To calculate the memory occupied by an input feature stripe, Equations (13) and (14) are used. In the case of no striping (# of stripes == 1), Equation (13) is used when the whole feature map is located in the on-chip memory. Otherwise, Equation (14) is used to account for the overlapping regions of the kernel windows. However, to keep the equation simpler, the kernel stride factor is assumed to be equal to 1. This leads to ($K_{H} - 1 = 2$) for both VGG-16 and Tiny-Yolo(v2).

The model introduced in this work considers memory transfers and the CA executions overlapped by taking advantage of DMA engines and double buffering. Due to the double buffering conditions, when there is a requirement to have more accelerator batch runs (indicated as $R_{batch}$), the execution model requires two stripes. Thus, one buffer can be used for data transfers, whereas accelerators work on the other feature stripe (Equation (15)).

Similarly, the memory footprint of kernel filters is also calculated as shown in Equation (16). $MEM_{kernel}$ is mostly affected by the convolutional mapping parameters, as they describe how the CAs will consume and process the data. Again, due to the usage of double buffering, two different kernel buffers are assumed to exist simultaneously.

Last, the output of CAs, also known as output feature maps, might consume on-chip memory in the form of partial accumulation buffers. This concept is considered in Equation (18). Hence, if there are multiple batch rounds, it means that the system does not need accumulation buffers and streams out the data directly to the external memory for the next layer. Additionally, when the striping is depth-first, CAs will process input channels first and the accumulator buffers hold just a subset of the output feature map size ($OFM_W \times OFM_H$). This relation is shown in Equation (17).

Equations (19), (20), and (21) describe the relationship between the memory footprint and the bandwidth for input feature maps, kernel parameters, and output feature maps, respectively. The input feature and kernel parameter bandwidth usage are related to how many times the configured CAs need to run to complete one layer and the output feature bandwidth equals to the total size of the output feature map in bytes since the outputs will be transferred only once to the external memory.

These bandwidth usages are critical in terms of determining the total time required for accessing the external memory. In an ideal mapping, it should be equal to or less than the computation cycles of the CAs; therefore, the transfer times are overlapped with computation via DMA (Equations (9) and (3)).

We obtained a quick but accurate enough estimate of the power consumption of the CA system based on our internal tests and measurements of hardware efficiency, and we considered a network-level model based on the aggregated data obtained from the performance model. To estimate the average power consumption, we introduce Equation (23), where the $GOPs_{i}$ term is based on the layer configuration parameters of layer ${\it i}$ (using Equation (22)), and it is normalized to its execution time. Then it is divided by the $GOPS/W$ metric, which is the hardware efficiency value that comes directly from the $DVFS_{CONFIG}$ selected.

In Equation (22), the terms $OFM_{W_i}$, $OFM_{H_i}$, and $OFM_{D_i}$ represent the width, height, and number of the output feature map for each layer $i,$ respectively.

After the power consumption for the network, the efficiency is calculated using Equation (24) as a unit of $fps / W$.

The Orlando CAs, as described in Section 2, are natively capable of handling 3 × 3 convolution kernel masks. However, some recent DCNN topologies (e.g., Howard et al. [2017]) include depthwise convolution and pointwise convolutional layers. Although these two types of layers are not natively supported by Orlando, we have optimized mapping of depthwise and pointwise convolutions on Orlando.

Depthwise convolutions differ from regular convolutional layers in that they have kernel masks with only one channel. In this way, each kernel corresponds to one channel of the input feature map. To map these layers, we consider the $BATCH_{SIZE}$ parameter equal to the $N_{PAR\_KERNEL}$ parameter, and we do not use CA chaining due to the lack of accumulation along the feature channel dimension. Furthermore, because kernel masks contain separate channel dimensions, we have $R_{batch} == 1$. In this way, it is possible to process multiple kernels with corresponding input feature channels utilizing line buffers and MAC clusters in CAs.

Pointwise convolutions are convolutions with kernel masks with a single dimension, and hence the feature map reuse due to the sliding window is not present. This creates problems for CA utilization, as the MAC clusters are designed to take advantage of the sliding window. Nevertheless, to provide acceleration support for such convolutional layers, each one of the MAC operations in the channel dimensions is mapped to different MAC clusters in a CA and utilizes a cluster for a dot product. Since each cluster is composed of 3 MAC units and only one of them is used for computation purposes, the maximum achievable utilization is only one third of a 3 × 3 convolutional kernel. Because CAs contain 12 MAC clusters, the $BATCH_{SIZE}$ is limited to 12 to enable the mapping described previously.

In this section, we compare our analytical model with a board implementation of an in-house DCNN, namely Pico-Yolo. Since the CA runs are orchestrated by one of the DSPs embedded in the Orlando SoC, their overhead is included in the performance measurements. To remove this overhead from the measurements, the relationship between the rounds of CA runs ($R_{CA}$) and the error of our model with respect to the board implementation is estimated with linear regression for both 200 MHz and 800 MHz (Figure 9) corresponding to the values 1 and 3 of $DVFS_{CONFIG}$ reported in Table 1. The accuracy of the linear regression results is summarized in Table 4. The p-value in Table 4 shows that the slopes in Figure 9(a) and (b) reject the null hypothesis; therefore, we can statistically assume that the slope shows the processor overhead per round.

Fig. 9. Model characterization results.

To evaluate the accuracy of our model, expressed as the absolute percentage error for each layer, we used Equation (25), where the terms , and express the error, predicted execution time, and board execution time, respectively.

Moreover, we use the weighted mean on the layer accuracy error, where the weights are the number of operations per layer. The predicted execution time is given by our model adjusted by the processor overhead estimated by linear regression according to the overhead per round expressed in Table 4. Overall, our model introduces an error of 15.63% and 15.56% for the 200 MHz and 800 MHz cases, respectively. This error is due to the internal memory bank and bus congestion because the board implementation does not include data striping to multiple memory banks.

In the first set of experiments, to evaluate the scalability of the DCNN workloads mapped to the Orlando architecture, we estimated the performance and power consumption by using the proposed models on a number of different configurations by varying the number of CAs. We assumed a total on-chip memory allocated to the DCNN workload of 512 KB. Scalability results are reported in Figure 10 and Figure 11, in terms of power and performance by varying the DVFS configurations (as reported in Table 1) and the number of CAs (1, 2, $4,$ and 8). We report the normalized power/performance results for two different values of the external memory bandwidth. Power consumption values (bars) and performance values (lines) are normalized with respect to a single CA assuming the 0.575 Vdd/200 MHz configuration. For each configuration of Vdd/frequency, we analyzed the scalability in terms of power and performance by varying the CAs.

Fig. 10. Pico-Yolo (left) and Tiny-Yolo(v2) (right) normalized power and performance scaling by varying DVFS configurations (refer to Table 1) and number of CAs for two values of external memory bandwidth.

Fig. 11. MobileNet (left) and VGG-16 (right) normalized power and performance scaling by varying DVFS configurations (refer to Table 1) and number of CAs for two values of external memory bandwidth.

In the case of 800 MB/s external bandwidth, the performance scales up to the DVFS configuration 3 (corresponding to 0.7 Vdd/450 MHz) across different workloads. However, when the bandwidth increases to 1.6 GB/s, the results start to show some differences between the workloads and number of CAs allocated. With 1.6 GB/s external bandwidth, MobileNet workload scales up to the configuration 5 (1.0 Vdd/950 MHz), whereas VGG-16 scales differently in the ranges between 1 to 2 CAs and 4 to 8 CAs. Considering 1 to 2 CAs, the performance is still saturated at configuration 5; however, when using 4 to 8 CAs, performance is limited by the external bandwidth at DVFS configuration 4 (0.875 Vdd/650 MHz). Similar behavior is observed by using Pico-Yolo and Tiny-Yolo(v2): the 4 to 8 CAs allocation saturates at DVFS configuration 4 (0.875 Vdd/650 MHz) and 3 (0.7 Vdd/450 MHz), respectively.

In this section, we evaluated the benefits due to the adaptivity of the proposed methodology by comparing our adaptive mapping to the one-fits-all mapping applied to the different convolutional layers. Evaluation results are reported in Figure 12 for VGG-16, Tiny-Yolo(v2), and MobileNet. For each network, the one-fits-all mapping has been calculated by selecting the best mapping based on memory usage, as reported in Figure 2, then using this mapping done at design time for all of the other convolutional layers. The adaptive mapping is obtained by choosing the best mappings resulting from the DSE for each layer as proposed in Section 3.

Fig. 12. Throughput comparison of adaptive mapping vs. one-fits-all mapping by varying the convolutional layers for VGG-16, Tiny-Yolo(v2), and MobileNet.

For the three selected networks, Figure 12 reports the throughput expressed as GOPs per second on the y-axis by varying the convolutional layers on the x-axis. We assume eight CAs, 512 KB of on-chip memory, 800 MB/s external bandwidth as resource allocation, and 0.6 Vdd/266 MHz DVFS configuration. In Figure 12(a), the sixth convolutional layer is selected for one-fits-all mapping, because it represents the middle ground between the feature memory and filter memory usage presented in Figure 2(a) and (d), respectively. Similarly, in Figure 12(b), the fourth layer is selected for the one-fits-all mapping according to the results shown in Figure 2(b) and (c). In Figure 12(c), the fifth convolutional layer is selected as one-fits-all being one of the most computational heavy layers in terms of the number of operations.

For the three selected networks, the throughput of the adaptive mapping outperforms or matches the one-fits-all mapping for all of the convolutional layers. (The cases where the throughput is equal correspond to when the adaptive mapping used is identical to the one-fits-all). We can notice that the throughput of the first layer is very small for both adaptive and one-fits-all mapping, because the channel size for the first layer is very small (since the input is a three-channel RGB image), and it reduces the amount of data reuse generating utilization problems with eight CAs. For MobileNet (Figure 12(c)), there is an alternating trend for the layers, because the utilization of the hardware is significantly different between depthwise convolutions and pointwise convolutions. The second reason is that the depthwise layers with a stride factor of 2 (layers 4, 8, 12, and 24) reduce the data reuse within the sliding windows.

CA utilization is explored in terms of low-memory (128 KB) and high-memory (512 KB) options for the selected workloads. For each option, we analyzed the behavior with 400 MB/s, 800 MB/s, and 1.6 GB/s external bandwidth. The results include utilization of accelerators per each layer of the networks and aggregated with a weighted average for the whole network. The y-axis of Figures 13 and 15 represents the percentage CA utilization (useful computation cycles) in the range from $25\%$ to $100\%$, whereas the y-axis of Figure 14 is in the range from $70\%$ to $100\%$. The difference between VGG-16 and the other networks is that VGG-16 does not contain any pointwise convolutional layer, so the minimum utilization achieved on one of its layers is larger than 70%. For space reasons, we reported the results for 800 MB/s only; however, the behavior obtained for 400 MB/s and 1.6 GB/s is quite similar. The number of allocated CAs is reported as $\#ca$ for each memory option and workload in Figures 13, 14, and 15. Since the results are after exploration of mapping parameters per each layer, the utilization values are the best values under the assumption of allocated resources and DVFS parameters. The results summarize how much of the $T_{compute}$ mentioned in Section 5.1 is utilized for actual meaningful computation. Due to the stalls during line start-up and frame start-up detailed in Section 5.2, some cycles are spent before either the pipelines of CAs are filled or waiting for data to be ready in the CA's buffers. This utilization concept is mostly independent of the data stalls due to limited external bandwidth. However, with increased bandwidth, our exploration methodology tries to include faster compute configurations; thus, it prefers higher-utilization mappings. In the VGG-16 workload, the low memory allocation mostly affected the first layers of the network. The main reason for this behavior is that with low memory, it is not possible to put more kernel filters on-chip than what is necessary to take advantage of more than 1 to 2 CAs (Figure 14). In the Tiny-Yolo(v2) workload, the ninth layer is quite different compared to the other layers, and it reaches below 30% utilization because the ninth layer is a pointwise convolutional layer (Figure 13). However, in terms of number of operations, the contribution of this layer is quite insignificant (see Table 3). The MobileNet workload differs from the previous two DCNN workloads significantly since it is mainly composed of pointwise and depthwise convolutions. Because of this, we can see alternating utilization patterns, where pointwise layers (3, 5, 7,…, 27) are below 30% utilization and depthwise convolutions with stride 2 (4, 8, 12, 24) are significantly lower than other depthwise convolutions (Figure 15). The geometry of the convolutional layers plays an important role, since the channel dimension (depth) of the input feature maps are shallow in the first layers of the network; therefore, it is also hard to utilize chained accelerator configurations. Nevertheless, the utilization for the first four layers is higher than 85%. The explanation comes from the height and width of the input feature map since first lines of a frame and beginning of each line cause wasted cycles for the CAs, larger feature maps are much more efficiently processed due to the amortized cost of CA stalls. This effect is also visible when we observe layers 11, 12, and 13, which have lower utilization due to smaller 14 × 14 feature dimensions. A similar situation is given also for the Tiny-Yolo(v2) workload (Figure 13). The last three layers (layers 6–8) have the lowest utilization of close to 70% (except the ninth layer). Again, the reason is the dimension of the feature map being 13 × 13. However, layer 2 achieves the highest utilization numbers under multiple CAs, which is explained by the larger feature map and having enough input channels to fill the accelerators completely. With higher memory allocations, the utilization drawback in the first layer is mitigated. Even if we are not able to show the results for all combinations of the resource allocation, with the choice of the best convolutional layer mapping, it is possible to achieve more than the 70% utilization for all resource allocations for the layers that the Orlando CA natively supports. This confirms the importance of adaptive mapping techniques to take advantage of the accelerator.

Fig. 13. Tiny-Yolo(v2) topology: percentage of CA utilization cycles for each layer and for the network.

Fig. 14. VGG-16 topology: percentage of CA utilization cycles for each layer and for the network.

Fig. 15. MobileNet topology: percentage of CA utilization cycles for each layer and for the network.

To obtain the most useful configurations from the design space, we applied DSE combined with Pareto front analysis to our design space. This is motivated by the huge design space that results from the combination of resource allocation, energy efficiency, and convolutional layer mapping parameters, which in our VGG-16 use case mapped to the Orlando architecture reaches 10 million configuration points, and for the Tiny-Yolo(v2) case, it reaches 5.3 million configuration points. In the cases of Pico-Yolo and MobileNet, the number of configurations are 6.7 and 5.6 million, respectively. After applying heuristic search and Pareto filtering techniques, the Pareto front in terms of normalized power consumption with respect to normalized execution time has been derived and represented in Figure 16 for our workloads. By using Pareto filtering, we reduced the number of design choices to 117 and 161 for Pico-Yolo and Tiny-Yolo(v2), respectively. Similarly, for MobileNet and VGG-16, the number of design choices after Pareto filtering are reduced to 160 and 140 design points, respectively. This corresponds to a reduction of five orders of magnitude in the number of design points. Each point in the Pareto front represents a good trade-off from the point of view of power/performance. Depending on the desired execution conditions such as ultra-low-power or high performance, a corresponding point from the Pareto front can be selected after this analysis, without being concerned with suboptimal solutions. Analyzing the Pareto front, we can observe that there are 193 unique combinations of mapping parameters (these unique runtime configurations are represented by different colors in Figure 16). This analysis confirms that to reach a target power/performance trade-off, the DSE must include mapping parameters as well.

Fig. 16. Power/performance Pareto fronts.