Handling of Inter-Thread Memory Access Dependencies for Automatic Binary-Code Parallelization

Kanemitsu Ootsu, Takashi Shiroto, Takashi Yokota, and Takanobu Baba


speculative multithreading, automatic parallelization, binary translation, memory access analysis


Now the multi-core processors are widely available everywhere, and the speedup with thread-level parallelization of sequential programs becomes quite important. In general, thread-level parallelization are performed using the source code of the target program, but the source code are not always available. In order to realize the parallelization of existing sequential programs without need of the source codes, we have developed the software system that can automatically parallelize the executable binary codes of the programs at thread level, with binary translation.For thread-level parallelization, it is necessary to correctly analyze the data dependencies of variablesbetween threads. However, since the memory accesses for the reference of variables are performed by specifying the target addresses using the registers and the values of the registers are generally unknown until execution, it is not easy to identify the variables located on memory and to examine the data dependencies. This paper discusses the analysis for the data dependencies of variables located on memory and the thread-level parallel processing based on the analysis results, in our automatic thread-level parallelization system by binary translation. The binary-level variable analysis statically analyzes and identifies the variables on memory in order to examine the data dependencies between threads. This is the method for identifying the variable by comparing the calculation trees that represent the target addresses of variables. And the runtime inspection of memory access dependencies hardware guarantees the correct parallel execution for the parallelized binary code containing data dependencies that cannot statically determined.

Important Links:

Go Back