Fall 2008 Presentations *********************************************** Note: Each presentation is around 15 minutes. Everyone is expected to attend and ask questions. A discussion follows each set of talks. Write a short review (a paragraph) of each talk for submission with your hardcopy project report (also email me an e-version) on 12/4/2008. Hard deadline: Friday, December 12, 2008, 5:00pm. If I am not in my office, slide hardcopy report under my office door. Please email me your topic and referenced paper(s)' titles one week before your presentation. *********************************************** 11/18 Kesiraju,Subba Rao --------------------------------------------------------------------------- Kambhampati,Srikanth Leela Venkata Energy aware scheduling of Real Time tasks upon HetErogenous Mutliprocessors. References: 1.Energy-aware implementation of hard real-time systems upon multiprocessor systems. James H.Andreson, Sanjoy K.Baruah 2. Implementing hard real time transactions on multiprocessors. James H.Andreson, Rohith Jain, Srikanth Ramamurthy 3. Dynamic and Aggressive Scheduling Techniques for Power-Aware Real Time Systems Hakan Aydin, Rami Melhem, Danie Mosse, Pedro Mejia-Alvarez --------------------------------------------------------------------------- Team: Gottipati,Sameer Kumar Gupta,Abhilasha " Applying Ant Colony Optimization (ACO) to the partitioned scheduled problem of heterogeneous multi processors"  Please guide us towards the success of this project. The papers we referenced are 1. Marco Dorigo , Thomas Stü Ant Colony Optimization, Bradford Book, 2004 2. J. Levine and F. Ducatelle, Ant Colony Optimisation and Local Search for Bin Packing and Cutting Stock Problems, Journal of the Operational Research Society (forthcoming), 2003. 3. Sanjoy K. Baruah, Partitioning Real-Time Tasks among Heterogeneous Multiprocessors, Proceedings of the 2004 International Conference on Parallel Processing (ICPP'04), p.467-474, August 15-18, 2004 4. Tracy D. Braun , Howard Jay Siegel , Noah Beck , Lasislau L. Böi , Muthucumara Maheswaran , Albert I. Reuther , James P. Robertson , Mitchell D. Theys , Bin Yao , Debra Hensgen , Richard F. Freund, A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, Journal of Parallel and Distributed Computing, v.61 n.6, p.810-837, June 2001 --------------------------------------------------------------------------- 11/20 Team: Koritala,Naga Chandana Kulkarni,Chaitali Laxman Kulkarni,Nupur P Cibermouse RTSS 08 competition --------------------------------------------------------------------------- Mangipudi,Aditya Tradeoff between Security and Packet Schedulability in Real-Time Networks - Authentication using Zero Knowledge Proof Most of the current approaches analyzing the stability of networked control systems consider delays and packet losses arising from queuing and congestion in the network. They do not consider the presence of a malicious adversary that is intentionally disrupting the network communications to create system instabilities. I intend to present a situation where the network will be provided with security and in the same time, all the packets meet their deadline. Worst case scenario being omission of few packets. I will try to find out the extent of loss for a tightly congested network with the introduction of security constraint. The idea behind the implementation of Zero Knowledge Proof is due to the fact that it is Simple and will provide less Overhead compared to many public key encryption algorithms as it uses just few Mathematical functions. Using Zero Knowledge Proof also nullifies the Man-In-The-Middle Attack which is the most sought improvement (needed) in the Real Time Networks today. Papers read (cause of motivation): 1) Krishna Sampigethaya, Radha Poovendran, and Linda Bushnell, Security of Future eEnabled Aircraft Ad hoc Networks, 8th AIAA Aviation Technology, Integration, and Operations (AIAA ATIO) Conference, September 2008. 2) Radha Poovendran, Krishna Sampigethaya, Linda Bushnell, Mingyan Li, Richard Robinson, Scott Lintelman, Security of Wireless Sensor Network Enabled Health Monitoring for Commercial Airplanes, 26th Congress of the International Council for Aeronautical Sciences (AIAA ICAS), September 2008. 3) Scheduling Security-Critical Real-Time Applications on Clusters -Tao Xie and Xiao Qin , EEE Computer Society Washington, DC, USA 4) W.A. Halang et al., "Measuring the Performance of Real-Time Systems," Int'l J. Time-Critical Computing Systems, vol. 18, pp. 59-68, 2000 And few papers on Zero Knowledge Proof System --------------------------------------------------------------------------- Team: Gunti,Vivek Rahul Juluri,Vishal Project Title : Real-Time Communication between Avionic Systems --------------------------------------------------------------------------- Hemrajani,Samira Ishwar Research directions given in section 7 of: 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/25 Team: Metry,Alex Albert Paramatmuni,Neelima WCET Techniques(Worst-Case Execution time analysis) and below are our references.   The references: 1. Worst-Case Execution time analysis for dynamic branch predictors by Iain Bate and Ralph Reuteman 2. New Directions in Worst-Case Execution Time Analysis by Iain Bate and Dimitar Kazakov 3. Portable Worst-Case Execution time analysis using java byte code by Guillem Bernat, Alan Burns and Andy Wellings 4. Loop Bound Analysis based on a combination of program slicing abstract interpretation and invariant analysis by Andreas Ermebahl, Christer Sand Berg 5. Making Worst-Case Execution Time analysis for hard Real-Time Tasks on state of the art processor feasible by Stefan M. Petters and Georg Farber 6. Applying Static WCET analysis to automotive communication software by Susanna Byhlin, Andreas Ermebahl, Jan Gustafsson --------------------------------------------------------------------------- Mathur,Aakash Raj ACO/Local Search --------------------------------------------------------------------------- Team: Matti,Rajani Rao Cherukupalli,Snigdha Improving the QoS by utilizing the excess network bandwidth using TCP-LP Distributed algorithm REFERENCES: 1. Kuzmanovic, A. and  Knightly, E.W. (2006) 'TCP-LP: low-priority service via end-point congestion control', EEE/ACM Transaction on Networking , Vol .14.No.4,August 2006 2.  Kuzmanovic, A. and Knightly, E. (2003) 'TCP-LP: A distributed algorithm for low priority data transfer', in Proc. IEEE INFOCOM, San Francisco, CA, pp. 1691-1701. 3.  Yang, S. and De Veciana, G. (2002) 'Size-based adaptive bandwidth allocation: Optimizing the average QoS for elastic flows', in Proc. IEEE INFOCOM '02, New York. 4. Cai, L., Xuemin Shen , Jianping  Pan, Mark, And  J.W. 'Performance analysis of TCP-friendly AIMD algorithms for multimedia applications'   IEEE Transactions  on  Multimedia , VOL. 7, NO. 2, APRIL 2005 --------------------------------------------------------------------------- Mohammed Abdul,Waheed "Scheduling Multi-Task Systems with improved Co-Synthesis of Hardware and Software" References: (i) "Enforcing Schedulability of Multi-Task Systems by Hardware-Software Codesign"  by Youngsoo Shin, Kiyoung Choi. (ii) "Hardware-Software Co-Synthesis of Distributed Embedded Systems" by T.Yen, W.Wolf. (iii) "Effective Analysis for engineering real-time fixed priority Schedulers" by A.Burns, K.Tindell and A.Wellings. --------------------------------------------------------------------------- 12/2 Team: Amraji,Nitish Mohammed,Javed Ahmed "Power-Awar Computing" 'A Dynamic-Mode Dynamic Voltage Scaling Algorithm under Dynamic Workloads'. The References we used are Y. Wang and A. M. K. Cheng, ``A Dynamic-Mode DVS Algorithm under Dynamic Workloads,'' Proc. IEEE-CS Real-Time and Embedded Technology and Applications Symposium WIP Session, San Francisco, March 2005.   -   Hong, I.; Potkonjak, M.; Srivastava, M.B. Computer-Aided Design, 1998. ICCAD 98. On-line scheduling of hard real-time tasks on variable voltage processor. Issue 8-12 Nov 1998.   -  T.Ishihara and H. Yasuura, "Voltage Scheduling Problem for Dynamically Variable Voltage Processors". --------------------------------------------------------------------------- Team: Kandiraju,Vijay Anand Pannala,Harisha Ramreddygari,Dineshreddy Topic: implementation of Hybrid priority scheduling comarision with an existing scheduling algorithm Paper by: Sanjoy Baruah & Narthan Fisher --------------------------------------------------------------------------- Team: Amujala,Sai Charan Chavali,Arun We are planning to implement an internet congestion avoidance mechanism called the "Network Border Patrol (NBP)". It is published in the following paper: Céo Albuquerque, Tatsuya Suda and Brett Vickers, "Network Border Patrol", to appear at IEEE Infocom 2000, Tel Aviv, Israel, March 2000. The basic overview of the paper is as follows. NBP is a core-stateless congestion avoidance mechanism which relies on the exchange of feedback between routers at the borders of a network in order to detect and restrict unresponsive traffic flows before they enter the network. Simulation results show that NBP effectively eliminates congestion collapse, and that, when combined with fair queueing, NBP achieves approximately max-min fair bandwidth allocations for competing network flows. References: ? Céo Albuquerque, Tatsuya Suda and Brett Vickers, "Network Border Patrol", to appear at IEEE Infocom 2000, Tel Aviv, Israel, March 2000. ? Céo Albuquerque, Tatsuya Suda and Brett Vickers, "Fair Queuing with Feedback-Based Policing: Promoting Fairness and Preventing Congestion Collapse in the Internet", UCI-ICS Technical Report 99-26, University of California, Irvine, USA, June 1999. [ICS-TR-99-26]. --------------------------------------------------------------------------- Team: Konatham,Rajesh Kumar Reddy Lagadapati,Ganesh Vinay Kumar Realtime Scheduling of tasks having response time constraints along with the deadlines. --------------------------------------------------------------------------- 12/4 Lee,Youngmi "efficient(tuning) garbage collection in real-time systems to guarantee deadline". reference paper : "Garbage Collection for Safety Critical Java" - Martin Schoeberl, Jan Vitek(07) "Hierarchical Real-time garbage collection" - Filip Pizlo, Anthony L. Hosking, Jan Vitek(07) "Real-time Garbage Collection" - David F. Bacon(07) "real-time garbage collection to reduce power consumption in Java". "3D GC: Towards a Garbage Collector that Considers Time, Space, and Energy" Lewis and Cheng --------------------------------------------------------------------------- Vantair,Sidharth Memory Access Latency in Embedded Multithreaded Processors. ABSTRACT Multithreading refers to the process of switching to an alternate task when an active task is blocked by an event such as a memory request rather than waiting for the stalled task to complete. Multithreading increases the throughput of the system. However there is a problem like the widening of processor-memory speed gap which limits throughput in embedded hard real time systems. The normal procedure for ensuring whether the given task set meets deadlines must be determined by offline scheduling algorithms apriori. This ensures safety of the hard real time system. In the method expressed here a schedulability test is derived that depends on memory components of tasks and aggregate computation which bounds the intersection between computation of an active task and ongoing memory requests of other tasks. The advantage of this method is that it avoids exploring all task variations for a feasible schedule and does not require the specific locality of memory requests. This method helps to make use of embedded processors despite the widening of the processor-memory gap. REFERENCES " C. Liu and J. Layland. Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment. Journal of ACM, vol. 20, pp. 46-61, January 1973 " T. Ungerer, B. Robic, and J. Silc. A Survey of Processors with Explicit Multithreading. ACM Computing Surveys,Vol. 35, No. 1, March 2003 " www.tinker.ncsu.edu/ericro/ talks/conference_CASES-2004.pdf " ARM, Inc. ARM-11 Technical Reference Manual. Available from: http://www.arm.com/pdfs/DDI0211D_arm1136_r0p2_trm.pdf " http://arstechnica.com/articles/paedia/cpu/ --------------------------------------------------------------------------- Team: Shetye,Apurva Venkatachalam,Alamu Title: Analysis of Worst Case Execution time based on program slicing, invariant analysis, abstract interpretation and dynamic branch prediction. We will analyze the pros and cons of each and propose a new technique having the pros of each of the techniques. We will also looking for some implementation. The papers that we are referring to are as follows: 1) Worst-Case Execution Time Analysis for Dynamic Branch Predictors: Iain Bate and Ralf Reutemann 2) Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis: Andreas Ermedahl, Christer Sandberg, Jan Gustafsson, Stefan Bygde, and Bj¨orn Lisper --------------------------------------------------------------------------- Team: Mylavarapu,Praveen Sameer Krishna Yalamanchili,Suresh Topic: Translating Real-Time UML to Real-Time Logic References: 1. A real-time profile for UML Susanne Graf, Ileana Ober and Iulian Ober 2. Translating Real-Time UML Timing Constraints into Real-Time Logic Formulas Gowri Aruchamy and Albert Mo Kim Cheng --------------------------------------------------------------------------- Mannepalli,Kartheek "Time slot allocation for real-time messages with negotiable distance constraints" libin dong, rami melhem, daniel mosse.