*********************************************** Note: Each presentation is at most 15 minutes *********************************************** Note: Please email me your topic and referenced paper(s)' titles before your presentation. If you are still looking for a project, consider the three future directions in section 7 of the paper shown in class: Ming Zu and Albert M. K. Cheng, ``Real-Time Scheduling of Hierarchical Reward-Based Tasks,'' Proc. IEEE-CS Real-Time Technology and Applications Symp., May 2003. ------------------------------------------------------- 11/9 Albani Andrea "Genetic Algorithm approach to Scheduling Real-Time Tasks on a Multiprocessor System" Partial bibliography: G. Syswerda, â^À^ÜSchedule Optimization Using Genetic Algorithmsâ^À^Ý, Chapter 21 of the Handbook of Genetic Algorithms, New York, NY, Van Nostrand Reinhold, 1990. G. Syswerda, J. Palmucci, â^À^ÜThe Application of Genetic Algorithms to Resource Schedulingâ^À^Ý, Proceedings of the Fourth International Conference on Genetic Algorithms, pp 502-508, July 1991 H. Mitra, P. Ramanathan â^À^Ü A Genetic Approach For Scheduling Non-preemptive Tasks With Precedence and Deadline Constraintsâ^À^Ý, 26th Hawaii International Conference on systems sciences, vol II, pp 556-564, Jan.1993. E.S.H. Hou, N. Ansari, H.Ren, â^À^ÜA Genetic Algorithm for Multiprocessor Schedulingâ^À^Ý, IEEE Transactions on parallel and distributed systems, vol 5, no 2, pp 113-120, Feb. 1994. Y. Monnier, J-P. Beauvais, A-M. Déplanche. â^À^ÜA Genetic Agorithm for Sheduling Tasks in a Real-Time Distributed Systemâ^À^Ý, Proceedings of the 24th Euromicro Conference, pp 708-714, 1998. I-J Jeong, G. Papavassilopoulos, D.S. Bayard, â^À^ÜTask scheduling on Spacecraft by Hybrid Genetic Algorithmsâ^À^Ý, Proceedings of the 1999 IEEE International Conference on Robotics and Automation, May 1999. J. Oh, C. Wu, â^À^ÜGenetic-algorithm-based real-time task scheduling with multiple goalsâ^À^Ý, the Journal of Systems and Software 71, pp 245-258, 2004. ------------------------------------------------------- Arora Nitin "Hardware in loop simulator for mini aerial vehicle" Primary requirement of HILS is real time operation and this puts lot of demand on the design of testing environment. Most of the Components have to perform in real-time including the simulation. ------------------------------------------------------- Chada Shashank "Task scheduling in multi-processor Real-time systems: A feedback control approach". Basically I would like to review some of the open-loop scheduling algorithms and discuss this new paradigm based on feedback control ( closed loop ). ------------------------------------------------------- Chen Chun-Sheng Power-aware computing: "Procrastination Scheduling in Fixed Priority Real-time systems" Ravindra Jejurikar, Rajesh Gupta June 2004 ACM SIGPLAN Notices , Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools, Volume 39 Issue 7 Abstract: Procrastination scheduling has gained importance for energy efficiency due to the rapid increase in the leakage power consumption. Under procrastination scheduling, task executions are delayed to extend processor shutdown intervals, thereby reducing the idle energy consumption. We propose algorithms to compute the maximum procrastination intervals for tasks scheduled by either the fixed priority or the dual priority scheduling policy. We show that dual priority scheduling always guarantees longer shutdown intervals than fixed priority scheduling. We further combine procrastination scheduling with dynamic voltage scaling to minimize the total static and dynamic energy consumption of the system. Our simulation experiments show that the proposed algorithms can extend the sleep intervals up to 5 times while meeting the timing requirements. The results show up to 18% energy gains over dynamic voltage scaling. ------------------------------------------------------- 11/11 Arigai Gunaranjan "Adaptative Time critical resource management using time/utility functions" ------------------------------------------------------- Dai Xiang "Deriving Real-Time Database Transaction for EDF Scheduling" ------------------------------------------------------- Dang Zheng "Multimedia Real-Time disk Scheduling by Local/Global Seek-optimizing Approaches" ------------------------------------------------------- Deo Abhisheik "Pattern Recognition Based Adaptive Real-Time Scheduling." Here I am presenting a Pattern Recognition based Adaptive Real-time Scheduling (PRARS) framework for adaptive real-time systems. The usage of Pattern Recognition Theory provides a scientific underpinning on PID Proportional, Integral, Derivative) control. Reference: 1) Pattern recognition based adaptive real-time scheduling Xiao-An Shi Xing-She Zhou Jian-Hua Gu Yi Lin Dept. of Comput. Sci. & Eng., Northwestern Polytech. Univ., Xi'an, China ------------------------------------------------------- Fang Shaohong Network Packet scheduling using NDIS 5.0 in windows XP. Topic: A Near-Optimal Packet Scheduler For QoS Networks I intend to simulate the RPQ+ scheduler. Reference 1. Dallas E. Wrege Jörg Liebeherr, A Near-Optimal Packet Scheduler for QoS Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.576, April 09-11, 1997 2. D. E. Wrege, E. W. Knightly, H. Zhang, and J. Liebeherr. Deterministic Delay Bounds for VBR Video in Packet-Switching Nelworks: Fundamental Limits and Practical Tradeoffs. IEEE/ACM Transactions on Networking, 4(3):352-362, June 1996. 3. Jörg Liebeherr , Dallas E. Wrege , Domenico Ferrari, Exact admission control for networks with a bounded delay service, IEEE/ACM Transactions on Networking (TON), v.4 n.6, p.885-901, Dec. 1996 4. Larry L. Peterson, Bruce S. Davie. Computer Networks. A systems Approach. ISBN 1-55860-514-2 2000 ------------------------------------------------------- Garg Abhinav "Design and evaluation of priority table based real-time scheduling algorithms" Qiang Wang; Hong-An Wang; Hong Jin; Guo-Zhong Dai; Robotics, Intelligent Systems and Signal Processing, 2003. Proceedings. 2003 IEEE International Conference on , Volume: 2 , 8-13 Oct. 2003 Pages:1294 - 1299 vol.2 ------------------------------------------------------- 11/16 Chen Jun "Scheduling periodic task systems to minimize jitter" Here are some referenced papers: "Scheduling periodic task systems to minimize output jitter" by Sanjoy Baruah, Giorgio Buttazzo,etc "Scheduling and admission testing for jitter-constrained periodic threads" by Andreas Mauthe and Geoff Coulson "The Jitter margin and its application in the design of real-time control systems" by Anton Cervin, Bo Lincoln, Johan Eker, Karl-Erick Arzen, Giorgio Buttazzo "Jitter concerns in periodic task systems" by Sanjoy Baruah, Deji Chen, etc ------------------------------------------------------- Goel Manav "Classification of images is a real time environment using RTS and AI" References: (1) Ming Zhu and Albert M.K.Cheng, `Real Time Scheduling of Hierarchical Reward Based Tasks` (2) Z. Zhu and A. M. K. Cheng, ``Worst Case Round Trip Time Prediction and Statistical Analysis Using Extreme Values Theory,'' (3) Feng Shang and Albert Cheng,`Time Constrained JPEG image Transmission via Variable Quality coding' (4) Shaogang and TaoXiang, `Recognition of Group Activities using DPN' (5) Thomas S.Huang and Ying Wu, `Hand Modeling Analysis and Recognition' It is basically a faster viewable approach of images in a bandwidth and time constrained environment. ------------------------------------------------------- Jamalpur Vinay "Rate Based Real-Time Scheduling for General Processor Sharing Systems" The References that I have taken are: 1. Tei-Wei Kuo,Wang-Ru Yang, Kwei-Jay Lin,"A Class of Rate-Based Real-Time Scheduling Algorithms". 2. C-W. Hsueh and K.-J. Lin, "On-Line Schedulers for Pinwheel Tasks Using the Time-Driven Approach, Proc. 10th Euromicro Real-Time Systems, pp. 180-187, June 1998. ------------------------------------------------------- Kasiviswanathan Muthu 'Real-time Adaptive Scheduling using Milestones' Ref: Adaptable Scheduler using Milestons for hard real-time systems, Celio Estevan Moron and Hussein Zedan, University of York, UK. What I m going to do is implementing that in vxWorks. ------------------------------------------------------- Khare Mayuresh V Topic: "Efficiency Improvement by Anomaly Detection in (Real Time)- Rule Based Systems" References: Papers: 1)Methods of verifying expert system knowledge bases - Alun Preece. 2)Optimization of Rule Based Systems using State Space Graphs - A.M.K. Cheng and Blaz Zupan. 3)Informed Selection of Training Examples for Knowledge Refinement - Nirmalie Wiratunga and Susan Craw. 4)Verifying Rule Based Systems - Rajjan Singhal et al. Websites: 1)http://www.csd.abdn.ac.uk/~apreece/Research/KRAFT.html 2)http://www.csd.abdn.ac.uk/~apreece/Pubs/kbsj99a.html [COVER tool.] 3)http://www.econ.kuleuven.ac.be/tew/academic/infosys/members/vthienen /pub/eurovav/eurovav.doc *if time permits, I will show an illustration of the "Jess" Expert Shell. ------------------------------------------------------- 11/18 Kulkarni Maithili P "Application of BDD to a real world Problem" References are as under: 1) [Bry92] Randal E. Bryant. Symbolic Boolean manipulation with ordered binary­decision diagrams. ACM Computing Surveys, 24(3):293--318, September 1992. 2)M. Fujita, H. Fujisawa, N. Kawato. "Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams", In Proceedings of the IEEE International Conference on Computer-Aided Design, 1988. 3)K. Brace, R. Rudell, and R. Bryant, Efficient Implementation of a BDD Package, Proc. Design Automation Conf., pp. 40-45, June 1990. ------------------------------------------------------- Kulkarni Santosh A "Fast Best-Effort Real-Time Scheduling Algorithms" Peng Li and Binoy Ravindran. The paper discussed about two real time algorithms "MDASA" and "MLBESA" which are modifications of "DASA" and "LBESA" scheduling algorithms respectively. MDASA stands for "Modified Dependent Activity Scheduling Algorithm" and MLBESA stands for "Modified Locke's Best Effort Scheduling Algorithm". ------------------------------------------------------- Kumar Shraddha "A Genetic Algorithm for Real-Time Multiprocessor Scheduling". References: 1. A Genetic Algorithm for Multiprocessor Scheduling - Edwin S.H. Hou, Nirwan Ansari and Hong Ren , IEEE Transactions on Parallel and Distributed Systems, Vol.5,No.2 , February 1994 2. Genetic-algorithm-based real-time scheduling with multiple goals - Jaewon Oh, Chisu Wu, The Journal of Systems and Software, October 2002 3. Scheduling Multiprocessor Tasks with Genetic Algorithms - Ricardo C. Correa,Afonso Ferreira and Pascal Rebreyend, IEEE Transactions on Parallel and Distributed Systems,Vol.10 ,No.8 , August 1999 ------------------------------------------------------- Mantri Mohit Topic: Performance Comparison and Analysis of Real-Time Operating Systems Abstract: For this I would look into two such freely available RTOSes - eCOS & RTLinux and compare & analyze the real-time attributes like timing latency, context-switch latency and interrupt latency of these OSes by means of a few simple applications. References: 1. Measuring the Real-Time Operating System Performance - Krzysztof M. Sacha Institute of Control and Computation Engineering, Warsaw University of Technology, Poland 2. Measuring Execution Time and Real-Time Performance - David B. Stewart Executive VP and Chief Technology Officer, Embedded Research Solutions, LLC. Columbia 3. Real-Time Performance of Standards based Commercial Operating Systems - K. Obenland. In Embedded Systems conference, San Francisco, April 2001. 4. eCOS website: http://ecos.sourceware.org 5. RTLinux website: http://www.fsmlabs.com/products/openrtlinux ------------------------------------------------------- 11/23 Lin Jian Shut-down techniques in power-aware scheduling ------------------------------------------------------- Wadwani Mamta Network simulation ------------------------------------------------------- Peter Sibin Q Security issues of RTOS ------------------------------------------------------- Pundole Faraidoon N "System Level Power Aware Design Techniques in Real Time Systems" by OSMAN S. UNSAL, MEMBER, IEEE, AND ISRAEL KOREN, FELLOW IEEE. December 18, 2002. I will perform a study of the paper and implement two power reduction techniques for the Texas Instruments MSC1200 Microcontroller on the evaluation board. The study will focus primarily on this family of chips and techniques. More References:- D. Singh and V. Tiwari, "Power challenges in the Internet world," in Cool Chips Tutorial, in conjunction with the 32nd Int. Symp. Microarchitecture, Nov. 1999, pp. 8-15. ------------------------------------------------------- Ghosh Parmav This project involves implementation of the scheduling algorithms that I am going to discuss. Title: Real-time scheduling of multimedia data retrieval to minimize buffer requirement. References: 1. Title paper 2. Real-Time Systems: Scheduling, Analysis, and Verification (Text Book) 3. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment 4. Disk scheduling in a multimedia I/O system 5. I/O issues in a multimedia system ------------------------------------------------------- 11/30 Rao Sahana ------------------------------------------------------- Song Yang Topic: "RAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks." Reference: [1] C. Lu, B. M. Blum, T. F. Abdelzaher, J. A. Stankovic, T. He, ^ÓRAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks^Ô the 8th IEEE Real-Time Systems Symposium, RTAS 2002, San Jose, California, September 25-27, 2002 [2] IETF Working Group on Mobile Ad Hoc Networks, http://www.ietf.org/html.charters/manet-charter.html. [3] Karp, B. and Kung, H.T., ^ÓGreedy Perimeter Stateless Routing for Wireless Networks,^Ô in Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August, 2000, pp. 243-254. [4] I. Aad and C. Castelluccia, ^ÓDifferentiation Mechanisms for IEEE 802.11,^Ô IEEE INFOCOM 2001, Anchorage, Alaska, April 2001. 1044-1056. [5] J. Broch, D. A. Maltz, D. B. Johnson, Y. Hu, and J. M. Gerla. "GloMoSim: A Scalable Network Simulation Environment," UCLA Computer Science Department Technical Report 990027, May 1999. QuaNet Network Simulator. ------------------------------------------------------- Srinivas Rao Deepa "Dual-Priority Scheduling for Weakly-Hard Real Time Systems" In this project I have: Made a detailed study into the Specification, Implementation and Analysis of Weakly-Hard Real Time Systems. I have also implemented Dual-Priority Scheduler and EDF scheduler for weakly-hard systems and also made a performance analysis of the same. Lastly, I have explained a suggested improvement by using Bi-Modal Scheduler which is more suitable to schedule tasks that are weakly-hard along with systems that may have hard tasks. Some of my References are: 1) Bernat G., Cayssials R., "Guaranteed On-Line Weekly-Hard Real Time Systems", Proceedings of IEEE conference on real-time systems, 2001 2)Bernat G., Burns A., "Weakly hard real-time systems", IEEE Transactions on Computers, 2001 3)Bernat G., "Specification & Analysis of Weakly Hard real time systems", PhD thesis, Universitat de les Illes Balears, Spain, 1998 4)Davis R., Wellings A., "Dual Priority Scheduling", Proceedings of 16th Real-time Systems Symposium, 1995 ------------------------------------------------------- Sunkaraneni Sudheer "Robust Aperiodic Scheduling in Dynamic Priority Systems". Some of the references I've chosen are : 1)"Robust Aperiodic Scheduling under Dynamic Piority Systems" by Marco Spuri,Giorgio Buttazzo,fabrizio Sensini. 2)J. Blazewicz, ^ÓScheduling dependent tasks with different arrival times to meet deadlines,^Ô In E. Gelenbe, H. Beilner (eds), Modelling and Performance Evaluation of ComputerSystems. 3)"Robust Bandwidth Allocation Stratergies" by Oliver Heckman,Jens Schmitt,Ralf Steinmetz. 4)Reducing delay with Dynamic Priority RED Queues(DPRQ) by Peter Dimopoulos,Panlop Zeephongsekul,Zahir Tari. ------------------------------------------------------- Thomas Justin R Title: Real time behavior-based obstacle avoidance for fast mobile robots in a simulated environment Abstract: I intend to implement a real-time robotic control system for fast moving mobile robots in a unknown environment using reactive/behavior-based techniques. Due to the lack of real robotics hardware capable of high-speeds, I will be using the player/stage simulation environment for mobile robotics (http://playerstage.sourceforge.net) References: Fast mobile robots in ill-structured environments Zapata, R.; Perrier, M.; Lepinary, P.; Thompson, P.; Jouvencel, B.; Intelligent Robots and Systems '91. 'Intelligence for Mechanical Systems, Proceedings IROS '91. IEEE/RSJ International Workshop on , 3-5 Nov. 1991 Slack, M. 1990. "Situationally Driven Local Navigation for Mobile Robots," JPL Publication No. 90-17, NASA Jet Propulsion Laboratory, Pasadena, CA, April. Arkin, Ronald C., Behavior-based Robotics, Intelligent Robots and Autonomous Agents Series, 1998 Brian Gerkey, Richard T. Vaughan and Andrew Howard. "The Player/Stage Project: Tools for Multi-Robot and Distributed Sensor Systems" Proceedings of the 11th International Conference on Advanced Robotics, pages 317-323, Coimbra, Portugal, June 2003 ------------------------------------------------------- Mohammed Abdul M "REAL TIME TRANSACTION SCHEDULING:A COST CONSCIOUS APPROACH" ------------------------------------------------------- 12/2 Wang Yan Power-saving ------------------------------------------------------- Muqsith Mohammed A ------------------------------------------------------- Rao Sahana ------------------------------------------------------- Dr. Albert Cheng Research outlook Teaching Evaluation Homework written part due in class 12/2 Program part due midnight 12/2 Project report due 12/8 -------------------------------------------------------