本論文針對I/O控制器與其驅動程式提出一個新的軟硬體協同設計最佳化的作法，旨在探索驅動程式的效能與I/O暫存器數量之間的設計權衡。根據我們所定義軟體成本模型，將軟硬體最佳化問題正規為整數線性規劃(Integer Linear Programming)問題。論文中也提出有效的經驗法則演算法，在硬體(軟體)成本限制下，求取軟體(硬體)最低成本之設計。針對一些業界實例，我們進行了各種不同優化目標之設計探討，其可達到同時減少軟體與硬體成本，獲致令人滿意的結果。

This thesis presents a new HW/SW codesign approach for a programmable I/O controller and a device driver that manages this controller. The approach attempts to explore the design trade-off between the code performance of a device driver and the number of registers in an I/O controller. The formulations of exact minimizations for both software and hardware costs are devised. This work also presents heuristic algorithms based on iterative refinement to minimize the software (hardware) cost under a hardware (software) constraint. The proposed algorithms were implemented in C language and evaluated with a set of real devices. Compared with current industrial designs, the proposed approach can obtain design alternatives that reduce both software and hardware costs.

Abstract (in Chinese)…...…………………………………………….……………i
Abstract …………….…..……………………………………….……………….. ii
Acknowledgement…………………………………………………………………iii
Contents …...…………………………………………………………..………..…iv
List of Tables…...…………………………………………………………….…...v
List of Figures…...…...…………………………………………...….………….. vi
1. Introduction……………………………………...………………….…....1
1.1 HW/SW Interfaces of IO Devices ……...…………….………….1
1.2 System Overview…………..…………………………………….……....4
1.3 Related Works…………………………………………………………….5
1.3.1 Driver Synthesis…..……………….….………………….……….............7
1.3.2 Interface HW/SW Codesign………………..……………....…...........9
1.4 Purpose of Thesis………………………………………………...…….11
1.5 Thesis Organization……………………………………………...……..12
2. Problem Formation…………..……………………..…………..…............13
2.1 Software Cost………………………………………………….....…….14
2.2 Exact Minimization of Software Constraint…………..…..……….17
2.3 Exact Minimization of Hardware Constraint……………………….18
3. Optimization Algorithms…………………………………….….………...20
3.1 Optimization Strategy…………………………………………..………20
3.2 Algorithm for Software Optimization…………………………..………24
3.3 Algorithm for hardware Optimization....………………………..……...27
3.4 Algorithm allowing different groups sharing registers…………….…31
4. Experiment Results………………………………………………..………35
5. Conclusion……………………………………..…………………...………38
References……………………………………………………………….………39
Appendix A………………………………………………………..………………43

﹝1﹞F. Mérillon and G. Muller, “Dealing with Hardware in Embedded Software: A General Framework Based on the Devil Language,” Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, S. pp. 121 – 127, 2001.

﹝2﹞G. Borriello, L. Lavagno and R. B. Ortega, “Interface Synthesis: A Vertical Slice from Digital Logic to Software Components,” Proc. Of ICCAD, 1998.

﹝3﹞M. O’Nils and A. Jantsch, “Communication in Hardware/Software Embedded Systems-A Taxonomy and Problem Formulation,” Proc. Of IEEE NORCHIP, 1997.

﹝4﹞Jungo Ltd, WinDriver V5 Users Guide, URL: http://www.jungo.com/

﹝5﹞Bsquare, WinDk Users Manual, URL: http://www.bsquare.com/

﹝6﹞L. R´eveill`ere, F. M´erillon, C. Consel, R. Marlet, and G. Muller, “The Devil language,” Research Report 1319,IRISA, Rennes, France, May 2000.

﹝7﹞Q. L. Zhang, M. Y. Zhu and S. Y. Chen, “Automatic Generation of Device Drivers,” ACM SIGPLAN Notices, pp. 60-69, June 2003.

﹝8﹞C. L. Conway and S. A. Edwards, “NDL: A Domain-Specific Language for Device Drivers,” Proceeding of ACM LCTES, 2004.

﹝9﹞L. R´eveill`ere, G. Muller, “Improving Driver Robustness: an Evaluation of the Devil Approach,” Research Report 1385, IRISA, Rennes, France, March 2001.

﹝10﹞G. D. Micheli and R. K. Gupta, “Hardware-Software Co-Design,” Proceeding of The IEEE, vol. 85, no. 3, pp. 349-365, 1997.

﹝11﹞P. Paulin, G Goossens, C. Liem, M. Cornero, and F. Nacabal, “Embedded Software in Real Time Signal Processing Systems: Design Techniques,” Proceeding of The IEEE, vol. 85, no. 3, pp. 436-454, 1997.

﹝12﹞M. K. Jain, M. Balakrishnan, A. Kumar, “ASIP Design Methodologies: Survey and Issues”, Technical Report, Embedded System Project, Department of Computer Science and Engineering, Indian Institute of Technology, 2000.

﹝13﹞P. Chou, R. B. Ortega and G. Borriello, “Interface Co-synthesis Techniques for Embedded Systems,” Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 280-287, 1995.

﹝14﹞S. Wang, S. Malik and R. A. Bergamaschi “Modeling and Integration of Peripheral Devices in Embedded Systems,” DATE, pp. 136-141, 2003.

﹝15﹞M. O’Nils and A. Jantsch, “Operating system sensitive device driver synthesis from implementation independent protocol specification,” Proceedings of Design, Automation and Test in Europe Conference and Exhibition, pp. 563-567, 1999.

﹝16﹞J. M. Daveau, G. F. Marchioro, T. Ben-Ismail and A. Jerraya, “Protocol Selection and Interface generation for HW-SW Codesign,” IEEE Trans. On VLSI Systems, pp. 136-144, vol. 5, no. 1, 1997.

﹝17﹞E.G. Coffman Jr., M.R. Garey and D.S. Johnson, “Approximation algorithms for bin packing: A survey.” To appear in Approximation Algorithms for NP-Hard Problems, D.S. Hochbaum, ed., PWS Publishing Company, Boston, 1996.

﹝18﹞S. Martello and P. Toth, “Knapsack problems,” Wiley, 1990.

﹝19﹞M. Berkelaar, Lp_Solve, 1996, mail:michel@es.ele.tue.nl.

﹝20﹞D. A. Spielman and S. H. Teng, “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time,” Journal of ACM(JACM), Volume 51 , Issue 3, pp. 385-463, 2004.

﹝21﹞K. J K. J. Lin, S. S. Huang and S. W. Chen, “A hardware/ software codesign approach for programmable IO devices,” Proceedings of the 15th ACM Great Lakes Symposium on VLSI, pp. 323-327, 2005.

﹝22﹞G. Gognoit, M. Auguin and L. Bianco, “Communication synthesis and HW/SW integration for Embedded System Design,” Proceeding of 6th international workshop on HW/SW codesing, pp. 49-53, 1998.

﹝23﹞D. Hommais, F. Petort and I. Auge, “A practical tool box for system level communication sythesis,” Proceeding of ninth international symposium on HW/SW codesing, pp. 48-53, 2001.

﹝24﹞D. Filo, D. C. Ku, C. N. Caulho and G. D. Micheli, “Interface optimization for cuncurrent system under timming constraints,” Proceeding of IEEE transactions on VLSI systems , vol. 1, no. 3, 1993.

﹝25﹞V. K. Madisetti and L. Shen, “Interface Design for Core Based Systems,” Proceedign of IEEE Desing and Test, pp. 42-57, 1997.

﹝26﹞A. Schooll, R. Klein, and C. Jürgens, “BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem,” Computer and Operation Research 24, pp. 627-645, 1997.

﹝27﹞D. B. Stewart and B. L. Jacob, “Hardware/Software Co-Design of IO Interfacing hardware and Real-Time Device rivers for Embedded Systems,” Proceedings. of 1999 IEEE Real-Time Applications Symposium, 2000.

﹝28﹞Jay K. Adams, Donald E. Thomas, “The design of mixed hardware/software systems”, Proceedings of the 33rd annual conference on DAC, pp. 512-520,1996.

﹝29﹞A. Kalavade, E. A. Lee, “Manifestations of Heterogeneity in Hardware/Software Codesign”, Proc. of 31st Design Automation Conference (DAC'94), pp. 437-438, June 1994.

﹝30﹞James A. Rowson and Alberto Sangiovanni-Vincentelli, “Interface-Based Design,” Proc. of DAC, 1997.

﹝31﹞D. A. Patterson and J. L. Hennessy, “Computer Organization and Design The Hardware-Software Interface”, Morgan Kaufmann Publishers, 1994.

﹝32﹞A. Rajawat, M. Balakrishnan and A. Kumar, “Interface Synthesis: Issues and Approaches,” Proc. of the 13th VLSI Design Conference, 2000.

﹝33﹞Jane S. Sun and Robert W. Brodersen, “Design of System Modules,” Proc. of IEEE/ACM on CAD, 1992.

﹝34﹞Thomas Lehmann, “Towards Device Driver Synthesis,” Ph.D. thesis, Department of Mathematics and Computer Science of the University of Paderborn, 2002.