Application driven embedded system design: a face recognition case study

ABSTRACT

The key to increasing performance without a commensurate increase in power consumption in modern processors lies in increasing both parallelism and core specialization. Core specialization has been employed in the embedded space and is likely to play an important role in future heterogeneous multi-core architectures as well. In this paper, the face recognition application domain is employed as a case study to showcase an architectural design methodology which generates a specialized core with high performance and very low powercharacteristics. Specifically, we create "ASIC-like" execution flows to sustain the high memory parallelism generated within the core. The price of this benefit is a significant increase in compilation complexity. The crux of the problem is the need to co-schedule the often conflicting constraints of data access, data movement, and computation. A modular compiler approach that employs integer linear programming (ILP) based "interconnect-aware" instruction and data scheduling techniques to solve this problem is then described. The resulting core running the compiled code delivers a 1.65x throughput improvement over a high performance processor (Pentium 4) while simultaneously achieving an 80x energy-delay improvement over an energy-efficient processor (XScale) and performs real-time face recognition at embedded power budgets.

REFERENCES

• 1: Cagdas Akturan , Margarida F. Jacome, CALiBeR: a software pipelining algorithm for clustered embedded VLIW processors, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 2: D. Burger and T. Austin. The Simplescalar Toolset, Version 2.0. Technical Report TR-97-1342, University of Wisconsin-Madison, June 1997.
• 3: Nathan Clark , Hongtao Zhong , Scott Mahlke, Processor Acceleration Through Automated Instruction Set Customization, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.129, December 03-05, 2003
• 4: Colorado State University. Evaluation of face recognition algorithms. http://www.cs.colostate.edu/evalfacerec/, 2003.
• 5: William J. Dally , Francois Labonte , Abhishek Das , Patrick Hanrahan , Jung-Ho Ahn , Jayanth Gummaraju , Mattan Erez , Nuwan Jayasena , Ian Buck , Timothy J. Knight , Ujval J. Kapasi, Merrimac: Supercomputing with Streams, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.35, November 15-21, 2003
• 6: F. EisenBrand. Gomory-Chvatal Cutting Planes and the Elementary Closure of Polyhedra. PhD thesis, Saarland University, 2000.
• 7: R. Gonzalez and M. Horowitz. Energy dissipation in general purpose microprocessors. IEEE Journal of Solid-State Circuits, 31(9):1277--1284, Sept. 1996.
• 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: Robert M. Haralick , Linda G. Shapiro, Computer and Robot Vision, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 10: A. Ibrahim. ACT: Adaptive Cellular Telephony Co-Processor. PhD thesis, University of Utah, December 2005.
• 11: Daniel Kästner , Sebastian Winkel, ILP-based Instruction Scheduling for IA-64, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.145-154, August 2001, Snow Bird, Utah, United States
• 12: Walter Lee , Rajeev Barua , Matthew Frank , Devabhaktuni Srikrishna , Jonathan Babb , Vivek Sarkar , Saman Amarasinghe, Space-time scheduling of instruction-level parallelism on a raw machine, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.46-57, October 02-07, 1998, San Jose, California, United States
• 13: Rainer Leupers, Instruction Scheduling for Clustered VLIW DSPs, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.291, October 15-19, 2000
• 14: B. Mathew, A. Davis, and R. Evans. A characterization of visual feature recognition. In Proceedings of the IEEE 6th Annual Workshop on Workload Characterization (WWC-6), pages 3--11, October 2003.
• 15: Binu K. Mathew , Al Davis, The perception processor, The University of Utah, 2004
• 16: Hyunchul Park , Kevin Fan , Manjunath Kudlur , Scott Mahlke, Modulo graph embedding: mapping applications onto coarse-grained reconfigurable architectures, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176778]
• 17: P. Jonathon Phillips , Hyeonjoon Moon , Syed A. Rizvi , Patrick J. Rauss, The FERET Evaluation Methodology for Face-Recognition Algorithms, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1090-1104, October 2000 [doi>10.1109/34.879790]
• 18: Laura Pozzi , Paolo Ienne, Exploiting pipelining to relax register-file port constraints of instruction-set extensions, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086300]
• 19: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]
• 20: Scott Rixner , William J. Dally , Ujval J. Kapasi , Brucek Khailany , Abelardo López-Lagunas , Peter R. Mattson , John D. Owens, A bandwidth-efficient architecture for media processing, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.3-13, November 1998, Dallas, Texas, United States
• 21: Henry A. Rowley , Shumeet Baluja , Takeo Kanade, Neural Network-Based Face Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.1, p.23-38, January 1998 [doi>10.1109/34.655647]
• 22: R. E. Schapire. The boosting approach to machine learning: An overview. In In MSRI Workshop on Nonlinear Estimation and Classification, 2002.
• 23: Michael S. Schlansker , B. Ramakrishna Rau, EPIC: Explicitly Parallel Instruction Computing, Computer, v.33 n.2, p.37-45, February 2000 [doi>10.1109/2.820037]
• 24: Michael D. Smith , Monica S. Lam , Mark A. Horowitz, Boosting beyond static scheduling in a superscalar processor, Proceedings of the 17th annual international symposium on Computer Architecture, p.344-354, May 28-31, 1990, Seattle, Washington, United States
• 25: P. Viola and M. Jones. Rapid object detection using a boosted cascade of simple features. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Dec. 2001.
• 26: Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997 [doi>10.1109/2.612254]
• 27: L. Wiskott, J. Fellous, N. Kruger, and C. Malsburg. Face Recognition by Elastic Bunch Graph Matching. Technical Report 96-08, Ruhr-Universitat Bochum, April 1996.
• 28: W. Zhao , R. Chellappa , A. Krishnaswamy, Discriminant Analysis of Principal Components for Face Recognition, Proceedings of the 3rd. International Conference on Face & Gesture Recognition, p.336, April 14-16, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Design, Performance

Keywords:
compilers, domain specific architectures, embedded systems, face recognition, instruction scheduling, workload characterization