Integrated Architectures for Computer Vision: Automatic Synthesis with Three Examples
Des architectures intégrées pour la vision: synthèse automatique en trois exemples
OPEN ACCESS
Computer aided computer design is an open problem because computers are becoming more and more powerfull, more and more complex and.. smaller. We explain what "automatic (high-level) synthesis of integrated circuits" means. It is now feasible and necessary for computer vision dedicated architectures in particular. Since it requires an optimization within an ill-formalized and ill-defined design space, we describe the experimental method aiming at : 1) proving the existence of a solution for each application case, 2) finding and instanciating the optimization parameters -including the initial state-,3)effectively designing an integrated circuit and 4) redesigning the solutions for more complex architecturesto still meet real-time constraints. The method is self-illustrated with three increasingly complex examples all along thispaper.
Résumé
La construction automatique d'ordinateur assistéeparordinateurC(AO)2est un problème ouvert parce que ceux-ci deviennent de plus en plus puissants, donc plus complexeset... plus petits. Nous expliquons ce qu'est la synthèse automatique de circuits intégrés ditede«haut niveau»,techniquedésormaisplausible et nécessaire notamment pourlesarchitectures spécialiséesen vision parordinateur. S'agissant d'une optimisation dans un ensembledifficileà formaliseret à circonscrire nous décrivons la démarche expérimentale suivie afin de : 1) prouver l'existence d'une solution par cas d'application, 2) déterminer les paramètresdel'optimisation, dont l'état initial, etlesinstancier, 3) concevoireffectivement un circuit et 4) retraiter les solutions pourdesarchitectures progressivement plus complexesn'en respectant pasmoinsdes contraintes de tempsréel. Ladémarche s'illustre parelle-même selon trois exemplesdedifficulté croissante qui jalonnent cet article.
Architecture, VLSI High-Level Synthesis, Image Processing, Data-Flow Graphs, Functional Description, Simulated Annealing.
Mots clés
Architecture, Synthèse VLSI,Traitement d'images, Graphes flot de données, Description fonctionnelle, Recuit simulé.
[1] E. Allartand B. Zavidovique. Functional image processing through implementation of regular data flow graphs. InProceedings of 21st Annual Asilomar Conference on signals, systems and computers. Pacific Grove, CA USA, November 1987, pp. 705-708.
[2] G. M. Amdahl. Validity ofthe simple processor approach to acheive large scale computing capabilities. InProceedings AFIPS, vol30, 1967.
[3] Pranav Ashar, Srinivas Devadas, and A. Richard Newton. Sequential Logic Synthesis. Kluwer Academic Publishers, Norwell, Massachusetts, USA, 1992.
[4] P.M. Athanas and A.L. Abbott. Reat-Time Image Processing on a Custom Computing Platform. Computer,28(2) : Fév. 1995, pp. 16-24.
[5] J. Backus . Can programming be liberated from the Von-Neumann style? A functional style and its algebra ofprograms.Communications of the ACM, 1978, 21.
[6] M. Barbacci. Instruction set processor specifications (ISPS) : The notation and its applications. InIEEETrans.on Computers, volume C-30, January 1981, pp. 24-40.
[7] Patricia Bournai, Bruno Chéron, Thierry Gautier, Bernard Houssais, and Paul Le Guernic. SIGNAL Manual. Technical Report 745, IRISA/INRIA Rennes, July 1993.
[8] Virginia Brecher. New techniques for patterned wafer inspection based on a model of human preattentive vision_ SPIE Journal on Applications of Artificial Intelligence : Machine Vision and Robotics, 1708 : 1992, pp. 452-459.
[9] R. Camposano. Structural synthesis in the Yorktown Silicon Compiler. In Proceedings of VLSI'87, Vancouver, August 1987.
[10] Raul Camposano and Wayne Wolf, editors. High-Level VLSI Synthesis. Kluwer Academic Publishers, 1991.
[11] J. Canny. A computational approach to edge detection . IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6): 1986, pp. 679-698.
[12] S. Dacic, Th. Bommart, and B . Zavidovique. A friendly interface for complex machine programming. In Proceedings of COMPINT'87, Montreal, CA, November 1987.
[13] Serge Dacic. Conception et exploitation intuitive de systèmes informatiques complexes.Thèsededoctorat, Universitéde Paris XI Centred'Orsay,1990.
[14] R. Deriche. Fast algorithms for low level vision . IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(1) : 1990, pp. 78-86.
[15] E. D.Dickmanns. Active Vision, chapter Expectation-based dynamic scene understanding, pages 303-335 . MIT Press, 1992.
[16] E. D.Dickmanns.Machine perception exploiting high-level spatio-temporal models. In Machine perception (La perception de l'environnement par senseurs automatiques). AGARD Lecture Series 185 (Advisory Group for Aerospace Research and Development). OTAN, Neuilly-Sur-Seine, FRANCE, 1992.
[17] Richard O. Duda and Peter E. Hart.Pattern Classification and Scene Analysis . Wiley-Interscience, New-York, 1973.
[18] E.F. Girczyc and J.P. Knight. An ADAto standard cell hardware compiler based on graph grammars and scheduling. InProceedings. of ICCD, 1984, pp. 726-731.
[19] G. Goossens, D. Lanneer, J. Vanhoof, J. Rabaey, J. Van Meerbergen, and H. De Man. Optimisation-based synthesis of multiprocessor chips for digital signal processing, with CATHEDRAL-Il. In Proceedings of the International Workshop on Logic and Architecture Synthesis for Silicon Compilers, Grenoble, FRANCE, 1988.
[20] Pravil Gupta, Chih-Tung Chen, J. C. DeSouza-Batista, and Alice C. Parker. Experience with image compression chip design using Unified System Construction tools. In Proceedings of the 31st ACM/IEEE Design Automation Conference, CD-ROM Publication, San Diego, CA, USA, 1994.
[21] J. L. Gustafson. Re-evaluating Amdahl's law.Communications of the ACM, 3](5) : 1988, pp. 532-533.
[22] Dave Johannsen. Bristle Blocks : a silicon compiler. InProceedings of the 16th ACM/IEEE Design Automation Conference, 1979.
[23] David W. Knapp and Alice C. Parker. A unified representation for design information. InProceedings of the 7th International Symposium on Computer Hardware Description Languages and their Applications, August 1985, pp. 337-353.
[24] I.C. Kraljié, G.M. Quénot, and B. Zavidovique. From Real-Time Emulation to ASIC Integration for Image Processing Applications . In Proc. of the 8th Annual IEEE International ASIC Conference, pages 31-4, Sept. 1995. Austin, TX, USA.
[25] Jean Mertnet, editor. VHDL for Simulation, Synthesis and Formal Proofs of Hardware.Kluwer Academic Publishers, 1992.
[26] J. W. Modestino and R. W. Fries. Edge detection in noisy images using recursive digital filtering. Computer Graphics and Image Processing, 6 1977, pp. 409-433.
[27] John K. Ousterhout, Gordon T. Hamachi, Robert N. Mayo, Walter S. Scott, and George S. Taylor. Magic : a VLSI layout system. In Proceedings of the 21" ACM/IEEE Design Automation Conference, Albuquerque, New Mexico, USA, 1984, pp. 152-159.
[28] L.Palmier,C. Legrand, F. Devos, and B. Zavidovique. A functional operation architecture for image processing . InInternational Symposium on Circuits and Systems,June 1985. Kyoto, Japan.
[29] Luc Palmier. Conception fonctionnelle de circuits intégrés de traitement d'images.Thèsedetroisièmecycle,Universitéde Paris XI Centre d'Orsay, 1985.
[30] Pierre G. Paulin. Algorithms for high-level synthesis with area and interconnect constraints. InProceedings of the EURO ASIC'89, Grenoble,France, 1989, pp. 144-158.
[31] Miodrag Potkonjak and Jan Rabaey. Optimizing resource utilization using transformations. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, CAD-13 : 1994, pp. 277-292.
[32] Stephane Praud. Implantationd'un algorithme d'étiquetage encomposantes connexes sur le Calculateur Fonctionnel.Rapport de DEA, Université de ParisSud Centred'Orsay, 1993.
[33] J. Rasure. KHOROS: Visual language and software development for image processing.International Journal on Imaging Systems and Technologies, 1990, pp. 183-199.
[34] A. Safir and B. Zavidovique. Towards a global solution to high-level synthesis problems. In Proceedings of European Design Automation Conference. Glasgow, Scotland, U.K.,March 1990, pp. 283-288.
[35] A. Safir and B. Zavidovique. A solution to the high level synthesis problems. The International Journal of Computer Aided VLSI Design, 3 : January 1991, pp. 43-69.
[36] G. Saucier and J. Trilhe, editors.IFIP Transactions on Synthesis for Control Dominated Circuits, volume A-22. North-Holland, 1992.
[37] J. Sérot, G.M. Quénot, and B. Zavidovique. Functional programming on a data-flow architecture : applications in real-time image processing. In International Journal of Machine Vision and Applications, volume 7, 1993, pp. 44-56.
[38] J. Sérot, G.M. Quénot, and B. Zavidovique. Calculateur Fonctionnel : une architecture flot de données pour le traitement d'images en temps réel. RevueScientifiqueet Technique de laDéfense, 1994, pp. 217-229.
[39] Jocelyn Sérot.Mise en oeuvred'un formalisme fonctionnelpour laprogrammation d'unearchitectureflotde données dédiée autraitement d'images temps réel. Thèse de doctorat, Université de Paris Sud Centred'Orsay, 1993.
[40] Jay R. Southard. MacPitts:An approach to silicon compilation. COMPUTER, pages 74-82, December 1983.
[41] D.E. Thomas, E.D. Lagnese, R.A. Walker, J.A. Nestor, J .V . Rajan, and R.L. Blackburn. Algorithmic and Register-Transfer Level Synthesis : The System Architect's Workbench. Kluwer Academic Publishers, Norwell, Massachusetts, USA, 1990.
[42] M. A. Turk, D. G. Morgenthaler, K. D. Gremban, and M. Marra. Vits - a vision system for autonomous land vehicle navigation.IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(3): 1988, pp. 342-361.
[43] P.J.M. van Laarhoven and E.H.L. Arts. Simulated Annealing : Theory and Applications. D.Reidel Publishing Company. Eindhoven, 1988.
[44] F. Verdier and B. Zavidovique. A complete environment for global architecture synthesis. InProceedings of Computer Architectures for Machine Perception Workshop, New Orleans, USA, December 1993, pp. 77-81.
[45] François Verdier. Conception de logiciels d'optimisation sous contraintes d'architectures VLSI pour le traitement d'images : le problème du contrôle.Thèsededoctorat, Université de Paris XI Centre d'Orsay, 1995.
[46] Naeem Zafar. Using emulation to cut ASIC and system verification time . ASIC Design, April 1994.
[47] B. Zavidovique, C. Fortunel, Quénot G., A. Safir, J. Sérot, and F. Verdier. Automatic synthesis of vision automata. In Magdi A. Bayoumi, editor, VLSI Design Methodologies for Digital Signal Processing Architectures, pages 261-318. Kluwer Academic Publisher, 1994.
[48] B. Zavidovique, V. Serfaty, and C. Fortunel. Mechanism to capture and communicate image-processing expertise. IEEE Software, November 1991, pp. 37-50.