Bilkent University
Department of Computer Engineering
S E M I N A R
Locality Aware Task Mapping by Hypergraph Partitioning
Mehmet Başaran
MSc Student
Computer Engineering Department
Bilkent UniversityThe recent developments in computer science, all gathered under the name “Parallel Computing”, paved the way for fundamental alterations in programming paradigms. This required programmers to move out of their comfort zone to exploit benefits of this new paradigm. They need to divide their code into several segments which will execute in parallel while respecting execution order and other dependencies. However, this is not the complete picture. Some of the problems existed long before this paradigm and the mainstream use of multicore processors for casual users. Advancements in CPU side dwarfed memory. As a result CPU got multiple times faster than memory. This rendered additional computational power useless, since we need to transfer data to CPU before we can even work on it. To address this problem, several techniques are used, namely latency hiding (with the help of prefetchers & performance counters). Although this tools are useful, they cannot do much without inside information about the code and may even slow down systems with multiple processors. To avoid constantly fetching data from memory to CPU caches, code segments should be grouped (for each processor) and ordered to provide optimal performance. This way, same data won't be fetched from memory over and over (because of eviction), Grouping is conventionally done on task dependency graphs (TDG). Using graphs to group for only 2 threads will yield optimum results. However, grouping several tasks using a graph as a data structure will fail to determine optimum groups and order. This problem can be solved accurately by using hypergraph representation of TDG.
DATE: 25 March, 2013, Monday @ 16:40
PLACE: EA409