Application-specific instruction generation for configurable processor architectures

ABSTRACT

Designing an application-specific embedded system in nanometer technologies has become more difficult than ever due to the rapid increase in design complexity and manufacturing cost. Efficiency and flexibility must be carefully balanced to meet different application requirements. The recently emerged configurable and extensible processor architectures offer a favorable tradeoff between efficiency and flexibility, and a promising way to minimize certain important metrics (e.g., execution time, code size, etc.) of the embedded processors. This paper addresses the problem of generating the application-specific instructions to improve the execution speed for configurable processors. A set of algorithms, including pattern generation, pattern selection, and application mapping, are proposed to efficiently utilize the instruction set extensibility of the target configurable processor. Applications of our approach to several real-life benchmarks on the Altera Nios processor show encouraging performance speedup (2.75X on average and up to 3.73X in some cases).

REFERENCES

• 1: A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
• 2: Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
• 3: László Babai , Eugene M. Luks, Canonical labeling of graphs, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.171-183, December 1983 [doi>10.1145/800061.808746]
• 4: R. K. Brayton and F. Somenzi, "Boolean Relations and the Incomplete Specification of Logic Networks," in Proceedings of the 1989 International Conference on Computer-Aided Design, pp. 316--319, Nov. 1989.
• 5: Timothy J. Callahan , John R. Hauser , John Wawrzynek, The Garp Architecture and C Compiler, Computer, v.33 n.4, p.62-69, April 2000 [doi>10.1109/2.839323]
• 6: Jason Cong , Chang Wu , Yuzheng Ding, Cut ranking and pruning: enabling a general and efficient FPGA mapping solution, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.29-35, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296425]
• 7: Olivier Coudert, On solving covering problems, Proceedings of the 33rd annual conference on Design automation, p.197-202, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240555]
• 8: Ricardo E. Gonzalez, Xtensa: A Configurable and Extensible Processor, IEEE Micro, v.20 n.2, p.60-70, March 2000 [doi>10.1109/40.848473]
• 9: A. Grasselli and F. Luccio, "A Method for Minimizing the Number of Internal States in Incompletely Specified Machines," IEEE Transactions on Electronic Computers, vol. 14(3), pp. 350--359, Jun. 1965.
• 10: S. Hauck , T. W. Fry , M. M. Hosler , J. P. Kao, The Chimaera reconfigurable functional unit, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.87, April 16-18, 1997
• 11: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 12: R. M. Karp, "Reducibility Among Combinatorial Problems," Tech. Rep #3, EECS Department, University of California, Berkeley, Apr. 1972.
• 13: R. Kastner , A. Kaplan , S. Ogrenci Memik , E. Bozorgzadeh, Instruction generation for hybrid reconfigurable systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.605-627, October 2002 [doi>10.1145/605440.605446]
• 14: K. Keutzer and D. Richards, "Computational Complexity of Logic Synthesis and Optimization," in Proceedings of International Workshop on Logic Synthesis, May 1989.
• 15: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 16: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
• 17: B. D. McKay, "Practical Graph Isomorphism," Congressus Numerantium, vol 30, pp. 45--87, 1981.
• 18: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 19: A. Peymandoust, L. Pozzi, P. Ienne, and G. De Micheli, "Automatic Instruction-Set Extension and Utilization for Embedded Processors," in Proceedings of the 14th International Conference on Application-specific Systems, Architectures and Processors, Jun. 2003.
• 20: Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989
• 21: Douglas C. Schmidt , Larry E. Druffel, A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices, Journal of the ACM (JACM), v.23 n.3, p.433-445, July 1976 [doi>10.1145/321958.321963]
• 22: Mani B. Srivastava , Miodrag Potkonjak, Optimum and heuristic transformation techniques for simultaneous optimization of latency and throughput, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.1, p.2-19, March 1995 [doi>10.1109/92.365450]
• 23: V. Zivojinovic, J. M. Velarde, C. Schlager, and H. Meyr, "DSPStone - A DSP-oriented Benchmarking Methodology," in Proceedings of International Conference on Signal Processing Application Technology, pp. 715--720, Oct. 1994.
• 24: Altera Corp., http://www.altera.com.
• 25: Nauty Package, http://cs.anu.edu.au/people/bdm/nauty.
• 26: SUIF Compiler, http://suif.stanford.edu.
• 27: Tensilica Inc., http://www.tensilica.com.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
ASIP, binate covering, compilation, configurable processor, technology mapping