Optimization of Block-based Cholesky Factorization for Modern Computer Systems

Linear systems and the solving of those is an important tool in many areas of science. The solving of linear systems is an operation of high complexity, and there are applications where systems of thousands of variables are used. Therefore, it is important to use methods and algorithms that can take full advantage of the performance of modern computers. Factorizing a matrix that represents a linear system makes solving it faster. If the matrix is symmetrical and positive definite Cholesky factorization can be used. J. Chen et. al. (2013) studied a block-based algorithm that gives better performance by using the cache memory more efficently when the matrix size increases. Since then, the conditions have changed. The cache memory of modern processors are subject to constant change, and modern processors capability of improving performance by vectorization have been vastly improved. This report examine how this block-based Cholesky factorization can be optimized for modern Intel processors. By using AVX2 instructions, the parts of the algorithm where most of the arithmetic operations are performed are vectorized. The report also study how the optimal block size, as well as how the breaking point between the naive algorithm and the block-based algorithm changes as the hardware develops. Using a fairly simple implementation with vectorization, the time required to factorize matrices of all sizes are cut in half. The breaking point between the naive and the block-based algorithm is now at matrices of sizes as small as 100 × 100. This is an interesting fact as prior research showed a trend where the breaking point seemed to move towards bigger matrices as the hardware developed.Linjära system och lösning av dessa är ett viktigt verktyg inom många vetenskapliga områden. Lösning av linjära system är en operation med hög komplexitet, samtidigt som det finns tillämpningar där system med tusentals variabler är vanligt. Därför är det viktigt att använda metoder och algoritmer som utnyttjar datorns prestanda maximalt. Genom att faktorisera en matris som representerar ett linjärt system kan det lösas snabbare. Är matrisen symmetrisk och positivt definit kan Choleskyfaktorisering användas. J. Chen et. al (2013) undersökte en blockbaserad algoritm som ger bättre prestanda genom förbättrad cachehantering. Förutsättningarna har dock förändrats sedan deras undersökning. Dels är processorns cacheminnen under ständig utveckling, och dels så har moderna processorer kraftigt förbättrade möjligheter att öka prestandan med hjälp av vektorisering. Denna rapport undersöker hur denna blockbaserade Choleskyfaktorisering kan optimeras för moderna Intelprocessorer. Genom att använda AVX2-instruktioner vektoriseras de delar av algoritmen där flest operationer utförs. Samtidigt undersöks hur valet av blockstorlek påverkas av, samt hur brytpunkten mellan en klassisk, naiv algoritm och den blockbaserade algoritmen förändras i takt med att hårdvaran utvecklas. Med hjälp av en relativt enkel implementation av vektorisering halveras tiden för att faktorisera matriser oavsett storlek. Brytpunkten mellan den naiva och de blockbaserade algoritmerna sker nu redan runt 100 × 100-matriser. Detta är extra intressant då utvecklingen tidigare gått mot allt större matriser