A framework for task placement on multicore architectures

Abstract

Mevcut ¸cok ¸cekirdekli sistemler ¸cok sayıda i¸slemci ¸cekirde˘gine sahiptir ve yakınzamanda kullanılmaya ba¸slanacak olan exascale sistemlerde ¸cekirdek sayısının dahada artması beklenmektedir. Paralel i¸sleri i¸slemcilere yerle¸stirmek ¸cip i¸cindeki islemciler arasındaki ileti¸sim miktarını azalttı˘gından ¸cok ¸cekirdekli makinelerde performansı arttırıcı bir etkendir. Ayrıca bu y¨ontem i¸sletim sisteminin i¸s par¸cacıklarınıng¨o¸c etmesini ¨onleyerek veri yerelli˘ginin iyile¸stirilmesi de sa˘glamaktadır. Ancak, farklıuygulamalar ve makineler arasında en iyi performansı sa˘glayacak tek bir paraleli¸sleri i¸slemcilere yerle¸stirme algoritması bulunmamakta ¸c¨unk¨u her makinenin farklıbir topolojisi bulunmakta ve her uygulama farklı bir ileti¸sim ¨or¨unt¨us¨u sergilemektedir. Bir uygulama veya bir makine i¸cin en uygun algoritmayı belirlemek, fazladanprogramlama eforu gerektirmektedir. Yazılımcının bu y¨uk¨un¨u ortadan kaldırmaki¸cin, uygulama ¨or¨unt¨us¨une ve makine topolojisine ¨ozel e¸sleme algoritması ¨uretecekotomatik bir i¸s atama aracının gereklili˘gini savunmaktayız.Bu ama¸c do˘grultusunda bu tezde yazılımcıya i¸s par¸cacıklarını donanıma atamasında yardımcı olacak i¸s par¸cacı˘gı atama k¨ut¨uphanesini, BindMe aracını, sunuyoruz. BindMe, etkili bir i¸s yerle¸stirme ilkesini form¨ulize etmek i¸cin uygulamadakiileti¸sim ¨or¨unt¨ulerini kullanır ve en yeni e¸sleme algoritmalarını b¨unyesinde bulundurmaktadır. Buna ilave olarak, paralel i¸s par¸cacıklarının ortak ¨onceliklerini de˘gerlendirereke¸sleme dizisi ¨ureten ileti¸sim bilin¸cine dayalı bir e¸sleme algoritması olan ChoiceMap'isunuyoruz. ChoiceMap, ¸cekirdekler arası ileti¸sim hacmini azaltarak dengeli bir e¸slemeger¸cekle¸stirmektedir. Algoritma hem da˘gıtık, hem payla¸sımlı sistemlerde kullanılır.BindMe, b¨unyesinde ChoiceMap algoritmasını da e¸sleme se¸ceneklerinden biri olarakbulundurmaktadır. BindMe aracını, NAS paralel benchmark kapsamındaki bir ¸cokuygulamayla de˘gerlendirdik. Bulgularımız g¨osteriyor ki, uygulama ¨or¨unt¨ulerine en iyi uyacak e¸sleme ilkesini se¸cmek, uygulamanın verimini arttırmakta ve tek bir ¸ce¸site¸sleme algoritması farklı uygulamalarda en iyi performansı sa˘glayamamaktadır.

Current multicore machines have a large number of cores and the number of coresis expected to increase in upcoming exascale multicore machines. Binding paralleltasks to cores according to a placement policy is one of the key aspects to achievegood performance in multicore machines because it can reduce on-chip communication among parallel threads. Binding also prevents operating system from migratingthreads, which improves data locality. However, there is no single mapping policy thatworks best among all different kinds of applications and machines because each machine has a different topology and each application exhibits different communicationpattern. Determining the best policy for a given application and for a given machinerequires extra programming effort. To relieve the programmer from that burden, weargue the need for an automated task binding tool that generates mapping policyspecific to the machine topology and application behaviour.We present BindMe, a thread binding library, that assists programmer to bindthreads to underlying hardware. BindMe incorporates state-of-the- art mapping algorithms which use communication pattern in an application to formulate an efficienttask placement policy. We also introduce ChoiceMap, a communication aware mapping algorithm that generates a mapping sequence by respecting mutual priorities ofparallel tasks. ChoiceMap performs a fair mapping by reducing communication volume among cores. The algorithm can be used both in shared memory and distributedmemory systems. ChoiceMap is incorporated in BindMe and can be used as one ofthe mapping options. We have tested BindMe with various applications from NASparallel benchmark. Our results show that choosing a mapping policy that best suitsthe application behavior can increase its performance and no single policy gives thebest performance across different applications.