Recent years have witnessed the emergence of deep neural network (DNN) applications. Additionally, with the proliferation of Internet-of-Things (IoT) devices, they became inseparable from our daily lives. The conventional methods to process raw IoT data are to offload them to cloud services. However, moving such a tremendous amount of data incurs a high amount of monetary cost and delay, besides creating a major concern of privacy leakages. Therefore, serverless and edge computation paradigms are recognized as promising solutions. As a result, pushing the frontier of DNNs computations to the edge is receiving a tremendous amount of interest both from academia [1]- [9] and from the industry with commercial edge-tailored hardware accelerators such as NVIDIA Jetson Nano, edge TPU, and Intel Movidius.
Processing IoT data locally in the edge may suffer from poor performance and energy efficiency because the computational demand from DNNs outweighs the computation capacity and energy constraints of IoT devices. Furthermore, the computational demands are escalated because these devices have to meet real-time constraints. Even for edge-tailored This work was supported in part by the NSF grant number 2103951. § This work was done when the authors were affiliated with Georgia Tech. hardware accelerators, the real timeliness of applications is not guaranteed [10], [11]. Nevertheless, privacy concerns, unreliable connection to the cloud, tight real-time requirements, and personalization are still pushing inferencing to the edge. To address the resource constraint challenges, a solution is to distribute heavy computations among idle devices [1], [2], [4], [12] because the state-of-the-art IoT networks are formed with various IoT sensors and recording agents, such as HD cameras and temperature sensors, many of which are capable of performing computations. However, such a distribution is susceptible to failures, from short disconnectivity and user interaction to losing a device. This fact necessitates developing a robust method for tolerating these failures. Additionally, since IoT networks use wireless technology, unreliability and variability in their networks are much higher than acceptable limits to ensure a robust system.
We extend studies that enable distributed single-batch inference of DNNs in the edge [1], [2], [4], [12] to tolerate failures with close-to-zero recovery latency. We first analyze general methods of distributing the computations of DNNs and how their underlying general matrix-matrix multiplication (GEMM) is affected by distribution. Such a detailed study is necessary to introduce a general seamless method within the underlying library or machine learning framework. Then, we propose a new recovery method based on coded distributed computing (CDC) that enables distributed DNN models on IoT devices to tolerate failures. Our method is inspired by CDC applications in big data analytics [13], and speeding up distributed learning using codes [14].
To enable robustness in distributed IoT, we introduce an extra coded computation per device. We propose a novel fault recovery method based on CDC that has close-to-zero recovery latency, does not disturb the balanced work assignment in distribution, requires minimal changes to the program, and has a constant cost with the increasing number of devices. Our introduced extra computations are derived by thoroughly analyzing how general methods of distributing the computation of DNNs affect their underlying GEMM. The added computations are similar in nature to those of DNNs, which eases balancing the work among IoT devices and reduces the deployment cost. Balanced distribution is essential in attaining the expected performance. Additionally, since our method is implemented at the library level, it does not require changes to the program. Moreover, unlike approaches that sacrifice latency for robustness to recompute the missing part of the data, our method, even at the time of failures, provides close-to-zero recovery time, which is necessary for critical time-sensitive tasks. Finally, compared with conventional modular redundancy methods with redundant computation by introducing a linear number of additional devices, our method has a constant cost as the number of devices increases. We demonstrate our method on Raspberry Pis (RPis), which represents the de facto choice for several small and edge use cases.
To illustrate unreliability in the communication latency of IoT systems, Figure 1 shows a histogram of the arrival times for data packets in an IoT system of four RPis (system setup in Section IV). This system performs the computation for a fully-connected (FC) layer of size 2048 in a distributed fashion and waits for the response, the measured time for the computation on a single device is 50 ms. This is why, in Figure 1, no packet arrives earlier than 50 ms. As seen, around 34% of the arrival times is within 100 ms, and 42% is within 150 ms. Even after 2x the computation time, around 34% of the packets have not arrived yet. Such behavior in distributed systems causes straggler problem, in which the slowest node in the distributed system defines the total latency. Our method, by introducing robustness in such systems, can additionally alleviate the straggler problem while also guaranteeing closeto-zero recovery latency.
To understand how failures are destructive in DNN applications, we perform another set of experiments, in which some part of data within a layer is lost. We choose two models: LeNet-5 [15] and Inception v3 [16]. LeNet-5 is a simple model that detects handwritten digits from 10 classes and consists of only five layers. On the other hand, Inception v3 is a DNN model for image recognition for 1k classes with 159 layers. Figure 2 illustrates the accuracy drop in these models when some part of the data in a layer is lost. As seen, for large
Fig.
2: High percentage data loss, common in distributed IoT systems, causes destructive accuracy drops. ⎡ ⎢ ⎣ w11 w12 ... w1k w21 w22 ... w2k w31 w32 ... w3k . . . . . . . . . . . . wm1 wm2 ... wmk ⎤ ⎥ ⎦ m×k × ⎡ ⎢ ⎢ ⎣ a 1 a 2 a 3 . . . Inputs (divided among nodes) Weights (divided among nodes) Outputs (each node calculates partial sums) ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎢ ⎣ δa1 . . . δam ⎤ ⎥ ⎦ m×1 . . . ⎡ ⎢ ⎣ δa1 . . . δam ⎤ ⎥ ⎦ m×1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎣ w11 w12 ... w1k w21 w22 ... w2k w31 w32 ... w3k . . . . . . . . . . . . wm1 wm2 ... wmk ⎤ ⎥ ⎦ m×k × ⎡ ⎢ ⎢ ⎣ a 1 a 2 a 3 . . . a k ⎤ ⎥ ⎥ ⎦ k×1 = = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ a1 a2 a3 . . . percentages of data loss (> 70%) per layer that are common in distributed IoT systems, the accuracy drop is destructive. Additionally, by comparing Figures 2a and b, we see that the sensitivity to data loss in more generalized models will only become worse. Since the amount of data loss happens in larger granularities, the current robustness methods in DNNs (e.g., bitlevel tolerance) are insufficient to recover the loss. In contrast, our proposed robustness method is designed specifically for such a high amount of data loss and can recover from it with close-to-zero latency.
This section first describes how distribution methods change computation, which helps us apply our robustness method at the library level. Next, we provide a simple example of our method and then we generalize it.
Fully-Connected Layer: An FC layer l th performs a l = σ W l a l-1 + b l , in which W , a, and b are weight, activation, and bias. First, we consider the GEMM: W l a l-1 . Figure 3 illustrates how output splitting affects weight and output matrices for an example with four devices. Since each device calculates a set of separate outputs, the output matrix is created separately by each device (and concatenated later). Such separation in output generation also divides the weight matrix along the y-axis, which has a one-by-one relationship with the output matrix division. Each device needs a copy of the input matrix, and the input matrix is not divided. In the input-splitting method, as Figure 4 depicts for the same four-devices example, the input matrix is divided between the devices. Similarly, the weights corresponding to those inputs are divided along the x-axis among devices. Each device calculates partial sums for all output elements. Finally, all partial sums are aggregated to create the final output. We can extend the above reasoning to bias and activation. For output splitting, biases, and the activation function can also be divided among the devices. But, for input splitting, both need to be applied after the aggregation. Since the majority of the computation time of DNNs is spent on GEMMs, such a difference does not have a big impact on computation time.
Convolution Layer: The channel-splitting method divides the filter weight matrix along the y-axis, as Figure 5 shows for two devices. Likewise, since the output is unrolled, such division translates to a similar along-the-y-axis division of the output matrix. Hence, channel splitting in convolution layers is the same as output splitting into FC layers and any robustness analysis is applicable on both, but with a different set of weights and inputs (i.e., unrolled version of filters and patches in convolution layers). In the spatial-splitting method, since each input patch is unrolled column-wise in the input matrix when we spatially divide the input, this division translates to an along-the-x-axis division of the input matrix. However, unlike input splitting in FC layers, filter weights cannot be divided. Therefore, spatial splitting, as conceptually shown in Figure 6 for two devices, divides the input matrix
H , in which C and K are the number of channels and filters, and filter size is F xF xC. In the filter-splitting method, a close representation of input splitting for FC layers, both filter weights and input are divided depth-wise. Since both filter weights and input are unrolled, we need to divide the weight and input matrices along the x-and y-axes, respectively. This distribution is similar to the outer product approach in matrix multiplication, versus the most commonly known algorithm of the inner product approach. Figure 7 shows this approach with two devices. Each device produces a partial sum for all elements. To create the final output, the final device aggregates all the elements and applies the activation function.
We propose a simple example of our CDC-based robustness to facilitate understanding. Consider an FC layer with two input and output elements, written as:
Assume that we perform output splitting. We add a row to the weight matrix with the value of [w 11 + w 21 w 12 + w 22 ] to create the summation of two outputs, or a 1 + a 2 . With such an addition, the above equation becomes:
As the summation of the weights can be done offline and is not dependent on inputs, we can rewrite the above equation as:
Fig. 6: Distribution of spatial splitting for convolution layers. The newly added weights to the weight matrix are the column sums of the weight matrix that is done offline before loading the weights. Therefore, with the addition of another device, we can guarantee to recover from one missing output with only a local subtraction in the final device. This method has three main benefits: (i) First, this level of guarantee on all devices is just with the addition of one device, compared to a double modular redundancy method that duplicates all devices.
(ii) Second, this method is faster than redoing all operations since the subtraction of two local values that we already have received is almost more immediate than restarting all operations. This is because, the vanilla recovery method consists of loading a set of new weights (corresponding to the missing values) in the final device, asking for input from previous devices, and performing multiplications with all of its associated overhead of communication. (iii) Third, although we introduced the computations corresponding to a cdc , these computations are similar in nature to the computations of a 1 and a 2 . Hence, the distribution of these newly added computations follows the same rules and would not create an imbalance in the modified distribution.
This section extends our simple scenario, where each device computes only one output element, to a more realistic scenario, where each device computes hundreds of elements. Similarly, we showcase the output-splitting method as our example.
Assume an FC layer performing the below equation: ⎡ ⎣ w11 w12 ... w1k w21 w22 ... w2k . . . . . . . . . . . . wm1 wm2 ... wmk ⎤ ⎦ m×k × ⎡ ⎢ ⎣ a 1 a 2 . . .
in which input matrices are the same, but the weight matrix is divided along the y-axis. Each device creates separate parts of the output matrix. To introduce robustness, the new weight matrix would be as follows:
. (7) By multiplying this new weight matrix with inputs, the below output matrix is created:
. . .
which is is the summation of two output matrices in Equations 5 and 6. Therefore, by introducing such a weight matrix as Equation 7, we can introduce robustness. Similar to our simple example, the computation of new weights is done offline, recovery has a close-to-zero latency, the robustness covers all devices, and the new computation is balanced. In contrast, splitting methods that divide the input matrix among the devices do not yield similar benefits. To illustrate why, we study input splitting among two devices for the computation of the FC layer in Equation 4. Input splitting for FC layers divides the input and the weight matrix along the x-axis. Accordingly, the computations per device are from Equations 9 and 10. Each of these equations calculates a partial sum. However, as seen, no share factor exists between the two computations. Therefore, to perform coded distribution, a third device needs to perform the entire calculations of Equations 9 and 10, which creates unbalanced work between the devices and has no advantage over just replicating the entire work as modular redundancy methods do.
. . .
(10) Distribution Techniques Suitable for Robustness: Based on our discussion, among the distribution methods for DNNs, only some are suitable for our CDC-based robustness. Such suitable methods do not split the input elements but split the weights. Table I provides a summary of all the presented methods and whether they are suitable for robustness. For FC layers, the output-splitting method is suitable for robustness.
TABLE I: Distribution Techniques Suitable for Robustness. Layer Distribution Divides Divides Divides Suitable for Method Input Weight Output Robustness fc Output Yes Input No conv Channel Yes Spatial No Filter No
For convolution layers, the channel-splitting method has similar characteristics. Unfortunately, the rest of the distribution methods are not suitable for robustness because to introduce robustness, they need to perform the entire computation again, which causes communication overhead. For instance, in spatial splitting, although every device has all the weights, they only own some part of the input. Therefore, with our technique, we need another device to perform the computation based on the summation of the input parts. Since input elements change, computing such a summation has an overhead during the runtime (2x compute). The filter-splitting method also suffers from the fact that no element from the input or weights is shared between computing devices.
Experiments Setup: We evaluate our method on a distributed system with RPi with 1.
2 GHz Quad Core ARM Cortex-A53 CPU and a 900 MHz 1 GB RAM LPDDR2 memory. We choose RPi because they represent the de facto choice for several IoT systems, they are readily available, and they allow common software packages. Our implementation is created with a software stack based on Docker containers. We use Keras 2.1 with the TensorFlow backend (version 1.5). For RPC calls and serialization, we use Apache Avro. A local WiFi network with a measured bandwidth of 94.1 Mbps and a measured client-to-client latency of 0.3 ms for 64 B is used. Task Creation & Assignment: The policy of task creation in IoT-based distributed DNN systems is done with either profiling or heuristics that use common monitoring/managing tools such as Kubernetes. The policies create tasks per device for a given DNN by studying its memory footprint, computation requirement, and communication overhead.
Regardless of the policy that finds the optimal distribution (out of the scope of this paper, see [4]), all the pre-trained weights are loaded to each device storage so that a device can switch its assigned task easily if needed. For each number of available devices, a single task allocation file is loaded to all devices and each device performs its allocated tasks based on the file. We use an IP table file to assign tasks to each RPi. CDC weights are also created offline and loaded to the storage. In the case of a failure, the system uses another pre-defined distribution file with fewer devices that has a lower performance. In such a case, since the detection of a missing device takes time, the system mishandles many requests. Our proposed solution has tolerance to such failures, so the system never loses a request. Additionally, with a close-to-zero recovery latency, the system proactively is more tolerant to straggler nodes. Weight Storage: Each Pi has an SD card storage, for storing the weights, which is relatively inexpensive compared to the Arrival Time (ms) Fig. 9: Case study I: Recovery latency with & without CDC.
main memory. All trained weights are loaded to each Pi's storage (16 GB storage in our system), so each Pi can be assigned to execute any part of a layer. If local storage is limited, the assigned weight can also be shared on the network from a network-storage filesystem. This approach makes a tradeoff between how fast the switching time between different models can be and per-device storage usage. Additionally, note that the distribution method does not replace other methods, such as offloading to servers. The decision is on a per-case basis and depends on several system-level decisions. The distribution offers the additional option of processing data locally.
Case Study I: To depict the impact of how failures affect a system, we deploy AlexNet [17] on two IoT systems. The first system (Figure 8a) contains five devices. The first fullyconnected layer is split with the output-splitting between two devices with no robustness method. The black bars in Figure 9 show the latency of the system when performing single-batch inferences. If device C experiences failure, as shown in Figure 8b, other devices need to perform the task assigned to the failed device. Since device C computes half of the first fully-connected layer, device D needs to perform this extra task. After the failure is detected, which takes tens of seconds, the red bars in Figure 9 depict the new shifted latency histogram of the system. Based on our measurements, on average, the system experiences 2.4x slowdown after recovery. The system does not perform beneficial work during failure detection and experiences a significant slowdown afterward. However, with our method, the system does not experience any slowdown or service interruption. Case Study II: As a remedy to failures, we deploy AlexNet on a six-device system. Figure 10a shows this system, in which an extra device is added for robustness using CDC. Note that our goal is to create robustness only for the first Arrival Time (ms) Fig. 11: AlexNet latency histogram without straggler mitigation. Time (ms) Fig. 12: AlexNet latency histogram with straggler mitigation.
fully-connected layer and the extra device provides robustness to all the computations done on devices D and E. If we experience failure (Figure 10b), the performance of the system does not change. Additionally, during the operation without failure, we use the extra device to mitigate the straggler problem. Figures 11 and 12 show the system latency with and without this mitigation, respectively. As shown, the range and the distribution of latencies are improved towards a better performance. Thus, in addition to robustness, we can exploit the extra device to increase the performance.
We study straggler mitigation benefits by extending the previous system. To initiate recovery, a device waits for a particular amount of time. By adjusting this waiting threshold in a device, we can treat our method as a solution for the straggler problem after receiving the necessary amount of data. A lower threshold reduces latency and thus increases performance. The straggler problem is more prominent with more devices, so we set up an experiment for a system with four devices, each of which performs a split in a fully-connected layer (Figure 13a). Figure 13b shows performance improvement of straggler mitigation with a diffident number of devices. The performance improvement is compared with the same system, with the same number of devices, and with no straggler mitigation. As seen, for more devices, straggler mitigation has better performance (up to 35%) compared with a no-stragglermitigation system with the same number of devices.
In the system in Figure 10, devices with model parallelism are robust with CDC. For other devices, by replicating the device's task (N-modular redundancy with N = 2, or 2MR), we can tolerate one failure. A hybrid approach (CDC+2MR) can cover the system for failures. Our method covers any number of devices in one layer with just one additional device (for
[ × [ Output Splitting for 4 nodes One Failure Tolerance robustness to one failure). However, 2MR requires an additional device for each device, resulting in a linear number of additional devices. Our method has a constant cost with an additional number of devices, whereas 2MR requires a linear number of additional devices. Figure 14 examines several DNNs [18]- [20] with distributed implementations, showcasing tolerance to one failure with 2MR-only and CDC+2MR. Since CDC requires fewer devices than 2MR to cover devices with model parallelism, the number of additional devices for full coverage in CDC+2MR is smaller than that of 2MR. The amount of difference depends on the number of layers distributed with model parallelism and the number of devices used per layer. For example, Figure 14c and d depict two C3D distributions with different numbers of devices for the layers utilizing model parallelism (two vs. three devices). In Figures 14c and d, with two additional devices, CDC+2MR achieves coverage of 67% and 73% compared to 2MR's coverage of 44% and 36%. This is because C3D distribution has two layers with model parallelism. Therefore, CDC+2MR achieves better coverage compared to 2MR. To summarize, by utilizing model parallelism for a layer with N devices, our method allows hiding a single node's failure at a cost of (1+foot_1 N ) times the hardware cost, as opposed to 2MR's cost of 2x hardware.
The Introduced Computation: The introduced new computations for our CDC-based method are similar to that of underlying GEMM computations. This is because the newly added weights are added to the weight matrix and can be calculated without the user's input at the library level. Therefore, there are no additional costs for reprogramming the applications. Moreover, since the nature of the computations for these new weights is similar to that of DNNs, there is no need to design new kernels or distribution methods. Extending Robustness to More Failures: Our discussions focused on tolerating up to one failure. However, Extending to more than one failure is possible by adding new devices that compute based on the summation of some rows of weights instead of all. Figure 15 illustrates three setups in order of increasing tolerance to failures. The last setup tolerates two failures because new devices perform partial sums on the weights. 1 Thus, by utilizing idle devices with an overlapping set of weights, the system's robustness increases. [13] introduces coding for MapReduce-type workloads for large-scale computing. By coding, which increases the computation of mapping functions, communication can be reduced in the reduction phase. The authors of the CDC theoretically study the limits and trade-offs of such distribution and illustrate an inverse relationship between the amount of computation and communication. Usually, coding in CDC is applied over bit-level representation of numbers. Instead of coding over floats/bits, we apply coding to the application level by introducing new weights. Furthermore, in contrast, to reduce communication overhead in other studies, our goal is to increase robustness and tolerate unstable latencies. CDC helps mitigate the straggler problem in computing clusters [21], [22], besides other methods such as straggler detection algorithms [23], [24] and replication-based approaches [25], [26].
Several studies also utilize CDC to mitigate the straggler problem in distributed storage systems [27]. Distributed learning algorithms have also used CDC opportunities [14]. Since these algorithms use data parallelism for learning, facilitates the mapping phase in learning algorithms with data shuffling. Particularly, Lee et al. [14] focused on two basic blocks of learning algorithms, matrix multiplication, and data shuffling. None of the above works has studied CDC in the context of robustness. In contrast with our work, distributed learning studies [14] examine large-scale learning algorithms, which employ data parallelism, whereas our work focuses on IoTbased inferencing, which utilizes model parallelism.
We proposed a method to introduce tolerance for the single-batch inferencing of DNNs, a key operation in IoT. Our method exploits model-parallelism methods in prevalent DNN layers to add balanced computation for robustness. Model parallelism helps us achieve efficient system distribution. We extended CDC to provide a trade-off between computations and robustness on distributed IoT.
Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on August 01,2025 at 16:58:59 UTC from IEEE Xplore. Restrictions apply.
Note that the coverage to two failures is almost complete (partial error correction). We need Hamming-style coverage for full error correction.