Navigation

Jan Reineke

About Me

I have moved to UC Berkeley. My new website can be found at http://www.eecs.berkeley.edu/~reineke.

Previously, I studied computer science in Oldenburg and Saarbrücken, receiving a Bachelor's degree from the University of Oldenburg in 2003 and a Master's from Saarland University in 2005. From 2005 to 2009, I was a PhD student and later a PostDoc under the supervision of Reinhard Wilhelm. In late 2008, I defended my PhD thesis on "Caches in WCET Analysis". Check out my defense talk below!

Research Interests

Caches, their analysis and predictability
Timing predictability
Topology and shape analysis by abstract interpretation

Relacs - Automatic Relative Competitive Analysis

Check out Relacs a tool for relative competitive and sensitivity analysis!

Publications

Journal Papers

Branch Target Buffers: WCET Analysis Framework and Timing Predictability
D. Grund, J. Reineke, and G. Gebhard
Journal of Systems Architecture, TODO, 2010. [doi] [pdf] [bib]

@ARTICLE{Grund10b,
   author = {Daniel Grund and Jan Reineke and Gernot Gebhard},
   title = {Branch Target Buffers: {WCET} Analysis Framework and Timing Predictability},
   journal = {Journal of Systems Architecture},
   year = {2010},
   volume = {TODO},
   doi = {10.1016/j.sysarc.2010.05.013},
   url = {http://rw4.cs.uni-saarland.de/~grund/papers/jsa10-BTBs.pdf}
 }

Memory Hierarchies, Pipelines, and Buses for Future Architectures in Time-critical Embedded Systems
R. Wilhelm, D. Grund, J. Reineke, M. Schlickling, M. Pister, and C. Ferdinand
IEEE Transactions on CAD of Integrated Circuits and Systems, 28 (7), 2009. [doi] [bib]

@ARTICLE{Wilhelm09,
   author = {Reinhard Wilhelm and Daniel Grund and Jan Reineke and Marc Schlickling and Markus Pister and Christian Ferdinand},
   title = {Memory Hierarchies, Pipelines, and Buses for Future Architectures in Time-critical Embedded Systems},
   journal = {IEEE Transactions on {CAD} of Integrated Circuits and Systems},
   year = {2009},
   volume = {28},
   pages = {966--978},
   number = {7},
   month = {July},
   doi = {10.1109/TCAD.2009.2013287}
 }

Timing Predictability of Cache Replacement Policies
J. Reineke, D. Grund, C. Berg, and R. Wilhelm
Real-Time Systems, 37 (2), 2007. [doi] [pdf] [bib]

@ARTICLE{Reineke07,
   author = {Jan Reineke and Daniel Grund and Christoph Berg and Reinhard Wilhelm},
   title = {Timing Predictability of Cache Replacement Policies},
   journal = {Real-Time Systems},
   year = {2007},
   volume = {37},
   pages = {99--122},
   number = {2},
   month = {November},
   doi = {10.1007/s11241-007-9032-3},
   url = {http://rw4.cs.uni-saarland.de/~grund/papers/rts07-predictability.pdf}
 }

Conference Papers

Static Timing Analysis for Hard Real-Time Systems
R. Wilhelm, S. Altmeyer, C. Burguière, D. Grund, J. Herter, J. Reineke, B. Wachter, and S. Wilhelm
VMCAI, 2010. [doi] [bib]

@INPROCEEDINGS{Wilhelm10,
   author = {Reinhard Wilhelm and Sebastian Altmeyer and Claire Burgui\`ere and Daniel Grund and J\"org Herter and Jan Reineke and Bj\"orn Wachter and Stephan Wilhelm},
   title = {Static Timing Analysis for Hard Real-Time Systems},
   booktitle = {VMCAI},
   year = {2010},
   pages = {3--22},
   publisher = {Springer Verlag},
   doi = {10.1007/978-3-642-11319-2_3}
 }

Resilience Analysis: Tightening the CRPD Bound for Set-Associative Caches
S. Altmeyer, C. Maiza, and J. Reineke
LCTES '10: Proceedings of the ACM SIGPLAN/SIGBED 2010 conference on Languages, compilers, and tools for embedded systems, 2010. [doi] [bib]

@INPROCEEDINGS{Altmeyer10,
   author = {Sebastian Altmeyer and Claire Maiza and Jan Reineke},
   title = {Resilience Analysis: Tightening the CRPD Bound for Set-Associative Caches},
   booktitle = {LCTES '10: Proceedings of the ACM SIGPLAN/SIGBED 2010 conference on Languages, compilers, and tools for embedded systems},
   year = {2010},
   pages = {153--162},
   address = {New York, NY, USA},
   month = {April},
   publisher = {ACM},
   doi = {10.1145/1755888.1755911},
   isbn = {978-1-60558-953-4},
   location = {Stockholm, Sweden}
 }

Predictability Considerations in the Design of Multi-Core Embedded Systems
C. Cullmann, C. Ferdinand, G. Gebhard, D. Grund, C. Maiza, J. Reineke, B. Triquet, and R. Wilhelm
Proceedings of Embedded Real Time Software and Systems, 2010. [bib]

@INPROCEEDINGS{Cullmann10,
   author = {Christoph Cullmann and Christian Ferdinand and Gernot Gebhard and Daniel Grund and Claire Maiza and Jan Reineke and Beno\^it Triquet and Reinhard Wilhelm},
   title = {Predictability Considerations in the Design of Multi-Core Embedded Systems},
   booktitle = {Proceedings of Embedded Real Time Software and Systems},
   year = {2010},
   month = {May},
 }

Precise and Efficient FIFO-Replacement Analysis Based on Static Phase Detection
D. Grund, and J. Reineke
Proceedings of the 22nd Euromicro Conference on Real-Time Systems (ECRTS '10), 2010. [pdf] [slides] [bib]

@INPROCEEDINGS{Grund10,
   author = {Daniel Grund and Jan Reineke},
   title = {Precise and Efficient {FIFO}-Replacement Analysis Based on Static Phase Detection},
   booktitle = {Proceedings of the 22nd Euromicro Conference on Real-Time Systems (ECRTS '10)},
   year = {2010},
   month = {July},
   slides = {http://rw4.cs.uni-saarland.de/~grund/talks/ecrts10-fifo.pdf},
   url = {http://rw4.cs.uni-saarland.de/~grund/papers/ecrts10-fifo_phases.pdf}
 }

Toward Precise PLRU Cache Analyis
D. Grund, and J. Reineke
Proceedings of 10th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2010. [pdf] [slides] [bib]

@INPROCEEDINGS{Grund10a,
   author = {Daniel Grund and Jan Reineke},
   title = {Toward Precise {PLRU} Cache Analyis},
   booktitle = {Proceedings of 10th International Workshop on Worst-Case Execution Time ({WCET}) Analysis},
   year = {2010},
   editor = {Bj\"orn Lisper},
   pages = {28--39},
   month = {July},
   publisher = {Austrian Computer Society},
   slides = {http://rw4.cs.uni-saarland.de/~grund/talks/wcet10-plru.pdf},
   url = {http://rw4.cs.uni-saarland.de/~grund/papers/wcet10-plru.pdf}
 }

A Graph Transformation Case Study for the Topology Analysis of Dynamic Communication System
P. Backes, and J. Reineke
Transformation Tool Contest 2010, 2010. [bib]

@INPROCEEDINGS{Backes10a,
   author = {Peter Backes and Jan Reineke},
   title = {A Graph Transformation Case Study for the Topology Analysis of Dynamic Communication System},
   booktitle = {Transformation Tool Contest 2010},
   year = {2010},
   volume = {WP10-03},
   series = {{CTIT} Workshop Proceedings},
   pages = {107--118},
   address = {Enschede},
   publisher = {University of Twente},
 }

Abstract Topology Analysis of the Join Phase of the Merge Protocol [using Astra]
P. Backes, and J. Reineke
Transformation Tool Contest 2010, 2010. [bib]

@INPROCEEDINGS{Backes10,
   author = {Peter Backes and Jan Reineke},
   title = {Abstract Topology Analysis of the Join Phase of the Merge Protocol [using Astra]},
   booktitle = {Transformation Tool Contest 2010},
   year = {2010},
   volume = {WP10-03},
   series = {{CTIT} Workshop Proceedings},
   pages = {127--133},
   address = {Enschede},
   publisher = {University of Twente},
 }

Abstract Interpretation of FIFO Replacement
D. Grund, and J. Reineke
Static Analysis, 16th International Symposium, SAS 2009, 2009. [doi] [pdf] [slides] [bib]

@INPROCEEDINGS{Grund09,
   author = {Daniel Grund and Jan Reineke},
   title = {Abstract Interpretation of {FIFO} Replacement},
   booktitle = {Static Analysis, 16th International Symposium, SAS 2009},
   year = {2009},
   editor = {Jens Palsberg and Zhendong Su},
   volume = {5673},
   series = {LNCS},
   pages = {120--136},
   month = {August},
   publisher = {Springer-Verlag},
   doi = {10.1007/978-3-642-03237-0},
   slides = {http://rw4.cs.uni-saarland.de/~grund/talks/sas09-fifo.pdf},
   url = {http://rw4.cs.uni-saarland.de/~grund/papers/sas09-AI_FIFO.pdf}
 }

Branch Target Buffers: WCET Analysis and Timing Predictability
D. Grund, J. Reineke, and G. Gebhard
15th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2009, 2009. [doi] [pdf] [slides] [bib]

@INPROCEEDINGS{Grund09a,
   author = {Daniel Grund and Jan Reineke and Gernot Gebhard},
   title = {Branch Target Buffers: {WCET} Analysis and Timing Predictability},
   booktitle = {15th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2009},
   year = {2009},
   month = {August},
   doi = {10.1109/RTCSA.2009.8},
   slides = {http://rw4.cs.uni-saarland.de/~grund/talks/rtcsa09-btb.pdf},
   url = {http://rw4.cs.uni-saarland.de/~grund/papers/rtcsa09-BTBs.pdf}
 }

Sound and Efficient WCET Analysis in Presence of Timing Anomalies
J. Reineke, and R. Sen
Proceedings of 9th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2009. [pdf] [bib]

@INPROCEEDINGS{Reineke09,
   author = {Jan Reineke and Rathijit Sen},
   title = {Sound and Efficient {WCET} Analysis in Presence of Timing Anomalies},
   booktitle = {Proceedings of 9th International Workshop on Worst-Case Execution Time ({WCET}) Analysis},
   year = {2009},
   month = {June},
   url = {http://rw4.cs.uni-saarland.de/~reineke/publications/TimingAnomaliesWCET09.pdf}
 }

Cache-Related Preemption Delay Computation for Set-Associative Caches—Pitfalls and Solutions
C. Burguière, J. Reineke, and S. Altmeyer
Proceedings of 9th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2009. [pdf] [bib]

@INPROCEEDINGS{Burgui`ere09,
   author = {Claire Burgui\`ere and Jan Reineke and Sebastian Altmeyer},
   title = {Cache-Related Preemption Delay Computation for Set-Associative Caches---Pitfalls and Solutions},
   booktitle = {Proceedings of 9th International Workshop on Worst-Case Execution Time ({WCET}) Analysis},
   year = {2009},
   month = {June},
   url = {http://drops.dagstuhl.de/opus/volltexte/2009/2285/pdf/Burguiere.2285.pdf}
 }

Making Dynamic Memory Allocation Static To Support WCET Analyses
J. Herter, and J. Reineke
Proceedings of 9th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2009. [bib]

@INPROCEEDINGS{Herter09,
   author = {J\"org Herter and Jan Reineke},
   title = {Making Dynamic Memory Allocation Static To Support {WCET} Analyses},
   booktitle = {Proceedings of 9th International Workshop on Worst-Case Execution Time ({WCET}) Analysis},
   year = {2009},
   month = {June},
 }

Polynomial Precise Interval Analysis Revisited
T. Gawlitza, J. Leroux, J. Reineke, H. Seidl, G. Sutre, and R. Wilhelm
Efficient Algorithms, 2009. [doi] [bib]

@INPROCEEDINGS{Gawlitza09,
   author = {Thomas Gawlitza and J\'er\^ome Leroux and Jan Reineke and Helmut Seidl and Gr\'egoire Sutre and Reinhard Wilhelm},
   title = {Polynomial Precise Interval Analysis Revisited},
   booktitle = {Efficient Algorithms},
   year = {2009},
   pages = {422--437},
   doi = {10.1007/978-3-642-03456-5_28}
 }

Designing Predictable Multicore Architectures for Avionics and Automotive Systems
R. Wilhelm, C. Ferdinand, C. Cullmann, D. Grund, J. Reineke, and B. Triquet
Workshop on Reconciling Performance with Predictability (RePP), 2009. [pdf] [bib]

@INPROCEEDINGS{Wilhelm09b,
   author = {Reinhard Wilhelm and Christian Ferdinand and Christoph Cullmann and Daniel Grund and Jan Reineke and Beno\^it Triquet},
   title = {Designing Predictable Multicore Architectures for Avionics and Automotive Systems},
   booktitle = {Workshop on Reconciling Performance with Predictability ({RePP})},
   year = {2009},
   month = {October},
   url = {http://www.tik.ee.ethz.ch/~jchen/RePP/papers/2-3.pdf}
 }

Estimating the Performance of Cache Replacement Policies
D. Grund, and J. Reineke
MEMOCODE '08: Proceedings of the 6th IEEE/ACM International Conference on Formal Methods and Models for Codesign, 2008. [doi] [pdf] [slides] [bib]

@INPROCEEDINGS{Grund08,
   author = {Daniel Grund and Jan Reineke},
   title = {Estimating the Performance of Cache Replacement Policies},
   booktitle = {MEMOCODE '08: Proceedings of the 6th IEEE/ACM International Conference on Formal Methods and Models for Codesign},
   year = {2008},
   pages = {101--111},
   month = {June},
   doi = {10.1109/MEMCOD.2008.4547695},
   slides = {http://rw4.cs.uni-saarland.de/~grund/talks/memocode08-policy_performance.pdf},
   url = {http://rw4.cs.uni-saarland.de/~grund/papers/memocode08-policy_performance.pdf}
 }

Relative Competitiveness of Cache Replacement Policies
J. Reineke, and D. Grund
SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 2008. [doi] [pdf] [bib]

@INPROCEEDINGS{Reineke08b,
   author = {Jan Reineke and Daniel Grund},
   title = {Relative Competitiveness of Cache Replacement Policies},
   booktitle = {SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems},
   year = {2008},
   pages = {431--432},
   address = {New York, NY, USA},
   month = {June},
   publisher = {ACM},
   doi = {10.1145/1375457.1375506},
   isbn = {978-1-60558-005-0},
   location = {Annapolis, MD, USA},
   url = {http://rw4.cs.uni-saarland.de/~grund/papers/sigmetrics08-rel_comp.pdf}
 }

Relative Competitive Analysis of Cache Replacement Policies
J. Reineke, and D. Grund
LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems, 2008. [doi] [pdf] [bib]

@INPROCEEDINGS{Reineke08c,
   author = {Jan Reineke and Daniel Grund},
   title = {Relative Competitive Analysis of Cache Replacement Policies},
   booktitle = {LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems},
   year = {2008},
   pages = {51--60},
   address = {New York, NY, USA},
   month = {June},
   publisher = {ACM},
   doi = {10.1145/1375657.1375665},
   isbn = {978-1-60558-104-0},
   location = {Tucson, AZ, USA},
   url = {http://rw4.cs.uni-saarland.de/~grund/papers/lctes08-rel_comp.pdf}
 }

CAMA: Cache-Aware Memory Allocation for WCET Analysis
J. Herter, J. Reineke, and R. Wilhelm
Proceedings Work-In-Progress Session of the 20th Euromicro Conference on Real-Time Systems, 2008. [pdf] [bib]

@INPROCEEDINGS{Herter08a,
   author = {J\"org Herter and Jan Reineke and Reinhard Wilhelm},
   title = {{CAMA}: Cache-Aware Memory Allocation for {WCET} Analysis},
   booktitle = {Proceedings Work-In-Progress Session of the 20th Euromicro Conference on Real-Time Systems},
   year = {2008},
   editor = {Marco Caccamo},
   pages = {24--27},
   month = {July},
   url = {http://rw4.cs.uni-saarland.de/~jherter/papers/camaecrts08.pdf}
 }

Shape Analysis of Sets
J. Reineke
Workshop Trustworthy Software 2006, 2006. [url] [bib]

@INPROCEEDINGS{Reineke06,
   author = {Jan Reineke},
   title = {Shape Analysis of Sets},
   booktitle = {Workshop Trustworthy Software 2006},
   year = {2006},
   editor = {Serge Autexier and Stephan Merz and Leon van der Torre and Reinhard Wilhelm and Pierre Wolper},
   address = {Dagstuhl, Germany},
   publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
 	(IBFI), Schloss Dagstuhl, Germany},
   url = {http://drops.dagstuhl.de/opus/volltexte/2006/698}
 }

A Definition and Classification of Timing Anomalies
J. Reineke, B. Wachter, S. Thesing, R. Wilhelm, I. Polian, J. Eisinger, and B. Becker
Proceedings of 6th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2006. [pdf] [bib]

@INPROCEEDINGS{Reineke06b,
   author = {Jan Reineke and Bj\"orn Wachter and Stephan Thesing and Reinhard Wilhelm and Ilia Polian and Jochen Eisinger and Bernd Becker},
   title = {A Definition and Classification of Timing Anomalies},
   booktitle = {Proceedings of 6th International Workshop on Worst-Case Execution Time ({WCET}) Analysis},
   year = {2006},
   month = {July},
   url = {http://rw4.cs.uni-saarland.de/~reineke/publications/TimingAnomaliesWCET06.pdf}
 }

PhD Theses

Caches in WCET Analysis
J. Reineke
Universität des Saarlandes, 2008. [bib]

@PHDTHESIS{Reineke08,
   author = {Jan Reineke},
   title = {Caches in {WCET} Analysis},
   school = {Universit\"at des Saarlandes},
   year = {2008},
   month = {November},
 }

MSc Theses

Shape Analysis of Sets
J. Reineke
Universität des Saarlandes, Germany, 2005. [pdf] [bib]

@MASTERSTHESIS{Reineke05,
   author = {Jan Reineke},
   title = {Shape Analysis of Sets},
   school = {Universit\"at des Saarlandes, Germany},
   year = {2005},
   month = {June},
   url = {http://rw4.cs.uni-saarland.de/~reineke/publications/MasterReineke.pdf}
 }

Technical Reports

Sensitivity of Cache Replacement Policies
J. Reineke, and D. Grund
Technical Report, SFB/TR 14 AVACS, 2008. [pdf] [bib]

@TECHREPORT{Reineke08a,
   author = {Jan Reineke and Daniel Grund},
   title = {Sensitivity of Cache Replacement Policies},
   institution = {SFB/TR 14 AVACS},
   year = {2008},
   type = {Reports of SFB/TR 14 AVACS},
   number = {36},
   month = {March},
   note = {ISSN: 1860-9821, http://www.avacs.org},
   access = {open},
   bibtex = {atr036.bib},
   editor = {Bernd Becker and Werner Damm and Martin Fr\"anzle and Ernst-R\"udiger Olderog and Andreas Podelski and Reinhard Wilhelm},
   series = {ATR},
   subproject = {R2},
   url = {http://www.avacs.org/Publikationen/Open/avacs_technical_report_036.pdf}
 }

Polynomial Precise Interval Analysis Revisited
T. Gawlitza, J. Reineke, H. Seidl, and R. Wilhelm
Technical Report, TU München, Germany, 2006. [bib]

@TECHREPORT{Gawlitza06,
   author = {Thomas Gawlitza and Jan Reineke and Helmut Seidl and Reinhard Wilhelm},
   title = {Polynomial Precise Interval Analysis Revisited},
   institution = {TU M\"unchen, Germany},
   year = {2006},
 }

Predictability of Cache Replacement Policies
J. Reineke, D. Grund, C. Berg, and R. Wilhelm
Technical Report, SFB/TR 14 AVACS, 2006. [pdf] [bib]

@TECHREPORT{Reineke06a,
   author = {Jan Reineke and Daniel Grund and Christoph Berg and Reinhard Wilhelm},
   title = {Predictability of Cache Replacement Policies},
   institution = {SFB/TR 14 AVACS},
   year = {2006},
   type = {Reports of SFB/TR 14 AVACS},
   number = {9},
   month = {September},
   note = {ISSN: 1860-9821, http://www.avacs.org},
   access = {open},
   bibtex = {atr009.bib},
   editor = {Bernd Becker and Werner Damm and Martin Fr\"anzle and Ernst-R\"udiger Olderog and Andreas Podelski and Reinhard Wilhelm},
   series = {ATR},
   subproject = {R2},
   url = {http://www.avacs.org/Publikationen/Open/avacs_technical_report_009.pdf}
 }

Selected Talks

Caches in WCET Analysis -- Predictability, Competitiveness, Sensitivity, PhD defense talk [ pdf ]
Relative Competitive Analysis of Cache Replacement Policies, at LCTES 2008 [ pdf ]
Timing Predictability of Cache Replacement Policies, at AVACS Virtual Seminar and Dagstuhl Seminar on Quantitative Aspects of Embedded Systems [ ppt ]
Shape Analysis of Sets, at Trustworthy Software Workshop, Tel Aviv University, etc. [ pdf ]
Timing Anomalies, at WCET'06 Workshop, AVACS Meeting Oldenburg, etc. [ ppt ]

Posters

Relative Competitiveness of Cache Replacement Policies [ pdf ]
CAMA: Cache-Aware Memory Allocation for WCET Analysis [ pdf ]

Teaching

Seminar "Modular Static Analysis", summer term 2007
Lecture "Compiler Construction", summer term 2006
Lecture "Parallel Programming", winter term 2005/2006

Supervised Theses

I supervised three excellent master students:

Jörg Herter: "Towards Shape Analysis of B-Trees"
Peter Backes: "Topology Analysis of Dynamic Communication Systems"
Kai Mittermüller: "Safety Analysis of Interrupts for Embedded Systems"

Professional Activities

PC Member: LCTES 2010, 2011
PC Member: MEMOCODE 2010

External Reviewer

SAS 10, ICCPS 10
WCET 09, SCOPES 09, LCTES 09
RTSS 08, WCET 08
PLDI 07, CC 07, LCPC 07
ESOP 06, SAS 06
VMCAI 05

Address

Jan Reineke
University of California, Berkeley
Dept. of EECS
545K Cory Hall
Berkeley, CA 94720-1770
USA

Mail: reineke (at) eecs (dot) berkeley (dot) edu

Compiler Design Lab