Dr. Chi-Sheng (Daniel) Shih

Assistant Professor
Embedded Systems and Wireless Networking Laboratory
Graduate Institute of Networking and Multimedia
Department of Computer Science and Information Engineering
National Taiwan University

#1 Roosevelt Rd. Sec. 4, Taipei, Taiwan 106, ROC
Office: +886-2-33664927
Fax: +886-2-23628167
Email:

News:


 

Starting from Feb. 1, 2004, I have joined the Department of Computer Science and Information Engineering at National Taiwan University as an assistant professor. I join the Real-time and Embedded Systems Lab.

Many research interests developed when I was at Urbana-Champaign will continue. For instance, multi-dimension real-time resource allocation and state-dependent deadline scheduling. In the meantime, I will start investigating other interesting research topics. At this moment, my research interests include real-time process scheduling, requirement assignment and determination, resource allocation, and system integration.

Awards:

  • The Best Paper Award, IEEE RTCSA 2005.
  • The Best Student Paper Award, IEEE RTSS 2004.

Research:

*Note: IEEE, SPIE and other institutions hold the copyrights on many papers listed here. Reproduction and distribution of these documents may be governed by those copyrights. To get softcopies of our published papers, please contact the publishers.

HW/SW Co-Design for System-on-Chip

I have started to investigate the research topics in HW/SW co-design area. There are tons of open problems to be solved in this area. Hopefully, I will come out some interesting and useful results soon. Some of my works related to this project are listed below*.
  • Li Chia and Chi-Sheng Shih, Template-based Run-time reconfiguration scheduling for partial reconfigurable SoC, in Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), Daegu, Korea, August 21-23, 2007.
  • Cheng-Min Lien, Ya-Shu Chen, Chi-Sheng Shih On-Chip Bus Architecture Optimization for Multi-core SoC Systems, Fifth IFIP Workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS 2007), Santorini Island, Greece, May 7-8, 2007.
  • Ya-Shu Chen, Chi-Sheng Shih and Tei-Wei Kuo, Dynamic Task Scheduling And Processing Element Allocation For Multi- Function SOCs, in Proceedings of 13th IEEE Real-Time and Embedded Technology and Applications Symposium, Bellevue, WA, United States, April 3 - April 6, 2007.
  • Jian-Jia Chen, Chuan-Yue Yang, Tei-Wei Kuo, and Chi-Sheng Shih, Energy-efficient Real-time Task Scheduling in Multiprocessor DVS Systems, In Proceedings of the 12th Asia and South Pacific Design Automation Conference, pp. 342 - 349, Yokohama, Japan, February 2007.
  • Chun-Nan Chou, Yi-An Chen, and Chi-Sheng Shih, Genetic-based Approach for Scheduling, Allocation, and Mapping for HW/SW Co-Design with Dynamic Allocation Threshold, in the WIP session of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications 2006 (To be appeared in NICTA technical report series).
  • Chun-Nan Chou, Yi-An Chen, and Chi-Sheng Shih, Genetic-based Approach for Scheduling, Allocation, and Mapping for HW/SW Co-Design. In Proceedings of VLSI/CAD 2006.
  • Jian-Jia Chen, Tei-Wei Kuo, and Chi-Sheng Shih, 1+epsilon Approximation Clock Rate Assignment for Periodic Real-Time Tasks on A Voltage-Scaling Processor. In Proceedings of EMSOFT 2005.
  • Chi-Sheng Shih, Chia-Lin Yang, Mong-Kai Ku, Tei-Wei Kuo, Shao-Yi Chien, Yao-Wen Chang, Liang-Gee Chen, Reconfigurable Platform for Content Science Research, In Proceedings of the 11th IEEE International Conference on RTCSA 2005, pp. 481--488, Hong Kong, China.[EI]
  • Nei-Chiung Perng, Chen-Min Lien, Tei-Wei Kuo, and Chi-Sheng Shih, On the Minimization of Buffer Memory for Hardware/Software Co-Synthesis Processes, In Proceedings of the 16th VLSI Design/CAD Symposium 2005.
  • Ya-Shu Chen, Nei-Chiung Perng, Chi-Sheng Shih, and Tei-Wei Kuo, Interference Analysis of Multiple Critical Paths, ASPICES 2005, Bangalore, India, July 2005.

Sensor Information Systems

Advance VLSI technology has made the dream of sensor information system almost come true. Should the sensor information system function well without proper software support. I am particularly interested in Sensor Information Systems for Active Retirees and Assisted Living, called SISARL in short. I have collaborated with faculty and students with Academia Sinica, National Taiwan University, National Tsing-Hua University and National Chao-Tung University in this project.

The thrusts of our work are on technologies for the design, production, and quality assurance of easy-to-use, dependable SISARL appliances and services with state-of-art and future capabilities. These appliances and services are not only needed to improve the well-being of an increasingly larger segment of the global population, but they also present to the ICT (Information and Communication Technologies) industry a tremendous new business opportunity. We want to help the industry to shorten the time and lower the cost required to bring families of high-quality SISARL products and services to market.

Some of my works related to this project are listed below*. The detail information of this project can be founded at its project web-site.

Mobile Web Services

I also started to investigate the research topics in mobile web services. Here are some of my latest results.
  • C.F. Kuo, C.Y. Chen, Chi-Sheng Shih, and T.W. Kuo, Threat-Based Configuration Architecture for Security Gateways. In Proceedings of the 14th IEEE International Conference On Networks, September, 2006.
  • Yi-Hua Tsai, Jian-Jia Chen, Tei-Wei Kuo, and Chi-Sheng Shih, Realizing Client and Server Mobility for WEB Applications, in Proceedings of Mobility, Agents, and Mobile Services Workshop 2005 (MAM2005).
  • Yi-Hua Tsai, Jian-Jia Chen, Tei-Wei Kuo, and Chi-Sheng Shih, Client and Server Mobility for WEB Applications. In Proceedings of the Sixth International Conference on Information Integration and Web Based Applications Services (iiWAS2004), 2004.

State-Dependent Deadline Scheduling

It all started from a chat with Prof. Jane Liu, my thesis advisor, in a sunny afternoon in 1999. Jane just came back from Taipei and we talked about how to survive and drive in Taipei (Yes, the traffic in Taipei was a nightmare at that time. Now, it is all different.) All of sudden, we started to dream of having 'intelligent' vehicle navigation systems on our cars. So, we can reserve a parking spot right before we arrive a restaurant, dynamically plan a new route by knowing the latest traffic condition, and other crazy ideas. Okay, let's make a long story short. We found that traditional real-time task workload models are not able to model the transmission jobs in the intelligent vehicle system. Essentially, the deadline of such jobs change as the state of the vehicle such as speed and direction and the state of the vehicle changes as time goes on. Hence, the job deadline changes over time. Obviously, the system has no control over the changes of deadlines but has to adapt its scheduling decisions to such changes. The rest is just the history.

Thanks for that wonderful afternoon. Since then, we have studied the related issues and published several papers. Most of all, I have completed my thesis. Here are the list of our papers on this topic*.
  • Jian-Jia Chen, Jun Wu, and Chi-Sheng Shih, Approximation algorithms for scheduling real-time jobs with multiple feasible intervals , in the Real-Time Systems Journal, Volume 34, Number 3 / November, 2006 Pages 155-172.
  • Jian-Jia Chen, Jun Wu, Chi-Sheng Shih, and Tei-Wei Kuo, Approximation Algorithms for Scheduling Multiple Feasible Interval Jobs, in the Proceeding of The 11th IEEE International Conference on RTCSA 2005, pp. 11 -- 16, August, 2005.[Best Paper Award][EI]
  • Chi-Sheng Shih and Jane Liu, Acquiring and Incorporating State-Dependent Real-Time Performance Requirements, Volume 9, Number 2: pp. 121 - 131, May 2004, Requirements Engineering Journal.
  • Chi-Sheng Shih, Scheduling Task with State-Dependent Deadlines, Ph.D. Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 2003.
  • Chi-Sheng Shih and Jane Liu, Acquiring and Incorporating State-Dependent Real-Time Performance Requirements, in the Proceeding of the IEEE Requirements Engineering Conference, Monterey Bay, CA, 2003.[Best Paper Award nominee][EI]
  • Chi-Sheng Shih, Jane Liu, and Infan Kuok Cheong, Scheduling Jobs with Multiple Feasible Intervals, in the Proceeding of the IEEE Real-Time Computing and Systems and Applications, Tainan, Taiwan, 2003.
  • Chi-Sheng Shih and Jane Liu, State-Dependent Deadline Scheduling, In Proceedings of the IEEE Real-Time Systems Symposium, Austin TX, Dec. 2002.[EI]
  • Chi-Sheng Shih, Lui Sha, and Jane Liu, Task Scheduling with Variable Deadlines, In Proceedings of the seventh real-time technology and applications symposium, Orlando FL, 2001.

Scheduling Tasks in Multi-Function Phased Array Radars

The scheduling problems of radar systems have been there for more than 30 years. For some mysterious reasons, the researchers in the real-time community do not want to touch it and the researchers in radar systems do not have time to solve it yet. When the MURI project started in 2001, our team was asked to solve this problem. As more materials we studied on this topic, the more we believe that this is an extremely difficult scheduling problem. Fortunately, we have made some progresses.

Here is the list of our papers on this topic*.

  • Chang-Gun Lee, Phil-Su Kang, Chi-Sheng Shih, Lui Sha: Schedulability Envelope for Real-Time Radar Dwell Scheduling, in the IEEE Trans. Computers Volume 55, Numbers 12, Pages 1599-1613, 2006.
  • Sathish Gopalakrishnan, Marco Caccamo, Chi-Sheng Shih, Chang-Gun Lee and Lui Sha, Finite-horizon scheduling of radar dwells with online template construction , in the Real-Time Systems Journal, Volume 33, Numbers 1-3 / July, 2006, Pages 47-75, July 2006.
  • Chin-Fu Kuo, Chi-Sheng Shih, and Tei-Wei Kuo, Resource Allocation Framework for Distributed Real-Time End-To-End Tasks, In Proceedings of The Twelfth International Conference on Parallel and Distributed Systems (ICPADS 2006) 2006, July 2006.
  • Chin-Fu Kuo, Chi-Sheng Shih, and Tei-Wei Kuo, Resource Allocation Framework for Distributed Real-Time End-To-End Tasks, Techical Report NTU/NEWS-6-005, NEWS Lab, Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan.
  • Sathish Gopalakrishnan, Marco Caccamo, Chi-Sheng Shih, Chang-Gun Lee, and Lui Sha, Finite-Horizon Scheduling of Radar Dwells with Online Template Construction, In Proceedings of IEEE Real-Time Systems Symposium, December 2004.[Best Student Paper Award][EI]
  • Chang-Gun Lee, Phil-Su Kang, Chi-Sheng Shih, Marco Caccamo, and Lui Sha, Schedulability Envelope for Real-Time Radar Dwell Scheduling and Its Application to Multi-Ship Multi-Radar Systems, in Proceedings of Radar 2004 International Conference, Toulouse, France, Oct. 2004
  • Chang-Gun Lee, Chi-Sheng Shih, and Lui Sha, Online QoS Optimization Using Service Class in Surveillance Radar Systems, Volume 28, Number 1: pp. 5-37, October 2004, Real-Time Systems Journal.[SCI]
  • Chi-Sheng Shih, Phanindra Ganti, and Lui Sha, Schedulability and Fairness for Computation Tasks in Surveillance Radar Systems, In Proceedings of the 10th RTCSA conference (Real-time and Embedded Computing Systems and Applications Conference), 2004.[Best Paper Award nominee]
  • Chi-Sheng Shih, Phanindra Ganti, and Lui Sha, Schedulability and Fairness for Computation Tasks in Surveillance Radar Systems, NTU Technical Report.
  • Chi-Sheng Shih, Sathish Gopalakrishnan, Phanindra Ganti, Marco Caccamo, and Lui Sha, Synthesizing Task Periods for Dwells in Multi-Function Phased Array Radars, IEEE Radar Conference 2004.[EI]
  • Chang-Gun Lee, Phil-Su Kang, Chi-Sheng Shih, Lui Sha. Radar dwell scheduling considering physical characteristics of phased array antenna, In Proceedings of IEEE Real-Time Systems Symposium. December 2003.[Best Paper Award nominee][EI]
  • Chi-Sheng Shih, Sathish Gopalakrishnan, Phanindra Ganti, Marco Caccamo, and Lui Sha, Dwell Scheduling Using Tasks with Synthetic Periods, in Proceedings of IEEE Real-Time Systems Symposium, Cancun, Mexico, Dec. 2003.[EI]
  • Chi-Sheng Shih, Sathish Gopalakrishnan, Phanindra Ganti, Marco Caccamo, and Lui Sha, Template-Based Real-Time Dwell Scheduling with Energy Constraint, IEEE RTAS, Washington DC, May 2003.
  • Chang-Gun Lee, Chi-Sheng Shih, and Lui Sha, Service Class based Online QoS Management in Surveillance Radar Systems, IEEE RTSS Dec. 2001.

Wireless Sensor Networks

I also work with Prof. Marco Caccamo at University of Illinois at Urbana-Champaign for real-time scheduling on wireless sensor networks. One of our works will be published on 2004 EuroMicro Real-Time Conference*.
  • Guo-Liang Li and Chi-Sheng Shih, Clock Free Data Streams Alignment for Sensor Networks , in Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), Daegu, Korea, August 21-23, 2007.
  • Simone Giannecchini, Marco Caccamo, and Chi-Sheng Shih. Collaborative Resource Allocation in Wireless Sensor Networks, in Proceedings of the 16th EuroMicro Conference on Real-Time Systems (ECRTS '04), 2004.

Open Real-Time Systems

This is the first project Jane gave me. Since 1995 (or 96), Jane had lead our lab to develop the open system architecture. The open system architecture allows a system to have real-time and non-real-time tasks to run simultaneously on one system without performing a global schedulability analysis when the system workload changes. The open system architecture was implemented on Windows NT4. However, due to the non-disclosure agreement between Microsoft and us, we are not allowed to show the community how we did it. So, Jane asked me to implement it on Linux*.

  • Chi-Sheng Shih, Jane W.-S. Liu, John Qian, Mangesh Jonnalagadda, Jia-Ru Li. Open Real-Time Linux, In Proceedings of The Second Real-Time Linux Workshop. 2000

Database, Knowledgebase, and Information Retrieval

In my senior year, I met Prof. Chiang Lee at National Cheng Kung University. He inspired to me to start the researches in database systems. We studied the query optimization problem in object-relational database systems.

Here is the list of our papers on this topic*.

  • Chi-Sheng Shih, Chiang Lee, Yaw-hui Chen. A Graph-Theoretic Model for Optimizing Large Join Queries, In Proceedings of The Fifth International Conference on Database Systems for Advanced Applications(DASFAA). 1997.
  • Shian-Hua Lin, Chi-Sheng Shih, Meng Chang Chen, Jan-Ming Ho, Ming-Tat Ko, Yueh-Min Huang. A Collaborative Internet Documents Access Scheme Using ACIRD. in Proceedings of International Computer Symposium on Software Engineering and Database Systems. 1998.
  • Shian-Hua Lin, Chi-Sheng Shih, Meng Chang Chen, Jan-Ming Ho, Ming-Tat Ko, Yueh-Min Huang. Extracting Classification Knowledge of Internet Documents: A Semantics Approach In Proceedings of the 21st International ACM SIGIR Conference on Research and Development in Information Retrieval. 1998.
  • Shian-Hua Lin, Chi-Sheng Shih, Meng Chang Chen, Jan-Ming Ho, Ming-Tat Ko, Yueh-Min Huang. ACIRD: An Intelligent information system based on data mining. In Proceedings of the ACM SIGMOD-PODS DKMS. 1998.
  • Sin-Yan Iap, Hung-Yu Kao, Chin-Fu Ku, Yau-Tsung Lee, Shian-Hua Lin, Yu-Chung Pan, Chi-Sheng Shih, Chia-Hui Chung Wang, Meng Chang Chen, Jan-Ming Ho, Ming-Tat Ko. ASIS MDL: A prototype electronic content service. In Proceedings of the IEEE Workshop on Dependable and Real-Time E-Commerce Systems. 1998.
  • Chiang Lee, Chi-Sheng Shih, Yaw-hui Chen. Optimizing Large Queries Using A Graph-Based Approach. in IEEE Transactions on Knowledge and Data Engineering, Vol. 13, No. 2, pages 298 -- 315. 2001.[SCI]
  • Chiang Lee, Chi-Sheng Shih, Yaw-hui Chen. A Graph-Theoretic Model For Optimizing Queries Involving Methods. in the VLDB Journal, Vol. 9, Issue 4. 2001.

Professional Activity:

  • Advisory committee of OSSF.
  • Member of the Program Committee of EUC 2008.
  • Program Co-Chair of 14th Workshop on Compiler Techniques for High-Performance Computing (CTHPC 2008).Web Site
  • Program Co-Chair of IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2008). Web Site
  • Program Co-Chair of International Conference for Enterprise Systems and Applications (ICESA) 2007.
  • Member of the Program Committee of RTSS 2007.
  • Member of the Program Committee of SIES (IEEE Second International Symposium on Industrial Embedded Systems) 2007.
  • Member of the Program Committee of ICPADS 2007.
  • Member of the Program Committee of TFIT 2007.
  • Member of the Program Committee of ICESS(International Conference on Embedded Software and Systems) 2007.
  • Workshop Program Co-Chair of EUC 2007.
  • Member of the Program Committee of ATC 2006, 2007.
  • Member of the Program Committee of TENCON 2006.
  • Publicity chair of RTAS 2005.
  • Member of the Program Committee of WESE 2006, 2007.
  • Member of the Program Committee of RTCSA 2004 - 2007.
  • Member of the Program Committee of ICPADS 2005.
  • External reviewers for IEEE TPDS, MobiCom 2004, RTSS 2003, RTAS 2003, EuroMicro Real-Time Conference, and IEEE Trans on Parallel and Distributed Systems, Journal of Computer Systems. [SCI]

Teaching:

Networked SoC Systems

This new course will be offered in Spring 2005. The course website is here. The curriculum design for this course is reported in the following reports*.
  • Chi-Sheng (Daniel) Shih, Chia-Lin Yang, Shih-Hao Hung, Chih-Wen Hsueh, Chuen-Liang Chen, and Tei-Wei Kuo, SoC System Design Program for Computer Science Majors, in the Proceedings of the Workshop of Embedded Software Education, October, 2007.
  • Chi-Sheng Shih, Shiao-Li Tsao, Yeh-Ching Chung, and Shyh-In Hwang, Toward HW/SW Integration: a Networked Embedded System Course in Taiwan, ACM SIGBED Review, Volume 4, Number 1, January 2007.
  • Chi-Sheng Shih, Shiao-Li (Charles) Tsao, Yeh-Ching Chung, and Shyh-In Hwang, Toward HW/SW Integration: Networked Embedded System Design, in the Proceeding of the Workshop of Embedded Software Eduction, October, 2006.
  • Chi-Sheng Shih, Shiao-Li (Charles) Tsao, Yeh-Ching Chung, and Shyh-In Hwang, Toward HW/SW Integration: Networked Embedded System Design, Tech Report NTU/NEWS-6-0008, National Taiwan University, August 2006.

Systems Programming (Course Number: 902 44000)

This course was offered in Spring semester. The course website for Spring 2006 is here.

Advanced Operating Systems (Course Number:922 M1360)

This course will be offered in Fall 2004. This course is one of the core courses of Graduate Institute of Networking and Multimedia. The course syllabus and materials is now available on-line.

Creative Workshop

Taiwan's manufacture industries have been the Original EquipmentManufacturer (OEM) and Original Design Manufacturer (ODM) center for various goods in the world for several decades. To maintain the momentum of Taiwan's economics, Taiwan's industries have to migrate from OEM, to ODM, and to Intellectual Property Creator (IPC). The creation of a workforce skilled in creative team work is a key ingredient for the successful transition.

The goal of the mini-workshop The Next-Wave Technology is to help the attendants to practice the process of creative thinking and team work. At the end of the mini-workshop, we expect the students to know how to build the process for creative and critical thinking and master the skills for bringing out the best from team members with different professional backgrounds.

This workshtop is not an official NTU course and the students will not earn any NTU credits. Current workshop started on March, 2006 and will ends at late April. The next workshop is scheduled to start in the coming summer. If you are interested in this course, please drop me a line. The course materials and students' works can be found at our course website.

Independent Study

In every year, I also advice senior students to conduct creative projects for one year. Here I list the projects I am doing or I have done.
  • Story Telling on TabletPC : Project website

    Early studies show that drawing and writing help the development for early childhood kids. Thanks to the advance hardware and software technology for personal computers, using computers for drawing is now an essential tool for many professionals such as illustration artists and animators. However, the studies also show that modern input devices including keyboard and point devices are not suitable to early childhood kids. In this project, we will design and develop an application for collaborative drawing on TabletPC for early childhood kids. The application will allow the kids who sit at different corners of the classroom or at different parts of the world to draw one picture or composite their stories. We will make use the new programming technology for TabletPC to develop the real-time collaborative drawing application. After the application development, we will conduct the field study to observe how the kids interact with each other via this application and how the application affects the childrens learning process.

  • Component-based Robotics for Assistive Living:
  • Real-Time Operating Systems for Heterogeneous Multi-core Platforms:

    Many operating systems are out there for multi-core platforms. However, only few of them are designed for heterogeneous multi-core platforms.

Misc:


*Note: IEEE, SPIE and other institutions hold the copyrights on many papers listed here. Reproduction and distribution of these documents may be governed by those copyrights.