Coded Fourier Transform

I Introduction

Discrete Fourier transform (DFT) is one of the fundamental operations, which has been broadly used in many applications, including signal processing, data analysis, and machine learning algorithms. Due to the increasing size and dimension of data, many modern applications require massive amount of computation and storage, which can not be provided by a single machine. Thus, finding efficient design of algorithms including DFT in a distributed computing environment has gained considerable attention. For example, several distributed DFT implementations, such as FFTW and PFFT , have been introduced and used widely.

A major performance bottleneck in distributed computing problems is the latency caused by “stragglers" , which are the small fraction of computing nodes at the high latency tail that prolongs the computation. Mitigating this effect involves creating certain types of “computation reduncancy”, such that the computation can be completed even without collecting the intermediate results assigned to the stragglers. For example, one can replicate the same computing task onto multiple nodes to provide this redundancy .

Recently, it has been shown that coding theoretic concepts that were originally developed for communication systems can also be useful in distributed computing systems, playing a transformational role by improving the performance of computation in various aspects. In this context, two “coded computing” concepts has been proposed: The first one, introduced in , injects computation redundancy in order to alleviate the communication bottleneck and accelerate distributed computing algorithms (e.g., Coded Terasort ). The second coded computing concept, introduced in , utilizes coding to handle the straggler effects and speed up the computations for distributed matrix multiplication. This technique has been further extended to decentralized “master-less” architectures , distributed convolution , short dot linear transform and gradient computation .

More recently, polynomial code has been proposed for distributed massive matrix multiplication, for optimal straggler effect mitigation. It was shown that by designing a pair of codes, whose multiplicative product forms an Maximum Distance Separable (MDS) code, one can orderwise improve upon the prior arts in terms of the recovery threshold (i.e., the number of workers that the master needs to wait in order to be able to compute the final output), while optimizing other metrics including computation latency and communication load. This provides the first code that achieves the optimum recovery threshold. Furthermore, it allows mapping the reconstruction problem of the final output to polynomial interpolation, which can be solved efficiently, bridging the rich literature of algebraic coding and distributed matrix multiplication. Moreover, a variation of the polynomial code was applied to coded convolution, and its order-optimality has been proved.

Our main result in this paper is the development of an optimal computing strategy, referred to as the coded FFT. This computing design achieves the optimum recovery threshold $m$, while allowing the the master to decode the final output with low complexity. Furthermore, we extend this technique to settings including computing multi-dimensional Fourier transform, and propose the corresponding optimal computation strategies.

To develop coded FFT, we leverage two key algebraic properties of the Fourier transform operations. First due to its recursive structures, we can decompose the DFT into multiple identical and simpler operations (i.e., DFT over shorter vectors), which suits the distributed computing framework and can be potentially assigned to multiple worker nodes. Secondly, due to the linearity of Fourier transform, we can apply linear codes on the input data, which commutes with the DFT operation and translates to the computing results. These two properties allow us to develop a coded computing strategy where the outputs from the worker nodes has certain MDS properties, which can optimally mitigate straggler effects.

II System Model and Main Results

Given the above system model, we can design the functions to compute $\boldsymbol{a}_{i}$s’ and $\boldsymbol{b}_{i}$s’ for the workers. We refer to these functions as the encoding functions and the computing functions. We say that a computation strategy consists of $N$ encoding functions and $N$ computing functions, denoted by

that are used to compute the $\boldsymbol{a}_{i}$s’ and $\boldsymbol{b}_{i}$s’. Specifically, given a computation strategy, each worker $i$ stores $\boldsymbol{a}_{i}$ and computes $\boldsymbol{b}_{i}$ according to the following equations:

For any integer $k$, we say a computation strategy is $k$-recoverable if the master can recover $X$ given the computing results from any $k$ workers using certain decoding functions. We define the recovery threshold of a computation strategy as the minimum integer $k$ such that the computation strategy is $k$-recoverable.

The goal of this paper is to find the optimal computation strategy that achieves the minimum possible recovery threshold, while allowing efficient decoding at the master node. This essentially provides the computation strategy with the maximum robustness against the straggler effect, which only requires a low additional computation overhead.

We summarize our main results in the following theorems:

In a distributed Fourier transform problem of computing $\boldsymbol{X}=\mathcal{F}\{\boldsymbol{x}\}$ using $N$ workers that each can store and process $\frac{1}{m}$ fraction of the input $\boldsymbol{x}$, we can achieve the following recovery threshold

Furthermore, the above recovery threshold can be achieved by a computation strategy, referred to as the Coded FFT, which allows efficient decoding at the master node, i.e., with a complexity that scales linearly with respect to the size $s$ of the input data.

Moreover, we can prove the optimally of coded FFT, which is formally stated in the following theorem

In a distributed Fourier transform environment with $N$ workers that each can store and process $\frac{1}{m}$ fraction of the input vector, the following recovery threshold

The above converse demonstrates that our proposed coded FFT design is optimal in terms of recovery threshold. Moreover, we can prove that coded FFT is also optimal in terms of the communication load (see Section IV).

While in the above results we focused on the developing the optimal coding technique for the one dimensional Fourier transform. The techniques developed in this paper can be easily generalized to the $n$-dimensional Fourier transform operations. Specifically, we can show that in a general $n$-dimensional Fourier transform setting, the optimum recovery threshold $K^{*}=m$ can still be achieved, using a generalized version of the coded FFT strategy (see Section V). Similarly, this also generalized to the scenario where we aim to compute the Fourier transform of multiple input vectors. The optimum recovery threshold $K^{*}=m$ can also be achieved (see Section VI).

Although the coded FFT strategy was designed focusing on optimally handling the stragglers issues, it can also be applied to the fault tolerance computing setting (e.g., as considered in , where a module can produce arbitrary error results under failure), to improve robustness to failures in computing. Specifically, given that the coded FFT produces computing results that are coded by an MDS code, it also enables detecting, or correcting maximum amounts errors even when the erroneous workers can produce arbitrary computing results.

III Coded FFT: the Optimal Computation Strategy

In this section, we prove Theorem 1 by proposing an optimal computation strategy, referred to as Coded FFT. We start by demonstrate this computation strategy and the corresponding decoding procedures through a motivating example.

We aim to design a computation strategy to achieve a recovery threshold of $2$.

In order to design the optimal strategy, we exploit two key properties of the DFT operation. Firstly, DFT has the following recursive structure:

where vectors $\boldsymbol{c}_{0}$ and $\boldsymbol{c}_{1}$ are the interleaved version of the input vector:

This structure decomposes the Fourier transform into two identical and simpler operations: the Fourier transform of $\boldsymbol{c}_{0}$ and $\boldsymbol{c}_{1}$, defined as follows.

Hence, computing the Fourier transform of a vector is essentially computing the Fourier transforms of its sub-components. This property has been exploited in the context of single machine algorithms and led to the famous Cooley-Tukey algorithm .

On the other hand, we exploit the linearity of the DFT operation to inject linear codes in the computation to provide robustness against stragglers. Specifically, given that the Fourier transform of any linearly coded vector equals the linear combination of the Fourier transforms of the individual vectors, by injecting MDS code on the interleaved vectors $\boldsymbol{c}_{0}$ and $\boldsymbol{c}_{1}$ and computing their Fourier transforms, we obtain a coded version of the vectors $\boldsymbol{C}_{0}$ and $\boldsymbol{C}_{1}$. This provides the redundancy to mitigate the straggler effects.

Specifically, we encode $\boldsymbol{c}_{0}$ and $\boldsymbol{c}_{1}$ using a $(3,2)$-MDS code, and let each worker store one of the coded vectors. I.e.,

Each worker computes the Fourier transform $\boldsymbol{b}_{i}=\mathcal{F}{\{\boldsymbol{a}_{i}\}}$ of its assigned vector. Specifically, each worker $i$ computes

To prove that this computation strategy gives a recovery threshold of $2$, we need to design a valid decoding function for any subset of $2$ workers. We demonstrate this decodability through a representative scenario, where the master receives the computation results from worker $1$ and worker $2$ as shown in Figure 2. The decodability for the other $2$ possible scenarios can be proved similarly.

According to the designed computation strategy, the server can first recover the computing result of worker given the results from the other workers as follows:

After recovering $\boldsymbol{b}_{0}$, we can verify that the server can then recover the final output $\boldsymbol{X}$ using $\boldsymbol{b}_{0}$ and $\boldsymbol{b}_{1}$ as follows:

III-B General Description of Coded FFT

Now we present an optimal computing strategy that achieves the optimum recovery threshold stated in Theorem 1, for any parameter values of $N$ and $m$. First of all we interleave the input vector $\boldsymbol{x}$ into $m$ vectors of length $\frac{s}{m}$, denoted by $\boldsymbol{c}_{0},...,\boldsymbol{c}_{m-1}$. Specifically, we let the $j$th element of each $\boldsymbol{c}_{i}$ equal

Note that if the master node can recover all the above Fourier transform $\boldsymbol{C}_{i}$ of the interleaved vectors, the final output can be computed based on the following identities:

where $\bmod(i,\frac{s}{m})$ denotes the remainder of $i$ divided by $\frac{s}{m}$.

Based on this observation, we can naturally view the distributed Fourier transform problem as a problem of distributedly computing a list of linear transformations, i.e., computing the Fourier transform of $\boldsymbol{c}_{i}$’s. We inject the redundancy as follows to provide robustness to the computation:

We first encode the $\boldsymbol{c}_{0},\boldsymbol{c}_{1},...,\boldsymbol{c}_{m-1}$ using an arbitrary $(N,m)$-MDS code, where the coded vectors are denoted $\boldsymbol{a}_{0},...,\boldsymbol{a}_{N-1}$ and are assigned to the workers correspondingly. Then each worker $i$ computes the Fourier of $\boldsymbol{a}_{i}$, and return it to the master. Given the linearity of Fourier transform, the computing results $\boldsymbol{b}_{0},...,\boldsymbol{b}_{N-1}$ are essentially linear combinations of the Fourier transform $\boldsymbol{C}_{i}$’s, which are coded by the same MDS code. Hence, after the master receives any $m$ computing results, it can decode the message $\boldsymbol{C}_{i}$’s, and proceed to recover the final result. This allows achieving the recovery threshold of $m$.

The recovery threshold $K^{*}=m$ achieved by coded FFT can not be achieved using computation strategies that were developed for generic matrix-by-vector multiplication in the literature . Specifically, the conventional uncoded repetition strategy requires a recovery threshold of $N-\frac{N}{m^{2}}+1$, and the short-dot (or short-MDS) strategy provided in requires $N-\frac{N}{m}+m$. Hence, by developing a coding strategy for the specific purpose of computing Fourier transform, we can achieve order-wise improvement in the recovery threshold.

III-C Decoding Complexity of Coded FFT

Now we show that coded FFT allows an efficient decoding algorithm at the master for recovering the output. After receiving the computing results, the master needs to recover the output in two steps: decoding the MDS code and then computing $\boldsymbol{X}$ from the intermediate value $\boldsymbol{C}_{i}$’s.

For the first step, the master needs of decode an $(N,m)$-MDS code by $\frac{s}{m}$ times. This can be computed efficiently, by selecting an MDS code with low decoding complexity for the coded FFT design. There has been various works on finding efficiently decodable MDS codes (e.g.,). In general, an upper bound on the decoding complexity of $(N,m)$-MDS code is given by $O(m\log^{2}m\log\log m)$, which can be attained by the Reed-Solomon codes and using fast polynomial interpolation as the decoding algorithm. Consequently, the first step of the decoding algorithm has a complexity of at most $O(s\log^{2}m\log\log m)$, which scales linearly with respect to $s$.

For the second step, the master node needs to evaluate equation (23) to recover the final result. Equivalently, the master needs to compute

To conclude, our proposed coded FFT strategy allows efficient decoding with a complexity of at most $O(s\log^{2}m\log\log m)$, which is linear to the input size $s$. The decoding computation is bottlenecked by the first step of the algorithm, which is essentially decoding an $(N,m)$-MDS code by $\frac{s}{m}$ times. To achieve the best performance, one can pick any MDS code with a decoding algorithm that requires the minimum amount of computation based on the problem scenatio .

IV Optimality of coded FFT

In this section, we prove Theorem 2 through a matching information theoretic converse. Specifically, we need to prove that for any computation strategy, the master needs to wait for at least $m$ workers in order to recover the final output.

V n𝑛n-dimensional Coded FFT

Fourier transform in higher dimensional spaces is a frequently used operation in image processing and machine learning applications. In this section, we consider the problem of designing optimal codes for this operation. We show that the coded FFT strategy can be naturally extended to this scenario, and achieves the optimum performances. We start by formulating the system model and state the main results.

We consider a problem of computing an $n$-dimensional Discrete Fourier transform $T=\mathcal{F}\{t\}$ in a distributed computing environment with a master node and $N$ worker nodes. The input $t$ and the output $T$ are tensors of order $n$, with dimension $s_{0}\times s_{1}\times...\times s_{n-1}$. For brevity, we denote the total number of elements in each tensor by $s$, i.e., $s\triangleq s_{0}s_{1}...s_{n-1}$.

Similar to the one dimensional Fourier transform problem, we design the functions to compute $\boldsymbol{a}_{i}$s’ and $\boldsymbol{b}_{i}$s’ for the workers, and refer to them as the computation strategy. We aim to find an optimal computation strategy that achieves the minimum possible recovery threshold, while allowing efficient decoding at the master node.

Our main results are summarized in the following theorems:

In an $n$-dimensional distributed Fourier transform problem of computing $T=\mathcal{F}\{\boldsymbol{t}\}$ using $N$ workers that each can store and process $\frac{1}{m}$ fraction of the input $t$, we can achieve the following recovery threshold

Furthermore, the above recovery threshold can be achieved by a computation strategy, referred to as the $n$-dimentional Coded FFT, which allows efficient decoding at the master node, i.e., with a complexity that scales linearly with respect to the size $s$ of the input data.

Moreover, we can prove the optimally of $n$-dimensional coded FFT, which is formally stated in the following theorem.

is optimal.Similar to the $1$-dimensional case, this optimally can be generalized to base fields with infinite cardinally, by taking into account of some practical implementation constrains.

V-B General Description of n𝑛n-dimensional Coded FFT

We first prove Theorem 3 by proposing an optimal computation strategy, referred to as $n$-dimensional Coded FFT, that achieves the recovery threshold $K^{*}=m$ for any parameter values of $N$ and $m$.

We denote the discrete Fourier transform of each interleaved tensor $c_{i_{0}i_{1}...i_{n-1}}$ by $C_{i_{0}i_{1}...i_{n-1}}$. Specifically,

Note that if the master node can recover all the above Fourier transform $C_{i_{0}i_{1}...i_{n-1}}$ of the interleaved tensors, the final output can be computed based on the following identity:

Specifically, we encode the $c_{i_{0}i_{1}...i_{n-1}}$’s using an arbitrary $(N,m)$-MDS code, where the coded tensors are denoted $\boldsymbol{a}_{0},...,\boldsymbol{a}_{N-1}$ and are assigned to the workers correspondingly. Then each worker $i$ computes the Fourier of tensor $\boldsymbol{a}_{i}$, and return it to the master. Given the linearity of Fourier transform, the computing results $\boldsymbol{b}_{0},...,\boldsymbol{b}_{N-1}$ are essentially linear combinations of the Fourier transform $C_{i_{0}i_{1}...i_{n-1}}$’s, which are coded by the same MDS code. Hence, after the master receives any $m$ computing results, it can decode the message $C_{i_{0}i_{1}...i_{n-1}}$’s, and proceed to recover the final result. This allows achieving the recovery threshold of $m$.

In terms of the decoding complexity, $n$-dimensional coded FFT also requires first decoding an MDS code, and then recovering the final result by computing Fourier transforms of tensors with lower dimension. Similar to the one dimensional FFT, the bottleneck of the decoding algorithm is also the first step, which requires decoding an $(N,m)$-MDS code by $\frac{s}{m}$ times. This decoding complexity is upper bounded by $O(s\log^{2}m\log\log m)$, which is linear with respect to the input size $s$. It can be further improved in practice by using any MDS code or MDS decoding algorithms with better computational performances.

V-C Optimally of n𝑛n-dimensional Coded FFT

Moreover, the above converse can also be extended to prove that the $n$-dimensional Coded FFT is optimal in terms of communication.

VI Coded FFT with multiple inputs

Coded FFT can also be extended to optimally handle computation tasks with multiple inputs entries. In this section, we consider the problem of designing optimal codes for such scenario.

For this problem, we can find an optimal computation strategy that achieves the minimum possible recovery threshold, while allowing efficient decoding at the master node. We summarize this result in the following theorems:

For an $n$-dimensional distributed Fourier transform problem using $N$ workers, if each worker can store and process $\frac{1}{m}$ fraction of the $q$ inputs, we can achieve the following recovery threshold

Furthermore, the above recovery threshold can be achieved by a computation strategy, which allows efficient decoding at the master node, i.e., with a complexity that scales linearly with respect to the size $s$ of the input data.

Moreover, we prove the optimally of our proposed computation strategy, which is formally stated in the following theorem.

In an $n$-dimensional distributed Fourier transform environment with $N$ workers that each can store and process $\frac{1}{m}$ fraction of the input vector, the following recovery threshold

VI-B General Description of Coded FFT with Multiple Inputs

As explained in Section V-B, if the master node can obtain the Fourier transforms of all the interleaved tensors, then the final outputs can be computed efficiently. Hence, we can view this distributed Fourier transform problem as a problem of computing a list of linear transformations, and we inject the redundancy using MDS code similar to the single input coded FFT strategy.

Given the linearity of Fourier transform, the computing results $\boldsymbol{b}_{0},...,\boldsymbol{b}_{N-1}$ are essentially linear combinations of the Fourier transforms of the interleaved tensors, which are coded by the same MDS code. Hence, after the master receives any $m$ computing results, it can decode all the needed intermediate values, and proceed to recover the final result. This allows achieving the recovery threshold of $m$.

In terms of the decoding complexity, one can show that the bottleneck of the decoding algorithm is the decoding of the $(N,m)$-MDS code by $\frac{s}{m}$ times, using similar arguments mentioned in Section V. This decoding complexity is upper bounded by $O(s\log^{2}m\log\log m)$, which is linear with respect to the input size $s$. It can be further improved in practice by using any MDS code or MDS decoding algorithms with better computational performances.

VI-C Optimally of Coded FFT with multiple inputs

Moreover, the above converse also applies for proving the optimally of Coded FFT in terms of communication.

VII Conclusions

We considered the problem of computing the Fourier transform of high-dimensional vectors, distributedly over a cluster of machines. We propose a computation strategy, named as coded FFT, which achieves the optimal recovery threshold, defined as the minimum number of workers that the master node needs to wait for in order to compute the output. We also extended coded FFT to settings including computing general $n$-dimensional Fourier transforms, and provided the optimal computing strategy for those settings. There are several interesting future directions, including the practical demonstration of coded FFT over distributed clusters, generalization of coded FFT to more general master-less architectures, and extension of coded FFT to other computing architectures (e.g., edge and fog computing architectures ).

VIII Acknowledgement

This work is in part supported by NSF grant CIF 1703575, ONR award N000141612189, and a research gift from Intel. This material is based upon work supported by Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001117C0053. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.

References