Systems Research and Architecture System und Rechnerarchitektur SRA
a SRA Theses Sparse Data Segment

Effizientes Laden dünn besetzter Datenstrukturen auf eingebetteten Systemen

During static generation and instantiation of operating-system objects, as it is done in the context of the AHA-Project, data structures tend to migrate from the .bss segment into the .data segment, as the compiler is able to deduce the values from static code analysis of the generated code. Without specialization, operating systems would have instantiated and computed their values at run-time. The specialization allows to eliminate this run-time computations and allow the compiler to reason about this values. Therefore, the structures get initialized at compile. Overall, this is a beneficial result of the static generation. However, there exist data structures consisting mostly of zeros. In such cases it might be beneficial not to copy the whole data (mostly zeros) from flash to ram, but instead copy just the non-zero values and blindly write the remaining zeros without reading from flash. This should result in lower start-up time since writing zeros is much cheaper than reading each zero from flash and write it back to ram.

The goal of this thesis is to define a specification how to represent sparse data in an elf file and develop a LLVM optimization pass which is able to detect whether a symbol in the data section mostly contains zeros, mark it as special, according to the aforementioned specification, and introduce the needed logic into the elf to copy the non-zero values after zero initializing the surrounding region. Additionally, it is target of the thesis to evaluate the benefits of the resulting variations and to compare their properties to the default implementation. This includes, but is not limited to, the analysis of image size, compile time and startup time. Finally, a comparative evaluation against other alternatives results in a sound evaluation of the approach.

tl;dr: Implement and evaluate sparse data sections for C structs containing mostly zeros

Further Reading

OSPERT Workshop B
ARA: Automatic Instance-Level Analysis in Real-Time Systems
Gerion Entrup, Benedikt Steinmeier, Christian DietrichProceedings of the 15th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT '19)2019.
PDF [BibTex]
OSPERT Workshop B Best Paper Award
Levels of Specialization in Real-Time Operating Systems
Björn Fiedler, Gerion Entrup, Christian Dietrich, Daniel LohmannProceedings of the 14th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT '18)2018Best Paper Award.
PDF [BibTex]
TECS Journal A
Global Optimization of Fixed-Priority Real-Time Systems by RTOS-Aware Control-Flow Analysis
Christian Dietrich, Martin Hoffmann, Daniel LohmannACM Transactions on Embedded Computing Systems16.2ACM Press2017.
PDF Raw Data 10.1145/2950053 [BibTex]
LLVM website: http://llvm.org/
LLVM passes: https://llvm.org/docs/Passes.html
Writing an LLVM Pass: http://releases.llvm.org/9.0.0/docs/WritingAnLLVMPass.html