Abstract:
The present disclosure provides A data access method and device for parallel FFT computation. In the method, FFT data and twiddle factors are stored in multi-granularity parallel memories, and divided into groups throughout the computation flow according to a uniform butterfly representation. Each group of data involves multiple butterflies that support parallel computation. Meanwhile, according to the butterfly representation, it is convenient to generate data address and twiddle factor coefficient address for each group. With different R/W granularities, it is possible to read/write data and corresponding twiddle factors in parallel from the multi-granularity memories. The method and device further provide data access devices for parallel FFT computation. In the method and device, no conflict will occur during read/write operations of memories, and no extract step is required for sorting the read/written data. Further, the method and device can flexibly define the parallel granularity according to particular applications.

Description:
TECHNICAL FIELD 
       [0001]    The present application relates to data access technology, and in particular to data access methods and devices for parallel FFT computation. 
       BACKGROUND 
       [0002]    Signal processing systems are typically required to convert signals between time and frequency domains. The Fast Fourier Transform (FFT) algorithm enables such signal conversion between time and frequency domains. Compared with other transform algorithms, FFT has advantages of uniform structure and less computation, and thus has been widely used in signal processing systems. 
         [0003]    FFT takes N points of data as input and outputs N pieces of data. In general, a transform from time to frequency domain is called forward transform, while a transform from frequency to time domain is called inverse transform. There are many approaches for implementing FFT, and they are all evolved from the Cooley-Tukey algorithm. The radix-2 Cooley-Tukey algorithm has log 2 N computation stages for N data points. Each computation stage takes N data points and outputs N data points. The output from the previous stage is sorted in certain manner and used as input to the next stage. The input to the first stage is original data, and the output from the last stage is the result of FFT computation.  FIG. 1  shows a computation flow including three computation stages  103  (S 0 , S 1 , S 2 ) by assuming that the length of the data points is 8. 
         [0004]    Each computation stage  103  is formed by N/2 butterflies  102 , of which the computation flow is shown in  FIG. 2 . Each butterfly  102  takes two data points A and B and a twiddle factor W as input, and obtains two results A+BW and A−BW after butterfly computation. In the computation of each butterfly, the indices of the input data A and B has a correspondence which is determined by the computation stage of the butterfly, and the indices of the input data A or B. Meanwhile, the value of the twiddle factor W is determined by the computation stage  103  of the butterfly, and the indices of the input data A or B, and the data length of FFT. In the computation stage S 0  of  FIG. 1 , the first data and the zeroth data form a butterfly, the zeroth data is the input A to the butterfly, and the first data is the input B to the butterfly. The value of W is 1. In the computation stage S 1 , the first data and the third data form a butterfly, the first data is the input A of the butterfly, the third data is the input B of the butterfly, and the value of W is 1. 
         [0005]    The computation stages are data-dependent, and the next stage can only start its computation until the computation of the previous stage is completed. Accordingly, after completing the computation, each stage stores the results in a memory, and the next stage reads from the memory the computation results of the previous stage as input. The butterflies in a computation stage are independent of each other, and the order of the butterflies computation does not affect the results. However, the data A, B and the twiddle factor W read out by each butterfly must satisfy certain internal correspondence. 
         [0006]    In parallel FFT computation, a computation module reads data and respective twiddle factors for multiple butterflies from a multi-granularity parallel memory, performs a plurality of multi-stage butterfly computations in parallel, and then writes computation results in parallel into the memory for use in the next stage, as shown in  FIG. 4 . Here, assuming that the data length is 64, and parallel granularity is 4, that is, the multi-granularity parallel memory  400  support reading/writing 4 points of data each time. Meanwhile, 4 data-dependent butterflies  403  in two adjacent stages form a butterfly group  402 , and the butterfly groups in the two adjacent stages form a computation node  401 . The butterfly computation module  301  reads data points and twiddle factors required for one butterfly group in parallel from the memory  300  or  302 , and the memory  303 , respectively, and writes computation results in parallel into the memory  300  or  302  after completing the computation of the butterfly group, as shown in  FIG. 3 . 
         [0007]    In the butterfly group  402 , the input A, B and W to each butterfly must satisfy the internal correspondence. Therefore, in the parallel FFT computation, consideration must be made as to the distribution of data and twiddle factors in the memory, and read/write (R/W) addresses and R/W schemes for each butterfly group  402 , in order to guarantee that the butterfly computation module can always read desired data and twiddle factors in parallel. 
         [0008]    Most of patent documents related to parallel FFT computation, such as U.S. Pat. No. 6,792,441B2 (“Parallel MultiProcessing For Fast Fourier Transform With Pipeline Architecture”), focus on how to decompose a long sequence of FFT data into a plurality of short sequences of FFT data, use a plurality of processors to compute the respective short sequences of FFT data in parallel, and then interleave the short sequences of FFT results to obtain a final long sequence of FFT result. Such algorithms do not consider possible conflict when the plurality of processors access the memory at the same time, or how the processors interleave the short sequences of FFT results. In practical applications, the conflict in memory access and synchronization and communication efficiency among the processors will greatly affect FFT computation efficiency. The U.S. Pat. No. 6,304,887B1 (“FFT-Based Parallel System For Array Processing With Low Latency”) discusses parallel read/write of data in FFT. According to the patent document, the FFT data are stored in a plurality of memories, and sorted by using multiple data buffers and multiple selectors, in order to guarantee that for each R/W operation, data are distributed in a different memory. In this way, it is possible to achieve parallel read/write of data. In the patent document, dedicated memories, data buffers and selectors are required, and calculation of R/W addresses is complex. Thus, it is difficult to implement parallel FFT computation with different data lengths and R/W granularities. 
       SUMMARY 
       [0009]    In view of the above problems, the present disclosure provides data access methods and devices for parallel FFT computation. 
         [0010]    The present disclosure provides a data access method for parallel FFT computation comprising: 
         [0011]    step 1, dividing initial FFT data of a length N into 2 G  groups by a parallel granularity 2 B , where G=log 2 N-B, and storing the 2 G  groups in respective memory rows  805  of 2 B  memory blocks  804  in a multi-granularity parallel memory  300  or  302 , where each of the memory blocks  804  comprises 2 G-B  groups, and occupies 2 G-B  memory rows  805 ; 
         [0012]    step 2, storing sequentially 2 B −1 twiddle factors required for computation of each butterfly group  402  in memory rows of a multi-granularity parallel memory  303 ; 
         [0013]    step  3 , reading data required for FFT butterfly computation stored in the jth memory row  805  of the ith memory block  804  in the multi-granularity parallel memory  300  or  302  with a read granularity of 2 B , where i and j each have an initial value of 0, and reading sequentially, from the multi-granularity parallel memory  303 , the twiddle factors required for FFT butterfly computation with a granularity of 2 B  in the order of the memory rows; 
         [0014]    step 4, performing parallel butterfly computation on the data read from the jth memory row  805  with a granularity of 2 B  based on the read twiddle factors; step  5 , writing the result data of butterfly computation to the multi-granularity parallel memory  300  or  302  with a granularity of 1, where when the data was read from the memory  300  at step 3, the result data is written to the memory  302  in step  5 , and vice versa; 
         [0015]    step  6 , determining whether an index j of the current memory row satisfies j&lt;2 G-B  and incrementing j by 1 and returning to step  3  if it satisfies, otherwise setting j to 0 and proceeding to step  7 ; 
         [0016]    step  7 , determining whether an index i of the current memory block satisfies i&lt;2 B , and incrementing i by 1 and returning to step  3  if it satisfies, otherwise terminating the method. 
         [0017]    Another aspect of the present disclosure provides a data access device for parallel FFT computation comprising multi-granularity parallel memories  300  and  302 , a multi-granularity parallel memory  303 , and a butterfly computation module  301 , wherein 
         [0018]    The multi-granularity parallel ,memories  300  and  302  is arranged as a ping-pang configuration to alternately store input data or output data of a computation stage  401 ; 
         [0019]    The multi-granularity parallel memory  303  is configured to store twiddle factors for the computation stage  401 ; 
         [0020]    The butterfly computation module  301  is configured to perform butterfly computation on to-be-processed data alternately acquired from the multi-granularity parallel memories  300  and  302  based on the twiddle factors stored in the multi-granularity parallel memory  303 , and alternately store the computation results in the multi-granularity parallel memories  300  and  302 ; 
         [0021]    Connection lines between the multi-granularity parallel memory  300  and the butterfly computation module  301  comprise data lines  306 , an address line  310 , and an access granularity indication line  309 ; 
         [0022]    Connection lines between the multi-granularity parallel memory  302  and the butterfly computation module  301  comprise data lines  305 , an address line  312 , and an access granularity indication line  311 ; 
         [0023]    Connection lines between the multi-granularity parallel memory  303  and the butterfly computation module  301  comprise data lines  304 , an address line  308 , and an access granularity indication line  307 ; 
         [0024]    Wherein if the data for butterfly computation are read from the multi-granularity parallel memory  300 , the result data of the computation are written to the multi-granularity parallel memory  302 , and vice versa. 
         [0025]    According to the present disclosure. FFT data and twiddle factors are stored in multi-granularity parallel memories, and divided into groups throughout the computation flow according to a uniform butterfly representation. Each group of data involves multiple butterflies that support parallel computation. Meanwhile, according to the butterfly representation, it is convenient to generate data address and twiddle factor coefficient address for each group. With different RAN granularities, it is possible to read/write data and corresponding twiddle factors in parallel from the multi-granularity memories. No conflict will occur during read/write operations of memories, and no extract step is required for sorting the read/written data. Further, the present disclosure can flexibly define the parallel granularity according to particular applications. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0026]      FIG. 1  is a flowchart of a radix2 FFT algorithm with temporal decimation when the data length is 8. 
           [0027]      FIG. 2  is a schematic diagram of a butterfly. 
           [0028]      FIG. 3  is a block diagram of a data access device for parallel FFT computation according to the present disclosure. 
           [0029]      FIG. 4  is a schematic diagram showing a butterfly, a butterfly group, a computation stage and a computation node according to the present disclosure. 
           [0030]      FIG. 5  is a schematic diagram showing composition of a butterfly representation. 
           [0031]      FIG. 6  is a schematic diagram showing butterfly representations of respective computation nodes and stages with a parallel granularity of 4 and a data length of 64. 
           [0032]      FIG. 7  is a schematic diagram showing how twiddle factors for a butterfly group are stored in memory rows when the parallel granularity is 8. 
           [0033]      FIG. 8  is a schematic diagram showing a distribution of 64 FFT data points in memories and the read/write scheme of a computation node according to the present disclosure. 
           [0034]      FIG. 9  is a flowchart of a data access method of a computation node in parallel FFT computation. 
       
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
       [0035]    In the following, the present disclosure will be further explained with reference to the figures and specific embodiments so that the objects, solutions and advantages of the present disclosure become more apparent. 
         [0036]    In the description, symbols are defined as follows:
       N: data length for FFT; it must be a power of 2;   B: bit width of parallel granularity, i.e., 2 B  denotes parallel granularity;   G: bit width of index value of a butterfly group, G=log 2 N-B;   g: index value of a butterfly group;   b: an intra-group index value of the data.       
 
         [0042]    To achieve parallel FFT read/write and computation, a parallel granularity 2 B  (B is a positive integer) is initially defined, and the parallel granularity represents the number of data points that can be read in parallel from a memory and can be used independently for butterfly computation. As shown in  FIG. 4 , assuming that the FFT data length is N=64, and the parallel granularity is 2 2 . Then, the 64 data points are divided into 16 groups for parallel processing. Each of the groups includes 4 data points, and can be used independently in two stages of radix-2 FFT computation. Each stage includes two butterflies  403 . When the parallel granularity is 2 B , each group can be used independently in B stages of radix-2 FFT computation, and each stage includes (2 B )/2 radix-2 butterflies. Therefore, upon reading a group, the butterfly computation module can perform B×(2 B )/2=B×2 B-1  butterfly computations independently, and then write the computation results to the multi-granularity parallel memory  400 . 
         [0043]    to For FFT data of a length N, log 2 N bits are required for representing an index value of each data point. After dividing into groups by the granularity 2 B , each of the N data points has its index value decomposed into two portions: a group index value and an intra-group index. For the N data points, there are in total N/2 B  groups, and log 2 (N/2 B )=log 2 N-B bits are required to represent the group index values. Given the definition G=log 2 N-B, the group index values may be denoted as g=g G-1  . . . g 1 g 0 . Meanwhile, each group includes 2 B  data points, and B bits are required to represent the intra-group index values. Here, the intra-group index values may be denoted as b=b B-1  . . . b 1 b 0 . Prior to starting the FFT computation, the index value of each data point may be denoted as: 
         [0000]      Data Index Value= g× 2 B   +b =( g&lt;&lt;B )+ b =( g   G-1    . . . g   1   g   0   b   B-1    . . . b   1   b   0 ) 
         [0044]    The 2 B  data points within a group may form 2 B /2=2 B-1  butterflies according to certain internal correspondence for FFT computation. Therefore, the index value of each butterfly needs to be represented by B-1 bits. According to the present disclosure, the data are grouped so that only one bit is different for the intra-group index values of two data points inputted to a butterfly computation. Here, this different bit is denoted by “b ? .” It is prescribed that when the bit “b ? ” has a value of 0, the corresponding data point represents input A of the butterfly computation; when the bit “b ? ” has a value of 1, the corresponding data point represents input B of the butterfly computation. Then, the intra-group index value for a butterfly may be denoted as b=b B-2  . . . b ?    . . . b   1 b 0 . The bit “b ? ” may be located at any position within the binary representation of the intra-group index value. The difference in position represents a “butterfly stride” for every butterfly in each computation stage, i.e., a difference between the index values of two input data points in the butterfly. For example, when the bit “b ? ” is located at the kth bit of the intra-group index value, all butterflies in the stage have a butterfly stride of 2 K . 
         [0000]      Butterfly stride=B′ Index−A′ Index=( b   B-2  . . . 1 b   k-1    . . . b   1   b   0 )−( b   B-2  . . . 0 b   k-1    . . . b   1   b   0 )=2 k  
 
         [0045]      FIG. 4  depicts data grouping and a parallel FFT computation flow. In the figure, assuming that the FFT data length is N=64, and the parallel granularity is 2 2 . Upon dividing data into groups in the parallel granularity of 2 B , each group can be used independently to perform B×(2 B )/2 2-based butterfly computations. The B×2 B-1  butterflies are referred to as a butterfly group  402 , and all butterfly groups available for parallel computation form a computation node  401 . The computation nodes have the same butterfly structure formed of a plurality of butterfly groups  402  in a vertical direction and a plurality of computation stages  404  in a horizontal direction. The overall FFT computation flow consists of a plurality of computation nodes  401 , which read data from the multi-granularity parallel memory  400 , pass the data through a plurality of computation stages  404 , and write the computation results to the multi-granularity parallel memory  400 . 
         [0046]    For different computation stages, the relative locations of the group index g and the intra-group index b may change. The present disclosure controls the R/W address and the R/W granularity for the butterfly groups in each computation node, so that the index of data for some butterfly in the kth computation stage of the ith computation node and the index of the corresponding twiddle factor can be expressed collectively as the butterfly representation  500  shown in  FIG. 5 . In  FIG. 5 , the butterfly representation  500  is divided into two portions. The first portion  501  is used to represent bits of the index values of two input data points for some butterfly computation, and the second portion  502  is used to represent bits of the index of the twiddle factor corresponding to the butterfly computation. A total of N/2 twiddle factors are required for FFT data of a length N. The value of each twiddle factor may be represented as e −(j2π/N)T (0≦T&lt;N/2). Accordingly, the value of the twiddle factor can be fully decided by T which is called as exponent of the twiddle factor. The index value  501  of the input data may also be viewed as two portions: group index value  502 ,  503 , and intra-group index value  504 .  502  refers to lower part of the group index value, and the lower part has a total of iB bits in a representation for the ith computation node.  503  refers to higher part of the group index value excluding the lower part  502 . Again, the intra-group index value  504  has B bits. For the butterfly at the kth computation stage of the ith computation node, the flag “b ? ” is located at the kth bit of the intra-group index value  504 . 
         [0047]    The exponent of the twiddle factor corresponding to the butterfly of the representation  501  may have a binary representation  505  in  FIG. 5 . The representation  505  has G+B-1 bits consisting of two portions: bits  507  and bits  506 . The bits  507  are k+iB bits on the right of the “b ? ” in the index value  501 , and the bits  506  consist of G+(1-i)B-1-k bits “0.” 
         [0048]      FIG. 6  shows butterfly representations of respective computation nodes and stages when N=64, and B=2. 
         [0049]      FIG. 1  shows a flowchart of the Cooley-Tukey algorithm with decimation in time. In the flowchart, the butterfly stride of the butterflies in the ith computation stage  103  is 2 i . To allow each butterfly group  402  to perform computation independently, data must be decimated from the initial data sequence by a butterfly stride at the time of data grouping. In the present disclosure, data decimation of various butterfly strides may be implemented by using multi-granularity parallel memories. 
         [0050]    The data storage method of the present disclosure is shown in  FIG. 8 , assuming N=64, and B=2. In the figure, the digital numbers denote index values of FFT data, the multi-granularity parallel memories  801  and  802  may be the multi-granularity parallel memories  300  and  301  of  FIG. 3 , respectively. There may be 2 B  memory blocks  804  within the multi-granularity parallel memory  901  when the parallel granularity is 2 6 . Here, the FFT data of a length N is divided into 2 6  groups which are stored sequentially in the 2 B  memory blocks  804 . One of the memory rows  805  in each memory block corresponds to data for one butterfly group. 
         [0051]      FIG. 9  shows a flowchart of a data access method at a computation node. Here, according to the steps shown in  FIG. 9 , the method of the present disclosure stores initial FFT data to a multi-granularity parallel memory, and sequentially reads data in respective memory rows  805  of memory blocks  804  in the memory. As shown in  FIG. 9 , the data access method for parallel FFT butterfly computation of the present disclosure includes the following steps. 
         [0052]    Step  1 , dividing initial FFT data of a length N into 2 G  groups by a parallel granularity 2 B , where G=log 2 N-B, and storing the 2 G  groups in respective memory rows  805  of 2 B  memory blocks  804  in the multi-granularity parallel memory  300  or  302 , where each of the memory blocks  804  comprises 2 G-B  groups, and occupies  2   G-B  memory rows  805 . 
         [0053]    For FFT data of a length N, there are a total of 2 G  groups when the parallel granularity is 2 B . 
         [0054]    Step  2 , storing sequentially 2 B −1 twiddle factors required for computation of each butterfly group  402  in memory rows of the multi-granularity parallel memory  303 . 
         [0055]    The exponent of the twiddle factor corresponding to the butterfly  403  at the kth computation stage  404  of the ith computation node  401  is T=(b k-1  . . . b 1 b 0 g iB-1  . . . g 1 g 0 0 . . . 0), 0≦k≦B-1, as denoted by  505  of  FIG. 5 . For a butterfly group  402 , g iB-1  . . . g 1 g 0  in  507  is fixed, while b k-1  . . . b 1 b 0  changes. Accordingly, the kth computation stage of the butterfly group needs 2 k  twiddle factors. The butterfly group has B computation stages, and thus the butterfly group as a whole needs Σ k-0   B-1 2 k =2 B −1 twiddle factors. 
         [0056]    The R/W bit width of the multi-granularity parallel memory  303  is 2 B  when the parallel granularity is 2 B . Accordingly, twiddle factors for the respective computation stages  404  of the butterfly group  402  may be calculated in advance, and stored sequentially in one of the memory rows of the multi-granularity parallel memory  303 . The twiddle factors for the butterfly group may be read in parallel with a granularity of 2 B  during the computation.  FIG. 7  shows how the twiddle factors for the respective computation stages  404  of the butterfly group  402  are stored in the memory row  700  when the parallel granularity is 8.  701  denotes a twiddle factor for the 1 st  computation stage,  702  denotes two twiddle factors for the 2 nd  computation stage, and  703  denotes four twiddle factors for the 3 rd  computation stage. 
         [0057]    Step  3 , reading data required for FFT butterfly computation stored in the jth memory row  805  of the ith memory block  804  in the multi-granularity parallel memory  300  or  302  with a read granularity of 2 B , where i and j each have an initial value of 0, and reading sequentially, from the multi-granularity parallel memory  303 , the twiddle factors required for FFT butterfly computation with a granularity of 2 B  in the order of the memory rows. 
         [0058]    When reading data for butterfly computation, the read granularity is set as 2 B , and data for FFT butterfly computation stored in the respective memory rows  805  of the memory blocks  804  in the multi-granularity parallel memory  300  are read sequentially. That is, the read operation starts with the zeroth memory row  805  of the zeroth memory block  804 , then the first memory row  805  of the zeroth memory block  804 , and so on, until all the memory rows  805  occupied by groups in the memory block  804  have been read. After the read operation of all the memory rows  805  occupied by groups in the zeroth memory block  804  is completed, the read operation continues with the memory rows  805  of the first memory block  804 , until all the memory rows  805  occupied by groups in the memory block  804  have been read. The R/W address is determined by the index value i of the memory block  804  and the index value j of the memory row  805 . The address for the jth memory row  805  of the ith memory block  804  is i×size of memory block+j×2 B . 
         [0059]    The memory rows  805  from which the data for the FFT butterfly computation are read at step  3  are sorted, and a global index for each memory row is obtained as I=(i&lt;&lt;G)+j, where i denotes the index of the memory block  804 , j denotes the index of the memory row  805 , and i&lt;&lt;G denotes shifting i by G bits leftward. Correspondence between the global index I of the memory row and the number g of the butterfly group  402  in the butterfly representation  500  is related to the index of the computation node  401  as follows: 
         [0000]      When the kth computation node reads data, the butterfly group  402  corresponding to the memory row of a global index I, which is numbered as g(whose value is I circulately shifted by kB bits leftward)  (Formula 1)
 
         [0060]    The twiddle factors for FFT butterfly computation are read sequentially from the multi-granularity parallel memory  303  in the order of the memory rows with a granularity of 2 B . Specifically, when reading the data for FFT butterfly computation at step  3 , the global index I of the memory row may be obtained from the index i of the memory block  804  and the index j of the memory row. Then, the number g of the butterfly group  402  corresponding to the Ith memory row may be obtained from the index I according to Formula  1 . The exponent  505  of the twiddle factor for the butterfly group  402  may be obtained from the number g by using the butterfly representation  500 , and then the twiddle factor may be calculated for the butterfly group  402 . 
         [0061]    Prior to the FFT computation, the twiddle factors for each butterfly group  402  in each computation node  401  are sequentially stored in a memory row  700  of the memory, as shown in  FIG. 7 . When reading the data for the computation at step  3 , the data stored in the memory row  700  may be sequentially read to obtain the twiddle factors for the butterfly group  402 . 
         [0062]    Step  4 , performing parallel butterfly computation on the data read from the jth memory row  805  with a granularity of 2 B  based on the read twiddle factors. 
         [0063]    The butterfly computation is an in-place operation, that is, in  FIG. 2  the index of the computation result A+BW in the output data must be the same as the index of A in the input data, and the index of the computation result A-BW in the output data must be the same as the index of B in the input data. 
         [0064]    Step  5 , writing the result data of butterfly computation to the multi-granularity parallel memory  300  or  302  with a granularity of 1, where when the data was read from the memory  300  at step  3 , the result data is written to the memory  302  in step  5 , and vice versa. 
         [0065]    The write address is the index of the memory row plus an increment. For the jth memory row  805  of the ith memory block  804 , the incremented index is i×N/2 2B +j. 
         [0066]    Step  6 , determining whether an index j of the current memory row satisfies j&lt; 2   G-B , and incrementing j by 1 and returning to step  3  if it satisfies, otherwise setting j to 0 and proceeding to step  7 . 
         [0067]    Step  7 , determining whether an index i of the current memory block satisfies i&lt;2 B , and incrementing i by 1 and returning to step  3  if it satisfies, otherwise terminating the method 
         [0068]    Each computation node  401  performs only one read/write operation. The multi-granularity parallel memories  801  and  802  form a ping-pong configuration. If the computation node  401  performs a read operation on the memory  801  at step  3  of  FIG. 9 , it will perform a write operation on the memory  802  at step  5 , vice versa. If the computation node  401  writes the results to the memory  801 , the next computation node will read the desired data from the memory  801 . 
         [0069]    The present disclosure also provides a data access device for parallel FFT computation which may implement the above data access method. As shown in  FIG. 3 , the device includes the multi-granularity parallel memories  300  and  302 , the multi-granularity parallel memory  303 , and the butterfly computation module  301 . 
         [0070]    The multi-granularity parallel memories  300  and  302  form a ping-pong configuration to alternatively store the input or output data of a computation stage  401 . 
         [0071]    The multi-granularity parallel memory  303  is configured to store twiddle factors for the computation stage  401 . The twiddle factors may be determined according to the above Formula 1. 
         [0072]    The butterfly computation module  301  is configured to perform butterfly computation on to-be-processed data alternately acquired from the multi-granularity parallel memories  300  and  302  based on the twiddle factors stored in the multi-granularity parallel memory  303 , and alternately store the computation results in the multi-granularity parallel memories  300  and  302 . 
         [0073]    Connection lines between the multi-granularity parallel memory  300  and the butterfly computation module  301  comprise data lines  306 , an address line  310 , and an access granularity indication line  309 ; connection lines between the multi-granularity parallel memory  302  and the butterfly computation module  301  comprise data lines  305 , an address line  312 , and an access granularity indication line  311 ; and connection lines between the multi-granularity parallel memory  303  and the butterfly computation module  301  comprise data lines  304 , an address line  308 , and an access granularity indication line  307 . 
         [0074]    It is assumed that a computation node reads data from the memory  300 , and writes the result to the memory  302 . According to the access method of  FIG. 9 , the R/W address and the R/W granularity for each memory block at the computation node are: 
         [0075]    address line  310 : i×size of memory block +j× 2   B    
         [0076]    access granularity indication line  309 : 2 B    
         [0077]    address line  312 : i×N/2 2B +j 
         [0078]    access granularity indication line  311 :  1   
         [0079]    address line  308 : i×N/2 B +j× 2   B    
         [0080]    access granularity indication line  307 : 2 B    
         [0081]    The foregoing description of the embodiments illustrates the objects, solutions and advantages of the present disclosure. It will be appreciated that the foregoing description refers to specific embodiments of the present disclosure, and should not be construed as limiting the present disclosure. Any changes, substitutions, modifications and the like within the spirit and principle of the present disclosure shall fall into the scope of the present disclosure.