Efficiency of parallel direct optimization

Tremendous progress has been made at the level of sequential computation in phylogenetics. However, little attention has been paid to parallel computa tion. Parallel computing is particularly suited to phylogenetics because of the many ways large computational problems can be broken into parts that c an be analyzed concurrently. In this paper, we investigate the scaling fact ors and efficiency of random addition and tree refinement strategies using the direct optimization software, POY, on a small (10 slave processors) and a large (256 slave processors) cluster of networked PCs running LINUX. The se algorithms were tested on several data sets composed of DNA and morpholo gy ranging from 40 to 500 taxa. Various algorithms in POY show fundamentall y different properties within and between clusters. All algorithms are effi cient on the small cluster for the 40-taxon data set. On the large cluster, multibuilding exhibits excellent parallel efficiency, whereas parallel bui lding is inefficient. These results are independent of data set size. Branc h swapping in parallel shows excellent speed-up for 16 slave processors on the large cluster. However, there is no appreciable speed-up for branch swa pping with the further addition of slave processors (>16). This result is i ndependent of data set size. Ratcheting in parallel is efficient with the a ddition of up to 32 processors in the large cluster. This result is indepen dent of data set size. (C) 2001 The Willi Hennig Society.