Application Mapping and Optimization for CMP Based Architectures

Summary:

Chip Multiprocessors (CMPs) are becoming standard and primary building blocks for personal computers as well as large scale parallel machines, including supercomputers. In this thesis, our main focus is on performance-aware mapping and optimization of application threads onto multicore architectures. Specifically, we propose three different approaches, which are data-to-core mapping methodology, threadto- core mapping methodology, and cache-centric data assignment methodology that includes data-to-thread mapping. For demonstrating data-to-core mapping methodology, we propose two novel parallel formulations for the Barnes-Hut method on the Cell Broadband Engine architecture by considering technical specifications and limitations of the Cell architecture. Our experimental evaluation indicates that the Barnes-Hut method performs much faster on the Cell architecture compared to the reference architecture, an Intel Xeon based system. To present thread-to-core mapping methodology, we propose a framework that uses helper threads running in parallel with application threads, which dynamically observe the behavior of application threads and their data access patterns. These helper threads calculate data sharing among application threads, cluster them to be mapped to available cores, use cache counters to calculate the efficiency of a mapping, and make the mapping decision after considering the execution needs. Our final methodology provides a locality-aware mapping algorithm, which targets to assign computations with similar data access patterns of an application to the same core. Our algorithm divides computations of the application into chunks to provide load balancing, and a set of chunks with high similarity is grouped into bins to provide data locality. We consider the sparse matrix-vector multiplication as the reference application.

Özet:

Yongada Çoklu-İşlemciler (CMP), kişisel bilgisayarların yanı sıra büyük ölçekli paralel makinaların ve süper bilgisayarların standart ve temel yapıtaşlarını oluşturmaya başlamıştır. Bu tezdeki temel amacımız, performansı arttıran haritalama ve optimizasyon yöntemleri geliştirerek, uygulama izleklerini çok çekirdekli mimarilere atamaktır. Bunu başarabilmek için üç farklı yöntem sunmaktayız, bunlar veri-çekirdek eşleme metodu, izlek-çekirdek eşleme metodu ve önbellek merkezli veri-izlek eşleme metodudur. Veri-çekirdek eşleme metodunda, Barnes-Hut algoritmasının bir CMP olan Cell Broadband Engine Mimarisinin teknik özelliklerini ve limitlerini göz önünde bulunduran iki özgün paralel formulasyonunu önermekteyiz. Yapılan deneysel değerlendirme, Barnes-Hut metodunun Cell mimarisi üzerindeki performansının karşılaştırma yapılan referans mimarisi olan Intel Xeon tabanlı sisteme göre belirgin oranda daha hızlı olduğunu göstermektedir. İzlek-çekirdek eşleme metodunu sunmak için, uygulama izlekleri ile paralel çalışan yardımcı izlekler kullanan ve dinamik olarak uygulama izleklerinin davranışlarını ve eriştikleri veri düzenini gözlemleyen bir sistem önerilmiştir. Yardımcı izlekler uygulama izleklerinin veri paylaşım miktarını hesaplayarak, bunları çekirdeklere eşlenmeleri için gruplara ayırır, eşlemelerin verimliliğini hesaplayabilmek için ön bellek sayaçları kullanır, ve çalışma zamanı ihtiyaçlarına bağlı olarak eşleme kararını alır. önerilmiş olan son metodumuzda, benzer veri erişim şekline sahip olan hesaplamaları aynı çekirdeğe atamayı hedefleyen, veri yerelliğini sağlayan bir eşleme algoritması tasarlanmıştır. önerilen algoritma verilen uygulamanın hesaplamalarını yükün eşit dağılımını sağlayabilmek için parçalara ayırır ve veri yerelliliğini sağlamak için yüksek benzerliğe sahip olan parçalar gruplandırılırlar. Metodun performansını ölçmek için, referans uygulama olarak seyrek matris-vektör çarpımı kullanılmıştır.