FPGA-­‐based  design  of  a     Million  point  Sparse  FFT   Abhinav  Agarwal   ([email protected])   Computer  Science  and  ArCficial  Intelligence  Laboratory   MassachuseHs  InsCtute  of  Technology Outline   •  IntroducCon     •  MoCvaCon  for  hardware   •  ImplementaCon   –  4  Blocks:  Challenges  and  soluCons   –  Resource  usage  and  performance  constraints   •  Conclusion     1 Collaborators   •  Haitham  Hassanieh   •  Omid  Abari   •  Ezzeldin  Hamed   •  Prof.  Dina  Katabi   •  Prof.  Arvind     2 SFFT  implementaCon   •  Haitham  Hassanieh,  Piotr  Indyk,  Dina  Katabi,  Eric  Price:             Simple  and  Prac.cal  Algorithm  for  Sparse  Fourier  Transform,     Proceedings  of  the  Symposium  on  Discrete  Algorithms,  2012   •  SFFT  already  quite  fast  in  soYware:  20  ms  per  million  pt  FFT     •  Special  purpose  hardware  may  offer  several  more  benefits:   –  power  :  100-­‐1000x  lower  than  soYware   –  cost  and  form  factor:  Enabling  wireless,  mobile  or  air  borne  applicaCons   –  real  .me:  make  it  possible  to  compute  SFFT  in  real  Cme  on  streaming   data     •  Design  metrics:  10x  higher  performance  than  SW  while   consuming  100x  lower  power     3 Rapid  Prototyping  -­‐  FPGA     •  Custom  hardware  –  ASICs   –  High  performance,  low  power   –  Very  high  costs,  fixed  design,  no  revisions   •  FPGA  based  prototyping   –  Lower  performance  &  efficiency  than  ASICs,   •  SCll  beats  SW  handily   –  Very  low  cost   –  Reprogrammable  –  useful  for  evolving  algorithms   –  Parameterized  HW  for  different  applicaCons   4 Goal  &  Challenges   •  Goal:  Perform  million  pt  FFTs  at  ~1  ms  throughput   –  Enable  ~1  GHz  line  rate   •  Use  FPGA  prototyping  for  hardware  design  &  development   –  Target  Pla*orm:  Xilinx  ML605  plagorm  with  Virtex-­‐6  FPGA   –  Power  consumpCon:  1  W     •  Challenges       –  Algorithm  uses  extremely  large  shared  data  structures   –  Requires  a  very  fast  and  relaCvely  large  dense  FFT  (1024  -­‐  4096  pts)   –  Limited  HW  resources  on  FPGA    ⇒  need  modular  dataflow   –  Architectural  exploraCon  needed  as  SFFT  algorithm  relaCvely  new   •  HDL:  Bluespec  System  Verilog   5 Sparse  FFT  algorithm  parameters   •  Sub-­‐linear  algorithm  requires  only  some  of  the  input  data   •  IteraCve  probabilisCc  algorithm   •  Higher  the  no  of  iteraCons  &  greater  the  input  slice  sizes   –  Higher  the  confidence  in  output   –  Higher  the  noise  tolerance   –  Lower  the  error     •  Parameters  under  consideraCon   –  Input  Slice  size:  W    -­‐  storage  requirements   –  No  of  buckets:  B    -­‐  computaConal  requirements   –  No  of  iteraCons:  t    -­‐  performance  &  storage   •  Chosen  Values  for  N  =  220  and  k  =  500   –  W  =  8192,  B  =  4096,  t  =  8   6 Outline   •  IntroducCon   •  MoCvaCon  for  hardware   •  ImplementaCon   –  4  Blocks:  Challenges  and  soluCons   •  Conclusion     7 ImplementaCon  Blocks   Input   Datastream   Generate  Input  Slices  (Sampling  &  permutaCons)   Repeat  iteraCvely  t:  8   Perform  dense  FFT   MulCply  by  filter:  W  =  8192   For  each  slice:  4096  pt   &  Aliasing:  B  =  4096  samples   Find  large  buckets  for  each   Keep  track  of  frequencies  in   iteraCon   large  buckets   Output   Frequencies   Determine  locaCons  &  values  of  largest  frequencies   8 Outline   •  IntroducCon  to  the  algorithm   •  MoCvaCon  for  hardware   •  ImplementaCon   –  Block  1:  Input  Cme  slices   9