Sungjun Kim
|
|
|
| Candidacy Exam: Syllabus |
|
|
|
Designing Time-Predictable Computer Architecture for Hard Real-Time Systems Sungjun Kim Department of Computer Science Columbia University, New York, NY 10027 skim@cs.columbia.edu CS Conference Room, 2:00 PM, December 13, 2010 Comittee: Prof. Stephen A. Edwards, Prof. Luca P. Carloni, Prof. Martha A. Kim |
|
|
|
Motivation: |
|
- John A. Stankovic. Misconceptions about real-time computing: A serious problem for next-generation systems. Computer, 21(10):10-19, 1988. |
|
- Edward A. Lee. Computing needs time. Commun. ACM, 52(5):70-79, 2009. |
|
|
|
Hard Real-Time Scheduling: |
|
- C. L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM, 20(1):46-61, 1973. |
|
- Lui Sha, Tarek Abdelzaher, Karl-Erik Arzen, Anton Cervin, Theodore Baker, Alan Burns, Giorgio Buttazzo, Marco Caccamo, John Lehoczky, and Aloysius K. Mok. Real time scheduling theory: A historical perspective. Real-Time Systems, 28:101-155, 2004. 10.1023/B:TIME.0000045315.61234.1e. |
|
|
|
Worst-Case Execution Time (WCET) Analysis: |
|
- Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, and Per Stenström. The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst., 7(3):1-53, 2008. |
|
|
|
Hard Real-Time Computer Architectures: |
- Jan Reineke, Björn Wachter, Stephan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. A definition and classification of timing anomalies. In Proceedings of 6th International Workshop on Worst-Case Execution Time (WCET) Analysis, July 2006. |
|
- Reinhard Wilhelm, Daniel Grund, Jan Reineke, Marc Schlickling, Markus Pister, and Christian Ferdinand. Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. Trans. Comp.-Aided Des. Integ. Cir. Sys., 28(7):966-978, 2009. |
|
- Martin Schoeberl. Time-predictable computer architecture. EURASIP J. Embedded Syst., 2009:2:1-2:17, January 2009. |
|
|
|
Scratch Pad Memory Allocation: |
|
- Rajeshwari Banakar, Stefan Steinke, Bo-Sik Lee, M. Balakrishnan, and Peter Marwedel. Scratchpad memory: design alternative for cache on-chip memory in embedded systems. In Proceedings of the tenth international symposium on Hardware/software codesign, pages 73-78, 2002. |
|
- Oren Avissar, Rajeev Barua, and Dave Stewart. An optimal memory allocation scheme for scratch-pad-based embedded systems. ACM Trans. Embed. Comput. Syst., 1:6-26, November 2002. |
|
- V. Suhendra, T. Mitra, A. Roychoudhury, and Ting Chen. WCET centric data allocation to scratchpad memory. Real-Time Systems Symposium. RTSS. 26th IEEE International, pages 10 pp. -232, dec. 2005. |
|
|
|
Structure and Scheduling Algorithms of DRAM: |
|
- Bruce Jacob, Spencer Ng, and David Wang. Overview of DRAMs. In Memory Systems: Cache, DRAM, Disk, pages 315-351, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc. |
|
- Scott Rixner, William J. Dally, Ujval J. Kapasi, Peter R. Mattson, and John D. Owens. Memory access scheduling. In ISCA, pages 128-138, 2000. |
|
- Onur Mutlu and Thomas Moscibroda. Parallelism-aware batch scheduling: Enhancing both performance and fairness of shared DRAM systems. SIGARCH Comput. Archit. News, 36:63-74, June 2008. |
|
- Benny Akesson, Kees Goossens, and Markus Ringhofer. Predator: a predictable SDRAM memory controller. In CODES+ISSS '07, pages 251-256, 2007. |
|
|
|
Structure and Scheduling Algorithms of Disk: |
|
- Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne. Overview of mass-storage structure and disk structure. In Operating System Concepts, pages 505-508. Wiley Publishing, 2008. |
|
- Margo Seltzer, Peter Chen, and John Ousterhout. Disk scheduling revisited. In Proceedings of the Winter 1990 USENIX Technical Conference, pages 313-324, 1990. |
|
- L. Reuther and M. Pohlack. Rotational-position-aware real-time disk scheduling using a dynamic active subset (DAS). In Real-Time Systems Symposium, 2003. RTSS 2003. 24th IEEE, pages 374-385, 2003. |
|
|
|
Real-Time Bus Protocols: |
|
- Robert Davis, Alan Burns, Reinder Bril, and Johan Lukkien. Controller area network (CAN) schedulability analysis: Refuted, revisited and revised. Real-Time Systems, 35:239-272, 2007. 10.1007/s11241-007-9012-7. |
|
- H. Kopetz and G. Grunsteidl. TTP - a time-triggered protocol for fault-tolerant real-time systems. Fault-Tolerant Computing, 1993. FTCS-23. Digest of Papers., pages 524-533, jun. 1993. |
|
|
|
|