A new retiming-based technology mapping algorithm for LUT-based FPGAs

ABSTRACT

In this paper, w e presen t a new retiming-based technology mapping algorithm for look-up table-based field programmable gate arrays. The algorithm is based on a novel iterative procedure for computing all k-cuts of all nodes in a sequen tialcircuit, in the presence of retiming. The algorithm completely avoids flow computation whic his the bottleneck of previous algorithms. Due to the fact that k is very small in practice, the procedure for computing all k-cuts is v ery fast. Experimental results indicate the overall algorithm is very efficient in practice.

REFERENCES

• 1: Altera. Data Book Altera, San Jose, CA, 1995.
• 2: N. Bhat and D. Hill. Routable technology mapping for FPGAs. ~ A CM/SIGDA ~~~ on ~~s, p~ 143-148, 1992.
• 3: 3. ~ong ~d Y. D~g. ~M~: An ~gm~ te~n~o~ mapping ~goHthm ~r d~ ~~z~~ ~ lo~u~ tab~ b~ed FPGA d~i~s. ~ ~ns. on ~~e~ Aid~ Des~ 13:1-11, 1994.
• 4: 3. Cong ~d ~ Din~ On ~e~de~h t~d~off ~ ~~ b~ed FPGA te~n~o~ m~p~ ~ ~~. on ~~ ~tem~ 2:13~148, 1994.
• 5: Jason Cong , Yean-Yow Hwang, Partially-dependent functional decomposition with applications in FPGA synthesis and mapping, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.35-42, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258310]
• 6: J. C~g ~d C. ~. An i~r~d ~~t~ ~ p~ ~~ce ~m~ te&n~o~ m~~g ~ ~t~g ~ ~~~ed FPGA d~. ~ ~c. ~ ~~ on ~mpurer Des~ pag~ 572-578, 1996.
• 7: 3. Cong ~d G. ~. P~~~&~n FPGA ~h~ s~ ~th r~i~ng ~d p~~ng ~r se~e~i~ c~cu~s. ~ ~c. A~ D~n A~om~n ~~, 199Z
• 8: A. H. ~~ ~d M. S~~~. C~l~ ~ ~ ~u~t~ m~im~ion p~em ~r FPGA te~do~ m~p~g. ~ ~~. on ~~~A~d D~~ 13:1~I~2, 1994. -
• 9: Robert J. Francis , Jonathan Rose , Kevin Chung, Chortle: a technology mapping program for lookup table-based field programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.613-619, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123418]
• 10: Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127670]
• 11: R. 3. ~c~, 3. ~se, ~d Z.~~~. ~~oN o~ m~ng ~r ~o~p t~l~b~ed FPGAs ~r p~~ m~ce. In D~est ~ ~ ~tL ~~ on ~~ut~ Aided D~n, pa~ 568-571, 1991.
• 12: Kevin Karplus, Xmap: A technology mapper for table-lookup field-programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.240-243, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127672]
• 13: C. E. L~~~ ~d 3. B. S~e. ~t~ng ~n~~o~ ~c~t~ A~~hm~, 6:5~5, 1991.
• 14: A. M~~ ~d C. L. L~. ~~rm~ ~i~n te~N o~ m~p~g ~r ~u~~e b~ed FPG~ ~g ~e gener~ d~ mode. In A GM/SIGDA ~~h~ on ~eld ~~mab~ Gate A~y~ 1994.
• 15: ~&T Mi~o~~o~. A~T ~~~~m~ Gate A~~ Data Boo~ ~&T Mi~o~~o~, 1995.
• 16: Rajeev Murgai , Robert K. Brayton , Albert Sangiovanni-Vincentelli, Sequential synthesis for table look up programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.224-229, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164681]
• 17: Rajeev Murgai , Yoshihito Nishizaki , Narendra Shenoy , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic synthesis for programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.620-625, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123421]
• 18: ~ Pan. Continuous ~tim~ ~gofithms and ap~N c~ns. In IntL Conf. on Computer Des~n ~CCD), pag~ 116-121, 199L
• 19: Peichen Pan , C. L. Liu, Optimal clock period FPGA technology mapping for sequential circuits, Proceedings of the 33rd annual conference on Design automation, p.720-725, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240655]
• 20: Peichen Pan , C. L. Liu, Technology mapping of sequential circuits for LUT-based FPGAs for performance, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.58-64, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228379]
• 21: Peichen Pan , C. L. Liu, Optimal clock period FPGA technology mapping for sequential circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.437-462, July 1998 [doi>10.1145/293625.293632]
• 22: P. Sawkar , D. Thomas, Area and delay mapping for table-look-up based field programmable gate arrays, Proceedings of the 29th ACM/IEEE conference on Design automation, p.368-373, June 08-12, 1992, Anaheim, California, United States
• 23: Prashant Sawkar , Donald Thomas, Performance directed technology mapping for look-up table based FPGAs, Proceedings of the 30th international conference on Design automation, p.208-212, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164672]
• 24: M. Schla~ J. Kon~ and EK. Chan. RoutabiHty-driven techn~ogy mapp~g ~r lookup tabl~b~ed FPGA~. IEEE Trans. on Compute~Aided Des~ 13:13-26, 1994.
• 25: U. We~mann and W. R~ns~. Techn~ogy mapping ~r sequentiM c~c&ts b~ed on ~fiming tech~qu~, in Proc. Europ~n Des~n A~om~n Conf., pages 318- 323, 1993.
• 26: Nam-Sung Woo, A heuristic method for FPGA technology mapping based on the edge visibility, Proceedings of the 28th conference on ACM/IEEE design automation, p.248-251, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127675]
• 27: XiHn.x. The Prog~mmable Gate A~a~ Data Book. XiN lax, San Jose, CA, 1993.
• 28: Honghua Yang , D. F. Wong, Edge-map: optimal performance driven technology mapping for iterative LUT based FPGA designs, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.150-155, November 06-10, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Experimentation