Integration of new SIMD-Features into the Android Dalvik VM

Student:Christian Cardello
Title:Integration of new SIMD-Features into the Android Dalvik VM
Type:bachelor thesis
Advisors:Dotzler, G.; Veldema, R.; Philippsen, M.
State:submitted on October 2, 2014
Prerequisits:
Topic:

Background

To use modern CPUs to their full potential, it is necessary to program parallel code for all cores and to use the vector processing units (VPUs). VPUs have specialized instructions that can operate on small arrays of int/float/double types. For example, instructions exist that multiply two 3 element float arrays and write the result to a third 3 element float array. Unfortunately, automatic vectorization and parallelization is complicated and a lot of techniques are only implemented in research projects. To make use of the processor's vector unit(s), the programmer will therefore need to help the VM explicitly. Currently this is done by exposing C libraries upwards, bypassing the VM.

Topic

The goal of this thesis is to give programmers access to the SIMD features of a VM. The first step of the thesis consists of analyzing the use of SIMD features in the Dalvik VM of Android. The collected data about SIMD handling should be used to extend the VM. In its first new version, the modified Dalvik VM should recognize special SIMD method calls and generate appropriate SIMD code.

For example:

for (i = 0; i < n; i++) {
..useSimd(length = 16)
..for (j = 0; j < n - 16; j++) {
....a[i][j] = a[i][j-16] + b[i][j];
....b[i][j] = b[i][j+16] + a[i][j];
..}
}

The useSimd(...) in the example should inform the Dalvik VM to generate SIMD code. As the alignment of the arrays has a huge influence on the performance of the generated the next milestone of the work should take alignment into account. This should be accomplished by code analysis inside the VM and/or by adding special calls to the source code which enforce the correct alignment of the arrays. In the next milestone the special method calls should be replaced by comments to make the code executable on standard Dalvik VMs. To achieve that it is necessary to change the Dalvik Compiler. Finally the performance of the new SIMD features should be measured with standard benchmarks.

Milestones

  • Evaluation of SIMD instruction use in the Dalvik VM
  • Implementation of enforced SIMD use in the VM
  • Implementation of array alignment options in the VM/Dalvik Compiler
  • Modification of the Dalvik Compiler to support special comments
  • Benchmarking of the new features
  • Thesis

Literature

watermark seal