Abstract
The Maximum Parsimony problem aims at reconstructing a phylogenetic tree from DNA,
RNA or protein sequences while minimizing the number of evolutionary changes. Much
work has been devoted by the Computer Science community to solve this NP-complete prob-
lem and many techniques have been used or designed in order to decrease the computation
time necessary to obtain an acceptable solution. In this paper we report an improvement of the
evaluation of the Fitch function for Maximum Parsimony using AVX2 assembler instruction
of Intel
TM
processors.
1 Introduction
This report is an extension of the technical report TR20080428-1 by the same author. We give here a new
version of the assembler code and we have performed some tests on an Intel Haswell processor to verify if
the AVX2 assembler instruction set gave any improvement over SSE2. For more details we refer the reader
to the technical report TR20080428-1.
1.1 Software improvement using AVX2 instructions
The release of the new Haswell architecture of Intel processor in June 2013 led to the introduction of
AVX2 (Advanced Vector Extensions, version 2) assembler instructions. With AVX, introduced in 2008, the
width of the SIMD registers is increased from 128 bits to 256 bits and the SSE registers xmm0-xmm15 are
renamed to ymm0-ymm15 for a 64 bits architecture.
AVX2 extensions like SSE2 (Streaming SIMD Extensions) instructions of modern x86 processors (Intel,
AMD) help vectorize the code, i.e. apply the same instruction on multiple data at the same time conse-
quently reducing the overall execution time.
In our implementation of phylogenetic reconstruction with Maximum Parsimony using Fitch criterion,
the main function that benefits from the use of vectorization is the computation of a hypothetical parsimony
sequence from two existing sequences. The C code of this function is given figure 1 and takes as input two
sequences x and y of a given size. The outputs are the hypothetical taxon z and the number of changes
(or differences) returned by the function.
1 int fitch(char x[], char y[], char z[], int size) {
2 int i, changes=0;
3 for (i = 0; i < length; ++i) {
4 z[i] = x[i] & y[i];
5 if (z[i] == 0) {
6 ++changes;
7 z[i] = x[i] | y[i];
8 }
9 }
10 return changes;
11 }
Figure 1: Fitch Parsimony function
Modern compiler (gcc GNU, icc Intel) are not able to vectorize the code of this function efficiently if
no implementation specific information is provided. It is then necessary to code the function in assembler
to get a significant improvement during the execution of the program.
The implementation with AVX2 is nearly the same as the one given in report TR20080428-1 for SSE2:
1. we first load into registers ymm0 and ymm1 the first 32 bytes of each taxon (x and y)
2. in ymm2 and ymm3, we respectively compute the binary-AND and the binary-OR of ymm0 and
ymm1 using instructions vpand and vpor (for parallel AND and parallel OR).
2
