qskeleton

qskeleton: parallel polyhedral computing software based on the double description method and Fourier-Motzkin elimination. We present open-source polyhedral computing software qskeleton. It implements the Fourier-Motzkin elimination (FME) method for variable elimination and a variation of the double description method (DDM) for computing a dual representation of convex polyhedra. The software is an ideological descendant of N.Yu. Zolotykh’s skeleton package and aims to combine its advancements with other approaches, such as using some ideas of the Quickhull algorithm in the DDM or combining the graph test of skeleton with other accelerating data structures for adjacency testing in DDM / Chernikov rules in FME. Parallel computing is an important direction of development of qskeleton. It supports shared-memory OpenMP parallelism. We are currently developing a version for Intel Xeon Phi coprocessors, which offer 60 cores on shared memory and serve as a promising alternative to GPUs in terms of accelerators with easier programming. Our first results show a modest (up to 1.5 x) advantage of Xeon Phi over an 8-core CPU. However, there is a potential to improve the performance on Xeon Phi by efficiently utilizing vector (SIMD) instructions. We will present evaluation of suitability of the DDM and FME for Xeon Phi coprocessors and our experience of porting and optimizing the code.